3

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?

  • 1
    It looks fine to me but not entirely sure. I don't think there is a single decomposition to 3NF. Does the algorithm produce one result only? Or is possible that it may produce different decompositions depending on the choices you make? – ypercubeᵀᴹ Jun 16 '18 at 10:36
  • Re "is this right": Show the steps of your work following your reference/textbook, with justification--you will likely find mistakes that make your question unnecessary & we want to check your work but not redo it & we need your choices when an algorithm allows them & otherwise we can't tell you where you went wrong & right. Please see How to Ask, hits googling 'stackexchange homework' & the voting arrow mouseover texts. – philipxy May 25 at 10:08
0

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).

  • Great answer! Now, it is more clear!! Thanks – Sena Aydin Jun 16 '18 at 12:43
  • Exactly! Bernstein Synthesis guarantees dependency preservation but not lossless-join! – Sena Aydin Jun 16 '18 at 12:57
  • @SenaAydin No, Bernstein synthesis guarantees both. – philipxy May 25 at 10:05
  • What theorem is that? Do you mean, if the other components each preserve at least one FD? – philipxy May 25 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.