Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


TRANSFORMARI CONSERVATIVE IN BAZE DE DATE

baze de date

+ Font mai mare | - Font mai mic



TRANSFORMARI CONSERVATIVE IN BAZE DE DATE



Transformarea de proiectie-unire ( pe scurt PJ-transformare ) a unei relatii r(R) determinata de schema bazei de date R AR1,R2,.,Rp} este utilizata pentru caracterizarea descompunerilor conservative ( fara pierderi de informatii ) .

Descompuneri fara pierderi de informatii

Fie o schema R si o descompunere a lui R in schemele R1,R2,,Rp astfel ca R=R1ÈR2È ÈRp si F o multime de F-dependente pe R. Descompunerea este fara pierderi (loss join descompozition) in raport cu F daca orice relatie r de schema R care satisface F atunci

r=R1(r)R2(r) .Rp(r).

Teorema 1 (Criteriul de descompunere fara pierderi) Fie schema de relatie R, descompunerea aR1,R2s si F o multime de F-dependente. Daca F implica una din urmatoarele F-dependente:

i)           R1 R2 R1tR2

ii)         R1 R2 R2tR1

iii)      R1 R2 R1

iv)        R1 R2 R2

atunci orice relatie r(R) care satisface F se descompune fara pierderi de informatie, adica r=pR1(r)pR2(r).

Demonstratie. i) Fie relatia r care satisface F, este suficient sa aratam ca r include pR1(r)pR2(r). Fie tuplul tIpR1(r)pR2(r) atunci exista tuplurile t1,t2Ir astfel incat t1(R1)=t(R1) si t2(R2)=t(R2) din care rezulta ca t1(R1 R2)=t2(R1 R2). Deoarece r satisface F rezulta t2(R2)=t(R2), t2(R1tR2)=t1(R1tR2)=t(R1tR2), din care rezulta t(R1ÈR2)=t2(R1ÈR2) adica t=t2 deci tIr.

Relatiile ii),iii) si iv) se demonstreaza analog.

Transformari conservative

Criteriul de conservare a relatiei prin descompunere este dat de relatia :

r=R1(r)R2(r) Rp(r) .

In continuare se prezinta o metoda pe baza careia se decide daca o dependenta ( F sau J ) este implicata de o multime de dependente ( F- si / sau J-dependente ) .

Definitia 1. Fie R AR1,R2,.,Rp} o multime de scheme de relatii si R R1R2.Rp . Se numeste transformare de proiectie-unire definita de R , functia de relatie de schema R notata data de relatia : (r) R1(r)R2(r) Rp(r).

Exemplul 1 Fie R AABC , BC , ADE } si R ABCDE . Se considera relatia

r(R) din figura 1 . Rezultatul aplicarii transformarii mR lui r este relatia s(R) .

r ( A B C D E ) s ( A B C D E )

3 1 5 7 8 3 1 5 7 8

3 4 5 2 8 3 4 5 2 8

3 4 5 2 9 3 4 5 2 9

3 1 5 2 9 3 1 5 2 9

3 1 5 2 9

Figura 1 Figura 2

Definitia 2. Fie R AR1,R2,.,Rp} o multime de scheme de relatii si R R1R2.Rp . Relatia r(R) se numeste punct fix al transformarii de proiectie-unire daca (r) r . Multimea tuturor punctelor fixe ale transformarii ( . ) se noteaza cu FIX(R) .

Relatia s(R) din figura 2 este un exemplu de punct fix dat de schema : R A ABC, BC, ADE }. A spune ca r satisface J-dependenta *aRs este acelasi lucru cu mR(r) r . In continuare se prezinta cateva proprietati ale PJ-transformarii mR( . ) .

Propozitia 1. Fie o multime de scheme de relatii R AR1,R2,.,Rp}, R R1R2.Rp si relatiile r si s de schema R . PJ-transformarea are urmatoarele proprietati:

i) r mR ( r ),

ii) daca r s atunci mR( r )mR( s ) ( monotonie ),

