

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

u()
with the so-called rules in Datalog, where all variables of the head must appear in the body (Abiteboul et al., 1995).  Such rules are also called safe in the literature.  Consider for instance the rules of Fig. 5: R 1 and R 2 are range restricted, while R 3 is not.

Also notice that a range restricted rule R can be decomposed into an equivalent set of rules D ( R ) with exactly one node in conclusion (either an individual concept node or a relation node). There is one rule for each node of the conclusion of R : for each individual node c , one rule with same hypothesis as R and a conclusion restricted to c ; for each relation node r , one rule whose hypothesis is the disjoint union of the hypothesis of R and of all individual concept nodes of the conclusion of R, and conclusion is r, with same neighbors as in R . The logical interpretation of such rules are (function free) range restricted Horn rules. If a SG Q is deducible from a set of r.r. rules R, then it is deducible from the set of their decompositions D ( R ), and reciprocally. However, as soon as constraints are involved, this equivalence does not hold any more.

## Property 11 A Set Of Range Restricted Rules Is A Finite Expansion Set.

Proof: Since all graphs are put into normal form, an individual marker appears at most once in a graph. The number of individual nodes created by the set of rules is bounded by M = [R] × maxRER|R(1)|. So the number of relation nodes created (no twin relation nodes are created) is bounded by N = ∑ n = 1 P n ( | V C ( G ) | + M ) n , where P n is the number of relation types with a given arity n appearing in a rule conclusion, and k is the greatest arity of such a relation type. So the closure of a graph can be obtained with a derivation of length L < N + M. We thus obtain GR in finite time.

Note that, contrary to general finite expansion sets, existence of the closure and existence of the full graph are equivalent notions in the case of range restricted rules. It follows from the proof of property 11 that the length of a derivation from G to GR is in O(nk+1), where n is the size of ( G, R ) and k is the greatest arity of a relation type appearing in a rule conclusion. This rough upper bound could be refined but it is sufficient to obtain the following property, which will be used throughout the proofs of complexity results involving range restricted rules.