|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
Aktuelles Einführung Inhalte Logbuch Termine Übungsblätter Prüfung Literatur Links
Achtung! Bei Aufgabe 2a vom Blatt 13 ist einiges schief gelaufen! Neue Version ist verfügbar!
Achtung! Die Aufgabe 4 vom Blatt 7 wird auf das Blatt 8 verschoben!
Wir wünschen Ihnen frohe Weihnachten und einen guten Start ins Jahr 2017!
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.
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
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.
Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
Dozentin: Prof. Dr. Nicole Schweikardt
Übungsleiter: André Frochaux
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 in der Übung bzw. am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Dienstag Nachmittag hier online bereit gestellt.
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:
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 Mittwoch
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.
| [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. |