4NF, 5NF, Multivalued and Join Dependencies

Concept

BCNF removes every redundancy caused by functional dependencies. Two further kinds of dependency can still cause redundancy, and 4NF and 5NF address them.

Multivalued dependency

A multivalued dependency X ->> Y holds when, for each value of X, there is a set of Y values that is independent of the other attributes of the relation.

  STUDENT_INFO ( roll, course, hobby )

   roll | course | hobby
   -----+--------+---------
    21  | CS201  | Chess
    21  | CS201  | Music
    21  | CS202  | Chess
    21  | CS202  | Music

  Meera takes 2 courses and has 2 hobbies. Her courses have
  NOTHING to do with her hobbies. Yet the relation is forced
  to store 2 x 2 = 4 rows to avoid implying a connection.

  Add one more hobby and you must add 2 more rows, one per
  course, or the relation falsely suggests that the new hobby
  applies to only some courses.

  roll ->> course
  roll ->> hobby

  Note: every functional dependency is also a multivalued
  dependency, with a set of size one. MVDs generalise FDs.

Fourth normal form

A relation is in 4NF when it is in BCNF and, for every non trivial multivalued dependency X ->> Y, X is a super key.

  STUDENT_INFO is in BCNF - the only key is the whole
  relation, and there are no functional dependencies to
  violate anything.

  But  roll ->> course  and roll is not a super key,
  so it is NOT in 4NF.

  DECOMPOSE into one relation per independent fact:

    STUDENT_COURSE ( roll, course )     STUDENT_HOBBY ( roll, hobby )
       21  CS201                            21  Chess
       21  CS202                            21  Music

  4 rows become 4 rows here, but the growth changes:
    3 courses and 4 hobbies
      combined: 12 rows
      split:     3 + 4 = 7 rows
    and adding a hobby now adds exactly ONE row.

  RULE: a multivalued dependency is trivial - and therefore
  harmless - when Y is a subset of X, or when X and Y
  together are the whole relation. That is why a relation
  with only TWO attributes is always in 4NF.

Join dependency and fifth normal form

A join dependency holds when a relation can be reconstructed by joining several of its projections, but not by joining any two of them. 5NF, also called project join normal form, removes them.

  SUPPLY ( supplier, part, project )

  meaning: this supplier supplies this part to this project

  Business rule that creates the join dependency:
    IF  a supplier supplies a part (anywhere)
    AND that part is used by a project
    AND that supplier supplies that project (any part)
    THEN that supplier supplies that part to that project

  supplier | part  | project
  ---------+-------+--------
  S1       | Bolt  | P1
  S1       | Nut   | P2
  S2       | Bolt  | P2

  Apply the rule to the three rows:
    S1 supplies Bolt        (row 1)
    Bolt is used by P2      (row 3)
    S1 supplies to P2       (row 2)
    -> therefore S1 supplies Bolt to P2 MUST also be true

  So the row  S1 | Bolt | P2  is IMPLIED, not independent.
  The relation contains a redundancy that no functional or
  multivalued dependency describes.

  DECOMPOSE INTO THREE

    SP ( supplier, part )     PJ ( part, project )
       S1 Bolt                   Bolt P1
       S1 Nut                    Nut  P2
       S2 Bolt                   Bolt P2

    SJ ( supplier, project )
       S1 P1
       S1 P2
       S2 P2

  Joining ALL THREE reconstructs the original exactly.
  Joining any TWO produces spurious rows.

  That is the signature of 5NF: it is decomposable into
  three or more relations, but not into two.

The full ladder

In practice a design that reaches BCNF is almost always in 4NF and 5NF already. The two higher forms are examined far more often than they are needed — but the 4NF case, an entity with two independent multivalued attributes, does occur and is worth recognising.

Spotting a 4NF violation in real design

  Warning sign: one relation storing two lists that have
  nothing to do with each other.

  EMPLOYEE_INFO ( emp_id, skill, language )
  DOCTOR_INFO   ( doctor, specialisation, clinic_day )
  PRODUCT_INFO  ( product, colour, size )

  Ask: does choosing one value of A constrain the choice of
  B in any way?
    NO  -> they are independent, split them
    YES -> they belong together, keep them

  A shirt available in red only in large IS a real
  constraint, so ( product, colour, size ) may be correct.
  A doctor whose specialisation has nothing to do with which
  days they attend is NOT, so split it.

Common mistakes

• Splitting attributes that are not independent. If the combination carries meaning, splitting loses information.
• Thinking a two attribute relation can violate 4NF. It cannot; every MVD in it is trivial.
• Confusing a multivalued dependency with a multivalued attribute. The attribute problem is 1NF; the dependency problem is 4NF.
• Decomposing a 5NF violation into two relations. It needs three or more, by definition.
• Chasing 5NF on ordinary schemas. Confirm the join dependency exists as a real business rule first.

Exam and interview questions

1. Define a multivalued dependency and give an example with the row explosion it causes.
2. Define 4NF and decompose a violating relation.
3. Why is every relation with two attributes automatically in 4NF?
4. Define a join dependency and explain the supplier, part, project example.
5. Define 5NF and state what distinguishes it from 4NF.
6. Why are 4NF and 5NF rarely needed in practice?

Practice

1. COURSE_INFO ( course, instructor, textbook ) where instructors and textbooks are independent. Test 4NF and decompose.
2. A student has multiple phone numbers and multiple email addresses. Design it in 4NF.
3. Explain why ( product, colour, size ) might legitimately stay as one relation.
4. Verify by hand that joining any two of SP, PJ and SJ produces a spurious row.

Conclusion

4NF removes independent multivalued facts crammed into one relation; 5NF removes join dependencies that only a three way split can eliminate. Both are worth recognising, and both are usually already satisfied once a design reaches BCNF.