Abstract
The formal semantics of XQuery 1.0, XPath 2.0, and XSLT 2.0 relies on sequences as the only compound data type assigned to all variables and expressions throughout the execution. Since concatenation of sequences is not commutative, it is difficult to reorder the operations during static optimization or to parallelize their execution.
In this paper, we suggest enriching the execution model with several types that carry less information than sequences and whose operations are easier to optimize and to evaluate. Various XQuery operators and XSLT instructions access their operands in different ways; backward propagation of the usage information allows using weaker types for variables and expressions.
Thus, the execution cost of an XQuery/XSLT program may be reduced in both time and space and more sophisticated methods of static optimization or parallelization become available.