Operatii Concurente Asupra Bazelor de Date

INTRODUCERE

Până nu demult, conceptul nostru despre bazele de date a fost unul în care programele care accesează o bază de date sunt rulate unul după altul. De multe ori aceasta este situația în care ne aflăm. Astăzi există de asemenea numeroase aplicații în care mai mult de un program, sau diferite execuții ale aceluiași program rulează simultan accesând aceeași bază de date. Un astfel de exemplu este un sistem de rezervare a locurilor la o companie aeriană, unde mai mulți agenți pot vinde bilete sau face rezervări de locuri. Problema care intervine este aceea că dacă nu suntem atenți cum permitem la mai mult de două programe să acceseze baza de date, putem vinde același loc de două ori. Intuitiv, două procese care citesc și schimbă valoarea aceluiași obiect nu trebuie rulate concurent .

Un al doilea exemplu este acela al unei baze de date statice, unde mai mulți utilizatori pot face interogări în același timp. Aici, atât timp cât nimeni nu schimbă datele, nu este important în ce ordine procesele citesc datele, putem lăsa sistemul de operare să programeze simultan cererile de citire cum dorește. În acest gen de situații, unde se face numai citire, dorim să permitem un număr maxim de operații concurente, ca să economisim timp. În cazul sistemului de rezervări, unde citirea și scrierea sunt amândouă în progres, avem nevoie de restricții pentru cazurile în care permitem ca două programe să ruleze concurent.

În această lucrare vom considera modele de procese concurente care sunt legate de operațiile pe bazele de date. Modelele se disting în primul rând prin detaliile care descriu accesul la elementele din baza de date. Pentru fiecare model vom descrie o cale rezonabilă de a permite acele operații concurente care păstrează integritatea bazelor de date și să prevenim acele operații care pot distruge integritatea unei baze de date, atât cât un model cu detalii limitate ne poate spune despre integritate. Și ca o regulă, cu cât modelul este mai detaliat cu atât mai mult putem permite concurența în siguranță.

De asemenea în această lucrare vom discuta și despre felul în care sunt abordate operațiile concurente pe baze de date în limbajul de programare Visual FoxPro. Partea practică a acestei lucrări o reprezintă aplicația “Administrația unui cămin studențesc”, care reprezintă un sistem informatic pentru un cămin studențesc. Această aplicație simulează serviciile de cazare și plată a taxei de cămin care se realizează într-un cămin studențesc.

TRANZACȚII ASUPRA BAZELOR DE DATE

CONCEPTE DE BAZĂ

O tranzacție este o singură execuție a unui program. Acest program poate fi o simplă interogare sau un program complex cu apeluri din unul din limbajele QUEL, SEQUEL, etc… Mai multe execuții independente ale aceluiași program pot fi în progres simultan; fiecare dintre aceste execuții este o tranzacție.

ITEM-URI

Ne imaginăm că baza de date este împărțită în item-uri (articole) care sunt porțiuni din baza de date care pot fi blocate. Prin blocarea unui item o tranzacție poate preveni alte tranzacții să mai acceseze acel item, până când tranzacția care deține blocajul nu deblochează itemul respectiv. O parte a DBMS (DataBase Maneger System) numită managerul de blocaje asigneză și înregistrează blocajele, ca de altfel și arbitrarea între două sau mai multe cereri de a bloca același item.

Natura și mărimea item-urilor sunt subiectele unor teme ce urmează în continuare. De exemplu, în modelul relațional de date, putem alege item-uri mari, cum sunt relațiile, sau item-uri mici ca tuple individuale sau componente din tuple. Putem alege o mărime intemediară pentru item-uri, de exemplu item-urile pot fi colecții de 100 de tuple din aceeași relație. În modelul de rețea, de exemplu, un item poate fi o colecție a tuturor înregistrărilor unui singur tip.

Alegând item-uri mari sistemul poate pica în timpul menținerii blocărilor, în timp ce alegând item-uri mici putem permite mai multor tranzacții să opereze în paralel. Dacă o tranzacție tipică (într-un sistem relațional) citește sau modifică un tuplu, care se găsește cu ajutorul unui index, ar fi mai convenabil de tratat tuplele ca item-uri. Dacă o tranzacție tipică face o operație de join pe două sau mai multe relații, atunci poate ar fi mai bine să tratăm relațiile ca item-uri.

În ceea ce urmează, vom presupune că atunci când o parte a unui item este modificată, întreg item-ul este modificat și primește o valoare unică și neegală cu nici o altă valoare care poate fi obținută prin orice altă modificare. Facem această presupunere nu numai pentru a simplifica modelarea tranzacțiilor. În practică, necesită multă muncă din partea sistemului pentru a deduce fapte ca acela că rezultatul unei modificări a unui item dă acelui item aceeași valoare pe care o avea după câteva modificări precedente. Mai mult dacă sistemul poate să-și amintească, când o parte a unui item a rămas neschimbată după ce item-ul a fost modificat, acesta poate de asemenea să împartă item-ul în mai multe item-uri mai mici. O consecință a presupunerii noastre despre indivizibilitatea item-urilor este că nu vom greși dacă vom considera item-urile ca simple variabile, așa cum sunt folosite în limbajele de programare obișnuite.

BLOCAJE

EXEMPLUL 1 : Pentru a vedea necesitatea blocării item-urilor vom considera două tranzacții T1 și T2. Fiecare accesează un item A, care are o valoare înteragă, și adaugă 1 la A. Cele două tranzacții sunt execuții ale programului P defint astfel :

P : READ A; A:=A+1; WRITE A.

Valoarea lui A există în baza de date. P citește A și incrementează această valoare în zona lui de lucru și scrie rezultatul în baza de date. În Fig. 1 vedem cele două tranzacții executându-se într-un stil împănat, și înregistrăm valoarea lui A așa cum apare ea în baza de date la fiecare pas.

Fig. 1 . Manifestarea tranzacțiilor necesită blocarea item-ului A.

Observăm că deși două tranzacții adaugă 1 la A, valoarea lui A este incrementată doar cu o unitate. Aceasta este o problemă serioasă dacă A reprezintă locurile vândute la zborul unui avion, de exemplu.

Soluția problemei reprezentată în EXEMPLUL 1 este de a efectua un blocaj asupra lui A. Înaintea citirii lui A, o tranzacție T trebuie să blocheze A, aceasta previne accesarea lui A de alte tranzacții până când T nu termină cu A. Mai mult, necesitatea ca T să blocheze A previne accesarea lui A de către T dacă alte tranzacții folosesc deja A. T trebuie să aștepte până când altă tranzacție deblochează A, asta făcându-se numai când această tranzacție termină cu A.

Vom considera acum programele care interacționează cu baza de date nu numai prin citirea și scrierea item-urilor, dar și prin blocarea și deblocarea lor. Presupunem că blocarea unui item trebuie făcută înaintea citirii sau scrierii acelui item, și că operația de blocare se comportă ca o primitivă de sincronizare. Astfel, dacă o tranzacție încearcă să blocheze un item deja blocat, aceasta așteaptă până când blocajul este eliberat de o comandă de deblocare, aceasta fiind executată de tranzacția care a realizat blocajul. Eventual putem presupune că orice program este scris astfel încât să deblocheze orice item pe care îl blochează. Un program cu tranzacții formate din pași elementari, în care regulile ce privesc blocajele sunt respectate, se termină legal.

EXEMPLUL 2 : Programul P din EXEMPLUL 1, se poate scrie cu blocaje astfel :

P : LOCK A ; READ A ; A:=A+1 ; UNLOCK A .

Presupunem din nou că T1 și T2 sunt două execuții ale lui P. Dacă T1 începe primul, el cere un blocaj asupra lui A. Presupunând că nici o altă tranzacție nu a blocat A, sistemul îi satisface cererea de blocare. Acum T1, și numai T1 poate accesa A. Dacă T2 începe înainte ca T1 să se termine, atunci când T2 încearcă să execute LOCK A, sistemul cauzează punerea în așteptare a lui T2. Numai atunci când T1 execută UNLOCK A sistemul va permite ca T2 să-și înceapă acțiunea. Ca o concluzie, eroarea indicată în EXEMPLUL 1 nu mai poate apărea : oricum ar fi, T1 și T2 se execută complet înaintea altor startări și efectul lor combinat este adăgarea lui 2 la A.

AȘTEPTAREA LA NESFÂRȘIT ȘI BLOCAREA DEFINITIVĂ

Am postulat o parte a DBMS care introduce blocajele asupra item-urilor. Un astfel de sistem nu se poate comporta capricios și nu pot apărea fenomene nedorite. În EXEMPLUL 2 am presupus că atunci când T1 eliberează blocajul asupra lui A, T2 este tranzacția care blochează în continuare A. Dar dacă în timp ce T2 așteaptă, o tranzacție T3 face deasemenea o cerere de blocare asupra lui A, și primește acest drept înaintea lui T2. Apoi în timp ce T3 blochează A, T4 face o cerere de blocaj, care va fi aprobată după ce T3 va debloca A, și așa mai departe. Evident este posibil ca T2 să aștepte la infinit, în timp ce alte tranzacții să aibă întotdeauna un blocaj asupra lui A, cu toate că T2 ar fi putut să blocheze A într-un număr nelimitat de ori. Un astfel de caz este numit livelock, adică așteptare la nesfârșit. Este o problemă care poate să apară în orice mediu în care se execută procese concurente. O varietate de soluții au fost propuse de arhitecții sistemelor de operare, iar noi nu vom discuta aici acest subiect, el neținând numai de sistemul de baze de date. Strategia “primul venit – primul servit” elimină livelock-urile, și vom presupune în continuare că livelock-ul nu este o problemă.

Există o altă problemă care poate apărea dacă nu suntem atenți. Această problemă, numită deadlock, adică blocarea definitivă poate fi ilustrată cel mai bine de un exemplu.

EXEMPLUL 3 : Presupunem că avem două tranzacții T1 și T2, ale căror acțiuni specifice sunt concentrate, din punct de vedere concurent, pe:

T1 : LOCK A LOCK B UNLOCK A UNLOCK B

T2 : LOCK B LOCK A UNLOCK B UNLOCK A .

Presupunem că T1 și T2 folosesc A și B, dar nu aceasta este important aici. Presupunem că T1 și T2 își încep execuția aproximativ în același timp. T1 cere și i se aprobă un blocaj asupra lui A, și T2 cere și i se aprobă un blocaj asupra lui B. Apoi T1 cere un blocaj asupra lui B și este forțat să aștepte deoarece T2 are un blocaj asupra acestui item. Similar, T2 cere un blocaj asupra lui A și va trebui să aștepte ca T1 să deblocheze A. Astfel nici o tanzacție nu poate începe acțiunea, fiecare așteptând pe cealaltă să deblocheze un item de care are nevoie, deci amândouă așteaptă la nesfârșit.

O situație în care o tranzacție dintr-un set S de mai multe tranzacții așteaptă să blocheze un item care este blocat de alte tranzacții din setul S se numește deadlock. De vreme ce fiecare tranzacție din S este în așteptare, ea nu poate debloca un item de care alte tranzacții din S au nevoie să-și înceapă acțiunea, așa deci toate așteaptă la nesfârșit. Ca și livelock-ul, prevenirea deadlock-ului este un subiect mult discutat în literatura sistemelor de operare și a proceselor concurente în general. Câteva idei apropiate de o eventuală soluție sunt următoarele :

Fiecare tranzacție să facă toate cererile de blocaj odată și sistemul să le acorde pe toate dacă este posibil, sau să nu acorde nici una și să pună procesul în așteptare, dacă unul sau mai multe blocaje sunt deținute de altă tranzacție. Observăm că această regulă va preveni deadlock-ul din EXEMPLUL 3. Sistemul va acorda ambele blocaje, asupra lui A și a lui B, lui T1, dacă acesta le va cere primul : T1 se va termina și astfel T2 poate obține ambele blocaje.

Asignarea unei ordini liniare arbitrare item-urilor și cerința ca toate tranzacțiile să ceară blocaje în această ordine.

A doua idee previne de asemenea deadlock-ul. În EXEMPLUL 3, presupunem că A precede B în ordine (pot exista și alte item-uri între A și B în ordine). Atunci T2 va cere blocajul lui A înaintea lui B și va gasi A deja blocat de T1. T2 nu va putea obține un blocaj asupra lui B, și deci blocajul asupra lui B va putea fi obținut de T1 când acesta o să-l ceară. T1 se va termina, drept care blocajele asupra lui A și B vor fi eliberate, T2 putând astfel să-și înceapă acțiunea. Ca să vedem că în general nici un deadlo Ca să vedem că în general nici un deadlock nu poate apare, presupunem că avem un set S de tranzacții în situația de deadlock, și fiecare tranzacție Ri din S așteaptă altă tranzacție din S să deblocheze un item Ai. Putem presupune că fiecare Ri deține cel puțin un Ai, altfel putem scoate Ri din S și totuși să avem un set de deadlock. Fie Ak primul item dintre Ai în ordinea liniară presupusă. Atunci Rk care așteaptă Ak nu poate ține nici un Ai cu i k, ceea ce este o contradicție.

O altă alternativă de a manevra deadlock-urile este de a nu face nimic să le prevenim. Mai degrabă să examinăm periodic blocajele cerute și să vedem dacă există vreo situație de deadlock. Algoritmul de desenare a grafului ale cărui noduri sunt tranzacții și ale cărui arce, T1T2, semnifică faptul că tranzacția T1 așteaptă să blocheze un item pe care T2 îl ține blocat, face acest test mai ușor; fiecare ciclu indică un deadlock, și dacă nu sunt cicluri atunci nu sunt nici deadlock-uri. Dacă un deadlock este descoperit, atunci cel puțin una din tranzacțiile din deadlock trebuie restartate, și efectul ei asupra bazei de date trebuie anulat. Acest proces de restartare poate fi complicat dacă nu suntem atenți la modul în care tranzacția scrie în baza de date înainte de terminare. Acest subiect este abordat în Secțiunea 6. În viitor vom presupune că nici situațiile de livelock și nici cele de deadlock nu vor aparea în timpul execuției tranzacților.

SERIALIZABILITATEA

Să revenim asupra EXEMPLULUI 1, unde două tranzacții executau un program P, fiecare adăugând 1 la A, apoi A fiind incrementat doar cu 1. Intuitiv simțim că această situație nu este corectă, dar poate că aceste tranzacții au făcut ceea ce a dorit persoana care a scris programul P. Oricum este greu de crezut că programatorul a avut aceasta în minte, deoarece dacă rulăm întâi T1 și apoi T2 obținem un rezultat diferit : la A este adaugat 2. De vreme ce este posibil întotdeauna ca tranzacțiile să se execute una după alta, este mai rezonabil să presupunem că rezultatul normal, sau intenționat al unei tranzacții este rezultatul obținut atunci când tranzacția nu se execută concurent cu alte tranzacții. Astfe execuția concurentă a mai multor tranzacții este corectă dacă și numai dacă efectul lor este același cu cel obținut prin rularea în serial a tranzacțiilor în aceeași ordine.

Definim un orar pentru un set de tranzacții ca fiind o ordine în care sunt făcuți pași elementari (blocări, citiri, ect.). Pașii oricărei tranzacții date trebuie, în mod natural, să apară în orar în aceeași ordine în care apar în programul în care tranzacția este o execuție. Un orar este serial dacă toți pașii fiecarei tranzacții apar consecutiv. Un orar este serializabil dacă efectul său este echivalent cu cel al unui orar serial.

EXEMPLUL 4. Vom considera următoarele două tranzacții :

T1 : READ A; A:=A-10; WRITE A; READ B; B;=B+10; WRITE B

