Resource Menu

XML Documents


In this page is presented the operational transformations used in ordonned tree conciliation. This kind of object can be used to represent an XML document. In an ordonned tree, each node is identified by its unique path. This path is the sequence of the integer values from root to this node. Figure 1 show a tree example, with values of paths for each node.

Figure 1 - Example of ordered tree

Two operations are defined on this ordonned tree :

  • InsNode(parent, n, val) : insert a new node as child of node parent. This new node is insert as position n in children list of parent, and has value val.
  • DelNode(parent, n) : delete the child n of node parent.
Some others functions are defined :
  • length(path) : return the lenght of the path path.
  • childOf(p1, p2) : return true if node with path p1 is a child of node with path p2.
  • getPos(p, n) : return the n+1Ith piece of the path p (getPos([3,2,1,4],2) = 1).
  • incPos(p, n) : return the path p to which one increments its n+1Ith piece (incPos([3,2,1,4],2) = [3,2,2,4]).
  • decPos(p, n) : return the path p to which one decrements its n+1Ith piece (decPos([3,2,1,4],2) = [3,2,0,4]).
Finally, we define the codeInf(val 1,val 2) function, which compare val1 and val2 defining an order relation. This function exists in all cases. For example, nodes which content is a text block, the function evaluate the relation between the two values according to the collating sequence.

If two concurrent insert operation on the same parent occur, the problem is the same than with caracters sequence :

  • We need to increment the insertion position (child number) of the second operation.
  • If the two insertion occurs on the same position, we need to decide which will be placed before the other.
In case of two concurrent insert operation on the two different nodes, the problem is the same : insertion the most "top-left" shift the most "right-bottom".

Example (Figure 2) :

  • op1 = InsNode([],1,X)
  • op2 = InsNode([2],1,Y)
Figure 2 - Two operations on the tree

After merging process, we must have the tree of Figure 3.

Figure 3 - The final tree

Th execution of op1 move the parent node, on which op2 must be executed. The transformation of op2 according to op1 must return the operation op'2 = InsNode([2+1], 1, Y).

Two concurrent insertions

T(InsNode(p 1, n 1, v 1), InsNode(p 2, n 2, v 2) =
  if (p 1 = p 2) then
     if (n 1 < n 2) then
        return InsNode(p 1, n 1, v 1)
     else if (n 2 < n 1) then
        return InsNode(p 1, n 1+1, v 1)
     else if (codeInf(v 1,v 2) = true) then
        return InsNode(p 1, n 1, v 1)
     else if (codeInf(v 2,v 1) = true) then
        return InsNode(p 1, n 1+1, v 1)
     else
        return Id()
     endif
  else if (childOf(p 1,p 2)) then
     if (n 2 < getPos(p 1,length(p 2))) then
        return InsNode(incPos(p 1,length(p 2)), n 1, v 1)
     else if (n 2 = getPos(p 1,length(p 2))) then
           return InsNode(incPos(p 1,length(p 2)), n 1, v 1)
     else
        return InsNode(p 1, n 1, v 1)
     endif
  else
     return InsNode(p 1, n 1, v 1)
  endif;


Two concurrent deletions

T(DelNode(p 1, n 1), DelNode(p 2, n 2)) =
  if (p 1 = p 2) then
     if (n 1 < n 2) then
       return DelNode(p 1, n 1)
     else if (n 2 < n 1) then
       return DelNode(p 1, n 1-1)
     else
       return Id()
     endif
  else if (childOf(p 1,p 2)) then
     if (n 2 < getPos(p 1,length(p 2))) then
        return DelNode(decPos(p 1,length(p 2)),n 1)
     else if (n 2 = getPos(p 1,length(p 2))) then
           return Id()
     else
        return DelNode(p 1,n 1)
     endif
  else
     return DelNode(p 1,n 1)
  endif;


An insertion and a deletion

T(InsNode(p 1,n 1,v 1), DelNode(p 2,n 2)) =
  if (p 1 = p 2) then
     if (n 1 < n 2) then
       return InsNode(p 1,n 1,v 1)
     else if (n 2 < n 1) then
       return InsNode(p 1,n 1-1,v 1)
     else
       return InsNode(p 1,n 1,v 1)
     endif
  else if (childOf(p 1,p 2)) then
     if (n 2 < getPos(p 1,length(p 2))) then
        return InsNode(decPos(p 1,length(p 2)),n 1,v 1)
     else if (n 2 = getPos(p 1,length(p 2))) then
           return Id()
     else
        return InsNode(p 1,n 1,v 1)
     endif
  else
     return InsNode(p 1,n 1,v 1)
  endif;
T(DelNode(p 1,n 1), InsNode(p 2,n 2,v 2)) =
  if (p 1 = p 2) then
     if (n 1 < n 2) then
       return DelNode(p 1,n 1)
     else if (n 2 < n 1) then
       return DelNode(p 1,n 1+1)
     else
       return DelNode(p 1,n 1+1)
     endif
  else if (childOf(p 1,p 2)) then
     if (n 2 < getPos(p 1,length(p 2))) then
        return DelNode(incPos(p 1,length(p 2)),n 1)
     else if (n 2 = getPos(p 1,length(p 2))) then
        return DelNode(incPos(p 1,length(p 2)),n 1)
     else
        return DelNode(p 1,n 1)
     endif
  else
     return DelNode(p 1,n 1)
  endif;


Last edited by Pascal Molli at Feb 2, 2006 11:33 AM - Edit content - View source