OPERATORI RELATIONALI

OPERATORI RELATIONALI

Operatiile definite in capitolul precedent nu opereaza asupra relatiilor, ele opereaza asupra tuplurilor. In acest capitol vom introduce operatori care opereaza asupra relatiilor in intregime. Rezultatul unui operator este o alta relatie (propietatea de inchidere). Aceasta propietate este foarte importanta, deorece outputul oricarui operator este un obiect de acelasi tip ca la intrare. Cu alte cuvinte operatorii relationali ne permit sa scriem expresii "nested", adica expresii in care operanzii sunt reprezentati de alte expresii si asa mai departe pana cand in final operanzii sunt nume de relatii. Vom arata ca operatiile obisnuite din teoria multimilor se aplica si la relatii si apoi vom defini trei operatori relationali speciali: selectia, proiectia si unirea etc.

3.1. Operatii booleene

Doua relatii care au aceeasi schema, pot fi considerate ca multimi de date ale aceluiasi univers, descris de multimea tuturor tuplurilor posibile ale schemei ce-l caracterizeaza. Daca r si s sunt doua relatii de schema R, atunci r s, r s, r-s sunt relatii de schema R.

Multimea r s este relatia q(R) a tuturor tuplurilor care apartin lui r sau lui s.

Multimea r s este relatia q(R) a tuturor tuplurilor care apartin in acelasi timp si lui r si lui s.

Relatia r-s este relatia q(R) formata din tuplurile care apartin lui r si nu apartin lui s. Se observa ca intersectia mai poate fi scrisa si astfel: r s=r-(r-s).

Fie dom(R) multimea tuturor tuplurilor posibile in raport cu atributele schemei si domeniile lor. Complementara relatiei r(R) se poate defini prin diferenta: =dom(R) -r .

Totusi, daca un atribut A din R are un domeniu infinit, atunci dom(R) este infinit si nu va fi relatie in sensul definitiei introduse. Versiunea modificata a complementarei, numita activa, este intotdeauna relatie.

Fie r(A1,A₂,,A_n) o relatie si D_i=dom(A_i), 1≤i≤n se numeste domeniu activ al atributului A_i in raport cu r este multimea:

adom(A_i,r)=

Fie multimea tuturor tuplurilor in raport cu atributele din R si multimea domeniilor activein raport cu r, notata cu adom(R). Complementara activa a relatiei r, notata cu =adom(R,r) - r care este intotdeauna o relatie.

Exemplul 3.1. Fie schema R=(ABC) si relatiile r si s de schema R.

r( A B C ) s( A B C )

a₁ b₁ c₁ a₁ b₂ c₁

a₁ b₂ c₁ a₂ b₁ c₂

a₂ b₁ c₂ a₂ b₂ c₂

atunci operatiile r s, r s, r-s sunt:

r s( A B C ) r s( A B C ) r-s( A B C )

a1 b₂ c₁ a₁ b₁ c₁ a1 b₁ c₁

a₂ b₁ c₂ a₁ b₂ c₁

a₂ b₁ c₂

a₂ b₂ c₂

Fie dom(A)= dom(B)= dom(C)=pentru care se da dom(R), adom(R), =dom(R)r si = adom(R)-r.

dom(R) ( A B C ) (A B C ) adom(R) ( A B C ) (R)( A B C )

a₁ b₁ c₁ a₁ b₁ c₂ a₁ b₁ c₁ a₁ b₁ c₂

a₁ b₁ c₂ a₁ b₂ c₂ a₁ b₁ c₂ a₁ b₂ c₂

a₁ b₂ c₁ a₁ b₃ c₁ a₁ b₂ c₁ a₂ b₁ c₁

a₁ b₂ c₂ a₁ b₃ c₂ a₁ b₂ c₂ a₂ b₂ c₁

a₁ b₃ c₁ a₂ b₁ c₁ a₂ b₁ c₂ a₂ b₂ c₂

a₁ b₃ c₂ a₂ b₂ c₁ a₂ b₂ c₁

a₂ b₁ c₁ a₂ b₂ c₂ a₂ b₂ c₂

a₂ b₁ c₂ a₂ b₃ c₁

a₂ b₂ c₁ a₂ b₃ c₂

a₂ b₂ c₂

a₂ b₃ c₁

a₂ b₃ c₂

