図面 (/)

技術 活動状態のコンピュータシステムにおいてシステムルールを実現するための方法及び装置

出願人 エイ・ティ・アンド・ティ・アイピーエム・コーポレーション
発明者 ホサグラハビベスバラヤジャガディッシュアルバートオスカーメンデルゾンインダーパルシングミュニック
出願日 1996年5月20日 (24年6ヶ月経過) 出願番号 1996-162290
公開日 1997年5月2日 (23年6ヶ月経過) 公開番号 1997-114666
状態 未査定
技術分野 特殊なプログラム実行装置 知識ベースシステム
主要キーワード 位相順序 代表モデル 状態点検 起動メカニズム 度右回転 システムルール 実行セット 不活動状態
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1997年5月2日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (5)

課題

コンピュータシステムシステムルールを実現する方法及び装置

解決手段

ワークステーション800が中央処理装置(CPU)801とシステムルールのセットを内蔵する記憶装置802とからなる。通信ポ−ト805を介して記憶装置802に入力された超ルールがCPU801により導出され、超ルールの完全セットとして記憶装置802に格納される。イベントが通信ポ−ト805を介して入力されると、記憶装置802に格納されているシステムルールセットが、CPU801によって点検され、超ルールが装置の条件記述満足されると発動可能(実行準備完了)状態となる。CPU801が、超ルールの適用により、発動すべき発動可能ルールの部分集合を定める。CPU801がシステムルールの部分集合の発動順序を定める。それから、CPU801が、順序づけされた出力ルールのセットを出力し、発動(実行)する。

概要

背景

ソフトウエアの開発及び維持に要するコストを減少させるために、又ソフトウエアの柔軟性を増大させるために、データの管理及び処理においては、可能な場合にはいつも、「ルール準拠した」実現化の手法を用いてきている。データベースアクセスする種々のアプリケーションの、包含される全ての意味をルールの形に取り込もうと試みる際に、ルールの対立及び「あいまいさ」(曖昧さ)が、意図的ではないにしてもしばしば発生する。

活動状態コンピュータ準拠システムは、特定の事象イベント)又は状態が発生した場合に実行されるシステムルール(又は簡単に、「ルール」)を有する。これらのルールは各々、そのルールで指定された条件が満足される場合にそのルールによって要求される行動が実行されるような、それらの指定された条件についての、予め定められたそれぞれの「条件記述」を有する。

或る特定のイベントの発生時にそのイベントが1個以上のルールの条件記述を満足することからそれら多数のルールが同時に発動される資格を有する場合が、しばしばある。しかし、順次処理コンピュータ上で実現された活動状態のコンピュータ準拠システムについて、それら発動された多数のルールによって要求される行動のうちで1度に実行できるのは、それら多数のルールのうちの1個のルールによって要求される行動だけである。

活動状態のデータベース及びルール準拠システムの設計者は、対立する多数のルールが起動される現象と闘ってきた。又、多数のルール対立を扱うためのルールの実行(ルールの行動部分の実行)を制御するのに広範囲にわたる種々の従来技術の手法が提案され実現されてきた。

従来技術による方法の1つは、(発動の)資格のある(すなわちその条件記述を満足する)全てのルールを単に並行して発動することである。このような手法は、理解しやすいという利点がある一方、同時に実行される各ルール対について、ルールの行動部分を交換する必要があり、これによって、ルールの行動部分にプログラムすることのできる内容が制約される。

従来技術による別の方法は、ルール発動の順序を定めるのに、最新性、特異性、又は確実性因子のような判定基準を用いることである。この従来技術の手法は、「システムルール」へハードコ−ド化するもので、確かな事実に基づくというよりも真にヒューリスティック発見的)であるという点で、制限される。

この従来技術の手法についての、有り得る個々の判定基準の総合的な分類が、文献(Timos K. Sellis and Yannis E. Ionnidis, Conflict resolution of rules assigning values to virtual attributes, Proceedings ofACMSIGMOD1989 International Conference on Management of Data, pages 205-214, Portland, OR, 1989) に述べられている。

ルール順序の選択は、難しいタスクで、システムが複雑になるにつれてその複雑性を増す。異なる状況下では判定基準を種々に変えるのが適切である。

従来技術の第3の例においては、システムルール間の明示された優先順位が用いられる。

優先順位を明示して宣言し又は記録するこれらの方法のうちで最も簡単な手法では、各ルールへ単一且つ絶対的な優先順位を割り当てる必要がある。これらの手法についての説明が、文献(Michael Stonebraker, E. N. Hanson and S. Potamianos, The postgres rule manager,IEEE Transactions of Software Engineering, 14(7):897-907, (July 1988); and E. N. Hanson, An initial report on the design of Ariel, Sigmod Record, 18(3):12-29, (September 1989)) に述べられている。

より高度なシステムにおいては、相対的な優先順位の指定が可能である。例えば、スターバースト手法では、明示指定された相対的優先順位の利用が可能であるが、優先順位を明示指定しないで「発見的」な判定基準を適用することによって得られるデフォルト優先順位を用いる。

スターバースト手法については、文献(Jennifer Widom, Roberta Jo Cochrane and Bruce Lindsay, Implementing set-oriented production rules as an extension to starburst, in Proceedings of Seventeenth International Conference on Very Large Database, Guy M. Lohman, Amilcar Sernadas, and RafaelCamps, editors, Barcelona, Spain, (September 3-6, 1991), pages 275-284) に述べられている。

又別の文献(Rakesh Agrawal, Roberta Cochrane, and Bruce Lindsay, On maintaining priorities in a production rule system, In Lohman et al. supra, page 479-487)も参照されたい。

順序付けされたルールのセットのルールが、ある時点で発動について適格であったとしても、実行はそう簡単ではない。この場合に大抵のルールシステムによって採用されている従来技術の手法の1つは、単にそのルールのセットのうちの最高優先順位を有する1個のルールを発動してから、その時点で資格を有するようになった全てのルールについて再検討する手法である。

別の方法では、点検評価及び発動のためにルールの待ち行列を形成し、優先順位については発動順序を定めるためにだけ用いる。そして、構文法のような正則表現での「制御表現式」の明示指定を許し又ただ1個のルール又は全てのルールを考慮して異なる評価メカニズムの使用を許すような従来技術の手法でさえも、或るルールの不能化を或る文脈で明示的に定めることをせず、デフォルト優先順位は「発見的」に導出され、明示指定されることがない。

データログ」ルールの文脈において、同様な従来技術の手法がイミエリンスキー及びナクビー(Tomasz Imielinski and Shamin Naqvi)によって採用されている(文献(Explicit control of logic programs through rule algebra, Proceedings of the Seventeenth Symposium on Principles of Database Systems(PODS), pages 103-115, Austin, TX, 1988) 参照)。

他のルールと並行してどのルールをどのルールの後に点検評価するかの指定を可能にするような、ルールのアルファベットについての正則表現が、データログプログラムに付加される。これは、プログラム及び表現式を、ローカル層状化したプログラムへ同じ意味を持たせてどのように翻訳変換するかを示す。

並行生成システムにおける従来技術の手法は、適格ルールを1度に1個づつ処理するよりも適格ルールのセット全体を並行して処理することを考える。これによって、特定のルールが起動停止されるべき条件の明示指定が強制的に行われる。例えば、「並行言語」手法においては、ルール名称を「条件記述」として、又「条件記述」名称を記号として用いて、より高い次元論理で「縮小簡約化」超ルール(メタルール)を指定し、これにより、発動に本来適格なルールを削除することが許される。

この「並行言語」手法は文献(S.J. Stolfo, H.M. Dewan and Ouri Wolfson,The parallel parallel rule language, in ICPP, pages II-36-II-45,(1991))に開示されている。同様な手法が「CREL」システムによって採用されており、文献(D.P. Miranker, C.M. Kuo and J.C. Browne, On the performance of the crel system, Journal of Parallel and Distributed Computing, 13:(4):424-441, (December 1991))に説明がある。

概要

コンピュータシステムのシステムルールを実現する方法及び装置

ワークステーション800が中央処理装置(CPU)801とシステムルールのセットを内蔵する記憶装置802とからなる。通信ポ−ト805を介して記憶装置802に入力された超ルールがCPU801により導出され、超ルールの完全セットとして記憶装置802に格納される。イベントが通信ポ−ト805を介して入力されると、記憶装置802に格納されているシステムルールセットが、CPU801によって点検され、超ルールが装置の条件記述を満足されると発動可能(実行準備完了)状態となる。CPU801が、超ルールの適用により、発動すべき発動可能ルールの部分集合を定める。CPU801がシステムルールの部分集合の発動順序を定める。それから、CPU801が、順序づけされた出力ルールのセットを出力し、発動(実行)する。

