Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme
Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» Fragmentarea datelor - logica fragmentarii


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:

1.      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 r1, r2,. . . ,  rk atunci fiecare element de data  ce poate fi gasit in relatia r trebuie sa fie gasit in cel putin un fragment ri, 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 R1, R2,.. . , RK sunt schemele fragmentelor si F  o multime de dependente functionale pe R1, R2,.. . , RK si Fi=F|Ri, 1<=i<=k atunci F=UFi.       

3. Separabilitate. Daca r este o relatie si este  descompusa orizontal in fragmentele r1,rp, si elementul de data ti  se afla in rj atunci el nu se mai afla in nici un alt fragment rk, kj.  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 L1 din figura anteriara.  Vom defini doua functii owner si member care specifica sursa si destinatia legaturii.

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

              Owner(L1) = C,

              Member(L1)=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(A1,A2,…,An), undeAi este un atribut cu domeniul Di, 1≤i≤n. un predicat simplu pj definit pe r are forma :   pj: Aiθd, unde dIDi si  θ este un comparator(<, ≤, =, >, ≥ ,¹) si d o valoare aleasa din domeniul atributului Ai. Notam cu pi multimea tuturor predicatelor simple definite pentru relatia ri.

 

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 Pi= pentru relatia ri. Multimea de predicate minterne   Mi= este definita de

Mi= unde pik*=pik sau ┐pik.

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 ≤ atribut1

           Atribut1  ≤ margine_superioara,  cu complementele lor

           (Margine_inferioara ≤ atribut1)

           ┐(Atribut1 ≤ margine_superioara)

Cele doua predicate simple pot fi scrise intr-unul singur

              margine_inferioara ≤ atribut1 ≤ margine_superioara,  cu complementul

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

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

                             p1 : Titlu=’analist’

                             p2 : Titlu=’progamator’

                             p3 : Titlu=’profesor’

                             p4 : Titlu=’inginer mec’

                             p5 : Titlu=’inginer calc’

                             p6 : Salariu≤60K

                             p7 : Salariu>60K

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

                          m1:  Titlu=’analist’ ÙSalariu≤6000

                          m2:  Titlu=’analist’ ÙSalariu>6000

                          m3:  Titlu=’programator’ ÙSalariu≤6000

                          m4:  Titlu=’progamator’ÙSalariu>6000

                          m5:  Titlu=’inginer mec’ÙSalariu≤4500

                          m6:  Titlu=’ inginer mec’ÙSalariu>4500

           

Exista doua observatii care pot fi facute:

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

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

1)  Selectivitatea minternuluinumarul de tupluri din relatie  ce ar trebui accesate de  intrebarea utilizatorului specificata de un predicat mintern dat.

De exemplu selectivitatea  lui m1 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 m2 este 1.

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

      Q=(q1,q2,,qp) este o multime de intrebari ale utilizatorilor, acc(qi) indica frecventa de   accesare  a intrebarii  qi 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  ri, un fragment orizontal al ei este dat de         

rijFj(ri) , 1≤j≤k,

unde  Fj este  o formula de selectie  utilizata pentru a obtine  fragmentul rij. Daca F este o formula normala conjunctiva  atunci ea este un predicat mintern  mij. 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

                       

 PR1LOC=BUC(Proiecte),

                         PR2LOC=CR(Proiecte),

                         PR3LOC=CJ(Proiecte).

           

Un fragment orizontal ri al relatiei r consta din toate tuplurile din r care satisfac un predicat mintern mi.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 proiecti 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 fi,fj) ar trebui sa existe cel putin o aplicatie care sa acceseze in mod diferit fi, fj. 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 mi, mj doua predicate minterm care sunt indentice in definitia lor, cu exceptia ca mi contine un singur predicat simplu pi si mj  contine pe ùpi. Astfel fragmetele fi,fj sunt definite in raport cu mi, mj.

Atunci pj 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 fi 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’.

1.      START [ ComMin ]





2.      INPUT

3.      CALL relvar (P, r; pi, fj)

4.      P’¬

5.      P¬P-

6.      F¬

7.      WHILE P’ nu e completa

7.1 CALL relvar (P, pk ;pj, fj)    

7.2 P’¬P’È

7.3 P¬P-

7.4 F¬FÈ

