Logik und Datenbanken

Vorlesung

• Logik und Datenbanken im WS 2012/13
• Logik und Datenbanken im SoSe 2010
• Logik und Datenbanken im SoSe 2008

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

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:

• Kapitel 0: Einführung ins Thema; Organisatorisches [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.10.2012)
• Kapitel 1: Das relationale Modell [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.10.2012)
• Kapitel 2: Konjunktive Anfragen
  • Teil 1: Deskriptiver Ansatz: regelbasiert, graphisch und logikbasiert [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 23.10.2012)
  • Teil 2: Konjunktive Anfragen mit "="; konjunktive Programme; Auswertungskomplexität konjunktiver Anfragen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 30.10.2012 - Aufgrund technischer Probleme wurden leider nur die ersten 30 (von insgesamt ca. 150) Minuten der Vorlesung aufgezeichnet.)
  • Teil 3: Algebraischer Ansatz: SPC-Algebra und SPJR-Algebra [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 06.11.2012)
    
  • Teil 4: Homomorphismus-Satz, statische Analyse und Anfrageminimierung [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 13.11.2012)
    
  • Teil 5: Anfrageminimierung und Azyklische Anfragen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 20.11.2012)
  • Teil 6: Azyklische Anfragen und Multimengen-Semantik [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 27.11.2012)
• Kapitel 3: Anfragesprachen mit Rekursion - Datalog
  • Teil 1: Syntax und Semantik sowie statische Analyse von Datalog [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 04.12.2012 - Aufgrund technischer Probleme wurde die ersten 15 Minuten der Vorlesung leider nicht aufgezeichnet.)
  • Teil 2: Statische Analyse von Datalog, nicht-rekursives Datalog und nicht-rekursives Datalog mit Negation [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 11.12.2012)

Die restlichen Teile der Vorlesung (Kapitel 4, 5 etc.) werden nicht aufgezeichnet.

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"