SISTEME DE INTEROGARE

10.1 Introducere

În capitolul 2 a fost introdus un [aa sistem de manipulare a bazelor de date relationale de date care cuprinde comenzile pentru adaugare, modificare si stergere, iar în capitolul 3 am introdus algebra relationala pentru a exprima selectii, proiectii, uniri de relatii etc.

O cerere ( întrebare, query) este osecventa de operatii care se aplica asupra unor relatii dintr-o baza de date al carui rezultat este o alta relatie. Un sistem de interogare este un sistem formal de exprimare a întrebarilor care constituie stuctura de baza pentru limbajele de interogare.

Sistemul de interogare dat de algebra relationala este un exemplu de sistem formal de exprimare a întrebarilor. Sistemele de interogare formeaza structura de baza pentru limbajele de interogare, adica a limbajelor specializate de programare care sunt folosite în sistemele de baze de date pentru formularea de comenzi. Vom da mai multe limbaje de interogare comerciale pentru baze de date relationale în ultimul capitol. În acest capitol vom examina trei sisteme de interogare .

-Algebra relationala care este un limbaj procedural deoarece orice expresie algebrica (întrebare ) indica explicit secventa de operatii logice aplicate asupra unor relatii care conduce la raspunsul dorit.

- Calculul relational bazat pe tupluri (pe scurt calculul tuplurilor) din contra este un limbaj neprocedural si este un sistem de formalizare a notaţ 727f57h ;iilor si a reprezentarilor de multimi care foloseste variabile ce sunt tupluri .

Calculul relational bazat pe domenii (pe scurt calculul domeniilor) este asemanator calculului relational bazat pe tupluri cu deosebirea ca, variabilele iau valori din domeniile atributelor .

In anul 1972 Codd a aratat ca, calculul tuplurilor si calculul domeniilor si algebra relationala sunt echivalente în raport cu puterea de expresivitate. Gallair si Minker a aratat în / / ca structura calcului relationl pune în evidenta legatura dintre logica predicatelor si bazele de date. In anul 1980 Jacobs / / a extins cercetarile folosind logica în teoria bazelor de date. Înca un mijloc de exprimare a întrebarilor este cel bazat pe modificarea tablourilor. Totusi tablourile nu pot exprima toate întrebarile care pot fi reprezentate în algebra relationala. Aceasta subclasa în care întrebarile care sunt expimate prin tablouri apar în multe aplicatii practice si reprezinta un mijloc eficient de verificare a echivalentei schemelor si restrictiilor. Cu toate ca algebra relationala este baza teoretica a câtorva limbaje de interogare, majoritatea din ele se bazeaza pe calcule sau pe tablouri. Cauza principala ale acestor aplicatii este ca algebra relationala este un sistem procedural în timp ce celelalte sunt neprocedurale. Calculul relational si tablourile exprima numai cum trebuie sa fie rezultatul calculat si nu si în ce mod s-a realizat calculul. Astfel de limbaje de interogare bazate pe sisteme neprocedurale tind sa fie de nivel înalt eliberând utilizatorul de necesitatea definirii modulului de obtinere a rezultatului dorit. Sarcina acestei determinari ramâne în seama procesorului limbajului de interogare al sistemului bazei de date. Vom arata ce expresii din calculul relational pot fi tranzlatate în expresii algebrice. Totusi în nici un caz nu trebuie sa ne asteptam la obtinerea unei expresii algebrice care sa devina un mijloc foarte eficient de calcul a valorilor expresiilor initiale. În urmatorul capitol vom studia procedeele de modificare a expresiilor algebrice care sa usureze evaluarea lor. Se vor introduce pe scurt întrebari conjunctive care formeaza o subclasa a calculului pe domenii. Întrebarile conjunctive sunt similare cu tablourile de interogare si astfel avem un mijloc de verificare a echivalentei expresiilor .

10.2 Echivalenta si completitudine

În diferite sisteme de interogare expresiile sunt considerate ca transformari de baze de date în relatii. Pentru o baza de date d calculul valorii expresiei E(d) are ca rezultat o relatie r .

Definitia 10.1. Doua expresii si sunt echivalente daca (d) (d) pentru orice instansa a bazei de date d si se noteaza

Problema este ca trebuie cunoscuta schema bazei de date pentru a decide echivalenta. De exemplu (rs) si (r) (s) sunt echivalente daca sch(r) ABC si sch(s) ABD, dar nu sunt echivalente daca sch(r) ABCD si sch(s) ABCE. De unde rezulta ca echivalenta expresiilor depinde de schema concreta a bazei de date. Uneori schema bazei de date este neesentiala, deoarece doua expresii sunt echivalente pentru orice schema a bazei de date ca de exemplu : (rs) si (r) (s) sunt echivalente pentru orice schema de baza de date când A sch(r) si A sch(s).

Definitia 10.2. E1 E2 Daca

1) (d)=(d) pentru orice d

2) sch(d,)=sch(d,) .

Aceasta definitie a echivalentei nu este întodeauna tranzitiva :

Exemplul 10.1 Se considera urmatoarele expresii algebrice :

= (r s)

= (r) s

= (r) (s)

