CSC 453 Homework 3 solved

Description

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}.
• [2pt] Can we infer NP → LM from F ?
• [3pt] Can we infer NQ → LO from F ?
A-2 Keys
(i) [5pt] Find all the candidate keys of the Relation R(ABCDE) with FD’s:
D → C, CE → A, D → A, and AE → D
(ii) [5pt] 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
[5pt] 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
[15pt] 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 (7 points)

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 (8 points)
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 (15 points)
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 (15 points)
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) (15 points)
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}
CSC 453