Jaroslav Pokorný

MFF UK, Praha

pokorny@ksi.ms.mff.cuni.cz

1. Úvod

Dva přístupy:

normalizační teorie

Metoda: návrh pomocí funkčních závislostí

z konceptuálního schématu

Metoda: návrh pomocí transformačních pravidel

2. Aktualizační anomálie

Uvaľujme relaci:PROGRAM(NÁZEV_K, JMÉNO_F, ADRESA, DATUM)

změní-li se adresa kina, je nutné ji měnit víckrát,

nehraje-li kino zrovna nic, ztrácíme jeho adresu

chceme-li přidat nové kino s adresou, lze to jen kdyľ se tam hraje nějaký film.

Codd: Aktualizační anomálie

zlepąení nevhodného schématu:

KINO(NÁZEV_K, ADRESA)MÁ_NA_PROGRAMU(NÁZEV_K, JMÉNO_F, DATUM)MÁ_NA_PROGRAMU[NÁZEV_K] ? KINO[NÁZEV_K]

Dekompozice

2. Aktualizační anomálie

Příčina:

Hodnoty některých atributů funkčně závisí na hodnotách jiných atributů. Závislost lze popsat tvrzeními:
- ke kaľdému kinu existuje nejvýąe jedna adresa
- pro kaľdé kino a film existuje nejvýąe jedno datum, kdy dané kino má daný film na programu

Značení: NÁZEV_K ? ADRESA, {NÁZEV_K,JMÉNO_F} ? DATUM,

Funkční závislosti

3. Funkční závislosti

{R(A),F} schéma relace doplněné o mnoľinu funkčních závislostí F

F ... speciální případ IO

obecněji: IO ... tvrzení vymezují mnoľinu přípustných relací

3. Funkční závislosti

Př: Rozvrh(Přednáąka, Učitel, Místnost, Hodina, Student, Známka) R(P,U,M,H,S,Z) ... úsporný zápis PUMHSZ ... jeątě úspornějąí

IO (v novějąí terminologii - podnikové pravidlo):Kaľdá přednáąka je přednáąena právě/nejvýąe jedním učitelem

mnoľinově: k jedné hodnotě z dom(P) se přiřadí právě/nejvýąe jedna hodnota z dom(U) ... P ??U

3. Funkční závislosti

R(A), X ? A. Jestliľe

X = {X1:dom(X1),...,Xn:dom(Xn)}, pak X-hodnotou je libovolný prvek z

dom(X1) ?... ? dom(1Xn).

Funkční závislost:

Nech» B, C ? A. Pak C závisí funkčně na B (nebo B funkčně určuje C), jestliľe ke kaľdé B-hodnotě existuje nejvýąe jedna C-hodnota.

Značení: B ? C.

3.1 Problém návrhu

Nahradit jediné schéma relace R mnoľinou schémat R’ = {R1,R2,...,Rn} tak, aby výsledek měl “rozumné” vlastnosti.

Moľnosti pro PUMHSZ

RI = {PU, HMP, HUM, PSZ, HSM} RII = {PU, HSP, PSZ, HSM} RIII = {PU, HSM, PSZ, HMP} RIV = {PU, HMP, PSZ, HSP} RV = {HMPU, PSZ, HSM} RVI = {PU, HMP, PSZ} RVII = {PSUHM, PSZ}

Která mnoľina schémat je lepąí?

3.1 Problém návrhu

Odhalení FZ mezi atributy 1 schématu

F: Nech» platí: P ? U, HM ? P, HU ? M, PS ? Z, HS ? M Jistě neplatí U ? HM

3.1 Problém návrhu

Df.: klíč schématu relace pomocí FZ: R(A), K ? A, pak K je klíčem schématu R, jestliľe splňuje dvě vlastnosti:

K ? A

neexistuje K', která je vlastní podmnoľinou K, taková, ľe K'? A.

3.2 Armstrongova pravidla

