NDLI: Partial Evaluation for Distributed XPath Query Processing and Beyond

Content Provider	ACM Digital Library
Author	Kementsietsidis, Anastasios Li, Jianzhong Fan, Wenfei Liu, Xianmin Cong, Gao
Copyright Year	2012
Description	Author Affiliation: Harbin Institute of Technology(University of edinburgh and harbin institute of technology (fan, Wenfei; Nanyang technological university (cong, Gao); Ibm t.j. watson research center (kementsietsidis, Anastasios); Liu, Xianmin); Li, Jianzhong)
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.
Starting Page	1
Ending Page	43
Page Count	43
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2389241.2389251
Volume Number	37
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Distributed XML documents XPath queries Parallel query processing
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed query evaluation with performance guarantees

Processing and Evaluating Partial Tree Pattern Queries on XML Data

Efficient algorithms for processing XPath queries

Revisiting answering tree pattern queries using views

Evaluation Techniques for Generalized Path Pattern Queries on XML Data

Distributed Evaluation of XPath Axes Queries over Large XML Documents Stored in MapReduce Clusters

Evaluating partial tree-pattern queries on XML streams

Using partial evaluation in distributed query evaluation (2006)

Using partial evaluation in distributed query evaluation (2006)

Partial Evaluation for Distributed XPath Query Processing and Beyond

Similar Documents

Distributed query evaluation with performance guarantees

Processing and Evaluating Partial Tree Pattern Queries on XML Data

Efficient algorithms for processing XPath queries

Revisiting answering tree pattern queries using views

Evaluation Techniques for Generalized Path Pattern Queries on XML Data

Distributed Evaluation of XPath Axes Queries over Large XML Documents Stored in MapReduce Clusters

Evaluating partial tree-pattern queries on XML streams

Using partial evaluation in distributed query evaluation (2006)

Using partial evaluation in distributed query evaluation (2006)

Partial Evaluation for Distributed XPath Query Processing and Beyond