1. m_R(r)m_S(r) oricare ar fi r(R),

2. T_R T_S,

3. FIX(R)FIX(S),

4. R S.

Demonstratie. Din propozitia 1 rezulta ca (1) este echivalenta cu (2). Vom arata ca (1) si (3) sunt echivalente. Din urmatoarea secventa rezulta ca (1)

d1) sFIX( R)

d2) s m_R (s) ( din d1 ),

d3) m_R(s)m_S(s) ( din ipoteza ),

d4) sm_S(s) ( din d2 si d3 ),

d5) sm_S(s ( din lema 1 ),

d6) s m_S(s) ( din d4 si d5 ),

d7) sFIX( S)

Aratam ca (3)(1). Adica din FIX( R) FIX( S) m_R(r)m_S (r).

Fie r(R), r' m_R(r), din idempotenta rezulta m_R(r') r', deci r'FIX( R) din ipoteza rezulta ca r'FIX( S) adica (a) m_S(m_R(r)) m_R(r). Dar m_R(r)r, din monotonia lui m_S rezulta (b) m_S(m_R(r))m_S(r) ; din (a) si (b) rezulta ca m_S(r) m_R(r).

Vom arata ca conditiile (1) si (4) sunt echivalente. Presupunem ca, dom(A) contine cel putin doua valori pentru orice atribut A din R. Notam aceste valori cu 0 si 1. Construim relatia s(R) cu q tupluri t₁,t₂,.,t_q definite în urmatorul mod :

Notam cu t₀ tuplul format numai din valori nule. Nu este greu de verificat ca t₀ apartine lui m_S(s). Prin urmare t₀m_R(s). Conform definitiei lui m_R, pentru fiecare schema R_i din R exista un tuplu t_js astfel ca t_j(R_i ) t₀(R_i). Astfel R_iS_j deci S R.

Presupunem ca R S. Fie r(R) o relatie arbitrara si t un tuplu arbitrar din m_S(r). În r exista tuplurile t₁,t₂,.,t_q astfel ca t_i(S_i) t(S_i), 1iq. Deoarece R S atunci pentru orice R_j din R exista S_i, S_iR_j, prin urmare t_i(R_j) t(Rj). Fie tuplurile t_j'r, t_j'(R_j) t(R_j ) din care rezulta ca t este din m_R(r) si prin urmare m_R(r)m_S(r).

Exercitiu. Fie R si S . Daca R S se observa ca T_R(r) T_S(r). Fie relatia r(R) din figura 1 si tablourile T_R(r) si T_S(r).

r(_{A1 A2 A3 A4} ) _TR(_{A1 A2 A3 A4} ) _TS (_{A1 A2 A3 A4} )

2 5 7 9  2 5 7 9  2 5 7 9

3 4 8 10  2 5 8 10  3 5 8 10

4 6 8 11  2 5 8 11  3 5 8 11

  3 5 7 9  4 6 8 10

  3 5 8 10 4 7 8 11

  3 5 8 11

  4 6 8 10

  4 6 8 11

Figura 1  Figura 2  Figura 3

Corolar 8.1. Fie multimile de scheme de relatie R si S unde R R₁,R₂,.,R_p S₁,S₂,.,S_q. Urmatoarele afirmatii sunt echivalente :

1. m_R m_S

2. T_RT_S,

3. FIX(R)=FIX(S),

4. R~ S.

Prin conditia (1) întelegem m_R(r) m_S(r) pentru orice r(R).

Fie R si S Multimile de scheme de relatie R si S sunt echivalente. Din corolarul 1 rezulta ca T_RT_S, dar evident ca T_RT_S. Cum se observa din exemplul urmator chiar daca se vor redefini variabilele secundare.

_TR(_{A1 A2 A3 A4} )  _TS (_{A1 A2 A3 A4} )

  _{a1 a2 a3 b1  a1 a2 a3 b1}

_{a1 b2 b3 a4  b2 b3 a3 a4}

_{a1 b4 a3 a4  a1 b4 a3 a4}

Figura 1  Figura 2

Definitia 8.7. Fie w₁ si w doua linii ale tabloului T de schema R. Daca pentru orice atribut A din R cu w₂(A) principala rezulta ca w₁(A) este variabila principala si se spune ca w₁ absoarbe ( subsume ) w₂.

Definitia 8.8. Fie T un tablou. în care liniile nu mai pot fi ( reduse ) absorbite de nici o alta linie se numeste redus prin absortie si se noteaza cu SUB(T).

Exemplul 8.6. În tabloul T_R w₁ absoarbe w₂ deoarece w₁(A₁) a₁ w₂(A₁) a₁ w₁(A₄) a₄ w₂(A₄) a₄ atunci :

SUB(T_R)(A₁ A₂ A₃ A₄) SUB(T_S)( A₁ A₂ A₃ A₄)

_{a1 a2 a3 b1  a1 a2 a3 b1}

_{a1 b4 a3 a4  a1 b4 a3 a4}

Teorema 8.3. Fie multimile de scheme de relatie R si S unde R R₁,R₂,.,R_p S₁,S₂,.,S_q. Atunci:

1) T_RT_S SUB(T_R) SUB(T_S) exceptând variabilele secundare.

2) SUB(T_R)T_R.

Pentru demonstratie vezi Maier/ /.

8.5. C-Transformari

