OPTIMIZAREA INTEROGĂ RILOR ÎN BAZE DE DATE [606358]

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

OPTIMIZAREA INTEROGĂ RILOR ÎN BAZE DE DATE
DISTRIBUITE

CAPITOLUL I

NOȚIUNI INTRODUCTIVE DESPRE BAZE LE DE DATE DISTRIBUITE

Profesor îndrumător
BOICEA ALEXANDRU

Student: [anonimizat]

1. Abrevieri ………………………….. ………………………….. ………………………….. ………………………….. ………………………….. …. 3
2. GENERALITĂȚI ………………………….. ………………………….. ………………………….. ………………………….. ……………………… 3
a) Definiții ………………………….. ………………………….. ………………………….. ………………………….. ………………………….. .. 3
b) Tipuri de baze de date distribuite (BDD) ………………………….. ………………………….. ………………………….. …………… 3
3. AVANTAJELE ȘI DEZAVANTAJELE BAZELOR DE DATE DISTRIBUITE ………………………….. ………………………….. ……….. 5
4. STOCAREA DATELOR IN BAZELE DE DATE DISTRIBUITE ………………………….. ………………………….. ………………………. 7
a) Fragmentarea ………………………….. ………………………….. ………………………….. ………………………….. …………………… 7
b) Replicarea ………………………….. ………………………….. ………………………….. ………………………….. ………………………. 10
c) Alocarea ………………………….. ………………………….. ………………………….. ………………………….. ………………………… 12
5. ASPECTE ALE PROCESĂRII CERERILOR ………………………….. ………………………….. ………………………….. ………………… 13
6. PROCESAREA CERERILOR ………………………….. ………………………….. ………………………….. ………………………….. …….. 15
a) Descompunerea cererilor ………………………….. ………………………….. ………………………….. ………………………….. … 16
b) Localizarea datelor ………………………….. ………………………….. ………………………….. ………………………….. ………….. 17
c) Optimizarea globală a cer erilor ………………………….. ………………………….. ………………………….. ……………………… 17
d) Optimizarea locală a cererii ………………………….. ………………………….. ………………………….. ………………………….. 17
e) Costul total de execuție ………………………….. ………………………….. ………………………….. ………………………….. …… 18
7. Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. ………………………… 20

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

1. Abrevieri

SGBD – sistem de gestiune al bazelor de date
BD – baze de date
BDD – baze de date distribuite
SD – sistem dis tribuit
2. GENERALITĂȚI
O baza de date distribuita este o baza de date stocata pe mai multe servere si este controlata de unul sau mai
multe sisteme de gestiune a bazelor de date (SGBD). Aceste servere pot sa se afle fizic in aceeasi locatie sau sa fie
distr ibuite geografic si conectate intr -o retea de calculatoare, acest lucru fiind transparent pentru utilizatori.
Sistemele de baze de date distribuite devin din ce in ce mai populare si sunt folosite intr -o gama larga de
aplicatii si domenii de activitate, multe dintre ele distribuite prin natura lor.
O baza de date distribuita este controlata de o baza de date centrala care are rolul de management a bazelor
distribuite. Partea din baza de date distribuita atasata la un singur server este numita partitie . Fiecare partitie a unei
baze de date distribuite se poate replica (duplica) identic intr -o alta locatie, deci in alt calculator din retea, cu scopul
maririi sigurantei in functionare (fiabilitatii). Avantajul acestei structuri redundante este ca eventua lele erori in
functionare se pot repara online fara intreruperea functionarii, asemanator cu principiul functionarii matricilor cu
discuri hard multiple de tip RAID.
a) Definiții
D1 BDD – colecție de BD integrate logic, însă repartizate fizic pe siturile unei rețele de calculatoare.
D2.: BDD – ansamblu de BD administrate de diferite situri – pentru utilizator o BD unică → proiectate sub
forma unor colecții de date integ rate, omogene1/ eterogene2, împrăștiate în rețea de calculatoare –
comportă ca BD globală.

b) Tipuri de baze de date distribuite (BDD)

1 Majoritatea BDD sunt omogene; Primele în ‘70
2 Începând din ‘80

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

Bazele de date distribuite pot sa fie :
➢ Omogene
o baza distribuita pe mai multe noduri;
o acelasi SGBD folosit in fiecar e nod al retelei;
o toate datele sunt organizate de catre un SGBD distribuit;
o schema globala care este insumarea tuturor schemelor locale;
o dificil de impus dar usor de administrat.

Sistemele de operare din noduri pot fi diferite (Windows, Linux) , d ar SGBD – ul trebuie să fie același (în
acest caz Oracle)
➢ Eterogene
o datele distribuite in mai multe noduri;
o SGBD diferit pentru fiecare nod in parte;
o utilizatorii cer acces local pentru scheme si SGBD;
o schema globala permite utilizatorilor sa accesez e date remote.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

În cazul bazelor de date etero gene atât sistemul de operare câ t și SGBD -ul sunt diferite.

3. AVANTAJELE ȘI DEZAVANTAJELE BAZELOR DE DATE DISTRIBUITE

BDD în general au mai multe avan taje decât dezavantaje, rămâne însă la latitudinea factori lor decizionali să
stabilească dacă este avantajoasă pentru activitate crearea unei baze de date distribuite și dacă da ce fel
de arhitectură trebuie implementată.
Avantaje
o Structura organizațională – SD – adaptează firesc cerințelor organizatorice ale înt reprinderilor. Spațiul
de lucru – distribuit geografic în clădire, localitate, județ, sau țară. Similitudini cu circulația
informațiilor într -o întreprindere. Un utilizator efectuează tranzacții asupra BD locale, pe când un
director de agenție, filială etc . prin interogări globale poate să consulte datele tuturor utilizatorilor
agenției sau activitatea întregii întreprinderi.
o Caracterul partajabil și autonomia locală – Chiar dacă o organizație este distribuită geografic, prin
utilizarea unui SD datele nu vo r fi proprietatea sitului local. Între utilizatori – posibilitatea de partajare
a anumitor informații, cum ar fi rapoartele. Un utilizator poate accesa și folosi atât datele din BD
locală cât și din celelalte situri. Informația solicitată cel mai des trebu ie să poată să fie găsită în
vecinătatea imediată. Chiar dacă datele sunt partajabile, acest lucru nu va afecta autonomiile
individuale. Fiecare sit este autonom și poate funcționa și în cazul în care resursele din alte situri nu
sunt disponibile. Problema tica autonomiei locale – structura organizațională descentralizată. În
structuri centralizate, SD – artificială, deoarece aceste sisteme urmăresc șablonul comportamental al
organizațiilor descentralizate.
o Disponibilitate și fiabilitate crescute – Sistemele centralizate slabe la fiabilitate. Dacănodul central
cade, întreg sistemul va deveni inoperabil. SD – datorită fragmentării și replicării datelor –
funcționează chiar și în cazul avariei unor situri sau a liniei de comunicație. Doar situl în cauză va fi
afectat și nu vor exista pierderi informaționale.
o Performanțe îmbunătățite – În SD datele sunt plasate în locul în care sunt solicitate cel mai des. Dacă
nu este situl local, trebuie să fie relativ apropiat. Când vorbim despre „distanță” nu ne referim

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

neapă rat la proximitate fizică. Un rol important îl poate juca lungimea mediului de transmisie (dacă
există), viteza și dimensiunea canalului de comunicație etc.
o Dezvoltare modulară – În BD centralizate adăugarea unuia sau mai multor membri putea să creeze
probleme serioase datorită SGBD -ului, capacitatea și performanța dispozitivului de stocare,
performanța tehnică a nodului central și performanța rețelei de calculatoare. La SD expansiunea se
poate trata modular, fără a fi afectată activitatea celorlalte situr i.
Economie – În anii ’60 – ’70 se considera că puterea de calcul se reflecta într -o anumită proporție în
costul suplimentar investit într -un singur sistem de calcul. Cu un cost se putea procura forța de calcul
egală cu pătratul diferenței de bani investi te. Legea lui Grosch – nu – valabilă în ultima perioadă. S -a
demonstrat că este mai ieftin să se investească în mai multe calculatoare de performanțe mai
modeste decât să se mărească sau să se achiziționeze un singur calculator de aceeași putere cu
perfor manțele însumate ale acelor calculatoare. Acesta a favorizat expansiunea SD în detrimentul
celor centralizate. Alt avantaj financiar – SD pot reduce costul comunicației pe distanțe mari specific
unor sisteme centralizate.
Dezavantaje
o Complexitatea – conce perea și întreținerea unui SD – mai greu decât a unui sistem centralizat.
Cerințele lui Date, îngreunează munca implementatorilor și administratorilor BD. Natura distribuită,
eterogenități, diferitele grade de transparență, fragmentarea, replicarea și aloc area complică
lucrurile la actualizarea BD, gestiunea tranzacțiilor sau prelucrarea și optimizarea interogărilor.
Connolly – dacă într -un SD nu se tratează corect aspectele specifice – riscăm ca avantajele se
transforme în dezavantaje față de sistemele cen tralizate.
o Lipsa de standarde – în diferite sectoare ale SD: de la arhitecturi, la protocoale specifice accesului la
date. Se reflectă în modul de abordare a proiectării sistemelor. Cu rigoarea ei, aplicarea
standardizării ar conduce și la elaborarea dacă nu a unor instrumente, cel puțin a unor metodologii
de translatare a unui sistem centralizat într -unul distribuit. Acest lucru este influențat și de
respectarea unor standarde pentru sistemele centralizate.
o Securitatea – atât avantaje cât și dezavantaje. Avantajul – în cazul unor atacuri informatice un SD
este mai puțin afectat fața de unul centralizat, dacă ținta este chiar nodul central. În alte cazuri, SD
va dezavantajate – atacul asupra oricărui sit al sistemului centralizat nu va afecta BD, pentru că
aceasta este stocată pe nodul central. SD sunt predispuse unor astfel de atacuri, tocmai datorită
naturii lor distribuite. Cu cât se utilizează mai mult rețeaua de comunicație, și cu cât întinderea ei
este mai mare, cu atât acesta devine un punct mai vulne rabil.
o Dificultatea controlului integrității și a concurenței – integritatea datelor – mai greu în SD; BD –
fragmente și chiar replicarea lor. Regulile de integritate nu se mențin în totalitate și în cadrul BD
divizate. Controlul concurenței se realizează în general mai greu în cadrul SD – este necesară
transferarea continuă a unui volum de mesaje prin intermediul rețelei. Uneori se sacrifică tocmai
aceste funcționalități primordiale în vederea reducerii traficului în mediul de comunicație.
o Lipsa de experie nță – Implementarea și proiectarea unui SD necesită persoane cu experiență în
proiectare, pe piață nu există prea multe opțiuni pentru alegerea unui SGBDD la prețuri rezonabile,
ca să fie la îndemâna oricărei organizații care ar avea nevoie de așa ceva.
o Dificultatea de înlocuire sau schimbare – SD sunt făcute la comanda beneficiarului și pe specificul
activității sale. Dacă intervin elemente noi, implementarea necesită un efort mai mare decât în
cazul sistemelor centralizate.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

