On the complexity of tree pattern containment with arithmetic comparisons
In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is Pi(P)(2)-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval ( , >=, =) attribute constraints. (C) 2011 Elsevier B.V. All rights reserved.
tree patterns arithmetic comparisons query containment databases xpath queries