Algebra relaţionalăbd.ac.tuiasi.ro/Doc/curs/Curs_03.pdfAlgebra relaţională Se bazează pe o...

Algebra relaţională

� Reuniune, intersecţie, diferenţă

� Redenumire, selecţie, proiecţie, joncţiune

� Interogări în algebra relaţională

� Valori NULL în algebra relaţională

� Vederi

�Actualizare - funcţie care pornind de la o bază de date produce o altă bază de date (fără a-i modifica schema).

� Interogare - funcţie care returnează o relaţie, plecând de la o bază de date.

Algebra relaţională

� Se bazează pe o colecţie de operatori ce sunt aplicaţi

relaţiilor, producând relaţii.

Operatorii algebrici relaţionali se împart în următoarele clase:

� Operatori clasici din teoria mulţimilor – reuniune, intersecţie, diferenţă;

� Operatori de redenumire, selecţie, proiecţie;

� Operatorul join (joncţiune), împreună cu variantele sale – joncţiune naturală, produs cartezian, theta joncţiune şi joncţiune

externă.

Reuniune, intersecţie, diferenţă

Reuniune, intersecţie, diferenţă - se aplică doar asupra perechilor de relaţii definite pe aceleaşi atribute.

GPS

Producător MODEL

Nokia N2310

Samsung S5100

Samsung S5600

Nokia N4215

RADIO

Producător MODEL

Nokia N4215

Samsung S2110

Samsung S5600

Samsung S1100

Reuniune?

Diferenţă? Intersecţie?

Reuniune, intersecţie, diferenţă

Definiţii

Reuniunea a două relaţii r1(X) şi r2(X) este relaţia notată r1 ∪ r2 care conţine tupluri ce aparţin fie lui r1 fie lui r2, fie ambelor relaţii r1 şi r2.

Intersecţia dintre relaţiile r1(X) şi r2(X) este relaţia notată r1 ∩ r2

formată din tuplurile comune relaţiilor r1 şi r2.

Diferenţa dintre relaţiile r1(X) şi r2(X) este relaţia notată r1 - r2

care conţine tuplurile din r1 care nu se regăsesc în r2.

Redenumire

TATA_COPIL

Tata Copil

Adam Dan

Adam Marian

Radu Cristi

Radu Catalin

MAMA_COPIL

Mama Copil

Eva Dan

Eva Lucian

Maria Cristi

Carmen Catalin

TATA_COPIL U MAMA_COPIL ??

Redenumire

Operaţia de redenumire (ρ)

Limitările impuse operatorilor standard din teoria mulţimilor pot fi restrictive în anumite situaţii.

Exemplu

� Să considerăm cele două relaţii din figura 3.1.

TATA_COPIL

Tata Copil

Adam Dan

Adam Marian

Radu Cristi

Radu Catalin

MAMA_COPIL

Mama Copil

Eva Dan

Eva Lucian

Maria Cristi

Carmen Catalin

TATA_COPIL U MAMA_COPIL ??

Figura 3.1 Reuniune logică, dar incorectă

Ar avea sens executarea unei reuniuni între cele două relaţii cu scopul de a obţine toate perechile ’părinte – copil’ din baza de date.

Acest lucru nu este însă posibil deoarece atributul denumit de noi ’părinte’ are numele ’tata’ într-o relaţie şi numele ’mama’ în cealaltă relaţie.

Redenumire

Operatorului de redenumire – adaptează numele atributelor atunci când este necesară aplicarea unui operator din teoria mulţimilor.

Obs. Acest operator modifică numele atributelor lăsând intact conţinutul relaţiei.

Exemplu

TATA_COPIL Tata Copil

Adam Dan

Adam Marian

Radu Cristi

Radu Catalin

Fig.3.2 Exemplu de redenumire

Parinte Tata←ρ

Parinte Copil

Adam Dan

Adam Marian

Radu Cristi

Radu Catalin

(TATA_COPIL)

Redenumire

Definiţie

Fie r o relaţie definită pe mulţimea X de atribute şi fie Y o altă mulţime de atribute având aceeaşi cardinalitate ca şi X; fie secvenţele ordonate şi A1A2...Ak , B1B2...Bk formate din atributele mulţimii X respectiv Y.

Redenumirea conţine pentru fiecare tuplu t din r un

tuplu t’ definit pe Y astfel încât , .

În practică, cele două secvenţe A1A2...Ak şi B1B2...Bk vor conţine doar

atributele ce urmează a fi redenumite şi noile lor nume.

... ... ( )1 2 k 1 2 kA A A B B B r←ρ

'[ ] [ ]i it B t A= ,i 1 k=

Selecţie

Operatorul de selecţie (σ) Rezultatul unei selecţii conţine tuplurile relaţiei operand ce satisfac

condiţia asociată operatorului.

Exemplu

Se consideră relaţia ANGAJAT din figura următoare:

ANGAJAT

Nume Prenume Varsta Salariu

Ionescu Maria 25 2000

Popescu Lucia 40 3000

Diaconescu Nicu 36 4500

Ionescu Marin 40 3900

Virsta 30 Salariu 4000< >σ ∨ ( ANGAJAT ) ??

Selecţie

Operatorul de selecţie (σ)

Exemplu

ANGAJAT



Popescu Lucia 40 3000


Ionescu Marin 40 3900

Virsta 30 Salariu 4000< >σ ∨ ( ANGAJAT )




Fig.3.3 Exemplu de selecţie

După cum se poate observa, sunt selectate tuplurile din relaţia ANGAJAT care îndeplinesc condiţia: Varsta < 30 sau Salariu > 4000 (formulă propoziţională).

Selecţie

Definiţii

Fiind dată o relaţie r definită pe o mulţime de atribute X, spunem că o

formulă propoziţională F definită pe X este o formulă compusă din condiţii

atomice de tipul AθB sau Aθc legate prin conectorii ∨ (OR), ∧(AND) şi

¬(NOT), în care:

� θ este un operator de comparaţie ( );

� A şi B sunt atribute din X compatibile (conţin valori pentru care are sens comparaţia);

� c este o constantă compatibilă cu domeniul atributului A.

, , , , ,= ≠ < ≤ > ≥

Selecţie

Definiţii

Fiind dată formula propoziţională F şi tuplul t, se defineşte valoarea

de adevăr a lui F pe t:

� AθB este adevărată dacă şi numai dacă t[A] este în relaţia θ cu t[B];

� Aθc este adevărată dacă şi numai dacă t[A] este în relaţia θ cu c;

� F1 ∨F2, F1∧F2 şi ¬F1 au semnificaţia uzuală.

O selecţie σF(r) produce o relaţie care are aceleaşi atribute ca relaţia r şi care conţine acele tupluri din r pentru care F este adevărată.

Proiecţie

Operatorul de proiecţie (π)

Definiţie

Fie dată relaţia r definită pe mulţimea de atribute X şi o submulţime Y a lui X.

Proiecţia relaţiei r pe Y (notată ) reprezintă mulţimea tuplurilor definite pe Y obţinute din tuplurile lui r luând în considerare numai valorile corespunzătoare atributelor din Y:

( )Y rπ

( ) { [ ]/ }Y r t Y t rπ = ∈

ANGAJAT

Nume Prenume Departament Sef Ionescu Maria Vanzari Luca Popescu Lucia Vanzari Luca Diaconescu Maria Personal Damian Ionescu Marin Personal Damian

,Departament Sefπ (ANGAJAT) ??

Proiecţie

Situaţii în care numărul de tupluri ale rezultatului este egal, respectiv mai mic decât numărul de tupluri ale operandului:

Nume Prenume Varsta Salariu Ionescu Maria 25 2000 Popescu Lucia 40 3000 Diaconescu Nicu 36 4500 Ionescu Marin 45 3900

ANGAJAT

Varsta Salariu

25 2000

40 3000

36 4500

45 3900

,Varsta Salariuπ (ANGAJAT)

Fig.3.5 Exemplu de proiecţie cu acelaşi număr de tupluri ca şi operandul

ANGAJAT

Nume Prenume Departament Sef Ionescu Maria Vanzari Luca Popescu Lucia Vanzari Luca Diaconescu Maria Personal Damian Ionescu Marin Personal Damian

