Re: [xml-dev] Patent on streaming evaluation of XPath

[Rick Jelliffe <rjelliffe@allette.com.au>]

Christian Nentwich wrote:
> Dear all,
>
> I was browsing through the archives of xml-dev on optimised XPath 
> evaluation, something I've looked at on and off since about 2000. By 
> coincidence, I stumbled across this patent application for "optimised 
> streaming evaluation of xml queries":
>
> http://www.peertopatent.org/patent/20090125495/activity
> http://www.freepatentsonline.com/y2009/0125495.html
>
> Pretty cheeky. The first time we did something like that was around 
> 2001, when a student implemented it for me. I can probably dig up the 
> report. STX and its Joost implementation 
> (http://stx.sourceforge.net/), which was worked on in 2003, should 
> also count as prior art. The only claim I cannot quite follow is the 
> one on the "XPath engine sending instructions to the streaming 
> component". If this is a material part of the patent, it may be a 
> different claim.
 
Unless I have misread it (not impossible), I think this patent is for 
the specific technique of the consumer requesting the event producer 
(parser or iterator or lazy-evaluated query) to rewind to a certain 
point and restart sending the input stream from that point. So the 
parser checkpoints the input, and resends the stream fragments as many 
times as are needed to evaluate the XPath.  This is fine for shallow 
downward reads but costly for  //x  of course. I imagine it would be a 
feasible technique for simple 1->1 transformations with limited context 
or where the reverse axis paths can be converted to forward axis paths.

I think there is a technical name for this: the Turing machine!  And 
since according to Church-Turing thesis, every calculation can be 
represented using this kind of machine, it is not surprising that XSLT 
can be implemented using it (if. indeed, that is what the nub of the 
patent is.)  Whether Turing counts as prior art, I don't know.

Also, it bears mentioning that prior art also includes any SGML 
techniques from the decade before XML, since "XML is an application 
profile or restricted form of SGML, the Standard Generalized Markup 
Language [ISO 8879] 
<http://www.w3.org/TR/2008/REC-xml-20081126/#ISO8879>. By construction, 
XML documents are conforming SGML documents."  
http://www.w3.org/TR/2008/REC-xml-20081126/#sec-intro       Even though 
a patent may talk about XML as if it were a thing in itself, prior art  
from SGML (relating to things that are kept in XML) should be in play too.

Cheers
Rick Jelliffe