XML Overlays and Deltas: Existing methods? Ideas?

["Stephen D. Williams" <sdw@lig.net>]

I've had this concept of an XML tree overlay or delta for a while and
haven't seen much defined so far that I could use.

I have looked at XML Fragment Interchange, fragserver, XPath, etc. 
While I really like XML Fragments and think that the proposal should
move forward, it doesn't give me what I want in an efficient way.  I
believe that the updates need to be embedded within the context with
possible shortcuts of context.

When I talk about an Overlay Delta, what I mean is that given an
arbitrary XML tree (or arbitrary within certain rules), I want to be
able to represent changes to the original in a minimal way.  Ideally
this would allow a very large base document with small 'state' trees. 
There are a number of places this is beneficial for processing, storage,
and transmission.

This can obviously be done with rules about ID's, attributes, and
structure.  I would like help determining the minimal set of such
requirements that solves the most general usage patterns.

The key requirements:

Support arbitrary replacement, insertion, appending, and deletion.

The resulting trees need to be 'searchable' as overlays very quickly. 
To illustrate this, assume that you have an array of DOM parse trees
ordered newest to oldest.  When traversing the tree, searching for an
element, or making a change, the 'overlay DOM' library needs to access
each DOM tree to give the effect of a single, up to date DOM tree.  Of
course updates would normally be written to the newest DOM tree and all
older trees could be condensed into a single base tree.

This ability should be sufficient to support transactions, transaction
processing with 'state' being small vs. a large application base,
backup, logging/auditing, backtracking, 'header compression'-style
protocol deltas, etc.

This problem is the same regardless of the form of XML, but I am
planning to use some solution to this as part of my binary structure XML
work.

Deletion and full replacement would probably be special cases where an
attribute of some kind would indicate "don't look deeper in the stack
for this subtree".  Efficiency could dictate that whole subtrees be
repeated rather than incur overhead that was larger than the actual
data.

Some ideas to beat up on:

<XML ID="ob1">
  <author ID="Bob">
    <name ID="Bob">Bob</name>
    <book ID="Bob's Life">
      <name>Bob's Life</name>
      <sold ID="E9F">45</sold>
    </book>
  </author>
</XML>

<XML ID="ob1">
  <author ID="Bob">
    <book ID="Bob's Life">
      <sold>98</sold>
    </book>
  </author>
</XML>

Or:

<XML ID="ob1">
  <update xpath="author/book["Bob's Life"]/sold">98</update>
</XML>

Or even better, assuming that each node has a unique ID and that XPath
supports ID's by 'zooming' the context to the ID specified in
decendant-or-self:

<XML ID="ob1" xmlns:u=....update >
  <upd xpath="//ID=E9F">98</upd>
or:
  <u:u ID="E9F">98</upd>
</XML>

Where '98' could be an arbitrary XML subtree.

Thanks!
sdw
-- 
sdw@lig.net  http://sdw.st
Stephen D. Williams
43392 Wayside Cir,Ashburn,VA 20147-4622 703-724-0118W 703-995-0407Fax 
Dec2000