3.10.2012
Relacijske baze podataka
Mr.sc. Emir Mešković
Tuzla, 26.09.2012. god.
Uvod
• Zasnovane na relacijskoj algebri
• Baza podataka sastoji se od relacija –
dvodimenzionalne tabele
• Eksplicitne veze među relacijama NE POSTOJE –
uspostavljaju se prema potrebi
• Nad relacijama se provode operacije relacijske
algebre
• Rezultati operacija su relacije
1
3.10.2012
Početak razvoja
• Teoretski zasnovan krajem 60-tih godina u radovima
Edgara F. Codd-a
– "A Relational Model of Data for Large Shared Data Banks“
- Comm. ACM 13, No. 6, June 1970
• Dugo se pojavljivao samo u akademskim raspravama
i knjigama
• Prve realizacije na računaru su bile suviše spore i
neefikasne
• Sredinom 80-tih godina 20. stoljeća relacijski model
je postao prevladavajući
• Danas se ogromna većina DBMS-ova koristi baš tim
modelom
Definicija relacije
Skup entiteta:
Atributi:
Domena:
Dekartov proizvod
OSOBA
IME
PREZIME
Damir
Maja
Dino
Ema
Pirić
Đurić
Pejić
Damir Pirić
Damir Đurić
Damir Pejić
Maja Pirić
Maja Đurić
Maja Pejić
Dino Pirić
Dino Đurić
Dino Pejić
Ema Pirić
Ema Đurić
Ema Pejić
Relacija
Damir Pirić
Maja Đurić
Dino Pejić
Ema Pirić
2
3.10.2012
Definicija relacije
• Neka postoji skup atributa A1, ..., An sa
pripadajućim domenama D1, ..., Dn
• Relacija r(A1, ..., An) je podskup dekartovog
proizvoda domena D1  ...  Dn
r(A1, ..., An)  D1  ...  Dn
Definicija relacije
• Skup entiteta: Osoba
• Atributi: Ime, BojaKose, BrojCipele
• Domene: { Deni, Lejla, Goran }, { Crna, Smeđa, Plava }, { 37, 38, 39,
40, 41, 42, 43 }
Relacija:
R=(
r(R)
< Deni, Smeđa, 41 >
< Lejla, Plava, 38 >
< Goran, Smeđa, 43 >
Ime,
Deni
Lejla
Goran
BojaKose, BrojCipele)
Smeđa
41
Plava
38
Smeđa
43
3
3.10.2012
Relacija i relacijska shema
• Relacijska shema R (intenzija) je imenovani skup
atributa: R = { A1, A2, ..., An } ili R = A1, A2, ..., An
• Relacija r (ekstenzija) definisana nad relacijskom
shemom R je konačan skup n-torki, označava se s r(R)
ili r(A1, A2, ..., An) i predstavlja trenutnu vrijednost
Primjer:
STUDENT = mbrStudent, prezimeStudent, imeStudent, prosjecnaOcjena
student(STUDENT) = { < 123456, Žunić, Senad, 9.65 >,
< 234567, Zorić, Slađana, 9.77 >,
< 345678, Ivanović, Valentina, 9.56 > }
student(mbrStudent,
123456
234567
345678
prezimeStudent,
imeStudent,
Žunić
Senad
Zorić
Slađana
Ivanović
Valentina
prosjecnaOcjena)
9.65
9.77
9.56
Vrijednost n-torke
• Oznaka t(A) predstavlja vrijednost koju atribut A poprima
u n-torki t. t(A) se naziva A-vrijednost n-torke t
Primjer:
t = < 123456, Žunić, Senad, 9.65 >
t(prezimeStudent) = Žunić
• Neka je X  R. N-torka t reducirana na skup atributa X se
naziva X-vrijednost n-torke t i označava s t(X)
Primjer:
t = < 234567, Zorić, Slađana, 9.77 >
prezimeStudent, imeStudent  STUDENT
t(prezimeStudent, imeStudent) = < Zorić, Slađana >
4
3.10.2012
Karakteristike i operacije
• Karakteristike relacije
– Stepen – broj kolona (atributa)
– Kardinalnost – broj n-torki (zapisa)
• Operacije s relacijama
– Relacijska algebra
• Vrednovanje algebarskih izraza građenih od relacija i
unarnih, odnosno binarnih, operatora
– Predikatni račun (prekidačka algebra)
• Ispitivanje istinitosti složenih sudova izrađenih pomoću
logičkih operatora i zagrada
Relacijska algebra
•
•
•
•
•
•
•
•
•
•
Unija

Presjek

Razlika
\
Dekartov proizvod *
Dijeljenje
/
Projekcija

Selekcija

Spajanje

