Relační datový model. Integritní omezení. Normální formy Návrh IS. funkční závislosti multizávislosti inkluzní závislosti

Relační datový model Integritní omezení funkční závislosti multizávislosti inkluzní závislosti

Normální formy Návrh IS

Vladimíra Zádová, KIN, EF, TUL - DBS

Funkční závislosti • funkční závislost – elementární – redundantní – redukovaná – částečná • pokrytí – minimální pokrytí • Armstrongova pravidla


Funkční závislosti • speciální druh IO, vymezuje určitou množinu přípustných relací. • Jsou definovány mezi 2 množinami atributů v rámci jednoho schématu relace – jedná se o vztahy mezi daty - ne mezi entitami či entitami a daty – funkční závislost lze definovat za předpokladu pevné sémantiky • Pozorováním funkčních závislostí lze zjistit že: – platnost některých vede k platnosti jiných – některé platí vždy Vladimíra Zádová, KIN, EF, TUL - DBS

Funkční závislosti • Formální popis funkční závislosti: R (Ω Ω, F ) ; R(Ω Ω) schéma relace a F množina funkčních závislostí

• Funkční závislost Mějme 2 množiny atributů: X, Y kde X, Y ⊆ Ω. Pak Y funkčně závisí na X ( nebo X funkčně určuje Y) jestliže ke každé X-hodnotě existuje nejvýše jedna Yhodnota. Značíme: X → Y


Funkční závislosti • Explicitní vyjádření funkční nezávislosti: X -/→ Y

• PK lze vyjádřit pomocí funkčních závislostí: Je-li dáno R(Ω Ω) a K, kde K ⊆ Ω, pak K je klíčem schématu R jestliže splňuje 2 vlastnosti: 1) K → Ω 2) Neexistuje K ´⊆ K taková, že K ´→ Ω (platí : K′-/→ → Ω)


Funkční závislosti uzávěr Pokrytí - ekvivalence • Uzávěr F Množina všech funkčních závislostí odvoditelných z F se nazývá uzávěr F, značí se F+. Je-li tedy funkční závislost odvoditelná z F patří do F+. • Pokrytí - ekvivalence Pokrytí množiny funkčních závislostí F je množina funkčních závislostí G taková, že F+ = G+. 2 množiny funkčních závislostí F, G jsou ekvivalentní vymezují-li 2 stejné množiny relací. Říkáme, že F je pokrytím G, resp.G je pokrytím F . Vladimíra Zádová, KIN, EF, TUL - DBS

Funkční závislosti • Kanonické pokrytí Je-li F′′ množina, která vznikne z F dekompozicí jejích neelementárních závislostí , platí F ′ + = F +. Toto pokrytí je kanonické. • Elementární funkční závislost Závislost, která má na pravé straně jeden atribut nazýváme elementární funkční závislost • Redundantní závislost – Závislost f je redundantní v F, pokud platí: ( F-{f}) + = F+


Funkční závislosti • Redukovaná závislost Redukovaná závislost je taková závislost, která nemá na levé straně žádné redundantní atributy. • Částečná závislost Částečná závislost je taková závislost, která není redukovaná.


Funkční závislosti • Minimální pokrytí Minimální pokrytí je kanonické neredundantní pokrytí tvořené z redukovaných závislostí. •

Odstraňování redundantních závislostí a odstraňování redundantních atributů nelze provádět v libovolném pořadí.


Funkční závislosti

• Nalezení minimálního pokrytí pro množinu funkčních závislostí F: – Vytvořit kanonické pokrytí F′′ – odstranit redundantní atributy ze závislostí -t.j. všechny závislosti budou redukované – odstranit redundantní funkční závislosti


Funkční závislosti ARMSTRONGOVA PRAVIDLA • ARMSTRONGOVA PRAVIDLA - jsou: – korektní - co jimi z nějaké množiny F odvodíme, platí ve všech relacích z Rel – úplná - lze jimi odvodit všechny funkční závislosti , které platí na každé relaci z Rel. – Nezávislá -odstraněním jakéhokoliv z nich porušíme vlastnost úplnosti.


