Interogarea In Bazele de Date Relationale

1. INTRODUCERE

Lucrarea de față prezintă caracteristicile de bază ale modelului de date relațional, componentele acestui model, precum și o scurtă evaluare a complexității diferitelor operații ce se pot executa asupra unui model relațional.

Alegerea acestei lucrări are la bază faptul că acest tip de model de bază de date este încă foarte răspândit în sistemele de baze de date existente. Lucrarea este structurată pe mai multe subcapitole. Primul capitol se ocupă cu descrierea modelului de date relațional, prin descrierea componentelor sale și a operațiilor ce se pot executa asupra acestora.

Al doilea subcapitol conține explicate câteva principii de evaluare a unor cereri într-o bază de date. În cel de-al treilea subcapitol sunt prezentate structuri de date care simplifică într-o mare măsură accesul la informațiile dintr-o bază de date.

Ultimele două subcapitole se ocupă cu evaluarea efectivă a diferitelor operații care se pot executa asupra unei baze de date și cu estimare costului acestor operații, ca și cu estimarea costurilor diferiților algoritmi folosiți pentru simplificarea unor procesări de cereri.

2. MODELUL DE DATE RELAȚIONALE

Componentele modelului relațional sunt:

1. Structura relațională a datelor. Aceasta înseamnă că, în bazele de date relaționale, datele sunt organizate sub forma unor tablouri bidimensionale (tabele) de date, numite relații. Asocierile dintre relații se reprezintă explicit prin atribute de legătură. Aceste atribute figurează într-una din relațiile implicate în asociere (de regulă, în cazul legăturilor de tip “unu la mulți”) sau sunt plasate într-o relație distinctă, construită special pentru exprimarea legăturilor între relații (în cazul legăturilor de tip “mulți la mulți”). O bază de date relațională (BDR) reprezintă un ansamblu de relații, prin care se reprezintă atât datele cât și legăturile dintre date.

2. Operatorii modelului relațional. Aceștia definesc operațiile care se pot executa asupra relațiilor, în scopul realizării funcțiilor de prelucrare asupra bazei de date, respectiv consultarea, inserarea, modificarea și ștergerea datelor.

3. Restricțiile de integritate ale modelului relațional. Permit definirea stărilor coerente ale bazei de date.

În comparație cu modelele ierarhice și în rețea, modelul relațional prezintă o serie de avantaje, precum:

Asigurarea unui grad sporit de independență a programelor de aplicație față de modul de reprezentare internă a datelor și metodele de acces la date. În precizarea prelucrărilor asupra datelor, programele de aplicație nu fac apel la pointeri, fișiere inverse sau alte elemente ale schemei interne a bazei de date. În ceea ce privește independența logică, aceasta nu este complet rezolvată nici cu ajutorul modelului relațional. O deficiență a modelului relațional este aceea că nu permite modelarea comportamentului dinamic al datelor, ceea ce face ca o mare parte din semantica aplicațiilor să fie codificată în programe și nu în schema conceptuală a bazei de date.

Furnizarea unor metode și tehnici eficiente de control a coerenței redundanței datelor, cu o bună fundamentare teoretică. Modificările pe care le suferă în timp datele ridică probleme serioase la întreținerea bazei de date, în ceea ce privește controlul actualizărilor, reflectarea modificărilor din structura mediului economic real în structura datelor etc. Modelul relațional, prin tehnica normalizării relațiilor permite definirea unei structuri conceptuale optime a datelor, prin care se minimizează riscurile de eroare la actualizare, reducându-se redundanța datelor.

Oferirea unor facilități multiple de definire și manipulare a datelor. În primul rând, modelul relațional oferă posibilitatea utilizării unor limbaje procedurale, bazate pe algebra relațională, precum și a unor limbaje neprocedurale având la bază calculul relațional. Limbajele neprocedurale (declarative) contribuie la îmbunătățirea semnificativă a comunicării dintre sistem și utilizatorii neinformaticieni. În al doilea rând, manipularea datelor se realizează la nivel de ansamblu (relație), fiind posibilă utilizarea paralelismului în prelucrarea datelor.

Ameliorarea integrității și confidențialității datelor. Modelul relațional realizează acest lucru prin mecanisme flexibile și eficace de specificare și utilizare a restricțiilor de integritate și a relațiilor virtuale.

Structura relațională a datelor

Pentru a defini structura relațională a datelor trebuie să definim noțiunile de: domeniu, relație, atribut și schemă a unei relații.

Domeniu

Domeniul reprezintă un ansamblu de valori, caracterizat printr-un nume. Un domeniu se poate defini explicit, prin enumerarea tuturor valorilor aparținând acestuia sau implicit, prin precizarea proprietăților pe care le au valorile domeniului respectiv.

Spre exemplu să consideră următoarele domenii D1, D2, D3, definite astfel:

D1 : {“F”,”M”}

D2 :

D3 : {s | s = șir de caractere }

Domeniul D1 este definit explicit în timp ce domeniile D2 și D3 sunt definite implicit.

Pentru un ansamblu de domenii D1, D2, …, Dn produsul cartezian al acestora reprezintă ansamblul tuplurilor <v1, v2, …, vn>, unde vi este o valoare aparținând domeniului Di. De exemplu, tuplurile <”Maria”, “F”, 45>, <”Vasile”, “M”, 24> aparțin produsului cartezian: D3xD1xD2.

Relație

Relația reprezintă un subansamblu al produsului cartezian al mai multor domenii, subansamblu caracterizat printr-un nume și care conține tupluri cu semnificație. Considerând, de exemplu că pentru produsul cartezian definit mai sus se cunosc doar două persoane, definim relația R prin tuplurile care descriu aceste persoane:

R : {<”Maria”, “F”, 20>, <”Vasile”, “M”, 22>}

Într-o relație, tuplurile trebuie să fie distincte (nu se admit duplicări ale tuplurilor).

O reprezentare comodă a relației este tabelul bidimensional (tabela de date), în care liniile reprezintă tuplurile, iar coloanele corespund domeniilor (vezi figura).

R:

În prezentarea conceptului de relație se poate recurge la analogii cu alte concepte, extrem de bine cunoscute în domeniul prelucrării automate a datelor, precum este conceptul de fișier. Relația poate avea semnificația unui fișier, tuplul poate fi considerat drept o înregistrare, iar valorile din cadrul tuplului pot fi interpretate drept valori ale câmpurilor înregistrării.

În cadrul modelului relațional nu interesează decât relațiile finite, chiar dacă la construirea relațiilor se admit domenii infinite. Numărul tuplurilor dintr-o relație reprezintă cardinalul relației, în timp ce numărul valorilor dintr-un tuplu definește gradul relației.

Atribut

Atributul reprezintă coloana unei tabele de date, caracterizată printr-un nume. Numele coloanei (atributului) exprimă de obicei semnificația valorilor din cadrul coloanei respective.

Atributele se folosesc pentru a conferi flexibilitate datelor. Pentru a înțelege această problemă vom considera următorul exemplu. Să presupunem că pentru o persoană dispunem de următoarele date: nume, sex, vârstă și numele soțului/soției.

O posibilitate de organizare a acestor date este reprezentată de relația din figura următoare.

Relația PERS reprezintă un subansamblu al produsului cartezian:

D3xD1xD2xD3.

Semnificația valorilor din cadrul unui tuplu se stabilește în acest caz nu numai pe baza domeniului de care aparțin valorile, ci și în funcție de poziția ocupată în cadrul tuplului.

Dependența față de ordine a datelor înseamnă o reducere a flexibilității organizării datelor. Într-o organizare eficientă, flexibilă ordinea liniilor și a coloanelor din cadrul tabelei de date nu trebuie să prezinte nici o importanță.

Pentru a diferenția coloanele care conțin valori ale aceluiași domeniu și a elimina astfel dependența de poziție în cadrul tabelei se asociază fiecărei coloane cu un nume distinct, lucru care a dus la apariția noțiunii de atribut.

Prin folosirea atributelor, relația PERS poate fi prezentată într-unul din modurile menționate mai jos.

Schema unei relații

Prin schema unei relații se înțelege numele relației, urmat de lista atributelor, pentru fiecare atribut precizându-se domeniul asociat. Astfel, pentru o relație R, cu atributele A1, A2, …, An și domeniile D1, D2, …, Dm, schema relației R poate fi reprezentată într-una din formele prezentate în figura de mai jos.

R (A1:D1, A2:D2, …, An:Dm)

sau

R:

Schema unei relații se mai numește și intensia relației, ca expresie a proprietăților comune și invariante ale tuplurilor care compun relația.

Spre deosebire de intensie, extensia unei relații reprezintă ansamblul tuplurilor care compun la un moment dat relația, ansamblu care este variabil în timp.

De obicei, extensia unei relații este stocată fizic în spațiul asociat bazei de date, caz în care relația poartă numele de relație de bază. Există însă și situații în care extensia nu este memorată în baza de date. Este cazul așa-numitelor relații virtuale, cunoscute și sub numele de relații derivate sau viziuni. Relația virtuală nu este definită explicit ca relație de bază, prin ansamblul tuplurilor componente, ci implicit, pe baza altor relații, prin intermediul unei expresii relaționale. Stabilirea efectivă a tuplurilor care compun relația virtuală se realizează prin evaluarea expresiei, ori de câte ori utilizatorul invocă această relație.

Restricțiile de integritate ale modelului relațional

Restricțiile de integritate, denumite și reguli de integritate, definesc cerințele pe care trebuie să le satisfacă datele din cadrul bazei de date pentru a putea fi considerate corecte, coerente în raport cu lumea reală pe care o reflectă.

Restricțiile de integritate reprezintă principalul mod de integrare a semanticii datelor în cadrul modelului relațional al datelor, mecanismele de definire și verificare a acestor restricții reprezentând principalele instrumente pentru controlul semantic al datelor. Avantajele încorporării semanticii datelor în cadrul bazelor de date constau din posibilitatea întreținerii mai ușoare a aplicațiilor și posibilitatea implementării unor mecanisme fizice mai eficiente.

În teoria sistemelor relaționale, restricțiile de integritate sunt studiate în principal sub aspectul puterii lor de modelare și al posibilităților de verificare eficace a respectării lor. Un exemplu semnificativ îl reprezintă dependențele între date, și în primul rând dependențele funcționale. Dependențele între date, ca restricții de integritate constituie un suport teoretic solid pentru problemele de modelare informatică. În acest sens, dependențele funcționale au permis definirea conceptului de “structură relațională optimă”, stând la baza teoriei optimizării structurii relaționale a datelor, respectiv teoria normalizării relațiilor.

Restricțiile de integritate ale modelului relațional sunt următoarele:

1. Restricții de integritate minimale, obligatoriu de definit și de respectat atunci când se lucrează cu modelul relațional. Din această categorie fac parte:

restricția de unicitate a cheii;

restricția referențială;

restricția entității.

2. Alte restricții de integritate, din care fac parte:

dependențele între date;

restricțiile de comportament.