Primjer: a = X=x & Y=y(d  (b  c))
Proceduralnost – navođenje redoslijeda operacija
5
3.10.2012
Predikatni račun
• r = { t | f(t) }
• t je varijabla koja predstavlja:
– n-torke – n-torski račun
– Domene – domenski račun
• Primjer:
– a = { t | (d(t)  (b(t)  c(t)))  t(X)=x  t(Y)=y }
• Neproceduralnost – navođenje predikata koje ntorke moraju zadovoljiti
Operacije relacijske algebre
• Osnovne operacije
– Presjek, unija i razlika
– Primjenjuju se nad relacijama koje su unijski kompatibilne
• Relacije istog stepena
• Korespodentni atributi definisani nad istim domenama
• Primjer relacija:
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
Stepen:
Kardinalnost:
R2=(prezime, ime,
Žunić
Senad
r2
Pirić
Damir
d1 = 3
m1 = 3
postBr)
72000
75000
d2 = 3
m2 = 2
Relacije su unijski kompatibilne
6
3.10.2012
Preimenovanje atributa
• Neka su A i B atributi i nekaje r relacija definisana na
shemi R, A  R, B  R \ A
• Neka je DOM(A) = DOM(B). Neka je R’ = (R \ A) B.
• Operacija preimenovanja atributa A u B u relaciji r(R)
označava se s AB(r), a definiše pomoću izraza:
– AB(r) = r’(R’) = { t’ | t  r, t’(R \ A) = t(R \ A)  t’(B) = t(A) }
• Neka su A1, A2, ..., Ak različiti atributi u R i neka su B1,
B2, ..., Bk različiti atributi koji nisu članovi skupa R \(A1,
A2, ..., Ak)
• Neka je DOM(Ai) = DOM(Bi), za 1  i  k
• Simultano preimenovanje atributa A1, A2, ..., Ak u
atribute B1, B2, ..., Bk u relaciji r označava se s A1, A2, ...,
AkB1, B2, ..., Bk(r)
Unijska kompatibilnost relacija
• Dvije relacije r i s definisane na shemama R i S,
odnosno njihove sheme R i S, su unijski
kompatibilne ukoliko postoji 1:1 preslikavanje
• f: R  S, f(Ai) = Bj, f-1(Bj) = Ai
• Pri čemu je Ai  R, Bj  S, DOM(Ai) = DOM(Bj)
7
3.10.2012
Unija relacija
r3 = r1  r2
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R3=(
r3(R3)
R2=(prezime, ime,
Žunić
Senad
r2
Pirić
Damir
prezime,
ime,
Pirić
Damir
Đurić
Maja
Pirić
Ema
Žunić
Senad
postBr)
72000
75000
postBr)
75000
71000
75000
72000
Unija relacija
• Neka su r i s unijski kompatibilne relacije definisane
na shemama R i S.
• Operacija unije relacija r i s označava se s r  s, a
definiše izrazom
• r  s = q(R) = { t | t  r  t  s } ako je R = S
• r  s = q(R) = { t | t  r  t  XYs(S) } ako je R  S
• gdje je:
–
–
–
–
–
XR\S
YS\R
X = f(Y)
Y = f-1(X)
i f: Y  X je restrikcija od f: R  S i f-1: R  S
8
3.10.2012
Presjek relacija
r4 = r1  r2
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R4=(
r4(R4)
R2=(prezime, ime,
Žunić
Senad
r2
Pirić
Damir
postBr)
72000
75000
prezime,
ime,
postBr)
Pirić
Damir 75000
Presjek relacija
• Neka su r i s unijski kompatibilne relacije definisane
na shemama R i S.
• Operacija presjeka relacija r i s označava se s r  s, a
definiše izrazom
• r  s = q(R) = { t | t  r  t  s } ako je R = S
• r  s = q(R) = { t | t  r  t  XYs(S) } ako je R  S
• gdje je:
–
–
–
–
–
XR\S
YS\R
X = f(Y)
Y = f-1(X)
i f: Y  X je restrikcija od f: R  S i f-1: R  S
9
3.10.2012
Razlika relacija
r5 = r 1 \ r2
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R5=(
r5(R5)
R2=(prezime, ime,
Žunić
Senad
r2
Pirić
Damir
prezime, ime,
Đurić
Maja
Pirić
Ema
postBr)
72000
75000
postBr)
71000
75000
Razlika relacija
• Neka su r i s unijski kompatibilne relacije definisane
na shemama R i S.
• Operacija razlike relacija r i s označava se s r \ s, a
definiše izrazom
• r \ s = q(R) = { t | t  r  t  s } ako je R = S
• r \ s = q(R) = { t | t  r  t  XYs(S) } ako je R  S
• gdje je:
–
–
–
–
–
XR\S
YS\R
X = f(Y)
Y = f-1(X)
i f: Y  X je restrikcija od f: R  S i f-1: R  S
10
3.10.2012
Dekartov proizvod relacija
r7 = r1 * r6
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R7=(
r7(R7)
prezime, ime,
Pirić
Damir
Pirić
Damir
Đurić
Maja
Đurić
Maja
Pirić
Ema
Pirić
Ema
R6=( pbr,
72000
r6 75000
postBr, pbr,
75000 72000
75000 75000
71000 72000
71000 75000
75000 72000
75000 75000
nazivGrad)
Zenica
Tuzla
nazivGrad)
Zenica
Tuzla
Zenica
Tuzla
Zenica
Tuzla
Dekartov proizvod relacija
• Spajanje n-torki
– Neka su a = (a1, a2, ..., ak) i b = (b1, b2, ..., bm) n-torke.
Operacija spajanja n-torki označava se s a ^ b, a
definiše pomoću izraza a ^ b = (a1, a2, ..., ak, b1, b2, ...,
bm).
• Neka su r i s relacije. Operacija Dekartov proizvod
relacija r i s označava se r  s, a definiše izrazom
• r  s = { (tr ^ ts) | tr  r  ts  s }
11
3.10.2012
Dijeljenje relacija
r18 = r11 / r12
R11=(A B)
a1 b 1
a1 b 2
a1 b 3
r11 a2 b1
a2 b 2
a3 b 1
a4 b 4
r19 = r11 / r13
R12=(B)
r12 b1
R13=(B)
b1
r13 b2
b3
R18=(A)
a1
r18 a2
a3
R19=(A)
r19 a1
• Neka je R relacija stepena n, a S relacija stepena m, i neka se svi
atributi od S pojavljuju i u R.
• Rezultat dijeljenja R sa S, oznakom R / S, je skup svih (n-m)-torki
<x> takvih da se n-torke <x,y> pojavljuju u R za sve m-torke <y> u S
Specifične operacije
• Unarne
– projekcija - izdvajanje kolona (atributa)
– selekcija - izdvajanje redova (n-torki)
• Binarne - spajanje
– prirodno spajanje
– spajanje uz uslov
12
3.10.2012
Projekcija relacije
r8 = prezime, ime(r1)
r9 = postBr(r1)
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R8=(
r8(R8)
prezime,
ime)
Pirić
Damir
Đurić
Maja
Pirić
Ema
R9 =
r8(R8)
(postBr)
75000
71000
Projekcija relacije
•
•
•
•
s = A1, ..., Ak(r)
Relacijska shema od s: S = { A1, ..., Ak }
Stepen: ds = k
Kardinalnost: card(s)  card(r)
– Obavlja se eliminacija duplikata
• Neka je r relacija definisana na shemi R i neka je X
skup atributa, X  R
• Operacija projekcije relacije r(R) na skup atributa
X se označava s X(r), a definiše izrazom:
• X(r) = q(X) = { t(X) | t  r }
13
3.10.2012
Operacija selekcije
• s = F(r)
• F – formula selekcije koja sadrži
– Operande – imena atributa iz r, konstante
– Operatore
• aritmetički operatori poređenja (<, =, >, , , )
• logički operatori (, , )
• s je skup n-torki iz r koje zadovoljavaju F – s
r
• Relacijska shema od s: S = R
Operacija selekcije
r10 = postBr=75000(r1)
r11 = postBr=75000  ime=“Damir”(r1)
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R10=(
r10(R10)
prezime, ime, postBr)
Pirić
Damir 75000
Pirić
Ema 75000
R11=(
r11(R11)
prezime,
ime, postBr)
Pirić
Damir 75000
14
3.10.2012
Formula
• Neka je r relacija definisana na shemi R i neka su A i B atributi iz
R.
• Neka je  relacijski operator iz skupa {=, , >, , <, }
• Neka je c konstanta iz skupa DOM(A)
• Formula F je definisana rekurzivnim izrazom:
– A  B, A  c, c  A su formule. Ove formule se nazivaju jednostavnim
formulama (atomi)
– Ako su G i H formule, tada su GH, GH, G i H također formule
– Ništa drugo nije formula
• Neka je R = A1, A2, ..., Ak i neka je r relacija definisana na shemi R
• Formula F je primjenjiva na r ako su:
– Konstante koje se pojavljuju u F iz skupa DOM(A1)  DOM(A2)  ... 
DOM(Ak) i
– ako su atributi koji se pojavljuju u F iz skupa R
Selekcija relacije
• Neka je r relacija definisana na shemi R i neka
je F formula primjenjiva na r.
• Operacija selekcije nad relacijom r uz uslov
selekcije F se označava s F(r), a definiše
izrazom:
• F(r) = q(R) = { t | t  r  t zadovoljava F }
15
3.10.2012
Spajanje (pridruživanje) relacija
• Prirodno spajanje (Natural Join)
• Spajanje uz uslov (Theta Join)
• Spajanje sa izjednačavanjem (Equi Join)
– Poseban slučaj spajanja uz uslov
Prirodno spajanje relacija
• Obavlja se na osnovu jednakih vrijednosti
istoimenih atributa
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R61=(postBr,
72000
r61 75000
nazivGrad)
Zenica
Tuzla
r12 = r1  r61
R12=(
prezime, ime,
Pirić
Damir
r12(R12) Pirić
Ema
postBr,
75000
75000
nazivGrad)
Tuzla
Tuzla
16
3.10.2012
Prirodno spajanje relacija
• Prirodno spajanje relacija bez istoimenih atributa
r13 = r1  r6
R1=(prezime, ime, postBr)
Pirić
Damir 75000
r1 Đurić
Maja 71000
Pirić
Ema 75000
R13=(
prezime, ime,
Pirić
Damir
Pirić
Damir
r13(R13) Đurić
Maja
Đurić
Maja
Pirić
Ema
Pirić
Ema
R6=( pbr,
72000
r6 75000
postBr, pbr,
75000 72000
75000 75000
71000
7100075000
75000 72000
75000 75000
nazivGrad)
Zenica
Tuzla
nazivGrad)
Zenica
Tuzla
72000 Zenica
Tuzla
Zenica
Tuzla
• … je jednako Dekartovom proizvodu
Spajanje uz uslov -  spajanje
• s = r1 
r2

•  - uslov na osnovu kojeg se obavlja spajanje:
– Operandi – imena atributa iz r1 i r2, konstante
– Operatori
• aritmetički operatori poređenja (<, =, >, , , )
• logički operatori (, , )
17
3.10.2012
Spajanje uz uslov -  spajanje
LINIJA=(let,
udaljenost)
CA-825
7200
A-224
3300
CA-878
4700
CA-224
2000
AVION=(tip,
B747
DC9
B727
dolet)
6000
3000
4500
mogućnost= linija  avion
udaljenost ≤ dolet
MOGUĆNOST=(let,
udaljenost,
tip, dolet)
A-224
3300
B747
A-224
3300
B727
CA-878
4700
B747
CA-224
2000 B747
6000
CA-224
2000 DC9
3000
CA-224
2000 B727
4500
6000
4500
6000
Spajanje uz uslov -  spajanje
Neka je  relacijski operator iz skupa {<, =, >, , , }
Neka su r i s relacije definisane na shemama R i S
Neka su A i B atributi, A  R i B  S
Operacija  spajanja relacija r i s na osnovi formule
A  B označava se sa r 
s, a definisana je izrazom:

• r 
s = { (tr ^ ts) | tr  r  ts  s  tr(A)  ts(B)}

• Umjesto jednostavne formule A  B kao formula
spajanja može se koristiti složena formula dobivena
konjunkcijom jednostavnih formula oblika Ai  Bj, pri
čemu je Ai  R i Bj  S
•
•
•
•
18
3.10.2012
Spajanje sa izjednačavanjem
• Spajanje relacija sa izjednačavanjem je poseban
oblik theta spajanja u kojem se kao  operator
koristi isključivo operator jednakosti
• Neka su r i s relacije definisane na shemama R i S
• Operacija prirodnog spajanja relacija r i s
označava se s r  s, a definiše izrazom
• r  s = q(R  S) = {t | tr  r  ts  s, t(R)=tr 
t(S)=ts}
1. zadatak
• Zadana je relacija:
popis(osoba,
O1
O2
O3
grad
G1
G1
G2
p1 = osoba, grad(popis)
p1(osoba,
O1
O2
O3
grad)
G1
G1
G2
telefon)
T1
T2
T3
p2 = osoba, telefon(popis)
p2(osoba,
O1
O2
O3
telefon)
T1
T2
T3
p3 = p1  p2
p3 (osoba,
O1
O2
O3
grad telefon)
G1
T1
G1
T2
G2
T3
19
3.10.2012
2. zadatak
• Zadana je relacija:
popis1(osoba,
O1
O2
O3
O1
grad
G1
G1
G2
G2
telefon)
T1
T2
T3
T4
p11 = osoba, grad(popis1) p12 = osoba, telefon(popis1) p13 = p11  p12
p11(osoba,
O1
O2
O3
O1
grad)
G1
G1
G2
G2
p12(osoba,
O1
O2
O3
O1
p13 <> popis
telefon)
T1
T2
T3
T4
p13 (osoba,
O1
O1
O2
O3
O1
O1
grad telefon)
G1
T1
G1
T4
G1
T2
G2
T3
G2
T1
G2
T4
20
Download

null