Database Theory

From International Center for Computational Logic

Database Theory

Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2025

Databases are a key technology in computer science that brings together fascinating theoretical topics and highly relevant practical applications. The goal of this lecture is to give an extended introduction to this interesting field, with a special focus on database query languages, their expressive power, and computational complexity. The lecture will introduce the relational data model, and then discuss theoretical and practical aspects of a variety of query languages:

  • first-order logic as a query language and the relational algebra
  • conjunctive queries and their unions
  • navigational queries: path queries
  • Datalog and its relatives
  • query answering under database dependencies

The lecture focuses on core principles that apply to many types of databases alike (relational, graph-based, semantic web). Some important query answering algorithms are presented, too, but otherwise, the details of database implementation and administration are not covered.

Prerequisites

Undergraduate-level knowledge of predicate logic, regular languages, and algorithmic and computational complexity is required. The lecture will connect with other topics in the Computer Science and Computational Logic curriculum, such as relational databases, logic programming, and Semantic Web technologies – familiarity with these topics is not required to follow the lecture.

Schedule and Location

  • The weekly lecture sessions will take place on Mondays from 09:20 to 10:50 in room APB E007 and Tuesdays from 09:20 to 10:50 in room APB E005.
  • The weekly exercise session will take place on Tuesdays from 14:50 to 16:20 in room APB E005.
  • The first exercise session will be on Tuesday, 2025-04-15.

Examinations

Dates for oral exams will be announced in due time. As usual, you should book a date with our secretary after you have officially enrolled in your respective examination office/system.

Legacy

This course has first been taught at TU Dresden by Prof. Dr. Markus Krötzsch in the form of the 2015 lecture Foundations of Databases and Query Languages, and later in the Database Theory lecture series. The plan for this year's course will be somewhat similar.

The structure of some of the lectures of this course is inspired by the course Theory of Data and Knowledge Bases in the version given by Georg Gottlob and Thomas Lukasiewicz at the University of Oxford.

The main reference textbook for the lecture is:

  • Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley. 1994.
The book is available for free from its webpage, but there are also copies in the library.

Further texts might be consulted for background information and additional details:

  • Michael Sipser: Introduction to the Theory of Computation. 2005
Accessible introduction to complexity theory that covers all topics of computational complexity that the lecture touches upon.
  • Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and expressive power of logic programming. ACM Computing Surveys, 33:3, pp 374-425, 2001.
Covers all Datalog complexity results mentioned in the lecture. Available at http://dx.doi.org/10.1145/502807.502810 (may require access from within a university network)
  • additional references may be added in the course of the lecture

Subscribe to events of this course (icalendar)

Lecture Introduction/Relational Data Model DS2, April 7, 2025 in APB E007 File 1 File 2
Lecture First-Order Queries DS2, April 8, 2025 in APB E005 File 1 File 2
Lecture Complexity of Query Answering DS2, April 14, 2025 in APB E007 File 1 File 2
Lecture Query Complexity of FO Query Answering DS2, April 15, 2025 in APB E005 File 1 File 2
Exercise 1. Relational Algebra DS5, April 15, 2025 in APB E005 File 1 File 2
No session No Lecture: Easter Monday DS2, April 21, 2025 in APB E007
Lecture Data Complexity of FO Query Answering DS2, April 22, 2025 in APB E005 File 1 File 2
Exercise 2. First-Order Queries DS5, April 22, 2025 in APB E005 File 1 File 2
Lecture Conjunctive Queries DS2, April 28, 2025 in APB E007 File 1 File 2
Lecture Tree-Like Conjunctive Queries (1) DS2, April 29, 2025 in APB E005 File 1 File 2
Exercise 3. Complexity of First-Order Queries DS5, April 29, 2025 in APB E005 File 1 File 2
Lecture Tree-Like Conjunctive Queries (2) DS2, May 5, 2025 in APB E007
Lecture Query Optimisation DS2, May 6, 2025 in APB E005
Exercise 4. Conjunctive Queries, CSP, and Hypergraphs DS5, May 6, 2025 in APB E005 File
Lecture Conjunctive Query Optimisation DS2, May 12, 2025 in APB E007
Lecture Conjunctive Query Optimisation (continued) DS2, May 13, 2025 in APB E005
Exercise 5. Tree Width and Hypertree Width DS5, May 13, 2025 in APB E005
Lecture Query Expressiveness DS2, May 19, 2025 in APB E007
Lecture Query Expressiveness (continued) DS2, May 20, 2025 in APB E005
Exercise 6. Trakhtenbrot's Theorem DS5, May 20, 2025 in APB E005
Lecture Introduction to Datalog / Datalog Complexity DS2, May 26, 2025 in APB E007
Lecture Datalog Expressivity and Containment DS2, May 27, 2025 in APB E005
Exercise 7. FO Query Expressivity DS5, May 27, 2025 in APB E005
Lecture Datalog Expressivity and Containment (continued) DS2, June 2, 2025 in APB E007
Lecture Datalog Evaluation (1) DS2, June 3, 2025 in APB E005
Exercise 8. Datalog DS5, June 3, 2025 in APB E005
No session No Lecture: Pentecost DS2, June 9, 2025 in APB E007
No session No Lecture: Pentecost DS2, June 10, 2025 in APB E005
No session No Exercise: Pentecost DS5, June 10, 2025 in APB E005
Lecture Datalog Evalution (2) / Graph Databases DS2, June 16, 2025 in APB E007
Lecture Path Queries DS2, June 17, 2025 in APB E005
Exercise 9. Semi-Positive Datalog DS5, June 17, 2025 in APB E005
Lecture Dependencies DS2, June 23, 2025 in APB E007
Lecture The Chase DS2, June 24, 2025 in APB E005
Exercise 10. Datalog Evaluation DS5, June 24, 2025 in APB E005
Lecture The Chase (continued; termination and acyclicity) DS2, June 30, 2025 in APB E007
Lecture Query Answering Beyond Acyclic TGDs DS2, July 1, 2025 in APB E005
Exercise 11. Graph Databases and Path Queries DS5, July 1, 2025 in APB E005
Lecture TBA DS2, July 7, 2025 in APB E007
Lecture TBA DS2, July 8, 2025 in APB E005
Exercise 12. Dependencies DS5, July 8, 2025 in APB E005
Lecture Outlook/Summary DS2, July 14, 2025 in APB E007
Consultation Consultation (time for your questions) DS2, July 15, 2025 in APB E005


Calendar