În expresia trebuie ca ambele relatii r si s sa aiba aceeasi schema. In expresia lui schema lui s trebuie sa fie AB deci si sunt strict echivalente. Analog se arata ca si sunt echivalente. Dar si nu sunt echivalente deoarece în aceasta baza de date schemele lui r si s sunt ABC. Vezi exemplul 10.1 .

De aceea echivalenta va fi examinata întotdeauna în raport cu o schema fixa a bazei de date. O data ce am definit alte sisteme de interogare vom discuta echivalenta expresiilor în sisteme diferite. Unul din parametrii prin care vor fi comparate schemele este puterea de expresie .

Definitia 10.3. Sistemul de interogare QS1 este mai expresiv decât sistemul de interogare QS2 daca pentru orice expresie din QS2 si orice schema a bazei de date compatibila cu exista o expresie din QS1 astfel ca . Sistemele QS1 si QS2 sunt la fel de expresive daca fiecare din ele este mai expresiv decît celalalt.

Notam ca poate depinde de o schema de baza de date particulara.

Definitia 10.4. Un sistem de interogare este complet daca este la fel de expresiv cu algebra relationala.

Sistemele de interogare bazate pe calculul relational al tuplurilor si calculul relational al domeniilor sunt complete. În timp ce sistemele bazate pe tablouri de interogare si întrebari conjunctive nu sunt complete. În capitolul 3 am definit algebra relationala B pentru un univers de atribute U cu domeniile corespunzatoare ca fiind :

o multime de relatii ,. . ., ;

o multime de comparatori binari Q

o multime de operatori compusa din operatorii booleeni de reuniune, intersectie si diferenta si operatorii de selectie, proiectie, unire naturala, redefinire, împartire, q-unire si complement activ.

Tot în capitolul 3 (teorema 3) se arata ca pentru orice expresie E din algebra relationala exista o expresie E' echivalenta care utilizeaza un singur atribut, un singur tuplu, relatii constante, redefiniri, selectii cu un singur comparator, proiectie, unire naturala, reuniune, diferenta si complement. Subalgebra algebrei relationale care utilizeaza numai operatorii mentionati este la fel de expresiva ca si algebra relationala si prin urmare completa.

De aceea pentru a demonstra ca un sistem de interogare este la fel de expresiv ca algebra relationala este suficient sa examinam expresiile pe aceasta subalgebra .

10.3 Calculul tuplurilor

Calculul tuplurilor constituie pentru utilizator un sistem obisnuit de notatii similar cu cel al expresiilor utilizate în capitolele 2 si 3 pentru definirea unor operatori din algebra relationala. În timp ce, în algebra relationala operanzii sunt relatii, în calculul relational pe tupluri operanzii expresiilor componente sunt variabile tuplu.

Expresiile de calcul a tuplurilor vor avea forma urmatoare:

unde f este un predicat de variabila t care este o variabila tuplu.

Aceasta expresie reprezinta o relatie de schema R compusa din toate tuplurile t(R) pentru care predicatul f(t) este adevarat.O intrebare in acest limbaj este o o definitie a unei multimi de tupluri printr-o formula de forma .

Exemplul 10.2 Consideram de exemplu o baza de date compusa din urmatoarele relatii : rp(reper), nc(necesar), st(stocuri).

rp ( CODR# CA D-Reper ) nc ( CODR# TIP NECESAR )

100 0 motor 100 Cielo 1

1001 100 pompa 100 Logan 1

1002 100 filtru-aer 1001 Cielo 1

1003 100 bujii 1001 Logan 4

1004 100 piston 1002 Cielo 1

500 0 bord 1002 Logan 1

5001 500 turometru 1003 Cielo 4

5002 500 surub 1004 Logan 4

5003 500 termostat 500 Cielo 1

500 Logan 1

5001 Logan 1

5002 Cielo 30

5002 Logan 30

5003 Logan 1

st ( CODR# MAGAZIN CANTITATE )

100 acr 50

100 service 10

1001 traian 3

1002 acr 20

1003 service 40

500 traian 4

5001 service 12

5002 acr 800

5002 service 900

5003 traian 10

Figura 1

Pentru exemplul 10.2 avem întrebarea : Care sunt reperele ce compun ansamblul cu numarul 100 ? Care are urmatoarea forma în calculul reltional pe tupluri:

iar în algebra relationala

p_{COD#, D-Reper} s_CA=100 (rp)) _.

Câte bujii se folosesc în Logan ?

10.4 Formule de calcul bazate pe tupluri

O multime de formule de calcul pe tupluri va fi definita în raport cu :

1) O multime universala de atribute U cu dom(A) dat pentru orice atribut A U .

2) O multime de comparatori binari pe domenii .

3) O multime de nume de relatii si de scheme ,. . ., toate submultimi ale lui U .

Vom da mai întâi reguli de generare a formulelor si semnificatia fiecarei expresii în concordanta cu multimea de restrictii .Elementele de baza ale constructiei formulelor sunt atomii care sunt de 3 tipuri :

Pentru orice nume de relatie r si orice variabila tuplu x, r(x) este un atom prin care întelegem ca x r ;

Fie x si y variabile tuplu, q Q un comparator, A si B atribute care sunt q-comparabile atunci x(A)qx(B) este un atom ;

Fie x o variabila tuplu, q Q un comparator, A si B doua atribute din U care sunt q_comparabile. Daca c este o constanta din dom(A) atunci cqx(B) este un atom, daca c este o constanta din dom(B) atunci x(B)qc este un atom .

Exemplul 10.3 Pentru baza de date din figura 1 se considera de exemplu urmatorii atomi rp(x), x(COD#)=y(COD#) si x(cantitate)

Pentru a construi recursiv formulele formate din atomi vom folosi conectorii :

(not ), ( and ), ( or ), ( ) si ("

conform urmatoarelor reguli :

Orice atom este o formula ;

2) Daca f este o formula atunci f este o formula, f este adevarata daca f este

falsa) si falsa daca f este adevarata;

3) Daca f si g sunt formule atunci f g si f g sunt formule, f g este adevarata

când f si g sunt adevarate si f g este adevarata când fie f fie g este adevarata ;

Daca x este o variabila tuplu, f este o formula care contine x si R este o submultime a lui U, atunci x(R)f este o formula. Aceasta formula este adevarata daca exista un tuplu t pe R care face pe f adevarata când se înlocuie x cu t .

Daca x este o variabila tuplu, f este o formula care contine x si R este o submultime a lui U, atunci "x(R)f este o formula. Aceasta formula este adevarata daca înlocuind pe x cu orice tuplu t de schema R f devine adevarata .

Daca f este o formula atunci (f) este o formula. Parantezele sunt necesare pentru a schimba ordinea de evaluare a conectorilor .

O întrebare în acest limbaj este o definitie a unei multimi de tupluri determinata de o formula de forma , unde f(t) este un predicat si R o schema de relatie.

Se presupune ca ( ) si (") sunt de rangul cel mai mare si egali comparabili ( de aceeasi precedenta ) si de precedenta descrescatoare pentru , ,

10.5 Tipuri si ocurente libere si dependente

Mai înainte de a defini formal interpretarea unei formule va trebui precizat ce înseamna " formula f care contine pe x " si " când t înlocuie pe x ". Este necesar sa excludem anumite formule fara sens ca de exemplu :

ans (x) x (MAGAZIN)='acr '.

Problema care se pune, este de a preciza tipul variabilei x. Din ans(x) rezulta ca x este o variabila tuplu de schema (COD#, TIP, NECESAR) în timp ce x(MAGAZIN) implica o schema ne definita .

Tipul unei variabile tuplu x este dat de schema sa. Multimea de atribute pe care variabila tuplu le utilizeaza în formula f se numeste multime de mentionare a lui x si se noteza men(x,f)

Întotdeauna avem incluziunea type(x,f) men(x,f)

Notiunea de ocurenta libera si dependenta este analoaga variabilelor globale si locale dintr-un limbaj de programare .

Exemplul 10.4. Se consideram programul schitat mai jos. Orice mentionare a lui X, Y sau Z în corpul programului MAIN se refera la variabilele din instructiunea 1 de declarare. Orice mentionare a lui X sau Y în corpul procedurii SUB1 se refera deasemenea la variabilele din instructiunea 1 de declarare, în timp ce mentionarea lui X si W se refera la variabilele din instructiunea 2 de declarare. Variabilele Y si Z sunt globale în SUB1. Ele au rezervate locatii de memorie care sunt nevazute de procedurile exterioare lui SUB1, ele pot fi vazute de procedurile interioare lui SUB1. In corpul procedurii SUB12 X,Y si W sunt globale dar Z este locala. Se observa ca în procedura SUB12 orice ocurenta a lui Z din declararea 3 poate fi schimbata fara a schimba semnificatia programului, deoarece aceste ocurente ale lui W sunt globale în SUB12. Se observa ca ocurentele variabilelor pot fi locale sau globale. O ocurenta a lui Z în corpul lui SUB12 este locala în timp ce o ocurenta sa în SUB1 este globala.

PROC MAIN

1) decl X, Y, Z ;

[ corpul lui MAIN ]

. ..

PROC SUB1

2) decl X, W ;

[ corpul SUB1 ]

. . .

PROC SUB12

3) decl Z;

[ corpul SUB12 ]

. . .

END ;

END;

END [ MAIN ]

Într-o formula ocurentele libere si dependente corespund la variabile globale si locale ale variabilelor dintr-un program. Cuantificatorii " si sunt de asemenea utilizati la declararea tipului variabilelor în formule (mai exact ca declaratiile din programe). Vom defini notiunile de ocurente libere si dependente recursiv înainte de a defini tipul variabilei x în formula f (type(x,f)) si multimea de mentionare a lui x în formula f (men(x,f)). Type(x,f) si men(x,f) sunt definite numai când x este ocurenta libera în f. Vom utiliza conceptele de ocurenta libera ocurenta dependenta, type si men pentru construirea de formule legale (permise ) utilizând diferiti conectori.

Vom considera mai întâi cazul când f este o formula atomica.

a1. Daca f=r(x), atunci x este o variabila libera în f, si type(x,f)=men(x,f)=R, unde

R este schema relatiei r.

a2. Daca f=x(A)qy(B) atunci x si y sunt libere, type(x,f) si type(y,f) sunt nedefinite si

men(x,f)=A si men(y,f)=B.

a3. Daca f= x(A)qc sau f=cqx(A) atunci x este libera în f, type(x,f) este nedefinit si

men(x,f)=A.

Consideram cazul când f este construita din formule mai mici. Presupunem ca formulele g si h sunt permise .

F1. Orice atom este o formula.

f2. Daca f= g atunci f este permisa si toate ocurentele variabilelor din f sunt libere

sau dependente ca si cele ale lui g. Pentru orice variabila libera x,

type(x,f)=type(x,g) si men(x,f)=men(x,g) .

f3. Daca f =g h sau f=g h, atunci toate ocurentele variabilelor din f sunt libere sau

dependente ca cele carora le corespund în g si h. Pentru orice variabila libera x din

f pentru care type(x,h) si type(x,g) sunt definite atunci ele trebuie sa coincida

si sa fie egale cu type(x,f). Daca tipul a fost definit numai pentru o subformula sa

zicem g si variabila x este libera în h, atunci type(x,g) men(x,h), trebuie sa aiba

loc pentru ca f sa fie dependenta. În ambele cazuri type(x,f)=type(x,g). Daca tipul

lui x este nedefinit pentru ambele subformule atunci type(x,f) este nedefinit. În

toate cazurile men(x,f)=men(x,g) men(x,h).

f4. Daca f= x(R)g atunci x trebuie sa fie ocurenta libera în g si pentru ca f sa fie

corecta, în plus type(x,g) trebuie sa fie R daca el este definit. Toate ocurentele lui

x în f sunt dependente type(x,f) men(x,f) nu sunt definite deoarece x nu este

ocurenta libera în f orice ocurenta a unei variabile y x este libera sau dependenta

în f cum este în g, type(y,f)=type(y,g) si men(y,f)=men(y,g).

f5. Daca f="(g) atunci proprietatile de dependenta si libertate, type si men sunt aceleasi ca în f4.

f6. Daca f=(g) atunci proprietatile de dependenta si libertate, type si men sunt

aceleasi ca în g.

Intr-o formula ca x(R)g sau "x(R)g este util sa definim ce ocurenta a variabilei x în g este dependenta de cuantificator. O ocurenta a lui x în x(R)g este dependenta de x(R) daca ea este independenta în g. Daca o ocurenta a lui x este dependenta atunci ea trebuie sa fie dependenta de un cuantificator continut în g.

În urmatoarele exemple se foloseste baza de date din figura 10.1. Punem

Exemplul 10.5. Examinam formula f :

"x()( st(x) x(CANTITATE) <100 )

Toate ocurentele lui x sunt dependente de x(). Aceasta formula este adevarata pentru orice tuplu t din relatia st, t(CANT) 100. Pe scurt vom folosi scrierea "x(R) rf în locul "x(R)( r(x) f ). Analog în locul x(R)( r(x) f ) se foloseste x(R) r f .

Exemplul 10.6. Fie f formula :

"x( st( y( st(x(MAGAZIN) y(MAGAZIN) x(COD)=z(COD)))

Toate ocurentele lui x si y sunt dependente. Ocurentele lui x sunt dependente de "x(), iar ale lui y sunt dependente de x( Ocurentele variabilei z sunt libere, type(z,f) este nedefinit iar men(z,f) COD .

Exemplul 10.7. Fie formula :

