10. NORMALIZATION

10.1: Functional Dependencies

To understand normalization theory (first, second, third and Boyce-Codd normal forms), we must understand what is meant by the term functional dependency. There is another type of dependency called a multi-valued dependency but that is important to the understanding of higher normal forms not covered in this text.

A functional dependency is an association between two attributes. We say there is a functional dependency from attribute A to an attribute B if and only if for each value of A there can be at most one value for B. We can illustrate this by writing:

      • A functional determines B, or
      • B is functionally determined by A, or
      • by a drawing such as: 

When we have a functional dependency from A to B, we refer to attribute A as the determinant.

 

EXAMPLE 1.

Consider a company collects information about each employee such as the employee’s identification number (ID), their first name, last name, salary and gender. As is typical, each employee is given a unique ID which serves to identify the employee. Hence for each value of ID there is at most one value for first name, last name, salary and gender.

Therefore, we have four functional dependencies where ID is the determinant; we can show this as a list or graphically:

 

image

If you think about this case, there cannot be any other FDs. For example, consider the gender attribute – we need to allow for more than one employee for a given gender, and so we cannot have a situation where gender functionally determines ID. So, gender  ID cannot exist. Now consider the first name attribute. Again, we need to allow for more than one employee to have the same first name and so first name cannot determine anything. Similarly, for other attributes.

 

EXAMPLE 2.

Recall the Department and Course tables introduced in Chapter 2 – sample data is shown below:

deptCode

deptName

deptLocn

deptPhone

chairName

MATH

Mathematics

2R33

786-0033

Peter Smith

HIST

History

3D07

786-0300

Simon Lee

IS

Indigenous Studies

3C11

786-3322

Leslie Roman

MENN

Mennonite Studies

3C11

786-3322

Leslie Roman

BIOL

Biology

2L88

786-9843

James Dunn

deptCo de

courseN o

title

description

creditHou rs

HIST

1010

Introduction to History

Within a relatively small lecture/seminar setting, this course introduces you to the ways in which people try to understand their present by studying their past.

6

IS

1010

Indigenous Ways of Knowing

This course offers an introduction to Indigenous ways of knowing through active participation in strategies that facilitate the production of Aboriginal knowledge and through comparisons with Euro-American ways of knowing.

3

MENN

1010

Mennonites and the Modern World

This course is a history of the ethnic identity and religious faith of the Mennonites from the sixteenth century to the present.

6

IS

1201

Introductory Ojibwe

This course is intended for students who are not fluent in Ojibwe and have never taken a course in the language

6

BIOL

2401

Forest Field Skills Camp

This intensive two-week field course is mandatory for students in the Forest Ecology program and is designed to give students field survival and basic forestry skills.

1

Recall the primary keys (underlined above) of these two tables:

Table

PK

Department

deptCode

Course

deptCode, courseNo

Consider the Department table where deptCode is the primary key. For each value of deptCode there is at most one value for deptName, deptLocn, deptPhone, and chairName. You should agree the following FDs exist:

      • deptCode –> deptName
      • deptCode –> deptLocn
      • deptCode –> deptPhone
      • deptCode –> chairName

Each row of the Course table has one value for title, one value for description, and one value for credit hours. The primary key of Course consists of two attributes, deptCode and courseNo. The following FDs exist for the Course table:

      • deptCode, courseNo –> title
      • deptCode, courseNo –> description
      • deptCode, courseNo –> credit hours

In this case we have a determinant comprising two attributes; the determinant is composite.

 

We can draw the functional dependencies as:

image

Could there be other functional dependencies in this situation?

These examples demonstrate that there is a FD from the primary key to each of the other attributes in a table.

 

EXAMPLE 3.

The following ERD is shown in the Chen notation. There is one entity type named Employee that has 4 attributes. In this design there are two keys (id and sin) and two descriptive attributes (firstName and lastName):

 

image

Each symbol in an ERD contains information about a model. From the above we know there are two keys, id and sin. An id value, or a sin value, will uniquely identify an employee and so we have the six FDs:

 

image

This example shows that an ERD carries information that can be expressed in terms of FDs.

 

Exercises

1) Consider the Product table below where productID is the PK. What FDs must exist in this table:

productID

description

unit price

quantity on

hand

33

16 oz. can tomato soup

1.00

50

41

454 grams box corn

flakes

4.50

39

45

Package red licorice

1.00

39

46

Package black licorice

1.00

50

47

1 litre 1% milk

1.99

25

 

2) Consider the ERD where the entity type Employee has one key attribute, id, and the entity type Position has one key attribute, title. As well the ERD shows a one-to-many relationship assigned to which can be expressed as:

  • An employee is assigned to at most one position. A position can be assigned to many employees.
image
  • List the FDs that must be present.

 

3) Consider the ERD below which is similar to the above, but where the assigned to relationship is many-to-many, and where assigned to has an attribute startDate. List the FDs that are present.

image

4) Consider the ERD below where Department has two keys deptCode and deptName – each department has a unique department code and has a unique department name. Course is a weak entity type with a partial key courseNo, and where offers is an identifying relationship.

image
  • List the FDs that must exist.

 

5) Consider the table T with attributes A, B and C.

A

B

C

1

33

100

2

33

200

3

22

200

1

33

101

2

33

350

4

67

350

5

67

101

6) Suppose there are many more rows that are not shown:

  • Is there a functional dependency from B to A? Explain your answer.
  • The rows that are shown suggest there could be a functional dependency A –> B. Compose a database query that would indicate counter examples, if they exist, for the functional dependency A –> B. Such a query would list values of A in the table where two or more rows have the same value for A but different values for B.

Share This Book