Decomposition in 3NF using synthesis

Question

I have an assignment at the university and it is about decomposition. These are the relation and FDs.

V={ABCDEF},F={AB→CD,ABDE→F,BC→A,C→DF}

We need to find candidate keys, canonical cover(basis) and decomposition in 3NF with dependency preservation and lossless-join.

-I found that our candidate keys are: {ABE, BCE}

-Basis= {AB→C,BC→A,C→DF}

-But I am not really sure about the decomposition in 3NF and really confused. This is my solution:

Minimal Basis R0= {AB→C,BC→A,C→DF} Step 1: Generation R1= (ABC) R2=(BCA) R3= (CDF) Step 2: If none of the relation schemas in Ri contains a candidate key of R0 Create new relation schema Rj contains attributes form a key of R0

Candidate Keys={ABE,BCE} R4= (ABE) R5= (BCE)

Step 4: Eliminate relational schemas that are included in others (R1 and R2) Result: Z= {R1, R3, R4, R5)

Do R4 and R5 relations make sense? What is the accurate decomposition in 3NF?

Answer 1

The problem is in your application of step 2:

If none of the relation schemas in Ri contains a candidate key of R0 Create new relation schema Rj contains attributes form a key of R0

This means that you must add a new relation (but only one!) that contains one of the original candidate keys (any one!).

So correct decompositions in 3NF are {R1, R3, R4} or {R1, R3, R5}. You can chose one of the two as result of the question (and this means yes, the synthesis algorithm can produce different decompositions).

Finally we can note that this step is used to guarantee the lossless-join property (while the dependency preservation is guaranteed by the previous steps, since all the decompositions are considered). In fact a theorem exists that says that if a decomposition preserves the dependencies and has at least a relation which contain one of the original candidate keys, than this decomposition preserves the data (i.e. is a lossless-join decomposition).