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.

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. 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. 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: \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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1283687708 under CC BY-SA 4.0; modifications have been made.