SWISCI, Biotechnologia, Fizyka, Labolatorium

METODA LIST PROSTYCH

zadanie 1.

Dane są dwa dowolnie wybrane rekordy kartoteki systemu wyszukiwania informacji o komputerach zainstalowanych w danym przedsiębiorstwie. Po przeanalizowaniu rekordów zaproponuj organizację systemu z pełnym jego zdefiniowaniem i wykorzystaniem właściwej modyfikacji met. list prostych.

Odra 1325	IBM 360/50
Elwro	IBM
Polska	USA
1974	1975
32 k	512 k
24 bity	8 bitów
2 programy	16 programów
słowowa	znakowa
110 rozkazów	139 rozkazów

S=<X,A,V,q> definicja systemu informacyjnego, gdzie X to zbiór obiektów, A to zbiór atrybutów, V to zbiór wartości atrybutów, q to funkcja informacji o obiektach.

Zbiór obiektów X={x₁…xn}. Wprawdzie zostały przedstawione tylko dwa opisy obiektów z kartoteki zewnętrznej ale w całej kartotece jest z pewnością n obiektów.

Zbiór atrybutów A={A₁,A₂,A₃,A₄,A₅,A₆,A₇,A₈,A₉}.

Funkcja informacji q:X^×A → V

Zbiory wartości atrybutów:

V_A1={Odra,IBM,inne}→{1,2,3}

V_A2={Elwro,IBM,inne}→{I,II,III}

V_A3={Polska,USA,inne}→{P,U,I}

V_A4={do 1970,1970-1980,po 1980}→{a,b,c}

V_A5={32k,512k,inne}→{A,B,C}

V_A6={24 bity,8 bitów,inne}→{24,8,IN}

V_A7={2 programy,16 programów,inne}→{2p,16p,ip}

V_A8={znakowa,słowowa}→{z,s}

V_A9={110 roz.,139 roz.,inne}→{110,139,iroz}

Kartoteka wtórna jest tu zarazem kartoteką wyszukiwawczą.

Stosuję tu modyfikację z uporządkowaniem opisów obiektów polegającą na ustaleniu kolejności atrybutów w opisie obiektów.

W pytaniach więc musi być taka sama kolejność atrybutów. Ta modyfikacja ułatwia i przyśpiesza proces wyszukiwania.

Wygląd kartoteki wyszukiwawczej:

x₁={(A₁,1)(A₂,I)(A₃,P)(A₄,b)(A₅,A)(A₆,24)(A₇,2p)

(A_8,s)(A₉,110)}

x₂={(A₁,2)(A₂,II)(A₃,U)(A₄,b)(A₅,B)(A₆,8)(A₇,16p)

(A_8,z)(A₉,139)}

Dalej idącą modyfikacją może być modyfikacja polegająca na pogrupowaniu obiektów w/g jednego atrybutu. W naszym przypadku będzie to atrybut A₁, ponieważ zakładam, ze ten atrybut najczęściej pojawia się w pytaniach do systemu oraz dzieli kartotekę równomiernie.

Tabelka przedstawiająca funkcję informacji q dla pogrupowanego systemu

	A₁	A₂	A₃	A₄	A₅	A₆	A₇	A₈	A₉
x₁	1	I	P	b	A	24	2p	s	110
x₂	2	II	U	b	B	8	16p	z	139

zadanie 2.

Przedstawić najbardziej optymalną implementację zadanego systemu informacyjnego dla metody list prostych z odpowiednią modyfikacją .

Opisy obiektów są następujące :

tx₁=a₁*b₂*c₅*d₈*e₁*f₁

tx₂=a₂*b₁*c₄*d₅*e₁*f₁

tx₃=a₂*b₇*c₄*d₄*e₁*f₄

tx₄=a₃*b₇*c₄*d₄*e₁*f₄

tx₅=a₅*b₂*c₄*d₈*e₁*f₅

tx₆=a₄*b₅*c₄*d₆*e₁*f₃

tx₇=a₁*b₂*c₅*d₈*e₁*f₁

tx₈=a₃*b₇*c₅*d₄*e₁*f₁

tx₉=a₂*b₇*c₅*d₄*e₁*f₃

tx₁₀=a₁*b₂*c₅*d₈*e₁*f₃

gdzie aj oznacza deskryptor określony przez j-tą wartość atrybutu a.

Mamy system zdefiniowany w następujący sposób :

S=<X,A,V,q> , gdzie :

X={x₁…x₁₀}-zb.obiektów

A={a,b,c,d,e,f}-zb.atrybutów

V-zb.wartości atrybutów

Va={a₁,a₂,a₃,a₄,a₅}

Vb={b₁,b₂,b₅,b₇}

Vc={c₄,c₅}

Vd={d₄,d₅,d₈}

Ve={e₁}

Vf={f₁,f₃,f₄,f₅}

q - funkcja informacji na obiektach q:X^×A → V

Z systemu możemy usunąć atrybut e, ponieważ posiada on tylko jedną wartość e₁ i wszystkie obiekty systemu są opisane właśnie ta wartością e₁, czyli wszystkie obiekty są nierozróżnialne w systemie ze względu na atrybut e Usunięcie atrybutu e nie wnosi nowej informacji do systemu.

Z kartoteki wyszukiwawczej możemy również usunąć atrybut d, który jest atrybutem równoważnym z atrybutem b. Usuwając atrybut d nie stracimy informacji.

b₁→d₅

b₂→d₈

b₅→d₆

b₇→d₄

Otrzymujemy taką kartotekę:

tx₁=a₁*b₂*c₅*f₁

tx₂=a₂*b₁*c₄*f₁

tx₃=a₂*b₇*c₄*f₄

tx₄=a₃*b₇*c₄*f₄

tx₅=a₅*b₂*c₄*f₅

tx₆=a₄*b₅*c₄*f₃

tx₇=a₁*b₂*c₅*f₁

tx₈=a₃*b₇*c₅*f₁

tx₉=a₂*b₇*c₅*f₃

tx₁₀=a₁*b₂*c₅*f₃

Dokonuję podziału zbioru obiektów w/g atrybutu a , ponieważ jest to atrybut wielowartościowy ,czyli dzieli kartotekę na wiele grup, dzieli kartotekę w miarę równomiernie. Zakładam również ,że atrybut a często występuje w pytaniach do systemu.

tx₁=a₁*b₂*c₅*f₁

tx₇=a₁*b₂*c₅*f₁

tx₁₀=a₁*b₂*c₅*f₃

tx₂=a₂*b₁*c₄*f₁

tx₃=a₂*b₇*c₄*f₄

tx₉=a₂*b₇*c₅*f₃

tx₄=a₃*b₇*c₄*f₄

tx₈=a₃*b₇*c₅*f₁

tx₆=a₄*b₅*c₄*f₃

tx₅=a₅*b₂*c₄*f₅

Tak powstałym grupom można nadać nazwy, bądź numery, które będą spełniać rolę identyfikatora grupy.

zadanie 3.

Dany jest system informacyjny :

x₁={a₁,b₂,c₃,d₂,e₅,f₄}

x₂={a₁,b₂,c₃,d₁,e₅,f₄}

x₃={a₂,b₂,c₂,d₁,e₅,f₂}

x₄={a₂,b₂.c₂.d₁,e₅,f₄}

x₅={a₃,b₂,c₁,d₁,e₅,f₄}

x₇={a₃,b₁,c₁,d₂,e₅,f₂}

x₈={a₁,b₁,c₃,d₂,e₅,f₄}

x₉={a₃,b₁,c₁,d₂,e₅,f₄}

x₁₀={a₂,b₁,c₂,d₂,e₅,f₂}

Gdyby system pracował w oparciu o metodę list prostych to jaką modyfikację tej metody byś zastosował? Odpowiedź należy uzasadnić podając uzyskaną poprawę parametrów systemu /czas wyszukiwania, zajętość pamięci, itp.

Mamy tu system zdefiniowany :

S=<X,A,V,q>

X={x₁,....,x₁₀}

A={A,B,C,D,E,F}

V_A={a₁,a₂,a₃}

V_B={b₁,b₂}

V_C={c₁,c₂,c₃}

V_D={d₁,d₂}

V_E={e₅}

V_F={f₂,f₄}

Z systemu możemy usunąć atrybut E, ponieważ obiekty systemu są opisane jedną wartością tego atrybutu e₅ , czyli wszystkie obiekty są nierozróżnialne w systemie ze względu na atrybut E. Atrybut ten nie wnosi nowej informacji do systemu.

Dlatego , że nie znamy zbioru pytań zadawanych do systemu nie możemy zastosować modyfikacji z organizacją zwartą obiektów , ani modyfikacji zwanej odcedzaniem.

Ponieważ opisy obiektów są alfanumeryczne można tu zastosować podział połówkowy.

Należy opisy obiektów uporządkować rosnąco lub malejąco i ponumerować od 1 do r.

x₈={a₁,b₁,c₃,d₂,e₅,f₄}

x₂={a₁,b₂,c₃,d₁,e₅,f₄}

x₁={a₁,b₂,c₃,d₂,e₅,f₄}

x₆={a₂,b₁,c₂,d₂,e₅,f₂}

x₁₀={a₂,b₁,c₂,d₂,e₅,f₂}

x₃={a₂,b₂,c₂,d₁,e₅,f₂}

x₄={a₂,b₂,c₂,d₁,e₅,f₄}

x₇={a₃,b₁,c₁,d₂,e₅,f₂}

x₉={a₃,b₁,c₁,d₂,e₅,f₄}

x₅={a₃,b₂,c₁,d₁,e₅,f₄}

Pytanie składowe kierowane do systemu powinno być przedstawione w postaci ciągu liczb.

Porównujemy term składowy t_i pytania z opisem obiektu x[r/2], czyli 5. W ten sposób znajdujemy połówkę , w której znajduje się odpowiedź na pytanie składowe t_i.

Na tej połówce dalej możemy dokonać podziału połówkowego.

Więcej niż 3-krotny podział traci sens.

W tej sytuacji (3-krotnego podziału), przy takich samych czasach wyszukiwania metoda grupowania jest dogodniejsza.

W naszym systemie istnieje atrybut wielowartościowy , dający podział na wiele grup i dzieli bazę danych w miarę równomiernie-jest to atrybut A. Możemy założyć , że atrybut ten prawie zawsze występuje w pytaniach kierowanych do systemu.

Po dokonaniu grupowania baza danych ma następującą postać:

x₁={a₁,b₂,c₃,d₂,e₅,f₄}

x₂={a₁,b₂,c₃,d₁,e₅,f₄}

x₈={a₁,b₁,c₃,d₂,e₅,f₄}

x₃={a₂,b₂,c₂,d₁,e₅,f₂}

x₄={a₂,b₂,c₂,d₁,e₅,f₄}

x₆={a₂,b₁,c₂,d₂,e₅,f₂}

x₁₀={a₂,b₁,c₂,d₂,e₅,f₂}

x₅={a₃,b₂,c₁,d₁,e₅,f₄}

x₇={a₃,b₁,c₁,d₂,e₅,f₂}

x₉={a₃,b₁,c₁,d₂,e₅,f₄}

Zajętość pamięci w metodzie list prostych ,jak i w modyfikacjach zależy od ilości obiektów.

Skraca się natomiast czas wyszukiwania.

W metodzie klasycznej czas wyszukiwania jest długi ł=N*ło

N-liczba obiektów, ło-czas przeglądu jednego opisu obiektu.

W modyfikacji z podziałem połówkowym wynosi :

ł''=ł/2^k k - lb. stosowanych podziałów połówkowych a w grupowaniu ł'=ł/k k - lb. grup. Oba te czasy są zbliżone do siebie.

zadanie 4.

Wiedząc ,że a₁,a₂,a₃ są wartościami atrybutu A; b₁,b₂,b₃ wartościami atrybutu B ; c₁,c₂,c₃ wartościami atrybutu C ; d₁,d₂,d₃ wartościami atrybutu D ; e₁,e₂,e₃ wartościami atrybutu E; f₁,f₂,f₃ wartościami atrybutu F.

Zaproponuj organizację bazy danych dla najbardziej optymalnej modyfikacji list prostych wiedząc, że wybrane 10 obiektów systemu opisane jest w sposób następujący :

tx₁=a₁*b₁*c₁*d₁*e₁*f₁

tx₂=a₁*b₁*c₁*d₁*e₁*f₂

tx₃=a₁*b₁*c₂*d₁*e₁*f₃

tx₄=a₁*b₁*c₃*d₁*e₁*f₁

tx₅=a₁*b₁*c₁*d₁*e₁*f₃

tx₆=a₂*b₁*c₂*d₁*e₁*f₂

tx₇=a₂*b₁*c₃*d₁*e₁*f₃

tx₈=a₂*b₂*c₃*d₃*e₁*f₃

tx₉=a3*b₃*c₂*d₂*e₁*f₂

tx₁₀=a₃*b₃*c₂*d₂*e₁*f₂

Opisać szczegółowe wyszukiwanie odpowiedzi na pytanie:

P₁=a₁*b₁*c₁

P₂=a₁

P₃=b₁*d₁*e₁

P₄=c₂*e₁

P₅=(∼c₁)*(∼a₁)

Z systemu możemy usunąć atrybut E , ponieważ wszystkie obiekty systemu są opisane deskryptorem (E,e₁) i zakładam, że reszta obiektów też jest opisana tym deskryptorem , który w tej sytuacji nie wnosi żadnej informacji do systemu , obiekty są nierozróżnialne w systemie ze względu na atrybut E.

W tym przypadku za optymalne rozwiązanie uważam grupowanie. Istnieje bowiem atrybut C , który jest wielowartościowy , dzieli zbiór obiektów na wiele grup , mniej więcej równomiernie. Atrybut ten występuje też w większości pytań zadawanych do systemu , jeżeli przykładowe pytania potraktujemy za grupę reprezentatywną.

Po dokonaniu grupowania baza danych wygląda następująco:

tx₁=c₁*a₁*b₁* d₁*f₁

tx₂=c₁*a₁*b₁*d₁*f₂

tx₅=c₁*a₁*b₁*d₁*f₃

tx₃=c₂*a₁*b₁*d₁*f₃

tx₆=c₂*a₂*b₁*d₁*f₂

tx₉=c₂*a3*b₃*d₂*f₂

tx₁₀=c₂*a₃*b₃*d₂*f₂

x₄=c₃*a₁*b₁* d₁*f₁

tx₇=c₃*a₂*b₁*d₁*f₃

tx₈=c₃*a₂*b₂*d₃*f₃

Można również usunąć atrybut B lub D ,ponieważ zachodzi między nimi relacja równoważności:

b1↔d1

b2↔d3

b3↔d2

Można by usunąć jeden z tych atrybutów , ale trzeba pamiętać zależności między nimi.

Ja jednak pozostawiam oba atrybuty , ponieważ nie mam pewności , że w dalszej części kartoteki te zależności są prawdziwe.

Odpowiedzi na pytania :

P₁=a₁*b₁*c₁

- znajdujemy grupę wyznaczoną przez atrybut C o wartości c₁

- następnie dokonuję przeglądu zupełnego grupy po pozostałych deskryptorach pytania.

P₂=a

- należy dokonać przeglądu zupełnego całej kartoteki

P₃=b₁*d₁*e₁

- dokonuję przeglądu zupełnego całej kartoteki po deskryptorach (B,b₁) i (D,d₁). Pamiętamy ,że deskryptorem (E,e₁) opisane są wszystkie obiekty.

P₄=c₂*e₁

- znajdujemy grupę wyznaczoną przez deskryptor (C,c₂). Odpowiedzią na to pytanie jest cała wyznaczona grupa. (Wszystkie obiekty są opisane deskryptorem (E,e₁)).

P₅=(∼c₁)*(∼a₁)

- pytanie doprowadzamy do postaci z niezaprzeczonymi deskryptorami :

P₅=(c₂+c₃)(a₂+a₃)=c₂a₂+c₂a₃+c₃a₂+c₃a₃

- znajdujemy odpowiedź na pytanie składowe jak w pkt.1

- odpowiedzią na pytanie jest suma odpowiedzi na pytanie składowe.

METODA LIST INWERSYJNYCH

zadanie 1.

Dany jest zbiór obiektów X={x₁,…,x₈} oraz zbiór deskryptorów D={a,b,c.d.e.f.g}.Opisy deskryptorowe obiektów są następujące:

t_x1=f⋅g⋅b

t_x2=d⋅g⋅a⋅e⋅f

t_x3=c

t_x4=c⋅a⋅b

t_x5=f⋅g⋅a⋅b⋅d

t_x6=b⋅c

t_x7=e⋅g⋅d

t_x8=a⋅g⋅e

a.) zaproponuj organizacje bazy danych dla w/w zbioru obiektów w oparciu o metodę list inwersyjnych wiedzą, że w pytaniach najczęściej pojawiają się (kolejno) deskryptory g i b, natomiast najrzadziej a i f.

b.) przedstaw optymalne algorytmy wyszukiwania odpowiedzi na pytania :

P₁=g⋅a⋅d⋅f⋅b

P₂=a⋅d⋅b⋅f+g⋅b

Podaj uzasadnienie słuszności rozwiązań zaproponowanych w pkt. a i b.

Mamy zdefiniowany system S=<X,A,V,q> gdzie X={x_1…x₈}, A={a,b,c,d,e,f,g}, V={0,1}, q:X^×A → V

Chcąc zorganizować wyżej wymienioną bazę danych w oparciu o met.list inwer. musimy utworzyć listy inwersyjne dla każdego deskryptora systemu. Ponieważ deskryptory g i b najczęściej pojawiają się w pytaniach do systemu, listy dla tych deskryptorów umieszczamy na początku kartoteki, a listy a i f z racji, że najrzadziej występują w pytaniach na końcu kartoteki, która przyjmuje postać :

α(g)={x₁,x₂,x₅,x₇,x₈}

α(b)={x₁,x₄,x₅,x₆}

α(c)={x₃,x₄,x₆}

α(d)={x₂,x₅,x₇}

α(e)={x₂,x₇,x₈}

α(a)={x₂,x₄,x₅,x₈}

α(f)={x₁,x₂,x₅}

W listach umieszczamy wprost obiekty ponieważ liczba ich nie jest duża.

P₁=g⋅a⋅d⋅f⋅b

generujemy listy α(g) i α(b)

znajdujemy przecięcie się tych list - {x₁,x₅}

generujemy pozostałe listy α(a), α(d), α(f)

znajdujemy przecięcie się tych list - {x₂,x₅}

znajdujemy przecięcie dwóch uzyskanych zbiorów - {x₅}

P₂=a⋅d⋅b⋅f+g⋅b

P₂=t₁+t₂ gdzie t₁=a⋅d⋅b⋅f t₂=g⋅b

odpowiedzi na pytania składowe t₁ i t₂ otrzymujemy analogicznie jak w poprzednim przypadku σ(t₂)={x₁,x₅} σ(t₁)={x₅} odpowiedz na pytanie P₂ otrzymujemy jako sumę odpowiedzi na pytania składowe

(P₂)= σ(t₁) ∪ σ(t₂) ⇒ σ(P₂)={x₅}∪{x₁,x₅}={x₁,x₅}

Odpowiedz uzyskaliśmy w b.długim czasie, lecz jeśli by nam nie zależało na kompletności i dokładności odpowiedzi, moglibyśmy nie brać pod uwagę deskryptorów a i f, które najrzadziej występują w pytaniach do systemu.

zadanie 2.

Przedstawić najbardziej optymalną implementację zadanego systemu informacyjnego dla metody list inwer. z odpowiednią modyfikacją. Opisy obiektów są następujące:

t_x1=a₁⋅b₂⋅c₅⋅d₈⋅e₁⋅f₁

t_x2=a₂⋅b₁⋅c₄⋅d₅⋅e₁⋅f₁

t_x3=a₂⋅b₇⋅c₄⋅d₄⋅e₁⋅f₄

t_x4=a₃⋅b₇⋅c₄⋅d₄⋅e₁⋅f₄

t_x5=a₅⋅b₂⋅c₄⋅d₈⋅e₁⋅f₅

t_x6=a₄⋅b₅⋅c₄⋅d₆⋅e₁⋅f₃

t_x7=a₁⋅b₂⋅c₅⋅d₈⋅e₁⋅f₁

t_x8=a₃⋅b₇⋅c₅⋅d₄⋅e₁⋅f₁

t_x9=a₂⋅b₇⋅c₅⋅d₄⋅e₁⋅f₃

t_x10=a₁⋅b₂⋅c₅⋅d₈⋅e₁⋅f₃

gdzie a_j oznacza deskryptor określony przez j-tą wartość atrybutu a.

S=<X,A,V,q> gdzie X={x_1…x₁₀} A={a,b,c,d,e,f}, V - zbiór wartości atrybutów gdzie V_a={a₁,a₂,a₃,a₄,a₅}, V_b={b₁,b₂,b₅,b₇}, V_c={c₄,c₅}, V_d={d₄,d₅,d₆,d₈}, V_e={e₁}, V_f={f₁,f₃,f₄,f₅} q - funkcja informacji.

Z opisów obiektów eliminujemy atrybut e₁, który nie wnosi żadnej informacji do systemu, obiekty są nierozróżniakne w systemie ze względu na atrybut e.

α (a₁)={x1,x7,x10}

α(a2)={x2,x3,x9}

α(a3)={x4,x8}

α(a4)={x6}

α(a5)={x5}

α(b1)={x2}

α(b2)={x1,x5,x7,x10}

α(b5)={x6}

α(b7)={x3,x4,x8,x9}

α(c4)={x2,x3,x4,x5,x6}

α(c5)={x1,x7,x8,x9,x10}

α(d4)={x3,x4,x8,x9}

α(d5)={x2}

α(d6)={x6}

α(d8)={x1,x5,x7,x10}

α(f1)={x1,x2,x7,x8}

α(f3)={x6,x9,x10}

α(f4)={x3,x4}

α(f5)={x5}

Zastosuję tu modyfikację z uporządkowaniem list w/g ich długości: od najkrótszej do najdłuższej - zmniejsza to czas wyszukiwania.

Ponadto utworzę listy wspólne dla takich samych list.

W listach umieszczam wprost obiekty, ponieważ liczba obiektów nie jest duża.

Po dokonaniu reorganizacji baza danych przyjmuje postać:

α_w(a4,b5,d6)={x6}

α_w(a5,f5)={x5}

α_w(b1,d5)={x2}

α(a3)={x4,x8}

α(f4)={x3,x4}

α(a1)={x1,x7,x10}

α(a2)={x2,x3,x9}

α(f3)={x6,x9,x10}

α_w(b2,d8)={x1,x5,x7,x10}

α_w(b7,d4)={x3,x4,x8,x9}

α(f1)={x1,x2,x7,x8}

α(c4)={x2,x3,x4,x5,x6}

α(c5)={x1,x7,x8,x9,x10}

zadanie 3.

Dany jest system informacyjny , którego wybrany fragment ma postać :

t_x1=a₁⋅b₂⋅c₃⋅d₂⋅e₅⋅f₄

t_x2=a₁⋅b₂⋅c₃⋅d₂⋅e₅⋅f₄

t_x3=a₂⋅b₂⋅c₂⋅d₁⋅e₅⋅f₂

t_x4=a₂⋅b₂⋅c₂⋅d₁⋅e₅⋅f₄

t_x5=a₃⋅b₂⋅c₁⋅d₁⋅e₁⋅f₄

t_x6=a₂⋅b₁⋅c₂⋅d₂⋅e₅⋅f₂

t_x7=a₃⋅b₁⋅c₁⋅d₂⋅e₅⋅f₂

t_x8=a₁⋅b₁⋅c₃⋅d₂⋅e₅⋅f₄

t_x9=a₃⋅b₁⋅c₁⋅d₂⋅e₅⋅f₄

t_x10=a₂⋅b₁⋅c₁⋅d₂⋅e₅⋅f₂

gdzie odpowiednio a_i oznacza deskryptor wyznaczony przez

i-tą wartość atrybutu A.

Przedstawić optymalny algorytm zakładania bazy danych zgodnie z właściwą modyfikacją metody list inwersyjnych pamiętając ,że najwięcej pytań kierowanych do systemu zawiera pewną wartość atrybutu C.

S=<X,A,V,q>, gdzie X={x1,...,x10}-zb.obiektów;

A={A,B,C,D,E,F}-zb.atrybutów; V-zb.wartści atrybutów, gdzie V_A={a1,a2,a3},V_B={b1,b2},V_C={c1,c2,c3},

V_D={d1,d2},V_E={e5},V_F={f2,f4}

q:X^×A→V - funkcja informacji, D - zb.deskryptorów systemu

D={(A,a1)(A,a2)(A,a3)(B,b1)(B,b2)(C,c1)(C,c2)(C,c3)

(D,d1)(D,d2)(E,e5)(F,f2)(F,f4)}

Deskryptora (E,e5) nie biorę pod uwagę w swoich rozważaniach ponieważ nie wnosi on żadnej nowej informacji do systemu , bo wszystkie obiekty mają w swoim opisie ten deskryptor , czyli są one nierozróżnialne ze względu na ten atrybut.

Utworzę listy inwersyjne dla wszystkich deskryptorów ze zbioru D.

Umieszczę w nich bezpośrednio obiekty, ponieważ liczba obiektów nie jest duża.

Poniewaz najwięcej pytań kierowanych do systemu zawiera pewną wartość atrybutu C - listy,które zawierają ten atrybut umieszczam na początku kartoteki wyszukiwawczej.

Zastosuję listy z podziałami, jeśli lista będzie zawierała kolejne obiekty , oraz listy łączone , dla podobnych list , listy wspólne dla takich samych list.

Algorytm zakładania dazy danych :

α(A,a₁)={x1,x2,x8}

α(A,a2)={x3,x4,x6,x10}

α(A,a3)={x5,x7,x9}

α(B,b1)={x6,x7,x8,x9,x10}

α(B,b2)={x1,x2,x3,x4,x5}

α(C,c1)={x5,x7,x9,x10}

α(C,c2)={x3,x4,x6}

α(C,c3)={x1,x2,x8}

α(D,d1)={x2,x3,x4 ,x5}

α(D,d2)={x1,x6,x7,x8,x9,x10}

α(F,f2)={x3,x6,x7,x10}

α(F,f4)={x1,x2,x4,x5,x8,x9}

Po reorganizacji :

α(C,c1)={x5,x7,x9,x10}

α(C,c2)={x3,x4,x6}

α((C,c3)(A,a1))={x1,x2,x8}

α(A,a2)={x3,x4,x6,x10}

α(A,a3)={x5,x7,x9}

α(B,b1)={x6,x7,x8,x9,x10}

α((B,b2)(D,d1))={x1#x2,x3,x4,x5#}

α(D,d2)={x1,x6,x7,x8,x9,x10}

α(F,f2)={x3,x6,x7,x10}

α(F,f4)={x1,x2,x4,x5,x8,x9}

Wersja oatateczna :

α(C,c1)={x5,x7,x9,x10}

α(C,c2)={x3,x4,x6}

α((C,c3)(A,a1))={x1,x2,x8}

α((A,a2)(F,f2))={x3#x4,x6,x10#x7}

α(A,a3)={x5,x7,x9}

α((B,b1)(D,d2))={#x6,x7,x8,x9,x10#x1}

α((B,b2)(D,d1))={x1#x2,x3,x4,x5#}

α(F,f4)={x1,x2,x4,x5,x8,x9}

Po uproszzeniu:

α((C,c1)(A,a3))={x10#x5,x7,x9#}

α(C,c2)={x3,x4,x6}

α((C,c3)(A,a1))={x1,x2,x8}

α((A,a2)(F,f2))={x3#x4,x6,x10#x7}

α((B,b1)(D,d2))={#x6,x7,x8,x9,x10#x1}

α((B,b2)(D,d1))={x1#x2,x3,x4,x5#}

α(F,f4)={x1,x2,x4,x5,x8,x9}

zadanie 3.

Dany jest system informacyjny S, w którym zgromadzono 20 obiektów opisanych w niżej podany sposób:

t_x1=bdegi	t_x6=adcg	t_x11=bagckd	t_x16=gadc
t_x2=dbh	t_x7=gcd	t_x12=bdh	t_x17=bdg
t_x3=cadg	t_x8=fgkad	t_x13=hfgd	t_x18=chdfi
t_x4=cadg	t_x9=bed	t_x14=dba	t_x19=dgb
t_x5=ebid	t_x10=cbdi	t_x15=hdeifk	t_x20=dehkf

A. Przedstaw optymalnie zorganizowaną bazę danych systemu S z zastosowaniem metody list inwersyjnych przy założeniach:

a) w pytaniach pojawiają się wszystkie deskryptory, przy czym częstość ich występowania można określić następująco:

f(a)>f(c)≥f(b)>f(e)>f(d)>f(i)>f(f)>f(h)>f(k)>f(g)

b) w systemie jest często dokonywana aktualizacja bazy poprzez dodawanie nowych obiektów

c) użtkownicy dość często zapytują o obiekt o zadanym identyfikatorze

d) projektantowi zależy zarówno na oszczędności nośnika informacji jak i minimalizacji czasu wyszukiwania odpowiedzi .

B. Przedstaw dokładnie sposób wyszukiwania odpowiedzi na pytanie P=b⋅(∼i) ⋅(∼g)

Opisy obiektów przedstawię za pomocą tablicy binarnej :

a b c d e f g h i j k

t_{x1 0 1 0 1 1 0 1}_{0 1 0 0}

t_{x2 0 1 1 1}

t_{x3 1 1 1 1}

t_{x4 1 1 1 1}

t_{x5 0 1 1 1 1}

t_{x6 1 1 1 1}

t_{x7 0 1 1 1}

t_{x8 1 1 1 1 1}

t_{x9 0 1 1 1}

t_{x10 0 1 1 1 1}

t_{x11 1 1 1 1 1 1}

t_{x12 1 1 1}

t_x13

t_x14

t_x15

t_x16

t_x17

t_x18

t_x19

t_x20

A. S=<X,A,V,q> ; D-zb.deskryptorów systemu .

Dany jest system informacyjny S, w którym zgromadzono 20 obiektów opisanych w niżej podany sposób:

t_x1=bdegi

t_x2=dbh

t_x3=cadg

t_x4=cadg

t_x5=ebid

t_x6=adcg

t_x7=gcd

t_x8=fgkad

t_x9=bed

t_x10=cbdi

t_x11=bagckd

t_x12=bdh

t_x13=hfgd

t_x14=dba

t_x15=hdeifk

t_x16=gadc

t_x17=bdg

t_x18=chdfi

t_x19=dgb

t_x20=dehkf

A. Przedstaw optymalnie zorganizowaną bazę danych systemu S z zastosowaniem metody list inwersyjnych przy założeniach:

a) w pytaniach pojawiają się wszystkie deskryptory, przy czym częstość ich występowania można określić następująco:

f(a)>f(c)≥f(b)>f(e)>f(d)>f(i)>f(f)>f(h)>f(k)>f(g)

b) w systemie jest często dokonywana aktualizacja bazy poprzez dodawanie nowych obiektów

c) użtkownicy dość często zapytują o obiekt o zadanym identyfikatorze

d) projektantowi zależy zarówno na oszczędności nośnika informacji jak i minimalizacji czasu wyszukiwania odpowiedzi .

B. Przedstaw dokładnie sposób wyszukiwania odpowiedzi na pytanie P=b⋅(∼i) ⋅(∼g)

X={x1,....,x20}

D={a,b,c,d,e,f,g,h,i,k}

