Deductive Databases SS 2019
Prof. Dr. Wolfgang May
Lars Runge, M.Sc.,
Sebastian Schrage, M.Sc.
Date and Time: Monday 1012, IFI SR 2.101 and Tuesday [1012 ct IFI SR 2.101] 1416 IFI SR 1.101.
Lecture and Exercises mixed (see announcements on this page).
There will be nonmandatory exercise sheets whose solutions will be discussed as
parts of the lecture.
If (and as long as) nongermanspeaking 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:
 FirstOrder Logic
 The firstoderlogicbased twin to the relational algebra: Relational Calculus;
domainindependence, safeness; translation of queries between Algebra and Calculus
 Model Theory, Reasoning and Query Answering in FirstOrder Logic: Resolution and Tableau Calculus
 Conjunctive queries (Datalog queries)
 Deductive Databases  Positive Recursive Datalog
 Advanced Datalog: Datalog with Negation, WellFounded 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 FirstOrder 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. BottomUp
Exercise Sheet 1 (Relational Calculus and Algebra).
Smartboard Notes
 14.5.: 1416h, 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. WellFounded Semantics. (Tuesday, the course is always in 1.101)
Slides Datalog II: WellFounded and Stable Models.
Smartboard Notes
Solutions to Exercise Sheet 2.
 17.6. WellFounded Semantics.
(again in 2.101, the Smartboard has been repaired)
Smartboard Notes
 18.6. WellFounded Semantics. (cont'd)
Smartboard Notes
 24.6. Lecture: WellFounded Model
Smartboard Notes
 25.6. Lecture: WellFounded Model
Smartboard Notes
 The slots for oral exams have been fixed, see below
(will appear in FlexNow in the next days)
 1.7. Lecture: WellFounded and Stable Models
Slides Datalog III: Stable Models and ASP.
Smartboard Notes
 2.7. Lecture: Stable Models, ASP
Exercise Sheet 3 (WellFounded Model, Stable Models).

Solution "Fish Puzzle" ... so far in theory
 8.7. Lecture: ASP
Smartboard Notes
 9.7. Lecture: ASP; example use case: Referential Integrity.
Practical Exercises: solve the Fish Puzzle and the soccer puzzle
Smartboard Notes
 15.7. Discussion of exercise sheet 3;
Solutions to Exercise Sheet 3.
liga.s (with some experiments commented out)
 16.7. Lecture: final considerations
on Open/Closed World; Discussion of the Fish Puzzle
fishpuzzle.s
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 inbetween.
Due to other appointments these will be fixed later (probably during the last 45 weeks of the lecture).
 Exam period in July: 18.31.7.
 Exam period in Aug/Sept: 22.8.17.9..
 Exam period in October: 14.10.1.11. (Winter term lectures start on Oct. 21)
 Note: FlexNow lists only the first day(!) of each of the slots. The system is not wellprepared
for the existence of oral exams.
 Please contact may at informatik.unigoettingen.de for the individual
appointments/slots.
 The exams take place in my office, Room 2.107, Inst.f.Informatik.
 Exam procedure: about 3040 minutes. Candidates start
with talking about a topic of their choice (510 minutes), then questions+answers,
including sketches on paper develops dynamically.
Languages: German, English.
 Registration via FlexNow:

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.unigoettingen.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 (mainly Chapters 4 und 5).
Software/Playground
 SQLQueries 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 CIPPool:
Add
alias xsb='rlwrap ~dbis/LPTools/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 CTRLD.
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
compareoperator/2."
There is no SQLstyle 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/LPTools/smodels2.34/smodels'
alias lparse='~dbis/LPTools/lparsebin/lparse'
to your ~/.bashrc and then source .bashrc. Then call
may@pc01> lparse n 0 porq.ssmodels
may@pc01> lparse n 0 d none winmove.ssmodels
may@pc01> lparse n 0 d none partial winmove.ssmodels
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 smodelsX.YZ, run make, creates smodels binary.
Assign an alias for calling it.
 cd into lparseX.Y.Z,
edit INSTALLATION_PATH in Makefile,
read INSTALL text, and do what is recommended.
Assign an alias for calling it.
