0

For R(A,B,C,D,E,G,H) here's the minimal cover:

{A->E,D->H,D->G,E->C,G->B,G->C,H->D}

Candidate keys:

{AH,AD}

By the definition of BCNF, none of the attributes on left side are SK or CK. Thus, it's not in BCNF. Is it safe to conclude that all of the FDs are violating BCNF? If so, in the process of decomposition to BCNF, as the algorithm says, to take the FD that violates BCNF, for example: X->Y, and do the procedure of R1(XY) and R2(R-Y)

In our case, do I need to that do that all over the FDs? If I do so, I get in the end

R1(AE), R2(EC), R3(GB), R4(DH), R5(DG) and R6(AD)

But still missing G->C and H->D and R6 isn't in the FD from the start. So that doesn't make it dependency preserving?

philipxy
  • 14,867
  • 6
  • 39
  • 83
Mustafa Shama
  • 1
  • 1
  • Does this answer your question? [What is the minimal proof that a database relation is not in BCNF?](https://stackoverflow.com/questions/53386095/what-is-the-minimal-proof-that-a-database-relation-is-not-in-bcnf) – philipxy Jan 27 '22 at 04:15
  • "isn't in the FD from the start" The FDs that hold in a schema are all those implied by the ones in a cover, not just the ones in a cover. And in a projection, the appropriate subset of all those in the original. "So that doesn't make it dependency preserving?" Well, what is the definition of dependency preserving & what exactly is your reasoning using it? You don't connect to the definitions of terms & algorithms in your reasoning & you don't give the definitions or full reasoning. So how do we know where you went wrong & why would you think your reasoning is sound? Give reasoning in detail. – philipxy Jan 27 '22 at 04:27

1 Answers1

0

Is it safe to conclude that all of the FDs are violating BCNF?

Yes

... and do the procedure of R1(XY) and R2(R-Y)

The standard analysis algorithm decompose the original schema in two subschemes R1(X+), R2(R - (X+ - X)). So if you start, for example, from AE, you produce R1(AEC) (since A+ = AEC), and R2(ABDGH). Then you repeat the steps in the remaining relations, if there are other dependencies that violates the BCNF.

For instance, in this case a decomposition that can be obtained is:

R4(AH)
R5(BG)
R6(DGH)
R7(CE)
R8(AE)

Note that, with this decomposition, the dependency G -> C is not preserved (it is a known fact that the algorithm can produce the loss of one or more dependencies).

Renzo
  • 26,848
  • 5
  • 49
  • 61
  • By coincidence, it was a question in my exam and it's stated in the answers that after the decomposition, the relations are dependency preserving so that's why I'm confused – Mustafa Shama Jan 27 '22 at 13:42
  • Your decomposition is still a valid decomposition in BCNF, but also with that decomposition the dependency G -> C is lost. You can easily verify this because no relation contains both G and C, and because such dependency cannot be derived by all the other dependencies projected on the decomposed relations (C is present only on the right part of that dependency). – Renzo Jan 27 '22 at 16:36
  • Final note. Not necessarily all the decompositions in BCNF produce a dependency loss. This can be true or false, it depends on the decomposition. What is known is that there are certain relations such that ALL the decompositions produce the loss of at least a dependency. I do not know if your relation has this property or not. – Renzo Jan 27 '22 at 16:42