Advanced Topics in Foundations of Databases (ATFD), 2017/18

DRPS Course Descriptor

Lecturer: Andreas Pieris
Office hours: by appointment

Lectures: Wednesday, 9:00-10:50, Room G.16, 7 Bristo Square



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 Database Systems in Edinburgh. Moreover, basic knowledge of complexity theory (e.g., Turing machines, complexity classes, reductions), and automata theory (e.g., finite state automata) is essential. In addition, it is assumed that students have a good level of familiarity with one of the following: 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.


Main topics

  1. Foundations of relational query languages (lecture, papers)
  2. Approximation of conjunctive queries (lecture, papers)
  3. Semantic optimization of conjunctive queries (lecture, papers)
  4. Foundations of XML (lecture, papers)
  5. Graph databases: Data model + query languages (lecture, papers)
  6. Ontology-based data access (OBDA) (lecture, papers)
  7. Query rewriting in OBDA (lecture, papers)
  8. Consistent query answering in OBDA (lecture, papers)

Background reading


Essay guidelines. The course is split into eight topics (see above), each with a set of associated papers. Each essay should pick a paper from one of those topics (in particular, Essay 1 from topics 1-3, Essay 2 from topics 4-5, and Essay 3 from topics 6-8), and present: Crucially, the 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.

Project guidelines. Projects should follow the same path (by taking another paper on a topic not previously covered) but add a new contribution done by you. This could be:

Think of it as a mini MSc project (or something that perhaps could lead to one).