COMPUTERWORLD
pod kapotou
3. normální forma relace

Již ve třetím pokračování Databázové abecedy (CW, 14, 1996) jsme se zmiňovali o E-R modelu a o tom, že v současné době se uplatňuje především shora dolů přístup k návrhu relační databáze, tj. transformace konceptuálního schématu do relačního modelu dat (RMD). Vedle toho existují také některé klasické postupy zavedené v RMD již v 70. letech, které jsou založené na normálních formách (NF). Jedna z nich, 1NF, je zřejmě nejznámější, protože představuje základní předpoklad RMD. Relace v 1NF má atomické hodnoty v komponentách řádku relace. Co však další normální formy? Projektant dnešních relačních databází by měl znát hlavně 3NF. Představuje zřejmě nejrozumnější podmínky, které by měla splňovat “dobře” navržená relace.

Uvažujme relaci

PROGRAM(NÁZEV_K, JMÉNO_F, ADRESA, DATUM)

kde ADRESA znamená adresu kina, kde se film dává. Každého napadne, že cosi není v pořádku. Odpovídající tabulky budou obsahovat některé informace zbytečně vícekrát. Adresa kina se bude opakovat tolikrát, kolik filmů kino zrovna hraje. Tabulka tedy bude zabírat více místa a navíc může dojít k problémům s údržbou tabulky. Změní-li se adresa kina, je nutné ji měnit víckrát, nehraje-li kino zrovna nic, ztrácíme jeho adresu. Tyto potíže nazýval Codd aktualizační anomálie. Lze je odstranit jednoduše dekompozicí schématu PROGRAM do dvou schémat

KINO(NÁZEV_K,ADRESA)

MÁ_NA_PROGRAMU(NÁZEV_K,JMÉNO_F,DATUM)

Funkční závislosti

Co však stojí za aktualizačními anomáliemi? Hodnoty některých atributů funkčně závisí na hodnotách jiných atributů. Např. 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. Uvedená tvrzení vlastně specifikují existenci jistých (datových) funkcí. Pojem funkce omezuje k dané hodnotě počet vztažených hodnot na nejvýše jednu. Tato tvrzení jsou tedy speciálním druhem integritních omezení (IO) a nazývají se funkční závislosti. Zapisují se např.

NÁZEV_K -> ADRESA, {NÁZEV_K, JMÉNO_F} -> DATUM,

ale také jednodušeji ABC -> D, AC -> ADH apod., jsou-li jména atributů jednopísmenná.

Funkční závislosti poskytly teoretikům RMD vděčný námět k bádání. Objevily se algoritmy, jak z množiny daných závislostí F odvodit všechny další, odvozené, které platí na týchž relacích, kde platí F. Algoritmicky lze přijít ze závislostí v F na všechny klíče schématu relace.

Pro projektanta databáze je třeba si uvědomit funkční podstatu uvažovaných závislostí. Mnoho praktických návodů či příruček hovoří o normálních formách a o závislostech, nicméně zapomínají zdůraznit fakt, že jde o funkční závislosti. Hezký příklad mi poskytnul kolega z praxe, kdy k atributům A a B udržoval v rámci jedné tabulky také atribut A+B. Jeho otázka zněla, zdali může narušit 3NF. Jistě může, protože 3NF je, jak uvidíme, založena na funkčních závislostech. Vypočítaný atribut C (daný jako A+B) totiž znamená, že je definována funkční závislost AB -> C.

Tranzitivní závislosti

Výskyt aktualizačních anomálií je spojen s výskytem speciálních funkčních závislostí, které se nazývají tranzitivní. Uvažujme národnost herce ve schématu

FILM(JMÉNO_F, HEREC, NÁRODNOST, ROK)

Evidentně platí JMÉNO_F -> HEREC -> NÁRODNOST. Tedy NÁRODNOST je na JMÉNO_F závislá "přes" atribut HEREC, tj. tranzitivně. Každý se může přesvědčit, že schéma FILM vede k podobným anomáliím jako schéma PROGRAM. Tam vadila také jistá tranzitivita, sice

{NÁZEV_K, JMÉNO_F} -> NÁZEV_K -> ADRESA

Dospět ke 3NF znamená odstranit tranzitivní závislosti neklíčových atributů, tj. těch, které se nevyskytují v žádném z klíčů schématu. Ne vždy však podobná tranzitivita vede k nevhodné situaci. Uvažujme na chvíli schéma relace

ZÁZNAM(RODNÉ_ČÍSLO, ČÍSLO_POJIŠTĚNÍ, HEREC)

Ve schématu ZÁZNAM jsou nyní dva klíče - RODNÉ_ČÍSLO a ČÍSLO_POJIŠTĚNÍ a tedy platí

ČÍSLO_POJIŠTĚNÍ -> RODNÉ_ČÍSLO a RODNÉ_ČÍSLO -> ČÍSLO_POJIŠTĚNÍ

Není však žádného důvodu schéma ZÁZNAM rozdělovat ve dvě, přestože obsahuje jisté tranzitivity jako např.

ČÍSLO_POJIŠTĚNÍ -> RODNÉ_ČÍSLO -> NÁRODNOST

Omezíme se tedy v definici tranzitivní závislosti X->Y->Z, kde X, Y, Z jsou množiny atributů, na takové, že vyloučíme případ, kdy Y->X. Nyní již lze vyslovit definici 3NF.

Nechť A je množina atributů. Schéma relace R(A) je ve 3NF,

jestliže každý neklíčový atribut z A není tranzitivně závislý

na žádném z klíčů schématu relace R.

Tuto definici lze vyjádřit alternativně bez pojmu tranzitivní závislosti.

Schéma relace R (A) je ve 3NF jestliže pro každou závislost X->C,

kde X je podmnožinou A a C je atribut z A, platí jedna ze tří podmínek:

1. C je obsaženo v X,

2. X obsahuje klíč schématu R,

3. C je prvkem nějakého klíče schématu R.

Lze se přesvědčit, že z jedné definice plyne druhá a naopak.

Někdy se hovoří i o 2NF. Podobně jako 3NF, i 2NF byla navržena Coddem, a to jako jistý přechodný článek ke 3NF. Zmíníme se o ní jen pro úplnost, protože jde o překonaný pojem. Jednalo se o to, že žádný neklíčový atribut nesmí být závislý na vlastní podmnožině klíče. Např. ADRESA splňuje tuto vlastnost vůči {NÁZEV_K, JMÉNO_F}. Současně však jde o tranzitivitu, jak jsme viděli výše, takže každé schéma ve 3NF je již automaticky ve 2NF.

Jak získat schéma databáze ve 3NF

Jeden ze způsobů, jak dojít ke 3NF, je založen na dekompozici. Schémata se (binárně) dekomponují tak dlouho, až jsou ve 3NF. Potřebujeme k tomu ale vždy znát dvě věci:

  • všechny klíče schématu,
  • všechny funkční závislosti.

Obojí vede obecně ke kombinatoricky komplikovaným problémům obtížně "ručně" řešitelným. Přestože existují poměrně jednoduše implementovatelné algoritmy vedoucí k dosažení 3NF, nejsou většinou součástí repertoáru funkcí dnešních nástrojů CASE. Nezbývá nic jiného, než analýzu funkčních závislostí provádět spíše intuitivně, být opatrný již při návrhu atributů typů entit na konceptuální úrovni. Existuje totiž povědomí, že převodem E-R schématu do schématu databáze v RMD obdržíme schémata ve 3NF. Bohužel toto tvrzení je pravdivé pouze zčásti. Navrhne-li totiž někdo typ entity FILM jako na obrázku 1, nezíská samozřejmě přímou transformací schéma relace ve 3NF.

Atribut Národnost je tranzitivně závislý na klíči. Jistě, má to svou logiku i na konceptuální úrovni. Národnost v daném kontextu totiž není atributem filmu, ale herce.

Jméno_f

FILM Jméno_h

