How to Comprehend Queries Functionally

Compilers and optimizers for declarative query languagesuse some form of intermediate language to represent user-levelqueries. The advent of compositional query languages for orthogonaltype systems (e.g., OQL) calls for internal query representationsbeyond extensions of relational algebra. This work adopts a view ofquery processing which is greatly influenced by ideas from thefunctional programming domain. A uniform formal framework ispresented which covers all query translation phases, includinguser-level query language compilation, query optimization, andexecution plan generation. We pursue the type-based design—basedon initial algebras—of a core functional language which isthen developed into an intermediate representation that fits theneeds of advanced query processing. Based on the principle ofstructural recursion we extend the language by monad comprehensions(which provide us with a calculus-style sublanguage that proves to beuseful during the optimization of nested queries) and combinators(abstractions of the query operators implemented by the underlyingtarget query engine). Due to its functional nature, the language issusceptible to program transformation techniques that were developedby the functional programming as well as the functional data modelcommunities. We show how database query processing can substantiallybenefit from these techniques.