XPath 3.0 Recursive Query

Question

I have some XML data with an inheritance-like semantics, and I'd like to make a query that takes the inheritance into consideration. I know it is not possible in XPath 1.0, but I believe it is possible in XPath 3.0, but I'm not familiar with 3.0.

So I have a structure which is like this:

<elems>
    <elem id="n">
        <property name="xxx" value="yyy"/>
        ...
    </elem>
</elems>

Not, the property with name inherits points to the @id of another <elem>. So, basically, I want to query the @id of the <elem> which have (or do not have) a property Z, whether that property is on itself or on any of the elements chained through the inherits property. For example:

<elems>
    <elem id="1">
        <property name="a" value="alpha"/>
    </elem>
    <elem id="2">
        <property name="inherits" value="1"/>
        <property name="b" value="bravo"/>
    </elem>
    <elem id="3">
        <property name="inherits" value="2"/>
        <property name="c" value="charlie"/>
    </elem>
</elems>

So a query for elements with property c would return 3, and its reverse would return 1 and 2. A query for elements with property b would return 2 and 3 and its reverse would return 1. Finally, a call for elements with property a would return 1, 2 and 3, and it's reverse would not return anything.

How do I do that?

Doesn't my answer provide exactly the XPath solution you were looking for? — Dimitre Novatchev, Oct 11 '19 at 15:19
@DimitreNovatchev I didn't notice it -- it had been a while since I worked on this problem. I'll take a look. — Daniel C. Sobral, Dec 03 '19 at 10:07
@DimitreNovatchev Not yet, I haven't had the time. But I'm keeping this question on a tab in my browser, so I'll get to it. — Daniel C. Sobral, Dec 16 '19 at 19:55
Daniel, seems like your browser has crashed... Does it do so on every terrific solution? :) Happy Holidays — Dimitre Novatchev, Dec 24 '19 at 02:55
@DimitreNovatchev lol! No, not really... I had a really rough end of year, followed by a long and much needed vacation. I haven't even turned that computer on in almost four weeks. But, no, the browser has not crashed, and it's still in my to-do list since I _am_ still interested in this, it's just not a high priority anymore. — Daniel C. Sobral, Jan 22 '20 at 18:50
Sorry to hear that, Daniel. Please, don't worry about this at all -- it isn't that important. — Dimitre Novatchev, Jan 22 '20 at 22:26

score 3 · Accepted Answer · edited Sep 30 '18 at 11:59

3

What you are looking for is essentially a transitive closure, which is the most common type of recursive query; and basically XPath cannot do recursive queries, except in the special case of the ancestor and descendant axes which are built in.

XPath 3.0 allows you to define functions, but because they are anonymous, they cannot (easily) call themselves.

The "(easily)" is because there is an escape clause: apparently Y-combinators allow you to overcome this limitation. See for example What is a Y-combinator?. But I've never really got my head around them and would never attempt this in real life, because there's a much easier solution: use named functions in XQuery or XSLT, which make recursion very straightforward. In fact in XSLT 3.0 you don't even need recursion, you can use xsl:iterate.

edited Sep 30 '18 at 11:59

Mads Hansen

63,927
12
112
147

answered Jun 22 '18 at 07:27

Michael Kay

156,231
11
92
164

I have transite closures on XSLT 1.0, plus EXSLT. In fact, even as a separate transitive closure function I can use only passing the query as a string. However, I can't write a command line XSLT to query information on an XML in an ad-hoc basic. Maybe XQuery will do it -- I'm not really familiar with XQuery, but it seems Saxon supports writing them on the command line, though it looks incredibly cumbersome. Thanks for the answer, though. – Daniel C. Sobral Jun 23 '18 at 20:00
Can you expand on how to use `xsl:iterate` to achieve this? As far as I can tell, it will only iterate through the input given on `select`, and since there's no query that will provide such input without being recursive, I can't see how it would work. – Daniel C. Sobral Jun 25 '18 at 23:49
See this: https://dnovatchev.wordpress.com/2013/04/08/recursion-with-anonymous-inline-functions-in-xpath-3-0-part-ii/ and this: https://www.balisage.net/Proceedings/vol10/html/Novatchev01/BalisageVol10-Novatchev01.html – Dimitre Novatchev Nov 25 '18 at 01:23