目的

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

イベント応動して活動状態コンピュータシステムにおいてシステムルールを実現するための方法であって、システムルールのセットから1個以上のシステムルールを入力するステップと、メタルールのセットを入力するステップと、前記メタルールのセットによって前記システムルールのセットを処理するステップと、前記システムルールの前記処理から導出された順序付けされた出力システムルールのセットを出力するステップと、からなることを特徴とする、活動状態のコンピュータシステムにおいてシステムルールを実現するための方法。

請求項2

前記方法において、前記メタルールのうちの少なくとも1個が、絶対的要求メタルールであるようにしたことを特徴とする請求項1の方法。

請求項3

前記方法において、前記メタルールのうちの少なくとも1個が、不能化メタルールであるようにしたことを特徴とする請求項1の方法。

請求項4

前記方法において、前記不能化メタルールが単方向性であるようにしたことを特徴とする請求項3の方法。

請求項5

前記方法において、前記メタルールのうちの少なくとも1個が、優先選択メタルールであるようにしたことを特徴とする請求項1の方法。

請求項6

前記方法において、前記メタルールのうちの少なくとも1個が、スケジューリングメタルールであるようにしたことを特徴とする請求項1の方法。

請求項7

前記方法において、前記絶対的要求メタルールが、前記1個以上のシステムルールのうちの第1のシステムルールが実行されるときに前記1個以上のシステムルールのうちの第2のシステムルールの実行を要求するステップからなる、ようにしたことを特徴とする請求項2の方法。

請求項8

前記方法において、前記不能化メタルールが、前記1個以上のシステムルールのうちの第1のシステムルールが実行されるときに前記1個以上のシステムルールのうちの第2のシステムルールの実行を不能化するステップからなる、ようにしたことを特徴とする請求項3の方法。

請求項9

前記方法において、前記優先選択メタルールが、前記1個以上のシステムルールのうちの第1のシステムルールと第2のシステムルールとの両方が実行可能な場合に該第2のシステムルールの実行を優先選択するステップからなる、ようにしたことを特徴とする請求項5の方法。

請求項10

前記方法において、前記スケジューリングメタルールが、実行を選択された第1及び第2のシステムルールを順序付けするステップからなる、ようにしたことを特徴とする請求項6の方法。

請求項11

イベントに応動して活動状態のコンピュータシステムにおいてシステムルールを実現するための方法であって、システムルールのセットから1個以上のシステムルールを入力するステップと、前記システムルールのセットを縮小簡約化するステップと、メタルール言語を用いるメタルールからなるメタルールのセットを入力するステップと、前記入力されたメタルールのセットから完全なメタルールのセットを推論するステップと、前記完全なメタルールのセットによって前記システムルールのセットを処理するステップと、前記システムルールの前記処理から導出された順序付けされた出力システムルールのセットを出力するステップと、からなることを特徴とする、活動状態のコンピュータシステムにおいてシステムルールを実現するための方法。

請求項12

前記方法が更に、起動された前記システムルールの各々について前記システムルールの特有出力順序を前記完全なメタルールのセットが特定するかどうか、を推論するステップ、からなるようにしたことを特徴とする請求項11の方法。

請求項13

前記方法において、前記入力されたメタルールのセットから完全なメタルールのセットを推論する前記ステップが、不作動システムルールの認識からなる、ようにしたことを特徴とする請求項11の方法。

請求項14

前記方法において、前記完全なメタルールのセットが、絶対的要求メタルールと、不能化メタルールと、プレファレンスルールと、スケジューリングメタルールとからなる、ようにしたことを特徴とする請求項11の方法。

請求項15

イベントに応動する活動状態のコンピュータシステムであって、システムルールのセットから1個以上のシステムルールを入力する手段と、メタルールのセットを入力する手段と、前記メタルールのセットによって前記システムルールのセットを処理する手段と、前記システムルールの前記処理から導出された順序付けされた出力システムルールのセットを出力する手段と、からなることを特徴とする、活動状態のコンピュータシステム。

技術分野

0001

本発明は、概しては活動状態ルール規則)に基づいた(ルール準拠コンピュータシステムに関し、詳しくは活動状態のルール準拠コンピュータシステムにおけるルール対立の管理に関する。

背景技術

0002

ソフトウエアの開発及び維持に要するコストを減少させるために、又ソフトウエアの柔軟性を増大させるために、データの管理及び処理においては、可能な場合にはいつも、「ルールに準拠した」実現化の手法を用いてきている。データベースアクセスする種々のアプリケーションの、包含される全ての意味をルールの形に取り込もうと試みる際に、ルールの対立及び「あいまいさ」(曖昧さ)が、意図的ではないにしてもしばしば発生する。

0003

活動状態のコンピュータ準拠システムは、特定の事象イベント)又は状態が発生した場合に実行されるシステムルール(又は簡単に、「ルール」)を有する。これらのルールは各々、そのルールで指定された条件が満足される場合にそのルールによって要求される行動が実行されるような、それらの指定された条件についての、予め定められたそれぞれの「条件記述」を有する。

0004

或る特定のイベントの発生時にそのイベントが1個以上のルールの条件記述を満足することからそれら多数のルールが同時に発動される資格を有する場合が、しばしばある。しかし、順次処理コンピュータ上で実現された活動状態のコンピュータ準拠システムについて、それら発動された多数のルールによって要求される行動のうちで1度に実行できるのは、それら多数のルールのうちの1個のルールによって要求される行動だけである。

0005

活動状態のデータベース及びルール準拠システムの設計者は、対立する多数のルールが起動される現象と闘ってきた。又、多数のルール対立を扱うためのルールの実行(ルールの行動部分の実行)を制御するのに広範囲にわたる種々の従来技術の手法が提案され実現されてきた。

0006

従来技術による方法の1つは、(発動の)資格のある(すなわちその条件記述を満足する)全てのルールを単に並行して発動することである。このような手法は、理解しやすいという利点がある一方、同時に実行される各ルール対について、ルールの行動部分を交換する必要があり、これによって、ルールの行動部分にプログラムすることのできる内容が制約される。

0007

従来技術による別の方法は、ルール発動の順序を定めるのに、最新性、特異性、又は確実性因子のような判定基準を用いることである。この従来技術の手法は、「システムルール」へハードコ−ド化するもので、確かな事実に基づくというよりも真にヒューリスティック発見的)であるという点で、制限される。

0008

この従来技術の手法についての、有り得る個々の判定基準の総合的な分類が、文献(Timos K. Sellis and Yannis E. Ionnidis, Conflict resolution of rules assigning values to virtual attributes, Proceedings ofACMSIGMOD1989 International Conference on Management of Data, pages 205-214, Portland, OR, 1989) に述べられている。

0009

ルール順序の選択は、難しいタスクで、システムが複雑になるにつれてその複雑性を増す。異なる状況下では判定基準を種々に変えるのが適切である。

0010

従来技術の第3の例においては、システムルール間の明示された優先順位が用いられる。

0011

優先順位を明示して宣言し又は記録するこれらの方法のうちで最も簡単な手法では、各ルールへ単一且つ絶対的な優先順位を割り当てる必要がある。これらの手法についての説明が、文献(Michael Stonebraker, E. N. Hanson and S. Potamianos, The postgres rule manager,IEEE Transactions of Software Engineering, 14(7):897-907, (July 1988); and E. N. Hanson, An initial report on the design of Ariel, Sigmod Record, 18(3):12-29, (September 1989)) に述べられている。

0012

より高度なシステムにおいては、相対的な優先順位の指定が可能である。例えば、スターバースト手法では、明示指定された相対的優先順位の利用が可能であるが、優先順位を明示指定しないで「発見的」な判定基準を適用することによって得られるデフォルト優先順位を用いる。

0013

スターバースト手法については、文献(Jennifer Widom, Roberta Jo Cochrane and Bruce Lindsay, Implementing set-oriented production rules as an extension to starburst, in Proceedings of Seventeenth International Conference on Very Large Database, Guy M. Lohman, Amilcar Sernadas, and RafaelCamps, editors, Barcelona, Spain, (September 3-6, 1991), pages 275-284) に述べられている。

0014

又別の文献(Rakesh Agrawal, Roberta Cochrane, and Bruce Lindsay, On maintaining priorities in a production rule system, In Lohman et al. supra, page 479-487)も参照されたい。

0015

