3.3. OD DIAGRAMÓW ZWIĄZKÓW ENCJI DO PROJEKTÓW RELACYJNYCH I 3 1

Ćwiczenie 3.2.2. Należy przekształcić opis w języku ODL z rys. 2.7 do relacyjnego schematu bazy danych. W jaki sposób trzy modyfikacje wyspecyfikowane w ćwicze­niu 2.1.8 wpływają na postać schematu relacyjnego?

!Ćwiczenie 3.2.3. Na rysunku 3.14 przedstawiono w języku ODL definicję klasy klienci. W obiektach tej klasy przechowuje się zbiór różnych rodzajów telefonów (np. domowy, biurowy, fax) oraz zbiór „dołączonych", w którym klient otrzymuje kredyt przy pozyskaniu dla firmy nowych klientów. Należy przekształcić tę specyfikację z języka ODL do schematu relacyjnego bazy danych.

3.3. Od diagramów związków encji do projektów relacyjnych

Przekształcanie diagramów związków encji na schemat bazy danych bar­dzo przypomina przekształcanie projektów w języku ODL do schematu bazy danych. Jednakże w pewnym sensie model związków encji stanowi postać pośrednią między projektami obiektowym a relacyjnym. Oznacza to, że gdy dysponujemy modelem związków encji, to unikamy części ciężkiego trudu. Dwie istotne różnice polegają na tym, że:

W modelu związków encji związki są wyodrębnione jako samoistne pojęcie, a nie są elementem składowym pojęcia klasy. Ta różnica po­zwala uniknąć redundancji pewnego rodzaju, które omawialiśmy w p. 3.2.2, kiedy zdecydowaliśmy, żeby włączyć związek wielowarto­ściowy, taki jak gwiazdy, do krotek reprezentujących obiekty klasy Film.

2. W modelu ODL dla atrybutów można określać złożony typ, np. <set>. Modele związków encji mają bardziej wyważony charakter i mimo że wartości strukturalne są w nich zasadniczo dopuszczalne, to nie są to ani wartości typu Set, ani inne konstruktory typu kolekcji'. Wskutek tego atrybut, którego wartości mają postać zbioru elemen­tów, takie jak np. zbiór adresów gwiazdy omawiany w przykładzie 3.4, zmusza projektanta do tego, aby w modelu związków encji zbiór adresów określać jako zbiór encji oraz utworzyć związek Mieszka-w, który wiąże gwiazdę z jej adresami.

3. W modelu związków encji można określać atrybuty związków. W modelu ODL nie istnieje równoważne pojęcie.

.lednak istnieją takie definicje formalizmu związków encji, w których typy atrybutów traktuje siF podobnie jak w j~zyku ODL: dopuszcza się tam i zbiory i kolekcje lub jeszcze prostsze typy.

132

3.3.1. Od zbiorów encji do relacji

3. RELACYJNY MODEL DANYCH

Na początku rozważmy zbiory encji, które nie są słabe. Modyfikacje, które są potrzebne do przekształcenia słabych związków encji, wprowadzimy w p. 3.3.3. Dla każdego zbioru encji, który nie jest słaby, utworzymy relację o takiej samej nazwie i z takim samym zbiorem atrybutów. W tej relacji nie będzie żadirych danych dotyczących związków, w których dany zbiór uczest­niczy. Związki zostaną zdefiniowane przez osobne relacje, omówimy to za­gadnienie w p. 3.3.2.

PRZYKŁAD 3.1 U

Rozważmy trzy zbiory encji: Filmy, Gwiazdy oraz Studia z rys. 2.8, który odtwarzamy na rys. 3.15. Atrybutami zbioru encji Filmy są: tytuł, rok, długość oraz typFilmu. Zatem relacja Filmy wygląda zupełnie tak samo jak relacja Film z rys. 3.1, którym rozpoczęliśmy podrozdział 3.1.

tytuł ) ( rok ) ~nazwiskoJ ( adres

Filmy Gwiazdy-w~ ~ Gwiazdy

długość ~ typFilmu

nazwa

Posiada

Studia

adres

RYSUNEK 3.15

Diagram E/R bazy danych filmów

O

PRZYKŁAD 3.11

A teraz rozważmy zbiór encji Gwiazdy z rys. 3.15. Tutaj występują dwa atrybuty: nazwisko i adres. A więc odpowiednia relacja mogłaby wyglądać następująco:

3.3. OD DIAGRAMÓW ZWIĄZKÓW ENCJI DO PROJEKTÓW RELACYJNYCH 133

nazwisko adres

Carrie Fisher 123 Maple St., Hollywood Mark Hamill 456 Oak Rd., Brentwood Harrison Ford 789 Palm Dr, Beverly Hills

Ta relacja przypomina relację Gwiazda z rys. 3.6, którą utworzyliśmy w przykładzie 3.3. Jednak miała ona trzy atrybuty, dwa z nich: ulica i mia­sto reprezentowały strukturę adresu. Różnica jest niewielka. Moglibyśmy równie dobrze zaprojektować nasz diagram związków encji z rys. 2.8 tak, aby zbiór encji Gwiazdy miał osobne atrybuty ulica i miasto, co uczyniłoby relację Gwiazdy identycznąz relacjąGwiazda z rys. 3.6.

0

3.3.2. Od związków encji do relacji

Związki z diagramów encji także przyjmują postać relacji. Relacja dane­go związku R ma następujące atrybuty:

1. Dla każdego zbioru encji uczestniczącego w R umieszczamy w sche­macie relacji odpowiadającej R klucze tych zbiorów jako atrybuty tej relacj i.

2. Jeśli związek ma własny klucz, to też dołączamy jego atrybuty do zbioru atrybutów relacji.

Jeśli zbiór encji uczestniczy w związku wielokrotnie, to musimy przemiano­wać atrybuty po to, by uniknąć konfliktu nazw. Podobnie, jeśli zdarzy się, że te same atrybuty muszą wystąpić w relacji R, jako jej własne atrybuty oraz jako pochodzące ze zbioru uczestniczącego w związku, to też nie można do­puścić do powtarzania się nazw i trzeba dokonać przemianowania.

PRZYKŁAD 3.12

Rozważmy związek Posiada z rys. 3.15. Ten związek łączy ze sobą zbiory Filmy i studia. W schemacie relacji Posiada korzystamy z klucza dla Filmów, czyli atrybutów tytuł i rok, oraz z klucza do studiów, którym jest nazwa. Poniżej przedstawiamy schemat relacji:

tui rok nazwaStudia

Gwiezdne Wojny 1977 Fox

Potężne Kaczory 1991 Disney

Świat Wayne'a 1992 Paramount

Atrybut nazwa z relacji studia nazwaliśmy tutaj nazwaStudia, aby schemat byk bardziej zrozumiały.

134 3. RELACYJNY MODEL DANYCH

Zauważmy, że powyższy związek oraz związek z przykładu 3.10, który utworzyliśmy dla zbioru encji Filmy (przedstawiony na rys. 3.1), zawierają do­kładnie te same dane, które zawiera związek z rys. 3.12, utworzony w przykładzie 3.6 dla klasy Film, jedynie z pominięciem właściwości gwiazdy.

0

PRZYKŁAD 3.13

Postępując w podobny sposób, można przekształcić związek Gwiazdy-w z rys. 3.15 do postaci relacji z atrybutami tytuł oraz rok (klucz Filmu) oraz z atrybutem nazwiskoGwiazdy, który stanowi klucz do zbioru encji Gwiaz­dy. Na rysunku 3.16 pokazano przykład relacji Gwiazdy-w. Zauważmy, że ta relacja oraz rys. 3.16 zawierają te same dane co rys. 3.13, nie obejmują one tylko tych atrybutów klasy Gwiazda, które nie wchodzą w skład klucza (atry­butów długość i typFilmu), umieszczone na rys. 3.13.

tytuł I rok I nazwiskoGwiazdy

Gwiezdne Wojny Gwiezdne Wojny Gwiezdne Wojny Potężne Kaczory Świat Wayne'a Świat Wayne'a

RYSUNEK 3.16

Relacja związku Gwiazdy-w

1977 Carrie Fisher

1977 Mark Hamill

1977 Harrison Ford

1991 Emilio Estevez

1992 Dana Carvey

1992 Mike Meyers

Może się wydawać, że na rys. 3.16 atrybut rok jest redundancyjny. Ale wynika to tylko z faktu, że w tym przykładzie nazwy filmów nie powtarzają się. Gdyby tam występowało kilka filmów o tym samym tytule, np. „King Kong", to rok byłby istotny na przykład do rozstrzygnięcia, które gwiazdy występująca której wersji filmu.

0

Zobaczmy, jakie są zalety schematu bazy danych, który otrzymamy, za­czynając od modelu związków encji w porównaniu ze schematem bazy prze­kształconym z modelu ODL.

• Relacje częściej występują w postaci znormalizowanej IIIŻ klasy, co oznacza, że zawierają mniej redundancji niż przy bezpośredniej trans­formacji z opisu ODL.

• Dwukierunkowy związek w modelu ODL zostaje zastąpiony pojedyn­czą relacją, która odzwierciedla związek w obu kierunkach.

PRZYKŁAD 3.14

Również związki wieloargumentowe można w łatwy sposób przekształcić w relacje. Rozważmy'czteroargumentowy związek Kontrakty z rys. 2.12, po­

3.3. OD DIAGRAMÓW ZWIĄZKÓW ENCJI DO PROJEKTÓW RELACYJNYCH I 3 S

wtórzony na rys. 3.17, który obejmuje gwiazdę, film i dwa studia, pierwsze utrzymujące kontrakt z gwiazdą i drugie, które pozyskuje gwiazdę do udziału w konkretnym filmie. Związek ten jest reprezentowany przez relację Kon­trakty, której schemat składa się z atrybutów czterech następujących kluczy dla czterech zbiorów encji:

1. Klucz nazwiskoGwiazdy dla zbioru gwiazd.

2. Klucz złożony z atrybutów tytuł oraz rok dla filmu.

3. Klucz studioGwiazdy wskazujący nazwę pierwszego studia, jak pamiętamy przyjęliśmy założenie, że nazwa studio jest kluczem zbio­ru encji studio.

4. Klucz studioProducenta, który stanowi nazwę tego studia, które produkuje film z udziałem gwiazdy.

RYSLIN>JK 3.17 Związek Kontrakty

Od ODL do relacji

Jak już wspomnieliśmy, w wyniku przeksztalcenia związku z modelu związków encji do schematu relacji czasami otrzymujemy lepszy schemat relacyjny bazy danych niż w sytuacjach, gdy przekształcamy związki w ODL do postaci relacji. Jednakże nic nie stoi na przeszkodzie, aby z modeli związków encji zapożyczyć technikę wydzielania w osobną rela­cję związków typu wiele do jeden albo wiele do wiele. Pozwoli to wyeli­minować redundancję oraz mnożenie się liczby encji, co dzieje się czasami przy próbach implementowania związku wielowartościowego w języku ODL przez definiujące go klasy. Poza tym przypomnijmy ponownie, że w podrozdziale 3.7 będzie można poznać automatyczny sposób naprawie­nia schematu relacji, otrzymanego bezpośrednio z opisu w języku ODL.

136

3. RELACYJNY MODEL DANYCIi

Nazwy atrybutów wprowadzonych do relacji zostały uważnie wybrane, po­nieważ,jeśli jak dotychczas używalibyśmy określenia „nazwa", to nie byłoby jak odróżnić, czy chodzi o nazwę studia producenta, czy o studio gwiazdy.

0

3.3.3. Zasady postępowania ze słabymi zbiorami encj i

Jeśli w diagramie związków encji występuje słaby zbiór encji, to trzeba przestrzegać trzech różnych zasad:

1. Relacja odpowiadająca słabemu zbiorowi encji W musi zawierać nie tylko atrybuty W, ale także te atrybuty kluczy z innych zbiorów encji, które wchodzą w skład zbioru W. Te wspomagające zbiory encji są łatwe do rozpoznania, ponieważ uczestniczą wraz z W w związkach wiele do jeden, a te związki z kolei w diagramie są oznaczone po­dwójnym rombem.

2. Każdy związek, który obejmuje słaby zbiór encji W, musi korzystać ze wszystkich atrybutów klucza W, włączając w to klucze W pochodzące z innych zbiorów encji, które uczestnicząca Yt'.

3. Jednakże, jak się przekonamy później, związki oznaczane podwójnym rombem, które istnieją po to, aby udostępnić dla zbioru W atrybuty klucza z właściwych zbiorów encji, wcale nie muszą być przekształ­cone w osobną relację. Atrybuty tych związków zawsze będą bowiem stanowić podzbiór słabego zbioru encji W, a tego typu związki nie do­starczają poza tym żadnych innych danych, ich jedyna funkcja polega na odnalezieniu właściwego klucza dla W

Oczywiście, przy wprowadzaniu do słabego zbioru encji tych dodatkowych atrybutów trzeba zachować ostrożność i nie dopuścić do tego, aby jakaś na­zwa wystąpiła dwukrotnie. Jeśli jest to konieczne, to część atrybutów, lub nawet wszystkie, trzeba przemianować.

numer ) ( nazwa ) ( adres

Zespoły ł--~ednostka-~~ Studia

RYSUNEK 3.18

Zespoły jako przykład słabego zbioru encji

3.3. OD DIAGRAMÓW ZWIĄZKÓW ENCJI DO PROJEKTÓW RELACYJNYCH I 37

PRZYKŁAD 3.15

Rozważmy słaby zbiór encji Zespo~y z rys. 2.27, który zamieściliśmy ponow­nie na rys. 3.18. Z tego diagramu tworzymy trzy relacje o następujących schematach:

Studia (nazwa, adr) Zespoły (numer, nazwaStudia) Jednostka-w(numer, nazwaStudia, nazwa)

Pierwsza relacja Studia jest wynikiem najprostszego przekształcenia ze zbioru encji o takiej samej nazwie. Druga relacja zespoły jest odpowiedni­kiem słabego zbioru encji Zespoły. Atrybutami tej relacji są atrybuty klucza zbioru Zespoly. Jeśli istniałyby w tym zbiorze jeszcze inne atrybuty, to trzeba by je dołączyć również do schematu tej relacji. Atrybut w relacji zespoły o nazwie nazwastudia stanowi odpowiednik atrybutu nazwa w zbiorze eneji Studia.

Trzecia relacja Jednostka-w powstaje ze związku o takiej samej na­zwie. Jak we wszystkich przypadkach, tak i tu związek eneji reprezentujemy w modelu relacyjnym relacją, której schemat zawiera atrybuty kluczy wszyst­kich zbiorów encji objętych oryginalnym związkiem. W rozważanym przy­padku relacja Jednostka-w zawiera atrybuty numer oraz nazwaStudia, które są kluczem słabego zbioru encji Zespoły oraz atrybut nazwa, który jest kluczem zbioru encji Stadia. Zauważmy jednak, że studio o kluczu nazwa­studia jest tym samym studiem, którego kluczem jest nazwa, ponieważ ,jednostka-w jest związkiem wiele do jeden.

Załóżmy na przykład, że Disney #3 oznacza jeden z zespołów w studio Disneya. Zatem w zbiorze związku Jednostka-w występuje para

(Disney #3, Disney)

Para ta w krotce relacji Jednostka-w będzie reprezentowana następująco:

(3, Disney, Disney)

W konsekwencji możemy w relacji Jednostka-w połączyć atrybuty nazwastudia i nazwa, co da prostszy schemat:

Jednostka-w(numer, nazwa)

A teraz widać już, że można całkiem pominąć relację Jednostka-w, ponie­waż jej atrybuty sąpodzbiorem atrybutów relacji zespoły.

0

PRZYKŁAD 3.16

Rozważmy teraz słaby zbiór encji kontrakty z przykładu 2.31 i rys. 2.28 z p. 2.6.1. Powtarzamy ten diagram na rys. 3.19. Poniżej zamieszczamy sche­mat relacji Kontrakty:

138

3. RELACYJNY MODEL DANYCH

Kontrakty(nazwaGwiazdy, nazwaStudia, tytuł, rok, wyna­grodzenie)

Atrybuty pochodzą z właściwie przemianowanych atrybutów klucza Gwiazd, klucza Studiów, również przemianowanych, dwóch atrybutów, które stanowią klucz Filmów oraz samotnego atrybutu wynagrodzenie należącego tylko do zbioru Kontrakty. Nie tworzy się relacji, które odpowiadałyby związkom: Gwiazda-czego, Film-w oraz Studio-w, bowiem każdy ze schematów stano­wiłby podzbiór relacji Kontrakty.

Warto zauważyć, że otrzymana relacja jest dokładnie taka sama, jaką otrzymalibyśmy, rozpoczynając od diagramów związków encji z rys. 2.13. Przypomnijmy tutaj, że na tamtym rysunku kontrakty zostały przedsta­wione jako związek trójargumentowy między gwiazdami, studiami i fil­mami, a także z atrybutem wynagrodzenie, który należy do związku Kontrakty.

0

Zjawisko wynikające z przykładów 3.15 i 3.16, polegające na tym, że związki w rombach z podwójną ramką nie mają odpowiadających im relacji, stanowi zasadę dla słabych zbiorów encji. Schemat relacji tworzonej dla ska­

RYSUNEK 3.19

Słaby zbiór encji Kontrakty

33. OD DIAGRAMÓW ZWI~ZKÓW ENCJI DO PROJEKTÓW RELACY.INYCH 1 39

bego zbioru encji E zawiera schematy relacji skonstruowanych dla każdego związku R, oznaczanego „podwójnym rombem", który jest typu wiele do jeden i prowadzi od zbioru E do każdego ze zbiorów użyczających E swoich atrybutów kluczy. Ta sytuacja wynika z faktu, że do relacji odpowiadającej zbiorowi E dołącza się wszystkie kluczowe atrybuty E, które z kolei obejmują atrybuty kluczy pozostałych zbiorów objętych związkiem R. A więc reguły dla słabych związków encji można sformułować w następujący sposób:

Jeśli E jest skabym zbiorem encji, to relacja konstruowana dla zbioru E składa się z atrybutów klucza E, włączając te atrybuty, które stanowią część kluczy „wspomagających" zbiorów encji, polączonych z E związkiem typu wiele do jeden.

Nie tworzy się relacji , które odpowiadałyby związkom typu wiele do jeden, łączących słaby zbiór encji z innymi zbiorami eneji, jeśli te związki oznacza się „podwójnymi rombami", dostarczających kluczy do słabych zbiorów encji.

3.3.4. Ćwiczenia do podrozdzia~u 3.3

*Ćwiczenie 3.3.1. Należy przekształcić diagram związków encji z rys. 3.20 do posta­ci relacyjnego schematu bazy danych.

rzad ) miejsce

Rezerwacje doKlienta ~ ~ doRejsu

Klienci i-itelefoni ~ Rejsy

NrKI )I adres (numer> I linia lotn

dzień

RYSUNEK 3.20

Diagram E/ R dla linii lotniczych

*Ćwiczenie 3.3.2. Diagram związków encji, przedstawiony na rys. 3.21, reprezentuje okręty. Okręty nazywają się siostrzanymi, jeśli powstały z tych samych planów. Na­leży przekształcić ten diagram do postaci relacyjnego schematu bazy danych.

140

nazwal rokWodowania

Okręty

Okręt j \5iostrzany

Siostrzany w dla i

RYSUNEK 3.21

Diagram E/R dla okrętów siostrzanych

3. RELACYJNY MODEL DANYCH

*Ćwiczenie 3.3.3. Następujące diagramy związków encji należy przekształcić do postaci relacyjnych schematów baz danych.

a) Rysunek 2.28.

