In diesem Logbuch werden regelmäßig Informationen
bereit gestellt. Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Tipps zum Weiterlesen und gelegentlich ergänzende Bemerkungen.
-
Mo, 25.04.2022:
-
Eröffnungsveranstaltung. Klärung von Organisatorischem (entlang der Webseite der Vorlesung). Kapitel 1: Einleitung. Kapitel 2: Das Relationale Modell - heute: Relationsschemata und Relationen,
Datenbankschemata und Datenbank(instanz)en, Beispieldatenbank mit Kinodaten, Anfragen und Anfragefunktionen, generische Anfragefunktionen (informell)
Material:
- Folien 1 -- 27
- Skript bis Seite 21
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Teil A und Kapitel 4.1 und 4.2 von [AHV]
- Abschnitte 19.1 und 19.2 des Artikels [SSS]
-
Di, 26.04.2022:
- Abschluss von Kapitel 2: Das Relationale Modell - heute: generische Anfragefunktionen (Definition), Boolesche Anfragen, Datenkomplexität und kombinierte Komplexität
Start mit Kapitel 3: Konjunktive Anfragen - heute: Syntax und Semantik von regelbasierten konjunktiven Anfragen, der "active domain" von Datenbanken und Anfragen; Monotonie und Erfüllbarkeit regelbasierter konjunktiver Anfragen (offen: Beweis Satz 3.6)
Material:
- Folien 27 -- 42
- Skript Seite 21 -- 31
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Teil A und Kapitel 4.1 und 4.2 von [AHV]
-
Mo, 02.05.2022:
- Weiter mit Kapitel 3: Beweis Satz 3.6, Syntax und Semantik von Tableau-Anfragen; Syntax und Semantik des konjunktiven Kalküls; eine Normalform für CQ; Beginn des Beweises der Äquivalenz der Ausdrucksstärke von Tableau-Anfragen, konjunktivem Kalkül und regelbasierten konjunktiven Anfragen
Material:
- Folien 43 -- 58
- Skript Seite 31 -- 41
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Teil A und Kapitel 4.1 und 4.2 von [AHV]
-
Di, 03.05.2022:
- Weiter mit Kapitel 3: Regelbasierte konjunktive Anfragen mit "="; regelbasierte konjunktive Programme; Auswertungskomplexität konjunktiver Anfragen: das Auswertungsproblem für CQ (kombinierte Komplexität) und die Größe von Anfragen und Datenbanken; ein "naiver" Algorithmus zum Auswerten konjunktiver Anfragen; der Begriff der "Algorithmen mit Taktung f(k,n)"; Beginn des Beweises von Theorem 3.20 (Transformation eines Algorithmus zur Auswertung Boolescher Anfragen des konjunktiven Kalküls zu einem Algorithmus zur Auswertung beliebiger Anfragen des konjunktiven Kalküls, so dass die Taktung zwischen der Ausgabe zweier Ergebnis-Tupel O(k^3 n log n) ist)
Material:
- Folien 59 -- 70
- Skript Seite 42 -- 52
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
-
Mo, 09.05.2022:
- Weiter mit Kapitel 3: Zweiter Teil des Beweises von Theorem 3.20 (Transformation eines Algorithmus zur Auswertung Boolescher Anfragen des konjunktiven Kalküls zu einem Algorithmus zur Auswertung beliebiger Anfragen des konjunktiven Kalküls, so dass die Taktung zwischen der Ausgabe zweier Ergebnis-Tupel O(k^3 n log n) ist); NP, Polynomialzeit-Reduktionen und NP-Vollständigkeit; Nachweis der NP-Vollständigkeit des Auswertungsproblems (kombinierte Komplexität) für Boolesche regelbasierte konjunktive Anfragen (ein Satz von Chandra und Merlin); Folgerung aus der NP-Vollständigkeit
Material:
- Folien 70 -- 78
- Skript Seite 52 -- 59
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 4.3 von [AHV];
die Originalarbeit [CM] von Chandra
und Merlin finden Sie hier
-
Di, 10.05.2022:
- Weiter mit Kapitel 3: SPC-Algebra und SPJR-Algebra: Syntax,Semantik und viele Beispiele; Nachweis der Äquivalenz der Ausdrucksstärke von SPC-Algebra und SPJR-Algebra; Nachweis der Äquivalenz zwischen SPC-Algebra, SPJR-Algebra, Tableau-Anfragen, regelbasierten konjunktiven Anfragen und Anfragen des konjunktiven Kalküls
Material:
- Folien 79 -- 100
- Skript Seite 59 -- 73
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 4.4, 4.5 und 6.2 von [AHV]
-
Mo, 16.05.2022:
- Weiter mit Kapitel 3: Konjunktive Anfragen - heute: Vorbemerkungen zum Thema Optimierung; Definition des Erfüllbarkeitsproblems, des Äquivalenzproblems und des Query Containment Problems; Einführung der Begriffe "Substitution", "Homomorphismus" (für Tableau-Anfragen) und "kanonische Datenbanken"; Formulierung und Beweis des Homomorphismussatzes; NP-Vollständigkeit des Query Containment Problems für Tableau-Anfragen nachgewiesen;
Material:
- Folien 100 -- 107
- Skript Seite 74 -- 82
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 6.2 und 6.4 von [AHV]
die Originalarbeit [CM] von Chandra
und Merlin finden Sie hier
-
Di, 17.05.2022:
- Weiter mit Kapitel 3: Konjunktive Anfragen - heute: Minimierung von Tableau-Anfragen; Greedy-Algorithmus zur Minimierung von Tableau-Anfragen (inkl. Korrektheitsbeweis) ; ein Beispiel zur Verwendung der Tableau-Minimierung zur Optimierung von SPJR-Anfragen;
Material:
- Folien 100 -- 107
- Skript Seite 74 -- 82
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 6.2 und 6.4 von [AHV]
die Originalarbeit [CM] von Chandra
und Merlin finden Sie hier
-
Mo, 23.05.2022:
- Weiter mit Kapitel 3: azyklische konjunktive Anfragen, Join-Bäume, Semijoin-Anfragen, ein effizienter Algorithmus zur Auswertung von Semijoin-Anfragen; die Äquivalenz von Booleschen Semijoin-Anfragen und azyklischen regelbasierten Booleschen Anfragen; ein Algorithmus zum Test auf Azyklizität und zum Erzeugen von Join-Bäumen (heute: Formulierung des Algorithmus und Beispielläufe des Algorithmus)
Material:
- Folien 110 -- 119
- Skript Seite 88 -- 98
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 6.2 und 6.4 von [AHV]
-
Di, 24.05.2022:
- Abschluss von Kapitel 3: ein Algorithmus zum Test auf Azyklizität und zum Erzeugen von Join-Bäumen (heute: Korrektheitsbeweis; detailierte Idee); der Satz von Yannakakis, der besagt, dass das Auswertungsproblem für azyklische konjunktive Anfragen (kombinierte Komplexität) in Polynomialzeit gelöst werden kann; die Komplexitätsklasse LOGCFL; das konjunktive Guarded Fragment GF(CQ) eingeführt und argumentiert, 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 regelbasierter konjunktiver Anfragen, inkl. Überblick über Forschungsergebnisse und offene Forschungsfragen
Material:
- Folien 118 -- 132
- Skript Seite 98 -- 108
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 6.2 und 6.4 von [AHV].
Die Originalarbeit [Y] von Yannakakis.
Einen Überblick über
Verallgemeinerungen des Begriffs der azyklischen Anfragen gibt die
Arbeit [Sca] von Scarcello.
-
Mo, 30.05.2022:
- Start mit Kapitel 4: Datalog - heute: einführendes Beispiel; Syntax von Datalog; der "immediate consequence-Operator" TP und der "Stufen-Operator" SP; die Fixpunkt-Semantik von Datalog; ein Algorithmus zum Auswerten von Datalog-Anfragen (dessen Datenkomplexität in Polynomialzeit liegt); Modellbasierte Semantik von Datalog und der Satz von Knaster und Tarski; Beweisbasierte Semantik von Datalog, Fakten und Beweisbäume;
Material:
- Folien 134 -- 153
- Skript Seite 119 -- 129
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Umfassende Informationen zum Thema Datalog finden sich in Teil D
von [AHV] und in dem Überblicksartikel
[Datalog] von Dantsin, Eiter,
Gottlob und Voronkov
-
Di, 31.05.2022:
- Weiter mit Kapitel 4: Monotonie von Datalog-Anfragen Q und deren Abschluss unter adom(Q)-Homomorphismen; Konstruktion eines Datalog-Programms PM,k, das bei Eingabe einer Datenbank Iw, die ein Wort w repräsentiert, die ersten |w|k-1 Schritte des Laufs der Turingmaschine M bei Eingabe w simuliert;Formulierung eines Satzes von Immerman und Vardi, der besagt, dass das Auswertungsproblem für Datalog-Anfragen bzgl. kombinierter Komplexität EXPTIME-vollständig und bzgl. Datenkomplexität PTIME-vollständig ist; das Erfüllbarkeitsproblem für Datalog-Anfragen; das Query Containment Problem (QCP) für Datalog-Anfragen (vorerst ohne Beweis)
Material:
- Folien 154 -- 172
- Skript Seite 129 -- 138
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Umfassende Informationen zum Thema Datalog finden sich in Teil D
von [AHV] und in dem Überblicksartikel
[Datalog] von Dantsin, Eiter,
Gottlob und Voronkov
-
Mo, 13.06.2022 (letzte Woche war Pfingsten und deshalb nur Ü):
- Weiter mit Kapitel 4: Beweis Unentscheidbarkeit des Query Containment Problems (QCP) für Datalog-Anfragen; Beschränktheit von Datalog-Programmen; Unentscheidbarkeit der Beschränktheit von Datalog-Programmen (ohne Beweis); Einschränkung: nr-Datalog, der Abhängigkeitsgraph eines Datalog-Programms, Charakterisierung der Ausdrucksstärke von nr-Datalog via SPCU-Algebra und positiv existentiellen Kalkül
Material:
- Folien 172 -- 184
- Skript Seite 138 -- 147
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Umfassende Informationen zum Thema Datalog finden sich in Teil D
von [AHV] und in dem Überblicksartikel
[Datalog] von Dantsin, Eiter,
Gottlob und Voronkov
-
Di, 14.06.2022:
- Abschluss von Kapitel 4: Datalog mit Negation: semipositives Datalog mit Negation, stratifiziertes Datalog mit Negation, nicht-rekursives Datalog mit Negation
- Beginn mit Kapitel 5: Funktionale Abhängigkeiten - heute: Einführung ins Thema ; Grundbegriffe zum Thema "funktionale Abhängigkeiten" und FD-Mengen; verlustfreie Joins (inkl. Beweis von Proposition 5.2); Beginn des Abschnitts über "The Chase - die Verfolgungsjagd": ein Beispiel zur Minimierung von Tableau-Anfragen unter Berücksichtigung von funktionalen Abhängigkeiten;
Material:
- Folien 184 -- 206
- Skript Seite 147 -- 164
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 8.1, 8.2 und 8.4
von [AHV]
-
Mo, 27.06.2022 (letzte Woche gab es krankheitsbedingt keine Veranstaltungen):
- Weiter mit Kapitel 5: Äquivalenz und Query Containment bzgl. einer FD-Menge F; die FD-Regel; Nachweis, dass das Anwenden der FD-Regel Äquivalenz bzgl. einer FD-Menge F erhält (Proposition 5.6); Verfolgungssequenzen und deren Eigenschaften; ein Polynomialzeit-Algorithmus zur Berechnung von chase(T,t,F); Algorithmen für Query Containment und Äquivalenz von konjunktiven Anfragen relativ zu einer FD-Menge, Minimierung von konjunktiven Anfragen relativ zu einer FD-Menge; Implikation von funktionalen Abhängigkeiten; ein Polynomialzeit-Algorithmus zum Entscheiden, ob eine FD f aus einer FD-Menge F folgt (Satz 5.17);
Material:
- Folien 184 -- 219
- Skript Seite 147 -- 172
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 8.2 und 8.4
von [AHV]
-
Mo, 28.06.2022 :
- Abschluss Kapitel 5: der Armstrong-Kalkül und Nachweises der Vollständigkeit des Armstrong-Kalküls
- Beginn Kapitel 6: Relationale Algebra - heute: 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; Wiederholung einiger aus der Veranstaltung DBS I bekannter Aspekte zur Anfrageauswertung und heuristischen Optimierung
Material:
- Folien 220 -- 252
- Skript Seite 173 -- 192 ??
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
-
Kapitel 5.1 und 6.1 von [AHV]
-
Di, 05.07.2022:
- Abschluss Kapitel 6 und Start Kapitel 7: Relationenkalkül - heute: Relationenkalkül mit natürlicher Semantik, Relationenkalkül mit Active Domain Semantik und bereichsunabhängigen Relationenkalkül eingeführt und an Beispielen illustriert; Beweis, 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 und benutzt, um zu zeigen, dass es keinen Algorithmus gibt, der bei Eingabe einer Anfrage des Relationenkalküls entscheidet, ob die Anfrage bereichsunabhängig ist
Material:
- Folien 253 -- 275
- Skript Seite 192 -- 213
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel 5.4 von [AHV];
zum Satz von Trakhtenbrot siehe Kapitel 9.1 von [L]
-
Mo, 11.07.2022:
- Weiter mit 7: Relationenkalkül - heute:
den sicheren Relationenkalkül CALCsr eingeführt und an
Beispielen illustriert; ein technisches Lemma zum Relationenkalkül CALCsr (ohne Beweis); nachgewiesen, dass der sichere Relationenkalkül CALCsr bereichsunabhängig ist und genau dieselbe Ausdrucksstärke wie die relationale Algebra hat; die Unentscheidbarkeit der statischen Analyse für relational vollständige Anfragesprachen nachgewiesen; Beweisidee zum Satz 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)
Material:
- Folien 276 -- 293
- Skript Seite 213 -- 228
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel Kapitel 5.4 und 6.3 von [AHV]
-
Di, 12.07.2022:
- Abschluss von Kapitel 7: Relationenkalkül - Gaifman-Lokalität und ihre Anwendung;
- Kapitel 8: Zusammenfassung und Ausblick, Abschluss der Veranstaltung, Hinweise zur Vorbereitung auf eine mündliche Modulabschlussprüfung
Material:
- Folien 293 --
- Skript Seite 228 --
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):
- Kapitel Kapitel 5.4 und 6.3 von [AHV]