Multimea relatiilor care au aceeasi schema este inchisa fata de reuniune, intersectie, complementara activa si diferenta simetrica, totusi aceste operatii nu pastreaza cheia.

3.2. Operatorul de selectie

Selectia este un operator unar de relatie. Operatorul de selectie aplicat unei relatii r produce o relatie s de aceiasi schema care contine tuplurile din relatia r ce verifica conditia data ca argument.

Definitia 3.1. Fie relatia r de schema R, un atribut AIR si un element aIdom(A). Operatorul de selectie face sa corespunda relatiei r(R) relatia s_A=a(r) formata din tuplurile lui r care au valoarea atributului A egala cu a.

Considerand tuplurile ca transformari, operatorul de selectie se poate defini astfel:

s_A=a(r)=.

Exemplul 3.2 Fie relatia orar, data in tabelul 2:

orar ( NR PD PA OD OA )

70 Bucuresti Cluj 16 18

75 Cluj Bucuresti 7 9

80 Bucuresti Craiova 16 17

85 Craiova Bucuresti 7 8

95 Bucuresti Timisoara 18 20

Dam rezultatul aplicarii operatorului s_{punct_decolare=Bucuresti}(orar).

orar ( NR PD PA OD OA )

70 Bucuresti Cluj 16 18

80 Bucuresti Craiova 16 17

95 Bucuresti Timisoara 18 20

3.3. Operatorul de proiectie

Operatorul de proiectie este de asemenea un operator unar de relatii. Proiectia este un operator specific relatilor care ne permite sa suprimam atribute dintr-o relatie data. El face sa corespunda unei relatii de grad n o alta relatie de grad mai mic p<n. Deci ne permite sa trecem de la un spatiu cu n dimensiuni la un spatiu cu mai putine dimensiuni.

Daca operatorul de selectie permite alegerea unei multimi de tupluri (linii) dintr-o relatie, operatorul de proiectie permite alegerea unei submultimi de atribute (coloane).

Definitia 3.2. Fie relatia r de schema R si X R o submultime de atribute din R. Relatia q(X) obtinuta din r prin inlaturarea coloanelor R-X si a tuplurilor (liniilor) care se repeta se numeste proiectia relatiei r in raport cu X. Daca consideram tuplurile ca transformari, atunci:

p_x(r)=

Fie relatia r(R) si X₁ X₂ X₃ X_k R, atunci:

p _X1 (p_X2 p_X3 p_Xk(r))= p_X (r)

Proiectia comuta cu selectia cand atributul sau atributele pentru selectie se afla printre atributele multimii X dupa care se face proiectia. Daca A X, X R si r este o relatie de schema R, atunci:

p_X s_A=a(r))= p_X

s_A=a p_X(r))

Observatie: Afirmatia nu este adevarata daca A nu se afla in X.

3.4. Operatorul de unire(JOIN)

Unirea a doua relatii este cel mai important operator din algeba relationala si cel mai dificil de realizat de sistemele de gestiune care il implementeaza. Unirea poate fi conceputa intuitiv ca o completare a produsului cartezian cu o conditie care ne permite sa comparam anumite atribute. Operatorul de unire a doua relatii produce o a treia relatie care contine toate concatenarile de tupluri din cele doua relatii initiale care satisfac o conditie specificata.

Conditia trebuie sa permita desigur alipirea celor doua relatii si deci sa fie de forma ;

Atribut1 operator atribut2 ,

unde atributul1 apartine relatiei1 si atributul2 apartine relatiei2. Dupa natura operatorului pot fi impartite in echi-uniri si inechi-uniri.

Vom ilustra acesta printr-un exemplu: presupunem ca avem o baza de date despre liniile aeriene, care este ipotetic formata din doua liste:

- lista de tipuri de avioane care pot fi folosite la fiecare linie;

- lista de tipuri de avioane pe care fiecare pilot are drept de conducere.

Fie relatiile: utilizare(CURSA, TIP_AVION) si drept_conducere(PILOT, TIP_AVION).

utilizare( CURSA, TIP AVION ) drept-conducere( PILOT, TIP_AVION )

80 BAC111 TICA BAC111

85 IAR500 TICA ROMBAC

88 ROMBAC ION IAR500

90 IAR100 RADU IAR500

