Introduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Module Theory and Query Processing
Fritz Henglein and Mikkel Kragh Mathiesen
DIKU, University of Copenhagen

8th Workshop on Mathematically Structured Functional
Programming (MSFP)
2020-09-01

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Triangle queries
How many reference triangles are there on Wikipedia?
A references B, which references C, which references A.

Experiment (Mathiesen, 2016):
Input: 335730 reference pairs between Wikipedia pages.
MySQL: SQL join query, in-memory database, query
optimization, indexing
Haskell: 3 pairwise join functions applied (A with B, B withC, C with A), no preprocessing
Implementation
MySQL
Haskell

Execution time (sec)6540

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Summary

Triangle queries

How many reference triangles are there on Wikipedia?
A references B, which references C, which references A.

Experiment (Mathiesen, 2016):
Input: 335730 reference pairs between Wikipedia pages.
MySQL: SQL join query, IMDB, query optimization, indexing
Haskell: 3 pairwise join functions applied (A with B, B withC, C with A), no preprocessing
Implementation
MySQL
Haskell

Execution time (sec)65404

Introduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

StrategyConsider a classic problem, say query processing
Forsake the old ways (relational algebra, SQL, etc.)
Take an algebraic approach (modules)
Sprinkle category theory on top···
Profit: generalise previous results, generate new results

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

ModulesA module V over commutative ring K consists ofA set |V|.
An element 0V : |V|
An operation + : |V| × |V| → |V|
An operation · : |K| × |V| → |V|such that
0V + x = x (zero identity)(x + y) + z = x + (y + z) (associativity)
x + y = y + x (commutativity)
1K · x = x (scalar identity)(αβ) · x = α · (β · x) (associativity)(α + β) · x = α · x + β · x (distributivity)
α · (x + y) = α · x + α · y (distributivity)

Joins

SummaryIntroduction

Modules

Coproducts

PolysetsTensor Products

Query Processing

Joins

Linear Maps
A linear map f : U → V respects the module structure:f (x + y) = f (x) + f (y)f (αx) = αf (x)A bilinear map f : U1 × U2 → V is linear in each argument:
f (x1 + x2 , y) = f (x1 , y) + f (x2 , y)f (x, y1 + y2 ) = f (x, y1 ) + f (x, y2 )f (αx, y) = αf (x, y)f (x, αy) = αf (x, y)
Modules over K with linear maps form a category.

SummaryIntroduction

ModulesCoproducts

Polysets

Tensor Products

Query Processing

Joins

Summary

Basic Modules

The trivial module {0} with only a zero element.
The ring K is a module.
Linear maps U → V form a module with pointwise operations.

Introduction

Modules

Coproducts

Polysets

Tensor Products

Coproducts: Universal property`

i:I Vicasehi.ci i

WWrite:
V1 ⊕ V2 =`i:{1,2} Vi ,x1 ⊕ x2 = inj1 (x1 ) + inj2 (x2 ).

injj

cj

Vj

Query Processing

Joins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Coproducts: Natural IsomorphismsaV ∼= {0}0aV ∼= K

1aV ∼=aV ∼=aa

I+Ja
I×JV⊕aIIVJVJThis is precisely the structure of generic tries.

Joins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Polysets: Universal property

Let K = Z.
|P[B]||exthb.f (b)i||W|`We have P[B] ∼= B Z.

[·]

fB

Joins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Polysets: Programming

Elements are polysets: finite sets(k )m){b1 1 , . . . , b(km } = k1 · [b1 ] + . . . + km · [bm ]where b1 , . . . , bm ∈ B and each element carries a multiplicity
0 6= ki ∈ Z.
All unlisted b ∈ B implicitly have multiplicity 0.

Application of f = exthb.vb i to polyset:
f (k1 · [b1 ] + . . . + km · [bm ]) = k1 · vb1 + . . . + km · vbm

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Tensor Products (Property)

U ⊗V⊗

uncurryhf ifW

U ×VJoins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor ProductsQuery Processing

Joins

SummaryTensor Products (Programming)

Any x : U ⊗ V can be thought of as y1 ⊗ z1 + . . . + yn ⊗ zn
where yi : U and zi : V.
Mapping out can be done by pattern matching:f (y ⊗ z) = E

f = uncurryhλy.λz.Ei

No non-zero natural map U ⊗ V → U, but U ⊗ P[B] → U ispossible.
Functorial action is (f ⊗ g)(y ⊗ z) = f (y) ⊗ g(z).

Introduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Query processing via multilinear functions

Union, difference, selection and projection are linear.
Cartesian product is bilinear.
Equi-joins are bilinear.
Aggregation is linear if the aggregation function is linear.
Idea:
Interpret query functions as (multi)linear maps over polysets(= fast).
Add nonlinear (= expensive) conversions to multisets (raisemultiplicity to ≥ 0) and sets (lower multiplicity to ≤ 1) only
where needed.

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Joins (Efficient Implementation)indexhf i : P[B] →`A P[B]indexhf i([b]) = injf (b) ([b])
flatten :`AV → V

flatten(inji (x)) = x```mergehIi : ( A U) ⊗ ( A V) → A (U ⊗ V)
(f ./ g) = flatten ◦ mergehIi ◦ (indexhf i ⊗ indexhgi)

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Summary

Joins (Merging)∼ ` V) ⊕ (` V)
AA2
`
` 1`
∼
β : A1 ×A2 V = ( A1 A2 V)
α:`

A1 +A2 V = (mergehZi = intmerge
mergehA1 + A2 i = α−1 ◦ (mergehA1 i ⊕ mergehA2 i) ◦ (α ⊗ α)`mergehA1 × A2 i = β −1 ◦ A1 (mergehA2 i) ◦ mergehA1 i ◦ (β ⊗ β)Introduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

JoinsJoins (Efficiency)

merge runs in linear time if intmerge does.
Size of output representation is linear due to symbolic tensor
products.

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Three Way Joins (Merging)For convenience define:``. : ( A U) ⊗ (U → V) → A V`
x . f = ( A f )(x)merge0 hA1 , A2 , A3 i(x ⊗ y ⊗ z)
= mergehA1 i(x ⊗ y)
. λ(x0 ⊗ y 0 ).mergehA2 i(x0 ⊗ z)
. λ(x00 ⊗ z 0 ).mergehA3 i(y 0 ⊗ z 0 ). λ(y 00 ⊗ z 00 ).x00 ⊗ y 00 ⊗ z 00

Joins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Joins

Three Way Joins (Efficiency)√For inputs all of size n, merge0 runs in time O(n n).
In general, it is worst-case optimal.
Practical advantage, especially for cyclic joins: 4 seconds
versus 1 hour 49 minutes for MySQL.

SummaryIntroductionModules

Coproducts

Polysets

Tensor Products

Query Processing

Summary

Categorical development of linear algebra.
Connection with databases and queries.
Efficient data representations.
An efficient join algorithm.

Joins

SummaryIntroduction

Modules

Coproducts

Polysets

Tensor Products

Query Processing

Linear algebra as a query processing language:
Quite expressive.
Functorial and natural constructions.
Symbolic representations, especially tensor products.
Efficient joins.

Joins

Summary