Boyce-Codd Normal Form (BCNF)

Definition

A relation is in BCNF if for every non-trivial FD X → Y:

• X is a superkey

BCNF is stricter than 3NF - it eliminates ALL redundancy from FDs.

BCNF Decomposition Algorithm

Steps:

1. Start with original relation

2. While any relation violates BCNF:

   • Find violating FD X → Y (X not superkey)

   • Split into: (X ∪ Y) and (Original - Y)

3. Continue until all relations in BCNF

Example 1: BCNF Decomposition

Given:

• R(A, B, C, D)

• FDs: {A → B, C → D, B → C}

Step 1: Find Candidate Keys

• A⁺ = {A, B, C, D} → A is only candidate key

Step 2: Check BCNF Violations

• A → B: A is superkey ✓

• C → D: C is NOT superkey ✗

• B → C: B is NOT superkey ✗

Step 3: First Decomposition (using C → D)

• R₁ = {C, D}

• R₂ = {A, B, C}

Step 4: Check R₂ for BCNF

• A → B: A is superkey in R₂ ✓

• B → C: B is NOT superkey in R₂ ✗

Step 5: Second Decomposition (using B → C)

• R₂₁ = {B, C}

• R₂₂ = {A, B}

Final BCNF Decomposition:

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

Example 2: BCNF May Not Preserve Dependencies

Given:

• R(Student, Course, Instructor)

• FDs: {(Student, Course) → Instructor, Instructor → Course}

Business Rules:

1. Each student-course pair has exactly one instructor

2. Each instructor teaches exactly one course

Candidate Keys: {Student, Course}, {Student, Instructor}

BCNF Violation:

• Instructor → Course violates BCNF (Instructor not superkey)

Decomposition:

• R₁(Instructor, Course)

• R₂(Student, Instructor)

Dependency Analysis:

• ✅ Instructor → Course: Preserved in R₁

• ❌ (Student, Course) → Instructor: LOST!

Consequence: Cannot enforce "student-course has one instructor" rule at database level.