Sisteme de Baze de Date Distribuite

. INTRODUCERE

Sistemele de baze de date (BD) au cunoscut o trecere de la o paradigmă a procesării datelor în care fiecare aplicație își definește și menține propriile sale date la una în care acestea sunt definite și administrate centralizat. În ultimii ani, bazele de date distribuite (BDD), următorul pas în dezvoltarea sistemelor de baze de date, au devenit un sector important al prelucrării informațiilor și se poate anticipa că importanța lor va crește rapid schimbând modul de lucru de la centralizat la descentralizat. Această tendință este motivată atât organizatoric cât și tehnologic, întrucât BDD elimină multe din neajunsurile BD centralizate, creează numeroase avantaje și sunt binevenite pentru descentralizarea structurilor organizatorice. Nevoile care au condus la dezvoltarea BDD au făcut necesară introducerea de noi facilități care constituie avantajele BDD, avantaje care urmează a fi prezentate pe parcursul acestei lucrări.

. DEFINIȚII ȘI CONCEPTE

În această parte a lucrării vom da câteva definiții pentru a alcătui un limbaj propriu BDD.

O BDD reprezintă o colecție de date integrate din punct de vedere logic care sunt fizic distribuite pe stații ale unei rețele de calculatoare. Fiecare stație din rețea are autonomie de prelucrare care îi permite să realizeze aplicații locale, aplicații care sunt executate în întregime de computerul stației. De asemenea, fiecare stație participă la execuția a cel puțin unei aplicații globale care necesită accesarea datelor din mai multe stații.

Pentru a înțelege mai bine vom dezvolta puțin noțiunile de integrare logică și distribuire fizică:

integrare logică: un utilizator interacționează cu BDD în același fel ca și în cazul BD centralizate și, în general, nu are informații despre localizarea datelor pe stații;

distribuire fizică: BD este partiționată fizic pe stațiile dintr-o rețea (se admit copii ale fragmentelor memorate pe stații diferite).

Fiecare stație are o BD locală alcătuită din toate datele stocate pe acea stație. Aceste BDL se integrează în BDD prin intermediul unei scheme globale la care va face referire orice utilizator global.

Un utilizator local reprezintă un utilizator care are acces și exploatează o BDL (cunoaște și manipulează numai schema acelei BDL).

Un utilizator global este un utilizator care cunoaște și are acces la schema întregii BD. Utilizatorul global exploatează schema globală conform autorizărilor și drepturilor sale de acces.

Pentru a distribui fizic BD pe diverse stații aceasta trebuie fragmentată conform unor principii și condiții de optimalitate care vor fi tratate pe larg în capitolul .

Un sistem de gestiune a bazei de date distribuite este software-ul care permite gestiunea unei BDD și face distribuirea transparentă pentru utilizatori.

. SISTEMUL DE GESTIUNE A BAZELOR DE DATE DISTRIBUITE (SGBDD)

.1. DEFINIȚIE

Am văzut în că un SGBDD este, de fapt, software-ul care permite gestionarea unei BDD și face distribuirea transparentă pentru utilizatori. BD este divizată într-un număr de fragmente, fiecare fragment fiind memorat pe unul sau mai multe calculatoare din rețea.

SGBDD are următoarele componente software:

componenta de comunicație (CC);

sistemul de gestiune a bazei de date locale (SGBDL);

dicționarul de date global (DDG);

sistemul de gestiune al bazei de date distribuite (SGBDD).

Componenta de comunicație este cea care realizează legăturile în cadrul rețelei. Cuprinde descrierea completă a nodurilor (stațiilor) și legăturilor din cadrul rețelei.

Sistemul de gestiune a bazei de date locale este un sistem standard de gestiune a bazelor de date.

Dicționarul de date global cuprinde informații despre BDD: localizarea, structura, disponibilitatea și modul de utilizare a datelor.

SGBDD propriu-zis cuprinde un sistem complex de programe care asigură interfața între BDD și utilizatorii acesteia.

.2. OBIECTIVELE UNUI SGBDD

Obiectivul informaticii îl constituie culegerea, verificarea, transmiterea, stocarea și prelucrarea automată a datelor cu ajutorul mijloacelor electronice de calcul, în scopul satisfacerii diferitelor nivele de conducere cu informații necesare luării deciziilor, în condiții de eficiență economică sporită.

În condițiile exploziei informaționale, cerința acută de informare trebuie satisfăcută ținând seama de o serie de condiții care să asigure: minimizarea costului procesului de prelucrare a datelor, creșterea vitezei de răspuns la întrebările solicitate de utilizatori, adaptabilitatea sistemului informatic la evoluția în timp a sistemului informațional din care face parte, posibilitatea folosirii sistemului de informare dispunând de un minim de cunoștințe despre modul de organizare a lui în general și informatică în special, integritatea și securitatea datelor etc.

În acest context, unui SGBD, nu neapărat distribuit, îi revin o serie de puncte de vedere: logic și fizic. Independența logică a datelor se referă la posibilitatea adăugării de noi articole sau extinderea structurii conceptuale fără a afecta programele existente. Independența fizică a datelor face ca memorarea lor și tehnicile fizice de memorare să poată fi modificate fără a determina rescrierea programelor de aplicație.

asigurarea unei redundanțe minime și controlate a datelor din BD: stocarea datelor astfel încât fiecare dată să apară o singură dată este optimă din punct de vedere al spațiului de memorare. Totuși, pentru a realiza performanțe sporite (minimizarea timpului de acces la date și a timpului de răspuns la solicitările utilizatorilor) este necesar a adopta o redundanță a datelor, instituindu-se, însă, un control automat asupra ei în vederea asigurării coerenței datelor din bază.

sporirea gradului de securitate a datelor împotriva accesului neautorizat la ele (administratorul BD hotărăște cui permite accesul la date și cui nu).

asigurarea integrităților datelor împotriva unor ștergeri intenționate sau neintenționate, prin intermediul unor proceduri de validare, a unor protocoale de control concurent și a unor proceduri de refacere a bazei de date după incidente.

În cazul SGBDD apar diverse nuanțări ale obiectivelor de mai sus, precum și noi obiective:

asigurarea transparenței distribuției: programele pot fi scrise făcând abstracție de distribuirea fizică a datelor, mutarea datelor de pe o stație pe alta afectând doar viteza de execuție, nu și corectitudinea programului.

redundanța datelor, în cazul BDD, devine o caracteristică dezirabilă, din mai multe motive:

localizarea este mai rapidă atunci când datele sunt replicate la stațiile unde sunt cerute de aplicații;

crește disponibilitatea, siguranța sistemului, în cazul căderii unei stații aplicațiile fiind dirijate spre stațiile unde datele sunt replicate.

Redundanța datelor reduce efortul de regăsire a datelor dar crește efortul de actualizare. Evaluarea unui grad optim al redundanței trebuie să țină seama de raportul între accesele de regăsire și accesele de actualizare a datelor.

asigurarea securității datelor: administratorul fiecărei BDL își realizează propria protecție fără să depindă de un administrator central; comunicația în rețea poate reprezenta un punct slab în realizarea protecției.

transmiterea datelor la utilizatorii lor: indiferent care este nodul în care se află un utilizator și indiferent unde se află datele, utilizatorul trebuie să-și poată obține informațiile de care are nevoie (cu condiția să aibă autorizarea de a le accesa).

evitarea centralizării datelor deoarece aceasta poate provoca un cost ridicat de prelucrare și transmitere a datelor la utilizatori.

proiectarea structurii organizatorice și funcționale a sistemului analizat: prin faptul că, în general, BDL se află în locurile în care se produc informațiile pe care le conțin, o arhitectură distribuită permite modelare mai bună a sistemului informațional, conform structurii organizatorice și funcționale.

posibilitatea accesului la BDD privită ca un sistem integrat: BDD trebuie să fie văzută de utilizator ca o BD centralizată.

.3. FUNCȚIILE UNUI SGBDD

Pentru realizarea obiectivelor de mai sus, SGBD, în general, dispun de o serie de componente ce permit efectuarea a numeroase operații. În funcție de natura lor și scopul urmărit, operațiile pot fi grupate pe activități. Activitățile acceptă și ele o grupare pe funcții (una sau mai multe activități, relativ omogene, vor realiza o anumită funcție). Ținând seama de multitudinea sarcinilor ce revin unui SGBD și grupând aceste sarcini pe activități și apoi pe funcții, în final pot fi deduse funcțiile sistemului de gestiune.

În continuare ne propunem să enumerăm unele dintre funcțiile unui SGBDD:

funcția de definire a datelor: la nivelul acestei funcții, cu ajutorul limbajului de definire a datelor, se descriu multitudinea atributelor din cadrul structurii BD, legăturile dintre entitățile BD, se definesc eventuale criterii de validare a datelor, metode de acces la date, aspecte referitoare la asigurarea integrității și confidențialității datelor. Tot în cadrul acestei funcții se descriu detaliile privitoare la distribuirea datelor și la fragmentarea acestora. Rezultatul celor expuse în cadrul acestei funcții este catalogul BDD.

funcția de manipulare a datelor: realizează următoarele activități: crearea BD, actualizarea și interogarea/extragerea datelor;

funcția de utilizare asigură mulțimea interfețelor necesare pentru comunicarea tuturor utilizatorilor cu baza de date;

funcția de administrare a BD este de competența administratorului BD;

funcția de transport: realizează accesarea stațiilor îndepărtate, transmiterea datelor prin rețea;

funcția de optimizare a cererilor distribuite: optimizarea se face pe baza informațiilor conținute în catalogul BDD.

.4. ARHITECTURA DE REFERINȚĂ A SGBDD

Spre deosebire de cazul SGBD centralizate unde există o arhitectură general acceptată, în cazul SGBD distribuite este mai dificil de prezentat o asemenea arhitectură dată fiind diversitatea SGBDD.

Arhitectura propusă de raportul ANSI/SPARC este cea mai larg răspândită. Această arhitectură este una multinivel pentru a realiza unul din principalele obiective ale SGBDD, și anume transparența distribuției.

Schema

globală

Schema

fragmentării nivelul global

Schema

de alocare

Schema Schema . . .

locală 1 locală 2 alte stații

SGBD 1 SGBD 2 nivelul local

BD 1 BD 2

Fig. 1. Arhitectura SGBDD.

Această arhitectură nu este implementată explicit în toate SGBDD dar nivelele ei prezentate conceptual ne ajută să înțelegem modul de organizare a BDD.

Nivelul global permite integrarea BDL într-o BD globală prin intermediul schemei globale, schemei fragmentării și schemei de alocare.

Schema globală este o descriere a BDD, descrierea fiind asemănătoare cu cea a unei BD centralizate.

Pentru a putea înțelege mai bine semnificația celorlalte două scheme din cadrul acestui nivel vom utiliza în continuare modelul relațional, cel mai utilizat model în domeniul bazelor de date.

În cadrul modelului relațional, schema globală este descrisă de un set de relații globale.

Fiecare relație globală poate fi împărțită în mai multe părți disjuncte numite fragmente. Corespondența între o relație globală și fragmente este definită de schema de fragmentare. Această corespondență este de tipul “unul la mulți” (mai multe fragmente corespund unei relații globale dar numai o relație globală corespunde unui fragment).

Fragmentele sunt porțiuni logice ale relațiilor globale care pot fi alocate fizic pe una sau mai multe stații ale rețelei. Schema de alocare definește stația sau stațiile unde sunt alocate fragmentele. Maniera de definire a schemei de alocare determină dacă BDD este redundantă sau neredundantă. Toate fragmentele care corespund aceleiași relații globale și sunt situate pe aceeași stație constituie imaginea fizică a relației la stația respectivă, fiecare fragment fiind o copie a fragmentului definit în schema de fragmentare.

Două imagini fal permite integrarea BDL într-o BD globală prin intermediul schemei globale, schemei fragmentării și schemei de alocare.

Schema globală este o descriere a BDD, descrierea fiind asemănătoare cu cea a unei BD centralizate.

Pentru a putea înțelege mai bine semnificația celorlalte două scheme din cadrul acestui nivel vom utiliza în continuare modelul relațional, cel mai utilizat model în domeniul bazelor de date.

În cadrul modelului relațional, schema globală este descrisă de un set de relații globale.

Fiecare relație globală poate fi împărțită în mai multe părți disjuncte numite fragmente. Corespondența între o relație globală și fragmente este definită de schema de fragmentare. Această corespondență este de tipul “unul la mulți” (mai multe fragmente corespund unei relații globale dar numai o relație globală corespunde unui fragment).

Fragmentele sunt porțiuni logice ale relațiilor globale care pot fi alocate fizic pe una sau mai multe stații ale rețelei. Schema de alocare definește stația sau stațiile unde sunt alocate fragmentele. Maniera de definire a schemei de alocare determină dacă BDD este redundantă sau neredundantă. Toate fragmentele care corespund aceleiași relații globale și sunt situate pe aceeași stație constituie imaginea fizică a relației la stația respectivă, fiecare fragment fiind o copie a fragmentului definit în schema de fragmentare.

Două imagini fizice ale unei relații globale la stații diferite pot fi identice.

