ルールエンジンのアルゴリズム

久しぶりの更新になってしまいましたが、ここのところルールベースエンジン関連の話題が次々と出てきて・・・Droolsはいつのまにか5.3のFinalが出ていて、5.4のβまで出ているし、CorticonはProgressに買収されるし・・・ちなみに最近またDroolsの新しい本が出たようです。

それはそうと、おかげさまで最近私もルールエンジンの仕事がだいぶ増えてきてうれしい限り。ただ、まだまだ人口に膾炙するといったところではないようで、ルールエンジンの動き等に関連していろいろ質問されることが多々あります。
たとえば
・ルールエンジンのプログラムって、if-Thenのルールが並んでいるけれども、上から順にやっていくの？？
・(上記に関連して)　通常のプログラムの(単体)テストだと全部のパスを通るようにテストするけれども、　ルールの場合のテストでは、全部のパスを通す…ってどのように考えればよい？
・ルールエンジンのメモリ使用量は何に依存してきまるのでしょうか？　ルール数？
・同じようにルールエンジンの処理速度は何できまる？
などなど。

私もこのような質問をされるようになって、あらためてネットなどを調べてもみるのですが、ルールエンジンの動きとかアルゴリズムとか結構情報が少なくて、ルールエンジンの代表的なアルゴリズムであるはずのReteアルゴリズムの日本語の解説などは、ちょっと探してみたところネット上にはほとんど皆無状態でした。
というわけで、これからぼちぼちルールエンジンの動きやアルゴリズムなど気が付いたときに書いていきたいと思います。
さて、最初というわけでルールエンジンの動きから。以前、本宅の記事(プロダクションシステム(ルールベースシステム)とは)にルールエンジンの動きを書きましたが、もともとはこのルールエンジン、人工知能や認知心理学の研究をルーツとするもので
人間が長期記憶にあたる「ルール」を使って、認識した外界の状況(短期記憶に保持される)に合わせて判断を行うという行動がモデルとなっています。
これをルールエンジンの動きとして翻訳してみると、
１．データの集合に対して、たくさんあるルールの条件部分をひとつひとつデータとマッチングさせて、マッチしたルールとデータのカップルを列挙しておく。
２．カップルの中からひとつを選んで実行する。
３．実行によってデータが書き換えられる場合もあるので、再度１．のカップリングを行う。
４．１～３を繰り返してマッチするルールがなくなったところで実行が終了する。
となります。
この動きをみるとわかるように、ルールエンジンでは、すべてのデータに対して、すべてのルールの条件部のマッチングを試し、そののちにルールを実行します。したがってルールの実行順序は必ずしも上から順などといったことではなくて(実はそれなりの実行順の規則はあるのですが)、実行順に過度に依存するようなルールの書き方はむしろお作法に反するものという見方が強いです。
特に最近ルールエンジンがよく使われている入力データのチェックなどは、(チェックそのものだけでいえば)別に順番などはどうでもよく、条件に合うか合わないかで正しくエラーが出ればそれでよいのであって、上記のようなルールエンジンの動きはこの「チェック」という作業に対して非常になじむもののように思います。