XML Twig Pattern Matching Processing

Abstract

Finding all occurrences of a twig pattern query is a core operation of XML query processing system. Many algorithms have been proposed. Existing algorithms generate individual path matches and then stitch them together through a merge operation to form twig matches. Due to the merging operation they have very expensive cost. To avoid the merging cost, many one phase algorithms have been proposed. However, these algorithms are quite efficient for queries with only ancestor-descendent relationship. TwigMMatch algorithm is proposed. Like Holistic TwigStack, a chain of linked stacks is applied to process the twig matches. The proposed algorithm not only avoids the merging process but also process the twig queries with mixed edges.