PRELIMINARIES

In this section, we introduce the notions that will be used along the paper. The data model we use for XML documents is labelled ordered trees as in Marian et al. (2001). We will alsobriefly consider some algorithms that support unordered trees.

Operations. The change model is based on editing operations as in Marian et al. (2001), namely insert, delete, update and move. There are various possible interpretations for these operations. For instance, in Kuo-Chung Tai's model Tai (1979), deleting a node means making its children become children of the node's parent. But this model may not be appropriate for XML documents, since deleting a node changes its depth in the tree and may also invalidate the document structure according to its DTD.