Join Dependencies and the Ternary Structure Fifth Normal Form Protects

Fourth normal form handles constraints that force a relation to be a cross product of two independent groups. There is a third case: a relation that is the join of three projections and not of any two, because the constraint that makes it decomposable is genuinely ternary. Such a relation is in fourth normal form by every test, has no binary decomposition that reconstructs it, and still contains a specific redundancy. Join dependencies express this constraint, and fifth normal form is the condition that no nontrivial one remains.

A constraint that three relations express and two cannot

Consider a relation recording which combinations of supplier, part, and project are permitted:

Supply(supplier, part, project)

The rule is not that suppliers, parts, and projects are independent. The rule is a cyclic one: if a supplier supplies a part, and that part is used by a project, and that supplier supplies that project, then the supplier supplies that part to that project. A triple is legal only when all three of its pairs are legal.

Suppose the relation holds four legal triples: (S1,P1,J1), (S1,P1,J2), (S1,P2,J2), and (S2,P1,J2). Take the three binary projections:

• SP(supplier, part) = {(S1,P1), (S1,P2), (S2,P1)}
• PJ(part, project) = {(P1,J1), (P1,J2), (P2,J2)}
• SJ(supplier, project) = {(S1,J1), (S1,J2), (S2,J2)}

Joining all three on their shared attributes produces exactly those four triples and no others, because each candidate triple must have all three of its pairs present in the corresponding projection. That equality is the constraint: the relation equals the join of its three binary projections, and no pair of projections would do. Joining only SP and PJ on part yields five triples: the four legal ones plus the spurious (S2,P1,J1), which pairs S2 with project J1 although S2 works on no such project. The third projection SJ exists to reject exactly that triple.

Written as a join dependency:

*( {supplier, part}, {part, project}, {supplier, project} )

This is the cycle dependency, and it is the canonical example. Note that it is not implied by any multivalued dependency. If supplier →→ {part, project} held, then for a fixed supplier every part would combine with every project, and the relation would be a cross product — but the relation above has (S1,P1,J1) and (S1,P2,J2) without (S1,P1,J2), so no such MVD holds. The constraint is genuinely ternary: it involves three attribute groups in a cycle, and no pair of them determines the third.

Formal statement and the relationship to MVDs

A join dependency *(R1, …, Rk) holds in relation R when R = R1 ⨝ R2 ⨝ … ⨝ Rk, where each Ri is understood as the projection of R onto the attributes of Ri. The union of the Ri must be all attributes of R; otherwise the join could not reproduce R.

Two special cases connect the definition to what is already known. For k = 2, *(R1, R2) is exactly the statement that R is the join of two projections, which holds precisely when the MVD (R1 ∩ R2) →→ R1 holds. So binary join dependencies and multivalued dependencies are the same constraint in different notation, which is why 4NF can be defined in terms of MVDs without loss.

For k = |attrs(R)|, with each Ri a single attribute, the dependency asserts that R is the join of its unary projections, which is the condition that R is a cross product of its attribute domains. This is the extreme case of independence and is rarely intended.

A join dependency is trivial when one of the Ri equals all attributes of R, since then the join is just that projection and the condition holds automatically.

The important structural fact: join dependencies are strictly more expressive than MVDs, and the implication problem for them is harder. A set of MVDs implies an MVD if and only if the chase on a two-row tableau succeeds, and that test is polynomial. For join dependencies, deciding implication is NP-complete. The reason is that the chase for a join dependency must consider subsets of the projections in combination, and the number of candidate combinations grows combinatorially.

Fifth normal form and what it eliminates

A relation is in fifth normal form — also called projection-join normal form — when every nontrivial join dependency that holds in it is implied by its candidate keys. That is, for every *(R1, …, Rk) holding in R, some Ri must be a superkey of R.

The Supply relation is not in 5NF: the cycle dependency holds, and none of {supplier, part}, {part, project}, {supplier, project} is a superkey, since the only candidate key is the full triple.

The decomposition is into exactly the three projections:

SP(supplier, part)
PJ(part, project)
SJ(supplier, project)

This decomposition is lossless by the join dependency itself — that is what the dependency asserts. It is also dependency-preserving in a sense that has no 3NF analogue: the constraint that the original triples were legal is now enforced by the three relations jointly, because a triple can only be reconstructed by joining rows that all exist. Inserting (S1,P2,J1) into the join would require (S1,P2) in SP, (P2,J1) in PJ, and (S1,J1) in SJ — and if all three exist, the triple is legal by the cyclic rule. The three binary relations are the constraint.

