Multivalued Dependencies and the Redundancy BCNF Cannot See

A relation can satisfy every functional dependency that a designer would declare, be in Boyce-Codd normal form by every test, and still store the same fact several times. The cause is a different kind of constraint: an attribute set determining a set of values rather than a single value. Functional dependencies cannot express this, so they cannot detect the redundancy it creates. Multivalued dependencies were introduced to make the constraint explicit, and fourth normal form is the condition that no such constraint is left embedded in a wider relation.

Independence is the constraint

Take a relation recording which employees work on which projects and which skills each employee has:

Assignment(employee, project, skill)

Neither project assignment nor skill possession depends on the other. If an employee works on three projects and holds four skills, the relation contains all twelve combinations — not because any pair of facts requires the others, but because the relation has no way to record one without the other.

The constraint is written employee →→ project, read “employee multivalued-determines project,” and it asserts: if tuples t1 and t2 agree on employee, then there is a tuple t3 that agrees with t1 on employee and project and with t2 on all remaining attributes. In the three-attribute case this says that for a fixed employee, the set of projects is independent of the set of skills: every project appears with every skill.

The formal definition for arbitrary attribute sets: X →→ Y holds in R when, for every pair of tuples t1, t2 with t1[X] = t2[X], there exists a tuple t3 with t3[X] = t1[X], t3[Y] = t1[Y], and t3[R − X − Y] = t2[R − X − Y]. Note that t3 is required to exist, so the constraint is a closure condition on the relation, not a statement about any two tuples.

Every functional dependency is a multivalued dependency: if X → Y holds, the set of Y values for a given X has exactly one member, and the independence condition is trivially satisfied. The converse is false, and that asymmetry is the whole point — MVDs are strictly more expressive than FDs, and a schema can be in BCNF while violating a nontrivial MVD.

Two degenerate cases are worth naming. X →→ Y is trivial when Y ⊆ X or X ∪ Y = attrs(R); in both cases the constraint is satisfied by every relation and carries no information. And X →→ Y is equivalent to X →→ (R − X − Y), because the definition is symmetric in the two determined groups. This complementarity is used constantly: proving one MVD also proves its complement.

Why the redundancy is unavoidable in one relation

The Assignment relation with three projects and four skills per employee stores twelve rows to represent two independent lists. If a project is added, four rows must be inserted; if a skill is removed, four rows must be deleted. The relation’s cardinality for one employee is |projects| × |skills|, a product, while the information content is the sum of the two list lengths.

That multiplication is not an artifact of a poor schema choice within the same normal form — it is forced by the representation. A relation has a fixed degree, and every tuple is an atomic fact about the full attribute set. To record “employee 7 works on project A” without also committing to a skill, the relation would need a tuple in which the skill attribute holds something like “not applicable,” which is not a value in the skill domain. The only way to avoid the product is to reduce the degree, which means splitting the relation.

The redundancy is also the source of an update anomaly that BCNF does not catch. Suppose employee 7’s skill list changes from {typing, welding, soldering, drafting} to {typing, welding, soldering}. Under the twelve-row representation, deleting the drafting skill requires deleting every row where skill = 'drafting' for employee 7 — three rows, one per project. A delete that removes only one of them leaves a relation in which the MVD no longer holds, because drafting now appears with some projects and not others. The relation has become inconsistent in a way that no functional dependency detects, since by assumption there are no nontrivial FDs beyond those implied by keys.

This is the precise sense in which the anomaly is invisible to BCNF: the constraint that is violated is not a functional dependency, so the normal form defined over FDs has nothing to say about it.

Fourth normal form and the decomposition

A relation is in fourth normal form when, for every nontrivial multivalued dependency X →→ Y that holds in it, X is a superkey. The condition mirrors BCNF with MVDs substituted for FDs.

For Assignment, employee →→ project is nontrivial and employee is not a superkey, so the relation is not in 4NF. The decomposition follows the dependency directly: split into a relation for X ∪ Y and a relation for X ∪ (R − X − Y).

EmployeeProject(employee, project)
EmployeeSkill(employee, skill)

