Fragmentarea datelor - logica fragmentarii

CAPITOLUL IV

FRAGMENTAREA DATELOR

Trebuie sa aratam ca fragmentarea are si unele dezavantaje. Daca o aplicatie are mai multe cereri conflictuale care impiedica descompunerea relatiei in mai multe fragmente disjuncte (reciproc exclusive). Atunci acea aplicatie are nevoie de mai multe fragmente pentru a gasi data ea trebuie sa realizeze reuniunea sau unirea acelor fragmente care necesita timp. Aceste uniri constitue o cercetare fundamentala a fragmentarii. Un alt aspect este legat de controlul semantic al datelor care ne permit sa verificam conditiile de integritate ale datelor. Decizia de a utiliza o baza de date fragmentata este foarte importanta deoarece determina performanta executiei unei intrebari. Gradul de fragmentare variaza intre a nu fragmenta nimic sau a fragmenta pana la nivel de tupluri (sau atribute) individuale in cazul fragmentarii orizonatale sau la nivel de atribute in cazul fragmentarii verticale. Ele se definesc numai in raport cu aplicatiile care se executa asupra BD. Aplicatiile sunt caracterizate de un numar de parametrii. In concordanta cu valorile acestor parametrii pot fi identificate in mod individual fragmentele.

Logica fragmentarii

Din punct de vedere numai al distributiei datelor nu exista rationamente de fragmentare a datelor. Sistemele de fisiere distribuite se obtin dintr-un fisier intreg. Este mult mai usor sa ne ocupam de activitati specifice ce privesc numai alocarea fisierelor in nodurile unei retele de calculatoare. In ceea ce priveste fragmentarea, o cercetare importanta priveste destinatia unitatilor distribuite. O relatie nu este numai o secventa de unitati, din urmatoarele motive:

Vederile aplicatiilor sunt in mod obisnuit submultimi de relatii.

Prin urmare, locul de unde aplicatiile acceseaza nu este definit de relatia intreaga, ci de submultimi ale ei. Asadar, este mai natural sa consideram multimi de relatii ca unitati de distributie.

2. Daca aplicatia cuprinde o vedere a unei relatii intregi care se afla pe situri diferite atunci se pot intalni urmatoarele alternative; relatia in intregime se afla pe un singur site si in acest caz aplicatia trebuie sa-si transfere un volum mare de date la distanta sau se utilizeaza o replicare a bazei de date care determina apoi mari probleme in realizarea actualizarii si in plus nu este de dorit daca memoria este limitata.

In plus, descompunerea unei relatii in fragmente, fiecare fiind tratata ca o unitate, permite ca un numar de tranzactii sa se execute concurent si ne da posibilitatea de a executa in paralel o singura intrebare prin descompunerea intr-o multime de subintrebari ce opereaza pe fragmente. Astfel fragmentarea creste nivelul de concurenta numit concurenta intraqweri.

Trebuie sa aratam ca fragmentarea are si unele dezavantaje. Daca o aplicatie are mai multe cereri conflictuale care impiedica descompunerea relatiei in mai multe fragmente disjuncte (reciproc exclusive) atunci acea aplicatie are nevoie de mai multe fragmente pentru a regasi data ce trebuie sa realizeze reuniunea sau unirea acelor fragmente care costa. Aceste uniri constituie o cercetare fundamentala a fragmentarii.

Un alt aspect este legat de controlul semantic al datelor care ne permite sa verificam conditiile de integritate a datelor. Decizia de a utiliza o baza de date fragmentata este foarte importanta deoarece determina performanta executiei unei intrebari. Gradul de fragmentare variaza intre a nu fragmenta nimic sau a fragmenta pana la nivelul de tupluri (sau atribute) individuale in cazul fragmentarii orizontale sau la nivel de atribute in cazul fragmentarii verticale. Va trebui sa gasim un nivel de fragmentare cuprins intre aceste nivele. Ele se definesc numai in raport cu aplicatiile care se executa asupra bazei de date. Aplicatiile sunt caracterizate de un numar de parametrii. In concordanta cu valorile acestor parametrii pot fi identificate in mod individual fragmentele.

Corectitudinea regulilor de fragmentare

Cand am tratat normalizarea BD s-a mentionat un numar de reguli care asigura consistenta bazei de date. Este important sa remarcam ca exista o similaritate intre normalizarea si fragmentarea datelor pe verticala. Dam trei reguli de care trebuie sa se tina seama ca baza de date nu sufera schimbari semantice in timpul fragemntarii

