Inclusion Dependencies and the Undecidability That Follows Them

A foreign key is a special case of a more general constraint: the projection of one relation onto a set of attributes is a subset of the projection of another. Written R[X] ⊆ S[Y], this is an inclusion dependency, and it is the constraint class that expresses everything from referential integrity to subtype hierarchies to coverage requirements such as “every department has at least one manager.” Its theory is unlike the theory of functional and multivalued dependencies in two ways: the objects involved are relations rather than attributes, so no closure computation applies; and the decision problems it raises range from tractable to undecidable depending on what it is combined with.

From foreign keys to general subset constraints

The foreign key constraint of referential integrity and the semantics of foreign key actions is the instance where Y is a key of S. The inclusion dependency formulation drops that requirement: R[X] ⊆ S[Y] asserts that every tuple of R, projected onto X, appears in the projection of S onto Y, and imposes no uniqueness condition on either side.

Dropping the key requirement is what makes the class useful. Three constraint shapes that a foreign key cannot express become expressible:

Coverage. Every department must appear as somebody’s department: department[id] ⊆ employee[dept_id]. This is an inclusion dependency in the direction opposite to a foreign key, and it cannot be enforced by a per-row check on either table — inserting a department requires that a matching employee exists, which is a check against the other table at insert time, but the constraint is also violated by deleting the last employee of a department. A foreign key enforces existence of a parent; this enforces existence of a child.

Subtyping. Every manager is an employee: manager[id] ⊆ employee[id]. The inclusion is over the same attribute name but different relations, and the two relations may have different degrees. This is the constraint that makes a table-per-subtype design coherent.

Equality. A relation’s attribute set equals another’s, expressed as two inclusions in opposite directions: R[X] ⊆ S[Y] and S[Y] ⊆ R[X]. Equality constraints arise when the same fact is recorded in two places by design, such as a denormalized summary and its detail table.

The theory permits X and Y of different lengths, but a shorter target makes the constraint unsatisfiable whenever the source projection has at least one tuple, so useful inclusions have equal arity. The correspondence between positions then matters: R[A, B] ⊆ S[C, D] pairs A with C and B with D. The pairing is positional, not by name, which is a detail that surprises people who expect attribute-name matching. SQL’s foreign key syntax names columns on both sides explicitly for this reason.

The chase must reason about values that do not exist yet

The chase described in the chase as a general test for dependency implication applies dependencies to a finite tableau of rows. Inclusion dependencies break that finiteness, and the break is the source of the whole theory’s difficulty.

Suppose F contains R[A] ⊆ S[B] and S[B] ⊆ T[C]. Testing whether F implies R[A] ⊆ T[C] requires a tableau with a row in R whose A value is a variable x. The first inclusion forces a row in S with B = x. The second forces a row in T with C = x. Both rows must be created by the chase, because neither exists in the initial tableau. The chase is now generating tuples rather than equating variables, and each generated tuple can trigger further inclusions.

For a chain of inclusions, the generated rows form a chain of finite length, and the chase terminates. For a cycle — R[A] ⊆ S[B] and S[B] ⊆ R[A] — the chase generates a row in S for the row in R, and then a row in R for the row in S, and so on. Nothing forces the generated row to be the same as the original, because a variable in an inclusion dependency is not forced to equal anything; it merely must appear somewhere.

Termination is recovered by noticing that the second generated R row is indistinguishable from the first: it has the same variable in A and the same (absent) values elsewhere. Adding it again changes nothing, so a chase that deduplicates rows by their variable content terminates on cycles. The standard formulation restricts the chase to distinguished variables in the target dependency and treats all other positions as wildcards, which collapses the cycle.

That collapse is sound for inclusions alone. It stops being sound when functional dependencies are present, because an FD can force two rows to agree on some attributes, which makes a previously indistinguishable row distinguishable — and then the cycle can produce a genuinely new row, and the process does not terminate.

Termination, and the loss of it

The classical result: the implication problem for inclusion dependencies alone is decidable, and in fact PSPACE-complete. The upper bound comes from bounding the chase, whose state can be explored in polynomial space; the lower bound comes from a reduction from quantified boolean satisfiability. The problem is therefore not efficient in the way that attribute closure is, but it is decidable, which is what matters for tooling.

The result for inclusion dependencies combined with functional dependencies is undecidable, established by Chandra and Vardi. The mechanism is worth understanding because it explains why no tool solves the general problem.

The reduction encodes a Turing machine’s computation as an instance of the constraint problem. Tuples represent tape cells and machine configurations; functional dependencies encode the determinism of the transition function — a state together with a read symbol determines the next state, the written symbol, and the head movement — while inclusion dependencies force the existence of the successor configuration’s tuples. Whether a particular inclusion is implied then coincides with whether the machine halts. Since halting is undecidable, so is implication.

The practical consequence is sharp: no algorithm decides, for an arbitrary schema with foreign keys and functional dependencies, whether a proposed constraint follows from the declared ones. A tool that appears to do so has restricted the dependency class — most often to acyclic inclusions, where the chase terminates — or has run a bounded search and reported failure to derive, which is a different answer from non-implication.

The acyclic restriction is the one that matters in practice. If the inclusion dependency graph has no cycles, the chase terminates in a number of steps bounded by the longest path, and implication is decidable by a straightforward procedure. A schema whose foreign keys form a hierarchy of tables with no mutual references is acyclic, and for it the procedure works. The schemas that defeat it are the ones with cycles.

Where cycles appear in real schemas

Mutual references are not exotic. Three patterns produce them routinely.

