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

<p>Two of the key figures in this area are <a href="http://homepages.inf.ed.ac.uk/opb/" rel="noreferrer">Peter Buneman</a> and <a href="http://db.inf.uni-tuebingen.de/team/TorstenGrust.html" rel="noreferrer">Torsten Grust</a>. 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. </p>

<p>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 <a href="https://ncatlab.org/nlab/files/WadlerMonads.pdf" rel="noreferrer">Philip Wadler's monad comprehension syntax</a> to give a categorically-inspired calculus for queries with a rich equational theory.  </p>

<p>Indeed, Buneman et al's query system <a href="http://www.comp.nus.edu.sg/~wongls/projects/kleisli/" rel="noreferrer"><em>Kleisli</em></a> got its name from the fact that monads are sometimes called "Kleisli triples". </p>

<p>Grust's PhD thesis, <a href="https://kops.uni-konstanz.de/bitstream/handle/123456789/709/312_1.pdf?sequence=1" rel="noreferrer"><em>Comprehending Queries</em></a>, works this out these ideas in detail, including the use of monad morphisms to model aggregation operators (like <code>sum</code> and <code>count</code>). Grust and his group also built a system, <a href="http://db.inf.uni-tuebingen.de/projects/ferry.html" rel="noreferrer"><em>Ferry</em></a>, which studied how to integrate databases into programming languages. </p>

<p>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 href="http://homepages.inf.ed.ac.uk/jcheney/publications/cheney13icfp.pdf" rel="noreferrer"><em>A practical theory of language-integrated query</em></a>), but the basic issue has a very nice categorical formulation. Relational algebra only uses the <em>monoidal</em> 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)$. </p>

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

<p>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 <a href="http://arxiv.org/abs/0904.2012" rel="noreferrer"><em>Simplicial Databases</em></a>. 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. </p>

<p>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 <a href="http://www.datomic.com/" rel="noreferrer"><em>Datomic</em></a> feature query languages based on Datalog. My PhD student, <a href="http://www.rntz.net" rel="noreferrer">Michael Arntzenius</a>, and I have studied the  semantics of Datalog, and come up with a functional analogue we call <a href="http://www.rntz.net/datafun/" rel="noreferrer"><em>Datafun</em></a>, which has a pretty categorical interpretation in terms of the categories of posets and semilattices.</p>

CC BY-SA 3.0
2017-05-17T10:59:50.383Z
2017-05-17T10:59:50.383Z
Neel Krishnaswami
<p>I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory. </p>

<p>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?</p>

<p><strong>Background:</strong>
A while ago I read <a href="http://math.mit.edu/~dspivak/CT4S.pdf" rel="noreferrer">David Spivak's <em>Category Theory for Scientists</em></a> 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.</p>

<p>However, recently I have been learning about <a href="https://en.wikipedia.org/wiki/SQL" rel="noreferrer">SQL</a> queries and two <a href="https://en.wikipedia.org/wiki/R_(programming_language)" rel="noreferrer">R</a> packages for data manipulation: <a href="https://cran.rstudio.com/web/packages/dplyr/vignettes/introduction.html" rel="noreferrer">dplyr</a> and <a href="https://cran.r-project.org/web/packages/data.table/data.table.pdf" rel="noreferrer">data.table</a>. SQL can apparently express <a href="http://www.cs.cornell.edu/projects/btr/bioinformaticsschool/slides/gehrke.pdf" rel="noreferrer">much of the ideas</a> of Codd's relational algebra/calculus/model, but <a href="https://en.wikipedia.org/wiki/Relational_model#SQL_and_the_relational_model" rel="noreferrer">not all</a>. Moreover, the author of dplyr, Hadley Wickham, has <a href="http://www.stat.wvu.edu/~jharner/courses/stat623/docs/tidy-dataJSS.pdf" rel="noreferrer">stated explicitly</a> that his philosophy underlying the package is based on Codd's work on relational algebra, and the basic commands of <a href="https://cran.r-project.org/web/packages/data.table/vignettes/datatable-intro.html" rel="noreferrer">data.table</a> map fairly well to commands in SQL and dplyr.</p>

<p>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 <a href="https://cran.r-project.org/web/packages/purrr/purrr.pdf" rel="noreferrer">purrr</a> package for R, the fact that <a href="https://en.wikipedia.org/wiki/Apache_Spark" rel="noreferrer">Apache Spark</a> is written in <a href="https://en.wikipedia.org/wiki/Scala_(programming_language)" rel="noreferrer">Scala</a>, and technologies related to <a href="https://en.wikipedia.org/wiki/MapReduce" rel="noreferrer">MapReduce</a>.</p>

<p>All of this sort of suggests to me that there <em>should</em> 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.</p>

