paper on intersection of XPath expressions

[Anne Anderson <Anne.Anderson@sun.com>]

One of the problems that must be solved for any policy language that 
supports use of XPath expressions to identify policy vocabulary items is 
that the intersection of two XPath expressions is not always computable. 
  WS-PolicyConstraints supports such expressions, and defines a very 
small subset of XPath for which intersection is computable, but a more 
general solution would be helpful; for example, is there a broader set 
of XPath expressions for which intersection is efficiently computable.

I just noticed a paper that addresses this problem:
On the Intersection of XPath Expressions, by
Beda Christoph Hammerschmidt, University of Lübeck
Martin Kempa, sd&m AG
Volker Linnemann, University of Lübeck
9th International Database Engineering #38; Application Symposium 
(IDEAS'05)    pp. 49-57

Part of abstract:

In this paper we introduce the intersection problem for XPath and give a 
motivation for its relevance. We present an efficient intersection 
algorithm for XPath expressions without the NOT operator that is based 
on finite automata. For expressions that contain the NOT operator the 
intersection problem becomes NP-complete leading to exponential 
computations in general. With an average case simulation we show that 
the NPcompleteness is no significant limitation for most real-world 
database operations.

Regards,
Anne
-- 
Anne H. Anderson               Anne.Anderson@sun.com
Sun Microsystems Labs          1-781-442-0928
Burlington, MA USA