Database Theory

From International Center for Computational Logic

Database Theory

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

Lecturer

Tutor

SWS

  • 4/2/0

Modules

Examination method

  • Oral exam

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

An 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

All sessions will take place in room APB/E005. The default arrangement is as follows:

  • The weekly lecture sessions will take place on Tuesday DS2 (9:20 to 10:50) and Friday DS5 (2:50 to 4:20).
  • The weekly exercise session will take place on Wednesday DS3 (11:10 to 12:40).

In some weeks, the Wednesday exercises will be swapped with the Friday lectures

Exceptions:

  • The first exercise session will take place in the second week on 12 April 2019.
  • There will NOT be a lecture on the 5th of April.

Legacy

This course has first been taught at TU Dresden in the form of the 2015 lecture Foundations of Databases and Query Languages and the 2018 lecture Database Theory. The plan for this year's course will be very 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 2, 2019 in APB E005 File 1 File 2
Lecture First-Order Queries (part 1) DS2, April 9, 2019 in APB E005 File 1 File 2
Lecture First-Order Queries (part 2) DS3, April 10, 2019 in APB E005
Exercise Relational Algebra DS5, April 12, 2019 in APB E005 File
Lecture Complexity of Query Answering DS2, April 16, 2019 in APB E005 File 1 File 2
Exercise First-Order Queries DS3, April 17, 2019 in APB E005 File
Lecture Complexity of FO Query Answering (1) DS2, April 23, 2019 in APB E005 File 1 File 2
Lecture Complexity of FO Query Answering (2) DS3, April 24, 2019 in APB E005 File 1 File 2
Exercise Complexity of FO Query Answering DS5, April 26, 2019 in APB E005 File
Lecture Conjunctive Queries DS2, April 30, 2019 in APB E005 File 1 File 2
Lecture Tree-Like Conjunctive Queries (1) DS5, May 3, 2019 in APB E005 File 1 File 2
Lecture Tree-Like Conjunctive Queries (2) DS2, May 7, 2019 in APB E005 File 1 File 2
Lecture Query Optimisation DS3, May 8, 2019 in APB E005 File 1 File 2
Exercise Conjunctive Queries, CSP, and Hypergraphs DS5, May 10, 2019 in APB E005 File
Lecture Conjunctive Query Optimisation DS2, May 14, 2019 in APB E005 File 1 File 2
Lecture Query Expressiveness (Part 1) DS3, May 15, 2019 in APB E005 File 1 File 2
Exercise Treewidth and Hypertreewidth DS5, May 17, 2019 in APB E005 File
Lecture Query Expressiveness (Part 2) DS2, May 21, 2019 in APB E005
Exercise Trakhtenbrot's Theorem DS5, May 24, 2019 in APB E005 File
Lecture Introduction to Datalog DS2, May 28, 2019 in APB E005 File 1 File 2
Lecture Datalog Complexity DS3, May 29, 2019 in APB E005 File 1 File 2
Exercise Query Optimisation and FO Query Expressivity DS5, May 31, 2019 in APB E005 File
Lecture Datalog Evaluation (1) DS2, June 4, 2019 in APB E005 File 1 File 2
Lecture Datalog Evaluation (2) DS3, June 5, 2019 in APB E005 File 1 File 2
Exercise Datalog DS5, June 7, 2019 in APB E005 File
Lecture Graph Databases and Path Queries DS2, June 18, 2019 in APB E005 File 1 File 2
Lecture (Cancelled) DS2, June 25, 2019 in APB E005
Exercise (Cancelled) DS3, June 26, 2019 in APB E005 File
Exercise Datalog Evaluation DS5, June 28, 2019 in APB E005 File
Lecture Dependencies DS2, July 2, 2019 in APB E005 File 1 File 2
Lecture The Chase DS3, July 3, 2019 in APB E005 File 1 File 2
Exercise Graph Databases and Path Queries DS5, July 5, 2019 in APB E005 File
Lecture Query Answering Beyond Acyclic TGDs DS2, July 9, 2019 in APB E005 File 1 File 2
Lecture Outlook DS3, July 10, 2019 in APB E005 File 1 File 2
Exercise Dependencies DS5, July 12, 2019 in APB E005 File


Calendar