XAL: an algebra for XML query optimization

This paper proposes XAL, an XML ALgebra. Its novelty is based on the simplicity of its data model and its well-defined logical operators, which makes it suitable for composability, optimizability, and semantics definition of a query language for XML data. At the heart of the algebra resides the notion of collection, a concept similar to the mathematician's monad or functional programmer's comprehension. The operators are classified in three clusters: extraction operators retrieve the needed information from XML documents, meta-operators control the evaluation of expressions, and construction operators build new XML documents from the extracted data. The resulting algebra has optimization laws similar to the known laws for transforming relational queries. As a consequence, we propose a heuristic optimization algorithm similar to its relational algebra counterpart.