Technical Report No. 166 - Abstract

F. "Wei, G." Lausen
Query Containment for Conjunctive Queries with Safe Negation

The problem of query containment for conjunctive queries with safe negated subgoals has drawn considerably less attention in the past than other variants of the containment problem of conjunctive queries. In \cite{DBLP:conf/vldb/LevyS93} uniform containment is discussed, which is a sufficient, however not necessary condition for containment. In \cite{DBLP:conf/icdt/Ullman97} it is argued that the complexity of the containment test is $\Pi^p_2$-complete, however the given arguments cannot be used to design a general algorithm. In this paper, a general algorithm for testing the containment of conjunctive queries with safe negated subgoals and built-in predicates is presented. To any conjunctive query with safe negation and built-in predicates we construct an equivalent set of subqueries, where each subquery is in a certain normal form. The containment problem for conjunctive queries obeying the normal form can be polynomially reduced to the containment problem of conjunctive queries without negated subgoals, however with built-in predicates. The complexity of the latter problem is known to be $\Pi^p_2$-complete. Testing containment for conjunctive queries with safe negated subgoals and built-in predicates thus has the same complexity as testing containment for its positive counterparts, whenever the given queries are in normal form. For an arbitrary query, however, our approach may require an exponential number of tests, in the worst case. In addition it is shown that known results from the literature can be applied to lower the complexity by applying certain restrictions to the queries.