DEPENDENTE FUNCTIONALE

Proiectarea logica a bazei de date urmareste printre altele diminuarea redundantei si asigurarea securitatii datelor. Acest scop se poate atinge, daca se cunosc a priori constrangerile ce pot fi aplicate asupra datelor. Dependentele sunt constrangeri impuse datelor in baza de date. Ba mai mult, multimea de dependente este partea esentiala a schemei unei relatii, deci si a schemei bazei de date. Dependentele functionale au fost primele constrangeri logice considerate in modelul relational. Ele formeaza cel mai simplu si cel mai larg raspandit tip de dependente.

Prezentul capitol e consacrat regulilor de inferenta, inchiderilor si diverselor forme de acoperiri ale dependentelor functionale.

1. Notiuni generale

Sa consideram relatia orar din fig. 1.

Aceasta relatie arata care profesor preda disciplina data, carei grupe, in ce zi a saptamanii, la ce ora si in ce sala. Atributele ce formeaza schema acestei relatii nu pot primi orice valori. Atributele se afla intr-o interdependenta. Aici, in particular, se suprapun asupra atributelor urmatoarele constrangeri:

o disciplina este predata unei grupe de studiu de un singur profesor;

profesorul, in ziua data, la ora data se gaseste intr-o singura sala;

in ziua data, la ora data, in sala data se preda o singura disciplina.

Aceste constrangeri ce reflecta o interdependenta intre atribute sunt exemple de dependente functionale. Dependenta functionala este o generalizare a notiunii de cheie.

Constrangerile de mai sus pot fi formulate:

DISCIPLINA GRUPA determina functional PROFESOR sau, ce e echivalent PROFESOR e determinat functional de DISCIPLINA GRUPA;

PROFESOR ZI ORA determina functional SALA;

ZI ORA SALA determina functional DISCIPLINA;

si notate respectiv:

DISCIPLINA GRUPA PROFESOR;

PROFESOR ZI ORA SALA;

ZI ORA SALA DISCIPLINA.

Unica posibilitate de a determina dependentele functionale consta intr-o analiza cu luare-aminte a semanticii atributelor. In acest sens dependentele sunt de fapt asertiuni despre lumea reala. Ele nu pot fi demonstrate. Dar ele pot si trebuie sa fie sustinute de SGBD-uri. Majoritatea sistemelor sustin numai dependentele functionale determinate de cheile relatiei. Dar sunt si sisteme ce sustin dependente functionale arbitrare.

Trebuie mentionat ca declararea dependentelor functionale intr-o baza de date este o decizie pe care o ia numai proiectantul bazei de date. Odata declarate SGBD-ul va sustine aceste constrangeri. In afara de aceasta, dupa cum se va vedea in celelalte sectiuni, gratie dependentelor, exista o structura mai eficienta de pastrare a datelor. Dependentele functionale vor servi la proiectarea schemelor bazelor de date cu anumite proprietati dezirabile.

Definitia 1. Fie relatia r cu schema R si X,Y R. Vom spune ca dependenta functionala X Y este valida in relatia r (sau relatia r satisface dependenta functionala X Y), daca, pentru orice doua tupluri din r, fie t₁ si t₂, din conditia ca tuplurile au X-valori identice, urmeaza ca au si Y-valori identice, adica t₁[X]=t₂[X]Tt₁[Y]=t₂[Y].

Daca X Y e valida in r(R), vom spune ca X determina functional Y sau, ca Y e determinat functional de X. In aceasta definitie (si mai departe) simbolul 'T' noteaza 'implica'.

Deci dependenta functionala X Y reprezinta o restrictie de integritate aplicata tuplurilor relatiei r(R), in sensul ca oricare doua tupluri din r care prezinta o aceeasi valoare pentru X trebuie sa prezinte o aceeasi valoare pentru Y.

Definitia 1 poate fi interpretata si in felul urmator: relatia r(R) satisface dependenta functionala X Y, daca relatia p_Y s_X=x(r)) contine nu mai mult de un tuplu pentru orice valoare x a atributului X.

Partea stanga a dependentei poarta numele de determinant, iar partea dreapta a dependentei poarta numele de determinat. Astfel in cadrul dependentei X Y, X este determinantul, iar Y determinatul.

Exemplul 1. Consideram relatiile din fig.2. In ele sunt valide urmatoarele dependente functionale. In relatia r₁: A B; in relatia r₂: A B, B A; in relatia r₃: A B.

Pentru a verifica daca o dependenta e valida intr-o relatie data, se utilizeaza urmatorul algoritm.

Algoritmul SATISF (r, X Y)

Intrare: Relatia r(R), dependenta functionala X Y, unde X,Y R.

Iesire: Adevar, daca relatia r satisface dependenta functionala X Y; fals - in caz contrar.

Se sorteaza tuplurile relatiei r in asa fel, ca tuplurile cu X-valori egale sa fie grupate impreuna.

Se verifica daca multimea de tupluri cu X-valori egale are si Y-valori egale, atunci la iesire obtinem adevar; in caz contrar - fals.

Mentionam ca nu ne intereseaza dependentele functionale intamplatoare, dar numai acele ce decurg din semantica atributelor. De exemplu, in relatia orar e valida si dependenta functionala PROFESOR DISCIPLINA. Dar ea nu reprezinta o constrangere ce reflecta lumea reala, fiindca in realitate un profesor poate si, de regula, preda mai multe discipline.

Numai dependentele neintamplatoare, asigura integritatea semantica a bazei de date. De exemplu, daca un utilizator doreste sa insereze in relatia orar un tuplu:

Add(orar; <Vasilache 'Structuri de date' luni 8:00 c942 402>),

sistemul de gestiune va stopa efectuarea acestei operatii, fiindca va fi violata dependenta functionala ZI ORA SALA DISCIPLINA. Daca SGBD-ul nu sustine dependentele functionale, atunci se poate intampla ca intr-o sala in acelasi timp se vor preda doua discipline diferite.

2. Reguli de inferenta

Intr-o relatie r(R) in orice moment sunt valide o multime de dependente functionale, sa zicem F. Adica F este o multime de dependente satisfacuta de relatia r(R). Aici apare aceeasi problema ca si in cazul cheilor. O extensie a relatiei satisface multimea F de dependente functionale, in timp ce alta extensie nu satisface. Pe noi ne intereseaza numai dependentele ce sunt satisfacute de orice extensie a relatiei r(R). Dar pentru aceasta sunt necesare cunostinte asupra semanticii relatiei r(R). Vom considera ca multimea F de dependente functionale este definita pe multimea R de atribute ce formeaza schema relatiei r si orice extensie a relatiei r satisface multimea F.

Evident ca multimea de dependente valide in r(R) este finita, fiindca finita este schema R. Prin urmare, s-ar putea verifica daca r satisface dependentele din F, aplicand algoritmul SATISF. Insa astfel de solutie este foarte laborioasa. Exista o alta cale. Daca sunt cunoscute niste dependente, din ele pot fi deduse altele.

Definitia 2. Fie relatia r cu schema R, F o multime de dependente functionale si f o dependenta asupra R. Notam cu SAT(F) multimea tuturor relatiilor asupra R ce satisface orice dependenta din F. Vom spune ca F logic implica f, sau f este consecinta logica a F, scriem F|=f, daca orice relatie r(R) ce satisface dependentele din F satisface si f, adica

