Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Einführung in die Datenbanktheorie

 

 

 

Aktuelles

  • 24.1.24: Beachten Sie: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung und zur Prüfungsanmeldung, die insbesondere bereits begonnen hat.
  • 16.1.24: Krankheitsbedingt wird auch die Übung am Mittwoch, den 17.1.24, und die Vorlesung am Donnerstag, den 18.1.24, leider nicht stattfinden.
  • 15.1.24: Krankheitsbedingt wird die Vorlesung am Dienstag, den 16.1.24, leider nicht stattfinden.
  • 07.12.23: leicht modifizierte Version von Blatt 7 bereitgestellt (die erste Zeile von Aufgabe 3 wurde etwas anders formuliert)
  • 23.11.23: neue Version des Skripts hochgeladen.
  • 15.11.23: Krankheitsbedingt fand die Vorlesung am Donnerstag, den 16.11.23, nicht statt.
  • 15.11.23: Krankheitsbedingt haben sich beide Übungsgruppen am Mittwoch, den 15.11.23 in Raum 1'306 getroffen.
  • 30.10.23: Termine für die beiden Tests bekannt gegeben.
  • 30.10.23: neue Version des Skripts hochgeladen.
  • Die Eröffnungsvorlesung fand am Dienstag, den 17.10.2023 statt.
  • Die ersten Übungsstunden fanden am 25.10.2023 statt.
  • Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird.
  • Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 

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: 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.

Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Bachelorstudiengang oder Studierende eines Masterstudiengangs, die an der Schnittstelle zwischen Theorie und Praxis interessiert sind. Voraussetzung für die Teilnahme sind Kenntnisse, die in der Vorlesung "Logik in der Informatik" vermittelt werden, sowie Kenntnisse über die Grundlagen von Datenbanksystemen.

 

Inhalte

  • Kapitel 1: Einleitung
  • Kapitel 2: Das Relationale Modell
  • Kapitel 3: Konjunktive Anfragen
  • Kapitel 4: Datalog
  • Kapitel 5: Funktionale Abhängigkeiten
  • Kapitel 6: Relationale Algebra
  • Kapitel 7: Relationenkalkül
  • Kapitel 8: Zusammenfassung und Ausblick

 

Vorlesungsskript (Version vom 23. November 2023)

 

Beachten Sie:
In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten oder in Moodle erhältlichen Materialien enthalten sind. Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

 

 

 

Logbuch

Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 

Termine

 

Vorlesung
Dienstag 15:00-17:00, ESZ (RUD26), Raum 1'306 und
Donnerstag 15:00-17:00, ESZ (RUD26), Raum 1'306
Übungen:
Gruppe 1: Mittwoch 15:00-17:00, ESZ (RUD26), Raum1'303
Gruppe 2: Mittwoch 15:00-17:00, ESZ (RUD26), Raum1'306

Dozent:in:

Dr. André Frochaux und Prof. Dr. Nicole Schweikardt

 

Übungsblätter

 

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Übungsaufgaben besprochen werden. Die Übungsgruppen treffen sich erstmalig in der zweiten Woche der Vorlesungszeit, also am 25.10.23.

Ab der zweiten Vorlesungswoche wird i.d.R. wöchentlich (jeden Mittwoch) ein Übungsblatt bereitgestellt. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

 

  • Blatt 1 (bereitgestellt am 24.10.; zu bearbeiten bis 01.11., 15:00 Uhr)
  • Blatt 2 (bereitgestellt am 30.10.; zu bearbeiten bis 08.11., 15:00 Uhr)
  • Blatt 3 (bereitgestellt am 6.11.; zu bearbeiten bis 15.11., 15:00 Uhr)
  • Blatt 4 (bereitgestellt am 13.11.; zu bearbeiten bis 22.11., 15:00 Uhr)
  • Blatt 5 (bereitgestellt am 21.11.; zu bearbeiten bis 29.11., 15:00 Uhr)
  • Blatt 6 (bereitgestellt am 28.11.; zu bearbeiten bis 06.12., 15:00 Uhr)
  • Blatt 7 (bereitgestellt am 05.12. und modifiziert am 07.12.; zu bearbeiten bis 20.12., 15:00 Uhr)
  • Blatt 8 (bereitgestellt am 20.12.; zu bearbeiten bis 10.01., 15:00 Uhr)
  • Blatt 9 (bereitgestellt am 10.1.; zu bearbeiten bis 24.01., 15:00 Uhr)
  • Blatt 10 (bereitgestellt am 24.1.; zu bearbeiten bis 31.01., 15:00 Uhr)
  • Blatt 11 (bereitgestellt am 31.1.; zu bearbeiten bis 07.02., 15:00 Uhr)

 

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten

Übungsblätter werden mittwochs online zur Verfügung gestellt und in der darauf folgenden Woche mittwochs in der Übungsstunde besprochen. Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde im Moodle-Kurs ab.

Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung vom Übungsleiter bzw. der Übungsleiterin bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden vom Übungsleiter bzw. der Übungsleiterin aus dieser Liste einzelne Studierende zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein.

 

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden behandelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen.

Auf der Webseite des Prüfungsbüros finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Prüfungsterminen und Anmeldefristen) und Hinweise zur Prüfungsan- und -abmeldung. Die Prüfungen im Modul "Einführung in die Datenbanktheorie" finden im Februar 2024 (12., 13., 14.2.24) und April 2024 (9., 10.04.24) statt; Die Prüfungen für dieses Modul finden in Raum 3.408 statt.

Hinweise zur Prüfungsanmeldung:
  1. Die Modulabschlussprüfung (kurz: MAP) wird als mündliche Prüfung durchgeführt. Dafür müssen Sie sich in AGNES anmelden – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 28. Januar 2024! Direkt anschließend an Ihre Anmeldung in AGNES müssen Sie einen konkreten Prüfungstermin über den Lehrstuhl vereinbaren (senden Sie eine Email an Dr. André Frochaux und Prof. Nicole Schweikardt ). Nennen Sie dabei bitte Ihren Namen, Matrikelnummer und das Modul ("Einführung in die Datenbanktheorie") und bitten Sie darum, einen konkreten Prüfungstermin (Tag und Uhrzeit) zugeteilt zu bekommen. Wichtig: zur ordnungsgemäßen Anmeldung zur MAP ist beides nötig: fristgerechte Anmeldung in AGNES und Vereinbarung eines konkreten Prüfungstermins.
  2. In AGNES melden Sie sich zwar für den Montag, den 12.2.24 an, der Termin kann aber an einem beliebigen Tag innerhalb des Prüfungszeitraumes 12.-14.02.24 liegen und wird Ihnen vom Lehrstuhl zugeteilt.
  3. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur MAP zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum Ende des Semesters nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen). Umgekehrt ist der 28. Januar 2024 eine harte Frist: Danach ist keine Anmeldung mehr möglich!
  4. Die Frist zum Rücktritt von der Prüfung entnehmen Sie der Webseite des Prüfungsbüros. Sollten Sie vor Ablauf der Frist zurücktreten wollen, AGNES Ihnen den Rücktritt jedoch nicht mehr ermöglichen (bspw. weil in AGNES der "Tag X" als Prüfungsdatum steht, Ihre Prüfung jedoch erst am "Tag X+1" stattfindet), melden sie sich per Mail an das Prüfungsbüro (mit Prof. Schweikardt und A. Frochaux im CC) von der Prüfung ab.

 

Voraussetzung für die Zulassung zur Prüfung ist:

  1. Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, die in der Mitte und am Ende der Vorlesungszeit geschrieben werden, und zwar
    • am Mittwoch, den 13.12.23, 15h15-16h45 (während der Übungsstunde) und
    • am Mittwoch, den 31.01.24, 15h15-16h45 (während der Übungsstunde)
    und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die oben angegebenen "Spielregeln" zum Erwerb von Übungspunkten.

 

Literatur

 

[AHV] S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
A pdf-version of the book is available here.
[WebDaM] S. Abiteboul, I. Manolescu, P. Rigaux, M.-C. Rousset, P. Senellart. Web Data Management. Cambridge Univ. Press, 2011.
A pdf-Version of the book is available here.
[PoD] Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Wim Martens, Andreas Pieris. Principles of Databases.. Book (in progress), 2022.
A (Preliminary) pdf-Version of the book is available here.
[M] D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.
A pdf-Version of the book is available here.
[SSS] N. Schweikardt, T. Schwentick, L. Segoufin. Database Theory: Query Languages. Chapter 19 in Algorithms and Theory of Computation Handbook, 2nd edition, volume 2: Special Topics and Techniques. Mikhail J. Atallah and Marina Blanton (editors), CRC Press, 2009.
[AD] P. Atzeni, V. De Antonellis. Relational Database Theory. Addison Wesley Longman; 1st edition (January 1993).
[CM] A. K. Chandra und P.M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases. Proceedings of the 9th Annual ACM Symposiom on Theory of Computer Science (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.
[Y] M. Yannakakis. Algorithms for acyclic database schemes. 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 and 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.
[Datalog] E. Dantsin, T. Eiter, G. Gottlob and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, Vol. 33, No. 3, pages 374-425. 2001.
[P] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004.

 

[databasetheory.org] Principles of Data Management — databasetheory.org
[PODS] ACM Symposium on Principles of Database Systems (PODS)
[ICDT] International Conference on Database Theory (ICDT)
[SIGRec] Database Principles Column of SIGMOD Record