Projektowanie struktury logicznej (schematu)
relacyjnych baz danych
Wykład
S. Kozielski
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