1

RELACYJNE BAZY DANYCH cd.

Zależności funkcyjne. Sprowadzanie schematów relacji do postaci normalnej.

Zależności funkcyjne

• Relacja R(U) o schemacie U:={A1, A2,..., An} spełnia zależność funkcyjną X → Y ( X , Y ⊂ U ) gdy w ramach krotek relacji R(U) wartości atrybutów zbioru X determinują jednoznacznie wartości atrybutów zbioru Y tzn.

* X → Y ⇔ (

∀ ( k [ X ] = k [ X ] ⇒ k [ Y ] = k [ Y ]) 1

2

1

2

k , k

R

∈ ( U )

1

2

Przykład1 Niech U := {ID_PRACOWNIKA, NAZWISKO_PRACOWNIKA, IMIĘ_PRACOWNIKA}

o IMIĘ_PRACOWNIKA zależy funkcyjnie od ID_PRACOWNIKA

o ID_PRACOWNIKA nie zależy funkcyjnie od IMIĘ_PRACOWNIKA

o IMIĘ_PRACOWNIKA nie zależy funkcyjnie od NAZWISKO_PRACOWNIKA

Przykład2. Niech U := {NR_INDEKSU, NAZWISKO_STUDENTA, NR_PRZEDMIOTU,OCENA} i

relacja R(U) określona następująco:

R:

NR_I

NAZ

NR_P

O

1

a

101

3

1

a

102

4

2

b

101

3

3

c

101

3

W relacji R(U) spełnione są następujące zależności funkcyjne: I→N , IP→O. Zauważmy, że dla zbiorów

{P} i {O} warunek z (∗) jest również spełniony, ale między tymi zbiorami nie istnieje zależność funkcyjna.

Istotnie, po dodaniu krotki (3, c, 102, 3) warunek z (∗) nie będzie spełniony.

Z każdym schematem relacji U wiążemy pewien zbiór zależności funkcyjnych F. Mówimy, że zależność funkcyjna X → Y wynika logicznie z zależności funkcyjnych F jeżeli w każdej relacji o schemacie U w której spełnione są zależności ze zbioru F spełniona jest również zależność X → Y .

Przez domknięcie zależności funkcyjnych F (zapis F+) rozumiemy zbór wszystkich zależności funkcyjnych wynikających logicznie z zależności funkcyjnych F.

Aksjomatyka ARMSTRONGA -- pozwala znaleźć nowe zależności funkcyjne na podstawie już znalezionych:

Aksjomaty Armstronga. Niech U będzie zbiorem atrybutów i niech

F ⊂ { X → Y | ( X ⊂ U ) ∧ ( Y ⊂ U ) }.

Przez F+ oznaczmy najmniejszy (ze względu na relację zawierania) zbiór zależności funkcyjnych, który zawiera zbiór F i dla dowolnych X,Y,Z⊂U spełnia następujące aksjomaty:

• ( Y ⊂ X ) ⇒ [ (X → Y ) ∈ F+ ],

(zwrotność);

• [ (X → Y ) ∈ F+ ] ⇒ [ (X ∪ Z → Y ∪ Z ) ∈ F+ ], (poszerzalność);

• [ (X → Y ) ∈ F+ ∧ (Y → Z ) ∈ F+] ⇒ [ (X → Z ) ∈ F+ ], (przechodniość).

Zbiór F+ nazywamy (najmniejszym) domknięciem zbioru F.

Analizując zależności funkcyjne w schemacie relacyjnym musimy brać pod uwagę wszystkie zależności funkcyjne obowiązujące w tym schemacie ( a więc te z F+ a nie tylko z F)

2

W tej terminologii pojęcie klucza relacji R(U) o schemacie U:={A1, A2,..., An} i zbiorze zależności funkcyjnych F można zdefiniować w następujący sposób

Kluczem (właściwym) nazywamy taki zbiór atrybutów X ( X ⊂ U ), że

•

X → U ∈ F +

→ ∈

• dla żadnego Y ⊂ X , Y ≠ X nie zachodzi Y → U ∈ F +

→ ∈

(każdy atrybut i cały schemat zależą funkcyjnie od klucza )

Normalizacja

Redundancja

• redundancja polega na powtarzaniu

• wady redundancji: anomalie, konieczność utrzymania spójności kopii, marnowanie miejsca Anomalie

• rodzaje:

o

wstawiania

o

usuwania

o

modyfikacji

Przykład: IMIĘ_PRAC NAZWISKO_PRAC NR_DZIAŁU NAZWA_DZIAŁU

Rozkład relacji i normalizacja

• redundancję usuwa się przez rozkład relacji

• rozkład ma być odwracalny: można odwrócić przez naturalne złączenie

• rozkład relacji powinien doprowadzić do tzw. postaci normalnej

• rozkład relacji nie powinien powodować utraty danych ani zależności funkcyjnych istniejących w relacji pierwotnej

Pierwsza postać normalna

• Schemat relacji (U,F) jest w 1PN gdy wszystkie atrybuty są atomowe -- prostych typów

• 1NF jest wymogiem dla rachunku relacyjnego, a więc i języków zapytań

o

kontrprzykłady:

atrybut tablicowy

zbiór

Uwaga: Dalej będzie mowa jedynie o relacjach spełniających 1PN

Definicje :

• Zależność funkcyjna X → A nazywa się zależnością częściową, jeśli X jest właściwym podzbiorem pewnego klucza.

• Zależność funkcyjna X → Anazywa się zależnością przechodnią jeśli X nie jest ani podzbiorem ani nadzbiorem żadnego klucza ( K → X → A )

3

Druga postać normalna

Schemat relacji (U,F) jest w 2PN gdy każdy atrybut niekluczowy (nie należący do klucza właściwego) jest zależny funkcyjnie od całego klucza właściwego (F+ nie zawiera żadnej zależności częściowej)

• przyczyną braku 2PN jest zwykle błędne połączenie danych

• kontrprzykład: spis przepustek { ID_PRAC. ID_BUDYNKU. NAZWISKO IMIĘ }

o

nazwisko zależy funkcyjnie od id prac., czyli od fragmentu klucza

o

rozkład { ID_PRAC. ID_BUDYNKU.},{ ID_PRAC. NAZWISKO IMIĘ }

doprowadza do 2NF

Trzecia postać normalna

Schemat relacji (U,F) jest w 3PN gdy

o

jest w 2PN i

o

każdy atrybut niekluczowy jest bezpośrednio zależny funkcyjnie od całego klucza

właściwego

Inne sformułowanie 3PN :

Schemat relacji (U,F) jest w 3PN gdy dla każdej zależności X → A∈ F +

→ ∈

(X ⊆ U,A ∈ U) zachodzi:

•

A ∈ X (zależność jest trywialna) albo

• X jest nadkluczem, albo

• A jest atrybutem głównym (jest częścią klucza)

• możliwe przypadki naruszenia 3PN:

o

naruszenie 2PN

o

istnienie zależności tranzytywnej (a więc przechodniej) od klucza właściwego

• przyczyną braku 3PN jest zwykle błędne połączenie danych

• 3PN jest zazwyczaj wystarczająca dla usunięcia praktycznie ważnych anomalii

• każdy schemat relacji daje się rozłożyć na sumę schematów relacji w 3PN zachowując: o

zależności funkcyjne

o

odwracalność rozkładu przez złączenie naturalne (zachowując informacje)

Przykład

ID_PRAC. NAZWISKO STANOWISKO PENSJA

• jest w 2PN bo klucz jest jednoatrybutowy

• istnieje zależność tranzytywna: ID _ PRAC → STANOWISKO → PENSJA

(pensja zależy funkcyjnie od stanowiska)

• rozkład { ID_PRAC, NAZWISKO, STANOWISKO}, {STANOWISKO, PENSJA)

doprowadza do 3PN

Własność:

Każdy schemat relacji daje się rozłożyć na sumę schematów relacji w trzeciej postaci normalnej z zachowaniem zależności funkcyjnych i informacji.

4

Metoda rozkładu schematu na sumę schematów w trzeciej postaci normalnej

1) Wyznaczamy minimalne pokrycie G zbioru zależności funkcyjnych F - minimalne i równoważne F

(tzn takie, że

• ma miejsce równość G+= F+ (zbiór G jest równoważny F)

• prawa strona każdej zależności w G składa się z jednego atrybutu

• usunięcie dowolnej zależności funkcyjnej z G powoduje, że G+ ≠ F+

• dla każdej zależności X → Aw G i Y ⊂ U , Y ≠ X , jeśli zastąpimy X → Aprzez

Y → Aotrzymamy zbiór, który nie jest równoważny F)

2) Dla każdej zależności funkcyjnej w minimalnym pokryciu (włączając do nich klucz podstawowy) z jej atrybutów tworzymy schemat relacji po czym schematy te odpowiednio grupujemy (wg tego samego klucza).

Przykłady:

U:={D,A,T,C} (z interpretacją odpowiednio Dostawca, Adres, Towar, Cena)

F:={ D →

,

A DT → C }

Jedynym kluczem jest DT. Zależność D → A jest zależnością częściową. Schemat ten nie jest w drugiej postaci normalnej. Rozkład {D, A}, {D,T,C} jest rozkładem na schematy w 3PN.

U:={S,T,D,K} (z interpretacją odpowiednio Sklep, Towar, Dział, Kierownik}

F:={ TS → D, SD → K }

Jedynym kluczem jest TS, SD → K jest zależnością przechodnią. Schemat jest w drugiej postaci normalnej ale nie jest w trzeciej. Rozkład {T,S,D}, {D,S,K} jest rozkładem na schematy w 3PN.

