5.4 Optimisations

5.4.5 Validities

In well-structured rulebases, most assumptions that are made are true. It is therefore worthwhile to assume that they are true until there is evidence to the contrary. This is implemented by giving every assumption a validity, which is one of the following: "assumed true", "assumed false", "known true", "known false" or "unknown". Assumptions are initially assumed true if they have no conflicting assumptions. If one assumption is assumed true, and another assumption relies on it being false, then the latter assumption is assumed false (if it has already been created; otherwise it is not created in the first place).*1 If an assumption's conflicting assumptions are known to be true, then the assumption is known to be false. Assumptions that are assumed or known to be false can be filtered out. This is done whenever clauses are retrieved from databases so that assumptions which are no longer assumed true are not propagated further.

The rules in a partition cease firing when all the consequences of assumptions with true or unknown validities have been deduced. Resolution is only used to determine which of the assumptions with unknown validities are true or false. If there is no valid resolution, then it may be because wrong validities have been assumed. The assumed validities are changed to unknown and rules in the partition are fired again, enabling new deductions to be made which allow the assumptions to be resolved.

When validities are used, the consequences of some assumptions are not deduced. If an assumption that was assumed false gets a true or unknown validity again, then the implementation must ensure that those further deductions are made by refiring rules. Fortunately, this is rarely necessary in well-structured rulebases.

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

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

Generated with CERN WebMaker