Structural Join Algorithm for Sequential Regular Path Expressions

Abstract

XML queries employ regular path expressions to find structural patterns within XML documents. The operation of structural join is a crucial part of XML query processing. Existing approaches reduce complex join expressions to several binary structural joins. It implies generation of superfluous intermediate data. In this paper, we propose a new structural join algorithm, called sequence join algorithm, for sequential regular path expressions. It exploits information about position of the elements in the document to skip generation of the redundant intermediate lists. The algorithm performs merge of several input lists of nodes in one pass. Experimental results prove the structural join algorithm is better than multiple binary join algorithm for queries of both small and large cardinality.