5.6 Transitive Closure Extension

There is some interest in the research community for a dedicated *transitive closure* operator (contrasted to XQuery's means to provide for recursion, user-defined functions). MonetDB/XQuery, hence, provides the syntax extension

  "with" $variable ["as" Type] "seeded by" SeedExpr "recurse" Expr

The semantics of this expression is

1. Evaluate SeedExpr. It serves as a seed to the recursion process and is bound to variable $variable in the first recursion step.
2. For each recursion step, evaluate the expression's body Expr. This body may refer to variable $variable, which is bound to the outcome of the previous recursion step (or to the seed expression if we are in the first step).
3. All evaluations of the body are collected by means of the XQuery union operator to form the expression result. Recursion stops as soon as we reach a fix point.

A few remarks:

• An optional type declaration may be used to restrict the type of the recursion variable. If it is omitted, Type defaults to node*. In any case, the static types of both expressions, seedExpr and Expr must be subtypes of Type.
• XQuery's union operator is only defined on nodes. Hence, Type must be a subtype of node*. There are some more restrictions on Type to make the entire expression sensible (e.g., its quantifier must be greater than 1).
• It is possible to write recursive expressions that do not reach a fix point. Evaluation won't terminate in that case.

The transitive closure operator is only supported when using Pathfinder's algebraic back-end. On the other hand, the algebraic back-end does not support any other means of recursion yet.