Nivelul local permite tratarea fiecărei BDL ca o bază de date centralizată. La acest nivel este necesară realizarea corespondenței între imaginea fizică și obiectele manipulate de SGBD locale. Acest lucru este realizat de schema locală de reprezentare a datelor care depinde de tipul de SGBD local.

Referitor la transparența distribuției și la alte aspecte privind transparența în cazul SGBDD vom discuta mai pe larg într-unul din capitolele următoare.

II.5. SGBDD OMOGENE ȘI ETEROGENE

O caracteristică importantă a SGBDD este omogenitatea sau eterogenitatea acestora. SGBDD este omogen atunci când toate SGBDD locale sunt de același fel. Un SGBDD eterogen implică existența a cel puțin două SGBDD locale diferite.

Sistemele omogene sunt mai ușor de proiectat și au unele avantaje, cum ar fi: adăugarea de noi stații sistemului se poate face ușor, se mărește performanța exploatând posibilitatea procesării paralele pe mai multe stații.

Sistemele eterogene rezultă, de obicei, când stații individuale își implementează propriile BD, de abia mai târziu punându-se problema integrării lor într-un singur sistem. Comunicarea între SGBD-uri este esențială. Sistemele eterogene trebuie să asigure transparența SGBD, aceasta echivalând cu faptul că un utilizator poate face cereri în limbajul SGBD local. După ce o cerere este făcută sistemul are sarcina localizării datelor și a efectuării tuturor translațiilor necesare. Datele necesare satisfacerii cererii pot fi localizate la o stație care poate avea:

hardware diferit;

aplicații diferite ale SGBD;

și una și alta.

Dacă diferă hardware-ul dar SGBD sunt identice atunci translațiile implică schimbări de coduri și lungimi de cuvinte. Dacă hardware-ul este identic dar SGBD diferă atunci translațiile sunt mai complicate, implicând transformarea logică a unui model de date într-un alt model de date (de exemplu, relațiile din modelul relațional devin înregistrări și realizări în modelul relațional). Poate fi necesară chiar și traducerea cererilor dintr-un limbaj în altul.

Soluția folosită de SGBDD eterogene este o multitudine de porți (gateways) care traduc limbaje și transformă modele.

II.6. TRANSPARENȚE ÎN CADRUL SGBDD

Definiția SGBDD prezentată în II.1. afirmă că sistemul trebuie să facă distribuția transparentă pentru utilizator. Transparența ascunde detaliile implementării. De exemplu, în cazul SGBD centralizate independența datelor este o formă a transparenței – ascunde schimbările intervenite în definirea și organizarea datelor.

Un sistem distribuit poate oferi diferite nivele de transparență. În orice caz, toate aceste nivele au ca obiectiv “centralizarea” BDD (pentru utilizator).

Se pot identifica patru tipuri de transparență în cazul sistemelor distribuite:

transparența distribuției;

transparența tranzacțiilor;

transparența performanței;

transparența SGBD.

Transparența distribuției

Transparența distribuției permite utilizatorului să perceapă BD ca o entitate logic independentă. Dacă SGBDD oferă această transparență utilizatorul nu are nevoie să cunoască detalii despre fragmentarea (transparența fragmentării) sau despre localizarea datelor (transparența localizării).

Transparența fragmentării este cel mai înalt grad de transparență și se referă la faptul că utilizatorii sau programatorii aplicațiilor lucrează pe relațiile globale.

Transparența localizării este un nivel de transparență mai scăzut și presupune că utilizatorii cunosc detalii despre fragmentare dar nu cunosc unde sunt localizate datele. Principalul avantaj al transparenței localizării este acela că BDD poate fi fizic reorganizată fără a afecta programele de aplicație care o accesează. Separarea conceptului de fragmentare de conceptul de alocare (localizare) este util în proiectarea BDD pentru că în acest fel determinarea fragmentelor relevante este delimitată de problema alocării optime a datelor. Un alt tip de transparență legat de transparența localizării este transparența replicării, care se referă la faptul că utilizatorii nu au informații despre replicarea fragmentelor, sistemul fiind cel responsabil cu menținerea consistenței BD.

Pentru a oferi transparența denumirii (denumirea diferitelor părți din BD de pe diferite stații să fie diferite) una din stațiile sistemului trebuie să-și asume rolul de server de nume, a cărui responsabilitate este să asigure unicitatea numelor în sistem. Dacă sistemul oferă această transparență apar câteva dezavantaje, cum ar fi:

scăderea autonomiei locale;

scăderea performanței dacă serverul de nume este inundat cu cereri;

reducerea disponibilității dacă serverul de nume cade, stațiile rămase active nu pot crea noi părți ale BD.

O alternativă la serverul de nume ar fi ca fiecare stație să numească părțile BD stocate acolo cu un prefix propriu (de exemplu, adresa stației).

Transparența tranzacțiilor

Transparența tranzacțiilor într-un SGBDD asigură menținerea integrității și consistenței BDD în cazul tranzacțiilor distribuite. O tranzacție distribuită accesează date localizate pe mai multe stații. Fiecare tranzacție este împărțită într-un număr de sub-tranzacții, câte una pentru fiecare stație care trebuie accesată. SGBDD trebuie să asigure sincronizarea sub-tranzacțiilor cu tranzacțiile locale de la o anumită stație precum și sincronizarea sub-tranzacțiilor cu alte sub-tranzacții. Transparența tranzacțiilor este complicată de fragmentare, alocare și duplicare. Vom prezenta două aspecte ale transparenței tranzacțiilor: transparența concurenței și transparența căderilor de sistem.

Transparența concurenței

Dacă rezultatele tuturor tranzacțiilor concurente (distribuite sau nedistribuite) coincid cu rezultatul acelorași tranzacții executate însă serial, într-o oarecare ordine, spunem că sistemul oferă transparența concurenței. Asigurarea acestei transparențe este îngreunată de faptul că tranzacțiile locale sau globale nu trebuie să interfereze unele cu celelalte. În același timp SGBDD trebuie să asigure consistența tuturor sub-tranzacțiilor tranzacțiilor globale.

Duplicarea face problema concurenței una și mai grea. Dacă o dată care este duplicată este actualizată atunci actualizarea trebuie făcută tuturor copiilor. Cu cât sunt mai multe copii probabilitatea ca tranzacția să se încheie cu succes scade exponențial. Dacă unele stații care conțin copii ale datelor ce trebuie actualizate nu sunt accesibile atunci în momentul în care devin accesibile trebuie să-și actualizeze propriile copii.

Transparența căderilor de sistem

SGBDD trebuie să asigure un mecanism de regăsire (recuperare) a datelor în caz că apar unele defecțiuni în sistem. Pentru aceasta tranzacțiile sunt considerate atomice (sau toate operațiile presupuse de acea tranzacție sunt executate sau nici una dintre ele). În consecință, dacă o tranzacție s-a realizat atunci schimbările sunt permanente. Iată câteva din defecțiunile ce pot surveni: erori de programare, dezastre naturale, sabotaje, pierderi de mesaje, căderi ale unor linii de comunicație, căderea unei stații, partiționarea rețelei etc.

Transparența performanței

Transparența performanței solicită din partea SGBDD ca acesta să lucreze ca un sistem centralizat. Într-un mediu distribuit performanța unui sistem nu trebuie să scadă din cauza arhitecturii distribuite. Transparența performanței înseamnă, totodată, că SGBDD trebuie să determine strategia cea mai bună (din punct de vedere al costurilor) pentru a executa o cerere distribuită.

Transparența SGBDD

Transparența SGBDD ascunde față de utilizator faptul că SGBDD locale pot fi diferite. În consecință, această transparență poate fi oferită doar de sistemele eterogene.

v. PROIECTAREA BDD

v.1. NoȚiunea de distribuȚie

Modul de distribuire a informațiilor în cadrul BDD se bazează pe: fragmentarea (partiționarea) datelor și replicarea datelor.

FRAGMENTAREA DATELOR

Din punct de vedere al modelului relațional, descompunerea unei relații globale în fragmente poate fi realizată aplicând două tipuri de fragmentare:

fragmentarea orizontală – are ca rezultat relații cu aceeași structură, conținând o parte din tuplurile inițiale;

fragmentarea verticală – are ca rezultat relații care au ca structură o parte din atributele inițiale;

Fig. 2. Fragmentare orizontală.

Fig. 3. Fragmentare verticală.

fragmentare mixtă.

Fig. 4. Fragmentare mixtă.

Există câteva reguli care trebuie respectate în definirea fragmentelor:

Condiția de completitudine: întreaga relație globală trebuie partajată în fragmente. Cu alte cuvinte, un articol care aparține relației globale care se fragmentează nu se poate să nu aparțină nici unui fragment.

Condiția de reconstrucție: în orice moment trebuie să fie posibil să reconstruim relația globală din fragmentele ei.

Condiția de disjuncție: este util ca fragmentele să fie disjuncte pentru ca astfel replicarea datelor să poată fi controlată explicit la nivelul alocării datelor.

REPLICAREA DATELOR

O bază de date este replicată dacă există mai multe copii ale acelorași informații. Din punct de vedere al replicării, o BD poate fi:

nereplicată – atunci când în sistem există o singură copie asignată unui nod și care rezidă numai pe acel nod.

parțial replicată – atunci când există informații care sunt replicate și informații care nu sunt replicate.

complet replicată – atunci când întreaga BD este în întregime replicată pe una sau mai multe stații.

Tehnicile de replicare și fragmentare pot fi aplicate succesiv pe aceeași relație. Astfel, un fragment poate fi replicat iar unitățile replicate pot fi fragmentate.

IV.2. ETAPELE PROIECTĂRII BDD

Comparativ cu proiectarea BD centralizate, proiectarea BDD este un proces mai complex. Stadiile care trebuiesc parcurse ar fi:

proiectarea schemei globale;

proiectarea schemei fizice;

proiectarea fragmentării;

proiectarea alocării.

Tehnica de abordare a proiectării schemelor globală și fizică a BDD este asemănătoare cu cea utilizată în cazul BD centralizate. Specifice BDD sunt problemele legate de proiectarea fragmentării și alocării datelor, probleme ce vor fi discutate în capitolele următoare.

Indiferent de modul de abordare, proiectarea BDD urmărește realizarea următoarelor obiective specifice:

Procesarea locală a datelor. Maximizarea procesării locale a datelor corespunde principiului simplu de a plasa datele cât mai aproape de aplicațiile care le solicită. Acest lucru presupune determinarea numărului de accese locale și a numărului de accese la distanță pentru fiecare fragment candidat și fragment alocat și alegerea acelui mod de distribuire a datelor care maximizează numărul de accese locale. Avantajul execuției complet locale a aplicației este dat nu numai de reducerea numărului de accese la distanță ci și de simplificarea controlului în execuția aplicației.

Siguranța și disponibilitatea datelor. Un grad ridicat de siguranță și disponibilitate a datelor este asigurat prin replicarea datelor pe mai multe stații. Sistemul poate să treacă la o copie alternativă atunci când cea care trebuie să fie accesată în condiții normale nu este disponibilă.

Procesarea paralelă a datelor. Distribuirea bazelor de date oferă posibilitatea de a beneficia eficient de capacitățile procesoarelor din fiecare stație pentru a maximiza gradul de paralelism în execuția aplicațiilor. În același timp, procesarea în paralel afectează negativ procesarea locală a datelor. Proiectarea BDD trebuie să asigure un raport optim între cele două tipuri de procesări.

IV.4. PROIECTAREA FRAGMENTĂRII

Înainte de a distribui datele, proiectarea fragmentării datelor determină modul în care relațiile globale vor fi divizate în unități logice care vor fi distribuite.

Iată câteva motive pentru fragmentare:

Utilizarea: în general, aplicațiile lucrează doar cu anumite părți ale unor relații.

Eficiență: datele vor fi memorate acolo unde sunt cele mai frecvent solicitate (dacă anumite date nu sunt solicitate de aplicațiile locale ale unei stații atunci nu vor fi memorate pe acea stație).

Paralelism: fragmentele fiind unitățile distribuției, o tranzacție va putea fi împărțită în mai multe subtranzacții care să opereze pe fragmente.

Securitate: date care nu sunt solicitate de aplicații locale nu sunt memorate pe respectivele stații, accesul diferiților utilizatori fiind astfel restrâns.

Există și dezavantaje ale fragmentării:

Performanța: va scădea performanța aplicațiilor care solicită date de la mai multe fragmente memorate pe stații diferite.

Integritatea: controlul integrității va deveni o problemă complexă în cazul în care un fragment va fi memorat pe mai multe stații.

Ne vom ocupa în continuare de cele trei tipuri de fragmentări prezentate în III.1.: orizontală, verticală și mixtă.

Fragmentarea orizontală

Fragmentarea orizontală se realizează prin selecții ale relațiilor globale și se bazează pe determinarea proprietăților logice ale datelor și proprietăților statistice cum ar fi numărul de referințe ale aplicațiilor la fragmente.

Un fragment orizontal constă dintr-un subset de tuple ale unei relații globale, deci are aceeași structură ca aceea a relației globale din care provine. Tuplele care vor aparține aceluiași fragment sunt alese specificând o condiție care va implica unul sau mai multe atribute ale relației. Aceste condiții vor fi numite predicatele fragmentării sau calificări. Fragmentele orizontale vor fi rezultatele unor operații de selecție folosind aceste codificări:

FOi=σCi(R)

Fragmentarea orizontală corectă a unei relații cere ca fiecare tuplu al relației globale să fie selectat în unul și numai unul din fragmente. Apare astfel necesitatea determinării unui set complet de predicate disjunctive. Pentru a arăta cum se realizează fragmentarea orizontală vom considera următoarea relație:

PERS (MARCA, NUME, SAL, FUNCT, NR_DEPT),

reprezentată pe tupluri astfel:

Vom introduce următoarele definiții:

Un predicat simplu este un predicat de tipul:

Atribut = Valoare (FUNCT = “P”).

Un predicat minterm Y pentru un set P de predicate simple este un predicat obținut prin conjuncția tuturor predicatelor din P, considerate în forma naturală sau negată, astfel încât Y să nu fie contradicție:

Y = pi* unde: (pi* = pi sau pi* = not pi și y ≠ fals).

Un fragment este un set de tupluri selectate cu ajutorul unui predicat minterm.

Un predicat simplu pi este relevant în raport cu un set de predicate simple P dacă există cel puțin două predicate minterm aparținând lui P ale căror expresii diferă numai în predicatul pi.

Referindu-ne la exemplul ales să presupunem că există o serie de aplicații care cer numai date referitoare la angajații care sunt programatori. Două predicate simple pentru acest exemplu sunt: NR_DEPT = 1 și FUNCT = ”P”. Predicatele minterm ce pot fi construite pentru acest set de predicate sunt:

NR_DEPT = 1 AND FUNCT = “P”

NR_DEPT = 1 AND FUNCT NOT = “P”

NR_DEPT NOT = 1 AND FUNCT = “P”

și NR_DEPT NOT = 1 AND FUNCT NOT = “P”.

Predicatele NR_DEPT=1 și FUNCT=”P” sunt relevante în raport cu setul de predicate minterm construit.

Predicatul SAL>0 nu este relevant pentru predicatele minterm construite deoarece nu contribuie la fragmentare.

Fie P={P1, P2,…, Pn} un set de predicate simple. Pentru ca P să realizeze corect și eficient fragmentarea trebuie să fie complet și minimal:

spunem că P este complet dacă și numai dacă oricare două tupluri aparținând aceluiași fragment sunt referite cu aceeași probabilitate de orice aplicație;

spunem că P este minimal dacă toate predicatele sunt relevante.

Iată o metodă care are ca rezultat o fragmentare orizontală corectă și eficientă:

Pas1 – fie p1 un predicat care partiționează tuplurile relației R în două părți care sunt referite diferit de cel puțin o aplicație. Fie P={p1};

Pas2 – considerăm un nou predicat simplu pi care partiționează unul din fragmentele rezultate până acum în două părți care sunt referite diferit de cel puțin o aplicație. Fie P=P U {pi};

Pas3 – eliminăm predicatele din P care, prin adăugarea lui pi, au devenit nerelevante;

Pas4 – dacă P nu este complet se reia de la P2.

Determinarea unui set de predicate complet și minimal poate fi destul de dificilă în anumite cazuri. În aceste situații putem realiza o fragmentare rezonabilă prin concentrarea asupra câtorva aplicații mai importante și nesepararea fragmentelor care au caracteristici asemănătoare.

În anumite cazuri, fragmentarea orizontală a unei relații nu se bazează pe proprietățile atributelor relației respective, ci este derivată din fragmentarea orizontală a altei relații, motiv pentru care se va numi fragmentare orizontală derivată.

Să considerăm următoarele relații globale:

CLIENT (CODCL, DENCL, LOC),

LIVRĂRI (DATA, CODCL, CODPROD, CANT).

Relația LIVRĂRI trebuie partiționată astfel încât fiecare fragment să conțină tuplurile referitoare la clienții dintr-o anumită localitate (vom presupune că sunt doar două localități implicate: SB și BV). Dar LOC nu este un atribut al relației LIVRĂRI, ci al relației CLIENT. În acest caz este necesară o operație de semijoncțiune pentru a determina tuplurile din relația LIVRĂRI care corespund clienților dintr-o localitate dată.

Vom fragmenta orizontal relația CLIENT pe baza atributului LOC:

CLIENT1 = σLOC=”BV” (CLIENT)

CLIENT2 = σLOC=”SB” (CLIENT)

Fragmentarea orizontală derivată a relației LIVRĂRI poate fi definită astfel:

LIVRĂRI1 = LIVRĂRI ⋈CODCL=CODCL CLIENT1

LIVRĂRI2 = LIVRĂRI ⋈CODCL=CODCL CLIENT2

Considerând că în urma fragmentării unei relații R au rezultat fragmentele FOi, i=1,n, relația poate fi reconstruită executând operația de reuniune a fragmentelor:

R = FOi .

Fragmentarea verticală

Fragmentarea verticală a unei relații R se realizează prin operații de proiecție a relației pe seturi de atribute care sunt referite în același fel în cadrul aplicațiilor.

Un fragment vertical constă dintr-un subset de atribute ale unei relații globale R și este obținut astfel:

FVi = πLi (R),

unde Li este o listă de atribute: a1, a2,…, am.

Condiția de corectitudine pentru fragmentarea verticală este ca fiecare atribut al relației R să aparțină cel puțin unui fragment. Pentru a permite reconstrucția relației originale este necesară existența unui atribut special care să permită joncțiunea fragmentelor obținute:

R = FV1 ⋈ FV2 ⋈… ⋈ FVn.

Acest atribut special poate fi cheia relației, însă dat fiind faptul că această cheie nu este întotdeauna simplă, de dimensiuni mici, este de preferat existența unui identificator de tuplu. Este foarte important ca acest atribut să nu fie “vizibil” pentru utilizatori. Dacă utilizatorii au acces la identificatorul de tuplu, sistemul nu mai poate schimba adresa acestui identificator. Accesul utilizatorilor la adresele interne violează noțiunea de independență a datelor.

Obținerea fragmentelor verticale se poate face prin două metode: partiționarea atributelor sau gruparea acestora.

Partiționarea atributelor

În acest caz fragmentele verticale obținute sunt aproape disjuncte, având în comun doar cheia relației.

O metodă de partiționare este stabilirea afinității atributelor. Această metodă produce fragmente verticale unde singurele atribute care se repetă sunt cele ale cheii. Având în vedere că aceste atribute apar peste tot le excludem din analiza următoare care va determina afinitatea.

Iată metoda care partiționează atributele unei relații R:

pentru fiecare aplicație care accesează relația R vom construi o matrice după următorul exemplu:

fie R (a1, a2, a3, a4, a5, CHEIA)

fie o aplicație care accesează CHEIA, a1, a2, a4

construim matricea triunghiulară:

a1 a2 a3 a4 a5

a1 1 0 1 0

a2 0 1 0

a3 0 0

a4 0

a5

Matricea este triunghiulară deoarece diagonala nu trebuie completată iar jumătatea de sub diagonală este imaginea în oglindă a celeilalte jumătăți. 1 reprezintă faptul că perechile de atribute corespunzătoare sunt implicate în aceeași tranzacție.

în toate matricile vom înlocui 1 cu frecvența fiecărei tranzacții corespunzătoare.

efectuăm suma tuturor matricilor, iar matricea sumă o vom numi matricea de afinitate.

stabilim fragmentele verticale ținând cont de faptul că perechile cu afinitate mare în matricea de afinitate trebuie să apară în același fragment iar cele cu afinitate mică trebuie separate.

Gruparea atributelor

Prin grupare, atributele relației globale sunt succesiv agregate pentru a construi fragmente. Gruparea atributelor introduce replicarea în cadrul fragmentelor. În aceste condiții este important ca atributele replicate să fie rar sau deloc actualizate.

Revenind la relația PERS definită mai sus să considerăm că există următoarele aplicații:

aplicații administrative care necesită informații referitoare la nume și salariu;

aplicații referitoare la structura fiecărui departament.

Potrivit acestor două tipuri de aplicații vom grupa atributele în două fragmente:

PERS1 = (MARCA, NUME, SAL)

PERS2 = (MARCA, NUME, FUNCT, NR_DEPT)

Dacă am fi utilizat partiționarea trebuia să decidem în care din cele două fragmente va rămâne atributul NUME. Întrucât atributul NUME este relativ stabil în acest caz este preferabilă utilizarea grupării deoarece partiționarea ar fi condus la necesitatea ca una dintre aplicații să implice realizarea unei joncțiuni și unei sau mai multor referiri la distanță.

Fragmentarea mixtă

Dacă fragmentarea orizontală sau cea verticală se dovedesc a fi insuficiente se recurge la fragmentarea mixtă care constă în fragmentarea orizontală a unui fragment vertical sau fragmentarea verticală a unui fragment orizontal.

Aceste operații de fragmentare pot fi repetate recursiv, generând arbori de fragmentare. În general, în practică este bine să avem cel mult două nivele de fragmentare.

Este evident că ordinea în care fragmentările verticale sau orizontale sunt aplicate poate afecta rezultatul fragmentării, chiar și în cazul în care avem doar două niveluri:

A1 A2 A3 A4 A5

a) fragmentare verticală urmată de fragmentare orizontală

A1 A2 A3 A4 A5

b) fragmentare orizontală urmată de fragmentare verticală

Fig.7. Fragmentarea mixtă a unei relații globale.

Pentru a exemplifica proiectarea fragmentării să considerăm următorul set de relații globale:

SCHEMA GLOBALĂ:

PERS (MARCĂ, NUME, SAL, MARCA_ȘEF, NRDEPT);

DEPT (NRDEPT, DEN, ARIA, MARCA_ȘEF);

CLIENT (CODCL, DENCL, LOC);

LIVRĂRI (DATA, CODCL, CODP, NRDEPT, CANT).

Să presupunem că departamentele pot fi grupate după numărul lor în trei categorii iar clienții provin din două localități (SB, BV).

Rezultatul proiectării fragmentării îl constituie schema fragmentării a cărei definiție o dăm în cele ce urmează: schema fragmentării unei BD este o definire a unui set de fragmente care să includă toate atributele și toate tuplele BD și care să permită reconstrucția întregii BD aplicând asupra fragmentelor o secvență de operații de reuniune și de joncțiune. Este foarte avantajos – deși nu necesar – ca fragmentele să fie disjuncte cu excepția cheii primare, în cazul fragmentelor verticale sau mixte.

Iată SCHEMA FRAGMENTĂRII pentru relațiile considerate mai sus:

PERS1 = σNRDEPT 10 ( MARCA, NUME, MARCA_ȘEF, NRDEPT (PERS));

PERS2 = σ10 NRDEPT 20 ( MARCA, NUME, MARCA_ȘEF, NRDEPT (PERS));

PERS3 = σNRDEPT > 20 ( MARCA, NUME, MARCA_ȘEF, NRDEPT (PERS));

PERS4 = MARCA, NUME, SAL, IMP (PERS);

DEPT1 = σNRDEPT 10 (DEPT);

DEPT2 = σ10 < NRDEPT 20 (DEPT);

DEPT3 = σNRDEPT > 10 (DEPT);

CLIENT1 = σLOC = “BV” (CLIENT);

CLIENT2 = σLOC = “SB” (CLIENT);

LIVRĂRI1 = LIVRĂRI ⋈CODCL=CODCL CLIENT1;

LIVRĂRI2 = LIVRĂRI ⋈CODCL=CODCL CLIENT2;

IV.5. PROIECTAREA ALOCĂRII

După definirea fragmentelor se pune problema alocării lor la diferite stații ale rețelei spre a fi memorate. În funcție de metodele utilizate, proiectarea alocării poate avea ca rezultat o alocare finală neredundantă sau redundantă.

Cea mai simplă metodă de alocare este ca întreaga bază de date să fie memorată pe o singură stație, toate aplicațiile ce vor fi rulate de pe alte stații urmând a accesa la distanță baza de date. În consecință, procesarea locală are foarte mult de suferit. La fel și disponibilitatea datelor, deoarece în caz că stația unde este memorată BD suferă o cădere atunci nici o altă stație nu mai poate rula nici o aplicație.

O altă metodă care determină o alocare neredundantă este metoda celei mai bune alegeri (1) care constă în comensurarea fiecărei alocări posibile și alegerea stației cu cea mai bună măsură pentru fiecare fragment. Această metodă elimină posibilitatea plasării unui fragment la o anumită stație dacă un fragment înrudit este deja alocat la stația respectivă.

În cazul alocării redundante replicarea datelor mărește complexitatea proiectării deoarece:

gradul de replicare al fiecărui fragment devine o variabilă a problemei,

realizarea acceselor de citire este complicată de faptul că aplicațiile trebuie să selecteze, din mai multe alternativ, stațiile pentru a accesa fragmentele.

V. CERERI DISTRIBUITE

V.1. NOȚIUNI GENERALE

Un utilizator global interacționează cu o BDD de aceeași manieră cu care ar interacționa cu o BD centralizată. El își exprimă cererile sale (de la terminale on-line sau prin aplicații) sub formă de tranzacții globale.

Pentru a înțelege mai bine cum sistemul răspunde unei cereri distribuite dăm în continuare următoarea schemă:

Dicționarul

Sistemului

Distribuit

Tranzacții Răspunsuri
locale locale

. . .

Fig.8. Execuția unei cereri distribuite.

Tranzacțiile globale sunt evaluate și descompuse, prin intermediul informațiilor conținute în dicționarul sistemului distribuit, în cereri care se referă la fragmente ale relațiilor globale, numite cereri fragment. Cea mai simplă cale pentru a realiza această transformare este de a substitui relațiile globale care apar în cererea globală cu expresiile de fragmentare corespunzătoare, inversate. Cererile rezultate vor opera asupra fragmentelor și vor alcătui expresia canonică a cererii inițiale. Aceste cereri sunt transmise supervizorului execuției distribuite. Acesta are rolul de a transmite fiecare cerere nodului pe care se află BDL pe care trebuie să o interogheze și, pe de altă parte, de a primi răspunsurile de la diversele BD interogate și a forma răspunsul pentru tranzacția globală.

Deoarece diversele BDL pot avea sisteme de gestiune diferite și, mai mult, calculatoarele din rețea pot fi neomogene este necesară realizarea unei adaptări, a fiecărui fragment al cererii globale, conformă cu protocolul fiecărui sistem de operare și fiecărui SGBD specific din fiecare nod. După adaptarea cererii la standardele cerute de SGBD nodului local acesta va trata cererea ca pe orice cerere locală.

Cererile care formează expresia canonică a cererii globale pot fi executate direct dar, în general, aceasta este o metodă ineficientă de a răspunde unei cereri. Din acest motiv expresia canonică trebuie modificată prin aplicarea succesivă a unor transformări echivalente.

Având mai multe cereri echivalente se pune problema alegerii celei mai profitabile dintr-un punct de vedere, în general din punct de vedere al cantității de date transferate prin rețea, implicit al costului transferului acestor date.

Pentru exemplificare să considerăm că relațiile PERS și DEPT sunt distribuite ca în Fig. 9.:

STAȚIA 1: PERS:

5000 angajați * 65 bytes = 325000 bytes

STAȚIA 2: DEPT:

50 departamente * 45 bytes = 2250 bytes

Fig.9. Exemplu.

Presupunem că relațiile nu sunt fragmentate. Să considerăm următoarea cerere:

“Pentru fiecare angajat să se găsească numele său precum și al departamentului în care lucrează”.

Utilizând limbajul algebrei relaționale această cerere poate fi formulată astfel:

πNUME, DEN (PERS ⋈NRDEPT=NRDEPT DEPT)

Rezultatul acestei cereri va avea 5000 de înregistrări lungi de câte 50 bytes fiecare (30+20).

Presupunând că această cerere este formulată la STAȚIA 3 putem adopta una din următoarele strategii:

transferăm relațiile PERS și DEPT la STAȚiA 3; astfel vom transfera 325000 + 2250 = 327250 bytes;

transferăm PERS la STAȚIA 2, executăm cererea pe acea stație și transferăm rezultatul la STAȚIA 3; mărimea rezultatului fiind 5000*50=250000 rezultă că, în total, transferăm 325000+250000=575000 bytes;

transferăm relația DEPT la STAȚIA 1, executăm cererea acolo și transferăm rezultatul la STAȚIA 3; în acest caz transferăm 2250+250000=252250 bytes.

Dacă minimizarea transferului de date este criteriul de optimizare vom alege strategia 3.

Presupunând că cererea a fost formulată la STAȚIA 2 putem alege una din următoarele strategii:

transferăm PERS la STAȚIA 2 și executăm cererea acolo, total transfer = 325000 bytes;

transferăm DEPT la STAȚIA 1, executăm cererea acolo și întoarcem rezultatul la STAȚIA 2: total transfer = 2250+250000=252250 bytes.

O strategie mai complexă, care uneori dă rezultate mai bune folosește o operație numită semijoncțiune. Vom discuta de spre semijoncțiune într-unul din subcapitolele următoare.

În continuare vom prezenta câteva criterii euristice pentru a simplifica expresiile cererilor.

V.2. TEHNICI DE REPREZENTARE A CERERILOR

O cerere globală poate fi exprimată utilizând diferite limbaje bazate pe algebra relațională sau pe calculul relațional.

Una din tehnicile cele mai utilizate pentru a reprezenta o expresie algebrică relațională este reprezentarea arborescentă. Arborele cererii este o reprezentare grafică a operațiilor și operanzilor care apar într-o expresie algebrică. Relațiile sunt reprezentate în nodurile frunză iar operațiile în nodurile interne. În execuția cererii, un nod intern poate fi executat atunci când operanzii săi sunt disponibili. După execuție, nodul este înlocuit cu rezultatul operației. Nodul rădăcină este ultimul executat și este înlocuit cu rezultatul final.

Dacă se utilizează calculul relațional, arborele cererii este înlocuit de graful cererii. În nodurile grafului sunt reprezentate constantele și atributele relației. Este permisă repetarea atributelor care apar în mai mult de o relație. Pe liniile care leagă nodurile atribut sunt reprezentate condițiile de joncțiune iar pe liniile care leagă o constantă de un atribut sunt reprezentate condițiile de selecție.

Pentru exemplificare să considerăm C1 cererea pentru codurile clienților pentru care s-au livrat produse în cadrul departamentelor situate în zona de nord.

c1: πCODCL (σARIA=”NORD” (LIVRĂRI ⋈NRDEPT=NRDEPT DEPT)).

Un exemplu de arbore pentru cererea C1 este:

πCODCL

σARIA=”NORD”

⋈NRDEPT=NRDEPT

LIVRĂRI DEPT

Fig.10. Arbore pentru C1

Acest arbore definește o ordine parțială de execuție a operațiilor. În cazul nostru se aplică mai întâi joncțiunea, urmată de selecție și apoi de proiecție.

O altă ordine de execuție a operațiilor, care corespunde reprezentării arborescente din Fig.11., ar fi: selecția aplicată relației DEPT, joncțiunea și proiecția:

πCODCL

⋈NRDEPT=NRDEPT

LIVRĂRI σARIA=”NORD”

DEPT

Fig.11. Arbore pentru C1.

Această inversare în ordinea de execuție a nodurilor corespunde unei transformări echivalente.

V.3. EXPRESIA CANONICĂ A CERERII GLOBALE

Așa cum am arătat în V.1. cererea globală poate fi descompusă în cereri fragment prin substituirea relațiilor globale cu expresiile de fragmentare corespunzătoare, obținându-se astfel expresia canonică a cererii globale.

Reprezentarea arborescentă a cererilor fragment se obține din reprezentarea arborescentă a cererii globale substituind relațiilor globale expresiile corespunzătoare schemei de fragmentare inversate. Astfel, nivelele arborelui expresiei canonice sunt fragmente și nu relații globale.

Iată arborele corespunzător cererilor fragment pentru cererea C1:

πCODCL

⋈NRDEPT=NRDEPT

U σ

(*) [ LIVRĂRI1: [LIVRĂRI2:

CODCL=CLIENT.CODCL CODCL=CLIENT.CODCL

AND CLIENT.LOC=”BV” ] AND CLIENT.LOC=”SB” ] U

[DEPT1: [DEPT2: [DEPT3:

NRDEPT10] 10<NRDEPT20] NRDEPT>20]

Fig.12. Forma canonică a cererii C1

În reprezentarea fragmentelor s-au utilizat simbolurile algebrei calificate care vor fi prezentate în secțiunea următoare.

Expresia canonică este o modalitate conservatoare de prelucrare a cererilor care presupune colectarea fragmentelor relațiilor globale și constituirea unor relații temporare. În general, prelucrarea directă a expresiei canonice este ineficientă. Fiind o expresie globală algebrică, expresia canonică a cererii globale poate fi supusă transformărilor echivalente din algebra relațiilor calificate. Se pot obține astfel cereri distribuite echivalente dar mult mai eficiente din punct de vedere al execuției.

V.4. ALGEBRA RELAȚIILOR CALIFICATE

O relație calificată este o relație extinsă printr-o calificare. Calificarea poate fi privită ca o proprietate a tuplurilor relației. Vom simboliza o relație calificată prin perechea [R:qR], unde R este relația numită corp, iar qR este predicatul numit calificare.

Fragmentarea orizontală este un exemplu tipic de relație calificată în care calificarea corespunde predicatului de fragmentare.

În general o calificare nu poate fi evaluată atunci când se elimină prin proiecție atribute utilizate în calificare.

Algebra relațiilor calificate este o extensie a algebrei relaționale care utilizează relațiile calificate drept operanzi.

Următoarele reguli sunt rezultatul aplicării operațiilor algebrei relaționale asupra relațiilor calificate:

Regula 1: σF[R:qR] [σF R : F AND qR] (F – predicatul de selecție)

Regula 2: A [R:qR] [A R:qR].

Regula 3: [R:qR] X [S:qS] [R X S :qR AND qS]

(X – produs cartezian)

Regula 4: [R:qR] – [S:qS] [R-S : qR]

Din această regulă, folosindu-ne de egalitatea R S = R – (R – S), putem deduce următoarea regulă:

[R:qR] [S:qS] [R S : qR]

Regula 5: [R:qR] [S:qS] [R S : qR OR qS]

Regula 6: [R:qR] ⋈F [S:qS] [R ⋈F S : qR AND qS AND F]

