S. 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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.259.2129

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

K. B. Mohamed, M. Leclère, and M. Mugnier, Containment of Conjunctive Queries with Negation: Algorithms and Experiments, STOC, pp.330-345, 1977.
DOI : 10.1007/978-3-642-15251-1_27
URL : https://hal.archives-ouvertes.fr/lirmm-00537832

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.

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.

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

]. 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. Kerdiles, Saying it with Pictures: a logical landscape of conceptual graphs, 2001.

M. [. Kolaitis and . Vardi, Conjunctive-Query Containment and Constraint Satisfaction Simple conceptual graphs with atomic negation and difference, ICCS, pp.302-332, 2000.
DOI : 10.1006/jcss.2000.1713
URL : http://doi.org/10.1006/jcss.2000.1713

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.

[. 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, Containment of Conjunctive Queries with Safe Negation, ICDT, pp.343-357, 2003.
DOI : 10.1007/3-540-36285-1_23