Next: Information Retrieval Up: Lent Term 2004: Part Previous: Computer Vision   Contents

## Database Theory

Lecturers: Dr G.M. Bierman and Dr A. Dawar

No. of lectures: 8

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

(This may well change for the academic year 2003/4.)

• 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. Datalog and recursive queries. Evaluation of queries. The role of 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.

• Types for database languages. Row types, collection types, SQL:1999 types, type inference.

• Semi-structured data. A model for web databases. Tree and graph-structured data. Query languages.

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.

Next: Information Retrieval Up: Lent Term 2004: Part Previous: Computer Vision   Contents
Christine Northeast
Thu Sep 4 15:29:01 BST 2003