- listy inwersyjne tworzę dla wszystkich deskryptorów ze zbioru D , za wyjątkiem deskryptora d , którego nie biorę pod uwagę , ponieważ wszystkie obiekty są nim opisane , czyli są nierozróżnialne ze względu na ten deskryptor;

- kolejność list inwersyjnych jest zdeterminowana częstością występowania deskryptorów w pytaniu (pkt.a) ;

- identyfikatory obiektów (adresy) w ramach list będą uporządkowane rosnąco, to ułatwi nieco aktualizację;

- zastosuję tu modyfikację polegającą na tworzeniu list wspólnych - dla list zawierających dokładnie takie same obiekty (dla identycznych list) ; list łączonych dla podobnych list i list zredukowanych dla list zawierających kolejne obiekty;

Modyfikacje te pozwolą na zminimalizowanie zarówno czasu wyszukiwania , jak i zajętości nośnika ;

- ponieważ lista dla deskryptora g będzie bardzo długa , a o deskryptor ten użytkownik pyta najrzadziej wobec tego utworzymy listę odwrotną (zanegowaną);

Nasza baza danych przyjmie postać :

α_Ł(a,c)={x8,x14#x3,x4,x6,x11,x16#x7,x10,x18}

α_za(b)={x1,x2,x5,x9,x10,x11,x12,x14,x17,x19}

α_Ł(e,i)={x9,x20#x1,x5,x15#x10,x18}

α_Ł(f,h)={x8#x13,x15,x18,x20#x2,x12}

α(k)={x8,x11,x15,x20}

α(∼g)={x2,x5,x9,x10,x12,x14,x15,x18,x20}

B. P=b⋅(∼i) ⋅(∼g)

- generujemy listę α(g)

- generujemy listę α(i) z listy α(e,i)

- znajdujemy listę odwrotną do listy α(i)

- generujemy listę α(∼g)

- znajdujemy przecięcie tych list i uzyskujemy odpowiedź {x2,x9,x12,x14}

zadanie 4.

Dany jest następujący system informacyjny ;

x1={a1,b2,c3,d2,e5,f4}

x2={a1,b2,c3,d1,e5,f4}

x3={a2,b2,c2,d1,e5,f2}

x4={a2,b2,c2,d1,e5,f4}

x5={a3,b2,c1,d1,e5,f4}

x6={a2,b1,c2,d2,e5,f2}

x7={a3,b1,c1,d2,e5,f2}

x8={a1,b1,c3,d2,e5,f4}

x9={a3,b1,c1,d2,e5,f4}

x10={a2,b1,c2,d2,e5,f2}

gdzie ai oznacza deskryptor (a,i) wyznaczony przez i-tą wartość atrybutu a.

Należy przedstawić algorytm zakładania bazy danych dla tego systemu zgodnie z ideą metody list inwersyjnych, zmodyfikowaną w ten sposób , że listy adresowe tworzymy jedynie dla deskryptorów związanych z atrybutami b,c,f.

S=<X,A,V,q> X={x1,...,x10}-zb.obiektów

A={a,b,c,d,e,f }-zb.atrybutów ; V-zb.wartości atrybutów ,gdzie Va={a1,a2,a3} , Vb={b1,b2] , Vc={c1,c2,c3} , Vd={d1,d2} , Ve={e5} , Vf={f2,f4]

D={a1,a2,a3,b1,b2,c1,c2,c3,d1,d2,e5,f2,f4}

Wszystkie obiekty są nierozróżnialne ze względu na atrybut e - deskryptor e5.

Ponieważ mamy wyodrębniony podzbiór deskryptorów D'={b,c,f,} stosuję modyfikację ze zmniejszonym zbiorem list. Polega ona na tym , że listy są tworzone tylko dla deskryptorów ze zbioru D'={b1,b2,c1,c2,c3,f2,f4}

W listach umieszczam wprost obiekty , ponieważ liczba obiektów nie jest duża.

α(b1)={x6,x7,x8,x9,x10}

α(b2)={x1,x2,x3,x4,x5}

α(c1)={x5,x7,x9}

α(c2)={x3,x4,x6,x10}

α(c3)={x1,x2,x8}

α(f2)={x3,x6,x7,x10}

α(f4)={x1,x2,x4,x5,x8,x9}

zadanie 5.

Dany jest zbiór uczniów X pewnej klasymistrzostwa sportowego. Każdego ucznia opisuje pewien podzbiór deskryptorów określający te dyscypliny , w których reprezentuje on najwyższy poziom.

Opisy mają postać :

x1 Jurek :jo∧si∧pł∧br

x2 Mirek :si∧br∧jo∧pł

x3 Antek :ko∧pł∧te∧na

x4 Waldek :te∧ko∧si∧pł

x5 Piotr :br∧si∧pł∧jo

x6 Janusz :te∧ko∧br∧pł

x7 Krzysiek :ko∧te∧pł∧br

x8 Władek :pł∧si∧na∧al

x9 Marek :si∧jo∧br∧pł

x10 Staszek :al∧pł∧si∧na

x11 Jasiu :te∧ko∧br∧pł

x12 Romek :na∧pł∧te∧ko

x13 Zbyszek :te∧ko∧na∧pł

x14 Darek :jo∧pł∧al∧br

x15 Bogdan :br∧jo∧na∧pł

Poszczególne skróty odpowiadają następującym dyscyplinom : jogging, siatkówka, pływanie, brydż, koszykówka, tenis, narciarstwo, alpinizm.

A. Zaproponuj organizację bazy danych systemu informacyjnego opartą na metodzie list inwersyjnych, przechowującego dane o w/w zbiorze uczniów , respektując następujące założenia :

- projektantowi systemu zależy na minimalnej zajętości nośnika informacji;

- do systemu - oprócz klasycznych pytań - często kierowane są żądania wygenerowania informacji o danym uczniu;

B. Omów przebieg wyszukiwania odpowiedzi na pytanie

P=∼ko∧na opierając się na klasycznej metodzie inwersyjnej.

S=<X,A,V,q> X={x1,...,x15}

D={jo,si,pł,br,ko,te,na,al} - zbiór deskryptorów

V={0,1}, q:X^×A → V

Tworzę listy inwersyjne dla wszystkich deskryptorów ze zbioru D , za wyjątkiem deskryptora pł , którym są opisane wszystkie obiekty , a więc są one nierozróżnialne w systemie ze względu na ten deskryptor.

W celu ułatwienia sobie zapisu obiektom nadaję odpowiednio identyfikatory ze zbioru X={x1,...,x15}

α(jo)={x1,x2,x5,x9,x14,x15}

α(si)={x1,x2,x4,x5,x8,x9,x10}

α(br)={x1,x2,x5,x6,x7,x9,x11,x14,x15}

α(ko)={x3,x4,x6,x7,x11,x12,x13}

α(te)={x3,x4,x6,x7,x11,x12,x13}

α(na)={x3,x8,x10,x12,x13,x15}

α(al)={x8,x10,x14}

W celu minimalizacji zajętości nośnika przeprowadzam następujące modyfikacje:

1.tworzę listy łączone dla list podobnych α(jo) i α(si);

2.tworzę listę zanegowaną dla α(br)

3.tworzę listę wspólną dla takich samych list α(ko) i α(te);

α(jo,si)={x14,x15#x1,x2,x5,x9#x4,x8,x10}

α(∼br)={x3,x4,x8,x10,x12,x13}

α(ko,te)={x3,x4,x6,x7,x11,x12,x13}

α(na)={x3,x8,x10,x12,x13,x15}

α(al)={x8,x10,x14}

Aby ułatwić znalezienie informacji o konkretnym uczniu pamiętam w systemie opisy obiektów.

B. P=∼ko∧na

- generuję listę α(ko) i znajduję jej dopełnienie {x1,x2,x5,x8,x9,x10,x14,x15}

- generuję listę α(na) {x3,x8,x10,x12,x13,x15]

- znajduję przecięcie tych dwu list - {x8,x10,x15}-ten zbiór stanowi odpowiedź na pytanie P.

METODA LIST ŁAŃCUCHOWYCH

zadanie 1.

Dany jest system informacyjny S, w którym zgromadzono 20 obiektów opisanych w niżej podany sposób:

t_x1=bcdfe

t_x2=bdegi

t_x3=dbh

t_x₄=cadg

t_x5=ebid

t_x6=adcg

t_x7=gcd

t_x8=fgkad

t_x9=bed

t_x10=ebdi

t_x11=bagckd

t_x12=bdh

t_x13=kfgd

t_x14=dba

t_x15=hdeifk

t_x16=gade

t_x17=bdg

t_x18=chdfi

t_x19=dgb

t_x20=dehkf

A. Przedstaw optymalnie zorganizowaną bazę danych systemu S z zastosowaniem klasycznej metody łańcuchowejprzy założeniach:

a) w pytaniach pojawiają się wszystkie deskryptory, przy czym częstość ich występowania można określić następująco:

f(a)>f(c)≥f(b)>f(e)>f(d)>f(i)>f(f)>f(h)>f(k)>f(g)

b) w systemie jest często dokonywana aktualizacja bazy poprzez dodawanie nowych obiektów

c) użtkownicy dość często zapytują o obiekt o zadanym identyfikatorze

d) projektantowi zależy zarówno na oszczędności nośnika informacji jak i minimalizacji czasu wyszukiwania odpowiedzi .

B. Przedstaw dokładnie sposób wyszukiwania odpowiedzi na pytanie P=b⋅(∼i) ⋅(∼g)

S=<X,A,V,q> X={x1,...,x20}-zb.obiektów

A-zb.atrybutów , V-zb.wartości atrybutów (0,1)

q:X^×A → V - funkcja informacji

Zb.deskryptorów: D={a,b,c,d,e,f,g,h,i,k}

Nie biorę pod uwagę atrybutu d , ponieważ nie wnosi żadnej nowej informacji (wszystkie obiekty są opisane tą samą wartością). Obiekty są nierozróżnialne w systemie , możemy więc usunąć go z opisu obiektów systemu.

Stosuję łańcuchowanie w przód i tył , które ułatwia i przyśpiesza aktualizację, która jest tutaj często dokonywana. Biorąc pod uwagę częstość występowania deskryptorów w pytaniach łańcuchuję tylko po czterech, najczęściej występujących w pytaniach, deskryptorach a c b e - zmniejsza to zajętość nośnika.

Tworzę też tablicę identyfikatorów w której obiektowi odpowiada identyfikator.

Będę tu stosować odsyłacze względem pierwszego adresu obiektu zawierającego deskryptor d_i dla łańcuchowania w przód a dla łańcuchowania w tył odsyłacze względem ostatniego adresu obiektu zawierającego deskryptor d_i

adres

obiektu

opis

obiektu

odsyłacz w tył

odsyłacz w przód

x₁

∅

x₂

-18

-19

x₃

-17

x₄

∅

-17

x₅

-16

-18

x₆

-12

-14

x₇

-12

+10

x₈

-10

x₉

-14

-15

x₁₀

-10

-11

+10

+14

x₁₁

-8

-9

-11

+10

+11

+17

x₁₂

-8

+13

x₁₃

x₁₄

-5

-7

+12

+16

x₁₅

-10

+15

x₁₆

-2

-5

∅

+19

x₁₇

-5

+18

x₁₈

-7

∅

x₁₉

-2

∅

x₂₀

-4

∅

Łańcuchy dla poszczególnych deskryptorów mają postać:

w przód

α(a)={4-2-4-7-10-12-∅}

α(b)={1-1-2-4-8-9-10-11-13-16-18-∅}

α(c)={1-3-5-6-10-17-∅}

α(e)={1-1-4-8-9-14-15-19-∅}

w tył

α(a)={16-2-5-8-10-12-∅}

α(b)={19-2-5-7-8-9-10-14-16-17-18-∅}

α(c)={18-7-11-12-14-17-∅}

α(e)={20-4-5-10-11-15-18-19-∅}

Tworzymy tablicę zakotwiczeń dla deskryptorów dla których stworzyliśmy łańcuchy

deskr. d_i	adr. początk.	adr. końc.	dl. łańcucha
a	4	16	6
b	1	19	11
c	1	18	6
e	1	20	8

Tablica identyfikatorów

adr. obiektu

identyfikator

adr. obiektu

identyfikator

x₁

x₂

x₃

x₄

x₅

x₆

x₇

x₈

x₉

x₁₀

x₁₁

x₁₂

x₁₃

x₁₄

x₁₅

x₁₆

x₁₇

x₁₈

x₁₉

x₂₀

Wyszukiwanie odpowiedzi P=b⋅(∼i) ⋅(∼g)

znajdujemy wszystkie obiekty mające w swoim opisie deskryptor b. Będzie to odp. przybliżona.

aby otrzymać odp. dokładną dokonujemy przeglądu zupełnego odpowiedzi przybliżonej po deskryptorze:

- i i znajdujemy dopełnienie zbioru

- otrzymany zbiór poddajemy kolejnemu przeglądowi zupełnemu po deskryptorze g i znajdujemy dopełnienie otrzymanego zbioru, które stanowić będzie odpowiedź dokładną na zadane pytanie.

zadanie 2.

Wykazać przydatność stosowania podwójnego łańcuchowania. Kiedy warto stosować łańcuchowanie w przód i w tył równocześnie ?

Podwójne łańcuchowanie nie zmienia samej metody wyszukiwania. Jest przydatna gdy zależy nam na szybkim procesie aktualizacji. Pozwala nam na szybkie ustalenie pozycji każdego obiektu w łańcuchu, co przyśpiesza właśnie aktualizację. Warto ją stosować gdy do bazy danych często dopisuje się lub usówa atrybuty, obiekty.

zadanie 3.

Dany jest następujący system informacyjny :

x₁={a₁,b₂,c₃,d₂,e₅,f₄}

x₂={a₁,b₂,c₃,d₁,e₅,f₄}

x₃={a₂,b₂,c₂,d₁,e₅,f₂}

x₄={a₂,b₂,c₂,d₁,e₅,f₄}

x₅={a₃,b₂,c₁,d₁,e₅,f₄}

x₆={a₂,b₁,c₂,d₂,e₅,f₂}

x₇={a₃,b₁,c₁,d₂,e₅,f₂}

x₈={a₁,b₁,c₃,d₂,e₅,f₄}

x₉={a₃,b₁,c₁,d₂,e₅,f₄}

x₁₀={a₂,b₁,c₂,d₂,e₅,f₂}

Należy skonstruować bazę danych dla systemu opisanego powyżej zgodnie z metodą list łańcuchowych oraz przedstawić optymalną postać kartoteki wyszukiwawczej dla takiego systemu.

Nie bierzemy pod uwagę w naszych rozwarzaniach deskryptora e₅ ponieważ są nim opisane wszystkie obiekty systemu. Deskryptor ten nie wnosi żeadnej informacji do systemu, bo obiekty są nierozróżnialne ze względu na ten deskryptor.

Zastosuję tu łańcuchowanie w przód i w tył ponieważ ułatwia to dostęp do obiektu. Zastosuję tu odsyłacze w postaci skoku czyli różnicy między dwoma sąsiednimi pozycjami łańucha.

adres

obiektu

opis

obiektu

odsyłacz w przód

odsyłacz w tył

x₁

a₁

b₂

c₃

d₂

f₄

∅

x₂

a₁

b₂

c₃

d₁

f₄

-1

∅

-1

x₃

a₂

b₂

c₂

d₁

f₂

∅

-1

∅

-1

∅

x₄

a₂

b₂

c₂

d₁

f₄

-1

-2

x₅

a₃

b₂

c₁

d₁

f₄

∅

-1

∅

-1

x₆

a₂

b₁

c₂

d₂

f₂

-2

∅

-2

-5

-3

x₇

a₃

b₁

c₁

d₂

f₂

-2

-1

-2

-1

x₈

a₁

b₁

c₃

d₂

f₄

∅

-6

-1

-6

-1

-3

x₉

a₃

b₁

c₁

d₂

f₄

∅

-2

-1

-2

-1

x₁₀

a₂

b₁

c₂

d₂

f₂

∅

-4

-1

