Thursday, February 27, 2014

Boyce-Codd Normal Form (BCNF)


Boyce-Codd Normal Form / BCNF Explained / What is BCNF? / Boyce-Codd Normal Form with Example / A relation which is in 3NF but not in BCNF Example.

 Boyce-Codd Normal Form (BCNF)

BCNF was jointly proposed by Raymond F. Boyce and Edgar F. Codd in the year 1974 to address certain types of anomaly which were present even after the schema is normalized to 3NF.

For a relation schema which is in 3NF, the presence of modification anomalies which could not be treated well by 3NF is due to one of the following reasons;

Reason 1: A relation schema might contain more than one candidate keys.
Reason 2: In case of more than one candidate keys presents, all of them might be composite.
Reason 3: If the above two reasons exist, then there is a possibility of overlap between the candidate keys.

A relation schema R is in BCNF if and only if,
  • For all the Functional Dependencies (FDs) hold in the relation R, if the FD is non-trivial then the determinant (LHS of FD) of that FD should be a Super key.
 Through this definition, BCNF insists that all the determinants of any Functional Dependency must be a Candidate Key. Due to this reason, BCNF sometimes referred as strict 3NF.

Note: A relation schema R which is in BCNF also in 3NF automatically. But, a relation schema R which is in 3NF need not be in BCNF.

Explanation:
If we have set of FDs in R such that X Y, then X must be a super key. In other words, if X is not a key, then the relation R is not in BCNF. 

A relation which is not in BCNF.


RegNo
SName
Gen
PR
Phone
R1
Sundar
M
BTech
9898786756
R2
Ram
M
MS
9897786776
R3
Karthik
M
MCA
8798987867
R4
John
M
BSc
7898886756
R1
Sundar
M
BTech
9898781158
R3
Karthik
M
MCA
8798987867
Table 1 – STUDENT

Let us find out the set F of FDs holding on Table 1 STUDENT.
F = { RegNo SName, RegNo Gen, RegNo PR }
But, Phone cannot be uniquely identified by RegNo. Hence, the key for this relation is a composite key (RegNo, Phone). We can write the set F of FDs as follows;

F = { (RegNo SName Gen PR), (RegNo Phone SName Gen PR) }

Among these two FDs, the first one which is having RegNo as the LHS is violating the rule of BCNF. The reason is, the determinant RegNo of the FD is not a key for this relation. Hence, the above table is not in BCNF.

How do we convert a table STUDENT into BCNF table?

We have to decompose the table into two or more tables as discussed in 2NF, and 3NF. For this, we can consider the set F of FDs already listed above.

Hence, the resultant schemas would be;
  • STUDENT(RegNo, SName, Gen, PR)
  • STU_PHONE(RegNo, Phone)

Now, the relation STUDENT with the FD {RegNo SName Gen PR} satisfies,
1NF (because no repeating group of values/no multivalued attributes),
2NF (because no partial key FD as the key is simple attribute),
3NF (because there is no transitive FD since there is no FDs with non-key attribute on the LHS), BCNF (because there is only one key for the relation).

For the relation, STU_PHONE the key is trivial. That is, composite key (RegNo, Phone). Hence, it is holding all the Normal Forms in it.

Note: The relation schema with the following properties need not be checked for every normal form conditions;
1. If only two attributes are present
2. If more than one attribute present and the key is simple attribute.

A relation schema which is in 3NF but not in BCNF


Let us take the following table, DEALER for our discussion. This table stores the information about various dealers for various products. And it stores the dealer details along with the products we purchase from them and the product count. According to the sample table given below, it is very evident that same products may be purchased from different dealers.

Dealer_ID
DName
Product_ID
Quantity
D101
Sun Flower
P101
100
D101
Sun Flower
P103
150
D102
Market One
P102
200
D105
A One
P101
100
D104
Indian Curry
P110
250
D104
Indian Curry
P102
50
Table 2 – DEALER

For this table, let us identify the set of Functional Dependencies;

1. Attribute Dealer_ID cannot be a determinant for this table. Because, it does not uniquely identify any other attribute other than dealer name (DName). Hence,
Dealer_ID DName
2. Attribute DName determine the value of Dealer_ID. That is, dealers have unique names. Hence,
DName Dealer_ID
3. Attribute Product_ID cannot uniquely identify anything. Because, same products purchased from different dealers in different quantify.

If we go on analyzing this, we would get the following set of FDs;

Dealer_ID DName
DName Dealer_ID
Dealer_ID Product_ID DName Quantity
DName Product_ID Dealer_ID Quantity

From the above set of FDs, we can derive Two Candidate Keys. Those are;
(Dealer_ID, Product_ID) and (DName, Product_ID)
From the derived FDs, it is clear that the relation DEALER is in 3NF, because, no Transitive Functional Dependency is held.
According to the properties of BCNF, the relation DEALER must have FDs with the LHS as candidate keys. But, for DEALER among the set of FDs, we have the FDs Dealer_ID DName and DName Dealer_ID where neither Dealer_ID nor DName are the candidate keys. Thus, these two FDs violate the rules of BCNF. Hence, DEALER is not in BCNF.

How do we convert DEALER into BCNF table?


We need to decompose DEALER using the FDs which are violating the BCNF rules. Thus, we get following schemas as a result of decomposition.
  1. DEALER1(Dealer_ID, DName)
  2. DEALER_PROD(Dealer_ID, Product_ID, Quantity)
Relation DEALER1 satisfies all the Normal Forms.
Relation DEALER_PROD has the following set of FDs;
Dealer_ID Product_ID   Quantity
As there are no other FDs, the relation DEALER_PROD is in BCNF.


*********

Related Links






Explain Boyce-Codd Normal Form (BCNF) with example in Normaliation DBMS

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery