BCNF

BCNF:

 

A relation schema R is in BCNF with respect to a set for functional dependencies, if for all FDS in .

 

F+         X® Y atleast one of the following is true.

 

                X® Y is trivial or

 

                X is a super key

 

EX: R (A,B,C) is the given relation schema and the given Functional Dependency is

 

F ={A ®B, B ®C}

 

Solution: Key = {A} since A+ = {A,B,C}

 

R is not in BCNF as B is not a super key.

 

 

Decomposition:
                                                        R (ABC)
                                       

                                         R1 (A,B)                     R2 (B,C)
 

Now R1 and R2 in BCNF

The decomposition is lossless and dependency preserving.

 

Boyce Code Normal Form (BCNF)

 

 To eliminate the problems and redundancy of 3NF. Boyce proposed a normal form known as Boyee code Normal form (BCNF).

 

 When the relation has more than one candidate key anamolies may arise even though the relation is in 3NF.

 

 3NF does not deal with the case of a relation with overlapping candidate keys.

 

 BCNF is based on the concept of a determinant.  A determinant is any attribute(s) on which some other attributes is fully functionally dependent.

 

Def: A relation is in BCNF if and only if every determinant so candidate key.

Let us consider a relation R (A,B,C,D) with the set of functional dependencies.

 

{A,C} ® {B,D}

 

{A,D} ® {B}

 

 Here the first determinant suggests that the primary key of R could be changed from {A.B} to {A,C}.

 

 If {A,C} would be the key then it could also determine all of the non key attributes present in R.

 

 However the second determinant indicates that {A,D} determines B. But {A,D} can’t be the key of R since it does not determine all the non key attributes of R (Eg.C).

 

 Here, first determinant is a candidate key ® {A,C}.

 

 But, the second determinant {A,D} is not a candidate key.

 

 Thus the relation R (A,B,C,D) is not in BCNF, since there exist over lapping keys candidate keys.

 

So the decomposition of the relation for BCNF is

 

            R (A,B,C,D)                                                     R (A,B,C,D)
 

R1 (A,C,D)     R2 (A,D,B)                                 R1 (A,B,C)                 R2 (A,D,B)

     AC®D             AD®B                                    AB®C                      AD®B  

 

Comparison of 3NF and BCNF:

 

 BCNF is stronger than 3NF

 

 The relations there in 3NF are not necessarily in BCNF

 

 BCNF is needed in certain situations to obtain full understanding of the data model.

 

 There are several routes to take to arrive at the same set of relations in BCNF.

 

Difference: The difference between 3NF and BCNF is that for a functional dependency A®B, 3NF allows this dependency in a relation if B is a primary key attribute and A is not a candidate key.

 

Whereas, BCNF insists that for this dependency to remain in this relation, A must be candidate key.

 

Therefore, BCNF is a stronger form of 3NF, such that every relation in BCNF is also in 3NF.

BCNF Contd.

 

Def: A relation R is Said to be in BCNF if for every non trivial FD : X®Y between

 

attributes X and Y holds in R.

 

i.e. X is a super key of R.

 

            X®Y is a trivial functional dependency i.e. YCX.

 

            In other words, a relation must have candidate keys as determinants.

 

            To find whether a relation is in BCNF or not, FDS within each relation is examined. If all non key attributes depend only on the complete key than the relation is in BCNF.

 

            Let us consider a relation project (Project code, manager machine, Quantityused).

 

Project

 

Project Code	Manager	Machine	Quantity used
P1	Thomas	Excavator	5
P3	John	Shovel	2
P2	Abhisek	Drilling	5
P4	Avinash	Dumper	10
P3	John	Welding	3
P1	Thomas	Drilling	4

 

Problems

 

Here, there are two overlapping candidate keys {Manager, Machine} and {Project code, Machine}

 

In the functional dependencies

 

{Manager} ® {Project Code}

 

{Project code} ® {Manager}

 

Neither, manager, nor project code is a super key.

 

Decomposition for BCNF:

 

 PROJECT (Project code, Machine, Quantity used.

 

 MANAGER (Project code, Manager)

 

 

Boyce Code- Normal form (BCNF) contd.

 

Def: A relation is said to be in BCNF if and only if every determinant is a candidate key.

 

Def: A relation is said to be in BCNF if and only if it is in 3NF or 2NF and for every non trivial functional dependency X®Y.

 

       X is a super key

 

       Y to be the prime attribute X to be super key.

 

Example: Let us consider a relation R (A,B,C) with the set of functional dependencies.

 

F = {A,B} ® {C} or {A} ®{B}, {B} ®{C}

 

{C} ® {B}.

 

Solution:

 

{A,B} ⁺ = {A,B,C}

 

 

Here, {A,B} is the candidate key, since there is no such single key for deriving all the non key attributes. So we take the minimal super key {A,B} as the candidate key. The relation is not is BCNF since {C} is not the .

Decomposition for BCNF:

 

The relation R (A,B,C) can be decomposed in toe R₁ (A,C) and R₂ (B,C)

 

 

R (A,B,C)

 

 

R₁ (A,C)                           R₂ (B,C)

 

BCNF (Boyce Codd Normal Form) is the advanced version of 3NF. A table is in BCNF if every functional dependency X->Y, X is the super key of the table. For BCNF, the table should be in 3NF, and for every FD. LHS is super key.

Boyce and Codd Normal Form is a higher version of the Third Normal form. This form deals with certain type of anomaly that is not handled by 3NF. A 3NF table which does not have multiple overlapping candidate keys is said to be in BCNF. For a table to be in BCNF, following conditions must be satisfied:

•           R must be in 3rd Normal Form

•           And, for each functional dependency (X → Y), X should be a super Key.

The second point means, that for a dependency A → B, A cannot be a non-prime attribute, if B is a prime attribute.

 

Example

Consider a relation R with attributes (student, subject, teacher).

Student	Teacher	Subject
Jhansi	P.Naresh	Database
jhansi	K.Das	C
subbu	P.Naresh	Database
subbu	R.Prasad	C

F: { (student, Teacher) -> subject

(student, subject) -> Teacher

Teacher -> subject}

Candidate keys are (student, teacher) and (student, subject).

The above relation is in 3NF [since there is no transitive dependency]. A relation R is in BCNF if for every non-trivial FD X->Y, X must be a key.

The above relation is not in BCNF, because in the FD (teacher->subject), teacher is not a key. This relation suffers with anomalies −

For example, if we try to delete the student Subbu, we will lose the information that R. Prasad teaches C. These difficulties are caused by the fact the teacher is determinant but not a candidate key.

Decomposition for BCNF

Teacher-> subject violates BCNF [since teacher is not a candidate key].

If X->Y violates BCNF then divide R into R1(X, Y) and R2(R-Y).

So R is divided into two relations R1(Teacher, subject) and R2(student, Teacher).

R1

Teacher	Subject
P.Naresh	database
K.DAS	C
R.Prasad	C

R2

Student	Teacher
Jhansi	P.Naresh
Jhansi	K.Das
Subbu	P.Naresh
Subbu	R.Prasad

All the anomalies which were present in R, now removed in the above two relations.

Note

BCNF decomposition does not always satisfy dependency preserving property. After BCNF decomposition if dependency is not preserved then we have to decide whether we want to remain in BCNF or rollback to 3NF. This process of rollback is called denormalization.

Let R(A,B,C,D,E,P,G) be a relational schema in which the following FDs are known to hold: 
AB->CD
DE->P
C->E
P->C
B->G
The relation schema R is
(a) in BCNF                                       (b) in 3NF, but not in BCNF
(c) in 2NF, but not in 3NF                   (d) not in 2NF