r(R) I SAT(F) T r(R) I SAT(F

O regula de inferenta stabileste ca, daca o relatie satisface anumite dependente, ea trebuie sa satisfaca si alte dependente. Vom considera sase reguli de inferenta a dependentelor functionale.

Fie relatia r definita pe multimea de atribute R si fie W,X,Y,Z R.

DF1. Regula reflexivitatii. Daca Y X, atunci X Y.

Demonstrarea acestei afirmatii este evidenta. Nu putem avea intr-o relatie doua tupluri cu X-valori egale si sa nu fie egale componentele lor pentru o submultime a lui X.

Definitia O dependenta X Y este triviala daca Y X.

Regula DF1 genereaza numai dependente triviale si ea nu depinde de F. Intrucat X R, atunci X si R X sunt dependente triviale. Deoarece X X, X X e dependenta triviala. Dintre aceste dependente prima, X , nu are nici o aplicare practica.

DF2. Regula incrementarii. Daca X Y si Z W, atunci XW YZ.

Demonstratie. Fie r satisface dependenta functionala X Y, insa in ea exista doua tupluri t₁ si t₂ cu XW-valori egale, dar componentele YZ nu coincid. Conform regulii DF1 tuplurile t₁ si t₂ au Z-valori egale (fiindca Z W). Atunci tuplurile trebuie sa nu coincida macar pe un atribut din Y. Dar aceasta inseamna ca tuplurile t₁ si t₂ au X-valori egale si nu au Y-valori egale, ce contrazice ipoteza ca relatia r satisface dependenta functionala X Y.

Sa observam ca regula DF2 are mai multe cazuri speciale. Daca Z= si X Y, atunci XW Y pentru orice submultime W din R. Daca W=Z si X Y, atunci XW YW. Daca X=W, Z=X si X Y, atunci XX XY, adica X XY.

Exemplul 2. Consideram relatia din figura  Relatia r(ABCD) satisface dependenta functionala A B. Conform regulii DF2 in aceasta relatie sunt valide si dependentele AB B, AC B, AD B, ABC B, ABD B, ACD B, ABCD B, AC BC, AD BD, ABC BC, ABD BD, ACD BC, ACD BD, ACD BCD, ABCD BC, ABCD BD, ABCD BCD.

DF Regula aditivitatii. Daca X Y si X Z, atunci X YZ.

Demonstratie. Presupunem contrariul: in relatia r(R) exista doua tupluri t₁ si t₂, pentru care t₁[X]=t₂[X], dar t₁[YZ] t₂[YZ]. Atunci, sau t₁[Y] t₂[Y], sau t₁[Z] t₂[Z], sau ambele concomitent. Dar aceasta contrazice presupunerea, ca relatia r satisface dependentele X Y si X Z.

Exemplul Relatia r(ABCD) reprezentata in fig.3 satisface dependentele functionale A B si A C. Conform regulii DF3, relatia r trebuie sa satisfaca si dependenta A BC.

DF4. Regula proiectivitatii. Daca X YZ, atunci X Y.

Demonstratie. Afirmatia este adevarata, fiindca, daca r satisface X YZ, atunci pentru orice doua tupluri t₁ si t₂ din t₁[X]=t₂[X] urmeaza t₁[YZ]=t₂[YZ] si tuplurile vor coincide si pe orice submultime ale multimii YZ. Deci t₁[Y]=t₂[Y].

Exemplul 4. Relatia din fig.3 satisface dependenta functionala A BC. Conform regulii DF4, ea satisface si dependentele A B si A C.

DF5. Regula tranzitivitatii. Daca X Y si Y Z, atunci X Z.

Demonstratie. Pentru a demonstra regula DF5, vom presupune contrariul. Fie relatia r satisface dependentele X Y si Y Z, dar nu satisface dependenta X Z. Atunci relatia r are cel putin doua tupluri t₁ si t₂, pentru care t₁[X]=t₂[X], iar t₁[Z] t₂[Z]. Daca t₁[Y]=t₂[Y], atunci inegalitatea t₁[Z] t₂[Z] contrazice presupunerea ca in r e valida dependenta functionala Y Z. Daca t₁[Y] t₂[Y], atunci egalitatea t₁[X]=t₂[X] contrazice presupunerea ca X Y e valida in r.

Exemplul 5. Relatia r(ABCD), reprezentata in fig.4, satisface dependentele functionale A B si B C. Conform regulii tranzitivitatii, relatia r satisface si dependenta functionala A C.

DF6. Regula pseudotranzitivitatii. Daca X Y si YW Z, atunci XW Z.

Demonstratie. Presupunem contrariul: relatia r(R) satisface dependentele functionale X Y si YW Z, dar nu satisface dependenta functionala XW Z. Adica exista doua tupluri t₁, t₂ Ir pentru care t₁[XW]=t₂[XW] si t₁[Z] t₂[Z]. Din egalitatea t₁[XW]=t₂[XW] urmeaza t₁[X]=t₂[X] si t₁[W]=t₂[W]. Pot avea loc doua cazuri: sau t₁[YW]=t₂[YW], sau t₁[YW] t₂[YW].

Fie t₁[YW]=t₂[YW]. Atunci din conditia ca t₁[Z] t₂[Z] reiese ca dependenta functionala YW Z nu e valida in r.

Fie t₁[YW] t₂[YW]. Intrucat t₁[W]=t₂[W] rezulta ca t₁[Y] t₂[Y]. Din ultima inegalitate si din conditia t₁[X]=t₂[X] urmeaza ca relatia r nu satisface dependenta functionala X Y.

Si intr-un caz si in altul am ajuns la contradictie. Deci din X Y si YW Z urmeaza XW Z.

Asadar, daca W,X,Y,Z R, atunci in orice relatie r cu schema R sunt valide regulile de inferenta din fig.5.

Sa observam ca proiectivitatea (DF4) este, intr-un sens, regula inversa regulii aditivitatii (DF3). Regula DF3 se utilizeaza pentru a uni doua dependente cu determinante egale in una, in timp ce regula DF4 - pentru descompunerea unei dependente.

Axiomele Armstrong

Definitia 4. Fie F o multime de dependente asupra R si fie f o dependenta functionala asupra R. Derivatie a dependentei f din F, notata cu F|-f, este o consecutivitate finita de dependente functionale f₁,f₂,,f_k unde:

orice dependenta f_i poate fi dedusa din (o submultime a multimii) F , aplicand regulile de inferenta DF1-DF6;

f este ultimul element, f_k, in consecutivitate.

Remarca. Conditia (1) mai poate fi formulata in felul urmator. Orice dependenta f este element al multimii F sau se deduce din consecutivitatea , aplicand regulile de inferenta DF1-DF6.

Daca F|-f, vom spune ca F deriva f sau ca f e derivabila din F. Daca G este multime de dependente functionale, atunci prin F|-G se subintelege ca orice dependenta functionala din G e derivabila din F.

E clar ca, daca in conditia (1) a definitiei 4 multimea de dependente functionale F e vida, adica |-f, atunci f e dependenta triviala, fiindca singura regula de inferenta corespunzatoare poate fi doar DF1.

Cu ajutorul regulilor de inferenta putem deduce noi dependente functionale din cele date.

Exemplul 4. Fie r o relatie cu schema R si X,Y,Z R. Presupunem ca in r(R) sunt valide dependentele XY Z si X Y. Atunci, conform regulii DF6, relatia r satisface si dependenta XX Z care se reduce la X Z.

Pentru a combate o afirmatie despre validitatea unei dependente functionale, e suficient de a aduce un exemplu de relatie ce nu satisface afirmatia data.

Exemplul 5. Sa combatem afirmatia ca dependenta XY ZW implica dependenta X Z. Relatia r(ABCD) din fig.6 satisface dependenta functionala AB CD, dar nu satisface dependenta A C.

Unele reguli de inferenta pot fi deduse din altele. Armstrong a aratat ca regulile DF1, DF2 si DF5 formeaza o multime de reguli independente, iar regulile DF3, DF4 si DF6 pot fi deduse din DF1, DF2 si DF5. Multimea de reguli de inferenta este cunoscuta sub denumirea de axiome Armstrong.

Teorema 1. Regulile DF3, DF4 si DF6 se deduc din regulile DF1, DF2, DF5.

Demonstratie. Sa aratam ca regula DF3 se deduce din regulile DF1, DF2, DF5, adica |-X YZ, aplicand doar DF1, DF2, DF5. Intr-adevar, aceasta asertiune are loc, fiindca putem construi urmatoarea consecutivitate de derivare.

f₁:=X Y (dependenta data),

f₂:=X XY (f₁|-f₂ aplicand DF2),

f₃:=X Z (dependenta data),

f₄:=XY YZ (f₃|-f₄, aplicand DF2),

f₅:=X YZ (|-f₅, aplicand DF5).

Fiindca X YZ este ultimul, f₅, element in consecutivitate, DF3 se deduce din DF2 si DF5.

Sa ne convingem ca regula DF4 se deduce din DF1, DF2, DF5, adica X YZ|-X Y, aplicand regulile DF1, DF2, DF5. Aceasta se confirma de urmatoarea consecutivitate de derivare.

f₁:=X YZ (dependenta data),

f₂:=YZ Y (dependenta triviala, aplicand DF1),

f₃:=X Y (|-f₃, aplicand DF5).

Deci, regula DF4 se deduce din DF1 si DF5.

In sfarsit, sa aratam ca |-XW Z, aplicand regulile DF1, DF2 si DF5. Putem construi urmatoarea consecutivitate de dependente functionale.

f₁:=X Y (dependenta data),

f₂:=XW YW (f₁|-f₂ aplicand DF2),

f₃:=YW Z (dependenta data),

f₄:=XW Z (|-f₄, aplicand DF5).

Deci, regula DF6 se deduce din regulile DF1, DF2, DF5.

Definitia 5. Fie F o multime de dependente functionale asupra schemei R si X,Y R. Inchiderea multimii F, notata cu F⁺, se defineste recursiv:

F F⁺;

Daca F¹ F si F¹|-X Y, atunci X YI F⁺;

Nimic altceva nu e in F⁺.

Deci, F⁺ =F . Cu alte cuvinte, inchiderea unei multimi de dependente functionale, F⁺, reprezinta multimea tuturor dependentelor functionale care se pot deriva din multimea F, aplicand axiomele Armstrong. Este clar ca F⁺=(F⁺)⁺.

Exemplul 6. Fie relatia r(ABC) si F=. Atunci F⁺= .

In F⁺ primele nouasprezece dependente sunt triviale si se deriva din multimea de dependente, aplicand DF1, adica |-. Alte dependente X Y se deriva din Z Y, unde Z X, aplicand regula incrementarii (DF2), adica |-. In F⁺ avem sase dependente deduse, aplicand regula DF2 asupra F. Deci AB C|- si |-. Regula tranzitivitatii nu genereaza dependente netriviale. In afara de aceasta, F⁺ contine cele doua dependente din F. In total F⁺ consta din douazeci si sapte dependente.

Din exemplul de mai sus, se observa ca numarul de dependente ce alcatuiesc F⁺ este destul de mare in raport cu F.

Daca F= , atunci F⁺ consta numai din dependente triviale. Fiindca orice relatie r(R) satisface orice dependenta triviala asupra R, dependentele triviale, bineinteles, nu se considera constrangeri asupra relatiei. Intrucat R are 2^|R| submultimi, numarul de dependente triviale intr-o relatie este exponential. Nu vom considera de asemenea dependentele de forma X , fiindca ele nu au aplicare practica.

4. Completitudinea regulilor de inferenta

Definitia 6. Fie RI o multime de reguli de inferenta asupra multimii de dependente F. Multimea RI de reguli este inchisa, daca F|-f, utilizand regulile din RI, implica F|=f. Multimea de reguli de inferenta RI este completa, daca F|=f implica F|-f, utilizand regulile din RI.

Ca multimea de reguli DF1-DF6 este inchisa, adica ele au loc in orice relatie, s-a demonstrat pentru fiecare regula in parte in sectiunea 2. Pentru a arata ca multimea de reguli este completa mai intai introducem notiunea de inchidere a unei multimi de atribute.

Definitia 7. Fie F o multime de dependente asupra R si X R. Inchiderea multimii de atribute X in raport cu multimea de dependente F, notata cu X⁺, se defineste astfel:

X X⁺ (X e o submultime a inchiderii);

Daca Z X⁺ si Z YIF, atunci Y X⁺;

Nici un alt atribut nu face parte din X⁺.

Adica X⁺=X

Exemplul 7. Fie R=ABCDEG si F=. Sa se arate ca (AB)⁺ = ABCDEG. In fig.7 este reprezentat procesul de construire a (AB)⁺.

Teorema 2. Multimea de reguli de inferenta DF1-DF6 este completa.

Demonstratie. Fie F o multime de dependente asupra R. Trebuie sa aratam ca, daca F|=X Y, atunci F|-X Y (sau, ce e echivalent, daca F|-X Y, atunci F|≠X Y).

Fie X Y o dependenta functionala ce nu se deduce din F, adica F|-X Y. Sa aratam ca relatia ce satisface toate dependentele din F nu satisface X Y, adica F|≠X Y.

Definim relatia r(R) in felul urmator (vezi fig.8). Ea consta din doua tupluri t₁ si t₂. Tuplul t₁=aaa; tuplul t₂ se defineste astfel t₂[A] = .

Mai intai, vom arata ca relatia construita satisface toate dependentele din F. Presupunem contrariul. Exista in F o dependenta V W ce nu e valida in r(R). Atunci V X⁺ si W X⁺, altminteri relatia r va satisface dependenta V W. Intrucat WX⁺, exista in W cel putin un atribut A si A X⁺. Conform regulii reflexivitatii V X⁺ implica X⁺ V. Dependentele X⁺ V si V W implica, conform regulii DF5, X⁺ W. Din AIW urmeaza W A. Aplicand asupra X⁺ W si W A regula tranzitivitatii obtinem X⁺ A. Din ultima dependenta, X⁺ A, urmeaza ca AIX⁺, ce contrazice faptului ca A X⁺. Deci relatia construita satisface orice dependenta din F.

Acum sa aratam ca relatia noastra nu satisface dependenta X Y. Presupunem ca relatia r(R) satisface dependenta X Y. Atunci t₁[X]=t₂[X] implica t₁[Y]=t₂[Y]. Aceasta se poate intampla doar cand Y X⁺. Din Y X⁺, aplicand regula DF1, urmeaza X⁺ Y. Dependenta X X⁺ este in F⁺. Aplicand asupra X X⁺ si X⁺ Y regula DF5, obtinem X Y. Dar aceasta contrazice ipoteza ca F|-X Y.

Deci, daca F|=X Y, atunci F|-X Y.

Luand in consideratie ca (in compartimentul 2.) s-a demonstrat ca multimea de reguli este inchisa, adica F|-X Y implica F|=X Y putem spune ca multimea de reguli de inferenta DF1-DF6 este inchisa si completa, adica F|=X Y, daca si numai daca F|-X Y. Prin urmare, putem utiliza "|= " si "|-" deopotriva.

Dat fiind faptul ca regulile DF1-DF6 se deduc din axiomele Armstrong, vom spune ca si axiomele Armstrong sunt inchise si complete.

5. Modele de derivari

Notiunea de consecutivitate de derivare introdusa in sectiunea 3 are o serie de dezavantaje. De regula, pentru o dependenta f pot exista o serie de derivari din multimea de dependente date F. Aceste derivari, fiind in esenta echivalente, difera prin ordinea si tipul regulilor aplicate pentru derivarea dependentelor din consecutivitate. In plus, consecutivitatile de derivare pot contine dependente derivate redundante. Mai jos vom examina modele de derivari ce intr-o masura sau alta sunt lipsite de aceste dezavantaje.

5.1. RAP-consecutivitati de derivare

Axiomele Armstrong sunt o submultime completa de reguli de inferenta a multimii DF1-DF6. Exista, insa, multimi complete de reguli de inferenta ce nu sunt submultimi ale multimii DF1-DF6. Consideram o astfel de multime de reguli de inferenta denumita B-axiome.

Pentru relatia r(R), submultimile W, X, Y si Z ale multimii R si CIR avem:

B1. Regula reflexivitatii. Daca Y X, atunci X Y.

B2. Regula acumularii. Daca X YZ si Z CW, atunci X YZC.

B Regula proiectivitatii. Daca X YZ, atunci X Y.

Teorema Multimea de reguli B1-B3 este o multime inchisa.

Demonstratie. In sectiunea 2 s-a demonstrat ca regulile reflexivitatii si proiectivitatii au loc in orice relatii r cu schema R. Sa examinam regula acumularii. Presupunem contrariul: relatia r satisface dependentele X YZ, Z CW si nu satisface X YZC. Atunci exista doua tupluri t₁ si t₂ pentru care t₁[X]=t₂[X], dar t₁[YZC] t₂[YZC]. Din t₁[YZC] t₂[YZC] urmeaza sau t₁[YZ] t₂[YZ], sau t₁[C] t₂[C]. Daca t₁[YZ] t₂[YZ], atunci dependenta X YZ nu e valida in r. Daca t₁[C] t₂[C] atunci r nu satisface dependenta Z CW. Prin urmare, dependenta X YZC e valida in orice relatie, in care sunt valide dependentele X YZ si Z CW.

Teorema 4. Multimea de reguli B1-B3 este completa.

Demonstratie. Pentru a arata ca regulile B1-B3 sunt complete, e de ajuns sa aratam ca axiomele Armstrong se deduc din B-axiome.

Regula reflexivitatii DF1 coincide cu B1.

Sa aratam ca regula incrementarii, DF2, urmeaza din regulile B1-B Fie X Y. Din regula B1 urmeaza XZ XZ. Aplicand asupra XZ XZ si X Y regula B2 de atatea ori cate atribute sunt in Y, obtinem XZ XZY. Conform regulii proiectivitatii, B3, obtinem XZ Y.

Sa demonstram ca regula tranzitivitatii DF5 urmeaza din B1-B Fie relatia r satisface dependentele functionale X Y si Y Z. Din B1 obtinem X X. Consecutiv, aplicam mai intai regula B2 asupra X X si X Y de atatea ori cate atribute sunt in Y si obtinem X XY. Aplicand asupra X XY si Y Z, regula B2, obtinem X XYZ. O singura aplicare a regulii B3 produce X Y.

Definitia 8. Consecutivitatea de dependente functionale se numeste RAP-consecutivitate de derivare (dupa primele litere ale denumirilor B-axiomelor: Reflexivitate, Acumulare, Proiectivitate) a unei dependente X Y din multimea de dependente F, daca:

prima dependenta in consecutivitate e X X;

ultima dependenta in consecutivitate e X Y (obtinuta, aplicand regula B3);

orice dependenta din consecutivitate (in afara de prima si ultima) sau este o dependenta din F, sau are forma X Z si e obtinuta, aplicand regula B2 asupra dependentelor precedente.

Exemplul 8. Fie F=. Consecutivitatea de mai jos este RAP-consecutivitate de derivare a dependentei AB GH din F.

f₁:=AB AB  (B1),

f₂:=AB E (data),

f₃:=AB ABE   (B2: f₁, f₂),

f₄:=BE I (data),

f₅:=AB ABEI  (B2: f₃, f₄),

f₆:=E G   (data),

f₇:= AB ABEIG (B2:f₅, f₆),

f₈:=GI H (data),

f₉:=AB ABEIGH    (B2: f₇, f₈),

f₁₀:=AB GH    (B3: f₉).

5.2. DDA-grafuri de derivare

DDA-graful (Derivation Directed Acyclic-graph) este o interpretare grafica a RAP-consecutivitatii de derivare.

Definitia 9. Fie F o multime de dependente functionale asupra schemei R. DDA-graf asupra F este un graf orientat fara cicluri ce se defineste recursiv:

R1. O multime de noduri notate cu atribute din R este DDA-graf.

R2. Daca H este DDA-graf si B₁,,B_n sunt noduri in H si dependenta functionala B₁B_n CZ este in F, atunci H¹, obtinut din H prin adaugarea nodului C (daca astfel de nod nu exista) si muchiilor (B₁C) (B_nC) orientate spre C, este DDA-graf.

R DDA-graf este numai graful obtinut prin aplicarea regulilor R1 si R2.

Definitia 10. Nodul B al unui DDA-graf H se numeste initial, daca in el nu intra nici o muchie (Nodurile initiale se adauga in H prin regula R1).

Definitia 11. Fie H un DDA-graf asupra F. Graful H se numeste DDA-graf de derivare a dependentei X Y din F, daca:

X este multimea de noduri initiale in H;

orice atribut din Y este un nod in H.

Definitia 12. Multimea de dependente din F utilizate de regula R2 pentru construirea DDA-grafului H de derivare a unei dependente X Y din F se numeste multime utilizabila, notata cu U(H).

Exemplul 9. In fig.9 sunt prezentate etapele de construire a DDA-grafului de derivare a dependentei AB CG din multimea de dependente functionale F=.

Nodurile initiale sunt A si B. Multimea utilizabila U(H)=. Graful H obtinut este DDA-graful de derivare a dependentei AB CG din F, fiindca multimea de atribute AB formeaza nodurile initiale din H, iar CG sunt noduri in H.

5. Derivatia maximala

Modelele de derivare descrise mai sus poarta mai mult un caracter teoretic. Ele nu sunt lipsite de neajunsul ca pentru o dependenta data exista mai multe consecutivitati de derivare. Aici vom considera un model, numit derivare maximala, liber de acest dezavantaj. Acest model este foarte aproape de notiunea de inchidere a unei multimi de atribute in raport cu o multime de dependente functionale. El va fi utilizat in demonstrarea diverselor rezultate privind acoperirile de dependente functionale.

Definitia 1 Fie F o multime de dependente functionale asupra schemei R si fie X R. Derivatia maximala a multimii de atribute X in raport cu multimea de dependente functionale F este o consecutivitate de multimi de atribute <X₀,X₁,,X_n>, unde

X₀=X;

X_i=X_i-1 Z, 1 i n, unde Z = _jW_j pentru orice dependenta V_j W_jIF ce satisface V_j X_i-1 si W_j X_i-1;

in F nu exista nici o dependenta V_j W_j pentru care V_j X_n si W X_n.

Inainte de a arata ca derivatia maximala este un instrument puternic de modelare a derivarii dependentelor functionale, consideram doua proprietati ale ei.

Lema 1. Daca X Y si consecutivitatile <X₀, X₁,, X_n>, <Y₀, Y₁,, Y_m> sunt derivatii maximale ale multimilor X si Y, corespunzator, in raport cu F, atunci pentru orice X_i exista o multime Y_j incat X_i Y_j si j i.

Demonstratie. Vom arata aceasta, aplicand inductia matematica asupra i. Cand i=0 avem X₀ Y₀, fiindca X Y. Fie ca presupunerea noastra e justa pentru i=k: X_k Y_p si p k. Sa aratam ca ceea ce trebuie de demonstrat are loc si pentru i=k+1. Intr-adevar, la pasul k+1, X_k+1=X_k Z, unde Z= _jW_j pentru toate dependentele V_j W_j din F determinantii si determinatii carora satisfac V_j X_k si W_j X_k corespunzator. Conform ipotezei inductiei X_k Y_p. Prin urmare, toti determinantii dependentelor V_j W_j ce se contin in X_k se vor contine si in Y_p . Dat fiind faptul ca multimea Y_p e mai "larga" ea poate contine toti determinatii W_j si atunci X_k+1 Y_p. Daca nu, atunci in derivatia multimii Y in raport cu F se executa urmatorul p+1 pas, in rezultatul caruia vom obtine Y_p+1 care va contine X_k+1.

Lema 2. Daca <X₀, X₁,, X_n> este derivatia maximala a multimii X in raport cu multimea de dependente functionale F, atunci X X_iIF⁺ , 0 i n.

Demonstratie. Vom face demonstrarea, utilizand inductia asupra numarului de aplicari a regulii (2) in construirea derivatiei maximale.

Fie ca in construirea derivatiei maximale nu s-a aplicat regula (2). Atunci ea are un singur element X₀, unde X₀=X si conform regulii reflexivitatii, DF1, X X₀IF⁺.

Presupunem ca la aplicarea i-1 a regulii (2) are loc X X_i-1IF⁺. Sa se arate veridicitatea afirmatiei pentru pasul i. Fara a constrange generalitatea, presupunem ca la acest pas avem o singura dependenta V W ce satisface V X_i-1, W X_i-1. Conform regulii reflexivitatii X_i-1 VIF⁺. Dar X_i-1 VIF⁺ si V WIF⁺ (regula tranzitivitatii) implica X_i-1 WIF⁺. Adaugam la determinantul si determinatul ultimei dependente multimea X_i-1. Obtinem (conform regulii incrementarii) X_i-1 X_i-1WIF⁺ . Din X X_i-1IF⁺ (ipoteza inductiei) si X_i-1 X_iIF⁺ urmeaza X X_iIF⁺.

In baza acestor doua proprietati vom demonstra

Teorema 5. Fie <X₀, X₁,, X_n> derivatia maximala a multimii X in raport cu multimea de dependente functionale F. Atunci X YIF⁺ daca si numai daca Y X_n.

Demonstratie. Necesitatea. Sa aratam ca, daca X YIF⁺, atunci exista o multime X_i in derivatia maximala <X₀,X₁,,X_n> incat Y X_i si, prin urmare, Y X_n. Vom utiliza inductia asupra (lungimii derivarii) numarului de dependente folosite in derivarea dependentei X Y in raport cu F, unde dependenta de derivare sau este in F, sau se deduce din regula reflexivitatii sau din regula incrementarii, aplicate asupra unei dependente precedente, sau cu ajutorul regulii tranzitivitatii, aplicate asupra a doua dependente precedente. Ultima dependenta in derivare, bineinteles, e X Y.

Fie ca derivarea dependentei X Y are lungimea 1, adica consta din insusi X Y. Sunt doua cazuri. Sau X Y se deduce din axioma reflexivitatii, sau X YIF. In primul caz, Y X si, prin urmare, Y X₀. In al doilea caz, dependenta X Y va participa la formarea elementului al doilea a derivatiei maximale a multimii X in raport cu F. Deci Y X₁.

Presupunem acum ca afirmatia noastra e justa pentru o derivare cu lungimea mai mica decat k si sa demonstram veridicitatea afirmatiei noastre pentru derivarea cu lungimea k. Consideram consecutiv regulile de inferenta ce pot fi aplicate la acest pas.

Daca pentru deducerea dependentei X Y se aplica regula reflexivitatii sau X YIF, atunci Y se comporta ca si pentru derivari cu lungimea unu, adica Y se pomeneste corespunzator in X₀ si X₁.

Daca X Y urmeaza din regula incrementarii asupra unei dependente precedente V W, atunci exista S si T, unde T S si VS=X, WT=Y. Intrucat V W are o derivare cu o lungime mai mica decat k, atunci conform ipotezei inductiei exista in derivatia maximala o multime V_j, unde W V_j. Fiindca V X, atunci conform lemei 1 exista in derivatia maximala pentru X in raport cu F o multime X_i, unde W X_i. Din T S X urmeaza T X₀ si T X_i.

Consideram ultimul caz, cand dependenta X Y e obtinuta, aplicand regula tranzitivitatii asupra a doua dependente precedente X Z si Z Y, derivatiile carora au lungimi mai mici decat k.

Urmand ipoteza inductiei, pentru X Z si Z Y avem corespunzator Z X_j si Y Z_p. Insa Z_p este element al derivatiei maximale a multimii Z in raport cu F. Fiindca Z X_j, conform lemei 1 Z_p X_j+m, unde X_j+m este elementul m+1 al derivatiei maximale a multimii X_j in raport cu F pe care o vom nota <X_j+0, X_j+1,, X_j+m,, X_j+p>. Este evident ca derivatia maximala a multimii X_j nu e altceva decat o subconsecutivitate ce consta din ultimele n-j+1 elemente ale derivatiei maximale a multimii X in raport cu F. Prin urmare, Y X_i , unde i=j+m.

Suficienta. Fie <X₀, X₁,, X_n> e derivatia maximala a multimii X in raport cu F. Conform lemei 2 X X_nIF⁺. Intrucat Y X_n, atunci aplicand regula proiectivitatii asupra dependentei X X_n obtinem X YIF⁺. Teorema e demonstrata.

Definitia 14. Fie X YIF⁺ si <X₀, X₁,, X_n> derivatia maximala a multimii X in raport cu F. Fie X_i este primul element din consecutivitate ce contine multimea Y. Subconsecutivitatea <X₀, X₁,, X_i> se numeste derivatia dependentei functionale X Y in raport cu F.

Din teorema 5 si definitia 14 urmeaza

Consecinta 1. X YIF⁺ atunci si numai atunci cand exista derivatia dependentei X Y in raport cu F.

Consecinta 2. Daca X YIF⁺ si dependenta V WIF e utilizata in construirea derivatiei dependentei X Y in raport cu F, atunci X VIF⁺.

Justetea acestei afirmatii decurge imediat din lema 2 si regula proiectivitatii.

Trebuie mentionat ca derivatia maximala este un model de derivare liber de dezavantajele mentionate la inceputul acestei sectiuni. Existenta a unei singure derivatii pentru o dependenta data va fi utila in expunerea de mai departe a materiei.

5.4. Algoritmi

Pentru a determina daca F|=X Y, e suficient de verificat daca X YIF⁺. Insa, F⁺ este excesiv de mare in raport cu F. E dezirabila o metoda de verificare, daca X Y apartine F⁺, fara a deduce toate dependentele functionale din F. Un astfel de algoritm e prezentat mai jos. Nucleul algoritmului consta din procedura de construire a inchiderii multimii de atribute X in raport cu F. Dupa ce se gaseste X⁺, se verifica daca Y X⁺.

Este evident ca ultimul element, X_n, din derivatia maximala nu este altceva decat X⁺. Iar teorema 5 ne sugereaza ca X Y urmeaza logic din F, daca Y X⁺. Deci, derivatia maximala serveste drept model teoretic pentru urmatorul algoritm de determinare a lui X⁺.

Algoritmul CLOSURE cauta in F o dependenta functionala pentru care determinantul reprezinta o submultime a lui X_i, iar determinatul nu este inclus in X_i. Daca se gaseste o astfel de dependenta functionala, atunci se adauga la X_i atributele care constituie determinatul dependentei. Daca nu se gaseste, atunci inchiderea cautata, X⁺ este reprezentata de multimea de atribute X_i.

Algoritmul CLOSURE (F, X, X⁺)

Intrare: F- o multime de dependente functionale asupra schemei R; X - o multime de atribute, X R.

Iesire: X⁺ - inchiderea multimii X in raport cu F

begin

i:=0; X_i:=X;

repeat

i:=i+1;

X_i:=X_i-1;

For all V W in F

if V X_i then X_i:=X_i W;

until X_i=X_i-1;

return (X⁺:=X_i);

end

Exemplul 10. Fie F=, X=B. Sa se calculeze X⁺.

Initial X₀=B.

In ciclul repeat:

X₁=B.

In ciclul for:

X₁= BCD (aplicand B CD),

X₁= ABCD (aplicand B A).

X₂=ABCD

In ciclul for:

X₂=ABCDE (aplicand AD E)

X₃=ABCDE

Dupa ciclul for:X₃=X₂.

Rezultat: X⁺:=ABCDE.

Deci inchiderea lui B in raport cu F este (B)⁺=ABCDE.

Algoritmul CLOSURE realmente construieste derivatia maximala a multimii de atribute X in raport cu F. Apeland la CLOSURE e usor de construit algoritmul de verificare a apartenentei unei dependente functionale la F⁺. Aceasta verificare e realizata in algoritmul MEMBERSHIP.

Algoritmul MEMBERSHIP(F, X Y)

Intrare: F- o multime de dependente functionale;

X Y - o dependenta functionala.

Iesire: adevar, daca F|=X Y, fals - in caz contrar.

begin

CLOSURE (f, x, x⁺);

if Y X⁺ then return (adevar) else return (fals);

end

Corectitudinea algoritmilor CLOSURE si MEMBERSHIP rezulta imediat din teorema 5.

6. Acoperiri

In aceasta sectiune se considera diverse moduri de reprezentare a multimilor de dependente, cum ar fi multimile nonredundante, reduse, canonice, minimale si optimale.

6.1. Multimi echivalente de dependente functionale

Definitia 15. Doua multimi de dependente functionale F si G se numesc echivalente, notat cu FsG, daca F⁺=G⁺. Vom mai spune in acest caz ca F acopera G (sau G acopera F).

Daca FsG, adica F⁺=G⁺, atunci orice dependenta X Y ce urmeaza logic din F urmeaza si din G. Deci pentru a verifica daca F si G sunt echivalente se ia orice dependenta X Y din F si se verifica daca G|=X Y. Daca o oarecare dependenta X Y nu apartine lui G⁺, atunci F⁺ G⁺. Apoi analogic se verifica daca orice dependenta V W din G se deduce din F. Daca toate dependentele se deduc, multimile F si G sunt echivalente.

Exemplul 11. Multimile F= si G= sunt echivalente, insa F nu este echivalenta multimii G¹= (a se verifica in calitate de exercitiu).

6.2. Acoperiri nonredundante

Definitia 16. Multimea de dependente functionale F este nonredundanta, daca nu exista o submultime proprie F¹a multimii F si F¹sF. Daca o astfel de submultime exista, atunci F se numeste redundanta. Multimea F este acoperire nonredundanta a multimii G, daca F este acoperire pentru G si F este nonredundanta.

Exemplul 12. Fie G=. Multimea F= este acoperire a multimii G, dar nu e acoperire nonredundanta, fiindca F¹= e acoperire pentru G, insa F¹ F.

Sa consideram o alta interpretare a notiunii de multime nonredundanta.

Definitia 17. Multimea F de dependente functionale se numeste nonredundanta, daca in ea nu exista nici o dependenta X Y incat (F )|=X Y. In caz contrar, F se numeste redundanta.

Aceasta definitie este pusa in baza urmatorului algoritm de construire a acoperirii nonredundante. E de mentionat ca rezultatul obtinut in urma aplicarii algoritmului depinde de ordinea considerarii dependentelor functionale.

Algoritmul NONREDUN (F,G)

Intrare: F - o multime de dependente functionale.

Iesire: G - o acoperire nonredundanta a multimii F.

begin

G:=F;

for all X Y in G

if MEMBERSHIP (G , X Y) then

G:=G ;

return (G);

end

Exemplul 1 Fie F = . In rezultatul aplicarii algoritmului NONREDUN obtinem acoperirea nonredundanta G = . Daca multimea F e prezentata in alta ordine se obtine rezultatul G = .

6. Acoperiri reduse

Daca F e o multime nonredundanta, atunci nu poate fi eliminata din F nici o dependenta functionala fara a afecta echivalenta multimii obtinute cu cea anterioara. In schimb poate fi micsorata dimensiunea multimii F, eliminand unele atribute din dependentele functionale.

Definitia 18. Fie F o multime de dependente functionale asupra schemei R si X YIF. Atributul A este redundant in dependenta X Y in raport cu F, daca

AIX, V=X A si F sF

sau

AIY, W=Y A si F sF.

Cu alte cuvinte, atributul A este redundant in dependenta X Y, daca el poate fi eliminat din determinant sau determinat, fara a fi schimbata inchiderea multimii F. Procesul de eliminare a atributelor redundante se numeste, corespunzator, reducere in stanga si reducere in dreapta a dependentelor.

Exemplul 14. Fie F = . Atributul C este redundant in AC B, fiindca (AC)⁺ = A⁺ = ACBD. Adica A B este in F⁺. Deci dependenta AC B poate fi inlocuita cu A B in multimea de dependente functionale F. Atributul B este redundant in partea dreapta a dependentei A BD.

Definitia 19. Fie F o multime de dependente functionale asupra schemei R. Multimea F se numeste redusa in stanga (dreapta), daca orice dependenta din F nu are atribute redundante in partea stanga (dreapta). Multimea de dependente redusa in stanga si in dreapta se numeste redusa.

Exemplu 15. Multimea F = nu este redusa nici in stanga, nici in dreapta. Multimea F₁= e redusa in stanga si nu e redusa in dreapta, dar F₂= e redusa in dreapta si nu in stanga. Multimea de dependente functionale F₃= e redusa in stanga si in dreapta, deci e redusa.

Mai jos se aduc algoritmii de reducere a unei multimi nonredundante.

Algoritmul LEFTRED (F, G)

Intrare: F - o multime nonredundanta de dependente functionale.

Iesire: G - o multime de dependente functionale redusa in stanga.

begin

G:=F;

for all X Y in G

for all A in X

if MEMBERSHIP (G, (X A) Y) then

G:=G

return (G);

end

Algoritmul RIGHTRED (F,G)

Intrare: F - o multime nonredundanta de dependente functionale.

Iesire: G - o multime de dependente functionale redusa in dreapta

begin

G:=F;

for all X Y in G

for all A in Y

if MEMBESHIP (G , X A) then G:= {G

return (G);

end

Algoritmul REDUCE (F, G)

Intrare: F - o multime de dependente functionale nonredundanta.

Iesire: G - o multime redusa de dependente de dependente functionale.

begin

LEFTRED (F, F¹);

RIGHTRED (F¹, G);

eliminarea din G a dependentelor X

return (G);

end

In algoritmul LEFTRED de mai sus, este inclusa conditia de verificare G|= (X A) Y. Este evident ca, daca (XA) Y se deduce din G, atunci X Y poate fi substituita cu (XA) Y, fiindca (X A) Y|=X Y.

E evident ca, daca o dependenta este redundanta, atunci toate atributele ei sunt redundante. Pentru a evita aparitia dependentelor de forma se presupune ca multimea destinata reducerii este nonredundanta.

S-ar parea ca acoperirile reduse pot fi calculate, gasind si eliminand in mod aleator atributele redundante. Insa, examinand partile stangi si drepte ale dependentelor in ordine diferita, obtinem rezultate diferite. In partile drepte odata examinate pot aparea atribute redundante dupa examinarea partilor stangi. Deci eliminarea atributelor redundante trebuie sa inceapa cu partea stanga. Dar si in cazul acesta pot aparea dependente de forma X . Ele se elimina la urma din multimea rezultat.

6.4. Acoperiri canonice

Definitia 20. Multimea de dependente functionale F este canonica, daca F este nonredundanta, redusa in stanga si orice dependenta din F are forma X A.

Intrucat multimea canonica este nonredundanta si redusa in stanga, iar determinatul oricarei dependente consta dintr-un singur atribut, ea este redusa si in dreapta, adica este redusa.

Exemplul 16. Multimea F= este o acoperire canonica a multimii G=.

Teorema 6. Fie F o acoperire redusa. Se formeaza multimea G, dezagregand orice dependenta de forma X A₁A_n in X A₁,, X A_n. Atunci G este canonica. Fie G o acoperire canonica. Formam F, agregand dependentele cu determinanti egali. Multimea F este acoperire redusa.

Demonstratie. Fie multimea G este formata din F prin dezagregarea dependentelor. Presupunem ca G nu e canonica. Daca dependenta X A_i e redundanta, atunci atributul A_i e redundant in X A₁A_n. Daca X A_i contine un atribut redundant in X, fie B, atunci G|=(XB) A_i. Dar G|=(XB) X, fiindca X A_i e nonredundanta. De unde conchidem ca F|=(XB) X si, prin urmare, B e redundant in partea stanga a dependentei X A₁A_n din F.

Sa demonstram a doua parte a teoremei. Presupunem contrariul: F nu e redusa. Daca F nu e redusa in dreapta, atunci G nu e nonredundanta. Dar daca F nu e redusa in stanga, atunci si G nu e redusa din stanga, ce contravine presupunerii ca G e canonica.

6.5. Clase de echivalenta

Definitia 21. Fie F o multime de dependente functionale asupra schemei R si X, Y R. Multimile de atribute X si Y sunt echivalente, notam cu X Y, in raport cu F, daca F|=X Y si F|=Y X.

Aceasta definitie ne sugereaza ca multimea F poate fi partitionata in clase de echivalenta. Adica asupra F se poate defini o relatie de echivalenta: dependentele X Y si V W din F apartin unei clase de echivalenta, daca si numai daca X V in raport cu F.

Notam cu E_F(X) multimea de dependente cu determinantii echivalenti lui X in raport cu F, adica E_F(X)=. E_F(X) se numeste clasa de echivalenta a dependentelor cu determinantii echivalenti multimii de atribute X.

Notam cu Ē_F=, adica Ē_F este multimea tuturor claselor de echivalenta nevide, in care este partitionata multimea de dependente functionale F.

Exemplul 17. Fie F=. Atunci (AB)⁺ = (AC)⁺ = (AD)⁺ = ABCD si C⁺=BC. Deci AB AC, AD AC, AB AD, adica Ē_F=, E_F(C)=}.

Urmatoarea lema arata corelatia dintre structurile a doua acoperiri nonredundante.

Lema Fie F si G doua multimi de dependente functionale nonredundante echivalente asupra schemei R. Fie X Y o dependenta in F. Atunci in G exista o dependenta V W, unde X V in raport cu F (si in raport cu G).

Demonstratie. Din faptul ca FsG urmeaza G|=X Y. Atunci exista derivatia H a dependentei functionale X Y, in raport cu G. Consideram toate dependentele utilizate in construirea derivatiei H, adica multimea U(H). In acelasi timp, orice dependenta V W din U(H) se deduce din F. Fie H¹ este derivatia dependentei V W in F. Trebuie sa existe in U(H) o dependenta V W pentru deducerea careia se utilizeaza dependenta X Y, adica X YIU(H¹). In caz contrar pentru dependenta X Y va exista o derivatie H¹¹ asupra F si, prin urmare, X Y va fi redundanta in F ce contrazice ipotezei ca F este o multime nonredundanta.

Intrucat X YIU(H¹), conform consecintei 2, F|=V X. Dar V WIU(H) si atunci G|=X V. Prin urmare, X V.

Lema de mai sus poate fi parafrazata in felul urmator. In doua acoperiri nonredundante F si G pentru orice dependenta din F exista o dependenta in G ce are partea stanga echivalenta celei din F. Prin urmare, multimile nonredundante echivalente au acelasi numar de clase de echivalenta.

Exemplul 18. Multimile F= si G= sunt nonredundante si echivalente. Sa observam ca A A, B B, AD BD si A B. Deci Ē_F=, E_F(AD) = } si Ē_G =, E_G(BD) = }.

6.6. Acoperiri minimale

Definitia 22. Multimea de dependente functionale F este minimala, daca nu exista o multime echivalenta ei cu mai putine dependente functionale.

Este evident ca orice multime minimala de dependente functionale este si nonredundanta. Afirmatia inversa nu este corecta.

Exemplul 19. Multimea F= este nonredundanta, dar nu este minimala, fiindca G= este acoperire pentru F si are o singura dependenta.

Fie e_F(X) este multimea partilor stangi ale dependentelor ce formeaza clasa de echivalenta E_F(X). Atunci are loc

Lema 4. Fie F o multime nonredundanta de dependente functionale, X determinantul unei dependente din F si Y o multime de atribute echivalenta lui X (adica Y X in raport cu F). Atunci exista in e_F(X) o multime Z, incat (F E_F(X))|=Y Z.

Demonstratie. Daca YIe_F(X), atunci lema e demonstrata, fiindca Y Y urmeaza din orice multime de dependente functionale. Fie Y e_F(X). Intrucat Y Z pentru orice Z din e_F(X), atunci exista derivatia H=<Y₀, Y₁, , Y_m>, unde Y₀=Y si Z Y_m. Daca in construirea lui H nu s-a utilizat nici o dependenta din E_F(X), atunci lema e demonstrata. Presupunem ca pentru construirea derivatiei H s-a utilizat dependenta V WIE_F(X) si fie V W e prima dependenta din E_F(X) utilizata in H. Atunci in H exista un Y_i incat V Y_i dar W Y_i. Dar Y Y_iI(F E_F(X))⁺ si, conform reflexivitatii, Y_i V are loc in orice multime de dependente. Aplicand regula tranzitivitatii asupra ultimelor dependente, obtinem ca (F E_F(X))|=Y V, adica Z=V.

