[Last time](https://forum.azimuthproject.org/discussion/2210/lecture-37-chapter-3-presentations-of-categories/p1) we saw a graph that could be used for designing databases:

This graph is not a database; it's just a kind of template for a database. Fong and Spivak call it a **database schema**. To create an actual database using this schema, you'd have to specify:

* a set of employees
* a set of departments
* a set of strings (that is, strings of symbols)
* a function mapping each employee to the department they work in
* a function mapping each employee to their manager
* a function mapping each department to its secretary
* a function mapping each employee to their first name
* a function mapping each department to its name.

You could do this using a table or spreadsheet, or some other way. See the start of Chapter 3 for more on this!

What does this have to do with category theory? _A lot!_

We've seen that this "database schema" is really a graph \$$G\$$. And we saw that from a graph we can get a category \$$\mathbf{Free}(G)\$$ called the "free category on \$$G\$$". This has nodes of the graph as objects and paths as morphisms.

So, our database schema gives a category \$$\mathbf{Free}(G)\$$. The objects in this category are things like \$$\textrm{Employee}\$$ and \$$\textrm{Department}\$$. The morphisms are things like \$$\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}\$$.

To get an actual database, we need to provide a _set_ for each _object_ of \$$\mathbf{Free}(G)\$$, and a _function_ for each _morphism_ of \$$\mathbf{Free}(G)\$$.

When we do this, we're providing some sort of map from the category \$$\mathbf{Free}(G)\$$ to the category \$$\textbf{Set}\$$. A map between categories is called a "functor": it sends objects to objects, and morphisms to morphisms... and it should also obey a few obvious rules, which I'll explain in a second.

But first, enjoy the beauty of this idea! A database schema is really a category, while an actual database is a functor from that category to \$$\textbf{Set}\$$. The database schema has "abstract" objects and morphisms like \$$\textrm{Employee}\$$ and \$$\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}\$$, while the functor makes these "concrete", turning them into actual sets and functions!

So what's a functor, exactly?

**Definition.** Given categories \$$\mathcal{C}\$$ and \$$\mathcal{D}\$$, a **functor** from \$$\mathcal{C}\$$ to \$$\mathcal{D}\$$, written \$$F: \mathcal{C} \to \mathcal{D} \$$, consists of:

1. A function sending objects of \$$\mathcal{C}\$$ to objects of \$$\mathcal{D}\$$. This is usually called \$$F\$$ as well, so we have \$$F: \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D}) \$$.

2. For each pair of objects \$$x,y \in \mathrm{Ob}(\mathcal{C})\$$, a function sending each morphism \$$f: x \to y\$$ to a morphism \$$F(f) : F(x) \to F(y) \$$. As you can see, we're calling this function \$$F\$$ too! So, it's a function

$F: \mathcal{C}(x,y) \to \mathcal{D}(F(x),F(y)) .$

Remember, \$$\mathcal{C}(x,y)\$$ is the set of morphisms from \$$x\$$ to \$$y\$$ in \$$\mathcal{C}\$$.

We demand that:

a) \$$F\$$ preserve composition: \$$F(g \circ f) = F(g) \circ F(f) \$$ whenever \$$f\$$ and \$$g\$$ are morphisms that can be composed in \$$\mathcal{C}\$$.

b) \$$F\$$ preserves identities: \$$F(1_x) = 1_{F(x)}\$$ whenever \$$x\$$ is an object of \$$\mathcal{C}\$$.

That's it!

It may freak you out that we're using \$$F\$$ to mean the functor, the function that describes what this functor does to objects, _and_ all the functions that describe what \$$F\$$ does to morphisms. However, this turns out not to be a problem. It would be much worse to have separate notations for all these things. You should think of them all as a single package: \$$F\$$.

You may wonder about conditions a) and b). They seem to have shown up by magic. How do they arise in our study of databases?

Here's an example. Take \$$\mathcal{C} = \mathbf{Free}(G)\$$ and look at the morphisms \$$\textrm{WorksIn} : \textrm{Employee} \to \textrm{Department}\$$ and
\$$\textrm{DepartmentName} : \textrm{Department} \to \textrm{String}\$$. Then choose a functor \$$F : \mathcal{C} \to \mathbf{Set}\$$. We must have

$F(\textrm{DepartmentName} \circ \textrm{WorksIn}) = F(\textrm{DepartmentName}) \circ F(\textrm{WorksIn}) .$

**Puzzle 109.** What does this mean, in practical terms?

There's a lot more to say, but not now!

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Chapter_3)**