4 Firing rules
Consider the rule in figure 4, called "Number generator", which states that if ?value is a low natural number less than a particular limit and ?newValue is ?value plus one, then ?newValue is also a low natural number. Assume that the clauses lowNaturalNumber 1and limit 20 have been asserted to a database. Consider firing this rule, in a partition on its own, using forward chaining. On the first iteration, the antecedents are evaluated twice yielding the bindings {?value = 1, ?n = 20, ?newValue = 1}, and the clause lowNaturalNumber 2 is asserted to the database. On the second iteration, evaluating the antecedents again would succeed twice, yielding the same bindings in addition to {?value = 2, ?n = 20, ?newValue = 2}. On the third iteration, the antecedents would succeed three times, and so on. The rule can only fire once on each iteration (and no times at all on the final iteration), since no clause can be asserted to the same database more than once, but the antecedents would succeed 209 times before the partition is completed!
After the first iteration, a rule instance can only fire if it depends on some knowledge that has been deduced since the rule was encountered last time. This fact can be used to avoid retrieving clauses which cannot have any effect. In rule "Number generator", lowNaturalNumber ?value is the only clause in the antecedents that can be affected by any rule in the partition. Therefore, when this clause is evaluated, clauses asserted to the database before the rule was encountered last time (previous clauses) are ignored; only recent clauses can be retrieved. Thus, the rest of the antecedents are only evaluated once on each iteration, and they only succeed 19 times. Of course, databases must be represented in such a way as to facilitate the fast retrieval of recent clauses. In SDML, databases contain lists of clauses (with other information attached) ordered according to when they were asserted. Thus, recent clauses can be found first and it is not necessary to backtrack once a previous clause has been found. Thus, the time taken to fire this rule by SDML is proportional to the limit (plus a small constant); i.e. these techniques reduce the time taken to complete the partition from O(n2) to O(n).
Sometimes, more than one clause in the antecedents of a rule may be affected by other rules in the same partition. The optimal way to fire the rule at a particular iteration depends on which rules have been fired since it was last encountered. SDML generates structures called recency arrays, in which each recency corresponds to a clause in the antecedents. Each recency is either recent, previous, all or none, and specifies whether recent and/or previous clauses should be retrieved. Different recency arrays can be used with the same compiled rule, depending on the combination of rules that have recently fired. Recency arrays are generated automatically when required, and are cached for speed.
For example, there may be another rule called "Determine limit" in the same partition as "Number generator" which asserts a clause with keyword limit to the database. Consider attempting to fire "Number generator" when both rules have fired since it was last encountered. Recency arrays for this rule have two elements corresponding to the first two clauses of the rule. When the antecedents are evaluated, either or both of the clauses retrieved should be recent. This can be ensured by evaluating the antecedents twice with the recency arrays (recent, all) and (previous, recent). If only one of the rules has fired recently, then the antecedents are evaluated once, using the recency array (recent, all) or (all, recent) as appropriate.*1
Information about antecedents that can retrieve clauses from databases, and the order in which they are evaluated, is gathered when rules are being compiled. This information, together with information gathered when dependencies are computed, is used to generate recency arrays for particular combinations of rules which have fired recently. This procedure is quite complicated, particularly when backward chaining rules and assumptions are taken into account, and is beyond the scope of this paper. Since compilation information is required by this mechanism, recency arrays cannot be used when rules are being interpreted.
Thus, forward chaining can be performed efficiently for rulebases containing cycles, without resorting to imperative techniques. If clauses could be retracted, then the problems addressed by recencies need not arise; a clause which triggers a rule could be retracted to prevent the rule from firing again. Recencies cannot make every declarative rulebase efficient, but this technique can be very successful in well-behaved partitions without many cycles.
Generated with CERN WebMaker