|
|
Databases, summer 2021/2022
At least 45% evaluation of your work during the semester (homeworks) is
required to qualify to an oral exam.
Lectures and tutorials
Monday 12:20-15:30, M.I
- 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
- Prolog
- Syntax Prologu
- Interpretacia programov, unifikacia, SLD rezolucia
- 4-port model
- Cut
- Praca so zoznamami
- Vybrane druhoradove operatory: findall, bagof, setof, subtotal
- Vybrane optimalizacne techniky
- Semantika Datalogovych programov
- Logika prveho radu, negacia, protirecenia, ...
- Teorie a modely
- Domenovo nezavisle a bezpecne formuly
- Semantika minimalneho modelu
- Semantika pevneho bodu (fix-point) Datalogovych programov
- Stratifikovane a lokalne stratifikovane programy
- Gelfond-Lifschitzova transformacia
- Stabilne modely
- Trojhodnotove modely, well-founded model
- Vypocet well-founded modelu: alternujuci pevny bod
- Hierarchia semantik, priklady inych semantik
- Vypocet zhora nadol
- Vstupne mnoziny, pseudokluce, realizovatelnost programov so
zabudovanymi (napr. aritmetickymi) predikatmi
- Datalog versus Prolog: vypocet zdola nahor vs zhora nadol
- Rule-Goal Tree (RGT)
- Sirenie vazieb a vysledkov: magicke a pomocne predikaty
- Vypocet RGT do hlbky: expand_goal, expand_rule
- Vypocet RGT do sirky: Queue-based RGT (QRGT)
- Ozdoby predikatov a pravidiel, dovolene a zakazane ozdoby
- Rule-Goal Graph (RGG)
- Realizovatelnost vypoctu podla RGG: rektifikacia programu,
usporiadanie podcielov v pravidlach
- Magicke transformacie
- Vzory toku dat
- Jednoducha magicka transformacia
- Zovseobecnena magicka transformacia
- Vypocet zovseobecnenych magickych programov
- Dosledna rektifikacia: rozbalovanie cyklov
- Optimalizacie na urovni relacnej algebry
- Reprezentacie algebraickych vyrazov: stromy, dagy, hypergrafy
- Reprezentacia hypergrafu
- GYO redukcia hypergrafu
- Trhanie usi hypergrafu
- Vybrane zakony relacnej algebry
- Pravidla pre konstrukciu planu vypoctu v relacnej algebre
- Optimalizacia poradia joinov
- Eliminacia spolocnych podvyrazov
- Semantika SQL
- Minimalizacia operatorov relacnej algebry
- Predpoklady na vypoctovy model, uskutocnitelnost operacii
- Optimalizacie zalozene na redukcii hypergrafu
- Transformacia dotazu na standardny hypergraf
- Wong-Youssefiho algoritmus, preferencie na poradie
ostranovanych hran
- Uplny reduktor
- Yannakakisov algoritmus
- Hypergrafy a nekonecne relacie
- Inzinierske aspekty optimalizacie dotazov
- Odhad velkosti vystupu dotazu
- Priklady pouzitia indexov
- Denormalizacia databazy
- Distribuovane databazy
- Centralizovana (2-tier) architektura
- Distribuovana (3-tier) architektura
- Poziadavky na atomicky commit
- Dvojfazovy atomicky commit protokol
- Trojfazovy atomicky commit protokol
- Protokol pre vyber koordinatora
- Replikacia dat
- Protokoly pre dvojfazove zamykanie replikovanych dat, quorum
protokol
- Riesenie distribuovanych deadlockov
- Vyssie normalne formy
- Multizavislosti, 4NF
- Joinovacie zavislosti, 5NF
- Inkluzne zavislosti
- DKNF
- Metodika konstrukcie 4NF dekompozicie
- Konjunktivne dotazy
- Subsumpcia (pohltenie)
- Pohlcujuce zobrazenia
- Petrifikovane dotazy
- Petrifikovane dotazy
- Kanonicke databazy
- Hladanie pohlteni, Sariayov algoritmus
- Test pohltenia zjednoteni konjunktivnych dotazov
- Pohltenie konjunktivneho dotazu programom a opacne
- Pohltenie dotazov s negaciou, Levy-Sagivov test
- Pohltenie dotazov so zabudovanymi predikatmi,
Gupta-Zhang-Ozsoyoglu test
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)).
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,
Jun/6/2022
|