x( st(x(MAGAZIN) ACR "y( ans(x(COD) y(COD) y(TIP) Cielo))

Toate ocurentele lui x si y sunt dependente si se poate descompune usor în doua subformule.

Exemplul 10.8. Fie formula :

x()(ans(x) x(MAGAZIN) y(MAGAZIN))

Se observa ca pentru subformulele g ans(y) si h x(MAGAZIN) y(MAGAZIN), type(x,g) în timp ce men(x,h) MAGAZIN prin urmare g h nu este permisa .

Pot fi utilizate si notatii prescurtate ca x(S) y(S) unde S este multimea de atribute A₁,.,A_m în locul lui x(A₁) y(A₁) x(A₂) y(A₂) x(A_m) y(A_m) .

10.6 Expresii bazate pe calculul tuplurilor

Sistemul de interogare bazat pe calculul tuplurilor, notat pe scurt TC este dat de sextetul

(U,D, dom,R,d,Q unde

U reprezinta un univers de atribute,

D o multime de domenii,

dom o functie definita pe U cu valori în D,

R o multime de scheme de relatii din U,

d o baza de date de schema R iar

Q o multime de comparatori care includ egalitatea si inegalitatea pentru fiecare

domeniu din D.

O expresie de calculul tuplurilor pe TC are forma

unde f este o formula permisa în raport cu TC.

Prin dom(R) vom nota multimea tuturor tuplurilor de schema R. Pentru definirea valorilor expresiilor de calcul a tuplurilor va trebui sa înlocuim variabilele tupluri prin tupluri.

Definitia 10.6. Fie f(x) o formula permisa. Fie R type(x,f), daca type(x,f) este definit, în caz contrar R este orice submultime a lui U care contine men(x,f). Atunci rezultatul înlocuirii lui x cu t în f notat f(t/x) este formula care se obtine prin modificarea fiecarui atom ce contine ocurenta libera x din f dupa urmatoarele reguli

a1. Daca x este libera în r(x) atunci r(x) se înlocuie cu true daca t r si false în caz

contrar .

a2. Daca x în x(A)qx(B) este libera în f atunci x(A) este înlocuit cu constanta

c dom(A), unde t(A) c în cazul când x y. Daca x y si atomul are forma

x(A)qx(B) se înlocuie cu atomul de adevar daca t(A)qt(B) este îndeplinita în caz

contrar cu fals.

a3. Daca x în x(A) qc este liber se în locuie atomul cu true daca t(A)qc în caz contrar

se înlocuie atomul cu false. Analog pentru cqx(A).

Observatie Formula se extinde usor ca sa cuprinda si constantele booleene true si false ca atomi.

Exemplul 10.9. Fie formula f(y)= st(y) y(COD)=100 y(CANT) 10 si fie tuplul t=<100,50,Traian> atunci f(t/x)=false.

Definitia 10.7. Fie formula f fara variabile tuplu libere dar în care true si false pot sa apara ca atomi. Interpretarea lui f notata cu I(f) se defineste recursiv în modul urmator:

f1. Daca f este true atunci I(f) este true. Daca f este false atunci I(f) este false.

f2. Daca f= g atunci g trebuie sa nu contina variabile libere I(f) = false daca I(g)=true

în caz contrar I(f)=true.

f3. Daca f este h g sau h g atunci nici h si nici g sa nu aiba variabile libere. Daca

f este g h, I(h)=true si I(g)=true atunci I(f)=true în caz contrar I(f)=false. Daca

f= h g si I(h)=I(g)=false atunci I(f)=false în caz conrar I(f) =true.

f4. Daca f= x(R)g atunci x trebuie sa fie numai o variabila libera în g. I(f)=true

daca exista cel putin un tuplu în dom(R) astfel ca I(g(t/x))=true în caz contrar

I(f)=false.

f5. Daca f="x(R)g atunci x trebuie sa fie numai o variabila libera în g. I(f)=true

daca pentru orice tuplu t din dom(R) I(g(t/x))=true în caz contrar I(f)=false.

f6. Daca f=(g) atunci I(f)=I(g).

Exemplul 10.10 Fie formula f : x(R2)(st(x) x(MAGAZIN)='acr' "y(R2)( st(y)) y(COD)=x(COD) "y(CANT) x(CANT).

Intuitiv I(f) este true, daca în acr exista o cantitate dintr-un reper mai mare decât în celelalte magazine.

Consideram baza de date din figura 1 si calculam I(f) pentru aceasta. Daca f are forma x(R2)g(x), atunci trebuie sa cunoastem numai daca I(g(t/x))=true pentru un tuplu oarecare t dom(R2

În loc sa verificam toate tuplurile, se observa ca g(x) are forma st(x) g (x), astfel trebuie sa verificam numai acele tupluri din dom(R2) care apar în relatia st (care poate fi prescurtata x(R2) st g (x). Formulele astfel studiate permit sa observam ca e necesar sa cautam numai acele tupluri din st, valoarea carora în coloana MAGAZIN este ACR. La început cautam tuplul T=(400, ACR, 10). Obtinem : g(t/x)=(true true "y(R2) st(y) y(COD)=400 y(CANT) 10) care se reduce la: "y(R2)( st(y) y(COD)=400 y(CANT) Aceasta formula are forma "y(R2)h(y), astfel ca este necesar sa verificam când I(h(u/y))=true pentru orice tuplu u dom(R2). În acest caz, vom putea limita cautarea. Deoarece h(y) are forma st(y) h (y) va trebui sa consideram numai tuplurile din st. Alegând t=( 400, iul, 30), obtinem : h(u/y)=( true true false). Evident ca I(h(u/g))=falsa, astfel ca I(g(x))=false.

Ne întoarcem la alegerea lui t=(100, acr, 160).

g(t/x)=(true true "y(R2)( st(y) y(COD)=100 y(CANT)

Aceasta formula are forma "y(R2)h(y), astfel ca este necesar sa verificam daca I(h(u/y))=true pentru orice tuplu u dom(R2). Ca mai sus, va trebui sa testam numai tuplurile din relatie st. Orice alegere pentru u face I(h(u/y))=true. De exemplu, daca u= (300, service, 30) avem : h(u/y)=( true false true), astfel ca I(h(u/y))=true. Daca u= (320, Traian, 20), atunci h(u/y)=( true true true). Deci, I(h(u/y))=true. Prin urmare, I(g(t/x))=true si rezulta ca I(f)=true. Se observa ca I(f)=false daca y(CANT) x(CANT) este înlocuita prin y(CANT) < x(CANT). Acum putem sa definim expresia de calcul a tuplurilor.

Definitia 10.8. Fie E= o expresie de calcul a tuplurilor în raport cu calculul tuplurilor TC=(U, D, dom, R, d, q). Valoarea expresiei E pentru starea curenta a bazei de date d, notata E(d), este relatia r de schema R care contine orice tuplu t din dom(R) astfel ca I(f(t/x))=true.

10.7. Reducerea algebrei relationale cu complement la calculul relational pe tupluri

În aceasta sectiune vom arata ca, calculul relational pe tupluri este la fel de expresiv ca algebra relationala. Vom da o interpretare alternativa pentru calculul tuplurilor. În raport cu acesta interpretare, calculul tuplurilor si algebra relationala sunt la fel de expresive.

Teorema 10.1. Fie algebra relationala cu complement =(U, D, dom, R, d, Q, O) si calculul tuplurilor TC=(U, D, dom, R, d, Q). Pentru orice expresie algebrica E exista o expresie F TC astfel ncât E(d)=F(d) pentru orice stare a lui d.

Demonstratie. Este sificient sa presupunem ca E este din subalgebra , unde O este înlocuita cu O⁰ care contine operatorii de selectie cu un singur comparator, proiectie, unire naturala, reuniune, diferenta, complement si unde sunt permise numai relatii cu un singur atribut si un singur tuplu. Demonstratia se face prin inductie dupa numarul operatorilor din expresia E.

Cazul inductiv. Se presupune ca teorema este adevarata pentru orice formula care are mai putini termeni decât E.

Daca E este o relatie constanta formata dintr-un singur atribut si un singur tuplu, adica E=<a:A>, atunci F= . Daca r este o relatie de schema R, atunci r are forma 1.

Cazul 1. (Redefinire). Fie E=d_{R-A1...Am B1....Bm}(E₁), unde E₁ are mai putin de k operatori, atunci exista o conversie F₁ din TC echivalenta cu E₁, adica F₁= . Atunci F= , unde, S=( R-A₁....A_m B₁...B_m) si g(x,y) = _R-A1...Amy(C) = x(C) y(B_i)=x(A_i). Din constructie resulta F TC.Cazul 2.(Selectie). Fie E=s_Aqa(E₁) sau E=s_AqB(E₁). Consideram expresia F₁= din TC echivalenta cu E₁. Atunci F= sau F=

Cazul 3. (Proiectie). Fie E=p_XE₁, atunci F=

Cazul 4. (Reuniune). Fie E=E₁ E₂. În baza inductiei E₁ si E₂ , atunci F=

Cazul 5. (Unire). Fie E = E₁ E₂ si R₁=TR, R₂=RS, E₁= TC, E₂= TC.

Atunci F=

Cazul 6. (Diferenta). Fie o expresie din algebra relationala E=E₁-E₂, unde E₁ este echivalenta cu E₁= si E₂= , atunci E este echivalenta cu expresia din TC : F=

Cazul 7. (Complement). Fie E=Ē₁ si expresia echivalenta din TC, atunci : E F=

Exemplul 10.11. E=p_NUMEF s_COMB=carb(furnizor))

furnizor

s_COMB=carb(furnizor)

p_numef

10.7 Interpretarea restrânsa a formulelor de calcul a tuplurilor

Interpretarea data pentru formulele de calcul a tuplurilor prezinta în practica câteva greutati când calculul tuplurilor este considerat ca baza pentru un sistem de interogare. Expresiile de calcul poate sa defineasca relatii infinite. În al doilea caz nu este evident cum se interpreteaza o formula arbitrara de forma x(R) f(x) si "x(R) f(x).

Interpretarea generala ar necesitacercetarea întregului dom(R) care poate sa fie infinit. Vom prezenta o interpretare alternativa pentru formulele când tuplurile nu sunt compuse din valorile domeniilor care apar în formulele sau relatiile ce sunt mentionate !n formula. Interpretarea initiala va fi numita generalizata în timp ce interpretarea alternativa va fi numita restrânsa.

Definitia 10.9 Fie f o formula de calcul al tuplurilor si A un atribut. Domeniul activ extins al lui A relativ la f , notat edom(A,f) este multimea tuturor valorilor din dom(R) care apar în relatiile continute în f sau ca, constante. Nu se exclude posibilitatea ca edom(A,f)= . Aceasta se întâmpla când atributele A nu sunt în f. Pentru o multime de atribute R ,vom numi edom(R,f) multimea tuturor tuplurilor t astfel ca t(A) edom(A,t), pentru orice A A.

Observatie. Daca g este o subformula a formulei de calcul a tuplurilor f, atunci edom(A,g) edom(A,f), pentru orice atribut A.

Definitia 10.10 Fie f o formula fara variabile libere. Interpretarea i(f) se defineste recursiv astfel :

i1) Daca f este adevarata, atunci i(f)=true ; daca f=false, atunci i(f)=false ;

i2) Daca f= g si în g nu sunt variabile libere, i(f)=true daca i(g)=false si i(f)=false daca i(g)=true ;

i3) Daca f=g h sau f=g h si în g si h nu exista variabile libere. i(f)=true daca i(g)= i(h)=true, în caz contrar i(f)=false. Daca f=g h, atunci i(f)=false ; daca i(f)= i(f)=false si i(f)=true în caz contrar.

i4) Daca f= x(R)g, x este ocurenta libera în g. Punem i(f)=true daca în dom(R)exista cel putin un tuplu t edom(R,g), astfel ca i(g(t/x))=true, în caz contrar i(f)=false.

i5) Daca f="x(R)g. i(f)=true daca pentru orice t edom(R,g), i(g(t/x))=true. În caz contrar, i(f)=false.

Interpretarea restrânsa a expresiei E= , este o relatie de schema R care consta din tuplurile t edom(R,f) astfel ca i(f(t/x))=true.

10.8. Formule sigure

Se defineste clasa formulelor sigure. Aceasta are urmatoarea proprietate importanta.

Multimea tuplurilor obtinute :

- prin interpretare generala a

- prin acea ca nu se considera decât tupluri din edom(R)

Definitia 10.11 O expresie este sigura:

- daca t satisface f(t), atunci t edom(R),

- pentru orice subformula a lui f de tipul ( t(R)g(t)), daca t_i satisface g, atunci t edom(R)

- pentru orice subformula a lui f de tipul ("t(R)g(t)), daca t_i edom(R), atunci g(t_i)=true.

Exercitiu. . Pentru baza de date din figura 1 este sigura(safe).

Lema 10.1. Pentru orice expresie de calcul sigura, evaluarile restrânse si generalizate sunt echivalente.

Teorema 10.2. Pentru orice expresie de calcul bazata pe tupluri exista o expresie sigura bazata pe calculul tuplurilor F e echivalenta cu E în raport cu interpretarea restrânsa.

Teorema 10.3. Pentru orice expresie E din algebra relationala exista o expresie sigura F din calculul relational pe tupluri echivalenta.

Demonstratie. Se face prin inductie asupra structurii expresiei E.

Caz de baza. E este data de relatia r sau de o relatie constanta. Daca E=r, atunci F= . Daca E este o relatie constanta t₁,t₂,..,t_n de schema R= cu t_i(A_j)=a_ij, atunci F= .Caz inductiv. Se presupune teorema adevarata pentru toate formulele care au operatori mai putin decât E (ipoteza inductiva).

Caz1. Fie E=E₁ E₂. Prin ipoteza inductiei :

E₁

E₂

Atunci E=E₁ E₂=E

Cazul 2. E=E₁-E₂ E

10.9 Calculul relational pe domenii

Calculul relational pe domenii este similar cu calculul relational pe tupluri cu deosebirea ca, o variabila nu reprezinta un tuplu întreg ci numai valorile dintr-un singur domeniu. De exemplu, întrebarea care determina toate reperele din produsul Cielo are forma:

Calculul relational pe domenii, notat cu CD, este dat de U,D,dom,R,d,q . Formulele de calcul relational pe domenii se construiesc din variabile domeniu utilizând relatii comparatori si conectori: " . O expresie din calculul relational pe domenii are urmatoarea forma , unde A₁,A₂,...A_n sunt atribute si f este o formula de calcul pe domenii.

Blocurile de baza din care se construiesc formulele sunt atomii urmatori:

a1) Daca r este o relatie în baza de date d de schema A₁,A₂,...A_n, atunci r(a₁,a₂,...a_n) este un atom, unde a_i sunt variabile doemniu sau constante din domeniul dom(A_i). Tehnic, ar trebui scrisa sub forma: r(A₁:x₁,A₂:x₂,....A_n:x_n);

a2) Daca x si x sunt variabile domeniu si q un comparator pentru doemniile lui X si Y si c o constanta arbitrara din dom (A_i), atunci xqy, xqc, cqx sunt atomi.

a3) Constantele booleene True si False sunt atomi. Atomii pot fi combinati recursive, obtinându-se astfel formulele:

f1) Orice atom este o formula.

