Advanced Topics in Foundations of Databases (ATFD), 2019/20

ANNOUNCEMENTS

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

PREREQUISITES

1. 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.
2. Have some basic familiarity with comlexity theory: standard complexity classes such as PTIME and NP, and the notion of completeness.

MAIN THEMES AND TOPICS

Theme 1: Relational Model and Foundations of Relational Query Languages

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

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

1. Graph-structured Data: data model, basic query languages (regular path queries and extensions thereof), query evaluation

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

ASSESSMENT

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