Hier wird eine ungefähre Übersicht gegeben, wann welcher Stoff behandelt werden soll. Im Laufe des Semesters ist beabsichtigt, die Liste zu aktualisieren, und den tatsächlich behandelten Stoff einzutragen. Selbstverständlich sind alle Angaben unverbindlich.
Tatsächlicher Ablauf:
- 1. Donnerstag, 05.04.2018:
- Kapitel 0: Organisatorisches
(Folie 0-1 bis 0-36)
Motivation. Hinweise auf zahlreiche freie Systeme und Literatur. Kapitel 1: Einführung (Folie 1-13 bis 1-37, 1-49 bis 1-56)
Prädikate. Fakten. Datenbanken als Faktenmenge. Regeln. Definition abgeleiteter Prädikate. Beispiel: Verwandtschaftsbeziehungen. Mehrere Regeln über ein Prädikat zur Formulierung von Disjunktionen. Anfragen. Aufruf eines Prädikats mit verschiedenen Bindungsmustern (Ein-/Ausgabeargumente). - 2. Donnerstag, 12.04.2018:
- Kapitel 1: Einführung
(Folie 1-1 bis 1-12, 1-38 bis 1-60)
Wiederholung: Einführung in das Gebiet, Vorteile deklarativer Programmierung, deduktive Datenbanken. Rekursion (Standard-Beispiel: "ancestor"/Vorfahr - transitive Hülle). Bearbeitung von Rekursion bottom-up (Anwendung der Regeln in Pfeilrichtung wie in deduktiven Datenbanken) oder top-down (zielorientiert wie in Prolog). Rekursion in SQL-99. Vergleich von Datalog und Prolog. Benutzung eines Prolog-Systems. Anonyme Variablen. Laden eines Prolog-Programms aus einer Datei. Definitionsmodus und Anfragemodus. Unterbrechen einer Endlos-Rekursion mit Control-C. Debugger, "a" (abort) zum Verlassen des Debuggers. "halt." zum Beenden von Prolog. "help". Motivation für deduktive Datenbanken. Vergleich mit anderen Lösungen zur Integration von Programmiersprache und Datenbank. Vergleich mit Prolog. - 3. Donnerstag, 19.04.2018:
- Kapitel 2: Grundlagen der Prädikatenlogik
(Folie 2-1 bis 2-52)
Signaturen, sortierte und unsortierte Logik. Interpretationen. Variablendeklaration (nur für sortierte Logik nötig). Terme, Formeln. Variablenbelegung. Auswertung von Termen. Wahrheitswert von Formeln, Modell. Bereichsunabhängigkeit und Bereichsbeschränkung (zur effektiven Auswertbarkeit von Formeln bei gegebener Interpretation). Konsistenz, Äquivalenz, logische Folgerung. Einige bekannte Äquivalenzen der Prädikatenlogik. Pränex-Normalform. Konjunktive Normalform, disjunktive Normalform. - 4. Donnerstag, 26.04.2018:
- Kapitel 2: Grundlagen der Prädikatenlogik
(Folie 2-53 bis 2-73)
Substitution. Literal, Klausel. Grundliteral, Grundinstanz einer Klausel, Grundsubstitution für eine Klausel. Skolemnisierung zur Umwandlung beliebiger Formeln in Allaussagen/Klauseln. Bedeutung der Klauselform: Erfüllbarkeitsgleichheit. Herbrand-Modelle, Bedeutung von Herbrand-Modellen für Allaussagen, Automatisches Beweisen durch Widerspruch mit Umwandlung in Klauseln. - Kapitel 3: Pure Prolog
(Folie 3-1 bis 3-32)
Anfrage-Beantwortung als Aufgabe des automatischen Beweisens. Lexikalische Syntax von Prolog. Verschiedene Möglichkeiten zur Repräsentation von Zeichenketten. Interne Datenstrukturen zur Termrepräsentation. Abstrakte Syntax von Prolog. Standardsyntax und Operatorsyntax. Besprechung vordefinierter Operatoren. Prädikat "display". Kurzeinführung zu Listen. - 5. Donnerstag, 03.05.2018:
- Kapitel 3: Pure Prolog
(Folie 3-32 bis 3-65)
Wiederholung zur Operator-Syntax und Standard-Syntax, Listen-Syntax, Beispiele append, member, Diskussion der Rekursion über Listen, Beispiel: Rätsel vom Fährmann, Wolf, Ziege und Kohlkopf. Unterschiede deduktiver Datenbanken und Prolog. Terminierung. Definitionen Logisches Programm, Regelkopf, Regelrumpf, Regel über ein Prädikat, Fakt. Definitionen Herbrand-Interpretation, Herbrand-Universum, Herbrand-Basis. Minimales Herbrand-Modell. - 6. Donnerstag, 17.05.2018:
- Kapitel 3: Pure Prolog
(Folie 3-71 bis 3-76, 3-94 bis 3-120)
Wiederholung zu Substitutionen. Unifikation, Unifikator, allgemeinster Unifikator. "Occur Check" (Problem und Lösungsalternativen), Allgemeine Resolventenmethode ("Resolution") zum automatischen Beweisen, Lineare Resolution, SLD-Resolution, Sichtweisen: Beweis durch Widerspruch bis zur leeren Klausel (false) oder Vereinfachung der Anfrage bis zur leeren Konjunktion (true), Beispiel für SLD-Herleitung ("SLD Derivation"), formale Definition eines SLD-Resolutions-Schrittes. - 7. Donnerstag, 24.05.2018:
- Kapitel 3: Pure Prolog
(Folie 3-114 bis 3-149)
Wiederholung zum SLD-Resolutions-Schritt. Selektionsfunktion, Diskussion der Prolog-Selektionsfunktion ("First Literal"), faire Selektionsfunktionen, formale Definition einer SLD-Herleitung/Ableitung, Klassifikation von SLD-Herleitungen (erfolgreich, gescheitert, unendlich, unvollständig), formale Definition der berechneten Antwortsubstitution, Korrektheit und Vollständigkeit der SLD-Resolution für definite Hornklauseln, Probleme bei der Übertragung dieser Aussagen auf Prolog, SLD-Bäume. Vierport-Modell des Prolog-Debuggers, praktische Verwendung des Debuggers. - 8. Donnerstag, 31.05.2018:
- Kapitel 3: Pure Prolog
(Folie 3-71 bis 3-93)
Minimales Herbrandmodell. Beispiele für Nicht-minimale Modelle. Gründe, warum man die logischen Formeln nicht so schreibt, dass man nur intendierte Modelle hat. Umwandlung von <- in <-> mittels Clark's CDB. Grenzen der CDB. Positives Wissen explizit, negatives implizit. Existenz und Eindeutigkeit des minimalen Modells (mit Beweis). Beziehung des minimalen Modells zur logischen Folgerung. Wiederholung zum T_P-Operator, Einführung in die Verbandtheorie um einen "Grenzwert" für unendliche Iterationen des T_P-Operators zu bekommen, Verband der Herbrand-Interpretationen, Satz: "Eine monotone Abbildung T auf einem vollständigen Verband hat immer einen kleinsten Fixpunkt, und zwar glb({I|T(I)<=I})." Bei unserer Anwendung ist das gerade das minimale Modell. Definition der Iteration einer Abbildung. Satz: Bei stetigen Abbildungen reicht eine omega-fache Iteration um den kleinsten Fixpunkt zu erreichen. "Supported" Modelle (kausale Modelle). - Kapitel 4: Eingebaute Prädikate
(Folie 4-1 bis 4-24)
Bindungsmuster, Beziehung von Prädikaten mit Bindungsmustern zu klassischen Prozeduren, formale Behandlung von eingebauten Prädikaten. - 9. Donnerstag, 07.06.2018:
- Kapitel 4: Eingebaute Prädikate
(Folie 4-24 bis 4-60)
Bindungsmuster, Beziehung von Prädikaten mit Bindungsmustern zu klassischen Prozeduren, formale Behandlung von eingebauten Prädikaten. Eingebaute Prädikate von Prolog: Term-Vergleich (=, ==, \=, \==, @> @< ...), Term-Klassifikation (var, nonvar, atom, atomic, integer, number, ...), Zugriff auf Komponenten von Termen und Term-Synthese (=.., functor, arg, name, ...), arithmetische Prädikate (is, =:=, =\=, <, =< >=, >), String-Funktionen, Prädikate zur Ausführung von Anfragen (call, findall, bagof, setof), dynamische Datenbank (dynamic, assert, retract, retractall, listing), Ein-/Ausgaben (kurzer Überblick). - 10. Donnerstag, 14.06.2018:
- Kapitel 4: Eingebaute Prädikate
(Folie 4-61 bis 4-84)
Bereichsbeschränkung ("range-restriction", "allowedness", "safety"). Bereichsbeschränkung für gegebene Bindungsmuster. Funktionssymbole, Termkonstruktoren. Eine Möglichkeit zur Integration auswertbarer Funktionen in einem erweiterten Datalog. - Kapitel 5: Praktische Prolog-Programmierung
(Folie 5-1 bis 5-42)
Cut: Wirkungsweise, Anwendungen: Verbesserung der Effizienz mit Cut (Prädikate deterministisch machen), Fallunterscheidungen mit Cut, Problem: Keine einfache logische Semantik, Gefahren: Beispiele für Fehler, wenn Pr"adikate mit unerwarteten Bindungsmustern aufgerufen werden, Alternativen zum Cut (if-then-else, not, once) (Konstrukte, die mittels Cut definiert sind, aber die intendierte Semantik klarer machen). Vergleich von Prolog mit klassischen Programmiersprachen: Datentypen (insbesondere Arrays), Variablen (z.B. mehrfache Zuweisung in Schleifen durch Rekursion ersetzen). - 11. Donnerstag, 21.06.2018:
- Kapitel 5: Praktische Prolog-Programmierung
(Folie 5-38 bis 5-80)
"Prolog vs. Pascal": Variablen in imperativer Programmierung im Vergleich mit Variablen in Prolog, If, Case, ausführliche Diskussion über Indexe beim Zugriff auf Prolog-Regeln, Vorschiedene Möglichkeiten zur Übersetzung von Schleifen nach Prolog, Endrekursions-Optimierung, repeat, Definite Clause Grammars, Differenzlisten, Beispielprogramm für Lexikalische Analyse. - Kapitel 6: Bottom-Up Auswertung
(Folie 6-1 bis 6-5)
Basis-Algorithmus der Bottom-Up Auswertung, "answer"-Prädikat, Probleme des zu simplen Basis-Algorithmus. Interpreter vs. Compiler. - 12. Donnerstag, 28.06.2018:
- Kapitel 6: Bottom-Up Auswertung
(Folie 6-5 bis 6-74)
Basis-Algorithmus der Bottom-Up Auswertung, "answer"-Prädikat, Beispiel für Ergebnis der Übersetzung eines Datalog-Programms in imperativen Code mit relationaler Algebra, schrittweise Verbesserung des Interpreters und Übergang zu Compiler durch partielle Auswertung. Erster Schritt: Spezielle Behandlung der EDB-Prädikate. Zweiter Schritt: Auswertungs-Reihenfolge für Regeln mittels Prädikat-Abhängigkeits-Graph. Dritter Schritt: Seminaive Auswertung. Ziel: Jede anwendbare Regel-Instanz wird nur ein Mal angewendet. Übersetzung von Datalog-Regeln in relationale Algebra und in SQL. Direkte Auswertung von Datalog-Regeln mittels Nested-Loop-Join bzw. Index-Join. Diskussion zur Duplikat-Eliminierung. Diskussion zur Nutzung relationaler DBMS als Grundlage, Hinweis auf temporäre Tabellen. - 13. Donnerstag, 05.07.2018:
- Kapitel 7: Magische Mengen
(Folie 7-1 bis 7-38)
[Verzögerung durch Beamer-Probleme]
Ziel der "Magischen Mengen"-Transformation, Erläuterung am Beispiel, Korrektheit (Äquivalenz für gegebene Anfrage und beliebige Datenbank-Zustände), Codierung von Unteranfragen durch "magische" Prädikate, SIP-Strategien, Hinweis auf Verallgemeinerung füp;r Merge Join und parallele Auswertung, Berechnung des "Adorned Program" mit expliziten Bindungsmustern, Diskussion zur Unterstützung mehrerer Bindungsmuster für ein Prädikat durch mehrere Kopien/Varianten der gleichen Regel des Eingabeprogramms. - ...
Planung (unverbindlich, wird noch aktualisiert):
- 14. Donnerstag, 12.07.2018:
- Kapitel 7: Magische Mengen
(Folie 7-42 bis 7-105)
... - Kapitel 8: Nichtmonotone Negation
(Folie 8-1 bis 8-48)
...
| Prof. Dr. Stefan Brass | Impressum |