In relational database theory, an embedded dependency (ED) is a certain kind of constraint on a relational database.
It is the most general type of constraint used in practice, including both tuple-generating dependencies and equality-generating dependencies.
Embedded dependencies can express functional dependencies, join dependencies, multivalued dependencies, inclusion dependencies, foreign key dependencies, and many more besides.
An algorithm known as the chase takes as input an instance that may or may not satisfy a set of EDs, and, if it terminates (which is a priori undecidable), output an instance that does satisfy the EDs.
An embedded dependency (ED) is a sentence in first-order logic of the form: where
ϕ
ψ
are conjunctions of relational and equality atoms.
[1] A relational atom has the form
and an equality atom has the form
are variables or constants.
Actually, one can remove all equality atoms from the body of the dependency without loss of generality.
[2] For instance, if the body consists in the conjunction
(analogously replacing possible occurrences of the variables
Analogously, one can replace existential variables occurring in the head if they appear in some equality atom.
[2] In literature there are many common restrictions on embedded dependencies, among with:[1][3] When all atoms in
are equalities, the ED is an EGD and, when all atoms in
are relational, the ED is a TGD.
Every ED is equivalent to an EGD and a TGD.
A common extension of embedded dependencies are disjunctive embedded dependencies (DED),[4] which can be defined as follows: where
are conjunctions of relational and equality atoms.
Disjunctive embedded dependencies are more expressive than simple embedded dependencies, because DEDs in general can not be simulated using one or more EDs.
An even more expressive constraint is the disjunctive embedded dependency with inequalities (indicated with DED
may contain also inequality atoms.
[4] All the restriction above can be applied also to disjunctive embedded dependencies.
Beside them, DEDs can also be seen as a generalization of disjunctive tuple-generating dependencies (DTGD).