Abstract
Structural joins and, in particular, twig joins are essential operations in XML query processing. Algorithms presented so far treat a twig join as a single operator with multiple inputs.
However, in XQuery and XSLT, a twig pattern may be scattered across several functions (templates); thus, function integration is required before the application of a twig join operator. This paper presents R-programs – a novel evaluation framework based on an expanding network of operators.
In this environment, a function may repeatedly and bidirectionally interact with its caller; consequently, a structural join algorithm may be distributed across the boundary of a function. Given this ability, function integration is no longer required and twig join algorithms become applicable even in the presence of recursive functions.