Tomas Plachetka

Databazy, leto 2016/2017

Oznamy

Prednaska

T. Plachetka, Utorok 9:50, M-IV

Starsia (uplnejsia a v podstatnych veciach presnejsia) verzia tohto kurzu: J. Sturc

• Uvod, vypocet dotazov s funkcnymi symbolmi
  • Organizacia kurzu, system hodnotenia
  • 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
  • Niektore 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
• Konjunktivne dotazy
  • Subsumpcia (pohltenie)
  • Pohlcujuce zobrazenia, petrifikovane dotazy, kanonicke databazy
  • Test pohltenia zjednoteni konjunktivnych dotazov
  • Pohltenie konjunktivneho dotazu programom
  • Pohltenie dotazov s negaciou, Levy-Sagivov test
  • Pohltenie dotazov so zabudovanymi predikatmi, Gupta-Zhang-Ozsoyoglu test
• Minimalizacia konjunktivnych dotazov
  • Silna a slaba ekvivalencia konjunktivnych dotazov
  • Tableaux, konstrukcia tableaux
  • Minimalizacia tableaux
  • Uzatvaracia procedura (chase): vynutenie funkcnych zavislosti a multizavislosti
• Vyssie normalne formy
  • Multizavislosti, 4NF
  • Joinovacie zavislosti, 5NF
  • Inkluzne zavislosti
  • DKNF
  • Metodika konstrukcie 4NF dekompozicie
• 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
  • Synchronizacia hodin a casove peciatky

Cvicenia

Domaca uloha 3: zadanie, priloha.

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, Jun/16/2017