1

Sometimes the 3NF synthesis decomposition algorithm (such as the one described here p.4) generates redundant relations, where all attributes of some R_i already appear in another R_j. The algorithm is supposed to delete such redundant relations.

I read several descriptions of BCNF decomposition algorithms (see an example below) and none of them mention a similar final deletion step, which let me think that maybe the reason is that this situation never occurs with BCNF decomposition.

However I stumbled upon this example : consider R(A,B,C,D) and the set of functional dependencies F = {A→B; B→C; B→D}. I use the BCNF decomposition algorithm described here:

Input: relation schema R and set of FD's for R
   (1) compute keys for R based on FD's
   (2) repeat until no more BCNF violations:
         (2a) pick any R' with AA → BB that violates BCNF
         (2b) decompose R' into R1(AA,BB) and R2(AA,CC)
              where CC is all attributes in R' except (AA U BB)
         (2c) compute FD's for R1 and R2
         (2d) compute keys for R1 and R2 based on FD's
  • step (1) leads to only one key: A.

  • (2a) the DF BC→D is a consequence of F and BC is not a superkey therefore R is not in BCNF.

  • (2b) we decompose R using BC→D and get R1(BCD) and R2(ABC).

  • Applying (2c) and (2d) for R1, we get that F1={B→C; B→D} is a cover for the FD's of R1, and then that R1 is in BCNF.

  • Applying (2c) and (2d) for R2, we get that F2={A→B; B→C} is a cover for the FD's of R2 and that A is the unique key for R2. Therefore R2 is not in BCNF since B→C belongs to F2 and B is not a superkey.

  • If we decompose R2 using B→C, we obtain R3(BC) and R4(AB), and we are done because R3 and R4 only have two attributes.

  • Finally we obtain a BCNF decomposition of R as R1(BCD),R3(BC) and R4(AB). But all attributes of R3 already appear in R1, therefore it would be preferable to delete R3.

Did I apply the algorithm incorrectly, or does it mean that one should add this additional deletion step to this BCNF decomposition algorithm ?

3
  • "the 3NF decomposition algorithm" Which one? "which let me think that it never occurs for BCNF" With what justification? But what do either of those have to do with your question? "the BCNF decomposition algorithm" Which one? You need to quote the algorithm for us to say you applied it correctly. How is it you are not sure you followed it? Explain clearly. Including how you calculated CKs. Do you understand that the FDs in a component might not be FDs in F?
    – philipxy
    Commented Oct 27, 2020 at 11:50
  • Your "I have these FDs" doesn't make sense. "These are all the FDs that hold"?--Not possible. "These are all the non-trivial FDs that hold"?--Not possible. "These are some FDs that hold"?--Question can't be answered. Find out what a cover is & what the exact conditions are to apply a particular definition/rule/algorithm. To determine CKs & NFs we must be given FDs that form a cover. Sometimes a minimal/irreducible cover. And the set of all attributes must given. See this answer.
    – philipxy
    Commented Oct 27, 2020 at 11:52
  • @philipxy I edited my question to clarify the terminology and add some computation details
    – Tran P.
    Commented Oct 27, 2020 at 15:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.