Set probleme “Baze de date 1” (P1, P2, Mai 2016) (exemplu). P1

Set probleme “Baze de date 1” (P1, P2, Mai 2016) (exemplu).

P1. Fie schema de relație R= ABCDEF, cu mulțimea de dependențe funcționale F= {A->B,

A->F, B->E, D->B, E->A}. Se cere:

1. 
   să se determine o cheie pentru R și să se calculeze închiderea acestei chei (se va demonstra de ce submulțimea de atribute respective este cheie, fără a afirma direct „aceasta este cheie”).
   
2. 
   Să se găsească pentru R o descompunere ρ, astfel încât fiecare sub-schemă din aceasta să fie în Forma Normală Boyce- Codd (FNBC). Pe fiecare pas al algoritmuilui de descompunere, se va calcula proiecția mulțimii de dependențe funcționale valabile în pasul curent, pe sub-schemele de relație obținute în pasul anterior.
   

P2. Fie schema de relație R= ABCDEF și mulțimea de dependențe funcționale pe R F= {A->B,

C->F, E->A,, CE->D}. Să se verifice dacă descompunerea ρ = (ABC, CEF, DEF) are proprietatea de joncțiune fără pierdere (j.f.p.).

P1. a/ Calculăm la început cheile schemei de relație R. Observăm că atributul C nu se găsește în niciuna din dependențele funcționale din F, iar atributul D nu face parte din nicio parte stângă a vreunei dependențe funcționale din F. Rezultă așadar că o cheie pentru R trabuie să fie CD. Să calculăm inchiderile pentru CD. Vom avea, succesiv :

(CD)₀⁺ = {CD} ; folosim acum dependența funcțională D->B si obțínem, mai întâi, (CD)₁⁺ = {CD} U {B} = {BCD}. Apoi folosim B->E și obțínem (CD)₂⁺ = {BCD} U {E} = {BCDE}. În continuare, cu E- >A , obțínem (CD)₃⁺ = {BCDE} U {A}’= {ABCDE}. Mai departe, (CD)₄⁺ = {ABCDE} U {F} =

{ABCDEF}. Ne oprim aici, nemaiput\nd ad[uga alte atribute. Așadar, vom avea CD⁺ =

ABCDEF, deci o cheie (minimală) a schemei de relație R este cu adevărat CD.

b/ pormim cu σ = {ABCDEF} și cu dependențele funcționale din F. Alegem A=F și găsim

σ₁ = {R₁ = AF, R₂= ABCDE}, unde σ₁ este o primă schemă de relație din descompunerea căutată. Așadar avem R₁= AF, cu dependența A->F și cu cheia A , respectiv R₂ = ABCDE, cu dependențele A -> B, B -> E, D -> B, și E -> A. Pentrtu a continua algoritmul de descompunere cu R₂, alegem E->A și vom avea: σ₁ = {R₁= AF, R’₂= AE, R₃ = BCDE}. Pentru R’₂= AE, luăm dependența E->A, cu cheia E. Pentru R₃ = BCDE, avem dependențéle B -> E ,

A->B ; vom alege pentru R₃ dependența B-> E, așa încât în continuare vom scrie:

σ₁ = {R₁ = AF, R’₂ = AE, R’₃ = BE, R₄ = BCD}, unde pentru R’₃ = BE avem dependența B->E, cu

cheia B, iar pentru R₄ = BCD avem fdependența D -> B, și cheia D.

În acest mod, am ajuns la descompunerea :

σ = { AF, AE, BE, BCD }, cu cheile A, E, B și respectiv D .

Faptul că în subschema BCD avem dependența D -> B șii atributul C nu apare în nicio dependență funcțională, ne face să afirmăm că CD este cheia acestei subscheme. Dependența trivială C -> C nu contravine definiței Formei Normale Boyce Codd. Descompunerea căutată poate fi reprezentată în forma :

A B C D E F

A-> B, A -> F, B -> E, E -> A

cheie CD

A F A B C D E

(FNBC) A->F A->B, B->E, D->B,

cheie A cheie CD

A E B C D E

(FNBC) E-> A B->E, D->B

cheie E cheie CD

B E B C D

(FNBC) B -> E (FNBC) D->B, C-> C

cheie B cheie CD

P2. Pentru respectarea dependențélor funcíonale de către descompunrea găsită se impune îndeplinirea condiției:

U_{i =1,.....K} Π_Ri (F) să implice logic F, deci:

Π_Ri (F) = { (X->Y)│ (X->Y)ϵ F^-1 și XUY϶ R_i }.

Calculăm F⁺ cu axiomele Armstrong și obținem:

F⁺ = { A->B, A->F, B->E, D->B, E->A, A->E, D->E, E->D, E->F, B->A} (observăm că am scos numai o parte a dependențelor funcționale din F⁺ ).

Calculăm în continuare Π_Ri (F):

Π_AB (F)= {A->B, B->A}

Π_BCD (F) = {D->B}

Π_AEF (F) = {A->F, E->A, A->E, E->F}

Π_CDE (F)= {D->E}

U_{i = 1….4} Π_Ri (F) = {A->B, B->A, D->B, A->F, E->A, A->E, E->F, D->E}.

Această mulțime trebuie să implice logic pe F. Observăm că singura dependență funcțională care la prima vedere nu face parte din reuniune este B->E. De fapt însă ea este implicată de reuniune, deoarece B->A ;I A->E, prin urmare B->E.