f2) Daca f este o formula, atunci f este o formula.

f3) Daca f si g sunt formule , atunci f g si f g sunt formule .

f4) Daca f este o formula, A este un atribut din universul U si x este o variabila

domeniu, atunci:

(f5) x(A)f(x) si "x(A)f(x) si (f) sunt deasemenea formule.

Tipul unei variabile x într-o formula f este dat fie de un domeniu din D, fie este nedefinit. În loc sa precizam un nume de atribut pentru variabile, precizam un nume de domeniu. Analog cu calculul relational pe tupluri, se definesc variabilele libere si restrânse. Cuantificatorii sunt utilizati chiar si la descrierea tipului unei variabile într-o formula ( ca si declaratiile într-un program). Se defineste notiunea de formula fiabila, asemanator cu cea din CRT. Notiunea de domeniu efectiv (activ extins) este identic cu cel din CRT.

. Ca si în cazul CRT, în CRD legalitatea reprezinta o cerinta de compatibilitate a tipului variabilelor în subformule.

Exemplul 1.Fie relatiile r(ABC) si s(BD). Pentru ca formula f= x(E)"y(A)(r(y,z,x) s(x,x) y<z)

sa fie legala, trebuie sa fie îndeplinita egalitatea: dom(C)=dom(D)=dom(E) si atributele A si B sa fie <-comparabile.

