Deductive Databases Summer 2020
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.
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).
DBIS does not use StudIP for uploading materials. 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:
- 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
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 20.4. 10-12: No meeting. Instead, from 14ct-16
there is an optional BBB test meeting with the Semistructured Data and XML
lecture where DBIS people will be present, and where we can answer questions.
Log in via StudIP->this lecture->Meetings->enter the meeting.
- Tue 21.4. 14-16 as planned:
BBB meeting: log in via StudIP (note: use the meeting "DD-21-apr-2020"; it is not
possible to "close" earlier meetings without also closing the recordings)
Administrativa, Overview, ...
pdf: the "concepts and buzzwords" graphics.
(no recording today because I forgot to switch it on)
- 27.4.: Lecture: First Order Logic (FOL), Relational Calculus
As I have nothing to write on ... reuse old Smartboard notes ... give a short overview:
DB vs relCalc vs FOL (querying vs reasoning) (first page)
DB vs RelCalc vs FOL (usage vs theory)
Declarative querying: Algebraic queries, internal
optimization; join, negation, relational calculus, CWA
Datalog style: Positional tuples, safeness of queries
transitive closure "flows into" (second page)
universal quantifier in RelCalc, XQuery (3rd page)
ObjOr modeling/RDF style, FOL->SQL [unsafe query patterns]
- 28.4.: Reasoning:
Types of knowledge - representation issues
... And then move to the regular slides of the lecture:
Slides Relational Calculus and First-Order Logic
(the slides are taken from the the continuation of the
Databases lecture)
- 1.5.: The above old Smartboard notes have been turned into slides
- 4.5.: FOL/Relational Calculus
- 5.5.: FOL/Relational Calculus, ... SRNF - Safety and Domain Independence
Exercise Sheet 1 (Relational Calculus and Algebra).
- 11.5.: Relational Calculus ... RANF - Sideways Information Passing vs. Bottom-Up
written notes from today
- 12.5.: Equivalence of the Relational Calculus and the relational algebra
- 18.5.: FOL Reasoning
Solutions to Exercise Sheet 1 Since I have nothing
to write and draw in real-time, there will not be a general presentation/recording
of the results. If you have questions, send me a mail.
- 19.5.: Datalog
Slides Datalog - Part I.
- 25.5. Datalog (cont'd)
The Datalog sample programs from the slides are available here.
- 26.5. Datalog (cont'd, Resolution Calculus)
Recall the Fish Puzzle.
Use your solution by human reasoning to solve it by the Resolution Calculus
- 1.6. NO LECTURE (Holiday)
- 2.6. Datalog (cont'd - Recursive Positive Datalog, Stratified Datalog)
Exercise Sheet 2 (Datalog).
- 8.6. Stratified Datalog, Well-Founded Semantics.
Slides Datalog II: Well-Founded and Stable Models.
- 9.6. Well-Founded Semantics.
Win-Move-Reduct-Computation as done in the lecture.
Solutions to Exercise Sheet 2. If some of the solutions should be
discussed or presented, or you have questions, send me a mail.
See also Discussion+Recording on 13.7.2020 below.
- 15.6. Well-Founded Model
continued Win-Move-Reduct-Computation with the Alternating Fixpoint
- 16.6. Well-Founded Model
-
Solution "Fish Puzzle" ... so far in theory
- 22.6. Lecture: Well-Founded and Stable Models
Slides Datalog III: Stable Models and ASP,
Exercise Sheet 3 (Well-Founded Model, Stable Models).
- 23.6. ASP and Stable Models
- 29.6. ASP - usage and examples
- 30.6. Lecture: ASP; example use case: Referential Integrity.
Practical Exercises: solve the Fish Puzzle and the soccer puzzle
- 6.7. Lecture: ASP; example use case: Referential Integrity, Finale.
Papers (Referential Integrity and Stable Models):
- see below: oral exam slots have been fixed
- 7.7. Solutions to Exercise Sheet 3,
liga.s (with some experiments commented out).
See also recording in StudIP/BBB (used uploaded pdf "paper", not slides -
for this, BBB is not appropriate).
- 13.7. "Discussion" of the solutions to Exercise Sheet 2 (pdf see above).
Annotated solution pdf (produced with
xournalpp and screen sharing),
see also recording in StudIP/BBB
(better than pdf BBB upload , but strange page-left-right scrolling
instead page-up-page-down).
- 14.7. (1) "Discussion" of the solutions to Exercise Sheet 1 (pdf see above).
Annotated solution pdf;
see also recording in StudIP/BBB
- 14.7. (2) Discussion of the Fish Puzzle
fishpuzzle.s
Note: this is a separate recording in a separate BBB meeting in StudIP/BBB.
- 17.7.2020 End of lecture period.
Exams
- Oral exams, between July and October 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 in-between.
- Exam period in July: 20.7.-28.7.
- Exam period in August/Sept: 18.8.-9.9.
- Exam period in October: 28.10.-6.11. (Winter term lectures start on 2.11. [looked up on 10.7.2020])
- Please contact may at informatik.uni-goettingen.de for the individual
appointments/slots.
- The exams take place as online meetings via BBB
- Exam procedure: 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:
-
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.uni-goettingen.de for a concrete appointment in
the slot. We try to 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
- 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.
|