eCite Digital Repository

Reducing graph matching to tree matching for XML queries with ID references


Wu, H and Ling, TW and Dobbie, G and Bao, Z and Xu, L, Reducing graph matching to tree matching for XML queries with ID references, Database and Expert Systems Applications Part II, 30 August - 3 September 2010, Bilbao, Spain, pp. 391-406. ISBN 978-3-642-15250-4 (2010) [Refereed Conference Paper]

Copyright Statement

Copyright 2011 Springer

DOI: doi:10.1007/978-3-642-15251-1_31


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, wemake 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.

Item Details

Item Type:Refereed Conference Paper
Keywords:graph matching, graph database
Research Division:Information and Computing Sciences
Research Group:Data management and data science
Research Field:Data management and data science not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Bao, Z (Dr Zhifeng Bao)
ID Code:92193
Year Published:2010
Web of Science® Times Cited:4
Deposited By:Information and Communication Technology
Deposited On:2014-06-09
Last Modified:2015-02-12

Repository Staff Only: item control page