Database Normalisation

Database Normalisation 1

Introduction Two levels of relation schemas The logical "user view" level The storage "base relation" level General Guidelines: Informally, each tuple in a relation should represent one entity or relationship instance. Attributes of different entities (EMPLOYEEs, DEPARTMENTs, PROJECTs) should not be mixed in the same relation Only foreign keys should be used to refer to other entities Entity and relationship attributes should be kept apart as much as possible. 2

A simplified COMPANY relational database schema

What is normalisation Divide into tables Relations among tables using primary/foreign keys Minimal redundancy Grouping correlated data in one place One place for modifications Based on functional dependencies 5

Functional dependency A B means that each value of A is always associated with one value of B. The opposite is false. A B holds if whenever two tuples have the same value for A, they must have the same value for B Read as: - B is functionally dependent on A - A is a determinant of B Partial functional dependency occur when A is composite of more than one attribute, and B is functionally dependent on one attribute of A s attributes. Full Functional Dependency is when B is functionally dependent on A, and not any proper subset of A. Transitive dependence: A B C, it is between A and C via B 6

Functional dependency Examples: {SSN, PNUMBER} -> HOURS is a full FD since neither SSN -> HOURS nor PNUMBER -> HOURS hold {SSN, PNUMBER} -> ENAME is not a full FD (it is called a partial dependency ) since SSN -> ENAME also holds 7

Process of normalisation UNF Remove repeating groups (Multi-valued) 1NF Remove partial dependencies 2NF Remove transitive dependencies 3NF 8

UNF A table (relation) that contains one or more repeating groups Vertically: some blank cells Client# Client_name 1 Smith & Sons Premise London Edinburgh Ipswich Birmingham 2 Truelove & Sons Sheffield Edinburgh Horizontally: no blank cells Client# Client_name 1 Smith & Sons 2 Truelove & Sons Edinburgh, Sheffield Premise London, Edinburgh, Ipswich, Birmingham 9

1NF Remove repeated groups To make the UNF in 1NF: Vertically: simply fill the blanks Client# 1 1 1 1 2 2 Client_name Smith & Sons Smith & Sons Smith & Sons Smith & Sons Truelove & Sons Edinburgh Truelove & Sons Sheffield Premise London Edinburgh Ipswich Birmingham 10

1NF To make the UNF in 1NF: Horizontally: separate into two tables Client# 1 2 Client_name Smith & Sons Truelove & Sons Edinburgh, Sheffield Premise London, Edinburgh, Ipswich, Birmingham Put the repeated groups in separate table with a foreign key Client# Premise 1 London 1 Edinburgh 1 Ipswich 1 Birmingham 2 Edinburgh 2 Sheffield Client# Client_name 1 Smith & Sons 2 Truelove & Sons 11

So far ... The relation has a primary key If the key is with single-attributes, the relation now in, at least, 2NF If the key is composite-key, the relation now in, at least,1NF Functional dependency is not used so far 1NF: A relation in which the intersection of each row and column contains one and only one value 12

2NF Remove partial dependencies That is; every non-key attribute depends on the whole of the primary key, and not just a part (subset) of it. In other words, fully functional dependency. 2NF A relation that is in 1NF and every non-primary-key attribute is fully functionally dependent on the primary key. Still, transitive dependency might exist. 13

Part of example on 2NF Supp# Supp_name Part# Date 1 McCabe 1 McCabe 1 McCabe 2 Smiths 2 Smiths 3 Heavers 4 Halo Bros Qty 20 P1 P2 P2 P3 P1 P1 P1 18/09/1999 18/09/1999 20/09/1999 22/09/1999 24/09/1999 26/09/1999 29/09/1999 8 1NF 10 45 18 16 24 Supp# Part# Date 1 P1 1 P2 1 P2 2 P3 2 P1 3 P1 4 P1 Qty 20 Supp# Supp_name 1 McCabe 2 Smiths 3 Heavers 4 Halo Bros 18/09/1999 18/09/1999 20/09/1999 22/09/1999 24/09/1999 26/09/1999 29/09/1999 8 10 45 18 16 24 2NF 14

Part of example on 2NF Stock# Description Warehouse# Quantity Location S1 plank S2 1 plank S3 1 plank S1 plank S2 1 plank S3 1 plank Area A A A A B B W1 W1 W2 W2 W3 W4 20 Winchester 10 Winchester 8 Winchester 26 Winchester 21 Chesterfield 5 Chesterfield 1NF Warehouse# Location W1 W2 W3 W4 Area A A B B Stock# Warehouse# Quantity S1 W1 S2 W1 S3 W2 S1 W2 S2 W3 S3 W4 Winchester Winchester Chesterfield Chesterfield 20 10 8 26 21 5 2NF Stock# Description S1 plank S2 1 plank S3 1 plank 15