b) Odpowiedź do ćwiczenia 2.6.1.

c) Odpowiedź do ćwiczenia 2.6.4 (a). d) Odpowiedź do ćwiczenia 2.6.4(b).

3.4. Przeksztalcanie struktur podklas do postaci relacji

Pojęcie podklas jest traktowane w modelach obiektowych inaczej niż w modelach związków encji Ta różnica powoduje, że w zależności od wybo­ru któregoś z tych modeli, w różny sposób organizuje się relacje, które mają reprezentować hierarchie klas. Przypomnijmy, że już na wstępie są widoczne różnice, polegające na tym, że:

W modelu ODL obiekt należy do dokładnie jednej klasy. Obiekt dzie­dziczy właściwości ze swoich wszystkich nadklas, ale w sensie tech­nicznym nie należy do żadnej nadklasy.

W modelu związków encji obiekt może być reprezentowany przez en­cje z kilku zbiorów encji, powiązanych związkiem typu isa. Zatem te powiązane encje wszystkie razem reprezentują obiekt i określają jego właściwości: atrybuty i związki.

Spróbujmy prześledzić, w jaki sposób te dwa poglądy wpływają na dobór różnych strategii przy projektowaniu relacyjnego schematu bazy danych. Warto uświadomić sobie, że ani model ODL, ani model związków encji nie wymuszają żadnego określonego sposobu postępowania i jeśli tylko chcemy, to zawsze możemy skorzystać z jeszcze innych modeli.

3.4- PRZEKSZTAŁCANIE STRUKTUR PODKLAS DO POSTACI RELACJI I4I

3.4.1. Relacyjne reprezentacje podklas z modelu ODL

Po pierwsze poznamy technikę przekształcania hierarchii podklas w mo­delu ODL do postaci schematu relacyjnego. Będziemy stosować następujące reguły:

• Każdej podklasie odpowiada osobna relacja.

• W każdej, powstałej w ten sposób relacji, występują wszystkie atry­buty oryginalnej podklasy wraz z atrybutami dziedziczonymi.

PRZYKŁAD 3.17

Rozważmy hierarchię czterech klas, przedstawioną na rys. 2.22. Przypomnij­my sobie ich charakterystykę:

1. Film jest najszerszą klasą. Byla ona już omawiana w wielu przykla­dach w bieżącym rozdziale.

2. Kreskówka, podklasa klasy Film, ma jedną dodatkową właściwość: związek głosy, który jest zbiorem gwiazd.

3. Kryminał, inna podklasa klasy Film, z dodatkowym atrybutem: broń.

4. Kreskówka-Kryminał jest podklasą Obu klas Kreskówka i Krymi­nał, nie ma już żadnych podklas, ale oczywiście wszystkie atrybuty dziedziczy z trzech uadklas.

Schemat dla klasy Fi lm jest taki sam jak poprzednio:

Film(tytuł, rok, długość, typFilmu, nazwaStudia, na­zwiskoGwiazdy)

Pewne typowe krotki zostały przedstawione na rys. 3.13. Podklasa Kreskówka, poza sześcioma atrybutami dziedziczonymi z klasy Film, ma jeszcze własny atrybut głosy, dzięki czemu otrzymujemy siedmioatrybutowy schemat:

Kreskówka (tytuł, rok, długość, typFilmu, nazwaStudia, nazwiskoGwiazdy, głosy)

Następna relacja jest odpowiednikiem podklasy Kryminał, gdzie poza sze­ścioma atrybutami dziedziczonymi z klasy Film występuje także atrybut broń. Zatem schemat dla relacji Kryminał wygląda następująco:

Kryminał (tytuł, rok, długość, typFilmu, nazwaStudia, nazwiskoGwiazdy, broń)

W końcu schemat relacji powstalej dla klasy Kreskówka-Kryminał obej­muje, poza sześcioma atrybutami klasy Film, dwa dodatkowe atrybuty: gło­

142 3. RELACYJNY MODEL DANYCH

sy i broń, które pochodzą z pozostałych dwóch nadklas. Schemat tej relacji zawiera zatem osiem atrybutów:

Kreskówka-Kryminał (tytuł, rok, długość, typFilmu, na­zwaStudia, nazwiskoGwiazdy, głosy, broń)

0

3.4.2. Reprezentowanie związków isa w modelu relacyjnym

Hierarchie typu isa w modelach związków encji są tworzone z encji potrą czonych pewnym związkiem isa. Dlatego naturalny sposób tworzenia schematu relacyjnego dla związku isa polega na utworzeniu osobnych relacji dla po­szczególnych zbiorów encji, które uczestniczą w tym związku, i określeniu atrybutów relacji przez skopiowanie atrybutów oryginalnych zbiorów. Ale przecież jednoznaczna identyfikacja krotki wymaga umieszczenia w każdej relacji kluczy zbiorów połączonych z nią przez związek isa. W rezultacie może okazać się, że dane o elementach niektórych podklas są umieszczane w różnych relacjach, ale to zjawisko występuje w prawie każdym przypadku, ponieważ każde przekształcenie od postaci związków encji do postaci relacyjnej powo­duje rozmieszczenie atrybutów encji i związków pomiędzy różne relacje.

Dla związku typu isa nie tworzy się osobnego związku. Jest on niejawnie zdefiniowany przez to, że w powiązanych encjach pojawiają się te same war­tości klucza.

PRZYKŁAD 3.18

Spróbujmy rozpoznać hierarchię zdefiniowaną w modelu związków encji, który został przedstawiony na rys. 3.22; jest to kopia rys. 2.23 i zawiera frag­ment diagramu związków encji. Ten fragment diagramu można przekształcić do następującej postaci:

1. Relacja Filmy ( tytuł, rok, długość, typFilmu) . Byka już opisana w przykładzie 3.10.

2. Relacja Kryminały (tytuł, rok, broń) . Pierwsze dwa atrybuty tworzą klucz dla wszystkich filmów, a ostatni jest specyficzny dla od­powiadającego tej relacji zbioru encji.

3. Relacja Kreskówki (tytuł, rok). Ta relacja jest zbiorem kreskó­wek. Poza atrybutami klucza nie występują w niej żadne inne atrybu­ty, ale pewne dane o kreskówkach sązawarte w relacji Głosy.

4. Relacja Głosy (tytuł, rck, nazwisko) stanowi odpowiednik związku Głosy, który obejmuje Gwiazdy i Kreskówki. Atrybut nazwi­sko jest kluczem dla Gwiazd, a pierwsze dwa atrybuty są kluczem dla Kreskówek.

3.4. PRlEKSZTAŁCANIE STRUKTUR PODKLAS DO POSTACI RELACJI I43

do Gwiazd

