TEORIA REPREZENTARII

In acest capitol sunt tratate criteriile care arata cand o descompunere a unei relatii determinata de o schema a unei baze de date este o reprezentare adecvata. Se introduce echivalenta prin date a schemelor bazelor de date. Aceste criterii sunt date la inceput pentru o multime arbitrara de relatii P, apoi se formuleaza rezultate suplimentare pentru cazul P=SAT(C).

1 Reprezentare adecvata

Vom introduce cateva notatii care vor fi folosite sistematic pe parcursul acestui capitol. Scopul este de a construi o reprezentare adecvata a elementelor multimii de relatii P. relatiile din P vor fi relatii de schema U.

Relatiile din Q le vom numi stari posibile (instantieri) pentru a le deosebi de relatiile care compun baza de date. Schema bazei de date va fi notata cu, R= unde U=R₁R₂.R_p. Multimea bazelor de date de schema R va fi notata cu D. Se pune problema reprezentarii instantelor din P prin baze de date din D si examinarea restrictiilor impuse schemei bazei de date pentru ca aceste reprezentari sa fie adecvate.

Definitia 1. Se numeste proiectie (transformare de proiectie) definita de schema R, notata p_R transformarea care face sa corespunda unei instante rI Q o baza de date dID, adica p_R=d, unde d= si p_Ri r_i 1≤i≤p.

Definitia 2. Transformarea care face sa corespunda unei baze de date dID o instanta din Q si este notata cu se numeste transformare de unire definita de R. Pentru baza de date d=ID d=r₁ r₂ r_p

Descrierea schemei este implicita in structura bazei de date d.

Exemplul 1. Fie si Daca r este instanta din figura 1, baza de date este , unde si sunt in figura 2 ; iar instanta s= d este data in figura 3.

r(A B C) = (A B ) (B C) s(A B C) '(B C)

3 5 1 3 3 5 1 3 5 9 8

1 4 6 1 4 4 6 1 4 5 3 9

2 4 5 2 4 4 5 1 4 6

2 4 6 2 4 5

2 4 6

Figura 1 Figura 2 Figura 3 Figura 4

Daca se considera in locul relatiei relatia ' atunci d= , adica instanta vida pe U.

Definitia3. Fie P Q. Se numeste imagine directa a lui P determinata de R, notata cu multimea: p_R(P)=.

Pentru usurinta scrierii vom renunta la p. Din definitia transformarii de proiectie rezulta ca pP pQ D. Ultima incluziune este stricta deoarece nu orice baza de date este proiectia unei stari admisibile oarecare din Q. Baza de date unde este dat in figura 1 iar este dat in figura 4, nu este proiectia nici unei instante cu schema ABC. Vom considera ca numai bazele de date din pQ pot candida pentru a reprezenta cu ele instante din P. Multimea pQ se compune din acele baze de date de schema R care se pot uni complet. In legatura cu aceasta, se pun urmatoarele intrebari:

sa se decida daca o multime de relatii se pot uni complet ?

bazele de date care nu se pot uni complet pot fi semnificative ?

sa se verifice daca o baza de date din pQ trebuie considerata in intregime ? Nu este

suficient sa consideram perechi de relatii in baze de date sau relatii individuale ?

Exemplu 2. Fie relatiile r₁, r₂ si r₃ din figura 5.

r₁ (A B)    r₂ (B C) r₃ (A C)

Figura 5

Acestea se pot uni complet daca le luam ca perechi, insa toate trei impreuna nu pot fi unite. In continuare sunt prezentate restrictiile impuse relatiilor care compun baza de date derivata din Q de inlaturare a acestor contradictii.

Definitia 4. Fie P Q. Multimea

CW_R(P)=, r_iIp_Ri(P)}

se numeste imagine pe componente a lui P determinata de R

Adica CW_R(P) consta din baze de date de schema R ale caror relatii sunt proiectii de instante din P dar nu in mod necesar ale aceleiasi instante. E clar ca pP CW_R(P) care in cele mai multe cazuri este stricta. Pentru reprezentarea lui P trebuie utilizate numai acele baze de date care sunt proiectii de instante pentru care imaginile pe componente sunt proiectii de instante din Q. Multimea acestor baze de date o vom nota cu L. Ea este data de:    L= CW_R(P)∩pQ. Este clar ca pP L si pP pQ

Relatiile de incluziune intre multimile introduse la momentul actual sunt aratate in figura 6.

pQ

P D

Q

pP

P

Figura 6 L

Definitia 5. Daca N D atunci N= .

Notiunea de reprezentare adecvata a fost introdusa de Rissanen / /.

Definitia 6. Schema bazei de date R descompune relatiile din P in componente independente daca au loc urmatoarele doua proprietati:

IC1: Daca dIL atunci exista cel mult o instanta rIP cu pr=d.

IC2: Daca dIL atunci exista cel putin o instanta rIP cu pr=d.

Proprietatea IC1 se numeste proprietate de reprezentare unica. Proprietatile IC1 si IC2 impreuna constituie conditia de componente independente. Conditia de componente independente impune ca transformarea p : P L sa fie bijectiva.

Se poate transcrie IC1 si IC2 ca o singura conditie, dar cum in continuare IC1 se va folosi in alte determinari ale adecvarii, le-am formulat separat. Observam ca IC2 este adevarata daca si numai daca pP=L. Conditia de componente independente provoaca greutati cand vrem sa revenim de la baza de date la instanta caci transformarea inversa a lui p e greu de calculat. Conditiile IC1 si IC2 nu cer ca sa fie inversa lui p. Este foarte posibila situatia reprezentata in figura 7.

Q pQ

P p L pP

p

Figura 7

Exemplul 3. Fie: U=ABC, R=.

P se compune din asemenea stari admisibile ce satisfac urmatoarea conditie: pentru orice pereche de tupluri si din r determina

Unirea unei baze de date din pQ poate sa nu fie o instanta din P.

Urmatoarea notiune de adecvare a fost introdusa de Arora si Carlson / /.

Definitia 7. Schema bazei de date R descrie o descompunere care conserva informatiile din P daca ea are urmatoarele proprietati:

AC1. Pentru dIL exista cel mult o instanta rIP astfel ca p(r)=d;

AC2. Daca instanta rIQ este proiectata in L, adica p(r)IL rezulta atunci ca rIP.

Proprietatea AC2 se numeste restrictie de conservare. AC1 si AC2 constituie o conditie de conservare a informatiei.

Definitia 8. Pentru orice submultime N pQ se numeste preimagine a lui N, notata N , multimea : N

Multimea care ne intereseaza este . Relatia dintre si alte multimi este aratata in figura urmatoare

D pQ

Q

L

P

pP

Figura 8

Lema 1. AC2 este echivalenta cu proprietatea

Demostratie Presupunem ca are loc AC2. Pentru orice , p(r)IL, atunci din AC2 rezulta ca rIP deci . Deoarece , rezulta ca .

Presupunem ca . Pentru orice instanta , unde p(r)IL rezuLta ca rIP Deci AC2 este satisfacuta.

Observatie. determina L=pP. Din aceasta rezulta consecinta care leaga conditia de componente independente de conditia de conservare a informatiei.

Corolar 1. AC2 implica IC2, prin urmare AC1 si AC2 implica IC1 si IC2.

Observatie. In sens invers implicatia nu este adevarata.

Din proprietatile AC1 si AC2 rezulta ca, putem reprezenta orice instanta rIP printr-o baza de date dIL si de asemenea rezulta ca d nu este posibil sa reprezinte o alta instanta din Q-P. Conditia de conservare a informatiei specifica faptul ca exista inversa transformarii p

Definitia Multimea de instante P satisface proprietatea de unire fara pierderi (LJ) determinata de schema bazei de date daca P FIX(R). Adica unirea lui p(r)=r pentru orice rIP.

Observatie. Intotdeauna

Lema 2. Proprietatea LJ implica proprietatea IC1.

Demonstratie. Presupunem ca LJ are loc. Fie instantele . Daca . Din proprietatea LJ rezulta r= p(r)). Prin urmare IC1 este corecta.

Corolar2. LJ si AC2 implica AC1 si AC2.

Lema 3. Proprietatile AC1 si AC2 implica LJ.

Demonstratie. Presupunem ca sunt indeplinite conditiile de conservare a informatiei. Fie si d=p(r). Aratam ca (d) este de asemenea o instanta astfel ca Deoarece dIL din AC2 rezulta ca (d)IP. AC1 implica (d) =r deoarece p(r)= =p (d) Prin urmare r= (d) care este proprietatea LJ.

Teorema 1. Daca AC2 este adevarata atunci proprietatile AC1 si LJ sunt echivalente.

Adica in conditiile de conservare a informatiei este inversa lui p pe P.

Exemplul 4. Fie F-dependenta asigura ca proprietatea LJ are loc. Daca instanta r satisface atunci satisface . Invers, satisface , atunci r va satisface . De aceea daca pentru instanta r, atunci . Multimea P satisface proprietatea AC2, deci este indeplinita conditia de consevare a informatiei.

Dupa cum am observat chiar in conditiile indeplinirii proprietatilor IC1 sI IC2 transformarea inversa de la baza de date la instante poate sa nu fie usor de calculat. Am vazut ca din proprietatile AC1 sI AC2 rezulta ca aplicatia de unire este inversabila dar pentru aceasta trebuie sa verificam ca p(r) nu apartine lui L pentru rIQ-P. Vom prezenta o conditie intermediara intre conditia de componente independente si conditia de conservare.

Definitia 10. Vom spune ca schema bazei de date R satisface conditia de unire (join) pe P daca au loc urmatoarele proprietati :

J1) Aceeasi ca IC1;

J2) Pentru orice baza de date dIL, dIP.

Observatie : J1 si J2 cer ca sa fie transformare inversa a lui p pe P.

Daca rIP atunci p(r)IL. Din J2 rezulta m_R(r)IP dar p(m_R(r))=p(r), iar din J1 m_R(r)=r. Vom arata ca proprietatea LJ are loc pe multimea P. Conditia de unire atrage dupa sine ca, orice baza de date dIL poate fi reprezentata printr-o instanta maximala rIP astfel ca d=r

Lema 4. Proprietatea J2 are loc daca si numai daca FIX(R) L P.

Demonstratie Necesitatea. J2 poate fi scrisa ca L P.

Fie rIFIX(R) L . Deoarece rIL rezulta ca p(r)IL si rIFIX(R), r= p(r) astfel ca rI L. Prin urmare rIP, deci FIX(R) L P.

Suficienta. Presupunem ca FIX(R) L P si ca r este o instanta rI L, atunci exista o baza de date dIL asfel incat r= d. Deoarece FIX(R) L P atunci d=p(r), m_R(r)= p(r)= dIFIX(R). Prin urmare rIFIX(R), deoarece dIL atunci rI L Din ipoteza ca rIP rezulta ca L P.

Comparam conditiile de componente independente cu conditiile de conservare a informatiei.

Lema 5. Din proprietatea J2 rezulta IC2

Demonstratie Presupunem J2 adevarata, adica L P atunci pentru orice dIL exista rIP astfel incat d=r.

s p

s'

r' p

Figura 9

P

r

Teorema 2. Din proprietatile AC1 si AC2 rezulta J1 si J2, din care la randul lor

rezulta IC1 si IC2.

Demonstratie. Presupunem ca AC1 si AC2 sunt indeplinite. Atunci J1 este adevarata. Pentru a dovedi ca J2 este adevarata vom lua o instanta arbitrara rI L. Fie atunci din AC2 rezulta ca rIP prin urmare L P deci J2 este indeplinita. Restul implicatiilor rezulta din lema 5. Atunci cand se compara AC1 si AC2 cu J1 si J2 se observa ca toate cer realizarea conditiei LJ , iar AC2 impune in timp ce din J1 si J2 rezulta ca P este o submultime proprie a lui L

}i in ambele conditii nu pot sa existe r si r' aratata in figura 9 dar pot sa existe s si s' dar nu pot satisface conditiile AC1 si AC2.

Exemplul 5. Fie . Atunci L se compune din doua perechi de relatii care se unesc complet pe AB si BC si este reformularea lui astfel ca R satisface LJ si deci J1. Reuniunea a doua relatii cu schema AB si BC satisface rezulta ca J2 e adevarat. AC2 nu se satisface deoarece orice instanta r satisface p(r)IL rezulta P Q. Este posibil ca rIP astfel incat

Definitia 11. Schema bazei de date R conserva (pastreaza) P daca are loc proprietatea :

PR. Pentru orice instanta rIP atunci m_R(r)IP adica m_R(P) P unde m_R(P) = p(P).

Lema 6. Proprietatea J2 implica proprietatea PR. Invers nu e adevarat.

Demonstratie. Din L=P rezulta ca pentru orice rIP avem m_R(r)IP.

Exemplul 6. Fie U=ABC, R= P=SAT(A B,B A)

Fie P SAT(B A) , atunci , adica PR e adevarata. Sa examinam baza de date unde relatiile si sunt prezentate in fig. 10. Baza de date d este in L deoarece date in fig. 11. E usor de vazut ca starea admisibila (d) data in fig. 12 nu este in P astfel J2 nu e adevarat.

(A B) (B C) S (A B C) S (A B C) (d) (A B C)

3 5 1 3 5 1 3 5 1 3 5

1 4 3 6 1 4 5 1 3 6 1 3 6

2 4 4 5 2 4 5 2 4 5 1 4 5

4 7 2 4 7 1 4 7

2 4 5

2 4 6

2 4 7

Figura 10 Figura 11 Figura 12

Lema 7. Proprietatile PR si IC2 implica proprietatea J2.

Demonstratie. Fie rI L si d o baza de date din L, astfel ca r= d, din IC2 avem pP=L astfel ca dIpP. Fie r' o instanta din P astfel ca p(r')=d. Atunci din PR rezulta . Prin urmare L P si J2 este adevarata.

Corolar 3. Proprietatile IC1, IC2 si PR sunt indeplinite daca si numai daca J1 si J2 sunt indeplinite.

Observatie. Putem inlocui IC1 si PR cu LJ.

Lema 8. Proprietatea LJ implica proprietatea PR.

Demonstratie. Din

Teorema 3. Conditiile LJ si IC2 sunt adevarate daca si numai daca J1 si J2 sunt adevarate.

Demonstratie. Din lema 2 rezulta ca LJ implica IC1. Din lema 8 rezulta ca LJ implica PR. Prin urmare din corolarul teoremei 2 si lema 7 LJ si IC2 implica conditiile de unire. Din teorema 2 rezulta ca J1 si J2 implica IC2. Din J1 si J2 rezulta de asemenea LJ prin urmare din J1 si J2 rezulta LJ si IC2.

Vom studia acum ce fel de proprietati trebuie adaugate la conditiile de unire ca sa obtinem un sistem de conservare a informatiei.

Definitia 12. Schema bazei de date R satisface proprietatea S daca

Teorema 4. Proprietatile J1, J2 si S au loc daca si numai daca AC1, AC2 au loc.

Demonstratie '< '. Din teorema 2 rezulta ca AC1 si AC2 implica J1 si J2. Din lema 1 proprietatea AC2 cere ca . Din lema 3 AC1 si AC2 implica proprietatea LJ astfel ca P FIX(R). Prin urmare L =P FIX(R) care implica proprietatea S.

>'. Se arata ca J2 si S implica AC2. Fie r o instanta din L unde p(r)=d, pentru dIL. Din J2 rezulta ca dIP. Din AC2 este adevarat.

Diferenta intre conditiile de unire si conditiile de conservare necesita sau mai strict . In multe cazuri ne intereseaza situatiile cand P este descrisa de o multime de restrictii C. In acest caz este echivalenta cu . Se cunoaste un astfel de procedeu de verificare a conditiilor C daca acestea sunt formate din dependente functionale si dependente multivoce. Conditia este aceeasi cu Unde am utilizat p_C pentru proiectia restrictiilor C pe R.

2 D-echivalenta schemelor bazelor de date

Se spune despre schemele R si S ca sunt echivalente daca T_R(r)=T_S(r) pentru orice instanta r din P. Schemele R si S sunt echivalente pe P in cazul cand transformarile T_R(r) si T_S(r) restrictionate la P coincid (adica cand descompunerea determinata de R a starii admisibile rIP are aceleasi pierderi de informatii ca si descompunerea determinata de S). Ne intereseaza doar acele instante care prin descompunere nu pierd informatii.

Definitia 13. Fie R o schema a unei baze de date si P o multime de instante posibile de schema R. Se numeste multime de puncte fixe determinata de R in P multimea :

Definitia 14. Schemele bazelor de date R si S sunt d-echivalente pe P (se noteaza ) daca

Pentru verificarea d-echivalentei (echivalenta determinata de datele din P) trebuie demonstrate doua incluziuni. Mentionam ca incluziunea se realizeaza atunci cand .

Lema Echivalenta determina .

Demonstratia este lasata cititorului.

Observatie: Reciproca lemei 8 nu este adevarata.

Exemplul 7 Fie U ABCD, iar R= si S= scheme de baze de date. Daca P este compusa din doua relatii r si s date in figura 1, atunci R si S sunt d-echivalente (echivalenta determinata de datele din P). Instanta r se descompune fara pierderi fata de R si fata de S, in timp ce s se altereaza la descompunere. Dar T_R si T_S nu sunt echivalente pe P, deoarece s'=T_R(s) nu coincide cu s"=T_R(s) (figura 2).

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

1 3 6 8 2 3 6 7 2 3 6 7 1 3 6 7

2 4 6 8 2 4 6 8 2 4 6 7 2 3 5 7

2 3 6 8 2 3 6 7 2 4 6 8 2 4 6 8

Figura 1 Figura 2

Definitia 15. Fie R o schema de baza de date. Submultimea a lui P determinata de R, se conserva (prezerva) in P

Conditia de conservare a lui P, este

Observatie :

Teorema 5. Fie R si S doua scheme de baze de date si P o multime de instante. Presupunem ca exista o multime de instante P' care satisface conditia:

atunci are loc pentru orice .   

Demonstratie. Necesitatea. Fie r instanta arbitrara din P'. Deoarece rezulta ca s=m_R(r) este in P. Dar PJ-tranformarea este idempotenta, deci s este in si, in consecinta sI . Din ipoteza sI . Dar , asa ca . Deoarece atunci m_S(s)=s. Combinand ambele inegalitati rezulta .

Suficienta. Fie r o relatie din ; atunci '. Din ipoteza , dar m_R(r)=r deci m_S(r) r, dar si m_S(r) r deci rIFIX(S) Astfel,

Corolar 4. Urmatoarele trei afirmatii sunt echivalente:

1)

2) pentru K=FIX_P(R);

3) pentru K=PRES_P(R);

Demonstratia rezulta din teorema 1.

Corolarul 4. Daca R si S sunt scheme de baze de date si R conserva P, atunci este echivalenta cu

Demonstratia se obtine direct din echivalenta afirmatiilor 1) si 3) corolarul 1.

