Bazy danych – wykład szósty

Normalizacja modelu bazy danych

Konrad Zdanowski

Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

1 / 52

Przykład

Rozwa˙zmy tabel ˛e 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 ˛e ...

2011

Zysk i Sk-a

Warszawa

W tabeli wyst ˛epuje redundancja informacji.

Skutkuje to trudno´sciami przy dodawaniu, aktualizowaniu lub
usuwaniu krotek z tabeli.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

2 / 52

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 ˛e

2011

Zysk i Sk-a

Warszawa

Dodanie krotki (P., Zyzak, ..., Arcana, Warszawa) rozspójni nam
informacje w tabeli.

Wydawnictwo Arcana b ˛edzie miało dwa adresy.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

3 / 52

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 ˛e

2011

Zysk i Sk-a

Warszawa

Modyfkuj ˛

ac adres wydawnictwa musimy zrobi´c to we wszystkich

krotkach, w których ono wyst ˛epuje

Zmiana jednej informacji wymaga zmiany wielu krotek w bazie
danych

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

4 / 52

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 ˛e

2011

Zysk i Sk-a

Warszawa

Usuwaj ˛

ac ksi ˛

a˙zk˛e Długie rami ˛e Moskwy stracimy wszystkie

informacje o wydawnictwie Zysk i Sk-a.

Usuwaj ˛

a´c ksi ˛

a˙zk˛e tracimy informacje o wydawnictwie.

Jedna krotka zawiera dwie, niezale˙zne od siebie informacje. Nie
mo˙zna usun ˛

a´c jednej nie usuwaj ˛

ac drugiej.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

5 / 52

Anomalie projektu BD

Nadmiarowo´s´c – powtarzanie si ˛e wiele razy tej samej informacji.

Anomalie aktualizacji – modyfikacja jednej informacji mo˙ze
pomina´c krotki.

Anomalie usuwania – usuni ˛ecie krotek pozbawia nas informacji,
które chcieliby´smy zachowa´c.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

6 / 52

Cechy optymalnego modelu BD

Ta sama informacja w BD nie powtarza si ˛e wiele razy.

Informacje w ró˙znych krotkach nie s ˛

a od siebie zale˙zne.

Informacja w jednej krotce jest „atomowa”.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

7 / 52

Cechy optymalnego modelu BD

Podczas procesu normalizacji usuwamy anomalie, które mog ˛

a

wyst ˛epowa´c w BD.

Wyró˙znimy pewne postacie normalne oraz omówimy jak je
uzyska´c.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

8 / 52

Pierwsza posta´c normalna

Definicja 1

Relacja jest w

pierwszej postaci normalnej

(1NF), je´sli wszystkie

atrybuty tej relacji maj ˛

a atomowe typy danych.

Pierwsza posta´c normalna wyklucza sytuacj ˛e, w której typ danych
danego atrybutu to zbiór warto´sci, 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 Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

9 / 52

Druga posta´c normalna

Definicja 2

Relacja jest w

drugiej postaci normalnej

(2NF), je´sli jest w 1NF oraz

˙zaden atrybut który nie wchodzi w skład klucza nie zale˙zy funkcyjnie

od atrybutów b ˛ed ˛

acych wła´sciwym podzbiorem klucza.

Druga posta´c normalna wyklucza sytuacj ˛e, w której atrybut X nie
wchodz ˛

acy w skład klucza zale˙zy funkcyjnie od wła´sciwej cz ˛e´sci

klucza. Je´sli tak by było, to mo˙zemy stworzy´c now ˛

a tabel ˛e z t ˛

a

zale˙zno´sci ˛

a usuwaj ˛

ac X z oryginalnej tabeli.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

10 / 52

Dekompozycja relacji

Definicja 3

Rozwa˙zmy relacj ˛e R(A

1

, . . . ,

A

n

)

oraz zbiory atrybutów

{B

1

, . . . ,

B

k

} ∪ {C

1

, . . . ,

C

m

} = {A

1

, . . . ,

A

n

}.

Dekompozycja R na relacje S(B

1

, . . . ,

B

k

)

i T (C

1

, . . . ,

C

m

)

zachodzi

gdy

S = π

B

1

,...,

B

k

(

R) oraz T = π

C

1

,...,

C

m

(

R).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

11 / 52

Przykład

Relacj ˛e Ksiazki mo˙zemy zdekomponowa´c 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 ˛e

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 ˛e

2011

Zysk i Sk-a

wydawca

adres

Arcana

Kraków

Zysk i Sk-a

Warszawa

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

12 / 52

Dekompozycja relacji

Maj ˛

ac dan ˛

a dekompozycj ˛e R(A

1

, . . . ,

A

n

)

na S(B

1

, . . . ,

B

k

)

i

T (C

1

, . . . ,

C

m

)

mo˙zemy zdefiniowa´c zło˙zenie relacji S i T .

Definicja 4

Niech D

1

, . . . ,

D

r

b ˛edzie cz ˛e´sci ˛

a wspóln ˛

a B

1

, . . . ,

B

k

i C

1

, . . . ,

C

m

.

Mo˙zemy zdefiniowa´c zł ˛

aczenie tych relacji

R

0

=

S o

n

D

1

,...,

D

r

T .

Relacj ˛e R

0

tworzymy jako S

natural join T (czyli S join T on

D

1

, . . . ,

D

r

).

Ale czy R

0

=

R?

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

13 / 52

Zale˙zno´sci funkcyjne

Definicja 5

Atrybuty B

1

, . . . ,

B

m

s ˛

a

zale˙zne funkcyjnie

od atrybutów A

1

, . . . ,

A

n

w

relacji R je´sli dowolne dwie krotki t, t

0

z relacji R, które zgadzaj ˛

a si ˛e na

atrybutach A

1

, . . . ,

A

n

musz ˛

a zgadza´c si ˛e na atrybutach B

1

, . . . ,

B

m

.

Zale˙zno´s´c funkcyjn ˛

a oznaczamy przez A

1

. . .

A

n

→ B

1

. . .

B

m

.

Definicja 6

Zale˙zno´sc funkcyjn ˛

a A

1

. . .

A

n

→ A nazywamy

trywialn ˛

a

je´sli

A ∈ {A

1

, . . . ,

A

n

}.

Zale˙zno´s´c funkcyjn ˛

a nale˙zy traktowa´c jako zale˙zno´s´c dotycz ˛

ac ˛

a

schematu relacji a nie jej szczególnego wyst ˛

apienia.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

14 / 52

Zale˙zno´sci funkcyjne

Dekomponuj ˛

ac relacj ˛e R na relacje S i T dzielimy zbiór zale˙zno´sci

funkcyjnych relacji R na dwa zbiory dla S i T w zale˙zno´sci od tego,
która z relacji posiada wszystkie atrybuty wyst ˛epuj ˛

ace w danej ZF.

Pewne zale˙zno´sci mog ˛

a pozosta´c nie przydzielone – takich

przypadków chcemy unikn ˛

a´c, gdy˙z tracimy wtedy informacje o

schemacie BD.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

15 / 52

Własno´sci dekompozycji

Twierdzenie 7

Niech S(B

1

, . . . ,

B

n

)

i T (C

1

, . . . ,

C

m

)

bed ˛

a dekompozycj ˛

a

R(A

1

, . . . ,

A

k

)

. Dekompozycja nie traci informacji o relacji R je´sli jest

spełniony przynajmniej jeden z warunków:

{B

1

, . . . ,

B

n

} ∩ {C

1

, . . . ,

C

m

} → {B

1

, . . . ,

B

n

},

{B

1

, . . . ,

B

n

} ∩ {C

1

, . . . ,

C

m

} → {C

1

, . . . ,

C

m

}.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

16 / 52

Własno´sci dekompozycji

Dekompozycje mo˙zemy wykona´c gdy:

eliminuje to anomalie omówione wcze´sniej,

mo˙zemy odtworzy´c pierwotn ˛

a relacj ˛e z nowych relacji (nie tracimy

informacji),

dowolne relacje spełniaj ˛

ace zale˙zno´sci funkcyjne obowi ˛

azuj ˛

ace w

zdekomponowanych relacjach mo˙zna poł ˛

aczy´c w relacj ˛e

stanowi ˛

ac ˛

a przypadek relacji oryginalnej.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

17 / 52

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 ˛e

