CONSTRUIREA UNEI BAZE DE DATE
In acest capitol vom prezenta principalele metode utilizate in construirea bazelor de date, punand accent in special pe modelul relational care este mai des utilizat. Se are in vedere in primul rand proprietatile bazei de date, usurinta implementarii la nivel fizic, usurinta interogarii si timpul de raspuns, integritatea datelor si modul de detectare si reparare a erorilor.
1. Dependente in bazele de date
Pentru modelul relational de o importanta deosebita este alegerea relatiilor ce compun baza de date. Includerea in baza de date a unei relatii
MAGAZINE(NUMEMAG,ADRESAMAG,MARFA,PRET)
asa cum apare in exemplul 3.8 poate sa provoace anumite anomali cum sunt:
- redondanta - adresa magazinelor este repetata pentru fiecare marfa
vanduta de un magazin
- posibile inconsistente datorate reactualizarilor - pentru valori
redondante se pot schimba unele valori fara a afecta toate aparitiile
acelor valori; astfel un magazit poate sa apara cu mai multe adrese
desi in realitate se considera ca fiecare magazin are o singura adresa
- anomalii de insertie - nu se poate introduce un magazin cu adresa lui
in baza de date decat daca vinde cel putin o marfa
- anomalii la stergere - daca se sterg pe rand toate marfurile vandute
de un magazin nu se mai retin date despre acel magtazin.
Problemele enumerate mai sus nu se mai pun daca in loc de relatia data se introduc in baza de date relatiile
MAGADR(NUMEMAG,ADRESAMAG)
MAGMAR(NUMEMAG,MARFA,PRET)
din care se poate reconstitui prin uniune naturala relatia initiala.
Calitatile diferitelor relatii sunt descrise cu ajutorul dependentelor functionale si multivaloare putandu-se face clasificari ale relatiilor in diferite tipuri de forme normale dupa cum vom vedea in cele ce urmeaza.
1.1. Dependente functionale
Datele continute in baza de date de cele mai multe ori nu pot fi luate la intamplare din domeniile asociate atributelor corespunzatoare lor. De exemplu nu putem avea inaltimea unei persoane mai mare decat 3m sau o persoana in viata nascuta inainte de anul 1800 asa cum nu poate avea o persoana varsta de 20 de ani si vechimea in munca de 30 de ani. Astfel de erori pot fi detectate impunand anumite restrictii asupra datelor. Exista doua tipuri de restrictii: restrictii ce depind de semantica domeniilor elementelor si restrictii rezultate din compararea unor valori.
Fie R(A1,A2,...,An) o schema relationala, X si Y submultimi de atribute ale lui R; vom spune ca "X determina functional Y" sau "Y depinde functional de X" si notam X->Y daca pentru orice relatie r valoarea curenta a lui R nu exista doua tupluri care sa aiba aceleasi valori pentru 22122b12w atributele din X si sa aiba valori diferite pentru cel putin un atribut din Y.
Daca R este corespondentul unei entitati avand cheia X, se vede imediat ca pentru orice submultime de atribute Y avem X->Y. Analog, daca R corespunde unei relatii unu-la-mai-multi de la entitatea E1 la entitatea E2 si X este o cheie a lui E2 iar Y este o cheie a lui E1 atunci X->Y.
Se spune ca Y este complet dependenta functional de X daca Y este dependenta functional de X si nu este dependenta functional de nici-o submultime proprie a lui X.
Dependentele functionale nu pot fi determinate automat. Ele sunt desemnate de cel care proiecteaza baza de date in functie de restrictiile pe care vrea sa le impuna si de semnificatia atributelor. De exemplu impunerea unei dependente functionale de tipul NUME -> ADRESA impune conditia ca fiecarei persoane sa i se atribuie cel mult o adresa in relatia respectiva.
In cele ce urmeaza vom nota cu A1A2...An multimea atributelor si cu XY vom nota X U Y unde X si Y sunt submultimi de atribute.
Exemplul 5.1. Pentru baza de date din exemplul 3.8 putem sa stabilim o serie de dependente functionale dupa cum urmeaza. Presupunand ca nu exista cumparatori cu acelasi nume si fiecare cumparator are o singura adresa si un singur cont rezulta pentru relatia CUMPARATORI dependenta functionala
NUME -> ADRESA CONT
Daca pentru comenzi se dau numere diferite atunci pentru relatia COMENZI se poate stabili dependenta functionala
NR_COM -> NUME MARFA CANTITATE
deoarece NR_COM devine in conditiile date cheie pentru aceasta relatie.
Pentru relatia MAGAZINE se pot impune dependente functionale de tipul
NUMEMAG -> ADRESAMAG
NUMEMAG MARFA -> PRET
care impun unicitatea adresei unui magazin si fatul ca un magazin vinde fiecare marfa cu un singur pret.
Fie F o multime de dependente functionale pentru o schema relationala R si X -> Y o dependenta functionala. Vom spune ca F implica logic X -> Y si vom nota F |= X -> Y daca orice relatie r continut actual pentru R care satisface dependentele functionale din F satisface si X -> Y. Multimea tuturor dependentelor functionale implicate logic de F o numim inchiderea lui F si o notam F\+, deci F\+ = .
Pentru o relatie R cu atributele A1A2...An si dependentele functionale F spunem ca o submultime X de atribute este cheie a lui R daca X -> A1A2...An este in F\+ dar pentru orice submultime proprie Y a lui X dependenta functionala
Y -> A1A2...An nu este in F\+.
O relatie are una sau mai multe chei. In cazul cand sunt mai multe chei se alege una dintre ele numita cheie primara drept reprezentativa pentru relatia respectiva, restul fiind numite candidat de cheie.
Exemplul 5.2. Pentru relatia CODURI(ORAS,STRADA,COD) cu dependentele functionale
ORAS STRADA -> COD
COD -> ORAS
pot fi considerate drept cheie atat cat si .
Pentru deducerea dependentelor functionale implicate logic de o multime de dependente functionale au fost introduse o serie de reguli cunoscute sub numele de axiomele lui Armstrong. Sa consideram o schema relationala R cu multimea atributelor U - multime universala de atribute - cu multimea dependentelor functionale F in care apar numai atribute din U, atunci regulile de inferenta sunt urmatoarele:
A1. (reflexivitate) |= X -> Y.
A2. (amplificare) |= XZ -> YZ.
A3. (tranzitivitate) |= X -> Z.
Regula A1 permite obtinerea dependentelor triviale in care partea din dreapta este continuta in partea din stanga si nu depinde in mod esential de F.
Lema 5.1. Axiomele lui Armstrong sunt corecte in sensul ca daca X -> Y se deduce din F folosind axiomele stunci X -> Y este verificata pentru orice relatie pentru care dependentele din F sunt verificate.
Demonstratie. A1 este corecta deoarece nu putem avea o relatie r cu doua tupluri care sa aiba aceleasi valori pentru 22122b12w atributele din X si in acelas timp sa difere pentru cel putin un atribut al unei submultimi a lui X. Pentru A2 sa consideram ca ar exista o relatie r care verifica X -> Y si care are doua tupluri u si v ce coincid pe atributele XZ dar nu coincid pe YZ si cum pe Z au aceleasi valori ar rezulta ca ele nu coincid pe Y dar coicid pe X ceea ce este in contradictie cu faptul ca r verifica X -> Y. Pentru A3 sa consideram relatia r care verifica X -> Y si Y -> Z si fie doua tupluri u si v care coincid pe X. Din faptul ca r verifica X -> Y rezulta ca u si v coincid si pe Y iar din faptul ca r verifica Y -> Z rezuta ca u si v coincid si pe Z ceea ce dovedeste ca r verifica si X -> Z.
Din axiomele lui Armstrong se pot deduce si alte reguli dintre care foarte utile sunt cele din lema urmatoare.
Lema 5.2. Sunt adevarate urmatoarele formule:
B1. (reuniune) |= X -> YZ
B2. (pseudotranzitivitate) |= XW -> Z
B3. (descompunere) F |= X -> Y si Z C Y atunci F |= X -> Z.
Demonstratie. Pentru B1 din X -> Y se obtine amplificand cu X dependenta X -> XY iar din X -> Z se obtine amplificand cu Y dependenta XY -> YZ si prin tranzitivitate din cele doua dependente se obtine X -> YZ. Pentru B2 din X -> Y se obtine prin amplificare cu W dependenta XW -> YW care impreuna cu a doua dependenta din enunt dau prin tranzitivitate XW -> Z. Pentru B3 din Z C Y rezulta prin reflexivitate Y -> Z si aplicand tranzitivitatea pentru prima dependenta din enunt si dependenta rezultata se obtine X -> Z.
Lema 5.3. X -> A1A2...Ak <=> X -> Ai pentru orice i @c .
Demonstratia se face prin inductie dupa k aplicand B1 si B3.
Fie F o multime de dependente functionale cu multimea atributelor U si fie X o submultime de atribute. Numim inchiterea lui X in raport cu F, notata X\+ multimea tuturor atributelor A astfel incat X -> A se deduce din F aplicand axiomele lui Armstrong.
Lema 5.4. X -> Y rezulta din axiomele lui Armstrong daca si numai daca
Y C X\+.
Demonstratia rezulta din definitii si aplicand lema 5.3.
Teorema 5.1. Axiomele lui Armstrong sunt corecte si complete.
Demonstratie. Corectitudinea este data de lema 5.1. Fie F o multime de dependente pe multimea de atribute U si sa presupunem ca X -> Y este dedusa logic din F dar nu poate fi obtinuta prin axiome. Consideram relatia r care are doua tupluri ce au aceleasi valori pe campurile din X\+ si valori distincte pe celelalte campuri. Sa aratam ca r satisface dependentele din F. Fie V -> W o astfel de dependenta. Daca V nu este inclus in X\+ conditia este evident indeplinita deoarece nu exista in r doua tupluri cu valori egale pentru atributele lui V. Daca V C X\+ rezulta conform lemei 5.4 ca X -> V si cum V -> W rezulta prin tranzitivitate ca X -> W si cum pe X cele doua tupluri ale lui r au aceleasi valori rezulta ca ele au aceleasi valori si pe campurile lui W ceea ce demonstraza ca r verifica si in acest caz V -> W. Cum X -> Y este dedusa logic din F rezulta ca este verificata de r si cum X C X\+ rezulta ca cele doua tupluri ale lui r au valori comune pentru atributele lui X deci ele trebuie sa aiba valori comune si pentru atributele lui Y ceea ce dovedeste ca Y C X\+ dar tinand seama de ipoteza si de lema 5.4 se ajunge la o contradictie.
Faptul ca orice dependenta obtinuta din F aplicand axiomele lui Armstrong este dedusa logic din F se demonstraza prin inductie dupa lungimea "demonstratiei" dependentei respective aplicand lema 5.1.
Pentru a decide daca o dependenta X -> Y poate fi dedusa logic din F este suficient sa calculam X\+ si sa vedem conform lemei 5.4 daca Y C X\+ sau nu. Calculul lui X\+ se poate face relativ simplu folosind algoritmul urmator.
Algoritmul 5.1. Fie X o multime de atribute si F o multime de dependente functionale.
1. Se face X\(0) = X si i = 0.
2. Daca exista in F o dependenta V -> W cu V C X\(i) si W @C/ X\(i)
atunci se face X\(i+1) = X\(i) U W; i = i+1 si se reia punctul 2;
altfel STOP (X\+ = X\(i)).
Exemplul 5.3. Fie X = BD si F avand urmatoarele dependente functionale
1) AB -> C 2) C -> A 3) BC -> D 4) ACD -> B
5) D -> EG 6) BE -> C 7) CG -> BD 8) CE -> AG
Aplicand algoritmul 5.1 se obtine mai intai X\(0) = BD, apoi folosind dependenta 5) X\(1) = BDEG, apoi folosind dependenta 6) X\(2) = BCDEG si folosind dependenta 2) se obtine X\(3) = ABCDEG pentru care nu mai sunt indeplinite conditiile din pasul doi si algoritmul se termina. Deci (BD)\+ = ABCDEG.
Exista posibilitatea de a implementa algoritmul precedent pentru a efectua un numar de calcule de ordinul sumei lungimilor cuvintelor din dependentele functionale din F.
Faptul ca algoritmul propus calculeaza pe X\+ se demonstreaza in mai multe etape. Mai intai se observa ca sirul de multimi X\(0), X\(1), ... este un sir strict crescator de multimi in raport cu incluziunea si marginit superior de multimea finita U si deci algoritmul se termina dupa un numar finit de pasi. Apoi se demonstreaza prin inductie dupa i ca X\(i) C X\+. In final se demonstreaza prin inductie dupa numarul de pasi din "demonstratia" dependentei
X -> Y ca exista un i astfel incat Y C X\(i) ceea ce asigura si incluziunea lui X\+ in multimea obtinuta de algoritm.
Fie F si G doua multimi de dependente. Spunem ca F si G sunt echivalente si notam F ~ G daca si numai daca F\+ = G\+. Spunem ca F acopera pe G daca si numai daca pentru orice dependenta X -> Y din G avem F |= X -> Y. Plecand de la aceste definitii se demonstraza usor ca F si G sunt echivalente daca si numai daca F acopera pe G si G acopera pe F. Testele corespunzatoare unei acoperiri se fac relativ simplu utilizand algoritmul 5.1. Pentru fiecare dependenta X -> Y din G se calculeaza cu algoritmul dat X\+ si daca Y nu este inclus in X\+ atunci F nu acopera pe G. In cazul cand pentru fiecare dependenta X -> Y din G multimea Y este inclusa in X\+, F acopera pe G.
Lema 5.5. Relatia ~ definita mai sus este o relatie de echivalenta pe multimea multimilor de dependente functionale.
Demonstratia rezulta usor din definitie prin justificarea proprietatilor de reflexivitate, simetrie si tranzitivitate ale acestei relatii.
Lema 5.6. Pentru orice multime de dependente functionale F existe o multime de dependente functionale G echivalenta cu ea, in care orice dependenta functionala contine in partea dreapta un singur atribut.
Demonstratie. G se obtine ca un sir de transformari ale lui F in multimi intermediare echivalente cu F, o multime obtinandu-se din precedenta prin inlocuirea unei dependente functionale X -> Y unde Y = A1A2...Ak (k>1) cu multimea de dependente functionale X -> A1, X -> A2, ..., X -> Ak. Echivalenta se demonstreaza usor aplicand regulile de descompunere si respectiv reuniune pentru dependentele diferite din doua multimi consecutive, acestea fiind cele precedente. Faptul ca procesul de transformare se termina dupa un numar finit de pasi este asigurat de micsorarea cu o unitate a numarului dependentelor functionale avand partea din dreapta cu mai mult de un atribut la fiecare transformare. Este usor de vazut, de asemenea ca rezultatul final nu depinde de ordinea in care sunt alese dependentele functionale ce se transforma.
Vom spune ca o multime de dependente este minimala daca sunt indeplinite urmatoarele proprietati:
1. Partea din dreapta oricarei dependente din F are un singur atribut.
2. Oricare ar fi X -> A din F multimea F - nu este echivalenta
cu F.
3. Oricare ar fi X -> A din F si oricare ar fi Z o submultime proprie a
lui X, multimea (F - ) U nu este echivalenta cu F.
Teorema 5.2. Pentru orice multime de dependente functionale F exista o multime de dependente functionale minimala F' echivalenta cu F.
Demonstratie. Aplicand procedeul din demonstratia lemei 5.6 din F se obtine o unica multime de dependente functionale F1 echivalenta cu F care indeplineste conditia 1. Eliminand pe rand din F1 dependentele care contrazic proprietatea 2 se obtine dupa un numar finit de pasi o multime de dependente F2 care indeplineste primele doua proprietati si este echivalenta cu F. Multimea F2 poate sa depinda de ordinea in care se fac eliminarile. In final se incearca eliminarea cate unui atribut din partea stanga a orcarei dependente care are mai mult de un atribut in partea stanga. Astfel pentru a putea elimina atributul Ai din dependenta functionala A1...Ai...Ak -> B este suficient a demonstra ca
F |= A1...Ai-1Ai+1...Ak -> B, adica B apartine lui (A1...Ai-1Ai+1...Ak)\+. Cand nu se mai pot face eliminari se obtine F'. Ordinea in care sunt eliminate atributele poate influenta rezultatul final.
Exemplul 5.4. Pentru multimea de dependente functionale F din exemplul 5.3 se pot obtine aplicand procedeul din demonstratia teoremei urmatoarele doua multimi de dependente minimale echivalente cu F:
F1 =
F2 = .
Determinarea unei multimi minimale de dependente functionale echivalenta cu o multime data de dependente functionale este utila in testele ce se fac in bazele de date la reactualizare, conducand la un timp de calcul mai mic.
CURSUL 10
1.2. Descompunerea schemelor relationale
Numim descompunere a unei scheme relationale R = inlocuirea ei printr-o multime de scheme relationale @r = astfel incat R = R1 U R2 U ... U Rk.
Fie R o schema relationala, @r = o descompunere a lui R si F o multime de dependente functionale. Spunem ca @r este o descompunere fara pierderi la uniune a lui R in raport cu F daca si numai daca pentru orice relatie r continut actual al lui R care verifica F are loc egalitatea:
r = @P/R1(r) |X| @P/R2(r) |X| ... |X| @P/Rk(r)
Descompunerea fara pierderi la uniune asigura reconstituirea relatiei initiale din proiectiile acesteia pe relatiile de descompunere in mod unic.
Lema 5.7. Fie R o schema relationala, @r = o descompunere a lui R si r continutul actual al lui R. Notand ri = @P/Ri(r) si m/@r(r) = r1 |X| r2 |X| ... |X| rk au loc urmatoarele relatii:
1. r C m/@r(r).
2. @P/Ri(m/@r(r)) = ri.
3. m/@r(m/@r(r)) = m/@r(r).
Demonstratia rezulta usor din definitiile si notatiile date.
Pentru a testa daca @r = este o descompunere fara pierderi la uniune a schemei relationale R in raport cu dependentele functionale F se poate aplica urmatorul algoritm:
Algoritmul 5.2. Daca R = A1A2...An si @r = se construieste o matrice avand k linii si n coloane ce contine in linia i si coloana j simbolul a/j daca Aj se afla in Ri si respenctiv b/ij daca Aj nu se afla in Ri. Apoi se considera pe rand dependentele X -> Y din F si pentru fiecare pereche de linii din tabel pentru care valorile corespunzatoare atributelor lui X coincid se identifica simbolurile din coloanele corespunzatoare lui Y prin urmatorul procedeu: daca ambele sunt a/j nu se face nici-o modificare, daca unul este a/j iar celalalt este b/ij se inlocuieste peste tot b/ij cu a/j iar daca unul este b/ij iar celalalt este b/sj se inlocuieste peste tot b/sj cu b/ij. Daca la un moment dat se obtine un rand care contine numai simboluri a descompunerea este fara pierderi la uniune, altfel, cand nu se mai pot face modificari in tabel, descompunerea este cu pierderi la uniune.
Exemplul 5.5. Fie R = ABCDE, dependentele F = si o descompunere a relatiei R in relatiile R1 = AD, R2 = AB, R3 = BE, R4 = CDE si R5 = AE. Aplicarea algoritmului se face plecand de la tabelul initial:
A B C D E
R1 a1 b12 b13 a4 b15
R2 a1 a2 b23 b24 b25
R3 b31 a2 b33 b34 a5
R4 b41 b42 a3 a4 a5
R5 a1 b52 b53 b54 a5
Se poate folosi A -> C pentru a identifica pe b23 si b53 cu b13 si apoi B -> C pentru a identifica b33 cu b13. Se foloseste C -> D pentru a identifica b24, b34 si b54 cu a4, apoi se foloseste DE -> C pentru a identifica b13 cu a3 si, in sfarsit se foloseste CE -> A pentru a identifica b31 si b41 cu a1 obtinandu-se tabelul urmator:
A B C D E
R1 a1 b12 a3 a4 b15
R2 a1 a2 a3 a4 b25
R3 a1 a2 a3 a4 a5
R4 a1 b42 a3 a4 a5
R5 a1 b52 a3 a4 a5
care avand al treilea rand numai cu simboluri a dovedeste ca descompunerea data este fara pierderi la uniune.
Teorema 5.3. Algoritmul 5.2 determina corect daca o descompunere este fara pierderi la uniune.
Demonstratie. Daca algoritmul nu produce un rand numai cu simboluri a se poate lua relatia r cu tupluri randurile tabloului obtinut care este de tipul R si indeplineste conditiile din F dar pentru care r @=/ m/@r(r) deoarece tuplul a1a2...an nu este in r dar este in m/@r(r) si deci descompunerea nu este fara pierderi la uniune. Reciproc, daca tabelul contine o linie cu simboluri a se poate identifica tabelul cu expresia calculului relational pe domenii
unde fiecare i este al i-lea rand din tabelul initial, acesta corespunzand functiei m/@r. Modificarile din algoritm transforma formula precedenta intr-o formula echivalenta (obtinuta prin identificarea variabilelor corespunzatoare)
care este o submultime a lui r si deci m/@r(r) C r. Cum incluziunea inversa este asigurata de lema 5.7 rezulta egalitatea ceea ce dovedeste ca descompunerea este fara pierderi la uniune.
Teorema 5.4. @r = este o descompunere fara pierderi la uniune a schemei relationale R in raport cu dependentele F daca si numai daca are loc una din cele doua relatii urmatoare:
F |= (R1 @O R2) -> (R1 - R2) sau F |= (R1 @O R2) -> (R2 - R1).
Demonstratia se face aratand ca rezultatul aplicarii algoritmului 5.2 concorda cu concluzia teoremei.
Exemplul 5.6. Daca R = ABC si F = atunci descompunerea lui R in AB si AC este fara pierderi la uniune deoarece AB @O AC = A, AB - AC = B si are loc A -> B. In schimb descompunerea lui R in AB si BC nu este fara pierderi la uniune deoarece AB @O BC = B, AB - BC = A, BC - AB = C si nu are loc nici-una din dependentele B -> A sau B -> C. Luand de exemplu r = se obtine @P/AB(r) = , @p/BC(r) = si de aici
@P/AB(r) |X| @P/BC(r) =
care este o relatie diferita de r.
Numim proiectia unei multimi de dependente F pe o multime de atribute Z si o notam cu @P/Z(F) multimea tuturor dependentelor X -> Y din F\+ pentru care XY C Z.
Lema 5.8. Fie R o schema relationala cu dependentele functionale F si fie @r = o descompunere a lui R fara pierderi la uniune in raport cu F. Pentru un i dat, fie Fi = @P/Ri(F) si fie @s = o descompunere fara pierderi la uniune in raport cu Fi. Atunci descompunerea lui R in este fara pierderi la uniune in raport cu F.
Demonstrarea acestei proprietati se bazeaza pe asociativitatea operatiei uniune naturala si pornind de la definitii se poate arata ca din elementele corespunzatoare la S1,...,Sm se poate reconstitui proiectia ri a unei relatii r dupa ri si apoi din r1,...,rk se poate reconstitui r.
Lema 5.9. Fie R, F si @r ca in lema 5.8 si fie @t = o descompunere a lui R in scheme relationale care le contine pe cele din @r. Atunci @t este de asemenea fara pierderi la uniune in raport cu F.
Demonstratia acestei proprietati se face folosind asociativitatea operatiei de uniune naturala, si deoarece proiectiile unei relatii r pe R1,..., Rk acopera pe r facand uniunea naturala cu celelalte proiectii se obtine cel mult o submultime a lui r insa din lema 5.7 rezulta si incluziunea pe dos de unde rezulta ca descompunerea este fara pierderi la uniune.
Spunem ca descompunerea @r = a schemei relationale R pastreaza dependentele F daca si numai daca dependentele lui F se deduc logic din reuniunea dependentelor @P/Ri(F) cu i = 1,2,...,k.
O descompunere poate sa pastreze dependentele dar sa nu fie fara pierderi la uniune. Un exemplu este relatia R = ABCD cu dependentele F = si descompunerea @r = .
De asemenea o descompunere poate sa fie fara pierderi la uniune dar sa nu pastreze dependentele dupa cum se vede din exemplul urmator.
Exemplul 5.7. Fie R = ABC cu dependentele F = . Descompunerea lui R in AC si BC este fara pierderi la uniune deoarece
(AC @O BC) -> (AC - BC)
si se aplica teorema 5.4. Proiectia lui F pe BC da numai dependentele triviale si pe AC da C -> A si cele triviale dar acestea nu determina logic pe AB -> C deci descompunerea nu este cu pastrarea dependentelor.
Se poate testa daca o descompunere este sau nu cu pastrarea dependentelor intr-un timp polinomial in raport cu dimensiunea lui F folosind algoritmul urmator.
Algoritmul 5.3. Fie R o schema relationala, F o multime de dependente functionale si @r = o descompunere a lui R.
Se defineste G = F1 U ... U Fk unde Fi = @P/Ri(F), i=1,2,...,k. Pentru fiecare dependenta functionala X -> Y a lui F se testeaza daca este in G\+ in felul urmator: se pleaca cu Z = X si atata timp cat mai apar modificari se calculeaza pentru fiecare i=1,2,...,k Z = Z U ((Z @O Ri)\+ @O Ri) inchiderea fiind luata in raport cu F. Daca in final Y C Z atunci dependenta poate fi dedusa logic din G, altfel nu. Daca proprietatea este valabila pentru toate dependentele din F atunci descompunerea este cu pastrarea dependentelor, altfel descompunerea este fara pastrarea dependentelor.
Exemplul 5.8. Fie R = ABCD, F = si descompunerea @r = . Se vede ca primele trei dependente ale lui F se gasesc chiar in G deci mai ramane de vazut daca si D -> A poate fi dedusa logic din G. Se pleaca cu Z = D si se obtine succesiv Z = D U ((D @O (AB))\+ @O AB) =D
, Z = D U ((D @O (BC))\+ @O BC) = D si Z = D U ((D @O (CD))\+ @O CD) = D U (D\+ @O CD) = D U (ABCD @O CD) = D U CD = CD. Reluand calculele obtinem Z = CD la combinarea cu AB si Z = BCD la combinarea cu BC iar la reluarea calculelor se obtine la combinarea cu AB Z = ABCD dupa care nu se mai fac alte schimbari in Z. Cum A este in Z se gaseste ca G |= D -> A si deci descompunerea este cu pastrarea dependentelor.
Teorema 5.5. Algoritmul 5.3 determina corect daca X -> Y este in G\+.
Demonstratie. De fiecare data cand se adauga un atribut in Z se foloseste o dependenta din G si deci in final Z reprezinta inchiderea lui X in raport cu G. Reciproc, daca X -> Y este in G\+ se considera etapele de aplicare a algoritmului 5.1 pana cand sunt gasite toate atributele din Y la gasirea inchiderii lui X in raport cu G. Fiecare pas al algoritmului presupune folosirea unei dependente U -> V din G care se gaseste de fapt intr-un @P/Ri(F). Prin inducrie dupa numarul pasilor se poate vedea ca U este inclus la un moment dat in Z de unde rezulta ca sigur la o noua folosire in algoritmul 5.3 a lui Ri va fi inclus si V in Z ceea ce completeaza demonstratia teoremei.
1.3. Dependente multivaloare
Fie R o schema relationala, X si Y submultimi ale lui R, vom spune ca exista o dependenta multivaloare a lui Y de X sau ca X determina multivaloare pe Y si vom nota X ->> Y daca pentru orice valoare a atributelor lui X sunt asociate valori pentru atributele lui Y care nu sunt corelate in nici-un fel cu atributele din R - X - Y. Formal, X ->> Y daca si numai daca pentru orice continut actual al relatiei R, oricare ar fi tuplurile u si v din r pentru care u[X] = v[X], r contine si tuplurile t si s cu t[X] = u[X], t[Y] = u[Y] si t[R-X-Y] = v[R-X-Y] respectiv s[X]= v[X], s[Y] = v[Y] si s[R-X-Y] = u[R-X-Y].
Exemplul 5.9. Sa consideram schema relationala R = CPOLSA unde C este pentru curs, P - profesor, O - ora, L - loc (sala), S - student si A - an de studiu si avand urmatoarele dependente functionale: C -> P (fiecare curs are un singur profesor), OL -> C (numai un curs se poate tine la o ora data intr-o sala data), OP -> L (la o anumita ora un profesor se poate afla in cel mult o sala), CS -> A (fiecare student urmeaza un curs intr-un anumit an de studiu), OS -> L (fiecare student se poate afla in cel mult o sala la un moment dat). La multimea dependentelor se poate adauga dependenta multivaloare C ->> OL care semnifica faptul ca fiecarui curs i se asociaza o multime de perechi de ore si sali care nu depind in nici-un fel de celelalte informatii. In schimb nu au loc in general dependentele multivaloare C ->> O sau C ->> L.
Si in cazul dependentelor multivaloare se pot descrie regulile de inferenta pentru determinarea dependentelor ce se pot deduce logic dintr-o multime de dependente date D cu atribute din multimea U si anume:
A1. (reflexivitate dependente functionale) |= X -> Y.
A2. (amplificare dependente functionale) |= XZ -> YZ.
A3. (tranzitivitate dependente functionale) |= X -> Z.
A4. (complementare dependente multivaloare) |= X ->> (U-X-Y).
A5. (amplificare dependente multivaloare) |= WX ->> VY.
A6. (tranzitivitate dependente multivaloare) |= X ->> (Z - Y).
A7. |= X ->> Y.
A8. |= X -> Z.
GATA
Teorema 5.6. (Beeri-Fagin-Howard) Axiomele A1-A8 sunt corecte si complete pentru dependentele functionale si multivaloare in sensul ca daca D este o multime de dependente functionale si multivaloare pe multimea atributelor U si D\+ este multimea dependentelor functionale si multivaloare ce se deduc logic din D (satisfacute de orice relatie care satisface dependentele din D), atunci elementele lui D\+ sunt elementele obtinute din D aplicand de un numar finit de ori axiomele A1-A8.
Demonstratia se face plecand de la definitii in mod asemanator cu demonstratia teoremei 5.1.
Din axiomele A1-A8 se pot deduce si alte reguli dintre care cele mai des utilizate sunt cele din lema urmatoare pe care le dam fara demonstratie.
Lema 5.10. Sunt adevarate urmatoarele reguli de inferenta:
B1. (reuniune dependente multivaloare) |= X ->> YZ.
B2. (pseudotranzitivitate dependente multivaloare)
|= WX ->> (Z - WY).
B3. (pseudotranzitivitate mixta) |= X -> (Z - Y).
B4. (descompunere dependente multivaloare)
|= .
Teorema 5.7. Daca U este multimea tuturor atributelor atunci se poate determina o partitie a multimii U - X in multimile de atribute Y1,Y2,...,Yk astfel incat pentru orice Z inclus in U - X, X ->> Z daca si numai daca Z se poate scrie ca o reuniune de multimi Yi1,Yi2,...,Yin.
Demonstratie. Se incepe cu multimea U - X. Sa presupunem ca la un moment dat am determinat multimile W1,...Wm care formeaza o partitie a lui U - X si astfel incat X ->> Wi, i=1,...,m. Daca exita o dependenta multivaloare X ->> Z si Z nu este reuniunea unora din elementele W1,...,Wm, se inlocuieste in sirul dat fiecare Wi cu multimile Wi @O Z si Wi - Z cand acestea sunt nevide. Din legea de descompunere rezulta ca X ->> (Wi @O Z) si X ->> (Wi - Z) si este usor de vazut ca sirul obtinut este tot o partitie a lui U - X. Numarul finit al atributelor asigura terminarea procesului de diviziune intr-un numar finit de pasi si regula reuniunii asigura ca orice reuniune de elemente din sir depinde multivaloare de X ceea ce demonstreaza teorema.
Multimea Y1,Y2,...,Yk construita prin procedeul din demonstratia teoremei precedente se numeste baza de dependente a lui X in raport cu D.
Exemplul 5.10. Pentru exemplul 5.9 din C ->> OL prin complementaritate se deduce C ->> PSA iar din C -> P aplicand axioma A7 deducem C ->> P care determina partitionarea lui PSA in P si SA. Cum nici-un alt atribut in afara de P si de C nu este determinat multivaloare de C rezulta ca baza de dependente a lui C in raport cu dependentele functionale si multivaloare date este .
Pentru a testa daca o dependenta multivaloare X ->> Y se deduce logic din D se calculeaza baza de dependente a lui X in raport cu D si daca Y - X se poate scrie ca o reuniune de elemente din baza de dependente atunci dependenta data se deduce logic din D, altfel nu.
Exemplul 5.11. Tinand seama de proprietatea anterioara si de exemplul 5.9 se poate deduce imediat ca sunt valabile dependentele C ->> CPSA, C ->> OLSA dar nu este satisfacuta C ->> PO sau altele asemanatoare.
Calculul efectiv al bazei de dependente se poate face eficient (polinomial) aplicand urmatorul algoritm:
Algoritmul 5.4. Fie M o multime de dependente multivaloare peste atributele U si X o submultime a lui U.
1. Fie T multimea multimilor Z C U pentru care exista W ->> Y in M cu W C X si
Z este oricare din multimile Y - X sau U - X - Y.
2. Se inlocuiesc in T oricare doua multimi Z1 si Z2 cu intersectie nevida cu
multimile Z1 - Z2, Z2 - Z1 si Z1 @O Z2, eliminand multimile vide. Fie S
rezultatul obtinut.
3. Pentru orice dependenta V ->>W din M pentru care exista Y in S care este
disjunct de V dar Y si W au intersectia nevida, se inlocuieste Y cu Y @O W si
Y - W in S. Baza de dependente este multimea S rezultata.
Ca si pentru dependentele functionale exista un criteriu simplu de a vedea daca o descompunere in doua componente este fara pierderi la uniune si in cazul dependentelor multivaloare dupa cum rezulta din teorema urmatoare.
Teorema 5.8. Fie R o schema relationala, D o multime de dependente functionale si multivaloare pe multimea atributelor lui R si @r = (R1,R2) o descompunere a lui R. Atunci @r este fara pierderi la uniune daca si numai daca (R1 @O R2) ->> (R1 - R2).
Demonstratie. Descompunerea @r este fara pierderi la uniune daca si numai daca pentru orice relatie r ce satisface D si pentru orice doua tupluri t si s din r, exista un tuplu in r astfel incat u[R1] = t[R1] si u[R2] = s[R2]. Dar tuplul u exista daca si numai daca t[R1 @O R2] = s[R1 @O R2] ceea ce duce la dependenta multivaloare din enuntul teoremei.
Se intalnesc situatii cand sunt valabile dependente multivaloare pe componente ale unei descompuneri fara a fi valabile pe relatia initiala. Aceste dependente se numesc dependente ascunse. O relatie r de tipul schemei relationale R satisface o dependenta multivaloare ascunsa X ->> Y | Z daca dependenta multivaloare X ->> Y este satisfacuta de relatia @P/XUYUZ(r). Exemple de dependente ascunse sunt C ->> S | P sau C ->> P | S unde P inseamna cursuri necesare de urmat anterior.
1.4. Dependente generalizate
Pana acum am definit dependentele functionale, dependentele multivaloare si dependentele multivaloare ascunse. In afara de acestea se mai poate considera dependenta si conditia de descompunere fara pierderi la uniune a unei scheme relationale numita dependenta de uniune si notata |X| (R1,R2,...,Rk) care este satisfacuta de relatia r continut actual al relatiei R1 U ... U Rk daca si numai daca uniunea naturala a proiectiilor lui r pe fiecare Ri este egala cu r. Toate aceste tipuri de dependente pot fi exprimate unitar prin dependentele generalizate pe care le definim in continuare.
O dependenta generalizata peste schema relationala A1...An este o expresie de forma (t1,...,tk)/t, unde fiecare ti este un n-tuplu de simboluri si t este fie un alt tuplu, in care caz avem o dependenta generatoare de tupluri, fie o expresie x = y cu x si y dintre simbolurile ce apar anterior, in acest caz avem o dependenta generatoare de egalitati. Numim (t1,...,tk) ipoteza dependentei si t concluzia dependentei. Un simbol din concluzie care nu mai apare in alta parte se numeste unic. O dependenta generalizata se numeste ascunsa daca are cel putin un simbol unic si se numeste completa daca nu contine nici-un simbol unic.
O dependenta functionala nebanala X -> Y se exprima printr-un numar de dependente generalizate egal cu numarul elementelor multimii Y - X cu ipoteza formata din doua tupluri ce contin simboluri comune pentru atributele din X si simboluri distincte pentru celelalte atribute iar concluzia contine o egalitate intre simboluri din cele doua tupluri pentru un atribut din Y - X.
O dependenta multivaloare de tipul X ->> Y se exprima ca o dependenta generalizata cu ipoteza formata din doua tupluri care au aceleasi simboluri pentru atributele din X si simboluri distincte in rest iar concluzia este un tuplu cu simboluri din primul tuplu pentru atributele XY si cu simbolurile din al doilea tuplu in rest.
O dependenta multivaloare ascunsa X ->> Y | Z se poate reprezenta ca o dependenta generalizata cu ipoteza formata din doua tupluri care au aceleasi valori pentru 22122b12w atributele lui X si valori diferite pentru celelalte atribute iar concluzia coincide cu ipotezele pe atributele lui X, are valorile din primul tuplu pentru atributele lui Y, are valorile din al doilea tuplu pentru atributele din Z si are simboluri unice in rest.
O dependenta de uniune se poate reprezenta ca o dependenta generalizata cu ipoteza continand un numar de tupluri egal cu numarul relatiilor din descompunere ce contin simboluri comune pentru aparitiile unui atribut in mai multe relatii pentru tuplurile corespunzatoare relatiilor in care apare acel atribut si simboluri diferite in rest iar concluzia contine simbolul asociat fiecarui atribut in ipoteza. Evident, concluzia nu are simboluri unice deoarece fiecare atribut apare cel putin intr-o componenta.
Pentru simplificarea notatiei, in tabelele asociate dependentelor generalizate se convine sa nu se mai noteze simbolurile care au o singura aparitie (ipoteza+concluzie).
Fie S si T doua multimi de simboluri. Spunem ca h este o aplicatie de simboluri daca pentru fiecare a din S se defineste h(a) ca fiind un element al lui t. Daca s = a1a2...an este un tuplu de simboluri se defineste h(s) ca fiind cuvantul obtinut prin concatenare h(a1)h(a2)...h(an). Daca s1s2..sk este o multime de tupluri cu simboluri din S si t1t2...tm este o multime de tupluri cu simboluri din T vom spune ca exista o aplicatie de simboluri de la prima multime de tupluri la a doua multime de tupluri daca si numai daca exista o aplicatie de simboluri h de la S la T astfel incat pentru orice i sa existe un j cu h(si)=tj.
Exemplul 5.12. Fie A = si B = . Exista mai multe aplicatii de simboluri de la A la B. De exemplu aplicatia h cu h(a) = h(f) = x, h(b) = h(d) = y si h(c) = h (e) = z are drept imagine pentru toate trei elementele lui A elementul xyz din B. Aplicatia g(a) = x, g(b) = g(d) = y, g(c) = g(e) = z si g(f) = w transforma abc si ade in xyz si pe fbe in wyz. Nu exista o aplicatie de simboluri care sa duca abc in xyz si ade in wyz daca x si w sunt simboluri distincte deoarece in acea aplicatie lui a i s-ar asocia atat x cat si w ceea ce nu este posibil.
O relatie r satisface o dependenta generalizata (t1,...,tn)/t daca pentru orice aplicatie de simboluri h de la multimea tuplurilor din ipoteza dependentei generalizate la r se poate extinde h la orice sibol unic din t astfel incat h(t) sa apartina lui r. Analog, spunem ca r satisface dependenta generalizata (t1,...,tn)/a=b daca pentru orice aplicatie de simboluri h de la ipoteza la r sa aiba loc egalitatea h(a) = h(b).
Exemplul 5.13. Fie d dependenta din fig. 5.1.a si relatia r din fig. 5.1.b. Deoarece in prima coloana a tuplurilor din ipoteza figureaza acelesi simbol a1 rezulta ca aplicatia de simboluri trebuie sa transforme tuplurile din ipoteza in tupluri care sa aiba pe primul loc aceleasi valori. Daca se ia h(a1) = 5 rezulta ca ambele tupluri sunt duse in tuplul 514 al lui r si deci h(b1) = h(b2) = 1 si h(c1) = h(c2) = 4 care se poate extinde luand h(a2) = 5 obtinand h(a2b1c2) = 514 care este un tuplu din r. Daca h(a1) = 0, o aplicatie de simboluri transforma cele doua tupluri din ipoteza in multimea primelor trei tupluri ale lui r si deci h(b1) este 1 sau 3 si h(c2) este 2 sau 4 dar pentru combinatiile 12, 32 si 34 se poate lua h(a2) = 0 si pentru combinatia 14 se poate lua h(a2) = 5 obtinand de fiecare data pentru h(a2b1c2) un tuplu al lui r.
Deci r satisface d.
a) a1 b1 c1 b) 0 1 2
a1 b2 c2 0 3 4
__________________ 0 3 2
a2 b1 c2 5 1 4
Figura 5.1.
Fie dependenta d = (s1,...,sk)/a=b si o relatie r = . Spunem ca se poate aplica d la r daca exista o aplicatie de simboluri h de la multimea s1s2...sk la multimea t1t2...tm. Efectul aplicarii lui d la r folosind aplicatia de simboluri h este obtinut prin identificarea simbolurilor h(a) si h(b) ori de cate ori apar in r.
Pentru dependente d = (s1,...,sk)/s se aplica d la r folosind aplicatia de simboluri h adaugand la r tuplul h(s). Pentru fiecare simbol unic c din s se creaza un simbol care nu mai apare in r si se defineste h(c) noul simbol creat.
Exemplul 5.14. Aplicarea dependentei generalizate (abc,ade,fbe)/a=f la relatia r = folosind aplicatia de simboluri g din exemplul 5.12 cu g(a) = x si g(f) = w identifica in r pe w cu x obtinand r = . Daca se aplica dependenta (abc,ade,fbe)/abq lui r folosind g atunci se adauga lui r tuplul xyu deoarece g(a) = x, g(b) = y si q fiind un simbol unic se introduce un nou simbol u si se defineste h(q) = u.
Se poate defini un proces care stabileste daca D |= d unde D este o multime de dependente generalizate si d este o dependenta generalizata. Procesul devine algoritm in cazul cand D contine numai dependente complete (fara elemente unice). Se incepe cu ipotezele dependentei d si se aplica pe rand inferentele rezultate din dependentele date D. Daca la un moment dat se obtine consecinta lui d rezulta ca d se poate deduce logic din D. Daca procesul se termina fara a gasi consecinta lui d rezulta ca d nu se poate deduce logic din D, rezultatul obtinut la terminarea procesului este un contraexemplu de relatie care satisface D dar nu satisface d. Procesul poate continua infinit daca D are elemente unice.
Exemplul 5.15. Pentru a verifica expresia
|= A ->> C|D
se construiesc dependentele generalizate din fig.5.2. Se incepe cu relatia r = la care se poate aplica dependenta din fig. 5.2.a luand ca aplicatie de simboluri h(a1)=a4, h(b1)=b5, h(c1)=c6, h(d1)=d7, h(b2)=b4, h(c2)=c5 si h(d2)=d6 care se extinde punand h(d3)=d8 (simbol nou) si deci se adauga lui r tuplul a4b5c5d8. Aplicand relatiei obtinute dependenta din fig. 5.2.b folosind o aplicatie de simboluri care transfeorma ipoteza in ultimile doua tupluri ale relatiei se obtine d7=d8 si deci relatia r devine r = si cum ultimul tuplu coincide cu concluzia din fig. 5.2.c in afara de coloana B unde apare un element unic b6 se poate trage concluzia ca expresia data este adevarata.
a1 b1 c1 d1 a2 b3 c3 d4
a1 b2 c2 d2 a3 b3 c4 d5
_____ _______ ______ ___________ _____ _______ ______ ___________
a1 b1 c2 d3 d4 = d5
a) A ->> B|C b) B -> D
a4 b4 c5 d6
a4 b5 c6 d7
_____ _______ ______ ___________
a4 b6 c5 d7
c) A ->> C|D
Figura 5.2.
2. Forme normale ale bazelor de date relationale
Pentru a deosebi anumite calitati specifice ale unor relatii s-au facut mai multe clasificari. Dintre aceste clasificari cea mai frecvent utilizata este clasificarea in forme normale. Se spune ca o relatie este intr-o forma normala particulara daca satisface o multime de constrangeri data. Transformarea unei relatii intr-o multime de relatii de un anumit tip se numeste normalizare. Primele trei forme normale au fost definite de Codd iar a patra si a cincia forma normala au fost definite de Fagin.
Principalele scopuri urmarite in procesul de normalizare sunt: eliminarea unor redondante, evitarea unor anomali de reactualizare, producerea unui proiect care sa reprezinte cat mai fidel modelul real (usor de inteles si eventual de modificat), stabilirea unor constrangeri de integritate simple si altele.
2.1. Prima forma normala (1NF)
Se spune ca o relatie este in prima forma normala (1NF) daca fiecarui atribut ii corespunde o valoare indivizibila (atom), deci orice valoare nu poate fi o multime sau un tuplu cu valori in anumite domenii, nu pot sa apara grupuri repetitive.
De exemplu, pentru o relatie in prima forma normala care contine atributul DATA se considera valoarea asociata sub forma zz-ll-aa fara a se putea descompune dupa ziua, luna sau anul corespunzator valorii respective.
Relatiile in prima forma normala pot fi vizualizate sub forma de tabele, permit o referire simpla a datelor prin indicarea numelui tabelului, a coloanei sau atributului si a chei tuplului din care face parte informatia respectiva (adresare de tip sistem de coordonate), operatorii pentru aceste relatii sunt mai simpli si in numar mai mic si permit definirea unor tehnici de proiectare si utilizare a bazelor de date.
2.2. A doua forma normala (2NF)
Fie R o schema relationala si A un atribut din R. Vom spune ca A este un atribut prim al lui R daca A apare in cel putin o cheie a lui R, altfel vom spune ca A este un atribut neprim.
Spunem ca schema relationala R este in a doua forma normala daca este in prima forma normala si pentru orice dependenta X -> A cu A atribut neprim necontinut in X care are loc in R nu exista nici-o cheie care sa contina strict pe X.
Cu alte cuvinte, o relatie R este in 2NF daca este in 1NF si orice atribut neprim este complet dependent de orice cheie.
Exemplul 5.16. Schema relationala R = ABCD cu dependentele F = nu este in a doua forma normala deoarece singura cheie este AC, B este un atribut neprim, are loc A -> B si A este inclusa strict in cheia AC.
A doua forma normala inlatura redondantele si anomaliile la modificari. Relatia MAGAZINE data la inceputul capitolului nu este in a doua forma normala deoarece dependenta NUMEMAG -> ADRESAMAG are in partea stanga o submultime proprie a singurei chei NUMEMAG MARFA si partea din dreapta este un atribut neprim. De aici rezulta si problemele privind lucrul cu o astfel de relatie.
A doua forma normala poate sa contina asa-numitele dependente tranzitive ce se deduc prin aplicarea axiomei tranzitivitatii din alte doua dependente functionale. Dependentele tranzitive pot sa produca anomali la insertie, stergere si modificare dupa cum am vazut mai sus.
Trecerea unei relatii din 1NF de forma
R ( A, B, C, D )
PRIMARY KEY ( A, B )
R.A --> R.D
in 2NF se face prin descompunerea lui R in relatiile
R1 ( A, D )
PRIMARY KEY ( A )
R2 ( A, B, C )
PRIMARY KEY ( A, B )
FOREIGN KEY ( A ) REFERENCES R1
2.3. A treia forma normala (3NF)
Spunem ca schema relationala R este in a treia forma normala daca este in a doua forma normala si pentru orice dependenta X -> A cu A necontinut in X care are loc in R fie X contine o cheie fie A este un atribut prim.
Cu alte cuvinte, relatia R este in 3NF daca si numai daca atributele care nu apar in chei sunt independente intre ele si sunt complet dependente de cheia primara (atributele prime nu sunt dependente tranzitiv de cheia primara).
Exemplul 5.17 Relatia R = ABC cu dependentele F = este in a treia forma normala deoarece avand cheile AC si BC toate atributele sunt prime si deci nu exista nici-un atribut neprim.
Orice relatie in a treia forma normala este in a doua forma normala. Reciproca nu este adevarata dupa cum se vede din urmatorul exemplu.
Exemplul 5.18. Fie relatia R = ABCD cu dependentele functionale F = care are unica cheie AB. Aceasta relatie nu este in a treia forma normala deoarece exista dependenta AC -> D cu D neprim si AC nu contine o cheie. Cum nici-o submultime proprie a lui AB nu determina functional nici pe C nici pe D rezulta ca R este in a doua forma normala.
A tria forma normala inlatura redondantele, anomaliile la modificari, anomaliile la insertie si anomaliile la stergere.
Orice schema relationala R cu dependentele F se poate descompune cu pastrarea dependentelor in relatii care sunt in a treia forma normala prin metoda data de algoritmul urmator.
Algoritmul 5.5. Fie R o schema relationala si F o multime minimala de dependente functionale.
1. Pentru fiecare atribut A din R care nu apare in nici-o dependenta functionala se costruieste o schema relationala cu singurul atribut A (care este evident in 3NF) se scoate la iesire schema relationala A si se elinima A din R.
2. Daca o dependenta din F contine toate atributele lui R se scoate R la iesire si STOP.
3. Pentru fiecare multime de dependente din F de tipul X -> A1, X -> A2,
..., X -> Ak se scoate la iesire X -> A1A2...Ak si STOP.
Exemplul 5.19. Aplicand algoritmul 5.5. pentru schema relationala R = CPOLSA unde C inseanma curs, P - profesor, O - ora, L - loc (sala), S - student si A - an de studiu si avand urmatoarea multime minimala de dependente functionale: C -> P (fiecare curs are un singur profesor), OL -> C (numai un curs se poate tine la o ora data intr-o sala data), OP -> L (la o anumita ora un profesor se poate afla in cel mult o sala), CS -> A (fiecare student urmeaza un curs intr-un anumit an de studiu), OS -> L (fiecare student se poate afla in cel mult o sala la un moment dat) se obtine descompunerea cu pastrarea dependentelor avand urmatoarele scheme relationale care sunt evident in 3NF: CP, OLC, OPL, CSA si OSL.
Teorema 5.9. Algoritmul 5.5 calculeaza o descompunere cu pastrarea dependentelor in scheme relationale de tip 3NF pentru orice schema relationala.
Demonstratie. Faptul ca sunt pastrate dependentele rezulta imediat din faptul ca fiecare dependenta din F se regaseste in cel putin una din componentele obtinute. Sa aratam ca aceste componente sunt in 3NF. Sa presupunem ca ar exista o componenta de tipul C = YB1B2...Bk produsa de algoritm care nu este in 3NF si fie dependenta functionala X -> A dedusa din F care nu indeplineste conditia din 3NF, deci A este neprim si X nu contine o cheie. Y este o cheie pentru C deoarece din Y -> Y (reflexivitate) si Y -> Bi (sunt in F) rezulta Y -> C si daca ar exista o submultime proprie Z a lui Y care sa fie cheie pentru C s-ar obtine o multime de dependente echivalenta cu F inlocuid fiecare dependenta de forma Y -> B cu Z -> B deci F nu ar fi minimala. Deci putem considera ca exista j cu A = Bj, A nu se afla in X care este continut in C. Y fiind cheie pentru C rezulta Y -> X este dedusa logic din F aplicand legea reuniunii pentru dependentele Y -> Ai pentru fiecare atribut Ai din X, care sunt diferite de Y -> Bj deoarece A nu este in X. Dar in acest caz Y -> Bj poate fi dedusa logic prin tranzitivitate din Y -> X si X -> A = Bj ceea ce dovedeste ca F nu ar fi minimala. Deci componentele obtinute prin algoritm sunt 3NF.
Teorema 5.10. Fie @r descompunerea cu pastrarea dependentelor a schemei relationale R obtinuta prin algoritmul 5.5 si K o cheie a lui R. Atunci @s = @r U este o descompunere a lui R cu toate componentele in 3NF cu pastrarea dependentelor si fara pierderi la uniune.
Demonstratie. Din definitia unei chei rezulta ca schema relationala ce contine numai atributele unei chei este in 3NF, deci @s are toate componentele in 3NF. Cum @s are cel putin dependentele lui @r care acopera pe F rezulta ca descompunerea @s este cu pastrarea dependentelor. Faptul ca descompunerea este fara pierderi la uniune se verifica aplicand algoritmul 5.2 prin care se obtine pe linia X numai simbolul a, deoarece X este cheie si pentru fiecare nou atribut A ce se adauga in calculul lui X\+ se adauga in coloana corespunzatoare lui A si in linia lui X simbolul a.
Descompunerile obtinute din enuntul teoremei precedente nu sunt minimale si se pot elimina acele componente care nu sunt necesare pentru pastrarea proprietatilor.
Trecerea unei relatii din 2NF de forma
R ( A, B, C )
PRIMARY KEY ( A )
R.B --> R.C
in 3NF se face prin descompunerea lui R in relatiile
R1 ( B, C )
PRIMARY KEY ( B )
R2 ( A, B )
PRIMARY KEY ( A )
FOREIGN KEY ( B ) REFERENCES R1
Pentru relatiile in 3NF singurele informatii care trebuie furnizate sistemului sunt cele ce indica cheia principala deoarece toate dependentele sunt deduse fiind de forma "orice atribut necheie este dependent functional de cheie".
2.4. Forma normala Boyce-Codd (BCNF)
Spunem ca o relatie R cu dependentele F este in forma normala Boyce-Codd daca oricare ar fi dependenta X -> A cu A atribut necontinut in X exista o cheie a lui R continuta in X.
Orice relatie in forma normala Boyce-Codd este in a treia forma normala dar reciproca nu este adevarata dupa cum se vede din exemplul urmator.
Exemplul 5.20. Relatia R = ABC cu dependentele F = este in a treia forma normala dar nu este in forma normala Boyce-Codd deoarece cheile acestei relatii sunt AC si BC iar pentru dependenta C -> A partea stanga nu contine nici-una din cele doua chei.
Daca orice relatie se poate descompune fara pierderi la uniune in forme normale Boyce-Codd nu acelasi lucru se poate spune despre descompunerea cu pastrarea dependentelor. Se vede imediat ca pentru relatia din exemplul 5.20 nu se poate face nici-o descompunere a lui ABC care sa dea forme normale Boyce-Codd si care sa permita deducerea dependentei functionale AB -> C. Descompunerea fara pierderi la uniune in forme normale Boyce-Codd in raport de proiectiile dependentelor functionale pe componentele respective se poate face aplicand urmatorul algoritm:
Algoritmul 5.6. Fie R o schema relationala si F multimea dependentelor functionale. Fie @r = . Pentru fiecare schema relationala S din @r care nu este in forma normala Boyce-Codd, deci pentru care exista X -> A cu A neprim si X necontinand o cheie se inlocuieste S in @r cu S1 = AX si S2 = S - A. Procesul continua pana cand toate componentele lui @r sunt in BCNF.
Corectitudinea algoritmului se verifica prin faptul ca la fiecare descompunere numarul atributelor din componente este mai mic decat multimea descompusa, ca fiecare descompunere este fara pierderi la uniune dupa cum rezulta din teorema 5.4 si nu afecteaza descompunerea fara pierderi la uniune pentru relatia initiala dupa cum rezulta din lema 5.8.
Exemplul 5.21. Sa consideram schema relationala R si dependentele functionale F din exemplul 5.9. Singura cheie este OS. Aplicand algoritmul 5.6 sa consideram dependenta CS -> A care nu indeplineste conditia din definitia BCFN rezultand descompunerea CSA si CPOLS. Proiectia lui F pe CSA are acoperirea minimala CS -> A si cheia CS de unde rezulta imediat ca CSA este in BCNF.
Proiectia lui F pe CPOLS are acoperirea minimala F1 = cu singura cheie OS. Pentru acesta ultima relatie consideram dependenta C -> P care nu indeplineste conditia din definitia BCNF ce descompune CPOLS in CP si COLS avand acoperirile minimale pentru proiectia dependentelor C -> P pentru CP si CO -> L, OS -> L si OL -> C pentru COLS. CP este BCNF dar COLS nu avand cheia OS si dependenta CO -> L care nu respecta conditia pentru BCNF si care produce descompunerea COL si COS ambele fiind in BCNF. Deci descompunerea lui CPOLSA in BCNF poate fi CSA, CP, COL si COS. In descompunerea data nu se pastreaza dependenta PO -> L.
Problema de a determina daca o relatie este in BCNF sau nu este o problema NP-completa deci nu exista algoritmi eficienti pentru a o rezolva in general.
2.5. A patra forma normala (4NF)
Fie R o schema relatioanla si D o multime de dependente functionale si multivaloare pe R. Spunem ca R este in a patra forma normala (4NF) daca pentru orice dependenta multivaloare X ->> Y cu Y neinclusa in X si XY @=/ R exista o cheie a lui R inclusa in X.
Cu alte cuvinte, o relatie R este in a patra forma normala daca este in BCNF si orice dependenta multivaloare este de fapt o dependenta functionala.
Daca D contine numai dependente functionale si R este in 4NF atunci R este in BCNF ceea ce se deduce usor din definitii.
Se poate gasi o descompunere @r = a lui R fara pierderi la uniune in raport cu D si in care toate componentele sa fie in 4NF cu procedeul urmator. Se incepe cu @r = . Daca @r contine o componenta care nu este in 4NF in raport cu proiectia lui D pe multimea atributelor S din componenta respectiva exista o dependenta X ->> Y in S cu Y necontinut in X, XY diferit de S si X nu contine o cheie a lui S. Se poate considera X si Y disjuncte deoarece din dependenta precedenta rezulta aplicand axiomele A1, A7 si legea descompunerii ca X ->> (Y - X). Se inlocuieste S cu S1 = XY si S2 = S - Y care sunt doua scheme relationale cu mai putine atribute decat S. Din teorema 5. , deoarece (S1 @O S2) ->> (S1 - S2) descompunerea lui S in S1 si S2 este fara pierderi la uniune in raport cu proiectia lui D pe S. Aplicand procedeul anterior, dupa un numar finit de pasi se obtine descompunerea fara pierderi la uniune a lui R in 4FN.
Proiectia dependentelor lui D pe multimea de atribute S se poate obtine cu formula urmatoare
@P/S(D) = U
Exemplul 5.22. Pentru
relatia din exemplul 5.9 dependenta C ->> OL nu respecta conditia din 4NF
deoarece C nu contine o cheie (singura cheie a relatiei este SO). Se descompune
relatia CPOLSA in
C ->> P care rezulta din C -> P si C nu contine o cheie. Se descompune CPSA in CP si CSA care sunt ambele in 4NF. Deci o descompunere a relatiei CPOLSA fara pierderi la uniune in 4FN este .
2.6. A cincia forma normala (5NF)
Se spune ca o relatie R satisface dependenta de uniune (join dependency sau pe scurt JD) * ( X, Y, ..., Z ) daca si numai daca R este egal cu uniunea proiectiilor lui R pe X, Y, ..., Z, acestea fiind submultimi ale lui R.
O relatie R este in cea de-a cincia forma normala numita si "forma normala proiectie-uniune" (pe scurt PJ/NF sau 5NF) daca si numai daca orice dependenta de uniune a lui R este o consecinta a unui candidat de chei a lui R.
Orice relatie care este in 5NF este si in 4NF deoarece fiecare dependenta multivaloare poate fi privita ca un caz particular de dependenta de uniune. Orice relatie poate fi descompusa fara pierderi la uniune intr-o multime de relatii care sunt in 5NF. Se garanteaza faptul ca o relatie in 5NF nu contine anomalii ce pot fi eliminate luand proiectiile.
Fagin a dat un algoritm prin care se poate testa daca o JD este o consecinta a unei multimi de candidati de cheie. In consecinta pentru a spune daca o relatie R este in 5NF este suficienta cunoasterea candidatilor de cheie si a tuturor dependentelor de uniune din R.
Procesul de normalizare a relatiilor se poate descrie in felul urmator:
1. Se proiecteaza relatia initiala in 1NF pe alte relatii pentru a elimina
dependentele functionale care nu sunt complete. Se obtine o multime de
relatii in 2NF.
2. Se proiecteaza relatiile obtinute in pasul 1 pe alte relatii pentru a elimina
dependentele functionale tranzitive. Se obtine o multime de relatii in 3NF.
3. Se proiecteaza relatiile obtinute in pasul 2 pe alte relatii pentru a elimina
dependentele in care partea din stanga nu este o supracheie. Se obtine o
multime de relatii in BCNF.
4. Se proiecteaza relatiile obtinute in pasul 3 pe alte relatii pentru a elimina
toate dependentele multivaloare care nu sunt si dependente functionale. Se
obtine o multime de relatii in 4NF.
5. Se proiecteaza relatiile obtinute in pasul 4 pe alte relatii pentru a elimina
orice dependenta de uniune care nu este implicata de o cheie. Se obtine o
multime de relatii in 5NF.
3. Integritate
Integritatea bazelor de date este in principiu data de corectitudinea informatiilor continute si presupune detectarea, corectarea si prevenirea diferitelor erori neintentionate privind datele introduse in bazele de date. Conditiile de integritate numite si reguli de integritate nu permit introducerea in baza de date a unor date aberante si sunt exprimate prin diferitele conditii puse asupra datelor. O serie de conditii sunt de tip structural, legate de anumite egalitati intre valori, si exprimate prin dependente functionale sau prin declararea unor campuri cu valori unice (de cele mai multe ori aceste campuri sunt chei). O alta serie de conditii de integritate privesc valorile actuale memorate in baza de date, permitand luarea unor valori numai dintr-un anumit domeniu sau stabilind relatii aritmetice intre diferite campuri.
Pot fi considerate mai multe criterii de clasificare a regulilor de integritate. Un prim criteriu priveste unitatea la care se aplica o constrangere si in acest caz exista constrangeri pe domenii (ce privesc anumite valori pentru atribute) sau constrangeri pe tabele sau relatii. Costrangerile pe tabele pot fi unituplu (se refera la fiecare tuplu in parte) sau multituplu (se refera la combinatii de mai multe tupluri), aceasta ultima clasa putand avea o subclasa de constrangeri ce folosesc functiile agregate. Un alt criteriu de clasificare este acela prin care se deosebesc regulile de integritate ce se refera la diferitele stari ale bazei de date de regulile ce se refera la tranzitia dintr-o stare in alta. Constrangerile mai pot fi clasificate si din punct de vedere al momentului in care se aplica ele puntand avea reguli imediate (ce se verifica in momentul in care se efectueaza operatia indicata) sau reguli amanate (ce se verifica numai dupa ce au fost executate si alte operatii asociate dar inainte de a modifica baza de date). Criteriile mai pot fi impartite in criterii generale, aplicabile tuturor relatiilor din baza de date si criterii particulare, care se pot aplica numai la anumite relatii.
Regulile de integritate se aplica relatiilor de baza in care sunt reprezentate efectiv datele bazei de date. Dintre regulile generale ce se aplica in modelul relational cel mai des folosite sunt regulile ce privesc cheile principale (unicitatea valorilor cheilor principale in cadrul relatiei) si cheile straine (necesitatea existentei unei chei principale din relatia asociata cu valoarea cheii straine nenule) numita constrangere referentiala.
Constrangerile de domeniu sunt intotdeauna constrangeri de stare si imediate. Aceste constrangeri se pot referi la tipul de date pentru un atribut, la o lista de valori posibile, la un ordin de marime, la un format sau o forma, la o condifie exprimata cu o formula logica sau la o procedura care este apelata de cate ori are loc o modificare pentru domeniul specificat.
Exemplul 5. . Constrangerile de domeniu pentru a exprima o data calendaristica pot fi exprimate intr-un pseudolimbaj in felul urmator:
CREATE DOMAIN ZI CHAR(2)
CHECK IS_INTEGER(ZI) AND NUM(ZI) >= 1 AND NUM(ZI) <= 31;
CREATE DOMAIN LUNA CHAR(2)
CHECK IS_INTEGER(LUNA) AND NUM(LUNA) >= 1 AND NUM(LUNA) <= 12;
CREATE DOMAIN AN CHAR(2)
CHECK IS_INTEGER(AN) AND NUM(AN) >= 0 AND NUM(AN) <= 99;
CREATE DOMAIN DATA(ZZ DOMAIN(ZI), LL DOMAIN(LUNA), AA DOMAIN(AN))
CHECK IF NUM(LL) IN (4,6,9,11) THEN NUM(ZZ) < 31
AND IF NUM(LL) = 2 THEN NUM(ZZ) < 30
AND IF NUM(LL) = 2 AND MOD(NUM(AA),4) = 0 AND
MOD(NUM(AA),100) <> 0 THEN NUM(ZZ) < 29;
Verificarea ca in fiecare tuplu al unei relatii de baza in campurile corespunzatoare cheii principale sa apara valori diferite de null, numita regula integritatii entitatii, este un exemplu de constrangere de integritate de relatie unituplu. Aceasta regula se mai poate enunta si sub forma: intr-o baza de date relationala nu se inregistreaza nici-o informatie despre ceva ce nu poate fi identificat.
Un exemplu de constrangeri de integritate de relatii de tip multituplu sunt numite constrangeri referentiale si se exprima prin necesitatea de a avea pentru chiele straine, daca nu sunt nule, valori corespunzatoare uneia din cheile primare existente in relatia referita. Aceasta verificare are loc de cate ori se insereaza un nou tuplu ce contine o cheie straina sau se modifica valoarea unei chei straine a unui tuplu, semnalandu-se eventualele neconcordante si anuland modificarile. Verificarea unicitatii cheii primare si constrangerile rezultate din dependentele functionale si multivaloare sunt alte exemple de acelasi tip.
Costrangerile de integritate pot fi exprimate prin intermediul limbajului de prelucrare a datelor sub forma unei egalitati sau ca o relatie intre rezultatele a doua cereri.
Exemplul 5. . In baza de date cu magazinele se poate impune conditia ca o comanda sa fie luata in consideratie numai daca este facuta de un cumparator din lista celor existenti in sistem, ceea ce se poate exprima prin
@P/NUME(COMENZI) @C= @P/NUME(CUMPARATORI)
iar conditia de a nu avea cumparatori cu cont negativ se poate exprima prin
@P/NUME(CUMPARATORI) = @P/NUME(@S/CONT@>=0(CUMPARATORI))
Verificarea conditiilor se face prin intermediul comenzilor impuse la definirea datelor. De exemplu in sistemul DBTG se pot include in declaratiile seturilor si ale inregistrarilor instructiuni de forma
ON <lista comenzi> CALL <procedura>
unde lista de comenzi este o submultime a multimii pentru seturi si respectiv pentru inregistrari iar procedura este o procedura de testare a diferitelor valori pentru operatiile indicate. Procedura poate fi scrisa in COBOL si poate sa foloseasca si elemente din limbajele de descriere si prelucrare ale datelor. O astfel de comanda se executa de cate ori se face o operatie din lista indicata asupra datelor definite, putandu-se eventual impiedica efectuarea operatiei daca nu sunt indeplinite conditiile impuse.
In sistemul QBE o prima verificare este facuta in legatura cu unicitatea valorilor pentru atributele declarate cheie in operatiile de inserare si modificare semnalandu-se cazurile exceptie fara a se mai efectua operatia.
Pentru fiecare relatie in parte sistemul QBE asociaza o tabela de constrangeri. Se pot crea constrangeri pentru relatia R punand pentru fiecare cate un rand in scheletul de tabel al lui R avand in prima coloana o expresie
I. CONSTR (<lista conditii>).I.
unde lista de conditii poate sa contina I.(inserare), D.(stergere), U.(modificare) sau identificatori de conditii definite de utilizatori. Pe aceeasi linie se pun in dreptul atributelor diferitele conditii ce trebuiesc indeplinite prin metodele date in limbajul de prelucrare a datelor.
Exemplul 5. . Pentru a impune ca nici-un cumparator sa nu aiba mai mult de 100000 lei datorii se pune in scheletul CUMPARATORI conditia:
CUMPARATORI | NUME | ADRESA | CONT |
I.CONSTR(I.U.).I. | | | >=-100000 |
| | | |
si conditia ca orice comanda acceptata sa contina marfa vanduta de cel putin un magazin se poate exprima prin scheletele COMENZI si MAGAZINE urmatoare:
COMENZI | NR_COM | NUME | MARFA | CANTITATE |
I.CONSTR(I.).
| | | | |
MAGAZINE | NUMEM | ADRESAM | MARFA | PRET |
| | | _portocale | |
| | | | |
Identificatorii de conditii definite de utilizatori sunt utilizati pentru delimitarea datelor pentru care sunt aplicate conditiile.
Exemplul 5. . Pentru a impune conditia ca tot timpul Popescu Dan sa aiba mai putin de 100000 lei datorii se poate folosi un identificator PD astfel
CUMPARATORI | NUME | ADRESA | CONT |
PD | Popescu Dan | | |
I.CONSTR(PD).I. | | | > -100000 |
| | | |
Se pot impune si restrictii pentru noile valori in raport de valorile existente in baza de date.
Exemplul 5. . Pentru a impune ca noile preturi ale fiecarui produs sa nu creasca mai mult de 10% fata de preturile vechi se poate formula constrangerea:
MAGAZINE | NUMEM | ADRESAM | MARFA | PRET |
I.CONSTR(U.).I. | _magazin | | _portocale | <=1.1*_p |
I. | _magazin | | _portocale | _p |
| | | | |
Se pot tipari constrangerile unei relatii daca se pune in scheletul relatiei sub nume comanda P.CONSTR.P. sau numai de un anumit tip cu comanda P.CONSTR(T.).P. unde T este una din literele I, D sau U. Se poate elimina o constrangere punand in schelet comanda D.CONSTR(<lista conditii>) urmata in coloanele atributelor de descrierea constrangerii respective.
In limbajul QUEL se poate construi o conditie de integritate prin instructiunea de forma urmatoare:
DEFINE INTEGRITY ON tabel IS conditie
Constrangerile de integritate sunt numerotate si tinute intr-un catalog INGRES. Numarul unei constrangeri se poate afla cu instructiunea HELP INTEGRITY si este utilizat de exemplu pentru anularea unei constrangeri printr-o instructiune de forma
DESTROY INTEGRITY tabel nr-constrangere
In legatura cu integritatea datelor este si protectia datelor pentru diferite evenimente de avarie cum ar fi: caderea sistemului cauzata de defectarea unor componente hardware sau software, executarea incompleta a unor programe din cauza aparitiei unor erori sau din necesitatea de intrerupere a lor din cauza unor interblocari sau prin iterventia utilizatorilor, programarea eronata a unor activitati prin strategiile folosite de sistem si alte cauze.
Pentru reconstituirea bazelor de date in cazul cand pot sa apara inconsistente in general, majoritatea bazelor de date se copiaza periodic pe medii magnetice ce se pastreaza in locuri sigure. De asemenea se tine o evidenta a tuturor transformarilor efectuate in baza de date de cand s-a efectuat ultima copie. Fisierul care contine aceste modificari se numeste jurnal. Fiecare inregistrare din jurnal contine un identificator al programului care a facut modificarea, fosta valoare si noua valoare introdusa pentru un element. Tot in jurnal se mai pastreaza diferitele monente importante din desfasurarea programelor (inceput, sfarsit, terminarea unor operatii, etc.).
Se spune despre o tranzactie ca este comisa daca au fost terminate toate calculele produse de ea in aria de lucru si s-a facut o copie a rezultatelor ei in jurnal. Aparitia unor caderi dupa ce o tranzactie a fost comisa nu afecteaza continutul bazei de date deoarece se poate reconstitui baza de date cu ajutorul ultimei copii si a jurnalului in care se gasesc toate rezultatele tranzactiilor comise. Modificarile tranzactiilor abandonate sau necomise nu sunt luate in considerare la parcurgerea jurnalului pentru restaurarea bazei de date.
Se defineste strategia de comitere in doua faze astfel: o tranzactie poate sa scrie intr-o baza de date numai dupa ce a fost comisa si o tranzactie poate fi comisa numai dupa ce a inregistrat in jurnal toate schimbarile de elemente produse de ea.
4. Securitate
Prin securitatea bazelor de date se intelege protejarea bazelor de date impotriva folosirii neautorizate a lor si in special a modificarilor si distrugerilor nedorite de date si citirilor nepermise de date. Tehnicile utilizate de obicei sunt urmatoarele:
1. Identificarea utilizatorilor. Fiecarui utilizator in parte i se acorda
anumite drepturi de operare cu diferite portiuni din baza de date la diferite
nivele cum ar fi relatia, inregistrarea, pagina, atributul, etc. Drepturile
se refera la posibilitatea citirii, inserarii, stergerii sau modificarii
datelor respective. Identificarea se face de obicei prin parole stabilite
fie de administratorul bazei de date fie de utilizator.
2. Protejarea fizica. Deoarece s-ar putea ajunge la date si prin alte mijloace
decat prin intermediul SGBD-ului (de exemplu prin citirea directa a mediului
magnetic) se poate face o protectie prin pastrarea codificata a datelor pe
mediul magnetic. Decodificarea datelor se poate face numai dupa identificarea
utilizatorului prin garzi asociate lui.
3. Administrarea si transmiterea drepturilor. Se tine evidenta stricta a
drepturilor de acces ale fiecarui utilizator la portiunile din baza de date
si se fixeaza reguli de transmitere de la un utilizator la altul a dreptului
de acces.
De multe ori utilizarea vederilor in diferitele aplicatii serveste si pentru protejarea datelor. In unele sisteme nu sunt posibile modificari prin intermediul vederilor. Astfel de vederi se numesc numai pentru citire (read-only) si sunt utilizate mai ales in aplicatiile in care datele pot fi citite de toti utilizatorii (baze de date publice) dar modificarile se fac numai cu aprobarea proprietarului bazei de date. De exemplu, in ISBL si QBE se pot crea vederi cu continutul actual al unor relatii, cu parti din relatii pe atribute sau pe tupluri care pot fi facute publice si citite de utilizatori.
Alte sisteme cum sunt IMS, System R si DBTG permit definirea unor vederi in care se poate face atat citire cat si scriere pentru anumite obiecte.
Modificarile din vederi pot duce la efecte laterale ce privesc partile din baza de date ce nu apar in vederi. De exemplu stergerea unui element din vedere poate sa duca la eliminarea unui alt element care are singura legatura cu elemntul sters si care nu se afla in vedere.
Diferitele protectii pot fi indicate prin intermediul limbajului de prelucrare a datelor. Portiunile din baza de date ce pot fi folosite de utilizator pot fi definite prin operatii de selectie si proiectie care fac invizibile alte portiuni ale bazei de date.
Problema securitatii cuprinde aspecte legale, sociale si etice, aspecte privind controlul fizic (paza si posibilitati de blocarea accesului la terminale), aspecte de politie (fixarea conditiilor de acces), aspecte operationale (modul de stabilire a parolelor), aspecte privind controlul hard (modul de acces hard la diferite componente), securitatea sistemului de operare (protejarea informatiilor si anularea rezultatelor intermediare pentru pastrarea secretului datelor) aspecte privind notiunea de proprietate asupra datelor din baza de date si altele asemanatoare.
4.1. Securitatea in QBE
In sistemul QBE sunt prevazute patru tipuri de drepturi: insertie (I.), stergere (D.), modificare (U.) si citire (P.). Conferirea drepturilor unei persoane sau unui grup de persoane pentru o relatie R se face de catre proprietarul relatiei R care pune un tuplu in scheletul relatiei R cu comanda
I.AUTR(<lista>). <nume> I.
unde lista cuprinde tipurile de drepturi alocate si numele reprezita un nume de persoana sau o variabila. Daca sunt date toate cele patru drepturi nu mai este necesara specificarea listei si daca lipseste numele se considera toti utilizatorii. In continuare sunt indicate prin variabile sau constante campurile la care se aplica drepturile respective. Constantele indica valori de selectie pentru tupluri si variabilele pot fi restrictionale prin conditii sau tupluri suplimentare. Coloanele ce contin spatii libere nu pot fi accesate.
Exemplul 5. . Pentru a da dreptul ca Ionescu sa vada comenzila facute fara a vedea cantitatile cerute se poate construi cererea
COMENZI | NR_COM | NUME | MARFA | CANTITATE |
I.AUTR(P.).Ionescu I. | _n | _p | _m | |
| | | | |
si pentru acordarea tuturor drepturilor in aceleasi conditii se elimina (P.) din prima coloana. Pentru a permite tuturor sa aiba drepturile indicate se elimina Ionescu din prima coloana sau se inlocuieste cu o variabile (eventual adaugand "_" inaintea lui). Daca se permite accesul numai la comenzile in care cantitatea este mai mare decat 5 se adauga in ultima coloana >5 si atunci toate coloanele sunt vizibile. Pentru a permite tuturor sa citeasca toate comenzile ce contin marfuri vandute de magazinul Unirea se face cererea
COMENZI | NR_COM | NUME | MARFA | CANTITATE |
I.AUTR(P.)._Ionescu I.| _n | _p | _m | _q |
| | | | |
MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |
I.AUTR(P.).
| | | | |
Se pot indica prin intermediul variabilelor subgrupuri de utilizatori la care sa se aplice anumite drepturi.
Exemplul 5. . Pentru a permite fiecarui cumparator sa poata sa-si citeasca propriul cont se poate formula cererea
CUMPARATORI | NUME | ADRESA | CONT | _____ _______ ______ _______|________________|_____ _______ ______ ________|______________|
I.AUTR(P.)._Ionescu I.| _Ionescu | | _c |
| | | |
Toate drepturile introduse prin comenzi AUTR. sunt continute intr-un tabel din care se pot afla informatii despre drepturile fiecarui utilizator sau restrictiile de acces la fiecare relatie prin cererile obisnuite din QBE. De asemenea, proprietarul unei relatii poate sa modifice drepturile de acces la relatia respectiva.
4.2 Securitatea in SQL
Problema securitatii in SQL se rezolva prin mecanismul vederilor prin care diferitii utilizatori au acces numai la anumite informatii, restul informatiilor ramanand invizibile pentru ei si prin sistemul de autorizari care permite utilizatorilor ce au anumite drepturi sa poata sa transmita sau sa anuleze aceste drepturi si pentru alti utilizatori. Sistemul prevede structuri ce memoreaza constrangerile de autorizare comunicate de utilizatori, face verificarile lor la efectuarea fiecarei cereri si are un modul de verificare si identificare a utilizatorilor.
La definirea vederilor prin CREATE VIEW se poate limita accesul numai la tablourile la care proprietar este utilizatorul respectiv folosind o conditie de selectie cu cuvantul cheie USER ce da identificatorul utilizatorului de tipul
WHERE CREATOR = USER
Orice operatie din baza de date se face numai pe baza unei autorizari pentru acea operatie. Initial sistemul acorda toate drepturile de operare pentru administratorul sistemului (SYSADM) si nu acorda nici-un drept de operare la ceilalti utilizatori. Apoi drepturile de operare sunt transmise prin intermediul instructiunii GRANT sau sunt revocate prin instructiunea REVOKE.
Instructiunea GRANT este de forma
GRANT operatii [ ( atribute ) ] ON TABLE tabele TO utilizatori
[ WITH GRANT OPTION ] ;
unde operatii este o submultime a multimii (ultimele doua se aplica numai la tabele de baza permitand adaugarea unei noi coloane si respectiv construirea unui index pentru tabelul respectiv) indicand operatiile autorizate (daca sunt permise toate se pune ALL), atribute este o lista a atributelor la care se aplica operatiile respective, tabele da lista tabelelor de baza si vederilor implicate in operatii, utilizatori da lista identificatorilor celor ce au drepturile respective (cuvantul cheie PUBLIC se foloseste pentru a indica toti utilizatorii sistemului), WITH GRANT OPTION permite transmiterea in cascada a acodrdarii unor drepturi si a revocarii lor.
Instructiunea REVOKE este de forma
REVOKE operatii ON TABLE tabele FROM utilizatori ;
cu operatii, tabele si utilizatori ca mai sus doar ca de aceasta data se refera la revocarea unor operatii.
Revocarea unor autorizari se poate face de catre persoana care a dat autorizarea respectiva si presupune invalidarea tuturor aplicatiilor care utilizeaza operatiile revocate.
4.3. Securitatea in QUEL
Constrangerile de securitate sunt exprimate in limbajul QUEL prin intermediul instructiunii DEFINE PERMIT care are forma generala
DEFINE PERMIT operatii ON tabele [ ( atribute ) ] TO utilizatori
[ AT terminale ] [ FROM ora1 TO ora2 ] [ ON zi1 TO zi2 ]
[ WHERE conditie ]
Se poate folosi variabila USERNAME pentru a fixa contextul aplicarii regulei la utilizatorul curent.
Constrangerile de securitate sunt numerotate si pastrate intr-un catalog al sistemului INGRES. Numarul asociat unei constrangeri se poate afla cu instructiunile HELP si RETRIEVE. Acest numar este utilizat la revocarea unei permisiuni printr-o instructiune de forma:
DESTROY PERMIT tabel nr-constrangere
4.4. Baze de date statistice
Se numeste baza de date statistica o baza de date din care se pot obtine informatii aplicand operatii agregate la submultimi de elemente continute in ea. Prin formularea unor intrebari unii utilizatori pot sa obtina informatii la care in mod obisnuit nu au acces. De exemplu daca un utilizator nu are acces la campul SALARIU dar poate face suma salariilor unor submultimi de cel putin m persoane cu m dat, pentru a afle salariul lui Popescu el poate calcula suma tuturor salariilor si suma tuturor salariilor fara al lui Popescu si prin scaderea celor doua sume afla salariul lui Popescu la care nu avea acces.
Pentru a preveni astfel de situatii, unele sisteme de baze de date tin o evidenta a intrebarilor puse de fiecare utilizator in parte sa refuza sa raspunda in anumite conditii cum ar fi: sunt implicate mai putine inregistrari decat un numar dat m sau sunt implicate mai mult de n-m inregistrari unde n este numarul total de elemente sau sunt implicate mai mult de p inregistrari comune cu o cerere anterioara si altele asemanatoare.
Fie o baza de date cu n inregistrari ce au valorile v=(v1,v2,...,vn) corespunzatoare unui camp care nu este cheie. Se numeste cerere liniara o suma de forma c1v1+c2v2+...+cnvn unde ci este un numar real oarecare pentru orice i. Fie r1,r2,...,rq un numar de q cereri liniare cu ri=ci1v1+...+cinvn. Spunem ca baza de date este compromisa daca exista o functie f astfel incat una din valorile vi se obtine aplicand f valorilor r1,...,rq, deci vi=f(r1,...,rq).
Lema 5. . Daca exista o functie f astfel incat vi=f(r1,...,rq) atunci exista o functie liniara g cu aceeasi proprietate, deci exista d1,...,dq astfel incat d1r1+d2r2+...dqrq = vi.
Daca notam cu M matricea cu q linii si n coloane a coeficientilor cererilor liniare r1,...,rq si cu d=(d1,d2,...,dq), din lema precedenta rezulta ca baza de date este compromisa daca si numai daca exista un vector d astfel incat dM = (0,...,0,1,0,...,0). Pentru a nu compromite baza de date se fac constrangeri de forma:
- fiecare linie din M are cel putin m elemente nenule;
- oricare doua linii au cel mult k elemente nenule pe coloane comune
Exemplul 5. . Pentru valorile v1,...,v7 cu cererile r1=v2+v3+v4, r2=v5+v6+v7, r3+v1+v2+v5, r4=v1+v3+v6 si r5=v1+v4+v7 baza de date este compromisa deoarece v1=(r3+r4+r5-r1-r2)/3 desi s-ar putea lua m=3 si k=1. Deci punerea conditiei m=4 sau k=0 poate eventual duce la o baza de date care nu e compromisa.
Teorema 5. . Daca se folosesc cereri liniare in care se folosesc cel putin m valori, doua cereri au in comun cel mult k valori si se cunosc deja p valori, atunci pentru a calcula un nou element necunoscut sunt necesare cel putin (m-p-1)/k+1 cereri.
Se poate da un exemplu prin care se demonstreaza ca pentru orice m si orice k sunt suficiente 2m/k-1 cereri pentru a compromite o baza de date.
5. Optimizarea cererilor
Pentru cererile adresate unei baze de date de foarte multe ori se pot face reformulari ale cererii in cereri echivalente cu ea a caror timp de executie si spatiu de memorie ocupat sa fie mult mai mici in comparatie cu tratarea cererii initiale. Transformarile respective sunt efectuate de utilizator sau de sistemul de calcul in procesul de optimizare a cererilor. In acest capitol prezentam unele metode utilizate in acest domeniu.
In sistemele de tip relational se consuma mult timp si memorie la efectuarea produsului cartezian si a uniunii naturale care sunt operatii des utilizate. Pentru efectuarea produsului cartezian a doua relatii ce sunt memorate ca doua fisiere se parcurge unul din fisiere si pentru fiecare inregistrare din primul fisier se parcurg inregistrarile celui de-al doilea fisier. Numarul de citiri de pe mediul extern este mai mic daca citirea se poate face pe blocuri de inregistrari si se rezerva un bloc pentru inregistrarile celui de-al doilea fisier si restul blocurilor pentru primul fisier. In acest caz numrul de citiri este n1/b1(1 + n2/((m-1)b2)) unde ni da numarul inregistrarilor din fisierul i, bi da numarul de inregistrari dintr-un bloc si m este numarul de blocuri din memoria interna ce se pot utiliza. Se vede ca se obtine un numar mai mic daca raportul n1/b1 este mai mic decat n2/b2 fata de cazul cand s-ar inversa rolul fisierelor.
Pentru n1 = n2 = 10000, b1 = b2 = 5 si m = 100 se obtine un numar de 42400 citiri si daca se fac 20 de citiri de blocuri pe secunda, efectuarea produsului cartezian ar lua circa 35 de minute.
De multe ori produsul cartezian nu se ia ca atare ci combinat cu alte operatii. De exemplul in cererea scrisa in limbajul QUEL
range of x is AB
range of y is CD
retrieve (x.A)
where x.B = y.C and y.D = 99
care se poate exprima in algebra relationala prin expresia
@p/A(@S/B=C@AD=99(AB X CD))
desi apare produsul cartezian putem evita calculul lui. Se transforma expresia data mai intai in expresia echivalenta
@P/A(@S/B=C(AB X @S/D=99(CD)))
si de aici se deduce expresia echivalenta
@P/A(AB |X| @S/D=99(CD))
B=C
Calculele se desfasoara in felul urmator: se parcurge fisierul pentru CD si se selecteaza tuplurile care au valoarea 99 pentru D retinandu-se numai valorile pentru C (determinarea acestor tupluri este mai rapida daca exista un index pentru D); se selecteaza apoi din fisierul corespunzator lui AB acele tupluri care au valori pentru B din multimea gasita pentru C si se retin valorile pentru A din tuplurile gasite. Acest procedeu necesita parcurgerea o singura data a fiecarui fisier cel mult si ia mult mai p[utin timp si spatiu decat daca s-ar fi efectuat operatiile in ordinea indicata de cererea initiala.
Pentru uniunea naturala exista mai multe metode de implementare. De exemplu pentru a efectua operatia AB |X| CD si nici-unul dintre cele doua
B=C
fisiere nu incape in memoria principala se pot sorta cele doua fisiere, primul dupa B si al doilea dupa C si apoi cu un procedeu de tip interclasare se poate obtine rezultatul uniunii naturale printr-o singura parcurgere a celor doua fisiere. Daca exista un index al primului fisier dupa B se parcurge al doilea fisier si se cauta prin intermediul indexului tuplurile din primul fisier care au pentru B valoarea gasita pentru C in fiecare tuplu din al doilea fisier. Numarul de accese devine mai mic in cazul cand inregistrarile sunt grupate in aceleasi blocuri in functie de valorile lui B si respectiv C.
In optimizarea cererilor se aplica diferite principii dintre care fac parte si urmatoarele:
1. Efectuarea selectiilor cat mai curand posibil. Acesta produce, in general,
rezultate intermediare cu mai putine elemente care se prelucreaza mai usor.
2. Combinarea eventuala a unor selectii cu produse carteziene pe care le preced
pentru a obtine uniuni naturale. Daca selectia contine atribute nunai dintr-o
relatie a produsului cartezian ea poate fi coborata in arborele asociat
expresiei (se aplica prioncipiul 1).
3. Combinarea unor operatii unare de tip proiectie si selectie eventual si cu o
operatie binara vecina. Se pot aplica in acelasi timp selectii si proiectii
pentru rezultatele intermediare obtinute dintr-o operatie anterioara fara a
mai fi necesara memorarea tuplurilor din operatia anterioara.
4. Determinarea subexpresiilor comune unei expresii. Acest principiu priveste
mai ales vederile pentru care relatiile utilizate nu sunt prea mari.
5. Prelucrarea corespunzatoare a fisierelor. Sortarea fisierelor dupa anumite
campuri sau folosirea unor indexi permanenti sau temporali pot spori
eficienta in determinarea raspunsului la cereri.
6. Evaluarea optiunilor inainte de a calcula. Se au in vedere dimensiunile
fisierelor cu care se lucreaza si in functie de acestea se determina cea mai
buna succesiune a operatiilor ce trebuiesc executate.
5.1. Prelucrarea algebrica a cererilor
Spunem ca doua expresii relationale E1 si E2 sunt echivalente si notam
E1 @=_ E2 daca cele doua expresii corespund aceleiasi aplicatii in sensul ca inlocuin cu aceeasi relatie aparitiile diferite ale aceleiasi variabile din cele doua expresii se obtine acelasi rezultat pentru ambele expresii.
Plecand de la definitia anterioara se pot demonstra o serie de proprietati ale operatorilor utilizati in bazele de date relationale in care relatiile sunt definite ca multimi de aplicatii pe multimi de atribute cu valori in domeniile asociate si anume:
1. Comutatitivitatea uniunii, uniunii naturale si produsului cartezian. Daca E1
si E2 sunt expresii relationale si F este o conditie pentru atribute din E1
si E2 atunci au loc echivalentele:
E1 |X| E2 @=_ E2 |X| E1
F F
E1 |X| E2 @=_ E2 |X| E1
E1 X E2 @=_ E2 X E1
2. Asociativitatea uniunii, uniunii naturale si produsului cartezian. Daca E1,
E2 si E3 sunt expresii relationale si F1 si F2 sunt conditii atunci au loc
echivalentele:
(E1 |X| E2) |X| E3 @=_ E1 |X| (E2 |X| E3)
F1 F2 F1 F2
(E1 |X| E2) |X| E3 @=_ E1 |X| (E2 |X| E3)
(E1 X E2) X E3 @=_ E1 X (E2 X E3)
3. Combinarea proiectiilor in cascada. Daca atributele A1,...,Am sunt o
submultime a atributelor B1,...,Bn care la randul lor sunt o submultime
a atributelor expresiei E, atunci are loc echivalenta:
@P/A1,...,Am(@P/B1,...,Bn(E)) @=_ @P/A1,...,Am(E)
4. Combinarea selectiilor in cascada. Daca F1 si F2 sunt conditii pentru
atribute din expresia E atunci au loc echivalentele:
@S/F1(@S/F2(E)) @=_ @S/F1@AF2(E) @=_ @S/F2@AF1(E) @=_ @S/F2(@S/F1(E))
5. Comutativitatea selectiei cu proiectia. Daca in conditia F se gasesc numai
atribute din multimea A1,...,An atunci are loc echivalenta:
@P/A1,...,An(@S/F(E)) @=_ @S/F(@P/A1,...,An(E))
iar daca F mai contine si atributele B1,...,Bm in afara de A1,...,An, atunci:
@P/A1,...,An(@S/F(E)) @=_ @P/A1,...,An(@S/F(@P/A1,...,An,B1,...,Bm(E)))
6. Comutatitivitatea selectiei cu produsul cartezian. Daca toate atributele ce
apar in conditia F apar in E1 atunci:
@S/F(E1 X E2) @=_ @S/F(E1) X E2
si o relatie asemanatoare daca toate atributele apar numai in E2. In general
daca F = F1 @A F2 cu F1 avand atribute numai din E1 si F2 avand atribute
numai din E2 atunci:
@S/F(E1 X E2) @=_ @S/F1(E1) X @s/F2(E2)
sau si mai general daca F = F1 @A F2 @A F3 cu F1 si F2 ca mai sus iar F3
contine atribute din ambele expresii atunci:
@S/F(E1 X E2) @=_ @S/F3(@S/F1(E1) X @S/F2(E2))
7. Comutativitatea selectiei cu reuniunea. Daca expresiile E1 si E2 au aceleasi
atribute atunci:
@S/F(E1 U E2) @=_ @S/F(E1) U @S/F(E2)
8. Comutatitivitatea selectiei cu diferenta de multimi. Daca expresiile E1 si E2
au aceleasi atribute atunci:
@S/F(E1 - E2) @=_ @S/F(E1) - @S/F(E2)
9. Comutatitivitatea proiectiei cu produsul cartezian. Fie E1 si E2 doua
expresii relationale si A1,...,An atribute din care B1,...,Bm sunt atribute
din E1 si C1,...,Cp sunt atribute din E2 (m+p=n), atunci:
@P/A1,...,An(E1 X E2) @=_ @P/B1,...,Bm(E1) X @P/C1,...,Cp(E2)
10. Comutativitatea proiectiei cu reuniunea. Daca E1 si E2 au atribute comune si
A1,...,An este o submultime a lor, atunci
@P/A1,...,An(E1 U E2) @=_ @P/A1,...,An(E1) U @P/A1,...,An(E2).
In afara de echivalentele anterioare se mai pot deduce si alte echivalente cum ar fi comutatitivitatea selectiei si uniunii care rezulta din regulile 4, 5 si 6 interpretand uniunea ca o compunere de produs cartezian si proiectie. De asemenea sunt valabile legi de comutatitivitate intre proiectie si produs cartezian sau reuniune asemanatoare cu 6 si 7 dar nu este o regula generala de comutatitivitate intre proiectie si diferenta de multimi.
Se poate construi un program eficient de tratare a unei cereri care sa contina activitati de una din urmatoarele forme:
- aplicarea unei selectii sau a unei proiectii;
- aplicare selectie+proiectie
- aplicarea unui produs cartezian, reuniune sau diferenta pentru doi
operanzi obtinuti eventual prin proiectie sau selectie, rezultatul
putand si el sa fie selectat sau proiectat.
Fiecare din operatiile anterioare produce un rezultat care se memoreaza si care poate fi rezultatul final sau operand pentru alta aplicare. Programul de evaluare a cererii se obtine aplicand algoritmul urmator:
Algoritmul 5. . Sa presupunem ca se da arborele asociat evaluarii cererii scrisa in algebra relationala.
1. Se foloseste regula 4 pentru a transforma fiecare selectie de forma
@S/F1@A...@AFn(E) in expresia @S/F1(...(@S/Fn(E))...).
2. Se folosesc regulile 4-8 pentru a muta selectiile cat mai jos posibil
in arbore.
3. Se folosesc regulile 3, 5, 9 si 10 pentru a muta proiectiile cat mai
jos posibil in arbore. Se elimina o proiectie daca se face dupa toate
atributele expresiei la care se aplica.
4. Se folosesc regulile 3-5 pentru a combina selectii si proiectii in
cascada obtinand o singura selectie, o singura proiectie sau o
selectie urmata de o proiectie.
5. Se partitioneaza nodurile interioare ale arborelui obtinut in grupe
care contin un operator binar X, U sau - impreuna cu predecesorii
imediati etichetati cu un operator unar (@P sau @S) si descendentii
de pe drumuri cu operatori unari ce se termina cu o frunza in afara
de cazul cand operatorul binar este un produs cartezian si nu este
urmat de o selectie pentru a produce o uniune naturala.
6. Se construieste programul care asociaza la fiecare grup o aplicatie
ordinea aplicatiilor trebuie sa respecte precedenta: un grup se
evalueaza numai dupa ce au fost evaluat toti descendentii sai
directi.
Exemplul 5. . Sa consideram o baza de date pentru o biblioteca avand urmatoarele relatii componente:
CARTI (TITLU, AUTOR, EDITOR, NR_INV)
EDITORI (NUMEE, ADRESAE, ORASE)
CITITORI (NUME, ADRESA, ORAS, NR_LEG)
FISE(NR_LEG, NR_INV, DATA)
unde, pentre a deosebii numele, adresa si orasul cititorului de cele ale editorului am adaugat la acesta din urma litera E la atributele respective. Intr-o vedere care contine informatii despre cartile imprumutate se pot face cereri diverse. Sa numim relatia corespunzatoare acestei vederi IMPRUMUT ea fiind obtinuta prin uniunea naturala a relatiilor CARTI, CITITORI si FISE cu
@P/S(@S/F(FISE X CITITORI X CARTI))
unde S=TITLU,AUTOR,EDITOR,NR_INV,NUME,ADRESA,ORAS,NR_LEG,DATA si F este
CITITORI.NR_LEG = FISE.NR_LEG AND CARTI.NR_INV = FISE.NR_INV
Listarea titlurilor cartilor care au fost imprumutate inainte de data de 1 august 1994 se poate face de exemplu cu cererea
@P/TITLU (@S/DATA < 1/8/94 (IMPRUMUT))
si inlocuind expresia relatiei IMPRUMUT se obtine arborele din fig. 5.3.
@P/TITLU
|
|
@S/DATA < 1/8/94
|
|
@P/TITLU,AUTOR,CARTI.NR_INV,NUME,ADRESA,ORAS,
| CITITORI.NR_LEG,DATA
|
@S/CITITORI.NR_LEG=FISE.NR_LEG A
| CARTI.NR_INV=FISE.NR_INV
|
X
/ \
/ \
X CARTI
/ \
/ \
FISE CITITORI
Figura 5.3.
Conform algoritmului primele transformari pe care le facem privesc selectiile. Cea de-a doua selectie se desparte in doua selectii avand cele doua conditii legate prin "si" in selectia originala. Sunt apoi coborate selectiile cat mai jos posibil in arbore. Selectia cu conditia DATA < 1/8/94 ce contine numai atributul DATA poate fi coborata pana la FISE ce contine acest atribut si selectia cu conditia CITITORI.NR_LEG=FISE.NR_LEG poste fi coborata pana inainte de produsul cartezian dintre @S/DATA < 1/8/94(FISE) si CITITORI avand atribute din aceste reletii. Se combina apoi cele doua proiectii consecutive obtinand @P/TITLU si aceasta proiectie impreuna cu selectia cu conditia CARTI.NR_INV = FISE.NR_INV se inlocuieste cu cascada
@P/TITLU
@S/CARTI.NR_INV = FISE.NR_INV
@P/TITLU,CARTI.NR_INV,FISE.NR_INV
si coborand cea de-a doua proiectie in arbore se obtine rezultatul final din fig. 5.4,
@P/TITLU
|
|
@S/CARTI.NR_INV=FISE.NR_INV
|
|
X
/ \
/ \
/ \
@P/FISE.NR_INV @P/CARTI.NR_INV,TITLU
| \
| \
@S/CITITORI.NR_LEG= CARTI
| FISE.NR_LEG
|
X
/ \
/ \
/ \
@P/FISE.NR_INV, @P/CITITORI.NR_LEG
| FISE.NR_LEG |
| |
@S/DATE<1/8/94 CITITORI
|
|
FISE
Figura 5.4.
Pentru fig. 5.4 corespunde un program cu doua instructiuni: prima instructiune este o uniune naturala in care se cuprinde produsul cartezian din partea de jos a arborelui impreuna cu proiectia si selectia ce il preced si cu proiectiile si selectia ce se gasesc in subarborii lui avand ca rezultat numarul de inventar al cartilor imprumutate inainte de 1 august 1994 iar cea de-a doua instructiune care este tot o uniune naturala combina rezultatul primei instructiuni cu informatiile obtinute despre carti pentru a obtine titlurile din lista asociata cererii.
5.2. Optimizari in System R
In System R cererile sunt mai intai optimizate si apoi sunt executate considerandu-se ca timpul consumat cu optimizarea se recupereaza la executie, mai ales in cazul cand cererea este evaluata in mod repetat. Cererile sunt considerate de forma:
SELECT A1,A2,...,An
FROM R
WHERE P1 AND P2 AND ...
unde P1,P2,... sunt predicate in care nu mai apare AND. In optimizari se folosesc mult indexarile si statisticile asupra diferitelor relatii existente.
Un caz special il constituie indexul grupat in care inregistrarile asociate unei valori din index sunt grupate in acelasi bloc sau in blocuri alaturate facand posibil un acces mai rapid la inregistrari. Un algoritm de optimizarea cererilor este cel urmator.
Algoritmul 5. . Sa presupunem ca relatia R contine T inregistrari si ocupa un numar de B blocuri pe mediul extern. Sunt estimate pe rand costurile diferitelor tipuri de metode expuse in continuare retinandu-se metoda care realizeaza costul cel mai mic.
1. Se determina tuplurile lui R care satisfac un predicat de forma A=c si pentru
A exista un index grupat din care se pot gasi usor tuplurile ce au valoarea
c, apoi se verifica celelalte predicate pentru ele. Numarul estimat al
acceselor la blocuri este B/I unde I este numarul elementelor din index.
2. Se foloseste indexarea grupata dupa atributul A pentru a obtine submultimea
de tupluri ale lui R care satisfac un predicat de forma A@0c cu @0 din
multimea si pentru acestea se verifica celelalte predicate.
Numarul estimat al acceselor la blocuri este B/2.
3. La fel ca la 1 doar ca A are un index obisnuit (fara grupari). Costul estimat
in acest caz este T/I.
4. Se citeste R si se verifica predicatele pentru fiecare tuplu in parte. Costul
este in acest caz B.
5. Daca fisierul nu este memorat in blocuri compacte dar are un index grupat, se
foloseste indexul pentru a ajunge la inregistrarile fisierului si apoi se
verifica predicatele. Costul in acesta metoda este B.
6. La fel ca la 2 doar ca A are un index oarecare. Costul acestei metode este
T/2.
7. Se foloseste un index negrupat sortat si se verifica predicatele pentru
tuplurile parcurse. Costul acestei metode este T.
8. Daca nu se poate aplica nici-una din metodele anterioare se parcurg toate
blocurile ce pot avea inregistrari din R si pentru cele gasite se testeaza
predicatele. Costul acestei metode este ceva mai mare de T.
Exemplul 5. . Sa aplicam algoritmul precedent la cererea
SELECT NR_COM
FROM COMENZI
WHERE CANTITATE @>= 5 AND MARFA = "portocale"
Daca pentru relatia COMENZI exista un index grupat dupa NUME si indexi negrupati dupa MARFA si CANTITATE, T=1000 (sunt circa 1000 de comenzi), B=100 (memorate in circa 100 de blocuri), I=50 (apar circa 50 de marfuri in comenzi), alegerile 1 si 2 nu se pot aplica. Alegerea 3 cu index negrupat dupa MARFA da costul T/I = 1000/50 = 20. Alegerea 4 daca fisierul are blocuri consecutive sau 5 cu parcurgerea indexului grupat dupa NUME in caz contrar are costul B = 100. Alegerea 6 se poate face prin parcurgerea indexului asociat pentru CANTITATE cu costul T/2 = 500 iar alegerile 7 si 8 dau costul T=1000. Deci se obtine costul cel mai mic daca se face optiunea 3 prin care se cauta in indexul pentru MARFA tuplurile ce corespund pentru "portocale" si pentru aceste tupluri se face testul CANTITATE @>= 5.
5.3. Algoritmul de descompunere QUEL
Pentru o cerere din QUEL de forma
range of t1 is R1
.
.
.
range of tk is Rk
retrieve(@a)
where F
unde @a este o lista de atribute ce apar in relatiile R1,...,Rk si F este o conditie asupra atributelor, se poate gasi o expresie echivalenta in calculul relational de forma
@P/@a(@S/F(R1 X R2 X ... X Rk))
Se pot utiliza proprietatile de comutativitate pentru a cobori proiectiile si selectiile dar si comutatitivitatea si asociativitatea produsului cartezian pentru a micsora numarul de elemente cautate.
Exemplul 5. . Sa presupunem ca vrem sa facem uniunea naturala a trei relatii AB, BC si CD fiecare avand cate n elemente, ca la calculul uniunii naturale rezultatul are de p ori mai multe elemente decat cea mai mare relatie implicata, ca timpul de calcul al uniunii naturale este de d ori dimensiunea rezultatului si ca pentru a calcula un index dupa un atribut al unei relatii este necesar un timp de c ori mai mare decat dimensiunea relatiei respective.
Pentru a calcula AB |X| BC este necesar timpul cn pentru a crea un
index pentru B in una din relatii si inca dpn pentru a calcula uniunea naturala.
Apoi, pentru a ajunge la rezultatul final mai este necesar cn pentru a calcula
un index dupa C pentru CD, cea mai mica dintre relatii, si inca dp\2n pentru a
calcula uniunea naturala. Deci timpul total de calcul este 2cn + d(p\2 + p)n.
Exista o metoda care da in general mai bune rezultate. Mai intai se creaza cate
un index dupa B in AB si dupa C in CD in timpul 2cn. Apoi prin parcurgerea
relatiei BC, pentru fiecare tuplu (b1,c1) se determina prin intermediul
indexilor perechile (a1,b1) din AB si (c1,d1) din CD formandu-se tuplul din
rezultatul final (a1,b1,c1,d1). Deci timpul total de calcul este 2cn + ep\2n
unde e este o
Sa presupunem ca trebuie sa se faca selectia cu conditia F1@A...@AFn din produsul cartezian al relatiilor R1,...,Rk. Presupunem ca fiecare Fi nu mai contine operatorul "si". Se construieste un hipergraf avand drept noduri relatiile R1,...,Rk si constantele ce apar in conditiile F1,...,Fn (doua aparitii ale aceleiasi valori se considera constante distincte) si ca hipermuchii multimile de noduri ce apar in fiecare din conditiile Fi sub forma de atribute ale relatiei respective sau constanta. Graful obtinut se numeste graful legaturilor.
Exemplul 5. . Sa consideram pentru baza de date din exemplul 5. cererea de listare a tuturor cititorilor care au imprumutat carti editate in acelasi oras cu cel in care locuiesc aceasta putandu-se exprima in QUEL prin:
range of t is CARTI
range of s is EDITORI
range of u is CITITORI
range of v ia FISE
retrive (u.NUME)
where t.NR_INV=v.NR_INV and u.NR_LEG=v.NR_LEG
and t.EDITOR=s.NUMEE and u.ORAS=s.ORASE
si pentru care corespunde graful legaturilor din fig. 5. .
_____________
| CARTI |
|___________|
/ \
CARTI.NR_INV / \ CARTI.EDITOR
=FISE.NR_INV / \ =EDITORI.NUMEE
/ \
__________ _____________
| FISE | | EDITORI |
|________| |___________|
\ /
FISE.NR_LEG \ / CITITORI.ORAS
=CITITORI.NR_LEG \ / =EDITORI.ORASE
\ /
______________
| CITITORI |
|____________|
Figura 5.5.
Executarea unei cereri poate fi vazuta ca o serie de operatii pe graful legaturilor asociat cererii, fiecare operatie construind o noua relatie folosita intr-un pas intermediar in evaluarea cererii si schimbarea corespunzatoare a grafului. In final graful va avea un singur nod care reprezinta rezultatul cererii. Numim constante si le marcam cu bare duble nodurile ce au putut sa fie evaluate, ele apartinand cel mult unei muchii, si numim muchii simple hipermuchiile ce corespund la conditii de forma A=B. Constructiile folosite pentru descompunerea grafului legaturilor sunt urmatoarele:
1. Instantiere. Daca exista o muchie simpla intre nodurile n si m, unde n
reprezinta o relatie r si m
reprezinta o
v, se elimina nodul m si muchia (m,n) etichetata cu A=v unde A este un
atribut al lui r si se inlocuieste nodul n cu @S/A=v(r).
2. Disectie. Daca nodul n reprezinta relatia r si apare in k muchii diferite,
pentru fiecare tuplu t din r se construieste un graf in care r se inlocuieste
cu si fiecare muchie e in care apare n corespunzatoare formulei F se
inlocuieste cu muchia avand formula obtinuta din F prin inlocuirea
atributului A din r cu t[A] si pentru fiecare componenta a lui t mentionata
in F se creaza un nod reprezentand valoarea constanta a acestei componente.
Apoi se elimina n din muchia e dar se adauga in e toate nodurile astfel
create. Se repeta operatia pentru toate muchiile in care apare n. Dupa ce se
evalueaza acest graf producand relatia s se face produsul cartezian s X
si se ia reuniunea tuturor acestor produse carteziene dupa toate tuplurile t
ale lui r obtinand rezultatul final.
Algoritmul 5. . Se poate obtine evaluarea unei cereri prin descompunere plecand de la graful legaturilor G asociat cererii si obtinand in final REL(G).
Se fac instantieri si disectii tinand seama de urmatoarele preferinte:
1. De cate ori este posibila o instantiere se face acea instantiere.
2. Daca nu mai sunt posibile instantieri se alege un nod n pentru disectie. Se
prefera noduri ce apar numai in muchii simple si dintre acestea cele care au
fost evaluate cu instantiere sau disectie anterioara, altfel se da prioritate
la nodurile care fac graful neconex.
3. Pentru fiecare tuplu t al nodului n se obtine prin disectie graful Gt si
aplicand recursiv algoritmul acesta pentru Gt se obtine relatia REL(Gt) si
se da ca rezultat U/t(REL(Gt)X).
4. Cand nu mai sunt muchii se intoarece drept rezultat produsul cartezian al
relatiilor reprezentand fiecare din nodurile ramase.
Exemplul 5. . Aplicand algoritmul 5. pentru graful legaturilor din fig. 5.5 se observa ca nu se poate face instantiere iar disecarea se poate face dupa oricare din cele patru noduri. Daca alegem nodul CARTI pentru fiecare tuplu t din relatia CARTI se obtine un graf de legaturi ca in fig.5.6.
=============== ===============
|| t[NR_INV] || || t[EDITOR] ||
=============== ===============
| |
NR_INV=t[NR_INV]| | NUMEE=t[EDITOR]
| |
__________ _____________
| FISE | | EDITORI |
|________| |___________|
\ /
FISE.NR_LEG \ / CITITORI.ORAS
=CITITORI.NR_LEG \ / =EDITORI.ORASE
\ /
______________
| CITITORI |
|____________|
Figura 5.6.
Se aplica pentru noul graf obtinut din nou algoritmul obtinandu-se prin instantiere doua relatii si anume
F1 = @S/NR_INV=t[NR_INV](FISE)
E1 = @S/NUMEE=t[EDITOR](EDITORI)
obtinand un graf cu trei noduri F1, CITITORI si E1 legate prin cele doua muchii din partea de jos a figurii 5.6. Alegand apoi pentru disectie nodul F1, pentru fiecare tuplu u din F1 se construieste un graf Gtu asociat avand ca noduri u[NR_LEG], CITITORI si E1 legate intre ele prin conditiile NR_LEG=u[NR_LEG] si respectiv ORAS=ORASE. Prin instantiere se inlocuieste nodul CITITORI cu relatia
C1 = @S/NR_LEG=u[NR_LEG](CITITORI)
obtinandu-se un graf cu doua noduri C1 si E1 legate prin muchia ORAS=ORASE. O ultima disectie alegand nodul C1 cu tupluri v da un graf Gtuv cu nodurile v[ORAS] si E1 legate prin muchia de conditie ORASE=v[ORAS] si prin instantiere un graf cu un singur nod E2 dat de expresia
E2 = @S/ORASE=v[ORES](E1)
apoi prin pasul 4 se fac succesiv evaluarile REL(Gtuv)=E2, REL(Gtu)=U/v@cC1 (REL(Gtuv X ), REL(Gt)=U/u@cF1 (REL(Gtu) X ) si in final
REL(G) = U (REL(Gt) X )
t in CARTI
5.4. Micsorarea numarului de uniuni
Evaluarile uniunilor relatiilor sunt mari consumatoare de timp si de aceea o buna euristica in problema optimizarii cererilor este determinarea unei cereri echivalente cu cererea data care sa aiba un numar cat mai mic de uniouni. O clasa de cereri pentru care exista metode de a determina o cerere echivalenta cu numar minim de uniuni este clasa cererilor conjunctive de forma
unde fiecare Pi este fie de forma R(c1...cr) cu cj constante sau a-uri sau b-uri fie de forma c@0d cu c si d constante sau a-uri sau b-uri si @0 unul din operatorii de comparatie <, >, @<=, @>=.
Fiecarei cereri conjunctive i se poate asocia un tablou care este o matrice bidimensionala eventual urmata de o lista de restrictii. Prima linie a tabloului contine numele tuturor atributelor relatiilor ce intervin in cerere (daca se cunoaste corespondenta intre atribute si pozitia lor in tablou se poate omite numirea atributelor). Al doilea rand numit sumar contine asa numitele variabile (simboluri) distinse care corespund a-urilor din cerere si spatiu liber pentru atributele care nu apar printre a-uri. Celelalte randuri ale tabloului corespund termenilor de forma R(c1,...,cr) care semnifica apartenenta tuplului (c1,...,cr) la relatia R, punand ci in dreptul celui de-al i-lea atribut al lui R si lasand spatiu liber pentru atributele care nu sunt in R. Randurile pot fi insotite de numele relatiilor corespunzatoare lor. Sub tabel sunt trecute predicatele cererii conjunctive de forma c@0d pe care le numim constrangeri. Variabilele ce apar cu operatorii existentiali (b-uri) le numim variabile (simboluri) nedistinse.
Tabloul poate fi interpretat ca o aplicatie de la valorile variabilelor relatii cu rezultat o relatie care are ca atribute pe cele corespunzatoare variabilelor din sumar si contine toate tuplurile v1v2...vn unde fiecare vi este o valoare a variabilei distinse ai pentru care exista valori ale variabilelor nedistinse bj care fac fiecare rand al tabloului sa fie un tuplu al relatiei corespunzatoare si satisfac constrangerile tabloului.
Formal, rezultatul este multimea tuplurilor h(s) unde s este sumarul cu spatiile libere eliminate, h este o aplicatie de simboluri care pentru orice rand t corespunzator relatiei R are h(t) un tuplu din R si pentru orice constrangere c@0d face h(c)@0h(d) adevarata.
Exemplul 5. . Pentru cererea din exemplul 5. se poate construi urmatorul tablou in care am notat prescurtat atributele T (titlu), Au (autor), E (editor), I (nr.inventar), Ad (adresa), O (oras), C (nume cititor), L (nr. legitimatie) si D (data).
T Au E I Ad O C L D
a1
b1 b2 b3 b4 (CARTI)
b5 b6 b7 (EDITORI)
b8 b9 a1 b10 (CITITORI)
b11 b12 b13 (FISE)
b4 = b11 b10 = b12 b3 = b5 b7 = b9
Se poate transforma tabelul precedent in urmatorul tabel in care nu mai apar constrangeri cu egalitati
T Au E I Ad O C L D
a1
b1 b2 b3 b4 (CARTI)
b3 b6 b7 (EDITORI)
b8 b7 a1 b10 (CITITORI)
b4 b10 b13 (FISE)
Se pot construi tablouri pentru selectie, proiectie si uniune naturala. Intersectia, echiuniunea si produsul cartezian pot fi privite ca niste cazuri speciale de uniune naturala eventual cu redenumirea unor atribute.
Algoritmul 5. . Pentru construirea tabloului corespunzator unei expresii ce contine selectii, proiectii si uniuni naturale aplicate unor variabile relatii se procedeaza in modul urmator:
1. Pentru fiecare frunza ce contine variabila relatie R(A1,A2,...,An) se creaza
cate un tablou care are sumarul si un singur rand marcat cu R, ambele
continand aceiasi variabila distinsa pentru fiecare atribut ce apare in R si
spatii libere pentru atributele ce nu apar in R (dar pot sa apara in alte
relatii continute in expresie).
2. Pentru fiecare din subexpresiile expresiei date pentru care au fost
determinate tablouri corespunzatoare operanzilor se aplica urmatoarele
transformari pana cand obtinem un tablou corespunzator la toata expresia:
- Pentru o subexpresie @P/A1,...,An(E) pentru care s-a construit tabloul T
corespunzator lui E se sterg din sumarul lui T toate variabilele care nu
se afla in corespondenta cu atributele A1,...,An, devenind astfel variabile
nedistinse si putand sa apara in celelalte randuri sau in constrangeri.
- Pentru o subexpresie @S/F(E) unde conditia F nu mai contine operatorul "si"
se modifica tabloul T corespunzator lui E prin adaugarea conditiei F'
obtinuta din F prin inlocuirea fiecarui atribut A cu variabila distinsa
corespunzatoare lui A din sumarul lui T. In particular, daca F este de
forma A = B se identifica in tablou cele doua variabile distinse ce
corespund atributelor A si B iar daca F este de forma A = c unde c este o
constanta, se inlocuieste variabila distincta pentru A cu valoarea c.
- Pentru o subexpresie E1 |X| E2 pentru care se cunosc tablourile T1 si T2
corespunzatoare pentru E1 si E2, se redenumesc eventual unele variabile
astfel incat variabilele distinse pentru atributele comune sa se numeasca
la fel si toate celelalte variabile sa fie denumite distinct in cele doua
tablouri. Se formeaza un nou tabel cu sumarul format prin reuniunea
sumarelor lui T1 si T2 si spatiu liber in rest iar ca randuri si
constrangeri se iau toate randurile si constrangerile celor doua tablouri.
Exemplul 5. . Pentru a construi tabloul corespunzator expresiei cu atributele A, B si C in ordinea date
@P/A@S/C=0(AB |X| BC)
construim mai intai tablourile pentru expresiile AB si BC care sunt:
a1 a2 a3 a4
_____ _______ ______ _____________ _____ _______ ______ _____________
a1 a2 (AB) a3 a4 (BC)
Pentru construirea uniunii naturale a celor doua relatii se identifica variabilele din coloana lui B care este atribut comun si se obtine tabloul
a1 a2 a4
_____ _______ ______ _____________
a1 a2 (AB)
a2 a4 (BC)
Aplicand apoi selectia cu conditia C=0 se inlocuieste a4 cu 0 obtinand
a1 a2 0
_____ _______ ______ _____________
a1 a2 (AB)
a2 0 (BC)
si prin aplicarea proiectiei dupa A se obtine tabloul final
a1
_____ _______ ______ ______________
a1 a2 (AB)
a2 0 (BC)
Pentru un tablou cu n randuri se poate construi o expresie echivalenta cu n-1 uniuni si anume luand produsul cartezian al relatiilor ce corespund randurilor, se face apoi selectia ce reflecta constrangerile si diferitele aparitii ale aceleiasi variabile si apoi se face proiectia corespunzatoare variabilelor distincte. Deci pentru a minimiza numarul de uniuni trebuie gasita o metoda prin care se poate gasi un tablou echivalent cu un tablou dat care sa contina cat mai putine randuri. Pentru rezolvarea acestei probleme vom introduce cateva notiuni suplimentare.
Vom spune ca aplicatia definita de tabloul T1 este continuta in cea definita de tabloul T2, si vom nota T1 @C= T2, daca si numai daca cele doua tablouri au aceleasi atribute , au variabile distincte in aceleasi pozitii din sumar si pentru orice atribuiri de relatii pentru variabilele reletii ale randurilor tabelelor, relatia produsa de T1 este o submultime a relatiei produsa de T2. Testarea acestei proprietati se poate face aplicand urmatoarea teorema:
Teorema 5. . T1 @C= T2 daca si numai daca exista o aplicatie de simboluri h de la simbolurile lui T2 la cele ale lui T1 astfel incat:
1. h aplicat sumarului lui T2 este sumarul lui T1,
2. h aplicat fiecarui rand din T2 este un rand in T1 cu aceiasi denumire,
3. Fiecare constrangere a lui T2 rezulta din presupunerea ca au loc constran-
gerile din T1 pentru simbolurile in care h transforma simbolurile lui T2.
Spunem ca doua tablouri T1 si T2 sunt echivalente, si notam T1 @=_ T2, daca si numai daca T1 @C= T2 si T2 @C= T1.
Exemplul 5. . Fie tablourile T1 si T2 definite astfel:
a b a b
_____ _______ ______ ____________ _____ _______ ______ ____________
a c d (R) a e f (R)
a e f (R) h e b (R)
g c b (R)
h e b (R)
Teorema 5. . Daca T este un tablou, atunci exista on tablou minimal echivalent cu T ce se obtine din T prin eliminarea eventuala a unor randuri.
Demonstratie. Sa presupunem ca T1 este un tablou echivalent cu T avand un numar minim de randuri. Din echivalenta rezulta existenta aplicatiilor de simboluri f de la T la T1 si g de la T1 la T care indeplinesc condiitiile din teorema 5. deci pot fi vazute ca aplicatii intre randurile tablourilor. Fie T2 tabloul obtinut din T prin eleminarea randurilor care nu sunt in imaginea lui g. Se vede imediat ca T si T2 sunt echivalente si cum T2 nu are mai multe randuri ca T1 fiind imaginea prin g a lui T1 si nici mai putine deoarece T1 a fost presupusa minimala rezulta ca T1 si T2 au acelasi numar de randuri ceea ce demonstreaza teorema.
Corolar. Toate tablourile cu un numar minim de randuri echivalente cu un tablou dat coincid cu exceptia eventuala a notatiilor simbolurilor.
Demonstratie. Aplicatia de simboluri f identifica tabloul T2 cu tabloul T1 minimal echivalent cu T si aceasta se intampla pentru orice tablou minimal. Faptul ca imaginea lui T2 ar putea fi proiectat prin f pe o submultime proprie a lui T1 ar contrazice minimalitatea lui T1.
Din proprietatile enuntate anterior rezulta un procedeu prectic de determinare a tabloului minimal echivalent cu un tablou dat. Se incearca gasirea unor aplicatii de simboluri care sa transforme tabloul dat intr-un tablou continut in el strict. Procesul continua pana cand nu se mai gaseste o astfel de aplicatie. Problema este NP-completa, dar tinand seama ca de obicei numarul de randuri in tablou este mic ea se poate rezolva in timp util.
Evaluarea unei expresii se poate face eficient parcurgand urmatoarele etape: se construieste tabloul asociat, se determina tabloul minimal echivalent cu el, se determina expresia corespunzatoare tabelului minimal si apoi se aplica algoritmul de descompunere pentru evaluarea expresiei.
6. Construirea unei baze de date de tip retea
7. Construirea unei baze de date de tip arborescent
8. Concurenta in bazele de date
Cele mai multe baze de date sunt folosite in acelasi timp de mai multi utilizatori. Daca asupra lor s-ar efectua numai operatii de citire nu ar apare probleme in utilizare. Probleme deosebite apar in momentul cand unele operatii privesc modificarea unor elemente din baza de date cand, datorita operarii in acelasi timp pot sa apara inconsistente sau anomalii.
8.1. Accesul concurent la date
Operatiile concurente sunt referite prin notiunea de tranzactie care reprezinta o unitate logica de lucru definita ca o singura executie a unui program. Programul poate sa contina o singura cerere exprimata intr-un limbaj de cereri sau o serie de instructiuni in limbajul gazda impreuna cu cereri. Se considera baza de date ca fiind alcatuita din elemente ce pot fi locate la un moment dat. Locarea unui element permite accesul la acel element a unei tranzactii si interzice accesul celorlalte tranzactii la elementul respectiv pana la terminarea tranzactiei curente cand are loc o delocare. O parte a SGBD numita administrator de locare se ocupa cu evidenta elementelor locate si atribuie elementele diferitelor tranzactii.
Nivelul de locare este diferit de la sistem la sistem. Se pot loca relatii, tupluri, parti de tupluri, grupe de n tupluri cu n dat, seturi in modelul retea, subarbori in modelul ierarhic si asa mai departe. Locarea la nivel inalt are avantejele de spatiu mai putin ocupat si timp de lucru suplimentar mai mic iar locarea la nivel jos are avantajul utilizarii simultane a bazei de date de mai multi utilizatori in acelasi timp. Un criteriu de a alege elementele locabile este acela al frecventei mai mari de aparitie in cereri.
Un exemplu clasic de incosistenta introdusa prin accesul concurent numita problema pierderii reactualizarii este cel cu doua tranzactii T1 si T2 care executa in paralel programul
P: READ A; A:=A+1; WRITE A;
in care rezultatul final poate fi valoarea lui A marita cu o unitate si nu cu doua unitati cum ar fi normal. Anomalii asemanatoare pot sa apara prin anularea unor modificari efectuate de tranzactii care nu se termina normal (problema dependentelor necomise) sau cele produse prin considerarea unor stari de tranzitie ale bazei de date (problema analizei inconsistente). Anomaliile se pot evita daca fiecare tranzactie nu permite accesul la variabila A decat dupa ce se termina toate operatiile ei asupra acestei variabile. Un program care permite aceasta este
P: LOCK A; READ A; A:=A+1; WRITE A; UNLOCK A;
Daca A a fost locat de o tranzactie nu poate fi accesat de alta tranzactie decat dupa ce tranzactia ce la locat se termina si are loc delocarea lui A.
Prin succesiuni de forma locare-executie-delocare se pot asigura sincronizarea diferitelor operatii din tranzactiile ce privesc o baza de date.
Pot sa apara unele fenomene ce trebuiesc tratate de sistemul de baze de date cum sunt asteptarea la nesfarsit (livelock) sau interblocarea (deadlock). Asteptarea la nesfarsit poate sa apara cand o tranzactie asteapta utilizarea unui element care este ocupat de noi tranzactii ce apar in sistem. Ea poate fi evitata printr-o strategie de tip coada pentru fiecare element in parte. Au prioritate de folosire a unui element tranzactiile cu cea mai veche cerere pentru acel element. Interblocarea apare cand unele tranzactii detin unele elemente cerute de alte tranzactii si la randul lor cer elemente detinute de alte tranzactii ajungandu-se la o asteptare in cerc inchis si nici-o tranzactie nu mai poate continua.
Rezolvarea interblocarilor se poate face prin mai multe metode cum ar fi impunerea satisfacerii tuturor cererilor de elemente pentru o tranzactie inainte de a se executa, inpunerea unei ordini asupra elementelor si prezentarea cererilor de elemente in tranzactii in aceasta ordine, determinarea si tratarea interblocarilor prin intreruperea si reluarea unor tranzactii si altele.
O alta problema este legata de rezultatul obtinut prin efectuarea anumitor tranzactii. Se numeste programare a unei multimi de tranzactii ordinea in care sunt executati pasii elementari ai tranzactiilor, pentru fiecare tranzactie in parte ordinea pasilor ei din programare coincide cu ordinea de executie din tranzactia respectiva. O programare este seriala daca pentru fiecare tranzactie pasii sai apar consecutiv in programare. O programare se numeste serializabila daca efectul ei este echivalent cu al unei programari seriale.
Exemplul 5. . Considerand tranzactiile urmatoare T1 si T2:
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 B;
in orice programare seriala A+B+C este constant. Dintre programarile
T1 | T2 T1 | T2 T1 | T2
__________|__________ __________|___________ ___________|___________
READ A | READ A | READ A |
A:=A-10 | | READ B A:=A-10 |
WRITE A | A:=A-10 | | READ B
READ B | | B:=B-20 WRITE A |
B:=B+10 | WRITE A | | B:=B-20
WRITE B | | WRITE B READ B |
| READ B READ B | | WRITE B
| B:=B-20 | READ C B:=B+10 |
| WRITE B B:=B+10 | | READ C
| READ C | C:=C+20 WRITE B |
| C:=C+20 WRITE B | | C:=C+20
| WRITE C | WRITE C | WRITE C
prima este o programare seriala, a doua este o programare serializabila iar a treia nu este o programare serializabila.
Evitarea interblocarii si posibilitatea serializarii unor programari sunt asigurate prin impunerea unor conditii asupra ordinei de efectuare a operatiilor fiecarei tranzactii in parte numite protocoale.
In studiul programarilor din fiecare tranzactie se retin numai operatiile de locare si delocare de resurse. In intervalul de timp al efectuarii unui pas LOCK A intr-o tranzasctie si urmatoarea UNLOCK A se spune ca respectiva tranzactie detine pe A. Pentru fiecare pereche formata cu LOCK A si UNLOCK A corespunzator se asdociaza cate o functie f(A) care arata cum se transforma valoarea lui A in acest caz. Daca A0 este valoarea initiala a lui A atunci o programare in care locarile si delocarile lui A au asociate functiile f1,...,fn da in final pentru a valoarea fn...f1(A0).
Algoritmul 5. . Pentru a testa daca programarea S a unei multimi de tranzactii T1,...,Tk este sau nu serializabila se procedeaza astfel:
Se creaza graful directionat G, numit graf de precedenta, cu noduri corespunzatoare tranzactiilor si pentru fiecare pas din S de forma Ti:UNLOCK A urmat de alt pas de forma Tj:LOCK A se construieste in G un arc de la Ti la Tj. Daca G contine cel putin un ciclu, atunci S nu este serializabil, altfel S este serializabil si o serializare sa este data de o ordonare topologica.
Exista un protocol simplu care asigura serializabilitatea numit in doua faze care impune tuturor tranzactiilor conditia de a face mai intai toate locarile si apoi toate delocarile.
Teorema 5. . Daca programarea S contine numei tranzactii in doua faze atunci S este serializabila.
Demonstratie. Sa presupunem ca S contine numai tranzactii in doua faze dar ca nu este serializabila. Din algoritmul precedent rezulta ca graful G de precedenta contine un ciclu Ti1-->Ti2-->...-->Tik-->Ti1. Atunci o locare in Ti2 se face supa o delocare din Ti1, o locare din Ti3 se face dupa o delocare din Ti2,..., o locare din Tik se face dupa o delocare din Tik-1 si o locare din Ti1 se face dupa o delocare din Tik ceea ce ar duce la concluzia ca o locare din Ti1 s-ar face dupa o delocare a lui Ti1 si deci Ti1 nu ar fi in doua faze. Deci se verifica proprietatea din enuntul teoremei.
Teorema 5. . Daca T este o tranzactie care nu este in doi timpi, atunci exista o tranzactie T1 si o programare S neserializabila a lor.
Ddemonstratie. Daca T nu este in doi timpi atunci in ea apar in aceasta ordine pasi de forma:
... LOCK A ... UNLOCK A ... LOCK B ... UNLOCK B ...
Daca luam tranzactia T1 de forma:
T1: LOCK A; LOCK B; UNLOCK A; UNLOCK B;
si programarea S ce programeaza prima parte din T pana la UNLOCK A inclusiv, apoi toti pasii din T1 si apoi ce a mai ramas din T, graful asociat lui S contine un arc de la T la T1 si un arc de la T1 la T deci are un ciclu si deci S nu este serializabila.
O eficienta mai buna se obtine daca se face distinctie intre utilizarea neexclusiva a resurselor numita locare la citire careia ii corespunde instructiunea RLOCK A prin care nu se modifica valoarea lui A si deci A poate fi accesibila la citire si pentru alte tranzactii si respectiv utilizarea exclusiva a resurselor numita locare la scriere careia ii corespunde instructiunea WLOCK A prin care se modifica valoarea lui A si deci A nu poate fi accesibila la citire sau la scriere de alte tranzactii. Ambele tipuri de locari sunt suspendate de o instructiune UNLOCK A.
Doua planificari sunt echivalente daca produc aceleasi valori pentru 22122b12w fiecare element in parte si orice locare la citire dintr-o tranzactie se face in cele doua programari in momente cand elementul implicat are aceleasi valori.
Algoritmul 5. . Pentru a testa daca programarea S a unei multimi de tranzactii T1,...,Tk avand locari de citire si scriere este sau nu serializabila se procedeaza astfel:
Se creaza graful directionat G cu nodurile corespunzatoare tranzactiilor si avand urmatoarele arce: un arc de la Ti la Tj daca Ti are RLOCK A sau are WLOCK A si Tj este urmatoarea tranzactie care are un WLOCK A sau daca Ti a avut o delocare la o locare la scriere pentru A si Tj are urmatoarea locare la citire pentru A fara o alta locare pentru A intre cele doua evenimente. Daca graful G are cel putin un ciclu atunci S nu este serializabila, altfel o serializare a lui S este data de o ordonare topologica a lui G.
Ca si in cazul anterior se poate demonstra ca protocolul in doua faze este suficient pentru a asigura serializabilitatea unei programari si ca pentru orice tranzactie in care un UNLOCK precede un RLOCK sau un WLOCK exista o alta tranzactie si o programare a celor doua tranzactii care nu e serializabila.
Un caz mai general si mai des intalnit in realitate este considerarea tranzactiilor ca avand o multime de resurse la intrare (de citit) si o multime de resurse la iesire (de scris). Un astfel de model il numim cu locari numai pentru citire si numai pentru scriere. Modelele precedente sunt cazuri particulare ale acestui model si anume in primul model multimea la intrare coincide cu multimea la iesire iar in al doilea model multimea la iesire este vida pentru locarea la citire si multimea la intrare este vida pentru locarea la scriere.
In acest caz transformarea unei programari intr-o programare seriala echivalenta cu ea trebuie sa indeplineasca si urmatoarele conditii:
- daca tranzactia T2 citeste valoarea unui element A scris de T1 atunci
T1 trebuie sa preceada T2 in programarea seriala;
- daca o alta tranzactie T3 scrie A ea trebuie sa apara in programarea
seriala fie inainte de T1 fie dupa T2 si nu intre T1 si T2.
Vom presupune o tranzactie initiala T0 care nu citeste nici-un element si scrie toate elementele si o tranzactie finala Tf care citeste toate elementele si nu scrie nimic.
Tranzactiile care nu au nici-un efect asupra lui Tf se numesc tranzactii nefolosite. Determinarea tranzactiilor nefolosite se face construind un graf cu noduri corespunzatoare tranzactiilor si avand arc de la T1 la T2 daca T1 scrie o valoare citita de T2; tranzactiile nefolosite corespund nodurilor pentru care nu exista drum de la ele la Tf in acest graf.
Testarea daca o programare este serializabila sau nu se face cu ajutorul notiunii de poligraf construit in felul urmator: nodurile sunt corespunzatoare tranzactiilor la care se adauga tranzactiile fictive initiala si finala; pentru orice pereche de tranzactii Ti si Tj astfel incat Ti scrie A care este citit de Tj se considera arc de la Ti la Tj si pentru Ti si Tj ca mai sus si orice alt Tp care scrie A se considera perechea de arce de la Tp la Ti si de la Tj la Tp. Un poligraf este aciclic daca exista o alegere a cate unui arc din fiecare pereche a lui care impreuna cu celelalte arce sa dea un graf aciclic.
Algoritmul 5. . Testarea daca o programare S din modelul locari numai pentru citire si numai pentru scriere pe multimea tranzactiilor T1,T2,...,Tk este sau nu serializabila se poate face in felul urmator:
1. Se adauga la inceputul lui S o serie de pasi in care o tranzactie fictiva T0
scrie toate elementele ce apar in S si la sfarsit o serie de pasi in care o
tranzactie fictiva Tf citeste toate elementele ce apar in S.
2. Se construieste un poligraf cu nodurile T0,T1,T2,...,Tk,Tf si cu arc intre Ti
si Tj de fiecare data cand in S Ti scrie o valoare A citita de Tj.
3. Se determina tranzactiile nefolosite (fara drum de la ele la Tf).
4. Se elimina arcele adiacente tranzactiilor nefolosite.
5. Pentru fiecare arc ramas Ti-->Tj, fiecare A scris de Ti si citit de Tj si
fiecare tranzactie T care scrie A nu se fac modificari daca Ti=T0 si Tj=Tf,
altfel se adauga arcul Tj-->T daca Ti=T0, se adauga arcul T-->Ti daca Tj=T0
si se adauga perechea de arce (T-->Ti, Tj-->T) altfel.
6. Se determina daca poligraful rezultat este aciclic si in acest caz
programarea S este serializabila, o programare seriala echivalenta cu S
corespunde ordonarii topologice a grafului aciclic rezultat din poligraf si
daca poligraful nu este aciclic atunci S nu este serializabila.
Ca si pentru modelele anterioare protocolul in doua faze este o conditie suficienta pentru ca orice programare corecta a tranzactiilor respective sa fie serializabila. Demonstratia se face asemanator.
In cazul structurilor arborescente se pot aplica doua tipuri de strategii: locarea individuala a fiecarui nod in parte sau locarea unui nod impreuna cu toti descendentii sai.
Pentru prima strategie a locarii individuale a fiecarui nod se poate aplica urmatorul protocol numit protocolul de arbore: nu se face locarea de doua ori a aceluiasi termen in aceiasi tranzactie si in afara de primul element locat in tranzactie (care poate sa nu fie radacina) orice alt element poate fi locat numai daca tranzactia detine o locare a tatalui acelui element.
Se poate arata ca protocolul de arbore este o conditie suficienta ca programarea unor tranzactii de acest tip sa fie serializabila. Serializabilitatea unei programari se poate testa prin determinarea daca un graf asociat este aciclic sau nu. Graful are noduri corespunzatoare tranzactiilor si pentru fiecare element A locat de tranzactiile Ti si Tj se considera arcul Ti-->Tj daca Ti locheaza pe A inainte de Tj.
Pentru a doua strategie a locarii unui element impreuna cu toti descendentii lui se foloseste atentionarea predecesorilor unui element care se locheaza. Deci operatiile permise legate de locare sunt: LOCK care locheaza un element impreuna cu toti descendentii sai (un element nu poate fi locat de doua tranzactii in acelasi timp), WARN care plaseaza o atentionare intr-un element (nici-o tranzactie nu poate loca un element in care o alta tranzactie a plasat o atentionare) si UNLOCK care anuleaza o locare sau o atentionare sau ambele pentru un element.
Spunem ca o tranzactie indeplineste protocolul de atentionare pe o ierarhie de elemente daca incepe prin a plasa o locare sau o atentionare in radacina, nu plaseaza in continuare o locare sau o atentionare pe un element decat daca are o atentionare pe tatal acelui element, anuleaza o locare sau o atentionare numai dupa ce a anulat locarile si atentionarile pe fii elementului respectiv si se supune la protocolul in doua faze in sensul ca toate delocarile urmeaza dupa toate locarile si atentionarile tranzactiei.
Programarile tranzactiilor care indeplinesc protocolul de atentionare sunt serializabile. Pentru determinarea unei programari seriale echivalenta cu ea se procedeaza astfel: se elimina atentionarile si anularile corespunzatoare lor, se inlocuiesc toate locarile si delocarile elementelor cu locari si delocari atat pentru elementele respective cat si pentru toti descendentii lor, se construieste graful asociat programarii obtinute si ordonarea topologica a grafului (care este aciclic) da o programare seriala a tranzactiilor.
8.2. Detectarea erorilor si restabilirea informatiei
Pentru pastrarea consistentei bazei de date orice tranzactie trebuie fie sa se execute in totalitate fie sa nu se execute deloc. Acest lucru este asigurat de o parte componenta a SGBD numita administratorul de tranzactii. Procesul de asigurare al consistentei bazei de date la tratarea tranzactiilor utilizeaza comenzi de tipul COMMIT ce permite efectuarea efectiva a schimbarilor si respectiv ROLLBACK pentru anularea unor modificari facute de o tranzactie incomplet executata.
De obicei comanda COMMIT este ultima comanda executata intr-o trnzactie prin ea indicandu-se ca toate operatiile tranzactiei au fost executate cu succes si deci modificarile facute sunt considerate corecte. Comanda ROLLBACK semnaleaza aparitia unei situatii limita ce poate sa duca la inconsistenta bazei de date si sistemul trebuie sa restabileasca informatiile ca la inceperea efectuarii tranzactiei sau sa nu permita efectuarea efectiva a modificarilor facute de tranzactia respectiva. Cele mai multe sisteme adauga automat comanda COMMIT la terminarea trnzactiei in cazul cand nu sunt determinate erori si comanda ROLLBACK in caz contrar. In cazul aparitiei unor intreruperi in lucrul sistemului, la reluarea lucrului pentru toate tranzactiile active din sistem in momentul intreruperii se efectueaza o comanda ROLLBACK. Aceste tranzactii trebuiesc planificate din nou pentru executie.
Erorile ce pot declansa procesul de restabilire pot fi clasificate in erori locale care sunt produse de tranzactie si care afecteaza numai tranzactia respectiva si erori globale care pot afecta mai multe tranzactii active la un moment dat. Erorile globale pot sa fie erori de sistem (oprirea curentului electric, efectuarea eronata a unor comenzi, erori din sistemul de operare si altele) sau erori de mediu (functionarea incorecta a unei unitati de discuri sau a unei portiuni din memoria interna si altele)
Pentru a putea restabili informatiile, sistemul contine o structura numita log sau jurnal in care sunt continute informatii privind toate modificarile efectuate de tranzactii. Se pastreaza pe un mediu extern o lista a tranzactiilor active la un moment dat care se reactualizeaza dupa anumite intervale de timp (checkpoint). La aparitia unei erori globale de sistem se aplica urmatorul procedeu de restabilire a bazei de date:
1. Se incepe cu o lista UNDO ce contine tranzactiile active la ultima salvare
si cu lista REDO vida.
2. Se parcurge jurnalul din momentul ultimei salvari a tranzactiilor active.
3. Daca in jurnal se gaseste inceperea tranzactiei T, se adauga T listei UNDO.
4. Daca in jurnal se gaseste "commit" pentru tranzactia T, se muta tranzactia T
din lista UNDO in lista REDO.
5. Se parcurge jurnalul inapoi pana la "checkpoint" si se elimina modificarile
din baza de date efecuate de tranzactii din lista UNDO.
6. Se parcurge jurnalul de la "checkpoint" pana la sfarsit si se fac in baza de
date modificarile facute de tranzactiile din lista REDO.
7. Se pregateste sistemul pentru acceptarea unor noi tranzactii (eventual se
poate reincepe efectuarea tranzactiilor din lista UNDO).
Restabilirea in cazul erorilor de mediu se face prin intermediul copiilor periodice ale bazei de date si cu ajutorul jurnalului. Se pleaca de la ultima copie a bazei de date considerata corecta si se fac modificarile continute in jurnal pentru tranzactiile ce s-au terminat corect (cele din lista REDO date de procedura precedenta. Copiile bazelor de date se pastreaza de obicei pe benzi magnetice sau diskete.
In cazul cand tranzactiile afecteaza mai multe medii in modificari acestea sunt coordonate si aplicate sau nu pentru toate mediile. Se aplica in acest caz un protocol de commit in doua faze (1) cerere de modificare catre toate mediile implicate si (2) efectuarea modificarilor la raspunsuri pozitive sau restabiliri daca exista cel putin un raspuns negativ. Acest sistem permite restabilirile in cazul erorilor.
9. Baze de date distribuite
O baza de date distribuita permite ca o colectie arbitrara de relatii, dintr-o colectie arbitrara de baze de date aflate pe o mare varietate de masini diferite ce lucreaza sub diferite sisteme de operare si fiind legate prin diferite retele de comunicatie sa poata fi utilizate ca si cum ar constitui o singura baza dedate pe o singura masina.
Primele sisteme de baze de date distribuite au fost INGRES/STAR, versiune distribuita a lui INGRES, SQL*STAR versiune distribuita a lui ORACLE si R* versiune distribuita a lui DB2.
Principalele cerinte pe care trebuie sa le asigure un sistem de baze de date distribuite sunt: autonomia locala in organizarea si prelucrarea datelor, neutilizarea unei centralizari a evidentei si a datelor, posibilitatea de lucru continuu al nodurilor independent de schimbarile in configuratiile de lucru (adaugari sau eleminari de noduri), independenta localizarii si fragmentarii datelor (transparenta fizica), posibilitati de replicare (copiere) si independenta copiilor, prelucrarea distribuita a cererilor, administrarea distribuita a tranzactiilor, independenta de hardware, de sistemul de operare, de retea si de sistemul de gestiune a bazelor de date.
Una din cele mai dificile probleme de rezolvat pentru sistemele distribuite este minimizarea numarului si dimensiunii mesajelor. Aceasta problema se reflecta in strategiile de prelucrare a cererilor, in administrarea cataloagelor, in propagarea reactualizarilor, in controlul reacoperirilor, in controlul concurentei si in celelalte operatii.
9.1. Reprezentarea bazelor de date distribuite
Pentru bazele de date de dimensiuni foarte mari, cu un numar mare de utilizatori plasati in locuri diferite se pune problema reprezentarii lor pe fragmente in diferite unitati de calcul ce constituie nodurile unei retele. Fragmentele contin relatii intregi sau parti de relatii care prin operatii de uniune naturala si reuniune pot sa reconstituie relatia initiala. Pentru utilizator distribuirea unei baze de date este transparenta, el "vazand" baza de date ca si cum ar fi nedistribuita.
Deci o baza de date distribuita poate fi privita ca o multime de noduri (orase) legate intre ele sub forma unei retele, fiecare nod avand posibilitati de memorare si prelucrare date. Accesul la date se face prin intermediul unui procesor de fisiere (file server) si prelucrarea cererilor se face cu un procesor de tranzactii (transzction server). Baza de date se considera formata din mai multe elemente locabile, unele dintre ele putand eventual prin duplicare sa apara de mai multe ori in noduri diferite. Legatura intre noduri se face prin schimb de mesaje si de date. O buna distribuire a datelor poate sa aduca urmatoarele avantaje:
- o viteza de acces mai mare prin operarea frecventa a unor cereri ce
folosesc local un volum mai mic de date, fara a fi necesar un transfer
de date intre noduri;
- posibilitati mai bune de recuperare a informatiilor in cazul unor
caderi prin afectarea unei parti mai mici din baza de date;
- posibilitati de lucru modular si a preluarii sarcinilor unui nod
defect la un moment dat de catre celelalte noduri.
Un dezavantaj in acest caz il constituie aparitia unui flux mare de informatii intre noduri si de aici necesitatea rezolvarii unor probleme cum ar fi sincronizarea mesajelor, detectarea si corectarea unor perturbatii, eliminarea unor inconsistente datorate redondantelor.
Datele unei baze de date distribuite sunt privite atat din punct de vedere logic prin semnificatia pe care o au ele cat si actual prin modul de organizare si valorile reprezentate la un moment dat. Orice relatie R poate fi reconstituita din fragmentele R1,R2,...,Rn aflate in diferitele noduri fie prin uniune naturala R = R1 |X| R2 |X| ... |X| Rn si atunci spunem ca avem o fragmentare verticala, fie prin reuniune R = R1 U R2 U ... U Rn si atunci spunem ca avem o fragmentare orizontala.
Exemplul 5. . Consideram baza de date a conturilor curente din filialele CEC in care intervin ca atribute F (filiala CEC), N (numarul contului), T (total lei in cont), O (nuarul operatiei in cont), S (suma operata), P (posesor cont curent) si A (adresa posesor cont curent) si relatiile logice urmatoare:
CONTURI(F,N,T)
OPERARI(F,O,S)
POSESORI(N,P)
OPERAT(O,P)
CLIENTI(P,A)
Aceasta baza de date ar putea fi reprezentata distribuit de exemplu prin fragmentarea orizontala a primelor patru relatii si pastrarea informatiilor legate de conturile deschise la o filiala in nodul asociat acelei filiale iar informatiile despre clienti pot fi memorate la sediul central CEC fiind in general mai rar accesate. Relatiile anterioare pot fi considerate fragmente verticale pentru diferite vederi.
Cererile adresate unei baze de date distribuite sunt exprimate in raport de reltiile logice ce se pot reconstitui din fragmente prin operatii de reuniune si uniune naturala. Plecand de la acestea se construiesc expresii care au ca operanzi relatiile fizice. Pentru arborele rezultat se aplica transformari ce fac determinarea rezultatului final mai rapid cum ar fi coborarea cat mai mult posibil a selectiilor in arbore.
De obicei fragmentele contin anumite valori specifice in anumite campuri si aceste valori pot servi pentru identificarea informatiilor din fragment purtand numele de garda. In general, daca fragmentul R are garda g se poate inlocui orice folosire a lui R intr-o expresie cu @S/g(R) fara a schimba rezultatul. Daca prin coborarea unei selectii in arbore se ajunge la un conflict cu garda g atunci se poate elimina R din expresie.
Exemplul 5. . Sa presupunem pentru banca de date din exemplul precedent ca relatiile POSESORI si OPERAT sunt fragmentate in functie de locul unde s-a facut identificarea si respectiv operatia si ca sunt in retea trei filiale referite prin 1, 2 si 3. Pentru a raspunde la o cerere de tipul "lista persoanelor care au in contul deschis la filiala 1 peste 100000 lei" ar trebui sa se faca o uniune naturala intre relatiile CONTURI si POSESORI, sa se selecteze din rezultat tuplurile care au F=1 si T>100000 si apoi sa se ia proiectia dupa P. Acest mod de operare produce un mare flux de informatii intre cele trei noduri si ocupa mult spatiu suplimentar si timp de calcul. Cum cereri de tipul specificat sunt destul de frecvente se impune o reproiectare a bazei de date. Se considera mai intai vederea R(F,N,T,P) care se fragmenteaza orizontal dupa valorile din F in relatiile R1, R2 si R3 cu F devenita garda pentru fiecare din cele trei relatii. Apoi fiecare Ri, i=1,2,3 se fragmenteaza vertical in relatiile Ci(F,N,T) si Pi(N,P) deci au loc egalitatile
Ri = @S/F=i(Ri) = @S/F=i(Ci |X| Pi) si R = R1 U R2 U R3
si cererea initiala care se putea exprima sub forma
@P/P(@S/F=1@AT>100000(R))
capata in baza de date reproiectata forma
@P/P(@S/F=1(@S/T>100000(@S/F=1(C1 |X| P1) U @S/F=2(C2 |X| P2) U @S/F=3(C3 |X| P3))))
si prin coborarea selectiilor in arbore si eliminarea ramurilor cu conditii contradictorii se obtine cererea
@P/P(@S/T>100000(C1) |X| P1)
care se poate efectua fara transfer de informatie si cu putina memorie ocupata si timp de calcul scazut.
Reactualizarea bazelor de date distribuite nu este dificil de realizat. Inserarea unui tuplu intr-o relatie logica se traduce prin inserarea unor tupluri in unele din fragmentele asociate relatiei logice. Daca vrem sa inseram tuplul t in relatia logica R si R este de forma R = R1 |X| ... |X| Rn acasta revine la a insera t[Ri] in Ri pentru i=1,...,n. Daca R = R1 U ... U Rn atunci se determina un i astfel incat garda lui Ri sa corespunda valorii din t si se insereaza t in Ri. Daca nu exista nici-un i cu aceasta proprietate se da mesaj de eroare si daca sunt mai multi indici se alege unul dintre ei, de preferinta fragmentul ce corespunde nodului unde are loc cererea.
Pentru a sterge un tuplu t din relatia logica R si R este compusa din fragmente orizontale, atunci se sterge tuplul t din toate fragmentele in care apare. Daca R este compusa din fragmente verticale apar probleme suplimentare de rezolvat deoarece stergerea tuplurilor t[Ri] ar putea duce la pierderea de informatii fiind eliminate si alte tupluri s pentru care s[Ri] = t[Ri]. In sistemul R* problema se rezolva asociind fiecarui tuplu din relatiile logice fragmentate vertical cate un identificator unic si acesta este pastrat in fiecare fragment al relatiei logice. Stergerea unui tuplu revine la eliminarea din fragmente a tuplurilor care au identificatorul respectiv.
9.2. Optimizarea cererilor in baze de date distribuite
O alta problema importanta este legata de costul transmisiilor de date intre noduri. De exemplu pentru a efectua uniunea naturala dintre relatia R cu r elemente si relatia S cu s elemente costul transmiterii datelor este proportional cu c0 + min(r,s) unde c0 este timpul de initiere al unui mesaj, unitatea de timp este considerata timpul necesar pentru a transmite un tuplu si se presupune ca se face transferul unei copii a relatiei cu mai putine elemente in nodul relatiei cu mai multe elemente.
Pentru a micsora costul transmisiilor in bazele de date distribuite se utilizeaza o operatie suplimentara numita semiuniune. Se numeste semiuniunea relatiilor R si S si se noteaza R |X S relatia obtinuta prin expresia @P/R(R|X|S).Aceasta operatie se poate efectua de exemplu proiectand pe S dupa atributele comune lui R si S si apoi eliminand din R acele tupluri t care nu au t[R@OS] in aceasta proiectie adica se obtine expresia echivalenta R|X|@P/R@OS(S). Aceasta operatie nu este comutativa.
Daca proiectiile lui R si S dupa R@OS contin r' si respectiv s' elemente si daca R |X S si S |X R au r" si respectiv s" elemente, se poate calcula R |X| S cu procedeul urmator: se transfera @P/R@OS(S) in nodul lui R, se calculeaza R |X S in nodul lui R, se transfera R |X S in nodul lui S si se calculeaza (R |X S) |X| S in nodul lui S (sau simetric schimband intre ele R si S). Costul acestei strategii este 2c0 + s' + r" si se obtine un cost mai mic decat efectuarea directa a uniunii daca are loc inegalitatea
c0 + min(s' + r",r' + s") < min(r, s)
care de cele mai multe ori in practica este indeplinita.
Teorema 5. . Pentru orice relatii R si S are loc (R |X S) |X| S = R|X|S.
Demonstratie. Din definitia lui R |X S rezulta ca este inclusa in R si deci expresia din stanga este inclusa in expresia din dreapta. Reciproc, daca t este un tuplu al relatiei din dreapta rezulta ca t[R] este in R si t[S] este in S de unde rezulta ca t[R] este in R |X S si deci t este in relatia din stanga, deci si incluziunea reciproca este adevarata ceea ce demostreaza teorema.
Uniunea naturala a mai multor relatii R1 |X| R2 |X| ... |X| Rn se poate calcula prin efectuarea consecutiva a mai multor semiuniuni in care fiecare relatie Ri intervine prin submultimea sa @P/Ri(R1 |X| ... |X| Rn) numita reducerea lui Ri in raport cu R1,...,Rn. Foarte multe cereri corespund la astfel de reduceri.
Un sir de pasi de forma R := R |X S se numeste program semiuniune. Se poate asocia unei uniuni un hipergraf in care nodurile sunt atribute si muchiile sunt schemele relationale ce apar in uniune.
Teorema 5. . Daca expresia uniunii naturale corespunde la un hiopergraf aciclic atunci exista un program semiuniune care reduce orice relatie din uniune si daca este ciclic exista cel putin o relatie pentru care nu se poate face reducerea prin nici-un program semiuniune.
Demonstratie. Vom demonstra prima parte a teoremei aratand cum se construieste efectiv un program semiuniune pentru reducerea in raport cu R a unei uniuni cu hipergraf acilic asociat. Daca in uniune apare o singura relatie R se considera programul vid rezultatul fiind chiar relatia R data. Daca hipergraful este aciclic si are mai mult de o muchie, el are cel putin un spic, muchia S. Daca S nu este R si are elemente comune cu muchia T atunci se efectueaza operatia T := T |X S si se elimina din hipergraf muchia S si atributele din S - T. Daca S este R se construieste recursiv un program semiuniune care reduce pe T in raport cu celelalte relatii decat R si se adauga R := R |X T. In ambele cazuri problema determinarii unui program semiuniune se reduce la problema corespunzatoare unei uniuni cu o relatie mai putin ceea ce asigura determinarea unui program semiuniune dupa un numar finit de pasi. Echivalenta expresiilor obtinute in fiecare din cele doua cazuri cu expresia initiala este usor de vazut.
Dintre multiplele programari semiuniune posibile asociate unei uniuni cu hipergraf aciclic este dificil de ales cea mai eficienta mai ales ca de multe ori eficienta depinde de continutul actual al relatiilor. Exista o clasa de cereri pentru care se poate determina programul optim numite cereri lant. O cerere lant corespunde reducerii lui R1 in raport cu R1,R2,...,Rn si relatiile sunt astfel incat Ri @O Rj = @O/ pentru orice i si j cu 1@<= i < i+1 < j @<= n.
O solutie posibila in acest caz este: Rn-1 := Rn-1 |X Rn, Rn-2 := Rn-2 |X Rn-1, ..., R1 := R1 |X R2.
Sa notam cu ai dimensiunea proiectiei lui Ri pe Ri-1 @O Ri pentru i > 1 si cu bi dimensiunea proiectiei lui Ri pe Ri @O Ri+1 pentru i < n si sa presupunem ca exista o constanta d astfel incat la efectuarea semiuniunii lui Ri cu uniunea altor k relatii dimensiunea proiectiei pe Ri are dimensiunea aid\k sau respectiv bid\k. Vom nota cu R/i\lr expresia @P/Ri(Rl |X| Rl+1 |X| ... |X| Rr) cu 1 @<= l @<= i @<= r @<= n. Cererea lant corespunde lui R/1\1n.
Lema 5. . Daca nici-un pas al unui program semiuniune nu face semiuniunea unor scheme relationale disjuncte si programul calculeaza o cerere lant pe R1,...,Rn, atunci fiecare pas al programului calculeaza o valoare R/i\lr pentru anumite valori i, l si r.
Demonstratie. Prin inductie dupa numarul pasilor programului. Fiecare pas in program este semiuniunea a doua relatii alaturate din lant Ri |X Ri+1 sau Ri+1 |X Ri. Pentru zero pasi proprietatea este adevarata deoarece Ri este R/i\ii si daca un pas este Ri := Ri |X Ri+1 si inainte de acest pas valoarea lui Ri corespunde la R/i\jk si valoarea lui Ri+1 corespunde la R/i\lm se vede imediat ca dupa efectuarea pasului respectiv Ri corespunde la R/i\pq unde p = min(j,l) si q = max(k,m). Cel de-al doilea caz se trateaza similar demonsrand lema.
Lema 5. . Cu parametrii c0, d, a2, ..., an, b1, ..., bn-1 definiti anterior, costul semiuniunii Ri-1 |X R/i\lr este c0 + aid\r-l si costul semiuniunii R/i\lr X| Ri+1 este c0 + bid\r-l iar in fiecare program semiuniune optim al cererii lant R1,...,Rn fiecare R/i\lr care se calculeaza se realizeaza in unul din urmatoarele moduri:
1. Se calculeaza R/i\ik cu pasul Ri := Ri |X Ri+1 unde Ri+1 are valoarea curenta
R/i+1\i+1,k.
2. Se calculeaza R/i\ji cu pasul Ri := Ri |X Ri-1 unde Ri-1 are valoarea curenta
R/i-1\j,i-1.
3. Se calculeaza R/i\jk prin pasi Ri := Ri |X Ri-1 si Ri := Ri |X Ri+1 intr-o
ordine data, in momentul executarii acestor pasi valoarea lui Ri-1 este
R/i-1\j,i-1 si a lui Ri+1 este R/i+1\i+1,k.
4. Se calculeaza R/i\jk cu pasul Ri := Ri |X Ri-1 unde Ri-1 are valoarea curenta
R/i-1\jk.
5. Se calculeaza R/i\jk cu pasul Ri := Ri |X Ri+1 unde Ri+1 are valoarea curenta
R/i+1\jk.
Algoritmul 5. . Pentru a determina un program semiuniune optim pentru o cerere lant @P/R1(R1 |X| ... |X| Rn) se procedeaza in felul urmator:
Fie c/i\jk costul calculului lui R/i\jk intr-un program semiuniune optim si numim jk-familie multimea . Se calculeaza recursiv costurile minime ale elementelor fiecarei jk-familii in ordinea crescatoare a lui k-j dupe formulele
a. c/i\ii = 0 pentru orice i.
b. c/i\ik = c0 + ai+1d\k-i-1 min(c/i+1\i+1,k, dc/i+1\ik) pentru k > i.
c. c/i\ji = c0 + bi-1d\i-j-1 min(c/i-1\j,i-1, dc/i-1\ji) pentru j < i.
d. c/i\jk = c0 + min(bi-1d\k-jc/i-1\jk, ai+1d\k-jc/i+1\jk,
c0 + b/i-1d\i-j-1c/i-1\j,i-1 +ai+1d\k-i-1c/i+1\i+1,k) pentru j<i<k.
Pentru fiecare jk-familie se evalueaza costurile elementelor sale plecand de la elementul cu costul cel mai mic de forma R/i\jk. Dupa ce s-a evaluat c/1\1n se determina elementele care au contribuit la calculul sau de forma R/i\jk si se scrie programul semiuniune corespunzator acestor elemente aplicand procedeul din lema 5. .
Exemplul 5. . Fie relatiile R1(A,B), R2(B,C) si R3(C,D) si sa presupunem ca c0=10, d=0.8, b1=10, a2=50, b2=20 si a3=1000. Aplicand algoritmul precedent se obtine mai intai c/1\11 = c/2\22 = c/3\33 = 0, apoi pentru a calcula costurile 12-familiei se obtin formulele
c/1\12 = 10 + min(50, 40+c/2\12)
c/2\12 = 10 + min(10, 8+c/1\12)
si cum ambele elemente au valori mai mari ca 10 rezulta valorile 60 si respectiv 20 deoarece minimul este obtinut pentru prima componenta. Analog pentru 23-familia obtinem formulele
c/2\23 = 10 + min(1000, 800+c/3\23)
c/3\23 = 10 + min(20, 16+c/2\23)
si deoarece c/2\23 este mai mare decat 810 rezulta ca 16+c/2\23 este mai mare ca 20 si deci c/3\23 este 30 de unde rezulta c/2\23 = 840. In sfarsit pentru 13-familia obtinem formulele
c/1\13 = 10 + min(40+c/2\23, 32+c/2\13)
c/2\13 = 10 + min(6.4+c/1\13,640+c/3\13,10+10+1000)
c/3\13 = 10 + min(16+c/2\12,12.8+c/2\13)
si inlocuid valorile cunoscute se poate evalua imediat c/3\13 = 46, apoi c/2\13 = 696 si in final c/1\13 = 738. Pentru a construi programul semiuniune se procedeaza astfel: pentru calculul lui c/1\13 s-a folosit c/2\13 deci ultimul pas in program este R1 := R1 |X R2 si calculul lui c/2\13 s-a facut cu ajutorul lui c/3\13 deci penultimul pas este R2 := R2 |X R3 iar c/3\13 a fost calculat cu c/2\12 care a fost calculat direct si deci corespunde la R2 := R2 |X R1 de unde rezulta urmatorul program
R2 := R2 |X R1; R3 := R3 |X R2; R2 := R2 |X R3; R1 := R1 |X R2.
9.3. Optimizarea cererilor in sistemul R*
Sistemul R* este o extindere experimentala a sistemului R pentru baze de date distribuite. Ca si in sistemul R fiecare cerere este mai intai optimizata si apoi este evaluata. Optimizarea se face plecand de la o expresie algebrica in care apar ca operanzi relatii fizice si constante si ca operatori selectia, proiectia, uniunea, reuniunea si o noua operatie numita alegere (CHOICE) care permite considerarea uneia din copiile identice ale unei relatii fizice la un moment dat in cazul cand exista mai multe copii.
Se fac modificari in arborele asociat expresiei prin identificarea nodurilor dintr-un subarbore numit cluster care contin acelas operator asociativ si comutativ (reuniune, uniune sau alegere) inlocuind astfel de subarbori cu un nod etichetat cu operatorul comun din care pleaca arce catre toti fii nodurile identificate si avand drept tata nodul care este tatal nodului de intrare in cluster (nodul ce precede toate celelalte noduri din cluster). Arborele obtinut se numeste arbore compactificat. De exemplu in fig. 5. este arborele corespunzator unei expresii care contine doua clustere cu operatori reuniune si respectiv uniune. Acestui arbore ii corespunde arborele compactificat din fig. 5. .
U U
/ \ // \
/ \ / / \
/ \ / / \
U |X| R S |X|
/ \ / \ / / \ \
/ \ / \ / / \ \
/ \ / \ / / \ \
R S |X| |X| T U V W
/ \ / \
/ \ / \ Figura 5.
/ \ / \
T U V W
Figura 5.
In algoritmul de optimizare a cererilor se considera ca fiecare relatie se afla intr-un singur nod prin redenumirea eventuala a unor copii si aplicarea operatorului de alegere in cazul cand intervin in expresii. Se tine sema de localizarea operanzilor si de localizarea rezultatului explorandu-se diferitele ordini de evaluare, diferitele strategii de plasare a rezultatelor intermediare si diferitele moduri de evaluare a uniunilor. Functia cost are componente atat pentru timpul de transmitere a datelor cat si pentru timpul de efectuare a operatiilor in diferite noduri, dominant fiind primul dintre acestea.
Pentru reuniunea a doua relatii costul este zero daca nodul rezultatului este acelasi cu cel al operanzilor, este dimensiunea relatiei din afara nodului rezultatului daca acesta coincide cu nodul unuia din operanzi si este suma dimensiunilor celor doua relatii daca nodul rezultatului nu coincide cu al nici-unui operand. Pentru operatorul de alegere costul este zero daca exista o copie a relatiei in nodul rezultatului si este dimensiunea relatiei altfel.
Uniuinea relatiilor R si S se poate face in unul din urmatoarele moduri:
1. Se trece R in nodul lui S si rezultatul ramane aici; cost c0+|R|.
2. Se trece S in nodul lui S si rezultatul ramane aici; cost c0+|S|.
3. Se trec R si S in al treilea nod si rezultatul ramane in el;cost 2c0+|R|+|S|.
4. Pentru fiecare tuplu t din R se determina tuplurile u din S care au valorile
lui T pentru atributele comune si se transfera acestea in nodul lui R unde se
obtine rezultatul; cost |R|(c0+|S|/I) unde I este dimensiunea proiectiei lui
S pe multimea atributelor comune lui R si S.
5. La fel ca 4. cu schimbarea rolurilor celor doua relatii.
Se pot genera si alte strategii sau considera cazuri particulare cand cele doua relatii se afla in acelasi nod care poate sa coincida sau nu cu al rezultatului.
Algoritmul 5. . Pentru evaluarea unei cereri pentru o baza de date distribuita reprezentata sub forma arborelui compactificat si cu indicarea nodului care sa contina rezultatul final se face prin urmatoarea metoda:
- Se coboara in arbore cat mai mult posibil selectiile si proiectiile. Daca un
operator precede operatorul de alegere se aplica acel operator la toti fii
operatorului de alegere. Se elimina ramurile cu conditii conflictuale si
conditiile redondante.
- Se generaza subarborii arborelui dat evaluandu-se pentru fiecare din ei
costurile. O frunza etichetata cu R da un singur subarbore caruia ii
corespunde expresia R. Fie n un nod intern astfel incat pentru fiecare din fii
sai c1,c2,...,ck au fost determinate multimile de expresii asociate S1,S2,...,
Sk. Daca n este selectie sau proiectie atunci k=1 si se formeaza expresiile
corespunzatoare lui n prin aplicarea pentru radacina fiecarei expresii din S1
a operatorului din n (selectie sau proiectie). Daca operatorul din n este o
alegere atunci multimea expresiilor asociate lui n este reuniunea multimilor
expresiilor asociate fiilor lui. Daca n este reuniune sau uniune se
construiesc mai intai toti arborii binari neordonati (nu conteaza ordinea
fiilor pe fiecare nivel) cu noduri etichetate cu operatorul asociat lui n si
cu frunzele c1,...,ck si se obtine multimea expresiilor asociate lui n prin
inlocuirea frunzelor din acesti arbori cu toate combinatiile de expresii din
multimile asociate S1,...,
- Se estimeaza costurile asociate expresiilor construite considerand rezultatul
in fiecare din noduri. Pentru o frunza etichetata cu R costul asociat este
zero pentru rezultat in nodul lui R si este c0+|R| pentru rezultat in alt nod.
Fie n un nod intern. Daca n este selectie sau proiectie se obtine un cost
minim daca rezultatul lui n este in acelasi nod cu rezultatul fiului lui n si
deci costul lui n coincide cu costul fiului sau pentru fiecare nod in parte.
Daca n este reuniune pentru a afla cel mai bun cost de a calcula n in nodul a
se considera minimul dupa toate nodurile b si c a costurilor de calcul a
fiilor lui n in b si in c la care se adauga eventualele costuri de transfer
cand b sau c nu coincid cu a. Daca n este uniune se procedeaza ca la reuniune
considerand toate cazurile posibile pentru efectuarea uniunii.
- Se determina arborele ce corespunde costului minim si se descrie programul de
evaluare corespunzator lui.
Considerand ca pentru fiecare relatie R si fiecare submultime de atribute X din R se poate estima numarul tuplurilor din @P/X(R) si notand cu IR numarul |@P/R@OS(R)| si cu IS numarul |@P/R@OS(S)| se obtine estimarea
|R |X| S| = |R||S|/max(IR,IS)
9.4. Problema concurentei
In cazul bazelor de date distribuite controlul concurentei se face mai dificil pe de o parte din cauza numarului mare de mesaje de transmis intre noduri si pe de alta parte prin posibilitatea de lucru in paralel in diferite noduri. Pentru a micsora numarul de mesaje, locarile se fac la nivele mari, de cele mai multe ori la nivel de relatii, fiecarei tranzactii corespunzandu-i in acest fel un numar mic de locari.
O problema suplimentara este asigurarea identitatii copiilor unei relatii existente in diferite noduri. Si in acest caz solutiile sunt mai simple daca se lucreaza cu tranzactii in doua faze deci care mai intai fac locarile, apoi fac operatiile de citire sau scriere si in final fac delocarile.
Una din cele mai utilizate strategii in acest caz este: locarea pentru citire a elementului A locheaza una din copiile lui A si locarea la scriere a lui A locheaza toate copiile lui A. Locarile se fac prin trimiterea de mesaje de cerere de locare catre nodurile ce au copii ale relatiei si obtinerea unor confirmari sau infirmari a posibilitatii locarii eventual si cu transmiterea valorilor elementelor locate.
O alta strategie se numeste strategia majoritara de locare si consta in posibilitatea locarii la citire sau scriere daca se pot loca mai mult de jumatate dintre copii de tranzactia respectiva. Acesta metoda micsoreaza numarul mesajelor la locarile pentru scriere si il mareste pe cel de la locarile pentru citire. In plus pot sa apara interblocari prin detinerea de copii de mai multe tranzactii dar nici-una neavand majoritatea.
Daca n este numarul de copii si k > n/2 atunci se poate defini o generalizare a celor doua strategii precedente numita k-din-n in care are loc o locare la scriere daca sunt locabile cel putin k dintre copii si poate fi o locare la citire daca sunt locabile cel putin n-k+1 copii.
Strategia copiei primare considera pentru fiecare relatie un reprezentant ce poate sa aiba un marcaj de scriere sau marcaj de citire. Pentru fiecare element A poate exista numai un marcaj de scriere si in acest caz nu mai poate fi un alt tip de marcaj iar nodul care a facut marcarea poate efectua locarea la citire si scriere pentru tranzactiile din nodul respectiv pentru A sau poate exista un marcaj de citire si in acest caz pot sa fie si alte marcaje de citire iar nodul care a facut marcarea poate efectua locarea numai la citire pentru tranzactiile din nodul respectiv pentru A.
Metoda numita strategia nodului central este asemanatoare cu precedenta cu deosebirea ca pentru toate elementele marcajele sunt tinute in acelasi nod care ar putea sa nu contina nici-o copie a elementului respectiv. Aceasta metoda este vulnerabila din cauza posibilitatii caderii nodului central care poate sa intrerupa complet lucrul cu baza de date si din cauza timpilor de asteptare prin concentrarea mesajelor catre un singur nod.
Interblocarile pot fi prevenite prin impunerea unor protocoale suplimentare ca de exemplu exprimarea celerilor de locare in fiecare tranzactie in ordinea lexicografica a numelor elementelor si cautarea intr-o ordine data a copiilor din diferitele noduri. Se pot considera si strategii de detectare si eliminare a interblocarii dupa modelele deja studiate.
Daca unele procesoare din noduri nu mai functioneaza din anumite motive sistemul poate sa asigure continuarea lucrului pentru tranzactiile care au asigurate toate resursele necesare. La reluarea lucrului sistemul trebuie sa faca toate modificarile necesare pentru a actualiza informatiile din nodurile cazute. De obicei modificarile unui nod cazut sunt pastrate intr-un jurnal al unui alt nod. Se fac si comparatii intre diferitele copii ale relatiilor si se actualizeaza dupa copia cu data cea mai recenta.
|
