{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:46:28Z","timestamp":1764557188625,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["E005039"],"award-info":[{"award-number":["E005039"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1.05E+13"],"award-info":[{"award-number":["1.05E+13"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["MEXC-CT-2005-024502"],"award-info":[{"award-number":["MEXC-CT-2005-024502"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Millennium Nucleus Center for Web Research","award":["P04-067-F"],"award-info":[{"award-number":["P04-067-F"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been investigated for relational data.<\/jats:p>\n          <jats:p>In this article, we start looking into the basic properties of XML data exchange, that is, restructuring of XML documents that conform to a source DTD under a target DTD, and answering queries written over the target schema. We define XML data exchange settings in which source-to-target dependencies refer to the hierarchical structure of the data. Combining DTDs and dependencies makes some XML data exchange settings inconsistent. We investigate the consistency problem and determine its exact complexity.<\/jats:p>\n          <jats:p>We then move to query answering, and prove a dichotomy theorem that classifies data exchange settings into those over which query answering is tractable, and those over which it is coNP-complete, depending on classes of regular expressions used in DTDs. Furthermore, for all tractable cases we give polynomial-time algorithms that compute target XML documents over which queries can be answered.<\/jats:p>","DOI":"10.1145\/1346330.1346332","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":79,"title":["XML data exchange"],"prefix":"10.1145","volume":"55","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375571"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0076-7"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press","author":"Amer-Yahia S.","key":"e_1_2_1_5_1","unstructured":"Amer-Yahia , S. , and Kotidis , Y . 2004. Web-services architecture for efficient XML data exchange . In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press , Los Alamitos, CA, 523--534. Amer-Yahia, S., and Kotidis, Y. 2004. Web-services architecture for efficient XML data exchange. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 523--534."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055592"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065171"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag","author":"Benedikt M.","key":"e_1_2_1_8_1","unstructured":"Benedikt , M. , Fan , W. , and Kuper , G. M . 2003. Structural properties of XPath fragments . In Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag , Heidelberg, Germany, 79--95. Benedikt, M., Fan, W., and Kuper, G. M. 2003. Structural properties of XPath fragments. In Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag, Heidelberg, Germany, 79--95."},{"key":"e_1_2_1_9_1","unstructured":"Comon H. Dauchet M. Gilleron R. L\u00f6ding C. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 2007. Tree automata techniques and applications. (Available on: http:\/\/www.grappa.univ-lille3.fr\/tata. release October 12th 2007).  Comon H. Dauchet M. Gilleron R. L\u00f6ding C. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 2007. Tree automata techniques and applications. (Available on: http:\/\/www.grappa.univ-lille3.fr\/tata. release October 12th 2007)."},{"volume-title":"Proceedings of the International Workshop on Knowledge Representation meets Databases (KRDB). CEUR-WS.org.","author":"Deutsch A.","key":"e_1_2_1_10_1","unstructured":"Deutsch , A. , and Tannen , V . 2001. Containment and integrity constraints for XPath . In Proceedings of the International Workshop on Knowledge Representation meets Databases (KRDB). CEUR-WS.org. Deutsch, A., and Tannen, V. 2001. Containment and integrity constraints for XPath. In Proceedings of the International Workshop on Knowledge Representation meets Databases (KRDB). CEUR-WS.org."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_1_14_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Fixed Points in Computer Science (FICS)","author":"Kozen D.","year":"2002","unstructured":"Kozen , D. 2002 . On two letters versus three . In Proceedings of the Fixed Points in Computer Science (FICS) . University of Aarhus, 44--50. Kozen, D. 2002. On two letters versus three. In Proceedings of the Fixed Points in Computer Science (FICS). University of Aarhus, 44--50."},{"volume-title":"Proceedings of the International XML Database Symposium (XSym). Springer-Verlag","author":"Krishnamurthy R.","key":"e_1_2_1_18_1","unstructured":"Krishnamurthy , R. , Kaushik , R. , and Naughton , J. F . 2003. XML-SQL query translation literature: The state of the art and open problems . In Proceedings of the International XML Database Symposium (XSym). Springer-Verlag , Heidelberg, Germany, 1--18. Krishnamurthy, R., Kaushik, R., and Naughton, J. F. 2003. XML-SQL query translation literature: The state of the art and open problems. In Proceedings of the International XML Database Symposium (XSym). Springer-Verlag, Heidelberg, Germany, 1--18."},{"volume-title":"Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Lakshmanan L. V. S.","key":"e_1_2_1_19_1","unstructured":"Lakshmanan , L. V. S. , Ramesh , G. , Wang , H. , and Zhao , Z . 2004. On testing satisfiability of tree pattern queries . In Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan Kaufmann , San Mateo, CA, 120--131. Lakshmanan, L. V. S., Ramesh, G., Wang, H., and Zhao, Z. 2004. On testing satisfiability of tree pattern queries. In Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan Kaufmann, San Mateo, CA, 120--131."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647852.737555"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag","author":"Neven F.","key":"e_1_2_1_24_1","unstructured":"Neven , F. , and Schwentick , T . 2003. XPath containment in the presence of disjunction, DTDs, and variables . In Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag , Heidelberg, Germany, 312--326. Neven, F., and Schwentick, T. 2003. XPath containment in the presence of disjunction, DTDs, and variables. In Proceedings of the International Conference on Database Theory (ICDT). Springer-Verlag, Heidelberg, Germany, 312--326."},{"volume-title":"Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan-Kaufmann","author":"Popa L.","key":"e_1_2_1_25_1","unstructured":"Popa , L. , Velegrakis , Y. , Miller , R. J. , Hern\u00e1ndez , M. A. , and Fagin , R . 2002. Translating web data . In Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan-Kaufmann , San Mateo, CA, 598--609. Popa, L., Velegrakis, Y., Miller, R. J., Hern\u00e1ndez, M. A., and Fagin, R. 2002. Translating web data. In Proceedings of the International Conference Very Large Data Bases (VLDB). Morgan-Kaufmann, San Mateo, CA, 598--609."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/320544.320549"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375554"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007611"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1346330.1346332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346332"}},"subtitle":["Consistency and query answering"],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1346330.1346332"],"URL":"https:\/\/doi.org\/10.1145\/1346330.1346332","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2005-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}