Tomas Plachetka

Databases, summer 2020/2021

At least 45% evaluation of your work during the semester (homeworks) is required to qualify to an oral exam.

Lectures and tutorials

Tuesday 9:00-12:10, online

• Introduction, function symbols
  • Course organisation, grading
  • Recommended literature
  • Function symbols in Datalog
  • Terms, Herbrand universum, substitution, term matching, term unification
  • Translation of Datalog with function symbols to relational algebra
  • Operators atov a vtoa
  • Bottom up computation of Datalog programs without negation
  • Operators semijoin a antijoin
  • Bottom up computation of Datalog programs with negation
• 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
• Konjunktivne dotazy
  • Subsumpcia (pohltenie)
  • Pohlcujuce zobrazenia
  • Petrifikovane dotazy
  • Petrifikovane dotazy
  • Kanonicke databazy
  • Hladanie pohlteni, Sariayov algoritmus
  • Test pohltenia zjednoteni konjunktivnych dotazov
  • Pohltenie konjunktivneho dotazu programom a opacne
  • Pohltenie dotazov s negaciou, Levy-Sagivov test
  • Pohltenie dotazov so zabudovanymi predikatmi, Gupta-Zhang-Ozsoyoglu test
• Vyssie normalne formy
  • Multizavislosti, 4NF
  • Joinovacie zavislosti, 5NF
  • Inkluzne zavislosti
  • DKNF
  • Metodika konstrukcie 4NF dekompozicie
• Minimalizacia konjunktivnych dotazov
  • Predpoklad univerzalnej relacie
  • Slabe pohltenie, slaba ekvivalencia konjunktivnych dotazov
  • Tableaux, konstrukcia tableaux
  • Minimalizacia tableaux
  • Uzatvaracia procedura (chase): vynutenie funkcnych zavislosti a multizavislosti
  • Silna ekvivalencia konjunktivnych dotazov
• 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

Homeworks

Solve your homeworks individually.

Some homeworks require installation of SWI-Prolog. I recommend to copy the file query.pl to your working directory, add a line
:- consult(query).
to your .pl files and execute the queries like this:
?- q(tree2node(L, L1, L2)).
(instead of ?- tree2node(L, L1, L2)).

• Homework 1 (due to 22.2.): Function symbols, attachment
• Homework 2 (due to 7.3.): Datalog semantics
• Homework 3 (due to 15.3.): Rectification etc.
• Homework 4 (due to 29.3.): Magic transformation
• Homework 5 (due to 26.4.): Magic transformation
• Homework 6 (due to 26.4.): Hypergraph-based optimisation

Recommended literature

• 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/1/2021