Reaminind definiția semijoncțiunii: R ⋉F S = Atr(R) (R ⋈F S, putem deduce și următoarea regulă:

[R:qR] ⋉F [S:qS] [R ⋉F S : qR AND qS AND F]

(Demonstrație: [R:qR] ⋉F [S:qS] Atr(R) ([R:qR] ⋈F [S:qS])

Atr(R) ([R ⋈F S : qR AND qS and F])

[Atr(R) (R ⋈F S) : qR AND qS AND F]

[R ⋉F S : qR AND qS AND F] )

Având definită algebra relaților calificate, putem dezvolta acum echivalența transformărilor. Două relații calificate sunt echivalente dacă corpurile lor sunt relații echivalente iar calificările au aceeași valoare de adevăr.

Dăm în continuare transformări echivalente din algebra relațională, transformări care rămân valabile și pentru algebra relațiilor calificate:

comutativitatea operațiilor de joncțiune și produs cartezian:

R ⋈ S = S ⋈ R

R X S = S X R

asociativitatea operațiilor de joncțiune și produs cartezian:

(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

(R X S) X T = R X (S X T)

compunerea proiecțiilor:

A1,…,An (B1,…,Bm) (R)) = A1,…,An (E),

unde A1,…,An trebuie să aparțină setului B1,…,Bm.

compunerea selecției cu proiecția:

dacă condiția F implică numai atributele A1,…,An atunci:

A1,…,An (σF (E)) = σF (A1,…,An (E))

dacă condiția F implică și alte atribute atunci:

A1,…,An (σF (E)) = A1,…,An (σF (A1,…,An,B1,…,Bm (E))),

unde B1,…Bm sunt celelalte atribute implicate în F.

comutarea selecției cu produsul cartezian:

dacă F implică doar atribute din R atunci:

σF (R X S) = σF (R) X E2

dacă F = F1 F2, F1 implică numai atribute din R, F2 implică numai atribute din S atunci:

σF (R X S) = σF1 (R) X σF2 (S)

dacă F1 implică numai atribute din R, dar F2 implică atâ atribute din R cât și din S atunci:

σF (R X S) = σF2 (σF1 (R) X S)

comutarea selecției cu reuniunea:

σF (R S) = σF (R) σF (S)

comutarea selecției cu diferența:

σF (R – S) = σF (R) – σF (S)

comutarea proiecției cu produsul cartezian:

dacă A1,…, An reprezintă o listă de atribute din cadrul a două relații, R și S, listă formată din atributele aparținând lui R și notate cu B1,…,Bm și din atributele aparținând lui S notate cu C1,…,Ck, atunci:

A1,…,An (R X S) = B1,…,Bm (R) X C1,…,Ck (S)

comutarea proiecției cu reuniunea:

A1,…,An (R S) = A1,…,An (R) A1,…,An (S)

V.5. CRITERII DE SIMPLIFICARE A CERERILOR DISTRIBUITE

Folosind transformările de mai sus putem schimba ordinea de execuție a operațiior, obținând cereri echivalente dar mai eficiente în sensul reducerii costurilor de acces, a costurilor de prelucrare și memorare a rezultatelor.

Criteriile generale de simplificare a cererilor distribuite urmăresc reducerea dimensiunii (cardinalitate) rezultatelor intermediare. În acest sens schimbarea ordinii de execuție a operațiilor joacă un rol foarte important.

Criteriul 1: Realizarea operațiilor de selecție și proiecție cât mai devreme posibil.

Acest criteriu este util ținând cont de faptul că atât selecția cât și proiecția acționează ca reducători ai numărului de tuple dintr-o relație. Aplicându-le cât mai devreme reducem din timp cardinalitatea relațiilor implicate în cerere.

Dacă aplicăm acest criteriu pentru cererea C1 (din IV.2) folosind distribuția selecției și proiecției în raport cu uniunea și joncțiunea obținem următorul arbore de execuție:

πCODCL

⋈NRDEPT=NRDEPT

U U

CODCL,NRDEPT CODCL,NRDEPT NRDEPT NRDEPT NRDEPT

LIVRĂRI1 LIVRĂRI2 σARIA=”NORD” σARIA=”NORD” σARIA=”NORD”

DEPT1 DEPT2 DEPT3

Fig.13. Arborele cererii C1

Calificările sunt utile pentru a elimina fragmentele care nu sunt implicate în cerere. Atunci când se produce după o selecție sau o joncțiune calificarea va conține o conjuncție de predicate. Această calificare poate fi contradictorie (de exemplu: NRDEPT=15 AND NRDEPT 10). Relațiile care au calificări contradictorii sunt nule și trebuie eliminate.

Prezentăm câteva transformări echivalente în care este implicată o relație nulă.

σF () = – R =

A () = R ⋈F =

R x = ⋈F R =

R = R ⋈F =

R – = R

Criteriul 2: Substituirea rezultatului selecției cu relația vidă dacă calificarea rezultatului este contradictorie.

Criteriul 3. Utilizarea algebrei relațiilor calificate pentru a evalua calificarea operanzilor de joncțiune. Substituirea subarborilor, incluzând joncțiunea și operanzii săi cu relația vidă dacă calificarea rezultatului este contradictorie.

Ultimele două criterii sunt utile pentru a simplifica fragmentarea orizontală și joncțiunea între fragmente orizontale.

SIMPLIFICAREA RELAȚIILOR FRAGMENTATE ORIZONTAL

Vom prezenta acest tip de simplificare cu un exemplu. Să considerăm cererea C2 asupra relației fragmentate orizontal DEPT:

C2 : σNRDEPT=1 (DEPT).

Iată forma canonică a acestei cereri:

σNRDEPT=1

U

[DEPT1: [DEPT2: [DEPT3:

NRDEPT10] 10<NRDEPT20] NRDEPT>20]

Fig.14. Forma canonică a cererii C2

Pentru simplificare vom împinge selecția în jos în cadrul arborelui pentru a fi distribuită în raport cu uniunea. Calificarea rezultatului selecției asupra fragmentelor DEPT2 și DEPT3 este contradictorie. Conform Criteriului 2 aceste rezultate vor fi substituite cu relația vidă. În final vom elimina operația de uniune, aceasta având un singur operand diferit de relația vidă.

Se obține următorul arbore de execuție:

σNRDEPT=1

[DEPT1: NRDEPT10]

Fig.15. Forma simplificată a cererii C2

Această modalitate de simplificare poate fi aplicată la majoritatea relațiilor fragmentate orizontal.

SIMPLIFICAREA RELAȚIILOR FRAGMENTATE VERTICAL

Simplificarea relațiilor fragmentate vertical este duală simplificării relațiilor fragmentate orizontal. Raționamentul care stă la baza acestei simplificări este de a determina un set de fragmente care să fie suficient pentru a rezolva cererea și de a elimina toate celelalte fragmente ca și joncțiunile care nu sunt necesare.

Vom prezenta și acest tip de simplificare printr-un exemplu: fie cererea C3 pentru numele și salariul angajaților. Expresia algebrică a cererii globale este:

Simb

Arborele corespunzător formei canonice pentru această cerere este:

NUME,SAL

⋈NRDEPT=NRDEPT

[PERS4 : true] U

[PERS1: [PERS2: [PERS3:

NRDEPT10] 10<NRDEPT20] NRDEPT>20]

Fig.16. Forma canonică a cererii C3

Reamintim că relația PERS este partiționată vertical în fragmentul PERS4 (care cuprinde informații referitoare la salarizare) și în al doilea fragment care este partiționat mai departe orizontal, în funcție de numărul departamentului. Atributele NUME și SAL sunt atribute ale fragmentului PERS4. Este posibil, în consecință, să răspundem cererii utilizând numai fragmentul PERS4. Arborele anterior va fi simplificat prin eliminarea celorlalte fragmente și a operatorului de joncțiune.

NUME,SAL

[PERS4 : true]

Fig.17. Cererea C3 simplificată.

SIMPLIFICAREA JONCȚIUNII ÎNTRE RELAȚIILE FRAGMENTATE ORIZONTAL

Să considerăm joncțiunea între două relații fragmentate orizontal R și S. Există două posibilități distincte de a realiza joncțiunea:

prima presupune colectarea tuturor fragmentelor relației R, respectiv S, înainte de realizarea joncțiunii;

a doua constă în realizarea joncțiunii între fragmente și apoi colectarea tuturor rezultatelor într-o singură relație rezultat; vom numi această metodă joncțiune distribuită.

În general, prima metodă este utilizată atunci când condițiile fragmentării au un grad ridicat de selecție. A doua metodă este preferată atunci când joncțiunea implică mai multe perechi de fragmente.

Următorul criteriu permite transformarea unei cereri fără joncțiune distribuită într-o cerere care să fie prelucrată cu ajutorul joncțiunii distribuite.

Criteriul 4: Pentru obținerea unei joncțiuni distribuite, operațiile de uniune trebuie realizate după joncțiunile pe care dorim să le distribuim.

Simplificarea joncțiunii presupune aplicarea acestui ultim criteriu (pentru a distribui joncțiunea), urmată de aplicarea criteriului 3 pentru a elimina joncțiunea între fragmentele care nu au nici o contribuție la rezultatul final.

Fie cererea C4 pentru codul tuturor clienților care au cel puțin o livrare. Expresia algebrică a cererii globale este:

C4: CODCL (LIVRĂRI ⋈CODCL=CODCL CLIENT)

Arborele corespunzător formei canonice este:

CODCL

⋈CODCL=CODCL

U U

[LIVRĂRI1 : [LIVRĂRI2: [CLIENT1: [CLIENT2:

CODCL=CLIENT.CODCL CODCL=CLIENT.CODCL LOC=”BV”] LOC=”SB”]

AND CLIENT.LOC=“BV”] AND CLIENT.LOC=”SB”]

Fig.18. Forma canonică a cererii C4

Aplicând criteriul 4 vom împinge cele două uniuni după operația de joncțiune, generând astfel patru joncțiuni între fragmente. Aplicând criteriul 3, constatând că două dintre rezultatele acestor joncțiuni sunt vide (au calificările contradictorii: CLIENT1 ⋈ LIVRĂRI2, CLIENT2 ⋈ LIVRĂRI1), arborele cererii se reduce la următorul:

U

CODCL CODCL

⋈CODCL=CODCL ⋈CODCL=CODCL

[LIVRĂRI1 : [CLIENT1: [LIVRĂRI2: [CLIENT2:

CODCL=CLIENT.CODCL LOC=”BV”] CODCL=CLIENT.CODCL LOC=”SB”]

AND CLIENT.LOC=“BV”] AND CLIENT.LOC=”SB”]

Fig.19. Joncțiunea distribuită pentru cererea C4

Presupunând că fragmentele cu același indice sunt plasate la aceeași stație, arborele din Fig.19 corespunde unei prelucrări eficiente a cererii deoarece fiecare joncțiune este locală la o stație.

PROGRAMUL DE SEMIJONCȚIUNE

Semijoncțiunea este o operație a algebrei relaționale care are particularități relevante în optimizarea cererilor distribuite.

O operație de joncțiune poate fi transformată cu ajutorul unui program de semijoncțiune astfel:

fie echijoncțiunea R ⋈A=B S, unde A și B sunt atribute sau seturi de atribute ale relației R, respectiv S;

programul de semijoncțiune este:

S ⋈A=B (R ⋉A=B (B (S))),

unde R ⋉A=B S = Atr(R) (R ⋈A=B S).

Iată reprezentarea arborescentă a programului de semijoncțiune:

⋈A=B

⋉A=B

R B

S

Fig.20. Reprezentarea arborescentă a programului de semijoncțiune.

Pentru a înțelege intuitiv utilitatea acestui program să presupunem că R și S sunt situate pe stații diferite. Executarea programului de semijoncțiune presupune proiecția relației S după atributul B și trimiterea rezultatului la stația unde se află R; aici se va realiza semijoncțiunea iar rezultatul va fi trimis la stația de origine a lui S, unde se va realiza și joncțiunea finală. Astfel, numai un subset de tupluri din R va supraviețui operației de semijoncțiune, și anume numai acelea care vor contribui la rezultatul final al joncțiunii.

Acest program reduce numărul de tupluri care vor fi transferate de la o stație la alta, reducându-se astfel transferul de date în rețea.

Utilizarea programului este eficientă doar dacă numărul de tupluri din R implicate efectiv în operația de joncțiune este sensibil mai mic decât numărul de tupluri ale lui R.

V.6. GRUPAREA DISTRIBUITĂ ȘI EVALUAREA FUNCȚIILOR DE AGREGARE

Aplicațiile bazelor de date necesită uneori operații de acces care nu pot fi exprimate direct în limbajul algebrei relaționale. Limbajele de interogare pentru BD relaționale permit formularea unor astfel de cereri complexe care necesită gruparea tuplurilor în subseturi disjuncte care pot fi evaluate utilizând funcții de agregare. În această secțiune vom prezenta tehnici de prelucrare eficientă a acestor cereri în cadrul BD distribuite.

Iată trei exemple de cereri care nu pot fi exprimate direct utilizând algebra relațională:

media cantităților livrate pentru produsul cu codul “C1”

partiționarea relației LIVRĂRI în grupuri care au același CODCL și CODP evaluând pentru fiecare grup suma cantităților livrate;

aceeași cerere ca cea de mai sus însă în relația rezultat să nu se păstreze decât acele înregistrări pentru care suma cantităților să fie mai mare decât o sumă dată (500 de exemplu).

Este evident faptul că trebuie să extindem algebra relațională cu noi operații.

Vom introduce operația de grupare GBG,FA(R) definită astfel:

G reprezintă mulțimea atributelor care determină gruparea;

FA sunt funcții agregate care urmează a fi evaluate;

GBG,FA(R) este o relație cu următoarele caracteristici:

schema relațională este formată din atributele G și funcțiile agregate FA;

numărul de tupluri este egal cu numărul de grupuri al relației R;

atributele mulțimii G iau valorile de grupare iar elementele mulțimii FA primesc valorile funcțiilor agregate evaluate pentru fiecare grup.

Cu ajutorul operației de grupare putem formula cererile descrise anterior:

C5 – GBAVG(CANT) (σCODP=”C1” (LIVRĂRI));

C6 – GBCODCL,CODP,SUM(CANT) (LIVRĂRI);

C7 – σSUM(CANT)>500 (GBCODCL,CODP,SUM(CANT) (LIVRĂRI)).

Această operație de grupare este distributivă în raport cu uniunea în anumite condiții:

GBG,FA (R1 U R2) = (GBG,FA (R1)) U (GBG,FA (R2)) dacă și numai dacă fiecare grup aparține în întregime unui fragment adică:

i (Gi R1) (Gi R1 = )

Această distributivitate permite reducerea cardinalității relațiilor care fac obiectul operației de uniune.

Putem enunța un nou criteriu de simplificare a cererilor distribuite:

Criteriul 5: Pentru distribuirea grupării și evaluarea funcțiilor agregate, operațiile de uniune trebuie realizate după operațiile de grupare.

Acest criteriu poate fi aplicat cu succes în cazul cererilor C6 și C7.

Iată forma canonică a cererii C7:

σSUM((CANT) > 500

GBCODCL,CODP,SUM(CANT)

U

LIVRĂRI1 LIVRĂRI2
Fig.21. Forma canonică a cererii C7

Tuplurile relației LIVRĂRI trebuie grupate după valorile pentru CODCL și CODP. Relația LIVRĂRI este fragmentată orizontal după localitatea clienților pentru care se efectuează livrările. Deci clienții cu același cod aparțin aceluiași fragment. Este îndeplinită condiția necesară și suficientă pentru a putea aplica Criteriul 5. Aplicând apoi criteriul 1 vom distribui selecția în raport cu uniunea. Arborele rezultat este prezentat în Fig.22.

U

σSUM(CANT) > 500 σSUM(CANT) > 500

GBCODCL, CODP, SUM(CANT) GBCODCL, CODP, SUM(CANT)

LIVRĂRI1 LIVRĂRI2

Fig.22. Gruparea distribuită a cererii C7

În cazul cererilor care nu îndeplinesc condiția necesară și suficientă criteriul 5 nu poate fi aplicat. În această situație vom utiliza un calcul distribuit al funcțiilor de agregare.

Pentru o funcție de agregare F se realizează un calcul distribuit dacă pentru orice set S și orice descompunere a lui S în subseturi S1, S2,…, Sn putem determina un set de funcții agregate F1,…,Fm și o expresie E(F1,…,Fm) astfel încât

F(S) = E(F1(S1),…, F1(Sn), F2(S1),…, F2(Sn),…,Fm(Sn)).

O altă funcție agregată pentru care putem determina funcțiile și expresia E(Fi) este media aritmetică:

AVG(S) =

Similar vom avea:

MIN(S) = MIN (MIN(S1),…, MIN(Sn))

MAX(S) = MAX (MAX(S1),…, MAX(Sn))

COUNT(S) = SUM (COUNT(S1), COUNT(S2),…, COUNT(Sn))

SUM(S) = SUM (SUM(S1),…, SUM(Sn)).

Calculul distribuit al funcțiilor agregate reprezintă o proprietate importantă deoarece rezultatele parțiale ale evaluării funcțiilor F1(S1),…, Fm(Sn) pot fi transmise la o stație comună, unde expresia E poate fi evaluată, în loc să transmitem toate datele la o singură stație unde să fie evaluate și funcțiile agregate.

Această proprietate poate fi aplicată în cazul cererii C5 care nu îndeplinește condiția necesară și suficientă deoarece produsul cu codul “C1” poate să apară în ambele fragmente ale relației LIVRĂRI. Forma canonică a cererii C5 este:

GBAVG(CANT)

σCODP=”C1”

U

LIVRĂRI1 LIVRĂRI2

Fig.23. Forma canonică a cererii C5

Pentru a simplifica cererea vom genera două subcereri care operează asupra fragmentelor LIVRĂRI1 Și LIVRĂRI2:

GBSUM(CANT),COUNT (σCODP=”C1” (LIVRĂRI2))

GBSUM(CANT),COUNT (σCODP=”C1” (LIVRĂRI1)).

Fie S1 și T1 valorile returnate de evaluarea funcțiilor SUM(CANT) și COUNT pentru fragmentul LIVRĂRI1, iar S2 și T2 valorile corespunzătoare pentru fragmentul LIVRĂRI2. Media cantităților va fi dată de (S1+S2)/(T1+T2).

Arborele calcului distribuit pentru cererea C5 este prezentat în Fig.24:

E: AVG(CANT) =

S1,T1: GBSUM(CANT), COUNT S2,T2: GBSUM(CANT), COUNT

σCODP=”C1” σCODP=”C1”

LIVRĂRI1 LIVRĂRI2

Fig.24. Calculul distribuit

VI. CONTROLUL ACCESULUI CONCURENT LA DATE

În această secțiune ne vom ocupa de modalitățile de prevenire a obținerii unor rezultate incorecte din execuția concurentă a unor prelucrări în regim multiutilizator.

Cea mai mare parte a aplicațiilor trebuie concepute pentru a putea funcționa în regim de lucru multiutilizator și implementate pe sisteme care prezintă această caracteristică.

În astfel de sisteme, sistemul de operare asigură accesul concurent al programelor în execuție la resurse după o anumită disciplină internă. În cazul aplicațiilor care utilizează o aceeași BD, întreruperea executării unui proces pentru începerea sau continuarea altora poate conduce la alterarea datelor. Asigurarea integrității datelor, în acest context, presupune existența unor facilități speciale pentru controlul accesului concurent la date la nivelul SGBD.

Câteva dintre problemele care conduc la necesitatea controlului accesului concurent la date sunt: menținerea consistenței multiplelor copii ale unor date, căderi ale unor stații sau ale unor linii de comunicație care pot conduce la partiționarea rețelei, realizarea unor tranzacții care accesează date de pe mai multe stații, interblocarea distribuită a tranzacțiilor.

Pe lângă soluții eficiente care să răspundă problemelor de mai sus, un bun mecanism de control al concurenței trebuie să asigure realizarea într-un timp finit a fiecărei acțiuni atomice și impunerea a cât mai puține constrângeri asupra structurii acestor acțiuni, trebuie să acționeze satisfăcător într-un mediu de rețea care are întârzieri semnificative și să permită paralelismul pentru a satisface cerințele de performanță.

V.1. CONCEPTUL DE TRANZACȚIE

În cazul celor mai multe sisteme de gestiune a bazelor de date unitatea de lucru în asigurarea consistenței datelor este tranzacția.

Tranzacția este o secvență de operații care din punctul de vedere al SGBD constituie o unitate de prelucrare (proprietatea de atomicitate), aceasta însemnând că se va accepta fie executarea ei completă fie, în situația în care acest lucru nu este posibil, nu va trebui reținută nici o modificare făcută de ea asupra bazei de date, SGBD efectuând (automat sau la comandă) derularea înapoi a tranzacției.

O tranzacție este caracterizată de punctele sale de început și de sfârșit. După modul în care acestea sunt definite, tranzacțiile se pot clasifica în:

Tranzacții implicite – sunt acelea pentru care punctele de început și sfârșit sunt automat definite. Pentru unele limbaje toate comenzile de modificare a datelor (INSERT, UPDATE, DELETE) sunt tratate ca tranzacții implicite. În consecință, nici una dintre aceste comenzi nu poate lăsa baza de date într-o stare de inconsistență.

Tranzacții explicite – acestea presupun folosirea unor comenzi speciale pentru stabilirea punctelor de început și sfârșit ale tranzacției. În SQL-SERVER, de exemplu, tranzacțiile explicite permit utilizatorului să grupeze un set de comenzi SQL într-o tranzacție folosind comenzile BEGIN TRANSACTION și COMMIT TRANSACTION pentru precizarea punctelor de început și de sfârșit. De asemenea, utilizatorul poate defini puncte de salvare (utile în cazul tranzacțiilor foarte mari) folosind comanda SAVE TRANSACTION sau să deruleze înapoi tranzacția până la punctul de început sau până la punctul de salvare anterior, folosind comanda ROLLBACK TRANSACTION.

Execuția concurentă necontrolată a tranzacțiilor poate avea efecte nedorite.

Pentru exemplificare, să presupunem că avem un cont în bancă de 5000$ (DISP) asupra căruia două tranzacții vor efectua modificări:

T1 – retragerea sumei de 500$;

T2 – depunerea sumei de 1000$.

Fiecare tranzacție presupune efectuarea a trei acțiuni:

citirea conținutului câmpului DISP într-o zonă de memorie;

modificarea valorii citite;

scrierea în câmpul DISP a valorii modificate.

Dacă cele două tranzacții se vor efectua concurent putem avea următoarea secvență de acțiuni în timp:

timp t0 t1 t2 t3 t4 t5

DISP 5000 5000 5000 5000 4500 6000

T1 Citeste(DISP1) DISP1=DISP1-500 Scrie(DISP1)

T2 Citeste(DISP2) DISP2=DISP2+1000 Scrie(DISP2)

Fig.25. Tranzacții concurente necontrolate

În final, BD va conține în câmpul DISP valoarea 6000 în loc de 5500, cât ar fi corect. Se observă că actualizarea realizată de T1 s-a pierdut ca efect al intercalării lui T1 și T2.

Asemenea probleme pot fi evitate dacă SGBD oferă posibilitatea blocării datelor utilizate la un moment dat de o tranzacție, înțelegând prin aceasta interzicerea accesului celorlalte tranzacții concurente la aceste date. O altă metodă de rezolvare a conflictelor generate de concurență este metoda “etichetelor de timp” (timestamps).

V.2. TEHNICA BLOCĂRII

Inconsistența BD din exemplul anterior este consecința execuției concurente necontrolate a tranzacțiilor.O tehnică utilizată de SGBD pentru a asigura execuția serializabilă a tra0nzacțiilor este tehnica blocării.

Efectiv, blocarea se realizează prin emiterea de către o tranzacție a unei cereri (implicite sau explicite) de blocare pentru SGBD. Dacă cererea este admisă, tranzacția va continua. Altfel, cererea va fi pusă într-o listă de așteptare până ce resursa vizată va fi eliberată.

Situațiile în care o cerere pentru o anumită resursă poate fi admisă, în condițiile în care există deja o blocare pentru resursa respectivă sunt ilustrate de matricea compatibilității blocărilor partajabile și exclusive:

Considerând două situații extreme (baza de date și câmpul) putem sintetiza următoarele aspecte:

blocarea întregii BD la o anumită operație a utilizatorului îi pune pe ceilalți utilizatori în imposibilitatea de a accesa concurent datele, în timp ce gestiunea informațiilor de blocare se simplifică foarte mult;

blocarea unui singur câmp al unei înregistrări dă posibilitatea de acces concurent celorlalți utilizatori chiar la câmpuri ale aceleiași înregistrări, însă face ca gestionarea informațiilor de blocare să fie foarte complexă.

Cele mai multe SGBD oferă posibilitatea blocării la nivel de înregistrare, la nivelul unui grup de înregistrări și la nivel de fișier.

Pentru administrarea blocărilor se poate recurge la unul din următoarele moduri:

setarea unui bit pentru resursa blocată;

menținerea unei liste a resurselor blocate;

menținerea resurselor blocate într-o zonă specială a memoriei.

V.3. PROTOCOALE DE BLOCARE

În această parte a lucrării vom prezenta câteva protocoale de blocare în două faze (2PL) care pot fi folosite pentru a asigura serializabilitatea într-un sistem distribuit.

Protocoalele de blocare în două faze au la bază următoarele principii:

nici o cerere nu are acces la date dacă acestea nu au fost blocate în prealabil (exclusiv sau partajabil);

după ce a deblocat unele date, acea cerere nu mai poate bloca nici o altă dată.

Cererile de acces pot solicita date situate pe stații diferite din rețea. Pentru a superviza execuția unor astfel de cereri o stație trebuie să-și asume rolul de coordonator. Celelalte stații care participă la realizarea cererii se numesc stații cooperante. O stație poate fi în același timp și coordonator (pentru cererile lansate de acolo) și cooperant (pentru cererile lansate de la alte stații care solicită acces la date de pe stația respectivă). Controlul execuției cererii la distanță se realizează prin schimb de mesaje (conform unui anumit protocol) între coordonator și cooperanți.

V.3.1. Protocolul 2PL-centralizat

Caracteristica acestui protocol este că există o singură stație unde se păstrează informațiile de blocare și unde există un singur modul care gestionează blocările pentru întreg sistemul distribuit.

Pentru o tranzacție globală inițiată la stația S1, 2PL centralizat înseamnă următoarele:

Coordonatorul cererii de la S1 împarte cererea în sub-cereri (sub-tranzacții) folosind informațiile din catalogul BDD. Coordonatorul are responsabilitatea de a menține consistența BD. Dacă tranzacția implică actualizarea unor date care sunt replicate atunci coordonatorul trebuie să asigure actualizarea tuturor copiilor. De aceea, înainte de a trece la actualizare trebuie blocate toate copiile. Coordonatorul poate alege orice copie pentru a citi date, în general copia de pe stația unde se află (dacă acolo există una);

Coordonatorul cererii solicită modulului care gestionează blocările, să blocheze toate datele, împreună cu copiile lor;

Acest modul verifică dacă cererea de blocare este compatibilă cu blocările existente. Dacă da, atunci este trimis un mesaj coordonatorului anunțându-l că cererea de blocare a fost admisă. Dacă nu, cererea este pusă într-o coadă până când blocarea poate fi acordată.

Modul de realizare al tranzacției propriu-zise va fi prezentat într-un capitol viitor.

Avantajele protocolului 2PL-centralizat sunt:

implementarea este relativ simplă;

detectarea blocajelor mortale este simplă, deoarece toate informațiile despre blocare sunt păstrate pe o singură stație.

Dezavantajele acestui protocol sunt:

“inundarea” stației unde se găsește modulul care gestionează blocările;

scăderea disponibilității sistemului deoarece dacă această stație cade atunci întreg sistemul este paralizat.

Tot ca avantaj, putem adăuga faptul că costul comunicării în rețea este relativ scăzut: dacă tranzacția de actualizare implică n stații atunci sunt necesare minim 2n+3 mesaje:

1 pentru cererea de blocare;

1 pentru acordarea/neacordarea blocării

n mesaje de actualizare;

n confirmări ale actualizărilor;

1 pentru cererea de deblocare.

V.3.2. Protocolul 2PL-copie principală

Acest protocol încearcă să rezolve unele din problemele protocolului anterior prin distribuirea gestionării blocărilor pe mai multe stații. Pentru fiecare obiect de date replicat este aleasă o copie principală, celelalte copii numindu-se copii sclav (slave copies). Modulul de gestionare a blocărilor din 2PL-centralizat este divizat în mai multe module care gestionează blocări pentru diferite seturi de date.

Principala deosebire între 2PL-centralizat și 2PL-copie principală este aceea că atunci când un obiect de date trebuie actualizat coordonatorul tranzacției trebuie să afle cărui modul să-i trimită cererea de blocare. Este necesar să blocheze la scriere doar copia principală, efectul actualizării propagându-se după aceea și pentru celelalte copii. Propagarea trebuie făcută cât mai repede posibil pentru a preveni citirile de date neactualizate. Deci, acest protocol garantează doar consistența copiei principale.

Această abordare poate fi folosită atunci când datele replicate nu sunt într-o măsură foarte mare, actualizările sunt rare și stațiile nu au neapărat nevoie de ultima versiune a datelor ale căror copii sclav le dețin.

Dezavantajele acestui protocol sunt:

rezolvarea blocajelor mortale este destul de complexă din cauza multiplelor module care gestionează blocările;

există, totuși, un grad de centralizare: blocările pentru o copie principală sunt gestionate de o singură stație.

Acest ultim dezavantaj poate fi depășit desemnând o stație de rezervă pentru a reține informațiile referitoare la blocări.

V.3.3. Protocolul 2PL-distribuit

Și acest protocol încearcă să rezolve unele dintre problemele protocolului 2PL-centralizat, de data aceasta prin distribuirea unor module de gestionare a blocărilor pentru datele de pe stațiile corespunzătoare. Dacă datele nu sunt replicate acest protocol este echivalent cu 2PL-copie principală.

Acest protocol este de tipul ROWA (Read-One-Write-All), adică orice copie a unui obiect de date poate fi blocată pentru citire dar toate copiile trebuie blocate pentru scriere.

Dezavantajele acestui protocol sunt:

rezolvarea blocajelor mortale este foarte complexă;

costurile comunicațiilor în rețea pentru acordarea blocării sunt foarte mari (5n mesaje).

V.3.4. Protocolul blocării majorității

Acest protocol este o extensie a protocolului 2PL-distribuit, extensie care nu necesită blocarea tuturor copiilor unui obiect de date înainte de actualizare.

La fel ca la 2PL-distribuit, există câte un modul la fiecare stație care gestionează blocările pentru datele de pe acea stație. Atunci când o tranzacție dorește să scrie sau să citească un obiect de date care este replicat la n stații, trebuie trimise cereri de blocare la mai mult de jumătate din cele n, nu neapărat la toate. Tranzacția se poate efectua dacă a obținut blocarea din partea majorității. Dacă nu a primit acordul majorității într-un anumit interval de timp, tranzacția este anulată și toate cele n stații sunt informate despre anulare. Dacă, în schimb, primește acordul majorității atunci informează toate celelalte stații (dintre cele n) că deține blocarea.

Dezavantajele acestui protocol sunt:

este foarte complicat de implementat;

rezolvarea blocajelor mortale este foarte complexă;

sunt necesare cel puțin mesaje pentru blocare și pentru deblocare;

în cazul blocării pentru citire este nevoie de acordul majorității, pe când acordul pentru blocarea unei singure copii ar fi de ajuns.

V.4. PROTOCOLUL “ETICHETELOR DE TIMP” (TIMESTAMPS)

Obiectivul acestui protocol este de a ordona tranzacțiile astfel încât tranzacțiile mai vechi (cele cu etichete mai mici) să aibă prioritate în cazul unui conflict.

Într-un mediu distribuit problema principală este generarea unor etichete unice, atât local cât și global. Utilizarea ceasurilor stațiilor nu rezolvă pe deplin problema și, în plus, aceste ceasuri nu sunt neapărat sincronizate. În general, soluția este folosirea unei perechi: <eticheta locală, identificatorul de stație>. Identificatorul de stație este plasat în poziția mai puțin semnificativă pentru a asigura desfășurarea tranzacțiilor în funcție de momentul începerii lor și nu în funcție de stația de la care provin.

Pentru sincronizarea ceasurilor sin sistem fiecare stație va include în orice mesaj și valoarea ceasului său. La primirea unui mesaj, fiecare stație compară ceasul său cu cel primit plus o întârziere oarecare. Dacă valoarea ceasului propriu este mai mică atunci ea este actualizată. Utilizând acest mecanism se ajunge foarte repede la o oră unică în rețea.

Nu numai tranzacțiile primesc etichete ci și datele atunci când sunt actualizate. O cerere este executată dacă eticheta sa este mai mare decât cea a articolelor de date la care solicită accesul.

V.5. PROTOCOLUL “INELULUI VIRTUAL”

În cazul acestui protocol trebuie stabilită o anumită ordine în rețea (fiecare stație să aibă un predecesor și un succesor bine stabiliți) astfel încât să fie posibilă realizarea unui inel virtual. Pe acest inel circulă continuu un tichet (inelul poate fi văzut ca o rețea circulară de cale ferată pe care circulă vagoane). Un vagon poate fi ocupat cu ajutorul tichetului pe care se “completează” tranzacția de efectuat. Vagonul nu va fi descărcat de către destinatar (destinatari) ci de furnizor, deoarece destinatarul poate să lipsească. Când tichetul ajunge din nou la furnizor acesta îl eliberează și îl transmite mai departe.

V.6. REZOLVAREA BLOCAJELOR MORTALE (INTERBLOCĂRII)

Orice algoritm de control al concurenței bazat pe blocare (precum și unii algoritmi bazați pe etichete de timp) poate cauza interblocări.

Interblocarea (deadlock), sau blocajul mortal, este un impas care rezultă când două tranzacții blochează anumite resurse, după care solicită fiecare resursele blocate de cealaltă:

Tranzacția A Resurse Tranzacția B

1 – blocare X

4 – așteptare până la

eliberarea resursei X

3 – așteptare până la

eliberarea resursei Y 2 – blocare Y

Fig.27. Interblocare

La nivelul sistemului trebuie să existe facilități de prevenire sau rezolvare a acestor situații. Astfel, poate fi implementată una din următoarele două strategii:

Prevenirea interblocării – presupune ca programele să blocheze toate resursele de care au nevoie, încă de la începutul fiecărei tranzacții. În exemplul de mai sus, tranzacția A ar fi trebuit să blocheze ambele resurse încă de la început. Dacă una dintre resurse ar fi fost blocată ar fi fost necesar să se aștepte până la eliberarea ei.

Această strategie este dificil de implementat și adesea nu este aplicată, deoarece în cele mai multe cazuri este imposibil de precizat înainte ce resurse vor fi necesare pentru o tranzacție.

Soluționarea interblocării – presupune permiterea apariției interblocării și existența unor mecanisme pentru detectarea și eliminarea acesteia.

Există trei metode pentru detectarea interblocării: centralizată, ierarhică și distribuită. Toate se bazează pe graful precedențelor care reflectă dependențele dintre procese din punct de vedere al ordinii în care trebuie executate. Într-un astfel de graf fiecare nod reprezintă un proces activ, iar arcele se trasează conform următoarei reguli: dacă procesul P deține sursa A și procesul Q o solicită, atunci în graf va fi trasat arcul Q –> P care arată că execuția procesului Q este condiționată de cea a procesului P. Existența unei interblocări va fi semnalată prin prezența unui ciclu în graf. Iată un simplu algoritm de determinare a interblocării:

fie v1 – vectorul obținut prin aplicarea operației “SAU” elementelor liniilor matricei grafului de precedență;

fie v2 – vectorul obținut prin aplicarea operației “SAU” elementelor coloanelor matricei grafului de precedență;

fie v3 = v1 “ȘI” v2; procesele pentru care s-a obținut valoarea 0 în v3 sunt eliminate din matrice, ele neputând fi implicate într-un blocaj mortal deoarece sau nici un proces nu așteaptă după ele sau ele nu așteaptă după nici un alt proces;

toate procesele rămase sunt implicate în blocaje mortale (nu neapărat toate într-un singur blocaj); unul dintre aceste procese va fi întrerupt, efectele lui asupra BD vor fi anulate și va aștepta un timp pentru a fi reluat; eliminarea unui proces va putea face posibilă continuarea altor procese dintre cele rămase; pentru determinarea celorlalte blocaje (altele decât cel în care este implicat procesul eliminat) reluăm algoritmul de la pasul 1.

Procesul care va fi eliminat poate fi:

procesul cu cele mai puține resurse blocate;

procesul care nu a făcut încă actualizări în BD;

procesul cu cea mai mică prioritate;

procesul cu cel mai recent început;

procesul cel mai vechi;

procesul care a cerut ultimul o blocare a unei resurse.

Prezentăm în continuare cele trei metode de detectare a interblocării:

DETECTAREA CENTRALIZATĂ

În cazul acestei metode o singură stație este desemnată ca și coordonator global al interblocării (CGI). Acest CGI are responsabilitatea de a construi și de a menține graful global de precedență. Periodic fiecare modul de gestiune a blocărilor trimite CGI propriul graf local. În momentul în care CGI detectează cicluri în graful global, decide care tranzacție să fie suspendată și informează toate stațiile implicate în acea tranzacție să anuleze efectele acesteia.

Pentru a minimiza transferul de date, modulele pot transmite doar schimbările intervenite în graful local de la ultima transmisie. Aceste schimbări pot reprezenta adăugări sau anulări de muchii.

Dezavantajul acestei metode este disponibilitatea redusă a sistemului: dacă stația coordonatoare cade atunci sistemul nu mai beneficiază de rezolvarea blocajelor mortale.

DETECTAREA IERARHICĂ

În cazul acestei metode stațiile din rețea sunt organizate (logic) într-o ierarhie. Fiecare stație trimite propriul graf local stației care se află deasupra sa în ierarhie. Iată o posibilă ierarhie pentru opt stații (S1,…,S8):

Fig.28. Detectarea ierarhică a interblocărilor

Pe nivelul 1 al ierarhiei se află chiar stațiile, unde are loc o detectare locală a interblocărilor, pe nivelul 2 sunt, în cazul nostru, doar patru stații care detectează interblocările în care sunt implicate două stații alăturate: (1,2), (3,4), (5,6), (7,8) ș.a.m.d. Rădăcina ierarhiei este Detectorul Interblocărilor Globale.

Această metodă sporește disponibilitatea sistemului însă complexitatea implementării este foarte mare.

DETECTAREA DISTRIBUITĂ

Dintre multiplele propuneri pentru o astfel de detectare prezentăm una dintre cele mai cunoscute. În cazul acestei metode fiecărui graf local i se adaugă un nod extern, Text, pentru a indica o tranzacție la o altă stație. Atunci când o tranzacție T1 la stația S1 creează o sub-tranzacție la o altă stație, să zicem S2, un arc de la Text la T1 este adăugat grafului local. De asemenea, la stația S2, este adăugat un arc de la Text la nodul care reprezintă sub-tranzacția lui T1.

Să considerăm următorul exemplu: fie S1, S2, S3 – trei stații și T1, T2, T3 – trei tranzacții inițiate astfel: Ti la Si, i=1,3. În plus T1 are o subtranzacție la S2, T2 are o subtranzacție la S3, iar T3 are o subtranzacție la S1. Cererile pentru blocările resurselor decurg astfel:

În acest caz grafurile locale vor fi:

S2 S3 S1

S3 S1 S2

S1 S2 S3

Fig.29. Grafurile locale în detectarea distribuită.

Arcele dintre tranzacții și Text sunt etichetate cu stațiile implicate. De exemplu, la stația S1, arcul etichetat cu S2 indică faptul că T1 are o sub-tranzacție la S2.

Dacă un graf local conține cicluri care nu implică nodul Text atunci stația respectivă este în blocaj mortal. Dacă nodul Text este implicat în ciclu, nu putem spune decât că s-ar putea să fie vorba despre un blocaj mortal. Pentru a determina dacă există interblocarea trebuie unite grafurile locale.

Dacă un graf local conține un potențial blocaj mortal atunci el conține un ciclu de forma:

Text Ti Tj … Tk Text.

Pentru a preveni transmiterile inutile de grafuri locale se utilizează o strategie bazată pe “etichetele de timp” alocate tranzacțiilor și care utilizează următoarea regulă: stația la care se înregistrează ciclul de mai sus transmite propriul graf local stației Sk, eticheta arcului Tk Text, dacă eticheta (Ti) < eticheta (Tk) (în caz contrar stația așteaptă primirea unui graf local de la alte stații). Presupunem că eticheta (Ti) < eticheta (Tk), deci graful local care conține ciclul va fi transmis stației Sk. Acesta adaugă informațiile primite propriului graf local. Dacă există cicluri care nu implică nodul Text avem de-a face cu un blocaj mortal. Dacă nu există un astfel de ciclu procesul continuă până când apare un ciclu care îl conține pe Text, caz în care vom suspenda una din tranzacțiile implicate. Punctul final al procesului, dacă nu s-a determinat blocajul în pașii anteriori, îl reprezintă construirea grafului global. Dacă nici în acest graf nu putem detecta un ciclu format doar din tranzacții atunci nu există interblocare în sistem.

Revenind la exemplu, cele trei grafuri locale conțin ciclurile:

S1: Text T3 T1 Text,

S2: Text T1 T2 Text,

S3: Text T2 T3 Text.

Putem transmite graful local de la stația S1 stației S2 unde se află subtranzacția lui T1 după care T1 așteaptă. Graful extins de la S2 este:

Text T3 T1 T2 Text.

Și acest graf conține un potențial blocaj mortal. În consecință transmitem noul graf extins stației S3 (eticheta arcului T2 Text). Graful extins de la stația S3 conține ciclul:

Text T3 T1 T2 T3 Text.

Acest ciclu indică interblocarea celor trei tranzacții.

Această metodă de detectare a interblocării sporește disponibilitatea sistemului, însă sunt necesare foarte multe transmisii de date prin rețea pentru a detecta și rezolva un blocaj mortal.

V. SALVAREA ȘI RESTAURAREA BAZEI DE DATE DISTRIBUITE

Salvarea și restaurarea BD au ca scop readucerea datelor la o formă consistentă în urma unor evenimente care au alterat corectitudinea lor, precum:

pierderea unui mesaj;

căderea unei linii de comunicație;

căderea unei stații;

partiționarea rețelei;

defecțiunea suportului fizic pe care este memorată BD.

Pierderea unui mesaj sau ordonarea necorespunzătoare a mesajelor sunt rezolvate transparent de către componenta de comunicație a SGBDD. În cazul defecțiunii suportului fizic acesta va fi inutilizabil, deci toate datele se vor pierde dacă nu există copii ale BD În celelalte cazuri, prin întreruperea tranzacțiilor active în momentul respectiv, BD va rămâne într-o stare de inconsistență.

În aceste situații trebuie să fie posibilă refacerea unei stări anterioare consistente a BD. O stare consistentă a BD este starea în care sunt reflectate rezultatele finale ale execuției unor tranzacții, nici o tranzacție nu este în curs de execuție și sunt satisfăcute restricțiile de integritate. Acțiunile întreprinse în acest sens se înscriu în procesul de restaurare a BD.

V.1. INFORMAȚII UTILIZATE ÎN PROCESUL DE RESTAURARE

Salvarea, în contextul asigurării integrității BD, este procesul de stocare de date în vederea folosirii lor pentru restaurarea bazei de date. Volumul informațiilor salvate, natura lor și intervalul de timp dintre două operații succesive de salvare vor influența procesul de restaurare. Astfel, stocarea unei cantități mari de date, cu o frecvență mare și în forme diferite face restaurarea simplă și rapidă însă cauzează întreruperi ale lucrului sau mărirea timpului de răspuns în exploatarea BD. În caz contrar, cu cât informațiile de care dispunem sunt mai sărace, cu atât procesul de restaurare va fi mai complicat și de durată.

Datele salvate pot fi diferite combinații între:

copii ale bazei de date;

jurnale ale tranzacțiilor;

jurnale ale imaginilor înregistrărilor din BD.

Copiile bazei de date pot fi realizate automat de către sistem la anumite intervale de timp sau la comanda administratorului BD. Dacă sunt utilizate suporturi magnetice diferite de cele pe care rezidă BD copiile constituie singura posibilitate de recuperare a BD. Ele pot fi utilizate însă ca unică sursă în procesul de restaurare doar în situația în care prelucrările efectuate între momentul realizării copiilor și cel al apariției unei defecțiuni pot fi reluate. Acest lucru este posibil dacă prelucrările sunt efectuate într-o ordine cunoscută și timpul necesar pentru reprocesarea lor nu este foarte mare. Această limită, ca și durata mare de execuție a acestei copii fac ca anumite sisteme să recurgă la efectuarea de copii ale jurnalelor BD. Volumul datelor ce vor fi copiate este în acest caz mult mai mic, iar procesul de restaurare implică doar într-o mică măsură intervenția umană.

Jurnalul tranzacțiilor este un fișier special întreținut de sistem, în care sunt memorate informații despre tranzacțiile efectuate asupra BD, cum sunt:

identificatorul sau codul tranzacției;

momentul începerii execuției tranzacției;

numărul terminalului sau utilizatorului care a inițiat-o;

datele introduse;

înregistrările modificate și tipul modificării.

Pe baza acestui jurnal va putea fi stabilită ulterior succesiunea corectă și natura prelucrărilor efectuate în intervalul de timp pentru care trebuie să se asigure restaurarea BD.

Jurnalul imaginilor se deosebește de jurnalul tranzacțiilor prin aceea că el nu conține descrierea operațiilor efectuate ci efectul acestora. Poate îmbrăca una din formele:

jurnalul cu imaginea înregistrărilor după modificare (after image) va conține copia fiecărei înregistrări modificate;

jurnalul cu imaginea înregistrărilor înainte de modificare (before image);

jurnalul care conține atât before image cât și after image.

În prima formă, jurnalul imaginilor permite restaurarea BD prin derularea înainte a tranzacțiilor într-un timp mai scurt decât în cazul utilizării jurnalului. În mod similar, cea de-a doua formă va putea fi utilizată pentru derularea înapoi a tranzacțiilor, fiind necesară doar regăsirea înregistrării memorate la începutul fiecărei tranzacții. Cea de-a treia formă facilitează mult procesul de restaurare însă presupune menținerea unui volum mare de informații redundante (pentru o înregistrare, ceea ce constituie after image, după modificare, va deveni before image la următoarea modificare).

V.2. TEHNICI DE BAZĂ FOLOSITE ÎN PROCESUL DE RESTAURARE

O cădere a sistemului lasă BD într-o stare de inconsistență care poate constitui un punct de plecare în procesul de restaurare, în timp ce, în cazul unei defecțiuni a suportului magnetic restaurarea va fi posibilă doar dacă există copii ale BD. Pe aceste baze, deci, procesul de restaurare va trebui să asigure o stare consistentă a BD, minimizând totodată volumul prelucrărilor pierdute.

Pentru BD inconsistentă, aceasta înseamnă eliminarea efectelor tranzacțiilor active în momentul căderii sistemului și reflectarea în BD a rezultatelor tranzacțiilor terminate, dar care din anumite motive nu apar în BD. Pentru o copie anterioară a BD, va trebui să existe posibilitatea ca într-un timp cât mai scurt aceasta să fie adusă la o stare consistentă.

Tehnicile de bază utilizate pentru restaurare sunt:

derularea înapoi a tranzacțiilor necompletate (ROLL BACK) – care presupune anularea modificărilor efectuate;

derularea înainte a tranzacțiilor completate dar nereflectate în BD (ROLL FORWARD) – care presupune efectuarea acelor transformări prin care BD restaurată să conțină rezultatele acestora.

Se observă deci că tranzacția poate fi considerată ca unitatea de restaurare, în sensul că BD restaurată trebuie fie să reflecte rezultatele finale ale tranzacțiilor, fie să nu fie afectată de acestea.

În acest sens, controlul restaurării într-un mediu distribuit își propune să mențină atomicitatea și durabilitatea tranzacțiilor distribuite. Pentru a asigura atomicitatea tranzacțiilor globale sistemul trebuie sau să realizeze toate subtranzacțiile implicate sau toate acestea să fie anulate. Dacă SGBDD detectează o defecțiune (căderea unei stații sau inaccesibilitatea unei stații), trebuie să parcurgă următorii pași:

întreruperea tuturor tranzacțiilor afectate de defecțiune;

marcarea stației respective pentru a preveni orice încercare de contactare de către alte stații;

verificarea periodică pentru a vedea dacă stația și-a revenit sau așteptarea unui mesaj din partea acestei;

la revenire, stația afectată trebuie să inițieze o procedură de restaurare pentru a sista toate tranzacțiile parțiale care erau active în momentul defecțiunii;

după restaurarea locală, stația afectată trebuie să-și actualizeze copiile datelor pentru a face BDD consistentă.

Asigurarea atomicității tranzacțiilor se poate face utilizând protocolul de realizare a tranzacțiilor în două faze 2PC (2 Phase – Commit). Acesta constă din următoarele:

faza de pregătire – la lansarea unei actualizări distribuite, nodul de unde se lansează tranzacția devine nod coordonator pentru acea tranzacție. El analizează tranzacția și determină BDL ce vor participa la execuția ei. Transmite tranzacția sau părți ale acesteia și ordinul “PREPARE” tuturor cooperanților și așteaptă răspunsurile lor. Dacă primește un răspuns “ABORT” de la cel puțin un cooperant, coordonatorul anulează tranzacția și trimite tuturor mesajul “GLOBAL ABORT”. Dacă primește răspunsul “PREPARED” de la toți atunci faza de pregătire s-a încheiat și se trece la faza a doua;

faza de realizare – coordonatorul transmite “GLOBAL COMMIT” la BDL implicate și așteaptă mesajul “TERMINATED” de la fiecare din ele. Dacă o BDL nu confirmă realizarea, coordonatorul retransmite decizia globală de realizare acelei stații până când este primit mesajul “TERMINATED”.

Procesele în care există mesaje de “ABORT” sau nu sunt algoritmizate astfel:

Coordonator Cooperant

Commit:

scrie “begin commit” în jurnal

trimite “PREPARE” tuturor cooperanților

PREPARE:

scrie “ready commit” în jurnal

așteaptă răspunsurile trimite “PREPARED” coordonatorului

așteaptă decizia globală

Ready commit:

dacă toți cooperanții au transmis mesajul

“PREPARED” atunci:

scrie “commit” în jurnal

trimite “GLOBAL COMMIT” tuturor

GLOBAL COMMIT:

scrie “commit” în jurnal

așteaptă răspunsurile realizează tranzacția

trimite confirmarea

Acknowledgements:

dacă toți au confirmat realizarea

tranzacției atunci:

scrie “end-of-transaction” în jurnal

a)

Coordonator Cooperant

Commit:

scrie “begin commit” în jurnal

trimite “PREPARE” cooperanților

PREPARE:

scrie “ABORT” în jurnal

așteaptă răspunsurile trimite “ABORT” coordonatorului

anulează tranzacția

Abort:

dacă un cooperant a răspuns “ABORT”

atunci:

scrie “ABORT” în jurnal

trimite “GLOBAL ABORT” tuturor

așteaptă răspunsurile

b)

