DEPENDENTE MULTIVALOARE SI DEPENDENTE JONCTIUNE

Modelul relational utilizeaza dependentele pentru exprimarea constrangerilor pe care datele din baza de date trebuie sa le satisfaca. Schema bazei de date relationale este definita de o varietate de constrangeri ce sunt impuse componentelor sale. Dependentele functionale sunt un exemplu de astfel de constrangeri de integritate. Ele au fost studiate detaliat in capitolul 3.

O generalizare a dependentelor functionale, numite dependente multivaloare, a fost descoperita de mai multi cercetatori in domeniu. Cea mai importanta proprietate a dependentei multivaloare consta in faptul ca existenta ei intr-o relatie este o conditie necesara si suficienta pentru ca relatia sa poata fi inlocuita fara pierderi de informatii, independent de extensia curenta, cu doua proiectii ale sale. Aceasta proprietate face ca dependenta multivaloare sa joace un rol important in teoria si practica proiectarii bazelor de date relationale.

O data ce dependentele multivaloare au devenit parte a teoriei relatiilor, o cerinta de baza ce trebuie sa fie satisfacuta este cunoasterea proprietatilor lor si, in particular, metodelor de manipulare. Intrucat dependentele multivaloare sunt o generalizare a celor functionale, metodele aplicate asupra ultimelor pot servi drept ghid in sustinerea acestei cerinte.

Este bine cunoscut ca existenta intr-o relatie a dependentelor functionale implica ca in ea exista dependente functionale aditionale. Aceasta e valabil si pentru dependentele multivaloare. Notiunea de implicare este formalizata in conceptul de reguli de inferenta. Sunt cunoscute multimi inchise si complete de reguli de inferenta pentru dependentele multivaloare.

Dependentele jonctiune sunt o generalizare a dependentelor multivaloare. E cunoscut faptul ca o multime de dependente functionale plus o dependenta jonctiune se considera suficiente pentru exprimarea dependentelor dintre atributele unei scheme a bazei de date.

Acest capitol cuprinde notiuni generale despre dependentele multivaloare, regulile de inferenta, dependentele multivaloare incluse, regulile de inferenta ale dependentelor jonctiune etc.

1. Dependente multivaloare

Definitia 1. Fie relatia r cu schema R si X,Y R. Notam Z=R XY. Vom spune ca relatia r(R) satisface dependenta multivaloare X Y (sau X Y e valida in r(R)), daca pentru orice pereche de tupluri t₁ si t₂ din r(R) ce satisfac t₁[X]=t₂[X] exista in r(R) un tuplu t₃ pentru care au loc egalitatile t₃[X]=t₁[X], t₃[Y]=t₁[Y] si t₃[Z]=t₂[Z].

Remarca. Din proprietatea de simetrie a acestei definitii urmeaza ca in r(R) mai exista un tuplu t₄ ce satisface egalitatile t₄[X]=t₁[X], t₄[Y]=t₂[Y] si t₄[Z]=t₁[Z].

Teorema 1. O dependenta multivaloare X Y e valida in relatia r(R) daca si numai daca X Z e valida in r(R), unde Z = R XY.

Demonstratie. Din remarca definitiei 1 urmeaza ca, daca relatia r(R) satisface dependenta multivaloare X Y, atunci de fiecare data cand t₁[X]=t₂[X] in r(R) exista nu numai un tuplu t₃ ce satisface t₃[X]=t₁[X], t₃[Y]=t₁[Y] si t₃[Z]=t₂[Z], dar si un tuplu t₄ pentru care au loc egalitatile t₄[X]=t₁[X], t₄[Y]=t₂[Y] si t₄[Z]=t₁[Z]. In consecinta, tupluri distincte cu aceleasi X-valori si cu Y-valori (Z-valori) identice trebuie sa aiba diferite Z-valori (Y-valori) pentru a mentine toate tuplurile distincte. Din aceasta proprietate simetrica rezulta ca relatia r(R) satisface dependenta multivaloare X Y daca si numai daca satisface dependenta multivaloare X Z.

Exemplul 1. Relatia r(ABCD) din fig.1 satisface dependenta multivaloare BC A. In relatia r(ABCD) e valida de asemenea dependenta multivaloare BC D. Daca, insa, din relatia r(ABCD) este eliminat un tuplu, atunci dependentele multivaloare BC A si BC D devin invalide in r(ABCD).

In definitia 1 nu s-au pus conditii asupra multimilor X si Y. Deci X Y in caz general. Determinatul Y poate fi redus. Sa demonstram ca varianta redusa, X Y X, e echivalenta dependentei X Y.

Teorema 2. Dependenta functionala X Y e valida in relatia r(R), daca si numai daca X Y X e valida in r(R).

Demonstratie. Necesitatea. Fie relatia r(R) satisface dependenta multivaloare X Y. Notam Y¹ = Y X. Atunci Z= R XY = R XY¹. Fie t₁ si t₂ doua tupluri cu X-valori egale, adica t₁[X] = t₂[X]. Fiindca X Y e valida in r(R), atunci in r trebuie sa existe un tuplu t₃ ce satisface t₃[X]=t₁[X], t₃[Y]=t₁[Y] si t₃[Z] = t₂[Z]. Egalitatea t₃[Y] = t₁[Y] implica egalitatea t₃[Y¹] = t₁[Y¹]. Prin urmare, relatia r satisface si dependenta multivaloare X Y¹.

Suficienta. Fie r(R) satisface dependenta multivaloare X Y¹, unde Y¹ = Y X si fie X¹ X. Sa aratam ca dependenta X Y¹X¹ e valida in r(R). Intrucat r satisface X Y¹ si daca t₁, t₂Ir si t₁[X] = t₂[X], atunci exista un tuplu t₃, pentru care t₃[X] = t₁[X], t₃[Y¹] = t₁[Y¹] si t₃[Z] = t₂[Z]. Din X¹ X  si t₃[Y¹] = t₁[Y¹] urmeaza t₃[Y¹X¹] = t₁[Y¹X¹]. Deci X Y¹X¹.

Exemplul 2. Relatia r(ABCD) din fig.1 satisface dependenta multivaloare BC A. Conform teoremei 2 in r e valida si dependenta multivaloare BC AB.

Teorema ce urmeaza poate fi considerata o metoda de verificare daca o dependenta multivaloare e valida intr-o relatie.

Teorema 3. Fie relatia r(R), X,Y R si Z = R XY. Dependenta multivaloare X Y e valida in r(R) daca si numai daca r este jonctiunea proiectiilor sale p_XY(r) si p_XZ(r).

Demonstratie. Necesitatea. Fie dependenta multivaloare X Y e valida in r(R) si fie r₁=p_XY(r), r₂=p_XZ(r). Fiindca intotdeauna are loc corelatia r(R) r₁ |x|r₂, pentru a demonstra necesitatea, e de ajuns sa aratam ca orice tuplu t din jonctiunea r₁ |x|r₂ este si in r(R), adica r₁ |x|r₂ r(R). Fie t un tuplu in r₁ |x|r₂. Atunci r₁ si r₂ trebuie sa contina corespunzator tuplurile t₁ si t₂ incat t[X] = t₁[X] = t₂[X], t[Y] = t₁[Y] si t[Z] = t₂[Z]. Intrucat r₁ si r₂ sunt proiectii ale relatiei r, atunci r contine tuplurile t₁¹ si t₂¹ pentru care t₁[XY]=t₁¹[XY] si t₂[XZ]=t₂¹[XZ]. In r este un tuplu t₃ (dat fiind faptul ca X Y e valida in r) ce satisface t₃[X] = t₁¹[X], t₃[Y] = t₁¹[Y] si t₃[Z] = t₂¹[Z]. Se vede ca acest tuplu t₃ este t.

Suficienta. Presupunem acum ca relatia r se descompune in doua relatii r₁ si r₂ fara pierderi. Sa aratam ca pentru orice doua tupluri t₁¹ si t₂¹ ce satisfac t₁¹[X] = t₂¹[X] exista un tuplu t incat t[X] = t₁¹[X], t[Y] = t₁¹[Y] si t[Z] = t₂¹[Z], adica in r e valida dependenta multivaloare X Y.

Fie t₁¹ si t₂¹ doua tupluri in r(R). Intrucat r(R) se descompune fara pierderi asupra XY si XZ (adica r=p_XY(r)|x|p_XZ(r)), atunci in r₁ si r₂ se gasesc, respectiv, tuplurile t₁ si t₂ si t₁ = t₁¹[XY], t₂ = t₂¹[XZ]. Fiindca r = r₁ |x|r₂ , r contine un tuplu t ce satisface t[XY]=t₁[XY] si t[XZ]=t₂[XZ]. Intrucat tuplurile t₁¹, t₂¹ si t satisfac definitia 1 relatia r(R) satisface dependenta multivaloare X Y.

Din teorema 3 se poate face urmatoarea concluzie.

Concluzie. Relatia r(R) se descompune fara pierderi in relatiile r₁(R₁) si r₂(R₂) daca si numai daca R₁ R₂ R₁ (sau R₁ R₂ R₂).

Este ineficienta utilizarea metodei din aceasta teorema pentru a verifica daca o relatie satisface sau nu o dependenta multivaloare. Testarea necesita doua proiectii si o jonctiune. Sa examinam un alt procedeu de verificare, daca o dependenta multivaloare e valida intr-o relatie.

Fie relatia r(R) satisface dependenta multivaloare X Y, atunci conform teoremei 3 r(R) = p_XY(r) |x|p_XZ(r), unde Z = R XY.

Expresiile |p_XY s_X=x(r))| si |p_XZ s_X=x(r))| reprezinta numerele de tupluri in proiectiile relatiei r asupra multimilor XY si XZ, corespunzator, pentru X-valoarea data egala cu x. Este evident ca, daca relatia r se descompune fara pierderi in relatiile p_XY(r) si p_XZ(r), atunci

s_X=x(r)| = |p_XY s_X=x(r))| p_XZ s_X=x(r))|.   (1)

Intrucat |p_XW s_X=x(r))| = |p_W s_X=x(r))|, atunci egalitatea (1) poate fi simplificata:

s_X=x(r)| = |p_Y s_X=x(r))| p_Z s_X=x(r))|.   (2)

Aceasta procedura de verificare a validitatii unei dependente multivaloare este mai putin laborioasa decat precedenta. Ea presupune sortarea tuplurilor dupa X-valori, apoi pentru orice X-valoare x se testeaza egalitatea de mai sus.

Exemplul 3. Relatia r(ABCD) din fig.1 satisface teorema 3. Proiectiile p_BCA(r) si p_BCD(r) sunt prezentate in fig.2. Jonctiunea lor este egala cu r(ABCD). Atunci egalitatea (2) e satisfacuta fiindca:

p_A s_BC=b1c1(r))|=|p_D s_BC=b1c1(r))|=2, si |(s_BC=b1c1(r)| = 4

si

p_A s_BC=b1c2(r))|=|p_D s_BC=b1c2(r))|=2, si |(s_BC=b1c2(r)| =

Proprietatea de mai sus poate fi utilizata intr-o noua definitie a dependentei multivaloare.

Definitia 2. Fie r o relatie asupra schemei R, X,Y R si Z = R XY. Relatia r(R) satisface dependenta multivaloare X Y, daca pentru orice X-valoare x si XZ-valoare xz e satisfacuta egalitatea p_Y s_X=x(r)) = p_Y s_XZ=xz(r)).

Cu alte cuvinte, in cadrul relatiei r(R) exista o dependenta multivaloare X Y, daca si numai daca multimea valorilor lui Y corespunzatoare unei perechi xz depinde numai de X-valoarea x nu si de valoarea lui Z.

2. Reguli de inferenta ale dependentelor multivaloare

Primele sase reguli sunt similare regulilor de inferenta omonime ale dependentelor functionale, insa numai primele trei contin aceleasi asertiuni.

Fie o relatie r cu schema R si W,X,Y,Z R.

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

Validitatea acestei reguli urmeaza din definitia dependentei multivaloare.

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

Validitatea acestei afirmatii reiese din definitia 1 si teorema 2.

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

Demonstratie. Fie in r sunt doua tupluri t₁ si t₂ ce au X-valori egale, t₁[X]=t₂[X]. Trebuie aratat ca in r exista un tuplu t, incat t[X] = t₁[X], t[YZ] = t₁[YZ] si t[U] = t₂[U], unde U=RXYZ.

Intrucat r(R) satisface dependenta X Y, atunci r contine un tuplu t₃ si t₃[X] = t₁[X], t₃[Y] = t₁[Y], t₃[V] = t₂[V] pentru orice t₁ si t₂ ce satisfac egalitatea t₁[X]=t₂[X], unde V=RXY. Acelasi rationament este si pentru X Z: exista in r(R) un tuplu t₄ care satisface t₄[X] = t₁[X], t₄[Z] = t₁[Z] si t₄[W] = t₃[W] (fiindca t₁[X] = t₃[X]), unde W = R XZ.