Lema 5. Fie F si G doua multimi nonredundante echivalente de dependente functionale. Fie X e determinantul unei dependente din F si Y o multime de atribute, unde Y X. Daca Y ZI(F E_F(X))⁺, atunci Y ZI(G E_G(X))⁺.

Demonstratie. Intrucat Y ZI(F E_F(X))⁺, atunci exista derivatia H=<Y₀, Y₁, , Y_m>, pentru Y Z in raport cu F E_F(X). Fie V W o dependenta utilizata in construirea lui H. Din FsG urmeaza V WIG⁺ .

Sa aratam ca in derivatia dependentei V W in raport cu G nu sunt utilizate dependente din E_G(X). Presupunem contrariul: pentru derivarea V W este utilizata dependenta T S din E_F(X). Atunci, conform lemei 3, Y T, iar din consecinta 2 V TIG⁺. Din V TIG⁺ si T YIG⁺ urmeaza V YIG⁺ . Insa Y VIG⁺ si atunci obtinem ca Y V in raport cu F. Contrazicere. Deci, orice dependenta utilizata in derivatia lui Y Z in raport cu FE_F(X) se deduce din GE_G(H).

Deci, derivatia dependentei Y Z va utiliza numai dependente din GE_G(H).

Teorema 7. O multime nonredundanta F este minimala, daca si numai daca nici o clasa de echivalenta E_F(X) nu contine doua dependente diferite X Y si V W, unde X VI(F E_F(X))⁺.

