P114_11 ‹#› P114_11 1 P114 Doladění a transformace do ERD Nadtypy, podtypy, identifikace Transformace 11 P114_11 ‹#› P114_11 2 Témata •vazební a popisné atributy •nadtypy, podtypy •identifikace •ekvivalentní vyjádření v RDBMS, ... •algoritmus transformace • P114_11 ‹#› P114_11 3 redukovaná hierarchie typů pro DM (zopakování) •E-typy, D-typy •uzlové typy •n-ticové typy •základní typy •prvky H-typů prvky H-typů základní typy konstruovány nad uzlové typy n-ticové typy E-typy D-typy se dělí na se dělí na typ Bool P114_11 ‹#› P114_11 4 Vazební a popisné atributy •Nechť A je atribut složitosti 2, tj. (a) A / (W ® (T ® S)) (b) A / (W ® (T ® (S ® Bool))) kde T, S jsou uzlové typy, z nichž alespoň jeden je E-typ. •Je-li jeden z typů (T nebo S) D-typem, nazýváme A popisným (deskriptivním) atributem. •V opačném případě nazýváme A vazebním (vztahovým) atributem. •Je-li A deskriptivní atribut typu (b), kde S je D-typ, říkáme že S je význačným popisným typem pro E-typ T P114_11 ‹#› P114_11 5 souvislost s databázovým schématem •Množina všech deskriptivních atributů daného E-typu T je podkladem pro strukturu objektové třídy (entity) v databázovém schématu (vyjma atributů s význačnými popisnými typy) •Vazební atributy jsou podkladem pro strukturu vazeb v databázovém schématu (a popisné atributy s význačným popisným typem také) •Atributy složitosti větší než 2 jsou podkladem pro strukturu vazebních tříd (vazebních entit) v databázovém schématu (pro realizaci složitějších vazeb) P114_11 ‹#› P114_11 6 Pragmatický pohled na E-typy •Když modelujeme realitu, vždy vycházíme z daného stavu představ o tom, které prvky tvoří jednotlivé entitní sorty. Tento stav představ je závislý na stavu světa w Î W, ve kterém se nacházíme. •Stav představ o tom, které prvky tvoří danou entitní sortu, budeme nazývat populace entitní sorty. Populaci entitní sorty T ve stavu světa w budeme značit Tw. •To nic nemění na definici entitní sorty pomocí rozumného časového okolí R přítomnosti a aktuálního světa wa v definici z přednášky č. 6. •Pragmatický pohled zaujímáme a populaci Tw zavádíme proto, že exaktní definice entitní sorty nám nedává použitelný návod k tomu, jak se sortami jako s množinami nějakých prvků pracovat. P114_11 ‹#› P114_11 7 definice entitní sorty (zopakování) •Nechť R Í Tim je rozumné časové okolí (bylo-je-bude) přítomnosti. Nechť rÎR je časový okamžik a wa je aktuální svět. •Nechť T1, …, Tm jsou ne nutně různé typy nad EB. •Nechť Pi / (((BoolTi)Tim)Wrd) jsou konkrétní vlastnosti přisouditelné Ti-objektům. •Označme C(Pi,r,wa) třídu Ti-objektů generovanou vlastností Pi v daném časovém okamžiku r a aktuálním světě wa. •Potom: •ÈrÎR C(Pi,r,wa) je entitní sorta definovaná vlastností Pi. •Èi=1..m ÈrÎR C(Pi,r,wa) je entitní sorta definovaná disjunkcí vlastností Pi, i=1,...,m. •Çi=1..m ÈrÎR C(Pi,r,wa) je entitní sorta definovaná konjunkcí vlastností Pi, i=1,...,m. •Entitní sorta je tedy extenze, nezávislá na stavu světa. P114_11 ‹#› P114_11 8 Nadtypy, podtypy •Nechť T, S jsou uzlové typy. Nechť Tw označuje populaci sorty T ve stavu světa w. Nechť pro každý stav světa w Î W platí Tw Í Sw Potom T nazýváme podtypem S, resp. S nazýváme nadtypem T. •Jestliže T a S jsou ve vztahu nadtyp-podtyp, pak buďto oba jsou E-typy, nebo oba jsou D-typy. (Plyne přímo z definice) •Vztah nadtyp-podtyp zapisujeme (v HITu) přímo do definic příslušných typů. •Oproti zvyklostem zavádíme vztah nadtyp-podtyp nejenom pro E-typy, ale obecněji pro všechny uzlové typy. •Z definice vyplývá, že vztah nadtyp-podtyp je dán prostě množinovou inkluzí. (Všechny sorty jsou extenze !!!) Příklad: PLAT Í PrirozCisla #ZAMESTNANEC Í #OSOBA P114_11 ‹#› P114_11 9 Příklady, doporučení •Pragmatické použití populace entitních sort: •#Zamestnanecw Í #Osobaw #Studentw Í #Osobaw #Zboziw Í #Produktw #Vyrobekw Í #Produktw #Produktw Í #Artiklw #Sluzbaw Í #Artiklw ... •Pro rozhodování o tom, zda dva uzlové typy (a zejména E-typy) jsou ve vztahu nadtyp-podtyp, jsou nutné definice těchto typů. •Definice E-typů a jejich vztahy nadtyp-podtyp je nutné vyvažovat se sémantikou a poměrem atributů, ve kterých vystupují. P114_11 ‹#› P114_11 10 Vyvažování - příklady , doporučení •(IČO) daného (#Podnik) / 1,1:0,1 #Podnikw Í #Organizacew pro "w (IČO) dané (#Organizace) / 0,1:0,1 „rozšířením funkce na nadtyp se ona stane parciální“ •(Plat)-s dané (#Osoba) / 0,M:0,M #Zamestnanecw Í #Osobaw pro "w (Plat) daného (#Zamestnanec) / 1,1:0,M „restrikcí funkce na podtyp se ona stane totální, a dokonce definicí zaměstnance jako zaměstnance „našeho“ podniku (kde má každý zaměstnanec jeden plat) se stane ona funkce jednoznačnou“ •„Ztotálňování“ parciálních funkcí je vhodný prostředek k vyčleňování podtypů daného E-typu •Definice E-typu často rozhoduje o horním poměru atributu (viz uvedený příklad) P114_11 ‹#› P114_11 11 Princip hierarchie nadtyp-podtyp •Nechť je dána hierarchie nadtyp-podtyp ... Í P2w Í P1w Í Tw Í N1w Í N2w Í ... • •pro každý objekt x/T platí $xiÎNi (xiw = xw) pro i = 1, 2, ... tj. x má obrazy ve všech nadtypech T takové, že pro každý stav světa w tyto obrazy a x konstruují (triviálně) tutéž extenzi • P114_11 ‹#› P114_11 12 Princip hierarchie nadtyp-podtyp - pokračování •pro každý atribut A/(W ® (T ® Z)), kde Z je základní typ nebo Z=(Z1® Bool) pro Z1 uzlový nebo n-ticový typ, platí: $AiR/(W ® (Pi ® Z)) ("xÎPi([AiRw x] = [Aw x])) pro i = 1, 2, ... $AiE/(W ® (Ni ® Z)) ("xÎT([AiEw x] = [Aw x])) pro i = 1, 2, ... tj. je možné zužovat nebo rozšiřovat atributy přechodem k pod- nebo nad- typům •totéž lze formulovat i pro integritní omezení P114_11 ‹#› P114_11 13 Identifikace •Prvky uzlových typů je třeba v každém stavu světa a) od sebe navzájem rozlišit b) rozpoznat, že se jedná o jeden a týž objekt •Prvky D-typů jsou identifikovány samy sebou - svojí hodnotou (jsou reprezentovatelné) •Prvky E-typů musí být identifikovány pomocí hodnot některých D-typů (poněvadž samy nejsou reprezentovatelné) •Identifikaci potřebujeme při práci s prvky entitních a deskriptivních sort (přednáška 6) v informačním systému. Avšak návrh identifikace je podstatnou součástí modelování. •Identifikace musí „fungovat“ pro všechny stavy světa ! P114_11 ‹#› P114_11 14 Princip identifikace •Mějme konceptuální model M = (BZT, K, C) •Nechť EÎ BZT je E-typ. Potom v K musí existovat takový atribut A / (W ® (E ® D)), že platí: 1) D je D-typ 2) A je totální funkce 3) rotA / (W ® (D ® E)) je přípustná singulární rotace •A se nazývá identifikační atribut E-typu E a D se nazývá identifikací typu E (v databázi se pak většinou označuje ID). •Identifikace, přiřazená jednou konkrétnímu objektu sorty E, se nesmí žádnou aktualizací měnit. •Identifikace je „nálepkou“ na příslušnou jednotlivinu z množiny Univ, pokud E je podmnožinou UNIV. P114_11 ‹#› P114_11 15 Princip izomorfního zobrazení světa „rodné číslo“ identifikuje ID „rodné číslo“ identifikuje REALITA INFO SYSTÉM P114_11 ‹#› P114_11 16 Kandidát identifikace •Nechť E je E-typ, T je základní typ, T ¹ Bool. Jestliže v konceptuálním modelu M existuje atribut A / (W ® (E ® T)), který je totální funkcí, pak A nazýváme kandidátem identifikačního atributu a T nazýváme kandidátem identifikace E-typu (entitní sorty) E •Kandidátem identifikace je např. ono „rodné číslo“ •Kandidáti identifikace jsou dáni atributy z reálného světa, nikoli jako uměle zavedená ID. P114_11 ‹#› P114_11 17 Klíč •Nechť E je E-typ, Ti je uzlový typ, i=1,...,n. Nechť v K existují atributy Ai / (W ® (E ® Ti)), které jsou kandidáty identifikačních atributů. x::E, y::(T1,...,Tn), L(i=1..n) značí konjunkci n členů Nechť A = l w l x i y (L(i=1..n)([Aiwx] = y(i))). Nechť platí (1) singulární rotace rotA = l w l y i x ([Awx] = y) je přípustná. (2) {T1,...,Tn} je minimální množina, pro kterou platí (1) Potom n-tici (T1,...,Tn) nazýváme klíčem typu E •Klíče jsou „uživatelské“ identifikace pro E. P114_11 ‹#› P114_11 18 Pravidlo identifikace nadtypů a podtypů •Nechť E je nadtypem E1, ..., Ek. Nechť "w ("ij (Ei Ç Ej = { })) a È(i=1..k) Ei = E, (È značí množinové sjednocení) •Jestliže pro každé Ei existuje v K identifikační atribut Ai / (W ® (Ei ® Di)), Di je D-typ, pak pro E nemusí v K existovat identifikační atribut. Říkáme, že E je identifikováno implicitně. •Napište konstrukci, která by konstruovala identifikační atribut E pomocí Ai. •Jestliže pro E existuje v K identifikační atribut A, pak A je identifikačním atributem i pro E1, ..., Ek. Říkáme, že E1, ..., Ek jsou identifikovány implicitně. •Podle jakého principu to platí? P114_11 ‹#› P114_11 19 … a incidenční atributy •Nechť pro E a některé Ej (resp. pro všechna) existuje v K identifikační atribut (v takovém případě říkáme, že E nebo Ej jsou identifikovány explicitně). •Potom musí v K existovat atributy Ij / (W ® (Ej ® E)) takové, že a) Ij je totální funkce b) rotIj / (W ® (E ® Ej)) je přípustná singulární rotace •dokažte, že rotIj je surjekce E na Ej •Jinak bychom totiž nedokázali rozpoznat, že objekt x Î Ej je totožný sám se sebou, tj. s objektem x Î E objekt x Î E má totiž jinou identifikaci než objekt x Î Ej •Atributy Ij nazýváme incidenčními atributy. P114_11 ‹#› P114_11 20 Přípustné transformace •Transformací množiny atributů A rozumíme takovou množinu atributů B, pro kterou platí: B Î B Þ (B Î A Ú B ¬ A) • •Transformace se nazývá přípustná, jestliže B » A. Také říkáme, že když transformace je přípustná, tak zachovává informační schopnost. •Transformací konceptuálního modelu M = (BZT, K, C) rozumíme transformaci množiny K a odpovídající přeformulování všech integritních omezení z C pomocí transformovaných atributů. •pro navrhování DB a IS jsou důležité přípustné transformace konceptuálního modelu P114_11 ‹#› P114_11 21 Věta 3 (o intenzionálních relacích) •Nechť A je libovolný HIT-atribut, w::W, xi::Ti, y::T, Ti, T příslušné základní typy, jak vyžaduje definice, A = lw lx1...xn y ([Aw(x1,,..., xn)] * y). Potom z A lze přípustnou transformací odvodit atribut A1 / (W ® ((T1,..., Tn, T) ® Bool)), ve kterém n-ticový typ bereme v normálním tvaru (tj. neobsahující vnořené n-ticové typy) •Atribut A1 nazýváme intenzionální relace (relation in intension). •DŮSLEDEK: Ke každému konceptuálnímu modelu M existuje schéma relací (v relačním modelu dat) se stejnou informační schopností. P114_11 ‹#› P114_11 22 Důsledky •Každý konceptuální model vytvořený metodou HIT lze implementovat pomocí RDBMS se zachováním informační schopnosti. •To co dokážeme implementovat v RDBMS, je možno vyjádřit rovněž v ERD, tj. také v běžně používaných prostředcích CASE (SDW, SELECT SE, Rational Rose, ...) a v běžně používaných standardech jako je UML (Unifying Modeling Language) •HIT metodu lze použít jako myšlenkový aparát a způsob zápisu výsledků při práci s kterýmkoli ze zmiňovaných nástrojů resp. standardů. P114_11 ‹#› P114_11 23 Binarizační princip (1) •Nechť A je libovolný nerozložitelný HIT-atribut složitosti větší než 2, w::W, xi::Ti, Ti, příslušné základní typy, jak vyžaduje definice, A = lw lx1...xn-1 xn ([Aw(x1,,..., xn-1)] * xn). •Zavedeme tzv. konkatenovaný typ: R = cn(T1, ...,Tn) •R Í (T1, ...,Tn) je podmnožina kartézského součinu tvořená právě těmi n-ticemi < x1,,..., xn>, které jsou dány tabulkou [A w] P114_11 ‹#› P114_11 24 Binarizační princip (2) •Definujeme pro i = 1..n projekce Bi / (W ® (R ® Ti)) takto: Bi = lw lr ixi (([Aw(r(1),,..., r(n-1))] * r(n)) Ù r(i) = xi) •Potom Bi jsou totální funkce na R, a {B1, ..., Bn} » A •DŮSLEDEK: všechno co dovedeme zapsat (HIT-) konceptuálním modelem, lze zaznamenat pomocí sítě uzlů a hran. P114_11 ‹#› P114_11 25 atribut A - nerozložitelný T1 T2 Tn-1 Tn A text1 text2 textn-1 P114_11 ‹#› P114_11 26 T1 T2 Tn-1 Tn Bn R B1 B2 Bn-1 sémantika je v definici R; Bi vyjadřují pouze projekci na i-tou složku P114_11 ‹#› P114_11 27 Algoritmus transformace •M = (B, K, C), B je báze tvořená uzlovými typy a Bool. •Následující transformace do ERAM zachovává (nesnižuje!!!) informační schopnost: •(1) Pro každé AÎK, jeli složitost A větší než 2, zavést konkatenovaný typ R a A nahradit konfigurací projekcí Bi POZN.: tím zavedeny vztahové entity z ERAM •(2) Všechna singulární omezení, platná pro A, přeformulovat jako tvrzení konzistence pomocí Bi •(3) Každý E-typ, který je explicitně identifikovaný a každý konkatenovaný typ reprezentovat entitou (po řadě kernel a vztahovou) v ERAM • P114_11 ‹#› P114_11 28 algoritmus - pokračování •(4) Popisné atributy k E-typu resp. konkatenovanému typu z (3), které neobsahují význačný popisný typ, reprezentovat jako ERAM atributy příslušné kernel nebo vztahové entity •(5) Popisné atributy, které obsahují implicitně identifikovaný typ, nahradit dle principu hierarchie nadtypů-podtypů příslušným rozšířením resp. zúžením v rámci záměny implicitně identifikovaného typu za explicitně identifikovaný. Dále pokračovat krokem (4). •(6) Význačné popisné typy reprezentovat samostatnými entitami v ERAM (tzv. charakteristickými entitami) P114_11 ‹#› P114_11 29 algoritmus - pokračování •(7) Vazební atributy, v nichž každý E-typ je explicitně identifikovaný, reprezentovat hranou v ERAM, jejíž typ (1-1, 1-M, M-M) je dán horním poměrem atributu •(8) Je-li ve vazebním atributu implicitně identifikovaný E-typ, nahradit jej dle principu hierarchie nadtypů-podtypů příslušným rozšířením resp. zúžením v rámci záměny implicitně identifikovaného typu za explicitně identifikovaný. Dále pokračovat krokem (7). •(9) Všechny definice E-typů z B zapsat jako definice kernel entit a všechny sémantiky atributů z K zapsat jako sémantiky hran resp. vztahových entit v ERAM. •KONEC P114_11 ‹#› P114_11 30 Praktické použití - poznámky •Výsledkem je model v ERAM, který má všechny entity (brány jako relační tabulky) v BCNF, dokonce v 4NF a 5NF. •Zkušený datový modelář provádí uvedený algoritmus (rovnou při návrhu datového modelu) v hlavě a přímo zapisuje výsledek v ERAM pomocí vhodného CASE. •Pro vysvětlení složitých vazeb resp. pro jejich analýzu a rozpoznání pravého stavu věcí, se doporučuje zakreslit situaci pomocí sémantických diagramů („kytiček“), a nad nimi diskutovat a řešit problém. •Krok (9) algoritmu je nepominutelný a závazný !! •Příklady výsledků - viz přednáška 12.