====== AP9, IN9 Databáze II ======

===== Zadání ====
(funkční závislosti; klíče relačních schémat; Armstrongovy axiómy; dekompozice relačních schémat; normální formy obecně, 1NF, 2NF, 3NF, Boyce-Coddova NF, vztahy mezi NF; převody relačních schémat do NF)

===== Vypracování =====
====  Na začátek ==== 

  * Účel databázových systémů -- řešit problémy redundance dat, inkonsistence, integrity, bezpečnosti ((kapitola 1 strana 1 ve skriptech předmětu PB154 Základy databázových systémů))

==== Funkční závislosti ====
Jedná se o zobecnění představy klíče, jsou to tvrzení o reálném světě, o významu atributů, entit či vztahů mezi entitami. Nechť <math>X \subseteq R</math>, <math>Y \subseteq R</math>, pak řekneme, že Y je **funkčně závislé** na X, píšeme <math>X \rightarrow Y</math>, když pro každou povolenou relaci r(R) platí, že mají-li její dva libovolné prvky stejné hodnoty v atributech X, pak mají i stejné hodnoty v atributech Y. ((z materiálů k předmětu PB155 Databázové systémy a aplikace, strana 43, zjednodušeno)) \\
Množina atributů K je superklíčem pro relační schéma R právě když platí funkční závislost <math>K \rightarrow R</math>. Jednoduše řečeno: když mají dvě množiny atributů, které jednoznačně identifikují n-tici, stejnou hodnotu, pak se jedná o stejný záznam.

Funkční závislosti umožňují vyjádřit omezení, které nelze vyjádřit pomocí superklíčů. Využíváme je k \\
  * testování relací, jsou-li povolené na dané množině funkčních závislostí. Je-li relace r povolená na množině F funkčních závislostí, říkáme, že **r splňuje F.**
  * definování omezení na množině povolených relací, říkáme, že F je platná na R, když všechny povolené relace na R splňují množinu F. ((kapitola 6 strana 6 ve skriptech předmětu PB154 Základy databázových systémů))

==== Klíče relačních schémat ====
  * **Klíč** je část relačního schématu ((kapitola 2 strana 5 a kapitola 6 strana 5 ve skriptech předmětu PB154 Základy databázových systémů))
  * **Superklíč** je identifikátor záznamu (n-tice) dostatečný pro jednoznačnou identifikaci ; **K je superklíč** pro relační schéma R právě tehdy, když <math>K \rightarrow R</math> ((kapitola 2 strana 5 a kapitola 6 strana 5 ve skriptech předmětu PB154 Základy databázových systémů))
  * **Kandidátní klíč** je minimální superklíč; **K je kandidátní klíč** pro relační schéma R právě tehdy, když <math>K \rightarrow R</math> a pro žádné <math>\alpha \subset K, \alpha \rightarrow R</math>  ((kapitola 2 strana 5 a kapitola 3 strana 2 ve skriptech předmětu PB154 Základy databázových systémů)). Jednoduše řečeno: jakákoliv vlastní podmnožina kandidátního klíče K již neidentifikuje n-tice jednoznačně.
  * **Primární klíč** je jeden zvolený kandidátní klíč ((kapitola 2 strana 5 a kapitola 3 strana 2 ve skriptech předmětu PB154 Základy databázových systémů))
 

