QReferate - referate pentru educatia ta.
Referatele noastre - sursa ta de inspiratie! Referate oferite gratuit, lucrari si proiecte cu imagini si grafice. Fiecare referat, proiect sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Referate matematica

Dependente Multivaloare, Jonctiune







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 t1 si t2 din r(R) ce satisfac t1[X]=t2[X] exista in r(R) un tuplu t3 pentru care au loc egalitatile t3[X]=t1[X], t3[Y]=t1[Y] si t3[Z]=t2[Z].

Remarca. Din proprietatea de simetrie a acestei definitii urmeaza ca in r(R) mai exista un tuplu t4 ce satisface egalitatile t4[X]=t1[X], t4[Y]=t2[Y] si t4[Z]=t1[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 t1[X]=t2[X] in r(R) exista nu numai un tuplu t3 ce satisface t3[X]=t1[X], t3[Y]=t1[Y] si t3[Z]=t2[Z], dar si un tuplu t4 pentru care au loc egalitatile t4[X]=t1[X], t4[Y]=t2[Y] si t4[Z]=t1[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).

r

A

B

C

D


a1

b1

c1

d1


a1

b1

c1

d2


a1

b1

c2

d1


a1

b1

c2

d2


a2

b1

c1

d1


a2

b1

c1

d2


a2

b1

c2

d1


a2

b1

c2

d2

Fig.1

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 Y1 = Y X. Atunci Z= R XY = R XY1. Fie t1 si t2 doua tupluri cu X-valori egale, adica t1[X] = t2[X]. Fiindca X Y e valida in r(R), atunci in r trebuie sa existe un tuplu t3 ce satisface t3[X]=t1[X], t3[Y]=t1[Y] si t3[Z] = t2[Z]. Egalitatea t3[Y] = t1[Y] implica egalitatea t3[Y1] = t1[Y1]. Prin urmare, relatia r satisface si dependenta multivaloare X Y1.

Suficienta. Fie r(R) satisface dependenta multivaloare X Y1, unde Y1 = Y X si fie X1 X. Sa aratam ca dependenta X Y1X1 e valida in r(R). Intrucat r satisface X Y1 si daca t1, t2Ir si t1[X] = t2[X], atunci exista un tuplu t3, pentru care t3[X] = t1[X], t3[Y1] = t1[Y1] si t3[Z] = t2[Z]. Din X1 X si t3[Y1] = t1[Y1] urmeaza t3[Y1X1] = t1[Y1X1]. Deci X Y1X1.

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 pXY(r) si pXZ(r).

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

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

Fie t11 si t21 doua tupluri in r(R). Intrucat r(R) se descompune fara pierderi asupra XY si XZ (adica r=pXY(r)|x|pXZ(r)), atunci in r1 si r2 se gasesc, respectiv, tuplurile t1 si t2 si t1 = t11[XY], t2 = t21[XZ]. Fiindca r = r1 |x|r2 , r contine un tuplu t ce satisface t[XY]=t1[XY] si t[XZ]=t2[XZ]. Intrucat tuplurile t11, t21 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 r1(R1) si r2(R2) daca si numai daca R1 R2 R1 (sau R1 R2 R2).

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) = pXY(r) |x|pXZ(r), unde Z = R XY.

Expresiile |pXY sX=x(r))| si |pXZ sX=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 pXY(r) si pXZ(r), atunci

sX=x(r)| = |pXY sX=x(r))| pXZ sX=x(r))|. (1)

Intrucat |pXW sX=x(r))| = |pW sX=x(r))|, atunci egalitatea (1) poate fi simplificata:

sX=x(r)| = |pY sX=x(r))| pZ sX=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 pBCA(r) si pBCD(r) sunt prezentate in fig.2. Jonctiunea lor este egala cu r(ABCD). Atunci egalitatea (2) e satisfacuta fiindca:

pA sBC=b1c1(r))|=|pD sBC=b1c1(r))|=2, si |(sBC=b1c1(r)| = 4

si

pA sBC=b1c2(r))|=|pD sBC=b1c2(r))|=2, si |(sBC=b1c2(r)| =

pBCA(r)

B

C

A


pBCD(r)

B

C

D


b1

c1

a1



b1

c1

d1


b1

c2

a1



b1

c1

d2


b1

c1

a2



b1

c2

d1


b1

c2

a2



b1

c2

d2

Fig.2.

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 pY sX=x(r)) = pY sXZ=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 t1 si t2 ce au X-valori egale, t1[X]=t2[X]. Trebuie aratat ca in r exista un tuplu t, incat t[X] = t1[X], t[YZ] = t1[YZ] si t[U] = t2[U], unde U=RXYZ.

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

Sa aratam ca t = t E evident ca t[X] = t4[X]. De asemenea t4[Z] = t1[Z] = t[Z]. Dar t4[Y W] = t3[Y W] = t1[Y W] = t[Y W] si atunci t4[YZ] = t[YZ]. Din U W V, urmeaza t4[U] = t3[U] = t2[U] = t[U]. Intrucat R=XYZU, atunci t4=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 t1, t2 si t1[X] = t2[X], atunci r contine un tuplu t ce satisface egalitatile t[X] = t1[X], t[YZ] = t1[YZ] si t[W] = t2[W].

Intrucat dependenta X Y e valida in r, relatia r contine un tuplu t3 ce satisface t3[X] = t1[X], t3[Y] = t1[Y] si t3[V] = t2[V], unde V = R XY. Dar dependenta Y Z presupune ca in r este un tuplu t4 ce satisface conditiile t4[Y]=t1[Y], t4[Z] = t1[Z] si t4[U] = t3[U]., unde U = R YZ.

Sa aratam ca tuplul t4 este tuplul cautat t. Intrucat t1[X]=t2[X] = t3[X] = t4[X] e evident ca t4[YZ] = t1[YZ]. Dat fiind faptul ca t4[U]=t3[U] si W U X, atunci t4[W] = t3[W]. Din t3[V] = t2[V] si (U X) V reiese ca t3[W] = t2[W]. Deci, tuplul t4 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.

Simbol

Denumire

Regula

DM1

Reflexivitatea

Y X T X Y



DM2

Incrementarea

Z W, X Y T XW YZ

DM3

Aditivitatea

X Y, X Z T X YZ

DM4

Proiectivitatea

X Y, X Z T X Y Z, X Y Z

DM5

Tranzitivitatea

X Y, Y Z T X Z Y

DM6

Pseudotranzitivitatea

X Y, YW Z T XW Z YW

DM7

Complementarea

X YTX R XY

Fig. Reguli de inferenta ale dependentelor multivaloare

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:

m1:=X Z (data),

m2:=X XZ (DM2:m1),

m3:=X Y (data),

m4:=XZ YZ (DM2:m3),

m5:=XZ R XYZ (DM7:m4),

m6:=X R XYZ (DM5:m2,m5 si fiindca (RXYZ)XZ = RXYZ)),

m7:=X R X(R XYZ) (DM7:m6).

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

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

m1:=X Y (data),

m2:=X Z (data),

m3:=X R XY (DM7:m1),

m4:=X Z(R XY) (DM3:m2, m3),

m5:=X Y Z (DM7:m4 (vezi fig.3.)),

m6:=X (YZ)(RXY)=

X R (X Y) (DM3:m3, m5 (vezi fig.3.)),

m7:=X X Y (DM7:m6).

Intrucat regula DM3 urmeaza din DM1, DM2, DM5 si DM7 substituirea dependentelor m4 si m6 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.

m1:=X Y (data),

m2:=XW YW (DM2:m1),

m3:=YW Z (data),

m4:=XW Z YW (DM5:m2, m3).

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 pY sX=x(r)) = pY sXZ=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 pY sXZ=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 t1, t2, pentru care t1[X] = t2[X], atunci in r exista un tuplu t3 ce satisface egalitatile t3[X] = t1[X], t3[Y] = t1[Y] si t3[RXY] = t2[R XY]. Sa observam ca, deoarece Y Z= , avem Z X(RXY) si intrucat t3[X] = t1[X] = t2[X], rezulta ca t3[Z] = t2[Z].

Conform dependentei functionale Z W avem t3[W]=t2[W]. Insa W Y, de unde urmeaza ca t3[W]=t1[W]=t2[W] si prin urmare dependenta functionala X W e valida in r.

In fig.5 sunt prezentate regulile mixte de inferenta.

Simbol

Denumire

Regula

DFM1

Replicarea

X Y T X Y

DFM2

Coalescenta

X Y, Z W, W Y, Y Z= T X W

Fig.5. Reguli 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 Wi IM+, 1 i k

si

X YIM+, daca si numai daca Y este uniunea a unor multimi Wi 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 W1,,Wk, incat pentru Y R X are loc X Y atunci si numai atunci cand Y este uniunea a unor multimi Wi, 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 W1,,Wm si e valida dependenta X Wi, 1 i m. Daca X Y, dar Y nu este uniunea unor Wi, atunci substituim toate multimile Wi care satisfac expresiile Wi Y si WiY , cu multimile Wi Y si Wi Y, respectiv. Conform regulii proiectivitatii, dependentele X Wi Y si X WiY 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 Wi. 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 A1 . An=X);

W1=R X;

k:=1;

for i=1 until k do

while S TIM & S Wi= & T Wi Wi do

begin

k:=k+1;

Wk:= T Wi;

Wi:= Wi Wk;

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), W1, k si i:

DEP(HI)=,

W1=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 W1. Pentru W1, dependenta m1 satisface conditiile liniei 4: HI W1= si A W1 W1, unde HI si A sunt, corespunzator, determinantul si determinatul dependentei m1. Deci, conform liniilor 5-7 pentru k, W2 si W1 sunt setate urmatoarele valori:

k=2,

W2=A,

W1=BCDEFG.

Pentru blocul W1 dependenta m4 e prima care satisface conditiile din linia 4 (dependenta m5, de asemenea, satisface). Prin urmare, dupa executarea liniilor 5-7, k, W3 si W1 obtin valorile:

k=3,

W3=BCD,

W1=EFG.

Blocul W2 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 W2 nu sunt dependente in M ce satisfac conditiile liniei 4 si atunci i creste cu o unitate, devenind 3. Pentru W3 exista dependenta m2. Prin urmare,

k=4,

W4=B,

W3=CD.

Blocul W3 nu e satisfacut de nici o dependenta si atunci i devine egal cu Pentru blocul W4, 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 F1 o acoperire nonredundanta a tuturor dependentelor functionale din (F M)+. Orice dependenta functionala din (F M)+ poate fi dedusa din F1 cu algoritmul MEMBERSHIP. Apoi se elimina dependentele redundante multivaloare din F1 M pentru a obtine F1 M1. Orice dependenta multivaloare din (F M)+ = (F1 M1)+ poate fi dedusa din F1 M1, utilizand numai algoritmul DEPBASIS.

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

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 R1 R, X,Y R1. Dependenta X Y se numeste multivaloare inclusa, daca X Y este dependenta multivaloare in pR (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 pABC(r) si pABD(r) din fig.6. Proiectiile pABC(r) si pABD(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.



r

A

B

C

D







a

b

c

d







a

b1

c1

d1







a

b

c1

d







a

b1

c

d1







a

b

c

d1







a

b1

c1

d
















pABC(r)

A

B

C


pABD(r)

A

B

D


a

b

c




a

b

d


a

b1

c1




a

b1

d1


a

b

c1




a

b

d1


a

b1

c




a

b1

d

Fig.6.

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 Zx X = Zy 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, X1 = A, X2 = C, Zx=D, Y1 = E, Y2 = F; DEP(D) D = , unde Y = D, Y1 = E, Y2 = F, Zy = B, X1 = A, X2 = C. Intrucat X Y = B D = si DEP( , atunci DEP(B) DEP(D) DEP(B D). Este satisfacuta si conditia Zx X = Zy Y, fiindca Zx X= si Zy 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 r1, , rm definite pe schemele R1,,Rm, respectiv, unde Ri U, 1 i m. Jonctiunea relatiilor r1, , rm, notata cu |x|(r1,,rm), este o relatie definita pe schema U1=R1Rm U:

|x|(r1, , rm)=.

De notiunea jonctiune |x|(r1, , rm) a relatiilor r1,,rm e strans legata notiunea de dependenta jonctiune asupra U1, care este o constrangere asupra U1 de forma |x|(R1,,Rm). Vom spune ca dependenta jonctiune este inclusa daca U1 U. Daca U1 = U, vom spune simplu dependenta jonctiune.

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

r(U) = |x|(pR1(r), , pRm(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|(pAB(r), pAC(r), pBC(r)).

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

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

r

A

B

C


pAB(r)

A

B


a1

b1

c1



a1

b1


a1

b2

c2



a1

b2


a3

b3

c3



a3

b3


a4

b3

c4



a4

b3


a5

b5

c5



a5

b5


a6

b6

c5



a6

b6









pAC(r)

A

C


pBC(r)

B

C



a1

c1



b1

c1



a1

c2



b2

c2



a3

c3



b3

c3



a4

c4



b3

c4



a5

c5



b5

c5



a6

c5



b6

c5

Fig.7.

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|(R1,,Rm). Tablou al dependentei |x|(R1,,Rm) este o relatie ce are un nume (fie tab) si |R1Rm| = |U| coloane, notate cu atributele din U, si m tupluri cate unul pentru fiecare schema Ri, 1 i m. Tuplul ti contine in coloana Aj variabila distincta aj, daca Aj apartine lui Ri. Celelalte componente ale tuplului ti sunt variabile nondistincte bij ce nu se repeta in alt tuplu. Deci ti[Aj] = aj, daca AjIRi si ti[Aj] = bij, daca Aj Ri.

 

tab

A

B

C

D

 


a1

a2

b13

b14

 


b21

a2

a3

b24

 


a1

b32

a3

a4

Fig.8. Tabloul dependentei |x|(AB, BC, ACD)

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 ti[X] = tj[X] si pentru AIY ti[A] = n , tj[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|(R1,,Rm) si fie J o multime de dependente jonctiune, multivaloare si functionale. Pentru orice dependenta jonctiune |x|(S1,,Sk) din J la tabloul tab se adauga tuplul t (daca el nu este deja un tab) daca tI|x|(pS1(tab),,pSk(tab)).

Trebuie de mentionat ca S1,,Sk trebuie sa formeze multimea universala U de atribute, adica R1,,Rm = S1,,Sk. 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 ti si tj sunt in tab si daca tuplul tj are componente distincte pentru toate atributele pentru care are variabile distincte tuplul ti, atunci tj 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|(R1,,Rm) - 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|(R1,,Rm).

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.

 

A

B

C

D

E

F

 

t1

a1

a2

b13

a4

a5

b16

 

t2

a1

b22

a3

a4

b25

a6

 

t3

b31

a2

a3

b34

a5

a6

Fig.9(a). Tabloul initial al dependentei jonctiune |x|(ABDE, ACDF, BCEF)

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


A

B

C

D

E

F

 

t1

a1

a2

b13

a4

a5

b16

 

t2

a1

a2

a3

a4

b25

a6

 

t3

b31

a2

a3

b34

a5

a6

Fig.9(b). Tabloul modificat de A B

Aplicand apoi dependenta functionala F E in pasul (2), obtinem tabloul modificat din fig.9(c). Aici t2[E] = a5, intrucat variabila b25 din tabloul precedent este substituita de a5. Examinand tabloul obtinut, observam ca t2 = <a1,a2,a3,a4,a5,a6> este tuplul-scop. Deci relatia r(ABCDEF) satisface dependenta jonctiune |x|(ABDE, ACDF, BCEF) sau jonctiunea |x|(pABDE(r), pACDF(r), pBCEF(r)) este fara pierderi.


A

B

C

D

E

F

t1

a1



a2

b13

a4

a5

b16

t2

a1

a2

a3

a4

a5

a6

t3

b31

a2

a3

b34

a5

a6

Fig.9(c). Tabloul modificat de F E

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 t1, t2 si t3, determinate respectiv de multimile AC, ABD si DE.

tab

A

B

C

D

E

t1

a1

b12

a3

b14

b15

t2

a1

a2

b23

a4

b25

t3

b31

b32

b33

a4

a5

Fig.10(a) Tabloul initial tab

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

pABD(tab)

A

B

D

a1

b12

b14


a1

a2

a4


b31

b32

a4

Fig.10(b). pABD(tab)


pCDE(tab)

C

D

E


a3

b14

b15


b23

a4

b25


b33

a4

a5

Fig.10(c). pCDE(tab)

In relatia pABD(tab) tuplurile <a1 b12 b14> si <b31 b32 a4> nu sunt esentiale, fiindca tuplul <a1 a2 a4> le recapituleaza. In relatia pCDE(tab) tuplurile reprezentative sunt <a1 b14 b15> si <b33 a4 a5>. Tuplul <b23 a4 b25> nu va participa la jonctiune, fiindca se substituie de tuplul <b33 a4 a5>. Jonctionand tuplurile reprezentative din relatiile pABD(tab) si pCDE(tab), obtinem tuplul t4=<a1 a2 b33 a4 a5>. Formam tabloul tab1=tab din fig.10(d).

 

tab1

A

B

C

D

E

 

t1

a1

b12

a3

b14

b15

 

t2

a1

a2

b23

a4

b25

 

t3

b31

b32

b33

a4

a5

 

t4

a1

a2

b33

a4

a5

Fig.10(d) Tabloul tab1= tab

Sa examinam acum actiunea asupra tabloului tab1 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)

pAC(tab1)

A

C


a1

a3


a1

b23


b31

b33


a1

b33

Fig.10(e). pAC(tab1)


pABD(tab1)

A

B

D


a1

b12

b14


a1

a2

a4


b31

b32

a4

Fig.10(f). pABD(tab1)


pBDE(tab1)

B

D

E


b12

b14

b15


a2

a4

b25


b32

a4

a5


a2

a4

a5

Fig.10(g). pBDE(tab1)

Sa observam tuplurile ce vor participa la jonctiune. In pAC(tab1) este tuplul <a1 a3>, in pABD(tab1) e tuplul <a1 a2 a4> si in pBDE(tab1) e tuplul <a2 a4 a5>. In urma jonctiunii acestor tupluri (cate unul din fiecare proiectie) obtinem tuplul t5=<a1a2a3a4a5>. Se construieste tabloul tab2=tab1 prezentat in fig.10(h).

 

tab2

A

B

C

D

E

 

t1

a1

b12

a3

b14

b15

 

t2

a1

a2

b23

a4

b25

 

t3

b31

b32

b33

a4

a5

 

t4

a1

a2

b33

a4

a5

 

t5

a1

a2

a3

a4

a5

Fig.10(h). Tabloul tab2=tab1

Tabloul tab2 contine tuplul-scop, t5. Deci dependenta jonctiune |x|(AC,ABD,DE) este valida in relatia r(ABCDE) sau, ceea ce e echivalent, jonctiunea |x|(pAC(r), pABD(r), pDE(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|(R1,, Rm) asupra U = R1Rm 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|(pR(r)).

DJ2. Daca |x|(R1, . ,Rm) si Y R1 . Rm, atunci |x|(R1, . ,Rm,Y).

Validitatea acestei reguli reiese din egalitatea |x|(|x|(R1, . ,Rm)Y) = |x|(R1, . ,Rm,Y).

r

A

B

C


a1

b1

c1


a1

b2

c2


a2

b1

c3

Fig. 11.

 

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|(R1, . ,Rm) si Y,Z U. Atunci |x|(R1, . ,Rm,Y,Z) implica |x|(R1, . ,Rm,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|(R1, . ,Rm), |x|(S1, . ,Sk) si Y = S1 . Sk. Atunci |x|(R1, . ,Rm,Y) si |x|(S1, . ,Sk) implica |x|(R1, . ,Rm,S1, . ,Sk).

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|(R1, . ,Rm), A R1 . Rm si Y U. Daca |x|(R1, . ,Rm,YA) atunci |x|(R1, . ,Rm,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|(R1, . ,Rm,Y), |x|(S1, . ,Sk) si Y, atunci |x|(R1, . ,Rm,S1 Y, . ,Sk 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|(R1,,Rm) asupra U= R1Rm este triviala, daca si numai daca Ri=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

r

A

B

C

D

E


a1

b1

C1

d1

e1


a1

b2

C1

d2

e1


a2

b1

C1

d1

e2

Fig.12.

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 R1 si R2, unde R1 R si R2 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.





Nu se poate descarca referatul
Acest referat nu se poate descarca

E posibil sa te intereseze alte referate despre:


Copyright © 2021 - Toate drepturile rezervate QReferat.com Folositi referatele, proiectele sau lucrarile afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul referat pe baza referatelor de pe site.
{ Home } { Contact } { Termeni si conditii }