Subject: Re: A theory problem From: James Clark <jjc@xxxxxxxxxx> Date: Thu, 28 Oct 1999 17:33:37 +0700 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
A theory problem, Kay Michael | Thread | Re: A theory problem, david . rosenborg |
RE: Remove duplicates from a list, Jarno Elovirta | Date | Re: XML/XSL on the client for dynam, Dylan Walsh |
Month |