TREE: the Heuristic Driven Join Strategy of a RETE-Like Matcher

1 Introduction

Match continues to be a problem for AI systems, espe­ cially for general .purpose production systems like SOAR [Laird et al., 1987]. In this kind of systems, a large flexi­ bility in representations is provided through their decom­ position into binary relations or into an object-attribute­ value paradigm. Consequently, basic data elements are mainly restricted to triples. As pointed out by Tambe and Rosenbloom [1990], this kind of restricted formalism leads to a combinatorial match since a condition element (CE) of a rule can match nearly all the working memory elements (WMEs), and condition parts of rules contain many CEs. Several works attempt to improve match algorithms for such systems. With or without paral­ lelism, efficiency gains can be obtained throu?h condi­ tion ordering [Smith and Genesereth, 1985; Ishida, 1988; Miranker, 1990], by restricting expressiveness [Tambe et al., 1990], or using hashing techniques [Gupta, 1987; Gupta et al., 1988].

·This work has been partly supported by the Program for Artificial Intelligence (PRC-IA) of the French Ministry of Research.

TREE [Bouaud, 1992] is a state-saving match algo­ rithm that has been designed for K, a production system with a restricted data formalism: WMEs are triples of symbols. TREE aims at reducing the size of join search spaces without using hashing techniques. It differs from RETE [Forgy, 1982] in its indexing scheme which does not rest on "memory support" [McDermott et al., 1978], i.e. based on the CEs, but on the sharing of references to symbols. In this framework, we investigate a new join formulation. A constraint propagation and a heuristic relaxation based on the·data paradigm is performed on the CEs in order to select the indexes to be used in the join step computation. These indexes are expected to be smaller than those built up from the CEs.

The paper is organized as follows: section 2 mentions RETE and join issues are revisited in the framework of the "k-search model" [Tambe et al., 1990]. The features of our system and the TREE algorithm are described in section 3. Section 4 reports experimental data about TREE's strategy in comparison with RETE's. These re­ sults and related works are discussed in section 5.

2 Background

We assume the reader is familiar with production system issues and the RETE algorithm. Condition parts of rules are mostly represented by conjunctions of CEs. Using the database terminology, an n-ary CE conjunction is represented by:

where 1><1 is the binary join operator. Tambe et al. [1990] showed that most match algorithms were based on the same model, referenced as the k-search model: an ex­ haustive standard backtracking search is made to ex­ hibit every instantiation of an n-ary join. A conjunction is processed from left to right according to the recur­ rent formula: CE1...k = CE1.. .k-1 1><1 CEk until CE1.. .n is produced. The trace of this algorithm yields an in­ stantiation tree where nodes at depth k are the partial instantiations corresponding to CE1.. .k·

In state-saving algorithms, all intermediate join results are memorized in what we shall call by analogy with the working memory (WM) the instantiation memory (IM). Then, each partial instantiation is an instantiation memory element (IME). Problems of IM update arise when a new WME is added or an old one is removed.

Following the k-search framework, the problem of completing a given partial instantiation can be described as follows:

Let i be an IME of CE1. .. k- 1 which is to be joined to CEk. Computing i IX1 CEk requires to find all the WMEs 4 hat both match CEk and satisfy some compatibility tests with i which are mainly equality tests between variable val­ ues. These WMEs constitute the solution space of this join. We shall call such a join aiming at completing a given IME an /-join.

The problem of IM update when a WME is added is to find every IME that the WME completes. When a WME is deleted, all IMEs including the WME must be deleted. We shall address this problem later on. Adding a new WME can be described as follows:

Let w be an added WME. For each CEk that matches w, the join CE1.. .k- 1 IX1 w must be computed to update CE1. .. k. This r·~quires to find all the IMEs of CE1.. .k- 1 such that w sat­ isfies their compatibility test. These IMEs con­ stitute the solution space of this join. Similarly, such a join aiming at updating IM from a WME will be called a W-join.

An index can be defined as a built-in relation: the set of its tuples can be directly enumerated. The indexing schemes of WM and IM are very important as indexes constitute practical search spaces for the joins. A neces­ sary condition for an index being used in an 1- or W-join is to include the solution space.

2.1 The RETE matcher

Like most matchers, RETE's indexing scheme is based on the CEs of a rule base. The set of WMEs matching a given CEk is stored in an a-memory, and the instantia­ tions of a given CE1. .. k- 1 are stored in a /3-memory. /3memories constitute the IM. RETE's abstract procedures for IME and WME adds are given in Figure 1 where c, p and r are respectively the number of CEk with an iden­ tical CE1...k- 1 (node sharing), of CEs matching w, and of CE1.. .k- 1 whose CEk matches w.

a- and /3-memories can be accessed from each other as they are connected in the RETE network that reflects the CE ordering. Data elements (WMEs) and partial in­ stantiations (IMEs) are called tokens without distinction as they traverse identically the network in order to com­ pute joins. Considering a linear RETE network, IMEs correspond approximately to left tokens, WMEs to right tokens, and 1- and W-joins to left and right join acti­ vations. The selection step, ADD-WHE.1, deals with the maintenance of WM. A number of tests are applied to a WME for assigning it to the right a-memories. Unlike the join step, this step is not costly and can be optimized [Ghallab, 1981].

When memories are implemented as linear lists and as the basic binary join algorithm is the cross­ product, ADD-IHE is basically c:omputed in O(c.ICEkl) and ADD-WHE in O(p.r.ICEl.. .k-!1) where the notation lXI stands for the cardinality of X. As for WME removal, RETE uses the same procedures as for adds except that store operations in memories are substituted by remove operations. Then, a WME removal is at least as costly than an add. This last point has often been criticized for state-saving algorithms [Miranker, 1990].

2.2 Improving RETE's joins: H-RETE

In practice and even with a good CE ordering, ICEkl and ICE1...k-d can be large thus limiting RETE's effi­ ciency. Indexing techniques like hashing can be used to improve the join step by reducing the search spaces [Gupta, 1987]. Most of join tests being equality tests, memories can be hashed according to the variable to be tested. Two global hash-tables are used for WM and IM. The hash code for a token (WME or IME) is a func­ tion of the value of the variable to be tested and of the actual memory (a or /3) location. As a result, hash­ values constitute memory indexes for joins. Their sizes depend on the hash-table sizes and on the quality of the hash-function. Though the aim of hashing is to access the solution space, it only provides a good search space reduction, by a tenfold factor as usually acknowledged. But, it is also known that the overhead of computing hash-values can eliminate the benefits of this reduction for small sets compared to a list implementation [Aho et al., 1983].

3 The TREE algorithm

3.1 Working framework

TREE has been implemented for a general purpose pro­ duction system, K, where WMEs are triples of sym­ bols, e.g. [F R V]. This structure is close to SOAR's and the equivalent notation would be: (triple -identifier F - attribute R -value V).

Indexation in K is not CE-based but organized on the criterion of sharing an identical reference to an identical symbol: WMEs are not aggregated according to their membership of CEs, but to the fact that they contain the same symbol at the same location (identifier, attribute, or value). For instance, the WME [F R V] is indexed 3 times: by F as first field, R as second, and V as third. In the following, we consider indexes as simple patterns. Hence, [F R V] is indexed by the patterns [F??], [?R?], and [??V], where? are unnamed free variables.

The set of symbols defines the indexing scheme of K insofar as each symbol S in the system controls the in­ dexes [S??], [?S?], and [??S] both in WM (for WMEs) and in IM (for IMEs). The six corresponding indexes are additional fields of a symbol and their content are simply implemented as linear lists. A symbol is unique and created when it is fir;;t referenced either at read time or during execution. As a result, symbols, and there­ fore their corresponding indexes, always exist before any WME that refers to them is created. When the WME [F R V] is created, the symbols F, R, and V are accessed and the WME is directly stored without test in the three indexes [F??], [?R?], and [??V]. This constitutes TREE's selection step which is independent of any rule base.

3.2 TREE's principles

TREE aims at reducing the size of join search spaces, making the most of K's actual indexing scheme. It mainly differs from RETE in the I-join formulation where contextual constraints (variable bindings) :~re used to de­ termine the join index.

