Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-15251-1_31
Title: Reducing graph matching to tree matching for XML queries with ID references
Authors: Wu, H.
Ling, T.W. 
Dobbie, G.
Bao, Z.
Xu, L.
Issue Date: 2010
Source: Wu, H.,Ling, T.W.,Dobbie, G.,Bao, Z.,Xu, L. (2010). Reducing graph matching to tree matching for XML queries with ID references. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6262 LNCS (PART 2) : 391-406. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-15251-1_31
Abstract: ID/IDREF is an important and widely used feature in XML documents for eliminating data redundancy. Most existing algorithms consider an XML document with ID references as a graph and perform graph matching for queries involving ID references. Graph matching naturally brings higher complexity compared with original tree matching algorithms that process XML queries. In this paper, we make use of semantics of ID/IDREF to reduce graph matching to tree matching to process queries involving ID references. Using our approach, an XML document with ID/IDREF is not treated as a graph, and a general query with ID references will be decomposed and processed using tree pattern matching techniques, which are more efficient than graph matching. Furthermore, our approach is able to handle complex ID references, such as cyclic references and sequential references, which cannot be handled efficiently by existing approaches. The experimental results show that our approach is 20-50% faster than MonetDB, an XQuery engine, and at least 100 times faster than TwigStackD, an existing graph matching algorithm. © 2010 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41591
ISBN: 3642152503
ISSN: 03029743
DOI: 10.1007/978-3-642-15251-1_31
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

7
checked on Dec 13, 2017

Page view(s)

61
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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