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 2018

Dozent

Tutor

Umfang (SWS)

  • 4/2/0

Module

Leistungskontrolle

  • Mündliche Prüfung

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

UPDATE: All the three lectures on the 19th of June will take place in room APB 1004.

  • The weekly lecture sessions will take place on Tuesdays DS2 (9:20 to 10:50) and DS3 (11:10 to 12:40).
  • The weekly exercise session will take place on Tuesdays DS5 (14:50 to 16:20).
  • The first exercise session will take place in the second week, i.e., on 17 April 2017.
  • All sessions will take place in room APB/E005 except for the lectures on the 19th of June, which will take place in room APB 1004.

Legacy

This course has first been taught at TU Dresden in the form of the 2015 lecture Foundations of Databases and Query Languages. 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

Veranstaltungskalender abonnieren (icalendar)

Vorlesung Introduction/Relational Data Model DS2, 10. April 2018 in APB E005 Download Download
Vorlesung First-Order Queries DS3, 10. April 2018 in APB E005 Download Download
Vorlesung Query Answering Complexity DS2, 17. April 2018 in APB E005 Download Download
Vorlesung FO Query Answering Complexity (I) DS3, 17. April 2018 in APB E005 Download Download
Übung Relational Algebra DS5, 17. April 2018 in APB E005 Download
Übung First-Order Queries DS5, 24. April 2018 in APB E005 Download
Vorlesung FO Query Answering Complexity (II) DS2, 8. Mai 2018 in APB E005 Download Download
Vorlesung Conjunctive Queries DS3, 8. Mai 2018 in APB E005 Download Download
Übung First-order Query Complexity DS5, 8. Mai 2018 in APB E005 Download
Vorlesung Tree-Like Conjunctive Queries (1) DS2, 15. Mai 2018 in APB E005 Download Download
Vorlesung Tree-Like Conjunctive Queries (2) DS3, 15. Mai 2018 in APB E005 Download Download
Übung Conjunctive Queries, CSP, and Hypergraphs DS5, 15. Mai 2018 in APB E005 Download
Vorlesung Query Optimisation DS2, 29. Mai 2018 in APB E005 Download Download
Vorlesung Conjunctive Query Optimisation DS3, 29. Mai 2018 in APB E005 Download Download
Übung Treewidth and Hypertreewidth DS5, 29. Mai 2018 in APB E005 Download
Vorlesung Query language expressivity DS2, 5. Juni 2018 in APB E005 Download Download
Vorlesung Expressivity of FO queries DS3, 5. Juni 2018 in APB E005
Übung Trakhtenbrot's Theorem DS5, 5. Juni 2018 in APB E005 Download
Vorlesung Introduction to Datalog DS2, 12. Juni 2018 in APB E005 Download Download
Vorlesung Datalog Complexity DS3, 12. Juni 2018 in APB E005
Übung Query Optimsation DS5, 12. Juni 2018 in APB E005 Download
Vorlesung Datalog Expressivity and Query Containment DS2, 19. Juni 2018 in APB 1004 Download Download
Vorlesung Datalog Implementation (1) DS3, 19. Juni 2018 in APB 1004 Download Download
Übung Datalog DS5, 19. Juni 2018 in APB 1004 Download
Vorlesung Datalog Implementation (2) DS2, 26. Juni 2018 in APB E005 Download Download
Vorlesung Graph Databases DS3, 26. Juni 2018 in APB E005 Download Download
Übung Semi-positive Datalog DS5, 26. Juni 2018 in APB E005 Download Download
Vorlesung Regular Path Queries DS2, 3. Juli 2018 in APB E005 Download Download
Vorlesung Dependencies DS3, 3. Juli 2018 in APB E005 Download Download
Übung Datalog Evaluation DS5, 3. Juli 2018 in APB E005 Download
Vorlesung The Chase DS2, 10. Juli 2018 in APB E005 Download Download
Vorlesung Chase Termination and Acyclicity DS3, 10. Juli 2018 in APB E005
Übung Graph Databases and Path Queries DS5, 10. Juli 2018 in APB E005 Download
Vorlesung Query Answering Beyond Acyclic TGDs DS2, 17. Juli 2018 in APB E005 Download Download
Vorlesung Summary and Outlook DS3, 17. Juli 2018 in APB E005 Download Download
Übung Dependencies DS5, 17. Juli 2018 in APB E005 Download


Kalender

Lade …