Tomas Plachetka

Databases, summer 2024/2025

At least 45% evaluation of work during the semester (homeworks) is required to qualify for the exam.

Lectures and tutorials

Friday 8:10-11:10, F1.109

• Introduction, function symbols
  • Course organisation, grading
  • Recommended literature
  • Function symbols in Datalog
  • Terms, Herbrand universum, substitution, term matching, term unification
  • Translation of Datalog with function symbols to relational algebra
  • Operators atov a vtoa
  • Bottom up computation of Datalog programs without negation
  • Operators semijoin a antijoin
  • Bottom up computation of Datalog programs with negation
• Semantics of Datalog
  • First-order logic, negation, contradictions, ...
  • Domain-independent and safe formulas
  • Theories and models
  • Minimal model semantics
  • Fix-point semantics
  • Stratified and locally stratified programs
  • Gelfond-Lifschitz transformation
  • Stable models
  • Three-valued models, well-founded model
  • Computation of well-founded model: alternating fix-point
  • Other semantics

Homeworks

Some homeworks require installation of PostgreSQL.

Some homeworks require installation of SWI-Prolog. I recommend copying the file query.pl to your working directory, and adding a line
:- consult(query).
to your .pl files and execute queries like this:
?- q(tree2node(L, L1, L2)).
(instead of ?- tree2node(L, L1, L2)).

Hand out your solutions via email.

Recommended literature

• S. Abiteboul, R. Hull, V. Vianu: Foundations of Databases
• J.D. Ullman: Database and Knowledge-Based Systems (Vol. 1, Vol. 2), Computer Science Press, 1989.
• P.A. Bernstein, V. Hadzilacos, N. Goodman: Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987
• H. Garcia-Molina, J.D. Ullman, J. Widom: Database Systems, The Complete Book, Prentice Hall, 2003
• C. Zaniolo: Advanced Database Systems, Morgan Kaufmann, 1997
• P.A. Bernstein, E. Newcomer: Transaction Processing (2nd ed.), Morgan Kaufmann, 2009

Updated by Tomas Plachetka, Mar/6/2026