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.

An equivalent definition is the following:[1]

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

References

Calì, Andrea; Pieris, Andreas (2011). On Equality-Generating Dependencies in Ontology Querying - Preliminary Report (PDF). Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2011).

Equality-generating dependency

Definition

References

Further reading