Functional Dependencies and Normalization
Schema design affects both correctness and efficiency. Normalization is a systematic process for reducing redundancy and eliminating update anomalies in relational schemas. It is grounded in the theory of functional dependencies.
Functional Dependencies
A functional dependency (FD) X → Y says that the value of attributes X uniquely determines the value of attributes Y. For example, StudentID → Name says each student ID has exactly one name. FDs arise from business rules and the semantics of the data.
Inference Rules (Armstrong's Axioms)
Armstrong's axioms let us derive all FDs implied by a given set: reflexivity (Y ⊆ X ⇒ X → Y), augmentation (X → Y ⇒ XZ → YZ), and transitivity (X → Y, Y → Z ⇒ X → Z). Derived rules include union, decomposition, and pseudotransitivity. The closure X+ is the set of all attributes functionally determined by X.
Update Anomalies
Poorly designed schemas suffer from insertion, update, and deletion anomalies. For instance, if student and course information are stored together, inserting a new course is impossible without a student; updating a course title requires changing every row; deleting the last student of a course loses the course entirely. Normalization eliminates these problems.
First Normal Form (1NF)
A relation is in 1NF if every attribute has an atomic value and no repeating groups. This is essentially a prerequisite for the relational model and is satisfied by all relational tables.
Second Normal Form (2NF)
A relation is in 2NF if it is in 1NF and every non-prime attribute is fully dependent on the whole primary key (no partial dependency). 2NF violations arise only when the primary key is composite.
Third Normal Form (3NF)
A relation is in 3NF if it is in 2NF and has no transitive dependency of a non-prime attribute on the primary key. A relation is 3NF iff for every FD X → A, either X is a superkey or A is a prime attribute.
Boyce-Codd Normal Form (BCNF)
BCNF is stricter than 3NF: every non-trivial FD X → A must have X as a superkey. BCNF eliminates all anomalies arising from FDs but may not always be achievable without losing dependency preservation.
Fourth and Fifth Normal Forms
4NF deals with multi-valued dependencies: X ↠ Y means that for each X, the set of Y values is independent of other attributes. 5NF (Project-Join Normal Form) addresses join dependencies; it is achieved when every join dependency is implied by candidate keys.
Decomposition
To normalize, schemas are decomposed into smaller ones. A decomposition should be lossless-join (no spurious tuples) and dependency-preserving (FDs can still be enforced locally). Algorithms exist to produce 3NF decompositions that are both lossless and dependency-preserving, and BCNF decompositions that are lossless but may sacrifice dependency preservation.
Denormalization
Sometimes schemas are deliberately denormalized for performance: reporting databases and data warehouses often accept redundancy to speed up queries. Denormalization is a conscious trade-off, not a design failure.
Summary
Normalization prevents anomalies and guides the designer toward schemas that are both logically clean and practical. Understanding FDs, normal forms, and decomposition is essential for building databases that remain correct as the application evolves.