5.4 Optimisations

5.4.1 Partitioning

Section 4.3 described how dependencies between rules can be used to partition a rulebase, so that rules in later partitions cannot affect rules in earlier ones. Partitioning yields two advantages with respect to assumptions:

Assumptions can be resolved at the end of each partition, rather than at the end of the entire rulebase. Thus, any clauses that were asserted on the basis of assumptions which have been resolved to be false are retracted before moving on to the next partition. Therefore, the effect of making a wrong assumption is reduced.
If an assumable clause cannot be affected by any rule in the same partition (because its subclause is not dependent on any rule in the partition) then it is not necessary to generate an assumption. If the clause is true when it is evaluated the first time, it will remain true. In well structured rulebases, assumptions are only required for a minority of assumable clauses. Indeed, many partitions do not require assumptions to be used at all.

It is possible for one partition to have several possible resolutions, and for some of these resolutions to result in unresolvable conflicts in later partitions. When such a contradiction is discovered, SDML backtracks to a previous partition that may have caused the contradiction and tries to resolve that partition's assumptions differently. This could undermine the advantages of partitioning in certain rulebases, but has not proved a problem in practice.

Efficient Forward Chaining for Declarative Rules in a Multi-Agent Modelling Language - 16 FEB 95

[Next] [Previous] [Up] [Top] [Contents]

Generated with CERN WebMaker