Demonstratie. Necesitatea. Fie F este o multime minimala, si presupunem contrariul: in clasa de echivalenta E_F(X) sunt doua dependente diferite X Y si V W incat X VI(F E_F(X))⁺. Construim o multime de dependente G, care se deosebeste de F, prin aceea ca in clasa de echivalenta E_G(X) dependentele X Y si V W sunt substituite de V YW. Vom arata ca FsG. Pentru aceasta e suficient sa verificam daca X YIG⁺. Conform lemei 5 X VI(GE_G(X))⁺. Din X VI(G E_G(X))⁺ si V YWIG⁺ urmeaza ca X YWIG⁺. Deci FsG, insa G contine cu o dependenta mai putin, ce contrazice ipotezei ca F e o multime minimala de dependente functionale.

Suficienta. Vom arata ca, daca orice clasa de echivalenta a unei multimi F nu contine doua dependente diferite, incat partile stangi sa se determine functional in afara propriei clase de echivalenta, atunci F este minimala. Sa demonstram ca nu exista o multime nonredundanta G si GsF, incat careva clasa de echivalenta din G sa contina mai putine dependente decat clasa corespunzatoare din F.

Presupunem contrariul: exista o multime nonredundanta G si GsF, iar clasa de echivalenta E_G(X) contine mai putine dependente decat clasa E_F(X).

Sa evidentiem dependentele acestor doua clase de echivalenta, unde m<n (vezi fig.10).

In corespundere cu lema 4 pentru orice X_jIe_F(X) exista in e_G(X) un determinant V_k si X_j V_kI(G E_G(X))⁺. Apeland la lema 5. obtinem X_j V_kI(F E_F(X))⁺. Intrucat n>m, atunci se vor gasi in e_F(X) cel putin doua multimi X_j si X_l, unde j l, ce satisfac X_j V_kI(F E_F(X))⁺ si X_l V_kI(F E_F(X))⁺. La randul sau, in e_F(X) exista un determinant X_h si V_k X_hI(FE_F(X))⁺. Consideram doua cazuri posibile: h j sau h l. Daca h j, atunci X_j V_kI(FE_F(X))⁺ si V_k X_hI(FE_F(X))⁺ implica X_j X_hI(F E_F(X))⁺. Daca, insa, h l, atunci obtinem V_l X_hI(F E_F(X))⁺.

In ambele cazuri, clasa de echivalenta E_F(X) va contine doua dependente diferite, partile stangi ale carora se determina functional in afara clasei de echivalenta examinata. Contrazicere.

Consecinta Daca F si G sunt multimi minimale echivalente, atunci clasele de echivalenta corespunzatoare contin acelasi numar de dependente functionale.