,Departament Sefπ (ANGAJAT)

Departament Sef

Vanzari Luca

Personal Damian

Fig.3.4 Exemplu de proiecţie cu mai puţine tupluri decât operandul

Proiecţie

Întrebare:

Când conţine acelaşi număr de tupluri ca şi r ?

( )Y rπ

Proiecţie

Propoziţie

conţine acelaşi număr de tupluri ca şi r dacă şi numai dacă Y este o super-cheie pentru r.

( )Y rπ

Joncţiune

Operatorul joncţiune – „join” � Permite realizarea unei conexiuni între datele conţinute de diverse relaţii.

Joncţiunea naturală ( ) – „natural join” - corelează datele din relaţii diferite pe baza valorilor egale asociate atributelor cu acelaşi nume.

Cod Data Cadru Judet NrInmat 143256 25/10/92 567 IS 02 AAA 987554 26/10/92 456 IS 02 AAA 987557 26/10/92 456 IS 03 BBB 630876 15/10/92 456 VS 03 BBB 539856 12/10/92 567 VS 03 BBB

NrInmat Judet Proprietar Adresa 03 BBB IS Maftei Eduard Nicolina 30 01 CCC IS Maftei Eduard Nicolina 30 02 AAA IS Luca Marian Primaverii 4 03 BBB VS Melinte Dan Primaverii 17

Cod Data Cadru Judet NrInmat Proprietar Adresa

143256 25/10/92 567 IS 02 AAA Luca Marian Primaverii 4 987554 26/10/92 456 IS 02 AAA Luca Marian Primaverii 4 987557 26/10/92 456 IS 03 BBB Maftei Eduard Nicolina 30 630876 15/10/92 456 VS 03 BBB Melinte Dan Primaverii 17 539856 12/10/92 567 VS 03 BBB Melinte Dan Primaverii 17

><CONTRAVENTIE AUTOVEHICUL

CONTRAVENTIE AUTOVEHICUL

Joncţiune

Operatorul joncţiune – „join” � Permite realizarea unei conexiuni între datele conţinute de diverse relaţii.

� Există două versiuni principale ale acestui operator, care, oricum, se pot obţine una din cealaltă.

Joncţiunea naturală ( ) – „natural join” - corelează datele din relaţii diferite pe baza valorilor egale asociate atributelor cu acelaşi nume.

Definiţie

Fie r1(X1) şi r2(X2) două relaţii. Joncţiunea naturală este o relaţie

definită pe X1X2 (reuniunea dintre X1 şi X2) astfel încât:

Pe scurt putem scrie:

><

1 2r r><

1 2r r>< { / , , . . [ ] [ ] }1 2 1 1 2 2 1 1 2 2t definit pe X X t r t r a i t X t si t X t= ∃ ∈ ∃ ∈ = =

{ / [ ] [ ] }1 2 1 1 2 2t definit pe X X t X r si t X r= ∈ ∈1 2r r><

CONTRAVENTIE Cod Data Cadru Judet NrInmat 143256 25/10/92 567 IS 02 AAA 987554 26/10/92 456 IS 02 AAA 987557 26/10/92 456 IS 03 BBB 630876 15/10/92 456 VS 03 BBB 539856 12/10/92 567 VS 03 BBB

AUTOVEHICUL

NrInmat Judet Proprietar Adresa 03 BBB IS Maftei Eduard Nicolina 30 01 CCC IS Maftei Eduard Nicolina 30 02 AAA IS Luca Marian Primaverii 4 03 BBB VS Melinte Dan Primaverii 17

Cod Data Cadru Judet NrInmat Proprietar Adresa

143256 25/10/92 567 IS 02 AAA Luca Marian Primaverii 4 987554 26/10/92 456 IS 02 AAA Luca Marian Primaverii 4 987557 26/10/92 456 IS 03 BBB Maftei Eduard Nicolina 30 630876 15/10/92 456 VS 03 BBB Melinte Dan Primaverii 17 539856 12/10/92 567 VS 03 BBB Melinte Dan Primaverii 17

><CONTRAVENTIE AUTOVEHICUL

Exemplu

