[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:
- Datensicherung (Konzept mit OSL, ASM)
- Hochverfügbarkeit (RAC, Standby)
- Datenschutz und Security (VPD)
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
- Einleitung (Motivation, Historische Entwicklung, Einordnung)
- Logische Grundlagen:
Horn-Klauseln, Herbrand Modelle, Minimales Modell
- Datenbank-Anfragen und Programmierung in Datalog
- Eingebaute Prädikate
- Anfrage-Auswertung I: Naiv, Seminaiv
- Pure Prolog (mit Funktionssymbolen)
- Programm-Ausführung: SLD-Resolution,
eventuell kurze Einführung in die Warren Abstract Machine (WAM)
- Praktische Prolog-Programmierung
- Anfrage-Auswertung II: Magische Mengen
- Nichtmonotone Negation
- Eventuell Integritätsüberwachung.
- Eventuell Constraint Logic Programming.
- Ausblick auf neuere logische Programmiersprachen
Termine
Vorlesung:
- Dienstags, 10:15-12:45 (3 Stunden), Raum 3.31 (Von-Seckendorff-Platz 1)
Theoretische Übung und
Praktische Übung am Rechner:
- Montags, 10:15-11:45, Seminarraum 1.16 (Von-Seckendorff-Platz 1)
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.
- 0. Informationen zur Vorlesung (29 Folien)
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 1. Introduction (85 Folien) [wird noch modifiziert]
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
[family.pro]
- 2. Basic Notions of Predicate Logic (73 Folien) [ALT]
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 3. Pure Prolog (146 Folien) [ALT]
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 4. Built-In Predicates (82 Folien) [ALT]
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 5. Practical Prolog programming (80 Folien)
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 6. Bottom-Up Evaluation (79 Folien)
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 7. Magic Sets (105 Folien)
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- 8. Negation (48 Folien) [IN ARBEIT]
[Postscript, S/W, verkleinert]
[PDF, farbig, gross]
- Funktional-logische Programmierung mit Mercury
[PDF, farbig, gross]
- ...
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.)
- Vorbemerkungen:
[Postscript]
[PDF]
- Prolog in Beispielen:
[Postscript]
[PDF]
- Prolog Syntax:
[Postscript]
[PDF]
- Prolog Ausführung:
[Postscript]
[PDF]
- Eingebaute Prädikate:
[Postscript]
[PDF]
- Prolog vs. Pascal:
[Postscript]
[PDF]
- Deklarative Semantik:
[Postscript]
[PDF]
- Korrektheit und Vollständigkeit der SLD-Resolution:
[Postscript]
[PDF]
- Negation as Failure:
[Postscript]
[PDF]
- Standard-Algorithmen:
[Postscript]
[PDF]
- Programmierstil:
[Postscript]
[PDF]
- Grammatiken in Prolog:
[Postscript]
[PDF]
- Prolog Implementierung (Interpreter):
[Postscript]
[PDF]
- Prolog Implementierung (Compiler):
[Postscript]
[PDF]
- Zusammenfassung (Beispiele für Prüfungsfragen):
[Postscript]
[PDF]
Übung (Hausaufgaben)
Software-Links
Andere Kurse, Tutorials (im Aufbau)
Voraussetzungen zur Teilnahme
- Vorlesung Datenbanken I, inklusive des Kapitels über Logik.
- Programmierkenntnisse.
Ü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:
- William F. Clocksin, Christopher S. Mellish:
Programming in Prolog. Using the ISO Standard.
Springer, 2003, 5th Ed., 299 Seiten, ISBN 3540006788,
37.40 Euro
[Amazon-Seite]
- William F. Clocksin:
Clause and Effect. Prolog for the Working Programmer.
Springer, 1997, ISBN 3540629718, 143 Seiten, 32.05 Euro.
[Amazon-Seite]
- Leon Sterling, Ehud Shapiro:
The Art of Prolog. Advanced Programming Techniques.
MIT Press, 1994, 2nd Ed., 560 Seiten, ISBN 0262193388,
78.90 Euro.
Taschenbuch: ISBN 0262691639, 59.90 Euro.
[Amazon-Seite (Hardcover)]
[Amazon-Seite (Taschenbuch)]
- Ulf Nilson, Jan Maluszynski:
Logic, Programming, and Prolog (2nd Ed.).
John Wiley, 1995, vom Verlag nicht mehr erhältlich, dafür online.
[http://www.ida.liu.se/~ulfni/lpp]
- Pierre Deransart, AbdelAli Ed-Dbali, Laurent Cervoni:
Prolog: The Standard. Reference Manual
Springer, 1996, 272 Seiten, ISBN 3540593047, 58.80 Euro.
[Amazon-Seite]
- Stefano Ceri, Georg Gottlob, Letizia Tanca:
Logic Programming and Databases.
Springer, 1990, 284 Seiten, ISBN 3540517286, nur noch gebraucht.
[Amazon-Seite]
- Armin B. Cremers, Ulrike Griefahn, Ralf Hinze:
Deduktive Datenbanken.
Vieweg, 1994, 463 Seiten, ISBN 3528047003, nur noch gebraucht.
[Amazon-Seite]
- Robert M. Colomb:
Deductive Databases and Their Applications.
Taylor&Francis Group,
1998, 288 Seiten, ISBN 0748407979, 52.86 Euro.
Gebundene Ausgabe: ISBN 0748407960.
[Amazon-Seite (Softcover)]
[Amazon-Seite (Hardcover)]
- Thom Frühwirth, Slim Abdennadher:
Constraint Programmierung. Grundlagen und Anwendungen.
Springer, 1997, 165 Seiten, ISBN 354060670X, 17.95 Euro.
[Amazon-Seite]
Übersichtsartikel
(online verfügbar, alphabetisch):
- Francois Bancilhon / Raghu Ramakrishnan:
An Amateur's Introduction to Recursive Query Processing Strategies.
Proc. ACM SIGMOD Int. Conf. on Management of Data, 1986,
16--51.
[Eintrag in der ACM Digital Library]
- François Bry / Dietmar Seipel:
Deduktive Datenbanken - das aktuelle Schlagwort.
Informatik Spektrum, Vol. 19, 1996, 214-215.
[Postscript-Datei]
- Stefano Ceri, Raghu Ramakrishnan:
Rules in Database Systems.
ACM Computing Surves, March 1996, Vol. 28, No. 1, 109-111.
[Eintrag in der ACM Digital Library]
- Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov:
Complexity and expressive power of logic programming.
ACM Computing Surves, Sep. 2001, Vol. 33, No. 3, 374-425.
[Eintrag in der ACM Digital Library]
- Herve Gallaire, Jack Minker, Jean-Marie Nicolas:
Logic and Databases: A Deductive Approach.
ACM Computing Surveys (CSUR), Volume 16, Issue 2, June 1984,
153 - 185.
[Eintrag in der ACM Digital Library]
- Mengchi Liu:
Deductive database languages: problems and solutions.
ACM Computing Surveys, March 1999, Vol. 31, No. 1, 27-62.
[Eintrag in der ACM Digital Library]
- John Grant / Jack Minker:
The Impact of Logic Programming on Databases.
Communications of the ACM 35 (3), March 1992, 67-81.
[Eintrag in der ACM Digital Library]
- Jack Minker:
Logic and Databases: A 20 Year Retrospective.
In: D. Pedreschi / C. Zaniolo (Ed.):
Logic in Databases, Int. Workshop (LID'96),
Springer LNCS 1154, 1996, 3--57.
[Webseite des Autors]
- Raghu Ramakrishnan / Jeffrey D. Ullman:
A Survey of Research in Deductive Database Systems.
The Journal of Logic Programming, Vol. 23, 1995, 125--149.
[Verfügbar auf dem Standord DB-PUBS Server]
- Kotagiri Ramamohanarao (Ed.):
Special Issue on Prototypes of Deductive Database Systems.
The VLDB Journal, Vol. 3, No. 2, 1994.
[Eintrag auf DBLP]
- Shalom Tsur:
Deductive Databases in Action.
Proc. 10th ACM SIGACT-SIGMOD-SIGART Symp. on
Principles of Database Systems (PODS'91), 1991, 205-218.
[Eintrag in der ACM Digital Library]
- Jeffrey D. Ullman, Carlo Zaniolo:
Deductive databases: achievements and future directions.
ACM SIGMOD Record, Volume 19, Issue 4, December 1990, 75-82.
[Eintrag in der ACM Digital Library]
- Laurent Vieille:
From Data Independence to Knowledge Independence:
An on-going Story.
VLDB'98, 650--654.
[PDF-Datei auf vldb.org]
- Amruth N. Kumar:
Prolog for imperative programmers.
Journal of Computing Sciences in Colleges,
Volume 17, Issue 6 (May 2002),
Pages: 167 - 181.
[Eintarg in der ACM Digital Library]
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]