Chapter 24 of 41

4NF & 5NF

By the end of the BCNF chapter, every functional dependency in our tables had a key on its left side. All redundancy caused by FDs was gone.

But FDs are not the only kind of rule data can follow. Some tables are in BCNF, have no non-trivial FDs at all, and still store the same fact again and again.

The higher normal forms deal with two other kinds of dependencies:

  • Fourth Normal Form (4NF) deals with multivalued dependencies (MVDs): two independent lists of facts stored in one table.

  • Fifth Normal Form (5NF) deals with join dependencies (JDs): a table that can only be split safely into three or more pieces.

These situations are rarer than 2NF/3NF problems, but they are popular in interviews and GATE because they test whether you really understand why normalization works.


A Table in BCNF That Still Has Redundancy

A company records which skills each employee has and which languages each employee speaks. The two facts have nothing to do with each other: knowing Java has no connection to speaking Hindi.

Someone puts both into one table:

CREATE TABLE emp_skill_lang (
  emp      VARCHAR(10),
  skill    VARCHAR(10),
  language VARCHAR(10),
  PRIMARY KEY (emp, skill, language)
);

INSERT INTO emp_skill_lang VALUES
('Anil','Java','English'), ('Anil','Java','Hindi'),
('Anil','SQL','English'),  ('Anil','SQL','Hindi');

SELECT * FROM emp_skill_lang ORDER BY skill, language;

Output:

+------+-------+----------+
| emp  | skill | language |
+------+-------+----------+
| Anil | Java  | English  |
| Anil | Java  | Hindi    |
| Anil | SQL   | English  |
| Anil | SQL   | Hindi    |
+------+-------+----------+

Anil has 2 skills and speaks 2 languages, so the table needs 2 × 2 = 4 rows. Why every combination? Because if we stored only (Anil, Java, English) and (Anil, SQL, Hindi), it would look as if Anil speaks English only "for Java", which means nothing. Since the facts are independent, the only consistent way to store them together is to pair every skill with every language.

Is this table in BCNF?

Does emp → skill hold? No, Anil has two skills. Does emp → language hold? No. In fact, no non-trivial FD holds at all. The only key is (emp, skill, language), so the table is trivially in BCNF.

And yet…

  • "Anil knows Java" is stored twice (once per language). "Anil speaks Hindi" is stored twice (once per skill).

  • When Anil learns Python, we must insert two rows: (Anil, Python, English) and (Anil, Python, Hindi). Insert only one and the table now claims a weird link between Python and a specific language (an update/insert anomaly).

  • If Anil learns a third language, we need one new row per skill.

With 5 skills and 4 languages, Anil needs 20 rows to store 9 facts. The rule causing this is a multivalued dependency.


Multivalued Dependency (MVD)

We write a multivalued dependency with a double arrow:

emp →→ skill        "emp multi-determines skill"
emp →→ language

Informally:

X →→ Y means: for each value of X there is a set of Y values, and that set is independent of the values of the remaining attributes.

For Anil, the set of skills is {Java, SQL} no matter which language we look at.

Formal Definition

Let R be a relation schema, X and Y subsets of R, and Z = R − X − Y. Then X →→ Y holds on R if, in every legal instance, whenever two tuples t1 and t2 agree on X, there is also a tuple t3 such that:

  • t3[X] = t1[X] = t2[X]

  • t3[Y] = t1[Y]

  • t3[Z] = t2[Z]

(Applying the same rule with t1 and t2 swapped gives the symmetric tuple t4.) In words: you can swap the Y part between two tuples with the same X, and the result must also be in the table.

Check it on our data. Take t1 = (Anil, Java, English) and t2 = (Anil, SQL, Hindi). For emp →→ skill, the swapped tuple t3 = (Anil, Java, Hindi) must exist. It does. Try every pair and you'll always find the swapped tuple: that is what the "every combination" pattern means.

Important Properties

Property

Statement

Trivial MVD