iii) mR( r ) mR (mR( r ) ) ( idempotenta ).

Demonstratie: Punctul i) rezulta din definitia PJ-transformarii . Punctul ii) rezulta din proprietatea de monotonie a proiectiei , adica daca rs atunci Ri(r)Ri(s) 1ip . Fie r'= mR(r) atunci iii) rezulta din proprietatea de completitudine a unirii lui R1(r)R2(r) Rp(r)

Trebuie studiat cazul, in care o relatie de schema R poate fi reprezentata printr-o baza de date de schema R astfel ca sa satisfaca urmatoarele conditii :

C1) sa nu existe pierderi de informatii ;

C2) sa fie eliminata redundanta .

In practica nu este interesanta multimea tuturor relatiilor posibile de schema R ci numai cateva submultimi , notam una din ele cu P . Multimea P satisface conditia (C1) daca mR(r) r pentru orice relatie rP , adica P FIX(R) . A doua conditie (C2) poate fi exprimata astfel : proiectiile oricarei relatii r din P in raport cu schemele din R sa aiba cel putin atatea tupluri cat r . Deoarece P este infinta ea nu poate fi descrisa prin enumerare ci numai prin specificarea multimii de restrictii de tip F- sau J- pe care relatiile componente le satisfac . In continuare notam cu C o multime de restrictii ( conditii ) pentru schema de relatie R .

Definitia 3. Multimea tuturor relatiilor r(R) care satisfac toate restrictiile din C se numeste SATR(C) . Daca schema R se subantelege atunci acesta se noteaza SAT(C) , iar cea pentru o singura conditie se noteaza cu SAT(c) .

Definitia 4. Fie C o multime de restrictii pentru o schema de relatie R . Spunem ca C implica c si notam Cc daca SATR(C)SATR (c) .

Daca P SATR(C) pentru o multime de restrictii C , atunci conditia (C1) de eliminare a pierderilor de informatii pentru baza de date de schema R poate fi formulata prin una din urmatoarele conditii : SAT(C)FIX(R) sau C *aRs. In paragraful urmator se da o metoda de verificare a acestor conditii cand C este formata dintr-o multime de F- si J-dependente .

3 . Tablouri

In acest paragraf se prezinta o metoda de reprezentare a unei PJ-transformari printr-un tablou. Tabloul este similar unei relatii cu deosebirea ca, in locul valorilor, tabloul contine variabile dintr-o multime oarecare V , care este reuniunea a doua multimi Vd si Vn , unde Vd este o multime de variabile principale ( distinguished ) notate cu litera a cu indice si Vn este o multime de variabile secundare notate cu litera b cu indice . Multimea atributelor este data de numele coloanelor tabloului care formeaza schema tabloului. Fiecare variabila principala apartine numai unei coloane. Tuplului dintr-o relatie ii corespunde o linie dintr-un tablou . Pentru un tablou de schema A1A2.An variabile principale din coloana Ai 1in sunt ai . Un tablou T de schema R poate fi privit ca paternul (sau sablonul ) unei relatii de schema R . Dam relatia ce se obtine dintr-un tablou inlocuind variabilele cu valori din domeniile respective . Presupunem ca R R1R2.Rn si cu Di dom (Ai) unde 1in . Se numeste evaluare (valoare, estimare ) a tabloului T o functie  : V D , astfel ca (v)dom (Ai) , daca v este o variabila care apartine coloanei . Se extinde evaluarea de la variabilele la linii si apoi la intreg tabloul. Daca w <w1,w2,.,wn> este o linie a tabloului atunci (w) <w1),w2),.,wn )> este o evaluare a liniei w. Notam cu  : ( t ) A(w) | w este linie in T } .

Exemplul 1.Fie tablou T din figura 1 , valoarea din figura 2 si (T) in figura 3 .

T (  ( r (

    2 5 6 9

    3 4 6 8

    2 5 6 8

 (

Figura 1 Figura 2 Figura 3

Vom interpreta un tablou T de schema R ca o functie de relatie de schema R . Fie wd linia formata numai din variabile principale wd < a1,a2,.,an > care nu este in mod necesar in T . Daca r este o relatie de schema R , punem

T (r) A(wd) | (T) r }.

Aceasta definitie arata ca , daca avem o evaluare  care face sa corespunda oricarei linii din T un tuplu din r atunci  (wd) este in T ( r ) .

Exemplul 2.Fie relatia din figura 4 si tabloul T din figura 1 si evaluarea din figura 2 arata ca tuplul <2,4,6,8> trebuie sa fie in T (r) . Evaluarea' din figura 5 pune <3,5,6,8> in T(r). T(r) este relatia s din figura 6.

R( ) T( r ) s (

2 5 6 9    

3 4 6 8 3 5 6 8

2 5 6 8    

3 4 7 8

Figura 4 Figura 5 Figura 6

Cand se evalueaza T(r) , daca coloana Ai din T nu contine variabile principale atunci in ea nu exista nici o restrictie asupra valorilor lui (ai).

Daca  (T)r atunci ' (T)r pentru orice ' care coincide cu  pe V exceptand ai . Prin urmare daca dom(Ai) este infinit, atunci T(r) poate avea o multime infinita de tupluri si nu este o relatie. De aceea cand se considera un tablou ca o functie trebuie ca in T sa aiba un simbol principal in fiecare coloana .

4 . Tabloul ca reprezentare a unei PJ-transformari

Pentru orice PJ-transformare mR exista un tablou T care, ca functie coincide cu mR . Fie R AR1,R2,.,Rp} o multime de scheme de relatie unde R R1R2.Rp A1A2.An . Tabloul determinat de schema bazei de date R notat TR are p linii si este definit in urmatorul mod :




. schema lui TR este R ;

TR are p linii w1,w2,.,wp ;

. linia wi are in coloana Aj o variabila principala aj daca AjRi ;

. Restul coloanelor din linia wi 1ip sunt simboluri secundare unice

( adica nu apar in alte linii ale TR ) ;

Aceasta transformare poate fi pusa sub forma urmatorului algoritmul :

0. START a TR-generarea tabloului TR

1. INPUT A r , p ,n, R1,R2,.,Rp , A1,A2,.,An }

2. k 0

3. FOR i 1 , 2 , . . . , p

3.1 FOR j 1 , 2 , . . . , n

3.1.1 IF AjRi

THEN

.1 wi j ' a j '

ELSE

.2 k k + 1

.3 wi j ' bk '

3.1.2 CONTINUE

3.2 CONTINUE

4. OUPUT A w }

STOP

Exemplul 1.Fie R AA1A2,A2A3,A3A4} . Tabloul TR este dat in figura 1 :

( )

    b4

Figura 1

Propozitia 1. Fie R AR1,R2,.,Rp} o multime de scheme de relatie si R R1R2,.,Rp. Tabloul TR si transformarea mR definesc aceeasi functie de relatie de schema R .

Demonstratia rezulta din definitia transformari conservative .

Exemplul 2 Fie R A A1A2,A2A3,A3A4} si relatia r din figura 2 atunci mR(r) TR (r) s unde s este data in figura 3 .

r( s(

2 5 6 8

3 4 6 8

Figura 2 Figura 3

5 . Echivalenta schemelor si a tablourilor

Definitia 1 . Fie T1 si T2 tablouri de schema R. Spunem ca T1 *T2 daca    T1(r) T2(r) pentru orice relatie r(R). Tablourile T1 si T2 sunt echivalente daca T1* T2 si T2 *T1 si se noteaza cu T2 T1 .

Definitia 2. Fie R A R1,R2,.,Rp} si S A S1,S2,.,Sq} doua multimi de scheme de relatie unde R R1R2,.,Rp S1S2,.,Sq . Se spune ca R acopera pe S notata RS , daca pentru orice schema Sj din S , exista Ri in R astfel ca Ri Ê Sj . Se spune ca R si S sunt echivalente daca RS si SR si se noteaza R~S .

Exemplul 1: Daca R AA1A2, A2A3, A3A4} si S A A1A2A3, A3A4} atunci SR

Teorema 1.Fie multimile de scheme de relatie R AR1,R2,.,Rp} si S A S1,S2,.,Sq } unde R R1R2,.,Rp S1S2,.,Sq . Urmatoarele afirmatii sunt echivalente :

1 . mR(r)ms (r) oricare ar fi r(R) ,

2 . TR*TS ,

3. FIX(R)FIX(S) ,

4. RS .

Demonstratie.Din propozitia 1 rezulta ca (1) este echivalenta cu (2) . Vom arata ca (1) si (3) sunt echivalente. Din secventa de demonstrare rezulta ca (1)

d1) sFIX( R)

d2) s mR (s)    ( din d1 ) ,

d3) mR(s)mS(s) ( din ipoteza ) ,

d4) smS(s)    ( din d2 si d3 ) ,

d5) smS(s ( din lema 1 ) ,

d6) s mS(s) ( din d4 si d5 ) ,

d7) sFIX( S)

Aratam ca (3)(1). Adica din FIX( R) FIX( S) mR(r)mS (r) .

Fie r(R) , r' mR(r) , din idempotenta rezulta mR(r') r', deci r'FIX( R) din ipoteza rezulta ca r'FIX( S) adica (a) mS(mR(r)) mR(r). Dar mR(r)r, din monotonia lui mS rezulta (b) mS(mR(r))mS(r) ; din (a) si (b) rezulta ca mS(r) mR(r) .

Vom arata ca conditiile (1) si (4) sunt echivalente. Presupunem ca, dom(A) contine cel putin doua valori pentru orice atribut A din R. Notam aceste valori cu 0 si 1. Construim relatia s(R) cu q tupluri t1,t2,.,tq definite in urmatorul mod :

Notam cu t0 tuplul format numai din valori nule . Nu este greu de verificat ca apartine lui mS(s). Prin urmare t0mR(s). Conform definitiei lui mR, pentru fiecare schema Ri din R exista un tuplu tjs astfel ca tj(Ri ) t0(Ri). Astfel RiSj deci RS .

Presupunem ca RS . Fie r(R) o relatie arbitrara si t un tuplu arbitrar din mS(r). In r exista tuplurile t1,t2,.,tq astfel ca ti(Si) t(Si), 1iq. Deoarece RS atunci pentru orice Rj din R exista Si , SiRj, prin urmare ti(Rj) ti(Si) . Fie tuplurile tj'r , tj'(Rj) t(Rj ) din care rezulta ca t este din mR(r) si prin urmare mR(r)mS(r) .

Exercitiu.Fie R AA1A2 A2A3 A3A4} si S A A1A2A3 A3A4} . Daca RS se observa ca TR(r) TS(r) . Fie relatia r(R) din figura 1 si tablourile TR(r) si TS(r) .

r(

2 5 7 9 2 5 7 9 2 5 7 9

3 4 8 10 2 5 8 10 3 5 8 10

4 6 8 11 2 5 8 11 3 5 8 11

3 5 7 9 4 6 8 10

3 5 8 10 4 7 8 11

3 5 8 11

4 6 8 10

4 6 8 11

Figura 1 Figura 2 Figura 3

Corolar 1.Fie multimile de scheme de relatie R AR1,R2,.,Rp} si S A S1,S2,.,Sq} unde R R1,R2,.,Rp S1,S2,.,Sq . Urmatoarele afirmatii sunt echivalente :

1 . mR mS

2 . TRTS

3. FIX(R)FIX(S) ,

4. R~ S .

Prin conditia (1) intelegem mR(r) mS(r) pentru orice r(R) .

Fie R AA1A2A3,A1A4,A1A3A4} si S A A1A2A3,A3A4,A1A3A4}. Multimile de scheme de relatie R si S sunt echivalente. Din corolarul 1 rezulta ca TRTS , dar evident ca TRTS. Cum se observa din exemplul urmator chiar daca se vor redefini variabilele secundare .

   



   

   

Figura 1 Figura 2

Definitia 1. Fie w1 si w doua linii ale tabloului T de schema R . Daca pentru orice atribut A din R cu w2(A) principala rezulta ca w1(A) este variabila principala si se spune ca w1 absoarbe ( subsume ) w2 .

Definitia 2. Fie T un tablou. Tabloul in care liniile nu mai pot fi ( reduse ) absorbite de nici o alta linie se numeste redus prin absortie si se noteaza cu SUB(T) .

Exemplul 1. In tabloul TR w1 absoarbe w2 deoarece w1(A1) a1 w2(A1) a1 w1(A4) a4 w2(A4) a4 atunci :

SUB( ) SUB(

   

Teorema 1 . Fie multimile de scheme de relatie R AR1,R2,.,Rp} si S A S1,S2,.,Sq} unde R R1,R2,.,Rp S1,S2,.,Sq . Atunci:

TRTS SUB(TR) SUB(TS) exceptand variabilele secundare.

2) SUB(TR TR

Pentru demonstratie vezia s.

5. C-Transformari

Teorema 1 arata ca exista un procedeu simplu pentru verificarea echivalentei a doua tablouri obtinute din multimi de scheme si anume verificarea identitatii reduse prin absortie. Orice tablou in care nici o variabila secundara nu se intalneste mai mult decat o data se obtine dintr-o multime oarecare de scheme. Teorema 1 nu este adevarata pentru tablourile unde variabilele secundare sunt duplicate .

Dorim sa formulam conditii de echivalenta pentru tablouri arbitrare introducand c-transformarea pentru tablouri. C-transformarea este asemanatoare evaluarii (estimarii) , care in locul transformarii variabilelor tabloului in elemente ale domeniului ele se transforma in variabile ale altui tablou . Prin urmare liniile se transforma in linii .

Definitia 1 : Fie T si T' doua tablouri de schema R si multimile de variabile V si V'. Transformarea y:V->V' se numeste C-transformare din T in T' daca ea satisface urmatoarele conditii :

1) daca variabila v se afla in linia A a tabloului T atunci y(v) se afla in linia A a tabloului T' ;

2) daca v este o variabila principala atunci y(v) este variabila principala ;

y(v)T' . Adica , daca y este extinsa la liniile lui T si deci la intregul tablou T atunci prin aceasta transformare o linie din T se transforma intr-o linie din T' .

Exemplul 1 : Fie tablourile T si T' din figura 1 si 2 si c-transformarea din figura 3

T( ) T'(

y i

y y

y y y

Figura 1 Figura 2 Figura 3

Primele doua linii din T sunt aplicate in primele doua linii din T' de y , c-transformarea y aplica a treia linie dinT in a doua linie din T' .

Teorema 1 : Fie tablourile T si T' de schema R . T *T' daca si numai daca exista o c-aplicatie de la T la T' .

Demonstratie : Suficienta . Fie y o aplicatie de la T la T'. Fie r(R) o relatie oarecare , T(r) si T'(r) . Daca  este o evaluare a lui T' astfel ca (T')r , atunci  y este o evaluare pentru T ,  y(T)r . Incluziunea rezulta din y(T)T' prin aplicarea lui . Daca wd este o linie formata din variabile principale si y( wd) wd (y(wd)) (wd) deci T'(r) T(r).

