Foundations of Databases and Query Languages

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

Foundations of Databases and Query Languages

Lehrveranstaltung mit SWS 2/2/0 (Vorlesung/Übung/Praktikum) in SS 2015

Dozent

Tutor

Umfang (SWS)

  • 2/2/0

Module

Leistungskontrolle

  • Mündliche Prüfung

Vorlesungsreihe


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 datamodel, 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


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.

Prerequistes

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.

Time plan

The general time plan is as follows:

  • Lectures: each Monday in DS3 (11:10–12:40)
  • Exercises: each Friday in DS4 (13:00–14:30)

However, there will be some exceptions that will be announced in the lecture. The first lecture is on Monday, 13 April 2015.

Legacy

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 DS3, 13. April 2015 in APB E005 Datei 1 Datei 2
Übung Relational algebra DS4, 17. April 2015 in APB E005 Datei
Vorlesung First-Order Queries DS3, 20. April 2015 in APB E005 Datei 1 Datei 2
Übung First-Order Queries DS4, 24. April 2015 in APB E005 Datei
Vorlesung Query Answering Complexity DS3, 27. April 2015 in APB E005 Datei 1 Datei 2
Vorlesung FO Query Answering Complexity DS3, 4. Mai 2015 in APB E005 Datei 1 Datei 2
Übung FO Query Answering Complexity DS4, 8. Mai 2015 in APB E005 Datei
Vorlesung Conjunctive Queries DS3, 11. Mai 2015 in APB E005 Datei 1 Datei 2
Übung Conjunctive Queries, CSP, and Hypergraphs DS4, 15. Mai 2015 in APB E005 Datei
Vorlesung Tree-Like Conjunctive Queries DS3, 18. Mai 2015 in APB E005 Datei 1 Datei 2
Übung Treewidth and Hypertree Width DS4, 22. Mai 2015 in APB E005 Datei
Vorlesung Query Optimisation DS3, 1. Juni 2015 in APB E005 Datei 1 Datei 2
Übung FO Query Optimisation and Trakhenbrot's Theorem DS4, 5. Juni 2015 in APB E005 Datei
Vorlesung CQ Optimisation and FO Expressivity DS3, 8. Juni 2015 in APB E005 Datei 1 Datei 2
Übung CQ Optimisation and FO Expressivity DS4, 12. Juni 2015 in APB E005 Datei
Vorlesung FO Expressivity and Introduction to Datalog DS3, 15. Juni 2015 in APB E005 Datei 1 Datei 2
Übung FO Expressivity and Introduction to Datalog DS4, 19. Juni 2015 in APB E005 Datei
Vorlesung Expressive Power and Complexity of Datalog DS3, 22. Juni 2015 in APB E005 Datei 1 Datei 2
Übung Datalog DS4, 26. Juni 2015 in APB E005 Datei
Vorlesung Datalog Optimisation and Evaluation DS3, 29. Juni 2015 in APB E005 Datei 1 Datei 2
Übung Datalog (part 2 of previous exercise) DS4, 3. Juli 2015 in APB 2026
Vorlesung Datalog Evaluation DS3, 6. Juli 2015 in APB E005 Datei 1 Datei 2
Übung Datalog Evaluation DS4, 10. Juli 2015 in APB E005 Datei
Vorlesung Graph Databases and Path Queries DS3, 13. Juli 2015 in APB E005 Datei 1 Datei 2
Übung Path Queries DS4, 17. Juli 2015 in APB E005 Datei
Vorlesung Database Theory in Practice DS3, 20. Juli 2015 in APB E005 Datei 1 Datei 2
Übung General Q&A Session DS4, 24. Juli 2015 in APB E005


Kalender