Aktuelles:

An dieser Stelle finden Sie im Laufe des Semesters aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt. Die Übungsscheine sind ausgestellt und können im Sekretariat bei Frau Nadland abgeholt werden. Die letzte Vorlesungsstunde fand am Dienstag, den 01.07.2008 statt. Am Donnerstag, den 03.07.2008 findet an Stelle der Vorlesung von 12:15 Uhr bis 14:00 Uhr eine Zusatz-Übungsstunde bzw. Fragestunde statt. Es wird insgesamt 9 Übungsblätter und ein Zusatzblatt geben. Einen Leistungsnachweis (Schein) bekommen alle Teilnehmer/innen, die mindestens 350 Punkte in den Übungsaufgaben erreicht haben. Die erste Vorlesung fand in der ersten Semesterwoche am Dienstag, den 01.04.2008 von 12:15 Uhr bis 14:00 Uhr im Magnus-Hörsaal, Robert-Mayer-Str. 11-15, statt. Die erste Übungsstunde fand am Dienstag, 08.04.2008 von 14:15 bis 16:00 Uhr im Magnus-Hörsaal statt. Die Vorlesungsfolien sowie Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen finden Sie (nach den Vorlesungen) im Logbuch.

Einführung:

Die theoretischen Grundlagen von modernen Datenbanksystemen beruhen zu einem wesentlichen Teil auf zahlreichen Verbindungen zur Logik. Eine relationale Datenbank ist aus Sicht der Logik eine Grundmenge mit mathematischen Relationen; eine SQL-Anfrage ist im Kern eine Formel der Logik erster Stufe. Aufgrund dieses Zusammenhangs ermöglichen Techniken aus dem Bereich der Logik es, präzise Aussagen über die Ausdrucksstärke und die Auswertungskomplexität von Datenbankanfragesprachen zu treffen. Die Vorlesung will den genannten Zusammenhang darstellen und die Grundzüge der Theorie relationaler Datenbanken vorstellen. Themen sind unter anderem: Verbindungen zwischen SQL und Logik, konjunktive Anfragen, Anfragesprachen mit Rekursion (Datalog), statische Analyse und Anfrageoptimierung (insbesondere von konjunktiven Anfragen), Ausdrucksstärke und Auswertungskomplexität von Anfragesprachen. Ziel dieser Veranstaltung ist, die theoretischen Grundlagen relationaler Datenbanksysteme zu verstehen. Dies beinhaltet u.a. die Fähigkeit, die Möglichkeiten und Grenzen der Ausdrucksstärke verschiedener Anfragesprachen sowie die zur Auswertung von Anfragen benötigten Ressourcen einschätzen zu können.

Inhalt:

Das Relationale Modell Konjunktive Anfragen (I) Relationale Algebra Relationenkalkül Konjunktive Anfragen (II) Abhängigkeiten und Normalformen Anfragesprachen mit Rekursion — Datalog Zusammenfassung und Ausblick auf weitere Themen

Logbuch:

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungs- und Übungsbetrieb:

Vorlesung: Dienstags und Donnerstags von 12-14 Uhr im Magnus Hörsaal, Robert-Mayer-Str. 11-15 Start der Vorlesung: 12:15 Uhr;   Ende der Vorlesung: 13:45 Uhr   Übung: Dienstags 14-16 Uhr im Magnus-Hörsaal.   Dozentin: Prof. Dr. Nicole Schweikardt Sprechstunde: Donnerstags 15-16 Uhr

Übungsaufgaben:

Es wird regelmäßig Übungsaufgaben geben, deren erfolgreiche Bearbeitung Voraussetzung für den Scheinerwerb ist. Blatt 1 (ausgeteilt am Di, 08.04.2008; abzugeben am Di, 15.04.2008) Blatt 2 (ausgeteilt am Do, 17.04.2008; abzugeben am Do, 24.04.2008) Blatt 3 (ausgeteilt am Do, 24.04.2008; abzugeben am Di, 06.05.2008) Blatt 4 (ausgeteilt am Do, 08.05.2008; abzugeben am Do, 15.05.2008) Blatt 5 (ausgeteilt am Di, 20.05.2008; abzugeben am Do, 29.05.2008) Blatt 6 (ausgeteilt am Do, 29.05.2008; abzugeben am Do, 05.06.2008; Hinweis: Aufgabe 4 wird auf das nächste Übungsblatt verschoben) Blatt 7 (ausgeteilt am Do, 05.06.2008; abzugeben am Do, 12.06.2008) Blatt 8 (ausgeteilt am Do, 12.06.2008; abzugeben am Do, 19.06.2008) Blatt 9 (ausgeteilt am Do, 19.06.2008; abzugeben am Do, 26.06.2008) Blatt 10 ("Zusatzblatt") (ausgeteilt am Do, 26.06.2008; abzugeben am Do, 03.07.2008)

Scheinerwerb:

Ein Leistungsnachweis (Schein) wird bei regelmäßiger aktiver Teilnahme ausgegeben, falls mindestens 40% aller Übungspunkte (d.h. insgesamt mindestens 350 Punkte) erreicht werden. Lösungen der Übungsaufgaben können alleine oder in 2-er Gruppen abgegeben werden. Es wird davon ausgegangen, dass jeder Teilnehmer alle von ihm selbst oder seiner 2-er Gruppe eingereichten Lösungen auch vorstellen kann.

Literatur:

[AHV] S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995. [AD] P. Atzeni, V. De Antonellis. Relational Database Theory. Addison Wesley Longman; 1st edition (January 1993). [ABS] S. Abiteboul, P. Buneman, D. Suciu. Data on the Web. Morgan Kaufmann Publishers, 2000. [M] D. Maier. The Theory of Relational Databases. Computer Science Press, 1983. [CM] A. K. Chandra und P. M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC 1977), May 4-6, 1977, Boulder, Colorado, USA. ACM 1977.   [G] M. Grohe. Parameterized Complexity for the Database Theorist. SIGMOD Record, Volume 31, Number 4, 2002, pages 86-96.   [SH] G. Saake und A. Heuer. Datenbanken: Implementierungstechniken. International Thomson Publishing, 800 Seiten, Mai 1999. [LV] D. Leinders und J. Van den Bussche. On the complexity of division and set joins in the relational algebra. Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS 2005), pages 76-83, 2005.   [Sch] N. Schweikardt. Logik und Komplexität. Skript zur Vorlesung im Sommersemester 2007, Humboldt-Universität zu Berlin.   Download (pdf):  hier. [Y] M. Yannakakis. Algorithms for acyclic database schemas. Proceedings of the 7th International Conference on Very Large Databases (VLDB 1981), pages 82-94, 1981.   [Sca] F. Scarcello. Query Answering Exploiting Structural Properties. SIGMOD Record , vol. 34, No 3, pages 91-99, Sept. 2005.   [CV] S. Chaudhuri und M. Vardi. Optimization of Real Conjunctive Queries. Proceedings of the 12th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS 1993), pages 59-70, 1993.   [AL] M. Arenas und L. Libkin. An Information-Theoretic Approach to Normal Forms for Relational and XML Data. Journal of the ACM, Volume 52, No. 2, 2005, pages 246-283.

Links:

• ACM Symposium on Principles of Database Systems (PODS)
• International Conference on Database Theory (ICDT)
• Leonid Libkin's Database Principles Column of SIGMOD Record