Database Theory
Database Theory
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in SS 2021
Dozent
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Mündliche Prüfung
Vorlesungsreihe
Important Information: The oral exam is going to take place on August 13th 2021. If you want to take the exam, please send an email to Sebastian Rudolph and Jonas Karge.
Announcement: because of the COVID-19 pandemic, the schedule and location of this lecture have changed quite a bit. For more information have a look at the corresponding section below.
Course Description
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
Because of the ongoing COVID-19 pandemic, we have decided to transform this lecture into an online course. The lecture and tutorials will be held as virtual live sessions via Zoom (lecture) and BigBlueButton (tutorials). Please use the link below:
Zoom: https://tu-dresden.zoom.us/j/83224074259?pwd=QXJWR2wxZ3J1TktWYjIyV2F2T1lDUT09
Password: 5j%@cP4*
The links for the exercise sessions are:
With ZIH-Login: https://selfservice.zih.tu-dresden.de/l/link.php?m=139763&p=b55653ea Without ZIH-Login: https://selfservice.zih.tu-dresden.de/link.php?m=139763&p=922d5a38
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.
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Introduction/Relational Model | DS5, 12. April 2021 in Videokonferenz | Datei |
| Vorlesung | First-Order Queries | DS6, 12. April 2021 in Videokonferenz | Datei |
| Entfällt | No lecture | DS5, 19. April 2021 in N/a | |
| Entfällt | No lecture | DS6, 19. April 2021 in N/a | |
| Übung | Relational Algebra | DS3, 20. April 2021 in Videokonferenz | Datei |
| Vorlesung | Complexity of Query Answering | DS5, 26. April 2021 in Videokonferenz | Datei |
| Vorlesung | Complexity of FO Query Answering (1) | DS6, 26. April 2021 in Videokonferenz | Datei |
| Übung | First-Order Queries | DS3, 27. April 2021 in Videokonferenz | Datei |
| Vorlesung | Complexity of FO Query Answering (2) | DS5, 3. Mai 2021 in Videokonferenz | Datei |
| Vorlesung | Conjunctive Queries | DS6, 3. Mai 2021 in Videokonferenz | Datei |
| Entfällt | Exercise session postponed to following week | DS3, 4. Mai 2021 in N/a | |
| Vorlesung | Tree-Like Conjunctive Queries (1) | DS5, 10. Mai 2021 in Videokonferenz | Datei |
| Vorlesung | Tree-Like Conjunctive Queries (2) | DS6, 10. Mai 2021 in Videokonferenz | Datei |
| Übung | Complexity of FO Query Answering | DS3, 11. Mai 2021 in Videokonferenz | Datei |
| Vorlesung | Query Optimisation | DS5, 17. Mai 2021 in Videokonferenz | Datei |
| Vorlesung | Conjunctive Query Optimisation | DS6, 17. Mai 2021 in Videokonferenz | Datei |
| Übung | Conjunctive Queries, CSP, and Hypergraphs | DS3, 18. Mai 2021 in Videokonferenz | Datei |
| Entfällt | No Lecture: Pentecost | DS5, 24. Mai 2021 in N/a | |
| Entfällt | No Lecture: Pentecost | DS6, 24. Mai 2021 in N/a | |
| Entfällt | No Exercise Session: Pentecost | DS3, 25. Mai 2021 in N/a | |
| Vorlesung | Query Expressiveness (Part 1) | DS5, 31. Mai 2021 in Videokonferenz | Datei |
| Vorlesung | Query Expressiveness (Part 2) | DS6, 31. Mai 2021 in Videokonferenz | |
| Übung | Treewidth and Hypertreewidth | DS3, 1. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Datalog Introduction | DS5, 7. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Datalog Expressivity | DS6, 7. Juni 2021 in Videokonferenz | Datei |
| Übung | Trakthenbrot's Theorem | DS3, 8. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Datalog Evaluation (1) | DS5, 14. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Datalog Evaluation (2) | DS6, 14. Juni 2021 in Videokonferenz | Datei |
| Übung | Query Optimisation and FO Query Expressivity | DS3, 15. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Graph Databases | DS5, 21. Juni 2021 in Videokonferenz | Datei |
| Übung | Datalog | DS3, 22. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Regular Path Queries | DS5, 28. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | Dependencies | DS6, 28. Juni 2021 in Videokonferenz | Datei |
| Übung | Semi-Positive Datalog | DS3, 29. Juni 2021 in Videokonferenz | Datei |
| Vorlesung | The Chase | DS5, 5. Juli 2021 in Videokonferenz | Datei |
| Vorlesung | Query Answering Beyond Acyclic TGDs | DS6, 5. Juli 2021 in Videokonferenz | Datei |
| Übung | Datalog Evaluation | DS3, 6. Juli 2021 in Videokonferenz | Datei |
| Übung | Graph Databases and Path Queries | DS3, 13. Juli 2021 in Videokonferenz | Datei |
| Vorlesung | Lecture Recap | DS5, 19. Juli 2021 in Videokonferenz | Datei |
| Übung | Dependencies | DS3, 20. Juli 2021 in Videokonferenz | Datei |
Kalender
