Abstract
XPath queries are usually translated into an algebra that combines traditional relational operators and XML-specific ones. In particular, FLWOR loops are represented using nest, unnest, join, and similar operators and their original nested-loop nature disappears, creating an opportunity for bulk evaluation and join reordering.
In XQuery, two additional issues shall be handled -- tree construction and the presence of user-defined functions. The recursive nature of functions pushes the problem outside of the range of relational algebra.
This book presents a novel evaluation framework based on an expanding network of relational operators, called R-program. In this environment, functions are evaluated in bulk instead of evaluating each call separately.
Besides obvious advantages of bulk evaluation, R-programs also allow rearrangement of data flow across function boundaries. A set of program transformations employing these capabilities is described; together with rule-based static interprocedural analysis algorithms used to determine the applicability of the transformations.