Editing Referential integrity (section)

==Formalization==
An '''inclusion dependency''' over two (possibly identical) predicates <math>R</math> and <math>S</math> from a schema is written <math>R[A_1, ..., A_n] \subseteq S[B_1, ..., B_n]</math>, where the <math>A_i</math>, <math>B_i</math> are distinct attributes (column names) of <math>R</math> and <math>S</math>. It implies that the tuples of values appearing in columns <math>A_1, ..., A_n</math> for facts of <math>R</math> must also appear as a tuple of values in columns <math>B_1, ..., B_n</math> for some fact of <math>S</math>.

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.<ref>{{cite web|url=https://www.knaw.nl/shared/resources/actueel/bestanden/kolaitis.pdf#page=5|title=A Tutorial on Database Dependencies|publisher=University of California Santa Cruz & IBM Research - Almaden|last=Kolaitis|first=Phokion G.|date=|access-date=2021-12-10}}</ref>  In [[first-order logic]] it is expressible as <math>\forall \vec{x},\vec{y} . (R(\vec{x},\vec{y}) \rightarrow \exists \vec{z} . S(\vec{x},\vec{z}))</math>, where <math>\vec{x}</math> is the vector (whose size is <math>n</math>) of variables shared by <math>R</math> and <math>S</math>, 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<ref name=foundations-db>{{cite book |last1=Abiteboul |first1=Serge |author-link1=Serge Abiteboul |last2=Hull |first2=Richard B. |last3=Vianu |first3=Victor |author-link3=Victor Vianu |date=1994 |title=Foundations of Databases |chapter=9. Inclusion Dependency |publisher=Addison-Wesley |pages=192–199 |url=http://webdam.inria.fr/Alice/}}</ref>{{rp|193}}
and can be [[decidable language|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]].<ref name=foundations-db />{{rp|196}} However, logical implication between dependencies that can be inclusion dependencies or [[functional dependencies]] is undecidable by reduction from the [[word problem (computability)|word problem]] for [[monoids]].<ref name=foundations-db />{{rp|199}}