Optimizarea frazelor de interogare prof. dr. ing. Mircea Petrescu

Obiectivul optimizarii: creterea vitezei de access la informaia din baza de date (reducerea timpului de access). Evident de la nceput: timpul cel mai lung se consum la prelucrarea interogrilor care conin produse carteziene, respectiv jonciuni.

Strategii generale folosite pentru optimizare: 1. Efectuarea seleciilor ct mai devreme posibil; 2. nainte de jonciuni, se prelucreaz preliminar fiierele (relaiile) prin operaiuni de sortare i

de indexare; 3. Cutarea de sub-expresii care se repet n expresii mai mari; 4. Aranjarea n cascad a seleciilor i proieciilor; 5. Combinarea proieciilor cu operaiuni binare adiacente; 6. Combinarea unora din selecii cu produse carteziene care eventual le preced, pentru a obine

jonciuni.

Echivalena expresiilor Folosit n procesul transformrii expresiilor (algebrice relaionale). n fapt, prelucrarea frazelor de interogare este iniiat de un procesor de cereri (interogri), a crui aciune ncepe prin construirea unui arbore de derivare destinat evalurii unei expresii algebrice (coninut implicit n fraza de interogare).

Reguli de echivalen a expresiilor: 1. Comutativitate: ; 1221 EEEE 1221 EEEE >< . 2. Asociativitate: ( ) ( )321321 EEEEEE ; ( ) ( 321321 EEEEEE >< ) . 3. Proiecii n cascad: ( )( ) ( )EE

nmn AABBAA ......... 111 , cnd fiecare Aj{Bi}.

4. Selecii n cascad: ( )( ) ( )EE FFFF 2121 . 5. Comutativitatea seleciilor cu proieciile: ( )( ) ( )( )EE FAAAAF nn ...... 11 . 6. Comutativitatea seleciei cu produsul cartezian: ( ) ( ) 2121 EEEE FF , dac toate

atributele din F fac parte din E1. Dac F=F1F2, unde F1 conine numai atributele din E1, iar F2 conine numai atribute din E2, atunci: ( ) ( ) ( 2121 21 EEEE FFF ) . Dac F1 conine numai atribute din E1, iar F2 conine att atribute din E1, ct i atribute din E2: ( ) ( )( )2121 12 EEEE FFF .

7. Comutativitatea selecie reuniune, respectiv selecie diferen: ( ) ( ) ( ) ( ) ( ) ( )2121 EEEE FFF 2121 EEEE FFF , . 8. Comutativitatea proiecie produs cartezian: ( ) ( ) ( )2...1...21... 111 EEEE kmn CCBBAA ,

unde {Bj} este mulimea atributelor care {Ai}, iar Bj este prezent n E1. Respectiv {Cj} este mulimea celorlalte atribute din {Ai}, fiecare Cj fiind prezent n E2.

9. Comutativitatea proiecie reuniune: ( ) ( ) ( 2...1...21... 111 EEEE nnn AAAAAA ) .

Algoritm pentru optimizarea expresiilor relaionale Intrare: un arbore sintactic ce reprezint o expresie relaional.

Ieire: program pentru evaluarea expresiei.

Metoda:

1

Pas 1. Fiecare selecie ( )EnFF ...1 este transformat n secvena ( )( )( )EnFF ...1 (regula 4).

Pas 2. Fiecare selecie este deplasat ct mai jos posibil n arborele sintactic (regulile 4-7).

Pas 3. Fiecare proiecie este deplasat ct mai jos posibil n arborele sintactic (regulile 3, 8, 9, 5).

Pas 4. Secvenele de selecii i proiecii sunt combinate n selecii sau proiecii unice, sau n selecii urmate de proiecii (regulile 3, 4, 5). Not: n pasul 4, procesul recomandat poate nclca principiul potrivit cruia proieciile sunt efectuate ct mai curnd posibil. Trebuie analizat eficiena!

Pas 5. Nodurile interne ale arborelui rezultate prin parcurgerea pailor anteriori sunt grupate n blocuri. Fiecare nod intern care corespunde unei operaiuni binare poate face parte din acelai bloc ca i predecesorii si imediai cu care sunt asociate operaiuni unare. Din bloc pot face parte i orice lan de noduri succesoare asociate cu operaiuni unare i terminate cu o frunz. Ultima regul nu se aplic atunci cnd operaiunea binar este un produs cartezian, iar acesta nu este urmat de o selecie care se combin cu produsul menionat, astfel nct s formeze o jonciune cu = semnul egalitii (echi-jonciune!).

Pas 6. Se evalueaz fiecare bloc, n orice ordine, astfel nct niciunul din blocuri nu este evaluat naintea grupurilor sale succesoare. Ca rezultat al evalurii este produs un program.

Exemplu. Fie baza de date cu relaiile: Circuit(Cnume, Fnume, Cod), Furnizor(Fnume, Fadr), Utilizator(Unume, Uadr, Nrdoc), Livrari(Nrdoc, Cod, Data).

Presupunem c pentru a rspunde la anumite fraze de interogare privind livrrile de circuite, este mai nti construit o vedere care conine informaii referitoare la circuitele livrate, cu ajutorul relaiilor Livrari, Utilizator, Circuit. Vederea va fi definit prin expresia relaional: (( CircuitUtilizatorLivrariUV )) , unde V = Cnume, Fnume, Cod, Unume, Uadr, Nrdoc, Data, iar U = Utilizator.Nrdoc = Livrari.Nrdoc Circuit.Cod = Livrari.Cod. Vom admite c fraza de interogare solicit lista numelor circuitelor livrate nainte de 10 ianuarie 2008. n termenii algebrei relaionale, aceast fraz poate fi formulat prin expresia: ( )( )( )( )CircuitUtilizatorLivrariVUDataCnume < 2008.01.10 . Pentru evaluarea expresiei, este construit mai nti arborele sintactic:

Cnume Data

Ca urmare a aplicrii algoritmului pentru optimizare, este obinut un nou arbore sintactic necesar evalurii frazei de interogare, cu forma:

Cnume Circuit.Cod=Livrari.Cod Livrari.Cod (Circuit.Cod),Cnume Utilizator.Nrdoc=Livrari.Nrdoc (Livrari.Cod),(Livrari.Nrdoc) Utilizator.Nrdoc Data