Fig.30. a) 2PC în cazul realizării tranzacției;

b) 2PC în cazul nerealizării tranzacției;

Dacă în timpul desfășurării unei tranzacții cade o stație atunci:

stațiile rămase operaționale invocă un protocol de terminare;

stațiile căzute, la repornire, invocă un protocol de restaurare;

V.3. PROTOCOALE DE TERMINARE

Un protocol de terminare este invocat atunci când coordonatorului sau unui cooperant le expiră timpul de așteptare a mesajelor. Acțiunile ce trebuie efectuate depind de momentul în care a intervenit expirarea și sunt diferențiate pentru coordonator față de cooperant.

Coordonatorul se poate găsi într-una din următoarele stări: INITIAL, WAITING, DECIDED sau COMPLETED așa cum este prezentat în Fig.31.:

trimite “PREPARE”

trimite decizia globală

primește răspunsurile

Fig.31. Stările posibile pentru coordonator

Expirarea timpului de așteptare nu poate interveni decât în cele două stări din mijloc: WAITING, DECIDED.

Iată acțiunile ce trebuie efectuate:

expirarea timpului în starea WAITING: coordonatorul așteaptă ca stațiile cooperante să răspundă dacă sunt pregătite sau nu pentru realizarea tranzacției. În acest caz el nu poate decide să trimită “GLOBAL COMMIT” deoarece nu a primit toate mesajele necesare, deci va putea trimite “GLOBAL ABORT” tuturor stațiilor;

