Logik und Datenbanken

Vorlesung im WS 2012/13

Gehalten von Prof. Dr. Nicole Schweikardt, Prof. Dr. Isolde Adler
Betreuung der Übungen durch Dipl.-Inf. André Frochaux, Dipl.-Inf. bacc. math. Philipp Klaus Krause

Aktuelles

 Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich 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: 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.

Kürzel laut Studienordnung: M-LD.  Creditpoints: 8.  SWS: 3V, 2Ü.

Inhalte

Logbuch

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

E-Lectures

 Im WS 2012/13 werden Teile der Vorlesungen von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet. Die einzelnen Aufzeichnungen finden Sie hier: Die restlichen Teile der Vorlesung (Kapitel 4, 5 etc.) werden nicht aufgezeichnet.

Termine
ZeitOrtLeitung
Vorlesung Dienstags 14:05-16:50 (Pausen: 14:55-15:00 und 15:50-16:00) Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Prof. Dr. Nicole Schweikardt (bis 11.12.12) , Prof. Dr. Isolde Adler (ab 18.12.12)
Übung 1 Donnerstags 14:15-16:00 Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Dipl.-Inf. André Frochaux (bis 20.12.12) , Dipl.-Inf. bacc. math. Philipp Klaus Krause (ab Januar 2013)

Übungsblätter

Prüfungen bzw. Scheine

Vorsicht:

In der Vorlesung und der Übung werden viele wichtige Dinge (insbesondere Beweise, aber auch einiges andere) an der Tafel erklärt. Diese Dinge sind für die Veranstaltung "Logik und Datenbanken" wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den hier erhältlichen pdf-Dateien der Folien enthalten sind.
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung oder Diplom-Prüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden (mit Folien oder an der Tafel) vermittelte Material durchzuarbeiten.

Modulabschlussprüfung (relevant für Studierende in einem Bachelor- oder Master-Studiengang):

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt.
Generelle Informationen zur Anmeldung zu mündlichen Prüfungen finden Sie hier.

Im Lauf des Semesters können Bonuspunkte erworben werden, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann (also von 4,0 auf 3,7; von 3,7 auf 3,3; von 3,3 auf 3,0; von 3.0 auf 2,7; von 2,7 auf 2,3; von 2,3 auf 2,0; von 2,0 auf 1,7; von 1,7 auf 1,3; von 1,3 auf 1,0).

In der Übungsstunde am 13.12.2012 und in der Übungsstunde am 14.02.2012 wird ein 90-minütiger Test geschrieben.
Voraussetzung für den Erwerb von Bonuspunkten, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann, sind:

  1. Bestehen der beiden Tests,
  2. regelmäßige aktive Teilnahme an den Übungen und
  3. Erreichen von mindestens 50 Prozent aller Übungspunkte.

Scheinerwerb (relevant für Studierende in einem Diplom- oder Lehramts-Studiengang):

In der Übungsstunde am 13.12.2012 und in der Übungsstunde am 14.02.2012 wird ein 90-minütiger Test geschrieben.
Voraussetzung für den Scheinerwerb sind:
  1. Bestehen der beiden Tests,
  2. regelmäßige aktive Teilnahme an den Übungen und
  3. Erreichen von mindestens 50 Prozent aller Übungspunkte.

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Am Donnerstag der darauf folgenden Woche wird das jeweilige Übungsblatt in der Übungsstunde besprochen. Zu Beginn dieser Übungsstunde können alle Teilnehmer in eine Liste eintragen, für welche Aufgaben(teile) sie wie viele Übungspunkte angerechnet bekommen wollen. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste willkürlich einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass ein Teilnehmer keine sinnvolle Lösung vorweisen kann, obwohl er in der Liste Übungspunkte für diese Aufgabe beansprucht hat, geschieht folgendes:
  1. Tritt diese Situation für den jeweiligen Teilnehmer zum ersten Mal in diesem Semester auf, so werden ihm für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet.
  2. Tritt diese Sitation für den jeweiligen Teilnehmer zum zweiten Mal in diesem Semester auf, so kann er in der Veranstaltung "Logik und Datenbanken" im WS 2012/13 keine Übungspunkte erwerben.

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.
Frontmatter | Table of Contents | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | Bibliography | Index
[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.
[SH] G. Saake und A. Heuer.Datenbanken: Implementierungstechniken. International Thomson Publishing, 800 Seiten, Mai 1999.
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004.
[LV] D. Leinders and 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.
[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. 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
[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
[DBVerstehen] Eine Webseite zum Thema "Datenbanken verstehen"
zuletzt geändert: Tue Feb 12 18:56:20 2013 von Lucas Heimberg