5 Normalization and Data Integrity

Dependencies, keys, and the purpose of normalization

Normalization is a way to organize relational data so that facts are stored in appropriate places rather than unnecessarily repeated. It relies on rules about the real-world domain, not merely on patterns that happen to appear in a small sample.

A Functional dependency expresses how one attribute set determines another. In $X \to Y$, each value of $X$ is associated with exactly one value of $Y$. The determinant is $X$; the dependent attribute set is $Y$.

For example, if each product has one name and one supplier, and each supplier has one name, the rules include:

• $\text{ProductID} \to \text{ProductName}, \text{SupplierID}$

• $\text{SupplierID} \to \text{SupplierName}$

• $(\text{OrderID}, \text{ProductID}) \to \text{Quantity}$

A Candidate key is a minimal set of attributes that uniquely identifies a row. A table may have multiple candidate keys, with one chosen as the primary key. A Composite key contains multiple attributes; for example, an order-item row can be identified by the pair $(\text{OrderID}, \text{ProductID})$. An attribute belonging to at least one candidate key is a prime attribute.

These concepts provide the basis for normalization: dependencies reveal which facts belong together, while keys identify the rows in which those facts are stored.

Why repeated facts cause problems

Repeated facts can cause three common anomalies:

• Update anomaly: A supplier name is repeated across many product rows, and an update changes only some of them.

• Insertion anomaly: A supplier cannot be recorded until a product is recorded as well.

• Deletion anomaly: Deleting a supplier’s last product row also removes the only stored record of that supplier.

Normalization reduces these risks by separating facts into related relations. Keys connect the relations, and joins can bring the data together when it is needed. The aim is not simply to create more tables: the design should place each fact where it can be recorded consistently and avoid losing or inventing information when relations are joined.

First normal form: one value per cell

1NF requires each row-column intersection to contain one value of the appropriate type, rather than a list or repeating group. Rows should represent individual occurrences and be distinguishable by a key.

For example, a cell containing P10, P11 stores a list of product identifiers. Instead, use one row for each product in the order:

The pair $(\text{OrderID}, \text{ProductID})$ is the composite key in this example. Reaching 1NF does not remove all redundancy: a table can have single-valued cells while repeating order dates or product names across many rows.

Takeaway: 1NF addresses the shape of individual rows and cells; it does not by itself ensure that each fact is stored only once.

Second normal form: remove partial dependencies

2NF requires a relation to be in 1NF and every non-prime attribute to depend on the whole of every candidate key. A dependency on only part of a composite key is a partial dependency. If all candidate keys have just one attribute, the relation is automatically in 2NF.

Consider an order-line relation with key $(\text{OrderID}, \text{ProductID})$ and these business rules:

• $\text{OrderID} \to \text{OrderDate}$

• $\text{ProductID} \to \text{ProductName}, \text{SupplierID}$

• $(\text{OrderID}, \text{ProductID}) \to \text{Quantity}$

The order date depends only on part of the key, $\text{OrderID}$; the product details depend only on the other part, $\text{ProductID}$. These are partial dependencies, so the relation is not in 2NF. Separate the facts into:

• Orders(OrderID, OrderDate)

• Products(ProductID, ProductName, SupplierID, SupplierName)

• OrderItems(OrderID, ProductID, Quantity)

Now order-level facts are stored with orders, product-level facts with products, and the quantity with the specific order-product pair.

Takeaway: When a key is composite, check whether any non-prime attribute depends on only part of it.

Third normal form: separate transitively dependent facts

3NF requires a relation to be in 2NF and addresses inappropriate dependencies between non-key attributes. In the Products relation, $\text{ProductID} \to \text{SupplierID}$ and $\text{SupplierID} \to \text{SupplierName}$. Thus, ProductID determines SupplierName indirectly through SupplierID. Keeping supplier names in product rows would repeat a supplier fact for each of that supplier’s products.

Store the supplier facts separately:

• Products(ProductID, ProductName, SupplierID)

• Suppliers(SupplierID, SupplierName)

Here, SupplierID in Products refers to Suppliers as a Foreign key relationship.

The formal 3NF rule is that, for every nontrivial functional dependency $X \to A$, either $X$ is a superkey or $A$ is a prime attribute. The informal practice of removing transitive dependencies is a useful guide; the formal rule also accounts for relations with multiple candidate keys.

Takeaway: Separate facts that depend on other non-key facts, while checking the formal rule when candidate keys make the informal shortcut insufficient.

Constraints and a final design check

Normalization improves a design’s structure, but constraints are also needed to enforce database rules:

• A primary key identifies rows.

• NOT NULL prevents missing values where they are not allowed.

• UNIQUE enforces additional uniqueness rules.

• A foreign key ensures that a reference points to an existing row.

• Checks or application-specific constraints can enforce other requirements.

When decomposing a relation, consider whether the resulting relations can be joined without losing or inventing information, and whether important dependencies can still be enforced. A sound design combines appropriate normalization with suitable constraints and tests of the rules the database must uphold.

The progression is cumulative: 1NF removes lists and repeating groups from cells, 2NF addresses partial dependencies on composite keys, and 3NF addresses problematic dependencies among non-key attributes.