The Programming of Algebra
Research output: Contribution to journal › Conference article › Research › peer-review
Standard
The Programming of Algebra. / Henglein, Fritz; Kaarsgaard, Robin; Mathiesen, Mikkel Kragh.
In: Electronic Proceedings in Theoretical Computer Science, EPTCS, Vol. 360, 06.2022, p. 71-92.Research output: Contribution to journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - The Programming of Algebra
AU - Henglein, Fritz
AU - Kaarsgaard, Robin
AU - Mathiesen, Mikkel Kragh
N1 - Publisher Copyright: © 2022 Henglein, Kaarsgaard, & Mathiesen.
PY - 2022/6
Y1 - 2022/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85134205943&partnerID=8YFLogxK
U2 - 10.4204/EPTCS.360.4
DO - 10.4204/EPTCS.360.4
M3 - Conference article
AN - SCOPUS:85134205943
VL - 360
SP - 71
EP - 92
JO - Electronic Proceedings in Theoretical Computer Science
JF - Electronic Proceedings in Theoretical Computer Science
SN - 2075-2180
T2 - 9th Workshop on Mathematically Structured Functional Programming, MSFP 2022
Y2 - 2 April 2022
ER -
ID: 318869458