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

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}\}$ and $\phi$ and $\psi$ are conjunctions 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 terms $w,...,w_{h},w_{i},w_{j}$ 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 $A(x,y)\land B(y,z,w)\land y=3\land z=w$ , then it can be replaced with $A(x,3)\land B(3,z,z)$ (analogously replacing possible occurrences of the variables $y$ and $w$ in the head). Analogously, one can replace existential variables occurring in the head if they appear in some equality atom.^[2]

Restrictions

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

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.

Extensions

A common extension of embedded dependencies are disjunctive embedded dependencies (DEDs),^[4] which can be defined as follows:

\forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \bigvee _{i=1}^{\ell }\exists z_{1}^{i},\ldots ,z_{k}^{i}.\psi (y_{1}^{i},\ldots ,y_{m}^{i})

where $\{z_{1}^{i},\ldots ,z_{k}^{i}\}=\{y_{1}^{i},\ldots ,y_{m}^{i}\}\setminus \{x_{1},\ldots ,x_{n}\}$ and $\phi$ and $\psi$ 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. A further extension is the disjunctive embedded dependency with inequalities (indicated with DED $^{\neq }$ ), in which every $\psi$ may contain also inequality atoms.^[4] However, it is important to note that this extension does not enhance expressive power, as DEDs are already expressively complete for recursively enumerable Boolean query answering.^[5]^[6]^[7]

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 (DTGDs).^[8]

Unlike the relationship between DEDs and EDs, when considering query answering with conjunctive queries (CQs), DTGDs can always be equivalently rewritten as TGDs.^[7] However, if unions of conjunctive queries (UCQs) are allowed in query answering, the expressive power of DTGDs still strictly exceeds that of TGDs.^[7] In addition, it is also noteworthy that DEDs are strictly more expressive than DTGDs.^[7]

References

^ ^a ^b (Kanellakis 1990)
^ ^a ^b (Abiteboul, Hull & Vianu 1995, p. 217)
^ Greco, Sergio; Zumpano, Ester (Nov 2000). Michel Parigot, Andrei Voronkov (ed.). Querying Inconsistent Databases. 7th International Conference on Logic for Programming Artificial Intelligence and Reasoning. Reunion Island, France: Springer. pp. 308–325. doi:10.1007/3-540-44404-1_20.
^ ^a ^b (Deutsch 2009)
^ Zhang, Heng; Zhang, Yan; You, Jia-Huai (2016-07-09). "Expressive completeness of existential rule languages for ontology-based query answering". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 1330–1337. ISBN 978-1-57735-770-4.
^ Zhang, Heng; Zhang, Yan; You, Jia-Huai; Feng, Zhiyong; Jiang, Guifei (2020-04-03). "Towards Universal Languages for Tractable Ontology Mediated Query Answering". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (3): 3049–3056. arXiv:1911.11359. doi:10.1609/aaai.v34i03.5699. ISSN 2374-3468.
^ ^a ^b ^c ^d Zhang, Heng; Jiang, Guifei (Jun 2022). Characterizing the Program Expressive Power of Existential Rule Languages. AAAI Conference on Artificial Intelligence. Vol. 36. pp. 5950–5957. arXiv:2112.08136. doi:10.1609/aaai.v36i5.20540.
^ Deutsch, Alin; Tannen, Val (2003). Calvanese, Diego; Lenzerini, Maurizio; Motwani, Rajeev (eds.). "Reformulation of XML Queries and Constraints". Database Theory — ICDT 2003. Berlin, Heidelberg: Springer: 225–241. doi:10.1007/3-540-36285-1_15. ISBN 978-3-540-36285-2.

Definition

Restrictions

Extensions

References

Further reading