wykład 1

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.

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

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.

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

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

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

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.

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)

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)

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

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)

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)

Graf

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.

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)

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

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)

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)

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)

Document Outline