RE: SQL BTree to XML Tree?

> I'm storing a btree in sql in the following manner:
> 
> +----------------------------+
> | Table: Departments         |
> +----------------------------+
> | id | name        | lh | rh |
> +----------------------------+
> | 1  | Managers    | 1  | 6  |
> | 2  | Supervisors | 2  | 5  |
> | 3  | Employees   | 3  | 4  |
> | 4  | Directors   | 7  | 8  |
> +----------------------------+
> 

The Celko technique. Illustrating the lengths people will go to to bend
their data to make it fit in a relational database!


> This is being converted to xml, resulting in:
> 
> <output>
>   <item>
>     <id>1</id>
>     <name>Managers</name>
>     <lh>1</lh>
>     <rh>2</rh>
----------^ should be 6, I assume
>   </item>
> <!-- etc -->
> </output>
> 
> I need to translate this using XSL to this:
> 
> <group>
>   <department title="Managers">
>     <department title="Supervisors" />
>     <department title="Employees" />
>   </department>
>   <department title="Directors" />
> </group>
> 

May not be very efficient, but what comes to mind is that your data gives
you the descendant relationship very easily:

<xsl:function name="f:descendants" as="element(item)*">
  <xsl:param name="boss" as="element(item)"/>
  <xsl:sequence select="$boss/../item[lh gt $boss/lh and rh le $boss/rh]"/>
</xsl:function>

and you can deduce from this the child relationship (as being those
descendants who are not descendants of a descendant):

<xsl:function name="f:children" as="element(item)*">
  <xsl:param name="boss" as="element(item)"/>
  <xsl:variable name="descendants" select="f:descendants($boss)
  <xsl:sequence select="$descendants except 
         (for $i in $descendants return f:descendant($i))"/>
</xsl:function>

and then you can do a recursive descent using the logical child relationship
in the usual way:

<xsl:template match="item">
  <department title="@name">
    <xsl:apply-templates select="f:children(.)"/>
  </department>
</xsl:template>

Not tested and almost certainly needs a bit of fine tuning. And of course if
you're in XSLT 1.0 you'll have to rewrite the algorithm completely.

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