Teorie relačních databází: Normalizace

2.8. 2007 Vebloud Teorie DB

Normalizace ER modelu je sada pravidel, jak byste měli postupovat při transformaci struktury entit a relací ER modelu na strukturu fyzického uspořádání tabulek a relací v databázi.

Proč normalizovat? Normalizace je odstranění redundantních(opakujících) se dat, omezení složitosti (rozloženít složité relace na dvojrozměrné tabulky) a zabránění tzv. aktualizačním anomáliím (např. abychom smazáním všech knih autora nepřišli o data o autorovi). Což by mělo vést k databázi přehlednější, rozšiřitelnější a výkonnější.

Normalizace by měla vést k vzniku tabulek, které lze snadno udržovat a efektivně se na ně dotazovat. Normalizované schéma musí zachovat všechny závislosti původního schémat a relace musí zachovat původní data, což znamená, že se musíme pomocí přirozeného spojení dostat k původním datům.

Normální formy:

• 1.NF – První normální forma
• 2.NF – Druhá normální forma
• 3.NF – Třetí normální forma
• BCNF – Boyce Coddova normální forma
• 4.NF – Čtvrtá normální forma
• 5.NF – Pátá normální forma

1. normální forma (1.NF)

Relace je v první normální formě, pokud každý její atribut obsahuje jen atomické hodnoty. Tedy hodnoty z pohledu databáze již dále nedělitelné. Například v relaci obsahující data o nějaké osobě budeme chtít mít více telefonních čísel:

S takovouto tabulkou by byla spousta problémů, například by se dost špatně prováděly změny čísel, případně vyhledávání podle telefonního čísla.

Aby tabulka byla v 1NF musíme buďto rozdělit atribut telefon do více atributů (pouze za předpokladu, že jsme si jisti, že se množství telefonních čísel nezvýší), nebo oddělit telefoní čísla do samostatné tabulky, což já osobně preferuji, protože je to podstatně flexibilnější řešení:

2.normální forma (2.NF)

Relace se nachází v druhé normální formě, jestliže je v první normální formě a každý neklíčový atribut je plně závislý na primárním klíči, a to na celém klíči a nejen na nějaké jeho podmnožině. Z čehož vyplívá, že druhou normální formu musíme řešit pouze v případě, že máme vícehodnotový primární klíč. Zní to poněkud složitě, ale nic na tom není, opět pomůže příklad:

V tabulce zboží v obchodě bude název zboží, výrobce, telefon na výrobce, cena zboží a množství na skladě.

Klíčem této relace je kombinace atributů Název a Výrobce. Telefon výrobce ovšem není závislí na celém klíči, ale pouze na atributu výrobce. To by vedlo k aktualizační anomálii a to k té, že pokud by se vymazaly veškeré výrobky od výrobce Milka, ztratilo by se telefoní číslo na výrobce Milka, což není zrovna žádané. Řešením je opět rozpad na dvě tabulky:

3.normální forma (3.NF)

V této formě se nachází tabulka, splňuje-li předchází dvě formy a žádný z jejich atributů není tranzitivně závislý na klíči. Jiné vyjádření téhož říká, že relace je v 3.NF, pokud je ve 2.NF a všechny neklíčové atributy jsou navzájem nezávislé.

Opět definice, která zní nesrozumitelně, ale její použití je vlastně jednoduché. Tranzitivní závislost je taková závislost, mezi minimálně dvěma atributy a klíčem, kde jeden atribut je funkčně závislý na klíči a druhý atribut je funkčně závislý na prvním.

Koukám, že jsem tomu opět moc nepomohl, takže nejlepší bude příklad:

Řekněme, že firma chce uchovávat informace o zaměstnancích, takže vytvoříme relaci Zaměstnanec s atributy r.č. (primární klíč), Jméno, Příjmení, Město, PSČ, Funkce a Plat, zbytek adresy vynecháme, protože pro příklad není důležitý.

Z této tabulky je vidět kromě závislosti všech atributů na klíči ještě závislost PSČ a Města a závislost Platu na Funkci. Aby jsme si to ukázali pomocí obou vyjádření definic. Závislost r.č -> Město -> PSČ je tranzitivní závislost PSČ na klíči, stejně tak závislost r.č. -> Funkce ->Plat. Pochopitelnější je asi druhé vyjádření, podle něj jsou závislosti Město -> PSČ a Funkce ->Plat přesně ty, které porušují sousloví: "všechny neklíčové atributy jsou navzájem nezávislé". Řešením problému je opět rozpad na více relací, v tomto případě dokonce na 3, protože jsme 3.NF porušily rovnou dvakrát.

Boyce Coddova normální forma (BCNF)

Boyce/Coddova normální forma se pokládá za variaci třetí normální formy a dokonce je původní definicí 3.NF tak jak byla publikována v 70 letech. Je vymezena stejnými pravidli jako 3.NF forma, říká, že musí platit i mezi hodnotami uvnitř složeného primárního klíče.

