[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 2007/2008)

Aufgrund eines Terminkonflikts beginnt die Vorlesung schon um 10:00 und endet um 12:00. Die fehlende Viertelstunde summiert sich im Laufe des Semesters auf knapp 4 Stunden auf, diese Zeit wird voraussichtlich am 11. Februar, 9:00-13:00, Raum 3.31, als Blockveranstaltung nachgeholt.

Am 31. Januar, 12-14, wird Herr Steffen Klehr von der GISA eine Gastvorlesung u.a. zu folgenden Themen halten:

Herr Kleer hat in Halle studiert, war dann SAP-Basisberater und ist seit 7 Jahren Datenbankadministrator. Es ist sehr erfreulich, daß wir so die Gelegenheit bekommen, etwas über den wirklichen Praxiseinsatz von Datenbanken zu erfahren. Bitte nutzen Sie diese Gelegenheit und bringen Sie möglichst viele Ihrer Mitstudenten mit.

Die Vorbesprechung der Arbeitsgemeinschaft zur Vorbereitung auf eine Datenbank-Zertifizierung ist für Freitag, 8. Februar, 10:15-11:45, Raum 1.30 geplant. Bitte achten Sie auf weitere Ankündigungen. Falls ausreichend viele Teilnehmer zusammen kommen, wird die IBM-Zertifizierung hier an der Uni möglich sein.

 


Geplante Themen


 


Termine


Vorlesung:

Theoretische Übung und Praktische Übung am Rechner:

 


Dozent


Prof. Dr. Stefan Brass

Büro:
Raum 313 (Institut für Informatik, Von-Seckendorff-Platz 1)
Sprechstunde:
Nach Vereinbarung.
Email:
brass@acm.org
Telefon:
0345/55-24740 (Büro)
Fax:
0345/55-27333 (im Sekretariat)
Sekretariat:
Frau Vahrenhold, Telefon 0345/55-24750, Zimmer 324

 


Übungsleiter


Dr. Henning Thielemann

Büro:
Raum 314 (Institut für Informatik, Von-Seckendorff-Platz 1)
Sprechstunde:
Nach Vereinbarung.
Email:
prolog2007@henning-thielemann.de
Telefon:
0345/55-24773

 


Vorlesungsmaterialien


Folien

Die Vorlesungsmaterialien werden hier ins Internet gestellt, sobald sie fertig sind. Die mit [ALT] markierten Folien sind von 2006 und werden voraussichtlich noch überarbeitet.

Folien meiner Vorlesung `Deduktive Datenbanken' im Sommer 1998: [Homepage der Vorlesung]

Folien meiner Vorlesung `Logische Programmierung' 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 PostScript Abgabe
01 PDF PS 2007-10-22 advisor.facts.bz2, doctorate.facts.bz2
02 PDF PS 2007-10-29
03 PDF PS 2007-11-05 cd.pro
04 PDF PS 2007-11-12
05 PDF PS 2007-11-19
06 PDF PS 2007-11-26
07 PDF PS 2007-12-03
08 PDF PS 2007-12-10
09 PDF PS 2007-12-17
10 PDF PS 2008-01-07
11 PDF PS 2008-01-14 mass_spectrum_facts.pro
12 PDF PS 2008-01-21
13 PDF PS 2008-02-11

 


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.2007):
Kapitel 0: Informationen zur Vorlesung / Organisatorisches (Folie 0-1 bis 0-29)
Kapitel 1: Einführung (Folie 1-1 bis 1-44)
Motiation 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, Beispiel für rekursive Regeln, Vergleich mit Rekursion in SQL-92.
2. (16.10.2007):
Kapitel 1: Einführung (Folie 1-42 bis 1-85)
Datalog vs. Prolog, Anonyme Variablen, Benutzung eines Prolog-Systems, Aufgaben: Formulierung von Anfragen an EMP/DEPT in Prolog und SQL, Deduktive Datenbank als integriertes System aus DBMS und Programmiersprache, Stärken deduktiver Datenbanken, Geschichte des Gebiets, Probleme, zukünftige Hoffnungen
3. (23.10.2007):
Kapitel 2: Basic Notions of Predicate Logic (Folie 2-1 bis 2-58)
Signatur, Interpretation, Variablendeklaration, Variablenbelegung, Term, Formel, freie Variablen, geschlossene Formel, Grundterm, Grundformel, Wert eines Terms, Gültigkeit einer Formel, konsistent, logische Folgerung, Tautologie, bereichsunabhängig, bereichsbeschränkt, äuivalent, bekannte äquivalenzen, Substitutionen, Grundsubstitution, Normalformen
4. (30.10.2007):
Kapitel 2: Basic Notions of Predicate Logic (Folie 2-59 bis 2-73)
Literale, Klauseln, Skolemnisierung, Herbrand-Interpretationen, Beweis durch Widerspruch mit Umwandlung in Klauselmenge und ausschliesslicher Betrachtung von Herbrand-Interpretationen
Kapitel 3: Pure Prolog (Folie 3-1 bis 3-41)
Prolog als automatischer Beweiser, Prolog Syntax, Operator Syntax, Listen Syntax
5. (06.11.2007):
Kapitel 3: Pure Prolog (Folie 3-42 bis 3-78, 3-81)
Komplizierteres Beispiel (Rätsel vom Fährmann), 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)
6. (13.11.2007):
Kapitel 3: Pure Prolog (Folie 3-78 bis 3-105)
T_P-Operator, etwas Verbandstheorie (mit Beweis des Satzes auf Folie 3-88: Existenz des kleinsten Fixpunktes), Berechnung des minimalen Modells durch Iteration des T_P-Operators (kleinster Fixpunkt), Ausblick auf seminaive Bottom-Up Auswertung, Supported Models, Unifikation, Occur Check
7. (20.11.2007):
Kapitel 3: Pure Prolog (Folie 3-106 bis 3-136)
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
Kapitel 4: Eingebaute Prädikate (Folie 4-1 bis 407)
Motivation, Probleme mit eingebauten Prädikaten
8. (27.11.2007):
9. (24.12.2007):
10. (11.12.2007):
11. (18.12.2007):
12. (08.01.2008):
Kapitel 6: Bottom-Up Evaluation (Folie 6-1 bis 6-44)
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 (Ersetzung von Prädikat-Aufruf durch Regelrumpf), Vermeidung der Materialisierung von IDB-Prädikaten (Vor- und Nachteile).
13. (16.01.2008):
Kapitel 6: Bottom-Up Evaluation (Folie 6-45 bis 6-79)
Einfacher Compiler von Datalog in SQL/Relationenalgebra/C plus Kontrollstrukturen, 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-19)
Motivation, Einordnung, Erläterung der Methode am Beispiel, Korrektheitsaussage
...

 


Literatur


Lehrbücher:

Übersichtsartikel (online verfügbar, alphabetisch):

 


Weitere Informationsquellen im WWW


Weitere Informationsquellen:


Stefan Brass (brass@acm.org), 27. Juli 2007

Original URL: http://www.informatik.uni-halle.de/~brass/lp07/   [HTML 3.2 Checked]   [Links Geprüft]