Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » informatica » baze de date
PROIECTAREA ALOCARII

PROIECTAREA ALOCARII




PROIECTAREA ALOCARII

Fie un set de fragmente F = intr-o retea formata din siteurile S = si asupra carora se executa anumite aplicatii (interogari) Q = . Problema proiectarii alocarii se refera la distribuirea optima a fragmentelor F pe siturile S.

Potrivit lui Dowdy si Foster, "optimul"  se refera la:

  • Cost minim. Functia cost - compusa din:
    • costul plasarii fragmentului Fi pe site-ul Sj
    • costul interogarii Sj de catre Fi
    • costul actualizarii tuturor fragmentelor Fi plasate in toate siteurile
    • costul comunicatiei.

Problema alocarii - gasirea unei scheme de minimizare a costurilor.



  • Performanta. Strategia de proiectare - mentinerea unui nivel de performanta prin minimizarea timpului de raspuns si maximizarea capacitatilor sistemului ca masura a contributiei fiecarui site.[1]

Alocarea - neredundanta sau redundanta

  • Alocarea neredundanta - mai ieftina ca efort de proiectare si mai usor de realizat. Alt avantaj - posibilitatea de actualizare a fragmentelor. Se bazeaza pe metoda celei mai bune alegeri - unei statii pe care deja a fost plasat un fragment, nu poate sa-i mai fie alocat un fragment "inrudit".
  • Alocarea redundanta - mai complexa. Consultarile de date si actualizarile sunt problematice. Exista doua variante de abordare a proiectarii in acest caz:

a)        Metoda selectarii - identificarea siturilor pentru care beneficiul alocarii unei copii depaseste costul alocarii;

b)        Metoda alocarii progresive - se implementeaza initial o alocare neredundanta. Apoi, in functie de gradul de profitabilitate al statiilor se vor raspandi replici ale fragmentelor deja alocate, pana cand nu mai exista candidati la replicare.

Prima metoda (selectarea) este mai riguroasa si elimina posibilitatea de a inmagazina pe acelasi site si copia fragmentului deja stocat.

Replicarea progresiva - metoda euristica - bazata pe asertiunea ca profitabilitatea scade pe masura ce gradul de redundanta creste.[2]

Abordare mai eficienta, dar si mai selectiva - metoda celei mai bune alegeri si in etapa de proliferare a copiilor. Se incepe cu fragmentele considerate ca fiind cele mai importante, tinandu-se cont la fiecare alocare de relatia de "rudenie" a tuturor fragmentelor ce exista sau urmeaza a fi stocate intr-un site.

Formule de evaluare a costurilor si beneficiilor implicate de alocarea fragmentelor [Lungu 1995], paginile 308 - 310:

Conventii in utilizarea notatiilor:

i - indice fragment;

j - indice site;

k - indice aplicatie sau cerere;

fkj - frecventa cererii k la site-ul j;

rki - numarul acceselor de regasire (citire, consultare) ale cererii k pentru fragmentul i;

wki - numarul acceselor de actualizare (scriere) ale cererii k pentru fragmentul i;

nki = rki + wki.

Alocarea fragmentelor orizontale

Metoda alocarii neredundanta. Se aloca fragmentul Fi la statia unde numarul de referiri la Fi este maxim. Calcularea numarului de referiri locale ale fragmentului Fi in situl Sj - → fragmentul Fi va fi alocat la statia pentru care Bij este maxim.

Metoda statiilor profitabile. Fragmentul Fi va fi plasat in acele situri j, unde costul referintelor de regasire este mai mare decat costul referintelor de actualizare in alte situri. Beneficiul Bij - o diferenta:

C - constanta ce cuantifica raportul dintre costul unei citiri si costul unei scrieri. In majoritatea cazurilor, C



→ Fi - alocat la statiile j pentru care Bij este pozitiv. Daca Bij ia numai valori negative, se va selecta maximul dintre acestea.

  • Metoda replicarii progresive - beneficiul stocarii unei noi replici se masoara in functie de siguranta si disponibilitatea sistemului.

di - gradul de redundanta a lui Fi

Pi - beneficiul de a avea cate o copie a lui Fi in fiecare sit

Beneficiul: β(di) = (1 - 21-di) Pi

Alocarea fragmentelor verticale

  • Partitionarea atributelor - masurarea beneficiului fragmentarii unui fragment Fi alocat la statia j, in doua fragmente Fs si Ft plasate in siturile s si t se considera si seturile de aplicatii ce acceseaza atributele din cele doua fragmente disparate vor fi qs si qt. Aceste cereri sunt cereri locale. Exista inca trei seturi de aplicatii: Q1, Q2 si Q3, - Q1 - local statiei r, care utilizeaza numai atribute ale fragmentelor Fs si Ft. Cererile Q1 necesita un acces la distanta. Setul Q2 - rezident in site-ul r si acceseaza atribute din ambele fragmente (q si t). Aici vom avea doua accese la distanta. Q3 apartine altor situri decat r, s, sau t, dar utilizeaza si fragmentul Fs, cat si Ft. Beneficiul acestei partitionari se cuantifica astfel:

Formula - numara atat accesele locale, cat si cele la distanta. Se poate rescrie prin inlocuirea lui nki cu rki + C wki.

Pentru determinarea schemei de alocare a fragmentelor Fs si Ft se va calcula beneficiul pentru toate combinatiile posibile ale siturilor s si t, alegandu-se perechea pentru care se realizeaza beneficiu maxim.

  • Gruparea atributelor - proiectarea fragmentelor - rezultat fragmente nedisjuncte. Problema descrisa in paragraful anterior - un set comun de atribute I. Gruparea verticala va prezenta particularitati si in ceea ce priveste cererile implicate.
    • Qs - setul de aplicatii locale site-ului s, care citesc sau actualizeaza orice atribut al fragmentului Fs, dar care nu se suprapun cu I.
    • Q2 - cererile de actualizare aflate pe statia r - actualizarea atributelor setului I si necesita acces atat la Fs, cat si la Ft.
    • Q3 - aplicatii din alte statii decat cele amintite, care actualizeaza atributele setului I si necesita acces atat la Fs, cat si la Ft.

→ Formula descrisa in cazul abordarii anterioare este valabila si in cazul gruparii → alocarea trebuie sa asigure regasirea facila a fragmentelor prin conferirea unui plasament optim, astfel ca sa se reduca pe cat posibil numarul de accese la distanta. In afara de componenta costului de comunicatie, alocarea trebuie sa tina cont si de celelalte aspect relative costului proiectarii alocarii.



[Mohan et al. 1986]

[Lungu 1995], pagina 308







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.