Tomas Plachetka

Comenius University > Faculty of Mathematics, Physics and Informatics > Department of Computer Science

Research
Teaching
Publications
Contact

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

J. Mazak, T. Plachetka, Utorok 13:10, M.V

Domaca uloha 3: zadanie, priloha.

Odporucana literatura


Updated by Tomas Plachetka, Jun/16/2017