We tackle the containment problem for conjunctive queries with negation, which takes two queries q and q_1 as input and asks if q_1 is contained in Q_2- A general approach for solving this problem consists of considering all completions of q_1 (intuitively these completions represent all canonical databases that satisfy q_1) and checking if each completion yields the same answer on q_2- Since the total number of completions of q_1 is exponential in the size of q_1, several proposals have aimed at reducing the number (and the size) of the completions checked. In this paper, we propose a unifying framework for comparing algorithms following this general approach and define two kinds of heuristics for exploring the space of completions. Combining these heuristics with both classical kinds of traver-sals, i.e., depth-first and breadth-first, we obtain four algorithms that we compare experimentally with respect to running time on difficult instances of the containment problem.
展开▼
