RE: [xsl] Merging elements within a range using a key

Subject: RE: [xsl] Merging elements within a range using a key
From: "Michael Kay" <mike@xxxxxxxxxxxx>
Date: Tue, 2 May 2006 09:33:57 +0100
Keys can only perform an equality test, not a range test.

Presumably you are scanning all the rows once for each category: I would
therefore expect the performance to be proportional to the number of
categories C times the number of rows R. Is that the relationship you are
observing? Does increasing the data volume increase both the number of rows
and the number of categories?

As far as I can see (someone may prove me wrong!), the only way to improve
this - to make it O(C+R) rather than O(C*R) - is to hand-code a sort-merge
join. That is, sort the rows, sort the categories, then do a recursive scan
through the rows keeping track of the current category and switching to a
different category when @r gets beyond the end of the current category's
range.

Michael Kay
http://www.saxonica.com/

> -----Original Message-----
> From: Mike B [mailto:mikeb0304@xxxxxxxxxxx] 
> Sent: 02 May 2006 01:48
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] Merging elements within a range using a key
> 
> I have a working transformation which merges Row elements 
> into the appropriate Category elements as shown, based on the range
> 
>            category/@s <= row/@r <= category/@e
> 
> This statement works,   <xsl:copy-of 
> select="/view/results/row[@r &gt;= 
> current()/@s and @r &lt;= current()/@e]" />  but seems to 
> slow things down as data volume increases.
> 
> Is it possible to use a key to find elements within a range 
> like this? I'm at a loss as to what the syntax might be.
> 
> Any suggestions are appreciated!
> 
> Thanks. Mike
> 
> Simplified Input document
> ------------------------------------
> <view>
>   <results>
>     <row r="20">
>       <col c="1">col 20.1 data</col>
>     </row>
>     <row r="21">
>       <col c="1">col 21.1 data</col>
>     </row>
>     <row r="22">
>       <col c="1">col 22.1 data</col>
>     </row>
>   </results>
>   <category>
>     <category s="18" e="19">cat a</category>
>     <category s="20" e="21">cat b</category>
>     <category s="22" e="25">cat c</category>
>   </category>
> </view>
> 
> 
> Output document
> ------------------------
> <view>
>   <results>
>     <category s="20" e="21">cat b
>       <row r="20">
>         <col c="1">col 20.1 data</col>
>       </row>
>       <row r="21">
>         <col c="1">col 21.1 data</col>
>       </row>
>     </category>
>     <category s="22" e="25">cat c
>       <row r="22">
>         <col c="1">col 22.1 data</col>
>       </row>
>     </category>
>   </results>
> </view>
> 
> 
> 
> Transformation - without a key
> ----------------------------------------
> <?xml version="1.0" encoding="utf-8"?>
> <xsl:stylesheet version="1.0" 
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
> 
>     <xsl:output method="xml" encoding="utf-8" />
> 
> <xsl:template match="/view">
>   <xsl:copy>
>    <xsl:apply-templates select="@*|node()"/>
>    <xsl:copy-of select="/view/category" />
>   </xsl:copy>
> </xsl:template>
> 
> <xsl:template match="results">
>   <!--  do not copy old results to output --> </xsl:template>
> 
> <xsl:template match="/view/category">
>   <xsl:element name="results">
>    <xsl:call-template name="copy-attributes">
>     <xsl:with-param name="attributes" select="@*" />
>    </xsl:call-template>
>    <xsl:call-template name="copy-attributes">
>     <xsl:with-param name="attributes" select="/view/results/@*" />
>    </xsl:call-template>
>    <xsl:apply-templates select="category" />
>   </xsl:element>
> 
> </xsl:template>
> 
> <xsl:template match="category">
> 
>   <xsl:variable name="row-test">
>    <!-- should be improved with a key -->
>    <xsl:copy-of select="/view/results/row[@r &gt;= 
> current()/@s and @r &lt;= current()/@e]" />
>   </xsl:variable>
> 
>   <xsl:if test="string-length($row-test) > 0">
>    <xsl:choose>
>     <xsl:when test="category">
> 
>      <xsl:element name="{name()}">
>       <xsl:call-template name="copy-attributes">
>        <xsl:with-param name="attributes" select="@*" />
>       </xsl:call-template>
>       <xsl:value-of select="text()" />
> 
>       <xsl:apply-templates select="category"/>
> 
>      </xsl:element>
>     </xsl:when>
> 
>     <xsl:otherwise>
>      <xsl:element name="{name()}">
>       <xsl:call-template name="copy-attributes">
>        <xsl:with-param name="attributes" select="@*" />
>       </xsl:call-template>
>       <xsl:value-of select="text()" />
> 
>       <xsl:copy-of select="$row-test" />
>      </xsl:element>
>     </xsl:otherwise>
>    </xsl:choose>
>   </xsl:if>
> 
> </xsl:template>
> 
> 
> <xsl:template name="copy-attributes">
>   <xsl:param name="attributes" />
> 
>   <xsl:for-each select="$attributes">
>    <xsl:attribute name="{name()}">
>     <xsl:value-of select="." />
>    </xsl:attribute>
>   </xsl:for-each>
> 
> </xsl:template>
> 
> <xsl:template match="@*|node()">
>   <xsl:copy>
>    <xsl:apply-templates select="@*|node()"/>
>   </xsl:copy>
> </xsl:template>
> 
> </xsl:stylesheet>
> 
> _________________________________________________________________
> FREE pop-up blocking with the new MSN Toolbar - get it now! 
> http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/

Current Thread