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).