Reteアルゴリズムに基づくJAVAルールエンジン



Java Rule Engine Based Rete Algorithm



著者:Zhang Yuan Xia Qingguo(西北工業大学コンピューター学部、西安710072)
From:Science、Technology and Engineering、Vol。 6 No. 11 2006年6月

概要



ソフトウェアアプリケーションでルールを抽出できる場合、ソフトウェアエンティティをより柔軟にすることができ、ルールエンジンがこれを可能にします。そのアルゴリズムReteは、最も重要な主流アルゴリズムの1つに徐々に進化してきました。まず、ルールエンジンとそのJAVAAPIの原理を強調します。次に、Reteアルゴリズムについて説明します。最後に、JessとオープンソースプロジェクトのDroolsについて簡単に紹介します。

キーワード



Rule Engine Rete Algorithm Java API Doorls J2EE
中国の図書館分類番号TP311.11文書識別コードB

JAVA実装には、基本的に3つのレイヤーがあり、各レイヤーは、プレゼンテーションレイヤーフレームワーク(Struts、JSFなど)、永続レイヤーフレームワーク(JDOなど)を含む、開発者が最も重要な開発に集中するための優れたフレームワークに対応します。およびエンティティBeanなど)および構造化フレームワーク(EJBなど)。これらのフレームワークには、商用ロジックフレームワークはありません。図1に現在の状態を示します[1]。

図1Javaアプリケーションのフレームワーク



ここではルールエンジンが必要です。この記事では、ルールエンジンの原理と使用されるReteアルゴリズムに焦点を当て、2つの主流のフレームワークについて説明します。

エンタープライズレベルでのエンタープライズ開発には傾向があります。つまり、ビジネスルールは頻繁に変更され、変更の理由のほとんどは開発者以外からのものであり、開発者でさえ、多くの複雑なルールはアルゴリズムや抽象的なデータを導出するのが困難です。モデル。さらに、これらのビジネスルールは、安定した要件として使用できないことがよくあります。つまり、設計およびコーディング後に変更される可能性があります。また、ビジネスルールはシステムのコードに埋め込まれていることが多く、システムの保守と更新が非常に困難になり、開発者以外の人が管理することはさらに不可能になります。ルールエンジンはこの問題を解決します。

1つのルールエンジン

1.1ビジネスルール

ビジネスルールは、ビジネスルールアプリケーションのビジネスロジックの一部を表す一連の条件と、これらの条件下で実行される操作で構成されます。ビジネスルールは通常、ビジネスアナリストとポリシーマネージャーが開発および変更する必要がありますが、一部の複雑なビジネスルールは、オブジェクト指向の技術言語またはスクリプトを使用して技術者がカスタマイズすることもできます。

ビジネスルールの理論的基礎は、これらの条件が満たされたときに1つ以上の操作[3]をトリガーする1つ以上の条件を設定することです。

1.2ルールエンジンの構造

ルールエンジンのアーキテクチャを図2に示します。

図2ビジネスルールエンジンのアーキテクチャ

ルールエンジンの推論手順は次のとおりです。

a。初期データを作業メモリーに入力します
b。パターンマッチングを使用して、ルールとルールベースのデータを比較します
c。実行ルールに競合がある場合、つまり複数のルールが同時にアクティブ化されている場合、競合するルールは競合セットに配置されます。
d。競合を解決し、アクティブ化されたルールを順番にアジェンダに入れます
e。ルールを実行する

議題のすべてのルールを完了するまで、手順bからeを繰り返します。ルールエンジンは、ルールの推論メカニズムとルール条件のマッチングの効率の問題を解決する必要があります。エンジンが実行されると、ルール実行キュー内の優先順位に従って、ルール実行インスタンスが1つずつ実行されます。ルールの実行部分によって作業領域のデータオブジェクトが変更される可能性があるため、条件の変更により、キュー内の一部のルール実行インスタンスが失敗する可能性があります。 、キューから取り消す必要があります。また、条件を満たさなかったルールをアクティブにし、新しいルール実行インスタンスをキューに生成する場合があります。したがって、「動的な」ルール実行チェーンが形成され、ルールベースの推論メカニズムが形成されます。このようなルールの「連鎖」応答は、ワークスペース内のデータによって完全に駆動されます。

2ネットワークアルゴリズム

2.1はじめに

ルールエンジン製品のアルゴリズムのほとんどは、基本的に1979年のチャールズフォージー博士のReteアルゴリズムとその変形から派生しています。Reteアルゴリズムは現在、最も効率的なフォワードチェーン推論アルゴリズムです。中心的なアイデアは、一致を分離することです。アイテムは、コンテンツに基づいてマッチングツリーを動的に構築し、計算量を大幅に削減します。

2.2アルゴリズムの説明

Reteパターンマッチングアルゴリズムは、推論エンジンの時間的冗長性とパターンマッチングのルール構造の類似性を使用して、中間位置を保存することで推論効率を向上させるパターンマッチングアルゴリズムです。

パターンマッチングプロセスでは、ルールの前提に多くの同一のモジュールが存在する可能性があります。したがって、ルールが一致すると、多数の反復操作が実行され、時間の冗長性がもたらされます。例えば:

