Package org.basex.query.up

Class NodeUpdateComparator

java.lang.Object
org.basex.query.up.NodeUpdateComparator
All Implemented Interfaces:
Comparator<NodeUpdate>
public final class NodeUpdateComparator extends Object implements Comparator<NodeUpdate>

Comparator for NodeUpdate.

In general, a list of updates is applied from the highest to the lowest PRE value in BaseX. The higher the actual location of an update the sooner it is applied, hence the 'greater' NodeUpdate is applied first. The order further relies on the definition of UpdateType.

NodeUpdates are identified by their target node's PRE values (T). Depending on the UpdateType of the update, a specific PRE value on the table is affected (L). Hence it is not sufficient to order primitives based on T (see case 2,3 below). It is also not sufficient to order them based on L (see case 2,3 below).

The first NodeUpdate is referred to as P1, the target node of P1 is referred to as T1, the (optional) insertion sequence for P1 is S1, the actually affected PRE value on disk is L1. For the second P2, T2, S2, L2.

The result of the comparison depends on several things:

  1. The PRE values of T1 and T2. Consider D the document <DOC><N1/><N2/></DOC>. If P1 is a DeleteNode on N1 and P2 is a DeleteNode on N2, it follows that T2 greater than T1. P2 wins the comparison and is therefore executed first.
  2. Whether the order of P1, P2 must be switched to get the desired result. Consider D the document <DOC><N1><N2/></N1></DOC>. If P1 is an InsertInto on N1 and P2 is an InsertInto on N2, it follows that T2 greater than T1. Yet, executing P2 first would lead to the following problem: The actually affected PRE value location on disk for both updates is L1=L2=L=4. P2 inserts a sequence of nodes S2 at L. After this P1 inserts a sequence of nodes S1 at the same location L and shifts S2 further back on disk. S1 and S2 are now ordered incorrectly (S1,S2) and invalidate the document. Hence the correct order (S2,S1) can only be achieved if P1 is executed first and S1 subsequently shifted by inserting S2. The problem can exist if P1 and/or P2 are of the kind InsertInto or InsertAfter and T1+size(T1) is equal T2+size(T2), hence T1 and T2 have the same following node. The correct order is realized by executing the update first, that is on the ancestor axis of the other. In this case P1 greater than P2. Another case similar to this is if P1 is an InsertIntoAsFirst on an element T1 and P2 is i.e. a ReplaceNode on an attribute T2 of T1. To get the desired order of insertion sequences (S2,S1) P1 must be executed first, hence P1 greater than P2.
  3. The UpdateType of P1, P2. Consider D the document <DOC><N1/></DOC> with T=N1. P1 is an InsertBefore on T and P2 is an InsertIntoAsFirst on the same target T. As they both operate on the same target, both have not to be re-located because of their type (see case 2), hence only differ in their UpdateType, it follows that P2 greater than P1 as nodes S2 are to be inserted on the following axis of S1. Another case: P2 a DeleteNode on T and P1 an InsertBefore on T. As L2=L1, P2, the execution sequence must be (P2,P1). for(P1,P2) S1 would be deleted by P2. The correct order is also determined by the order of UpdateType. Here we see that ordering updates simply by the actually affected PRE value L is not sufficient.
Author:
BaseX Team 2005-21, BSD License, Lukas Kircher