[Themen]      [Dozent]      [Termine]      [Materialien]      [Übung]      [Ablauf]      [Punkte-DB]      [Literatur]      [Software]      [StudIP]

 

MARTIN-LUTHER-UNIVERSITÄT HALLE-WITTENBERG
Institut für Informatik
Prof. Dr. Stefan Brass

Deduktive Datenbanken und Logische Programmierung

(Winter 2009/2010)

 

Geplante Themen

 

Termine

Vorlesung:

Theoretische Übung und Praktische Übung am Rechner:

 

Dozent

Dr. Henning Thielemann

Büro:
Raum 314 (Institut für Informatik, Von-Seckendorff-Platz 1)
Sprechstunde:
Nach Vereinbarung.
Email:
prolog2009@henning-thielemann.de
Telefon:
0345/55-24773 (Büro)
Fax:
0345/55-27333 (im Sekretariat)
Sekretariat:
Frau Vahrenhold, Telefon 0345/55-24750, Zimmer 324

 

Übungsleiter

Dipl.-Inform. Martin Herzberg

Büro:
Raum 315 (Institut für Informatik, Von-Seckendorff-Platz 1)
Sprechstunde:
Nach Vereinbarung.
Email:
lp09@informatik.uni-halle.de
Telefon:
0345/55-24737

 

Vorlesungsmaterialien

Folien

Die Vorlesungsmaterialien werden hier ins Internet gestellt, sobald sie fertig sind.

Folien der Vorlesung `Deduktive Datenbanken' von Prof. Brass im Sommer 1998: [Homepage der Vorlesung]

Folien der Vorlesung `Logische Programmierung' von Prof. Brass vom WS 1993/94:

     (Die Folien lagen in einer nicht mehr unterstützten LaTeX-Version vor. Es gibt daher kleinere Abweichungen von den Originalen.)

  1. Vorbemerkungen:
                [Postscript]   [PDF]
  2. Prolog in Beispielen:
                [Postscript]   [PDF]
  3. Prolog Syntax:
                [Postscript]   [PDF]
  4. Prolog Ausführung:
                [Postscript]   [PDF]
  5. Eingebaute Prädikate:
                [Postscript]   [PDF]
  6. Prolog vs. Pascal:
                [Postscript]   [PDF]
  7. Deklarative Semantik:
                [Postscript]   [PDF]
  8. Korrektheit und Vollständigkeit der SLD-Resolution:
                [Postscript]   [PDF]
  9. Negation as Failure:
                [Postscript]   [PDF]
  10. Standard-Algorithmen:
                [Postscript]   [PDF]
  11. Programmierstil:
                [Postscript]   [PDF]
  12. Grammatiken in Prolog:
                [Postscript]   [PDF]
  13. Prolog Implementierung (Interpreter):
                [Postscript]   [PDF]
  14. Prolog Implementierung (Compiler):
                [Postscript]   [PDF]
  15. Zusammenfassung (Beispiele für Prüfungsfragen):
                [Postscript]   [PDF]

 

Übung (Hausaufgaben)

Nr. PDF Abgabe
01 PDF 2009-10-30 advisor.facts.bz2, doctorate.facts.bz2
02 PDF 2009-11-06
03 PDF 2009-11-13 cd.pro
04 PDF 2009-12-04
05 PDF 2009-12-04 Musterlösung 5 : Symbolisches Differenzieren
06 PDF 2009-12-18
07 PDF 2009-12-18
08 PDF 2009-12-18
09 PDF 2010-01-15 Musterlösung 9 : Range Restriction
10 PDF 2010-01-15 Musterlösung 10.1 a : Cut
11 PDF 2010-01-22 mass_spectrum_facts.pro | Musterlösung 11 a : Parser
12 PDF 2010-01-29

 

Software-Links

 

Andere Kurse, Tutorials (im Aufbau)

 

Voraussetzungen zur Teilnahme

 

Übungsscheine

Bei Interesse besteht die Möglichkeit zum Erwerb eines Übungsscheins. Die genauen Modalitäten hängen von der Anzahl der Interessenten ab und werden in der Vorlesung bekanntgegeben. Voraussichtlich wird es Hausaufgaben und ein oder zwei Klausuren geben.

 

