{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T19:38:22Z","timestamp":1773344302737,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/J010995\/1"],"award-info":[{"award-number":["EP\/J010995\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100012774","name":"Innovation Fund Denmark","doi-asserted-by":"crossref","award":["10-092299"],"award-info":[{"award-number":["10-092299"]}],"id":[{"id":"10.13039\/100012774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,7,30]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3236781","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Relational algebra by way of adjunctions"],"prefix":"10.1145","volume":"2","author":[{"given":"Jeremy","family":"Gibbons","sequence":"first","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fritz","family":"Henglein","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Hinze","sequence":"additional","affiliation":[{"name":"University of Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Bristol, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750543"},{"key":"e_1_2_2_2_1","volume-title":"Category Theory","author":"Awodey Steve","unstructured":"Steve Awodey . 2006. Category Theory . Oxford University Press . Steve Awodey. 2006. Category Theory. Oxford University Press."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/181550.181564"},{"key":"e_1_2_2_4_1","first-page":"3","article-title":"Tarski\u2019s High School","volume":"100","author":"Burris Stanley","year":"1993","unstructured":"Stanley Burris and Simon Lee . 1993 . Tarski\u2019s High School Identities. Amer. Math. Monthly 100 , 3 (March 1993), 231\u2013236. Stanley Burris and Simon Lee. 1993. Tarski\u2019s High School Identities. Amer. Math. Monthly 100, 3 (March 1993), 231\u2013236.","journal-title":"Identities. Amer. Math. Monthly"},{"key":"e_1_2_2_5_1","volume-title":"Email correspondence. (May","author":"Carette Jacques","year":"2018","unstructured":"Jacques Carette . 2018. Email correspondence. (May 2018 ). Personal communication. Jacques Carette. 2018. Email correspondence. (May 2018). Personal communication."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500586"},{"key":"e_1_2_2_7_1","unstructured":"Eugenia Cheng. 2015. Cakes Custard and Category Theory. Profile Books.  Eugenia Cheng. 2015. Cakes Custard and Category Theory. Profile Books."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500000803"},{"key":"e_1_2_2_9_1","volume-title":"Links: Web Programming without Tiers. In Formal Methods for Components and Objects (Lecture Notes in Computer Science)","author":"Cooper Ezra","year":"2006","unstructured":"Ezra Cooper , Sam Lindley , Philip Wadler , and Jeremy Yallop . 2006 . Links: Web Programming without Tiers. In Formal Methods for Components and Objects (Lecture Notes in Computer Science) , Vol. 4709 . Springer , 266\u2013296. Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop. 2006. Links: Web Programming without Tiers. In Formal Methods for Components and Objects (Lecture Notes in Computer Science) , Vol. 4709. Springer, 266\u2013296."},{"key":"e_1_2_2_10_1","volume-title":"IRIA Symposium on Proving and Improving Programs . Arc-et-Senans, France, 133\u2013144","author":"Darlington John","year":"1975","unstructured":"John Darlington . 1975 . Application of Program Transformation to Program Synthesis . In IRIA Symposium on Proving and Improving Programs . Arc-et-Senans, France, 133\u2013144 . John Darlington. 1975. Application of Program Transformation to Program Synthesis. In IRIA Symposium on Proving and Improving Programs . Arc-et-Senans, France, 133\u2013144."},{"key":"e_1_2_2_11_1","volume-title":"An Introduction to Database Systems","author":"Date Christopher J.","unstructured":"Christopher J. Date . 2004. An Introduction to Database Systems ( 8 th ed.). Pearson . Christopher J. Date. 2004. An Introduction to Database Systems (8th ed.). Pearson.","edition":"8"},{"key":"e_1_2_2_12_1","volume-title":"International Conference on Database Theory (Lecture Notes in Computer Science) , Jan Van den Bussche and Victor Vianu (Eds.)","volume":"1973","author":"Fernandez Mary","year":"2001","unstructured":"Mary Fernandez , Jerome Simeon , and Philip Wadler . 2001 . A Semi-Monad for Semi-Structured Data . In International Conference on Database Theory (Lecture Notes in Computer Science) , Jan Van den Bussche and Victor Vianu (Eds.) , Vol. 1973 . Springer, 263\u2013300. Mary Fernandez, Jerome Simeon, and Philip Wadler. 2001. A Semi-Monad for Semi-Structured Data. In International Conference on Database Theory (Lecture Notes in Computer Science) , Jan Van den Bussche and Victor Vianu (Eds.), Vol. 1973. Springer, 263\u2013300."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.09.001"},{"key":"e_1_2_2_14_1","volume-title":"Foundations of Software Science and Computation Structures (Lecture Notes in Computer Science)","author":"Fujii Soichiro","unstructured":"Soichiro Fujii , Shin-ya Katsumata, and Paul-Andr\u00e9 Melli\u00e8s . 2016. Towards a Formal Theory of Graded Monads . In Foundations of Software Science and Computation Structures (Lecture Notes in Computer Science) . Springer-Verlag , 513\u2013530. Soichiro Fujii, Shin-ya Katsumata, and Paul-Andr\u00e9 Melli\u00e8s. 2016. Towards a Formal Theory of Graded Monads. In Foundations of Software Science and Computation Structures (Lecture Notes in Computer Science) . Springer-Verlag, 513\u2013530."},{"key":"e_1_2_2_15_1","volume-title":"A List of Successes that can Change the World (Lecture Notes in Computer Science)","author":"Gibbons Jeremy","unstructured":"Jeremy Gibbons . 2016. Comprehending Ringads . In A List of Successes that can Change the World (Lecture Notes in Computer Science) , Sam Lindley, Conor McBride, Don Sannella, and Phil Trinder (Eds.), Vol. 9600 . Springer , 132\u2013151. Jeremy Gibbons. 2016. Comprehending Ringads. In A List of Successes that can Change the World (Lecture Notes in Computer Science) , Sam Lindley, Conor McBride, Don Sannella, and Phil Trinder (Eds.), Vol. 9600. Springer, 132\u2013151."},{"key":"e_1_2_2_16_1","volume-title":"Implementation and Application of Functional Languages (Lecture Notes in Computer Science) , Jurriaan Hage and Marco T","author":"Giorgidze George","unstructured":"George Giorgidze , Torsten Grust , Tom Schreiber , and Jeroen Weijers . 2011a. Haskell Boards the Ferry: Database-Supported Program Execution for Haskell . In Implementation and Application of Functional Languages (Lecture Notes in Computer Science) , Jurriaan Hage and Marco T . Moraz\u00e1n (Eds.), Vol. 6647 . Springer , 1\u201318. George Giorgidze, Torsten Grust, Tom Schreiber, and Jeroen Weijers. 2011a. Haskell Boards the Ferry: Database-Supported Program Execution for Haskell. In Implementation and Application of Functional Languages (Lecture Notes in Computer Science) , Jurriaan Hage and Marco T. Moraz\u00e1n (Eds.), Vol. 6647. Springer, 1\u201318."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034675.2034678"},{"key":"e_1_2_2_18_1","first-page":"10","article-title":"Glasgow Haskell Compiler Users\u2019 Guide","volume":"7","author":"Glasgow","year":"2015","unstructured":"Glasgow 2015 . Glasgow Haskell Compiler Users\u2019 Guide , Version 7 . 10 .1. https:\/\/downloads.haskell.org\/~ghc\/7.10.1\/docs\/html\/ users_guide\/index.html . Glasgow 2015. Glasgow Haskell Compiler Users\u2019 Guide, Version 7.10.1. https:\/\/downloads.haskell.org\/~ghc\/7.10.1\/docs\/html\/ users_guide\/index.html .","journal-title":"Version"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008705026446"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03542-0_23"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-011-9078-8"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003713"},{"key":"e_1_2_2_23_1","volume-title":"The Fun of Programming, Jeremy Gibbons and Oege de Moor (Eds.)","author":"Hinze Ralf","unstructured":"Ralf Hinze . 2003. Fun with Phantom Types . In The Fun of Programming, Jeremy Gibbons and Oege de Moor (Eds.) . Palgrave Macmillan , 245\u2013262. Ralf Hinze. 2003. Fun with Phantom Types. In The Fun of Programming, Jeremy Gibbons and Oege de Moor (Eds.). Palgrave Macmillan, 245\u2013262."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535846"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1523"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006326"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297078"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_2_29_1","volume-title":"The Semantic Marriage of Monads and Effects. CoRR abs\/1401.5391","author":"Orchard Dominic A.","year":"2014","unstructured":"Dominic A. Orchard , Tomas Petricek , and Alan Mycroft . 2014. The Semantic Marriage of Monads and Effects. CoRR abs\/1401.5391 ( 2014 ). Dominic A. Orchard, Tomas Petricek, and Alan Mycroft. 2014. The Semantic Marriage of Monads and Effects. CoRR abs\/1401.5391 (2014)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291201.1291209"},{"key":"e_1_2_2_31_1","volume-title":"Basic Category Theory for Computer Scientists","author":"Pierce Benjamin C.","unstructured":"Benjamin C. Pierce . 1991. Basic Category Theory for Computer Scientists . MIT Press . Benjamin C. Pierce. 1991. Basic Category Theory for Computer Scientists. MIT Press."},{"key":"e_1_2_2_33_1","volume-title":"Dubinsky, and Edmond Schonberg","author":"Schwartz Jacob T.","year":"1986","unstructured":"Jacob T. Schwartz , Robert B. K. Dewar , Ed Dubinsky, and Edmond Schonberg . 1986 . Programming with Sets : An Introduction to SETL . Springer , New York. Jacob T. Schwartz, Robert B. K. Dewar, Ed Dubinsky, and Edmond Schonberg. 1986. Programming with Sets: An Introduction to SETL . Springer, New York."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_35_1","first-page":"217","article-title":"Two Constructions on Lax Functors","volume":"13","author":"Street Ross","year":"1972","unstructured":"Ross Street . 1972 . Two Constructions on Lax Functors . Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle Cat\u00e9goriques 13 , 3 (1972), 217 \u2013 264 . http:\/\/eudml.org\/doc\/91107 Ross Street. 1972. Two Constructions on Lax Functors. Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle Cat\u00e9goriques 13, 3 (1972), 217\u2013264. http:\/\/eudml.org\/doc\/91107","journal-title":"Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle Cat\u00e9goriques"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847538.2847542"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159884"},{"key":"e_1_2_2_38_1","unstructured":"Philip W. Trinder. 1991. Comprehensions a Query Notation for DBPLs. In Database Programming Languages. 55\u201368.   Philip W. Trinder. 1991. Comprehensions a Query Notation for DBPLs. In Database Programming Languages. 55\u201368."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500001560"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003585"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236781","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":39,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236781"],"URL":"https:\/\/doi.org\/10.1145\/3236781","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}