Efficient processing of XML twig pattern matching based on extended region encoding labeling scheme

XML query technology has attracted more and more attention in data management research community. Finding all the occurrences of a twig pattern in an XML database is a core operation for XML queries. The previous approaches produce large set of intermediate results when they processing queries with parent-child relationship edges. We propose a new labeling scheme, called extended region encoding labeling scheme. From the label of an element, we can obtain all distinct tag names of its children. Based on this new labeling scheme, we design a holistic twig join algorithm TwigStackBE. Our main technique is before processing twig query we firstly check whether an element would contribute to the final solutions. So the set of intermediate results in twig pattern matching can be much smaller than previous algorithms. The experimental results indicate that the proposed algorithm performs better than the previous.