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>\forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow \psi(y_1,\ldots,y_m)</math> where <math>\{y_1, \ldots, y_m\} \subseteq \{x_1, \ldots, x_n\}</math>, <math>\phi</math> is a conjunction of relational and equality atoms and <math>\psi</math> is a non-empty conjunction of equality atoms. A relational atom has the form <math>R(w_1,\ldots,w_h)</math> and an equality atom has the form <math>w_i = w_j</math>, where each of the terms <math>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.<ref>{{harv|Abiteboul|Hull|Vianu|1995|p=217}}</ref> For instance, if the body consists in the conjunction <math>A(x,y) \land B(y,z,w) \land y=3 \land z=w</math>, then it can be replaced with <math>A(x,3)\land B(3,z,z)</math> (analogously replacing possible occurrences of the variables <math>y</math> and <math>w</math> in the head).
An equivalent definition is the following:<ref>{{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)}}</ref> :<math>\forall x_1,\ldots,x_n . \phi(x_1,\ldots,x_n) \rightarrow x_i=x_j</math> where <math>i,j\in\{1, \ldots, n\}</math>. Indeed, generating a conjunction of equalities is equivalent to have multiple dependencies which generate only one equality.
== References == <references/>
== Further reading == * {{cite book |last1=Abiteboul |first1=Serge |author-link1=Serge Abiteboul |last2=Hull |first2=Richard B. |author-link2=Richard B. Hull |last3=Vianu |first3=Victor |author-link3=Victor Vianu |date=1995 |title=Foundations of Databases |url= |location= |publisher=Addison-Wesley |page= |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
Category:Database theory Category:Logic
{{database-stub}}