ullman080 (2)

166 3. RELACYJNY MODEL DANYCH m

166 3. RELACYJNY MODEL DANYCH m

Kompletny zbiór reguł wnioskowania

Algorytm obliczania domknięć, opisany w p. 3.6.3, zawsze może pomóc w rozstrzygnięciu, czy dana zależność funkcyjna wynika z innych danych zależności. Może się jednak okazać interesujące to, że istnieje zbiór reguł, nazywanych aksjomatami Armstronga, które umożliwiają wyprowadzenie z danego zbioru zależności wszystkich tych, które są od nich zależne funkcyjnie. A oto te aksjomaty:

1. Zwrotność (Reflexivity). Jeśli {2?_h B₂,..._? B„} ę {A u A₂,

to A]A₂ — A_n —* B\B₂ ... B_m. Nazywaliśmy to zależnościami trywialnymi.

2. Rozszerzenie (Augmentation). Jeśli A\A₂... A„ —* B_XB₂... B_m, to AiA₂ ...A„C]C₂... C_k —*■ B]B₂... B_mC\C₂— C* dla dowolnych C\C₂ ...C_k.

3.    Przechodniość (TransitMty). Jeśli /M₂...    ... B_m oraz

B\Bi ••• 2?w -> CjC₂... C*, toA\A₂ ...    —► C\C₂... C*.

W tej relacji można wyodrębnić kilka baz minimalnych. Jedna z nich ma postać:

C, C -> B}

Inną zaś zapiszemy jako:

{A-+B,B->C,C->A}

Można w tej przykładowej relacji znaleźć jeszcze wiele baz, również minimalnych, ale pozostawimy to zadanie jako ćwiczenie.

□

f

3.6.6. Ćwiczenia do podrozdziału 3.6

*Ćwiczenie 3.6.1. Rozważmy relację o schemacie R(A, B, C, D) oraz zależności AB -*C,Ć—>DiD—>A.

a)    Określić wszystkie zależności nietrywialne, które wynikają z tych zależności.

b)    Określić wszystkie klucze R.

c)    Określić wszystkie nadklucze w R, które nie są kluczami.

Ćwiczenie 3.6.2. Powtórzyć ćwiczenie 3.6.1 dla następujących schematów i zależności:

i)    S(A, B, C, D) 7. zależnościami funkcyjnymi A —> B, B — C oraz B —* D.

ii)    1\A, B, C, D) z zależnościami funkcyjnymi AB —* C, BC — D, CD. —* A oraz AD -* B.

iii) U(A, B, C, D) z. zależnościami funkcyjnymi A-¹B,B—>C,C-¹D oraz D-¹A.

Ćwiczenie 3.6.3. Korzystając z testu domknięcia, opisanego w p. 3.6.3, należy wykazać prawdziwość następujących reguł:

*a) Rozszerzenie lewej strony: Jeśli zachodzi zależność A\A₂... A„ —» B. a C jest dowolnym atrybutem, to zachodzi zależność A_t/1₂- A_n C —¹ B.

b)    Rozszerzenie pełne: Jeśli zachodzi zależność A\A₂... A„ —¹ £, a C jest dowolnym atrybutem, to zachodzi zależność A\A₂... A_nC —¹ BC. Uwaga: jeśli ta reguła jest prawdziwa, to stąd niemal bezpośrednio wynika aksjomat rozszerzenia Armstronga, który opisano w ramce w p. 3.6.5.

c)    Pseudoprzechodniość: Załóżmy, że zachodzą zależności A\A₂... A_n > B_:B₂... B_m oraz C-.C₂... C\ £>, a wszystkie atrybuty ty^rpu B znajdują się wśród C. Wówczas zachodzi również A_{A₂... A„E_XE₂... E_; > D. gdzie £ pokrywają się z tymi z C, które nie są typu B.

d)    Dodawania: Załóżmy, że zachodzą zależności A\A₂... A„ > £,£_;... B„ oraz C\C₂... Ck - ¹ D\D₂... D,\ wówczas również zachodzi zależność:

A iA₂... A„ C\C₂... Ck —¹ B[B₂... B_m D[D₂... D Należy usunąć po jednej kopii atrybutów' z A i z Club zB oraz z D.

!Ćw iczenic 3.6.4. Należy wykazać, ze żadna z poniższych reguł nie jest prawdziwa dla zależności funkcyjnych. W tym celu należy wskazać przykłady relacji, która spełnia przesłanki, ale nie spełnia wniosku.

*a) Jeśli A —> £. to £ —» A.

b)    Jeśli AB — C i A — C, to B -¹ C.

c)    Jeśli AB —> C, to A —¹► C lub £ —► C.

.'Ćwiczenie 3.6.5. Wykazać, 2e jeśli w' relacji nie występuje żaden atrybut, który zależy funkcyjnie od wszystkich innych atrybutów, to w tej relacji nie istnieje żadna zależność nictrywialna.

IĆwiczenic 3.6.6. Załóżmy, że X i Y są zbiorami atrybutów . Należy- wykazać, że jeśli X c: Y. to X¹ ę Z¹, gdzie domknięcia są obliczane względem tego samego zbioru zależności funkcyjnych.

!Ćwiczenie 3.6.7. Udowodnić, 2e (A^-)’ - >C.

!IĆwiczenic 3.6.8. Mówimy, że zbiór atrybutów A" jest domknięty (ze względu na dany zbiór zależności funkcyjnych), jeśli X' = X. Trzeba rozważyć relację o schemacie R(A, B_y C\ D) oraz nieznanym zbiorze zależności funkcyjnych. Jeśli określimy który zbiór atrybutów jest domknięty, to odnajdziemy zbiór zależności funkcyjnych Jakie są te zależności, gdy:

1

a) Wszystkie podzbiory tych czterech atrybutów są domknięte.

b)    Jedynymi zbiorami domkniętymi są zbiór pusty i cały zbiór {A, B, C, D}.

c)    Domknięte zbiory to: zbiór pusty, {A, B) oraz {A, £. C, D}.