Is there a relationship between relational algebra/calculus and category theory?

Question

I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory.

Is there any relationship between these two approaches? Are they in some sense equivalent? Is there any introductory work explaining how both of these frameworks explain relational databases?

Background: A while ago I read David Spivak's Category Theory for Scientists which spent quite some time discussing how category theory could be applied to understand the theory of relational databases. However, having little personal experience about what relational databases are or why they are useful, at the time I did not fully appreciate the depths of insight found in the book.

However, recently I have been learning about SQL queries and two R packages for data manipulation: dplyr and data.table. SQL can apparently express much of the ideas of Codd's relational algebra/calculus/model, but not all. Moreover, the author of dplyr, Hadley Wickham, has stated explicitly that his philosophy underlying the package is based on Codd's work on relational algebra, and the basic commands of data.table map fairly well to commands in SQL and dplyr.

I also know that category theory influences a lot of programmers using functional programming languages like Haskell. However, I am not really aware of there being any use of functional programming for data manipulation or data science, besides Hadley Wickham's purrr package for R, the fact that Apache Spark is written in Scala, and technologies related to MapReduce.

All of this sort of suggests to me that there should be some sort of relationship between category theory and Codd's relational algebra/calculus, but I have never heard of anyone making such a connection explicit or explain how it underlies the design decisions in popular data manipulation and relational database technologies. So I also suspect I could be entirely wrong.

EDIT: Apparently David Spivak has worked on a "functorial query language (FQL)". This sounds like it might be an application of such a theoretical connection, provided it exists.

Note: I am not sure if "relational-structures" is the appropriate tag for discussion of relational databases or relational algebra/calculus. This Wikipedia article suggests they might be connected, but ultimately I don't know what the phrase "relational structure" means. Please feel free to re-tag.

Answer 1

Categorical approaches to query languages is a bit of a niche interest, but I think it's a very interesting niche!

Two of the key figures in this area are Peter Buneman and Torsten Grust. Obviously, they didn't do all the work, but if you start with their papers and trace out the citation graph, you'll get pretty good coverage of the area.

The central observation that they work from is that since a relation can be viewed as a set of tuples, the powerset functor can be interpreted as taking a tuple type to the type of relations over that tuple. Then, the fact that the powerset functor forms a monad means that you can use ideas inspired by Philip Wadler's monad comprehension syntax to give a categorically-inspired calculus for queries with a rich equational theory.

Indeed, Buneman et al's query system Kleisli got its name from the fact that monads are sometimes called "Kleisli triples".

Grust's PhD thesis, Comprehending Queries, works this out these ideas in detail, including the use of monad morphisms to model aggregation operators (like sum and count). Grust and his group also built a system, Ferry, which studied how to integrate databases into programming languages.

One of the main issues in this work (and also in Kleisli, if memory serves), is that monadic query languages tend to be a bit more expressive than relational algebra -- they permit queries to handle sets of sets. Compiling this to SQL or relational algebra requires some care (for example, see Cheney et al's A practical theory of language-integrated query), but the basic issue has a very nice categorical formulation. Relational algebra only uses the monoidal structure of the powerset functor, i.e., the existence of a cartesian product natural transformation $(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$; and monadic query languages also demand the join, $\mu : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X)$.

That's probably the primary stream of work on categorical approaches to query languages.

A new idea (which unfortunately hasn't gotten as much traction as I think it deserves) is David Spivak's work on using simplicial sets to model databases -- see Simplicial Databases. The central innovation is that the simplicial structure permits explicitly modelling the whole database schema including the relationships between tables (eg, the system of foreign keys), and this enables giving semantics to schema update operations.

Another deviation from standard query languages are restricted logic programming languages such as Datalog, which can be understood as relational algebra plus a fixed point operator. Fixed points permit expressing things like transitive closure queries, and so new databases like Datomic feature query languages based on Datalog. My PhD student, Michael Arntzenius, and I have studied the semantics of Datalog, and come up with a functional analogue we call Datafun, which has a pretty categorical interpretation in terms of the categories of posets and semilattices.