Reteアルゴリズム
Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート(根)となるノード以外はルールの左辺部(LHS)に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。
新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部(RHS)が起動される。
Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。
新たなプロダクションを定義する場合、複数の条件の論理和を使うことができる。多くのプロダクションシステムでは、このような論理和パターンを使った単一プロダクションを複数のプロダクションと等価に解釈する。この場合、複数の終端ノード群で1つのプロダクションを表す。この場合、論理和操作を省略することはできない。また、場合によっては同じWME群が複数の内部プロダクションにマッチングし、同じプロダクション・インスタンスの複製がアジェンダ上に活性化される可能性がある。この問題に対処するため、推論エンジンによってはアジェンダ上で複製の除去を行う。
WME をワーキングメモリから削除する場合、格納している全アルファメモリから削除しなければならない。さらに、そのWMEを含むWMEリストもベータメモリから削除し、そのWMEリストによって活性化されたプロダクション・インスタンスを非活性化して、アジェンダから削除しなければならない。この削除方式はいくつか存在する。削除の最適化のためにメモリのインデックスを活用することもある。
このネットワークがルールの条件(パターン)と事実(データタプル)のパターンマッチを行う。Reteネットワークは一種のクエリプロセッサのように働き、関係代数の「射影」、「選択」、「結合」などの操作をデータタプルに対して必要に応じて行う。
プロダクション(ルール)は、アナリストやソフトウェア開発者が高レベルなルール記述言語を使って作成する。それをルール群として集め、(多くの場合実行時に)変換して使用する。
事実がワーキングメモリ上に「表明」されると、エンジンは「ワーキングメモリ・エレメント」(WME)を各事実に対応させて生成する。事実はタプルであり、その中に任意個のデータが含まれている。各 WME はそのタプル全体を格納するか、WME が格納できるタプルのサイズが固定の場合、タプルを複数の WME 群で表現する。後者の場合、タプルはトリプレット(3-タプル)であることが多い。
各 WME はReteネットワークの唯一のルートノードから投入される。ルートノードは WME を子ノードに渡していき、さらにその WME がネットワーク上を転送されていく。