4. STOCAREA DATELOR IN BAZELE DE DATE DISTRIBUITE

a) Fragmentarea

Fragmentarea este procedeul de spargere a relațiilor utilizate într -o BDD prin operațiuni relaționale de
proiecție și selecție controlate, pentru a plasa fragmentele acolo unde sunt cel mai frecvent solicitate datele
lor.
Se imparte relația r în fragmente mai mici de relații r1, r2,…..rn care conțin suficientă informație pentru a
reconstitui relatia principală r. Fragmentele r1,r1…rn vor fi plasate în BDD in locațiile în care ele sunt cel mai
frecvent accesate.

O abordare – prin divizarea tabelelor în unul sau mai multe fragmente disjuncte, în scopul stocării fizice.

Premisele de bază pentru fragmentare:

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

• Uzanța – Aplicațiile cu BD – multiutilizator – tabelele virtuale în detrimentul relațiilor – nu este nevoie
de toate informațiile, atât ca și structură, cât și ca și conținut, pe care o relație întreagă este capabilă
să le furnizeze → unitatea atomică de proiectare și utilizare nu va fi relația, ci o subdiviziune a
acesteia;
• Eficien ța – Apropierea de locul utiliză rii și eliminarea datelor care nu sunt prelucrate loc al. Exemplu:
corect – în situl A din Cluj – stochează relația ce conține mat eriile de studiu, iar pe nodul B din Sighet
relația care conține datele de identificare a tuturor studenților? Secretariatul di n Cluj utilizează
informațiile studenților din Cluj; cel din Sighet, informațiile studenților din Sighet. → Abordare
normală – datele studențil or din Cluj – stocate pe situl A, a celor din Sighet în B rezultă ca vom plasa
datele unde sunt solicitate cel m ai des;
• Paralelismul. Mai multe fragmente ale unei BD → sporirea accesului concurent – sistemul poate
răspunde în același timp la mai multe cereri. Exemplu: se răspunde mai repede unor cereri lan sate
simultan, una de pe situl A și una de pe B, în cazul în care A solicită med iile studenților din Cluj, iar B
ale celor din Sighet;
• Securitate – un atac asupra unui sit nu afectează funcționarea întregului sistem – doar fragmente ale
BD și nu întreaga BD sau relații întregi. Pentru a avea succes atacu l ar trebu i să fie direcționat asupra
mai multor noduri.

Dezavantajele fragmentării:
• Complexitatea proiectării. Bazele de date distribuite sunt mai greu de pro iectat. Existența
fragmentelor implică factori suplimentari de calcul cum ar fi stabilirea locației unui f ragment,
optimizarea interogărilor etc.;
• Performanța – performan țele unui sistem distribuit sunt mai bune decâ t cele ale unui sistem
nedistribuit dar în cazul în care se solicită informații prea disparate (de pe mai multe situri) acestea
pot scădea foa rte mult ;
• Controlul integrități i – dezideratul primordial al oricărui sistem tranzacțional, totuși existența mai
multor fragmente răspândite pe siturile sistemului distribuit , complică lucrurile.

Fragmentele rezultate – condițiile:
• Completitudinea fragmen tării . Fragmentele să asigure acoperirea întregii relații inițiale. Unele
fragmente pot fi redundante, suprapunîndu -se total sau parțial. F ragmentarea are ca obiectiv
eliminarea apariției pierderilor informaționale și nu cea a redundanțelor.
• Reconstruirea relației inițiale . În orice moment să poată fi reprodusă relația inițială din care provin
fragmentele. Se păstrează dependențele funcționale. Operatorii de recompunere trebuie să fie strict
relaționali.
• Caracterul disjunct – o completare la completitudin e. Fragmentele din aceeași relație trebuie să fie
disjuncte, să nu se suprapună, ca tuple sau atribute. Excepție fragmentarea verticală: pent ru
recompunere, cheile primare sunt replicate pentru fiecare fragment creat de -a lungul atributelor.
Unele SGBD -uri utilizează atribute surogat pentru cheie primară – prin generarea automată a unor
valori unice pentru fiecare tuplu – chei de replicare Access: Autonumber .

