File(s) under permanent embargo
Reducing graph matching to tree matching for XML queries with ID references
conference contribution
posted on 2023-05-23, 09:00 authored by Wu, H, Ling, TW, Dobbie, G, Bao, Z, Xu, LID/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.
History
Publication title
Database and Expert Systems Applications Part IIEditors
PG Bringas, A Hameurlain, G QuirchmayrPagination
391-406ISBN
978-3-642-15250-4Department/School
School of Information and Communication TechnologyPublisher
Springer-VerlagPlace of publication
Berlin, GermanyEvent title
21st International Conference on Database and Expert Systems ApplicationsEvent Venue
Bilbao, SpainDate of Event (Start Date)
2010-08-30Date of Event (End Date)
2010-09-03Rights statement
Copyright 2011 SpringerRepository Status
- Restricted