Relacyjny model danych
Wykład 2
S. Kozielski
Model danych
" struktury danych
" operacje na danych
" ograniczenia integralnościowe
Relacyjny model danych
" relacje
" operacje (operatory) algebry relacji
" więzy referencyjne + ograniczenia dziedzin relacji
Relacja (matematyka)
X, Y  zbiory,
Iloczyn kartezjański X �Y = {(x,y): x"X '" y"Y}
Dwuczłonowa relacja w X �Y = {(x,y): x"X '" y"Y '" x � y} �" X �Y
N  członowa relacja (relacja stopnia N):
podzbiór iloczynu kartezjańskiego X1 � X2 � X3 � ... � XN
Relacja  bazy danych
Atrybuty: A1, A2, A3, & np.: nazwisko, nrp, kwota, adres
Dziedziny atrybutów: DA1, DA2, DA3,... (inaczej domeny: dom(A1), dom(A2))
 zbiory dopuszczalnych wartości atrybutów (typy danych)
Schemat relacji: R = { A1, A2, ..., Ap}  podzbiór zbioru atrybutów
Relacja r o schemacie R: r(R) - podzbiór iloczynu kartezjańskiego dziedzin
atrybutów tworzących schemat DA1 � DA2 � ... � DAp
r(R) �" DA1 � DA2 � ... � DAp
Przykład:
R = {nrp, nrt, kwota}
Dnrp= {1, 2, 3}, Dnrt= {1, 2, 3}, Dkwota= {150, 200, 300}
Dnrp � Dnrt � Dkwota= {1, 1, 150
2, 1, 150
3, 1, 150
&
3, 3, 150
3, 3, 200
3, 3, 300}
Wypłaty
nrp nrt kwota
2 2 300
3 3 150
1 1 150
3 2 200
1 3 200
Wypłaty �" Dnrp � Dnrt � Dkwota
Relacja jako zbiór krotek
r(R) = {t1, t2, t3, & , tk}
Krotka t jest uporządkowaną listą wartości t = < v1,v2 & vp>
gdzie vi " DAi lub jest specjalną wartością pustą NULL
(A, B, C)
   
a1 b1 c1 - krotka t1
a2 b2 c2 - krotka t2
a3 b3 c3 - krotka t3
a4 b4 c4 - krotka t4
n-ty element krotki t oznaczany jest przez t[An] np. t4[B] = b4
Elementarne własności relacji
" Każdy atrybut relacji ma unikalną nazwę
" Porządek atrybutów w relacji nie jest istotny
" Porządek krotek w relacji nie jest istotny
" Relacja nie zawiera krotek powtarzających się
(wszystkie krotki są unikalne)
Unikalność krotek relacji a pojęcie klucza
" Każdy podzbiór S atrybutów schematu relacji R
(S ą" R), taki że dla każdych dwóch krotek ze zbioru
r(R) zachodzi ti [S] `" tj [S] jest nazywany
superkluczem (super key) relacji
" Superkluczem jest m.in. cały schemat relacji R
" Superklucz może posiadać nadmiarowe atrybuty
Pojęcie klucza relacji
" Kluczem K schematu relacji R nazywamy superklucz
schematu R o takiej własności, że usunięcie
dowolnego atrybutu A z K powoduje, że K = K - A nie
jest już superkluczem
" Klucz jest minimalnym superkluczem (zachowującym
własność unikalności krotek relacji)
" Schemat relacji może posiadać więcej niż jeden klucz
" Wyróżniony klucz: klucz główny (podstawowy)
" Pozostałe klucze: klucze kandydujące (wtórne)
Inna definicja klucza
" Kluczem jest minimalny zestaw atrybutów schematu
relacji, którego wartości jednoznacznie identyfikują
każdą krotkę relacji
Przykład
Pracownicy (nrp, imię, nazwisko, PESEL, NIP,
seria_i_nr_dowodu, data_urodzenia, imię_ojca,
imię_matki, adres, nazwisko_rodowe, tytuł, zawód,
nazwa_zakładu_pracy, adres_zp, staż)
Klucze kandydujące:
nrp
PESEL
NIP
seria_i_nr_dowodu
imię, nazwisko, imię_ojca
Różne formy opisu stosowane w modelu relacyjnym
Opis formalny Opis tablicowy Opis fizyczny
(fizycznych struktur d.)
relacja tablica (tabela) plik
krotka wiersz rekord
atrybut kolumna pole
schemat relacji nagłówek tablicy typ rekordu
Algebra relacji
Dane relacje: r(R), s(S)
Podstawowe operacje: selekcja, projekcja, złączenie,
iloczyn kartezjański, dzielenie, operacje na zbiorach
Selekcja
w  warunek selekcji (wyrażenie logiczne - predykat)
�w(r) = {t : t " r '" w(t) = True } = p(R)
Przykład selekcji
A B C
A B C
2
�C=2 2
1
�!
2
2
Projekcja
Niech X ą" R
ĄX(r) = { u : t " r '" u = t [X] } = q (X)
Przykład projekcji
A B C A C
ĄAC
�!
Złączenie (naturalne)
r s = { u : "t " r '" "w " s '"
t [R )" S] = w [R )" S] '" u[R] = t '" u[S] = w}
= z (R *" S)
Przykład złączenia naturalnego
r (A, B, C) s (C, D) z (A, B, C, D)
       =     
a1 b1 c1 c1 d1 a1 b1 c1 d1
a2 b2 c2 c5 d5 a4 b4 c1 d1
a3 b3 c3
a4 b4 c1
Ogólna postać złączenia (Ś - złączenie)
r w s = �w (r � s)
lub
r AŚB s = � AŚB (r � s) ,
gdzie A " R, B " S, dom(A) = dom(B)
Dzielenie
Niech będą dane relacje: r(XY), s(Y)
r � s = { u : "w " s "t " r t [Y] = w '" t [X] = u }
Przykład dzielenia
r (nrp, nrt) s (nrt) r � s = z (nrp)
         
1 1 1 1
1 2 2 3
1 3 3
2 2
2 3
3 1
3 2
3 3
Operatory mnogościowe
(operacje na zbiorach krotek)
Niech będą dane relacje: r(R), s(R)
Suma: r *" s
Różnica: r \ s
Iloczyn: r )" s
Powyższe operacje mogą być rozszerzone na
przypadek relacji r(R), s(S), w których R i S są
równoliczne, a odpowiadające sobie atrybuty
schematów R i S mają identyczne dziedziny
Pytanie Z1 jako wyrażenie algebry relacji
Z1 = Ąnazwa (�nazwisko =  Jaworek (Pracownicy Wypłaty Tematy))
Złączenie tabel
Wypłaty
Pracownicy
nrp nrt kwota
nrp nazwisko adres nrz
2 2 300
1 Lipowski Ruda 2
3 3 150
2 Grabski Zabrze 1
1 1 150
3 2 200
3 Jaworek Gliwice 1
1 3 200
Pracownicy Wypłaty
nrp nazwisko adres nrz nrt kwota
2 Grabski Zabrze 1 2 300
3 Jaworek Gliwice 1 3 150
1 Lipowski Ruda 2 1 150
3 Jaworek Gliwice 1 2 200
1 Lipowski Ruda 2 3 200
Pracownicy Wypłaty Tematy
nrp nazwisko adres nrz nrt kwota nazwa kier.
2 Grabski Zabrze 1 2 300 Pr. przetwor. 1
3 Jaworek Gliwice 1 3 150 Pr. reaktora 2
1 Lipowski Ruda 2 1 150 Pr. zasilacza 2
3 Jaworek Gliwice 1 2 200 Pr. przetwor. 1
1 Lipowski Ruda 2 3 200 Pr. reaktora 2
�nazwisko =  Jaworek (Pracownicy Wypłaty Tematy)
nrp nazwisko adres nrz nrt kwota nazwa kier.
3 Jaworek Gliwice 1 3 150 Pr. reaktora 2
3 Jaworek Gliwice 1 2 200 Pr. przetwor. 1
Ąnazwa (�nazwisko =  Jaworek (Pracownicy Wypłaty Tematy))
nazwa
Pr. reaktora
Pr. przetwor.
Własności operatorów algebry relacji
r(R), s(S), z(Z)  dane relacje
1) Przemienność złączeń: r s = s r
2) A
ączność złączeń: (r s) z = r (s z)
3) Przemienność selekcji i złączeń dla wyrażenia
�w(r s)
Niech atr(w)  zbiór atrybutów występujących w w
Jeśli atr(w) ą" R, to �w(r s) = (�w(r )) s
Jeśli atr(w) ą" S, to �w(r s) = r (�w(s ))
Jeśli w= w1 '" w2 oraz atr(w1) ą" R i atr(w2) ą" S,
to �w(r s) = (�w1(r )) (�w2(s))
Przykłady równoważnej postaci wyrażeń
P1=Ąnazwisko (�nrz=3'"kwota>2000 (Pracownicy Wypłaty))
P1= Ąnazwisko ((�nrz=3 (Pracownicy)) (�kwota>2000 (Wypłaty)))
P2= Ąnazwisko (�nazwa =  Pr.gen. (Pracownicy Wypłaty Tematy))
P2= Ąnazwisko (Pracownicy Wypłaty (�nazwa =  Pr.gen. (Tematy)))
Drzewo rozbioru wyrażenia algebry relacji  plan realizacji zapytania
Pracownicy(20) Wypłaty(50)

+
�nrz = 3 '" kwota>2000
+
Ąnazwisko
P1
Optymalizacja wyrażeń algebry relacji
(wykorzystanie przemienności selekcji i złączeń)
Pracownicy(20) Wypłaty(50)
�nrz = 3 � kwota>2000

+
Ąnazwisko
P1
P2= Ąnazwisko (�nazwa =  Pr.gen. (Pracownicy Wypłaty Tematy))
P2= Ąnazwisko (Pracownicy Wypłaty (�nazwa =  Pr.gen. (Tematy)))
Optymalizacja wyrażeń algebry relacji
(dobór kolejności złączeń - 1)
Pracownicy(20) Wypłaty(50) Tematy(10)
� nazwa = Pr. gen.


+
Ąnazwisko
P2
Optymalizacja wyrażeń algebry relacji
(dobór kolejności złączeń - 2)
Pracownicy(20) Wypłaty(50) Tematy(10)
� nazwa = Pr. gen.


+
Ąnazwisko
P2
Proste reguły optymalizacji wyrażeń algebry relacji
" Przenieść selekcje (i projekcje) jak najwyżej w drzewie rozbioru
wyrażenia
" Wykonać projekcje razem ze złączeniami lub selekcjami
" Dobrać kolejność złączeń według selekcji najsilniej
redukujących