deduction in FOL(^, 3) can be seen as an alternative version of the homomorphism theorem
(Chandra & Merlin, 1977), considered as fundamental for database queries optimization
(Abiteboul, Hull, & Vianu, 1995). Other results are obtained from constraint programming. The strong equivalence between SG-DEDUCTION and the CONSTRAINT SATISFAC-
TION PROBLEM (see Sect. 8, where the transformations used keep all solutions and preserve the structure of the constraint network in the query) allows to translate the results obtained in this latter community (by example, tractable cases based upon the structure of the graph, Gottlob, Leone, & Scarcello, 1999), first to SG-DEDUCTION , then to deduction in FOL(A, 3).

The graph structure can also be used to develop efficient algorithms in more general models of the SG family: in the model we call SR (see below), Coulondre and Salvat (1998)
use the graph-based notion of piece to build an efficient backward-chaining algorithm. To enhance the forward-chaining algorithm used in the more general models of the SG family, Baget (2001) expresses dependencies between rules and constraints in terms of a graph homomorphism.

Our aim is thus to build formal extensions of simple conceptual graphs, keeping readability of objects as well as reasonings, and preferably, logically founded. The SG family is a first step in this direction.

## 3.2 An Overview Of The Sg Family

Let us now informally present the SG family. The generic problem to be solved, DEDUCTION,
asks, given a knowledge base (KB) K and a simple graph Q , whether Q can be deduced from K. According to the kinds of objects composing K t one obtains the different members of the family. In the basic model SG, K is composed of a set G of simple graphs representing facts, and solving DEDUCTION amounts to check whether there is a projection from Q into G .

Rules and constraints are more complex objects based upon simple graphs, and operations dealing with these objects are based upon projection.

Throughout this section, we will use examples inspired from a modelization of a knowledge acquisition case study, called SYSIPHUS-I: it describes a resource allocation problem, where the aim is to assign offices to persons of a research group while fulfilling some constraints (Baget et al., 1999).

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

