Another bridge can be built using rules. Indeed, a graph G satisfies a positive constraint C if and only if, considering C as a rule, all applications of C on G produce a graph equivalent to G. Or, more specifically: Property 5 A SG G π-violates a positive constraint C iff, considering C as a rule, the application of C on G according to π produces a graph not equivalent to G .

Proof: Let C be a constraint and G be a SG such that G satisfies C . If π 0 is a projection from C ( 0 ) into G , let us consider the graph G ′ obtained by the application of C (considered now as a rule) on G according to π 0 . Let us now build the following projection π ′ from G ′
into G: for each node v, π ′ ( v ) = v if v belongs to G: otherwise, v is a copy of a node w of C(1), and if π is one of the projections from C into G that extends π 0 , we have π ′ ( v ) = π ( w ).

Then π ′ is a projection of G ′ into G ′ and since G trivially projects into G ′ , they are thus equivalent.

This proves the { part of property 5. For the { part, we use the following property, proved by Cogis and Guinaldo (1995). In their property (prop. 6 of their paper) the SGs considered are connected graphs, but the proof holds for non connected graphs.

Property 6 (Cogis & Guinaldo, 1995) Let G be a SG and irr(G) be one of its equivalent irredundant subgraphs (if G is not redundant then irr(G) = G). Then there exists a folding from G to irr(G), i.e. a projection f from G into irr(G), such that the restriction of f to nodes of irr(G) is the identity (for every node x of irr(G), f(x) = x).

Suppose now G π -violates C . Since constraint violation is defined with respect to the irredundant form of a graph, we can consider, without loss of generality, that G is irredundant. We denote by G ′ the graph obtained by the application of C (again, considered now as a rule) on G according to π . We prove that " G l equivalent to G r leads to a contradiction.

If G ′ is equivalent to G ′ then there exists a projection from G ′ into G ′ And since G is an irredundant subgraph of G ′ , there exists a folding f from G ′ into G (property 6). Consider now π ′ the projection from C to G defined as follows: for any node x of C (0), π ′ ( x ) =
f(π(x)), otherwise let x' be the copy of x in G ′ , we have π'(x) = f(x'). Since for all x in C(0), f(π(x)) = π(x), π' extends π . This contradicts the hypothesis " G π-violates C n . Thus G is not equivalent to G.

□
Property 7  If a SG G satisfies a positive constraint C, then any graph in a {C}-derivation of G is equivalent to G.

Proof: Let G = G 0 , ..., G k be a { C } -derivation of G . From property 5, each G i , 1 ≤ i ≤ k, is equivalent to G i _1, thus by transitivity, is equivalent to G .

□
Using soundness and completeness of the SR deduction, and properties 5 and 7, one obtains the following relation with FOL deduction.

Theorem 7 A SG G violates a positive constraint C iff there exists a SG G¹ such that Φ(G), Φ(G), Φ(G) = Φ(G') and not Φ(S), Φ(G) = Φ(G'), where Φ(C) is the translation of C
considered as a rule.