Normalization and Schema Quality

Introduction and Context

A relational schema is more than a collection of tables. It is a formal representation of business facts, rules, and relationships. A poorly designed schema may store the same fact repeatedly, permit contradictory values, or make ordinary operations unexpectedly difficult. Normalization provides a principled method for reducing such problems by decomposing relations according to dependencies among attributes.

Normalization is not a mechanical requirement that every database must pursue to the highest possible normal form. It is a design discipline. A normalized schema generally improves integrity and maintainability, while carefully justified denormalization may improve performance for read-intensive workloads. The professional task is to understand the theoretical consequences of each choice and document the trade-off.

Learning Objectives

By the end of this chapter, you should be able to:

• explain functional, partial, transitive, and multivalued dependencies;
• identify candidate keys, prime attributes, and non-prime attributes;
• diagnose insertion, update, and deletion anomalies;
• apply 1NF, 2NF, 3NF, BCNF, 4NF, and 5NF;
• evaluate lossless decomposition and dependency preservation;
• use MySQL or PostgreSQL constraints to enforce a sound design; and
• make and justify normalization or denormalization decisions.

1. The Information-Management Problem

Consider this relation:

Enrollment(StudentID, StudentName, CourseID, CourseTitle, InstructorID, InstructorName, Grade)

Suppose each student can enroll in many courses, each course has one instructor, and student and course identifiers determine their names and titles. A row records a student-course enrollment. The same student name is repeated for every enrolled course, and the same course and instructor data are repeated for every student.

This repetition creates three classic anomalies:

• Update anomaly: changing an instructor's name requires changing several rows. If only some rows are changed, the database becomes inconsistent.
• Insertion anomaly: a course cannot be recorded until at least one student enrolls, even though the course exists independently.
• Deletion anomaly: deleting the last enrollment for a course may accidentally delete the only stored information about that course.

Normalization separates facts with different determinants. The result is usually a set of smaller relations connected by keys and foreign keys.

2. Functional Dependencies and Keys

2.1 Functional dependency

A functional dependency (FD) X → Y in a relation means that each value of attribute set X is associated with at most one value of attribute set Y. X is the determinant, and Y is functionally dependent on X.

For example:

• StudentID → StudentName
• CourseID → CourseTitle, InstructorID
• (StudentID, CourseID) → Grade

An FD is a semantic rule about the data domain, not merely a pattern observed in a small sample. If two rows currently happen to share the same course title, that does not prove that CourseTitle → CourseID or its reverse holds.

Important inference rules include:

• Reflexivity: if Y is a subset of X, then X → Y.
• Augmentation: if X → Y, then XZ → YZ.
• Transitivity: if X → Y and Y → Z, then X → Z.

These are Armstrong's axioms. They are sound and complete for reasoning about functional dependencies.

2.2 Superkeys, candidate keys, and prime attributes

A superkey is an attribute set that uniquely identifies a tuple. A candidate key is a minimal superkey: removing any attribute destroys uniqueness. A chosen candidate key is commonly called the primary key; other candidate keys are alternate keys.

An attribute belonging to at least one candidate key is a prime attribute. An attribute belonging to no candidate key is a non-prime attribute. This distinction is essential in 2NF and 3NF. The phrase “non-key attribute” is often used informally, but it can be misleading when alternate candidate keys exist.

For Enrollment(StudentID, CourseID, Grade), assuming a student receives at most one grade per course, (StudentID, CourseID) is a candidate key. Grade is non-prime, while StudentID and CourseID are prime.

2.3 Closure of an attribute set

The closure X⁺ is the set of all attributes functionally determined by X under a given FD set. To compute it, begin with X and repeatedly add attributes whose determinants are already contained in the closure. If X⁺ contains every attribute in the relation, X is a superkey.

Example, with FDs:

• StudentID → StudentName
• CourseID → CourseTitle, InstructorID
• InstructorID → InstructorName
• (StudentID, CourseID) → Grade

