Disclaimer : These are notes on a KCL Database course I'm taking (module ID below). The example database is taken from the lectures. This page was created only for the purpose of revising in preparation for the winter exams.
KCL Module Ref.: 7CCSMDDW.

We will look at database normalisation and how to fix bad table designs. We will go through 1NF up to 3NF (including Boyce-Codd normal form).

The following is the relational table we will be working on.

Note: Assume that a project (at least one) is always assigned to an employee.

Schema (MySQL v5.7)

CREATE TABLE IF NOT EXISTS EMPLOYEE(
empid INT NOT NULL,
name VARCHAR(255) NOT NULL,
job VARCHAR(150) NOT NULL,
salary INT NOT NULL,
project VARCHAR(255) NOT NULL,
manager VARCHAR(255) NOT NULL,
prlength INT NOT NULL,
prcost INT NOT NULL
);

INSERT INTO EMPLOYEE VALUES(1, "Jones", "engineer", 35000, "Gherkin", "Davis", 5, 500);
INSERT INTO EMPLOYEE VALUES(2, "Wilson", "sales", 28000, "Tunnel", "Fulton", 6, 250);
INSERT INTO EMPLOYEE VALUES(1, "Jones", "engineer", 35000, "Tunnel", "Fulton", 6, 250);
INSERT INTO EMPLOYEE VALUES(3, "Peters", "tech", 24000, "Gherkin", "Davis", 5, 500);
INSERT INTO EMPLOYEE VALUES(3, "Peters", "tech", 24000, "Dome", "Mandelson", 2, 2000);
INSERT INTO EMPLOYEE VALUES(4, "Price", "runner", 17500, "Dome", "Mandelson", 2, 2000);
INSERT INTO EMPLOYEE VALUES(5, "Dollis", "designer", 45000, "Airport", "Craig", 5, 500);

Query #1

SELECT * 
FROM EMPLOYEE
ORDER BY empid, project;

Query #2

UPDATE EMPLOYEE
SET project = "Dome"
WHERE empid = 1;

Query #3

SELECT * 
FROM EMPLOYEE
ORDER BY empid, project;

We can observe that a (theoretical) update anomaly occurred. We also take notice of the redundancy of some columns in this table. Each time a project is assigned to an employee, their name, job and salary is reinserted into the table again.

The table above is already in first normal form (1NF). The requirement to be in 1NF is that each row of a non-key column must be atomic. That is, we only allow one entry per row.

We check if the table above is in second normal form (2NF). That is, there can be no non-prime attributes (attributes that are not part of any of the candidate keys) that only partially depend on the candidate key. In otherwords, all the non-prime columns must depend fully on the candidate key.

We start by finding the candidate keys of our relational table. Remember that the candidate key must be unique and define a single row.

Some of the functional dependencies that are present in our table are:

• empid ⟶ {name, job}
• project ⟶ {manager, prlength, prcost}
• prlength ⟶ prcost
• job ⟶ salary

We use these functional dependencies to find the closure of each set of attributes. The minimal superkey, that is, the set with the least number of attributes on the LHS, is going to be our candidate key:

• {empid}⁺ = {empid, name, job}
• {name}⁺ = {name}
• {job}⁺ = {job, salary}
• {salary}⁺ = {salary}
• {project}⁺ = {project, manager, prlength, prcost}
• {manager}⁺ = {manager}
• {prlength}⁺ = {prcost}
• {prcost}⁺ = {prcost}
• {empid, job}⁺ = {empid, name, job, salary}
• {empid, project}⁺ = {empid, name, project, manager, prlength, prcost}
• {empid, job, project}⁺ = {empid, name, job, salary, project, manager, prlength, prcost}

I skipped a few combinations of attributes, but we can see that {empid, job, project} is a candidate key. Their union defines all the attributes in the table. However, this candidate key does not make our table 2NF since we can see that there are partial dependencies.

To turn this table to 2NF, we need to decompose it. We will do this when we convert it to BCNF.

We want to check that it's in 3NF. To be in the 3NF we have two requirements:

1. The table must be in 2NF.
2. There cannot be any dependencies between non-prime and any other attributes other than the entire candidate key.

Additionally, for a table to be in BCNF we require:

1. The table must be in 3NF.
2. The determinant of every functional dependency is a candidate key.

The table is clearly not in 3NF as it is not even in 2NF. What we will do is a process called "decomposition". We will be separating this table into different tables in order to make them all BCNF.

To start the decomposition process, we select a functional dependency and create a table using the determinant as the key and the rest as non-prime attributes.

We start with {job} ⟶ {salary}. We create a new relation

E₁(:key: job, salary).

We then remove all the non-key attributes of E₁ from the employee table and create a new relation

E₂(empid, name, job, project, manager, prlength, prcost).

To make sure that this decomposition did not make us lose any information, we need to check that the union of the attributes of both tables make up the original table, and the natural join also returns the original table.

In fact,

{salary} ∪ {empid, name, job, project, manager, prlength, prcost} = Employee

and

E₁ ⋈ E₂ = Employee

(Reminder: The natural join merges two tables by the common columns and common rows)

We check if any of the new tables are in BCNF. We know that E₁ is in 1NF since the rows are atomic, it's in 2NF since there are no partial dependencies. It's also in 3NF since the salary depends fully on the key and there is no transitive dependency. It's also in BCNF because there is only one possible FD and the dependant is the candidate key. However, we notice that E₂ is not even in 2NF. We still have partial dependencies.

We repeat the same procedure and create two new tables E₃ and E₄. We pick empid ⟶ {name, job}. Thus,

E₃(:key: empid, job, name),
E₄(empid, project, manager, prlength, prcost).

So now we have three tables: E₁, E₃ and E₄. We see that E₃ is in 1NF and 2NF since every non-key attribute depends fully on empid. It's also in 3NF since every non-key attribute depends fully on the candidate key and there is no FD between name and job. It's also in BCNF as the dependant is always the candidate key. E₄ is still not in 2NF. We repeat the process again.

We now consider the FD {project} ⟶ {manager, prlength, prcost}:

E₅(:key: project, manager, prlength, prcost),
E₆(empid, project).

E₇(:key: prlength, prcost),
E₈(:key: project, manager, prlength).

So, to recap we now have the following decomposed tables: E₁, E₃, E₆, E₇ and E₈. We can see that E₈ is finally in 3NF since there are no partial dependencies and every non-key attributes depend fully on the candidate key. It's also in BCNF since the dependant of every FD is the candidate key. E₇ is obviously also in BCNF.

Now we check if we lost any information while decomposing the tables:

1. The union must equal the original table

   {job, salary} ∪ {empid, job, name} ∪ {empid, project} ∪ {prlength, prcost} ∪ {project, manager, prlength} = {empid, name, job, salary, project, manager, prlength, prcost}.

2. The natural join must equal the original table (I won't be showing this but it is true).

Therefore, we have successfully decomposed our original table, which was not even in 2NF, to five new tables which are all in BCNF.