Databázové systémy 1 (DB1) - Normální formy

Příklad

Název relace: výuka R(přednáška, učitel, místnost, hodina, student, známka) Relace je navržena nevhodně, protože obsahuje duplicity. Přednáška, učitel, místnost, hodina se musí opakovat tolikrát, kolik studentů přednášku navštěvuje.

�?ešení tohoto problému se nazývá normální formy. Při zjišťování normálních forem (NF) nebo při převodu do NF se musíme zabývat tzv. závislostí atributů.

Vymezení: Populací relace R budeme rozumět hodnoty atributů relace v daném čase (konkrétní naplnění).

Poznámka: funkční závislostí rozumíme vztah mezi atributy jedné relace.

Definice

Nechť A a B jsou atributy relace R, budeme říkat, že atribut B funkčně závisí na atributu A, jestliže pro všechny populace relace R platí pro libovolnou n-tici u,v elementem R: u.A=v.A => u.B=v.B, označení A->B.

Příklad

vyuka(P,U,M,H,S,Z), P->U (jestliže předmět učí jeden učitel), HM->P, HU->M. PS->Z, HS->M.

Poznámka: Z jedné populace nelze dokázat, že nějaká funkční závislost platí, ale lze dokázat, že neplatí. Funkční závislosti zjistíme z analýzy úlohy. Pomocí závislostí lze definovat klíč.

Je-li dáno R(o) o…množina atributů a K, K je elementem o, pak K je klíčem schémat R, jestliže spl�?uje obě vlastnosti:

• K -> o
• neexistují K’, K’ elementem K, K’ -> o

Význam definice

Na klíči jsou závislé všechny ostatní atributy relace.

Pravidla

Dávají podklad k postupu, jak z daných odhalených závislostí odvodit další závislosti.

1. Reflexivnost (triviální funkční závislost) – nechť je zadána množina X a Y podmnožina X, pak x -> X nebo XY (množina definuje svoji libovolnou podmnožinu).
2. Tranzitivita – X -> Y  a zárove�? Y -> Z => X -> Z
3. Spojování (kompozice) – X -> Y a zárove�? X -> Z => X -> YZ
4. Projekce (dekompozice) – X -> YZ => X -> Y a X -> Z
5. Doplnitelnost – X -> Y a zárove�? X elementem W => W -> Y, jiná varianta spojování: X -> Y a zárove�? W -> Z => XW -> YZ

Armstrongova pravidla jsou korektní, úplná a nezávislá.

Normální formy

1.normální forma (NF)

�?ekneme, že relace se nachází v 1.NF, pokud všechny komponenty n-tice jsou atomické (tj. nejsou opět relací).

2. normální forma (NF)

Relace R je v 2.NF, pokud je v 1.NF a pokud každý atribut, který nepatří k žádnému klíči relace R silně závisí na klíči relace R.

Silná funkční závislost: Nechť A->B, říkáme, že atribut B silně závisí na A, jestliže neexistuje žádná vlastní podmnožina A’ složeného atributu A taková, že platí A’ -> B.

Pokud hledám NF, tak 2.NF vyžaduje nalezení klíče a zabývání se závislostmi. Pokud je klíč jednoduchý atribut, je tabulka automaticky v 2.NF.

3. normální forma (NF)

Relace je v 3.NF, pokud je ve 2.NF a žádný atribut, který není složkou klíče relace X, není tranzitivně závislý na klíči relace R. 

Boyce-Codova normální forma 

Relace R se nachází v BCNF, jestliže pro každou funkční závislost tvaru X->Y, kde Y není v X, platí, že X je nadmnožinou nějakého klíče X v R klíče. Jestliže je v 3.NF nemusí být v BCNF. Zkoumá atributy, ať jsou v klíči nebo nejsou v klíči (rozdíl v 3.NF) �?ešení: vazbu, která kazí BCNF dám do samostatné tabulky.

4. normální forma

Multizávislost – tak jako ve funkční závislosti odpovídá dané hodnotě atributu 1 hodnota jiného atributu u multizávislosti odpovídá 1 hodnotě množina hodnot.

Multizávislost  (množina hodnot závisejících na 1 hodnotě jiného atributu) nám vadí jedině v kontextu na jiné atributy relace.

Definice – označme nejprve Y(x) množinu Y-hodnot přiřazených v daný moment k Y-hodnotě x. Nechť A,B,C jsou podmnožiny O (O – atributy relace) takové, že C = O – A – B. Pak B multizávisí na A, jestliže pro každou AC-hodnotu ac je B(ac)=B(a). Daný fakt či tvrzení nazýváme multizávislost B na A a označujeme   A ->> B. Je-li C prázdná množina, nazývá se multizávislost A->>B triviální.

Definice 4.NF – říkáme, že schéma relace R je ve 4.NF, jestliže pro každou netriviální multizávislost X->>platí, že X je nadmnožinou nějakého klíče schématu R.

Věta – mějme schéma R(A,B,C), kde A,B,C jsou množiny atributů a funkční závislost B->C. Rozložíme-li R na schémata R1(B,C) a R2(A,B), takto provedená dekompozice je bezztrátová.

Bezztrátovost – je-li dána relace R a její projekce na atributy BC a AB, pak spojením těchto projekcí získáme zpátky relaci R.

5. normální forma (NF)

Vychází z principu, že relaci můžeme dekomponovat na více tabulek a samozřejmě dekompozice musí být bezztrátová. Relace se nachází v 5.NF, pokud neobsahuje závislost podle spojení. Pokud tam závislost je, měli bychom ji rozložit.

Poznámky k normálním formám

V praxi se zabývat návrhem do 3.NF. NF ano, ale přece jen zvážit, zda důslednost není přehnaná (v žádném případě nechceme velké množství 2 sloupečkových tabulek) – zpomalení práce s databází. Pokud bychom v návrhu vyrobili tabulku, která porušuje 3.NF, přehlédli jsme v návrhu nějakou vazbu.Převod do 2.(3.NF) znamená v ERA modelu přidat entitní množinu připojenou vazbou 1:N.