4736387436

4. Badanie odwracalności

Dane : schemat relacji: R(Ai,...,A_n); zbiór zależności funkcyjnych F; rozkład p(R|,...,R_k)

Wynik : stwierdzenie, czy p jest rozkładem odwracalnym.

Metoda :

1°) Konstruujemy tablicę on - kolumnach i k - wierszach; j - ta kolumna odpowiada atrybutowi A;, a i-ty wiersz odpowiada schematowi relacji Rj. Jeśli A, jest atrybutem R; to na przecięciu i-tego wiersza i j-tej kolumny wstawiamy symbol aj. Jeżeli nie wstawiamy tam b,y. Każdą z zależności X—»Y ze zbioru F "rozważamy wielokrotnie” - dopóki w tablicy nie można dokonać żadnej zmiany.

2°) Za każdym razem, gdy rozważamy X—>Y szukamy wierszy zgodnych we wszystkich kolumnach odpowiadającym atrybutom X. Jeśli znajdziemy dwa takie wiersze zrównujemy w nich symbole odpowiadające atrybutom Y (jeśli jednym jest a; to drugi staje się też a, lub jeśli jednym jest b,y, a drugi by to oba stają się arbitralnie równe, bądź by, bądź by). Gdy po zmodyfikowaniu wierszy tablicy odkryjemy, że jeden wiersz przybrał postać a|,...,a„ to rozkład jest odwracalny, jeżeli nie to rozkład jest nieodwracalny.

Rozkładem schematu relacji R ={ A!,...,A_n}nazywamy układ p = (R|,...,R_k) złożony z podzbiorów R, takich że R = R,uR₂u...u R_k.

Jednym z motywów dokonywania rozkładów jest to. że można wyeliminować : a) redundancję; b) potencjalna niespójność czyli anomalia przy aktualizacji; c) anomalia przy wyszukiwaniu (nie można wstawiać tylko 1 wartości - trzeba wypełnić całe pola): d) anomalia przy usuwaniu.

Przykład:

Relacja R = ABCDE;

Zależności: A-»C, C-»D, B-»C, DE-»C, CE-kA;

Relacje: R|= AD, R₂=AB, R₃=BE, R₄=CDE, Rs=AE.

1) Budujemy macierz:

	A	B	C	D	E
R	3|	b)2	bu	a.	b,5	X
R ?	3l	a2	b23	b24	b25	X
R	b3	a2	b33	b34	a5
R	b4	b42	a3	a4	a5
R 5	ai	b52	b53	b54	^a5	X

2) Analiza relacji: A—»C: otrzymujemy: ABC

oprflcowflt x>flkvu.flw Polflte vi.il wwAv.uczelm.fl.loss.pl