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.

Di, 13.04.2010
Kapitel 0: Einführung ins Thema; Organisatorisches.
Kapitel 1: Das Relationale Modell.
Beginn mit Kapitel 2: Konjunktive Anfragen (I) (bis inkl. Folie "Kapitel 2, Seite 9"): regelbasierte konjunktive Anfragen
Weitere Lektüre:
Teil A und Kapitel 4.1 und 4.2 von .
Di, 20.04.2010
Weiter mit Kapitel 2: Konjunktive Anfragen (I) (bis inkl. Folie "Kapitel 2, Seite 31"): Monotonie und Erfüllbarkeit regelbasierter konjunktiver Anfragen; Tableau-Anfragen; konjunktiver Kalkül; bereichsbeschränkte konjunktive Anfragen mit "="; regelbasierte konjunktive Programme
Weitere Lektüre:
Kapitel 4.1 bis 4.3 von .
Di, 27.04.2010
Weiter mit Kapitel 2: Konjunktive Anfragen (I) (bis inkl. Folie "Kapitel 2, Seite 40"): Auswertungskomplexität konjunktiver Anfragen
Weitere Lektüre:
Originalarbeit von Chandra und Merlin: hier; Einführung in die Parametrische Komplexität für Datenbanktheoretiker/innen: hier.
Di, 04.05.2010
Abschluss von Kapitel 2: Konjunktive Anfragen (I) (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
Weitere Lektüre:
Kapitel 4.4 und 4.5 von .
Di, 11.05.2010
Kapitel 3: Relationale Algebra (bis inkl. Folie "Kapitel 3, Seite 36"): 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; SIP-Strategien
Weitere Lektüre:
Kapitel 5.1 und 6.1 von .
Di, 18.05.2010
Beginn mit Kapitel 4: Relationenkalkül (bis inkl. Folie "Kapitel 4, Seite 16"): 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.
Weitere Lektüre:
Kapitel 5.3 von .
Di, 25.05.2010
Weiter mit Kapitel 4: Relationenkalkül (bis inkl. Folie "Kapitel 4, Seite 18"): 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. Außerdem: zusätzliche Übungsstunde.
Weitere Lektüre:
Kapitel 6.3 von . Zum Satz von Trakhtenbrot siehe Kapitel 9.1 von .
Di, 01.06.2010
Weiter mit Kapitel 4: Relationenkalkül (bis inkl. Folie "Kapitel 4, 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. Beginn des Beweises 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).
Weitere Lektüre:
Kapitel 5.4 und 6.3 von .
Di, 08.06.2010
Abschluss von Kapitel 4: Relationenkalkül (bis inkl. Folie "Kapitel 4, Seite 42"): Abschluss des Beweises 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 Komplexitätsklasse AC° und die Datenkomplexität des Auswertungsproblems des Relationenkalküls betrachtet. 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 5: Konjunktive Anfragen (II) (bis inkl. Folie "Kapitel 5, Seite 8"): Kurze Wiederholung des Begriffs der Tableau-Anfragen. Die Begriffe Substitution und Homomorphismus eingeführt.
Weitere Lektüre:
Kapitel 17.1 und 17.2 sowie Kapitel 6.2 und 6.3 von .
Di, 15.06.2010
Weiter mit Kapitel 5: Konjunktive Anfragen (II) (bis inkl. Folie "Kapitel 5, Seite 19"): 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, ein Beispiel zur verbesserten Optimierung von SPJR-Anfragen mittels Tableau-Minimierung betrachtet. Beginn mit Abschnitt 5.2: Azyklische Anfragen: Motivation und einführende Beispiele, Join-Bäume und azyklische regelbasierte konjunktive Anfragen definiert, die Klasse der Semijoin-Anfragen definiert.
Weitere Lektüre:
Kapitel 6.2 und 6.4 von . Die Originalarbeit von Chandra und Merlin finden Sie hier.
Di, 29.06.2010
Weiter mit Kapitel 5: Konjunktive Anfragen (II) (bis inkl. Folie "Kapitel 5, Seite 24"): ein Polynomialzeit-Algorithmus (bzgl. kominierter Komplexität) zur Auswertung von Semijoin-Anfragen; die Äquivalenz von Booleschen Semijoin-Anfragen und azyklischen regelbasierten Booleschen Anfragen; ein Polynomialzeit-Algorithmus zum Erzeugen eines Join-Baums bzw. zum Erkennen, dass eine gegebene Anfrage nicht azyklisch ist.
Weitere Lektüre:
Kapitel 6.2 und 6.4 von . Einen Überblicksartikel von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen finden Sie hier.
Do, 01.07.2010
Abschluss von Kapitel 5: Konjunktive Anfragen (II) (bis inkl. Folie "Kapitel 5, Seite 37"): 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 Multimengensemantik konjunktiver Anfragen.
Beginn mit Kapitel 6: Abhängigkeiten und Normalformen (bis inkl. Folie "Kapitel 6, Seite 18"): Funktionale Abhängigkeiten, verlustfreie Joins, FD-Regel, Verfolgungssequenzen, die Church-Rosser-Eigenschaft, chase(T,t,Σ).
Weitere Lektüre:
Kapitel 6.2 und 6.4 von . Die Originalarbeit von Yannakakis finden Sie hier. Einen Überblicksartikel von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen finden Sie hier.
Di, 06.07.2010
Weiter mit Kapitel 6: Abhängigkeiten und Normalformen (bis inkl. Folie "Kapitel 6, Seite 43"): Ein Polynomialzeit-Algorithmus, der chase(T,t,Σ) berechnet (die so genannte "Chase-Prozedur"). Entscheidbarkeit von Äquivalenz und Query Containment konjunktiver Anfragen bzgl. einer Menge von FDs. Minimierung konjunktiver Anfragen unter Berücksichtigung von FDs. Ein Algorithmus zum Testen, ob eine FD f aus einer gegebenen Menge von FDs folgt. Zerlegungen von Relationsschemata, informationsverlustfreiheit und abhängigkeitstreue. Boyce-Codd Normalform (BCNF). Ein Algorithmus zur BCNF-Dekomposition eines gegebenen Relationsschemas. Crashkurs in Informationstheorie: Die Begriffe Entropie und Informationsgehalt.
Weitere Lektüre:
Kapitel 8.1, 8.2, 8.4 und 11.2 von .
Do, 08.07.2010
Abschluss von Kapitel 6: Abhängigkeiten und Normalformen (bis inkl. Folie "Kapitel 6, Seite 52"): Entropie zum Messen der Güte eines Datenbankschemas; Arenas' und Libkins informationstheoretische Charakterisierung der BCNF.
Kurzer Ausblick auf Kapitel 7: Anfragesprachen mit Rekursion Datalog — Datalog (Folien "Kapitel 7, Seite 1 bis 9"): Einführendes Beispiel einer Datalog-Anfrage, Syntax von Datalog, informelle Betrachtung der Semantik von Datalog-Anfragen.
Kapitel 8: Zusammenfassung und Ausblick (bis inkl. Folie "Kapitel 8, Seite 8"): Rückblick auf die wichtigsten Themenbereiche dieser Vorlesung; Ausblick auf weiterführende Themen im Bereich "Logik und Datenbanken".
Weitere Lektüre:
Die Originalarbeit von Arenas und Libkin finden Sie 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.
Umfassende Informationen zum Thema Datalog finden sich in Teil D von .