În funcție de operatorii relaționali: fragmentarea poate fi:
o Orizontală – relatia r este împarti tă in doua relatii R1 și R2 care conțin tuplurile tabelei
corespunzătoare relației R astfel : R1 preia tuplurile T1,T2,….T100 iar R2 preia tuplurile r ămase
T101,T102…T600.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

o verticală fragmentarea se face prin impărțirea coloanelor relației R în mai multe scheme A1,A2 care
au în comun tupluri -cheie comună TID

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

o mixtă – combină elementele celor două tipuri de fragmentare deja prezentate.

Uneori – fragmentări derivate (tip de fragmentare orizontală) sau relații nefragmentate .

Limitele de fragmentarea – de la un tuplu (în cazul fragmentării orizontale) un atribut (în cazul celei verticale),
sau o valoare a unui tuplu, în cazul celei mixte, până la întreaga relație în toate cazurile de fragmentare sau
până la întreaga BD în cazul fragmentării derivate → granulația fragmentăr ii. Ce, cum și cât fragmentăm sunt
întrebările la care trebuie să raspundă proiectanții de BDD.

b) Replicarea

Replicarea reprezint ă procesul prin care multiple copii ale datelor sunt stocate pe diferite site -uri.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

Avantaje
– Căderea unui site care conține relatia r nu afectează prelucrararea datelor atât timp cât există o
copie a acesteia replicată pe un alt nod
– Interogările care solicită relația r pot fi efectuate în paralel pe mai multe noduri
– Transferul de date este redus datorită faptului că relația r este disponibilă local pe mai multe
noduri.
Dezavantaje
– este folosit un spațiu de stocare mare
– Replicarea favorizează perfor manțele sistemului la interogarea datelor . La actualizări, poate constitui
un impediment: se generează trafic suplimentar, pot apărea inconsistențe datorită indisponibilității
temporare a unei replici.

Tehnica de replicare a datelor utilizata d e serverul Oracle este denumită Table Snapshots, prin care
serverul central (master) copiază la anumite momente de timp definite, numai acele înregistră ri din baza
de d ate care s -au modificat, propagând apoi aceste modificări în reț ea. Mecanismul de replicare utilizat de
serverul de baze de date IBM este sim ilar metodei snapshots utilizată de Oracle dar utilizeaza fiș iere de log
si backup pentru a gestiona datele din tabelele bazei de date ce trebuie replicate (care contin modificari).
Serverele de replicare reprezinta numai inceputul unei intregi generatii de produse software care
implementeaza concepte abstracte referi toare la distribuirea datelor in medii eterogene impreuna cu
tehnologii avansate de gestiune si procesare paralela, optimizata a tranzactiilor. Replicarea modificarilor de
date apare doar dupa ce sistemul se asigura ca semnatarul are cele mai recente snaps hoturi ale tabelelor
de scheme si date care au fost generate. Cand snapshoturile sunt distribuite si aplicate asupra
semnatarilor, doar acei semnatari care au nevoie de snapshotul initial sunt afectati. Semnatarii care au

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

primit deja inserarile, modificari le si stergerile (sau alte modificari asupra datelor) nu sunt afectati, numai
daca subscrierea (aderarea) este marcata pentru reinitializare.

c) Alocarea

Fie un set de fragmente F = {F 1, F2, …, F i, …, F n} într-o rețea formată din siteurile S = {S 1, S2, …, S j, …, S m}
și asupra cărora se execută anumite aplicații (interogări) Q = {q 1, q2, …, q k, …, q q}. Problema proiectării
alocării se referă la distribuirea optimă a fragmentelor F pe siturile S.
Potrivit lui Dowdy și Foster, „optimul” se referă la:
• Cost minim .
Funcția cost – compusă din:
o costul plasării fragmentului F i pe site -ul S j
o costul interogării S j de către F i
o costul actualizării tuturor fragmentelor F i plasate în toate siteurile
o costul com unicației.
Problema alocării – găsirea unei scheme de minimizare a costurilor

