CSC453-Homework 3 Solved

Part A: Functional Dependencies 

A-1 Transitive Dependency and Keys

You have a relation R(L,M,N,O,P,Q) and a set of functional dependencies F = {LNO→M, MN→LOP, N→O, OP→LN}.

·         Can we infer NP → LM from F ?

·          Can we infer NQ → LO from F ?

A-2 Keys 

(i)  Find all the candidate keys of the Relation R(ABCDE) with FD's:

D → C, CE → A, D → A, and AE → D

(ii)  Determine all the candidate and superkeys of the relation R(ABCDEF) with FD's:

AEF → C, BF → C, EF → D, and ACDE → F

 

A-3 Minimal Cover 

 Find a minimal cover for the following set F of functional dependencies.

A→BC

AB→D

C→AD

D→B

Show your working clearly. Points will be deducted if you do not show the extraneous attributes, and their elimination. 

 

A-4 Equivalence 

 Consider the following set of F.Ds. Determine if FD1 is equivalent to FD2 or to FD3:

FD1:

{BC->D,ACD->B,CG->B,CG->D,AB->C,C->A,D->E,BE->C,D->G,CE->A,CE->G}

FD2:

{AB->C,C->A,BC->D,CD->B,D->E,D->G,BE->C,CG->D}

FD3:

{AB->C,C->A,D->G,BE->C,CG->D,CE->G,BC->D,CD->B,D->E}

 

Part B: Normalization

B-1.  Dependency Preservation 

 

For the relation R(w,x,y,z), consider the decomposition D consisting of R1(w,y,z)  and R2(x,y), and the set of functional dependencies 

F ={yàxz; yzàw; xàw}.  Recall that the projection of set of functional dependences G on relation Rx consists of every functional dependency in (G)+ that contains only attributes from Rx.  

 

a. Compute the projection of F on R1.

b. Compute the projection of F on R2.

c. Does the decomposition D preserve the set of dependencies F?  Why or why not?

 

B-2.  Lossless Decomposition 

Perform the test for the non-additive join property (lossless join) for the relation R(A1, A2, A3, A4, A5), and the decompositions Da, Db, Dc, Dd and set of functional dependencies F given below.  You can ignore attributes that are not mentioned in each particular subsection (e.g., you can ignore absence of A4 in Dd, just test the join between R1 and R2):

 

F = {A1àA4;A4àA5;A3àA4}

 

Da = {R1(A1, A2), R2(A3, A4, A5)} 

Db = {R1(A3, A4), R2(A4, A5)}

Dc = {R1(A1, A5), R2(A4, A5)}

Dd = {R1(A1, A2, A3), R2(A1, A2, A5)}

 

a. Does the decomposition Da have the non-additive join property?  Explain why or why not.

b. Does the decomposition Db have the non-additive join property?  Explain why or why not.

c. Does the decomposition Dc have the non-additive join property?  Explain why or why not.

d. Does the decomposition Dd have the non-additive join property?  Explain why or why not.

 

B-3.  Normalization 

Consider the universal relation

EMPLOYEE(ID, First, Last, Team, Dept, Salary)

with the following set F of functional dependencies:

 

ID à First

ID à Last

First, Last à ID

Last à Team

ID à Dept

ID à Salary

Salary à Dept

 

a. Identify candidate keys of EMPLOYEE.

 

b. Construct a decomposition of EMPLOYEE into relations in 3NF that preserves dependencies.  Show full working. How can you be sure that your decomposition is dependency-preserving? 

 

c. Are all of the relations in your decomposition in BCNF?  Either explain why they are, or identify one that is not and explain why it is not. (Note that for a relation to be in BCNF, the determinants of all functional dependencies in the relation must be superkeys of that relation – not superkeys of the original universal relation.)

 

B-4. 3NF 

Which of the following relations is in Third normal form (3NF)? Give sufficient reasoning if not in 3NF.

 

(a) R(ABCD) F = {ACD → B; AC → D; D → C; AC → B}

(b) R(ABCD) F = {AB → C; BCD → A; D → A; B → C} 

(c) R(ABCD) F = {AB → C; ABD → C; ABC → D; AC → D} 

(d) R(ABCD) F = {C → B; A → B; CD → A; BCD → A} 

 

B-5. (BCNF)  

Which of the following relations is in BCNF? Give sufficient reasoning if not in BCNF.

(a) R(ABCD) F = {BC → A; AD → C; CD → B; BD → C}

(b) R(ABCD) F = {BD → C; AB → D; AC → B; BD → A}

(c) R(ABCD) F = {A → C; B → A; A → D; AD → C}