After successful completion of the course, students are able to

• Analyze and compare formal models of database systems, including relational algebra and query languages based on first-order logic.
• Evaluate the theoretical underpinnings of query languages and their expressive power within the framework of computational complexity.
• Examine the mathematical foundations of data dependencies and their role in database normalization theory.
• Investigate theoretical aspects of query optimization, including the study of join algorithms and their complexity analysis.

Different from previous iterations, there will be no entrance exam this year!

Fundamental Aspects of database query languages:
*) relational query languages (introduction)
*) Datalog
*) Codd's Theorem: relational calculus, relational algebra, datalog
*) Trakhtenbrot's theorem
*) Complexity of query evaluation
*) Conjunctive queries
*) Expressive power, Ehrenfeucht-Fraisse games

Further details are available on the course website.

The first part of the course consists in presentations by the lecturer on the aspects of database query languages mentioned above.

In the second part of the course, the students have to present one research article each from this area

ECTS Breakdown

 2 h quiz 
 23 h lecture (10 classes including preparation)
 35 h research article (report, presentation)
 15 h preparation for oral exam
-----------------------------------------------------------
 75 h = 3 Ects

Assessment is based on the presentation of the research article and an oral exam.

The oral exam can only be taken after holding the presentation.

The oral exam can be repeated once.

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995, ISBN 0-201-53771-0.

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").