Advanced Topics in Foundations of Databases

Course descriptor
Professor: Leonid Libkin
Office hours: by appointment

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


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 not be covered in lectures: they are part of the background knowledge. Standard notions related to computability such as finite automata, grammars, and Turing machines are supposed to be part of the background knowledge as well (in Informatics, this is generally taught in the first year of the undergraduate program). In addition, it is assumed that students have a good level of familiarity with one of the following: either theoretical underpinnings of databases (especially logic and complexity), or systems aspects of databases (such as details of RDBMS implementation), to be able to do projects in either theoretical, or systems aspects of data management.

Essay guidelines   The course is split into 10 topics (see below), each with a set of associated papers. Each essay should pick a paper from one of those topics (you cannot use the same one for different essays) and present: Suggested length: 5-7 pages.

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

Reading list, 2016.

Background reading

Lecture materials