Bazy danych

Normalizacja schematów
logicznych relacji.
Denormalizacja.

Krzysztof Molenda

Normalizacja

– wprowadzenie (1)

• W 1970 E.F. Codd sformułował pewne reguły dotyczące projektowania baz

danych. Reguły te zostały pierwotnie wyrażone jako trzy

postacie

normalne

:

– pierwsza postać normalna (1NF)
– druga postać normalna (2NF)
– trzecia postać normalna (3NF)

• W połowie lat siedemdziesiątych spostrzeżono pewne braki w trzeciej

postaci normalnej i zdefiniowano mocniejszą postać normalną, znaną jako

postać normalna Boyce’a-Codda

. W późniejszym czasie opracowano postać

normalną

czwartą

, a nawet

piątą

.

• Proces kolejnego przekształcania projektu baz danych przez te trzy postacie

normalne znany jest jako

normalizacja

.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

2

Normalizacja

– podstawowe pojęcia

• Więzy integralności

to zbiór twierdzeń, które muszą być zawsze spełnione

w każdym stanie bazy danych.

Zależności

mają reprezentować semantyczne

związki między elementami świata.

• Normalizacja danych

to takie uporządkowanie tablic (najczęściej przez

rozbicie dużych tabel na kilka mniejszych – z mniejszą liczbą kolumn), aby
były one maksymalnie wydajne i zwarte. Unikamy dzięki temu błędów i
utraty spójności danych podczas pracy z relacyjną bazą danych.

• Redundancja danych

, czyli powtarzanie się tych samych informacji w kilku

miejscach w bazie (co może prowadzić do nadmiernego rozrostu bazy
danych). Pewna powtarzalność danych jest prawie zawsze konieczna,
jednak należy unikać powtórzeń, jeśli to tylko możliwe.

• Redundancja danych w niektórych sytuacjach prowadzi do anomalii:

– Anomalie modyfikacji

: wartość danej zostanie zmodyfikowana w pewnej

krotce, a w innej nie.

– Anomalie przy usuwaniu

: jeżeli dla pewnego atrybutu zaczyna obowiązywać

wartość

null

, to jako efekt uboczny może zdarzyć się utrata danych.

– Anomalie dołączania

: pewnych danych nie można wprowadzić niezależnie od

innych.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

3

Nieznormalizowany zbiór danych

• Tabela ZAMOWIENIA jest

nieznormalizowana

.

• Aby tabelę można było nazwać RELACJĄ, wartości atrybutów muszą być

elementarne (nie mogą być zbiorami wartości).

• W przykładzie tabeli ZAMOWIENIA, atrybuty

Id części

,

Nazwa części

,

Ilość

,

Magazyn

,

Adres

zawierają listy wartości a nie wartości elementarne.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

4

ZAMOWIENIA

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy

Id części

Nazwa części

Ilośc

Magazyn

Adres magazynu

1

3

Dewoo

W-wa

53, 57 59 gaźnik, wał, błotnik 100, 50 500

5, 5, 6

Chopina, Chopina, Mozarta

2

4

Fiat

Tychy

54, 32

gaźnik, koło

500, 100

5, 6

Chopina, Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59, 21

błotnik, prądnica

400, 50

6, 7

Mozarta, Bacha

5

3

Dewoo

W-wa

53, 57

gaźnik, wał

200, 30

5, 5

Chopina, Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Pierwsza postać normalna (1NF) – slajd 1

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

5

• Relacja jest w pierwszej postaci normalnej (1NF,

1 Normal Form

),

jeżeli wartości atrybutów są elementarne, tzn. są to wartości
określonego typu, a nie zbiory wartości. Pierwsza postać normalna
jest konieczna, aby tabelę można było nazwać relacją.

• Większość systemów baz danych nie ma możliwości zbudowania tabel

nie będących w pierwszej postaci normalnej.

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy Id części

Nazwa części

Ilość

Magazyn

Adres magazynu

1

3

Dewoo

W-wa

53

gaźnik

100

5

Chopina

1

3

Dewoo

W-wa

57

wał

50

5

Chopina

1

3

Dewoo

W-wa

59

błotnik

500

6

Mozarta

2

4

Fiat

Tychy

54

gaźnik

500

5

Chopina

2

4

Fiat

Tychy

32

koło

100

6

Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59

błotnik

400

6

Mozarta

4

6

Fiat

Bielsko

21

prądnica

50

7

Bacha

5

3

Dewoo

W-wa

53

gaźnik

200

5

Chopina

5

3

Dewoo

W-wa

57

wał

30

