Projektowanie struktury logicznej (schematu)
relacyjnych baz danych
Wykład
S. Kozielski
Projektowanie struktury (logicznej) baz danych
Modelowanie związków encji  elementy diagramów
niezależny byt, reprezentuje zbiór
encja
jednoznacznie obiektów opisanych tymi
identyfikowalny samymi cechami
(własnościami,
atrybutami)
związek
łączy encje
opisuje encje
atrybut
i związki
Przykłady diagramów związków encji (1)
student przedmiot
N M
N
studiuje
zalicza
1
kierunek
Przykłady diagramów związków encji (2)
pracownik temat
N M
N
należy
wykonuje
1
zespół
Przykłady diagramów związków encji (3)
chory lekarstwo
N M
N
leży
zażywa
1
oddział
typ - student
encja
wystąpienie - Grabski
typ - studiuje
związek
wystąpienie  Grabski studiuje informatykę
typ encji zbiór wartości
atrybut-odwzorowanie
typ związku zbiór wartości
integer char(20) char(50)
nazwisko
album
album nazwisko adres
adres
student
student
nazwa prowadzący
album nazwisko adres id_p
jęz_ob
student przedmiot
N M N
studiuje zalicza
sem
1
id_k
kierunek
ocena
N
nazwa
podlega
dziekan
1
id_w
wydział
nazwa
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ędz
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)
student
album
nazwisko
adres
studiuje
kierunek
id_k
nazwa
Problem atrybutów wielowartościowych
album nazwisko adres nazwa
M N
student język_obcy
zna
stopień
student (album, nazwisko, adres)
język_obcy (nazwa)
zna (album, nazwa, stopień)
Relacja (tablica) język_obcy  pełni rolę słownika
Problem związków 1 : 1
nr_karty
album nazwisko adres staż
1 1
student czytelnik
jest
student (album, nazwisko, adres)
czytelnik (nr_karty, staż)
jest (album, nr_karty) - problem wyboru klucza
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
nazwisko imię
adres
encja właścicielska
nrp
Pracownik
1
ID
należy
ma
encja słaba
N
Zespół
Dziecko
kierownik
nrz
imię
nazwa data_ur
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
album
1 N
nrp
prowadzi
pracownik dyplomant
adres
1 N
nazwisko
nazwisko recenzuje
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)
Powiązanie encji samej z sobą
zwierzchnik
nrp
1
kieruje-
pracownik
podlega
N
nazwisko
podwładny
pracownik (nrp, nazwisko)
kieruje_podlega (nrp, nrp)
ę! ę!
zwierzchnik podwładny
po modyfikacji nazw i scaleniu:
pracownicy (nrp, nazwisko, nrp_zwierzchnika)
Projektowanie struktury b. d. poprzez normalizację
schematu bazy danych
Punkt wyjścia: zbiór atrybutów A1, A2, A3, . . . , An ,
których wartości chcemy przechowywać w bazie.
Początkowy cała b.d. jest widziana jako jedna relacja
o schemacie R = {A1, A2, A3, . . . , An }.
Następnie schemat R dzielony jest na zbiór schematów
relacji w procesie normalizacji.
R �! { R1, R2, R3, . . . , Rk }
Schematy tworzone w procesie normalizacji powinny
spełniać warunki kolejnych postaci normalnych.
nrp nazwisko adres dziecko
2 Grabski Zabrze, ul. Wolności 123 Adam
5 Jaworek Gliwice, ul. Zwycięstwa 33 Kasia, Ania, Krzyś
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
nrp nazwisko adres dziecko
2 Grabski Zabrze, ul. Wolności 123 Adam
5 Jaworek Gliwice, ul. Zwycięstwa 33 Kasia
5 Jaworek Gliwice, ul. Zwycięstwa 33 Ania
5 Jaworek Gliwice, ul. Zwycięstwa 33 Krzyś
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
nrp nazwisko adres dziecko
2 Grabski Zabrze, ul. Wolności 123 Adam
5 Jaworek Gliwice, ul. Zwycięstwa 33 Kasia
5 Jaworek Gliwice, ul. Zwycięstwa 33 Ania
5 Jaworek Gliwice, ul. Zwycięstwa 33 Krzyś
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
1PN
{nrp, nazwisko, adres, dziecko}
2PN
{nrp, nazwisko, adres} {nrp, dziecko}
Przykład innej relacji
pracownik instytut wydział temat kwota
Grabski Inf AEiI BK 303 150
Jaworek Inf AEiI BK 303 200
Jaworek Inf AEiI BW 202 150
Bukowy El AEiI BW 202 200
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
1PN
{ pracownik, instytut, wydział, temat, kwota }
{ pracownik, instytut, wydział } { pracownik, temat, kwota }
2PN
pracownik instytut wydział
Grabski Inf AEiI
Jaworek Inf AEiI
Bukowy El AEiI
Istniejące zależności funkcyjne:
pracownik instytut
instytut wydział
pracownik wydział
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
2PN
{ pracownik, instytut, wydział }
{ pracownik, instytut} { instytut, wydział } 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
2PN
{ pracownik, instytut, wydział }
{ pracownik, instytut} { instytut, wydział } 3PN
Przykład dekompozycji nieodwracalnej
2PN
{ pracownik, instytut, wydział }
{ pracownik, wydział } { instytut, wydział } 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 t1, t2 relacji r(R) zachodzi: t1 [S] `" t2 [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