Previous topic  Top  Next topic  Print this Topic
 

Range Restriction

 

All of the variables in a rule or a query must be range-restricted, i.e. for each variable one or more of the following conditions must hold:

1.The variable occurs in a positive (not negated) body literal which is not a built-in-literal (simple built-in, connector built-in, or aggregate).
2.The variable is bound top-down by constants in the query or in connected rules
3.A variable is bound by the output of a built-in-literal and all input-arguments of the built-in are range-restricted or ground. Which arguments are input and output of a built-in is defined by the signatures of the built-in.

Let us illustrate the above topics in examples. For the following rule all of the variables are bound and hence the query is range-restricted. The variables ?X and ?Y are bound because they occur in the positive literal p(?X,?Y) (condition 1). Built-in _add/3 has the signature {number,number,variable} which means that the first two (input) arguments must be bound to numbers and the third can be a variable and is hence an output parameter. Thus variable ?Z is bound because it is the output variable of built-in add and all of the input variables of add are bound (condition 3).

?- p(?X,?Y) AND _add(?X,?Y,?Z).

 

In the next query and rule the variable ?Y of the rule is bound top-down by the constant 5 in the query (condition 2). Variable ?X is again bound by the positive literal q(?X) (condition 1) and thus ?Z is bound as an output parameter of the add built-in (condition 3).

p(?X,?Y) :- q(?X) AND _add(?X,?Y,?Z).

?- p(?X,5).

 

In the next rule there is a transitive dependency of variable bindings through the built-ins given. Thus also ?U is range-restricted (condition 1 and condition 3).

p(?X,?Y) :- q(?X,?Y) AND _add(?X,?Y,?Z) and _add(?Z,?Y,?U).

 

The above mentioned conditions have the consequence that a rule or query is not range-restricted if a variable only occurs in a negated literal. Rules which have variables occurring in the head only are obscure because these variables must be bound top-down in every case for the rule to be range-restricted.