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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2018
|
| Subjects: |
| _version_ | 1826265993950789632 |
|---|---|
| author | Gibbons, J Henglein, F Hinze, R Wu, N |
| author_facet | Gibbons, J Henglein, F Hinze, R Wu, N |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T20:32:15Z |
| format | Journal article |
| id | oxford-uuid:316e6be3-772f-4f27-95e7-1e3ba834b002 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:32:15Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:316e6be3-772f-4f27-95e7-1e3ba834b0022022-03-26T13:08:02ZRelational algebra by way of adjunctionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:316e6be3-772f-4f27-95e7-1e3ba834b002Software and its engineering → SemanticsInformation systems → Relational database query languagesTheory of computation → Categorical semanticsSymplectic Elements at OxfordAssociation for Computing Machinery2018Gibbons, JHenglein, FHinze, RWu, NBulk 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. |
| spellingShingle | Software and its engineering → Semantics Information systems → Relational database query languages Theory of computation → Categorical semantics Gibbons, J Henglein, F Hinze, R Wu, N Relational algebra by way of adjunctions |
| title | Relational algebra by way of adjunctions |
| title_full | Relational algebra by way of adjunctions |
| title_fullStr | Relational algebra by way of adjunctions |
| title_full_unstemmed | Relational algebra by way of adjunctions |
| title_short | Relational algebra by way of adjunctions |
| title_sort | relational algebra by way of adjunctions |
| topic | Software and its engineering → Semantics Information systems → Relational database query languages Theory of computation → Categorical semantics |
| work_keys_str_mv | AT gibbonsj relationalalgebrabywayofadjunctions AT hengleinf relationalalgebrabywayofadjunctions AT hinzer relationalalgebrabywayofadjunctions AT wun relationalalgebrabywayofadjunctions |