Match algorithms for generalized Rete networks

Abstract

We present a match algorithm which operates correctly on generalized Rete networks that allow arbitrary association of patterns. The original OPS5 Rete algorithm implements matching for left-associative joins; later work generalized this algorithm to support arbitrary join association. However, the naive extension of the OPS5 Rete algorithm to support arbitrary join associations has some subtle flaws (sometimes not all matches are produced with no duplicates) when processing networks having reconvergent (or self-joined) nodes. As a pedagogical means, we first describe an abstract match algorithm for an abstract Rete network having additional edge memories, which provides a useful model for general Rete operations. We then develop two practical specializations of the abstract algorithm, and prove their correctness. The first specialization corresponds to traditional Rete match implementation techniques that are guaranteed to operate correctly for generalized Rete networks. The second specialization is formulated in a general way that allows for delaying match processing at arbitrary stop points within the Rete, with correct match results available on demand at a later time. One current system uses a derivative of this algorithm to support Rete-based matching on demand, complementing the normal match computations done on data-change. © 1992.