|
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. |
Di, 01.04.2008:
Einführung ins Thema. Organisatorisches. Kapitel 1: Das Relationale Modell.
Folien.
Lektüre: Teil A von [AHV]
Do, 03.04.2008:
Mit Kapitel 2: Konjunktive Anfragen (I) begonnen. Regelbasierte konjunktive Anfragen, Tableau-Anfragen,
eingeführt.
Monotonie und Erfüllbarkeit konjunktiver Anfragen bewiesen.
Folien.
Lektüre: Kapitel 4.1 & 4.2 von [AHV]
Di, 08.04.2008:
Weiter mit Kapitel 2: Konjunktive Anfragen (I):
Anfragen des konjunktiven Kalküls eingeführt. Äquivalenz der regelbasierten konjunktiven Anfragen, Tableau-Anfragen und
Anfragen des konjunktiven Kalküls bewiesen.
Konjunktive Anfragen mit "=" eingeführt, regelbasierte konjunktive Programme eingeführt.
Übungsblatt 1 ausgeteilt.
Folien (heute wurden die Folien 55–71 behandelt).
Lektüre: Kapitel 4.3 von [AHV]
Di, 15.04.2008:
Weiter mit Kapitel 2:
Auswertungskomplexität konjunktiver Anfragen:
Ein 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) (Theorem 2.20). Kurze Wiederholung des Begriffs der NP-Vollständigkeit.
Folien (heute wurden die Folien 72–79 behandelt).
Do, 17.04.2008:
Rest des Beweises von Theorem 2.20.
Die NP-Vollständigkeit des Auswertungsproblems (kombinierte Komplexität) für Boolesche Anfragen des konjunktiven Kalküls bewiesen.
Beginn mit Abschnitt 2.3: SPC-Algebra und SPJR-Algebra.
Übungsblatt 2 ausgeteilt.
Folien (heute wurden die Folien 77–88 behandelt).
Lektüre:
Originalarbeit [CM] von Chandra und Merlin.
Einführung [G] in Parametrische Komplexität für Datenbanktheoretiker/innen:
Kapitel 4.4 von [AHV].
Di, 22.04.2008:
Weiter mit Abschnitt 2.3: SPC-Algebra und SPJR-Algebra: Beispiele für SCP-Anfragen; die SPJR-Algebra eingeführt und an Beispielen illustriert;
Beginn des Beweises der Äquivalenz der Ausdrucksstärke von SPC-Algebra, SPJR-Algebra und konjunktivem Kalkül.
Folien (heute wurden die Folien 88–101 behandelt).
Lektüre:
Kapitel 4.4 und 4.5 von [AHV].
Do, 24.04.2008:
Rest des Beweises der Äquivalenz der Ausdrucksstärke von SPC-Algebra, SPJR-Algebra und konjunktivem Kalkül.
Beginn mit Kapitel 3: Relationale Algebra: Definition, Beispiele, Ausdrucksstärke,
Anfrageauswertung.
Übungsblatt 3 ausgeteilt.
Folien (heute wurden die Folien 101–119 behandelt).
Lektüre:
Abschnitte 5.1 und 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/. Dort sind auch
Hinweise zur Optimierung in real existierenden Datenbanksystemen zu finden.
Di, 29.04.2008:
Abschluss von Kapitel 3: Relationale Algebra: Anfrageauswertung und heuristische Optimierung; SIP-Strategien.
Folien (heute wurden die Folien 120–137 behandelt).
Lektüre: Abschnitt 6.1 von [AHV].
Di, 06.05.2008:
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.
Folien (heute wurden die Folien 138–150 behandelt).
Lektüre: Abschnitt 5.3 von [AHV].
Do, 08.05.2008:
Weiter mit Kapitel 4: Relationenkalkül. Beispiele für bereichsunabhängige Anfragen.
Bewiesen, dass die relationale Algebra, der Relationenkalkül mit Active Domain Semantik und der
bereichsunabhängige Relationenkalkül dieselbe Ausdrucksstärke haben.
Übungsblatt 4 ausgeteilt.
Folien (heute wurden die Folien 150–153 behandelt).
Lektüre: Abschnitt 5.3 von [AHV].
Di, 13.05.2008:
Weiter mit Kapitel 4: Relationenkalkül.
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 (heute wurden die Folien 153–162 behandelt).
Lektüre: Abschnitt 5.4 von [AHV].
Zum Satz von Trakhtenbrot siehe Kapitel 1.3.4 des Vorlesungsskripts [Sch].
Do, 15.05.2008:
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).
Beginn des Beweises der PSPACE-Vollständigkeit des Auswertungsproblems für Boolesche Anfragen des Relationenkalküls.
Folien (heute wurden die Folien 162–171 behandelt).
Lektüre: Abschnitte 5.4 und 6.3 von [AHV].
Di, 20.05.2008:
Abschluss des Beweises der PSPACE-Vollständigkeit des Auswertungsproblems für Boolesche Anfragen des Relationenkalküls.
Die Schaltkreis-Komplexitätsklasse AC° eingeführt.
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. Damit ist Kapitel 4: Relationenkalkül abgeschlossen.
Übungsblatt 5 ausgeteilt.
Folien (heute wurden die Folien 171–178 behandelt).
Lektüre: Abschnitte 17.1 und 17.2 von [AHV].
Di, 27.05.2008:
Ergänzung zu Definition 4.22: Definition des Begriffs "partieller C-Isomorphismus".
Mit Kapitel 4: Konjunktive Anfragen II begonnen: Kurze Wiederholung des Begriffs der "Tableau-Anfragen". Homomorphismen und kanonische Datenbanken eingeführt.
Den Homomorphismus-Satz bewiesen.
Folien (heute wurden die Folien 179–187 behandelt).
Lektüre: Abschnitt 6.2 von [AHV].
Originalarbeit [CM] von Chandra und Merlin.
Do, 29.05.2008:
Die NP-Vollständigkeit des Query Containment Problems für Tableau-Anfragen bewiesen.
Algorithmus zur Tableau-Minimierung.
Übungsblatt 6 ausgeteilt (Hinweis: Aufgabe 4 wird auf das nächste Übungsblatt verschoben).
Folien (heute wurden die Folien 187–189 behandelt).
Lektüre: Abschnitte 6.2 und 6.4 von [AHV].
Di, 03.06.2008:
Ein Beispiel zur verbesserten Optimierung von SPJR-Anfragen mittels Tableau-Minimierung.
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.
Gezeigt, dass Semijoin-Anfragen in Polynomialzeit (kombinierte Komplexität) ausgewertet werden können.
Folien (heute wurden die Folien 190–197 behandelt).
Lektüre: Abschnitte 6.2 und 6.4 von [AHV].
Originalarbeit [Y] von Yannakakis: .
Überblicksartikel [Sca] von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen.
Do, 05.06.2008:
Algorithmus zur Übersetzung von azyklischen Booleschen regelbasierten konjunktiven Anfragen in Boolesche Semijoin-Anfragen.
Algorithmus zur Konstruktion von Join-Bäumen.
Übungsblatt 7 ausgeteilt.
Folien (heute wurden die Folien 198–201 behandelt).
Lektüre: Abschnitte 6.2 und 6.4 von [AHV].
Originalarbeit [Y] von Yannakakis.
Überblicksartikel [Sca] von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen.
Di, 10.06.2008:
Abschluss des Beweises der Korrektheit des Algorithmus zur Konstruktion von Join-Bäumen.
Satz von Yannakakis: Das Auswertungsproblem für azyklische regelbasierte konjunktive Anfragen
kann in Polynomialzeit (kombinierte Komplexität) gelöst werden.
Definition des "konjunktiven Guarded Fragment" (kurz: GF(CQ)).
Nachweis der Äquivalenz der Ausdrucksstärke von GF(CQ)-Sätzen und azyklischen Booleschen
regelbasierten konjunktiven Anfragen.
Beginn mit Abschnitt 5.3: Konjunktive Anfragen mit Multimengen-Semantik betrachtet.
Folien (heute wurden die Folien 201–209 behandelt).
Lektüre: Abschnitte 6.2 und 6.4 von [AHV].
Originalarbeit [Y] von Yannakakis.
Überblicksartikel [Sca] von Scarcello zu Verallgemeinerungen des Begriffs der azyklischen Anfragen.
Originalarbeit [CV] von Chaudhuri und Vardi zur Multimengen-Semantik.
Do, 12.06.2008:
Abschluss von Kapitel 5: einige grundlegende Punkte zur Multimengen-Semantik betrachtet.
Beginn mit Kapitel 6: Abhängigkeiten und Normalformen. Funktionale Abhängigkeiten und verlustfreie Joins. Beginn mit Abschnitt 6.2: The Chase:
ein Beispiel, Definition der FD-Regel.
Übungsblatt 8 ausgeteilt.
Folien (heute wurden die Folien 210–228 behandelt).
Lektüre:
Originalarbeit [CV] von Chaudhuri und Vardi zur Multimengen-Semantik.
Abschnitte 8.1 und 8.2 von [AHV].
Di, 17.06.2008:
Abschluss von Abschnitt 6.2: The Chase:
Beweis der Church-Rosser-Eigenschaft der Verfolgungsjagd.
Äquivalenz, Query Containment und Minimierung von Anfragen unter Berücksichtigung einer Menge funktionaler Abhängigkeiten.
Folien (heute wurden die Folien 229–236 behandelt).
Lektüre:
Abschnitt 8.4 von [AHV].
Do, 19.06.2008:
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.
Dritte Normalform (3NF).
Übungsblatt 9 ausgeteilt.
Folien (heute wurden die Folien 237–253 behandelt).
Lektüre: Abschnitt 11.2 von [AHV].
Originalarbeit [AL] von Arenas und Libkin.
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.
Di, 24.06.2008:
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 (heute wurden die Folien 253–266 behandelt).
Lektüre: Abschnitt 11.2 von [AHV].
Originalarbeit [AL] von Arenas und Libkin.
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.
Do, 26.06.2008:
Abschluss von Kapitel 6: 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, den Satz
von Knaster und Tarski bewiesen.
Übungsblatt 10 ("Zusatzblatt") ausgeteilt.
Folien (heute wurden die Folien 266–290 behandelt).
Lektüre: Abschnitte 12.1–12.5 von [AHV].
Di, 01.07.2008:
Abschluss von Kapitel 7: Statische Analyse von Datalog-Programmen; Einschränkungen und Erweiterungen von Datalog (nicht-rekursives Datalog sowie
Datalog mit Negation).
Kapitel 8: "Zusammenfassung und Ausblick": Rückblick auf die wichtigsten Themenbereiche dieser Vorlesung; Ausblick auf weitere interessante Themen und
auf Lehrveranstaltungen im kommenden Semester.
Folien (heute wurden die Folien 290–323 behandelt).
Lektüre: Abschnitte 12.4, 12.5, 14.3 und 15 von [AHV].