# Embedded dependency

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Embedded_dependency
> Markdown URL: https://mediated.wiki/source/Embedded_dependency.md
> Source: https://en.wikipedia.org/wiki/Embedded_dependency
> Source revision: 1334769481
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Kind of constraint on a relational database}}
In relational [database theory](/source/database_theory), an '''embedded dependency''' (ED) is a certain kind of constraint on a [relational database](/source/relational_database). It is the most general type of constraint used in practice, including both [tuple-generating dependencies](/source/tuple-generating_dependency) and [equality-generating dependencies](/source/equality-generating_dependency). Embedded dependencies can express functional dependencies, join dependencies, [multivalued dependencies](/source/Multivalued_dependency), inclusion dependencies, [foreign key](/source/foreign_key) dependencies, and many more besides.

An algorithm known as [the chase](/source/Chase_(algorithm)) 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](/source/Sentence_(logic)) in [first-order logic](/source/first-order_logic) of the form:
:<math>\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)</math>

where <math>\{z_1,\ldots,z_k\} = \{y_1,\ldots,y_m\} \setminus \{x_1,\ldots,x_n\}</math> and <math>\phi</math> and <math>\psi</math> are [conjunctions](/source/Logical_conjunction) of relational and equality atoms.<ref name="Kanellakis1990">{{harv|Kanellakis|1990}}</ref> A relational atom has the form <math>R(w_1,\ldots,w_h)</math> and an equality atom has the form <math>w_i = w_j</math>, where each of the [terms](/source/Term_(logic)) <math>w, ..., w_h, w_i, w_j</math> are [variables](/source/Variable_(mathematics)) or constants.

Actually, one can remove all equality atoms from the body of the dependency [without loss of generality](/source/without_loss_of_generality).<ref name="Abiteboul95-p217">{{harv|Abiteboul|Hull|Vianu|1995|p=217}}</ref> For instance, if the body consists in the conjunction <math>A(x,y) \land B(y,z,w) \land y=3 \land z=w</math>, then it can be replaced with <math>A(x,3)\land B(3,z,z)</math> (analogously replacing possible occurrences of the variables <math>y</math> and <math>w</math> in the head). Analogously, one can replace existential variables occurring in the head if they appear in some equality atom.<ref name="Abiteboul95-p217"/>

