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:
∀x1,…,xn.ϕ(x1,…,xn)→ψ(y1,…,ym) where {y1,…,ym}⊆{x1,…,xn}, ϕ is a conjunction of relational and equality atoms and ψ is a non-empty conjunction of equality atoms. A relational atom has the form R(w1,…,wh) and an equality atom has the form wi=wj, where each of the terms w,...,wh,wi,wj 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 A(x,y)∧B(y,z,w)∧y=3∧z=w, then it can be replaced with A(x,3)∧B(3,z,z) (analogously replacing possible occurrences of the variables y and w in the head). An equivalent definition is the following:
∀x1,…,xn.ϕ(x1,…,xn)→xi=xj where i,j∈{1,…,n}. Indeed, generating a conjunction of equalities is equivalent to have multiple dependencies which generate only one equality.
== References ==
== 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
Wikipedia contributors, "Equality-generating dependency", Wikipedia, revision 1283687708, retrieved 20 November 2026, source, CC BY-SA 4.0.