R(A), X, Y, Z ? A

triviální FZ:jestliľe Y ? X, pak X ? Y (FZ1)Př.: UM ? U

tranzitivita mezi mnoľinami atributů:jestliľe X ? Y a Y ? Z, pak X ? Z (FZ2)Př.: HS ? HM a HM ? P, pak také platí HS ? P.

kompozice pravých stran:jestliľe X ? Y a X ? Z, pak X ? YZ (FZ3)

dekompozice pravé strany:jestliľe X ? YZ, pak X ? Y a X ? Z (FZ4)

3.2 Armstrongova pravidla

Tv.: Nech» Rel je mnoľina vąech těch relací, které jsou vymezeny mnoľinou funkčních závislostí F. Armstrongova pravidla jsou

i) korektní, tj. co jimi z nějaké mnoľiny F odvodíme, platí na vąech relacích z Rel.

ii) úplná, tj. lze jimi odvodit vąechny funkční závislosti, které platí na kaľdé relaci z Rel.

iii) navzájem nezávislá, tj. odstraněním jakéhokoliv z nich poruąíme vlastnost úplnosti.

3.2 Armstrongova pravidla

Př: Uvaľujme F: P ? U, HM ? P, HU ? M, PS ? Z, HS ? M.

Podle (FZ1) platí HM ? H a HU ? H.

Podle (FZ3) z HU ? H a HU ? M odvodíme HU? HM

Podle (FZ2) z HM ? P a P ? U odvodíme HM ? U

Podle (FZ3) z HM ? H a HM ? U odvodíme HM ??HU

Vidíme, ľe HM a HU jsou funkčně ekvivalentní. Tento fakt lze zapsat jako HM ? HU.

3.3 Uzávěr, pokrytí mnoľiny FZ

Df.: Mnoľina vąech f odvoditelných z F se nazývá uzávěr FZnačení: F+.

Je-li f odvoditelná z F, znamená to, ľe patří do F+. F lze nahradit mnoľinou závislostí, které vzniknou dekompozicí pravých stran závislostí na jednotlivé atributy.

f, která má na pravé straně jeden atribut, nazýváme elementární.

3.3 Uzávěr, pokrytí mnoľiny FZ

Df.: Pokrytí mnoľiny funkčních závislostí F je mnoľina funkčních závislostí G taková, ľe F+ = G+.

Je-li F' mnoľina elementárních závislostí, která vznikne z F dekompozicí jejích neelementárních závislostí, platí F+ = F'+. Vzniklo tak kanonické pokrytí.

Df.: Závislost f je redundantní v F, jestliľe platí (F - { f })+ = F+Odstraněním vąech redundantních vznikneneredundantní pokrytí F.

3.3 Uzávěr, pokrytí mnoľiny FZ

Př.: Zatím jsme empiricky odhalili F = { AC????CB?D}

Odhalíme AC?D, ověřme, zda přináąí novou informaci.

1. AC??

2. CB?D

3. AC?C? ... dle FZ1 {AC?D} ??F+

4. dle FZ2 z 1. a 3. odvodíme AC?BC? byla by tedy

5. dle FZ4 z 2. a 4. odvodíme AC?D, redundantní

}

Úloha: Zjistit, zda f je redundantní v F.

Neredundantní pokrytí není dáno jednoznačně,

nemusí být podmnoľinou F, můľe vzniknout z F+

3.3 Uzávěr, pokrytí mnoľiny FZ

Df.:Uzávěr mnoľiny atributů X+ vzhledem k F je mnoľina vąech atributů funkčně závislých na X. Označujeme jej X+.

Obsahuje-li F závislost X ? Y a existuje atribut A ??X takový, ľe platí (X-A) + = X+, říkáme, ľe A je v X redundantním atributem.

Závislost, u které neexistují na levé straně ľádné redundantní atributy, se nazývá redukovaná závislost.

Př.: AB ? Y ??F; jestliľe vzhledem k F platí B+ = AB+, potom A je redundantní

