Datenbanktheorie
VU 181.140 (2.0) Sommersemester 2012
Reinhard Pichler
|
|
General informationen
- Language. This lecture will most probably be held in English since it is part of the European Master's Program in Computational Logic (EMCL) curriculum.
- Place. Classes will be held in the Seminarraum 188/2 (Favoritenstraße 9-11, 4th floor, stairs 3).
- Time. The course has a regular meeting time. Classes will be held Tuesdays, 9:00 sharp - 11:00. Depending on the number of students, additional classes will be needed for the students' presentations at the end of the semester. The first class meets on Tuesday, 6 March, 9:00 - 11:00.
- Prerequisites. This course is designed for master's students. It is highly recommend 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").
Registration
Registration in TISS is required for this course!!
(Attention: registration != subscription)
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, 0-1 Laws)
Schedule of lectures (preliminary plan)
| Lecture | Date/Place | Topic | Slides | Supplementary material | 1 | Tuesday, 06-March 9:00 - 11:00 Seminarraum 188/2 |
General Information Introduction: Relational Query Languages |
dbt00,
4x1 dbt01, 4x1 |
|
| 2 | Tuesday, 13-March 9:00 - 11:00 Seminarraum 188/2 |
Introduction to Datalog
| dbt02, 4x1 |
|
| 3 | Tuesday, 20-March 9:00 - 11:00 Seminarraum 188/2 |
Codd's Theorem | dbt03, 4x1 | |
| 4 | Tuesday, 27-March 9:00 - 11:00 Seminarraum 188/2 |
Trakhtenbrot's Theorem
Information on the Report and Presentation |
dbt04,
4x1
report, 4x1 |
|
| Tuesday, 17-April |
no class
|
|
|
|
| 5 | Tuesday, 24-April 9:00 - 11:00 Seminarraum 188/2 |
Complexity of Query Evaluation
|
dbt05,
4x1 |
|
| Tuesday, 01-May |
no class
|
|
|
|
| 6 | Tuesday, 8-May 9:00 - 11:00 Seminarraum 188/2 |
Conjunctive Queries |
dbt06,
4x1 |
|
| 7 | Tuesday, 15-May 9:00 - 11:00 Seminarraum 188/2 |
Conjunctive Queries (continued)
|
|
|
| 8 | Tuesday, 22-May 9:00 - 11:00 Seminarraum 188/2 |
Ehrenfeucht-Fraïssé Games | |
|
| Tuesday, 29-May |
no class
|
|
|
|
| 9 | Tuesday, 5-June 9:00 - 11:00 Seminarraum 188/2 |
Ehrenfeucht-Fraïssé Games
(continued) |
|
|
| 10 | Tuesday, 12-June 9:00 - 11:00 Seminarraum 188/2 |
students' presentations |
|
|
| 11 | Tuesday, 19-June 9:00 - 11:00 Seminarraum 188/2 |
students' presentations |
|
|
| 12 | Tuesday, 26-June 9:00 - 11:00 Seminarraum 188/2 |
students' presentations |
|
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).
G. Kolaitis: On
the Expressive Power of Logics on Finite
Models
(pdf).
| Last modified 16 March, 2012 |