Transforming flat xml to nested xml using Xquery and recursive functions

Question

I'm troubled with an exercise on recursive functions in Xquery. I need to transform a flat XML tree to a nested XML tree using only Xquery.

The flat XML looks like this:

    <?xml version="1.0"?>
    <tree>
      <node id="1" type="Folder">
        <child>2</child>
        <child>3</child>
      </node>
      <node id="2" type="Folder">
        <child>4</child>
      </node>
      <node id="3" type="Folder">
        <child>5</child>
        <child>6</child>
      </node>
      <node id="4" type="Item" />
      <node id="5" type="Folder">
        <child>7</child>
      </node>
      <node id="6" type="Item" />
      <node id="7" type="Item" />
    </tree>

The nested XML required looks like this:

    <?xml version="1.0"?>
    <tree>
      <node id="1" type="Folder" children="2 3">
        <node id="2" type="Folder">
          <node id="4" type="Item" />
        </node>
        <node id="3" type="Folder">
          <node id="5" type="Folder" children="7">
            <node id="7" type="Item" />
          </node>
          <node id="6" type="Item" />
        </node>
      </node>
    </tree>

I've tried to Xquery this without recursive functions, but without much luck. Especially the conditioning seems strange to me; the root element of the new nested XML should be the node with id="1", since it does not exist as a child of any other element. However, if I try to specify this as a condition, e.g. below, it does not seem possible to just select that node.

    for $node in /Tree/node[@id != /Tree/node/child]
    return
    <node id="{data($node/@id)}" type="{data($node/@type)}">

            (: Lower level subqueries.... :)

    </node>

UPDATE: I've come a lot further, but now I'm stuck with the [condition] on the selection of nodes that have an id equal to the contents of a parent node, i.e. the for statement in the recursive function does not give back any nodes, which is unexpected.

This is my code thus far:

    declare namespace output = "http://www.w3.org/2010/xslt-xquery-serialization";
    declare namespace local = "localhost";
    declare option output:method "xml";
    declare option output:omit-xml-declaration "no";
    declare option output:indent "yes";
    declare option output:doctype-system "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd";

    declare function local:addSubNode($n)
    {
        for $subnode in doc("xml/flat-tree.xml")/tree/node[@id = $n]
            let $subnid:=data($subnode/@id)
            let $subtype:=data($subnode/@type)
        return <node id="{$subnid}" type="{$subtype}">
                {local:addSubNode($subnid)}
                </node>
        };

    <tree>

    {
    for $node in doc("xml/flat-tree.xml")/tree/node[not(@id = /tree/node/child)]
    let $nid:=data($node/@id)

    return <node id="{$nid}" type="{data($node/@type)}"> 
        {for $child in $node
        let $cid:=data($child)
        return local:addSubNode($cid)
        }

            </node>
    }

    </tree>

Answer 1

Just a partial answer - = and != can compare an atomic value against a sequence, but it works as a logical OR against each term. That is "a = b" means "is there a value in b that equals a" and "a != b" means "is there a value in b that does not equal a", which is not what you're looking for. You want "is there no value in b which equals a" which is "not(a = b)".

for $node in $d/node[not(@id = $d/node/child)] return
<node id="{$node/@id}" type="{$node/@type}">
    (: etc. :)
</node>

Answer 2

Ok got it! Eventually I fed the whole $node or $child element to the recursive function instead of just its id attribute, now it works!

    declare namespace output = "http://www.w3.org/2010/xslt-xquery-serialization";
    declare namespace local = "localhost";
    declare option output:method "xml";
    declare option output:omit-xml-declaration "no";
    declare option output:indent "yes";
    declare option output:doctype-system "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd";

    (:lookupChildren function :)
    declare function local:lookupChildren($p)
    {
    for $child in $p/child
    return $child
    };

    declare function local:addSubNode($n)
    {
    for $subnode in doc("xml/flat-tree.xml")/tree/node
            let $subnid:=data($subnode/@id)
            let $subtype:=data($subnode/@type)
    where $subnode/@id = $n/child
        return 
        <node id="{$subnid}" type="{$subtype}" children="{local:lookupChildren($subnode)}">
               {local:addSubNode($subnode)}
                </node>
    };

    <tree>

    {
    for $node in doc("xml/flat-tree.xml")/tree/node[not(@id = /tree/node/child)]
    let $nid:=data($node/@id)
    let $ntype:=data($node/@type)

    return  <node id="{$nid}" type="{$ntype}" children="{local:lookupChildren($node)}"> 
            {local:addSubNode($node)}

            </node>
    }

    </tree>