Ways to tell if two XPath expressions have intersecting results

[Weston]

Are there any quick, reliable shortcuts to determine if two arbitrary
XPath expressions yield result sets that intersect?

The obviously way would be to iterate over the set of nodes from one
expression, checking each one to see if it's also contained in the
other set, but I'm wondering if there might be ways of doing this by
looking at or rewriting the actual XPath expressions themselves,
without evaluating them.

[Joseph Kesselman]

Weston wrote:

Are there any quick, reliable shortcuts to determine if two arbitrary
XPath expressions yield result sets that intersect?

In general, no. Appropriate logic on the paths can recognize cases that
must intersect, and cases that definitely can't intersect, but there's
going to be a huge set in the middle which depends on the actual data
the paths are being evaluated against.

Folks who have worked on XML processing have explored, published, and/or
patented some related techniques. So a literature search would seem to
be a good place to start... Sorry, I don't have any pointers already on
hand to pass you.

--
Joe Kesselman / Beware the fury of a patient man. -- John Dryden

[Anthony Jones]

"Weston" <no***********************************@canncentral .orgwrote in
message news:11**********************@y27g2000pre.googlegr oups.com...

Are there any quick, reliable shortcuts to determine if two arbitrary
XPath expressions yield result sets that intersect?

The obviously way would be to iterate over the set of nodes from one
expression, checking each one to see if it's also contained in the
other set, but I'm wondering if there might be ways of doing this by
looking at or rewriting the actual XPath expressions themselves,
without evaluating them.

(count(XPath1) + count(XPath2)) != Count(XPath1 | XPath2)

When creating union of node sets with the | operator any node common to both
sides will only be included in the resulting set once. Hence the above
boolean expression is true when XPath1 and XPath2 contain at least one Node
in common.

--
Anthony Jones - MVP ASP/ASP.NET

[Dimitre Novatchev]

"Weston" <no***********************************@canncentral .orgwrote in
message news:11**********************@y27g2000pre.googlegr oups.com...

Are there any quick, reliable shortcuts to determine if two arbitrary
XPath expressions yield result sets that intersect?

The obviously way would be to iterate over the set of nodes from one
expression, checking each one to see if it's also contained in the
other set, but I'm wondering if there might be ways of doing this by
looking at or rewriting the actual XPath expressions themselves,
without evaluating them.

In XPath 1.0 the following XPath expression selects all nodes that are the
intersection (belong to both) of two node-sets:

$ns1[count(. | $ns2) = count($ns2)]

Also knowns as the Kaysian (after Michael Kay) method of finding the
intersection of two node-sets.

In the above XPath expression just replace $ns1 and $ns2 with your two XPath
expressions.
Cheers,
Dimitre Novatchev

[Joseph Kesselman]

>>$ns1[count(. | $ns2) = count($ns2)]

>
I'd like to understand how it works, though, and I don't think I do.

The predicate is true if the union of . ("this node") and the node set
$ns2 is the same length as $ns2 by itself... in other words, if . is
already present in $ns2.

So applying the predicate to nodeset $ns1 yields "those nodes in $ns1
which are present in $ns2"... in other words, the intersection of the
two sets.
--
Joe Kesselman / Beware the fury of a patient man. -- John Dryden