Skip to Main content Skip to Navigation
Journal articles

On Querying Simple Conceptual Graphs with Negation

Marie-Laure Mugnier 1 Michel Leclère 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query. This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.
Document type :
Journal articles
Complete list of metadata
Contributor : Marie-Laure Mugnier <>
Submitted on : Thursday, November 9, 2006 - 2:24:01 PM
Last modification on : Saturday, May 30, 2020 - 3:39:50 AM


  • HAL Id : lirmm-00112647, version 1
  • PRODINRA : 318648



Marie-Laure Mugnier, Michel Leclère. On Querying Simple Conceptual Graphs with Negation. Data and Knowledge Engineering, Elsevier, 2007, 60 (3), pp.468-493. ⟨lirmm-00112647⟩



Record views