順序付けされたルールのセットのルールが、ある時点で発動について適格であったとしても、実行はそう簡単ではない。この場合に大抵のルールシステムによって採用されている従来技術の手法の1つは、単にそのルールのセットのうちの最高優先順位を有する1個のルールを発動してから、その時点で資格を有するようになった全てのルールについて再検討する手法である。

0016

別の方法では、点検評価及び発動のためにルールの待ち行列を形成し、優先順位については発動順序を定めるためにだけ用いる。そして、構文法のような正則表現での「制御表現式」の明示指定を許し又ただ1個のルール又は全てのルールを考慮して異なる評価メカニズムの使用を許すような従来技術の手法でさえも、或るルールの不能化を或る文脈で明示的に定めることをせず、デフォルト優先順位は「発見的」に導出され、明示指定されることがない。

0017

データログ」ルールの文脈において、同様な従来技術の手法がイミエリンスキー及びナクビー(Tomasz Imielinski and Shamin Naqvi)によって採用されている(文献(Explicit control of logic programs through rule algebra, Proceedings of the Seventeenth Symposium on Principles of Database Systems(PODS), pages 103-115, Austin, TX, 1988) 参照)。

0018

他のルールと並行してどのルールをどのルールの後に点検評価するかの指定を可能にするような、ルールのアルファベットについての正則表現が、データログプログラムに付加される。これは、プログラム及び表現式を、ローカル層状化したプログラムへ同じ意味を持たせてどのように翻訳変換するかを示す。

0019

並行生成システムにおける従来技術の手法は、適格ルールを1度に1個づつ処理するよりも適格ルールのセット全体を並行して処理することを考える。これによって、特定のルールが起動停止されるべき条件の明示指定が強制的に行われる。例えば、「並行言語」手法においては、ルール名称を「条件記述」として、又「条件記述」名称を記号として用いて、より高い次元論理で「縮小簡約化」超ルール(メタルール)を指定し、これにより、発動に本来適格なルールを削除することが許される。

0020

この「並行言語」手法は文献(S.J. Stolfo, H.M. Dewan and Ouri Wolfson,The parallel parallel rule language, in ICPP, pages II-36-II-45,(1991))に開示されている。同様な手法が「CREL」システムによって採用されており、文献(D.P. Miranker, C.M. Kuo and J.C. Browne, On the performance of the crel system, Journal of Parallel and Distributed Computing, 13:(4):424-441, (December 1991))に説明がある。

発明が解決しようとする課題

0021

多数のルールが発動される場合の従来技術による別の手法は、全てのシステムルールを、複合行動部分を有する単一の大型トリガー起動メカニズム)の形に合体させる方法である。このような手法はいくつもの欠点を有する。

0022

第1に、合体の結果として得られる大型トリガーの行動部分は、制御の流れを管理するための状態点検行動を伴うことになる。単なる「構造化質問言語」(SQL)ではなく汎用プログラミング言語が要求され、アプリケーションが複雑化し、ルール準拠システムの利点が失われる。又、流れを正しく指定することも困難になる。

0023

第2に、設計は、もはやモジュラー設計とはならず、ルールについての本来のトリガーと異なりユーザの考えているアイデアの直接表現ではなくなる。単一の大型ルールの形成後に追加ルールを包含させることは一般に、単に新たなルールを表現する問題ではなく、複雑な再プログラミングタスクとなる。最後に、結果として得られるプログラムが手順的に指定される限りにおいて、最適化の機会も同様に失われる。

課題を解決するための手段

0024

本発明によって開示される方法は、イベントに応動して活動状態のコンピュータシステムにおいてシステムルールを実現するための方法で、この実現化は、システムルールのセットから1個以上のシステムルールを入力するステップと、メタルール言語を用いて実現されるメタルールのセットを入力するステップとによって行われる。システムルールは、メタルールに基づいて処理され、これにより、順序付けされた出力システムルールのセットが生成される。

0025

本発明のメタルールは、「絶対的(ポジティブ)要求」メタルール、「不能化」メタルール、「優先選択」(プレファレンス)メタルール、又は「スケジューリング」メタルールとである。

0026

本発明においては更に、システムルールのセットを縮小簡約化するステップと、入力されたメタルールのセットから完全なメタルールのセットを推論するステップとが開示される。

発明を実施するための最良の形態

0027

図1に本発明の方法の概念を示す。活動状態のルール準拠システム(又は簡単に、ルールシステム)のシステムルールのセット10が、論理的な「メタルール」(メタルール)のセット20によって定められる要に基づいて処理され、順序付けされた出力ルールのセット30が得られる。

0028

本発明の方法は、発動された多数のシステム間にあるあいまいさを解決してあいまいでないシステムルールからなる順序付けされたシステムルールのセットを得るために、システムルール間の種々の種類の関係を表現する「論理的なメタルール」(以下簡単に、メタルール)を導出し実現する。メタルールは、システムルールが決して実行されることがないかどうか、2個のシステムルールが共に実行されることがあり得るかどうか、そしてルールシステムが、発動可能となる全てのシステムルールについて、特有な実行を設定しているかどうかを定める。

0029

活動状態のルールシステムS=〈V,M〉が、ルールのセットVとメタルールのセットMとから構成される(Vについては下で述べる)。

0030

本発明の一実施例において、「活動状態のルール」(又は簡単に、「ルール」とも表す)は、「(イベント)−(条件)−(行動)」ルールである。すなわち、各ルールは、データベース内の特定の関係位置への新しいデータの挿入というイベントもしくは1個又は複数のルールを起動させるのに十分なその他のイベント(例えば、借金の申し込みのような、システムそのものの外部で発生するイベント)のような、予め定められたイベントの発生時に起動される。

0031

単一のコマンドイベントで起動が可能なルールのセットを「V」と称する。ルールの起動後にその条件が点検される。もしルールの条件が真であると判断される場合、そのルールは「発動可能である」とされる。発動可能なシステムルールのセット10を「I」、又は「入力ルールのセット」と称する。この入力ルールのセットが、下で述べるメタルール分析プロセスに入力される。

0032

発動可能なルールは、ルールの実行を制御するように指定されたメタルール次第で実行されたりされなかったりする。入力ルールのセットのうち実際に実行される部分集合サブセット)を「O」又は「出力ルールのセット」、30と称する。この出力ルールのセットはメタルール分析プロセスから出力される。

0033

出力ルールのセット「O」、30は、入力ルールのセット[I]、10の部分集合であり、入力ルールのセット[I]、10は、ルールのセット「V」の部分集合である。これを式で表すと、O⊆I⊆Vとなる。出力ルールのセットO内の全てのルールについての順序付けが定められ、これらのルール全てが指定された順に実行される。

0034

本発明の一実施例においては、システムルールの相互関係のあいまいさの除去とシステムルールの相互関係の制御とを行う「超ルール」(メタルール)を表す言語が、ルール指定に際して利用可能である。

0035

本発明の方法は、制御言語におけるステートメントを用いて、ルールのセットV内のルールの相互関係を管理する。本実施例において、対象システム内の各ルールについて2個の命題記号を有する命題論理の或る部分集合が、メタルール制御言語(又は簡単に、「メタルール言語」)として用いられる。ルールRj について、命題Ij は、「ルールRj が発動可能化されている」ことを意味し、命題Oj は、「ルールRj が実際に発動される」ことを意味する。

0036

制御ルールは、「もし或るルールが発動可能化され/又は発動可能化されず、或るルールが発動され/又は発動されない場合、或る他のルールが発動されなければならない/又は発動されてはならない」という形式のステートメントである。

0037

本実施例のメタルール言語によって、ユーザ及びアプリケーションが望み又は要求する種類のルール相互関係の大部分を実現させることのできる表現力が与えられる。本実施例のメタルールのセットは、関心対象のルール相互関係の全てを表現する。

0038

メタルールのセット「M」20は、ルールのセット「V」内のルールの相互関係及びルールの実行を制御するメタルールのセットである。これらのメタルールセットは、(1)入力ルールのセット「I」、10から出力ルールのセット「O」、30を選択するため、そして(2)結果として得られる実行ルールセットを順序付けするために用いられる。ルールのセット「I」からルールのセットOを差し引いた残りのルール、すなわち「I−O」のルールセットのルールは、メタルールによって課される制約の結果、実行されない。

0039

本発明の本実施例によるメタルールは、絶対的要求、不能化、優先選択、及びスケジューリングの4つの種類からなる。ここに、ルールa,b,c,d,..とルールのセットVとの関係は、a,b,c,d,...∈Vである。

0040

「絶対的要求」メタルールは、記号的に「ルールaがルールbを含む」を意味する式、a⊃bとして表され、「もしルールaが実行される場合にはルールbも同様に実行されなければならない」ことを表すものとして定義される。いい替えれば、もし或るシステムルールの実行が選択された場合には、別の或るシステムルールもその実行が選択されなければならない。

0041

「不能化」メタルールは、記号的に「abの上に横線上線)を引いた」形で表される(これを本文中では便宜上[ab+上線]と表す。以下同様)。そして、「ルールa及びルールbが相互に相手を不能化し、a及びbのうちの一方のルールだけが実行される」ことを表すものとして定義される。不能化メタルールによって、或るシステムルールの実行が選択された場合にそれらのシステムルールが他のシステムルールの実行を妨げることが許される。

0042

記号[a+上線]で表されるメタルールは、このメタルール[ab+上線]の特別単一体の場合を示し、「ルールaが決して実行されることがない」ことを意味する。これは又、[aa+上線]を簡略化したものと見ることもできる。

0043

本発明においては又、単方向性のメタルールも存在する。これは、もしルールaが実行される場合には、ルールbが不能化されることを意味する。この単方向性のメタルールは「ルールaとルールbとの両方が一緒には実行できない」というステートメントと同等である。したがって、不能化メタルールが方向性なしで表されるのに対し、絶対的要求メタルールは、単方向性である(互いに相手の逆である2個の絶対的要求メタルールは双方向性の絶対的要求を捉えるのに用いることができる)。

0044

「優先選択」メタルールは、記号的には、b>aとして表される。そして、「もしルールaとルールbとが両方共発動可能である場合には、ルールbは、ルールaも実行セットから外されるのでなければ、実行セットから外してはならない」ことを表すものとして定義される。いい替えれば、もしルールaとルールbとが両方共発動可能であり且つ両方が一緒には実行できない場合には、ルールaではなくルールbの実行が優先して選択される。

0045

すなわち、「優先選択」メタルールは、1対のシステムルールのうち1度に1個のシステムルールだけしか実行の選択ができない場合に、或る特定のシステムルールに他のシステムルールに対しての優先選択順位を与える。

0046

「スケジューリング」メタルールは、記号的に、aとbとの間にvを90度右回転させて得られる記号を挿入した式で表されるが、本文中では便宜上、a(<)bで表す。この場合の「スケジューリング」メタルールは、「もしルールaとルールbとが両方共実行の選択をされた場合に、ルールaがルールbよりも前に実行される」ことを表すものとして定義される。「スケジューリング」メタルールは、実行の選択をされた複数のルールが実際に実行される場合の実行順序の制御を可能にする。

0047

メタルールのセットMの形式的意味はこのセットMについてのモデルを考慮して定義される。メタルールのセットMについてのモデルの一例は、四文字構成体〈V,I,O,ω〉として定義される。ここにVはルールのセットで、OとIとVとのの関係は、O⊆I⊆Vで表され、ωはセットO上の全体の順序である。

0048

〈V,I,O,ω〉は、もし次の条件が成立する場合にメタルールμを満足する。
1.メタルールμが、a⊃bの形式を取る。そして、もしa∈Oの場合には、b∈Oである。
2.メタルールμが、[ab+上線]の形式を取る。そして、¬(a∈O&b∈O)である。

0049

3.メタルールμが、b>aの形式を取る。そして、もしab⊆I&a∈Oの場合には、b∈Oである。
4.メタルールμが、a(<)bの形式を取る。そして、もしa及びbの両方がO内に現れる場合には、aが、全体の順序ωにおいてbよりも前に現れる。

0050

もし四文字構成体〈V,I,O,ω〉が各メタルールμ(μ∈M)を満足する場合には、この四文字構成体〈V,I,O,ω〉は、メタルールのセットMについてのモデルである。

0051

活動状態のルールシステムS=〈V,M〉の、与えられた文法について、本発明によれば次の決定が可能である。

0052

・それらの決定とは、ルールa∈Vが与えられた場合に、ルールaが実行されず不活動ルールとなるような入力ルールセットがあるかどうかの決定と、このような不活動ルール全ての特定とである。ルールの条件記述が決して真実でない場合、又はルールが、決して生じ得ないイベントによって起動されるように設定されている場合には、このルールは決して発動されることがない。不活動ルールは、指定されたメタルールのセットが理由で不活動であるようなルールを全て含む。

0053

・1対のルールa及びb(a,b∈V) が与えられた場合に、ルールa及びbが共に実行されるような入力ルールセットがあるかどうかの決定と、このようなa及びbの対の全てについての特定とである。不活動ルールの場合と同様に、これら2個のルールの条件記述が実際に同時に満足されるようなデータベース状態及びイベント発生が実際にあるかどうかを定めるための分析は行われない。メタルールのセットが与えられた場合に条件の同時満足が可能かどうかだけが捉えられる。

0054

もしアプリケーションの意味(セマンティックス)によって、これら2個のルールが決して一緒には発動されないことが示される場合には、これをメタルールとして捉えることは有用である。

0055

