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-... A_n —> 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_]tA_2>..., A„}\ to oznacza że

A\A₂... A„—*B

wynika z S, jeśli natomiast B nie należy do {A\_tA2....,A„y_t 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 <A₂... A,. —► BiB₂ ... B_m wynika zc zbioru zależności S wtedy i tylko wtedy, kiedy wszystkie atrybuty B\.B₂, -> należą do {A_h A₂,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\A₂... 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\A₂... 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_}, A₂,..., A_n, 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\B₂... B_m—* D. Z założenia indukcyjnego wiemy, żc R spełnia wszystkie zależności postaci A\A₂ ...A„ —> B, dla wszystkich i~ 1.2,..., m. Inaczej mówiąc: jeśli dwie krotki R są zgodne dla atrybutów A\,A₂, ....A,_i} to są zgodne również dla B,. B₂,..., B_m. Ponieważ relacja R spełnia zależność B\B₂... B_m —> Z), w ięc te dwie krotki są również zgodne dla D. A zatem R spełnia zależność A\A₂... 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, A_2t.... to na pewno zależność A,A₂... A„ —* Z) jest prawdziwa. Nie wykazaliśmy jedynie twierdzenia odwrotnego o kompletności algorytmu, tzn. że jeśli zachodzi zależność A\A₂... A_n —* D, to atrybut D na pewno znajdzie się w {A\_y A₂..... A_n}~. 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,A₂...A„ —> B\B₂...B_m oraz B_]B₂...B_m —> C,C₂... ć’i, to w relacji R zachodzi także zależność

a,a₂ ... A_n —* C\C₂... 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, A_2>..._tA„}' i w ten sposób potwierdzimy, że spełniona jest zależność A\A₂... A_n —> C]C₂... C*.