Přednáška předmětu KIV/DBM1
8. týden výuky, zastupující přednášející: Ing. Tomáš Kotouč

Normální formy, funkční závislost a multizávislost.

Doposud jsme se bavili o vztahu mezi několika tabulkami, jak na sebe tabulky vážou (1:1, 1:N, M:N) a jaké mají atributy. Nyní se budeme bavit o tom, že i mezi atributy je jistý vztah, který v určitých případech vede k rozkladu tabulky na více tabulek.

Základní pojmy potřebné pro pochopení Normálních forem:

• Funkční závislost
  • Máme relaci R a v ní dvě množiny atributů A a B, pak existuje funkční závislost B na A, jestliže jedné A-hodnotě se přiřadí nejvýše jedna B-hodnota.
  • Máme tabulku, ve které evidujeme rozvrh malé vysoké školy, kde každý předmět je učen právě jedním učitelem a každý učitel je natolik vytížen, že učí jen jeden předmět:
    
    

    Předmět	Učitel	Kroužek	Místnost	Čas
    Matematika	Novák	A4-01	PC406	Út3
    Matematika	Novák	A4-01	UL411	Po9
    Matematika	Novák	E3-15	PC406	Út3
    Matematika	Novák	E3-15	UL411	Po9
    Dějepis	SUKOVÁ	S1-07	AM701	St5
    Dějepis	SUKOVÁ	A4-01	AM701	St5
    Dějepis	SUKOVÁ	S1-87	AM701	St5
    Dějepis	SUKOVÁ	K3-05	AM701	St5

    
    
  • Z ukázky dat (relace) nelze dokázat, že platí nějaká funkční závislost (nemusí být zobrazeny některé možnosti, které potom vedou k tomu, že funkční závislost mezi určitými množinami atributů neexistuje), ale naopak negativní fakta mohou být z dané relace zjistitelná, tvoří totiž protiklad. Kladná fakta víceméně určíme z obecných znalostí a podmínek, které se daného případu týkají.

  • Atribut Učitel je funkčně závislý na množině atributů {Místnost-Čas}, protože pro každou hodnotu množiny atributů {Místnost-Čas} existuje nejvýše jedna hodnota atributu Učitel. To jinými slovy znamená, že v jedné místnosti ve stejnou dobu nemohou učit dva učitelé.
  • Atribut Předmět je funkčně závislý na množině atributů {Místnost-Čas}.
  • Atribut Předmět je funkčně závislý na atributu Učitel. To by obecně platit nemuselo protože jeden učitel je schopen učit i více předmětů, ale mi to máme v úvodní podmínce a tak to platí.
  • Atribut Učitel je funkčně závislý na atributu Předmět.
  • Ale atribut Učitel není funkčně závislý na atributu Místnost, protože v jedné místnosti je možné učit obecně několik předmětů, přestože to z našich dat není na první pohled vidět. Může existovat samozřejmě výjimka, typu např. chemické laboratoře, kde se bude učit jen chemie, ale obecně to neplatí a to je důležité.
  • Atribut Učitel není funkčně závislý na atributu Čas.
  • Atribut Učitel není funkčně závislý na atributu Kroužek.
  • Atribut Předmět není funkčně závislý na atributu Kroužek.
  • Atribut Předmět není funkčně závislý na atributu Místnost.
  • Atribut Předmět není funkčně závislý na atributu Čas.
  • Atribut Kroužek není funkčně závislý na atributu Předmět.
  • Atribut Kroužek není funkčně závislý na atributu Učitel.
  • Atribut Kroužek není funkčně závislý na atributu Místnost.
  • Atribut Kroužek není funkčně závislý na atributu Čas.
  • Atribut Místnost není funkčně závislý na atributu Předmět.
  • Atribut Místnost není funkčně závislý na atributu Učitel.
  • Atribut Místnost není funkčně závislý na atributu Kroužek.
  • Atribut Místnost není funkčně závislý na atributu Čas.
  • Atribut Čas není funkčně závislý na atributu Předmět.
  • Atribut Čas není funkčně závislý na atributu Učitel.
  • Atribut Čas není funkčně závislý na atributu Kroužek.
  • Atribut Čas není funkčně závislý na atributu Místnost.