5

Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Pierwsza postać normalna (1NF) – slajd 2

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

6

• Cechy powyższej relacji ZAMOWIENIA:

– Redundancja – problem zapewnienia spójności danych
– Anomalia wprowadzania danych – nie można wprowadzić danych nowego

dostawcy dopóki nie dostarcza on części.

– Anomalia usuwania danych – usunięcie części „silnik” spowoduje usunięcie

bezpowrotne danych o dostawcy „Andrychów”.

– Anomalia uaktualniania danych - zmiana adresu konkretnego dostawcy musi

być wykonana w każdej krotce jego dotyczącej.

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy Id części

Nazwa części

Ilość

Magazyn

Adres magazynu

1

3

Dewoo

W-wa

53

gaźnik

100

5

Chopina

1

3

Dewoo

W-wa

57

wał

50

5

Chopina

1

3

Dewoo

W-wa

59

błotnik

500

6

Mozarta

2

4

Fiat

Tychy

54

gaźnik

500

5

Chopina

2

4

Fiat

Tychy

32

koło

100

6

Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59

błotnik

400

6

Mozarta

4

6

Fiat

Bielsko

21

prądnica

50

7

Bacha

5

3

Dewoo

W-wa

53

gaźnik

200

5

Chopina

5

3

Dewoo

W-wa

57

wał

30

5

Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Pierwsza postać normalna (1NF) – slajd 3

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

7

• Definicja: Relacja jest w pierwszej postaci normalnej (1NF) wtedy i tylko

wtedy, gdy

każdy atrybut niekluczowy jest funkcjonalnie zależny od

klucza głównego

.

– Kluczem

relacji nazywamy taki zbiór atrybutów, który jednoznacznie

identyfikuje każdą krotkę relacji. Klucze: prosty, złożony, potencjalny. Klucz
główny (primary key).

– B jest

funkcjonalnie zależny

od A (

A



B

), jeśli dowolnej wartości a atrybutu A

odpowiada nie więcej niż jedna wartość b atrybutu B.

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy Id części

Nazwa części

Ilośc

Magazyn

Adres magazynu

1

3

Dewoo

W-wa

53

gaźnik

100

5

Chopina

1

3

Dewoo

W-wa

57

wał

50

5

Chopina

1

3

Dewoo

W-wa

59

błotnik

500

6

Mozarta

2

4

Fiat

Tychy

54

gaźnik

500

5

Chopina

2

4

Fiat

Tychy

32

koło

100

6

Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59

błotnik

400

6

Mozarta

4

6

Fiat

Bielsko

21

prądnica

50

7

Bacha

5

3

Dewoo

W-wa

53

gaźnik

200

5

Chopina

5

3

Dewoo

W-wa

57

wał

30

5

Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Klucz: {Nr zam, Id części}

Zależności funkcyjne – definicje – slajd 1

• Uniwersalny schemat relacji R = {A

1

, A

2

, ..., A

n

} jest zbiorem atrybutów

tworzących relację.

• Zbiór identyfikujący relacji R = {A

1

, A

2

, ..., A

n

} to zbiór atrybutów S



R,

który jednoznacznie identyfikuje wszystkie krotki relacji o schemacie R.
Inaczej mówiąc, w żadnej relacji o schemacie R nie mogą istnieć dwie krotki
t

1

i t

2

takie, że t

1

[S] = t

2

[S].

• Klucz K schematu relacji R to minimalny zbiór identyfikujący, tzn. taki, że

nie istnieje K’



K będące zbiorem identyfikującym schematu R.

– W uproszczeniu klucz stanowi więc kolumnę lub kilka kolumn tabeli,

pozwalających na jednoznaczne zidentyfikowanie rekordu. Klucze dzielą się
na klucze proste i złożone. Klucz nazywamy kluczem prostym, jeżeli zbiór
atrybutów (kolumn) wchodzących w jego skład jest zbiorem
jednoelementowym; w przeciwnym wypadku mamy do czynienia z kluczem
złożonym. Najczęściej w relacji można wyróżnić wiele kluczy, które
nazywamy kluczami potencjalnymi. Dla każdego wiersza wartość atrybutu
będącego kluczem potencjalnym musi być inna i nie może on przyjmować
wartości pustych.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

8

Zależności funkcyjne – definicje – slajd 2

• Ponieważ dana tabela może mieć tylko jeden klucz główny, to w sytuacjach

gdy więcej atrybutów spełnia cechy klucza potencjalnego wybieramy jeden
klucz spośród kluczy potencjalnych i nazywamy go kluczem głównym
(primary key), natomiast pozostałe kluczami drugorzędnymi (secondary
key).

• Atrybut

relacji jest

podstawowy

, jeżeli należy do dowolnego z kluczy tej

relacji.

• Atrybut

relacji nazywa się

wtórnym

, jeżeli nie należy do żadnego z kluczy

tej relacji.

• Atrybut B relacji R jest

funkcjonalnie zależny

od atrybutu A tej relacji (A

identyfikuje B): (

A



B

), jeśli dowolnej wartości a atrybutu A odpowiada

nie więcej niż jedna wartość b atrybutu B.

• Atrybut B jest

w pełni funkcjonalnie zależny

od zbioru atrybutów X w

schemacie R, jeżeli X



B i nie istnieje podzbiór taki, że X’



B.

• Zbiór atrybutów Y jest

częściowo zależny

od zbioru atrybutów X w

schemacie R, jeżeli X



Y i istnieje podzbiór taki, że X’



Y.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

9

Zależności funkcyjne – definicje – slajd 3

• Niech X, Y i Z będą trzema rozłącznymi podzbiorami atrybutów danej

relacji. Podzbiór atrybutów Z jest przechodnio funkcjonalnie zależny od
podzbioru atrybutów X, jeśli podzbiór atrybutów Z jest funkcjonalnie
zależny od podzbioru atrybutów Y i podzbiór atrybutów Y jest funkcjonalnie
zależny od podzbioru atrybutów X, natomiast podzbiór atrybutów X nie jest
funkcjonalnie zależny od Y i podzbiór atrybutów Y nie jest funkcjonalnie
zależny od Z.

• Podzbiór atrybutów Y jest wielowartościowo funkcjonalnie zależny od

podzbioru atrybutów X w schemacie R, jeżeli dla dowolnej relacji r w
schemacie R i dla dowolnej pary krotek t

1

i t

2

z relacji r takich, że

t

1

[X] = t

2

[X] istnieje taka para krotek s

1

i s

2

w relacji r, że:

– s

1

[X] = s

2

[X] = t

1

[X] = t

2

[X]

– s

1

[Y] = t

1

[Y] i s

1

[R–X–Y] = t

2

[R–X–Y] oraz

– s

2

[Y] = t

2

[Y] i s

2

[R–X–Y] = t

1

[R–X–Y]

Występowanie krotek spełniających wymienione wyżej warunki wiąże się

najczęściej z niezależnością jednego zbioru atrybutów od drugiego.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

10

Zależności funkcjonalne w relacji ZAMOWIENIA

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

11

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy Id części Nazwa części

Ilośc Magazyn Adres magazynu

1

3

Dewoo

W-wa

53

gaźnik

100

5

Chopina

1

3

Dewoo

W-wa

57

wał

50

5

Chopina

1

3

Dewoo

W-wa

59

błotnik

500

6

Mozarta

2

4

Fiat

Tychy

54

gaźnik

500

5

Chopina

2

4

Fiat

Tychy

32

koło

100

6

Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59

błotnik

400

6

Mozarta

4

6

Fiat

Bielsko

21

prądnica

50

7

Bacha

5

3

Dewoo

W-wa

53

gaźnik

200

5

Chopina

5

3

Dewoo

W-wa

57

wał

30

5

Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Klucz: {Nr zam, Id części}

• Atrybuty „Nazwa dostawcy” i „Adres dostawcy” są przechodnio

funkcjonalnie zależne od atrybutu „nr zamówienia”, ponieważ atrybut
„Id dostawcy” jest funkcjonalnie zależny od atrybutu „Nr zamówienia”
i atrybuty „Nazwa dostawcy” oraz „Adres dostawcy” są funkcjonalnie
zależne od „Id dostawcy”.

• Jednocześnie „Id dostawcy” nie jest funkcjonalnie zależny od „Nazwy

dostawcy” (mogą być różni dostawcy o tej samej nazwie) ani od
„Adresu dostawcy” (dwóch dostawców może mieć ten sam adres).

Id dostawcy

Nr zam

Nazwa dostawcy

Adres dostawcy

Id części

Nazwa części

ilość

magazyn

Adres magazynu

Proces normalizacji -

własności

Proces normalizacji relacji to proces, podczas którego schematy relacji
posiadające pewne

niepożądane

cechy są dekomponowane na mniejsze

schematy relacji o

pożądanych

własnościach. Proces normalizacji musi

posiadać trzy dodatkowe własności:

• Własność zachowania atrybutów - żaden atrybut nie zostanie zagubiony w

trakcie procesu normalizacji.

• Własność zachowania informacji - dekompozycja relacji nie prowadzi do

utraty informacji, tj. łącząc zdekomponowane relacje możemy odtworzyć
oryginalną relację.

• Własność zachowania zależności - wszystkie zależności funkcyjne są

reprezentowane w pojedynczych schematach relacji.

Proces normalizacji schematu relacji polega na sprawdzeniu czy dany schemat
jest w odpowiedniej postaci normalnej, jeżeli nie wówczas następuje
dekompozycja schematu relacji na mniejsze schematy relacji. Ponownie,
weryfikowana jest postać normalna otrzymanych schematów relacji. Jeżeli nie
spełniają one zadanej postaci normalnej to proces dekompozycji jest
kontynuowany dopóki otrzymane schematy relacji nie będą w odpowiedniej
postaci normalnej.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

12

Druga postać normalna (2NF) – slajd 1

Pełna zależność funkcjonalna:

• Atrybut B relacji jest

w pełni zależny

od zbioru atrybutów

X jeśli jest

funkcjonalnie zależny od

X

ale nie jest zależny od żadnego jego podzbioru.

Druga postać normalna (2NF):

• Relacja jest w

drugiej postaci normalnej

, jeśli

1. jest w pierwszej postaci normalnej i

2. każdy atrybut tej relacji nie wchodzący w skład klucza (atrybut wtórny)

jest w pełni funkcjonalnie zależny od wszystkich kluczy potencjalnych
(

jest po prostu w pełni zależny od klucza

lub inaczej,

nie jest częściowo

zależny od klucza

).

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

13

Druga postać normalna (2NF) – slajd 2

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

14

Nr

zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy Id części Nazwa części

Ilośc Magazyn Adres magazynu

1

3

Dewoo

W-wa

53

gaźnik

100

5

Chopina

1

3

Dewoo

W-wa

57

wał

50

5

Chopina

1

3

Dewoo

W-wa

59

błotnik

500

6

Mozarta

2

4

Fiat

Tychy

54

gaźnik

500

5

Chopina

2

4

Fiat

Tychy

32

koło

100

6

Mozarta

3

5

Andrychów Andrychów

88

silnik

15

7

Bacha

4

6

Fiat

Bielsko

59

błotnik

400

6

Mozarta

4

6

Fiat

Bielsko

21

prądnica

50

7

Bacha

5

3

Dewoo

W-wa

53

gaźnik

200

5

Chopina

5

3

Dewoo

W-wa

57

wał

30

5

Chopina

6

3

Dewoo

W-wa

59

błotnik

20

6

Mozarta

Klucz: {Nr zam, Id części}

Relacja „Zamówienie” nie jest w drugiej
postaci normalnej, ponieważ atrybuty „Id
dostawcy”, „Nazwa dostawcy”, „Adres
dostawcy” i „Nazwa części” nie są w pełni
funkcjonalnie zależne od jednego klucza
potencjalnego – pary („Nr zamówienia”, „Id
części”).

Id dostawcy

Nr zam

Nazwa dostawcy

Adres dostawcy

Id części

Nazwa części

ilość

magazyn

Adres magazynu

Druga postać normalna (2NF) – slajd 3

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

Nr zam

Id części

Ilośc

1

53

100

1

57

50

1

59

500

2

54

500

2

32

100

3

88

15

4

59

400

4

21

50

5

53

200

5

57

30

6

59

20

dostawy części

Nr zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy

1

3

Dewoo

W-wa

2

4

Fiat

Tychy

3

5

Andrychów Andrychów

4

6

Fiat

Bielsko

5

3

Dewoo

W-wa

6

3

Dewoo

W-wa

dostawca na zamówieniu

Id części

Nazwa części

Magazyn

Adres

magazyn

u

53

gaźnik

5

Chopina

57

wał

5

Chopina

59

błotnik

6

Mozarta

54

gaźnik

5

Chopina

32

koło

6

Mozarta

88

silnik

7

Bacha

59

błotnik

6

Mozarta

21

prądnica

7

Bacha

części w magazynie

Druga postać normalna (2NF) – slajd 4

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

Nr zam

Id części

Ilośc

1

53

100

1

57

50

1

59

500

2

54

500

2

32

100

3

88

15

4

59

400

4

21

50

5

53

200

5

57

30

6

59

20

dostawy części

Nr zam

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy

1

3

Dewoo

W-wa

2

4

Fiat

Tychy

3

5

Andrychów Andrychów

4

6

Fiat

Bielsko

5

3

Dewoo

W-wa

6

3

Dewoo

W-wa

dostawca na zamówieniu

