NORMALIZATION: An example
-------------------------

I got a question that could be of interest for everyone in the class.
Indeed, someone asked me to give a concrete example of normalization.

A typical task that arises in databases is the following: given a database
instance, tell whether there are problems related to updating, inserting or
deleting with respect to that instance. If there are problems (usually
related to update, insertion and deletion anomalies), you may be asked
to solve them by normalization, i.e. decomposition of the schema of
the original relation instance into a set of smaller schemas.

So consider the following instance of the EMPLOYEES relation:

    eid  name  seniority bonus rating  sal     deptid deptname deptaddress
    ----------------------------------------------------------------------
    1    Joe   12        8K    2       100K    5      justice  Rideau
    2    Mills 4         3K    4       60K     5      justice  Rideau
    2    Mills 4         3K    4       60K     5      justice  Rideau
    3    jim   10        7K    2       100K    5      justice  Rideau
    4    Moll  4         3K    4       60K     4      defense  Laurier
    5    Ann   12        8K    2       100K    5      justice  Rideau
    6    Mae   4         3K    4       60K     4      defense  Laurier



By observing this instance, we see several repeating groups of values.

Functional dependencies (FDs) that we can discover from this instance are:

           1) seniority ---> bonus
           2) rating ---> sal
           3) deptid  ---> deptid deptname  deptaddress

We may use these dicovered FDs to tranform the schema of the relation
instance above into the third normal form as follows:

First step:
-----------
The FD Seniority ---> Bonus introduces a transitive dependency on the
primary key;
We deal with it by creating the following 2 tables:

(a)    (eid, name, seniority, rating, sal, deptid, deptname, deptaddress)
(b)    (seniority, bonus)

Second step:
------------
Since the relation (a) in the previous step is not yet in 3NF (because
of the FDs (2) and (3) above), we continue decomposing (a) by using the
FD Rating --> Sal:
(a1)   (eid, name, seniority, rating, deptid, deptname, deptaddress)
(a2)   (rating, sal)
(b)    (seniority, bonus)

Third step:
-----------
We now use the FD (3) above to finish up:
(a11)   (eid, name, seniority, rating, deptid)
(a12)   (deptid, deptname, deptaddress)
(a2)    (rating, sal)
(b)     (senirity, bonus)

This is our set of relation schemas that will replace the original,
unique schema that we got from the relation instance above.