Foundations of Query Languages

Organizers:

Course Contents:

The lecture covers a variety of topics on the foundations of database query languages, discussing classical as well as recent developments in database research.

We will discuss about the expressiveness of query languages, relational algebra, which is the theoretical foundation of SQL. We will further consider a more expressive language such as Datalog. Foundations on semantic query optimizations will be addressed, such as conjunctive queries. Theoretical aspects on relational database design is another topic.

During the lecture, various algorithms with the corresponding complexities will be introduced, such that at the end of the lecture, a wide spectrum on computational complexies will be constructed based on the query language related problems.

Necessary Prerequisites:

The key course (Kursvorlesung) 'Databases and Information Systems' or an equivalent Database course. A course on computational complexity is helpful, but not obligatory.

Time, Location and Organization:

Lecture: Mo 2pm - 4pm, Building 101, Room 01-018

Tutorials: Wed 2pm - 4pm, Bulding 101, Room 01-018

Language: English

ECTS: 6 Points

Program of Study: Master CS, Applied CS, Lehramt

Exam: 19th August 2011, 12:00pm, Kinohoersaal im Mensa-Gebaeude

Exercises

Tutorials will take place on Wednesdays. Every exercise sheet is published on Wednesday and your solution to it is to be handed in the next Wednesday before the exercise class begins. The due date is written on the sheet.

Reading Assignments

During the semester, related research papers will be distributed and the students are required to read them and submit short reviews.

Exam

You have to submit at least 50% of the exercise solutions to be qualified to take the exam.

Literature:

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

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X