How to Normalize a Relation in Boyce-Codd Normal Form (BCNF)

An explanation of BCNF and a walk-through of its decomposition

Normalizing a database table is important in order to remove redundancies, avoid update, insert, and delete anomalies, and preserve functional dependencies. This ensures that your database structure is simple and easy to manage without unexpected, harmful errors occurring.

BCNF Rules

When we decompose a relation into BCNF, each functional dependency F->A (read as “F determines A”) must exist so that:

F is a super key (it determines the value of all the attributes in one of the relations obtained from decomposition. For example, if EmloyeeID->EmloyeeName,Department, then EmloyeeID is a super key in the relation R(EmloyeeID, EmloyeeName, Department), but it would not be a super key in the relation R2(EmloyeeID, EmloyeeName, Department, Date) since “Date” is not determined by EmloyeeID.)

OR

F -> A is a trivial dependency (this means that the functional dependency is known to exist from common sense. For example, EmloyeeName->EmloyeeName is trivial. EmloyeeName,Department,Building->EmloyeeName is also trivial)

BCNF Decomposition Algorithm Examples

To illustrate the BCNF decomposition algorithm, here are a couple of examples:

Relation:

Person(SSN, Name, BirthMonth, ZodiacSign)

SSN->Name, BirthMonth

BirthMonth->ZodiacSign

A person has a social security number (SSN) which determines their name and birth month. A person’s birth month determines their zodiac sign.

BCNF Decomposition:

The original Person relation is not in BCNF because BirthMonth from the functional dependency BirthMonth->ZodiacSign is not a super key. Notice that SSN->Name,BirthMonth, which can be expanded to SSN->Name,BirthMonth,ZodiacSign since BirthMonth->ZodiacSign, meets the BCNF condition since SSN is a super key. However, we need a decomposition where ALL the functional dependencies meet the BCNF condition.

The relation is split on the functional dependency BirthMonth->ZodiacSign to get R1(BirthMonth, ZodiacSign), and the remaining relation becomes R2(SSN, Name, BirthMonth) with ZodiacSign removed since it can be determined from R1 given BirthMonth.

R1(BirthMonth, ZodiacSign) where BirthMonth->ZodiacSign

R2(SSN, Name, BirthMonth) where SSN->Name,BirthMonth

In this decomposition, BirthMonth is a super key in R1 and SSN is a super key in R2, so R1 and R2 are a BCNF decomposition of Person.

Relation:

M(A, B, C, D, E, F)

A->C,D

B->E

A,E->F

BCNF Decomposition:

Every functional dependency in relation M violates BCNF because none of the left hand sides are a super key of M.

So, we start by splitting M on the functional dependency A->C,D to obtain:

M1(A,C,D) where A->C,D

M2(A,B,E,F) where B->E, and A,E->F, and A,B->E,F (This is a derived functional dependency since B->E and A,E ->F)

Now, M1 is in BCNF because A is a super key and there are no other functional dependencies in that relation violating BCNF. M2 is not in BCNF because B->E and A,E->F violate BCNF (Note that A,B->E,F does not violate BCNF). We can break M2 on B->E to obtain M3 and M4:

M1(A,C,D) where A->C,D

M3(B, E) where B->E

M4(A,B,F) where only trivial functional dependencies remain

Now, M4 contains only trivial functional dependencies (A,B,F->A,B,F) and M1 and M3 contain functional dependencies where their left hand sides are super keys. So, M1, M3, and M4 are a BCNF decomposition of M.

Loss of Functional Dependencies

It is possible to lose functional dependencies when decomposing some relations into BCNF (with some relations, it can be impossible to avoid this. If this is the case, decomposing into a less strict normalized form like 3NF would be better). Notice this is what occured in the above BCNF decomposition example. The functional dependency A,E->F was lost!

Now that you know how to decompose your relation into BCNF, you can implement this in the real world by, for example, turning your relations into SQL tables and creating a database!

Hope that helps, thanks for reading!

I am a fourth year computer science major at Cal Poly SLO, and I'm excited to learn new things and share my process with others!