Něco jako poznámky k Databázovým systémům

Story všichni znáte.
Moral of the Story: Pořádným zamotáním lze i z něčeho jednoduchého udělat neproniknutelnou vědu.

Cílem tohoto textu je vnést trochu řádu do přednášek Databázové systémy.

Obsah. Zatím není (a asi nebude) linkovaný. 

Úvodní kapitoly
  Cíl databázových systémů
  Úvodní (bezúčelné) definice
Relační datový model
  Povolené datové struktury relačního dm
  Operace na n-árních relacích rel. dat. modelu
Navrhování a manipulace s databází
  Dotazy do databáze
    ...tady chybí DRK, NRK, SQL, QBE
  Navrhování a modifikace schémat databází
    Funkční závislosti
      Odvozování jedné funkční závislosti z druhé
      Algortimus příslušnosti (Membership Algorithm)
    Klíče k tabulkám a databázím
      Jak najdeme univerzální klíč
      Jak najdeme všechny univerzální klíče
    Normální formy databází
    "Ekvivalentní informativnost"
    Algoritmy vylepšování schémat databází
      Syntéza
      Dekompozice
    ...tady nejsou multizávislosti

Cíl databázových systémů

Sdílení množství dat: Další požadavky na DB:

Úvodní (bezúčelné) definice

Datový model
je nějaká teorie, soubor pojmů o tom, jak data skladuji.
Definuje:

Schéma
je definice (popis) databáze nebo její části.
Schéma databáze návrhář odvozuje ze zvoleného datového modelu.

Trojschématová architektura
Návrháři databáze ve snaze o oddělení dat a programů postupně přišli na to, že nebudou navrhovat celý systém naráz, ale že ho rozdělí na tři vrstvy:

Relační datový model

Relační datový model je datový model (tj. teorie) "relačních databází" (tj. těch databází, které na tomhle modelu stojí :-).

Povolené datové struktury relačního dm

Jedině n-ární relace (tj. podmža kart. součinu). Ekvivaletně ji budeme nazývat tabulkou.

Představujte si to tak, že máte mžu J všech potenciálních jmen, mžu P všech potenciálních příjmení a mžu D všech potenciálních dat narození. Pak snadno porozumíte, co je to relace žáků ve třídě a jejich dat narození. Je to podmža kart. součinu JxPxD, přičemž každá trojice (j,p,d) je v relaci <=> ex ve třídě žák jp, který se narodil dne d.

Pro účely databází je nejlepší chápat pojem relace sloupečkově. Uvedená relace jsou tři sloupečky, první je sloupeček jmen, druhá sloupeček příjmení a třetí sloupeček dat narození. Každá řádka popisuje jednoho existujícího žáka.

Pořadí řádek tabulky neuvažujeme.

Sloupečky nečíslujeme, ale raději pojmenováváme. Těmto jménum se říká atributová jména, atributy a pro tabulku hrají roli selektorů (pokud to někomu něco řekne).

Doména je mža povolených údajů pro každý sloupeček. Třeba doménou pro pořadové číslo žáka v třídním výkazu jsou přirozená čísla. Domény jsou většinou jasné, a proto se vynechávají.

Schéma n-ární relace je množina atributových jmen (tj. množina názvů něch sloupečků) a přílušejících domén. Je samozřejmě konečná.
Formálně S = { [A1, M1], [A2, M2], ..., [Ak, Mk] | Ai jsou atrubuty, Mi jsou domény}

Instance relace, relace nad schématem S je konkrétní tabulka se sloupečky a hodnotami v rozsahu podle daného schématu.
Formálně je to mža { [A1, m1], [A2, m2], ..., [Ak, mk] | Ai jsou atrubuty, mi jsou individua z příslušné domény Mi}

Zadání databáze vypadá tak, že dostaneme zadání schémat všech tabulek, které se v databázi vyskytují. (A správně bychom měli dostat i přehled integritních omezení, ale protože nikdo neví, co to je, tak to nikdy nedostáváme.) Příklady hledejte ve skriptech nebo na cvičení.

Operace na n-árních relacích rel. dat. modelu

Povolené operace na relacích v relačním datovém modelu se souhrnně nazývají relační algebra. Jsou to tyto (a možná další) operace. Značení, které uvádím, není určitě obecně používané, ale v té zpřeházené hromadě příkladů bylo uvedeno takhle.

