MyTwigStack: A Holistic Twig Join Algorithm with Effective Path Merging Support

While an XML database consists of a collection of data trees, an XML Query is essentially a tree pattern associated with selection predicates. Various structural join algorithms have been designed to obtain the matches of a tree pattern within an XML database, and more recently, holistic twig joins were proposed as better alternatives to structural joins. The proposed twig join algorithms typically rely on a two-phase processing scheme: the first phase discovers the root-to-leaf paths (solutions) and the second phase join-merges the identified paths for producing the desired matches of a twig pattern. In this paper, we address the deficiencies (especially, the path merging deficiency) as found in TwigStack - the representative of twig join algorithms; we then present an alternative algorithm, called MyTwigStack, that improves TwigStack through an effective path merging scheme.