Logik und Datenbanktheorie Prof. Dr. Nicole Schweikardt

Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen. Vorsicht:   Viele wichtige Dinge, die in der Vorlesung an der Tafel erklärt werden (insbesondere Beweise, aber auch einiges Andere), erscheinen nicht unbedingt auf den Folien, sind aber trotzdem für diese Veranstaltung wesentlich und daher auch prüfungsrelevant.

1. Mi, 19.04.2006:
   Einführung ins Thema. Organisatorisches. Kapitel 1: Das Relationale Modell.
   Folien.   Lektüre: Teil A von [AHV]

2. Mo, 24.04.2006:
   Mit Kapitel 2: Konjunktive Anfragen (I) begonnen. Regelbasierte konjunktive Anfragen, Tableau-Anfragen, Anfragen des konjunktiven Kalküls eingeführt und Äquivalenz dieser drei Anfragesprachen gezeigt. Monotonie und Erfüllbarkeit konjunktiver Anfragen betrachtet. Übungsblatt 1 ausgeteilt.
   Folien.   Lektüre: Kapitel 4.1 & 4.2 von [AHV]

3. Mi, 26.04.2006:
   Weiter mit Kapitel 2: Konjunktive Anfragen (I): konjunktive Anfragen mit "=", regelbasierte konjunktive Programme, SPC-Algebra, SPJR-Algebra eingeführt und Äquivalenz dieser Anfragesprachen gezeigt.
   Folien.   Lektüre: Kapitel 4.3 & 4.4 von [AHV]

4. Mi, 03.05.2006:
   Weiter mit Kapitel 2: Konjunktive Anfragen (I): Einfacher Algorithmus zum Auswerten konjunktiver Anfragen. Begriff der "Algorithmen mit Verzögerung f(k,n)" eingeführt und bewiesen, dass die Auswertung (allgemeiner) Anfragen des konjunktiven Kalküls auf die Auswertung von Booleschen Anfragen des konjunktiven Kalküls zurückgeführt werden kann (mit Verzögerung k³.n). Kurze Wiederholung des Begriffs der NP-Vollständigkeit. Übungsblatt 2 ausgeteilt.
   Folien.  

5. Mo, 08.05.2006:
   Die NP-Vollständigkeit des Auswertungsproblems für Boolesche Anfragen des konjunktiven Kalküls bewiesen. Mit Kapitel 3: Relationale Algebra begonnen. Übungsblatt 3 ausgeteilt.
   Folien.
   Lektüre:   Abschnitte 4.5 & 5.1 von [AHV].   Originalarbeit [CM] von Chandra und Merlin: hier.   Einführung [G] in Parametrische Komplexität für Datenbanktheoretiker/innen: hier.

6. Mi, 10.05.2006:
   Weiter mit Kapitel 3: Relationale Algebra: Anfrageauswertung und heuristische Optimierung.
   Folien.  
   Lektüre:   Abschnitt 6.1 von [AHV].   Mehr Details zur Speicherverwaltung und Optimierung finden Sie in den Kapiteln 3–7 von [SH]; siehe http://wwwdb.informatik.uni-rostock.de/biber2/, wo auch Hinweise zur Optimierung in real existierenden Datenbanksystemen zu finden sind.

7. Mo, 15.05.2006:
   Zum Abschluss des Abschnitts über heuristische Optimierung den Begriff des SIP-Graphen bzw. der SIP-Strategie betrachtet.
   Mit Abschnitt 3.3: "Das Semijoin-Fragment der Relationalen Algebra" begonnen. Lineare, sub-quadratische und mindestens quadratische Anfragen betrachtet. Die Algebren RelAlg[R] und SemAlg[R] eingeführt. Gezeigt, dass jede SemAlg[R]-Anfrage linear ist, dass das Auswertungsproblem für SemAlg[R]-Anfragen in Polynomialzeit gelöst werden kann, und dass die Ergebnistupel von SemAlg[R]-Anfragen eine sehr eingeschränkte Form haben. Das Guarded Fragment GF[R] (Teilklasse der Logik erster Stufe) eingeführt. Übungsblatt 4 ausgeteilt.
   Achtung: RAUMÄNDERUNG wegen des Studieninformationstags: Am Mittwoch, 17. Mai findet die Vorlesung in Raum 3.101 (JvN-Haus) und die Übung in Raum 1.306 (ESZ) statt.
   Folien.
   Lektüre:   Abschnitt 6.1 von [AHV].   Originalarbeit [LV] von Leinders und Van den Bussche: hier.

8. Mi, 17.05.2006:
   Beweis, dass die Semijoin-Algebra genau dieselben Anfragefunktionen beschreiben kann wie das Guarded Fragment (eingeschänkt auf Erlaubte-Tupel(I)).
   Zusammenfassung der bisher kennengelernten Methoden zum Nachweis, dass eine Anfragefunktion nicht in der Semijoin-Algebra beschreibbar ist.
   Folien.  
   Lektüre:   Originalarbeit [LV] von Leinders und Van den Bussche: hier.

   Vorsicht:   Fehler auf Blatt 4 in Aufgabe 4:   Für Anfrage (11) ist die Aufgabe nicht lösbar, d.h. die Anfrage kann gar nicht durch eine Formel des Guarded Fragment beschrieben werden.

9. Mo, 22.05.2006:
   Den Begriff der bewachten C-Bisimulation eingeführt und bewiesen, dass Formeln des Guarded Fragment invariant sind unter bewachten C-Bisimulationen (Satz 3.19). Übungsblatt 5 ausgeteilt – Aufgabe 4 dieses Blatts ist "freiwillig".
   Folien.
   Lektüre:   Originalarbeit [LV] von Leinders und Van den Bussche: hier.

10. Mi, 24.05.2006:
    Bisimulations-Methode zum Nachweis, dass bestimmte Anfragefunktionen q nicht in GF[R] ausgedrückt werden können. Ein technisches Lemma bewiesen, das für den Beweis von Theorem 3.10 gebraucht wird.
    Folien.
    Lektüre:   Originalarbeit [LV] von Leinders und Van den Bussche: hier.

11. Mo, 29.05.2006:
    Beweis des Satzes von Leinders und Van den Bussche (Theorem 3.10). Mit Kapitel 4: Relationenkalkül begonnen. Relationenkalkül mit natürlicher Semantik, Relationenkalkül mit Active Domain Semantik und bereichsunabhängigen Relationenkalkül eingeführt. Übungsblatt 6 ausgeteilt.
    Folien.
    Lektüre:   Abschnitt 5.3 von [AHV].   Originalarbeit [LV] von Leinders und Van den Bussche: hier.
    

12. Mi, 31.05.2006:
    Bewiesen, dass die relationale Algebra, der Relationenkalkül mit Active Domain Semantik und der bereichsunabhängige Relationenkalkül dieselbe Ausdrucksstärke haben. Den Satz von Trakhtenbrot zitiert (ohne Beweis) und benutzt, um die Unentscheidbarkeit des bereichsunabhängigen Relationenkalküls zu zeigen. Den "sicheren Relationenkalkül" eingeführt.
    Folien.
    Lektüre:   Abschnitt 5.4 von [AHV].   Zum Satz von Trakhtenbrot siehe Kapitel 1.3.4 des Vorlesungsskripts [KS].

13. Mi, 07.06.2006:
    Gezeigt, dass der sichere Relationenkalkül (a) nur bereichunabhängige Anfragen enthält und (b) dieselbe Ausdrucksstärke wie die relationale Algebra besitzt. Die Unentscheidbarkeit des Erfüllbarkeitsproblems, des Äquivalenzproblems und des Query Containment Problems für relationale Algebra nachgewiesen. Beobachtet, dass die Auswertung (allgemeiner) Anfragen des Relationenkalküls auf die Auswertung von Booleschen Anfragen des Relationenkalküls zurückgeführt werden kann (mit Verzögerung k³.n). Die PSPACE-Vollständigkeit des Auswertungsproblems für Boolesche Anfragen des Relationenkalküls bewiesen. Die Schaltkreis-Komplexitätsklasse AC° eingeführt.
    Folien.
    Lektüre:   Abschnitte 5.4, 6.3 und 17.1 von [AHV].  

14. Mo, 12.06.2006:
    Gezeigt, dass die Datenkomplexität von Booleschen Anfragen der Relationalen Algebra in der Schaltkreis-Komplexitätsklasse AC° liegt. 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. Mit Kapitel 5: Konjunktive Anfragen II begonnen: Kurze Wiederholung des Begriffs der "Tableau-Anfragen". Homomorphismen und kanonische Datenbanken eingeführt und Proposition 5.3 bewiesen. Übungsblatt 7 ausgeteilt.
    Folien.
    Lektüre:   Abschnitte 17.1, 17.2 und 6.2 von [AHV].  

15. Mi, 14.06.2006:
    Den Homomorphismus-Satz und die NP-Vollständigkeit des Query Containment Problems für Tableau-Anfragen bewiesen. Algorithmus zur Tableau-Minimierung. Join-Bäume und azyklische regelbasierte konjunktive Anfragen definiert.
    Folien.
    Lektüre:   Abschnitte 6.2 und 6.4 von [AHV].   Originalarbeit [CM] von Chandra und Merlin: hier.

