Tech Report CS-89-39

Elements of Relational Database Theory

Paris C. Kanellakis

November 1989


The goal of this paper is to provide a systematic and unifying introduction to relational database theory, including some of the recent developments in database logic programming. The first part of the presentation covers the two basic components of the relational data model: its specification component, that is the database scheme with dependencies, and its operational component, that is the relational algebra query language. The choice of basic constructs for specifying the semantically meaningful databases and for querying them is justified through an in-depth investigation of their properties. Some important research themes are reviewed in this context: the analysis of the hypergraph syntax of a database scheme and the extensions of the query language using deduction or universal relation assumptions. The subsequent parts of the presentation are structured around the two fundamental concepts illustrated in the first part, dependencies and queries. The main themes of dependency theory are implication problems and applications to database scheme design. Queries are classified in a variety of ways, with emphasis on the connections between the expressibility of query languages, finite model theory and logic programming. The theory of queries is very much related to research on database logic programs, which are an elegant formalism for the study of the principles of knowledge base systems. The optimization of such programs involves both techniques developed for the relational data model and new methods for analyzing recursive definitions. The exposition closes with a discussion of how relational database theory deals with the problems of complex objects, incomplete information and database updates.

(complete text in pdf)