expirarea timpului în starea DECIDED: coordonatorul așteaptă ca toți cooperanții să confirme realizarea tranzacției (sau nerealizarea). Dacă unele stații nu au răspuns, coordonatorul le trimite din nou decizia globală și așteaptă răspunsurile lor.

Cooperantul se poate afla într-una dintre următoarele stări: INITIAL, COMMITED sau ABORTED:

primește “PREPARE”

trimite “ABORT” trimite “PREPARED”

“GLOBAL ABORT” “GLOBAL COMMIT”

Fig.32. Stările pentru nodul cooperant

Expirarea timpului de așteptare poate interveni doar în faza PREPARED, când cooperantul așteaptă decizia globală. În acest caz, deși el trimisese mesajul “PREPARED” nu își poate asuma dreptul de a realiza tranzacția, rămânând blocat. Pentru a se debloca el poate încerca contactarea celorlalți cooperanți pentru a afla decizia globală. Pentru a cunoaște pe ceilalți, coordonatorul poate trimite împreună cu mesajul “PREPARE” o listă a cooperanților. Acest mod de deblocare este cunoscut sub numele protocolul de terminare cooperant. Acesta reduce riscul blocării însă nu îl elimină, procesele blocate trebuind să continue încercările de deblocare până când defecțiunea este înlăturată. Dacă doar coordonatorul a căzut, iar cooperanții află acest lucru, ei pot alege un nou coordonator care să-i deblocheze.

