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:
- ...
Planung (unverbindlich, wird noch aktualisiert):
- 1. Donnerstag, 04.04.2024:
- Kapitel 0: Organisatorisches
(Folie 0-1 bis 0-42)
Motivation. Organisatorisches. Hinweise auf zahlreiche freie Systeme und Literatur. - Kapitel 2: Prolog-Einführung an Beispielen
(Folie 2-1 bis 2-42)
Bezeichner in Prolog. Datenbanken als Faktenmenge. Prädikate. Bereichskalkül vs. Tupelkalkül. Beispiel-Datenbank zu Verwandtschaftsbeziehungen. Benutzung eines Prolog-Systems. Laden eines Prolog-Programms aus einer Datei. Definitionsmodus und Anfragemodus. Anfragen. Aufruf eines Prädikats mit verschiedenen Bindungsmustern (Ein-/Ausgabeargumente). Unterbrechen einer Endlos-Rekursion mit Control-C. Debugger, "a" (abort) zum Verlassen des Debuggers. "halt." zum Beenden von Prolog. "help". Logische Formeln. Fakten. Regeln. Regelkopf und Regelrumpf. Definition abgeleiteter Prädikate. Regel über ein Prädikat. Beispiel: Verwandtschaftsbeziehungen. Anonyme Variablen. Mehrere Rumpfliterale. Regelsyntax in Prolog. - 2. Donnerstag, 11.04.2024:
- Kapitel 2: Prolog-Einführung an Beispielen
(Folie 2-42 bis 2-57)
Wiederholung: Beispiel-Datenbank zu Verwandtschaftsbeziehungen. Regelsyntax in prolog. Definition abgeleiteter Prädikate. Mehrere Regeln über ein Prädikat zur Formulierung von Disjunktionen. Syntax von Anfragen. 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. Anwendungen von Rekursion. - Kapitel 1: Einführung
(Folie 1-1 bis 1-19)
Einführung in das Gebiet. Vorteile deklarativer Programmierung. Deduktive Datenbanken. Vergleich von Datalog und Prolog, Vorteile deduktiver Datenbanken. Geschichte des Gebiets. - 3. Donnerstag, 18.04.2024:
- Kapitel 1: Einführung
(Folie 1-18 bis 1-24)
Geschichte des Gebiets. Nutzung von Prolog und Constraint Technologien in der Industrie. - Kapitel 3: Klausel-Logik
(Folie 3-1 bis 3-23)
Pränex-Normalform, Konjunktive-Normalform. Literal, Klausel, leere Klausel, Horn Klausel, definite Horn Klausel, Logisches Programm. Regel-Schreibweise von Klauseln. Kopf und Rumpf von Regeln. Regeln in der disjunktiven logische Programmierung. Definite Hornklauseln als Regeln. Beweis durch Widerspruch. Anfragen. Skolemisierung zur Umwandlung beliebiger Formeln in Allaussagen/Klauseln. Skolem-Konstanten, Skolem-Funktionen. Bedeutung der Klauselform: Erfüllbarkeitsgleichheit. Grundterm, Grundliteral. Exkurs zu unserem Konsistenztest für SQL-Anfragen mit der Technik der Skolemisierung, Erkennung semantischer Fehler in SQL-Anfragen. Herbrand-Interpretationen, Herbrand-Universum, Herbrand-Basis. Herbrand-Modelle, Bedeutung von Herbrand-Modellen für Allaussagen, Automatisches Beweisen durch Widerspruch mit Umwandlung in Klauseln. - 4. Donnerstag, 25.04.2024:
- Kapitel 3: Klausel-Logik
(Folie 3-24 bis 3-33)
Wiederholung zur Bedeutung von Herbrand-Interpretationen. Substitutionen, Anwendung einer Substitution auf Terme und Formeln. Grundsubstitution für eine Klausel. Grundinstanzen von Klauseln, Menge aller Grundinstanzen der Regeln eines logischen Programms. - Kapitel 4: Prolog Syntax
(Folie 4-1 bis 4-29, 4-36 bis 4-38)
Anfrage-Beantwortung als Aufgabe des automatischen Beweisens. Lexikalische Syntax von Prolog: Atome (Bezeichner für Konstanten, Funktionssymbole und Prädikate). Notation für Zahlen mit verschiedener Basis. Verschiedene Möglichkeiten zur Repräsentation von Zeichenketten. Garbage Collection. Interne Datenstrukturen zur Termrepräsentation. Abstrakte Syntax von Prolog. Standardsyntax und Operatorsyntax. Ausgaben der Prädikate "write" (Operator-Syntax) und "display" (Standard-Syntax). Kurzeinführung zu Listen. - 5. Donnerstag, 02.05.2024:
- Kapitel 4: Prolog Syntax
(Folie 4-30 bis 4-47)
Besprechung vordefinierter Operatoren. Einschrängen bei gemischter Syntax (Standardsyntax und Operatorsyntax). Listensyntax. Definition von append als Beispiel für rekursive Verarbeitung von Listen. Formale Definition der Syntax von Termen. - Kapitel 5: SLD Resolution
(Folie 5-1 bis 5-44)
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. 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. - 6. Donnerstag, 16.05.2024:
- Kapitel 5: SLD Resolution
(Folie 5-5, 5-24, 5-27, 5-33, 5-35, 5-40 bis 5-61)
Wiederholung zur Unifikation, Wiederholung zur SLD-Resolution, Resolution-Schritt, SLD-Ableitung. Wiederholung zu berechneten Antwort-Substitutionen, Korrektheit und Vollständigkeit von SLD-Resolution und von Prolog. SLD-Bäume. Endloszweige bei SLD-Resolution, kurzer Exkurs zu SLD-Resolution mit Tabellierung (XSB). Vierport-Modell des Prolog-Debuggers, praktische Verwendung des Debuggers, Spypoints, Prädikate trace, spy, notrace, nodebug. - Kapitel 6: Eingebaute Prädikate in Prolog
(Folie 6-1 bis 6-13)
Bedeutung eingebauter Prädikate. Bindungsmuster, Beziehung von Prädikaten mit Bindungsmustern zu klassischen Prozeduren, formale Behandlung von eingebauten Prädikaten. Datenbank-Relationen: "Full Table Scan" entspricht Bindungsmuster f...f. - 7. Donnerstag, 23.05.2024:
- Kapitel 6: Eingebaute Prädikate in Prolog
(Folie 6-8 bis 6-61)
Wiederholung zu Bindungsmustern. Bindungsmuster und Datenbank-Relationen: Full Table Scan, Indexe. Was ist allgemein ein Index? Modes in Prolog, verschiedene mögliche Bedeutungen von "bound". 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, ...), Atome und Strings (atom_chars, name ...), arithmetische Prädikate (is, =:=, =\=, <, =< >=, >), Prädikate zur Ausführung von Anfragen (call, findall, bagof, setof), dynamische Datenbank (dynamic, assert, retract, retractall, listing), Ein-/Ausgaben (write, display, nl, read, put_char, get_char, ...), Ein-/Ausgabeströme (open, close, ...), Steuerung (true, fail, repeat, once, \+, ...), Prolog Umgebung (halt, statistics, ...), Debugger (trace, spy, nodebug). Exkurs zur Bedeutung von Backups, Diskussion zu Hackern, die Backups zu Erpressungszwecken zerstören wollen. - Kapitel 7: Praktische Prolog-Programmierung
(Folie 7-1 bis 7-8)
Cut: Wirkungsweise, Bedeutung. - 8. Donnerstag, 30.05.2024:
- Kapitel 7: Praktische Prolog-Programmierung
(Folie 7-4, 7-7 bis 7-42)
Cut: Wirkungsweise, Anwendungen: Verbesserung der Effizienz mit Cut (Prädikate deterministisch machen, Laufzeit verbessern, Speicherbedarf verbessern), 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). Diskussion zu Vor- und Nachteilen des Cuts, und vernünftige, zurückhaltende Anwendungen in Prolog-Programmen. Vergleich von Prolog mit klassischen Programmiersprachen: Datentypen (insbesondere Arrays), Variablen (z.B. mehrfache Zuweisung in Schleifen durch Rekursion ersetzen). - 9. Donnerstag, 06.06.2024:
- Kapitel 7: Praktische Prolog-Programmierung
(Folie 7-40 bis 7-61)
"Prolog vs. Pascal": Variablen in imperativer Programmierung im Vergleich mit Variablen in Prolog, Beispiel zum Verpacken von mehreren Variablen in einer Struktur (Objekt), Dynamische Datenbank für globale Variablen, If, Case, ausführliche Diskussion über Indexe beim Zugriff auf Prolog-Regeln, Vorschiedene Möglichkeiten zur Übersetzung von Schleifen nach Prolog, Endrekursions-Optimierung, Schleifen mit Backtracking, repeat. - Kapitel 8: Grammatiken in Prolog (Definite Clause Grammars)
(Folie 8-1 bis 8-25)
Vergleich von Syntaxanalyse in Prolog mit Syntaxanalyse in Parsergeneratoren wie yacc, Definite Clause Grammars, Differenzlisten, Beispielprogramm für Lexikalische Analyse. - 10. Donnerstag, 13.06.2024:
- Kapitel 9: Module in Prolog (Kurze Einführung)
(Folie 9-1 bis 9-16)
Gründe für Module. Exkurs zum ISO Standard für Prolog. Diskussion zur Portabilität des Modul-Konstruktes. Module sind Namensraum für Prädikate, nicht für Konstanten und Funktionssymbole. module, use_module. Spezielle Module system und user. Direkter Zugriff auf Prädikate anderer Module (auch nicht exportierter Prädikate) mit modul:pred. Probleme bei Meta-Prädikate, meta_predicate Deklaration. Module und Operatoren. - Kapitel 10: Minimales Model
(Folie 10-1 bis 10-34)
Kurze Wiederholung zu logischen Programmen, Regeln, Fakten. EDB und IDB-Prädikate. Wiederholung zu Herbrand-Interpretationen (Herbrand-Universum, Herbrand-Basis, Identifikation einer Herbrand-Interpretation mit einer Teilmenge der Herbrand-Basis). Beispiele für Nicht-minimale Modelle. Minimales Herbrandmodell. Existenz und Eindeutigkeit des minimalen Modells (mit Beweis). Beziehung des minimalen Modells zur logischen Folgerung. Tp-Operator (direkte Konsequenzen aus einer gegebenen Menge von Fakten). Iteration des Tp-Operators zur Berechnung des minimalen Modells. - 11. Donnerstag, 20.06.2024:
- Kapitel 10: Minimales Model
(Folie 10-34 bis 10-47)
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. 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 11: Datalog mit eingebauten Prädikaten
(Folie 11-1 bis 11-24)
Bindungsmuster, Beziehung von Prädikaten mit Bindungsmustern zu klassischen Prozeduren, formale Behandlung von eingebauten Prädikaten. 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 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, 27.06.2024:
- 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, 04.07.2024:
- Kapitel 7: Magische Mengen
(Folie 7-1 bis 7-38)
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. - 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 |