Restricțiile de integritate minimale sunt definite în raport cu noțiunea de cheie a unei relații. Cheia unei relații, R, reprezintă ansamblul minimal de atribute prin care se poate identifica în mod unic orice tuplu din R. Orice relație posedă cel puțin o cheie. La limită, cheia este constituită fie dintr-un singur atribut, fie din totalitatea atributelor din schema relației respective. Când cheia este constituită dintr-un singur atribut poartă numele de cheie simplă, iar atunci când este formată din mai multe atribute este denumită cheie compusă.

Într-o relație pot exista mai multe combinații de atribute cu proprietatea de identificare unică a tuplurilor. Se spune în acest caz că relația posedă mai mulți candidați cheie (sau mai multe chei candidate). În această situație, administratorul bazei de date va alege dintre cheiltorul bazei de date va alege dintre cheile candidate una care să servească în mod efectiv la identificarea tuplurilor și care va primi numele de cheie primară. Restul cheilor candidate vor purta numele de chei alternate.

Cheia unei relații trebuie să fie minimală, adică nici o parte a sa nu trebuie să fie la rândul ei cheie. Un grup de atribute din cadrul unei relații care conține o cheie a relației poartă numele de supercheie.

Modelarea asocierilor dintre entități impune recurgerea la conceptul de cheie externă. O cheie externă reprezintă un atribut/grup de atribute dintr-o relație R1 ale cărui/căror valori sunt definite pe același/aceleași domeniu/domenii ca și cheia primară a unei relații, R2 și care are rolul de a modela asocierea între entitățile reprezentate prin relațiile R1 și R2. În acest context, R1 este denumită relație care referă, în timp ce R2 poartă numele de relație referită.

Restricția de unicitate a cheii reprezintă restricția de integritate care impune ca într-o relație, R care are cheia K, oricare ar fi tuplurile t1 și t2 să fie satisfăcută inegalitatea: t1 (K) # t2 (K). Această inegalitate semnifică faptul că într-o relație nu pot exista două tupluri cu aceeași valoare pentru atributele cheie.

Restricția referențială (integritatea referirii) reprezintă restricția de integritate care impune ca într-o relație R1 care referă o relație R2, valorile cheii externe să figureze printre valorile cheii primare din relația R2 sau să fie valori nedefinite (“null”). R1 și R2 nu trebuie să fie neapărat distincte. Semnificația restricției de integritate a referirii este următoarea : o asociere nu poate exista decât între entități deja definite. Atunci când, într-o anumită situație, asocierea nu este aplicabilă, unul din parteneri va fi desemnat prin valoarea “null”, cu semnificația de “partener inexistent”.

Restricția entității (integritatea entității) reprezintă restricția de integritate care impune ca într-o relație atributele cheii primare să fie nenule. Unicitatea cheii impune ca la încărcarea unui tuplu, valoarea cheii să fie cunoscută, pentru a se putea verifica faptul că această valoare nu există deja încărcată (tuplul nu figurează deja în baza de date). Cu valori <null>, cheia își pierde rolul de identificator de tuplu. Restricția de integritate a entității nu se aplică cheilor externe dintr-o relație, dacă acestea nu aparțin cheii primare.

Restricțiile referitoare la dependența datelor semnifică modul în care datele depind unele de altele. Această dependență între date poate fi de mai multe tipuri și anume:

dependență funcțională; reprezintă dependența între date prin care se poate identifica un atribut/grup de atribute prin intermediul altui atribut/grup de atribute. Fiind dată o relație R, un atribut Y din R este dependent funcțional de un alt atribut X din R, dacă și numai dacă fiecare valoare a lui X are asociată o valoare precisă a lui Y.

dependență multivaloare; reprezintă acel tip de dependență între date în care un atribut/grup de atribute poate prezenta mai multe valori pentru o singură valoare a unui alt atribut/grup de atribute. Fie o relație R, în care apar atributele/grupurile de atribute:X, Y și Z. În cadrul relației R există o dependență multivaloare dacă și numai dacă mulțimea valorilor lui Y corespunzătoare unei perechi: (valoare X, valoare Z) depinde numai de valoarea lui X, nu și de valoarea lui Z;

dependență jocțiune; această restricție exprimă o dependență între date mai generală decât dependența funcțională sau dependența multivaloare. Considerând o relație R, cu schema R(X:Dx,Y:Dy,Z:Dz) pentru care nu se manifestă dependențe funcționale sau dependențe multivaloare, adică relația R se poate asimila unei chei compuse. Asupra acestei relații se formulează următoarea restricție: dacă în relația R figurează tuplurile, și atunci în R trebuie să figureze și tuplul .

Restricțiile de comportament se pot defini de către utilizator în funcție de realitatea descrisă în baza de date și pot fii:

restricții de domeniu; care impun ca valorile unui atribut dintr-o relație să se încadreze în anumite limite;

restricții temporale etc.

2.1. Limbajul de Descriere a Datelor (LDD)

LDD-ul permite definirea unor scheme sau a unor subscheme care fumizează informațiile referitoare la:

descrierea logică a bazei de date;

specificarea fișierelor de date și a legăturilor logice dintre acestea;

definirea constrângerilor de integritate;

definerea unor chei de confidențialitate și a unor proceduri de criptare;

definirea modului de indexare;

identificarea unei date prezente fizic în înregistrare.

Forma de organizare a relațiilor în cadrul algebrelor relaționale este aceea de tabel.

Fiecare tabel reprezintă o relație din baza de date. Un tabel este format din una sau mai multe coloane și una sau mai multe linii. Coloanele constitue atributele relației date, și fiecare atribut are asociat un domeniu de valori caracteristic. Liniile unui tabel reprezintă înregistrările dintr-o relație și se numesc tuplurile relației. Valorile atributelor într-un tuplu sunt atomice. Există cazuri când introducerea unor înregistrări într-un tabel conține unul sau mai multe atribute care au valori necunoscute sau neaplicabile. În acest caz, în tabel se va introduce ca valoare a atributului sau atributelor respective valoarea null.

În cadrul oricarei relații există un atribut sau un grup de atribute prin care fiecare tuplu al relației date se poate identifica în mod unic. Un astfel de atribut sau grup de atribute formează o supercheie (SUPERKEY) a relației date. Dacă toate atributele unei superchei participă la identificarea în mod unic a tuplurilor, atunci supercheia devine o cheie (KEY) a relației respective. Într-o relație trebuie să existe cel puțin o cheie. O relație poate conține două tipuri de chei:

• cheie primară (PRIMARY KEY),

• cheii secundare (CANDIDATE KEY}.

O cheie secundară a unei relații care este cheie primară într-o altă relație, diferită de prima, formează o cheie externă (FOREIGN KEY) pentru prima relație. De exemplu, fie relațiile R(A,B,C) și S(C,D,E). Dacă C este o cheie secundară pentru relația R și este cheie primară pentru relația S, atunci C este o cheie externă a relației R.

2.2 Limbajul de Manipulare a Datetor (LMD)

LMD-ul specifică modul de executare a unor operații asupra bazelor de date folosind operatorii algebrei relaționale. Operațiile ce se execută asupra unei baze de date sunt:

introducere de date;

ștergere de date;

modificarea unor date existente în bază;

căutarea unor date în bază.

Fiecare operator al algebrei relaționale poate acționa asupra unei relații dacă este un operator unar sau asupra a două relații, în cazul în care este un operator binar.

Operatorii algebrei relaționale sunt:

Selecția (SELECT);

Proiecția (PROJECT);

Produsul cartezian (PRODUCT);

Reuniunea (UNION);

Diferența de mulțimi (DIFFERENCES)

Intersecția (INTERSECT);

Compunerea (JOIN);

Diviziunea (DIVISION).

Selecția (σ).

Se notează și extrage toate tuplurile din R care verifică condiția de selecție C. Condiția de selecție este o formulă logică care poate conține nume de atribute, valori și operatori logici (and, or, not) și aritmetici (=, ≠, <, ≤, >, ≥).

2. Proiecția ()

Se notează și este o operație unară care elimină atributele din R nespecificate în AL. Aceste eliminări pot avea ca efect apariția de duplicate în rezultatul obținut la ieșire. În general, aceste duplicate sunt eliminate de către operatorul proiecție.

3. Produsul cartezian (x)

Se notează R1xR2 și are ca rezultat relația care conține toate tuplurile obținute prin concatenarea fiecărui tuplu din relația R1 cu fiecare tuplu din relația R2. Produsul cartezian stabilește o legătură pe tupluri între două relații diferite. Este o operație care generează un rezultat de dimensiune foarte mare, datorită concatenărilor de tupluri care se fac.

4. Reuniunea ()

Se notează și reprezintă mulțimea care conține toate tuplurile existente în relațiile R1 și R2. Operatorul de reuniune presupune că relațiile au aceeași aritate și că ordinea (nu numele) atributelor este aceeași.

5. Diferența de mulțimi (÷)

Se notează R1-R2 și generează mulțimea care conține toate tuplurile ce aparțin relației R1 și nu aparțin relației R2. Acest operator cere aceleași condiții impuse în cazul reuniunii.

6. Intersecție de mulțimi (∩)

Se notează R1∩R2 și generează mulțimea care conține toate tuplurile comune celor două relații R1 și R2. Se impun aceleași condiții ca și la reuniune și diferența de mulțimi.

7. Join (►◄ C)

Se notează R1 ►◄C R2 și generează mulțimea care conține toate tuplurile din R1xR2, care satisfac o condiție dată C. O condiție C poate avea o formă simplă: "R1.A op R2.B" sau o formă compusă: "R1.A op R2.B op_log R1.C op R2.A", unde op_log este unul dintre operatorii logici: and, or sau not, iar op este un operator din mulțimea (=, ≠, <, ≤, >, ≥). Comparativ cu produsul cartezian, join-ul reprezintă o alternativă mult mai eficientă pentru relaționarea tuplurilor diferitelor relații, prin punerea unei restricții pe tupluri la ieșire. Cu alte cuvinte, un tuplu din R1 este concatenat cu un tuplu din R2 numai dacă cele două tupluri satisfac condiția de join C.

Exemplu: Fie relațiile R(A,B,C) și S(D,E) date de tabelele următoare și join-ul R ►◄ C S, unde C="R.B< S.D":

Există patru tipuri de relații join. Acestea sunt: θ-join-ul, join-ul natural, semi-join-ul și join-ul extern. Noțiunile prezentate anterior se refereau la o operație de tip θ-join.

Join-ul natural combină tuplurile relațiilor R1 și R2 dacă atributele comune au valori identice.

Exemplu: Fie relațiile R(A,B,C) și S(B,C,D) date de tabele următoare asupra cărora vom efectua join-ul natural. Obținem rezultatul:

Semi-join-ul este operația care conservă atributele unei singure relații participante la operația de join. Este utilizat în general atunci când nu sunt necesare toate atributele compunerii pentru operațiile următoare.

Exemplu: Fie relațiile R(A,B,C) și S(B,C,D) date de tabelele următoare:

Join-ul extern este operația care combină tuplurile dintre două relații, astfel încât condițiile de corelare să fie satisfăcute. Tuplurile care nu satisfac aceste condiții sunt completate cu valoarea null pe atributele care nu sunt comune.

Exemplu: Fie relațiile R(A,B,C) și S(C,D) reprezentate de tabele următoare asupra cărora efectuăm join extern. Obținem rezultatul:

