RE: XQuery -- Reinventing the Wheel?

[Michael Rys <mrys@microsoft.com>]

It is true that if you have full recursion, that you can express the same
queries as with templates. The difference from an optimization point of view
are as follows, IMHO:

1. Making the recursive processing explicit, the rule-base is hardcoded into
the code. Thus, a compiler can do static analysis and optimizations. This is
only partially true for template processing, mainly when your rule-base is
not changing (which is the case for single XSLT template files, but probably
not anymore for query systems based on template processing).

2. Since the explicit recursive processing is normally only used when no
other mean is necessary, people will more likely write better optimizable
expressions.

Please note, I am not debating the use-fullness of XSLT templates for
processing XML documents. I just don't think that this processing style will
scale well to large numbers of documents and large rule-bases.

Best regards
Michael

> -----Original Message-----
> From: Evan Lenz [mailto:elenz@xyzfind.com]
> Sent: Friday, February 23, 2001 6:39 PM
> To: Michael Rys
> Cc: xml-dev@lists.xml.org
> Subject: RE: XQuery -- Reinventing the Wheel?
> 
> 
> 
> > However rule-based systems have not achieved the
> > level of performance and scalability of query-based systems,
> > neither in the
> > research area (as far as I know) nor in the commercial world.
> 
> I'm coming to realize that there's no technical reason why 
> XQuery should not
> have a template rule mechanism like that of XSLT. Perhaps 
> what you mean by
> "rule-based systems" is some sort of magic. XSLT's template 
> rules, on the
> other hand, have an exact functional equivalent already in 
> XQuery, though it
> is not nearly as convenient to specify in XQuery (even in 
> comparison to
> XSLT's XML syntax, imagine that.) The difference between the two, as I
> mentioned in my paper, is that one uses *implicit* recursive 
> processing and
> the other uses *explicit* recursive processing.
> 
> Let me demonstrate. Take a small set of template rules such as the
> following:
> 
> <xsl:template match="heading">
>   <title>
>     <xsl:value-of select="."/>
>   </title>
> </xsl:template>
> 
> <xsl:template match="chapter">
>   <section>
>     <xsl:apply-templates/>
>   </section>
> </xsl:template>
> 
> A stylesheet containing these will recursively process these 
> template rules
> *implicitly*. In XQuery (or in XSLT minus template rules), 
> you can specify
> the same query, but you have to use *explicit* recursion, as in the
> following XQuery example (the XPath self:: axis is used, 
> because I'm not yet
> sure how to test a node's node type in XQuery yet):
> 
> FUNCTION applyTemplates(NODE $n) RETURNS LIST(NODE)
> {
>     IF name($n) = 'heading'
>     THEN
>       <title>
>         $n/text()
>       </title>
>     ELSE IF name($n) = 'chapter'
>     THEN
>       <section>
>         applyTemplates($n/node())
>       </section>
>     ELSE IF self::text()
>       $e
>     ELSE
>       applyTemplates($n/node())
> }
> applyTemplates(/)
> 
> The above query will evaluate to the same result as produced 
> by the set of
> XSLT template rules above. This could apply for any set of 
> template rules.
> Since a template-rule-based query a la XSLT could always be 
> algorithmically
> converted to a recursive XQuery function, why should the 
> convenience of
> template rules be thrown out? Since I can express any set of 
> template rules
> in XQuery using recursive functions, (though quite awkwardly 
> as I add more
> rules), your argument that their inclusion would inherently hamper
> performance simply holds no water.
> 
> And that is why I would be sad to see an XML query language 
> developed that
> makes no use of template rules. As I said in a prior post, 
> such a mechanism
> would not always have to be used. Some queries will always be 
> slow. These
> are documentable. Template rules might be among those, or 
> maybe even not.
> Regardless, their perfect fit for XML processing, i.e. 
> processing recursive,
> flexible, unexpected tree structures, should *not* be 
> sacrificed because
> certain queries might be slow.
> 
> An XML query language, as the WG Requirements document states 
> clearly, is
> about handling XML--not just relational data in XML, or even 
> OO data in XML,
> but also *documents*.
> 
> Excluding template rules from an XML query language would be 
> a terrible
> mistake, since there is no good technical reason to do so, 
> and XML was made
> for template rules, IMHO.
> 
> Evan Lenz
> XYZFind Corp.
>