Teorema 8.3 arata ca exista un procedeu simplu pentru verificarea echivalentei a doua tablouri obtinute din multimi de scheme si anume verificarea identitatii reduse prin absortie. Orice tablou în care nici o variabila secundara nu se întâlneste mai mult decât o data se obtine dintr-o multime oarecare de scheme. Teorema 8.3 nu este adevarata pentru tablourile unde variabilele secundare sunt duplicate.

Dorim sa formulam conditii de echivalenta pentru tablouri arbitrare introducând c-transformarea pentru tablouri. C-transformarea este asemanatoare evaluarii (estimarii), care în locul transformarii variabilelor tabloului în elemente ale domeniului ele se transforma în variabile ale altui tablou. Prin urmare liniile se transforma în linii.

Definitia 8.9. Fie T si T' doua tablouri de schema R si multimile de variabile V si V'. Transformarea y :V→V' se numeste c-transformare din T în T' daca ea satisface urmatoarele conditii :

1) daca variabila v se afla în linia A a tabloului T atunci y(v) se afla în linia A a tabloului T' ;

2) daca v este o variabila principala atunci y(v) este variabila principala ;

y(v) T'. Adica, daca y este extinsa la liniile lui T si deci la întregul tablou T atunci prin aceasta transformare o linie din T se transforma într-o linie din T'.

Exemplul 8.7 Fie tablourile T si T' din figura 1 si 2 si c-transformarea din figura 3

T(A₁ A₂ A₃ A₄) T'(A₁ A₂ A₃ A₄)

  y 1 i

  y y

  y y y  

Figura 1  Figura 2  Figura 3

Primele doua linii din T sunt aplicate în primele doua linii din T' de y, c-transformarea y aplica a treia linie dinT în a doua linie din T'.

Teorema 8.4. Fie tablourile T si T' de schema R. T T' daca si numai daca exista o c-aplicatie de la T la T'.

Demonstratie. Suficienta. Fie y o aplicatie de la T la T'. Fie r(R) o relatie oarecare, T(r) si T'(r). Daca r este o evaluare a lui T' astfel ca r (T') r, atunci r y este o evaluare pentru T, r y(T) r. Incluziunea rezulta din y(T) T' prin aplicarea lui r. Daca w_d este o linie formata din variabile principale si y( w_d) w_d r y(w_d)) r (w_d) deci T'(r) T(r).

Necesitatea. Presupunem ca T T'. Considerând tabloul T' ca relatie obtinem T(T')T'(T') Luând evaluarea r' care este transformarea identica a variabilelor V' din T'. Evident r'(T') T'T' si r'(w_d) w_dT'(T'). Exista o evaluare r pentru T astfel ca r (T) T', r (w_d) w_d. Atunci definim c-aplicatia din T la T' prin r

Corolar 8.2. Fie T si T' doua tablouri de schema R. T T' exista o c-transformare de la T la T' si o c-transformare de la T' la T.

Exemplul 8.8 Fie T tabloul care este compus numai dintr-o linie formata numai din variabile principale w_d si T' un tablou care contine w_d, atunci T T'. C-transformarea din T la T' aplica w_d în w_d. C-transformarea din T' în T aplica toate liniile în w_d.

8.6. Echivalenta schemelor determinata de restrictii

În acest paragraf se determina care sunt proprietatile unei relatii care sa fie corect reprezentata prin proiectiile sale. Din corolarul 8.1 rezulta ca, daca R este o schema a bazei de date atunci FIX(R) este multimea tuturor relatiilor pe R R₁,R₂,.R_p numai daca R_i R pentru un i anumit. În multe cazuri dorim sa reprezentam o multime de relatii pentru schema R asupra careia se aplica o multime impusa de restrictii. Vom utiliza restrictiile ca sa reprezentam relatiile.

Definitia 8.10. Fie P o multime de relatii de schema R. Daca T₁ si T₂ sunt tablouri de schema R atunci T₁ cuprinde peT₂ în raport cu P ( notat T₁⊒_P T₂ ) daca

T₁(r) T₂ (r), r P.

T_{1 P}T₂ ( sunt echivalente pe P ) daca T_{1 P}T₂ si T_{2 P}T₁.

În majoritatea cazurilor se considera P SAT(C) pentru o multime de restrictii C data. Notam pe scurt pe prin . Ne intereseaza când SAT(C) FIX(R) pentru o schema a bazei de date R. Adica pentru o schema a bazei de date R putem sa descompunem fara pierdere pe R orice relatie din SAT (C). În termenii restrictiilor aceasta se poate reduce la verificarea corectitudinii relatiei C *[R]. Daca T_I este un tablou pentru transformarea identica (T_I contine linia formata din variabile principale), atunci dorim sa stim daca T_R se comporta ca T_I pe SAT(C) adica T_R T_I ? Teorema 8.3 da un test pentru dar ne trebuie un test pentru . Pentru lema urmatoare va trebui sa privim un tablou ca o relatie care este din multimea P. Prin aceasta se întelege ca pentru orice evaluare r, r(T) P Pentru o multime arbitrara de relatii aceste conditii sunt mai greu de verificat. Totusi câând P=SAT(C) unde C consta într-o multime de F- sau J-dependente daca pentru o evaluare bijectiva r r (T) P, atunci pentru orice alta evaluare r r'(T) P.

Lema 8.1. Fie T₁ si T₂ doua tablouri de schema R si P o multime de relatii pe R. Fie T₁' si T₂' astfel ca :

1) T_{1 P} T₁' si T_{2 P} T₂' si

2) T₁' si T₂' considerate ca relatii sunt ambele din P.

Atunci T₁ T₂ daca si numai daca T₁' T₂'.

Demonstratie Suficienta este directa. Daca T₁' T₂' atunci rezulta ca T₁'⊑_P T₂', dar T_{1 P}T₁'si T_{2 P} T₂' deci T₁⊑_PT₂. Vom arata ca, daca T₁⊑_P T₂ atunci T₁' T₂'. Considerând T₁' simultan ca relatie si tablou atunci T₁'(T₁') este din P si T₁'(T₁') T₂'(T₂'). Fie w_d o linie a tuturor variabilelor principale si r o evaluare identica a lui T₁'. Evident r (T₁') T₁' astfel r (w_d) w_d este în T₁'(T₁') prin urmare si în T₂(T₁'). Exista o evaluare h pentru T₂' astfel ca h( T₂') T₂' si h(w_d) w_d. Evaluarea h poate fi considerata ca o c-transformare din T₂' în T₁' si prin urmare rezulta T₁ * T₂'.

Corolar 8.3. În ipotezele lemei 8.1. rezulta ca T_{1 P} T₂ daca si numai daca

T₁' T₂'.

Acest corolar poate fi interpretat ca un test de verificare a relatiei T₁ T₂, daca printr-un procedeu am afla tabloul T', astfel ca T' _CT si T' ca relatie este în SAT(C). Vom introduce reguli de transformare pentru tablouri. O regula de transformare determinata de o multime de restrictii C este un procedeu de modificare a tabloului T în tabloul T' astfel ca T _CT'. Prima transformare particulara a fost c-transformarea prin absortie. Pentru un tablou T cu variabile secundare ne duplicate eliminarea liniilor absorbite conserva echivalenta. Va trebui sa gasim multimea regulilor de transformare ( F-reguli si J-reguli) pentru o multime data C de F-dependente si J-dependente. Aplicarea repetata a acestor reguli de transformare are ca rezultat obtinerea unui tablou care satisface toate dependentele din C. În continuare vom considera o multime C de F- si J-dependente pentru o multime U de atribute care constituie schema pentru toate restrictiile si tablourile considerate. Oricarei F-dependente XA din C îi este asociata o F-regula. F-regula determinata de X A reprezinta o clasa de transformari care poate fi aplicata unui tablou care nu depinde de liniile alese.

F-regula

Fie un tablou T care contine liniile w₁ si w₂ unde w₁(X) w₂(X) si v₁ w₁(A) si v₂ w₂ (A), v₁ v₂. A aplica o F-regula determinata de F-dependenta X A la tabloul T, înseamna a identifica variabilele v₁ si v₂ si a înlocui una din ele prin alta în urmatorul mod :

- daca una din v₁ si v₂ este principala, sa zicem v₁ instanta lui v₂ este înlocuita cu v₁.

- daca v₁ si v₂ nu sunt principale atunci orice instanta cu indice mai mare este înlocuita cu instanta variabilei cu indice mai mic.

Deoarece tabloul este o multime de linii, câteva din ele prin redefinire vor fi identice si vor fi eliminate.

Exemplul 8.9 Fie tabloul T din figura 1 si C . Aplicând F-regula determinata de A₂A₄ A₃ la liniile 1 si 2 permitem înlocuirea variabilei b₃ cu a₃ deoarece a₃ este principala si obtinem tabloul T'.

T(A₁ A₂ A₃ A₄ T'(A₁ A₂ A₃ A₄) T"( A₁ A₂ A₃ A₄

Figura 1  Figura 2   Figura 3

Aplicând F-regula determinata de A₁A₂ A₄ se obtine tabloul T" deoarece variabile b₁ si b₄ trebuie identificate prin cea cu indice mai mic. Astfel prima si ultima linie sunt identice deci se elimina una din ele.

Teorema F. Fie T' tabloul rezultat prin aplicarea unei F-reguli date de X A din tabloul T. Atunci T si T' sunt echivalente pe SAT(X A).

J-regula

Fie S o multime de scheme de relatii si *[S] o J-dependenta pe U. Fie T un tablou si w₁,w₂,.,w_q liniile lui T care sunt unibile pe S cu rezultatul w. Aplicarea J-regulii *[S] la T înseamna formarea tabloului T' T

Exemplul 8.10. Fie T tabloul reprezentat în figura 4 si C . Aplicând J-regula determinata de *[ A₁A₂, A₂A₃, A₃A₄] la a doua si a treia linie din T genereaza linia <a₁ b₁ b₃ a₄>. Rezultatul este tabloul T' dat în figura 5.

T(A₁ A₂ A₃ A₄ T'(A₁ A₂ A₃ A₄ ) T"( A₁ A₂ A₃ A₄

Figura 4  Figura 5  Figura 6

J-regula data de *[A₁A₂A₄, A₁A₃A₄] poate fi aplicata la prima si a patra linie a lui T'; se genereaza linia <a₁ b₁ b₃ a₄> iar tabloul T" este rezultatul acestei aplicatii.

Teorema J. Fie S Fie T' tabloul rezultat prin aplicarea J-regulii determinata de *[S] din tabloul T. Atunci tablourile T si T' sunt echivalente pe SAT(*[S]).

Demonstratie. Va trebui sa aratam ca T(r) T'(r) pentru orice r SAT(*[S]). Fie t' T'(r) si r o evaluare cu r (w_d) t' si r(T') r. Deoarece T T' avem r(T) r(T') de asemenea r(T') r si r(w_d) t' T(r). Prin urmare T'(r) T(r). Acum fie t un tuplu oarecare din T(r) si r o evaluare cu r(w_d) t si r(T) r. Tuplul unic care ar putea apartine lui r(T') dar nu lui r(T) este r(w) unde w este generata de J-regula determinata de *[S] din liniile w₁,w₂,.,w_q care apartin lui T. Daca w₁,w₂, .,w_q sunt unibile pe S atunci r(w₁), r(w₂),.,r(w_q) unite pe *[S] dau rezultatul w. Întrucât r intra în SAT(*[S]) si r(w₁), r(w₂),., r(w_q) r(T) r atunci r(w) r. Prin urmare r(T') r si r(w_d) t T(r), deci T(r) T'(r) si deci T(r) T'(r).

8.7. Algoritmul chase

În acest paragraf se da un algoritm de calcul care se bazeaza pe metoda chase, cu ajutorul careia pentru un tablou dat si o multime de dependente C se construieste un nou tablou T* astfel ca T T* si T* ca relatie sa apartina lui SAT(C). Pentru un tablou T si o multime de dependente C se aplica regulile determinate de F- si J-dependentele din C atâta timp cât se realizeaza schimbari. Ordinea de aplicare este neesentiala. Conform teoremelor F si J la terminarea algoritmului se genereaza un tablou T* T si T* SAT(C).

Fie tabloul T din figura 1 si C . Aplicând F-regula determinata de B C se obtine T₁ din figura 2. Aplicând J-regula *[ABC, BCD] se obtine T₂ din figura 3. Aplicând F-regula determinata de AD C se obtine T₃ din figura 4.

T ( A B C D) ( A B C D ) ( A B C D ) (A B C D ) T*( A B C D )

b₄

Figura 1 Figura 2 Figura 3 Figura 4 Figura 5

Aplicarea J-regulii determinatâ de *[ABC, BCD] lui T₃ permite obtinerea lui T* si orice alta regula îl lasa invariant. Astfel T* este ca relatie în SAT(C).

Definitia 8.11. Se numeste secventa generata din T prin aplicarea regulilor ( F- sau J) determinate de dependentele din C, secventa T₀ T,T₁,. .T_i. unde T_i se obtine din T_i-1 prin aplicarea unei F- sau J-reguli determinata de o dependenta din C, se presupune T_i-1 T_i. Ultimul element T_n din secventa generata, care prin aplicarea oricarei F- sau J- reguli determinata de C nu-l mai schimba se numeste chase-ul lui T în raport cu C. Operatorul corespunzator îl notam cu (T).

Algoritmul realizat mai jos doua proceduri TR si DIF. Procedura TR transforma tabloul T_j+i în T_j+i+1 pe baza regulei determinata de dependenta C_i. Functia DIF determina daca exista o diferenta între doua transformari succesive.

0 START [Chase ]

1 INPUT [ T, k, C₁,C₂,.,C_k]

2 n

3 T_n T

4 d

5 WHILE d

5.1 d

5.2 FOR i 1, 2. .., k

5.1.1 CALL TR(T_n,C_i;T*)

5.1.2 IF DIF(T_n,T')

  THEN

  .1 nn+1

  .2 T_nT*

  .3 d =0

5.1.3 CONTINUE

5.3 CONTINUE

6 OUPUT

7 STOP

Exemplul 8.11. Fie T si C din exemplul 1. T, T₁, T₂, T₃ si T* este o secventa generata din T de C si T* Chase_C(T). Va trebui sa observam cum se transforma liniile pe parcursul aplicarii algoritmului Chase. Fie T' obtinut din T prin aplicarea unei J-reguli. Atunci daca w este o linie a lui T ei îi corespunde în T' aceeasi linie sau are în plus o linie obtinuta prin unirea unui numar de linii. Fie T' derivat din T prin aplicarea unei F-reguli care schimba variabila v cu variabila v'. Daca w este o linie în T îi corespunde în T' o linie w' care este de fapt w în care s-a înlocuit v cu v'. ( Daca w nu contine v atunci w w' ).

Daca T₀,T₁,.,T_i,.,T_j este o secventa generata din T determinata de C si este o linie din relatia " corespunde " poate fi prelungita tranzitiv.

Spunem ca linia din corespunde liniei daca exista unde si corespunde lui , corespunde , si corespunde lui . Pentru orice linie w dintr-un tablou al secventei generate din T în orice tablou care îi urmeaza exista o linie care îi corespunde.

Teorema 8.5. Fie tabloul T si retrictiile C. Orice secventa generata din T determinata de C este finita, adica (T)

Demonstratie. Deoarece tablourile sunt multimi finite de linii si orice regula nu introduce noi variabile, exista numai un numar finit de tablouri care pot sa apara în secventa generata din T determinata de C. Este suficient sa aratam ca nici un tablou nu apare de doua ori. Fie si doua tablouri dintr-o secventa generata de din T deterninata de C, i<j. Daca la fiecare pas o F-regula a fost utilizata atunci contine câteva variabile care în lipsesc, deci . Daca în secventa se aplica numai J-reguli atunci contine cel putin o linie în plus fata de , deci

Teorema 8.6. Orice tablou T* din (T), considerat ca relatie este în SAT(C).

Demonstratie. Daca T* nu ar satisface F-dependenta XA din C atunci ar exista doua linii si în T* astfel ca (X) (X) si (A)(A). Atunci putem aplica F-regula determinata de XA liniilor si care se schimba în T* ceea ce arata ca T* nu este ultimul tablou în secventa generata din T determinata de C. Similar daca T' violeaza o J-dependenta din C atunci aplicând J-regula determinata de F-dependenta respectiva se obtine un nou tablou cu o linie în plus.

Corolar 8.4. (T) T considerat ca relatie apartine lui SAT(C).

8. 8. Proprietatea Church-Rosser

Calculul chase-ului este un exemplu de sistem de implicatii. Un sistem de implicatii este o pereche ( Q,), unde Q este o multime de obiecte si este o relatie binara antireflexiva pe Q, numita relatie de transformare. În cazul nostru calculul chase-ului este un nou sistem de implicatii n raport cu orice multime de restrictii. Multimea Q este formata din tablouri pe U si TT' daca T' se obtine din T prin aplicarea unei F- sau J-reguli determinata de o dependenta din C.

Definitia 8.12. Închiderea tranzitiva si reflexiva a relatiei se noteaza . Vom citi T T' prin " T trece în T' " sau " T' este obtinut din T ".

Definitia 8.13. Fie sistemul de implicatii ( Q,), obiectul pQ se numeste ireductibil ( terminal ) daca p q implica p q, adica nu exista pq pentru ca sa avem pq.

Definitia 8.14. Sistemul de implicatii ( Q,) este finit daca pentru orice pQ exista o constanta c, care depinde de p astfel daca p q în i pasi atunci ic. Adica pentru orice obiect pQ exista numai un numar finit de transformari ale lui într-un obiect ireductibil (terminal ).

Utilizând teorema 8.5 din paragraful precedent rezulta ca sistemul de implicatii pentru calculul chase-ului este finit. Prin (T) am notat toate tablourile terminale obtinute din T prin utilizarea F- sau J-regulilor determinate de dependentele din C.

Definitia 8.15. Un sistem de implicatii ( Q, ) este FCR ( Finit Church-Rosser ) daca pentru orice pQ si daca p si p si si sunt ireductibile atunci Adica începând cu orice p ajung la unul si acelasi obiect ireductibil independent de procedeul de aplicare a transformarii.

Teorema 8.7. ( Sethi ) : Sistemul de implicatii ( Q,) este FCR daca si numai daca pentru orice pQ, p si p exista qQ astfel ca q si q₂ q.

Pentru demonstratie vezi Sethy / /.

Daca T₀,T₁,.,T_i,.,T_j este o secventa generata din T determinata de C si este o linie din , relatia " corespunde " poate fi prelungita tranzitiv.

Spunem ca linia din corespunde liniei daca exista unde si corespunde lui corespunde , si corespunde lui . Pentru orice linie w dintr-un tablou al secventei generate din T în orice tablou care îi urmeaza exista o linie care îi corespunde.

Teorema 8.8. Calculul chase-ului determinat de o multime de restrictii C este un sistem de implicatii FCR. Prin urmare este un singleton.

Demonstratie. Trebuie sa aratam ca calculul chase-ului este un sistem de implicatii finit. Adica va trebui sa aratam ca, daca din tabloul T se obtin tablourile si prin aplicarea unor reguli de transformare determinate de dependentele din C atunci exista un tablou T* care poate fi obtinut din T₁ sau T₂ prin aplicarea a uneia sau mai multor reguli de transformare determinate de C.

Pentru aceasta vom examina trei cazuri.

T  T T

F-regula F-regula F-regula J-regula J-regula J-regula

T₁ T₂  T₁ T₂  T₁ T₂

Cazul 1 Cazul 2  Cazul 3

Se observa ca J-regulile lasa neschimbate liniile si ca o F-regula nu poate schimba ocurenta unei unei variabile fara a o schimba pe cealalta. Fie w₁ si w₂ doua linii în T si u₁ si u₂ linii în T' corespunzatoare lui w₁ si w₂ unde T' este obtinut din T prin aplicarea unei F- sau J-reguli. Deoarece daca w₁(X) w₂(X) atunci u₁(X) u₂(X) rezulta ca daca o F- sau J-regula este aplicata la o multime de linii în T atunci aceeasi regula este aplicabila la multimea de linii corespunzatoare lui T'.

Cazul 1: Fie T₁ dedus din T prin aplicarea regulii XA cu variabilele v₁ si v₂, si T₂ dedus din T prin aplicarea regulii YB cu variabilele v₃ si v₄. Daca AB se utilizeaza regula dedusa din XA pentru a identifica variabilele v₁ si v₂. Rezultatul este T*. Analog plecând

de la T₁ prin aplicarea lui YB se identifica v₃ si v₄. Daca A B se aplica succesiv regulile XA si YB cel mult de doua ori si se obtine T*.

Celelalte cazuri sunt simple exercitii.

Corolar 8.5. Daca SAT(C) SAT(C') atunci (T) (T) pentru orice tablou T.

Demonstratie: Vom da demonstratia în cazul când C' C pentru orice c cu proprietatea Cc. Fie T* (T). Aplicarea acelorasi reguli determinate de C la tabloul T conduce la obtinerea lui T*, deoarece C'C. Din teorema 8.6 rezulta ca nu putem aplica o regula din C' la T*, deoarece T* ca relatie este în SAT(C) si prin urmare în SAT(C'). Deci (T) T*.

8.9. Echivalenta tablourilor determinata de restrictii

Vom testa echivalenta tablourilor determinata de o multime de restrictii, care constituie un test pentru cazul când transformarea m_R este fara pierderi de informatii pe SAT(C). Din observatiile de la începutul acestui paragraf se stie ca T(T). Din lema 1 rezulta urmatoarea teorema :

Teorema 8.9. Fie tablourile T₁ si T₂ si C o multime de restrictii.

  T₂⊑_CT_{1 dac}a s_{i numai dac}a Chase_C(T₂) Chase_C(T₁).

Corolar 8.6. T₁T₂Chase_C(T₁)Chase_C(T₂)

Vom da un procedeu de a verifica când toate relatiile din SAT(C) pot fi corect reprezentate prin proiectiile lor dupa schemele de relatie ale unei baze de date de schema R. Aceasta conditie este echivalenta cu C*[R] sau ca este aplicatia identica pe SAT(*[C]). În termenii echivalentei tablourilor T_{R C}T_I unde T_I este tabloul compus din w_d linia variabilelor principale. T_I este aplicatia identica a tuturor relatiilor.

Dintr-o teorema 8.8 rezulta ca pentru a testa echivalenta este suficient Chase_C(T_I) T_I. Verificarea conditiei Chase_C(T_R) T_I se reduce la a verifica ca Chase_C(T_R) contine w_d.

8.10. Verificarea implicatiei dependentelor functionale

Fie C o multime de dependente functionale. Vom introduce un test pentru verificarea unei F-dependente din multimea C. Prezentam lema pe baza careia se demonstreaza teorema de caracterizare a implicatiei.

Lema 8.2. Fie T un tablou si C o multime de restrictii. Fie ρ o evaluare a tabloului T astfel ca ρ(T) r unde r SAT(C). Daca este o secventa generata pentru (T), atunci pentru 0in :

ρ (w_i) si w_i absoarbe unde w₀ este o linie oarecare în si w_i este

linia care-i corespunde în ;

r;

, in.

Demonstratie. Pentru a demonstra (1) si (2 ) este suficient sa aratam ca, daca este o linie din si este linia care-i corespunde în atunci ρ ( ) si absoarbe . Daca w este o linie în care nu corespunde la nici o linie în , atunci ρ(w) r. Daca este obtinut prin aplicarea unei F-reguli care nu schimba variabilele în , atunci , si deci ρ( absoarbe . În caz contrar, deoarece trece în , pentru un atribut A (A) se schimba din în . Schimbarea se face prin aplicarea F-regulii determinata de F-dependenta XA atunci pentru liniile si în în care (X) (X) si (A) si (A) si ρ( unde si sunt tupluri din r. Va trebui sa avem (X) (X) deoarece r este în SAT(C) si (A) (A). Deci ρ( (A)) (A) (A) (A)) ). Prin urmare ρ( ). Daca w este o linie în care nu corespunde nici unei linii din atunci w este rezultatul unei uniri si deci apartine lui SAT(C).

Fie dependenta netriviala XA si dorim sa testam când CXA. Construim tabloul care este format din doua linii si . Linia este formata numai din variabile principale si are variabile principale numai în coloanele care apartin lui X. Adica , R

Teorema 8.10. C X A daca si numai daca (T_X) contine în coloana lui A numai variabile principale.

Demonstratie. Fie T ). Presupunem ca T* are variabile secundare în coloana A. T* este considerat ca relatie este contraexemplu pentru CXA. Din teorema 8.6 rezulta ca T* satisface C. Prin urmare orice linie a lui T* are toate simbolurile principale în coloanele lui X, deoarece calculul chase-ului nu creaza noi simboluri. Din lema 8.2 rezulta ca linia ramâne neschimbata. Prin urmare T* are doua linii compatibile pe X si necompatibile pe A, deci T* contrazice XA. Presupunem ca T* are numai variabile principale în coloana X si r o relatie arbitrara din SAT(C). Fie si cu (X) (X), r. Consideram ρ o evaluare a lui astfel ca ρ( si ρ( . O astfel de evaluare exista deoarece (X) (X). Iar este linia din T* este linia care corespunde lui din . Fie * linia din * care corespunde lui din . Din lema 8.2 ρ( ) si T* are aceleasi variabile în coloana A, (A) *(A).

(A) (A)) (A)) (X)) (A)

Astfel doua tupluri din r compatibile pe X sunt comparibile pe A. Prin urmare deoarece r a fost arbitrar aleasa rezulta SAT(C)SAT(XA) sau CXA.

Pe aceasta teorema se bazeaza urmatorul algoritm :

0 PROCEDURE TID ( X, A, C, n ;w) /*-Testarea implicatiei CXA */

1 Call generare(X,n;T_X)

2 CALL Chase( C, ; T, p) /p-reprezinta nr de linii ale chase-ului/

3 d 0

4 i

5 WHILE d

5.1 IF T( i, A ) a_A

THEN

.1 d

ELSE

.2 IF ip

THEN

.2.1 i i + 1

ELSE

.2.2 d

6 IF d

THEN

6.1 w TRUE

ELSE

6.2 w FALSE

7 RETURN(w)

0 Procedure generare(X,n;T_X)

1 k

2 FOR i 1, 2,..., n

2.1 ( 1, i )

2.2 IF X

THEN

.1 ( 2, i )

ELSE

.2 k k + 1

. ( 2, i )

2 Return

Exemplul 8.12. Fie C si dorim sa aratam ca CBCD. În acest caz . Exista în coloana D astfel ca BCD nu este implicata de C. Daca C' atunci ) este T*.

T* ( A B C D )

T* are numai în coloana D, deci CBCD.

Pâna acum am definit închiderea lui X numai în raport cu o multime de F-dependente. Vom extinde definitia pentru a cuprinde si J-dependente.

Definitia 8.16. Fie C o multime de F-dependente si J-dependente si X o multime de atribute. Se numeste închidere a lui X determinata de C, notata , cea mai mare multime Y cu proprietatea CX Y.

Observatie. Daca C este formata numai din F-dependente, aceasta definitie se reduce la vechea definitie.

Corolarul 8.7. Pentru o multime data C, este formata din toate atributele A pentru care ) are numai variabile principale.

Corolarul 8.8. Daca J este o multime de J-dependente, atunci JX Y implica XY. Adica o multime de J-dependente implica numai F-dependente triviale.

Demonstratie. Deoarece ) are o variabila secundara în orice coloana corespunzatoare lui U, X , deoarece J regula nu identifica simboluri. Deoarece dependentele multivoce sunt cazuri speciale de J-dependente vom putea testa CX Y prin testarea lui C*[ XY, XZ], unde Z U-XY.

Teorema urmatoare arata o cale alternativa care utilizeaza Chase pentru a gasi întreaga multime Y astfel ca CX --»Y, pentru un X dat.

Teorema 8.11. Fie C o multime de restrictii si fie Y o multime disjunctiva de multimea determinata de C. CX Y daca si numai daca contine o linie cu variabile principale numai în coloana Y

Demonstratie. Necesitatea. Fie ). Fie si liniile corespunzatoare lui si din . Fie schema bazei de date R unde Z U-Y. Vom arata ca ) trebuie sa contina . Prin urmare C[XY,XZ]. Fie si liniile în pentru schemele XY si XZ si fie si liniile în . Se considera aplicatia δ de la variabile din la variabile din data de δ( . Daca este considerat ca relatie atunci δ poate fi privita ca o evaluare si deoarece (X) (X) rezulta (X) (X). Prin urmare T* considerat ca relatie este în SAT(C), din lema 8.1 δ( (X), δ( ) si δ( ). Deoarece ). Se vede ca aplica variabilele principale din coloanele lui în ale lui * si variabilele principale din coloanele lui în ale lui *. Vom arata ca linia a lui are variabile principale în coloanele Y ) este linia din *. Deoarece contine variabile principale în coloanele ) contine variabile principale în coloanele lui . Deoarece absoarbe contine p-variabile în coloanele din Y. Se stie ca δ( , δ aplica p-variabilele din Y în coloanele Y ale lui *. Linia contine variabile principale în coloanele Y, astfel δ() este variabila principala în toate coloanele Y. Deoarece absoarbe este formata din variabile principale în toate coloanele lui Z. Este cunoscut ca δ( , de aceea δ trebuie sa aplice variabile principale din coloana Z a lui în variabile principale ale coloanelor lui Z ale lui *. Linia este neprincipala în coloanele Z. U=YZ, astfel δ () este d-principala în coloanele Z. Prin urmare contine , astfel CX Y.

Implicatia inversa. Presupunem CX Y. Fie C'= C *[ XY, XZ], unde Z=U-Y. Din corolarul 8.6 rezulta ca ) deoarece SAT(C) =SAT(C').

0 PROCEDURE ÎNCHIDERE ( X, C,n ; , k )

1 CALL generare(X,n;T_X )

2 CALL ; T*, m )

3 k 0

4

5 FOR j = 1, 2,..., n

5.1 d

5.2 i

5.3 WHILE d=1 & i m

5.3.1 IF

  THEN

  5.3.1.1 d 2

  ELSE

  5.3.1.2 i i + 1

5.3.2 CONTINUE

5.4 IF d = 1

THEN

5.4.1 k k + 1

5.4.2

5.5 CONTINUE

6 RETURN

Teorema 8.11 sta la baza urmatorului algoritm de verificare a implicatiei CX--»Y.

0 START [ TIDM - Testerea Implicatiei MV-dependentei ]

1 INPUT

2 CALL generare ( X,n ; ) //genereaza

3 CALL Chase(C, ; T*, m )

4 CALL INCHIDERE ( X, C ; , k )

5 i

6 d

7 WHILE in & d=2

7.1 j 1 w

7.2 WHILE w=0 & jn

7.2.1 IF Y

  THEN

  .1 IF

  THEN

  .1.1 w

ELSE

  .1.2 j j+1

  .2 CONTINUE

7.2.2 CONTINUE

7.3 IF w = 0

THEN

7.3.1 d

ELSE

7.3.2 i i 1

7.4 CONTINUE

8 CASE d OF

8.1 OUTPUT

8.2 OUTPUT

9 STOP

8.11. Tabloul ca patern al unei relatii

În acest paragraf se formalizeaza ideea tabloului ca patern (sablon) al unor relatii.

Definitia 8.17. Fie P o multime de relatii si r o relatie oarecare. Relatia s din P se numeste completare a lui r în P daca rs si nu exista nici o relatie s' P astfel ca rs's. Multimea tuturor completarilor se noteaza cu (r). Scrierea prescurtata a lui (r) este COMP(r). Completarea nu exista întotdeauna.

Exemplul 8.13 Fie relatia r din figura 1). Daca C = atunci (r)=. Daca C = [ AB, BCD ] atunci (r)= s din figura 2.

r ( A B C D ) s ( A B C D ) Q ( A B C D )

4 5 7  2 4 5 7 2 4 5 7

4 5 7  3 4 5 7 3 4 5 7

2 4 6 8 2 4 6 8 2 4 6 8

  3 4 6 8 3 4 6 8

Figura 1 Figura 2 Figura 3

Daca o completare exista ea nu este unica.

Exemplu 8.14 Fie relatia din figura 1 si P = SAT([AB, BC]). Completarea (r) contine relatia s din figura 2 si relatia q din figura 3.

O multime P de relatii se numeste închisa în raport cu intersectia daca pentru orice pereche de relatii r si s din P r s este în P.

Lema 8.3. P este închisa în raport cu intersectia daca si numai daca completarea în raport cu P este unica.

Demonstratie. Presupunem ca P este închisa fata de intersectie. Fie s si s' completari ale lui r în raport cu P. Din închidere rezulta s' s P si s' s r, astfel ca s= s' s = s'. Fie r si s din P si q= r s. Exista o submultime r' a lui r ( care poate fi r însasi) astfel ca r' este o completare a lui q în raport cu P. Analog exista s' în P care este o completare a lui q. Din ipoteza de unicitate rezulta s'= r', de unde s'= q'= r', deci q apartine lui P.

Corolar 8.9. Daca C este o multime de F- si J- dependente atunci (r) este unica.

Vom defini multimea relatiilor care reprezinta un tablou.

Definitia 8.18. Fie T un tablou si P o multime de relatii. Multimea care reprezinta T în raport cu P este notata REP_C (T) este :

.

Notam cu REP_C (T)= REP _{SAT( C )} (T).

Lema 8.4. Fie P o multime de relatii închisa în raport cu intersectia si T₁ si T₂ doua tablouri. Daca T₂ ⊒T₁ atunci orice r REP_P (T₁) exista s REP_P(T₂) astfel ca sr.

Demonstratie:Vezi Maier pagina 189.

Teorema 8.12. Fie C o multime de restrictii si T un tablou. Daca T*=(T) atunci REP_P (T)= REP_P (T*).

Demonstratie. Presupunem r REP(T). Fie ρ o evaluare astfel ca r = COMP_C(ρ(T)). Evident ca ρ(T) r. Deoarece r SAT(C) din lema 8.4 rezulta ρ(T) (T*) si ρ(T*) r de unde rezulta COMP(T*))=r deci REP(T) REP(T*). Acum presupunem ca r REP(T*). Fie evaluarea ρ astfe ca COMP(ρ(T*))=r. Deoarece T* ca relatie apartine lui SAT(C) ρ(T*) SAT(C), avem r=ρ(T*). Tabloul T poate avea mai multe variabile decât tabloul T dar ρ(T) (T*). Fie w o linie arbitrara din T si w* linia corespunzatoare din T*, punem ρ( w)= ρ(w*).