8. Diviziunea (÷)

Acest operator necesită ca relația care va fi divizată (the divident) să conțină toate atributele relației prin care se divide (the divisor). Fie relația R1 cu atributele (Ai, …. An, Bi, …, Bm) și relația R2 cu atributele (Bi, …, Bm). Fie T=. Atunci expresia R1÷R2 generează toate tuplurile din T care prin concatenarea cu tuplurile din R2 aparțin relației R1. Intuitiv, R1÷R2 gasește toate tuplurile din R1 legate cu fiecare tuplu din R2.

De exemplu, dacă relația R1 este Participant(SSN, Proj#), reprezentând fiecare angajat care participa la un proiect și proiectul la care lucrează, și R2 este Proiect(Proj#), reprezentând mulțimea proiectelor, atunci R1÷R2 furnizează SSN-ul corespunzător fiecărui angajat implicat într-un proiect din mulțimea proiectelor date.

Se observă că nu toți operatorii algebrei relaționale prezentați sunt independenți. Unii operatori pot fi exprimați în funcție de alți operatori. Se poate arăta că intersecția de mulțimi, diferite tipuri de join-uri și diviziunea pot fi exprimate folosind restul operatorilor.

De exemplu, join-ul natural între relațiile R1(A, B, C) și R2(B, C, D) se poate exprima folosind selecția, proiecția și produsul cartezian astfel:

R1 ►◄ R2 = .

2.3. Limbajul de interogare SQL

SQL (Structured Querry Language) este un limbaj standard pentru sistemele de gestiune a bazelor de date relaționale (SGBDR) care conține numeroase rutine și care se ocupă cu administrarea și manipularea datelor într-o baza de date. Ca limbaj de procesare de cereri, SQL-ul este un limbaj nonprocedural. În SQL o cerere trebuie să conțină trei clauze principale:

SELECT: permite interogarea unei baze de date prin specificare atributelor țintă care trebuiesc retumate;

FROM: specifică relațiile asupra cărora se face interogarea;

WHERE: precizează condițiile pe care trebuie să le îndeplinească tuplurile relațiilor pentru a fi selectate.

Putem observă că se pot asocia acestor clauze operatori din algebra relațională. SELECT poate fi asociat operatorului proiecție, FROM se poate asocia unuia sau mai multor operatori produs cartezian, iar WHERE poate fi asociat cu operatorul selecție. Diferența dintre SELECT și proiecție este aceea că SELECT nu elimina duplicatele. Pentru a fi eliminate și duplicatele din rezultat trebuie să se folosească clauza SELECT DISTINCT.

În afară de cele trei clauze principale, SQL-ul mai conține și alte clauze sau proprietați, cum ar fi:

funcții totale: MIN, MAX, AVG, SUM, COUNT, VAR, NPV;

clauze opționale: GROUP BY (clauza de grup, care reprezintă o listă de atribute care permit partiționarea tuplurilor de intrare), HAVING (clauza ce determină contiții asupra partițiilor și se referă la un grup), ORDER BY (clauza de sortare, care conține o listă de atribute în funcție de care se sortează rezultatul cererii);

subcereri imbricate (nested), care pot fi corelate sau necorelate;

subcereri asociate operatorilor ∩, u și ÷.

Se poate demonstra că, dacă o cerere poate fi transpusă într-o expresie a algebrei relaționale, atunci ea poate fi exprimata și cu ajutorul unei secvențe de tip SQL.

3. PROCESARE ȘI OPTIMIZARE DE CERERI

La lansarea unei cereri în SQL, procesorul de cereri determină mai întâi corectitudinea sintaxei cererii și localizarea relațiilor și atributelor specificate de acestea. În cazul în care cererea este acceptabilă, se generează un plan de execuție al cererii. Un plan de execuție reprezintă o secvență de pași prin care se evaluează cererea dată.

Exemplul 2.1 Fie secventa SQL:

SELECT*

FROM R, S, T

WHERE R.A>a and R.B=S.B and S.C=T.C

Această secvență poate avea următoarele două plane de execuție:

1. σA>a (R) = R1; (1). σA>a(R) = R1;

2. R1 ►◄ri.b=s.bS = R2; (2). S ►◄ s.c=t.c T = R2;

3. R2 ►◄ R2.C=T.CT; (3). R1 ►◄ R1.B=R2.B R2

Cele două planuri de execuție furnizează același rezultat. În acest caz, spunem că avem planuri de execuție echivalente.

Evaluarea planelor de execuție echivalente se face din punct de vedere al costului evaluării cererii. Scopul optimizării cererilor este acela de a determina un plan de execuție de cost minim din mulțimea planelor de execuție echivalente. Un astfel de plan se numeste plan de execuție optim.

În sistemele de baze de date centralizate, costul prelucrării unei cereri este influențat de două componente: costul operațiilor de I/O și costul prelucrării cererii de către CPU. Costul operațiilor de I/O este dat de transferul datelor din memoria principală într-o memorie secundară, deoarece majoritatea aplicațiilor asupra bazelor de date folosesc un volum mare de date care nu poate fi stocat în întregime în memorie. Costul prelucrării cererii de CPU este determinat de verificarea efectivă a tuplurilor care îndeplinesc anumite condiții asociate prelucrării.

Un plan de execuție este determinat de doi factori:

numărul de operații care compun cererea;

numărul de metode ce pot fi folosite la evaluarea fiecărei operații.

De exemplu, dacă o cerere conține m operații, și pentru fiecare operație există k moduri de evaluare, atunci numărul de planuri de execuție echivalente este aproximativ egal cu (m!)km. Mulțimea tuturor planurile de execuție formează spațiul de căutare pentru optimizarea cererilor. Din cauza numărului mare de planuri de execuție existente, găsirea unui plan optim este o problemă extrem de complicată și consumă foarte mult timp. Dacă cererea pentru care se caută planul de execuție este rar utilizată, acestă risipă de timp este inutilă. În cazul în care cererea este des folosită, atunci timpul pierdut cu căutarea unui plan de execuție optim se amortizează prin folosirea ei în mod repetat.

În general, în practică se caută stabilirea unui echilibru între timpul alocat căutării unui plan optim de execuție și timpul necesar executării acestuia.

4. CĂI DE ACCES RAPID LA DATE

Majoritatea aplicațiilor în baze de date conțin volume mari de date care trebuiesc memorate pe diferite dispozitive fizice. Există mai multe tipuri de ierarhii de memorare: memorare pe un nivel, memorare pe două nivele și memorare pe trei nivele.

• Organizarea pe un nivel. Bazele de date sunt păstrate în memoria principală obținându-se un sistem de baze de date cu memorie principală. Această obțiune este valabilă în cazul în care aplicațiile necesita un acces rapid la date.

• Organizarea pe două nivele. În acest caz, cele două nivele de memorare sunt: memoria principală și memoria secundară. O memorie secundară este reprezentată de un dispozitv de stocare fizică a datelor (hard-disk-ul de obieci). Pentru prelucrare, datele trebuiesc transferate din memoria secundară în memoria principală. Costul acestui transfer depinde de trei factori:

timpul de căutare;

timpul de întârziere la rotație;

timpul de transfer al paginii. Cea mai mare parte a timpului alocat transferului unei pagini este ocupată de timpul de căutare și de deplasare a capului de citire-scriere în poziție corectă.

Fișierele de I/O pot conține blocuri de date care pot fi accesate:

secvențial: transferul blocului de date implică timp de căutare și timp de întârziere la rotație;

aleator: transferul blocului de date nu implică timp de căutare sau de întârziere la rotație.

Este de preferabil ca fișierele de I/O să conțină cât mai puține blocuri de date cu acces aleator.

• Organizarea pe trei nivele. Acesta este un tip de organizare utilizat în special pentru baze de date cu un volum foarte mare de informații. Astfel de tipuri de baze de date nu mai pot fi stocate doar în memoria principală și pe cea secundară. În acest caz au mai fost introduse noi tipuri de medii de memorare, cum ar fi discurile optice, care vor forma un al treilea nivel de memorare. Tipuri de baze de date masive pot fi întâlnite în domeniile de cercetare (a mediului, medicale), în rețele de telecomunicații, în cadrul serviciilor de informație digitate, în exploatările spațiale, etc. Al treilea nivel de memorare este mai lent decât al doilea nivel, dar prezintă o capacitate de stocare mult mai mare.

Mai poate fi considerat și un alt tip de mediu de memorare, acela al memoriei cache, care este frecvent utilizată în cadrul sistemelor de baze de date. Memoria cache permite un acces rapid la memoria principală. Având un cost mult prea ridicat, capacitatea acesteia este mai redusă.

Pentru creșterea vitezei de accesare a informațiilor dintr-o bază de date se caută structuri de date speciale. Vom analiza în continuare două dintre acestea, și anume B+ arborii și tabelele de dispersie.

4.1. B+ arbori

Un B+ arbore este o structură frecvent utilizată în sistemele de gestiune a bazelor de date. Nodurile unui astfel de arbore pot fi de două tipuri: nod intern și nod frunză. Deosebirea între cele două noduri este aceea că un nod intern poate avea unul sau mai mulți descendenți, în timp ce un nod frunză nu are descendenți. Fiecare nod al arborelui memorează o pagină. Să presupunem că index-ul de căutare este format din A-valorile unei relații R date, adică A este o cheie de căutare. Structura generală a unui nod al B+ arborelui este (P1, a1, P2, …, ak-1, Pk), unde a1 sunt valori ale atributului A cu proprietatea a1<a2< …<ak, iar Pi sunt pointeri de legături către un nivel inferior în arbore. Valori indicate de acești pointer-i verifică proprietățile:

P1: avem ;

Pk: avem ;

pentru 2 ≤ j ≤ k-1, Pj: avem .

Orice nod intern diferit de rădăcină trebuie să fie cel puțin pe jumătate completat (să fie cel puțin jumătate de poziții posibile ocupate cu informații). Nodurile frunză ale arborelui sunt de forma (a1,P1; a2,P2;..;am,Pm;P). unde a, sunt valori ale lui A care satisfac relația a1<a2<…<am și P este un nod frunză de legatură, care indică următorul nod frunză din arbore. Aceste noduri frunză formează o listă cu legături. Nodurile frunză pot fi ordonate crescător sau descrescător. Legătura unui nod frunză către următorul nod frunză din listă constitue o cale mai rapidă de acces la tupluri, și este utilă la determinarea domeniului de exitență (range conditions), cum ar fi, de exemplu, b≤A<c. Pointerii P, pot fi descriși astfel:

1. dacă tuplurile din R sunt ordonate crescător (sau descrescător) în funcție de valorile lui A, atunci indexul B+ arborelui se numește index primar (sau clustered index). În practică, în funcție de natura implementării, fiecare Pj este fie un tuplu de legătură, indicând acele tupluri pentru care valorile lui A sunt ai, fie un pointer de pagină, indicând o pagină din R care conține acele tupluri pentru care valorile lui A sunt egale cu aj. Dacă A nu este o cheie, atunci Pi-urile sunt implementate ca pointeri de pagină. Se observă că poate există cel mult un cluster index pentru o relație, deoarece tuplurile unei relații pot fi memorate într-un singur fel la un moment de timp dat. De exemplu, presupunând că avem un index primar pentru atributul A și un alt index primar pentru atributul B, asta înseamnă că tuplurile relației R trebuiesc sortate crescător după valorile lui A și sortate descrescător după valorile lui B în același timp, ceea ce în practică este imposibil.

2. dacă tuplurile relației nu sunt sortate crescător (sau descrescător) în funcție de valorile lui A, atunci indexul B+ aborelui se numește index secundar (sau nonclustered index). În aceste condiții putem avea două cazuri:

(a) A este o cheie, și atunci pi este un tuplu de legătură, indicând acele tupluri pentru care A are valoarea ai.

(b) A nu este cheie. În acest caz, cea mai comună implementare este aceea în care pi pointează către un bloc N care conține legături spre tuplurile care conțin A-valoarea ai. În acest fel crește numărul de indirectări deoarece N nu conține în mod direct tuplurile respective. Astfel P, devine un tuplu de legătură către acele tupluri care au A-valoarea egală cu ai, iar condiția ai < a2<…<am din frunze este înlocuită cu condiția ai ≤ az ≤ -am.

Fie T un pointer către rădăcina B+ arborelui. Algoritmul de căutare al unui tuplu după o A-valoare egală cu a este următorul:

1. Dacă T este un nod intern, atunci se compara A-valoarea cu valoarea dată a și se determină legătura către un nivel inferior în arbore

pentru a < a1, se va face search(a,P1);

pentru ai-1 <a<ai, se va face search(a,Pi), 1 < i ≤ k-1;

pentru a > ak-1, se va face search(a,Pk).

Căutarea se termină când întreg arborele este parcurs. Pentru creșterea vitezei de căutare se poate folosi un algoritm de căutare binară.

2. Dacă T este un nod frunză, atunci a se compară cu toate A-valorile din T. Dacă nici o A-valoare nu este egală cu a, atunci vom avea o căutare fără succes, iar rezultatul va fi "not found". Dacă există o A-valoare egală cu a, fie aceasta ai, atunci pentru a obține toate tuplurile care conțin această valoare se va avansa în direcția pointerului Pi.

Performanța algoritmulul de căutare este strâns legată de înălțimea B+ arborelui. Dacă n este numărul A-valorilor distincte în R, atunci înălțimea B+ arborelui asociat este logFn, unde F este numărul mediu de descendenți ai unui nod intern. Operațiile de inserare și stergere dintr-un astfel de arbore sunt foarte complicate, aceasta constituind un dezavantaj al acestor structuri.

4.2 Dispersie

Dispersia este o altă metodă des utilizată în accesarea tuplurilor dorite dintr-o relație. Principiul constă din construirea unei tabele de dispersie (hashing table) care să conțină un indice de intrare pentru fiecare tuplu al relației și folosirea unei funcții de dispersie h() pentru identificarea rapidă a intrărilor în tabela de dispersie. Orice tabelă de dispersie este constituită din mai multe locații (buckets). De obicei, numărul acestor locații este determinat în avans de numărul de tupluri al unei relații. Fiecare locație corespunde uneia sau mai multor pagini de disk. Să presupunem că A este atributul unei relații folosit pentru obținerea unui acces rapid la date. Conținutul fiecărei locații este un număr al indicilor de intrare de forma (a,P), unde a este A-valoarea unui tuplu oarecare și P este un tuplu cu legături, ce indică tuplurile pe disk. 0 funcție de dispersie h() este folosită la atribuirea unui număr n fiecarei A-valori a relației; n se numește număr de locație (buckets number).

În general, locațiile sunt numerotate de la 0 la n-1, unde n este numărul de locații folosite. Funcția de dispersie este astfel construită încât să atribuie un întreg între 0 și n-1 oricărei valori valide a lui A. De exemplu, dacă A ia valori negative, atunci funcția h(x)=x mod n – care furnizează restul împărțirii lui x la n – este o astfel de funcție de dispersie.

Fie t un tuplu și a o A-valoare a lui t. Dacă h(a)=k, 0<=k<=n-1, atunci intrarea (a,P) este poziționată în a k-a locație a tabelei de dispersie. După crearea și poziționarea corectă a fiecărei intrări corespunzătoare fiecarui tuplu al relației, costrucția tabelei de dispersie este încheiată. Este posibil ca prea multe A-valori să primească o aceeași locație și să nu poată fi păstrate toate intrarile; un astfel de caz se numeste depașirea locației (bucket overflow). Prin alegerea cu atenție a unei funcții de dispersie se pot evita aceste tipuri de aglomerări, prin distribuirea echilibrată a A-valorilor în locațiile tabelei de dispersie. 0 altă metodă de rezolvare a problemei este aceea de folosire a unor locații de depășire pentru intrările care depășesc spațiul alocat locațiilor obișnuite și sunt legate de acestea printr-o legătură de tip pointer.

5. PROCESAREA PARALELĂ A CERERILOR RELAȚIONALE

5.1. Elemente de bază ale procesării paralele

Într-un sistem cu procesare paralelă de baze de date, resursele principale sunt procesoarele, modulele de memorie și discurile (depozite secundare de date). În funcție de modul de interacțiune a acestor resurse, sistemele pot avea diverse arhitecturi multiprocesor.

5.1.1. Arhitecturi multiprocesor

Arhitectura cu distribuirea memoriei

Orice procesor poate accesa direct o memorie comună și orice disc din sistem. Din acest motiv, arhitectura cu distribuirea memoriei se mai numește și arhitectură cu distribuire totală. Sincronizarea procesoarelor se realizează prin intermediul memoriei comune, la fel și echilibrarea sarcinilor. Problema principală care intervine se referă la volumul mare de date ce trebuiesc tratate de rețea, cauzat de accesul frecvent la discuri și la memoria comună. Cu cât numărul procesoarelor crește, cu atât problema devine mai complexă.

P1, …, Pn = procesoare

M = memoria principală

HDD = hard-disck

Arhitectura cu distribuirea discurilor

În acest caz fiecare procesor are o memorie proprie, pe care o accesează doar acel procesor; în schimb orice procesor poate accesa orice disc din sistem. Memoria proprie oferă avantajul micșorării numărului (dimensiunii) datelor care circula în rețea, dar sincronizarea procesoarelor nu se mai face prin intermediul memoriei.

Arhitectura fără distribuire

În acest caz fiecare procesor are o memorie și unități de hard-disck proprii, la care are acces unic. Schimbul de informații între noduri se realizează prin intermediul rețelei, interfețele între procesoare fiind astfel minimalizate. Avantajele acestei arhitecturi constau în viteza și corespondența aproape liniare, adică: având de n ori mai multe procesoare se poate reduce de n ori timpul estimat realizării unei sarcini și se poate îndeplini o sarcină de n ori mai mare în același timp. Problema care apare constă în echilibrarea încărcăturii de date între noduri pentru a minimiza timpul de răspuns.

Cea mai mare căutare (și din punct de vedere comercial), o are arhitectura fără distribuire.

5.1.2. Procesarea paralelă a cererilor relaționale

În ceea ce privește bazele de date, paralelismul poate fi obținut la diferite nivele. La nivel de sistem, cererile concurente pot fi executate de mai multe procesoare în paralel, micșorându-se astfel timpul de trecere prin sistem. La acest nivel există deci paralelism intercereri. De asemenea, operațiile care compun o cerere relațională pot fi executate de către diverse procesoare în paralel; avem de-a face cu paralelism interoperație. La nivelul următor, aceeași operație poate fi procesată în paralel în mai multe noduri, rezultând astfel paralelism de tip intraoperație.

Există câteva mecanisme de bază în vederea obținerii paralelismului, și anume:

Paralelismul independent

Acest mecanism este valabil în cazul paralelismului interoperații. Mai multe operații ale aceleiași cereri pot fi procesate independent în paralel.

Exemplu : Pentru o cerere de tipul R1 ►◄C R2 ►◄C R3 ►◄C R4 se pot executa în paralel join-urile R1 ►◄C R2 și R3 ►◄C R4.

Paralelism înlănțuit

Acest mecanism este de asemenea valabil pentru paralelismul interoperații.

În cazul în care trebuiesc executate două operații astfel încât rezultatul uneia reprezintă intrarea celeilalte, cea de-a două operație nu se mai execută după completa procesare a primei. Mecanismul de paralelism înlănțuit constă în generarea unor rezultate parțiale ale unei operații, rezultate ce vor reprezenta datele de intrare pentru o altă operație. Cea de-a două operație se va executa astfel în paralel cu prima (care nu a returnat toate rezultatele).

Paralelism partiționat

În cazul în care datele de intrare, pentru o operație, au dimensiuni mari, se pot împărți în submulțimi. Submulțimile obținute sunt trimise la procesoare diferite, unde se execută operația dată, având ca intrări datele din submulțimea corespunzătoare. Procesoarele execută în paralel aceeași operație, iar la final se unesc rezultatele. În acest caz avem de-a face cu paralelism intraoperație.

În general toate mecanismele prezentate se utilizează combinate pentru obținerea rezultatelor și perfomanțelor dorite.

5.2. Tehnici de partiționare a datelor

Într-un sistem paralel de baze de date există mai multe procesoare și discuri. Problema care se pune este modul în care trebuie împărțită cererea relaționala în subcereri care să fie executate în paralel.

Problema se poate enunta astfel : Pentru o relație R data și n noduri Pi, , relația R se împarte în n fragmente astfel încât toate fragmentele să aibă aproximativ aceeași dimensiune și fiecare să poată suporta operațiile așteptate în relație.

În continuare sunt prezentate o serei de modalități de partiționare.

5.2.1. Partiționarea Round-Robin

Este vorba de cea mai simplă împărțire a datelor: tuplul k al relației R se distribute nodului P((k-i)mod n)+1.

Exemplu: R = SALARIAT; n = 2 .

Principalul avantaj al schemei este împărțirea relației inițiale în fragmente de aceeași dimensiune, mai puțin ultima rotunjire care poate să nu conțină n tupluri. Acest tip de partiționare este bun pentru cererile relaționale care privesc intreaga relație (de exemplu: "select * from R").

Dar dacă, de exemplu, se doresc acele tupluri ale relației R care satisfac o anumită condiție C, trebuie accesate toate fragmentele relației (în fiecare putându-se afla un tuplu dorit). Indexarea relației nu este o soluție. Schema este dezavantajată și dacă se dorește, de exemplu, R ►◄C S, R și S partiționate Round-Robin. În acest caz trebuie să se execute operația de join între fiecare dintre fragmentele relației R cu toate fragmentele relației S, ceea ce duce la un trafic mare în rețea.

5.2.2. Partiționarea după domeniu

Se partiționează o relație R dată, după un anume atribut A. Metoda de partiționare constă în două etape, și anume:

a) împărțirea domeniului de valori al atributului A în subdomenii (câte un subdomeniu pentru fiecare nod);

