Kaushik's Notes

BCNF - Boyce-Codd Normal Form

8 min read

Overview

  • Definition: A relation is in BCNF if, for every non-trivial functional dependency X → Y, X is a superkey (contains a candidate key)
  • Purpose: Eliminates remaining anomalies that 3NF doesn’t address
  • Requirement: Must first be in 3NF
  • Stronger: More restrictive than 3NF, eliminates all functional dependency anomalies

Key Concepts

Determinant

  • Definition: The left-hand side of a functional dependency
  • Example: In A → B, A is the determinant
  • Role: Determines or controls the value of other attributes

Candidate Key

  • Definition: Minimal set of attributes that uniquely identifies each row
  • Properties:
    • Unique identification
    • Minimal (no subset can serve as key)
    • May have multiple candidate keys per table

BCNF Rule

  • Requirement: For every non-trivial functional dependency X → Y (Y not a subset of X), X must be a superkey
  • Implication: Only keys (or key-containing sets) can determine other attributes
  • Eliminates: All functional dependencies where determinant is not a superkey
  • Why superkey, not candidate key: {id, name} → x is fine (it contains the key id), even though {id, name} isn’t a minimal candidate key

Difference Between 3NF and BCNF

3NF Allows

  • Prime Attributes: Non-key attributes can be determined by non-candidate keys if the dependent attribute is prime
  • Example: In 3NF, A → B is allowed if B is part of some candidate key

BCNF Prohibits

  • All Non-Superkey Determinants: No non-trivial functional dependency allowed unless determinant is a superkey
  • Stricter Rule: Eliminates all anomalies related to functional dependencies

Violations of BCNF

Example 1: Student Advisor System

Table in 3NF but NOT BCNF:

Student_Advisor Table:
Student_ID | Subject | Advisor
S001       | Math    | Dr. Smith
S001       | Physics | Dr. Jones
S002       | Math    | Dr. Smith
S002       | Biology | Dr. Brown
S003       | Physics | Dr. Jones

Candidate Keys: (Student_ID, Subject), (Student_ID, Advisor) Functional Dependencies:

  • (Student_ID, Subject) → Advisor ✓ (Candidate key determines advisor)
  • (Student_ID, Advisor) → Subject ✓ (Candidate key determines subject)
  • Advisor → Subject ❌ (Non-candidate key determines subject)

BCNF Violation: Advisor → Subject violates BCNF because Advisor is not a superkey

Example 2: Course Instructor Time

Table in 3NF but NOT BCNF:

Course_Schedule Table:
Course_ID | Instructor | Time_Slot
CS101     | Dr. Smith  | Mon 9:00 AM
CS101     | Dr. Smith  | Wed 9:00 AM
CS103     | Dr. Smith  | Mon 2:00 PM
CS102     | Dr. Jones  | Mon 10:00 AM
MA101     | Dr. Brown  | Mon 9:00 AM

Assumptions: Each course has exactly one instructor and can meet in several time slots; an instructor teaches one course per time slot Candidate Keys: (Instructor, Time_Slot), (Course_ID, Time_Slot) Functional Dependencies:

  • (Instructor, Time_Slot) → Course_ID ✓ (Candidate key)
  • Course_ID → Instructor ❌ (Course_ID is not a superkey, but Instructor is a prime attribute, so 3NF is satisfied while BCNF is not)

Converting to BCNF

Example 1: Student Advisor System

Before (3NF but not BCNF):

Student_Advisor Table:
Student_ID | Subject | Advisor
S001       | Math    | Dr. Smith
S001       | Physics | Dr. Jones
S002       | Math    | Dr. Smith
S003       | Physics | Dr. Jones

Problem: Advisor → Subject (Each advisor teaches only one subject)

After (BCNF):

Advisor_Subject Table:
Advisor   | Subject
Dr. Smith | Math
Dr. Jones | Physics
Dr. Brown | Biology

Student_Advisor Table:
Student_ID | Advisor
S001       | Dr. Smith
S001       | Dr. Jones
S002       | Dr. Smith
S003       | Dr. Jones

Example 2: Course Instructor Time

Before (3NF but not BCNF):

Course_Schedule Table:
Course_ID | Instructor | Time_Slot
CS101     | Dr. Smith  | Mon 9:00 AM
CS101     | Dr. Smith  | Wed 9:00 AM
CS103     | Dr. Smith  | Mon 2:00 PM
CS102     | Dr. Jones  | Mon 10:00 AM

Problem: Course_ID → Instructor, so the instructor is repeated for every time slot of the course

After (BCNF):

Course_Instructor Table:
Course_ID | Instructor
CS101     | Dr. Smith
CS102     | Dr. Jones
CS103     | Dr. Smith

Course_Time Table:
Course_ID | Time_Slot
CS101     | Mon 9:00 AM
CS101     | Wed 9:00 AM
CS103     | Mon 2:00 PM
CS102     | Mon 10:00 AM
  • Lossless: Joining on Course_ID (the key of Course_Instructor) gives back exactly the original rows
  • Trade-off: (Instructor, Time_Slot) → Course_ID can no longer be enforced inside a single table (see “When BCNF Cannot Be Achieved”)

Example 3: Employee Skills Certification

Before (NOT 2NF, so also not 3NF or BCNF):

Employee_Skills Table:
Emp_ID | Skill      | Certification
E001   | Java       | Oracle_Java
E001   | Python     | Python_Institute
E002   | Java       | Oracle_Java
E002   | JavaScript | W3C_JS
E003   | Python     | Python_Institute

Assumptions:

  • Each skill has only one standard certification
  • Skill → Certification

Problem: The key is (Emp_ID, Skill), so Skill → Certification is a partial dependency (a 2NF violation), not a 3NF-but-not-BCNF case. The same decomposition fixes it

After (BCNF):

Skill_Certification Table:
Skill      | Certification
Java       | Oracle_Java
Python     | Python_Institute
JavaScript | W3C_JS

Employee_Skills Table:
Emp_ID | Skill
E001   | Java
E001   | Python
E002   | Java
E002   | JavaScript
E003   | Python

Real-World Examples

Note: The hospital and library examples below are ordinary transitive dependencies on the key (Doctor_ID → Department → Department_Head), so they are plain 3NF violations too. They don’t show what BCNF adds over 3NF; for that, see the Student/Subject/Advisor and Course/Instructor/Time_Slot examples above.

Hospital Department System

Before (Not BCNF):

Doctor_Department Table:
Doctor_ID | Department | Department_Head
D001      | Cardiology | Dr. Johnson
D002      | Neurology  | Dr. Williams
D003      | Cardiology | Dr. Johnson
D004      | Pediatrics | Dr. Davis

Assumption: Each department has only one head Problem: Department → Department_Head (violates BCNF)

After (BCNF):

Departments Table:
Department | Department_Head
Cardiology | Dr. Johnson
Neurology  | Dr. Williams
Pediatrics | Dr. Davis

Doctor_Department Table:
Doctor_ID | Department
D001      | Cardiology
D002      | Neurology
D003      | Cardiology
D004      | Pediatrics

Library Book Copies

Before (Not BCNF):

Book_Location Table:
Book_ID | Copy_No | Location | Shelf_Capacity
B001    | 1       | A1       | 100
B001    | 2       | A1       | 100
B002    | 1       | B2       | 150
B003    | 1       | A1       | 100

Assumption: Each location has fixed shelf capacity Problem: Location → Shelf_Capacity (violates BCNF)

After (BCNF):

Locations Table:
Location | Shelf_Capacity
A1       | 100
B2       | 150
C3       | 200

Book_Copies Table:
Book_ID | Copy_No | Location
B001    | 1       | A1
B001    | 2       | A1
B002    | 1       | B2
B003    | 1       | A1

When BCNF Cannot Be Achieved

Dependency Preservation

Sometimes achieving BCNF results in loss of functional dependencies:

Example: Student Subject Teacher

Original Table:
Student | Subject | Teacher
Alice   | Math    | Dr. A
Alice   | Physics | Dr. C
Bob     | Math    | Dr. B
Carol   | Math    | Dr. A

Dependencies:

  • {Student, Subject} → Teacher (each student has one teacher per subject)
  • Teacher → Subject (each teacher teaches one subject)

Problem: Teacher → Subject violates BCNF. The BCNF decomposition (Teacher, Subject) + (Student, Teacher) is lossless, but {Student, Subject} → Teacher can no longer be checked within one table, so nothing stops Alice from getting a second Math teacher without a join-based check. This is why 3NF (always dependency-preserving) is sometimes preferred.

Benefits of BCNF

Complete Functional Dependency Normalization

  • Eliminates All FD Anomalies: No functional dependency anomalies remain
  • Strongest Normal Form: For functional dependencies
  • Data Integrity: Highest level of data integrity for FDs

Prevents Sophisticated Anomalies

  • Update Anomalies: Eliminates all update anomalies from functional dependencies
  • Insert Anomalies: Prevents insertion anomalies
  • Delete Anomalies: Avoids deletion anomalies

Logical Consistency

  • Intuitive Design: Tables represent single concepts clearly
  • Clear Relationships: Relationships between entities are explicit
  • Maintainable: Easier to maintain and understand

Disadvantages of BCNF

Performance Considerations

  • More Joins: May require more joins for queries
  • Query Complexity: Queries might become more complex
  • Storage Overhead: Additional tables and foreign keys

Design Challenges

  • Not Always Possible: Some designs cannot achieve BCNF without losing dependencies
  • Over-Normalization: May lead to excessive fragmentation
  • Trade-offs: Balance between normalization and performance

Implementation Steps

Step 1: Ensure 3NF

  • Verify table is in Third Normal Form
  • All transitive dependencies eliminated

Step 2: Identify All Functional Dependencies

  • List every functional dependency in the table
  • Include both obvious and subtle dependencies

Step 3: Check Each Determinant

  • For each functional dependency X → Y
  • Verify if X is a superkey (skip trivial FDs)
  • Identify violations where X is not a superkey

Step 4: Decompose Violating Dependencies

  • Create new table for each violating functional dependency
  • Use determinant as primary key in new table
  • Remove dependent attributes from original table
  • Add foreign key reference

Step 5: Verify BCNF

  • Ensure all remaining non-trivial functional dependencies have superkeys as determinants
  • Check that no functional dependencies are lost
  • Validate referential integrity

Practical Considerations

When to Use BCNF

  • High Data Integrity Requirements: When accuracy is critical
  • Stable Schema: When structure doesn’t change frequently
  • OLTP Systems: For transaction processing systems
  • Small to Medium Tables: Where join overhead is manageable

When 3NF Might Be Sufficient

  • Performance Critical: When query performance is primary concern
  • Complex Queries: When normalization creates too many joins
  • Reporting Systems: Where denormalization benefits outweigh anomalies
  • Legacy Systems: Where restructuring is costly

Summary

  • Purpose: Eliminates all functional dependency anomalies
  • Rule: Every non-trivial FD’s determinant must be a superkey
  • Stronger than 3NF: More restrictive requirements
  • Benefits: Complete FD normalization, highest data integrity
  • Trade-offs: May increase complexity and join requirements
  • Use Case: When data integrity is more important than query performance

Graph View

Backlinks