1
wykład
normalizacja schematów
logicznych relacji
wykład przygotował: dr inż. Janusz Dudczyk
2
Plan wykładu
Motywacja
Normalizacja
Postacie normalne
Celem niniejszego wykładu jest przedstawienie i omówienie procesu normalizacji. Proces
normalizacji traktujemy jako proces, podczas którego schematy relacji posiadające niepożądane
cechy są dekomponowane na mniejsze schematy relacji o pożądanych własnościach. Wykład
rozpoczniemy od krótkiego przykładu motywacyjnego, ilustrującego problem. Następnie,
wprowadzimy pojęcie zależności funkcyjnych stanowiących punkt wyjścia procesu normalizacji.
Następnie przejdziemy do omówienia kolejnych postaci normalnych.
3
Motywacja (1)
Dana jest następująca relacja Dostawcy :
Rozważmy następujący przykład. Dana jest następująca relacja Dostawcy, jak na slajdzie,
składająca się z 4 atrybutów. Załóżmy, że atrybut nazwisko jest unikalny, to jest nie ma dwóch
dostawców o tym samym nazwisku. Relacja Dostawcy zawiera informacje o dostawcach (o ich
adresach), dostarczanych produktach i cenach dostarczanych produktów.
4
Motywacja (2)
Analizując relację Dostawcy zauważmy, że relacja ta charakteryzuje się następującymi cechami. Po
pierwsze, obserwujemy
redundancję danych
– adres dostawcy jest pamiętany tyle razy ile różnych
produktów dany dostawca dostarcza. Problem redundancji danych nie sprowadza się do problemu
zajętości pamięci,
aktualnie pamięci są bardzo tanie, lecz problemu potencjalnej niespójności danych. W momencie
zmiany adresu dostawcy, zmiana ta musi być odzwierciedlona we wszystkich krotkach
zawierających adres dostawcy. W przeciwnym razie pojawi się problem spójności danych. Po drugie,
obserwujemy tzw.
anomalię wprowadzania
danych. Załóżmy, że chcemy wprowadzić informację o
nowym dostawcy, tj. jego nazwisko i adres. Niestety, informacji tej nie można wprowadzić do relacji
Dostawca tak długo, jak długo dostawca nie dostarcza żadnych produktów. Po trzecie, obserwujemy
anomalię usuwania
danych. Załóżmy, że rezygnujemy z usług dostawcy Nowak. Usuwając
informację o dostawach Nowaka mimo woli usuwamy informacje o samym dostawcy Nowak.
Wreszcie, obserwujemy
anomalię uaktualniania
danych. Aktualizując adres dostawcy, jak już
wspominaliśmy, aktualizację tę musimy wprowadzić do wszystkich krotek zawierających adres
dostawcy.
Reasumując, schemat relacji Dostawca posiada szereg niepożądanych własności, które w
późniejszym czasie będą utrudniały przygotowanie aplikacji operującej na tej relacji. Zauważmy, że
rozwiązaniem wszystkich omówionych problemów jest dekompozycja relacji Dostawca na dwie
relacje: Dostawca i Dostawy.
Załóżmy, że atrybut Nazwisko jest
unikalny, tj. nie ma dwóch dostawców o
tym samym nazwisku.
Cechy relacji Dostawca:
redundancja danych - problem spójności
danych
anomalia wprowadzania danych
anomalia usuwania danych
anomalia uaktualniania danych
Rozwiązaniem: dekompozycja relacji
Dostawca na dwie relacje: Dostawca i
Dostawy
5
Motywacja (3)
Dekompozycja bez utraty informacji
Relacja Dostawca zawiera informacje o dostawcach, natomiast relacja Dostawy zawiera
informacje o dostarczanych produktach i ich cenach. Zauważmy, że w przypadku relacji
Dostawca adres dostawcy jest pamiętany tylko w jednej krotce – brak redundancji danych.
Zauważmy również, że dekompozycja rozwiązuje problem anomalii wstawiania – informacje o
nowym dostawcy możemy wstawić do relacji Dostawca, nawet jeżeli dostawca ten nie dostarcza
żadnych produktów. Dekompozycja ta rozwiązuje również problem anomalii usuwania –
usunięcie informacji o dostawach z relacji Dostawy nie pociąga za sobą usunięcia informacji o
samych dostawcach. Dekompozycja rozwiązuje również problem anomalii aktualizacji – zmiana
adresu dostawcy dotyczy wyłącznie jednej krotki. Zauważmy, że dekompozycja relacji Dostawca
na relacje Dostawca i Dostawy jest dekompozycją bez utraty informacji w tym sensie, że łącząc
relację Dostawca i Dostawy wg. atrybutu połączeniowego Nazwisko możemy odtworzyć
oryginalną zawartość relacji Dostawca.
6
Normalizacja
Proces normalizacji relacji można traktować jako 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:
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. Zanim przejdziemy do przedstawienia
postaci normalnych przypomnimy podstawowe pojęcia dotyczące schematu relacji.
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
Własność zachowania zależności - wszystkie
zależności
funkcyjne są reprezentowane w pojedynczych
schematach
relacji
7
normalizacja
Relacja jest w trzeciej postaci normalnej
(3PN 3NF)
wtedy i tylko
wtedy, gdy: jest w drugiej postaci normalnej i żaden atrybut, nie będący
kluczem, nie jest funkcjonalnie związany żadnym innym atrybutem, nie
będącym również kluczem.
Relacja jest w pierwszej postaci normalnej (1PN 1NF) wtedy i tylko
wtedy, gdy nie ma powtarzających się grup i każdy atrybut jest w
postaci atomowej.
Relacja jest w drugiej postaci normalnej (2PN 2NF) wtedy i tylko
wtedy, gdy: jest w pierwszej postaci normalnej i każdy niekluczowy
atrybut jest zależny od wszystkich części klucza głównego.
Zapewnienie, że każda informacja jest
reprezentowana w modelu encji tylko raz
8
normalizacja – receptura
1PN
Każdy atrybut musi mieć jedną wartość dla każdego wystąpienia jego encji
w danym momencie czasu
Przejście z postaci 0PN do 1PN:
• usunięcie wielowartościowych atrybutów z encji w 0PN i
utworzenie dla niej nowej encji
• skopiowanie unikalnego identyfikatora do nowej encji - będzie on
prawdopodobnie stanowił część identyfikatora unikalnego dla tej nowej
encji
2PN
Wartość każdego atrybutu musi zależeć od całego identyfikatora jego encji.
Przejście z postaci 1PN do 2PN:
• usunięcie wszystkich częściowo zależnych atrybutów i utworzenie dla nich
nowej encji
• skopiowanie części identyfikatora z encji pierwotnej (od której zależne są
usunięte
atrybuty) do tej nowej encji
3PN
Wartość każdego atrybutu nie może zależeć od niczego innego poza
identyfikatorem unikalnym
Przejście z postaci 2PN do 3PN:
• należy usunąć atrybuty niezależne i wtawić je do nowej encji
Uwaga: ta nowa encja potrzebuje identyfikatora unikalnego
9
definicje
Normalizacja schematu relacji jest sformalizowaną procedurą, w
wyniku której eliminujemy redundancje (powtarzanie się) danych,
ich niespójność oraz anomalie.
Normalizacja opiera się na zależności funkcjonalnej
atrybutów i polega na dekompozycji początkowego schematu
relacji na kilka innych. Postacie normalne są kolejno numerowane i
im wyższy numer, tym projekt BD powinien być lepszy – mniej
podatny na anomalie wstawiania, aktualizacji i usuwania.
Normalizacja powoduje zwiększenie schematów relacji (tabel)
Dobrze zorganizowana BD powinna być przynajmniej w trzeciej
postaci normalnej.
10
zależność funkcyjna
atrybutów
Atrybut B relacji R jest funkcyjnie zależny od atrybutu A
tej relacji,
A B
jeżeli zawsze każdej wartości a atrybutu A odpowiada
więcej niż jedna wartość b atrybutu B.
Stwierdzenie, że atrybut B jest funkcyjnie zależny od atrybutu A
jest równoważne stwierdzeniu, że atrybut A jednoznacznie
wyznacza funkcyjnie (identyfikuje) atrybut B.
Przykład:
W schemacie relacji: Osoba(PESEL, Nazwisko) atrybut PESEL
jednoznacznie określa nazwisko osoby (atrybut Nazwisko jest funkcyjnie
zależny do atrybutu PESEL), czyli:
PESEL
Nazwisko
przy czym dane nazwisko może posiadać więcej niż jedna osoba (a więc
PESEL nie jest funkcyjnie zależny od Nazwiska)
11
pełna zależność funkcyjna
atrybutów
Atrybut B relacji R jest w pełni funkcyjnie zależny od
zbioru atrybutów A tej relacji,
A B
jeżeli jest funkcyjnie zależny od A, ale nie jest funkcyjnie
zależny od żadengo podzbioru zbioru A.
Przykład:
Dany jest schemat relacji
EGZAMINY ( Student, Przedmiot, Data,
Ocena)
W schemacie relacji zachodzą zależności:
(Student, Przedmiot)
Data
(Student, Przedmiot) Ocena
czyli atrybut DATA (podobnie jak Ocena) jest w pełni funkcyjnie zależny od
klucza głównego złożonego (Student, Przedmiot) (nie jest funkcyjnie zalezny
ani od atrybutu Student ani od atrybutu Przedmiot)
12
pierwsza postać normalna
1PN
Schemat relacji R znajduje się w pierwszej postaci
normalnej(1NF), jeżeli wartości atrybutów są
atomowe (niepodzielne, nierozkładalne)
Przykłady:
KLIENT (NrKlienta, Nazwisko, Imię, Miasto, Ulica)
KASETA (NrKasety, Opis)
FILM (KodFilmu, Tytuł, CzasTrwania)
GATUNEK (KodGatunku, Rodzaj)
OSOBA (NrOsoby, Nazwisko, Imię, ImionaDzieci,
DatyUrDzieci)
13
druga postać normalna 2PN
Schemat relacji R znajduje się w drugiej postaci
normalnej (2PN), jeżeli jest w 1PN i każdy atrybut
schematu relacji, nie wchodzący w skład żadnego
klucza kandydującego, jest w pełni funkcyjnie
zależny od wszystkich kluczy kandydujących
Każdy schemat relacji w 1PN posiadający proste klucze kandydujące
jest w 2PN
W celu uzyskania 2PN należy podzielić daną relację na kilka
innych (na ogół o mniejszej liczbie atrybutów) tak aby we
wszystkich relacjach atrybuty były w pełni funkcyjnie zależne od
klucza.
Przykład ogólny:
Schemat relacji R (A, B, C, D) w którym zachodzą zależności:
{A, B} C, {A, B} D, A C należy zastąpić 2-ma relacjami:
R1 (A, B, C) w którym {A, B} C oraz
R2 (A, D) w którym A D
14
druga postać normalna 2PN
Przykład:
Mamy danych schemat relacji do przechowywania informacji o
dzieciach pracowników:
OSOBA (PESEL, Nazwisko, Imię, ImięDziecka, DataUrDziecka)
W schemacie tym istnieją następujące zależności funkcyjne:
PESEL Nazwisko
PESEL Imię,
{PESEL, ImięDziecka} DataUrDziecka
Kluczem w relacji Osoba jest zbiór {PESEL, ImięDziecka}. Atrybuty
niekluczowe Nazwisko, Imię nie są w pełni zależne od klucza (bo zależą
funkcyjnie tylko od jego części – PESEL) czyli schemat nie jest w 2PN.
Należy go podzielić na 2 schematy relacji:
DOROSŁY (PESEL, Nazwisko, Imię)
DZIECKO (PESEL, ImięDziecka, DataUrDziecka)
15
zależność funkcyjna
przechodnia
Niech A, B, C będą trzema rozłącznymi
podzbiorami atrybutów danej relacji R. Podzbiór
atrybutów C jest przechodnio (tranzytywnie)
funkcyjnie zależny od podzbioru atrybutów A co
zapisujemy
A ➔ C
jeżeli
A B,
B C, B A, C A,
(B zależy funkcyjnie od A, C zależy funkcyjnie od B, A nie zależy
funkcyjnie od B i A nie zależy funkcyjnie od C)
A
B
C
Graf
16
zależność funkcyjna
przechodnia
Przykład:
Mamy danych schemat relacji do przechowywania informacji o
fakturach:
FAKTURA (NrFaktury, NazwaKlienta, AdresKlienta)
W schemacie tym istnieją następujące zależności funkcyjne:
NrFaktury NazwaKlienta
NazwaKlienta AdresKlienta
Atrybut AdresKlienta jest przechodnio funkcyjnie zależny
od NrFaktury ponieważ zależy od atrybutu NazwaKlienta, który
jest zależny funkcyjnie od NrFaktury. Z kolei NrFaktury nie jest
zależny funkcyjnie od atrybutu NazwaKlienta ponieważ jeden
klient może mieć wiele faktur. Również NrFaktury nie zależy
funkcyjnie od atrybutu AdresKlienta, ponieważ dany adres może
być na wielu fakturach.
17
trzecia postać normalna 3PN
Schemat relacji R znajduje się w trzeciej postaci
normalnej (3PN), jeżeli jest w 2PN i każdy
atrybut niekluczowy (nie wchodzący w skład
żadnego klucza kandydującego) nie jest
przechodnio funkcyjnie zależny od żadnego
klucza kandydującego (czyli wszystkie atrybuty
niekluczowe są wzajemnie niezależne)
Przykład ogólny:
Schemat relacji R (A, B, C) w którym zachodzą zależności:
A B, B C czyli A ➔ C należy zastąpić 2-ma relacjami
R1 (A, B) oraz R2 (B, C)
Przykład FAKTURA w 3PN:
WYKAZ (NrFaktury, NazwaKlienta)
KLIENT (NazwaKlienta, AdresKlienta)
18
trzecia postać normalna 3PN
Przykład FAKTURA:
w 2PN
FAKTURA (NrFaktury, NazwaKlienta, AdresKlienta)
w 3PN
WYKAZ (NrFaktury, NazwaKlienta)
KLIENT (NazwaKlienta, AdresKlienta)
ALE UWAGA !!!
w 3PN
ZAJĘCIA (Student, Kurs, Wykładowca)
{Student, Kurs} Wykładowca (student może uczęszczać na dany kurs
tylko do
jednego wykładowcy)
Wykładowca Kurs (każdy wykładowca prowadzi dokładnie jeden kurs)
Schemat ZAJĘCIA jest w 3PN ale nadal występują anomalie usuwania
danych (po usunięciu informacji o ostatnim studencie tracimy
informacje o kursie) oraz anomalie dodawania danych (nie można
dopisać kursu i wykładowcy, zanim na kurs nie zapisze się co najmniej
jeden student)
ROZWIĄZANIE - PNBC
19
PNBC – postać normalna Boyce’a-
Codda
jest to poprawiona wersja 3PN. Schemat relacji R jest
w PNBC jeżeli A B i B nie zawiera się w A, zbiór A
zawiera klucz (tzn. jest nadkluczem), przy czym Ai B
są zbiorami atrybutów relacji. Wszystkie zależności
funkcyjne są determinowane przez klucze (wszystkie
atrybuty zależą tylko i wyłącznie od klucza)
W praktyce muszą być spełnione 3 warunki:
1. w schemacie relacji muszą być co najmniej dwa klucze kandydujące
2. co najmniej dwa klucze kandydujące muszą być kluczami złożonymi
3. klucze kandydujące muszą mieć wspólne atrybuty
ZAJĘCIA (Student, Kurs, Wykładowca)
1. 2 klucze kandydujące {Student, Kurs} oraz {Student,
Wykładowca}
2. oba są kluczami złożonymi
3. mają wspólny atrybut {Student}
PNBC
PRZYDZIAŁ (Wykładowca, Kurs)
ZAJĘCIA (Student, Kurs)
20
przykład procesu
normalizacji
21
1PN, 2PN i 3PN itd ?
W praktyce mamy 8 postaci normalnych
1. 0PN – zerowa postać normalna (NF – normal form)
2. 1PN – pierwsza postać normalna
3. 2PN – druga postać normalna
4. 3PN – trzecia postać normalna –
ostateczna postać większości
modeli implementacyjnych
5. PNBC – postać normalna Boyce’a-Codda
6. 4PN - czwarta postać normalna
7. 5PN – piąta postać normalna
8. PNKD - postać normalna klucza dziedziny
Uproszczona idea procesu normalizacji
• bez powtórzeń (1PN)
• atrybuty zależą od klucza (2PN)
• od całego klucza (3PN)
• i niczego innego jak tylko klucza (PNBC)
22
kolejne postaci
normalne ??
KROKI i DEFINICJE
definicja zależności wielowartościowej
definicja zależności trywialnej
4PN – schemat relacji jest w 4PN jeśli jest w 3PN i nie
zawiera wielowartościowej nietrywialnej zależności atrybutów
definicja zależności złączenia
5PN – schemat relacji R jest w 5PN gdy każda zależność
złączenia w R jest implikowana kluczami kandydującymi
schematu relacji. Inaczej, schemat który jest w 4PN jest w 5PN
jeżeli nie istnieje odwracalny rozkład na schematy relacji
przykład 5PN schematu DOSTAWY (Dostawca, Towar, Odbiorca)
KTO_CO (Dostawca, Towar)
KTO_KOMU (Dostawca, Odbiorca)
CO_KOMU (TOWAR, Odbiorca)
PNKD – zapewnia, że wszystkie więzy stanowią logiczną
konsekwencję definicji kluczy i dziedziny (PN Klucza Dziedziny)
DENORMALIZACJA (zmniejszenie w celu uzyskania zdolności
implementacyjnej)
23
KONIEC WYKŁADU