0

I seem to have a strange problem when doing normalization problems. When I'm giving relations with actual names I can figure these out easily but when I'm given letters it seems to be a lot harder.

For the following problem I don't know why it's not 3NF and why it is 2NF.

Given R (A, B, C, D, E, F)

FDs = {AB->C, DBE->A, BC->D, BE->F, F->D}

So for 2NF all the right hand side attributes must be fully functionally dependent on the left hand side attributes. For 3NF either all the left hand side attributes must be superkeys or the right hand attributes must be prime attributes.

I tried drawing this out, but I can't even find a candidate key. Can anyone help me determine why this is not 3NF? Also, what is the candidate key here? Since I don't see any attribute that has a closure equal to the original relation.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • The candidate key is probably composite — there's certainly no guarantee it will be a singleton attribute. Isn't ABE a possible candidate key? Given AB, you can find C; given BE you can find F, and hence D, so that covers all the attributes. The BE->F and F->D transitive dependency prevents it being 3NF, doesn't it? – Jonathan Leffler Dec 13 '15 at 23:22
  • I think DBE could be another candidate key. Given DBE, you can find A; given BE, you can find F; given AB, you can find C; that covers all the attributes again. – Jonathan Leffler Dec 13 '15 at 23:40
  • BE is the only candidate key. @JonathanLeffler is right about the transitive dependency. – Mike Sherrill 'Cat Recall' Dec 13 '15 at 23:52
  • @MikeSherrill'CatRecall': Good point: given BE you can get to A or D, so both my possible candidate keys were superkeys and not minimal ones, and hence not candidate keys. – Jonathan Leffler Dec 13 '15 at 23:55
  • Ahh, I see, thank you, I'll try this question again with all of this in mind. –  Dec 14 '15 at 00:22
  • I think every textbook I've ever seen includes at least one way to determine all the candidate keys using just pencil and paper. You should look for that. – Mike Sherrill 'Cat Recall' Dec 14 '15 at 01:07
  • 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.](https://stackoverflow.com/a/53386492/3404097) – philipxy Feb 17 '21 at 17:52

1 Answers1

0

I seem to have a strange problem when doing normalization problems. When I'm giving relations with actual names I can figure these out easily but when I'm given letters it seems to be a lot harder.

Yes, its less intuitive with letters. I will tell you a neat method which you can follow to determine the candidate keys in such situations :

Make three columns left(L), middle(M) and right(R) where left columns consists of all the attributes that appear only on the left side in all the given functional dependencies. In our case such attributes will be B and E since they are always on the left side of any FD given (or you can say they are never on the right side in any of the given FD.). Similarly middle column contains attribute that appear on both left and right side of the given FD's. So we have A,C,D and F in the middle column. The right column contains attributes which only occur on the right hand side of FD's (never on the LHS of any given FD's). So we have :

L  |   M   |R
B,E|A,C,D,F|-

Now that you have this table remember the following rules: (these are very intuitive)

  • Attributes in the left(L) column are always part of the candidate keys
  • Attributes in the right(R) column are never part of the candidate keys
  • Attributes in the middle(M) column may or may not be a part of the candidate keys.

So in our case we start with checking if BE is a candidate key. We find BE-closure consists of all the attributes of the relation R so it is the candidate key. (Note: If BE would not have been the candidate key then we would have taken attributes from middle(M) column one-by-one and combine it with BE and check its closure eg. BEA,BEC,BED ...)

So now we have only 1 candidate key BE. So our prime attributes are {B,E} and non-prime attributes are {A,C,D,F}.

We know that 3NF is violated if RHS is a non-prime attribute and LHS is not a candidate key. Given FD's are:

  1. AB->C
  2. DBE->A
  3. BC->D
  4. BE->F
  5. F->D

We note that in all these FD's RHS is a non-prime attribute. So in all of these LHS should be a key for it to be in 3NF. We see that (1),(3) and (5) violate this so it is not in 3NF. (Note: In (2) we can see that D on the LHS is an extraneous attribute so its BE->A and hence (2) does not violate 3NF rule)

Karup
  • 2,024
  • 3
  • 22
  • 48