Id części

Nazwa części

Magazyn

Adres

magazyn

u

53

gaźnik

5

Chopina

57

wał

5

Chopina

59

błotnik

6

Mozarta

54

gaźnik

5

Chopina

32

koło

6

Mozarta

88

silnik

7

Bacha

59

błotnik

6

Mozarta

21

prądnica

7

Bacha

części w magazynie

Przykład: tabela „dostawca na zamówieniu”
Redundancja: (Id dostawcy, Nazwa dostawcy,
Adres dostawcy)
Anomalie:
• przy modyfikacji danych – np. zmiana

adresu firmy „Dewoo”

• przy wstawianiu – nie można zarejestrować

dostawcy dopóki nie będzie zamówienia

• przy usuwaniu – usunięcie zamówienia nr 3

spowoduje usunięcie bezpowrotne
dostawcy „Andrychów”

Problemy: zapewnienie spójności bazy -
kaskadowe usuwanie:
• usunięcie zamówienia w „dostawca na

zamówieniu” powinno zaktualizować
relację „dostawy części”

• usunięcie krotki w relacji „dostawy części”

powinno zaktualizować relację „dostawca
na zamówieniu”

Trzecia postać normalna (3NF) – slajd 1

• Relacja jest w trzeciej postaci normalnej jeśli:

– jest w drugiej postaci normalnej i
– każdy jej atrybut nie wchodzący w skład klucza potencjalnego nie jest

przechodnio zależny od żadnego potencjalnego klucza tej relacji
(inaczej mówiąc każdy atrybut musi być w pełni zależny od klucza głównego i
niezależny od pozostałych atrybutów)

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

17

A

B

C

Przechodnia zależność
funkcjonalna

A

B

C

B

Równoważne zależności
funkcjonalne w trzeciej postaci
normalnej

Trzecia postać normalna (3NF) – slajd 2

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

18

Zamówienie-dostawcy

Nr zam

Id

dostawcy

1

3

2

4

3

5

4

6

5

3

6

3

Dostawcy

Id

dostawcy

Nazwa

dostawcy

Adres

dostawcy

3

Dewoo

W-wa

4

Fiat

Tychy

5

Andrychów Andrychów

6

Fiat

Bielsko

Części

Id części

Nazwa części

21

prądnica

32

koło

53

gaźnik

54

gaźnik

57

wał

59

błotnik

88

silnik

Magazyny

Magazyn

Adres magazynu

5

Chopina

6

Mozarta

7

Bacha

Części w magazynie

Id części

Magazyn

21

7

32

6

53

5

54

5

57

5

59

6

88

7

Co zostało zrobione

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

19

Dane

nieuporządko

wane
• ???

1 NF

• ZAMOWIENIA

2 NF

• Dostawca na

zamówieniu

• Części w

magazynie

• Dostawy

części

3 NF

• Dostawcy
• Części
• Magazyny
• Części w

magazynie

• Zamówienie-

dostawcy

UWAGI:

1. Proces normalizacji nie jest jednoznaczny. Może

być wspomagany komputerowo.

2. Nie zawsze, z punktu widzenia efektywności

przetwarzania posiadanie 2PN lub 3PN jest
korzystne.

Postać normalna Boyce’a-Codda (BCNF) – slajd 1

• Przykład: relacja GRUNTY

– Dwa klucze:

• Klucz1: Id_Własności,
• Klucz2: {Województwo, Id_gruntu}

– Zależności:

• (1) oraz (2) są zależnościami od klucza
• (3) Stopa_podatku zależy od Województwo
• (4) Województwo zależy od Obszar
• (5) Cena zależy od Obszar

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

20

Relacja jest w 1NF.
Relacja nie jest w 2NF:
• Stopa_podatku jest

częściowo zależna od
Klucza2 (zależność 3)

Postać normalna Boyce’a-Codda (BCNF) – slajd 2

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

21

• Dekomponujemy GRUNTY na:

– Grunty-1 – jest w 2NF ale nie jest w 3NF (ze względu na Obszar



Cena)

– Grunty-2 – jest w 2NF oraz w 3NF

Grunty-1

Stopa_podatk
u

Grunty-2

Grunty

Postać normalna Boyce’a-Codda (BCNF) – slajd 3

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

22

• Relacja GRUNTY została zdekomponowana do relacji w 3NF

• Problem: zależność Obszar



Województwo może powodować dużą redundancję (np. w woj.

małopolskim działki standardowo 1, 2, 3 ha, zaś w woj. podkarpackim 5, 10, 20, 30 ha. Jeśli w
relacji GRUNTY informacja o zależności między województwem a obszarem wystąpiła w
tysiącach krotek, to po dekompozycji przeniosła się do relacji Grunty-1A).