7.5 IF $pkIP’care nu e relevant

 Then

 .1. P’¬P’-

 .2. F¬F-

                  7.6 CONTINUE

            7. STOP

            Procedura relvar determina un pjIP astfel ca pj sa partitioneze un fragment fk 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

                        p1: atr=v1

                        p2: atr=v2  si dom(atr)-,

Evident ca I contine doua implicatii care sunt definite astfel:

                        i1: (atr=v1)Tù(atr=v2)

                        i2: ù (atr=v1)T(atr=v2).

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

            m1: (atr=v1)Ù(atr=v2)  

            m2: (atr=v1)Ùù(atr=v2) 

            m3: ù (atr=v1)Ù(atr=v2)

            m4: ù (atr=v1)Ùù(atr=v2)            .

            In acest caz predicatele minterne m1, m4  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 ri care este supusa fragmentarii orizontale cu ajutorul predicatelor simple din multimea P, care a fost determinata in raport cu aplicatiile definite pentru o relatia ri.

1.      START [ Porizontal ]

2.      INPUT

3.      CALL ComMin

4.      CALL DetMin(Pi’,Mi)

5.      CALL DImp(P’,I)

6.      FOR fiecare mi I Mi

0.1 IF mi= contradictoriu in I

THEN

5.1.1 Mi ¬Mi-

                   5.2 CONTINUE

            6. OUTPUT  

            7. STOP.

           

            Procedura DetMin detetrmina multimea de predicate minterm. Procedura DImp determina multimea I de implicatii determinate de piIP’.

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

r1=бBUGET≤1000(proiect)

r2=б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:

p1=Sal≤5000

p2=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:

                        m1 : (Sal≤5000) Ù(Sal>5000),

                        m2 : (Sal≤5000) Ùù(Sal>5000),

                        m3 : ù (Sal≤5000) Ù(Sal>5000),

                        m4 : ù (Sal≤5000) Ùù (Sal>5000).

Presupunem ca  domeniul atributului Sal poate fi impartit  in doua, cum sugereaza p1 si p2, urmatoarele  implicatii sunt evidente.

    

           

           

           

In raport cu I predicatul mintern m1 este contradictoriu  cu i1 si m4 este contradictoriu cu i2. Prin urmare M=  In plus, i1 si i4 reduce  specificarea lui m1 la p1 si similar m3 se reduce la p2 datorita lui i2 si i3.

 r1 (Titlu              Sal)                                  r2(Titlu             Sal)

     ing. mec.       2700                                     Analist         4000

     Programator  3800                                     ing. el.         3400

Exista  doua fragmente definite in raport cu M.

Impreuna i1 si i4 reduc specificatia lui m2 la p1 si similar  reducem  m3 la p2 datorita lui i2 si lui i3. Prin urmare definim doua fargmente  F= in concordanta  cu M.

S1(Titlu             Sal)                             S2(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:

p1       LOC=’Montreal’

p2       LOC=’Paris’

p3       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 :

p1: Buget £ 20

p2: 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.

                        m1: (Loc=Montreal) Ù(Buget≤20)

                        m2: (Loc=Montreal) Ù(Buget>20)

                        m3: (Loc=NewYork) Ù(Buget≤20)

                        m4: (Loc= NewYork) Ù(Buget>20)

                        m5: (Loc=Paris) Ù(Buget≤20)

                        m3: (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 ri=si  si 1≤i≤n      unde n este  numarul maxim de fragmente  distincte  care vor fi definite  pe r1 si si=σFi(s) unde Fi este formula in raport cu care  este definit fragmentul  orizontal  primar si. 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.

    S1                                          S2  

           

    E1                                          E2

    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.  



loading...




Copyright © 2017 - Toate drepturile rezervate

Informatica


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word


Descrierea pachetului de programe TURBO-ASSEMBLER
HARDWARE
NOTIUNI DE ALGEBRA LOGICA (BOOLEANA)
Editarea suprafetelor 3D pornind de la desene 2D
Stive si Cozi - Creare. Inserare. Stergere.
Dezvoltare in spirala
Antrenarea retelelor neurale
Mediul si limbajul de programare VISUAL BASIC
Structura Sistemelor de Operare
Proiect atestat de specialitate informatica - farmacie












loading...