Theory of Data and Knowledge Bases: 20102011
Lecturer 

Degrees 
Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science 
Term 
Hilary Term 2011 (16 lectures) 
Overview
The lecture series provides an understanding of the logical foundations of database query languages and knowledge representation formalisms, the expressive power of such languages/formalisms, and the complexity of query answering and reasoning with such languages/formalisms.Learning outcomes
By the end of this lecture series, you should have a good understanding of the fundamentals of query languages, understand the tradeoff between complexity and expressive power of query languages, and understand some basic formalisms of nonmonotonic reasoning. You should be in the position of analyzing a query language and expressing knowledge in suitable logical formalisms.Prerequisites
Basic knowledge of automata theory (e.g., finite state automata), databases (e.g., the relational data model, relational algebra, SQL), and complexity theory (e.g., NPcompleteness) will be assumed. This can be gained from the undergraduate courses Models of Computation, Databases and Computational Complexity, or the MSc courses Introduction to Foundations of Computer Science and Databases. Students who have not studied these courses should talk to the lecturer.
Synopsis
We will try to cover the following topics:
 A brief introduction to databases, finite model theory, and descriptive complexity.
 Conjunctive queries: complexity and optimization.
 SQL and firstorder queries: complexity, limits of expressive power.
 Reasoning with propositional Horn theories.
 Datalog and fixpoint queries: complexity and expressive power.
 Querying semistructured data.
 Elements of nonmonotonic reasoning and closedworld reasoning.
 Problems of data integration and data exchange.
 Advanced material (time permitting).
It is roughly planned to spend two hours for each of the topics 18, and to insert additional material (9) dynamically where appropriate.
Reading list
Books:
 S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. AddisonWesley, 1995.
 L. Libkin. Elements of Finite Model Theory. Springer, 2004. (selected chapters)
A list of papers covering various relevant topics will be supplied in due course.