Logische Programmierung und deduktive Datenbanken

(Sommersemester 2011)

Die Klausur findet am 22.09.2011, 10-12, statt (Raum wird noch bekanntgegeben). Beispiel für Klausur (aus WS 2003/04): [PDF] [ps]. Klausur von Herrn Dr. Thielemann aus dem Wintersemester 2009/10: [PDF]

Nützliche Quelle zur freiwilligen Weiterbildung über CLP: Books and Course Materials about ECLiPSe.

Prolog Programming Contests

Lernziele

Dies ist eine Spezialvorlesung zu meinem Haupt-Forschungsthema. Nach erfolgreicher Teilnahme an dieser Vorlesung sollten die Teilnehmenden Folgendes können:

Die logischen und konzeptuellen Grundlagen der logischen Programmierung erklären.
In der Sprache Prolog programmieren.
Mindestens ein ausgewähltes deduktives Datenbanksystem benutzen, d.h. insbesondere Anfragen und Sichtdefinitionen in der Sprache dieses Systems formulieren.
Die Ausführung von Programmen und Anfragen in Prolog bzw. deduktiven Datenbanken erklären und ggf. selbst Teile eines logischen Programmiersystems entwicklen.
Durch diese andere Art von Programmierung und Datenbank-Abfragen auch klassische Programmierung und Datenbank-Sprachen besser verstehen.

Geplante Inhalte sind (vorläufige Planung):

Einleitung (Motivation, Beispiele, 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, Warren Abstract Machine (sehr kurz)
Praktische Prolog-Programmierung
Anfrage-Auswertung II: Magische Mengen
Nichtmonotone Negation
Ausblick (z.B. Integritätsüberwachung, Constraint Logic Programming, neuere logische Programmiersprachen).

Dozent

Dr. Stefan Brass

Büro:: Raum 313 (Institut für Informatik, Von-Seckendorff-Platz 1)
Sprechstunde:: Dienstags, 12:00-13:00 (und nach Vereinbarung)
Email:: brass@informatik.uni-halle.de
Telefon:: 0345/55-24740
Fax:: 0345/55-27333 (im Sekretariat)
Sekretariat:: Frau Vahrenhold, Telefon 0345/55-24750, Zimmer 324

Termine

Vorlesung:

Donnerstags, 10:15-11:55 (mit 10min Pause), Raum 3.31, Informatikgebäude (Von-Seckendorff-Platz 1)

Übung:

Donnerstags, 14:15-15:45, Seminarraum 1.03 (Von-Seckendorff-Platz 1) oder PC-Pool (Raum 3.32)
Der PC-Pool ist auch in der Zeit 12-14 für uns reserviert.

Leistungspunkte und zeitliche Belastung:

Diese Veranstaltung hat 5 Leistungspunkte, das entspricht einem durchschnittlichen studentischen Arbeitsaufwand von 150 Stunden. Diese Zeit verteilt sich ungefähr wie folgt auf verschiedene Modulbestandteile:

Lehr- und Lernformen	SWS	Studentische Arbeitszeit
Vorlesung	2	30
Selbststudium (Lesen von Literatur)	0	45
Tafelübung	1	15
Praktische Übung	1	15
Lösen von Hausaufgaben	0	30
Spezielle Prüfungsvorbereitung	0	15

Vorlesungs-Materialien

Folien:

Die Folien werden jeweils vor der Vorlesung hier ins Netz gestellt (leichte Verbesserungen/Korrekturen sind auch noch möglich, nachdem die Folien schon ins Netz gestellt wurden).

0. Informationen zur Vorlesung (32 Folien)
[PDF]
1. Einführung (wird noch aktualisiert)
[PDF] [ps, verkleinert]
2. Basic Notions of Predicate Logic (73 Folien)
[PDF] [ps, verkleinert]
3. Pure Prolog (148 Folien)
[PDF] [ps, verkleinert]
4. Builtin Predicates (82 Folien)
[PDF] [ps, verkleinert]
5. Practical Prolog Programming (80 Folien)
[PDF] [ps, verkleinert]
6. Bottom-Up Evaluation (79 Folien)
[PDF] [ps, verkleinert]
7. Magic Sets (105 Folien)
[PDF] [ps, verkleinert]
8. Negation (48 Folien) [IN ARBEIT]
[PDF] [ps, verkleinert] [Vortrag zur WFS (PDF)]
9. Constraint Logic Programming (19 Folien)
[PDF] [ps, verkleinert]
Vorlesungsmaterialien von 2007

Übungsblätter:

0. Präsenzübung am 14.04.2011: Benutzung von Prolog
[PDF] [ps, verkleinert] [Familien-DB als Prolog-Fakten]
1. Hausaufgabe zum 21.04.2011: Datenbank-Abfragen in Prolog
[PDF] [ps, verkleinert] [CD-Datenbank als Prolog-Fakten]
2. Hausaufgabe zum 28.04.2011: Mathematiker-Stammbaum
[PDF] [ps, verkleinert] [doctorate.facts] [advisor.facts]
3. Hausaufgabe zum 05.05.2011: Listen in Prolog
[PDF] [ps]
4. Hausaufgabe zum 12.05.2011: Operatordeklarationen, Aussagenlogischer Modellprüfer
[PDF] [ps]
5. Hausaufgabe zum 26.05.2011: T_P-Operator, Unifikation
[PDF] [ps]
6. Hausaufgabe zum 09.06.2011: Typprüfer
[PDF] [ps]
7. Präsenzaufgabe: Benutzung von CORAL
[PDF] [ps] [cd.F] [Homepage von CORAL] [Artikel über CORAL]
8. Bitte lesen (mindestens einen Artikel, ggf. hintere Teile nur überfliegen):
     [Introduction to Deductive Database Languages and Systems]
     [CORAL]
     [CORAL++]
     [Aditi]
     [Glue-Nail]
     [Declare and SDS]
     [LDL]
     [XSB]
...
...
...
...

Hinweis:

Postscript-Dateien können mit Aladdin Ghostscript angezeigt und ausgedruckt werden. Teurere Laserdrucker haben einen Postscript-Interpreter eingebaut. PDF-Dateien können mit dem Acrobat Reader angezeigt und gedruckt werden.

Hausaufgaben / Übungen (Modulvorleistung)

Um zur Prüfung (mündliche Prüfung) zugelassen zu werden, müssen Sie zwei Voraussetzungen erfüllen:
- Sie müssen in den Hausaufgaben mindestens 50% der Punkte erreichen. Die Hausaufgaben sind einzeln zu bearbeiten (keine Gruppenarbeit). Sie müssen Ihre Abgaben in den Übungen erklären können, und auch Fragen zum Umfeld der Aufgabe beantworten können.
- Sie müssen regelmässig an den Übungen teilnehmen und sich aktiv beteiligen. Sie dürfen drei Mal fehlen, darüber hinaus nur nach Rücksprache mit dem Dozenten.
Daneben muß man sich natürlich zu Modul und zur Modulleistung (Prüfung) korrekt anmelden.
In Einzelfällen (begründete Ausnahmen) kann der Dozent ein Projekt mit Verteidigung als Alternative anbieten.
Plagiate sind kein Kavaliersdelikt! Das Abschreiben von Hausaufgaben kann ernste Folgen haben (minimal 0 Punkte für alle Beteiligten bei zu ähnlichen Lösungen, in schlimmeren Fällen ist aber z.B. auch ein Ausschluss von der Prüfung möglich). Es ist selbstverständlich auch ein Plagiat, wenn Sie eine eventuell im Web gefundene Lösung ohne Quellenhinweis abgeben. Mit Quellenhinweis ist es kein Plagiat, aber ich werde Sie dann extrem gründlich nach der genauen Funktionsweise befragen.

Prüfung (Modulleistung)

Die Prüfung findet voraussichtlich als mündliche Prüfung statt (es sei denn, es würde sehr viele Teilnehmer geben).
Prüfungstermine werden noch bekanntgegeben. In Ausnahmefällen ist eventuell auch ein individueller Termin möglich (nach Rücksprache mit dem Dozenten).
Man kann sich zur Prüfung nur anmelden, wenn man die Modulvorleistung erbracht hat (s.o.)

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.

Literatur (Lehrbücher)

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. Taschenbuch: ISBN 0262691639, 50.99 Euro.
Hardcover: ISBN 0262193388.
[Amazon-Seite (Taschenbuch)] [Amazon-Seite (Hardcover)]
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]
Krzysztof R. Apt, Mark G. Wallace:
Constraint Logic Programming using ECLiPSe.
Cambridge University Press, 2007, 348 Seiten, ISBN 0-521-86628-6, 52.22 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]

Software