== Restrictions ==
In literature there are many common restrictions on embedded dependencies, among with:<ref name="Kanellakis1990"/><ref>{{cite conference|conference=7th International Conference on Logic for Programming Artificial Intelligence and Reasoning|title=Querying Inconsistent Databases|pages=308–325|url=https://books.google.com/books?id=x9yIe1NiWHkC&pg=PA308|first1=Sergio|last1=Greco|first2=Ester|last2=Zumpano|doi=10.1007/3-540-44404-1_20|date=Nov 2000|place=Reunion Island, France|editor=Michel Parigot, Andrei Voronkov|publisher=Springer|url-access=subscription}}</ref>
* ''full'' (or ''universal'') ''dependencies'', which are the ones without [existentially-quantified](/source/Existential_quantification) variables (<math>\exists z_i</math>)
* ''[tuple-generating dependencies](/source/Tuple-generating_dependency)'' (TGDs)
* ''[equality-generating dependencies](/source/equality-generating_dependency)'' (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 <math>\psi</math> are equalities, the ED is an EGD and, when all atoms in <math>\psi</math> 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),<ref name="deutsch">{{harv|Deutsch|2009}}</ref> which can be defined as follows:
:<math>\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)</math>
where <math>\{z_1^i,\ldots,z_k^i\} = \{y_1^i,\ldots,y_m^i\} \setminus \{x_1,\ldots,x_n\}</math> and <math>\phi</math> and <math>\psi</math> are [conjunctions](/source/Logical_conjunction) 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<math>^\ne</math>), in which every <math>\psi</math> may contain also inequality atoms.<ref name="deutsch"/> 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.<ref>{{Cite journal |last1=Zhang |first1=Heng |last2=Zhang |first2=Yan |last3=You |first3=Jia-Huai |date=2016-07-09 |title=Expressive completeness of existential rule languages for ontology-based query answering |url=https://dl.acm.org/doi/10.5555/3060621.3060806 |journal=Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence |series=IJCAI'16 |location=New York, New York, USA |publisher=AAAI Press |pages=1330–1337 |isbn=978-1-57735-770-4}}</ref><ref>{{Cite journal |last1=Zhang |first1=Heng |last2=Zhang |first2=Yan |last3=You |first3=Jia-Huai |last4=Feng |first4=Zhiyong |last5=Jiang |first5=Guifei |date=2020-04-03 |title=Towards Universal Languages for Tractable Ontology Mediated Query Answering |url=https://ojs.aaai.org/index.php/AAAI/article/view/5699 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=34 |issue=3 |pages=3049–3056 |doi=10.1609/aaai.v34i03.5699 |issn=2374-3468|arxiv=1911.11359 }}</ref><ref name=":0">{{cite conference |last1=Zhang |first1=Heng |last2=Jiang |first2=Guifei |date=Jun 2022 |title=Characterizing the Program Expressive Power of Existential Rule Languages |url=https://ojs.aaai.org/index.php/AAAI/article/view/20540 |conference=AAAI Conference on Artificial Intelligence |volume=36 |pages=5950–5957 |arxiv=2112.08136 |doi=10.1609/aaai.v36i5.20540 |number=5}}</ref>  

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).<ref>{{Cite journal |last=Deutsch |first=Alin |last2=Tannen |first2=Val |date=2003 |editor-last=Calvanese |editor-first=Diego |editor2-last=Lenzerini |editor2-first=Maurizio |editor3-last=Motwani |editor3-first=Rajeev |title=Reformulation of XML Queries and Constraints |url=https://link.springer.com/chapter/10.1007/3-540-36285-1_15 |journal=Database Theory — ICDT 2003 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=225–241 |doi=10.1007/3-540-36285-1_15 |isbn=978-3-540-36285-2|url-access=subscription }}</ref>

Unlike the relationship between DEDs and EDs, when considering query answering with conjunctive queries (CQs), DTGDs can always be equivalently rewritten as TGDs.<ref name=":0" /> However, if unions of conjunctive queries (UCQs) are allowed in query answering, the expressive power of DTGDs still strictly exceeds that of TGDs.<ref name=":0" /> In addition, it is also noteworthy that DEDs are strictly more expressive than DTGDs.<ref name=":0" />  

== References ==
<references/>

== Further reading ==
* {{cite conference |url=https://www.sciencedirect.com/science/article/pii/B9780444880741500226 |title=Elements of Relational Database Theory |last1=Kanellakis |first1=Paris C. |author-link1= |date=1990 |publisher=Elsevier |book-title=Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics |pages=1073–1156 |location=Amsterdam |conference= |id= |doi=10.1016/b978-0-444-88074-1.50022-6|isbn=978-0-444-88074-1|url-access=subscription }}
* {{cite book |last1=Abiteboul |first1=Serge |author-link1=Serge Abiteboul |last2=Hull |first2=Richard B. |author-link2=Richard B. Hull |last3=Vianu |first3=Victor |author-link3=Victor Vianu |date=1995 |title=Foundations of Databases |url= |location= |publisher=Addison-Wesley |page= |isbn=0-201-53771-0}}
* {{cite book|last=Deutsch|first=Alin|year=2009|chapter=FOL Modeling of Integrity Constraints (Dependencies)|title=Encyclopedia of Database Systems|publisher=Springer US|place=Boston, MA|pages=1155–1161|isbn=978-0-387-39940-9|doi=10.1007/978-0-387-39940-9_980}}

Category:Database theory
Category:Logic

---
Adapted from the Wikipedia article [Embedded dependency](https://en.wikipedia.org/wiki/Embedded_dependency) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Embedded_dependency?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.