Projektowanie struktury logicznej (schematu)

relacyjnych baz danych

Wykład

S. Kozielski

Projektowanie struktury (logicznej) baz danych

Modelowanie zwi

ą

zków encji – elementy diagramów

encja

niezale

ż

ny byt,

jednoznacznie
identyfikowalny

zwi

ą

zek

ł

ą

czy encje

atrybut

opisuje encje
i zwi

ą

zki

reprezentuje zbiór
obiektów opisanych tymi
samymi cechami
(własno

ś

ciami,

atrybutami)

Przykłady diagramów zwi

ą

zków encji (1)

zalicza

studiuje

przedmiot

kierunek

student

N

M

1

N

Przykłady diagramów zwi

ą

zków encji (2)

wykonuje

nale

ż

y

temat

zespół

pracownik

N

M

1

N

Przykłady diagramów zwi

ą

zków encji (3)

za

ż

ywa

le

ż

y

lekarstwo

oddział

chory

N

M

1

N

zwi

ą

zek

wyst

ą

pienie – Grabski studiuje informatyk

ę

typ - studiuje

encja

wyst

ą

pienie - Grabski

typ - student

atrybut-odwzorowanie

typ zwi

ą

zku zbiór warto

ś

ci

typ encji

zbiór warto

ś

ci

student

integer

album

char(20)

char(50)

nazwisko

adres

student

album

nazwisko

adres

student

album

1

nazwisko

adres

j

ę

z_ob

przedmiot

id_p

prowadz

ą

cy

nazwa

studiuje

zalicza

podlega

kierunek

wydział

sem

ocena

id_k

id_w

dziekan

nazwa

nazwa

M

1

N

N

N

Algorytm tworzenia schematów relacji na

podstawie diagramu zwi

ą

zków encji

1) Utwórz schemat relacji dla ka

ż

dego typu encji. Do schematu tego wchodz

ą

wszystkie atrybuty proste (pojedyncze) opisuj

ą

ce encj

ę

. Kluczem schematu jest

klucz encji.

2) Utwórz dodatkowy schemat relacji dla ka

ż

dego atrybutu wielowarto

ś

ciowego.

Do schematu tego wchodzi klucz encji i dany atrybut wielowarto

ś

ciowy. Kluczem

schematu jest ca

ł

y schemat.

3) Utwórz schemat relacji dla ka

ż

dego typu zwi

ą

zku. Do schematu tego wchodz

ą

klucze encji powi

ą

zanych zwi

ą

zkiem oraz atrybuty w

ł

asne zwi

ą

zku. Klucz

schematu jest wyznaczany nast

ę

puj

ą

co:

• dla krotno

ś

ci 1:N – klucz encji wchodz

ą

cej do zwi

ą

zku przez kraw

ę

d

ź

N,

• dla krotno

ś

ci M:N – zło

ż

enie kluczy obu encji,

• dla krotno

ś

ci 1:1 – dowolny z kluczy obu encji,

4) Scal schematy o identycznych kluczach (optymalizacja struktury).

Schematy relacji utworzone dla diagramu

opisuj

ą

cego studentów

student (album, nazwisko, adres)

kierunek (id_k, nazwa)

wydział (id_w, nazwa, dziekan)

przedmiot (id_p, nazwa, prowadz

ą

cy)

j

ę

zyki (album, j

ę

zyk_obcy)

studiuje (album, id_k, sem)

podlega (id_k, id_w)

zalicza (album, id_p, ocena)

Schematy relacji po optymalizacji

studenci (album, nazwisko, adres, id_k, sem)

kierunki (id_k, nazwa, id_w)

wydziały (id_w, nazwa, dziekan)

przedmioty (id_p, nazwa, prowadz

ą

cy)

j

ę

zyki (album, j

ę

zyk_obcy)

zaliczenia (album, id_p, ocena)

Inna forma zapisu diagramów (narz

ę

dzia CASE)

studiuje

student

album
nazwisko
adres

kierunek

id_k
nazwa

Problem atrybutów wielowarto

ś

ciowych

student (album, nazwisko, adres)

j

ę

zyk_obcy (nazwa)

zna (album, nazwa, stopie

ń

)

Relacja (tablica)

j

ę

zyk_obcy

– pełni rol

ę

słownika

N

student

album

nazwisko

adres

nazwa

j

ę

zyk_obcy

stopie

ń

zna

M

Problem zwi

ą