1. Completitudine. Daca o relatie r este descompusa in fragmente r , r_{2,. . . ,} r_k atunci fiecare element de data ce poate fi gasit in relatia r trebuie sa fie gasit in cel putin un fragment r_i, Aceasta proprietate este identica cu proprietatea de descompunere fara pierderi de la normalizare. Aceasta este importanta in fragmentare deoarece ne asigura ca datele dintr-o relatie sunt mapate in fragmente (orizontale) fara nici o pierdere. In cazul fragmentarii orizontale elementul se refera la un tuplu, in timp ce in cazul fragmentarii verticale se refera la un atribut.

2.Reconstructie. Reconstructia relatiei din fragmente ne asigura ca, restrictiile definite asupra datelor sub forma de dependente sunt prezervate (adica daca R , R₂,.. . , R_K sunt schemele fragmentelor si F o multime de dependente functionale pe R , R₂,.. . , R_K si F_i=F|_{Ri, 1<=i<=k} atunci F=UF_i.

3. Separabilitate. Daca r este o relatie si este descompusa orizontal in fragmentele r₁,r_p, si elementul de data t_i se afla in r_j atunci el nu se mai afla in nici un alt fragment r_k, k j. Acest criteriu ne asigura ca fragmentele sunt disjuncte. Daca r este descompusa in fragmente pe vertical atunci atributele care sunt chei primare sunt repetate in toate fragmentele ei. Prin urmare, pentru partitionare pe verticala separabilitatea este definita numai pentru atributele neprime (care nu apartin cheilor candidate).

Alternative de alocare

Presupunem ca baza de date este complet fragmentata si trebuie sa decidem asupra alocarii fragmentelor pe diverse siteuri din retea. Cand datele sunt alocate, ele pot fi replicate sau mentinute intr-o singura copie. Ratiunile pentru replicare sunt date de siguranta in exploatare si eficienta interogarii, a intrebarilor de citire mai ales. Daca exista copii multiple de elemente de date exista si o sansa mai mare ca o copie sa fie accesibila, chiar daca sistemul are erori. In plus numai intrebarile de citire care acceseaza acelasi element de date pot fi executate in paralel, deoarece exista copii pe mai multe statii. Pe de alta parte, executia intrebarilor de actualizare deranjeaza sistemul, deoarece toate copiile datelor trebuie toate actualizate. Prin urmare decizia de replicare depinde de raportul dintre numarul de intrebari READONLY si numarul de intrebari de actualizare. Aceste decizii afecteaza aproape toti algoritmii si functiile de control ale unui SGBD distribuit. O baza de date nereplicata (numita si baza de date partitionata contine fragmente ce sunt alocate pe statii diferite si exista numai o copie a oricarui fragment pe o singura statie a retelei). In cazul replicarii, fie ca baza de date exista pe fiecare statie (BD complet replicata) sau copii de fragmente pot exista pe mai multe statii (BD replicata partial).

Cum vom vedea in continuare, numarul de copii ale fragmentelor poate fi o data de intrare intr-un algoritm de alocare sau o variabila de decizie a carei valoare este determinata de algoritm. Un aspect al proiectarii distribuite este ca, o multime de factori contribuie la proiectarea optima. Organizare logica a bazei de date, localizarea aplicatiilor, caracteristicile de acces ale aplicatiilor la baza de date, si proprietatile sistemului de calcul pe fiecare statie au o influenta importanta asupra deciziilor de distribuire. Informatiile pentru partitionare pot fi impartite in patru categorii: informatii asupra bazei de date, asupra aplicatiilor, asupra retelei si asupra sistemului de calcul.

Fragmentarea orizontala

Fragmentarea orizontala partitioneaza o relatie in raport cu tuplurile ei. Astfel fiecare fragment contine cate o submultime de tupluri din relatie. Exista doua variante de partitionare orizontala, primara si derivata.

Fragmentarea primara a unei relatii este realizata prin utilizarea de predicate definite pe acea relatie. Fragmentarea orizontala derivata este realizata cu ajutorul unor predicate care sunt definite pe alte relatii. Pentru a realiza o fragmentare orizontala avem nevoie de informatii despre baza de date si de informatii cu privire la aplicatia care va utiliza fragmentele. Informatiile despre baza de date sunt date de schema conceptuala globala a bazei de date. In acest context trebuie sa vedem cum sunt legate relatiile intre ele, cum se unesc in mod special. In modelul relational, legaturile sunt descrise prin relatii. Totusi in alte modele de date ca modelul E/R legaturile sunt descrise in mod explicit. Mai tarziu in modelul relational legaturile intre relatii se realizeaza printr-o operatie de echiunire.

Figura 1 arata modul cum se asigura legaturile dintre relatiile unei baze de date. Sagetile unei legaturi arata o relatie 1: n (unu la mai multi). De exemplu pentru fiecare calificare exista mai multi salariati cu acea profesie(F). Aceasta constituie o legatura intre relatiile de calificare(C) si salariati(S) notata cu L1.

Calificare C

Titlu, Salariu

Salariati S Proiecte

IdSalariat, Nume, Titlu IdProiect, Denumire, Buget, Loc

Functie

IdSalariat, IdProiect, OreLucrate, Sef

Figura 1. Exprimarea legaturilor (relationship) cu ajutorul sagetilor

Relatia din coada sagetii este numita owner(sursa), iar cea din varf member. Fie legatura L₁ din figura anteriara. Vom defini doua functii owner si member care specifica sursa si destinatia legaturii.

Exemplul 1. Consideram legatura L₁ din figura anterioara. Functiile owner si member au urmatoarele valori:

Owner(L₁) = C,

Member(L₁)=S.

Informatia cantitativa ceruta despre baza de date este data de cardinalitatea fiecarei relatii r, notata cu card(r). La proiectare aplicatiile necesita ambele tipuri de informatii cantitative si calitative. Informatiile calitative orienteaza activitatea de fragmentare, in timp ce informatiile cantitative sunt cuprinse in modele de alocare. Informatiile calitative fundamentale constau din predicate utilizate in intrebarile utilizatorilor. Daca nu este posibil sa ne imaginam toate predicatele utilizatorilor trebuie sa investigam pe cele mai importante dintre ele. Se sugereaza alegerea acelor intrebari ale utilizatorilorcare au o frecventa de uilizare de cel putin 20% si acceseaza in total cel putin 80% din date. Din acest punct de vedere suntem interesati de determinarea predicatelor simple. Fie relatia r(A₁,A₂, . ,A_n), undeA_i este un atribut cu domeniul D_i, 1≤i≤n. un predicat simplu p_j definit pe r are forma : p_j: A_iθd, unde dID_i si θ este un comparator(<, ≤, =, >, ≥ , ) si d o valoare aleasa din domeniul atributului A_i. Notam cu p_i multimea tuturor predicatelor simple definite pentru relatia r_i.

Exemplu 2. Fie o instanta a relatiei proiect din figura anterioara. Denumire proiect='productie' este un predicat simplu ca si buget ≥20K

Totusi intrebarile utilizatorilor iunclud intrebari complexe care sunt combinatii de predicate simple. O combinatie de predicate simple care ne intereseaza se numeste predicat mintern care este o cojunctie de predicate simple, deoarece orice expresie booleana o putem transforma intr-o forma normala conjunctiva. Utilizarea predicatelor minterne in proiectarea algoritmilor nu restrange generalitatea. Fie o multime de predicate simple P_i= pentru relatia r_i. Multimea de predicate minterne M_i= este definita de

M_i= unde p_ik^*=p_ik sau ┐p_ik.

Orice predicat simplu poate fi cuprins intr-un predicat mintern fie in forma naturala, fie in forma negata. Referinta la negatia unui predicat se refera numai la predicatele care contin operatorul de egalitate, adica de forma A=valoare. Pentru predicatele care contin inegalitate, negarea unui predicat simplu de forma A≤v este inlocuita cu predicatul A>v. In afara de problemele teoretice, negarea complementului in multimi infinite, complementul poate fi dificil de definit. De exemplu doua predicate simple de forma

Margine_inferioara ≤ atribut₁

Atribut₁ ≤ margine_superioara, cu complementele lor

(Margine_inferioara ≤ atribut₁)

┐(Atribut₁ ≤ margine_superioara)

Cele doua predicate simple pot fi scrise intr-unul singur

margine_inferioara ≤ atribut₁ ≤ margine_superioara, cu complementul

┐(Margine_inferioara ≤ atribut₁ ≤ margine_superioara), care nu este usor de definit.

Exemplul 3.Consideram relatia de calificare C pentru care dam cateva predicate simple posibile:

p₁ : Titlu='analist'

p₂ : Titlu='progamator'

p₃ : Titlu='profesor'

p₄ : Titlu='inginer mec'

p₅ : Titlu='inginer calc'

p₆ : Salariu≤60K

p₇ : Salariu>60K

Dam exemple de predicate minterm care pot fi definite pe baza acestor predicate simple.

m₁: Titlu='analist' Salariu≤6000

m₂: Titlu='analist' Salariu>6000

m₃: Titlu='programator' Salariu≤6000

m₄: Titlu='progamator' Salariu>6000

m₅: Titlu='inginer mec' Salariu≤4500

m₆: Titlu=' inginer mec' Salariu>4500

Exista doua observatii care pot fi facute:

a) Nu exista orice predicat mintern ce poate definit, ca de exemplu m₄.