The result is lossless by construction, and the reason is worth stating precisely. The two relations intersect on employee. The join of EmployeeProject and EmployeeSkill on that attribute produces exactly the original relation because the MVD held: for each employee, every project combines with every skill, which is what the cross product of the two lists gives. If the MVD had not held — if some project appeared only with some skills — the join would produce tuples that were not in the original, and the decomposition would be lossy. So the MVD is simultaneously the justification for the decomposition and the guarantee that it is lossless.

Dependency preservation is a subtler question. FDs in the original relation are preserved if each one’s attributes fit inside one of the new relations. In this example there are no nontrivial FDs, so the question is vacuous. In general, 4NF decomposition preserves FDs when the FDs are compatible with the MVD-driven split, and a schema can lose an FD by decomposing for 4NF — the same trade described for BCNF in Boyce-Codd normal form and the cost of losing a dependency, now with a second constraint class competing for the same attribute placement.

The synthesis path to 4NF is less tidy than the 3NF synthesis algorithm. There is no analogue that constructs a 4NF decomposition directly from a mixed set of FDs and MVDs while guaranteeing both properties; the standard approach is to decompose repeatedly on violating dependencies until none remain, and the result depends on the order in which violations are chosen.

Checking an MVD without enumerating tuples

Testing whether X →→ Y holds in a relation instance is not a scan-and-compare over all pairs — that would be quadratic in the relation size and would still only test the instance, not the constraint. The correct test is the chase, applied to a two-row tableau: place one row with distinguished variables for X ∪ Y and a second row agreeing on X but differing elsewhere, then apply the dependencies until either the tableau collapses or it does not. The MVD is implied when the chase forces the two rows to agree on Y.

There is a shortcut for the common case: X →→ Y holds in a relation whose only dependencies are FDs and MVDs if and only if the chase on the appropriate tableau succeeds, and for schemas with a single MVD the test reduces to checking the definition directly on the relation. The general implication problem for MVDs alone is decidable in polynomial time — unlike the implication problem for join dependencies, which is NP-complete.

-- Violations of employee →→ project, if any: for each employee,
-- the set of projects paired with each skill must be identical.
SELECT e.employee
FROM assignment AS e
GROUP BY e.employee
HAVING COUNT(DISTINCT e.project) * COUNT(DISTINCT e.skill)
     <> COUNT(*);

The query compares the product of the two distinct counts against the row count for each employee. Equality means the full cross product is present, which is the MVD holding for that employee. The check is a full scan with a grouping, so it is a diagnostic for a suspect table, not something to run as a constraint on every write. Note also that it detects violation of the independence condition, not the presence of the MVD — a table can satisfy the condition on its current contents while the constraint is not intended to hold.

Where multivalued constraints come from

The canonical source is two independent one-to-many relationships recorded in the same relation. A product with multiple suppliers and multiple certifications; a course with multiple instructors and multiple textbooks; a patient with multiple diagnoses and multiple medications. In each case, the two lists are genuinely independent — no rule says that supplier A only supplies certified products — and combining them in one relation multiplies the rows.

The diagnostic question is whether the two lists are independent or merely correlated. If every product from supplier A is always certified under the same scheme, the constraint is not an MVD but a more complex dependency, and splitting on the assumption of independence produces a schema that permits combinations the domain forbids. That is the failure mode of over-eager 4NF: the decomposition is lossless with respect to the stated MVD, but the stated MVD was wrong, and the split has removed the relation’s ability to express the correlation.

A relation with a nontrivial MVD that is not implied by its FDs and where the MVD is not intended is also possible — the data happens to exhibit the cross product by coincidence. In that case the relation is not in 4NF by the formal test, but the decomposition would impose an independence claim that the domain does not make. The formal test cannot distinguish coincidence from constraint; only the designer can.

Fifth normal form generalizes the same idea from two independent groups to three or more, using join dependencies, and the chase becomes the only practical test — see join dependencies and fifth normal form. The step from 4NF to 5NF is where the constraint language stops being tractable, and that boundary is examined in inclusion dependencies and the limits of implication.