Relational algebra by way of adjunctions

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.

References

1. Alexander Alexandrov, Andreas Kunft, Asterios Katsifodimos, Felix Schüler, Lauritz Thamsen, Odej Kao, Tobias Herb, and Volker Markl. 2015. Implicit Parallelism through Deep Language Embedding. In SIGMOD record. ACM, 47–61.
2. Steve Awodey. 2006. Category Theory. Oxford University Press.
3. Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, and Limsoon Wong. 1994. Comprehension Syntax. SIGMOD Record 23, 1 (1994), 87–96.
4. Stanley Burris and Simon Lee. 1993. Tarski’s High School Identities. Amer. Math. Monthly 100, 3 (March 1993), 231–236.
5. Jacques Carette. 2018. Email correspondence. (May 2018). Personal communication.
6. James Cheney, Sam Lindley, and Philip Wadler. 2013. A Practical Theory of Language-Integrated Query. In International Conference on Functional Programming , Greg Morrisett and Tarmo Uustalu (Eds.). ACM, 403–416.
7. Eugenia Cheng. 2015. Cakes, Custard, and Category Theory. Profile Books.
8. Richard H. Connelly and F. Lockwood Morris. 1995. A Generalization of the Trie Data Structure. Mathematical Structures in Computer Science 5, 3 (September 1995), 381–418.
9. 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–296.
10. John Darlington. 1975. Application of Program Transformation to Program Synthesis. In IRIA Symposium on Proving and Improving Programs . Arc-et-Senans, France, 133–144.
11. Christopher J. Date. 2004. An Introduction to Database Systems (8th ed.). Pearson.
12. 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–300.
13. Marcelo Fiore, Roberto Di Cosmo, and Vincent Balat. 2006. Remarks on Isomorphisms in Typed Lambda Calculi with Empty and Sum Types. Annals of Pure and Applied Logic 141, 1-2 (2006), 35–50.
14. Soichiro Fujii, Shin-ya Katsumata, and Paul-André Melliès. 2016. Towards a Formal Theory of Graded Monads. In Foundations of Software Science and Computation Structures (Lecture Notes in Computer Science) . Springer-Verlag, 513–530.
15. 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–151.
16. 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án (Eds.), Vol. 6647. Springer, 1–18.
17. George Giorgidze, Torsten Grust, Nils Schweinsberg, and Jeroen Weijers. 2011b. Bringing Back Monad Comprehensions. In Haskell Symposium . ACM, 13–22.
18. Glasgow 2015. Glasgow Haskell Compiler Users’ Guide, Version 7.10.1. https://downloads.haskell.org/~ghc/7.10.1/docs/html/ users_guide/index.html .
19. Torsten Grust and Marc H. Scholl. 1999. How to Comprehend Queries Functionally. Journal of Intelligent Information Systems 12, 2-3 (1999), 191–218.
20. Fritz Henglein and Ralf Hinze. 2013. Distributive Sorting and Searching: From Generic Discrimination to Generic Tries. In Asian Symposium on Programming Languages and Systems (Lecture Notes in Computer Science) , Chung-chieh Shan (Ed.), Vol. 8301. Springer, 315–332.
21. Fritz Henglein and Ken Friis Larsen. 2010. Generic Multiset Programming with Discrimination-Based Joins and Symbolic Cartesian Products. Higher-Order and Symbolic Computation 23, 3 (2010), 337–370.
22. Ralf Hinze. 2000. Generalizing Generalized Tries. Journal of Functional Programming 10, 4 (2000), 327–351.
23. Ralf Hinze. 2003. Fun with Phantom Types. In The Fun of Programming, Jeremy Gibbons and Oege de Moor (Eds.). Palgrave Macmillan, 245–262.
24. Shin-ya Katsumata. 2014. Parametric Effect Monads and Semantics of Effect Systems. In Principles of Programming Languages. ACM, 633–645.
25. Leonid Libkin and Limsoon Wong. 1997. Query Languages for Bags and Aggregate Functions. J. Comput. System Sci. 55, 2 (1997), 241–272.
26. Conor McBride and Ross Paterson. 2008. Functional Pearl: Applicative Programming with Effects. Journal of Functional Programming 18, 1 (2008), 1–13.
27. Erik Meijer. 2007. Confessions of a Used Programming Language Salesman. In Object-Oriented Programming: Systems, Languages and Applications . ACM, 677–694.
28. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2012. Worst-Case Optimal Join Algorithms. In Principles of Database Systems . ACM, 37–48.
29. Dominic A. Orchard, Tomas Petricek, and Alan Mycroft. 2014. The Semantic Marriage of Monads and Effects. CoRR abs/1401.5391 (2014).
30. Simon Peyton Jones and Philip Wadler. 2007. Comprehensive Comprehensions. In Haskell Workshop. ACM, 61–72.
31. Benjamin C. Pierce. 1991. Basic Category Theory for Computer Scientists. MIT Press.
32. Rinus Plasmeijer and Marko van Eekelen. 1995. Concurrent Clean Language Report (Version 1.0). Technical Report. University of Nijmegen. ftp://ftp.science.ru.nl/pub/Clean/old/Clean10/doc/refman.ps.gz .
33. Jacob T. Schwartz, Robert B. K. Dewar, Ed Dubinsky, and Edmond Schonberg. 1986. Programming with Sets: An Introduction to SETL . Springer, New York.
34. Patricia Griffiths Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. 1979. Access Path Selection in a Relational Database Management System. In SIGMOD record. ACM, 23–34.
35. Ross Street. 1972. Two Constructions on Lax Functors. Cahiers de Topologie et Géométrie Différentielle Catégoriques 13, 3 (1972), 217–264. http://eudml.org/doc/91107
36. Kenichi Suzuki, Oleg Kiselyov, and Yukiyoshi Kameyama. 2016. Finally, Safely-Extensible and Efficient Language-Integrated Query. In Partial Evaluation and Program Manipulation, Martin Erwig and Tiark Rompf (Eds.). ACM, 37–48.
37. Don Syme. 2006. Leveraging .NET Meta-programming Components from F#: Integrated Queries and Interoperable Heterogeneous Execution. In ML Workshop. ACM, New York, NY, USA, 43–54.
38. Philip W. Trinder. 1991. Comprehensions, a Query Notation for DBPLs. In Database Programming Languages. 55–68.
39. Philip Wadler. 1992. Comprehending Monads. Mathematical Structures in Computer Science 2, 4 (1992), 461–493.
40. Limsoon Wong. 2000. Kleisli, a Functional Query System. Journal of Functional Programming 10, 1 (2000), 19–56.

Index Terms

• Information systems

  • Data management systems

    • Query languages

      • Relational database query languages

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

      • Semantics

• Theory of computation

  • Semantics and reasoning

    • Program semantics

      • Categorical semantics