** 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
*