zków 1 : 1

student (album, nazwisko, adres)

czytelnik (nr_karty, sta

ż

)

jest (album, nr_karty) -

problem wyboru klucza

1

student

album

nazwisko

adres

czytelnik

jest

sta

ż

1

nr_karty

student (album, nazwisko, adres)

czytelnik (nr_karty, sta

ż

)

jest (album, nr_karty) -

problem wyboru klucza

Mo

ż

liwe rozwi

ą

zania:

1)

Klucz: nr_karty

Wtedy schemat:

studenci (album, nazwisko, adres),

czytelnik (nr_karty, sta

ż

, album)

2) Klucz

: album

Wtedy schemat:

studenci (album, nazwisko, adres, nr_karty),

czytelnik (nr_karty, sta

ż

)

3)

album i nr_karty –

klucze równowa

ż

ne Wtedy schemat:

studenci (album, nazwisko, adres, nr_karty, sta

ż

)

Zwi

ą

zek identyfikuj

ą

cy

encja wła

ś

cicielska

1

N

encja słaba

ID

nrp

nrz

Zespół

Dziecko

Pracownik

nazwisko

imi

ę

data_ur

nazwa

adres

imi

ę

ma

nale

ż

y

kierownik

Encja słaba:

- nie jest w pełni identyfikowalna przez swoje atrybuty

- posiada tylko klucz cz

ęś

ciowy

- jest identyfikowana przez klucz cz

ęś

ciowy + klucz encji wła

ś

cicielskiej

Zwi

ą

zek identyfikuj

ą

cy - wi

ąż

e encj

ę

słab

ą

z encj

ą

wła

ś

cicielsk

ą

Uzupełnienie algorytmu tworzenia schematów relacji na podstawie
diagramu zwi

ą

zków encji:

w przypadku encji słabej doł

ą

cz do klucza schematu tworzonej relacji

klucz encji wła

ś

cicielskiej

dziecko (nrp, imi

ę

, data_ur)

ma (nrp, imi

ę

)

Dwa zwi

ą

zki mi

ę

dzy dwiema encjami

pracownik (nrp, nazwisko)

dyplomant (album, nazwisko, adres)

prowadzi (nrp, album)

recenzuje (nrp, album)

po modyfikacji nazw i scaleniu:

pracownicy (nrp, nazwisko)

dyplomanci (album, nazwisko, adres, nrp_prowadz, nrp_rec)

nrp

dyplomant

album

nazwisko

adres

N

recenzuje

1

pracownik

N

prowadzi

1

nazwisko

Powi

ą

zanie encji samej z sob

ą

pracownik (nrp, nazwisko)

kieruje_podlega (nrp, nrp)

↑

↑

zwierzchnik podwładny

po modyfikacji nazw i scaleniu:

pracownicy (nrp, nazwisko, nrp_zwierzchnika)

zwierzchnik

nrp

N

pracownik

kieruje-
podlega

1

nazwisko

podwładny

Projektowanie struktury b. d. poprzez normalizacj

ę

schematu bazy danych

Punkt wyj

ś

cia: zbiór atrybutów A

1

, A

2

, A

3

, . . . , A

n

,

których warto

ś

ci chcemy przechowywa

ć

w bazie.

Pocz

ą

tkowy ca

ł

a b.d. jest widziana jako jedna relacja

o schemacie R = {A

1

, A

2

, A

3

, . . . , A

n

}.

Nast

ę

pnie schemat R dzielony jest na zbiór schematów

relacji w procesie normalizacji.

R

⇒

{ R

1

, R

2

, R

3

, . . . , R

k

}

Schematy tworzone w procesie normalizacji powinny

spełnia

ć

warunki kolejnych postaci normalnych.

5

2

nrp

Kasia, Ania, Krzy

ś

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Adam

Zabrze, ul. Wolno

ś

ci 123

Grabski

dziecko

adres

nazwisko

Definicja 1PN

Schemat relacji (relacja) jest w 1 PN (postaci

normalnej), je

ś

li dziedziny atrybutów tworz

ą

cych

schemat zawieraj

ą

jedynie warto

ś

ci atomowe,

tzn. nie s

ą

zbiorami, ci

ą

gami czy listami warto

ś

ci.

Relacja w 1PN

5

5

5

2

nrp

Ania

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Kasia

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Krzy

ś

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Adam

Zabrze, ul. Wolno

ś

ci 123

Grabski

