ullman086 (2)

178 3 RF.I ACYJNY MODEL DANYCH

nazwaStudia adresSrudia

Fox

Disney

Paramount

Holywood Buena Vista Hollywood

RYSUNEK 3.36 Relacja S t ud i oFi 1 jr.o we 2

□

W poprzednich przykładach wystarczało jedno dobrze przemyślane wykonanie dekompozycji, aby utworzyć zbiór relacji, zapisanych w postaci BCNF. Nie zawsze jednak da się to tak zrobić.

PRZYKLAJ) 3.38

Można uogólnić przykład 3.37 w ten sposób, aby otrzymać łańcuch zależności o długości większej niż dwa. Rozważmy następujący schemat relacji:

{tytuł, rok, nazwaStudia, prezes, adrosFrezesa}

Każda krotka zawiera dane dotyczące tytułu filmu, roku jego produkcji, nazwy studia, prezesa studia oraz adresu prezesa studia. A oto trzy zależności funkcyjne, które z założenia zachodzą w tej relacji:

tytuł rok —» nazwaStudia nazwaStudia —> prezes prezes -► adresPrezesa

Jedynym kluczem jest tutaj para {tytuł, rok}. A zatem dwie ostatnie zależności naruszają warunek BCNF. Dekompozycję możemy zacząć na przykład od zależności:

nazwaStudia —► prezes

Najpierw do prawej strony tej zależności funkcyjnej powinniśmy dołączyć wszystkie pozostałe atrybuty z domknięcia atrybutu nazwaStudia. Stosując regułę przechodniości do zależności nazwaStudia prezes oraz prezes —► adresPrezesa, otrzymujemy now^rą zależność:

nazwaStudia —» adresPrezesa

Łącząc dwie zależności z atrybutem nazwaStudia po lew^fej stronie, otrzymujemy:

nazwaStudia —* prezes adresPrezesa

Ta zależność z kolei ma już maksymalnie rozwiniętą prawą stronę, a więc stosujemy dekompozycję i otrzymujemy w ten sposób dwa schematy:

{tytuł, rok, nazwaStudia)

{nazwaStudia, prezes, adresPrezesa}

Pierwsza z nich jest już w postaci BCNF. Jednakże w drugiej relacji atrybut nazwaStudia stanowi jedyny klucz, a obowiązuje zależność

prezes —► adresPrezesa

co stanowi naruszenie warunku BCNF. Trzeba zatem ponownie zastosować dekompozycję w sposób rozszerzający, dołączając do prawej strony atrybut prezes. W wyniku tego wszystkie trzy relacje są już w postaci BCNF:

{tytuł, rok, nazwaStudia}

{nazwaStudia, prezes}

{prezes, adresPrezesa}

□

W praktyce regułę dekompozycji stosuje się tak długo, jak długo wszystkie schematy relacji przyjmą postać BCNF. Możemy być pewni uzyskania pomyślnego wyniku w skończonej liczbie kroków, ponieważ zawsze przy zastosowaniu dekompozycji do relacji R oba schematy wynikowe mają mniej atrybutów' niż R. Gdy dojdziemy już do relacji z dwoma atry butami, jak już przekonaliśmy się w przykładzie 3.35, to relacja z pewnością będzie w postaci BCNF.

Aby odpowiedzieć na pytanie, dlaczego w wyniku dekompozycji powstają coraz mniejsze schematy, załóżmy, żc dana jest zależność A\A₂... A„ —* B,B₂...B_m, która narusza warunek BCNF. Możemy również przyjąć, że ta zależność jest już w postaci rozszerzonej i wobec tego zbiór atrybutów typu B zawiera wszystkie atrybuty relacji zależne od atrybutów typu A, a także że wszystkie atrybuty powtarzające się występują tylko po prawej stronie relacji.

Pierwszy ze schematów', powstający w wyniku wykonania dekompozycji z użyciem danej zależności, zawiera te wszystkie atrybuty R, które nie są typu B. Ponieważ musi istnieć co najmniej jeden atrybut typu B, więc schemat ten nic zawiera wszystkich atrybutów R.

W drugim schemacie występują wszystkie atrybuty typu A i typu B. Nic zawiera on wszystkich atrybutów' R, ponieważ gdyby tak było, wów czas zbiór {Ai, A₂,..., A_n} stanowiłby nadklucz w R (tzn. każdy atrybut R byłby zależny funkcyjnie od A). Ale przecież żadna zależność z nadkluczem po lewej stronie nic może naruszać warunku BCNF.

Zatem uzasadniliśmy, że oba schematy, powstałe w wyniku dekompozycji, są mniejsze od wejściowej relacji R. Stąd też zasadne jest twierdzenie, że powtarzając operacje dekompozycji, otrzymamy w końcu zbiór relacji. /. których każda jest w postaci BCNF.