・少なくとも1個の有効な非空(ノンエンプティ入力セットIについて、ノンエンプティ解「O」が可能かどうかの決定。

0056

・メタルールのセットから、発動可能な各ルールセットIについての出力ルールセットOの各々に対して特有の全体順序ωが得られるかどうかの決定。

0057

・セットM内のメタルールで冗長なものがあるかどうかの決定。

0058

メタルールのセットMが与えられた場合、このセットによって他のメタルールが論理的に暗示される。例えば、もしルールaが絶対的にルールbを要求し入れ替わってルールbが絶対的にルールcを要求する場合には、例えこの要求がメタルールにおいて明示的に述べられていなくても、これら2個のメタルールのモデルは、ルールaが絶対的にルールcを要求していることも満足しなければならない。

0059

同様に、もしルールaが絶対的にルールcを要求するがルールbとルールcとが互いに相手を不能化する場合には、ルールaは決して実行され得ない(ルールaは自身を不能化する)。

0060

上記の仕方でのメタルールの推論は、入力ルールのセットIとは無関係に行うことができる。本発明に基づく推論の手順を図2に示す。この手順によれば、ルールシステムSにおける与えられたルールのセットVとメタルールのセットMとに基づいて導出することのできる事実上全ての相互関係が推論される。この推論手順を用いることにより、決して実行され得ない不活動ルールを特定することができ、又他の決定についての根拠を得ることができる。

0061

本実施例における第1の推論ルールのセットでは、当初、スケジューリングメタルールに関する分析が遅らされる。スケジューリングメタルールに関しては、後の方の分析段階で考慮される。

0062

ルールのセットVとメタルールのセットMとからなるルールシステムSにおいてもしMの各モデルがメタルールμを満足する場合、Mによってメタルールμが暗示される。

0063

下で公理A1〜A8として定める、本発明に基づく構文法的推論ルールのセットによって、メタルールの暗示(すなわち推論)が定義される。推論ルールは、Γ(→)γの形を取る。ここに、Γはメタルールのセットであり、又γはメタルールである。メタルールμが、メタルールのセットM内にあるか又は次のA1〜A8に定める推論ルールを繰り返し適用することによってMから導出することができる場合に、「メタルールμをメタルールのセットMから導出することができる」と称し、これを、M(→)μと表す。

0064

A1:[ab+上線](→)[ba+上線]。ここにおいて、もしルールaがルールbと実行できない場合、bはaと実行できない。
A2:(a⊃b∧[bc+上線])(→)[ac+上線]。ここにおいて、もしルールaが絶対的にルールbを要求し、そしてもしb及びcが一緒に実行できない場合、ルールaとcとは決して一緒に実行できない。

0065

A3:[a+上線](→)[ab+上線]。ここにおいて、もしルールaが決して実行されない場合には、各ルールbについて、ルールa及びルールbは決して一緒に実行できない。
A4:(→)a⊃a。ここにおいてルールaは絶対的にそれ自身を要求する。
A5:(a⊃b∧b⊃c)(→)a⊃c。ここにおいて、もしルールaが絶対的にbを要求し、そしてもしルールbが絶対的にcを要求する場合には、ルールaは絶対的にルールcを要求する。

0066

A6:[a+上線](→)a⊃b。ここにおいて、もしルールaが決して実行できない場合には、各ルールbについてルールaは絶対的にルールbを要求する。
A7:(→)a>a。ここにおいて、ルールaはそれ自身に優先する優先選択を有する。
A8:(a⊃b∧c>c)(→)c>c。ここにおいて、もしルールaが絶対的にbを要求し、そしてもしルールcがルールbに優先する優先選択を有する場合には、ルールcはルールaに優先する優先選択を有する。

0067

もしこれらのルールを用いてメタルールμをメタルールのセットMから導出することができる場合その場合に限って、メタルールのセットMがメタルールμを暗示する。推論ルールA1〜A8のセットは、絶対的要求、不能化、及び優先選択メタルールについて健全且つ完全である。

0068

推論ルールA1〜A8の完全さから、どの絶対的要求メタルール及び不能化メタルールがルールのセットによって暗示されるかを、優先選択メタルールを考慮せずに定めることが可能である。「Mの上に^を配置して得られる記号」(本文では便宜上、[M+^]で表す)を、a⊃b又は[ab+上線]の形式を有するメタルールのセットM内のメタルールのセットとし、μをこれらの形式のうちの1つの形式のメタルールとすると、[M+^](→)μの場合その場合にのみ、M(→)μである。

0069

与えられたメタルールのセットMについてMによって暗示される絶対的要求メタルール及び不能化メタルールのセットの導出についての本発明に基づく手順例を図2に示す。各ルールaについて、セットa+ ={ルールb|M(→)(a⊃b)}及びセットaー ={ルールb|M(→)[ab+上線]}が計算される。図2の手順が完了すると、ap=a+ 及びam=aー が成立する。

0070

図2の手順によって、絶対的要求メタルール及び不能化メタルールについての効率のよい暗示点検が得られる。優先選択メタルールの暗示については、次の定理に基づいて点検することができる。すなわち、もし、b∈a+ である場合又はもしMが、c⊆a+ であるようなメタルールb>cを導出する場合のいずれかの場合にその場合にのみ、M(→)b>aが成立するという定理である。

0071

メタルールのセットMからの絶対的要求、不能化、及び優先選択のメタルールの暗示は、Mのサイズの時間多項式において点検が可能である。

0072

ここで、スケジューリングメタルールの分析を開始する。スケジューリング、絶対的要求、及び不能化のメタルール間の関係が、次の3個の推論公理によって捉えられる。ここで、aをルールとしXをルールのセットとした場合に、「各b∈Xについてa⊃b」の表記を簡約化して、a⊃Xと表記することとする。

0073

A9:(a(<)b1∧b1(<)b2∧...∧bk(<)b)∧a⊃X∧b⊃Y(→)a(<)b。ここにおいて、X∪Y={b1,...,bk}。(<)は、パスの両端が全ての中間点の存在を要求する限り、過渡的である。
A10:(b1(<)b2∧...∧bk∧b)∧a⊃X∧b⊃Y(→)[ab+上線]。ここにおいて、X∪Y={b1,...,bk}。もし2個のルールa及びbが共に、優先関係周期的なルールのセットの実行を要求する場合には、ルールa及びルールbの両方が実行を選択されることはあり得ない。

0074

A11:[ab+上線](→)a(<)b。a(<)bは、もしルールa及びルールbの両方が実行シーケンスに現れた場合にはルールaがルールbの前に現れることを意味する。このことは、もしルールa及びルールbの両方が実行シーケンスに現れることが決してない場合には自明の理である。b(<)aも公理A11によって導出が可能である。

0075

推論ルール(公理)A1〜A11は、絶対的要求、不能化、及びスケジューリングのメタルールについて健全且つ完全である。

0076

ルールシステムS=〈V,M〉はいくつかの静的特性を有する。これらの特性は、特定の入力ルールセットを点検せずに定めることが可能である。これらの特性は、活動性確定性、及び順序性からなる。

0077

もし発動可能なルールセットIが存在し、これに連関する実行ルールセットO内にルールaがある場合に、ルールaはルールシステムにおいて活動状態にある(アライブ)と称する。活動状態にないルールは不活動状態にある(デッド)と称する。活動状態にないルールはこれに付帯するメタルールと共に抹消され、これによってルールシステムのサイズが縮小簡約化される。

0078

もしメタルールのセットMがメタルール[a+上線]を導出する場合その場合にのみ、ルールaはルールシステムにおいて不活動状態にある。

0079

ルールシステムにおいてどの対のルールが或るルールセットOにおいて同時に発生可能かを知ることも、例えばどのようなスケジューリングメタルールを指定すべきかを定める際に有用である。もし2個のルールが共には発動できないことが(導出又は明示によって)知られていない場合、2個のルールが共に発動できるような例について(そのアプリケーションに特定の意味を考慮しなくても、又いずれのルールの内部分析もしなくても)少なくともあるモデルが存在する。

0080

メタルールのセットMが与えられた場合、ルールa及びbは、もし M∀[ab+上線] の関係が成立する場合その場合にのみ、或るモデルMのセットOにおいて発生が可能である。

0081

確定性の特性に関しては、発動可能な各ルールセットIについて実行ルールセットOがルールとメタルールとによって特有に定義されるという特性がルールシステムにある。最大限の実行セットによって、発動可能な各ルールを、メタルール及び他の発動可能なルールから阻止されることなく発動できる。

0082

もし出力ルールのセットOについての1個以上の全体順序ωに対して〈V,I,O,ω〉がMのモデルであるような、特有な最大限のセットOが、ルールシステムS=〈V,M〉の各入力ルールのセットIについて存在する場合、このルールシステムSは確定的である。

0083

不能化メタルールによって、ルールシステム内に非確定性が導入される。もしルールaがルールbに優先て優先選択されることを知らずに、メタルール[ab+上線]にも拘らずルールa及びbが発動可能な場合、ルールaが発動される実行セットとルールbが発動される実行セットとからなる2個の最大限実行セットが存在する。

0084

確定性を保証するために、不能化メタルールに優先選択を設定することによって不能化メタルールのあいまいさを除去する必要がある。ルールシステムが完全にあいまいさをなくすのに必要且つ十分な条件が、本実施例に基づいて導出される。

0085

ルールを前処理してルールシステムを縮小簡約化させることにより、確定性についての条件を得るための分析が可能となる。ルールシステムS’=〈V’,M’〉が与えられた場合、縮小簡約化されたルールシステムS=〈V,M〉が次の手順によって得られる。

0086

・V’内の各ルールについて1個のノードを持たせて絶対的要求グラフGを構築する。もしセットM’内にメタルールa⊃bがある場合、ノードaからノードbへの辺(エッジ)部が存在する。
グラフGの強固に連結された各要素{a1,...ak}を単一のノードaに縮小簡約化する。

0087

・ルール{a1,...ak}を単一記号aで置換することによりルールセットVを縮小簡約化する。ai の各発生を新しいルール記号aで置換することによりメタルールセットMを縮小簡約化する。重複メタルールを削除する。
・縮小簡約化されたルールセット及びメタルールセットが、それぞれV及びMである。
・〈V,M〉に対して活動状態分析を行い、不活動ルールを全てVから削除する。

0088

縮小簡約化により、メタルールセットから全ての絶対的要求周期が除去され、これらのルールをセットに一括することが許される。このような周期中のルールは、全てが出力セットに入れられるか又は全てが出力セットから除去されるかする必要がある。もし周期中のルールが1個でも不作動状態であると、全てのルールが不作動状態になる。したがって、これらのルールの分析は、1個のルール記号によって早められる。分析を更に早めるために、不作動状態のルールは全てルールシステムから除去される。

0089

縮小簡約化されたシステムS=〈V,M〉が与えられた場合、Dは、M内の全ての不能化メタルールのセットであり、εは、M内の残りのメタルール全てである。Dは、次のステップを反復適用することにより最小化される。この適用は、不能化メタルールセットが最小の不能化セットに到達して適用が不要になるまで継続される。
・もしメタルールμ∈Dが、ε∪D−{μ}から導出可能な場合には、セットDからμを除去する。

0090

結果として得られるセットDは、最小の不能化セットである。D内のメタルールは、最小の不能化メタルールである。縮小簡約化されたシステムS=〈V,M〉が与えられた場合、最小の不能化メタルールセットDは、固有であり、よく定義されている。

0091

ルールのセットVとメタルールのセットMとからなる、縮小簡約化されたルールシステムSは、もしM内の各最小不能化メタルール[ab+上線]について、M(→)(a>b)又はM(→)(b>a)である場合その場合にのみ、確定的である。

0092

確定的ルールシステムが与えられた場合、各出力ルールセットOについての固有の全体順序ωが必要である。

0093

ルールのセットVとメタルールのセットMとからなる確定的ルールシステムSは、もしMが、出力ルールセットO内のルールについての特有の全体順序を暗示する場合に、順序性良好と称する。すなわち、どのような入力ルールのセットであっても、もしルールa及びbが出力セットに現れた場合には、これらのルールは同じ順序で現れるに違いない。

0094

順序性良好のための必要且つ十分条件は、もしa,b∈Vの各対について、Mが次の3つの式で示す条件、
1.[ab+上線]、
2.a(<)b、又は
3.b(<)a
のうちの1つを暗示する場合に、ルールのセットVとメタルールのセットMとからなる確定的な、縮小簡約化されたルールシステムSが、順序性良好であるということである。

0095

もし、ルールa及びbが特異の対であることから、この必要且つ十分条件が満足されない場合には、これらのルールの相対的順序は、システムによって可能な任意の手法で定められることがプログラマーには判る。もしこれらのルールの実行の相対的順序に重要性がない場合には、プログラマーはこれを放置しておいて差し支えない。そうでなければ、プログラマーは、このルール対に対する適切な不能化メタルール又は順序付けメタルールを表明して、システムを順序性良好状態にしてもよい。

0096

上記の説明で、特定の入力セットを用いずに静的分析から、ルールシステムの有用な特性を定める手法と、これらの特性を利用してプログラマーによる追加の又は別のメタルールの指定を援助する手法を示したことは、当業者には明らかであろう。

0097

特定のイベントが発生し多数のルールがその条件記述を満足する場合の、メタルールの実際の適用例について次に述べる。すなわち、確定的なルールシステムS及び発動可能なルールセットIを与えられた場合に、対応する実行セットOの計算及びそれについての全体順序の設立が、残りのステップである。

0098

メタルールのセットMは、上記のように縮小簡約化されたものと仮定する。すなわち、互いに相手を絶対的に要求するルールは同価類に分解されているものとする。手順を適用する前に、発動可能なルールをその類別代表モデルに変換し、手順終了後に、類別代表モデルから個々のルールへ変換して戻すことは、簡単である。

0099

本発明の一実施例に基づく、順序付けされた出力セットの導出手順を図3に示す。

0100

別の実施例においては、グラフを用いることによって、より効率的に手法を実現することが可能である。メタルールグラフが、ルールセットV内の活動状態のルールの各々について1個のノードと、必須の不能化メタルールの各々についての、宛先のない辺部と、3種類の、宛先のある辺部とによって定義される。

0101

これら3種類の辺部は、絶対的要求メタルールの各々に対する辺部(メタルールa⊃bに対するノードaからノードbまでの辺部)と、優先選択メタルールの各々に対する辺部(メタルール、a>bに対するノードbからノードbまでの辺部)と、スケジューリングメタルールの各々に対する辺部(メタルールa(<)bに対するノードaからノードbまでの辺部)とである。

0102

メタルールグラフを構築する際、絶対的要求メタルールのセットの推移的な縮小簡約化だけを考慮すればよく、推論公理[A8]から導出されたスケジューリングメタルールは無視できる。メタルールグラフは、絶対的要求メタルール辺部を含む周期に沿って縮小簡約化される。そして、縮小簡約化されたグラフは、絶対的要求メタルール辺部に、位相的に格納される。

0103

特定の入力セットIが与えられた場合、メタルールグラフが最初に入力セットI内のノードセット上に投影展開される。この投影は、入力セットI内にあるグラフのノードだけと、I内のノードから放射するグラフ内の絶対的要求メタルール辺部だけと(もし宛先がI内にない場合は、空白NULL)と記した特別ノードを形成する)、I内の2個のノード間に位置するグラフ内のスケジューリング、優先選択、及び不能化メタルールの辺部だけを保持する。

0104

次に、投射されたメタルールグラフを、逆位相順に(絶対的要求メタルールに関して)そして各ノードについて移動させる。

0105

・もし「NULL」への外向きの優先選択辺部がある場合には、このノードと、このノードの先祖全てとと抹消し、抹消されたノードへの優先選択辺部に関する全てのノードも抹消する。
・このノードに入る不能化メタルール辺部がある場合には、その不能化メタルール辺部上の優先選択の方向について点検する。優先度の低いノードと、このノードの先祖全てとと抹消し、抹消されたノードへの優先選択メタルール辺部に関する全てのノードも抹消する。

0106

スケジューリングメタルール辺部に基づく位相順序でグラフに残るノードは、出力セット内の望む実行順序になっている。

0107

図3の順序付けされたセットの導出手順は、入力セットI内のルールの数での時間多項式で、確定的ルールシステムについての出力セットを計算する。これによって、発動可能なルールのセットが与えられた場合にどのルールをどの順序で実行するかの決定が高価すぎるコストにならないことが保証される(リソース消費に関して)。実は、このグラフ構造で、出力セットをメタルールの数のの時間線形で計算することが可能である。

0108

多項式(発動可能なルールの数の)のコストは、高性能アプリケーションにおける関心事である。対応する、発動可能なルールのセットで、このようなアプリケーションにおける規準的な更新の種類は存在するがわずかである。その1つは、各組合わせについて1回、実行順序を計算し、テ−ブルに格納する。その後、或る一般的なイベントによってルールセットが発動可能になった場合、適切な実行順序を見出すにはこのテ−ブルを見さえすればよい。

0109

本発明の理解に役立てるため、航空会社のデータベースにおける実施例について説明する。

0110

一般的な航空会社データベースには、頻繁利用客飛行距離フリークエント・フライヤーズ・マイル)の記録用フィールドに加えて、多くのフィールドが含まれるが、本発明の原理を示す目的から、この飛行距離記録フィールドだけに関する簡単化した形態を用いて説明する。

0111

各顧客について利用飛行距離を記録するためのフィールドを有する例示の航空会社データベースは、次のようなレコード関係を有する。
1.「フライト詳細」関係:顧客当りフライト当り1レコード。属性顧客識別子(cust−id)、出発地目的地、日付、サービス等級、飛行距離、その他。飛行距離フィールドは、顧客がこの飛行によって得た頻繁飛行距離のマイル数を記録する。

0112

2.「距離」関係:1対の都市当り1レコード。これら2都市間の航空マイルによる距離を示す。属性:出発地、目的地、及び距離。
3.「顧客」関係:顧客当り1レコード。この関係は、キーとしてのcust−id及びその他の属性を有する。属性には、合計マイル(顧客によって蓄積された合計頻繁利用客飛行距離)、及び状態(顧客の現会員資格ベーシックシルバーゴールド、又はプラチナ))。

0113

このデータベースで頻繁に適用される更新項目は、フライト詳細関係への新レコードの追加で、内容は、或る顧客がある特定のフライトを利用した記録である。説明の目的上、この記録挿入の時点において、記録の「マイル」フィールドがゼロ(又は空白)にセットされるものと仮定する。この挿入に連関して、データベース内の情報に基づいてこのフィールドの適切な価値を計算させるトリガーが設けられている。更に別のトリガーが、「顧客」関係の合計マイルフィールドを更新するように作用する。

0114

本説明の目的のために書かれたトリガーのいくつかについて下に説明する。これらトリガーの各々についての「イベント」は、「フライト詳細」関係への(要素のセットの)挿入で、省略する。新たに挿入された要素は、「挿入」関係に存在すると仮定する。トリガーの行動及び条件部分を下にSQL(構造化質問言語)ふうの構文法で記載する。

0115

[a]:「挿入」関係を更新
距離(マイル)を、挿入された発進地と挿入された目的地との距離から選択された距離にセットする。このルール[a]は飛行した1対の都市(出発地及び目的地)間の距離に基づいて基本マイル計算を行う。このルール(及び下のルールのいくつか)は、挿入されたセット内の各要素に適用される。

0116

[b]:「挿入」関係を更新
距離が<500マイルの場合、500にセットする。このルール[b]においては、各フライト毎に少なくとも500マイルが加算対象として認められる。

0117

[c]:「挿入」関係を更新
サービスクラスが1等の場合、距離を実マイルx2にセットする。このルール[c]によって、ファーストクラスの顧客には利用マイルの2倍の距離が加算対象として認められる。

0118

[d]:「挿入」関係更新
顧客資格プレミアムの場合、距離を実マイルx2にセットする。このルール[d]においては、プレミアム顧客には利用マイルの2倍の距離が加算対象として認められる。

0119

[e]:「挿入」関係更新
顧客の合計マイル数>100、000の場合、距離を実マイル+500にセットする。このルール[e]においては、既に1万マイルを超える合計マイル数を持つ顧客には追加として500マイルが加算対象として認められる。

0120

[f]:「挿入」関係を更新
目的地がサンフランシスコの場合、距離を実マイル+500にセットする。このルール[f]においては、サンフランシスコ空港飛来する顧客には特別販売促進として追加の500マイルが加算対象として認められる。

0121

[g]:「顧客」関係を更新
合計マイルを、「合計マイル」+「挿入」関係マイル数合計にセットする。このルール[g]においては、「顧客」関係に、加算対象とされた合計マイル数が累積される。「INSERTED」(挿入)が「挿入された要素のセット」を表すので、「SUM」を用いる。そして複数のこれら項目が同じ顧客に関連する。

0122

これらのトリガーが相互関係を有することは、当業者には明らかである。例えば、もしトリガー[g]が他の全ての適用可能なトリガーよりも前に実行された場合には、「顧客」関係に合計マイル数について格納されている結果が間違っていることになる。同様に、上記のルール[a]は、他のルールが適切に実行できるようにその前に実行を完了している必要がある。

0123

得られる結果を意味のあるものにするために、前項で述べたようなトリガー実行についての或る種の制御が要求される。異なる可能性のうちから適切な選択をするために他の制御も用いられる。

0124

例えば、ルール[d]の前にルール[f]を適用すると、もしサンフランシスコがプレミアム顧客の目的地だった場合には追加の500マイルの代わりに、実際には1000マイルを与えることになる。「f」の前に「d」を適用するとプレミアム顧客にサンフランシスコまでの500マイルだけを与えることになる。すなわち、どの順序を取るかが、得られるマイル数の最終値に影響を与える。

0125

しばしば、プレミアム顧客が100,000マイルを超えた値を累積している場合がある。これらの顧客には、実距離の2倍(ダブルマイル)だけを与えて追加の500マイルボーナスは与えないことが望ましい。いい替えれば、ルール[d]とルール[e]とは相互に不能化する。更に、100、000マイルを超えた蓄積のあるプレミアム顧客については、100,000マイルボーナスよりもプレミアムボーナスの方が望ましい。

0126

本発明においては、ルール間の相互関係を管理するために、メタルールの宣言仕様が用意される。例えば、上記の例において、メタルールが[d]と[e]とのうちのただ1つだけが実行されるように宣言すべきである。

0127

そこで、文脈中での実行用に適用可能なルールの部分集合を選択するようにメタルールが指定され実現される。そして、この選択された部分集合が望む順序で実行される。

0128

活動状態のルール[a]...[g] を考える。これらのルールの全てが、「フライト詳細」関係への挿入時に起動される。したがって、V={a,b,c,d,e,f,g}である。

0129

各ルールについての条件を点検する際に、「UPDATE」の「WHERE」節が命令する。ルール[a]及び[b]は常に発動可能である。その理由は、初めに「マイル<500」が真実だからであり、又、都市対の各々の間に「距離」要素があるからである。ルール「c」は、もしフライトがファーストクラスで利用された場合には発動可能である。ルール「d」は、もしフライトが「プレミアム」顧客によって利用された場合には発動可能である。

0130

ルール[e]は、もしフライトが、合計マイルが10、000マイルを超える顧客によって利用された場合に発動可能である。ルール[f]は、もしフライトがサンフランシスコで終る場合には発動可能である。ルール[g]は、もしフライトが登録された顧客によって利用されたばあいには発動可能である。すなわち入力セットIは、挿入されたフライト要素と顧客のレコードとに依存する。

0131

例示データベースのメタルールは次の通りである。
・絶対的要求メタルール:本例においてルール[c]は、ルール[a]も又実行されなければならないと要求する。そうでなければマイル値が定義されない。この制約を表すために、メタルール[c]⊃[a]が定義される。

0132

・不能化メタルール:本例において、ルール[d]及び[e]のうちの1個だけが実行を許される。

0133

前に述べたように、単方向性の不能化メタルールが利用可能である。例えば、もしルールaが実行される場合にはルールbは不能化される。このような因果関係が時にアプリケーション・セマンティックスにおいて発生するが、実行セットに何があるかという意味で、この単方向性ルールは、ルールa及びbの両方が共には実行できないというステートメントと同等である。

0134

これが、本発明による不能化メタルールをなぜ方向性なしで表現でき、一方、絶対的要求メタルールが単方向性であるのかの理由である(互いに逆の、2個の絶対的要求メタルールを用いて、双方向性の絶対的要求メタルールを捉えることが可能である)。

0135

・優先選択メタルール:本例において、ルール[d]及び[e]が両方共発動可能である場合、これらルールの両方の実行は、不能化メタルール[ab+上線]、によって禁じられる。この時点において、ルール[e]ではなくルール[d]を実行することが優先選択される。すなわち、[d]>[e]である。

0136

・スケジューリングメタルール:この航空会社データベース例において、ルール[a]及び[b]が両方共実行可能の場合、[a](<)[b]を述べることによって、ルール「b」より前にルール[a]を実行するように要求することが可能である。

0137

前に述べたように、[c]>[e]は、ルール[d]及び[e]の両方が発動可能であるが1個だけしか選択されない場合にルール[d]が選択されることを意味する。もし発動可能なセットがr[e]だけを含む場合には、ルール[e]を実行することは可能である。他方、[c]⊃[a]は、ルール[c]を実行させるためには、ルール[a]を実行しなければならないことを意味する。

0138

もしルール[c]だけが発動可能な場合には、「c」は実行できない。しかし、もしルール[a]だけが発動可能な場合には、「a」は実行できる。そしてもしルール[a]及び[c]の両方が発動可能であるがこれらのうちの1つを選択しなければならない場合には、ルール[a]が実行できる。

0139

例えば、次のメタルールは、上に述べたルール相互関係を捉える。
b⊃a:ルール[b]が絶対的にルール[a]を要求する。
c⊃b,d⊃b,e⊃b,f⊃b,及びg⊃b:ルール[c],[d],[e],[f],及び[g]は全て絶対的にルール[b]を要求する。
[de+上線]:ルール[d]及び[a]は共には実行できない。
d>e:もし[d]及び[e]の両方が発動可能な場合には[d]を優先選択する。

0140

a(<)b,b(<)c,b(<)d,b(<)e,b(<)f,b(<)g,c(<)f,c(<)g,d(<)f,d(<)g,e(<)f,e(<)g及びf(<)g:登録されたルール対が実行される場合、一方を他方よりも前にスケジューリングしなければならない。

0141

この航空会社データベース例について、四文字構成体、〈{a,b,c,d,e,f,g},{a,b,c,d,g},(a→b→c→d→g)〉はモデルである。用語(a→b→c→d→g)は、出力セット内のルール間の全体順序ωを指定する。

0142

航空会社ECAルールに対する上記メタルールについての図2実行手順によって、次の絶対的要求メタルールが導出(又は推論)される。新たな不能化メタルールは導出されない。a⊃aの形式で表される重要でない絶対的要求メタルールについては記載しない。

0143

c⊃a,d⊃a,e⊃a,f⊃a,及びg⊃a: これらのメタルールが与えられると、絶対的要求超及び不能化のメタルールが推論される。それから、次の優先選択メタルールが導出される(形式a>aの、重要でない優先選択メタルールは記載しない)。a>b,a>c,a>d,a>e,a>f,a>g,g>c,b>d,b>e,b>f。

0144

メタルールが与えられると、絶対的要求、不能化、及び優先選択のメタルールが導出される。公理A9〜A11を用いて次のスケジューリングメタルールが導出される:a(<)c,a(<)d,a(<)f,a(<)g(全て公理A9を使用)。

0145

本例において、[a+上線]の形式のメタルールは導出されなかった。したがって、ルールは全て活動状態である。不能化メタルールで唯一導出されたのは、 [de+上線]である。こうして、他のルール対は全て、或る入力セットについては出力セットに同時発生する。

0146

システムSのVを、V=abcdとし、Mを、 {[ab+上線],[cd+上線],c>d,a,⊃c,b⊃d}とする。これは、絶対的要求メタルールグラフが非周期的なので、縮小簡約化されたシステムである。最小不能化セットは、{[cd+上線]}である。その理由は、ルール[ab+上線]、が次のように導出することができるからである。すなわち、a⊃c∧[cd+上線]が、公理A2によって、 [ad+上線]を産出し、b⊃d∧[ad+上線]が、公理A2によって、 [ab+上線]を産出する。

0147

本例について、絶対的要求メタルールグラフは周期的である。したがって、縮小簡約化されたシステムは、当初のシステムと同じである。更に、不能化メタルールは、[de+上線]だけであり、これはメタルールセットの部分集合から導出できない。したがって、最小不能化セットは、{[de+上線]}である。

0148

最小不能化メタルールは、[cd+上線]の1個だけであり、これは、優先選択メタルールc>dがMによる場合である。不能化メタルール[ab+上線]が更に1個あり、これについては優先選択メタルールは導出されないが、システムは確定的である。理由は、ルールaとbとの間の選択がcとdとの間の選択の間接的効果としてなされるからである。