Funkční závislosti ARMSTRONGOVA PRAVIDLA • Nechť X, Y, Z jsou podmnožiny Ω. FZ1: triviální funkční závislost : je-li Y ⊆ X , pak X → Y FZ2: tranzitivita : X → Y ∧ Y → Z, pak X→Z FZ3: kompozice : X → Y ∧ X → Z, pak X → YZ FZ4: dekompozice: X → YZ, pak X → Y ∧ X→Z Pozn.: YZ je sjednocení množiny Y a Z.


Multizávislosti – vycházejí ze závislostí mezi 2 množinami atributů v rámci jedné relace – Na multizávislostech je založena 4.NF Uvažujme schéma relace R(Ω), 2 množiny atributů A, B ⊂ Ω, pak multizávislost B na A vychází z představy, že jedné A-hodnotě přiřadí více B-hodnot .


Multizávislosti • Definice multizávislosti: Pro schéma relace R(Ω Ω), kde Ω = { A, B, C}, C = Ω -A - B, A →> B je multizávislost na A, jestliže pro každou přípustnou relaci R platí: R = R[A, B] * R[A, C]. Je-li C prázdná množina, pak se A →> B nazývá multizávislost triviální. Lze říci, že B multizávisí na A.


Multizávislosti • Na multizávislostech je založena 4.NF jsou to jiné typy závislostí než FZ, ale stejně jako FZ vycházejí ze závislostí mezi 2 množinami atributů v rámci jedné relace. • Uvažujme schéma relace R(Ω), 2 množiny atributů A, B ⊂Ω , pak multizávislost B na A vychází z představy, že jedné Ahodnotě přiřadí více hodnot B.


Inkluzní závislosti •

Na rozdíl od předchozích závislostí se jedná o vztah dvou relací, je to tedy globální IO • Definice inkluzní závislosti: Ωi) a Rj(Ω Ωj) jsou 2 schémata relací z R. Nechť X, Nechť Ri(Ω resp. Y jsou kompatibilní podmnožinyΩi resp. Ωj. Pak tvrzení Ri[X] incl Rj[Y] nazýváme inkluzní závislost. Daná inkluzní závislost platí na odpovídajících relacích tehdy, jestliže platí vztah inkluze mezi uvedenými projekcemi. • Pokud je Y primární klíč Rj, pak se jedná o referenční integritu, je-li Y jednotlivý atribut, pak se jedná o unární inkluzní závislost Vladimíra Zádová, KIN, EF, TUL - DBS

Normalizace • Normalizace přestavuje soubor pravidel aplikovaných na datové struktury • Pravidla vycházejí z praktických problémů při aktualizaci databáze – UPDATE, INSERT, DELETE •

Na základě pravidel (NF) se provádí úprava těch struktur (relací), které pravidla porušují. • Základní postup je jediný - rozdělení do menších datových struktur (dekompozice ) .


Normalizace • Jednotlivým pravidlům se říká normální formy (NF) – každá z těchto NF vede k omezení některých nedostatků – NF vedou k odstranění duplicit a nekonzistencí v datech • Codd nazýval praktické problémy aktualizační anomálie – redundance – ztráta informace – nemožnost evidovat informace aniž by si je někdo vybral.


Normalizace Existují tyto NF: I.NF, II.NF, III.NF, IV.NF, BCNF IV.NF vychází z multizávislostí Platí: Je-li schéma relace ve vyšší NF, pak je samozřejmě i v nižší NF. V praxi je snaha dosáhnout III. NF, resp. BCNF


Normalizace • I.NF Týká se jednoho záznamu (prvku relace) a odstranění nekonzistence v něm - prvky domén jsou atomické • 0.NF Schéma relace je v nulté normální formě právě tehdy, když existuje alespoň jeden atribut, který obsahuje více než jednu hodnotu. • Pokud schéma relace není v nulté normální formě, pak je alespoň v první normální formě.


Normalizace II.NF • Schéma relace je ve II. NF, pokud je v I.NF a každý neklíčový atribut je plně funkčně závislý na PK. Plná funkční závislost Nechť pro podmnožiny atributů X, Y relace R ( Ω) existuje funkční závislost X → Y . Pak říkáme, že Y je plně funkčně závislý na X, pokud neexistuje žádná funkční závislost A → Y , kde A ⊂ X .


Normalizace III.NF • III.NF Schéma relace je ve III.NF, jestliže každý neklíčový atribut schématu R není tranzitivně závislý na žádném klíči schématu. • Tvrzení: Schéma relace R(Ω Ω,F) , kde F je množina elementárních funkčních závislostí, je ve III.NF právě když pro každou funkční závislost schématu X→ → A platí alespoň jedna ze tří podmínek: a) závislost je triviální b) X obsahuje klíč schématu R c) A je částí klíče schématu R Vladimíra Zádová, KIN, EF, TUL - DBS

