Search Results

Query containment is a fundamental database problem which has been extensively studied for conjunctive queries (CQs). The most famous result is arguably the Homomorphism Theorem: a CQ q₁ is contained in a CQ q₂ iff there is a homomorphism from q₂ to q₁. However, when extending conjunctive queries with safe base negation (CQ^¬), this test becomes incomplete, hence, requiring significantly more expensive procedures due to its inherently harder complexity (Π₂^P-hard). In this paper, we define and study the classes CQ^{1¬}_{HT} and CQ^{¬}_{HT}: the classes of conjunctive queries extended with one or several safe negated atoms that satisfy the Homomorphism Theorem, and hence, whose containment check is in NP. To characterise them, we define what we call the dependency-version of a query, which is a dependency that, intuitively, models the databases in which the query is false. It turns out that, when the query q contains one (several) negated atom(s), the query satisfies the Homomorphism Theorem iff its tgd(ded)-version is uniformly one-bounded. We also show that CQ^¬_{HT} membership is EXPTIME-hard, but its complexity reduces to Π₂^P in the CQ^{1¬}_{HT} case, and to NP when bounding the number of positive atoms that can unify with the negated one.