Datenbanktheorie
VU 181.140 (2.0) Wintersemester 2020
Reinhard Pichler
|
Since a TUWEL course has been created for this lecture, the course homepage will no longer be maintained. |
General information
- Language. This lecture will most probably be held in English since it is part of the English master's programme in "Logic and Computation".
- Place. Due to the Covid-19 situation, all classes will be held online via Zoom. The Zoom link is shown in TUWEL.
- Time. The course has a regular meeting time. Classes will be held Fridays, 09:15 - 11:00.
- Prerequisites. This course is designed for master's students. It is highly recommended to attend this course after the course Formale Methoden der Informatik (185.291). Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory to the extent taught in the course "Formale Methoden der Informatik (185.291)". Above all, students should have the skills and knowledge taught in the introduction to complexity theory in that course. In particular, students should have a clear understanding of the central concept of "problem reduction" and they should have no difficulty with the exercise sheet (block 1) of the course Formale Methoden der Informatik (185.291).
Registration and Admission
- Registration in TISS is required for this course! (Attention: registration != subscription)
- Admission to the course requires positive assessment in a quiz at the beginning of the term
(details to be announced in the first class). Each student has at most two attempts:
- Tuesday, 6 October 2020, 09:00 - 11:00
- Tuesday, 13 October 2020, 09:00 - 11:00
Course overview
In this course, some fundamental aspects of query languages will be touched on. The following topics will be covered (as time permits):- Relational Query Languages
- Introduction to Datalog
- Relational Algebra vs. First-Order Logic (Codd's Theorem)
- Undecidability Results (Trakhtenbrot's Theorem)
- Complexity of Query Evaluation
- (Acyclic) Conjunctive Queries
- Inexpressibility Results (Ehrenfeucht-Fraïssé Games)
- Beyond relational data
Schedule of lectures
| Lecture | Date | Topic | Slides | Supplementary material | 1 | Friday, 02 October 09:15 - 11:00 |
General Information short recapitulation of the lecture Formale Methoden der Informatik (185.291) |
dbt00
cc02 |
|
| Tuesday, 06 October 09:00 - 11:00 |
Quiz, first attempt |
|
||
| 2 | Friday, 09 October 09:15 - 11:00 |
Introduction: Relational Query Languages Datalog |
|
|
| Tuesday, 13 October 09:00 - 11:00 |
Quiz, second attempt |
|
||
| 3 | Friday, 16 October 09:15 - 11:00 |
Datalog (continued)
|
|
|
| 4 | Friday, 23 October 09:15 - 11:00 |
Datalog (continued)
|
|
|
| 5 | Friday, 30 October 09:15 - 11:00 |
Codd's Theorem | |
|
| 6 | Friday, 06 November 09:15 - 11:00 |
Trakhtenbrot's Theorem
Information on the Report and Presentation |
|
|
| 7 | Friday, 13 November 09:15 - 11:00 |
Complexity of Query Evaluation
|
|
|
| 8 | Friday, 20 November 09:15 - 11:00 |
Conjunctive Queries | |
|
| 9 | Friday, 27 November 09:15 - 11:00 |
Conjunctive Queries (continued)
|
|
|
| 10 | Friday, 04 December 09:15 - 11:00 |
Ehrenfeucht-Fraïssé Games | |
|
| 11 | Friday, 11 December 09:15 - 11:00 |
Ehrenfeucht-Fraïssé Games
(continued) |
||
| Friday, 18 December |
no class
|
|
|
|
| 12 | Friday, 08 January 09:15 - 11:00 |
Beyond relational data | ||
| 13 | Friday, 15 January 09:15 - 11:00 |
students' presentations, part 1 |
|
|
| 14 | Friday, 22 January 09:15 - 11:00 |
students' presentations, part 2 |
|
|
| Friday, 29 January |
reserve
|
|
|
Assessment
Assessment will be based on students' presentations and an oral exam at the end of the term. Detailed information will be provided in the first class.Selection of References
S. Abiteboul, R. Hull, and V. Vianu: Foundations
of Databases, Addison-Wesley, 1995.
G. Gottlob, N. Leone, and
F. Scarcello: The
Complexity of Acyclic Conjunctive Queries, J. ACM 48(3): 431-498 (2001)
(acm digital library).
P. Kolaitis: On
the Expressive Power of Logics on Finite
Models
(pdf).
| Last modified 04 October, 2020 |