Third Normal Form and Transitive Dependency

Definition

A relation is in third normal form when:

1. It is in 2NF, and
2. No non prime attribute is transitively dependent on any candidate key.

A transitive dependency is X -> Y and Y -> Z, where X is a key, Y is not a key, and Z is non prime — giving X -> Z indirectly.

The alternative definition

An equivalent and more usable statement: for every non trivial dependency X -> A, at least one of the following must hold:

• X is a super key, or
• A is a prime attribute — it belongs to some candidate key.

The second clause is what separates 3NF from BCNF. BCNF drops it and demands that every determinant be a super key, full stop. Learning both definitions now makes the next note almost free.

The violating relation

  STUDENT ( roll, name, dept_code, dept_head, dept_building )

  candidate key = { roll }
  prime     : roll
  non prime : name, dept_code, dept_head, dept_building

  Dependencies:
    roll      -> name, dept_code
    dept_code -> dept_head, dept_building

  dept_code is NOT a key, and dept_head is non prime, so:

    roll -> dept_code -> dept_head       TRANSITIVE

  In 2NF (the key is a single attribute) but NOT in 3NF.

  roll | name   | dept_code | dept_head | dept_building
  -----+--------+-----------+-----------+--------------
   21  | Meera  | CS        | Dr Rao    | Block A
   22  | Ravi   | CS        | Dr Rao    | Block A
   25  | Divya  | CS        | Dr Rao    | Block A
   23  | Anitha | EC        | Dr Iyer   | Block B

  Dr Rao and Block A repeat on every Computing student.

  ANOMALIES
    insert  a department with no students cannot be recorded
    update  a new head means changing every student row
    delete  the last EC student leaves erases Dr Iyer and
            Block B

Converting to 3NF

1. Find the transitive dependency: a non key determinant with non prime dependents.
2. Move the determinant and its dependents into a new relation.
3. Make the determinant the primary key of that relation.
4. Leave the determinant behind in the original relation as a foreign key.

  AFTER DECOMPOSITION

  STUDENT ( roll, name, dept_code )
     21 Meera  CS
     22 Ravi   CS
     25 Divya  CS
     23 Anitha EC
       dept_code -> DEPARTMENT

  DEPARTMENT ( dept_code, dept_head, dept_building )
     CS  Dr Rao   Block A
     EC  Dr Iyer  Block B

  Check:
    STUDENT     roll -> name, dept_code. No non key
                determinant remains.            -> 3NF
    DEPARTMENT  dept_code is the key.           -> 3NF

  The head is now stored once. A department with no
  students exists in its own right. Deleting a student
  loses only that student.

Why the prime attribute exemption exists

  R ( city, street, pincode )
  F = { { city, street } -> pincode
      , pincode          -> city }

  candidate keys: { city, street } and { street, pincode }
  prime attributes: city, street, pincode  - ALL of them
  non prime attributes: NONE

  Test  pincode -> city  against 3NF:
     is pincode a super key?   no
     is city prime?            YES
  -> the second clause is satisfied, so R IS in 3NF.

  Test the same dependency against BCNF:
     is pincode a super key?   no
  -> NOT in BCNF.

  This is the classic relation that is in 3NF but not BCNF,
  and it is worth memorising because it appears constantly
  in exams.

3NF synthesis: guaranteed decomposition

There is an algorithm that always produces a 3NF decomposition which is both lossless and dependency preserving. It uses the minimal cover from Phase 7.

  1  compute a MINIMAL COVER of F
  2  for each dependency  X -> A  in the cover,
       create a relation containing X and A
       (combine dependencies with the same X into one relation)
  3  if no relation contains a candidate key of the original,
       add one relation consisting of a candidate key
  4  remove any relation whose attributes are contained
       in another

  Step 3 is what guarantees losslessness. Step 2 is what
  guarantees dependency preservation. Both properties
  together are why 3NF is often preferred to BCNF in
  practice - BCNF cannot always promise the second one.

  APPLYING IT

  R ( A, B, C, D, E )
  minimal cover = { A -> B, A -> C, C -> D, D -> E }
  candidate key = { A }

  step 2   A -> B and A -> C share a left side  -> R1 ( A, B, C )
           C -> D                               -> R2 ( C, D )
           D -> E                               -> R3 ( D, E )

  step 3   does any relation contain { A }?  R1 does.
           nothing to add.

  step 4   no relation is contained in another.

  RESULT   R1 ( A, B, C ), R2 ( C, D ), R3 ( D, E )
           lossless and dependency preserving.

Common mistakes

• Missing the prime attribute clause. It is what makes 3NF weaker than BCNF, and it is where marks are lost.
• Forgetting the middle attribute must not be a key. If it is, the dependency is not a violation.
• Deleting the determinant from the original relation. It must stay as the foreign key, or the join is lost.
• Applying the synthesis algorithm without a minimal cover. The result will contain redundant relations.
• Assuming 3NF removes all redundancy. It does not; BCNF, 4NF and 5NF each remove more.

Exam and interview questions

1. Define 3NF using both the transitive dependency form and the two clause form.
2. What is a transitive dependency? Give an example with the anomalies it causes.
3. Convert STUDENT above to 3NF, showing the decomposition.
4. Give a relation in 3NF but not in BCNF and explain exactly which clause saves it.
5. Describe the 3NF synthesis algorithm and state the two properties it guarantees.

Practice

1. R ( A, B, C, D ), F = { A -> B, B -> C, C -> D }, key { A }. Identify the transitive dependencies and decompose to 3NF.
2. Normalise EMPLOYEE ( emp_id, name, dept_id, dept_name, dept_location ) to 3NF.
3. Apply the synthesis algorithm to F = { A -> B C, C D -> E, B -> D, E -> A } after computing a minimal cover.

Conclusion

3NF removes transitive dependencies: no non prime attribute may depend on a non key determinant. The prime attribute exemption is what distinguishes it from BCNF, and the synthesis algorithm is the reason 3NF can always be reached without losing a dependency.