# 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

### ANNOUNCEMENTS

- First class on 17 January
- Click here for useful information about the course
- General guidelines for the preparation of the final project/essays can be found here

### 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 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.

### COURSE INFORMATION

**Main topics**

- 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 (papers)
- Ontology-based data access (OBDA)
- Query rewriting in OBDA
- Consistent query answering in OBDA

**Background reading**

- Notes on complexity theory
- Materials of the Database
Systems course (3rd year)
- Materials of
the Computation
and Logic course (1st year)
- Abiteboul, Hull, Vianu, Foundations of Databases,
1995
- Libkin, Elements of Finite Model Theory (Chapters 6-9), 2012
- Arenas, Barceló, Libkin, Murlak, Foundations of Data Exchange, 2014

### ASSESSMENT

- Essay 1: due 9 February (ITO; before 4pm); 15%
- Essay 2: due 9 March (ITO; before 4pm); 15%
- Essay 3: due 6 April (ITO; before 4pm); 15%
- Final project: due 27 April (ITO; before 4pm); 40%
- Project presentation: in class, to be scheduled; 15%

**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:
- 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.

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:

- 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)

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