|
|
Databazy, Leto 2022/2023
Nutnou podmienkou kvalifikacie na ustnu skusku je hodnotenie prace pocas
semestra (domace ulohy) aspon 45%.
Prednaska
Pondelok 12:20-15:20, M.IX
- Uvod, funkcne symboly
- Organizacia kurzu
- Odporucana literatura
- Funkcne symboly v Datalogu
- Termy, Herbrandove universum, substitucia, term matching, term
unification
- Preklad Datalogovych programov s funkcnymi symbolmi do relacnej
algebry, operatory atov a vtoa
- Naivna evaluacia, operatory semijoin a antijoin
- 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
- 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
- Vypocet zhora nadol
- 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
- Vstupne mnoziny, pseudokluce, realizovatelnost programov so
zabudovanymi (napr. aritmetickymi) predikatmi
- Magicke transformacie
- Vzory toku informacii
- 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
- Minimalizacia konjunktivnych dotazov
- Predpoklad univerzalnej relacie
- Slabe pohltenie, slaba ekvivalencia konjunktivnych dotazov
- Tableaux, konstrukcia tableaux
- Minimalizacia tableaux
- Uzatvaracia procedura (chase): vynutenie funkcnych zavislosti a
multizavislosti
- Silna ekvivalencia konjunktivnych dotazov
Domace ulohy
Niektore ulohy vyzaduju instalaciu SWI-Prolog.
Odporucam skopirovat file query.pl do working
directory, pridat riadok
:- consult(query).
na zaciatok .pl suborov, a pisat dotazy takto:
?- q(tree2node(L, L1, L2)).
(namiesto 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,
May/13/2023
|