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.