Please use this identifier to cite or link to this item: https://doi.org/10.1109/TKDE.2010.126
Title: Extended XML tree pattern matching: Theories and algorithms
Authors: Lu, J.
Ling, T.W. 
Bao, Z.
Wang, C.
Keywords: algorithms
Query processing
tree pattern
XML/XSL/RDF
Issue Date: 2011
Source: Lu, J., Ling, T.W., Bao, Z., Wang, C. (2011). Extended XML tree pattern matching: Theories and algorithms. IEEE Transactions on Knowledge and Data Engineering 23 (3) : 402-416. ScholarBank@NUS Repository. https://doi.org/10.1109/TKDE.2010.126
Abstract: As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about "matching cross" which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms. © 2006 IEEE.
Source Title: IEEE Transactions on Knowledge and Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/39331
ISSN: 10414347
DOI: 10.1109/TKDE.2010.126
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

26
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

14
checked on Nov 22, 2017

Page view(s)

69
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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