School of Science/ Computer Science and Information Technology
ISYS3412 Practical Database Concepts Week 10: Lecture – Normalisation Exercises (with answers)
Semester 1 2020
1 Objective
The objective of this example to give a hands-on experience on using normalisation in both top- down and bottom-up approach.
1.1 ProblemDescription.
This example is based on the Question 5.11 in Fundamentals of Database Systems (5th Edition), by Elmasri and Navathe.
Your task is to build a relational database model (COMPANY) to store required data in a small company.
The COMPANY database keeps track of a company’s employees, departments, and projects. Suppose that after the requirements collection and analysis phase, the database designers provide the following description of the part of the company to be represented in the database.
The company is organised into departments. Each department has a unique name, a unique number, and a particular employee who manages the department. We keep track of the start date when that employee began managing the department. A department may have several locations.
A department controls a number of projects, each of which has a unique name, a unique number, and a single location.
We store each employee’s name, social security number1, address, position, salary, sex, and birth date. An employee is assigned to one department, but may work on projects, which are not necessarily controlled by the same department. We keep track of the number of hours per week that an employee each project. We also keep track of the direct supervisor of each employee.
All employees in a specific position receive the same salary.
We want to keep track of the dependents of each employee for insurance purposes. We keep each dependent’s first name, sex, birth date, and relationship to the employee.
1.2 NormalisationProcess
In the lecture 9, we discussed both top-down and bottom-up approaches we can utilise the normalisation process to build a well-designed relational database schema.
In the top-down approach, we use the normalisation mainly as a validation tool. You may still be required to do some decomposition of relations, but, chances are that the relations resulting from the ERàRelations mapping process are in higher normal forms anyway.
1 This example is based on US system, assume it is similar to Australian Tax File Number.
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara School/Department/Area Save Date: 12/05/2020 Page 1 of 11
In the bottom-up approach, the original schema is likely to be in poor form and decomposition of relations are to be carried out regularly. So, here, we use normalisation as a decomposition process.
The following diagram illustrates the complete process of normalisation – red processes denoting the top-down approach, and green processes denoting the bottom-up approach.
2 Exercises
2.1 Awarm-upexercise
Consider the following relation.
1. Based on the above business rules (section 1.1), identify functional dependencies among these attributes.
Answer:
FD1: SSNàFname, Minit, Lname
EmpProject (SSN, Fname, MInit, Lname, Pno, Pname, Plocation, Dno, DName Hours)
FD2: PnoàPname, PLocation, DNo FD3: SSN, PnoàHours
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 2 of 11
FD4: DNoàDName
In fact, FD1 is not just one functional dependency, it is three functional dependencies written together.
FD11: SSNàFname
FD12: SSNàMinit
FD13: SSNàLname
In the same token, FD2 is also three functional dependencies written together.
2. What is the primary key of the relation?
Answer:
Based on the above functional dependencies, it can be derived that SSN and Pno attributes do not depend on any other attributes and there are no functional dependencies between them, as well. The rest of the attributes are dependent on one or both of them.
So, the primary key is
3. What the highest normal form is this relation in?
Answer:
Fname, Minit, Lname, PName, PLocation, DNo, and DName are partially dependent on the primary key. Only Hours is fully functionally dependent on the entirety of the primary key. Therefore, this relation does not meet 2NF. The highest normal form it is in 1NF.
4. Decompose the above EmpProject relation into a set of 3NF relations. Answer:
Eliminate the attributes that are partially dependent, along with a copy of the attribute that they are depend on (determinant). There are two such sets of attributes.
As a result we will have two new relations and the old one with remaining attributes. EmpProject1 (SSN, Pno, Hours) — this is the old one
EmpProject2 (SSN, Fname, Minit, LName) EmpProject3 (Pno, Pname, Plocation, DNo, DName) All the above relations are in 2NF.
Let’s test them for 3NF.
EmpProject1 is in 3NF, because it has only one non-primary-key attribute and there isn’t any possibility of having any transitive dependencies.
EmpProjectect2 has three non-primary-key attributes, however, none of them are dependent on each other and all of them are directly dependent on the primary key.
So, it is in 3NF.
EmpProject3 has one attribute, DName, that is transitively dependent.
So, that required a decomposition:
EmpProject 31 (Pno, Pname, Plocation, DNo*) – this is the old one
EmpProject32 (DNo, DName)
So, the final schema:
EmpProject1 (SSN*, Pno*, Hours) EmpProject2 (SSN, Fname, Minit, LName) EmpProject 31 (Pno, Pname, Plocation, DNo*) EmpProject32 (DNo, DName)
2.2 Anotherexercise
Consider the following relation for published books.
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 3 of 11
Book (BookTitle, AuthorName, BookType, DeweyNo, SubjectArea, ListPrice, AuthorAffiliation, Publisher)
Suppose the following functional dependencies exist:
BookTitleàBookType, DeweyNo, ListPrice, Publisher DeweyNo à SubjectArea
AuthorName à AuthorAffiliation
1. What is the primary key of the relation?
Answer:
Only BookTitle and AuthorName are the attributes that’s not been determined by any other attribute. The rest of the attributes are determined by one or both of them. (note that SubjectArea is only transitively dependent, but still it can be determined by BookTitle).
So, the primary key is
2. What the highest normal form is this relation in? Explain your answer. Answer:
All of the non-primary key attributes are partially dependent on the primary key (BookTitle, AuthorName).
So, the relation is not in second normal form. The highest normal form it is in 1NF.
3. Apply the normalisation process until you cannot decompose the relations further. State the reasons behind each decomposition.
Answer:
First move the attributes that are partially dependent along with a copy of the determinant attribute(s).
So, we have three relations: old one with residue attributes, a relation for attributes determined by BookTitle and the third wit attributes determined by AuthorName. Book1 (BookTitle, AuthorName)
Book2 (BookTitle, BookType, DeweyNo, SubjectArea, ListPrice, Publisher)
Book3 (AuthorName, AuthorAffiliation)
Out of these three relations, Book1 and Book3 are already in 3NF. (prove them by yourself).
Book2 is not in 3NF, due to the fact that SubjectArea (a non-primary key attribute) is functionally depend on another non-primary key attribute (DeweyNo).
So, Book2 has to be decomposed further.
Book21 (BookTitle, BookType, DeweyNo*, ListPrice, Publisher) Book22 (DeweyNo, SubjectArea)
As such, final relations are Book1, Book21, Book22, and Book3.
2.3 BuildingtheschemausingtheERmodel(top-downapproach)
This problem involves three steps, as outlined on the flowchart above.
1. Draw an ER model (using UML notation) to represent specifications and business rules outlined in Section 1.1.
Answer:
Refer to the diagram in Week 9 Lecture exercise solution.
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 4 of 11
2. Using the 7-step mapping process, map entities and relationships in your ER model into relations.
Answer:
After following 7-step mapping process, you will get the following relations:
Step 1: Strong entities
Employee (SSN, FName, MInit, LName, DoB, Addr, Gender, Position, Salary) Department (DNumber, DName, {DLocation})
Project (PNumber, PName, PLocation)
Step 2: Weak Entities
Dependent (SSN, Name, DoB, Relationship)
Step 3: 1:1 Relationships
Department(DNumber, DName, {DLocation}, SSN*, MgrStartDate)
Step4: 1:M Relationships
Employee (SSN, FName, MInit, LName, DoB, Addr, Gender, Position, Salary, SupervisorSSN*, DNumber*)
Project (PNumber, PName, PLocation, DNumber*)
Step 5: M:N relationships
WorksOn (SSN*, PNumber*, Hours)
Step6: Multi-valued Attribs
Department (DNumber, DName, SSN*, MgrStartDate) DeptLocations (DNumber, DLocation)
Step 7: Higher-degree relationships.
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 5 of 11
No actions required.
Final Relational Schema:
Dependent (SSN, Name, DoB, Relationship)
Employee (SSN, FName, MInit, LName, DoB, Addr, Gender, Position, Salary,
SupervisorSSN*, DNumber*)
Project (PNumber, PName, PLocation, DNumber*) WorksOn (SSN*, PNumber*, Hours)
Department (DNumber, DName, SSN*, MgrStartDate) DeptLocations (DNumber, DLocation)
Testing for 2NF
Dependent (SSN, Name, DoB, Relationship) FD1: SSN, NameàDoB —–ok
FD2: SSN, NameàRelationship —-ok Relation is in 2NF
Testing for 3NF No transitive deps Relation is in 3NF
Design (ER)àMappingàValidate
3. Validate each of the relations in the model using normalisation process. If any of the relations are not in 3NF, they must be decomposed. This is done, as follows:
a. Using the underlying business rules, identify the functional dependencies among attributes in the relation. Do not assume that primary key (that was identified at the mapping process) determines the rest of the attributes (because you cannot trust the choice of the primary key). If the business rules are not provided in a descriptive manner or you may have made several assumptions. However, they must all be present in the ER model in a graphical presentation. So, that’s where you should look to identify business rules.
b. Based on the functional dependencies identified in the above step, first determine the primary key of the relation. This may or may not the same as the original, but, this is the correct primary key.
c. Now that you have the correct primary key and a set of functional dependencies, you can determine the highest normal form the relation is in.
d. If it is not 3NF, start the decomposition process.
(Note: If you have used Oracle SQL Developer Data Modeler tool (or a similar tool) to draw the ER diagram, you can automatically generate the schema. However, you still are required to do the validation process before the database deployment in a real-time situation.)
Answer:
Employee:
Among the attributes in Employee relation, the following functional dependencies exist. FD1: SSNàFName, Minit, Lname, Bdate, Address, Sex, Position, SuperSSN, DNumber Note that Salary is not included here, because it can be derived from FD1 and FD2.
FD2: PositionàSalary
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 6 of 11
Based on the above, we can derive the correct primary key – SSN, because it cannot be derived from any other attributes. (In this case the given PK was correct).
This relation is in 1NF — because there are no multi-valued attributes.
The relation is in 2NF – because the primary key is simple primary key, as such no way it is not in 2NF. Partial dependencies can only occur when we have composite primary keys.
However, it is not in 3NF due to transitive dependency PositionàSalary.
Decompose Employee relation, by taking away Salary attribute with a copy of its determinant (Position.)
Employee1 (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*, Dnumber) Employee2 (Position, Salary)
They are both in 3NF.
All the other relations are already in 3NF. However, you still are required to go through the validation process. It is left as an exercise.
The final relations are:
Employee (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*, Dnumber*) Wages (Position, Salary)
DeptLocations (Dnumber, Location)
Department (Dnumber, Dname, MGRSSN*, MGRStartDate)
WorksOn (Pno, ESSN, Hours)
Project (Pno, Pname, Plocation, Dno)
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship)
The above will be the final 7 relations.
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 7 of 11
2.4 BuildingRelationsfromscratch(bottom-upapproach)
Let’s suppose that the following schema is developed to store data in the above-mentioned COMPANY.
1. For each of these relations, write down all non-trivial functional dependencies. If there are no functional dependencies among attributes, you must state so.
2. Write down the highest normal form each of these relations are in. For each of these relations, state the reasons why it doesn’t meet the next normal form requirements. This is not required if the relation is in 3NF.
3. If they are not in 3NF, decompose them into 3NF relations.
4. Where possible, combine the relations resulting from Part 3.
Answer: (combined together for convenience)
As discussed in the class, when relations are built from scratch (in bottom-up approach), it is unsafe to assume the correctness of the primary key. Always, determine the primary key based on functional dependencies.
1. Employee
Among the attributes in Employee relation, the following functional dependencies exist. FD1: SSNàFName, Minit, Lname, Bdate, Address, Sex, Position, SuperSSN
Note that Salary is not included here, because it can be derived from FD1 and FD2. FD2: PositionàSalary
Based on the above, we can derive the correct primary key – SSN, because it cannot be derived from any other attributes. (In this case the given PK was correct).
This relation is in 1NF — because there are no multi-valued attributes.
The relation is in 2NF – because the primary key is simple primary key, as such no way it is not in 2NF. Partial dependencies can only occur when we have composite primary keys.
However, it is not in 3NF due to transitive dependency PositionàSalary.
Decompose Employee relation, by taking away Salary attribute with a copy of its determinant (Position.)
Employee1 (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*) Employee2 (Position, Salary)
They are both in 3NF.
2. Department
Department (Dnumber, Dname, MGRSSN*, MGRStartDate, Location1, Location2, Location3, ESSN*)
This relation is a result of an incorrect attempt to address multi-valued attribute problem. On a quick glance, you may think it is in 1NF, because no multi-valued attributes visible. However, Location1, Location2, and Location3 is in fact created to store same attribute values. We call it a poor man’s solution to repeating groups problem. However, this is not acceptable solution.
Employee (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position, Salary, SuperSSN*) Department (Dnumber, Dname, MGRSSN*, MGRStartDate, Location1, Location2, Location3, ESSN*) Project (Pno, ESSN*, Pname, Plocation, Dno*, Hours)
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship)
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 8 of 11
Take one step back, put the relation back into having a multi-valued attribute and let the normalisation process to deal with it.
It should be:
Department (Dnumber, Dname, MGRSSN*, MGRStartDate, {Location}, ESSN*) The curly-braces denote the location is a multi-valued attribute.
So, this relation does not in 1NF. It is an unnormalised (or 0NF) relation.
To address this problem, remove the offending attribute, along with Dnumber and form a separate relation.
We’ll then have:
Department1 (Dnumber, Dname, MGRSSN*, MGRStartDate, ESSN*)
Department2 (Dnumber, Location)
(In Department2, multiple locations (for a department) are stored in multiple tuples.) With no non-primary key attributes, we can safely assume that Department2 is in 3NF.
We have to validate and decompose Department1.
The following functional dependencies exist here:
FD1: DnumberàDName, MGRSSN, MGRStartDate
Note that we cannot determine ESSN from the Dnumber (one department can have a large number of employees).
However, to contrary to that, we can derive:
FD2: ESSNàDnumber,
Because each employee is assigned to one department.
Based on FD1 and FD2, (against all expectations!) the correct primary key is ESSN. The given primary key is incorrect. Only attribute that’s not determined by any other attribute is the ESSN.
So, we can rewrite the relation as follows:
Department1 (ESSN, Dnumber, Dname, MGRSSN*, MGRStartDate) This relation is in 2NF. (prove!)
However, it is not in 3NF, due to transitive dependencies. Dnumber, Dname, MGRSSN, and MGRStartDate are all transitively dependent on the primary key.
As is the case with previous relations, decompose Department1 into two relations, as follows:
Department3 (ESSN, Dnumber*)
Department4 (Dnumber, Dname, MGRSSN*, MGRStartDate)
Department 3 and Department4 are in 3NF.
3. Project
Project (Pno, ESSN*, Pname, Plocation, Dno*, Hours)
The following functional dependencies exist. PnoàPname, Plocation, DNo
Pno, ESSNàHours
Based on that we can determine the primary key —
So, the correct relation is:
Project (Pno, ESSN*, Pname, Plocation, Dno*, Hours)
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 9 of 11
Based on this correct primary key and the functional dependencies, we can determine the highest normal form this relation is 1NF.
It does not meet 2NF requirements, because Pname, Plocation, and DNo attributes are partially dependent.
After decomposing, we end up with following two relations: Project1 (Pno, ESSN, Hours)
Project2 (Pno, Pname, Plocation, Dno)
We can prove that they are also in 3NF. (i.e no transitive dependencies).
4. Dependent
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship) The following functional dependencies exist.
FD1: ESSN, DependentNameàSex, Bdate, Relationship No other functional dependencies exist.
As such, we can determine the primary key –
Also, we can prove that in the absence of partial dependencies and transitive dependencies, this relation is in 3NF.
The given relation doesn’t need any decompositions.
All four relations have gone through the normalisation process. Now is the time to collate all the resultant relations.
They are:
Employee1 (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*) Employee2 (Position, Salary)
Department2 (Dnumber, Location)
Department3 (ESSN, Dnumber*)
Department4 (Dnumber, Dname, MGRSSN*, MGRStartDate)
Project1 (Pno, ESSN, Hours)
Project2 (Pno, Pname, Plocation, Dno)
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship)
After a careful inspection on the above list, you will find that Employee1 and Department3 have the same primary key – SSN. There is no reason to keep them separate. They should be re-joined to form one relation.
Employee1 (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*, Dnumber*)
Employee2 (Position, Salary)
Department2 (Dnumber, Location)
Department3 (ESSN, Dnumber*)
Department4 (Dnumber, Dname, MGRSSN*, MGRStartDate) Project1 (Pno, ESSN, Hours)
Project2 (Pno, Pname, Plocation, Dno)
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship)
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara School/Department/AreaComputer Science and IT Save Date: 12/05/2020 Page 10 of 11
To improve the readability of the schema, it is a good idea to give them better names (to better reflect what they really represent).
Employee1 (SSN, Fname, Minit, Lname, BDATE, Address, Sex, Position*, SuperSSN*, Dnumber*)
Positions Employee2 (Position, Salary)
DeptLocations Department2 (Dnumber, Location)
Department4 (Dnumber, Dname, MGRSSN*, MGRStartDate) WorksOn Project1 (Pno, ESSN, Hours)
Project2 (Pno, Pname, Plocation, Dno)
Dependent (ESSN*, DependentName, Sex, Bdate, Relationship)
The above will be the final 7 relations.
2.5 Achallengequestion
Consider the following relation.
The following constraints exist:
A course can have multiple tutors, however, a student can only attend one class run by one tutor. A tutor can only take classes from one course.
Study (Student, Course, Tutor)
1. Is this relation in 3NF? Discuss.
2. Is this relation in BCNF? Discuss. (question for next week)
School/Department/AreaComputer Science and IT
Document: 2020 Lecture 10 – Normalisation Exercises — with answers.docx Author: Santha Sumanasekara Save Date: 12/05/2020 Page 11 of 11