Database Theory

Module overview

This module will cover foundational concepts in data management. It will study classic database theory, as well as new areas of research. The first part of the class will focus on query languages and their complexity, while the second part will focus more on advanced topics in data management, such as incomplete information, provenance, privacy, data dependencies, and others. Topics we will include query languages, query containment, query complexity, worst-case optimal algorithms, datalog semantics, evaluation, and optimisation techniques. Bag Semantics and its relation to Diophantine inequalities. Database dependencies and reasoning with data.

Aims and Objectives

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

Advanced concepts in data management, including incomplete data, provenance, privacy-preserving computation, dependencies and bag semantics.
The formal foundations of query languages, including conjunctive queries, datalog, and their associated complexity classes.
The structure and conventions of research writing and presenting in database theory, including how technical arguments and results are presented in the literature.

Subject Specific Intellectual and Research Skills

Having successfully completed this module you will be able to:

Evaluate the computational behaviour of queries and algorithms, including identifying tractable and intractable cases in data complexity.
Analyse query language expressiveness and complexity using formal logical and algebraic tools.
Apply formal reasoning and abstraction to analyse complex technical problems.

Transferable and Generic Skills

Having successfully completed this module you will be able to:

Communicate rigorous theoretical arguments clearly and effectively in written form

Learning and Teaching

Teaching and learning methods

- Reading and preparation, including lecture notes and selected research papers. - Lectures: Three hours per week during the teaching weeks.

Study time
Type	Hours
Wider reading or practice	70
Revision	14
Lecture	36
Completion of assessment task	30
Total study time	150

Assessment

Summative

This is how we’ll formally assess what you have learned in this module.

Breakdown
Method	Percentage contribution
Coursework assignment(s)	20%
Final Assessment	80%

Referral

This is how we’ll assess you if you don’t meet the criteria to pass this module.

Breakdown
Method	Percentage contribution
Examination	100%

Repeat

An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.

Breakdown
Method	Percentage contribution
Examination	100%