Krzysztof Regulski
AGH, WIMiIP, ZIP

Bazy Danych i SQL

- Projektowanie baz danych (2). Normalizacja.

2

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Etapy projektowania baz danych:

1.

Specyfikacja wymaga

ń

u

ż

ytkownika

- okre

ś

lenie zjawisk,

dost

ę

pno

ś

ci i u

ż

yteczno

ś

ci danych, ich formatu i sposobów oblicze

ń

,

cele, zakres i kontekst systemu

2.

Projektowanie konceptualne

- projektowanie schematu E–R bazy.

U

ż

ycie modelu E–R wpływa równie

ż

na realizacj

ę

pozostałych faz.

3.

Specyfikacja wymaga

ń

funkcjonalnych

- dokładny opis wymaga

ń

klienta i wszystkich przyszłych u

ż

ytkowników systemu

4.

Projektowanie logiczne i fizyczne

5.

Implementacja

3

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

4

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

s

ą

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

5

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

6

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Dekompozycja:

Mo

ż

na

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

ą

si

ę

pojawi

ć

w

dekompozycji (R

1

, R

2

):

R = R

1

∪

R

2

W przypadku gdy relacja nie posiada wła

ś

ciwej postaci nale

ż

y

dokona

ć

dekompozycji relacji R na <R

1

, R

2

, ..., R

n

>

Proces „dochodzenia” do „wła

ś

ciwej” postaci okre

ś

la si

ę

mianem

normalizacji

7

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Postacie normalne:

Pierwsza (1PN)

Druga (2PN)

Trzecia (3PN)

Boyce’a-Codd’a (PNBC)

Czwarta (4PN)

Pi

ą

ta (5PN)

8

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

ś

ci

ą

elementarn

ą

, czyli

nierozkładaln

ą

.

Relacja jest w pierwszej postaci normalnej, je

ś

li nie ma

powtarzaj

ą

cych si

ę

grup

.

9

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Przykład:

10

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Zale

ż

no

ś

ci funkcyjne i wielowarto

ś

ciowe:

Zale

ż

no

ść

funkcyjna

oznacza,

ż

e znaj

ą

c warto

ść

jednego atrybutu, zawsze

mo

ż

emy okre

ś

li

ć

warto

ść

innego. Symbolem stosowanym w teorii relacji jest

strzałka umieszczona pomi

ę

dzy dwoma atrybutami, na przykład:

X

→

Y

(X okre

ś

la Y)

przykład:

gdy znamy numer PESEL naszego pracownika, mo

ż

emy okre

ś

li

ć

jego

nazwisko

Zale

ż

no

ść

wielowarto

ś

ciowa

oznacza,

ż

e znaj

ą

c warto

ść

jednego atrybutu,

mo

ż

emy zawsze okre

ś

li

ć

warto

ś

ci zbioru innego atrybutu. W teorii relacji

u

ż

ywa si

ę

symbolu zale

ż

no

ś

ci wielowarto

ś

ciowej w postaci podwójnej strzałki,

na przykład:

X

→→

Y

(X okre

ś

la wiele Y)

przykład:

znaj

ą

c numer oddziału mo

ż

emy okre

ś

li

ć

nazwiska wszystkich zatrudnionych

pracowników

11

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Teoria postaci normalnych relacji:

Formalnie zale

ż

no

ść

danych mo

ż

na zdefiniowa

ć

nast

ę

puj

ą

co.

Schemat relacji oznaczamy przez R<A

1

...A

N

>, gdzie A

1

...A

N

s

ą

atrybutami relacji. Niech X i Y b

ę

d

ą

podzbiorami zbioru atrybutów.

X

⊂

{A

1

...A

N

}, Y

⊂

{A

1

...A

N

}.

Zale

ż

no

ść

danych zapisujemy w postaci:

X

→

Y

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.

12

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

ą

ka

ż

d

ą

krotk

ę

tej relacji

a

ż

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

ś

ci. W kluczu nie

mo

ż

e zawiera

ć

si

ę

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ó

ż

ni

ć

wiele kluczy, które nazywamy

kluczami potencjalnymi

. Wybrany klucz spo

ś

ród kluczy potencjalnych

nazywamy

kluczem głównym

.

13

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

ą

cy

w skład

ż

adnego klucza potencjalnego jest w

pełni

funkcyjnie zale

ż

ny

od wszystkich kluczy potencjalnych tej relacji.

Relacja jest w 2PN je

ż

eli ka

ż

dy atrybut nie wchodz

ą

cy w skład klucza

zale

ż

y

od klucza a nie od jego cz

ęś

ci

.

Relacja b

ę

d

ą

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

ż

ny

od

ż

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”

14

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Przykład:

Warto

ś

ci atrybutów nie s

ą

elementarne

15

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Przykład (c.d.):

Powtarzaj

ą

ce si

ę

grupy

Zale

ż

no

ś

ci funkcyjne

