Reteアルゴリズム(2) - El mundo que soñé

(前回の続き)

さて、Reteアルゴリズムは最初にルールをコンパイルしてネットワークの形に表現します。

(なお、ここではDroolsで用いられているReteOOというオリジナルReteの派生形を説明に用いますが、本質的な部分での違いはありません)。

たとえば本家サイトの方で例示しているルール(DroolsTest3.drl)をReteのネットワークにコンパイルすると、

Reteネットワーク0

となり、入口(○)が一つ、出口(●)がルール数だけある有向グラフができます。

(ちなみにDroolsのEclipseプラグインでルールファイル(.drlファイル)を表示するとReteTreeタグで上のようなReteネットワークを見ることができます)

Reteアルゴリズムは、ファクト(データ)を追加/変更/削除するたびにReteネットワークの入口から投入/チェックしていくのですが、まずはこのグラフについて最初に説明しましょう。ただ上記のルールそのままですと説明が複雑になるかと思いますので、最初にルール一つのケースから説明をします。

さて、以下のルールがあったとします。

rule “基本保険金額1”
when
契約(　$id_no : 証券番号,
基本保険金額 > 30000000
)
then
System.out.println(“証券番号 ” + $id_no + ” の基本保険金額が3000万円を超えています。”);
end

このルールは以下の形のReteネットワークとなり、

Reteネットワーク1
それぞれのノードは

Reteノード
ファクトを追加する際の入り口となるノード
EntryPointノード
CEP(Drools Fusion)で複数のエントリーポイントを持つことができるが、今回はデフォルトのエントリーポイントのみを使用。
ObjectTypeノード
ファクトのオブジェクトタイプを識別して、フィルタとして働くノード。上記のルールでは「契約」タイプのオブジェクトを通す。
αノード
条件部での制約をチェックしてフィルタとして働くノード。条件部のひとつのオブジェクトに対する制約条件ひとつがひとつのノードになる。上記の例では、「基本保険金額>30000000」がこれにあたる。
LeftInputAdapterノード
βノード(後述)へのエントリーポイントとなるノード。ここまで関門をくぐり抜けてきたファクトからファクトの組(tuple)を生成する。
Terminalノード
if-thenルールのthen部分にあたるノード。ここまで到達したファクト(の組)がthen部分と合わさって実行候補のリストに登録される(前回の記事の１．で言う「マッチしたルールとデータのカップルを列挙」したリストに登録されるということ)

と呼ばれます。

以上がReteのネットワークの説明ですが、単にルールをネットワーク化しただけではルールの実行サイクルを効率化することには寄与しません。そこで着目するのが、前回書いたように

「ワーキングメモリの中身が変わらなければ、マッチするファクトとルールの組も変わらない。」
「1回のルール実行では、ワーキングメモリの中身はほとんど変わらない。」

という点です。ワーキングメモリにファクトが追加されたり、ワーキングメモリのファクトを変更/削除したりした都度、今作成したReteネットワークの入り口から投入し、ルールの条件にマッチするかしないかを判定します。ここで重要なことは、ファクトとルール条件との判定はルールの実行サイクルの判定のフェーズで行われるのではなく、すでにファクトをワーキングメモリに挿入したり、変更/削除したりするときに同時に判定されるということなのです。

では、上で作成したReteネットワークにファクトを挿入してみましょう。以下の3つのファクトがワーキングメモリにinsertされるとします。

f-1．契約(証券番号=’10001′, 基本保険金額=40000000)
f-2．契約(証券番号=’10005′, 基本保険金額=20000000)
f-3．顧客(顧客番号=’10005′)

この例では、ファクトf-1のみが、ルール基本保険金額1にマッチしますから、基本保険金額1(f-1)といったルールとファクトの組が、ルール実行候補のリストに追加されるはずです。

ではまず、ファクトf-1がinsertされたとしましょう。f-1は、Reteノード、EntryPointノードを通過し、Objectノードに入ります。このObjectノードはObjectの種類が契約であるというフィルタとなっていますがf-1は条件を満たすので、そのまま通過します。次のαノードは、基本保険金額 > 30000000という判定条件ですが、f-1はこれもまた満たすので通過します。次のLeftInputAdapterノードは、次に向かう準備としてf-1をファクトの組(tuple)に変換して、最後のTerminalノードに渡します。TerminalノードではLeftInputAdapterノードでできたファクトの組とルールとを組にして(基本保険金額1(f-1))、ルール実行候補リストに追加します。

次にf-2をinsertしてみましょう。f-2は、f-1と同様に、Reteノード、EntryPointノード、Objectノードは通過しますが、αノードは基本保険金額 > 30000000という判定条件を満たさないのでこれ以上は進めません。

最後にf-3をinsertしてみると、Reteノード、EntryPointノードは通過しますが、Objectノードは条件を満たさないのでこれ以上は進みません。

以上の状況を図にすると、
Reteネットワーク1-1
となります。

(つづく)