{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:29Z","timestamp":1750220909426,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1217869"],"award-info":[{"award-number":["IIS-1217869"]}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M025268\/1"],"award-info":[{"award-number":["EP\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["809965"],"award-info":[{"award-number":["809965"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["VRG18-013 and ICT12-015"],"award-info":[{"award-number":["VRG18-013 and ICT12-015"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Austrian Science Fund","award":["(FWF):P25207-N23 and (FWF):Y698"],"award-info":[{"award-number":["(FWF):P25207-N23 and (FWF):Y698"]}]},{"DOI":"10.13039\/100017637","name":"Simons Institute for the Theory of Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100017637","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>During the past 15 years, schema mappings have been extensively used in formalizing and studying such critical data interoperability tasks as data exchange and data integration. Much of the work has focused on GLAV mappings, i.e., schema mappings specified by source-to-target tuple-generating dependencies (s-t tgds), and on schema mappings specified by second-order tgds (SO tgds), which constitute the closure of GLAV mappings under composition. In addition, nested GLAV mappings have also been considered, i.e., schema mappings specified by nested tgds, which have expressive power intermediate between s-t tgds and SO tgds. Even though nested GLAV mappings have been used in data exchange systems, such as IBM\u2019s Clio, no systematic investigation of this class of schema mappings has been carried out so far. In this article, we embark on such an investigation by focusing on the basic reasoning tasks, algorithmic problems, and structural properties of nested GLAV mappings. One of our main results is the decidability of the implication problem for nested tgds. We also analyze the structure of the core of universal solutions with respect to nested GLAV mappings and develop useful tools for telling apart SO tgds from nested tgds. By discovering deeper structural properties of nested GLAV mappings, we show that also the following problem is decidable: Given a nested GLAV mapping, is it logically equivalent to a GLAV mapping?<\/jats:p>","DOI":"10.1145\/3369554","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:33:48Z","timestamp":1594125228000},"page":"1-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Language of Nested Tuple Generating Dependencies"],"prefix":"10.1145","volume":"45","author":[{"given":"Phokion G.","family":"Kolaitis","sequence":"first","affiliation":[{"name":"UC Santa Cruz and IBM Research - Almaden, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuel","family":"Sallinger","sequence":"additional","affiliation":[{"name":"TU Wien and University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vadim","family":"Savenkov","sequence":"additional","affiliation":[{"name":"Vienna University of Economics and Business, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"volume-title":"Foundations of Data Exchange","author":"Arenas Marcelo","key":"e_1_2_1_1_1","unstructured":"Marcelo Arenas , Pablo Barcel\u00f3 , Leonid Libkin , and Filip Murlak . 2014. Foundations of Data Exchange . Cambridge University Press , Cambridge, UK . Marcelo Arenas, Pablo Barcel\u00f3, Leonid Libkin, and Filip Murlak. 2014. Foundations of Data Exchange. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.002"},{"key":"e_1_2_1_3_1","article-title":"The recovery of a schema mapping: Bringing exchanged data back","volume":"34","author":"Arenas Marcelo","year":"2009","unstructured":"Marcelo Arenas , Jorge P\u00e9rez , and Cristian Riveros . 2009 . The recovery of a schema mapping: Bringing exchanged data back . ACM Trans. Datab. Syst. 34 , 4 (2009), 22:1\u201322:48. Marcelo Arenas, Jorge P\u00e9rez, and Cristian Riveros. 2009. The recovery of a schema mapping: Bringing exchanged data back. ACM Trans. Datab. Syst. 34, 4 (2009), 22:1\u201322:48.","journal-title":"ACM Trans. Datab. Syst."},{"volume-title":"Proceedings of the SIGMOD Conference. ACM, 157--168","author":"Arocena Patricia C.","key":"e_1_2_1_4_1","unstructured":"Patricia C. Arocena , Boris Glavic , and Renee J. Miller . 2013. Value invention in data exchange . In Proceedings of the SIGMOD Conference. ACM, 157--168 . Patricia C. Arocena, Boris Glavic, and Renee J. Miller. 2013. Value invention in data exchange. In Proceedings of the SIGMOD Conference. ACM, 157--168."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases. 1267--1270","author":"Bonifati Angela","year":"2005","unstructured":"Angela Bonifati , Elaine Qing Chang , Aks V. S. Lakshmanan , Terence Ho , and Rachel Pottinger . 2005 . HePToX: Marrying XML and heterogeneity in your P2P databases . In Proceedings of the 31st International Conference on Very Large Data Bases. 1267--1270 . Angela Bonifati, Elaine Qing Chang, Aks V. S. Lakshmanan, Terence Ho, and Rachel Pottinger. 2005. HePToX: Marrying XML and heterogeneity in your P2P databases. In Proceedings of the 31st International Conference on Very Large Data Bases. 1267--1270."},{"volume-title":"Principles of Data Integration. Morgan Kaufmann","author":"Doan AnHai","key":"e_1_2_1_6_1","unstructured":"AnHai Doan , Alon Halevy , and Zachary Ives . 2012. 11 - XML . In Principles of Data Integration. Morgan Kaufmann , Boston, MA , 291--323. AnHai Doan, Alon Halevy, and Zachary Ives. 2012. 11 - XML. In Principles of Data Integration. Morgan Kaufmann, Boston, MA, 291--323."},{"volume-title":"Proceedings of the Symposium on Principles of Database Systems. 179--190","author":"Fagin Ronald","key":"e_1_2_1_7_1","unstructured":"Ronald Fagin and Phokion G. Kolaitis . 2012. Local transformations and conjunctive-query equivalence . In Proceedings of the Symposium on Principles of Database Systems. 179--190 . Ronald Fagin and Phokion G. Kolaitis. 2012. Local transformations and conjunctive-query equivalence. In Proceedings of the Symposium on Principles of Database Systems. 179--190."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376922"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.09.003"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 67--78","author":"Fuxman Ariel","year":"2006","unstructured":"Ariel Fuxman , Mauricio A. Hern\u00e1ndez , C. T. Howard Ho , Ren\u00e9e J. Miller , Paolo Papotti , and Lucian Popa . 2006 . Nested mappings: Schema mapping reloaded . In Proceedings of the International Conference on Very Large Data Bases. 67--78 . Ariel Fuxman, Mauricio A. Hern\u00e1ndez, C. T. Howard Ho, Ren\u00e9e J. Miller, Paolo Papotti, and Lucian Popa. 2006. Nested mappings: Schema mapping reloaded. In Proceedings of the International Conference on Very Large Data Bases. 67--78."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745756"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342631"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775231"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369046"},{"key":"e_1_2_1_19_1","volume-title":"Dagstuhl Follow-Ups","volume":"5","author":"Kolaitis Phokion G.","year":"2013","unstructured":"Phokion G. Kolaitis , Maurizio Lenzerini , and Nicole Schweikardt ( Eds .). 2013 . Data Exchange, Integration, and Streams . Dagstuhl Follow-Ups , Vol. 5 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Phokion G. Kolaitis, Maurizio Lenzerini, and Nicole Schweikardt (Eds.). 2013. Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Vol. 5. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594544"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9812-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_2_1_23_1","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 572--583","author":"Madhavan Jayant","key":"e_1_2_1_24_1","unstructured":"Jayant Madhavan and Alon Y. Halevy . 2003. Composing mappings among data sources . In Proceedings of the International Conference on Very Large Data Bases. 572--583 . Jayant Madhavan and Alon Y. Halevy. 2003. Composing mappings among data sources. In Proceedings of the International Conference on Very Large Data Bases. 572--583."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9397-0"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering. 30--39","author":"Raffio Alessandro","key":"e_1_2_1_26_1","unstructured":"Alessandro Raffio , Daniele Braga , Stefano Ceri , Paolo Papotti , and Mauricio A. Hern\u00e1ndez . 2008. Clip: A visual language for explicit schema mappings . In Proceedings of the IEEE International Conference on Data Engineering. 30--39 . Alessandro Raffio, Daniele Braga, Stefano Ceri, Paolo Papotti, and Mauricio A. Hern\u00e1ndez. 2008. Clip: A visual language for explicit schema mappings. In Proceedings of the IEEE International Conference on Data Engineering. 30--39."},{"key":"e_1_2_1_27_1","volume-title":"Dagstuhl Follow-Ups","volume":"5","author":"Sallinger Emanuel","year":"2013","unstructured":"Emanuel Sallinger . 2013 . Reasoning about schema mappings. In Data Exchange, Information, and Streams . Dagstuhl Follow-Ups , Vol. 5 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 97--127. Emanuel Sallinger. 2013. Reasoning about schema mappings. In Data Exchange, Information, and Streams. Dagstuhl Follow-Ups, Vol. 5. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 97--127."},{"volume-title":"Proceedings of the International Conference on Database Theory. 63--72","author":"Cate Balder","key":"e_1_2_1_28_1","unstructured":"Balder ten Cate and Phokion G. Kolaitis . 2009. Structural characterizations of schema-mapping languages . In Proceedings of the International Conference on Database Theory. 63--72 . Balder ten Cate and Phokion G. Kolaitis. 2009. Structural characterizations of schema-mapping languages. In Proceedings of the International Conference on Database Theory. 63--72."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369554","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369554","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:57Z","timestamp":1750203897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3369554"],"URL":"https:\/\/doi.org\/10.1145\/3369554","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}