0149

実際、このシステムへの可能な16個の入力の全てについての特有な(入力/出力)セットは、次の通りである(○に/を重ねて得られる記号を便宜上、[○+/]で表す):[○+/]/[○+/],a/[○+/],b/[○+/],c/e,d/d,ab/[○+/],ac/ac,ad/d,bc/c,bd/bd,cd/e,abc/ac,abd/bd,acd/ac,bcd/c,及びabcd/ac。

0150

優先選択メタルールはd>eであり、最小不能化メタルールは、[de+上線]である。したがってこの航空会社システムは確定的である。

0151

本発明は、ルールシステムが特有な最大出力を選択するかどうかの回答への十分な条件を与えるだけでなく、まだ確定的ではないシステムを確定的にするには何をしなければならないかについての指標を提供するものである。具体的には、優先選択の方向を指定されていない特定の最小不能化メタルールを特定できる。そしてプログラマーが適切な優先選択メタルールを付加して、システムを確定的にすることができる。

0152

縮小簡約化されたルールセットV={a,b,c}及び、 M={a(<)b,b(<)c}について、このシステムは、確定的である。出力Iに対して、出力セットも又Iである。

0153

しかし、システムは順序性良好ではない。入力{a,b,c}について、出力は(a→b→c)として順序付けできる。しかし、入力{a,c}については、出力は順序付けできない。これは、スケジューリングメタルール内の中間ノードbを用いて、a(<)cを推論できるのが、bが出力内にあるときだけであり、bは必ずしも出力内にあるとは限らないからである。

0154

このように、このシステムは、対a,cが原因で順序性良好ではない。システムは、メタルールを指定することによって順序性を良好にできる。もしプログラマーが、aとcとの間の順序が重要ではないことを知っていれば、プログラマーが順序性が良好でないシステムとの共生を選ぶのもよい。

0155

与えられたメタルールセットから本発明に基づいて導出できるメタルールの完全セットは次のようになる(形式a>a及びa⊃aの、重要でない優先選択及び絶対的要求のメタルールについては含めない):b⊃a,c⊃a,d⊃a,e⊃a,f⊃a,g⊃a,c⊃b,d⊃b,e⊃b,f⊃b,g⊃b、[de+上線]。

0156

d>e,a>b,a>c,a>d,a>e,a>f,a>g,b>c,b>d,b>e,b>f。a(<)b,a(<)c,a(<)d,a(<)f,a(<)g,b(<)c,b(<)d,b(<)e,b(<)f,b(<)g,c(<)f,c(<)g,d(<)f,d(<)g,e(<)f,e(<)g,及びf(<)g。

0157

優先選択及び絶対的要求のメタルールが関与しないルール対がいくつかある。例えば、(c,d)及び(c,e)がこれらの対の2つの例である。従って、このシステムは順序性が良好ではない。しかし、今や(c,d)については、どの順序を用いるかはあまり問題ではない。しかし、(c,e)については、順序は重要である。この時点で、ルールシステム設計者は新しいスケジューリングメタルール、例えば、c(<)eを書こうとするであろう。

0158

例について更に詳細に述べると、「フライト詳細」データベースに要素を挿入し、結果として、ルールI={a,b,d,e,g}が発動可能であるとする。図3の手順を計算して、Iセットが絶対的要求メタルールに関して有効であるとする。そして、OをI={a,b,d,e,g}に等しくセットする。次のステップにおいて、最小不能化メタルール[de+上線]を考慮し、優先選択メタルールd>eが与えられ、ルールeがOから削除される。導出可能な、a⊃e又はe>aの形式のメタルールはない。したがって、これ以上するべきことはない。

0159

他の最小不能化メタルールで残っているものはない。したがって、出力セットO={a,b,d,g}は、最終の出力セットである。順序については、上記のスケジューリングメタルールが与えられると、全体順序ω=(a→b→d→g)が得られる。

0160

更に別の例として、入力セットI={a,b,c,d,g}に至る、別のルールの起動を考える。不能化メタルールにより、削除されるルールはない。そして、O=I={a,b,c,d,g}が産出される。今、2つの順序が可能である。ω1=(a→b→c→d→g)及びω2=(a→b→d→c→g)である。これらの順序は両方とも同じ結果をもたらす。したがて、ルールシステム設計者は、この問題を無視できるので、順序の選択はシステムにまかせればよい。

0161

本発明は又、プログラマーが、活動状態のデータベース内の多数のルール間の相互関係を指定し管理するための直観宣言手段を提供する。このような仕様についての公理化及びこのような指定されたメタルールセットから暗示を導出するための健全且つ完全な手順が本発明によって提供される。

0162

簡単な点検によって、与えられたルールセットがよく定義された特有の実行セット及び、特有の実行順序を有することが、特定のルールがその条件記述を同時に満足するかどうかに関係なく、保証されるかどうか、が定められる。活動状態及び同時発生性のようなルールセットのその他の望ましい特性についても検査点検が行われる。

0163

プログラマーが内部の特定の条件記述が何かについての知識を有することがしばしばある。プログラマーはこの知識を利用して、例えば、ルールaの条件が満足されているか、又ルールbの条件が満足されているか、もしくはルールa及びbについての条件記述が同時には満足されない等を定めることができる。

0164

このような、プログラマー側での「表明」は又、絶対的要求及び不能化のメタルールの形式に符号化してルール相互関係の管理と実行時の正当性の検証の両方に用いることができる。

0165

本発明におけるメタルール機能の語彙はきわめて大きい。実行の選択をされたルール間の(部分的な)順序だけでなく、実際に実行されるルールの適格なセットの正当付けも可能である。1つのルールが別のルールを要求し、1つのルールが又別のルールを不能化し、更にルール間の優先選択が設立される。

0166

トリガー装置がデータベースにおいてより多く用いられるようになり、より広範囲に利用されるようになるにつれ、多数のトリガールールの管理がかなりの重要性を帯びつつある。本発明は、或るルールによってセットされ別のルールによって点検される全体的な変数を用いる必要なしに、多数のルールの相互関係を制御するための宣言メカニズムを提供する。

0167

更に、ルールシステムの特性を推論するだけでなく、あいまいな行動を取るルールをプログラマーに示すことによりルールシステムのあいまいさへプログラマーをガイドすることのできる非常に完全且つ強力な分析システムも提供する。

0168

図4に、中央処理装置(CPU)801と記憶装置802とからなるワークステーション800を示す。記憶装置802は主メモリ803とディスク804とから構成される。記憶装置802はシステムルールのセットを内蔵する。本発明のメタルールが、通信ポ−ト805を介して記憶装置802に入力される。記憶装置内のメタルールを与えられてメタルールの完全セットがCPU801により、図2及び図3に示す本発明の手順を用いて導出される。そして、このメタルールの完全セットが記憶装置802に格納される。

0169

イベントが通信ポ−ト805を介して入力されると、記憶装置802に格納されているシステムルールセットが、CPU801によって点検される。ゼロ以上のこれらメタルールが装置の条件記述を満足されると発動可能(すなわち、実行準備完了状態)となる。CPU801が、メタルールの適用により、発動すべき発動可能ルールの部分集合を定める。更に、CPU801がシステムルールの部分集合の発動順序を定める。それから、CPU801が、出力ルールの順序づけされたセットを出力し、発動(すなわち、実行)する。

0170

以上の説明は、本発明の一実施例に関するもので、この技術分野の当業者であれば、本発明の種々の変形例を考え得るが、それらはいずれも本発明の技術的範囲に包含される。

発明の効果

0171

以上述べたごとく、本発明によれば、コンピュータシステムのシステムルール実現に際して、強力な超ルール(メタルール)を導入し、このメタルールを用いて、同一イベントに対して起動し得る複数のシステムルールの実際の発動を制御するようにしたので、従来技術では回避に難点のあったシステムルール間の矛盾対立が有効に回避できる。したがって、イベント発生時に効率よくシステムを運用することが可能となる。

図面の簡単な説明

0172

図1本発明の概念を説明する流れ図である。
図2本発明の一実施例により或る与えられたメタルールのセットによって暗示される絶対的要求メタルールと不能化メタルールとを導出する手順を示す手順図である。
図3本発明の一実施例に基づき、順序付けされた出力システムルールのセットを導出する手順を示す手順図である。
図4本発明を実現した一実施例を示す説明図である。

--

0173

10発動可能なシステムルールのセット「I」
20 超ルール(メタルール)のセット「M」
30出力ルールのセット「O」
800ワークステーション
801中央処理装置(CPU)
802記憶装置
803主メモリ
804ディスク
805通信ポ−ト

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