-4

-1

-3

Łańcuchy dla poszczególnych deskryptorów mają postać :

w przód	w tył
α(a₁)={1-1-6-∅}	α(a₁)={8-6-1-∅}
α(a₂)={3-1-2-4-∅}	α(a₂)={10-4-2-1-∅}
α(a₃)={5-2-2-∅}	α(a₃)={9-2-2-∅}
α(b₁)={6-1-1-1-1-∅}	α(b₁)={10-1-1-1-1-∅}
α(b₂)={1-1-1-1-1-∅}	α(b₂)={5-1-1-1-1-∅}
α(c₁)={5-2-2-∅}	α(c₁)={9-2-2-∅}
α(c₂)={3-1-2-4-∅}	α(c₂)={10-4-2-1-∅}
α(c₃)={1-1-6-∅}	α(c₃)={8-6-1-∅}
α(d₁)={2-1-1-1-∅}	α(d₁)={5-1-1-1-∅}
α(d₂)={1-5-1-1-1-1-∅}	α(d₂)={10-1-1-1-1-5-∅}
α(f₂)={3-3-1-3-∅}	α(f₂)={10-3-1-3-∅}
α(f₄)={1-1-2-1-3-1-∅}	α(f₄)={9-1-3-1-2-1-∅}

Tablica zakotwiczeń:

deskr. d_i	adr. początk.	adr. końc.	dl. łańcucha
a₁	1	8	3
a₂	3	10	4
a₃	5	9	3
b₁	6	10	5
b₂	1	5	5
c₁	5	9	3
c₂	3	10	4
c₃	1	8	3
d₁	2	5	4
d₂	1	10	6
f₂	3	10	4
f₄	1	9	6

zadanie 4.

Dany jest zbiór obiektów X={x₁,x₂,x₃,x₄,x₅}. Obiekty te opisane są następująco :

x₁ : a₂∧b₃∧c₁

x_{2 :} a₂∧b₂∧c₂

x₃: a₁∧b₁∧c₁

x₄: a₂∧b₃∧c₁

x₅: a₂∧b₁∧c₂

gdzie A={A,B,C}, V_A={a₁,a₂}, V_B={b₁,b₂,b₃}, V_C={c₁,c₂}.

Zbuduj kartotekę wyszukiwawczą opartą o metodę łańcuchową oraz :

- dopisz nowy obiekt x₈ , o opisie a₁∧b₂∧c₁ na początku kartoteki (przed x₁)

- usuń x₃

- zaktualizuj opis deskryptorowy obiektu x₂ - nowy opis to

a₁∧b₃∧c_2.

Zastosuj tu łańcuchowanie w przód, a odsyłacze będą względem pierwszego adresu obiektu zawierającego deskryptor d_i.

adres obiektu

opis obiektu

odsyłacz w przód

x₁

a₂

b₃

c₁

x₂

a₂

b₂

c₂

∅

x₃

a₁

b₁

c₁

∅

x₄

a₂

b₃

c₁

∅

x₅

a₂

b₁

c₂

∅

Tak wyglądają łańcuchy :

α(a₁)={3-∅}

α(a₂)={1-1-3-4-∅}

α(b₁)={3-2-∅}

α(b₂)={2-∅}

α(b₃)={1-3-∅}

α(c₁)={1-2-3-∅}

α(c₂)={2-3-∅}

Łańcuchy nie są pamiętane lecz odsyłacze przy opisach obiektów, łańcuchy jedynie mogą zostać odtworzone.

Tablica zakotwiczeń:

deskryptor	początek łańc.	długość łańc.
a₁	3	1
a₂	1	4
b₁	3	2
b₂	2	1
b₃	1	2
c₁	1	3
c₂	2	2

Dopisanie nowego obiektu x_{8 :}a₁∧b₃∧c₂ na początku kartoteki wyszukiwawczej. Obiekt umieszczamy na początku zbioru obiektów systemu, zapamiętujemy adres który w naszym przypadku będzie 8 (umownie od identyfikatora x₈). Bierzemy pierwszy deskryptor do procesu aktualizacji czyli a1. Sprawdzamy czy znajduje się on w tablicy zakotwiczeń. Jeżeli znaleźliśmy deskryptor a₁ w tabl. zakotw. to zwiększamy dł. łańc. o 1 i zmieniamy adres początku łańc. Przechodzimy do kartoteki wyszukiwawczej i dkonujemy zmiany odsyłaczy dla tego deskryptora. Dla pozostałych deskrpt. podobna procedura.

Zaktualizowane łańc. będą miały postać :

α(a₁)={8-3-∅}

α(b₂)={8-2-∅}

α(c₁)={8-1-3-4-∅}

Tablica zakotwiczeń :

deskryptor	początek łańc.	długość łańc.
a₁	8	2
a₂	1	4
b₁	3	2
b₂	8	2
b₃	1	2
c₁	8	4
c₂	2	2

Usunięcie obiektu x₃.

Znajduję obiekt o adresie x₃ wybieram pierwszy deskryptor z opisu usówanego obiektu czyli a₁. Z tabl. zakotw. znajduję ten deskryptor, zmniejszam długość tego łańcucha o 1. Jeśli otrzymana dł. łańc. jest =0 to wykreślam z tabl. zakotw. linijkę dotyczącą tego deskryptora. Jeśli dł. łańc. ≠0 to przechodzę na podstawie adresu początku łańcucha do kartoteki wyszukiwawczej i tam muszę zmienić odsyłacze dla tego deskryptora. Dla pozostałych deskryptorów podobna procedura.

Zaktualizowane łańcuchy będą miały postać :

α(a₁)={∅}

α(b₁)={5-∅}

α(c₁)={1-3-∅}

Tablica zakotwiczeń :

deskryptor	początek łańc.	długość łańc.
a₂	1	4
b₁	5	1
b₂	2	1
b₃	1	2
c₁	1	2
c₂	2	2

Zaktualizowanie obiektu x₂ : a₁∧b₃∧c₂

- znajduję obiekt o zadanym nieaktualnym opisie x₂

- dokonuję zmiany wszystkich łańcuchów związanych z deskryptorami, które zostały zaktualizowane, czyli zmiany odsyłaczy dla deskryptorow nieaktualnych jak i dla nowych w całej kartotece oraz w tabl. zakotw.

Dokonywana jest tutaj pełna reorganizacja kartoteki wyszukiwawczej.

Po dokonaniu aktualizacji łańcuchy i tabl. zakotwiczeń jest :

α(a₁)={2-1-∅}

α(a₂)={1-3-4-∅}

α(b₁)={3-2-∅}

α(b₂)={∅}

α(b₃)={1-1-3-∅}

α(c₁)={1-2-3-∅}

α(c₂)={2-3-∅}

Tablica zakotwiczeń:

deskryptor	początek łańc.	długość łańc.
a₁	2	2
a₂	1	3
b₁	3	2
b₃	1	3
c₁	1	3
c₂	2	2

Aktalizacja jest wadą tej metody, jest skomplikowana i czasochłonna.

f(C_wst,x₁)=4/7=0,57

f(C_wst,x₂)=4/7=0,57

f(C_wst,x₃)=3/8=0,37

f(C_wst,x₄)=4/7=0,57

f(C_wst,x₅)=4/7=0,57

f(C_wst,x₆)=2/9=0,22

f(C_wst,x₇)=3/8=0,37

f(C_wst,x₈)=2/9=0,22

f(C_wst,x₉)=1/10=0,1

f(C_wst,x₁₀)=1/10=0,1

x₁ 0,57

x₂ 0,57

x₄ 0,57

x₅ 0,57

x₃ 0,37

x₇ 0,37

x₆ 0,22

x₈ 0,22

x₉ 0,1

x₁₀ 0,1

zadanie 5.

Dany jest system S=<X,A,V,q> w ktorym obiekty X={x₁…x₁₀} zostały opisane przez 4 atrybuty A={a,b,c,d}.

Każdy z nich może przyjmować jedną z trzech wartości np.: V_a={a₁,a₂,a₃}. system ten zorganizowano zgodnie z met. łańcuchową. Po pewnym czasie eksploatacji tego systemu okazało się, że najczęściej stawiane pytania do systemu są postaci :

t=a₁⋅b₃⋅c₂

t=a₁⋅b₂⋅c₁

t=a₂⋅b₂⋅c₁

t=a₂⋅b₂⋅c₂

t=a₁⋅b₃⋅c₁

Jak można w związku z tym zmodyfikować ten system ? Przedstaw zreorganizowaną strukturę tego systemu.

Zbiór deskryptorów systemu :

D={a₁,a₂,a₃,b₁,b₂,b₃,c₁,c₂,c₃,d₁,d₂,d₃}

Znając najczęściej stawiane pytania mogę zaproponować modyfikację polegającą na łańcuchowaniu grup obiektow.

Możemy wyodrębnić podzbiór deskryptorów D₀ który będzie zbiorem deskryptorów najczęściej występujących w pytaniach do systemu. f(x₇,x₇)=4

D₀={a₁,a₂, b₂,b₃,c₁,c₂}

dla tych deskryptorow tworzę dowolną metodę łańcucha np.: metodą łańcuchowania w przód oraz tworzę tablicę zakotwiczeń.

METODA SALTONA - ALGORYTM ROCCHIO'A

zadanie 1.

W jednym z kroków wiązania w grupy w/g algorytmu Rocchia otrzymano następujące współczynniki korelacji obiektów x₁…x₆ z przypuszczalnym centrum grupy

k(x₁)=0,20

k(x₂)=0,11

k(x₃)=0,30

k(x₄)=0,48

k(x₅)=0,5

k(x₆)=0,05

k(x₇)=0,28

k(x₈)=0,41

Załóżmy , że minimalny rozmiar grupy wynosi M₁=2 , zaś max.M₂=5. Test gęstości zakłada natomiast , że conajmniej N₁=6 obiektów ma współczynnik korelacji (z centrum grupy) wyższy niż p₁=0,1 oraz , że conajmniej N₂=3 ma ten współczynnik wyższy niż p₂=0,4. Jaki jest rezultat tego etapu wiązania obiektów w grupy.

Minimalny rozmiar grupy M₁=2

Maksymalny rozmiar grupy M₂=5

Parametry testu gęstości : N₁=6 p₁=0,1 N₂=3 p₂=0,4

k(x₅)=0,5

k(x₄)=0,48

k(x₃)=0,30

k(x₈)=0,41 N₂

k(x₇)=0,28

k(x₁)=0,20

k(x₂)=0,11 N₁p_min=0,41

k(x₆)=0,05

G={x₅,x₄,x₈}

Rezultatem tego etapu wiązania dokumentów w grupy jest grupa dokumentów związanych: G={x₅,x₄,x₈}

i grupa dokumentówswobodnych (niezwiązanych) L={x₁,x₂,x₃,x₆,x₇}

Rozmiar grupy G mieści się w przedziale wyznaczonym przez minimalny i max. rozmir grupy.

zadanie 2.

Dla podanego zbioru obiektów dokonaj ich grupowania stosując algorytm Rocchia , a następnie przedstaw problem wyszukiwania strukturalnego w tym systemie.

t_x1=a₁_⋅b₁_⋅c₁_⋅d₁_⋅e₁_⋅f₁

t_x2= a₁_⋅b₁_⋅c₁_⋅d₁_⋅e₁_⋅f₂

t_x3= a₁_⋅b₁_⋅c₂_⋅d₁_⋅e₁_⋅f₃

t_x4= a₁_⋅b₁_⋅c₃_⋅d₁_⋅e₁_⋅f₁

t_x5= a₁_⋅b₁_⋅c₁_⋅d₁_⋅e₁_⋅f₃

t_x6= a₂_⋅b₁_⋅c₂_⋅d₁_⋅e₁_⋅f₂

t_x7= a₂_⋅b₁_⋅c₃_⋅d₁_⋅e₁_⋅f₃

t_x8= a₂_⋅b₂_⋅c₃_⋅d₃_⋅e₁_⋅f₃

t_x9= a₃_⋅b₃_⋅c₂_⋅d₂_⋅e₁_⋅f₂

t_x10= a₃_⋅b₃_⋅c₂_⋅d₂_⋅e₁_⋅f₂

W naszych rozważaniach mogę pominąć atrybut e o wartości e₁ , ponieważ wszystkie obiekty są nim opisane i są nierozróżnialne w systemie ze względu na ten deskryptor ), więc deskryptor e₁ nie wnosi nowej informacji do systemu.

Możemy również pominąć atrybut d , który jest równoważny z atrybutem b. Pomijając ten atrybut nie utracimy informacji o obiektach . Musimy tylko pamiętać zależności między tymi atrybutami: b₁_↔d₁b₂_↔d₃b₃_↔d₂

Otrzymamy kartotekę , która ma postać:

t_x1=a₁_⋅b₁_⋅c₁_⋅f₁

t_x2= a₁_⋅b₁_⋅c₁_⋅f₂

t_x3= a₁_⋅b₁_⋅c₂_⋅f₃

t_x4= a₁_⋅b₁_⋅c₃_⋅f₁

t_x5= a₁_⋅b₁_⋅c₁_⋅f₃

t_x6= a₂_⋅b₁_⋅c₂_⋅f₂

t_x7= a₂_⋅b₁_⋅c₃_⋅f₃

t_x8= a₂_⋅b₂_⋅c₃_⋅f₃

t_x9= a₃_⋅b₃_⋅c₂_⋅f₂

t_x10= a₃_⋅b₃_⋅c₂_⋅f₂

Parametry testu gęstości:

N₁=3 p₁=0,6 N₂=5 p₂=0,2

N_1c=4 p_1c=0,5 N_2c=6 p_2c=0,2

Będę tu stosować grupowanie rozłączne , bez redundancji.

Do liczenia współczynników korelacji wykorzystam następujący wzór:

Wybieram obiekt x₁ jako przypuszczalne centrum grupy i dla tego obiektu przeprowadzam test gęstości.

Ustawiam obiekty w kolejności malejących współ.korelacji.

f(x_1,x₁)=4/4=1

f(x_1,x₂)=3/5=0,6

f(x_1,x₃)=2/6=0,33

f(x_1,x₄)=3/5=0,6

f(x_1,x₅)=3/5=0,6

f(x_1,x₆)=1/7=0,14

f(x_1,x₇)=1/7=0,14

f(x_1,x₈)=0

f(x_1,x₉)=0

f(x_1,x₁₀)=0

x₁ 1

x₂ 0,6

x₄ 0,6

x₅ 0,6

x₃ 0,33

x₆ 0,14

x₇ 0,14

x₈ 0

x₉ 0

x₁₀ 0

p_min=0,6

Tworzymy grupę o wsp.korel. ≥ p_min.

G_wst={x₁,x₂,x₄,x₅} - grupa wstępna. Wyodrębniamy centroid z pojęć wstępnych w dokumentach grupy. C_wst={a₁,b₁,c₁,c₃,f₁,f₂,f₃} - centroid grupy wstępnej.

Teraz tworzymy grupę poprawioną. W tym celu obliczamy wsp.korel. centroidu ze wszystkimi obiektami.

p_min=0,57

G={x₁,x₂,x₄,x₅}

C={a₁,b₁,c₁,c₃,f₁,f₂,f₃}-centroid zawiera te same cechy , co zbiór pojęć występujących w grupie

L={x₃,x₆,x₇,x₈,x₉,x₁₀}-zbiór dokumentów niezwiązanych.

Teraz przeprowadzam grupowanie pozostałych obiektów niezwiązanych,

Jako przypuszczalne centrum nowej grupy wybieram x₇ i dla tego obiektu przeprowadzam test gęstości.

f(x₇,x₇)=4/4=1 x₇1

f(x₇,x₃)=2/6=0,33 x₈ 0,6

f(x₇,x₆)=2/6=0,33 x₃0,33

f(x₇,x₈)=3/5=0,6 x₆ 0,33

f(x₇,x₉)=0 x₉ 0

f(x₇,x₁₀)=0 x₁₀ 0