That is the distinguishing property of 5NF decomposition: the constraint is not lost, it is redistributed. Compare the BCNF case in Boyce-Codd normal form and the cost of losing a dependency, where a functional dependency spanning two relations becomes unenforceable. Here the join dependency becomes three relations whose joint existence is the enforcement mechanism.

The cost is on the read side. Reconstructing Supply requires a three-way join, and the join is not free: with n rows in each relation the join can produce up to n² intermediate tuples before the third relation filters them, and the result is only the legal triples. In a schema where the full triple is queried constantly, the 5NF decomposition trades write-time consistency for read-time joining.

Why pairwise tests miss it

The trap in the Supply example is that no binary decomposition of it is lossless, and none of them is obviously wrong either. Splitting into SP and SJ intersects on {supplier}, and the split is lossless only if supplier →→ {part, project} holds — it does not, so the split is lossy and the two relations still permit spurious combinations. Splitting into SP and PJ intersects on {part}, and no MVD holds there either. Splitting into PJ and SJ intersects on {project}, with the same outcome.

So a designer who tests each pair, finds no MVD, and concludes the relation is fully normalized has missed the ternary constraint entirely. The relation is in 4NF by the MVD test — there are no nontrivial MVDs — and yet it has the redundancy the cycle dependency permits.

The redundancy is visible in the data: the fact “S1 supplies P1” is stored once in SP, but in the unnormalized relation it appears once per project that uses P1. With many projects per part, the same supplier-part pair is repeated many times, and a change to the pair requires updating every triple. The update anomaly is exactly the one 4NF handles, but the constraint driving it is invisible to the MVD test.

Spotting a join dependency

The mechanical test is the chase on a k-row tableau, but the practical question is how a designer comes to suspect one. Three patterns recur.

A ternary relationship with a cyclic rule. The Supply shape — three entities, pairwise relationships, and a rule that a triple is legal only when its pairs are. Whenever a schema records a three-way association and the business rule is stated in terms of pairs, the join dependency is a candidate.

A relation that no two-way split reconstructs. If every two-way decomposition is lossy yet the relation still contains repeated combinations, the constraint may be ternary or higher. The diagnostic is to look for a set of projections whose join reproduces the relation — which is the join dependency, stated constructively.

Redundancy that no FD or MVD explains. A relation with no nontrivial FDs beyond keys and no nontrivial MVDs can still contain repeated facts. If the repetition is systematic — the same pair appearing once per value of a third attribute — the constraint is a join dependency.

The negative test matters more than the positive one. Most relations with three attributes are not the join of their binary projections, because the cycle dependency is a strong condition that the data must satisfy exactly. A relation that merely happens to contain some legal triples does not satisfy it; the condition is equality with the join, for every legal instance, not for the current one.

-- Reconstruct the join and compare: if the counts differ, the
-- cycle dependency does not hold for the current contents.
SELECT (SELECT COUNT(*) FROM supply) AS stored,
       (SELECT COUNT(*)
          FROM sp NATURAL JOIN pj NATURAL JOIN sj) AS joined;

Equality is necessary but not sufficient evidence for the dependency — the current contents can coincide with the join without the constraint being intended. The designer’s judgement is what decides whether the equality reflects a rule of the domain or an accident of the data.

Where the ladder ends

Fifth normal form is the last of the classical normal forms defined over dependencies that are expressible as constraints on a single relation. Beyond it, the constraint classes leave the single-relation frame.

Domain-key normal form is stated differently: every constraint on the relation must be a consequence of the domain constraints and the key constraints, where a domain constraint is a constraint on a single attribute. It is a condition on the set of all constraints, not on a dependency type, and it is not decidable in general — deciding whether an arbitrary constraint follows from a set of dependencies is undecidable once the constraint language is rich enough.

Sixth normal form takes the opposite direction from the ladder: rather than decomposing to remove redundancy, it decomposes until every relation consists of a key plus at most one non-key attribute, which removes the possibility of update anomalies entirely at the cost of a relation per attribute — described in sixth normal form and attribute-level decomposition.

The reason the ladder stops where it does is a complexity boundary, not a loss of imagination. Deciding 5NF requires deciding join-dependency implication, which is NP-complete. Deciding conditions beyond that requires constraint languages whose implication problem is undecidable. Normalization is tractable exactly up to the point where the constraint language is restricted to FDs and MVDs, and the tools that automate it — the closure computation of attribute closure and the mechanical derivation of candidate keys and the chase of the chase as a general test for dependency implication — work because of that restriction, not despite it.

A schema in 5NF is not necessarily better than one that is not. The three-way decomposition of Supply is correct by the theory and expensive in every query that needs the triple. The engineering decision is whether the update anomaly the cycle dependency permits is worth the join, and the answer depends on the ratio of writes to reads and on how often the repeated pair actually changes.