dziecko

adres

nazwisko

Problemy zwi

ą

zane z redundancj

ą

• aktualizacja danych redundancyjnych – niebezpiecze

ń

stwo

utraty spójno

ś

ci bazy,

• anomalia usuwania (klucz główny oraz jego sk

ł

adowe nie

mog

ą

by

ć

puste).

• anomalia wstawiania

Relacja w 1PN

5

5

5

2

nrp

Ania

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Kasia

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Krzy

ś

Gliwice, ul. Zwyci

ę

stwa 33

Jaworek

Adam

Zabrze, ul. Wolno

ś

ci 123

Grabski

dziecko

adres

nazwisko

Zale

ż

no

ść

funkcyjna

X, Y – atrybuty, dom(X), dom(Y) – dziedziny atrybutów

Atrybut Y jest funkcyjnie zale

ż

ny od X, je

ś

li istnieje

odwzorowanie

f: dom(X)

→

dom (Y)

które ka

ż

dej warto

ś

ci z dziedziny X przyporz

ą

dkowuje

nie wi

ę

cej ni

ż

jedn

ą

warto

ść

z dziedziny Y.

Zapis uproszczony: X

→

Y

Przykłady zale

ż

no

ś

ci funkcyjnych

nrp

→

nazwisko

nrp

→

adres

nrp, dziecko

→

adres

Rola klucza w tworzeniu zale

ż

no

ś

ci funkcyjnych

K – klucz, A – atrybut niekluczowy

Z definicji klucza wynika,

ż

e zawsze zachodzi: K

→

A

Cz

ęś

ciowa zale

ż

no

ść

funkcyjna

Zało

ż

enie: zachodzi zale

ż

no

ść

funkcyjna: X

→

A

Je

ś

li dodatkowo spełniona jest zale

ż

no

ść

X’

→

A,

gdzie X’

⊂

X, to wtedy zale

ż

no

ść

X

→

A nazywamy

zale

ż

no

ś

ci

ą

cz

ęś

ciow

ą

.

Przykład
Zachodzi zale

ż

no

ść

:

nrp, dziecko

→

adres

ponadto zachodzi te

ż

zale

ż

no

ść

:

nrp

→

adres

wi

ę

c zale

ż

no

ść

:

nrp, dziecko

→

adres

jest zale

ż

no

ś

ci

ą

cz

ęś

ciow

ą

Definicja 2PN

Schemat relacji (relacja) jest w 2PN, je

ż

eli jest w 1 PN

i

ż

aden atrybut niekluczowy nie jest cz

ęś

ciowo zale

ż

ny

od klucza (od

ż

adnego z kandyduj

ą

cych kluczy relacji).

Przykład dekompozycji do 2PN

{nrp, nazwisko, adres, dziecko}

{nrp, nazwisko, adres}

{nrp, dziecko}

1PN

2PN

Przyk

ł

ad innej relacji

150

200

150

200

BK 303

BK 303

BW 202

BW 202

AEiI

AEiI

AEiI

AEiI

Inf

Inf

Inf

El

Grabski

Jaworek

Jaworek

Bukowy

kwota

temat

wydział

instytut

pracownik

Istniej

ą

ce zale

ż

no

ś

ci funkcyjne:

pracownik

→

instytut

instytut

→

wydział

pracownik

→

wydział

pracownik, temat

→

kwota

a ponadto

pracownik, temat

→

instytut

pracownik, temat

→

wydział

Przykład dekompozycji do 2PN

{ pracownik, instytut, wydział, temat, kwota }

{ pracownik, instytut, wydział }

{ pracownik, temat, kwota }

1PN

2PN

Istniej

ą

ce zale

ż

no

ś

ci funkcyjne:

pracownik

→

instytut

instytut

→

wydział

pracownik

→

wydział

AEiI

AEiI

AEiI

Inf

Inf

El

Grabski

Jaworek

Bukowy

wydział

instytut

pracownik

pracownik

instytut

wydział

Definicja zale

ż

no

ś

ci tranzytywnej

K

X

A

Tranzytywna zale

ż

no

ść

atrybutu A od klucza K poprzez X

Definicja 3PN

(oryginalna definicja Codd’a)

Schemat relacji (relacja) jest w 3 PN, je

ż

eli jest w 2 PN

i

ż

aden z atrybutów niekluczowych nie jest tranzytywnie

zale

ż

ny od klucza g

ł

ównego relacji.

