{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:54Z","timestamp":1759638294567,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"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":["E005039F028288G049165"],"award-info":[{"award-number":["E005039F028288G049165"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7-ICT-233599"],"award-info":[{"award-number":["FP7-ICT-233599"]}],"id":[{"id":"10.13039\/501100004963","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":["11080011"],"award-info":[{"award-number":["11080011"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>We study models of incomplete information for XML, their computational properties, and query answering. While our approach is motivated by the study of relational incompleteness, incomplete information in XML documents may appear not only as null values but also as missing structural information. Our goal is to provide a classification of incomplete descriptions of XML documents, and separate features\u2014or groups of features\u2014that lead to hard computational problems from those that admit efficient algorithms. Our classification of incomplete information is based on the combination of null values with partial structural descriptions of documents. The key computational problems we consider are consistency of partial descriptions, representability of complete documents by incomplete ones, and query answering. We show how factors such as schema information, the presence of node ids, and missing structural information affect the complexity of these main computational problems, and find robust classes of incomplete XML descriptions that permit tractable query evaluation.<\/jats:p>","DOI":"10.1145\/1870103.1870107","type":"journal-article","created":{"date-parts":[[2010,12,22]],"date-time":"2010-12-22T14:41:31Z","timestamp":1293028891000},"page":"1-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["XML with incomplete information"],"prefix":"10.1145","volume":"58","author":[{"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonella","family":"Poggi","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina","family":"Sirangelo","sequence":"additional","affiliation":[{"name":"ENS-Cachan and INRIA, Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,12,21]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_2_2_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132869"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00294-2"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646895"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346332"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559832"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the International Symposium on Database Programming Languages, M. Arenas and M. I. Schwartzbach, Eds. Lecture Notes in Computer Science","volume":"4797","author":"Bj\u00f6rklund H.","unstructured":"Bj\u00f6rklund , H. , Martens , W. , and Schwentick , T . 2007. Conjunctive query containment over trees . In Proceedings of the International Symposium on Database Programming Languages, M. Arenas and M. I. Schwartzbach, Eds. Lecture Notes in Computer Science , vol. 4797 . Springer, 66--80. Bj\u00f6rklund, H., Martens, W., and Schwentick, T. 2007. Conjunctive query containment over trees. In Proceedings of the International Symposium on Database Programming Languages, M. Arenas and M. I. Schwartzbach, Eds. Lecture Notes in Computer Science, vol. 4797. Springer, 66--80."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85238-4_10"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"volume-title":"Proceedings of the Workshop on Description Logics.","author":"Calvanese D.","key":"e_1_2_2_13_1","unstructured":"Calvanese , D. , Giacomo , G. D. , and Lenzerini , M . 1998. Semi-structured data with constraints and incomplete information . In Proceedings of the Workshop on Description Logics. Calvanese, D., Giacomo, G. D., and Lenzerini, M. 1998. Semi-structured data with constraints and incomplete information. In Proceedings of the Workshop on Description Logics."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/9.3.295"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376933"},{"key":"e_1_2_2_16_1","unstructured":"Date C. and Darwin H. 1996. A Guide to the SQL Standard. Addison-Wesley.  Date C. and Darwin H. 1996. A Guide to the SQL Standard. Addison-Wesley."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85238-4_22"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 225--241","author":"Deutsch A.","key":"e_1_2_2_18_1","unstructured":"Deutsch , A. , and Tannen , V . 2003. Reformulation of XML Queries and Constraints . In Proceedings of the International Conference on Database Theory (ICDT). 225--241 . Deutsch, A., and Tannen, V. 2003. Reformulation of XML Queries and Constraints. In Proceedings of the International Conference on Database Theory (ICDT). 225--241."},{"key":"e_1_2_2_19_1","unstructured":"DOM. April 2004. Document object model (DOM). W3C recommendation. http:\/\/www.w3.org\/ TR\/DOM-Level-3-Core\/.  DOM. April 2004. Document object model (DOM). W3C recommendation. http:\/\/www.w3.org\/ TR\/DOM-Level-3-Core\/."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559827"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376953"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1811"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Kolaitis P. and Vardi M. 2007. A logical approach to constraint satisfaction. In Finite Model Theory and Its Applications. Springer 339--370.  Kolaitis P. and Vardi M. 2007. A logical approach to constraint satisfaction. In Finite Model Theory and Its Applications. Springer 339--370.","DOI":"10.1007\/3-540-68804-8_6"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_2_29_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory 1 st Ed. Springer-Verlag . Libkin, L. 2004. Elements of Finite Model Theory 1st Ed. Springer-Verlag.","edition":"1"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.004"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science. 17--18","author":"Schwentick T.","year":"2008","unstructured":"Schwentick , T. 2008 . A little bit infinite&quest; On adding data to finitely labelled structures . In Proceedings of the Symposium on Theoretical Aspects of Computer Science. 17--18 . Schwentick, T. 2008. A little bit infinite&quest; On adding data to finitely labelled structures. In Proceedings of the Symposium on Theoretical Aspects of Computer Science. 17--18."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_3"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265570"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568321"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90016-4"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870103.1870107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1870103.1870107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:47Z","timestamp":1750244387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870103.1870107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1870103.1870107"],"URL":"https:\/\/doi.org\/10.1145\/1870103.1870107","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2009-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}