node c is labelled by a pair (type(c), marker(c)), where type(c) is an element of Tc, called its type, and  marker(c) is an element of I ∪ { ∗ }, called its marker.  If marker(c) is an individual marker m, then type(c)= τ(m).

A concept node with a generic marker is called a generic node (it refers to an unspecified entity of a certain type); otherwise it is called an individual node (it refers to a specific individual defined in the support). We will adopt the following classical conventions about SGs. In the drawing of a SG, concept nodes are represented by rectangles and relation nodes by ovals. In textual notation, rectangles are replaced by [] and ovals by (). Generic markers are omitted. Thus a generic concept label ( t, *) is simply noted t. An individual concept label ( t, m ) is noted t : m . When in our examples we use binary relations, we may replace numbers on edges by directed edges: a binary relation node is then incident to exactly one incoming and one outgoing edge. Fig. 2 shows two (connected) simple graphs PSfrag replacements G and Q assumed to be defined over the support of Fig. 1.

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

The elementary reasoning operation, projection, is a kind of graph homomorphism that preserves the partial order defined on labels. Let us first precise this order for concept node labels. We have defined the following partial order on the marker set I U {*}: * is the greatest element (for all m ∈ I, m ≤ ∗ ) and elements of I are pairwise non comparable. Then the partial order on concept node labels is the product of the partial orders on T C and I U { *}, i.e. (t, m) ≤ (t', m') iff t ≤ t' and m ≤ m'. In other words, a concept label (t, m) is more specific than a concept label ( t ′ , m ′ ) if t is a subtype of t ′ and, if m ′ = *, then m can be any marker, otherwise m must be equal to m ′ . Definition 3 (Projection) Let Q and G be two SGs defined on a support S. A projection from Q into G is a mapping π from V C ( Q ) to V C ( G ) and from V R ( Q ) to V R ( G ) which preserves edges (it is a bipartite graph homomorphism) as well as their numbering, and may specialize concept and relation node labels:
1. V(r, i, c) E U(Q), (π(r), i, π(c)) E U(G);