b) Cateva predicate pot avea sens cand sunt date semanticile relatiei r. Informatia cantitativa despre aplicatia utilizatorului cuprinde urmatoarele doua multimi:

1) Selectivitatea minternului - numarul de tupluri din relatie ce ar trebui accesate de intrebarea utilizatorului specificata de un predicat mintern dat

De exemplu selectivitatea lui m₁ in C este 0 deoarece nu exista nici un tuplu in relatia de decodificare unde un analist sa aiba salariul mai mic de 6000. Pe de alta parte selectivitatea lui m₂ este 1.

2) Frecventa de accesare cu care aplicatiile utilizatorului acceseaza datele. Daca

Q=(q₁,q₂,,q_p) este o multime de intrebari ale utilizatorilor, acc(q_i) indica frecventa de accesare a intrebarii q_i intr-o perioada data. Frecventa de acces ale minternelor sunt

determinate de frecventele de acces ale componentelor date de predicatele simple.

Fragmentarea orizontala primara

Fragmentarea orizontala primara este definita ca o opetatie de selectie pentru relatia sursa (owner). Prin urmare, fiind data o relatie r_i, un fragment orizontal al ei este dat de

r_i^j=σ_Fj(r_i) , 1≤j≤k,

unde F_j este o formula de selectie utilizata pentru a obtine fragmentul r_i^j. Daca F este o formula normala conjunctiva atunci ea este un predicat mintern m_ij. Algoritmii care sunt dati sunt pentru predicate minterne.