Consecinta 4. Daca F si G sunt doua multimi minimale echivalente, atunci pentru orice determinant X_jIe_F(X) exista un singur determinant V_k in e_G(X) pentru care au loc X_j V_kI(FE_F(X))⁺ si V_k X_jI(FE_F(X))⁺.

Remarca. Existenta corespondentei biunivoce, indicate in consecinta 4, permite substituirea unor parti stangi ale multimii minimale cu parti stangi ale altei acoperiri minimale, neafectand echivalenta multimilor. Mai mult ca atat, multimea noua de dependente functionale va continua sa fie minimala.

In teorema de mai sus se afirma ca, daca o multime nonredunanta G are doua dependente X Y si V W pentru care X V si (G E_G(X))|=X V, atunci G nu este minimala. Aceste doua dependente pot fi substituite cu alta dependenta V YW. In rezultat obtinem o multime echivalenta de dependente functionale ce contine cu o dependenta mai putin.

Acest proces este pus la baza urmatorului algoritm de minimizare a unei multimi de dependente functionale.

Algoritmul MINIMIZE (f,g)

Intrare: F - o multime de dependente functionale.

Iesire: G - o multime minimala de dependente functionale.

begin

NONREDUN (F, G);

get Ē_G;

for all E_G(X) in Ē_G

