Referential integrity

An inclusion dependency over two (possibly identical) predicates ${\displaystyle R}$ and ${\displaystyle S}$ from a schema is written ${\displaystyle R[A_{1},...,A_{n}]\subseteq S[B_{1},...,B_{n}]}$, where the ${\displaystyle A_{i}}$, ${\displaystyle B_{i}}$ are distinct attributes (column names) of ${\displaystyle R}$ and ${\displaystyle S}$. It implies that the tuples of values appearing in columns ${\displaystyle A_{1},...,A_{n}}$ for facts of ${\displaystyle R}$ must also appear as a tuple of values in columns ${\displaystyle B_{1},...,B_{n}}$ for some fact of ${\displaystyle S}$.

Such constraint is a particular form of tuple-generating dependency (TGD) where in both the sides of the rule there is only one relational atom.[3] In first-order logic it is expressible as ${\displaystyle \forall {\vec {x}},{\vec {y}}.(R({\vec {x}},{\vec {y}})\rightarrow \exists {\vec {z}}.S({\vec {x}},{\vec {z}}))}$, where ${\displaystyle {\vec {x}}}$ is the vector (whose size is ${\displaystyle n}$) of variables shared by ${\displaystyle R}$ and ${\displaystyle S}$, and no variable appears multiple times neither in the TGD's body nor in its head.

Logical implication between inclusion dependencies can be axiomatized by inference rules[4]^: 193 and can be decided by a PSPACE algorithm. The problem can be shown to be PSPACE-complete by reduction from the acceptance problem for a linear bounded automaton.[4]^: 196 However, logical implication between dependencies that can be inclusion dependencies or functional dependencies is undecidable by reduction from the word problem for monoids.[4]^: 199

Declarative Referential Integrity (DRI) is one of the techniques in the SQL database programming language to ensure data integrity.

• Null pointer dereferencing
• Dangling pointer
• Data integrity
• Domain/key normal form
• Entity integrity
• Functional dependency
• Propagation constraint
• Surrogate key
• Slowly changing dimension

• DRI versus Triggers (archived)