Relace se nachází v BCNF, jestliže pro každou netriviální závislost X -> Y platí, že X je nadmnožinou nějakého klíče schématu R.

Zní to poněkud šíleně, ale ničeho se nebojte, k tomu, aby byla porušena BCNF musí být splněno několik podmínek a to poměrně specifických:

• Relace musí mít více kandidátních klíčů
• Minimálně 2 kandidátní klíče musí být složené z více atributů
• Některé složené kandidátní klíče musí mít společný atribut.

Nejsnáze Boyce/Coddovu normální formu pochopíme s pomocí funkčních závislostí. Boyce/Coddova normální forma v podstatě říká, že mezi kandidátními klíči nesmí být žádná funkční závislost. Jak známo, nejlépe se definice chápou na příkladech, takže mějme relaci adresář:

Původní příklad byl odstraněn, byl chybný, tento jsem si vypůjčil ze script Databázové systémy, Prof. RNDr. Jaroslav Pokorný CSc., Ing Ivan Halška

V této relaci platí dvě netriviální funkční závislosti:
{Město,Ulice} -> PSČ a PSČ -> Město
Protože neplatí Ulice -> PSČ ani Město -> PSČ, tvoří dvojice {Město, Ulice} klíč schématu. Klíčem je ale i {Ulice, PSČ} platí totiž PSČ -> Město, nikoliv však PSČ -> Ulice. Tudíž je {PSČ, Ulice} kandidátním klíčem schématu. Schéma má všechny atributy atomické a nemá žádný neklíčový atribut a tudíž je v 3.NF, ale není v BCNF. Tento fakt vede k tomu, že nelze evidovat města s PSČ bez znalosti Ulice a krom toho jsou v relaci redundantní data, pokud by se evidovalo velké množství ulic v jednom městě, začal by to být problém.

Klasické řešení, rozpad na dvě tabulky. Vzhledem k tomu, že neplatí PSČ -> Ulice, musíme spojit PSČ a Ulice. Výsledkem tudíž budou relace Města(PSČ, Město) a Ulice(PSČ, Ulice)

Čtvrtá normální forma (4.NF)

Tabulka je ve čtvrté normální formě, je-li v BCNF a popisuje pouze příčinnou souvislost (jeden fakt). Sice jednoduché vyjádření bez složitých definic, ale poněkud nicneříkající, takže zkusíme jinou definici: " Relace je ve čtvrté normální formě, pokud je v Boyce/Coddově normální formě, a navíc všechny vícehodnotové závislosti jsou zároveň funkčními závislostmi z kandidátních klíčů. " Mno koukám, že jsem tomu moc nepomohl, tak zkusíme definici a příklad ze skript Tvorba datového modelu v prostředí strategických informačních systému, Prof. Ing. Jindřich Kaluža, CSc. : "ve čtvrté normální formě je relace tehdy, je-li v BCNF a všechny vícehodnotové závislosti obsažené v relaci jsou zároveň funkčními závislostmi. Vícehodnotovou závislost atributů lze definovat následovně: V relaci R, která je v BCNF, s atributy A, B, C nastává vícehodnotová závislost atributu B na atributu A právě tehdy, jestliže množina hodnot B přiřazená dvojici hodnot A, C závisí jen na hodnotě atributu A a je nezávislá na hodnotě atributu C."

Tak teď už je to definice přesná a všeříkající, ale bez perfektní znalosti všech použitých pojmů je opět špatně pochopitelná, tudíž příklad si vypůjčím vysvětlení a příklad ze skript Databázové systémy, Vostrovský, Merunka:

Čtvrtá normální forma se zabývá vztahy uvnitř složeného primárního klíč. Pokud je v tabulce složený primární klíč, může se stát, že některé hodnoty tohoto klíče jsou na sobě nezávislé, ale tím, že spolu tvoří klíč, vzniká falešná souvislost mezi těmito hodnotami a nemohou existovat nezávisle na sobě, což není v souladu s modelovanou realitou. 4.NF proto vyžaduje, aby klíč tvořily jen ty hodnoty, které mají skutečnou vzájemnou souvislost.

Mějme relaci zachycující vztah zaměstnance, kvalifikace a úkolu: Pracovní zařazení(Zaměstnanec, Úkol, Kvalifikace)

Všechny atributy dohromady tvoří klíč schématu a neexistuje mezi nimi žádná funkční závislost, tudíž je v BCNF a všechno vypadá ideálně, ale není tomu tak. I když se dá předpokládat, že atributy Kvalifikace a Úkol jsou na sobě nezávislé, tak tabulka neumožňuje zachytit kvalifikaci zaměstnance, který nemá přiřazen žádný úkol (a úkolujte někoho o kom netušíte co umí) a nelze ani úkolovat zaměstnance bez kvalifikace. Krom ztráty informací se rozkladem vyvarujeme i redundance dat. Tudíž je opět nutno tabulku rozdělit a to na dvojici: Kvalifikace (Zaměstnanec, Kvalifikace), Úkol (Zaměstnanec, Úkol).

Do rozložených relací jsem záměrně přidal data, která v původní relaci nebyla, ale měla by být. Krásně se tím ukazuje, jak snadné je teď najít project m,anagera na tvorbu podnikového IS, ale zkuste si to v nenormalizované tabulce, když pan Cibula zrovna nemá přidělen žádný úkol.

Pátá normální forma (5.NF)

Relace je v páté normální formě, pokud je ve čtvrté a není možné do ní přidat další atribut (skupinu atributů) tak, aby se vlivem skrytých závislostí rozpadla na několik dílčích relací.

A už je to tu zase, poměrně normálně znějící definice, ale opět docela naprd. Takže zkusíme jinou:

Relace je v páté normální formě jestliže je ve 4NF a nemůže-li být dále bezeztrátově rozložena. Jinými slovy relace, která má n klíčových atributů (n >= 3) a která se rozloží na relace o n-1 klíčových atributech, nemůže být opětovně spojena operací přirozeného spojení do jedné relace, aniž by došlo ke ztrátě informace.

To už začíná být trošku lepší, ale zkusme to ještě jednou trošku jinak:

Pátá normální forma se týká primárních klíčů, které jsou tvořeny nejméně třemi atributy. V případě, že mezi těmito hodnotami v klíči existují párové cyklické závislosti, tak je třeba tyto závislosti extrahovat do samostatných tabulek, ale původní tabulku je v některých případech třeba zachovat!

To byli definice, teď zkusím trošku jiný popis. K porušení 5NF musí opět být splněno několik podmínek a to dost specifických. Relace musí být ve 4NF a musí mít klíč složený z třech nebo více atributů a mezi nimi musí být párové cyklické závislosti, ale nikoliv funkční, ani multizávislosti, to by nebyla ve 4NF. Typicky se jedná o vztah třech a více tabulek, kde platí vztahy M:N:O:M a tento vztah je vytvořen jednou relací. 5NF řeší redundanci dat a možnou ztrátu závislostí.

Myslím, že příklad opět pomůže. Mějme firmu, která provozuje síť obchodních zástupců strojírenských firem pro celou Evropu. Ta potřebuje vědět, který zástupce zastupuje kterou firmu a v jakých státech a ve kterých státech působí firmy. Předpokládejme, že o Zástupcích, Firmách i Státech máme vytvořeny informační relace a použité hodnoty jsou pouze cizí klíče, kterými řešíme vztahy mezi těmito relacemi. Zdánlivě jednoduché:

Problém vypadá na první pohled vyřešeně, ale dle naší definice páté normální formy tomu tak není, neboť zde existují závislosti Zástupce-> Firma -> Sát -> Zástupce a to jsou párové cyklické závislosti. Mohlo by se stát, že s vymazáním obchodního zástupce, by se mohlo ztratit informace o tom, že firma prodává v zemi, kde jí zastupoval pouze ten smazaný zástupce a to je pochopitelně nežádoucí. Stejně tak odebrání firmy může způsobit ztrátu informace o působení obchodního zástupce v některé zemi a to je taktéž nežádoucí. Takže musíme provést rozpad tři relace, které nám pokryjí všechny vztahy.

Zdá se, že problém je vyřešen, nicméně není. Jedna z definic říká, že relace je v páté normální formě pokud již nelze bezeztrátově rozdělit a menší relace. Důležité je slovíčko bezeztrátově. Protože pokud si spojíme výsledné tabulky pomocí přirozeného spojení, nedostaneme původní výsledek. Dostaneme úplně jiné informace.

Takže jak z toho, tříatributová relace není dobře, tři dvouatributové jsou taky špatně. A co takhle nechat oboje? Ve své podstatě udržuje každá relace jinou informaci. Zastupuje nám říká, které firmy kdo zastupuje, Pusobi říká, kde nám pracuji zástupci a Zastoupeni říká, kam prodávají firmy a ObchodniZastoupeni, říká kdo koho kde.

Pátá normální forma v tomto příkladu nebyla ani tak o špatném převodu konceptu do fyzického modelu databáze, jako spíš o neuvědomění si skutečných vztahů. Ve své podstatě jsem se snažili vymodelovat tuto situaci:

Závěr

Normalizovat je určitě potřeba a čím složitější databáze a čím více dat, tím více je potřeba normalizovat. Ale i tady platí všeho s mírou. Například u příkladu u 3.NF by firma s několika desítkami zaměstnanců asi neměla potřebu dávat PSČ do další tabulky a bylo by to zbytečné. Ale v tabulce zákazníků některého z mobilních operátorů s milióny zákazníků to už význam určitě má.