[xquery-talk] Need some theory help

[Michael Kay]

I've asked this in the past on other lists without success; in the hope that
this list is a better place to find some theoreticians, I'll ask it again
here.

Given general expressions E,F,G, I believe it is true that the following two
expressions are equivalent:

E/F union E/G <=> E/(F union G)

(That is, union distributes through "/")

But this is not true for "except".

$a/descendant::*/child::b except $a/descendant::*/(child::c/child::b)

is not the same as

a/descendant::*/(child::b except child::c/child::b)

(easily seen because child::c/child::b will not select any nodes that are
selected by child::b).

Questions:

(a) How would you prove that "union" distributes through "/" and "except"
does not? (Assuming my conjecture is correct, of course)

(b) What about "intersect": does it distribute or not?

(c) Is there a restricted class of path expressions for which "except" does
distribute through "/" (for example, path expressions that only use the
child axis)? How large can you make that class?

Clearly these questions are all directly relevant to the expression rewrites
that an optimizer can perform safely.

Michael Kay
Saxonica