Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Die Eröffnungsvorlesung fand am Mittwoch, den 14.10.2015 statt.
• Die ersten Übungsstunden fanden in der zweiten Semesterwoche statt, also in der Woche vom 19.-23.10.2015
• 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: 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.

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

• Folien - komplett - (Version vom 10. Februar 2016)
• Skript-Fragmente (Version vom 10. Februar 2016)

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.

Logbuch

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

Termine

Vorlesung

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

Dozentin: Prof. Dr. Nicole Schweikardt

 

Übungen

Gruppe 1:   Mittwochs 13:15-15:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303
Gruppe 2:   Donnerstags 11:15-13:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303

Übungsleiter: André Frochaux

Melden Sie sich bitte bis 22.10.2015 mittels GOYA für den von Ihnen bevorzugten Übungstermin an.

Ü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 mittwochs am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Mittwoch Nachmittag hier online bereit gestellt.

• Blatt 1 (ausgeteilt am 21.10.; zu bearbeiten bis 28.10, 13:30)
• Blatt 2 (ausgeteilt am 28.10.; zu bearbeiten bis 4.11, 13:30)
• Blatt 3 (ausgeteilt am 4.11.; zu bearbeiten bis 11.11, 13:30)
• Blatt 4 (ausgeteilt am 11.11.; zu bearbeiten bis 18.11, 13:30)
• Blatt 5 (ausgeteilt am 18.11.; zu bearbeiten bis 25.11, 13:30)
• Blatt 6 (ausgeteilt am 25.11.; zu bearbeiten bis 2.12, 13:30)
• Blatt 7 (ausgeteilt am 9.12.; zu bearbeiten bis 16.12, 13:30)
• Blatt 8 (ausgeteilt am 16.12.; zu bearbeiten bis 6.1, 13:30)
• Blatt 9 (ausgeteilt am 6.1.; zu bearbeiten bis 13.1, 13:30)
• Blatt 10 (ausgeteilt am 13.1.; zu bearbeiten bis 20.1, 13:30)
• Blatt 11 (ausgeteilt am 20.1.; zu bearbeiten bis 27.1, 13:30)
• Blatt 12 (ausgeteilt am 27.1.; zu bearbeiten bis 3.2, 13:30)
• Blatt 13 (ausgeteilt am 3.2; zu bearbeiten bis 10.2, 13:30)

Prüfung

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

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können kurz vor Ende der Vorlesungszeit bei Frau Sandig angefragt werden.

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

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