Logik in der Informatik Prof. Dr. Nicole Schweikardt

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden des Theorieteils, Tipps zum Weiterlesen und gelegentlich ergänzende Bemerkungen.

1. Di, 07.11.2017:  

   Kapitel 1: "Grundbegriffe" Heute: Festlegung grundlegender Notationen, u.a. Schema, Datenbank, konjunktive Anfragen (kurz: CQ), Homomorphismus von einer Anfrage Q auf eine Datenbank D, Beispiele für Anfragen, das Auswertungsproblem (kurz: AWP) für CQ, ein naiver Algorithmus zum Lösen des AWP für CQ, Satz von Chandra und Merlin über die NP-Vollständigkeit des AWP für 0-stellige CQ.

   Material: handschriftliche Notizen zu Kapitel 1

   Weitere Lektüre:
   [CM] ist die Originalarbeit von Chandra und Merlin. Die Arbeit [G-Param] gibt einen Überblick über Konzepte der parametrisierten Komplexitätstheorie.

2. Di, 14.11.2017:  

   Abschluss von Kapitel 1: "Grundbegriffe" - Heute: Folgerung aus der NP-Vollständigkeit des Auswertungsproblems für 0-stellige CQ; ein Satz von Papadimitriou und Yannakakis (ohne Beweis)
   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Klärung zur Frage, wie man alle "Dreiecke" in einem gerichteten Graphen berechnen kann; ein Satz über die maximale Anzahl von Dreiecken (Beginn des Beweises)

   Material: handschriftliche Notizen zu Kapitel 1; handschriftliche Notizen zu Kapitel 2: Teil 1

   Weitere Lektüre:
   Die Arbeit [NPRR] enthält (neben vielem Anderen) Informationen zur Anzahl der Dreiecke.

   Übungsaufgaben:

   1. Überlegen, ob es ein realistisches Anwendungsszenario gibt, in dem Datenbanken vorkommen, die in etwa von der Form D_m aus Beispiel 2.1 sind.
   2. Die Dreiecksanfrage Q_Δ in einem echten Datenbanksystem auf der Datenbank D_m aus Beispiel 2.1 für verschiedene (große) Werte von m auswerten und den Auswertungsplan sowie die Anzahl der bei der Auswertung durchgeführten Schritte analysieren.

3. Mi, 15.11.2017:  

   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Beweis des Satzes über die maximale Anzahl von Dreiecken; ein Algorithmus, der mit Laufzeit O((Anzahl Kanten)^3/2) alle Dreiecke ausgibt, die in dem Eingabe-Graph vorkommen; Definition des Begriffs Join-Anfragen inkl. Beispiele

   Material: handschriftliche Notizen zu Kapitel 2: Teil 1, Teil 2

   Weitere Lektüre:
   Die Arbeit [NPRR] enthält (neben vielem Anderen) Informationen zur Anzahl der Dreiecke.

   Übungsaufgaben:

   1. Versuchen, den in der Vorlesung vorgestellten effizienten Algorithmus zur Auswertung der Anfrage Q_Δ in SQL zu übertragen und auf einem Datenbanksystem auszutesten (u.a. auf Datenbanken der Form D_m aus Beispiel 2.1).
   2. Überlegen, ob sich die von Satz Δ gegebene obere Schranke an die Anzahl der Dreiecke von von 2(Anzahl der Kanten)^3/2 zu (Anzahl der Kanten)^3/2 verbessern lässt.
   3. Seien E₁, E₂, E₃ drei verschiedene Relationssymbole der Stelligkeit 3. Betrachten Sie die Join-Anfrage Q'_Δ(A,B,C) ← E₁(A,B), E₂(B,C), E₃(C,A). Seien N₁, N₂, N₃ die Anzahl der Tupel in den Relationen E₁, E₂, E₃ einer Datenbank D. Finden Sie eine möglichst gute (d.h. kleine) obere Schranke an die Anzahl der Tupel in Q'_Δ(D).

