PRELUCRAREA DISTRIBUITA A INTEROGARILOR

Interogari pur locale - rare in SD. Datele cerute - plasate in cel putin doua situri diferite → pentru optimizarea interogarilor, problema trebuie tratata:

la nivel global: strategiei - datele problemei, coordonarea operatiunilor aferente, transmiterea si preluarea de mesaje catre/dinspre siturile locale

nivel local: strategia de prelucrare a interogarilor, comunicare rezultate partiale, verificari.

Daca cererea a fost emisa de catre situl X, catre Y pentru filtrari necesare si returnarea rezultatului partial, pentru a economisi timp, X rezolva in paralel problemele care-l privesc. In functie de cardinalitatea rezultatelor partiale, a dimensiunii unui tuplu si a vitezei de transfer pe linia de comunicatie, siturile trimit rezultatul partial la celalalt pentru efectuarea prelucrarilor finale → in cazul sistemelor relationale - doua mesaje. Pentru alte modele de date - numar de mesaje creste in functie de cardinalitatea fragmentului de pe un sit, sau cardinalitatea rezultatului partial → in privinta numarului de mesaje dintre siturile participante la interogare, modelul relational se preteaza cel mai bine SD.

O alta problema - o interogare poate fi rezolvata in mai multe feluri, neexistand doar o solutie unanim acceptata. Error! Reference source not found. - 6 modalitati de rezolvare a unei cereri intr-un SD. Numarul solutiilor depinde de factori:

• complexitatea interogarii
• situl de pe care se efectueaza cererea
• numarul de situri solicitate
• densitatea datelor de pe fragmentele siturilor implicate.

Timpul de raspuns la interogare depinde de strategia adoptata, de la < 1 secunda la zile intregi. Pentru acelasi tip de interogare, strategiile optime nu coincid intotdeauna. In majoritatea cazurilor rezultatele furnizate de strategiile specifice BD relationale dau rezultate mai bune.

Ideea de baza - performante cat mai apropiat de ale unei cereri locale. SD pot surclasa pe cele centralizate, deoarece in cele centralizate, interogarile implica accese la distanta.

Exemplu de identificarea strategiei optime de rezolvare a interogarilor - una din principalele probleme ale SD. Problema: cu cat creste timpul de prelucrare a unei cereri distribuite fata de una locala si cum se alege strategia optima? Ipoteze de lucru in exemplu:

• intre noduri - aceeasi rata de transfer
• nu are importanta situl din care se lanseaza cererea - in practica, acest factor nu este de neglijat.
• interogarea utilizeaza ca sursa de date 3 fragmente plasate in doua situri, unul care se afla la Secretariat, iar doua la Arhiva
• rezolvarea interogarii necesita uniuni (join-uri) ale fragmentelor, proiectii si selectii pentru a furniza raspunsul
• nu se iau in considerare timpii pentru prelucrarea interna (in cadrul aceluiasi fragment) a datelor, deoarece acesti timpi s-ar cheltui si la o prelucrare locala.

Datele problemei

Fragmente:

STUDENT (Matricol, Student) - evidenta simplificata a studentilor- plasat in situl Arhiva si are 3.600 de tuple. Dimensiunea unui tuplu:

4 + 20 + 25 = 49 octeti = 49 x 8 = 392 biti/tuplu

Atributul Student - uniunea Nume si Prenume din relatia initiala;

EXAMEN (CodMat, DenMat) - nomenclatorul materiilor de examen - in situl Secretariat si are cardinalitate 85 si

2 + 20 = 22 octeti = 176 biti/tuplu

NOTE (Matricol, CodMat, Nota) - catalogul virtual al facultatii - in Arhiva are 200.000 de tuple, cu 4 + 2 + 2 = 10 byti = 80 biti/tuplu.

Cererea: Afisarea tuturor studentilor, materiei de examinare si a notei obtinute pentru acei studenti care au luat note mai mari decat 8 la una dintre disciplinele de informatica.

