CSc Databases 3- Normalisation

What is normalisation?

It is a process which takes a relation schema through a series of tests to certify whether it satisfies a certain normal form. It proceeds in a top down fashion rather than a bottom up one.

The two requirements of first normal form:

The domain of an attribute must include only atomic values.

The value of any attribute in a tuple must be a single value from the domain of that attribute.

1NF does not allow multi-valued attributes, composite attributes or combinations thereof. This means no single value for a single tuple can be a list (eg. a person's children). There can also not be any nested relations (eg. an address attribute, which itself has sub-attributes of number, street name and city).

Remove the attribute that violates 1NF.

Place the attribute in a new relation, along with the primary key from the original relation.

eg. Children (a value that could potentially be multiple). The "children" attribute and the "ID" attribute of the original relation are used to create a new relation with only these attributes. The primary key of the new relation is the whole tuple. Now what was ID={123} and children={Fred, Daphne} is now ID={123} and children={Fred} and ID={123} and children={Daphne}. ID is a foreign key that leads back to the original relation.

This is known as "primary key propogation".

Expand the key and make a separate tuple for each value of the multi-valued/composite attribute.

The problem with this solution is increased redundancy. For each new tuple created, there is a new set of values that must ALL be updated, when usually only one tuple would need to be changed.

If we know the maximum amount of values in the multi-valued attribute, we can replace it by that number of atomic attributes.

eg. instead of one attribute "children", 10 attributes "child1", "child2", "child3"...etc.

The disadvantage of this solution is that it introduces NULL values if a tuple does not fill every attribute.

The first one.

It does not suffer from redundancy, and there is no limit on the maximum number of values.

Link between the new relation and the original one is lost (no foreign key link).

The remaining attributes are often not enough to act as a key.

eg. employee-department: without employee it is just a list of departments.