Tomas Plachetka

Databazy, leto 2017/2018

Oznamy

• Na skusku treba priniest index a ISIC kartu (na pisomku tiez pero a dostatok cistych papierov). Ziadne ine pomocky nie su dovolene. Vsetky elektronicke zariadenia, vratane mobilnych telefonov, budu pocas pisomky vypnute. Opisovanie, akakolvek komunikacia pocas testu alebo iny pokus o podvod znamena neuspesne absolvovanie kurzu (Fx). Vynimkou je komunikacia s ucitelom za ucelom upresnenia zadania ulohy.
• Skuska ma pisomnu a ustnu cast. Na skusku sa treba najneskor 1 den vopred elektronicky prihlasit. Ak sa Vam nedari prihlasit, poslite mi email. Prihlasenie na test je zavazne (t.j. termin, na ktory ste prihlaseny, sa pocita aj ked ten test nepisete). Ak viete ze na termin nepridete, prosim odhlaste sa z neho (ak mate problem s odhlasenim, dajte mi vediet cez email).
• Pri hodnoteni sa berie do uvahy len posledny termin skusky.
• V pondelok 19.marca o 14:00 v M.II bude prednaska, ktora nahradza prednasku 8.5.
• V pondelok 12.marca o 14:00 v M.II bude prednaska, ktora nahradza prednasku 1.5.

Skusky

• 13.6., 10:00, F1-109
• 6.6., 10:00, F1-109
• 23.5., 10:00, F1-108
• 29.5., 10:00, F1-108

Prednaska

Utorok 9:50, M-IV

Starsia (v niektorych 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

Cvicenia

Priebezne hodnotenie

Riesenie ulohy z cvicenia 24.4. (optimalizacia Wong-Youssefi)

Riesenie ulohy z cvicenia 17.4. (optimalizacia tableau, Yannakakis)

Domaca uloha z 24.4. (sub3), do 14.5.

Domaca uloha z 24.4. (sub2), do 14.5.

Domaca uloha z 24.4. (sub1), do 14.5.

Domaca uloha z 24.4. (tab), do 14.5.

Domaca uloha z 24.4. (maori), do 14.5.

Domaca uloha z 24.4. (halt), do 14.5.

Domaca uloha z 20.3. (cestarska), do 16.4.

Domaca uloha z 13.3. (naivna), do 9.4.

Domaca uloha z 6.3. (gurmanska)

Domaca uloha z 27.2. (Fibonacciho postupnost)

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/04/2018