Ipoteza auxiliara: pentru disciplinele de informatica codul materiei incepe cu cifra 5 → interogarea in SQL:

SELECT Student, Examen, Nota FROM Student S, Examen E, Nota N

WHERE S.Matricol = N.Matricol AND E.CodMat = N.CodMat

AND Nota > 8 AND CodMat BETWEEN 50 AND 59;

sau

SELECT Student, Examen, Nota FROM (Student S INNER JOIN Nota N ON S.Matricol = N.Matricol) INNER JOIN Examen E ON E.CodMat = N.CodMat

WHERE Nota > 8 AND CodMat BETWEEN 50 AND 59

sau

SELECT Student, Examen, Nota FROM (Examen E INNER JOIN Nota N ON E.CodMat = N.CodMat) INNER JOIN Student S ON S.Matricol = N.Matricol

WHERE Nota > 8 AND CodMat BETWEEN 50 AND 59;

Numarul estimat de tuple pentru fiecare restrictie in parte:

Presupunem ca numarul studentilor cu note mai mari de 8 este 30.000;

Estimarea numarului de materii de informatica: 8.

Parametrii retelei de comunicatie:

Intarzierea (latenta) transmisiei: 0,2 secunde;

Rata de transfer: 10.000 de biti pe secunda.

Strategii de rezolvare

Strategia 1: Se muta toate fragmentele in Arhiva - prelucrarile in acelasi loc. Singurul fragment care trebuie mutat este cel din Secretariat, adica fragmentul EXAMEN. Cardinalitatea fragmentului este 85, iar dimensiunea unui tuplu de 22 de octeti, → pentru o transmisie de date, timpul alocat comunicarii:

T1 = 0,2 + (176 x 85)/10.000 = 1,696 secunde

Apoi - o prelucrare locala, nu va mai fi folosit mediul de comunicatie, doar eventual la publicarea rezultatelor.

Strategia 2: Se muta toate fragmentele in Secretariat, adica pe cele doua fragmente din Arhiva. In Secretariat se fac cele doua operatii de uniune si cele doua de restrictie, urmate de proiectii asupra rezultatului intermediar pentru eliminarea atributelor care nu sunt solicitate in raspuns (cheile de legatura). Nu este obligatorie respectarea ordinii operatiilor amintite.

T2 = 0,2 x 2 + (392 x 3.600 + 80 x 200.000)/10.000 =

301,52 secunde = 5,0253 minute

Strategia 3: Se determina in Arhiva sunt studentii cu note > 8, indiferent de examenul sustinut (o operatie de uniune si una de selectie intr-o ordine aleatoare). Rezultatul partial (30.000 de tuple) va fi transmis spre verificare, pe rand, fragmentului de date din situl Secretariat. Pentru optimizarea verificarii - chiar daca este una locala - se va efectua restrictia asupra fragmentului EXAMEN, in vederea stabilirii disciplinelor de informatica. O verificare necesita o operatiune de transfer a cererii de verificare de la Arhiva la Secretariat urmata de furnizarea raspunsului de la Secretariat la Arhiva pentru a afla daca acei studenti care au obtinut note > 8 le-au obtinut la discipline de informatica. Formarea rezultatului final este graduala si se obtine prin comparare tuplu cu tuplu. Cererea si raspunsul pentru verificarile individuale au timpi insesizabili, atat lungimea cererii, cat si a raspunsului va trebui impartita la rata de transfer, care este foarte mare in comparatie cu acestea.

T3 = 0,2 x 2 x 200.000 = 80.000 secunde = 22,22 ore

Strategia 4: Se fac aceleasi operatii preliminare in ambele situri, cu diferenta ca se vor transmite cererile de verificare dinspre situl Secretariat inspre Arhiva, adica se va verifica pentru fiecare examen de informatica cine a luat nota mai mare de 8. Pentru aceasta, cele 8 cereri de verificare vor fi transmise dinspre situl Secretariat inspre Arhiva.

T4 = 0,2 x 2 x 8 = 3,2 secunde

