Managemantul Tranzactiilor In Baze de Date Relationale
CAPITOLUL I
INTRODUCERE
Mecanismele tranzacționale nu sunt o noutate în lumea bazelor de date. În anii 70, la doar câteva sute de kilometri distanță, laboratoarele IBM de la San Jose și Universitatea Berkeley dezvoltau în paralel primele sisteme relaționale, System R și Ingres, ambele cuprinzând anumite forme de procesare tranzacțională. Începând de atunci, toate SGBD-urile importante încorporează mecanisme tranzacționale.
Procesarea tranzacțiilor are ca scop păstrarea integrității bazei de date. Trebuie însă precizat că mecanismele tranzacționale nu sunt singurele care se ocupă de păstrarea integrității. Mai precis, procesarea tranzacțiilor se referă doar la două aspecte:
Recuperarea bazei de date după un incident (database recovery) – se bazează pe includerea unui anumit nivel de redundanță prin memorarea istoriei tranzacțiilor într-un așa-numit “jurnal” (log). Deși acest aspect nu face subiectul articolului de față, anumite elemente tehnice privind jurnalizarea vor fi utilizate în continuare.
Controlul interferențelor care pot avea loc între tranzacțiile care se execută in mod concurent (concurrency control) – este un aspect critic în sistemele de aplicații OLTP (On-Line Transaction Processing). Este vorba despre “controlul” (și nu neapărat “evitarea”) interferențelor deoarece, deși întotdeauna nedorite, aceste interferențe pot fi permise – în anumite forme bine precizate – pentru a crește performențele sistemului.
Progresele informaticii, atât la nivel hardware cât și software: scăderea costului hardware-ului și creșterea considerabilă a puterii de calcul au condus la o generalizare a utilizării informaticii în toate domeniile de activitate.
În consecință, în perioada ultimilor ani au apărut domenii de aplicații mai puțin clasice, ca de exemplu: CAD (Proiectarea asistată de computer), birotică, aplicații pentru gestiunea datelor spațiale sau geografice etc. Aceste aplicații, au scos în evidență limitele modelului relațional de date în ceea ce privește reprezentarea, stocarea și prelucrarea informațiilor complexe.
Noile tipuri de date, precum sunetul, imaginea și grafica, din ce în ce mai frecvent utilizate nu pot fi prelucrate în cadrul sistemelor de gestiune de baze de date relaționale.
Limitele modelului relațional de date sunt generate pe de o parte de incapacitatea de reprezentare structurală a informațiilor și, pe de altă parte de imposibilitatea de a reprezenta în totalitate semantica acestor informații.
Singura structură de date disponibilă în modelul relațional este tabloul cu două dimensiuni, care materializează o relație n-ară între mai multe domenii elementare de valori, și care nu permite reprezentarea directă a obiectelor complexe care conțin adesea mai multe nivele de imbricare, fiind necesară descompunerea obiectelor în mai multe relații, iar reconstituirea obiectelor complexe pornind de la relații este o operație dificilă.
De asemenea, datele stocate sunt pur descriptive, esența semanticii asociată acestor date se găsește în programele de prelucrare, doar restricțiile de integritate permit reprezentarea unui anumit nivel al semanticii asociată datelor.
Mai mult, sistemele relaționale au început să-și dezvăluie limitele și în ceea ce privește puterea de calcul. Limbajele de interogare, în general declarative, nu permit exprimarea tuturor prelucrărilor.
O aplicație clasică de gestiune a produselor complexe, formate din repere elementare și/sau compuse își propune, de exemplu, calculul prețului unui produs, constituit din prețul de bază pentru reperele elementare și costul de asamblare pentru reperele compuse. Un astfel de calcul trebuie să se aplice recursiv tuturor elementelor care intervin în componența produsului considerat. Această operație nu poate fi realizată cu un limbaj de interogare declarativ precum SQL.
Programatorul aplicației este obligat să utilizeze două limbaje de programare: un limbaj imperativ (Cobol, Pascal, C) și un limbaj declarativ (SQL). Aceste două limbaje utilizează concepte de programare diferite și nu comunică între ele într-un mod armonios: sistemele lor de tipuri sunt diferite, limbajul declarativ accesând un ansamblu de înregistrări, în timp ce limbajul imperativ accesează doar câte o singură înregistrare.
Limitele sistemelor relaționale ar putea fi înlăturate prin anumite abordări ale orientării obiect. Nu există o terminologie strictă pentru a denumi modelele, limbajele și sistemele care se inspiră din conceptul de obiect. Se pot utiliza deci, în egală măsură termenii pe obiecte, orientate obiect sau simplu obiectuale pentru a califica sistemele și limbajele evocate.
Cercetarea în domeniul bazelor de date s-a axat pe furnizarea de soluții pentru problemele expuse anterior. Au fost urmate în special două direcții de cercetare:
Elaborarea unor modele de date mai bogate și mai puternice decât modelul relațional, care s-a concretizat prin două abordări:
– Extinderea modelului relațional prin eliminarea restricției de reprezentare a datelor sub formă de relații care nu mai sunt in prima formă normală. De aici au rezultat mai multe propuneri care generalizează noțiunea de relație prin introducerea constructorilor “mulțime”, “tuplu” și „lista” oferind astfel posibilitatea modelării mulțimilor de tupluri, dar și a mulțimilor de mulțimi etc. Aceste modele sunt numite în general modele complexe orientate pe obiecte .
– Definirea de noi modele de date, independente de cel relațional. Aceste modele, numite modele semantice, utilizează concepte și mecanisme de abstractizare care permit o modelare mai fidelă a realității, valorificând anumite tehnici ale inteligenței artificiale cu privire la reprezentarea cunoștințelor.
2) Definirea limbajelor de programare pentru baze de date (LPBD), care reunesc funcționalitățile limbajelor de programare și cele ale bazelor de date. Această direcție de cercetare a avut în vedere următoarele obiective importante:
– Diminuarea sau chiar eliminarea disfuncționalităților între limbajul de programare și limbajul de interogare prin integrarea modelului de date într-un limbaj de programare, experiențe care au generat limbajele Pascal/R și Adaplex.
– Integrarea noțiunii de persistență în limbajele de programare, elaborându-se astfel limbaje de programare persistente (LPP), ceea ce permite conservarea datelor prelucrate prin programe după execuția lor, fără implicarea directă a utilizatorului. Limbajele de programare PS-Algol și Galileo se constituie printre primele realizări ale acestei abordări.
3) Apariția și dezvoltarea limbajelor orientate obiect (LOO) a avut o influență determinantă asupra dezvoltării noilor sisteme, atât în domeniul bazelor de date cât și al limbajelor. Limbajele orientate obiect care utilizează primitive de modelare asemănătoare celor specifice modelelor semantice, oferă posibilități superioare de integrare a bazelor de date și limbajelor de programare.
Ca rezultat al cercetărilor s-au conturat trei mari categorii de sisteme de baze date:
sistemele care vizează extinderea modelului relațional, numite sisteme de gestiune a bazelor de date relaționale extinse (SGBDRE), se caracterizează prin adăugarea unor noi instrumente de modelare și programare:
tipurile abstracte de date și reguli;
limbaje de programare de nivel înalt, limbajele de generația a patra (L4G).
sistemele bazate pe noile modele de date, numite sisteme de gestiune a bazelor de date orientate obiect (SGBDOO), care se caracterizează prin:
utilizarea noțiunii de obiect complex și a conceptelor din modelele semantice;
preluarea din domeniul limbajelor de programare a tipurilor abstracte de date și a numeroase concepte orientate obiect, beneficiind, de asemenea, de experiența limbajelor de programare persistente.
c) sistemele bazate pe programarea logică, numite sisteme de baze de date deductive, care utilizează reguli de inferență pentru a deduce noi fapte pornind de la cele stocate în bază, prin intermediul limbajelor de programare logică, precum Prolog sau Datalog.
Apariția modelului relațional de date la începutul anilor ‘70 și sistemele de baze de date relaționale care formează generația de sisteme a anilor ‘80, constituie o realizare majoră în domeniul bazelor de date. Bazat pe teoria relațiilor și pe logică, modelul relațional a constituit o revoluție în raport cu sistemele bazate pe modelul de date ierarhic și rețea.
Sistemele relaționale reprezintă, cu certitudine, un stadiu avansat în domeniul utilizării bazelor de date și au permis dezvoltarea unei tehnologii relaționale importante, bine fundamentată teoretic.
Am putea rezuma avantajele modelului relațional de date prin:
– Simplitatea conceptelor și schemei, prin utilizarea noțiunii de relație și a teoriei normalizării;
– Un înalt grad de independență a datelor, prin asigurarea independenței fizică și logică a datelor;
– Un bun suport teoretic, bazat pe teoria matematică a mulțimilor și pe logică;
– Limbaje de manipulare de nivel înalt, prin caracterul lor declarativ;
– Posibilitatea optimizării accesului la baza de date, prin exploatarea proprietăților algebrice ale operatorilor;
– Ameliorarea integrității și confidențialității, prin utilizarea unor limbaje de interogare de nivel înalt și prin specificarea restricțiilor de integritate;
– Manipularea booleană a datelor, care oferă prelucrarea globală a datelor, asigură o gestiune automată și o posibilă utilizare a paralelismului.
Toate aceste caracteristici ale modelului relațional de date constituie o referință în tendința de elaborare a altor modele de date, multe dintre acestea încercând să valorifice achizițiile realizate în decurs de câteva decenii de către modelul relațional.
CAPITOLUL II
TRANZACȚII
Conceptul de gestiune a tranzacțiilor se referă la problematica menținerii într-o stare consistentă a bazei de date în condițiile accesul la date se face în regim concurent si este posibilă apariția unor defecte. În consecință se disting două domenii de sine stătătoare în cadrul problematicii generale a gestiunii tranzacțiilor:
– controlul concurenței
Se ocupă cu mecanismele de sincronizare a acceselor astfel încât să fie menținută integritatea bazei de date. Atunci când controlul concurenței este realizat prin mecanismele de blocare(care la ora actuală sunt cele mai răspândite) mai apare o altă problemă, colaterală și anume aceea a interblocărilor. Datorită importanței sale problema gestiunii interblocărilor este de multe ori tratată ca o problematică de sine stătătoare a gestiunii tranzacțiilor.
– rezistenta la defecte
Se referă la tehnicile prin care se asigură atât toleranța sistemului fața de apariția unor defecte, cât și capacitatea de recuperare a acestuia, adică posibilitatea de revenire la o stare consistentă în urma apariției unui defect care a acuzat intrare lui într-o stare inconsistentă.
Definiția conceptului de tranzacție
Prin controlul concurenței si rezistența la defecte se urmărește asigurarea consistenței si sigurantei bazei de date. O bază de date este într-o stare consistentă dacă respectă toate constrângerile de integritate a datelor definite asupra sa. În timpul operațiilor de adăugare, ștergere și actualizare baza de date trece dintr-o stare în alta. Evident, starea rezultată după orice prelucrare asupra bazei de date trebuie să fie o stare consistentă chiar dacă in timpul prelucrării baza de date s-a găsit temporar într-o stare incosnistentă.
Siguranța bazei de date se referă la toleranța acesteia față de defecte si la capacitatea de recuperare după apariția unui defect.
O tranzacție este o unitate logică de prelucrare care asigură consistența si siguranța bazei de date. În principiu orice execuție a unui program se poate considera o tranzacție dacă baza de date este într-o stare consistentă atât înainte cât si dupa execuția sa. Consistența bazei de date este garantată indepentent de faptul că :
1. tranzacția a fost executată in mod concurent cu alte tran interblocărilor este de multe ori tratată ca o problematică de sine stătătoare a gestiunii tranzacțiilor.
– rezistenta la defecte
Se referă la tehnicile prin care se asigură atât toleranța sistemului fața de apariția unor defecte, cât și capacitatea de recuperare a acestuia, adică posibilitatea de revenire la o stare consistentă în urma apariției unui defect care a acuzat intrare lui într-o stare inconsistentă.
Definiția conceptului de tranzacție
Prin controlul concurenței si rezistența la defecte se urmărește asigurarea consistenței si sigurantei bazei de date. O bază de date este într-o stare consistentă dacă respectă toate constrângerile de integritate a datelor definite asupra sa. În timpul operațiilor de adăugare, ștergere și actualizare baza de date trece dintr-o stare în alta. Evident, starea rezultată după orice prelucrare asupra bazei de date trebuie să fie o stare consistentă chiar dacă in timpul prelucrării baza de date s-a găsit temporar într-o stare incosnistentă.
Siguranța bazei de date se referă la toleranța acesteia față de defecte si la capacitatea de recuperare după apariția unui defect.
O tranzacție este o unitate logică de prelucrare care asigură consistența si siguranța bazei de date. În principiu orice execuție a unui program se poate considera o tranzacție dacă baza de date este într-o stare consistentă atât înainte cât si dupa execuția sa. Consistența bazei de date este garantată indepentent de faptul că :
1. tranzacția a fost executată in mod concurent cu alte tranzacții
sau că
2. au apărut defecte în timpul execuției tranzacției.
În general o tranzacție constă dintr-o secvență de operații de citire si scriere a bazei de date, la care se adaugă o serie de operații de calcul. Baza de date poate fi într-o stare temporar inconsistentă în timpul executării tranzacției, dar trebuie să fie în stări consistente atât înainte, cât și după execuția tranzactiei.
Exemplu:
Fie un sitem de rezervare a locurilor pe liniile aeriene a cărei bază de date conține 3 relații definite prin schemele:
ZBOR(Codz, Sursa, Dest, Libere)
CLIENT(Codc, Nume, Adresa)
REZERVARE(Codz, Codc, Observații).
Semnificația atributelor este următoarea:
Codz codul unic al zborului; este cheie în relația ZBOR;
Sursa, Dest sursa și destinația zborului;
Libere numărul de locuri încă nevândute;
Codc codul unic al fiecărui client al companiei;
este cheia în relația CLIENT;
Nume, Adresa numele și adresa clientului;
Observații informații referitoare la rezervarea în sine.
Pentru a face o rezervare se introduce codul zborului solicitat și codul clientului care dorește rezervarea. Tranzacția corespunzătoare operației de rezervare poate fi implementată, folosind o interfață SQL integrată într-un mediu PASCAL, astfel:
Begin_tranzaction Rezervare
Begin
Input (cod_zbor, cod_client);
EXEC SQL
Update zbor
SET Libere = Libere – 1
WHERE Codz = Cod_zbor;
EXEC SQL
INSERT INTO REZERVARE(Codz,Codc,Observatii)
VALUES(cod_zbor, cod_client, NULL);
Output(“Rezervare efectuata!”);
End.
După cum se poate observa din implementarea tranzacției, rezervarea unui loc presupune doua accese la baza de date:
Primul acces se face în relația ZBOR pentru a decrementa numărul de locuri libere; este o operație de actualizare;
Al doilea acces realizează scrierea unei noi înregistrări în relația în relația CLIENT. Înregistrarea unui nou client costituie obiectul unei alte tranzacții.
2.1 Condiții de terminare a tranzacțiilor
În exemplul de mai sus tranzacția prin care se face rezervarea unui nou loc nu ia în considerare faptul că s-ar putea șa nu mai existe locuri libere pentru un zbor. Din contră, tranzacția se bazează pe presupunearea implictă că întotdeauna există un loc liber, ceea ce este total nerealist. Rezultă că tranzacția în cauză nu se poate realiza întotdeauna cu succes, ci trebuie analizate și celelalte alternative. Totuși orice tranzacție trebuie să se termine, indiferent de situația existentă (chiar și în cazul unoe defecte ). Dacă tranzacția reușește să execute cu succes toate operațiile prevăzute, atunci aceasta se va termina printr-o operație de validare (commit). În schimb, dacă, dintr-un motiv sau altul, tranzacția nu reușește să-și execute complet operațiile prevăzute, atunci se va termina printr-o operație de abortare (abort sau rollback). Motivele pentru care tranzacție se abortează sunt numeroase, ele pot fi interne tranzacției sau externe acesteia (ex : detectarea de către SGBD a unei situații de interblocare). În cazul abortării execuția tranzacției este oprită iar efectele tuturor operațiilor pe care le-a executat până în acel moment sunt anulate astel încât baza de date revine la starea de dinaintea lansării tranzacției.
Comanda de validare a unei tranzacții are un dublu rol:
Indică SGBD-ului momentul de la care efectele tranzacției pot fi reflectate în baza de date și devin vizibile altor tranzacții;
Marchează momentul începând de la care efectele tranzacției nu mai pot fi anulate (tranzacția nu se mai poate aborta) și modificările efectuate în baza de date devin permanente.
Operația de validare este vitală în cazul sistemelor concurente, deci acolo unde este posibilă executarea în același timp mai multor tranzacții care accesesază aceeași bază de date. Prin validare se pot preveni o serie de fenomene nedorite cum este abortare în cascadă a tranzacțiilor.
Să presupunem că o tranzacție T este abortată după ce a efectuat una sau mai multe operații de actualizare a bazei de date. În acest caz alterate de catre tranzacția T vor fi readuse la valorile pe care le-au avut înainte de a fi modificate de aceast. Este, însă posibil ca unele dintre tranzacțiile executate în mod concurent cu tranzacția T să fi accesat aceste date înainte de abortarea lui T. Aceste tranzacții vor trebui să fie la rândul lor abortate deoarece au avut acces la date inconsistente din bază ceea ce înseamnă că rezultatele produse de ele pot fi compromise. Acest efect se poate propaga în continuare și asupra altor tranzacții, pe un număr nedefinit de nivele, conducând la abortarea în cascadă a tranzacțiilor. Fenomenul este cunoscut în literatura de specialitate sub numele de efect domino.
Dacă se folosește un mecanism de validare care respectă cele două reguli de mai sus, atunci apariția fenomenului de abortare în cascadă devine imposibilă . Într-adevăr, conform primei reguli, nici o tranzacției nu va putea accesa datele modificate de către tranzacția T decât validarea acesteia. Pe de altă parte, conform regulii a doua, după validarea sa tranzacția T nu mai poate fi abortată, deci nu poate declanșa un lanț de abortări în cascadă.
Validarea unei tranzacții marchează, din punct de vedere logic, terminarea acesteia. Validarea nu se poate face înainte ca operațiile specficate prin codul tranzacției să fie executate integral și înainte ca tranzacția să ajungă intr-o stare începând de la care există certitudinea că nu mai poate fi abortată.
Până în momentul validării, actualizările efectuate de tranazcției sunt indivizibile alor tranzacții, au caracter tentativ și pot fi oricând revocate(o dată cu abordare tranzacției). După validare actualizările se înscriu cu caracter permanent în baza de date și devin irevocabile. După validare nu mai este posibilă abortarea tranzacțiilor.
Exemplu:
Pentru a lua în considerare și situatia în care nu mai este nici un loc disponibil pentru un zbor dat, tranzacția pentru exemplul din paragraful precedent poate fi rescrisa astfel:
Begin_tranzaction Rezervare
Begin
Input(cod_zbor, cod_client);
EXEC SQL
SELECT Libere
INTO temp
FROM ZBOR
WHERE Codz=cod_zbor;
If temp = 0 then
Begin
Output(“Nu mai sunt locuri libere!”);
ABORT
End
Else
Begin
EXEC SQL
UPDATE ZBOR
SET Libere = Libere-1
WHERE Codz = cod_zbor;
EXEC SQL
INSERT INTO
REZERVARE(Codz,Codc,Observații)
VALUES(cod_zbor,cod_client,NULL);
COMMIT;
Output(“Rezervare efectuată!”);
End
End.
În această variantă a tranzacției numărul de locuri libere corespunzător zborului solicaitat este citit în variabila temp pentru a se verifica dacă mai sunt locuri libere. Dacă nu sunt locuri, atunci tranzacția se termină prin abortare, după ce s-a semnalat printr-un mesaj lipsa de locuri. Dacă mai sunt locuri disponibile, atunci se face rezervarea și tranzacția se termină printr-o comnadă de validare (COMMIT). De remarcat că mesajul către utilizator indicând efectuarea cu succes a rezervării trebuie să succeadă comanda de validare, deoarece tranzacția ar putea fi abortată în orice moment dinaintea validării datorită unor cauza externe tranzacției. Numai după validare există certitudinea că rezervarea nu mai poate fi anulată și că va fi înregistrată cu caracter permanent în baza de date.
2.2 Proprietățile tranzacțiilor
Prin definiție tranzacțiile sunt unități de execuție care garantează consistența și siguranța bazei de date. Pentru aceasta orice tranzacție trebuie să satisfacă un set de 4 condtiții sintetizate în literatură prin acronimul ACID-atomicitate, consistență, izolare, durabilitate.
Atomicitatea
Se referă la faptul că o tranzacție este considerată ca o unitate elementară de prelucrare. Aceasta înseamnă că execuția unei tranzacții se face după regula “totul sau nimic”, adică ori sunt executate toate operațiile din tranzacție, ori nu se execută nimic. Dacă o tranzacție este întreruptă datorită unor cauze oarecare, atunci îi revine SGBD-ului sarcina de a asigura, într-un fel sau altul, terminarea tranzacției. După eliminarea cauzei care a dus la întreruperea tranzacției în funcție de stadiul de execuție în care s-a aflat aceasta în momentul apariției întreruperii, SGBD-ul poate proceda în două moduri :
Fie completează operațiile rămase neexecutate din cadrul tranzacției terminând tranzacția cu succes
Fie anulează toate efectele operațiilor executate de tranzacție în momentul întreruperii, terminând tranzacția prin abortare.
Consistența
Consistența unei tranzacții constă pur și simplu în corectitudinea sa. Orice tranzacție, dacă este executată independent, trenuie să mențină consistența bazei de date. Altfel spus, o tranzacție este un program corect care transformă baza de date dintr-o stare consistentă intr-o altă stare consistentă a sa. Prin consistența bazei de date înțelegem satisfacerea tuturor constrângerilor de integritate, explicite sau implicite, cum ar fi :
Unicitatea cheilor primare;
Integritatea referențială;
Orice predicat exprimat în sens de constrângere de integritate asupra bazei de date.
Bineînțeles că este de neconceput verificarea tuturor acestor condiții după executarea fiecărei tranzacții. De aceea unicul criteriu pentru stabilirea proprietății de consistență a unei tranzacții rămâne corectitudinea sa din punct de vedere logic. Spre deosebire de celelalte proprietăți din complexul ACID care sunt asigurate de către sistem, proprietatea de consistență a tranzacției cade în sarcina programatorului de aplicații. De remarcat faptul că stările intermediare prin care trece baza de date în timpul execuției unei tranzacții nu sunt neapărat consistente.
Izolarea
Se referă la proprietatea oricărei tranzacții de a avea acces doar la stările consistente ale bazei de date. Aceasta înseamnă că modificările efectuate de către o tranzacție sunt incaccesible altor tranzacții concurente până în momentul validării acesteia. Prin proprietatea de izolare se creează iluzia că fiecare tranzacție este executată singură în sistem. Utilizatorul care a lansat o tranzacție nu va percepe în nici un fel (cel puțin în ce privește rezultatele) faptul că alte tranzacții sunt executate în același timp în sistem. Izolarea tranzacțiilor este asigurată prin algoritmii de control al concurenței. Conceptul de izolare este aproximat adesea prin cel de serializabilitate, deși nu se confundă cu acesta. Serializabilitatea, deși este o condiție suficientă pentru realizarea izolării, nu este și necesară.
Proprietatea de izolare este importantă deoarece elimină fenomenul de abordare în cascadă a tranzacțiilor (efect domino). Într-adevăr dacă rezultatele incomplete ale unei tranzacții ar fi vizibile altor tranzacții înanite de validarea acesteia și dacă se întâmplă ca această tranzacție să aborteze, atunci toate tranzacțiile care au accesat rezultatele incomplete vor trebui abortate. Aceasta poate conduce la abortarea altor tranzacții ș.a.m.d. rezultând efectul domino.
Durabilitatea
Durabilitatea unei tranzacții este proprieteatea prin care se garantează faptul că odată tranzacția validată, rezultatele sale devin permanente și sunt înscrise în baza de date. Chiar dacă după momentul validării apare un defect care împiedică înscrierea normală a rezultatelor tranzacției în baza de date acestea vor fi trecute în baza de date după reluarea activității. Rezultatele tranzacțiilor validate vor supraviețui unor căderi de sistem.
Mecanismul prin care se realizează propretatea de durabilitate are la bază conceptul de jurnal. Jurnalul este un fișier secvențial în care sunt înregistrate toate operațiile efectuate de tranzacțiile din sitem. Jurnalul conține istoria evoluției întregului sitem. El este folosit la reluarea activității de către procedurile de recuperare care vor completa eventualele operații neterminate ale tranzacțiilor care au fost validate înainte de apariția defectului.
2.3 Formalizarea conceptului de tranzacție
Pentru a putea raționa asupra tranzacțiilor și asuprea algoritmilor de gestiune a acestora este necesară o definire formală a conceptului de tranzacție. În cele ce urmează vom lua în considerare doar acele tranzacții care efectuează numai operații de citire sau scriere, ignorând tranzacțiile care cuprind operații de inserare sau șterger. Această simplificare restânge aria discuției la cazul bazelor de date statice care nu cresc sau descresc în dimensiune. În cazul, mai general, al bazelor de date dinamice apar aspecte suplimentare cum ar fi, de exemplu, problema fantomelor. Acestea însă depășesc cazul prezentării de față.
În virtutea celor de mai sus tranzacțiile pot fi caracterizate ca secvențe de operații abstracte de tip citire sau scriere. Definim setul de citire(read set – RS) al unei tranzacții ca mulțimea datelor accesate de aceasta în citire. Setul de scriere(write set – WS) este mulțimea datelor scrise de către o tranzacție. De remarcat că cele două seturi nu sunt neapărat disjuncte. Reuniunea dintre setul de citire și setul de scriere al unei tranzacții formează setul de bază(base set – BS=RS WS) al acesteia.
Notăm prin Oij(x) o operație Oj (read (R) sau write (W)) efectuată de către tranzacția Ti asupra unei entități x din baza de date, iar prin OSi setul tuturor operațiilor de citire sau scriere din Ti(OSi)= jOij). Fie, de asemeanea, Ni condiția de terminare a tranzacției Ti (care poate fi abortat (A) sau commit (C)) și i=OSi {Ni} mulțimea operațiilor tranzacției Ti împreună cu condiția de terminare.
Cu notițele de mai sus o tranzacție Ti se poate defini ca o relație de ordine parțială {i,<i} peste mulțimea operațiilor sale și condiția de terminare, operatorul de relație < indicand ordinea de execuție a operațiilor (Oi < Oj are semnificația “Oi se execută înaintea lui Oj”).
Așadar o tranzacție Ti se definește formal ca o relație de ordine parțială Ti={i,<i}, unde:
i=OSi Ni ;
Pentru orice două operații Oi, Oik OSi, dacă există o entitate x astfel încât:
Oij=R(x) și Oik=W(x)
ori Oij=W(x) și Oik=R(x)
ori Oij=W(x) și Oik=W(x),
atunci fie Oij <i Oik ori Oik <i Oij;
Oij OSi , avem Oij <i Ni.
Prima condiție din definiția formală a unei tranzacții definește domeniul al relației de ordine parțială ca fiind mulțimea operațiilor tranzacției împreună cu condiția de terminare. A doua condiție arată faptul că între oricare două operații conflictuale trebuie să existe ordine bine definită prin tranziție. Două operații sunt conflictuale dacă ambele accesează aceeași dată și cel puțin una dintre ele este de tip scriere. Ordinea relativă de execuție a două asemenea operații nu este indiferentă. Condiția a treia arată că toate operațiile tranzacției trebuie să preceadă condiția de terminare.
Exemplu:
Fie tranzacția T dată prin secvența:
READ(x)
READ(y)
xx+y
WRITE(x)
READ(z)
zx+z
WRITE(z)
COMMIT
Conform definiției de mai sus specificația fomală a acestei tranzacții este T=(, <) unde :
= {R(x),R(y),W(x),R(z),W(z),C}
< =
{(R(x),W(x)),(R(y),W(x)),(R(x),W(z)),
(R(y),W(z)),(R(z),W(z)),(R(x),C),
(R(y),C),(R(z),C),(W(x),C),(W(z),C),
De remarcat în exemplul de mai sus că relația de ordine < specifică precedența tuturor operațiilor față de condiția de terminare (conform condiției 3 din definiția formală). De asemenea se observă ca nu există definită o ordine pentru fiecare pereche de operații. Există mai multe perechi de operații (neconflictuale) a căror ordine de execuție este indiferentă (exemplu: R(x)-R(y), R(x)-R(z) sau W(x)-W(z)). Din acest motiv relația < este considerată ca una de ordine parțială.
Orice relație de ordine parțială poate fi reprezentată sub forma unui graf orientat aciclic (directed acylic graph – DAG). Înseamnă că o tranzacție se poate reprezenta ca un DAG ale cărui noduri reprezintă operațiile tranzacției sau condiția de terminare, iar arcele orientate reprezintă relația între diferitele perechi de operații. Această corescpndență este deosebit de utilă deoarece permite utilizarea instrumentelor din teoria grafurilor la rezolvarea problemelor legate de controlul execuției concurente a mai multor tranzacții.
Exemple:
Graful orientat aciclic corespunzător tranzacției T din exemplul de mai sus este reprezentat în figura 1.1. De remarcat faptul că s-a omis reprezentarea acelor arce care corespund unor relații ce sunt implicate prin tranzitivitate de către cele existente (ex: (R(x),C)).
În majoritatea cazurilor nu este necesar să se facă referiri la domeniul al relației de ordine parțială. Din acest motiv, de obicei, se renunță la specificarea explicită a lui din specificația formală a unei tranzacții și se folosește numele tranzacției pentru a referi atât domeniul cât și relația de ordine parțială. Această convenție permite reprezentarea într-o formă mai simplificată a ordinii operațiilor dintr-o tranzacție folosind ordonarea operațiilor dată prin definiția tranzacției. Astfel tranzacția T din exemplul de mai sus poate fi specificată astfel:
T= {R(x),R(y),W(x),R(z),W(z),C}.
R(x)
W(x)
R(y) C
W(z)
R(z)
Fig 2.1 Graful aciclic corespunzător tranzacției T.
CAPITOLUL III
CONTROLUL CONCURENȚEI
La sistemele în care o bază de date este accesată simultan de către mai mulți utilizatori apar situații de conflict datorate accesului concurent la datele care constituie o resursă comună. Modul de rezolvare al conflictului depinde de natura cererilor de acces la date, funcție de care putem distinge două cazuri extreme:
Dacă cererile de acces sunt de tipul "regăsire", atunci secvențializarea accesului la mediul de memorare este suficientă pentru a nu mai fi nevoie de alte precauții. Așa sunt bazele de date statistice, unde mai mulți utilizatori interoghează baza de date simultan. Atâta timp cât nici unul dintre utilizatori nu face modificări asupra datelor, nu are o importanță prea mare ordinea în care se asigură accesul utilizatorilor la date. Ca urmare rezolvarea situațiilor conflictuale cauzate de operațiile de citire simultane poate fi lăsată în seama sistemului de operare care stabilește ordinea de satisfacere a cererilor după criteriul asigurării concurenței maxime de operare minimizând timpul global de satisfacere a cererilor.
Situația este diferită dacă unele dintre cereri sunt de tipul "actualizare". În aceste cazuri este necesară aplicarea unor strategii adecvate de tratare a cererilor de acces. Exemplul tipic pentru această situație îl constituie sistemele de rezervare a locurilor, unde mai mulți agenți fac rezervări simultan și deci modifică permanent lista locurilor libere și lista rezervărilor. În lipsa unui control adecvat al cererilor de acces există pericolul ca același loc să fie rezervat de mai multe ori. Acest lucru este posibil deoarece în intervalul de timp de la acceptarea unei anumite cereri de rezervare pe un loc anume și până la rezolvarea acesteia (eliminarea locului cu pricina din lista de locuri libere) ar putea fi acceptate și rezolvate alte cereri de rezervare pentru același loc. Deci două procese care citesc și modifică valoarea aceluiași obiect ar putea interacționa în mod nedorit atunci când sunt executate simultan. Pentru a evita interacțiunile nedorite este necesară impunerea unor restricții asupra execuției concurente a proceselor care execută operații de citire și de modificare a datelor.
Calea cea mai simplă de evitare a interacțiunilor este de a executa tranzacțiile în mod independent, una după cealaltă. Este clar că o asemenea alternativă prezintă interes doar din punct de vedere teoretic și este practic inacceptabilă, deoarece minimizează eficiența sistemului. De fapt, nivelul de concurență, măsurat prin numărul de tranzacții executate concurent, este unul dintre cei mai importanți parametrii pentru caracterizarea unui asemenea sistem. Din acest motiv, mecanismele de control al concurenței urmăresc realizarea unui compromis între menținerea consistenței bazei de date și obținerea unui nivel de concurență cât mai ridicat. Din punctul de vedere al tranzacțiilor, controlul concurenței asigură proprietățile de izolare și consistență ale acestora, chiar și în condițiile executării concurente a mai multor tranzacții.
În cele ce urmează vom presupune că sistemul în discuție este absolut sigur, deci ne aflăm în situația ideală în care nu sunt posibile nici un fel de defecte (hardware sau software). Deși ipoteza este total nerealistă, ea constituie o simplificare necesară deoarece permite izolarea aspectelor legate de controlul concurenței față de cele relative la rezistența la defecte. Vom renunța la această ipoteză atunci când vom trece la prezentarea aspectelor legate de rezistența la defecte a sistemelor, unde vom analiza modificările care trebuie făcute algoritmilor de control al concurenței pentru a asigura fie funcționarea fără întreruperi a sistemului, fie posibilitatea de recuperare a acestuia la apariția diverselor defecte.
3.1. Anomalii de interferență
Interacțiunea necontrolată a două sau mai multe tranzacții poate conduce la apariția unor stări inconsistente ale bazei de date și la producerea unor rezultate eronate. Două tranzacții Ti și Tj sunt susceptibile de interferență dacă rezultatul execuției concurente a acestora poate fi diferit de rezultatul execuției seriale. Între două tranzacții poate să apară o interferență dacă acestea efectuează operații asupra unor date comune. În plus, dacă aceste tranzacții sunt executate în mod concurent, atunci spunem că sunt conflictuale. Deci două tranzacții Ti și Tj sunt conflictuale dacă sunt concurente și susceptibile de interferență.
În funcție de natura operațiilor pe care le efectuează asupra datelor comune, între două tranzacții pot să apară mai multe tipuri de interferență. Aceste interferențe sunt cauza a mai multor anomalii de interferență:
Anomalia de actualizare pierdută
Corespunde unui conflict de tip scriere-scriere și constă în faptul că rezultatul actualizării efectuate de o tranzacție se pierde ca urmare a reactualizării aceleiași date de către o alta tranzacție, fară ca reactualizarea să fie influențată de rezultatul primei actualizări.
Exemplu:
Fie următoarea execuție concurentă a două tranzacții T1 și T2
T1 T2
READ A;
READ A;
A=A+5;
WRITE A;
A=A+10;
WRITE A;
în urma căreia valoarea lui A apare mărită cu 10, în loc de 15 așa cum ar fi de așteptat. Este ca și cum tranzacția T1 nu s-ar fi executat de loc.
Anomalia de citire improprie
Corespunde unui conflict de tip scriere-citire și apare atunci când o tranzacție suprinde o stare temporar inconsistentă a bazei de date.
Exemplu:
Fie următoarea execuție concurentă a două tranzacții T1 și T2
T1 T2
READ A;
A=A-10;
WRITE A;
READ A;
READ B;
C=A+B;
WRITE C;
READ B;
B=B+10;
WRITE B;
unde se remarcă faptul că valoarea sumei A+B este aceeași înainte și după execuția de mai sus. Intenția este de a reține în C valoarea acestei sume, dar datorită interferenței valoarea din C este cu 10 mai mică decât cea reală.
Anomalia de citire nereproductibilă
Corespunde unui conflict de tip citire-scriere și apare atunci când aceeași tranzacție găsește valori diferite la citiri repetate ale aceleiași date.
Exemplu:
Fie următoarea execuție concurentă a două tranzacții T1 și T2,
T1 T2
READ A;
B=A;
WRITE B;
READ A;
A=A+10;
WRITE A;
READ A;
C=A;
WRITE C;
unde se observă că deși valorile rezultate pentru B și C în urma execuției tranzacției T1 ar trebui să fie egale, ele sunt diferite din cauza interferenței cu tranzacția T2.
3.2 Primitivele LOCK și UNLOCK
Fie tranzacțiile T1 și T2 execuții diferite ale următoarei secvențe de operații:
READ A; A=A+1; WRITE A;
unde A este o valoare existentă în baza de date. Fiecare din cele două tranzacții citește valoarea A într-o zonă de lucru proprie (buffer1, respectiv buffer2), adună 1 la această valoare după care scrie rezultatul în baza de date. După execuția tranzacțiilor T1 și T2 este de așteptat ca valoarea lui A să fie mărită cu 2. Totuși dacă tranzacțiile T1 și T2 sunt executate concurent, este posibil, funcție de modul de interferență al acestora, ca rezultatul să nu fie cel așteptat. De exemplu, după execuția concurentă din figura 3.l. valoarea lui A apare mărită doar cu 1.
Fig. 3.1. Execuție concurentă a două tranzacții TI și T2 care conduce la un rezultat eronat
Cea mai simplă metodă de evitare a situațiilor de genul celei prezentate este de a permite accesul la valoarea A a unei singure tranzacții pe toată durata executării acesteia. Accesul celorlalte tranzacții va fi temporar blocat în acest interval de timp. Acest lucru se poate realiza prin folosirea a două funcții primitive LOCK(A) și UNLOCK(A). Aceste funcții sunt considerate primitive în sensul că secvența de microperații corespunzătoare executării lor nu poate fi întreruptă de alte operații. Altfel spus LOCK() și UNLOCK() sunt operații indivizibile.
Dacă o tranzacție T execută cu succes o primitivă LOCK(A), atunci componenta lock manager a SGBD asigură accesul exclusiv al tranzacției T la valoarea A, interzicând accesul la această valoare a oricărei alte tranzacții atâta timp cât tranzacția T nu eliberează valoarea A prin executarea primitivei UNLOCK(A). Spunem că valoarea A este blocată în acest interval de timp. O tranzacție poate executa cu succes o primitivă LOCK() doar asupra unei valori care nu este blocată. În acest caz valoarea returnată de fucția LOCK() este TRUE. Orice tentativă de a executa primitiva LOCK() asupra unei valori blocate va eșua, valoarea returnată fiind FALSE. Acesta este cel mai simplu mecanism de a asigura excluderea mutuală. De remarcat că problema excluderii mutuale nu este specifică numai bazelor de date, ci caracterizează orice sistem concurent: limbaje concurente, sisteme de operare, hardware paralel ș.a.m.d.
Primitivele LOCK() și UNLOCK() pot fi folosite pentru realizarea mecanismelor dc sincronizare a tranzacțiilor. Astfel dacă o tranzacție dorește să acceseze o anumită valoare, ea va trebui să obțină accesul exclusiv la aceasta prin executarea unei primitive LOCK(). Dacă valoarea este blocată, atunci accesul exclusiv va fi refuzat, iar tranzacția va trebui să aștepte până la deblocarea acesteia, moment în care va putea executa cu succes primitiva LOCK() asupra acestei valori. Orice tranzacție care a executat cu succes o primitivă LOCK() asupra unei valori, va trebui să execute primitiva UNLOCK() asupra aceleiași valori înainte de a-și încheia execuția. Despre orice ordonare secvențială (eventual intermixată) a pașilor a două sau mai multe tranzacții care respectă regulile de mai sus se spune ca este legală.
Pentru tranzacțiile T1 și T2 considerate anterior secvența de pași folosind primitivele LOOK() și UNLOCK() este următoarea:
WHILE NOT(LOCK(A)); READ A; A=A +1; WRITE A; UNLOCK(A);
Observăm că dacă una dintre tranzacții, să zicem T1, obține accesul exclusiv la valoarea A, atunci tranzacția T2, va trebui să aștepte terminarea completă a lui T1 pentru a obține accesul la valoarea A. La terminarea tranzacției T1 valoarea lui A este mărită cu 1, iar la terminarea lui T2 valoarea va fi mărită cu 2.
În această ultimă variantă rezultatul este corect, dar execuția este pur secvențială, nu este posibil nici un fel de paralelism în executarea celor două tranzacții. Din punctul de vedere al timpului de execuție această situație este
inacceptabilă și de aceea se folosesc algoritmi care să realizeze ordonării secvențiale legale cu un grad de concurență al execuției cât mai ridicat, dar și cu garanția obținerii de rezultate corecte.
3.3. Unități de acces
O bază de date este partiționată în mai multe unități de acces (items). Acestea sunt porțiuni ale bazei de date care pot constitui obiectul unei operații de blocare (lock). Prin blocarea unei unități de acces o tranzacție poate împiedica accesul altor tranzacții la unitatea blocată până în momentul deblocării acestei unități de către tranzacția care a efectuat blocarea. Gestiunea operațiilor de blocare, precum și arbitrarea cererilor de blocare venite din partea tranzacțiilor este realizată de către o componentă specială a SGBD numită lock manager. Natura și dimensiunea unităților de acces este stabilită de proiectantul sistemului. De exemplu, în cazul modelului de date relațional unitațile de acces pot fi de dimensiuni mari cuprinzând relații întregi ale bazei de date, pot fi grupuri de tuple sau pot fi tuple individuale sau chiar componente ale tuplelor. Prin alegerea unor unități de acces de mari dimensiuni se reduce numărul operațiilor de blocare ceea ce înseamnă reducerea excesului de timp consumat de sistem pentru gestiunea acestor operații, precum și reducerea spațiului de memorie necesar înregistrării blocajelor. În schimb folosind unități de acces de mici dimensiuni crește gradul de concurență suportat de sistem deoarece vor putea fi executate în paralel un număr mai mare de tranzacții care operează în unități de acces diferite. În practică dimensiunea potrivită a unităților de acces este dată de extinderea operațiilor efectuate de tranzacțiile cu cea mai mare frecvență. Astfel dacă tranzacția tipică presupune efectuarea unor operații de cuplare, atunci unitatea de acces va fi relația. Dacă însă majoritatea tranzacțiilor efectuează operații asupra unor tuple individuale, atunci va fi convenabil să se aleagă tupla ca unitate de acces.
3.4. Serializabilitate
Serializabilitatea este o problemă de concurență care prezintă un interes deosebit în cazul bazelor de date. Așa cum s-a constatat și din exemplele de până acum, prin execuția concurentă a mai multor tranzacții se pot obține rezultate diferite față de situația în care fiecare tranzacție este executată independent. Dar rezultatele execuțiilor concurente pot să difere și între ele și sunt în general inconsistente. În mod firesc se consideră corect rezultatul obținut prin execuția independentă a tranzacțiilor. Numim o astfel de execuție execuție serială. Execuția concurentă a mai multor tranzacții este considerată corectă dacă și numai dacă efectul acesteia este echivalent cu cel al unei execuții seriale a acelorași tranzacții.
Numim planificare a unui set de tranzacții o ordine de execuție a pașilor elementari (LOCK, READ, WRITE, etc.) ai tranzacțiilor setului. Ordonarea se referă la pași din tranzacții diferite, ordinea relativă a pașilor aceleiași tranzacții nefiind afectată. O planificare se numește serială dacă toți pașii oricărei tranzacții apar în poziții consecutive ale planificării. O asemenea planificare determină o execuție serială, fără interferențe a tranzacțiilor.
O planificare se numește serializabilă dacă și numai dacă efectul ei este echivalent cu cel al unei planificări seriale.
Exemplu:
Fie două tranzacții T1 și T2 definite prin secvențele:
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;
Orice planificare serială a tranzacțiilor T1 și T2 are proprietatea că suma A+B+C rămâne nemodificată.
În figura 3.2. sunt prezentate trei planificări diferite ale tranzacțiilor T1 și T2: una serială, a doua serializabilă și a treia neserializabilă.
După execuția planificării neserializabile suma A+B+C este mărită cu 20 ca urmare a pierderii actualizării lui B (WRITE B) din tranzacția T2.
Fig. 3.2. Trei planificări diferite it două tranzacții T1 și T2
3.5. Formalizarea conceptului de serializabilitate
O planificare P (numită și istorie) este definită peste un set de tranzacții T={T1,T2,…,Tn} și specifică o ordine de execuție, posibil intercalată, a operațiilor acestora. Pornind de la definiția formală a conceptului de tranzacție, o planificare P poate fi, la rândul ei, definită ca o relație de ordine parțiala peste multimea T a tranzacțiilor componente.
După cum s-a arătat, două operații Oij(x) și Okl(x) (i și k nu neapărat distincte) care accesează aceeași entitate x din baza de date, sunt conflictuale dacă cel puțin una dintre ele este de tip scriere. Dacă cele două operații conflictuale aparțin unor tranzacții diferite Ti și Tk (i≠k), atunci aceste tranzacții sunt considerate de asemenea conflictuale.
O planificare completă definește ordinea de execuție ale tuturor operațiilor din domeniul său. Formal, o planflicare completă PTC definită peste un set de tranzacții T={T1,T2,…,Tn} este o relație de ordine parțială PTC={∑T,<T}, unde:
1. ∑T = i=1,n∑i;
2. <T i=1,n<I;
3. Pentru oricare două operații conflictuale Oij, Okl∑T, avem fie Oij <T Okl ori Okl <T Oij.
Prima condiție definește domeniul planificării ca fiind reuniunea domeniilor tranzacțiilor individuale. Condiția a doua arată că relația de ordine asociată planificării este un superset al relațiilor de ordine ale tuturor tranzacțiilor individuale. În sfârșit, condiția a treia precizează faptul că între oricare două operații conflictuale din domeniul planificării trebuie să existe o ordine relativă bine definită.
Exemplu:
Fie tranzacțiile:
Tl: READ(x) T2: READ(x)
xx+1 xx+1
WRITE(x) WRITE(x)
COMMIT COMMIT
O posibilă planificare completă PTc peste setul de tranzacții T=T1,T2 poate fi specificată formal prin relația de ordine partială: PTc={∑T, <T} unde:
∑T = R1,W1,C1,R2,W2,C2,
<T =
(R1,R2),(R1,W1),(R1,C1),(R1,W2),(R1,C2),
(R2,W1),(R2,C1),(R2,W2),(R2,C2)
(W1,C1),(W1,W2),(W1,C2),(C1,W2),(C1,C2),(W2,C2).
(Pentru simplificarea notației s-a omis specificarea explicită a argumentului operațiilor, acesta rezultând fără echivoc din contextul exemplului prezentat).
Graful aciclic corespunzător acestei planificări este prezentat în figura 3.3. (de menționat faptul că s-au omis din reprezentare arcele corespunzătoare acelor relații care sunt implicate prin tranzitivitate de către celelalte relații).
2
Fig, 3.3. Planificarea completă a setului de tranzacții T = T1,T2
Ca și în cazul tranzacțiilor individuale este uzuală folosirea unei convenții care simplifică notația unei planificări. Conform acestei convenții, o planificare este reprezentată sub forma unei liste a operațiilor din domeniul ∑T, ordinea acestora în listă fiind aceeași cu ordinea lor de execuție în cadrul planificării. Cu această convenție planificarea PTc din exemplul de mai sus se poate specifica astfel:
PTc = R1(x),R2(x),W1(x),C1,W2(x),C2.
O planificare se definește formal ca un prefix al unei planificări complete. Fiind data o relație de ordine parțială P={∑, <}, un prefix P'={∑', <'} al lui P se definște astfel:
1. ∑' ∑;
2. ei,ej ∑', avem: ei <' ej dacă și numai dacă ei < ej;
3. ei ∑', dacă ej ∑ și ej < ei, atunci ej ∑'.
Primele două condiții de mai sus definesc prefixul P' ca fiind o restricție a lui P la domeniul ∑', toate relațiile de ordonare din P fiind menținute și în P'. A treia condiție arată că pentru orice element din ∑', toți predecesorii săi din ∑ trebuie să fie incluși și în ∑'.
Conceptul de planificare, definit ca un prefix al unei planificări complete, oferă posibilitatea de a raționa asupra planificărilor incomplete. Acest lucru este util din punctul de vedere al teoriei serializabilității deoarece permite luarea în considerare doar a operațiilor conflictuale din cadrul tranzacțiilor, neglijând restul operațiilor care oricum nu au efect asupra serializabilității. De asemenea, capacitatea de a trata planificări incomplete devine absolut necesară atunci când se ia în considerare posibilitatea apariției defectelor în sistem.
Exemplu:
Fie tranzacțiile:
T1: READ(x) T2: WRITE(x) T3: READ(x)
WRITE(x) WRITE(y) READ(y)
COMMIT READ(z) READ(z)
COMMIT COMMIT
O posibilă planificare completă, Pc, a celor trei tranzacții este dată prin graful aciclic din figura 2.4:
R1(x) W2(x) R3(x) R1(x) W2(x) R3(x)
W1(x) W2(y) R3(y) W2(y) R3(y)
C1 R2(z) R3(z) R2(z) R3(z)
C2 C3
Fig.2.4. O posibilă planificare completă Fig.2.5. O posibilă planificare completă
a tranzacțiilor T1,T2 și T3 a tranzacțiilor T1,T2 și T3
O posibilă planificare P, prefix al lui Pc, este dată prin graful aciclic din figura 2.5.
Așa cum s-a arătat, o planificare P este serială dacă pașii tranzacțiilor componente nu sunt intercalați. O planilicare serială menține consistența bazei de date deoarece, conform proprietății de consistență a tranzacțiilor, orice tranzacție executată independent pe o bază de date consistentă va produce o bază de date tot consistentă. Deci o planificare serială în care tranzacțiile sunt executate pe rând, una câte una, va lăsa baza de date într-o stare consistentă dacă, bineînțeles, starea inițială a bazei de date a fost una consistentă.
Pornind de la relația de precedență, introdusă prin relația de ordine parțială, este posibilă definirea echivalenței planificărilor pe baza efectelor acestora asupra bazei de date. Intuitiv, două planificări P1 și P2, definite peste același set de tranzacții T, sunt echivalente dacă au același efect asupra bazei de date. Formal, două planilicări P1 și P2, definite peste același set de tranzacții T, sunt echivalente dacă pentru orice pereche de operații conflictuale Oij și Okl (i≠k), avem:
Oij <1 Okl Oij <2 Okl.
Această formă de echivalență poartă numele de echivalență la conflict fiind definită pe baza ordinii relative de execuție a operațiilor conflictuale.
Exemplu:
Fie tranzacțiile T1, T2 și T3 din exemplul precedent, atunci planificările P1 și P2 definite prin:
P1 = W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3,
P2 = W2(x), R1(x),W1(x),R3(x),C1,W2(y),R3(y),R2(z),C2,R3(z),C3,
sunt echivalente la conflict, deoarece pentru fiecare pereche de operații conflictuale ordinea relativă de execuție este aceeași în ambele planificări. Într-adevăr perechile de operații conflictuale sunt:
(W2(x), R1(x)); (W2(y), R3(y));
(W2(x), W1(x)); (R1(x), W1(x));
(W2(x), R3(x)); (W1(x), R3(x)),
iar ordinea relativă de execuție este cea care apare în aceste perechi, atât pentru planificarea P1, cât și pentru P2.
Echivalența la conflict permite definirea formală a conceptului de serializabilitate. O planificare P este serializabilă dacă și numai dacă este echivalentă la conflict cu o planificare serială. Această formă de serializabilitate poartă numele de serializabilitate bazată pe conflict.
Planificarea P1 din exemplul de mai sus este serială deoarece constă din execuția pe rând a tranzacțiilor componente, în ordinea: T2T1T3. Planificarea P2 este serializabilă datorită faptului că este echivalentă la conflict cu planificarea P1.
Conceptul de serializabilitate permite definirea mai clară a obiectivelor urmărite prin controlul concurenței. Funcția principală a oricărui mecanism de control al concurenței este de a genera o planificare serializabilă pentru execuția tranzacțiilor active din sistem. Problema principală care se pune în domeniul controlului concurenței este de a dezvolta algoritmi care garantează faptul că orice planificare pe care o produc este serializabilă.
3.6 Algoritmi de control al concurenței în bazele de date centralizate
Există mai multe criterii după care se pot clasifica algoritmii de control al concurenței. Criteriul cel mai adesea folosit este cel al primitivei de sincronizare care stă la baza fiecărei clase de algoritmi. Conform acestui criteriu algoritmii de control al concurenței se împart în:
algoritmi de control al concurenței prin blocare
Se bazează pe accesul mutual cxclusiv al tranzacțiilor la datele partajate; excluderea mutuală este asigurată prin primitive de tip LOCK și UNLOCK.
algoritmi de control al concurenței prin mărci de timp
Încearcă să ordoneze execuția tranzacțiilor conform unui set de reguli; ordonarea tranzacțiilor este asigurată prin mărci de timp asociate atât tranzacțiilor, cât și datelor pe care le accesează.
Un alt criteriu de clasificare al algoritmilor de control al concurenței este după mediul in care acționează aceștia: baze de date centralizate sau distribuite. În acest subcapitol vom trece în revistă principalii algoritmi de control al concurenței utilizați in bazele de date centralizate.
Algoritmi de control al concurenței prin blocare
Algoritmii de control al concurenței prin blocare își propun prevenirea executării unor secvențe incorecte de operații prin punerea în așteptare a tranzacțiilor care execută operații conflictuale. Aceasta se realizează prin folosirea primitivelor LOCK și UNLOCK. Simpla folosire a acestor primitive nu este însă suficientă pentru a obține execuții serializabile ale seturilor de tranzacții. Pentru acesta este nevoie de mecanisme de control suplimentare sau de restricții suplimentare care să elimine planificările neserializabile, forțând setul de tranzacții să se execute sub forma unei planificări serializabile. Serializabilitatea poate fi asigurată prin impunerea unor restricții asupra structurii interne a tranzacțiilor, deci în ce privește secvența de pași pe care o tranzacție are voie să o execute. Un set de asemenea restricții poartă numele de protocol. Orice protocol care asigură serializabilitatea constituie un algoritm de control al concurenței.
În cazul folosirii primitivelor de blocare apare o problemă suplimentară și anume aceea a interblocărilor. Orice tranzacție care solicită o resursă care momentan nu este disponibilă, deoarece este blocată de o altă tranzacție, va fi pusă în așteptare până la eliberarea resursei. Dacă, la un moment dat sunt puse în așteptare mai multe tranzacții simultan, atunci este posibilă formarea unui lanț circular de așteptare în care fiecare tranzacție blochează niște resurse, dar nu poate, în nici un fel, să-și continue execuția deoarece nu poate obține celelalte resurse de care are nevoie. O asemenea situație se cere a fi tratată prin metode specifice care vor fi prezentate în subcapitolul 3.7. În cele ce urmează presupunem că este activ unul din algoritmii de prevenire, evitare sau eliminare a interblocărilor. Obiectivul urmărit în continuare este asigurarea serializabilității pentru un set de tranzacții concurente fără a mai lua în considerare problema interblocării.
Din punctual de vedere al algoritmilor de control al concurenței prin blocare prezintă interes acei pași din cadrul tranzacțiilor care corespund operațiilor de tip blocare și deblocare. În consecință tranzacțiile vor fi privite ca secvențe de operații LOCK și UNLOCK. De asemenea presupunem că sunt respectate următoarele reguli:
1. Orice unitate de acces care este la un moment dat blocată (prin LOCK) de o tranzacție, trebuie să fie ulterior deblocată (prin UNLOCK) de aceeași tranzacție.
2. O tranzacție nu încearcă să blocheze blochează deja.
3. O tranzacție nu încearcă să deblocheze altă tranzacție.
La regulile de mai sus se adaugă restricțiile care derivă direct din definiția primitivelor LOCK și UNLOCK. O unitate de acces poate fi la un moment dat blocată de către o singură tranzacție care are accesul exclusiv la această unitate. Orice altă tranzacție care dorește accesul la aceeași unitate trebuie să aștepte deblocarea acesteia de către tranzacția care a blocat unitatea.
O planiticare a două sau mai Mite tranzacții care respectă regulile de mai sus este considerată legală.
Exemplu:
Fie tranzacțiile:
T1: LOCK A; LOCK B; UNLOCK A; UNLOCK A
T2: LOCK A; UNLOCK A;
și următoarea planificare:
T1 T2
LOCK A;
LOCK B;
LOCK A;
UNLOCK A;
UNLOCK A;
UNLOCK B;
Această planificare este ilegală deoarece este imposibil ca tranzacția T2 să obțină blocarea valorii A atâta timp cât aceasta este blocată de către tranzacția T1, deci operația LOCK A din T2 nu poate fi situată în timp între operațiile LOCK A și UNLOCK A din T1. De asemenea T2 nu poate debloca valoarea A atâta timp cât aceasta este blocată de către T1.
Algoritm de testare a serializabilității
Acest algoritm ne permite să stabilim dacă o anumită planificare a unui set de tranzacții este sau nu serializabilă, deci dacă există sau nu o planificare serială echivalentă cu planificarea dată. Esența algoritmului constă în a examina ordinea în care diferitele tranzacții blochează fiecare unitate de acces în cadrul planificării date. Ordinea în care tranzacțiile din planificarea dată blochează o anumită unitate de acces determină ordinea de blocare a acestei unități de acces de către tranzacțiile din planificarea serială echivalentă. Dar într-o planificarea serială toate unitățile de acces sunt blocate în aceeași ordine care nu este alta decât ordinea de execuție serială a tranzacțiilor. Dacă o altă unitate de acces impune o ordonare a tranzacțiilor diferită de prima, atunci se ajunge la o situație de paradox, în care o anumită tranzacție din planificarea serială ar trebui concomitent să preceadă, dar să și urmeze unei alte tranzacții. Aceasta nu înseamnă altceva decât că nici o planificare serială nu poate fi echivalentă cu planificarea dată, adică planificarea dată nu este serializabilă.
Algoritmul de testare a serializabilității se poate exprima ca o problemă de găsire a ciclurilor dintr-un graf orientat numit graful de precedență. Fiind dată o planificare P a unei mulțimi de tranzacții M se construiește graful de precedență asociat astfel:
Nodurile grafului sunt tranzacțiile din M.
Arcul orientat de la nodul Ti la nodul Tj, TiTj, are semnificația că există o unitate de acces pentru care tranzacția Ti obține blocarea (pereche LOCK-UNLOCK) înaintea tranzacției Tj, iar între Ti și Tj nici o altă tranzacție nu blochează această unitate de acces.
Arcul TiTj arată că în orice planificare serială echivalentă cu planificarea inițială P, tranzacția Ti se execută înaintea tranzacției Tj. Este deci evident că dacă în graful de precedență există un ciclu care include tranzacțiile Ti și Tj, atunci în planificarea serială echivalentă tranzacția Ti se execută atât înaintea tranzacției Tj cât și după. Acest lucru este imposibil într-o planificare serială, deci nu poate exista o planificare serială echivalentă cu planificarea dată.
Dacă graful de precedență nu are cicluri, atunci există o planificare serială echivalentă și se poate determina o ordonare a tranzacțiilor astfel încât Ti se execută înaintea lui Tj dacă există un arc TiTj. Această ordonare se determină prin algoritmul de sortare topologică definit astfel:
1. Dacă graful de precedență nu are, cicluri , atunci există un nod care nu este extremitate a nici unui arc. În caz contrar se poate demonstra că graful are cicluri. Se localizează acest nod, se elimină din graf împreună cu arcele adiacente, iar tranzacția corespunzătoare se trece în lista de tranzacții a planificării seriale.
2. Se reia pasul 1) până la epuizarea tuturor nodurilor.
Ordinea do eliminare a nodurilor din graful de precedență este chiar ordinea de execuție a tranzacțiilor in planificarea serială.
Exemple:
Fie tranzacțiile T1, T2, T3 și următoarea planificare:
T1 T2 T3
LOCK A;
LOCK B;
UNLOCK B;
LOCK B;
UNLOCK A;
LOCK A;
UNLOCK A;
LOCK A;
UNLOCK B;
UNLOCK A;
Construim graful de precedență asociat acestei planificări. Nodurile sunt T1, T2 și T3. Avem arcele T1T2 și T2T3 deoarece tranzacțiile blochează unitatea A în ordinea T1, T2, T3. Mai apare arcul T2T1 ca o consecință a ordinii de blocare asupra unității B. Graful de precedență este prezentat în figura 3.6.
Fig. 3.6. Graf de precedență pentru o planificare neserializabilă
Se observă existența unui ciclu conținând nodurile T1 și T2, ceea ce înseamnă că planificarea dată nu este serializabilă. O planificare serială echivalentă ar trebui să execute tranzacția T1 înainte de T2, dar și pe T2 înainte de T1, ceea ce este imposibil.
Fie planificarea:
T1 T2 T3
LOCK A;
UNLOCK A;
LOCK A;
UNLOCK A;
LOCK B;
UNLOCK B;
LOCK B;
UNLOCK B;
Graful de precedență are nodurile T1, T2, T3 și conține arcele T2T3 (determinat de accesul la A) și T1T2 (determinat de accesul la B}. Graful nu are cicluri, deci planificarea este serializabilă, iar planificarea serială echivalentă este T1, T2, T3. De remarcat că deși în realitate tranzacția T3 se execută înainte de T1, în planificarea serială echivalentă T1 precede T3.
Algoritmul de testare a serializabilității bazat pe detectarea ciclurilor din graful de precedență poate fi folosit, cel puțin teoretic, pentru elaborarea unui mecanism general de control a concurenței. Aceasta ar presupune construirea dinamică a grafului de precedență și verificarea la fiecare pas a ciclicității sale. În cazul apariției unui ciclu ar urma abortarea a cel puțin uneia dintre tranzacțiile vinovate de apariția ciclului în graful de precedență. Metoda aceasta s-a dovedit a fi însă neviabilă în practică datorită costurilor mari pe care le implică. Ori nu este permis ca metoda de control a concurenței să implice costuri suplimentare care să depășească câștigul obținut datorită execuției concurente. Execuția concurentă a tranzacțiilor, împreună cu costurile suplimeratare implicate de controlul concurenței, trebuie să fie, în orice situație, cel puțin la fel de eficientă ca și execuția serială a acelorași tranzacții. Din acest motiv este preferată o altă abordare a problemei controlului concurenței și anume aceea de a impune asupra tranzacțiilor suficiente restricții astlel încât nici o planificare posibilă a acestora să nu violeze condiția de serializabilitate. Aceste restricții, numite protocoale, reduc nivelul de concurență al sistemului, prin faptul că admit doar un subset al planificărilor serializabile posibile pentru o mulțime dată de tranzacții.
Protocol pentru asigurarea serializabilității
Cel mai simplu protocol care asigură serializabilitatea unei mulțimi de tranzacții este protocolul în două faze se poate formula astfel:
În orice tranzacție toate operațiile de blocare se execută înaintea oricărei operații de deblocare.
Așadar nu este permisă intermixarea operațiilor de blocare și deblocare în cadrul tranzacțiilor. Tranzacțiile care respectă acest protocol execută întâi toate operațiile de blocare de care au nevoie, urmează apoi operațiile propriu-zise specifice fiecărei tranzacții, iar în final se execută operațiile de deblocare. Distingem deci două faze de execuție care sunt comune tuturor tranzacțiilor din această categorie: faza de acaparare a tuturor resurselor necesare (blocările) și faza de eliberare a acestora (deblocările). Aceste tranzacții poartă numele de tranzacții în două faze. Se poate enunța urmatoarea teoremă:
TEOREMĂ:
Orice planificare legală a unei mulțimi de tranzacții în două faze este serializabilă.
Demonstrație:
Prin reducere la absurd. Presupunem că există o planificare a unui set de tranzacții în două faze care nu este serializabilă. Atunci graful de precedență corespunzător acestei planificări conține un ciclu: …–>`h;. Înseamnă că există o operație de blocare în Tj care este situată după o operație de deblocare din Ti; în Tk există o blocare care urmează unei deblocări din Tj ș.a.m.d. În final rezultă că Ti conține o operație de blocare situată după o operație de deblocare din cadrul ei, ceea ce contrazice ipoteza că Ti este în două faze.
Trebuie menționat faptul că acesta este singurul protocol cu caracter general care asigură serializabilitatea. Cu alte cuvinte se poate arăta ca dacă T1 este o tranzacție care nu este în două faze, atunci se poate găsi o tranzacție T2 astfel încât pentru T1 și T2 există o planificare care nu este serializabilă. Fie deci T1, care nu este în două faze, atunci va exista o operație de deblocare UNLOCK A care precede o operație de blocare LOCK B. Fie T2 tranzacția:
T2: LOCK A; LOCK B; UNLOCK A; UNLOCK B;
și următoarea planificare:
T1 T2
LOCK A;
UNLOCK A;
LOCK A;
LOCK B;
UNLOCK A;
UNLOCK B;
LOCK B;
NLOCK B;
al cărui graf de precedență este cel din figura 3.8., unde se poate observa că planificarea nu este serializabilă.
Fig. 3.8. Graful de precedență: ciclic corespunzător unei
planificări neserializabile
Menționăm faptul că există totuși mulțimi particulare de tranzacții, dintre care unele nu sunt în două faze, dar care au proprietatea că orice planificare legală a lor este și serializabilă.
Tranzacții cu accese de tip read-only și read-write
În cele de mai sus s-a considerat în mod implicit că o tranzacție care blochează o unitate de acces modifică una sau mai multe valori din cadrul acestei unități, cu alte cuvinte s-a considerat că accesele sunt de tipul read-write. În practică însă, sunt foarte frecvente tranzacțiile care fac acces la date doar pentru consultarea acestora; este cazul tuturor tranzacțiilor care compun interogările adresate bazelor de date. Despre aceste tranzacții se știe dinainte că vor accesa datele doar în citire fără a face modificări asupra lor. Dar pentru efectuarea operațiilor de citire nu este obligatorie excluderea mutuală, aceeași dată poate fi citită de către mai multe tranzacții în mod concurent fără ca acestea să se influențeze reciproc, ordinea citirilor fiind arbitrară. Este, deci, util să se facă distincție între accesele numai pentru citire (read-only) și cele pentru citire-scriere (read-write), deoarece astfel se pot formula protocoale care permit un grad mai ridicat de concurență a operațiilor. Într-un sistem care face această distincție se folosesc două primitive de blocare:
1. RLOCK – cerere de blocare pentru citire (read-lock) numită și cerere dc blocare partajată (shared-lock). Este folosită de tranzacțiile care doresc accesul la o valoare doar pentru operații de citire. Dacă o tranzacție blochează în citire o unitate dc acces, atunci nici o altă tranzacție nu poate obține blocarea în scriere a acestei unități de acces, dar oricâte tranzacții pot obține în acest timp blocarea în citire a aceleiași unități de acces.
2. WLOCK – cerere de blocare pentru citire-scriere (read-write lock) numită și cerere de blocare exclusivă (exclusive-lock). Este folosită de către tranzacțiile care doresc, eventual, modificarea unor valori din cadrul unității de acces și este echivalentă cu primitiva LOCK discutată în paragrafele precedente. Dacă o tranzacție blochează în citire-scriere o unitate de acces, atunci nici o altă tranzacție nu poate obține blocarea acestei unități nici pentru citire, nici pentru citire-scriere.
Atât blocările pentru citire, cât și cele pentru citire-scriere sunt anulate prin executarea primitivei UNLOCK.
O planificare a pașilor unei mulțimi de tranzacții care conțin primitive RLOCK și WLOCK este legală, dacă sunt respectate următoarele reguli:
1. Orice unitate de acces blocată de o tranzacție trebuie să fie deblocată de aceeași tranzacție înainte de terminarea acesteia.
2. Nici o tranzacție nu încearcă deblocarea unei unități de acces pe care nu o blochează în citire sau citire-scriere.
3. Nici o tranzacție nu încearcă blocarea pentru citire a unei unități de acces pe care o blochează (fie în citire, fie în citire-scriere).
4. Nici o tranzacție nu încearcă blocarea pentru citire-scriere a unei unități de acces pe care o blochează în citire-scriere.
5. O tranzacție poate cere și obține blocarea pentru citire-scriere a unei unități de acces pe care o blochează deja în citire. Această situație este posibilă deoarece blocarea în citire-scriere este mai restrictivă decât blocarea doar pentru citire.
Două planificări ale unei mulțimi de tranzacții care conțin primitivele RLOCK și WLOCK sunt echivalente dacă:
1. Produc aceeași valoare finală pentru toate datele accesate.
2. Valorile datelor asupra cărora se execută o primitivă RLOCK sunt aceleași în ambele planificări (cu alte cuvinte valorile citite de diferitele tranzacții sunt aceleași pentru ambele planificării).
Algoritmul dc testare a serializabilității pentru o planificare a unui set de tranzacții care efectuează asupra datelor accese de tip read-only sau read-write este asemănător cu algoritmul prezentat pentru cazul acceselor de tip read-write. Deosebirea provine din faptul că, spre deosebire de accesele de tip read-write a căror ordine de execuție nu este indiferentă, operațiile de tip read-only sunt permutabile, deci ordinea lor de execuție nu influențează rezultatele. De asemenea nu putem permuta un acces de tip read-only cu unul de tip read-write sau invers. Așadar în stabilirea serializabilității unei planificări vom ține seama de ordonarea relativă a următoarelor cupluri de accese: read-write cu read-write, read-only cu read-write și read-write cu read-only. Ordinea relativă a două accese de tip read-only este arbitrară.
Pornind de la aceste observații arcele grafului de precedență G sunt determinate pe baza următoarelor reguli. Fie Ti și Tj două noduri ale lui G; gralul G va conține un arc TiTj dacă:
1. 'I'i blochează în citire-scriere unitatea A, iar Tj este prima tranzacție care blochează în citire-scriere aceeași unitate de acces dupa Ti.
2. Ti blochează în citire unitatea A, iar Tj este prima tranzacție care blochează în citire-scriere unitatea A dupa Ti.
3. Ti blochează în citire-scriere unitatea A, iar Tj este oricare dintre tranzacțiile care blochează în citire unitatea A după Ti.
Între nodurile Ti și Tj nu se trasează nici un arc dacă tranzacția Ti blochează unitatea A în citire urmată de tranzacția Tj care blochează unitatea A tot în citire.
Dacă graful G conține cel puțin un ciclu, atunci planificarea corespunzătoare acestui graf nu este serializabilă. Dacă graful G este aciclic, atunci prin sortare topologică se determină o ordine serială a tranzacțiilor echivalentă cu planificarea dată.
Exemple:
1. Fie mulțimea de tranzacții {T1,T2,T3,T4} și următoarea planificare a acesteia:
T1 T2 T3 T4
WLOCK A;
RLOCK B;
UNLOCK A;
RLOCK A;
UNLOCK B;
WLOCK B;
RLOCK A;
UNLOCK B;
WLOCK B;
UNLOCK A;
UNLOCK A;
WLOCK A;
UNLOCK B;
RLOCK B;
UNLOCK A;
UNLOCK B;
Dorim să stabilim dacă planificarea este sau nu serializabilă. Pentru aceasta construim graful de precedență, corespunzător acestei planificări.
Tranzacția T1 blochează valoarea B în citire-scriere, urmată de tranzacția T2, care blochează valoarea B în citire, deci graful de precedență va conține arcul T1T2.
Tranzacția T1 blochează valoarea A în citire, iar tranzacția care îi urmează este T4 care blochează valoarea A în citire-scriere, deci graful de precedență va conține arcul T1T4.
Similar, T2 blochează A în citire, urmată de T4, care blochează A în citire-scriere, rezultă T2T4.
T3 blochează A în citire-scriere, urmată de T1 și T2 care blochează A
în citire, rezultă T3T1 și T3T2.
T4 blochează B în citire, urmată de T3 care blochează B în citire-scriere, rezultă T4T3.
Fig. 3.9. Graful de precedență conținc ciclul: T1-T4-T3-T1
Graful de precedență este corespunzător planificării de mai sus este prezentat în figura 3.9. și se observă că acesta conține mai multe cicluri: T1-T4-T3-T1, T2-T4-T3-T2, T1-T2-T4-T3-T1 ș.a. Rezultă că planificarea dată nu este serializabilă.
2. Fie mulțimea de tranzacții {T1,T2,T3,T4} și următoarea planificare a acesteia:
T1 T2 T3 T4
RLOCK A;
UNLOCK A;
RLOCK A;
RLOCK B;
RLOCK B;
UNLOCK B;
UNLOCK A;
UNLOCK B;
WLOCK A;
UNLOCK A;
WLOCK B;
UNLOCK B;
WLOCK A;
UNLOCK A;
Construim graful de precedență corespunzător acestei planificări.
T1 blochează A în citire, urmată de T2 care blochează A în citire-scriere, rezultă T1T4.
Similar T3 blochează A și B în citire, înaintea blocărilor pentru citire-scriere de către T2, respectiv T4, rezultă arcele T3T2 și T3T4.
T2 blochează A în citire-scriere, înaintea lui T4, care blochează A tot în citire-scriere, rezultă T2T4.
Determinarea unei planificări seriale echivalente se realizează prin algoritmul de sortare tolologică. Etapele sortării sunt:
1. Se caută un nod care nu este extremitatea nici unui arc. În cazul de față există două noduri T1 și T3. Alegem T1.
2. Se elimină nodul T1 din graf împreună cu arcele adiacente: T1T2 și T1T4.
3. În graful rămas singurul nod care nu este în extremitatea unui arc este T3. Se elimină nodul T3 împreună cu arcele: T3T2 și T3T4.
4. În graful rămas singurul nod care nu este în extremitatea unui arc este T2. Se elimină nodul T2 și arcul T2T4.
5. Singurul nod rămas este T4 care este ultimul eliminat.
Ordinea de eliminare a nodurilor din graful de precedență este: T1, T3, T2 și T4, ceea ce constituie o posibilă planificare serială echivalentă cu planificarea dată.
Alegând în pasul 1) nodul T3 în loc de T1 se obține o a doua planificare serială echivalentă: T3, T1, T2, T4.
Asigurarea serializabilității oricărei planificări posibile pentru o mulțime de tranzacții cu accese de tip read-only sau read-write este garantată prin folosirea unui protocol în două faze. Așadar orice set de tranzacții care satisfac condiția că execută primitivele RLOCK și/sau WLOCK înaintea oricărei execuții a unei primitive UNLOCK are proprietatea că orice planificare a acesteia este serializabilă.
Reciproc, pentru orice tranzacție T1 care conține o primitivă UNLOCK care precede o primitivă RLOCK sau WLOCK există o tranzacție T2, astfel încât setul de tranzacții {T1,T2} are cel puțin o planificare neserializabilă.
Protocoale conservative și protocoale agresive
Restricțiile impuse tranzacțiilor de protocolul în două faze garantează serializabilitatea planificărilor și totodată lasă libertatea mai multor opțiuni în organizarea pașilor unei tranzacții, ceea ce conduce la mai multe versiuni ale acestui protocol. Există două variante extreme ale protocolului în două faze:
Protocoale conservative
Se caracterizează prin faptul că fiecare tranzacție emite toate cererile de blocare la începutul execuției sale. Dacă aceste cereri pot fi satisfăcute, atunci tranzacția este lansată în execuție, iar în caz contrar este pusă într-o coadă de așteptare. După cum se va vedea acest protocol previne apariția interblocărilor, dar reduce nivelul de concurență al sistemului.
Protocoalele conservative au o serie de dezavantaje printre care și producerea fenomenului de "înfometare" a tranzacțiilor. Acesta poate fi prevenit dacă se respectă anumite reguli în satisfacerea cererilor de blocare. O tranzacție T poate obține blocările solicitate și intră în execuție dacă și numai dacă:
a. Toate unitățile de acces pe care T dorește să le blocheze sunt deblocate.
b. Nici o altă tranzacție, aflată în coada de așteptare, nu solicită blocarea unei unități de acces solicitate de T.
O altă dificultate, legată de folosirea unui protocol conservativ, apare în cazul unor tranzacții care necesită blocarea unui subset de tuple satisfăcând o anumitiă condiție (bIocări cu predicat). Mai mult, uneori această condiție ar putea fi determinată doar în mod dinamic, în timpul execuției tranzacției, ceea ce înseamnă că subsetul de tuple care se cere a fi blocat nu este cunoscut la începutul execuției tranzacției.
Exemplu:
Fie interogarea: “Disciplinele la care studiază studentul Lupu?” cu echivalentul său în SQL:
SELECT Profesori.Disciplina
FROM Profesori,Note
WHERE Profesori.Nume=Note.Note_prof
AND Note.Nume_stud=Lupu
Strategia cea mai eficientă pentru interogarea de mai sus constă în selectarea din relația Note a tuplelor pentru care Nume_stud='Lupu' și cuplarea acestora cu relația Profesori. În ipoteza că există indecși pe câmpurile Note.Nume_stud, respectiv Profesori. Disciplină și că blocările se fac dinamic, în timpul execuției interogării, doar o fracțiune din relațiile Profesori și Note ar trebui blocate. Folosind un protocol conservativ întreaga relație Profesori va trebui blocată, deoarece nu se pot cunoaște anticipat tuplele care vor fi implicate în interogare, acestea fiind determinate în timpul prelucrării.
Protocoale agresive
Se caracterizează prin faptul că fiecare cerere de blocare este emisă doar în momentul când se dorește o scriere sau o citire în/din unitatea de acces corespunzătoare. Prin acest protocol blocarea fiecărei unități de acces este amânata până în ultimul moment ceea ce conduce la un nivel mai ridicat de concurență al sistemului. Din păcate acest protocol nu previne apariția interblocărilor. În cazul folosirii unui protocol agresiv problema interblocărilor poate fi tratată în două moduri:
• printr-o metodă de detecție și ieșire din interblocare, ceea ce presupune operații costisitoare de abortare și reluare a tranzacțiilor;
• prevenind interblocarea prin metoda ordonării, care are o aplicabilitate limitată și o serie de alte dezavantaje care vor fi discutate în detaliu odată cu prezentarea metodei.
Alegerea uneia sau alteia dintre variantele de protocol în două faze depinde de natura unităților de acces și a tranzacțiilor din sistem. Dacă probabilitatea ca două tranzacții să solicite blocarea aceleiași unități de acces este mică, atunci riscul apariției unei interblocări este redus, deci este preferabil un protocol agresiv care asigură un grad de concurență ridicat al sistemului. Abortarea tranzacțiilor va fi un eveniment rar al cărui cost nu va afecta simțitor performanța sistemului. În schimb, dacă probabilitatea apariției situațiilor de interblocare este ridicată, atunci un protocol prea agresiv reduce mult șansele oricărei tranzacții de a se termina fără a fi abortată. Abortările vor fi dese, iar costul lor va depăși câștigul datorat gradului sporit de concurență. În acestă situație se va prefera un protocol conservativ.
3.7. Gestiunea interblocărilor în bazele de date centralizate
Una dintre principalele obiective ale oricărui sistem concurent este folosirea în comun a resurselor, adică partajarea acestora. Interblocarea este un fenomen care poate să apară în orice sistem care permite utilizarea partajată a unor resurse. Ea are un caracter permanent și odată apărută nu poate fi eliminată decât printr-o intervenție din exterior. Această intervenție poate veni din partea utilizatorului, a operatorului sistem sau din partea unui modul software specializat în acest scop (parte a sistemului de operare sau a sistemului de gestiune al bazei de date).
În cazul bazelor de date concurente cea mai importantă resursă partajabilă sunt însăși datele. Așa cum s-a arătat, în bazele de date cu acces concurent interblocarea poate să apară în cazul folosirii algoritmilor de control al concurenței prin blocare datorită accesului mutual exclusiv al tranzacțiilor la datele partajate. Atunci când datele sunt partajate de către un grup de tranzacții concurente și fiecare tranzacție deține controlul exclusiv a1 unor date particulare este posibil să se ajungă la situații în care unele tranzacții nu-și vor putea termina execuția niciodată.
Fie două tranzacții T1 și T2 definite prin două secvențe de forma:
T1 T2
WHILE NOT(LOCK(A)); WHILE NOT(LOCK(B));
WHILE NOT(LOCK(B)); WHILE NOT(LOCK(A));
..………….. ………………….
{prelucrare 1} {prelucare2}
…………… …………………
UNLOCK(A); UNLOCK(B);
UNLOCK(B); UNLOCK(A);
Presupunem că tranzacțiile T1 și T2 își încep execuția aproximativ în același timp. T1 cere și obține blocarea lui A, iar T2 cere și obține blocarea lui B. Apoi T1 cere blocarea lui B, dar este pusă în așteptare deoarece unitatea de acces B este blocată de către tranzacția T2. Concomitent T2 cere blocarea lui A și este pusă în așteptare până când T1 deblochează pe A. Dar T1 așteaptă deblocarea lui B de către T2. În consecință nici una dintre tranzacții nu-și poate continua execuția, ambele fiind puse în așteptare până la nesfârșit. O asemenea situație poartă numele de interblocare (deadlock).
Într-o situație de interblocare pot fi implicate un număr mai mare de tanzacții care se așteaptă reciproc. Interblocarea constituie o problemă comună tuturor sistemelor concurente și se folosesc mai multe metode pentru rezolvarea ei. Aceste metode pot fi împărțite în trei clase:
– metode de prevenire a interblocării;
– metode de evitare a interblocării;
– metode de detecție și ieșire din interblocare.
Metode de prevenire a interblocării
Strategia metodelor de prevenire a interblocării constă în a proiecta în așa fel sistemele concurente încât să fie exclusă a priori posibilitatea aparitiei unei interblocări. Într-o bază de date cu acces concurent poate să apară o situație de interblocare numai dacă sunt satisfăcute simultan următoarele 4 condiții:
1. Condiția de excludere mutuală (mutual exclusion) – tranzacțiile solicită controlul exclusiv al unităților de acces asupra cărora optează.
2. Condiția de așteptare pentru (wait for) – o tranzacție care deține controlul exclusiv asupra unor unități de acces este în așteptare pentru altele.
3. Condiția de completare (completion) – nici o unitate de acces nu poate fi deblocată de către tranzacția care o controlează înainte ca aceasta să termine toate operațiile pe care le are de executat asupra unității respective.
4. Condiția de așteptare circulară (circular wait) – există un lanț circular de tranzacții cu proprietatea că fiecare tranzacție deține controlul asupra unei unități de acces solicitată de următoarea tranzacție din lanț.
Nesatisfacerea oricăreia dintre cele 4 condiții de mai sus face imposibilă interblocarea, deci, în principiu, negarea fiecărei condiții ar putea sta la baza unei metode de prevenire a interblocării.
Negarea condiției 1) conduce la observația trivială că nu poate apare interblocare în cazul tranzacțiilor care nu solicită accesul exclusiv la unitățile de acces. Deci în cazul execuției concurente al unei set de tranzacții care efectuează numai operații de citire nu poate apare interblocare.
Negarea condiției 2) conduce la o metodă de prevenire a interblocării care are la bază alocarea unităților de acces după principiul "totul sau nimic", numită și metoda cererilor anticipate.
Negarea condiției 3) ar implica posibilitatea că o tranzacție să poată debloca temporar o unitate de acces solicitată de către o altă tranzacție, urmând ca ulterior să o blocheze din nou. Acest lucru este inacceptabil în cazul tranzacțiilor deoarece a doua tranzacție ar fi putut modifica unitatea de acces în cauză, ceea ce conduce la execuții neserializabile. În principiu, tranzacțiile nu-și pot elibera resursele înainte de a fi efectuat toate operațiile asupra acestora (excepție fac situațiile de abortare care, însă, presupun reluarea de la început a tranzacției abortate). Spunem că tranzacțiile trebuie să satisfacă condiția de completare sau că sunt non-preemptive.
Prevenirea interblocării prin negarea condiției 3) este practică în cazul acelor resurse a căror stare poate fi ușor salvată și restaurată ulterior. Este folosită în sistemele de operare în cazul unor resurse cum ar fi memoria sau unitatea centrală.
Negarea condiției 4) conduce la o metodă de prevenire a interblocării bazată pe ordonarea unităților de acces numită metoda ordonării.
Metode de evitare a interblocării
Metodele de prevenire a interblocării introduc restricții a priori asupra accesului la resurse prevenind astfel satisfacerea a cel puțin uneia dintre cele 4 condiții necesare apariției interblocării. Aceste restricții sunt permanente, statice, iar respectarea lor este impusă chiar și atunci când s-ar putea să nu apară interblocări. Acest fapt conduce la utilizarea ineficientă a resurselor și, în speță, la reducerea, mai mult decât este necesar, a nivelului de concurență al sistemului. Metodele de evitare a interblocării diferă în mod subtil față de cele de prevenire, prin faptul că nu impun restricții permanente, ci actionează doar în momentul în care apare iminentă producerea unei interblocări. Tipic, interblocarea este evitată prin impiedicarea apariției unui lanț circular de așteptare. Metodele de evitare se bazează pe decizii luate dinamic, în momentul în care se detectează faptul că alocarea unei resurse ar putea conduce la interblocare, fapt pentru care permit un nivel de concurență mai ridicat decât metodele de prevenire.
În cazul sistemelor tranzacționale esența metodelor de evitare constă în a folosi mărcile de timp asociate tranzacțiilor pentru a realiza o prioritate a acestora și de a rezolva interbocările prin abordarea tranzacțiilor în raport cu prioritatea pe care o au (fie pe cele cu prioritate mai mare, fie pe cele cu prioritate mai mică). Pentru aceasta lock manager-ul din sistemul concurent se modifică astfel:
Dacă o cerere de blocare a unei tranzacții Ti nu poate fi satisfăcută, atunci aceasta nu este pusă automat în așteptare. În schimb se verifică dacă tranzacția Ti, împreună cu tranzacția Tj care blochează unitatea de acces solicitată de Ti, pot fi într-un lanț circular de așteptare. Dacă răspunsul este negativ, atunci tranzacției Ti i se permite să aștepte dupa Tj, altfel una dintre tranzacțiile Ti sau Tj este abortată.
Doi dintre algoritmii frecvent utilizați care se bazează pe principiul arătat mai sus, sunt cunoscuți în literatură sub numele de: WAIT-DIE și WOUND-WAIT.
Algoritmul WAIT-DIE
Caracteristic algoritmului WAIT-DIE este faptul că nu va aborta niciodată tranzacția Tj care blochează o resursă solicitată de Ti. Nici o resursă controlată de Tj nu va fi eliberată în mod forțat în scopul alocării unei alte tranzacții care solicită resursa, ceea ce înseamnă că WAIT-DIE este un algoritm nonpreemptiv. Esența algoritmului este definită prin următoarea regulă:
• Dacă o tranzacție Ti solicită blocarea unei unități de acces care este blocată de către Tj, atunci Ti este pusă în așteptare dacă și numai dacă marca sa de timp este anterioară mărcii de timp asociată tranzacției Tj (Ti este mai "bătrână" decât Tj ).
• Dacă Ti este o tranzacție mai "tânără" decât Tj și solicită o resursă a acesteia, atunci Ti va fi abortată și reluată ulterior cu acceași marcă de timp.
Algoritmul WOUND-WAIT
Algoritmul WOUND-WAIT reprezintă versiunea preemptivă a aceluiași principiu care stă la baza algoritmului precedent. În acest caz, atunci când este nevoie, se va aborta tranzacția Tj care blochează o resursă solicitată de Ti. Resursa astfel eliberată se alocă tranzacției Ti. Regula care definește algoritmul este:
Dacă o tranzacție Ti solicită blocarea unei unități de acces care este blocată de către Tj, atunci Ti este pusă în așteptare dacă și numai dacă marca sa de timp este mai recentă decât marca de timp asociată tranzacției Tj (Ti este mai “tânără” decât Tj).
Dacă Ti este o tranzacție mai “bătrână” decât Tj și solicită o resursă a acesteia, atunci Tj va fi abortată, iar resursa se alocă tranzacției Ti. Ulterior tranzacția Tj va fi reluată cu aceeași marcă de timp.
Notând cu m(T) marca de timp a unei tranzacții T, regulile pentru cei doi algoritmi se pot exprima sintetic astfel:
WAIT- DIE: if m(Ti)m(Tj) then Ti așteaptă else abortează Ti;
WOUND-WAIT: if m(Ti) m(Tj) then abortează Tj else Ti așteaptă.
De remarcat faptul că în ambii algoritmi se abortează tranzacția cea mai tânără. De asemenea se poate observa că algoritmul WAIT- DIE favorizează terminarea tranzacțiilor tinere cu resursele deja alocate, în timp ce tranzacțiile mai bătrâne pot fi puse în așteptare atunci când solicită resurse. Aceasta favorizează fenomenul de îmbătrânire al tranzacțiilor, deoarece accesul la resurse al tranzacțiilor bătrâne este mai dificil decât al celor tinere. În schimb algoritmul WOUND-WAIT avantajază tranzacțiile bătrâne care pot elimina tranzacții mai tinere dacă acestea controlează resurse solicitate de primele. Pentru a realize un mecanism de evitare a interblocărilor se poate folosi oricare dintre cei doi algoritmi sau chiar o combinație a lor.
Algoritmii WAIT –DIE și WOUND – WAIT garantează atât evitarea interblocării(deadlock), cât și a reluărilor repetate de tranzacții (livelock), după cum rezultă din următoarea demonstrație.
Demonstrație:
Să presupunem că există un lanț circular de așteptare T1 ,T2 , …Tk , în care fiecare tranzacție Ti așteaptă după o resursă controlată de Ti+1 , pentru orice 1ik, iar Tk așteaptă după T1 . Conform regulilor enunțate pentru cei doi algoritmi mărcile de timp ale tranzacțiilor trebuie să satisfacă relațiile:
m(T1)<m(T2)<…<m(Tk)<m(T1) pentru WAIT-DIE
și
m(T1)>m(T2)>…>m(Tk)>m(T1) pentru WOUND-WAIT.
Evident nici unul dintre seturile de egalități nu poate fi satisfăcut căci ar implica fie m(T1)<m(T1) ori m(T1)>m(T1), ceea ce demonstrează imposibilitatea formării unui lanț circular de așteptare și deci imposibilitatea unei interblocări.
Să arătăm acum că cei doi algoritmi garantează terminarea oricărei tranzacții, adică nu este posibilă reluarea repetată la infinit a nici unei tranzacții.
Fie T cea mai bătrână tranzacție din sistem. Conform regulilor WAIT-DIE și WOUND-WAIT tranzacția T nu mai poate fi abortată- In cel mai rău caz T poate fi pusă în așteptarea unor resurse controlate de tranzactii mai "tinere"(cazul WAIT-DIE). Dar aceste resurse vor fi eliberate, mai devreme sau mai târziu, deoarece în sistem nu pot exista interblocări. Rezultă de aici că până la urmă tranzația T se va termina.
Fie acum "f o tranzacție oarecare. 'I' poate fi abortată din cauza unor tranzacții mai "bătrâne" din sistem care dețin (cazul WAIT-DIE) sau solicită (cazul WOUND-WAIT) resurse solicitate (controlate) de către tranzacția T. Dar conform celor arătate mai sus, aceste tranzacții mai ”bătrâne” se vor termina pe rand și cum T este reluată mereu cu aceeași marcă de timp va deveni în cel mai rău caz, cea mai “bătrână” tranzacție din sistem, caz în care sigur se va termina.
Metodele de evitare a interblocării sunt mai adecvate pentru utilizarea în bazele de date decât metodele de prevenire. Dezavantajul metodelor de evitare constă în timpul suplimentar de execuție necesar pentru operațiile de gestiune posibilelor interblocări. Acest timp contribuie la creșterea timpului mediu de execuție al tranzacțiilor. De asemenea metodele prezentate sunt marcate de fenomenul "abortărilor fantomă". Acest lucru se datorează faptului că testele de abortare din algoritmii WAIT-DIE și WOUND-WAIT reprezintă doar o aproximare a testului de apariție a lanțului circular de așteptare, test care ar fi mult mai costisito. Așadar compromisul făcut în acest caz este de a folosi teste mai simple, dar care pot provoca abortări chiar și atunci când nu este necesar.
Metode de detecție și ieșire din interblocare
Metodele de prevenire sau de evitare a interblocărilor se bazează pe strategii conservative care limitează accesul la resurse sau impun restricții asupra tranzacțiilor. Prin contrast metodele de detecție nu impun nici un fel de restricții în funcționarea sistemului, cererile de resurse fiind satisfăcute ori de câte ori este posibil. Astfel sistemul poate funcționa la nivelul de concurență maxim și fără costuri de execuție suplimentare atâta timp cât nu se detectează nici o interblocare. La apariția unei interblocări (sau a unei situații suspecte de a fi o interblocare) se activează mecanismul de ieșire din interblocare. Rezolvarea situației de interblocare constă, de obicei, în selectarea a una sau mai multe tranzacții "victimă" care vor fi abortate în scopul ruperii lanțurilor circulare de așteptare,
Detectarea situației de interblocare se poate realiza prin mecanisme care sunt fie externe, fie inteme SGBD-ului.
Extern interblocarea poate fi detectată de către un operator uman sau la nivelul sistermului de operare prin utilirzarea unui mecanism de ceas de gardă (time-out) care se fixează la o anumită valoare prestabilită. Astfel orice tranzacție aflată în așteptarea unei resurse pe o durată mai lungă decât cea prestabilită va fi abortată, deoarece este suspectă de implicare într-o interblocare. Această metodă este foarte simplă și larg raspandită în ciuda faptului că determină abortarea și a unor tranzacții care ar putea fi în așteptare din alte motive decât interblocarea. Apare deci și aici fenomenul "abortărilor fantomă". Prin alegerea judicioasă a perioadei de time-out se poate reduce numărul tranzacțiilor abortate în mod inutil, ceea ce diminuează efectele nedorite ale acestui fenomen.
Deși foarte simplu, mecanismul de ceas de gardă se dovedește a fi surprinzător de eficient in practică.În consecință, majoritatea proiectanților de sisteme comerciale au adoptat această tehnică, considerând-nejustifcate eforturile cerute de implementarea unor metode mai sofisticate de detecție a interblocărilor.În plus, mecanismul de ceas de gardă poate fi adaptat la sistemete distribuite fără a necesita modificări esențiale.
Mecanismul intern de detecție a interblocării se bazează pe examinarea cererilor de blocare.Pentru aceasta se construicște un graf de așeptare având în noduri tranzacții și ale cărui arce TiTj semnifică faptul că tranzactia Ti este în așteptare pentru blocarea unei unități de acces care este blocată de Tj. Ciclurile din acest graf indică interblocările. În cazul depistării unei interblocări, cel puțin una dintre tranzacțiile implicate în interblocare trebuie să fie suspendată. Presupunând cunoscut costul suspendării oricăreia dintre tranzacțiile implicate într-o interblocare, se pune problema alegerii subsetului de tranzactii "victimă", a căror abortare minimizează costul întregii operații de ieșire din interblocare. Din păcate s-a demonstrat faptul că accastă problemă este NP-completă, ceea ce înseamnă că nu pot exisla algoritmi eficienți pentru rezolvarea ei. Din acesl motiv, în practica, se recurge la abortarca una câte una a tranzacțiilor "victimă", alegerea urnătoarei tranzacții de abortat făcându-se după o serie de criterii euristice cum ar fi:
Tranzacția care blochează cele mai puține unități de acces; prin aceasta se simplifică operația de abortare;
tranzacția care încă nu a cxecutat nici o actualizare; aceasta simplifică operațiunile de recuperare;
ultima tranzacție care a lansat o cerere de blocare exclusivă; este mare probabilitatea ca aceasta să fie tranzacția vinovată de producerea interblocării;
ultima tranzacție lansată în execuție; s-ar putea ca aceasta să fie într-un stadiu putin mai avansat de execuție, deci pierderile implicate de abortarea sa să fie mai mici fată de alte tranzacții.
Fiecare din strategiile de alegere de mai sus are avantajele și dezavantajele sale. –
Pentru ieșirea dintr-o situație de intrblocare este necesar ca unele dintre tranzacții, cele declorate ca victimă, să elibereze resursele ce le-au fost alocate rupând astfel lanțurile circulare de așteptare. Dar, odată ce o tranzacție eliberează
o unitate de acces, ea nu mai poate obține blocarea vreunei unități de acces fără a viola protocolul în două faze.Pe de altă parte, orice tranzacție implică într-o situație de interblocare este într-o stare în care așteaptă permisiunea de a bloca o unitate de acces. Rezultă că tranzacția victimă, odată ce au fost forțate să-și resursele, nu-și mai pot continua execuția fără a viola protocolul in două faze și deci fără riscul unor execuții neserializabile. Aceasta este de fapt condiția de completare a tranzacțiilor.
Așadar pentru ieșirea din interblocare nu este suficientă eliberarea resurselor deținute de unele tranzacții. Singura alternativă este abortarea completă a tranzacțiilor "victimă".
Operația de abortare a unei tranzacții presupune anularea operațiilor de actualizare pe care deja le-a efectuat (activitate de tip UNDO) și deblocarea unităților de acces blocate. Aceste operații presupun crearea de puncte de reluare cu memorarea periodică (jurnalizarea), într-un fisier special afectat acestui scop (jurnal), a tuturor variabilelor de stare care reflectă atât starea tranzacțiilor cât și a resurselor utilizate (baze de date, unități de acces etc.). Acesta este un proces destul de anevoios și costisitor.
Metodele de detecție și ieșire din interblocare sunt cele mai răspândite și mai bine studiate mecanisme de gestiune a interblocărilor.Ele se dovedesc a fi foarte eficiente în sistemele în care interblocarea este un fenomen rar. Mai mult, există studii statistice care au pus în evidență faptul că majoritatea situațiilor de interblocare implică exact 2 tranzacții, iar interblocările cu lanțuri circulare de 3 sau mai multe tranzacții sunt extrem de rare. Astăzi, majoritatea proiectanților consideră inacceptabilile restricțiile impuse de metodele de prevenire a interblocărilor sau de cele de evitare. Deși aceste metode s-au dovedit utile în alte domenii, de exemplu în sistemele de operare pentru cazul metodelor de prevenire, ele nu prea sunt folosite în sistemele tranzacționale din cauza limitării severe pe care o impun asupra nivelului de concurență. Tranzacțiile au un comportament complex și imprevizibil, în cazul acestora fiind preferate metodele de detecție și ieșire din interblocare, în varianta cea mai simplă, cu folosirea mecanismului de ceas de gardă.
Totuși, pentru sistemele în care probabilitatea interblocărilor este mare, costul operațiilor de ieșire din interblocare poate deveni prohibitiv, ceea cce face mai avantajoasă utilizarea metodelor de prevenire sau de evitare a interblocărilor.
CAPITOLUL IV
ALGEBRĂ RELAȚIONALĂ
Scopul esențial al modelului relațional constă în a manipula date și în particular a le interoga (se vorbește de cereri la bază). În majoritatea sistemelor relaționale, răspunsul la o cerere se obține prin utilizarea unuia sau mai multor operatori relaționali. Mulțimea acestor operatori este definită prin algebra relațională.
Sistemele de baze de date au în vedere trei tipuri de structuri de reprezentare a informațiilor la nivel logic și de operare cu ele, și anume: modelul relațional, modelul rețea și modelul arborescent sau ierarhic. În continuare vom prezenta caracteristicile acestor modele și unele limbaje specifice, cu o mențiune specială pentru SQL, pe care se bazează majoritatea sistemelor de baze de date relaționale folosite în zilele noastre.
În descrierea modelelor vom urmări, pe de o parte, modul de reprezentare a dalelor și relațiilor dintre ele, iar pe de altă parte, operațiile asupra datelor folosite pentru a răspunde la cererile utilizatorilor și alte transformări ce se pot efectua asupra datelor.
Modelul relațional de baze de date
Un model relațional de baze de date cuprinde trei componente principale:
– Structura datelor prin definirea unor domenii (valori atomice) și a relațiilor n-are (atribute, tupluri, chei primare etc.).
– Integritatea datelor prin impunerea unor restricții.
– Prelucrarea datelor prin operații din algebra relațională sau calculul relațional.
Modelul relațional se bazează pe noțiunea matematică de relație, așa cum este definită în teoria mulțimilor, și anume ca o submulțime a produsului cartezian a unei liste finite de mulțimi numite domenii. Elementele unei relații se numesc tupluri, iar numărul de domenii (nu toate distincte) din produsul cartezian se numește aritatea relației. De exemplu, (a1,a2,…,ak) sau, mai pe scurt, a1a2…ak; cu ai din Di pentru orice i=1,…,k reprezintă un tuplu al unei relații de aritate k, în care ai este cel de-al i-lea element al tuplului.
De obicei relațiile sunt reprezentate sub forma unor tabele în care fiecare rând reprezintă un tuplu și fiecare coloană reprezintă valorile tuplurilor dintr-un domeniu dat al produsului cartezian.
În reprezentarea sub formă de tabel a unei relații, coloanelor și, respectiv domeniilor corespunzătoare lor li se asociază nume intitulate atribute. Mulțimea numelor atributelor unei relații se numește schemă relațională. Dacă relația numită R are atributele A1, A2……Ak, atunci schema relațională se notează R(A1,A2……Ak).
Un alt mod de a defini relațaiile este următorul: prin relație înlelegem o mulțime de funcții definite pe o mulțime de atribute cu valori în reuniunea unor domenii, cu restricția ca valoarea corespunzătoare fiecărui atribut să se afle în domeniul asociat acelui atribut.
Trecerea de la un mod de definire al relației la celălalt se face relativ simplu. O relație în sensul de mulțime se transformă într-o relație în sensul de funcții asociind fiecărui domeniu D1,D2,…,Dk al produsului cartezian câte un nume de atribut A1,A2,…,Ak și definind pentru fiecare tuplu ti=(ai1,ai2,…,aik) funcția fi cu fi(Aj)=aij,j=l,…,k.Mulțimea acestor funcții formează o relație în sensul celei de-a doua definiții. Trecerea inversă se face impunând o relație de ordine totală pe mulțimea atributelor și asociind fiecărei functii tuplul obținut din valorile funcției respective, în ordinea corespunzătoare a atributelor.
Din punct do vedere al bazelor de date, cea de-a doua definiție este de preferat deoarece permite prelucrarea informațiilor corespunzătoare unui atribut fără a cunoaște poziția acelui atribut în relație. Aceasta asigură o mai mare independenpță de reprezentare a datelor, atât la nivel logic, cât și la nivel fizic, putându-se efectua modificări în definirea structurilor fără afectarea altor nivele.
Penru relațiile ce constituie o bază de date se fac diferite presupuneri inițiale cum ar fi: neexistența unor tupluri duplicate, neapariția într-o ordine dată a tuplurilor, neapariția într-o ordine dată a atributelor, posibilitatea ca toate atributele să aibă numai valori atomice (nedecompozabile) și altele.
Se numește candidat de cheie a unei relații R coloana sau mulțimea de coloane din R pentru care valorile corespunzătoare din oricare două tupluri nu coincid, deci identifică tuplurile din relația respectivă, și nu conțin strict o submulțime de coloane cu această proprietate. Pentru fiecare relație se alege un candidat de cheie care se numește cheie primară a relației. Tuplurile unei relații nu pot să conțină valoarea nulă în coloane ce aparțin cheii primare. Eventualii candidați de cheie diferiți de cheia primară se numesc chei alternante. Se numește cheie străină o coloană sau o mulțime de coloane a unei relații R1 ale cărei (căror) valori, dacă nu sunt nule, coincid cu valori ale unei chei primare dintr-o relație R nu neapărat distinctă de R1.
Mulțimea tuturor schemelor relaționale corespunzătoare unei aplicații se numește schema bazei de date relaționale, iar conținutul curent al relațiilor la un moment dat se numește bază de date relațională.
În modelul relațional, entitățile sunt reprezentate sub formă de relații în care schema relațională conține toate atributele entității și fiecare tuplu al relației corespunde unui element al entității. La atributele entității se pot adăugă în relație și eventuale atribute suplimentare utilizate pentru exprimarea relațiilor între entități. O relație între entitățile E1, E2,…,Ek se reprezintă ca o relație în care fiecare tuplu (e1,e2,….,ek) este un element al relației inițiale, e1 fiind o cheie pentru relația E1 asociată.
Cele mai multe cereri privesc determinarea unor informații cu anumite proprietăți, iar răspunsul posibil este o relație care descrie toate elementele cu aceste proprietăți. Modul de prezentare al răspunsului depinde de interfața dintre SGBD și utilizator.
Limbaje de prelucrare a datelor pentru modelul relațional
Limbajele de prelucrare a datelor sau, mai pe scurt, limbajele de cereri pentru modelul relațional se pot împărți în două mari categorii:
– limbaje algebrice, în care cererile sunt exprimate prin operatorii pe care trebuie să-i aplicăm relațiilor existente în baza de date pentru a obține răspunsul;
– limbaje cu calculul predicatelor, în care cererile sunt exprimate prin mulțimi de tupluri sau valori pentru care se specifică, sub forma unor predicate, proprietățile pe care trebuie să le îndeplinească.
A doua clasă se divide în două subclase în funcție de obiectele cu care operează predicatele și anume:
– limbaje cu calcul pe tupluri, dacă obiectele primare sunt tupluri;
– limbaje cu calcul pe domenii, dacă obiectele primare sunt domeniile diferitelor atribute ale relațiilor.
Sistemele de gestiune a bazelor de date existente conțin majoritatea operațiilor descrise în continuare pentru unul sau o combinație de limbaje de acest tip. Pot fi implementate și alte operații care permit o mai ușoară utilizare a sistemelor respective, după cum vom vedea în cele ce urmează.
Algebra relațională
Algebra relațională constă dintr-o colecție de operator ce au ca operanzi relații. Rezultatul aplicării unui operator la una sau două relații (în funcție de aritatea acelui operator) este tot o relație.
În cele ce urmează vom presupune că toate relațiile au un număr finit de tupluri distincte și sunt descrise printr-o mulțime ordonată de atribute. Atributele se deosebesc prin poziția pe care o ocupă în relație sau prin numele asociat, numărul atributelor dând aritatea relației.
Operanzii algebrei relaționale sunt fie relații constante, fie variabile ce reprezintă relații de o aritate dată. Cererile din algebra relațională pot fi exprimate prin cinci operații asupra relațiilor pe care le vom numi operații de bază și anume:
– Reuniunea. Reuniunea relațiilor R și S, notată RS, este mulțimea tuplurilor care se găsesc în cel puțin una din relațiile R sau S. Această operație se poate aplica numai în cazul în care R și S au aceeași aritate și atributele corespunzătoare iau valori în aceleași domenii, rezultatul având și el aceeași aritate ca a celor două relații și aceleași domenii asociate. Dacă atributele au nume, se cere ca, în plus, cele două liste de nume să coincidă și rezultatul va avea aceeași listă de nume pentru atribute.
2. Diferenta. Diferența relațiilor R și S, notată R-S, este mulțimea tuplurilor din R care nu sunt în S. Trebuie îndeplinite aceleași condiții ca pentru reuniune.
3. Produsul cartezian. Fie relațiile R de aritate r și S de aritate s. Produsul cartezian al relațiilor R și S, notat RS, este mulțimea tuplurilor cu r+s componente, în care primele r componente formează un tuplu în R și ultimele s componente formează un tuplu în S. Dacă atributele au nume, lista numelor atributelor din rezultat este reuniunea disjunctă a celor două liste (folosind calificări sau redenumiri pentru atributele cu același nume în cele două relații).
4. Proiecția. Fie relația R de aritate r. Proiecția relației R după câmpurilc i1,i2,…,ik, notată i1,i2,…ik(R), este mulțimea tuplurilor de aritate k de forma a1,a2…ak pentru care există un tuplu b1,b2…br în R astfel încât a1=bi1, a2=bi2,……,ak=bik. Dacă relația R are asociate nume pentru atribute, se pot înlocui indicii cu numele atributelor respective, aceste nume păstrându-se și în relația rezultată.
5. Selecția sau restriția. Fie F o formulă logică formată din operanzi care sunt constante sau numere de componente în tupluri, operatori de comparare aritmetică <, = , >, , ≠, și operatori logici (și), (sau) și (non). Selecția relației R în raport cu formula F, notată 1(R), este mulțimea tuplurilor din R pentru care formula F devine adevărată prin înlocuirea fiecărui număr de componentă i din ea cu valoarea celei de-a i-a componente a tuplului . Dacă relația R are asociate nume pentru atribute, se pot înlocui indicii cu numele atributelor respective, relația rezultat având pentru atribute aceleași nume ca și relația R. Pentru a se deosebi de indicii sau numele atributelor, toate constantele care apar în F sunt incluse între apostrofuri.
Exemplul 3.1. Dacă pentru relația R(A,B,C) considerăm conținutul actual următor:
R = {(a,b,c), (d,a,f), (c,b,d)}
și pentru relația S(D,E,F) considerăm conținutul actual următor:
S= {(b,g,a), (d,a,f)}
atunci
R S= {(a,b,c), (d,a,f) (c,b,d), (b,g,a)}
R – S= {(a,b,c), (c,b,d)}
R S= {(a,b,c,b,g,a), (a,b,c,d,a,f), (d,a,f b,g,a),
(d,a,f,d,a,f), (c,b,d,b,g,a), (c,b,d,d,a,f)}
A,,C(R)= {(a,c), (d,f),(c,d)}
B,D(R)= {(a,b,c), (c,b,d)}.
Pe lângă cele cinci operații de bază, mai pot fi utilizate și alte operații numite operații derivate, ce se pot exprima în funcție de operațiile de bază. Utilizarea acestora permite o mai simplă exprimare a cererilor și, uneori, dacă sunt bine implementate, obținerea unui răspuns mai rapid. Cele mai des utilizate operații derivate sunt următoarele:
6. Interseția. Intersecția relațiilor R și S, notată RS, este mulțimea tuplurilor care se găsesc în ambele relații. Această operație se poate aplica numai în cazul în care R și S îndeplinesc condițiile specificate la reuniune. Intersecția se poate exprima prin operațiile de bază cu formula:
RS=R-(R-S)
7. Câtul. Fie relațiile R de aritate r și S de aritate s cu r>s și S≠. Câtul lui R prin S, notat R S, este mulțimea tuplurilor de aritate r-s astfel încât, pentru orice tuplu u al lui S, tuplul u este în R. Dacă atributele celor două relații au nume, atunci lista atributelor lui S trebuie să fie o submulțime a listei atributelor lui R și rezultatul are ca listă de atribute diferența celor două liste. Câtul se poate exprima prin operațiile de bază cu formula:
R S = 1,2,…,r-s(R) – 1,2,…,r-s((1,2,…,r-s(R) S)-R)
8. Uniunea (join). O -uniune a relațiilor R și S după coloanele i și j, notată R IXI S, unde este un operator de comparație, este mulțimea tuplu-
i j
rilor produsului cartezian dintre R și S pentru care a i-a componentă a lui R se află în relația cu a j-a componentă a relației S. Daca este operantul =, operația se numește echiuniune. Uniunea se poate exprima prin operațiile de bază cu formula:
R IXI S= i(r+j)(R S)
i j
Dacă R și S au nume pentru atribute, atunci în loc de i și j se pot folosi numele atributelor corespunzătoare.
9. Uniunea naturală (natural join). Uniunea naturală a relațiilor R și S, notata R IXI S, se aplică dacă cele două relații au nume asociate atributelor și, în acest caz, se selectează din produsul cartezian al relațiilor R și S acele tupluri ce conțin valori comune pentru câmpurile cu același nume din cele două relații și apoi se elimină valorile din câmpurile lui S comune cu cele ale lui R. Dacă relațiile R și S au în comun atributele A1,A2,…,Ak, atunci se obține formula:
R IXI S=i1,i2,…,im(RA1=SA1…..RAk=SAk(RS))
unde i1,i2,…,im, este o sublistă a atributelor lui R S în care apar mai întâi atributele din lista atributelor lui R, urmată de atributele din lista atributelor lui S din care se elimină atributele S.A1,S.A2,…,S.Ak.
Exemplul 3.2. Pentru relațiile R și S din exemplul 3.1. intersecția este:
R S= {(c,b,d)}.
Dacă
R = {(a,b,c,d), (a,b,e,f), (b,c,e,f), (e,d,c,d), (e,d,e,f), (a,b,d,e)}
și
S = {(c,d), (e,f)}
atunci:
R S = {(a,b),(e,d)}
Dacă relatia R(A,B,C) are conținutul actual:
R= {(1,2,3), (4,5,6), (7,8,9)}
și relația S(D,E) are conținutul actual:
S= {(3,1), (6,2)},
notând cu T relația R IXI S, se obține T(A,B,C,D,E), care are următorul conținut actual:
B D
T= {(1,2,3,3,1),(1,2,3,6,2), (4,5,6,6,2)}.
Dacă relația R(A,B,C) are conținutul actual:
R={(a,b,c),(d,b,c),(b,b,f),(c,a,d}
și S(B,C,D) are conținut actual:
S= {(b,c,d), (b,c,e), (a,d,b)},
atunci pentru uniunea naturală a lui R cu S se obține:
R 1XI S= {(a,b,c,d), (a,b,c,e), (d,b,c,d), (d,b,c,e), (c,a,d,b)}.
Cu operatorii din algebra relatională se pot defini noi relații ce pot fi utilizate pentru: regăsirea unor informații din baza de date, definirea unor reactualizări (inserare, , ștergere sau modificare) în baza de date, definirea unor date virtuale (vederi), definirea unor rezultate intermediare, definirea unor drepturi de acces ladate, definirea unor cerințe de stabilitate în cazul accesului concurent la date, definirea constrângerilor de integritate și altele.
Nu se poate obține cea mai eficientă interpretare a cererilor din algebră relațională efectuând calculele în ordinea indicată în expresia asociată. De exemplu, pentru expresia următoare:
C(A-a(R IXI S))
aplicată relațiilor binare R(A,B) și S(B,C), care se poate evalua prin succesiunea uniune, apoi selecție și, în final, proiecție, se poate găsi o transformare într-o expresie echivalentă:
C (B(A-a (R)) IXI S)
în care se efectuează pe rând selecție, proiecție, uniune și din nou proiecție care, în general, este mult mai eficientă din punct de vedere al spațiului ocupat și al timpului de calcul, lucrându-se tot timpul cu relații mai mici atât ca lungime a înregistrărilor, cât și ca număr.
Se poate obține o eficiență mai bună dacă uneori se combină mai mulți operatori ce pot să apară într-o succesiune dată în diferitele cereri. Un exemplu ar fi expresia selecție-uniune-proiecție, care poate să apară relativ frecvent în cereri prin selectarea unor tupluri ale unei relații, combinarea acestora cu tuplurile altei relații prin uniune și alegerea unor câmpuri din relația obținută. Astfel de succesiuni se pot implementa fără a mai fi nevoie de unele relații intermediare sau cu micșorarea numărului de câmpuri și de tupluri, ceea ce presupune mai puțin spațiu ocupat și timp de calcul mai mic.
Un exemplu de gramatică pentru definirea algebrei relaționale este următorul:
expresie :: = expresie-unară expresie-binarăe
expresie-unară ::= redenumire selecție proiecție
redenumire ::= termen RENAME atribut AS atribut
termen ::= relație ( expresie )
selecție ::= termen WHERE comparație
proiectie ::= termen termen lista-atribute]
listă-atribute ::= atribut atribut , lista-atribute
expresie-binară ::= expresie operator-binar expresie
operator-binar ::= UNION INTERSECT MINUS TIMES JOIN DIVIDEBY
atribut ::=…
relație ::= …
comparație ::=…
Se definesc pentru atribut și relație identificatori și pentru comparație un operator de comparare între mărimi scalare.
Se mai pot defini și alți operatori cu relații, cum ar fi:
– Extensia unei relații, care se definește prin construirea unei noi relații ce are ca atribute lista atributelor relației operand, la care se adaugă un nou atribut având ca valoare rezultatul obținut prin evaluarea unei expresii scalare. Sintaxa unei astfel de operații este:
EXTEND termen ADD expresie-scalara AS atribut
– Totarlizarea unei relații, permite aplicurca unor operații agregate pe păirțile componente ale unei relații, avand sintaxa:
SUMMARIZE termen GROUPBY (listă-atribute) ADD expresie AS atribut
în care listă-atribute selectează prin valorile pe care le au grupele la care se aplică evaluarea respectivă. Dacă lista este vidă, evaluarea se aplică o singură dată pentru toată relația.
– Câtul generalizat al relatiilor R(X,Y)si S(Y,Z), unde Y este lista atributelor comune celor două relații, notat:
R DIVIDEBYS
este o relație T(X,Z) ce conține toate tuplurile de forma (x,z) astfel încât, pentru orice y cu(y,z) din S, rezultă că (x,y) este un tuplu din R. Se observă că dacă Z este mulțimea vidă se obține câtul dintre R și S, daca X este mulțimea vidă se obține câtul dintre S și R și dacă Y este mulțimea vidă se obține produsul cartezian al celor două relații.
– Uniunea externă (outer join) conține tuplurile uniunii naturale, la care se adaugă câte un tuplu pentru acele tupluri dintr-o relație care nu au corespondent în cealaltă relație. Tuplurile adăugate astfel au valoarea null pentru toate atributele ce nu apar în relația din care provin.
Pe 1ângă operațiile asupra relațiilor în sistemele de baze de date concepute pe ideea algebrei relaționale, sunt considerate și alte operații cum ar fi generarea unor relații, înserarea, ștergerea sau modificarea unui tuplu într-o relație etc.
2. Calculul relațional pe tupluri
În calculul relațional pe tupluri, cererile se exprimă prin expresii de forma [t (t)], unde t este o variabilă tuplu iar este o formulă construită din atomi ,și o serie de operatori pe care îi vom defini în cele ce urmează.
Atomii din formula sunt de unul din următoarele tipuri:
– R(r), unde R este numele unei relații și r este o variabilă tuplu; acest atom corespunde propoziției r este un tuplu al relației R.
– r[i] sj], unde r și s sunt variabile tuplu și este un operator de comparație aritmetic. Acest atom corespunde propoziției a i-a componentă a lui r este în relație cu a j-a conenponentă a lui s.
– r[i] a, respectiv a r[i], unde r și sunt ca mai sus, iar a este o constantă. Acești atomi corespund propozițiilor a i-a componentă a lui r este în relație cu a, respectiv a este în relație cu a i-a componentă a lui r.
Formulele și calitatea ocurențelor variabilelor tuplu din formulă de a fi variabile libere sau variabilc legate se stabilesc prin următoarele reguli:
1. Orice atom este o formulă. Toate ocurențele de variabile tuplu menționate în atomi sunt variabile libere pentru aceste formule.
2. Dacă 1 și 2 sunt formule, atunci 12, 12 și 1 sunt formule corespunzătoare respectiv propozițiilor 1 și 2 ,sunt adevărate, 1 sau 2 sau ambele sunt adevărate și 1 nu este adevărată. Calitatea fiecărei ocurențe de a fi variabilă liberă sau variabilă legată în 1 și 2 rămâne aceeași și în formulele ce rezultă prin combinarea cu operatorii , și .
3. Dacă este o formulă, ațunci (t)() este o formulă ce corespunde propoziției există tuplul t astfel încât să fie adevărată dacă se înlocuiesc aparițiile libere din ale lui t cu valorile respective. Ocurențele de variabile libere ale lui t din devin variabile legate în expresia rezultată, iar toate celelalte ocurențe de variabile tuplu din rămân cu aceeași calitate (variabile libere sau variabile legate) și în formula rezultată.
4. Dacă este o formulă, atunci (t)() este o formulă ce corespunde propoziției oricare ar fi tuplul t, înlocuind aparițiile libere ale lui t în cu valorile respective este adevărată. Ocurențele de variabile libere ale lui t din devin variabile legate în expresia rezultată, toate celelalte ocurențe de variabile tuplu din rămân cu aceeași calitate (variabile libere sau variabile legate) și în formula rezultată.
5. Pot fi adăugate sau eliminate paranteze dacă nu mai sunt necesare, ținând seama de următoarea ordine de precedență: operatorii de comparație, apoi cuantificatorii și , apoi , apoi , apoi , operatorii aplicându-se de la stânga la dreapta în cazul a doi operatori consecutivi cu aceeași prioritate.
6. Orice formulă se obține aplicând de un număr finit de ori regulile 1 – 5. O expresie a calculului relațional pe tupluri reprezintă o expresie de forma {t (t), unde t este singura variabilă tuplu care are ocurențe libere în .
Exemplu1 3.3. Dacă relația R are aritatea doi, atunci expresia:
{t(u)(R(t)R(u)(t[1]u[1]t[2]u[2]))}
este relația vidă dacă R are cel mult un element și R în caz contrar.
Deoarece expresii de forma {t R(t)}, care ar însemna mulțimea tuturor tuplurilor de aceeași aritate cu R care nu se află în R, în general nu au snes, putând da relații infinite în bazele de date ce utilizează calculul relațional pe tupluri, se folosește numai o submulțime de expresii numite expresii sigure.
Dacă este o formulă, vom numi domeniul lui și vom nota DOM() mulțimea simbolurilor care apar în explicit sau sunt componente de tupluri din conținutul actual al relațiilor ce apar în . Deoarece toate relațiile folosite au conținutul actual finit, DOM() este o mulțime finită.
Spunem că o expresie a calculului relațional pe tupturi {t (t)} este expresie sigură dacă, pentru orice tuplu t care satisface , toate eomponentele lui t sunt elemente ale lui DOM().
Pentru a stabili valoarea de adevăr a formulelor de tipul (t)((t)) și (t)((t)) numai prin valori pentru componentele lui t din DOM(), facem următoarele convenții:
– (t) este falsă pentru toate tuplurile t ce conțin cel puțin o componentă în afara lui DOM() pentru formula (t)((t)).
– (t) este adevarată pentru toate tuplurile t ce conțin cel puțin o componentă în afara lui DOM() pentru formula (t)((t)).
Un exemplu de gramatică pentru definirea calculului relațional pe tupluri este următorul:
definire-domeniu ::= RANGE OF variabilă IS listă-domenii
listă-domenii ::= domeniu domeniu , listă-domenii
domeniu ::= relație ( expresie )
expresie ::= listă-rezultat WHERE formulă ]
listă-rezultat ::= rezultat rezultat , listă-rezultat
rezultat ::= [ atribut = ] variabilă . atribut variabilă
formulă ::= comparație NOT formulă comparație AND formulă comparatie OR formulă IF comparație THEN formulă EXISTS variabilă (formulă) FORALL variabilă (formulă)
variabilă ::= …
relație ::= …
atribut ::= …
comparație ::= …
Pentru variabilă, relație și atribut se stabilesc identificatori ce definesc elementele respective, iar comparație definește o expresie în care apare un operator de comparare între două expresii scalare.
3. Reducerea algebrei relaționale la calculul relațional pe tupluri
Vom arăta în continuare cum se poate trece de la o cerere exprimată în algebra relațională la o cerere exprimată în calculul relațional pe tupluri. Demonstrația teoremei dă și algoritmul prin care se poate face practice această trecere.
'I'eorema 3.1. Dacă E este o expresie din algebra relațională, atunci există o expresie sigură în calculul relațional pe tupluri echivalentă cu E.
Demonstrație. Vom aplica metoda inducției complete după numărul ocurențelor operatorilor din expresia E.
Dacă E nu conține nici un operator, atunci E poate fi o variabilă relație R sau o relație constantă {t1,t2,…,tn}. În primul caz, E este echivalentă cu expresia {t R(t)} care este sigură, deoarece orice tuplu t care verifică R(t) are evident componentele în DOM(R(t)), care conține toate valorile corespunzătoare componentelor relației R. În cazul al doilea, E este echivalentă cu expresia t t=t1t=t2…..t=tn, unde prin t=t1 am notat formula t = t1 … tk = t1k, presupunând aritatea k pentru t. Cum și această expresie este o expresie sigură luând ca domeniu asociat reuniunea valorilor ce apar în componentele tuplurilor t1,t2,…,tn, proprietatea din enunțul teoremei este verificată pentru o expresie cu 0 ocurențe de operatori.
Să presupunem acum că E are cel puțin un operator și că proprietatea din enunțul teoromei este adevărată pentru expresii cu mai puține ocurențe de operatori decât are E. Vom avea următoarele cazuri posibile:
1. E = E1 E2. Cum E1 și E2 au mai puține ocurențe de operatori decât E, aplicăm ipoteza inducției și admitem existența expresiilor sigure {t 1(t)} și {t 2(t)}, echivalente respectiv cu E1 și E2. Atunci E este echivalentă cu expresia t 1(t) 2(t)} care este o expresie sigură având domeniul:
DOM(1(t) 2(t)) = DOM (1(t)) DOM (2(t)).
2. E=E1-E2. Ca și în cazul 1 , E1 și E2 admit expresii sigure, iar E este echivalentă cu expresia {t 1(t) 2(t)} care este o expresie sigură având domeniul:
DOM(1 (t) 2(t)) = DOM(1 (t)) DOM(2 (t)).
3. E=E1E2. Dacă E1 și E2 au aritățile m și respectiv n și le corespund expresii sigure ca la 1. Atunci E este echivalentă cu expresia următoare:
{t (u)(v)(1(u)2(v)t1 = u1…tm = umm+1 = v1…tm+n = vn)}
care este o expresie sigură având ca domeniu:
DOM(1(u)) DOM(2(v)).
4. E=i1,i2,…ik(E1). Dacă E1 este echivalentă cu expresia sigură t 1(t), atunci E este echivalentă cu expresia:
t (u)( 1(u))t1 = ui1…tk = uik
care este o expresie sigură având ca domeniu o submulțime a lui DOM(1(u)) și anume mulțimea valorilor posibile pentru componentele i1,…,ik ale lui u.
5. E = 1(E1). Dacă E1 este echivalentă cu expresia sigură {t 1(t)}, atunci E este echivalentă cu {t 1(t)F}, unde F se obține din F înlocuind fiecare operand i cu t[i. Această expresie este sigură pe un domeniu inclus în DOM(1(t)).
Deoarece orice expresie din algebra relațională se poate obține inclusiv prin aplicarea de un număr finit de ori a celor cinci operații de bază, rezultă că proprietatea din enunțul teoremei este adevarată.
Aplicând algoritmul de transformare a unei expresii din algebra relațională într-o expresie sigură din calculul relațional pe tupluri rezultat din demonstrația teoremei precedente nu se ajunge mereu la cea mai simplă expresie. De aceea se aplică apoi metode de optimizare, pe care le vom prezenta în continuare, pentru a obține expresii echivalente ce pot fi calculate mai ușor.
Exemplul 3.4. Compunerea a două relații binare R și S în sensul obișnuit din teoria mulțimilor se poate exprima în algebra relațională prin expresia următoare:
1,4(2 3(RS))
căreia îi corespunde aplicând algoritmul expresia sigură următoare:
{w (t)(u)(v)(R(u)S(v)t1 = u1t2 = u2t3 = v1t4 = v2t2 = t3w1 = t1w2 = t4)}
dar există și următoarea expresie sigură mai simplă echivalentă ei:
{w (u)(v)(R(u)S(v)u2=v1w1=u1w2=v2)}.
4. Calculul relațional pe domenii
Calculul relațional pe domenii permite exprimarea cererilor tot sub forma unor expresii care se construiesc analog expresiilor calculului relațional pe tupluri, cu următoarele deosebiri:
– în loc de variabile tuplu se folosesc variabile pe domeniu ce pot să ia drept valori elemente componente ale tuplurilor;
– un atom este de forma R(x1,x2,…,xk), unde R este o relație de aritate k și x1,x2,…,xk sunt constante sau variabile de domeniu, sau de forma xy, unde x și y sunt constante sau variabile de domeniu și este un operator relațional aritmetic; semnificația atomilor este analoagă cu cea din calculul relațional pe tupluri;
– în calculul relațional pe domenii se folosesc operatorii , și , ca în calculul relațional pe tupluri, iar pentru cuantiticatorii (x) și (x), x este o variabilă de domeniu; calitatea ocurențelor de variabile libere sau legate se definesc în același mod.
O expresie a calculului relațional pe domenii este de forma {x1x2…xk(x1,x2,…,xk.)}, unde este o formulă pentru care singurele variabile pe domeniu libere sunt x1,x2,…,xk.
Ca și în cazul calculului relațional pe tupluri, se definește o expresie sigură a calculul relațional pe domenii ca o expresie pentru care se poate stabili dacă formula conținută în ea este adevărată sau nu numai pentru valori ale variabilelor domeniu într-o mulțime finită asociată, numită domeniu expresiei.
5. Reducerea calculului relațional pe tupluri la calculul relațional pe domenii
Pentru a transforma o expresic {t(t)} a calculului relațional pe tupluri înlr-o espresie echivalentă din calculul relațional pe domenii, se introduc variabilele de domeniu t1,t2,…tk,unde k este aritatea lui t,și se definește formula {t1,t2..tk(t1t2….tk)cu obținut din înlocuind orice atom R(t) cu R(t1t2…tk), ocurcnțele lui ti prin ti ,iar pentru cuantificatorii (u) și (u) cu u de aritate m se intrucluc m noi variabile de domeniu u1,u2,. ,um, se înlocuiesc cuantificalorii cu (u1)…(um), respecliv (ut)…(um), iar în domeniul asociat aceslor operatori se înlocuiește fiscare ocurență liberă ui cu u1 si R(u) cu R(u1u2…um)
Prin procesul anterior se construiește o exresie a calculului relațional pe domenii care este echivalentă cu o expresie dată a calculului relațional pe tupluri. Se poate demonstra următoarea proprietate:
Teorema 3.2. Pentru orice expresie singură a calculului relațional pe tupluri există în expresie sigură a calculului relațional pe domnenii echialentă cu ea.
Demonstrația se face arătând că metoda expusă anterior dă expresii echivalente și, dacă expresia inițială este sigură, atunci și expresia rezultată esie sigură.
Exemplul 3.5. Expresia finală din exemplul 3.4 pentru compunerea a două relații binare poate fi transformată prin procedeul descris, obținând:
w1w2(u1)(u2)(v1)(v2)(R(u1u2)S(v1v2)u2=y1w1=u1w2=v2)
6.Reducerea calculului relațional pe domenii la algebra relațională
Pentru a arăta modul cum se poate trece de la o expresie sigură a calculului relațional pe domenii la o eapresie din algebra relatională, vom stabili câteva rezultate preliminare.
Lema 3.1. Dacă este o formulă în calculul relațional pe domenii, atunci există o expresie în algebra relațională pentru relația unară DOM() pe care se poate stabili valoarea de adevăr a lui .
Demonstrație. Pentru o relație R de aritate k, notăm cu E(R) mulțimea 1(R) 2(R) . .. k(R). Fie C = {c1,c2,…,cm} mulțimea constantelor care apar în formula și R1,R2,…,Rn relațiile ce apar în . Se verifică imediat din definiție că pentru domeniul lui se poate lua expresia următoare:
DOM() = E(R1)E(R2)…E(Rn)C
aceasta fiind o expresie din algebra relatională.
Lema 3.2. Pentru orice expresie a calculului relațional pe domenii, există o expresie echivalentă ' a calculului relațional pe domenii în care nu apar operatorii sau . În plus, dacă e sigură, atunci și ' este sigură.
Demonstrație. Plecând de la formula , se fac pe rând următoarele transformări: orice subformulă de forma 12 se înlocuiește prin formula echivalentă (12) (legea DeMorgan) și apoi orice subformulă de forma (u)( 1(u)) se înlocuiește prin formula echivalentă (u)(1(u)). Cum oricare dintre cele două tipuri de transformări aplicate unei formule sigure au ca rezultat tot o formulă sigură, rezultă că proprietatea din enunțul lemei este adevărată.
Teorema 3.3. Pentru orice expresie sigură a calculului relațional pe domenii, există o expresie echivalentă în algebra relațională.
Demonstrație. Fie x1x2…xk (x1,x2,…,xk) o expresie sigură a calculului relațional pe domenii care conține numai operator , , și (conform lemei 3.2, operatorii și pot fi eliminați obținând o expresie echivalentă). Din lema 3.1 rezultă că există o expresie E a algebrei relaționale pentru DOM(). Vom demonstra prin inducție după numărul ocurențelor operatorii dintr-o subformulă a lui că, dacă are variabilele de domeniu libere y1,y2,…,ym atunci expresia:
(DOM())m {y1y2…ym (y1y2…ym)}
are o expresie echivalentă în algebra relațională. Când coincide cu se obține rezultatul din enunțul teoremei. Demonstrația este constructivă, furnizând o metodă efectivă pentru această transformare.
Dacă are zero operatori, atunci este un atom care poate fi de una din formele x1x2, x1a sau R(xi1,xi2,…xik), unde este un operator de comparație aritmetică și a este o constantă. Pentru x1x2 expresia echivalentă este 12(EE), putru x1a expresia echivalentă este 1a(E) și pentru R(xi1,xi2,…,xik) se construiește expresia j1j2…jm(1(R)), unde F este o formulă ce conține termeni u=v dacă xiu și xiv reprezintă aceeași variabilă, și u<v legați cu operatorul , iar indicii j1,j2,…,jm sunt aleși în așa fel încât x1=xij1,x2=xij2,…,xm=xijm, deci dau una din pozițiile pe care se află în R variabilele domeniu x1,x2,…,xm.
Să presupunem acum că are cel puțin un operator și că proprietatea enunțată este adevarată pentru toate subformulele lui care au mai puține ocurențe de operatori decât . Vom trata trei cazuri distincte:
Cazul 1. (y1,y2,…,ym)=1(u1,u2,…,un)2(v1,v2,…vp) unde u1,u2,…,un și respectiv v1,v2,…,vp sunt variabile domeniu distincte ce fac parte din mulțimea y1,y2,…,ym. Conform ipotezei de inducție, fie E1 și E7 expresiile din algebra relațională echivalente respectiv cu expresiile:
En {u1u2…un 1(u1,u2,…,un)}
Ep v1v2…vp 2(v1,v2,…,vp).
Definim relația
E3 = i1…im(E1 Em n )
unde i1 este acel indice k astfel încât vk=yj, dacă acesta există, sau un indice unic între n+1 și m dacă yj nu apare în mulțimeav1,…,vn.Similar se definește:
E4 =i1…,im(E2 Em p)
Atunci E3E4 este expresia din algebra relațională echivalentă cu:
E1m{y1y2….ym(y1,y2,…,ym)}.
Cazul 2. (y1y2,…ym)= 1(y1,y2…,ym).Fie E1 expresia echivalentă din algebra relațională corespunzătoare expresiei:
Em {y1y2…ym 1(y1,y2,…,ym)}
care există conform ipotezei de inducție. Atunci E1 – Em este expresia algebrei relaționale echivalentă cu:
Em y1y2…ym (y1,y2,…,ym)
Cazul 3. Fie (y1,y2,…,ym)=(m+1)(1(y1,y2,…,ym+1)) și E1 expresia echivalentă din algebra relațională pentru:
Em+1 y1y2…ym 1(y1,y2,…,ym+1)
Deoarece este sigură și, deci, și este sigură, 1(y1…ym+1) poate să fie adevărată numai dacă ym+1 este în mulțimea DOM(), care este o submulțime a lui DOM(). Deci 1,2,…,m(E1) este expresia echivalentă din algebra relațională pentru expresia:
Em y1y2…ym (ym+1)(1(y1,y2,…,ym,ym+1))
ceea ce completează demonstrația teoremei.
Exemplul 3.6. Fie R și S două relații binare și expresia:
wx R(wx)(y)(S(wy)S(xy))
Pentru a găsi expresia echivalentă din algebra relațională, procedăm în felul următor. Notăm E=1(R)2(R)1(S)2(S). Eliminăm operatorii și prin metoda din lema 3.2 și obținem:
{wx (R(wx)(y)(S(wy)S(xy)))}
apoi pentru E3 wxy S(xy)S(xy)} obținem expresia:
E1=1,3,2(SE)3,1,2(SE)
iar pentru expresia E2wx (y)(S(wy)S(xy)) se obține:
E2=1,2(E1)=1,3(SE)3,1(SE)
și în final se obține formula:
E2-((E2-R)E2)
care este echivalentă cu R-E2 și deci expresia din algebra relațională căutată este:
R-(1,3(SE)3,1(SE))
Din proprietățile demonstrate anterior rezultă, de fapt, că cele trei tipuri de sisteme relaționale sunt echivalente, în sensul că orice cerere care se poate exprima în unul din ele se poate exprima și în celelalte două.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Managemantul Tranzactiilor In Baze de Date Relationale (ID: 149121)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.