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:

${\displaystyle \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 ${\displaystyle \{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{x_{1},\ldots ,x_{n}\}}$ and ${\displaystyle \phi }$ is a possibly empty and ${\displaystyle \psi }$ is a non-empty conjunction of relational and equality atoms.^[1] A relational atom has the form ${\displaystyle R(w_{1},\ldots ,w_{h})}$ and an equality atom has the form ${\displaystyle w_{i}=w_{j}}$, where each of the terms ${\displaystyle w,...,w_{h},w_{i},w_{j}}$ are variables or constants.

In literature there are many common restrictions on embedded dependencies, among with:^[1][2]

• full (or universal) dependencies, which are the ones without existentially-quantified variables (${\displaystyle \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 ${\displaystyle \psi }$ are equalities, the ED is an EGD and, when all atoms in ${\displaystyle \psi }$ are relational, the ED is a TGD. Every ED is equivalent to an EGD and a TGD.

References[]

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, , 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

This computing article is a stub. You can help Wikipedia by .

• v
• t