RESTRIC II REDUNDANTE IN BAZE DE DATE

În acest capitol vor fi examinate metode care dau reprezentari mai scurte pentru o multime de F-dependente. De exemplu, orice F-dependenta implicata de F= este implicata de G= deoarece orice F-dependenta din F poate fi derivata din G. Restrictiile date de F-dependentele din sistemele de baze de date asigura consistenta si corectitudinea datelor. Mai putine F-dependente înseamna un consum de memorie mai mic si mai putine teste de facut, când se actualizeaza baza de date. ‌De exemplu, o multime redusa de F-dependente determina o executie mai rapida a algoritmilor satisfie, termen etc.

. Multimi de F-dependente echivalente

Definitia 5.1. Doua multimi de F-dependente F si G sunt echivalente daca F⁺=G si se noteaza cu F G Daca F G atunci F este o acoperire a lui G.

În definitia acoperirii nu se aminteste nimic de dimensiunile 747e46h multimilor F si G. Vom considera numai acoperirile lui F care sa nu depasasca pe cele ale lui G în ceea ce priveste numarul de F-dependente.

Lema 5.1. Fie F si G doua multimi de F-dependente pe R, atunci F G daca si numai daca F ‌‌‌‌‌ ‌ G si G ‌‌‌‌‌ F.

Demonstratie: Necesitatea. Fie X Y G atunci X Y G⁺, deci X Y F⁺ deci X Y este implicata de F, (F ‌‌‌‌‌ X Y ) deci F ‌‌‌‌‌ G Deoarece definitia echivalentei este simetrica rezulta ca si G ‌‌‌‌‌ F. Suficienta rezulta din teorema de completitudine.

Exemplul 5.1. Multimile F= si G= sunt echivalente. Multimea F nu este echivalenta cu multimea G întrucât G BCD E.

Lema 5.1. da un procedeu simplu de verificare a echivalentei a doua multimi de F-dependente. Functia derivat verifica daca F ‌‌‌‌‌ G.

0 FUNCTION derivat(F, G)

1 v true

2 FOR fiecare X Y G

2.1 v v Termen(F,X Y)

3 derivat v

4 RETURN

Functia Equiv verifica echivalenta a doua multimi de F-dependente si returneaza true daca cele doua multimi sunt echivalente si false în caz contrar.

0 PROCEDURE equiv(F,G;v)

1 v derivat(F,G) AND derivat(G,F)

3 RETURN

5.2. Restrictii redundante

În acest paragraf sunt considerate restrictiile date numai de F-dependente.

Definitia 5.2. O multime de F-dependente F este neredundanta daca nu exista nici o submultime proprie F a lui F astfel încât F F. Daca exista o submultime proprie F a lui F astfel încât F F atunci F se numeste redundanta.

Exemplul 5.2. Fie F= . Multimea F G si F este redundanta. Multimea F este acoperire neredundanta a lui G.

Definitia 5.3. Multimea de F-dependente este neredundanta daca nu exista X Y F astfel încât F- = F. Dependenta functionala Y Y din F este redundanta daca F- ‌‌‌‌‌ X Y.

Aceasta definitie sta la baza procedurii de caracterizare a redundantei pentru o multime data de F-dependente.

0 PROCEDURE redundant(F;v)

1 v false

2 FOR fiecare X Y F

2.1 IF termen(F-X Y,X Y)

Then

.1 v true

2.2 continue

RETURN

Pentru orice multime data de F-dependente G exista o multime F a lui G neredundanta atunci G F. Daca G este redundanta atunci exista X Y G care este redundanta în G. Fie G =G se observa ca (G )⁺=G . Daca G este redundanta atunci în G exista W V redundanta. Fie G =G W V, (G )⁺=(G )⁺=G . Deoarece G este finita, procesul de eliminare a dependentelor functionale se termina si ca rezultat se obtine o multine neredundanta de dependente functionale F. Acest procedeu sta la baza algoritmului nonrendun.

0 START[nonrendun]

1 Input

2 F G

3 FOR fiecare X Y G

3.1 IF termen(F- ,X Y)

Then

3.1.1 F F

3.2 continue

4 Output

5 Stop

Exemplul 5.3. Fie G= . Aplicarea algoritmului nonrendun determina multimea F= . Daca G= . Exemplul ne arata ca o multime F poate avea mai multe acoperiri neredundante.

5.3. Atribute eliminabile

Daca F este omultime de F-dependente neredundanta atunci ea nu mai contine nici o F-dependenta redundanta si ea nu poate fi facuta mai mica. Eliminarea oricarei F-dependente din F duce la obtinerea unei multimi neechivalente cu F.

Totusi, se poate arata ca, dimensiunea lui F se poate reduce si prin eliminarea unor atribute din anumite F-dependente din F.

Definitia 5.4. Fie F o multime de F-dependente pe schema R si X Y F. Atributul A din R este eliminabil din X Y în raport cu F daca :

i)            X=AZ, X Z si F- F sau

ii)          Y=AW, Y W si F- F.

Cu alte cuvinte A este eliminabil în X Y daca el poate fi eliminat din partea stânga sau partea dreapta a F-dependentei fara a schimba închiderea lui F.

Exemplul 5.4. Fie F= . Atributul C este eliminabil în F-dependenta A BC si B în AB D.

Definitia 5.5. Fie F o multime de F-dependente pe R si X YF, atunci:

i)            X Y este redusa la stânga daca X nu contine niciun atribut eliminabil în X Y.

ii)          X Y este redusa la dreapta daca X nu contine nici un atribut eliminabil eîn X Y.

iii)        X Y este redusa daca este redusa la stânga si la dreapta si Y

iv)        O F-dependenta redusa la stânga se numeste completa.

Definitia 5.5. Multimea de F-dependente F se numeste redusa (stânga,dreapta) daca fiecare F-dependenta din F este redusa(stânga corespunzator dreapta).

Exemplul 5.5. Multimea F din exemplul 5.4 nu este redusa (stânga, dreapta). Multimea F este redusa la stânga si dreapta.

Se observa ca pentru orice F-dependenta X Y are loc implicatia X Y XA Y. De unde se vede ca eliminarea unui atribut din partea stânga a unei F-dependente conduce la o multime de f-dependente mai puternice, adica G=F si G =F atunci G G. Pentru verificarea conditiei G=G este suficient sa aratam ca G G care duce la a verifica numai conditia ca G X Y. Algoritmul de reducere la stânga Redst a lui F se bazeaza pe aceste observatii.

0 START Redst

INPUT

G F

FOR fiecare X Y F

3.1 FOR fiecare atribut A X

3.1.1 IF termen(G,X-A Y)

then

.1 G G

3.1.2 CONTINUE

CONTINUE

OUTPUT

STOP

Pentru înlaturarea atributelor eliminabile din partea dreapta se verifica daca G =F X YA. În acest caz G G unde G=F . Întrucât X Y G , aceasta verificare conduce la verificarea X A si la algoritmul Reddr.

0 start Reddr

1 input

2 G F

3 FOR fiecare X Y F

3.1 FOR fiecare atribut A Y

3.1.1 IF termen(G- ,X A)

then

.1 G G

3.1.2 continue

3.2 continue

4 output

stop

Se poate obtine algoritmul de reducere redus.

0 start Redus

1 input

2 G redst(reddr(F))

3 call elimina(G,X Y) / Elimina X Y din G /

4 output

5 stop

Exemplul 5.6. Fie G , atunci  redus(G

5.4. Acoperiri canonice si neredundante

Definitia 5.6. Multimea de F-dependente F se numeste canonica, daca este neredundanta si orice F-dependenta din F este de forma X A si este redusa la stânga.

Deoarece multimea canonica este neredundanta si fiecare F-dependenta are un singur atribut în partea dreapta ea este redusa la dreapta, de unde rezulta ca este redusa.

Exemplul 5.7. Fie F= este o acoperire canonica pentru G= . Urmatoarea lema da legatura între acoperirea redusa si acoperirea canonica.

Lema 5.2. Fie F o acoperire redusa. Formam G descompunând fiecare F-dependenta X A₁A₂.....A_m în X A₁,X A₂,...X A_m. Acoperirea G este canonica. Daca G este o acoperire canonica atunci ea este redusa. În ambele cazuri F G.

Demonstratie. Fie G formata prin descompunerea F-dependentelor din F. Daca X A_i este redundanta atunci A_i este un atribut atrain în X A₁A₂..A_n. Daca X A_i contine un atribut eliminabileîn partea stânga atunci G X-B A_i, ceea ce înseamna ca G X-B X si prin urmare se elimina atributul eliminabile din partea stânga a F-dependentei X A₁...A_n.

Ce se poate spune despre doua acoperiri neredundante F si F pentru o multime de F-dependente G?

Definitia 5.7. Doua multimi de atribute X si Y sunt echivalente (X Y) în raport cu F, daca F X Y si F Y X.

Lema 5.2. Fie F si G doua multimi de F-dependente neredundante echivalente pe R. Fie X Y F atunci exista Z W G astfel încât X Z în raport cu F respectiv G.

Demonstratie. Fie H graful aciclic orientat derivat din F pentru X Y. Consideram F-dependentele din U(H). Fiecare din ele au un graf aciclic orientat derivat din F. În U(H) trebuie sa existe o F-dependenta oarecare Z W care are un graf J care foloseste X Y. Daca o astfel de dependenta nu exista pentru X Y exista un graf pe F- si prin urmare X Y este redundanta în F. Prin urmare J foloseste X Y si deci F Z X. Întrucât H foloseste Z W atunci G X Z si prin urmare F X 5.Z.

Lema 5.1. arata ca, daca doua acoperiri neredundante sunt echivalente, atunci pentru orice parte din stânga a unei F-dependente din F exista o F-dependenta în G a carei parte stânga este echivalenta cu cea din G.

Exemplul 5.8. Fie F= si . Multimile F si G sunt neredundante si echivalente una cu alta. Se observa ca A X, B D, AD AD. Fie F= X R.

E_F(X)=

E=

Daca în F nu exista F-dependenta cu partea stânga echivalenta cu X atunci E_F(X)=F. Multimea E_F formeaza întotdeauna o descompunere a lui X.

Daca sunt date duoa multimi neredundante F si G echivalente atunci din lema 5.1 rezulta E_F(X) F E_G(X) F. Prin urmare E_F si E_G coincid.

Definitia 5.8. O multime de F-dependente este minimala daca ea contine nu mai multe F-dependente decât orice acoperire echivalenta cu ea.

Eemplul 5.8. Multimea G= este neredundanta dar nu este mimimala, Multimea F= este minimala si este echivalenta cu G.

Definitia 5.9. Fie o multime de F-dependente G spunem ca X determina direct pe Y în raport cu G daca exista o acoperire neredundanta F a lui G care contine un graf aciclic orientat derivat din F astfel ca U(H) E_F(X)= si se noteaza cu

X ^. Y .

Constructia algoritmului de calcul a acoperirii minimale are la baza umatoarea teorema.

Teorema 5.1, Fie G o acoperire neredundanta dar ne minimala de F-dependente atunci exista E_G(X) care contine doua F-dependente distincte Y U si Z V astfel ca Y^. Z.

Demostratia vezi David Maier pagina 94.

0 PROCEDURE Minimize(G)

1 F= nonrendun (G)

2 CALL class(F; E_F)

FOR fiecare E_F (X) din E_F

4.1. FOR fiecare Y U din E_F (X)

4.1.2. FOR fiecare Y V Y U din E_F (X)

.1 IF DDeriva(F ,Y. Z)

THEN

.1.1 F:=F- Z UV

4.1.3 CONTINUE

4.2 CONTINUE

RETURN(F)

Procedura DDeriva este analoaga lui Derive si determina numai dependentele functionale directe

Teorema 5.2. Ordinul de complexitate al procedurii este O(np), unde n este numarul de atribute si p numarul de F-dependente .

Demostratie vezi Maier pagina 95.

5.5 Acoperiri optime

Pana acum acperirile estimate contineau o cantitate de F-dependente. Se putea estima chiar numarul de atribute care o definea. De exemplu conform acestei estimari multimea are dimensiunea 10.

Definitia 5.10. Multimea de F-dependente F este optima, daca nu exista nici o acoperire echivalenta cu ea cu un numar mai mic.

Exemplu 5.9. Multimea F= este acoperire optima pentru G=. Se observa ca G este redusa si minimala dar nu este optima.

Din algoritmul de minimizare rezulta lema urmatoare.

Lema 5.3. Daca F este o multime de depndente optima atunci ea este redusa si minimala.

Algoritmul de minimizare schimba multimea initiala cu una cu un numar minim de atribute.

5.5 Acoperiri inelare si depndente functionale compuse