<p><strong>EDIT:</strong> Apparently David Spivak has worked on a "<a href="http://categoricaldata.net/fql.html" rel="noreferrer">functorial query language (FQL)</a>". This sounds like it might be an application of such a theoretical connection, provided it exists.</p>

<p><strong>Note:</strong> I am not sure if "relational-structures" is the appropriate tag for discussion of relational databases or relational algebra/calculus. <a href="https://en.wikipedia.org/wiki/Structure_(mathematical_logic)#Homomorphism_problem" rel="noreferrer">This Wikipedia article</a> suggests they might be connected, but ultimately I don't know what the phrase "relational structure" means. Please feel free to re-tag.</p>

CC BY-SA 3.0
2017-05-16T21:35:10.253Z
Have you seen work by Tannen and Buneman, e.g. [A Structural Approach to Query Language Design](http://link.springer.com/chapter/10.1007%2F978-3-662-05372-0_14)?
reinierpost
CC BY-SA 3.0
2017-05-17T05:16:50.747Z
@reinierpost I have not, but I will look at it.
Chill2Macht
<reference-request><ct.category-theory><db.databases><relational-structures>
Is there a relationship between relational algebra/calculus and category theory?
Chill2Macht
# Is there a relationship between relational algebra/calculus and category theory?

(Asked by: username_0 on 2017-05-15)

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*](http://math.mit.edu/~dspivak/CT4S.pdf) 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](https://en.wikipedia.org/wiki/SQL) queries and two [R](https://en.wikipedia.org/wiki/R_(programming_language)) packages for data manipulation: [dplyr](https://cran.rstudio.com/web/packages/dplyr/vignettes/introduction.html) and [data.table](https://cran.r-project.org/web/packages/data.table/data.table.pdf). SQL can apparently express [much of the ideas](http://www.cs.cornell.edu/projects/btr/bioinformaticsschool/slides/gehrke.pdf) of Codd's relational algebra/calculus/model, but [not all](https://en.wikipedia.org/wiki/Relational_model#SQL_and_the_relational_model). Moreover, the author of dplyr, Hadley Wickham, has [stated explicitly](http://www.stat.wvu.edu/~jharner/courses/stat623/docs/tidy-dataJSS.pdf) that his philosophy underlying the package is based on Codd's work on relational algebra, and the basic commands of [data.table](https://cran.r-project.org/web/packages/data.table/vignettes/datatable-intro.html) 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](https://cran.r-project.org/web/packages/purrr/purrr.pdf) package for R, the fact that [Apache Spark](https://en.wikipedia.org/wiki/Apache_Spark) is written in [Scala](https://en.wikipedia.org/wiki/Scala_(programming_language)), and technologies related to [MapReduce](https://en.wikipedia.org/wiki/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)](http://categoricaldata.net/fql.html)". 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](https://en.wikipedia.org/wiki/Structure_(mathematical_logic)#Homomorphism_problem) suggests they might be connected, but ultimately I don't know what the phrase "relational structure" means. Please feel free to re-tag.

**Tags:** reference-request, ct.category-theory, db.databases, relational-structures

> **Comments:**
> **username_1**: Have you seen work by Tannen and Buneman, e.g. [A Structural Approach to Query Language Design](http://link.springer.com/chapter/10.1007%2F978-3-662-05372-0_14)?  
> **username_0**: @username_1 I have not, but I will look at it.  

---

## 1 answers

### Answer by username_2 on 2017-05-17. Score: 20

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](http://homepages.inf.ed.ac.uk/opb/) and [Torsten Grust](http://db.inf.uni-tuebingen.de/team/TorstenGrust.html). 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](https://ncatlab.org/nlab/files/WadlerMonads.pdf) to give a categorically-inspired calculus for queries with a rich equational theory.

Indeed, Buneman et al's query system [*Kleisli*](http://www.comp.nus.edu.sg/~wongls/projects/kleisli/) got its name from the fact that monads are sometimes called "Kleisli triples".

Grust's PhD thesis, [*Comprehending Queries*](https://kops.uni-konstanz.de/bitstream/handle/123456789/709/312_1.pdf?sequence=1), 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*](http://db.inf.uni-tuebingen.de/projects/ferry.html), 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*](http://homepages.inf.ed.ac.uk/jcheney/publications/cheney13icfp.pdf)), 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*](http://arxiv.org/abs/0904.2012). 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*](http://www.datomic.com/) feature query languages based on Datalog. My PhD student, [Michael Arntzenius](http://www.rntz.net), and I have studied the semantics of Datalog, and come up with a functional analogue we call [*Datafun*](http://www.rntz.net/datafun/), which has a pretty categorical interpretation in terms of the categories of posets and semilattices.


---