Klucz potencjalny:

<rodzaj_studiow, rok_studiow, rok_akademicki,

przedmiot, forma, termin, student_nr_albumu>

16

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Klucz główny relacji protokoly:

<id_przedmiot, termin, nr_albumu>

17

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

ż

no

ś

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

ż

no

ść

funkcyjna B

→

A (warto

ść

ka

ż

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).

18

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Zale

ż

no

ś

ci wielowarto

ś

ciowe:

nr_albumu

→→

przedmiot

Nr_albumu

→→

forma

Zwi

ą

zek pomi

ę

dzy zbiorami atrybutów X i Y;

Niezale

ż

no

ść

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

ą

zwi

ą

zane

ze sob

ą

po

ś

rednio poprzez zbiór atrybutów X.

Wyst

ą

pienie zale

ż

no

ś

ci

wielowarto

ś

ciowej X

→→

Y w

relacji o schemacie R = XYZ wyra

ż

a

dwa fakty:

19

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Modyfikacja relacji z zale

ż

no

ś

ciami wielowarto

ś

ciowymi:

Przykład:

Wchodzi w

ż

ycie ustawa o konieczno

ś

ci

prowadzenia laboratoriów ze
wszystkich przedmiotów, a ponadto
nasz student zapisał si

ę

na Ekonomi

ę

:

Dodane krotki

20

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

DEKOMPOZYCJA

DEKOMPOZYCJA

MODYFIKACJA

MODYFIKACJA

schemat

student

jest

niedekomponowalny bez

utraty informacji.

21

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Trywialna zale

ż

no

ść

wielowarto

ś

ciowa:

Zale

ż

no

ść

wielowarto

ś

ciowa X

→→

Y w relacji r(R)

nazywamy

zale

ż

no

ś

ci

ą

trywialn

ą

, je

ż

eli

•

zbiór Y jest podzbiorem X, lub

•

X

∪

∪

∪

∪

Y = R

Zale

ż

no

ść

nazywamy trywialn

ą

, gdy

ż

jest ona spełniona

dla dowolnej instancji r schematu R.

22

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

ż

no

ś

ci wielowarto

ś

ciowych MVD je

ż

eli jest ona w

3PN i dla ka

ż

dej zale

ż

no

ś

ci wielowarto

ś

ciowej X

→→

Y

⊂

MVD

zale

ż

no

ść

ta jest trywialna lub X jest nadkluczem schematu R.

Przedstawiony uprzednio schemat relacji

student

nie jest w 4PN

gdy

ż

zale

ż

no

ść

wielowarto

ś

ciowa, np.

nr_albumu

→→

przedmiot

nie jest trywialna jak równie

ż

nr_albumu

nie jest nadkluczem

schematu

student

.

Schematy relacji

student1

i

student2

, uzyskane w wyniku

dekompozycji, s

ą

w 4PN gdy

ż

ka

ż

dy z tych schematów zawiera

trywialn

ą

zale

ż

no

ść

wielowarto

ś

ciow

ą

.

23

Kraków, 2006

str.

K. Regulski, ZIP, v.2.0

Pi

ą

ta posta

ć

normalna:

Dana relacja

r

o schemacie

R

jest w

pi

ą

tej postaci normalnej

wtedy i tylko

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

ę

powania w

niej poł

ą

czeniowej zale

ż

no

ś

ci funkcyjnej

*R<R

1

,..., R

m

>

zale

ż

no

ść

ta wynika z zale

ż

no

ś

ci atrybutów od klucza.

Mówimy,

ż

e w schemacie relacji

R<A

1

, ..., A

n

>

wyst

ę

puje

poł

ą

czeniowa

zale

ż

no

ść

funkcyjna

(co zapisuje si

ę

:

*R<R

1

, ..., R

n

>

) wtedy i tylko

wtedy, gdy mo

ż

liwa jest dekompozycja relacji

r(R)

na relacje

r

1

, ..., r

n

taka,

ż

e relacj

ę

pierwotn

ą

r

mo

ż

na zrekonstruowa

ć

przez wykonanie

sekwencji operacji poł

ą

czenia relacji

r

1

, ..., r

m

.

Podstaw

ą

pi

ą

tej postaci normalnej (5PN), zwanej tak

ż

e

postaci

ą

normaln

ą

zł

ą

czenie-rzut (PNZR)

, jest koncepcja zł

ą

czenia bezstratnego lub brak

anomalii zł

ą

czenie-rzut. Taki problem wyst

ę

puje w przypadku zale

ż

no

ś

ci

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.

24

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

ę

ci

potrzebnej do

przechowania informacji

.

Unikanie powtórze

ń

pozwala na

łatwiejsz

ą

i szybsz

ą

aktualizacj

ę

danych.

Doprowadzenie bazy do wysokiej postaci normalizacji mo

ż

e

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

ś

l

ą

o przyspieszeniu dost

ę

pu do

pewnych danych.