T2 : READ B; B:=B-20; WRITE B; READ C; C;=C+20; WRITE C.

În mod clar, orice orar serial are proprietatea că suma A+B+C este constantă. În Fig. 2(a) vedem un orar serial iar în Fig. 2(b) un orar serializabil dar nu serial. Observăm că Fig. 2(c) are ca efect adăugarea lui 10 la B, mai degrabă decât scăderea lui 20 din B deoarece T1 citește B înainte ca T2 să scrie noua valoare a lui B. Este posibil să prevenim producerea orarului din Fig. 2(c) prin blocarea lui B.

(a) (b) (c)

Fig. 2 Câteva orare.

Reamintim că un orar este serializabil dacă efectul lui este echivalent cu cel al unui orar serial. În general, nu este posibil să testăm când două orare au același efect pentru toate valorile inițiale ale item-urilor, dacă operațiile arbitrare pe item-uri sunt permise. În practică facem câteva presupuneri pentru a simplifica operațiile pe care le facem pe item-uri. În particular, este convenabil să presupunem că valorile nu pot fi egale decât în cazul în care sunt produse de exact aceeași secvență de operații. Așadar, nu privim ( A + 10 ) – 20 și ( A + 20 ) – 30 ca producând aceeași valoare. Ignorarea proprietăților algebrice ale artimeticii implică faptul de a face doar greșeli “nefatale”, în acest sens putem respinge un orar ca fiind neserializabil, când în fapt produce același rezultat ca un orar serial, dar nu vom spune niciodată că un orar este serializabil când în fapt nu este (o greșeală “fatală”). Erorile nefatale pot exclude câteva operații concurente și în felul acesta se poate ca sistemul să ruleze mai încet decât poate teoretic. Oricum aceste erori niciodată nu cauzează un rezultat incorect pentru a fi analizat, așa cum erorile fatale o pot face.

PROTOCOALE ȘI ORARE

Am constatat că tranzacțiile arbitrare, când sunt executate concurent pot da naștere la livelock, deadlock și comportări neserializabile. Pentru a elimina aceste probleme avem două unelte. Prima este programatorul, o porțiune a sistemului bazei de date care arbitrează cererile care produc conflict. Am văzut, de exemplu cum un programator de tipul “primul venit – primul servit” poate elimina livelock-urile. Un programator poate de asemenea trata deadlock-urile și neserializabilitatea prin restartarea uneia sau a mai multor tranzacții, nerealizând nici o acțiune de-a lor până în acel moment. Vom considera restartarea unei tranzacții în Secțiunea 6.

O altă posibilitate de a trata deadlock-urile și neserializabilitatea este de a folosi unul sau mai multe protocoale pe care toate tranzacțiile trebuie să le respecte. Un protocol, în cel mai general sens, este pur și simplu o restricție asupra secvențelor de pași pe care o tranzacție le poate face. De exemplu, strategia de evitare a deadlock-urilor prin cererea blocajelor asupra item-urilor într-o anumită ordine fixată este un protocol. Cea mai mare parte din ceea ce urmează în acest capitol privește dezvoltarea protocoalelor care garantează serializabilitatea.

UN MODEL SIMPLU DE TRANZACȚII

Vom începe prin a introduce, ceea ce este cu siguranță cel mai simplu model de tranzacții, care ne permite totuși să vorbim despre serializabilitate. În acest model, o tranzacție este văzută ca o secvență de instrucțiuni de blocare și de deblocare. Fiecare item blocat trebuie ulterior deblocat. Între un pas LOCK A și următorul pas UNLOCK A, spunem că o tranzacție “deține un blocaj asupra lui A”. Presupunem că o tranzacție nu încearcă să blocheze un item dacă în acel moment ea deține deja un blocaj asupra acelui item și nici nu încearcă să deblocheze un item asupra căruia nu deține un blocaj.

În continuare presupunem că ori de câte ori o tranzacție blochează un item A ea schimbă valoarea lui A, iar valoarea pe care o are A când este deblocat este în mod esențial unică, în sensul că dacă v1 și v2 sunt două valori pe care A le poate avea înainte de pasul LOCK A, atunci valoarea obținută de A după pasul UNLOCK A este întotdeauna diferită în cele două cazuri, cu condiția ca v1v2.

Un mod mai formal de a privi comportarea tranzacțiilor este de a asocia fiecărei perechi LOCK A – UNLOCK A o funcție unică . Reținem că o tranzacție poate avea mai multe asemenea perechi pentru un A dat, în acest caz, cu toate că în general nu este o idee bună, putem bloca și debloca același item mai mult de o singură dată. Fie A0 valoarea inițială a lui A, înainte de a se executa vreo tranzacție. Valorile pe care A le poate avea sunt formule de forma 12….n(A0), unde i sunt funcții asociate perechilor LOCK A – UNLOCK A ale diferitelor tranzacții. Valorile sunt privite ca formule neinterpretate .

EXEMPLUL 5. Fig. 3 reprezintă trei tranzacții și funcțiile asociate fiecărei perechi LOCK – UNLOCK. Fig. 4 reprezintă un posibil orar al acestor tranzacții și efectul final asupra item-urilor A, B, C. Se poate observa că orarul este neserializabil. Presupunem că ar fi serializabil. Dacă T1 precede T2 atunci valoarea finală a lui B ar fi 3(2(B0)), nu 2(3(B0)). Dacă T2 precede T1, atunci valoarea finala a lui A ar fi 0(1(5(A0))), 1(6(5(A0))) sau 1(5(6(A0))) în funcție de ordinile seriale T2 T1 T3, T2 T3 T1 sau T3 T2 T1. Cum nici una din aceste formule nu este de fapt valoarea finală a lui A în Fig. 4 rezultă că T2 nu poate nici precede nici urma T1 într-un orar serial echivalent, deci nu există un orar serial.

Fig. 3 . Trei tranzacții.

Observăm că presupunerea în baza căreia funcțiile produc valori unice este esențială în demonstrație. De exemplu, dacă ar fi fost posibil ca 32 = 23, atunci nu am fi putut exclude posibilitatea ca T1 să preceadă T2. Presupunerea ca valorile să fie unice nu este doar pentru conveniență matematică. Munca necesară pentru a da posibilitatea sistemului bazei de date să examineze tranzacțiile și să depisteze situații ca 32 = 23, și în felul acesta să permită ca o altă categorie de clase să fie privită ca serializabilă, în general nu merită efortul.

Fig. 4. Un orar.

TEST DE SERIALIZABILITATE

Dacă considerăm EXEMPLUL 5 și dovada că orarul din Fig. 4 este neserializabil, vedem necesitatea unui test de serializabilitate. Examinăm un orar cu privire la ordinea în care diferite tranzacții blochează un item dat. Această ordine trebuie să fie corespunzătoare cu echivalentul ipotetic al unui orar serial de tranzacții. Dacă ordinea indusă de două item-uri diferite forțează două tranzacții să apară în ordine diferită, atunci avem un paradox, deoarece amândouă ordinile nu pot să corespundă unui singur orar serial. Putem exprima acest test ca o problemă de găsire a ciclurilor într-un graf direct. Această metodă este descrisă formal în următorul algoritm .

ALGORITMUL 1 : Testarea Seriabilității unui Orar.

Intrare : Un orar S pentru un set de tranzacții T1,…,Tk.

Ieșire : Determină dacă S este serializabil, și în caz afirmativ un orar

serial echivalent cu S.

Metoda : Crearea unui graf direct G (numit graf de precedență), ale cărui

noduri corespund tranzacțiilor. Pentru a determina arcele din G, fie S de forma a1; a2; ….; an, unde fiecare ai este o acțiune de forma

Tj : LOCK Am sau Tj : UNLOCK Am.

Tj indică tranzacția la care aparține pasul. Dacă ai este

Tj : UNLOCK Am

căutăm următoarea acțiune ap, ce urmează ai, care este de forma Ts :

LOCK Am. Dacă există, atunci desenăm un arc de la Tj la Ts. Intuitiv

acest arc înseamnă că în orice orar serial echivalent cu S, Tj trebuie să

preceadă Ts.

Dacă G are un ciclu, atunci S nu este serializabil. Dacă G nu are cicluri atunci găsim o ordine liniară pentru tranzacții astfel încât Ti precede Tj și oricând există un arc TiTj. Aceasta poate fi realizată întotdeauna de un proces cunoscut sub numele de sortare topologică, definit în continuare. Trebuie să existe câteva noduri Ti care nu conțin arce ce intră în ele, în caz contrar putem demonstra că G conține un ciclu. Listăm Ti și apoi eliminăm Ti din G. Apoi repetăm procesul pe graful obținut până când nu mai există nici un nod. Ordinea în care nodurile sunt listate este ordinea serială pentru tranzacții.

Fig. 5 Graful de precedență al tranzacțiilor.

EXEMPLUL 6. Considerăm orarul din Fig. 4. Graful G prezentat în Fig. 5 conține nodurile T1,T2 și T3. Pentru a găsi arcurile ne uităm la fiecare pas UNLOCK în Fig. 4. De exemplu pasul (4), T2 : UNLOCK B, este urmat de T1 : LOCK B; în acest caz blocajul apare la pasul următor. În continuare desenăm un arc T2T1. Un alt exemplu, acțiunea de la pasul (8), T2 : UNLOCK C, este urmată la pasul (11) de T3 : LOCK C, și nu intervine nici un pas care să-l blocheze pe C. În continuare desenăm un arc de la T2 la T3. Pasul (6) și pasul (7) implică plasarea unui arc T1T2. Deoarece există un ciclu, orarul din Fig. 4 nu este serializabil.

EXEMPLUL 7. Fig. 6 conține un orar pentru trei tranzacții iar Fig. 7 conține graful lor de precedență. Cum nu există nici un ciclu, orarul din Fig. 6 este serializabil, și din ALGORITMUL 1 reiese că ordinea serială este T1, T2, T3. Este interesant de observat că în ordinea serială T1 precede T3, cu toate că în Fig. 6 T1 nu începe până când nu termină T3.

Fig. 6. Un orar serializabil

Fig. 7. Graful de precedență pentru Fig. 6

TEOREMA 1 : ALGORITMUL 1 determină corect dacă un orar este serializabil.

Demonstrație : Presupunem că graful de precedență G nu are cicluri. Considerăm secvența de tranzacții Ti1, Ti2, …, Tit, care în orarul S blochează și deblochează itemul A în această ordine. Atunci în G există arcurile Ti1Ti2 ….Tit, deci tranzacțiile trebuie să apară în această ordine în orarul serial construit. Deoarece alte tranzacții nu blochează A, este ușor de verificat că valoarea lui A după executarea lui S este aceiași ca în cazul unui orar serial construit de ALGORITMUL 1. Deoarece aceasta este valabilă pentru orice item A, rezultă că S este echivalent cu orarul serial construit, deci S este serializabil.

Reciproc, presupunem că G are un ciclu Tj1Tj2….TjpTj1. Fie R un orar serial echivalent cu S, și presupunem că în R, Tj apare primul printre tranzacțiile din ciclu. Fie în G arcul Tjp-1Tjp (jp-1 = jt, dacă p = 1), datorită item-ului A. Atunci în R, deoarece Tjp apare înaintea lui Tjp-1, în formula finală funcția asociată unei perechi LOCK A – UNLOCK A din Tjp va fi aplicată înaintea funcției g asociată unei perechi LOCK A – UNLOCK A din Tjp-1. În S Tjp-1 precede oricum Tjp, deoarece există un arc Tjp-1Tjp. Prin urmare, în S, g este aplicată înaintea lui . Așadar valoarea finală a lui A este diferită în R și S, în sensul că cele două formule nu sunt identice, de aici rezultând că R și S nu sunt echivalente. Prin urmare S nu este echivalent cu nici un orar serial.

UN PROTOCOL CARE GARANTEAZĂ SERIALIZABILITATEA

Vom prezenta un protocol care are proprietatea că orice colecție de tranzacții care respectă acest protocol nu pot avea un orar neserializabil corect. Mai mult acest protocol este cel mai bun care poate fi formulat, într-un sens care va fi discutat mai târziu. Protocolul este simplu și cere ca în orice tranzacție toate blocările să preceadă toate deblocările . Tranzacțiile care respectă acest protocol se spune că sunt “în două faze”; prima fază este cea de blocare și a doua este cea de deblocare. De exemplu, în Fig. 3, T1 și T3 sunt în două faze, pe când T2 nu este.

TEOREMA 2. Dacă S este un orar al unor tranzacții în două faze atunci, S este

serializabil.

Demonstrație : Presupunem că S nu este serializabil. Atunci în baza Teoremei 1, graful de precedență G pentru S are un ciclu, Ti1Ti2… TipTi1. Atunci câteva blocaje de ale lui Ti2 urmează un deblocaj de al lui Ti1, câteva blocaje de ale lui Ti3 urmează un deblocaj de al lui Ti2, și așa mai departe. În final câteva blocaje de ale lui Ti1 urmează un deblocaj de al lui Tip. Prin urmare un blocaj de al lui Ti1 urmează un deblocaj de al lui Ti1, ceea ce contrazice ipoteza că Ti1 este în două faze.

Am menționat că protocolul în două faze este cel mai bun într-un anumit sens. Mai precis putem arăta că dacă T1 este o tranzacție oarecare care nu este în două faze, atunci există o alta tranzacție T2 cu care T1 ar putea rula într-un orar neserializabil. Presupunem că T1 nu este în două faze. Atunci există câțiva pași UNLOCK A de-ai lui T1 care preced un pas LOCK B. Fie T2 după cum urmează :

T2 : LOCK A; LOCKB; UNLOCK A; UNLOCK B.

Atunci se observă ușor că orarul din Fig. 8 nu este serializabil, deoarece tratarea lui A cere ca T1 să preceadă T2, în timp ce tratarea lui B cere ca T2 să preceadă T1.

Reținem că în figură sunt colecții particulare de tranzacții, nu toate fiind în două faze, dar care produc doar orare seriale. Cu toate că este normal să nu știm setul tuturor tranzacțiilor care pot fi executate concurent cu o tranzacție dată, suntem adeseori forțați să cerem ca toate tranzacțiile să fie în două faze.

Fig. 8 Un orar neserializabil.

UN MODEL CU BLOCAJE LA CITIRE ȘI SCRIERE

În Secțiunea 2 am presupus că de fiecare dată când o tranzacție blochează un item schimbă acel item. În practică, de multe ori o tranzacție are nevoie doar să obțină valoarea unui item nu și să schimbe această valoare. Dacă facem distincție între accesul “doar-citire” și cel “citire-scriere” putem dezvolta un model de tranzacții mult mai detaliat care ne va permite unele situații de concurență care nu erau premise în modelul din secțiunea precedentă. Vom distinge două tipuri de blocaje :

Blocaj-citire. O tranzacție T care dorește doar să citească un item A, execută RLOCK A, care previne orice altă tranzacție de a scrie o nouă valoare pentru A în timp ce T citește A. În orice caz un număr nelimitat de tranzacții pot să dețină un blocaj-citire asupra lui A în același timp.

Blocaj-scriere . O tranzacție care dorește să schimbe valoarea item-ului A, mai întâi obține un blocaj-scriere executând WLOCK A. Când o tranzacție deține un blocaj-scriere pe un item, nici o altă tranzacție nu poate să obțină un blocaj-citire sau un blocaj-scriere pe acel item.

Amândouă blocajele-, citire și scriere, sunt eliminate printr-o instrucțiune UNLOCK. Ca și în Secțiunea 2 vom presupune că nici o tranzacție nu încearcă să deblocheze un item asupra căruia nu are blocaje-, citire sau scriere, și nici o tranzacție nu încearcă să obțină un blocaj-citire asupra unui item pentru care deține deja un alt blocaj. Mai mult o tranzacție nu încearcă să obțină un blocaj-scriere pe un item pe care mai deține un asemenea blocaj, dar sub anumite circumstanțe un blocaj-scriere poate fi obținut pentru un item asupra căruia deține un blocaj-citire. Aceasta are sens deoarece un blocaj-scriere este mult mai restrictiv pentru comportarea unei tranzacții decât un blocaj-citire.

Două orare sunt echivalente dacă :

produc aceeași valoare pentru fiecare item, și

fiecare blocaj-citire aplicat unei tranzacții date apare în ambele orare atunci când item-ul blocat are aceeași valoare.

TEST DE SERIALIZABILITATE

Ca și în secțiunea precedentă, presupunem că de fiecare dată când un blocaj-scriere este aplicat unui item, o funcție unică asociată acestui blocaj operează asupra valorii acestui item. Oricum blocajele-citire nu schimbă valoarea itemului. Presupunem că avem un orar S în care un blocaj-scriere este aplicat lui A prin tranzacția T1, și fie funcția asociată acestui blocaj-scriere. După ce T1 deblochează A, fie T2 o tranzacție care urmează cu efectuarea unui blocaj-citire pe A, înaintea tranzacțiilor care vor să obțină un blocaj-scriere asupra lui A. Atunci cu siguranță T1 trebuie să preceadă T2 în orice orar serial echivalent cu S. Altfel, T2 citește o valoare a lui A în care nu este implicată funcția , și această valoare nu este identică cu o valoare care implică funcția . Similar, dacă T3 este următoarea tranzacție, după T1, pentru a bloca A de tipul blocaj-scriere, atunci T1 trebuie să preceadă T3.

Acum presupunem că T4 este o tranzacție care blochează A pentru citire, înainte ca T1 să blocheze pentru scriere. Dacă T1 apare înaintea lui T4 într-un orar serial, atunci T4 citește o valoare a lui A care implică , în timp ce în orarul S, valoarea citită de T4 nu implică . Așadar T4 trebuie să preceadă T1 într-un orar serial. Singura concluzie pe care o putem trage este că dacă în S două tranzacții efectuează blocaje-citire asupra aceluiași item A într-o ordine particulară , atunci tranzacțiile trebuie să apară în această ordine într-un orar serial. În realitate doar în sens invers este adevarat. Ordinea relativă a blocajelor pentru citire nu are nici un efect asupra valorilor produse de tranzacții care se execută concurent. Aceste observații ne sugerează că o abordare similară cu cea din Secțiunea 2 ne va permite să spunem când un orar este serializabil.

ALGORITMUL 2 : Test de serializabilitate pentru orare cu blocaje de

tip citire/scriere.

Intrare : Un orar S pentru un set de tranzacții T1,…,Tk.

Ieșire : Determină dacă S este serializabil, și dacă da, întoarce un orar serial

echivalent.

Metoda : Construim un graf de precedență G după cum urmează. Nodurile

sunt tranzacții ca mai înainte. Arcele sunt determinate de următoarele reguli :

Presupunând că în S tranzacția Ti blochează pentru citire un item A, iar tranzacția Tj este următoarea tranzacție (dacă există ) care blocheză pentru scriere A. Atunci plasăm un arc de la Ti la Tj.

Presupunând că în S, tranzacția Ti blochează pentru scriere A, iar Tj este următoarea tranzacție (dacă există ) care blochează pentru scriere A. Atunci desenăm un arc TiTj. În continuare fie Tm o tranzacție care blocheză pentru scriere A după ce Ti eliberează blocajul său de tip scriere, dar înainte ca Tj să blocheze pentru scriere A (dacă Tj nu există, atunci Tm este orice tranzacție care blocheză pentru citire A după ce Ti deblochează A). Atunci desenăm un arc TiTm.

Dacă G are un ciclu, atunci S nu este serializabil. Dacă G este aciclic atunci orice sortare topologică a lui G este o ordine serială pentru tranzacții.

EXEMPLUL 8. : Fig. 9 conține orarul a patru tranzacții, iar Fig. 10 conține graful de precedență al acestui orar. Primul UNLOCK este la pasul (3), unde T3 elimină blocajul pentru scriere de pe A. În continuarea pasului (3) sunt blocajele pentru citire pe A ale tranzacțiilor T1 și T2 (pașii 4 și 7) și blocajul pentru scriere al tranzacției T4 la pasul (12). Așadar T1, T2 și T4 trebuie să urmeze T3, și vom desena arcuri de la T3 către celelalte noduri. Reținem că nu este nici o greșeală ca ambele tranzacții T1 și T2 să dețină blocaje pentru citire asupra lui A după pasul (7). Oricum T4 nu poate bloca pentru scriere A până când T1 și T2 nu eliberează blocajele lor pentru citire. Ca un alt exemplu, T4 eliberează un blocaj de scriere de pe B la pasul (5), iar următorul blocaj de scriere pe B este al tranzacției T3, deci desenăm un arc de la T4 la T3. În acest caz avem un ciclu, deci orarul din Fig. 9 nu este serializabil. Setul complet de arce este desenat în Fig. 10.

Fig. 9 . Un orar.

TEOREMA 3 : ALGORITMUL 2 determină corect dacă orarul S este serializabil.

Demonstrație : Este simplu să demonstrăm, de fiecare dată când desenăm un arc de la Ti la Tj, că în orice orar serial echivalent Ti trebuie să preceadă Tj. Așadar dacă G are un ciclu, putem arăta, ca în Teorema 1, că un astfel de orar nu există. În sens invers, presupunem că G nu are cicluri. Atunci în baza Teoremei 1 rezultă că valoarea finală a fiecărui item din S este aceeași cu cea din orarul serial R, care este construit din sortarea topologică a lui G. Trebuie de asemenea să arătăm că blocajele pentru citire pe itemul A obțin aceeași valoare în S și R. Aceasta este ușor de demonstrat deoarece arcele din G garantează că blocajele pentru scriere pe A care preced un blocaj pentru citire dat trebuie să fie aceleași în R și în S și trebuie să apară în aceeași ordine.

Fig. 10 . Graful de precedență pentru Fig. 9.

PROTOCOLUL ÎN DOUĂ FAZE

Ca și modelul din secțiunea precedentă, protocolul în două faze, în care toate blocajele pentru citire și scriere preced toți pașii de deblocare, este suficient pentru a garanta serializabilitatea. De altfel, avem aceeași conversie parțială, că orice tranzacție în care există pași UNLOCK care preced un blocaj pentru scriere sau citire poate rula într-un mod neserializabil cu alte tranzacții.

UN MODEL „DOAR-CITIRE, DOAR-SCRIERE”

O presupunere subtilă cu consecințe profunde care a fost făcută în Secțiunea 2 și 3 este aceea că oricând o tranzacție scrie o nouă valoare pentru un item A, ea mai întâi citește valoarea lui A, și mult mai important, noua valoare a lui A depinde de valoarea veche a lui A. Această presupunere este construită pe baza definiției de “valoare” din secțiunile precedente. Un model mai realistic ar admite ca o tranzacție să citescă un set de item-uri și să scrie un set de item-uri , cu proprietatea că un item A poate să apară în unul din aceste seturi sau în ambele.

De exemplu, orice tranzacție care interoghează o bază de date, dar care nu o modifică are un set-scriere vid. În tranzacția :

READ A; READ B; C:= A+B; A:=A-1; WRITE C; WRITE A

setul-citire este {A, B}, iar setul-scriere este {A, C}.

ECHIVALENȚA ORARELOR

Când permitem item-uri doar-scriere, trebuie să revenim asupra noțiunii de orare echivalente. O diferență importantă este următoarea: presupunând, în modelul din Secțiunea 3, că tranzacția T1 a scris o valoare pentru A și mai târziu T2 a scris o valoare pentru A. Atunci am presupus că T2 blochează pentru scriere A după ce T1 a deblocat A, și prin urmare T2 a folosit valoarea lui A în calcularea unei valori noi, în timp ce s-a presupus că funcția asociată blocărilor-deblocărilor lui A de către T2 produce o valoare nouă distinctă a lui A pentru fiecare din vechile valori ale lui A. Ca urmare, atunci când avem de-a face cu serializabilitatea am acceptat că într-un orar serial T1 apare înaintea lui T2 , și că nici o tranzacție T care blochează pentru scriere A nu apare între T1 și T2.

În orice caz, dacă presupunem că T2 a scris valoarea sa pentru A, fără ca să citească A, atunci noua valoare a lui A este independentă de cea veche, ea depinde doar de valorile item-urilor care au fost realmente citite de T2 . Așadar, dacă între timp T1 și T2 scriu valorile lor pentru A, tranzacțiile necitind A, observăm că valoarea scrisă de T1 se pierde și nu are nici un efect asupra bazei de date. Ca o consecință, într-un orar serial, nu avem nevoie ca T1 să preceadă T2 (cel puțin atunci când ne interesează A). De fapt, singura restricție pentru T1, este că ea trebuie făcută la un moment dat când altă tranzacție T3 va scrie mai târziu A, și în timp ce T1 și T3 scriu A nici o altă tranzacție nu citește A.

Acum am putea formula o nouă definiție a serializabilității bazată pe conceptul că valorile scrise de o tranzacție sunt în funcție doar de valorile citite, și citirea de valori distincte produce scrierea de valori distincte. Aceste condiții sunt formulate informativ și fără o prea mare acuratețe după cum urmează. Dacă în orarul S tranzacția T2 citește valoarea unui item A, scris de T1 atunci :

T1 trebuie să preceadă T2 în orice orar serial echivalent cu S.

Dacă T3 este o tranzacție care scrie A, atunci în orice orar serial echivalent cu S T3 poate fie să preceadă T1, fie să urmeze T2, dar nu poate să apară între T1 și T2.

Este nevoie de două detalii pentru a crește acuratețea definiției de mai sus. Mai întâi, sunt “efectele de mărginire” care implică, citirea unui item înainte să fie scris de cel puțin o tranzacție sau scrierea unui item care nu va mai fi niciodată rescris. Aceste regului sunt cel mai bine respectate prin cererea existenței unei tranzacții inițiale T0 care scrie toate item-urile fără să le citească, și a unei tranzacții finale T, care citește toate item-urile fără să le scrie.

Al doilea detaliu este concentrat asupra tranzacțiilor T a căror ieșire este “invizibilă”, în sensul că valorile pe care T le scrie nu au nici un efect asupra valorilor citite de T. Reținem că acest efect poate să nu fie direct, acesta putând rezulta dintr-o tranzacție T’ care citește o valoare scrisa de T, altă tranzacție T’’ care citește o valoare scrisă de T’, și așa mai departe până când găsim în lanț o tranzacție care scrie o valoare citită de T. O tranzacție care nu are nici un efect asupra lui T o numim inutilă. A doua modificare asupra regulilor de mai sus este excluderea posibilităților ca T2 , din (1) și (2) de mai sus, să fie o tranzacție inutilă.

TEST PENTRU DEPISTAREA TRANZACȚIILOR INUTILE

Dat un orar S este ușor să spunem care tranzacții sunt inutile. Creem un graf ale cărui noduri sunt tranzacții, incluzând și tranzacția T despre care am presupus că există la sfârșitul lui S. Dacă T1 scrie o valoare citită de T2, desenăm un arc de la T1 la T2. Acum tranzacțiile inutile sunt exact acele tranzacții care nu au nici o cale spre T. Un exemplu al acestui algoritm urmează după discuția asupra testului de serializabilitate.

UN MODEL FORMAL

Să privim tranzacțiile ca în Secțiunea 3, adică, ca o serie de pași RLOCK A (blochează pentru citire item-ul A), WLOCK A (blochează pentru scriere item-ul A) și UNLOCK A. Ca mai înainte, presupunem că tranzacțiile nu deblochează un item asupra căruia nu dețin un blocaj (pentru scriere sau citire), și nu blochează un item pe care îl țin blocat deja, cu excepția că o tranzacție poate bloca pentru scriere un item asupra căruia deține un blocaj pentru citire sau invers. Singura diferență esențială dintre acest model și cel de mai înainte ține de semantică. Aici am presupus că atunci când o tranzacție blochează pentru scriere un item, nu citește valoarea item-ului (excepție doar dacă are și un blocaj pentru citire asupra item-ului), în timp ce mai înainte am folosit faptul că un blocaj pentru scriere include privilegii de citire și de fapt include obligația de a citi și de a folosi valoarea citită.

TEST DE SERIALIZABILITATE

Testul pe baza grafului de precedență simplă din secțiile anterioare nu se potrivește aici. Reținem că în modelul curent sunt două tipuri de constrângeri asupra unui potențial orar serial echivalent cu un orar S dat. Tipul I de constrângeri sunt de genul că dacă T2 citește o valoare a lui A scrisă de T1 în S, atunci T1 trebuie să preceadă T2 în orice orar serial. Acest tip de constrângere poate fi exprimat grafic printr-un arc de la T1 la T2. Tipul II de constrăngere este că orice T3 care scrie A trebuie să apară fie înaintea lui T1 fie după T2, și aceasta nu poate fi exprimată printr-un arc simplu. Rezultă că avem o pereche de arce T3T1 și T2T3 și se pune problema pe care trebuie să-l alegem. Orarul S este serializabil dacă și numai dacă după ce am făcut o alegere din fiecare pereche de arce rămânem cu un graf aciclic.

O colecție de noduri, arce și perechi de arce alternative a fost numită poligraf. Un poligraf este aciclic dacă prin alegerea uui arc din fiecare pereche rezultă un graf aciclic în sensul obișnuit. Testul de serializabilitate pentru modelul prezentat sub considerațiile făcute este construirea unui astfel de poligraf și să determinăm dacă este aciclic. Din nefericire, problema de a decide dacă un poligraf este aciclic, este o problemă foarte grea și a fost arătat de către Papadimitriou, Berstein și Rothnie că este NP-completă [1977].

ALGORITMUL 3 : Test de serializabilitate pentru tranzacții cu blocaje doar pentru

citire și doar pentr scriere.

Intrare : Un orar S pentru un set de tranzacții T1, T2, …Tk.

Ieșire : Determină dacă S este serializabil și în caz afirmativ întoarce

orarul serial echivalent.

Metoda :

Mărim S prin adăugarea la început a unei secvențe de pași în care o tranzacție imaginară T0 scrie fiecare item care apare în S, și prin adăugarea unor pași la sfârșit în care tranzacția imaginară T citește fiecare astfel de item.

Începem crearea unui poligraf P cu câte un nod pentru fiecare tranzacție, incluzând T0 și T. Temporar plasăm un arc de la Ti la Tj atunci când Tj citește un item A care în orarul S mărit, ultima dată a fost scris de Ti.

Descoperirea tranzacțiilor inutile. O tranzacție T este inutilă dacă nu exista nici o cale de la T la T.

Pentru fiecare tranzacție inutilă T, eliminăm toate arcele care intră în T.

Pentru fiecare arc rămas TiTj și pentru fiecare item A pentru care Tj citește valoarea lui A scrisă de Ti, consideram o altă tranzacție TT0 care de asemenea scrie A. Dacă Ti=T0 și Tj=T nu adăugăm nici un arc. Dacă Ti=T0, dar TjT adăugăm arcul TjT. Dacă Tj=T, dar TiT0 adăugăm arcul TTi. Dacă TiT0 și TjT atunci introducem perechea de arcuri (TTi, TjT).

Determinăm dacă poligraful P rezultat este aciclic. Pentru acest pas nu este nici o metodă mai bună decât una exhaustivă (costisitoare). Dacă sunt n perechi de arce încercăm toate cele 2n posibilități ale unui arc din fiecare pereche pentru a vedea dacă rezultatul este un graf aciclic. Dacă P este aciclic, atunci fie G un graf acicilc format din P prin alegerea unui arc din fiecare pereche. Atunci orice sortare topologică a lui G, cu T0 și T eliminate, reprezintă un orar serial echivalent cu S. Dacă P nu este aciclic atunci nu există nici un orar serial echivalent cu S.

EXEMPLUL 9 : Considerăm orarul din Fig. 11. Arcele construite prin pasul (2) al ALGORITMULUI 3 sunt reprezentate în Fig. 12; pentru claritate arcele sunt etichetate cu item-ul sau item-urile care justifică prezența lor. Pentru a înțelege cum a fost creată Fig. 12 este folositoare observația că orarul din Fig. 11 este legal, în sensul că două tranzacții nu dețin blocaje pentru scriere sau simultan pentru citire și scriere. Așadar, putem presupune că toate citirile și scrierile apar la timpul când este obținut blocajul, și putem ignora pașii UNLOCK.

Să considerăm în schimb fiecare pas blocare pentru citire. Blocările pentru citire asupra lui A din pașii (1) și (2) citesc valoarea “scrisă” de tranzacția imaginară T0. Așadar desenăm arce de la T0 la T1 și T2. La pasul (5) T3 citește valoare lui C scrisă de T1 la pasul (3), deci avem arcul T1T3. La pasul (8), T4 citește ceea ce T1 scrie la pasul (6), deci avem arcul T1T4, și așa mai departe. În final T “citește” A, B, C și D, ale căror valori au fost scrise ultima dată de T4, T3, T1 și respectiv T2, aceasta explicând cele trei arce care intră în T.

Fig. 11. Un orar.

Acum căutăm în Fig. 12 tranzacțiile inutile, acele tranzacții care nu au cale către T; T3 fiind singura astfel de tranzacție. În continuare vom elimina arcul T1T3 din Fig. 12.

În pasul (5) din ALGORITMUL 3, considerăm arcele sau perechile de arce necesare pentru a preveni intersecția unei operații de scriere cu alta. Un item ca C sau D care este scris doar de tranzacții care nu sunt fictive nu apare în pasul (5). Oricum, A este scris și de T3 și de T4 ca și de tranzacția fictivă T0. Valoarea scrisa de T3 nu este citită de o altă tranzacție, deci T4 nu este nevoit să apară într-o poziție particulară relativă la T3. Valoarea scrisă de T4 este “citită” de T. Așadar, cum T3 nu poate să apară după T, trebuie să apară înainte de T4. În acest caz, nu este nevoie de o pereche de arce; pur și simplu adăugăm la P arcul T3T4. Valoarea lui A scrisă de T0 este citită de T1 și T2. Cum T3 și T4 nu pot să apară înainte de T0, plasăm arce de la T1 și T2 către T3 și T4; din nou nefiind nevoie de perechi de arce.

Fig. 12 Primul pas în construcția unui poligraf

Item-ul B este scris de T1 și T4. Valoarea lui B scrisă de T4 este citită doar de T, deci avem nevoie de arcul T1T4. Valoarea lui B scrisă de T1 este citită de T2 și T4 . Scrierea lui B de către T4 nu se poate interfera cu citirea lui B de către T4. Așadar nu este nevoie de nici o cerință de felul “T4 precede T1 sau urmează T4”. Oricum T4 nu trebuie să se interpună între T1 și T2, așa că adăugăm perechea de arcuri (T4 T1, T2 T4 ). Poligraful rezultat este reprezentat în Fig. 13, cu o pereche de arce desenată cu linie întreruptă. Observăm că arcul T1 T3 eliminat în pasul (4), revine în pasul (5).

Dacă alegem arcul T4 T1 din pereche, obținem un ciclu. însă, alegând T2T4 obținem un graf aciclic, din care putem lua ordinea serială T1, T2, T3, T4. Prin urmare orarul din Fig. 11 este serializabil.

Fig. 13 Poligraful final.

TEOREMA 4 : ALGORITMUL 3 determină corect dacă un orar este serializabil.

Demonstrație : Vom da o descriere scurtă a demonstrației. Presupunem mai întâi că poligraful rezultat este aciclic. Aceasta înseamnă că există posibilitatea de a alege un arc din fiecare pereche rezultând un graf aciclic G. Construcția lui P în ALGORITMUL 3, asigură faptul că fiecare tranzacție care nu este inutilă, incluzând T, citește aceeași copie a fiecărui item în S cum o face în orarul serial rezultat dintr-o sortare topologică a lui G. Așadar valorile corespunzătoare produse pentru fiecare item sunt aceleași în ambele orare.

Reciproc, presupunem că există un orar S’ echivalent cu S. Atunci prin raționamentul folosit în Teorema 1, dacă TiTj este un arc oarecare introdus în pasul (2) și neeliminat în pasul (4), Ti trebuie să preceadă Tj în S’. Presupunem că perechea de arcuri (TnTi, TjTn) este introdusă în pasul (5). Atunci Tn nu poate să apară între Ti și Tj în S’. Alegem arcul TnTi din pereche dacă Tn precede Ti în S’, altfel alegem TjTn. Ordinea liniară implicată de S’ va fi consistentă cu această alegere din perechile de arce. Similar, un singur arc adăugat în pasul (5) trebuie să fie consistent cu această ordine liniară, deci avem o cale de construcție, bazată pe S’, a unui graf aciclic din poligraful P.

PROTOCOLUL ÎN DOUĂ FAZE, DIN NOU

Ca și modelele precedente, un protocol în două faze este de succes în garantarea serializabilității oricărui orar legal. Pentru a vedea de ce, presupunem că S este un orar legal de tranzacții care respectă protocolul în două faze. Presupunem că (T3 T1, T2T3) este o pereche de arce în poligraful P. Atunci există un item A pentru care T2 citește copia lui A scrisă de T1. Dacă în S, T3 deblochează A înainte ca T1 să blocheze pentru citire A, atunci selectăm T3 T1 din pereche. Dacă T3 blochează A pentru scriere după ce T2 deblocheză A selectăm T2T3. Deoarece perechile au fost plasate în P după ALGORITMUL 5 alte posibilități nu mai există.

Avem acum un graf G construit din P. Presupunem că G are un ciclu T1T2 …TnT1. Desigur nici una din tranzacțiile fictive nu pot face parte dintr-un ciclu. Examinarea ALGORITMULUI 5 și a regulilor de mai sus pentru construirea lui G din P indică faptul că pentru fiecare arc TiTj ( cu Tn+1=T1) din ciclu, există un item Ai pentru care în S, Ti deblocheză Ai înainte ca Ti+1 să blocheze Ai. După protocolul în două faze, Ti+1 trebuie să deblocheze Ai+1 după ce blochează Ai. Așadar T1 deblocheză A1 înainte ca Ti+1 să blocheze An. Dar Tn+1 este T1 și protocolul în două faze interzice ca T1 să deblocheze A1 înainte de blocarea lui An de către T1. Am demonstrat așadar următoarea teoremă :

Teorema 5 : În modelul din această secțiune, dacă tranzacțiile respectă protocolul în două faze, atunci orice orar legal este serializabil.

CONCURENȚA PENTRU STRUCTURILE IERARHICE DE ITEM-URI

Sunt multe cazuri în care un set de item-uri accesate de o tranzacție poate fi văzut în mod natural ca un arbore sau ca o pădure. Câteva exemple sunt următoarele :

Item-urile sunt noduri ale unui B-arbore.

Sunt definite item-urile de dimensiuni diferite, cu item-uri mici înglobate în cele cu item-uri mari. De exemplu, o bază de date relațională poate avea item-urile pe patru nivele :

întreaga bază de date,

fiecare relație,

fiecare bloc în care este stocat fișierul corespunzător unei relații, și

fiecare tuplu.

Sunt două politici diferite care ar putea fi urmate atunci când item-urile sunt blocate. Prima, un blocaj asupra unui item poate implica blocarea tuturor item-urilor descendente. Această tactică economisește timp deoarece blocarea item-urilor mici poate fi evitată. De exemplu, în (3) de mai sus, o tranzacție care trebuie să citească o relație întreagă poate bloca relația ca un întreg, decât blocarea fiecărui item în parte. A două tactică este blocarea unui item fără nici o implicație asupra blocării descendenților săi. De exemplu dacă inspectăm un B-arbore, vom citi un nod și selectăm unul din fii săi pentru a-l citi în continuare. Nu este nevoie să blocăm toți descendenții de vreme ce citim doar un singur nod. Reiese că un protocol acceptabil pentru politica de blocare individuală a item-urilor este mai ușor de explicat decât un protocol pentru politica de blocare a subarborilor, deci vom considera blocarea individuală a item-urilor mai întâi.

UN PROTOCOL SIMPLU PENTRU ARBORII DE ITEM-URI

Revenim asupra modelului din Secțiunea 2 folosind doar operațiile LOCK și UNLOCK. Presupunem că blocarea unui item (nod într-un arbore) nu blochează automat nici un descendent. Ca și în Secțiunea 2 doar o tranzacție poate bloca un item la un moment dat. Spunem că o tranzacție respectă protocolul arbore, cu excepția primului item blocat (care nu este necesar să fie rădăcina), dacă nici un item nu poate fi blocat decât dacă deține un blocaj curent asupra părintelui său.

Observăm că o tranzacție care respectă protocolul arbore nu este necesar să fie în două faze. De exemplu, ea poate bloca item-ul A, apoi blochează fiul B, deblochează A și blocheză un fiu C a lui B. Această situație este chiar realistică, adică în cazul în care o tranziție realizează o operație de inserție într-un B-arbore. Dacă B este un nod într-un B-arbore care conține și un alt pointer, atunci știm că restructurarea arborelui după inserție poate implica părintele lui B. Așadar după examinarea lui B putem debloca părintele A, astfel permiterea actualizărilor concurente pe B-arbore implică descendenții lui A care nu sunt descendenții lui B.

EXEMPLUL 10 : Fig. 14 reprezintă un arbore de item-uri și Fig. 15 este un orar pentru trei tranzacții T1,T2 și T3 care respectă protocolul arbore. Se observă că T1 nu este în două faze deoarece blochează C după deblocarea lui B.

Cu toate că nu vom da o demonstrație aici (a se vedea Silberschatz și Kedem [1978]), toate orarele legale de tranziții care respectă protocolul arbore sunt serializabile. Algoritmul pentru construirea unei ordini seriale a tranzițiilor începe prin crearea unui nod pentru fiecare tranziție. Presupunem că Ti și Tj blochează același item (la timpi diferiți, desigur). Fie FIRST (T) un item care este blocat pentru prima dată de tranzacția T. Dacă FIRST(Ti) și FIRST(Tj) sunt independenți (nici unul nefiind descendentul celuilalt), atunci protocolul arbore ne asigură faptul că Ti și Tj nu blochează un nod în comun și nu este nevoie să desenăm un arc între ele. Presupunem în continuare, fără să pierdem din generalitate, că FIRST (Ti) este un strămoș al lui FIRST(Tj). Dacă Ti blochează FIRST(Ti) înaintea lui Tj, atunci desenăm arcul TiTj. Altfel desenăm arcul TjTj.

Fig. 14 . Ierarhia item-urilor.

Se poate arăta că graful rezultat nu are cicluri și orice sortare topologică a acestui graf este o ordine serială a tranzacțiilor. Ideea pe care se bazează demonstrația este că, tot timpul, fiecare tranzacție are o frontieră a celor mai de jos noduri din arbore asupra cărora deține blocaje. Protocolul arbore garantează că aceste frontiere nu se intersectează. Așadar, dacă frontiera lui Ti apare mai sus decât frontiera lui Tj, trebuie să ramână în acest fel, și fiecare item blocat de Ti și de Tj va fi blocat de Ti mai întâi.

Fig. 15. Un orar al unor tranzacții care respectă protocolul arbore.

EXEMPLUL 11 : Vom reconsidera orarul din Fig. 15.

FIRST(T1) = A, FIRST(T2) = B și FIRST(T3) = E.

T1 și T2 blochează fiecare B, dar T1 îl blochează mai întâi, deci avem arcul T1T2. De asemenea T2 și T3 blochează fiecare E, dar T3 precede T2 în această ordine. Așadar avem arcul T3T2. Graful de precedență în acest caz este reprezentat în Fig. 16, din care reiese că sunt două orare seriale posibile : T1, T3, T2 și T3, T1, T2.

Fig. 16. Graful de precedență pentru Fig. 15.

UN PROTOCOL CARE PERMITE BLOCAREA PE SUBARBORI

Este convenabil, atunci când ierarhia de item-uri include item-uri care sunt subseturi ale altor item-uri, să permitem ca blocarea unui item să implice blocarea tuturor descendenților săi. De exemplu, dacă o tranzacție trebuie să blocheze majoritatea sau toate tuplele unei relații, poate la fel de bine să blocheze însăși relația. Cu riscul posibil de a exclude câteva operații concurente din relație, sistemul va lucra mai puțin la blocarea și deblocarea item-urilor dacă vom bloca relația ca un întreg.

Oricum, blocări la întâmplare pot rezulta în orare ilegale, unde două tranzacții dețin efectiv un blocaj pe un același item în același timp. De exemplu, presupunem că tranzacția T1 blochează E (și prin urmare, cu noile presupuneri și F și G) în Fig. 14. Apoi, T2 blochează B, și prin urmare obținem un blocaj cu conflict asupra lui E, F și G. Pentru a evita acest conflict, a fost inventat un protocol în care o tranzacție poate plasa un blocaj asupra unui item doar dacă mai întâi “avertizează” toți strămoșii săi. Un avertisment pentru item-ul A previne orice altă tranzacție de a bloca A, dar nu o previne de a plasa de asemenea un avertisment pe A sau de a bloca câțiva descendenți ai lui A care nu au un avertisment plasat asupra lor.

Aici vom considera că tranzacțiile sunt alcătuite din operațiile :

LOCK, care blochează un item și toți descendenții săi. Orice două tranzacții nu pot deține un blocaj asupra unui item în același timp.

WARN, care plasează un “avertisment” asupra unui item. Nici o altă tranzacție nu poate bloca un item asupra căruia altă tranzacție are plasat un “avertisment”.

UNLOCK, care elimină fie un blocaj, fie un avertisment sau ambele de pe un item.

O tranzacție respectă protocolul de avertizare pe o ierarhie de item-uri dacă :

Începe prin plasarea unui blocaj sau avertisment pe rădăcină.

Nu plasează un blocaj sau un avertisment asupra unui item decât dacă deține un avertisment asupra părintelui sau.

Nu elimină un blocaj sau un avertisment decât dacă nu mai deține nici un blocaj sau avertisment asupra fiilor.

Se supune protocolului în două faze, în sensul că toate deblocările urmează toate avertismentele și blocările.

EXEMPLUL 12 : Fig 17 reprezintă o ierarhie și Fig. 18 reprezintă un orar pentru trei tranzacții care se supun protocolului de avertizare. Observăm, de exemplu că la pasul (4) T1 plasează un avertisment pe B. În continuare T3 nu poate bloca B până când T1 nu deblochează avertismentul pe B la pasul (10). Oricum, la pașii (1) – (3) toate cele trei tranzacții plasează avertismente pe A, ceea ce este legal.

Blocarea lui C de către T2 la pasul (5) implică bloacrea lui C, F și G. Presupunem că unul sau toate dintre aceste item-uri sunt schimbate de T2 înainte ca blocajul să fie eliminat la pasul (7).

Fig. 17. O ierarhie.

TEOREMA 6 : Orarele care se supun protocolului de avertizare sunt serializabile.

