Databases are Categories

http://blog.ezyang.com/2010/06/databases-are-categories/

by sz • 16 years ago

24 2 16 years ago

blog.ezyang.com

bitdiddle• 16 years ago

I would think Freyd and Scedrov's work on Allegories (replace functions in categories with relations) would be more suitable for relational databases. That said I'm somewhat skeptical of the use of category theory as more than just a beautiful descriptive language. As someone once mentioned, "it's all just definitions, there are no theorems", which is a bit of a stretch but there is truth in it.

Mathematically a function is just a special case of a relation. I like to think of relations, as they might be modeled as columns of a table, as "extensional" (they relate things to one another), functions are more like attributes. Storing relations in tables involves a commitment to a schema. This is the beauty of a document store such as CouchDB. A document is a uniquely identified collection of name-value pairs. There's nothing that prevents one from viewing these values as other entities but I like to model them as attributes. In this sense document stores seem to occupy a sweet spot in between relational databases and graph databases, such as RDF where every instance is just part of a labeled graph, or k-v stores where the values can be anything.

However at the end of the day, databases are all about b-trees and page boundaries and the Yoneda embedding just isn't going to help you with that, in my opinion.

[1] http://en.wikipedia.org/wiki/Allegory_(category_theory)

ekidd• 16 years ago

One of the classic papers on category theory and databases is "Comprehending Queries"[1], which is ultimately the basis for Microsoft's LINQ. In one sense, it's a fairly straightforward paper: Joining two tables is just a special case of a list comprehension, which the paper later transforms into optimizable combinators. Nonetheless, the paper presents a clean and elegant framework, and it lays out the category theory quite well.

As for category theory being mostly definitions, and not so much theorems, well, there's some truth in that. But don't underestimate the power of well-chosen definitions. An enormous number of mathematical structures are either topoi or closed cartesian categories. Once you understand how to map a closed cartesian category onto the lambda calculus, for example, you can design some pretty exotic programming languages. And many of the purely mathematical uses of category theory have a similar quality—smuggling theorems from one branch of mathematics to another. (One pretty reasonable introduction to category theory is "Basic Category Theory for Computer Scientists"[2], but there may be something better.)

[1] http://www.inf.uni-konstanz.de/dbis/publications/download/TG... [2] http://www.amazon.com/Category-Computer-Scientists-Foundatio...

Databases are Categories

Related Stories