==== Armstrongovy axiómy ====
Pro danou množinu funkčních závislostí F existují další funkční závislosti, které F logicky implikuje (tzv. **uzávěr** množiny F, značíme jej F<sup>+</sup>). Všechny F<sup>+</sup> můžeme najít pomocí **Armstrongových axiomů** (//jsou to pravidla odvozování logických implikací závislosti//):
  * A1: je-li <math>\beta \subseteq \alpha </math>, pak <math>\alpha \rightarrow \beta</math> (reflexivita) 
  * A2: je-li <math>\alpha \rightarrow \beta </math>, pak <math>\gamma\alpha \rightarrow \gamma\beta</math> (rozšíření, zápis <math>\gamma\alpha</math> je zkratka pro <math>\gamma\ \cup\ \alpha</math>) 
  * A3: je-li <math>\alpha \rightarrow \beta </math> a <math>\beta \rightarrow \gamma </math>, pak <math>\alpha \rightarrow \gamma</math> (tranzitivita) ((kapitola 6 strana 6 ve skriptech předmětu PB154 Základy databázových systémů))

Z těchto pravidel jsou odvozena další užitečná pravidla:
  * je-li <math>\alpha \rightarrow \beta </math> a <math>\alpha \rightarrow \gamma </math>, pak <math>\alpha \rightarrow \beta\gamma</math> (sjednocení) 
  * je-li <math>\alpha \rightarrow \beta\gamma </math>, pak <math>\alpha \rightarrow \beta </math> a <math>\alpha \rightarrow \gamma</math> (rozklad)   
  * je-li <math>\alpha \rightarrow \beta </math> a <math>\gamma\beta \rightarrow \delta </math>, pak <math>\alpha\gamma \rightarrow \delta </math> (pseudotranzitivita) ((kapitola 6 strana 6 ve skriptech předmětu PB154 Základy databázových systémů))

<note important> Měli byste umět Armstrongovy axiomy také používat, například právě pro odvození těch dodatečných pravidel. </note>
<box 95% round blue|Odvození dodatečných pravidel>
**Odvození pravidla sjednocení**
Z prvního předpokladu <math>\alpha \rightarrow \beta </math> pravidla sjednocení získáme podle A2, že <math>\alpha\gamma \rightarrow \beta\gamma </math>. Z druhého předpokladu <math>\alpha \rightarrow \gamma </math> pravidla sjednocení získáme také podle A2, že <math>\alpha\alpha \rightarrow \alpha\gamma </math>, což odpovídá <math>\alpha \rightarrow \alpha\gamma </math>. Poté z <math>\alpha\gamma \rightarrow \beta\gamma </math> a <math>\alpha \rightarrow \alpha\gamma </math> dostaneme podle A3, že <math>\alpha \rightarrow \beta\gamma </math>.

**Odvození pravidla rozkladu**
Z pravidla A1 plyne platnost <math>\beta\gamma \rightarrow \beta </math> a <math>\beta\gamma \rightarrow \gamma </math>. Poté z předpokladu <math>\alpha \rightarrow \beta\gamma </math> a po aplikaci pravidla A3 přímo vyplývá <math>\alpha \rightarrow \beta</math> a <math>\alpha \rightarrow \gamma </math>

**Odvození pravidla pseudotranzitivity**
Z prvního předpokladu <math>\alpha \rightarrow \beta </math> pravidla pseudotranzitivity získáme aplikací A2 <math>\gamma\alpha \rightarrow \gamma\beta </math>. Toto společně s dalším předpkladem <math>\gamma\beta \rightarrow \delta </math> pravidla pseudotranzitivity implikuje funkčí závislosti <math>\alpha\gamma \rightarrow \delta </math> podle pravidla A3. ((postup podle dokumentu DATABÁZOVÉ SYSTÉMY, Doc. RNDr. Ing. Miloš Šeda, Ph.D., VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ, FAKULTA STROJNÍHO INŽENÝRSTVÍ, Ústav automatizace a informatiky, strana 25, elektronická verze: http://www.uai.fme.vutbr.cz/~mseda/DBS02_BS.pdf))
</box>


=== Uzávěr množiny atributů===

Uzávěr atributu <math>\alpha</math> pod F (značíme <math>\alpha^{+}</math>) definujeme jako množinu atributů, které jsou funkčními závislostmi F určeny z <math>\alpha</math>: <math>\alpha \rightarrow \beta</math> je z <math>F^{+} \Leftrightarrow \beta \subseteq \alpha^{+}</math>.((kapitola 6 strana 7 ve skriptech předmětu PB154 Základy databázových systémů))


<box 95% round blue|Příklad >

Mějme <math> R={A, B, C, G, H, I}</math> \\  <math>\{F = A \rightarrow B,</math> \\  <math>A \rightarrow C,</math> \\ <math>CG \rightarrow H,</math> \\ <math>CG \rightarrow I,</math> \\ <math>B \rightarrow H\}</math>

**Otázka:** Jaké jsou některé prvky F<sup>+</sup>?

**Odpověď:** <math>A \rightarrow H</math> (tranzitivita), <math> AG \rightarrow I</math> (pseudotranzitivita), <math>CG \rightarrow HI</math>(sjednocení)

**Otázka:** Je AG kandidátní klíč?

**Odpověď:** 
  * Nejprve je nutné ukázat, zda je AG superklíč, tedy zda platí <math>AG \rightarrow R</math>, toto se ukáže jednoduše (díky pravidlu <math>A \rightarrow B</math> odvodíme <math>AG \rightarrow ABG</math>, díky pravidlu <math>A \rightarrow C</math> odvodíme <math>AG \rightarrow ABCG</math>, díky pravidlu <math>CG \rightarrow H</math> odvodíme <math>AG \rightarrow ABCGH</math> a díky pravidlu <math>CG \rightarrow I</math> nakonec odvodíme již celé R)
  * Poté musíme ukázat, že samotné A není kandidátní klíč, tedy že z A nevyplývá celé R
  * Nakonec ještě musíme ukázat, že samotné G není kandidátní klíč.
((kapitola 6 strana 7 ve skriptech předmětu PB154 Základy databázových systémů)) </box>


==== Dekompozice relačních schémat ====

Při návrhu relačních databází je potřeba nalézt dobrou množinu relačních schémat, problémem je především opakování stejné informace a dat (redundance) a nemožnost vyjádřit nějakou informaci či ztráta informace. Problémy řeší **dekompozice relačních schémat** a **normalizace**.
=== Dekompozice ===
  * všechny atributy původního schématu R se musí objevit v rozkladu <math>(R_{1},R_{2}):</math>\\
    * <math>R = R_{1} \cup R_{2}</math>
  * zpětné spojení musí být beztrátové - pro všechny možné relace r na schématu R platí <math>r = \Pi_{R1}(r) </math> {{:home:prog:bowtie.png|}} <math> \Pi_{R2}(r)</math> ((kapitola 7 strana 2 ve skriptech předmětu PB154 Základy databázových systémů)) 


==== Normální formy ====

=== Normální formy obecně ===
Stanovují vlastnosti a teorii tak, aby bylo výsledné schéma v dobrém tvaru. Požaduje se **bezeztrátovost spojení** (nejméně jedna ze závislostí <math>R_{1} \cap R_{2} \rightarrow R_{1}, R_{1} \cap R_{2} \rightarrow R_{2}</math> je v F<sup>+</sup>), **žádné redundance**, **uchování závislostí** <math> (F_{1} \cup F_{2})^{+} = F^{+} </math>. ((kapitola 7 strana 1 ve skriptech předmětu PB154 Základy databázových systémů)) 

=== 1NF ===
Relační schéma R je v první normální formě, když každý jeho atribut je dále **nedělitelný** neboli **atomický** (je tedy jednoduchý či primární a není vícehodnotový ani složený).((materiály k předmětu PB155 Databázové systémy a aplikace, strana 48)) 
=== 2NF ===
Relační schéma R je v druhé normální formě, když **je v první normální formě** a každý atribut, který není primární, je **úplně závislý** na každém klíči. (// Závislost může být i tranzitivní, musí být na celém klíči nikoli jen na některé části.//)((materiály k předmětu PB155 Databázové systémy a aplikace, strana 48)) 
=== 3NF ===
Relační schéma R je ve třetí normální formě, když **je v druhé normální formě** a žádný atribut, který není primární, **není transitivně závislý** na žádném klíči schématu R. Schéma, které je v 3NF může mít ale stále následující problémy: opakuje se informace a je potřeba používat hodnoty null. ((materiály k předmětu PB155 Databázové systémy a aplikace, strana 49)).

Praktický pohled: v praxi se například považuje za porušení 3NF i vytvoření tzv. vypočteného sloupce v tabulce - to je takový, jehož hodnota je odvozena od dalších atributů v rámci záznamu. Na příkladě to může být výpočet cena výrobku na základě ceny bez DPH a výše daně.
=== Boyce-Coddova NF ===
Relační schéma R je v Boyce-Coddově normální formě, jestliže **je v třetí normální formě** a každý atribut je triviálně závislý na klíči (tedy každá závislost v relačním schématu je závislost na klíči). (//Laický pohled -- nejsou tam hodnoty typu null.//) Někdy není možné vytvořit rozklad do BCNF, který zachovává funkční závislosti. ((materiály k předmětu PB155 Databázové systémy a aplikace, strana 49)) 
=== Vztahy mezi NF ===
Třída schémat v BCNF je vlastní podtřídou třídy schémat 3NF. Třída relací 3NF je vlastní podtřídou třídy relací ve 2NF a ta je podtřídou relací 1NF.   
  * Vždy je možné provést rozklad schématu na několik schémat, která jsou v 3NF a rozklad je bezeztrátový a závislosti jsou zachovány.
  * Vždy je možné provést rozklad schématu na několik schémat, které jsou v BCNF a rozklad je bezeztrátový, ale všechny závislosti **nemusí být zachovány**.((materiály k předmětu PB155 Databázové systémy a aplikace, strana 48, 49 a kapitola 7 strana 6 ve skriptech předmětu PB154 Základy databázových systémů)) 
=== Převody relačních schémat do NF ===

<box 95% round blue|Příklad z hodin předmětu PB155, zkráceno> Mějme atributy číslo výrobku (CV), název výrobku (NV), cena výrobku (Cena), číslo stroje (CS), název stroje (NS), typ stroje (TS), výkon stroje (VS), příkon stroje (PS). 

Mezi atributy platí tyto vztahy: 

<math>CV \rightarrow NV</math>

<math>CS \rightarrow NS, PS, TS</math>

<math>TS \rightarrow PS</math>

<math>CV, CS \rightarrow VS</math>

<math>CV, CS \rightarrow Cena</math>

  * Nejprve dáme všechny atributy do jednoho relačního schématu R = (CV, NV, Cena, CS, NS, PS, TS, VS), klíčem je množina {CV, CS}. Protože jsou již všechny atributy nedělitelné, je toto schéma v 1NF. Není ale v 2NF, protože například atribut NS není plně závislý na celém klíči, ale pouze na jeho části.
  * Provedeme dekompozici na relační schémata R<sub>1</sub> = (CV, NV), R<sub>2</sub> = (CS, NS, PS, TS), R<sub>3</sub> = (CV, CS, VS, Cena). R<sub>1</sub> a R<sub>3</sub> jsou už i v 3NF, protože neobsahují tranzitivní závislosti na klíči. R<sub>2</sub> je pouze v 2NF, protože atribut PS je tranzitivně závislý na klíči {CS}.
  * Provedeme dekompozici schématu R<sub>2</sub> na schémata R<sub>2a</sub> = (CS, NS, TS) a R<sub>2b</sub> = (TS, PS), teď jsou schémata R<sub>1</sub>, R<sub>2a</sub>, R<sub>2b</sub>, R<sub>3</sub> v 3NF a dokonce i v BCNF. 
</box>

==== Podněty, co lze zmínit dále, ale podle mě už není nutné ====

  * **Kanonický obal** -- jedná se o množinu závislostí takovou, že F (množ. funkčních závislostí) logicky implikuje všechny závislosti v obalu, obal implikuje závislosti v F a žádná funkční závislost v obalu **neobsahuje nadbytečný atribut** a každá **levá strana** funkční závislosti v obalu je **jedinečná** ((kapitola 6 strana 7 ve skriptech předmětu PB154 Základy databázových systémů))

===== Co byste ještě měli znát? =====

  * Měli byste znát problémy relačního schématu, které není v dané normální formě.

===== Předměty =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?id=427861|FI:PB154]] Základy databázových systémů (podzim 2007), prof. Ing. Pavel Zezula, CSc. 
  * [[https://is.muni.cz/auth/predmety/predmet.pl?id=290000|FI:PB155]] Databázové systémy a jejich aplikace (podzim 2007), RNDr. Pavel Hajn, CSc.
  * [[https://is.muni.cz/auth/predmety/predmet.pl?id=427854|FI:PB007]] Analýza a návrh systémů (podzim 2007), RNDr. Jaroslav Ráček, Ph.D. 

===== Použitá literatura =====
  * [[http://is.muni.cz/el/1433/podzim2007/PB154/index.qwarp|Osnova předmětu PB154 a z ní odkazované dokumenty k předmětu PB154]] (česky přeložené dokumenty jsou jen pro přihlášené v IS MU)
  * [[https://is.muni.cz/auth/el/1433/podzim2007/PB154/um/czech/zezula07.pdf|Kapitola 7: Návrh relačních databází]] hlavní dokument, ze kterého jsem čerpala informace, přístupný jen pro přihlášené v IS MU, autorem je prof. Ing. Pavel Zezula, CSc. 
  * materiály k předmětu PB155 Databázové systémy a aplikace -- nejsou dostupné online
  * prezentace Modelování dat pro předmět PB007, autorem je RNDr. Jaroslav Ráček, Ph.D. a doc. Ing. Jiří Sochor, CSc. (přístupné jen pro studenty předmětu)
  * RÁČEK, Jaroslav.//Strukturovaná analýza systémů//. 1.vyd. Brno: Vydavatelství MU, 2006. 103 s. ISBN 80-210-4190-0.
===== Kam dál? =====

===== Vypracuje =====
Jitka Pospíšilová ICQ: 218703195  mám <99%>, aspoň si to myslím, kdyžtak doplňujte, co je případně ještě potřeba

Otázku si přečetl pan RNDr. Vlastislav Dohnal a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~