4. Di, 21.11.2017:  

   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Überlegungen dazu, wie viele Tupel es im Anfrageergebnis Q(D) einer Join-Anfrage Q höchstens geben kann; Definition der folgenden Begriffe: Anfrage-(Hyper)Graph G_Q, Kantenüberdeckung eines Hypergraphen (und einer Join-Anfrage), fraktionale Kantenüberdeckung eines Hypergraphen (und einer Join-Anfrage), Formulierung der AGM-Schranke; Beispiele zur Anwendung der AGM-Schranke

   Material: handschriftliche Notizen zu Kapitel 2: Teil 2, Teil 3

   Weitere Lektüre:
   Die Arbeit [G-AGM] gibt einen Überblick über die AGM-Schranke sowie intuitive Erklärungen zum Thema. [AGM] ist die Originalarbeit von Atserias, Grohe und Marx, in der die AGM-Schranke bewiesen wurde.

   Übungsaufgaben:

   1. Überlegen, ob es ein realistisches Anwendungsszenario gibt, in dem eine der Loomis-Whitney Join-Anfrage LW_k ähnliche Anfrage ausgewertet werden muss.
   2. Die Loomis-Whitney Join-Anfrage LW_k (für einige verschiedene Werte von k) in einem echten Datenbanksystem auf einer geeigneten Datenbank auswerten und den vom Datenbanksystem verwendeten Auswertungsplan sowie die Anzahl der bei der Auswertung durchgeführten Schritte analysieren.

5. Mi, 22.11.2017:  

   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Überlegungen dazu, wie man für eine gegebene Join-Anfrage Q und Zahlen N₁, ..., N_m eine fraktionale Kantenüberdeckung x von Q finden kann, für die das Produkt der Werte N_i^x(i) (für alle i) kleinstmöglich wird — Formulierung als lineares Optimierungsproblem über den rationalen Zahlen; Vorarbeiten zum Beweis der AGM-Schranke — grundlegende Begriffe aus der Wahrscheinlichkeitsrechnung: endliche Wahrscheinlichkeitsräume, Zufallsvariablen, die Entropie eines endlichen Wahrscheinlichkeitsraums, die Entropie einer Zufallsvariablen; Formulierung von Shearer's Lemma

   Material: handschriftliche Notizen zu Kapitel 2: Teil 3

   Weitere Lektüre:
   Die Arbeit [G-AGM] gibt einen Überblick über die AGM-Schranke sowie intuitive Erklärungen zum Thema. [AGM] ist die Originalarbeit von Atserias, Grohe und Marx, in der die AGM-Schranke bewiesen wurde.
   Das Buch [T] gibt eine Einführung zum Begriff der Entropie.