Demonstrație : Punctele (1) – (3) din protocolul de avertizare garantează că nici o tranzacție nu poate plasa un blocaj pe un item decât dacă deține avertismente pe toți strămoșii lui. Rezultă că niciodată două tranzacții nu pot ține blocaje pe doi strămoși ai aceluiași item. Putem arăta acum că un orar care respectă protocolul de avertizare este echivalent cu un orar care folosește modelul din Secțiunea 2, în care toate item-urile sunt blocate explicit (nu implicit, prin blocarea unui strămoș). Fiind dat un orar S care satisface protocolul de avertizare, construim un orar S’ în modelul din Secțiunea 2, după cum urmează :

Eliminăm toți pașii de avertizare și pașii corespondenți de deblocare.

Înlocuim toate blocajele prin blocaje asupra unui item și asupra tuturor descendenților săi. Facem același lucru pentru deblocările corespunzătoare.

Orarul rezultat S’ este legal în baza punctelor (1) – (3) din protocolul de avertizare, și tranzacțiile sale sunt în două faze, în baza punctului (4) din protocolul de avertizare.

Fig. 18. Orarul unor tranzacții care se supun protocolului de avertizare.

PROTECȚIA ÎMPOTRIVA DISTRUGERILOR

Până acum am presupus, în mod fericit, că fiecare tranzacție rulează până la finalul ei teoretic. În practică, se poate întâmpla ca mai multe lucruri să prevină o tranzacție de la terminarea ei cu succes.

Sistemul poate cădea dintr-o varietate de cauze hardware sau software. În acest caz, toate tranzacțiile active sunt împiedicate de la completare și este chiar posibil ca un număr de tranzacții complete să fie “anulate”, deoarece ele citesc valori scrise de tranzacții care nu au fost terminate încă. Prăbușirile de sistem cauzează probleme serioase, deoarece noi nu trebuie să găsim doar un set de tranzacții pentru “anulare” care ne vor duce înapoi către o stare consistentă ci trebuie să fim siguri și de existența unor căi de a reconstrui acea stare.

O singură tranzacție poate fi forțată să se oprească înainte de terminare dintr-o varietate de motive. Dacă detecția deadlock-urilor este făcută de sistem, o tranzacție poate fi găsită ca fiind cauza parțială a unui deadlock și selectată pentru anulare de către sistem. O excepție într-o tranzacție, de exemplu o împărțire la zero, poate cauza întreruperea și anularea tranzacției. În mod similar, un utilizator poate cauza o întrerupere la terminalul lui pentru a anula o tranzacție în mod expres.

COPIILE DE SIGURANȚĂ

Ar trebui să fie evident că nu putem avea încredere în păstrarea nedefinită a datelor într-o bază de date. Nu putem presupune că datele din regiștrii mașinii sau din starea solidă din memorie pot supraviețui unei fluctuații de curent, de exemplu. Componentele magnetice precum ar fi casetele, dischetele sau alte suporturi magnetice de stocare a memoriei vor fi de obicei păstrate chiar dacă mașina trebuie să fie oprită, dar chiar și așa datele sunt vulnerabile la problemele fizice cum ar fi distrugerea porțiunii de boot a unei dischete. În plus, datele nu sunt în siguranță totală deoarece ar putea fi șterse de erorile software ale sistemului.

Din aceste motive, este esențial ca, copiile de siguranță ale bazelor de date să fie făcute periodic, cel puțin o dată pe zi dacă este posibil, deasemenea și bazele de date enorme, pentru care procesul de copiere poate dura ore, trebuie să fie copiate, mai puțin frecvent însă. Copia, odată făcută pe un disc, trebuie înlăturată din vecinătatea calculatorului (în caz de incendiu, de exemplu), și ținută într-un loc sigur. Pentru siguranța sporită, mai multe din cele mai recente copii pot fi ținute în locuri diferite.

Când facem o copie este important ca datele copiate să reprezinte o stare consistentă. Așadar, utilitatea rutinei de copiere trebuie ea însăși să fie o tranzacție care blochează pentru citire toate item-urile din baza de date.

JURNALUL

Trebuie să fim pregătiți, de asemenea, să refacem baza de date la o stare consistentă care reflectă situația după ce un număr, poate un număr foarte mare, de tranzacții au fost îndeplinite urmând crearea ultimei copii de siguranță. Din acest motiv, trebuie să salvăm într-un loc relativ sigur, de exemplu pe dischete, o istorie , numită jurnal sau log, a tuturor schimbărilor făcute asupra bazei de date de când a fost făcută ultima copie de siguranță. În cel mai general caz intrările din jurnal sunt alcătuite din :

Un identificator unic al tranzacției care a făcut modificarea.

Vechea valoare a item-ului, și

Noua valoare a item-ului.

Ne așteptăm de asemenea ca jurnalul să înregistreze chei în funcție de timp, în desfășurarea unei tranzacții, cum ar fi începutul tranzacției, sfârșitul tranzacției și ceea ce vom numi mai târziu “ punctul de comitere”.

Necesitatea vechilor și noilor valori va deveni evidentă când vom considera că nu va fi necesar doar refacerea tranzacțiilor dar și anularea lor, ceea ce înseamnă să ștergem complet efectul anumitor tranzacții. Dacă item-urile sunt mari, de exemplu dacă sunt relații, este mai înțelept să reprezentăm doar modificările, decât să listăm complet vechile și noile valori. De exemplu, putem lista tuplele inserate și cele șterse și să dăm valorile vechi și cele noi pentru tuplele modificate.

TRANZACȚII COMISE

Când avem de-a face cu tranzacții care ar trebui refăcute sau anulate, ne este de ajutor să gândim în termenii de tranzacții “comise” sau “necomise”. Există un punct în timpul execuției oricărei tranzacții, în care privim tranzacția ca fiind completă. Toate calculele făcute de tranzacție în zona sa de lucru trebuie terminate și o copie a rezultatelor tranzacției trebuie scrisă într-un loc sigur, de presupus în jurnal. În acest moment putem privi tranzacția ca fiind comisă, dacă o cădere de sistem apare pe urmă, efectele tranzacției vor supraviețui căderii, cu toate că valorile produse de tranzacție s-ar putea să nu apară încă în baza de date. Acțiunea de comitere a tranzacțiilor poate fi ea însăși scrisă în jurnal, pentru că dacă trebuie să recuperăm dintr-o cădere a sistemului examinând jurnalul să știm care tranzacții sunt comise. Vom defini politica de comitere în două faze** după cum urmează :

O tranzacție nu poate să scrie în baza de date până când nu este comisă.

O tranzacție nu se poate comite până când nu a înregistrat toate modificările asupra item-urilor în jurnal.

Observăm că prima fază este scrierea datelor în jurnal și faza a două este scrierea acelorași date în baza de date.

Dacă în plus, tranzacțiile urmează protocolul de blocare în două faze și deblocările apar după comiteri, atunci vom ști că nici o tranzacție nu poate citi din baza de date o valoare scrisă de o tranzacție necomisă. În cazul unei prăbușiri a sistemului, este posibilă atunci examinarea jurnalului și să refacem toate tranzacțiile comise care nu au avut posibilitatea de a scrie valorile lor în baza de date. Dacă prăbușirea este de natură să distrugă datele din baza de date, va trebui să refacem toate tranzacțiile comise de la momentul în care ultima copie de siguranță a fost făcută, care este în general mai mare consumatoare de timp. Nu este necesar să anulăm nici o tranzacție care nu și-a atins punctul de comitere înainte de prăbușirea sistemului, deoarece acestea nu au nici un efect asupra bazei de date. Ar fi o idee bună afișarea unui mesaj utilizatorului, care să-l avertizeze că tranzacția sa nu a fost îndeplinită. Pentru a fi în stare să facem acest lucru după o prăbușire sunt necesare rutine care să intoducă în jurnal faptul că o tranzacție a început. Reținem că o prăbușire poate cauza ca blocajele să rămână asupra item-urilor, fie dintr-o tranzacție comisă fie din una necomisă, și acestea trebuie înlăturate de rutina de recuperare.

EȘUAREA TRANZACȚIILOR INDIVIDUALE

Mai puțin serioasă decât o prabușire de sistem este eșuarea unei singure tranzacții, când, de exemplu, poate cauza un deadlock sau este întreruptă dintr-un anumit motiv. Dacă urmăm politica de comitere în două faze, vom ști că nu are nici un efect asupra bazei de date, prevăzând că nici o întrerupere a unei tranzacții nu poate să apară după comitere. Dacă urmăm protocolul în două faze, atunci nici un blocaj sau calcul nu poate să apară după comitere, deci nu este posibil ca un deadlock să fie creat după comitere, sau ca o eroare aritmetică să cauzeze o întrerupere. Așadar eșuarea tranzacțiilor nu lasă nici o urma în baza de date. O informație care să indice faptul că o tranzacție a fost anulată ar trebui plasată în jurnal, astfel încât dacă o restartare survine după o prăbușire a sistemului, să știm să ignorăm orice intrare din jurnal pentru acea tranzacție.

TRANZACȚII CARE NU SE SUPUN POLITICII DE COMITERE ÎN DOUĂ FAZE

Să considerăm pe scurt ce se întamplă dacă tranzacțiilor nu li se cere ca înainte de a scrie în baza de date să-și atingă punctul de comitere. Prin slăbirea acestei cerințe, putem permite tranzacțiilor să deblocheze item-urile mai devreme, și prin urmare permitem altor tranzacții să se execute concurent în loc să aștepte. Oricum, această potențială incrementare a concurenței este plătită prin faptul că face recuperarea, după o prăbușire, mai dificilă, după cum vom vedea.

Vom presupune că fiecare item are modificările făcute introduse în jurnal înainte ca baza de date însăși să fie modificată și vom presupune că tranzacțiile se supun protocolului în două faze în ceea ce privește blocările. De asemenea presupunem că o tranzacție nu se comite până când nu a terminat de scris în jurnal ori de câte ori item-urile se modifică. Sub noile noastre presupuneri nu este imposibil să recuperăm din prăbușirile sistemului sau eșuarea individuală a tranzacților, dar devine mai dificil din două motive :

Pentru o tranzacție care nu este comisă, când apare o prăbușire trebuie ca modificările făcute de ea în baza de date să fie anulate.

O tranzacție care citește o valoare scrisă de o altă tranzacție care trebuie anulată, trebuie ea însăși anulată. Acest efect se poate propaga la infinit.

EXEMPLUL 13 : Considerăm cele două tranzacții din Fig. 19. În principiu aceste tranzacții urmează modelul din Secțiunea 2, cu toate acestea pentru a face clare anumite detalii de sincronizare, am arătat în mod explicit citirile – scrierile comise și operațiile aritmetice făcute de fiecare tranzacție în zona ei de lucru. Se presupune că pașii WRITE scriu vechile și noile valori în jurnal și apoi în baza de date. Presupunem că după pasul (14) este o cădere de sistem. De vreme ce T1 este singura tranzacție activă, nu contează dacă a fost o căderea de sistem sau o eșuare a lui T1, spunem aceasta deoarece o împărțire la 0 apare în pasul (14).

Trebuie să anulăm T1 deoarece este necomisă. De vreme ce deține un blocaj asupra lui B, acest blocaj trebuie înlăturat. Apoi trebuie să refacem valoarea precedentă a lui A la pasul (1). Trebuie de asemenea să anulăm T2, chiar dacă este comisă, și în fapt completă. Dacă altă tranzacție T3 a citit A între pașii (13) și (14), atunci T3 va trebui refăcută de asemenea , chiar dacă T3 a fost completă, și așa mai departe.

Fig. 19. Un orar.

Pentru a anula tranzacțiile vom considera fiecare item C scris de una sau mai multe tranzacții vizate pentru anulare. Examinăm jurnalul pentru a găsi cea mai apropiată scriere a lui C de una din tranzacțiile anulate. Aceste intrări din jurnal vor avea vechea valoare a lui C care poate fi plasată în baza de date. Reținem că de vreme ce am asumat că toate tranzacțiile sunt în două faze, și că folosim modelul din Secțiunea 2, nu este posibil ca o tranzacție T, care nu trebuie să fie refăcută, să fi scris o valoare pentru C mai târziu decât cea mai apropiată tranzacție anulată care a scris C.

În cazul exemplului nostru din Fig. 19, doar A a fost scris de tranzacțiile T1 și T2 anterior căderii. Găsim că cea mai apropiată scriere a lui A de una din aceste tranzacții a fost făcută de T1 la pasul (4). Intrarea din jurnal pentru pasul (4) va include vechea valoare a lui A, valoare citită la pasul (2). Înlocuirea lui A cu această valoare anulează toate efectele lui T1 și T2 asupra bazei de date.

Cineva poate presupune că având anulate T1 și T2 în EXEMPLUL 13, este posibil acum să refacem T2, deoarece a fost comisă, prin simpla examinare a jurnalului, mai degrabă decât rularea ei din nou. Ceea ce nu este cazul, deoarece T2 citește valoarea lui A scrisă în baza de date de T1, iar această valoare nu mai există. A retrage această valoare a lui A din jurnal, fără să rulăm din nou T1, poate conduce la o inconsistență în baza de date.

PARTAJAREA DATELOR ÎN REȚEA CU AJUTORUL PROGRAMULUI VISUAL FOXPRO

Oricine a lucrat cu aplicații de baze de date în rețea pentru o perioada mai lungă s-a lovit inevitabil de una dintre principalele probleme ale procesării datelor : cum trebuie tratate conflictele care survin atunci când doi utilizatori încearcă să actualizeze simultan aceleași date. În multe aplicații, cel care salvează ultimul modificările câștigă jocul actualizării. Datele acestei persoane reprezintă modificările finale și definitive efectuate asupra bazei de date, în detrimentul oricăror actualizări anterioare care sfârșesc la coșul de gunoi.

Sistemul Visual FoxPro al firmei Microsoft protejează într-o oarecare măsură acest tip de activitate permițând utilizatorului să invoce o metodă (fie automată, fie explicită) de blocare a înregistrării sau a tabelului înaintea actualizării datelor. Atunci când tabelul și înregistrarea sau înregistrările aferente sunt accesate, blocarea împiedică orice alt utilizator să acceseze zona respectivă până în momentul în care primul utilizator nu a terminat operațiile de editare și nu a părasit în bune condiții zona.

În locul utilizării exclusive a datelor de către un singur utilizator, informațiile pot fi partajate de un departament sau de un grup de utilizatori. Soluția uzuală este de a elimina datele de pe unitatea de disc locală și a le instala într-un calculator server de fișiere la care au acces toți cei care au nevoie de fișierele respective. O alternativă o reprezintă partajarea hard-discului local. Prima abordare este în prezent cea mai uzuală, în schimb, rețelele de tip “peer” devin din ce în ce mai populare.

TIPURI DE BLOCAJE

Atunci când dezvoltăm aplicații multiutilizator, avem de-a face cu două tipuri de blocaje : de fișier și de înregistrare. Această secțiune tratează deosebirile între aceste două tipuri de blocaje și propune o serie de abordări pentru implementarea lor în aplicații. De asemenea, sunt tratate diferențele între blocajele automate și cele manuale.

BLOCAREA ÎNREGISTRĂRILOR SAU A FIȘIERELOR ?

În aplicațiile în care trebuie asigurat accesul mai multor utilizatori, trebuie avut în vedere ca accesul la date să fie permis numai utilizatorilor care îl solicită. Un blocaj de înregistrare, dacă este corect aplicat, împiedică accesul în mod scriere al altor utilizatori în afară celui care a solicitat blocarea. Pe de altă parte, un blocaj de fișier blochează tabelul la nivel fizic, împiedicându-i pe ceilalți utilizatori să scrie date în tabel atât timp cât edităm una sau mai multe înregistrări ale tabelului. Blocarea înregistrărilor și a fișierelor nu împiedică pe ceilalți utilizatori să citească datele din înregistrările sau fișierele blocate, ci pur și simplu interzice scrierea datelor. O dată activată blocarea fișierului, accesul la fișierul respectiv și la înregistrările acestuia este interzis până în momentul în care utilizatorul originar eliberează fișierul din starea blocată.

