1

I am trying to understand how to normalize a relation into BCNF form. I know what is the definition of BCNF, and I know that in order to normalize it I need to eliminate every D -> X where D isn't part of a key candidate. And to create a new tables of (D,X) and (S,X).

I also read this threads:

  1. Normalisation into BCNF
  2. BCNF Decomposition
  3. Difference between 3NF and BCNF

But the problem I am facing is how to use the algorithm when X is part of the super key. I will explain:

Assume we have this relation:

R = (a,b,c,d,e)
FD = { {a,b}->{c} , {a,b}->{d} , {a,b}->{e} , {d}->{b} }

Obviously, the only super key is (a,b). And clearly, d isn't a key candidate.

d->b violating the BCNF but we can't just take b out of the table since it is part of the super key.

So my question is: in this case, how can we normalize this relation into BCNF form?

Community
  • 1
  • 1
Ran Eldan
  • 1,350
  • 11
  • 25
  • I assume F is supposed to represent the functional dependencies, but I can't tell what the FDs actually are — the notation is ambiguous. Maybe you mean `{a,b}⟶c; {a,b}⟶d; {a,b}⟶e; d⟶b`? where I've not used set `{}` around singleton sets. Please clarify the set of FDs. – Jonathan Leffler Jul 18 '13 at 14:27
  • Yes, by `f` I ment `FD`. I edited, thank you. About the notation, I an following what I have saw so far at many places. – Ran Eldan Jul 18 '13 at 14:32
  • Yes, I ment to the FD you wrote. Edited that as well. – Ran Eldan Jul 18 '13 at 14:57
  • IIRC, there are sets of FDs that cannot be reduced to BCNF; this may be one such. Meditate on the two relations R1 = (a,b,c,e) and R2 = (a,b,d). I'm not at all sure that's a correct BCNF schema; the d⟶b FD is a pain. – Jonathan Leffler Jul 18 '13 at 15:39
  • *"Obviously, the only super key is (a,b)."* AD? – Mike Sherrill 'Cat Recall' Jul 18 '13 at 15:44
  • @MikeSherrill'Catcall' Now it's more confusing..If `AD` is a super key, then this relation is in BCNF (since all FD are key candidate) but it is not even in 3NF since there is a transitive dependency on the key (AD is a key and we get C,E from D->B , A,B->E). But BNCF supposed to be stricter than 3NF. What am I missing? – Ran Eldan Jul 18 '13 at 16:01
  • *"If AD is a super key, then this relation is in BCNF (since all FD are key candidate)"* No, it would be in BCNF if every arrow in every FD were an arrow *out* of a candidate key. In the FD D->B you have an arrow that's *not* out of a candidate key. – Mike Sherrill 'Cat Recall' Jul 18 '13 at 16:05
  • @MikeSherrill'Catcall' You right. It needs to be a candidate key, not a **part of** candidate key. But we came back to the original problem. – Ran Eldan Jul 18 '13 at 16:17

1 Answers1

0

Answearing my own question (with the great help of Jonathan Leffler):

This relation should be normalize into:

R1 = (a,b,c,e). super-key is (a,b).
R2 = (b,d). super-key is (d).

I.e. every time a scheme S have a FD D->X who violating the BCNF:

If D isn't part of the key the new tables are (D,X) and (S,X).
If D is part of the key the new tables are (D,X) and (S,D).
If both D and X are part of the key then the relation can not normalize into BCNF from.

Ran Eldan
  • 1,350
  • 11
  • 25