Obiekt nie przeszedł testu gęstości , ponieważ nie są spełnione parametry testu gęstości. Obiekt ten staje się obiektem izolowanym.

W wyniku przeprowadzenia algorytmu otrzymaliśmy grupę obiektów związanych G={x₁,x₂,x₄,x₅} z centroidem C={a₁,b₁,c₁,c₃,f₁,f₂,f₃}.Otrzymaliśmy też grupę obiektów izolowanych : L={x₃,x₆,x₇,x₈,x₉,x₁₀}

Wyszukiwanie strukturalne:

Pytanie składowe por/ównujemy najpierw z pniami , czyli obliczamy współczynnik korelacji pytania z każdym pniem. Wybieramy tzw.pnie najbardziej obiecujące czyli takie , dla których współczynnik korelacji z pytaniem jest najwyższy. Następnie usuwamy wybrane pnie i przechodzimy o poziom niżej do centroidów i obliczamy współczynnik korelacji z centroidami. Wybieramy centroidy najbardziej obiecujące. Przechodzimy do obliczeń korelacji z dokumentami , czyli obiektami wybranych grup. Dopiero dokumenty, których współczynniki korelacji są większe od współczynnika założonego minimalnego , stanowią odpowiedź nz pytanie.Jeśli współczynniki są małe to wracają do pominiętych pni i liczymy współczynniki dla jego centroidu , aby nie pominąć istotnej odpowiedzi na pytanie.

zadanie 3.

Dany jest zbiór dokumentów X={x₁…x₁₀},ktore są opisane pojęciami:

t_x1=a⋅d⋅f⋅g

t_x2=b⋅c⋅d⋅f⋅h⋅i⋅j

t_x3=a⋅e⋅i⋅j

t_x4=d⋅e⋅f⋅g⋅h

t_x5=c⋅e⋅h⋅i⋅j

t_x6=a⋅d⋅f

t_x7=b⋅c⋅g⋅j

t_x8=a⋅f⋅g⋅h⋅i

t_x9=d⋅e⋅j⋅f

t_x10=g⋅h⋅i⋅j

Dla zbioru dokumentów należy dokonać ich podziału na grupy stosując algorytm Rocchia.

Przedstawić realizację tego algorytmu wybierając jako przypuszczalne centrum grupy kolejno dokumenty x₃ i x₄.

Scharakteryzować wygenerowane grupy.

Założenia:

1)dla wielkości grupy minimalnej rozmiar M₁=3, max. M₂=6

2)dla testu gęstości p₁=0,2 N₁=6 p₂=0,4 N₂=4

3)dla określenia współczynnika korelacji między x_i oraz x_j należy stosować funkcję :

gdzie p_i i p_j - zbiory pojęć opisujących dokumenty x_i oraz x_j.

Centroidem będzie tu zb.pojęć grupy poprawionej . Dla przypuszczalnego centrum grupy - x₃ , liczę współczynniki korelacji ze wszystkimi dokumentami.

f(x₃,x₃)=4/4=1

f(x₃,x₁)=1/7=0,14

f(x₃,x₂)=2/9=0,22

f(x₃,x₄)=1/8=0,125

f(x₃,x₅)=3/6=0,5

f(x₃,x₆)=1/6=0,16

f(x₃,x₇)=1/7=0,14

f(x₃,x₈)=2/7=0,28

f(x₃,x₉)=2/6=0,33

f(x₃,x₁₀)=2/6=0,33

Ustawiam obiekty w kolejności malejących współ.korelacji:

x₃1

0x08 graphic

x₅0,5

x₉ 0,33

x₁₀0,33

x₈0,28

x₂ 0,22

x₆0,16

x₁ 0,14

x₇0,14

x₄ 0,125

Dokument x₃ nie przeszedł testu gęstości , ponieważ rozmiar grupy minimalnej wynosi M₁=3 i conajmniej N₂=4 powinno mieć współczynnik większy lub równy p₂=0.4 , a ten podział nie spełnia tych założeń.

Teraz przypuszczalnym centrum grupy będzie x₄.

f(x₄,x₄)=5/5=1

f(x₄,x₁)=3/6=0,5

f(x₄,x₂)=3/9=0,33

f(x₄,x₃)=1/8=0,125

f(x₄,x₅)=2/8=0.25

f(x₄,x₆)=2/6=0,33

f(x₄,x₇)=1/8=0,125

f(x₄,x₈)=3/7=0,428

f(x₄,x₉)=3/6=0,5

f(x₄,x₁₀)=2/7=0,28

Ustawiam obiekty w kolejności malejących współ.korelacji:

x₄1

x₁0,5 m₁

x₉0,5

x₈0,428

x₂0,33

x₆0,33

x₁₀0,28 m₂

x₅0,25

x₃0,125

x₇0,125

Test gęstości mówi nam , że conajmniej N₁=6 dokumentów powinno mieć z wybranym dokumentem współ.korelacji wyższy niż parametr p₁=0,2 oraz conajmniej N₂=4 obiekty wyższy niż p₂=0,4.

Z tego wniosek , że obiekt x₄ przeszedł pomyślnie test gęstości.

Określam współczynnik korelacji progowej p_min:

Dokument	różnica wsp.korelacji
x₈ x₂	0,098
x₂ x₆	0
x₆ x₁₀	0,05
x₁₀ x₅	0,03
x₅ x₃	0,125

p_min=0,428

Tworzę grupę obiektów o współ.korelacji większych lub równych od p_min : G={x₄,x₁,x₉,x₈}

Grupa ta (jej rozmiar) powinien mieścić się w przedziale utworzonym przez minimalny i maksymalny rozmiar grupy.

Wyodrębniamy centroid z pojęć występujących w dokumentach grupy wstępnej: C={a,d,e,f,g,h,i,j}.

Następnie tworzymy grupę poprawioną - w tym celu obliczamy współ.korelacji centroidu ze wszystkimi obiektami:

f(c,x₁)=4/8=0,5

f(c,x₂)=5/10=0,5

f(c,x₃)=4/8=0,5

f(c,x₄)=5/8=0,625

f(c,x₅)=4/9=0,44

f(c,x₆)=3/8=0,375

f(c,x₇)=2/10=0,2

f(c,x₈)=5/8=0,625

f(c,x₉)=4/8=0,5

f(c,x₁₀)=4/8=0,5

Porządkuję obiekty w/g malejących współ.korelacji:

x₄0,625

x₈0,625

x₁0,5

x₂0,5

x₃0,5

x₉0,5

x₁₀0,5

x₅0,44

x₆0,375

x₇0,2

p_min=0,44

G={x₄,x₈,x₁,x₂,x₃,x₉,x₁₀,x₅}

Obiekty w powstałej grupie są uporządkowane w/g malejących współ.korelacji.

Grupa ta jest większa niż założony maksymalny rozmiar grupy, więc obcinam ją do max. rozmiaru grupy M₂=6 . Obcinam dwa ostatnie obiekty.

G={x₄,x₈,x₁,x₂,x₃,x₉,}

C={a,d,e,f,g,h,i,j,}- centroid

C={a,b,c,d,e,f,g,h,i,j}-zb.cech występujących w grupie.

Pozostaje jeszcze grupa dokumentów swobodnych {x₅,x₆,x₇,x₁₀}.

Dokumenty tej grupy są do siebie w miarę podobne . Odpowiedź uzyskana jednak może być nie kompletna lub niedokładna.

METODA GHOSHA

Zadanie 34 (zestaw b1,luty 91)

Danych jest 11 atrybutów binarnych A_1,A₂,..., A₁₁. Należy skonstruować zbalansowany algbraiczny schemat zbioru BFS₂ w oparciu o dowolnie wybraną geometrię skończoną. Dokonać oszacowania nadmiarowości występującej w schemacie oraz przedstawić ilustrację graficzną przestrzeni dyskretnej.

A={ A₁,A2,....,A11}-atrybuty binarne

Wybieram odpowiednią geometrię. Biorę pod uwagę geometrię dla atrybutów binarnych , ponieważ dane jest 11 atrybutów binarnych.

EG(2,5)

-bo tu lb.atr.binarnych wynosi p^2=5^2=25 ,a w EG(2,3) p^2=9 więc nie zmimeści się w tym 11 atr.bin. z zadania.

lb.klas K=(p²+p)(p nad 2 )=30 *10=300

d.R=((2^p-p-1)/(2^p))*G-1=((32-6)/32)*30-1 =23.4

PG(2,3)

-bo tu lb. atr. bin. wynosi 13 ,a w PG(2,2) jest ich 7 ,a to jest za mało.

lb. klas K=(G nad 2)=(13 nad 2)=78

redundancja R=((2^s+1-s-2)/(2^s+1))*G-1=7.93

Liczę lb. klas i redundancję ,ponieważ lb. klas wpływa na zajętość pamięci ,a redundancja określa nadmiarowość.

Po dokonaniu analizy wybieram geometrię rzutową PG(2,3) ,ponieważ jest tu mniejsza zajętość pamięci niż w EG(2,5) (a zajętość pamięcizależy od lb. klas w systemie) Ponadto PG(2,3) wnosi mniejszą redundancję niż EG(2,5)

Tworzę teraz kartotekę wyszukiwawczą.

Najpierw przyporządkowuje atrybutom punkty w przestrzeni rzutowej:

A₁=001 A₂=010 A₃=011 A₄=100 A₅=101 A₆=110 A₇=111 A₈=021 A₉=121 A₁₀=201 A₁₁=211 A₁₂=221 A₁₃=210

Przyjmujemy dwa atrybuty sztuczne A₁₂i A₁₃. Będą one w bazie danych, ale nigdy nie wystąpią w opisie obiektów.

A'=A∪{A₁₂,A₁₃}

Kokrzystając z równania prostej , ustalamy wszystkie proste dla PG(2,3), będzie ich:

G=(s³-1)/(s-1)=(3³-1)/(3-1)=13

Równanie prostej:λ₀⊗r₀⊕λ₁⊗r₁⊕λ₂⊗r₂=0

Następnie znajdujemy punkty na prostej i na tej podstawie wyznaczamy klasy.

Kartoteka wyszukiwawcza zawiera:nr grupy ,nr klasy i odpowiadające zbiory obiektów. Redundancja w tej metodzie wynosi 7.9 co oznacza ,że każdy obiekt jest podwielony w kartotece około 8 razy.

Zadanie 35

Zaproponować organizację bazy danych zgodnie z met.Ghosha dla systemu , który pamięta następujące informacje o obiektach:

Płeć={kobieta,mężczyzna}={K,M}

Wiek={młody,średni,stary}={m,śr,s}

Wykształcenie={podst,średnie,niep_wyż,wyż}

Wiadomo ,że najczęściej zadawane są do systemu pytania w postaci iloczynu dwóch deskryptorów .Wybierz właściwy wymiar geometrii (uzasadnij).Omów dokładnie sposób udzielania odpowiedzi na pytanie

q=(płeć,m)(wyksz,śr)

S=<X,A,V,q>

X={x₁,..,x_n} -zb.obiektów

A={płeć,wiek,wykształ}

V_pt={k-a,m-b}

V_wiek={m-c,śr-d,s-e}

V_wyksz={pod-f,śred-g,np-h,w-i}