Strategia 5: Se efectueaza toate operatiunile posibile din cadrul sitului Arhiva. adica uniunea dintre STUDENT si NOTE, precum si restrictia referitoare la acele note care sunt mai mari de 8. Se executa proiectia asupra atributelor Student, CodMat si Nota. Rezultatul intermediar va fi format din 30.000 de tuple a cate 49 de octeti (292 biti). Relatia rezultat va fi transferata in situl Secretariat, unde se va face uniunea, selectia relativ la materiile de informatica si proiectia dupa Student, Examen, Nota.

T5 = 0,2 + (292 x 30.000)/10.000 = 876,2 secunde = 14,8 minute

Strategia 6: Prin selectie se gasesc in Secretariat toate materiile de informatica din nomenclator (fragmentul EXAMEN). Rezultatul partial (cele 8 tuple care indeplinesc conditia) se muta in Arhiva unde vor avea loc toate prelucrarile necesare: efectuarea restrictiei asupra notelor obtinute in cadrul fragmentului NOTE pentru gasirea cazurilor cu nota > 8. Uniunea celor 3 fragmente rezultate si efectuarea proiectiilor relativ la atributele Student, Examen, Nota.

T6 = 0,2 + (176 x 8)/10.000 = 0,3408 secunde

Sintetizarea rezultatelor celor 6 strategii:

→ strategia a 6-a a furnizat cea mai mica intarziere fata de un sistem nedistribuit, 0,3408 secunde, de 234.742 ori mai mic decat timpul maxim → rezultatele cele mai bune sunt date de tipurile de strategii care folosesc mutari de tuple in bloc.

GESTIONAREA DISTRIBUITA A TRANZACTIILOR

Obiect de studiu - controlul accesului concurent si problema tolerantei la defecte. Fata de abordarea cu un nod central, in cazul SD lucrurile se complica. O tranzactie lansata in SD are nevoie de agenti, care sa reprezinte si sa verifice rezultatul finalizarii tranzactiei in fiecare din siturile implicate. Pentru ca o tranzactie sa satisfaca cerinta de atomicitate fiecare agent al tranzactiei trebuie sa-si fi indeplinit sarcina, sau toti sunt nevoiti sa ruleze tranzactia inapoi.

Metoda cea mai raspandita de control al accesului concurent este blocarea.

Gestionarea distribuita a tranzactiilor este strans legata de transparenta tranzactiilor. Fara a lua in considerare aspectele referitoare la controlul concurentei si a rezistentei la defecte, intr-un mediu distribuit, performante atat la nivelul vitezei de executie, cat si la cel al concurentei se realizeaza prin utilizarea subtranzactiilor,.

Fie un SD cu siturile - CLUJ si SIGHET→ 2 fragmente orizontale: C_STUDENT cu n tuple si S_STUDENT cu m tuple. Tranzactia T: afisarea numelor si a notelor obtinute de fiecare student.

Comparatie dintre gestiunea tranzactiilor in sistem centralizat si distribuit

→ Timpul total de executie al tranzactiei T este 2(m+n)+2, al subtranzactiei TC 2n+2, iar cel al subtranzactiei TS e 2m+2 → in sistem centralizat - 2(m+n+1) unitati de timp, in BDD timpul de executie - 2k+2, k=MAX(m,n) → timpul executiei tranzactiei nedistribuite = timpul necesar parcurgerii secventiale a tuplelor relatiilor implicate - timpul finalizarii unei tranzactii distribuite = timpul necesar prelucrarii fragmentului orizontal cu cardinalitatea cea mai mare → cu cat numarul de fragmente ale relatiei la care se refera tranzactia este mai mare - viteza de executie este mai mare. Un SD permite o concurenta mai ridicata, cat si o granularitate mai fina a protocoalelor de control a accesului (in prelucrarea centralizata - blocarea intregii relatii, in SD blocarea unui fragment de relatie).

