Databázy

(sylaby štátnic magisterského štúdia informatiky - plná verzia)

Účel databáz, charakteristika DB aplikácií, trojstupňová ANSI/SPARC architektúra, koncepčné dátové modely, navrhovanie databáz
- Entitno-relačný a relačný dátový model.
- Entitno-relačné diagramy, UML diagramy.
- Motivácia normalizácie.
Teória navrhovania databáz
- Funkčné závislosti, Armstrongove axiómy.
- Uzáver množiny atribútov, uzáver množiny funkčných závislostí.
- Pokrytie a minimálne pokrytie množiny funkčných závislostí.
- Nadkľúče a kľúče.
- Relačné schémy, dekompozícia relačných schém, bezstratovosť dekompozície.
- Normálne formy: 3NF, BCNF.
- Naivná dekompozícia do 3NF a BCNF.
- Dekompozícia do 3NF zachovávajúca funkčné závislosti.
Dotazovacie jazyky
- Relácie a predikáty, dotazy, relačný kalkul, Datalog, SQL, relačná algebra.
- Vyjadrovacia sila a vzájomné simulácie dotazovacích jazykov.
Agregácia a rekurzia v dotazovacích jazykoch
- Grupovanie a agregácia v relačnej algebre, SQL, relačnom kalkule a Datalogu.
- Rekurzia v relačnej algebre, SQL, relačnom kalkule a Datalogu.
Výpočet rekurzívnych programov a programov s negáciou
- Naivná evaluácia, seminaivná evaluácia.
- Unifikácia, SLD rezolúcia, rule-goal-tree, rule-goal-graph, väzby medzi premennými (binding patterns).
- Magická transformácia.
- Modely, stratifikovaná negácia, stable a well-founded sémantika.
Optimalizácia dotazov
- Strom relačného výrazu.
- Optimalizácia konjunktívnych dotazov dekompozíciou hypergrafu, Wong-Youssefiho algoritmus.
- Optimalizácia pomocou semijoinov, úplný reduktor, Yannakakisov algoritmus.
Optimalizácia konjunktívnych dotazov
- Pohltenie (containment) a ekvivalencia konjunktívnych dotazov.
- Testovanie pohltenia, petrifikované dotazy.
- Optimalizácia za predpokladu slabej ekvivalencie.
- Tablá a ich použitie.
Transakcie
- Definícia transakcie, elementárne transakčné operácie, požiadavky na transakčný systém.
- Komponenty transakčného databázového systému.
- Rozvrhy, triedy rozvrhov.
- Konflikt-sériovateľnosť, testovanie konflikt-seriovatelnosti, view-sériovateľnosť, dvojfázové zamykanie, obnova.
- Striktné dvojfázové zamykanie, riešenie deadlockov.
- Časové pečiatky, validácia.
Fyzická organizácia
- Fyzická algebra, zložitosť fyzických operátorov.
- Sekvenčné indexy, B stromy a B+ stromy.
- Hashovanie.
- Štruktúra hashovaného súboru: adresár, základné bloky, bloky preplnenia.
- Rozšíriteľné hashovanie.
- Lineárne hashovanie.
- Implementácia a zložitosť vybraných fyzických operátorov (merge-sort, nested-loop-join, ...).
Distribuované databázy
- Atomický commit, výber koordinátora (bully algoritmus), replikácia dát.
- Distribuované zámky, distribuované deadlocky.
- Synchronizácia času, Christianov algoritmus, Berkeley algoritmus.