4 Firing rules
A dependency graph can be constructed by finding all the dependencies in a rulebase. This graph indicates which rules may directly or indirectly affect each other. Rules are arranged in partitions, so that all rules in the same partition are directly or indirectly dependent upon each other (unless the partition contains a single rule, which need not be a dependent of itself). The partitions are partially ordered so that no rule in an earlier partition is dependent upon a rule in a later partition. An example dependency graph is illustrated in figure 1, with arrows from determiners to dependents and each partition shaded.
Partitioning can be utilised to improve the efficiency of forward chaining. The rules are fired in each partition, continuing until no more instances of rules in the partition can be fired (until every instance with true antecedents also has true consequents), before moving on to the next partition. In the rulebase of figure 1, rule R1 is fired before the rules in the other partition. Since no rule in a later partition can affect the antecedents of a rule in an earlier partition, there cannot be any further instances to fire after all the partitions have been dealt with. Partitioning increases speed by reducing the number of rules to be considered for firing at one time, reducing the likelihood that rules will be considered too early (before the antecedents have been deduced to be true), and therefore reducing the number of attempts to fire the same rule. It is obviously most effective in rulebases with many small partitions.
Dependencies can also be used to optimise the firing of rules within partitions, to try to minimise the number of attempts to fire each rule. If the rules within a partition are ordered, then the system can try each rule in that ordering in turn and repeat until no more rules can fire. An algorithm is therefore required to order the rules efficiently, to try to minimise the number of iterations. If a rule occurs earlier in the sequence than its dependents, then its consequents can be used by the dependents in the same iteration; otherwise they cannot be used until the next iteration. Therefore, a good heuristic is to put dependents later in the sequence than the rules they depend on. If the dependency graph is displayed graphically, with rules shown in order from left to right, then the aim is to minimise the number of dependency links from right to left. Indeed, the same rule ordering algorithm is used by SDML to display dependency graphs, as shown in figure 2. The chosen ordering is more efficient than (R2, R4, R3), which would take two iterations before the results of deductions made in R2 can affect R3, its results can affect R4, and its results can affect R2 again. This is all done in one iteration with the ordering shown in figure 2.
Dependencies can also be used to avoid trying to fire rules when the antecedents cannot have changed since the last time firing was attempted. For example, in the rulebase with the dependency graph shown in figure 3, if rule R3 has not fired since it was last attempted to fire rule R4, it is not necessary to check whether R4 can fire again. Similarly, all the instances of rule R1 can be fired in a single iteration using backtracking, whereas it is necessary to iterate if rule R8 succeeds.
SDML's facility to display dependency graphs is useful for the construction and debugging of rulebases. Dependency graphs are easier to navigate than unstructured lists of rules, and they are useful for understanding the deductions that are made when rules are fired. Errors can be spotted when two rules are unexpectedly shown to be dependent, or when the modeller thinks rules should affect each other but no dependency is shown. In our experience, well structured rulebases, with relatively few dependencies and small partitions, are more likely to terminate when rules are fired and are more robust to the addition of new rules, as well as being generally more efficient. Therefore, it is worthwhile for modellers to invest some time and effort in ensuring that their rulebases are well structured.
Dependencies and partitions are not original to SDML. Similar techniques were devised by Simon [15] to order variables when solving systems of simultaneous equations. Mobal [10] can similarly generate "predicate topologies" (ignoring arguments of predicates) which are used to restrict hypotheses when learning. Dependencies are used in [2] to reduce inter-process communication by parallel logic programs and in [4] to facilitate rules asserting and retracting other rules in the same rulebase. However, to the authors' knowledge, SDML is the first rule-based system to use dependencies to determine rule-firing order.
Generated with CERN WebMaker