A Practical Approach to Holistic B-Twig Pattern Matching for Efficient XML Query Processing

摘要

Efficient twig pattern matching is essential to XML queries and other tree-based queries. Numerous so-called holistic algorithms have been proposed to process the twig patterns in XML queries. However, a more general form of twig patterns, called B-twig (or Boolean-twig), which allow arbitrary combination of all the three logical connectives, AND, OR, and NOT in the twig patterns, has not yet been adequately addressed. In this paper, a new approach accompanied with an optimal implementation algorithm is presented for efficiently processing B-twig XML queries. Experimental study confirms the viability and performance superiority of our new approach.