Instituts-Logo Logik in der Informatik
Prof. Dr. Nicole Schweikardt
Humboldt-Logo

Vorlesung Einführung in die Datenbanktheorie

Wintersemester 2018/19

Aktuelles   Einführung    Inhalte    Logbuch    Termine    Übungsblätter    Prüfung    Literatur   Links  


Aktuelles


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

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.

Handout zu den in der Vorlesung verwendeten Folien:

Ein Vorlesungsskript wird es bis auf Weiteres nur in fragmentarischer Form geben:

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

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

Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.


Termine

Vorlesung
Mittwochs 13:15-15:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307 und
Donnerstags 13:15-15:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

Dozentin: Prof. Dr. Nicole Schweikardt

 
Übung
Donnerstags 15:15-17:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

Übungsleiter: André Frochaux


Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt wird jeweils donnerstags in der Übung bzw. am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Mittwoch Nachmittag hier online bereit gestellt.


Prüfung

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

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

  1. Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, die in der Mitte und am Ende der Vorlesungszeit geschrieben werden 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.

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden mittwochs nach der Vorlesung ausgeteilt. Das jeweilige Übungsblatt wird in der Übungsstunde der darauf folgenden Woche 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 am Donnerstag ab.

Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine vom Übungsleiter 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 aus dieser Liste einzelne Teilnehmer 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.


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] Pablo Barcelo's Database Principles Column of SIGMOD Record


Last modified:   06.02.2019
Nicole Schweikardt
Valid HTML 4.01!