3.3 Uzávěr, pokrytí mnoľiny FZ

Algoritmus: Nalezení minimálního pokrytí pro F.

Vstup: F nad mnoľinou atributů A relace R(A)

Výstup: minimální pokrytí G

begin 1. Dekomponuj pravé strany funkčních závislostí, tedy převeď FZ do elementárního tvaru, sestroj pro F kanonické pokrytí F’.

2. Odstraň redundantní atributy, tedy uprav F' na F’’ tak, aby vąechny f byly redukované.

3. Odstraň redundantní funkční závislosti, tedy pro F’’ vytvoř neredundantní pokrytí F’’’

end

3.3 Uzávěr, pokrytí mnoľiny FZ

Algoritmus: Nalezení neredundantního pokrytí pro F, které jsou elementární.

Vstup: F nad mnoľinou atributů A relace R(A)

Výstup: neredundantní pokrytí G

begin G := F

for each f ? G do

if f ? (G - { f })+ then G := G - { f }

end

3.3 Uzávěr, pokrytí mnoľiny FZ

Algoritmus: Řeąení problému přísluąnosti funkčních závislostíVstup: R(A), kde |A| = n,

F, kde |F| = m, f: X?C, kde C?A a X?A.

Výstup: Out ... typu Boolean Struktury dat:LS[1:m], RS[1:m] ... pole mnoľin, i-tý prvek obsahuje atributy z levé, resp. pravé strany i-té závislosti z F,

UZAVERX je proměnná obsahující po skončení algoritmu X+, DONE je proměnná typu Boolean.

Algoritmus počítá X+. Jestliľe C? X+ ? f ? F+ .

elementární funkční závislost

3.3 Uzávěr, pokrytí mnoľiny FZ

begin UZAVERX: = X; { na základě FZ1} DONE:= FALSE; while (not DONE) do begin DONE:= TRUE; for i = 1 to m do begin if ( LS[i] ??UZAVERX ) and ( RS[i] ??UZAVERX ) then begin UZAVERX:= UZAVERX ? RS[i]; DONE:= FALSE end end

end

Out := (C ? UZAVERX) end

Cyklus se určitě zastaví a vypočítá X+

3.3 Uzávěr, pokrytí mnoľiny FZ

Př.: R(A,B,C,D,E)

F = {AD?E, B?CD, B?A}. Pomocí algoritmu spočti B+.

řeąení:UZAVERX = B {inicializace}

UZAVERX = BCD { pouľití 2. FZ v 1. aplikaci vnitřního cyklu}

UZAVERX = BCDA { pouľití 3. FZ v 1. aplikaci vnitřního cyklu}

UZAVERX = BCDAE { pouľití 1. FZ v 2. aplikaci vnitřního cyklu}

Tedy B+ = ABCDE ... Co z toho lze vyvodit?

B? ABCDE ?????je klíčem schématu

3.3 Uzávěr, pokrytí mnoľiny FZ

Př.: R(A,B,C,D) a F = {A ?AC, B?ABC, D?ABC}. Pomocí algoritmu spočti minimální pokrytí.

Krok 1: Elementární závislosti: F'= {A ? A, A ??C, B?A, B?B, B?C, D?A, D?B, D?C}.

Krok 2: Vąechny závislosti jiľ jsou redukované.

Krok 3: A?A můľe být eliminována, je redundantní (je triviální).

A?C nemůľe (kdyby ano, pak v A+ nebude C (= A))

B?A nemůľe být eliminována (kdyby ano, pak B+= BC)

B?B můľe být eliminována, je redundantní (je triviální).

B?C můľe, (platí B?A a A ? C, tedy C?zůstane???B+)

D?A můľe, je redundantní (stále bude platit D+= DABC)

D?B nemůľe (kdyby ano, pak D+= DC)

D?C můľe, je redundantní (stále bude platit D+= DABC)