În aceste conditii type(z,t)=dom(B) si daca y este o subformula (r(y,z,x) s(x,x) y<z) atunci type(x,g)=dom(C), type(y,f)=dom(A). când se utilizeaza variabile precedate de cuantificatori este mai bine sa se foloseasca domeniul si nu atributul de notare a tipului. Înlocuirea unei variabile libere x în formula f în CRD cu constanta c este analoaga cu cea din CRT si se noteaza cu f(c/x). se presupune ca c type(x,f). Dupa ce s-a înlocuit variabila libera x cu constanta c, atomii compusi în întregime din constante se schimba cu constantele booleene True si False, în concordanta cu regulile cuprinse în formule.

Exemplul 2. Consideram formula:

f=nrc(x, Cielo ,y) "w(CANT)( st(x, ACR , w) w>y x=400).

Variabila x este libera în f si f(100/y) este formula:

g= nrc(100, Cielo ,y) "w(CANT)( st(x, ACR ,w) w>y False).

Variabila y este libera în g. Calculati g(86/y). Interpretarea nelimitata a formulei de calcul pe domenii cu ocurente nelibere ale variabilelor este notata I(f). Definitia este aceiasi ca în formulele de calcul a tuplurilor. Pentru o formula f= x(A)g(x), I(f)=true daca si numai daca exista c dom (A) astfel ca I(g(c/x))=true. Pentru o formula f=$x(A)g(x), I(f)=true daca si numai daca pentru orice c dom(A), I(g(c/x))=true.

