Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Meseria se fura, ingineria se invata.Telecomunicatii, comunicatiile la distanta, Retele de, telefonie, VOIP, TV, satelit




Aeronautica Comunicatii Constructii Electronica Navigatie Pompieri
Tehnica mecanica

Comunicatii


Index » inginerie » Comunicatii
» Dependente multivoce


Dependente multivoce


DEPENDENTE MULTIVOCE

1. Introducere

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



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

r( U V P )

u v p1

u1 v2 p

u v p2

u1 v2 p

u v p1

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

fabricare ( U P ) vanzare(U V )

u p1 u1 v1

u p2 u1 v2

u p2 u2 v2

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

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

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

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

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

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

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

Dam in continuare o definitie formala:

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

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

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

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

r( X Y Z )

a b c1

a b2 c

a b c2

a b2 c

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

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

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

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

r(A B C D)

a b c d

a b c' d'

a b c d'

a b c' d

a b' c' d

a' b c d'

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

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



2. Proprietati ale MV-dependentelor

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

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

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

Intrucat r si r sunt proiectii ale relatiei r, trebuie sa existe t si t pentru care t (XY)=t '(XY), t (XY) = t '(XY).

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

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

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

Fie Z=R-(XY), R1=XY, R2=XZ daca r1=( r ) si r2=( r ) atunci r1r2 intotdeauna contine r. Fie x o X-valoare, exista c1 tupluri in r pentru care X-valoarea coincide cu x si c2 tupluri in r2 cu aceeasi proprietate.Fie c numarul unor astfel de tupluri in r. Daca pentru orice X-valoare x c= c1c2, atunci r= r1 r2.

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

Orice instanta r(R) satisface pYZ (sX=x(r))= pY (sX=x(r)) pZ (sX=x(r)) pentru valoare x a lui X.

Introducem functia

cw [X=x](r)

care face sa corespunda relatiei r un numar real nenegativ.

cw [X=x] = |pw sX=x(r))|

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

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

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

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

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

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

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

Demonstratia este analoaga teoremei de completitudine.

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

A »BCD si A »DE.

3. Axiome de inferenta pentru dependente multivoce

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

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

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

M1 Reflexivitate: Relatia r satisface X »Y.

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

orice Z R.

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

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



X Y Z si X Y-Z.

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

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). Intrucat r satisface X »Y ea trebuie sa contina tuplul t astfel ca: t (X)=t (X), t (Y)=t (Y), t (V)=t (V) unde V=R-(XY). Din relatia X »Z rezulta ca exista tuplul t astfel ca: t (X)=t (X), t (Z)=t (Z), t (W)=t (W) unde W=R-(XZ. Luam t=t . Evident t(X)=t (X), t (Z)=t (Z)=t(Z), t (X W)=t (X W)= t (X W)=t(X W) astfel ca t (XZ)=t(XZ).

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

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

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

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

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

X »Y obtinem ca X Z-Y.

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

Pentru utilizarea combinata a celor doua tipuri de dependente exista numai doua axiome

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

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

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

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

4. Completitudinea sistemului de inferente multivoce

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

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

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

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

Algoritmi de verificare si de determinare pentru MV-dependente sau pentru F- si MV-dependente au o structura asemanatoare cu cei de la F-dependente si au o complexitate polinomiala.







Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate