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
Cited by (1)
Algorithmics bird-2021-algorithmics
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.
Remarks on isomorphisms in typed lambda calculi with empty and sum types fiore-2006-remarks
External (37)
- Email correspondence (Jacques Carette, personal communication) (2018)
- Finally, safely-extensible and efficient language-integrated query (2016)
- Towards a Formal Theory of Graded Monads (2016)
- Comprehending Ringads - For Phil Wadler, on the Occasion of his 60th Birthday (2016)
- Implicit Parallelism through Deep Language Embedding (2015)
- Glasgow Haskell Compiler Users’ Guide (2015)
- Cakes, Custard and Category Theory (2015)
- Parametric effect monads and semantics of effect systems (2014)
- The Semantic Marriage of Monads and Effects (2014)
- Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries (2013)
- Haskell Boards the Ferry: Database-Supported Program Execution for Haskell (2011)
- Bringing back monad comprehensions (2011)
- Generic multiset programming with discrimination-based joins and symbolic Cartesian products (2010)
- Confessions of a used programming language salesman (2007)
- Comprehensive comprehensions (2007)
- Links: Web Programming without Tiers (2006)
- Leveraging .NET meta-programming components from F#: integrated queries and interoperable heterogeneous execution (2006)
- Category Theory (2006)
- An Introduction to Database Systems (8th ed.) (2004)
- Fun with phantom types (2003)
- A Semi-Monad for Semi-Structured Data (2001)
- Generalizing generalized tries (2000)
- Kleisli, a functional query system (2000)
- How to Comprehend Queries Functionally (1999)
- Query Languages for Bags and Aggregate Functions (1997)
- A generalization of the trie data structure (1995)
- Comprehension syntax (1994)
- Tarski's High School Identities (1993)
- Basic Category Theory for Computer Scientists (1991)
- Comprehensions, a Query Notation for DBPLs (1991)
- Comprehending monads (1990)
- Programming with Sets (1986)
- Access path selection in a relational database management system (1979)
- Application of Program Transformation to Program Synthesis (1975)
- Two Constructions on Lax Functors (1972)
- 10.1145/2500365.2500586
- 10.1145/2213556.2213565