COMP1204:

Normalisation II
Tom Blount
[Link]@[Link]
 If you didn’t do this last week, please do it now!

Activity 0: W o r l d B u i l d i n g
(Remember XML?)
• We’re going to make some data - Remember how to write XML?
• Please create and save your planet
• [Link]

• Ruler
• You need to give yourself a name and a 1-sentence
biography
• Race
• You need to create a single race, giving it a name
and a 1-sentence biography
• Location
• There can only be one planet in a given quadrant sector You can add these
• A quadrant cannot have multiple planets with the same additional appearance
name parameters
• Quadrant must be alpha, beta, gamma or delta
quadrant The custom parameter
• Sector x and y must be between 0 and 20 can take SVG for full
• Appearance personalisation if you
• What do you want your planet to look like? want to use it!
Today
• Continuing Normal Forms
• 1NF
• 2NF
• 3NF
• BCNF
• De-Normalisation
• More Space!
 Anomalies
Player Name Race ShipName ShipType ShipSpeed Planet Planet Colour Location Items
1 Kathryn Human Voyager Intrepid 9 Earth Blue Alpha Transporter,Phaser,Torpedo,Hologram
1 Kathryn Human Deadalus Intrepid 8 Qonos Red Beta Transporter,Phaser
2 Borg Queen Borg Borg Cube Cube 10 Borgland Green Delta Transporter,Phaser,Torpedo
3 James Human Enterprise Enterprise 7 Earth Blue Alpha Phaser
3 James Human Enterprise B Enterprise 8 Tetriana Prime Yellow Gamma Transporter,Phaser
4 James Human Gauntlet Sovereign 5 Earth Blue Alpha Transporter,Phaser,Torpedo

• Some examples
• Redundancy: We have a lot of redundant data
• Insert: A new player has to have a race, ship and
location when they start
• Update: To change a planet name, will need to update
lots of entries
• Delete: Deleting a player may remove all references to a
planet or race or location
The Steps to being normal
• First normal form: atomicity, find keys
• Second normal form: remove partial dependencies
• Non-key attributes must depend on every part of the primary key
• Third normal form: remove transitive dependencies
• No non-key attributes depend on another non-key attribute
• Boyce-Codd normal form: Stricter than 3NF
• Every attribute must be a fact about a key

• There’s also fourth and fifth normal form (but we don’t

really worry about those)…
 1 st Normal Form
• Relation must contain only atomic values
• Cannot be broken down any further
• Single values
• Cannot be composite, multi-valued or nested
• No objections, arrays etc.
• No repeating groups
• The same attribute across multiple columns
Player Name Race ShipName ShipType ShipSpeed Planet Planet Colour Location Items
1 Kathryn Human Voyager Intrepid 9 Earth Blue Alpha Transporter,Phaser,Torpedo,Hologram
1 Kathryn Human Deadalus Intrepid 8 Qonos Red Beta Transporter,Phaser
2 Borg Queen Borg Borg Cube Cube 10 Borgland Green Delta Transporter,Phaser,Torpedo
3 James Human Enterprise Enterprise 7 Earth Blue Alpha Phaser
3 James Human Enterprise B Enterprise 8 Tetriana Prime Yellow Gamma Transporter,Phaser
4 James Human Gauntlet Sovereign 5 Earth Blue Alpha Transporter,Phaser,Torpedo

Not Atomic
1 st Normal Form
• Relation must contain only atomic values
• Cannot be broken down any further
• Single values
• Cannot be composite, multi-valued or nested
• No objections, arrays etc.
• No repeating groups
• The same attribute across multiple columns

Repeating Group
 1 st Normal Form
• Identify any non-atomic values
Player Name Race ShipName ShipType ShipSpeed Planet Planet Colour Location Items
1 Kathryn Human Voyager Intrepid 9 Earth Blue Alpha Transporter,Phaser,Torpedo,Hologram
1 Kathryn Human Deadalus Intrepid 8 Qonos Red Beta Transporter,Phaser
2 Borg Queen Borg Borg Cube Cube 10 Borgland Green Delta Transporter,Phaser,Torpedo
3 James Human Enterprise Enterprise 7 Earth Blue Alpha Phaser
3 James Human Enterprise B Enterprise 8 Tetriana Prime Yellow Gamma Transporter,Phaser
4 James Human Gauntlet Sovereign 5 Earth Blue Alpha Transporter,Phaser,Torpedo

Decompose
Using our key: into a new
relation
(Player, Ship)
 Reminder: Finding the keys
• Go to [Link]

• Can you identify the candidate keys?

• Attributes able to be used to uniquely identify any
single row
• The system will tell you if you find one
• Can you identify good candidate keys?
• As few attributes as possible
• What would be the best primary key?
• Remember to consider the domain
 Reminder: Found the Keys

Thoughts on Attributes
We can uniquely identify planets by:
Name
- Their quadrant and sector
A planet cannot share the same name in the
- Their quadrant and name
same quadrant, but can across quadrants
Description Which is best as a primary key?
Any planet can have any description
A primary key should not change and ideally
Race and Race Bio should avoid being text
Any planet can have any race and bio The restriction on planet name to quadrant
may change later!
Sector X and Sector Y alone Quadrant and sector is less likely to change
Are repeated across quadrants A planet could rename itself!
The Minimal Set of FDs
• This does not include trivial FDs (A → A)
• Every FD must have only one attribute on the RHS
• Break up A → B,C,D into A→B, A→C, A→D
• Every FD must be minimal on it’s LHS
• It must not be possible to remove anything from the LHS
• If A → B, then A,C → B is not minimal
• There must be no redundant FDs
• A redundant FD is one which is implied by another FD
• For example, if A → B and C → B and C → A
• Then C → B is redundant because C → A → B
Activity: 1 s t N o r m a l
Form and F D s
• [Link]
• Can you find the minimal set of FDs
• This does not include trivial FDs (A → A)
• Every FD must have only one attribute on the RHS
• Break up A → B,C,D into A→B, A→C, A→D
• Every FD must be minimal on it’s LHS
• It must not be possible to remove anything from the LHS
• If A → B, then A,C → B is not minimal
• There must be no redundant FDs (implied by other FDs)
• If A → B and C → A, then C → B is redundant

• Identify the domain restrictions

• Then answer: are we in 1st Normal Form?
What did you find?
How many did you find?

Is ruler → ruler_bio valid?

 What did you not find

In our data, it is possible for a ruler to rule multiple planets in multiple quadrants

So, we cannot use planet and ruler name

What did you not find?

Why is this not valid?

Could it have been valid?
What did you not find?

There are FDs we might think are valid, but aren’t! Why is this not valid?
2 n d Normal Form
• No partial-key dependencies allowed
• Every non-key attribute (that is not part of any candidate
key) is dependent on all attributes of all candidate keys
• Identify primary key and functional dependencies in
the relation
• If partial dependencies exist on the primary key,
decompose into a new relation
• TLDR: All attributes must be dependent on all parts
of any candidate key
• “The key, the whole key”
2 n d Normal Form
Anti- Illustration
• R(a,b,c,d,e)
• (a,b) → (c,d,e) [Candidate key]
• (c,d) → (a,b,e) [Another Candidate key]
• (b) → (e) [A normal FD]
• Our key attributes are
• a,b,c and d
• Our non-key attributes are
•e
• Is e dependent on all parts of (a,b) or (c,d) ?
• No, because b → e
• Therefore, this is not in 2NF
2 n d Normal Form
• A table R is in 2NF if for every non-trivial FD A→b, either
• A is not a proper subset of any candidate key
• Or b is a key attribute (appears in some candidate key)

• If A is a proper subset (contains some but not all attributes)

of some candidate key, then:
• A → b is a partial dependency
• b is partially dependent on the candidate key

• Therefore, there are no non-key attributes that are partially

dependent on any candidate key
 Examine the dependencies

Functional Dependency A → B, if we know A, we also know B

(Player, Ship Name) → Name, Race, Ship Type, Ship Speed, Planet, Planet Colour, Location
Player → Name, Race Only partially dependent
Ship Name → Ship Type, Ship Speed, Planet, Planet Colour, Location
 Further decomposition

Copying the
determinant –
the part of the
key they are
dependent on
Decompose
into a new
relation

We get rid of the redundant data!

 But we’re not done yet!
Primary key is:
(Player, Ship Name)

(Player, Ship Name)

→ Name, Race

Player → Name, Race

Name and Race are only

partially dependent on

the key

(Player, Ship Name)

And we get Continue to apply

rid of more decomposition
redundant Copying the determinant –
data! the part of the key they are
dependent on
Back to our Planets…
• Checking if a non-key attribute is (partially) dependent
• The keys are
• quadrant, sector_x, sector_y
• quadrant, name
• So, the key attributes are • The non-key attributes are all other
• quadrant attributes
• sector_x • Let’s select a non-key attribute:
• sector_y description
• Name

So, for description, it is

dependent on all parts of
the key

Now you need to check the rest!

Activity: 2 n d Normal Form
• [Link]
• We can use the full form rather than the minimal form this time
• This means we can represent A → b,c,d

• Identify the key and non-key attributes

• Then Identify all the functional dependencies
• After you find each one, save them on the system
• Then we can ask are we in 2nd Normal Form?
• Check each key → non-key FD
• The keys are
• quadrant, sector_x, sector_y
• quadrant, name
• First, work out what the non-key attributes are
• Then check: Are all non-key attributes dependent on all parts of the key
• ignore the FDs that aren’t key → non-key
Activity: 2 n d Normal Form

• The keys are (quadrant, sector_x, sector_y) and

(quadrant, name)
• So, the non-key attributes are… everything else
• description
• ruler
• ruler_bio
• race
• race_bio
Activity: 2 n d Normal Form

For both candidate keys, we cannot remove any part of the key
Activity: 2 n d Normal Form
• Ignore the FDs that aren’t key → non-key
• We ignore ruler -→ ruler_bio

• Every non-key attribute is dependent on all attributes of the

key
• If we only know some of quadrant/sector_x/sector_y or any other
combination of them, it is not sufficient to determine the non-key
attributes

• Therefore, it is in 2NF!
Activity: 2 n d Normal Form
• What data could conceivably be in the table to
make it not 2nd Normal Form?
3 rd Normal Form
• A table is in 3NF if for every non-trivial FD A→B,
either
• A is a super key (determines all other attributes), or
• B is a key attribute

• Therefore, there are no non-key attributes that

are transitively dependent on any candidate key

• TLDR: All attributes are determined only by the keys

• “The key, the whole key, and nothing but the key”
3 rd Normal Form Illustration
• R(a,b,c,d,e)
• (a,b) → (c,d,e) [Candidate Key]
• (d) → (e)
• It is in 2NF
• Key attributes: a,b
• Non-Key Attributes: c,d,e
• c, d and e are dependent on all the candidate key (a,b)
• It is not 3NF
• e is not a key attribute
• e is determined by d, which is not a key
Reminder: Trivial
dependency
• A → B is a trivial functional dependency if B is a subset of A

• For example,
• Player → Player
• {Player, Ship Name} → Player
• {Player, Ship Name} → Ship Name
Transitive Dependence
• If A → B → C (but it is not the case that B → A)
• Then A → C
• Transitive dependency

• If K → Ai (2nd Normal Form), there must be no set of

attributes X such that K → X → Ai
Transitive Dependence

Ship Name → Ship Type, Ship Speed, Planet, Planet Colour, Location
Planet → Planet Colour, Location

Ship Name → Planet → Planet Colour, Location

Planet Colour and Location have transitive dependence on the Ship Name via Planet
Further Decomposition

Decompose
into new
relations

Copying the
determinant – the
part of the key they
are dependent on

