Equality-Generating Dependencies

Synonyms

egd

Definition

Equality-generating dependencies, or egds, are one of the two major types of database dependencies (the other major type consists of tuple-generating dependencies, or tgds).

To define egds, it is necessary to begin with the notion of an atomic formula, which is a formula of the form P(x₁,…,x_k), where P is a k-ary relational symbol and x₁,…,x_k are variables, not necessarily distinct.

Then egds are formulas of the form ∀x(ϕ(x) → (x₁ = x₂)), where:

• ϕ(x) is a conjunction of atomic formulas, all with variables among the variables in x.

• Every variable in x appears in ϕ(x).

• x₁ and x₂ are distinct variables in x.

Conditions (1) and (2) together are sometimes replaced by the weaker condition that ϕ(x) be an arbitrary first-order formula with free variables exactly those in x.

Key Points

The most important example of an egd is a functional dependency, where an example is the formula

$$ \begin{array}{l}\forall {x}_1 \ldots \forall {x}_k\forall...