BCNF Decomposition | A step by step approach

BCNF algorithm:

It is used to decompose any given relation to BCNF directly.

This algorithm gives guarantee for:

• Final BCNF decomposition.
• Lossless decomposition (Final BCNF decomposition will always be Lossless)

Note: This algorithm fails to give guarantee for dependency preservation.

To understand BCNF algorithm properly, we need to know the below two Definitions:

• Lossless Decomposition.
• Dependency Preservation.

Steps:

1. Identify the dependencies which violates the BCNF definition and consider that as X->A
2. Decompose the relation R into XA & R-{A} (R minus A).
3. Validate if both the decomposition are in BCNF or not. If not re-apply the algorithm on the decomposition that is not in BCNF.

All the decomposition resulted by this algorithm would be in BCNF and they would be lossless however some of the decomposition will preserved the dependencies and rest not.

BCNF is not a preferred normal form as it does not guarantee for dependency preservation.

Example:

R(A,B,C,D,E) { AB->CD, D->E, A->C, B->D}

Find the BCNF decomposition of the above relation.

Solution:

Given Relation is R(A,B,C,D,E) with dependencies as {AB->CD, D->E, A->C, B->D}

Candidate Key for this relation is AB.

[ Here I am not going to explain how to get dependency closure and determine candidate key, for this you please refer another article as below:

How to determine Candidate Key using dependency closure. ]

Hence Prime Attributes: A, B.

Non Prime Attributes: C, D, E.

using the dependency definition:

AB -> CD (Full Dependency – CD is dependent on candidate key)

D -> E ( Transitive Dependency : non prime derives non prime)

A -> C (Partial Dependency : Prime derives non prime)

B -> D (Partial Dependency : Prime derives non prime)

Hence the dependency which violates BCNF are D -> E, A -> C, B -> D.

so will take one by one the dependencies which violates the BCNF definition.

so will take D -> E first as X -> ‘A’ {not the A listed in relation as attributes}

So X = D & ‘A’ = E.

X’A’ will be DE and R-{‘A’} will be ABCD

in above decomposition AB->CD is missing which is in the original relation. however we can derive AB->CD as below:

AB->AB =>AB->A and AB->B

now AB->A and A->C => AB->C ———1

also AB->B and B->D => AB ->D ——–2

combining 1 & 2 => AB->CD

hence we can derive missing AB->CD from the decomposed relation. hence in the decomposition dependency also preserved.

All BCNF decomposition guarantees Lossless decomposition, hence above decomposition is also lossless.

Hope now BCNF decomposition would be cleared. If you have any doubt please feel free to drop your doubts in the comment section below.

Thank You.