b) distribuirea tuplurilor relației la nodurile sistemului, fiecare tuplu ajungând în nodul asociat subdomeniului căruia îi aparține. Exemplu : Împărțim relația R = SALARIAT după valorile atributului A = vechime (n = 6). Se obține : P1 subdomeniu 0-5; Pz subdomeniu 6-10;…; P@ subdomeniu 25-30.

Partiționare după domeniu acoperă problemele partiției Round-Robin. Dezavantajul său îl constă faptul că nu se garantează că toate fragmentele au aceeași dimensiune (dacă se alege prost atributul de partiționare se poate ca un fragment să conțină întreaga relație).

Modelul se poate îmbunătăți alegând domenii de lungimi diferite pentru valorile atributului A, în urma analizării relației.

Această schemă de partiționare este utilizată în cele mai multe sisteme pentru împărțirea orizontală a unei relații (împărțirea în fragmente care conțin tuplurile relației).

5.2.3. Partiționarea Hash

Partiționarea Hash se bazează pe aplicarea unei funcții (numita funcție hash) valorilor unui atribut al relației date. Domeniul funcției hash este împărțit în n subdomenii, fiecare fiind asociat cu un nod. Un caz particular constă în alegerea funcției hash astfel încât subdomeniile să conțină o singură valoare (se realizează join eficient). Tuplul t se distribuie nodului i dacă h(at) subdomeniului i, unde h = funcția hash.

