Algebraic XML construction in Natix

While using an algebra that acts on sets of variable bindings for evaluating XML queries, the problem of constructing XML from these bindings arises. One approach is to define a powerful operator that is able to perform a complex construction of a representation of the XML result document. The drawback is that such an operator in its generality is hard to implement and disables algebraic optimization since it has to be executed last in the plan. Therefore we suggest to construct XML documents by special query execution plans called construction plans built from simple, easy to implement and efficient operators. The paper proposes four simple algebraic operators needed for XML document construction. Further we introduce an optimizing translation algorithm of construction clauses into algebraic expressions.