Obs. Nu se poate deduce o regula generala pentru timpii implicati. Factorul timp depinde de complexitatea tranzactiei, numarul de fragmente implicate, tipul de fragmentare, distributia fragmentelor si a replicilor lor in sistem etc.

Transparenta la defectiuni si capacitatea de refacere, trebuie sa se tina cont de atomicitatea tranzactiilor si de caracterul durabil (permanent) al modificarilor facute. Un SGBDD trebuie sa garanteze ca tranzactia globala este atomica, adica toate tranzactiile locale pe care le implica fie s-au terminat cu succes, fie au fost toate anulate. Nu exista situatii de compromis, deoarece datorita caracterului durabil al subtranzactiilor se pot ajunge la inconsistente. Pe langa problemele din sistemele centralizate - caderea sistemului, pene de mediu, erori software, neglijenta, dezastre fizice naturale sau sabotajul - SD trebuie sa tina cont si de: pierderea unui mesaj, defectarea legaturilor de comunicatie, defectarea unui sit sau de partitionarea retelei. SD trebuie sa furnizeze mecanisme de refacere, care indiferent de posibilele accidente enumerate trebuie sa sustina atomicitatea tranzactiei globale.

INDEPENDENTA DE HARDWARE

Aplicatiile trebuie sa satisfaca criteriul transparentei fata de masina de calcul. SD nu trebuie sa faca rabat de la acest aspect. Putem sa avem echipamente Dell, HP, Siemens-Fujitsu, Compaq, IBM etc. in configuratii si de performante diferite. SD nu trebuie sa aiba afinitati inspre anumite marci si deci sa nu trateze discriminatoriu nodurile conectate. Toate siturile sunt tratate in mod egal. Tehnologia - transparenta utilizatorului.

INDEPENDENTA DE SISTEMUL DE OPERARE

SD trebuie sa functioneze pe masini diferite din punct de vedere al tehnologiei hardware, cat si pe calculatoare echipate cu SO. Utilizatorul nu trebuie sa resimta amprenta unui SO diferite, instalate pe masini diferite, sau chiar pe acelasi echipament. Indiferent ca e vorba de Unix/Windows, OS/2, de versiuni sau "dialecte" diferite SD ruleaza pe oricare dintre acestea, fara ca operatorul sa sesizeze diferente in utilizare intre calculatoare cu SO diferit.

INDEPENDENTA DE RETEA

Nodurile SD sunt conectate logic la aceeasi retea de comunicatie - indiferent de topologii, vitezele de transfer, dimensiunile pachetelor, metodele de acces la mediu sau tehnologia subretelelor - acestea nu trebuie sa devina un impediment in buna functionare a sistemului. Siturile unui astfel de ansamblu pot sa provina din retele eterogene fara a fi afectate performantele.

INDEPENDENTA DE SISTEMUL SGBD

Este unul dintre cel mai greu de atins. Ideal - toate siturile SD sa ruleze acelasi SGBD. Nu poate fi pus in practica datorita eterogenitatii echipamentelor si a SO si latura financiara. Cu SGBD-uri - diferite, ar fi de recomandat ca sa nu fie problema incompatibilitatii canalelor de comunicare intre siturile cu SGBD-uri diferite. Un astfel de canal ar fi recunoasterea de catre siturile implicate a aceluiasi standard SQL. SD ideal - asigura transparenta fata de SGBD-ul utilizabil in siturile sale.

Exemplu: SD, contine cel 2 situri: A si B. Pe unul ruleaza Ingres, iar pe celalalt Oracle. Un utilizator din A doreste sa lanseze o interogare care necesita informatii din A, cat si din situl B. Daca sistemul ar fi omogen solutionarea cererii n-ar fi o problema. Asa insa, pentru asigurarea transparentei fata de SGBD sistemul are nevoie de o interfata intre cele doua sisteme care sa furnizeze raspunsul fara a crea senzatia sistemele ar fi eterogene. Aceasta interfata poarta numele de poarta/wrapper - un program special care va face ca Oracle sa se comporte ca sistemul din care se lanseaza cererea (Ingres). Localizarea acestui program nu prezinta importanta.

O poarta ipotetica a sistemului Ingres catre sistemul Oracle[1]

Pentru asigurarea transparente fata de SGBD, poarta are functiile:

Implementarea protocoalelor - schimbul de informatii: Ingres - Oracle;

Asigurarea unei functionalitati SQL server pentru situl B;

Realizarea corespondentei intre tipurile de date acceptate de sisteme;

Realizarea corespondentelor "dialectelor" SQL folosite de cele 2;

Asigurarea suportului de prelucrare a raspunsului furnizat de serverul Oracle in format recunoscut de clientul Ingres;

Corespondenta cataloagelor;

Uniformizarea problemelor de natura semantica: nume de atribute, conversii intre tipurile de date, unitati de masura, tratarea NULL-urilor;

Asigurarea aceluiasi protocol de control al concurentei si aplicarea lui.[2]

PROCESAREA SI OPTIMIZAREA CERERILOR

Limbajul de interogare, in SGBD-uri relationale putea sa fie bazat atat pe algebra relationala, cat si pe calcul relational. In cazul calculului relational este necesara o faza suplimentara de translatare a interogarilor in algebra relationala. In contextul SD, aceasta etapa este inglobata direct in sistem.[3]

Error! Reference source not found., procesarea interogarilor presupune 4 etape:

• Descompunerea interogarilor,
• Localizarea datelor,
• Optimizarea cererilor globale
• Optimizarea cererilor locale.

Primele 3 etape - executate centralizat, ultima la nivelul siturilor locale.

Prima etapa - descrisa asemanator si in Error! Reference source not found., dupa care modul de abordare se schimba, intalnindu-se totusi similitudini.

Descompunerea interogarilor

Este prima etapa a procesarii interogarilor - transformarea cererii intr-o cerere bazata pe algebra relationala aplicata relatiilor globale. Se face analiza sintactica si semantica. Tehnicile utilizate sunt identice ca si in cazul sistemelor centralizate. Descompunerea cererilor - pasi:

• Analiza preliminara,
• Normalizarea,
• Analiza semantica,
• Simplificarea si
• Restructurarea interogarilor.

Analiza preliminara

Se verifica corectitudinea lexicala si sintactica a interogarii. De exemplu, intr-o interogare SQL se verifica numele si ordinea clauzelor, scrierea corecta a numelor atributelor, testarea ambiguitatii, utilizarea corecta a operatorilor relationali si logici in functie de specificatiile limbajului etc. Oricare din aceste incalcari va fi semnalata de compilator.

Exemple de interogari incorecte:

SELECT Nume FORM STUDENTI;

SELECT Nume WHERE Matricol="47812" FROM STUDENTI; (ordine clauze)

SELECT IdStud, Nota FROM STUDENTI, CATALOG; (ambiguitate)

SELECT Nume, Prenume, CodLoc FROM STUDENTI; (avem doar CodLocD sau CodLocN)

SELECT Nume, Prenume FROM STUDENTI WHERE AnStud="1", 6<=Media<9; (omiterea operatorului AND si folosirea incorecta a operatorilor relationali)

Normalizarea

Normalizarea - traducerea cererii intr-o forma normala disjunctiva sau conjunctiva.

Exemplu de forma disjunctiva: (p q) ^~r (^~t p)

Exemplu de forma conjunctiva: p ^~q (r ^~t p), unde p, q, r, t sunt predicate. Exemple: Matricol = "14568", AnStud="3", SEX = "F", MEDIA > 8, Localitate="Cluj-Napoca" etc.

Analiza sintactica

Mai multe tehnici de reprezentare grafica a cererilor bazate pe algebra relationala - cea mai utilizata si intuitiva este cea arborescenta. Frunzele sunt reprezentate de relatii, iar nodurile intermediare de operatori. Ordinea de executie este dinspre frunze spre radacina, adica mai intai se aplica operatorii specifici frunzelor. O operatie se poate executa doar daca au fost executate toate operatiile inferioare nodului respectiv.[5]

