Résumé: We present the Constructive Query Containment ( CQC) method to check query containment and query containment under constraints for queries over databases with safe negation in both IDB and EDB subgoals and with or without built- in predicates. The aim of the CQC method is to construct a counterexample that proves that the query containment relationship being checked does not hold. The method uses different Variable Instantiation Patterns ( VIPs) to generate only relevant counterexamples according to the syntactic properties of the queries and the databases considered in each test. The main contribution of the CQC method is threefold: it handles broader cases of queries and database schemas than most previous methods, it checks ‘‘true ’’containment instead of uniform containment ( which is a su .cient but not necessary condition for containment) and it is not less e .cient than other methods for the cases that they handle. Moreover, we prove also soundness and completeness of our method both for success and for failure.

Langue: Anglais