[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)
else:
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

>
>
>
> --