În majoritatea cazurilor, se va opta probabil pentru utilizarea blocajelor de înregistrări în aplicații, întrucât acestea interzic accesul numai la înregistrările individuale, nu la întregul tabel.

BLOCĂRI AUTOMATE SAU MANUALE ?

Dacă în ceea ce privește siguranța datelor există două posibilități, blocarea fișierelor și a înregistrărilor, în ceea ce privește protejarea datelor în raport cu operațiile de manipulare a fișierelor există două metode de blocare a datelor : automată și manuală.

În funcție de necesități, blocarea fișierelor poate avea loc fie automat, fie prin intermediul unei metode manuale. FoxPro va încerca să blocheze automat înregistrările atunci când sunt utilizate anumite comenzi de actualizare a datelor (vezi Tabelul 1). De asemenea, FoxPro dă posibilitatea de a bloca manual înregistrările folosind un set de funcții de blocare, care vor fi tratate mai târziu. Tabelul care urmează ilustrează multe dintre comenzile care conduc la blocarea automată a înregistrărilor și a fișierelor.

În măsura posibilităților, este preferabil să folosim comenzi care blochează înregistrări individuale în locul celor care încearcă să blocheze întregul tabel. Această afirmație se bazează pe două aspecte : supraîncărcarea rețelei cauzată de blocarea unui fișier și riscul ca fișierul să fi fost deja blocat de un alt utilizator. În Visual FoxPro, un fișier poate fi blocat numai dacă nu conține înregistrări blocate. În aplicații multiutilizator de orice dimensiuni, îndeplinirea acestei condiții poate dura destul de mult.

În exemplul următor, un utilizator care dorește să blocheze întregul tabel GERMFASK folosește comanda APPEND FROM, care încearcă să blocheze tabelul în timp ce adaugă înregistrări din alt fișier.

SET EXCLUSIVE OFF

USE GERMFASK

APPEND FROM HOUGHTON FOR STATUS = “CLOSED”

În momentul finalizării operației de adăugare, comanda APPEND elimină toate blocajele pe care le-a creat.

Observație : Orice comandă care crează în mod automat blocaje eliberează toate

blocajele create în momentul în care este finalizată.

Tabelul 1

Funcțiile de blocare manuală testează starea de blocare a unei înregistrării sau a unui tabel. Dacă în urma testării se constată că înregistrarea nu este blocată, înregistrarea (sau tabelul) este blocată și utilizatorul poate începe să utilizeze fișierul.

Pentru a bloca manual un tabel, trebuie să folosim una dintre funcțiile LOCK(), RLOCK() sau FLOCK(). Funcțiile RLOCK() și LOCK() sunt folosite pentru blocarea înregistrărilor individuale. Comanda FLOCK() este folosită pentru a bloca fișiere întregi. Dacă folosim aceste comenzi pentru a bloca o înregistrare sau un tabel, trebuie să eliminăm blocajele de îndată ce nu mai utilizăm înregistrarea sau tabelul. Deblocarea permite celorlalți utilizatori să acceseze datele blocate anterior.

În exemplul următor, comanda FLOCK() este utilizată pentru a bloca tabelul GERMFASK, împiedicându-i pe ceilalți utilizatori să-l actualizeze. Atunci când blocarea tabelului reușește, comanda REPLACE ALL actualizează fiecare înregistrare a tabelului GERMFASK. La sfârșit, comanda UNLOCK elimină blocajul fișierului. Dacă fișierul nu poate fi blocat (în cazul în care un alt utilizator a blocat o înregistrare), este afișat un mesaj de eroare.

SET EXCLUSIVE OFF

SET REPROCESS TO 0

USE GERMFASK

IF FLOCK()

REPLACE ALL LASTNAME WITH UPPER (LASTNAME)

UNLOCK

ELSE

WAIT WINDOW “Fișierul este utilizat de altcineva ”

NOWAIT

ENDIF

În Tabelul 2, sunt explicate comenzile pentru deblocarea înregistrărilor și a fișierelor. În multe situații, deplasarea fizică de la o înregistrare a tabelului la o altă înregistrare sau tabel face ca FoxPro să deblocheze automat un element blocat. În schimb, dacă am blocat în mod explicit un tabel (sau o înregistrare), va trebui să-l deblocăm pentru ca acesta să poată fi accesat de alți utilizatori.

Tabelul 2

Observație : Dacă blocăm o înregistrare într-o funcție definită de utilizator și

deplasăm indicatorul de înregistrări, după care revenim la înregistrarea respectivă, blocajul acelei înregistrări va fi automat eliminat.

CUM PROCEDĂM ATUNCI CÂND ÎNREGISTRAREA DE CARE AVEM NEVOIE ESTE BLOCATĂ

Se întâmplă să dorim să accesăm o înregistrare a unui tabel și să constatăm că este folosită de un alt utilizator sau proces. Atunci când survine o asemenea situație, vom vedea mesajul de eroare “Record is în use by another”. Acest mesaj este generat atunci când înregistrarea sau tabelul au fost blocate de un alt utilizator sau dacă tabelul a fost deschis de un alt utilizator cu o comandă exclusivă. Dacă se întâmplă acest lucru, va trebui să așteptăm pentru a efectua editările.

Atunci când edităm câmpuri sitaute în tabele aflate în relație, înregistrările aferente sunt blocate pentru a preveni dubla editare. În schimb, dacă înregistrarea curentă sau oricare dintre înregistrările corelate sunt blocate de alt utilizator, tentativa de blocare va eșua. Atunci când tentativa de blocare reușește, FoxPro ne permite să edităm înregistrarea. Blocajul este eliminat atunci când trecem la altă înregistrare, activăm altă fereastră sau efectuăm o altă activitate.

Dacă optăm pentru utilizarea comenzilor Browse, Edit sau Modify Memo în vederea editării, vom constata că aceste comenzi nu blochează înregistrarea decât în momentul în care este editată.

UTILIZAREA SESIUNILOR

Visual FoxPro prezintă programatorilor conceptul de sesiune de date. Sesiunile de date sunt medii de date care sunt asociate unui formular. Acest lucru înseamnă că putem asocia unui formular tabelele pe care acesta urmează să le utilizeze pentru diverse operații. Există două tipuri de sesiuni de date : private și prestabilite.

Fiecare sesiune de date reprezintă un mediu de date distinct care este asociat unui formular. De exemplu, mediul de date descrie zona : modul în care apar cursoarele în zona de lucru, tabelele și indecșii asociați și relațiile dintre ele. Sesiunile de date permit crearea instanțelor multiple ale aceluiași formular. Un exemplu de acest gen este cazul unui utilizator care dorește să vadă simultan mai multe înregistrări referitoare la clienți. În loc să închidă formularul curent, utilizatorul va solicita pur și simplu o nouă instanță a formularului referitor la clienți.

Sesiuni de date multiple, echivalente

UTILIZAREA ZONELOR TAMPON PENTRU EDITARE

Una dintre cele mai performante caracteristici ale programului Visual FoxPro este abilitatea acestuia de a utiliza zone tampon pentru date. Această caracteristică permite să utilizăm mai eficient resursele locale, limitând astfel conflictele referitoare la resursele rețelei și ale serverului.Prin utilizarea zonelor tampon pentru date se stochează în stația de lucru toate modificările efectuate asupra datelor Aceste date nu sunt actualizate în server decât în momentul în care aplicația comunică programului FoxPro să le actualizeze.

Există două opțiuni disponibile pentru utilizarea zonelor tampon : zone tampon pentru înregistrări și zone tampon pentru tabele. Prin utilizarea zonelor tampon pentru înregistrări, se stochează editările efectuate asupra înregistrărilor individuale. De îndată ce sunt finalizate actualizările unei înregistrări individuale, datele sunt transferate pe disc. Acest lucru se întâmplă de îndată ce indicatorul de înregistrări este deplasat sau este executată o funcție TABLEUPDATE(). Prin utilizarea zonelor tampon pentru tabele, se stochează în memorie modificările multiple efectuate asupra unui tabel. Aceste date sunt transferate atunci când tabelul este închis sau când este utilizată o funcție TABLEUPDATE().

Zonele tampon Visual FoxPro pentru înregistrări și tabele

Aceste zone tampon asigură securitatea în contextul actualizării și întreținerii datelor atunci când se efectuează activități de editare, eliminare și modificare atât asupra înregistrărilor individuale, cât și asupra înregistrărilor de date multiple, în medii multiutilizator.

Observație : O dată ce utilizarea zonelor tampon a fost activată pentru sesiunea

curentă, ea rămâne activă până în momentul în care este dezactivată sau

până când tabelul este închis.

Atunci când opțiunea de utilizare a zonelor tampon este activă, conflictele între operațiile de actualizare a datelor pot fi detectate și rezolvate. Pe parcursul unei operații de editare, înregistrarea curentă este copiată într-o locație din memorie sau de pe disc, care a fost identificată în prealabil, după care este gestionată de FoxPro. Datorită prezenței acestei copii distincte, ceilalți utilizatori pot accesa înregistrarea originală fără riscul de a o altera. În momentul în care înregistrarea este transferată înapoi, FoxPro încearcă să blocheze înregistrarea și verifică dacă au fost efectuate modificări de către ceilalți utilizatori. Modificările rezultante sunt scrise pe hard-disc. Această tehnică este cunoscută sub numele de blocare optimistă.

După efectuarea tentativei de actualizare a datelor, orice alte conflicte care împiedică scrierea în fișier a editărilor stocate pe hard-disc trebuie, de asemenea, să fie identificate și rezolvate.

ZONELE TAMPON DE ÎNREGISTRĂRI

Utilizarea zonelor tampon pentru înregistrări este recomandabilă atunci când suntem interesați de accesarea, modificarea și/sau scrierea pe disc a unei singure înregistrări la un moment dat. Acest proces permite validarea adecvata a proceselor cu un impact minim asupra operațiilor de actualizare a datelor efectuate de alți utilizatori, într-un mediu multiutilizator.

ZONE TAMPON DE TABELE

Utilizarea zonelor tampon de tabele pentru date, pe de alta parte, este folosită atunci când dorim să stocăm actualizările mai multor înregistrări ale unui tabel. Această metodă este perfect adaptată pentru înregistrările situate într-un singur tabel sau pentru înregistrările fiu aflate în relație una-la-mai-multe.

BLOCAREA ÎN ZONELE TAMPON

Utilizarea zonelor tampon pentru înregistrări sau tabele poate fi utilizată împreună cu unul din două moduri posibile de blocare. Aceste moduri determină în ce condiții vor fi blocate una sau mai multe înregistrări, precum și cum și când pot fi eliminate blocajele înregistrărilor respective. Cele două moduri sunt numite modul optimist și modul pesimist.

Deosebirea dintre aceste două tipuri de mecanisme de blocare este dată de momentul în care FoxPro efectuează blocările. Blocarea pesimistă solicită programului Visual FoxPro să interzică accesul la înregistrare de îndată ce începe editarea. În aceste fel, este interzisă modificarea înregistrării de către ceilalți utilizatori până în momentul în care este terminată actualizarea. Blocarea optimistă interzice accesul la înregistrare atunci când datele sunt actualizate pe disc. Această abordare permite mai multor utilizatori să editeze aceeași înregistrare.

În Tabelul 3, sunt date valorile a cinci optiuni de utilizare a zonelor tampon. În cazul utilizarii zonelor tampon pentru accesarea datelor aflate la distanță, proprietății de utilizare a zonelor tampon trebuie să-i fie atribuită valoarea 3 (utilizarea optimistă a zonelor de tampon pentru linii) sau 5 (utilizarea optimistă a zonelor de tampon pentru tabele).

Tabelul 3

Cele cinci exemple care urmează ilustrează metodele de activare a utilizării zonelor de tampon un aplicații. Paragrafele insoțitoare furnizează explicații referitoare la modul în care sunt configurate diversele comenzi de utilizare a zonelor tampon pentru înregistrări cu ajutorul functiei CURSORSETPROP(); fiecare secțiune se încheie cu o scurtă explicație.

Pentru a activa blocarea pesimistă a înregistrărilor, se folosește comanda următoare :

=CURSORSETPROP(“Buffering”, 2, “customer”)

Cu această comandă, FoxPro încearcă mai întâi să blocheze înregistrarea din poziția curentă a indicatorului. Dacă această tentativă reușește, FoxPro plasează înregistrarea în zona tampon și permite înregistrarea acesteia. Atunci când indicatorul este mutat din poziția curentă sau este lansată comanda TABLEUPDATE(), programul transferă înregistrarea din zona tampon înapoi în fișierul original.

Pentru a activa blocarea optimistă a înregistrărilor, se folosește comanda următoare :

=CURSORSETPROP(“Buffering”, 3, “customer”)

Cu aceasta comandă, FoxPro scrie înregistrarea curentă într-o zona tampon. După efectuarea acestei operațiuni, este permisă editarea înregistrării respective. Dacă indicatorul este mutat din poziția curentă sau dacă este lansată comanda TABLEUPDATE(), FoxPro încearcă să instituie un blocaj asupra înregistrării. Dacă blocarea reușește, este efectuată o comparație între valoarea curentă a înregistrării situate pe disc și valoarea originală din zona de tampon. Dacă cele două valori coincid, eventualele editari sunt scrise în tabelul original. În caz contrar, editarea nu este efectuată și este generat un mesaj de eroare pentru inștiințarea utilizatorului în legatură cu acest fapt.

Pentru a activa blocarea pesimistă a înregistrărilor multiple, se folosește comanda următoare :

=CURSORSETPROP(“Buffering”, 4, “customer”)

Această comanda face o tentativă de blocare a înregistrării din poziția indicatorului. Dacă blocarea reuseste, programul plasează înregistrarea în zona tampon. În continuare, este permisă editarea înregistrării.

Pentru a activa blocarea optimistă a înregistrărilor multiple, se folosește comanda următoare :

=CURSORSETPROP(“Buffering”, 5, “customer”)

Această comandă copiază înregistrarea în zona tampon, după care permite editarea până în momentul în care este lansată comanda TABLEUPDATE(). În continuare, sunt efectuate în mod secvențial următoarele activități :

Se încearcă blocarea tuturor înregistrărilor.

Dacă blocarea reușește, FoxPro compară valoarea curentă a fiecarei înregistrări de pe disc cu valoarea originală din zona de tampon.

În cazul în care în urma comparației se constată că valorile sunt identice, FoxPro scrie valorile originale ale tabelului pe hard-disc.

Dacă valorile nu sunt identice este genarat un mesaj de eroare.

Observatie : pentru ca oricare dintre metodele de utilizare a zonelor tampon să

funcționeze, trebuie să executăm comanda SET MULTILOCKS ON.

EFECTUAREA ACTUALIZĂRILOR

Înainte de efectuarea oricăror actualizări ale datelor trebuie să stabilim ce metodă de utilizare a zonelor tampon și ce mecanism de blocare vom folosi. O dată stabilite aceste opțiuni, utilizarea zonelor de tampon pentru înregistrări și tabele poate fi activată fie din cod, fie din caseta de dialog Data Enviroment a formularului.

Pentru scrierea editărilor în tabelul originar, trebuie folosită funcția TABLEUPDATE(). În cazul eșuării unei operații de actualizare a unui tabel care face obiectul unor restricții definite cu ajutorul regulilor, aceste editări pot fi anulate cu comanda TABLEREVERT(). Comanda TABLEREVERT rămâne validă chiar dacă nu este activată utilizarea explicită a zonelor tampon pentru tabele.

