COMPUTERWORLD
pod kapotou
4. normální forma

Již léta jsem neslyšel mezi projektanty databází o 4NF relací. Až nedávno jsem se stal aktérem konzultace s profesionálem, na kterém zadavatel žádal, aby navržená databáze měla relace ve 4NF. Tento požadavek, ať už byl formulován z jakýchkoliv důvodů, se stal motivací pro dnešní Databázovou abecedu. Nejde o to, že je nutné se v praxi 4NF zabývat (ukážeme si, že spíše ne), nicméně je dobré vědět, o co vlastně jde, zdali o něco nepřicházíme, neuvažujeme-li tuto vlastnost relační databáze ve svém návrhu.

První věc, kterou je třeba si uvědomit, je typ závislostí, na kterých je 4NF založena. Nejde totiž o funkční závislosti, ale o tzv. multizávislosti. Uvažujme schéma relace R(A). Jsou-li dány dvě množiny atributů C, D z A, pak multizávislost D na C vychází z intuitivní představy, že jedné C-hodnotě se přiřadí několik D-hodnot. Tento jev se v praxi vyskytuje běžně a v některých případech nečiní žádné potíže.

Uvažujme nejprve tabulku ATELIÉR s atributy JMÉNO_A a REŽISÉR. Zaměstnává-li ateliér více režisérů, pak zřejmě REŽISÉR multizávisí na JMÉNO_A. Tato multizávislost je ovšem triviální a nevede k žádným problémům z hlediska provozu tabulky ATELIÉR. Přidejme nyní do schématu ATELIÉR atribut UMÍSTÉNÍ_A. Tento atribut je ovšem nezávislý na režisérech, znamená, že jeden ateliér je někde umístěn a to dokonce navíce místech. Tedy klíčem takto rozšířeného schématu je množina všech atributů, schéma je ve 3NF a dokonce v BCNF. Jednu relaci ATELIÉR* ukazuje tabulka 1.

ATELIÉR

JMÉNO_A

REŽISÉR

UMÍSTÉNÍ_A

 

KOLIBA

Dufek

Hostivař

 

KOLIBA

Smolík

Řepy

 

KOLIBA

Dufek

Řepy

 

KOLIBA

Smolík

Hostivař

 

STODOLA

Menzel

Barrandov

 

STODOLA

Menzel

Háje

Tab. 1 Tabulka v BCNF s anomáliemi

Každý vidí, v čem je problém. Objevuje se zcela nevhodná redundance, protože v jedné tabulce se dávají do souvislosti nesouvisející fakta, založená na dvou multizávislostech. Problémy s aktualizací takové relace jsou zřejmé. Vzhledem k nezávislosti informací o režisérech a umístěních ateliérů je vhodné provést dekompozici schématu ATELIÉR do dvou schémat:

REŽISÉŘI_A(JMÉNO_A, REŽISÉR)

POLOHA(JMÉNO_A, UMÍSTĚNÍ_A)

Data, která se umístí do těchto tabulek se snadno získají projekcemi na atributy původní tabulky, tj, jako ATELIÉR [ JMÉNO_A, REŽISÉR] a ATELIÉR[ JMÉNO_A, UMÍSTĚNÍ_A] . Lze si povšimnout, že spojíme-li obě tabulky přirozeným spojením (přes atribut JMÉNO_A), obdržíme zase původní tabulku ATELIÉR*. Tato vlastnost je pro multizávislosti zásadní. Dají se dokonce pomocí spojení definovat.

Multizávislost C ->> D v R(A), o které se zde bavíme, tedy nějak závisí na kontextu tvořeným zbytkem atributů, tj. atributy z A - C - D. Formálně lze multizávislost definovat takto:

 

Pro schéma relace R(A), kde A = { C,D,X} , X = A - C - D, C ->> D je multizávislost nad A, jestliže pro každou přípustnou relaci R* platí R* = R* [ C,D] * R* [ C,X] . Je-li X prázdná množina, nazývá se multizávislost C ->> D triviální. Říkáme, že D multizávisí na C.

Původní definice multizávislostí je trochu nepřehlednější a nebudeme ji zde uvádět. Naznačuje, jak jsou množiny hodnot přiřazené hodnotám C nezávislé. Prakticky jde o to, že se např. pro hodnotu KOLIBA v našem příkladu musí v řádcích tabulky prokombinovat všechny možnosti mezi režiséry Koliby a umístěními Koliby. Všimněme si, že když odstraníme z tabulky 1 řádek (KOLIBA, Smolík, Hostivař), okamžitě přestane platit multizávislost v uvedeném smyslu. Provedeme-li dekompozici REŽISÉR_A a POLOHA takto upravené tabulky (nazvěme ji tabulka 2) a opětné spojení dílčích relací, ve výsledku se objeví inkriminovaný řádek, což je ve sporu s definicí (výsledkem má být tabulka 2).

Teoreticky byly multizávislosti studovány v 2. polovině 70. let. Byla pro ně zkonstruována také odvozovací pravidla. Úplný a korektní soubor odvozovacích pravidel byl dokonce sestaven i pro "smíšené" závislosti, tj. pro základní množinu závislostí obsahující jak funkční závislosti, tak multizávislosti. Pro praktickou manipulaci při návrhu relačního schématu databáze jde ovšem o dost komplikované mechanismy. Jednoduché je pravidlo replikace, které říká,

  • jestliže A -> B, pak i A ->> B

Tedy funkční závislosti jsou speciálním případem multizávislostí. Z dalších pravidel uvedeme pouze pravidlo o komplementu, které přímo vyplývá ze symetrie definice multizávislosti.

  • je-li R(C,D,X) a X = A - C - D, pak platí, jestliže C ->> D, pak i C ->> D.

Platnost pravidla komplementu potvrzuje i náš příklad ATELIÉR.

Nyní již lze tušit, jak asi bude vypadat definice 4NF.

Schéma relace R (A) je ve 4NF, jestliže je v BCNF a každá

multizávislost nad A je triviální.

Podobně jako u 3NF nebo BCNF se ke 4NF přiblížíme vhodnou dekompozicí, která separuje netriviální multizávislosti do různých relací.

Projektant může namítnout, že objevit multizávislost podobného typu jako předváděl příklad s ateliérem, je triviální záležitost. To je pravda. Jakmile ale je ve schématu relace atributů více, je již problém značně složitější. Pěkný školní příklad (týkající se navíc školy) ukazuje Ullman ve své známé učebnici Principles of Database and Knowledge-Base Systems.

Schéma databáze je VÝUKA(PŘEDNÁŠKA, UČITEL, HODINA, MÍSTNOST, STUDENT, ZNÁMKA). Tuto tabulku si snadno dovedeme představit jako pohled v SQL sloužící úřednici na studijním oddělení. Jako databázisti budeme oprávněně protestovat proti uložení takovéto tabulky jako základní relace. Zmiňme pouze, že jediným klíčem je dvojice atributů { STUDENT, HODINA} . Analýzou lze zjistit, že zde existuje multizávislost PŘEDNÁŠKA ->> { HODINA, MÍSTNOST} . Dvěma dekompozicemi bychom pak obdrželi schéma relační databáze (klíče neuvádíme)

R1(PŘEDNÁŠKA, HODINA, MÍSTNOST),

R2(PŘEDNÁŠKA, UČITEL),

R1(PŘEDNÁŠKA, STUDENT, ZNÁMKA),

které je smysluplné a nelze ho získat pouze na základě znalosti funkčních závislostí a postupnými dekompozicemi do BCNF (či 3NF).

Existují ovšem i další zdroje multizávislostí. Představme si E-R model, kde jsou povoleny vícehodnotové atributy (budeme je označovat hvězdičkou). Nechť typ entity REŽISÉR má kromě atributů JMÉNO_R, ADRESA apod. vícehodnotové atributy JAZYKY (které ovládá) a ŠKOLY (které vystudoval). Na obrázku 1 je vidět grafické vyjádření.

 

 

JMÉNO_R

REŽISÉR ADRESA

JAZYKY

ŠKOLY Obr. 1 Typ entity s vícehodnotovými atributy

Vytvořit z daného E-R diagramu jednu tabulku REŽISÉR by vedlo k relaci, která nebude ve 4NF. Jejím klíčem by zřejmě byla množina atributů { JMÉNO_R, JAZYKY, ŠKOLY} . Nevýhoda odpovídajících tabulek je zřejmá: mnohonásobná redundance dat. Např. pro jednoho režiséra hovořícího třemi jazyky se třemi školami jeho vzdělání bychom potřebovali 6 řádků (se stále se opakující jednou adresou).

Ne nadarmo se v praxi proto vyskytují verze E-R modelů s jednoduchými atributy. V našem příkladu to znamená, že JAZYK a ŠKOLA budou samostatné entity s jedním atributem. Schéma relační databáze pak bude obsahovat, jak lze očekávat, 3 schémata relací ve 3NF, např. REŽISÉR, JAZYKOVÉ_ZNALOSTI, VZDĚLÁNÍ. Co z toho plyne? Odstraňování vícehodnotových atributů na konceptuální úrovni vede ke 4NF odpovídajících relací. Kdo si ovšem složitějších multizávislosti při návrhu na konceptuální úrovni nevšimne (viz třeba příklad VÝUKA), má smůlu.

Poznamenejme však, že přirozené vyjádření reality na obrázku 1 by bylo v praxi rovněž akceptovatelné, pouze algoritmus transformace do RMD by musel být trochu složitější. Povzbuzením nám může být fakt, že dnešní objektové databáze umožňují přímou reprezentaci takovýchto struktur.

Vzhledem k obtížnosti objevování multizávislostí se těžko dosahuje 4NF. Taková je však již profese projektanta databází. Objevování a chápání zákonitostí v reálném světě je empirická záležitost vyžadující zkušenosti, dobrou intuici, porozumění. Pak lze teprve nasadit formální prostředky, které odhalí další závislosti a pomohou dospět k smysluplnému návrhu. Škoda, že současné počítačové prostředky podporující návrh (CASE systémy) toho umí tak málo.



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