34844 ullman087 (2)

180 3. RELACYJNY MODEL DANYCH T

3.7.5. Projektowanie zależności funkcyjnych

Po wykonaniu dekompozycji schematu relacji tr/eba sprawdzić, czy otrzymane nowe schematy spełniają warunek BCNF. Z przykładu 3.38 wynika, że jeden lub nawet oba wynikowe schematy naruszają warunek BCNF. Ale w jaki sposób można stwierdzić, że schemat nie spełnia warunku BCNF, jeśli nie w iadomo, jakie zależności zachodzą w schemacie? W przykładzie 3.38 określiliśmy te zależności ad hoc. nic stosując żadnej określonej metody. Na szczęście istnieje sposób wyznaczenia zależności, powstających w wyniku dekompozycji.

Załóżmy, że w wyniku dekompozycji relacji R powstaje relacja S oraz jeszcze inna relacja. Zbiór zależności funkcyjnych prawdziwych w R oznaczymy przez F. Aby wyznaczyć zbiór zależności, które są spełnione w F, należy wykonać co następuje:

Rozważmy wszystkie podzbiory X zbioru atrybutów S. Dla każdego z nich obliczmy X. Wówczas, jeśli jakiś atrybut B spełnia następujące warunki:

1.    B należy do S,

2.    B należy do X oraz

3.    B nic należy do X,

to zależność funkcyjnaX —* B jest spełniona w relacji S.

PRZYKŁAD 3.39

Niech schematem relacji R będzie R(A, B, C, D) i załóżmy, że są spełnione w R zależności funkcyjne A —* B oraz B —► C. Niech schemat S(A, C) powstaje w wyniku dekompozycji R. Wyznaczymy teraz zależności spełnione w .V.

Na początku trzeba wyznaczyć domknięcia wszystkich podzbiorów S, czyli zbioru atrybutów {A, C). Zacznijmy od {A}'. Widać, że jest to zbiór [A. B, C}. Ponieważ jednak atrybut B nic należy do S, w ięc nie może tam zachodzić zależność A —* B. Natomiast, ponieważ atrybut C należy do S, zależność A —> C zachodzi w S.

Teraz z kolei rozważmy {C}‘. Ponieważ w żadnej z obowiązujących zależności atry but C nie występuje po lewej stronie, więc {C} = {C}. Można określić ogólną zasadę, że jeśli pewien atry but nie występuje w żadnej zależności po lewej stronie, to jego obecność w schemacie nie ma wpływu na zbiór zależności tam spełnionych.

W końcu trzeba rozważyć {A, C}', którym jest zbiór {A. B, C}. Nie wprowadza on żadnych nowych zależności, ponieważ jest równy {A}~. A w ięc jedyną zależnością spełnioną w Sjest zależność A —* C. Oczyw iście są inne zależności spełnione w S, jak na przykład AD —*■ C lub zależność trywialna A —> A. Ponieważ jednak wyprow adza się je przez zastosowanie reguł opisanych w podrozdziale 3.6, więc nie trzeba ich specjalnie definiować w trakcie wyznaczania zależności funkcyjnych dla schematu S.

□

PRZYKŁAD 3.40

Rozważmy teraz dekompozycję relacji R(A, B, C, D, E) na schemat S(A, B, C) oraz jakaś inna relację. Niechaj w R zachodzą następujące zależności funkcyjne: A —> D, B—+ E, oraz DEC.

Na początek rozważmy {Ay= {A. D). Ponieważ w schemacie S nic występuje atrybut D. wiec ten podzbiór nic wprowadza żadnych zależności. Analogicznie ani {/?}' = {B, E}, ani {C}*- {C} nie powodują wprowadzenia żadnych zależności do S.

Teraz rozważymy domknięcia par atrybutów. {A, B}' = {A, B, C, D, E). A więc w S zachodzi zależność AB —► C. Żadna z innych par nie dostarczy nowych zależności do S. W oczywisty sposób zbiór wszystkich trzech atrybutów S, {A. B, C}, również nie dostarczy- żadnej nowej metry wialń ej zależności. A zatem jedną zależnością, którą można przenieść do schematu ó’, jest zależność AB —* C.

□

3.7.6. Odzyskiwanie danych po dekompozycji

Skoncentrujmy się teraz na zagadnieniu, w jaki sposób algorytm, opisany wp. 3.7.4, zachowuje dane z relacji początkowej. Chcemy bowiem, aby rzutowania początkowych krotek można było „połączyć'’ w sposób umożliwiający otrzymanie wszy stkich i tylko tych krotek, które były dane przed dekompozy cją.

W celu uproszczenia rozważmy relację R o schemacie {A. B. C}, w której zachodzi zależność funkcyjna B —> C, naruszająca warunek BCNF. Możemy w tym miejscu się powołać na przykład 3.37, gdzie występuje przechodni łańcuch zależności, wśród których znajduje się zależność A —* B. Wówczas {A} stanowi jedyny klucz relacji, a wobec tego lewa strona zależności B -* C nie jest kluczem. Inna możliwość polega na tym, że zależność B —> C jest jedyną zależnością nietry wialną, a wówczas jedynym kluczem jest zbiór {A. B}. 1 w tym przypadku również lewa strona zależności B —> C nie jest nadkluczem. W obu przypadkach wykonanie dekompozycji z zastosowaniem zależności B —> C dzieli atrybuty na schematy {A, B} oraz {B. C}.

Uproszczenie poszukiwania zależności

Jeśli do określenia zależności funkcyjnych schematu S powstałego z dekompozycji R stosujemy algorytm z p. 3.7.5, to czasami udaje się ograniczyć liczbę wyznaczanych domknięć podzbiorów S. A oto jakie zasady pozwalają zmniejszyć nakład pracy:

1.    Nie trzeba rozważać domknięcia zbioru wszystkich atry butów- S.

2.    Nie trzeba rozważać zbiorów atrybutów, do których nie należy żadna lewa strona jakiejkolwiek zależności.

3.    Nie trzeba rozważać zbiorów, do których należy jakikolwiek atrybut, który nie występuje po lewej stronie jakiejkolwiek zależności.