3.6: Summary and further reading

Congratulations on making it through one of the longest chapters in the book! We apologize for the length, but this chapter had a lot of work to do. Namely it introduced the “big three” of category theory—categories, functors, and natural transformations as well as discussed adjunctions, limits, and very briefly colimits.

That’s really quite a bit of material. For more on all these subjects, one can consult any standard book on category theory, of which there are many. The bible (old, important, seminal, and requires a priest to explain it) is [Mac98]; another thorough introduction is [Bor94]; a logical perspective is given in [Awo10]; a computer science perspective is given in [BW90] and [Pie91] and [Wal92]; math students should probably read [Lei14] or [Rie17] or [Gra18]; a general audience might start with [Spi14a].

We presented categories from a database perspective, because data is pretty ubiq- uitous in our world. A database schema—i.e. a system of interlocking tables can be captured by a category C, and filling it with data corresponds to a functor C → Set. Here Set is the category of sets, perhaps the most important category to mathematicians.

The perspective of using category theory to model databases has been rediscovered several times. It seems to have first been discussed by various authors around the mid-90’s [IP94; CD95; PS95; TG96]. Bob Rosebrugh and collaborators took it much further in a series of papers including [FGR03; JR02; RW92]. Most of these authors tend to focus on sketches, which are more expressive categories. Spivak rediscovered the idea again quite a bit later, but focused on categories rather than sketches, so as to have all three data migration functors ∆, Σ, Π; see [Spi12; SW15b]. The version of this story presented in the chapter, including the white and black nodes in schemas, is part of a larger theory of algebraic databases, where a programming language such as Java or Haskell is attached to a database. The technical details are worked out in [Sch+17], and its use in database integration projects can be found in [SW15a; Wis+15].

Before we leave this chapter, we want to emphasize two things: coherence conditions and universal constructions.

Coherence conditions. In the definitions of category, functor, and natural transforma- tions, we have data (indexed by (i)) that is required to satisfy certain properties (indexed by (a)). Indeed, for categories it was about associativity and unitality of composition, for functors it was about respecting composition and identities, and for natural trans- formations it was the naturality condition. These conditions are often called coherence conditions: we want the various structures to cohere, to work well together, rather than to flop around unattached.

Understanding why these particular structures and coherence conditions are “the right ones” is more science than mathematics: we empirically observe that certain combinations result in ideas that are both widely applicable and also strongly compo- sitional. That is, we become satisfied with coherence conditions when they result in beautiful mathematics down the road.

Universal constructions. Universal constructions are one of the most important themes of category theory. Roughly speaking, one gives some specified shape in a category and says “find me the best solution!” And category theory comes back and says “do you want me to approximate from the left or the right (colimit or limit)?” You respond, and either there is a best solution or there is not. If there is, it’s called the (co)limit; if there’s not we say “the (co)limit does not exist.”

Even data migration fits this form. We say “find me the closest thing in D that matches my C-instance using my functor F : C → D.” In fact this approach known as Kan extensions—subsumes the others. One of the two founders of category theory, Saunders Mac Lane, has a section in his book [Mac98] called “All concepts are Kan extensions,” a big statement, no?