(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)
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ť , , pak řekneme, že Y je funkčně závislé na X, píšeme , 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 . 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
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):
Z těchto pravidel jsou odvozena další užitečná pravidla:
Odvození dodatečných pravidel
Odvození pravidla rozkladu Z pravidla A1 plyne platnost a . Poté z předpokladu a po aplikaci pravidla A3 přímo vyplývá a
Odvození pravidla pseudotranzitivity Z prvního předpokladu pravidla pseudotranzitivity získáme aplikací A2 . Toto společně s dalším předpkladem pravidla pseudotranzitivity implikuje funkčí závislosti podle pravidla A3. 10)
Uzávěr atributu pod F (značíme ) definujeme jako množinu atributů, které jsou funkčními závislostmi F určeny z : je z .11)
Příklad
Mějme
Otázka: Jaké jsou některé prvky F+?
Odpověď: (tranzitivita), (pseudotranzitivita), (sjednocení)
Otázka: Je AG kandidátní klíč?
Odpověď:
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.
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í je v F+), žádné redundance, uchování závislostí . 14)
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)
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)
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ě.
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)
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.
Příklad z hodin předmětu PB155, zkráceno
Mezi atributy platí tyto vztahy:
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.
Diskuze
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)
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.
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ě? :)
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 tedaTS → 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ázkyR2b
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 bludyTS → 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
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
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…
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.
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…
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.
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.
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.
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.
Č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í…
Pre tych, co si nevedia zapamatat prevod do NF:
http://ufd.sweb.cz/fimuni/databaze.JPG
http://ufd.sweb.cz/fimuni/databaze2.JPG