X →→ Y is trivial if Y ⊆ X or X ∪ Y = R. It holds in every relation.

Complementation

If X →→ Y, then X →→ R − X − Y. (emp →→ skill implies emp →→ language.) So MVDs come in pairs.

Every FD is an MVD

If X → Y, then X →→ Y (the "set" of Y values for each X has exactly one element).

Lossless split (Fagin)

R decomposes losslessly into (X ∪ Y) and (X ∪ Z) if and only if X →→ Y (equivalently X →→ Z) holds.

The last property is the important one: an MVD is exactly the condition that lets you split a table into two pieces that join back perfectly. It generalizes the FD-based test you will see in Lossless Join & Dependency Preservation.

MVD vs Multivalued Attribute

Do not confuse these. A multivalued attribute (from the Types of Attributes chapter) is an ER-level idea: one entity has many phone numbers. 1NF handles it by moving it to a separate table. An MVD is a constraint between columns of a relation that already is in 1NF. MVD problems typically appear when two multivalued attributes of the same entity end up in the same table.


Fourth Normal Form (4NF)

A relation R is in 4NF if, for every non-trivial multivalued dependency X →→ Y that holds on R, X is a superkey of R.

Look how similar this is to BCNF. The only change is → became →→. Since every FD is also an MVD, a 4NF relation automatically satisfies the BCNF condition:

4NF  ⊂  BCNF  ⊂  3NF  ⊂  2NF  ⊂  1NF

Checking emp_skill_lang

  • emp →→ skill is non-trivial: skill ⊄ {emp}, and {emp, skill} ≠ R.

  • Is emp a superkey? No, the only key is (emp, skill, language).

So the table is in BCNF but not in 4NF.

Decomposing into 4NF

Split on the violating MVD X →→ Y into (X ∪ Y) and (X ∪ (R − X − Y)):

emp_skill_lang(emp, skill, language)
        │  split on emp →→ skill
        ├──→ emp_skill(emp, skill)
        └──→ emp_language(emp, language)

emp_skill

emp

skill

Anil

Java

Anil

SQL

emp_language

emp

language

Anil

English

Anil

Hindi

