62517 ullman077 (2)

160 3. RELACYJNY MODEL DANYCH

Atrybuty, które występują równocześnie z prawej i lewej strony, zawsze można pominąć po prawej stronie. Prawdziwe jest zatem stwierdzenie następujące:

• Zależność funkcyjna A\A₂... A_n —> B\B₂... B_m jest równoważna zależności A]A₂... A„ —* C1C2... Cfo gdzie C są tymi elementami z /?, które nie są równe A.

Regułę tę, która została zilustrowana na rys. 3.28, nazywamy regułą zależności trywialnych.

<— A —		<- C -> — B —>

Jeśli t i u To muszą są    być także

zgodne zgodne dla A    dla B

Zatem na pewno są zgodne dla C

RYSUNEK 3.28

Reguła zależności trywialnej

3.6.3. Obliczanie domknięcia zbioru atrybutów

Zanim przejdziemy do stosowania reguł, określimy podstawowe prawo, z którego te reguły wynikają. Załóżmy, żc zbiór {Au A2,A„} zawiera atrybuty, a zbiór S zależności funkcyjne. Domknięciem zbioru [A 1, A₂, nad zbiorem zależności S nazywamy taki zbiór atrybutów B, że jeśli pewna relacja R spełnia wszystkie zależności ze zbioru S, to spełnia także zależność A_]A₂... A,, —> B, a zatem zależność A,A₂... A„ —+ B wynika z S. Domknięcie zbioru atrybutów A\_y A₂, ...,A_n oznaczamy przez [Au A₂, ...,A„} . Dla uproszczenia omawiania tematu obliczania domknięć dopuścimy zależności trywialne, a więc przyjmiemy, że A\, A₂,...>A„ jest zawsze zawarte w (A,,

a ......A„y.

Na rysunku 3.29 przedstawiono procedurę domykania. Początkowy zbiór atrybutów A iteracyjnie uzupełniamy atrybutami z tych prawych stron zależności ze zbioru S, które wynikają z A, i postępujemy w ten sposób tak długo, jak się da. W końcu, gdy już nie można rozszerzyć tego nowego zbioru, to znaczy, że stanowi on domknięcie. Poniżej przedstawiamy bardziej szczegółowy zapis algorytmu obliczania domknięcia zbioru atrybutów {Au A₂, •••> A„) ze względu na zbiór zależności funkcyjnych.

RYSUNEK 3.29

Obliczanie domknięcia zbioru atrybutów

1.    Niech X oznacza nazwę zbioru domknięcia. Na początku zbiorem X jest zbiór atrybutów {Au A₂>..., A,,}.

2.    Teraz znajdujemy te wszystkie zależności funkcyjne postaci

B_xRi... B_m->C

gdzie B\. B_2>..., B_m należą do zbioru X, a C nie należy. Wówczas dołączamy C. do zbioru X.

3.    Powtarzamy krok 2 tak długo, jak długo nie będzie można dołączyć do X żadnego nowego atry butu. Ponieważ zbiór X w ten sposób może się tylko rozszerzać, a z kolei liczba atrybutów każdej relacji jest z założenia skończona, zatem nastąpi taki moment, że niczego więcej nie da się dołączyć do zbioruX.

4.    Jeśli już żadnego atrybutu nie można dołączyć do zbioru X, to znaczy, że jest on wartością {A i, A₂,..., A_n}'.