Theory of Data and Knowledge Bases: 2008-2009
Information
|
Lecturer |
|
|
Degrees |
Schedule C1 — Honour School of Computer Science Part C — Honour School of Mathematics and Computer Science |
|
Term |
Hilary Term 2009 (16 lectures) |
Overview
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.Learning outcomes
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.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 First Order Queries: Complexity, limits of expressive power
- Reasoning with propositional Horn theories.
- Datalog and fixed-point queries: Complexity and expressive power.
- Querying semi-structured data.
- Elements of non-monotonic reasoning and closed-world reasoning.
- Problems of data integration and data exchange.
- Advanced material (time permitting)
Reading list
Books:
- Abiteboul, S., Hull, R. and Vianu, V. Foundations of Databases. Addison-Wesley, 1995.
- Leonid Libkin, Elements of Finite Model Theory, Springer, 2004 (selected chapters)