5.4 Optimisations

5.4.2 Extending dependency graphs

It is useful to include assumable clauses as well as rules in dependency graphs. An assumable clause is a dependent of a rule if the rule may assert a clause that can be retrieved by evaluating the assumable clause. An assumable clause's dependents are the rules or other assumable clauses enclosing it.

When an assumable clause is encountered within a rule in a later partition, it is not necessary to create any assumptions (or assumption contexts) for the reasons described in the previous section. They are only required in partitions containing cycles. An assumable clause may have various assumption contexts, corresponding to different bindings of variables used within it. Each assumption context caches the results of evaluating the subclause, when it is encountered for the first time within an enclosing rule or assumable clause. If the same context is encountered again, the cached results can be used in order to avoid evaluating the subclause again.

If one of the determiners of an assumable clause fires, the results cached in that clause's contexts are quickly updated using recencies as described in Section 4.4. This may cause the overall results of some assumption contexts to change, creating new assumptions, and affecting the dependents of the assumable clause.*1 When these dependents attempt to fire, overall changes to these assumption contexts can also be propagated using recencies.

Including assumable clauses in dependency graphs reduces the number of times that an assumable clause or enclosing rule attempts to fire, and using recencies increases the speed of evaluation when it is required.

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

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

Generated with CERN WebMaker