Topological sorting in XQuery

In the course of my attempts to implement an XQuery engine for the XML pipeline language XPL, I realized that I would need to sort the processes so that each process has its inputs available, i.e. a topological sort.

Given a sequence of nodes and references with the Relax-NG schema:

    element node {
           attribute id { xs:string },
           element ref {
               attribute id { xs:string }
           }*
       }+

The post-condition after sorting can be defined as:



declare function local:topological-sorted($nodes) as xs:boolean {
   every $n in $nodes satisfies
         every $id in $n/ref/@id
                satisfies $id = $n/preceding::node/@id
};

and the recursive function to order the nodes is:

declare function local:topological-sort($unordered, $ordered )   {
   if (empty($unordered))
   then $ordered
   else
       let $nodes := $unordered [ every $id in ref/@id satisfies $id = $ordered/@id]
       return local:topological-sort( $unordered except $nodes, ($ordered, $nodes ))
};

Sweet, eh? Even if this implementation is not the most efficient, it has the advantage of being obviously correct.

See (and improve!) the XQuery WikiBook article.