After successful completion of the course, students are able to

• enumerate various research areas of database theory research
• explain the most important questions concerning query languages
• analyse themselves the complexity and expressive power of query languages

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

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.

Remark: The course in the WS 2022 is planned to be held in person. If required by the Covid situation, the course will be held online via Zoom at the planned dates and times.

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 articel and an oral exam.

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