Uni Göttingen
Institute for Informatics
Databases and Information Systems

dbis

Deductive Databases
(formerly Database Theory)
Summer 2026

Prof. Dr. Wolfgang May

Date and Time:

  • Monday 10-12 IFI SR 2.101 and Tuesday 14-16 IFI SR -1.101.
  • This year, DBIS will again use mainly non-live teaching by pre-recordings. There will be some live online meetings with BigBlueButton provided by GWDG; the rooms/meetings can be entered via StudIP.
  • Materials for self-studying (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 non-mandatory 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) non-german-speaking participants attend, the course will be given in english.

Module CS.M.inf.1241, 4 SWS, 6 ECTS:
The module's home is the MSc studies in Applied CS. It can also be credited in the BSc studies in Applied CS (as Module "Vertiefung Softwaresysteme und Daten", B.inf.1706), and in several other studies:
e.g., MSc Wirtschaftsinformatik/Information Systems, Maths, Education/2-Subjects-Bachelor, PhD GAUSS, ...

It is strongly recommended that participants have successfully attended the module Databases or an equivalent module and have basic knowledge in formal logics.

Enrolment: there is no official enrollment for DD/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:

  • 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 (classical Relational Database Theory)
  • 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

Part I: Logic-Based Database Theory: Relational Calculus

Part II: Positive and Stratified Datalog

  • Tue 19.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 in-between. Use logics. Continue first with "simple" things.
    • Next level: positive Datalog, recursive rules, stratified negation in rules.
      Covers SQL + recursion.
      Intuitive bottom-up evaluation semantics, top-down proof-theoretic semantics, Datalog's underlying model theory: closed-world negation ("where not exists"/minus) as common for databases.
      Still rather simple, but builds the basis for more: problems that are not simple database-style.
    • Third, final level then: non-stratified negation.
      Well-founded "argumentation-style" semantics of "showing what cannot be derived".
      There is always one well-founded model - computable in polynomial time. But, it might be non-total (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.
  • 19.5.: Datalog
    Slides Datalog - Part I
    The Datalog sample programs from the slides are available here.
    Recording: Datalog I
  • 25.5.: Holiday (Whitsun Monday)
  • 26.5.: Datalog
    Recording: Datalog II
  • 1.6.: Datalog
    Recording: Resolution Calculus
    Recall the Fish Puzzle.
    Use your solution by human reasoning to solve it by the Resolution Calculus
  • 2.6.: Datalog
    Recording: Stratified Datalog
    Exercise Sheet 2 (Datalog).
  • Solutions to Exercise Sheet 2.
    Recording: Presentation of the solutions to Exercise Sheet 2
    Annotated solution pdf to Ex.Sheet 2 from the recording.

Part III: Well-Founded and Stable Models, Answer Set Programming

Exams

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"; 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.