Topics in Foundations of Databases

Professor: Leonid Libkin

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 (for example, in Informatics at Edinburgh, this is generally taught in the first year of the undergraduate program).

Essay and presentation The coursework consists of an essay and in-class presentation on the last day of lectures (1 August). The mark is determined solely by the essay but the presentation is compulsory, that is, essays will only be marked if students did a presentation. The rationale for this is that the course is short and intense and students have little time for presentation, hence its role is downsized.

Presentation guidelines Each presentation should be around 7-8 minutes; students are expected to say which paper from the reading list they have chosen, why they find it interesting, and give a very brief (one or two slides at most) overview.
Please prepare you slides as a PDF file (better than powerpoint: with PDF viewers there are fewer surprises and it allows faster switches between presenters; of course you can always save powerpoint or keynote as pdf) and have it with you on a usb stick. We shall go in the alphabetical (by last name) order, so that the last two 50-minute sessions will be sufficient for all the students to go over their presentation.

Essay guidelines   The course is split into several topics (see below), each with a set of associated papers from the reading list (see the link below). Each essay should pick a paper from the list and present:

Suggested length: 5-7 pages. Please don't be too short but also don't go over too much (verbosity is rarely a good way to show your knowledge of the subject or introduce new ideas).
Deadline: 16 August 2017, 5pm Beijing time.
Please email a PDF file (no .doc, no .tex source etc, just pdf) to me, to two emails: and
Course materials

Main topics

Reading list.

Background reading

Lecture materials