Bazy danych  wykład szósty
Normalizacja modelu bazy danych
Konrad Zdanowski
Uniwersytet Kardynała Stefana Wyszyńskiego, Warszawa
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 1 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Rozważmy tabelę Ksiazki:
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski ... 2010 Arcana Kraków
S. Cenckiewicz Długie ramię ... 2011 Zysk i Sk-a Warszawa
W tabeli występuje redundancja informacji.
Skutkuje to trudnościami przy dodawaniu, aktualizowaniu lub
usuwaniu krotek z tabeli.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 2 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Dodanie krotki (P., Zyzak, ..., Arcana, Warszawa) rozspójni nam
informacje w tabeli.
Wydawnictwo Arcana będzie miało dwa adresy.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 3 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Modyfkując adres wydawnictwa musimy zrobić to we wszystkich
krotkach, w których ono występuje
Zmiana jednej informacji wymaga zmiany wielu krotek w bazie
danych
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 4 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przyklad
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Usuwając książkę Długie ramię Moskwy stracimy wszystkie
informacje o wydawnictwie Zysk i Sk-a.
Usuwająć książkę tracimy informacje o wydawnictwie.
Jedna krotka zawiera dwie, niezależne od siebie informacje. Nie
można usunąć jednej nie usuwając drugiej.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 5 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Anomalie projektu BD
Nadmiarowość  powtarzanie się wiele razy tej samej informacji.
Anomalie aktualizacji  modyfikacja jednej informacji może
pominać krotki.
Anomalie usuwania  usunięcie krotek pozbawia nas informacji,
które chcielibyśmy zachować.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 6 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Cechy optymalnego modelu BD
Ta sama informacja w BD nie powtarza się wiele razy.
Informacje w różnych krotkach nie są od siebie zależne.
Informacja w jednej krotce jest  atomowa .
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 7 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Cechy optymalnego modelu BD
Podczas procesu normalizacji usuwamy anomalie, które mogą
występować w BD.
Wyróżnimy pewne postacie normalne oraz omówimy jak je
uzyskać.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 8 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Pierwsza postać normalna
Definicja 1
Relacja jest w pierwszej postaci normalnej (1NF), jeśli wszystkie
atrybuty tej relacji mają atomowe typy danych.
Pierwsza postać normalna wyklucza sytuację, w której typ danych
danego atrybutu to zbiór wartości, struktura lub inna relacja.
Dlatego atrybut imiona, który zawierałby wszytkie imiona danej osoby
nie jest zgodny z 1NF.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 9 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Druga postać normalna
Definicja 2
Relacja jest w drugiej postaci normalnej (2NF), jeśli jest w 1NF oraz
żaden atrybut który nie wchodzi w skład klucza nie zależy funkcyjnie
od atrybutów będących właściwym podzbiorem klucza.
Druga postać normalna wyklucza sytuację, w której atrybut X nie
wchodzący w skład klucza zależy funkcyjnie od właściwej części
klucza. Jeśli tak by było, to możemy stworzyć nową tabelę z tą
zależnością usuwając X z oryginalnej tabeli.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 10 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja relacji
Definicja 3
Rozważmy relację R(A1, . . . , An) oraz zbiory atrybutów
{B1, . . . , Bk} *" {C1, . . . , Cm} = {A1, . . . , An}.
Dekompozycja R na relacje S(B1, . . . , Bk) i T (C1, . . . , Cm) zachodzi
gdy
S = ĄB1,...,Bk (R) oraz T = ĄC1,...,Cm(R).
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 11 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Relację Ksiazki możemy zdekomponować na Wydanie(imie, nazwisko,
tytul, rok, wydawca) oraz Wydawnictwo(wydawca, adres).
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
imie nazwisko tytul rok wydawca
S. Cenckiewicz SB a Lech 2009 Arcana
P. Gontarczyk SB a Lech 2009 Arcana
A. Nowak Od Polski do 2010 Arcana
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a
wydawca adres
Arcana Kraków
Zysk i Sk-a Warszawa
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 12 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja relacji
Mając daną dekompozycję R(A1, . . . , An) na S(B1, . . . , Bk) i
T (C1, . . . , Cm) możemy zdefiniować złożenie relacji S i T .
Definicja 4
Niech D1, . . . , Dr będzie częścią wspólną B1, . . . , Bk i C1, . . . , Cm.
Możemy zdefiniować złączenie tych relacji
R = S D1,...,Dr T .
Relację R tworzymy jako S natural join T (czyli S join T on
D1, . . . , Dr ).
Ale czy R = R?
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 13 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności funkcyjne
Definicja 5
Atrybuty B1, . . . , Bm są zależne funkcyjnie od atrybutów A1, . . . , An w
relacji R jeśli dowolne dwie krotki t, t z relacji R, które zgadzają się na
atrybutach A1, . . . , An muszą zgadzać się na atrybutach B1, . . . , Bm.
Zależność funkcyjną oznaczamy przez A1 . . . An B1 . . . Bm.
Definicja 6
Zależnośc funkcyjną A1 . . . An A nazywamy trywialną jeśli
A " {A1, . . . , An}.
Zależność funkcyjną należy traktować jako zależność dotyczącą
schematu relacji a nie jej szczególnego wystąpienia.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 14 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności funkcyjne
Dekomponując relację R na relacje S i T dzielimy zbiór zależności
funkcyjnych relacji R na dwa zbiory dla S i T w zależności od tego,
która z relacji posiada wszystkie atrybuty występujące w danej ZF.
Pewne zależności mogą pozostać nie przydzielone  takich
przypadków chcemy uniknąć, gdyż tracimy wtedy informacje o
schemacie BD.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 15 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Własności dekompozycji
Twierdzenie 7
Niech S(B1, . . . , Bn) i T (C1, . . . , Cm) bedą dekompozycją
R(A1, . . . , Ak). Dekompozycja nie traci informacji o relacji R jeśli jest
spełniony przynajmniej jeden z warunków:
{B1, . . . , Bn} )" {C1, . . . , Cm} {B1, . . . , Bn},
{B1, . . . , Bn} )" {C1, . . . , Cm} {C1, . . . , Cm}.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 16 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Własności dekompozycji
Dekompozycje możemy wykonać gdy:
eliminuje to anomalie omówione wcześniej,
możemy odtworzyć pierwotną relację z nowych relacji (nie tracimy
informacji),
dowolne relacje spełniające zależności funkcyjne obowiązujące w
zdekomponowanych relacjach można połączyć w relację
stanowiącą przypadek relacji oryginalnej.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 17 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Możemy założyć, że wydawnictwo ma jedną siedzibę a więc
występuje zależność funkcyjna: wydawca adres.
Podobnie, jeśli założymy, że w danym roku tylko jedno
wydawnictwo wydaje książkę o danym tytule, to otrzymamy
zależność funkcyjną: tytul, rok wydawca.
Zauważmy, że powyższe zależności pociągają za sobą zależność:
tytul, rok adres.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 18 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności funkcyjne
Fakt 8
Zależność funkcyjna A1 . . . An B1 . . . Bm jest równoważna zbiorowi
zależności A1 . . . An Bi, dla i m.
Dlatego od teraz zakładamy, że każda ZF ma tylko jeden atrybut po
prawej stronie.
Fakt 9
Jeśli A1 . . . An Bi, dla i m, oraz B1 . . . Bm C, to A1 . . . An C.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 19 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności funkcyjne
Mając dany zbiór zależności funkcyjnych F = {F1, . . . , Fn} oraz zbiór
atrybutów A1, . . . , Am możemy obliczyć zbiór wszystkich atrybutów X
zależnych funkcyjnie od A1, . . . , Am:
X �! {A1, . . . , Am}
while isnieją B1, . . . , Bk " X oraz C " X ( (B1 . . . Bk C) " F) do
X �! X *" {C}
end while
Definicja 10
Dla ustalonego F, zbiór atrybutów zależnych funkcynjnie od A1, . . . , An
będziemy oznaczali przez {A1, . . . , An}+.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 20 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Klucze
Definicja 11
Zbiór atrybutów {A1, . . . , An} jest kluczem w relacji R jeśli
1
{A1, . . . , An}+ to zbiór wszystkich atrybutów R,
2
żaden właściwy podzbiór zbioru {A1, . . . , A - n} nie ma powyższej
własności.
Definicja 12
Jeśli zbiór atrybutów X zawiera klucz relacji R to mówimy, że X jest
nadkluczem R.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 21 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Postać normalna Boyce a Coda  BCNF
Definicja 13
Relacja R jest w BCNF jeśli dla jej każdej nietrywialnej ZF,
A1 . . . An A, zbiór {A1, . . . , An} jest nadkluczem R.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 22 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Relacja nie jest w BCNF bo atrybut wydawca nie jest kluczem w relacji
Ksiazki ale wystepuje zaleznosc wydawca adres.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 23 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do BCNF
Jeśli relacja R(A1, . . . , An) nie jest w BCNF to istnieją zbiór
atrybutów X oraz atrybut A takie, że
X nie jest nadkluczem w R,
X A jest nietrywialną zależnością funkcyjną.
Możemy wtedy zdekomponować R do relacji S zawierjącej
+
atrybuty X oraz T zawierającą atrybuty X oraz atrybuty R spoza
+
X .
Powstałe relacje  dziedziczą zależnosci funkcyjne z R
Jeśli powstałe relacje nie są w BCNF, możemy wykonać także ich
dekompozycję.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 24 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
imie nazwisko tytul rok wydawca adres
S. Cenckiewicz SB a Lech 2009 Arcana Kraków
P. Gontarczyk SB a Lech 2009 Arcana Kraków
A. Nowak Od Polski do 2010 Arcana Kraków
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a Warszawa
Możemy zdekomponować Ksiazki na Wydanie(imie, nazwisko, tytul,
rok, wydawca) oraz Wydawnictwo(wydawca, adres).
imie nazwisko tytul rok wydawca
S. Cenckiewicz SB a Lech 2009 Arcana
P. Gontarczyk SB a Lech 2009 Arcana
A. Nowak Od Polski do 2010 Arcana
S. Cenckiewicz Długie ramię 2011 Zysk i Sk-a
wydawca adres
Arcana Kraków
Zysk i Sk-a Warszawa
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 25 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do BCNF
Twierdzenie 14
Niech X A jest nietrywialną zależnością funkcyjną w R(A) oraz
niech S i T są dekompozycją R taką, że S = ĄX +(R) i T = ĄY (R), dla
+
Y = X *" ({A} \ X ). Wtedy
S T = R.
Możemy odtworzyć relację R z dwóch relacji, na które rozłozylismy R
podczas algorytmu dekompozycji.
Jest tak dlatego, że każdej krotce z T odpowiada dokładnie jedna
krotka z S.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 26 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Problemy z BCNF  przykład
Rozważmy relację Sieci(sprzedawca, miasto, marka), o której
założymy, że
w każdym mieście jest najwyżej jeden sprzedaca danej marki,
sprzedawca ma siedzibę dokładnie w jednym mieście (nie tworzy
sieci).
Możemy opisać to jako zależności funkcyjne
miasto, marka sprzedawca,
sprzedawca miasto.
Uwaga. Sprzedawcy mogą sprzedawać różne marki ale na każdą
markę mają monopol w swoim mieście.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 27 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Problemy z BCNF  przykład
Sieci(sprzedawca, miasto, marka):
miasto, marka sprzedawca,
sprzedawca miasto.
Klucze tej relacji to:
miasto, marka;
sprzedawca, marka;
Możemy znalez
ć ZF: sprzedawca miasto, która sugeruje
dekompozycje na relacje
S(sprzedawca, miasto), ZF: sprzedawca miasto.
T (sprzedawca, marka).
Gdzie jest problem?
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 28 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Problemy z BCNF  przykład
Sieci(sprzedawca, miasto, marka):
miasto, marka sprzedawca,
sprzedawca miasto.
Dekompozycja:
S(sprzedawca, miasto), ZF: sprzedawca miasto.
T (sprzedawca, marka).
Chcielibyśmy, żeby dowolne relacje S i T spełniające wyliczone ZF-y
dały się skomponować w relację Sieci.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 29 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Problemy z BCNF  przykład
Chcielibyśmy, żeby dowolne relacje S i T spełniające wyliczone ZF-y
dały się skomponować w relację Sieci.
S(sprzedawca, miasto), ZF: sprzedawca miasto.
T (sprzedawca, marka).
Rozważmy
sprzedawca miasto sprzedawca miasto
Kulczyk Poznan Kulczyk audi
Solorz Poznan Solorz audi
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 30 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Problemy z BCNF  przykład
sprzedawca miasto sprzedawca marka
Kulczyk Poznan Kulczyk audi
Solorz Poznan Solorz audi
Połączenie tych dwóch relacji po atrybucie sprzedawca daje
sprzedawca miasto marka
Kulczyk Poznan audi
Solorz Poznan audi
Nie jest zachowana ZF: miasto, marka sprzedawca!
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 31 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Trzecia postać normalna  3NF
Definicja 15
Relacja R o zależnościach funkcyjnych F jest w trzeciej postaci
normalnej (3NF) jeśli dla dowolnej ZF, A1 . . . Ak B, którą można
wyprowadzić z F zachodzi przynajmniej jeden warunek:
zbiór A1, . . . , Ak jest nadkluczem R,
B wchodzi w skład pewnego klucza w R.
W warunku dla 3NF ograniczamy zbiór ZF, które  psują postać w
stosunku do BCNF.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 32 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do 3NF
Definicja 16
Niech F bedzie zbiorem zależności funkcyjnych dla relacji R. Zbiór
zależności funkcyjnych G jest bazą dla F jeśli każda ZF z F wynika z
zależności funkcyjnych w G i nic więcej nie można wywnioskować z G.
Zbiór G jest bazą minimalną dla F jeśli
G jest bazą dla F,
usunięcie dowolnego G " G powoduje, że nowy zbiór ZF przestaje
być bazą,
dla dowolnej A1 . . . Ak B " G usunięcie jednego z Ai powoduje,
że nowy zbiór przestaje być bazą.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 33 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do 3NF
Algorytm dekompozycji R i zależności funkcyjnych F do 3NF.
1
wyznacz bazę minimalną G dla F,
2
dla każdej X A " G tworzymy nową relację o atrybutach
X *" {A}.
3
jesli nie stworzyliśmy relacji, która zawiera klucz R to dodajemy
taką relację.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 34 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do 3NF  przyklad
Rozważmy relację Samochody(wlasciciel, samochod, pojemnosc) oraz
zależności
wlasciciel samochod,
samochod pojemnosc,
wlasciciel pojemnosc.
wlasciciel samochod pojemnosc
Kowalski audi 1.8
Nowak audi 1.8
Turek ford 1.8
Gołąb fiat 1.4
Szpak trabant 1.4
Jedynym kluczem tej relacji jest atrybut wlasciciel.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 35 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do 3NF
Relację Samochody rozkładamy na
wlasciciel samochod
samochod pojemnosc
Kowalski audi
audi 1.8
Nowak audi
ford 1.8
Turek ford
fiat 1.4
Gołąb fiat
trabant 1.4
Szpak trabant
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 36 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Rozważmy relację Filmy(aktor, adres, tytul).
aktor adres tytul
Pitt L.A Mr & Mrs Smith
Pitt Londyn Mr & Mrs Smith
Jolie Paryż Rybki z Ferajny
Jolie L.A Rybki z Ferajny
Jolie Paryż Mr & Mrs Smith
Jolie L.A Mr & Mrs Smith
W tej relacji nie zachodzi żadna nietrywialna ZF.
Ale dodając nowy film z Pittem należy dodać dwie krotki. Nie ma
powodu, żeby opuścić jeden z adresów Pitta. Podobnie usuwająć
aktora z filmu lub adres aktora trzeba usunąć wiele krotek.
W relacji występują anomalie ale jest ona w BCNF.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 37 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności wielowartościowe
Niech A1, . . . , An i B1, . . . , Bk to atrybuty relacji R. Zależność
wielowartościowa pomiędzy A1, . . . , An i B1, . . . , Bk zachodzi jeśli po
wybraniu krotek z R o ustalonej wartości atrybutów A1, . . . , An,
wartości atrybutów B1, . . . , Bk nie zależą od pozostałych atrybutów
relacji.
aktor adres tytul
Pitt L.A Mr & Mrs Smith
Pitt Londyn Mr & Mrs Smith
Jolie Paryż Rybki z Ferajny
Jolie L.A Rybki z Ferajny
Jolie Paryż Mr & Mrs Smith
Jolie L.A Mr & Mrs Smith
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 38 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności wielowartościowe
Definicja 17
Niech A1, . . . , An i B1, . . . , Bk to atrybuty relacji R i niech C1, . . . , Cm to
pozostałe atrybuty R.
Zależność wielowartościowa w R pomiędzy A1, . . . , An i B1, . . . , Bk,
ozn. A1 . . . An B1 . . . Bk, zachodzi jeśli dla każdej pary krotek
t, s " R takich, że
t(A1, . . . , An) = s(A1, . . . , An)
istnieje krotka v " R taka, że
v(A1, . . . , An) = s(A1, . . . , An) (= t(A1, . . . , An)),
v(B1, . . . , Bk) = s(B1, . . . , Bk),
v(C1, . . . , Cm) = s(C1, . . . , Cm).
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 39 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności wielowartościowe
Fakt 18
Jeśli A1 . . . An B1 . . . Bk, to A1 . . . An B1 . . . Bk.
Fakt 19
Niech A1, . . . , An i B1, . . . , Bk to atrybuty relacji R i niech C1, . . . , Cm to
pozostałe atrybuty R. Jeśli A1 . . . An B1 . . . Bk, to
A1 . . . An C1 . . . Cm
Fakt 20
Jeśli A1, . . . , An, B1, . . . , Bk to wszystkie atrybuty relacji R, to zachodzi
A1 . . . An B1 . . . Bk.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 40 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Zależności wielowartościowe
Definicja 21
Zależność wielowartościowa A1 . . . An B1 . . . Bk jest trywialna jeśli
{B1, . . . , Bk} ą" {A1, . . . , An} lub A1, . . . , An, B1, . . . , Bk to wszystkie
atrybuty relacji.
Fakt 22
Dla każdej relacji R zachodzą wszystkie trywialne zależności
wielowartościowe.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 41 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Czwarta postać normalna  4NF
Definicja 23
Relacja R jest w czwartej postaci normalnej (4NF) jeśli dla dowolnej
nietrywialnej zależności wielowartościowej A1 . . . An B1 . . . Bk w R,
zbiór atrybutów {A1, . . . , An} jest nadkluczem.
Obserwacja. Warunek na 4NF jest powtórzeniem warunku dla BCNF
ale dla zależności wielowartościowych.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 42 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Czwarta postać normalna  4NF
Ponieważ każda zależności funkcyjna jest też wielowartościową, to z
ostatniej obserwacji wynika.
Fakt 24
Jeśli relacja R jest w 4NF to jest też w BCNF.
Zachodzą więc nastepujące wynikania:
R jest w 4NF =�! R jest w BCNF =�! R jest w 3NF.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 43 / 52
Bazy Wyszyńskiego, szósty Normalizacja
4NF  przykład dekompozycji
Relację Filmy
aktor adres tytul
Pitt L.A Mr & Mrs Smith
Pitt Londyn Mr & Mrs Smith
Jolie Paryż Rybki z Ferajny
Jolie L.A Rybki z Ferajny
Jolie Paryż Mr & Mrs Smith
Jolie L.A Mr & Mrs Smith
możemy zdekomponować używając zależności aktor adres do
Adresy(aktor, adres) i Wystapil(aktor, tytul).
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 44 / 52
Bazy Wyszyńskiego, szósty Normalizacja
4NF  przykład dekompozycji
Adresy: Wystapil:
aktor adres aktor tytul
Pitt L.A Pitt Mr & Mrs Smith
Pitt Londyn Jolie Mr & Mrs Smith
Jolie L.A Jolie Rybki z Ferajny
Jolie Paryż
Oryginalną relację Filmy możemy odtworzyć jako Adresy Wystapil
czyli
select A . aktor , A . adres , W. t y t u l
from Adresy A, Wystapil W
where A . a k t o r = W. a k t o r ;
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 45 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Dekompozycja do 4NF
Aby zdekomponować relację R do 4NF musimy:
1
znalez
ć nietrywialną zależność wielowartościową
A1 . . . An B1 . . . Bk taką, że {A1, . . . , An} nie jest nadkluczem R,
2
jeśli C1, . . . , Cm to pozostałe atrybuty R, to dekomponujemy R na:
S(A1, . . . , An, B1, . . . , Bk )
T (A1, . . . , An, C1, . . . , Cm).
3
powtarzamy dekompozycję dla nowych relacji.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 46 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Do zrozumienia
na czym polegają anomalie, zależności funkcyjne, klucze, 1NF, 2NF,
dekompozycja, 3NF
może nawet:
BCNF, zależnosci wielowartościowe, 4NF, ...
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 47 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Chcemy stworzyć BD dla sklepu "Mydło i powidło". Możemy
zdefiniować jedną tabelę Zamówienia o jednej kolumnie zawierającą
wartości takie jak np.
dane klienta  imię, nazwisko, jego id, ...
listę przedmiotów które zakupił, nazwy, ilość, ceny, kwota zakupu,
...
dane do rachunku i dane do wysyłki.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 48 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Możemy zdefiniować jedną tabelę Zamówienia o jednej kolumnie
zawierającą wartości takie jak np.
Adam Abacki, adres do rachunku, adres do wysyłki, nożyczki, kod
nożyczek, ilość, cena, VAT, klej, kod kleju, ilość, cena, VAT, wartość
zakupów, data.
Taki schemat nie jest w 1NF, jest prosty lecz trudno wydobyć z niego
informacje. Dlatego, rozdzielamy dane na oddzielne kolumny.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 49 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Ponieważ ilość artykułów w zamówieniu może być różna a mamy
tylko stałą liczbę kolumn musimy stworzyć dwie tabele:
Zamówienia: id_zamowienia (PK), data, id_klienta, imie, nazwisko,
adres do rachunku, adres do wysyłki.
Towary: id_zamowienia (PK, FK), id_artykulu (PK), ilosc, cena,
VAT, wartość zakupów.
Jak tylko rozdzielimy dane na odrębne atrybuty, staniemy przed
pytaniem, co może być kluczem w naszej tabeli.
Zauważmy, że częśc danych w tabeli Towary zależy tylko od
id_artykulu (cena, VAT). Schemat BD nie jest w 2NF bo
id_artykulu to tylko część klucza.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 50 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Mamy tabele:
Zamówienia: id_zamowienia (PK), data, imie, nazwisko, adres do
rachunku, adres do wysyłki.
Towary: id_zamowienia (PK, FK), id_artykulu (PK), ilosc, cena,
VAT, wartość zakupów.
Aby uzyskać 2NF rozdzielamy tabelę Towary na
Towary_zamowione: id_zamowienia (PK, FK), data, imie,
nazwisko, adres do rachunku, adres do wysyłki, id_artykulu (PK,
FK), ilosc, wartosc zakupów.
Asortyment (czyli towary, którymi sklep handluje): id_artykułu
(PK), cena, VAT.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 51 / 52
Bazy Wyszyńskiego, szósty Normalizacja
Przykład
Zamówienia: id_zamowienia (PK), data, id_klienta, imie,
nazwisko, adres do rachunku, adres do wysyłki.
Pola imie, nazwisko, adres do rachunku zależą tylko od id_klienta,
który nie jest kluczem w tabeli. Aby uzyskać 3NF tworzymy nową
tabelę.
Zamówienia: id_zamowienia (PK), data, id_klienta (FK), adres do
wysyłki.
Klienci: id_klienta (PK), imie, nazwisko, adres do rachunku.
Konrad Zdanowski ( Uniwersytet Kardynała Stefanadanych  wykładWarszawa) modelu bazy danych 52 / 52
Bazy Wyszyńskiego, szósty Normalizacja