Tomas Plachetka

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

Research
Teaching
Publications
Contact

Databases, summer 2021/2022

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

Lectures and tutorials

Monday 12:20-15:30, M.I

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

Homeworks

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

Recommended literature

  • S. Abiteboul, R. Hull, V. Vianu: Foundations of Databases
  • J.D. Ullman: Database and Knowledge-Based Systems (Vol. 1, Vol. 2), Computer Science Press, 1989.
  • 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/6/2022