We remove some more redundant data!

Activity: 3 rd Normal Form

• We are not in 3rd Normal Form

• Remember: There can be no transitive dependencies,
where A → B → C (unless B → A)
• But why are we not in 3rd Normal Form?
• So now, how can we decompose into 3rd Normal
Form?
• Use [Link]
to help you
Getting into 3NF
• Why was this not 3NF?

• Because if we knew (name,quadrant) or

(quadrant,sector_x,sector_y) we knew ruler
• If we knew ruler, we knew ruler_bio
• (name,quadrant) → ruler → ruler_bio
• (quadrant,sector_x,sector_y) → ruler_bio
 Decomposing into 3NF

We decomposer Ruler → Ruler_Bio into its own Relation, leaving us with a list of
planets and a list of rulers
Next up: Boyce-Codd Normal
Form
• A slightly stronger version of 3NF (Sometimes called 3.5NF)

• Every relation in BCNF is also 3NF

• But not vice versa
• One further restriction on 3NF…
• Every determinant is a candidate key (can uniquely identify any
row)
• Formally,
• If A1,…,An → B is a non-trivial dependency in R, then {A1,…,An} is a
superkey for R

• “The key, the whole key, and nothing but the key, so help me Codd”
Let’s extend our example
• Each ship has a defence slot, offense slot and
enhancement slot for enhancement items which
can be equipped

• We want to keep track of what items are in what

slots on each ship

• So, we have a relation of Ship, Slot and Item

• For example: Deadalus has a shield in it’s defence slot
and a phaser in its offence slot
It’s 3 N F …
• Our new table is 3NF
• (Ship, Slot) → Item
• (Ship, Item) → Slot
• Item → Slot
• There are no non-key
attributes with a partial
dependencies (2NF)
• Item → Slot; but Slot is a key
attribute!
• Non-key attributes are only
dependent on candidate keys
(3NF)
• (Everything is part of a candidate
key)
… b u t it’s not BC N F Item → Slot
The determinant is Item
Item is not a candidate key!
• (Ship, Slot) → Item
• (Ship, Item) → Slot
• Item → Slot

• BCNF Restriction: Every

determinant (an attribute to
determine others) is a
candidate key
• (Ship,Slot) and (Ship,Item) are
both candidate keys (can
uniquely identify a row)
The result: Redundant data!
• Item is not a candidate key (it
alone can’t uniquely identify a If we know the item, we know slot
row) it goes into
 BCNF Decomposition Now we only have
(Ship, Item)

Our one and only key

(and the trivial FDs)

And here we have only

(Item) → Slot

And we lose more

redundant data!

What made sense as a logical concept introduced redundancy and didn’t make sense from a
database perspective
Activity 4: BCNF
• [Link]

• Are we in BCNF Normal Form?

 In the planets table

Every determinant is a
Activity 4: BCNF candidate key

(quadrant,name) → …
(quadrant,sector_x,sector
• Yes, we are in BC Normal Form _y) → …
There are no other
determinants, and both
we have here are
candidate keys

In the rulers table

The only determinant

we have is
Ruler →
ruler_bio And
ruler is a
candidate key

Therefore, both are

BCNF
W h y is it better?
• No redundancy
• Less storage space required
• Efficiency
• Less data to search through → faster queries
• No duplication
• Better integrity
• Only have to modify something in 1 place
• Less chance of mistakes
• Changes can cascade across relations
• Example: Remove a person and anything related to them
What are the
consequences?
• More tables
• More complexity
• More relationships
• Queries become more complex

• But it’s worth it!

• How many times have you been annoyed by a
spreadsheet?
Denormalisation?
• Driven by the need to improve query speed
• At the expense of less normalisation
• More complex operations required to updates, deletions
and insertions to avoid integrity issues

Including the Customer Name in

the order, as well as in the
customer table
More Space!
•  
•  
•  
•  
•  
•  
•  
•  
•  
•  
•  
S u mmary
• Normalisation
• Normal forms
• Issues with normalising