# Advanced Topics in Foundations of Databases (ATFD), 2016/17

DRPS Course Descriptor

Lecturer: Andreas Pieris

Office hours: by appointment

Lectures: Wednesday, 9:00-10:50, Room 2.14, Appleton Tower

### ANNOUNCEMENTS

- First class on 18 January
- Click here for useful information about the course
- General guidelines for the preparation of the final project/essays can be found here
- The papers for Essay 1 (topics 1-4) have been posted (see below)
- The papers for Essay 2 (topics 5-7) have been posted (see below)
- You can collect the essays (topics 1-4) from the ITO
- The papers for Essay 3 (topics 8-10) have been posted (see below)
- You can collect the essays (topics 5-7) from the ITO
- The details for the final project presentations have been mailed to you
- You can collect the essays (topics 8-10) from the ITO

### 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 desirable. 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)
- Scale independence (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)
- Semantic Web Data: RDF + SPARQL (papers)
- Ontology-based data access/integration (OBDA) (lecture, papers)
- Query rewriting in OBDA (lecture, papers)
- Consistent query answering in OBDA (lecture, papers)

**Background reading**

- 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 3 February (ITO; before 4pm); 15%
- Essay 2: due 3 March (ITO; before 4pm); 15%
- Essay 3: due 24 March (ITO; before 4pm); 15%
- Final project: due 14 April (ITO; before 4pm); 40%
- Project presentation: in class, to be scheduled; 15%

**Essay guidelines.** The course is split into ten 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-4,
Essay 2 from topics 5-7, and Essay 3 from topics 8-10), 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).