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 Π2P-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.

► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is Π2P-complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete.