Normalizace

Normalizace je proces organizování dat v databázi. Představte si to jako úklid skříně – chceme, aby každá věc měla své logické místo a nic jsme neměli dvakrát.

Hlavní cíle normalizace:

• Odstranění redundance: Abychom neukládali stejnou informaci (např. adresu zákazníka) na tisíci místech. Šetříme místo a zrychlujeme práci. Odstraňujeme také nežádoucí závislosti mezi atributy.
• Konzistence dat (Data Integrity): Když se zákazník přestěhuje, změníme adresu jen na jednom místě, ne v každé jeho objednávce zvlášť.
• Reversibilita: I když data rozdělíme do více relací, musíme být schopni je pomocí vztahů opět spojit dohromady, aniž bychom ztratili informace.

Celá normalizace se bude týkat vždy závislostí mezi atributy jedné relace, kterou, identifikujeme-li problém, budeme rozdělovat. Pojďme se tedy nyní ponořit do pojmů týkajících se závislostí mezi atributy.

Závislosti atributů

Abychom vůbec mohli přistoupit k normalizaci, musíme nejprve pochopit vztahy mezi jednotlivými atributy v relaci.

Funkční závislost

Pokud znám hodnotu A, znám jednoznačně i hodnotu B. A → B

Říkáme, že B vyplývá z A (pozor nikoliv obráceně) nebo A určuje B.

Příklad: představme si pod A rodné číslo, pod B jméno. Jestliže známe A, jednoznačně nám z něj vyplývá B, tj. například z rodného čísla 0712152101 nám jednoznačně vyplyne Antonín.

Plná funkční závislost

Týká se situace, když klíč (A) je složený (z více atributů).

Atribut B závisí na celém klíči A, nikoliv pouze na jeho části. (A₁, A₂) → B

Příklad: představme si klíč složený z částí StudentID (A₁) a Předmět (A₂) – pak z něj můžeme vyvodit hodnocení na konci roku (B). Jestliže známe konkrétního studenta, například 2023C23 a předmět DEJ, můžeme z něj vyvodit známku 2.
Naopak z tohoto klíče nemůžeme odvodit název předmětu, protože ten závisí pouze na A₂, nejedná se tedy o plnou funkční závislost.

Částečná funkční závislost

Týká se opět situace, kdy klíč (A) je složený (z více atributů).

Atribut B závisí pouze na části klíče A, nikoliv na celém složeném klíči. A₁ → B, resp. A₂ → B

Příklad: představme si klíč složený z částí StudentID (A₁) a Předmět (A₂) – pak z něj můžeme vyvodit hodnocení na konci roku (B). Jestliže známe konkrétního studenta, například 2023C23 a předmět DEJ, můžeme z A₁ vyvodit například jméno studenta nebo jeho příjmení, z A₂ pak například název předmětu nebo hodinovou dotaci.

Tranzitivní závislost

Jestliže A určuje B a B určuje C, pak A tranzitivně určuje C. A → B ∧ B → C ⇒ A → C

Příklad: představme si ObjednavkaID jako A, ZakaznikID jako B a Mesto jako C. Můžeme říct, že z A jednoznačně vyplývá B, protože každou objednávku udělal vždy jeden konkrétní zákazník. Také můžeme říct, že z B jednoznačně vyplývá C, protože zákazník má jednoznačně stanovené město, kam objednávku doručit. V tom případě můžeme říct, že z objednávky (A) můžeme vyvodit město doručení (C) – nikoliv sice napřímo, ale tranzitivně (přes prostředníka).

Vícehodnotová závislost

Týká se situace, kdy klíč (A) je složený ze třech nebo více atributů.

Vícehodnotová závislost nastává, když jeden klíčový atribut (A₁) určuje více hodnot u dvou jiných atributů (A₂ a A₃), přičemž A₂ a A₃ jsou na sobě vzájemně nezávislé.

Lidsky řečeno – v rámci klíče nemíchejme hrušky s jablky.

Příklad: Představme si relaci, kde primární klíč je složený z atributů (Student, Project, Hobby). Můžeme si představit i konkrétní hodnoty – student Lohnický pracuje na projektu Web Mlsná Koza a na projektu MongoDB. Jako koníčky má šachy a pěší turistiku. Abychom to vše v jedné relaci zachytili, museli bychom to ale zkombinovat:

Atributy Project (A₂) a Hobby (A₃) spolu totiž nesouvisejí – nemůžeme říct, že všichni, kteří pracují na projektu Web Mlsná Koza mají jako koníček šachy a z projektu MongoDB vyplývá jednoznačně pěší turistika. Abychom to tedy zachytili do jedné relace, museli jsme udělat kartézský součin všech možných hodnot. Teď si představte, že velmi aktivní student Lohnický se přihlásí do dalšího projektu nebo se začne věnovat dalšímu koníčku. Ufff.

Normální formy

Máme celkem 6 normálních forem:

• 1. NF: Jedinečnost polí
• 2. NF: Závislost na celém primárním klíči
• 3. NF: Bez tranzitivních závislostí
• 3.5 NF: Boyce-Codd
• 4. NF: Nezávislost polí
• 5. NF: Další bezztrátový rozklad již možný

přičemž platí, že relace je v dané normální formě, jestliže je již ve všech předchozích normálních formách.

První normální forma

Relace je v 1. NF, jestliže každý atribut v relaci představuje jedinečný typ informace.

Toto pravidlo může trochu připomínat podmínku relačnosti ohledně elementárnosti jednotlivých hodnot. Například není možné mít několik lidí vypsaných v jednom atributu Absolventi. Není možné napsat několik hodnot do jednoho atributu Složení. Není možné napsat ulici, číslo popisné, město a PSČ do jednoho atributu Adresa.

Tato relace například nesplňuje první normální formu:

Vidíme totiž hned několik chyb:

• jméno a příjmení nesmí být uloženo v jednom atributu Name
• v atributu Cellphone nemohou být zároveň dvě telefonní čísla

Aby relace splnila 1. NF, musíme relaci rozdělit minimálně na dvě:

Druhá normální forma

Relace je v druhé normální formě, jestliže je v první normální formě a všechny neklíčové atributy v relaci závisí na celém primárním klíči (v relaci nemáme žádnou částečnou funkční závislost).

Například tato relace nesplňuje druhou normální formu:

Rozdělíme si nejprve atributy relace na klíčové a neklíčové:

• Subject (součást primárního klíče, označený #) = klíčový
• Year (součást primárního klíče, označený #) = klíčový
• Teacher = neklíčový
• Subject_Name = neklíčový

Nyní se ptáme u všech neklíčových atributech, na jakých klíčových atributech závisejí:

• Teacher = závisí na Subject i Year (stejné předměty v různých letech učí různí vyučující) = OK
• Subject_Name = závisí na Subject, ale nezávisí na Year (název vždy odvodíme pouze ze zkratky) = částečná funkční závislost = chyba

Pro splnění druhé normální formy je tedy nutné relaci rozdělit nejméně na dvě:

Rozdělením jsme dokonce ušetřili místo (odstranili redundanci), protože název předmětu máme uložený pouze jedenkráte.

Třetí normální forma

Relace je ve třetí normální formě, jestliže je ve druhé normální formě a všechny její neklíčové atributy závisí pouze na klíčových atributech a nikoliv mezi sebou (relace v sobě nemá tranzitivní závislost).

Například tato relace nesplňuje třetí normální formu:

Nyní procházíme jeden atribut za druhým a ověřujeme, že závisí výlučně na primárním klíči:

• ZanrID = ID žánru, žánr odvodíme z konkrétního filmu, platí FilmID → ZanrID = OK
• Zanr = název žánru, odvodíme z ZanrID, čili FilmID → ZanrID → Zanr = tranzitivní závislost = chyba
• Nazev_Filmu = název filmu odvodíme z FilmID, platí FilmID → Nazev_Filmu = OK
• Delka = délku filmu odvodíme z FilmID, platí FilmID → Delka = OK

Aby relace splňovala třetí normální formu, je tedy nutné ji rozdělit minimálně na dvě relace:

Boyce-Coddovo pravidlo

Relace je v BCNF, jestliže je ve 3. NF a cokoliv něco určuje, musí být klíčem.

Pojďme si opět ukázat problematickou relaci, která je ve 3. NF, ale nikoliv v BCNF:

Můžeme říci, že platí:

• (Court, Start Time) –> End Time (jestliže víme kde a od kdy, odvodíme z toho do kdy)
• (Court, Start Time) –> Rate Type (v daném čase na daném kurzu platí konkrétní tarif)
• Rate Type –> Court (vidíme, že SAVER a STANDARD je pro kurt 1, kdežto PREMIUM pro kurt 2)

Poslední závislost je ale nesprávná, protože nemůžeme odvodit Court z Rate Type – Rate Type není klíč.

Abychom tedy relaci opravili, je potřeba ji rozdělit do dvou:

Čtvrtá normální forma

Relace je ve 4. NF, jestliže je v BCNF a její složený primární klíč není tvořen z nezávislých atributů (v klíčových atributech nesmí být vícehodnotová závislost).

Tuto normální formu tedy ověřujeme pouze v případě, že primární klíč je tvořen třema a více atributy.

Například tato relace není ve 4. NF:

Pojďme prozkoumat jednotlivé dvojice klíčových atributů, zda-li spolu souvisejí:

• IDStudent a IDCollege: souvisí, student chodí na konkrétní fakultu = OK
• IDStudent a IDHobby: souvisí, student má konkrétní koníček = OK
• IDCollege a IDHobby: nesouvisí – fakulta s koníčkem nemá nic společného = chyba

Vícehodnotovou závislost tedy odstraníme rozdělením relace:

Pátá normální forma

Relace je v 5. NF, pokud je ve 4. NF a dále již nelze bezztrátově rozložit.

Představme si opět relaci, která má složený klíč (minimálně ze třech atributů):

V této relaci vidíme tři atributy, které tvoří primární klíč. Mohli bychom si je představit také jako tři dvojice:

• Supplier – Customer
• Supplier – Part
• Customer – Part

Pojďme tedy zkusit tuto relaci rozložit na tři relace podle těchto dvojic:

Nyní si zkusíme tyto tři relace opětovně složit dohromady. Dostaneme:

Ale pozor! Dostali jsme o jeden záznam více – S1 dodává VW, S1 vyrábí volanty a VW nakupuje volanty – čili všechny tři dvojice záznamů jsme z rozložených relací dostali – přesto podle původní relace vidíme, že VW od S1 volanty nenakupuje. Složením rozložených relací jsme tedy získali tzv. Ghost record (falešný záznam) (v tabulce výše červeně).

Tím jsme dokázali, že původní relaci již nelze dále bezztrátově rozložit, a tudíž původní relace již byla v 5. NF.