Joncţiunea naturală a celor două relaţii s-a obţinut prin combinarea fiecărui tuplu din CONTRAVENŢIE cu exact un tuplu din AUTOVEHICUL:

• cu cel mult unul deoarece atributele Judet şi NrInmat formează o cheie a relaţiei AUTOVEHICUL; • cu cel puţin unul datorită constrângerii de referinţă dintre atributele Judet şi NrInmat din CONTRAVENTII şi relaţia AUTOVEHICUL.

Joncţiune

Definiţie. Fie r1(X1) şi r2(X2) două relaţii. Spunem că joncţiunea naturală

este completă dacă: 1 2r r><

,1 1t r t∀ ∈ ∃ ∈ . . [ ]1 1a i t X t=,1 2r r><

, '2 2t r t∀ ∈ ∃ ∈ . . '[ ]2 2a i t X t=,1 2r r><

Angajat Departament Ionescu vanzari Balint productie Baltag productie

Departament Sef

productie Manole

vanzari Burlacu

Angajat Departament Sef Ionescu vanzari Burlacu Balint productie Manole Baltag productie Manole

r1 r2

1 2r r><

Fig.3.6 Exemplu de joncţiune naturală completă

Joncţiune


Departament Sef

productie Manole

depanare Burlacu

Angajat Departament Sef Balint productie Manole Baltag productie Manole

r1 r2

1 2r r><

Exemplu de joncţiune naturală incompletă

Joncţiune


Departament Sef

marketing Manole

depanare Burlacu

Angajat Departament Sef

r1 r2

1 2r r><

Exemplu de joncţiune vidă

Joncţiune

Joncţiunea externă – „outer join”

Operatorul de joncţiune exclude tuplurile unei relaţii ce nu au corespondent în celălalt operand.

Operatorul de joncţiune externă - asigură prezenţa în relaţia rezultat a tuturor tuplurilor unei relaţii, acestea fiind completate cu valori NULL atunci când nu au corespondent în cealaltă relaţie.

Acest operator are trei variante :

� joncţiune externă la stânga – extinde doar tuplurile primului operand;

� joncţiune externă la dreapta – extinde doar tuplurile celui de-al doilea operand;

� joncţiune externă completă – extinde toate tuplurile.

Joncţiune

Exemplu

r1

Angajat Departament Ionescu vanzari Balint productie Luca productie

Departament Sef productie Manole achizitii Burlacu

r2

><

Angajat Departament Sef Ionescu vanzari null Balint productie Manole Luca productie Manole

Angajat Departament Sef Balint productie Manole Luca productie Manole null achizitii Burlacu

Angajat Departament Sef Ionescu vanzari null Balint productie Manole Luca productie Manole null achizitii Burlacu

r1 LEFT r2 ><r1 RIGHT r2

><r1 FULL r2

Fig.3.7 Exemple de joncţiuni externe

Joncţiune

Theta–joncţiune şi echi–joncţiune În general produsul cartezian nu prezintă interes deoarece combină tuplurile celor doi operanzi într-o manieră lipsită de semnificaţie.

ANGAJAT Angajat Proiect Ionescu A Balint A Balint B

PROIECT

Cod Nume A Venus B Marte

><

Angajat Proiect Cod Nume Ionescu A A Venus Balint A A Venus Balint B A Venus Ionescu A B Marte Balint A B Marte Balint B B Marte

ANGAJAT PROIECT

Figura 3.8 Produs cartezian

Joncţiune

Operatorul de theta–joncţiune - produs cartezian urmat de o selecţie.

( )1 F 2 F 1 2r r r r=σ>< ><

F este condiţia de selecţie

ANGAJAT Angajat Proiect Ionescu A Balint A Balint B

PROIECT

Cod Nume A Venus B Marte

Proiect=Codσ ><(ANGAJAT PROIECT)

Angajat Proiect Cod Nume

Ionescu A A Venus

Balint A A Venus

Balint B B Marte

Figura 3.9 Produs cartezian urmat de o selecţie

Joncţiune

Echi–joncţiunea - o theta–joncţiune în care condiţia de selecţie F este o conjuncţie de atomi de egalitate, fiecare atom implicând câte un atribut din fiecare operand.

