Revista Informatica Economica , nr. 81998 51 [614045]

Revista Informatica Economica , nr. 8/1998 51
Proiectarea bazelor de date distribuite

Lect. Cristina IONITA, prep. Petrisor OPREA
Catedra de Informatica Economica, A.S.E. Bucuresti

Ca urmare a cerintelor de crestere a disponibilitatii, sigurantei si flexibilitatii sistemelor de baze
de date (BD) pr ecum si a progreselor înregistrate în tehnologia BD si în domeniul comunicatiilor,
sistemele de baze de date distribuite (BDD) sunt în prezent larg raspândite. Dezvoltarea BDD
este motivata atât tehnologic cât si organizatoric întrucât elimina o parte din neajunsurile
bazelor de date centralizate si sunt bine venite pentru descentralizarea structurii organizatorice
în cadrul unei unitati economice. Cercetarile în domeniul BDD au început în anii '70 dar
adevaratele sisteme distribuite au început sa apara pe piata pe la mijlocul anilor '80: ORACLE
SQL*STAR, INGRES/STAR, VAX Data Distribution etc. În prezent, majoritatea SGBD -urilor au
în componenta module pentru asigurarea distributiei datelor. Proiectarea unei BDD necesita
metodologii si tehnici noi care sa t ina seama de obiectivele specifice BDD. Proiectarea BDD este
dificil de formalizat datorita complexitatii problemei de distributie a datelor si a restrictiilor de
realizare.
Cuvinte cheie : baze de date, model distribuit, metode de proiectare.

1. Introduc ere

Pentru a asigura respectarea obiectivelor
specifice ale BDD si anume: cresterea sigurantei
sistemului si a disponibilitatii datelor,
descentralizarea resurselor sistemu -lui, o mai
buna utilizare a acestora precum si sporirea
adaptabilitatii sistemulu i la modifi -carile din
structura organizatorica, în proiec -tarea BDD
se urmareste asigurarea respec -tarii
urmatoarelor principii :
Ä Maximizarea prelucrarii locale a date –
lor, care presupune plasarea datelor cât mai
aproape de aplicatiile care le solicita. Se
apreciaza ca într -o BDD corect proiectata
aproximativ 90% din volumul de date trebuie sa
fie accesate local si numai 10% sa fie accesate
de la distanta.
Ä Asigurarea unui nivel crescut de sigu –
ranta si disponibilitate a datelor, care poate fi
realizat prin replicarea datelor pe mai multe
statii. În aceste conditii, sistemul poate utiliza o
copie alternativa atunci când cea care trebuia sa
fie accesata în conditii normale nu este
disponibila. Ä Procesarea paralela a datelor . Distri –
buirea bazelor de date ofera posibilitatea de a
utiliza eficient capacitatile procesoarelor din
fiecare statie pentru a maximiza gradul de
paralelism în executia aplicatiilor. Cresterea
numarului de prelucrari realizate în paralel intra
însa în contradictie cu principiul de maximizare a
prelucrarilor locale. În proiectarea BDD trebuie
sa asigure un raport optim între cele doua tipuri
de prelucrari.
Tipuri de proiectare. Proiectarea BDD poa –
te fi realizata, ca si în cazul BD centralizate, în
maniera top -down si/sau bottom -up:
§ Proiectare a top -down urmareste asigu –
rarea unei distribuiri optime a datelor si este
utilizata atunci când proiectarea BDD începe de
la zero. În general în urma abordarii top -down
sistemele rezultate sunt omogene.
§ Proiectarea bottom -up a BDD este reco –
mandata în caz ul în care BD locale exista si
trebuie integrate într -un sistem unitar. În acest
caz obiectivul principal urmarit în proiectarea
BDD îl constituie asigurarea unei cooperari cât
mai bune între BD existente care sunt de regula
eterogene.

Revista Informatica Economica , nr. 8/1998 52
§ Proiectarea mixta, p artial top -down si
respectiv partial bottom -up este reco -mandata
în majoritatea cazurilor pentru ca raspunde mai
bine situatiilor practice.

2. Proiectarea top -down

Proiectarea descendenta, reprezentata sche –
matic în figura 1 , este un proces de rafinare
succesiva a specificatiilor globale ale BDD,
independente de sistem, în specificatii deta -liate
care sa tina cont de restrictiile impuse de sistem.
Punctul de plecare îl constituie identificarea si
analiza cerintelor informati -onale ale sistemului
care va exploata BDD. Pornind de la aceste
cerinte se va proiecta mai întâi schema globala a
BDD indepen -dent de restrictiile fizice de
distribuire si implementare. Urmeaza
proiectarea distribu -irii datelor, care va pune în
evidenta modul de fragmentare a BDD si de
alocare a fragmentelor la statii. Abordarea
descen -denta se va încheia cu proiectarea BD
locale pentru fiecare statie în parte.
Tehnicile de proiectare a schemei globale a
BDD si a BD locale sunt asemanatoare cu cele
utilizate în cazul BD centralizate. Spe -cifice
BDD sunt aspectele legate de proiec -tarea
schemei de fragmentare si a schemei de alocare
a fragmentelor la statii.
a. Proiectarea fragmentarii. Descompu –
nerea schemei globale în frag -mente poate fi
realizata aplicând doua tipuri principale de
fragmentare: fragmentarea orizontala si frag –
mentarea verticala.
Fragmentarea orizontala consta în partiti –
onarea tuplurilor unei colectii globale în
subseturi, pe baza unor predicate de selectie.
Predicatul de selectie denumit si calificare este
asociat f iecarui fragment si defineste
proprietatea care a stat la baza gruparii tu –
plurilor în cadrul fragmentului. Ratiunea
fragmentarii orizontale este de a produce
fragmente cu potential maxim de procesare
locala, fiecare fragment obtinut fiind alocat la statia unde este cel mai utilizat. Alegerea
predicatelor de selectie nu este atât de simpla
cum ar putea sa para la prima vedere. Trebuie
luate în considerare atât de propri -etatile logice
ale datelor cât si de carac -teristicile aplicatiilor
care le exploateaza (cum ar fi numarul de
accese de regasire, respectiv de actualizare a
seturilor de date). Corelarea aspectelor logice
ale datelor cu ca -racteristicile aplicatiilor este
adesea dificil de realizat.
Identificarea setului de predicate este arbi -trara
si se rea lizeaza tinând cont de cerintele
informationale ale sistemului.
Pentru determinarea unui set de predicate de
fragmentare Pr ’, care sa realizeze fragmen -tarea
corecta si eficienta a unei colectii de date
globale R pornind de la un set de predi -cate,
Pr, det erminat în mod arbitrar, se poate aplica
un algoritm constituit din doi pasi :
P1. Initializarea . Se cauta un predicat p i ∈ Pr
care partitioneaza tuplurile colectiei R în doua
fragmente referite diferit de cel putin o aplicatie.
Predicatul p i va fi adaugat la m ultimea Pr’ si va
fi eliminat din multimea Pr : Pr’ = {p i}, Pr = Pr –
pi
P2. Adaugarea iterativa a predicatelor
simple la multimea Pr ’ pâna când devine
completa . Se cauta un predicat p j ∈ Pr care
partitioneaza o parte din fragmentele definite în
acord cu predi catele minterm construite pe baza
setului Pr’, în doua parti referite diferit de cel
putin o aplicatie. Predicatul p j va fi adaugat la
multimea Pr’ si va fi eliminat din multimea Pr :
Pr’ = Pr’ ∪ pj, Pr = Pr – pj
Determinarea unui set complet si minimal d e
predicate poate fi destul de costisitoare în
anumite cazuri. Pentru a evita aceste situatii este
recomandat ca în stabilirea setului de predicate
simple sa fie luate în considerare numai
aplicatiile importante, care acceseaza frecvent o
parte din tupluri le unei relatii globale si sa nu
separam fragmente care au caracteristici
asemanatoare.

Revista Informatica Economica , nr. 8/1998 53

Fig. 1. Proiectarea top -down a BDD

Fragmentarea verticala se realizeaza prin
împartirea atributelor unei relatii globale în setu ri
astfel încât mai multe aplicatii sa poa -ta fi
executate utilizând un singur fragment.
Ratiunea pentru fragmentarea verticala este
aceea de a grupa împreuna atributele frec -vent
utilizate împreuna. O buna fragmentare verticala
se realizeaza când fiecare aplicatie utilizeaza un
singur fragment, altfel aplica -tiile care necesita
accesarea mai multor fragmente verticale vor avea performante mai scazute, deoarece trebuie
sa realizeze una sau mai multe jonctiuni si,
implicit, nu -meroase accese la distanta. În
aceste conditii, trebuie asigurat un echilibru între
beneficiul potential datorat posibilitatii de
plasare a fiecarui fragment în apropierea
aplicatiilor care îl utilizeaza cel mai frecvent si
pierderile potentiale datorate faptului ca exista
aplicatii ca re utilizeaza doua sau mai multe
fragmente aflate pe statii diferite. ANALIZA CERINTELOR /
RESTRICTIILOR DE
DISTRIBUIRE Dictionarul global al BDD Cerinte / Restrictii
Informatii despre retea ANALIZA
CERINTELOR INFORMATIONALE
PROIECTAREA
CONCEPTUALA
PROIECTAREA
FRAGMENTARII
PROIECTARE A
ALOCARII Informatii despre aplicatii
Schema de alocare a BDD
(Schemele BD locale) PROIECTAREA
DISTRIBUTIEI Schema conceptuala
globala a BDD
Schema de
fragmentare a BDD aplicatii Informatii despre

Revista Informatica Economica , nr. 8/1998 54
Fragmentarea verticala este considerata mai
dificila decât cea orizontala pentru ca exista mai
multe alternative. Posibilitatile de gru -pare a
atributelor cresc combinatorial cu numarul de
atribute al tabelei de date. În schimb conditia de
corectitudine a fragmen -tarii este mai usor de
realizat si de verificat, fara a apela la algoritmi
speciali.
Fragmentarea mixta se realizeaza prin apli –
carea succesiva a operatiilor de fragmentare
orizontala si verticala. Astfel, fragmentele mixte
pot fi obtinute prin aplicarea fragmen -tarii
orizontale la un fragment vertical, respectiv prin
aplicarea fragmentarii verti -cale la un fragment
orizontal. Aceste operatii pot fi repetate
recursiv generând arbo ri de fragmentare de
orice complexitate. În prac -tica este
recomandat sa existe cel mult doua niveluri de
fragmentare.
b. Proiectarea alocarii. Alocarea fragmen –
telor pe statii este stâns legata de replicarea
datelor din BDD. La alocare proiectantul
trebu ie sa decida daca fragmentele BDD vor fi
replicate si gradul de replicare a acestora.
Replicarea are ca efect pozitiv cresterea
sigurantei sistemului si regasirea mai rapida a
datelor. În conditiile replicarii datelor,
mentinerea consistentei datelor în BD este mai
dificil de asigurat pentru ca actualizarea unui
fragment trebuie sa fie propagata la toate copiile
fragmentului. Decizia replicarii unui fragment
este influentata, în mare ma -sura, de raportul
dintre numarul acceselor de regarire si cel al
accese lor de actualizare pentru fragmentul
respectiv.
Alocarea fragmentelor pe statiile retelei, în
functie de metodele utilizate, poate avea ca
rezultat o alocare finala neredundanta sau re –
dundanta. Alocarea finala neredundanta este
recomandata când frecventa de actualizare a
datelor este mai mare decât frecventa de re –
gasire a datelor. Alocarea finala redundanta
este recomandata când frecventa de regasire a
datelor este mai mare decât frecventa de
actualizare a datelor. Replicarea datelor este mai convenabila în cazul sistemelor care admit
inconsistente temporare ale datelor.
Problema de alocare
Distribuirea eficienta a fragmentelor presu -pune
asigurarea unui echilibru între costuri (de
stocare, prelucrare si transmitere a datelor),
performante (în special tim pul de raspuns) si
restrictii de distribuire a datelor. Realizarea
alocarii fragmentelor BDD este o problema de
optimizare complexa ce presu -pune distribuirea
unei multimi de n fragmente F ={F1, F2, …, F n}
exploatate de o mul time de k aplicatii A={A 1,
A2, …, A k} pe o mul time de m statii S={S 1, S2,
…, Sm}, luând în calcul urmatoarele categorii de
in-formatii (variabile) [OZSU94] :
1. Informatii despre fragmentele BDD, cum ar
fi: dimensiunea fragmentelor , selecti -vitatea
fragmentelor ;
2. Informatii despre cerer ile (aplicatiile) care
vor exploata fragmentele, cum ar fi : numarul
acceselor de citire/actualizare ale fiecarei cereri
pentru fiecare fragment , timpul maxim
acceptabil de r aspuns ;
3. Informa tii privind statiile retelei, cum ar fi :
unitatea de cost pentru st ocarea/ prelucrarea
datelor pe o sta tie, capacitatea maxim a de
stocare/prelucrare a datelor pe o statie ;
4. Inform atii privind comunicarea în retea, cum
ar fi: costul comunicarii între statii, dimensiunea
frame -urilor, overhead -ul de comunicatie.
În general, costul alocarii unui fragment R i la o
statie j poate fi determinat astfel :
∑∑ ∑=
≠= =+ +=p
kn
jjjkijp
kkijij ij a l s C
1
'1''
1, i=1,m; j=1,n
unde:
sij – costul stoc arii fragmentului R i la statia j;
lijk – costul acceselor locale la fragmentul R i de
pe statia j a aplicatiei k;
aij – costul acceselor de actualizare a
fragmentului R i la statia j realizate de aplicatiile
k de pe celelalte statii (j `≠j);
p – num arul de aplicatii; m – numarul de
fragmente; n – numarul de statii.
Replicarea unui fragment R i la sta tia j se
justifica daca costul al ocarii fragmentului este

Revista Informatica Economica , nr. 8/1998 55
mai mic decât costul accesului la distanta a
aplicatiilor k de la statia j, la cele -lalte copii ale
fragmentului aflate pe statiile j ` (j`≠j):
'j
kki ij d C ∑<
În literatura de specialitate sunt prezentate
metode de alocare a frag mentelor BDD care
iau în calcul, integral sau partial, categoriile de
informatii prezentate. Cele mai cunoscute sunt
metodele propuse de Stefano Ceri si Giusepe
Pelagatti în [CERI85] pentru evaluarea
costurilor si respectiv beneficiilor de alocare a
fragme ntelor si anume :
§ Metoda cele mai bune alegeri consta în
comensurarea beneficiului fiecarei alocari
posibile a unui fragment si alegerea statiei cu
cea mai buna masura. Metoda realizeaza o
alocare finala neredundanta.
§ Metoda selectarii statiilor profitabile
presupune determinarea unui set de statii pentru
care beneficiul alocarii unei copii a fragmentului
este mai mare decât costul alocarii
§ Metoda replicarii progresive presupune
construirea initiala a unei solutii nere -dundante si
apoi introducerea progresiv a a copiilor
replicate, începând cu cea mai profitabila.
Replicarea progresiva se va încheia atunci când
nici o replicare posibila nu mai este profitabila.
Metodele sunt empirice, punând accent pe
evidentierea criteriilor de alocare a frag –
mentelor si nu p e masurarea exacta a costurilor
si beneficiilor, acestea fiind exprimate simplificat
numai prin frecventele de acces la fragmente.

3. Proiectarea bottom -up

În cadrul proiectarii bottom -up, reprezentata
schematic în figura 2 , punctul de plecare îl
constituie schemele BD locale. Se presupune ca
specificatiile BD pentru fiecare statie exista, fie
pentru ca BD locale exista deja si trebuie
interconectate într -un sistem de multi -BD, fie
pentru ca specificatiile con -ceptuale ale BD au
fost facute pentru fiec are statie, în mod
independent, si trebuie inte -grate într -o schema globala.
Prin integrarea schemelor BD existente se
urmareste corelarea descrierilor comune de
date si rezolvarea conflictelor care pot sa apara
ca urmare a diferentelor. Atunci când BD
existente sunt integrate într -o BDD este posibil
ca acestea sa utilizeze SGBD -uri diferite. Un
sistem eterogen adauga, deci, la complexitatea
integrarii datelor si necesi -tatea translatarii lor
între diferite repre -zentari. În acest caz,
abordarea ascendenta a BDD presupune
parcurgerea urmatorilor pasi: alegerea unui
model comun pentru a descrie schema globala;
translatarea fiecarei scheme locale în modelul de
date ales; integrarea schemelor locale într -o
schema globala.
Unul dintre cele mai utilizate modele pentru
descrierea schemei globale îl constituie modelul
entitate -asociere extins cu asocieri de tip
generalizare si specializare. Genera -lizarea ne
ajuta sa punem în evidenta partile comune ale
entitatilor iar specializarea diferentele între
entitati. De e xemplu, în figura 3a este
reprezentata entitatea E în viziunea a doua
scheme locale: E( A1, A2, A3, A4, A5) si
E(A1, A2, A3, A6, A7) , iar în figura 3b este
prezentat arborele de generalizare. Integrarea
unui set de BD locale eterogene constituie o
problema complexa, dificil de formalizat pentru
ca situatiile de la care se porneste sunt foarte
variate. În literatura de specialitate majori -tatea
tehnicilor de proiectare se refera la abordarea
top-down si numai un numar redus trateaza
proiectarea bottom -up, des i în practica aceasta
abordare este cea mai frecventa. Un set de
activitati pe care se bazeaza integrarea
schemelor BD locale a fost identificat in
[CERI92] , si anume :
§ Identificarea similarit atilor . Partile co –
mune ale schemelor locale pot fi identificate
relativ usor datorita similaritatii numelor de
entitati si atribute, a descrierii structurii sau chiar
prin identificarea unui set de valori comune.
§ Identificarea diferentelor si a conflicte –
lor posibile . Principalele categorii de dife -rente

Revista Informatica Economica , nr. 8/1998 56
care pot gener a conflicte se refera la diferente
de nume (sinonime respectiv omonime),
diferente de descriere a datelor (natura,
dimensiune), diferente de domeniu de valori, diferente structurale. Multe din aceste
conflictele pot fi rezolvate înainte de integrarea
schemelor locale prin modificarea
corespunzatoare a acestor scheme

Fig. 2. Proiectarea bottom -up a BDD

a. Viziunea schemelor locale

A2 A3
A1 E
A5 A4 A2 A3
E
A6 A7 A1
E1
A4 A5 E2
A6 A7 A2 A3
A1 E PROIECTAREA
DISTRIBUTIEI
PROIECTAREA
INTEGRARII
Schema globala a BDD
Schemele BD locale
Schema de
distributie a BDD

Revista Informatica Economica , nr. 8/1998 57
b. Arborele de generalizare
Fig. 3. Integrarea schemelor locale

O parte însa neces ita includerea în schema
globala a unor informatii suplimentare pentru
tratarea conflictelor (tabele de cores -pondenta,
formule de conversie, comporta -mentul diferit al aplicatiilor). Daca SGBD -ul distribuit nu ofera
facilitati pentru tratarea conflictelor , acestea vor
trebui gestionate de aplicatii, lucru mai dificil de
realizat.
§ Determinarea politicilor de solutionare a
inconsistentelor . Inconsistentele deter -minate
de replicarea datelor sunt frecvent întâlnite într –
un sistem de multi -BD si sunt datorate
deficientelor de integrare a sche -melor locale,
nesincronizarii operatiilor de actualizare sau
erorilor de refacere a BD dupa incidente.
Proiectantul BDD va trebui sa decida politica
de tratare a situatiilor în care se înregistreaza
valori diferite ale uno r obiecte aparent identice
aflate pe statii diferite : utilizarea uneia din
valorile incon -sistente, f ara sa avertizeze
utilizatorul; prezentarea tuturor valorilor
inconsistente utilizatorului, indicând si sursa
informatiilor; utilizarea celei mai recente v alori;
utilizarea valorii din sistemul cel mai de
“încredere”; utilizarea unor marimi agregate
determinate pe baza valorilor inconsistente
(medie aritmetica, maxim, minim etc.).

Concluzii

Sistemele de BDD prezinta o serie de avantaje
legate în special de cresterea performantelor
sistemului, de reducerea relativa a costurilor
prelucrare si transmitere a datelor si nu în ultimul
rând de faptul ca un sistem de BDD se
potriveste mai bine structurii organizatorice
dintr-o unitate economica. Dezavantajele sunt
legate de complexitatea ridicata de proiectare a unui astfel de sistem care suprapune peste
complexitatea unei retele de calculatoare
problemele legate de prelucrarea distribuita a
datelor si asigurarea unui nivel înalt de
transparenta a distributiei.
Procesul de realizare a unui sistem de BDD este
complex si se justifica în general în una din
urmatoarele situatii : atunci când se realizeaza
BD de dimensiuni mari, care ofera suport
pentru majoritatea activitatilor desfasurate într -o
organizatie, în situatia în care se preconizeaza
extinderi frecvente ale sistemului existent sau
pentru interconec -tarea unui set de BD
existente.

Bibliografie

1. S. Ceri, G. Pelagatti, Distributed Databases,
Principles and Systems, Interna -tional Student
Edition, McGraw Hill, 1985
2. S. Ceri, B. Pernici, G. Wiederhold,
Distributed Database Design Methodologies,
Proceedings of The Second International
Conference on Systems integration, New
Jersey, April 23 -26, 1992
3. I. Lungu, C. Bodea, G. Badescu, C.Ionita,
Baye de date. Organ izare, proiectare si
implementare, Ed. ALL, 1995
4. M. Tamer Özsu, P. Valduriez, Distributed
Database Management, Prentice Hall, 1994