PROIECTAREA BAZELOR DE DATE DISTRIBUITE

Principiile proiectarii bazelor de date discutate in anul II (normalizare, descompunere etc.) se aplica deasemenea si la bazele de date distribuite. in acest paragraf ne vom concentra aupra cercetarilor de proiectare ce sunt specifice BDD.

Consideram o relatie ce urmeaza a fi memorataaintr-o BD. Exista mai multe probleme in memorarea relatiei in BDD ca:

Replicarea. Sistemul mentine mai multe replici (copii) ale relatiei. Fiecare replica este memorata pe un sit diferit, care resulta din replicarea datelor. O alternativa la replicare este sa memoreze numai o copie a relatiei r.

Fragmentarea. Relatia este partitionata in mai multe fragmente. Fiecare fragment este memorat intr-un sit.

Replicare si fragmentare. Aceasta este o combinatie a celor doua notiuni de mai sus.

Replicarea datelor

Daca relatia r este replicata, o copie a relatiei r este memorata in doua sau mai multe situri. in cazul extrem avem o replicare completa in care o copie este memorata in fiecare sit din sistem. Exista un numar de avantaje si dezavantaje ale replicarii.

Disponibilitatea. Daca un sit are o pana (se defecteaza) atunci relatia poate fi gasita pe alt sit. Astfel sistemul poate continua procesul de interogare ce implica relatia r in ciuda erorii de pe sit.

Paralelism crescut. in cazul cand majoritatea accesarilor la relatia r se reduc numai la citiri ale relatiei, mai multe situri pot prelucra intrebari in paralel. Cand exista mai multe replici ale lui r atunci exista o sansa mai mare ca datele necesare executarii unei tranzanctii sa fie in acelasi sit, in care se executa tranzactia. Prin urmare replicarea datelor minimizeaza miscarea intre situri.

Cresc cheltuielile cu actualizarea. Sistemul trebuie sa asigure ca toate replicile relatiei r sunt consistente in acest caz calculele pot fi enorme.Astfel cand r este actualizata, actualizarea trebuie sa fie propagata pe toate siturile care contin replica si astfel cresc cheltuielile de actualizare. De exemplu intr-un sistem de banci, unde informatiile dintr-un cont sunt replicate pe diverse situri, este necesar sa modificam conturile in toate siturile. in general, replicarea asigura performanta operatiilor de citire si cresterea disponibilitatilor datelor la tranzactiile de citire. Totusi, tranzactiile de actualizare comporta mari cheltuieli. Problema controlului actualizarii tranzactiilor concurente a mai multor de date replicate este mult mai complexa decat abordarea centralizata a controlului concurentei. Vom putea simplifica gestiunea replicilor lui r prin alegerea uneia drept "copie primara" a lui r. De exemplul, intr-un sistem bancar un cont poate fi asociat unui sit in care contul a fost deschis. Similar intr-un sistem de rezervare, zborul poate fi asociat cu situl din care se zboara initial.

Fragmentarea datelor

Daca relatia r este fragmentata, adica este divizata intr-un numar de fragmente r,r,.r. Aceste fragmente trebuie sa contina informatii suficiente sa reconstruim relatia initiala r. Reconstruirea relatiei r se face fie aplicand reuniunea fie aplicand unirea (join) pentru diverse fragmente ale relatiei. Exista doua scheme diferite pentru fragmentarea unei relatii:

fragmentarea orizontala si

fragmentarea verticala.

Fragmentarea orizontala descompune relatia r prin atribuirea fiecarui tuplu al relatiei r la unul sau mai multe fragmente. Fragmentarea verticala descompune relatia r prin impartirea schemei de relatie R a lui r. Aceste doua scheme pot fi aplicate succesiv la aceeasi relatie, rezultand un numar de fragmente diferite. Remarcam ca acealeasi informatii pot sa apara in mai multe fragmente. Vom discuta diverse moduri de fragmentare a relatiei r. Vom ilustra acest iiiincaz considerand un depozit de bani la o banca care are schema :

D=(NUME_SUCURSALA, NR_CONT, NUME_CLIENT, SOLD)

Relatia depozit(D) este:

Figura 1. Exemplu de relatie de depozit.

Un fragment poate fi definit ca o selectie si/sau proiectie dintr-o relatie globala r. Adica se utilizeaza in constructia fragmentului r un predicat P si

r =_P(r)

Reconstructia relatiei r poate fi obtinuta prin reuniunea tuturor fragmentelor fragmentelor r=r r r.

Sa ilustram aceasta, presupunand ca relatia r este relatia depozit din figura 1. Aceasta relatie poate fi impartita in fragmente diferite, unde fiecare contine conturi numai dintr-o sucursala. Daca sistemul bancar are numai doua sucursale: Iasi si Craiova atunci exista doua componente diferite:

depozit1= (depozit),