2011

Zysk i Sk-a

Warszawa

Mo˙zemy zało˙zy´c, ˙ze wydawnictwo ma jedn ˛

a siedzib ˛e a wi ˛ec

wyst ˛epuje zale˙zno´s´c funkcyjna: wydawca → adres.

Podobnie, je´sli zało˙zymy, ˙ze w danym roku tylko jedno
wydawnictwo wydaje ksi ˛

a˙zk˛e o danym tytule, to otrzymamy

zale˙zno´s´c funkcyjn ˛

a: tytul, rok → wydawca.

Zauwa˙zmy, ˙ze powy˙zsze zale˙zno´sci poci ˛

agaj ˛

a za sob ˛

a zale˙zno´s´c:

tytul, rok → adres.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

18 / 52

Zale˙zno´sci funkcyjne

Fakt 8

Zale˙zno´s´c funkcyjna A

1

. . .

A

n

→ B

1

. . .

B

m

jest równowa˙zna zbiorowi

zale˙zno´sci A

1

. . .

A

n

→ B

i

, dla i ¬ m.

Dlatego od teraz zakładamy, ˙ze ka˙zda ZF ma tylko jeden atrybut po
prawej stronie.

Fakt 9

Je´sli A

1

. . .

A

n

→ B

i

, dla i ¬ m, oraz B

1

. . .

B

m

→ C, to A

1

. . .

A

n

→ C.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

19 / 52

Zale˙zno´sci funkcyjne

Maj ˛

ac dany zbiór zale˙zno´sci funkcyjnych F = {F

1

, . . . ,

F

n

} oraz zbiór

atrybutów A

1

, . . . ,

A

m

mo˙zemy obliczy´c zbiór wszystkich atrybutów X

zale˙znych funkcyjnie od A

1

, . . . ,

A

m

:

X ← {A

1

, . . . ,

A

m

}

while isniej ˛

a B

1

, . . . ,

B

k

∈ X oraz C 6∈ X ( (B

1

. . .

B

k

→ C) ∈ F ) do

X ← X ∪ {C}

end while

Definicja 10

Dla ustalonego F , zbiór atrybutów zale˙znych funkcynjnie od A

1

, . . . ,

A

n

b ˛edziemy oznaczali przez {A

1

, . . . ,

A

n

}

+

.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

20 / 52

Klucze

Definicja 11

Zbiór atrybutów {A

1

, . . . ,

A

n

} jest kluczem w relacji R je´sli

1

{A

1

, . . . ,

A

n

}

+

to zbiór wszystkich atrybutów R,

2

˙zaden wła´sciwy podzbiór zbioru {A

1

, . . . ,

A − n} nie ma powy˙zszej

własno´sci.

Definicja 12

Je´sli zbiór atrybutów X zawiera klucz relacji R to mówimy, ˙ze X jest
nadkluczem R.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

21 / 52

Posta´c normalna Boyce’a–Coda — BCNF

Definicja 13

Relacja R jest w BCNF je´sli dla jej ka˙zdej nietrywialnej ZF,
A

1

. . .

A

n

→ A, zbiór {A

1

, . . . ,

A

n

} jest nadkluczem R.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

22 / 52

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 ˛e

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 Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

23 / 52

Dekompozycja do BCNF

Je´sli relacja R(A

1

, . . . ,

A

n

)

nie jest w BCNF to istniej ˛

a zbiór

atrybutów X oraz atrybut A takie, ˙ze

I

X nie jest nadkluczem w R,

I

X → A jest nietrywialn ˛

a zale˙zno´sci ˛

a funkcyjn ˛

a.

Mo˙zemy wtedy zdekomponowa´c R do relacji S zawierj ˛

acej

atrybuty X

+

oraz T zawieraj ˛

ac ˛

a atrybuty X oraz atrybuty R spoza

X

+

.

Powstałe relacje „dziedzicz ˛

a” zale˙znosci funkcyjne z R

Je´sli powstałe relacje nie s ˛

a w BCNF, mo˙zemy wykona´c tak˙ze ich

dekompozycj ˛e.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

24 / 52

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 ˛e

2011

Zysk i Sk-a

Warszawa

Mo˙zemy zdekomponowa´c 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 ˛e