sjednocení, rozdíl, průnik
chápeme je množinově
kartézský součin
sice taky chápeme množinově, ale zaslouží vysvětlení:
Nechť R=(A,B), tj. mějme relaci nad schématem A, B, tj. tabulku se sloupečky s názvy A a B. Nechť S=(C,D). Kart. součin RxS je pak relace se sloupečky A, B, C a D, v níž jsou všechny čtveřice, které lze získat kombinací všech řádků R se všemi řádky S.
projekce
vybírá některé sloupce relace
R[X] značí, z relace R mne zajímá jen sloupec X
R[X, Y] značí, že z relace R chci sloupce X a Y
R[X->A] značí, že z relace R chci sloupec X, ale chci ho přejmenovat na A
selekce, restrikce
vybírá řádky z relace podle nějakého pravidla
R[X<>const] vybere z relace R ty řádky, jejichž hodnota ve sloupci X je větší, menší, rovna, různá od konstanty (selekce)
R[X<>Y] vybere z relace R ty řádky, jejichž hodnota ve sloupci X je větší, menší, rovna či různá od hodnoty ve sloupci Y (selekce)
spojení
spojení ze dvou tabulek udělá jednu tabulku, platí identita:
R[X<>Y]S = (R x S)[X<>Y]
Při spojení se občas musí explicitně sloupečky přejmenovávat!
... a ještě další!
Materiál jde proti mně.. Ještě toho hodně zbývá a nemůžu se dostat k vysvětlování toho, co vážně nechápu. Teď udělám skok, ale nechám si tu názvy kapitol.

Navrhování a manipulace s databází

Manipulace s databází slouží k:

Nejprve se budeme zabývat dotazy a pak navrhováním a vylepšování databázových schémat.

Dotazy do databáze

Dotaz je funkce! Je definovaná na množině přípustných instancí databáze a jako obor hodnot má množinu jistých instancí relací (odpovídajících na dotaz).
Zápis dotazu je konkrétní písemné vyjádření dotazu v některém z dotazovacích jazyků (n-ticový relační kalku, doménový relační kalkul, SQL, QBE a určitě další).

Popíšeme si zde některé užívané formalismy.
n-ticový relační kalkul
Doménový relační kalkul
SQL
QBE
Tabulka srovnávající syntaxi různých dotazovacích jazyků

Navrhování a modifikace schémat databází

U složitějších databází si můžeme pěkně zavařit, když databázi špatně navrhneme, nebo když nám ji špatně navrhne někdo jiný. K tomu zavaření se váží dva nedefinovatelné termíny: aktualizační anomálie (v tabulkách máme údaje dvakrát, nebo naopak není, co do sloupečků napsat) a míšení informací, kterým si tyhle problémy uděláme.

Nejdříve si zavedeme nějaké pojmy, pak shrneme, o co nám při úpravách databázových schémat jde a nakonec popíšeme dva významné algoritmy pro úpravu databázových schémat.

Funkční závislosti

Funkční závislost (nějakých atributů na jiných)
znamená, že jakmile udáme hodnotu ve výchozích atributech, je tím jednoznačně určen řádek tabulky a tedy i hodnota v těch cílových sloupečcích.
Rodné_číslo->{Jméno, Příjmení} značí, že jméno a příjmení člověka je jednoznačně určeno (funkčně závisí) jeho rodným číslem.
R->JP je zkrácený zápis, při zápisu fčních závislostí píšeme místo sjednocení rovnou prvky za sebe

Na začátku nám někdo zadá množinu F funkčních závislostí (nebo ji sami na základě znalosti reálného světa známe). Např. F={RČ->Příjmení; Jméno, Příjmení->RČ;...}. Hned ze začátku se hodí si množinu závislostí hezky upravit.

Uzávěr F+ množiny závislostí F
je množina všech závislostí, které z F logicky vyplývají (spojováním pravidel za sebe).
My se vlastně chceme držet zadaného uzávěru závislostí a konkrétní seznam semínek F si můžeme upravovat tak, aby byl co nejkratší a nejjednodušší.
Uzávěr množiny atributů X v množině závislostí F
je množina všech závislostí, které z X logicky vyplývají při použití všech možných pravidel z F.
Elementární funkční závislost
ja taková fční závislost, která má na pravé straně jediný atribut.
Pokrytí množiny závislostí F
je množina G, jestliže platí F+ = G+.
Kanonické pokrytí
je pokrytí popsané elementráními závislostmi.
Redundantní závislost v nějaké mže závislostí F
je závislost odvoditelná z ostatních závislostí v F
Formálně: Závislost X->Y je v F redundantní, jestliže uzávěr levé strany X v F\{X->Y}, tj. F bez toho redundantního pravidla, již obsahuje pravou stranu Y.
Neredundatní pokrytí
je pokrytí bez redundatních závislostí.
Atribut A je redundatní v levé straně X některé závislosti,
jestliže (X\A)+ = X+.
Redukovaná závislost
je taková, které nemá na levé straně žádný redundantní atribut.
Minimální pokrytí
je kanonické neredundantní pokrytí prořené pouze redukovanými závislostmi.

Odvozování jedné funkční závislosti z druhé

Funkční závislosti je možné ze sebe navzájem odvozovat. (Tak také provádíme ty kýžené úpravy množiny F). K odvozování jedné závislosti z druhé se užívají následující odvozovací pravidla, která mají podobu implikací. Správně bychom si měli u každého uvědomit jeho korektnost (tj. že nevyvodí závislost silnější, než byla v zadání) a uvažovat o síle pravidel (o kolik informace přijdeme, když pravidlo použijeme).

Pravidla mají často několik rozdílných způsobů zápisu, ne všechny jsou stejně silné. Připomínám úmluvu, že místo sjednocení mžin píšeme jména mžin hned za sebe.

Přehled odvozovacích pravidel: (implikace píšu "pozpátku", předpoklady následují za slůvkem pro)

reflexivita
to co už znáš, to taky umíš odvodit
Y->X, pro množinu atributů X, která je částí mži Y
X->prázdná mža
X->X
augmentace, rozšíření
k danému pravidlu přifař ještě reflexivitu
W->Z, pro X->Y, Z částí Y, X částí W
XW->YZ, pro X->Y, Z částí W
XZ->YZ, pro X->Y
aditivita, union, kompozice
slepení dvou pravidel do jednoho
X->YZ, pro X->Y, X->Z
XW->YZ, pro X->Y, W->Z
tranzitivita
X->Z, pro X->Y, Y->Z
pseudotranzitivita
XW->Z, pro X->Y, YW->Z
dekompozice, projektivita
něco z toho, co umím odvodit, mohu zapomenout; 3 ekvivaletní znění:
X->Y, pro X->YZ
X->W, pro X->Y, W částí Y
X->Y, X->Z, pro X->YZ
akumulace
X->YZc, pro X->YZ, Z->cW
c může být jediný atribut a ne množina
Podle přednášejícího můžu klidně za C vzít i množinu, a uvažovat opakované použití pravidla pro všechny její prvky.

Příklady odvozování jednoho pravidla z druhého můžete najít na str. cca 20 poznámek k přednášce.

Někteří databázoví teoretici usilují o vytvoření úplného a korektního systému pravidel. Tj. chtějí zvolit takový (co nejmenší) soubor pravidel, aby pomocí něj bylo možné odvodit všechny závislosti a abychom žádnou neplatnou nepřidali. (Je to snaha podobná té, která ve výrokové logice prosadila jediné pravidlo, Modus ponens.) Příklady různých "axiomatických systémů" (nejde sice o axiomy, ale budiž) jsou na straně cca 20 poznámek k přednášce.

Algortimus příslušnosti (Membership Algorithm)

Vstup:
mža F funkčních závislostí
nějaká závislost X->c, c je nespíš jeden atribut (ale snadno se to upraví pro mžu)
Výstup:
odpověď, je-li závislost X->c prvkem uzávěru F

Algoritmus příslušnosti je navržený praktickými informatiky. Nemusíme generovat F uzávěr, abychom zjistili, jestli do něj X->c patří.

Myšlenka algoritmu je založena na ekvivalenci (X->c) je v F+ <=> c je v uzávěru X v F. Obě strany ekvivalence jsou vidět.

Konstruujme tedy X+ vzhledem k F, iterativně:

  1. X+ := X, pro začátek
  2. dokud X+ roste, opakuj:
    Přes všechna pravidla, je-li levá strana pravidla částí X+, přidej pravou stranu pravidla k X+
  3. pokud C je prvkem výsledného X+, odpověd kladně, jinak záporně

Klíče k tabulkám a databázím