Grunty-1

Stopa_podatku

Grunty-2

Grunty

Postać normalna Boyce’a-Codda (BCNF) – slajd 4

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

23

• Relacja jest w postaci BCNF gdy każdy atrybut relacji zależy

funkcjonalnie tylko od klucza podstawowego.

• W tym przypadku, dla zmniejszenia redundancji należy

zdekomponować relację Grunty-1A na dwie relacje:

– Grunty-1A-1
– Grunty-1A-2

Id_Własności

Id_Gruntu

Obszar

Grunty-1A-1

Obszar

Województwo

Grunty-1A-2

3NF z zależnościami wielowartościowymi

• Schemat relacji jest 3NF
• Kluczem relacji jest {Nazwisko, J prog,

J obcy} (klucz złożony)

• Problem: modyfikacja zależna od

stanu bazy danych:

• Załóżmy, że Nowak nauczył się języka

PHP oraz języka francuskiego.
Wprowadzenie tej informacji do
relacji wymaga wprowadzenia aż 6
nowych krotek:

– (Nowak, PHP, Francuski)
– (Nowak, Fortran, Francuski)
– (Nowak, C++, Francuski)
– (Nowak, PHP, Angielski)
– (Nowak, PHP, Rosyjski)

• Problemy z pielęgnacją relacji przez

nieinformatyka

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

24

Nazwisko

J prog

J obcy

Kowalski

Fortran

Angielski

Kowalski

Fortran

Francuski

Kowalski

Basic

Angielski

Kowalski

Basic

Francuski

Kowalski

Pascal

Angielski

Kowalski

Pascal

Francuski

Ciastoń

C

Angielski

Ciastoń

C

Włoski

Ciastoń

C

Hiszpański

Ciastoń

Pascal

Angielski

Ciastoń

Pascal

Włoski

Ciastoń

Pascal

Hiszpański

Nowak

Fortran

Angielski

Nowak

Fortran

Rosyjski

Nowak

C++

Angielski

Nowak

C++

Rosyjski

3NF z zależnościami wielowartościowymi

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

25

Nazwisko

J prog

J obcy

Kowalski

Fortran

Angielski

Kowalski

Fortran

Francuski

Kowalski

Basic

Angielski

Kowalski

Basic

Francuski

Kowalski

Pascal

Angielski

Kowalski

Pascal

Francuski

Ciastoń

C

Angielski

Ciastoń

C

Włoski

Ciastoń

C

Hiszpański

Ciastoń

Pascal

Angielski

Ciastoń

Pascal

Włoski

Ciastoń

Pascal

Hiszpański

Nowak

Fortran

Angielski

Nowak

Fortran

Rosyjski

Nowak

C++

Angielski

Nowak

C++

Rosyjski

Nazwisko

J prog

Kowalski

Fortran

Kowalski

Basic

Kowalski

Pascal

Ciastoń

C

Ciastoń

Pascal

Nowak

Fortran

Nowak

C++

Nazwisko

J obcy

Kowalski

Angielski

Kowalski

Francuski

Ciastoń

Angielski

Ciastoń

Włoski

Ciastoń

Hiszpański

Nowak

Angielski

Nowak

Rosyjski

dekompozycja

Wprowadzenie informacji „Nowak nauczył się PHP oraz francuskiego
wymaga tylko wprowadzenia po jednej krotce do każdej z relacji.

Zależności wielowartościowe – 4NF

• Zależności wielowartościowe są konsekwencją wymagań pierwszej postaci

normalnej, która nie dopuszcza, aby krotki zawierały atrybuty
wielowartościowe. Zależność wielowartościowa jest własnością semantyczną
schematu relacji.

• Zależność wielowartościowa występuje w relacji nie dlatego, że na skutek

zbiegu okoliczności tak ułożyły się wartości krotek, lecz występuje ona

dla

dowolnej relacji

dlatego, że

odzwierciedla ona ogólną prawidłowość

modelowanej rzeczywistości

.

– Nazwisko ->> J prog
– Nazwisko ->> J obcy

• Zależności wielowartościowe występują rzadziej niż inne.
• Relacja jest w

czwartej postaci normalnej

(4NF), gdy jest w trzeciej

postaci normalnej i wielowartościowa zależność podzbioru (atrybutów) Y od
X pociąga za sobą funkcjonalną zależność wszystkich atrybutów tej relacji
od X.

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

