Normal Forms (1st to 3rd)

Guest lecture by K. Yue (November 29th, 2001)

This supplementary note is for a guest lecture on Dr. Boetticher's class on November 29th, 2001. Refer to the main note by Dr. Boetticher. The notes are based on my old notes in database classes.

Lossless Decomposition

It is assumed that the students are already familiar with the theory of lossless decomposition, including the concepts of closure, minimal covers, etc, as well as the 'matrix algorithm' for testing lossless decomposition.

I have written several Lisp programs long time ago for getting closure, cover and determining lossless decomposition. If you are interesting in reading, they are here:

• closure.lisp: finding the closure of a set of attributes.
• cover.lisp: finding a minimal cover of a set of functional dependencies.
• preserve.lisp: testing whether a decomposition is lossless.

Relational Database Designs

• Bad designs results in:
  • redundancy: inefficient storage.
  • anomalies: data inconsistency, difficulties in maintenance

Example:

Relation Scheme:

EMPLOYEE(EMP_NO, NAME, DEPT_NO, MANAGER_NO).

with the following assumptions:

• Every employee works for only one department.
• Every department has only one manager.
• Every manager manages only one department.

An instance of the relation:

Redundancy:

The fact Manager 54321 manages department D123 is stored three times.

Update Anomalies:

Update: 44444 is now the new manager of department D123

• inefficiency in update.
• potential inconsistency.
  

Update: Magic Johnson now works for department D337:

• need to know the manager of D337 before insertion.
• Potential inconsistency.
  

Update: Nolan Ryan now works for the new department D822, which does not have a manager yet.

Insertion Anomalies:

Insert: a new department D888, with manager 77111, currently with no employee is not possible.

Deletion Anomalies:

Delete: Carl Sagan no longer works here.

• The information 33323 is the manager of the department D337 (now without employees) is lost.

Solution

Decomposition to relations that satisfy desirable normal forms.

EMP(EMP_NO, NAME, DEPT_NO)
DEPARTMENT(DEPT_NO, MANAGER_NO)

All anomalies mentioned above are now gone.

Normal Forms

• A set of rules to avoid redundancy and inconsistency.
• Require the concepts of:
  • functional dependency (most important: up to BCNF)
  • multivalued dependency (4NF)
  • join dependency (5NF)
• Seven Common Normal Forms: 1NF, 2NF, 3NF, BCNF, 4NF, 5NF, DKNF. (There are more.)
• Higher normal forms are more restrictive.
• A relation is in a higher normal form implies that it is in a lower normal form, but not vice versa.
• Assumption: students are already familiar with functional dependencies (FD).

First Normal Form

• A relation is in 1NF if all attribute values are atomic: no repeating group, no composite attributes.
• Formally, a relation may only has atomic attributes. Thus, all relations satisfy 1NF.

Example:

Consider the following table. It is not in 1 NF.

The corresponding relation in 1 NF:

• Problem of NFNF (non-first normal form): relational operations treat attributes as atomic.

Second Normal Form

• A relation R is in 2NF if
  • (a) R is in 1NF, and
  • (b) all non-prime attributes are fully dependent on the candidate keys.
• A prime attribute appears in a candidate key.
• There is no partial dependency in 2NF. For a nontrivial FD X -> A and X is a subset of a candidate key K, then X = K.
  

Example:

The following relation is not in 2NF. The relation has the following FD:

Student_ID, Course -> Grade
Course -> Credit

Note the redundancy and anomalies.

Third Normal Form

• A relation R is said to be in the third normal form if for every nontrivial functional dependency X --> A,
  • (1) X is a superkey, or
  • (2) A is a prime (key) attribute.
• An attribute is prime (a key attribute) if it appears in a candidate key. Otherwise, it is non-prime.

Example:

The example relation for anomalies is not in 3NF.

EMPLOYEE(EMP_NO, NAME, DEPT_NO, MANAGER_NO).

with the following assumptions:

• Every employee works for only one department.
• Every department has only one manager.
• Every manager manages only one department.

An instance of the relation:

• Note that it is important to consider only non-trivial FD in the definitions of both 2NF and 3NF.

Example:

Consider R(A,B,C) with the minimal cover F: {A -> B}. Note that F |- B -> B, or B -> Bis in F+. For B -> B, B is not a superkey and B is non-prime. However, B -> B is not a violation of 3NF as it is trivial and should not be considered for potential violation.

• 3NF cannot eliminate all redundancy due to functional dependencies.
  

Example:

Consider the relation

S(SUPP#, PART#, SNAME, QUANTITY) with the following assumptions:

(1) SUPP# is unique for every supplier.
(2) SNAME is unique for every supplier.
(3) QUANTITY is the accumulated quantities of a part supplied by a supplier.
(4) A supplier can supply more than one part.
(5) A part can be supplied by more than one supplier.

We can find the following nontrivial functional dependencies:

(1) SUPP# --> SNAME
(2) SNAME --> SUPP#
(3) SUPP# PART# --> QUANTITY
(4) SNAME PART# --> QUANTITY

Note that SUPP# and SNAME are equivalent.

The candidate keys are:

(1) SUPP# PART#
(2) SNAME PART#

The relation is in 3NF.

However, the relation has unnecessary redundancy:

We need a higher normal: BCNF. The relation above is not in BCNF.

Dr. Kwok-Bun Yue
Professor, Computer Science and Computer Information Systems
Chair, Division of Computing and Mathematics
University of Houston-Clear Lake
2700 Bay Area Boulevard
Houston, TX 77058
  Yue's home page      yue@uhcl.edu       281-283-3864