Query Containment for Conjunctive Queries with Safe Negation
Abstract:
We consider the problem of query containment for conjunctive queries with safe negated subgoals ($\cqn$s). We propose a new method for the containment test of $\cqn$s. Comparing to the previous known approach, which always requires an exponential number of canonical databases to be verified to prove that $\qone \containedin \qtwo$, the algorithm proposed in this paper exploits the containment mappings of their positive counterparts, and terminates once the specified test succeeds. We show that in the worst case, the algorithm has the same performance as the one proposed in previous work. We also extend our algorithm to unions of $\cqn$s in a natural way. Due to the close relation between query containment and answering queries using views, we give some notes on considering answering queries using views when both queries and views have safe negated subgoals.