The closure of (StudentID, CourseID) is:

{StudentID, CourseID}

→ add StudentName

→ add CourseTitle, InstructorID

→ add InstructorName

→ add Grade.

Thus the closure contains every attribute, so (StudentID, CourseID) is a superkey. Neither StudentID nor CourseID alone determines all attributes, so the pair is minimal and is a candidate key.

3. Normal Forms

Normal forms are increasingly restrictive conditions. They should be applied using all candidate keys, not only the selected primary key.

3.1 First normal form (1NF)

A relation is in 1NF when each attribute contains atomic, indivisible values for the chosen relational model, and repeating groups or arrays are not used to represent multiple values in one cell.

A table such as Customer(CustomerID, Name, Phone1, Phone2) is not necessarily a good design even if it technically has scalar columns. The numbered phone columns represent a repeating group with an arbitrary limit. A better design is:

• Customer(CustomerID, Name)
• CustomerPhone(CustomerID, PhoneNumber)

1NF does not eliminate redundancy, and it does not require every value to be physically indivisible in every possible sense. “Atomic” is interpreted relative to the operations and constraints required by the application.

3.2 Second normal form (2NF)

A relation is in 2NF if:

1. it is in 1NF; and
2. every non-prime attribute is fully functionally dependent on every candidate key.

A partial dependency occurs when a non-prime attribute depends on a proper subset of a candidate key. It is not enough to say that an attribute depends on “part of the primary key”; alternate candidate keys must also be considered.

In Enrollment(StudentID, CourseID, StudentName, CourseTitle, Grade), the candidate key is (StudentID, CourseID). The dependencies StudentID → StudentName and CourseID → CourseTitle are partial dependencies because each determinant is a proper subset of the composite key and each dependent is non-prime. Decompose into:

• Student(StudentID, StudentName)
• Course(CourseID, CourseTitle)
• Enrollment(StudentID, CourseID, Grade)

Important qualification: if a relation has only single-attribute candidate keys, it has no proper subset of a candidate key that could produce a partial dependency, and therefore it satisfies 2NF provided it is in 1NF. However, the mere existence of one single-attribute candidate key does not by itself guarantee 2NF if another composite candidate key exists and a non-prime attribute depends on a proper subset of that composite key.

For example, suppose candidate keys are {A} and {B,C}, and the FD B → D holds, where D is non-prime. The dependency is partial with respect to candidate key {B,C}. The relation is therefore not in 2NF, despite having the single-attribute candidate key A.

3.3 Third normal form (3NF)

A relation is in 3NF if, for every nontrivial FD X → A, at least one condition holds:

• X is a superkey; or
• A is a prime attribute.

A nontrivial FD is one where A is not already a member of X. Equivalently, 3NF prohibits a non-prime attribute from depending transitively on a candidate key through another non-key determinant.

In Course(CourseID, CourseTitle, InstructorID, InstructorName), assume:

• CourseID → CourseTitle, InstructorID
• InstructorID → InstructorName.

Then CourseID → InstructorName follows transitively. Decompose into:

• Course(CourseID, CourseTitle, InstructorID)
• Instructor(InstructorID, InstructorName).

The formal definition is safer than the informal slogan “no transitive dependencies,” because 3NF permits some dependencies whose right-hand side is prime.

3.4 Boyce–Codd normal form (BCNF)

A relation is in BCNF if, for every nontrivial FD X → Y, X is a superkey. BCNF is stricter than 3NF because it does not provide the 3NF exception for a prime attribute.

Consider Teaching(Student, Course, Instructor) with rules:

• (Student, Course) → Instructor
• Instructor → Course because each instructor teaches one course in this simplified domain.

Instructor is not a superkey for the relation, so Instructor → Course violates BCNF. A decomposition can be:

• InstructorCourse(Instructor, Course)
• StudentInstructor(Student, Instructor).

BCNF decomposition may fail to preserve every dependency in the original schema, so dependency preservation must be checked rather than assumed.

3.5 Fourth normal form (4NF) and multivalued dependencies

A multivalued dependency (MVD) X ↠ Y states that, for a given X, the set of Y values is independent of the remaining attributes Z = R − X − Y. In practical terms, two independent many-valued facts should not be stored in one relation.

Suppose PersonSkillLanguage(Person, Skill, Language) records skills and spoken languages, and a person's skills are independent of their languages. If Alex has two skills and two languages, the relation may need four combinations. The redundancy is not an FD problem; it is an MVD problem:

• Person ↠ Skill
• Person ↠ Language.

A relation is in 4NF if, for every nontrivial MVD X ↠ Y, X is a superkey. Decompose into:

• PersonSkill(Person, Skill)
• PersonLanguage(Person, Language).

The MVD is nontrivial when Y is not a subset of X and X ∪ Y is not the entire relation schema.

3.6 Fifth normal form (5NF)

5NF, also called project-join normal form (PJ/NF), addresses redundancy caused by join dependencies that are not reducible to functional or multivalued dependencies.

A join dependency states that a relation is equal to the join of several projections. A relation is in 5NF if every nontrivial join dependency is implied by the candidate keys. Thus, no further lossless decomposition based on a join dependency is possible unless that dependency is already a consequence of the key structure.

A classic pattern is SupplierPartProject(Supplier, Part, Project), where a triple is valid exactly when the supplier supplies the part, the supplier serves the project, and the project uses the part. If that business rule is genuinely equivalent to the join of three binary relationships, storing triples creates redundancy. The design may be decomposed into:

• SupplierPart(Supplier, Part)
• SupplierProject(Supplier, Project)
• PartProject(Part, Project).

This decomposition is justified only when the business semantics guarantee the join dependency. 5NF is relatively uncommon in everyday application schemas because its dependencies are difficult to discover and excessive decomposition can make queries complex.

4. Lossless Decomposition and Dependency Preservation

A decomposition is lossless if joining the decomposed relations reconstructs exactly the original legal relation, without spurious tuples. It is dependency preserving if all original dependencies can be enforced by examining the decomposed relations without repeatedly joining them.

For a binary decomposition of R into R₁ and R₂, a standard losslessness test is that the common attributes R₁ ∩ R₂ functionally determine R₁ or R₂ under the closure of the dependencies. For example, decomposing Course(CourseID, CourseTitle, InstructorID, InstructorName) into Course(CourseID, CourseTitle, InstructorID) and Instructor(InstructorID, InstructorName) is lossless because the common attribute InstructorID determines all attributes of the second relation.

The synthesis algorithm for 3NF commonly produces a dependency-preserving, lossless design. BCNF decomposition guarantees losslessness under its standard decomposition procedure, but may not preserve all dependencies. A designer must therefore balance formal normal form against enforceability and operational simplicity.

5. A Worked Normalization Example

Consider:

OrderLine(OrderNo, ProductNo, OrderDate, CustomerNo, CustomerName, ProductName, UnitPrice, Quantity)

Assume:

• OrderNo → OrderDate, CustomerNo
• CustomerNo → CustomerName
• ProductNo → ProductName, UnitPrice
• (OrderNo, ProductNo) → Quantity

The candidate key is (OrderNo, ProductNo). OrderDate, customer data, and product data depend on only part of the composite key, so the relation violates 2NF. CustomerName also depends transitively on OrderNo through CustomerNo.

A suitable decomposition is:

• Orders(OrderNo, OrderDate, CustomerNo)
• Customers(CustomerNo, CustomerName)
• Products(ProductNo, ProductName, UnitPrice)
• OrderLines(OrderNo, ProductNo, Quantity).

Each relation has a clear determinant. OrderLines stores facts about a particular product on a particular order, while the other relations store facts about orders, customers, and products. The decomposition is lossless when the foreign-key relationships are correctly defined.

In PostgreSQL, representative constraints might be:

CREATE TABLE customers (
    customer_no integer PRIMARY KEY,
    customer_name text NOT NULL
);

CREATE TABLE orders (
    order_no integer PRIMARY KEY,
    order_date date NOT NULL,
    customer_no integer NOT NULL REFERENCES customers(customer_no)
);

CREATE TABLE order_lines (
    order_no integer NOT NULL REFERENCES orders(order_no),
    product_no integer NOT NULL REFERENCES products(product_no),
    quantity integer NOT NULL CHECK (quantity > 0),
    PRIMARY KEY (order_no, product_no)
);

MySQL supports the same relational principles with appropriate engine and data-type choices. The database should enforce candidate keys with PRIMARY KEY or UNIQUE, mandatory participation with NOT NULL, domain rules with CHECK where supported, and referential rules with FOREIGN KEY.

6. Normalization in Professional Design

A practical workflow is:

1. collect business rules, not merely sample rows;
2. list attributes and determine candidate keys;
3. identify FDs and MVDs with domain experts;
4. compute closures to test keys and implications;
5. remove repeating groups and achieve 1NF;
6. remove partial dependencies for 2NF;
7. remove transitive non-prime dependencies for 3NF;
8. test whether BCNF, 4NF, or 5NF is warranted;
9. verify losslessness and dependency preservation;
10. implement constraints, indexes, and tests; and
11. benchmark realistic workloads before denormalizing.

Normalization is not the same as splitting every column into its own table. Excessive decomposition can increase joins, complicate reporting, and make transactional logic harder to understand. Conversely, leaving derived or duplicated facts in place without controls creates integrity risk.

7. Denormalization: A Justified Exception

Denormalization intentionally introduces controlled redundancy for a documented purpose, such as reducing expensive joins, supporting a star schema, serving a read model, or maintaining a materialized summary. It should follow, rather than replace, a normalized conceptual design.

For example, an order API may need customer name, order date, and total amount in one response. Instead of duplicating customer names in the transactional Orders table, an application can use a view, materialized view, cache, or separately maintained read model. If a summary column is stored, its maintenance mechanism must be explicit: transaction triggers, application logic, scheduled refresh, or an event-driven pipeline.

A denormalization decision should document:

• the performance problem and measured baseline;
• the duplicated facts and their authoritative source;
• synchronization and failure handling;
• acceptable staleness;
• constraints and reconciliation jobs; and
• rollback and monitoring procedures.

Indexes, query planning, partitioning, caching, and materialized views should be considered before duplicating base facts.

8. Case Study: A University Registration Platform

This is an illustrative case.

Background

A university initially stores registration data in Registration(StudentID, StudentName, Program, CourseID, CourseTitle, InstructorID, InstructorName, Semester, Grade). Staff report inconsistent instructor names and difficulty adding a new course before registration opens.

Problem analysis

The business rules are:

• StudentID determines StudentName and Program.
• CourseID and Semester determine the offering and its instructor.
• InstructorID determines InstructorName.
• StudentID, CourseID, and Semester determine Grade.

The registration key is (StudentID, CourseID, Semester). Student facts depend only on StudentID; course facts depend on CourseID; offering facts depend on (CourseID, Semester); and instructor name depends transitively on InstructorID. The original relation therefore contains partial and transitive dependencies.

Solution

A normalized design is:

• Student(StudentID, StudentName, Program)
• Course(CourseID, CourseTitle)
• Instructor(InstructorID, InstructorName)
• Offering(CourseID, Semester, InstructorID)
• Registration(StudentID, CourseID, Semester, Grade).

The primary key of Offering is (CourseID, Semester), and Registration references the offering through a composite foreign key. A unique constraint can enforce that one student has at most one registration for an offering.

Outcome

A student can be added without an enrollment, a course can be offered without registrations, and an instructor's name is updated once. The trade-off is that a transcript query requires joins. Indexes on foreign-key columns and materialized reporting views can address measured reporting costs without corrupting the transactional model.

Learning points

The quality of a decomposition depends on accurately stated business rules. Normalization cannot correct an incorrect rule, an incomplete key, or an unrecognized temporal condition such as semester-specific instructor assignments.

9. Limitations, Governance, and Contemporary Practice

Normalization depends on domain knowledge. Hidden rules, nullable attributes, temporal changes, and poorly defined identifiers can produce a formally elegant but semantically wrong schema. Null values also complicate informal dependency reasoning because SQL's three-valued logic is not identical to classical relational theory.

Governance matters: keys should avoid exposing unnecessary personal information, access should follow least privilege, and audit requirements should determine whether historical values must be preserved rather than overwritten. AI-assisted schema tools can suggest dependencies or detect repeated values, but they cannot reliably infer business semantics from data alone. Human review, constraint testing, and representative workload testing remain necessary.

Chapter Summary

Normalization organizes relational facts around their determinants. Functional dependencies support reasoning about keys and decomposition; multivalued dependencies explain independent many-valued facts; and join dependencies motivate 5NF. 1NF removes repeating groups, 2NF removes partial dependencies of non-prime attributes on proper subsets of candidate keys, 3NF removes problematic transitive dependencies, BCNF requires every determinant of a nontrivial FD to be a superkey, 4NF controls nontrivial MVDs, and 5NF requires every nontrivial join dependency to be implied by candidate keys. A sound design must also be lossless and sufficiently dependency preserving. Denormalization is acceptable when measured performance or operational requirements justify controlled redundancy and its maintenance is governed.

Key Terms

Functional dependency: A rule X → Y stating that X determines Y.

Determinant: The left-hand side of a dependency.

Superkey: An attribute set that uniquely identifies a tuple.

Candidate key: A minimal superkey.

Primary key: The candidate key selected as the principal identifier.

Alternate key: A candidate key not selected as the primary key.

Prime attribute: An attribute belonging to at least one candidate key.

Non-prime attribute: An attribute belonging to no candidate key.

Partial dependency: A dependency of a non-prime attribute on a proper subset of a candidate key.

Transitive dependency: A dependency obtained through an intermediate determinant.

Multivalued dependency: A rule X ↠ Y expressing independent sets of values.

Join dependency: A constraint stating that a relation equals the join of projections.

Lossless decomposition: Decomposition that reconstructs exactly the original legal relation.

Dependency preservation: Ability to enforce original dependencies without recombining relations.

1NF: Normal form requiring atomic values and no repeating groups.

2NF: 1NF plus no partial dependency of a non-prime attribute on a candidate key.

3NF: A normal form defined by the superkey-or-prime-right-side condition.

BCNF: Every determinant of a nontrivial FD is a superkey.

4NF: Every determinant of a nontrivial MVD is a superkey.

5NF: Every nontrivial join dependency is implied by candidate keys.

Review Questions

Short Answer Questions

1. Distinguish a candidate key from a superkey.
2. Why is a partial dependency defined using non-prime rather than merely “non-key” attributes?
3. State the formal condition for BCNF.
4. What kind of redundancy does 4NF address?
5. Explain the difference between losslessness and dependency preservation.

Long Answer Questions

1. Explain the progression from 1NF through BCNF using a single registration example.
2. Compare 3NF and BCNF, including the 3NF exception for a prime attribute.
3. Explain functional, multivalued, and join dependencies and associate each with the normal form that primarily addresses it.
4. Describe a normalization workflow for a new transactional database.
5. Discuss why denormalization should normally follow, rather than replace, normalization.

Analytical / Application Questions

1. A relation has candidate keys {A} and {B,C}, and the FD B → D, where D is non-prime. Determine whether the relation is in 2NF and justify your answer.
2. Given OrderLine(OrderNo, ProductNo, CustomerNo, CustomerName, ProductName, Quantity) with OrderNo → CustomerNo, CustomerNo → CustomerName, ProductNo → ProductName, and (OrderNo, ProductNo) → Quantity, identify the anomalies and propose a lossless decomposition.
3. A reporting query is slow after normalization. Propose two alternatives to duplicating base facts, and specify what evidence would justify a final denormalization decision.

Multiple Choice Questions with Answers

Question 1

Which statement correctly defines a partial dependency?

A. A prime attribute depends on any superkey.

B. A non-prime attribute depends on a proper subset of a candidate key.

C. Any attribute depends on a foreign key.

D. A relation contains two candidate keys.

Correct Answer: B. A non-prime attribute depends on a proper subset of a candidate key.

Question 2

A relation has candidate keys {A} and {B,C}. The FD B → D holds, and D is non-prime. Is the relation automatically in 2NF because {A} is a single-attribute candidate key?

A. Yes, every single-attribute candidate key guarantees 2NF.

B. Yes, because B is prime.

C. No, because B is a proper subset of the composite candidate key {B,C}.

D. No, because 2NF prohibits all composite candidate keys.

Correct Answer: C. No, because B is a proper subset of the composite candidate key {B,C}.

Question 3

Which condition defines BCNF?

A. Every non-prime attribute depends on the whole primary key.

B. Every determinant of a nontrivial functional dependency is a superkey.

C. Every relation has exactly one candidate key.

D. Every multivalued dependency has a prime right-hand side.

Correct Answer: B. Every determinant of a nontrivial functional dependency is a superkey.

Question 4

Which dependency most directly motivates a 4NF decomposition?

A. CourseID → CourseTitle

B. StudentID → StudentName

C. Person ↠ Skill, where skills are independent of languages

D. OrderNo → OrderDate

Correct Answer: C. Person ↠ Skill, where skills are independent of languages

Question 5

What is the formal 5NF criterion?

A. Every relation must have a single-attribute primary key.

B. Every nontrivial join dependency must be implied by candidate keys.

C. Every FD must have a foreign key on its right side.

D. Every table must contain at least three attributes.

Correct Answer: B. Every nontrivial join dependency must be implied by candidate keys.

Question 6

In the FD set StudentID → StudentName and CourseID → CourseTitle, with candidate key (StudentID, CourseID), what kind of dependency is StudentID → StudentName?

A. A partial dependency if StudentName is non-prime

B. A multivalued dependency only

C. A join dependency

D. A dependency that violates 1NF

Correct Answer: A. A partial dependency if StudentName is non-prime

Question 7

Which property means that joining decomposed relations does not create spurious tuples and reconstructs the original legal relation?

A. Dependency preservation

B. Lossless decomposition

C. Denormalization

D. Augmentation

Correct Answer: B. Lossless decomposition

Question 8

In an order-line schema, ProductNo → ProductName and UnitPrice, while (OrderNo, ProductNo) → Quantity. What is the main reason to place product attributes in a separate Product relation?

A. Product attributes depend only on part of the composite line key.

B. Product attributes are always multivalued.

C. ProductNo cannot be a candidate key.

D. Separating them guarantees BCNF in every possible domain.

Correct Answer: A. Product attributes depend only on part of the composite line key.

Question 9

Which statement about 3NF is correct?

A. Every determinant must be a superkey, with no exception.

B. For every nontrivial FD X → A, X is a superkey or A is prime.

C. 3NF removes all multivalued dependencies.

D. 3NF requires every attribute to be part of the primary key.

Correct Answer: B. For every nontrivial FD X → A, X is a superkey or A is prime.

Question 10

Which is the best first response when a normalized reporting schema produces slow queries?

A. Duplicate every column in every table immediately.

B. Remove all foreign keys to reduce checking overhead.

C. Measure query plans and consider indexes, views, or materialized views before controlled denormalization.

D. Replace all candidate keys with random text values.

Correct Answer: C. Measure query plans and consider indexes, views, or materialized views before controlled denormalization.