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, 16.10.2012

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

Kapitel 0: Einführung ins Thema; Organisatorisches (Aufzeichnung vom 16.10.2012)
Kapitel 1: Das relationale Modell (Aufzeichnung vom 16.10.2012)

Weitere Lektüre:

Teil A von [AHV].

Di, 23.10.2012

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 (Aufzeichnung vom 23.10.2012)

Weitere Lektüre:

Kapitel 4.1 und 4.2 von [AHV].

Di, 30.10.2012

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 (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 von Chandra und Merlin: hier; Einführung in die Parametrische Komplexität für Datenbanktheoretiker/innen: hier.

Di, 06.11.2012

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 (Aufzeichnung vom 06.11.2012)

Weitere Lektüre:

Kapitel 4.4 und 4.5 von [AHV].

Di, 13.11.2012

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 (Aufzeichnung vom 13.11.2012)

Weitere Lektüre:

Kapitel 6.2-6.4 von [AHV]. Originalarbeit von Chandra und Merlin: hier.

Di, 20.11.2012

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 (Aufzeichnung vom 20.11.2012)

Weitere Lektüre:

Kapitel 6.2 und 6.4 von [AHV]. Die Originalarbeit von Chandra und Merlin finden Sie hier.

Di, 27.11.2012

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 (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 zu Verallgemeinerungen des Begriffs der azyklischen Anfragen finden Sie hier.

Di, 04.12.2012

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 (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 von Dantsin, Eiter, Gottlob und Voronkov.

Di, 11.12.2012

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 (Aufzeichnung vom 11.12.2012)

Weitere Lektüre:

Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel von Dantsin, Eiter, Gottlob und Voronkov.

Di, 18.12.2012

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

Di, 15.01.2013

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

Di, 22.01.2013

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

Di, 29.01.2013

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

Di, 05.02.2013

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

Di, 12.02.2013

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.