Problematic Datalog Rules
Introduction: There are certain Datalog rules or programs that technically have no meaning and should not be used. The two most important risks are
1. Unsafe rules: those that have a variable in the head that does not appear in the body in a way that constrains that variable to take on only values that appears in the EDB.
2. Unstratified programs: sets of rules that have a recursion involving a negation.
We shall elaborate on each of these risks.
Rule Safety: Any variable that appears in the head of a rule must also appear in the body.Moreover, that appearance must be in a sub goal that is an ordinary IDB orEDB atom. It is not acceptable if the variable appears only in a negated atom,or only in a comparison operator. The reason for this policy is to avoid rulesthat let us infer an infinite number of facts.
Example: The rule
p(X,Y) :- q(Z) & NOT r(X) kX^Y
is unsafe for two reasons. Variable X appears only in the negated subgoal r(X) and the comparison X / Y. Y appears only in the comparison. The consequence is that p is true for an infinite number of pairs (X, Y), as long as r(X) is false and Y is anything other than X.
In order for a program to make sense, recursion and negation must be separated. The formal requirement is as follows. We must be able to divide the IDB predicates into strata, so that if there is a rule with head predicate p and a subgoal of the form NOT #(•••), then q is either EDB or an IDB predicate in a lower stratum than p. As long as this rule is satisfied, we can evaluate the strata, lowest first, by Algorithm 12.15 or 12.18, and then treat the relations for the IDB predicates of that strata as if they were EDB for the computation of higher strata. However, if we violate this rule, then the iterative algorithm may fail to converge, as the next example shows.
Example: Consider the Datalog program consisting of the one rule:
p(X) :- e(X) & NOTp(X)
Suppose e is an EDB predicate, and only e(l) is true. Is p(l) true? This program is not stratified. Whatever stratum we put p in, its rule has a subgoal that is negated and has an IDB predicate (namely p itself) that is surely not in a lower stratum than p.
If we apply the iterative algorithm, we start with Rp = 0, so initially, the answer is "no; p (1) is not true." However, the first iteration lets us infer p (1), since both e(1) and NOT p (1) are true. But then the second iteration tells us p ( 1 ) is false. That is, substituting 1 for X in the rule does not allow us to infer p ( 1 ) , since subgoal NOT p ( l ) is false. Similarly, the third iteration says p(l) is true, the fourth says it is false, and so on. We conclude that this unstratified program is meaningless, and do not consider it a valid program.