În exemplul următor, înregistrările sunt actualizate cu opțiunea de blocare pesimistă a înregistrărilor activată. În codul metodei Init a formularului, tabelul este deschis și este activată blocarea pesimistă a înregistrărilor. În continuare, indicatorul parcurge toate câmpurile, verificându-le pe fiecare pentru a stabili dacă au fost modificate. Apoi, fiecare câmp este comparat cu originalul pentru a vedea dacă valoarea inițială s-a modificat. În caz afirmativ, utilizatorul poate opta pentru restabilirea datelor inițiale.

OPEN DATABASE BOOK

Use Pages

= CURSORSETPROP (“Buffering”, 2)

1Modified = .F.

For nFieldNum = 1 to FCOUNT()

IF GETFLDSTATE(nFiledNum) = 2

1Modified = .T.

EXIT

ENDIF

ENDFOR

IF 1Modified

nResult = MESSAGEBOX;

(“ Înregistrarea a fost modificată . Doriți să o salvați ?” ; 4+32+256)

IF nResult = 7

=TABLEREVERT(.F.)

ELSE

=TABLEUPDATE(.T. , .T.) && Forțează modificarea tabelului

ENDIF

ENDIF

SKIP

IF EOF()

=MESSAGEBOX(“Sunteți deja la sfârșitul tabelulu !”)

SKIP –1

ENDIF

THISFORM.Refresh

DETECTAREA ȘI REZOLVAREA CONFLICTELOR

Este de la sine înțeles că orice proces care efectuează operații de actualizare a datelor trebuie proiectat cu atenție. De exemplu, trebuie să stabilim cum și când să deschidem tabelele și înregistrările, care este opțiunea optimă da utilizare a zonelor de tampon și dacă datele trebuie blocate. Cea mai mare atenție trabuie acordată intervalului de timp în care datele sunt considerate a fi în pericol.

Conflictele survin atunci când, de exemplu, apare următorul scenariu : unul sau mai mulți utilizatori încearcă simultan să blocheze o înregistrare sau un tabel care este deja blocat (și utilizat) de un alt utilizator. Doi utilizatori nu vor putea să blocheze simultan și apoi să acceseze aceeași înregistrare sau tabel. Această competiție nu va avea învingător!

Blocarea definitvă survine survine atunci când un utilizator a blocat o înregistrare, sau un tabel, după care încearcă să blocheze o a două înregistrare sau tabel care a fost blocată anterior de un al doilea utilizator. În același timp, acest al doilea utilizator încearcă să blocheze înregistrarea care a fost deja blocată de primul utilizator.

Aplicatiile trebuie scrise astfel încât să gestioneze situații de genul celor tocmai descrise. La proiectarea unei aplicații multiutilizator sau în activitățile care adaugă facilități pentru lucrul în rețea într-un sistem monoutilizator, caracteristica FoxPro de utilizare a zonelor tampon pentru tabele și înregistrări simplifică într-o oarecare măsură lucrurile.

După cum am constatat anterior, dacă încercăm să blocăm o înregistrare sau un tabel care a fost blocat anterior de alt utilizator, FoxPro returnează un mesaj de eroare pentru a ne avertiza în legătură cu acest fapt. Dacă folosim blocarea în cod cu comanda SET REPROCESS, cu rutina ON ERROR sau cu comanda RETRY, vom putea să gestionăm automat situațiile în care survin tentative nereușite de blocare.

În exemplul următor, rutinele SET REPROCESS și ON ERROR sunt folosite pentru gestionarea coliziunilor datelor utilizatorilor. În acest exemplu, dacă survine o eroare, este rulată rutina numită ERR_FIX. În continuare, fișierele sunt deschise neexclusiv. Reprocesarea blocărilor nereușite este efectuată automat și tabelul este deschis. În continuare, codul efectuează o serie de activități de adăugare, înlocuire și adăugare de înregistrări. În sfârșit, o rutină (REP_CURR) înlocuiește datele în înregistrarea curentă înainte de a adăuga înregistrări din alt fișier (ADD_RECS).

ON ERROR DO err_fix WITH ERROR(), MESSAGE()

SET EXCLUSIVE OFF

SET REPROCESS TO AUTOMATIC

USE CLIENT

IF !FILE (‘custcopy.dbf ’)

COPY TO CUSTCOPY

ENDIF

DO appblank

DO repnext

DO repall

DO repcurr

DO addrecs

ON ERROR

PROCEDURE repcurr

PARAMETERS lnError, lcMessage

WAIT WINDOW “ERROR ” + lcMessage + “at line ” + STR(lnError)

RETURN

PROCEDURE appblank

Append Blank

RETURN

PROCEDURE repnext

Replace Next 100 contact with Proper(contact)

RETURN

PROCEDURE repall

Replace all contact with Proper(contact)

GO TOP

RETURN

PROCEDURE repcurr

Replace contact with Proper(contact)

RETURN

PROCEDURE addrecs

Append from cus_copy

RETURN

Fără discuție, mediile partajate reprezintă o provocare pentru programatori și administratorii de sistem atunci când se efectuează operații de actualizare a datelor. Va trebui să determinăm care câmpuri au fost modificate (dacă exsită vreunul), care a fost valoare inițială a unui câmp și cu ce valoare a fost ulterior înlocuită. Probabil este mai simplu să determinăm care câmpuri au fost modificate, să găsim datele care au fost modificate și să comparăm în mod individual valoarea curentă, cea inițială și noua valoare editată înainte de a decide care este metoda optimă de tratare a erorii sau a conflictului.

În exemplul următor, funcția GETFLDSTATE() este folosită pentru a stabili dacă un câmp a fost modificat. Această funcție trebuie executată după efectuarea unei operații de actualizare :

1Modified = .F.

FOR nFieldNum = 1 to FCOUNT()

IF GETFLDSTATE(nFieldNum) = 2

1Modified = .T.

EXIT

ENDIF

ENDFOR

Funcția GETFLDSTATE() funcționează numai asupra datelor pentru care sunt utilizate zone tampon. Dacă folosim funcția GETFLDSTATE() în codul unui buton SKIP al unui formular, în momentul în care indicatorul este deplasat, FoxPro verifică starea tuturor câmputilor înregistrării. În continuare în cazul în care au fost efectuate modificări, putem evalua dacă utilizatorul poate trece la următoarea înregistrare.

Functia GETNEXTMODIFIED() returnează numărul primei înregistrări modificate a unui tabel care folosește zone tampon. Aceasta este o metodă elegantă de a controla actualizarea înregistrărilor prin compararea lor cu fișierul de date original. Atunci când o combinăm cu funcțiile CURVAL() și OLDVL(), funcția GETNEXTMODIFIED() ne permite să dezvoltăm rutine de “mediere” pentru cazurile în are doi utilizatori accesează simultan aceleași date.

În exemplu următor, sunt utilizate atât valorile curente, cât și cele anterioare pentru a permite utilizatorului să opteze în cunoștință de cauză pe parcursul unei operații de actualizare. Exemplu este destinat continuării verificărilor după detectarea primei înregistrări modificate. În primul rând, indicatorul parcurge ciclic zona tampon și blochează înregistrarea modificată. În continuare, indicatorul caută o zonă de conflict. Atunci când o găsește, compară valoarea inițială cu valoarea curentă rezidentă pe hard-disc. Atunci când găsește această valoare, programul solicită utilizatorului să specifice dacă dorește să păstreze modificarile, iar în cazul în care acesta răspunde negativ, înregistrarea este readusă la valorile inițiale și este deblocată. După care, indicatorul continuă să parcurgă ciclic zona tampon în căutarea altor conflicte. În final, sunt actualizate toate înregistrările.

DO WHILE nCurRec <> 0

GO nCurRec

= RLOCK()

FOR nField = 1 to FCOUNT(cAlias)

CField = FIELD(nField)

IF OLDVAL(cField)<> CURVALcField()

nResult = MESSAGEBOX (“Datele au fost modificate de un alt utilizator. Doriț să păstrați

modificările ?” ; 4+48+0)

IF nResult = 7

= TABLEREVERT(.F.)

UNLOCK RECORD nCurRec

ENDIF

ENDFOR

nCurRec = GETNEXTMODIFIED(nCurRec)

ENDDO

= TABLE UPDATE(.T., .T.)

UTILIZAREA PROCESĂRII TRANZACȚIILOR

Chiar și cele mai elaborate planuri pot eșua pe parcursul execuției unei aplicații. Din acest motiv, caracteristica Visual FoxPro de procesare a tranzacțiilor ne ajută să protejăm datele în timpul proceselor de actualizare și de recuperare a înregistrărilor.

Utilizarea zonelor tampon pentru înregistrări și tabele în mediul FoxPro ne ajută să protejăm aplicațiile prin plasarea unor întregi secțiuni de actualizări ale datelor într-o regiune protejată, însă recuperabilă a hard-discului. Tranzacțiile pot fi la rândul lor imbricate și folosite pentru protejarea actualizărilor care utilizează zone tampon.

Tranzacțiile acționează ca un înveliș pentru stocarea temporară (în memorie sau pe hard-disc) a operațiilor de actualizare a datelor, în locul efectuării actualizărilor direct în tabel. Deși actualizările propriu-zise sunt efectuate la sfârșitul tranzacției, dacă pentru un motiv sau altul aceste actualizări nu poti fi efectuate, întreaga tranzacție poate fi abandonată, actualizările anulate, fără efectuarea nici unei operații de actualizare asupra datelor noastre, protejându-le în acest fel de suprascrierea accidentală.

Pentru controlarea unei tranzacții se folosesc trei comenzi : BEGIN TRANSACTION, END TRANSACTION și ROLLBACK.

Tabelul 4 definește aceste trei comenzi.

Tabelul 4

DEFINIREA LIMITELOR UNEI TRANZACȚII

Procesarea unei tranzacții poate fi utilizată în conjuncție cu zone tampon de înregistrări, însă nu și cu activități care utilizează zone tampon pentru tabele. Singura excepție o constituie includerea funcției de comandă TABLEUPDATE() într-o tranzacție. Atunci când se utilizează această comandă, o actualizare eșuată poate fi derulată înapoi, iar cauza eșuării actualizării poate fi determinată și eliminată înainte de reîncărcarea funcției TABLEUPDATE(), fără să existe pericolul pierderii datelor.

DERULAREA ÎNAPOI A UNEI TRANZACȚII

Procesarea tranzacțiilor simple nu este atât de volatilă pe cât am putea presupune la prima vedere. Totuși, sistemul nu garantează o protecție împotriva căderii sistemului. Atunci când sistemul cade sau survine o altă anomalie, cum ar fi întreruperea tensiunii în timpul procesării comenzii END TRANSACTION, există posibilitatea eșuării actualizării și, prin urmare, a alterării datelor.

În exemplul următor este ilustrată utilizarea comenzilor BEGIN TRANSACTION, END TRANSACTION și ROLLBACK sub forma unui șablon.

BEGIN TRANSACTION

IF …

ROLLBACK

ELSE

Operații de validare a câmpurilor

IF … ROLLBACK

ELSE END TRANSACTION

ENDIF

ENDIF

Din exemplul precedent se pot desprinde următoarele reguli referitoare la procesarea tranzacțiilor :

Trebuie să încadrăm tranzacțiile cu comenzile BEGIN TRANSACTION și END TRANSACTION. Dacă o folosim pe una fără cealaltă, va fi generat un mesaj de eroare. Datele noastre vor fi blocate în momentul în care o comandă solicită direct sau indirect acest lucru. Astfel, orice comenzi UNLOCK directe sau indirecte ale sistemului sau ale utilizatorului sunt păstrate în zona tampon a tranzacției până la sfârșitul operației, semnalat fie de comanda END TRANSACTION, fie de comanda ROLLBACK.

Dacă folosim comenzile de blocare FLOCK() și/sau RLOCK(), tratate la începutul acestui capitol, utilizarea comenzii END TRANSACTION nu elimină blocajul; trebuie deblocate în mod explicit toate blocajele unei tranzacții.

În cazul în care comanda ROLLBACK este utilizată fără a fi precedată de comanda BEGIN TRANSACTION, instrucțiunea ROLLBACK va genera o eroare.

O dată ce inițiem procesarea unei tranzacții, procesul continuă până în momentul în care este întâlnită comanda END TRANSACTION sau ROLLBACK corespunzătoare. Acest proces poate fi extrapolat referitor la execuția tuturor programelor și funcțiilor până în momentul terminării aplicației, când începe o derulare înapoi.

În ceea ce privește interogările implicate în tranzacțiile noastre programul Visual FoxPro utilizează mai întâi datele din zona tampon a tranzacției, înainte de a utiliza datele de pe disc. Acest proces asigură utilizarea în primul rând a celor mai actuale date.

Ori de câte ori execuția unei tranzacții eșuează, toate operațiile eșuează, iar datele rămân intacte până în momentul în care cauza eșecului a fost identificată și eliminată.

Tranzacțiile au loc numai într-un container de bază de date. Nu putem folosi comanda INDEX dacă utilizarea ei determină suprascrierea unui fișier de index existent sau dacă a fost deschis vreun fișier de index.

IMBRICAREA TRANZACȚIILOR

În anumite situații, va trebui să utilizăm tranzacții imbricate. Tranzacțiile imbricate sunt grupuri logice de operații de actualizare a tabelelor care pot fi eliminate din procesele concurente. Atunci când este necesară imbricarea, nu este obligatoriu ca perechea de comenzi BEGIN și END TRANSACTION să se găsească în aceeași procedură sau funcție.

Ca și în cazul tranzacțiilor obișnuite, imbricarea tranzacțiilor trebuie să respecte o serie de reguli :

Putem imbrica până la cinci perechi BEGIN și END TRANSACTION.

Actualizările efectuate în cadrul unei tranzacții imbricate nu vor fi finalizate (salvate) pe hard-disc decât în momentul în care este întâlnită comanda END TRANSACTION finală.

Comanda END TRANSACTION are efect nu numai asupra tranzacției care a fost inițiată de ultima comandă BEGIN TRANSACTION.

Instrucțiunile ROLLBACK operează numai asupra tranzacției care a fost inițiată de ultima comandă BEGIN TRANSACTION.

Într-un set de tranzacții imbricate, cea mai interioară actualizare a acelorași date va avea prioritate față de toate celelalte actualizări din același bloc.

În exemplul următor, este executată o tranzacție imbricată. În primul rând este executat un proces de curățare a efectelor tranzacțiilor executate anterior. Apoi este configurat mediul în vederea utilizării zonelor tampon prin atribuirea valorii ON parametrului Multilocks și a valorii OFF parametrului Exclusive. În continuare, este activată blocarea optimistă a tabelelor, iar programul modifică o serie de înregistrări. Dacă actualizarea eșuează, întreaga tranzacție este derulată înapoi până când cauza eșecului este determinată și apoi corectată.

DO WHILE TXNLEVEL() > 0

ROLLBACK

ENDDO

CLOSE ALL

SET MULTILOCKS ON

SET EXCLUSIVE OFF

OPEN DATA TEST

Use MRGTEST1

= CURSORSETPROP (“BUFFERING”, 5)

GO TOP

REPLACE FLD1 WITH “alterat”

SKIP

REPLACE FLD1 WITH “alterat din nou”

= MESSAGEBOX(“Modifică primul câmp al ambelor înregistrări pe o altă mșină.”)

BEGIN TRANSACTION

1Success = TABLEUPDATE(.T. , .F.)

IF 1Success = .F.

ROLLBACK

=AERROR(aErrors)

DO CASE

CASE aErrors[1,1] = 1539