Możnaby tu zastosować geometrię EG(2,3) ponieważ mamy tu trzy atrybuty.Atrybut `PŁEĆ' można rozszerzyć o jedną wartość , a atrybuty pozostałe zawężić o jedną wartość np.V_wyksz={pod,śr,wyższe}

Jednak nie znamy na tyle specyfiki systemu , aby bez ryzyka utraty informacji zlikwidować jedną wartość atrybutu.Toteż rozpatruję inne możliwości organizacji systemu:

EG(2,5)-dla syst.funkcyjnego: tu będziemy musieli dodać 2 atry. fikcyjne i uzupełnić wszystkie zb. wartości atry. do 5 wart.

lb.grup G=p²=25

lb.klas K=p²*(p nad 2)=250

lb.klas w grupie K_G=(p nad 2)=10

redundancja R=19.3

EG(2,3) -dla atrybutów binarnych:

w naszym systemime możemy wyodrębnić 9 atr. bin. A<= p²

lb.grup G=p²+p=12

lb. klas w gr. K_G=(p nad 2)=3

lb.klas K=G*K_G=36

_{redun. R=5.0}

_PG(2,3)

_{to samo co się tyczy EG(2,3) dla bina.}

_D=(p³-1)/(p-1)=13-musimy dodać atr.fikcyjne

lb.grup G=D

lb.klas w gr. K_G=(p+1 nad 2) =6

lb.klas K=G*K_G=78

_{redu. R=7.9}

Po przeprowadzonej analizie wybieram EG(2,3) dla atr. bina.,ponieważ:

-najmniejsza zajętość pamięci (która wiąże się z lb.klas ) oraz redundancja

-nie musimy dokładać żadnych atry.fikcyjnych.

Przyporządkowuję atr. bin.punkty w przestrzeni:

atr.-(r1,r2) a-(0,0) b(0,1) c(0,2) d(1,0) e(1,1) f(1,2) g(2,0) h(2,1) i(2,2)

Teraz ustalam wszystkie proste, punkty na prostych (patrz dodatek)

Sposób udzielania odpowiedzi na pytanie

q =(płeć,męższ)(wyksz,śr)=b*g

1.należy znależć współrzędne punktów odpo. deskryptorom pyt. b→(0,1)

g→(2,0)

2.współ. te wstawić odpowiednio do równania ogólnego prostej

λ₀⊗r₀⊕λ₁⊗r₁⊕λ₂⊗r₂=0

i rozwiązać powstały układ rownań

λ₀⊕λ₁⊗0⊕λ₂⊗1=0

λ₀⊕λ₁⊗2⊕λ₂⊗0=0

patrz dodatek

3.odpowiedzią jest zbiór obiektów dla klasy (0,1)*(2,0) w grupie o nr 221

Zadanie 36

Zaproponuj organizację banku danych zgodnie z met. Ghosha dla 17 atr. bin.Uzasadnij wybór geometrii .

Ponieważ atrybuty są bin. rozpatruję geom. dla atr. bin.

Atr. bin. jest 17 więc muszę znalezć taki wymiar geometrii , gdzie 17 <=lb.atr.bin. w systemie.

EG(2,5) dla atr.bin.

lb atr. bin. D=p²=25-tu trzeba by rozszerzyć ilość atr. o 8

K=(p²+p)(p nad 2)== 30*10=300

R=((2^p-p-1)/2^p)*G-1=23.4

PG(2,5)

lb.atr.bin.

D=(p³-1)/(p-1)=31=G

tu trzeba rozszerzyć ilość atr. o 14

K=(G nad 2)=465

R=((2^p+1-p-2)/(2^p+1))*G-1=26.6

PG(2,3)

lb.atr.bin. D=(p³-1)/(p-1)=13=G

tu trzeba zmniejszyć lb.atr. o 4

K=78 R=7.3

Najkorzystniejsze warunki oferuje geometria PG(2,3) jednak nie znamy na tyle specyfiki systemu by móc zmniejszyć lb.atr. o 4 bez ryzyka utraty informacji.Dlatego rezygnuję z tej geometrii.

W tej sytuacji pozostaje nam geometria EG(2,5) dla atr.bin.,która daje nam mniejszą lb.klas niż w PG(2,5), a co za tym idzie i mniejszą zajętość pamięci i mniejszą redun.

Ponad to w EG(2,5) rozszerzamy o 8 atr.bin. a w PG(2,5) o 14

W EG(2,5) dla atr.bin. mamy

-ilość grup G=30

-ilość klas w gr K_G=10

A={a₁,...a₁₇)∪{a₁₈,..,a₂₅}-zb.atr.bin

Przyporządkowuję atr.bin. punkty w przestrzeni Euklidesowej:

a1(0,0) a2(0,1) a3(0,2) a4(0,3) a5(0,4) a6(1,0) a7(1,1) a8(1,2) a9(1,3) a10(1,4) a11(2,0) a12(2,1) a13(2,2) a14(2,3) a15(2,4) a16(3,0) a17(3,1) a18(3,2) a19(3,3) a20(3,4) a21(4,0) a22(4,1) a23(4,2) a24(4,3) a25(4,4)

Teraz znajduję proste i wyznaczm numery grup , punkty na tych prostych i klasy.

patrz dodatek

Kartoteka wyszukiwawcza zawiera numery grup, numery klas i odpowiadające im zbiory obiektów.

Zadanie 37

Dane są :-zb.atrybutów Ä ={A,B,C,D,E}

-zb.wartości V_A={a1,a2,a3}

V_B={b1,b2,b3,b4} V_C={c1,c2,c3,c4}

V_D={d1,d2,d3,d4,d5} V_E={e1,e2,e3,e4,e5e,e6}

Zaproponuj odpowiednią geometrię, uzasadniającą zastosowanie met.Ghosha. Przedstaw organizację bazy danych i przeprowadż pełną analizę wyboru geom.

EG(2,5) dla sys. funkcyjnego

-aby zachować założonie ,że cardA=cardV=p(5) należy uzupełnić do 5 zbiory wartości atrybutów A,B,C i jednocześnie należy zmniejszyć zb. wartości atr. E o jedną wartość

-lb.klas w syst. K=p²*(p nad 2)=25*10=250

-redun. R=((2^p-p-1)/(2^p))*g-1=19.3

EG(2,5) dla atrybutów binarnych

-należałoby uzupełnić o 3 atr.bin. , bo tu powinno ich być 25

-lb.klas w syst. K=(p²+p)(p nad 2) =300

-redun. R=23.4

PG(2,5)

-należałoby rozszerzyć zb.atr. bin. o 9

-lb.klas w syst. K=( G nad 2)=931 nad 2)=465

-redun. R=26.6

W/g mnie najlepszą geometrią będzie EG(2,5) dla atr.bin. , ponieważ nie musimy tu obcinać żadnej wartości, a co za tym idzie nie ponosimy ryzyka utraty informacji. Redun. i zajętość pamięci jest tu mniejsza niż w PG(2,5) .W EG(2,5) dla atr.bin. będzie mniej klas pustych związanych z dodanymi atrybutami bin. niż w pozostałych geometriach.

Teraz tworzymy kartotekę wyszukiwawczą dla EG(2,5) dla atr. bin.

a1(0,0) a2(0,1) a3(0,2) b1(0,3) b2(0,4) b3(1,0) b4(1,1) c1(1,2) c21(1,3) c3(1,4) c4(2,00 d1(2,1) d2(2,2) d3(2,3) d4(2,4) d5(3,0) e1(3,1) e2(3,2) e3(3,3) e4(3,4) e5(4,0) e6(4,1) x(4,2) y(4,3) z(4,4,)

zad.38

Atrybuty A1,A2,A3,A4,A5,A6,A7, są atrybutami siedmiowartościowymi. Zaproponuj organizację bazy danych dla metody Gosh'a. podaj uzasadnienie wyboru geometrii z dokonaniem odpowiednich obliczeń.

EG(2,7) dla systemu funkcyjnego K=1029 R=44.93

PG(2,2)

Można zastosować tu taką geometrię, gdy weżmiemy pod uwagę atrybuty ale nie atrybuty binarne.Każda klasa wtedy będzie opisana przez iloczyn nie 2 atryb. bin. ,lecz przez iloczyn 2 atryb. Wtedy każdorazowo należy stosować przegląd zupełny wyszukanej klasy obiektów.

K=21

Jednak redundancja tego systemu będzie duża przy dobrych szybkościsch wyszukiwania (zwłaszcza dla pytań o długości klasy)

Jeśli nie zależy nam na niskiej redundancji (a to właśnie sobie tu zakładam),to można zastosować tu geometrię PG(2,2)

lb.atryb. A=7^p

lb. grup G=(p³-1)/(p-1)=7

lb. klas wsystemie K=(G nad 2)=21

lb. klas w grupie Kg=3

Atrybut (r0 r1 r2) A1(001) A2(010) A3(011) A4(100) A5(101) A6(110) A7(111)

(patrz dodatek)

Zad.41

Dany jest zb. obiektów opisanych przez cztery atrybuty czterowartościowe. Wybierz właściwą geometrię i zastosuj m. Gosh'a dla zorganiowania bazy danych.Wybór uzasadnij przaprowadzoną analizą. Przedstaw interpretację geometryczną wybranej geometrii.

EG(2,p) dla syst. funkcyjnego

-uzupełnić o 1 atrybut 5-wart. i pozostałe atrybuty uzupełnić po 1 wartości

EG(2,5) K=250 R=19.3

-zmniejszyć zb. wart. atryb. o 1 i usunąć 1 atrybut. Jednak nie znamy na tyle specyfiki systemu ,aby narażać się na utratę informacji (9 wartości)

EG(2,p) dla atryb. bin.

-uzupełnić o 9 atryb. bin.

EG(2,5) K=300 R=23.4

-zmniejszyć zb. atr. bin. o 7 ,ale to nie

PG(2,s)

-zmniejszyć zb. atr. bin. o 3

PG(2,3) K=78 R=7.9

-geometria rzutowa dla systemu funkcyjnego PG(2,2)

należy uzupełnić o 3 atryb. fikcyjne.

K=21

Będzie tu duża redundancja ,ale krótki czas wyszukiwania.

-PG(2,5) K=465 R=26.6

Najkorzystniejsze warunki oferuje nam geometria EG(2,5) dla systemu funkcyjnego i PG2,2) dla systemu funkcyjnego.

Ja wybieram geometrię PG(2,2) dla systemu funkcyjnego ,ponieważ jest tu mała lb. klas i krotki czas wyszukiwania .Tutaj klasy będą opisane przez atrybuty, a nie przez atr.bin.

Wyszukiwanie będzie tu polegało nz dokonaniu przeglądu zupelnego wybranej klasy.

Zad.42

Dany jest pewien podzbiór D={d1,d2,d3} zbioru książek D. Do opisu tematyki każdej z nich zastosowano następujący zbior pojęć :

A={BD,SI,OP,PR,TD,PD}

Książki ze zbioru D mają opisy:

d1:PR∩BD∩SI

d2:TD

d3:OP∩PD

A.Przedstaw kolejne kroki konstruowania bazy danych syst. informacyjnego służącego do wyszukiwania informacji o książkach ze zbioru D , wykorzystując model geometrii PG. Zał:dłu.większości pytań kierowanych do systemu jest rowna 2

B.Omów praktyczną realizację modelu bazy d. określonego w punkcie A

Zał:opis `tematyczny' książki jest niewielkim fragmentem inf. przechowywanych o książce

C.Gdzie zostaną rozmieszczone dane o książkach d1,d2,d3 ?

Tu najlepiej pasuje geometria PG(2,2) , ponieważ ma ono 7 atr.bin., a wsystemie jest ich 6 i trzeba dodać jeden atr.fikcyjny

-lb.gr. G=7

-lb.klas w syst. K=21

-lb.klas w gr. K_G=3

-redun. R=2.5

Przyporządkowujemy atr. punkty w przestrzeni rzutowej:

BD(001) SI(010) OP(011) PR(100) TD(101) PD(110) F(111) Teraz określamy równania prostych na podstawie ogólnego równania prostej λ₀⊗r₀⊕λ₁⊗r₁⊕λ₂⊗r₂=0

Na podstawie tych równań określam numery grup.Potem odnajduję punkty leżące na tych prostych .Te punkty określają nam klasy.(dod)

METODA CHOWA

zad.43

Obiekty są opisywanedeskryptorami ze zbioru D=d1...d8 , l=8 deskryptorów. Przyjmując ,że dł. opisu klasy k=3, a w grupie jest r=7 klas:

a)podać numery grup ,w ktorych znajdzie się ob. x8 opisany iloczynem deskryptorów d2*dd4*d6*d8

b)opisać dokładnie sposób udzielania odpowiedzi na pytanie q1=d5 oraz q2=d1*d3*d5*d7

c)co się zmieni w bazie danych , gdy zmieni się opis obiektu x8 w następujący sposob t_x8=d5*d2*d6*d8

D={d1,d2,d3,d4,d5,d6,d7,d8}

l=8-lb.deskryp.

k=3-dł.opisu klasy

r=7-lb.klas w grupie

K=(l nad k)-lb.klas w systemie

K=(8 nad 3)=56

g-lb.grup g=K / r =56/7=8

Wszystkie desk. syst. numerujemy cyframi od 0 do n-1 (npd1 nadajemy wart. 0, d2 -1 itd)

a) x8:d2*d4*d6*d8 { klasy mają dł k=3, więc należy podać wszystkie możliwe kom. trzech des.} - i tak t_x8=d2*d4*d6+d2*d4*d8+d2*d6*d8+d4*d6*d8

Należy obliczyć wszystkie numery klas do ktorych obiekt będzie należał

N=(n nad k)-Σ[((n-ij)/(k-j-1))-1](n-ij-1 nad k-j)-n-i_k)+1 gdzie

n-lb.desk. w sys.

k-dł.opisu klasy

ij- nr j-tego desk. w sys.

i_k-nr osttatniego des. w pytaniu

j-nr des. w pyt.

N=(8nad3)-Σ[((8-ij)/(3-j+1))-1](8-ij-1nadk-j) --(8-i3)+1

1:(d2*d4*d6) to i1=1 i2=3 i3=5

2:(d2*d4*d8) to i1=1 i2=3 i3=7

3:(d4*d6*d8) to i1=3 i2=5 i3=7

4:(d2*d6*d8) to i1=1 i2=5 i3=7

N₁=28 N₂=30 N₃=51 N₄=33

Obliczam numery grup do których będzie dopisany obiekt.

G=[N / r ]

G₁=[28/7]=4

G₂=[30/7]=[4.28]=5

G3=8 G4=5

Obiekt x8 zostanie dopisany do grupy 4 i klasy 28,grupy 5 i klasy 30 oraz do grupy 8 iklasy 51

b)q1=d5

1)pyt.należy znormalizować , czyli sprowadzić do postaci sumy termów o dł klasy -k

2)odpowiedz na term składowy pytania otrzymujemy

-obliczamy numer klasy

-znajdujemy numer grupy :

gdy c całkowite (lb.klas w gr) G=[N/c]

c ułamkowe -,gdy N<=(r-1)([c]-1) to G=[N/([c]-1)] ; gdy N>(r-1)([c]-1) to G=r

-znajdujemy pozycję klasy w grupie

c całkowite to N_KG=N-(G-1)*c

c ułam. N_KG=N-(G-1)*[c]

3)odpowiedz na pytanie stanowi suma obiektów będących odpowiedzią na termy składowe pytania q2=d1*d3*d5*d7

1)ponieważ pytanie jest dłuższe niż dł. opisu klasy obcinamy pytanie do dł.klasy

2)dla tak powstałego termu znajdujemy odpowiedz przybliżoną , a odpo. dokl. uzyskujemy dokonując przeglądu zupełnego odpowiedzi przybliżonej

c)t_x8=d5*d2*d6*d8

tworzymy wszystkie trójki:

tx8=d2*d5*d6+d2*d6*d8+d2*d5*d8+d5*d6*d

poprzdni opis

tx8=d2*d4*d6*d8

tx8=d2*d4*d6+d2*d4*d8+d2*d6*d8+d4*d6*d8

Obiekt x8 pozostanie wpisany w klasie o opisie d2*d6*d8

Natomoast zostanie usunięty z klas:

d2*d4*d6 d2*d4*d8 d4*d6*d8

i dopisany do klas d2*d5*d6 d2*d5*d8 d5*d6*d8

zad.44

Podaj możliwość zastosowania dla zb. obiektów metody Chowa.

x1=f*b*g

x2=d*g*a*e*f

x3=c

x4=c*a*b

x5=f*g*a*b*d

x6=b*c

x7=e*g*d

x8=a*g*e

Zaproponuj organizację bazy danych w tej metodzie i przedstaw sposób wyszukiwania odpowiedzi na pyt. t=a*d*b*f+g*b

Zastosuję m.Chowa o dł klas k=3

D={a,b,c,d,e,f,g} n=7-lb.des.

Desk. numerujemy od 0 do n-1

Liczę liczbę klas : K=(n nad k) =(7nad3)=35

Zakładam lb.grup r=7

Wyliczam lb.klas w grupie c=k / r=35/7=5

Tworzę klasy:

G1={abc,abd,abe,abf,abg}

G2={acd,ace,acf,acg,ade}

G3={adf,adg,aef,aeg,afg}

G4={bcd,bce,bcf,bcg,bde}

G5={bdf,bdg,bef,beg,bfg}

G6={cde, cdf,cdg,cef,ceg}

G7={dfg,def,deg,dfg,efg}

nr Grupy

iden. klas

obiekty

opis klas

012

013

014

015

016

x4 x3 x6

abc

abd

abe

abf

abg

023

024

025

026

034

acd

ace

acf

acg

ade

035

036

045

046

056

adf

adg

aef

aeg

afg

123

124

125

126

134

x3 x6

bcd

bce

bcf

bcg

bde

135

136

145

146

156

bdf

bdg

bef

beg

bfg

234

235

236

245

246

cde

cdf

cdg

ceg

256

345

346

356

456

x2 x7

cfg

def

deg

dfg

efg

Kartoteka wysz. będzie zawierać : nr grupy , nr klasy, odpowiadające klasom zb. obie.

Już na pierwszy rzut oka widać tu dość dużą redun.Jest ona wynikiem między innymi tego ,że opisy obiektów są o różnej dł.

W tym wypadku nie ma klas pustych z założenia, i mało jest klas pustych z powodu braku obiektów o takich opisach.

Myślę ,że ta metoda nie jest najlepszą do podanego zestawu obiektów, ze względu na to ,że prawie każdy obiekt znajduje się w wielu klasach(redun).

Wyzsukiwanie odpowiedzi na pyt. t=a*d*b*f+g*b

Na początku w pyt. należy uporządkować desk. t=a*b*d*f+b*g

Pyt. t składa się z dwóch pyt. skła. t1=a*b*d*f t2=b*g

Ponieważ term skła. t1 jest dłuższy niż dł. opisu klasy obcinamy ten term do dł opisu klas t1'=a*b*d

Teraz znajdujemy odpowiedz przybliżoną.

obliczamy numer klasy dla t1' N=wz1

i1=0 i2=1 i3=3

Obliczam numer grupy w której znajduje się ta klasa.Ponieważ c jest cał.,to G=[N/c]=[2/5]=[0.4]=1

Odpowiedzią przybliżoną stanowią obiekty należące do klasy N=2 należącej do grupy G=1

Są to obiekty δ=(t1')={x5}

Odp. dokł. otrzym. przez dokonanie przeglądu zupełnego odpo. przybliżonej.

Obiekt x5 zawiera w swoim opisie des. f , więc stanowi on odp. dokładną.

t2=b*g

Ponieważ term składowy t2 jest krótszy od dł. opisu klasy , to term ten normalizujemy.

t2'=abg+bcg+bdg+beg+bfg

t2'=t1''+t2''+t3''+t4''+t5''

Teraz odpowiedz na każdy term ti'' uzyskujemy jako zbiór obiektów klasy Kn tak jak w poprzednim przypadku.

METODA LUMA

ZAD.45

Dany jestsys. infor. z nastepującymi opisami obiektów:

tx1=a1b2c3d4e5f4 tx6=a2b1c2d2e5f2

tx2=a1b2c3d1e5f4 tx7=a3b1c1d2e5f2

tx3=a2b2c3d1e5f4 tx8=a1b1c3d2e5f4

tx4=a2b2c2d1e5f4 tx9=a3b1c1d2e5f4

tx5=a3b2c1d1e5f4 tx10=a2b1c2d2e5f2

gdzie ai oznacza des. wyznaczony przez i-tą wartość atr. a.

Zaproponuj zastosowanie do tego systemu m.Luma z podbankami.Podaj liczbę koniecznych podbanków. Przeanalizuj `opłacalność' zastosowania rozwiązania.

S=<X,A,V,ρ>

X={x1,..,x10}

A={A,B,C,D,E,F}

V_A={a1,a2,a3}

VB={b1,b2}

VC={c1,c2,c3}

VD={d1,d2,d4}

VE={e5}

VF={f2,f4}

Możemy usunąć z naszego sys. atr. E ponieważ wszystkie obiekty systemu są opisane jedaną wartością {e5} tego atrybutu.Wszystkie obiekty są nierozróżnialne w sys. ze względu na atrybut E.

Atr.w sys. są uporządkowane i ponumerowane od 1 do n.Zostają też uporządkowane i ponumerowane wartości w obrębie każdego atrybutu.

Opis grupy jest iloczynem des. z każdego atr. sys.

Stosuję m.Luma z podbankami.

Wszystkie grupy odpowiadające jednej permutacjii atr. sys. będziemy nazywać podbankami.

Konieczna lb.podbanków zapewniająca zasadę spójności.

L=(n nad s ) gdzie s=[n/2] , n-lb.atr. w sys.

n=5 s=[n/2]=[5/2]=2

L=(5 nad 2)=10

Podbanków będzie 10.

Są dwie metody uzyskiwania właściwej lb.podbanków :

1)m.kombinatoryszna-wszystkie permutacje dla atr. i wykreślamy powtarzające się permutacje

2)m.ścieżki krytycznej-każdemu atr. przypo. jest odcinek jednostkowy, który umieszczamy na płaszczyżnie

Otrzymujemy albo odcinki wznoszące się albo opadające .Wprowadzamy trzy taśmy:

R-odcinki opadające

S-odcinki rosnące

T-ostatni odcinek rosnący przed opadającym

Podbanki charakteryzują się inną kolejnością atr.Tworzy się je aby skrocić czas odp. na pyt.ogolne. Wykorzystuje się tu zasadę spójności (obszary spójne) Aby zachować tą zasadę należy zapamiętać grupy o opisach będących odpowiedniednikiem innego ciągu atr. (chodzi tu o kolejność atr. w opisie grupy).Każdy podbank ma identyczną lb.grup (taką samą jak w m.klasycznej)

Pojawienie się podbanków wprowadza redun.,ponieważ każdy opis obiektu musi być pamiętany w każdym podbanku R=(l-1) l-lb.podban.

Wraz ze wzrostem lb.atrybutow w sys. wzrasta lb.podbanków . Przy zbyt dużej lb.atry. warto się zastanowić nad możliwością zastosowania modyfikacji z częściowymi podbankami.Tutaj lb.podbanków nie jest jeszcze zbyt wysoka i jest ona opłacalna.

Zad. 46

Dany jest system o podanym niżej zbiorze obiektów;

tx1=a1*b1*c1*d1*e1 tx6=a2*b1*c2*d1*e1

tx2=a1*b1*c1*d1*e1 tx7=a2*b1*c3*d1*e1

tx3=a1*b1*c2*d1*e1 tx8=a2*b2*c3*d3*e1

tx4=a1*b1*c3*d1*e1 tx9=a3*b3*c2*d2*e1

tx5=a1*b1*c1*d1*e1 tx10=a3*b3*c2*d2*e1

Zaproponuj organizację bazy danych dla w/w systemu stosując m. Luma z podbankami. Dla organizacji podbanków zastosuj metodę graficzną.

S=<X,A,V,q> X={x1,...,x10} A={A,B,C,D,E}

V_A={a1,a2,a3}

V_B={b1,b2,b3}

V_C={c1,c2,c3}

V_D={d1,d2,d3}

V_E={e1}

Z systemu możemy usunąć atr. E ponieważ wszystkie obiekty są nierozróżnialne w sys. ze względu na ten atr.

Ponadto zaobserwowałem zależności:

b1→d1 i d1-b1

b2→d3 i d2-b3

b3-d2 i d3-b2

b' x1 x8 x9 d' x1 x9 x8

x1 x10 x2 x10

x3 x3

x4 x4

x5 x5

x6 x6

x7 x7

Z tego wynika ,że atr. b i d są sobie równoważne. W związku z tym w naszych rozważaniach mogę pominąć jeden z tych atr.Wybieram atr. d .

Po powyższych operacjach mamy:

A'={A,B,C} i V_A={a1,a2,a3} V_B=b1,b2,b3} V_C={c1,c2,c3}

W tej sytuacji najmniejsz lb. podbanków , która zapewnia zasadę spójności wynosi:

L(n nad s)=(3nad1)=3

DODATEK

zad.47

Dla podanego zbioru obiektów zaproponuj organizację bazy danych stosując m.Luma z podbankami. Przeanalizuj sensowność stosowania takiej organizacji:

tx1=a1b1c1d1e1f1 tx2=a1b1c1d1e1f2

tx3=a1b1c2d1e1f3 tx4=a1b1c3d1e1f1

tx5=a1b1c1d1e1f3 tx6=a2b1c2d1e1f2

tx7=a2b1c3d1e1f3 tx8=a2b2c3d3e1f3

tx9=a3b3c2d2e1f2 tx10=a3b3c2d2e1f2

S=<X,A,V,ρ>

X={x1,..x10} A={A,B,C,D,E,F}

VA={a1,a2,a3} VB={b1,b2,b3}

VC={c1,c2,c3} VD={d1,d2,d3}

VE={e1} VF={f1,f2,f3}

Usuwam z sys. atr. E, ponieważ wszystkie obiekty są nierozróżnialne w sys. ze względu na ten atr.

ponadto zauważyłem ,że atr. B i D są równoważne w sys. b1-d1 i d1-b1

b2-d3 d2-b3

b3-d2 d3-b2

Mogę, więc usunąć z naszych rozważań jeden z tych atry.Wybieram atr, D .

W związku z tym otrzymujemy następujący zb.atr.: A={A,B,C,F}

Wyliczam najmniejszą lb podbanków, która zapewnia zasadę spójności:

n=4 s=[n/2]=2 L(n nad s)=6

Będę tworzyć podbanki metodą ścieżki krytycznej.(rysunki)

Spisujemy kolejno z taśm podbanki:

1.ABCF 4.CFAB

2.FABC 5.BCFA

3.CAFB 6.BFAC

Kiedy podbank ma iedentyczną lb.grup jak w m.klasycznej , czyli : L_G=m1m2*..*m3, gdzie mi=cardV_Ai

m1=3 m2=3 m3=3 m4=3

L_G=3*3*3*3=81

Jednak w każdym podbanku jest inna kolejność atr. Pozwala towykorzystać zasadę spójności do udzielania odpowiedzi na pyt. ogólne (nie będące termami elementarnymi)

Pojawienie się podbanków wprowadza redun.,ponieważ każdy obiekt musi być pamiętany w każdym podbanku.

R=(l-1)=6-1=5

Tu redun. nie jest jeszcze zbyt , ale wraz ze wzrostem lb.atr. wzrasta lb.podbanków a co za tym idzie wzrasta redun.

Kiedy lb,atr. sys. jest b.duża warto się zastanowić nad możliwością zastosowania modyfikacji z częściowymi podbankamim.

Zad.48

Dla systemu:

obiekty x1,x2,...,x25 opisane różnymi deskrypt. atrybutów a2,a3,a5,a6,a8

obiekty x26,x27,...,x50 opisane różnymi deskryp. atrybutów a1,a4,a7,a9,a10

Zaproponować organizację bazy danych zgodnie z m. Luma.Przedstaw szczegółowo znajdowanie odpowiedzi na pytania będące iloczynem wartości następujących atrybutów.

a1^a2^a3 a4^a7^a10

Skoro obiekty są podzielone na 2 grupy i każda z tych grup jest opisana innymi atrybutami ,to tworzę dwie kartoteki m. Luma.

W pierwszej grupie będą obiekty opisane następującymi atrybutami: a2,a3,a5,a6

W drugiej grupie będą obiekty opisane takimi atrybutami: a1,a4,a7,a9,a10

Ponieważ nie znam zbiorów wartości tych atrybutów nie jestem w stanie określić ilości grup w każdej z tych kartotek.

Proces tworzenia kartoteki przebiega w następujący sposób:

1. Opis grup jest iloczynem deskryptorów z każdego atrybutu systemu (tu podsystem).

2. Atrybuty muszą być uporządkowane od 1 do n (to samo dotyczy wart. atrybutów).

3. NR. GR. Opis grupy

Zmieniają się wartości ostatniego atryb. potem przedostatniego itd. ,aż do ostatniej grupy.

Odp. na pyt: a1^a2^a3

Po wstępnej analizie systemu wiemy ,że nie występuje obiekt ,który miałby w swoim opisie wartości atrybutów a1,a2 i a3 jednocześnie.

Dlatego odpowiedzią na to pytanie będzie zb. pusty.

Pyt. a4^a7^a10 (dokończyć)

-atrybuty pytania należą do zb. atrybutów drugiej kartoteki

-pytanie to należy znormalizować przez sprowadzenie pytania do sumy termów elementarnych

-odp. na pyt. składowe jest zb. obiektów grupy Gi i=(j₁-1)*m₂*m₃*...*m_n+(j₂-1)*m₃*...*m_n+...+(j_n-1-1)*m_n +(jn-1)+N

gdzie: j_k- j-ta wartość k-tego atrybutu występującego w pytaniu

m_k- card Vak

N - adres pierwszej grupy

Zad.49

Dany jest system informacyjny S o zbiorze atrybutów A={a,b,c,d,e,f} ,gdzie każdemu z nich można przyporządkować trójelementowy zbiór wartości. System S zorganizowano w oparciu o m. Luma (z tzw. podbankami).

Po wstępnej eksploatacji systemu określono tzw. `'współczynniki współwystępowania atrybutów w pytaniach'' ,zawarte w poniższej tabeli T:

a b c d e f

a - 0.58 0.03 0.61 0.64 0.02

b 1 - 0.02 0.63 0.61 0.01

c 0.02 0.04 - 0.60 0.59

d 1 0.58 - 0.59 0.04

e 0.65 0.32 0.29 0.30 - 0.31

f 0.04 0.01 0.65 0.02 0.63 -

t(i,j) ,gdzie i,j nal. do A ,można interpretować jako prawdopodobieństwo występowania w pytaniu wartości atrybutu j ,jeżeli pojawiła się w nim wartość atrybutu i.

Podaj możliwości wykorzystania przez projektanta systemu danych zawartych w tablicy T oraz omów wszelkie konsekwencje płynące z reorganizacji systemu.

System S zorganizowany w oparciu o m. Luma z podbankami.

A={a,b,c,d,e,f} n=6 S=[6/2]=3 L=(n nad 3)=(6 nad 3)=20

Podbanki będę generować m. ścieżki krytycznej (teraz wykresy)

1 ABCDEF Na podstawie tabeli określającej

2 FABCDE współczynniki współwystępow.

3 EFABCD atrybutów wpytaniach mogę

4 DEFABC wyeliminować te podbanki w

5 CDAEFB których na pierwszych 3 pozyc.

6 BDFACE są atrybuty najrzadziej występ.

7 EABCFD w pytaniach wskazanych

8 DEABFC przez S. Zostało 16 podbanków.

9 DABEFC Teraz uporządkowujemy podb.

10 DFABCE w/g malejących współcz.

11 CDFABE współwyst. atrybutów w

12 CADEFB pyt.Można tu jeszcze upo-

13 CFADBE rządkować podbanki od

14 CEFABD najwięk. współcz. do najm.

15 CEABDF Wpływa to na szybkość

16 BCDEFA wyszukiwania (skraca czas

17 BFCDAE wysz.) Usunięcie podbanków o

18 BEFCAD najmniejszej współwystępowal.

19 BECFAD zmniejsza redundan. i zajętość

20 BDEFAC pamięci.

M. SKŁADOWYCH ATOMOWYCH

z dekompozycjami

ZAD.50

Dany jest sys.inf. S zorganizowany zgodnie z MSA ,przy czym:S=<X,A,V,q>

X={Ania,Basia,Iwonka,Jasiu,Magda,Marek,

Olek,Radek}

A={P,W,B}-{Płeć,Wiek,ulub.Bohater film.}

V=V_p∪V_w∪V_B

Vp={dz,ch}Vw={3,4} VB={Bolek,Lolek,Maja}

Natomiast f-kcja informacji o obiekcie x∈X w S mają postać:

	P	W	B
Basia	dz	3	Maja
Radek	ch	4	Maja
Ania	dz	3	Maja
Iwonka	dz	3	Maja
Jasiu	ch	3	Maja
Olek	ch	4	Maja
Magda	dz	4	Maja
Marek	ch	3	Maja

A)Czy sys. S jest selektywny?

B)Czy sys. jest kompletny?

C)Czy sys.S cechuje redun.?

Odpowiedzi należy uzasadnić.

D)Przedstaw alternatywne sposoby organizacji b.d. dla sys. S oraz porównaj je.

System jest selektywny ,wtedy i tylko wtedy ,kiedy każda SA zawiera 1 obiekt lub 0 obiektów. Tutaj term elem. (P,dz)(W,3)(B,Maja) zawiera 3 obiekty, więc sys. nie jest selektywny.

System jest kompletny ,kiedy każda SA jest różna od zera. Tutaj sys,nie jest kompletny , ponieważ są termy elem.,które są puste-nie odpowiadają im żadne zbiory obiektów,np

(P,dz)(W,3)(B,Bolek)

(P,dz)(W,3)(B,Bolek)itd

Nie występuje tu redun.,każdy obiekt występuje tylko raz w kartotece wyszuki.

Usuwamy z sys.atr. B poniważ wszystkie obiekty są nierozróżnialne w sys.ze względu na ten atr.

A={P,W} Vp={dz,ch} Vw={3,4}

cardVp=2 cardVw=2

L_SA=2*2=4

Zmniejszamy zajętość pamięci,gdyż nie pamiętamy całych opisów obiektów ale tylko identyfikatory i składowe atomowe.

ten system jest już kompletny ,ale nie jest selektywny.

SA	obiekty
00	{Basia,Ania, Iwonka}
01	{Magda}
10	{Jasiu,Marek}
11	{Radek,Olek}

Zad.51

tx1=a1,b2,c3,d8,e1,f1 tx6=a4,b5,c4,d6,e1,f3

tx2=a2,b1,c4,d5,e1,f1 tx7=a1,b2,c5,d8,e1,f1

tx3=a2,b7,c4,d4,e1,f4 tx8=a3,b7,c5,d4,e1,f1

tx4=a3,b7,c4,d4,e1,f4 tx9=a2,b7,c5,d4,e1,f3

tx5=a5,b2,c4,d8,e1,f5 tx10=a1,b2,c5,d8,e1,f3

Zaproponuj organizację bazy danych dla powyższego systemu opartą na MSA z dekompozycją atrybutową zależną (hierarchiczną). Podaj pełną definicję zorganizowanego systemu.

Usuwam atrybut E, bo obiekty są nierozróżnialne ze względu na ten atrybut. Wyznaczam klasy równoważności ,aby móc zaobserwować zależność atrybutów.

a~ b~

x1 x2 x4 x6 x5 x2 x1 x6 x3

x7 x3 x8 x5 x4

x10x9 x7 x8

x10 x9

c~ d~

x1 x2 x7 x3 x2 x6 x1

x3 x8 x4 x5

x4 x9 x8 x7

x5 x10 x9 x10

x1 x6 x5 x3

x2 x9 x4

x7 x10

b--->d<=>b~⊂d~ ∧ d--->b<=>d~⊂b~ ⇒ b≡d

(nad literami przy grupach x-ów należy stawiać znaczek: ~)

ab (tu znaczek itd.) ac

x1 x2 x3 x4 x5 x6 x1 x2 x4 x5 x6 x7 x9

x7 x9 x8 x3 x10

x10

x1 x2 x3 x4 x6 x5

