Obsah

AP9, IN9 Databáze II
Diskuze

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 ¹⁾

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ť $X \subseteq R$ , $Y \subseteq R$ , pak řekneme, že Y je funkčně závislé na X, píšeme $X \rightarrow Y$ , 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. ²⁾
Množina atributů K je superklíčem pro relační schéma R právě když platí funkční závislost $K \rightarrow R$ . 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. ³⁾

Klíče relačních schémat

Klíč je část relačního schématu ⁴⁾
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ž $K \rightarrow R$ ⁵⁾
Kandidátní klíč je minimální superklíč; K je kandidátní klíč pro relační schéma R právě tehdy, když $K \rightarrow R$ a pro žádné $\alpha \subset K, \alpha \rightarrow R$ ⁶⁾. 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íč ⁷⁾

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⁺). Všechny F⁺ můžeme najít pomocí Armstrongových axiomů (jsou to pravidla odvozování logických implikací závislosti):

A1: je-li $\beta \subseteq \alpha$ , pak $\alpha \rightarrow \beta$ (reflexivita)
A2: je-li $\alpha \rightarrow \beta$ , pak $\gamma\alpha \rightarrow \gamma\beta$ (rozšíření, zápis $\gamma\alpha$ je zkratka pro $\gamma\ \cup\ \alpha$ )
A3: je-li $\alpha \rightarrow \beta$ a $\beta \rightarrow \gamma$ , pak $\alpha \rightarrow \gamma$ (tranzitivita) ⁸⁾

Z těchto pravidel jsou odvozena další užitečná pravidla:

je-li $\alpha \rightarrow \beta$ a $\alpha \rightarrow \gamma$ , pak $\alpha \rightarrow \beta\gamma$ (sjednocení)
je-li $\alpha \rightarrow \beta\gamma$ , pak $\alpha \rightarrow \beta$ a $\alpha \rightarrow \gamma$ (rozklad)
je-li $\alpha \rightarrow \beta$ a $\gamma\beta \rightarrow \delta$ , pak $\alpha\gamma \rightarrow \delta$ (pseudotranzitivita) ⁹⁾

Měli byste umět Armstrongovy axiomy také používat, například právě pro odvození těch dodatečných pravidel.

Odvození dodatečných pravidel

Odvození pravidla sjednocení Z prvního předpokladu $\alpha \rightarrow \beta$ pravidla sjednocení získáme podle A2, že $\alpha\gamma \rightarrow \beta\gamma$ . Z druhého předpokladu $\alpha \rightarrow \gamma$ pravidla sjednocení získáme také podle A2, že $\alpha\alpha \rightarrow \alpha\gamma$ , což odpovídá $\alpha \rightarrow \alpha\gamma$ . Poté z $\alpha\gamma \rightarrow \beta\gamma$ a $\alpha \rightarrow \alpha\gamma$ dostaneme podle A3, že $\alpha \rightarrow \beta\gamma$ .

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

Odvození pravidla pseudotranzitivity Z prvního předpokladu $\alpha \rightarrow \beta$ pravidla pseudotranzitivity získáme aplikací A2 $\gamma\alpha \rightarrow \gamma\beta$ . Toto společně s dalším předpkladem $\gamma\beta \rightarrow \delta$ pravidla pseudotranzitivity implikuje funkčí závislosti $\alpha\gamma \rightarrow \delta$ podle pravidla A3. ¹⁰⁾

Uzávěr množiny atributů

Uzávěr atributu $\alpha$ pod F (značíme $\alpha^{+}$ ) definujeme jako množinu atributů, které jsou funkčními závislostmi F určeny z $\alpha$ : $\alpha \rightarrow \beta$ je z $F^{+} \Leftrightarrow \beta \subseteq \alpha^{+}$ .¹¹⁾

Příklad

Mějme $R={A, B, C, G, H, I}$
$\{F = A \rightarrow B,$
$A \rightarrow C,$
$CG \rightarrow H,$
$CG \rightarrow I,$
$B \rightarrow H\}$

Otázka: Jaké jsou některé prvky F⁺?

Odpověď: $A \rightarrow H$ (tranzitivita), $AG \rightarrow I$ (pseudotranzitivita), $CG \rightarrow HI$ (sjednocení)

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

Odpověď:

Nejprve je nutné ukázat, zda je AG superklíč, tedy zda platí $AG \rightarrow R$ , toto se ukáže jednoduše (díky pravidlu $A \rightarrow B$ odvodíme $AG \rightarrow ABG$ , díky pravidlu $A \rightarrow C$ odvodíme $AG \rightarrow ABCG$ , díky pravidlu $CG \rightarrow H$ odvodíme $AG \rightarrow ABCGH$ a díky pravidlu $CG \rightarrow I$ 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íč.

¹²⁾

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 $(R_{1},R_{2}):$
- $R = R_{1} \cup R_{2}$
zpětné spojení musí být beztrátové - pro všechny možné relace r na schématu R platí $r = \Pi_{R1}(r)$ $\Pi_{R2}(r)$ ¹³⁾

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í $R_{1} \cap R_{2} \rightarrow R_{1}, R_{1} \cap R_{2} \rightarrow R_{2}$ je v F⁺), žádné redundance, uchování závislostí $(F_{1} \cup F_{2})^{+} = F^{+}$ . ¹⁴⁾

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ý).¹⁵⁾

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.)¹⁶⁾

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. ¹⁷⁾.

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. ¹⁸⁾

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.¹⁹⁾

Převody relačních schémat do NF

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:

$CV \rightarrow NV$

$CS \rightarrow NS, PS, TS$

$TS \rightarrow PS$

$CV, CS \rightarrow VS$

$CV, CS \rightarrow Cena$

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₁ = (CV, NV), R₂ = (CS, NS, PS, TS), R₃ = (CV, CS, VS, Cena). R₁ a R₃ jsou už i v 3NF, protože neobsahují tranzitivní závislosti na klíči. R₂ je pouze v 2NF, protože atribut PS je tranzitivně závislý na klíči {CS}.
Provedeme dekompozici schématu R₂ na schémata R_2a = (CS, NS, TS) a R_2b = (TS, PS), teď jsou schémata R₁, R_2a, R_2b, R₃ v 3NF a dokonce i v BCNF.

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á ²⁰⁾

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

FI:PB154 Základy databázových systémů (podzim 2007), prof. Ing. Pavel Zezula, CSc.
FI:PB155 Databázové systémy a jejich aplikace (podzim 2007), RNDr. Pavel Hajn, CSc.
FI:PB007 Analýza a návrh systémů (podzim 2007), RNDr. Jaroslav Ráček, Ph.D.

Použitá literatura

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)
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.

¹⁾

kapitola 1 strana 1 ve skriptech předmětu PB154 Základy databázových systémů

²⁾

z materiálů k předmětu PB155 Databázové systémy a aplikace, strana 43, zjednodušeno

³⁾ , ⁸⁾ , ⁹⁾

kapitola 6 strana 6 ve skriptech předmětu PB154 Základy databázových systémů

⁴⁾ , ⁵⁾

kapitola 2 strana 5 a kapitola 6 strana 5 ve skriptech předmětu PB154 Základy databázových systémů

⁶⁾ , ⁷⁾

kapitola 2 strana 5 a kapitola 3 strana 2 ve skriptech předmětu PB154 Základy databázových systémů

¹⁰⁾

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

¹¹⁾ , ¹²⁾ , ²⁰⁾

kapitola 6 strana 7 ve skriptech předmětu PB154 Základy databázových systémů

¹³⁾

kapitola 7 strana 2 ve skriptech předmětu PB154 Základy databázových systémů

¹⁴⁾

kapitola 7 strana 1 ve skriptech předmětu PB154 Základy databázových systémů

¹⁵⁾ , ¹⁶⁾

materiály k předmětu PB155 Databázové systémy a aplikace, strana 48

¹⁷⁾ , ¹⁸⁾

materiály k předmětu PB155 Databázové systémy a aplikace, strana 49

¹⁹⁾

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ů