Reference. Relational algebra by way of adjunctions

Bulk types such as sets, bags, and lists are monads, and therefore support a notation for database queries based on comprehensions. This fact is the basis of much work on database query languages. The monadic structure easily explains most of standard relational algebra—specifically, selections and projections—allowing for an elegant mathematical foundation for those aspects of database query language design. Most, but not all: monads do not immediately offer an explanation of relational join or grouping, and hence important foundations for those crucial aspects of relational algebra are missing. The best they can offer is cartesian product followed by selection. Adjunctions come to the rescue: like any monad, bulk types also arise from certain adjunctions; we show that by paying due attention to other important adjunctions, we can elegantly explain the rest of standard relational algebra. In particular, graded monads provide a mathematical foundation for indexing and grouping, which leads directly to an efficient implementation, even of joins.

Cite

Cite as @gibbons-2018-relational (helia, typst) · \cite{gibbons-2018-relational} (LaTeX)
BibTeX
bibtex · 1 line
@article{gibbons-2018-relational, title={Relational algebra by way of adjunctions}, volume={2}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3236781}, DOI={10.1145/3236781}, number={ICFP}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Gibbons, Jeremy and Henglein, Fritz and Hinze, Ralf and Wu, Nicolas}, year={2018}, month=July, pages={1–28} }
hayagriva YAML (typst)
yaml · 18 lines
gibbons-2018-relational:
  type: article
  title: Relational algebra by way of adjunctions
  author:
  - Gibbons, Jeremy
  - Henglein, Fritz
  - Hinze, Ralf
  - Wu, Nicolas
  date: 2018-07
  page-range: 1-28
  serial-number:
    doi: 10.1145/3236781
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: ICFP
    volume: 2
Cited by (1)

Algorithmics bird-2021-algorithmics

DOI
Cites 39 works (2 here)
With notes (2)

Applicative programming with effects mcbride-2008-applicative

In this article, we introduce Applicative functors – an abstract characterisation of an applicative style of effectful programming, weaker than Monads and hence more widespread. Indeed, it is the ubiquity of this programming pattern that drew us to the abstraction. We retrace our steps in this article, introducing the applicative pattern by diverse examples, then abstracting it to define the Applicative type class and introducing a bracket notation that interprets the normal application syntax in the idiom of an Applicative functor. Furthermore, we develop the properties of applicative functors and the generic operations they support. We close by identifying the categorical structure of applicative functors and examining their relationship both with Monads and with Arrow.
PDF · DOI · pldb

Remarks on isomorphisms in typed lambda calculi with empty and sum types fiore-2006-remarks

DOI
External (37)
gibbons-2018-relational reference entries/refs/gibbons-2018-relational/gibbons-2018-relational.hel