Normalizace Boyce-Coddova NF - BCNF • Boyce-Coddova NF - BCNF Schéma relace je Boyce-Coddově NF, jestliže pro každou netriviální závislost X→ →A platí, že X obsahuje klíč schématu R • Tvrzení: Schéma relace R(Ω Ω,F) , kde F je množina elementárních funkčních závislostí, je v BCNF právě když pro každou funkční závislost schématu X→ →A platí alespoň jedna ze dvou podmínek: a) závislost je triviální b) X obsahuje klíč schématu R Vladimíra Zádová, KIN, EF, TUL - DBS

Normalizace Boyce-Coddova NF - BCNF

• BCNF Relace je v BCNF tehdy a jen tehdy, pokud každý determinant je kandidátem klíče. • Tvrzení: Je-li schéma relace R(Ω Ω,F) ve třetí NF a má pouze jednoduché klíče , pak je v BCNF.


Normalizace IV.NF • IV.NF Schéma relace je ve IV.NF jestliže pro každou netriviální multizávislost X →> Y platí, že X je nadmnožinou nějakého klíče schématu R. • Tvrzení: Schéma relace R , je ve čtvrté NF právě když pro každou multizávislost schématu X→ →>A platí alespoň jedna ze dvou podmínek: a) multizávislost je triviální b) X je nadmnožinou nějakého klíče schématu R


Normalizace V.NF • V.NF Schéma relace je v páté normální formě, pokud je ve čtvrté normální formě a není možné do ní přidat nový atribut nebo novou skupinu atributů tak, aby se tím rozpadla vlivem skrytých závislostí na několik dílčích tabulek.


Návrh relačního schématu databáze

•

na základě funkčních závislostí a multizávislostí

• kriteria pro návrh relačního schématu databáze: – odstranění anomálií při aktualizacích relací • řešení pomocí 3NF , BCNF • děje se v procesu dekompozice schématu relace


Návrh relačního schématu databáze

•

Problém při dekompozici = problém reprezentace : – výsledné relace by měly mít stejnou sémantiku – Výsledné relace by měly obsahovat stejná data


Návrh relačního schématu databáze stejná sémantika • Stejná sémantika relace je dána IO ( zde IO = FZ) – Při dekompozici - jedná se o dekompozici FZ mezi jednotlivá schémata. Jde tedy o vztah F, Fi pro i ∈1,2, ... N • Vlastnost pokrytí závislostí: Nechť R = {S(Ω Ω,F)} je relační schéma databáze a R 1= {Ri(Ω Ω i, Fi), 1 ≤ i ≤ n , n ≥ 1} je dekompozice daného relačního schématu R . Pak R 1 má vlastnost pokrytí závislostí, jestliže: F+ = ( ∪ Fi )+


Návrh relačního schématu databáze stejná sémantika • Jak stanovit Fi: – jde o závislosti , které platí na Ω i . – jsou z F+ (nejen z F), • Projekce závislostí: Projekce F do Ω i je definována jako množina funkčních závislostí Fi = { X →Y; X →Y je v F+a XY je podmnožinou Ωi}


