Please use this identifier to cite or link to this item:
Title: Efficient processing of partially specified twig pattern queries
Authors: Zhou, J.F.
Meng, X.F.
Ling, T.W. 
Keywords: Holistic twig join
Partially specified twig pattern
Query processing
XML database
Issue Date: 2009
Citation: Zhou, J.F., Meng, X.F., Ling, T.W. (2009). Efficient processing of partially specified twig pattern queries. Science in China, Series F: Information Sciences 52 (10) : 1830-1847. ScholarBank@NUS Repository.
Abstract: As huge volumes of data are organized or exported in tree-structured form, it is quite necessary to extract useful information from these data collections using effective and efficient query processing methods. A natural way of retrieving desired information from XML documents is using twig pattern (TP), which is, actually, the core component of existing XML query languages. Twig pattern possesses the inherent feature that query nodes on the same path have concrete precedence relationships. It is this feature that makes it infeasible in many actual scenarios. This has driven the requirement of relaxing the complete specification of a twig pattern to express more flexible semantic constraints in a single query expression. In this paper, we focus on query evaluation of partially specified twig pattern (PSTP) queries, through which we can reap the most flexibility of specifying partial semantic constraints in a query expression. We propose an extension to XPath through introducing two Samepath axes to support partial semantic constraints in a concise but effective way. Then we propose a stack based algorithm, pTwigStack, to process a PSTP holistically without deriving the concrete twig patterns and then processing them one by one. Further, we propose two DTD schema based optimization methods to improve the performance of pTwigStack algorithm. Our experimental results on various datasets indicate that our method performs significantly better than existing ones when processing PSTPs. © Science in China Press and Springer Berlin Heidelberg 2009.
Source Title: Science in China, Series F: Information Sciences
ISSN: 10092757
DOI: 10.1007/s11432-009-0152-3
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 20, 2019

Page view(s)

checked on Feb 9, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.