W3C home > Mailing lists > Public > www-ql@w3.org > July to September 2004

RE: XQuery and graph data

From: Michael Kay <mhk@mhk.me.uk>
Date: Wed, 1 Sep 2004 15:48:33 +0100
To: <markb@archweb.co.uk>, <www-ql@w3.org>
Message-ID: <E1C2WQD-0003lm-IQ@frink.w3.org>

> 
> I have XML data in the form of a graph (nodes, edges) and I 
> need to check if
> any cycles exist in the data before I join the data together 
> in one XML file.
> 
> Can anyone point me to any resources to do this? Has anyone 
> already done this in XQuery?
> 

There is an example of how to do this in my book XSLT 2.0 Programmer's
Reference, and the example translates directly into XQuery. 

If you don't want to buy the book, the code (together with a "main program"
that invokes it to look for cycles among the attribute sets in a stylesheet)
is here:

<xsl:stylesheet version="2.0"
     xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
     xmlns:xs="http://www.w3.org/2001/XMLSchema"
     xmlns:cyc="http://www.wrox.com/569090/cycles"
     exclude-result-prefixes="xs cyc">
     
<xsl:import-schema namespace="http://www.w3.org/1999/XSL/Transform"
                   schema-location="xslt20.xsd"/>

<!-- follow a direct reference -->
     
<xsl:function name="cyc:direct" as="schema-element(xsl:attribute-set)*">
  <xsl:param name="in" as="schema-element(xsl:attribute-set)"/>
  <xsl:sequence 
    select="$in/../xsl:attribute-set[@name=$in/@use-attribute-sets]"/>
</xsl:function>

<!-- test if A references B directly or indirectly -->

<xsl:function name="cyc:references" as="xs:boolean">
  <xsl:param name="A" as="schema-element(xsl:attribute-set)"/>
  <xsl:param name="B" as="schema-element(xsl:attribute-set)"/>
  <xsl:sequence select="
       if (cyc:direct($A) intersect $B)
       then true()
       else some $X in cyc:direct($A) satisfies cyc:references($X, $B)"/>
</xsl:function>

<!-- there is a cycle if A references A -->

<xsl:template match="/">
  <xsl:variable name="cyclic-attribute-sets" 
     select="/*/xsl:attribute-set[cyc:references(., .)]"/>
  <xsl:choose>
  <xsl:when test="empty($cyclic-attribute-sets)">
    <result>No cycles found</result>
  </xsl:when>
  <xsl:otherwise>
    <result cyclic-attribute-sets="{$cyclic-attribute-sets/@name}"/>
  </xsl:otherwise>
  </xsl:choose>
</xsl:template>

</xsl:stylesheet>

The book also shows how to generalize this so the code that looks for cycles
is independent of the way that the nodes and arcs are implemented.
Unfortunately this generalization relies on Dimitre Novatchev's technique
for simulating higher-order functions, which is dependent on XSLT and won't
work in XQuery.

Michael Kay
http://www.saxonica.com/
Received on Wednesday, 1 September 2004 14:49:13 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:17:16 UTC