PhD defence by Mikkel Kragh Mathiesen

Portrait of Mikkel

Title

The Programming of Algebra 

Abstract

We study how abstract algebra can be used as a foundation for programming,in particular for the purpose of query processing. The basic algebraic structuresof rings, modules and algebras provide an expressive language for workingwith generalised multisets. Queries are expressed as linear maps between modules.The theory is presented categorically by means of universal properties andconstitutes a promising replacement for classical relational algebra.Many algebraic hallmarks turn out to be vital. Negative elements providea uniform method for deleting data and multiplication expresses join of tables.

Tensor products provide an efficient non-canonical representation of Cartesianproducts. Natural isomorphisms inexorably lead to efficient generalised trierepresentations of finite maps. Ultimately this begets highly efficient techniquesfor evaluation and in particular demonstrates worst-case output optimality for conjunctive queries.Going further, we posit that linear algebra can be viewed as an excellentfunctional logic programming language. From this perspective a potential avenue of improvement becomes visible: finite-dimensional spaces are convenientto work with and—crucially—allow representing linear maps as elements of thetensor product, whereas infinite-dimensional spaces are less convenient in thisregard 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 Algeoand comes with a syntax, type system and axiomatic as well as denotational semantics.

Assessment Committee

Professor Robert Glück, DIKU 
Professor Ralf Hinze, University of Kaiserslautern 
Senior Lecturer Nicolas Wu, Imperial College, London 

Moderator: Ken Friis Larsen 

Supervisors

Principal Supervisor Friedrich Henglein
Co-Supervisor Robin Kaarsgaard 

For an electronic copy of the thesis, please visit the PhD Programme page.