Partial Evaluation for Distributed XPath Query Processing and Beyond
Open Access
- 1 December 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 37 (4) , 1-43
Abstract
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.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/J015377/1)
- National Natural Science Foundation of China (61133002)
- Ministry of Science and Technology of the People's Republic of China (2012CB316200)
This publication has 29 references indexed in Scilit:
- The Active XML project: an overviewThe VLDB Journal, 2007
- Storing and retrieving XPath fragments in structured P2P networksData & Knowledge Engineering, 2006
- Structural properties of XPath fragmentsTheoretical Computer Science, 2005
- The Piazza Peer Data Management SystemIEEE Transactions on Knowledge and Data Engineering, 2004
- Distributed evaluation of network directory queriesIEEE Transactions on Knowledge and Data Engineering, 2004
- An XML query engine for network-bound dataThe VLDB Journal, 2002
- Distributed query evaluation on semistructured dataACM Transactions on Database Systems, 2002
- The state of the art in distributed query processingACM Computing Surveys, 2000
- An introduction to partial evaluationACM Computing Surveys, 1996
- Parallel database systemsCommunications of the ACM, 1992