Does query evaluation tractability help query containment?

While checking containment of Datalog programs is undecidable, checking whether a Datalog program is contained in a union of conjunctive queries (UCQ), in the context of relational databases, or a union of conjunctive 2-way regular path queries (UC2RPQ), in the context of graph databases, is decidable. The complexity of these problems is, however, prohibitive: 2EXPTIME-complete. We investigate to which extent restrictions on UCQs and UC2RPQs, which have been known to reduce the complexity of query containment for these classes, yield a more "manageable" single-exponential time bound, which is the norm for several static analysis and verification tasks. Checking containment of a UCQ⊖′ in a UCQ ⊖ is NP-hard, in general, but better bounds can be obtained if ⊖ is restricted to belong to a tractable class of UCQs, e.g., a class of bounded treewidth or hypertreewidth. Also, each Datalog program ∏ is equivalent to an infinite union of CQs. This motivated us to study the question of whether restricting ⊖ to belong to a tractable class also helps alleviate the complexity of checking whether ∏ is contained in ⊖. We study such question in detail and show that the situation is much more delicate than expected: First, tractability of UCQs does not help in general, but further restricting ⊖ to be acyclic and have a bounded number of shared variables between atoms yields better complexity bounds. As corollaries, we obtain that checking containment of ∏ in ⊖ is in EXPTIME if ⊖ is of treewidth one, or it is acyclic and the arity of the schema is fixed. In the case of UC2RPQs we show an EXPTIME bound when queries are acyclic and have a bounded number of edges connecting pairs of variables. As a corollary, we obtain that checking whether ∏ is contained in UC2RPQ Γ is in EXPTIME if Γ is a strongly acyclic UC2RPQ. Our positive results for UCQs and UC2RPQs are optimal, in a sense, since slightly extending the conditions turns the problem 2EXPTIME-complete. Copyright ACM.