Containment for queries over trees with attribute value comparisons

• We study the containment problem for query languages with attribute value comparisons.
• Attribute value comparisons in general do not increase the complexity of containment.
• Restrictions on the attribute domain do not affect the complexity, but the restriction on attributes being required does.

Björklund et al. [6] showed that containment for conjunctive queries (CQ) over trees and positive XPath is respectively Π2P and coNP-complete. In this article we show that the same problem has the same complexity when we expand these languages with XPath׳s attribute value comparisons. We show that different restrictions on the domain of attribute values (finite, infinite, dense, discrete) have no impact on the complexity. Making attributes required does have an impact: the problem becomes harder. We also show that containment of tree patterns without the wildcard ⁎⁎, which is in PTIME, becomes coNP-hard when adding equality and inequality comparisons.