The Programming of Algebra

Fritz Henglein, Robin Kaarsgaard, Mikkel Kragh Mathiesen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

15 Downloads (Pure)

Abstract

We present module theory and linear maps as a powerful generalised and computationally efficient framework for the relational data model, which underpins today’s relational database systems. Based on universal constructions of modules we obtain compact and computationally efficient data structures for data collections corresponding to union and deletion, repeated union, Cartesian product and key-indexed data. Free modules naturally give rise to polysets, which generalise multisets and facilitate expressing database queries as multilinear maps with asymptotically efficient evaluation on polyset constructors. We introduce compact maps as a way of representing infinite (poly)sets constructible from an infinite base set and its elements by addition and subtraction. We show how natural joins generalise to algebraic joins, while intersection is implemented by a novel algorithm on nested compact maps that carefully avoids visiting parts of the input that do not contribute to the eventual output. Our algebraic framework leads to a worst-case optimal evaluation of cyclic relational queries, which is known to be impossible using textbook query optimisers that operate on lists of records only.
Original languageEnglish
Title of host publicationProceedings of the Ninth Workshop on Mathematically Structured Functional Programming
Volume360
Publication date30. Jun 2022
Pages71-92
DOIs
Publication statusPublished - 30. Jun 2022
Externally publishedYes
EventNinth Workshop on Mathematically Structured Functional Programming -
Duration: 2. Apr 20222. Apr 2022

Workshop

WorkshopNinth Workshop on Mathematically Structured Functional Programming
Period02/04/202202/04/2022
SeriesElectronic Proceedings in Theoretical Computer Science
Volume360
ISSN2075-2180

Fingerprint

Dive into the research topics of 'The Programming of Algebra'. Together they form a unique fingerprint.

Cite this