Prof. Dr. Wolfgang May
Lars Runge, M.Sc.,
Sebastian Schrage, M.Sc.
Date and Time:
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.
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.
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).
DBIS does not use StudIP for uploading materials. You find all
relevant information about the lecture at this Website.
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
- 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
Dates & Topics
- Mon 12.4. No lecture. There is the institute's MSc welcome meeting in the afternoon.
- Tue 13.4. and Mon 19.4.: No DD meetings
- As stated on information
about DBIS virtual teaching, this year, DBIS will use mainly non-live teaching by pre-recordings;
there will be a small number of live meetings.
- Tue 20.4.: live meeting via StudIP->Meetings->DD-2021-04-20
Administrativa, Overview, ...
Materials for self-studying (videos taken from summer term 2020 as the dates in the filenames indicate;
the slides are taken from the continuation of the Databases lecture slide set)
- 26.4./27.4. No live meetings. Materials for Self-studying:
- 3./4./10./11.5.: Relational Calculus. Materials for Self-studying:
Recording: Relational Calculus
Recording: SRNF - Safety and Domain Independence
Recording: RANF - Sideways Information Passing vs. Bottom-Up
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: First-Order Logic Reasoning I
Recording: First-Order Logic Reasoning II
Focus: meta-notions of reasoning wrt. some model theory. FOL has a model theory (that you migt have
learnt about in the "Formal Systems" lecture, and which is revised here), and Datalog
(continuing with this lecture) has a different model theory.
I suggest to have a live online meeting on Tuesday, May
18th 14:15 (i.e. the usual afternoon slot).
to get some feedback (maybe some ad-hoc polls), answer questions, and to discuss/give a roadmap for the
rest of the lecture.
From then on, the course gets "productive" and continues with the different Datalog
- 19.5.: Datalog
Slides Datalog - Part I
The Datalog sample programs from the slides are available here.
Recording: Datalog I
- TO BE EXTENDED
- 16.7.2021 End of lecture period.
- With this year, we try a modified strategy for oral exams:
Oral exams, basically whenever needed:
- Exam procedure (as before): 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 FlexNow:
The exam regulations
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
- 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 (De-registration
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).
- For your actual individual exam appointment, contact
may at informatik.uni-goettingen.de for a concrete appointment,
usually 3-4 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.)
- All slides of DBIS lectures can be found
- 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
- 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).
- SQL-Queries on the Mondial
database can be stated via this web form.
- Mondial in Datalog is
- The Datalog sample programs from the slides are available here.
- For experimenting with Datalog, the XSB system is installed in the IFI CIP-Pool:
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
The xsb prompt is then ?- .
To leave XSB, press CTRL-D.
to "load" mondial into XSB (The file mondial.P must be in the current directory). Query with e.g.
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
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)"
?- 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:
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"; 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 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.