Skip to main content

Theory of Data and Knowledge Bases:  2011-2012



Schedule C1Computer Science

Schedule C1Mathematics and Computer Science

Schedule CMSc in Advanced Computer Science

MSc in Mathematics and Foundations of Computer Science



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 trade-off between complexity and expressive power of query languages, and understand some basic formalisms of non-monotonic reasoning. You should be in the position of analyzing a query language and expressing knowledge in suitable logical formalisms.


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., NP-completeness) 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.


We will try to cover the following topics:

  1. A brief introduction to databases, finite model theory, and descriptive complexity.
  2. Conjunctive queries: complexity and optimization.
  3. SQL and first-order queries: complexity, limits of expressive power.
  4. Reasoning with propositional Horn theories.
  5. Datalog and fixpoint queries: complexity and expressive power.
  6. Querying semi-structured data.
  7. Elements of non-monotonic reasoning and closed-world reasoning.
  8. Problems of data integration and data exchange.
  9. Advanced material (time permitting).

It is roughly planned to spend two hours for each of the topics 1-8, and to insert additional material (9) dynamically where appropriate.

Reading list


  • S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 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.


Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.