Mecanisme pentru optimizarea cererilor de date
Utilizarea limbajelor relationale de manipulare bazate pe calculul relational sau a celor bazate pe mapping face necesara prezenta, unor mecanisme care sa transforme cererile īntr-o forma adaptata prelucrarilor eficiente. Aceste mecanisme sunt de fapt niste mecanisme de rescriere a cererilor de date si sunt necesare 22422s181w pentru optimizarea prelucrarilor de BD, cat si la realizarea bazelor de date distribuite, la care se folosesc mai multe tipuri de limbaje relationale.
Optimizarea cererilor de date se realizeaza prin parcurgerea urmatoarelor etape:
- exprimarea cererilor sub forma unor expresii algebrice relationale;
- aplicarea unor transformari algebrice asupra expresiilor obtinute īn etapa precedenta, īn scopul obtinerii unor expresii echivalente celor initiale, dar care sa fie executate mai eficient.
Exprimarea cererilor de date sub forma unor expresii din algebra relationala are la baza echivalenta dintre calculul relational si algebra relationala.
Procesul de transformare a cererilor de date se realizeaza conform unor strategii de optimizare.
Operatiile din algebra relationala, poseda o serie de proprietati care permit implementarea strategiilor generale de optimizare. Aceste proprietati sunt:
Deoarece F 1 F 2 = F 2 F 1, selectiile se pot comuta:
sF1 sF2 (E)) sF2 sF1 (E))
P5. Comutarea selectiei cu proiectia
Daca, conditia F implica numai atributele A1,..,An, atunci:
PA1,.,An (sF (E)) sF P A1,.,An (E))
Daca, conditia F implica si atributele B1,.,Bm, care nu apartin de A1,.,An, atunci:
PA1,..An (sF (E)) PA1,.,An sF PA1,..An, B1,..,Bm (E))).
Daca toate atributele mentionate īn F sunt atribute ale lui E1 atunci:
sF (E1 E2) sF (E1) E2
Daca, īn plus F este de forma F=F1 F2 si F1 implica numai atribute din E1, iar F2 implica numai atribute din E2, atunci: sF (E1 E2) sF1 (E1) sF2 (E2).
Daca F1 implica numai atributele din E1, dar F2 implica atribute aātat din E1 cat si din E2, atunci:
sF (E1 E2) sF2 sF1(E1) E2).
P7. Comutarea selectiei cu reuniunea
sF(E1 E2) sF (E1) sF (E2)
P8. Comutarea selectiei cu diferenta
sF(E1-E2) sF (E1)-sF (E2)
P9. Comutarea proiectiei cu produsul cartezian
Daca A1,.,An reprezinta o lista de atribute din cadrul a doua expresii relationale: E1 si E2, lista formata din atributele apartinand lui E1 si notate cu: B1,.,Bm si din atributele apartinand lui E2 notate cu: C 1,.,Ck, atunci:
PA1,..,An(E1 E2) PB1,.,Bm(E1) PC1,.,Ck(E2))
P10. Comutarea proiectiei cu reuniunea
PA1,..,An(E1 E2) PA1,..,An(E1) PA1,..,An(E2)
Aceste transformari permit definirea unor strategii generale de optimizare a cererilor de date, strategii care se refera la posibilitatile de crestere a performantelor de executie a cererilor de date prin reordonarea operatiilor implicate de aceste cereri. De exemplu, prin deplasarea operatiilor de selectie cat mai īn stanga expresiilor algebrice se reduce numarul de tupluri care trebuie manipulate īn procesul de executare a cererii.
Se pot mentiona urmatoarele strategii generale de optimizare a cererilor de date:
Deplasarea operatiilor de selectie īnaintea operatiilor de join. Join-ul si produsul cartezian actioneaza ca generatori de tupluri. Prin selectie se reduce dimensiunea relatiilor la care se aplica acesti generatori de tupluri, deci si a rezultatelor obtinute. Pentru deplasarea selectiei īn fata join-ului se vor aplica proprietatile mentionate anterior, tinand cont de faptul ca un join poate fi exprimat sub forma unui produs cartezian urmat de o selectie, iar īn cazul join-ului natural printr-un produs cartezian urmat de o selectie si o proiectie.
Deplasarea operatiilor de proiectie īnaintea operatiilor de join. Este realizata cu ajutorul proprietatii de comutare a selectiei cu produsul cartezian. Prin deplasarea proiectiei īn fata join-ului se obtin o serie de avantaje si anume:
- Daca proiectia lasa intacta cheia, operatia de join se poate realiza mai rapid īntrucat s-a redus numarul de tupluri ce trebuie memorate si eventual sortate.
- Proiectia implica eliminarea tuplurilor duplicate, care se poate realiza relativ usor, de exemplu cu ajutorul unui index. Dupa eliminarea tuplurilor duplicate, join-ul va fi mai simplu, pentru ca relatiile sunt mai mici.
Combinarea selectiilor multiple. Se realizeaza cu ajutorul relatiei de compunere a selectiilor. Nu toate selectiile sunt la fel de usor de realizat. Din aceasta cauza, numai selectiile mai rapide trebuie grupate si mutate īn fata operatiilor de join.
Selectiile rapide sunt cele realizate cu ajutorul unor tehnici de acces direct(indexare, hash, etc). Īn acest caz, timpul pentru realizarea selectiilor va depinde numai de numarul de tupluri selectate, nu si de marimea īntregii relatii.
Nu se recomanda gruparea selectiilor rapide cu cele lente. De aceea, este necesar, ca īnainte de combinarea selectiilor sa se estimeze viteza de realizare a fiecarei selectii īn parte.
Deplasarea selectiilor īn fata proiectiilor. Regula de mutare a selectiilor īn fata proiectiilor este data de proprietatea de comutare a selectiei cu proiectia. Realizarea deplasarii este utila atunci cand:
- exista o serie de facilitati īn realizarea selectiei, precum accesul direct, facilitati care ar putea fi inhibate prin operatia de proiectie ;
- eliminarea tuplurilor duplicate obtinute prin proiectie se realizeaza prin sortarea tuplurilor. Selectia reduce numarul de tupluri care trebuie sortate, facilitand astfel realizarea operatiei de proiectie.
|
