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}