Deductive Databases SS 2018
Prof. Dr. Wolfgang May
Lars Runge, M.Sc.,
Sebastian Schrage, M.Sc.
Date and Time: Wednesday 1012, IFI SR 2.101 and Friday 1416 ct, IFI SR 2.101.
Lecture and Exercises mixed (see announcements on this page).
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.
Note: the course is a prerequisite for "Semantic Web" (prospectively in SS2017)
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
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
 11.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)
Smartboard Notes: Overview of related
courses, concepts and buzzwords.
 13.4.: FOL
Smartboard Notes.
 Another example (and later exercise): Today, an online
newspaper article (in german) takes the ranking of the 2nd german
soccer league (after 29 rounds, Friday, April 13th morning) and shows a
possible final table (after 34 rounds) where all teams from the 4th to
the last, 18th place have 44 points each. (the current table is
actually quite dense, all teams from 5th position on fight against
relegation).
How must the teams play such that this final table
would come true? Guess, how many possibilities exist. This
problem can be solved with Stable Models with 6 rules (and
additionally atoms about the facts for the current table and the
remaining schedule of the season).
 18.4.: FOL
Smartboard Notes: FOL as a background model for symbolic reasoning.
 20.4.: FOL/Relational Calculus
Smartboard Notes
 25.4.: Relational Calculus ... SRNF  Safety and Domain Independence
Smartboard Notes
 27.4.: Relational Calculus ... RANF  Sideways Information Passing vs. BottomUp
Smartboard Notes
Exercise Sheet 1 (Relational Calculus and Algebra).
 2.5.: Discussion of Exercise Sheet 1, Ex. 1 ad
Smartboard Notes
Solutions of Exercise Sheet 1
 4.5.: Discussion of Exercise Sheet 1.1e, Lecture: Equivalence between RelCalc and RelAlg
Exercise Sheet 1 (updated, the second page was missing).
Smartboard Notes
 9.5.: Rel.Calculus, Reasoning
Smartboard Notes
 11.5.: Discussion Exercises 1.3 and 1.4;
Lecture: Reasoning (Tableau calculus only shortly)
Smartboard Notes
 16.5.: Datalog
Slides Datalog  Part I.
Smartboard Notes
 18.5. Datalog (cont'd)
Smartboard Notes
 23.5. Datalog (cont'd, Resolution Calculus)
Smartboard Notes
 25.5. Datalog (cont'd, Resolution Calculus)
Smartboard Notes
Recall the Fish Puzzle.
Use your solution by human reasoning to solve it by the Resolution Calculus
(see sketch of the first step on the Smartboard slides).
 Exercise 1.5 will be discussed on 30.5. or 1.6., when coming back
to XSB. (recall that there was a similar exercise in the
basic DB lecture for extending the algebra with aggregation.)

Revised Slides Datalog  Part I.
(the resolution proof for the sudoku example fragment has been added)
 30.5. Datalog (cont'd)
Smartboard Notes
 The Datalog sample programs from the slides are available here.
 1.6. Datalog (cont'd Stratified Datalog)
Smartboard Notes
Exercise Sheet 2
 6.6. WellFounded Semantics.
Slides Datalog II: WellFounded and Stable Models.
Smartboard Notes
 8.6. Discussion of Exercises 2.1 and 2.2; Lecture: Datalog (cont'd)
Smartboard Notes
Solutions of Exercise Sheet 2
 13.6. Discussion Ex. 2.6 and 2.2; Lecture: WellFounded Model
Smartboard Notes
 15.6. Lecture: WellFounded Model
Smartboard Notes
 20.6. Lecture: WellFounded Model
Smartboard Notes
 22.6. Lecture: WellFounded and Stable Models
Smartboard Notes
Slides Datalog III: Stable Models and ASP.

Solution "Fish Puzzle" ... so far in theory
 27.6. Lecture: Stable Models, ASP
Smartboard Notes
Exercise Sheet 3 (Wellfounded model, stable models)
 29.6. Lecture: ASP  the "Programming Language" based on the LP theory [up to the farmer puzzle]
Smartboard Notes
 4.7. Lecture: ASP; example use case: Referential Integrity.
Practical Exercises: solve the Fish Puzzle and the soccer puzzle
 6.7. Lecture: ASP
Smartboard Notes
 11.7. Discussion of exercise sheet 3; Lecture: final considerations
on Open/Closed World; questions/hints for the Practical Exercises
Solutions of Exercise Sheet 3 (Ex. 13)
Smartboard Notes
 13.7. Discussion of the practical exercises (Fish Puzzle, Soccer)
fishpuzzle.s
liga.s (with some experiments commented out)
 Papers (Referential Integrity and Stable Models):
Exams
 Oral exams, between July 16th and October 2018 with individual appointments:
 Exam period in July: 16.20.7.
 Exam period in August: 18.24.8.
 Exam period in September: 3.18.9.
 Exam period in October: 8.19.10. (Winter term lectures start on Oct. 15)
 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.
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.
