Lecturer: Andreas Pieris

Office hours: by appointment

Lectures: Friday, 16:10-18:00, 50 George Square, Room G02

- First class on January 17
- General information about the course
- New deadlines for Essay 3 and Final Project - see below. The submission can be done via email.

- Have passed an introductory course in Databases such as the undergraduate course Introduction to Databases; in particular, some familiarity with the relational model, the main query languages (algebra and calculus), and integrity constraints is welcome.
- Have some basic familiarity with comlexity theory: standard complexity classes such as PTIME and NP, and the notion of completeness.

**Theme 1: Relational Model and Foundations of Relational Query Languages **

- Relational Model: data model, relational algebra, relational calculus, query evaluation, static analysis
- Conjunctive Queries (CQs): syntax and semantics (via homomorphisms), CQ evaluation, static analysis of CQs, minimization of CQs
- Fast CQ Evaluation: acyclic CQs, evaluation of acyclic CQs (Yannakaki's algorithm), semantic acyclicity, evaluation of semantically acyclic CQs

- Inconsistent Databases: integrity constraints, database repairs, consistent query answering
- Incomplete Databases: the model, querying incomplete databases
- Probabilistic Databases: the model, querying probabilistic databases
- Knowledge-enriched Databases: ontologies, querying knowledge bases

**Background reading**

- Notes on complexity theory
- Abiteboul, Hull, Vianu, Foundations of Databases, 1995
- Bertossi, Database Repairing and Consistent Query Answering, 2011
- Suciu, Olteanu, Re, Koch, Probabilistic Databases, 2011

- Essay 1 (15%): due 7 February
- Essay 2 (15%): due 3 March
- Essay 3 (15%): due 13 April (extended deadline)
- Final project (40%): due 27 April (extended deadline)
- Project presentation (15%): in class, to be scheduled

**Essay Guidelines.** Choose a paper (from the list of papers given below for each theme) and present:

- A summary of the paper.
- Analysis and critical thoughts; in particular, criticism of the paper, and discussion on follow-up papers that show how the ideas of the paper under review have influenced the field.

**Project Guidelines.** Choose a paper (from the list of papers given above for each theme) and present:

- A summary of the paper.
- Analysis and critical thoughts; in particular, criticism of the paper, and discussion on follow-up papers that show how the ideas of the paper under review have influenced the field.
- 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)

**Preparation of Essays and Final Project.** Here are the general guidelines that *must* be followed during the preparation of the essays and the final project:

- The submission must be word-processed in font size 12 with 1.5 line spacing and margins 2.5 cm; pages should be consecutively numbered.
- The length of each essay must be 5 to 7 pages (including references).
- The length of the final project must be 7 to 9 pages (including references).
- Each submission should be clearly written in sentences with appropriate punctuation, display of formulae, appropriate use of "Definition", "Lemma", "Theorem", "Proof", etc.
- The work should be properly and adequately referenced in the text, with the full list of references at the end of the essay/project, following any of the standard labelling conventions as technical papers (e.g., numerical, or by abbreviated name).
- The title of each essay/final project should be the title of the chosen paper.
- Your details (name, student number) should be clearly stated.