On the reduction of sequences of XML document and schema update operations

Automating the management of data throughout its lifecycle requires solutions to effectively and efficiently handle updates, both on data and on the corresponding schema. Such solutions are especially needed for XML documents and schemata, due to the high dynamicity of the contexts in which they are employed. XML documents need to be kept up-to-date, schemata as well are often subjected to updates and progressively refined to adapt to changing requirements. In this paper, we address the problem of reducing a sequence of updates on a tree representing either an XML document or an XML schema. Reducing means deriving a shorter sequence with the same effect on the tree of the original one. Specifically, we propose a set of reduction rules and an efficient reduction algorithm.