Teorema 6. Daca R si S sunt scheme de baze de date care conserva P, atunci daca si numai daca

}tim deja ca atat conditia de unire cat si conditia de conservare a informatiei cer indeplinirea proprietatii PR. De aceea, in cazul determinarii a adecvarii reprezentarii putem alege oricare din aceste conditii.

Verificarea adecvarii reprezentarii si a echivalentei determinata restrictii

Conditiile de unire si de independenta pe componente sunt echivalente in cazul cand, unirea transforma o baza de date din L intr-o relatie din Q. Diferentele intre conditiile de unire si conservare a informatiei constau in verificarea incluziunii P FIX(R) sau a unei conditii mai stricte ca . Daca P este SAT(C), pentru o multime oarecare de restrictii C, aceste conditii se exprima ca si p_C Amintim ca pC este notatia neformala a proiectiei restrictiilor din C pe R, adica a restrictiilor care determina multimea . In acest fel p_C se compune din acele restrictii care satisfac p(r) ( pentru orice si RIR

Am determinat p_C anterior, astfel ca L =SAT(p_C). Una din greutatile introducerii determinarii formale este aceea ca restrictiile din p_C nu se exprima obligatoriu prin aceleasi tipuri de dependente ca si restrictiile din C. Deseori in p_C se intalnesc dependente de acelasi tip ca si in C, dar acolo pot apare dependente si de alt tip.

Exemplul 8. Fie U=ABCDE, R=ABCD, P=SAT(A E, B E, CE D).   

Multimea F-dependentelor pe care trebuie sa le satisfaca proiectia p(r) pentru un r arbitrar din P este . Sa examinam relatia s data in figura 1. Relatia sISAT(F), dar s nu este proiectia nici unei instante din P. Daca sunt tupluri din p(r) astfel incat :

atunci :

Aceasta dependenta nu este echivalenta cu nici o multime de F-dependente. Observam ca s nu satisface aceasta dependenta.

s (A B C D) s (A B C)

1 3 5

2 4 5 8 1 4 6

1 4 6 8 2 4 5

Figura 1 Figura 2

Exemplul Fie U=ABCD, R=ABC, P=SAT

Proiectiile p(r) pentru un r arbitrar din P satisfac numai MV-dependentele triviale. Relatia s data in figura 2 nu este proiectia nici unei instante din P.

4. Cazul cand P este definita numai de dependente functionale

S-a aratat mai sus ca in determinarea lui p_C, si in verificarea incluziunii exista anumite greutati. In cazul cand C este compus doar din F-dependente este suficient sa se examineze aceleasi dependente din p_C

Teorema 7. Daca P=SAT(F) pentru o multime F de F-dependente atunci conditiile de componente independente, unire si conservare a informatiilor sunt echivalente.

Demonstratie. Din teorema 2 este suficient sa aratam ca, daca AC1 sau AC2 nu sunt indeplinite, nu vor fi indeplinite nici IC1 si nici IC2. Este evident ca neindeplinirea lui AC1 duce la neindeplinirea lui IC1. Sa presupunem ca AC2 nu este indeplinita, adica . Fie r o instanta din . Se poate presupune ca r este compus numai din doua tupluri. Deoarece relatia r nu satisface F exista o F-dependenta X A care rezulta din F. Deoarece in r sunt numai doua tupluri, ele trebuie sa coincida pe X si sa se deosebeasca in A, adica r are valori ce coincid in coloanele X si doua valori in coloana A. Daca IC2 nu este indeplinita, atunci totul este demosntrat. Sa presupunem ca este indeplinita. Fie d=p(r). Baza de date d este in L. Din IC2 rezulta ca in P exista o instanta r, astfel ca p(r')=d. Relatia r' in fiecare din coloanele X poate avea doar o singura valoare. Dar r' trebuie sa aiba doua valori in coloana A, din aceasta cauza r' contrazice . In consecinta r P si IC2 nu este adevarata. Sa examinam acum verificarea conditiilor de unire in cazul cand P=SAT(F), unde F este o multime de F-dependente. Vom verifica proprietatile LJ si J2. Proprietatea LJ se scrie ca . Ea se verifica cu ajutorul algoritmului chase. Examinam numai verificarea lui J2 adica L P.

Definitia 16. Fie R schema bazei de date, F o multime de F-dependente. Vom numi restrictie a lui F la R multimea tuturor dependentelor din F+, care sunt aplicabile la o schema de relatie R din R. Vom nota aceasta multime

Exemplul 10. Fie U=ABCD, R=, F=.

F-dependentele netriviale din sunt: , BC A, BC AB, BC AC, BC ABC, AB C.

Reamintim ca F este constransa (enforceable) la R daca sF.

Lema 10. Fie P=SAT(F), unde F este o multime de F-dependente. Proprietatea J2 este indeplinita daca si numai daca FsF_R

Demontratie Necesitatea. Vom arata ca daca F s F_R, atunci in L exista o baza de date d, astfel incat d PL Fie si nu este in . Fie Z inchiderea lui X in raport cu G. Este clar ca . Construim instanta din Q dupa cum urmeaza. Ea va fi compusa din doua tupluri: compus din 0 si cu 0 in partea Z si cu 1 in rest. Se vede ca nu apartine lui P. Fie d=p(r_X). Instanta nu este in P deoarece . Vom arata acum ca orice relatie din d este proiectia unei instante din P. Fie RIR. Definim instanta r_R din P astfel incat p_R(r_X)=p_R(r_R). contine doua tupluri: I si t_X compus doar din 1 in afara de locurile din pe F, in care se afla 0. Instanta nu contrazice pe F, deoarece ar fi incorect definita. Pentru a arata ca p_R(r_X)=p_R(r_R) trebuie aratat ca (aceste multimi sunt compuse din coloane in care p_R(r_R) si p_R(r_X) contin cate doua simboluri). Sa presupunem ca B este un atribut continut doar de prima multime. Este clar ca . Deoarece , atunci . Dar atunci astfel ca si in consecinta BIZ R. Am obtinut o contradictie deoarece dIP ceea ce inseamna ca J2 nu este indeplinita.

In continuare vom descrie un procedura de complexitate polinomiala care permite sa verifice daca F este constransa la R. Algoritmul 1 calculeaza in raport cu . Incluziunea din pasul 2.1.1 se va face in raport cu F.

Procedure PCLOSURE (F,R,X;Y)

Y: X

Z=O

WHILE(Y Z)    3.0 Z=Y

3.1 FOR fiecare RIR

Y:=((Y R)⁺ R) Y

3. return (Y)

Exemplul 11. Fie U=ABCDE, R=, F=.

Atunci PCLOSURE(F,R,A;ABC). Remarcam ca pe F este ABCDE.

Teorema 8. PCLOSURE(F,R,X; ) calculeaza in raport cu .

Demonstratie. Fie Y multimea returnata de procedura. Atunci Y este o submultime a lui si ramane astfel pe parcursul aplicarii procedurii deoarece F-dependenta care se foloseste in pasul 2.1.1 este in (aceasta este (Y R) (Y R)⁺ R, unde incluziunea se face in raport cu F). Vom arata ca orice atribut din se va adauga la Y. Fie H un graf aciclic orientat derivat din al lui . Sa presupunem ca sunt reperele varfurilor grafului, numerotate in ordinea in care apar in constructia lui . Afirmam ca dupa sfarsitul iteratiei i a ciclului while, . Se observa ca . Sa presupunem ca la trecerea de la la s-a folosit F-dependenta . Deoarece este in , exista o schema de relatie RIR astfel ca . Mai mult decat atat, astfel ca la inceputul iteratiei (i+1). Cand se termina ciclul for ajungem la R, iar V apare ca submultime a lui atunci W (Y R)⁺ R deoarece . Inseamna ca W se adauga la Y si fiecare atribut care se adauga la la trecerea spre se adauga respectiv la Y. Prin urmare, cand procedura se termina astfel ca

Lema 11. Ordinul de complexitate al procedurii PCLOSURE este O(|U|*|R|*||F||) unde ||F|| este numarul tuturor F-dependentelor din F.

Demonstratie: Ciclul while din pasul 2 nu se poate realiza mai mult de ori deoarece Y nu poate deveni mai mare decit U. Pentru fiecare iteratie a ciclului while, ciclul for din pasul 2.1 se realizeaza de ori. Pasul 2.1.1 care calculeaza se realizeaza intr-un timp liniar dupa . In consecinta durata totala a calculului are valoarea O(|U|*|R|*||F||).

Teorema 8. Fie F este o multime de F-dependente si P=SAT(F). Timpul de verificare a unei conditii de unire este polinomial in raport cu si

Demonstratie. Conform celor afirmate anterior, timpul de verificare al proprietatii LJ este polinomial. Dupa lema 2 proprietatea J2 este adevarata daca . Pentru verificare este nevoie doar de a arata ca , ceea ce se poate face utilizand algoritmul PCLOSURE pentru fiecare dependenta din F prin testarea incluziunii Y Acest test implica apelari ale procedurii PCLOSURE care are complexiate polinomiala.

Urmatoarele doua exemple demonstreaza ca proprietatile LJ si J2 sunt independente pe P, daca aceasta este descrisa de o multime dependente functionale.

Exemplul 12. Fie U=ABC, R=, P=SAT().

Proprietatea LJ este indeplinita pentru aceste date deoarece A C, dar proprietatea J2 nu este indeplinita deoarece nu are loc, prin urmare F nu este constransa la R.

Exemplul 13. Fie U si P aceleasi ca in exemplul anterior si . Atunci F este aplicabila la R si prin urmare constransa la R, deci proprietatea J2 este indeplinita. Se observa ca LJ nu este adevarata deoarece nu are loc.

5 Cazul cand P este determinata de dependente functionale si multivoce

Anterior s-a aratat cum se verifica conditia de unire daca P este definit de o multime de dependente functionale. Acum se va da o procedura de verificare a acestor conditii in cazul cand unde C se compune din F-dependente si din MV-dependente, iar R este schema bazei de date in FN4. Este necesara verificarea proprietatilor LJ si J2. Verificarea proprietatii LJ se reduce la definirea, cu ajutorul algoritmului chase, a corectitudinii relatiei . Pentru verificarea proprietatii J2 este necesar sa se verifice daca este adevarata incluziunea L P ceea ce in limbajul dependentelor apare ca pC S-a aratat deja ca verificarea implicatiei din p_C provoaca greutati. Vom arata ca in cazul cand R este o schema in FN4, este suficient sa se verifice ca , unde F este multimea F-dependentelor care rezulta din C.

Lema 12. Fie R o schema de baza de date in FN4 si P=SAT(C), unde C este o multime de F- si MV-dependente. Fie F omultime de F-dependente care rezulta din C, iar o F-dependenta din F care nu rezulta din si . Atunci nu rezulta din pC si (adica orice instanta din contrazice

Demonstratie. Pe parcursul demonstratiei cu simbolul , unde V este o submultime a lui U, vom nota o instanta compusa dintr-un tuplu format doar din 0 si din a al doilea tuplu format din 0 pentru atributele din V si 1 in rest. Se poate considera ca in raport cu si deoarece si nu atrage dupa sine , deci va contrazice si . Fie r_X instanta determinata mai sus, iar d baza de date p(r_X). Deoarece , iar r_X contrazice , atunci si d contrazice . Trebuie demonstrat ca d este in L. Vom arata ca d este in L. Pentru aceasta vom arata ca fiecare relatie din d este proiectia unei instante. Fie R o schema de relatie din R, Y=R X, iar ( 0-urile le consideram ca variabile principale iar 1-urile ca secundare). Multimea coloanelor din , formate doar din 0 va coincide cu Y⁺ in raport cu C. Dar Y⁺ R=R X deoarece pentru un atribut BIY⁺, F-dependenta Y B este in F, si in consecinta, este in , astfel BIX. Sa presupunem ca p_R(r_X) p_R(r^*). Atunci in r^* trebuie sa fie tuplu t ale carui 0-uri sunt pe locurile din W unde . Din teorema chase-ului pentru MV-dependente, Y W, astfel ca Y R W se realizeaza pe R. Dar relatia nu este indeplinita (deoarece ). De aceea nu este indeplinita nici . Inseamna ca R nu este in FN4, ceea ce contrazice conditia. De aceea proiectiile amintite mai sus trebuie sa coincida si in consecinta dI L.

Lema 13. Fie R o schema de baza de date in FN4, iar P=SAT(C), unde C este o multime F-dependente si MV-dependente. Sa presupunem ca LJ este indeplinita. Fie F o multime de F-dependente care rezulta din C, iar MV-dependenta X―Y rezulta din C si nu rezulta din si . Atunci X Y nu rezulta din pC si

Demonstratie. Sa presupunem ca Y este o multime minimala care satisface ipotezele, adica nici o submultime proprie Y' a multimii Y nu satisface concomitent conditiile X-―Y' si X―Y. Sa presupunem ca X este multimea maxima satiface ipotezele. Atunci , in raport cu si ca si in demonstratia lemei 12 si nici o submultime proprie Z a multimii U-XY nu satisface concomitent conditiile XZ―Y si XY―Y. Notam cu aceeasi relatie ca in demonstratia lemei 1. Este clar ca satisface . Afirmam ca satisface de asemeni si . Presupunem ca nu este asa atunci algoritmul chase aplicat la in raport cu si va adauga la noi tupluri. Fie t unul din tuplurile adaugate. Vom nota cu XW multimea de atribute in care t este egal cu 0, caz in care . Conform teoremei chase-ului pentru MV-dependente, X―Y. Conform proprietatii LJ avem astfel ca X―Y. Evident ca . Daca , atunci XZ―Y unde . Multimea Z nu este vida deoarece . Dependenta XZ―Y nu rezulta din si deoarece XZ―Y si X―Y implica X―Y (aceasta este usor de verificat cu ajutorul algoritmului chase). De aceea contrazice maximalitatea lui X. Daca , atunci contine Y si X―W' ceea ce ce conduce la contrazicerea aceealesi ipoteze. Singura posibilitate ramasa este ca Y sa se intersecteze partial cu W. Fie , iar . Atunci . Dar din si nu poate sa rezulte concomitent X―Y' si X―Y" deoarece din ele rezulta prin aditivitate X―Y ceea ce contrazice minimalitatea lui Y. De aceeea aplicarea algoritmului chase la si nu adauga noi tupluri si inseamna ca satisface in raport cu . A mai ramas de aratat ca baza de date d=p(r_X) este in L ceea ce determina faptul ca d= r_X sa fie in L. Deoarece in raport cu si din demonstratia lemei 1 rezulta ca dIL.

Noi am obtinut un procedeu de verificare a conditiilor de unire pentru scheme de baze de date in FN4 si multimi de instante P, determinate de o multime de F- si MV-dependente. Mai exact, la inceput, prin folosirea algoritmului chase se verifica proprietatea LJ, adica . Apoi trebuie gasita o multime de dependente functionale ce rezulta din C sau o acoperire a sa. Din pacate pentru aceasta nu se cunoaste nici o metoda cu exceptia verificarii. Urmatorul pas consta in a-l determina pe . Folosind algoritmul chase se poate verifica indeplinirea conditiei J2 pe calea verificarii . Acest proces nu este atat de eficient ca in cazul cand C este compus numai din F-dependente. Sa remarcam ca in cazul in care C este compus din F-dependente si J-dependente, iar schema R este arbitrara, in general nu se cunoaste nici o metoda de verificare a conditiei de unire.

Exemplul 14. Fie U=ABCD, R=,C=.

Multimea de dependente acopera unde F este multimea deF-dependente care rezulta din C. De aici . In afara de aceasta si determina pe C deoarece conditia de unire este realizata in acest caz.

Exemplul 15. Fie U=ABCDE, R=,C=.

Multimea dependentelor acopera , dar impreuna cu nu determina pe C deoarece conditia de unire nu este indeplinita.

6 Verificarea echivalentei determinata de date

Pentru a verifica R _PS unde P=SAT(C), R si S scheme de baze de date, este necesar sa se determine daca este indeplinita egalitatea . Dupa cum s-a observat, se realizeaza cand . Aceasta incluziune este echivalenta cu conditia care se poate verifica folosind algoritmul chase in cazul cand C este compusa din F-dependente si J- dependente.

Lema 14. Fie schemele de baze de date R si S si C o multime de F-si J-dependente. Sa presupunem ca . Atunci daca si numai daca

Observatie : Lema 14 este utila deoarece este foarte usor de verificat. Ca sa demonstram aceasta incluziune este necesar sa gasim C-transformarea din in . Deoarece in variabilele principale nu se repeta, este necesar doar sa se verifice daca pentru orice linie w din exista o linie w' din care include w.

(A B C D E) (A B C D E) T (A B C D E)

a₁ a₂ a₃ b₁ a₅ a₁ b₁ a₃ b₂ a₅ a₁ a₂ a₃ b₁ b₂

b₃ a₂ a₃ a₄ a₅ b₃ a₂ a₃ a₄ b₄ b₃ a₂ b₄ a₄ b₅

b₅ b₆ b₇ a₄ a₅ a₁ a₂ a₃ b₆ a₅

b₃ b₆ a₃ a₄ a₅

b₅ a₂ b₇ a₄ a₅

Figura 1 Figura 2 Figura 3

Exemplul 16. Fie U=ABCDE, S=, R=,

C= si P=SAT(C).

In figurile 1 si 2 sunt date . Avem C-transformarea din in astfel incat . Dar nu exista C-transformare din in , astfel ca .

Stim ca este echivalenta cu cand R si S prezerva . Daca multumea C este compusa numai din F-dependente putem aplica la si algoritmul chase. Fie si rezultatele aplicarii algoritmului chase. Incluziunile se pot verifica deoarece C-transformarile respective se pot determina usor in aceste cazuri.

Definitia 16. Fie T un tablou. Vom spune ca T descrie F-dependenta daca exista o linie in T care are variabile principale exact in coloanele XY. Tabloul T descrie o multimea de F-dependente daca fiecare F-dependenta din aceasta multime este descrisa de T.

Este evident ca, multimea de F-dependente este constransa la schema bazei de date R daca si numai daca descrie orice acoperire G ale multimii F.

Exemplul 17. Tabloul T dat in figura 3 descrie multimea de F-dependente

Teorema Fie R o schema de baza de date si F o multime neredundanta de F-dependente. Schema R conserva SAT(F), (FIX(R)=SAT(F)) daca si numai daca T*_R=chase_F(T_R) descrie F.

Pentru demonstatie vezi Maier/ /. Aceasta teorema sta la baza algoritmului de verificare a propietatii de conservare.

START

INPUT R, F

Call TR(R: T_R) //procedura genereza //

Call Chase_F(T_R:T*,m)

d

FOR fiecare X Y din F

5.1 w

5.2 i

5.3 WHILE i m si w=0

5.3.1 IF t_i(XY)=variabile principale

THEN

. 1 w

ELSE

. 2 i i+1

5.3.2 Continue

5.4 IF w=0

THEN

5.4.1 d

5.5 Continue

6. CASE d OF

6.2 OUTPUT

6.2 OUTPUT

7. STOP