# What categories are described by relational programming languages?

I know that lambda calculus is the language of cartesian closed categories.

As I understand it, relational programming systems (that, as the name implies describe a computation in terms of relations) would then operate on those, but also other categories (since functions are a special case of relations).

So what categories do relational databases/languages describe?

• While functions are a special case of relations, the converse is also true: relations are a special case of functions. The two typical ways to express this are: (1) to take the graph of the relation -- e.g. a binary relation between $X$ and $Y$ can be identified with a subset of $X \times Y$, which in turn is a monic map with codomain $X \times Y$; (2) as a function whose codomain consists of truth values. – Hurkyl Jun 6 '18 at 3:20
• Adding to @Hurkyl's comment, a relation between $X$ and $Y$ is the same as a function $X \to 2^Y$, so the category Rel of relations is the Kleisli category of the powerset monad on Set. Also perhaps more interestingly, Rel is a model for linear logic, see e.g. cs.man.ac.uk/~schalk/notes/llmodel.pdf – arkeet Jun 27 '18 at 1:41

$$\textbf{Relations are to allegories as functions are to categories.}$$