Y. Chen (Canada)
XML documents, Twig pattern queries, Tree matching, Tree encoding
With the growing importance of XML in data exchange, much research has been done in providing flexible query mechanisms to extract data from XML documents. A core operation for XML query processing is to find all occur rences of a twig pattern Q (or small tree) in a document T. Prior work has typically decomposed Q into binary struc tural relationships, such as parent-child and ancestor-de scendant relations, or root-to-leaf paths. The twig matching is achieved by: (i) matching the binary relationships or paths against XML databases, and (ii) using the join algo rithms to stitch together all the matching binary relation ships or paths. In the worst case, the time for doing joins can be exponential (in the number of query nodes or de composed paths). In this paper, we propose a new algo rithm for this task with no path joins invovled. The time and space complexities of the algorithm are bounded by O(|T|⋅Qleaf) and O(Tleaf⋅Qleaf), respectively, where Tleaf stands for the number of the leaf nodes in T and Qleaf for the number of the leaf nodes in Q.
Important Links:
Go Back
