Structural Join Algorithm for Sequential Regular Path Expressions

Kevin Lu


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.

Full Text:



Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Crossref Similarity Check logo

Crossref logologo_doaj

 Hrvatski arhiv weba logo