Equality-generating dependency

In relational database theory, an equality-generating dependency (EGD) is a certain kind of constraint on data. It is a subclass of the class of embedded dependencies (ED). An algorithm known as the chase takes as input an instance that may or may not satisfy a set of EGDs (or, more generally, a set of EDs), and, if it terminates (which is a priori undecidable), output an instance that does satisfy the EGDs.

An important subclass of equality-generating dependencies are functional dependencies.

Definition

An equality-generating dependency is a sentence in first-order logic of the form:

[math]\displaystyle{ \forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow \psi(y_1,\ldots,y_m) }[/math]

where [math]\displaystyle{ \{y_1, \ldots, y_m\} \subseteq \{x_1, \ldots, x_n\} }[/math], [math]\displaystyle{ \phi }[/math] is a conjunction of relational and equality atoms and [math]\displaystyle{ \psi }[/math] is a non-empty conjunction of equality atoms. A relational atom has the form [math]\displaystyle{ R(w_1,\ldots,w_h) }[/math] and an equality atom has the form [math]\displaystyle{ w_i = w_j }[/math], where each of the terms [math]\displaystyle{ w, ..., w_h, w_i, w_j }[/math] are variables or constants.

Actually, one can remove all equality atoms from the body of the dependency without loss of generality. For instance, if the body consists in the conjunction [math]\displaystyle{ A(x,y) \land B(y,z,w) \land y=3 \land z=w }[/math], then it can be replaced with [math]\displaystyle{ A(x,3)\land B(3,z,z) }[/math] (analogously replacing possible occurrences of the variables [math]\displaystyle{ y }[/math] and [math]\displaystyle{ w }[/math] in the head).

An equivalent definition is the following:

[math]\displaystyle{ \forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow x_i=x_j }[/math]

where [math]\displaystyle{ i,j\in\{1, \ldots, n\} }[/math]. Indeed, generating a conjunction of equalities is equivalent to have multiple dependencies which generate only one equality.

Further reading

• Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0. 
• Alin Deutsch, FOL Modeling of Integrity Constraints, https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf