Multivalued Dependencies and Fourth Normal Form

Learning outcomes

Fourth Normal Form (4NF) addresses redundancy caused not by ordinary functional dependencies, but by multivalued dependencies. This occurs when one entity has two or more independent many-valued facts stored in the same relation.

A motivating example

Suppose each Technician may have many skills and many spoken languages, and these two sets are independent:

TechnicianFact(  technician_id,  skill_code,  language_code)

Cross-product redundancy

If technician 17 has:

Skills: welding, diagnosticsLanguages: English, German, Persian

the relation needs six rows:

17 welding     English17 welding     German17 welding     Persian17 diagnostics English17 diagnostics German17 diagnostics Persian

The facts are independent

The fact “Technician 17 knows welding” does not depend on which language row it is paired with. Likewise, language knowledge is independent of skill knowledge.

Multivalued dependency notation

We write:

\[ technician\_id \twoheadrightarrow skill\_code \]

and:

\[ technician\_id \twoheadrightarrow language\_code \]

to say that each technician determines a set of skills and independently determines a set of languages.

Why ordinary FDs do not capture this

Technician does not functionally determine one skill:

technician_id -/-> skill_code

because each technician can have many skills. The dependency is set-valued rather than single-valued.

The 4NF rule

A relation is in 4NF when for every non-trivial multivalued dependency:

\[ X \twoheadrightarrow Y \]

X is a superkey.

4NF decomposition

Split the independent facts:

TechnicianSkill(  technician_id,  skill_code)TechnicianLanguage(  technician_id,  language_code)

Now each fact is stored once.

WorkshopHub example

Suppose Part has many compatible equipment models and many approved suppliers, independently:

PartCompatibilitySupplier(  part_id,  model_id,  supplier_id)

If every approved supplier can supply the part regardless of compatible model, the relation repeats every supplier for every model.

Correct decomposition

PartCompatibleModel(part_id, model_id)PartApprovedSupplier(part_id, supplier_id)

When the facts are not independent

If Supplier A supplies a part only for Model X, while Supplier B supplies it only for Model Y, then the triple has joint meaning. The multivalued facts are not independent, so decomposing into two pairwise relations would invent false combinations.

Independence is a business rule

4NF depends on semantics. You cannot infer independence solely because a relation has three columns.

Another example: Employee projects and dependents

If an Employee participates in many Projects and has many Dependents, and these are independent sets, a table:

EmployeeProjectDependent(  employee_id,  project_id,  dependent_id)

contains unnecessary combinations.

4NF versus 1NF

1NF eliminates repeating groups inside a row. 4NF handles a subtler case where the repeating values are already rows but independent sets are combined into one relation.

4NF versus M:N associative entities

An associative entity such as WorkOrderAssignment is not a 4NF problem merely because both sides are many. 4NF problems arise when multiple independent multivalued relationships are stored in one relation.

Practice: independent or joint?

Summary and next lesson

4NF separates independent multivalued facts so their Cartesian combinations are not redundantly stored. The next lesson moves one level further to join dependencies and Fifth Normal Form, where redundancy can remain even without ordinary functional or multivalued dependency violations.

References

• Ronald Fagin, foundational work on multivalued dependencies and Fourth Normal Form.
• C. J. Date, Database Design and Relational Theory.
• Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems.