28640 ullman078 (2)
162 3. RELACYJNY MODEL DANYCH
PRZYKŁAD 3.28
Rozważmy relację z atrybutami: A, B, C, D, E, F. Załóżmy, że w tej relacji zachodzą zależności AB —> C, BC —> AD. D —* E oraz CF —» B. Co jest domknięciem zbioru {A, B}, czyli {A, 5}+?
Zaczniemy od (yl, /?}. Po pierwsze zauważamy, że wszystkie atrybuty lewej strony zależności funkcyjnej AB —* C są w A', a więc do X możemy dołączyć atrybut C, który występuje po prawej stronie tej zależności. Zatem po pierwszej iteracji kroku 2 zbiór X przyjmuje postać {A, B. C}. Potem Stwierdzamy, żc lewa strona zależności BC —► AD jest już zawarta w X, a więc do zbioru X można dołączyć atrybuty A oraz. D \ A już znajduje się wl. lecz D nic, więc następny stan X zapisujemy jako {>1, B, C, D). W tym miejscu możemy zastosować zależność D —> E i w ten sposób dołączyć do Af atrybut E. Więcej zmian w X nie można zrobić. Nie możemy zastosować zależności CF —* B, ponieważ jej lewa strona nigdy nic znajdzie się w X. Zatem {A,B}-={A,B,C.L\E}.
□
Jeśli potrafimy obliczyć domknięcie dowolnego zbioru atrybutów, to możemy sprawdzić, czy dana zależność funkcyjna A\A-... An —> B wynika ze zbioru zależności S. Najpierw' obliczamy {A\Ai...A„}' dla zbioru zależności S. Jeśli B należy do {A]tA2>..., A„}\ to oznacza że
A\A2... A„—*B
wynika z S, jeśli natomiast B nie należy do {A\tA2....,A„yt to znaczy, żc ta zależność nie wynika z S. Można testować uogólnioną zależność, która po prawej stronie ma zbiór atry butów, jeśli pamięta się o tym. żc jest to zapis skrótowy zbioru zależności. Zatem zależność A <A2... A,. —► BiB2 ... Bm wynika zc zbioru zależności S wtedy i tylko wtedy, kiedy wszystkie atrybuty B\.B2, -> należą do {Ah A2,A„}\
PRZYKŁAD 3.29
Rozważmy relacje i zależności funkcjonalne, które określono w przykładzie 3.28. Chcemy sprawdzić, czy z tego zbioru zależności wynika zależność AB —*► D. Z przykładu wynika, żc zbiór {A. B, C, A E} jest dopełnieniem {A, B}~. Ponieważ element D jest elementem dopełnienia, więc zależność AB —* D wynika ze zbioru zależności.
A teraz rozważmy zależność D —* A. Chcemy sprawdzić, czy ta zależność wynika zc zbioru zależności. W tym celu najpierw obliczymy {/■>} . Zaczniemy od X- {D}. Na podstawie zależności D —► E do zbioru X można dołączyć element E. Ale to już koniec. Nie można już znaleźć żadnej zależno-
Przyjmijmy, żc zapis BC —* AD jest skrótem zapisu paw zależności BC—* A oraz BC —» D. Można te zależności rozpatrzyć osobno.
ści, która po lewej stronie miałaby któryś z elementów E lub D, a zatem {Dy~ {D. E}. Ponieważ atrybut A nie jest elementem zbioru {D, £}, w ięc wnioskujemy, że D—> A nie wynika ze zbioru zależności.
□
Algorytm domknięć - dlaczego to działa?
Algorytm obliczania domknięć ma sens z bardzo prostego powodu. Stosując indukcję ze względu na liczbę kroków drugiego punktu algorytmu, wykażemy, że dla każdego atrybutu D ze zbioru X zachodzi zależność A\A2... A„ -* D (gdy D jest równe któremuś z atrybutów' typu A, zależność jest trywialna). A zatem wykażemy, że jeśli pewna relacja R spełnia zależności zc zbioru S, to spełnia również zależność A\A2... A„ —* D.
Na początku przyjmujemy, że liczba kroków wynosi 0. Wówczas D musi być równe któremuś z elementów' A}, A2,..., An, a to znaczy, żc A —* D zachodzi w każdej relacji, bowiem jest to zależność trywialna.
Załóżmy teraz, że element D został dołączony do domknięcia w wyniku zastosowania zależności B\B2... Bm—* D. Z założenia indukcyjnego wiemy, żc R spełnia wszystkie zależności postaci A\A2 ...A„ —> B, dla wszystkich i~ 1.2,..., m. Inaczej mówiąc: jeśli dwie krotki R są zgodne dla atrybutów A\,A2, ....A,i} to są zgodne również dla B,. B2,..., Bm. Ponieważ relacja R spełnia zależność B\B2... Bm —> Z), w ięc te dwie krotki są również zgodne dla D. A zatem R spełnia zależność A\A2... A„ —» D.
Powyższy dowód świadczy, że algorytm jest poprawny, tzn. żc jeśli umieścimy w wyniku jego działania atrybut D w domknięciu {Ai, A2t.... to na pewno zależność A,A2... A„ —* Z) jest prawdziwa. Nie wykazaliśmy jedynie twierdzenia odwrotnego o kompletności algorytmu, tzn. że jeśli zachodzi zależność A\A2... An —* D, to atrybut D na pewno znajdzie się w {A\y A2..... An}~. Nasza książka jednak nie obejmie tego dowodu.
3.6.4. Reguła przechodniości
Reguła przechodniości umożliwia kaskadowe łączenie zależności.
• Jeśli w relacji R zachodzą zależności A,A2...A„ —> B\B2...Bm oraz B]B2...Bm —> C,C2... ć’i, to w relacji R zachodzi także zależność
a,a2 ... An —* C\C2... ey
Jeśli pewne atrybuty typu C znajdują sic wśród atrybutów typu A, to możemy jc wyeliminować z prawej strony zależności, stosując regułę zależności trywialnej.
Aby uzasadnić prawdziwość reguły przechodniości, zastosujmy test z p. 3.6.3. Obliczymy domknięcie {A i, A2>...tA„}' i w ten sposób potwierdzimy, że spełniona jest zależność A\A2... An —> C]C2... C*.
Wyszukiwarka
Podobne podstrony:
16212 ullman068 (2) 142 3. RELACYJNY MODEL DANYCH sy i broń, które pochodzą z pozostałych dwóch nadk
18968 ullman090 (2) 186 3. RELACYJNY MODEL DANYCH spełniają zadane zależności funkcyjne. Natomiast p
70840 ullman074 (2) 04 i. RELACYJNY MODEL DANYCH będzie oczywiste, co jest kluczem relacji bez wnika
ullman059 (2) 124 .1 RELACYJNY MODEL DANYCH miały strukturę złożoną zbioru lub zbioru struktur. W pr
ullman060 (2) 126 3 RELACYJNY MODEL DANYCH szczególnych wartości. I tak jak w przypadku atrybutów o
więcej podobnych podstron