Aktueller Eintrag

Logbuch: Logik und Datenbanken

Vorlesung  im WS 2012/13

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

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.


  1. Di, 16.10.2012
  2. Kapitel 0: Einführung ins Thema; Organisatorisches. Kapitel 1: Das Relationale Modell.
    Material:
    Folien zu Kapitel 0; Folien zu Kapitel 1
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Weitere Lektüre:
    Teil A von [AHV].
  3. Di, 23.10.2012
  4. Beginn mit Kapitel 2: Konjunktive Anfragen. Heute Abschnitt 2.1 "Deskriptiver Ansatz: regelbasiert, graphisch und logikbasiert" behandelt (bis inkl. Folie "Kapitel 2, Seite 24"): Syntax und Semantik regelbasierter konjunktiver Anfragen; Monotonie und Erfüllbarkeit regelbasierter konjunktiver Anfragen; Tableau-Anfragen; konjunktiver Kalkül; Äquivalenz der Ausdrucksstärke von Tableau-Anfragen, konjunktivem Kalkül und regelbasierten konjunktiven Anfragen.
    Material:
    Folien zu Kapitel 2
    Übungsblatt 1
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - Teil 1: Deskriptiver Ansatz: regelbasiert, graphisch und logikbasiert [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 23.10.2012)
    Weitere Lektüre:
    Kapitel 4.1 und 4.2 von [AHV].
  5. Di, 30.10.2012
  6. Weiter mit Kapitel 2: Konjunktive Anfragen. Heute Abschnitt 2.2 "Auswertungskomplexität" behandelt (bis inkl. Folie "Kapitel 2, Seite 41"): Bereichsbeschränkte konjunktive Anfragen mit "="; regelbasierte konjunktive Programme; Auswertungskomplexität konjunktiver Anfragen
    Material:
    Folien zu Kapitel 2
    Übungsblatt 2
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - 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.)
    Weitere Lektüre:
    Kapitel 4.3 von [AHV].
    Originalarbeit [CM] von Chandra und Merlin: hier; Einführung [G] in die Parametrische Komplexität für Datenbanktheoretiker/innen: hier.
  7. Di, 06.11.2012
  8. Weiter mit Kapitel 2: Konjunktive Anfragen. Heute Abschitt 2.3 "Algebraischer Ansatz: SPC-Algebra und SPJR-Algebra" behandelt (bis inkl. Folie "Kapitel 2, Seite 61"): SPC-Algebra; SPJR-Algebra; die Äquivalenz von SPC-Algebra, SPJR-Algebra, Tableau-Anfragen, regelbasierten konjunktiven Anfragen und Anfragen des konjunktiven Kalküls
    Material:
    Folien zu Kapitel 2
    Übungsblatt 3
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - Teil 3: Algebraischer Ansatz: SPC-Algebra und SPJR-Algebra [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 06.11.2012)
    Weitere Lektüre:
    Kapitel 4.4 und 4.5 von [AHV].
  9. Di, 13.11.2012
  10. Weiter mit Kapitel 2: Konjunktive Anfragen. Heute Abschnitt 2.4: "Homomorphismus-Satz, statische Analyse und Anfrageminimierung" behandelt (bis inkl. Folie "Kapitel 2, Seite 72"): Kurze Wiederholung des Begriffs der Tableau-Anfragen. Die Begriffe Substitution und Homomorphismus eingeführt. Kanonische Datenbanken eingeführt, den Homomorphismus-Satz bewiesen, die NP-Vollständigkeit des Query Containment Problems für Tableau-Anfragen bewiesen. Einen Algorithmus zur Tableau-Minimierung kennen gelernt.
    Material:
    Folien zu Kapitel 2
    Übungsblatt 4
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - Teil 4: Homomorphismus-Satz, statische Analyse und Anfrageminimierung [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 13.11.2012)
    Weitere Lektüre:
    Kapitel 6.2-6.4 von [AHV]. Originalarbeit [CM] von Chandra und Merlin: hier.
  11. Di, 20.11.2012
  12. Weiter mit Kapitel 2: Konjunktive Anfragen. Heute Abschnitt 2.4: "Homomorphismus-Satz, statische Analyse und Anfrageminimierung" abgeschlossen und Abschnitt 2.5: "Azyklische Anfragen" begonnen (bis inkl. Folie "Kapitel 2, Seite 81"): Die Korrektheit des Algorithmus zur Tableau-Minimierung bewiesen; ein Beispiel zur verbesserten Optimierung von SPJR-Anfragen mittels Tableau-Minimierung betrachtet; Motivation und einführende Beispiele zum Thema "azyklische Anfragen"; Join-Bäume und azyklische regelbasierte konjunktive Anfragen definiert; die Klasse der Semijoin-Anfragen definiert; ein Polynomialzeit-Algorithmus (bzgl. kominierter Komplexität) zur Auswertung von Semijoin-Anfragen; die Äquivalenz von Booleschen Semijoin-Anfragen und azyklischen regelbasierten Booleschen Anfragen.
    Material:
    Folien zu Kapitel 2
    Übungsblatt 5
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - Teil 5: Anfrageminimierung und Azyklische Anfragen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 20.11.2012)
    Weitere Lektüre:
    Kapitel 6.2 und 6.4 von [AHV]. Die Originalarbeit [CM] von Chandra und Merlin finden Sie hier.
  13. Di, 27.11.2012
  14. Abschluss von Kapitel 2: Konjunktive Anfragen. Heute Abschnitt 2.5: "Azyklische Anfragen" abgeschlossen und Abschnitt 2.6: "Mengen-Semantik vs. Multimengen-Semantik" behandelt (bis inkl. Folie "Kapitel 2, Seite 97"): Ein Algorithmus zum Test auf Azyklizität und zum Erzeugen von Join-Bäumen; der Satz von Yannakakis, der besagt, dass das Auswertungsproblem für azyklische konjunktive Anfragen in Polynomialzeit (bzgl. kombinierter Komplexität) gelöst werden kann; das "konjunktive Guarded Fragment" GF(CQ) eingeführt und gezeigt, dass mit Sätzen von GF(CQ) genau dieselben Booleschen Anfragen beschrieben werden können wie mit Booleschen Semijoin-Anfragen bzw. mit azyklischen Booleschen regelbasierten Anfragen. Kurzer Überblick über die Multimengen-Semantik konjunktiver Anfragen.
    Material:
    Folien zu Kapitel 2
    Übungsblatt 6
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 2: Konjunktive Anfragen - Teil 6: Azyklische Anfragen und Multimengen-Semantik [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 27.11.2012)
    Weitere Lektüre:
    Kapitel 6.2 und 6.4 von [AHV]. Die Originalarbeit von Yannakakis finden Sie hier. Einen Überblicksartikel von Scarcello [Sca] zu Verallgemeinerungen des Begriffs der azyklischen Anfragen finden Sie hier.
  15. Di, 04.12.2012
  16. Beginn mit Kapitel 3: "Anfragesprachen mit Rekursion - Datalog": Heute Abschnitt 3.1: "Syntax und Semantik" behandelt und Abschnitt 3.2: "Statische Analyse" begonnen (bis inkl. Folie "Kapitel 3, Seite 24"): Syntax und Semantik (Fixpunkt-Semantik, Modellbasierte Semantik, Beweisbasierte Semantik), der Satz von Knaster und Tarski, Monotonie von Datalog-Anfragen, Entscheidbarkeit des Erfüllbarkeitsproblems für Datalog, Unentscheidbarkeit des Query-Containment-Problems für Datalog.
    Material:
    Folien zu Kapitel 3
    Heute wurde kein Übungsblatt ausgeteilt. Das nächste Übungsblatt gibt es am 11.12.2012.
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • 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.)
    Weitere Lektüre:
    Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov.
  17. Di, 11.12.2012
  18. Abschluss von Kapitel 3: "Anfragesprachen mit Rekursion - Datalog": Heute Abschnitt 3.2: "Statische Analyse" und Abschnitt 3.3: "Einschränkungen und Erweiterungen: nr-Datalog und Datalog mit Negation" behandelt (Folien "Kapitel 3, Seiten 24-39 und 47"): Erwähnung der Entscheidbarkeit des uniformen Containment Problems für Datalog-Programme (ohne Beweis); Beschränktheit (engl.: boundedness) von Datalog-Programmen; nicht-rekursives Datalog und die Äquivalenz der Ausdrucksstärke von nr-Datalog, SPCU-Algebra und positiv existentiellem Kalkül; Diskussion möglicher Erweiterungen von Datalog um "Negationen"; nicht-rekursives Datalog mit Negationen betrachtet (als Ausblick auf Kapitel 4 und 5) erwähnt, dass dies dieselbe Ausdrucksstärke wie die relationale Algebra bzw der Relationenkalkül hat.
    Material:
    Folien zu Kapitel 3
    Übungsblatt 7
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Kapitel 3: Anfragesprachen mit Rekursion - Datalog - Teil 2: Statische Analyse von Datalog, nicht-rekursives Datalog und nicht-rekursives Datalog mit Negation [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 11.12.2012)
    Weitere Lektüre:
    Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov.
  19. Di, 18.12.2012
  20. Kapitel 4: Relationale Algebra (bis inkl. Folie "Kapitel 4, Seite 30"): Syntax und Semantik der relationalen Algebra; Beispiele für Anfragen der relationalen Algebra; Vergleich der Ausdrucksstärke von SPC-Algebra, SPCU-Algebra und relationaler Algebra; (Nicht-)Redundanz einzelner Operatoren der relationalen Algebra; Theta-Joins und Semijoins; Anfrageauswertung und heuristische Optimierung
    Material:
    Folien zu Kapitel 4
    Übungsblatt 8
    Weitere Lektüre:
    Kapitel 5.1 und 6.1 von [AHV], sowie Kapitel 1 und 2 aus [SH] .
  21. Di, 15.01.2013
  22. Kapitel 4 zuende: SIP-Strategien. Beginn mit Kapitel 5: Relationenkalkül (bis inkl. Folie "Kapitel 5, Seite 15, Beweis von Satz 5.9"): Relationenkalkül mit natürlicher Semantik, Relationenkalkül mit Active Domain Semantik und bereichsunabhängigen Relationenkalkül eingeführt und an Beispielen illustriert; bewiesen, dass die relationale Algebra, der Relationenkalkül mit Active Domain Semantik und der bereichsunabhängige Relationenkalkül dieselbe Ausdrucksstärke haben.
    Material:
    Folien zu Kapitel 4
    Folien zu Kapitel 5
    Übungsblatt 9
    Weitere Lektüre:
    Die in der Vorlesung erwähnte Arbeit von Grohe finden Sie hier.
    Kapitel 5.3 von [AHV].
  23. Di, 22.01.2013
  24. Weiter mit Kapitel 5: Relationenkalkül (bis inkl. Folie "Kapitel 5, Seite 20"): Beweis vn Satz 5.9 zuende, Satz 5:10: Äquivalenz von nicht-rekursivem Datalog mit Negation und relationaler Algebra: eine Richtung bewiesen. Den Satz von Trakhtenbrot zitiert und benutzt, um zu beweisen, dass es keinen Algorithmus gibt, der bei Eingabe einer Anfrage des Relationenkalküls entscheidet, ob die Anfrage bereichsunabhängig ist.
    Material:
    Folien zu Kapitel 5
    Übungsblatt 10
    Weitere Lektüre:
    Kapitel 6.3 von [AHV]. Zum Satz von Trakhtenbrot siehe Kapitel 9.1 von [L] .
  25. Di, 29.01.2013
  26. Weiter mit Kapitel 5: Relationenkalkül (bis inkl. Folie "Kapitel 5, Seite 34"): Den sicheren Relationenkalkül eingeführt, an Beispielen illustriert, und bewiesen, dass der sichere Relationenkalkül bereichsunabhängig ist und genau dieselben Anfragefunktionen wie der bereichsunabhängige Relationenkalkül ausdrücken kann. Die Unentscheidbarkeit der statischen Analyse für relational vollständige Anfragesprachen nachgewiesen.
    Material:
    Folien zu Kapitel 5
    Übungsblatt 11
    Weitere Lektüre:
    Kapitel 5.4 und 6.3 von [AHV].
  27. Di, 05.02.2013
  28. Beweis des Satzes von Chandra und Merlin, der besagt, dass das Auswertungsproblem für Boolesche Anfragen des Relationenkalküls PSPACE-vollständig ist (bzgl. der kombinierten Komplexität). Die Gaifman-Lokalität des Relationenkalküls eingeführt (ohne Beweis) und benutzt, um zu zeigen, dass die Erreichbarkeits-Anfrage nicht im Relationenkalkül ausgedrückt werden kann.
    Beginn mit Kapitel 6 Anfragen beschränkter Hyperbauweite. Anfrage-Hypergraphen Boolescher, regelbasierter konjunktiver Anfragen eingeführt, Anfrage-Hypergraphen für Beispiel-Anfragen aus Kapitel 2, das (monotone) Räuber-und-Gendarmen-Spiel eingeführt und an den Beispielen illustriert. Bis Beispiel 6.7.
    Weitere Lektüre:
    Kapitel 5.1 und 6.1 von [AHV].
  29. Di, 12.02.2013
  30. Kapitel 6 Anfragen beschränkter Hyperbauweite zuende: Gewinnstrategien für die Gendarmen eingeführt, (monotone) Gendarmen-Zahl definiert und an Beispielen illustriert. Hyperbaumweite eingeführt, am Beispiel illustriert, und den Satz, dass die Hyperbauweite gleich der monotonen Gendarmenzahl ist ohne Beweis angegeben. Satz: Boolesche regelbasierte konjunktive Anfragen beschränkter Hyperbaumweite lassen sich in Polynoialzeit auswerten (kombinierte Koplexität) mit Beweisskizze.