Module Theory and Query Processing(Extended Abstract)
Fritz Henglein

Mikkel Kragh Mathiesen

University of Copenhagen

University of Copenhagenfritz@henglein.com

mkm@di.ku.dk

Summary. We develop the basics of module theory with an emphasis on categorical constructions.
Elements of free modules have a natural interpretation as finite polysets, generalized multisets whereelements can also occur a negative or even fractional number of times. Many queries traditionally expressed in SQL correspond to multilinear maps on polysets. By employing symbolic constructors forscalar multiplication and tensor products we obtain more compact representations that facilitate run-time
optimizations using algebraic identities and yield asymptotic speed-ups compared to the conventional
stream-of-tuples representation in database systems. In particular we show that a straightforward functional join algorithm is efficient even for cyclic joins.
From sets and multisets to polysets. Traditional query processing is based on relational algebra andSQL. In relational algebra query inputs and results are sets (elements occur 0 or 1 times) whereas SQL
uses bag semantics (elements occur zero or more times). Extensions to this model have been proposed,such as probabilistic databases [2] (elements have real number multiplicities between 0 and 1) or provenance semirings [3] (elements have multiplicities from any semiring). In this manner databases are gradually progressing from set-like semantics to algebraic semantics. We propose to continue in this direction
and go to using modules over rings to harvest increased expressiveness (support for subtraction/deletion),compact data structures and computational efficiency simultaneously facilitated by (symbolic) linear algebra [5].1 The result is a theory of polysets: occurrences have multiplicities from any ring with linear
maps (homomorphisms), which turn out to be sufficient for expressing a wide variety of queries. If
and only if necessary, computationally expensive non-linear operations can be inserted in select places,
e.g. for mapping a polyset to a multiset by eliminating negative multiplicities.
Modules. The general structure is that of an 𝑅-module, a set 𝑀 equipped with operations+ : 𝑀→𝑀→𝑀· : 𝑅→𝑀→𝑀
satisfying the usual axioms of identity, commutativity, associativity and distributivity where 𝑅 is a ringwith unity.
Compared to the usual set and multiset semantics this already gives us two new tools. Firstly, forany element 𝑥 we have its negation −𝑥 = (−1) · 𝑥. This operation takes the place of set difference inrelational algebra but has the additional advantage that updates are commutative, e.g. 𝑥 + (−𝑦) is thesame as (−𝑦) + 𝑥.
1 Most of this development is described in the second author’s thesis.

Submitted to:
MSFP 2020c F. Henglein & M.K. Mathiesen
This work is licensed under theCreative Commons Attribution License.

2

Module Theory and Query Processing

Negative multiplicities of elements is not always desirable so we may wish to normalize the dataat specific points. If data is normalized after every update we recover the usual set- or multiset-based
semantics, whichever is desired. In this fashion query processing is not intrinsically about finite sets
(relational algebra) or multisets (SQL).
The other tool is a notation for repeated elements, so we can write e.g. 4 · 𝑥 instead of 𝑥 + 𝑥 + 𝑥 + 𝑥.
Directly using this notation as a representation we can obtain asymptotic improvements in some cases,
especially in combination with tensor products as explained later.
Universal properties. To further explore the possibilities of exploiting algebraic properties we look at
module theory through the lens of category theory using universal properties. Consider the homogeneousÝ
coproduct 𝑋 𝑀, i.e. 𝑋 copies of 𝑀. This can be seen as a mapping with finite support from the setÝ
𝑋 into the elements of 𝑀. In particular, 𝑋 𝑅 which is the free 𝑅-module generated by 𝑋. If we haveattributes 𝐴1 , . . . , 𝐴𝑛 then the free Z-module over 𝐴1 × · · · × 𝐴𝑛 serves as the domain for tables containing
these attributes. By the universal property of coproducts we get natural isomorphisms such asÞÞÞ𝑀 𝑀⊕
𝑀𝑋 +𝑌Þ
𝑋 ×𝑌𝑀

𝑋ÞÞ
𝑋𝑌𝑀

𝑌In this way we precisely recover the structure of generic tries [4].
Next, we turn to tensor products which are described by their universal property relative to bilinear
maps. Specifically, bilinear maps (𝑀1 , 𝑀2 ) → 𝑀3 are equivalent to linear maps 𝑀1 ⊗ 𝑀2 → 𝑀3 . A
symbolic tensor product constructor gives rise to a compact representation of join results since we canrepresent elements of the tensor space as 𝑥 ⊗ 𝑦 for arbitrary tables 𝑥 and 𝑦. This avoids unnecessarily
multiplying it out to the standard stream-of-tuples form used in database systems, which has a worstcase quadratic blowup. Hence, we recover the advantages of factorized databases [1]. Additionally, asymbolic scalar multiplication constructor provides a potentially exponentially more compact representation of tables, storing 𝑘 · 𝑥 instead of 𝑥 + . . . + 𝑥. This is for example useful in representing the output ofprojections or SQL semi-joins.
In general, by taking an algebraic perspective we can draw on a vast repository of knowledge, exposing optimizations that are otherwise nonobvious, impractical or difficult to get right.
Joins. A major challenge of evaluating database queries is handling joins. Using the trie structuresderived from coproducts and symbolic tensor products we can compute simple joins in worst-case linear
time. Applying this technique to more complicated situations we get efficient joins even in more complicated situations. In particular, triangle joins, which belong to the notoriously hard class of cyclic joins,3
are computed in 𝑂 (𝑛 2 ). This is worst-case time optimal [6] and known not to be achievable by classicalrelational database systems [7].

F. Henglein & M.K. Mathiesen

3References[1] Nurzhan Bakibayev, Dan Olteanu & Jakub Závodný (2012): FDB: A Query Engine for Factorised Relational
Databases. Proc. VLDB Endow. 5(11), pp. 1232–1243, doi:10.14778/2350229.2350242. Available at https://doi.org/10.14778/2350229.2350242.
[2] Nilesh Dalvi & Dan Suciu (2004): Efficient Query Evaluation on Probabilistic Databases. In: Proceedings ofthe Thirtieth International Conference on Very Large Data Bases - Volume 30, VLDB ’04, VLDB Endowment,
pp. 864–875.
[3] Todd J. Green, Grigoris Karvounarakis & Val Tannen (2007): Provenance Semirings. In: Proceedings of
the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’07, Association for Computing Machinery, New York, NY, USA, pp. 31–40, doi:10.1145/1265530.1265535.
Available at https://doi.org/10.1145/1265530.1265535.
[4] Ralf Hinze (2000): Generalizing generalized tries. Journal of Functional Programming 10(4), pp. 327–351,
doi:10.1017/S0956796800003713.
[5] Mikkel Kragh Mathiesen (2016): Infinite-Dimensional Linear Algebra for Query Processing. Master’s thesis,
University of Copenhagen.
[6] H.Q. Ngo, E. Porat, C. Ré & A. Rudra (2012): Worst-case optimal join algorithms. In: Proceedings of the31st symposium on Principles of Database Systems, ACM, pp. 37–48.
[7] Hung Q Ngo, Christopher Re & Atri Rudra (2013): Skew Strikes Back: New Developments in the Theory ofJoin Algorithms. arXiv preprint arXiv:1310.3314.