Relatia Optiune(CURSA, TIP_AVION, PILOT).

Optiune( CURSA TIP AVION PILOT )

80 BAC111 Tica

85 IAR500 Ion

ROMBAC Tica

90 IAR100 Radu

Calculul proiectiei p _{CURSA, PILOT}(Optiune):

p _{CURSA, PILOT} Optiune)( NR CURSA PILOT )

80 Tica

85 Ion

88 Tica

90 Radu

Fie relatiile, r de schema R si s de schema S. Notam cu T=R S.

Definitia 3.3. Relatia q de schema T, care pentru orice tuplu tIq exista tuplurile t_rIr si t_sIs, astfel incat t(R)=t_r, t(S)=t_s se numeste unirea relatiei r cu s si se noteaza cu

r s.

Fiecare tuplu tIq este o combinatie de doua tupluri t_rIr si t_sIs.

Se vede usor ca este adevarata egalitatea varianta=utilizare optiune. In definitia unirii nu este necesar ca R si S sa aiba intersectia nevida. Daca R S= atunci r s este produsul cartezian al lui r si s.

Exemplul 3.3. Fie relatiile

r (A B ) s( C D ) r s ( A B C D )

a₁ b₁ c₁ d₁ a₁ b₁ c₁ d₁

a₂ b₂ c₂ d₂ a₁ b₁ c₂ d₂

c₃ d₃ a₁ b₁ c₃ d₃

a₂ b₂ c₁ d₁

a₂ b₂ c₂ d₂

a₂ b₂ c₃ d₃

Operatia selectie poate fi inlocuita prin unire. Fie relatia r(R) din care trebuie sa selectam s_A=a (r), definim mai intai relatia s(A) cu un singur tuplu t(a)=a.

Atunci r s=s_A=a(r), deoarece R A=A.

r s====s_A=a(r).

Daca alegem doua atribute A si B din R luam in calitate de s relatia s(AB) cu un singur tuplu t, t(A)=a si t(B)=b, atunci: r s=s_{A=a, B=b}(r).Folosind operatia de unire se poate construi o operatie de selectie generalizata. Pentru aceasta folosim relatia s(A) cu tuplurile t₁, t₂,.,t_k, unde t_i(A)=a_i, a_iIdom(A_i), 1≤i≤k. Atunci

r s= s_{A1=a1, A2=a2,, Ak=ak} (r).

Din simetria operatiei de unire rezulta ca operatorul de unire este comutativ. De asemenea, pentru orice q, r si s avem proprietatea de asociativitate:

q r) s=q (r s)

Introducem unirea unei secvente finite de relatii.

Definitia 3.4. Fie relatiile s₁(S₁),..,s_m(S_m), schema de relatie R=S₁ S₂ S_m si S secventa S₁,,S_m. Fie o secventa de tupluri t_iIs_i cu 1≤i≤m. Spunem ca tuplurile t_i 1≤i≤m se pot uni pe S, daca exista un tuplu t de schema R astfel incat t_i=t(S_i) cu 1≤i≤m. Tuplul t se numeste rezultatul unirii tuplurilor t₁,,t_m pe S.

Exemplul 3.4. Fie relatiile s₁(A B), s₂(B C), s₃(A C)

s₁( A B ) s₂ ( B C ) s₃ ( A C )

a₁ b₁ b₁ c₂ a₁ c₂

a₁ b₂ b₂ c₂ a₁ c₁

a₂ b₂ a₂ c₁

Tuplurile <a₁,b₁>, <b₁,c₂>, <a₁,c₂> din s₁, s₂, s₃ unite cu rezultatul (a₁,b₁,c₂) si <a₁,b₂>, <b₂,c₁>, <a₂,b₂> sunt unite cu rezultatul (a₁,b₂,c₁).

s₁ s₂ s₃( A B C )

a₁ b₁ c₂

a₂ b₂ c₁

Daca in definitia de mai sus m=2 si daca tuplurile t₁ si t₂ sunt unite pe S=S₁ S₂ cu rezultatul t, atunci t₁=t(S₁) si t₂=t(S₂).

Din definitia unirii rezulta ca tuplul t trebuie sa apartina lui s₁ s₂ atunci exista t₁ si t₂ in s₁ si s₂ astfel incat t₁ si t₂ sunt unite pe S cu rezultatul t. Folosind asociativitatea si inductia se poate demonstra urmatorul rezultat:

Lema 3.1. Relatia s₁ . s_m este compusa din multimea tuplurilor t care sunt rezultate ale unirii pe S₁ .S_m a tuplurilor t₁,..,t_m care apartin corespunzator lui s₁,..,s_m.

Nu toate tuplurile fiecarei selectii pot sa intre in unire. Relatiile s₁,..,s_m sunt complet unite daca orice tuplu din fiecare relatie este componenta a unei secvente unite pe S.

Exemplul 3.5. In exemplul 3.5 se observa ca unirea celor trei selectii s₁,s₂ si s₃ nu este completa. Daca unim tuplurile <a₁,a₂> din s₁ si <b₂,c₁> din s₂ trebuie sa adaugam tuplul <a₁,c₁> la s₃ atunci relatia devine completa, unita cum se vede mai jos:

s₁( A B ) s₂ ( B C ) s₃ ( A C ) s₁ s₂ s₃= ( A B C )

a₁ b₁ b₁ c₂ a₁ c₁ a₁ b₁ c₂

a₁ b₂ b₂ c₁ a₁ c₂ a₁ b₂ c₁

a₂ b₁ a₂ c₂ a₂ b₁ c₂

Operatiile de unire si proiectie nu sunt reciproc inversabile, ele formeaza functii complementare.

Fie relatiile r(R) si s(S) si q=r s de schema R S. Punem r' =p(r). Atunci r' r deoarece pentru orice tuplu tIq proiectia t(R) trebuie sa fie un tuplu din r, iar r'=

Exemplul 3.6. Incluziunea aratata mai sus este stricta r' r.

r( A B ) s( B C ) r s= ( A B C ) p_AB(q)=r'( A B )

a1 b₁ b₁ c1 a1 b₁ c₁ a1 b₁

a1 b₂

Incluziunea devine egalitate daca si numai daca, pentru orice tuplu t_rIr exista un tuplu t_sIs cu t_r(R S)=t_s(R S). Incluziunea poate deveni egalitate fara ca r si s sa fie complet unite.

Aratam mai jos cazul in care are loc egalitatea:

r( A B ) s( B C ) r s= ( A B C ) p_AB(q)=r'( A B )

a₁ b₁ b₁ c₁ a₁ b₁ c₁ a₁ b₁

a₁ b₂ b₂ c₂ a₁ b₂ c₂ a₁ b₂

Totusi daca s'=p_s(q) atunci conditia r=r' si s=s' este echivalenta cu conditia ca r si s sa fie complet unite.

Fie q o relatie de schema R S si r=p_R(q) si s=p_S(q). Punem q'=r s. Daca tIq atunci t(R) Ir si t(S) Is deci tIq'. Prin urmare qIq'.

Daca q=q' atunci spunem ca relatia q se descompune fara pierderi in raport cu schemele R si S. Inaintand inca un pas, fie r'=p_R(q') si s'=p_S(q) si q''=r' s'. Pentru ca sa obtinem q'' din q aplicam procedura de proiectie-unire.

Fie T=R S, atunci p_T(r)= p_T p_R(r))= p_T(r)= p_T p_S(r))= p_T(s). Prin urmare, r si s sunt complet unite, deoarece pentru orice t_rIr exista t_sIs astfel incat t_R(T)=t_S(T) si invers. Prin urmare r=r' si s=s' deci q si q'' coincid, de unde rezulta ca procedura de proiectie-unire este idempotenta, rezultatul aplicari primei uniri coincide cu rezultatul aplicarii celei de a doua.

3.5. Operatorul de echiunire

In definitia operatorului de unire, relatiile sunt unite sau nu cand au o multime de atribute comune. Operatia de unire naturala este o operatie de unire a doua relatii r si s in raport cu multimea de atribute commune. Valorile ne comune sunt eliminate din rezultatul unirii celor doua relatii.

Definitia 3.5. Fie relatiile r(R) si s(S) cu A_iIR si B_iIS, dom (A_i)=dom(B_i),1≤i≤m si A_i si B_i se presupune ca sunt diferite. Relatia:

q(RS)=

se numeste echiunirea relatiilor r si s in raport cu A₁=B₁,,A_m=B_m. Ea se noteaza cu r[A₁=B₁,,A_m=B_m]s.

