Remarks and instructions READ THIS FIRST!

For all problems, you should indicate steps. For example:

For finding candidate keys, a simple final answer is not sufficient. You should clearly indicate which method you have used.

If you need to find canonical cover Fc, be sure to go through the loop of the algorithm at least once. You should not do this by observation.

If you are asked to decide whether a relation is in 3NF or BCNF, a simple yes or no does not demonstrate your understanding of the materials. You should clearly indicate WHY.

For BCNF and 3NF decomposition, you should follow the algorithms introduced in classes, make sure that you have applied all steps, and show the steps on paper. For example, if you use the BCNF decomposition algorithm, you should explain why the last relation is in BCNF (otherwise, why would you stop there?). For 3NF decomposition, you should first find Fc (and show steps). After you form the smaller relations, you still need to verify whether at least one relation contains a candidate key. For each decomposition, clearly indicate what are the relations in the final result. Also please remember: The two algorithms have different purposes, and the steps of these two algorithms are different!

1. Meaning of FD (4 points). In relation schema R=(ABCDE), we have F = {A B, BD C}. Make an instance (i.e., a table) r with 5 tuples, where at least two tuples should have the same value of A, and two other tuples have the same value of B and same value on D. This table must satisfy the requirement of F.

2. Computing alpha closure (8 points). Consider R (ABCDEF) with F = {A B, B CE, CD A}. Compute (i) A+; (ii) (CD)+. Show the steps of your work, not just final result.

3. Determine elements in F+ (8 points). Consider R (ABCDEF) with F = {A B, B CE, DE AF}. (i) Is AD F in F+? (ii) Is A CD in F+? For each of them, show steps in justification, indicate which Armstrong axiom is used at each step.

4. Alpha closure and canonical cover (36 points total). Consider relation R (ABCDE) and the F = {AC B, AB C, CB, D BC, CD}. Now answer the following.

(a) (8 points) Find the canonical cover. Show steps.

(c) (8 points) Find all candidate keys. Show steps.

(d) (10 points) Is relation R in BCNF? If yes, explain why. If not, perform the lossless-join decomposition algorithm to obtain a set of BCNF relations. Show steps. Also indicate whether this decomposition is dependency-preserving or not, and explain why.

(e) (10 points) Is relation R in 3NF? If yes, explain why. If not, perform the lossless-join, dependency-preserving decomposition algorithm to obtain a set of 3NF relations. Show steps of your work, and clearly indicate final result.

5. More on decomposition (24 points total). Consider relation R(ABCDE) and F = {AC B, B D, DE}. Suppose the original relation R is decomposed (regardless which algorithm is used) into R1 (ABD) and R2 (BCE).

(a) [6] Compute F1 and F2 (i.e., identify FDs projected into two smaller relations R1 and R2).

(b) [3] Is R1 in 3NF? Explain.

(c) [3] Is R2 in 3NF? Explain.

(d) [6] Is this decomposition (from R into R1 and R2) a lossless-join decomposition? Justify your answer.

(e) [6] Is this decomposition dependency preserving? Justify your answer.