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
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 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.
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%
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:
- 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.
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
- 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
Reading list, 2016.
Background reading
Lecture materials