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

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

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

  • Klíč je část relačního schématu 4)
  • 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 5)
  • 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 6). 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íč 7)

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

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

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

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^{+}.11)

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íč.

12)

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

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^{+}. 14)

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

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

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

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

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

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 R1 = (CV, NV), R2 = (CS, NS, PS, TS), R3 = (CV, CS, VS, Cena). R1 a R3 jsou už i v 3NF, protože neobsahují tranzitivní závislosti na klíči. R2 je pouze v 2NF, protože atribut PS je tranzitivně závislý na klíči {CS}.
  • Provedeme dekompozici schématu R2 na schémata R2a = (CS, NS, TS) a R2b = (TS, PS), teď jsou schémata R1, R2a, R2b, R3 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á 20)

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.

1) kapitola 1 strana 1 ve skriptech předmětu PB154 Základy databázových systémů
2) z materiálů k předmětu PB155 Databázové systémy a aplikace, strana 43, zjednodušeno
3) , 8) , 9) kapitola 6 strana 6 ve skriptech předmětu PB154 Základy databázových systémů
4) , 5) kapitola 2 strana 5 a kapitola 6 strana 5 ve skriptech předmětu PB154 Základy databázových systémů
6) , 7) kapitola 2 strana 5 a kapitola 3 strana 2 ve skriptech předmětu PB154 Základy databázových systémů
10) 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
11) , 12) , 20) kapitola 6 strana 7 ve skriptech předmětu PB154 Základy databázových systémů
13) kapitola 7 strana 2 ve skriptech předmětu PB154 Základy databázových systémů
14) kapitola 7 strana 1 ve skriptech předmětu PB154 Základy databázových systémů
15) , 16) materiály k předmětu PB155 Databázové systémy a aplikace, strana 48
17) , 18) materiály k předmětu PB155 Databázové systémy a aplikace, strana 49
19) 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ů

Diskuze

, 2008/06/11 11:00

Ahoj, v prvom rade musim poznamenat, ze je to velmi kvalitne spracovana otazka :-)
Mal by som mensiu pripomienku k vypoctu uzaveru mnoziny atributov. Uvedeny priklad je spravny, ale pre tych co nepoznaju algoritmus vypoctu mozno trosku matuci.
Mozno by pomohlo doplnenie nasledovneho algoritmu:

Vypocet alfa+ ⇒ uzaveru alfa pod F

1. krok
result := alfa;
2. krok
while (changes to result) do (robime dovtedy, pokial sa nam meni result)

for each beta->gama in F do 
  begin 
    if beta <= result then result := result U gama (ak je beta podmnozinou vysledku, tak k vysledku pridame gama) 
  end 

Cize v uvedenom priklade by sa postupovalo nasledovne:
1. result := AG
2. A → B a A ⇐ AG, cize result := ABG
3. A → C a A ⇐ ABG, cize result := ABCG
4. CG → H a CG ⇐ ABCG, cize result := ABCGH
5. CG → I a CG ⇐ ABCGH, cize result := ABCGHI
6. B → H a B ⇐ ABCGHI, cize result := ABCGHI
7. skoncil sa foreach a result sa oproti zadaniu zmenil, takze znova foreach

result sa uz nezmeni takze algoritmus skoncil s vysledkom AG → ABCGHI.

Ukazanie, ze A nie je kandidatny kluc:
1. result := A
2. A → B a A ⇐ A, cize result := AB
3. A → C a A ⇐ AB, cize result := ABC
4. CG → H, ale CG nie je podmnozinou ABC
5. CG → I, ale CG nie je podmnozinou ABC
6. B → H a B ⇐ ABC, cize result := ABCH
7. nastala zmena v resulte, znovu sa pokracuje foreachom cez F

po skonceni sa result uz nezmeni, takze vysledkom je ABCH, preto A nie je kandidatny kluc.

analogicky sa ukaze, ze G nie je kandidatny kluc.

, 2008/06/20 11:42

Rozumíte někdo tomu, co přesně říká věta pod Uzávěr množiny atributů? Nechtěl by mi to někdo napsat formálně? :)

, 2008/06/23 14:44

Trošku mi tam vadí definícia 3NF. V materiáloch k Ananasu (str. 38) znie definícia takto:

Def. 3.NF (přesněji):
Záznam R je ve 3.NF, pokud je ve 2.NF a každá neklíčová položka R je netranzitivně závislá na každém kandidátním klíči z R.

A definícia z tejto stránky znie:
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.

Napr. v príklade na prevod relačných schémat do NF sa R2b = (TS, PS) platí TS → TS (reflexivita, axióm A1) a zároveň TS → PS a teda TS → PS (tranzitivia, A3). Keďže PS nie je primárny atribút, našiel som tu tranzitívnu závislosť, takže podľa definície 3NF z tejto otázky R2b nie je v 3NF. Preto so myslím, že tá definícia z ananasu je jediná správna. Opravte ma ak sa mýlim, je možné, že teraz pred skúškami už píšem bludy =)

, 2008/06/23 15:00

TS → PS musi platit z principu zachovania funkcnych zavislosti (tato zavislost je v zadani), ja si to predstavujem tak, ze ta R2b je nova tabulka a nova tabulka musi mat primarny kluc, ktorym je TS :) tym padom to je aj v 3. NF a aj v BCNF, lebo je tam jedina zavislost a to zavislost na kluci

, 2008/06/23 15:10

