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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Hurkyl Jun 6 '18 at 3:20
  • 2
    $\begingroup$ 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 $\endgroup$ – arkeet Jun 27 '18 at 1:41

Relational languages may be described by allegories.

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

An allegory is a category where the arrows are considered to be (some form of abstract) relation and are endowed with the notions one expects of relations: Converse, an order, and intersection --to name a few.

An allegory can be thought of a a middle ground between a category and a topos.

As your remark points out, the arrows --i.e., relations-- in an allegory that are functional, in nearly the same way as in set theory, form a category themselves.

  • $\begingroup$ It may be worth clarifying that "relation" as used in this post refers specifically to binary relations. $\endgroup$ – Hurkyl Jun 27 '18 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.