x7 x9 x8

x10

x1 x2 x3 x4 x5 x6 x8 x9 x10

ab≡ad z tego wynika, że b≡d

x1 x2 x3 x5 x6 x7 x8

x4 x10 x9

x1 x2 x3 x5 x6 x8 x9 x10

x7 x4

x1 x2 x3 x5 x6 x7 x8

x4 x10 x9

x1 x2 x3 x5 x6 x7 x9

x4 x8 x10

abc

x1 x2 x3 x4 x5 x6 x7 x8 x9

x10

abf

x1 x2 x3 x4 x5 x6 x8 x9 x10

b--->d d--->b ab--->d af--->d af--->d--->b

b-atrybut najbardziej zależny

Narysować drzewko: od S wychodzą : S1 S2 S3 S4 ,od S1 : S11 S12 S13 S14 ,od S11 : S111 S112 ... S119 od S4 : S41 S42 S43 S44

zad.55

Wiedząc,że A={A,B,C,D,E,F} i V_A={a1,a2,a3} i V_B={b1,b2,b3} , V_C={c1,c2,c3} V_D={d1,d2,d3} V_E={e1,e2,e3} V_F={f1,f2,f3}. Zaproponować sposób dekompozycji sysytemu zawierającego 10 następujących obiektów:

tx1=a1b1c1d1e1f1 tx6=a2b1c2d1e1f2

tx2=a1b1c1d1e1f2 tx7=a2b1c3d1e1f3

tx3=a1b1c2d1e1f3 tx8=a2b2c3d3e1f3

tx4=a1b1c3d1e1f1 tx9=a2b3c2d2e1f2

tx5=a1b1c1d1e1f3 tx10=a2b3c2d2e1f2

Opisać szegółowo wyszukiwanie odp. na pyt.:

1)P1=a1*b1*c1 4)P4=c2*e1

2)P2=a1 5)P5=(-c)*(-a)

3)P3=b1*d1*e1

Pierwszą moją obserwacją jest to ,że wszystkie obiekty są opisane jedną wartością atrybutu E,jest to wartość e1.W związku z tym , że obiekty są nierozróżnialne w sys. ze względu na atrybut E,więc mogę go usunąć z sys. bez straty informacji o obiektach.

Przeprowadzam analizę zależności atrybutów w sys.:

A~	B~	C~	D~	F~
x1x6	x1x8x9	x1x3x4	x1x9x8	x1x2x3
x2x7	x1 x10	x2x6x7	x1 x10	x4x6x5
x3x8	x3	x5x9x8	x3	x9x7
x4x9	x4	x10	x4	x10 x6
x5x10	x5		x5
	x6		x6
	x7		x7

b-->d i d-->b⇒b≡d

Ponieważ zbiór obiektów nie jest duży nie możemy tu zastosować dekompozycji obiektowej .Nie możemy tu też zastosować dekompozycji atr. poniewż jest zbyt mała liczba atr.Ponieważ istnieją tu dwa atr. zależne zastosuję dekompozycję hierarchiczną:

S={X,A∪B₁,V,ρ}

A={A,C,F}-zb.atr.niezależ.

B₁={B,D} V-zb.wartości atr.zależ.

ρ:X*A∪B --->V

RYSUNEK!!!

Od S : wychodzą S1 S2 S3

S1=<X,A∪B₂,V1,q> s2,s3 taki sam opis

B₂={B}

Odpowiedzi na pyt.

1)P=a1*b1*c1

-ponieważ pyt.nie zawiera desk. z atr. D, który był atr. najbardziej zależnym i w/b którego została dokonana dekompozycja pytanie tp kierujemy do wsztstkich podsystemów,

-w podsystemie znajdowana jest odpowiedz zgodnie z zastosowaną metodą wyszukiwania,

-sys.główny daje odpowiedz jako sumę odpowiedzi ze wszystkich podsystemów

δ(R)=δ₁(P)∪δ₂(P)∪δ₃(P)

2)P=a1 4)P=c2*e1 -- to samo co w przypadku 1) + do 4) ponieważ wszystkie obiekty są opisane deskryptorem e1 , więc udzielenie odp. będzie się ograniczało do podania zb.obiektów,którre w swoim opisie zawierają des. c1

3)P=b1*d1*e1

-ponieważ wszystkie obiekty zawierają w swoim opisie des. e1,więc możemy go pominąć w naszych rozważaniach, a więc obcinamy pyt. do postaci P'=b1*d1

-pyt.dotyczy tylko podsystemu dla d1

-w tym podsystemie znajdujemy odp.na pyt.P'=b1 zgodnie z zsatosowaną metodą wyszukiwania

5)P(-c)*(-a)

-doprowadzamy pyt. do postaci nie zawierającej des. zaprzeczonych P=(c2+c3)*(a2)=a2*c2+a2*c3

-dalej to co w przypadku 1)

zad.56

Na zaproponowanym przez ciebie przykładzie sys.inf, omów:

a)sposób organizacji b.d. dla MSA,

b)sposób wyszukiwania odp. na różne typy pyt. Jaki jest związek pomiędzy postacią pytania,a czasem wyszukiwania odp.na pyt dla MSA?

S={X,A,V,q}

X={x1,...,x5}

A={A,B,C,D} VA={a1,a2,a3} VB={b1,b2} VC={c1,c2,c3} VD={d1,d2,d3,d4}

q:X*A-->V- f-kcja inf. (można ją zapisać w postaci tab.)

	A	B	C	D
x1	a3	b1	c3	d4
x2	a2	b2	c2	d2
x3	a2	b2	c3	d3
x4	a3	b1	c3	d4
x5	a1	b2	c3	d1

a) Założenia do sys. zorganizowanego zgodnie z MSA:

₁)dla każdego t1,t2 należących do T_r δ(t1)∩δ(t2)=∅

₂)∪t_i należących do T_e_δ₍t_i)=X

Obliczam liczbę składowych atomowych:

1)numerujemy wartości atr., kolejność str. jest ustalona,

2)L_SA=m1*m1*...*m_n m_i=cardV_Ai

L_SA=3*2*3*4=72

Opisy skladowych atomowych stanowią iloczyny wartości z każdego atr.

Tworzymy identyfikatory SA, które są ciągami b1,b2,..,bn gdzie b_j odpowiada liczbie określającej numer wartości j-tego atr.

0000	0100	1000	1100	2000
0001	0101	1001	1101	2001
0002	0102	1002	1102	2002
0003	0103	1003	1103	2003
0010	0110	1010	1110	2010
0011	0111	1011	1111	2011
0012	0112	1012	1112	itd
0013	0113	1013	1113
0020	0120	1020	1120
0021	0121	1021	1121
0022	0122	1022	1122
0023	0123	1023	1123

Można zamiast identyfikatora zastosować numer SA

Σbi*Ui gdzie Ui=m2*m3*..*mn

Un-1=mn

Un=1

np 1023 Σb_i*Ui=1*24+0*12+2*4+3*1=35

W kartotece pamiętamy SA i odpowiadające im zbiory obiektów.Pamiętamy tylko niepuste składowe atomowe.

identyfikator	nr SA	zb.obi.
0123	23	x5
1111	41	x2
1122	46	x3
2023	59	x1,x4

0*24+1*12+2*4+3*1=23

1*24+1*12+1*4+1*1=41

1*24+1*12+2*4+2*1=46

2*24+0*12+2*4+3*1=59

b)Proces wyszukiwania odpowiedzi na pyt.

1)pyt w postaci sumy termów elem. t=t1+t2+..+tn

to odpowiedz δ(t)=δ(t1)∪δ(t2)∪....∪δ(tn)

ti należy do T_E

-pyt. przekształcamy do postaci identyfikatora

t_i ⇒ b1..bn -przeszukujemy kartotekę ,aby znależć identyfikator i odpowiadające mu zbiory obiektów

-identyfikator można przekształcić do postaci numeru

2)Jeśli termy pyt. nie są termami elem. to należy je przeanalizować.Dalej wyszukiwanie przebiega jak w 1)

Jednak czas wtszukiwania jest tu wydłużony o proces normalizacji.

W MSA preferowane są pyt. szczegółowe,o skł atomową, czyli pyt. oterm elem.

zad.57

Dla sys. S o wybranym zbiorze obiektów opisanych:

tx1=a1b1c1d1e1f1 tx6=a2b1c2d1e1f2

tx2=a1b1c1d1e1f2 tx7=a2b1c3d1e1f3

tx3=a1b1c2d1e1f3 tx8=a2b2c3d3e1f3

tx4=a1b1c3d1e1f1 tx9=a3b3c2d2e1f2

tx5=a1b1c1d1e1f3 tx10=a3b3c2d2e1f2 Wymień kolejne czynności, które muszą być wykonane dla stworzenia kartoteki wyszukiwawczej w MSA.Określ możliwe parametry tej metody.Dal jakiego typu pyt.czasy wyszukiwania będą najkrótsze w zaproponowanej organizacji kar.wyszu.?

W rozważaniach nad sys. mmogę pominąć atr.E ,ponieważ wszystkie obiekty w bazie są nierozróżnialne ze względu na ten atr.

S=<X,A,V,q> X={x1,..,x10} A={A,B,C,D,E}

VA={a1,a2,a3} VB={b1,b2,b3} VC={c1,c2,c3}

VD={d1,d2,d3} VF{f1,f2,f3}

q:X*A-->V

1)Określam lb. SA w sys.

mi=cardV_Ai

L_SA=m1*m2*m3*m4*m5=3*3*3*3*3=243

SA będzie b.dużo,ich liczba przewyższa znaczenie lb.obiektów, wobec tego będzie duża lb.SA pustych.

2)Opisy SA stanowią iloczyn wartości z każdego atr.Dla podania niepustych SA wykorzystam tu uporządkowanie leksykograficzne opisów SA i przyjmujemy wartości atr. od 0 do n-1

3)Każdemu opisowi będzie odpowiadał ciąg liczb b1,b1,...,bn , gdzie b_j odpowiada lb.określającej nr wartości j-tego atr.

b1b2b3b4b5 nr SA

00000 0

00001 1

00002 2

00102 11

00200 18

10101 91

10202 101

11222 134

22111 229

4)Dla stworzenia dogodnej kart.wysz. wprowadzamy numerację SA

W celu pamiętania tylko niepustych SA stosujemy tu modyfikację z tablicą adresową, która ma postać:

nr SA zb.obiektów

0 x1

1 x2

2 x5

11 x3

18 x4

91 x6

101 x7

134 x8

229 x9,x10

Baza danych jest tutaj tylko powiększona o tab.adresową,ale struktura jest prosta.

Brak redun. i mniejsza zajętość pamięci niż w m.klasycznej bez tab.adr.

Jest to m.mniej czsochłonna niż m.klasyczna,która jest czsochłonna.

Najkrótsze czsy wyszukiwania w tak zorganizowanym sys. osiąga się dla pytań będących termami elel.

Zad.59

Definicja formalna sys.

S=<X,A,V,q>

A={A,B,C,D,E,F}

VA={a1,a2,a3} cardVA=3

VB={b1,b2} cardVB=2

VC={c1,c2,c3} cardVC=3

VD={d1,d2} cardVD=2

VE={e5}

VF={f2,f4} cardVF=2

Określona jest funkcja informacji q:X*A-->V

Ze zbioru atr. odrzucamy atr. E,dla którego wsztstkie obiekty są opisane wartością e5, czyli są one nierozróżnialne w sys. ze względu na ten atr.

Ogólna liczba składowych atom.jest liczona ze wzoru: L_SA=m1*m2*...*m5

m1=cardVA

m2=cardVB itd.

L_SA=3*2*3*2*2=72

L_SA'puste'=72-9=63

Są 63 klasy puste;( jest to lb.skł.atom…pełnych.

W kartotece jest 10 obiektów ,wszystkie są opisane różnymi termami elem.,tylko obiekty x8 i x10 są opisane takim samym termem elem.,więc należą do jednej skł.atom…

Sposób szukania odpowiedzi na pyt. a3*b1*f2 -wszystkie wartości w obrębie każdego atr. numerujemy od 0 do n

-nasze pyt.nie jest w postaci termu elem.,więc musimy je znormalizować, czyli sprowadzić do postaci sumy termów elem.

P=a3*b1*[(c1+c2+c3)*(d1+d2)]*f2=

a3*b1*[c1*d1+c1*d2+c2*d1+c2*d2+c3*d1+c3*d2]*f2=a3*b1*c1*d1*f2+a3*b1*c1*d2*f2+a3*b1*c2*d1*f2+a3*b1*c2*d2*f2+a3*b1*c3*d1*f2+a3*b1*c3*d2*f2

Teraz każdy z termów ele. pyt. zostaje przekształcony do postaci identyf. b1..bn

1)20001

2)20011

3)20101

4)20111

5)20201

6)20211

Odpowiedzią jest suma obiektów odpowi. powy ższym identyfikatorom.

Kompozycje

zad.60

Dane są dwa sys.inf. S₁ ,S₂ zorganizuj zgodnie z MSA .

	A1	A2	A3	A4
X1	V11	V21	V31	V41
X2	V12	V22	V31	V42
X3	V11	V23	V32	V42
X4	V12	V21	V32	V42

	A1	A2	A3	A4
X5	V11	V21	V31	V41
X6	V13	V23	V31	V42
X7	V13	V23	V31	V42

Niech S jest złożeniem obiektowym S1 i S2.

1)Podać dla sys. S zbiór obiektów X,Zb.atr.A, zbiory wartości atr. V_ai

2)Sprowadzić do postaci standardowj w S term q=(A1,V13)∩(A2,V23)

i podać zbiory obiektów ,które są odpowiedzią na q w S1,S2 i S.

1)S=S1+S2 S=<X,A,V,q>

X={x1,x2,x3,x4,x5x,6,x7}

Ponieważ zb.wartości atr. A1 nie są identyczne w obu podsystemach ,musi zachodzić warunek ,że wartości w obrębie atr. nie będą się wykluczać.

VA1={V11,V12,V13} VA2={V21,V22,V23} VA3={V31,V32} VA4={V41,V42}

2)q=(A1,V13)∧(A2,V28)∧((A3,V31)∨(A3,V32))∧((A4,V41)∨(A4,V42))=(A1.V13)∧

(A2,V23)∧(A3,V31)∧(A4,V41)∨(A1,V13)∧(A2,V23)∧(A3,V31)∧(A4,V41)∨(A1,V13)∧(A2,V23)∧(A3,V32)∧(A4,V41)∨(A1,V13)∧(A2,V23)∧(A3,V32)∧(A4,V42)

δ(q)_S1 {zb.pusty} δ(q)_S2{x6,x7}

δ(q)_S{x6,x7}

Strona A

1. Act Of Love

2. Brother

3. Dead Man

4. Footsteps

5. Gremmine Out Of Control

6. Hard To Imagine

7. My Genaration

8. Naked Eye

9. Seenface

10. Suggestion & Teen Spirit

11. Sympathy

12. Three Little Birds

13. Trouble

14. Words Out Of Place

15. Xmas Time

16. By Your Side

17. Don't Need

18. Dirty Frank

Strona B

1. Going Down

2. Hold Your Head Up

3. Just A Girl

4. Master Of War

5. Myster

6. Patriots

7. Happy When I'm. Crying

8. History Never Repeats

9. My Way

10. Olimpic Platinum

11. Sonic Reducer

12. Swallow My Pride

Wyszukiwarka

	A1	A2	A3	A4
X1	V11	V21	V31	V41
X2	V12	V22	V31	V42
X3	V11	V23	V32	V42
X4	V12	V21	V32	V42

	A1	A2	A3	A4
X1	V11	V21	V31	V41
X2	V12	V22	V31	V42
X3	V11	V23	V32	V42
X4	V12	V21	V32	V42

	A1	A2	A3	A4
X1	V11	V21	V31	V41
X2	V12	V22	V31	V42
X3	V11	V23	V32	V42
X4	V12	V21	V32	V42