Database Theory
Database Theory
Course with SWS 4/2/0 (lecture/exercise/practical) in SS 2020
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Oral exam
Lecture series
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. If the university reopens later on during the semester, we will probably revert to a standard, in-person lecture. For now, we will be doing the following:
- Every week on Tuesday, we will publish two videos with the weekly lectures.
- Every week on Monday, we will post one video with the weekly exercises.
- The videos with the lectures and exercises will be posted on this webpage under the "Dates and Materials" tab.
- Every week, we will host a "live session" in which the students can ask us questions. This session, which will take place on Wednesdays from 11:10 to 12:40, can be joined using this link (if you cannot access the chatroom, do send us an email).
- We have set up an online forum using Opal in which the students can post questions and discuss topics related to this course.
- Note that we will neither post an exercise video nor host a "live session" in the first week of the semester. That is, we will only post two videos with the weekly lectures in the first week.
When the university reopens, we will follow this schedule:
- The weekly lecture sessions will take place on Tuesdays from 14:50 to 16:20 and Wednesdays from 11:10 to 12:40.
- The weekly exercise session will take place on Tuesdays from 11:10 to 12:40.
All sessions will take place in room APB/E005.
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 | DS7, April 7, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | First-Order Queries (part 1) | DS8, April 7, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Relational Algebra | DS8, April 13, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | First-Order Queries (part 2) | DS7, April 14, 2020 in Screencast | File |
| Lecture | Complexity of Query Answering | DS8, April 14, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | First-Order Queries | DS8, April 20, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Complexity of FO Query Answering (1) | DS7, April 21, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Complexity of FO Query Answering (2) | DS8, April 21, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Complexity of FO Query Answering | DS8, April 27, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Conjunctive Queries | DS7, April 28, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Tree-Like Conjunctive Queries (1) | DS8, April 28, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Conjunctive Queries, CSP, and Hypergraphs | DS8, May 4, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Tree-Like Conjunctive Queries (2) | DS7, May 5, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Query Optimisation | DS8, May 5, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Treewidth and Hypertreewidth | DS8, May 11, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Conjunctive Query Optimisation | DS7, May 12, 2020 in Screencast | File 1, File 2, File 3 |
| No session | No lecture: Dies Academicus | DS8, May 12, 2020 in N/a | |
| Exercise | Trakhtenbrot's Theorem | DS8, May 18, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Query Expressiveness (Part 1) | DS7, May 19, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Query Expressiveness (Part 2) | DS8, May 19, 2020 in Screencast | |
| Exercise | Query Optimisation and FO Query Expressivity | DS8, May 25, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Datalog Introduction | DS7, May 26, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Datalog Expressivity | DS8, May 26, 2020 in Screencast | File 1, File 2, File 3 |
| No session | No Exercise Session: Pentecost | DS8, June 1, 2020 in N/a | |
| No session | No Lecture: Pentecost | DS7, June 2, 2020 in N/a | |
| No session | No Lecture: Pentecost | DS8, June 2, 2020 in N/a | |
| Exercise | Datalog | DS8, June 8, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Datalog Evaluation (1) | DS7, June 9, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Datalog Evaluation (2) | DS8, June 9, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Semi-Positive Datalog | DS8, June 15, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Graph Databases | DS7, June 16, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Regular Path Queries | DS8, June 16, 2020 in Screencast | File 1, File 2, File 3 |
| No session | No Exercise Session | DS8, June 22, 2020 in N/a | |
| No session | No Lecture | DS7, June 23, 2020 in N/a | |
| No session | No Lecture | DS8, June 23, 2020 in N/a | |
| Exercise | Datalog Evaluation | DS8, June 29, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Dependencies | DS7, June 30, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | The Chase | DS8, June 30, 2020 in Screencast | File 1, File 2, File 3 |
| Exercise | Graph Databases and Path Queries | DS8, July 6, 2020 in Screencast | File 1, File 2, File 3 |
| Lecture | Query Answering Beyond Acyclic TGDs | DS7, July 7, 2020 in Screencast | File 1, File 2, File 3 |
| No session | No Lecture | DS8, July 7, 2020 in Screencast | |
| Exercise | Dependencies | DS8, July 13, 2020 in Screencast | File 1, File 2, File 3 |
Calendar