Exemplul 3. Fie formula h="w(CANT)( st(400, acr , w) w>86). Pentru a calcula I(h) trebuie sa cunoastem I(h (c/x)) pentru orice c dom(CANT), unde h (w) este formula st(400, acr w>86). Interpretarea în h (w) este true pentru orice alegere a lui w cu exceptia lui 106 si este true pentru orice c dom(CANT). Prin urmare, I(h)=true.

O expresie de calcul pe domenii are forma

unde f este o formula de calcul pe domenii legala cu x₁,x₂,..,x_n variabile libere, A₁,A₂,..,A_n atribute distincte în U si type(x_i,f)=dom(A_i), 1 i ­n.

Valoarea unei expresii în raport­ cu evaluarea extinsa este relatia de schema (A₁,A₂,...,A_n) care contine toate tuplurile < c₁,c₂,..,c_n> astfel ca c_i dom(A_i) pentru 1 i ­n si I(c₁/x₁, c₂/x₂,..,c_n/x_n)=true. Ca mai înainte, valoarea unei expresii E pentru baza de date d este notata cu E(d).

Exemplul 4. Utilizând formula din exemplul 1, calculati evaluarea extinsa a lui E(d) pentru starea bazei de date d data la începutul capitolului. Ca si în CRT, putem defini analog interpretarea limitata pentru formule si evaluarea limitata pentru expresii. Domeniul activ extins al unui atribut A într-o formula CRD, notata edom(A,f) este multimea tuturor elementelor din dom(A), care sunt constante în f sau în relatii mentionate în f. Interpretarea I(f) limitata difera de interpretarea extinsa numai pentru formulele cu cuantificatori.

Daca f= x(A)g(x), atunci I(f)=true c dom(A,g) astfel ca I(g(c/x))=true. Similar, daca f="x(A)g(x), atunci I(f)=true " c dom(A,g) astfel ca I(g(c/x))=true.

Sa calculam evaluarea limitata a unei expresii

x_i ia valori din edom(A_i,f), 1 i ­n si interpretarea limitata este utilizata în f.

Vom defini clasa expresiilor fiabile (safe) din CRD.

O expresie este fiabila daca au loc urmatoarele trei conditii:

s1) Daca pentru constantele c₁,c₂,..,c_n, I(c₁/x₁, c₂/x₂,...,c_n/x_n)=true, atunci c_i edom(A_i,f) pentru 1 i ­n.

s2) Pentru orice subformula a lui f de forma y(A)g(y), I(g(c/y))=true implica c dom(A,g).

s3) Pentru fiecare subformula a lui f de forma "y(A)g(y) c edom(A_i,g) implica I(g(c/y))=true.

Lema 1. Pentru orice expresie fiabila E din CRD, evaluarile limitate si melimitate coincid.

Teorema 1 Pentru orice expresie E din CRD exista o expresie fiabila F în CRD care este echivalenta cu E în raport cu evaluarea limitata.

Aceste rezultate sunt analoage cu cele din calculul tuplurilor. Orice expresie din CRT de forma se translateaza într-o expresie din CRD, unde x_i sunt variabile domeniu.

Teorema 2. Fie E o expresie din CRT si F expresia din CRD obtinuta din E prin translatare. Atunci :

E F în raport cu evaluarea nelimitata;

E F în raport cu interpretarea limitata

Daca E este fiabila, atunci F este fiabila.

Demonstratia are la baza urmatoarele observatii: Daca A este un atribut oarecare si g este o subformula a lui E si g subformula corespunzatoare f a lui F, atunci edom(A,g)=edom(A,g ). Egalitatea rezulta din faptul ca g si g contin acelasi relatii si constante. Orice parte y_i(A_i) din F este o parte a formulei y₁(A₁) y₂(A₂),..., y_k(A_k)/g (y₁,y₂,...,y_k) care este o translatare a formulei y(S)g(y) din E, unde S= A₁,A₂,..,A_k. Fie c_i dom(A_i), 1 i ­n si presupunem I(g(c₁/y₁, c₂/y₂,...,c_k/y_k)=true. Din corespondenta lui g si g resulta I(g(t/y))=true, unde t=( c₁,c₂,..,c_k).