How To Check if a Relation is in BCNF, 3NF, or Both

Another note of my database lecture class regarding Normalization and checking whether a relation is in BCNF, 3NF, or both.

The textbook that I use is “Database Management System” by Ramakrishnan and Gehrke and though it is a very comprehensive textbook, it is not that easy to understand. The discussion about BCNF, and 3NF was so wordy and has few examples.

So this is my way of making notes that will help myself on the final exam later, and I hope it can help you also understanding the BCNF and 3NF relation.

BCNF Relation

Probably you’ve heard the definition of Boyce-Codd Normal Form, and let’s repeat it again:

A relation in in BCNF if for every non-trivial FD X → A, X is a superkey.

Now, this doesn’t help at all, does it? But an example will surely help:

Example #1 :
ABCD
AB → CD

The steps are :

  1. Find the candidate keys (We will not discuss how to find candidate keys here).
  2. Check if all the FD satisfies the definition.

For example #1:

  1. The candidate key is only one, that is AB.
  2. Fortunately that AB is also our left hand side FD (AB → CD), so the relation is in BCNF.

Example #2 :
ABCDE
AB → CD
E → A
D → A

  1. Candidate key : BE.
  2. Unfortunately, all the left hand side FDs does not include BE, so the relation is not in BCNF.
3NF Relation

Third Normal Form (3NF) is a bit more relaxed form compared to BCNF. Let’s see the definition:

A relation is in 3NF if for every non-trivial FD X → A, X is a superkey or A is part of some key for R.

Once again, it doesn’t help much until we see the example. So let’s go back to our previous examples.

Example #1 :
ABCD
AB → CD

The steps are the same with checking for BCNF.

  1. Candidate key is AB, and
  2. Our only FD’s left hand side is equal to that candidate key, so it is in 3NF.

Honestly, you don’t need to check for 3NF for the first example, because all relation that is in BCNF is also in 3NF. :D

Example #2 :
ABCDE
AB → CD
E → A
D → A

  1. Candidate key : BE.
  2. Let’s check the FDs one by one:
  • E → A : this is not ok, because E is not a candidate key, and A is not part of BE.
Do you have examples of relation that is not in BCNF but it is in 3NF?

Sure I have!

Example #3:
ABCD
ABC → D
D → A

Let’s check this relation for both BCNF and 3NF.

BCNF check:

  1. Candidate keys : ABC and BCD.
  2. Check the FDs:
  • ABC → D : ABC is a candidate key.
  • D → A : D is not a candidate key, so it is not in BCNF.

3NF check:

  1. Candidate keys : ABC and BCD.
  2. Check the FDs:
  • ABC → D : ABC is a candidate key.
  • D → A : D is not a candidate key, BUT A is part of candidate key (ABC), so it is ok.

Since both are okay, this relation is 3NF.

That’s all there is in regards to determining whether a database relation is in BCNF or 3NF, it’s not that confusing at it appears to after all.

Questions and critics are welcome! And if you have a relation example that you are not sure of, you can ask in the comments section. :D


Popularity: 43% [?]

Tags:

Related Posts


30 comments ↓

#1 Nirav on 12.03.10 at 12:44 am

hi..its really helpful.. i have doubt in finding out candidate key in following type of relation:
R(A,B,C,D,E)
A->BC
CD->E
B->d
E->A

will you plz tell me how to find out candidate key for above??

#2 djitz on 12.04.10 at 5:55 pm

Hi Nirav,

First, the process to find a candidate key will be a bit long one so I will write it briefly here. I’ll have a separate blog post for finding candidate keys within this week. :D
Since you’re having question for an interesting example here, I also suppose that you have an idea about finding a candidate key from the given relation and functional dependencies.

The candidate keys I got for the relation you posted are : A, E, BC, and CD
How I got these key? Since all the attributes are on both sides, so we must try each attribute one by one, starting from single attribute.
For single attributes, we can find that A closures are all attributes, and E closures are all attributes.
Next for two attributes, we will also find that BC closures are all attributes, and CD closures are also all attributes.

We don’t need three attributes test because they will contain both the single attribute and two attributes candidate keys.

I hope it answers your question! :D

#3 RandomSpectrum on 12.05.10 at 5:16 pm

I believe the best method to find the candidate key(s) is by doing the 4 step:

1. Attribute on no sides
2. Attribute on right side but not left side.
3. Attribute on left side but no right side.
4. Both sides

Then from 1 and 3, you get the main attributes that your candidate key should have. You try it out (trialKey+) and if it works, that is your only candidate key. If it fails you try add to it the attributes in step 4 one by one and group by group and also removing the attributes in step 2.

So if your main key derived from 1 and 3 is let’s say AB. And in step 2 you have C and in step four you have DE.

Then the next tries for your candidate keys would be :

ABD, ABE, ABDE. You do not include C.

Anyways, been working on a small application that should work on this algorithm. Make it easier for others.

#4 djitz on 12.06.10 at 1:07 pm

hi RandomSpectrum,
Thank you for your comment on the method you use to find the candidate keys, it’s actually a bit different with the method I know. I will try the method you posted and compare it with some examples. I’ll let you know the result. :D

#5 NXN on 12.16.10 at 5:32 pm

Good job!

Last year i spent a lot of time to find out EXACTLY the way you wrote above. I wish you had posted this 1 year ago LOL. What a pity !

To find out the key, my method is testing all the k-combinations , k is the number of element in R.

#6 djitz on 12.17.10 at 6:19 am

Hi NXN,

Thank you for the compliment! :D
Yeah, I found some of the information in the book and internet are too hard to understand while actually it’s quite simple with few examples.

Your method to find the key is interesting, never heard that before actually, but I suppose that will work too. :)

#7 RandomSpectrum on 12.17.10 at 8:52 am

@NXN

The combinations method is not that useful due to the time it takes. What if you have ABCDEFGHJ as a relation. 2n-1 ways to choose from. How will you know which are keys or superkeys?

#8 Nirav on 12.17.10 at 7:44 pm

@RandomSpectrum

ya i agree with your reply to @NXN. actually the solution that you have provided in your earlier post is working well for some example but for some other example (eg. i have posted it)in which all attributes are on both the sides and no missing attribute in FD, it won’t work.

#9 NXN on 12.18.10 at 6:51 am

Hi all,

Yes, actually i see my method is quite long. The more elements there are in R , the more time it takes. But i think it always works and if you concentrate enough, no key missed !?

Moreover, while you do this method, you’ll find some “tips” by urself and the testing time will not be that long as you do step by step :D

#10 djitz on 12.18.10 at 6:22 pm

Wow, never thought that we’ll have a good discussion here. :D

RandomSpectrum, Nirav and NXN, I agree with all of you!
When it comes to speed, the algorithm RandomSpectrum is really good. Besides that’s one of the reason why people come up with algorithms right? To speed up a process.
In fact it probably cover most of the cases, though not all. So knowing how it works in more basic level like the method NXN gave is really useful. :)

#11 RandomSpectrum on 12.19.10 at 5:20 pm

@ djitz

The example where all attributes are on both sides is the longest case because there is no core Candidate key (let’s say for R(ABCDE). It would be :

1. none
2. none.
3. none.
4. all

Now as I said before, you check the core key (step 1 + step 3) and if it does not give you the full relation R(ABCDE) (it obviously does not because it is empty), then you have to try all the combinations in step 4.

So you try, A,B,C,D,AB,BC,CD,DE….etc, which will take us to the thing NXN was talking about. This is the type of example that would mean the “worst-case” for my way of solving CKs.

#12 djitz on 12.20.10 at 9:48 pm

@RandomSpectrum

Yes, you’re right. It’s actually also one of the algorithm that my professor teach to me. :)

#13 Jyoti pandey on 01.28.11 at 6:30 pm

Thanks, your way has cleared my concept.

#14 Aleksander S. on 04.12.11 at 1:52 am

Sitting here, prepairing for my exam in database design. Using Database Management Systems from Ramakrishnan and Gerhrke. This site could not have come more in handy.

Thanks, and keep up the good work!

#15 djitz on 04.14.11 at 6:39 pm

@Aleksander, you’re welcome and God bless for your exam! :D

#16 Dipti on 04.25.11 at 6:35 pm

Hi,
I need some help from you can you tell me where can I post my question or where do I email it to.

Also its a request if you could give examples as how to decompose a relation with FD into BCNF and 3NF form. Also give info abt how to check if it is a lossless-join and does it preserve dependancies.

I appreciate your help regarding these topics as I have my exam nearing an I am not getting a hang of this topics… I like your way for explaining as It helps in understanding it clearely.

Thank you

Dipti

#17 djitz on 04.25.11 at 7:39 pm

Hi Dipti, you can post your question here in the comment section or email me too.

But I can’t promise if I can answer you soon because I’m busy with my school also now.

#18 Dipti on 04.25.11 at 7:49 pm

Here is my question, ya just see if you find time you can reply to this one :

Given that R(A,B,C,D,E) with the FD’s C -> E, D -> BC, E -
> D, B -> A and A -> D. This relation is in BCNF.

1. Explain why it is in BCNF
2. Now, suppose you decompose R into relations S(C,D,E) and T(A,B,D). Is this a
lossless join decomposition?
3. Give all the non-trivial FD’s for relation S (i.e., non-trivial FDs involving only A,
B, and C).
4. Give all the non-trivial FD’s for relation T (i.e., non-trivial FDs involving only A,
D, and E).
5. Does this decomposition preserve dependencies?

I tried the second one an got it, but not able to answer others. I hope you find some time as I think this question can clear a lot of doubts I have.

Hope to see the reply !!

Thank you so much !!!

#19 Wave on 05.24.11 at 9:13 pm

Hi,

Just want to say, this has helped me so much. I have a midterm on BCNF and 3NF tomorrow, and you’ve really done a great job in clearing up the differences between the two forms. Thank you!

#20 renuka on 07.13.11 at 5:37 am

its really very very helpful to me. thank you

#21 Koray on 11.26.11 at 6:41 am

Incredibly simple explanations here! Thanks a lot!

#22 Ernast on 12.12.11 at 6:43 pm

This is unbelievable!!! Exam tomorrow and you just possibly helped me avoid a C so thank you for you simple and straight to the point examples. Please never take this down for other struggling database students.

#23 Justin on 03.22.12 at 2:45 am

Thank you for this. Explains it much better than the textbook.

#24 Sudeep Kumar Rana on 05.23.12 at 1:54 pm

I was trying to understand the difference between 3NF and BCNF from past 3 hours and were not able to understand it. Finally you explained it to me.
Thank you Trijito

#25 Eric Pena on 10.24.12 at 3:22 pm

Thank you, this has helped my understanding. Great explanation.

#26 sayali on 01.21.13 at 2:57 pm

Hi,
your post was really helpful !

#27 bademeister on 02.12.13 at 7:08 am

nice.. thank you man

#28 Jeffrey on 02.27.13 at 4:09 am

Thanks so much!

#29 Vivek Vikas on 04.22.13 at 8:17 pm

Really awesome explanation !!!

#30 Dani .H on 07.13.13 at 3:49 pm

Hey man,
I gotta give it to you – you the man :)
It takes a lot of manliness to understand all the material first, and lay it out in a manner that others can find useful.
Really saved me.
Thanks.

Leave a Comment