Database Theory

Lecturers: Dr G.M. Bierman and Dr A. Dawar
(gmb@cl.cam.ac.uk, ad260@cl.cam.ac.uk)

No. of lectures: 12

Aims

The aims of the course are to introduce the study of foundational issues in databases. A number of theoretical issues that arise from consideration of databases at the ``logical level'' will be examined, including relational algebra and calculus, deductive databases and the complexity of query languages. These ideas will further be extended beyond the flat relational model to consider object-oriented databases and semi-structured data, among others.

Lectures

• Relational algebra. A review of the relational model of data. Normal forms. The relational algebra as query language. Evaluation.

• Relational calculus. Using the relational calculus to express queries. Equivalence with relational algebra and the first-order predicate calculus. Safety and domain independence.

• Deductive databases.

• Recursion and negation.

• Complexity of query languages. Measuring the complexity of queries. Relational calculus, fixed-points and while loops. The role of numerical relations.

• Complex values. Nested relations. Algebra and calculus. Extended query languages.

• Object-oriented databases. A model for object-oriented databases. Languages for queries and methods.

• Semi-structured data and XML. Tree and graph-structured data. XML. Query languages including XQuery.

Objectives

At the end of the course students should:

• Be familiar with a variety of logical models of databases and the role they play in modelling different forms of structured data.

• Understand the relationship between a variety of languages for expressing database queries and their respective complexity.

• Understand how the structure of large databases interacts with the structure of languages that deal with them.

• Understand some of the various proposals for extending the classical relational model of data.

Recommended books

Abiteboul, S., Hull, R. & Vianu, V. (1995). Foundations of Databases. Addison-Wesley.
Abiteboul, S., Buneman, P. & Suciu, D. (2000). Data on the Web. Morgan Kaufmann.