SISTEME DE INTEROGARE

1 Introducere

In 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 in capitolul 3 am introdus algebra relationala pentru a exprima selectii, proiectii, uniri de relatii etc.

O cerere ( intrebare, 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 intrebarilor 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 intrebarilor. Sistemele de interogare formeaza structura de baza pentru limbajele de interogare, adica a limbajelor specializate de programare care sunt folosite in sistemele de baze de date pentru formularea de comenzi. Vom da mai multe limbaje de interogare comerciale pentru baze de date relationale in ultimul capitol. In acest capitol vom examina trei sisteme de interogare .

-Algebra relationala care este un limbaj procedural deoarece orice expresie algebrica (intrebare ) 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 notatiilor 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 in raport cu puterea de expresivitate. Gallair si Minker a aratat in / / ca structura calcului relationl pune in evidenta legatura dintre logica predicatelor si bazele de date. In anul 1980 Jacobs / / a extins cercetarile folosind logica in teoria bazelor de date. Inca un mijloc de exprimare a intrebarilor este cel bazat pe modificarea tablourilor. Totusi tablourile nu pot exprima toate intrebarile care pot fi reprezentate in algebra relationala. Aceasta subclasa in care intrebarile care sunt expimate prin tablouri apar in multe aplicatii practice si reprezinta un mijloc eficient de verificare a echivalentei schemelor si restrictiilor. Cu toate ca algebra relationala este baza teoretica a catorva 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 in timp ce celelalte sunt neprocedurale. Calculul relational si tablourile exprima numai cum trebuie sa fie rezultatul calculat si nu si in ce mod s-a realizat calculul. Astfel de limbaje de interogare bazate pe sisteme neprocedurale tind sa fie de nivel inalt eliberand utilizatorul de necesitatea definirii modulului de obtinere a rezultatului dorit. Sarcina acestei determinari ramane in seama procesorului limbajului de interogare al sistemului bazei de date. Vom arata ce expresii din calculul relational pot fi tranzlatate in expresii algebrice. Totusi in 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. In urmatorul capitol vom studia procedeele de modificare a expresiilor algebrice care sa usureze evaluarea lor. Se vor introduce pe scurt intrebari conjunctive care formeaza o subclasa a calculului pe domenii. Intrebarile conjunctive sunt similare cu tablourile de interogare si astfel avem un mijloc de verificare a echivalentei expresiilor .

2 Echivalenta si completitudine

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

Definitia 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 cand AIsch(r) si AIsch(s).

Definitia 2. E1sE2 Daca

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

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

Aceasta definitie a echivalentei nu este intodeauna tranzitiva :

Exemplul 1 Se considera urmatoarele expresii algebrice :

= (r s)

= (r) s

= (r) (s)

In 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 in aceasta baza de date schemele lui r si s sunt ABC. Vezi exemplul 1 .

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

Definitia 3. Sistemul de interogare QS1 este mai expresiv decat 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 s . Sistemele QS1 si QS2 sunt la fel de expresive daca fiecare din ele este mai expresiv decit celalalt.

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

Definitia 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. In timp ce sistemele bazate pe tablouri de interogare si intrebari conjunctive nu sunt complete. In 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, impartire, q-unire si complement activ.

Tot in 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 .

3 Calculul tuplurilor

Calculul tuplurilor constituie pentru utilizator un sistem obisnuit de notatii similar cu cel al expresiilor utilizate in capitolele 2 si 3 pentru definirea unor operatori din algebra relationala. In timp ce, in algebra relationala operanzii sunt relatii, in 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 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 2 avem intrebarea : Care sunt reperele ce compun ansamblul cu numarul 100 ? Care are urmatoarea forma in calculul reltional pe tupluri:

iar in algebra relationala

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

Cate bujii se folosesc in Logan ?

4 Formule de calcul bazate pe tupluri

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

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

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 intai reguli de generare a formulelor si semnificatia fiecarei expresii in 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 intelegem ca xIr ;

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

Fie x o variabila tuplu, q I 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 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

cand f si g sunt adevarate si f g este adevarata cand 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 cand se inlocuie 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 inlocuind 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 intrebare in 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

5 Tipuri si ocurente libere si dependente

Mai inainte de a defini formal interpretarea unei formule va trebui precizat ce inseamna " formula f care contine pe x " si " cand t inlocuie 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) in 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 in formula f se numeste multime de mentionare a lui x si se noteza men(x,f)

Intotdeauna 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 4. Se consideram programul schitat mai jos. Orice mentionare a lui X, Y sau Z in corpul programului MAIN se refera la variabilele din instructiunea 1 de declarare. Orice mentionare a lui X sau Y in corpul procedurii SUB1 se refera deasemenea la variabilele din instructiunea 1 de declarare, in timp ce mentionarea lui X si W se refera la variabilele din instructiunea 2 de declarare. Variabilele Y si Z sunt globale in 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 in 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 in SUB12. Se observa ca ocurentele variabilelor pot fi locale sau globale. O ocurenta a lui Z in corpul lui SUB12 este locala in timp ce o ocurenta sa in 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 ]