Exemplu: h(x) = (x • 10) mod 5 +1, x valorilor atributului vechime;

R = SALARIAT; n=5 noduri.

Se observă că partiționare Round-Robin și cea după domeniu sunt cazuri particulare ale partiționării Hash: pentru Round-Robin h(x) = ((x – 1) mod n) + 1, x = indexul (atribultui identitate); pentru partiționarea după domeniu h(x) = x, funcția identitate.

5.2.4. Probleme legate de partiționarea datelor

Se pune problema când anume trebuie partiționată o relație și în câte fragmente. Intuitiv am fi dispuși să credem că, odată cu mărirea numărului de fragmente, scade timpul de răspuns. Nu este însă întotdeauna adevărat, deoarece : având mai multe fragmente, unirea rezultatelor, în vederea obținerii rezultatului final, necesită un timp și un cost mai mare. De asemenea, având fragmente de dimensiuni foarte mici nu se justifică costurile inițializării proceselor care utilizează acele fragmente.

0 altă problemă, legată de partiționarea datelor, constă în distribuirea tuplurilor relației inițiale astfel încât datele să fie încărcate în noduri în mod echilibrat (chiar și în cazul datelor nesimetrice). Chiar dacă se rezolvă această problemă, nu se garantează același timp de răspuns al procesoarelor, în primul rând deoarece unele tupluri ale relației pot fi utilizate mai des decât altele.

0 strategie pentru echilibrarea datelor în noduri constă în :

• Partiționarea în multe fragmente (mai multe decât numărul nodurilor) a relației care intră în componența sarcinilor sau cererilor relaționale.

• Sortarea sarcinilor în ordine descrescătoare a timpului de execuție estimat.

• Distribuirea optima a sarcinilor la procesoare : sarcina cea mai mare distribuita procesorului care se asteapta să termine primul. Distribuirea se poate face static (alocare înainte de procesăre) sau dinamic (o noua sarcina se distribuie unui procesor, numai după ce acesta a terminat de efectuat sarcina ce i se încredințase anterior).

Altă strategie de echilibrare a datelor ar putea avea la bază utilizarea frecvenței de acces a tuplurilor unei relații, astfel încât relația să fie partiționata în sensul accesării, cu aproximativ aceeași frecvență, a fragmentelor rezultate.

5.3. Algoritmi de sortare paralelă

Sortarea tuplurilor unei relații este o operație frecvent cerută în cererile relaționale (de exemplu prin clauza "order by" sau în apelul funcțiilor: "average", "minimum", "count"). Deseori se utilizează sortarea pentru eliminarea duplicatelor ("select distinct", "union"), iar unii algoritmi de join se bazează pe sortare. Aceasta operație este costisitoare din punct de vedere al timpului (0(n log n) pentru sortarea a n articole în memorie), de aceea se impune găsirea unor algoritmi paraleli de sortare.

După numărul de grupuri de date de intrare și de ieșire, algoritmii de sortare în paralel se clasifică în algoritmi de tipul:

• one-to-one : datele de intrare provin de la un singur nod (nu au fost partiționate), iar cele de ieșire sunt depozitate într-un singur nod (nu trebuie partiționate pentru o nouă operație <=> pas final) în procesarea unei cereri.

• one-to-many;

• many-to-one;

• many-to-many.

0 problemă importantă care intervine în cazul sortării sarcinilor, o constituie numărul de procesoare care trebuie utilizat. Un număr mare de procesoare are avantajul că sortarea se execută în întregime în memoria atașată procesoarelor (fragmente multe => dimensiuni mici) și dezavantajul că în realitate nu se dispune de foarte multe procesoare, iar traficul în rețea ar fi prea mare. În cazul utilizării unui singur procesor s-ar ajunge la o sortare externă și nu în paralel, iar timpul de răspuns ar fi redus. În realitate se utilizează un număr fix de procesoare, chiar dacă la un moment dat ar fi nevoie de o sortare externă.

În continuare sunt prezentați câțiva algortimi paraleli de sortare:

5.3.1. Parallel binary merge sort (sortare paralelă cu fuziune binară)

Acest algoritm este de tip many-to-one și constă în două etape:

• Etapa 1 : Sortarea în paralel a tuturor fragmentelor relației, aflate în noduri, utilizând un algoritm de sortare centralizat (de exemplu quicksort).

• Etapa 2 : Perechi de fragmente sortate se unesc prin distribuirea fragmentelor de la un nod la altul.

Se repetă procesul până la obținerea rezultatului final. Între pași se poate realiza paralelismul înlănțuit.

Exemplu:

P1: 3,5

P2:1,7 P1:1,3,5,7

P3:1,9 P1:1,1,1,2,3,5,7,9

P4:2,3 P3:1,2,3,9

5.3.2. Block bitonic sort (sortarea în bloc)

Algoritmul este de tip many-to-many. Etapele de realizare:

• Etapa Sort-Split-Ship (sortare-împărțire-expediere): Se sortează fragmentele în fiecare procesor. Fragmentele astfel obținute se împart în două părți așa încât orice valoare din primul subfragment (L – lower) este mai mică sau egală decât orice valoare din al doilea subfragment (H -higher). Etapa se realizează în paralel, cu participarea tuturor procesoarelor. Fiecare subfragment se expediază către un alt sau același procesor.

• Etapa Two-Way Merge Split (unire-separare) : când două fragmente ajung într-un procesor, se unesc pentru sortare, iar apoi se separă din nou pentru repetarea procesului. În final, orice valoare aflată în procesorul Pi va fi mai mică sau cel mult egală cu orice valoare din procesorul Pj, unde i<j.

La fiecare pas în fiecare procesor se vor afla două subfragmente de relație.

Exemplu:presupunem că trebuie sortate șaisprezece numere utilizând patru procesoare. Inițial, numerele sunt împărțite în patru fragmente care sunt atribuite procesoarelor. La primul pas, numerele din fiecare preocesor sunt sortate și apoi împărțite în două subfragmente (lower și higher). Fiecare subfragment este atribuit unui procesor determinat în prealabil. Se repeta pașii până când sortarea este completa. După șase pași cele șaisprezece numere sunt sortate.

5.3.3 NOW Sort ("Network of Workstation")

Acest algoritm se aplică în sistemele paralele cu arhitectura fără distribuire. Rezultatul sortării se depozitează în mai multe procesoare.

Varianta "sortare NOW într-un pas" constă în citirea fiecărui tuplu al relației o singură dată dintr-un depozit secundar (disc) în memoria principală. Pentru aceasta trebuie ca suma dimensiunilor memoriilor principale să fie destul de mare pentru a păstra toate tuplurile relației în vederea sortării.

Etapele algoritmului:

• Etapa Citire : fiecare procesor citește tupluri de pe discul local în memoria principală. Această etapă se execută în paralel de către toate procesoarele.

• Etapa Distribuire : după citirea în memorie, tuplurile se distribuie procesoarelor (stațiilor de lucru) în funcție de valorile cheilor, adică : având p procesoare, numerotate de la 0 la p-1, atunci cei mai semnificativi log2(p) biți ai valorii cheii sunt utilizați pentru determinarea destinației tuplului respectiv. Adică, dacă i reprezintă valoare corespunzătoare celor mai semnificativi log2(p) biți ai cheii unui tuplu, acesta se trimite procesorului i (0 < i < p-1). Când un tuplu ajunge în procesor, se formează perechea (pk, pt), unde: pk = valorea cheii pentru tuplul respectiv (de dimensiune 4 bytes), iar pt = pointer la tuplu. Perechea (pk, pt) se distribuie unei memorii locale de 2b buckets, astfel încât valoarea celor mai semnificativi log2(p)+1 și log2(p)+b biți să fie aceeași. Se repetă pentru toate tuplurile din procesoare.

• Etapa Sortare : fiecare procesor utilizează un algoritm pentru sortarea locală a bucket-urilor (pe rând). Etapa se realizează în paralel.

• Etapa Scriere : la fiecare procesor, pointerii din perechile sortate sunt utilizați pentru adunarea tuplurilor (se începe cu bucket-ul având cel mai mic string binar). Tuplurile ale căror valori, pentru cei mai semnificativi log2(p)+b+32 biti ai cheii, sunt egale și se sortează după biții rămași. După

Exemplu :Considerăm relațiile:

S: cod nume R: cod profesie

001 Ion 003 doctor 002 profesor

003 Popa 001 inginer 004 actor

004 Albu 005 dulgher

Presupunem ca relația S (cea mai mică) a fost partiționată și trimisă la procesoare (n = 2 procesoare), și a fost și sortată în interiorul procesoarelor:

P1 : 001 Ion

003 Popa

P2: 004 Albu

Relația R se trimite pagină cu pagină procesoarelor; în procesoare se realizează join-ul:

P1 : 001 Ion inginer

003 Popa doctor

p2 : 004 Albu actor

Rezultatul se obține într-unul dintre cele două procesoare :

P1 : 001 Ion inginer

003 Popa doctor

004 Albu actor

5.3.4. Sort Merge Join

Într-o bază de date centralizată, algoritmul "sort merge join" constă în doi pași ce trebuiesc efectuați : sortarea relațiilor inițiale, după atributul de join, și unirea, după acel atribut, a relațiilor sortate. O modalitate de a paraleliza acest algoritm este de a aplica un algoritm de sortare,

i) Dacă relația internă a fost partiționată și distribută procesoarelor și a fost și indexată după atributul A pe fiecare fragment, atunci se aleg pentru join procesoarele din nodurile conținând fragmentele relației interne. Acest lucru se face deoarece indexul nu mai poate fi utilizat după realocarea datelor.

Relația externă se emite tuturor procesoarelor, pagină cu pagină, în paralel. Când o pagină ajunge într-un nod, se realizează join-ul cu fragmentul relației interne aflat în acel nod. Se pot emite mai multe pagini o dată, dar trebuie să rămână disponibile în memorie k+2 pagini (k = numărul nivelelor în arborele de indexare, o pagina pentru relația internă și o alta pentru păstrarea rezultatului).

ii) În cazul în care cerințele anterioare nu sunt valabile;