V.4. PROTOCOALE DE RESTAURARE

Dacă până acum am discutat despre acțiunile ce trebuie efectuate de către stațiile operaționale în cazul unei defecțiuni, în această parte vom discuta ce acțiuni trebuie efectuate la repornirea stațiilor căzute. Aceste acțiuni depind în ce stare se afla coordonatorul sau cooperantul în momentul defecțiunii.

Coordonatorul este afectat de defecțiuni în următoarele stări:

defecțiune în starea INITIAL – coordonatorul nu a apucat să înceapă procedura de realizare așa că, la repornire, începe această procedură;

defecțiune în starea WAITING – a trimis mesajul “PREPARE” și chiar dacă nu a primit toate răspunsurile, nu a primit nici un “ABORT”. În acest caz reîncepe procedura de realizare;

defecțiune în starea DECIDED – a trimis decizia globală. La repornire, dacă a primit toate confirmările, poate termina tranzacția. Dacă nu inițiază protocolul de terminare discutat mai sus.

Cooperantul

Obiectivul protocolului de restaurare pentru un cooperant este de a asigura, la repornire, execuția aceleiași acțiuni ca și celelalte stații cooperante rămase funcționale.

Acțiunile ce trebuie efectuate în cazul unei defecțiuni a cooperantului la repornirea acestuia se diferențiază în funcție de starea în care au apărut defecțiunile.

defecțiune în starea INITIAL – cooperantul nu a transmis încă nici “ABORT”, nici “PREPARE”. De aceea, la repornire, poate decide unilateral să anuleze tranzacția (coordonatorul nu putea să decidă realizarea acesteia fără acordul său);

defecțiune în starea PREPARED – cooperantul a transmis mesajul “PREPARED” coordonatorului. În acest caz, restaurarea se face apelând la protocolul de terminare.

defecțiune în stările ABORTED/COMMITED – cooperantul a executat sau a anulat tranzacția. La repornire nu se efectuează nici o acțiune suplimentară.