In cazul calculului relational se va utiliza graful cererii. Nodurile grafului sunt ocupate de constante si atribute. Pe arcele care pornesc dintr-un nod atribut se vor trece operatii care reprezinta conditii de jonctiune. Pe cele care deriva dintr-un nod reprezentat de o constanta, vom avea conditii de selectie.[6]

Exemplu: Sa se afiseze studentii din anul 3 cu domiciliul in Cluj-Napoca

→ utilizeaza relatiile STUDENTI, LOCALITATI si JUDETE. Interogare SQL:

SELECT Nume, Prenume FROM LOCALITATI, STUDENTI

WHERE AnStud="3" AND CodLoc=CodLocD AND

(Sex="F" OR Sex="M") AND Loc="Cluj-Napoca";

C: Π_{Nume, Prenume} (σ_AnStud="3" (σ_{Loc="Cluj-Napoca"} LOCALITATI _{CodLoc=CodLocD} σ_{Sex="F" Sex="M"} STUDENTI)

Arborele cererii C

Urmeaza analiza semantica.

Analiza semantica

"Curatarea" interogarilor transpuse deja intr-o forma normalizata, de posibile formulari incorecte sau contradictorii.

• Primul nivel - compatibilitatea tipurilor. Nu putem sa avem comparatii intre atribute si valori/variabile de tipuri diferite. Chiar se admite in algebra predicatelor, nu avem corectitudine semantica. Predicatul AnStud = 1 pare corect - daca verificam domeniul de definitie al atributului vom constata ca este vorba de un sir de un caracter - comparat cu o valoare numerica. Ea va fi reformulata prin aducerea celor doi membri la un tip comun.
• Nu orice compatibilitate de tip conduce la rezolvarea definitiva a problemei semanticii. Exemplu AnStud = "I" sau AnStud = "8".

O interogare - incorecta semantic cand componentele sale nu contribuie la generarea unui rezultat. In contextul calcului relational nu se poate determina corectitudinea relatiilor generale[7]. Error! Reference source not found. se arata ca este posibila determinarea corectitudinii pentru un numar mare de interogari relationale, cu conditia ca acestea sa nu contina disjunctii si negatii. Pentru demonstarea acestui fapt - grafuri ale interogarii sau grafuri de conectare (a relatiilor sau a atributelor). In cazul in care nu toate nodurile sunt conectate la graf inseamna ca interogarea nu este corecta din punct de vedere semantic.

Interogare contradictorie rezulta adesea in cazul unor conjunctii de predicate disjuncte, in care intervin valori discrete, continue, sau combinatii mixte. Exemplu: Sex="M" Sex="F" Sex="M" ^~(Sex="M"),

Matricol = "85142" Matricol < "5".

Simplificarea

Etapa de eliminare a redundantelor - determina si elimina predicatele identice sau cele care se pot reduce la un singur domeniu, adica toate cele ce sunt superfluu → interogare echivalenta cu cea initiala, dar mai simplificata.

Se vor folosi proprietatile valorilor de adevar si ale conectorilor logici si

Exemplu: unul dintre predicate este redundant si anume:

AnStud="3" (Sex="M" Sex="F") AnStud="3" (Sex="M" ^~(Sex="M")) (8) AnStud="3" T (3) AnStud="3".

Evident - un student nu poate fi atat fata cat si baiat. → cererea

SELECT Nume, Prenume FROM LOCALITATI, STUDENTI

WHERE AnStud="3" AND CodLoc=CodLocD AND

(Sex="F" OR Sex="M") AND Loc="Cluj-Napoca";

poate fi reformulata: "Sa se afiseze studentii din anul 3 cu domiciliul in Cluj-Napoca"

SELECT Nume, Prenume FROM LOCALITATI, STUDENTI

WHERE AnStud="3" AND CodLoc=CodLocD AND Loc="Cluj-Napoca";

C':Π_{Nume, Prenume}(σ_AnStud="3" (σ_{Loc="Cluj-Napoca"} (LOCALITATI)  _{CodLoc=CodLocD} STUDENTI))

Arborele cererii C'

C' - simplificarea lui C, cele doua fiind echivalente: C C'

Restructurarea interogarilor

Ultimul pas din cadrul etapei de descompunere a cererilor - 2 activitati:

• transformarea interogarii din calcul relational in algebra relationala (daca e cazul)
• transformarea prin aplicarea unor reguli euristice intr-o cerere echivalenta, dar cu executie mai eficienta. Nu se garanteaza insa ca rezultatul va fi si cererea optima.

O interogare scrisa in SQL se transcrie in algebra relationala prin interpretarea arborelui construit dupa cum urmeaza:

a)     Pentru fiecare relatie care intervine se va crea cate o frunza (se pot lua din clauza FROM);