Zadanie. Niech U := { A,B,C,D,E,X,Y } i F := { X→C, X→D, CD→E, CD→A, Y→B, C→A, X→A }.

Stosując algorytm dokonać rozkładu U na sumę schematów w 3PN bez utraty danych i utraty zależności funkcyjnych.

Zbiór G={ X→C, X→D, CD→E, Y→B, C→A} jest minimalnym pokryciem.

Zbiór K={X,Y} jest kluczem głównym.

Stąd rozkład na schematy {X,Y}, {X,C,D}, {C,D,E}, {C,A} będącej w trzeciej postaci normalnej.

Postać normalna Boyce-Codda

Relacja jest w BCPN gdy każda nie trywialna zależność funkcyjna jest zależnością od klucza (niekoniecznie właściwego)

Inne sformułowanie BCPN :

Relacja jest w BCPN gdy dla każdej zależności X → A∈ F +

→ ∈

(X ⊆ U,A ∈ U) zachodzi:

5

A ∈ X (zależność jest trywialna) albo X jest nadkluczem Każdy schemat można rozłożyć na schematy w BCNF z zachowaniem informacji (ale niekoniecznie z zachowaniem zależności funkcyjnych)

Przykład

{Miasto, Ulica, Kod}

relacja ta jest w 3PN z anomaliami:

istnieją tu klucze: {M,U}, {U,K}

(nazwy ulic mogą się powtarzać w różnych miastach, zakładamy że nazwy miast się nie powtarzają) występują zależności: MU → K , K → M

schemat jest w 3NF

schemat nie jest w BCNF: K nie jest kluczem

schemat jest nierozkładalny do BCNF (np. {K,U}, {K,M}) bez utraty zależności MU → K

Najczęściej zależności prowadzące do braku BCNF nie są istotne z punktu widzenia projektu.

Związki między postaciami normalnymi :

BCPN => 3PN => 2PN => 1PN

Zależności wielowartościowe i czwarta postać normalna

Zależności funkcyjne wielowartościowe.

Zbiór atrybutów Y jest zależny wielowartościowo od zbioru X gdy z każdą konfiguracją wartości atrybutów z X jest związany zbiór konfiguracji wartości z Y niezależnie od wartości pozostałych atrybutów:

X →> Y ⇔ (

∀ ( k [ X ] = k [ X ]) 1

2

k , k

R

∈ ( U )

1

2

∃ ( k [ X ] = k [ X ] ∧ k [ Y ] = k [ Y ] ∧ k [ Z] =

k [ Z ]))

3

1

3

1

3

2

k

R

∈ ( U )

3

gdzie Z = U \ (X ∪ Y)

Zauważmy, że zależności między atrybutami możemy interpretować jako reguły:

• X → Y można interpretować jako regułę:

jeśli 〈 x, y, z〉 ∈ R oraz 〈 x, y', z' 〉 ∈ R , to y = y'

• X →>

→ Y można interpretować jako regułę:

jeśli 〈 x, y, z〉 ∈ R oraz 〈 x, y', z' 〉 ∈ R , to 〈 x, y, z' 〉 ∈ R oraz 〈 x, y', z〉 ∈ R

najważniejsze własności:

6

X →> Y ⇒ X →> Z

X → Y ⇒ X →> Y

Uwagi.

• Relacja R(U) (w powyższej sytuacji) daje się rozłożyć w sposób odwracalny na dwie: R(X∪Y) i R(X∪Z)

• Istnieje odpowiednik aksjomatów Armstronga dla zależności wielowartościowych

• Zależności X →> U i X →> ∅ spełnione są w każdej relacji R(U). Nazywamy je trywialnymi zależnościami wielowartościowymi

Aksjomaty Armstronga dla zależności wielowartościowych.

Niech U będzie zbiorem atrybutów i niech

M⊂ { X →> Y | ( X ⊂ U ) ∧ ( Y ⊂ U ) }.

Przez M+ oznaczmy najmniejszy (ze względu na relację zawierania) zbiór zależności funkcyjnych wielowartościowych, który zawiera zbiór M i dla dowolnych X,Y,Z⊂U spełnia następujące aksjomaty:

( Y

X )

( X →> Y )∈ M+

⊂

⇒

→>

∈

,

( zwrotność ),

( X →> Y )∈ M+ ⇒ ( X →> U − ( X ∪ Y))∈ M +

→>

∈

, ( dopełnialność ),

( X →> Y )∈ M+ ⇒ ( X ∪ Z →> Y ∪ Z )∈ M+

→>

∈

, ( poszerzalność ),

Przykład:

{Zajęcia, Wykładowca, Podręcznik}

podręczniki nie zależą od wykładowców

nie ma zależności funkcyjnych

zachodzą zależności wielowartościowe

Z →> P i Z →> W (zawsze para!)

można zamienić części krotek ZP i W

Uwaga. Zależności X →> U i X →> ∅ spełnione są w każdej relacji R(U). Nazywamy je trywialnymi zależnościami wielowartościowymi.

Czwarta postać normalna

Relacja jest w 4NF gdy jeżeli każda nietrywialna zależność wielowartościowa jest zależnością od klucza (niekoniecznie właściwego)

+

+

** ( X →> Y ) ∈ M ∧ ( Y ⊂ U − X ) ⇒



( X → U )∈ F .

Przykład:

{Zajęcia, Wykładowca, Podręcznik }

7

istnieją zależności Z →> P i Z →> W

nie ma zależności funkcyjnych

jest więc BCPN

występuje nadmiar informacji: powtórzone dane podręczników i wykładowców

schemat ten można rozłożyć na schematy {Z,W}, {Z,P}

Reguła rozkładu (dla zależności wielowartościowych)

Dla każdej zależności wielowartościowej X →> Y jeśli X∩Y=0 oraz X∪Y ≠ U oraz X nie jest nadkluczem, dokonujemy rozkładu U na X∪Y oraz U-Y.

Przykład

U:={Nr_studenta, Przedmiot, Sport}

F:={ N →> P, N →> S}

X={N}, Y={P}

Stąd U rozkładamy na schematy {N,P}, {N,S}

Związki między postaciami normalnymi

4PN => BCPN => 3PN => 2PN => 1PN