2011

Zysk i Sk-a

wydawca

adres

Arcana

Kraków

Zysk i Sk-a

Warszawa

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

25 / 52

Dekompozycja do BCNF

Twierdzenie 14

Niech X → A jest nietrywialn ˛

a zale˙zno´sci ˛

a funkcyjn ˛

a w R(A) oraz

niech S i T s ˛

a dekompozycj ˛

a R tak ˛

a, ˙ze S = π

X

+

(

R) i T = π

Y

(

R), dla

Y = X ∪ ({A} \ X

+

)

. Wtedy

S o

n T = R.

Mo˙zemy odtworzy´c relacj ˛e R z dwóch relacji, na które rozłozylismy R
podczas algorytmu dekompozycji.

Jest tak dlatego, ˙ze ka˙zdej krotce z T odpowiada dokładnie jedna
krotka z S.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

26 / 52

Problemy z BCNF – przykład

Rozwa˙zmy relacj ˛e Sieci(sprzedawca, miasto, marka), o której
zało˙zymy, ˙ze

w ka˙zdym mie´scie jest najwy˙zej jeden sprzedaca danej marki,

sprzedawca ma siedzib ˛e dokładnie w jednym mie´scie (nie tworzy
sieci).

Mo˙zemy opisa´c to jako zale˙zno´sci funkcyjne

miasto, marka → sprzedawca,

sprzedawca → miasto.

Uwaga. Sprzedawcy mog ˛

a sprzedawa´c ró˙zne marki ale na ka˙zd ˛

a

mark˛e maj ˛

a monopol w swoim mie´scie.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

27 / 52

Problemy z BCNF – przykład

Sieci(sprzedawca, miasto, marka):

miasto, marka → sprzedawca,

sprzedawca → miasto.

Klucze tej relacji to:

miasto, marka;

sprzedawca, marka;

Mo˙zemy znale´z´c 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 Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

28 / 52

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´smy, ˙zeby dowolne relacje S i T spełniaj ˛

ace wyliczone ZF-y

dały si ˛e skomponowa´c w relacj ˛e Sieci.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

29 / 52

Problemy z BCNF – przykład

Chcieliby´smy, ˙zeby dowolne relacje S i T spełniaj ˛

ace wyliczone ZF-y

dały si ˛e skomponowa´c w relacj ˛e Sieci.

S(sprzedawca, miasto), ZF: sprzedawca → miasto.

T (sprzedawca, marka).

Rozwa˙zmy

sprzedawca

miasto

Kulczyk

Poznan

Solorz

Poznan

sprzedawca

miasto

Kulczyk

audi

Solorz

audi

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

30 / 52

Problemy z BCNF – przykład

sprzedawca

miasto

Kulczyk

Poznan

Solorz

Poznan

sprzedawca

marka

Kulczyk

audi

Solorz

audi

Poł ˛

aczenie 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 Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

31 / 52

Trzecia posta´c normalna – 3NF

Definicja 15

Relacja R o zale˙zno´sciach funkcyjnych F jest w

trzeciej postaci

normalnej

(3NF) je´sli dla dowolnej ZF, A

1

. . .

A

k

→ B, któr ˛

a mo˙zna

wyprowadzi´c z F zachodzi przynajmniej jeden warunek:

zbiór A

1

, . . . ,

A

k

jest nadkluczem R,

B wchodzi w skład pewnego klucza w R.

W warunku dla 3NF ograniczamy zbiór ZF, które „psuj ˛

a” posta´c w

stosunku do BCNF.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

32 / 52

Dekompozycja do 3NF

Definicja 16

Niech F bedzie zbiorem zale˙zno´sci funkcyjnych dla relacji R. Zbiór
zale˙zno´sci funkcyjnych G jest baz ˛

a dla F je´sli ka˙zda ZF z F wynika z

zale˙zno´sci funkcyjnych w G i nic wi ˛ecej nie mo˙zna wywnioskowa´c z G.

Zbiór G jest

baz ˛

a minimaln ˛

a

dla F je´sli

G jest baz ˛

a dla F ,

usuni ˛ecie dowolnego G ∈ G powoduje, ˙ze nowy zbiór ZF przestaje
by´c baz ˛

a,

dla dowolnej A

1

. . .

A

k

→ B ∈ G usuni ˛ecie jednego z A

i

powoduje,

˙ze nowy zbiór przestaje by´c baz ˛

a.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

33 / 52

Dekompozycja do 3NF

Algorytm dekompozycji R i zale˙zno´sci funkcyjnych F do 3NF.

1

wyznacz baz ˛e minimaln ˛

a G dla F ,

2

dla ka˙zdej X → A ∈ G tworzymy now ˛

a relacj ˛e o atrybutach

X ∪ {A}.

3

jesli nie stworzyli´smy relacji, która zawiera klucz R to dodajemy
tak ˛

a relacj ˛e.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

34 / 52

Dekompozycja do 3NF – przyklad

Rozwa˙zmy relacj ˛e Samochody(wlasciciel, samochod, pojemnosc) oraz
zale˙zno´sci

wlasciciel → samochod,

samochod → pojemnosc,

wlasciciel → pojemnosc.

wlasciciel

samochod

pojemnosc

Kowalski

audi

1.8

Nowak

audi

1.8

Turek

ford

1.8

Goł ˛

ab

fiat

1.4

Szpak

trabant

1.4

Jedynym kluczem tej relacji jest atrybut wlasciciel.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

35 / 52

Dekompozycja do 3NF

Relacj ˛e Samochody rozkładamy na

wlasciciel

samochod

Kowalski

audi

Nowak

audi

Turek

ford

Goł ˛

ab

fiat

Szpak

trabant

samochod

pojemnosc

audi

1.8

ford

1.8

fiat

1.4

trabant

1.4

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

36 / 52

Przykład

Rozwa˙zmy relacj ˛e Filmy(aktor, adres, tytul).

aktor

adres

tytul

Pitt

L.A

Mr & Mrs Smith

Pitt

Londyn

Mr & Mrs Smith

Jolie

Pary˙z

Rybki z Ferajny

Jolie

L.A

Rybki z Ferajny

Jolie

Pary˙z

Mr & Mrs Smith

Jolie

L.A

Mr & Mrs Smith

W tej relacji nie zachodzi ˙zadna nietrywialna ZF.

Ale dodaj ˛

ac nowy film z Pittem nale˙zy doda´c dwie krotki. Nie ma

powodu, ˙zeby opu´sci´c jeden z adresów Pitta. Podobnie usuwaj ˛

a´c

aktora z filmu lub adres aktora trzeba usun ˛

a´c wiele krotek.

W relacji wyst ˛epuj ˛

a anomalie ale jest ona w BCNF.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

37 / 52

Zale˙zno´sci wielowarto´sciowe

Niech A

1

, . . . ,

A

n

i B

1

, . . . ,

B

k

to atrybuty relacji R. Zale˙zno´s´c

wielowarto´sciowa pomi ˛edzy A

1

, . . . ,

A

n

i B

1

, . . . ,

B

k

zachodzi je´sli po

wybraniu krotek z R o ustalonej warto´sci atrybutów A

1

, . . . ,

A

n

,

warto´sci atrybutów B

1

, . . . ,

B

k

nie zale˙z ˛

a od pozostałych atrybutów

relacji.

aktor

adres

tytul

Pitt

L.A

Mr & Mrs Smith

Pitt

Londyn

Mr & Mrs Smith

Jolie

Pary˙z

Rybki z Ferajny

Jolie

L.A

Rybki z Ferajny

Jolie

Pary˙z

Mr & Mrs Smith

Jolie

L.A

Mr & Mrs Smith

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

38 / 52

Zale˙zno´sci wielowarto´sciowe

Definicja 17

Niech A

1

, . . . ,

A

n

i B

1

, . . . ,

B

k

to atrybuty relacji R i niech C

1

, . . . ,

C

m

to

pozostałe atrybuty R.

Zale˙zno´s´c wielowarto´sciowa

w R pomi ˛edzy A

1

, . . . ,

A

n

i B

1

, . . . ,

B

k

,

ozn. A

1

. . .

A

n

 B

1

. . .

B

k

, zachodzi je´sli dla ka˙zdej pary krotek

t, s ∈ R takich, ˙ze

t(A

1

, . . . ,

A

n

) =

s(A

1

, . . . ,

A

n

)

istnieje krotka v ∈ R taka, ˙ze

v (A

1

, . . . ,

A

n

) =

s(A

1

, . . . ,

A

n

) (=

t(A

1

, . . . ,

A

n

))

,

v (B

1

, . . . ,

B

k

) =

s(B

1

, . . . ,

B

k

)

,

v (C

1

, . . . ,

C

m

) =

s(C

1

, . . . ,

C

m

)

.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

39 / 52

Zale˙zno´sci wielowarto´sciowe

Fakt 18

Je´sli A

1

. . .

A

n

→ B

1

. . .

B

k

, to A

1

. . .

A

n

 B

1

. . .

B

k

.

Fakt 19

Niech A

1

, . . . ,

A

n

i B

1

, . . . ,

B

k

to atrybuty relacji R i niech C

1

, . . . ,

C

m

to

pozostałe atrybuty R. Je´sli A

1

. . .

A

n

 B

1

. . .

B

k

, to

A

1

. . .

A

n

 C

1

. . .

C

m

Fakt 20

Je´sli A

1

, . . . ,

A

n

,

B

1

, . . . ,

B

k

to wszystkie atrybuty relacji R, to zachodzi

A

1

. . .

A

n

 B

1

. . .

B

k

.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

40 / 52

Zale˙zno´sci wielowarto´sciowe

Definicja 21

Zale˙zno´s´c wielowarto´sciowa A

1

. . .

A

n

 B

1

. . .

B

k

jest

trywialna

je´sli

{B

1

, . . . ,

B

k

} ⊆ {A

1

, . . . ,

A

n

} lub A

1

, . . . ,

A

n

,

B

1

, . . . ,

B

k

to wszystkie

atrybuty relacji.

Fakt 22

Dla ka˙zdej relacji R zachodz ˛

a wszystkie trywialne zale˙zno´sci

wielowarto´sciowe.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

41 / 52

Czwarta posta´c normalna – 4NF

Definicja 23

Relacja R jest w

czwartej postaci normalnej

(4NF) je´sli dla dowolnej

nietrywialnej zale˙zno´sci wielowarto´sciowej A

1

. . .

A

n

 B

1

. . .

B

k

w R,

zbiór atrybutów {A

1

, . . . ,

A

n

} jest nadkluczem.

Obserwacja. Warunek na 4NF jest powtórzeniem warunku dla BCNF
ale dla zale˙zno´sci wielowarto´sciowych.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

42 / 52

Czwarta posta´c normalna – 4NF

Poniewa˙z ka˙zda zale˙zno´sci funkcyjna jest te˙z wielowarto´sciow ˛

a, to z

ostatniej obserwacji wynika.

Fakt 24

Je´sli relacja R jest w 4NF to jest te˙z w BCNF.

Zachodz ˛

a wi ˛ec nastepuj ˛

ace wynikania:

R jest w 4NF =⇒ R jest w BCNF =⇒ R jest w 3NF.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

43 / 52

4NF – przykład dekompozycji

Relacj ˛e Filmy

aktor

adres

tytul

Pitt

L.A

Mr & Mrs Smith

Pitt

Londyn

Mr & Mrs Smith

Jolie

Pary˙z

Rybki z Ferajny

Jolie

L.A

Rybki z Ferajny

Jolie

Pary˙z

Mr & Mrs Smith

Jolie

L.A

Mr & Mrs Smith

mo˙zemy zdekomponowa´c u˙zywaj ˛

ac zale˙zno´sci aktor  adres do

Adresy(aktor, adres) i Wystapil(aktor, tytul).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

44 / 52

4NF – przykład dekompozycji

Adresy:

aktor

adres

Pitt

L.A

Pitt

Londyn

Jolie

L.A

Jolie

Pary˙z

Wystapil:

aktor

tytul

Pitt

Mr & Mrs Smith

Jolie

Mr & Mrs Smith

Jolie

Rybki z Ferajny

Oryginaln ˛

a relacj ˛e Filmy mo˙zemy odtworzy´c jako Adresy o

n Wystapil

czyli

s e l e c t A . a k t o r , A . adres , W. t y t u l

from Adresy A , W y s t a p i l W
where A . a k t o r = W. a k t o r ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