26

4NF

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

27

Hurtownia Producent Wyrób
Centr

Opel

rozrząd

Centr

Opel

wałek

Centr

Ford

rozrząd

Centr

Ford

wałek

Centr

Star

sk. bieg.

Doda

Opel

rozrząd

Doda

Ford

rozrząd

Doda

Star

sk. bieg.

Miks

Fiat

koło

Miks

Fiat

hamulec

Miks

Star

koło

Miks

Star

hamulec

Dostawy

Czwarta postać normalna,
bo występuje tylko
wielowartościowa
zależność od klucza
{Hurtownia}

Relacja jest w piątej postaci
normalnej (5NF), gdy jest w
czwartej postaci normalnej i gdy
zależność połączeniowa (w
przypadku jej występowania) wynika
z zależności od klucza.

Relacja w 4NF jest w 5NF, jeżeli
nie istnieje jej rozkład
odwracalny na zbiór mniejszych
tabel.

5NF

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

28

Hurtownia Producent
Centr

Opel

Centr

Ford

Centr

Star

Doda

Opel

Doda

Ford

Doda

Star

Miks

Fiat

Miks

Star

Producent Wyrób
Fiat

koło

Fiat

hamulec

Ford

rozrząd

Ford

wałek

Opel

rozrząd

Opel

wałek

Star

sk. bieg.

Star

koło

Star

hamulec

Hurtownia Wyrób
Centr

rozrząd

Centr

wałek

Centr

sk. bieg.

Doda

rozrząd

Doda

sk. bieg.

Miks

koło

Miks

hamulec

Hurtownia Producent Wyrób
Centr

Opel

rozrząd

Centr

Opel

wałek

Centr

Ford

rozrząd

Centr

Ford

wałek

Centr

Star

sk. bieg.

Doda

Opel

rozrząd

Doda

Ford

rozrząd

Doda

Star

sk. bieg.

Miks

Fiat

koło

Miks

Fiat

hamulec

Miks

Star

koło

Miks

Star

hamulec

4NF

5NF

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

29

dealer

firma

pojazd

Jones

Ford

Samochód_osobow

y

Jones

Vauxhall Furgonetka

Smith

Ford

Furgonetka

Smith

Vauxhall Samochód_osobow

y

Punkty
sprzedaży

• Tabela w czwartej postaci normalnej jest w piątej postaci normalnej,

jeżeli nie istnieje jej rozkład odwracalny na zbiór mniejszych tabel.

• W podanym przykładzie nie można dokonać rozkładu struktury,

ponieważ, chociaż dealer Jones sprzedaje samochody osobowe firmy
Ford i furgonetki firmy Vauxhall, nie sprzedaje furgonetek firmy Ford
ani samochodów osobowych firmy Vauxhall. Piąta postać normalna
dotyczy powiązanych między sobą zależności wielowartościowych,
nazywanych też

zależnościami złączeń

.

Hierarchia zależności poziomów normalizacji

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

30

Etapy normalizacji -

ściąga

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

31

Przysięga normalizacji:
1. Bez powtórzeń
2. Pola zależą od klucza
3. Od całego klucza
4. I niczego innego, tylko klucza
5. Tak mi dopomóż Codd!

Denormalizacja

• Dotyczy przede wszystkim baz danych tworzonych na potrzeby tzw.

HURTOWNI DANYCH

• Czym charakteryzują się hurtownie?

- Statyczność
- Archiwalność
- Tematyczność
- Analityczność

- Schematy gwiaździste:

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

32

TABELE

FAKTÓW

I

WYMIARÓW

FAKTY:

•Dochód

•Sprzedaż

•Dostawy

WYMIARY:

•Produkt

•Rynek

•Czas

Id okresu

Opis okresu
Kwartał
Rok

Id rynku

Opis rynku
Sektor
Region

Id produktu

Opis produktu
Marka
Rozmiar

Id okresu

Id produktu
Id rynku
Jednostki
Koszt
Rabaty

SCHEMAT GWIAŹDZISTY

w

w

w

F

W - wymiar

F - fakty

Klucz:

Wymiar: rynek

Wymiar: okres

Wymiar: produkt

Fakty: sprzedaż

PRZYKŁADY

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

34

Przykład 1 (slajd 1)

• Baza danych sklepu

– Postać nieznormalizowana, należy wykonać:
1. Usunąć atrybuty złożone
2. Usunąć atrybuty wielowartościowe
3. Usunąć powtarzające się wiersze
4. Ustalić klucze

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

35

Przykład 1 (slajd 2)

Baza w 1NF
• relacja

Rachunki(id_za, data_za, id_to, nazwa, ilosc, cena, id_pr, nazw_pr)

• klucz:

{id_za, id_to}

• zależności funkcyjne:

– id_za  data_za, id_pr
– id_pr  nazw_pr
– id_to  nazwa, cena
– {id_za, id_to}  ilosc

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

36

Nie jest w 2NF, bo:
• jest klucz złożony
• są atrybuty niekluczowe zależne

od części klucza, a nie od całości

Przykład 1 (slajd 3)

• Przejście z 1NF do 2NF

– Identyfikacja zależności funkcyjnych
– Ustalenie wszystkich kluczy, podział atrybutów na kluczowe i niekluczowe
– Sprawdzenie, czy są atrybuty niekluczowe zależne od fragmentu klucza.
– Jeśli tak – dekompozycja relacji

• Relacje po dekompozycji:

– Zamowienia( id_za, data_za, id_pr, nazw_pr)
– Towary( id_to, nazwa, cena )
– Pozycje( id_za, id_to, ilosc )

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

37

Nie jest w 3NF, bo:
• są atrybuty niekluczowe

zależne tranzytywnie od
klucza

id_za  id_pr  nazw_pr

Przykład 1 (slajd 4)

• Przejście z 2NF do 3NF

– Sprawdzenie (dla każdej relacji), czy są atrybuty niekluczowe zależne

tranzytywnie od klucza.

– Jeśli tak, dekompozycja relacji

• Relacje po dekompozycji

– Zamowienia( id_za, data_za, id_pr)
– Pracownicy( id_pr, nazw_pr)
– Towary( id_to, nazwa, cena )
– Pozycje( id_za, id_to, ilosc )

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

38

Jest w 3NF i jest w BCNF, bo:
• nie ma zależności nie od

klucza

Przykład 1 (slajd 5)

• Przejście z 3NF do BCNF

– Sprawdzenie, czy są zależności nie od klucza? Jeśli tak, to próba

dekompozycji.

• Relacje są w BCNF. Wszystkie atrybuty zależą od klucza

– id_za  data_za
– id_za  id_pr
– id_pr  nazw_pr
– id_to  nazwa
– id_to  cena
– {id_za, id_to}  ilosc

• UWAGA:

– BCNF eliminuje wszystkie

anomalie (redundancje)
ale może nie zachowywać
oryginalnych zależności
funkcyjnych

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

39

Przykład 2 (slajd 1)

• Baza danych dla przychodni

• Postać nieznormalizowana

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

40

Przykład 2 (slajd 2)

• Przekształcenie do 1NF

– Relacja: Przychodnia(id, data, pacjent, id_lek, nazw_lek, typ_bad, id_lab,

nazw_lab)

– Klucze:

{id, typ_bad}

– Zależności:

• id  data, pacjent, id_lek
• id_lek  nazw_lek
• {id, typ_bad}  id_lab
• id_lab  typ_bad, nazw_lab

• Ńie jest w 2NF (jest klucz złożony,

data

,

pacjent

,

id_lek

zależą od części

klucza a nie od całości

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

41

Przykład 2 (slajd 3)

• Przekształcenie do 2NF
• Relacje:

– Wizyty(id, data, pacjent, id_lek, nazw_lek)
– Badania(id, typ_bad, id_lab, nazw_lab)

• Nie jest w 3NF, bo

id  id_lek  nazw_lek

oraz

{id, typ_bad}  id_lab  nazw_lab

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

42

Przykład 2 (slajd 4)

• Przekształcenie do 3NF
• Relacje:

– Wizyty(id, data, pacjent, id_lek)
– Lekarze(id_lek, nazw_lek)
– Badania(id, typ_bad, id_lab)
– Laboranci(id_lab, nazw_lab)

• Nie jest BCNF, ponieważ dla relacji

Badani

mamy zależności:

– {id, typ_bad}  id_lab
– id_lab  typ_bad
– id_lab

nie jest kluczem,

a

typ_bad

od niego zależy

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

43

Przykład 2 (slajd 5)

• Przekształcenie do 4NF
• Relacje:

– Wizyty(id, data, pacjent, id_lek)
– Lekarze(id_lek, nazw_lek)
– Badania(id, id_lab)
– Laboranci(id_lab, nazw_lab, typ_bad)

• Wszystkie atrybuty zależą tylko od kluczy

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

44

Zrób to sam

2013-01-10

Bazy danych / Krzysztof Molenda / WSEI w Krakowie

45

• Przeprowadź proces normalizacji powyższej tabeli.