Advanced Topics in Foundations of Databases (ATFD), 2019/20
DRPS Course Descriptor
Lecturer: Andreas Pieris
Office hours: by appointment
Lectures: Friday, 16:10-18:00, 50 George Square, Room G02
ANNOUNCEMENTS
PREREQUISITES
While there are no formal prerequisites, it is recommended that students taking this course:
- 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.
In any case, this course is self-contained, and all the necessary tools will be properly introduced and explained during the lectures.
MAIN THEMES AND TOPICS
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
Theme 2: Uncertaintly - Reasoning over Possible Worlds
- 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
Theme 3: Semi-structured Data
- 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
The essays and the final project should be handed to the ITO before 4pm.
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.
Essay 1 should be for a paper from Theme 1 (papers), Essay 2 for a paper from Theme 2 (papers), and Essay 3 for a paper from Theme 3 (papers). Each essay will be marked on its clarity and technical accuracy. Crucially, an essay must be understood by someone who has not read the paper under review.
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)
Think of it as a mini MSc project (or something that perhaps could lead to one). The project should be for paper from Theme 1 or 2 or 3. Each project will be marked on its clarity and technical accuracy, as well as the relevance and accuracy of the new contribution. Crucially, a project must be understood by someone who has not read the paper under review.
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.