16. Mo, 19.06.2006:
    Algorithmen zur Konstruktion von Join-Bäumen und zur effizienten Auswertung azyklischer Anfragen entwickelt (Satz von Yannakakis). Äquivalenz zwischen azyklischen Booleschen regelbasierten Anfragen, Booleschen Semijoin-Anfragen und konjunktiven Sätzen des Guarded Fragment bewiesen. Übungsblatt 8 ausgeteilt.
    Folien.
    Lektüre:   Abschnitt 6.4 von [AHV].   Originalarbeit [Y] von Yannakakis: hier.   Überblicksartikel [S] von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen: hier.

17. Mi, 21.06.2006:
    Konjunktive Anfragen mit Multimengen-Semantik betrachtet. Mit Kapitel 6: "Abhängigkeiten und Normalformen" begonnen: Funktionale Abhängigkeiten betrachtet. Korrektheit und Vollständigkeit des Armstrong-Kalküls bewiesen. Übungsblatt 9 ausgeteilt.
    Achtung: Am 26.6. und 28.6. findet keine Vorlesung bzw. Übung statt. Die nächste Vorlesung ist am Montag, den 3.7.
    Folien.
    Lektüre:   Abschnitte 8.1 und 8.2 von [AHV].   Originalarbeit [CV] von Chaudhuri und Vardi: hier.  

18. Mo, 03.07.2006:
    Kurze Bemerkungen zum Armstrong-Kalkül. Start mit Kapitel 6.2: "The Chase — Die Verfolgungsjagd": Beispiel; Definition der FD-Regel; Beweis der Church-Rosser-Eigenschaft der Verfolgungsjagd (Theorem 6.19).
    Folien.
    Lektüre:   Abschnitt 8.4 von [AHV].

19. Mi, 05.07.2006:
    Ende des Beweises der Church-Rosser-Eigenschaft der Verfolgungsjagd (Theorem 6.19). Äquivalenz, Query Containment und Minimierung von Anfragen unter Berücksichtigung einer Menge funktionaler Abhängigkeiten. Start mit Abschnitt 6.3: "Normalformen — Informationstheoretischer Ansatz": Begriff der Zerlegung eines Relationsschemas eingeführt; Methode zum Nachweis der Informationsverlust-Freiheit; Boyce-Codd Normalform (BCNF); Algorithmus zur BCNF-Dekomposition; Beispiel für eine BCNF-Zerlegung, die nicht Abhängigkeits-treu ist. Übungsblatt 10 ausgeteilt.
    Folien.
    Lektüre:   Abschnitte 8.4 und 11.2 von [AHV].

20. Mo, 10.07.2006:
    Dritte Normalform (3NF); Algorithmus zur 3NF-Synthese. Crashkurs zum Thema Informationstheorie: Entropie und Informationsgehalt. Entropie zum Messen der Güte eines Datenbankschemas; Arenas' und Libkins informationstheoretische Charakterisierung der Boyce-Codd Normalform.
    Folien.
    Lektüre:   Abschnitt 11.2 von [AHV].   Originalarbeit [AL] von Arenas und Libkin: hier.  
    Zum Reinhören:   Folien + O-Ton von Leonid Libkins Vortrag beim Workshop Logic and Databases am Isaac Newton Institute in Cambridge, März 2006: hier.

21. Mi, 12.07.2006:
    Rest des Beweises von Arenas' und Libkins informationstheoretischer Charakterisierung der Boyce-Codd Normalform; Anmerkungen zur Wahl eines adäquaten Kriteriums zum Messen des relativen Informationsgehalts. Mit Kapitel 7: "Anfragesprachen mit Rekursion — Datalog" begonnen: Syntax und Semantik von Datalog definiert und den Satz von Knaster und Tarski bewiesen. Übungsblatt 11 ausgeteilt.
    Folien.
    Lektüre:   Abschnitte 12.1–12.3 von [AHV].

22. Mo, 17.07.2006:
    Beweisbasierte Semantik von Datalog. Statische Analyse von Datalog-Programmen: Erfüllbarkeit, Query Containment & uniformes Containment, Boundedness. Effiziente Auswertung von Datalog-Anfragen: Bottom-Up, Top-Down, Magic Sets Methode.
    Folien.
    Lektüre:   Abschnitte 12.4 & 12.5 und Kapitel 13 von [AHV].

23. Mi, 19.07.2006:
    Magic Sets Methode. Nicht-rekursives Datalog. Datalog mit Negation: semipositives Datalog, stratifiziertes Datalog, nicht-rekursives Datalog mit Negation. Kapitel 8: "Zusammenfassung und Ausblick": Rückblick auf die wichtigsten Themenbereiche dieser Vorlesung; Ausblick auf weitere interessante Themen und auf Lehrveranstaltungen in den kommenden Semestern.
    Folien.   Lösung für Aufgabe 2 von Blatt 10:  hier.
    Lektüre:   Abschnitte 13.3, 14.3, 15.1 und 15.2 von [AHV].