Tomas Plachetka

Databazy, leto 2019/2020

Nutnou podmienkou kvalifikacie na ustnu skusku je aspon 45% hodnotenie prace pocas semestra (domace ulohy).

Prednaska

Utorok 9:50, M.II

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
• 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

Cvicenia

Utorok 13:10, M.I

Domace ulohy

Domace ulohy treba riesit samostatne, riesenia odovzdat do uvedenych terminov.

K rieseniam niektorych uloh je potrebne mat instalovany SWI-Prolog. Pre zjednodusenie spustania dotazov odporucam do adresara so zdrojovymi subormi skopirovat query.pl a na zaciatok zdrojoveho suboru .pl pridat riadok
:- consult(query).
a dotazy spustat takto:
?- q(tree2node(L, L1, L2)).
(namiesto ?- tree2node(L, L1, L2)).

• Domaca uloha 1 (do 9.3.): Konverzie stromov v SWI-Prolog
• Domaca uloha 2 (do 16.3.): Modely
• Domaca uloha 3 (do 20.3.): Modely
• Domaca uloha 4 (do 20.3.): Modely
• Domaca uloha 5 (do 3.4.): Vypocet zhora nadol
• Domaca uloha 6 (do 3.4.): Rektifikacia, dovolene/zakazane ozdoby predikatov
• Domaca uloha 7 (do 16.4.): Magicka transformacia
• Domaca uloha 8 (do 16.4.): Magicka transformacia
• Domaca uloha 9 (do 24.4.): Hypergrafove optimalizacie, riesenie
• Domaca uloha 10 (do 24.4.): Hypergrafove optimalizacie, riesenie
• Domaca uloha 11 (do 10.5.): Hypergrafove optimalizacie

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/12/2020