Highest Normal Form (HNF)

• Before We Begin

• Worked Examples

• Q & A

• Normal Forms Definitions

• Find the HNF of BUNYIP

[Top]

Before We Begin

What do we need to know before we can determine a relation's HNF?

The functional dependencies (FDs) amongst the attributes in the relation

What do we need to do before we can determine a relation's HNF?

1. Determine a minimal FD list

2. Find all the candidate keys

3. Categorise each attribute in the relation as prime or non-prime

   A prime attribute is an attribute which is part of any candidate key

   A non-prime attribute is not part of any candidate key

[Top]

Worked Examples

• R1

• WORKSTATION

[Top]

R1 Example

We are given a relation

   R1  (A, B, C, D, E)

and the minimal set of FDs amongst its attributes

  F= {A    -> B
      A, C -> D
      B    -> E}

and asked to find its highest normal form (HNF).

First, we find the candidate keys of R1.

A candidate key uniquely defines each row in a relation. It follows that each candidate key functionally determines each and every attribute in the relation.

To demonstrate that {A, C} is a candidate key:

     A, C -> A  trivial dependency

     A, C -> B  augmentation of A -> B
                  from the minimal FD list F

     A, C -> C  trivial dependency

     A, C -> D  from the minimal FD list F

     A, C -> E  augmentation of A -> E
                  which is derived transitively from A -> B  and B -> E

{A,C} is the only candidate key for R1.

Therefore

• the set of prime attributes of R1 is {A, C}

• the set of non-prime attributes of R1 is {B, D, E}

Now we can find the (highest) normal form of R.

First, let's quickly check to see if the relation is in BCNF.

Is every determinant in F a candidate key?
No, determinant A is not a candidate key.   (It is part of a candidate key but it is not a candidate key.)

So let's step through the normal forms.

We are told that R1 is a relation, so it is in 1NF.
(It is possible that you may interpret an E-R diagram in such a way that you propose a relation which is un-normalised, but all the relations you are given in COMP2400 and COMP3420 will be in at least 1NF.)

Are there any partial dependencies? Are any of the non-prime attributes dependent on only part of any candidate key?
Yes. Non-prime attribute B is dependent on A which is only part of the candidate key {A, C}. So R1 is not in 2NF.
Therefore the Highest Normal Form of R1 is 1NF.

(There is no point in checking for 3NF. If R1 is not in 2NF, it cannot be in 3NF.)

[Top]

WORKSTATION Example

We are given a relation and its associated minimal FD Diagram

and asked to find its highest normal form (HNF).

The minimal FD list which corresponds to the minimal FD diagram for WORKSTATION is:

     Model-id            → Weight
     Lab-no              → Model-id
     Model-id, Serial-no → Lab-no
     Model-id, Serial-no → Condition

The candidate keys of WORKSTATION are  {Model-id, Serial-no}  and  {Lab-no, Serial-no}.

The prime attributes of WORKSTATION are  {Model-id, Serial-no, Lab-no}.
The non-prime attributes of WORKSTATION are  {Weight, Condition}.

Is WORKSTATION in 1NF?

Yes, it is a proper relation.

Is WORKSTATION in 2NF?

Is each non-prime attribute fully functionally dependent on each candidate key?

A non-prime attribute is fully functionally dependent on a candidate key if it is not dependent on any proper subset of the candidate key.

The non-null proper subsets of  {Model-id, Serial-no } are

  {Model-id}
  {Serial-no}

Are either of the non-prime attributes,  Weight  and  Condition, determined by either  Model-id  or  Serial-no?

Yes.  Model-id → Weight
Weight  is not fully functionally dependent on the candidate key  {Model-id, Serial-no} 
because  Weight  is dependent on  {Model-id}  which is a proper subset of the candidate key  {Model-id, Serial-no}.

Having found one counter example, we can stop and say that WORKSTATION is not in 2NF.

Therefore the highest normal form of WORKSTATION is 1NF.

[Top]

Q & A

Question

How can the following FD diagram be in 2NF when Drug-id has nothing to do with Colour?

Answer

Relations have normal forms; FD diagrams do not have normal forms.

What exactly do you mean by "has nothing to do with"?

The relation which corresponds to the FD diagram is:

DRUG (Drug-id, Country-id, Category, Colour)

The candidate key of DRUG (shown in the FD diagram in a bold box) is {Drug-id, Country-id}.

The prime attributes of DRUG (shaded in the FD diagram) are {Drug-d, Country-id}.

The non-prime attributes of DRUG are {Category, Colour}.

Is DRUG in 1NF?

Yes, it is a proper relation.

Is DRUG in 2NF?

Is each non-prime attribute fully functionally dependent on each candidate key? A non-prime attribute is fully functionally dependent on a candidate key if it is not dependent on any proper subset of the candidate key.

The non-null proper subsets of {Drug-id, Country-id} are:

{Drug-id} {Country-id}

Are either of the non-prime attributes, Category and Colour, dependent on either {Drug-id} or {Country-id}?

No.

Therefore, DRUG is in 2NF

If you wish to show that my assertion is incorrect, that DRUG is not in 2NF, you have to show that one of the non-prime attributes (Category or Colour) is dependent on either {Drug-id} or {Country-id}.

[Top]

Question

How can the following FD diagram be in 2NF when Phone-no is dependent on Lecturer-id as well as Unit-name?

Answer

I think you are mixing up partial dependencies and transitive dependencies.

The only candidate key (and therefore the primary key) of UNIT is {Unit-name}.

If UNIT is not in 2NF, which part (proper subset) of {Unit-name} is Room-no (or any other non-prime attribute) dependent upon?

Full and Partial FDs Example

[Top]