Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • Communities & Collections
  • Research Outputs
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Computing
  4. Computing
  5. Relational algebra by way of adjunctions
 
  • Details
Relational algebra by way of adjunctions
File(s)
3236781.pdf (811.6 KB)
Published version
OA Location
https://dl.acm.org/doi/10.1145/3236781
Author(s)
Gibbons, Jeremy
Henglein, Fritz
Hinze, Ralf
Wu, Nicolas
Type
Conference Paper
Abstract
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.
Date Issued
2018-09-01
Date Acceptance
2018-05-01
Citation
Proceedings of the ACM on Programming Languages, 2018, pp.86.1-86.28
URI
http://hdl.handle.net/10044/1/85696
URL
https://dl.acm.org/doi/10.1145/3236781
DOI
https://www.dx.doi.org/10.1145/3236781
ISSN
2475-1421
Publisher
Association for Computing Machinery (ACM)
Start Page
86.1
End Page
86.28
Journal / Book Title
Proceedings of the ACM on Programming Languages
Copyright Statement
© 2018 Copyright held by the owner/author(s). This work is under a Creative Commons Attribution 4.0 License (https://creativecommons.org/licenses/by/4.0/)
License URL
https://creativecommons.org/licenses/by/4.0/
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000461309200020&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Source
23rd ACM SIGPLAN International Conference on Functional Programming (ICFP)
Subjects
Science & Technology
Technology
Computer Science, Software Engineering
Computer Science
SQL
comprehension
adjunction
monad
graded monad
Publication Status
Published
Start Date
2018-09-23
Finish Date
2018-09-29
Coverage Spatial
St Louis, MO, USA
Date Publish Online
2018-07-30
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback