Week 3: Functional Dependencies & Normalisation
Functional Dependencies & Normalisation
Functional Dependencies
- A functional dependency (FD) is a constraint between two sets of attributes in a relation from a database. FD is when one attribute (or set of attributes) precisely determines the value of another attribute in a database.
-
Advantages -
- Prevents data redundancy (data stored multiple times).
- Maintains quality of data (e.g. easy to update/delete data).
- Helps determine relations and constraints.
Rules of Functional Dependencies
- Armstrong's
Axioms
-
Reflexive: If Y is a subset of X, then X→Y.
- Example: {seat_no, name} → name.
-
Augmentation: If X → Y is a valid dependency, then XZ → YZ is also valid.
- Example: {seat_no, name} → movie_name, then {seat_no,name, movie_theatre} → {movie_name, movie_theatre}.
-
Transitivity: If X → Y and Y → Z are both valid dependencies, then X→Z is
also valid.
- Example: seat_no → movie_name & movie_name → movie__theatre, then seat_no → movie_theatre
-
Reflexive: If Y is a subset of X, then X→Y.
- Secondary Rules
- Union: If X → Y and X → Z, then X → YZ.
- Decomposition: If X → YZ, then X → Y and X → Z
- Pseudo-Transitivity: If X → Y and EY → Z, then XE → Z.
Types of Functional Dependencies
- Trivial
FD: If X → Y and Y is a subset of X.
- Example: {seat_no, name} → name.
- Non-Trivial
FD: If X → Y and Y is not a subset of X (opposite of Trivial FD).
- Example: {seat_no, name} → movie_theatre.
- Multivalued
FD: If X → {Y,Z} and Y and Z are not dependent on each other.
- Example: seat_no → {name, age}, name → age and age → name not holding.
- Transitive
FD: If X → Y and Y → Z, then X → Z (as per the transitivity rule/axiom).
- Example: seat_no → movie_name and movie_name → movie_theatre, then seat_no → movie_theatre.
Functional Dependencies Closure – F+ & Attribute Closure X+
- F+ is all the FDs that can be derived, given a set of FDs F. By determining the closure of F, we can design normalised databases.
- X+ of an attribute set X is a set of these attributes that can be functionally determined from X. By determining the closure of X we can determine the keys for the relation.
Normalisation
- Normalisation is the process of organising the data in the database, with a focus on minimising redundancy in relations or set of relations.
- 6 Normal Forms
(NFs) available. We will focus on the first 3 (1NF, 2NF, 3NF) - most commonly used as they
address the 3 data modification anomalies:
- Insertion Anomaly: Omission of data during insertion due to absence of other data.
- Deletion Anomaly: Unintended loss of data due to the deletion of other data.
- Update Anomaly: Data inconsistency that results from redundant data and partial updates.
- Advantages of
Normalisation:
- Prevents data redundancy.
- Offers data consistency
- Offers flexibility in design and data management.
- Enforces relational (referential) integrity.
Normal Forms
- First Normal
Form (1NF)
- It contains no repeating groups
- The values in each column are atomic (cannot be divided so not multi-valued or composite attributes)
- Second Normal
Form (2NF)
- It is in 1NF
- There are no partial dependencies (every non-key attribute is functionally dependent on the PK)
- Third Normal
Form (3NF)
- It is in 2NF
- There are no transitive dependencies for non-key attributes
Practice Question
In the table below, select the true answer about anomalies
| Order_ID | Date | Time | Status | Customer | Item_ID |
|---|---|---|---|---|---|
| 2 | 2023/04/20 | 13:12 | Paid | 1 | 28, 23, 17 |
| 16 | 2023/07/09 | 16:47 | Pending | 12 | 14, 9 |
In the table below, select the true answer about anomalies
| Region_ID | Cuisine_ID | Name |
|---|---|---|
| 1 | 201 | American |
| 2 | 202 | Angolan |
| 3 | 203 | Arab |
| 4 | 204 | Argentine |
Laboratory 03 - Functional Dependencies & Normalisation
The goal of this activity is for you to practice the technique of using functional
dependencies to normalize a relational database schema and for you to take an
information source and normalise from UNF to 3NF.
We will start with the universal schema, i.e., a single relation database schema, where all the attributes of interest belong to the single relation in the database schema. However, we could start from a partially normalized schema as well. In the next task given the information source you are to undergo the normalisation process to create new relations that progressively become strong to help avoid insert, update and delete anomalies.
This technique is often applied in real-world software development by a database designer when a relational database schema already exists but needs expansion, or else needs to be revised if it has been otherwise modified.
The outcome of this step is a normalized relational database schema.
We will start with the universal schema, i.e., a single relation database schema, where all the attributes of interest belong to the single relation in the database schema. However, we could start from a partially normalized schema as well. In the next task given the information source you are to undergo the normalisation process to create new relations that progressively become strong to help avoid insert, update and delete anomalies.
This technique is often applied in real-world software development by a database designer when a relational database schema already exists but needs expansion, or else needs to be revised if it has been otherwise modified.
The outcome of this step is a normalized relational database schema.
Tasks 01:
Consider the universal relation:
$$R = \{A,B,C,D,E,F,G,H,I,J\}$$
and the set of functional dependencies:
$$R = \{AB \rightarrow C,A \rightarrow DE, B \rightarrow F, F \rightarrow GH, D \rightarrow
IJ \}$$
- What is the key for \(R\)? Explain your answer.
- Decompose \(R\) into 2NF, then 3NF relations. Explain your decisions.
Tasks 02:
Consider the following information source:
- Show the information source as a table with the associated columns and data in UNF. Include a short description of the process.
- Convert from UNF to 1NF and show the resulting relations. Include a short description of the process
- Convert from 1NF to 2NF and show the resulting relations. Include a short description of the process
- Convert from 2NF to 3NF and show the resulting relations. Include a short description of the process
End Of Week Quiz
Note: A score of 70% or higher would mean you
have successfully completed the week 3 workshop