• Performanță . Strategia de proiectare – menținerea unui nivel de performanță prin minimizarea
timpului de răspuns și maximizarea capacităților sistemului ca măsură a contribuție i fiecărui site.
Alocarea – neredundantă sau redundantă
• Alocarea neredundantă – mai ieftină ca efort de proiectare și mai ușor de realizat. Alt avantaj –
posibilitatea de actualizare a fragmentelor. Se bazează pe metoda celei mai bune alegeri – unei stații
pe care deja a fost plasat un fragment, nu poate să -i mai fie alocat un fragment „înrudit”.
• Alocarea redundantă – mai complexă. Consultările de date și actualizările sunt problematice. Există
două variante de abordare a proiectării în acest caz:
a) Metoda s electării – identificarea siturilor pentru care beneficiul alocării unei copii depășește
costul alocării;
b) Metoda alocării progresive – se implementează inițial o alocare neredundantă. Apoi, în funcție
de gradul de profitabilitate al stațiilor se vor răspân di replici ale fragmentelor deja alocate, până
când nu mai există candidați la replicare.
Prima metodă (selectarea) este mai riguroasă și elimină posibilitatea de a înmagazin a pe același site
și copia fragmentului deja stocat.
Replicarea progresivă – meto dă euristică – bazată pe aserțiunea că profitabilitatea scade pe măsură
ce gradul de redundanță crește.

Abordare mai eficientă, dar și mai selectivă – metoda celei mai bune alegeri și în etapa de proliferare a
copiilor. Se începe cu fragmentele considerat e ca fiind cele mai importante, ținându -se cont la fiecare alocare
de relația de „rudenie” a tuturor fragmentelor ce există sau urmează a fi stocate într -un site.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

5. ASPECTE ALE PROCESĂRII CERERILOR

Complexitatea procesării cererii este proporțională cu pu terea de exprimare și capacitatea de
abstractizare a limbajului cererii. Scopul procesării cererii distribuite este de a găsi, pentru o cerere dată, o
strategie de execuție care să minimizeze funcții le de cost ale sistemului. O strategie de execuție este
specificată în termenii operațiilor algebrei relaționale și a primitivelor de comunicație cerute de baza de date
locală. Complexitatea operațiilor relaționale care afectează performanțele execuției ce rerii este de o
importanță majoră în proiectarea procesoarelor de cereri. Procesoarele de cereri pot să difere prin diferite
aspecte cum ar fi: tipul de algoritm, granularitatea optimizării, momentul optimizării, utilizarea statisticilor,
alegerea stațiilo r de decizie, exploatarea fragmentelor replicate, exploatarea topologiei rețelei, utilizarea
semijoin -ului etc. Această caracterizare este utilă pentru a compara alternativele de proiectare a
procesoarelor de cereri și pentru înțelegerea medierii între ef iciență și complexitate.

Caracteristicile sistemelor

Este destul de dificil de evaluat și de comparat procesoarele de cereri centralizate și distribuite pentru
că ele pot să difere prin mai multe aspecte. Vom prezenta câteva caracteristici importante pe ntru cele două
sisteme, dintre care primele patru sunt comune sistemelor centralizate și celor distribuite, iar restul sunt
specifice sistemelor distribuite.
Limbaje. Principala activitate a procesării era făcută inițial în contextul bazelor de date relați onale
deoarece acestea dispun de un limbaj de nivel înalt care permite efectuarea de către sistem a multor
optimizări. Limbajul de intrare al procesorului de cereri se poate baza pe algebra relațională sau pe calculul
relațional, cu observația că ultimul n ecesită o fază adițională de descompunere a cererii într -una formulată
în algebra relațională. Limbajul de ieșire este, în general, o formă internă a algebrei relaționale argumentată
cu primitive de comunicație.

Tipuri de optimizări. Scopul optimizării ce rerilor este de a alege cele mai bune metode dintre toate
strategiile posibile de execuție. Un mod de a căuta în spațiul soluțiilor este cel care utilizează previziunile
exhaustive ale costurilor fiecărei strategii și selectează strategia cu costul minim. Cu toate că este o metodă
eficientă în selectarea celei mai bune strategii, ea poate produce un cost de procesare semnificativ pentru
optimizare. Dacă spațiul soluțiilor este mare pot fi multe strategii echivalente, chiar pentru un număr mic de
relații, ia r dacă numărul relațiilor crește, problema devine complexă.
O metodă frecvent folosită, de reducere a costului căutării exhaustive este aceea de a minimiza
mărimea relațiilor intermediare. Aceasta se poate face executând mai întâi operațiile unare și ordon ând
operațiile binare după creșterea mărimii relațiilor intermediare. O euristică importantă în sistemele
distribuite este înlocuirea operațiilor de join prin combinații de semijoin pentru a minimiza schimburile de
date.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

Momentul optimizării
O cerere poat e fi optimizată la diferite momente, față de acela al execuției cererii. Optimizarea se
poate face static (înaintea executării cererii), dinamic (în timpul execuției) sau hibrid. Optimizarea statică
este făcută în momentul compilării și astfel costul ei po ate fi amortizat pentru mai multe execuții. Acest tip
de optimizare este util mai ales în metodele de căutare exhaustivă. Deoarece mărimea relațiilor intermediare
nu este cunoscută până în momentul rulării, ea trebuie estimată utilizând statisticile bazei de date. Dacă
aceste estimări sunt eronate, ele pot conduce la alegerea unor strategii suboptimale. Optimizarea dinamică
se face în timpul execuției. În orice moment al execuției, alegerea următoarei operații optime se poate baza
pe acuratețea informațiilo r despre rezultatele operațiilor executate anterior. Principalul avantaj față de
optimizarea statică este că mărimea relațiilor intermediare este disponibilă procesorului de cereri, dar
constituie o problemă faptul că optimizarea trebuie repetată la fiecar e execuție a cererii.

Statistici. Optimizarea cererilor se bazează pe statisticile bazei de date. În optimizarea dinamică ele
sunt utilizate la alegerea primelor operații, iar în cea statică furnizează o estimare pentru mărimea relațiilor
intermediare. În bazele de date distribuite, statisticile pentru optimizare sunt legate de analiza fragmentelor,
incluzând informații despre cardinalitatea și mărimea acestora, despre mărimea și numărul valorilor distincte
pentru fiecare atribut. Acuratețea statisticilor este obținută prin actualizări periodice.

Stații de decizie. Când se utilizează optimizarea statică, la selectarea strategii care se aplică cererii
pot participa mai multe stații. Multe sisteme utilizează modul de decizie centralizat, în care o singură st ație
generează strategia, dar procesul de decizie poate fi distribuit între diverse stații participante la generarea
celei mai bune strategii. Modul centralizat este mai simplu, dar cere cunoștințe despre întreaga bază de date
distribuite, în timp ce modul distribuit necesită numai informații locale. Se utilizează frecvent și modul hibrid
în care o stație ia majoritatea deciziilor, iar o altă stație poate lua decizii locale.

Exploatarea topologiei rețelei. Topologia rețelei este exploatată de procesorul de cereri distribuite.
In rețelele întinse, funcția de cost care trebuie minimizată poate fi restricționată la costul de comunicație,
care va fi considerat factorul dominant. Această presupunere simplifică mult optimizarea cererilor
distribuite, care poate f i împărțită în două probleme: selectarea strategiei de execuție globală și selectare
fiecărei strategii locale de execuție. În rețelele locale, costurile de comunicație sunt comparabile cu costurile
I/O. Astfel, este preferabil ca procesorul de cereri dist ribuite să mărească execuția paralelă. Capacitățile de
transmitere a unor rețele locale pot fi exploatate cu succes pentru optimizarea procesării operațiilor de join.
Exploatarea fragmentelor replicate. Relația distribuită este uzual împărțită în fragmente , iar cererile
distribuite exprimate pentru o relație globală sunt transformate în cereri pe fragmente fizice ale relației
(localizare). Mulți algoritmi de optimizare exploatează existența fragmentelor replicate în timpul rulării, cu
scopul reducerii timpi lor de comunicație.

Utilizarea interogărilor join optimizate

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

Operația de semijoin are proprietatea de a reduce mărimea relațiilor. Când principala componentă
a costului considerat este costul de comunicație, semijoin -ul este utilizat pentru îmbunătățire a procesării
operațiilor de join distribuit, în sensul reducerii schimburilor de date între relații .
Join-ul de tip Bloom are același scop de a minimiza cantitatea de date ce este transferată în rețea prin
folosirea filtrelor de tip Bloom. Filtrele de tip Bloom sunt structuri probabilistice ce au rolul de a testa dacă un element
aparține unui set de date. Acest tip de join apare in Oracle 10.2.0.x și este mult mai eficient decât toate tipurile de join
existente.

6. PROCESAREA CERERILOR

Problema procesării c ererilor poate fi descompusă în câteva subprobleme corespunzând diferitelor
componente ale procesării. Pentru simplificare, presupunem că avem un procesor static și semicentralizat
care nu exploatează fragmentele replicate. Intrarea este o cerere distribui tă exprimată în calculul relațional,
care se referă la o relație globală, necunoscându -se distribuția datelor. La transformarea acestei cereri într –
o secvență optimizată de operații locale contribuie patru direcții principale:
• descompunerea cererilor ( query decomposition );
• localizarea datelor ( data localization );
• optimizarea globală a cererii ( global query optimization );
• optimizarea locală a cererii ( local query optimization ).

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

a) Descompunerea cererilor
Prima componentă descompune cererile din calculul d istribuit în cereri algebrice pe relații globale.
Informația necesară pentru această transformare este găsită în schema conceptuală globală. Tehnicile
utilizate de această componentă sunt cele ale sistemelor centralizate. Descompunerea cererilor se face în
patru pași: normalizarea, analiza, simplificarea și rescrierea.
o Normali zarea
Cererea poate avea o complexitate arbitrara, depinzand de facilitatile furnizate de limbaj. Scopul
normalizarii este de a transforma cererea intr -o forma care sa faciliteze pr ocesarea sa ulterioara. In limbajele
relationale cea mai importanta transformare este cea a calificarii cererii, prin aplicarea de prioritati asupra
operatorilor logici. Exista doua forme de normalizare pentru predicate, una in care se acorda prioritate lu i
AND si alta in care OR este prioritar. In forma normala disjunctiva, cererea poate fi procesata considerandu –
se ca este compusa din subcereri conjunctive independente legat e prin reuniune (corespunzator
disjunctiilor). Aceasta forma poate conduce la mult iplicarea operatiilor de join. Forma normala conjunctiva
este mult mai practica deoarece calificarea cererii include mai multe predicate AND decat OR. Aceasta forma
conduce la replicarea predicatelor pentru cererile care implica mai multe disjunctii si doa r cateva conjunctii,
dar este un caz foarte rar.

