Jump to content

Equality-generating dependency

From Wikipedia, the free encyclopedia

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

[edit]

An equality-generating dependency is a sentence in first-order logic of the form:

where , is a conjunction of relational and equality atoms and is a non-empty conjunction of equality atoms. A relational atom has the form and an equality atom has the form , where each of the terms are variables or constants.

Actually, one can remove all equality atoms from the body of the dependency without loss of generality.[1] For instance, if the body consists in the conjunction , then it can be replaced with (analogously replacing possible occurrences of the variables and in the head).

An equivalent definition is the following:[2]

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

References

[edit]
  1. ^ (Abiteboul, Hull & Vianu 1995, p. 217)
  2. ^ 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).

Further reading

[edit]