No, to neva. Skús zabudnúť na to, že to je upravované z niečoho do niečoho. Zober si akúkoľvek relačnú schému v tvare R = (A PRIMARY KEY, B) a už ti to porušuje tú podmienku na 3NF z tejto stránky, kdežto tú z anansu nie

, 2008/06/23 15:02

tak ted jsi mi tim zamotal hlavu.. me ta definice prijde porad celkem podobna i s tim uvedenim prikladem a prijdem mi, ze stejny problem s tou reflexivitou, jak jsi ji popsal, ma i ta definice z ananasu… presne podle axiomu jsem nad tim tak neuvazovala, pan Hajn nam na to kreslil takove hezke sipky a podle toho jsem to vse chapala.. jenze ted s tema definicema uz v tom moc jasno nemam…

, 2008/06/23 15:18

V tej 3NF forme ide vlastne o to, že je zakázaná táto situácia: R = (A, B, C) a platí A → B a B → C, pretože C je tranzitívne závislé na A. Aby sme to dokopali do 3NF, tak to proste rozdelíme: R = (A, B) a S = (B, C).

Oba spomenuté schémy porušujú def. 3NF odtiaľto, ale keď si zoberieme tú def. z ananasu, tak tá prvá ju porušuje, kdežto tá druhá nie. Problém je v tom, že „atribút A nie je tranzitívne závislý na B“ nie je to isté ako „A je netranzitívne závislý na B“.

EDIT: Hm, teraz som sa nad tým zamyslel a asi máš pravdu, že tá Tvoja definícia je v pohode. Ono tá tranzitivita tu je trošku niečo iné ako v matike, bo tu sa predpokladá, že to neberieme cez reflexivitu. Neuvedomil som si, že tá úplná závislosť na kľúči je def. už v 2NF a 3NF len odstráňuje tie tranzitívne vzťahy. Takže sa všetkým ospravedlňujem za zmätky =P.

, 2008/06/23 15:46

Tak prave som ti chcel odpisat ked vidim EDIT :) sa tu 15 minut zamyslam nad tym, co tym chcel basnik povedat a ty mi to skazis :) Inak podla mna su tie definicie ekvivalentne a tu neplati, ze ked mas X→X a X→Y, ze Y je tranzitivne zavisle na X (ak som to dobre pochopil, to inak neplati ani v matematike), to by potom platilo vsade…

, 2009/06/20 11:58

Ahoj,
nie som si isty, ci platia podmienky na kandidatny kluc. Nech {A,B,C}=R je relacna schema a {A} a {B,C} su superkluce. Funkcne zavislosti su F={A → BC, BC → A}.
Otazka: Je {B,C} kandidatny kluc?
Podla prvej vety nie je. Minimalny superkluc je {A}.
Podla druhej vety kandidatnym klucom je: neplati B → R ani A → R (ak som kdesi nespravil chybu).
Ja si myslim, ze definicia nie je spravna. Prosim o potvrdenie, resp. vyvratenie. Dakujem.

, 2009/06/20 12:47

Ahoj,
nie som si isty, ci platia podmienky na kandidatny kluc. Nech {A,B,C}=R je relacna schema a {A} a {B,C} su superkluce. Funkcne zavislosti su F={A → BC, BC → A}.
Otazka: Je {B,C} kandidatny kluc?
Podla prvej vety nie je. Minimalny superkluc je {A}.
Podla druhej vety kandidatnym klucom je: neplati B → R ani A → R (ak som kdesi nespravil chybu).
Ja si myslim, ze definicia nie je spravna. Prosim o potvrdenie, resp. vyvratenie. Dakujem.

, 2009/06/20 14:48

Ahoj,
nie som si isty, ci platia podmienky na kandidatny kluc. Nech {A,B,C}=R je relacna schema a {A} a {B,C} su superkluce. Funkcne zavislosti su F={A → BC, BC → A}.
Otazka: Je {B,C} kandidatny kluc?
Podla prvej vety nie je. Minimalny superkluc je {A}.
Podla druhej vety kandidatnym klucom je: neplati B → R ani A → R (ak som kdesi nespravil chybu).
Ja si myslim, ze definicia nie je spravna. Prosim o potvrdenie, resp. vyvratenie. Dakujem.

, 2009/06/20 16:37

Ahoj,
nie som si isty, ci platia podmienky na kandidatny kluc. Nech {A,B,C}=R je relacna schema a {A} a {B,C} su superkluce. Funkcne zavislosti su F={A → BC, BC → A}.
Otazka: Je {B,C} kandidatny kluc?
Podla prvej vety nie je. Minimalny superkluc je {A}.
Podla druhej vety kandidatnym klucom je: neplati B → R ani A → R (ak som kdesi nespravil chybu).
Ja si myslim, ze definicia nie je spravna. Prosim o potvrdenie, resp. vyvratenie. Dakujem.

, 2009/06/22 20:43

Čauko,

myslím, že BC kand. klíč je. IMHO ty jsi tu první větu pochopil tak (a mně to přijde taky logické), že X je kandidatní klíč ⇔ X je minimální superklíč PŘES VŠECHNY superklíče. Ale taky je možno to chápat tak, že X je kandidátní klíč ⇔ X je superklíč a je minimální (tzn. že jeho libovolná ostrá podmnožina už ostatní atributy neurčuje).

No, doufám, že to není moc matoucí…

, 2009/06/21 15:49

Pre tych, co si nevedia zapamatat prevod do NF:
http://ufd.sweb.cz/fimuni/databaze.JPG
http://ufd.sweb.cz/fimuni/databaze2.JPG

You could leave a comment if you were logged in.
home/prog/ap9.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0