Date and Time:

• Thursday 14-16 ct, MN28 (Chemistry building [im EG der anorganischen Chemie, das ist der mittlere der drei Chemie-Türme]; derselbe HS, wo auch "Datenbanken" stattgefunden hat).
• Friday 10-12 ct, HS2, A0.102, Physik "Max Born-Hörsaal".

Lecture and Exercises mixed (see announcements on this page)

Module CS.M.inf.1241:
The module's home is the MSc studies in Applied CS. It can also be credited in the BSc studies in Applied CS, and in several other studies:
6 ECTS credits (Studies in Applied Informatics and in MSc Wirtschaftsinformatik),
Maths (Dipl, MSc), Teaching, Magister, PhD GAUSS, ...

Note: participants are required to have successfully attended the module "Databases".

Note: the course is a prerequisite for "Semantic Web" (prospectively in WS2012/13) since it provides the necessary basic knowledge in logics.

Course Description

The course combines theoretical aspects with their applications in databases and knowledge representation:

• First-Order Logic
• The first-oder-logic-based twin to the relational algebra: Relational Calculus; domain-independence, safeness; translation of queries between Algebra and Calculus
• Model Theory, Reasoning and Query Answering in First-Order Logic: Resolution and Tableau Calculus
• Conjunctive queries (Datalog queries)
• Deductive Databases - Positive Recursive Datalog
• Advanced Datalog: Datalog with Negation, Well-Founded Semantics, Stable Semantics

Dates & Topics

• Thu 19.4.: No course.
• Fr 20.4.: No course.
• Thu 26.4.: 14-16 MN 28: Introduction, Begriffe ...
• Fri 27.4.: 10-12 HS2 Physik.
  Relational Calculus and First-Order Logic
  (die Folien sind aus der Fortsetzung des Foliensatzes der Vorlesung "Datenbanken")
• 3.5. FOL
• 4.5. FOL, Relational Calculus;
  Übungsblatt 1.
• Weitere Anfragen:
  Geben Sie die Anfragen aus den Aufgaben 6,7,8 von Blatt 2 sowie Aufgabe 6 von Blatt 3 der Datenbank-Vorlesung im relationalen Kalkül an (soweit diese keine Aggregation enthalten),
• Lösen Sie die Aufgaben von Blatt 1 des SQL-Praktikums im relationalen Kalkül.
• 10.5. Relational Calculus
• 11.5. Relational Calculus: RANF;
  Musterlösungen zu Übungsblatt 1
• Übungsblatt 2.
• 17.5. Feiertag
• 18.5. keine Vorlesung
• 24.5. Besprechung von Aufgaben 5 und 6 (Blatt 2), Musterlösungen zu Übungsblatt 2
  Vorlesung: Umformung zwischen relationalem Kalkül und Algebra
• 25.5. Besprechung von Aufgaben 4 und 7 (Blatt 2),
  Vorlesung: First-Order Model Theory and Reasoning
• Änderungen an den Folien am 30.5./31.5.: (1) F 453-458: Der Beweis Algebra -> Kalkül ist jetzt besser. (2) F480/481: eine Folie "Axiomatisierung" am Ende von Abschnitt 9.1 eingefügt.
• 31.5. Vorlesung: Reasoning, ab "Modelltheorie"
  Übungsblatt 3 - weitere Aufgaben: "Italiener-Aufgaben" von Folien 511/512; Besprechung am 7.6.
• 1.6. Vorlesung: Reasoning.
• 7.6. Besprechung Blatt 3 Aufg. 1, Vorlesung: Tableaux.
  Musterlösung zu Übungsblatt 3
  • Beispielaufgabe für Reasoning: Fish Puzzle: Überlegen Sie sich die Lösung und zeigen Sie die Korrektheit im Tableaukalkül. (Hinweis: definieren Sie eine Tableau-Regel für "XOR").
• 8.6. Vorlesung: FOL, Datalog - Teil I.
  Hinweis: auf Übungsblatt 3 ist noch eine Aufgabe dazugekommen.
• The Datalog sample programs from the slides are available here.
• 14.6. Besprechung Blatt 3 Aufg. 2, Vorlesung: Datalog
  Übungsblatt 4.
• 15.6. Vorlesung: Datalog
• 21.6. Bespr. Aufgabe 4.6 (tc, Pos. Datalog);
  Vorlesung: Stratifiziertes Datalog
• 22.6. Vorlesung: Stratifiziertes Datalog
• 28.6.: Bespr. Rest von Blatt 4,
  Musterlösung zu Übungsblatt 4, die Beispielprogramme (aggs.P usw) liegen hier.
  
• 29.6. Vorlesung: Datalog II: Well-Founded and Stable Models
• 5.7. Vorlesung,
  Übungsblatt 5.
• 6.7. Vorlesung: WFS and Stable Models
• 12.7. Übung (Besprechung Blatt 5, Aufg.1),
  Hinweis: Aufgabe 2 auf Blatt 5 ist neu dazugekommen.
  Vorlesung: Stable Models and Answer Set Programming
  Aufgabe: Codieren Sie das Fish Puzzle als ASP-Problem.
• 13.7. Übung (Besprechung Blatt 5, Aufg.2)
  Musterlösung zu Übungsblatt 5,
  Vorlesung
• 19.7. Vorlesung: Anwendung "Referentielle Aktionen in Relationalen Datenbanken" und Finale.
  Folien: ASP II: Referential Integrity (falls das Browser-PDF-plugin das Dokument nicht mag, pdf downloaden und mit was anderem anschauen).
  Papers:
  • IWS 1996 "Dagstuhl Castle" Workshop Paper: First version of deletions
  • PODS 1997 Conference Paper: Deletions and Updates (Only LP)
  • EDBT 1998 Conference Paper: Deletions with Games
  • TODS 2003 Journal Paper: The Long version of Everything
  • Appendix to the TODS 2003 Journal Paper
• 20.7. Letzter Termin. Finale und Auflösung/Besprechung "Fish Puzzle".
  • Lösungsweg
  • Resolution Proof
  • fishpuzzle.s

Prüfungen

• mündlich.
• Einzeltermine nach Absprache; fast beliebig (bis auf Urlaub).
• Prüfungsablauf (wie in Semantic Web): pro Person sind ca. 40 Minuten (einschl. Notenbesprechung und Bekanntgabe) geplant. Als Einstieg sollen Sie zuerst ca. 5 Minuten zu einem Teilthema Ihrer Wahl anfangen, der Rest ergibt sich dann dynamisch ...
• Anmeldung via FlexNever:
  An- und Abmeldefrist 21.7.
  Vorgehensweise wegen Einzelprüfungen (lt. Frau Jachinke, 11.5.2012):
  Nach Rücksprache mit dem PA muss für mündliche Prüfungen, die über mehrere Zeiträume verteilt erfolgen, ein "Fixtermin" zur Anmeldung festgelegt werden. Im Falle einer Abmeldung muss der Student bis 24 h vor "seinem Termin" eine Mail mit der Terminvereinbarung ans PA senden, die Abmeldung erfolgt dann von dort.
• 5.11.2012: Notenliste an PA übermittelt. Müsste also bald in FlexNever erscheinen. Die Scheine können ebenfalls bei Frau Jachinke abgeholt werden.

Resources

• All slides of DBIS lectures can be found here.
• Some topics of the course are closely related to chapters of the book Foundations of Databases by Serge Abiteboul, Richard Hull, and Victor Vianu that can be found as pdf here.
• A comprehensive course in logics (incl. slides and a skriptum) can be found at Formale Systeme, Prof. Dr. P.H.Schmitt, Karlsruhe (im wesentlichen Kapitel 4 und 5).

Software/Playground

• SQL-Queries on the Mondial database can be stated via this web form.
• Mondial in Datalog is available here.
• The Datalog sample programs from the slides are available here.
• For experimenting with Datalog, the XSB system is installed in the IFI CIP-Pool:
  Add

     alias xsb='rlwrap ~dbis/LP-Tools/XSB/bin/xsb'
  

  to your ~/.bashrc and then source .bashrc. Then call

   may@pc01> xsb
  

  The xsb prompt is then ?- .
  To leave XSB, press CTRL-D.
  Enter

   ?- [mondial].
  

  to "load" mondial into XSB. Query with e.g.

   ?- country(A,B,C,D,E,F).
  

  returns the first answer. Press "return" once to leave answers, press any other key and "return" to get next answer.
• Download of XSB Prolog/Datalog from Stony Brook University.
• For experimenting with stable models, smodels and its lparse frontend are installed in the CIP pool:
  Add

     alias smodels='~dbis/LP-Tools/smodels-2.34/smodels'
     alias lparse='~dbis/LP-Tools/lparsebin/lparse'
  

  to your ~/.bashrc and then source .bashrc. Then call

   may@pc01>  lparse -n 0 porq.s|smodels
   may@pc01>  lparse -n 0 -d none winmove.s|smodels
  

  where -n 0 indicates to show all stable models (any number can be given 0 means "all"). Option -d none omits the EDB predicates from the models.
  See lparse -help and smodels -help for further options.
• Download smodels and lparse from Helsinki University of Technology.
  • gunzip both, unpack with tar xvf.
  • cd into smodels-X.YZ, run make, creates smodels binary.
    Assign an alias for calling it.
  • cd into lparse-X.Y.Z, edit INSTALLATION_PATH in Makefile, read INSTALL text, and do what is recommended.
    Assign an alias for calling it.