Supporting and Optimizing Full Unification in a Forward Chaining Rule System

The Rete and Treat algorithms are considered the most efficient implementation techniques for Forward Chaining rule systems. These algorithms support a language of limited expressive power. Assertions are not allowed to contain variables, making universal quantification impossible to express except as a rule. In this paper we show how to support full unification in these algorithms. We also show that: Supporting full unification is costly; Full unification is not used frequently; A combination of compile time and run time checks can determine when full unification is not needed. We present data to show that the cost of supporting full unification can be reduced in proportion to the degree that it isn’ t employed and that for many practical systems this cost is negligible.

Authors

• Howard E. Shrobe

Keywords

No keywords are indexed for this paper.