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}.P(x_{1},\ldots ,x_{n})\rightarrow \exists z_{1},\ldots ,z_{k}.Q(y_{1},\ldots ,y_{m})

where $\{z_{1},\ldots ,z_{k}\}=\{y_{1},\ldots ,y_{m}\}\setminus \{x_{1},\ldots ,x_{n}\}$ , and $P$ is a possibly empty and $Q$ is a non-empty conjunction of relational and equality atoms.[1] 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:[1]

full (or universal) dependencies, which are the ones without existential quantifiers ( $\exists$ )
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 $Q$ are equalities, the ED is an EGD, and when all atoms in $Q$ are relational, the ED is a TGD. Every ED is equivalent to an EGD and a TGD.

References

(Kanellakis 1990)

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Kanellakis1990-1] (Kanellakis 1990)