Exemplul 4. Descompunerea relatiei proiecte in fragmentele Proiecte1 si Proiecte2 din exemplul 1.

Proiecte1=σ_Buget≤20(Proiecte) Proiecte2=σ_Buget>20(Proiecte)

Aceste probleme pot fi rezolvare in practica prin limitarea domeniilor atributelor in concordanta cu cerintele aplicatiilor. Consideram relatia Proiecte

Proiecte(IdProiect Denumire Buget Loc)

P1 Productie    40 Buc

P2 DezvoltareBD 35 CR

P3 CAD/CAM 20 CR

P4 Intretinere 30 CJ

PR₁=σ_LOC=BUC(Proiecte),

PR₂=σ_LOC=CR(Proiecte),

PR₃=σ_LOC=CJ(Proiecte).

Un fragment orizontal r_i al relatiei r consta din toate tuplurile din r care satisfac un predicat mintern m_i.Prin urmare fiind data o multime M de predicate minterne, exista o multime de fragmente orizontale corespunzatoare predicatelor minterne. Aceasta multime de fragmente orizontale sunt numite in mod obisnuit fragmente minterne. Prin urmare primul pas al oricarei fragmentari este sa determinam o multime de predicate simple cu anumite proprietati ca: minimalitatea, si completitudinea.

O multime de predicate P se numeste completa daca si numai daca pentru orice aplicatie exista o acceasi probabilitate de acces la orice doua tupluri care apartin oricarui fragment mintern ce sunt definite in concordanta cu P.

Este evident ca, completitudinea multimii de predicate este diferita de completitudinea regulilor de fragmentare.Consideram fragmentarea relatiei Proiect in raport cu atributul loc. Daca exista numai aplicatii care acceseaza relatia proiect, dorind sa accesam tupluri in raport cu Localitatea, multimea este completa deoarece fiecare tuplu al acestui fragment proiect_i are acceasi probabilitate de accesare. Daca ar exista o aplicatie care ar accesa tuplurile care au un buget mai mic de 20, atunci P nu este complet. Unele tupluri au probabilitati mai mari de a fi accesate datorita acestei aplicatii. Pentru a face multimea P de predicate completa trebuie sa adaugam predicatele

