On the twig joins

An XML twig query, represented as a labeled tree, is essentially a complex predicate on both structure and content of an XML document. Twig query matching has been considered as a core operation in querying tree structured XML data. Among all the proposed strategies, the method based on the so-called stack encoding aims at the reduction of intermediate results by compressing matching paths. The idea itself is very interesting. However, the processes for generating compressed paths suffer substantial redundancy and can be greatly improved. In this paper, we analyze this method and show that the time complexities of path generation in its two main procedures: PathStack and TwigStack can be reduced from O(m2n) to O(mn), where m and n are the sizes of the query tree and document tree, respectively.