R. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

Y. [. Aho, J. D. Sagiv, and . Ullman, Equivalences among Relational Expressions, SIAM Journal on Computing, vol.8, issue.2, pp.218-246, 1979.
DOI : 10.1137/0208017

L. [. Buss and . Hay, On truth-table reducibility to SAT, Information and Computation, vol.91, issue.1, pp.86-102, 1991.
DOI : 10.1016/0890-5401(91)90075-D

[. Mohamed, M. Leclère, and M. Mugnier, Containment of Conjunctive Queries with Negation: Algorithms and Experiments, Lecture Notes in Computer Science, vol.6262, issue.2, pp.330-345, 2010.
DOI : 10.1007/978-3-642-15251-1_27
URL : https://hal.archives-ouvertes.fr/lirmm-00537832

P. [. Chandra and . Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing , STOC '77, pp.77-90, 1977.
DOI : 10.1145/800105.803397

M. [. Chein and . Mugnier, Conceptual Graphs: Fundamental Notions. Revue d, Intelligence Artificielle, vol.6, issue.4, pp.365-406, 1992.

M. [. Chein and . Mugnier, Graph-based Knowledge Representation and Reasoning?Computational Foundations of Conceptual Graphs. Advanced Information and Knowledge Processing, 2008.

[. Even, A. L. Selman, and Y. Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, vol.61, issue.2, pp.159-173, 1984.
DOI : 10.1016/S0019-9958(84)80056-X

C. Farré, W. Nutt, E. Teniente, and T. Urpí, Containment of Conjunctive Queries over Databases with Null Values, ICDT, pp.389-403, 2007.
DOI : 10.1007/11965893_27

D. [. Garey and . Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, 1979.

N. [. Gottlob, F. Leone, and . Scarcello, Hypertree Decompositions: A Survey, MFCS'01, pp.37-57, 2001.
DOI : 10.1007/3-540-44683-4_5

[. Goldreich, On promise problems (a survey in memory of shimon even, Electronic Colloquium on Computational Complexity (ECCC), issue.018, 1935.

]. G. Got87 and . Gottlob, Subsumption and implication, Inf. Process. Lett, vol.24, issue.2, pp.109-111, 1987.

]. A. Hal01 and . Halevy, Answering queries using views: A survey, VLDB J, vol.10, issue.4, pp.270-294, 2001.

]. G. Ker01 and . Kerdiles, Saying it with Pictures: a logical landscape of conceptual graphs, 2001.

M. [. Kolaitis and . Vardi, Conjunctive-Query Containment and Constraint Satisfaction, Journal of Computer and System Sciences, vol.61, issue.2, pp.302-332, 2000.
DOI : 10.1006/jcss.2000.1713

M. [. Leclère and . Mugnier, Simple Conceptual Graphs with Atomic Negation and Difference, ICCS, pp.331-345, 2006.
DOI : 10.1007/11787181_24

M. [. Leclère and . Mugnier, Some Algorithmic Improvements for the Containment Problem of Conjunctive Queries with Negation, ICDT, pp.404-418, 2007.
DOI : 10.1007/11965893_28

Y. [. Levy and . Sagiv, Queries independent of updates, VLDB, pp.171-181, 1993.

M. Mugnier and M. Leclère, On querying simple conceptual graphs with negation, Data & Knowledge Engineering, vol.60, issue.3, pp.468-493, 2007.
DOI : 10.1016/j.datak.2006.03.008
URL : https://hal.archives-ouvertes.fr/lirmm-00106650

L. [. Marcinkowski and . Pacholski, Undecidability of the Horn-clause implication problem, Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pp.354-362, 1992.
DOI : 10.1109/SFCS.1992.267755

L. [. Muggleton and . De-raedt, Inductive Logic Programming: Theory and methods, The Journal of Logic Programming, vol.19, issue.20, pp.629-679, 1994.
DOI : 10.1016/0743-1066(94)90035-3

]. Mug07 and . Mugnier, On the ? 2 p -completeness of the containment problem of conjunctive queries with negation and other problems, 2007.

]. O. Shm87 and . Shmueli, Decidability and expressiveness of logic queries, PODS, pp.237-249, 1987.

. [. Schmidt-schauß, Implication of clauses is undecidable, Theoretical Computer Science, vol.59, issue.3, pp.287-296, 1988.
DOI : 10.1016/0304-3975(88)90146-6

C. [. Schaefer and . Umans, Completeness in the polynomial-time hierarchy: A compendium, 2002.

J. [. Spakowski and . Vogel, Theta 2 p -completeness: A classical approach for new results, Ull89] J. D. Ullman. Principles of Database and Knowledge-Base Systems, Volume II, pp.348-360, 1974.

G. [. Wei and . Lausen, Resource Description Framework (RDF) Technical report, www.w3.org Containment of conjunctive queries with safe negation, ICDT, pp.343-357, 2003.