Next: Distributed Systems
Up: Easter Term 2003: Part
Previous: Business Studies
  Contents
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.
Next: Distributed Systems
Up: Easter Term 2003: Part
Previous: Business Studies
  Contents
Christine Northeast
Wed Sep 4 14:43:05 BST 2002