(Buget≤20, Buget>20),

P=.

Completitudinea este o proprietate necesara deoarece o multime completa de predicate ne permite sa definim o multime de predicate minterne in raport cu care se realizeaza fragmentarea orizonatala primara. Fragmentele obtinute in acest mod nu sunt numai uniforme din punct de vedere logic, in sensul ca ca ele satisfac predicatul mintern, dar sunt omogene din punct de vedere statistic. Vom da o definitie formala a completitudinii astfel ca sa ne permita obtinerea unei multimi complete pe baza unui algoritm.

Totusi, aceasta va cere ca proiectantul sa specifice probabilitatiile de acces pentru fiecare tuplu al unei relatii pentru fiecare aplicatie considerata. Vom prezenta pe scurt un algoritm de obtinere al acestei multimi. A doua proprietate a multimii de predicate minterne in raport cu care se realizeaza fragmentarea este minimalitatea.

Ea arata ca, daca un predicat influenteaza modul cum se realizeaza fragmentarea (adica cum un fragment F este fragmentat in f_i,f_j) ar trebui sa existe cel putin o aplicatie care sa acceseze in mod diferit f_i, f_j. Cu alte cuvinte, predicatul simplu ar trebui sa fie relevant in determinarea unei fragmentari. Daca toate predicatele din multimea P sunt relevante, atunci P este minimala. O definitie formala a relevantei a fost data de Ceri in 1982. Fie m_i, m_j doua predicate minterm care sunt indentice in definitia lor, cu exceptia ca m_i contine un singur predicat simplu p_i si m_j contine pe p_i. Astfel fragmetele f_i,f_j sunt definite in raport cu m_i, m_j.

Atunci p_j este relevant daca si numai daca

.

Exemplu 5: Multimea P de predicate este completa si minimala, dar daca se mai adauga Nume="instrumentare" nu mai este minimala deoarece predicatul este nerelevant in raport cu P. Nu exista nici o aplicatie care ar trebui sa acceseze fragmentele rezultate in mod diferit. Vom prezenta un algoritm care genereaza o multime completa si minimala de predicate P' dintr-o multime simpla de predicate P. Acest algoritm se numeste COMMIN.

Regula R1 este o regula de completitudine si minimalitate daca o relatie sau un fragment este partitionat in cel putin doua parti care sunt accesate in mod diferit de cel putin de o aplicatie.

Notam cu f_i IP' un fragment definit in raport cu un predicat minterm definit de predicatele din P'. In continuare dam un algoritm care dintr-o multime de predicate simple determina o multime completa si minimala P'.

START [ ComMin ]

INPUT

CALL relvar (P, r; p_i, f_j)

P'

P P-

F

WHILE P' nu e completa

7.1 CALL relvar (P, p_k ;p_j, f_j)

7.2 P' P'

7.3 P P-

7.4 F F

7.5 IF p_kIP'care nu e relevant

Then

.1. P' P'-

.2. F F-

7.6 CONTINUE

7. STOP

Procedura relvar determina un p_jIP astfel ca p_j sa partitioneze un fragment f_k determinat de P in concordanta cu regula R1. Algoritmul incepe cu gasirea unui predicat care este relevant si care partitioneaza relatia de intrare. In ciclul while se adauga predicate la aceasta multime ce pastreza minimalitatea la fiecare pas.

Al doilea pas in fragmentarea orizontala este obtinerea multimii de predicate minterm ce pot fi definite de o multime de predicate P . Aceste predicate minterm determina fragmentele care sunt utilizate in pasul de alocare. Determinarea fiecarui predicat minterm este triviala, dificultatea este ca, multimea de predicate minterm este foarte mare (de ordin , unde n este numarul de predicate simple). In pasul urmator vom determina modul de reducere al predicatelor minterm ce sunt necesare in fragmentare. In al treilea pas se face eliminarea unui anumit fragment ce poate fi nesemnificativ. Aceasta eliminare este realizata prin identificarea acelor mintermuri ce pot fi contradictorii cu o multime de implicatii I data.

De exemplu daca P=, unde

p₁: atr=v₁

p₂: atr=v₂ si dom(atr)-,

Evident ca I contine doua implicatii care sunt definite astfel:

i₁: (atr=v₁)T (atr=v₂)

i₂: (atr=v₁)T(atr=v₂).

Sunt definite astfel urmatoarele patru predicate in raport cu P':

m₁: (atr=v₁) (atr=v₂)

m₂: (atr=v₁) (atr=v₂)

m₃: (atr=v₁) (atr=v₂)

m₄: (atr=v₁) (atr=v₂) .

In acest caz predicatele minterne m₁, m₄ sunt contradictorii in raport cu implicatia I, si prin urmare pot fi eliminate din M. Aceasta sta la baza algoritmului Porizontal. Intrarea in acest algoritm este o relatie r_i care este supusa fragmentarii orizontale cu ajutorul predicatelor simple din multimea P, care a fost determinata in raport cu aplicatiile definite pentru o relatia r_i.

START [ Porizontal ]

INPUT

CALL ComMin

CALL DetMin(P_i',M_i)

CALL DImp(P',I)

FOR fiecare m_i I M_i

0.1 IF m_i= contradictoriu in I

THEN

5.1.1 M_i M_i-

5.2 CONTINUE

6. OUTPUT

7. STOP.

Procedura DetMin detetrmina multimea de predicate minterm. Procedura DImp determina multimea I de implicatii determinate de p_iIP'.

Exemplu: Sa consideram baza de date obtinuta prin selectie din relatia proiect.

r₁= _BUGET≤1000(proiect)

r₂= _BUGET>1000(proiect)

Presupunem ca exista numai o aplicatie care acceseaza relatia profesie(Titlu, Salariu). Aplicatia verifica informatiile despre salariu si determina suma corespunzatoare. Presupunem ca, inregistrarile sunt gestionate in doua locuri, unul unde sunt gestionate salarii mai mici ca 5 mii si altul in care sunt manipulate salariile mai mari ca 5mii. Exista intrebari care se refera la doua statii. Predicatele simple ce vor fi utilizate la partitionarea relatiei ''profesie'' sunt:

p₁=Sal≤5000

p₂=Sal>5000

Fie initial, multimea P=. Aplicand algoritmul ComMin lui P se arata ca este completa si minimala. Vom forma urmatoarele predicate minterm ca termeni ai lui M:

m₁ : (Sal≤5000) (Sal>5000),

m₂ : (Sal≤5000) (Sal>5000),

m₃ : Sal≤5000) (Sal>5000),

m₄ : Sal≤5000) (Sal>5000).

Presupunem ca domeniul atributului Sal poate fi impartit in doua, cum sugereaza p₁ si p₂, urmatoarele implicatii sunt evidente.

In raport cu I predicatul mintern m₁ este contradictoriu cu i₁ si m₄ este contradictoriu cu i₂. Prin urmare M= In plus, i₁ si i₄ reduce specificarea lui m₁ la p₁ si similar m₃ se reduce la p₂ datorita lui i₂ si i₃.

r₁ (Titlu Sal) r₂(Titlu Sal)

ing. mec. 2700 Analist 4000

Programator 3800 ing. el. 3400

Exista doua fragmente definite in raport cu M.

Impreuna i₁ si i₄ reduc specificatia lui m₂ la p₁ si similar reducem m₃ la p₂ datorita lui i₂ si lui i₃. Prin urmare definim doua fargmente F= in concordanta cu M.

S₁(Titlu Sal) S₂(Titlu Sal)

Ing. mec. 2700 ing. electronist 3400

Programator 3800 Analist sistem 4000

Fragmentarea orizontala a relatiei salariati (S). Vom considera urmatoarea relatie. Presupunand ca exista doua aplicatii. Mai intai la trei site-uri si sa cautam numele si bugetele proiectelor dand numarul lor. In notatia SQL intrebarea este :

SELECT S.Nume, Buget

FROM salariati S

WHERE Sal=valoare

Pentru aceasta aplicatie predicatele simple care ar trebui utilizate sunt urmatoarele:

p₁ LOC='Montreal'

p₂ LOC='Paris'

p₃ LOC='New York'

Aplicatia a doua se reduce la 2 site-uri pe care ar trebui sa se gestioneze proiectele.Acele proiecte ce au bugetul mai mic decat 20 sunt gestionate pe un site in timp ce celelalte cu bugetul mai mare sunt gestionate pe un al doilea site. Astfel aplicatiile simple ce ar trebui sa fie utilizate la fragmentare in concordanta cu a doua aplicatie sunt :

p₁: Buget

p₂: Buget > 20

Aplicatia algoritmului ComMin conduce la obtinerea lui P'= care este completa si minimala. Bazata pe P' pot fi definite urmatoarele predicate minterm ce formeaza M.

m₁: (Loc=Montreal) (Buget≤20)

m₂: (Loc=Montreal) (Buget>20)

m₃: (Loc=NewYork) (Buget≤20)

m₄: (Loc= NewYork) (Buget>20)

m₅: (Loc=Paris) (Buget≤20)

m₃: (Loc=Paris) (Buget>20)

Fragmentarea orizontala derivata

O fragmentare orizonatala derivata este definita pe o relatie membru(fiu a unei legaturi in raport cu un operator de selectie specificat pentru relatia parinte(tata). Legatura dintre relatiile tata si fiu sunt definite de operatorul de echiunire (Equijoin). Operatorul de echiunire putem sa-l definim printr-o semiunire. Aceasta este importanta deoarece vom partitiona relatia membru in concordanta cu fragmentele relatiei parinte, deci fragmentele rezultate sa fie numai pentru atributele relatiei membru. In concordanta cu legatura L unde

Owner(L)=s

Member(L)=r

Se numeste fragment orizontal derivat r_i=s_i si ≤i≤n unde n este numarul maxim de fragmente distincte care vor fi definite pe r si s_i σ_Fi(s) unde F_i este formula in raport cu care este definit fragmentul orizontal primar s_i. Fie relatiile r de schema R si s de schema S cu atributele AIR si BIS cu dom(A)=dom(B). Se numeste semiunire a relatiei r sau s notata cu multimea tuturor tuplurilor t din r ce pot participa la unirea cu un tuplu din s.

rs=π_R(rs)= π_R®π_{R S}(S)=rπ_{R S}(S)

Fie r(R) si s(A), AIR, , dom(A)=dom(B)

Intr-o schema a unei baze de date exista in mod obisnuit mai mult de doua legaturi intre relatiile de schema R si S. In acest caz exista mai multe fragmentari posibile. Alegerea unei fragmentari se bazeaza pe unul din criteriile urmatoare:

1 Se alege fragmentarea cu cele mai bune caracteristici de unire (join) adica sa

raspunda la intrebarile care necesita unirea relatiilor de scheme R si S prin

folosirea de fragmente cat mai mici sau a unor algoritmi de unire

permanenti.

2 Fragmentarea este determinata de frecventa cu care aplicatiile acceseaza

datele din fragmentele componente si este utilizata de mai multe aplicatii.

Al doilea punct este cel mai important pentru BDD. Daca in plus, avem de executat un numar de intrebari de pe mai multe site-uri, vom putea executa orice intrebare in parallel, atunci timpul de raspuns sau total al sistemului se micsoreaza. Consideram unui graf de unire (al legaturilor) dintre fragmente. Daca exista numai o legatura care intra sau iese dintr-un fragment atunci graful se numeste simplu. Avantajul proiectarii unei relatii de unire cand graful este simplu este ca legatura poate fi alocata pe un site si member si owner-ul ei si unirile dintre diferite fragmente pot fi executate in paralel si independent.

S₁ S₂

E₁ E₂

Fig. Graful de unire dintre fragmente.

In mod obisnuit obtinerea unui graf de unire simplu nu este posibil. In acest caz, proiectarea se face pe baza unui graf de unire partitionat.

Completitudinea este o proprietate dorita deoarece multimea de predicate ne da posibilitatea sa definim numai multimea de predicate minterne in raport cu care realizam fragmentarea orizontala.Fragmentele obtinute pe aceasta cale nu sunt numai uniforme din punct de vedere logic, dar si omogene din punct de vedere statistic. Este posibil sa definim formal completitudinea care sa permita sa se obtina o multime de predicate in mod automat. Aceasta necesita ca proiectantul sa specifice probabilitatea de acces pentru fiecare tuplu al fiecarei aplicatii considerate. Aceasta nu cere mai multa munca ci apeleaza la elementele BD si la experiensa proiectantului pentru a gasi o multime completa.