DEPENDENTE MULTIVOCE

1. Introducere

Exista situatii in care si in lipsa dependentelor functionale se poate da o descompunere a schemei care micsoreaza redundanta si conserva informatiile.

Se considera schema de relatie R=[UZINA,VANZATOR, PRODUS] notata pe scurt R=[U, V, P] si relatia

r( U V P )

u v p₁

u₁ v₂ p

u v p₂

u₁ v₂ p

u v p₁

Un tuplu t=<u,v,p> din relatia r arata ca uzina u fabrica produsul p si il aprovizioneaza pe vanzatorul v. Se presupune ca o uzina fabrica mai multe produse si aprovizioneaza mai multi vanzatori. Avem doua functii independente, de fabricare si vanzare.

fabricare ( U P ) vanzare(U V )

u p₁ u₁ v₁

u p₂ u₁ v₂

u p₂ u₂ v₂

Evident ca relatia r contine o anumita redundanta. Prin urmare, daca uzina u₁ aprovizioneaza un nou vanzator v , este necesar sa creeze doua tupluri pentru fiecare produs.

Definitia urmatoare a dependentei multivoce apartine lui Fagin si Zaniola / /.

Definitia 1. Fie schema de relatie R [A₁,A ,.,A_n] o partitie [X,Y,Z] a schemei R cu X si Y care nu intersecteaza relatia r(R). Se presupune ca relatia r satisface dependenta multivoca (MV-dependenta) X Y sau X Z daca tuplurile <x,y,z> si <x,y',z'> apartin lui r atunci <x,y',z> si <x,y,z'> apartin lui r.

Pentru relatia r avem U― P si U― V:

daca un vanzator se aprovizioneaza de la uzina el are in vedere toate produsele fabricate de uzina.

daca un produs este fabricat de o uzina el trebuie avut in vedere de toti vanzatorii care se aprovizioneaza de la uzina respectiva.

toate produsele fabricate de o uzina sunt comercializabile de toti vanzatorii care se aprovizioneaza de la uzina.

Dam in continuare o definitie formala:

Definitia 2. Fie schema de relatie R si X,Y R,X Y , Z=R-XY. Schema de relatia R satiface dependenta multivoca (pe scurt: MV-dependenta) X―Y daca:

Orice instanta r(R) si ( ) t t Ir, t (X)=t (X) ( ) t Ir astfel incat t (X)=t (X), t (Y)=t (Y), t (Z)=t (Z) sau

) t t Ir,t (X)=t (X) ( ) t Ir astfel incat t (X)=t (X), t (Y)=t (Y), t (Z)=t (Z).

Relatia urmatoare este un exemplu care satisface definitia de mai sus.

r( X Y Z )

a b c₁

a b₂ c

a b c₂

a b₂ c

Lema 1. Daca relatia r de schema R satisface MV-dependenta X―Y si Z=R-(XY) atunci r satisface X―Z.

Demonstratia rezulta din simetrie. Presupunem ca intersectia lui X cu Y este vida si relatia r(R) satisface X―Y Daca X X, atunci X―YX', daca tuplurile t si t apartin lui r si t (X)=t (X), atunci tuplul t cu t (X)=t (X), t (X)=t (X) si t (X)=t (X). Prin urmare t (YX')=t₁(YX'). Mai departe in locul definitiei initiale o aplicam pe cea modificata.

In definitia MV-depentei X―Y este necesar ca X si Z sa fie de intersectie vida. Aceasta conditie poate fi eliminata din definitie. Fie r(R) care satisface X― Y'. Prin urmare fie Z=R-(XY)=R-(XY') si t , t doua tupluri din r pentru care t (X)=t₂(X). Intrucat X―Y in r exista tuplu t cu t (X)=t (X), t (Y)=t (Y) si t (Z)=t (Z).

Exemplu 1. Relatia introdusa mai jos satisface MV-dependenta AB BC, ea satisface AB―C.

r(A B C D)

a b c d

a b c' d'

a b c d'

a b c' d

a b' c' d

a' b c d'

Sa se cerceteze sensul cazurilor particulare Y si Y― pentru relatia r(R).

Conform ipotezei t( )=1 pentru orice tuplu t. Pentru orice doua tupluri t si t din t t ), daca r satisface T, atunci trebuie sa existe t Ir pentru care t (Y)=t (Y) si t (Z)= t (Z). Prin urmare r este produsul cartezian al proiectiilor p_Y(r) si p_Z(r).   

2. Proprietati ale MV-dependentelor

Vom arata in ce mod MV-dependenta este legata de descompunerea fara pierderi de informatii.

Teorema 1. Fie r relatia de schema R ; X,Y,Z sunt multimi din R, astfel ca Z=R-XY. Relatia r satisface MV-dependenta X―Y daca si numai daca r se descompune fara pierderi de informatii in relatii cu schemele R =XY si R =XZ.

Demonstratie. Presupunem ca r satisface MV-dependentele X―Y. Fie r r), r ( r) si t un tuplu din r r . Atunci din definitia unirii exista tuplurile t I r si

t I r astfel ca t(X)= t (X)= t (X), si t(Z)= t (Z), t(Y)= t (Y). Intrucat r si r sunt proiectii ale relatiei r, trebuie sa existe t si t pentru care t (XY)=t '(XY), t (XY)=t '(XY).

Din MV-dependenta X―Y rezulta ca t trebuie sa apartina lui r, deoarece r trebuie sa contina tuplu t cu t (X)=t (X), t (Y)=t (Y) si t (Z)=t (Z). Din aceste relatii rezulta ca t= t care apartine lui r.

Presupunem ca t se descompune fara pierderi de informatii pe R si R . Fie t si t tuplurile din r pentru care t (X)= t (X), iar r si r sunt definite mai sus. Relatia r contine tuplul t '= t (XY), relatia r tuplu t '=t (XY), deoarece r =r r , atunci r contine tuplul pentru care t(XY)=t (XY) si t(XZ)=t (XY). Tuplul t este rezultatul unirii t si t . Prin urmare t si t verifica dependenta X Y si r satisface X― Y

Teorema 1 da un procedeu de verificare a MV - dependentei X―Y in relatia r. Pentru aceasta proiectam r pe XY si pe X( R - XY ) si unim ; se verifica daca rezultatul coincide cu r. Exista o a doua metoda de verificare a MV-dependentei, unde nu trebuie sa redeca proiectiile si unirile.

Fie Z=R-(XY), R₁=XY, R₂=XZ daca r₁=( r ) si r₂=( r ) atunci r₁r₂ intotdeauna contine r. Fie x o X-valoare, exista c₁ tupluri in r pentru care X-valoarea coincide cu x si c₂ tupluri in r₂ cu aceeasi proprietate.Fie c numarul unor astfel de tupluri in r. Daca pentru orice X-valoare x c= c₁c₂, atunci r= r₁ r₂.

Definitia 3. Fie schema de relatie R si X,Y R,X Y , Z=R-XY. Schema de relatia R satiface dependenta multivoca (pe scurt: MV-dependenta) X―Y daca:

Orice instanta r(R) satisface p_YZ (s_X=x(r))= p_Y (s_X=x(r)) p_Z (s_X=x(r)) pentru valoare x a lui X.

Introducem functia

c_w [X=x](r) care face sa corespunda relatiei r un numar real nenegativ.

c_w [X=x] = |p_w s_X=x(r))|

Definitia 3. Fie relatia de schema R, X si Y doua submultimi distincte si

Z R-XY.Relatia r satisface dependenta multivoca X―Y, daca pentru orice X-valoare x si pentru orice Y-valoare y in r astfel ca x,yIr:

c_Z [X=x](r)= c_Z [XY=xy](r)

Corolarul 1 face legatura intre dependentele functionale si multivoce si se poate deduce urmatoarea consecinta:

Corolar 1. Fie relatia r de schema R si X,Y doua submultimi din R. Daca r satisface F-dependenta X Y, atunci r satisface MV-dependenta X Y

Demonstratie. Din dependenta X Y rezulta ca r poate fi descompusa fara pierderi de informatie in raport cu XY si XZ.

Teorema 2. Fie F o multime de F-dependente pe R. Fie X,Y,Z submultimi ale lui R,unde Z=R-XY. Notam cu X inchiderea lui X in raport cu F. Daca Y X si Z X , atunci exista r(R) care satisface F si nu satisface MV-dependenta X―Y

Demonstratia este analoaga teoremei de completitudine.

Exemplu 2. R=ABCDEI unde F= atunci din F rezulta ca

A BCD si A DE.

3. Axiome de inferenta pentru dependente multivoce

Am definit mai sus clase de denpendente multivoce care sunt consecinte ale unei multimi de F-dependente. Examinam clasa MV-dependentelor care sunt consecinte ale MV- si F-dependentelor.

Primele sase axiome de inferenta introduse mai jos sunt analoage cu axiomele pentru F-dependente, numai primele trei sunt afirmatii identice cu cele de la F-dependente.

Fie r o relatie de schema R si X,Y,Z,W submultimi ale lui R.

M1. Reflexivitate: Relatia r satisface X Y.

M2. Augmentare: Daca r satisface X Y, atunci ea satisface XZ Y, pentru

orice Z R.

M3. Aditivitate: Daca r satiface X Y si X Z atunci ea satisface X YZ.

M4. Proiectivitate: Daca r satisface X Y si X Z atunci ea satisface

X Y Z si X Y-Z.

M5. Tranzitivitate :Daca r satisface X Y si X Z atunci r satisface X Z-Y.

M Pseudotranzitivitate : Daca r satisface X Y si YW Z atunci r satisface

XW Z-YW.

M7. Complementaritate : Daca r satisface X Y si Z=R-XY atunci r satisface

X Z-Y.

Axiomele M1 si M2 rezulta direct din prima definitie a MV dependentelor. Aratam ca axioma M3 este adevarata. Fie relatia r care contine tuplurile t si t pentru care t (X)=t (X). Trebuie sa aratam ca r contine tuplul t astfel ca t(X)=t (X), t(YZ)=t (YZ) si t(U)=t (U) unde U=R-(XYZ). Intrucat r satisface X Y ea trebuie sa contina tuplul t astfel ca : t (X)=t (X), t (Y)=t (Y), t (V)=t (V) unde V=R-(XY). Din relatia X Z rezulta ca exista tuplul t astfel ca: t (X)=t (X), t (Z)=t (Z), t (W)=t (W) unde W=R-(XZ. Luam t=t . Evident t(X)=t (X), t (Z)=t (Z)=t(Z), t (X W)=t (X W)= t (X W)=t(X W) astfel ca t (XZ)=t(XZ).

Intrucat U W V avem t (U)=t (V)=t (V)=t(V). Deoarece R=XYZU, atunci t =t. Axioma M7 rezulta din teorema 1. Axiomele M3 si M7 pot fi folosite la demonstrarea axiomei M4. Daca r satisface X―Y si X―Z atunci conform axiomei M3 X―YZ si conform axiomei M7 r satisface X―V, V=R-(XYZ). Folosind din nou M3 rezulta ca r satisface X―VZ. Din ultima aplicatie a axiomei M7 rezulta ca X―R-(XVX).Prin schimbare si ordonare rezulta M4. R-(XVZ)=R-(XZ)=R-(XZ)=

Y-(XZ)=(Y-Z)-X. Prin urmare r satisface X― (Y-Z)-X, de aici conform lemei 1 rezulta X― Y-Z. Din X―Y cu ajutorul axiomei M7 obtinem X―W, unde W=R-(XY). Combinata cu X―Y-Z cu ajutorul axiomei M3 obtinem X―W(Y-Z). Din nou folosind axioma M7, avem X R-(XW(Y-Z)). Schimband ordinea obtinem :

R-(WX(Y-Z))=R-(X(Y-Z))=R-(X(Y-Z))=Y-(X(Y-Z))=(Y Z)-X.

Prin urmare satisface X― (Y Z)-X si prin urmare X―Y Z. Pentru demonstrarea axiomei M5 la inceput aratam ca daca in r exista tuplurile t si t astfel ca t (X)=t (X), atunci r contine tuplul t astfel ca t(X)=t (X), t(YZ)=t (YZ), t(W)=t (W). Din X Y rezulta ca exista tuplul t pentru care t (X)=t (X), t (Y)=t (Y) si t (V)=t (V), unde V=R-(XY). Prin urmare X―Z rezulta ca exista tuplul t pentru care t (Y)=t (Y), t (Z)=t (Z) si t (U)=t (U), unde U=R-(XZ).

Intrucat pentru fiecare atribut AIX, tuplurile t ,t₂ t au aceleasi valori avem t (X)=t₁(X). Evident t (YZ)=t₁(YZ). Dar, deoarece W U-X V atunci t (W)=t₂(W). Prin urmare t este tuplul cautat. Noi aratam ca r satisface X YZ. Folosind axioma M4 si

X Y obtinem ca X Z-Y.

Exemplul 3. Fie R=ABCDE si F=. Din A― BC cu ajutorul augmentarii obtinem A―DE. Mai departe din tranzitivitate avem A―C. Cu ajutorul axiomei de augmentare obtinem ca DA― C. Prin urmare aplicarea repetata a axiomelor atrage dupa sine AD―BE. Prin urmare F|=AD― BE.

Pentru folosirea combinata exista numai doua axiome

C1. Replicarea : Daca r satisface X Y atunci r satisface si X Y.

C2. Fuzionarea : Daca r satisface X―Y si Z W unde W Y, Y Z= , atunci r satisface X W.

Axioma C1 se poate deduce din corolarul teoremei 1. Demontram corectitudinea axiomei C2. Fie t si t₂ doua tupluri din r, pentru care t (X)=t₂(X). Intrucat X―Y este satisfacuta de r, in r trebuie sa fie tuplu t, astfel ca t(X)=t (X), t(Y)=t (Y) si t(V)=t (V) unde V=R-(XY). Din Y Z= , Z XY rezulta t(Z)=t₂(Z). Conform F-dependentei Z W avem t(W)=t₂(W), totusi W Y, de aici rezulta ca t (W)=t(W)= t (W) si prin urmare r satisface X W.

Exemplul 4. Fie R=ABCDE si F=. Conform axiomei C2 F|=A C.

4. Completitudinea sistemului de inferente multivoce

Ne vom limita la numai formularea rezultatelor despre completitudinea sitemului de inferente pentru MV-dependente, deoarece demonstratia este asemanatoare ca la F-dependente.

Teorema 3. Sistemul de inferente M1-M7 pentru MV-dependente este complet.

Teorema 4. Sistemul de inferente M1-M7, A1-A6 si C1, C2 pentru multimile de F- si MV-dependente este complet.

Din teorema 1 rezulta ca multimea formata dintr-o singura MV-dependenta genereaza numai F-dependente triviale. Adica F-dependentele de forma X Y, unde X contine Y. Aceste observatii rezulta din forma inferentelor. Axiomele A1-A6 pot sa genereze numai dependente triviale M1-M7 si C1 nu pot sa genereze nici o F-dependenta axioma C2 in cazul dependentei triviale este neaplicabila. Axiomele C1 si C2 sunt necesare. Fara axioma C1 inferenta MV-dependentelor dintr-o multime de F-dependente ar fi imposibila.

Nu vom da algoritmi de verificare, de determinare pentru MV-dependente sau pentru F- si MV-dependente care in ambele cazuri au o complexitate polinomiala.

Definitia 4. Fiind data S=, unde U= S₁ S₂ S_p. Se numeste baza minimala de descompunere a multimii S notata mdsb(S) descompunerea T₁,T₂,., T_q a multimii U astfel ca :

S_k I S $ I_k astfel incat S_k=T_j

Nu exista o descompunere cu numar mai mic de elemente care poseda aceasta proprietate. Mdsb(S) este unica.

Exemplul 5. Fie S=. Avem U=ABCDE si mdsb(S)=A,B,C,D,E. Fie F o multime de MV-dependente pe S si X S. Notam G=.

Din constructia lui G rezulta ca mdsb(S) este o submultime a lui G. Daca in G exista multimea Y astfel ca atributele care o compun nu intra in nici o multime oarecare Y din G, atunci conform axiomei M4, in G exista multimile Y = Y -Y si Y =Y Y Baza mdsb(G) consta tocmai in acele multimi nevide din G care nu contin in calitate de submultimi alte submultimi ale lui G. Se observa ca daca X=A₁ A₂ .A_n, atunci toate atributele A₁ A₂ .A_n intra in mdsb(G).

Definitia 5. Fie F,X si G de mai sus. mdsb(G) se numeste baza dependenta de X relativ la F multimea notata DEP(X). Daca X=A₁ A₂ .A_n si DEP(X)= atunci introducem notatia X―Y₁ |Y₂ |.|Y_n

Exemplul Fie F= o multime de MV-dependente pe ABCDE. Daca X=A atunci G= iar DEP(A)=mdsb(G)=