45 / 52

Dekompozycja do 4NF

Aby zdekomponowa´c relacj ˛e R do 4NF musimy:

1

znale´z´c nietrywialn ˛

a zale˙zno´s´c wielowarto´sciow ˛

a

A

1

. . .

A

n

 B

1

. . .

B

k

tak ˛

a, ˙ze {A

1

, . . . ,

A

n

} nie jest nadkluczem R,

2

je´sli C

1

, . . . ,

C

m

to pozostałe atrybuty R, to dekomponujemy R na:

I

S(A

1

, . . . ,

A

n

,

B

1

, . . . ,

B

k

)

I

T (A

1

, . . . ,

A

n

,

C

1

, . . . ,

C

m

)

.

3

powtarzamy dekompozycj ˛e dla nowych relacji.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

46 / 52

Do zrozumienia

na czym polegaj ˛

a anomalie, zale˙zno´sci funkcyjne, klucze, 1NF, 2NF,

dekompozycja, 3NF

mo˙ze nawet:

BCNF, zale˙znosci wielowarto´sciowe, 4NF, ...

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

47 / 52

Przykład

Chcemy stworzy´c BD dla sklepu "Mydło i powidło". Mo˙zemy
zdefiniowa´c jedn ˛

a tabel ˛e

Zamówienia o jednej kolumnie zawieraj ˛

ac ˛

a

warto´sci takie jak np.

dane klienta – imi ˛e, nazwisko, jego id, ...

list ˛e przedmiotów które zakupił, nazwy, ilo´s´c, ceny, kwota zakupu,
...

dane do rachunku i dane do wysyłki.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

48 / 52

Przykład

Mo˙zemy zdefiniowa´c jedn ˛

a tabel ˛e

Zamówienia o jednej kolumnie

zawieraj ˛

ac ˛

a warto´sci takie jak np.

Adam Abacki, adres do rachunku, adres do wysyłki, no˙zyczki, kod
no˙zyczek, ilo´s´c, cena, VAT, klej, kod kleju, ilo´s´c, cena, VAT, warto´s´c
zakupów, data.

Taki schemat nie jest w 1NF, jest prosty lecz trudno wydoby´c z niego
informacje. Dlatego, rozdzielamy dane na oddzielne kolumny.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

49 / 52

Przykład

Poniewa˙z ilo´s´c artykułów w zamówieniu mo˙ze by´c ró˙zna a mamy
tylko stał ˛

a liczb ˛e kolumn musimy stworzy´c dwie tabele:

I

Zamówienia: id_zamowienia (PK), data, id_klienta, imie, nazwisko,
adres do rachunku, adres do wysyłki.

I

Towary: id_zamowienia (PK, FK), id_artykulu (PK), ilosc, cena,
VAT, warto´s´c zakupów.

Jak tylko rozdzielimy dane na odr ˛ebne atrybuty, staniemy przed
pytaniem, co mo˙ze by´c kluczem w naszej tabeli.

Zauwa˙zmy, ˙ze cz ˛e´sc danych w tabeli

Towary zale˙zy tylko od

id_artykulu (cena, VAT). Schemat BD nie jest w 2NF bo
id_artykulu to tylko cz ˛e´s´c klucza.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

50 / 52

Przykład

Mamy tabele:

I

Zamówienia: id_zamowienia (PK), data, imie, nazwisko, adres do
rachunku, adres do wysyłki.

I

Towary: id_zamowienia (PK, FK), id_artykulu (PK), ilosc, cena,
VAT, warto´s´c zakupów.

Aby uzyska´c 2NF rozdzielamy tabel ˛e

Towary na

I

Towary_zamowione: id_zamowienia (PK, FK), data, imie,
nazwisko, adres do rachunku, adres do wysyłki, id_artykulu (PK,
FK), ilosc, wartosc zakupów.

I

Asortyment (czyli towary, którymi sklep handluje): id_artykułu
(PK), cena, VAT.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

51 / 52

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˙z ˛

a tylko od id_klienta,

który nie jest kluczem w tabeli. Aby uzyska´c 3NF tworzymy now ˛

a

tabel ˛e.

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 Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład szósty Normalizacja modelu bazy danych

52 / 52