Self-references. An employee table with a manager_id referencing employee.id is a cycle of length one. The inclusion employee[manager_id] ⊆ employee[id] has the same relation on both sides. Under MATCH SIMPLE, nulls in manager_id exempt the top of the hierarchy, and the constraint is satisfiable. Without a nullable column every row must point at another row, so the hierarchy cannot have a root: the only legal instances are ones containing a management cycle, which no longer describes a hierarchy.

Mutual foreign keys. A department table with a head_id referencing employee, and an employee table with a dept_id referencing department. Each table’s rows require a row in the other. Inserting either first violates a constraint. The standard resolutions are to make one of the columns nullable, to defer one constraint to commit time, or to insert a placeholder row and update it — all three are workarounds for a schema whose constraint graph is cyclic.

Coverage plus reference. The coverage constraint department[id] ⊆ employee[dept_id] combined with the reference employee[dept_id] ⊆ department[id] is a two-way inclusion. The pair asserts a bijection at the level of value sets: every department has an employee, and every employee’s department exists. Enforcing it requires deferred checking, since neither table can be populated first.

Deferred checking is the mechanism SQL provides for these cases, and it is a real weakening: the constraint holds at commit, not at every statement. A transaction that temporarily violates it is legal, and a concurrent reader at a lower isolation level may observe the violation. The trade is between a schema that can be populated and one that is checked continuously.

Enforcing inclusions without a native constraint

Most systems do not offer a general inclusion dependency. SQL has foreign keys, CHECK constraints scoped to one row, and assertions — the standard’s CREATE ASSERTION construct, which is specified but unimplemented in the major open-source systems because checking an arbitrary predicate on every statement is expensive and hard to optimize.

The practical alternatives are triggers and materialized checks.

-- Enforce department[id] ⊆ employee[dept_id] on the employee side:
-- deleting or moving the last employee of a department is rejected.
CREATE TRIGGER department_coverage
AFTER DELETE ON employee
FOR EACH ROW
WHEN NOT EXISTS (
  SELECT 1 FROM employee WHERE dept_id = OLD.dept_id
)
AND EXISTS (
  SELECT 1 FROM department WHERE id = OLD.dept_id
)
BEGIN
  SELECT RAISE(ABORT, 'department would have no employees');
END;

This is SQLite’s trigger syntax; other systems differ in the body form but not in the structure. The trigger carries a concurrency hazard that a declarative constraint would not. Two transactions each delete one of a department’s two employees; each sees one remaining employee at the time of its own check, so neither aborts, and both commit, leaving a department with no employees. That is write skew, and it is invisible to snapshot isolation because neither transaction writes what the other reads. Serializable isolation prevents it, either by aborting one transaction or by taking predicate locks on the employee rows for the department.

Materializing the check is the other approach: maintain a table of departments with an employee count, updated by triggers, and constrain the count to be positive. The count is a derived value, and its maintenance is the same problem as maintaining any materialized aggregate — the triggers must fire on every relevant change, including changes made by bulk loads that bypass them.

What the constraint class buys and costs

The value of stating an inclusion dependency explicitly is that it makes a constraint that would otherwise live in application code into something the schema records. A reader of the schema can see that every department has an employee, rather than inferring it from the absence of a delete path in the service layer. That is the same argument for any declarative constraint, and it is strongest where the constraint spans relations, because that is where application-level enforcement is most easily bypassed.

The cost has three parts. Enforcement requires either a deferred check or a trigger with the concurrency hazard above. Implication testing is PSPACE-complete for inclusions alone and undecidable once functional dependencies are added, so no tool can say in general whether a proposed constraint is redundant or contradicts the declared ones. And the chase-based reasoning that makes FD and MVD theory tractable does not extend to the combined class.

The practical discipline is to keep the inclusion graph acyclic, to state inclusions explicitly where the system supports them, and to treat cyclic inclusions as a signal that the schema is encoding a mutual dependency that would be better represented by a single relation or by a nullable column. The cycle is not merely an enforcement inconvenience; it is a statement that neither entity can exist without the other, and that is usually a modelling error rather than a requirement.

The boundary of the decidable

The ladder of dependency classes and their decision problems forms a clean progression, and inclusion dependencies sit at its edge:

Constraint class	Implication problem
Functional dependencies	Polynomial (attribute closure)
FDs and MVDs	Polynomial
Join dependencies	NP-complete
Inclusion dependencies	PSPACE-complete
Inclusions and FDs	Undecidable

Each row’s complexity is the reason the corresponding normalization step is or is not automated. Third normal form synthesis runs on closure computations. Fourth normal form testing runs on the chase. Fifth normal form testing requires deciding join-dependency implication, which is NP-complete, so tools verify it only for small schemas. General inclusion reasoning has no tool at all.

The progression is not a defect in the theory but a property of the constraint languages. A constraint language expressive enough to state “every department has an employee” and also interact with functional dependencies is expressive enough to encode computation. The restriction to acyclic inclusions is the standard escape, and it is a genuine restriction: it excludes exactly the mutual-dependency schemas that are hardest to enforce anyway.

Sixth normal form, described in sixth normal form and attribute-level decomposition, shows the escape from the ladder rather than a step along it. Its condition is structural — no relation may have two non-key attributes — so checking it needs no dependency reasoning and no implication test at all. The price is that any constraint relating two non-key attributes becomes undeclarable. That is the same trade visible in every row of the table above: the more a constraint language can express, the less decidable its implication problem becomes, and schema design remains a matter of judgement precisely because the most useful constraint classes are the least tractable.