4 Firing rules
Backward chaining is sometimes much faster than forward chaining, particularly for rules which can deduce a lot of irrelevant knowledge. For some rules, backward chaining must be used because there are an infinite number of valid instances. For example, the clause appended ?list1 ?list2 ?list3 specifies that ?list1 is the result of appending the other two lists. Forward chaining cannot be used to append all lists of arbitrary lengths. Backward chaining rules can be fired recursively to determine ?list1 if ?list2 and ?list3 are instantiated to lists, or all valid combinations of ?list2 and ?list3 if ?list1 is instantiated.
In other circumstances, forward chaining is much faster than backward chaining, particularly for rules which deduce knowledge that will be used many times and rules with multiple consequents. In SDML, it is the modeller's responsibility to decide where to use forward and where to use backward chaining (in clause definition groups). This facilitates further optimisation of dependency graphs than would be possible if SDML could decide which to use in the middle of a rulebase. The order in which forward chaining rules are fired is governed by dependencies, whereas backward chaining rules are fired when required from within other rules. It is therefore useful to construct a forward dependency graph by discovering the dependencies between forward chaining rules. When searching for the determiners of a particular rule, backward chaining rules which may be fired by it are also considered, taking into account any bindings of variables which can be ascertained statically. In general, this procedure yields a simpler and hence more efficient forward dependency graph than the one that would be generated by eliminating backward chaining rules from the graph of dependencies between all rules.
In some systems such as Mobal [10], deductions made using backward chaining are stored on databases, to avoid having to make the same deductions again. However, storing all such deductions could use up a lot of memory and it would be slower for deductions that are only made once. Furthermore, checking the database may only find some bindings of the variables such that a goal is true, and backward chaining would still be required to find out if there are any more. Therefore, the results of firing backward chaining rules are not stored by SDML, and modellers must use forward chaining rules when they want the results of deductions to be stored on a database.
Generated with CERN WebMaker