Embedded dependency

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, multi-valued 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.

Definition

An embedded dependency (ED) is a sentence in first-order logic of the form:

$\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists z_{1},\ldots ,z_{k}.\psi (y_{1},\ldots ,y_{m})$

where $\{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{x_{1},\ldots ,x_{n}\}$, $\phi$ is a possibly empty and $\psi$ is a non-empty conjunction of relational and 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 $w,...,w_{h},w_{i},w_{j}$, are variables or constants.

In literature there are many common restrictions on embedded dependencies, among with:

• full (or universal) dependencies, which are the ones without existentially-quantified variables ($\exists z_{i}$)
• tuple-generating dependencies (TGDs)
• equality-generating dependencies (EGDs)
• single-head (or 1-head) dependencies, which have only one atom in the head
• unirelational dependencies, in which only one relation symbol occurs

When all atoms in $\psi$ are equalities, the ED is an EGD and, when all atoms in $\psi$ are relational, the ED is a TGD. Every ED is equivalent to an EGD and a TGD.

Further readings

• Kanellakis, Paris C. (1990). "Elements of Relational Database Theory". Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics. Amsterdam: Elsevier. pp. 1073–1156. doi:10.1016/b978-0-444-88074-1.50022-6. ISBN 978-0-444-88074-1.
• Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
• Alin Deutsch, FOL Modeling of Integrity Constraints, https://www.researchgate.net/publication/228579497_FOL_Modeling_of_Integrity_Constraints_Dependencies