Uni Göttingen
Institute for Informatics
Databases and Information Systems

dbis

Database Theory
SS2015

Prof. Dr. Wolfgang May may@informatik.uni-goettingen.de
Daniel Schubert schubert@informatik.uni-goettingen.de

Date and Time: Wednesday 10-12, Friday 14-16 ct, IFI SR 2.101.

Lecture and Exercises mixed (see announcements on this page).
If (and as long as) non-german-speaking participants attend, the course will be given in english.

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 WS2015/16) since it provides the necessary basic knowledge in logics.

Enrolment: there is no official enrollment for DBT. Students may freely decide to attend the lecture. Only at the end, for the exams, there is a registration (with FlexNever).
In general, I don't use StudIP (it is a lot of additional work, and past misfunctions of it resulted in severe problems). You find all relevant information about the lecture at this Website.

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
  • Practical Exercises will be done with XSB Prolog/Datalog and smodels.
  • The running example is the "Mondial" database. SQL queries against Mondial can be stated via a Web interface.

Dates & Topics

  • 15.4.: Introduction, Notions, Overview ...
    Lecture: FOL, Relational Calculus
    Slides Relational Calculus and First-Order Logic
    Smartboard Notes
    (the slides are taken from the the continuation of the Databases lecture)
  • 16.4.: FOL
    Smartboard Notes
  • 17.4.: FOL, Relational Calculus
  • 22.4.: Relational Calculus ... up to the "Safety"/"Domain Independence" issue.
    Smartboard Notes
  • Further Schedule
    • Goal: proceed as soon as possible with "interesting" things like Datalog
      (last time, I made the experience that at the end there was too less time to play with these things in more depth)
    • Overview and pragmatic summary of the remaining Slides of "Relational Calculus" (Relational Algebra Normal Form (RANF) and equivalence of the relational calculus and the relational algebra)
      ("classical" DB theory stuff; we need the conceptual implications of this (algebraic evaluation vs. logic), but not the technical details)
    • Short Review of Reasoning: This section has been dealt with extensively in the "Semantic Web" lecture and in "Formal Systems".
      FOL "Model Theory" is needed for the comparison with Datalog Model Definitions; the FOL Tableau Calculus is not needed for DBT (Datalog uses different mechanisms, as we will see ...)
      Again, the conceptual ideas are important to see what is different in the Datalog family.
  • 24.4.: finalize FOL/Relational Calculus.
    Starting point today (and main theme wrt. Negation, OpenWorld, Closed World in the following): Negation, Safety. We want to have negation, and we need safety (i.e. practical computability) ...
    And we want symbolic reasoning, for that there is the idea of Herbrand Interpretations.
    Smartboard Notes
  • 29.4.: Overview of First-Order Model Theory and Reasoning.
    Slides First-Order Model Theory and Reasoning
    Smartboard Notes
  • 1.5. Holiday. No lecture.
  • 6.5.: Overview of First-Order Model Theory and Reasoning (cont'd). The focus is on the meaning of the |= symbol for Structure |= Formula ("a fixed structure satisfies formula") and Formula1 |= Formula2 ("Formula1 entails Formula2") and the idea of "Model Theory". Datalog will use Model Theories that differ from the FOL one.
    Smartboard Notes
  • 8.5. Lecture: Datalog.
    Slides Datalog - Part I.
    Exercise Sheet 1 (Relational Calculus and Algebra).
    Smartboard Notes
  • 13.5. Lecture: Datalog (cont'd)
    Smartboard Notes
  • 15.5. Questions; Discussion of (parts of) Ex. 1.
    Smartboard Notes
  • 20.5. Discussion of Ex. 1 and 2
    Smartboard Notes
    Solutions to Exercises 1 and 2 of Sheet 1
  • 22.5. Lecture: Datalog (cont'd)
    Smartboard Notes
  • The Datalog sample programs from the slides are available here.
  • 27.5. Discussion of Exercises ...
    Lecture: Datalog (Cont'd)
    Exercise Sheet 2 (Datalog).
    Smartboard Notes
    Solutions to Exercises 3 etc of Sheet 1
  • 29.5. Lecture: Datalog (Cont'd): Prolog, Negation
    Smartboard Notes
  • 3.6. Some exercises from Sheet 2, Lecture: Stratified Datalog
    Smartboard Notes
  • 5.6. Lecture: Lecture: Stratified Datalog
    Smartboard Notes
  • 10.6. Remaining exercises from Sheet 2
    Smartboard Notes
  • 12.6. Remaining exercises from Sheet 2; Lecture: Stratified Datalog
    Smartboard Notes
    Solutions to Sheet 2
  • 17.6. Lecture: Datalog II: Well-Founded and Stable Models
    Smartboard Notes
  • 19.6. Lecture: Well-Founded Model
    Exercise Sheet 3 (Well-founded model).
    Smartboard Notes
  • 24.6. Lecture: Well-Founded Model
    Smartboard Notes
  • 26.6. Lecture: Well-Founded Model
    Smartboard Notes (continued from 24.6.)
  • 1.7. Lecture: Stable Models I
    Smartboard Notes (continued from 24.6./26.6.)
  • 3.7. Lecture: Well-Founded and Stable Models - three-valued
    Smartboard Notes
  • 8.7. Lecture: Well-Founded and Stable Models - three-valued
    Smartboard Notes
  • 10.7. Lecture: Well-Founded and Stable Models
    Smartboard Notes
  • 15.7. Discussion of the Exercises from Sheet 3 (some of them have already been discussed on-the-fly last week); Lecture: Stable Models/Answer Set Programming
    Solutions to Sheet 3
  • 17.7.
  • Exercise: encode the Fish Puzzle as an ASP problem.
    First, solve it by human reasoning. Then by ASP.
  • Solution "Fish Puzzle" -- going on as a supervised exercise (mail/meetings).
    • Solution by human reasoning
    • Hint I: encode the basic facts and some "simple" rules, look at the stable model/models.
      The first step from the human reasoning solution should show up ("second house is blue").
    • Try the next steps ...

Exams

  • Oral exams with individual appointments:
    • Exam period in July: 28.7.-1.8.
    • Exam period in September: 8.9.-12.9.
    • Exam period in October: 20.10.-31.10. (Winter term lectures start on Oct. 26)
    • Please contact may at informatik.uni-goettingen.de for the individual appointments/slots.
    • The exams take place in my office, Room 2.107, Inst.f.Informatik.
  • Exam procedure: about 30-40 minutes. Candidates start with talking about a topic of their choice (5-10 minutes), then questions+answers, including sketches on paper develops dynamically.
    Languages: German, English.
  • Registration via FlexNever:
    • Exam regulations (Allgemeine Prüfungsordnung BSc/MSc Göttingen (2013), Par.10b):
      Registration is possible until 7 days before begin of the exam period (here: the respective exam period). Deregistration is only possible during registration period.
    • According to the above slots, 3 entries will be provided by FlexNever; for each of them, registration+deregistration end 7 days before the beginning of the period.
      Choose the appropriate entry for registering.
    • Contact may at informatik.uni-goettingen.de for a concrete appointment in the slot. We try do have several exams on single days during each period.

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) (in German) 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 (The file mondial.P must be in the current directory). 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.
    Some usage hints:
    • String constants are enclosed in single quotes (like in SQL): ?- city('Berlin',C,P,Pop,_,_,_).
      Double quotes are not allowed.
    • ?- city(N,C,P,Pop,_,_,_), Pop > 1000000 . ... complains about "Wrong domain in evaluable function compare-operator/2."
      There is no SQL-style NULL in Datalog. Instead we use the constant null; this breaks the domain for numerical comparison. So check first that P is not null:
      ?- city(N,C,P,Pop,_,_,_), not (Pop = null), Pop > 1000000 .
  • 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
 may@pc01>  lparse -n 0 -d none --partial 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. Option --partial also outputs the partial stable models, where an output of p'(...) then means that p(...) is a least undefined.
    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.