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:

: $\forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow \psi(y_1,\ldots,y_m)$

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

Actually, one can remove all equality atoms from the body of the dependency without loss of generality.{{harv|Abiteboul|Hull|Vianu|1995|p=217}} For instance, if the body consists in the conjunction $A(x,y) \land B(y,z,w) \land y=3 \land z=w$ , then it can be replaced with $A(x,3)\land B(3,z,z)$ (analogously replacing possible occurrences of the variables $y$ and $w$ in the head).

An equivalent definition is the following:{{cite conference|url=http://ceur-ws.org/Vol-749/paper23.pdf|title=On Equality-Generating Dependencies in Ontology Querying - Preliminary Report|first1=Andrea|last1=Calì|first2=Andreas|last2=Pieris|date=2011|conference=Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2011)}}

: $\forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow x_i=x_j$

where $i,j\in\{1, \ldots, n\}$ .

Indeed, generating a conjunction of equalities is equivalent to have multiple dependencies which generate only one equality.

Equality-generating dependency

Definition

References

Further reading