Containment for tree patterns with attribute value comparisons
Evgeny Sherkhonov, M. Marx · International Workshop on the Web and Databases · 2013
Tree patterns (TP) is a simple and widely used fragment of XPath. The problem of containment in TP has been extensively studied previously. It was shown that the containment problem ranges from PTime to PSpace depending on the available constructs. In this paper we study the complexity of the containment problem for tree patterns with attribute value comparisons. We show that the complexity ranges between PTime and PSpace. We distinguish the parameters which have to be taken into account in the containment problem: (i) available axes, (ii) type of comparisons (e.g. 6 (iii) the underlying domain for attribute values (e.g. linear dense order) and (iv) optionality of attributes.