Intr-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 in formule (mai exact ca declaratiile din programe). Vom defini notiunile de ocurente libere si dependente recursiv inainte de a defini tipul variabilei x in formula f (type(x,f)) si multimea de mentionare a lui x in formula f (men(x,f)). Type(x,f) si men(x,f) sunt definite numai cand x este ocurenta libera in f. Vom utiliza conceptele de ocurenta libera ocurenta dependenta, type si men pentru construirea de formule legale (permise ) utilizand diferiti conectori.

Vom considera mai intai cazul cand f este o formula atomica.

a1. Daca f=r(x), atunci x este o variabila libera in 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 in f, type(x,f) este nedefinit si

men(x,f)=A.

Consideram cazul cand 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 in 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 in h, atunci type(x,g) men(x,h), trebuie sa aiba

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

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

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

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

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

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

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

in f cum este in 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 in f4.

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

aceleasi ca in g.

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

In urmatoarele exemple se foloseste baza de date din figura 1. Punem

=

Exemplul 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)Irf in locul x(R)( r(x) f ). Analog in locul x(R)( r(x) f ) se foloseste x(R)Ir f .

Exemplul 6. Fie f formula :

x( Ist( y( Ist(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 7. Fie formula :

x( Ist(x(MAGAZIN) ACR y( Ians(x(COD) y(COD) y(TIP) Cielo))

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

Exemplul 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) in 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 in locul lui x(A₁) y(A₁) x(A₂) y(A₂) x(A_m) y(A_m) .

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 in 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 in 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 inlocuim variabilele tupluri prin tupluri.

Definitia 6. Fie f(x) o formula permisa. Fie R type(x,f), daca type(x,f) este definit, in caz contrar R este orice submultime a lui U care contine men(x,f). Atunci rezultatul inlocuirii lui x cu t in 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 in r(x) atunci r(x) se inlocuie cu true daca tIr si false in caz

contrar .

a2. Daca x in x(A)qx(B) este libera in f atunci x(A) este inlocuit cu constanta

cIdom(A), unde t(A) c in cazul cand x y. Daca x y si atomul are forma

x(A)qx(B) se inlocuie cu atomul de adevar daca t(A)qt(B) este indeplinita in caz

contrar cu fals.

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

se inlocuie atomul cu false. Analog pentru cqx(A).

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

Exemplul 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 7. Fie formula f fara variabile tuplu libere dar in care true si false pot sa apara ca atomi. Interpretarea lui f notata cu I(f) se defineste recursiv in 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

in 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 in caz contrar I(f)=false. Daca

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

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

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

I(f)=false.

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

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

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

Exemplul 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 in acr exista o cantitate dintr-un reper mai mare decat in 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 tIdom(R2

In 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 in relatia st (care poate fi prescurtata x(R2)Ist g (x). Formulele astfel studiate permit sa observam ca e necesar sa cautam numai acele tupluri din st, valoarea carora in coloana MAGAZIN este ACR. La inceput 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) 10). Aceasta formula are forma y(R2)h(y), astfel ca este necesar sa verificam cand I(h(u/y))=true pentru orice tuplu uIdom(R2). In acest caz, vom putea limita cautarea. Deoarece h(y) are forma st(y) h (y) va trebui sa consideram numai tuplurile din st. Alegand 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 intoarcem 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 uIdom(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 inlocuita prin y(CANT) < x(CANT). Acum putem sa definim expresia de calcul a tuplurilor.

Definitia 8. Fie E= o expresie de calcul a tuplurilor in 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.

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

In 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. In raport cu acesta interpretare, calculul tuplurilor si algebra relationala sunt la fel de expresive.

Teorema 1. Fie algebra relationala cu complement A=(U, D, dom, R, d, Q, O) si calculul tuplurilor TC=(U, D, dom, R, d, Q). Pentru orice expresie algebrica EIA exista o expresie FITC astfel incat E(d)=F(d) pentru orice stare a lui d.

Demonstratie. Este sificient sa presupunem ca E este din subalgebra A , unde O este inlocuita 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 decat 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-A1Am 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-A1Amy(C) x(C) y(B_i)=x(A_i). Din constructie resulta FITC.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₂. In baza inductiei E₁ si E₂ , atunci F=

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

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 : EsF=

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

furnizor

s_COMB=carb(furnizor)

p_numef

7 Interpretarea restransa a formulelor de calcul a tuplurilor

Interpretarea data pentru formulele de calcul a tuplurilor prezinta in practica cateva greutati cand calculul tuplurilor este considerat ca baza pentru un sistem de interogare. Expresiile de calcul poate sa defineasca relatii infinite. In 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 intregului dom(R) care poate sa fie infinit. Vom prezenta o interpretare alternativa pentru formulele cand tuplurile nu sunt compuse din valorile domeniilor care apar in formulele sau relatiile ce sunt mentionate !n formula. Interpretarea initiala va fi numita generalizata in timp ce interpretarea alternativa va fi numita restransa.

Definitia 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 in relatiile continute in f sau ca, constante. Nu se exclude posibilitatea ca edom(A,f)= . Aceasta se intampla cand atributele A nu sunt in f. Pentru o multime de atribute R ,vom numi edom(R,f) multimea tuturor tuplurilor t astfel ca t(A)Iedom(A,t), pentru orice AIA.

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 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 in 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 in g si h nu exista variabile libere. i(f)=true daca i(g)= i(h)=true, in caz contrar i(f)=false. Daca f=g h, atunci i(f)=false ; daca i(f)= i(f)=false si i(f)=true in caz contrar.

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

i5) Daca f= x(R)g. i(f)=true daca pentru orice tIedom(R,g), i(g(t/x))=true. In caz contrar, i(f)=false.

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

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 decat tupluri din edom(R)

Definitia 11 O expresie este sigura:

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

- pentru orice subformula a lui f de tipul ( t(R)g(t)), daca t_i satisface g, atunci tIedom(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 1. Pentru orice expresie de calcul sigura, evaluarile restranse si generalizate sunt echivalente.

Teorema 2. Pentru orice expresie de calcul bazata pe tupluri exista o expresie sigura bazata pe calculul tuplurilor F e echivalenta cu E in raport cu interpretarea restransa.

Teorema 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 decat E (ipoteza inductiva).

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

E₁

E₂

Atunci E=E₁ E₂=E

Cazul 2. E=E₁-E₂ E

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 intreg ci numai valorile dintr-un singur domeniu. De exemplu, intrebarea 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 utilizand 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 in 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, obtinandu-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 intr-o formula f este dat fie de un domeniu din D, fie este nedefinit. In 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 restranse. Cuantificatorii sunt utilizati chiar si la descrierea tipului unei variabile intr-o formula ( ca si declaratiile intr-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 in cazul CRT, in CRD legalitatea reprezinta o cerinta de compatibilitate a tipului variabilelor in 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 indeplinita egalitatea: dom(C)=dom(D)=dom(E) si atributele A si B sa fie <-comparabile.

In 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). cand se utilizeaza variabile precedate de cuantificatori este mai bine sa se foloseasca domeniul si nu atributul de notare a tipului. Inlocuirea unei variabile libere x in formula f in CRD cu constanta c este analoaga cu cea din CRT si se noteaza cu f(c/x). se presupune ca cItype(x,f). Dupa ce s-a inlocuit variabila libera x cu constanta c, atomii compusi in intregime din constante se schimba cu constantele booleene True si False, in concordanta cu regulile cuprinse in formule.

Exemplul 2. Consideram formula:

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

Variabila x este libera in 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 in 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 in formulele de calcul a tuplurilor. Pentru o formula f= x(A)g(x), I(f)=true daca si numai daca exista cIdom (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 cIdom(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)) pentri orice cIdom(CANT), unde h (w) este formula st(400, acr w>86). Interpretarea in h (w) este true pentru orice alegere a lui w cu exceptia lui 106 si este true pentru orice cIdom(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 in U si type(x_i,f)=dom(A_i), 1 i n.

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

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

Daca f= x(A)g(x), atunci I(f)=true cIdom(A,g) astfel ca I(g(c/x))=true. Similar, daca f= x(A)g(x), atunci I(f)=true cIdom(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 in 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_iIedom(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 cIdom(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 in CRD care este echivalenta cu E in raport cu evaluarea limitata.

Aceste rezultate sunt analoage cu cele din calculul tuplurilor. Orice expresie din CRT de forma se translateaza intr-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 s F in raport cu evaluarea nelimitata;

E s F in 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_iIdom(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).