Main Page | See live article | Alphabetical index

Database normalization

Database normalization is a series of steps followed to obtain a database design that allows for consistent storage and efficient access of data in a relational database. These steps reduce data redundancy and the chances of data becoming inconsistent.

However, many relational DBMSs lack sufficient separation between the logical database design and the physical implementation of the data store, such that queries against a fully normalized database often perform poorly. In this case denormalization is sometimes used to improve performance, at the cost of reduced consistency guarantees.

Table of contents
1 Informal Overview
2 Formal Treatment

Informal Overview

A table in a relational database is said to be in a certain normal form if it satisfies certain constraints. Edgar F. Codd's original work defined three such forms but there are now other generally accepted normal forms. We give here a short informal overview of the most common ones. Each normal form below represents a stronger condition than the previous one (in the order below). For most practical purposes, databases are considered normalized if they adhere to third normal form.

First Normal Form (or 1NF) requires that all column values in a table are atomic (e.g., a number is an atomic value, while a list or a set is not). For example, normalization eliminates repeating groups by putting each into a separate table and connecting them with a primary key-foreign key relationship.

Second Normal Form (or 2NF) requires that there are no non-trivial functional dependencies of a non-key attribute on a part of a candidate key.

Third Normal Form (or 3NF) requires that there are not non-trivial functional dependencies of non-key attributes on something else than a superset of a candidate key.

Boyce-Codd Normal Form (or BCNF) requires that there are no non-trival functional dependencies of attributes on something else than a superset of a candidate key. At this stage, all attributes are dependent on a key, a whole key and nothing but a key (excluding trivial dependencies, like A->A).

Fourth Normal Form (or 4NF) requires that there no non-trivial multi-valued dependencies of attribute sets on something else than a superset of a candidate key.

Fifth Normal Form (or 5NF or PJ/NF) requires that there are no non-trivial join dependencies that do not follow from the key constraints.

Domain-Key Normal Form (or DK/NF) requires that all constraints follow from the domain and the key constraints.

Formal Treatment

Before we can talk about normalization we first need to fix some terms from the relational model and define them in set theory. These definitions will sometimes be simplifications of their proper definitions in this model because normalization only concerns certain aspects of the relational model.

Basic notions in the relational model are relation names and attribute names. We will represent these as strings such as "Person" and "name" and we will usually use the variables r, s, t, ... and a, b, c to range over them. Another basic notion is the set of atomic values that contains values such as numbers and strings.

Our first definition concerns the notion of tuple which formalizes the notion of row or record in a table:

Def. A tuple is a partial function from attribute names to atomic values.

Def. A header is a finite set of attributes names.

Def. The projection of a tuple t on a finite set of attributes A is t[A] = { (a, v) : (a, v) ∈ t, aA }.

The next definition defines relation which formalizes the contents of a table as it is defined in the relational model.

Def. A relation is a tuple (H, B) with H, the header, a header and B, the body, a set of tuples that all have the domain H.

Such a relation closely corresponds to what is usually called the extension of a predicate in first-order logic except that here we identify the places in the predicate with attribute names. Usually in the relational model a database schema is said to consist of a set of relation names, the headers that are associated with these names and the constraints that should hold for every instance of the database schema. For normalization we will concentrate on the constraints that hold for individual relations, i.e., the relation constraints. The purpose of these constraints is to describe the relation universe, i.e., the set of all relations that are allowed to be associated with a certain relation name.

Def. A relation universe U over a header H is a non-empty set of relations with header H.

Def. A relation schema (H, C) consists of a header H and a predicate C(R) that is defined for all relations R with header H.

Def. A relation satisfies the relation schema (H, C) if it has header H and satisfies C.

Key Constraints and Functional Dependencies

One of the simpelest and most important type of relation constraint is the key constraint. It tells us that in every instance of a certain relational schema the tuples can be identified by their values for certain attributes.

Def. A superkey is written as a finite set of attribute names.

Def. A superkey K holds in a relation (H, B) if KH and there are no two distinct tupels t1 and t2 in B such that t1[K] = t2[K].

Def. A superkey holds in a relation universe U over a header H if it holds in all relations in U.

Def. A superkey K holds as a candidate key for a relation universe U over H if it holds as a superkey for U and there is no proper subset of K that also holds as a superkey for U.

Def. A functional dependency (or FD for short) is written as X->Y with X and Y finite sets of attribute names.

Def. A functional dependency X->Y holds in a relation (H, B) if X and Y are subsets of H and for all tuples t1 and t2 in B it holds that if t1[X] = t2[X] then t1[Y] = t2[Y]

Def. A functional dependency X->Y holds in a relation universe U over a header H if it holds in all relations in U.

Def. A functional dependency is trivial under a header H if it holds in all relation universes over H.

Theorem A FD X->Y is trivial under a header H iff YXH.

Theorem A superkey K holds in a relation universe U over H iff KH and K->H holds in U.

Def. (Armstrong's rules) Let S be a set of FDs then the closure of S under a header H, written as S+, is the smallest superset of S such that:
(reflexivity) if YXH then X->Y in S+
(transitivity) if X->Y in S+ and Y->Z in S+ then X->Z in S+
(augmentation) if X->Y in S+ and ZH then XZ -> YZ in S+

Theorem Armstrong's rules are sound and complete, i.e., given a header H and a set S of FDs that only contain subsets of H then the FD X->Y is in S+ iff it holds in all relation universes over H in which all FDs in S hold.

Def. If X is a finite set of attributes and S a finite set of FDs then the completion of X under S, written as X+, is the smallest superset of X such that:
if Y->Z in S and YX+ then ZX+

The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.

Theorem Given a header H and a set S of FDs that only contain subsets of H it holds that X->Y is in S+ iff YX+.

Algorithm (deriving candidate keys from FDs)
      INPUT: a set S of FDs that contain only subsets of a header H
      OUTPUT: the set C of superkeys that hold as candidate keys in
              all relation universes over H in which all FDs in S hold
      begin
        C := ∅;          // found candidate keys
        Q := { H };      // superkeys that contain candidate keys
        while Q <> ∅ do
          let K be some element from Q;
          Q := Q - { K };  
          minimal := true;
          for each X->Y in S do 
            K' := (K - Y) ∪ X;   // derive new superkey
            if K' K
            then
              minimal := false;
              Q := Q ∪ { K' };
            fi
          od
          if minimal and there is not a subset of K in C
          then
            remove all supersets of K from C;
            C := C ∪ { K };
          fi
        od
      end

Def. Given a header H and a set of FDs S that only contain subsets of H an irreducible cover of S is a a set T of FDs such that
  1. S+ = T+
  2. there is no proper subset U of T such that S+ = U+,
  3. if X->Y in T then Y is a singleton set and
  4. if X->Y in T and Z a proper subset of X then Z->Y is not in S+.

First Normal Form

Second Normal Form

Third Normal Form

Boyce-Codd Normal Form

Multi-valued and Join Dependencies

Fourth Normal Form

Fifth Normal Form

Domain-Key Normal Form

Other Dependencies


Based on material from
FOLDOC, used with permission.