05-normalizacja

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Etapy projektowania baz danych:

Specyfikacja wymaga

ytkownika

- okre

lenie zjawisk,

dost

pno

ci i u

yteczno

ci danych, ich formatu i sposobów oblicze

cele, zakres i kontekst systemu

Projektowanie konceptualne

- projektowanie schematu E–R bazy.

ycie modelu E–R wpływa równie

na realizacj

pozostałych faz.

Specyfikacja wymaga

funkcjonalnych

- dokładny opis wymaga

klienta i wszystkich przyszłych u

ytkowników systemu

Projektowanie logiczne i fizyczne

Implementacja

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Projektowanie bazy danych:

Projektowanie logicznej struktury bazy:

•

Etap I:

okre

lenie encji i zdefiniowanie atrybutów opisuj

cych encje

–

przyporz

dkowanie encji do zjawisk

–

standaryzacja nazw i formatów

–

identyfikacja

ródeł danych

•

Etap II:

okre

lenie zwi

zków mi

dzy encjami

–

identyfikacja typu zwi

zków (relacji) (1-1, 1-M, N-M)

•

Etap III:

normalizacja relacji

–

obni

enie redundancji i wyeliminowanie anomalii (usuwania, wstawiania i

aktualizacji)

Projektowanie fizycznej struktury bazy:

•

nało

enie struktury logicznej na fizyczne urz

dzenia

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Przykład wad bazy danych:

Rozwa

my schemat relacji

•

pracownik_oddzialu = <nazwa_oddzialu, numer_oddzialu,
adres_oddzialu, pesel, imie, nazwisko, stanowisko,
wynagrodzenie>

Redundancja

•

Dane

nazwa_oddzialu, numer_oddzialu, adres_oddzialu

pami

tane

dla ka

dego pracownika

•

Marnowanie miejsca (przestrzeni potrzebnej dla przechowywania danych)

•

Komplikacje

Brak mo

liwo

ci reprezentowania pewnych informacji

•

Nie mo

na reprezentowa

informacji o oddziałach, których powołanie dopiero jest

planowane i nie zatrudniły jeszcze pracowników

•

Rozwi

zaniem mogło by by

zastosowanie warto

ci NULL, ale takie rozwi

zanie

tak

e stwarza pewne problemy

•

Nie mo

emy zaprezentowa

w prosty sposób wszystkich pracowników z danego

miasta, poniewa

miejscowo

ść

nie jest wyodr

bnionym atrybutem

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Rodzaje anomalii:

Anomalia doł

czania

- wad

jest to,

e musimy wpisywa

wszystko

albo nic, np. planuje si

powołanie nowego oddziału, nie mo

emy

jednak zapisa

w bazie miejscowo

ci, adresu i nazwy zakupionego

budynku, dopóki nowy oddział nie zatrudni pracowników

Anomalia aktualizacji

- np. oddział firmy został przeniesiony, przez

co musimy aktualizowa

jego adres dla ka

dego pracownika, a przez

przypadek omijamy Jana Kowalskiego

Anomalia usuwania

– zamkni

to oddział firmy, w zwi

zku z czym

usuni

to z bazy wszystkie rekordy zawieraj

ce jego nazw

, tym

samym usuni

to wszystkie dane dotycz

ce pracowników

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Dekompozycja:

zdekomponowa

schemat relacji –

pracownik_oddzialu:

•

oddzial = <nazwa_oddzialu, numer_oddzialu,
miejscowosc_oddzialu, adres_oddzialu>

•

pracownik = <numer_oddzialu, pesel, imie, nazwisko,
stanowisko, wynagrodzenie>

Wszystkie atrybuty

oryginalnego schematu (R) musz

pojawi

