P114_9 ‹#› P114_9 1 P114 Definovatelnost Manipulace s HIT-atributy 9 P114_9 ‹#› P114_9 2 Témata •Identita a semiidentita HIT-atributů •Definovatelnost •Informační ekvivalence •Informační schopnost •Rotace, triviální odvození P114_9 ‹#› P114_9 3 HIT-atributy •každá taková funkce A je dána konstrukcí lwt lx1...xn y (C) kde w::Wrd, t::Tim, xi::Ti, y::S, Ti, S jsou základní typy splňující podmínky definice HIT-atributu, nebo lwt lx y (C) kde x :: (T1,...,Tn) C je otevřená Bool-konstrukce neobsahující jiné volné proměnné než w, t, xi, y A/(Wrd ® (Tim ® ((T1,...,Tn) ® S))) nebo A/(Wrd ® (Tim ® ((T1,...,Tn) ® (S ® Bool)))), P114_9 ‹#› P114_9 4 Základní předpoklad o HIT-atributech: •extenze HIT-atributů jsou konečné tabulky. •Předpoklad je oprávněný, poněvadž při modelování bereme v úvahu vždy –konečný diskrétní časový interval „života“ IS –konečnou populaci sort (E-typů a/nebo D-typů) • P114_9 ‹#› P114_9 5 základní předpoklad o analytických funkcích •Analytické funkce které budeme dále uvažovat jsou vždy surjekce a jsou to totální funkce. •ZOPAKOVÁNÍ: f / (T ® Â), kde  = S nebo  = (S ® Bool) f je injekce (zobrazení prosté), když "x,yÎT([f x] = [f y] Þ x = y) f je surjekce (zobrazení na), když "yΠ($xÎT([f x] = y)) f je bijekce, když je injekce a surjekce •často používané budou logické funkce, tj. funkce jejichž oborem hodnot je Bool •základní předpoklad vylučuje možnost, že by mezi logickými funkcemi, které budeme používat, byly tautologie nebo kontradikce P114_9 ‹#› P114_9 6 Identita HIT-atributů •konstrukce C1 je ekvivalentní s konstrukcí C2, jestliže pro libovolnou valuaci v a libovolný objekt A platí C1 v-konstruuje A právě tehdy, když C2 v-konstruuje A . •Nechť A1, A2 jsou HIT-atributy pořadě konstruované konstrukcemi C1 a C2. •Jestliže C1 je ekvivalentní s C2, pak HIT-atributy A1 a A2 jsou identické a píšeme A1 = A2. •To, že konstrukce C konstruuje HIT-atribut A budeme pro jednoduchost rovněž zapisovat A = C • P114_9 ‹#› P114_9 7 Problém s parcialitou HIT-atributů •Budeme konstruovat atributy pomocí jiných atributů •atribut může být na některých argumentech nedefinován: konstrukce jej používající pak je pro příslušnou valuaci v-nevlastní •jiná konstrukce, která konstruuje prakticky totéž, však na těchže argumentech vrací { }. •Tento rozdíl nemá vliv na množinu z atributu generovaných propozic •Proto se zavádí tzv. semiidentita P114_9 ‹#› P114_9 8 Semiidentita •Nechť A = lwt lx y (C), B = lwt lx y (C1) •Atributy A, B nazveme semiidentické, jestliže •buďto jsou identické •nebo se liší následujícím způsobem: "wtx ([Awtx] = [ Bwtx] Ú ([Awtx] = { } Ù [ Bwtx] = {^})) kde { } je prázdná množina, to v případě, že C je na x Nepravda, a {^} je třída taková, že o žádném prvku daného typu nemůžeme říci, že patří do této třídy proto, poněvadž C1 je na x nedefinováno. •V dalším bude A = B značit i semiidentitu. P114_9 ‹#› P114_9 9 Definovatelnost •Atribut A je definovatelný nad množinou atributů {B1, ..., Bn} právě když $f ("wt ([A wt] = [f ([B1 wt], ..., [Bn wt])])) kde f je analytická funkce splňující základní předpoklad, w je možný svět, t je časový okamžik. Píšeme: A ¬ (B1, ..., Bn) •Množina atributů M je definovatelná nad množinou atributů N, je-li každý prvek z M definovatelný nad nějakou podmnožinou N. Píšeme: M ¬ N •Atribut A je definovatelný nad atributem B, když je definovatelný nad množinou {B}. Píšeme: A ¬ B P114_9 ‹#› P114_9 10 Informační ekvivalence •Nechť M = {A1, ..., An}, N = {B1, ..., Bm} jsou množiny atributů a nechť M ¬ N a zároveň N ¬ M. Potom říkáme, že M a N jsou informačně ekvivalentní. Píšeme: M » N •Intuitivně je zřejmé, a lze dokázat, že dvě informačně ekvivalentní množiny atributů generují v každém stavu světa stejnou třídu propozic. •Jiná intuice: z n-tice tabulek daných množinou atributů M dostaneme tutéž informaci jako z m-tice tabulek daných množinou atributů N •VĚTA: Relace » na množině atributů je ekvivalence. • P114_9 ‹#› P114_9 11 Důsledek •Nechť atribut A je definovatelný nad množinou atributů {B1, ..., Bn}. Potom {A, B1, ..., Bn} » {B1, ..., Bn}. •Intuitivně: přidáním definovatelného („odvoditelného“) atributu nic nového nezískáme, nebo odebráním definovatelného („odvoditelného“) atributu nic z původního neztratíme •Co je to, co nezískáme ani neztratíme ? P114_9 ‹#› P114_9 12 quasi-uspořádání •Relace definovatelnosti mezi množinami atributů je: –reflexivní (evidentně M ¬ M, za f stačí vzít identitu) –tranzitivní (viz důkaz předchozí věty) •Avšak není antisymetrická: tj. z M ¬ N a N ¬ M neplyne M = N viz předchozí důsledek •Tedy není to relace částečného uspořádání, ale pouze quasi-uspořádání •Z Algebry:: lze definovat částečné uspořádání na množině ekvivalenčních tříd P114_9 ‹#› P114_9 13 Informační schopnost •Nechť BZT je nějaká báze základních typů. Nechť ATR je množina všech možných HIT-atributů nad BZT. •Faktorová množina ATR / » (tj. množina všech tříd ekvivalence nad ATR) je částečně uspořádaná relací indukovanou definovatelností. Značíme Ð •Každá třída ekvivalence z ATR / » definuje určitou informační schopnost. Relace Ð je částečným uspořádáním informačních schopností. P114_9 ‹#› P114_9 14 Tvrzení o informační schopnosti •Nechť CM, CN Î ATR / », M Î CM, N Î CN •CM Ð CN právě když M ¬ N •Tvrzení 1: všechny prvky třídy CM mají stejnou informační schopnost •Tvrzení 2: každý prvek CM má menší informační schopnost než každý prvek třídy CN •Tvrzení 3: Jestliže pro CM a CN neplatí ani CM Ð CN, ani CN Ð CM, pak informační schopnost libovolného prvku z CM je nesrovnatelná s informační schopností libovolného prvku z CN. P114_9 ‹#› P114_9 15 dohoda na označení, příklad •A = počet (PrirozCislo) druhů výrobků vyráběných daným výrobcem (#Vyrobce) / 0,1:0,M •A/(Wrd ® (Tim ® (#Vyrobce ® PrirozCislo))) to lze psát (Shönfinkelova redukce): A/((Wrd,Tim) ® (#Vyrobce ® PrirozCislo)) toto platí pro všechny HIT-atributy •Označíme (Wrd, Tim) = W ... stav světa, potom: A/(W ® (#Vyrobce ® PrirozCislo)) a konstrukce A má tvar: A = lw lx iy ([[Aw] x] = y), kde w::W, x::#Vyrobce, y::PrirozCislo •Aplikace [Aw] je velmi častá; proto zkracujeme: Aw •Aw je extenze atributu A ve stavu světa w (je to tabulka) P114_9 ‹#› P114_9 16 Příklad •Atribut A je definovatelný nad atributem B = druhy výrobků (#Vyrobek)-s vyráběné daným výrobcem (#Vyrobce) / 0,M:0,M •Odvození: (x::#Vyrobce, z::#Vyrobek, y::PrirozCislo) B = lw lx lz ([[Bw x] z]) • hledáme f tak, aby pro všechna w Aw = [f Bw] : b :: (#Vyrobce ® (#Vyrobek ® Bool)), a :: (#Vyrobce ® PrirozCislo) jsou proměnné, pak f = lb ia ("x ([ax] = [Card [bx]])), kde Card je funkce kardinality množiny Skutečně (beta-pravidlo): [f Bw ] = ia ("x ([ax] = [Card [Bwx]])) = Aw P114_9 ‹#› P114_9 17 méně formálně •f je algoritmus, který nezávisle na stavu světa vypočítává z tabulky b (mimochodem nenormalizované) tabulku a. •V praxi se netrápíme hledáním konstrukce funkce f ve tvaru lambda-termu, ale stačí, když se přesvědčíme o existenci algoritmu, který - ale v každém stavu světa - vypočítává z jedné tabulky tu druhou •lambda-termy potřebujeme pro důkazy obecných tvrzení, které aplikujeme v praxi při vytváření konkrétních datových modelů P114_9 ‹#› P114_9 18 Příklad •A1 = plat (Pl) daného (#Zamest) / 0,1:0,M A2 = (#Zamest)-s daného (#Podnik) / 0,M:1,M •B = průměrný plat (Pl) v daném (#Podnik) / 0,1:0,M •B je definovatelný nad {A1, A2} toto intuitivně cítíme; (mohl by poměr B být 1,1:0,M ??) •Jak se hledá konstrukce příslušné odvozovací fce f ? Tj. její algoritmus ? •fce f počítá v každém wÎW tabulku atributu B z tabulek atributů A1 a A2 P114_9 ‹#› P114_9 19 Příklad - pokračování •tedy při označení z :: #Zamest, p :: #Podnik •for all p:Podnik do write p (* první sloupec tabulky B *) Sum1 = 0; Sum2 = 0 for all z:Zamest do if [[A2p]z] then Sum1 = Sum1+[A1z] Sum2 = Sum2+1 endfor write Sum1/Sum2 (* druhý sloupec tabulky B *) endfor P114_9 ‹#› P114_9 20 Rotace atributu •Nechť atribut A je dán konstrukcí A = lw lx1...xn-1 xn ([Aw(x1,,..., xn-1)] * xn) kde xi :: Ti, Ti jsou uzlové typy. Nechť (i1, ..., in) je libovolná permutace indexů (1, ..., n). Potom atribut rotA daný konstrukcí rotA = lw lxi1...xin-1 xin ([Aw(x1,,..., xn-1)] * xn) se nazývá rotací atributu A. •Jestliže v rotA zastupuje l, říkáme že je to l-rotace, resp. plurální rotace. Jestliže v rotA zastupuje i, říkáme že je to i-rotace, resp. singulární rotace. •Rotace atributu A se nazývá přípustná, jestliže A ¬ rotA. •Nebude-li řečeno jinak, označuje rotA v dalším přípustnou rotaci. • P114_9 ‹#› P114_9 21 Lemma 1 •Nechť A je dán v plurální rotaci, tj. A = lw lx1...xn-1 l xn [[Aw(x1,,..., xn-1)] xn] Potom každá jiná jeho plurální rotace je přípustná. • P114_9 ‹#› P114_9 22 Přípustné singulární rotace •A = (#Podnik)-s ve kterých pracuje daný (#Zamest) •rot1A = (#Zamest)-s daného (#Podnik) rot2A = (#Zamest) daného (#Podnik) •Zřejmě rot1A je přípustná a rot2A není přípustná: rot2A / (W ® (#Podnik ® #Zamest)) tj. v každém stavu světa je definovaná pouze na podnicích, které mají nejvýše jednoho zaměstnance tedy: z rot2A nelze odvodit zpět atribut A, poněvadž neoprávněným použitím singularizátoru jsme ztratili informaci •POZN.: obrácená funkce (viz přednáška 7) je speciální případ rotace atributu P114_9 ‹#› P114_9 23 Věta 1 (o informační ekvivalenci a rotacích) •Každá přípustná rotace atributu A je informačně ekvivalentní s A. Každá nepřípustná rotace A není informačně ekvivalentní s A. P114_9 ‹#› P114_9 24 Pravidlo singularity •Z daného atributu nelze žádným formálním způsobem odvodit, které jeho rotace jsou přípustné singulární rotace. •To že nějaká singulární rotace je přípustná je netriviální empirický fakt. •Studiem přípustnosti singulárních rotací určujeme poměr atributu. •PRAVIDLO: Při datovém modelování je třeba s každým HIT-atributem prozkoumat všechny jeho rotace, a zjistit zda má nějaké přípustné singulární rotace. Pokud ano, do výsledného modelu zapisujeme vždy tyto přípustné singulární rotace, nikoli jiné - plurální - rotace. P114_9 ‹#› P114_9 25 Triviální odvození •Řekneme, že atribut A vznikl z atributu B triviálním odvozením, jestliže A ¬ B, tj. pro všechna w Aw = [f Bw] a funkce f obsahuje nejvýše identitu, přípustně použitý singularizátor a/nebo existenční kvantifikátor. •Triviální odvození jsou nejčastěji používána jako nástroj odvození odpovědi na dotazy nad databází. Pro formulování dotazů je vhodnější využívat všech funkcí jednoduchých typů (přednáška 6) a neomezovat se pouze na H-typy. Pro vlastní modelování je toto omezení (pouze na H-typy) výhodnější. P114_9 ‹#› P114_9 26 obecná rotace atributu •Vychází z obecnějšího pojetí atributu jako funkce jednoduchého typu: A = lw lx1...xk xk+1... xn [Aw(x1,,..., xk)]*(xk+1, ..., xn) •Nechť (i1, ..., in) je libovolná permutace indexů (1, ..., n). Potom atribut rotA daný konstrukcí rotA = = lw lxi1...xik xik+1... xin [Aw(x1,,..., xk)] * (xk+1..., xn) se nazývá rotací atributu A. Plurální a singulární rotace jako v původní definici. •Používá se v důkazech a odvozování, nikoli jako modelovací konstrukt. • P114_9 ‹#› P114_9 27 Příklad: DOD ZBOZI ODB kterým daný dodává dané ODZ 0,M .. 0,M P114_9 ‹#› P114_9 28 příklad - pokračování •ROTACE: ZDO = (#Zbozi)-s dodávaná daným (#Dodavatel) danému (#Odberatel) / 0,M:0,M DZO = (#Dodavatel)-s kteří dodávají dané (#Zbozi) danému (#Odberatel) / 0,M:0,M podle lemmatu víme, že jsou přípustné. Empirickým výzkumem se přesvědčíme, že žádná singulární rotace není přípustná. •TRIVIÁLNĚ ODVOZENÉ ATRIBUTY: ZD = (#Zbozi)-s dodávaná daným (#Dodavatel) / 0,M:0,M OZ = (#Odberatel)-s daného (#Zbozi) / 0,M:0,M OD = (#Odberatel)-s daného (#Dodavatel) / 0,M:0,M •Příklad algoritmu odvození: P114_9 ‹#› P114_9 29 OD ¬ ODZ •for all x:DOD do for all y:ODB do if $ z:ZBOZI ([[ODZw(x, z)] y] ) then write y else endif endfor endfor příkazem write vytváříme tabulku odběratelů příslušných k danému dodavateli P114_9 ‹#› P114_9 30 příklad obecné rotace •Dvojice zboží + dodavatel (#Zbozi, #Dodavatel) přiřazená k danému odběrateli (#Odberatel) taková, že onen dodavatel dodává ono zboží tomu dodavateli / 0,M:0,M •nakreslete si schéma tohoto atributu • •Z lineárního zápisu je vidět, že obecné rotace nejsou vhodné jako modelovací konstrukty. Avšak pro úvahy o správnosti a adekvátnosti vystižení reality a pro důkazy určitých zákonitostí (viz následující přednáška) jsou potřebné.