Database normalization for relational schema design
Database normalization organizes table schemas to eliminate update anomalies, reduce data duplication, and preserve functional dependencies. In US university database courses such as Berkeley CS 186, Stanford CS 145, and CMU 15-445, normalization questions follow a strict progression: computing attribute closures, determining all candidate keys, identifying prime versus non-prime attributes, testing normal form compliance (1NF through BCNF), and decomposing schemas when violations occur.
This normalization checker automates every step of that pipeline. Given a relation schema and a set of functional dependencies, it finds all minimal candidate keys, computes the minimal cover (canonical cover), tests each normal form requirement, and produces both a 3NF synthesis and a BCNF recursive decomposition with detailed proofs of lossless joins and dependency preservation.
Understanding normal form requirements: 1NF to BCNF
Relational normal forms build hierarchically on attribute dependencies:
- First Normal Form (1NF) requires that all attribute values are atomic and relations have no repeating groups. This tool assumes atomic values from the schema definition.
- Second Normal Form (2NF) forbids partial dependencies. A partial dependency occurs when a proper subset of a candidate key determines a non-prime attribute. If any part of a compound key determines a column that is not part of any key, the relation violates 2NF.
- Third Normal Form (3NF) forbids transitive dependencies of non-prime attributes on candidate keys. Formally, for every non-trivial functional dependency X → A, either X is a superkey or A is a prime attribute (part of some candidate key).
- Boyce-Codd Normal Form (BCNF) eliminates all redundancy based on functional dependencies. For every non-trivial functional dependency X → A, the determinant X must be a superkey. Unlike 3NF, BCNF does not allow exceptions for prime attributes on the right-hand side.
Minimal cover (canonical cover) algorithm
Before decomposing a relation into 3NF, the functional dependencies must be reduced to a minimal cover (also known as a canonical cover, Fc). A minimal cover contains no redundant attributes or extraneous dependencies:
- Singleton right-hand sides: Every multi-attribute dependency X → Y is split into individual dependencies X → A for each attribute A in Y (excluding trivial dependencies where A is in X).
- Extraneous left-hand side attributes: For each dependency X → A with two or more attributes on the left, we test whether dropping attribute B leaves a determinant (X \ {B}) whose closure still determines A under the current dependencies. If so, B is extraneous and removed.
- Redundant dependencies: Dependencies are tested sequentially. If removing X → A leaves a remaining set of dependencies whose closure of X still reaches A, X → A is redundant and eliminated.
- Grouped canonical form: Dependencies sharing identical determinants are merged into X → Y₁Y₂...
Worked example 1: Course, Student, and Teacher (3NF vs BCNF)
Consider the classic database textbook relation R(C, S, J) representing Courses (C), Students (S), and Teachers/Instructors (J), with the following dependencies:
- CS → J (A student in a course has exactly one teacher)
- J → S (Each teacher teaches exactly one student)
Running this schema through the normalization library yields:
- Candidate keys: CJ and CS. Both are minimal determinants whose attribute closures under the dependencies reach all three attributes {C, J, S}.
- Prime attributes: C, J, and S. Because every attribute belongs to at least one candidate key, there are zero non-prime attributes.
- Normal form testing: Because there are no non-prime attributes, partial dependencies (2NF) and transitive dependencies on non-primes (3NF) cannot exist. Relation R is in 2NF and 3NF.
- BCNF violation: In the dependency J → S, the determinant J has closure {J, S}, which does not reach C. Because J is not a superkey, J → S violates BCNF.
- 3NF synthesis: Bernstein's synthesis creates relation R1(C, J, S). The decomposition contains one relation, guarantees a lossless join, and preserves all dependencies.
- BCNF decomposition: Decomposing on J → S produces R1(J, S) with key J, and R2(C, J) with key CJ. By Heath's theorem, this decomposition guarantees a lossless join. However, dependency preservation fails: the dependency CS → J cannot be checked in R1 or R2 alone without performing an expensive join between them.
Worked example 2: Employee Projects (2NF partial dependency)
Consider an employee assignment schema R(EmpId, ProjId, Hours, EmpName, ProjName) with dependencies:
- EmpId, ProjId → Hours
- EmpId → EmpName
- ProjId → ProjName
The library computes:
- Candidate key: {EmpId, ProjId}.
- Prime attributes: EmpId, ProjId. Non-prime attributes: EmpName, Hours, ProjName.
- 2NF violation: EmpId → EmpName and ProjId → ProjName have determinants that are proper subsets of the candidate key {EmpId, ProjId} determining non-prime attributes. The relation is only in 1NF.
- 3NF and BCNF decomposition: Decomposes into three tables: R1(EmpId, Hours, ProjId) with key {EmpId, ProjId}, R2(EmpId, EmpName) with key EmpId, and R3(ProjId, ProjName) with key ProjId. Both decompositions are lossless and preserve all original functional dependencies.
3NF synthesis vs BCNF decomposition trade-offs
In production database architecture, database engineers frequently choose 3NF over BCNF when functional dependencies span multiple attributes. While BCNF eliminates all redundancy, it cannot guarantee dependency preservation. Enforcing a lost dependency in a BCNF schema requires database triggers or application-level locks on table joins during every INSERT and UPDATE. In contrast, 3NF synthesis guarantees that every functional dependency can be verified as a simple primary key or UNIQUE constraint within a single table.