{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T12:44:25Z","timestamp":1791117865926,"version":"4.1.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>We study the representation and querying of XML with incomplete information. We consider a simple model for XML data and their DTDs, a very simple query language, and a representation system for incomplete information in the spirit of the representations systems developed by Imielinski and Lipski [1984] for relational databases. In the scenario we consider, the incomplete information about an XML document is continuously enriched by successive queries to the document. We show that our representation system can represent partial information about the source document acquired by successive queries, and that it can be used to intelligently answer new queries. We also consider the impact on complexity of enriching our representation system or query language with additional features. The results suggest that our approach achieves a practically appealing balance between expressiveness and tractability.<\/jats:p>","DOI":"10.1145\/1132863.1132869","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"208-254","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Representing and querying XML with incomplete information"],"prefix":"10.1145","volume":"31","author":[{"given":"Serge","family":"Abiteboul","sequence":"first","affiliation":[{"name":"INRIA-Futurs, Orsay, Orsay Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[{"name":"INRIA-Futurs, Orsay, Orsay Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[{"name":"University of California, San Diego"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007596"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_3_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.]]   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375571"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375730"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).]]","author":"Balmin A.","unstructured":"Balmin , A. , Ozcan , F. , Beyer , K. , Cochrane , R. , and Pirahesh , H . 2004. A framework for using materialized XPath views in XML query processing . In Proceedings of the International Conference on Very Large Data Bases (VLDB).]] Balmin, A., Ozcan, F., Beyer, K., Cochrane, R., and Pirahesh, H. 2004. A framework for using materialized XPath views in XML query processing. In Proceedings of the International Conference on Very Large Data Bases (VLDB).]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT).]]","author":"Beeri C.","unstructured":"Beeri , C. and Milo , T . 1999. Schemas for integration and translation of structured and semi-structured data . In Proceedings of the International Conference on Database Theory (ICDT).]] Beeri, C. and Milo, T. 1999. Schemas for integration and translation of structured and semi-structured data. In Proceedings of the International Conference on Database Theory (ICDT).]]"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the WebDB.]]","author":"Bose S.","unstructured":"Bose , S. and Fegaras , L . 2005. XFrag: A query processing framework for fragmented XML data . In Proceedings of the WebDB.]] Bose, S. and Fegaras, L. 2005. XFrag: A query processing framework for fragmented XML data. In Proceedings of the WebDB.]]"},{"key":"e_1_2_1_10_1","unstructured":"Bruggemann-Klein M.Murata A. and Wood D. 1998. Regular tree languages over non-ranked alphabets. Unpublished manuscript.]]  Bruggemann-Klein M.Murata A. and Wood D. 1998. Regular tree languages over non-ranked alphabets. Unpublished manuscript.]]"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Description Logic Workshop (DL'98)","author":"Calvanese D.","unstructured":"Calvanese , D. , De Giacomo , G. , and Lenzerini , M . 1998. Semi-structured data with constraints and incomplete information . In Proceedings of the Description Logic Workshop (DL'98) . 11--20.]] Calvanese, D., De Giacomo, G., and Lenzerini, M. 1998. Semi-structured data with constraints and incomplete information. In Proceedings of the Description Logic Workshop (DL'98). 11--20.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303996"},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Data Engineering. 389--398","author":"Calvanese D.","unstructured":"Calvanese , D. , Giacomo , G. D. , Lenzerini , M. , and Vardi , M . 2000a. Answering regular path queries using views . In International Conference on Data Engineering. 389--398 .]] Calvanese, D., Giacomo, G. D., Lenzerini, M., and Vardi, M. 2000a. Answering regular path queries using views. In International Conference on Data Engineering. 389--398.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335207"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543646"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering.]]","author":"Chaudhuri S.","unstructured":"Chaudhuri , S. , Krishnamurthy , R. , Potamianos , S. , and Shim , K . 1995. Optimizing queries with materialized views . In Proceedings of the IEEE International Conference on Data Engineering.]] Chaudhuri, S., Krishnamurthy, R., Potamianos, S., and Shim, K. 1995. Optimizing queries with materialized views. In Proceedings of the IEEE International Conference on Data Engineering.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276321"},{"key":"e_1_2_1_18_1","unstructured":"Codd T. 1975. Understanding relations (installment &num;7). FDT Bull. of ACM Sigmod 7. 23--28.]]  Codd T. 1975. Understanding relations (installment &num;7). FDT Bull. of ACM Sigmod 7. 23--28.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80059-X"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International XML Database Symposium. 238--253","author":"Flesca S.","unstructured":"Flesca , S. , Furfaro 1, F., Greco , S. , and Zumpano , E . 2003. Repairs and consistent answers for xml data with functional dependencies . In Proceedings of the International XML Database Symposium. 238--253 .]] Flesca, S., Furfaro1, F., Greco, S., and Zumpano, E. 2003. Repairs and consistent answers for xml data with functional dependencies. In Proceedings of the International XML Database Symposium. 238--253.]]"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).]]","author":"Garcia-Molina H.","unstructured":"Garcia-Molina , H. , Labio , W. , and Yang , J . 1998. Expiring data in a warehouse . In Proceedings of the International Conference on Very Large Data Bases (VLDB).]] Garcia-Molina, H., Labio, W., and Yang, J. 1998. Expiring data in a warehouse. In Proceedings of the International Conference on Very Large Data Bases (VLDB).]]"},{"key":"e_1_2_1_22_1","volume-title":"The Problem of Incomplete Information in Relational Databases","author":"Grahne G.","unstructured":"Grahne , G. 1991. The Problem of Incomplete Information in Relational Databases . Springer-Verlag , Berlin Heidelberg , Germany.]] Grahne, G. 1991. The Problem of Incomplete Information in Relational Databases. Springer-Verlag, Berlin Heidelberg, Germany.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/369275.369284"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90114-3"},{"key":"e_1_2_1_25_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.]]   Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303999"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253405"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322280"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).]]","author":"Mandhani B.","unstructured":"Mandhani , B. and Suciu , D . 2005. Query caching and view selection for XML databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB).]] Mandhani, B. and Suciu, D. 2005. Query caching and view selection for XML databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB).]]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872793"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00030-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220199"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5388"},{"key":"e_1_2_1_39_1","unstructured":"Schwentick T. 2000. Personal communication.]]  Schwentick T. 2000. Personal communication.]]"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15419"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90080-1"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132869","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132869"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132869","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}