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.
*
1
2
1
2
1
2
,
(
)
(
( [
]
[
]
[ ]
[ ])
k k
R U
X
Y
k X
k X
k Y
k Y
∈
∈
∈
∈
→ ⇔
∀
=
→ ⇔
∀
=
→ ⇔
∀
=
→ ⇔
∀
=
⇒
⇒
⇒
⇒
====
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
Y
X
→
→
→
→
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ść
Y
X
→
→
→
→
.
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
A
X
→
→
→
→
nazywa się zależnością częściową, jeśli X jest właściwym
podzbiorem pewnego klucza.
•
Zależność funkcyjna
A
X
→
→
→
→
nazywa się zależnością przechodnią jeśli X nie jest ani podzbiorem
ani nadzbiorem żadnego klucza (
A
X
K
→
→
→
→
→
→
→
→
)
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
U,A
U)
X
A
F
++++
→ ∈
⊆
∈
→ ∈
⊆
∈
→ ∈
⊆
∈
→ ∈
⊆
∈
zachodzi:
•
X
A
∈
∈
∈
∈
(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
A
→
→
→
→
w G i
,
Y
U Y
X
⊂
≠
⊂
≠
⊂
≠
⊂
≠
, jeśli zastąpimy
X
A
→
→
→
→
przez
Y
A
→
→
→
→
otrzymamy 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
U,A
U)
X
A
F
++++
→ ∈
⊆
∈
→ ∈
⊆
∈
→ ∈
⊆
∈
→ ∈
⊆
∈
zachodzi:
5
X
A
∈
∈
∈
∈
(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:
1
2
3
1
2
,
(
)
3
1
3
1
3
2
(
)
(
( [
]
[
])
( [
]
[
]
[ ]
[ ]
[ ]
[ ]))
k k
R U
k
R U
X
Y
k X
k X
k X
k X
k Y
k Y
k Z
k Z
∈
∈
∈
∈
∈
∈
∈
∈
→> ⇔
∀
=
→> ⇔
∀
=
→> ⇔
∀
=
→> ⇔
∀
=
∃
=
∧
=
∧
=
∃
=
∧
=
∧
=
∃
=
∧
=
∧
=
∃
=
∧
=
∧
=
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
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
,
,
oraz
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
'
,
'
,
, to
'
y
y
====
•
X
Y
→>
→>
→>
→>
można interpretować jako regułę:
jeśli
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
,
,
oraz
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
'
,
'
,
, to
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
'
,
,
oraz
R
z
y
x
∈
∈
∈
∈
〉〉〉〉
〈〈〈〈
,
'
,
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