o Analiza
Analiza cererii permite respingerea cererilor normalizate pentru care procesarea ulterioara este
imposibila sau nu este necesara. Principalul motiv pentru respingere este incorectitudinea ca ti p sau ca
semantica. De exemplu, se verifica existenta schemelor si obiectelor specificate in cerere, corectitudinea
sintaxei, etc. Cand unul dintre cazuri este detectat, cererea este returnata utilizatorului cu un mesaj
explicativ. Altfel, procesarea cerer ii continua.

o Eliminarea redundanț elor.
Limbajele relationale pot fi utilizate pentru controlul semantic al datelor. Î n particula r, o cerere
utilizator exprimată printr-o vizualizare poate fi imbogățită cu cateva predicate pentru obtinerea unei
coresp ondente vizualizare -relatie si asigurarea integritatii si securitatii semantice. Calificarea imbogatita a
cererii poate contine predicate redundante. Redundanta poate fi eliminata prin simplificare, utilizand reguli
fundamentale ale logicii matematice (abs ortia, idempotenta, principiul tertului exclus, principiul
contradictiei, regulile lui Morgan etc.).

o Rescrierea .
Ultimul pas al descompunerii cererilor este rescrierea cererii in algebra relationala. Aceasta rescriere
se face in doua etape:
• se tra nsforma cererea din calculul relational in algebra relationala;
• se restructureaza cererea din algebra relationala pentru a imbunatati performantele.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

b) Localizarea datelor
Intrarea pentru componenta a doua este o cerere algebrică pe relații distribuite. Rolul principal al
acestei componente este de a localiza datele necesare utilizând informațiile despre distribuția datelor. Ea
determină care fragmente sunt implicate și transformă cererea distribuită într -o cerere fragment. O relație
distribuită poate fi reconstruită utilizând regulile de fragmentare și apoi aplicând un program de localizare.

Generarea unei cereri fragment se realizează în doi pași:
1. cererea distribuită este transformată într -o cerere fragment prin substituirea fiecărei relații
distribuit e cu programul său de descompunere;
2. cererea fragment este simplificată și restructurată, pentru îmbunătățirea ei, utilizând aceleași
reguli ca și la descompunere.

c) Optimizarea globală a cererilor
Intrarea celei de -a treia componente este o cerere fragment , iar ieșirea acestei componente este o
cerere algebrică optimizată cu operații de comunicare incluse. Scopul optimizării cererii este de a găsi o
strategie de execuție optimă pentru cerere. O strategie de execuție pentru o cerere distribuită poate fi
desc risă prin operații ale algebrei relaționale și primitive de comunicație (operații de primire/trimitere), de
transfer a datelor între stații. Nivelurile anterioare au optimizat deja cererea, dar operațiile de comunicație
nu sunt încă specificate. Permutând ordinea operațiilor se pot găsi mai multe cereri echivalente.
Optimizarea cererilor constă în găsirea unei ordini optime a operațiilor în cererea fragment, încluzând
și operațiile de comunicație care minimizează funcția de cost. În general, această funcție este o combinație
între costuri I/O, costuri CPU și costuri de comunicație. O simplificare tipică făcută de sistemele distribuite
este de a considera costul de comunicație ca fiind cel mai important factor, lucru adevărat mai ales pentru
sistemele întinse unde limitarea lățimii de bandă face costisitoare comunicațiile.
Pentru a selecta ordinea operațiilor este necesar să se estimeze costurile de execuție ale ordinilor
alternative candidate. Determinarea costurilor de execuție înaintea executării cererii se face utilizând
statistici referitoare la fragmente și formule de estimare a cardinalității rezultatelor operațiilor relaționale.
Un aspect important al optimizării cererilor este ordinea join-urilor, deoarece, permutări ale join-
urilor în interiorul cere rii pot duce la îmbunătățirea ordonării după mărime. O tehnică de bază pentru
optimizarea unei secvențe de operații de join distribuit folosește operatorii de semijoin. Principalul rol al
semijoin -ului în sistemele distribuite, este de a reduce mărimea ope ranzilor pentru join și, astfel, a costurilor
de comunicație. Tehnicile mai noi, în care se consideră și costurile de procesare locală și cele de comunicație,
nu utilizează semijoin -ul pentru că poate amplifica costul procesării locale.

d) Optimizarea local ă a cererii

Ultimul nivel este îndeplinit de toate stațiile care au fragmente implicate în cerere. Fiecare subcerere
ce se execută pe o stație, numită cerere locală, este optimizată utilizându -se schema locală a stației.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

e) Costul total de execuție

