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 First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...

of the form: :

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

where

\ \subseteq \

\phi

is a

conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...

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. An equivalent definition is the following: :

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

where

i,j\in\

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

Definition

References

Further reading