długość ( tytuł ~ (\ rok ~ ~ typFilmu

Filmy

Głosy

broń

Kreskówki I (Kreskówka -Kryminał

RYSUNEK 3.22 Hierarchia filmów

Zauważmy, że na rys. 3.22 nie ma zbioru encji odpowiadającego klasie Kreskówka-Kryminał. Dlatego też tutaj, inaczej niż miało to miejsce w projekcie relacyjnym opisanym w przykładzie 3.17, nie tworzy się specjal­nej relacji dla filmów, które są jednocześnie i kreskówkami, i kryminałami. Wartości atrybutów tych filmów, które są jednocześnie kreskówkami i krymi­nałami można otrzymać kolejno: głosy z relacji Głosy, broń z relacji Krymi­nały, a wszystkie pozostałe dane z relacji Filmy lub z tej relacji, która zo­stała określona dla pewnego związku, obejmującego zbiory Filmy, Kre­skówki lUb Kryminały.

Zauważmy ponadto, że schemat relacji Kreskówki stanowi podzbiór schematu relacji Głosy. Z wielu powodów byłoby dobrze, gdyby relacje Giosy całkiem usunąć ze schematu bazy, zwłaszcza że nie ma w niej żadnych innych danych poza tymi, które występują również w relacji Głosy. Ale przecież w naszej bazie danych mogą pojawić się również kreskówki nieme, a dla takich kreskówek nie można określić wartości atrybutu głosy. Ten pro­blem występuje również w trochę innej postaci w relacji Kreskówki z przy­kładu 3.17. Tam, jeśli postaciom kreskówki nie udzielono głosów, to nie jest ona klasyfikowana w bazie jako kreskówka. Można tę usterkę projektu usunąć w procesie normalizacji, o czym przekonamy się w podrozdziale 3.7.

0

3.4.3. Porównanie różnych metod

Stosowanie dowolnej z metod, opisanych w punktach 3.4.1 i .3.4.2 może powodować kłopoty. W tłuumaczeniu z języka ODL wszystkie właściwości obiektu są przechowywane razem w jednej relacji. Jednak przy takim podejś­

I ~l4 3. RELACYJNY MODEL DANYCH

ciu, jeśli chcemy odszukać określony obiekt,.to trzeba przeszukać szereg rela­cji, zanim trafi się na właściwą. Jeżeli na przykład chcemy odszukać czas trwania pewnego filmu, to korzystając ze schematu z przykładu 3.17, zanim znajdziemy właściwy film, musimy przeszukać cztery różne relacje, w których umieszcza się filmy.

Przy przekształcaniu diagramów encji natomiast trzeba dla danego obiektu w każdym zbiorze encji lub związku, w którym pojawia się obiekt, powtórzyć jego klucz. Takie powtórzenia są marnowaniem przestrzeni na dysku. Ponadto ta metoda powoduje, że powstaje konieczności uzyskiwania danych o obiekcie z wielu relacji. Taki przypadek pojawiłby się w schemacie bazy danych z przykładu 3.18, gdybyśmy chcieli uzyskać dane jednocześnie o czasie trwania kryminału, jak i użytej tam broni.

3.4.4. Tworzenie relacji z wartościami pustymi

Jeszcze inny sposób reprezentowania danych o strukturze hierarchicznej polega na zastosowaniu pustych wartości, które oznacza się NULL. Jeśli w jakiejś krotce występuje pusta wartość pewnego atrybutu, to oznacza to nieformalnie, że w tej krotce wartość tego atrybutu nie może zostać określona. Mimo że wartości puste nie występują w tradycyjnym ujęciu modelu relacyj­nego, to są bardzo wygodne i odgrywają znaczącą rolę w języku zapytań SQL, o czym przekonamy się w podrozdziale 5.9.

Jeśli jednak dopuścimy stosowanie w krotkach wartości NULL, to hierar­chie klas można przedstawić w jednej relacji. Relacja taka ma wszystkie atry­buty, które dotyczą właściwości obiektów z dowolnej klasy w hierarchii. Dzięki temu jeden obiekt jest opisywany w jednej krotce. Atrybuty, które są spoza podklasy danego obiektu, przyjmują w krotce wartości NULL.

PKZYKŁAD 3.19

Gdybyśmy zastosowali ten sposób do rozwiązania problemu z przykładu 3.17, to otrzymalibyśmy jednąrelację, o następującym schemacie:

Film (tytuł, rok, długość, typFilmu, nazwaStudia, nazwiskoGwiazdy, głos, broń)

Filmy takie jak na przykład Kto zabił królika Rogera?, które są zarówno kre­skówkami, jak i kryminałami, byłyby tu reprezentowane jako kilka krotek, w których nie pojawia się wartość pusta, bowiem dla każdego głosu musiała­by istnieć osobna krotka". Natomiast taki film jak Mala Syrenka, który jest

" W rzeczywistości, ponieważ w filmie o Króliku Rogerze występują nie tylko głosy gwiazd, lecz również same gwiazdy, więc dla każdęj pary (gwiazda, głos) musiałaby w relacji pojawić się odrębna krotka. Film, który jest czystą kreskówką, miałby przypisaną wartość pustą dla atrybutu nazwisxocwiazdy, a głosy i inne dane byłyby podane.

3,4. PRZEKSZTAŁCANIE STRUKTUR PODKLAS DO POSTACI RELACJI I ~1S

kreskówką, ale nie jest kryminałem, miałby przypisaną wartość NULL do atry­butu broń. Film Orient Ekspres miałby określoną wartość NULZa dla atrybutu głosy, podczas gdy dla Przeminę~o z wiatrem wartość NULL pojawiłaby się zarówno w polu atrybutu głos, jak i broń.

0

Zauważmy, że w wyniku zastosowania tego podejścia, tak samo jak w przypadku metody opisanej w p. 3.4.2, w jednej relacji występująwszystkie krotki z wszystkich klas tworzących hierarchię. Ponadto, podobnie jak przy użyciu sposobu przedstawionego w p. 3.4.1, możemy wszystkie dane o obiek­cie odnaleźć w jednej relacji.

3.4.5. Ćwiczenia do podrozdzia~u 3.4

Ćwiczenie 3.4.1. Należy przekształcić diagram związków encji przedstawiony na rys. 3.23 do postaci relacyjnego schematu bazy danych.

numer ~ ~ nazwa

sala Wykłady`Wykład-~~ Wydziały Knn /n

Zajęcia (komputery laboratoryjne ~

RYSUNEK 3.23

Diagram EIR dla ewiczenia 3.4.1

Ćwiczenie 3.4.2. Na rysunku 3.24 przedstawiono w języku ODL opis schematu, który przypomina diagram związków encji z ćwiczenia 3.4.1. Trzeba ten opis przekształcić do postaci relacyjnego schematu bazy danych. Należy przy tym pamiętać, że obiekt Wykład ma „identyfikator obiektu" i można w związku z tym wprowadzić własny atrybut odpowiadający temu identyfikatorowi, np. idWykładu. Nie trzeba jednak tutaj stosować strategii przeksztalcania słabych zbiorów eneji, którą opisywaliśmy przy okazji ćwiczenia 3.4.1 (chyba że ktoś koniecznie chce).

interface Wykład(

attribute int numer; attribute string sala;

146 3. RELACYJNY MODEL DANYCH

relationship Wydział WydziałCzego inverse Wydział:: WykładyCzego;

interface ZajęciaLab: Wykład attribute int komputery; };

interface Wydział(

unique attribute string nazwa; attribute string katedra; relationship Set<Wykład> WykładyCzego

inverse Wykład::WydziałCzego; };

RYSUNEK 3.24

Opis w języku ODL wykładów oraz ząjęć laboratoryjnych

RYSUNEK 3.25

Diagram E /R do ćwiczenia 3.4.E

3.5. ZALEŻNOŚCI FONKCYJNE 147

Ćwiczenie 3.4.3. Należy utworzyć relacyjne schematy bazy danych na podstawie opisów w języku ODL, które powstały w następujących ćwiczeniach:

*a) ćwiczenie 2.4.1, b) ćwiczenie 2.4.4.

Ćwiczenie 3.4.4. Należy utworzyć relacyjne schematy bazy danych na podstawie diagramów związków encji, które powstały w następujących ćwiczeniach:

*a) ćwiczenie 2.4.3, b) ćwiczenie 2.4.4.

!Ćwiczenie 3.4.5. Należy przekształcić diagram związków encji z rys. 3.25 do postaci relacyjnego schematu bazy danych.

!Ćwiczenie 3.4.6. Jak zmieniłby się relacyjny schemat bazy danych z ćwiczenia 3.4.5, gdybyśmy go utworzyli na podstawie definicji w języku ODL.

3.5. Zależności funkcyjne

Najważniejszy rodzaj więzów, z jakim mamy do czynienia w modelu rela­cyjnym, dotyczy więzów jednoznaczności, które nazywa się również „zależno­ścią funkcyjną". Wiedza dotycząca tych więzów jest nieodzowna w przypadku powtórnego definiowania schematu relacyjnego w celu wyeliminowania z nie­go redundancji. Te procedury opisujemy dokładnie w podrozdziale 3.7. Poza tym istnieją jeszcze inne więzy, które wspomagają opracowanie dobrego schematu bazy danych: np. zależności wielowartościowe, o których jest mowa w podrozdziale 3.8, oraz zależności istnienia i niezależności, które będą omó­wione w podrozdziale 4.5.

3.5.1. Definicja zależności funkcyjnych

Zależnościc~ funkcyjna w relacji R będziemy nazywać zdanie następującej postaci: „Jeśli dwie krotki relacji R są zgodne dla atrybutów A,, AZ, ... A„ (tzn. obie krotki maja takie same wartości składowych dla wymienionych atrybu­tów), to muszą być również zgodne w pewnym innym atrybucie B". Taki rodzaj zależności zapisujemy formalnie w postaci AI Az ... An --> B, a odczy­tujemyten zapis jako: „A,, Az, ..., An określają funkcyjnie B".

Jeśli zbiór atrybutów AI, Az, ..., An określa funkcyjnie więcej niż jeden atrybut, tzn. na przykład

A,AZ...A„--FBI A, AZ ... An --ł Bz

AIAZ...A„-->B,n

14Ó 3. RELACYJNY MODEL DANYCH

to taki zbiór zależności skrótowo przedstawiamy jako:

A~AZ...A~,--łB,BZ...B„, Na rysunku 3.26 schematycznie przedstawiono zależność funkcyjną w relacji R oraz jej znaczenie dla dwóch krotek tej relacji: t oraz u.

-- B

t~ i r ,

i i i i i i

i i i i

U i i

Jeśli t i u To muszą są być także zgodne tu zgodne tu RYSUNEK 3.26

Wynik zależności funkcyjnej dwóch krotek

tytul rok dlugość typFilmu nazwaStudia nazwisko-

Gwiazdy

Gwiezdne 1977 124 kolor Fox Carrie

Wojny Fisher

Gwiezdne 1977 124 kolor Fox Mark

Wojny Hamill

Gwiezdne 1977 124 kolor Fox Harrison

Wojny Ford

Potężne 1991 104 kolor Disney Emilio

Kaczory Estevez

Świat 1992 95 kolor Paramount Dana

Wayne'a Carvey

Świat 1992 95 kolor Paramount Mike

Wayne'a Meyers

RYSUNEK 3.27 Relacja Film

YRZYKł.AD 3.20

Rozważmy relację Film z rys. 3.13, której instancję prezentujemy na rys. 3.27. W relacji Film w łatwy sposób można wyodrębnić kilka zależności funkcyjnych. Na przykład mogą to być następujące trzy zależności:

3.5. ZALEŻNOŚCI FUNKCYJNE I X19

tytuł rok -ł długość tytuł rok --> typFilmu tytuł rok -~ nazwaStudia

Ponieważ te wszystkie trzy zależności mają te same atrybuty po lewej stronie, zatem możemy je skrótowo zapisać w następujący sposób:

tytuł rok --• długość typFilmu nazwaStudia

Powyższy zbiór zależności funkcyjnych można odczytać w nieformalny sposób następująco: jeśli dwie krotki mają takie same wartości skkadowej tytuł, a także takie same wartości składowej rok, to te dwie krotki muszą mieć również takie same wartości składowej długość, takie same waaości składowej typFilmu oraz takie same wartości składowej nazwastudia. Takie stwierdzenie nabiera sensu, gdy przypomnimy sobie projekt początko­wy, z którego utworzyliśmy schemat relacji Film. Atrybuty tytuł i rok tworzą klucz relacji. Dlatego też można się spodziewać, że przy konkretnym tytule i roku musi istnieć jedna określona długość filmu, jeden typ filmu oraz jedyne studio, które ten film wyprodukowało.

Wnioski na temat schematu na podstawie zaleźnaści funkcyjnych Nie zapominajmy o tym, że zależności funkcyjne, tak jak każde inne wię­zy, dotyczą schematu bazy, a nie określonej instancji. Patrząc na jakąś in­stancję, nigdy nie możemy twierdzić, że na pewno istnieją jakieś zależno­ści funkcyjne, albo że ich nie ma. Patrząc na przykład na rys. 3.27, mogli­byśmy wysnuć wniosek, że występuje z ależność tytuł --> typFilmu, ponieważ w każdej krotee akurat tej instancji relacji Film zachodzi to, że jeśli dwie krotki mająten sam tytui, to zgadza się również typFilmu.

Nie możemy jednak stwierdzać na tej podstawie, że jest to zaleźność funkcyjna w relacji Film. Gdyby na przykład jakaś instancja zawierała krotki opisujące obie wersje King Konga, z których jedna jest czarno-biała, a druga kolorowa, to nasze wcześniejsze stwierdzenie zostałoby obalone.

Jednakże przy bliższej obserwacji widać, że zdanie

tytuł rok --ł nazwiskoGwiazdy

jest fałszywe, nie określa ono bowiem zależności funkcyjnej. Mogliśmy ocze­kiwać, że ponieważ atrybuty tytuł i rok są kluczem dla filmów, to taka zależność musi być prawdziwa. Jednak film nie ma jednoznacznie określone­go zbioru gwiazd, ze względu na sposób w jaki była zdefiniowana klasa Film. Przy przekształcaniu opisu w języku ODL do postaci modelu relacyj­nego trzeba było dla każdego filmu utworzyć szereg' krotek, po jednej dla

I S O 3. RELACY.INY MODEL DANYCH

każdej gwiazdy, która wystąpiła w tym filmie. Dlatego też, mimo że wszyst­kie krotki są zgodne dla pozostałych atrybutów, to nie są zgodne w przypadku nazwiska gwiazdy.

0

3 .5 .2. Klucze relacj i

Mówimy, że atrybut, lub zbiór atrybutów {AI, Az , ..., A„} tworzy klucz relacji, jeśli:

1. Wszystkie pozostałe atrybuty relacji są funkcyjnie zależne od tych atrybutów. A zatem nie może się zdarzyć, aby dwie różne krotki rela­cji R były zgodne dla wszystkich atrybutów AI, AZ, ..., A„.

2. Nie istnieje taki podzbiór właściwy zbioru {A,, Agi, ..., An}, od którego pozostale atrybuty relacji R sązależne funkcyjnie, tzn. klucz musi być minimalny.

Jeśli klucz składa się tylko z jednego atrybutu A, to mówimy, że A (nie {A}) jest kluczem.

PRZYKŁAD 3.21

Atrybuty {tytuł, rok, nazwiskoGwiazdy} tworzą klucz relacje Film, która została przedstawiona na rys. 3.27. Przede wszystkim trzeba wykazać, że wszystkie pozostałe atrybuty w relacji Film są od nich zależne funkcyjnie. Załóżmy więc, że dwie krotki są zgodne dla tych trzech atrybutów: tytuł, rok i nazwiskoGwiazdy. Ze względu na to, że są zgodne dla atrybutów tytuł i rok, muszą być również zgodne dla pozostałych atrybutów: długość, typ­Filmu oraz nazwastudia; wykazano to już w przykkadzie 3.20. A więc dwie różne krotki nie mogą być zgodne dla wszystkich atrybutów tytuł, rok i na­zwi s koGwia zdy, muszą być w takim przypadku tą samą krotką.

Teraz trzeba wykazać, że żaden z podzbiorów właściwych zbioru { ty­tuł, rok, nazwiskoGwiazdy} nie wyznacza pozostałych atrybutów w sposób zależny funkcyjnie. Na początku zauważmy, że atrybut nazwisko­Gwiazdy nie zależy funkcyjnie od atrybutów tytuł i rok, ponieważ prze­ważnie w filmach występuje wiele gwiazd. Zatem para {tytuł, rok) nie stanowi klucza.

Para {rok, nazwiskoGwiazdy) nie może być kluczem, ponieważ w danym roku gwiazda może wystąpić w wielu filmach. A zatem

rok nazwiskoGwiazdy --ł tytuł

nie jest zależnością funkcyjną. Można także twierdzić, że {tytuł, nazwi­skoGwiazdy) nie stanowi klucza, ponieważ w różnych latach mogą zostać

3.5. ZALEŻNOŚCI FUNKCYJNE I S I

wyprodukowane dwa różne filmy o takim sarnym tytule. Może się także zda­rzyć, że w obu tych filmach wystąpi ten sam aktor, mimo że szczerze mówiąc nie potrafimy znaleźć przykładu takiej sytuacji".

0

Czasami zdarza się, że w relacji można wskazać więcej niż jeden klucz. W komercyjnych systemach baz danych wybór klucza głównego może mieć wpływ na implementację, na przykład na sposób przechowywania relacji na dysku.

Na czym polega funkcyjność zależności funkcyjnych? Zależność AI, Az, ...,An --; B nazywa się „funkcyjną", ponieważ w zasa­dzie istnieje funkcja, która dla danej listy wartości atrybutów A,, A2, ..., A„ wyznacza dokładnie jedną (lub nie określa żadnej) wartość atrybutu B. Dla relacji R możemy na przykład określić funkcję, która napisowi „Gwiezd­ne wojny" oraz liczbie całkowitej 1977 przypisuje dokładnie jedną wartość długości, w tym przypadku liczbę 124, która występuje w rela­cji Film. Nie możemy jedvak utożsamiać takich funkcji z matematycznym pojęciem funkcji, ponieważ tutaj nie istnieją reguły przyporządkowywania wartości argumentom. Nie możemy na przykład określić ciągu operacji, których przetworzenie spowodowałoby nadanie parze złożonej z napisu „Gwiezdne wojny" oraz liczby 1977, właściwej długości. Wartości funkcji są w tym przypadku określane w wyniku przeszukiwania relacji. Poszukujemy krotki o podanych wartościach tytuł i rok i w tej krotce odczytujemy wartość składowej długość.

3.5.3. Nadklucze

Zbiór atrybutów, który zawiera klucz nazywa się uadkluczem, co jest skrótem od pojęcia „nadzbioru klucza". A więc każdy klucz jest również nad­kluczem. Jednakże istnieją nadklucze, które same nie są kluczami (minimal­nymi). Zauważmy, że każdy nadklucz spełnia pierwszy warunek bycia klu­czem, wszystkie atrybuty relacji są bowiem od niego zależne funkcyjnie. Jed­nakże najczęściej nadklucz nie spełnia warunku minimalności.

PRZYKŁAD 3.22

W relacji z przykładu 3.21 można określić wiele nadkluczy. Nie tylko sam klucz

' Przypomnijmy, że zależności funkcyjne wynikąją z możliwych do przyjęcia założeń lub uzgodnień dotyczących danych. Nie istnieje żaden autorytet zewnętrzny, który mógłby roz­strzygnąć z absolutną pewnością, czy dana zależność funkcyjna zachodzi, czy też nie. Stąd też należy przyjmować takie założenia, które wydąjąsię nąjbardziej odpowiednie.

152

{tytuł, rok, nazwiskoGwiazdy}

3. RELACYJNY MODEL DANYCłI

jest nadkluczem, ale każdy jego nadzbiór, jak na przykład

{tytuł, rok, nazwiskoGwiazdy, długość}

także jest nadkluczem.

0

3.5.4. Wykrywanie kluczy w relacji

Jeśli schemat relacji otrzymuje się z przekształcenia projektu zapisanego w języku ODL lub w modelu związków encji, to klucz jest zazwyczaj łatwy do przewidzenia. Obecnie rozważymy relacje powstałe na podstawie diagra­mu związków encji, z kolei w p. 3.5.5 omówimy te sytuacje, kiedy relacja powstaje w wyniku przekształcania projektu opisanego w języku ODL.

Jeśli relacja pochodzi z projektu w języku ODL lub związków encji, to prawie na pewno (ale nie w stu procentach) wiadomo, że istnieje w niej tylko jeden klucz. Użyteczna konwencja nakazuje w schemacie relacji taki jedyny klucz oznaczać podkreśleniem atrybutów wchodzących w jego skład.

Pierwsza reguła wyodrębniania klucza może brzmieć zatem następująco:

• Jeśli relacja pochodzi z przekształcenia zbioru encji, to jej klu­czem sąatrybuty kluczowe tego zbioru encji lub klasy.

Alternatywna terminologia kluczy

W niektórych książkach lub opracowaniach można zetknąć się z innymi terminami dotyczącymi kluczy. Można na przykład napotkać termin „klucz" używany w znaczeniu, które my przypisaliśmy pojęciu „nadklu­cza", tzn. jako określenie każdego zbioru atrybutów, od którego wszystkie inne są zależne funkcyjnie, bez wymagania minimalności tego zbioru. W tych źródłach można także napotkać określenie minimalnego klucza ja­ko „klucz kandydacki", co odpowiada pojęciu „klucza" w tym znaczeniu, które my przyjmujemy za właściwe.

PRZYKŁAD 3.23

W przykładach 3.10 oraz 3.11 opisaliśmy sposoby przekształcenia zbiorów encji Filmy i Gwiazdy do postaci relacji. Kluczami w tych zbiorach były od­powiednio {tytul, rok} oraz {nazwisko}. Stały się one kluczami relacji odpo­wiadających tym zbiorom, a schematy powstałych relacji przyjęły następującą postać:

3.5. ZALEŻNOŚCI FUNKCYJNE ł S3

Filmy (tytuł, rok, długość, typFilmu) Gwiazdy (nazwisko, adres)

Klucze relacji oznaczono przez podkreślenie właściwych atrybutów.

0

Druga reguła dotyczy związków binarnych. Jeśli relacja R powstaje ze związku, to liczba argumentów związku ma wpływ na wybór klucza R. Moż­na wyróżnić trzy przypadki:

Jeśli związek jest typu wiele do wiele, to klucze obu zbiorów encji objętych związkiem tworzą zbiór atrybutów klucza R.

Jeśli związek ze zbioru encji E, do zbioru encji Ez jest typu wiele do jeden, to atrybuty klucza E, stają się kluczem R, ale atrybuty klucza EZ nie wchodządo klucza relacji R.

Jeśli związek jest typu jeden do jeden, to atrybuty klucza któregokol­wiek ze zbiorów mogą być kluczem R. W tym przypadku nie ma za­tem jednego tylko klucza.

PRZYKŁAD 3.24

W przykładzie 3.12 omówiono związek Posiada, który jest typu wiele do jeden i prowadzi ze zbioru encji Filmy do zbioru encji Studia. Zatem, zgodnie z naszą regułą, kluczem relacji Posiada są atrybuty kluczowe: tytuł oraz rok z klucza dla Filmów. Schemat relacji Posiada można przedstawić na­stępująco:

Posiada( tytuł, rok, nazwaStudia)

Atrybuty klucza zostały oznaczone podkreśleniem.

W przykładzie 3.13 omówiono inny związek Gwiazdy-w, który zacho­dzi między zbiorami Filmy i Gwiazdy i jest typu wiele do wiele. Tym razem wszystkie atrybuty związku musza wejść w skład klucza powstającej relacji:

Gwiazdy-w(tytuł, rok, nazwiskoGwiazdy)

Jedyny praktyczny przypadek, kiedy relacja, odpowiadająca związkowi wiele do wiele, ma jeszcze inne atrybuty poza atrybutami kluczowymi, występuje wówczas, gdy związek ma jakieś własne atrybuty. Wówczas te atrybuty nie wchodzą w skład klucza.

0

Rozważmy w końcu związki wieloargumentowe. Ponieważ nie można w tym przypadku opisać wszystkich zależności strzałkami wychodzącymi ze związku, zatem trzeba się pogodzić z tym, ze wystąpią takie sytuacje, gdy nie

1 S4 3. RELACYJNY MODEL DANYCH

będzie oczywiste, co jest kluczem relacji bez wnikania w to, które zbiory encji sąfunkcyjnie zależne od innych zbiorów encji. Możemy tylko zapewnić, że:

• Jeśli ze związku wieloargumentowego R wychodzi strzałka w kierunku zbioru encji E, to dla odpowiadającej relacji istnieje co najmniej jeden klucz, który eliminuje klucz E.

Inne notacje zależności funkcyjnych

Wyznajemy pogląd, że po lewej stronie zależności funkcyjnej może wy­stępować wiele atrybutów, natomiast po prawej występuje dokładnie je­den. Ponadto ten atrybut, który występuje po prawej stronie zależności nie może pojawiać się po lewej stronie tej samej zależności. Jednakże dopusz­czamy skrótowy zapis dla kilku zależności, które mają takie same atrybuty z lewej strony, w postaci jednej zależności z prawą stroną otrzymaną z połączenia wszystkich prawych stron zależności wejściowych. Czasami również bywa wygodnie dopuścić zależności „trywialne", w których pra­wą stronę stanowi jeden z atrybutów lewej strony.

W innych opracowaniach jest prezentowany pogląd, że zarówno pra­wa, jak i lewa strona zależności funkcyjnej jest zbiorem atrybutów, a te same atrybuty mogą występować po obu stronach jednocześnie. Między tymi dwoma poglądami nie ma zbyt dużej różnicy, ale w naszych rozwa­żaniach będziemy utrzymywać zasadę, że żaden atrybut nie pojawia się jednocześnie po obu stronach zależności funkcyjnej, chyba że wyraźnie to zostanie stwierdzone.

3.5.5. Klucze relacji powstających z opisów w języku ODL

Sytuacja komplikuje się w przypadku, gdy projekt relacyjny powstąje na podstawie opisu w języku ODL. Po pierwsze w klasie ODL może być okre­ślonych wiele kluczy, a może ich nie być wcale. W takim przypadku trzeba na własną rękę wymyślić w relacji atrybut zastępujący identyfikatory obiektów klasy, wspominaliśmy już o tym problemie w p. 3.2.6.

Jednakże bez względu na to, czy klasa w języku ODL ma własny klucz, czy też trzeba tworzyć odpowiednik dla identyfikatora obiektów, istniejątakie okoliczności, kiedy klucz klasy nie może stanowić klucza relacji. Nasz sposób przeksztalcania projektu z postaci ODL do postaci relacji powoduje bowiem, że czasami zbyt dużo danych ~unieszcza się w pojedynczej relacji. Problem ten pojawia się, gdy relacja jest częścią składową definicji klasy.

Załóżmy na początek, że w klasie C określono jednowartościowy zwią­zek R, skierowany do klasy D. Wówczas zgodnie ze wskazówkami z p. 3.2.4 klucz D zostaje dolączony do relacji tworzonej dla klasy C. Klucz klasy C pozostaje nadal kluczem relacji.

3.5. ZALEŻNOŚCI FUNKCYJNE 1SS

Problem pojawia się wówczas, gdy związek R z C do klasy D jest wielo­wartościowy. Jeśli w kierunku odwrotnym związek odwrotny do R jest jed­nowartościowy (związek R jest typu jeden do wiele), to możemy związek R reprezentować wyłącznie przez jego odwrotność w relacji powstającej dla klasy D; była o tym mowa w ramce pt. „Reprezentowanie związków w jed­nym kierunku" w p. 3.2.7. Odwrotność związku R nie stwarza problemu, po­nieważ w klasie D jest on jednowartościowy.

Ale załóżmy, że związek R jest typu wiele do wiele, a wiec w obu kie­runkach między klasami C a D związek ten jest wielowartościowy. Wówczas może się zdarzyć, ze w relacji tworzonej dla klasy C wystąpi wiele krotek reprezentujących pojedynczy obiekt klasy C. A zatem klucz klasy C nie będzie mógł być kluczem w odpowiadającej klasie C relacji. Aby otrzymać klucz rela­cji odpowiadającej klasie C, trzeba będzie połączyć klucze klas C i D.

PRZYKŁAD 3.25

W przykładzie 3.7, tworząc relację odpowiadającą klasie ODL Film, do atry­butów relacji Film do-lączyliśmy:

1. Klucz nazwastudia z klasy studio, z którą klasa Film jest połą­czona związkiem jednowartościowym należyDo oraz

2. Klucz nazwiskoGwiazdy z klasy Gwiazda (z którą klasa Film jest objęta związkiem wielowartościowym gwiazdy).

Pierwszy z nich pochodzi z jednowartościowego związku, a zatem nie ma wpływu na klucz relacji Film. Jednakże drugi z nich, ponieważ pochodzi ze związku wielowartościowego, musi zostać dołączony do zbioru atrybutów klucza relacji Film, który przyjmuje następującąpostać:

{tytuł, rok, nazwiskoGwiazdy}.

Analiza przykładu relacji Film z rys. 3.13 stanowi potwierdzenie tego, że same atrybuty tytuł i rok nie stanowią klucza relacji Film, ale dołączenie do tego zbioru atrybutu nazwiskoGwiazdy już wystarczy do określenia klucza.

0

Mówiąc ogólniej: jeśli w relacji dla klasy C trzeba reprezentować kilka związków wielowartościowych z C, to wszystkie klucze klas, uczestniczących w tych związkach wraz z klasą C, trzeba dołączyć do pierwotnego klucza klasy C i dopiero wówczas powstaje klucz relacji C. Jeśli kilka związków wielowartościowych łączy klasę C z tąsama klasąD, to w relacji C pojawiają się różne atrybuty reprezentujące klucz klasy D w różnych związkach C i D.

Często zdarza się, że trzeba poprawiać projekt relacji, otrzymany w wy­niku postępowania zgodnego z procedurą tworzenia relacji, którą opisano w podrozdziale 3.2, ponieważ klucz klasy z ODL może paradoksalnie nie być

J S6 3. REI,ACY.INY MODEL DANYCH

wystarczający dla relacji odpowiadającej tej klasie. Sposób postępowania w takich przypadkach zostanie przedstawiony w podrozdziale 3,7. Okaże się wówczas, źe związek typu wiele do wiele można rozłożyć między klasy, które w nim uczestniczą. Wynikowy zbiór schematów relacji jest bardzo podobny do schematów, które uzyskujemy bezpośrednio z przekształceń diagramów związków encji".

3.5.6. Ćwiczenia do podrozdziatu 3.5

Ćwiczenie 3.5.1. Rozważmy relację populacji w Polsce, która zawiera: nazwisko, PESEL, adres, miasto, województwo, kod pocztowy, NIP oraz numer telefonu (7 cyfr). Jakie zależności funkcyjne mogłyby tu zachodzić? Co jest kluczem takiej relacji? Aby odpowiedzieć na te pytania, należy coś wiedzieć o wymienionych nume­rach, Czy na przykład NIP i PESEL są powiązane ze sobą? Czy kod pocztowy jest związany z NIPem? Czy dwie osoby mogą mieć taki sam PESEL? Czy mogą mieć taki sam adres i numer telefonu?

*Ćwiczenie 3.5.2. Rozważmy relację, w której zawiera się opis bieżącego stanu czą­steczek w zamkniętym pojemniku. Atrybuty tej relacji obejmują: identyfikator czą steczki, współrzędne x, y, z połoźenia cząsteczki oraz jej prędkość w układzie x, y, z. Jakich zależności funkcyjnych można by tu oczekiwać? Jakie są klucze?

!Ćwiczenie 3.5.3. W ćwiczeniu 2.3.2 ustaliliśmy cztery założenia na temat związku Uro­cLenia. Należy określić klucze relacji odpowiadających poszczególnym przypadkom. !!Ćwiczenie 3.5.4. Załóżmy, że w relacji R występują atrybuty: A,, Agi, .,., A„. Okre­ślić liczbę nadkluczy R w funkcji n, jeśli:

*a) Jedynym kluczem może być A,.

b) Kluczem może być tylko A, lub Agi.

c) Kluczem może być albo {A,, Az}, albo {A3, A4}. d) Kluczem może być alba {A,, AZ}, albo }A,, A3}.

3.6. Reginy dotyczące zależności funkcyjnych

W bieżącym podrozdziale nauczymy się, w jaki sposób prowadzić wnio­skowanie na temat zależności funkcyjnych. Załóżmy, że uzyskaliśmy infor­tnacje na temat zależności spełnianych przez relację. Często, nawet bez oglą

Dlatego moglibyśmy projekt w języku ODL przekształcić do postaci związków encji, a dopiero potem tworzyć schemat relacyjny. Mimo że można by w ten sposób rozwiązać część problemów, które są charakterystyczne dla podejścia opisanego w podrozdziale 3.2, jednak nie jest to jed~ma droga. Techniki projektowania relacyjnego opisane w podrozdziale 3.7, których i tak trzeba się nauczyć, są co najmniej tak samo efektywne.

3.6. REGUŁY DOTYCZĄCE ZALEŻNOŚCI FUNKCYJNYCH I S%

dania przykładów krotek, można określić pewne warunki, które muszą być spełnione w relacji. Możliwość określenia takich warunków jest niezbędna przy projektowaniu dobrego schematu dla relacji, co zamierzamy omówić w podrozdziale 3.7.

PRZYKŁAD 3.26

Jeśli wiadomo, że w relacji R z atrybutami A, B i C zachodzą związki funk­cyjne A --ł B 1 B -~ C, to łatwo jest wyprowadzić wniosek, że zachodzi rów­nież zależność funkcyjna A --~ C. W jaki sposób uzasadnić taki wniosek? Żeby udowodnić, że zachodzi zależność A --ł C musimy zanalizować dwie krotki z R, które są zgodne dla A, i uzasadnić, że muszą być wówczas zgodne dla C.

Załóżmy, że nasze dwie krotki zgodne dla A mają postać (a, bl, c,) oraz (a, b2, cZ). Przyjęliśmy, że porządek atrybutów w R określono jako A, B, C. Ponieważ spełniona jest zależność A -ł B, a nasze krotki są zgodne dla A, więc muszą być również zgodne dla B, Oznacza to, że b~ = bz, a więc postać naszych krotek w rzeczywistości jest następująca: (a, b, c~) i (a, b, ez), gdzie b jest równe b~ i bz. Z kolei ponieważ R spełnia także zależność B -~ C, więc jeśli krotki sązgodne dla B, to sąrównież zgodne dla C. A zatem c~ = cz, czyli nasze krotki są zgodne dla C. W ten sposób wykazaliśmy, że każde dwie krotki relacji R, które są zgodne dla A, są również zgodne dla C, a zatem za­chodzi zależność funkcyjna A --ł C.

0

Jeśli zależności funkcyjne moźna określić na różne sposoby i nie ma to wpływu na instancje relacji, to takie zależności nazywamy równoważhyn~i. Jeszcze ogólniejsza wkaściwość polega na tym, że zbiór zależności funkcyj­nych S wynika ze zbioru zależności funkcyjnych. To oznacza, że jeśli z faktu, iż dowolna instancja relacji R spełnia wszystkie zależności w T, wynika, że spełnia takźe wszystkie zaleźności w S. Zauważmy, że zbiory zależności funkcyjnych S i T są równoważne wtedy i tylko wtedy, kiedy z S wynika T i jednocześnie z T wynika S.

Poznamy teraz kilka użytecznych zasad dotyczących zależności funkcyjnych. Zasady te, mówiąc najogólniej, pozwalają na zastępowanie zbioru zależności fiu~k­cyjnych zbiorami równoważnymi lub ua dołączanie do zbioru tych zależności, które wynikają ze zbioru początkowego. Widzieliśmy już przykład 3.26 z regule przechodniości (tra~rsitive rule), która umożliwia przejście przez łańcuch zależno­ści. Poznamy także algorytm, który umoźliwia udzielenie odpowiedzi na pytanie o to, czy jakaś zależność funkcyjna wynika z jednej lub więcej zależności.

3.6.1. Zasady podziału i łączenia

W punkcie 3.5.1 określiliśmy zależność funkcyjną:

A,, Agi, ..., A„ -~ B1B2 ... B„,

158

3. RELACYJNY MODEL DANYCH

jako skrótowy zapis zbioru zależności następującej postaci:

A~, Az, ..., A„ -> B, A,, Az, ..., A„ --~ Bz

A,, Az, ..., An -~ Bm

a zatem możemy podzielić atrybuty z prawej strony w ten sposób, że w jednej zależności funkcyjnej po prawej stronie występuje dokładnie jeden atrybut. W podobny sposób możemy zastąpić ciąg zależności funkcyjnych o identycz­nych lewych stronach przez jedną zależność, łącząc atrybuty prawych stron tych zależności. W każdym z tych dwóch przypadków nowy zbiór zależności jest równoważny poprzedniemu. Zapisana wyżej równoważność może być stosowana na dwa sposoby.

• Zależność funkcyjną A~Az ... A„ --~ B1Bz ... B„, możemy zastąpić zbio­rem zależności funkcyjnych A~Az ... A„ --> B;, gdzie i = 1, 2, ..., m. Tę zasadę nazywamy regułci podzialu (spliting rule).

• Zbiór zależności funkcyjnych A~Az ... A„ --> B;, gdzie i = 1, 2, ..., m możemy zastąpić pojedynczą zależnością funkcyjną A~Az ... A„ B~Bz ... B„,. Takie przekształcenie nazywamy regulct lączenia (combi­ning rule).

W przykładzie 3.20 pokazaliśmy, że zbiór zależności funkcyjnych:

tytuł rok -~ długość tytuł rok -~ typFilmu tytuł rok --> nazwaStudia

jest równoważny pojedynczej zależności

tytuł rok ---> długość typFilmu nazwaStudia

Można by sobie wyobrazić, że analogiczna reguła podziału mogłaby do­tyczyć lewych stron zależności. Jednak nie jest to prawdą, co widać na poniż­szym przykładzie.

PRZYKŁAD 3.27

Rozważmy jednąz zależności określonych w relacji Film, na przykład:

tytuł rok ~ długość

Jeśli lewą stronę spróbujemy podzielić, to w wyniku otrzymamy dwie nastę­pujące zależności:

3.6. REGUŁY DOTYCZĄCE ZALEŻNOŚCI FUNKCYJNYCH 1 S9

tytuł -~ długość rok ~ długość

Obie są fałszywe, bowiem długość nie jest zależna funkcyjnie od tytułu filmu, jako że mogą istnieć dwa różne filmy o takim samym tytule (np. King Kong), ale o różnych długościach. Również długość filmu nie zależy od roku produk­cji, w danym roku powstają bowiem filmy o różnych długościach.

0

3.6.2. Zależności trywialne

Mówimy, że zależność funkcyjna A~ Az ... A„ -ł B jest trywialna, jeśli B jest równe któremuś A. Na przykład

tytuł rok --> tytuł

jest zależnościątrywialną.

Każda zależność trywialna zachodzi w każdej relacji, ponieważ jej treść sprowadza się do stwierdzenia, że ,jeśli dwie krotki są zgodne dla wszystkich A~, Az, ..., An, to są zgodne dla pewnego z nich". A zatem możemy korzystać z dowolnej zależności trywialnej, bez potrzeby udowadniania jej w konkret­nych przypadkach danych.

W początkowej deńnicji zależności funkcyjnej nie dopuszczaliśmy przy­padku zależności trywialnych. Jednakże nie ma przeszkód, aby je wprowa­dzić, szczególnie że są we wszystkich przypadkach spełnione, a z kolei często upraszczają ustalenie reguł.

Jeśli dopuścimy stosowanie zależności trywialnych, to także dopuścimy w skrótowych zapisach występowanie tych samych atrybutów po lewej i po prawej stronie. Mówimy, że zależnośćA~ AZ ... A„ -~ B,B, ... B„,jest:

Trywialna, jeśli zbiór złożony z atrybutów typu B jest podzbiorem zbioru atrybutów typu A.

Nietrywialna, jeśli co najmniej jeden z atrybutów typu B znajduje się pośród atrybutów typu A.

Calkowicie nietrywialna, jeśli żaden z atrybutów typu B nie znajduje się pośród atrybutów typu A.

A zatem zależność:

tytuł rok --> rok długość

jest nietrywialna, ale nie jest całkowicie nietrywialna. Po usunięciu atrybutu rok z prawej strony otrzymamy zależność całkowicie nietrywialną.

I6O 3. RELACYJNY MODEL DANYCłi

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,Az ... A„ --~ B,BZ ... B„, jest równoważna zależ­ności A~A~ ... A„ -ł C~CZ ... Ck, gdzie C są tymi elementami z B, które nie są równe A.

Regułę tę, która została zilustrowana na rys. 3.28, nazywamy regulct za­leżności trywialnych.

i i i~ C ~ i ~~.- A -­

i i i i i i i i i i t

i i i i i i i

i i i i i i i i i i i i i i

i i i i i i i

Jeśli t i u To musza sa 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, że zbiór {A,, Az, ..., A„} zawiera atry­buty, a zbiór S zależności funkcyjne. Domknięciem zbioru fA,, Agi, ..., A„} nad zbiorem zależności ,S nazywamy taki zbiór atł-ybutó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,Az ... A„ -ł B, a zatem zależność A,A~ ... An --~ B wynika z S. Domknięcie zbioru atłybutów A,, Agi, ..., A„ oznaczamy przez {A~, Az, ..., A„} `. Dla uprosz­czenia omawiania tematu obliczania domknięć dopuścimy zależności trywial­ne, a więc przyjmiemy, że A,, AZ, ..., A„ jest zawsze zawarte w fA~, Agi, ..., A„} .

3.6. REGUŁY DOTYCZĄCE ZALEŻNOŚCI FUNKCYJNYCH I G I

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 {A~, AZ, ..., A„} ze względu na zbiór zależności funkcyjnych.

Domknięcie

Wypycha

Poczatkowy zbiór

atrybutów

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 {A~, A2, ..., A„}.

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

B1BZ...B„,--łC

gdzie B,, Bz, ..., B„, 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 atrybutu. 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 zbioru X.

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

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 do­mknięciem zbioru {A, B}, czyli {A, B}+?

Zaczniemy od X= {A, B}. Po pierwsze zauważamy, że wszystkie atry­buty lewej strony zależności funkcyjnej AB --> C są w X, 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, że 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ę w X, lecz D nie, więc następny stan X zapisujemy jako {A, B, C, D} . W tym miejscu możemy zastosować zależność D --> E i w ten sposób dołączyć do X atrybut E. Więcej zmian w X nie można zrobić. Nie możemy zastosować za­leżności CF--~ B, ponieważ jej lewa strona nigdy nie znajdzie się wX. Zatem {A, B}+= {A, B, C, D, E}.

0

Jeśli potrafimy obliczyć domknięcie dowolnego zbioru atrybutów, to możemy sprawdzić, czy dana zależność funkcyjna A,Az ... A„ --ł B wynika ze zbioru zależności S. Najpierw obliczamy {A~Az ... A„}+ dla zbioru zależności S. Jeśli B należy do {A,,Az, ..., A„}+, to oznacza że

A~Az...A„--łB

wynika z S, jeśli natomiast B nie należy do {A~, Az, ..., A„}+, to znaczy, że ta zależność nie wynika z S. Można testować uogólnioną zależność, która po prawej stronie ma zbiór atrybutów, jeśli pamięta się o tym, że jest to zapis skrótowy zbioru zależności. Zatem zależność A,Az ... A„ -~ B,Bz ... Bm wynika ze zbioru zależności S wtedy i tylko wtedy, kiedy wszystkie atrybuty B B B należą do {A A . A }+.

~, z~ ..., nt n z~ .~ > >,

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, że zbiór {A, B, C, D, 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 ze zbioru zależności. W tym celu najpierw obliczymy {D}+. 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, że zapis BC --ł AD jest skrótem zapisu pary zależności BC ~ A oraz BC --~ D. Można te zależności rozpatrzyć osobno.

3.6. REGUŁY DOTYCZĄCE ZALEŻNOŚCI FUNKCYJNYCH 163

ści, która po lewej stronie miałaby któryś z elementów E lub D, a zatem {D}+= {D, E}. Ponieważ atrybut A nie jest elementem zbioru {D, E}, więc wnioskujemy, że D -~ A nie wynika ze zbioru zależności.

0

Algorytm domknięć - dlaczego to dziala?

Algorytm obliczania domknięć ma sens z bardzo prostego powodu. Sto­sują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ść AIAZ ... 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 ze zbioru S, to spełnia również zależność A~Az ... An --> D.

Na początku przyjmujemy, że liczba kroków wynosi 0. Wówczas D musi być równe któremuś z elementów AI, A2, ..., A„, a to znaczy, że 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 wy­niku zastosowania zależności BIBZ ... B„, --> D. Z założenia indukcyjnego wiemy, że R spełnia wszystkie zależności postaci AIAZ ... A„ --~ B; dla wszystkich i = 1, 2, ..., m. Inaczej mówiąc: jeśli dwie krotki R są zgodne dla atrybutów AI, AZ, ..., A„, to są zgodne również dla BI, B2, ..., B„,. Po­nieważ relacja R spełnia zależność B1B~ ... Bm -~ D, więc te dwie krotki są również zgodne dla D. A zatem R spełnia zależność AIAZ ... A„ --; D.

Powyższy dowód świadczy, że algorytm jest poprawny, tzn. że jeśli umieścimy w wyniku jego działania atrybut D w domknięciu {A,, AZ, ..., AN}+, to na pewno zależność AIAz ... A„ --> D jest prawdziwa. Nie wy­kazaliśmy jedynie twierdzenia odwrotnego o kompletności algorytmu, tzn. że jeśli zachodzi zależność AIAZ ... A„ --> D, to atrybut D na pewno znajdzie się w {A ~, A2, ..., A„}+. Nasza książka jednak nie obejmie tego dowodu.

3.6.4. Regina przechodniości

Reguła przechodniości umożliwia kaskadowe łączenie zależności.

• Jeśli w relacji R zachodzą zależności A,Az ... A„ --> BIBZ ,.. B„, oraz B~Bz ... Bn, -> C~CZ ... Ck, to w relacji R zachodzi także zależność A,AZ ... A„ --ł CIC~ ,.. Ck.

Jeśli pewne atrybuty typu C znajdują się wśród atrybutów typu A, to mo­żemy je 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,, Az, ..., A„}+ i w ten sposób potwier­dzimy, że spełniona jest zależność A,A~ ... An -; C1C~ ... Ck.

164 3. RELACYJNY MODEL DANYCH

Zależność funkcyjna A~AZ ... An --ł B1B2 ... B„, świadczy o tym, że wszyst­kie atrybuty B~, BZ, ..., B„, należą do zbioru {A,, AZ, ..., A„}+. Stosując zależ­ność B~BZ ... Bm --ł ClC2 ... Ck, mamy więc prawo dołączyć również atrybuty Cl, CZ, ..., Ck do zbioru {A~, A2, ..., A„}+. Ponieważ wszystkie elementy C,Cz ... Ck znalazły się w ten sposób w zbiorze {A~, AZ, ..., A„}+, więc możemy wysnuć wniosek, że zależność

A,Az ... A„ ~ C,CZ ... Ck

jest spełniona we wszystkich relacjach, które spełniają jednocześnie zależno­ści AiA2 ... A„ -~ B~BZ ... B„, oraz B~BZ ... B„, --ł C~CZ ... Ck.

Domknięcia i klucze

Zauważmy, że zbiór {A,, A2, ..., A„}+zawiera wszystkie atrybuty relacji R wtedy i tylko wtedy, gdy elementy A ~, Az, ..., A„ są nadkluczem w R. Bo­wiem tylko wtedy wszystkie atrybuty są zależne funkcyjnie od zbioru A,, AZ, ..., A„. A zatem stwierdzenie, czy atrybuty A~, Az, ..., An stanowią klucz relacji, może polegać na sprawdzeniu po pierwsze, czy wszystkie atrybuty R należą do zbioru {A1, A2, ..., A„}+, a potem czy S" otrzymane z dowolne­go S, który tworzymy przez usunięcie choćby jednego elementu spośród A,, Az, ..., A„, nie zawiera wszystkich atrybutów R.

PRZYKŁAD 3.30

Rozważmy relację Film z rys. 3.12, która powstała w p. 3.2.4 z czterech atry­butów klasy oraz związku należyDo z klasą studio. Poniżej przedstawia­my relację i przykład danych:

tul rok dłu

Gwiezdne wojny 1977 124

Potężne Kaczory 1991 104

Świat Wayne'a 1992 95

nazwaStudia

kolor Fox kolor Disney kolor Paramount

Przypuśćmy, że pewne dane o studiu producenta filmu chcemy przecho­wywać w tej samej relacji. Dla uproszczenia dołączymy tylko nazwę miasta, która będzie reprezentować adres studia. Wówczas relacja może wyglądać następująco:

tul rok dlu ość Filmu nazwaStudia adresS'tudia

Gwiezdne wojny 1977 124 kolor Fox Hollywood

Potężne Kaczory 1991 104 kolor Disney Buena Vista

Świat Wayne'a 1992 95 kolor Paramount Hollywood

3.6. REGUŁY DOTYCZĄCE ZALEŻNOSCI FUNKCYJNYCH I 6S

Z tych danych w łatwy sposób wynikają dwie zależności:

tytuł rok -> nazwaStudia nazwaStudia -~ adresStudia

Pierwsza z nich jest uzasadniona, ponieważ związek należyDo z klasy Film jest jednowartościowy, dany film należy bowiem tylko do jednego stu­dia. Drugą zależność uzasadnia fakt, że atrybut adres w klasie studio jest jednowartościowy, jest on typu string (porównaj rys. 2.6).

Zastosowanie reguły przechodniości pozwala utworzyć nową zależność:

tytuł rok -~ adresStudia

Z tej zależności wynika, że adres zależy funkcyjnie od tytułu i roku (filmu), bowiem jest to adres studia produkującego film.

0

3.6.5. Domknięcie zbioru zależności funkcyjnych

Z powyższych rozważań wynika, że zbiór zależności można rozszerzyć o nowe zależności zarówno trywialne, jak i nietrywialne. W następnych roz­działach chcemy rozróżniać zależności dane, które wynikają bezpośrednio z definicji relacji, od zależności wyprowadzonych z tego oryginalnego zbioru, przez zastosowanie jednej z opisanych powyżej reguł lub przez przetworzenie algorytmu domknięcia zbioru atrybutów.

Czasami może się zdarzyć, że istnieje wybór zależności, których używa się do reprezentowania pełnego zbioru zależności relacji. Każdy zbiór zależ­ności relacji, z którego można wyprowadzić wszystkie inne zależności tej relacji, nazywa się bazą tej relacji. Jeśli składa się tak, że żaden z podzbiorów bazy nie umożliwia wyprowadzenia wszystkich zależności, to taka baza na­zywa się mininaalnc~.

PRZYKŁAD 3.31

Rozważmy relację R(A, B, C), w której każdy atrybut zależy funkcyjnie od pozostałych dwóch atrybutów. Pełny zbiór zależności zawiera zatem sześć zależności z jednym atrybutem po lewej stronie i jednym po prawej: A --> B, A -~ C, B -• A, B --~ C, C --~ A, C --~ B. W tym zbiorze znajdują się także trzy zależności nietrywialne: AB --> C, AC -~ B oraz BC --~ A. Skróty par zależności takie jak A --~ BC oraz trywialne zależności postaci A --~ A oraz nie całkiem trywialne AB -ł BC można także dołączyć do tego zbioru (mimo że nasza ścisła definicja zależności funkcyjnych nie wymaga dołączania zależno­ści trywialnych, częściowo trywialnych ani takich z kilkoma atrybutami po prawej stronie).

166

3. RELACYJNY MODEL DANYCH

Kompletny zbiór reguł wnioskowania

Algorytm obliczania domknięć, opisany w p. 3.6.3, zawsze może po­mó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 {Bl, B2, ..., B„,} c {A~, A2, ..., A„}, to AlA2 ... A„ -~ B~BZ ... B„,. Nazywaliśmy to zależnościami try­wialnymi.

2. Rozszerzenie (Augmentation). Jeśli A~AZ ... A„ --> B~BZ ... B„„ to A,AZ ... A„C~CZ ... Ck -• B,BZ ... BmC,C2 ... Ck dla dowolnych C, CZ ... Ck.

3. Przechodniość (Transitivity). Jeśli AlA2 ... A„ ~ B~BZ ... B„, oraz B~BZ ... B„, -~ C~CZ ... Ck, to AlA2 ... A„ --~ C~CZ ... Ck.

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

{A-•B,B-~A,B-~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ż mi­

nimalnych, ale pozostawimy to zadanie jako ćwiczenie. i

0

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,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) z zależnościami funkcyjnymi A -> B, B -~ C oraz B -> D.

ii) T(A, B, C, D) z zależnościami funkcyjnymi AB -> C, BC -> D, CD. --> A oraz AD -• B.

3.6. REGUŁY DOTYCZĄCE ZALEŻNOŚCI FUNKCYJNYCH 167

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 wyka­zać prawdziwość następujących reguł:

*a) Rozszerzenie lewej strony: Jeśli zachodzi zależność A,AZ ... A„ -~ B, a C jest dowolnym atrybutem, to zachodzi zależność A,AZ ... A„ C --~ B.

b) Rozszerzenie pelne: Jeśli zachodzi zależność A~AZ ... A„ --> B, a C jest do­wolnym atrybutem, to zachodzi zależność A,AZ ... A„ C --~ BC. Uwaga: jeśli ta reguła jest prawdziwa, to stąd niemal bezpośrednio wynika aksjomat roz­szerzenia Armstronga, który opisano w ramce w p. 3.6.5.

c) Pseudoprzechodniość: Załóżmy, że zachodzą zależności A~A2... A„ ­B1Bz ... B„, oraz C,CZ ... Ck -~ D, a wszystkie atrybuty typu B znajdują się wśród C. Wówczas zachodzi również A,AZ ... A„E,EZ ... E~ -~ D, gdzie E po­krywają się z tymi z C, które nie są typu B.

d) Dodawania: Załóżmy, że zachodzą zależności A,AZ ... A„ --~ B~BZ ... B„, oraz C,CZ ... Ck --> D,D2 ... D;; wówczas również zachodzi zależność:

A,AZ ... A„ C1C2 ... Ck -> B,Bz ... B„, D,DZ ... D

Należy usunąć po jednej kopii atrybutów z A i z C lub z B oraz z D.

!Ćwiczenie 3.6.4. Należy wykazać, że ż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 --> B, to B --> A.

b) Jeśli AB --> C i A --~ C, to B --> C. c) Jeśli AB -~ C, to A --~ C lub B --~ C.

!Ćwiczenie 3.6.5. Wykazać, że 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ść nietrywialna.

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

!Ćwiczenie 3.6.7. Udowodnić, że (X")+=X".

!!Ćwiczenie 3.6.8. Mówimy, że zbiór atrybutów X jest domknięty (ze względu na dany zbiór zależności funkcyjnych), jeśli X"=X. Trzeba rozważyć relację o schema­cie R(A, B, 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:

*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, B, C, D}.

1 C)Ó 3. RELACYJNY MODEL DANYCH

!Ćwiczenie 3.6.9. Należy znaleźć minimalne bazy dla zależności i relacji określonych w przykładzie 3.31.

!!Ćwiczenie 3.6.10. Wykazać, że jeśli pewna zależność funkcyjna F wynika z okre­ślonego zbioru zależności, to F można wyprowadzić z tego zbioru, korzystając z aksjomatów Armstronga (zdefiniowano je w ramce w p. 3.6.5). Wskazówka: należy zanalizować algorytm obliczania domknięcia zbioru atrybutów i wskazać, w jaki sposób każdy krok algorytmu jest równoważny z wyprowadzeniem zależności funk­cyjnej przez zastosowanie któregoś z aksjomatów Armstronga.

3.7. Projektowanie relacyjnych schematów baz danych

Już kilka razy wspominaliśmy, że bezpośrednie przekształcenie projektów obiektowych zapisanych w języku ODL (może w mniejszym stopniu stosuje się to do diagramów związków encji) prowadzi do kłopotów z relacyjnymi schema­tami baz danych. Główny problem polega na redundancji, tzn. na tym, że pewne dane powtarzają się w wielu krotkach. Ustaliliśmy już nawet najpowszechniejsze źródło redundancji: próby obejmowania w jednej relacji zarówno jedno- jak i wielowartościowych właściwości obiektu. W p. 3.2.2 rozważaliśmy przykład redundancji, która wynikła, gdy próbowaliśmy umieścić daną jednowartościową o filmie (np. długość filmu) razem z wielowartościowymi właściwościami (np. zbiorem gwiazd filmu). Zilustrowano ten problem na rys. 3.27 i 3.30. Podobną redundancję otrzymaliśmy, gdy próbowaliśmy dane o dacie urodzin gwiazdy przechowywać w jednej relacji ze zbiorem adresów tej gwiazdy.

i tytul rok dlugość typFilmu r~azwaStudia nazwisko­Gwiazdy i

Gwiezdne 1977 124 kolor Fox Carrie Wojny Fisher Gwiezdne 1977 124 kolor Fox Mark Wojny Hamill i

Gwiezdne 1977 124 kolor Fox Harrison Wojny Ford Potężne 1991 104 kolor Disney Emilio

i Kaczory Estevez Świat 1992 95 kolor Paramount Dana Wayne'a Carvey i

j Świat 1992 95 kolor Paramount Mike Wayne'a Meyers RYSUNEK 3.30

i Anomalie w relacji Film

3.7. PROJEKTOWANIE RELACYJNYCH SCHEMATÓW t3AZ DANYCH 1 C)9

W bieżącym podrozdziale rozwiążemy problem projektowania dobrego relacyjnego schematu bazy danych i przedstawimy ten proces w podziale na następujące etapy:

1. Najpierw szczegółowo opiszemy problemy, które wynikają przy two­rzeniu schematu.

2. Następnie przedstawimy metodę dekompozycji, która polega na po­dziale schematu relacji (zbioru atrybutów) na dwa mniejsze sche­maty.

3. Potem opiszemy „postać normalna Boyce'a-Codda", inaczej „BCNF", czyli taki warunek nałożony na schemat, dzięki któremu można wy­eliminować jego niedoskonałości.

4. Połączymy potem te elementy i wytłumaczymy, w jaki sposób zapew­nić spełnienie warunków BCNF przez dekompozycję schematów rela­cyjnych.

3.7.1. Anomalie

Takie problemy jak redundancja, które powstają, gdy próbujemy do po­jedynczej relacji włączyć zbyt wiele danych, są nazywane anomaliami. Poni­żej wyliczamy podstawowe rodzaje anomalii:

1. Redundancja (redudancy). Dane niepotrzebnie powtarzają się w kilku krotkach. Jako przykład może służyć długość i typ filmu zdefiniowane na rys. 3.30.

2. Anomalie modyfikacji (update anomalies). Może się zdarzyć, że wartość danej zostanie zmodyfikowana w pewnej krotce, a w innej nie. Na przykład w pewnym momencie okaże się , że Gwiezdne Wojny trwają naprawdę 125 minut i beztrosko zmieniamy wartość tego atrybutu w pierwszej krotce na rys. 3.30, ale druga i trzecia krotka pozostają bez zmian. Co prawda można by się kłócić, że nikt nie powinien zachowywać się tak beztrosko. Jednak przekonamy się, że można takich sytuacji uniknąć dzięki zmianom schematu relacji Film.

3. Anomalie usunżęć (deletion anomalies). W przypadku gdy dla pewne­go atrybutu zaczyna obowiązywać wartość pusta, to jako efekt ubocz­ny może się zdarzyć utrata części danych. Jeśli na przykład ze zbioru gwiazd filmu Potężne Kaczory usuniemy nazwisko Emilio Estevez, to w bazie nie będzie już żadnych danych o gwiazdach tego filmu. Z re­lacji Film zniknie wówczas ostatnia krotka zawierająca dane o filmie Potężne KaczoYy, a wraz z nią informacje o tym, że film trwa 95 mi­nut oraz że jest kolorowy.

170

3.7.2. Dekompozycja relacji

3. RELACYJNY MODEL DANYCH

Właściwym sposobem eliminowania wymienionych powyżej anomalii jest dekompozycja relacji. Sprowadza się on do podziału atrybutów relacji R między dwa schematy nowych relacji. Reguła dekompozycji obejmuje rów­nież podział krotek relacji wejściowej R między nowe relacje, dzięki operacji rzutowania krotek R. Sposób eliminowania anomalii przez dekompozycję opiszemy zaraz po omówieniu procesu samej dekompozycji.

Relację R o schemacie {At, Az, ..., A„} dekomponujemy między dwie re­lacje S i T o schematach odpowiednio {Bt, B2, ..., B„,} oraz {Ct, Cz, ..., Ck} według następujących zasad:

1. {At, Az, ..., An} _ {Bt, Bz, ..., Bn,} u Ct, Cz, ..., Ck}.

2. Krotki relacji S powstają przez rzutowanie wszystkich krotek relacji R na zbiór atrybutów {Bt, Bz, ..., B„,}. Oznacza to, że z każdej krotki t z bieżącej instancji relacji R pobieramy wartości atrybutów {Bt, Bz, ..., B„,} i tworzymy w ten sposób krotkę relacji S, należącą do jej bieżącej instancji. Ponieważ relacje są zbiorami, więc taką sama krot­kę S można uzyskać z rzutowania różnych krotek relacji R. W takich przypadkach w S umieszcza się tylko jedną kopię.

3. W podobny sposób, z rzutowania krotek bieżącej instancji relacji R na zbiór atrybutów {Ct, Cz, ..., Ck}, otrzymuje się krotki relacji T.

PRZYKŁAD 3.32

Spróbujmy dekomponować relację Film z rys. 3.30. Najpierw dekomponu­jemy schemat tej relacji. Wybór atrybutów do poszczególnych relacji został podyktowany motywami, które omówimy w p. 3.7.3; przedstawia się on na­stępująco:

1. Do relacji Filml dołączamy wszystkie atrybuty prócz atrybutu na­zwiskoGwiazdy.

2. Relacja Film2 obejmuje atrybuty tytuł, rok oraz nazwisko­Gwiazdy.

Proces dekompozycji instancji relacji przedstawimy na krótkim przykła­dzie danych z rys. 3.30. Ale najpierw zbudujemy rzut schematu relacj i Filml:

(tytuł, rok, długość, typFilmu, nazwaStudia}

Na rysunku 3.30 pierwsze trzy krotki mają identyczne wartości tych pięciu atrybutów:

(Gwiezdne Wojny, 1977, 124, kolor, Fox)

3.7. PROJEKTOWANIE RELACYJNYCH SCHEMATÓW BAZ DANYCH 17I

W czwartej krotce wartości tych pięciu atrybutów są inne, a krotki piąta i szósta mają jednakowe wartości tych pięciu atrybutów. Relację Filml przedstawiono na rys. 3.3 I .

tytul rok Gwiezdne Wojny 1977 Potężne Kaczory 1991 Świat Wayne'a 1992

długość typFilmu

124 kolor

104 kolor

95 kolor

nazwaStudia

Fox Disney Paramount

RYSUNEK 3.31 Relacja Filml

A teraz rozważmy rzut danych z rys. 3.30 do schematu relacji Film2. Każda z sześciu krotek różni się albo wartością atrybutu tytuł, albo atrybutu rok, albo nazwiskoGwiazdy, a zatem otrzymujemy w wyniku relację przedstawioną na rys. 3.32.

tytul I rok I nazwiskoGwiazdy

Gwiezdne Wojny 1977 Gwiezdne Wojny 1977 Gwiezdne Wojny 1977 Potężne Kaczory 1991 Świat Wayne'a 1992 Świat Wayne'a 1992

Carrie Fisher Mark Hamill Harrison Ford Emilio Estevez Dana Carvey Mike Meyers

RYSUNEK 3.32 Relacja Film2

O

Zauważmy, że dzięki dekompozycji udało się wyeliminować anomalie, które omawialiśmy wcześniej. Po pierwsze nie ma już redundancji: na przy­kład długość filmu w relacji Filml występuje tylko raz. Znika również ryzy­ko anomalii modyfikacji. Na przykład jeśli musimy zmienić długość filmu Gwiezdne Wojny, to nie powstanie już taka sytuacja, żeby ten film miał w bazie dwie różne wartości tego atrybutu.

Ryzyko wystąpienia anomalii usunięć również znika. Jeśli usuniemy wszystkie gwiazdy filmu Potężne Kaczory, to zostaną w ten sposób usunięte wszystkie dane o tym filmie z relacji Film2. Ale wszystkie inne dane o nim będą nadal dostępne w relacji Fi1m1.

Pozornie może się wydawać, że w dalszym ciągu w relacji Film2 wystę­puje redundancja, ponieważ tytuł oraz rok produkcji filmu ukazują się kilka razy. Trzeba jednak pamiętać o tym, że te dwa atrybuty stanowią klucz dla filmu, a nie da się tu już określić bardziej lapidarnego sposobu identyfikacji. Póza tym w relacji Film2 nie ma żadnych możliwości wystąpienia anomalii modyfikacji. Można mniemać, że gdy zmienimy rok w krotce z Carrie Fisher,

17Z 3. RELACYJNY MODEL DANYCH

a w innych krotkach Gwiezdnych woj en - nie, wystąpi anomalia modyfika­cji. Otóż założenia, dotyczące zależności funkcyjnych, nie zabraniają wystą­pienia filmu o takiej samej nazwie i innym roku produkcji, czyli innych Gwiezdnych Wojen, wyprodukowanych na przykład w 1997 roku z Carrie Fisher w charakterze gwiazdy. A zatem nie należy wprowadzać mechani­zmów uniemożliwiających tego typu modyfikacji, a dodatkowo, taka zmiana wcale nie musi być błędem.

3.7.3. Postać normalna Boyce'a-Codda

Zadanie dekompozycji polega na zastąpieniu relacji równoważnym jej zbiorem relacji, których struktura uniemożliwia wystąpienie anomalii. Oka­zuje się, że istnieje prosty warunek, którego spełnienie zapewnia, że w sche­macie nie występują anomalie, które powyżej omówiliśmy. Warunek ten na­zywa się postacie normalna Boyce'a-Codda lub w skrócie BCNF (Boyce­-Codd normal form).

• Relacja R jest w postaci BCNF wtedy i tylko wtedy, gdy dla każdej nietrywialnej zależności A~, AZ, ..., An -~ B zbiór {A~, A2, ..., An} jest nadkluczem R.

To znaczy, że lewa strona każdej zależności nietrywialnej musi być nadklu­czem. Przypomnijmy, że nadklucz nie musi spełniać warunku minimalności. Można sformułować więc warunek równoważny do BCNF, który stwierdza, że lewa strona każdej nietrywialnej zależności funkcyjnej musi zawierać klucz.

Jeśli odnajdzie się zależność, która narusza warunek BCNF, to czasami warto odszukać wszystkie inne zależności o takiej samej lewej stronie, bez względu na to czy one też naruszają ten warunek, czy nie. Poniżej przedsta­wiamy alternatywną definicję BCNF, w której poszukuje się wszystkich za­leżności o takich samych lewych stronach, z których co najmniej jedna jest nietrywialna i narusza warunek BCNF.

• Relacja R jest w postaci BCNF wtedy i tylko wtedy, gdy dla każdej nietrywialnej zależności A, AZ ... A„ -ł B~Bz ... Bm zachodzącej w R, zbiór {Ai, A2, ..., An} jest nadkluczem R.

Powyższy warunek jest równoważny pierwszej definicji BCNF. Przypomnij­my, że zapis A~ AZ ... A„ --ł B~BZ ... B„, jest skrótem zapisu A~AZ ... A„ --> B;, dla i = 1, 2, ..., m. Ponieważ musi istnieć co najmniej jedno i takie, że B; nie jest typu A (w przeciwnym przypadku zależność A~ Az ... A„ -~ B~BZ ... B„, byłaby trywialna), zatem A,AZ ... A„ -~ B; naruszałoby warunek BCNF według pier­wotnej definicji.

3.7. PROJEKTOWANIE RELACYJNYCH SCHEMATÓW BAZ DANYCH I %3

PRZYKŁAD 3.33

Relacja Film z rys. 3.30 nie jest w postaci BCNF. Aby uzasadnić to stwier­dzenie, najpierw wyodrębnimy zbiór atrybutów tworzących klucz. W przy­kładzie 3.21 podaliśmy powody tego, że zbiór (tytuł, rok, nazwisko­Gwiazdy) stanowi klucz. A zatem każdy zbiór zawierający wymienione trzy atrybuty jest nadkluczem. Te same argumenty, których użyliśmy w przykła­dzie 3.21, mogą posłużyć do uzasadnienie tego, że żaden zbiór, który nie za­wiera wszystkich trzech atrybutów , nie może być nadkluczem. Stąd wynika więc, że atrybuty (tytuł, rok, nazwiskoGwiazdy} są jedynym kluczem relacji Film.

Ale rozważmy z kolei zależność funkcyjną:

tytuł rok ~ długość typFilmu nazwaStudia

która zachodzi w relacji Film. Przypomnijmy, że wynikła ona z faktu, że wprojekcie w języku ODL kluczem był zbiór (tytuł, rok), a poza tym zawierał on atrybuty jednowartościowe długość i typFilmu oraz jedno­wartościowy związek należyDo, który prowadził do studia producenta.

Ale lewa strona tej zależności nie jest nadkluczem. Wiadomo przecież, że atrybuty tytuł i rok nie wyznaczają jednoznacznie szóstego atrybutu nazwiskoGwiazdy. A zatem ta zależność stanowi naruszenie warunku BCNF, a stąd wynika, że relacja Film nie jest w postaci BCNF. A co więcej, jeśli zastosujemy pierwotną definicję BCNF, gdzie po prawej stronie wystę­puje jeden atrybut, to możemy wskazać aż trzy zależności takie jak np. tytuł rok -~ długość, które sąnaruszeniem warunku BCNF.

0

PRZYKŁAD 3.34

Relacja Filml, przedstawiona na rys. 3.31, jest w postaci BCNF. Ponieważ zależność

tytuł rok --> długość typFilmu nazwaStudia

zachodzi dla tej relacji, ale ani atrybut rok, ani atrybut tytuł samoistnie nie wyznaczają jednoznacznie pozostałych atrybutów, więc jedynym kluczem relacji filml może być zbiór (tytuł, rok}. Ponadto jedyna nietrywialna zależność funkcyjna musi mieć z lewej strony co najmniej tytuł i rok, co prowadzi do wniosku, że jej lewe strony muszą być nadkluczem. Stąd też wynika, że Filml jest w postaci BCNF.

0

PRZYKŁAD 3.35

Każda relacja binarna (o dwóch atrybutach) jest w postaci BCNF. Aby uza­sadnić takie twierdzenie, sprawdzimy wszystkie nietrywialne zależności, któ­

---