Przykład dekompozycji do 3PN

{ pracownik, instytut, wydział }

{ pracownik, instytut}

{ instytut, wydział }

2PN

3PN

Projektowanie schematu bazy danych metod

ą

dekompozycji

Dane wej

ś

ciowe:

• Zbiór wszystkich atrybutów, traktowany jako

schemat jednej relacji

• Zbiór zale

ż

no

ś

ci mi

ę

dzy atrybutami

Cel:

Uzyskanie zbioru schematów relacji w trzeciej lub
czwartej postaci normalnej spełniaj

ą

cych warunek

odwracalno

ś

ci dekompozycji

Warunek odwracalno

ś

ci dekompozycji

Dekompozycja schematu R na zbiór schematów

{ R1, R2, R3, . . . , Rk } jest odwracalna,

je

ś

li dla ka

ż

dej relacji r(R) zachodzi:

π

R1

(r)



π

R2

(r)



…



π

Rk

(r) = r

Twierdzenie o dekompozycji odwracalnej

Dane: relacja r o schemacie R, tzn. r(R),

K - klucz relacji, X, Y - atrybuty tej relacji.

Je

ś

li w relacji r(R) istnieje tranzytywna zale

ż

no

ść

atrybutu Y od klucza K poprzez atrybut X,

to dekompozycja schematu R na dwa schematy

{XY, R-Y} jest dekompozycj

ą

odwracaln

ą

.

Przykład dekompozycji odwracalnej

{ pracownik, instytut, wydział }

{ pracownik, instytut}

{ instytut, wydział }

2PN

3PN

Przykład dekompozycji nieodwracalnej

{ pracownik, instytut, wydział }

{ pracownik, wydział }

{ instytut, wydział }

2PN

3PN

Inna definicja 3PN - wprowadzenie

Przedstawiona definicja 3PN mo

ż

e zosta

ć

uogólniona, tak aby uwzgl

ę

dniała istnienie innych

kluczy (kandyduj

ą

cych) relacji.

• Nadklucz (superklucz) relacji r(R): taki podzbiór S

atrybutów schematu relacji R (S

⊆

R),

ż

e dla ka

ż

dych

dwóch krotek

t

1

,

t

2

relacji r(R) zachodzi:

t

1

[S]

≠

t

2

[S].

• Atrybut podstawowy (atrybut kluczowy) relacji r(R):

ka

ż

dy taki atrybut relacji r(R), który jest składow

ą

pewnego klucza kandyduj

ą

cego relacji r(R).

Definicja 3PN

(ogólna)

Schemat relacji (relacja) jest w 3PN, je

ż

eli zawsze,

kiedy nietrywialna zale

ż

no

ść

funkcyjna X

→

A jest

spe

ł

niona w r(R), to albo (a) X jest nadkluczem w r(R),

albo (b) A jest atrybutem podstawowym w relacji r(R).

Przypadek naruszenia ogólnej definicji 3PN

Równocze

ś

nie nast

ę

puje:

• naruszenie (b), co oznacza,

ż

e A jest atrybutem

niepodstawowym (nie jest atrybutem kluczowym),

• oraz naruszenie (a), co oznacza,

ż

e X nie jest

nadzbiorem

ż

adnego klucza w r(R), to znaczy mo

ż

e

by

ć

zbiorem atrybutów niepodstawowych lub

podzbiorem wła

ś

ciwym klucza w relacji r(R).

X – zbiór atrybutów niepodstawowych

⇒

w relacji

r(R) wyst

ę

puje zale

ż

no

ść

tranzytywna,

X - podzbiór wła

ś

ciwy klucza

⇒

w relacji r(R)

wyst

ę

puje zale

ż

no

ść

cz

ęś

ciowa od klucza

Ogólna alternatywna definicja 3PN

Schemat relacji (relacja) jest w 3 PN, je

ż

eli ka

ż

dy

niepodstawowy (niekluczowy) atrybut relacji r(R)
spełnia oba poni

ż

sze warunki:

• jest zupełnie zale

ż

ny funkcyjnie od ka

ż

dego klucza w

relacji r(R),

• jest nietranzytywnie zale

ż

ny od ka

ż

dego klucza w