Návrh relačního schématu databáze stejná data – Stejnost dat je dána bezztrátovostí dekompozice – Nahrazení schématu R(Ω Ω) schématy Ri(Ω Ωi) , kde 1≤ i ≤ n, přičemž pro množinu atributů platí: Ω = ∪ Ωi • Dekompozice schématu znamená na úrovni databáze projekci původní relace na atributy odpovídající jednotlivým schématům po dekompozici (Ω Ω i ): Ri (Ωi) = R [Ωi ] • Pro každou dekompozici platí: R(Ω) ⊆ ∗ R [Ωi ]


Návrh relačního schématu databáze stejná data

•

dekompozice ztrátová - pak rekonstrukcí získáme více prvků relace (tj. bude obsahovat některé řádky relace, které v původní relaci nebyly).

• Dekompozice bezztrátová, pokud pro každou její přípustnou relaci je odpovídající dekompozice bezztrátová. R(Ω) = ∗ R [Ωi ]


Návrh relačního schématu databáze stejná data • Tvrzení pro bezztrátovou dekompozici: Nechť R( X,Y,Z) je schéma relace kde X, Y, Z jsou disjunktní množiny atributů a X →Y je funkční závislost. Rozložíme-li R( X,Y,Z) na schémata R1( X,Y) a R2( X,Z), je takto provedená dekompozice bezztrátová.

Naopak: je-li dekompozice R1( X,Y) a R2( X,Z) bezztrátová, musí platit buď X →Y nebo X →Z.


Návrh relačního schématu databáze 2 algoritmy návrhu • Dekompozice může mít buď jednu nebo obě vlastnosti – pokrytí závislostí – bezztrátové spojení • Dekompozice a syntéza – 2 algoritmy návrhu relačního schématu databáze – Vycházejí z funkčních závislostí – jde o dekompozici univerzálního schématu relace


Návrh relačního schématu databáze 2 algoritmy návrhu • Univerzální schéma relace - zajišťuje: – jednoznačnost jmen atributů ve všech schématech – jméno atributu má pouze jeden význam, atributy se stejnými jmény mají stejnou doménu • Cílem návrhu: – splnit požadavek 3NF či BCNF – zachování pokrytí závislostí – vlastnost bezztrátového spojení


• Metoda dekompozice • Metoda syntézy


Dekompozice – postupné nahrazování jednoho schématu dvěma. – v tomto případě je vždy výsledné schéma v dané NF – dekompozice má vlastnost bezztrátového spojení – nemusí být zachována vlastnost pokrytí závislostí


Syntéza – jde o vytváření schémat syntézou - přímo z funkčních závislostí – výsledek algoritmu bude ve 3NF – má zachovány závislosti – nemusí být vždy zachováno bezztrátové spojení


Syntéza • Vstup: F, R(Ω) • Postup: – vytvoří se minimální pokrytí – závislosti minimálního pokrytí se roztřídí do skupin : • každá skupina obsahuje závislosti se stejnou levou stranou, atributy závislostí každé skupiny tvoří schéma jedné relace -syntezované schéma, atributy levé strany tvoří klíč – Jsou-li mezi syntezovanými schématy schémata s funkčně ekvivalentními klíči - pak se tato schémata sloučí v jedno schéma. Pokud při sloučení vzniknou tranzitivity je třeba je odstranit. Vladimíra Zádová, KIN, EF, TUL - DBS

Syntéza • Pokud nebudou atributy obsažené v R v žádné FZ umístí se do samostatné relace, která se připojí k R: – X je množina atributů nevyskytujících se v minimálním pokrytí – Y jsou takové atributy, aby XY tvořily klíč schématu R


Syntéza • Metodu syntézy uvedl v r. 1976 Bernstein . • V r. 1979 - Biskup, Dayal, Bernstein dokázali zařídit bezztrátovost spojení: – pokud K, kde K je klíč příslušného univerzálního schématu, není podmnožinou některého ze syntezovaných schémat pak stačí připojit k výsledku schéma s množinou atributů K . – V tomto případě bude muset klíč K obsahovat i ty atributy, které nejsou obsaženy v žádné FZ.


Relační datový model. Integritní omezení. Normální formy Návrh IS. funkční závislosti multizávislosti inkluzní závislosti

Recommend Documents