Výsledné neredundantní pokrytí G pro F' ( minimální) je F’’ = {A ? C, B?A, D?B}.

4. Normální formy schémat relací

Integritní omezení:

IO1: Klíčem schématu je {NÁZEV_K, JMÉNO_F}.

IO2: Kaľdé kino má právě jednu adresu

moľná ztráta informace

4. Normální formy schémat relací

Intuitivním řeąením je dekompozice schématu PROGRAM

ADRESÁŘ(NÁZEV_K,ADRESA),

PROGRAMY(NÁZEV_K, JMÉNO_F, DATUM)

adresa kina je pouze jednou (odstraněna redundance)

lze evidovat i kino, kde se (právě) nic nehraje

podstata řeąení: je odstraněna závislost neklíčového atributu (ADRESA) na podklíči (NÁZEV_K)

4. Normální formy schémat relací

IO1: Klíčem schématu je JMÉNO_F.IO2: Kaľdý herec má právě jednu národnost

moľná ztráta informace

Nelze sledovat národnost herců, kteří “nehrají”,

Ztratíme informaci o národnosti herce, jestliľe jeho filmy vypadnou z db

4. Normální formy schémat relací

Intuitivním řeąením je dekompozice

OSOBNÍ_ÚDAJE(HEREC, NÁRODNOST) FILM2(JMÉNO_F, HEREC, ROK),

národnost herce je pouze jednou (odstraněna redundance)

lze evidovat i národnost herce, jehoľ filmy nejsou v db

podstata řeąení: odstraněna závislost neklíčového atributu (národnost) na klíči (film) „přes“ neklíčový atribut (herec)

4. Normální formy schémat relací

V obou situacích byly jisté neklíčové atributy závislé tranzitivně na klíči.

V prvním případě ąlo o tranzitivitu klíč ??podklíč ??neklíčV druhém případě ąlo o tranzitivitu klíč ??neklíč ??neklíčJsou-li vąechny neklíčové atributy závislé na klíči přímo a nikoliv tranzitivně, schéma je ve 3NF.Má-li schéma více klíčů (klíč1?klíč2), nebude nám vadit klíč1??klíč2? neklíč

4. Normální formy schémat relací

Nechľ X a Y ? A, C je jednotlivý atribut, který se nevyskytuje v X ani v Y, X? Y? C a neplatí, ľe Y? X. Pak říkáme, ľe C je tranzitivně závislý na X.

Df.: Říkáme, ľe schéma relace R je ve 3. normální formě (3NF), jestliľe kaľdý neklíčový atribut schématu R není tranzitivně závislý na ľádném klíči schématu.

4. Normální formy schémat relací

ROZVRH(MHUP), HU? HM ... obě dvojice jsou klíče, tedy HU?P, HM?P P ? U ... závislost neplynoucí z definice klíče (daný předmět přednáąí nejvýąe jeden učitel)P ... jediný neklíčový atribut ROZVRH vyhovuje kritériu pro 3NF.

4. Normální formy schémat relací

Existuje zde ale tranzitivita klíč1 ? neklíč ? část_klíče2Jde o HM ? P? U, nabízí se dekompozice SEZNAM_P(P,U), ROZVRH(HMP)

zmizela redundance v atributech P a U

neztratí se informace, ľe Kryl přednáąí Programování, kdyľ toto vypadne z rozvrhu

řeąení spočívá v odstranění tranzitivní závislosti podklíče2 (U) na klíči1 (HM)

4. Normální formy schémat relací

Df: Říkáme, ľe schéma relace R je v Boyce - Coddověnormální formě (BCNF), jestliľe pro kaľdou netriviálnízávislost X ? Y platí, ľe X obsahuje klíč schématu R.

Kaľdé schéma, které je v BCNF, je také ve 3NF. Obrácené tvrzení neplatí. U schématu majícího jediný klíč, nebo jednoatributové klíče platí, ľe je-li ve 3NF je také v BCNF.