� A treia relaţie din figura anterioară - rezultat al unei echi–joncţiuni.

Obs.

1. Majoritatea sistemelor de gestiune a bazelor de date nu exploatează avantajele numelor atributelor în combinarea relaţiilor ⇒ theta şi echi–joncţiunea au o importanţă deosebită.

2. interogările SQL corespund echi – joncţiunilor.

3. Joncţiunea naturală a devenit disponibilă doar în versiunile recente de SQL.

Joncţiune

Interogări în algebra relaţională

� Interogarea - funcţie care, aplicată asupra unei instanţe a unei baze de date, produce o relaţie;

� Fiind dată o schemă R a unei baze de date, o interogare este o funcţie care, pentru fiecare instanţă r a lui R, produce o relaţie definită pe o mulţime X de atribute.

� În algebra relaţională, interogările unei scheme R de baze de date sunt formulate cu ajutorul unor expresii, ale căror atomi sunt relaţii din R.


Exemple

Se consideră o bază de date formată din relaţiile:

ANGAJAT (NrInreg, Nume, Varsta, Salariu)

SUPERVIZOR (NrSup, NrAng)

ANGAJAT

NrInreg Nume Varsta Salariu 101 Maria Ionescu 34 40 103 Maria Balint 23 35 104 Lucia Popescu 38 61 105 Nicu Luca 44 38 210 Marcel Burlacu 49 60 231 Alin Lupu 50 60 252 Nicu Luca 44 70 301 Andrei Popa 34 70 375 Maria Ionescu 50 65

SUPERVIZOR

NrSup NrAng

210 101

210 103

210 104

231 105

301 210

301 231

375 252

Fig.3.10 Bază de date pentru exemplificarea interogărilor în algebra relaţională

1) Să se găsească numerele de înregistrare pentru supervizorii acelor angajaţi ce câştigă mai mult de 40.



(NrSupπ ( )Salariu 40 ANGAJAT>σSUPERVIZOR )>< (NrAng NrInreg=)


2) Să se găsească numerele de înregistrare şi numele supervizorilor ce au numai subalterni ce câştigă mai mult de 40.



� se găsesc toţi supervizorii pentru care există subalterni care câştigă maxim 40;

)(NrAng NrInregSUPERVIZOR =>< ( )Salariu 40 ANGAJAT≤σ(NrSupπ )


ANGAJAT


SUPERVIZOR

NrSup NrAng

210 101

210 103

210 104

231 105

301 210

301 231

375 252



� se aplică operatorul de diferenţă între submulţimea supervizorilor şi

mulţimea obţinută la pasul anterior.

)(NrAng NrInregSUPERVIZOR =>< ( )Salariu 40 ANGAJAT≤σ(NrSupπ ) )

( )NrSup SUPERVIZORπ −(NrInreg NrSupANGAJAT =><, (NrInreg Numeπ

)


ANGAJAT


SUPERVIZOR

NrSup NrAng

210 101

210 103

210 104

231 105

301 210

301 231

375 252

Valori NULL în algebra relaţională

În cele discutate anterior am presupus că expresiile algebrice sunt aplicate unor relaţii ce nu conţin valori NULL.

Ţinând cont de importanţa valorilor NULL în aplicaţii, vom vedea care este impactul lor asupra limbajelor de interogare şi actualizare a datelor.

Exemplu. Să considerăm relaţia din figura următoare

Nume Varsta Salariu Ionescu 35 500 Popescu 27 600 Popa NULL 500

PERSOANA

Figura 3.12 Relaţie cu valori NULL

şi selecţia ( )Varsta 30 PERSOANA>σ

.

- Primul tuplu va contribui la rezultatul selecţiei, iar al doilea tuplu nu. - Ce putem spune despre al treilea tuplu (valoarea NULL având semnificaţia unei informaţii pe care o ignoram)?

În raport cu interogările prezentate anterior vom utiliza o logică trivalentă în locul celei bivalente:

� O formulă poate avea valorile de adevăr TRUE (T), FALSE (F) sau UNKNOWN (U).

� Rezultatul unei condiţii atomice va avea valoarea de adevăr UNKNOWN dacă cel puţin un termen al comparaţiei are valoarea NULL.

Revenind la exemplul anterior, expresia va produce o relaţie formată din primul tuplu, pentru care valoarea de adevăr a expresiei a fost TRUE.

Tabelele de adevăr în logica trivalentă pentru conectorii not, and şi or sunt:

not

U U

F T

T F

and T U F

T T U F

U U U F

F F F F

or T U F

T T T T

U T U U

F T U F


Este de notat că această logică trivalentă pentru operatorii algebrici prezintă unele dezavantaje.

Exemplu

Să considerăm expresia

( ) ( )Varsta 30 Varsta 30PERSOANA PERSOANA> ≤σ ∪σ

� Logic, această expresie ar trebui să returneze relaţia PERSOANA.

� Pe de altă parte, dacă cele două subexpresii sunt evaluate separat, al treilea tuplu va produce un rezultat necunoscut pentru fiecare subexpresie, deci şi pentru reuniune.

� Numai prin intermediul unei evaluări globale (abordare care nu este practică în cazul expresiilor complexe) putem ajunge la concluzia că un astfel de tuplu trebuie să apară în rezultat.


Nume Varsta Salariu Ionescu 35 500 Popescu 27 600 Popa NULL 500

PERSOANA

Cea mai bună metodă practică de a depăşi astfel de dificultăţi este de a trata valorile NULL din punct de vedere pur sintactic.

În acest sens sunt introduse două noi condiţii atomice de selecţie pentru a verifica dacă o valoare este specificată sau este NULL:

� A is NULL este adevărată pentru tuplul t dacă t[A] = NULL şi falsă în rest;

� A is NOT NULL este adevărată pentru tuplul t dacă t[A] ≠ NULL şi falsă în rest.

Exemplu

- returnează persoanele cu vârsta peste 30 ani.

- returnează persoanele care au sau care pot avea peste 30 ani.

Această abordare este utilizată în versiunile recente de SQL care suportă logica trivalentă.

( )Varsta 30 PERSOANA>σ

( )Varsta 30 Varsta IS NULL PERSOANA> ∨σ


VEDERI

În cele prezentate anterior am văzut că se pot construi reprezentări diferite ale datelor, reprezentări ce vor fi disponibile utilizatorilor prin intermediul relaţiilor derivate.

Tipuri de relaţii într-o bază de date relaţională

� relaţii de bază - conţinutul este autonom şi stocat în baza de date

� relaţii derivate - conţinutul este definit pe baza conţinutului altor relaţii

Există două tipuri principale de relaţii derivate:

� vederi materiale - relaţii derivate stocate în baza de date;

� vederi (relaţii virtuale) – relaţii definite prin intermediul unor funcţii (expresii ale limbajului de interogare) care nu sunt stocate în baza de date, dar pot fi folosite în interogări ca şi cum ar exista fizic.

Vederile materiale oferă un avantaj când numărul cererilor de interogare este mai mare decât operaţiile de actualizare ale relaţiei pe care se bazează vederea.

Deoarece nu se pot specifica tehnici generale de păstrare a consistenţei între relaţiile de bază şi vederile materiale, majoritatea sistemelor comerciale oferă mecanisme numai pentru relaţiile virtuale (vederi).

Vederile sunt definite în sistemele relaţionale ca fiind expresii ale unui limbaj de interogare.

Vederi

� un utilizator interesat numai de o porţiune din baza de date poate evita contactul cu componentele ce nu prezintă interes;

Exemplu

Într-o bază de date cu două relaţii având schemele

ANGAJAT (NrAngajat, Departament)

MANAGER (Departament, NrSupervizor),

un utilizator interesat doar de angajaţi şi de supervizorii lor ar putea fi ajutat de existenţa unei vederi definită astfel:

, (NrAngajat NrSupervizor ANGAJATπ )MANAGER><

Vederi

Algebra relaţionalăbd.ac.tuiasi.ro/Doc/curs/Curs_03.pdfAlgebra relaţională Se bazează pe o...

Documents

Transcript of Algebra relaţionalăbd.ac.tuiasi.ro/Doc/curs/Curs_03.pdfAlgebra relaţională Se bazează pe o...