Pro výklad normálních forem a algoritmů na vylepšení databází se bude hodit pojem klíče.

Klíč schématu relace R
je nejmenší množina atributů ze schématu R, na níž celá R funkčně závisí
Jakmile tedy máme hodnoty pro klíčové atributy, máme jednoznačné určen libovolný řádek tabulky.
Nadklíč schématu relace R
je libovolná nadmnožina nějakého klíče.
Když zkrátka ke klíči ještě přidáme nějaký další sloupeček.
Atribut se nazývá klíčový
je-li obsažen v libovolném klíči. (Jinak se nazývá neklíčový.)
Čili, když (třeba spolu s něčím dalším) zpřístupňuje řádky tabulky.
(Snaha je, aby uživatel nevyplňoval žádné klíčové atributy.)
Univerzální schéma databáze
je (myšlená) tabulka, která obsahuje úplně všechny sloupečky všech tabulek v databázi.
Co je v ní za data na jednotlivých řádcích si neumím představit (třeba jak vyplnit položku Rodné_číslo u druhu zeleniny...).
Univerzální klíč
je klíč univerzálního schématu databáze.
Tzn. to jsou ty atributy z kterýchkoli tabulek databáze, že pomocí nich přesně najdeme kteroukoli položku databáze.

Jak najdeme univerzální klíč

Ten se musí uhodnout.

Máme relaci nad schématem S (třeba ABDEF) a množinu funkčních závislostí F (třeba AB->C, DE->AB...). Zvládnutelný postup nalezení jednoho univerzálního klíče je:

  1. Začni s celým F.
  2. Dokud uzávěr F+ generuje celé S, zahazuj pravidla z F.
  3. Poslední množina závislostí F, která ještě generovala celé S, představuje jeden z univerzálních klíčů - jako univerzální klíč vezmi všechny atributy na levých stranách závislostí.

Ještě by mohlo jít:

  1. Vezmi jako základ Z nějaký atribut/dvojici atributů/trojici... z S.
  2. Udělej Z+ vzhledem k F.
  3. Pokud už jsi dostal celé S, je Z univerzální klíč.

Také je jasné, že jeden z univerzálních klíčů je rovnou celé S.

Jak najdeme všechny univerzální klíče

Máme relaci nad schématem S (třeba ABCDEF) a množinu funkčních závislostí F (třeba AB->C, DE->AB...). Univerzální klíče bychom mohli snadno najít tímto postupem:

  1. Pro každou podmnožinu A schématu S
  2. Udělej uzávěr A+ vzhledem k F
  3. Pokud ten uzávěr A+ je roven S, je A univerzální klíč.

Popsaný algoritmus je očividně exponenciální složitosti. Lepší je postup Lucchesiho a Osborna. Funguje iterativně - předloží se mu jeden univerzální klíč a on postaví jiný. A tak pořád dál, dokud množina univerzálních klíčů poroste (nebo alg. neprojde všechna pravidla, snad!).

  1. Vezmi nějaký univerzální klíč K. Třeba AC.
  2. Procházej pravidla v F a hledej takové, které má neprázdný průnik pravé strany s klíčem K. (To se dělá proto, že ten průnik budeme pak zahazovat.) Našli jsme BD->C.
  3. Levou stranu tohoto pravidla přidej ke klíči K. Dostáváme ACBD.
  4. Pravou stranu tohoto pravidla z klíče naopak odstraň. Dostáváme ABD.
  5. Takto upravená množina je jistě nadklíč, ověřme, že nelze zmenšit.
  6. Postupně zkoušíme z mži vyřadit jednotlivé atributy. Ověřujeme, že (BD)+!=S, (AD)+!=S, (AB)+!=S.
  7. Až už žádný atribut vyřadit nepůjde, je tato množina nalezeným univerzálním dalším klíčem.

Výhoda tohoto algoritmu je v tom, že se neprocházejí všechny podmožiny dané množiny. Jaká je ale jeho složitost, to si fakt netroufnu odhadovat.

Ještě je tu problém s nejasně formulovanou ukončovací podmínkou!!!

Normální formy databází

Databáze je v nějaké normální formě, když splňuje nějaké podmínky. Dělá se to proto, že ty podmínky ověřují, že databáze není rozbordelená nebo jinak neupravená. Jen co normální formy zavedeme ukážeme si, jak k vyšší normálním formám dospět.

První normální forma (1NF)
vyžaduje, aby všem atributovým jménům byly jako domény přiřazeny jednoduché datové typy.
Tedy vlastně nic extra. 1NF asi nelze nesplnit.
Druhá normální forma (2NF)
zakazuje míšení různých údajů v jedné tabulce.
Formálně se to řekne: Žádný neklíčový atribut (něco, co se vždy v tab. vyhledává) není funkčně závislý jen na části libovolného klíče.
Nesmím být tedy schopen najít nějaký údaj v tabulce podle informace, která je menší než klíč. (Jinak bych tabulku měl rozdělit na dvě.)
Třetí normální forma (3NF)
zakazuje tranzitivní funkční závislosti.
Formálně: neexistuje klíč Klíč schématu R, podmnožina P schématu R a neklíčový atribut X, který není v P obsažen, aby Klič->P->X, ale přitom neplatilo P->Klíč ani x->Klíč.
V tabulce Zaměstnanec( RČ, Č_Vedoucího, Č_Oddělení) lze Č_Vedoucího odvodit z Č_Oddělení. Klíčem do tabulky je přitom RČ zaměstance. (Nešikovné je to , protože při změně vedoucího nějakého oddělení budu muset projít všechny zaměstnance toho oddělení a vedoucího u nich upravit.)
Třetí normální forma definovaná jinak (ekvivalentně)
Relační schéma A je v 3NF, jestliže pro každou fční závislost Y->x, kde Y je podmža A a x je atribut z A platí alespoň jedna z podmínek:
  1. závislost je triviální, tj. atribut x je obsažen v Y,
  2. Y je nadklíč schématu A,
  3. x je klíčový atribut (je obsažen v alespoň jednom klíči).
Boyce-Coddova normální forma (BCNF)
nedovoluje ani tranzitivní závislost klíčových atributů, tj. obsahuje pouze body 1. a 2. z předchozí definice.
Tady bych chtěl příklad, ale nějak mne nenapadá.

"Ekvivalentní informativnost"

Chystáme se upravovat schéma relační databáze. Bylo by špatné, kdybychom úpravami třeba přišli o nějaká data nebo vztahy v databázi, proto během úprav kontrolujeme, jestli si neubližujeme. Soukromě jsem to nazval "ekvivalentní informativností" původního a nového schématu databáze.

Cílem je z relačního schématu (R, F), kde R je konečná mža atributových jmen a F konečná mža funkčních závislostí, udělat konečnou množinu schémat (R1, F1), ..., (Rk, Fk). Přitom Fi je "projekce" závislostí z F do dílčí relace Ri, tj. Fi obsahuje všechny závislosti z F, pro které se v Ri vyskytují potřebné atributy.

Jinak řečeno: Při úpravách databáze sekám tabulky na kusy a o zadané závislosti mezi atributy se moc nestarám. Až nakonec se ale musím kouknout, jestli jsem to nerozsekal tak, že nějakou závislost už v tabulkách nikdy nevyčtu.

"Informativnost" databázových schémat má dvě složky, které je třeba v zájmu "ekvivalence" ohlídat:

Bezztrátovost dekompozice relace R na relace R1, ..., Rk
Dekompozice je bezztrátová, jestliže zpětné spojení relací R1, ..., Rk (což jsou vykousané sloupečky z původní velké relace R) splňuje R1 * R2 * ... * Rk = R.
Tj., nestane se, že v zápalu boje zapomenu na nějaký údaj, ale taky žádný údaj nepřidám.
Většinou, tj. když úplně nevynechám nějaký sloupeček, by se mi stalo, že nageneruju víc, než v původní relaci bylo. Na to je třeba dát pozor.

Věta o dekompozici dle funkčních závislostí:
Nechť A je relační schéma, X, Y, Z rozklad na A. Jestliže na A platí X->Y, je dekompozice do schémat {X, Y} a {X, Z} bezztrátová.
Ekvivalentně: Dekompozice schématu S do schémat T, U je bezztrátová, jestliže platí T průnik U->T nebo T průnik U->U
Důkaz: je prý vidět z definic operace projekce a spojení a fčních závislostí.
Komentář: Když před každým rozdělením tabulky na dvě ověřím, že rozděluji tam byla požadovaná závislost, rozděluji bez ztráty informací.