dekompozycji (R

, R

R = R

∪

W przypadku gdy relacja nie posiada wła

ciwej postaci nale

dokona

dekompozycji relacji R na <R

, R

, ..., R

Proces „dochodzenia” do „wła

ciwej” postaci okre

la si

mianem

normalizacji

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Pierwsza posta

normalna

Relacja jest w pierwszej postaci normalnej, je

li ka

da warto

ść

atrybutu w ka

dej krotce tej relacji jest

warto

elementarn

, czyli

nierozkładaln

Relacja jest w pierwszej postaci normalnej, je

li nie ma

powtarzaj

cych si

grup

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Zale

ci funkcyjne i wielowarto

ciowe:

Zale

ść

funkcyjna

oznacza,

e znaj

c warto

ść

jednego atrybutu, zawsze

emy okre

warto

ść

innego. Symbolem stosowanym w teorii relacji jest

strzałka umieszczona pomi

dzy dwoma atrybutami, na przykład:

→

(X okre

la Y)

przykład:

gdy znamy numer PESEL naszego pracownika, mo

emy okre

jego

nazwisko

Zale

ść

wielowarto

ciowa

oznacza,

e znaj

c warto

ść

jednego atrybutu,

emy zawsze okre

warto

ci zbioru innego atrybutu. W teorii relacji

ywa si

symbolu zale

ci wielowarto

ciowej w postaci podwójnej strzałki,

na przykład:

→→

(X okre

la wiele Y)

przykład:

znaj

c numer oddziału mo

emy okre

nazwiska wszystkich zatrudnionych

pracowników

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Teoria postaci normalnych relacji:

Formalnie zale

ść

danych mo

na zdefiniowa

nast

puj

co.

Schemat relacji oznaczamy przez R<A

...A

>, gdzie A

...A

atrybutami relacji. Niech X i Y b

podzbiorami zbioru atrybutów.

⊂

...A

}, Y

⊂

...A

Zale

ść

danych zapisujemy w postaci:

→

i mówimy,

e podzbiór atrybutów Y zale

y funkcyjnie od podzbioru

atrybutów X, je

eli nie jest mo

liwe, by relacja R zawierała dwie krotki

maj

ce składowe zgodne (tzn. identyczne dla wszystkich atrybutów ze

zbioru X) i jednocze

nie co najmniej jedn

niezgodn

składow

dla

atrybutów ze zbioru Y.

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Klucz:

Kluczem relacji

nazywamy taki zbiór atrybutów tej relacji, których

kombinacje warto

ci jednoznacznie identyfikuj

krotk

tej relacji

aden podzbiór tego zbioru nie posiada tej własno

ci. W kluczu nie

e zawiera

warto

ść

NULL.

Klucz jest

kluczem prostym

, je

eli powy

ej opisany zbiór jest

jednoelementowy - w przeciwnym razie mówimy o

kluczu zło

onym

W ogólno

ci, w relacji mo

na wyró

wiele kluczy, które nazywamy

kluczami potencjalnymi

. Wybrany klucz spo

ród kluczy potencjalnych

nazywamy

kluczem głównym

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Druga i trzecia posta

normalna:

Relacja jest w drugiej postaci normalnej, je

li jest w 1PN oraz ka

dy atrybut tej

relacji

nie wchodz

w skład

adnego klucza potencjalnego jest w

pełni

funkcyjnie zale

od wszystkich kluczy potencjalnych tej relacji.

Relacja jest w 2PN je

eli ka

dy atrybut nie wchodz

cy w skład klucza

zale

od klucza a nie od jego cz

ęś

Relacja b

ca w pierwszej postaci normalnej, jest równocze

nie w drugiej

postaci normalnej, je

li wszystkie jej klucze potencjalne s

kluczami prostymi.

Dana relacja jest w trzeciej postaci normalnej, je

li jest ona w drugiej postaci

normalnej i ka

dy jej atrybut nie wchodz

cy w skład

adnego klucza

potencjalnego

nie jest przechodnio funkcyjnie zale

adnego klucza

potencjalnego tej relacji.

Inaczej mówi

c, wszystkie niekluczowe kolumny s

okre

lane kluczem,

całym kluczem i tylko kluczem, „…tak nam dopomó

Codd”

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Posta

normalna Boyce’a-Codd’a

Dana relacja r o schemacie R jest w postaci normalnej

Boyce’a-

Codd’a

, je

eli dla ka

dej zale

ci funkcyjnej X

→

A w R spełniony

jest nast

puj

cy warunek: X jest nadkluczem schematu R .

Nadklucz

– dowolny podzbiór atrybutów B z A, taki,

e zachodzi

zale

ść

funkcyjna B

→

A (warto

ść

dego atrybutu jest

jednoznacznie zdeterminowana przez warto

ci atrybutów zbioru B).

Jednym z nadkluczy jest zawsze zbiór wszystkich atrybutów A.

Kluczem

- nazywamy ka

dy minimalny nadklucz

(nie zawieraj

cy w sobie

adnego innego nadklucza).

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Zale

ci wielowarto

ciowe:

nr_albumu

→→

przedmiot

Nr_albumu

→→

forma

Zwi

zek pomi

dzy zbiorami atrybutów X i Y;

Niezale

ść

zbiorów atrybutów Y, Z. Zbiory te s

zwi

zane

ze sob

rednio poprzez zbiór atrybutów X.

Wyst

pienie zale

wielowarto

ciowej X

→→

Y w

relacji o schemacie R = XYZ wyra

dwa fakty:

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Trywialna zale

ść

wielowarto

ciowa:

Zale

ść

wielowarto

ciowa X

→→

Y w relacji r(R)

nazywamy

zale

trywialn

, je

eli

•

zbiór Y jest podzbiorem X, lub

•

∪

Y = R

Zale

ść

nazywamy trywialn

, gdy

jest ona spełniona

dla dowolnej instancji r schematu R.

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Czwarta posta

normalna:

Relacja r o schemacie R jest w

czwartej postaci normalnej

wzgl

dem zbioru zale

ci wielowarto

ciowych MVD je

eli jest ona w

3PN i dla ka

dej zale

ci wielowarto

ciowej X

→→

⊂

MVD

zale

ść

ta jest trywialna lub X jest nadkluczem schematu R.

Przedstawiony uprzednio schemat relacji

student

nie jest w 4PN

gdy

zale

ść

wielowarto

ciowa, np.

nr_albumu

→→

przedmiot

nie jest trywialna jak równie

nr_albumu

nie jest nadkluczem

schematu

student

Schematy relacji

student1

student2

, uzyskane w wyniku

dekompozycji, s

w 4PN gdy

dy z tych schematów zawiera

trywialn

zale

ść

wielowarto

ciow

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

ta posta

normalna:

Dana relacja

o schemacie

jest w

tej postaci normalnej

wtedy i tylko

wtedy, gdy jest w czwartej postaci normalnej i w przypadku wyst

powania w

niej poł

czeniowej zale

ci funkcyjnej

*R<R

,..., R

zale

ść

ta wynika z zale

ci atrybutów od klucza.

Mówimy,

e w schemacie relacji

R<A

, ..., A

wyst

puje

poł

czeniowa

zale

ść

funkcyjna

(co zapisuje si

*R<R

, ..., R

) wtedy i tylko

wtedy, gdy mo

liwa jest dekompozycja relacji

r(R)

na relacje

, ..., r

taka,

e relacj

pierwotn

na zrekonstruowa

przez wykonanie

sekwencji operacji poł

czenia relacji

, ..., r

Podstaw

tej postaci normalnej (5PN), zwanej tak

postaci

normaln

zł

czenie-rzut (PNZR)

, jest koncepcja zł

czenia bezstratnego lub brak

anomalii zł

czenie-rzut. Taki problem wyst

puje w przypadku zale

n-warto

ciowej, gdzie n > 2. Szybki sposób sprawdzenia zgodno

ci z 5PN

polega na sprawdzeniu, czy tabela odpowiada 3PN oraz czy wszystkie klucze
kandyduj

ce s

pojedynczymi kolumnami.

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Podsumowanie:

Normalizacja ma na celu takie przekształcenie relacji, by unikn

ąć

redundancji i anomalii

Przekształcenie relacji do kolejnych postaci normalnych wi

ąŜ

e si

najcz

ęś

ciej ze

zmniejszeniem ilo

ci pami

potrzebnej do

przechowania informacji

Unikanie powtórze

pozwala na

łatwiejsz

i szybsz

aktualizacj

danych.

Doprowadzenie bazy do wysokiej postaci normalizacji mo

spowolni

odczyt

w du

ych bazach ze wzgl

du na skomplikowany

schemat danych.

W wi

kszo

ci przypadków po znormalizowaniu bazy danych

przychodzi kolej na rozwa

enie mo

liwo

ci wykonania

odwrotnej

operacji (denormalizacji)

, polegaj

cej na poł

czeniu niektórych

znormalizowanych tabel, a to z my

o przyspieszeniu dost

pu do

pewnych danych.