b)     Nodul radacina reprezinta o operatie de proiectie asupra tuturor atributelor care se gasesc in clauza SELECT;

c)     Pornindu-se de la frunze, se rezolva problema calificarii relatiilor. Operatiile ce apar in clauza WHERE (selectie, uniune, reuniune) vor fi trecute - in ordinea in care apar in clauza amintita - in nodurile intermediare ale arborelui.[10]

→ este transpusa in algebra relationala, insa desi corecta si completa nu este optima. → reguli de transformare a unei interogari in interogari echivalente, dar mai eficiente. Ullman a demonstrat corectitudinea acestora.

Comutativitatea operatiilor binare

Asociativitatea operatiilor binare

Idempotenta operatiilor unare

Comutarea selectiei cu proiectia

Comutarea selectiei cu operatiile binare

Comutarea proiectiei cu operatiile binare

Error! Reference source not found., pag. 585 - 587 - 12 reguli, toate derivate din cele 6, insa mai specifice tipurilor de operatii implicate. In loc de "operatii unare" sau "operatii binare" se mentioneaza clar "proiectia", "selectia", respectiv "uniunea", "produsul cartezian" etc.

→ arborelui cererii C' din forma descrisa de algoritmul prezentat in cadrul primei subetape se aplicam regulile amintite mai inainte - regula 5 (comuta selectia cu join):

CodLoc=CodLocD

Arborele cererii C"

Cererea obtinuta C" este echivalenta atat cu C', cat si cu C - prin schimbarea ordinii de executie a celor 2 operatori s-a redus cardinalitatea relatiei STUDENTI care va fi implicata in operatia de uniune cu LOCALITATI → benefic deoarece uniunea necesita un efort mai mare decat selectia.

Localizarea datelor

In SD - interogari atat la nivelul BD locale, cat si la nivelul BD globale, distribuite. Daca BD locala - nefragmentata, interpretarea cererilor de catre SGBD-ul local se va face fara probleme specifice SD. Daca intervine   fragmentarea - se trateaza diferit. Cererile implica fragmente - o interogare nu il specifica in mod explicit datorita transparentei de localizare → sistemul va transforma cererea intr-o cerere in care in locul relatiilor se vor trece expresii echivalente acestora, dar in care unitatea de interogare nu va fi relatia, ci fragmentul - cereri fragment - interogarea echivalenta cu cea globala se va numi expresie canonica a cererii globale. Executia acestei cereri nu este eficienta → optimizari. Cererile pot fi optimizate si prin replicari - accesate replicile cele mai apropiate sau in paralel replici ale aceluiasi fragment → creste complexitatea interogarilor distribuite. Nu vom tine cont de aspectele care deriva din existenta replicarii fragmentelor.

Expresia canonica a cererii globale se obtine prin aplicarea formulelor de reconstructie ale relatiilor initiale din fragmente - operatia inversa fragmentarii.

