MONASH
INFORMATION TECHNOLOGY
Normalisation
Data Normalisation
▪ Relations should be normalised in order to avoid anomalies which may occur when inserting, updating and deleting data.
▪ Normalisation is a systematic series of steps for progressively refining the data model.
▪ A formal approach to analysing relations based on their primary key (or candidate keys) and functional dependencies.
▪ Used:
▪ as a design technique “bottom up design”, and
▪ as a way of validating structures produced via “top
down design” (ER model converted to a logical model – see next week)
2
Sample Data
* against EMP_NAME indicates the project leader
3
Problems with sample data
▪ JOB_CLASS invites entry errors eg. Elec. Eng. vs Elect. Engineer vs E.E. ▪ Table has redundant data
– Details of a charge per hour are repeated for every occurrence of job class
– Every time an employee is assigned to a project emp name repeated ▪ Relations that contain redundant information may potentially suffer from
several update anomalies
– Types of update anomalies include:
• Insert Anomaly
–Insert a new employee only if they are assigned to a project
• Delete Anomaly
–Delete the only employee assigned to a project? –Delete the only employee of a particular job class?
• Modification (or update) Anomaly
–Update a job class hourly rate – need to update multiple rows
4
The Normalisation Process Goals
▪ Creating valid relations, i.e. each relation meets the properties of the relational model. In particular:
– Entity integrity
– Referential integrity
– No many-to-many relationship
– Each cell contains a single value (is atomic).
▪ In practical terms when implemented in an RDBMS:
– Each table represents a single subject
– No data item will be unnecessarily stored in more than one table.
– The relationship between tables can be established (pair of PK and FK is identified).
– Each table is void of insert, update and delete anomalies.
5
Representing a form as a relation
▪ This process follows a standard approach:
– arrive at a name for the form which indicates what it represents (its
subject)
– determine if any attribute is multivalued (repeating) for a given entity
instance of the forms subject
• if an attribute (or set of attributes) appears multiple times then the group of related attributes need to be shown enclosed in brackets to indicate there are multiple sets of these values for each instance
▪ Looking at our SAMPLE DATA
– Name: EMPLOYEE_PROJECT_ASSIGNMENT • simplify name to ASSIGNMENT for lecture
– ASSIGNMENT (proj_num, emp_num, emp_name, job_class, chg_hour, assign_hours)
– i.e. the form consists of repeating rows (instances) of assignment data
6
Representing a form as a relation
CUSTOMER ORDER
Order Number:
Customer Number: Customer Name: Customer Address:
61384
1273
Computer Training Centre 123 Excellent St
Monash, Vic, 3000
Order Date:
12/3/2020
PRODUCT NUMBER
DESCRIPTION
QTY ORDERED
LINE PRICE
M128
Bookcase
4
800
B381
TV Cabinet
2
600
R210
Round Table
3
1500
ORDER ( orderno, orderdate, custnumb, custname, custaddress (prodno, proddesc, qtyordered, lineprice))
7
▪
Functional Dependency Revisited
An attribute B is FUNCTIONALLY DEPENDENT on another attribute A, if a value of A determines a single value of B at any one time.
– A➔B
– PRODNO ➔ PRODDESC
– CUSTNUMB ➔ CUSTNAME
– ORDERNO ➔ ORDERDATE
• ORDERNO – independent variable, also known as the DETERMINANT
• ORDERDATE – dependent variable ▪ TOTALDEPENDENCY
– attribute A determines B AND attribute B determines A
• EMPLOYEE-NUMBER ➔ TAX-FILE-NUMBER
• TAX-FILE-NUMBER ➔ EMPLOYEE-NUMBER
8
Functional Dependency
▪ For a composite PRIMARY KEY, it is possible to have FULL or PARTIAL dependency.
▪ FULLDEPENDENCY
– occurs when an attribute is always dependent on all attributes in the
composite PK
– ORDERNO, PRODNO ➔ QTYORDERED
▪ Lack of full dependency for multiple attribute key = PARTIAL DEPENDENCY
– ORDERNO, PRODNO
➔ PRODDESC, QTYORDERED
– here although qtyordered is fully dependent on orderno and prodno, only
prodno is required to determine proddesc
– proddesc is said to be partially dependent on orderno and prodno
9
Functional Dependency
▪ TRANSITIVE DEPENDENCY
– occurs when Y depends on X, and Z depends on Y – thus Z also
depends on X ie. X ➔ Y ➔ Z
– and Y is not a candidate key (or part of a candidate key) – ORDERNO ➔ CUSTNUMB ➔ CUSTNAME
▪ Dependencies are depicted with the help of a Dependency Diagram.
▪ Normalisation converts a relation into relations of progressively smaller number of attributes and tuples until an optimum level of decomposition is reached – little or no data redundancy exists.
▪ The output from normalisation is a set of relations that meet all conditions set in the relational model principles.
10
Unormalised Form (UNF)
▪ The UNF representation of a relation is the representation which you have mapped from your inspection of the form
– it is a single named representation (name is not pluralised)
– no PK etc have as yet been identified
▪ ASSIGNMENT (proj_num, emp_num, emp_name, job_class, chg_hour, assign_hours)
▪ ORDER (orderno, orderdate, custnumb, custname, custaddress (prodno, proddesc, qtyordered,
lineprice))
Can ASSIGNMENT and/or ORDER be called a relation? If not, why not?
11
First Normal Form
▪FIRST NORMAL FORM (part of formal definition of a relation)
– A RELATION IS IN FIRST NORMAL FORM (1NF) IF:
• a unique primary key has been identified for each tuple/row.
• it is a valid relation
– Entity integrity (no part of PK is null)
– Single value for each cell ie. no repeating group (multivalued attribute).
• all attributes are functionally dependent on all or part of the primary key
12
UNF to 1NF
▪ Move from UNF to 1NF by:
identify a unique identifier for the repeating
group.
remove any repeating group along with the PK of the main relation.
The PK of the new relation resulting from the removal of repeating group will normally have a composite PK made up of the PK of the main relation and the unique identifier chosen in 1. above, but this must be checked.
13
Q1. Given the CUSTOMER ORDER UNF as:
ORDER ( orderno, orderdate, custnumb, custname, custaddress (prodno, proddesc, qtyordered, lineprice)).
What would be the 1NF of this UNF relation?
A. Two relations
– ORDER (orderno, orderdate, custnumb, custname, custaddress)
– ORDER_PROD (orderno, prodno, proddesc, qtyordered, lineprice )
B. Three relations
– ORDER (orderno, orderdate, custnumb)
– CUSTOMER (custnumb, custname, custaddress)
– ORDER_PROD (orderno, prodno, proddesc, qtyordered, lineprice )
C. CUST_ORDER (orderno, orderdate, custnumb, custname, custaddress, prodno, proddesc, qtyordered, lineprice)
D. PROD_ORDER (orderno, prodno, proddesc, qtyordered, lineprice, orderdate, custnumb, custname, custaddress)
14
Q2. Given the ASSIGNMENT UNF as:
A. Two relations
– PROJECT (proj_num, proj_name) and
– ASSIGNMENT (proj_num, emp_num, emp_name,
job_class, chg_hour, assign_hours)
B. ASSIGNMENT (proj_num, emp_num, proj_name, emp_name, job_class, chg_hour, assign_hours)
C. PROJECT (proj_num, proj_name)
D. ASSIGNMENT (proj_num, emp_num, job_class, proj_name, emp_name, chg_hour, assign_hours)
15
1NF to 2NF
▪ A RELATION IS IN 2NF IF –
– all non key attributes are functionally dependent on
the primary key (simple definition)
• used by the textbook in examples
– all non key attributes are functionally dependent on any candidate key (general definition)
• see textbook section 6-3, same as simple if only one candidate key
• Requirement for our unit
16
Q3. Which of the following attributes has a partial dependency in the relation ASSIGNMENT?:
A. proj_name
B. emp_name
C. job_class
D. chg_hour
E. assign_hours
F. More than one option is correct.
17
Q4. Which of the following attributes has a transitive dependency in the relation ASSIGNMENT?:
A. proj_name
B. emp_name
C. job_class
D. chg_hour
E. assign_hours
F. More than one option is correct.
18
Dependency Diagram ( Drawn based on 1NF)
Note show only partial dependencies at 1NF
19
1NF to 2NF
▪ ASSIGNMENT(proj_num, emp_num, proj_name, emp_name, job_class, chg_hour, assign_hours)
▪ Move from 1NF to 2NF by removing partial dependencies
– 2NF: ASSIGNMENT (proj_num, emp_num, assign_hours) – 2NF: PROJECT (proj_num, proj_name)
– 2NF: EMPLOYEE (emp_num, emp_name, job_class, chg_hour)
20
Note show only transitive dependencies at 2NF
2NF Conversion Results
21
Q5. Where is the location of the FK for the relations below?
EMPLOYEE (emp_num, emp_name, job_class, chg_hour) ASSIGNMENT (proj_num, emp_num, assign_hours) PROJECT (proj_num, proj_name)
A. EMPLOYEE B. ASSIGNMENT
C. PROJECT
D. More than one answer is correct
22
Q6. What type of relationship is the relationship between: ASSIGNMENT and EMPLOYEE
and
ASSIGNMENT and PROJECT
EMPLOYEE (emp_num, emp_name, job_class, chg_hour) ASSIGNMENT (proj_num, emp_num, assign_hours)
PROJECT (proj_num, proj_name)
A. non-identifying, non-identifying
B. identifying, identifying
C. identifying, non-identifying
D. non-identifying, identifying
23
2NF to 3NF
▪ A RELATION IS IN 3NF IF –
– all transitive dependencies have been removed – check for non key attribute dependent on another non key attribute
▪ Move from 2NF to 3NF by removing transitive dependencies
24
2NF to 3NF
▪ PROJECT and ASSIGN already in 3NF
– 3NF PROJECT (proj_num, proj_name)
– 3NF ASSIGNMENT (proj_num, emp_num, assign_hours)
▪ 2NF EMPLOYEE (emp_num, emp_name, job_class, chg_hour)
– It has transitive dependency, job_class-> chg_hour.
• Remove the attributes with transitive dependency into a new relation.
• The determinant will be an attribute in both the original and new relations (it will become the PK and FK relationship)
• Assign the determinant to be the PK of the new relation. 25
2NF to 3NF
▪ After the removal of transitive dependency in EMPLOYEE, we have:
– 3NF EMPLOYEE (emp_num, emp_name, job_class)
– 3NF JOB (job_class, chg_hour)
26
Relations in 3NF
Note show only full dependencies at 3NF
27
Q7. Where is the location of the FK for the relations below?
EMPLOYEE (emp_num, emp_name, job_class) JOB (job_class, chg_hour)
A. EMPLOYEE
B. JOB
C. Both EMPLOYEE and JOB
28
Q8. What type of relationship is the relationship between the JOB and EMPLOYEE?
EMPLOYEE (emp_num, emp_name, job_class) JOB (job_class, chg_hour)
A. non-identifying
B. identifying
C. Cannot be determined
29
Entire Process UNF to 3NF
▪ UNF –
▪ 1NF –
▪ 2NF – – –
▪ 3NF – – – –
–
–
–
ASSIGNMENT (proj_num,emp_num ,proj_name, emp_name, job_class, chg_hour, assign_hours)
remove repeating group
ASSIGNMENT (proj_num,emp_num ,proj_name, emp_name, job_class, chg_hour, assign_hours) Note: 1NF is only identify PK, no repeating group.
remove partial dependencies
ASSIGNMENT (proj_num, emp_num, assign_hours) PROJECT (proj_num, proj_name)
EMPLOYEE (emp_num, emp_name, job_class, chg_hour) remove transitive dependencies
ASSIGNMENT (proj_num, emp_num, assign_hours) PROJECT (proj_num, proj_name)
EMPLOYEE (emp_num, emp_name, job_class)
JOB (job_class, chg_hour)
▪ NOTE: dependencies must be shown at each normal form, not shown here
30
Customer Order Form
CUSTOMER ORDER
Order Number:
Customer Number: Customer Name: Customer Address:
61384
1273
Computer Training Centre 123 Excellent St
Monash, Vic, 3000
Order Date:
12/3/2020
PRODUCT NUMBER
DESCRIPTION
QTY ORDERED
LINE PRICE
M128
Bookcase
4
800
B381
TV Cabinet
2
600
R210
Round Table
3
1500
ORDER ( orderno, orderdate, custnumb, custname, custaddress (prodno, proddesc, qtyordered, lineprice))
31
Customer Order Normalisation
UNF
ORDER ( orderno, orderdate, custnumb, custname, custaddress (prodno,
proddesc, qtyordered, lineprice))
1NF
ORDER ( orderno, orderdate, custnumb, custname, custaddress) ORDER_PRODUCT ( orderno, prodno, proddesc, qtyordered, lineprice) Partial dependencies:
prodno -> proddesc
2NF
ORDER ( orderno, orderdate, custnumb, custname, custaddress) ORDER_PRODUCT ( orderno, prodno, qtyordered, lineprice) PRODUCT (prodno, proddesc)
Transitive dependencies:
custnumb -> custname, custaddress
32
Customer Order Normalisation continued
2NF
ORDER ( orderno, orderdate, custnumb, custname, custaddress) ORDER_PRODUCT ( orderno, prodno, qtyordered, lineprice) PRODUCT (prodno, proddesc)
Transitive dependencies:
custnumb -> custname, custaddress
3NF
ORDER ( orderno, orderdate, custnumb) ORDER_PRODUCT ( orderno, prodno, qtyordered, lineprice) PRODUCT (prodno, proddesc)
CUSTOMER (custnumb, custname, custaddress)
Full dependencies:
orderno -> orderdate, custnumb orderno, prodno -> qtyordered, lineprice prodno -> proddesc
custnumb -> custname, custaddress
33
Assume a phone number may be shared between employees
34
Monash Software EMPLOYEE form
▪ List all attributes found on the form, maintain consistency with previously used attribute names if exist:
– emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode, phone_type, phone_no, degree_name, degree_institution, degree_year, fmemb_no, fmemb_name, fmemb_dob, skill_name
▪ Determine if any attribute is multivalued (repeating) for a given entity instance
– phone_type, phone_no, degree_name, degree_institution, degree_year, fmemb_no, fmemb_name, fmemb_dob, skill_name
35
Monash Software EMPLOYEE form continued
▪ Group multivalued attributes that are related and place in brackets
EMPLOYEE (emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode, (phone_type, phone_no), (degree_name, degree_institution, degree_year), (fmemb_no, fmemb_name, fmemb_dob), (skill_name))
▪ This is our beginning UNF, to proceed to 1NF:
– PK of main relation EMPLOYEE is emp_no
– Four repeating groups to remove
• Remove repeating group (multi valued attribute/s) along with PK of main relation (here emp_no)
– assume a phone number may be shared between employees
36
Monash Software EMPLOYEE form continued
UNF
EMPLOYEE (emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode, (phone_type, phone_no), (degree_name, degree_institution, degree_year), (fmemb_no, fmemb_name, fmemb_dob), (skill_name))
1NF
EMPLOYEE (emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode)
EMP_PHONE (emp_no, phone_no, phone_type)
EMP_QUALIFICATION (emp_no, degree_name, degree_institution, degree_year)
FAMILY_MEMBER (emp_no, fmemb_no, fmemb_name, fmemb_dob)
EMPLOYEE_SKILL (emp_no, skill_name) Partial dependencies:
None present
Note we are making an assumption that a phone number may be shared between employees
37
Monash Software EMPLOYEE form continued
2NF
EMPLOYEE (emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode)
EMP_PHONE (emp_no, phone_no, phone_type)
EMP_QUALIFICATION (emp_no, degree_name, degree_institution, degree_year)
FAMILY_MEMBER (emp_no, fmemb_no, fmemb_name, fmemb_dob) EMPLOYEE_SKILL (emp_no, skill_name)
Transitive dependencies: None present
38
Monash Software EMPLOYEE form continued
3NF
EMPLOYEE (emp_no, emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode)
EMP_PHONE (emp_no, phone_no, phone_type)
EMP_QUALIFICATION (emp_no, degree_name, degree_institution, degree_year)
FAMILY_MEMBER (emp_no, fmemb_no, fmemb_name, fmemb_dob) EMPLOYEE_SKILL (emp_no, skill_name)
Full dependencies:
emp_no -> emp_fname, emp_lname, emp_dob, emp_street_no, emp_street, emp_town, emp_pcode
emp_no, phone_no -> phone_type
emp_no, degree_name, degree_institution -> degree_year emp_no, fmemb_no -> fmemb_name, fmemb_dob
39
Summary
▪ Things to remember
– Represent form as presented, no interpretation, to yield
starting point (UNF)
– Functional dependency
– Process of removing attributes in relations based on the concept of 1NF, 2NF and 3NF.
• UNF to 1NF define PK & remove repeating group. • 1NF to 2NF remove partial dependency.
• 2NF to 3NF remove transitive dependency.
40