Punkte-Datenbank

Es wird die Möglicht geben, Ihren Punktestand für Hausaufgaben und Klausur online abzufragen. Sie müssen sich dazu in der ersten Semesterwoche als Benutzer der Datenbank registrieren. Wenn Sie von dieser Möglichkeit keinen Gebrauch machen wollen, melden Sie sich bitte beim Dozenten, da sich sonst jemand anderes unter Ihrem Namen registrieren kann. Achten Sie bitte auf weitere Ansagen in der Vorlesung.

 

Ablauf

1. (09.10.2009):
Kapitel 1: Einführung (Folie 1-1 bis 1-37)
Motivation für deduktive Datenbanken, Einordnung des Gebietes, EDB vs. IDB, Beispiele für Regeln, Begriffe Regelkopf und Regelrumpf, Kopfliteral, Rumpfliteral, Regel über ein Prädikat, Beispiel für mehrere Regeln über ein Prädikat
2. (16.10.2009):
Kapitel 1: Einführung (Folie 1-38 bis 1-63)
Beispiel für rekursive Regeln, Vergleich mit Rekursion in SQL-92. Datalog vs. Prolog, Anonyme Variablen, Benutzung eines Prolog-Systems, Aufgaben: Formulierung von Anfragen an EMP/DEPT in Prolog und SQL,
3. (23.10.2009):
Kapitel 1: Einführung (Folie 1-64 bis 1-88)
Deduktive Datenbank als integriertes System aus DBMS und Programmiersprache, Stärken deduktiver Datenbanken, Geschichte des Gebiets, Probleme, zukünftige Hoffnungen
Kapitel 2: Basic Notions of Predicate Logic (Folie 2-1 bis 2-35)
Signatur, Interpretation, Variablendeklaration, Variablenbelegung, Term, Formel, freie Variablen, geschlossene Formel, Grundterm, Grundformel, Wert eines Terms, Gültigkeit einer Formel, Modell
4. (30.10.2009):
Kapitel 2: Basic Notions of Predicate Logic (Folie 2-36 bis 2-67)
konsistent, logische Folgerung, Tautologie, bereichsunabhängig, bereichsbeschränkt, äuivalent, bekannte äquivalenzen, Substitutionen, Grundsubstitution, Normalformen, Literale, Klauseln, Skolemnisierung
5. (06.11.2009):
Kapitel 2: Basic Notions of Predicate Logic (Folie 2-68 bis 2-71)
Herbrand-Interpretationen, Beweis durch Widerspruch mit Umwandlung in Klauselmenge und ausschließlicher Betrachtung von Herbrand-Interpretationen
Kapitel 3: Pure Prolog (Folie 3-1 bis 3-41)
Prolog als automatischer Beweiser, Prolog-Syntax, Operator-Syntax, Listen-Syntax
6. (13.11.2009):
Kapitel 3: Pure Prolog (Folie 3-42 bis 3-51)
Komplizierteres Beispiel (Rätsel vom Fährmann); Wegen Krankheit verschoben
6a. (20.11.2009):
Kapitel 3: Pure Prolog (Folie 3-52 bis 3-82)
unterschiedliche Denkweise/Formulierung in deduktiven Datenbanken und in Prolog (bottom-up vs. top-down), Wiederholung zu logischen Programmen, Herbrand-Interpretationen, Minimales Modell, Substitutionen, Grundinstanzen, T_P-Operator (direkte Konsequenzen), Berechnung des minimalen Modells durch Iteration des T_P-Operators (kleinster Fixpunkt),
7. (27.11.2009):
Kapitel 3: Pure Prolog (Folie 3-92 bis 3-136)
Supported Models, Unifikation, Occur Check Resolution (Resolventenmethode zum automatischen Beweisen), SLD-Resolution, Selektionsfunktion, SLD-Ableitungsschritt, SLD-Ableitung, Berechnete Antwort-Substitution, Korrektheit und Vollständigkeit der SLD-Resolution, Einschränkungen bei Prolog, SLD-Baum, Unendliche Pfade
8. (04.12.2009):
Einschub: Unification in Hindley-Milney-Typsystemen (wie in Haskell)
Kapitel 3: Pure Prolog (Folie 3-137 bis 3-148)
Debugger und Modell der Bausteine mit vier Anschlüssen
Kapitel 4: Eingebaute Prädikate (Folie 4-1 bis 4-14)
Motivation, Probleme mit eingebauten Prädikaten, Bindungsmuster
9. (04.12.2009):
Kapitel 4: Eingebaute Prädikate (Folie 4-15 bis 4-70)
gültige Bindungsmuster, Beispiele für eingebaute Prädikate: Termklassifikation und -manipulation, Arithmetik, Texte, Implementierung von Funktionen als Prädikate, zur Laufzeit erstellte Beweisziele, zur Laufzeit geänderte Prädikate, Extension eines Prädikates zur Laufzeit ermitteln, Ein-/Ausgabe, Programmflusssteuerung, Dokumentationskonventionen, Bereichsbeschränkungen für deduktive Datenbanken
10. (11.12.2009):
Kapitel 4: Eingebaute Prädikate (Folie 4-71 bis 4-82)
Bereichsbeschränkung, Konstruktoren als Prädikate schreiben, was wäre wenn es echte Funktionen gäbe?
Kapitel 5: Praktische PROLOG-Programmierung (Folie 5-1 bis 5-32)
Cut: Funktionsweise und Anwendungen, Anwendungen: Geschwindigkeitssteigerung, reduzierter Speicherverbrauch, Kontrollstrukturen: If-Then-Else, Negation, Beschränkung auf eine einzige Lösung, Gefahren, Kategorisierung
11. (18.12.2009):
Kapitel 5: Praktische PROLOG-Programmierung (Folie 5-33 bis 5-68)
PROLOG vs. Pascal: Datentypen, veränderliche Objekte vs. Zustandsfreiheit, Programmfluss: If-Then, Switch, Schleifen, Endrekursion,
Parser: Grammatiken
12. (15.01.2010):
Kapitel 6: Bottom-Up Evaluation (Folie 6-1 bis 6-52)
Ziel der Bottom-Up Auswertung, Grundsätzliche Methode, Unterscheidung von EDB- und IDB-Prädikaten, Prädikat-Abhängigkeitsgraph, rekursive Prädikate, rekursive Cliquen, rekursive Regeln, reduzierter Prädikat-Abhängigkeitsgraph, Auswertungsreihenfolge für die Prädikate, Übersetzung von Regeln in Relationenalgebra/SQL/Programmcode, Anfrageoptimierung, Unfolding/Inlining (Ersetzung von Prädikat-Aufruf durch Regelrumpf), Vermeidung der Materialisierung von IDB-Prädikaten (Vor- und Nachteile), Einfacher Compiler von Datalog in SQL/Relationenalgebra/C plus Kontrollstrukturen.
13. (22.01.2010):
Kapitel 6: Bottom-Up Evaluation (Folie 6-53 bis 6-79)
Seminaive Auswertung, Datenstruktur für mehrere Varianten einer Relation bei seminaiver Iteration, Diskussion über Vor- und Nachteile der Verwendung eines kommerziellen SQL-DBMS als Grundlage, weitere Optimierungen
Kapitel 7: Magic Sets (Folie 7-1 bis 7-32)
Motivation, Einordnung, Erläterung der Methode am Beispiel, Korrektheitsaussage, Bedeutung "Magische Menge", Sideways-Information-Passing-Strategien
14. (29.01.2010):
Kapitel 7: Magic Sets (Folie 7-33 bis 7-48)
Verzierte Programme, Magische-Mengen-Transformation, Informationsfluss in transformiertem Programm, Korrektheit

Lehrevaluation: Ergebnis vom 2010-01-15.

 

Literatur

Lehrbücher:

Übersichtsartikel (online verfügbar, alphabetisch):

 

Weitere Informationsquellen im WWW

Weitere Informationsquellen:

Stefan Brass (brass@acm.org), Henning Thielemann (prolog2009@henning-thielemann.de), 28. September 2009

Original-URL: http://dbs.informatik.uni-halle.de/Lehre/LP09/   [HTML 3.2 Checked]   [Links Geprüft]