BCNF and BCNF Decomposition

Definition

A relation is in Boyce-Codd normal form when, for every non trivial functional dependency X -> Y that holds:

  X must be a SUPER KEY.

  One condition. No exemptions, no clauses about prime
  attributes. Every determinant must determine the whole
  relation.

3NF and BCNF side by side

Every relation in BCNF is in 3NF. The reverse is not true. That single sentence is the answer to the most common question on this topic.

The classic 3NF but not BCNF relation

  ADDRESS ( city, street, pincode )

  F = { { city, street } -> pincode
      , pincode          -> city }

  Reasoning:
    a city and street together identify a pincode
    a pincode belongs to exactly one city

  candidate keys
    { city, street }+  = { city, street, pincode }  = R  -> key
    { street, pincode }+ : pincode -> city gives city,
                           so = { street, pincode, city } = R -> key

  prime attributes: city, street, pincode - all three
  non prime: none

  3NF TEST
    { city, street } -> pincode   left side is a key    ok
    pincode -> city               pincode is not a key,
                                  BUT city is prime      ok
    -> IN 3NF

  BCNF TEST
    pincode -> city               pincode is not a super key
    -> NOT IN BCNF

  The redundancy 3NF left behind

  city    | street        | pincode
  --------+---------------+--------
  Chennai | Anna Salai    | 600002
  Chennai | Mount Road    | 600002
  Chennai | Poonamallee   | 600002
  Madurai | West Masi     | 625001

  "pincode 600002 is in Chennai" is stored three times.
  Change it once and miss the others, and the relation
  contradicts itself. That is a real anomaly, and 3NF
  permitted it.

BCNF decomposition

  ALGORITHM

  while some relation R is not in BCNF:
      find a dependency  X -> Y  in R where X is not a super key
      replace R with two relations:
          R1 = ( X union Y )          the offending dependency
          R2 = ( X union ( R minus Y ) )   X kept as the link
      repeat until every relation is in BCNF

  R1 and R2 share exactly X, and X is a key of R1, which is
  what guarantees the decomposition is LOSSLESS.

  APPLYING IT to ADDRESS

  offending dependency:  pincode -> city

    R1 = ( pincode, city )
    R2 = ( pincode, street )      = X union ( R minus Y )

  Check R1: key is pincode, and pincode -> city.
            determinant is the key.              -> BCNF
  Check R2: key is { pincode, street }. No other
            dependency holds inside it.          -> BCNF

  Lossless? The shared attribute is pincode, which is a
  key of R1. Yes.

  Dependency preserving? The original dependency
  { city, street } -> pincode is now SPLIT across two
  relations. Neither relation can enforce it alone, and
  checking it needs a join.

  So the decomposition is LOSSLESS but NOT dependency
  preserving. This is not a mistake in the working - it is
  a genuine, unavoidable property of this relation.

The trade off

  Some relations simply cannot be in BCNF and dependency
  preserving at the same time. You must choose:

  KEEP 3NF                      GO TO BCNF
    all dependencies              no redundancy from
    enforceable locally           functional dependencies
    some redundancy remains       one dependency now needs
                                  a join to check

  WHICH TO CHOOSE
    if the lost dependency is critical and checked often
        -> stay at 3NF
    if the redundancy causes real anomalies in practice
        -> go to BCNF and enforce the lost rule with a
           trigger or application check

  Most production schemas end up at 3NF or BCNF, and the
  difference rarely matters because most relations that are
  in 3NF are already in BCNF anyway.

When 3NF is automatically BCNF

• The relation has only one candidate key.
• Every candidate key is a single attribute.
• No two candidate keys overlap.

The 3NF but not BCNF case requires overlapping composite candidate keys, which is why it is uncommon in real designs and common in exams.

A second worked example

  TEACHING ( student, subject, teacher )

  Rules:
    each teacher teaches exactly one subject
    for each subject a student has exactly one teacher

  F = { { student, subject } -> teacher
      , teacher              -> subject }

  candidate keys: { student, subject }, { student, teacher }
  prime: student, subject, teacher.  non prime: none

  3NF:  teacher -> subject. teacher is not a key, but
        subject is prime -> IN 3NF
  BCNF: teacher is not a super key -> NOT IN BCNF

  DECOMPOSE on teacher -> subject

    R1 ( teacher, subject )
    R2 ( teacher, student )

  Both in BCNF. Lossless, since teacher is a key of R1.
  The dependency { student, subject } -> teacher is lost.

Common mistakes

• Thinking BCNF is always achievable with dependency preservation. It is not, and saying so is the marked point.
• Testing only the given dependencies. Every dependency implied by F must satisfy the rule.
• Decomposing on the wrong dependency. Choose one whose determinant is not a super key.
• Losing the shared attribute. X must appear in both relations, or the decomposition is lossy.
• Claiming 3NF and BCNF always differ. They coincide unless candidate keys overlap.

Exam and interview questions

1. Define BCNF and state how it differs from 3NF.
2. Give a relation in 3NF but not in BCNF and show why.
3. Write the BCNF decomposition algorithm and explain why it is lossless.
4. Why can BCNF decomposition lose a dependency? Give an example.
5. Under what conditions is a 3NF relation automatically in BCNF?

Practice

1. R ( A, B, C ), F = { A B -> C, C -> B }. Find the keys, test 3NF and BCNF, and decompose if needed.
2. Decompose TEACHING above and verify losslessness by joining the two relations back.
3. Give a relation with two overlapping candidate keys that is nevertheless in BCNF.

Conclusion

BCNF demands that every determinant be a super key. It removes the redundancy 3NF permits through the prime attribute exemption, but it cannot always preserve every dependency — so the choice between 3NF and BCNF is a genuine engineering decision, not an automatic upgrade.