DATABASE SYSTEMS
Lecture 8 More about Data Redundancy!
Functional Dependency
Note that the attribute to the right of the arrow is functionally dependent on the
attribute in the left of the arrow.
Thus the combination (Sid, Course-id) is the determinant (that determines other
attributes) and attributes Sname, Phone, Course-description, Credit-hours and
Grade are dependent attributes.
Formally speaking a determinant is an attribute or a group of attributes determine
the value of other attributes.
In addition to the (Sid, Course-id) there are two other determinants in the
above Student-courses relation.
These are; Sid and Course-id attributes. Note that Sid alone determines both
Sname and Phone, and attribute Course-id alone determines both Credit-hours and
Course_description attributes.
Attribute Grade is fully functionally dependent on the primary
key (Sid, Course-id) because both parts of the primary keys are
needed to determine Grade.
On the other hand both Sname, and Phone attributes are not fully
functionally dependent on the primary key, because only a part
of the primary key namely Sid is needed to determine
both Sname and Phone.
Also attributes Credit-hours and Course-Description are not fully
functionally dependent on the primary key because only Course-
id is needed to determine their values.
Third Normal Form
A table is in third normal form (3NF) iff it is in 2NF
and there is no transitive dependency, that is, no
non-key attribute is dependent on another non-key
attribute
3rd Normal Form
The THIRD NORMAL FORM’s objective is to remove
data in a table that is not dependent on the primary
key.
The entity is in SECOND NORMAL FORM and a non-UID
attribute can’t depend on another non-UID attribute
All non-UID attributes should depend directly on the
whole UID and not on each other.
3rd Normal Form
Put another way, attributes don’t have attributes of
their own. If attributes do have attributes, they’re
really entities.
For example, the EMPLOYEE entity
has an attribute called category.
Category initially has potential
values of technical, management,
administrative, or professional.
Later, however, we decide to add
an attribute called category level,
which further qualifies category into
a more detailed subgroup based on
expertise level with potential values
of 1 for a beginner, 2 for a middle
level, and 3 for an expert.
Category level is dependent first on category.
Category level is only dependent on the
employee id ( entity Unique ID, UID) through
category. An attribute dependency on the
UID—which is not direct but only passes
through another attribute that is dependent on
the UID—is called a transitive dependency.
Transitive dependencies are unacceptable in
THIRD NORMAL FORM.
Category and category level need to be moved
from the EMPLOYEE entity to their own
EMPLOYEE_CATEGORY entity as a violator
of THIRD NORMAL FORM.
Third Normal Form
A table is in third normal form (3NF) iff it is in 2NF
and there is no transitive dependency, that is, no
non-key attribute is dependent on another non-key
attribute
Transitive Dependency Example
STD(stId, stName, stAdr, prName, prCrdts)
stId → stName, stAdr, prName, prCrdts
prName → prCrdts
Anomalies
stId stName stAdr prName prCrdts
S1020 Sohail Dar I-8 Islamabad MCS 64
S1038 Shoaib Ali G-6 Islamabad BCS 132
S1015 Tahira Ejaz L Rukh Wah MCS 64
S1015 Tahira Ejaz L Rukh Wah MCS 64
S1018 Arif Zia E-8, Islamabad. BIT 134
Third Normal Form
STD(stId, stName, stAdr, prName, prCrdts)
stId → stName, stAdr, prName, prCrdts
prName → prCrdts
STD (stId, stName, stAdr, prName)
PROGRAM (prName, prCrdts)
3NF Relations
Each of the table is in 3NF
Free of all anomalies
Boyce Code Normal Form (BCNF)
A general form of 3NF.
Every relation in BCNF is in 3NF vice-versa is not
always true
3NF is checked in steps, BCNF is checked directly
Boyce Code Normal Form (BCNF)
A table is in BCNF if every determinant is a candidate key
Situation when table in 3NF is not in BCNF
A non-key determines a part of the composite primary key
HINT:
-- If we have only one candidate key and that will definitely the PK then surely the table
is in BCNF
-- If we have multiple candidate keys but all these candidate keys are consisted of
single attribute again its in 3NF and BCNF.
-- If we have multiple candidate keys and these are also composite keys but there is no
common attributes in them again its in 3NF and BCNF.
Boyce Code Normal Form (BCNF)
FACULTY(fId, dept, office, rank, dateHired)
fId, dept → office, rank, dateHired
office → dept
Table is in 3NF, not in BCNF since the office is not a
candidate key
Boyce Code Normal Form (BCNF)
We decompose the table again to bring it into BCNF
FACULTY(fId, dept, office, rank, dateHired)
FACULTY(fId, office, rank, dateHired)
OFFICE(office, dept)
Normalization Example
Identify FDs
Apply on the relevant tables; see if any
normalization requirement is being violated, that is,
causing some anomaly
Normalization Example
PROJNAME PROJMGR EMPID HOURS EMPNAME BUDGET STARTDATE SALARY EMPMGR EMPDEPT RATING
Business Rules (Specifications)
1. Each project has a unique name, but names of
employees and managers are not unique
2. Each project has one manager, whose name is
stored in PROJMGR
PROJNAME PROJMGR
3. Many employees may be assigned to work on
each project, and an employee may be assigned
to more than one project. HOURS tells the number
of hours per week that a particular employee is
assigned to work on a particular project
PROJNAME, EMPID HOURS
4. Budget stores the amount budgeted for a
project, and STARTDATE gives the starting date
for a project
PROJNAME PROJMGR, BUDGET, STARTDATE
5. Salary gives the annual salary of an employee
EMPID SALARY
6. EMPMGR gives the name of the employee’s
manager, who is not the same as the project manager
EMPID EMPMGR
7. EMPDEPT gives the employee’s department.
Department names are unique. The employee’s
manager is the manager of the employee’s
department.
EMPDEPT EMPMGR
8. RATING gives the employee’s rating for a
particular project. The project manager assigns the
rating at the end of the employee’s work on that
project.
PROJNAME, EMPID RATING
2 4 4
PROJNAME PROJMGR, BUDGET, STARTDATE
5 6 6, 7
EMPID EMPNAME, SALARY, EMPMGR, EMPDEPT
3 8
PROJNAME, EMPID HOURS, RATING
7
EMPDEPT EMPMGR
Original relation:
WORK (PROJNAME, PROJMGR, EMPID, HOURS, EMPNAME, BUDGET, STARTDATE,
SALARY, EMPMGR, EMPDEPT, RATING)
New relations:
PROJ ( PROJNAME, PROJMGR, BUDGET, STARTDATE)
EMP ( EMPID, EMPNAME, SALARY, EMPMGR, EMPDEPT)
WORK ( PROJNAME, EMPID, HOURS, RATING)
PROJ ( PROJNAME, PROJMGR, BUDGET, STARTDATE)
EMP ( EMPID, EMPNAME, SALARY, EMPMGR, EMPDEPT)
WORK ( PROJNAME, EMPID, HOURS, RATING)
PROJ ( PROJNAME, PROJMGR, BUDGET, STARTDATE)
EMP ( EMPID, EMPNAME, SALARY, EMPDEPT)
DEPT ( EMPDEPT, EMPMGR)
WORK ( PROJNAME, EMPID, HOURS, RATING)
Checking for BCNF
PROJ ( PROJNAME, PROJMGR, BUDGET, STARTDATE)
PROJNAME PROJMGR, BUDGET, STARTDATE
EMP ( EMPID, EMPNAME, SALARY, EMPDEPT)
EMPID EMPNAME, SALARY, EMPMGR, EMPDEPT
WORK ( PROJNAME, EMPID, HOURS, RATING)
PROJNAME, EMPID HOURS, RATING
DEPT ( EMPDEPT, EMPMGR)
EMPDEPT EMPMGR
Normalization Summary
A step by step process to make DB
design more efficient and accurate
A strongly recommended activity
performed after the logical DB design
phase
Normalization Summary
Un-normalized relations are more
prone to errors or inconsistencies
Normalization is based on the FDs
FDs are not created rather identified
by the designer/analyst
Normalization Summary
Normalization forms exist up to 6NF,
however, for most of the situations 3NF
is sufficient
Performed through Analysis or
Synthesis process