Now each fact is stored once. Anil learning Python is one row in emp_skill. And because emp →→ skill holds, joining the two tables on emp gives back exactly the original four rows (Fagin's property). In each new table, the only MVDs left are trivial (two attributes, X ∪ Y = R), so both are in 4NF.

The general algorithm is the same as BCNF decomposition: while some table has a non-trivial MVD X →→ Y with X not a superkey, split it into (X ∪ Y) and (R − (Y − X)), that is, X together with everything else. Each split is lossless.

When Is It NOT an MVD?

The MVD exists only because skills and languages are independent. Change the meaning, and it disappears.

Suppose the table instead records "which language an employee can teach each skill in". Anil might teach Java in Hindi and English, but SQL only in English:

emp

skill

teaching_language

Anil

Java

English

Anil

Java

Hindi

Anil

SQL

English

Here the row (Anil, SQL, Hindi) is legitimately absent, so emp →→ skill does not hold. This table is in 4NF, and splitting it would be wrong: the join would invent "Anil teaches SQL in Hindi".

Whether an MVD holds is a fact about the real world, not about the current rows. You decide it from the meaning of the data.


Join Dependency (JD)

4NF handles tables that split into two pieces. Occasionally a table cannot be split into any two pieces without spurious rows, yet it can be split into three. This is captured by a join dependency.

A join dependency *(R1, R2, …, Rn) holds on R if every legal instance r of R equals the natural join of its projections: r = πR1(r) ⋈ πR2(r) ⋈ … ⋈ πRn(r).

  • A JD is trivial if one of the Ri is R itself.

  • An MVD X →→ Y is just the special case with two pieces: *(X ∪ Y, X ∪ Z).

Example: Agents, Companies and Products

A sales agency has this business rule (a cyclic rule):

If an agent represents a company, and that company makes a product, and the agent sells that type of product, then the agent sells that product for that company.

Current data:

CREATE TABLE agent_company_product (
  agent   VARCHAR(10),
  company VARCHAR(10),
  product VARCHAR(10),
  PRIMARY KEY (agent, company, product)
);

INSERT INTO agent_company_product VALUES
('Ravi','Tata','Car'), ('Ravi','Tata','Truck'),
('Ravi','Mahindra','Truck'), ('Meena','Tata','Truck');

-- the three two-column projections
CREATE TABLE agent_company   AS SELECT DISTINCT agent, company   FROM agent_company_product;
CREATE TABLE company_product AS SELECT DISTINCT company, product FROM agent_company_product;
CREATE TABLE agent_product   AS SELECT DISTINCT agent, product   FROM agent_company_product;

The three projections contain:

agent_company        company_product       agent_product
---------------      ----------------      -------------
Ravi   Tata          Tata      Car         Ravi   Car
Ravi   Mahindra      Tata      Truck       Ravi   Truck
Meena  Tata          Mahindra  Truck       Meena  Truck

Two pieces are not enough

Let's join just agent_company and company_product:

SELECT ac.agent, ac.company, cp.product
FROM agent_company ac
JOIN company_product cp ON cp.company = ac.company
ORDER BY 1, 2, 3;

Output:

+-------+----------+---------+
| agent | company  | product |
+-------+----------+---------+
| Meena | Tata     | Car     |
| Meena | Tata     | Truck   |
| Ravi  | Mahindra | Truck   |
| Ravi  | Tata     | Car     |
| Ravi  | Tata     | Truck   |
+-------+----------+---------+

5 rows instead of 4. (Meena, Tata, Car) is spurious: Meena does not sell cars. The other two pairs fail too: joining agent_company with agent_product invents (Ravi, Mahindra, Car), and joining company_product with agent_product invents (Meena, Mahindra, Truck). So no two-way split works, and therefore no non-trivial MVD holds: the table is in 4NF.

Three pieces work

Now join all three:

SELECT ac.agent, ac.company, cp.product
FROM agent_company ac
JOIN company_product cp ON cp.company = ac.company
JOIN agent_product ap   ON ap.agent = ac.agent AND ap.product = cp.product
ORDER BY 1, 2, 3;

Output:

+-------+----------+---------+
| agent | company  | product |
+-------+----------+---------+
| Meena | Tata     | Truck   |
| Ravi  | Mahindra | Truck   |
| Ravi  | Tata     | Car     |
| Ravi  | Tata     | Truck   |
+-------+----------+---------+

Exactly the original 4 rows. The third table removed the spurious row because Meena does not appear with Car in agent_product.

This is no coincidence. The business rule says that a row (a, c, p) exists exactly when (a, c), (c, p) and (a, p) all exist, which is precisely the join dependency:

*( {agent, company}, {company, product}, {agent, product} )

And it causes redundancy in the single table: the row (Ravi, Tata, Truck) is forced by the other facts. Insert the facts "Ravi represents Tata", "Tata makes Trucks" and "Ravi sells Trucks" in any form, and the single table must also contain that row, or it violates the rule.


Fifth Normal Form (5NF)

A relation R is in 5NF (also called Project-Join Normal Form, PJNF) if every non-trivial join dependency that holds on R is implied by the candidate keys of R.

"Implied by the candidate keys" means the JD exists only because of keys, for example splitting student(roll_no, name, dept) into (roll_no, name) and (roll_no, dept). Such splits are always lossless, but they don't remove any redundancy, so they are harmless.

In practical terms:

A table is in 5NF if it cannot be split into smaller tables without either losing information or splitting along a key.

agent_company_product has the JD above, its only key is all three attributes, and none of the three pieces is a superkey. So it is in 4NF but not in 5NF. The 5NF design is the three tables:

agent_company(agent, company)
company_product(company, product)
agent_product(agent, product)

Each fact is stored once, and the rule is now automatic: the agency's offerings are simply the three-way join.

A word of caution

If the cyclic business rule does not hold (for example, Ravi sells cars for Tata but has chosen not to sell trucks for Tata even though he sells trucks for Mahindra), then the three-way join would produce wrong rows. Then the JD doesn't hold and the single table is already in 5NF. As with MVDs, the decision depends on the business rule, not on a lucky sample of data.


The Complete Normal Form Ladder

Normal form

Dependency it looks at

Condition

1NF

—

Atomic values

2NF

FD

No non-prime attribute depends on part of a key

3NF

FD

X → A: X superkey or A prime

BCNF

FD

X → Y: X superkey

4NF

MVD

X →→ Y (non-trivial): X superkey

5NF

JD

Every non-trivial JD is implied by candidate keys

Each step is stricter than the previous one. Beyond 5NF, textbooks also mention Domain-Key Normal Form (DKNF) and 6NF (used for temporal data), but they rarely appear in university exams or placements.

4NF vs 5NF at a glance

4NF

5NF

Problem

Two independent multi-valued facts in one table

A cyclic rule linking three (or more) facts

Dependency

MVD (X →→ Y)

JD *(R1, …, Rn), n ≥ 3 in interesting cases

Decomposition

Into 2 tables

Into 3 or more tables

How common

Occasional

Rare

Example

emp, skill, language

agent, company, product


Common Mistakes

  • Thinking BCNF means "fully normalized". BCNF only covers FD redundancy. MVD and JD redundancy can remain.

  • Spotting an MVD from sample data alone. A few rows may look like "every combination" by accident. MVDs come from the meaning of the data.

  • Forgetting complementation. If X →→ Y holds, then X →→ R − X − Y also holds.

  • Confusing MVDs with multivalued attributes. They are related but not the same thing.

  • Splitting a 3-attribute table into two just because it has no FDs. If no two-way split is lossless, splitting into two is wrong (the table may need three pieces, or none). Check with the join.

  • Over-normalizing. Decomposing into 5NF when the cyclic rule does not actually hold produces wrong answers.


Interview Questions

What is a multivalued dependency?

X →→ Y holds if, for each value of X, the set of associated Y values is independent of the other attributes. Equivalently, swapping the Y part between any two tuples with the same X gives tuples that are also in the relation.

Define 4NF.

A relation is in 4NF if for every non-trivial MVD X →→ Y, X is a superkey.

Why does 4NF imply BCNF?

Every FD X → Y is also an MVD X →→ Y. If every non-trivial MVD has a superkey on the left, then every non-trivial FD does too.

Give an example of a table in BCNF but not in 4NF.

(emp, skill, language) where skills and languages are independent. No non-trivial FDs exist (BCNF), but emp →→ skill holds and emp is not a superkey.

What is a join dependency and what is 5NF?

A JD *(R1, …, Rn) says the relation always equals the join of its projections on R1…Rn. A relation is in 5NF if every non-trivial JD is implied by its candidate keys, so it cannot be decomposed further without losing information (apart from harmless splits along a key, which remove no redundancy).

When is a decomposition into (X ∪ Y) and (X ∪ Z) lossless, with Z = R − X − Y?

Exactly when X →→ Y holds (Fagin's theorem).


Summary

  • BCNF removes FD-based redundancy, but tables can still be redundant because of MVDs and JDs.

  • MVD X →→ Y: the set of Y values for each X is independent of the rest of the row. Trivial if Y ⊆ X or X ∪ Y = R.

  • 4NF: every non-trivial MVD has a superkey on the left. Fix by splitting into (X ∪ Y) and (X ∪ rest).

  • JD: the table equals the join of several projections. An MVD is a two-piece JD.

  • 5NF: every non-trivial JD follows from the keys. Fix by splitting into the JD's components, often three tables.

  • Both MVDs and JDs come from business rules, so always reason from meaning, not from sample rows.

4NF: don't store independent lists together. 5NF: don't store a fact that can be derived from three smaller facts.