Zachování/pokrytí závislostí při dekompozici relace R se závislostmi F na relace R1, ..., Rk se závislostmi F1, ..., Fk.
Závislosti F1, ..., Fk pokrývají závislost F, jestliže platí F+ = (sjednocení všech Fi)+.
(Tato definice je v souladu s předchozí definicí pokrytí závislostí.)

Teď už jsme konečně hotovi vrhnout se do úprav schémat databází.

Algoritmy vylepšování schémat databází

Někdo nám dá špatně navrženou databázi nebo nějaký zamotaný popis toho, co chce do databáze ukládat. Předpokládejme alespoň:

Dejme tomu, že dostaneme jedinou tabulku R a množinu závislostí F. Cílem je z té jediné relace R a funčních závislostí F udělat více relací R1, ..., Rk s odpovídajícími závislostmi F1, ..., Fk. Nová schémata musí být lepší co do dosažené normální formy a zároveň musí být zachována jejich "informativnost"

Popíšeme dva odlišné postupy úprav schématu databáze, u každého zkusíme zkontrolovat, jestli jsme dosáhli vyšší normální formy a jestli jsme zachovali "informativnost".

Pokud jsme dostali špatnou databázi, proces dekompozice ji opraví.
Pokud jsme dostali hromadu závislostí (z RČ poznáte příjmení, z příjmení poznáte barvu očí...), proces syntézy nám z těchle funkčních závislostí postaví databázi v 3NF.

Syntéza

Vstup:
Množina atributových jmen R
Množina funkčních závislostí F mezi atributy v R
Výstup:
Relace R1, ..., Rk s funkčními závislostmi F1, ..., Fk.
Relace budou v 3NF a funkční závislosti pokryjí původní F.
O bezztrátovosti syntézy (vycházíme-li z hotové databáze) hovoří věta na konci tohoto odstavce.
Fáze I. Zjednodušme zadanou F
Ve skriptech se praví, že chceme minimální pokrytí množiny závislostí (odstranění redundantních atributů a závislostí). Neboť nevím, co to znamená, musím si domyslet vlastní obsah.
1. Vytvořme (pomocí pravidla dekompozice) elementrání závislosti:
A->BC <=> A->B, A->C
tím uděláme, že všechna pravidla budou mít vlevo jediný symbol
Algoritmicky jsme to nikde neviděli.
2. Odstraňme redundantní atributy na levé straně pravidel:
např. místo {RČ, Barva_vlasů, Barva_očí} -> Příjmení stačí RČ->Příjmení
Jde o to, aby levé strany byly co nejmenší.
Jak se to dělá algoritmicky, to zase nikdo neřekl.
3. Odstraňme redundantní závislosti:
Tj. chceme zahodit pravidlo jako celek, je-li odvoditelné ze zbytku F.
Algoritmus neznáme, kouzlíme.
Jediné, co máme k dispozici, je věta: (BC->D) je v (F\(BC->D))+ <=> (BC)+ v F obsahuje D.
4. Spojme závislosti se stejnými nebo ekvivaletními levými stranami.
Např. místo pravidel AB->C a AB->D použijme AB->CD.
Nebo pokud AB<->CD (což prostě uhodneme! zas chybí alg!), z pravidel AB->E a CD->F uděláme AB->EF. (Musíme si trošku dát pozor, abychom při samém vyhazování nezahodili pravidla, která umožňují tu ekvivalenci AB<->CD!)
Na konci tohoto kroku se už mezi závislostmi nesmí vyskytovat žádné dvě se shodnými nebo ekvivaletními levými stranami.

Fáze II. Konstrukce tabulek
Podle závislostí, které zbyly v F, udělejme tabulky.
Postup je snadný, ze závislostí vykácejme šipky.
Tedy např. na základě závislosti AB->DEF uděláme tabulku se schématem ABDEF.

Text ve skriptech obsahuje ještě bod 2. Nalezněme nějaký univerzální klíč databáze Proč to vůbec děláme??
A chceme najít jediný univerzální klíč, nebo všechny univerzální klíče? (To by se dělalo pomocí Lucchesiho Osbornova algoritmu.)
Odpovědí na tyto otázky je snad následující věta, která pro posouzení předpokladů vyžaduje znalost nejlépe všech univerzálních klíčů.

Syntézu můžeme použít i pro vylepšení zadané databáze - když nám někdo zadá jedinou tabulku a seznam závislostí, je to totiž vlastně vstup pro syntézu. No a pak má smysl se ptát, je-li tahle úprava schématu databáze bezztrátová.

Věta: (Bernstein, Dayal, Biskup)
Výsledek syntézy má vlastnosti bezztrátového spojení <=> alespoň jedna z výsledných tabulek obsahuje alespoň jeden univerzální klíč původní databáze.
Bez náznaku dk.

Pokud jsme v maléru a nikde žádný univerzální klíč nemáme, stačí k databázi přidat navíc tabulku právě s tímto klíčem.

Možná tohle byl důvod hledání univerzálního klíče...

Dekompozice

Dekompozice je metoda historicky starší než syntéza. Byla vytlačena syntézou hlavně proto, že její algoritmus je nedeterministický (v tom smyslu, že není řečeno, v jakém pořadí by měl člověk dekomponovat, aby dosáhl co nejlepšího schématu) a že postupy jsou složité.

Princip dekompozice spočívá v opakovaném používání známé věty, vždy na závislosti, které nám kazí požadovanou NF. Připomínám znění věty o bezztrátové dekompozici:

Nechť A je relační schéma, X, Y, Z rozklad na A. Jestliže na A platí X->Y, je dekompozice do schémat {X, Y} a {X, Z} bezztrátová.

Rovněž připomínám test 3NF:

Relační schéma A je v 3NF, jestliže pro každou fční závislost Y->x, kde Y je podmža A a x je atribut z A platí alespoň jedna z podmínek:
  1. závislost je triviální, tj. atribut x je obsažen v Y,
  2. Y je nadklíč schématu A,
  3. x je klíčový atribut (je obsažen v alespoň jednom klíči).

Algoritmus dekompozice:

Vstup:
Množina atributových jmen R (univerzální relace)
Množina funkčních závislostí F mezi atributy v R
Výstup:
Relace R1, ..., Rk s funkčními závislostmi F1, ..., Fk.
Relace budou v takové NF, kam to budeme chtít dotlačit (3NF nebo BCNF).
Pokrytí funkčních závislostí bude třeba ověřit, obecně se mohou porušit.
Bezztrátovost dekompozice je zaručena, všechny kroky děláme v souladu s větou.
1. Najít všechny univerzální klíče schématu.
Algoritmus viz výše, hledání klíčů.
Děláme to proto, abychom dokázali snadno odpovídat na otázku splněnosti 3NF.
2. Najít funkční závislost v F+, která porušuje BCNF nebo 3NF.
Škodící fční závislost stačí hledat v F. Právě tady potřebujeme znát všechny klíče dekomponovaného schématu.
V praxi se ukazuje, že lepšího výsledku dosáhneme, když místo nalezené závislosti W->X budeme dekomponovat raději podle závislosti W->(W+).
3. Provést dekompozici schématu podle nalezené závislosti A->B.
Schéma C se rozdělí na dvě tabulky: levá bude obsahovat jako atributy levou a pravou stranu nalezené závislosti (tj. AB), pravá bude obsahovat levou stranu závislosti a zbytek atributů původního schématu (tj. A, C\B).
4. V dekomponovaných tabulkách najít klíče a pokračovat s každou tabulkou zvlášť podle bodu 2.
V levé tabulce je jasným kandidátem na klíč levá strana závislosti, podle níž se štípalo (tj. A).
Tento cyklus opakujeme, dokud všechny tabulky nejsou v požadované NF.

Postupovali jsme výhradně podle věty o bezztrátové dekompozici, bezztrátovost je tedy zaručena.

Obecně není jisté, že původní množina závislostí F bude novými Fi pokryta. Pokrytí je nutno ověřit samostatně. Stačí pro každou závislost z původní F zkontrolovat, že je v nějaké tabulce buď obsažena přímo, nebo že lze odvodit. (Při tomto odvozování se opět velmi hodí mít podtrhané klíče do jednotlivých tabulek.)

Podle pořadí výběru závislostí k dekompozici lze dosáhnout velmi odlišných výsledků. Žádný jednoduchý návod, jak si vybírat co nejlépa, ale navržen nebyl.

Snad se můžete poučit z příkladů, které najdete v textu přednášce.

Vícehodnotové závislosti (multizávislosti)

Multizávislosti už rozebírat nebudu. Za prvé jsem je nepochopil a za druhé už mne to nebaví.