TY - BOOK

T1 - The Programming of Algebra

AU - Mathiesen, Mikkel Kragh

PY - 2023

Y1 - 2023

N2 - We study how abstract algebra can be used as a foundation for programming, in particular for the purpose of query processing. The basic algebraic structures of rings, modules and algebras provide an expressive language for working with generalised multisets. Queries are expressed as linear maps between modules. The theory is presented categorically by means of universal properties and constitutes a promising replacement for classical relational algebra. Many algebraic hallmarks turn out to be vital. Negative elements provide a uniform method for deleting data and multiplication expresses join of tables. Tensor products provide an efficient non-canonical representation of Cartesian products. Natural isomorphisms inexorably lead to efficient generalised trie representations of finite maps. Ultimately this begets highly efficient techniques for evaluation and in particular demonstrates worst-case output optimality for conjunctive queries. Going further, we posit that linear algebra can be viewed as an excellent functional logic programming language. From this perspective a potential avenue of improvement becomes visible: finite-dimensional spaces are convenient to work with and—crucially—allow representing linear maps as elements of the tensor product, whereas infinite-dimensional spaces are less convenient in this regard but are necessary to model database schemata with infinite domains. We present a solution in the form of symbolic sums that provide a language of “compact-dimensional” linear algebra. The resulting language is called Algeo and comes with a syntax, type system and axiomatic as well as denotational semantics.

AB - We study how abstract algebra can be used as a foundation for programming, in particular for the purpose of query processing. The basic algebraic structures of rings, modules and algebras provide an expressive language for working with generalised multisets. Queries are expressed as linear maps between modules. The theory is presented categorically by means of universal properties and constitutes a promising replacement for classical relational algebra. Many algebraic hallmarks turn out to be vital. Negative elements provide a uniform method for deleting data and multiplication expresses join of tables. Tensor products provide an efficient non-canonical representation of Cartesian products. Natural isomorphisms inexorably lead to efficient generalised trie representations of finite maps. Ultimately this begets highly efficient techniques for evaluation and in particular demonstrates worst-case output optimality for conjunctive queries. Going further, we posit that linear algebra can be viewed as an excellent functional logic programming language. From this perspective a potential avenue of improvement becomes visible: finite-dimensional spaces are convenient to work with and—crucially—allow representing linear maps as elements of the tensor product, whereas infinite-dimensional spaces are less convenient in this regard but are necessary to model database schemata with infinite domains. We present a solution in the form of symbolic sums that provide a language of “compact-dimensional” linear algebra. The resulting language is called Algeo and comes with a syntax, type system and axiomatic as well as denotational semantics.

M3 - Ph.D. thesis

BT - The Programming of Algebra

PB - Department of Computer Science, Faculty of Science, University of Copenhagen

ER -