depozit2= (depozit).

In exemplul nostru fragmentele sunt disjuncte.

Prin schimbarea predicatului de selectie s-ar putea ca un tuplu particular a lui r sa apara in mai mult de un fragment r a lui r. Aceasta forma de replicare o vom discuta mai jos.

Fragmentarea verticala

In forma cea mai simpla fragmentarea verticala este aceeasi cu descompunerea. Fragmentarea verticala a relatiei r(R) implica definitia mai multor submultimi ;

R, R,.,R ale schemei R astfel ca

R= R R R

Fiecare fragment r_i a lui r este definit prin:

r=p(r ) i=1,2,..,n.

Relatia r poate fi construita din fragmente luand unirea naturala

r=rr r

In plus, fragmentarea verticala poate fi insotita de adaugare de atribute speciale numite "identificatori_de_tupluri" la schema R. Un identificator_de_tuplu (ID) este o adresa fizica sau logica. Deoarece fiecare tuplu a lui R trebuie sa aiba o adresa unica, atributul ID este o cheie pentru schema de relatie marita.

Exercitiu. Scrieti relatia r obtinuta din r prin adaugarea ID la schema R. In figura 2 am aratat o descompunere a relatiei depozit la care am adaugat atributul ID si din care au rezultat schemele de relatie:

R₃=(NUME_SUCURSALA, NUME_CLIENT, ID)

R₄=(NR_CONT, SOLD, ID).

Relatiile depozit3 si depozit4 rezulta din evaluarea expresiilor:

depozit3=p_R3 depozit)

depozit4=p _R4(depozit)

Exercitiu. Scrieti relatiile depozit3 si depozit4 obtinute prin fragmentarea pe verticala. Se observa ca:

depozit5=depozit3depozit4

este o forma speciala de unire. Atributul de unire este ID. Deoarece valoarea atributului ID reprezinta adresa relativa, este posibil sa imperechem un tuplu al relatiei depozit3 cu tuplul al relatiei depozit4. Aceste adrese permit regasirea tuplului fara indexare. Astfel aceasta unire este calculata mult mai usor si mai eficient decat unirea naturala. Prin urmare, atributul ID faciliteaza implementarea unei partitionari verticale si ceea ce este important este ca, acest atribut nu este vizibil utilizatorilor. Daca accesul la tupluri este dat de ID atunci este imposibil ca sistemul sa schimbe adresele tuplurilor. Astfel, accesibilitatea adreselor interne violeaza notiunea de independenta a datelor, una din virtutile principale ale modelui relational.

depozit3 depozit4

Figura2. Fragmentarea verticala a relatiei depozit.

Replicarea si fragmentarea datelor

Tehnicile descrise mai sus pentru replicarea si fragmentarea datelor pot fi aplicate succesiv la aceiasi relatie. Adica, un fragment poate fi replicat succesiv, si apoi replicile fragmentelor pot fi din nou fragmentate si asa mai departe. De exemplu, sa consideram un sistem distributiv constand din siturile S,S,.,S. Vom putea fragmenta depozit in depozit3a si depozit3b si depozit4 si vom memora o copie a lui depozit3a pe siturile S, Ssi S, o copie a depozit3b pe siturile Ssi S, si o copie a lui depozit4 pe siturile S, S si S.

Transparenta si autonomie

O relatie poate fi memorata intr-o BDD in diverse moduri. Ceea ce este important este ca sistemul minimizeaza gradul in care un utilizator ar trebui sa cunoasca cum se memoreaza o relatie. Cu alte cuvinte sistemul "ascunde detaliile de implementare pentru utilizator. Sistemul poate ascunde detaliile de distributie a datelor in retea. Vom numi aceasta transparenta retelei. Transparenta retelei este legata intr-un anumit sens de autonomia locala. Autonomia locala este gradul in care un proiectant sau un administrator al unui sit poate fi independent de ceea ce ramane din sistemul distribuit. Vom cerceta transparenta si autonomia legata de:

Numirea elementelor de date,

- Replicarea elementelor de date,

Fragmentarea elementelor de date,

Localizarea fragmentelor si replicilor,

Independenta datelor,

Transparenta retelei

Numire si autonomie locala

Orice element de data dintr-o BD trebuie sa aiba un nume unic. Aceasta proprietate este usor de asigurat intr-o BD nedistribuita. Trebuie sa ne asiguram intr-o BDD ca doua situri nu utilizeaza acelasi nume pentru elemente de date distincte. O solutie la aceasta problema esta sa cerem ca toate numele sa fie inregistrate intr-un server central. Aceasta abordare are urmatoarele dezavantaje:

Numele serverului poate duce la strangulare

Daca serverul se defecteaza este posibil ca orice sit dintr-un sistem distribuit

sa nu continue executia

Exista o autonomie locala minima deoarece numirea este controlata central