[xquery-talk] Function for determining one XPath as subset of another

Pavel Velikhov pavel.velikhov at gmail.com
Thu Jan 28 05:09:33 PST 2016

> On 28 Jan 2016, at 15:35, Adam Retter <adam.retter at googlemail.com> wrote:
>> So you need an algorithm to test subsumption of path expressions (with the given limitations)?
> Yes.
>> Or just that one case?
> No I want to cover any case where the set which would be selected by
> the path expression is statically known (i.e. no function calls).

I think this should work:

So suppose you have 2 path expressions, p1 and p2, and you allow only /x or //x as path steps
and each path step can have a predicate:

p1 = axis_1 pred_1, …, axis_n pred_n
p2 = axis_1 pred_1, … , axis_m pred_m

subsumes(p1, p2):
  /* recursion base case */
  if p1 is empty: return true
  if p2 is empty: return false

  a_1 = first axis of p1
  a_2 = first axis of p2

  if a_1 is a child axis ‘/‘ label l :
   if a_2 is a child axis ‘/' with the same label l, and the predicates are equivalent:
      return subsumes(p1 - a_1, p2 - a_2)
      return false

   if a_1 is a descendants axis ‘//‘ with label l:
     if p2 contains an axis with label l:
        p2’ = remove all axes of p2 from the head, until you find an axis with label l
        p2’ = remove the axis with label l from p2'
        return subsumes( p_1 - a_1, p2’ )

  return false

> -- 
> Adam Retter
> skype: adam.retter
> tweet: adamretter
> http://www.adamretter.org.uk

More information about the talk mailing list