RE: Xmlc: RE: XML Overlays and Deltas: Existing methods? Ideas?

[Brian Topping <topping@digidemic.com>]

Hi Mark,

This is slightly different.  What I am talking about doing is adding
speed to modifying the Document.  In my mind, the process of modifying a
Document generated by XMLC for use with page templates involves either
generating the Document by calling the generated XMLC or caching the
output of the first run of the XMLC and duplicating that Document
whenever that page needs to be customized and rendered.  

What I am proposing is that instead of deep copying the cached Document
every time it is needed that a reference to a static Document is kept
along with changes to the Document in a separate overlay structure that
implements the DOM interfaces.

In the real world of XMLC page generation (and contrasted to the
scenario above), the goal would be that the cost of the deep copy of the
Document is avoided, while still retaining the functionality of having
the page template as a Document for manipulation through DOM interfaces.
See what I mean?  Once we replace XMLC tag attributes in the Document
that we have cached, it's dirty when the next client wants to use it, so
they need to generate another Document.  If they don't modify the cached
copy, it's because they made a copy of it (or worse, regenerated it from
scratch.)  The common thread in these two scenarios is "generating a
Document" and "deep copying a Document".  Both are expensive operations
in time and memory.

With overlays, you can simply drop the overlay structure when you are
done with it and your changes disappear.  In a typical XMLC app, there
would be as many overlay structures as there are current sessions that
are using the template.  On a very large page, the deep copy to
duplicate the Document is not only computationally expensive but a
burden on memory as well.  With overlays, there is only one copy of the
base Document in a cache that is referenced by these "delta Documents".
There's additional processing for checking for deltas while reading a
DOM, but it should be much less than the processing for deep copying or
regenerating the entire Document.

-B

-----Original Message-----
From: Mark Diekhans [mailto:markd@lutris.com]
Sent: Wednesday, August 08, 2001 12:45 AM
To: Brian Topping
Cc: xmlc@enhydra.org; jjb5@cornell.edu; sdw@lig.net;
alaric@alaric-snell.com; xml-dev@lists.xml.org
Subject: Re: Xmlc: RE: XML Overlays and Deltas: Existing methods? Ideas?



Hi Brian

  What you are describing sounds similar to what the XMLC LazyDOM
already does
. The LazyDOM use a read-only, template DOM of the original document.
When an
instance of the document DOM is created, only the Document node is
initially
created.  As portions of the DOM are accessed, they are expanded into
nodes in
the instance DOM.  When the elements are accessed via the getElementXXX
methods, they go though a lookup table that obtains an element without
expanding it's parent or children. On output, the formatter traverses
the tree
without expanding unexpanded nodes.  This was approach was a big
performance
improvement for most XMLC applications.

Mark


Brian Topping <topping@digidemic.com> writes:
> Hi Guys,
> 
> I was writing to see if you guys had made any progress on XML DOM
> Overlays.  I was thinking about a problem that I am considering (I
will
> describe shortly) and thought that this would be perfect.  I came
across
> your posts on my initial research.
> 
> Here is what I would like to do.  I'm not sure if any of you has had
> experience with XMLC on Enhydra.  Basically, it takes tagged input
> template and makes Java utility classes.  These classes create and
> manage a DOM that represents the template.  So if I feed a tagged HTML
> file into XMLC, it creates a class that will generate a DOM with
> attributes corresponding to the tags.  It's then a simple matter to
> replace the tag attributes with the dynamic data that should be a part
> of the page and send the DOM to the output stream.
> 
> My problem with this scheme is that the generated classes are static
and
> generate the same DOM every time they are run.  That's fine, but it's
> more efficient to cache the DOM, deep copy it, then modify and output
it
> on a session basis for generation of pages.  Refining this one step
> further, I would prefer to avoid the deep copy altogether, and simply
> overlay a DOM for the changed attributes over a reference to a static
> DOM that is used by all sessions.  This should result in page
rendering
> speeds that rival page caching when the DOM is unchanged, and only
minor
> impact when it is changed.  It also solves a huge issue with page
> caching though -- there's no way to tell precisely when the cache
should
> be changed.  Instead, the cache is very efficiently located underneath
> the application, thereby allowing the content management system to be
> layered underneath the cache.  I think it straightens out a lot of
> organic growth that has been occurring in this area.
> 
> So while Stephen has a very comprehensive architecture envisioned for
> DOM overlays, I believe that even a minimal implementation with
> throwaway overlays would start to yield spectacular results.  I think
> this is what Al was talking about.
> 
> Is there anything that has become available since you guys posted
about
> this in April?
> 
> best,
> 
> Brian
> 
> ___________________________________________________
> Brian Topping -- CTO/Founder -- Digidemic, Inc.
> P.O. Box 78054, San Francisco, CA 94107
> +1 415 505-0403 (mobile) +1 415 643-0167 (fax)
> <mailto:topping@digidemic.com>  <http://www.digidemic.com>  
> 
> 
> 
> Subject: XML Overlays and Deltas: Existing methods? Ideas? 
> *	From: "Stephen D. Williams" <sdw@lig.net> 
> *	To: "xml-dev@lists.xml.org" <xml-dev@lists.xml.org> 
> *	Date: Wed, 18 Apr 2001 10:47:45 -0400 
> 
> 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
> 
> _______________________________________________
> XMLC mailing list
> XMLC@enhydra.org
> http://www.enhydra.org/mailman/listinfo.cgi/xmlc