Structural Join and Staircase Join Algorithms of Sibling Relationship

The processing of XML queries can result in evaluationof various structural relationships. Efficient algorithms forevaluating ancestor-descendant and parent-child relationships have beenproposed. Whereas the problems of evaluatingpreceding-sibling-following-sibling and preceding-following relationshipsare still open. In this paper, we studied the structural join andstaircase join for sibling relationship. First, the idea of how tofilter out and minimize unnecessary reads of elements using parent'sstructural information is introduced, which can be used to acceleratestructural joins of parent-child and preceding-sibling-following-siblingrelationships. Second, two efficient structural join algorithms ofsibling relationship are proposed. These algorithms lead to optimaljoin performance: nodes that do not participate in the join can bejudged beforehand and then skipped using B^+-tree index. Besides,each element list joined is scanned sequentially once at most.Furthermore, output of join results is sorted in document order. Wealso discussed the staircase join algorithm for sibling axes. Studiesshow that, staircase join for sibling axes is close to the structuraljoin for sibling axes and shares the same characteristic of highefficiency. Our experimental results not only demonstrate theeffectiveness of our optimizing techniques for sibling axes, but alsovalidate the efficiency of our algorithms. As far as we know, this isthe first work addressing this problem specially.