Sa aratam ca t = t E evident ca t[X] = t₄[X]. De asemenea t₄[Z] = t₁[Z] = t[Z]. Dar t₄[Y W] = t₃[Y W] = t₁[Y W] = t[Y W] si atunci t₄[YZ] = t[YZ]. Din U W V, urmeaza t₄[U] = t₃[U] = t₂[U] = t[U]. Intrucat R=XYZU, atunci t₄=t.

DM Regula proiectivitatii. Daca X Y si X Z, atunci X Y Z, X Y Z.

Demonstratie. Conform regulii DM3, X Y si X Z implica X YZ. Aplicand teorema 1 asupra dependentei multivaloare X YZ, obtinem X R XYZ. Aplicand regula DM3 asupra dependentelor X R XYZ si X Z, obtinem X (R XYZ)Z. Dar conform teoremei 1, X (R XYZ)Z implica X R X(R XYZ)Z. Determinatul ultimei dependente se simplifica in felul urmator (vezi fig. 3): R X(R XYZ)Z = R X(R Y)Z = Y XZ = (Y Z) X. Deci X (Y Z) X si conform teoremei 2 dependenta X Y Z este valida in r(R).

Am demonstrat validitatea regulii: daca X Y si X Z, atunci X Y Z.

Sa aratam acum ca, daca X Y si X Z, atunci X Y Z.

Dependenta X Y implica dependenta X R XY. Combinand, conform regulii DM3, dependentele X Y Z si X R XY, obtinem X (R XY)(Y Z). Aplicand teorema 1 asupra ultimei dependente multivaloare, obtinem X R X( R XY)(Y Z). Sa examinam partea dreapta a dependentei multivaloare obtinute, utilizand diagrama din fig.3.

R X( R XY)(Y Z) = R X( R Y)(Y Z) = Y X(Y Z) = (Y Z) X.

Prin urmare, relatia r(R) satisface dependenta multivaloare X (Y Z) X si, conform teoremei 2, satisface dependenta X Y Z.

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

Demonstratie. Daca vom arata ca X YZ e valida in relatia r, atunci asupra acestei dependente si dependentei X Y poate fi aplicata regula DM4, pentru a obtine dependenta X YZ Y sau X Z Y.

Notam W=R XYZ si sa aratam ca X Y si Y Z implica X YZ. Adica, daca in r sunt doua tupluri t_1, t₂ si t₁[X] = t₂[X], atunci r contine un tuplu t ce satisface egalitatile t[X] = t₁[X], t[YZ] = t₁[YZ] si t[W] = t₂[W].

Intrucat dependenta X Y e valida in r, relatia r contine un tuplu t₃ ce satisface t₃[X] = t₁[X], t₃[Y] = t₁[Y] si t₃[V] = t₂[V], unde V = R XY. Dar dependenta Y Z presupune ca in r este un tuplu t₄ ce satisface conditiile t₄[Y]=t₁[Y], t₄[Z] = t₁[Z] si t₄[U] = t₃[U]., unde U = R YZ.

Sa aratam ca tuplul t₄ este tuplul cautat t. Intrucat t₁[X]=t₂[X] = t₃[X] = t₄[X] e evident ca t₄[YZ] = t₁[YZ]. Dat fiind faptul ca t₄[U]=t₃[U] si W U X, atunci t₄[W] = t₃[W]. Din t₃[V] = t₂[V] si (U X) V reiese ca t₃[W] = t₂[W]. Deci, tuplul t₄ este cel cautat.

Fig. 3. - R, - X, - Y, - Z.

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

Demonstrarea acestei reguli e similara regulii tranzitivitatii si se propune in calitate de exercitiu.

DM7. Regula complementarii. Daca X Y, atunci X Z, unde Z = R XY.

Validitatea acestei reguli este demonstrata de teorema 1.

In fig.4 sunt prezentate regulile de inferenta ale dependentelor multivaloare.

Dupa cum s-a observat din demonstrarile validitatii regulilor de inferenta, unele reguli se pot deduce din celelalte. Similar multimii de reguli , pentru dependentele functionale, exista submultimi de reguli pentru dependentele multivaloare, din care se deduc celelalte.

Teorema Regulile DM3, DM4 si DM6 se deduc din regulile DM1, DM2, DM5 si DM7.

Demonstratie. Sa aratam validitatea regulii DM3 utilizand DM1, DM2, DM5, DM7, adica |- X YZ. Intr-adevar:

m₁:=X Z     (data),

m₂:=X XZ   (DM2:m₁),

m₃:=X Y     (data),

m₄:=XZ YZ    (DM2:m₃),

m₅:=XZ R XYZ    (DM7:m₄),

m₆:=X R XYZ    (DM5:m₂,m₅ si fiindca (RXYZ)XZ = RXYZ)),

m₇:=X R X(R XYZ) (DM7:m₆).

Din fig.3 se vede ca R X(R XYZ) = YZ, deci m₇=X YZ.

Sa demonstram ca regula DM4 urmeaza din DM1, DM2, DM5, DM7. Validitatea expresiei |- este confirmata de urmatoarea consecutivitate de inferenta.

m₁:=X Y     (data),

m₂:=X Z     (data),

m₃:=X R XY     (DM7:m₁),

m₄:=X Z(R XY)   (DM3:m₂, m₃),

m₅:=X Y Z    (DM7:m₄ (vezi fig.3.)),

m₆:=X (YZ)(RXY)=

X R (X Y)    (DM3:m₃, m₅ (vezi fig.3.)),

m₇:=X X Y (DM7:m₆).

Intrucat regula DM3 urmeaza din DM1, DM2, DM5 si DM7 substituirea dependentelor m₄ si m₆ cu consecutivitati de inferenta corespunzatoare se propune in calitate de exercitiu.

Si, in sfarsit, sa aratam ca pseudotranzitivitatea, DM6, urmeaza din DM1, DM2, DM5, DM7. Pentru aceasta vom defini o consecutivitate de inferenta pentru a arata validitatea expresiei |-XW Z YW, aplicand doar regulile DM2 si DM5.

m₁:=X Y     (data),

m₂:=XW YW     (DM2:m₁),

m₃:=YW Z (data),

m₄:=XW Z YW    (DM5:m₂, m₃).

3. Reguli de inferenta mixte

Fie M o multime de dependente functionale si multivaloare asupra schemei R si m o dependenta functionala sau multivaloare. Sunt reguli de inferenta ce pot fi utilizate pentru a verifica daca M|=m.

Fie relatia r(R) si W,X,Y,Z R.

DFM1. Regula replicarii. Daca X Y, atunci X Y.

Validitatea acestei reguli este evidenta. Apeland la definitia 2 a dependentei multivaloare are loc egalitatea p_Y s_X=x(r)) = p_Y s_XZ=xz(r)), unde Z = R XY, fiindca dependenta functionala presupune ca pentru orice X-valori egale corespund Y-valori egale ale tuplurilor. Deci valorile pe care le primeste atributul Z sunt imateriale.

Dependenta functionala reprezinta un tip particular de dependenta multivaloare, pentru care multimea valorilor dependente este constituita dintr-o singura valoare, adica p_Y s_XZ=xz(r)) este o relatie ce contine nu mai mult de un tuplu.

DFM2. Regula coalescentei. Daca X Y si Z W, unde W Y si Y Z= , atunci X W.

Demonstratie. Deoarece X Y si daca in r sunt doua tupluri t_1, t₂, pentru care t₁[X] = t₂[X], atunci in r exista un tuplu t₃ ce satisface egalitatile t₃[X] = t₁[X], t₃[Y] = t₁[Y] si t₃[RXY] = t₂[R XY]. Sa observam ca, deoarece Y Z= , avem Z X(RXY) si intrucat t₃[X] = t₁[X] = t₂[X], rezulta ca t₃[Z] = t₂[Z].

Conform dependentei functionale Z W avem t₃[W]=t₂[W]. Insa W Y, de unde urmeaza ca t₃[W]=t₁[W]=t₂[W] si prin urmare dependenta functionala X W e valida in r.

In fig.5 sunt prezentate regulile mixte de inferenta.

Definitia 3. Fie relatia r(R) si X,Y R. Dependenta multivaloare X Y se numeste triviala, daca X Y sau XY=R.

Astfel, regula de inferenta DM1, genereaza numai dependente multivaloare triviale.

Aici ne vom limita numai la formularea unor rezultate despre completitudinea regulilor de inferenta fara a aduce demonstrarile corespunzatoare.

Teorema Regulile DM1-DM7 formeaza o multime completa de reguli de inferenta a dependentelor multivaloare.

Teorema 5. Sistemul de reguli DF1, DF2, DF5, DM1, DM2, DM5, DM7, DFM1, DFM2 formeaza o multime inchisa si completa de reguli de inferenta a dependentelor functionale si multivaloare.

Problema calitatii de membru

Fie M o multime de dependente functionale si multivaloare si m o dependenta functionala sau multivaloare. Deseori e necesar de determinat daca urmeaza logic dependenta m din M. Aceasta problema se numeste problema calitatii de membru (membership problem). Bineinteles ca asemanator cu cazul numai dependentelor functionale calcularea M⁺, adica a multimii tuturor dependentelor ce se deduc din M, este o procedura destul de laborioasa. Procesul necesita un timp care depinde exponential de dimensiunile multimii M. Similar notiunii de inchidere a unei multimi de atribute in raport cu o multime de dependente functionale, pentru multimea M se introduce notiunea de baza a dependentelor (dependency basis).

Definitia Fie relatia r cu schema R, o multime M de dependente multivaloare si functionale si X R. Baza dependentelor a multimii de atribute X, notata cu DEP(X), in raport cu M este o partitie a lui R: DEP(X) = ce satisface

X W_i IM⁺, 1 i k

si

X YIM⁺, daca si numai daca Y este uniunea a unor multimi W_i din DEP(X).

Sa remarcam ca regula proiectivitatii pentru dependentele multivaloare este mai slaba decat omologul sau pentru dependentele functionale. Proiectivitatea pentru dependentele functionale ne spune ca, daca dependenta X Y e valida intr-o relatie, atunci e valida in aceasta relatie si dependenta X A, pentru orice AIY. Regula proiectivitatii pentru dependentele multivaloare ne permite sa spunem ca, daca X Y e valida intr-o relatie, atunci dependenta X A e valida in aceeasi relatie numai daca exista in schema relatiei o multime de atribute Z ce satisface conditiile: dependenta X Z e valida si sau Z Y=A, sau Y Z=A.

Cu toate acestea regulile aditivitatii (DM3) si proiectivitatii (DM4) ne permit sa formulam urmatoarea teorema despre multimea de atribute Y, ca Y sa depinda de o multime de atribute X, adica X Y. Aceasta teorema sta la temelia notiunii de baza a dependentelor si a algoritmului de calculare a bazei dependentelor descris ceva mai jos.

Teorema 6. Fie relatia r(R) si X R. Multimea de atribute R X poate fi partitionata in submultimi disjuncte W₁,,W_k, incat pentru Y R X are loc X Y atunci si numai atunci cand Y este uniunea a unor multimi W_i, 1 i k.

Demonstratie. La inceput fie ca avem o singura submultime constituita din atributele R X. Presupunem ca la un oarecare pas de partitionare am obtinut submultimile W₁,,W_m si e valida dependenta X W_i, 1 i m. Daca X Y, dar Y nu este uniunea unor W_i, atunci substituim toate multimile W_i care satisfac expresiile W_i Y si W_iY , cu multimile W_i Y si W_i Y, respectiv. Conform regulii proiectivitatii, dependentele X W_i Y si X W_iY sunt valide in r(R). Fiindca o multime finita de atribute nu poate fi partitionata la infinit, in cele din urma, vom avea o partitie incat Y din dependenta X Y, va fi uniunea unor submultimi W_i. Conform regulii aditivitatii, X va determina uniunea oricarei submultimi din partitie.

Remarca. Dependentele multivaloare triviale X Y, unde Y X, ce se obtin din regula reflexivitatii nu sunt considerate in teorema de mai sus. Din definitia bazei dependentelor multimii de atribute X urmeaza ca DEP(X) contine si toate atributele singulare A, unde AIX.

Algoritmul DEPBASIS (r, x, m, dep(x))

Intrare: R - o schema relationala;

X - o multime de atribute;

M - o multime de dependente functionale si multivaloare definite pe schema R.

Iesire: DEP(X) - baza dependentelor multimii X in raport cu M.

begin

DEP(X):= ( unde A₁ . A_n=X);

W₁=R X;

k:=1;

for i=1 until k do

while S TIM & S W_i= & T W_i W_i do

begin

k:=k+1;

W_k:= T W_i;

W_i:= W_i W_k;

end

DEP(X):=DEP(X)

return (DEP(X));

end

Algoritmul DEPBASIS construieste baza dependentelor pentru o multime data de atribute X in raport cu o multime de dependente M si este de complexitate polinomiala.

Exemplul Fie R=ABCDEFGHI, X=HI si

M=. Sa se calculeze DEP(X).

La inceput, conform liniilor 0,1,2,3 ale algoritmului, sunt setate urmatoarele valori pentru DEP(HI), W₁, k si i:

DEP(HI)=,

W₁=ABCDEFG,

k=1, i=1.

Variabila k indica numarul de blocuri, iar i blocul curent. Conform liniei 4 a algoritmului, vom considera pe rand dependentele din M in privinta satisfacerii conditiilor corespunzatoare. Fiindca i=1, este selectat blocul de atribute W₁. Pentru W₁, dependenta m₁ satisface conditiile liniei 4: HI W₁= si A W₁ W₁, unde HI si A sunt, corespunzator, determinantul si determinatul dependentei m₁. Deci, conform liniilor 5-7 pentru k, W₂ si W₁ sunt setate urmatoarele valori:

k=2,

W₂=A,

W₁=BCDEFG.

Pentru blocul W₁ dependenta m₄ e prima care satisface conditiile din linia 4 (dependenta m₅, de asemenea, satisface). Prin urmare, dupa executarea liniilor 5-7, k, W₃ si W₁ obtin valorile:

k=3,

W₃=BCD,

W₁=EFG.

Blocul W₂ nu e satisfacut de nici o dependenta. El va intra in DEP(HI). Atunci, in linia 3 variabila i creste cu o unitate, adica i=2. Dar pentru W₂ nu sunt dependente in M ce satisfac conditiile liniei 4 si atunci i creste cu o unitate, devenind 3. Pentru W₃ exista dependenta m₂. Prin urmare,

k=4,

W₄=B,

W₃=CD.

Blocul W₃ nu e satisfacut de nici o dependenta si atunci i devine egal cu  Pentru blocul W₄, de asemenea, nu exista nici o dependenta. Aici generarea blocurilor sfarseste, si in final vom obtine:

DEP(HI)==.

Exemplul 5. Fie R si M din exemplul  Sa se confirme sau sa se infirme ca:

(a)   M|=HI AB,

(b)   M|=HI H,

(c)   M|=HI ABC.

Pentru a verifica daca X Y, se deduce din M, conform definitiei bazei dependentelor, Y trebuie sa fie uniunea unor multimi din DEP(X). In cazul nostru, DEP(HI)=. Deci:

(a)   M|=HI AB,

(b)   M|=HI H,

(c)   M HI ABC.

5. Acoperiri nonredundante cu dependente multivaloare

Ca si in cazul dependentelor functionale, o multime de dependente multivaloare este redundanta, daca cel putin una din dependente este derivabila din celelalte. Vom spune, de asemenea, ca aceasta dependenta este redundanta in multimea data. O acoperire nonredundanta a unei multimi de dependente  este o multime nonredundanta echivalenta. Problema construirii acoperirilor nonredundante pentru dependentele multivaloare se solutioneaza similar acoperirilor nonredundante ale dependentelor functionale.

Fie M o multime de dependente multivaloare. O acoperire nonredundanta a multimii M se construieste de urmatoarea procedura simpla. Se selecteaza o dependenta din M. Daca ea se deduce din celelalte dependente multivaloare, atunci se elimina din M. Acest proces continua pana nu poate fi gasita nici o dependenta redundanta. Fiindca in acest proces fiecare dependenta multivaloare se examineaza o singura data, complexitatea acestui proces este proportionala complexitatii construirii multimii DEP(X) inmultita la numarul de dependente in M.

Un proces similar poate fi aplicat asupra unei multimi de dependente functionale si multivaloare. Dar trebuie mentionat ca in acest caz ordinea, in care dependentele sunt examinate, determina care dependente vor ramane in acoperirea nonredundanta. Intuitiv, se observa ca pentru utilizatori (de asemenea si pentru SGBD) dependentele functionale poarta mai multa informatie decat dependentele multivaloare. De aceea e rezonabil pentru eliminare mai intai de examinat dependentele multivaloare.

Fie F si M multimi de dependente functionale si multivaloare, respectiv. Fie F¹ o acoperire nonredundanta a tuturor dependentelor functionale din (F M)⁺. Orice dependenta functionala din (F M)⁺ poate fi dedusa din F¹ cu algoritmul MEMBERSHIP. Apoi se elimina dependentele redundante multivaloare din F¹ M pentru a obtine F¹ M¹. Orice dependenta multivaloare din (F M)⁺ = (F¹ M¹)⁺ poate fi dedusa din F¹ M¹, utilizand numai algoritmul DEPBASIS.

Sa mentionam ca F¹ M¹ nu este neaparat nonredundanta, fiindca unele dependente functionale pot deveni redundante in F¹, fiindca dependentele multivaloare M¹ n-au fost considerate cand se construia F¹.

De asemenea F nu este neaparat o acoperire pentru dependentele functionale din (F M)⁺. Regulile DFM1 si DFM2 pot deduce dependente functionale noi ce pot fi adaugate la F. Dar aceasta metoda e destul de ineficienta.

Exista metode mai eficiente de generare a astfel de acoperiri ale dependentelor functionale fiind prezente si dependente multivaloare. Dar discutiile asupra algoritmilor eficienti depaseste cadrul acestei lucrari.

6. Dependente multivaloare incluse

Vom considera o generalizare a clasei dependentelor multivaloare care se numeste dependente multivaloare incluse (embedded multivalued dependencies).

Definitia 5. Fie relatia r asupra multimii de atribute R si R¹ R, X,Y R¹. Dependenta X Y se numeste multivaloare inclusa, daca X Y este dependenta multivaloare in p_R (r).

Este evident din definitie ca orice dependenta multivaloare este dependenta multivaloare inclusa. Exemplul de mai jos arata ca afirmatia inversa e gresita.

Exemplul 6. Consideram relatia r(ABCD) si proiectiile ei p_ABC(r) si p_ABD(r) din fig.6. Proiectiile p_ABC(r) si p_ABD(r) satisfac respectiv dependentele A C si A D. Conform regulii complementarii (DM7), ambele proiectii satisfac dependenta A B. In acelasi timp relatia r(ABCD) nu satisface dependenta A B, deci si A CD nu e valida in r.

Trebuie mentionat ca nu exista o multime completa de reguli de inferenta pentru dependentele multivaloare incluse.

7. Dependente multivaloare noncontradictorii

Definitia 6. Fie o multime M de dependente multivaloare definite pe schema R. Vom spune ca dependenta multivaloare X Y din M separa doua atribute A si B, daca unul din atribute, fie A, este in Y, iar B este in R XY. Multimea M de dependente multivaloare separa o multime de atribute V, daca M separa doua atribute din V.

Exemplul 7. Fie schema R=ABCD. Dependenta AB C separa atributele C si D. Similar, dependenta multivaloare CD A separa A si B. Daca schema R=ABCD e proiectata in baza dependentei AB C in doua subscheme ABC si ABD, atunci in ele sunt valide doar dependentele multivaloare AB C si AB D, respectiv. Nici intr-o schema nu e valida dependenta CD A.

Problema descrisa in exemplul de mai sus e cunoscuta sub denumirea de problema a separarii determinantilor.

Definitia 7. Fie determinantii X,Y a doua dependente multivaloare si fie DEP(X), DEP(Y). Determinantii X si Y sunt noncontradictorii (conflict free), daca

DEP(X) = ,

DEP(Y) = ,

unde DEP(X Y) si Z_x X = Z_y Y. Vom spune ca o multime M de dependente multivaloare este noncontradictorie, daca sunt noncontradictorii determinantii ai oricaror doua dependente din M.

Din definitiile 6 si 7, urmeaza ca multimea M de dependente multivaloare este noncontradictorie, daca nici o dependenta din M nu separa determinantul altei dependente multivaloare din M.

Exemplul 8. Fie R = ABCDEF si M = . Sa se arate ca multimea M de dependente multivaloare e noncontradictorie.

