{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:59Z","timestamp":1759639019075,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"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":[[2013,4]]},"abstract":"<jats:p>\n            XML data projection (or pruning) is a natural optimization for main memory query engines: given a query\n            <jats:italic>Q<\/jats:italic>\n            over a document\n            <jats:italic>D<\/jats:italic>\n            , the subtrees of\n            <jats:italic>D<\/jats:italic>\n            that are not necessary to evaluate\n            <jats:italic>Q<\/jats:italic>\n            are pruned, thus producing a smaller document\n            <jats:italic>D'<\/jats:italic>\n            ; the query\n            <jats:italic>Q<\/jats:italic>\n            is then executed on\n            <jats:italic>D'<\/jats:italic>\n            , hence avoiding to allocate and process nodes that will never be reached by\n            <jats:italic>Q<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>In this article, we propose a new approach, based on types, that greatly improves current solutions. Besides providing comparable or greater precision and far lesser pruning overhead, our solution\u2014unlike current approaches\u2014takes into account backward axes, predicates, and can be applied to multiple queries rather than just to single ones. A side contribution is a new type system for XPath able to handle backward axes. The soundness of our approach is formally proved. Furthermore, we prove that the approach is also complete (i.e., yields the best possible type-driven pruning) for a relevant class of queries and Schemas. We further validate our approach using the XMark and XPathMark benchmarks and show that pruning not only improves the main memory query engine's performances (as expected) but also those of state of the art native XML databases.<\/jats:p>","DOI":"10.1145\/2445583.2445587","type":"journal-article","created":{"date-parts":[[2013,4,23]],"date-time":"2013-04-23T13:04:26Z","timestamp":1366722266000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimizing XML querying using type-based document projection"],"prefix":"10.1145","volume":"38","author":[{"given":"V\u00e9ronique","family":"Benzaken","sequence":"first","affiliation":[{"name":"LRI, Universit\u00e9 Paris-Sud, CNRS, Orsay F-91405, France"}]},{"given":"Giuseppe","family":"Castagna","sequence":"additional","affiliation":[{"name":"CNRS, Universit\u00e9 Paris Diderot, Sorbonne Paris Cit\u00e9, Paris, France"}]},{"given":"Dario","family":"Colazzo","sequence":"additional","affiliation":[{"name":"LRI, Universit\u00e9 Paris-Sud, CNRS, Orsay F-91405, France"}]},{"given":"Kim","family":"Nguy\u02dc\u02c6en","sequence":"additional","affiliation":[{"name":"LRI, Universit\u00e9 Paris-Sud, CNRS, Orsay F-91405, France"}]}],"member":"320","published-online":{"date-parts":[[2013,4,26]]},"reference":[{"volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments. SIAM Press.","author":"Arroyuelo D.","key":"e_1_2_2_1_1","unstructured":"Arroyuelo , D. , C\u00e1novas , R. , Navarro , G. , and Sadakane , K . 2010. Succinct trees in practice . In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments. SIAM Press. Arroyuelo, D., C\u00e1novas, R., Navarro, G., and Sadakane, K. 2010. Succinct trees in practice. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments. SIAM Press."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456650.1456653"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/112198.112207"},{"volume-title":"Proceedings of the Workshop on Persistent Object Systems. Morgan Kaufmann.","author":"Benzaken V.","key":"e_1_2_2_5_1","unstructured":"Benzaken , V. and Delobel , C . 1990. Enhancing performance in a persistent object store: clustering strategies in O2 . In Proceedings of the Workshop on Persistent Object Systems. Morgan Kaufmann. Benzaken, V. and Delobel, C. 1990. Enhancing performance in a persistent object store: clustering strategies in O2. In Proceedings of the Workshop on Persistent Object Systems. Morgan Kaufmann."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30557-6_18"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'06)","author":"Benzaken V.","year":"2006","unstructured":"Benzaken , V. , Castagna , G. , Colazzo , D. , and Nguy &tilde;\u00ean, K. 2006 . Type-based XML projection . In Proceedings of the International Conference on Very Large Databases (VLDB'06) . 271--282. Benzaken, V., Castagna, G., Colazzo, D., and Nguy&tilde;\u00ean, K. 2006. Type-based XML projection. In Proceedings of the International Conference on Very Large Databases (VLDB'06). 271--282."},{"key":"e_1_2_2_8_1","unstructured":"Benzaken V. Delobel C. and Harrus G. 1992. Clustering strategies in O2: An overview. In Building an Object-Oriented Database System: The Story of O2 F. Bancilhon C. Delobel and P. Kanellakis Eds. Morgan Kaufman 385--410.   Benzaken V. Delobel C. and Harrus G. 1992. Clustering strategies in O 2 : An overview. In Building an Object-Oriented Database System: The Story of O 2 F. Bancilhon C. Delobel and P. Kanellakis Eds. Morgan Kaufman 385--410."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367609"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 115--126","author":"Bex G. J.","key":"e_1_2_2_10_1","unstructured":"Bex , G. J. , Neven , F. , Schwentick , T. , and Tuyls , K . 2006. Inference of concise DTDs from XML data . In Proceedings of the International Conference on Very Large Databases. 115--126 . Bex, G. J., Neven, F., Schwentick, T., and Tuyls, K. 2006. Inference of concise DTDs from XML data. In Proceedings of the International Conference on Very Large Databases. 115--126."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142527"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2004.12.003"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1069774.1069793"},{"key":"e_1_2_2_15_1","unstructured":"CDuce 2004-2011. The CDuce language. http:\/\/www.cduce.org.  CDuce 2004-2011. The CDuce language. http:\/\/www.cduce.org."},{"key":"e_1_2_2_16_1","unstructured":"Chamberlin D. Fankhauser P. Florescu D. Marchiori M. and Robie J. 2003. XML query use cases. Tech. rep. 20030822 World Wide Web Consortium.  Chamberlin D. Fankhauser P. Florescu D. Marchiori M. and Robie J. 2003. XML query use cases. Tech. rep. 20030822 World Wide Web Consortium."},{"volume-title":"What are real DTDs like&quest","author":"Choi B.","key":"e_1_2_2_17_1","unstructured":"Choi , B. 2002. What are real DTDs like&quest ; In Proceedings of the 5th International Workshop on the Web and Databases (WebDB '02). 43--48. Choi, B. 2002. What are real DTDs like&quest; In Proceedings of the 5th International Workshop on the Web and Databases (WebDB'02). 43--48."},{"key":"e_1_2_2_18_1","unstructured":"Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1997. Tree automata techniques and applications. http:\/\/www.grappa.univ-lille3.fr\/tata.  Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1997. Tree automata techniques and applications. http:\/\/www.grappa.univ-lille3.fr\/tata."},{"key":"e_1_2_2_19_1","unstructured":"Dom 2004. W3C: DOM specifications. http:\/\/www.w3.org\/TR\/DOMTR.  Dom 2004. W3C: DOM specifications. http:\/\/www.w3.org\/TR\/DOMTR."},{"key":"e_1_2_2_20_1","unstructured":"Draper D. Fankhauser P. Fernandez M. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2007. XQuery 1.0 and XPath 2.0 formal semantics. Tech. rep. World Wide Web Consortium.  Draper D. Fankhauser P. Fernandez M. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2007. XQuery 1.0 and XPath 2.0 formal semantics. Tech. rep. World Wide Web Consortium."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11547273_10"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391293"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185877.1185882"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042051"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'03)","author":"Grust T.","key":"e_1_2_2_26_1","unstructured":"Grust , T. , van Keulen , M. , and Teubner , J . 2003. Staircase join: Teach a relational DBMS to watch its (axis) steps . In Proceedings of the International Conference on Very Large Databases (VLDB'03) . 524--535. Grust, T., van Keulen, M., and Teubner, J. 2003. Staircase join: Teach a relational DBMS to watch its (axis) steps. In Proceedings of the International Conference on Very Large Databases (VLDB'03). 524--535."},{"key":"e_1_2_2_27_1","first-page":"65","article-title":"Ten reasons why Saxon XQuery is fast","volume":"31","author":"Kay M.","year":"2008","unstructured":"Kay , M. 2008 . Ten reasons why Saxon XQuery is fast . IEEE Data Eng. Bull. 31 , 4, 65 -- 74 . Kay, M. 2008. Ten reasons why Saxon XQuery is fast. IEEE Data Eng. Bull. 31, 4, 65--74.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'03)","author":"Koch C.","year":"2003","unstructured":"Koch , C. 2003 . Efficient processing of expressive node-selecting queries on XML data in secondary storage: a tree automata-based approach . In Proceedings of the International Conference on Very Large Databases (VLDB'03) . Koch, C. 2003. Efficient processing of expressive node-selecting queries on XML data in secondary storage: a tree automata-based approach. In Proceedings of the International Conference on Very Large Databases (VLDB'03)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189771"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'03)","author":"Marian A.","key":"e_1_2_2_30_1","unstructured":"Marian , A. and Sim\u00e9on , J . 2003. Projecting XML documents . In Proceedings of the International Conference on Very Large Databases (VLDB'03) . 213--224. Marian, A. and Sim\u00e9on, J. 2003. Projecting XML documents. In Proceedings of the International Conference on Very Large Databases (VLDB'03). 213--224."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_5"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646146.678868"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'02)","author":"Schmidt A.","key":"e_1_2_2_36_1","unstructured":"Schmidt , A. , Waas , F. , Kersten , M. L. , Carey , M. J. , Manolescu , I. , and Busse , R . 2002. XMark: A benchmark for XML data management . In Proceedings of the International Conference on Very Large Databases (VLDB'02) . 974--985. Schmidt, A., Waas, F., Kersten, M. L., Carey, M. J., Manolescu, I., and Busse, R. 2002. XMark: A benchmark for XML data management. In Proceedings of the International Conference on Very Large Databases (VLDB'02). 974--985."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"volume-title":"W3C: XML Version 1.0","author":"Xml","key":"e_1_2_2_38_1","unstructured":"Xml 2008. W3C: XML Version 1.0 ( Fifth Edition). http:\/\/www.w3.org\/TR\/REC-xml\/. Xml 2008. W3C: XML Version 1.0 (Fifth Edition). http:\/\/www.w3.org\/TR\/REC-xml\/."},{"key":"e_1_2_2_39_1","unstructured":"XPath 1999. W3C: XML path language (XPath) version 1.0. http:\/\/www.w3.org\/TR\/xpath.  XPath 1999. W3C: XML path language (XPath) version 1.0. http:\/\/www.w3.org\/TR\/xpath."},{"key":"e_1_2_2_40_1","unstructured":"Xpathmark. Xpathmark Web Site (M. Franceschet). http:\/\/sole.dimi.uniud.it\/~massimo.franceschet\/xpath mark\/.  Xpathmark. Xpathmark Web Site (M. Franceschet). http:\/\/sole.dimi.uniud.it\/~massimo.franceschet\/xpath mark\/."},{"key":"e_1_2_2_41_1","unstructured":"XQuery 2010. W3C: XML query (XQuery). http:\/\/www.w3.org\/TR\/xquery.  XQuery 2010. W3C: XML query (XQuery). http:\/\/www.w3.org\/TR\/xquery."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2445583.2445587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:09Z","timestamp":1750239249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2445583.2445587"],"URL":"https:\/\/doi.org\/10.1145\/2445583.2445587","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}