|
|
Databazy, leto 2018/2019
Prednaska
Utorok 9:50, M.IV
Starsia (v niektorych veciach presnejsia) verzia tohto kurzu:
J.
Sturc
- Uvod, vypocet dotazov s funkcnymi symbolmi
- Organizacia kurzu, hodnotenie
- Odporucana literatura
- Funkcne symboly v Datalogu, suvis s XML
- Termy, Herbrandove univerzum, substitucie, matching, unifikacia
- Preklad Datalogu s funkcnymi symbolmi do relacnej algebry
- Operatory atov a vtoa
- Vypocet zdola nahor: naivna a seminaivna iteracia programov bez negacie
- Operatory semijoin a antijoin
- Vypocet zdola nahor: naivna a seminaivna iteracia programov s negaciou
- 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
- 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
- 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
- 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
- Inzinierske aspekty optimalizacie dotazov
- Odhad velkosti vystupu dotazu
- Priklady pouzitia indexov
- Denormalizacia databazy
- Vyssie normalne formy
- Multizavislosti, 4NF
- Joinovacie zavislosti, 5NF
- Inkluzne zavislosti
- DKNF
- Metodika konstrukcie 4NF dekompozicie
Cvicenia
Utorok 13:10, M.IV
Odporucana literatura
- S. Abiteboul, R. Hull, V. Vianu:
Foundations of Databases
- 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/15/2019
|