Professor: Leonid Libkin

Office hours: by appointment

Class meets Wednesdays 9:00-10:50 in AT LT 2

Announcements

- First class on Wednesday 20 January
- Information about project presentations has been mailed to you; please check your email and respond as/if required by 23:59 on Thursday 10 March.

Prerequisites

While there are no formal prerequisites, it is assumed that students taking this course are familiar with the topics taught in a standard database course such as DBS in Edinburgh. Concepts such as relational calculus (i.e., first-order logic), algebra, constraints (keys, foreign keys, functional dependencies), basics of SQL programming, basics of database design, and basics of relational query processing will

Assessment

- Essay 1, due 5 February (ITO; before 4pm); 15%
- Essay 2, due 26 February (ITO; before 4pm); 15%
- Essay 3, due 18 March (ITO; before 4pm); 15%
- Project, due 8 April (ITO; before 4pm); 40%
- Project presentation, in class, to be scheduled; 15%

- a summary of the paper, and
- your own analysis and critical thoughts. This may be a criticism of the paper, your ideas for extending its results, or analysis of followup papers that show how the ideas of the paper under review have influenced the field.
- Crucially, your essay must be understood by someone who
has
**not**read the paper. Of course in reality it will be marked by someone who has (although in some cases, a while ago), but still this is an important criterion that will be used in marking.

**Projects** should follow the same path (by taking another paper
from a category not previously covered) but add a *new
contribution* done by you. This could be: an implementation of a
theoretical algorithm with performance analysis, or an extension of
some of the results to cover new cases, or an improvement for an
existing solution, perhaps under some restrictions. Think of it as a mini MSc
project (or something that perhaps could lead to one).

Course materials

**Main topics**

- Foundations: conjunctive queries, constraints, datalog, automata
- Scalable query answering
- Approximation of queries
- XML databases
- Graph databases and RDF
- Incomplete information
- Inconsistent data and consistent query answering
- Data integration
- Data exchange

**Background reading**

- Materials of the Database Systems course (3rd year)
- Materials of the Computation and Logic course (1st year)
- Abiteboul, Hull, Vianu,
*Foundations of Databases*, 1995 - Books on data exchange and finite model theory (chapters 6-9)

**Lecture materials**