
## 2. ∀ X ∈ V(Q), Λ(Π(X)) ≤ Λ(X)

We note Q ≥ G ( Q subsumes G ) if there exists a projection from Q into G . Typically, Q represents a query, G a fact, and projections from Q to G define answers to Q . In Fig. 2, suppose Researcher < Person, then there is one projection from Q into G. The image of Q by this projection is the subgraph G ′ of G .

## 2.2 Relationships With Fol

The semantics Φ maps SGs to the existential conjunctive and positive fragment of FOL.

Given a support S, a constant is assigned to each individual marker and an n-adic (resp.

a unary) predicate is assigned to each n-adic relation (resp. concept) type. For simplicity, we consider that each constant or predicate has the same name as the associated element of the support. A set of formulas Φ( S ) is assigned to any support S , translating partial orders on types. More specifically, for all distinct types t 1 and t 2 such that t 2 ≤ t 1 , one has the formula ∀ x 1 ... x p ( t 2 ( x 1 ,  ..., x p ) → t 1 ( x 1 ,  ..., x p )), where p = 1 for concept types, and p is otherwise the arity of the relation type. Given any SG G, a formula Φ( G ) is built as follows.

A term is assigned to each concept node: a distinct variable for each generic node, and the const ant corresponding to its marker otherwise. Then an atom t ( c ) (resp. t ( c 1 , ... , c k )) is associated to ea concept node ( resp. relation node r of arity k ), where t is the type of the node, and c (resp. c i ) is the term assigned to this node (resp. assigned to the i th neighbour of r ). Let α( G ) be the conjunction of these atoms. Φ( G ) is the existential closure of α( G ).

E.g. the formula assigned to the subgraph G ′ in Fig. 2 is ∃ x ∃ y( Researcher( x ) ∧ Project( y ) ∧
Researcher(K) ∧ member(x, y) ∧ member(K, y) ∧ works-with(x, K)).

Projection is sound and complete w.r.t. the semantics Φ, up to a normality condition for completeness; the normal form of a SG G is the SG nf( G ) obtained by merging concept nodes having the same individual marker. This SG always exists (and is computable in linear time with a naive algorithm). Figure 3 shows a counter-example to projection completeness when SGs are not in normal form: G for instance does not project to H , even if both SGs have the same logical semantics, but it projects to nf ( H ). A SG in normal form is said to be normal

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

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

Figure 3: The need for normal forms Theorem 1 (Chein & Mugnier, 1992; Gosh & Wuwongse, 1995) Let Q and G be two SGs defined on a support S . Then Q ≥ nf(G) if and only if Φ(S), Φ(G) = Φ(Q).