Národnost

Rok

Obr. 1 Nevhodně navržený typ entity FILM

Jinými slovy řečeno, neodhalí-li projektant databáze nevhodné funkční závislosti na úrovni E-R modelování, pak ani výsledné databázové schéma nemůže být v pořádku.

Jiným problémem je, zdali je dekompozice smysluplná. Nejde jen o to, zdali ve vzniklých tabulkách jsou spolu smysluplně soustředěna data, která spolu nějak souvisejí. Problém může být hlubší, při dekompozici se totiž může něco ztratit. Cílem je, aby dekompozice byla v nějakém smyslu korektní. Pokusíme se tento pojem vysvětlit v některém z příštích čísel Databázové abecedy. Metodologicky může být přínosné, že cílem je “odseparovat” nevhodnou závislost od klíče, na kterém tranzitivně závisí.

Normalizace má nespornou výhodu v tom, že odstraňuje redundanci a tedy i aktualizační anomálie. Databáze normalizovaných relací zřejmě zabere méně místa než původní databáze. Na druhé straně zjednodušení údržby u normalizovaných relací je vykoupeno tím, že data jsou rozptýlena do více relací. Tento fakt může být na obtíž při dotazování, kdy je nutné data z více datových struktur spojit operací spojení dohromady.

V praxi se proto často pečlivě váží, zdali stát důsledně o 3NF či ne. Mnohdy převáží efektivita zpracování dotazů nad úsporou místa či nad problémy s aktualizacemi, kterých je třeba přiměřeně málo. Klasickým příkladem slouží statistické či vědecké databáze. Jde o to, že je užitečné udržovat v databázi i odvozená, tj. možná složitými algoritmy vypočítaná data.

Boyce-Coddova normální forma

Závěrem se ještě stručně zmiňme o Boyce-Coddově normální formě (BCNF). Jde o vylepšení 3NF v tom smyslu, že se netrvá na tom, aby se nevhodné závislosti týkaly pouze neklíčových atributů.

Definici BCNF ze vyjádřit takto:

Schéma relace R (A) je v BCNF, jestliže pro každou závislost X->C,

kde X je podmnožinou A a C je atribut z A, platí jedna ze dvou podmínek:

1. C je obsaženo v X,

2. X obsahuje klíč schématu R.

Klasický databázový příklad na BCNF poskytuje zjednodušená situace s poštovními směrovacími. Uvažujme schéma relace ADRESÁŘ(MĚSTO, ULICE, PSČ). Platí tu dvě netriviální funkční závislosti:

{MĚSTO, ULICE}-> PSČ, PSČ-> MĚSTO

Protože neplatí ani ULICE->  PSČ, ani MĚSTO->  PSČ, je {MĚSTO, ULICE} klíčem schématu. Klíčem je ovšem i {ULICE, PSČ}. Platí totiž PSČ->  MĚSTO, avšak nikoliv PSČ-> ULICE. Proto musíme atribut ULICE připojit k PSČ. Schéma tedy nemá žádný neklíčový atribut a je tedy ve 3NF. Nikoliv však v BCNF. Závislost PSČ-> MĚSTO škodí (k danému PSČ se město podle počtu ulic v relaci vícekrát opakuje). Tento fakt vede navíc k efektu, že nemůžeme evidovat města spolu se směrovacími čísly, aniž bychom znali nějakou ulici v městě. Převod do BCNF to umožní. ADRESÁŘ lze nahradit schématy

SEZNAM_ULIC(ULICE, PSČ), MĚSTA(PSČ, MĚSTO)

Pro projektanta databáze BCNF znamená rozumný přístup k návrhu. Díky historickému vývoji jsou normální formy obestřeny jistým tajemstvím, málokdo zná jejich přesnou definici a jemné rozdíly mezi nimi. BCNF může být praktickým cílem pro kvalitu návrhu. Neznamená totiž nic jiného, že jistá fakta se neukládají do databáze vícekrát.

 

 



<seznam dílů seriálu>   <COMPUTERWORLD>