ルール1:(A> B)かつDまたはCの場合、E = 100
ルール2:(A> B)および(B規則3:if(!(A> B)または(B

これらの3つのルールに一致させるには、式A> Bに3つの計算が必要であり、BB、M2 = Bに2つの計算が必要です。

ルール1:(M1)およびDまたはCの場合、E = 100
ルール2:(M1)および(M2)の場合、E = 200
規則3:if(!(M1)or(M2))then E = 300

これは、AまたはBが同様に変更された場合にのみ、E1を再計算し、BまたはCが変更された場合は、E2を再計算します。このような推論は、パターンマッチングが実行されるたびに同じ式を繰り返すことを回避し、関連するパラメーターが変更されたかどうかを検出するだけで、式を更新するかどうかを決定できます。これにより、推論プロセスの時間とオーバーヘッドが大幅に節約され、推論効率。 。

32つの主流のルールエンジンの紹介

JSR94仕様は、一連のルールエンジンの基本操作を記述する一連のルールエンジンのJAVAAPIを定義します。この一連の操作の定義は、ほとんどのクライアントがマルチステップのルールエンジンサイクル(ルールの解析、オブジェクトのエンジンへの配置、ルールのヒット、エンジンからの結果オブジェクトの取得)を実行する必要があるという前提に基づいています。

仕様で定義されているクラスとインターフェースは、javax.rulesパッケージとjavax.rules.adminパッケージにあります。ルールエンジンランタイムクライアントのクラスとインターフェイスはjavax.rulesに含まれており、登録されたルール実行セットからルールセッションを取得し、ルールセッションと対話する方法を提供します。管理APIは、URI、入力ストリーム、XMLドキュメント、バイナリ抽象構文木、リーダーなどの外部リソースからルール実行セットをロードするためのメソッドを提供します。管理APIには、ルール実行セットを登録および登録解除するためのメソッドも含まれています。ランタイムクライアントAPIを介してアクセスできるのは、登録されたルール実行セットのみです。

例:Sandia NationalLabのJessルールエンジンオープンソースソフトウェアのDroolsルールエンジン[5]。

3.1イエス

Jessでは、ルールの表現はCLIPSの文法構造に従い、事前ルールと事後ルールを定義することにより、豊富なパターンマッチング言語をサポートします。さらに、Jessはプロセス指向プログラミングアプローチをサポートしています。これは、if ... then ... elseおよびwhile ... do ...ステートメントの使用など、投稿のルールのフローを制御するためのいくつかのステートメントを提供します。そのため、プロセス指向プログラミングを非常に効果的に活用できます。要するに、ジェスのこれらの機能は、システムに強力な知識表現を提供します。

例えば:

(defruleライブラリ-ルール-1
(本(名前?X)(ステータスが遅い)(借り手?Y))
(借り手(名前?Y)(住所?Z))
=>
(送信遅延通知?X?Y?Z))

この一連のルールは、次のように中国語に翻訳できます。このルールは次のようになります。
ライブラリルール#1:
Yという名前の人が借りているXという名前の期限切れの本があり、Zが借り手の住所を知っている場合は、Zでの通知に関するXの本をYに送信します[6]。

3.2よだれ

Droolsは、CharlesForgyのReteアルゴリズムに基づいてJava言語用に設計されたルールエンジンでもあります。 Reteアルゴリズムをオブジェクト指向インターフェースに適用すると、ビジネスオブジェクトに基づくビジネスルールの表現がより自然になります。 DroolsはJavaで記述されていますが、Javaと.Netの両方で実行できます。

Droolsは宣言型プログラミングを提供し、ドメイン固有言語(DSL)を使用して、問題のあるドメインのXmlのパターンを定義します。これは、ユーザーの問題のあるドメインを記述するために使用できます。 DSLに含まれるXml要素(要素)と属性は、問題のあるドメインのさまざまな要素を表します。たとえば、ルールセットは特定のパターンに準拠するXmlファイルです(詳細については、XmlSpyのリンクを参照してください)。ルール「言語」は実際にはポータル式パッケージの使用であり、ルールエンジンの追加要件を満たすように拡張できます。
Droolsルールセットには.rls拡張子があり、これには通常、ラベル、ルールが含まれ、各ルールはテスト条件とアクションを定義します。

例えば:



com.zhang.rules

x.getStatus()。equals( 'y:borrower')
vo.setMassage(z、 '後期の本')

4結論

Reteアルゴリズムに基づくJavaRule Engine API(JSR-94)を使用すると、クライアントプログラムは、さまざまなベンダーのルールエンジン製品と統一された方法で対話でき、ルールエンジンベンダーにある程度の標準化仕様を提供します。ただし、ルールエンジンとは何かを定義することはほとんどなく、もちろん、ルールの構築方法と操作方法、ルール呼び出しのユーティリティ、およびルールのJava言語へのバインドについては説明していません。また、JSR-94はJ2EEをサポートするのに十分ではありません[1]。 JessとDroolsにはそれぞれのメリットがありますが、ルール言語の標準化とJSR-94のさらなる強化についてはまだ検討されていません。

謝辞:Li Guangsheng、Zhang Heqing、およびOuJianshenの支援に感謝します。

参照

1 BrowneP。エンタープライズJavaアプリケーションでのDroolsの使用。 http://www.onjava.com/pub/a/onjava/2005/08/24/drools。 html。 2005年8月
2 Rupp N A. Droolsプロジェクトの紹介、http://www.theserverside.com/articles/content/Drools/article.html.05/2004
3彼はレンジエ、リャンビン。コードをルールエンジンに置き換えます。 http://blog.csdn.net/csdnloading/archive/2005/02/02/277276.aspx。 2004年
4 Li Guole JavaルールエンジンとそのAPI。 http:/ / www- 128.ibm。 com / developerworks / cn / java / j-java-rules /#IDACCWOB。 2005年7月
5 JSR94:Java Rule Engine APIhttp://jcp.org/en/jsr/detail?id = 94.2005
6アーネストJ.フリードマンヒル。ジェス、Javaエキスパートシステムシェルhttp://herzberg.ca.sandia.gov/jess。 1997年