ii1) Dacă relația externă a fost partiționată și distribuită, se aleg ca procesoare pentru join, acelea care conțin fragmente ale relației exteme. La fiecare procesor se citesc în memorie primele m-2 pagini ale relației externe, în paralel.

ii2) Se partiționează relația externă în n fragmente disjuncte și se distribuie celor n noduri, care devin noduri pentru join.

Relația internă se emite tuturor procesoarelor (în paralel), pagină cu pagină (chiar dacă a fost partiționată și distribuită). Ajunsă în procesor, o pagină se unește (join) cu cele m-2 pagini din memorie (în memorie rămâne o pagină care este utilizată pentru depozitarea rezultatului). La fel se procedează și cu paginile relației interne care au rămas de procesat.

• Etapa 3 : Dacă se dorește rezultatul într-un singur nod, atunci trebuie asamblate rezultatele parțiale.

5.4. Procesarea paralela a join-urilor

Cei mai mulți algoritmi paraleli pentru join sunt derivați din algoritmii de bază, și anume: nested loop join, sort merge join și hash join. În continuare vom presupune că se dorește realizarea join-ului R ►◄ C S (după atributul A), unde S este relația mai mică (nu se pierde din generalitate).

5.4.1. Nested Loop Join

Putem considera că fiecare procesor are o memorie locală cu m pagini valabile (libere). Etapele algoritmului sunt următoarele :

• Etapa 1 : alegerea relației externe (relația care va utiliza cât mai multe pagini din memorie). Fiecare tuplu al acestei relații va fi cercetat pentru a vedea dacă se potrivește cu vreun tuplu al relației interne. R se alege ca relație externă doar în cazurile:

R și S sunt partiționate și distribute procesoarelor, iar S este indexată după atributul A (pentru toate fragmentele) și R nu este indexată.

ii) R este partitionata și distribuita procesoarelor, iar S nu. În toate celelalte cazuri se alege S ca relație externă.

• Etapa 2 : alegerea procesoarelor în care se va realiza join-ul și îndeplinirea acestei operații.

Sortare, tuplurile se scriu pe disc. Motivul de formare a perechilor (pk, pt) este de a reduce timpul de sortare. Pentru sortarea în memorie se poate utiliza un algoritm de tip rădăcina partială.

Se utilizează paralelismul partiționat (între procesoare) și paralelismul înlănțuit (între operațiile efectuate de același procesor).

Procesarea Paralelă a Selecțiilor și Proiecțiilor

În general, selecțiile și proiecțiile pentru o aceeași relație se execută în același timp. Se poate astfel considera o singură operație, numită reducere, care întoarce un set de subtupluri ale tuplurilor relației inițiale, satisfăcând o anumită condiție.

Fie R relația care se supune reducerii. În paralel, în fiecare nod al sistemului, se reduc fragmentele relației R (în mod obișnuit, ca într-un sistem centralizat, și anume: secvențial sau utilizând o funcție de acces determinată de condiția impusă prin reducere). Dacă se permit și dubluri, nu mai rămzne decât de unit rezultatele obținute. În cazul în care dublurile nu sunt admise (de exemplu: "select distinct), eliminarea duplicatelor se poate face după o sortare prealabilă sau chiar în momentul sortării.

Exemplu : Pi, procesoare; Ri = fragment al relației R; Ri se trimite procesorului. Apoi se emite Rn tuturor celorlalte procesoare în paralel și se elimină duplicatele care apar. Rezultă de aici relațiile R11,…,Rn-i1. Rn nu trebuie păstrat decât în primul procesor. Se repetă operația pornind cu Rn-i1 și așa mai departe, până la obținerea rezultatului final: procesorul Pi conține fragmentele sortate și fără duplicate R1n, R21,…,R2n-1 (unirea acestora conduce la rezultatul final).

5.4.2. Simple Hash Join

Se presupune că relațiile implicate (R, S) nu au fost încă partiționate (altfel se repartiționează). Etapele algoritmului:

• Etapa 1 : Se partiționează S utilizând o funcție hash hi bazată pe valorile atributului A, iar Si se trimite procesorului P,.

• Etapa 2 : La fiecare procesor Pi se creează o tabelă de partiție Ti, utilizând o funcție h2i (bazată pe atributul A). Tuplurile care au aceeași valoare pentru h2i(a) sunt amplasate în același bucket, iar cele cu valori diferite în bucket-uri diferite. Acest lucu se face în paralel de către toate procesoarele.

• Etapa 3 : se partiționează și se distribuie relația R, utilizând funcția hi.

• Etapa 4 : la fiecare procesor Pi (în paralel) se cerceteaza Ri și apoi (utilizând funcția h2i) se verifică tabela Ti pentru a vedea dacă fragmentele relației Ri se potrivesc cu tuplurile lui Si.

Pentru algoritmul prezentat anterior s-a presupus ca tabelele de partiționare au loc pentru a fi păstrate în memorie. În cazul depășirii capacității memoriei, trebuie urmată strategia : înainte de construirea tabelei de partiționare se calculează dimensiunea sa pe baza datelor existente. Dacă dimensiunea sa este mai mare decât capacitatea memoriei, se alege un domeniu de valori astfel încât tabela pentru tuplurile care aparțin domeniului (din punct de vedere al valorilor atributului A) să poată fi pastrată în memorie. Se construiește tabela pentru tuplurile respective, iar restui tuplurilor vor forma o relație temporară. Se aplică algoritmul pentru relația temporară, iar apoi se reia (cu două relații mai mici), până la obținerea rezultatului final.

Exemplu:

Fie relațiile următoare:

Relația R Relația S

Presupunem ca relația S a fost partiționată în S1 și S2:

Fragmentul sortat S1 Fragmentul sortat S2

Se utilizează funcția h(x) = x mod 3 pentru a creea tabelele hash:

Fragmentele relației R:

R1 R2

sunt utilizate pentru realizarea join-ului (după ce au fost create tabelele hash).

Rezultatul după realizarea join-urilor Ri ►◄C Si:

5.4.3. GRACE Hash Join

Prin acest algoritm se încearcă prevenirea (nu rezolvarea) depășirilor capacității memoriei. Etapele algoritmului sunt:

• Etapa 1 (de generare a fragmentelor):

i) Se partiționează S în N fragmente cu ajutorul funcției hi, alegând N suficient de mare, astfel încât dimensiunea oricărui fragment Și să fie mai mică decât capacitatea totală a memoriilor procesoarelor. Se distribuie S,, K i :< N, pe unul sau mai multe discuri.

ii) Se partiționează R (Ri,) cu funcția hi și se depozitează undeva (nu contează unde). Evident Ri ►◄C Sj=, .

• Etapa 2 (de unire a fragmentelor):

Fiecare join Ri ►◄C Sj se procesează independent (), utilizând spre exemplu algoritmul "Simple Hash Join" (fără overflow).

Nu se poate totuși garanta evitarea totală a depășirii capacității memoriei, orice funcție hi am alege, datorită neregularității datelor. Dacă N este foarte mare, fragmentele Si vor fi foarte mici și nu se justifica începerea join-ului cu date de intrare puține (algoritmul nu va fi eficient).

5.4.4. Hybrid Hash Join

Acest algoritm încearcă să unească cele două etape din algoritmul GRACE Hash Join, pentru reducerea traficului în rețea (scriere, citire de pe discuri). Când se partiționează relația S, se distribuie tuplurile lui S aparținând primului fragment, imediat ce aceste tupluri au fost determinate. Ajunse la procesor, se construiește tabela de partiționare. Celelalte fragmente se scriu mai întâi pe discuri (ca la GRACE Hash Join). La fel se procedează și cu tuplurile primului fragment al relației R.

5.4.5. Compararea algoritmilor paraleli pentru join

Neded Loop Join : Acest algoritm este cu atât mai rapid cu cât creste numărult de procesoare implicate. Până în acest moment este cel mai bun algoritm pentru join între relații de dimensiuni diferite.

Sort Merge Join : Algoritmul de acest tip nu se îmbunătățește substanțial odată cu creșterea numărului de procesoare, dar este avantajos în cazul în care cresc dimensiunile relațiilor implicate în proces.

Simple Hash Join : Este un algoritm bun în cazul în care tabelele de partiționare nu depășesc capacitatea memoriei. În caz contrar, devine mai avantajoasă utilizarea algoritmului GRACE Hash Join.

Hybrid Hash Join : Este în general cel mai bun algoritm pentru efectuarea join-urilor între relații.

5.5. Optimizarea cererilor paralele

O singură cerere relațională poate implică mai multe operații. Optimizarea cererilor paralele trebuie să ia în considerare nu numai paralelismul intraoperație, discutat anterior, ci și paralelismul interoperații. Deoarece selecțiile și proiecțiile sunt relativ ușor de manevrat, se pune problema optimizării paralele a cererilor care implică join-uri multiple.

Într-un mediu centralizat sau uniprocesor, optimizarea join-urilor multiple presupune mai întâi găsirea ordinii în care să se execute operațiile, precum și metodele care se aplică (nested loop, sort merge etc.). Într-un mediu multiprocesor, planificarea și alocarea resurselor constitiue un pas important în optimizarea cererilor.

În continuare vom considera un join cu patru căi, care implică relațiile R0 ►◄C R1 ►◄C R2 ►◄C R3. Datorită comutativității join-urilor, din aceasta cerere pot fi derivate mai multe cereri echivalente. În acest caz (patru-cai), există cincisprezece cereri echivalente, dintre care șase sunt prezentate mai jos:

(1) R0 ►◄C1 R1 ►◄C2 R2 ►◄C3 R3

(2) R0 ►◄C1 R1 ►◄C3 R2 ►◄C2 R3

(3) R0 ►◄C2 R1 ►◄C1 R2 ►◄C3 R3

(4) R0 ►◄C2 R1 ►◄C3 R2 ►◄C1 R3

(5) R0 ►◄C3 R1 ►◄C1 R2 ►◄C2 R3

(6) R0 ►◄C3 R1 ►◄C2 R2 ►◄C1 R3

unde indicele fiecărui join arată ordinea în care acestea vor fi evaluate.

Join-urile și ordinea lor de evaluare pot fi reprezentate grafic, ca arbori. Pentru relațiile (1), (2) și (6), arborii arată astfel:

Arbore stâng Arbore stufos (bushy tree) Ra

Arbore drept

Într-un arbore stâng, toate nodurile copii din dreapta sunt noduri frunză, iar toate nodurile copii din stânga, mai puțin cel mai de jos, sunt noduri interne. Într-un arbore drept, toate nodurile copii din stânga sunt noduri frunză, iar toate nodurile copii din dreapta, mai puțin cel mai de jos, sunt noduri interne. Într-un arbore stufos, ambii copii ai unui nod intern pot fi noduri interne.

Datorită numărului mare de posibile ordonări a join-urilor, multe tipuri de optimizări de cereri relaționale consideră doar un subset de ordonări. Arborii drepți au cel mai mare potențial de exploatare a paralelismului pipeline, iar arborii stufoși pentru paralelismul independent, deoarece subarborii săi pot fi procesați independent în paralel.

Dacă există trei metode de executare a join-urilor (nested loop, sort merge și hash join), atunci numărul total de planuri pentru executarea unei cereri este 33 • 15 = 405.

Planificarea și alocarea resurselor complică optimizarea cererilor relaționale într-un mediu multiprocesor. O posibilă modalitate de alocare a procesoarelor pentru join este utilizarea tuturor procesoarelor pentru fiecare join, astfel încât join-urile se execută unul câte unul. Altă posibilitate o constituie partiționarea procesoarelor în clustere astfel încât fiecare cluster de procesoare este utilizat pentru procesarea unui join. În acest mod, toate join-urile pot fi procesate în același timp (eventual în maniera înlănțuită). Această alternativă exploatează atât paralelismul intraoperațional, cât și pe cel interoperațional.

În general, există două strategii de bază pentru a genera un plan de executare pentru o cerere de multi-join într-un mediu multiprocesor. Prima strategic divide sarcina în două subsarcini. Prima dintre acestea genereza un plan de execuție fără să considera planificare și alocare resurselor. Cea de-a doua subsarcina produce un plan de alocare pentru operațiile generate de prima subsarcină. Aceasta strategic este cunoscută sub numele de optimizare în două faze. Principalele sale avantaje sunt flexibilitatea și relativă simptitate. Principala problemă o constituie faptul că nimic nu garantează că planul este optim sau cel puțin aproape optim. Strategia într-o singură fază este utilizată pentru rezolvarea acestei probleme (cea de-a doua dintre strategii)

6. EVALUAREA PROCESĂRII UNEI OPERAȚII

6.1 Evaluarea selecției

Să considerăm selecția , unde A este un atribut simplu, a este o valoare constantă și op este un operator în mulțimea {=, ≠, <, ≤, >, ≥}. Dacă op este ^, atunci majoritatea tuplurilor din R tind să satisfacă condiția dată. În acest caz, o parcurgere secvențială a relației R este o opțiune de evaluare a condiției date mai bună decât cea obținută folosind un index de structuri. Următoarele afinității se vor referi la operatori diferiți de ^. Costul evaluării selecției este strâns corelat cu numărul de tupluri al relației R care satisfac condiția dată.

Definiție: Selectivitatea unei condiții "A op a" pe o relație R, notată sA op a(R), reprezintă procentul de tupluri din R care satisfac condiția "A op a".

Evident, o ≤ sA op a(R) ≤ 1. Factorul de selectivitate al oricărei condiții poate fi estimat pe baza unor statistici asupra relației și a unor presupuneri asupra distributivității A-valorilor relației R. Adaugate la numărul t de tupluri n din R, aceste statistici includ dist(A), numărul t de valori distincte ale lui A în R; min(A), valoarea minimă a lui A în R; și max(A), valoarea maximă a lui A în R. Frecvent se utilizează presupunerea că valorile lui A sunt uniform distribute între min(A) și max(A). Folosind statisticile asociate și presupunerea de uniform distributivitate, SA op a(R) poate fi ușor estimată. De exemplu, SA=a(R) poate fi estimată prin 1/dist(A) și SA>a(R) se poate estima prin [max(A)-a]/[max(A)-min(A)]. Fie k numărul de tupluri din R care satisfac conditia "A op a". Atunci k poate fi estimat prin n*SA op a(R).

6.2 Evaluarea proiecției

Să considerăm proiecția , unde A1, …. at( sunt atribute ale relației R. Avem două cazuri distincte.

Cazul 1. Nu se șterg duplicatele. În SQL duplicatele sunt șterse numai dacă se folosește SELECT DISTINCT. În acest caz, proiecția poate fi evaluată prin parcurgerea fiecărui tuplu o singură dată.

Cazul 2. Se șterg duplicatele. Acest lucru se realizează în trei pași. Primul pas constă în scanarea relației și proiectarea ei cu păstrarea duplicatelor. Al doilea pas sortează rezultatul obținut la primul pas. Al treilea pas are ca rezultat îndepartarea duplicatelor din rezultatul sortat.

6.3 Evaluarea join-ului

Deși este una dintre cele trei operații cel mai des utilizate (selecție, proecție și join), join-ul este cea mai costisitoare operație. În consecință, este una dintre operațiile cele mai studiate. În cadrul acestui paragraf sunt prezentați câțiva algoritmi de evaluare a operației de join. Se va lua în considerare doar equijoin-ul. Vom presupune că join-ul considerat este de forma: R ►◄C S.

Presupunem de asemenea că R are n tupluri și pagini de dimensiune N, iar S are m tupluri și pagini de dimensiunea M. Vom presupune de asemenea că S este relația mai mică dintre cele două relații, adică M≤N. Există mai mulți algoritmi de evaluare a operației de join. În continuare vom prezenta algoritmii: nested loop, sort merge și hash join.

Nested loop

Algoritmul compară fiecare tuplu din R cu fiecare tuplu din S în mod direct pentru a găsi tuplurile care satisfac condiția dată. Algoritmul este următorul:

pentru fiecare tuplu x din R

pentru fiecare tuplu y din S

dacă x[A]=y[B] atunci return (x,y)

În cazul acestei implementari, R este folosită la nivelul buclei externe și se va numi relație externă; S este folosit la nivelul buclei interne și se va numi relație intenă. O variantă ar fi să folosim S ca relație externă și R ca relație internă. După cum vom observa este importantă alegerea relației externe și a celei interne din punct de vedere al costului dacă acesta se va calcula pe baza numărului de pagini de I/O citite. Această alegere nu are un impact prea mare asupra costului CPU.

Pentru a estima costul operațiilor de I/O, algoritmul va trebui modificat pentru a folosi pagini nu tupluri. În acest caz, fie K dimensiunea (în pagini) a memoriei disponibile în buffer pentru join. Evident, K≥3 deoarece buffer-ul trebuie să pastreze cel puțin câte o pagină pentru fiecare dintre relații și o pagină pentru păstrarea rezultatului. În continuarea analizei, von considera ca în K se gasesc numai paginile de buffer disponibile pentru cele două relații de join, nu și cele care conțin rezultatele join-ului. Vom considera un prim caz special – în acest caz K=2. Atunci când R este relație externă și S este relația internă, vom obține următorul algoritm modificat:

pentru fiecare pagină P din R

pentru fiecare pagina Q din S

pentru fiecare tuplu x din P

pentru fiecare tuplu y din Q

dacă x[A]=y[B] atunci return (x,y)

De asemenea, K poate fi un întreg pozitiv, mai mare sau egal cu 2.

Analiza bazată pe numărul de pagini de I/O are un cost de I/O liniar. În acest caz o optimizare a costului poate fi următoarea: folosim ca relație externă relația mai mică, și lasăm relația externă să foloseasca atâtea pagini de buffer de câte are nevoie (min{M, K-1}).

Sort merge

Acest algoritm conține următorii doi pași:

1. Sortarea crescătoare a celor două relații pe atributele de join. Adică, sortăm relația R după valorile atributului A și relația S după valorile atributului B.

2. Executăm merge join-ul. Se va considera cazul când printre valorile inferioare ale atributelor de join există cel puțin o valoare distinctă. Fără a pierde din generalitate, vom presupune că atributul de join pentru R este A, iar pentru S avem atributul B. Se inițializează cei doi pointeri de referință către tuplurile cu cele mai mici valori pe atributele de join. Dacă valorile atributelor de join sunt egale, atunci se execută join-ul, iar pointer-ul din S coboară o poziție. În cazul în care valorile referite sunt diferite, pointer-ul care repera valoarea cea mai mică coboară o poziție. Procesul se repetă până când toate valorile atributelor de join au fost parcurse. Vom considera cazul în care atributele de join conțin și valori repetitive. Algoritmul trebuie modificat astfel încât el să ia în considerare toate valorile atributelor. Să presupunem că pointer-ul din R refera tuplul a1 și pointer-ul din S tuplul b1. Dacă cele două tupluri au aceeași valoare pe atributele de join, să spunem x, atunci cei doi pointeri vor avansa pe relații până când se va întâlni un pointer în R, respectiv S, care să aibă o valoare diferită de x pe atributui de join. Fie acești doi pointeri a2 pentru R și b2 pentru S. Pentru realizarea join-ului se va efectua un produs cartezian pe mulțimile determinate de limitele a1 și a2 (excluzând a2) pentru R, și b1 și b2 (fără b2) pentru S.

Costul acestui algoritm depinde în mare măsură de gradul de sortare al celor două relații și de numărul t de valori repetitive continute la nivelul atributelor de join. Cea mai frecventă situație întâlnită este aceea în care ambele relații sunt sortate și cel puțin unul dintre atributele de join nu conține valori repetitive.

Hash join

Algoritmul de bază constă în următorii doi pași:

1. Se construiește o tabelă de dispersie pentru cea mai mică dintre relații S pe atributul de join. Tuplurile sunt plasate direct în locațiile tabelei de dispersie.

2. Se sondează tabela de dispersie folosind relația mai mare R pentru a se efectua operația de join. ProcedeuI de sondare este:

pentru fiecare tuplu x din R

{folosind aceeași funcție de dispersie de la pasul 1, se determină o locație din tabela de dispersie pentru valoarea atributului de join din R;

dacă locația este nevidă

pentru fiecare tuplu y din locație

dacă x[A]=y[B] atunci return (x,y)

}

Folosirea aceleași funcții de dispersie este esențială pentru a asigura dispunerea în aceleași locații ale tabelei de dispersie pentru tuplurile celor două relații care au aceleași valori pe atributul de join. Este posibil ca nu toate tuplurile dintr-un bucket să aibe aceeași valoare pe atributul de join, dar oricum o intrare trebuie comparată cu toate tuplurile existente intr-un bucket pentru a putea determina dacă se va executa join-ul cu unul sau mai multe tupluri din bucket-ul respectiv.

O problemă ce poate apărea în aceste cazuri este aceea că tabela de dispersie a relației S să nu poată fi păstrata în memoria buffer. Pentru acest tip de probleme, există o variantă de hash join numită hash join hibrid (hybrid hash join). Aceasta metodă consta din operațiile: se partiționează relațiile S și R în F fragmente distincte S1, S2, …, SF, respectiv R1, …, RF, se construiesc succesiv tabelele de dispersie pentru fiecare fragment al partiției S și se efectuează join-ul între Sj și Rj, pentru je{1,…,F}. Numărul F de fragmente este determinat astfel încât tabele de dispersie ale oricărui fragment să poată fi păstrată în memoria buffer a sistemului. Pentru fragmentarea celor două relații se folosește aceeași funcție.

Compararea algoritmilor

Studiul asupra eficienței algoritmilor de evaluare a operației de join a avut drept rezultat următoarele concluzii:

1. Hash join-ul este cel mai eficient algoritm de join, atunci când este aplicabil. În general, acest algoritm este aplicabil numai equijoin-ului.

2. Sort merge join-ul este mai eficient decât nested loop join-ul dacă cele două relații implicate au dimensiuni foarte mari sau dacă una dintre relații sau ambele relații sunt ordonate după atributele de join. Dacă cele două relații sunt sortate, atunci sort merge join-ul este la fel de eficient ca și hash join-ul. În general, sort merge join-ul este mai puțin sensibil la dimensiunea memoriei buffer disponibile decât oricare al algoritm.

3. Nested loop join evoluează bine atunci când una dintre relații are o dimensiune mai mare, iar cealaltă relație are o dimensiune mai mică. Un caz special este acela în care relația cu dimensiunea mai mică poate fi păstrată în memoria buffer în întregime. În acest caz, cele două relații trebuiesc citite în întregime o singură dată. Când nested loop join-ul este combinat cu un index pe atributul de join în relația internă perfomanța obținută este excelentă. Această îmbunătățire este datorată faptului că indexul pe atributul de join al relației interne determină o identificare mai rapidă a tuplurilor relației interne care se potrivesc cu fiecare tuplu al relației externe. Această combinație este mult mai eficientă dacă diferența între dimenșiunile celor două relații este foarte mare.

7. DETERMINAREA ORDINII DE EXECUȚIE A OPERAȚIILOR

O cerere într-o bază de date constă dintr-un număr de operații. Ordinea executării operațiilor are o foarte mare importanță în evaluarea costului cereri.

În continuare vom prezenta o serie de tehnici și probleme pentru determinarea ordinii optime de execuție a operațiilor. Există două moduri de determinare a ordinii de executare a operațiilor: bazat pe algebra relatională și bazat pe estimarea costului. Ambele metode folosesc un set de reguli care pot transforma un plan de execuție (reprezentat printr-o expresie a algebrei relaționale) într-un alt plan de execuție echivalent.

7.1 Reguli de transformare

Există numeroase reguli care pot transforma o expresie algebrică relațională într-o altă expresie algebrică relațională echivalentă. Două expresii sunt echivalente dacă ele furnizează întotdeauna același rezultat.

Reguli de transformare

1. Cascada de selecții: Fie C1 și C2, două condiții de selecție asupra lui R, atunci:

2. Comutarea selecției cu join-ul. Dacă condiția C implică numai atribute din R, atunci:

σC(R ►◄ S)=(σC(R))►◄ S

Din regulile de transformare (1) și (2), se poate deduce următoarea regulă: dacă condiția C1 implică numai atribute din R și condiția C2 implică numai atribute din S, atunci

σC1 and C2(R ►◄ S)=( σC1 (R)) ►◄ (σC2 (S)).

Se poate observa că această regulă rămâne adevărată și dacă înlocuim relația de join cu produsul cartezian.

3. Comutarea proiecției cu join-ul. Presupunem că AL={A1,… An, B1,… ,Bm}, unde A-urile sunt atribute din R și B-urile sunt atribute din S.

(a) Dacă condiția C implică numai atributele din AL, atunci

(R ►◄C S)=(R) ►◄C (S)

(b) Dacă pe lângă atributele din AL, C mai implică și alte atribute A1',…, An’ din R și B1',…,Bm’ din S atunci (R ►◄C S)=(R) ►◄C (S))

4. Asociativitatea θ-join-ului și a join-ului natural:

R ►◄C1 (S ►◄C2 T) = (R ►◄C1 S) ►◄C2 T

R ►◄ (S ►◄ T)= ( R ►◄ S) ►◄ T

Motivul prezentării separate a regulilor pentru θ-join și join-ul natural este acela că prin amestecarea acestor reguli nu se obține o regulă validă. Ceea ce înseamnă că regula

R ►◄C (S ►◄ T)=(R ►◄C S) ►◄ T este o regulă incorectă.

Exemplu:

Să considerăm relațiile: R cu atributele (A,B), S cu (D,E), T cu (A,E) și condiția de join C="R.A=S.D". În acest caz, join-ul natural din stânga egalității va evalua numai "S.E=T.E", spre deosebire de join-ul natural din dreapta egalității care va evalua "S.E=T.E" și "R.A==T.A". Deci rezultatele obținute sunt diferite, ceea ce semnifică faptul că cele două expresii nu sunt echivalente.

5. Înlocuirea x cu ►◄ și σ: Dacă C este o condiție de forma "R.A op S.B" sau o conjuncție de astfel de forme, atunci obținem relația:

σc(RxS)= R ►◄ C S.

7.2 Optimizare pe baza algebrei relaționale

Ideea de bază a metodei de optimizare bazată pe algebra relațională este aceea de a prezenta fiecare cerere relațională ca o expresie a algebrei relaționale și de a o transforma într-o altă expresie relațională dar mult mai eficientă. Transformarea este bazată pe tehnici euristice de optimizare. Cele mai utilizate reguli de optimizare sunt:

Regula de optimizare 1

Evaluarea selecțiilor cât mai devreme posibil. Motivul acestei reguli este acela ca selecția poate reduce semnificativ dimensiunea relațiilor, astfel că restul operațiilor vor fi evaluate mult mai eficient. Această regulă poate fi obținută cu ajutorul regulilor de tranformare 1 și 2 prezentate anterior. Mai exact, prin regula de transformare 1 două (sau mai multe) selecții sunt separate în selecții individuale care pot fi distribuite cu regula de transformare 2 join-urilor sau produselor carteziene.

Regula de optimizare 2

Inlocuirea produsului cartezian cu join, ori de câte ori este posibil. Un produs cartezian între două relații este mult mai costisitor decât un join între două relații, deoarece produsul cartezian generează prin concatenarea perechilor de tupluri rezultate foarte mari. Această regulă poate fi obținută folosind regula de transformare 5.

Regula de optimizare 3

În cazul mai multor relații de join, se evaluează prima cea mai restrictivă dintre ele. Un join este mai restrictiv decât altul dacă furnizează un rezultat mai mic. Transformarea poate fi obținută folosind regula de transformare 4.

Regula de Optimizare 4

Eliminarea atributelor nefolosite cât mai devreme. Dacă un atribut al relației nu este utilizat în cadrul operațiilor ulterioare, atunci el ar trebuie șters astfel încât să obținem o relație mai mică la intrare care va fi folosita în cadrul operațiilor viitoare. Aceasta regulă poate fi obținută folosind regula de transformare 3.

Regulile de optimizare euristice anterioare pot fi ilustrate grafic folosind conceptui de arbore de cereri (query tree). În acest caz se impune o reprezentare arborescenta a expresiilor algebrei relaționale. Într-un arbore de cereri, fiecare relație de intrare este reprezentată ca un nod frunză și fiecare operație este reprezentată ca un nod intern. Arborele prezintă o execuție semantică bottom-up, adică o operație poate fi evaluata numai dacă toți descendenții săi au fost evaluați.

7.3 Optimizare pe baza costului estimat

Acest tip de optimizare se bazează pe numărul de planuri de execuție posibile pentru o cerere dată. Pentru fiecare plan de executie se estimeaza costul executării planului respectiv. În final este ales acel plan de execuție care prezintă un cost de execuție minim. În acest fel poate fi determinat chiar un plan optim de execuție pentru o cerere data. În general apar două mari probleme:

1. Poate apărea un număr prea mare de planuri de execuție. În general, numărul de planuri de execuție pentru o cerere variază exponențial cu numărul de relații conținute de aceasta.

2. Poate fi foarte dificil de estimat costul fiecărui plan de execuție cu exactitate. În special, este foarte dificil de estimat cu precizie dimensiunile rezultatelor intermediare ale unui plan de execuție.

Selecția σc(R). Fie Sc(R) selectivitatea conditiei C asupra relației R. Atunci numărul de tupluri din σc(R) poate fi estimat prin n.Sc(R), unde n este numărul de tupluri din R, sau dimensiunea rezultatului σc(R) poate fi estimata prin N.Sc(R), unde N este dimensiunea unei pagini a lui R. De asemenea, evaluarea costului va mai depinde și de tipul și de costul de evaluare a condiției C.

Proiecția . În acest caz vom considera duplicatele eliminate din cadrul rezultatului.

Cazul 1. Presupunem ca {A1,…,At} formează o supercheie. În acest caz nu pot există duplicate. De asemenea, în acest caz, numărul de tupluri din este tot n (dacă numărul de tupluri din R este n), iar dimensiunea acestuia în pagini este: , unde length(Ai) reprezintă numărul de bytes a valorilor din Ai.

Cazul 2. Presupunem ca t=1. În acest caz, numărul de tupluri conținut de rezultat este egal cu numărul de A-valori distincte din R, iar dimensiunea în pagini este

Cazul 3. Presupunem că unul dintre atribute, Aj cu 1 < j < t, determină funcțional restul de atribute. În acest caz numărul de tupluri din rezultat este dist(Aj), iar dimensiunea rezultatului este

Cazul 4. Presupunem ca Aj sunt independente. Numărul de tupluri în acest caz poate fi estimat foarte simplu. De exemplu, pentru t=2, avem

Join R ►◄ r.a op S.B S. Vom lua în considerare numai cazul în care op este operatorul '='. Presupunem ca A și B sunt atribute arbitare ale relațiilor R și S. În general estimarea numarului de tupluri din rezultat este o operație foarte dificila de efectuat. Vom mai presupune ca A este cheie primară a lui R, iar B este o cheie externă a lui S. În acest caz, dimensiunea în pagini a rezultatului este unde m este numărul de tupluri din S.

8. Concluzii

În lucrarea de față au fost prezentate sintetizat o serie de modalități de tratare a cererilor de date care apar în bazele de date relaționale. Interogarea bazelor de date este o operație frecventă care ține de chiar scopul final al existenței unei baze de date.

Dar, cu cât structura tabelelor care compun baza de date este mai complexă, precum și cu creșterea numărului de tupluri din baza de date, extragerea de informații devine din ce în ce mai complicată, consumând timp și necesitând tot mai multă memorie pentru lucru (memorie internă cât și memorie virtuală).

Din această cauză este foarte importantă găsirea unor modalități de tratare a cererilor de date în mod optim, pentru a reduce durata căutării informațiilor dar și cantitatea de memorie ocupată pentru operațiunea respectivă.

Astăzi există mai multe modalități de optimizare a procedurilor de tratare a cererilor de date pentru baze de date rela

Cu toate acestea, astăzi există o tendință de trecere la modelul de date orientat obiect datorită posibilităților crescute de modelare a unor entități complexe. În acest caz algoritmii de căutare și regăsire a informației depind foarte mult de caracteristicile particulare ale obiectelor din baza de date (sunete, imagini, filme, text, formulare etc.) astfel că se pot utiliza cu bune rezultate algoritmi euristici specifici inteligenței artificiale.

BIBLIOGRAFIE

Dușmănescu Dorel, Baze de date, Editura Universității din Pliești, 2005

lleana Popescu, Baze de date relaționale, Tipografia Universitatii Bucuresti, 1996

Lungu Ion, ș.a., Baze de date. Organizare, proiectare, implementare, Editura All, București, 1997

Velicanu M., Lungu I., Muntean M., Dezvoltarea aplicatiilor cu baze de date in Visual FoxPro, Editura All, București, 2001

Bâscă O., Baze de date, Editura All, București, 1999

Ben Forta, SQL pentru incepatori, Editura Teora, Bucuresti, 2002

Fotache M., SQL. Dialecte DB2, ORACLE și Visual FoxPro, Editura Polirom, Iași, 2002

Thomas Connolly, Carolyn Begg, Anne Strachan, Baze de date – proiectare, implementare, gestionare, Editura Teora, București, 2002