Normalisation to third normal form

Functional dependencies, update anomalies, and taking a flat score sheet through first, second and third normal form.

A11.3Databases and big dataA level60 min

At GCSE you split a table because a robot's colour was repeated in every run. Normalisation is the formal version of that idea: a step-by-step method for arranging data into tables so that every fact is stored once, in the right table. The steps are called normal forms, and the target at A level is third normal form (3NF).

What goes wrong without it

Here is the competition score sheet kept as one flat table:

Three kinds of problem, called anomalies, come from storing facts more than once:

• Update anomaly. Hawks renames itself. The name is in three records; change two and forget one, and the data now disagrees with itself.
• Insertion anomaly. A new team, T3 Kites, joins but has no robots or scores yet. There is nowhere to record the team without inventing a fake score.
• Deletion anomaly. Dot's only score is removed. The facts that task L is called "line" and that Dot is in Owls vanish with it.

Functional dependency

Normalisation rests on one idea. Attribute B is functionally dependent on attribute A, written A → B, if each value of A always goes with exactly one value of B. In the score sheet:

• RobotID → RobotName, TeamID (a robot has one name and one team)
• TeamID → TeamName
• TaskCode → TaskName
• (RobotID, TaskCode) → Score (a score belongs to one robot at one task)

A program can test a dependency against the data: A → B fails as soon as one value of A appears with two values of B.

flat = [
    ("R1", "Ada", "T1", "Hawks", "W", "wall", 42),
    ("R1", "Ada", "T1", "Hawks", "S", "square", 80),
    ("R2", "Bolt", "T1", "Hawks", "W", "wall", 38),
    ("R3", "Cog", "T2", "Owls", "S", "square", 76),
    ("R3", "Cog", "T2", "Owls", "W", "wall", 45),
    ("R4", "Dot", "T2", "Owls", "L", "line", 60),
]
FIELDS = ["RobotID", "RobotName", "TeamID", "TeamName", "TaskCode", "TaskName", "Score"]

def determines(a, b):
    """True if the fields named in a functionally determine the field b in this data."""
    seen = {}
    for row in flat:
        key = tuple(row[FIELDS.index(f)] for f in a)
        value = row[FIELDS.index(b)]
        if seen.setdefault(key, value) != value:
            return False
    return True

print("TeamID -> TeamName:", determines(["TeamID"], "TeamName"))
print("RobotID -> TeamName:", determines(["RobotID"], "TeamName"))
print("RobotID -> Score:", determines(["RobotID"], "Score"))
print("RobotID, TaskCode -> Score:", determines(["RobotID", "TaskCode"], "Score"))

Run this in the simulator

As with the degree of a relationship, data can disprove a dependency but never prove one. The dependencies come from the rules of the system; the program only checks the data does not break them.

Unnormalised form

Written as one record per robot, the score sheet has a repeating group: the task, task name and score repeat for every task the robot tried. Braces mark the group:

• ScoreSheet (RobotID, RobotName, TeamID, TeamName, {TaskCode, TaskName, Score})

First normal form

A table is in first normal form (1NF) when:

1. every attribute holds a single, atomic value, so there are no repeating groups, and
2. it has a primary key, so every record is unique.

Removing the repeating group gives one record per robot per task, which is the flat table at the top. RobotID repeats, so it cannot be the key on its own; the key is composite:

• Score (RobotID, TaskCode, RobotName, TeamID, TeamName, TaskName, Score)

Second normal form

A table is in second normal form (2NF) when it is in 1NF and has no partial dependencies: no non-key attribute depends on only part of a composite key.

RobotName, TeamID and TeamName depend on RobotID alone. TaskName depends on TaskCode alone. Only Score needs the whole key. Each group of partially dependent attributes moves to a table of its own, keyed by the part it depends on, and that part stays behind as a foreign key:

• Robot (RobotID, RobotName, TeamID, TeamName)
• Task (TaskCode, TaskName)
• Score (RobotID*, TaskCode*, Score)

A table in 1NF whose primary key is a single attribute is already in 2NF, because a single attribute has no parts.

Third normal form

A table is in third normal form (3NF) when it is in 2NF and has no non-key dependencies (also called transitive dependencies): no non-key attribute depends on another non-key attribute.

In Robot, TeamName depends on TeamID, which is not the key: RobotID → TeamID → TeamName. TeamName moves out with the attribute it depends on:

• Team (TeamID, TeamName)
• Robot (RobotID, RobotName, TeamID*)
• Task (TaskCode, TaskName)
• Score (RobotID*, TaskCode*, Score)

A way to remember all three: every non-key attribute depends on the key (1NF), the whole key (2NF) and nothing but the key (3NF).

Check the anomalies again. Renaming Hawks changes one record in Team. T3 Kites can be added to Team with no robots. Deleting Dot's score leaves Dot in Robot and "line" in Task.

Why normalise, and when not to

A normalised database has no redundant data, so it takes less space and cannot become inconsistent through a missed edit. Each update touches one record, integrity rules are simpler to enforce, and the design is easier to change. The cost is more tables: a question that reads one flat table now needs joins, which take longer to run. Systems that mostly read huge amounts of data, such as reporting systems, sometimes store a deliberately denormalised copy for speed, while the normalised database stays the master copy.

Task: normalise the score sheet

The list flat is the 1NF score sheet: each item is a tuple (robot_id, robot_name, team_id, team_name, task_code, task_name, score), where score is a whole number and the rest are strings.

Build the four 3NF tables from flat (you choose the Python structure), with each fact stored once, and print them in this order, each table sorted by its key:

• teams, as team <team_id> <team_name>
• robots, as robot <robot_id> <robot_name> <team_id>
• tasks, as task <task_code> <task_name>
• scores, sorted by robot then task, as score <robot_id> <task_code> <score>

That is 15 lines, starting team T1 Hawks and ending score R4 L 60. The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# robot_id, robot_name, team_id, team_name, task_code, task_name, score
flat = [
    ("R1", "Ada", "T1", "Hawks", "W", "wall", 42),
    ("R1", "Ada", "T1", "Hawks", "S", "square", 80),
    ("R2", "Bolt", "T1", "Hawks", "W", "wall", 38),
    ("R3", "Cog", "T2", "Owls", "S", "square", 76),
    ("R3", "Cog", "T2", "Owls", "W", "wall", 45),
    ("R4", "Dot", "T2", "Owls", "L", "line", 60),
]

Challenges

1. A library loan table is Loan (BookID, MemberID, LoanDate, Title, Author, MemberName, MemberPostcode, ReturnDate). Normalise it to 3NF.
2. Add a Coach attribute that depends on the team. Where does it go in 3NF?
3. Use determines to test Score against each of the other attributes on its own. Why does none of them determine it?