* – Cod pentru tratarea erorii

CASE aErrors[1,1] = 1581

* – Cod pentru tratarea erorii

CASE aErrors[1,1] = 1582

* – Cod pentru tratarea erorii

CASE aErrors[1,1] = 1585

NNextModified = getnextmodified(0)

Do While nNextModified <> 0

Go nNextModified

= RLOCK()

For nField = 1 to FCOUNT()

CField = FIELD(nField)

If OLDVAL(cField) CURVAL(cField)

NResult = Messagebox (“Aceste date au fost modificate de un alt utilizator. Doriți

să păstrați modificările ?” , 4+48)

If nResult = 7

= TABLEREVERT(.F.)

UNLOCK record nNextModified

ENDIF

EXIT

ENDIF

ENDFOR

ENDDO

BEGIN TRANSACTION

=TABLEUPDATE (.T., .T.)

ENDTRANSACTION

UNLOCK

…

CASE aErrors[1,1] = 1700

…

CASE aErrors[1,1] = 1583

…

CASE aErrors[1,1] = 1884

…

OTHERWISE

=MESSAGEBOX(“Mesaj de eroare necunoscut :” + STR(aErrors[1,1]))

ENDCASE

ELSE

END TRANSACTION

ENDIF

ALTE SOLUȚII PENTRU REDUCEREA NUMĂRULUI DE BLOCAJE

Atunci când dezvoltă aplicații multiutilizator, programatorii trebuie să înțeleagă faptul că orice blocaj prezent într-un fișier, indiferent dacă este vorba de un blocaj de înregistrare sau de fișier, trebuie menținut într-un fel sau altul de sistemul de operare al rețelei. Nu este un lucru neobișnuit ca o rețea să rețină mii de blocaje la un moment dat. Întreținerea blocajelor duce la scăderea performanțelor rețelei. Există câteva tehnici pentru reducerea numărului de blocaje menținute în rețea. Această secțiune tratează pe scurt câteva dintre aceste tehnici.

UTILIZAREA SEMAFORIZĂRII BLOCAJELOR

O abordare uzuală în aplicațiile multiutilizator o reprezintă imlpementarea unei tehnici oarecare de semaforizare. Tehnicile de acest gen utilizează un câmp suplimentar al tabelului pentru a stabili dacă o înregistrare este utilizată sau nu. În cazul în care câmpul este completat, înregistrarea nu va fi disponibilă în vederea actualizării. Avantajul acestei abordări este că reduce supraîncărcarea rețelei. Citirea datelor din tabelele FoxPro nu necesită instituirea de blocje în rețea. Prin urmare, putem verifica dacă o înregistrare este blocată prin efectuarea unei citiri a înregistrării respective, după care, în cazul în care câmpul suplimentar este gol, o putem bloca. Această metodă prezintă unele inconveniente, și anume creșterea gradului de utilizare a spațiului de pe disc și riscul ca o înregistrare să rămână blocată în cazul căderii discului.

LUCRUL CU VARIABILE DE MEMORIE

O a două metodă utilizată la dezvoltarea aplicațiilor multiutilizator este aceea de a transfera în memorie conținutul unei înregistrări și de a edita conținutul în memorie. Această abordare reduce supraîncărcarea asociată editării directe a tabelelor, deoarce blocajele pot fi plasate pe înregistrare în momentul actualizării (abordare optimistă). Dezavantajul acestei abordări este că înainte de a le actualiza, programatorii trebuie să creeze funcții care să verifice dacă datele de pe disc s-au modificat. Această abordare, deși este corectă, poate fi înlocuită cu succes prin utilizarea tehnicilor de utilizare a zonelor tampon.

STOCAREA DATELOR DE CĂUTARE ÎN MASIVE

O altă abordare presupune stocarea în memorie a conținutului tuturor tabelelor de căutare. Aceasta nu reduce solicitarea rețelei, însă reduce numărul fișierelor deschise la un moment dat. Identificatoarele de fișiere, ca și blocajele, trebuie menținute de sistemul de operare al rețelei. În consecință, ori de câte ori avem posibilitatea de a reduce numărul acestor elemente în sistem, aplicația va rula mai rapid.

CREAREA FIȘIERELOR TEMPORARE

Aplicațiile multiutilizator tind să fie mai lente decât cele monoutilizator. Dacă avem probleme cu un sever lent trebuie avut în vedere sugestiile următoare pentru mărirea vitezei calculatorului și, pe această cale, mărirea vitezei globale a aplicației.

Putem plasa fișierele temporare pe unitatea de disc locală. De exemplu, dacă folosim indecși pentru a efectua activități ad-hoc, la care nimeni altcineva nu solicită accesul, acești indecși pot fi mutați pe unitatea de disc locală. (Presupunând că avem o unitate de disc locală și nu folosim un simplu terminal și un monitor.)

Visual FoxPro pentru Windows creează toate fișierele temporare în directorul prestabilit (de obicei n:\VXP). În cazul în care calculatorul local posedă o cantitate impresionantă de spațiu pa hard-disc, mutarea fișierelor de lucru temporare pe unitatea locală sau pe un disc RAM conduce la creșterea semnificativă a performanțelor aplicației prin reducerea numărului de cereri de fișiere adresate serverului de fișiere din rețea.

Putem specifica și alte locații pentru fișierele noastre prin includerea următoarelor instrucțiuni în fișierul nostru de configurare (CONFIG.FPW) : EDITWORK, SORTWORK, PROGWORK și TMPFILES.

ALEGERE ÎNTRE SORTARE ȘI INDEXARE

Vom analiza diferența dintre sortarea și indexarea datelor. Sortarea datelor creează o copie fidelă a datelor respective sub un alt nume, însă cu un anumit câmp sortat în ordine alfabetică ascendentă (A-Z) sau descendentă (Z-A). Pe de altă parte, indexarea creează un nou fișier cu informațiile pe care le vedem, prezentate în ordinea în care vrem să fie afișate, însă fără crearea unui nou tabel care să furnizeze datele. Sortarea o vom efectua după câmpurile care sunt ordonate în mod uzual : numărul clientului, numărul comenzii și așa mai departe.

DESCHIDEREA FIȘIERELOR PENTRU UTILIZARE EXCLUSIVĂ

Putem opta pentru utilizarea unei comenzi exclusive. O comandă exclusivă interzice altor utilizatori să acceseze datele, atunci când acestea sunt manipulate de un (singur) utilizator. Candidate pentru acest tip de activitate sunt actualizările masive, precum și cerințele ad-hoc ce sunt specifice unui singur utilizator și așa mai departe.

UTILIZAREA COMENZII EXCLUSIVE

Comanda EXCLUSIVE este cea care ne permite să deschidem un tabel în vederea utilizării lui exclusiv de către noi. Comanda interzice tuturor celorlalți să deschidă tabelul atâta timp cât acesta se află sub controlul nostru. În momentul în care încheiem sesiunea de editare, închiderea tabelului dezactivează exclusivitatea tabelului. În continuare acesta este disponibil pentru a fi folosit de un alt utilizator.

Comenzile care urmează determină deschiderea exclusivă a tabelelor. În primul exemplu, comanda are două părți, fiecare fiind tastată sub forma unei linii distincte în fereastra de comenzi. Al doilea exemplu ne permite să deschidem un fișier în vederea utilizării exclusive cu o singură linie :

SET EXCLUSIVE ON

USE POOH

sau

USE POOH EXCLUSIVE

Lista care urmează conține o serie de comenzi. Înainte de a folosi aceste comenzi, trebuie să deschidem tabelul în vederea utilizării exclusive. Dacă încercăm să lansăm oricare dintre aceste comenzi asupra unui tabel deschis în mod neexclusiv, FoxPro ne avertizează afișând mesajul Exclusive Open of File is required.

ALTER TABLE

INDEX

INSERT [BLANK]

MODIFY STRUCTURE

PACK

REINDEX

ZAP.

PREZENTAREA APLICAȚIEI

Aplicația se numește ”Administrarea unui cămin” și reprezintă un sistem informatic care se ocupă cu administrarea unui cămin studențesc în ce privește serviciile de cazare și plată a taxei de cămin. Aplicația permite accesul mai multor utilizatori în același timp la bazele de date, fiind proiectată pentru rularea în rețea. De asemenea poate fi îmbunătățită prin modelerea ei ca o aplicație client-server. Accesul la aplicație se face pe baza unui nume de utilizator și a unei parole, și este structurat pe nivele de securitate. În funcție de aceste nivele sunt acordate drepturile pe care utilizatorul le va avea pe tot timpul în care este intrat în sistem.

Aplicația folosește o singură bază de date și o tabelă liberă. Structura este reprezentată în următoarea figură :

Structura de date a aplicației.

Baza de date se numește administrație, iar tabelele care o compun sunt : studenți, buletine, adrese, camere, cazări și plăți. Tabela liberă se numește funcționari. Structurile acestor tabele sunt prezentate în continuare.

Tabelele : studenți, buletine și adrese.

Tabelele : camere, cazări și plăți.

În continuare voi prezenta meniul aplicației :

Meniul aplicației.

În continuare voi prezenta pe larg aplicația prin intermediul unor fotografii captate din timpul rulării.

Această imagine reprezintă prima formă care se execută atunci când startăm aplicația. Din această formă avem două opțiuni, fie continuăm și trecem la următorul pas care este introducerea unui nume de utilizator și a unei parole fie părăsim aplicația.

Aceasta este forma care permite unui utilizator să acceseze aplicația. Numele de utilizator se alege din combobox-ul din dreptul etichetei “Username”. Odată selectat un nume, celelalte căsuțe se completează cu datele personale ale respectivului utilizator. În acest moment dacă utilizatorul introduce parola corectă, el intră în aplicație cu drepturile care le are, iar dacă alege opțiunea “Cancel” accesează aplicația cu drepturi minime. Această formă face parte din modulul “Login”. Tot din modulul acesta mai fac parte “Logout” și “Schimbare parolă”. Opțiunea “Logout” permite unui utilizator să iasă din sesiunea sa de lucru și setează aplicația la acces cu drepturi minime. “Schimbare parolă” permite unui utilizator să-și schimbe parola. Tot din acest modul mai face parte și “Exit”, care permite ieșirea din aplicație.

Următorul modul este cel de informații. Aici se pot obține informații, în limita drepturilor utilizatorilor, despre studenți, serviciile de cazare și plată și despre camere.

Această formă reprezintă informațiile despre un student , atunci când utilizatorul ale nivelul 2 de securitate, nivelul 3 fiind cel mai mare, iar 0 cel mai mic.

Această fotografie reprezintă forma cu informații despre camere. La aceste informații au acces toți utilizatorii.

Imaginea de mai sus reprezintă informațiile care se pot obține despre un student: camera la care este cazat și plățile pe care acesta le-a efectuat.

Următoarele două module necesită drepturi de scriere și de citire din partea utilizatorului, adică nivelul de securitate trebuie să fie cel puțin 2. Funcțiile care realizează opțiunile celor două module folosesc comenzi care blochează, în funcție de necesități, antetul unei tabele, o singură înregistrare sau o înregistrare împreună cu toate înregistrările din celelalte tabele cu care se alfă în relație. Începem cu opțiunea “Funcționari” din modulul “Administrație”. Această opțiune permite navigarea prin tabela liberă “Funcționari”, editare și adăugare de înregistrări.

Prima pagină este pentru navigare și editare. Prin apăsarea butonului de editare această pagină se modifică permițând ediatrea înregistrării curente.

A doua pagină permite adăugarea unei înregistrări noi.

Cealaltă opțiune a modulului “Administrație” permite aceleași operații de navigare, editare și adăugare pentru tabela “Camere”, care face parte din baza de date “Administrație”.

În imaginea de mai sus este surprins momentul în care se face modificarea datelor unei camere. Aceste modificări sunt salvate în baza de date doar în momentul în care se obține blocarea tabelei “Camere”, în caz contrar utilizatorul este avertizat că tabela este folosită de o altă persoană.

În cadrul modulului “Servicii” se poate opta pentru o acțiune de cazare sau de plată a taxei de cămin. În primul caz se eliberează contractul de cazare, iar în celălat caz se eliberează chitanța .

Mai sus este prezentat formularul specific operațiunii de cazare. Precizez faptul că în timp ce se completează acest formular se pot consulta și informațiile care se obțin din modulul “Informații”.

Formularul de mai sus trebuie completat în cazul operațiunii de plată a taxei de cămin. Prin selectarea butonului “Chitanța” se obține chitanță care reprezintă suma pe care studentul a plătit-o. Ca și în cazul contractului de cazare, chitanța poate fi listată pe ecran sau la imprimantă.

Ultima opțiunea a meniului este cea de “Help”. Aici se pot afla informații despre aplicație și despre opțiunile din meniu.

În încheiere precizez faptul ca aplicația se poate extinde la o aplicație bazată pe modelul Client-Server, și poate fi îmbunătățită prin adăugarea unor module noi pentru a informatiza în totalitate activitățile administrative ale unui camin studențesc.

CONCLUZII

În această lucrare am prezentat tehnici pentru controlul concurenței aupra unei baze de date. Am început mai întâi cu câteva noțiuni de bază cum ar fi : tranzacție, item , blocaj, serializabilitate, orar, protocol. Apoi am continuat cu prezentarea unor situații care se pot ivi atunci când mai mulți utilizatori accesează o bază de date și fiecare încearcă sa blocheze unul sau mai multe item-uri. Am prezentat in acest caz situațiile de livelock și de deadlock. În capitolele următoare am prezentat câteva modele pentru tranzacții. În cadrul acestor modele am facut teste de serializabilitate și am descries protocoale care trebuie respectate pentru a garanta serializabilitatea. De la modele simple de tranzacții am trecut la modele cu blocaje la scriere și la citire. Următorul model care a fost discuat era unul în care puteam avea blocaje doar pentru scriere sau doar pentru citire. Aici ne-am pus problema echivalenței orarelor și am întălnit noțiunea de tranzacție inutilă.

Următorul fapt discutat a fost concurența pentru structurile ierarhice de item-uri. În cadrul acestei secțiuni s-au prezentat două protocoale de blocare a item-urilor :

pe arbori și pe subarbori. Având în vedere că vorbim despre accesarea datelor dintr-o rețea era evident să discutăm de cazurile în care sistemul s-ar putea prăbuși. Aici s-au discutat posibilitățile de recuperare a datelor după o prăbușire de sistem sau alte cauze care ar putea determina întreruperea tranzacțiilor.

Capitolul “Partajarea datelor în rețea cu ajutorul programului Visual FoxPro” prezintă cum se pot implementa aplicații pentru rețea în Visual Foxpro.

Capitolul “Prezentarea aplicației” descrie partea practică a acestei lucrări, și

anume “Administrația unui cămin studențesc”. Această aplicație este implementată astfel încât sa poată fi rulată în rețea și se bazează pe aspectele tratate în această lucrare.

BIBLIOGRAFIE

“Principles of Database Systems” de Jeffrey D. Ullman; Stanford University.

Eswaran [1976] – modelul din Secțiunile 2 și 3 ale primului capitol.

Papadimitriou, Berstein, Rothnie [1977] și Papadimitriou [1978] – modelul din Secțiunea 4 (care permite blocaje doar-scriere) și testul de serializabilitate bazat pe poligraf.

Silberschatz și Kedem [1978] – protocolul arbore pentru bazele de date structurate ierarhic.

Gray, Putzolo, Traiger [1976] și Gray [1978] – “protocolul de avertizare”.

Coffman și Denning [1973] – este o sursă pentru materiale generale despre sisteme concurente.

“Utilizare Visual Foxpro, Ediție specială” – Christopher R. Green –“Partajarea

datelor în rețea”.