Database Theory

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

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

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=117024&p=c425f17c

Without ZIH-Login: https://selfservice.zih.tu-dresden.de/link.php?m=117024&p=cb77399b

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
Vorlesung Tree-Like Conjunctive Queries (2) DS6, 10. Mai 2021 in Videokonferenz
Übung Complexity of FO Query Answering DS3, 11. Mai 2021 in Videokonferenz Datei
Vorlesung Query Optimisation DS5, 17. Mai 2021 in Videokonferenz
Vorlesung Conjunctive Query Optimisation DS6, 17. Mai 2021 in Videokonferenz
Übung Conjunctive Queries, CSP, and Hypergraphs DS3, 18. Mai 2021 in BBB
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
Vorlesung Query Expressiveness (Part 2) DS6, 31. Mai 2021 in Videokonferenz
Übung Treewidth and Hypertreewidth DS3, 1. Juni 2021 in BBB
Vorlesung Datalog Introduction DS5, 7. Juni 2021 in Videokonferenz
Vorlesung Datalog Expressivity DS6, 7. Juni 2021 in Videokonferenz
Übung Trakthenbrot's Theorem DS3, 8. Juni 2021 in BBB
Vorlesung Datalog Evaluation (1) DS5, 14. Juni 2021 in Videokonferenz
Vorlesung Datalog Evaluation (2) DS6, 14. Juni 2021 in Videokonferenz
Übung Query Optimisation and FO Query Expressivity DS3, 15. Juni 2021 in BBB
Vorlesung Graph Databases DS5, 21. Juni 2021 in Videokonferenz
Vorlesung Regular Path Queries DS6, 21. Juni 2021 in Videokonferenz
Übung Datalog DS3, 22. Juni 2021 in BBB
Vorlesung Dependencies DS5, 28. Juni 2021 in Videokonferenz
Vorlesung The Chase DS6, 28. Juni 2021 in Videokonferenz
Übung Semi-Positive Datalog DS3, 29. Juni 2021 in BBB
Vorlesung Query Answering Beyond Acyclic TGDs DS5, 5. Juli 2021 in Videokonferenz
Übung Datalog Evaluation DS3, 6. Juli 2021 in BBB
Übung Graph Databases and Path Queries DS3, 13. Juli 2021 in BBB
Übung Dependencies DS3, 20. Juli 2021 in BBB


Kalender