TEMA PBD

UNIVERSITATEA "POLITEHNICA"

FACULTATEA DE AUTOMATICA SI CALCULATOARE

TEMA PBD

P1. Se da schema de relatie R = ABCDEFG si o realizare a acesteia. Se cere:

a) Sa se analizeze R si r si sa se evidentieze eventualele dependente multivaluate si dependente functionale;

b) Sa se stabileasca daca R este 828b15i in FN4 si sa fie evidentiate eventualele anomalii;

c) Sa se descompuna R pentru a fi adusa la FN4. Sa fie analizat rezultatul din punctul de vedere al DMV.

Rezolvare

a) Din realizarea relatiei r, se poate observa ca apar niste DF si DMV:

A à B, CàDE, FàG. Deci vom avea si DMV AààB, CààDE, FààG, folosind axioma 7.

Incercam sa gasim si alte DMV, pe langa cele evident obtinute din DF existente:

ABààCDE. Consider tuplurile 2 si 3:

Exista tuplul 1,

care are AB aceleasi ca 2 si 3, CDE este ca la 3, si R-CDE este ca la 2. Mai exista si tuplul 4,

cu aceeasi proprietate.

din ABààCDE rezulta ABààR- , deci ABààFG

Din modul in care este construita tabela, si din definitia formala a DMV de tip XààY, se observa ca trebuie sa am 3 tupluri in care X e identic. Singurele X care pot verifica asta sunt A,B,AB. Iar tuplurile de la care se porneste sunt 2,3 si apoi se analizeaza daca 1, 4 respecta conditia din definitia formala.

BààFG, BààCDE, si analog se mai obtin si AààFG, AààCDE.

b) Daca R ar fi in FN4, orice DMV netriviala ar avea in partea stanga o supercheie.

In primul rand, sa identificam o cheie pentru R. Pornind de la multimea de DF observabile, , se obtine evident cheia ACF. Alegand o DMV netriviala, de exemplu ABààCDE, se observa ca AB nu e supercheie pentru ACF, deci R nu este in FN4.

Din aceasta cauza pot sa apara unele anomalii, de exemplu:

- redundanta informationala:

* se stocheaza pentru fiecare tuplu B, desi el e unic determinat de A, care e identic la tuplurile din aceasta realizare.

* se stocheaza pentru fiecare pereche ACF si atributul E (sau D) care e unic determinat de C, si apare iar redundanta. Mai mica decat in primul caz, dar e prezenta.

- anomalia de actualizare: apare daca modific in tuplul 1 valoarea atributului D, de exemplu, pentru ca va trebui modificata automat si valoarea D din tuplul 3, pentru a pastra consistenta.

- anomalia de inserare: nu pot adauga o noua valoare pentru C, fara a adauga valori si pentru A si F. (sau alte combinatii de pana la doua atribute din cheia primara ACF).

- anomalia de stergere: daca se sterg tuplurile 2 si 4, pentru a sterge combinatia ACF (1, 40, 3), se pierde si informatia despre BDEG (2, 50, 60, 4).

c) pentru a aduce R la FN4, avem in vedere multimea de DF netriviale si cheia initiala ACF, R = ABCDEFG. Multimea de DF este

pas 1. aleg DMV AààCDE, pentru ca nu respecta conditia ca A sa fie supercheia lui ACF.

rezulta ρ=.

pas2

pentru ACDE: cheia este AC, multimea DF iar multimea DMV este

pentru ABFG: cheia este AF, multimea DF iar multimea DMV este

In cazul ACDE aleg DMV CààDE, pentru ca C nu e supercheie AC (iar cealalta DMV e triviala pentru ca A U = ACDE, schema completa). Obtin ρ=.

CDE este in FN4 pentru ca singura DMV din ea e CààDE, care e triviala (oricum, C e supercheie a cheii C, deci se respecta conditia si asa).

AC este in FN4 pentru ca nu am DMV sau DF pe ea (A si C sunt independente), iar cheia va fi AC.

pas 3. aleg BààFG, pentru ca B nu e supercheie a lui AF.

Obtin ρ=.

Pentru AB, multimea DF este , deci A este cheie, iar multimea DMV este , deci e triviala, si rezulta AB in FN4.

Pentru BFG, multimea DF este , deci BF cheie, iar multimea DMV este . FààG este singura DMV netriviala, iar F nu e supercheie, deci.

pas 4 Descompun BFG, cu DMV FààG, si obtin ρ=.

FG e in FN4, pentru ca FààG e triviala, si nu am alta DMV

BF e in FN4, pentru ca nu am DMV pe ea.

Deci am obtinut descompunerea ρ=, in care DMV pe fiecare schema sunt:

CDE are ,

AC are

FG are

BF are

AB are .

Se observa pierderea unor DMV, ca urmare a descompunerilor facute:

. Acest lucru ajuta la evitarea posibilelor anomalii evidentiate anterior.

P2. Se da schema de relatie R=ABCD si sunt date AàBCD, BààC. Se cere?

a) Sa fie gasite cheile pentru R si sa se stabileasca daca R este 828b15i in FNBC;

b) Analizand atent DF pe R, sa se stabileasca daca R este in FN4.

Indicatie: sa se construiasca la inceput o realizare a relatiei cu schema R, cu valori ale atributelor alese de dumneavoastra.

Rezolvare

O realizare a relatiei de schema R care respecta DMV BààC este urmatoarea:

a) Pornind de la DF AàBCD, rezulta ca AàABCD, deci A este o cheie pentru R. Din cauza ca cheia contine un singur atribut, inseamna ca are si proprietatea de minimalitate, deci e chiar cheia primara pentru relatie. Singura DF existenta este AàBCD, iar A este supercheie pentru cheia primara A, deci R este in FNBC.

b) Din AàBCD rezulta AààBCD, dar aceasta este o DMV triviala. Daca analizam cealalta DMV, si anume BààC, observam ca in partea stanga nu se afla o supercheie pentru A, deci R nu se afla in FN4, daca aceasta dependenta este corecta.

Pentru ca dependenta sa existe, trebuie sa am 4 tupluri cu acelasi B. Consider asadar tuplurile 2 si 3:

Acum, mai trebuie 1 tuplu care are acelasi B, acelasi C cu tuplul 2, iar AD sunt aceleasi de la tuplul 3. Analog, tuplul 4 va trebui sa aiba acelasi B, acelasi C cu tuplul 3, iar AD aceleasi de la tuplul 2. Se va obtine realizarea care e data la inceput, si care respecta DMV.

Problema este ca aceasta realizare NU RESPECTA conditia ca A sa fie cheie. Intr-adevar, tuplul 1 si 3, iar 2 si 4 au acelasi A, dar C-uri diferite. Deci, ca sa respect si conditia aceasta, transformam realizarea astfel:

Aceasta realizare respecta ambele dependente, dar introduce redundanta mare, si apare o problema viitoare pentru orice nou tuplu cu B = 2. Deci nu se poate pastra o FN4 cu aceste doua constrangeri.