Database Theory
Database Theory
Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2023
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Oral exam
Matrix channel
Lecture series
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, 2023-04-11.
- Room change: the first lecture on Monday, 2023-04-03, takes place in APB 3027.
- Room change: the second lecture on Tuesday, 2023-04-04, takes place in APB E009.
Examinations
For the oral exams, we have blocked two dates this term:
- Monday, 2023-07-17
- Friday, 2023-07-28
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, the 2018 lecture Database Theory, and the 2019 lecture Database Theory. 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 will be added in the course of the lecture
Subscribe to events of this course (icalendar)
| Lecture | Introduction/Relational Data Model | DS2, April 3, 2023 in APB 3027 | File |
| Lecture | First-Order Queries | DS2, April 4, 2023 in APB E009 | File |
| No session | No Lecture: Easter Monday | DS2, April 10, 2023 in APB E007 | |
| Lecture | Complexity of Query Answering | DS2, April 11, 2023 in APB E005 | File |
| Exercise | 1. Relational Algebra | DS5, April 11, 2023 in APB E005 | File 1, File 2 |
| Lecture | Query Complexity of FO Query Answering | DS2, April 17, 2023 in APB E007 | File |
| Lecture | Data Complexity of FO Query Answering | DS2, April 18, 2023 in APB E005 | File |
| Exercise | 2. First-Order Queries | DS5, April 18, 2023 in APB E005 | File 1, File 2 |
| Lecture | Conjunctive Queries | DS2, April 24, 2023 in APB E007 | File |
| Lecture | Tree-Like Conjunctive Queries (1) | DS2, April 25, 2023 in APB E005 | File |
| Exercise | 3. Complexity of First-Order Queries | DS5, April 25, 2023 in APB E005 | File 1, File 2 |
| No session | No Lecture: International Workers' Day | DS2, May 1, 2023 in APB E007 | |
| Lecture | Tree-Like Conjunctive Queries (2) | DS2, May 2, 2023 in APB E005 | File |
| Exercise | 4. Conjunctive Queries, CSP, and Hypergraphs | DS5, May 2, 2023 in APB E005 | File 1, File 2 |
| Lecture | Query Optimisation | DS2, May 8, 2023 in APB E007 | File |
| Lecture | Conjunctive Query Optimisation | DS2, May 9, 2023 in APB E005 | File |
| Exercise | 5. Tree Width and Hypertree Width | DS5, May 9, 2023 in APB E005 | File 1, File 2 |
| Lecture | Conjunctive Query Optimisation (continued) | DS2, May 15, 2023 in APB E007 | |
| Lecture | Query Expressiveness | DS2, May 16, 2023 in APB E005 | File |
| Exercise | 6. Trakhtenbrot's Theorem | DS5, May 16, 2023 in APB E005 | File 1, File 2 |
| Lecture | Query Expressiveness (continued) | DS2, May 22, 2023 in APB E007 | |
| Lecture | Introduction to Datalog / Datalog Complexity | DS2, May 23, 2023 in APB E005 | File |
| Exercise | 7. FO Query Expressivity | DS5, May 23, 2023 in APB E005 | File 1, File 2 |
| No session | No Lecture: Pentecost | DS2, May 29, 2023 in APB E007 | |
| No session | No Lecture: Pentecost | DS2, May 30, 2023 in APB E005 | |
| No session | No Exercise: Pentecost | DS5, May 30, 2023 in APB E005 | |
| Lecture | Datalog Expressivity and Containment | DS2, June 5, 2023 in APB E007 | File |
| Lecture | Datalog Expressivity and Containment (continued) | DS2, June 6, 2023 in APB E005 | |
| Exercise | 8. Datalog | DS5, June 6, 2023 in APB E005 | File 1, File 2 |
| Lecture | Datalog Evaluation (1) | DS2, June 12, 2023 in APB E007 | File |
| Lecture | Datalog Evalution (2) / Graph Databases | DS2, June 13, 2023 in APB E005 | File |
| Exercise | 9. Semi-Positive Datalog | DS5, June 13, 2023 in APB E005 | File 1, File 2 |
| Lecture | Path Queries | DS2, June 19, 2023 in APB E007 | File |
| Lecture | Dependencies | DS2, June 20, 2023 in APB E005 | File |
| Exercise | 10. Datalog Evaluation | DS5, June 20, 2023 in APB E005 | File 1, File 2 |
| Lecture | The Chase | DS2, June 26, 2023 in APB E007 | File |
| Lecture | The Chase (continued; termination and acyclicity) | DS2, June 27, 2023 in APB E005 | |
| Exercise | 11. Graph Databases and Path Queries | DS5, June 27, 2023 in APB E005 | File 1, File 2 |
| Lecture | Query Answering Beyond Acyclic TGDs | DS2, July 3, 2023 in APB E007 | |
| Lecture | Outlook/Summary | DS2, July 4, 2023 in APB E005 | |
| Exercise | 12. Dependencies | DS5, July 4, 2023 in APB E005 | File 1, File 2 |
| Consultation | Consultation (time for your questions) | DS5, July 11, 2023 in APB E005 |
Calendar
