Programming Research Group Technical Monograph PRG-82

Phil Trinder December 1989, 198 pages, ISBN 0-902928-61-9

This thesis explores the use of functional languages to implement, manipulate and query databases.

Implementing databases.

A functional language is used to construct a database manager that allows efficient and concurrent access to shared data. In contrast to the locking mechanism found in conventional databases, the functional database uses data dependency to provide exclusion. Results obtained from a prototype database demonstrate that data dependency permits an unusual degree of concurrency between operations on the data. The prototype database is used to exhibit some problems using a new primitive. The design of a more realistic database is outlined. Some restrictions on the data structures that can be used in functional database are also uncovered.

Manipulating databases.

Functions over the database are shown to provide a powerful manipulation language. How to make such functions atomic is described. Such atomic transaction-functions permit consistent concurrent transformations of a database. Some issues in the transaction model are also addressed, including nested transactions.

Querying databases.

Others have recommended list comprehensions, a construct found in some functional languages, as query notation. Comprehensions are clear, concise, powerful, mathematically tractable and well integrated with a functional manipulation language. In this thesis comprehensions are proved to be adequately powerful, or relationally complete. Database and programming language theories are further integrated by describing the relational calculus in a programming language semantics. Finally, the tractability of the notation is used to improve the efficiency of list comprehension queries. For each major conventional improvement an analogous comprehension transformation is given.