3NF Remove transitive dependencies OR non-key attributes are dependent on the key only OR Remove the non-key attributes that do not depend on the key 3NF: A relation that is in 1NF and 2NF and in which no non- primary-key attribute is transitively dependent on the primary key 16

Part of example on 3NF Stock# Description Warehouse# Quantity Location S1 plank S2 1 plank S3 1 plank S1 plank S2 1 plank S3 1 plank Area A A A A B B W1 W1 W2 W2 W3 W4 20 Winchester 10 Winchester 8 Winchester 26 Winchester 21 Chesterfield 5 Chesterfield 1NF Warehouse# Location W1 W2 W3 W4 Area A A B B Stock# Warehouse# Quantity S1 W1 S2 W1 S3 W2 S1 W2 S2 W3 S3 W4 Winchester Winchester Chesterfield Chesterfield 20 10 8 26 21 5 2NF Stock# Description S1 plank S2 1 plank S3 1 plank 17

Part of example on 3NF Warehouse# Location W1 W2 W3 W4 Area A A B B Winchester Winchester Chesterfield Chesterfield 2NF Warehouse# Location W1 W2 W3 W4 Location Winchester Chesterfield Area A B Winchester Winchester Chesterfield Chesterfield 3NF 18

Examples 19

Example 1 UNF 1NF 20

Example 1 2NF 21

Example 1 2NF 3NF 22

Example 2 (assumption 1) One action may shift the relation two levels. More than one action might be taken to shift the relation one level. In the following example, we assumed that the employee can work only in one department. Therefore, the PK is the emp# and the relation is in the 2NF (no partial functional dependency). 23

Example 2 (emp# is the PK) Employee table emp# emp_name salary dept# dept_name dept_mngr Mngr_address 2NF Employee table emp# emp_name salary dept# Department table dept# dept_name dept_mngr Mngr_address Department table Employee table 3NF dept# dept_name dept_mngr emp# emp_name salary dept# Manager table dept_mngr Mngr_address 24

Example 2 (assumption 2) Assuming that the employee can work in more than one department makes the PK(emp#, dept#) and thus, the relation is in the 1NF (there is partial functional dependency).

Example 2 ((emp#, dept#) is the PK) Employee table 1NF emp# emp_name salary dept# dept_name dept_mngr Mngr_address Employee table emp# emp_name salary 2NF Original table Department table emp# dept# dept# dept_name dept_mngr Mngr_address Employee table Original table emp# emp_name salary 3NF emp# dept# Manager table Department table dept_mngr Mngr_address dept# dept_name dept_mngr 26

Example 3 car# Model Colour Engine_id Max_speed Petrol_type Width 3NF 27

Example 4 Assume that the Dept. # and Cust. # are all needed to uniquely identify the date and nature of the complaint about the department. Dept Name Soap Division Mgr Name Mary Samuel Mgr ID No. Cust Name Robert Drumtree 12/01/1998 Steven Parks 14/01/1998 Date of Complaint Dept # Location Tel Extn. Cust # Nature of Complaint UNF 11232 Cincinnati S11 7711 P10451 Poor Service Discourteous Attendant P10480 Fill the blanks to be in 1NF Date of Complaint Nature of Complaint Dept # Cust # 2NF Dept Name Mgr ID No. Dept # Location Mgr Name Tel Extn. Cust Name Cust # Date of Complaint Nature of Complaint Dept # Cust # Dept Name Mgr ID No. Dept # Location Tel Extn. 3NF Cust Name Cust # Mgr ID No. 28 Mgr Name

Anomaly 29

Redundant Information in Tuples and Anomalies If information is stored redundantly Wastes storage Causes problems with update anomalies Insertion anomalies Deletion anomalies Modification anomalies

EXAMPLE OF AN UPDATE ANOMALY Consider the relation: Storing project name and employee name in the Emp_Proj table: EMP_PROJ (Emp#, Proj#, Ename, Pname, No_hours) Update Anomaly: Changing the name of project number P1 from Billing to Customer-Accounting may cause this update to be made for all 100 employees working on project P1. Same goes for changing an employee name.

EXAMPLE OF AN INSERT ANOMALY Consider the relation: EMP_PROJ (Emp#, Proj#, Ename, Pname, No_hours) Insert Anomaly: Cannot insert a project unless an employee is assigned to it. Cannot insert an employee unless a he/she is assigned to a project.

EXAMPLE OF AN DELETE ANOMALY Consider the relation: EMP_PROJ(Emp#, Proj#, Ename, Pname, No_hours) Delete Anomaly: When a project is deleted, it will result in deleting all the employees who work on that project. Alternately, if an employee is the only employee on a project, deleting that employee would result in deleting the corresponding project.

Two relation schemas suffering from update anomalies

Relationsformed after a Natural Join

The End 36