Institute for Informatics
Georg-August-Universität Göttingen

Databases and Information Systems

dbis
Uni Göttingen

Deductive Databases
SS 2019

Prof. Dr. Wolfgang May
Lars Runge, M.Sc., Sebastian Schrage, M.Sc.

Date and Time: Monday 10-12, IFI SR 2.101 and Tuesday [10-12 ct IFI SR 2.101] 14-16 IFI SR -1.101.

Lecture and Exercises mixed (see announcements on this page). There will be non-mandatory exercise sheets whose solutions will be discussed as parts of the lecture.
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 or an equivalent module.

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, DBIS does not 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 deductive 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, Answer Set Programming (ASP).
  • 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.
  • On a higher level, students will gain some insights into (commonsense) reasoning and about the intuitive background of formal logical frameworks.
  • Example for reasoning: Fish Puzzle:
    First step: find a solution (by human reasoning). This will finally be solved by ASP.

Dates & Topics

  • 15.4. NO LECTURE - note: 16:00h MSc introductory meeting with the Dean of Studies (room IFI 0.101).
  • 16.4.: Introduction, Notions, Overview ...
    Lecture: First Order Logic (FOL), Relational Calculus
    Slides Relational Calculus and First-Order Logic
    (the slides are taken from the the continuation of the Databases lecture)
    No smartboard notes today since the smartboard does not work;
    basically very similar to first smartboard notes last year: Overview of related courses, concepts and buzzwords.
  • 22.4.: NO LECTURE. Easter Monday.
  • 23.4.: FOL
    Smartboard Notes
  • 29.4.: FOL
    Smartboard Notes
  • NO LECTURE
  • 6.5.: FOL/Relational Calculus
    Smartboard Notes
  • 7.5.: FOL/Relational Calculus, ... SRNF - Safety and Domain Independence
    Smartboard Notes
  • 13.5.: Relational Calculus ... RANF - Sideways Information Passing vs. Bottom-Up
    Exercise Sheet 1 (Relational Calculus and Algebra).
    Smartboard Notes
  • 14.5.: 14-16h, Room -1.101: Rel.Calculus, Reasoning; Datalog
    Slides Datalog - Part I.
  • 20.5. from now on, the lecture takes place in SR -1.101 because the Smartboard in 2.101 is dead
    Datalog (cont'd)
    Solutions to Exercise Sheet 1. Plan: For each exercise sheet, there is one week to work alone - ask in the lecture if there are specific questions for hints, then the solutions are put on the Web, and then, concrete exercises will be discussed live in detail on demand.
  • 21.5. Datalog (cont'd, Resolution Calculus)
    Smartboard Notes
  • 27.5. Datalog (cont'd, Resolution Calculus)
    The Datalog sample programs from the slides are available here.
    Recall the Fish Puzzle. Use your solution by human reasoning to solve it by the Resolution Calculus
    Smartboard Notes
  • 28.5. Datalog (cont'd - Recursive Positive Datalog)
  • 3.6. Datalog (cont'd - Stratified Datalog)
    Exercise Sheet 2 (Datalog).
    Smartboard Notes
  • 4.6. Datalog (cont'd - Stratified Datalog)
    Smartboard Notes
  • 10.6. NO LECTURE (Holiday)
  • 11.6. Well-Founded Semantics. (Tuesday, the course is always in -1.101)
    Slides Datalog II: Well-Founded and Stable Models.
    Smartboard Notes
    Solutions to Exercise Sheet 2.
  • 17.6. Well-Founded Semantics. (again in 2.101, the Smartboard has been repaired)
    Smartboard Notes
  • 18.6. Well-Founded Semantics. (cont'd)
    Smartboard Notes
  • 24.6. Lecture: Well-Founded Model
  • 25.6. Lecture: Well-Founded Model
  • TO BE EXTENDED

Exams

  • Oral exams, between July 16th and October 2019 with individual appointments. There will always be slots directly after the end of the lecture, around the beginning of the lectures of the winter term. There will be additional slots in-between. Due to other appointments these will be fixed later (probably during the last 4-5 weeks of the lecture).

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 (mainly Chapters 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. Go to the directory where your input sources (e.g. mondial.P from above) is located and 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 (unequality can be written as "x \= y" or "not (x=y)" in Prolog):
      ?- city(N,C,P,Pop,_,_,_), Pop \= null, Pop > 1000000 .
      ?- 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.