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 occurrences of a twig pattern Q (or small tree) in a document T. rnor work has typically decomposed Q into binary structural relationships, such as parent-child and ancestor-descendant 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 algorithms to stitch together all the matching binary relation-snips or paths,. In the worst case, the time for doing joins can be exponential (in the number of query nodes or decomposed paths). In this paper, we propose a new algorithm for this task with no path joins invovled. The time rviTiSpaCe cornPlexities of the algorithm are bounded by ^WQleaf) and O(TleafQleaf), respectively, where Tleaf stands for the number of the leaf nodes in T and Qleaf for the number of the leaf nodes in Q.
展开▼
