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)

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.

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.

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.

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.