Exemplul 3.7. Consideram proiectia relatiei 'ORAR' in raport cu atributele 'PUNCT_DECOLARE (PD)', 'PUNCT_ATERIZARE (PA)', ' NUMAR_CURSA (NC)', numita 'ruta' si relatia 'adresa' de atribute 'PILOT (PL)' si 'AEROPORT (A)'.

Ruta ( NC PD PA ) Adresa ( PL A )

70 Bucuresti Craiova Luca Bucuresti

75 Craiova Bucuresti Lupu Cluj

80 Bucuresti Cluj Lica Craiova

85 Cluj Bucuresti Lari Timisoara

90 Iasi Timisoara Dorin Iasi

Relatia 'poate_sa_zboare' arata in ce oras traieste pilotul si directia cursei.

Poate-sa-zboare ( NC PD PA PL A )

70 Bucuresti Craiova Luca Bucuresti

75 Craiova Bucuresti Lica Craiova

80 Bucuresti Cluj Luca Bucuresti

85 Cluj Bucuresti Lupu Cluj

90 Iasi Timisoara Dorin Iasi

Aceasta relatie este calculata prin echiunire dupa atributele PD si A. Echiunirea se mai numeste si unire naturala. Unirea nu repeta coloanele unite, si prin aceasta difera de echiunire.

Pana acum singurul operator de comparare a valorilor unui domeniu a fost egalitatea. Se pot compara valorile unui domeniu folosind comparatorii <, ≤, > Pentru o examinare generala a comparatorilor se introduce o multime Q de simboluri pentru operatiile binare pe perechi de domenii. Daca qI Q si A si B doua atribute spunem ca A este q comparabil cu B, daca q este o relatie binara in dom(A) x dom(B).

3.6. Operatorul de q unire

Operatia de q-unire defineste o relatie ce contine tuplurile produsului cartezian rxs ce

satisfac un predicat P de forma r.A_iqs.B_j unde q este un comparator.

r _P s =s_P(rAs).

Simbolul cel mai utilizat din multimea Q pentru comparare este '='. Compararile vor fi folosite si pentru generalizarea operatorului de selectie si unire. Echiunirea este o extindere a operatorului de unire, iar operatorul q-unire este o extindere a operatorului de echiunire.

Exemplul 3.8. Presupunem ca sunt date orele de zbor a avioanelor intre orasele A si B si intre orasele B si C care au legatura prin calcularea relatiei tranzit intre A si C.

Timp( A B) ( NC OD OA )

75 9:30 10:30

76 12:45 14:40

81 16:00 18:00

91 20:00 22:00

97 21:00 23:00

Tabelul 1 : Zbor intre orasele A si B:

Timp( B C )( NC OD OA )

62 8:00 12:00

75 11:00 12:00

99 19:00 20:00

110 23:30 00:30

Tabelul 2 : Zbor intre orasele B si C:

Tranzit ( A C) ( NC OD OA NC' OD' OA')

Tabelul 3 : Zborurile de tranzit intre A si C:

Definitia 3.6. Fie r(S) si s(S) pentru care R S= si AIR si BIS sunt q-comparabile pentru qIQ. Relatia

q(RS)=

se numeste r q-unita cu s si se noteaza cu r[AqB]s.

Fie A₁,A₂,,A_m R si B₁,B₂,,B_m S si operatiile q_iIQ, 1≤i≤m. Se numeste calificare si se noteaza cu

Q=A₁q B₁ A₂q B₂ A_mq_m B_m.

Unirea relatiilor r(R) si s(S) in raport cu calificarea Q este relatia:

q(RS)=

Aceasta operatie esentiala in realizarea sistemelor relationale este notata cu:

JOIN(r,s/Q)

si se reprezinta grafic:

Unirea naturala a lui r si s, notata simplu cu r s sau JOIN(r,s) este o echiunire a lui r si s in raport cu atributele comune in R si S, urmata de proiectie care permite a conserva numai acele atribute comune.

Exemplul 3.9 Fie relatiile material(COD_MATERIAL, DENUMIRE_MATERIAL, PRET) si reper( COD_REPER, DENUMIRE_REPER, COD_MATERIAL, CANTITATE_MATERIAL).

In urma unirii se obtine o relatie care specifica din ce material este construit fiecare reper.

3.7. Operatorul de impartire

Operatorul de impartire se aplica in putine situatii practice.

Definitia 3.7. Fie schemele de relatii R, S si S R si R'=R-S, si relatiile r(R) si s(S). Relatia

r'(R')=

se numeste catul impartirii relatiei r la s si se noteaza cu r s.

Exemplu 3.10 Fie relatia r(PILOT, TIP_AVION) si s(TIP_AVION):

r( PILOT TIP AVION ) s( TIP AVION )

Dan Rombac Rombac

Dan BAC111 BAC111

Dan IAR500 IAR500

Dragos Rombac

Dragos IAR500

Dragos BAC111

Mihai Rombac

Daca dorim sa gasim acei piloti care au drept de conducere pe toate avioanele calculam r s.

r s( PILOT )

Dan

Dragos

Operatorul de impartire poate fi exprimat cu ajutorul operatorilor dati anterior.

Fie R, S, S R si r(R) si s(S). Atunci:

r s=p_R'(r)- p_R' p_R'(r ) s)-r) , r(R), s(S), R'=R-S, S R

Operatorul de impartire se reprezinta grafic astfel:

Operatorul de selectie extinsa

Daca in locul simbolului '=' din operatorul de selectie σ_A=a(r) punem simbolul q, obtinem un operator de selectie extins notat σ_Aqa

Definitia 3.8. Fie relatia r de schema R si atributul A. Presupunem ca valorile lui sunt q-comparabile , atunci relatia:

_Aqa(r)=

se numeste selectie extinsa (q-selectie).

O selectie a relatiei R in raport cu o calificare Q=A₁q a₁ A_mq_m a_m este o relatie de aceeasi schema ale carei tupluri sunt acelea din R care satisfac calificarea Q.

Sunt utilizate urmatoarele notatii pentru selectia extinsa:

- _Q(r);

-SELECT(r/ A₁q a₁ A_mq_m a_m

-SELECT(r/Q).

Selectia extinsa se reprezinta grafic prin:

3.9. Relatii constante

In proprietatile operatorului de unire s-a aratat ca, rezultatul unei operatii de selectie se poate obtine prin unirea relatiei cu o relatie constanta. Introducem un procedeu de descriere a unei relatii constante reprezentata direct in expresii.

Definitia 3.9. Fie A₁,A₂,,A_n, n atribute diferite iar c_i sunt constante din dom(A_i), 1 i n, atunci <c₁:A₁,c₂:A₂,,c_n:A_n> reprezinta tuplul constant <c₁,c₂,,c_n> de schema A₁A₂A_n. Fie c_ijIdom(A_i), 1 i n, 1 j k. Atunci:

reprezinta relatia constanta si are forma:

A₁ A₂ .. A_n

===============

c₁₁ c₂₁ ....c_n1

c₁₂ c₂₂ ... c_n2

..

c_1k c_2k ...c_nk

_{Relatia constanta cu numar oarecare de tupluri si un numar de atribute poate fi construita din relatii constante cu un singur atribut si un singur tuplu cu ajutorul operatorilor de unire si reuniune.}

Exemplul 3.11.

PILOT TIP_AVION

Dan Rombac

Vali BAC111

poate fi reprezentata prin <Vali:PILOT> <BAC111:TIP_AVION> <Dan: PILOT> <Rombac:TIP_AVION>

3.10 Operatorul de redefinire a atributelor

Sa consideram relatia utilizare care specifica ce avion este utilizat intr-o cursa intr-o anumita zi.

Definitia 3.10. Fie relatia r de schema R, A IR si B un atribut care nu apartine lui R si R'=(R-A) B. Schimband pe A cu B in relatia r obtinem relatia notata cu d_A←B(r) care este data de relatia:

r'(R')=

Sa consideram relatia utilizare data in tabelul 1 care indica ce avion poate fi utilizat intr-o cursa data, intr-o zi dintr-un orar dat.

Presupunem ca, pentru un orar dat trebuie sa aflam cursele care folosesc acelasi avion in aceeasi zi.

Tabelul 1: Relatia de 'Utilizare' indica ce avion poate fi folosit pentru o cursa data.

Utilizare ( NC DATA TIP AVION )

70 7-01 Rombac

75 8-01 Rombac

78 7-01 Rombac

80 7-01 IAR500

85 7-01 IAR400

86 8-01 IAR300

88 8-01 IAR100

90 7-01 Rombac

91 8-01 BAC11

Pentru a formaliza cererea de mai sus se utilizeaza operatorul de redefinire.

Fie relatia r de schema R care contine atributele A₁, A₂, , A_k. Fie atributele B₁, B₂, , B_k diferite cu dom( A_i)= dom(B_i), 1 i k. Notam relatia de redefinire a atributelor A₁, A₂, , A_k cu B₁, B₂, , B_k in relatia r cu :

d_{A1, , Ak← B1, , Bk}(r).

3.11. Algebra relationala

Operatorii de reuniune, intersectie, diferenta, complementara activa, proiectie, selectie, unire, q-unire, echiunire, impartire si redefinire, impreuna cu relatiile constante si relatiile regulate ce permit formarea expresiilor relationale.

Orice expresie construita corect cu ajutorul acestor operatori si relatii se numeste expresie algebrica. Pentru orice expresie algebrica E si valorile curente date tuturor relatiilor din E in raport cu care E se poate calcula se obtine o relatie unica.

Prin urmare E reprezinta o transformare a unei multimi de relatii intr-o singura relatie.

Fie U multimea tuturor atributelor care descriu un univers, D o multime de domenii si fie dom o functie completa din U in D. Fie in continuare R= o multime de scheme de relatii diferite, unde R_i U, 1 i p si d= o multime de relatii astfel incat relatia r_i este de schema R_i. Fie Q o multime de comparatori definiti pe domeniile din D care contine cel putin o relatie de egalitate si de inegalitate pentru fiecare domeniu.

Definitia 3.11. Se numeste algebra relationala in raport cu U, D, dom, R, d si Q septetul B=( U, D, dom, R, d, Q O), unde O este multimea opratorilor enuntati mai sus ce folosesc atributele din U si relatiile din d.

Definitia 3.12. Se numeste expresie algebrica in raport cu B orice expresie corect construita din relatii care apartin lui d si relatii constante cu schema din U care folosesc operatori din O

In expresii se admit paranteze rotunde si se presupune ca nici un operator binar nu are prioritate in executare fata de celalalt cu exceptia fata de Chiar putem sa eliminam parantezele pentru secvente legate prin unul si acelasi operator daca operatia este asociativa.

Se observa ca doua relatii cu una si aceeasi schema nu sunt permise. Numele relatiilor este analog unei variabile dintr-un program unde r_i reprezinta o relatie de schema R_i, unde i ia valori de la 1 la n.

Deoarece rezultatul fiecarei operatii relationale este o relatie atunci orice expresie algebrica se defineste ca o functie care transforma o multime de relatii intr-o relatie. Schema de relatie depinde de schemele relatiilor care compun expresia E.

Notam cu sch(E) schema expresiei algebrice E care se poate defini recursiv conform urmatoarelor reguli:

1. Daca E este r_i atunci sch(E)=R_i.

2. Daca E este relatia constanta atunci sch(E) este schema relatiei constante.   

3. Daca E=E₁ E₂, E₁ E₂, E₁E₂, E₁sau _c(E₁) unde c este o multime de conditii,

atunci sch(E)= sch(E₁).

4. Daca E=p_X(E₁) atunci sch(E)=X.

Daca E=E₁ E₂ sau E₁ [C] E₂ pentru o multime de conditii C atunci sch(E)=

sch(E₁) sch(E₂).

6. Daca E=E₁ E₂ atunci sch(E)=sch(E₁)-sch(E₂).

7. Daca E=d_{A1A2 Ak B1B2Bk}(E₁) atunci sch(E)= (sch(E)-A₁A_k) B₁B_k.

Daca E este o expresie algebrica intre schemele relatiilor s₁, s₂,, s_k notate S₁, S₂, , S_k atunci E este o transformare :

E:Rel( S₁)* Rel( S₂)** Rel(S_k) Rel( sch(E)),

unde Rel( R) reprezinta multimea tuturor relatiilor de schema R. Uneori se pune problema folosirii relatiei de complementare in algebra relationala care se numeste algebra relationala complementara.

Multimea operatorilor formata din: reuniune, diferenta, proiectie, selectie si unire naturala se numeste multimea primara de operatori si se noteaza cu O^p.

Dupa cum s-a observat in capitolul precedent operatorii relationali nu sunt independenti. Exista multimi restranse de operatori care au aceeasi putere ca si multimea intreaga.

Observatia 1. Rezultatul oricarei operatii de selectie extinsa poate fi obtinut prin folosirea operatorului de selectie σ_AqB sau σ_Aqa si a unor operatori din O^p din care s-a eliminat selectia obisnuita, presupunand ca multimea relatiilor binare este inchisa fata de negatie.

Observatia 2. Operatorul de impartire poate fi scris cu ajutorul proiectiei, diferentei si unirii, astfel:

r s=p_R'(r)- p_R' p_R'(r ) s)-r) , r(R), s(S), R'=R-S, S R

Teorema 3.1. Pentru orice expresie de relatie E(s₁,s₂,,s_q) in raport cu algebra relationala B, exista o expresie E'(s₁,s₂,,s_q) in raport cu algebra de relatii B care defineste aceleasi functii si care utilizeaza numai relatii constante cu un singur atribut cu un tuplu, operatori de selectie cu un singur criteriu de comparare, unire naturala, proiectie, reuniune, diferenta si redefinire

Demonstratie: Toate relatiile constante din E se inlocuiesc cu expresii care contin relatii constante cu un atribut si un singur tuplu si operatori de reuniune si unire.Operatorul de selectie generalizat se exprima numai cu operatori din O^p(Obs. 1). Din (1) rezulta ca operatorul de impartire se poate exprima cu ajutorul proiectiei, unirii si diferentei. Complementul activ se exprima cu ajutorul diferentei. Observam ca unirea este produs cartezian.

Corolar 3.1. Fie E o expresie in raport cu algebra de relatie B =[U, D, dom, R, d,Q,O] Atunci exista expresia E' in raport cu B, care defineste aceeasi functie de s₁,s₂,,s_q si care foloseste numai relatii constante cu atribute unice si formate numai dintr-un singur tuplu, operatori de selectie cu o singura comparatie, operatorii de unire, proiectie, unire naturala, complement si redefinirea.

Demonstratie: Din teorema 3.1 rezulta ca singurul operator, care trebuie sa fie scos din E, este diferenta. Se mai observa ca E₁-E₂= .

3.12. Operatorul SPLIT

Operatorul SPLIT are ca argument o singura relatie si ca rezultat al aplicarii se obtin doua relatii.

Definitia 3.12. Fie r o relatie de schema R si b(t) un predicat pe R, relatiile s si s' se obtin prin spargerea lui r in raport b si se noteaza cu SPLIT(r: b),unde

s=, s'= este evident ca s'=r-s.

Exemplul 3.13. Fie relatia drept-de-cond(PILOT,TIP_AVION), fie

b (t)=t(TIP_AVION=Rombac sau TIP_AVION=BAC111) atunci se obtin relatiile s si s' :

s( PILOT TIP AVION ) s'( PILOT TIP AVION )

Dan Rombac Dan IAR500

Dan BAC111 Lica IAR500

Lica Rombac

Lica BAC111

Lupu Rombac

Lupu BAC111

Exercitii;

Fie relatiile r(ABC) si s(BCD), aI dom(A), bI dom(B). Care din urmatoarele relatii sunt corecte?

a) r s, b) p_B( r)-p_B(s), c) s_B=b( r), d) s_A=a,B=b ( r), e) r s,

f) p_A( r) p_D (s)

Fie relatiile r si s

r( A B C ) s(B C D )

a b c b^' c^' d

a b^' c^' b^'' c^' d

a^' b^' c b^'' c d

3. Calculati urmatoarele expresii din exercitiul 1 si , s_A=a( r).

4. Fie relatia r( R) AIR a,a'Idom(A). Sa se demonstreze ca :

s_A-a,A=a'(r )= sau s_A-a,A=a'(r )= s_A-a(r ).

Fie relatiile r si s de schema R si K o cheie comuna. Care din urmatoarele

relatii au cheie? r s , r s ,r-s, r s, p_K( r).

Fie relatiile r si s de schema R aratati ca: s_A=a (rqs)= s_A-a(r )q s_A-a(s ) unde q

este un operator boolean.

7. Elaborati algoritmul pentru operatorul nerelational split.