The problem of WME removal in our implementation is treated like in [Dixneuf et al., 1988] where dependency links between IMEs are memorized. IMEs are organized in a tree structure according to the instantiation tree of the k-search algorithm. This tree is independent of the join strategy used to build or update it. When a WME is deleted, the subtrees the roots of which are the WME are deleted. Thus, WME removals are like the instantiation tree independent of the join strategy. We do not address here the evaluation of this method.

Now let us consider the !-join i ~ CEk where i E CE1.. . k~l· Let CP~ be the constrained pattern obtained by the substitution of the bound variables of i in CEk. The corresponding constraint propaf!ation function is noted P and CP~ = P(i, CEk)· CPj. describes the so­ lution space of the initial join: every present or future WME matching CP~ is successfully joined to i with­ out test. For instance, let i be an instantiation where ?x is bound to A, CEk = [?x P ?y], and the !-join be i ~ [?x P ?y]. Applying P we obtain P(i, [?x P ?y]) = [A P ?y] and the initial join is equivalent to i x [A P ?y] . Now, two situations must be considered:

1. CP~ is an index: the search space WM[CP~] is ex­ actly the solution space and this !-join is computed optimally. For the future updates of i, i is stored in IM[CP~]. The idea is to group IMEs accord­ ing to the WMEs that will complete them, not to their membership of CEt.. .k- 1: every added WME matching CP~ completes i without test.
2. CP~ is not an index: some constraints on CP~ must be relaxed in order to find a subsuming relaxed pat­ tern RP~ that is an index. We note the constraint relaxation function n and the initial join is turned into another one: i ~ n(i,CPD. WM[RP~] de­ scribes the new search space, wider than the solu­ tion space CP~, but including it. WMEs matching RP~ complete i only if some compatibility test. suc­ ceeds. For future updates, i is stored in IM[RPj.]. In our example, the constrained pattern [A P ?y] is not

an index but [A ?t ?y] is, then n(i, [A P ?y]) could be [A ?t ?y] and therefore the initial join would be computed as i ~ [A ?t ?y] with the test ?t = P.

With regard to the whole join algorithm, TREE computes the same joins as RETE, but initial !-joins i ~ CE~c are re­ formulated as i ~ n(i, P(i,CEk)), where P(i,p) returns the substitution of i in p, and n(i,p) returns an index subsuming p. In the following, every pattern p is consid­ ered within an !-join ( i given) so that we use the notation n(P(p)) in place of n(i, P(i,p)). RETE's procedures are consequently slightly modified for TREE (Figure 2) . ADD-IHE is basically computed in O(c.!n(P(CEk))l) and ADD-WHE in 0(3.IIM[Index]l).

ADD-IME(i/ match(i, CEt. .. t-d)

1. Get c GEt

2. For each GEt do

2.1. Let Index='R(i,'P(i,GEt))

2.2 . Store i in IH[Jndex)

1. For each wE WH(Index] do If test then ADD-IME(i X tv)

ADD-WME(w/w = [F R V])

1 . For each Index E { [F??], [?R?], [??V]} do

1 . 1 Store w in WH[Jndex)

1.2 For each i .E IH[Index) do

If test then ADD-IHE(i X w)

Figure 2: RETE's modified procedures for TREE.

Since only the search spaces of joins are changed, it is not possible to demonstrate which of TREE and RETE performs better joins without explicit relations between index cardinalities, i.e. ICEI vs. ln(P(CE))I, and ICEt. .. kl vs. IIM[indexJI. If P could be used 1 alone one could not perform a better join computation. But, building an architecture providing all possible indexes is unreasonable. n could be also easily directed toward the initial CE, but we would return to the RETE model. As a consequence, efficiency depends on n which itself depends on the predefined indexing scheme.

3.3 A heuristic constraint relaxation

In our implementation, n is heuristic based. Unlike P which depends on both a CE and its local constraints (variable bindings), n only considers its argument, a pattern, to deliver an index. The heuristic principles rest on the expected cardinalities of different pattern types which themselves depend on the properties of the for­ malism the WMEs are used for. Since triples are mainly used in the relational paradigm, we assume that the no­ tation [F R V] expresses that F is in relation R with V. We also assume that the number of relations is relatively small compared to the number of other symbols. In the general case and back to pattern cardinalities, I[? R?JI is expected to be much greater than I[F??JI and I[??Vjl, and, I[??VJI to be close to, or even smaller than, I[F?? I, whatever the symbols F, V, and the relation R.

TREE's !-join formulation is realized at compile-time. Within an ordered conjunction, noP is virtually applied to each CE. If the type of P( CE) is [F??J, [?R?] or [??VJ, where letters correspond to known places (symbols or bound variables), then it corresponds to an index that the matcher will use. In the other situations, P( CE) is not an index and constraint relaxation applies. Here is how R selects a subsuming index for each of the five non index pattern types accc·rding to our assumptions:

1 This is only true considering a RETE-like algorithm, with a given initial WM and a given conjunction ordering.

• R([?RV]) = [??V], instead of [?R?];
• R([FR?]) = [F??J, instead of [?R?];
• R([F?V]) = [??VJ, instead of [F??J;
• R([FRV]) = [??V], instead of [F??J or [?R?];
• [???], which describes the whole WM, is a special case. We suppose that such a CE will never remain unconstrained (P([???]) # [???]).

The plain lines in Figure 3 represent our constraint relax­ ation function between pattern types 2 whereas dashed lines represent the subsumption relation and illustrate how constraint propagation can apply.

Now the question is: are the search spaces of 1-joins and W-joins defined by RoP applied to the CEs smaller than those defined by the CEs themselves?

4 Experimental measurements

In order to evaluate TREE's join strategy and compare it with aCE-based join, some experimental measurements were carried out with K. Five rule-based programs de­ velopped in our laboratory were used as benchmarks: MAB, the "monkey and bananas" problem [Brownston et al., 1985]; ALEXIA, a qualitative model for hypertension [Bichindaritz and Seroussi, 1992]; CHART, a syntactic chart parser; AMD, a semantic analyzer for natural lan­ guage [Cavazza and Zweigenbaum, 1992]; and ABACAB, a blackboard controller [Bachimont, 1991]. Table 1 pro­ vides some of their external characteristics.

4.1 Pattern cardinality measurements

We first studied the cardinality in WM of every possible pattern at the end of each execution. The average cardi­ nalities of each pattern type are reported in Table 2. As these numbers correspond to the cardinalities of poten­ tial CEs, search and solution spaces for 1-joins, the CE

2 Pattern types with a* correspond to indexes.

tranformations P and R can be quantified. From now on, it must be noted that all quantitative information is given on average.

As expected, the cardinality of [?R ?] is always the highest ( [???] excepted). I[? R?]l is much greater than the cardinalities of the other indexes, [F??J and [??V], by a factor ranging from 2.6 (I[?R?]I/I[F??JI , ABACAB) to 51 (I[?R?JI/I[??VJI, ALEXIA). I[??VJI is only slightly smaller than I[F??JI , the reduction factor is not very im­ portant, no more than 7 (I[F??JI/I[??VJI, ALEXIA). This ensures that the heuristic foundations for TREE were correct at least for these programs.

Considering the constraint propagation function P and a CE, we know that IP(CE)I ~ ICEI. Thus, the reduction or gain factor g = 1 J~1ll due toP, if applied in some relevant cases, could vary from 1 (no constraint) to more than 1000 (1[???]1/I[FRV]I = 3772, ALEXIA). Now, let us consider the constraint relaxation function R for non index patterns. The cardinalities of [F??] and [??VJ, which are the indexes selected by R in our case, are rather low, 12 being a maximum ([F??J, ALEXIA) . As the cardinalities of non index patterns are yet lower, the expansion or loss factor l = ljVtf;)PI due toR ranges from 1 (I[??VJI/I[?RV]I, CHART) to 7 (I[F??JI/I[FR?]I, ALEXIA). Thus, we can see that for 1-joins, the gain factor due to P could reach three orders of magnitude whereas the loss factor due to R would be always inferior to one order of magnitude.

4.2 Analysis of pattern distributions

In a second step, the rule bases were analyzed to study qualitatively how P and R apply. Table 3 reports the pattern type distributions of: the CEs, the CEs con­ strained by P, and the indexes resulting from RoP ap­ plied to the CEs. A CE column gives the CE distribution in the rule base. It also corresponds to the kind of search spaces RETE would use for 1-joins. A P column describes the solution spaces of these 1-joins, and a 'Ro'P column, their search spaces with TREE.

Comparing column CE with 'Ro'P illustrates how the initial search spaces defined by the CEs are transformed by TREE. With the numbers of Table 2 in mind, one should notice that for each program:

1. Most of the CEs correspond to high C'"!.rdinality pat­ terns, [?R ?] being the most frequent and [???] some­ times used {AMD and ABACAB);
2. Most of the CEs are constrained, especially [?R?] and every [???], and the constrained CEs correspond to low cardinality patterns;
3. As most of the constrained CEs are non index pat­ terns, 'R is often applied and [F??] and [??V] are mainly used, the cardinalities of which are not high.

These points highlight that high gain factors g due to 'P and low loss factors l due to n are often expected, 1 . . b" d d . t" ICEI !I. resu tmg m a com me re uctwn ra 10 I"R(P(CE))I = 1 due to 'Ro'P greater than 1. However, this would be only valid for 1-joins, but in practice the previous arguments are not sufficient to determine whether the loss due to 'R discards the benefits from 'P or not. Yet, no similar information is available for W-joins.

4.3 Program execution measurements

Finally, each program has been run with three different join strategies. The only difference between them lies in the indexes used to search WMEs (in 1-joins) and to store IMEs (for W-joins): TREE uses the indexes deter­ mined by the heuristic 'Ro'P function applied to the CEs. RETE uses the initial CEs as indexes and then simulates a standard RETE linear network. OPT! is a simulation; only 'P is applied. It is as if the solution space of every join was directly accessible: search spaces were exactly solution spaces.

The number of comparisons per join is used as the metric for comparing the strategies as it corresponds to the size of the ·search spaces explored during join at­ tempts. The smaller this number, the more efficient the join strategy. Moreover, this metric is adequate to com­ pare indexing schemes [Miranker et al., 1990]. For a given program, identical initial WM and condition or­ dering were used. Comparing the number of generated "tokens" {IMEs) as in [Nayak et al., 1988] is inappro­ priate here because the general algorithm is the same, used in the same conditions, and consequently produces identical IMEs: every join has the same solution space whatever the strategy. As ewry local join is optimal in OPT!, this "virtual" strategy is the best one and neither TREE nor RETE can outperform it: in the same condi­ tions, it is not possible to do less comparisons.

Statistics about the number of comparisons per 1- and W-joins are recorded in Table 4. Only non empty join attempts, i.e. with at least one comparison, were con­ sidered. Runtime performance is not significant here since the RETE and OPT! strategies were emulated from TREE's. Although each result could be separately dis­ cussed, some points must be emphasized.

1 - The average number of comparisons per join ( Avg.) is lower with TREE than with RETE whatever the program. Thus, actual search spaces defined by 'R o 'P, for both 1- and W-joins, are smaller than those defined by the CEs. The resulting reduction ratio ranges from 1 up to nearly two orders of magnitude and the same trend is also observed for standard deviation (SD) and maxima (Max.p

2 - For every program, MAB excepted, TREE's number of non empty join attempts is approximately the same as, or even smaller than RETE's. This being combined with the previous result explains that the total number of comparisons per execution (Sum) is always much smaller with TREE than with RETE by a factor ranging from 10 (W-joins of AMD) to 74 (W-joins of ABACAB).

3 - MAB, which is a simpler program, is an interesting case for it illustrates a situation where RETE performs better than TREE: RETE's total number of comparisons for W-joins is lower and though TREE's search spaces are smaller than RETE's, more join attempts are performed, just enough to cancel out the previous benefits.

4 - The number of comparisons of OPT! corresponds to the number of solutions of the joins. With this number and those of RETE and TREE, a global gain factor G due to constraint propagation and a global loss factor L due to constraint relaxation can be estimated. Table 5 gives such ratios. G is RETE/OPT! and ranges from 5 to 750 whereas L, which is TREE/OPT!, never exceeds 22. As previously noted the global resulting reduction ratio RETE/TREE is between 1 and nearly two orders of magnitude. Actually, this shows that in our most complex programs the effect of 'P outdoes the effect of 'R even during execution, then producing an actual search space reduction. MAB excepted, this reduction seems to increase with the number of WM modifications. As a global result, TREE does less comparisons than RETE for both I- and W-joins.

3 These properties are very interesting in the framework of parallel implementations [Gupta, 1987).

5 Discussion and related works

On the basis of experimental evidence, TREE has shown a better performance than a standard RETE on the over­ all number of comparisons performed during join at­ tempts. This result has been obtained with five pro­ grams in different areas that all satisfied the assumption of the relational paradigm. To explain this result, we can observe that most of the CEs mention explicit re­ lations: [?x R ?y]. These CEs are also nearly always linked through variable sharing such that often ?x or ?y are bound. In this situation, TREE choses [F??] or [??V] as indexes. For the join step, TREE prefers using the contextual constraints of variables bindings to focus the searches instead of the definitional constraints of the CEs that RETE would use. Under our assumption and with the previous results, it appears that the contex­ tual constraints are stronger than the definitional ones. Moreover, this tendancy is not expected to collapse as the WM size increases. In this situation, we expect new symbols to be created, new connections to be made, but no (or few) new relations to appear. As a result, I[?R?JI would increase whereas both I[F??JI and I[??VJI would very likely remain constant. Therefore, the global re­ duction ratio due to TREE is also expected to increase making still more difference with RETE. This is an hy­ pothesis that would have to be studied and confirmed.

Several other works attempt to improve the join step by the use of indexing techniques which are not {only) based on CEs. The domain-based indexing of a new version of TREAT [Miranker et al., 1990] relies on the actual values of variables in a rule.

The role of hashing in H-RETE is also to provide smaller join search spaces. It is usually acknowledged that hashing techniques provide a tenfold reduction. Gupta et al. [1988] exhibit on three 0Ps5 programs search space reductions ranging from 1 to 12. This num­ bers indicate that H-RETE and TREE provide the same range of search space reduction though we did not test the H-RETE strategy on our programs. Nevertheless, the overhead due to hash-code computations can be impor­ tant and can sometimes eliminate the benefits of hashing. Compared to that, TREE's indexing scheme maintenance cost is low even compared to RETE's because no test is performed.

The predefined indexing scheme provides some addi­ tional advantages. Random WM access is handled effi­ ciently either by static pattern-matching or by program. Since it is independent of the CEs and therefore of any rule base, new rules can be dynamically compiled with­ out any WM re-structuration. As a RETE-like algorithm, TREE also handles some features that have not been dis­ cussed such as "node sharing", explicit right join opera­ tor, and negated CE conjunction.

Though TREE and H-RETE would provide quantita­ tively identical effects, we would like to point out some qualitative difference. The nature of an index is sym­ bolic with TREE versus numeric with H-RETE and the index choice is made according to a heuristic strategy versus to some hashing algorithm. The index choice can be made at compile time with TREE whereas it must be made at runtime with H-RETE. Lastly, changing the index choice can be made according to some qualitative reasonning versus some numerical algorithm. This al­ lows us to consider the possibility of taking into account some properties of representations in order to improve production system performance.

6 Conclusion

In the framework of K, TREE's heuristic join strategy has been shown as a challenger for RETE. We are con­ vinced that TREE can be applied to other systems with a restricted WM formalism because CEs are often weakly selective but often constrained. For instance, we believe TREE would certainly perform efficiently for SOAR as it fulfills these conditions and satisfies the assumption of relational paradigm. Though we did not test it, TREE would probably not fit for OPS5 programs as their CEs are likely more discriminant than symbol sharing.

However, TREE can still be optimized. It could be in­ teresting to explore other constraint relaxation strategies that would take into account the CEs and the represen­ tation framework. A join strategy exploiting a combi­ nation of TREE's and RETE's indexing schemes would certainly lead to better results than TREE alone. This has to be tested in the future.

Acknowledgements

We would like to thank B. Bachimont, I. Bichindaritz, M. Cavazza, and L. Don~ for gracefully providing the rule-based programs we used.