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 risk 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.
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 no 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-trivial 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 are 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 attribute names.
- Def.- The projection of a tuple t on a finite set of attributes A is t[A] = { (a, v) : (a, v) ∈ t, a ∈ A }.
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, 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 simplest and most important types of relation constraints 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 K ⊆ H and there are no two distinct tuples 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 Y ⊆ X ⊆ H.
- Theorem A superkey K holds in a relation universe U over H iff K ⊆ H 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 Y ⊆ X ⊆ H 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 Z ⊆ H then X∪Z -> Y∪Z 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 Y ⊆ X+ then Z ⊆ X+
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 Y ⊆ X+.
- 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 set T of FDs such that
- S+ = T+
- there is no proper subset U of T such that S+ = U+,
- if X->Y in T then Y is a singleton set and
- if X->Y in T and Z a proper subset of X then Z->Y is not in S+.
First normal form
- Def. A relation is in 1NF if and only if all underlying domains contain scalar values only. (Note: that relations as defined above are necessarily in 1NF)
- define NFNF relations
- how to transform NFNF relations (also called UNF relations) to 1NF relations
- how to transform the key constraints of nested relations
- how to transform the functional dependencies of nested relations
Example
1NF requires that relations do not have repeating groups or attributes. Consider a relation for capturing an Order as follows
ORDER_NUMBER (PRIMARY_KEY)
CUSTOMER_NAME
CUSTOMER_ADDRESS
ITEM_1_NAME
ITEM_1_PRICE
ITEM_1_QUANTITY
ITEM_2_NAME
ITEM_2_PRICE
ITEM_2_QUANTITY
...
The attributes for holding information about each Item on the Order are repeated for the number of different Items ordered. These attributes should instead be placed on a separate relation called ORDER_ITEM containing the following attributes
ITEM_NAME
ORDER_NUMBER
ITEM_PRICE
ITEM_QUANTITY
An ORDER relation can then reference many ORDER_ITEMs.
Second normal form
- Def. A relation is said to be in the 2NF if and only if it is in the 1NF and every non-key attribute is irreducibly dependent on the primary key (i.e.,not partially dependent on candidate key).
- example1:taken, and semester_taken fields would belong in the STUDENTCOURSE
Example
2NF applies to relations that have Composite Primary Keys . That is, where 2 or more attributes comprise the Primary Key .
In order to find if a relation is in 2NF, ask whether any of the non-key attributes of the table could be derived from a subset of the composite key, rather than the whole composite key.
Consider a table describing Parts with the following attributes:
PART_NUMBER (PRIMARY_KEY)
SUPPLIER_NAME (PRIMARY_KEY)
PRICE
SUPPLIER_ADDRESS
The part number and supplier name form the composite primary key, because the same part can be supplied by multiple suppliers. In this example, price is correctly placed on the Part relation, because it is fully dependent on the Primary Key i.e. different suppliers will charge a different price for the same part.
Supplier Address, however, is only dependent on the Supplier Name, and therefore this relation breaks 2NF. This attribute should be placed on a second relation comprising
SUPPLIER_NAME (PRIMARY_KEY)
SUPPLIER_ADDRESS
Third normal form
- Def. A relation is said to be in the 3NF if and only if it is in the 2NF and all non-key attributes are mutually independent (i.e. there should not be transitive dependencies).
- Third Normal Form is the most common level of normalization.
- example: Given this relation (#A, B, C) in 2NF where #A->B, #A->C and B->C (first two are fixed by 2NF). This relation isn't in 3NF because C is functionally dependent from B. This relation should be descomposed into (#A, B),(#B, C) or (#A, B), (#A, C) to be in 3NF.
- (rissanen's rule ? )
- how to transform from 2NF to 3NF
- def: dependency preserving
- can always be reached while staying dependency preserving
Example
A relation is in 3NF if none of the non-Primary Key attributes is a fact about any other non-Primary Key attribute.
Consider a relation that defines a Part as having the following attributes.
PART_NUMBER (PRIMARY_KEY)
MANUFACTURER_NAME
MANUFACTURER_ADDRESS
In this case, the manufacturer address does not belong on this relation, because it is a fact about the Manufacturer of the Part, rather than the Part itself. Manufacturer should therefore be made into a separate relation with the attributes
MANUFACTURER_NAME (PRIMARY_KEY)
MANUFACTURER_ADDRESS
and the Part relation should be redefined as
PART_NUMBER (PRIMARY_KEY)
MANUFACTURER_NAME
Boyce-Codd normal form
- Def. A relation is said to be in the BCNF if and only if it is in the 3NF and every non-trivial, left-irreducible functional dependency has a candidate key as its determinant. In more informal terms, a relation is in BCNF if it is in 3NF and the only determinants are the candidate keys.
- example
- how to transform from 3NF to BCNF
- can not always be reached in a dependency preserving way.
Multi-valued and join dependencies
- def Given a relation (A,B,C) there is a multi-valued dependency between A and B noted by A->>B if and only if the set of values of B, given a fixed value (a: A, c: C), only depends on a and is independent of c.
- example
- trivial multi-value dependency (X->>Y is trivial if X+Y contains all attributes or Y is a subset of X)
- reasoning rules for MVDs (it only can happen if the relation have at least tree attributes, all functional dependency implies multi-valued dependeny but not in the other direction)
- def join dependency
- example
- reasoning rules for JDs
- when is join dependency implied by key constraints?
- Fagin's theorem: A relation (A,B,C) can be decomposed lossless in (A,B) and (A,C) if and only if A->> B | C is true in (A,B,C).
- relationship between JDs and MVDs
Fourth normal form
- Def. A relation is said to be in 4NF if and only if it is in the BCNF and multi-valued dependencies are functional dependencies.
- Notes: The 4NF removes unwanted data structures: multi-valued dependencies. Ronald Fagin demonstrated that it is always possible to achieve 4NF (but not always desirable). Rissanen's theorem is also applicable on multi-valued dependencies.
- example
- how to transform from BCNF to 4NF
Example
Consider a case where an Employee relation has multiple job categories and multiple locations where they work. It might be tempting to create a relation as follows to capture this information:
EMPLOYEE_ID
JOB_CATEGORY_ID
LOCATION_ID
The problem with this relation is that we might have to enter Employees Job Category more than once if they fulfill the same Job Category at more than one location. Therefore this relation is not in 4NF.
There are actually 3 distinct many-to-many relationships here, one between Employee and Job Category, one between Employee and Location, and one between Job Category and Location. So 3 relations should be created to capture these.
EMPLOYEE_JOB_CATEGORY relation:
EMPLOYEE_ID
JOB_CATEGORY_ID
EMPLOYEE_LOCATION relation:
EMPLOYEE_ID
LOCATION_ID
JOB_CATEGORY_LOCATION relation:
JOB_CATEGORY_ID
LOCATION_ID
Fifth normal form
- Def. A relation R is said to be in the 5NF if and only if it is in 4NF and every join dependency in R is implied by the candidate keys.
- example
- from 4NF to 5NF
- explain that ultimate normal form that can be reached with projections
Domain-key normal form
- 1NF, 2NF, 3NF, BCNF, 4NF, 5NF are all subsets of the general constraints (G) and thus are all special cases of DK/NF
- ultimate normal form as any general constraint on the Universe of Discourse can be included in the set G
- emphasizes on separating the attributes according to themes
- have to take into account all the logical consequences of domains and keys
- has no modificational anomalies
Other dependencies
- embedded dependencies
- dependencies as statements in first-order logic
Implementation notes
- At 3NF it may become necessary to create additional entities in order to normalize relations beyond 3NF. From an implementation standpoint, this is not always desirable due to possible performance issues, and sheer complexity. See Denormalization.
References
