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

Einführung in die Datenbanktheorie (WS 20/21)

 


Aktuelles

  • 18.02.21: Heute wurde eine neue Version des Vorlesungsskripts und der Folien hochgeladen (neu: Beweise zu Satz 7.10 und Korollar 7.19).
  • 16.02.21: In jedem der beiden schriftlichen Test können bis zu 100 Punkte erreicht werden. Zum Bestehen eines einzelnen der beiden Tests müssen Sie mindestens 51 Punkte (aus 100 verfügbaren Punkten) erreichen. Um die beiden Tests gemeinsam zu bestehen genügt es, wenn Sie in beiden Tests zusammen in Summe mindestens 102 Punkte erreichen (d.h.: ein etwaiges Nicht-Bestehen von einem der beiden Tests können Sie dadurch ausgleichen, dass Sie in dem anderen der beiden Tests eine entsprechend höhere Punktzahl erreichen).
  • 12.02.21: Heute wurde eine neue Version des Vorlesungsskripts und der Folien hochgeladen.
  • 26.1.21: Unter dem Punkt Prüfung stehen nun Informationen zur Modulabschlussprüfung zur Verfügung.
  • Pandemiebedingt findet die Veranstaltung in diesem Semester in rein digitaler Form statt. Falls Sie an der Veranstaltung teilnehmen wollen, melden Sie sich bitte über AGNES für die Übungen an. Die Eröffnungsvorlesung fand am Dienstag, den 3.11.20 ab 15:15 Uhr statt. Der Übungsbetrieb startete in der zweiten Woche der Vorlesungszeit, also am 11. November.
  • Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird. Ergänzend dazu werden manche Teile der Veranstaltung über die Moodle-Plattform durchgeführt; bitte schreiben Sie sich dort bis 05.11.2020 in den Kurs unter https://moodle.hu-berlin.de/enrol/index.php?id=99908 ein. Der Einschreibeschlüssel wurde an die über AGNES eingeschriebenen Studierenden verschickt (am 02.11.20) und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, danach auch per Mail an Prof. Dr. Nicole Schweikardt erfragt werden.
  • Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 15-17 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird. Das erste solche Online-Treffen fand am Donnerstag, den 05.11.2020 statt; Zugangsdaten erhalten Sie über Moodle.

 


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 und Handout zu den in der Vorlesung verwendeten Folien:

Teile des in der Vorlesung behandelten Stoffs wurden auch in der Vorlesung Logik und Datenbanken behandelt, die ich an Goethe-Universität Frankfurt am Main gehalten habe. Videoaufzeichnungen dieser Vorlesung finden Sie hier.

 


Logbuch

Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 15-17 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird. Das erste solche Online-Treffen findet am Donnerstag, den 05.11.2020 statt. Zugangsdaten erhalten Sie über Moodle.

 


Termine

 

Vorlesung (Online-Treffen, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird)
Dienstag 15:15-17:00 und
Donnerstag 15:15-17:00
über Zoom. Die Eröffnungsvorlesung fand am Dienstag, den 3.11.20 ab 15:15 Uhr statt. Die Zugangsdaten zu den nachfolgenden Online-Treffen ab dem 5.11.20 sind über Moodle erhältlich.

Dozentin: Prof. Dr. Nicole Schweikardt

 
Übung
Mittwoch 09:15-11:00
über Zoom (erstes Treffen am 11.11.20, Zugangsdaten sind über Moodle erhältlich)

Übungsleitung: Prof. Dr. Nicole Schweikardt

 


Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt hier online bereitgestellt. Lösungen zu den Übungsaufgaben sollen vor der nächsten Übungsstunde von allen Teilnehmer*innen erarbeitet werden und dann in der Übungsstunde präsentiert werden.

  • Blatt 1 (bereitgestellt am 9.11.; zu bearbeiten bis 18.11, 9:15 Uhr)
  • Blatt 2 (bereitgestellt am 16.11.; zu bearbeiten bis 25.11, 9:15 Uhr)
  • Blatt 3 (bereitgestellt am 24.11.; zu bearbeiten bis 2.12, 9:15 Uhr)
  • Blatt 4 (bereitgestellt am 01.12.; zu bearbeiten bis 9.12, 9:15 Uhr)
  • Blatt 5 (bereitgestellt am 8.12.; zu bearbeiten bis 6.1., 9:15 Uhr)
  • Blatt 6 (bereitgestellt am 4.1.; zu bearbeiten bis 13.1., 9:15 Uhr)
  • Blatt 7 (bereitgestellt am 12.1.; zu bearbeiten bis 20.1., 9:15 Uhr)
  • Blatt 8 (bereitgestellt am 14.1.; zu bearbeiten bis 27.1., 9:15 Uhr)
  • Blatt 9 (bereitgestellt am 26.1.; zu bearbeiten bis 3.2., 9:15 Uhr)
  • Blatt 10 (bereitgestellt am 2.2.; zu bearbeiten bis 10.2., 9:15 Uhr)
  • Blatt 11 (bereitgestellt am 9.2.; zu bearbeiten bis 17.2., 9:15 Uhr)

 


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 — pandemiebedingt digital über Zoom. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Pergl (oder alternativ bei Frau Kämpfer) angefragt werden: es stehen Prüfungstermine am 11.+12.03.21 und am 13.+14.04.21 zur Verfügung.

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

  • Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, die in der Mitte und am Ende der Vorlesungszeit geschrieben werden: am Mittwoch, den 16.12.20, 9h15-10h45 und am Mittwoch, den 24.02.2021, 9h15-10h45.

Um dies zu erreichen empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden und den Online-Treffen zur Vorlesung teilzunehmen.

 


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