Fie relatia STUDENTI cu 3 fragmente orizontale: in Cluj-Napoca (CJ_STUD), Sfantu Gheorghe(SG_STUD) si Sighetu Marmatiei (SM_STUD). Analog relatia LOCALITATI este divizata in 2 fragmente: AM_LOCALITATI (localitatile ce incep cu A pana la M) si MW_LOCALITATI (localitatile de la M incolo).

CJ_STUD = σ_{Locatie="Cluj-Napoca"}STUDENTI

SG_STUD = σ_{Locatie="Sfantu Gheorghe"}STUDENTI

SM_STUD = σ_{Locatie="Sighetu Marmatiei"}STUDENTI[13]

AM_LOC = σ_Loc<"M"LOCALITATI

MW_LOC = σ_Loc>="M"LOCALITATI[14]

STUDENTI = CJ_STUD SG_STUD SM_STUD

LOCALITATI = AM_LOC MW_LOC

Expresia canonica a cererii C"

Expresia canonica - echivalenta cu cea pe baza careia s-a format- nu este optima. Complexitatea expresiilor care le formeaza tinde sa devina tot mai mare in functie de numarul fragmentelor implicate in cerere. → cateva reguli de reducere atat a timpului de executie cat si a complexitatii reprezentarii.

• Regula 1: Folosirea operatiilor unare la generarea de selectii si proiectii pentru fiecare operand relational al expresiei.
• Regula 2: Grabirea executiei operatiilor unare.
• Regula 3: Substituirea rezultatelor selectiilor individuale cu relatia vida, atunci cand calificarea rezultatului este contradictorie.
• Regula 4: Utilizarea algebrei calificate pentru evaluarea rezultatelor jonctiunilor.
• Regula 5: Pentru obtinerea unei jonctiuni distribuite, operatiile de uniune vor avea loc dupa operatiile de jonctine ce urmeaza a fi distribuite.[15]

Transformarea cererii canonice conform primelor doua reguli

Se observa ca predicatul de selectie asupra fragmentului MW_LOC este contradictoriu cu definitia lui. Localitatea Cluj-Napoca nu este in fragmentul in care apar doar localitatile de la litera M inspre finalul alfabetului.

In urma aplicarii regulii 5 → reunim jonctiunile cate unui fragment din LOCALITATI cu cate unul din STUDENTI. Insa, evaluand posibilele rezultate ca urmare a aplicarii algebrei calificate (regula 4) s-a constatat ca din cele 3 uniuni posibile, doua dintre ele nu satisfac criteriul de jonctiune, returnand astfel relatii intermediare vide (nu puteam avea studenti domiciliati in Cluj-Napoca in fragmentele de Sighet sau Sfantu Gheorghe). Asadar, simplificarea cererii arata:

Simplificarea cererii canonice

In exemplu - problema transformarii cererilor globale bazate pe fragmente orizontale. Si in cazul celor verticale situatia asemanatoare, in sensul ca in cererea simplificata nu au ce sa caute acele fragmente verticale care nu contin atributele solicitate de interogare. Exemplu: vom lua aceleasi fragmente care au fost utilizate in paragraful de prezentarea a fragmentarii verticale:

L_LOC: Π_{CodLoc, Loc}(LOCALITATI)

J_LOC: Π_{CodLoc, Jud}(LOCALITATI)

Ne intereseaza doar localitatile care apar in relatia LOCALITATI.

SELECT Loc FROM LOCALITATI;

Simplificarea cererilor care implica fragmente verticale

In cazul fragmentarii mixte se aplica tratamentul specific pentru fiecare tip de fragment in parte. Atunci cand intervine fragmentarea derivata s-ar putea sa se reduca numarul operatiunilor de jonctiune.

Functiile de agregare sunt deosebit de importante in consultarea BD. Pentru ca acelor cereri globale, care contin grupuri si functii agregate, sa li se ofere un nivel acceptabil de optimizare, Ion Lungu aminteste de o noua regula euristica specifica:

• Regula 6: Pentru asigurarea gruparii distribuite si evaluarea functiilor de agregare, operatiile de reuniune[16] trebuie efectuate dupa cele de grupare.