Trebuie sa aratam ca orice pereche din multimea de determinanti este noncontradictorie. Intr-adevar, DEP(B) B = , unde X = B, X₁ = A, X₂ = C, Z_x=D, Y₁ = E, Y₂ = F; DEP(D) D = , unde Y = D, Y₁ = E, Y₂ = F, Z_y = B, X₁ = A, X₂ = C. Intrucat X Y = B D = si DEP( , atunci DEP(B) DEP(D) DEP(B D). Este satisfacuta si conditia Z_x X = Z_y Y, fiindca Z_x X= si Z_y Y = . Prin urmare, B si D sunt determinanti noncontradictorii. Similar poate fi aratat ca sunt noncontradictorii si perechile B, E si D, E. Verificarea acestor din urma se lasa in calitate de exercitiu.

Exemplul 9. Fie R = ABCD si M = . Atunci DEP(AB)=,   DEP(CD) = . Definitia 7 nu e satisfacuta si, prin urmare, multimea M de dependente multivaloare e contradictorie.

Unii cercetatori afirma ca, daca o multime de dependente multivaloare reflecta o parte a lumii reale, atunci multimea neaparat este noncontradictorie. Dar daca multimea specificata nu e noncontradictorie, atunci inseamna ca o parte de semantica a lumii reale nu a fost capturata.

8. Dependente jonctiune

Definitia 8. Fie U multimea universala de atribute si fie relatiile r₁, , r_m definite pe schemele R₁,,R_m, respectiv, unde R_i U, 1 i m. Jonctiunea relatiilor r₁, , r_m, notata cu |x|(r₁,,r_m), este o relatie definita pe schema U¹=R₁R_m U:

|x|(r₁, , r_m)=.

De notiunea jonctiune |x|(r₁, , r_m) a relatiilor r₁,,r_m e strans legata notiunea de dependenta jonctiune asupra U¹, care este o constrangere asupra U¹ de forma |x|(R₁,,R_m). Vom spune ca dependenta jonctiune este inclusa daca U¹ U. Daca U¹ = U, vom spune simplu dependenta jonctiune.

Definitia 9. Vom spune ca relatia r(U) satisface dependenta jonctiune |x|(R₁,,R_m) sau dependenta jonctiune |x|(R₁R_m) e valida in r(U), daca r(U) se descompune fara pierderi pe schemele R₁,,R_m, adica

r(U) = |x|(p_R1(r), , p_Rm(r))   (3)

Exemplul 10. Relatia r(ABC) satisface (vezi relatia si proiectiile corespunzatoare in fig.7) dependenta jonctiune |x|(AB, AC, BC), fiindca r(ABC) = |x|(p_AB(r), p_AC(r), p_BC(r)).

O conditie necesara, ca egalitatea (3) sa fie satisfacuta, este U=R₁R_m.

Este evident ca dependenta de jonctiune inclusa este o generalizare a dependentei jonctiune. La randul sau, apeland la teorema 3, despre conditia necesara si suficienta ca o relatie sa se descompuna fara pierderi in doua proiectii, conchidem ca dependenta jonctiune este o generalizare a dependentei multivaloare. Intr-adevar, teorema 3 ne spune ca r(R) satisface dependenta multivaloare X Y, atunci si numai atunci cand r se descompune fara pierderi pe schemele XY si XZ, unde Z = R XY. Conditia coincide cu definitia dependentei jonctiune |x|(XY, XZ).

9. Tablouri

Vom descrie o metoda tabelara de testare a dependentei jonctiune, bazata pe notiunea de tablou. Tabloul, de fapt este o relatie, cu numai o singura deosebire - in loc de valori tuplurile contin variabile. Variabilele sunt luate din doua multimi: multimea variabilelor distincte si multimea variabilelor nondistincte. Variabilele distincte sunt formate din litera a cu indice, iar cele nondistincte din litera b cu doi indici. Multimea de atribute ce denumesc coloanele este schema tabloului. O variabila corespunde unei singure coloane. O coloana nu poate avea mai mult de o variabila distincta.

Definitia 10. Fie o dependenta jonctiune |x|(R₁,,R_m). Tablou al dependentei |x|(R₁,,R_m) este o relatie ce are un nume (fie tab) si |R₁R_m| = |U| coloane, notate cu atributele din U, si m tupluri cate unul pentru fiecare schema R_i, 1 i m. Tuplul t_i contine in coloana A_j variabila distincta a_j, daca A_j apartine lui R_i. Celelalte componente ale tuplului t_i sunt variabile nondistincte b_ij ce nu se repeta in alt tuplu. Deci t_i[A_j] = a_j, daca A_jIR_i si t_i[A_j] = b_ij, daca A_j R_i.

Exemplul 11. Fie dependenta jonctiune |x|(AB,BC,ACD). Tabloul acestei dependente arata ca in fig.8.

Tuplurile intr-un tablou pot fi transformate conform unor reguli ce corespund anumitor clase de dependente: functionale si jonctiune. Scopul unor astfel de transformari consta in obtinerea unui tuplu alcatuit numai din variabile distincte. Tuplul format exclusiv din variabile distincte se numeste tuplu-scop. Daca in urma transformarilor tabloul contine tuplul scop, atunci dependenta jonctiune e valida, adica jonctiunea este fara pierderi. Sunt cunoscute doua tipuri de reguli de transformare a tabloului: F-reguli si J-reguli.

F-reguli. Fie tab un tablou a unei dependente jonctiune si J o multime de dependente jonctiune, multivaloare si functionale. Pentru orice dependenta functionala X Y din J modificarea tabloului tab se produce in felul urmator. In tab se cauta tuplurile ce coincid pe atributele din X. Fiind descoperite astfel de tupluri, se egaleaza variabilele atributelor din Y. Fie t_i[X] = t_j[X] si pentru AIY   t_i[A] = n , t_j[A] = n . Atunci,

(a)   daca una din variabilele n si n este distincta, atunci variabila nondistincta e substituita de cea distincta;

(b)   daca ambele variabile sunt nondistincte, atunci variabila cu indice mai mare e substituita de variabila cu indice mai  mic.

J-reguli. Fie tab un tablou determinat de dependenta jonctiune |x|(R₁,,R_m) si fie J o multime de dependente jonctiune, multivaloare si functionale. Pentru orice dependenta jonctiune |x|(S₁,,S_k) din J la tabloul tab se adauga tuplul t (daca el nu este deja un tab) daca tI|x|(p_S1(tab),,p_Sk(tab)).

Trebuie de mentionat ca S₁,,S_k trebuie sa formeze multimea universala U de atribute, adica R₁,,R_m = S₁,,S_k. Consideram un rationament de executare eficienta a jonctiunii. Nu toate tuplurile ce vor participa la jonctiune sunt esentiale in formarea tuplului t ce se adauga la tab. Daca tuplurile t_i si t_j sunt in tab si daca tuplul t_j are componente distincte pentru toate atributele  pentru care are variabile distincte tuplul t_i, atunci t_j nu trebuie sa participe la jonctiune.

Regulile de transformare a tabloului legate de dependentele multivaloare sunt de prisos, intrucat dependenta multivaloare este un caz particular al dependentei jonctiune: dependenta multivaloare X Y este dependenta jonctiune |x|(XY, XZ), unde Z = R XY.

Sa aducem urmatorul algoritm de testare a dependentelor jonctiune.

Algoritmul LOSSLESSTEST (J, j)

Intrare: J - o multime de dependente jonctiune, multivaloare si functionale;

|x|(R₁,,R_m) - o dependenta jonctiune.

Iesire: Adevar, daca dependenta jonctiune e valida (sau jonctiunea e fara pierderi) si fals, in caz contrar.

Se defineste tabloul dependentei jonctiune |x|(R₁,,R_m).

Se aplica F-regulile si J-regulile asupra tabloului pana nu mai poate fi schimbat.

Dupa substituirile produse de toate dependentele din J, se verifica daca tabloul contine un tuplu ce are toate componentele distincte. Daca exista in tablou tuplul-scop, atunci return (adevar) in caz contrar - return(fals).

Exemplul 12. Fie relatia r(ABCDEF) si J=. Sa se verifice daca dependenta jonctiune |x|(ABDE,ACDF,BCEF) este valida in relatia r(ABCDEF).

Aplicand algoritmul de mai sus, pasul (1) produce tabloul din fig.9(a). Acest tabel are trei tupluri si sase coloane.

Urmand F-regulile in aplicarea dependentei A B din J (pasul (2)), obtinem tabloul modificat din figura 9(b). In tablou tuplul t₂[B] = a₂, fiindca t₁[A] = t₂[A] in tabloul initial si b₂₂ a fost substituit de a₂.

Aplicand apoi dependenta functionala F E in pasul (2), obtinem tabloul modificat din fig.9(c). Aici t₂[E] = a₅, intrucat variabila b₂₅ din tabloul precedent este substituita de a₅. Examinand tabloul obtinut, observam ca t₂ = <a₁,a₂,a₃,a₄,a₅,a₆> este tuplul-scop. Deci relatia r(ABCDEF) satisface dependenta jonctiune |x|(ABDE, ACDF, BCEF) sau jonctiunea |x|(p_ABDE(r), p_ACDF(r), p_BCEF(r)) este fara pierderi.

Exemplul 13. Fie relatia r(ABCDE) si multimea de dependente jonctiune J= valida in r. Sa se arate ca relatia r(ABCDE) satisface si dependenta jonctiune |x|(AC,ABD,DE).

Construim tabloul initial tab pentru dependenta jonctiune |x|(AC,ABD,DE) din fig. 10(a) ce consta din trei tupluri t₁, t₂ si t₃, determinate respectiv de multimile AC, ABD si DE.

Aplicam dependenta jonctiune |x|(ABD,CDE) din J asupra tabloului tab. Proiectam tabloul tab asupra schemelor ABD si CDE. Obtinem proiectiile p_ABD(tab) si p_CDE(tab) din fig.10(b) si fig.10(c), respectiv.

In relatia p_ABD(tab) tuplurile <a₁ b₁₂ b₁₄> si <b₃₁ b₃₂ a₄> nu sunt esentiale, fiindca tuplul <a₁ a₂ a₄> le recapituleaza. In relatia p_CDE(tab) tuplurile reprezentative sunt <a₁ b₁₄ b₁₅> si <b₃₃ a₄ a₅>. Tuplul <b₂₃ a₄ b₂₅> nu va participa la jonctiune, fiindca se substituie de tuplul <b₃₃ a₄ a₅>. Jonctionand tuplurile reprezentative din relatiile p_ABD(tab) si p_CDE(tab), obtinem tuplul t₄=<a₁ a₂ b₃₃ a₄ a₅>. Formam tabloul tab₁=tab din fig.10(d).

Sa examinam acum actiunea asupra tabloului tab₁ a dependentei |x|(AC,ABD,BDE) din J, proiectandu-l pe schemele AC, ABD si BDE (vezi fig.10(e), fig.10(f), fig.10(g), respectiv)

Sa observam tuplurile ce vor participa la jonctiune. In p_AC(tab₁) este tuplul <a₁ a₃>, in p_ABD(tab₁) e tuplul <a₁ a₂ a₄> si in p_BDE(tab₁) e tuplul <a₂ a₄ a₅>. In urma jonctiunii acestor tupluri (cate unul din fiecare proiectie) obtinem tuplul t₅=<a₁a₂a₃a₄a₅>. Se construieste tabloul tab₂=tab₁ prezentat in fig.10(h).

Tabloul tab₂ contine tuplul-scop, t_5. Deci dependenta jonctiune |x|(AC,ABD,DE) este valida in relatia r(ABCDE) sau, ceea ce e echivalent, jonctiunea |x|(p_AC(r), p_ABD(r), p_DE(r)) este fara pierderi.

Deci tablourile pot fi utilizate pentru solutionarea problemei calitatii de membru pentru dependentele jonctiune. Adica, daca J e o multime de dependente jonctiune, multivaloare si functionale si j e o dependenta jonctiune, atunci cu ajutorul tablourilor putem determina daca j urmeaza logic din J. Aceasta metoda este aplicabila, numai daca dependentele jonctiune din J sunt definite pe toata multimea universala de atribute U

Pentru multimea de dependente jonctiune nu exista o multime completa de reguli de inferenta.

Definitia 11. Dependenta jonctiune |x|(R₁,, R_m) asupra U = R₁R_m este triviala, daca e valida in orice relatie r cu schema U.

10. Reguli de inferenta ale dependentelor jonctiune

Consideram urmatoarea multime de reguli de inferenta ale dependentelor jonctiune. Este clar ca multimea este inchisa, dar e putin probabil sa fie si completa.

DJ1. Daca R U, atunci |x|(R).

Aceasta regula ne spune ca orice relatie r(R) satisface dependenta jonctiune |x|(R), fiindca r(R) = |x|(p_R(r)).

DJ2. Daca |x|(R₁, . ,R_m) si Y R₁ . R_m, atunci |x|(R₁, . ,R_m,Y).

Validitatea acestei reguli reiese din egalitatea |x|(|x|(R₁, . ,R_m)Y) = |x|(R₁, . ,R_m,Y).

Exemplul 1 Fie dependenta jonctiune |x|(AC,BC) si fie Y = AB. Atunci |x|(AC,BC)|=|x|(AC,BC,AB), adica relatia r(ABC) ce satisface dependenta (vezi fig.11) |x|(AC,BC) satisface si dependenta |x|(AC,BC,AB). Aceste doua dependente sunt definite pe multimea universala de atribute, deci ele pot fi testate prin intermediul tabloului.

DJ3. Fie |x|(R₁, . ,R_m) si Y,Z U. Atunci |x|(R₁, . ,R_m,Y,Z) implica |x|(R₁, . ,R_m,YZ).

Exemplul 15. Fie in relatia r(ABCDE) este valida dependenta jonctiune |x|(AC,DE). Atunci |x|(AC,DE,ABD,BD) |=|x|(AC,DE,ABD). Intrucat ambele dependente antreneaza toate atributele, deductia poate fi verificata cu ajutorul tabloului.

DJ Fie |x|(R₁, . ,R_m), |x|(S₁, . ,S_k) si Y = S₁ . S_k. Atunci |x|(R₁, . ,R_m,Y) si |x|(S₁, . ,S_k) implica |x|(R₁, . ,R_m,S₁, . ,S_k).

Exemplul 16. Fie |x|(AC,ABD), |x|(BD,DE) si Y=BDE. Atunci |= |x|(AC,ABD,BD,DE). Aici tabloul nu poate fi utilizat pentru verificarea implicatiei, fiindca dependenta jonctiune |x|(BD,DE) este inclusa, adica nu e definita pe multimea universala.

DJ5. Fie |x|(R₁, . ,R_m), A R₁ . R_m si Y U. Daca |x|(R₁, . ,R_m,YA) atunci |x|(R₁, . ,R_m,Y).

Exemplul 17. Fie |x|(BCD), Y = DE si A BCD. Atunci |x|(BCD,DEA) |= |x|(BCD,DE). Intrucat dependenta |x|(BCD,DE) e inclusa, tabloul nu poate fi utilizat pentru verificarea acestei reguli.

Regulile DJ4 si DJ5 contin dependente jonctiune incluse. Vom combina aceste reguli pentru obtinerea unei reguli DJ6 echivalente, dar care antreneaza numai dependente jonctiune definite pe multimea universala.

DJ6. Daca |x|(R₁, . ,R_m,Y), |x|(S₁, . ,S_k) si Y, atunci |x|(R₁, . ,R_m,S₁ Y, . ,S_k Y).

Exemplul 18. |=. Sa se calculeze DEP(ACGJ).

Fie relatia r(ABC) si J=. Sa se arate ca relatia r(ABC) nu satisface dependenta jonctiune |x|(AB, AC).

Fie U=ABCDEFGH si J=. Sa se arate ca schema bazei de date Db= se bucura de proprietatea jonctiunii fara pierderi.

Sa se arate ca dependenta jonctiune |x|(R₁,,R_m) asupra U= R₁R_m este triviala, daca si numai daca R_i=U pentru careva i, 1 i m.

Sa se completeze cu tupluri relatia r(ABCDE) din fig.12, ca sa satisfaca dependentele multivaloare A BC si CD BE

Sa se descrie clasa de dependente multivaloare ce pot fi deduse din dependenta functionala X Y.

Sa se gaseasca DEP(AC) pentru multimea de dependente multivaloare definite pe schema R=ABCDEI.

Sa se arate ca o relatie r(R) nu poate fi descompusa fara pierderi in doua relatii cu schemele R₁ si R₂, unde R₁ R si R₂ R, atunci si numai atunci cand in r sunt valide numai dependente multivaloare triviale.

Fie relatia r(ABCDE) si fie F= o multime de dependente functionale valide in r. Sa se arate ca in r e valida si dependenta jonctiune |x|(AD, AB, BE, CDE, AE).

Fie R = ABCDE si M=. Sa se arate ca multimea M de dependente multivaloare este noncontradictorie.