{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:03Z","timestamp":1750307103707,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"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":["EP\/J015377\/1"],"award-info":[{"award-number":["EP\/J015377\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61133002"],"award-info":[{"award-number":["61133002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2012CB316200"],"award-info":[{"award-number":["2012CB316200"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>This article proposes algorithms for evaluating XPath queries over an XML tree that is partitioned horizontally and vertically, and is distributed across a number of sites. The key idea is based on partial evaluation: it is to send the whole query to each site that partially evaluates the query, in parallel, and sends the results as compact (Boolean) functions to a coordinator that combines these to obtain the result. This approach possesses the following performance guarantees. First, each site is visited at most twice for data-selecting XPath queries, and only once for Boolean XPath queries. Second, the network traffic is determined by the answer to the query, rather than the size of the tree. Third, the total computation is comparable to that of centralized algorithms on the tree stored in a single site, regardless of how the tree is fragmented and distributed. We also present a MapReduce algorithm for evaluating Boolean XPath queries, based on partial evaluation. In addition, we provide algorithms to evaluate XPath queries on very large XML trees, in a centralized setting. We show both analytically and empirically that our techniques are scalable with large trees and complex XPath queries. These results, we believe, illustrate the usefulness and potential of partial evaluation in distributed systems as well as centralized XML stores for evaluating XPath queries and beyond.<\/jats:p>","DOI":"10.1145\/2389241.2389251","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Partial Evaluation for Distributed XPath Query Processing and Beyond"],"prefix":"10.1145","volume":"37","author":[{"given":"Gao","family":"Cong","sequence":"first","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Harbin Institute of Technology"}]},{"given":"Anastasios","family":"Kementsietsidis","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology"}]},{"given":"Xianmin","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2012,12]]},"reference":[{"volume-title":"Proceedings of the International Conference on Very Large Databases. 1087--1090","author":"Abiteboul S.","key":"e_1_2_1_1_1","unstructured":"Abiteboul , S. , Benjelloun , O. , Manolescu , I. , Milo , T. , and Weber , R . 2002. Active XML: Peer-to-peer data and web services integration . In Proceedings of the International Conference on Very Large Databases. 1087--1090 . Abiteboul, S., Benjelloun, O., Manolescu, I., Milo, T., and Weber, R. 2002. Active XML: Peer-to-peer data and web services integration. In Proceedings of the International Conference on Very Large Databases. 1087--1090."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872821"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007596"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0049-y"},{"volume-title":"Proceedings of the International Conference on Data Engineering. 141","author":"Al-Khalifa S. A.","key":"e_1_2_1_5_1","unstructured":"Al-Khalifa , S. A. , Jagadish , H. V. , Koudas , N. , Patel , J. M. , Srivastava , D. , and Wu , Y . 2002. Structural joins: A primitive for efficient XML query pattern matching . In Proceedings of the International Conference on Data Engineering. 141 . Al-Khalifa, S. A., Jagadish, H. V., Koudas, N., Patel, J. M., Srivastava, D., and Wu, Y. 2002. Structural joins: A primitive for efficient XML query pattern matching. In Proceedings of the International Conference on Data Engineering. 141."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 53--64","author":"Altinel M.","key":"e_1_2_1_6_1","unstructured":"Altinel , M. and Franklin , M. J . 2000. Efficient filtering of XML documents for selective dissemination of information . In Proceedings of the International Conference on Very Large Databases. 53--64 . Altinel, M. and Franklin, M. J. 2000. Efficient filtering of XML documents for selective dissemination of information. In Proceedings of the International Conference on Very Large Databases. 53--64."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1269671"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.030"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142527"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2006.01.011"},{"volume-title":"Proceedings of the International XML Database Symposium. 346--357","author":"Bordawekar R.","key":"e_1_2_1_11_1","unstructured":"Bordawekar , R. and Shmueli , O . 2004. Flexible workload-aware clustering of XML documents . In Proceedings of the International XML Database Symposium. 346--357 . Bordawekar, R. and Shmueli, O. 2004. Flexible workload-aware clustering of XML documents. In Proceedings of the International XML Database Symposium. 346--357."},{"volume-title":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 73--78","author":"Bremer J.","key":"e_1_2_1_12_1","unstructured":"Bremer , J. and Gertz , M . 2003. On distributing XML repositories . In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 73--78 . Bremer, J. and Gertz, M. 2003. On distributing XML repositories. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 73--78."},{"volume-title":"Proceedings of the International Conference on Data Engineering. 139--150","author":"Bruno N.","key":"e_1_2_1_13_1","unstructured":"Bruno , N. , Gravano , L. , Koudas , N. , and Srivastava , D . 2003. Navigationvs index-based XML multi-query processing . In Proceedings of the International Conference on Data Engineering. 139--150 . Bruno, N., Gravano, L., Koudas, N., and Srivastava, D. 2003. Navigationvs index-based XML multi-query processing. In Proceedings of the International Conference on Data Engineering. 139--150."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 211--222","author":"Buneman P.","key":"e_1_2_1_15_1","unstructured":"Buneman , P. , Cong , G. , Fan , W. , and Kementsietsidis , A . 2006. Using partial evaluation in distributed query evaluation . In Proceedings of the International Conference on Very Large Databases. 211--222 . Buneman, P., Cong, G., Fan, W., and Kementsietsidis, A. 2006. Using partial evaluation in distributed query evaluation. In Proceedings of the International Conference on Very Large Databases. 211--222."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543648"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247537"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017082"},{"volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 137--150","author":"Dean J.","key":"e_1_2_1_19_1","unstructured":"Dean , J. and Ghemawat , S . 2004. MapReduce: Simplified data processing on large clusters . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 137--150 . Dean, J. and Ghemawat, S. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 137--150."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129894"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247515"},{"key":"e_1_2_1_22_1","first-page":"27","article-title":"Storing and querying XML data using an RDMBS","volume":"22","author":"Florescu D.","year":"1999","unstructured":"Florescu , D. and Kossmann , D. 1999 . Storing and querying XML data using an RDMBS . IEEE Data Eng. Bull. 22 , 27 -- 34 . Florescu, D. and Kossmann, D. 1999. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull. 22, 27--34.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_23_1","unstructured":"Galax. http:\/\/galax.sourceforge.net\/. Galax . http:\/\/galax.sourceforge.net\/."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 444--455","author":"Ganesan P.","key":"e_1_2_1_24_1","unstructured":"Ganesan , P. , Bawa , M. , and Garcia-Molina , H . 2004. Online balancing of range-partitioned data with applications to Peer-to-Peer systems . In Proceedings of the International Conference on Very Large Databases. 444--455 . Ganesan, P., Bawa, M., and Garcia-Molina, H. 2004. Online balancing of range-partitioned data with applications to Peer-to-Peer systems. In Proceedings of the International Conference on Very Large Databases. 444--455."},{"volume-title":"Proceedings of the International Joint Conference on Intelligent Information Systems. 337--349","author":"Godfrey P.","key":"e_1_2_1_25_1","unstructured":"Godfrey , P. and Gryz , J . 2000. A strategy for partial evaluation of views . In Proceedings of the International Joint Conference on Intelligent Information Systems. 337--349 . Godfrey, P. and Gryz, J. 2000. A strategy for partial evaluation of views. In Proceedings of the International Joint Conference on Intelligent Information Systems. 337--349."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 95--106","author":"Gottlob G.","key":"e_1_2_1_26_1","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2002. Efficient algorithms for processing XPath queries . In Proceedings of the International Conference on Very Large Databases. 95--106 . Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the International Conference on Very Large Databases. 95--106."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182597"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1318562"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645475.654157"},{"volume-title":"Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications. 107--118","author":"Huck G.","key":"e_1_2_1_30_1","unstructured":"Huck , G. , Macherius , I. , and Fankhauser , P . 1999. PDOM: Lightweight persistency support for the document object model . In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications. 107--118 . Huck, G., Macherius, I., and Fankhauser, P. 1999. PDOM: Lightweight persistency support for the document object model. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications. 107--118."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0078-5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304194"},{"volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. 661--672","author":"Jagadish H. V.","key":"e_1_2_1_33_1","unstructured":"Jagadish , H. V. , Ooi , B. C. , and Vu , Q. H . 2005. Baton: A balanced tree structure for peer-to-peer networks . In Proceedings of the ACM SIGMOD International Conference on Management of Data. 661--672 . Jagadish, H. V., Ooi, B. C., and Vu, Q. H. 2005. Baton: A balanced tree structure for peer-to-peer networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 661--672."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/243439.243447"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066242"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.452.0321"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 91--102","author":"Kanne C.-C.","key":"e_1_2_1_37_1","unstructured":"Kanne , C.-C. and Moerkotte , G . 2006b. A linear time algorithm for optimal tree sibling partitioning and approximation algorithms in Natix . In Proceedings of the International Conference on Very Large Databases. 91--102 . Kanne, C.-C. and Moerkotte, G. 2006b. A linear time algorithm for optimal tree sibling partitioning and approximation algorithms in Natix. In Proceedings of the International Conference on Very Large Databases. 91--102."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564707"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880173"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Conference on Very Large Databases. 249--260","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. 249--260 . 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. 249--260."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/371578.371598"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206012"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 193--204","author":"Lu J.","key":"e_1_2_1_43_1","unstructured":"Lu , J. , Ling , T. W. , Chan , C. Y. , and Chen , T . 2005. From region encoding to extended dewey: On efficient processing of XML twig pattern matching . In Proceedings of the International Conference on Very Large Databases. 193--204 . Lu, J., Ling, T. W., Chan, C. Y., and Chen, T. 2005. From region encoding to extended dewey: On efficient processing of XML twig pattern matching. In Proceedings of the International Conference on Very Large Databases. 193--204."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.183.0217"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 213--224","author":"Marian A.","key":"e_1_2_1_45_1","unstructured":"Marian , A. and Sim\u00e9on , J . 2003. Projecting XML documents . In Proceedings of the International Conference on Very Large Databases. 213--224 . Marian, A. and Sim\u00e9on, J. 2003. Projecting XML documents. In Proceedings of the International Conference on Very Large Databases. 213--224."},{"volume-title":"Proceedings of the International Conference on Database Theory. 277--295","author":"Milo T.","key":"e_1_2_1_46_1","unstructured":"Milo , T. and Suciu , D . 1999. Index structures for path expressions . In Proceedings of the International Conference on Database Theory. 277--295 . Milo, T. and Suciu, D. 1999. Index structures for path expressions. In Proceedings of the International Conference on Database Theory. 277--295."},{"key":"e_1_2_1_47_1","unstructured":"MonetDB. http:\/\/monetdb.cwi.nl\/projects\/monetdb\/xquery \/index.html. MonetDB . http:\/\/monetdb.cwi.nl\/projects\/monetdb\/xquery \/index.html."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 1146--1157","author":"Pal S.","key":"e_1_2_1_48_1","unstructured":"Pal , S. , Cseri , I. , Schaller , G. , Seeliger , O. , Giakoumakis , L. , and Zolotov , V . 2004. Indexing XML data stored in a relational database . In Proceedings of the International Conference on Very Large Databases. 1146--1157 . Pal, S., Cseri, I., Schaller, G., Seeliger, O., Giakoumakis, L., and Zolotov, V. 2004. Indexing XML data stored in a relational database. In Proceedings of the International Conference on Very Large Databases. 1146--1157."},{"volume-title":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 95--100","author":"Papadimos V.","key":"e_1_2_1_49_1","unstructured":"Papadimos , V. and Maier , D . 2002. Distributed queries without distributed state . In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 95--100 . Papadimos, V. and Maier, D. 2002. Distributed queries without distributed state. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 95--100."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_51_1","unstructured":"Saxon. http:\/\/saxon.sourceforge.net\/. Saxon . http:\/\/saxon.sourceforge.net\/."},{"volume-title":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 137--150","author":"Schmidt A.","key":"e_1_2_1_52_1","unstructured":"Schmidt , A. , Kersten , M. L. , Windhouwer , M. , and Waas , F . 2000. Efficient relational storage and retrieval of XML documents . In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 137--150 . Schmidt, A., Kersten, M. L., Windhouwer, M., and Waas, F. 2000. Efficient relational storage and retrieval of XML documents. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 137--150."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 974--985","author":"Schmidt A.","key":"e_1_2_1_53_1","unstructured":"Schmidt , A. , Waas , F. , Kersten , M. , Carey , M. , Manolescu , I. , and Busse , R . 2002. XMark: A benchmark for XML data management . In Proceedings of the International Conference on Very Large Databases. 974--985 . Schmidt, A., Waas, F., Kersten, M., Carey, M., Manolescu, I., and Busse, R. 2002. XMark: A benchmark for XML data management. In Proceedings of the International Conference on Very Large Databases. 974--985."},{"key":"e_1_2_1_54_1","volume-title":"LDAP: Programming Directory-Enabled Apps. Sams.","author":"Smith M.","year":"1997","unstructured":"Smith , M. and Howes , T. A . 1997 . LDAP: Programming Directory-Enabled Apps. Sams. Smith, M. and Howes, T. A. 1997. LDAP: Programming Directory-Enabled Apps. Sams."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/507234.507235"},{"volume-title":"Proceedings of the IEEE International Conference on Distributed Computing Systems. 449--457","author":"Tomasic A.","key":"e_1_2_1_56_1","unstructured":"Tomasic , A. , Raschid , L. , and Valduriez , P . 1996. Scaling heterogeneous databases and the design of Disco . In Proceedings of the IEEE International Conference on Distributed Computing Systems. 449--457 . Tomasic, A., Raschid, L., and Valduriez, P. 1996. Scaling heterogeneous databases and the design of Disco. In Proceedings of the IEEE International Conference on Distributed Computing Systems. 449--457."},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 99--110","author":"Zhang Y.","key":"e_1_2_1_57_1","unstructured":"Zhang , Y. and Boncz , P. A . 2007. XRPC: Interoperable and efficient distributed XQuery . In Proceedings of the International Conference on Very Large Databases. 99--110 . Zhang, Y. and Boncz, P. A. 2007. XRPC: Interoperable and efficient distributed XQuery. In Proceedings of the International Conference on Very Large Databases. 99--110."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375722"},{"volume-title":"Proceedings of the International Conference on Data Engineering. 54","author":"Zhang N.","key":"e_1_2_1_59_1","unstructured":"Zhang , N. , Kacholia , V. , and Ozsu , M. T . 2004. A succinct physical storage scheme for efficient evaluation of path queries in XML . In Proceedings of the International Conference on Data Engineering. 54 . Zhang, N., Kacholia, V., and Ozsu, M. T. 2004. A succinct physical storage scheme for efficient evaluation of path queries in XML. In Proceedings of the International Conference on Data Engineering. 54."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.79"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389251","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2389241.2389251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:58Z","timestamp":1750239298000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2389241.2389251"],"URL":"https:\/\/doi.org\/10.1145\/2389241.2389251","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}