|
|
Databases, summer 2024/2025
At least 45% evaluation of work during the semester (homeworks) is
required to qualify for the exam.
Lectures and tutorials
Thursday 9:50-13:00, M.IX
- 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
- Prolog
- Syntax of Prolog
- Unification, SLD resolution
- 4-port model
- Cut
- Lists
- Selected second-order predicates: findall, bagof, setof, subtotal
- Selected optimisation techniques
- Top-down computation of queries
- Datalog vs. Prolog: bottom-up vs. top-down
- Rule-Goal Tree (RGT)
- Propagation of bindings and results
- Evaluation of RGT: expand_goal, expand_rule
- Breadth-first evaluation of RGT: Queue-based RGT (QRGT)
- Adornments of predicates and rules, forbidden adornments,
processing of built-in predicates
- Rule-Goal Graph (RGG)
- Computationally feasible RGG: rectification of programs,
ordering of goals in rules
- Magic transformations
- Patterns of top-down information flow
- Magic transformation
- Generalised magic transformation
- Issues with computation of generalised magic programs
Homeworks
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/31/2025
|