Dimitre Novatchev · Answer 2 · 2019-10-05T21:30:03.853

Here is a pure XPath 3.1 solution:

The function $allProps() below, returns a sequence of strings that are the names of all the properties of an element whose id is equal to the $id parameter passed to the function.

In this sample expression the function $allProps() is called 3 times -- once for each "elem" element and the returned properties are delimited by a NL character:

let $root := /,
      $allProps-inner := function($id as xs:integer, $self as function(*)) as xs:string*
{
  let $elem := $root/*/elem[xs:integer(@id )eq $id],
        $ownProperties := $elem/property/@name[not(. eq 'inherits')]/string(),
        $ParentId := $elem/property[@name eq 'inherits']/@value
    return
      (
        $ownProperties, 
        if(empty($ParentId)) then ()
        else
           $self($ParentId, $self)
         )
 },

$allProps :=  function($id as xs:integer) as xs:string*
{ $allProps-inner($id, $allProps-inner ) }

return
  (
    $allProps(1), '&#xA;',
    $allProps(2), '&#xA;',
    $allProps(3), '&#xA;'
)

XSLT 3.0 - based verification:

<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xsl:output omit-xml-declaration="yes" indent="yes"/>

  <xsl:template match="/">
    <xsl:value-of select=
      "let $root := /,
           $allProps-inner := function($id as xs:integer, $self as function(*)) as xs:string*
          {
           let $elem := $root/*/elem[xs:integer(@id )eq $id],
           $ownProperties := $elem/property/@name[not(. eq 'inherits')]/string(),
           $ParentId := $elem/property[@name eq 'inherits']/@value
           return
           (
           $ownProperties, 
           if(empty($ParentId)) then ()
           else
             $self($ParentId, $self)
           )
          },

          $allProps :=  function($id as xs:integer) as xs:string*
          { $allProps-inner($id, $allProps-inner ) }

      return
         (
          $allProps(1), '&#xA;',
          $allProps(2), '&#xA;',
          $allProps(3), '&#xA;'
         )
      "/>
  </xsl:template>
</xsl:stylesheet>

When this transformation is applied on the provided XML document:

<elems>
  <elem id="1">
    <property name="a" value="alpha"/>
  </elem>
  <elem id="2">
    <property name="inherits" value="1"/>
    <property name="b" value="bravo"/>
  </elem>
  <elem id="3">
    <property name="inherits" value="2"/>
    <property name="c" value="charlie"/>
  </elem>
</elems>

the wanted, correct result is produced:

 a 
 b a 
 c b a

Finally, we reach naturally the solution of the original question:

So a query for elements with property c would return 3, and its reverse would return 1 and 2. A query for elements with property b would return 2 and 3 and its reverse would return 1. Finally, a call for elements with property a would return 1, 2 and 3, and it's reverse would not return anything.

How do I do that?

let $root := /,
      $allProps-inner := function($id as xs:integer, $self as function(*)) as xs:string*
{
  let $elem := $root/*/elem[xs:integer(@id )eq $id],
        $ownProperties := $elem/property/@name[not(. eq 'inherits')]/string(),
        $ParentId := $elem/property[@name eq 'inherits']/@value
    return
      (
        $ownProperties, 
        if(empty($ParentId)) then ()
        else
           $self($ParentId, $self)
         )
 },

$allProps :=  function($id as xs:integer) as xs:string*
{ $allProps-inner($id, $allProps-inner ) }

return
  (
    for $name in ('a', 'b', 'c')
      return
         ( $root/*/elem[$name = $allProps(@id) ]/@id, '&#xA;' )
)

When this XPath expression is evaluated (just replace the XPath expression in the transformation with this one), then the result when output is the wanted, correct one:

 1 2 3 
 2 3 
 3

XPath 3.0 Recursive Query

2 Answers2