Costul total de execuție al unei interogări într -un sistem distribuit constă din costul de prelucrare
(CCPU), costurile de accesare a discurilor (CI/O) și costul comunicației între noduri. Costul comunicației
constă din costul de trimitere și primire mesaje între noduri (CMSG) și, respectiv, costul de transfer date
între noduri (CTR). Costurile de comunicație depind în mare măsură de tipul rețelei de comunicație.
Formula costului total poate fi scrisă, după cum urmează:
Cost total = CCPU * nr_instrucțiuni + CI/O * nr_I/O + CMSG * nr_mesaje + CTR * cantitate_date
Timpul de răspuns al sistemului distribuit se calculează din momentul în care interogarea începe până când
primește răspuns din partea sistemului. O influență semnificativă în reducerea timpului de răspuns o au
procesarea paralelă și, respectiv, comunicația paralelă. Cu cât timpul de execuție și comunicație în paralel
sunt mai mari, cu atât mai mic va fi timpul de răspuns.
Formula timpului de răspuns al sistemului distribuit este următoarea:
Timp răsp = TC PU * nr_instrucțiuni + TI/O * nr_I/O + TMSG * nr_mesaje + TTR * cantitate_date

Reducerea la minimum a timpului de răspuns se realizează prin creșterea gradului de paralelism al
execuției interogării distribuite. Acest lucru nu implică neapărat faptul că v a fi minimizat și costul total.
Dimpotrivă, costul total poate crește atunci când se încearcă să crească gradul de paralelism al execuției și
transmisiei. Pe de altă parte, minimizarea costului total implică îmbunătățirea utilizării resurselor în
detriment ul timpului de răspuns care va crește. În practică, este de dorit un compromis între cele două
obiective.

Exemplu de alegere a strategiei pentru minimizare costuri

Baza de date
S ( S#, oras ) – tabela furnizori 10,000 tupl uri, stocate în site A.
P ( P#, culoare ) – tabela piese 100,000 tupl uri, stocate în site B.
SP ( S#, P# ) 1,000,000 tupl uri, stocate în site A.
Presupunem că fiecare tuplu are 100 bi ți.

Interogare : "Select S# în Bucureș ti furnizorii de piese roșii "

Estima re

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

# piese de culoare roșie = 10
# comenzi preluate de furnizorii din Bucuresti = 100,000
• Comunicații :
Viteza retelei = 10,000 biti pe secundă
Access Delay = 1 secundă
• T[i] = timpul tota l de comunicare pentru strategia i
= total access delay + volum ul total de date / viteza retelei
= (nr de mesaje * 1 sec) + ( nr total de biti transmisi / 10,000 ) sec.
Strat egia 1
1. Join S and SP la site A
2. Select am tuplurile din ( S SP ) pentru care orasul este Bucuresti
( 100,000 tupluri )
3. Pentru fiecare din aceste tupluri , verificam site -ul pentru a vewrifica daca piesa este de culoare roșie
(2 mesaje : 1 interogare , 1 răspuns )
T[1] = ( 100,000 * 2 ) * 1 = 2.3 zile
• Strategia 2
Mutam relatiile S și SP la site -ul B și procesăm intero garea la site -ul B.
T[2] = 2+(10,000+1,000,000)*100/10,000 = 28 ore

• Strategia 3

Mutăm relatia P la site -ul A si procesăm interogarea la site -ul A
T[3] =1+(100,000*100) /10,000 = 16.7 min ute
• Strategia 4
1. Selectam tuplurile din P care au culoare a roșie. (10 tupluri )
2. Verificăm site -ul A pentru a verifica dacă există o comandă referitoare la piesă către un furnizor din
București. ( 2*10 mesaje )
T[4] = 2*10*1 = 20 sec
• Strategia 5
1. Selectam tuplurile din P care au culoarea roșie. (10 tupluri)
2. Mutăm rezultatul la site-ul A si terminam interogarea la site -ul A.

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA D E AUTOMATICĂ ȘI CALCULATOARE

T[5] = 1 + ( 10*100) / 100,000 = 1.01 sec

Concluzie
Având în vedere rezultatele de mai sus obse rvăm că î n sistemele distribuite este foarte importantă
strateg ia de prelucrare a datelor, optimizarea are un rol foarte important, deoarece alegând o strategie
greșită performanțele sistemului distribuit pot fi mai slabe decat cele ale unui sistem clasic.

7. Bibliografie

1. Note de curs – profesor Alexandru Boicea
2. Note d e curs – profesor Florin Rădulescu
3. Distribute Query Processing – Wei-Pang Yang , Information Managemen t
4. Dollinger, R. – Baze de date și gestiunea tranzacțiilor, E ditura Albastră, 1998.
5. Lungu, I., Bodea, C., Bădescu, G., Ioniță, C. – Baze de date – organizare, proiectare și
implementare, Editura All Educational, 1995.
6. Lungu, I., Velicanu, M., Badea, C., Ioniță, C. – Sisteme de gestiune a bazelor de date, Editura ALL,
1998.
7. Popescu, I. – Modelarea bazelor de date, Editura Tehnică, 2001.
8. Popescu, I. − Baze de date relaționale, Editura Universității din București, 1996.