Aktuelle Version vom 26. Oktober 2020, 18:53 Uhr

Foundations of Databases and Query Languages

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

Dozent

Markus Krötzsch

Tutor

Tomáš Masopust

Umfang (SWS)

2/2/0

Module

Leistungskontrolle

Mündliche Prüfung

Vorlesungsreihe

Database Theory

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

@@ Zeile 6: / Zeile 6: @@
 |Term=SS
 |Year=2015
+|Lecture series=Database Theory
 |Module=INF-B-510,INF-B-520,INF-BAS6,INF-VERT6,MCL-KR,MCL-PI,MCL-TCSL
 |SWSLecture=2
@@ Zeile 53: / Zeile 54: @@
 |Date=2015/04/13
 |DS=DS3
-|Download=FDQLSS15-lecture-01.pdf, FDQLSS15-lecture-01-2x2.pdf,
+|Download=FDQLSS15-lecture-01.pdf,FDQLSS15-lecture-01-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 61: / Zeile 62: @@
 |Date=2015/04/17
 |DS=DS4
-|Download=FDQL15-exercise01.pdf,
+|Download=FDQL15-exercise01.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 69: / Zeile 70: @@
 |Date=2015/04/20
 |DS=DS3
-|Download=FDQLSS15-lecture-02.pdf, FDQLSS15-lecture-02-2x2.pdf,
+|Download=FDQLSS15-lecture-02.pdf,FDQLSS15-lecture-02-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 77: / Zeile 78: @@
 |Date=2015/04/24
 |DS=DS4
-|Download=FDQL15-exercise02.pdf,
+|Download=FDQL15-exercise02.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 85: / Zeile 86: @@
 |Date=2015/04/27
 |DS=DS3
-|Download=FDQLSS15-lecture-03.pdf, FDQLSS15-lecture-03-2x2.pdf
+|Download=FDQLSS15-lecture-03.pdf,FDQLSS15-lecture-03-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 93: / Zeile 94: @@
 |Date=2015/05/04
 |DS=DS3
-|Download=FDQLSS15-lecture-04.pdf, FDQLSS15-lecture-04-2x2.pdf,
+|Download=FDQLSS15-lecture-04.pdf,FDQLSS15-lecture-04-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 101: / Zeile 102: @@
 |Date=2015/05/08
 |DS=DS4
-|Download=FDQL15-exercise03.pdf,
+|Download=FDQL15-exercise03.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 109: / Zeile 110: @@
 |Date=2015/05/11
 |DS=DS3
-|Download=FDQLSS15-lecture-05.pdf, FDQLSS15-lecture-05-2x2.pdf,
+|Download=FDQLSS15-lecture-05.pdf,FDQLSS15-lecture-05-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 117: / Zeile 118: @@
 |Date=2015/05/15
 |DS=DS4
-|Download=FDQL15-exercise04.pdf,
+|Download=FDQL15-exercise04.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 125: / Zeile 126: @@
 |Date=2015/05/18
 |DS=DS3
-|Download=FDQLSS15-lecture-06.pdf, FDQLSS15-lecture-06-2x2.pdf,
+|Download=FDQLSS15-lecture-06.pdf,FDQLSS15-lecture-06-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 133: / Zeile 134: @@
 |Date=2015/05/22
 |DS=DS4
-|Download=FDQL15-exercise05.pdf,
+|Download=FDQL15-exercise05.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 141: / Zeile 142: @@
 |Date=2015/06/01
 |DS=DS3
-|Download=FDQLSS15-lecture-07.pdf, FDQLSS15-lecture-07-2x2.pdf
+|Download=FDQLSS15-lecture-07.pdf,FDQLSS15-lecture-07-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 149: / Zeile 150: @@
 |Date=2015/06/05
 |DS=DS4
-|Download=FDQL15-exercise06.pdf,
+|Download=FDQL15-exercise06.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 157: / Zeile 158: @@
 |Date=2015/06/08
 |DS=DS3
-|Download=FDQLSS15-lecture-08.pdf, FDQLSS15-lecture-08-2x2.pdf,
+|Download=FDQLSS15-lecture-08.pdf,FDQLSS15-lecture-08-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 165: / Zeile 166: @@
 |Date=2015/06/12
 |DS=DS4
-|Download=FDQL15-exercise07.pdf,
+|Download=FDQL15-exercise07.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 173: / Zeile 174: @@
 |Date=2015/06/15
 |DS=DS3
-|Download=FDQLSS15-lecture-09.pdf, FDQLSS15-lecture-09-2x2.pdf,
+|Download=FDQLSS15-lecture-09.pdf,FDQLSS15-lecture-09-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 181: / Zeile 182: @@
 |Date=2015/06/19
 |DS=DS4
-|Download=FDQL15-exercise08.pdf,
+|Download=FDQL15-exercise08.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 189: / Zeile 190: @@
 |Date=2015/06/22
 |DS=DS3
-|Download=FDQLSS15-lecture-10.pdf, FDQLSS15-lecture-10-2x2.pdf,
+|Download=FDQLSS15-lecture-10.pdf,FDQLSS15-lecture-10-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 197: / Zeile 198: @@
 |Date=2015/06/26
 |DS=DS4
-|Download=FDQL15-exercise09.pdf,
+|Download=FDQL15-exercise09.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 205: / Zeile 206: @@
 |Date=2015/06/29
 |DS=DS3
-|Download=FDQLSS15-lecture-11.pdf, FDQLSS15-lecture-11-2x2.pdf,
+|Download=FDQLSS15-lecture-11.pdf,FDQLSS15-lecture-11-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 220: / Zeile 221: @@
 |Date=2015/07/06
 |DS=DS3
-|Download=FDQLSS15-lecture-12.pdf, FDQLSS15-lecture-12-2x2.pdf,
+|Download=FDQLSS15-lecture-12.pdf,FDQLSS15-lecture-12-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 228: / Zeile 229: @@
 |Date=2015/07/10
 |DS=DS4
-|Download=FDQL15-exercise11.pdf,
+|Download=FDQL15-exercise11.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 236: / Zeile 237: @@
 |Date=2015/07/13
 |DS=DS3
-|Download=FDQLSS15-lecture-13.pdf, FDQLSS15-lecture-13-2x2.pdf
+|Download=FDQLSS15-lecture-13.pdf,FDQLSS15-lecture-13-2x2.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 244: / Zeile 245: @@
 |Date=2015/07/17
 |DS=DS4
-|Download=FDQL15-exercise12.pdf,
+|Download=FDQL15-exercise12.pdf
 }}
 {{Vorlesung Zeiten
@@ Zeile 252: / Zeile 253: @@
 |Date=2015/07/20
 |DS=DS3
-|Download=FDQLSS15-lecture-14.pdf, FDQLSS15-lecture-14-2x2.pdf,
+|Download=FDQLSS15-lecture-14.pdf,FDQLSS15-lecture-14-2x2.pdf
 }}
 {{Vorlesung Zeiten

Foundations of Databases and Query Languages (SS2015): Unterschied zwischen den Versionen