CS 353 Homework 5 Solved

Q.1 [25 pts, 5 pts each] Given an instance of the relation R(A, B, C, D)

A
B
C
D
a1
b1
c1
d1
a1
b2
c1
d1
a2
b3
c1
d3
a2
b3
c2
d3
a3
b3
c2
d3
a4
b4
c2
d4

a. Does A  C hold on R?  If not, explain why.

b. Does B  D hold on R?  If not, explain why.
c. Does BCD  A hold on R? If not, explain why.
d. Find the attribute closures of A and B.
e. Is AB a candidate key and/or a super key of this relation? Explain your answer.

Q.2 [15 pts, 5 pts each]

Consider a relation R(A,B,C, D, E, F) with the following set of functional dependencies:

{ABC,AD,FA,DE,BEF,ACB}.

a. Find the attribute closure of A.
b. Find the attribute closure of CF.

c. Using only Armstrong’s axioms, show that DB  C holds on R.

Q.3 [15 pts, 5 pts each]

Given a relation R (A, B, C, D) with F = {A  D, B  C, A  BD and D  B}

a. What is the candidate key of this relation?
b. Does this relation satisfy BCNF? Explain your answer.
c. Does this relation satisfy 3NF? Explain your answer.

Q.4 [25 pts, 5 pts each]

Given a relation R (A, B, C, D, E, F) with F = {A  D, BC  E, and AF  BC}

a. Show that R does not satisfy BCNF.
b. Give a lossless decomposition of R into BCNF.
c. Is your decomposition dependency preserving? Explain your answer.

d. Suppose that the following decomposition is given: R1(A, B, C, D) and R2(D, E, F). Is this decomposition lossless?

e. Is the decomposition in part (d) dependency preserving? Explain your answer.

Q.5 [20 pts]

Given R(A, B, C, D, E) with F = {A  BC, B  E, BD  C, AD  CE, E  AD}.

a. [5 pts] Check if D is extraneous in BD  C.
b. [5 pts] Check if C is extraneous in A  BC.

c. [10 pts] Find the canonical cover of F.