Overview of normalisation

Suppose that the tables instructor and department are combined via natural join.

bad-relation-design-example

This relation design is not good because:

There are repetitions of information.
Null values must be used when a new department with no instructor is added.

However, not all combined schemas result in repetitions of information.

Decomposition

The only way to avoid the repetition-of-information problem in the previous example is to decompose it into two schemas: instructor and department.

However, not all decompositions are good. Consider the decomposition

Relation	Attributes
employee	ID, name, street, city, salary

into

Relation	Attributes
employee1	ID, name
employee2	name, street, city, salary

The problem arises when there are multiple employees with the same name.

lossy-decomposition-example

Such decomposition is unable to represent certain important facts about the relation before the decomposition. This kind of decomposition is referred to as a lossy decomposition. Conversely, those that are not are referred to as lossless decomposition.

Lossless decomposition

Let $r$ be a relation, $R$ be a relation schema of $r$ and let $R_{1}, R_{2}$ form a decomposition of $R$ . In other words, $R = R_{1} \cup R_{2}$ .

The decomposition is said to be lossless if there is no loss of information by replacing $R$ with $R_{1} \cup R_{2}$ . Or equivalently,

Π_{R_{1}} (r) ⋈ Π_{R_{2}} (r) = r

Conversely, a decomposition is said to be lossy if

r ⊊ Π_{R_{1}} (r) ⋈ Π_{R_{2}} (r)

Definitions with functional dependencies

Functional dependencies can be used to show when certain decompositions are lossless.

Consider the decomposition of $R$ into $R_{1}, R_{2}$ . The sufficient condtion for it to be a lossless decomposition is that at least one of the following dependencies is in $F^{+}$ :

$R_{1} \cap R_{2} \to R_{1}$
$R_{1} \cap R_{2} \to R_{2}$

Design goals of relational database

The primary goal for a relational database design is:

However, if all three of the goals cannot be achieved, then one of the followings is accepted:

Lossless BCNF: Lack of dependency preservation
3NF: More redundancy