DEPENDENTE MULTIVOCE

6.1. Introducere

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

Se considera schema de relatie R=[UZINA,VÂNZATOR, 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 îl aprovizioneaza pe vânzatorul v. Se presupune ca o uzina fabrica mai multe produse si aprovizioneaza mai multi vânzatori. Avem doua functii independente, de fabricare si v`ânzare.

fabricare ( U P ) vânzare(U V )

u p₁ u₁ v₁

u p₂ u₁ v₂

u p₂ u₂ v₂

Evident ca rela& 656h72g #355;ia r contine o anumita redundanta. Prin urmare, daca uzina u1 aprovizioneaza un nou vânzator v , este necesar sa creeze doua tupluri pentru fiecare produs.

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

Definitia 6.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 vânzator se aprovizioneaza de la uzina el are în vedere toate produsele fabricate de uzina.

daca un produs este fabricat de o uzina el trebuie avut în vedere de toti vânzatorii care se aprovizioneaza de la uzina respectiva.

toate produsele fabricate de o uzina sunt comercializabile de toti vânzatorii care se aprovizioneaza de la uzina.

Dam în continuare o definitie formala:

Definitia 6.2. Fie schema de relatie R si X,Y R,X Y , Z=R-XY. Relatia r(R) satiface dependenta multivoca (pe scurt: MV-dependenta) X―-»Y daca:

(")t t r,t (X)=t (X) ( ) t r astfel încât t (X)=t (X), t (Y)=t (Y), t (Z)=t (Z) sau

")t t r,t (X)=t (X) ( ) t r astfel încât t (X)=t (X), t (Y)=t (Y), t (Z)=t (Z).

Lema 6.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 în locul definitiei initiale o aplicam pe cea modificata.

În 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). Întrucât X―»Y în r exista tuplu t cu t (X)=t (X), t (Y)=t (Y) si t (Z)=t (Z).

Exemplu 6.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 r 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). 

.

6.2. Proprietati ale MV-dependentelor

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

Teorema 6.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 în 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 r si

t r astfel ca t(X)= t (X)= t (X), si t(Z)= t (Z), t(Y)= t (Y). Întrucât 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 6.1 da un procedeu de verificare a MV - dependentei X―»Y în 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₂ întotdeauna contine r. Fie x o X-valoare, exista c₁ tupluri în r pentru care X-valoarea coincide cu x si c₂ tupluri în r₂ cu aceeasi proprietate.Fie c numarul unor astfel de tupluri în r.Daca pentru orice X-valoare x c= c₁c₂, atunci r= r₁ r₂.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 6.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 în r astfel ca x,y r:

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

Corolarul 6.1 face legatura între dependentele functionale si multivoce si se poate deduce urmatoarea consecinta:

Corolar 6.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 în raport cu XY si XZ.

Teorema 6.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 închiderea lui X în 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 6.2. R=ABCDEI unde F= atunci din F rezulta ca

A »BCD si A »DE.

6.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.

M6. 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). Întrucât 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).

Întrucât 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)). Schimbând 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 început aratam ca daca în 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).

Întrucât pentru fiecare atribut A X, 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 6.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 6.1. Demontram corectitudinea axiomei C2. Fie t si t₂ doua tupluri din r, pentru care t (X)=t₂(X). Întrucât X―»Y este satisfacuta de r, în 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 6.4. Fie R=ABCDE si F=. Conform axiomei C2 F|=A C.

6.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 6.3. Sistemul de inferente M1-M7 pentru MV-dependente este complet.

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

Din teorema 6.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 în 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 în ambele cazuri au o complexitate polinomiala.

Definitia 6.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 S $ I_k astfel încât S_k=T_j

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

Exemplul 6.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 în G exista multimea Y astfel ca atributele care o compun nu intra în nici o multime oarecare Y din G, atunci conform axiomei M4, în G exista multimile Y = Y -Y si Y =Y Y Baza mdsb(G) consta tocmai în acele multimi nevide din G care nu contin în 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 în mdsb(G).

Definitia 6.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 6.6. Fie F= o multime de MV-dependente pe ABCDE. Daca X=A atunci G= iar DEP(A)=mdsb(G)=