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