SWI-Prolog
[http://www.swi-prolog.org/]
GNU Prolog
[http://gnu-prolog.inria.fr/]
The Ciao Prolog System
[http://clip.dia.fi.upm.es/~clip/Software/Ciao/]
ECLiPSe Constraint Logic Programming System
[http://eclipse.crosscoreop.com/eclipse/]
[http://www.clps.de/]
B-Prolog
[http://www.probp.com/]
SICStus Prolog
         [http://www.sics.se/sicstus/] (Homepage)
         [http://www.sics.se/sicstus/docs/3.7.1/html/sicstus_toc.html] (User Manual)
         [http://www.sics.se/isl/sicstuswww/site/links.html] (Useful Links)
Visual Prolog
[http://www.visual-prolog.com/]
[http://www.pdc.dk/Default.htm] (PDC: Prolog Development Center)
Coral Deductive Database
         [http://www.cs.wisc.edu/coral/]
         [http://se.aminet.net/pub/databases/deductive/coral/
         [http://se.aminet.net/pub/databases/object-oriented/exodus/
The Aditi Deductive Database
[http://www.cs.mu.oz.au/research/aditi/]
The Deductive Database System LDL++
         [http://wis.cs.ucla.edu/ldl/]
         [http://www.cs.ucla.edu/~zaniolo/papers/tplp02.pdf] (Neuerer Artikel über LDL++)
         [http://www.cs.ucla.edu/ldl/] (LDL Java Interface)
[http://www.cs.uwyo.edu/~ruben/research/pdf/guide.pdf] (SALAD User Guide - Implementierung von LDL)
The LOLA Project, Implementation of a Deductive Database System
[http://www.im.uni-passau.de/projekte/lola.html]
The Mercury Project
[http://www.cs.mu.oz.au/research/mercury/]
The Mozart Programming System
[http://www.mozart-oz.org/]
XSB
[http://xsb.sourceforge.net/]
Flora-2
[http://flora.sourceforge.net/]
FLORID/FloXML
[http://www.informatik.uni-freiburg.de/~dbis/florid/]
[http://www.semwebtech.org/domains/test/DLFlorid/] (Online Demo)
Xcerpt
[http://www.xcerpt.org/]
ROCK&ROLL: Deductive Object Oriented Database System
[http://www.cee.hw.ac.uk/Databases/rnr.html]
ConceptBase: A Deductive Object Manager for Meta Databases
[http://www-i5.informatik.rwth-aachen.de/CBdoc/]
The Goedel Programming Language
[http://www.cs.bris.ac.uk/~bowers/goedel.html]
The Prolog ISO Standard Documents
[http://pauillac.inria.fr/~deransar/prolog/docs.html]
A Java Deductive Reasoning Engine for the Web
[http://www.jdrew.org/jDREWebsite/jDREW.html]
Datalog Educational System 1.7.0
[http://www.softpedia.com/get/Others/Home-Education/Datalog-Educational-System.shtml]
[http://www.fdi.ucm.es/profesor/fernan/des/]
Lightwight Deductive Database System (MITRE Corporation)
[http://www.ccs.neu.edu/home/ramsdell/tools/datalog/]
IRIS - Integrated Rule Inference System
[http://iris-reasoner.org/]
bbdbddb - BDD-Based Deductive DataBase
[http://bddbddb.sourceforge.net/]

Andere Kurse, Tutorials (im Aufbau)

Literatur im WWW (Web-Links)

Dieser Abschnitt ist noch im Aufbau. Bitte schicken Sie mir eine EMail, wenn Sie Webseiten zum Thema der Vorlesung empfehlen möchten.

Wikipedia: Prolog (deutsch)
[http://de.wikipedia.org/wiki/Prolog_(Programmiersprache)]
Wikipedia: Prolog (englisch)
[http://en.wikipedia.org/wiki/Prolog]
Wikipedia: Datalog (deutsch)
[http://de.wikipedia.org/wiki/Datalog]
Wikipedia: Datalog (englisch)
[http://en.wikipedia.org/wiki/Datalog]
Wikipedia: Logische Programmierung (deutsch, sehr kurz)
[http://de.wikipedia.org/wiki/Logische_Programmierung]
Wikipedia: Logic Programming (englisch)
[http://en.wikipedia.org/wiki/Logic_programming]
Wikipedia: Constraint Logic Programming (englisch)
[http://en.wikipedia.org/wiki/Constraint_logic_programming]
Wikipedia: Answer Set Programming (englisch)
[http://en.wikipedia.org/wiki/Answer_set_programming]
Wikipedia: Comparison of Prolog implementations (englisch)
[http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations]
Wikipedia: SWI-Prolog (englisch)
[http://en.wikipedia.org/wiki/SWI-Prolog]
Wikipedia: ECLiPSe (englisch)
[http://en.wikipedia.org/wiki/ECLiPSe]
Wikipedia: BProlog (englisch)
[http://en.wikipedia.org/wiki/BProlog]
Wikipedia: GNU Prolog (englisch)
[http://en.wikipedia.org/wiki/GNU_Prolog]
Wikipedia: Warren Abstract Machine (WAM) (englisch)
[http://en.wikipedia.org/wiki/Warren_abstract_machine]
Wikipedia: Visual Prolog (englisch)
[http://en.wikipedia.org/wiki/Visual_Prolog]
Wikipedia: Mercury (englisch)
[http://en.wikipedia.org/wiki/Mercury_(programming_language)]
Wikipedia: Logtalk (englisch)
[http://en.wikipedia.org/wiki/Logtalk]
Overview of Prolog Systems (von Ulrich Neumerkel)
[http://www.complang.tuwien.ac.at/ulrich/prolog_misc/systems.html]
Linksammlung zu Logikorientierten Programmiersprachen (von Ulrich Neumerkel)
[http://www.complang.tuwien.ac.at/ulrich/prolog_misc/]
Prolog++ Toolkit
[http://www.lpa.co.uk/ppp_det.htm]
...

Stefan Brass (brass@informatik.uni-halle.de), 01. März 2011

Original URL: http://www.informatik.uni-halle.de/~brass/lp11/ [XHTML 1.0 geprüft] [CSS geprüft] [Links Geprüft]