• Multizávislost
  • Máme relaci R a v ní dvě množiny atributů A a B, pak existuje multizávislost B na A, jestliže jedné A-hodnotě se přiřadí několik B-hodnot.
  • Máme tabulku, ve které evidujeme modely aut, v jaké zemi se vyrábějí a kolik mají jejich motory válců.
  • Platí zde jedno pravidlo: model se vyrábí ve všech státech ve všech verzích motorů.
    
    

    Model	Země	Počet válců
    Mustang	USA	4
    Mustang	USA	6
    Mustang	Kanada	4
    Mustang	Kanada	6

    
    
  • Atribut Počet válců multizávisí na atributu Model.
  • Tuto tabulku lze rozdělit na dvě tabulky:
    
    

    Model Země Mustang USA Mustang Kanada

    1:N

    Model Počet válců Mustang 4 Mustang 6

    
    
  • Když nyní přidáme např. model Škoda vyráběný v ČR se 4 válci, projeví se to v původní i nových tabulkách takto:
    
    

    Model Země Počet válců Mustang USA 4 Mustang USA 6 Mustang Kanada 4 Mustang Kanada 6 Škoda ČR 4

    Model Země Mustang USA Mustang Kanada Škoda ČR

    1:N

    Model Počet válců Mustang 4 Mustang 6 Škoda 4

    
    
  • Když nyní začneme ČR model Škoda vyrábět i s 6 válci, projeví se to v původní i nových tabulkách takto:
    
    

    Model Země Počet válců Mustang USA 4 Mustang USA 6 Mustang Kanada 4 Mustang Kanada 6 Škoda ČR 4 Škoda ČR 6

    Model Země Mustang USA Mustang Kanada Škoda ČR

    1:N

    Model Počet válců Mustang 4 Mustang 6 Škoda 4 Škoda 6

    
    
  • Tento rozklad je velice výhodný, protože zmenšuje využívaný databázový prostor a zrychluje prohledávání v databázi. Tento rozklad je předmětem 4. normální formy, kterou probereme za okamžik.
  • Pokud by neplatila naše podmínka, tedy že by se v každé zemi nemuseli vyrábět modely se všemi verzemi motorů (např. Mustang se v Kanadě vyrábí jen ve verzi 4 válcové), potom by nešlo o multizávislost a nebyl by možný rozklad na dvě tabulky.
  • Při návrhu aplikace je tedy nutné se pořádně zamyslet, jaké omezující podmínky máme a co s nimi dokážeme provádět.

Normální formy:

• Příklad úpravy databázového schématu, aby vyhovoval všem normálním formám:
  • Máme školní rozvrh v tomto stavu:
    • VÝUKA(Číslo_učitele, Předmět, Student, Zařazení_učitele, Pracoviště_učitele, Budova_pracoviště, ROZVRH)
    • ROZVRH(Den, Čas_od)
      
      

      Číslo učitele	Předmět	Student	Zařazení učitele	Pracoviště učitele	Budova pracoviště	ROZVRH
      U1	DB1	A97222	asistent	KIV	UK	Út 09:00
      U1	CPP	E99444	asistent	KIV	UK	Pá 15:00
      U1	CPP	A97222	asistent	KIV	UK	Pá 15:00
      U1	DB1	E99444	asistent	KIV	UK	Út 09:00
      U555	GRA	H96777	docent	KEE	PC	Čt 14:00

      
      
    • Platí zde dvě pravidla:
      • Učitel učí více předmětů. Jestliže student navštěvuje jeden učitelův předmět, navštěvuje i všechny ostatní jeho předměty. Příkladem by mohla být 1.-4. třída základní školy, kdy všichni žáci chodí do stejné třídy a na všechny předměty je má ten samý učitel.
      • Pracoviště je umístěno vždy jen v jedné budově.
    • Tabulka v atributu ROZVRH může mít i několik řádků.
  • Relace R je v 1. normální formě (1NF), jestliže žádný atribut není relací.
    • To že tabulka obsahuje atribut, který je zároveň relací si můžeme také představit tak, že zde máme spojení více údajů (např. den a čas), které budeme chtít později dělit a využívat samostatně (pokud nebudeme nikdy potřebovat zvlášť den nebo čas, tak se o atribut/relaci nejedná).
    • V našem případě relace VÝUKA obsahuje atribut ROZVRH, který je sám relací. Toto musíme odstranit.
    • VÝUKA(Číslo_učitele, Předmět, Student, Zařazení_učitele, Pracoviště_učitele, Budova_pracoviště, Den, Čas_od)
      
      

      Číslo učitele	Předmět	Student	Zařazení učitele	Pracoviště učitele	Budova pracoviště	Den	Čas od
      U1	DB1	A97222	asistent	KIV	UK	Út	09:00
      U1	CPP	E99444	asistent	KIV	UK	Pá	15:00
      U1	CPP	A97222	asistent	KIV	UK	Pá	15:00
      U1	DB1	E99444	asistent	KIV	UK	Út	09:00
      U555	GRA	H96777	docent	KEE	PC	Čt	14:00

      
      
  • Relace R je v 2. normální formě (2NF), jestliže je v 1NF a jestliže každný atribut, který nepatří žádnému klíči relace R, silně závisí na klíči R.
    • V našem případě v realaci VÝUKA atributy Zařazení_učitele, Pracoviště_učitele a Budova_pracoviště silně závisí na atributu Číslo_učitele. To vyřešíme rozpadem:
    • VÝUKA(Číslo_učitele, Předmět, Student, Den, Čas_od)
    • UČITEL(Číslo_učitele, Zařazení_učitele, Pracoviště_učitele, Budova_pracoviště)
      
      

      Číslo učitele Předmět Student Den Čas od U1 DB1 A97222 Út 09:00 U1 CPP E99444 Pá 15:00 U1 CPP A97222 Pá 15:00 U1 DB1 E99444 Út 09:00 U555 GRA H96777 Čt 14:00

      N:1

      Číslo učitele Zařazení učitele Pracoviště učitele Budova pracoviště U1 asistent KIV UK U555 docent KEE PC

      
      
  • Relace R je v 3. normální formě (3NF), jestliže je v 2NF a jestliže žádný atribut, který není složkou klíče relace R, není tranzitivně závislý na klíči relace R.
    • V našem případě, protože platí pravidlo "pracoviště je umístěno vždy jen v jedné budově", atribut Budova_pracoviště který není klíčem (tranzitivně) závisí na atributu Pracoviště_učitele, který také není klíčem a ten teprve závisí na klíči atributu Číslo_učitele. Tranzitivnost = nezávisí přímo na klíči, ale silně závisí na atributu, který také není klíčem a ten teprve slabě závisí na klíči. To je nutné odstranit:
    • VÝUKA(Číslo_učitele, Předmět, Student, Den, Čas_od)
    • UČITEL(Číslo_učitele, Zařazení_učitele, Pracoviště_učitele)
    • PRACOVIŠTĚ(Pracoviště, Budova_pracoviště)
      
      

      Číslo učitele Předmět Student Den Čas od U1 DB1 A97222 Út 09:00 U1 CPP E99444 Pá 15:00 U1 CPP A97222 Pá 15:00 U1 DB1 E99444 Út 09:00 U555 GRA H96777 Čt 14:00

      N:1

      Číslo učitele Zařazení učitele Pracoviště učitele U1 asistent KIV U555 docent KEE

      N:1

      Pracoviště Budova pracoviště KIV UK KEE PC

      
      
  • Relace R je v 4. normální formě (4NF), jestliže je v 3NF a jestliže v případě, že obsahuje multizávislost X->->Y, kde Y není podmnožinou X a XY nezahrnují všechny atributy R, pak X zahrnuje i klíč relace R.
    • Protože platí pravidlo "Učitel učí více předmětů. Jestliže student navštěvuje jeden učitelův předmět, navštěvuje i všechny ostatní jeho předměty.", atribut Student multizávisí na atributu Číslo_učitele. A díky tomu je možné provést následující úpravu:
    • UČITEL_UČÍ_PŘEDMĚT(Číslo_učitele, Předmět, Den, Čas_od)
    • UČITEL_UČÍ_STUDENTY(Číslo_učitele, Student)
    • UČITEL(Číslo_učitele, Zařazení_učitele, Pracoviště_učitele)
    • PRACOVIŠTĚ(Pracoviště, Budova_pracoviště)
      
      

      Číslo učitele Student U1 A97222 U1 E99444 U555 H96777

      N:1

      Číslo učitele Předmět Den Čas od U1 DB1 Út 09:00 U1 CPP Pá 15:00 U555 GRA Čt 14:00

      N:1

      Číslo učitele Zařazení učitele Prac. U1 asistent KIV U555 docent KEE

      N:1

      Prac. Budova KIV UK KEE PC

      
      
    • Pozor: kdyby např. student A97222 nestudoval předmět CPP nejednalo by se už u multizávislost a rozklad by se neuskutečnil.
  • Relace R je v Boyce-Coddově normální formě (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 nebo je X v R klíčem.
    • Příkladem může být toto schéma: ADRESÁŘ(Město, Ulice, PSČ). Atribut Ulice přitom představuje název ulice, tedy název, který se může vyskytovat v několika městech. Nalezneme zde dvě funkční závislosti: Atribut PSČ je funkčně závislý na množině atributů {Město, Ulice} a atribut Město je fukčně závislý na atributu PSČ. Naopak PSČ není funkčně závislý na atributu Ulice, protože jedna ulice může mít několik PSČ a také atribut PSČ není funkčně závislý na atributu Město, protože město může mít více PSČ. Z toho vyplývá, že množina atributů {Město, Ulice} je klíčem v tomto schématu. Klíčem je ovšem i množina atributů {Ulice, PSČ}, protože atribut Město je funkčně závislý na atributu PSČ a atribut Ulice není funkčně závislý na atributu PSČ. Můžeme tedy evidovat města spolu s PSČ aniž bychom znali nějakou ulici v městě. Původní schéma můžeme tedy převést na SEZNAM_ULIC(ULICE, PSČ) a MĚSTA(PSČ, Město). Toto schéma je již v BCNF. (Tento příklad je čerpán ze skript: Pokorný, Halaška - Databázové systémy, Vybrané kapitoly a cvičení, ČVUT 1997)
    • Je-li relace ve 4NF, je i v BCNF. Obráceně to neplatí.
    • Je-li relace v BCNF, je i ve 3NF. Obráceně to neplatí.

Další příklady úpravy schématu databáze dle normálních forem:

• Letadlo - týdenní rozvrh letů letadel:
  • LET(Číslo_letu, Odkud, Kam, ROZVRH)
  • ROZVRH(Den, Čas)
    
    

    Číslo letu	Odkud	Kam	ROZVRH
    OK101	Praha	Bratislava	Út 09:00 Ne 16:10
    OK101	Praha	Bratislava	St 14:00
    OK101	Praha	Bratislava	So 18:00
    OK800	K.V.	Moskva	Čt 08:00
    OK800	K.V.	Moskva	Út 09:00

    
    
  • Tato tabulka nesplňuje 1.NF, protože tabulka Let obsahuje atribut ROZVRH, který je sám relací. Toto musíme odstranit:
  • LET(Číslo_letu, Odkud, Kam, Den, Čas)
    
    

    Číslo letu	Odkud	Kam	Den	Čas
    OK101	Praha	Bratislava	Út	09:00
    OK101	Praha	Bratislava	Ne	16:10
    OK101	Praha	Bratislava	St	14:00
    OK101	Praha	Bratislava	So	18:00
    OK800	K.V.	Moskva	Čt	08:00
    OK800	K.V.	Moskva	Út	09:00

    
    
  • Realace LET není v 2.NF, protože obsahuje atributy Odkud a Kam, které jsou silně závislé na atributu Číslo_letu.
  • LET(Číslo_letu, Den, Čas)
  • LINKA(Číslo_letu, Odkud, Kam)
    
    

    Číslo letu Den Čas OK101 Út 09:00 OK101 Ne 16:10 OK101 St 14:00 OK101 So 18:00 OK800 Čt 08:00 OK800 Út 09:00

    N:1

    Číslo letu Odkud Kam OK101 Praha Bratislava OK800 K.V. Moskva

    
    
  • Teď už je schéma i v 3.NF, protože neobsahuje žádný atribut, který není klíčem a který by silně závisel na atributu, který také není klíčem. Takže tím pro nás rozklad končí.

   

• Potraviny v ledničce:
  • POTRAVINY_V_LEDNIČCE(Čárový_kód, Spotřebujte_do, Název, Typ_zkratka, Typ_název, Počet)
    
    

    Čárový kód	Spotřebujte do	Název	Typ zkratka	Typ název	Počet
    8555111777999	10.11.2000	Jogurt bílý DANONE 0,2 l	JO	Jogurt	3
    8555111777999	30.12.2000	Jogurt bílý DANONE 0,2 l	JO	Jogurt	2
    8111000222333	06.11.2000	Jogurt YOGOBELLA 0,5 l	JO	Jogurt	5
    8999444888000	13.02.2001	Máslo RAMA 0,5 kg	MA	Máslo	1
    8777333000777	22.03.2001	Máslo PERLA 0,25 kg	MA	Máslo	3

    
    
  • Tabulka POTRAVINY_V_LEDNIČCE je v 1.NF, protože neobsahuje žádný atribut, který by byl relací (složené atributy).
  • Tabulka POTRAVINY_V_LEDNIČCE není ve 2.NF protože obsahuje atributy Název, Typ_zkratka a Typ_název, které jsou silně závislé na atributu Čárový_kód. Takže se nám schema rozpadne na dvě tabulky.
  • POTRAVINY_V_LEDNIČCE(Čárový_kód, Spotřebujte_do, Počet)
  • POTRAVINY(Čárový_kód, Název, Typ_zkratka, Typ_název)
    
    

    Čárový kód Spotřebujte do Počet 8555111777999 10.11.2000 3 8555111777999 30.12.2000 2 8111000222333 06.11.2000 5 8999444888000 13.02.2001 1 8777333000777 22.03.2001 3

    N:1

    Čárový kód Název Typ zkratka Typ název 8555111777999 Jogurt bílý DANONE 0,2 l JO Jogurt 8111000222333 Jogurt YOGOBELLA 0,5 l JO Jogurt 8999444888000 Máslo RAMA 0,5 kg MA Máslo 8777333000777 Máslo PERLA 0,25 kg MA Máslo

    
    
  • Tabulka POTRAVINY tak pro tabulku POTRAVINY_V_LEDNIČCE představuje číselník.
  • Schéma databáze není ve 3.NF, protože atribut Typ_název je silně závislý na atributu Typ_zkratka. Takže další rozklad:
  • POTRAVINY_V_LEDNIČCE(Čárový_kód, Spotřebujte_do, Počet)
  • POTRAVINY(Čárový_kód, Název, Typ_zkratka)
  • TYP(Zkratka, Název)
    
    

    Čárový kód Spotřebujte do Počet 8555111777999 10.11.2000 3 8555111777999 30.12.2000 2 8111000222333 06.11.2000 5 8999444888000 13.02.2001 1 8777333000777 22.03.2001 3

    N:1

    Čárový kód Název Typ zkratka 8555111777999 Jogurt bílý DANONE 0,2 l JO 8111000222333 Jogurt YOGOBELLA 0,5 l JO 8999444888000 Máslo RAMA 0,5 kg MA 8777333000777 Máslo PERLA 0,25 kg MA

    N:1

    Typ zkratka Typ název JO Jogurt MA Máslo

    
    
  • Tabulka TYP tak tvoří číselník tabulce POTRAVINY. Takto se tvoří informační číselníky často, kdy uživateli v aplikaci zobrazujete plný název z číselníku, ale do tabulky zapisujete jen zkratku, kterou uživatel nemusí ani znát.