relacji r(R

Posta

ć

normalna Boyce’a - Codd’a (BCPN)

Schemat relacji (relacja) jest w postaci normalnej

Boyce’a - Codd’a (BCNF), je

ż

eli zawsze, kiedy

nietrywialna zale

ż

no

ść

funkcyjna X

→

A jest

spe

ł

niona w r(R), to X jest nadkluczem w r(R).

Ró

ż

nica mi

ę

dzy

3PN i BCPN

BCPN nie dopuszcza wyst

ę

powania zale

ż

no

ś

ci

funkcyjnej X

→

A, gdzie A jest atrybutem

podstawowym w relacji r(R).

Przykład

Rozwa

ż

my relacj

ę

:

r(student, przedmiot, wykładowca)

dla której s

ą

spełnione nast

ę

puj

ą

ce zale

ż

no

ś

ci:

student, przedmiot

→

wykładowca

wykładowca

→

przedmiot

Relacja

r(student, przedmiot, wykładowca)

jest w 3PN, ale nie jest w BCPN.

Mo

ż

emy wykona

ć

dekompozycj

ę

:

{wykładowca, przedmiot}, {wykładowca, student}

Teraz obie relacje s

ą

w BCPN, ale nie jest spełniona zale

ż

no

ść

student, przedmiot

→

wykładowca

Zale

ż

no

ść

wielowarto

ś

ciowa

(definicja uproszczona)

W relacji r(R) jest spełniona
wielowarto

ś

ciowa zale

ż

no

ść

X

→→

Y

je

ś

li z dan

ą

warto

ś

ci

ą

atrybutu X jest zwi

ą

zany

dobrze okre

ś

lony zbiór warto

ś

ci atrybutu Y

Przykład:

pracownik

→→

dziecko

student

→→

j

ę

zyk_obcy

Definicja 4PN

Schemat relacji r(R) jest w 4PN, je

ż

eli jest w 1PN i ka

ż

da

zale

ż

no

ść

wielowarto

ś

ciowa X

→→

Y, spełniona w r,

jest zale

ż

no

ś

ci

ą

trywialn

ą

, tzn. X

∪

Y = R,

lub X jest kluczem relacji r.

Twierdzenie

Je

ś

li w relacji r(R) istnieje wielowarto

ś

ciowa zale

ż

no

ść

X

→→

Y, to dekompozycja schematu R

na dwa schematy {XY, R-Y}

jest dekompozycj

ą

odwracaln

ą

.

Przykład

Rozwa

ż

my relacj

ę

o schemacie R = {pracownik, adres, dziecko}.

W relacji tej spełniona jest zale

ż

no

ść

wielowarto

ś

ciowa

pracownik

→→

dziecko

wobec czego dekompozycja schematu R na dwa schematy

{pracownik, dziecko} i {pracownik, adres}

jest dekompozycj

ą

odwracaln

ą

Inny przykład

R = {student, dyscyplina_sportowa, j

ę

zyk_obcy}

W relacji tej spełnione s

ą

zale

ż

no

ś

ci wielowarto

ś

ciowe:

student

→→

dyscyplina_sportowa

student

→→

j

ę

zyk_obcy

Wykorzystanie jednej z nich prowadzi do odwracalnej dekompozycji:

{student, dyscyplina_sportowa}

{student, j

ę

zyk_obcy}

Zale

ż

no

ść

wielowarto

ś

ciowa

(definicja

ś

cisła)

Niech R oznacza schemat relacji, natomiast X, Y s

ą

rozł

ą

cznymi

zbiorami atrybutów schematu R i Z = R – (XY)

• Relacja r(R) spełnia zale

ż

no

ść

wielowarto

ś

ciow

ą

X

→→

Y, je

ż

eli

dla dwóch dowolnych krotek t1 i t2 z r(R) takich,

ż

e t1[X] = t2[X],

zawsze istniej

ą

w r(R) krotki t3, t4 takie,

ż

e spełnione s

ą

nast

ę

puj

ą

ce

warunki:

t1 [X]= t2 [X] = t3 [X] = t4 [X]

t3 [Y] = t1 [Y] i t4 [Y] = t2 [Y]

t3 [R - X – Y] = t2 [R – X – Y]

t4 [R – X – Y] = t1 [R – X – Y]

• Z symetrii powy

ż

szej definicji wynika,

ż

e je

ż

eli w relacji r(R)

zachodzi X

→→

Y, to zachodzi równie

ż

: X

→→

[R – X – Y]

• Poniewa

ż

R – X – Y = Z, to powy

ż

szy fakt zapisujemy czasami

w postaci: X

→→

Y / Z