Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Tuple-generating dependency
open-in-new
<h2 id="definition">Definition</h2> <p>A tuple-generating dependency is a <a href="/facts/Sentence_(logic)/lnsLzvTx">sentence</a> in <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a> of the form:<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> ∀ x 1 , … , x n . ϕ ( x 1 , … , x n ) → ∃ y 1 , … , y m , ψ ( x 1 , … , x n , y 1 , … , y m ) {\displaystyle \forall x_{1},\ldots ,x_{n}.\phi (x_{1},\ldots ,x_{n})\rightarrow \exists y_{1},\ldots ,y_{m},\psi (x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m})} <p>where ϕ {\displaystyle \phi } is a possibly empty and ψ {\displaystyle \psi } is a non-empty <a href="/facts/Logical_conjunction/62uyyn1d">conjunction</a> of <a href="/facts/Atomic_formula/s9WMnbqT">relational atoms</a>. A relational atom has the form R ( w 1 , … , w h ) {\displaystyle R(w_{1},\ldots ,w_{h})} , where each of the <a href="/facts/Term_(logic)/M0nXp7dH">terms</a> w , … , w h {\displaystyle w,\ldots ,w_{h}} are <a href="/facts/Variable_(mathematics)/VbQlrvKz">variables</a> or constants. </p> <h2 id="fragments">Fragments</h2> <p>Several <a href="/facts/Fragment_(logic)/KxvnWnl9">fragments</a> of TGDs have been defined. For instance, <i>full TGDs</i> are TGDs which do not use the existential quantifier. Full TGDs can equivalently be seen as programs in the <a href="/facts/Datalog/67jbYWDb">Datalog</a> query language. </p><p>There are also some fragments of TGDs that can be expressed in <a href="/facts/Guarded_logic/esTjeXz3">guarded logic</a>, in particular:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <ul><li>in <i>frontier-guarded TGDs</i> (FGTGD), all the variables shared by the body and the head of a rule (called <i>frontier variables</i>) must occur together in some atom;</li> <li><i>guarded TGDs</i> (GTGD) are particular FGTGDs where all variables used in the body of a rule must occur together in some atom;</li> <li><i>linear TGDs</i> (LTGD) are particular GTGDs where whose body consists of a single atom;</li> <li><i><a href="/facts/Inclusion_dependencies/UJzY2tw5">inclusion dependencies</a></i> (IND) are particular LTGDs where in both the sides of the rule there is only one relational atom.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a></li></ul> <p>The expressive power of these fragments and TGDs has been studied in depth. For example, Heng Zhang et al.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>, as well as Marco Console and Phokion G. Kolaitis,<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> have developed a series of model-theoretic characterizations for these languages. In addition, Heng Zhang and Guifei Jiang have provided characterizations of the program expressive power of TGDs, several of their extensions, and Linear TGDs, specifically in the context of query answering.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>In <a href="/facts/SQL/UjQLJcYm">SQL</a>, inclusion dependencies are typically expressed by means of a stronger constraint called <a href="/facts/Foreign_key/52Ns8RTD">foreign key</a>, which forces the frontier variables to be a <a href="/facts/Candidate_key/1SyxFj7C">candidate key</a> in the <a href="/facts/Table_(database)/5INvK1Vd">table</a> corresponding to the relational atom of ψ {\displaystyle \psi } . </p> <h2 id="further-reading">Further reading</h2> <ul><li><a href="/facts/Serge_Abiteboul/m2a4AL4h">Abiteboul, Serge</a>; Hull, Richard B.; <a href="/facts/Victor_Vianu/xF98xUdg">Vianu, Victor</a> (1995). <i>Foundations of Databases</i>. Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-201-53771-0.</li> <li>Alin Deutsch, FOL Modeling of Integrity Constraints, <a href="https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf">https://web.archive.org/web/20140912044956/http://db.ucsd.edu/pubsFileFolder/305.pdf</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Fagin, Ronald (2009). "Tuple-Generating Dependencies". In LIU, LING; ÖZSU, M. TAMER (eds.). Encyclopedia of Database Systems. Springer US. pp. 3201–3202. doi:10.1007/978-0-387-39940-9_1274. ISBN 9780387355443. <a href="9780387355443" target="_blank">9780387355443</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Benedikt, Michael; Bourhis, Pierre; Jachiet, Louis; Thomazo, Michaël (Aug 2019). Reasoning about Disclosure in Data Integration in the Presence of Source Constraints. IJCAI 2019 - 28th International Joint Conference on Artificial Intelligence. Macao, China. pp. 1551–1557. arXiv:1906.00624. doi:10.24963/ijcai.2019/215. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Zhang, Heng; Zhang, Yan; Jiang, Guifei (2020-07-09). "Model-theoretic Characterizations of Existential Rule Languages". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. 2: 1940–1946. arXiv:2001.08688. doi:10.24963/ijcai.2020/269. <a href="https://www.ijcai.org/proceedings/2020/269" target="_blank">https://www.ijcai.org/proceedings/2020/269</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Console, Marco; Kolaitis, Phokion G.; Pieris, Andreas (June 2021). Model-theoretic Characterizations of Rule-based Ontologies. Symposium on Principles of Database Systems. PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Virtual Event, China. pp. 416–428. doi:10.1145/3452021.3458310. hdl:11573/1568516. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Kolaitis, Phokion G. "A Tutorial on Database Dependencies" (PDF). University of California Santa Cruz & IBM Research - Almaden. Archived from the original (PDF) on February 20, 2015. Retrieved 2021-12-10. <a href="https://web.archive.org/web/20150220105559/https://www.knaw.nl/shared/resources/actueel/bestanden/kolaitis.pdf#page=5" target="_blank">https://web.archive.org/web/20150220105559/https://www.knaw.nl/shared/resources/actueel/bestanden/kolaitis.pdf#page=5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Zhang, Heng; Zhang, Yan; Jiang, Guifei (2020-07-09). "Model-theoretic Characterizations of Existential Rule Languages". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. 2: 1940–1946. arXiv:2001.08688. doi:10.24963/ijcai.2020/269. <a href="https://www.ijcai.org/proceedings/2020/269" target="_blank">https://www.ijcai.org/proceedings/2020/269</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Console, Marco; Kolaitis, Phokion G.; Pieris, Andreas (June 2021). Model-theoretic Characterizations of Rule-based Ontologies. Symposium on Principles of Database Systems. PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Virtual Event, China. pp. 416–428. doi:10.1145/3452021.3458310. hdl:11573/1568516. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Zhang, Heng; Jiang, Guifei (2022-06-28). "Characterizing the Program Expressive Power of Existential Rule Languages". Proceedings of the AAAI Conference on Artificial Intelligence. 36 (5): 5950–5957. arXiv:2112.08136. doi:10.1609/aaai.v36i5.20540. ISSN 2374-3468. <a href="https://ojs.aaai.org/index.php/AAAI/article/view/20540" target="_blank">https://ojs.aaai.org/index.php/AAAI/article/view/20540</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>