Re: A theory problem

[James Clark <jjc@xxxxxxxxxx>]

A path expression has the property if 

(a) it doesn't use / and the axis is a forward axis, or

(b) it is a / expression, and the left hand operand has the
"single-level" property and the right hand operand has the
"stays-in-subtree" property.

A path expression E has the "single-level" property if and only if for
any context node C, evaluating E wrt C yields a set of nodes all of
which have the same parent.

A path expression E has the "stays-in-subtree" property if and only if
for any context node C, evaluating E wrt C yields a set of nodes all of
which are in the subtree rooted at C (ie have C in their
ancestor-or-self axis).

It's easy to see this is a sufficient condition for the path expression
to have the property: if x and y have the same parent, and x is before y
in document order, then any node in the subtree rooted at x is before
any node in the subtree rooted at y.

XT implements this.

Kay Michael wrote:
> 
> I sometimes get asked for suggestions for student projects, so if there are
> any budding theoreticians out there, or professors trying to teach theory,
> here's a little problem I want to know the answer to. It's prompted by the
> recent discovery of a bug in SAXON.
> 
> The problem is as follows:
> 
> A path expression returns a nodeset. There is a "natural order" to the
> result which is obtained by following the steps in a particular sequence.
> For some path expressions the natural order will always be the same as
> document order, for others it will not. Provide an algorithm that examines a
> path expression and determines whether it will always return nodes in
> document order.
> 
> Here are some examples of path expressions that have this property:
> 
> child::X
> parent::X
> following::X
> descendant::X
> following-sibling::X
> child::X/child::Y
> child::X/descendant::Y
> following-sibling::X/child::Y
> parent::X/descendant::Y
> child::X/child::Y/child::Z
> 
> and here are some that don't:
> 
> ancestor::X
> preceding::X
> descendant::X/child::Y
> child::X/following-sibling::Y
> descendant::X/parent::Y
> 
> I can't see a pattern emerging, and where the path has more than two
> components I don't think I can rely on intuition any more, it needs some
> formal proof.
> 
> (I do know that I haven't stated the problem fully, in that I haven't
> defined the "natural order" of a step such as descendants::X. A more formal
> statement of the problem must obviously form part of any proof).
> 
> The motivation, of course, is that in SAXON I want to avoid doing a sort
> whenever possible. The prize for the winning entry is that the algorithm
> gets out into the wild!
> 
> Mike Kay
> 
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list



 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list