P114_10 ‹#› P114_10 1 P114 Rozložitelnost Manipulace s HIT-atributy 10 P114_10 ‹#› P114_10 2 Témata •Podatributy •Rozklad atributů •Jak poznat rozložitelnost •Věta o rozkladu •Jádro datového modelu P114_10 ‹#› P114_10 3 Zopakování •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_10 ‹#› P114_10 4 Informační ekvivalence (zopakování) •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_10 ‹#› P114_10 5 Triviální odvození (zopakování) •Ř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ů a transformací atributů je vhodnější využívat všech funkcí jednoduchých typů (přednáška 6) a neomezovat se pouze na H-typy. P114_10 ‹#› P114_10 6 Podatribut •Atribut A1 vzniklý triviálním odvozením z atributu A budeme nazývat podatributem A. Každý podatribut, který není totožný s některou přípustnou rotací A, nazýváme vlastní podatribut. •Zejména A je podatributem A. •Složitost vlastního podatributu A1 je vždy menší než složitost A. •Všechny rotace a odvozené atributy v posledním příkladu přednášky 9 jsou podatributy. P114_10 ‹#› P114_10 7 Rozklad atributu •Atribut A je rozložitelný na atributy B1, ..., Bn, píšeme A à (B1, ..., Bn), když 1) B1, ..., Bn jsou vlastní podatributy A, a 2) A ¬ (B1, ..., Bn) •DŮSLEDEK 1: Jestliže A à (B1, ..., Bn), potom A » {B1, ..., Bn}. DŮKAZ: plyne z definic. •DŮSLEDEK 2: Jestliže A à (B1, ..., Bn), potom každá jeho přípustná rotace rotA je rovněž rozložitelná na B1, ..., Bn. DŮKAZ: plyne z definice rotace, definice rozložitelnosti a věty 1 (viz přednáška 9). P114_10 ‹#› P114_10 8 Příklad: A/(W® ((Prednaska, Ucitel)® Student)) PREDNASKA UCITEL STUDENT A navštěvující danou vedenou daným P114_10 ‹#› P114_10 9 příklad - pokračování •uvažme atribut: B1 = (#Ucitel)-s kteří vedou danou (#Prednaska) opravdu je jich víc? Nechť realita je, že danou přednášku vede vždy jenom jeden učitel. Potom bude správně: B1 = (#Ucitel) který vede danou (#Prednaska) •B1 ¬ A triviálně (pomocí =, $ a i ve f) •přidejme: B2 = (#Student)-s kteří navštěvují danou (#Prednaska) /0,M:0,M •B2 ¬ A triviálně (pomocí = a $ ve f) •dokážeme napsáním algoritmu, že A ¬ (B1, B2) : P114_10 ‹#› P114_10 10 příklad - pokračování •declare p:Prednaska, u:Ucitel declare s:Student for all p do for all u do for all s do if [[B2w p] s] Ù [B1w p] = u then write s else endif endfor endfor endfor •ve f stačila identita a konjunkce ... P114_10 ‹#› P114_10 11 A à (B1, B2), A » {B1, B2} PREDNASKA UCITEL který vede danou B1 PREDNASKA STUDENT kteří navštěvují danou B2 P114_10 ‹#› P114_10 12 Poznámka o rozkladové konstrukci •Nechť A à (B1, ..., Bn), a nechť Aw = [f (B1w, ..., Bnw)]. •Potom vždy f obsahuje konjunkce a identity •V případě, že A je zadán v singulární rotaci, pak f obsahuje navíc singularizátor. • P114_10 ‹#› P114_10 13 Jak poznat rozložitelnost •(1) použitím definice: v diskusi s expertem se často k atributu složitosti > 2 objeví jeho podatribut; pak hledáme další podatribut původního a pokoušíme se zkonstruovat (algoritmem) původní atribut (viz min. příklad) •(2) podle horního poměru je-li poměr atributu A / (W® ((T1, ..., Tn) ® S)) resp. A / (W® ((T1, ..., Tn) ® (S ® Bool))) tvaru p,n:0,1, tj. horní poměr obrácené funkce je 1, pak A je rozložitelný. (viz násl. obrázek) •(3) použitím věty o rozkladu (viz dále) P114_10 ‹#› P114_10 14 Příklad: A/(W ® ((T1, T2) ® (S ®Bool)) T1 T2 S A text1 text2 0,1 .. p,n P114_10 ‹#› P114_10 15 A à (B1, B2) S T1 text1* B1 S T2 text2* B2 P114_10 ‹#› P114_10 16 Věta 2 (o rozkladu) •Zobecnění obou příkladů •Nechť A je atribut složitosti větší než 2. Nechť existuje jeho vlastní podatribut B1 daný v přípustné singulární rotaci. Potom A à (B1, B2), při čemž (a) definiční obor funkce B2w je stejný jako definiční obor funkce B1w (b) obor hodnot funkce B2w je tvořen zbylými uzlovými typy atributu A, které nejsou v podatributu B1. •Netriviálnost přesné formulace věty (DM2) je dána parcialitou uvažovaných datových funkcí: je třeba se vypořádat s tím, že jedna funkce je na daném argumentu nedefinována (píšeme ^), a druhá - skoro identická - vrací na tomtéž argumentu { }. P114_10 ‹#› P114_10 17 Jádro datového modelu •Nechť A je libovolná množina HIT-atributů nad BZT. Jádrem množiny A je taková množina atributů K, pro kterou platí: •(1) K » A •(2) každý atribut v K je nerozložitelný •(3) neexistuje atribut A Î K tak, že A ¬ K - {A} • •Tedy jádro je minimální množina elementárních atributů, poskytující danou informační schopnost P114_10 ‹#› P114_10 18 Konceptuální model •Konceptuální datový model je tvořen a) bází základních typů BZT b) jádrem K množiny A všech relevantních (datovým modelářem navržených) atributů c) množinou C integritních omezení (formulovaných datovým modelářem nad atributy z K) •Použití: IDM, LDM, Object-Class Model, UML, ... P114_10 ‹#› P114_10 19 DM metodou HIT – minikurs (jak pracovat s příručkou) •Zopakování a přehled pojmů •Příklady k jednotlivým jevům •Metodická doporučení –Pojmenování –Zkoumání rozložitelnosti –Zkoumání odvoditelnosti •Zadání semestrální práce