On the Intersection of XPath Expressions

XPath is a common language for selecting nodes in an XML document. XPath uses so called path expressions which describe a navigation path through semistructured data. In the last years some of the characteristics of XPath have been discussed. Examples include the containment of two XPath expressions p and p' (p /spl sube/ p'). To the best of our knowledge the intersection of two XPath expressions (p /spl cap/ p') has not been treated yet. The intersection of p and p' is the set that contains all XML nodes that are selected both by p and p'. In the context of indexes in XML databases the emptiness of the intersection of p and p' is a major issue when updating the index. In order to keep the index consistent to the indexed data, it has to be detected if an index that is defined upon p is affected by a modifying database operation with the path expression p'. 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 NP-completeness is no significant limitation for most real-world database operations.