Necesitatea . Presupunem ca T T'. Considerand tabloul T' ca relatie obtinem T(T')T'(T') Luand evaluarea' care este transformarea identica a variabilelor V' din T' . Evident'(T') T'T' si'(wd) wdT'(T'). Exista o evaluare  pentru T astfel ca (T) T', (wd) wd . Atunci definim c-aplicatia din T la T' prin.

Corolar : Fie T si T' doua tablouri de schema R .T T' exista o C-transformare de la T la T' si o C-transformare de la T' la T .

Exemplul 2: Fie T tabloul care este compus numai dintr-o linie formata numai din variabile principale wd si T' un tablou care contine wd , atunci T T' . C-transformarea din T la T' aplica wd in wd . C-transformarea din T' in T aplica toate liniile in wd .

6 . Echivalenta schemelor determinata de restrictii

In acest paragraf se determina care sunt proprietatile unei relatii care sa fie corect reprezentata prin proiectiile sale. Din corolarul teoremei 1 3 rezulta ca, daca R AR1,R2,.Rp} este o schema a bazei de date atunci FIX(R) este multimea tuturor relatiilor pe R R1,R2,.Rp numai daca Ri R pentru un i anumit. In multe cazuri dorim sa reprezentam o multime de relatii pentru schema R asupra careia se aplica o multime impusa de restrictii . Vom utiliza restrictiile ca sa reprezentam relatiile .

Definitia 1 : Fie P o multime de relatii de schema R . Daca T1 si T2 sunt tablouri de schema R atunci T1 cuprinde T2 in raport cu P ( notat T1 T2 ) daca T1(r) T2 (r) , rP .

T1T2 ( sunt echivalente pe P ) daca T1 T2 si T2 T1 .

In majoritatea cazurilor se considera P SAT(C) pentru o multime de restrictii C data. Notam pe scurt pe prin . Ne intereseaza cand SAT(C)FIX(R) pentru o schema a bazei de date R . Adica pentru o schema a bazei de date R putem sa descompunem fara pierdere pe R orice relatie din SAT(C) . In termenii restrictiilor aceasta se poate reduce la verificarea corectitudinii relatiei C *aRs. Daca TI este un tablou pentru transformarea identica (TI contine linia formata din variabile principale), atunci dorim sa stim daca TR se comporta ca TI pe SAT(C) adica TRTI ? Teorema 1 din &5 da un test pentru * dar ne trebuie un test pentru . Pentru lema urmatoare va trebui sa privim un tablou ca o relatie care este din multimea P. Prin aceasta se intelege ca pentru orice evaluare  , (T)P Pentru o multime arbitrara de relatii aceste conditii sunt mai greu de verificat . Totusi caand P=SAT(C) unde C consta intr-o multime de F- sau J-dependente daca pentru o evaluare bijectiva ,(T)P , atunci pentru orice alta evaluare','(T)P .

Lema 1: Fie T1 si T2 doua tablouri de schema R si P o multime de relatii pe R . Fie T1' si T2' astfel ca :

1) T1 T1' si T2T2'si

2) T1' si T2' considerate ca relatii sunt ambele din P .

Atunci T1* T2 daca si numai daca T1' * T2' .

Demonstratie : Suficienta este directa . Daca T1'* T2' atunci rezulta ca T1' T2', dar T1 T1'si T2 T2' deci T1 T2 . Vom arata ca, daca T1 T2 atunci T1'* T2' . Considerand T1' simultan ca relatie si tablou atunci T1'(T1') este din P si T1'(T1') T2'(T2') . Fie wd o linie a tuturor variabilelor principale si  o evaluare identica a lui T1'. Evident (T1') T1' astfel este in T1'(T1') prin urmare si in T2(T1') . Exista o evaluare pentru T2' astfel ca( T2') T2' si ( . Evaluarea poate fi considerata ca o c-transformare din T2' in T1' si prin urmare rezulta T1 * T2'.

Corolar : In ipotezele lemei 1 rezulta ca T1 T2 daca si numai daca T1' T2' .

Acest corolar poate fi interpretat ca un test de verificare a relatiei T1 T2 , daca printr-un procedeu am afla tabloul T' , astfel ca T'T si T' ca relatie este in SAT(C). Vom introduce reguli de transformare pentru tablouri . O regula de transformare determinata de o multime de restrictii C este un procedeu de modificare a tabloului T in tabloul T' astfel ca TT' . Prima transformare particulara a fost c-transformarea prin absortie. Pentru un tablou T cu variabile secundare ne duplicate eliminarea liniilor absorbite conserva echivalenta. Va trebui sa gasim multimea regulilor de transformare ( F-reguli si J-reguli) pentru o multime data C de F-dependente si J-dependente. Aplicarea repetata a acestor reguli de transformare are ca rezultat obtinerea unui tablou care satisface toate dependentele din C. In continuare vom considera o multime C de F- si J-dependente pentru o multime U de atribute care constituie schema pentru toate restrictiile si tablourile considerate. Oricarei F-dependente XA din C ii este asociata o F-regula . F-regula determinata de XA reprezinta o clasa de transformari care poate fi aplicata unui tablou care nu depinde de liniile alese. Fie un tablou T care contine liniile w1 si w2 unde w1(x) w2(x) si v1 w1(A) si v2 w2 (A), v1v2 .



A aplica o F-regula determinata de F-dependenta XA la tabloul T, inseamna a identifica variabilele v1 si v2 si a inlocui una din ele prin alta in urmatorul mod :

- daca una din v1 si v2 este principala, sa zicem v1 instanta lui v2 este inlocuita cu v1.

- daca v1 si v2 nu sunt principale atunci orice instanta cu indice mai mare este inlocuita cu instanta variabilei cu indice mai mic .

Deoarece tabloul este o multime de linii , cateva din ele prin redefinire vor fi identice si vor fi eliminate .

Exemplul 1 : Fie tabloul T din figura 1 si C AA1A2 A4 , A2A4 A3}. Aplicand F-regula determinata de A2A4 A3 la liniile 1 si 2 permitem inlocuirea variabilei b3 cu a3 deoarece a3 este principala si obtinem tabloul T' .

T( ) T'( ) T"(

Figura 1 Figura 2 Figura 3

Aplicand F-regula determinata de A1A2 A4 se obtine tabloul T" deoarece variabile b1 si b4 trebuie identificate prin cea cu indice mai mic . Astfel prima si ultima linie sunt identice deci se elimina una din ele .

Teorema F. Fie T' tabloul rezultat prin aplicarea unei F-reguli date de X A din tabloul T . Atunci T si T' sunt echivalente pe SAT(X A) .

Fie S AS1,S2,.,Sl} o multime de scheme de relatii si *aSs o J-dependenta pe U. Fie T un tablou si w1,w2,.,wq liniile lui T care sunt unibile pe S cu rezultatul w . Aplicarea J-regulii *aSs la T inseamna formarea tabloului T' TAw}.

Exemplul 3. Fie T tabloul reprezentat in figura 4 si C A*aA1A2A4, A1A3A4s , *aA1A2, A2A3, A3A4s} . Aplicand J-regula determinata de *a A1A2, A2A3, A3A4s la a doua si a treia linie din T genereaza linia <a1 b1 b3 a4> . Rezultatul este tabloul T' dat in figura 5 .

T( ) T'( ) T"(

Figura 4 Figura 5 Figura 6

J-regula data de *aA1A2A4, A1A3A4s poate fi aplicata la prima si a patra linie a lui T'; se genereaza linia <a1 b1 b3 a4> iar tabloul T' este rezultatul acestei aplicatii.

Teorema J. Fie S AS1,S2,.Sq}. Fie T' tabloul rezultat prin aplicarea J-regulii determinata de *aSs din tabloul T . Atunci tablourile T si T' sunt echivalente pe SAT(*aSs).

Demonstratie : Va trebui sa aratam ca T(r) T'(r) pentru orice rSAT(*aSs) . Fie t'T'(r) si  o evaluare cu (wd) t' si (T')r . Deoarece TT' avem (T)(T') de asemenea (T')r si(wd) t'T(r) . Prin urmare T'(r)T(r) . Acum fie t un tuplu oarecare din T(r) si  o evaluare cu (wd) t si (T)r . Tuplul unic care ar putea apartine lui(T') dar nu lui(T) este(w) unde w este generata de J-regula determinata de *aSs din liniile w1,w2,.,wq care apartin lui T. Daca w1,w2, .,wq sunt unibile pe S atunci (w1), (w2),.,(wq) unite pe *aSs dau rezultatul w. Intrucat r intra in SAT(*aSs) si (w1) ,(w2),.,(wq)Tr atunci (w)r. Prin urmare(T')r si(wd) tT(r), deci T(r)T'(r) si deci T(r) T'(r).

7. Algoritmul chase

In acest paragraf se da un algoritm de calcul care se bazeaza pe metoda chase , cu ajutorul careia pentru un tablou dat si o multime de dependente C se construieste un nou tablou T* astfel ca TT* si T* ca relatie sa apartina lui SAT(C) . Pentru un tablou T si o multime de dependente C se aplica regulile determinate de F- si J-dependentele din C atata timp cat se realizeaza schimbari . Ordinea de aplicare este neesentiala . Conform teoremelor F si J la terminarea algoritmului se genereaza un tablou T*T si T*SAT(C) .

Procedura TR transforma tabloul Tj+i in Tj+i+1 pe baza regulei determinata de dependenta Ci. Functia DIF determina daca exista o diferenta intre doua transformari succesive . Dam algoritmul chase in detaliu :

0 START a Chase s

1 INPUT a T , k , C1,C2,.,Cks

2 n

3 Tn T

4 d

5 WHILE d

5.1 d

5.2 FOR i 1 , 2 , k

5.1.1 CALL TR(Tn,Ci;T*)

5.1.2 IF DIF(Tn,T')

THEN

.1 nn+1

.2 TnT'

.3 d =0

. 5.1.3 CONTINUE

5.4 CONTINUE

6 OUPUT ATn}

7 STOP

Fie tabloul T din figura 1 si C AB C,ADC,*a BCD , ABCs}. Aplicand F-regula determinata de B C se obtine T1 din figura 2 . Aplicand J-regula *aABC, BCDs se obtine T2 din figura 3 . Aplicand F-regula determinata de AD C se obtine T3 din figura 4 .

T ( A B C D) ( A B C D ) ( A B C D ) (A B C D ) T*( A B C D )

Figura 1 Figura 2 Figura 3 Figura 4 Figura 5

Aplicarea J-regulii determinata de *aABC , BCDs lui T3 permite obtinerea lui T* si orice alta regula il lasa invariant . Astfel T* este ca relatie in SAT(C) .

Definitia 1: Se numeste secventa generata din T prin aplicarea regulilor ( F- sau J) determinate de dependentele din C , secventa T T,T1, . . . unde Ti+1 se obtine din Ti prin aplicarea unei F- sau J-dependente determinate de o dependenta din C , se presupune TiTi+1 . Daca secventa generata are un ultim element Tn astfel ca orice F- sau J-dependenta determinata de C aplicata nu-l mai schimba atunci Tn este numit chase-ul lui T in raport cu C . (T) reprezinta multimea chase-urilor .

Exemplul 2 : Fie T si C din exemplul 1. T , T1 , T2 , T3 si T* este o secventa generata din T de C si T*IChaseC(T) . Va trebui sa observam cum se transforma liniile pe parcursul aplicarii algoritmului Chase . Fie T' obtinut din T prin aplicarea unei J-reguli . Atunci daca w este o linie a lui T ei ii corespunde in T' aceeasi linie sau are in plus o linie obtinuta prin unirea unui numar de linii . Fie T' derivat din T prin aplicarea unei F-reguli care schimba variabila v cu variabila v' . Daca w este o linie in T ii corespunde in T' o linie w' care este de fapt w in care s-a inlocuit v cu v'. ( Daca w nu contine v atunci w w' ) .





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 792
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2023 . All rights reserved