Fie T=T₀,T₁,...,T_n=T* secventa generata pentru T*. Din lema 8.4 rezulta

(T _) (T₂) (T _n).

Deoarece SAT(C) satisface proprietatea de intersectie

COMP_C(ρ(T_i))  COMP_C (ρ (T_i+1))

In ρ(T_i+1) trebuie sa existe ρ(w) care nu intra în COMP_P(ρ(T_i)) în caz contrar ρ(T_i+1) COMP_C(ρ(T)) si ambele incluziuni sunt adevarate. Prin urmare w T_i+1 si w T_i.

Corolar 8.8. Pentru o multime data de restrictii C si pentru un tablou T

REP_C(T)=.

Exercitii.

1. Fie relatiile r si s figurile 1 si 2 si R=

R(A B C D E ) s(A B C D E)

1 2 3 5 2 1 2 3 5 2

1 4 3 7 2 1 4 3 7 2

1 4 3 7 6 1 4 3 7 6

1 2 3 7 6 1 2 3 5 6

1 2 3 7 2

Figura 1  Figura 2

Sa se calculeze m(r) si m(s).

2. Fie schema bazei de date R= . Aratati ca pentru orice r( R ).

m_R(r) FIX( R).

3. Fie R= si S= . Aratati ca:

R S

FIX(S) FIX (R)

4. Calculati Chase (T ) unde

T. = (A₁ A₂ A₃ A₄ )

  a₁ b₁ a₃ b₂

  b₃ a₂ a₃ a₄

  a₁ b₄ b₅ a₄

Pentru multimile C=

.