for all X Y in E_G(X)

for all V W X Y in E_G(X)

if MEMBERSHIP (G E_G(X), x v) then G:= G

return (G);

end

Exemplul 20. Fie F=. Sa construim acoperirea minimala a multimii F.

Nu e greu de observat ca, daca examinam dependentele functionale din F de la stanga la dreapta, dependenta functionala AB D e redundanta in F. Intr-adevar, (AB)⁺ in raport cu F este ABCD. Deci (F)|=AB D. Am obtinut multimea nonredundanta G=.

Sa partitionam G in clase de echivalenta. Pentru aceasta construim inchiderile determinantilor tuturor dependentelor din G. Dependentele ce au inchideri ale determinantilor egale fac parte din aceeasi clasa de echivalenta. Asadar,

(AB)⁺=ABCD,

(AC)⁺=ABCD,

(AD)⁺=ABCD,

C⁺=BC.

Deci, multimea G contine urmatoarele doua clase de echivalenta G=, E_G(C)=}.

Intrucat clasa E_G(C) contine o singura dependenta, se examineaza numai clasa de echivalenta E_G(AB). Nu e greu de verificat ca in E_G(AB) sunt doua dependente AC D, AB C si (G E_G(AB))|=AC AB. Atunci in clasa de echivalenta E_G(AB) aceste doua dependente se substituie cu AB CD.

Am obtinut multimea de dependente G=, E_G(C)=}. In clasa de echivalenta E_G(AB) nu se mai gasesc dependente determinatii carora se determina functional in afara clasei E_G(AB). Prin urmare, multimea G= este o acoperire minimala a multimii F.

6.7. Acoperiri optimale

Multimea de dependente functionale F poate fi estimata dupa numarul de atribute (inclusiv repetate) antrenate de dependentele functionale din F. De pilda, multimea F= are aritatea cinci.

Definitia 2 Multimea de dependente functionale F se numeste optimala, daca nu exista o multime echivalenta ei cu o aritate mai mica.

Exemplul 21. Multimea F= nu este acoperire optimala, fiindca multimea G= are aritatea mai mica decat F si GsF. Multimea G este optimala.

Trebuie mentionat ca problema construirii unei acoperiri optimale apartine clasei de probleme NP-complete, pentru care inca nu au fost gasiti algoritmi polinomiali.

Teorema 8. Multimea optimala este minimala si redusa.

Demonstrarea acestei afirmatii se lasa in calitate de exercitiu.

7. Exercitii

Sa se aduca un exemplu de doua atribute ce se gasesc intr-o dependenta functionala si un exemplu de doua atribute ce nu sunt functional dependente.

Sa se gaseasca dependentele functionale valide in relatia r din fig.11.

Fie r e definita pe multimea ABC. Sa se aduca o extensie a relatiei r ce ar satisface dependenta functionala A B si nu ar satisface dependenta C A.

Sa se arate ca |-X Y.

Fie relatia r(R) si V, W, X, Y, Z R. Sa se demonstreze sau sa se combata urmatoarele reguli de inferenta.

(a)    |- XZ YW;

(b)    |- Z Y;

(c)    |- X YZ;

(d)    |-ZV XY;

(e)    |-X Z, unde W Y.

Sa se arate ca regulile DF1, DF2 si DF6 sunt independente, adica nici una din ele nu se deduce din celelalte.

Sa se arate ca pentru orice multime de dependente functionale F are loc egalitatea F⁺s(F⁺)⁺.

Fie F o multime de dependente functionale asupra schemei R. Care este F⁺, daca F=

Fie multimea F= definita asupra atributelor ABC. Sa se gaseasca F⁺.

Sa se demonstreze ca sistemul de reguli DF1, DF3, DF4 si DF5 este complet. Sunt aceste reguli independente?

Fie F=.

(a)    Sa se construiasca consecutivitatea de derivare a dependentei AB E din F.

(b)    Sa se construiasca consecutivitatea de derivare a dependentei AB G din F, utilizand axiomele Armstrong.

(c)    Sa se construiasca RAP-consecutivitatea de derivare a dependentei AB G din F.

(d)    Sa se construiasca DDA-graful de derivare a dependentei AB G din F.

Sa se arate ca multimile si G= sunt echivalente.

Sa se gaseasca multimea claselor de echivalenta Ē_G, daca G=.

Sa se construiasca o acoperire nonredundanta a multimii de dependente functionale F=.

Sa se construiasca o multime de dependente functionale in care o dependenta functionala X Y are toate atributele redundante.

Sa se construiasca doua multimi de dependente functionale F si G, unde F e o acoperire nonredundanta a multimii G, dar contine un numar mai mare de dependente decat G.

Fie F multimea tuturor dependentelor posibile asupra schemei R=A₁A_n, in afara de X. Sa se gaseasca o acoperire nonredundanta a multimii F.

Sa se gaseasca doua multimi nonredundante echivalente cu un numar diferit de dependente.

Fie F = si G = .

(a)    Sa se arate ca multimile F si G sunt echivalente.

(b)    Sa se gaseasca o acoperire redusa a multimii G.

Fie G=. Sa se gaseasca o acoperire canonica a multimii de dependente G.

Sa se gaseasca acoperire minimala a multimii G=.

Sa se construiasca o acoperire optimala a multimii G=.