Deductive Databases SS 2022
Prof. Dr. Wolfgang May
Lars Runge, M.Sc.,
Dr. Sebastian Schrage
Date and Time:
 Monday 1012
IFI SR 2.101 and Tuesday 1416 IFI SR 1.101.
 This year, DBIS will again use mainly nonlive teaching by prerecordings.
There will be some live online meetings with BigBlueButton provided by GWDG;
the rooms/meetings can be entered via StudIP.
 Materials for selfstudying (in english) will be linked below weekwise:
 revised videos taken from summer term 2020 (as the "original" dates in the filenames indicate),
 PDF slides from the continuation of the Databases lecture slide set
 Please also read the general and technical information
about DBIS virtual teaching.
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.
All materials and announcements can be found HERE on the "blue DBIS pages".
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 FlexNow).
DBIS does not use StudIP for uploading materials. You find all
relevant information about the lecture at this Website.
Course Description
The course is a "practical theory" lecture: it 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
 Mon 18.4. Easter Monday
 Wed 19.4.: No DD meeting
 Mon 25.4.: No DD meeting
 Tue 26.4.: live meeting via StudIP>Deductive Databases>Meetings>DD20220426intromeeting
Administrativa, Overview, Introduction
Material for Selfstudying:
Part I: LogicBased Database Theory: Relational Calculus
 26.4. Materials for Selfstudying:
 2.5./3.5./9.5./10.5./16.5.: Relational Calculus. Materials for Selfstudying:

Recording: Relational Calculus
Recording: SRNF  Safety and Domain Independence
Recording: RANF  Sideways Information Passing vs. BottomUp
written notes (RANF) from the video.
Recording: Equivalence of the Relational Calculus and the relational algebra
Exercise Sheet 1 (Relational Calculus and Algebra).
 17.5.: FOL Reasoning
Recording: FirstOrder Logic Reasoning I
Recording: FirstOrder Logic Reasoning II
Focus: metanotions of reasoning wrt. some model theory. FOL has a model theory (that you might have
learnt about in the "Formal Systems" lecture, and which is revised here), and Datalog
(continuing with this lecture, using the same syntax as FOL) has a different model theory.
 23.5. Solutions to Exercise Sheet 1
Recording: Solution of Exercise Sheet 1
Annotated solution pdf

Tue 24.5. 14:15: Live online meeting
to answer questions, and to discuss/give a roadmap for the rest of the lecture:
 Up to here: the relational calculus. Queries, and especially conjunctive queries.
The relational calculus is equivalent to SQL, and thus polynomial.
The relational algebra has the same expressiveness as the relational calculus,
but as the equivalence proof shows, the relational calculus is more flexible
and intuitive for expressing a user's queries.
FOL is more expressive, so let's investigate what is inbetween. Use logics.
Continue first with "simple" things.
 Next level: positive Datalog, recursive rules, stratified negation in rules.
Covers SQL + recursion.
Intuitive bottomup evaluation semantics, topdown prooftheoretic semantics, Datalog's
underlying model theory: closedworld negation ("where not exists"/minus) as common for
databases.
Still rather simple, but builds the basis for more: problems that are not simple databasestyle.
 Third, final level then: nonstratified negation.
Wellfounded "argumentationstyle" semantics of "showing what cannot be derived".
There is always one wellfounded model  computable in polynomial time. But, it might be
nontotal (i.e., some atoms might not be "provable" or "disprovable", but "can be, can not be 
depending on each other" > alternative choices).
=> disjunctive reasoning with multiple "reasonable" solutions:
Stable models, Answer Set Programming. Puzzles, (real world) planning problems, and sudokus.
Part II: Positive and Stratified Datalog
Part III: WellFounded and Stable Models, Answer Set Programming

Tue 14.6. 14:15: Live online meeting
Questions and answers, summary, and outlook to the next lectures (for the recording, see StudIP).
 14.6.: Extending Datalog
Slides Datalog II: WellFounded and Stable Models
Recording: Summary and intuitive ideas from
Stratified Datalog towards WellFounded Semantics
 20.6.: WFS
Recording: Introduction to the
ideas of the wellfounded semantics; the winmovegame...
 21.6.: WFS
Recording: Reduct, winmove example, stability, ...
WinMoveReductComputation as done in this video ... with the continuation in the next session.
 22.6.: WFS
Recording: alternatingfixpoint computation and its interpretation, intro to 3valued logic
continued WinMoveReductComputation with the Alternating Fixpoint

Solution "Fish Puzzle" ... so far in theory
 28.6.: WFS
Recording: 3valued reduct and 3valued WFS
Recording: Comments and hints on the exercises (ex.sheet 3 and Fishpuzzle)
Exercise Sheet 3 (WellFounded Model, Stable Models, ASP).
 29.6.: WFS: alternating fixpoint and 3valued EFS towards stable models
Recording: AFP, 3valued WFS towards stable models
 4.7.: Stable Models and Answer Set Programming
Slides Datalog III: Stable Models and ASP
Recording: ASP
 5.7.: Stable Models and ASP
Recording: ASP examples
 11.7. ASP: example use case: Referential Integrity.
Recording: ASP use case referential integrity
Papers (Referential Integrity and Stable Models):
 12.7.: Conclusions
Conclusion of the lecture
 19.7. Solutions to Exercise Sheet 3,
liga.s (with some experiments commented out).
Recording: Presentation of the
solutions to Exercise Sheet 3
 20.7.: Solve the Fish Puzzle with ASP.
Hint: encode first 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").
Then, try the next steps ...
 Finale: Discussion of the Fish Puzzle
fishpuzzle.s
Recording: Presentation of the
solutions of the FishPuzzle
 An extensive slide set on ASP,
the Potassco system, and
application examples by Prof. Torsten Schaub, Uni Potsdam.
 22.7.2022 End of lecture period.
Exams
 Oral exams, basically whenever needed:
 Exam procedure (as before): 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:

The exam regulations
(Allgemeine
Prüfungsordnung BSc/MSc Göttingen (2013), Par.10b)
and the FlexNow system (that we must use) are not very appropriate
for administrating flexible individual oral exams. We solve this as follows:
 Oral exams and the formal registration in FlexNow are "always"
possible, this means, also during semesters where the lecture does not
take place.
 Deregistration in FlexNow is not possible. So register in FlexNow
only when you are sure that you want to do the exam. You must
be registered when actually doing the exam.
 The "FlexNow Exam" for summer term lectures is thus configured as
follows: Registration between Jul 1st and Jan 31st (Deregistration
until Jul 1st, means "not possible"). If you want to do the exam later,
use the subsequent winter term exam (always Feb 1st  Jun 30th).
Note that both
slots are listed under "Summer Term 2022" in FlexNow because they refer
administratively to the summer term lecture.
 For your actual individual exam appointment, contact
may at informatik.unigoettingen.de for a concrete appointment,
usually 34 weeks before the exam, specifying which week and maybe even
what day you prefer and morning/afternoon.
(We will become aware of your registration only via this mail  FlexNow
does not notify us about incoming registrations  and usually, we do not
look inside it actively.)
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"; default is 1, then, it stops after returning the first stable model!).
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.