6. Di, 28.11.2017:  

   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Beweis der AGM-Schranke (unter Verwendung von Shearer's Lemma); Formulierung einer Aussage zur Optimalität der AGM-Schranke und Vorarbeiten zum Beweis dieser Optimalität: lineare Optimierungsprobleme, LP-Dualität und der starke Dualitätssatz

   Material: handschriftliche Notizen zu Kapitel 2: Teil 3, Teil 4

   Weitere Lektüre:
   Die Arbeit [G-AGM] gibt einen Überblick über die AGM-Schranke sowie intuitive Erklärungen zum Thema. [AGM] ist die Originalarbeit von Atserias, Grohe und Marx, in der die AGM-Schranke bewiesen wurde.
   Das Buch [T] gibt eine Einführung zum Begriff der Entropie.

   Übungsaufgabe:

   • Den Beweis von Shearer's Lemma durcharbeiten (siehe Teil 3 der handschriftlichen Notizen zu Kapitel 2).

7. Mi, 29.11.2017:  

   Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Beweis der Optimalität der AGM-Schranke; Erweiterung der AGM-Schranke auf Projektionen von Join-Anfragen

   Material: handschriftliche Notizen zu Kapitel 2: Teil 4, Teil 5

   Weitere Lektüre:
   Die Arbeit [G-AGM] gibt einen Überblick über die AGM-Schranke sowie intuitive Erklärungen zum Thema. [AGM] ist die Originalarbeit von Atserias, Grohe und Marx, in der die AGM-Schranke bewiesen wurde. In der Arbeit [GLV] haben Gottlob, Lee und Valiant die AGM-Schranke zu einer Schranke erweitert, die für alle konjunktiven Anfragen gilt.

   Übungsaufgabe:

   • Versuchen Sie, das im Beweis der Optimalität der AGM-Schranke betrachtete duale lineare Optimierungsproblem als ein geeignetes "fraktionales Rucksack-Packproblem" darzustellen.

8. Di, 05.12.2017:  

   Abschluss von Kapitel 2: Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen - Heute: Erweiterung der AGM-Schranke auf Projektionen von Join-Anfragen und auf allgemeine konjunktive Anfragen, in denen keine Konstanten vorkommen

   Material: handschriftliche Notizen zu Kapitel 2: Teil 5, Teil 6

   Weitere Lektüre:
   Die Arbeit [G-AGM] gibt einen Überblick über die AGM-Schranke sowie intuitive Erklärungen zum Thema. [AGM] ist die Originalarbeit von Atserias, Grohe und Marx, in der die AGM-Schranke bewiesen wurde. In der Arbeit [GLV] haben Gottlob, Lee und Valiant die AGM-Schranke zu einer Schranke erweitert, die für alle konjunktiven Anfragen (in denen keine Konstanten vorkommen) gilt.

   Übungsaufgabe:

   • Versuchen Sie, eine Variante des Resultats von Gottlob, Valiant und Lee zu formulieren und zu beweisen, die auch für konjunktive Anfragen, in denen Konstanten vorkommen, gilt.

9. Di, 19.12.2017:  

   Kapitel 3: Aufzählung von Anfrageergebnissen mit konstanter Verzögerung - Heute: verschiedene Aspekte der Auswertung von konjunktiven Anfragen unter updates (Zählen, Testen, Aufzählen mit konstanter Verzögerung); der Begriff der hierarchischen und der q-hierarchischen konjunktiven Anfragen; Grundlagen zur Komplexität von Matrixmultiplikation; die OMv-Vermutung; Nachweis der unteren Schranke für's Aufzählen von Anfrageergebnissen

   Material: Folien - heute: Folien 1-13; Kapitel 3 (Seiten 6-8) und Kapitel 5 (vor allem: Abschnitte 5.1-5.3, d.h. Seiten 10-13) der Arbeit [BKS]

   Weitere Lektüre:
   Dieses Kapitel beruht auf der Arbeit [BKS].

10. Mi, 20.12.2017:  

    Kapitel 3: Aufzählung von Anfrageergebnissen mit konstanter Verzögerung - Heute: die OuMv-Vermutung; die OV-Vermutung; Beweisidee zum Nachweis der unteren Schranke für's Zählproblem; Formulierung der oberen Schranke; der Begriff eines q-Tree

    Material: Folien - heute: Folien 13-19; Kapitel 3 (Seiten 6-8) und Kapitel 5 (vor allem: Abschnitte 5.1-5.3, d.h. Seiten 10-13) der Arbeit [BKS]

    Weitere Lektüre:
    Dieses Kapitel beruht auf der Arbeit [BKS].

    Übungsaufgabe:

    • Arbeiten Sie zu Folie 14 den Beweis für die Formel ψ_S-E-T aus.

11. Mi, 07.02.2018:  

    Abschluss von Kapitel 3: Aufzählung von Anfrageergebnissen mit konstanter Verzögerung - Heute: der Begriff eines q-tree und ein Algorithmus zur Konstruktion von q-Trees; ein Verfahren zur effizienten Auswertung von q-hierarchischen Anfragen unter Berücksichtigung von Datenbank-Updates (zunächst Illustration an einem Beispiel; danach Details zum allgemeinen Verfahren)

    Material: Folien - heute: Folien 17-21; Kapitel 4 (Seiten 8-10) und Kapitel 6 (vor allem: Seiten 17-22) der Arbeit [BKS]

    Weitere Lektüre:
    Dieses Kapitel beruht auf der Arbeit [BKS].

12. Di, 13.02.2018:  

    Kapitel 4: Leapfrog-Triejoin — ein worst-case-optimaler Join-Algorithmus - Heute: das leapfrog-join-Verfahren zur Berechnung des Durchschnitts von k Mengen; die trie-Repräsentation von Relationen; das leapfrog-triejoin-Verfahren zur Auswertung von Join-Anfragen

    Material: Kapitel 1-3 (Seiten 91-101) der Arbeit [V]

    Weitere Lektüre:
    Dieses Kapitel beruht auf der Arbeit [V].

    Übungsaufgaben:

    1. Überlegen Sie sich, wie die einzelnen Operatoren key, next, seek in einem Datenbanksystem realisiert werden können.
    2. Überlegen Sie sich, wie man einen B-Baum nutzen kann um eine trie-Repräsentation einer Datenbankrelation simulieren zu können.

13. Mi, 14.02.2018:  

    Abschluss von Kapitel 4: Leapfrog-Triejoin — ein worst-case-optimaler Join-Algorithmus - Heute: Details zur Laufzeitanalyse des leapfrog-triejoin-Verfahrens und zu Möglichkeiten der Realisierung der einzelnen verwendeten Iteratoren innerhalb eines Datenbanksystems

    Material: Kapitel 1-4 der Arbeit [V]

    Weitere Lektüre:
    Dieses Kapitel beruht auf der Arbeit [V].

    Übungsaufgaben:

    1. Arbeiten Sie die Details des leapfrog-triejoin-Verfahrens inkl. Angabe von Pseudo-Code für sämtliche vom Verfahren verwendeten Methoden und Prozeduren aus.
    2. Arbeiten Sie Kapitel 4 der Arbeit [V] (inkl. Beweis von Theorem 4.2) durch.