Advanced Topics in Foundations of Databases (ATFD), 2018/19
DRPS Course Descriptor
Lecturer: Andreas Pieris
Office hours: by appointment
Lectures: Wednesday, 9:00-10:50, Lister Learning and Teaching Centre, Room 3.3
- First class on 16 January
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.
Click here for useful information about the course
- Foundations of relational query languages (lecture, papers)
- Approximation of conjunctive queries (lecture, papers)
- Semantic optimization of conjunctive queries (lecture, papers)
- Foundations of XML (lecture, papers)
- Graph databases: Data model + query languages (lecture, papers)
- Ontology-based data access (OBDA) (lecture, papers)
- Query rewriting in OBDA (lecture, (papers)
- Consistent query answering in OBDA (lecture, (papers)
- Notes on complexity theory
- Materials of the Database
Systems course (3rd year)
- Materials of
and Logic course (1st year)
- Abiteboul, Hull, Vianu, Foundations of Databases,
- Libkin, Elements of Finite Model Theory (Chapters 6-9), 2012
- Arenas, Barceló, Libkin, Murlak, Foundations of Data Exchange, 2014
- Essay 1: due 8 February (ITO; before 4pm); 15%
- Essay 2: due 8 March (ITO; before 4pm); 15%
- Essay 3: due 5 April (ITO; before 4pm); 15%
- Final project: due 26 April (ITO; before 4pm); 40%
- Project presentation: in class, to be scheduled; 15%
General guidelines for the preparation of the final project/essays can be found here
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.
- A summary of the paper.
- Analysis and critical thoughts; e.g., a
criticism of the paper, ideas for extending its results, or
analysis of followup papers that show how the ideas of the paper
under review have influenced the field.
Project guidelines. Projects should follow the same path (by taking another paper not previously studied) 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).
- An implementation of a theoretical algorithm with performance analysis.
- An extension of some of the results to cover new cases.
- An improvement for an existing solution, perhaps under some restrictions.
- Etc. (the list is not exhaustive)