(57)【要約】【課題】本開示は、知識(構造化データ)のコンテンツベースの検証に関係する。【解決手段】知識検証のためのコンピュータ実装方法は、検証に対するファクトを識別する段階を含む。検証に対するファクトを表すセマンティックモデルを作成することができる。ファクトに関連する文脈を識別し、識別された文脈に少なくとも部分的に基づきオートマトンを作成することができる。ファクトは、このオートマトンを使用して検証することができる。【選択図】図1
2013120605.tif 000002
【特許請求の範囲】
【請求項１】
知識検証のためのコンピュータ実装方法であって、
検証に対するファクトを識別する段階と、
検証に対する前記ファクトを表すセマンティックモデルを作成する段階と、
前記ファクトに関連付けられている文脈を識別する段階と、
前記識別された文脈に少なくとも部分的に基づきオートマトンを作成する段階と、
前記オートマトンを使用して前記ファクトを検証する段階とを含むコンピュータ実装方法。
【請求項２】
統合モデルを識別する段階をさらに含み、前記統合モデルは会社内および会社間のビジネス取引ネットワークに関する情報を含み、検証に対する前記ファクトは前記統合モデルに関連付けられる請求項1に記載のコンピュータ実装方法。
【請求項３】
前記オートマトンは、決定性有限オートマトンである請求項1に記載のコンピュータ実装方法。
【請求項４】
前記決定性有限オートマトンは、ε-非決定性有限オートマトンから導出される請求項3に記載のコンピュータ実装方法。
【請求項５】
前記決定性有限オートマトンは、状態、入力記号、遷移関数、開始状態、および最終状態のうちの1つまたは複数によって定義される請求項3に記載のコンピュータ実装方法。
【請求項６】
前記最終状態は受理状態であり、前記オートマトンは前記ファクトの検証に成功した後前記受理状態に入る請求項5に記載のコンピュータ実装方法。
【請求項７】
前記オートマトンは、前記セマンティックモデルに少なくとも部分的に基づき生成される請求項1に記載のコンピュータ実装方法。
【請求項８】
前記セマンティックモデルは、前記ファクトに関連付けられているファクト依存関係をさらに表す請求項1に記載のコンピュータ実装方法。
【請求項９】
検証すべき前記ファクトは、前記文脈の部分集合である請求項1に記載のコンピュータ実装方法。
【請求項１０】
前記識別された文脈に少なくとも部分的に基づき前記オートマトンを生成する段階は、モデルエンティティのそれぞれのインスタンスについてオートマトンを生成する段階を含む請求項1に記載のコンピュータ実装方法。
【請求項１１】
前記ファクトは、Datalogファクトである請求項1に記載のコンピュータ実装方法。
【請求項１２】
前記ファクトは、ファクト、知識、またはデータのうちの1つまたは複数である請求項1に記載のコンピュータ実装方法。
【請求項１３】
エラー状態を識別する実行時グラフ出力をもたらす段階をさらに含む請求項1に記載のコンピュータ実装方法。
【請求項１４】
エラーを識別する実行時テキストログ出力をもたらす段階をさらに含む請求項1に記載のコンピュータ実装方法。
【請求項１５】
前記オートマトンを使用して前記ファクトを検証する段階は、構造もしくは構造化データのコンテンツのうちの1つまたは複数を検証する段階を含む請求項1に記載のコンピュータ実装方法。
【請求項１６】
ドメイン固有言語が、検証プログラムを指定するためにプログラミングモデルに使用される請求項1に記載のコンピュータ実装方法。
【請求項１７】
検証プログラムが、前記セマンティックモデルから生成され、前記セマンティックモデルはドメイン固有言語で記述され、前記オートマトンは、前記セマンティックモデルから実行時に生成される請求項1に記載のコンピュータ実装方法。
【請求項１８】
前記オートマトンは、インテリジェントアルゴリズムによって自動的に生成される請求項17に記載のコンピュータ実装方法。
【請求項１９】
前記ファクトは、統合モデル内のファクトであり、前記統合モデルは前記オートマトンによる検証を受ける請求項1に記載のコンピュータ実装方法。
【請求項２０】
有形の非一時的な媒体上に格納され、命令を実行するように動作可能である、知識検証のためのコンピュータプログラムであって、前記命令は、
検証に対するファクトを識別する段階と、
検証に対する前記ファクトを表すセマンティックモデルを作成する段階と、
前記ファクトに関連付けられている文脈を識別する段階と、
前記識別された文脈に少なくとも部分的に基づきオートマトンを作成する段階と、
前記オートマトンを使用して前記ファクトを検証する段階とを含む、知識検証のためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検証(information validation)、より具体的には、例えば、決定性有限オートマトンを使用するコンテンツベースの知識検証(content-based knowledge validation)に関するものである。
【背景技術】
【０００２】
構造化データは、ユーザーに対して情報をグラフで表示するために使用されうるか、またはプログラムにより処理するために使用されうる。異なるソースに由来すると思われる、無効な情報は、構造化データの品質を損なう可能性がある。情報の検証では、構造化データの品質を、そのモデル、例えば、ビジネス取引のネットワークドメイン内の統合モデルに従って維持することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
全体として、本開示は、知識(構造化データ)のコンテンツベースの検証に関係する。これは、検出され、注入される知識のコンテンツだけでなく、与えられたモデル、例えば、統合モデルへの適合性をも含む。検証は、知識の(ユーザー定義の)依存関係の検証を含む。本開示では、統合モデルに従って企業の取引ウェブについて示される知識を検証するシステム、方法、およびコンピュータプログラム製品の設計ならびに実装を説明する。
【課題を解決するための手段】
【０００４】
いくつかの実施形態では、知識検証のためのコンピュータ実装方法は、検証に対するファクト(fact)を識別する段階を含むことができる。検証に対するファクトを表すセマンティックモデルを作成することができる。ファクトに関連する文脈を識別し、識別された文脈に少なくとも部分的に基づきオートマトンを作成することができる。ファクトは、このオートマトンを使用して検証することができる。
【０００５】
いくつかの実施形態では、知識検証のためのコンピュータプログラム製品は、有形の非一時的な媒体上に格納され、検証に対するファクトを識別する段階を含むことができる命令を実行するように動作可能であるものとしてよい。検証に対するファクトを表すセマンティックモデルを作成することができる。ファクトに関連する文脈を識別し、識別された文脈に少なくとも部分的に基づきオートマトンを作成することができる。ファクトは、このオートマトンを使用して検証することができる。
【０００６】
これらの実施形態のいくつかの実施例は、統合モデルを識別する段階も含むことができる。統合モデルは、会社内および会社間のビジネス取引ネットワークに関する情報を含むことができる。検証に対するファクトは、この統合モデルに関連付けられうる。
【０００７】
これらの実施形態のいくつかの実装では、オートマトンは、決定性有限オートマトンである。決定性有限オートマトンは、ε非決定性有限オートマトンから導き出すことができる。決定性有限オートマトンは、状態、入力記号、遷移関数、開始状態、および最終状態のうちの1つまたは複数によって定義されうる。最終状態は、受理状態とすることができ、オートマトンは、ファクトの検証に成功した後、受理状態に入ることができる。
【０００８】
これらの実施形態のいくつかの実装では、オートマトンは、セマンティックモデルに少なくとも部分的に基づいて生成される。
【０００９】
これらの実施形態のいくつかの実装では、セマンティックモデルは、ファクトに関連付けられているファクト依存関係をさらに表す。
【００１０】
これらの実施形態のいくつかの実装では、検証すべきファクトは、文脈の部分集合であってもよい。
【００１１】
これらの実施形態のいくつかの実装では、識別された文脈に少なくとも部分的に基づきオートマトンを生成する段階は、モデルエンティティのそれぞれのインスタンスについてオートマトンを生成する段階を含むことができる。
【００１２】
これらの実施形態のいくつかの実装では、ファクトは、Datalogファクト(Datalog fact)であるものとしてよい。
【００１３】
これらの実施形態のいくつかの実装では、ファクトは、ファクト、知識、もしくはデータのうちの1つまたは複数であるものとしてよい。
【００１４】
これらの実施形態のいくつかの実装は、エラー状態を識別する実行時グラフ出力を供給する段階も含みうる。
【００１５】
これらの実施形態のいくつかの実装は、エラーを識別する実行時テキストログ出力を供給する段階も含みうる。
【００１６】
これらの実施形態のいくつかの実装では、オートマトンを使用してファクトを検証する段階は、構造もしくは構造化データのコンテンツのうちの1つまたは複数を検証する段階を含むことができる。
【００１７】
これらの実施形態のいくつかの実装では、検証プログラムを指定するプログラミングモデルに、ドメイン固有言語を使用することができる。
【００１８】
これらの実施形態のいくつかの実装では、検証プログラムをセマンティックモデルから生成することができる。セマンティックモデルは、ドメイン固有言語で記述することができ、オートマトンは、そのセマンティックモデルから実行時に生成されうる。オートマトンは、インテリジェントアルゴリズムによって自動的に生成することができる。
【００１９】
これらの実施形態のいくつかの実装では、ファクトは、統合モデル内のファクトであり、この統合モデルはオートマトンによる検証を受ける。
【００２０】
本明細書で説明されているシステム、方法、およびコンピュータプログラム製品は、異なる次元(構造、コンテンツなど)の構造化データの品質に適用される。本開示では、構造化データの構造およびコンテンツの検証を自動的に行うが、ただし、この検証は構成可能である。検証プログラムを指定するプログラミングモデルに、ドメイン固有言語(DSL)またはFluent Application Programming Interface(Fluent API)を使用することができる。検証プログラムは、例えば、DSLから生成され、セマンティックモデルと称される。セマンティックモデルから、実行時モデルが、例えば、オートマトンとして生成される。いくつかの実装では、オートマトンは、インテリジェントアルゴリズムによって自動的に生成される。実行時モデルは、検証プログラムのトップダウン、ボトムアップ、またはランダムな評価などの異なる評価プロシージャを実行することができる。
【００２１】
本明細書で説明されているアプローチは、データの効率的な格納および読み込み、検証プログラムの並列処理、さらには共有メモリ計算(例えば、定義されている検証プログラムに対する同時並行性)を行うように設計される。
【００２２】
このアプローチは、ファクトの検証に対して適用可能であり、Datalogプログラムの一部であってもよい。Datalogファクトは、構造化されており、そのため、本開示に適用可能である。本明細書で説明されている技術は、複雑なファクトモデル、例えば、本明細書で説明されている統合モデルにも適用可能であり、本明細書で説明されている技術は、その領域に対するファクトを検証するために使用することができる(例えば、モデルベースの検証)。
【００２３】
検証プログラムは、検証プログラミングモデルを他のプログラミング言語として使用できるように、デバッグ可能である。デバッギンングは、リアルタイムのデバッギングのためにグラフ出力およびテキスト出力によって円滑に行える。
【００２４】
本開示では、正規言語および文脈依存言語の分野におけるプログラミングモデルとして構成可能であるが、自動化された検証スキームを定義する段階を用意する。これは、領域固有のデータ品質に対応することができ、値リスト、構造性などのさまざまな種類の検査も実行できる。検証プログラムを作成する人々のプログラミングに関する知識の程度はさまざまであると思われる。
【００２５】
状態は、検証プログラムの演算子に適用される。これらの状態は、自己定義可能であり、そのため、本明細書で説明されている技術は、フィルター状態、長さチェックなどのカスタム検証演算によって拡張することができ、文字列のチェック、数値型の境界チェックなどから開始するか、または文字列のチェック、数値型の境界チェックなどで終了する。
【００２６】
本発明の1つまたは複数の実施形態の詳細は、付属の図面および以下の説明で述べられる。本開示の他の特徴、目的、および利点は、説明および図面、さらに請求項から明白になるであろう。
【図面の簡単な説明】
【００２７】
【図１】ビジネスグラフエンジンのアクティビティ図である。
【図２】例示的な取引ネットワークランドスケープを表す概略図である。
【図３】例示的なビジネス取引ウェブランドスケープの概略図である。
【図４】統合ネットワークモデルの概略図である。
【図５】例示的な統合アルゴリズムのプロセスフロー図である。
【図６】システムのアウトゴーイングコールグラフの概略図である。
【図７】システムの拡張コールグラフの概略図である。
【図８】システムを追加することによるコールグラフの拡張の概略図である。
【図９】図5のステップ2、3、および4の結果としてのシステムSlのマージグラフの概略図である。
【図１０】決定性有限オートマトンの遷移図の概略を示す図である。
【図１１】ファクトの依存関係の抜粋を示すグラフである。
【図１２】message_flowファクトの例示的な解決された依存関係の抜粋の図である。
【図１３】2種類の引数検証のグラフ表現の図である。
【図１４】ファクト検証のグラフ表現である。
【図１５】ファクトを検証するため完全に構成されたε-NFAのグラフ表現である。
【図１６】部分集合構成に使用されるファクト検証ε-NFAのグラフ表現である。
【図１７】部分集合構成によって生成されるファクト検証DFAのグラフ表現である。
【図１８】セマンティックモデルのグラフ図である。
【図１９】共有メモリの例示的な実装を示す概略図である。
【図２０】オートマトンの例示的なプログラミングモデルのグラフ表現である。
【図２１】例示的なdataファクトのグラフ出力である。
【図２２】対応するsystemファクトが対応するdataファクトを有しないruns_onファクトに対する例示的なオートマトンのグラフ出力である。
【図２３】ホストURIが指定されていないruns_onファクトに対する例示的なオートマトンのグラフ出力である。
【図２４】有効なruns_onファクトに対する例示的なオートマトンのグラフ出力である。
【図２５】知識のコンテンツベースの検証に対する例示的なシステムレベルの環境を示す概略図である。
【図２６】ファクトを検証する段階のプロセスフロー図である。
【図２７】ファクトに対する状態リストを決定するための例示的なアルゴリズムを示す図(アルゴリズム1)である。
【図２８】ファクトモデルのレベルを決定するための例示的なアルゴリズムを示す図(アルゴリズム2)である。
【図２９】ファクト検証に対する前処理を行うための例示的なアルゴリズムを示す図(アルゴリズム3)である。
【図３０】オートマトンに対する次の状態を決定するための例示的なアルゴリズムを示す図(アルゴリズム4)である。
【図３１】ファクトの検証のための例示的なアルゴリズムを示す図(アルゴリズム5)である。
【図３２】ファクト検証後処理のための例示的なアルゴリズムを示す図(アルゴリズム)である。
【図３３】ファクト検証遷移関数の例示的なアルゴリズムを示す図(アルゴリズム7)である。
【図３４】引数の依存関係ファクトを決定するための例示的なアルゴリズムを示す図(アルゴリズム8)である。
【図３５】ファクト検証遷移関数のリターン状態を決定するための例示的なアルゴリズムを示す図(アルゴリズム9)である。
【図３６】定義ファイルからの例示的な抜粋を示す図(リスティング1)である。
【図３７】有効なdataファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング2)である。
【図３８】有効なdataファクトに対するドットグラフの例示的な説明を示す図(リスティング3)である。
【図３９】無効なsystemファクトを伴うruns_onファクトに対する例示的な定義ファイルを示す図(リスティング4)である。
【図４０】無効なsystemファクトを伴うruns_onファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング5)である。
【図４１】対応するsystemファクトを伴い、dataファクトがない、runs_onファクトに対する例示的な定義ファイルを示す図(リスティング6)である。
【図４２】無効なsystemファクトを伴うruns_onファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング7)である。
【図４３】無効なruns_onファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング8)である。
【図４４】有効なruns_onファクトに対する例示的な定義ファイルを示す図(リスティング9)である。
【図４５Ａ】有効なruns_onファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング10)である。
【図４５Ｂ】有効なruns_onファクトに対するオートマトンの例示的なテキスト出力を示す図(リスティング10)である。
【００２８】
さまざまな図面内の類似の参照記号は、類似の要素を示す。本開示で説明されているアルゴリズムおよびコードリスティングは、例を示すことを目的としている。ここに示されていないアルゴリズムおよびコードも適用可能である場合がある。
【発明を実施するための形態】
【００２９】
この後、本明細書で開示されている発明対象が適用可能な例示的な領域(ビジネス取引ウェブ)について説明する。しかし、この発明対象が、その領域だけに制限されることにはならないことは理解される。例えば、本明細書で説明されている発明対象は、後述の統合モデルに関連付けられているものを含む、構造化データに使用することができる。それに加えて、本明細書で説明されている発明対象は、演繹システムへの入力、リンクドデータコミュニティ(linked data community)に対するデータ品質検証、プロセスマイニングなど、他の領域についても適用可能である。
【００３０】
ビジネス取引ウェブは、SAP AGが開発したソフトウェアであり、企業の取引ネットワークの主要部の俯瞰をグラフで示すものである。このために、カスタマーランドスケープに関する情報を、論理知識表現がDatalog内に実装されている1つのモデルで収集し、統合し、格納する。ユーザーは自分専用のデータエクストラクタおよびプロセッサを開発することによってファクトの注入に影響を及ぼすがあるので、知識ベースの無矛盾性を保証するためにファクトをそのコンテンツおよび相互依存関係に従って検証しなければならない。この問題に取り組むために、決定性有限オートマトンに基づき、プログラミングモデルが開発された。これは、一般的に、Datalog内に符号化されている知識を処理することを可能にし、また検証ロジックにカスタム拡張の機能を付与する。
【００３１】
本開示では、コンテンツベースのファクト検証の異なる方法について説明し、決定性有限オートマトンを使用するファクト検証の概念、実装、およびプログラミングモデルに関して詳細に説明する。実装されたファクト検証オートメーション(FVA)機能は、異なる検証戦略を使用する与えられた文脈におけるファクトの分散検証を円滑にする。検証は、ドメイン固有言語を使用するファクトの構造の定義によって操作することができる。さらに、FVAに対して、検証ロジックを含むカスタム状態を実装することができる。さらに、本開示では、ビジネス取引ウェブの文脈における開発されたFVAの適用について説明する。これは、この文脈内の異なる根本的原因を評価し、異なる検証戦略に対する性能測定を示す。それに加えて、デバッギング、つまり、ファクトが無効であることの理由を分析する段階に関する何らかの指針もある。
【００３２】
企業は、従業員の技量と能力だけでなく、企業が参加するさまざまなビジネスネットワークに関する情報も含む、自社の知識を管理する。しかし、収集され、管理される知識の量に無関係に、知識の便益は、その品質と同程度でしかない。知識は、無矛盾でなくてはならず、したがって、検証される必要がある。
【００３３】
ビジネス取引ウェブは、会社内および会社間のビジネス取引ネットワークに関する情報を収集し、それらをモデル(統合モデルと称される)内に格納し、それらをグラフでユーザーに表示するソフトウェアである。しかし、情報が無効となる原因はさまざまであるため(例えば、ユーザーがファクトを手動で注入する可能性がある)、ビジネス取引ネットワークに関する知識の品質を維持するために情報を検証しなければならない。したがって、本明細書の主題は、知識のコンテンツベースの検証である。これは、検出され、注入される知識のコンテンツだけでなく、事前定義済みの統合モデルへの適合性をも含む。これは、知識の可能な依存関係の検証を含む。しかし、この研究は、完全性または無矛盾性に関して統合モデルそれ自体の検証を含まない。
【００３４】
企業は、非集中的な管理方式によりビジネスプロセスを遂行する大きなビジネス取引ネットワークを有する。ビジネス取引ウェブは、契約、仮想組織、下請契約、フランチャイズ、ジョイントベンチャー、持ち株会社、および他のものの結果である、異なる種類のビジネスネットワークによって形成される。現在まで、企業内でも、企業間でも、主要部の俯瞰を得る手段はない、商品またはサービスを別の企業に販売するプロセスである、企業間の企業間電子商取引(B2B)プロセスから結果として生じるネットワークのアウトラインを示す作業は非常に複雑である。
【００３５】
つまり、異なる情報技術、ミドルウェア、およびアプリケーションが管理されなければならない場合、これは、大きな労力を伴わずには行えない。例えば、「as-is」ネットワークに関する知識は、もし入手可能であれば、領域専門家または文書から集めなければならない。ミドルウェアは、使用されるプログラミング言語および通信プロトコルを気にせずに、アプリケーションシステムとデータソースとの間のプラットフォームに依存しない通信を実行することを可能にする抽象ソフトウェアレイヤと考えることができる。
【００３６】
そこで、ビジネス取引ウェブが開発中である。その目的は、会社のビジネス取引ウェブを正確に、明示的に表現することである。そこで、ネットワーク化された企業のB2B関係を可視化し、インテグレーション開発さらにはアプリケーションの背後にあるエンドツーエンドのライフサイクルを容易にし、異なる相互リンクされた情報に関する共同作業を可能にして実行を高速化する。これを行うために、ビジネス取引ウェブは、ビジネス、社会、およびインテグレーションのアーチファクトの例からの「as-is」ネットワークの自動生成を円滑にする。また、これは、異なる人々が推論されるネットワーク上の「to-be」側面の定義を協同で行うことを可能にする。これは、場合によっては、詳細な計画に基づいて行われうる、つまり、「to-be」ネットワークが、すでに存在している「as-is」側面を使用せずに、例えば、イベント駆動型プロセス連鎖(EPC)またはホワイトボード図面として新規に作成されるということである。さらに、これらは、ビジネスセマンティックス(例えば、ビジネスタグまたはドキュメントエンティティ)を使って推論されたネットワークを文脈化し、充実することができる。それに加えて、原価、価格および目的、サービスレベル、ならびに稼働システムの品質、さらには合意が履行されない場合の手続きに関する契約である、ポリシーおよびサービス内容合意書(SLA)を定義することが可能である。また、変更を元のデータソースに書き戻すことも可能である。随時協力し合って解決できる、ビジネスおよびインテグレーションの例外もしくはイベントが生じていないか、ネットワークを監視することができる。
【００３７】
ビジネス取引ウェブの利点は、取引ウェブの可視性、パートナーオンボーディング、ビジネス例外管理、および契約決定にある。これらの特徴はすべて、カスタマーの自取引ウェブの文脈において遂行できる。
【００３８】
図1に示されている、ビジネスネットワークグラフの作成は、異なるレイヤを使用することで行いやすくなる。図1は、ビジネスグラフエンジンのアクティビティ図100である。ビジネスネットワークグラフの作成には、異なるレイヤが関与する。最下位レイヤであるネットワーク/カスタマーランドスケープレイヤ102は、右側にあり、ビジネス取引ウェブに関する情報が抜粋される。最上位レイヤであるビジネスグラフユーザーインターフェース/アプリケーション112は、図1の左側にあり、そこではグラフが表示される。ネットワークソースレイヤ104では、ネットワーク/カスタマーランドスケープ102内でソースを探索する。ネットワークソースレイヤ104の一部であり、システムから情報を読み出し、処理するための特定領域の知識を含むいくつかの領域分析コンポーネントは、コネクタインフラストラクチャを使用してソースシステムからデータを取り出す。コネクタは、このランドスケープ内のシステムと、例えば、ハイパーテキスト転送プロトコル(HTTP)またはエンタープライズサービスを介して通信し、それらに関する情報を読み込む。例えば、「データを発見する」コンポーネント114は、セキュアチャネル上で「データを抽出する」コンポーネント116に接続する。「データを抽出する」コンポーネント116は、「ファクトに対してデータ分析を処理する」コンポーネント118に接続され、そこで、情報がファクトの形態で格納される。次のステップは、エクスポートされたファイルまたは公開されたAtomフィード(「分析ファクトを公開する」コンポーネント120)を介してファクトをネットワーク統合レイヤ108に提供することである。これは、非武装地帯(DMZ)106において行われる。一般的に、イントラネットの外部からそれへのアクセスを許可することなく到達されることを必要とするサーバーへのアクセスを許可するコンピュータネットワーク内のサブネットである。ビジネスクラスエンジン100の文脈において、ファクトは、ネットワーク統合レイヤ108からアクセスすることができ、これはクラウド内にあってもよい、つまり、これはクライアントのコンピュータ内にインストールされていないということである。しかし、ファクトは、ネットワーク/カスタマーランドスケープレイヤ102から抽出される。これら2つのレイヤを分離するために、DMZ 106がある。ネットワーク統合モデルレイヤ110とネットワーク統合レイヤ108とからなる、リンクドデータエンジン109は、DMZ 106および対応する規則からの前処理されたファクトを利用し、推論アルゴリズム124を使用してファクトを統合する。
【００３９】
推論アルゴリズム124は、統合プロセスを含む。統合は、発見されたデータと、さらに知識ベース内にすでに格納されている情報をも含む。統合時に、システムに関する情報は、共通フォーマット(例えば、統合モデルのフォーマットなど)に変換される。このモデルついて、以下でさら説明する。統合した後、統合モデルが持続する。次のステップは、統合モデルをネットワーク統合メタモデル(Network Integration Meta-Model)(NIMM)リソースグラフ121に変換する。NIMMモデル122は、会社内、および会社間のビジネスプロセスをモデル化するためのグラフ表現に関する標準である、Business Process Modeling Notation (BPMN) 2.0の拡張および特殊化である。したがって、NIMM 122は、異なるエンティティ、および会社内および会社間とのそれらの関係を記述する。これは、ネットワーク統合モデルレイヤ110内で行われる。最後に、ビジネスグラフユーザーインターフェース/アプリケーション112において、ビジネスクラスを解決し、ユーザーインターフェース上に表示することができる130。
【００４０】
ビジネスグラフは、異なる企業および人々からなるグラフであるが、さらには、互いに協力し合うシステムおよびアプリケーションのネットワークも含む。一般的に、大企業のビジネスグラフは、2つのネットワークからなり、一方は内部プロセスのためのアプリケーションおよびミドルウェアのネットワークであり、もう一方はビジネスパートナー(例えば、仕入れ先、運送会社、または販売店)と相互にやり取りするために使用される外部プロセスのネットワークである。それが明らかでない場合であっても、エンタープライズリソースプランニング(ERP)システム内の膨大な量のデータは、ネットワーク化された企業の外部からやってくる。これの原因は、実際には、企業間電子商取引(B2B)プロセスが、多くの場合、ビジネスをより協力的に行うためにビジネスパートナーとの取引上のドキュメントのやり取りとして実装されることにある。このため、パートナーネットワークおよびパートナー関係の文脈においてリンクドデータアーキテクチャのスタイルをとる。したがって、複数の企業にまたがってプロセスのオーケストレーションを行うことが強く要求される。オーケストレーションは、実行可能なビジネスプロセスならびにこれらのプロセスと内部ウェブサービスおよび外部ウェブサービスとの相互のやり取りさらにそれらの相互のやり取りの記述である。接続、ビジネス、および社会的側面を組み合わせた、一般化されたビューは、リンクドビジネスグラフと称することができる。
【００４１】
典型的な従来の技術的なネットワークが、図2に示されている。図2は、例示的な取引ネットワークランドスケープ200を表す概略図である。図2は、イントラおよびインターネット内のシステムからなるよりインテグレーション指向のビジネス取引ネットワークの抜粋を示している。これらのシステム上で、異なるアプリケーションおよびミドルウェアが実行され、互いにやり取りしている。例えば、システムA 202は、アプリケーションAおよびエンタープライズサービスバス(ESB)-Aを含み、これは、エンタープライズサービス(ES)プロキシであってよく、これはシステム組み込みインテグレーションのカテゴリのものである、ウェブサービスベースのアプリケーションプロキシである。イントラネット内で接続されているシステムは、互いに通信するか、またはDMS内の、もしくはインターネット上のシステムと通信することができる。例えば、システムD 204は、システム206とファイアウォール越しに通信するが、これは、この場合、B2Bゲートウェイである。このカスタマーランドスケープは、インテグレーションコンサルタントおよびインテグレーションアーキテクトによって実装されることもありえ、これは、IT運用および管理ペルソナによって管理されうる。この時点では、完全なネットワークの一般ビューは、企業内のインテグレーション知識を収集することによってしか得られない。さらに、このビジネス取引ウェブは暗黙的である、つまり、それらのシステムおよびそれらの間の関係のみを示す。しかし、ビジネス取引ウェブ内の企業は、ビジネスパートナーの相互のやり取りの種類に応じて異なる役割(例えば、カスタマーまたはベンダー)を果たす。この情報および対応するセマンティックスは、マスターデータ、ビジネスプロセス、および領域特有の構成内に隠されている。
【００４２】
図3は、例示的なビジネス取引ウェブランドスケープ300の概略図である。このネットワークは、企業302およびそのビジネスパートナー(小売店304およびベンダー306)を含む。商品は、倉庫に保持することができ、ERPロジスティックシステム308が、異なる流通センター310を接続する。流通センター310は、ERPシステムリテール312およびロジスティックス314などの他のERPシステムを通じてビジネスパートナーと接続する。図3のビジネス取引ウェブランドスケープ300は、自社内、および企業にまたがる関係および依存関係を維持するビジネスおよびパワーユーザーからなる。ユーザーは、毎日の仕事をこなすために、異なるビジネス領域内の特定の知識、さらには他の領域との頻繁な通信連絡を必要とする。これらの状況の下で、ユーザーは、取引関係を俯瞰することができるようになる。
【００４３】
ユーザーの自分の画面上に表示される、リンクドビジネスグラフは、1つのモデル、つまり統合モデルに基づく。上で述べたように、統合モデルの最初の未処理の形態のものは、ネットワーク分析によって収集された領域特有の情報を使用することによって形成される。この未処理のデータを使用して、異なるアプリケーションおよびインテグレーションシステムにまたがるネットワーク上のビュー、さらにはビジネスの側面である、統合ネットワークが、統合メカニズムによって決定される。このメカニズムは、このタスクを遂行するためだけの量の情報を含む。
【００４４】
統合モデルの構造は、図4に示されている。図4は、統合ネットワークモデル400の概略図である。このモデルは、ビジネス取引ウェブの主要な参加要素と関係を示す。図4は、ビジネスネットワーク内のいくつかの参加要素を例示している。主要な参加要素は、システム(例えば、システム402およびホスト404)である。システムは、runsOnセマンティクを使用して物理的エンティティ(つまり、ホスト)に割り当てられうる論理的エンティティである。これら2つのシステム間の関係は、MessageFlows 408またはSysteinLinks 406によって定義されうる。さらに、2つの参加要素の間のメッセージの交換を表す、MessageFlow 408は、システムと構成との間に、または2つの構成間にも存在しうる。構成は、システムに属し、システム間の関係に関する技術的またはビジネス情報を記述するものである。2種類の構成があり、それぞれ、インカミングMessageFlowsを示す、インカミング構成、およびアウトゴーイングMessageFlowsを表す、アウトゴーイング構成である。
【００４５】
統合モデルの重要な特性の1つは、セマンティックスrunsOn 420、sameSystem 422、およびsameHost 424を除くすべてのエンティティ、ならびにsystemProperties 426ファクトは、データエンティティにリンクされており、それらに関する技術的情報、例えばそれらのURIを含む。その結果、対応するエンティティと一致する1つのデータエンティティが存在しなければならない。
【００４６】
一般に、この考え方は、物理的ホストをParticipantとして表し、その後、このホストとこのホスト上で実行しているシステムとによって提供される、または呼び出されるインターフェースを見つけるというものである。異なる種類のシステムは、それらの上で異なるアプリケーションおよびインテグレーションロジックが実行される。統合のため、インテグレーションロジックおよびビジネスエンティティは、システムという用語によって1つにまとめられる。図4のブラケット[]は、データの分析および発見の種類を示し、[ユーザー]名は、情報がユーザーによって注入されたことを意味するが、[バス]または[ディスク]は、ビジネスもしくはインテグレーション関係データを意味する。
【００４７】
統合モデルが取り扱う発見された情報は、ファクト(Datalogファクトなど)を使用して形式化される。Datalogは、一階述語論理を使用する知識の表現の一種である。つまり、これは、ホーン節を使用する関係に対する演算を表現する言語である。一般に、節は、複数のリテラルの和である。リテラルは、原子式または原子式の否定である。原子式の1つの部分は、述語記号pである。それぞれの原子式は1つの述語を有するので、一階述語論理は、述語論理とも呼ばれる。原子式の他の部分は、引数(qi)のリストである。したがって、これは、以下のようにして記述することができる。
p(q1, q2, ..., qi)
【００４８】
一般に、ホーン節は、高々1つの正のリテラルを有する節である。以下のようにホーン節にいくつか異なる種類のものがある。
【００４９】
ホーン節が、1つの単一の正のリテラルからのみからなる場合、これはファクトと称される。ファクトは、述語と引数のリストから構成されるだけでなく、これらはアリティkも有する。式pkは、kが述語pを持つファクトのアリティであることを意味している。例えば、統合モデルにおけるシステムは、以下のファクトによって記述される。
system_discx(name; description; systenURI)
このファクトは、3つの引数をとるので、そのアリティはk=3、つまりsystem3である。ファクトがデータベースに格納されると、これは、外延データベース(EDB)と称される。これは、統合モデルを表現する方法である。
【００５０】
1つまたは複数の負のリテラルからなるホーン節は、整合性制約として定義される。
【００５１】
1つの正のリテラルと1つまたは複数の負のリテラルがある場合、ホーン節は規則と称される。規則は、頭部hと本体とからなり、本体は式p1Λp2Λ...Λpiのような形をとる。piのそれぞれは、サブゴールと称される。完全な規則は、以下のようになる。
h:- p1Λp2Λ...Λpi
この規則は、p1とp2と...とpiが真である場合に、hは真であることを意味する。知識ベースに規則を格納したものは、演繹データベース(IDB)と称される。
【００５２】
さらに、ホーン節の集合体は、論理プログラムと称される。このプログラムは、ファクトおよび規則に関して論理的推論を適用するDatalogエンジンによって実行される。そうするために、ビジネス取引ウェブエンジンは、特別な統合アルゴリズムを使用する。これは、分析の大部分を特定のソースモデルと相互にやり取りする特定の「調査して分析する」コンポーネントにデリゲートする、コンソリデータによって調整され、実行される。したがって、コンソリデータは、異なるシステムのソースモデルから独立したままでいられる。
【００５３】
前述のように、統合アルゴリズムは、発見されたファクトから新しいファクトを導出するために使用される、規則の集合(例えば、Datalog規則)として記述される。統合アルゴリズムによって処理されるすべてのファクトは、表1および表2で説明されている。表1は、図5の統合アルゴリズムで使用される発見されたファクトの一例の抜粋である。この表は、発見されたファクトの選択、その意味、およびそれらが発見されたときの統合アルゴリズムのステップを示している。
【００５４】
【表１】
2013120605.tif 000003
【００５５】
表2は、例示的な拡張統合モデルにおける発見されたファクトの抜粋である。この表は、発見されたファクトの選択および拡張統合モデルにおけるその意味を示している。
【００５６】
【表２】
2013120605.tif 000004
【００５７】
統合アルゴリズムの概要は、図5に示されている。図5は、例示的な統合アルゴリズムのプロセスフロー図である。このアルゴリズムのステップは、関連する情報が確実に発見されるように特定の順序で実行されうる。統合アルゴリズムの第1のステップは、一意的なホストおよびシステム502を識別することである。上述のように、ネットワークは、カスタマーランドスケープ内で実行されるホストに基づく。ホストは、通常、名前、インターネットプロトコル(IP)アドレスなどによって識別される。ホスト上で実行される論理的な識別であるシステムは、文脈依存の識別子を有するだけである。ホストとは対照的に、システムに対して普遍的に適用可能な識別スキームはない。その結果、ホストおよびシステムに関する情報は、異なるソースから収集され、ソース特有のソースモデルに最初に格納される。これは、ネットワークソースレイヤにおいて生じる。単一の統一されたモデル(統合モデル)を作成するために、一意的なシステムおよびホストのリストをコンパイルしなければならない。
【００５８】
上で述べたように、問題は、普遍的な識別スキームがないという点である。例えば、時間が経過するうちに、特定のIPアドレスを持つホストに対して、異なるドメインネームシステム(DNS)名が使用され、またその逆もありうる。この問題を解決するために、可能なすべての識別子の集合に同値類を作成する。1つの同値類は、同じシステムをもしくはホストを識別することが知られているすべての識別子を含む。同値類の少なくとも1つの要素は、他の要素が変化したときにも変化しないので、一定の、ただし段階的な変化がある間、ホストおよびシステムの識別は、長期間にわたって維持されうる。新規情報を追加し、期限を経過した情報を取り除くプロセスは、連続的である。その結果、どの情報が関連性を有し、との情報が期限切れとなっているかを判定する方法は、発見されたそれぞれの情報にタイムスタンプを追加することによってなされる。
【００５９】
次いで、システムからのインカミングおよびアウトゴーイングコールの判定が実行される504。ソースモデルを使用して、異なるシステム間のインカミングおよびアウトゴーイングコールを判定することが可能である。一方で、システムへのインカミングコールの大半に対するインカミングコール構成があると仮定される(ただしおそらくはすべてについてではない)。他方では、システムのほとんどのアウトゴーイングコールに対してアウトゴーイングコール構成があるべきである。しかし、リモートファンクションコール(RFC)などの、いくつかの場合については、システムのファンクションが別のシステムによって呼び出される場合、リモートで使用されているファンクション以外の必要なインカミングコール構成はない。したがって、構成がないということが検出されうる。このステップの結果は、図6に示されているような特定の識別子を持つシステムに対するアウトゴーイングおよびインカミングコールグラフであるべきである。図6は、システム600のアウトゴーイングコールグラフの概略図である。一意的に識別されたシステムS1 602は、異なるアウトゴーイングコール構成(例えば、OCx 604、OCa 606)を有し、これらの構成はそのシステムを直接的にまたは間接的にそれを他のシステムに接続する。
【００６０】
次のステップは、アウトゴーイングコール506に基づきシステムからのメッセージフローを判定することである。アウトゴーイングコールは、特定のシステムの方に向けられるので、対応するコール構成は、多くの場合、そのコールを受けるシステムの識別子を含む。この場合、これらの識別子は、第1のステップで発見されたシステムの識別子とマッチングされる。このステップの結果、図7に示されているように、特定の識別子を持つシステムに対する拡張コールグラフが得られる。これは、システムを存在するアウトゴーイングコール構成に追加することによって生じる。図7は、システム700の例示的な拡張コールグラフの概略図である。一意的に識別されたシステムS1 702は、異なるインカミングコール構成(例えば、ICz 704、ICy 706)を有し、これらは、メッセージフローを介して他の一意的なシステム(例えば、S2 708)に対するアウトゴーイングコール構成(例えば、OCb 710)に接続される。
【００６１】
次いで、インカミングコールに基づくシステムへのメッセージフローが決定される508。特定のシステムのそれぞれのインカミングコール構成について、コール側システムの識別子をステップ502で見つかったシステムとマッチングする。これは、ステップ506に類似しているが、この場合、アルゴリズムは、検査されているシステムに送信するシステムを探索するが、ステップ506では、調査されたシステムからコールを受けたシステムを探していた。しかし、アウトゴーイングコール構成で受け手を見つけるのが一般的であるとしても、インカミングコール構成で送り手を見つけるのはあまり一般的ではない。この理由は、非常に単純である。例えば、Aという人が、Bという別の人に葉書を送ることがある。葉書がBに届くように、Aは、葉書にBの住所を書く必要があるが、そうしないと、Bの住んでいる場所が郵便局にはわからないからである。しかし、郵便局にとっては、Aの住んでいる場所を知るのは重要ではない。したがって、葉書をBに届けるためには、Aが葉書に自分の住所を書くことは必須ではない。同じことが、システムおよびコール構成にも当てはまる。そのような理由から、インカミング/送り手の対に比べてかなり多いアウトゴーイング/受け手の対が発見される。全体として、このステップは、インカミングコールの送り元であるシステムを追加するときにステップ506によって形成されるグラフをさらに拡大する。その結果のグラフに対する例が、図8に示されている。図8は、システムを追加することによるコールグラフの例示的な拡張の概略図800である。システムS1 802は、他のシステム(例えば、S2 804)と直接的に、またはそのインカミングコール構成(例えば、ICa 806)および他のシステムのアウトゴーイングコール構成(例えば、OC1 808)を介して間接的に通信する。通信元であるシステムの追加は、コールグラフをさらに拡張する。
【００６２】
次のステップでは、システムに対するコールグラフがマージされ、ネットワークが形成される510。このステップでは、アルゴリズムは、異なる識別されたシステムからのすでに発見されているインカミングおよびアウトゴーイングコール構成をマッチングすることによってさらに多くのメッセージフローを決定しようとする。これは、互換性のあるメッセージタイプまたはプロトコルをマッチングすることによって行われる。いくつかのインカミングコール構成が、すでに識別されているアウトゴーイングコール構成とマッチしないか、またはその逆である可能性がある。しかしながら、これらの構成は、統合モデル内にまだ保持される。このステップが実行され成功した後、すでに作成されているグラフの間にいくつかの追加のリンクがある。図9は、(図5の)ステップ504、506、および508の結果としてのシステムSlのマージグラフ900の概略図である。このグラフ900は、システムS1 902と直接的にまたは間接的に通信しているすべてのシステム(例えば、S2 904)および構成(例えば、OCa 906およびICz 908)を示している。
【００６３】
次のステップは、メッセージフローをアプリケーションおよびインテグレーションコンテンツ512とリンクする。このステップがある理由は、前のステップの結果はネットワーク上のビューであるが、発見されたメッセージフローはホストとシステムとの間の通信しか表さないことである。しかし、アウトゴーイングコール構成は、配備され、システム上で実行中のアプリケーションおよびインテグレーションコンテンツへのリンクを有することもできる。アプリケーションホストまたはシステムおよび特定のアウトゴーイングまたはインカミングコール構成について。特定のアプリケーションプロキシまたはシステムそれ自体へのリンクを決定する。これは、同時に1つのホスト上で実行中のアプリケーションが多数ありうるため重要である。インテグレーションバス、エンタープライズサービスバスまたはB2Bゲートウェイ、および特定のインカミングコール構成については、このステップで、1つのアウトゴーイングコール構成またはアウトゴーイングコール構成の集合を決定する。これは、後でインテグレーションプロセスとして参照される。
【００６４】
最終ステップは、ユーザーエンリッチメント(user enrichment)514の組み込みである。統合モデルの品質は、アルゴリズムが異なるデータソースから情報を集めるにつれて時間の経過とともに改善される。さらに、これは、「ユーザーエンリッチメント」とも称される、直接的ユーザー入力から学習することができる。これらのファクトは、postfix_discxによって指示される、発見されたファクトと比較して由来が異なることを強調するために接尾辞ユーザーによってマークされる。
【００６５】
これらは、統合アルゴリズムのステップで言及されていないとしても、例えばシステムまたはシステム上で実行されるアプリケーションのインターフェースに関する、統合モデルが管理する情報はさらにある。これらの種類の情報は、統合時には(まだ)処理されていない。しかしながら、これらは、リンクドビジネスグラフ上に表示されるべきである。
【００６６】
統合モデルの無矛盾性を確実なものとするために、ファクトの検証が行われなければならない。ビジネス取引ウェブの文脈において(図4を参照)、知識検証は、ファクト集合内のすべてのファクトが一貫していることを保証するプロセスである。これは、それぞれのファクトがビジネス取引ウェブのモデルに属す、つまり、その構造が予想どおりであり、ビジネスグラフを作成するために必要な本質的情報を含むことを示している。したがって、妥当性は、以下を含む。
1. 必要なすべての引き数の存在、
2. 引数に対して定義されている可能性のある制限への適合性(例えば、システムの名前の長さまたはパターン)、
3. ファクト同士の間のすべての依存関係を解決する可能性(例えば、それぞれのrunsOnファクトに対する有効なシステムおよびホストファクト)。
ファクト間の依存関係を解決するときに、ファクトを一意的に識別する1つのキー引数がなければならない。この引数は、ファクトのURIである。一般に、「ユニフォームリソースアイデンティファイア(URI)は、抽象的または物理的リソースを識別するコンパクトな文字の列である。」URIはリソースを識別するものなので、これは、ファクトが依存する対応するファクトが見つかることを保証する。その結果、ファクトの大部分は、そのURIをプライマリーキーとして含む1つの引数を有し、これはそれらのファクトを一意的に識別するために使用される。他のファクトも、他のファクトのURIを含むが、これらのURIは、それらが依存するファクトへの参照として使用される。例えば、システムファクトの検証は、以下の調査を伴う。
1. システムは名前およびURIを有するか?名前は、クラシカルユーザーインターフェース上に表示され、URIは、ファクトを識別し、依存関係を解決するために必要である。
2. 引数の名前が少なくとも1つあるが、長さ255文字以下であるか?
3. systemファクトと同じURIを有する有効なdataファクトがあるか?
その結果、これら3つの要件が満たされた場合かつその場合に限り、systemファクトは有効である。
【００６７】
知識検証のインセンティブは、知識ベースが異なる原因により矛盾を生じることを防ぐことである。ソースシステムからのデータ発見および抽出において実装エラーがありうる。例えば、これらのコンポーネントのソースコードに変更がある場合、発見は、もはや正常に機能せず、そのため、かなり正しいファクトをもゆがめてしまう可能性がある。これらの実装エラーに気づくために、知識検証が役立つ場合がある。さらに、ユーザーは、ファクトも同様に注入することが許される。これは、不正確な、矛盾したファクトの潜在的発生源でもある。最後に、カスタマーまたはパートナーは、自分の「ファクトプロバイダ」を構築することができ、これらはソースシステムからファクトを抽出し、したがって不正確なファクトの考えられる原因である。知識ベースに格納されているファクトのソースに関係なく、これらは、知識ベース全体に矛盾を生じさせるべきでない。これらの理由から、検証が不可欠である。
【００６８】
上で述べたように、知識ベースは、矛盾がないと想定される。したがって、ファクトが持続する前の検証は、妥当なものと思われる。最良の時点は、検証が持続するプロセスの直前に行われる場合に、統合プロセス全体が終了しているため、ファクトのインバウンド処理の間に、またはその後の時点である。有効なファクトが1つある場合、統合プロセスが開始する前にそれを検出するのは妥当なことである。他方で、Datalogファクトも標準の「ファクトプロバイダ」またはパートナーもしくはカスタマーによってコンパイルされたものの中にエクスポートされうるので、別の妥当な時点は、ファクトのエクスポートの前である。これにより、有効なファクトのみが確実にエクスポートされる。
【００６９】
決定性有限オートマトンを、ファクト検証に使用することができる。技術的なシステムは、イベントに基づく挙動を示しうる。つまり、これらのシステムは、特定のイベントが発生するまである状態にとどまる。その状態およびイベントに応じて、指定されたアクションで反応する。そのため、状態は、システムの「記憶」ではない。その結果、1つのイベントは2つの効果がある。一方で、これにより、機械は顕著に反応し、他方では、これにより、機械の内部状態が変化する可能性がある。
【００７０】
この概念は、ファクトを検証の問題に適用することができる。ファクトの入力により、ファクトの集合は無矛盾であるか、または矛盾するかのいずれかとなる。さらに、この問題をより細かく見ると、引数の検証は、ファクトが有効であるか、またはそうでないかを引き起こしうる。したがって、この問題は、状態の有限集合を持つオートマトンである、有限オートマトンの概念を使用して解決できる。有限オートマトンには2種類あり、それぞれ、入力を受理または拒否する、アクセプタ、または入力を読み込み、それを使用して出力を生成する、トランスデューサである。
【００７１】
ファクト問題の検証は、アクセプタオートマトンが有効なファクトを受理するか、または無効なファクトを拒否するかのいずれかのときにアクセプタオートマトンによって行われなければならない。しかし、有限オートマトンをさらに導入することができる前に、オートマトン理論の主要な概念のいくつかが提示されなければならない。アルファベットΣがあり、これは記号の有限な空でない集合である。例えば、アルファベット
Σ={a,b,c,...,z}
は、すべて小文字であることを表す。さらに、文字列とは、いくつかのアルファベットの記号の有限列のことである。文字列がゼロ個の記号からなる場合、これは、空文字列(ε)と称される。文字列wを形成する記号の量は、文字列の長さと称され、|w|で表される。例えば、空文字列|ε|の長さ=0である。任意のアルファベットΣについて、特定の長さkのすべての文字列の集合は、Σkと表される。任意のアルファベットΣについて、長さ0のすべての文字列の集合は、Σ0={ε}である。これは、長さ0の唯一の文字列が、空文字列εであることを意味する。例えば小文字のアルファベットでは、長さ2の文字列の集合は、Σ2={aa, ab, ac, ..., zz}である。アルファベットΣ上のすべての文字列の集合は、Σ*と表され、これは、
Σ*=Σ0∨Σ1∨....
と定義される。
特定のアルファベットΣに対するあるΣ*から選択されたすべての文字列の集合は、言語とも称される。いくつかのアルファベットΣについて、Lは、
L⊆Σ*
であれば、Σ上の言語である。
言語の唯一の制約条件は、すべてのアルファベットが有限であるということである。これらが有限の数の文字列を有している可能性があるとしても、言語は、1つの固定された有限のアルファベット内にある文字列のみを含むように制限される。与えられた文字列が与えられた言語の要素であるかどうかの決定は、問題と称される。ファクト検証の場合、問題は、ファクトが有効であるかどうか、つまり、それが有効なファクトのみからなる言語の要素であるかどうかを決定することである。
【００７２】
すでに上で述べたように、異なる種類のオートマトンがある。オートマトンには有限と非有限とがある。有限オートマトンの種類の1つは、決定性有限オートマトン(DFA)であり、これは、同時に1つの状態しかとりえない有限オートマトンである。何らかの入力に応答して、DFAの状態の集合から1つの状態に移る遷移がある。同時に複数の状態をとりうる非決定性有限オートマトン(NFA)とは対照的に、DFAは、1台のコンピュータ上で直接実行することができる。NFAは、実行するためには、最初にDFAにコンパイルしなければならないが、その代わりに、「高水準言語」を使用することが可能である。
【００７３】
形式的な定義によれば、DFAは以下の特性を有する。
状態の有限集合(Q)
入力記号の有限集合(Σ)
遷移関数(δ)：状態qおよび入力記号aを引数としてとり、状態pを返す関数である。したがって、δ(q,a)=pは、qからpへのaとラベル付けされた弧を記述する
開始状態(q0)： q0∈Qを満たす
有限もしくは受理状態の集合(F)： F⊆Qを満たす
【００７４】
DFA記述する一方法では、5項組
DFA=(Q,Σ,δ,q0,F)
という記法を用いる。
オートマトンを表現するために他の方法もある。ある記法は、遷移図であり、これは、Qにおけるそれぞれの状態について1つの節点を含むグラフである。さらに、Qに含まれるそれぞれの状態qとEに含まれるそれぞれの入力記号について、aとラベル付けられた、節点qから節点pへの弧がある。さらに、どの状態からの起点をも有しない、オートマトンの開始状態q0に入る1つの矢印がある。受理状態を表現する節点は、二重円でマークされ、Fに入っていない(したがって、非受理状態である)すべての状態は、単一の円でマークされる。遷移図の例が、図10に示されている。図10は、決定性有限オートマトン(DFA)の遷移図1000の概略を示す図である。DFAは、3つの状態を有する。入力に応じて、これは、利用可能な遷移を使用して、受理状態か、または非受理状態に進む。
【００７５】
3つの状態q0 1002、q1 1004、およびq2 1006のそれぞれについて、グラフ内に1つのノードがある。開始状態は、そこに入る起点を有しない矢印があるの、q0である。状態q2は、二重円によってマークされる唯一の節点であり、したがって、DFAの唯一の最終状態である。さらに、状態の間にはいくつかの弧がある。例えば、q0からq2への、aとラベル付けられた弧があり、これは遷移関数δ(q0,a)=q2を表す。図10のオートマトンは、5項組
DFA=({q0,q1,q2},Σ,δ,q0,{q2})
の記法でも表される。
DFAのアルファベットは、Σ={a,a}であり、これは、例えば、入力がaであるか、または非a(¬a)であるかのいずれかで区別される。DFAに対する遷移図において、この状態から出る、アルファベットΣからのそれぞれの入力記号に対する1つの弧があることに留意されたい。
【００７６】
上で述べたように、オートマトンは、アクセプタまたはトランスデューサのいずれかとすることができる。話をアクセプタに限れば、受理するアクションは、単一の入力記号に対してアクセプタオートマトンが入る状態によって決定されず、むしろ、文字列と呼ばれる、入力記号のリストに対して決定される。問題は、入力文字列w全体を処理した後にオートマトンが入る状態を決定することである。オートマトンの最後の状態を決定するために、拡張遷移関数を定義しなければならない。与えられた状態および与えられた入力記号に対する次の状態を決定する、遷移とは異なり、拡張遷移関数は、入力文字列に対する最後の状態を決定する。DFAの拡張遷移関数
【００７７】
【数１】
2013120605.tif 000005
【００７８】
は、入力文字列の長さに関する帰納法によって定義することができる。
【００７９】
入力記号がない場合、オートマトンは、現在の状態
【００８０】
【数２】
2013120605.tif 000006
【００８１】
である、状態qにとどまる。部分文字列xおよび最後の記号aからなる文字列wがある場合、
【００８２】
【数３】
2013120605.tif 000007
【００８３】
となる。これは、
【００８４】
【数４】
2013120605.tif 000008
【００８５】
を決定するために、部分文字列x(
【００８６】
【数５】
2013120605.tif 000009
【００８７】
である)を処理した後にオートマトンが入る状態が最初に決定されることを意味している。この状態はpと称されていると仮定すると、
【００８８】
【数６】
2013120605.tif 000010
【００８９】
となる。したがって、
【００９０】
【数７】
2013120605.tif 000011
【００９１】
は、入力記号aを持つpからの遷移の後にオートマトンが入る状態を記述する。この結果、
【００９２】
【数８】
2013120605.tif 000012
【００９３】
となる。DFA、その状態、および遷移に関する情報を使用すると、アクセプタの概念を知識検証のために提供することができる。
【００９４】
検証すべき知識は、Datalogファクトまたは他のファクトモデルを使用して記述されうる。ファクトは、統合モデルによる他のファクトに依存する可能性がある。ビジネス取引ウェブのファクトのいくつか、およびそれらの依存関係は、図11に示されている。図11は、ファクトの依存関係の抜粋1100を示すグラフである。このグラフは、他のファクトに依存するファクトの抜粋を示している。例えば、system_discxファクト1104が有効であるためには、同じキー(例えば、URI)を持つdata_discxファクト1102がなければならない。別の例は、operation_discx 1108であるが、これは、incoming_discx 1110および/またはoutgoing_discx 1112にそのconfigURlとともに依存し、また有効なdata_discxにそのoperationURIとともに依存する。さらに、1つのファクトは、2つのファクトのうちの一方、例えば、senderURlおよびreceiverURlが有効なincoming_discx 1110/outgoing discx 1112または有効なsystem_discx 1104のいずれかに依存するmessage_flow_discxに依存する。
【００９５】
図11に示されているように、他方から独立して検証されうるファクトのいくつかの「クラスタ」がある。例えば、message_flow_discx 1114を検証する場合、host_discx 1116ファクトは関連しない。しかし、system_discx 1104ファクトは、senderURIおよびreceiverURlがincorning_discx 1110/outgoing_discxまたはsystem_discx 1104のいずれかに依存するので、すべて関連する。これが、2つの構成ファクトに依存する場合、これらのファクトも、system_discx 1104などに依存する。この問題は、図12に示されている。
図12は、message_flow_dscxファクト1202の例示的な解決された依存関係の抜粋1200の図である。図12は、message_flow_discxファクト1202の検証に関連しうるファクトを示している(矢印は、「依存している」ことを意味する)。ファクトは、一方のファクトまたは別のファクトに依存することが可能である。
【００９６】
例えば、レベル2 104以上のファクトは、必ずしもより低いレベルのすべてに依存するとは限らない。その結果、検証すべきファクトの集合を、共有されているファクトが複製される場合かつその場合に限りいくつかの部分集合に分割することが可能である。例えば、operation_discx、binding_discx(図11に示されているような)、およびmessage_low_discx 1202、incoming _discx 1206、outgoing_discx 1208、system_discx(例えば、1210)、host_discx(図11に示されているような)、およびdata_discx(例えば、1212)ファクトからなる集合では、ファクトを配分する1つの可能性として、以下の部分集合Siを使用することが挙げられる(ファクト述語の_discxは、読みやすいように省かれている)。
S1=Soperation∨Sbinding∨Sincoming∨Soutgoing∨Ssystem∨Sdata
S2 = Smessage_flow∨Sincoming∨Soutgoing∨Ssystem∨Sdata
S3=Shost∨Sdata
その結果、S1、S2、およびS3は、同じ述語を持つファクトのみを含むすべてのファクト集合が前に複製されている限り互いに独立して検証されうる。
【００９７】
ファクトを検証することができるためには、その依存関係を解決する。この解決は、決定性有限検証オートマトン(DFVA)によって円滑に行われる。ファクト検証(FVA)に使用されるオートマトンは、上で説明されている有限オートマトンとまったく同様に記述することができる。これも、状態の集合(Q')、入力記号の集合(Σ')、遷移関数(δ')、開始集合(q0')、および受理状態の集合(F')を有する。このオートマトンの5項組の記述は、
FVA= (Q';Σ';δ'; q0'; F')
として示される。
しかし、この定義のいくつかの部分は、正規言語を受理する標準的な決定性有限オートマトンとは異なる仕方で解釈されうる。
Q':状態の集合。オートマトンは、引数の検証前にこれらの状態のうちの1つの状態にある。それ以降、Q'からの別の状態の前または別の状態にある場合と同じであるものとしてよい。
Σ':入力記号の集合は、有効または無効のいずれかであるものとしてよい、ファクトの引数の集合である。したがって、Σ'は、その引数が順序集合の要素であるか、またはより正確にはリストであるという制限を持つ1つのファクトとして解釈されうる。
δ':遷移関数は、1つの引数の検証を表す、つまり、これは、入力引数が有効であるかないかを判定する。
q0':ファクト検証オートマトンについては、開始状態は、オートマトンが第1の引数を検証することを開始する前に入っている状態である。
F':受理状態の集合は、すべての引数の検証に成功した後にオートマトンが入る状態である、ただ1つの状態を含む。したがって、検証の成功は、オートマトンがファクトを検証した後に受理状態に入っているかどうかを調査することによって判定されうる。qnを、ファクト検証の後にオートマトンが入っている状態とすると、
qn∈F'→ファクトは有効であり、
qn∈/ F'→ファクトは有効でない。
オートマトンの構成は、オートマトンへの正規表現(したがって正規言語)の変換の帰納的証明を使用して行われる。検証される知識は、必ずしもテキスト文字列ではない。むしろ、複合ファクトによって表され(例えば、Datalogに符号化され)うるものであり、その有効性は、人間によって指定されうるモデルによって定義される。したがって、このアプローチは、場合によっては、より強力な言語に拡張されなければならない。
【００９８】
言語の生成能力は、形式文法に分類することができ、これらが記述する言語は、4つのカテゴリに分類することができる。文法Gは、4個組(V,Σ,P;S)と定義される。
Vは、非終端記号の集合である(つまり、ある種の規則を使用して終端記号によって置き換えられうる変数)。
Σは、それ以上置き換えることができない終端記号のアルファベットである。これらは、言語の基礎である。
Pは、左辺と右辺とからなる生成規則の有限集合である。左辺は、非終端記号からなり、右辺は、終端記号または非終端記号または両方の組み合わせからなるものとしてよい。生成規則は、数式と似ており、右辺は、式の左辺に代入される。一般に、l→rと表記される。
Sは、英文法の開始記号である。文法の定義は、この記号から開始する。他のすべての記号については、生成規則を使用して非終端記号を終端記号で次々に置き換えることができるときに横断してゆくことによって到達する。
上で述べたように、4種類の文法がある。
0型:無制限文法:この型の文法は、上記の定義にかかるすべての文法を含む。
1型:文脈依存文法:この型の文法は、0型文法でもある。しかし、それぞれの生成規則l→rは、条件|l|≦|r|を満たさなければならない。その結果、生成規則を適用した後、導出される文字列は、前のものよりも短くはなりえない。
2型:文脈自由文法:2型の文法は、文脈依存であるが、どの生成規則の左辺も、ただ1つの非終端記号で成り立っていなければならない。したがって、すべての生成規則l→rについて、l∈Vが成り立つ。1型および2型の文法は、コンパイラの設計および製作に使用される。さらに、大部分のプログラミング言語の構文は、文脈自由文法によって記述することができる。
3型:正規文法:すべての正規文法は、文脈自由文法である。さらに、それぞれの生成規則の左辺は、非終端記号から成り立っていなければならない。しかし、生成規則の右辺は、空文字列εまたはΣからの終端記号から成り立っていなければならず、この後にVからの非終端記号が続く場合も続かない場合もある。したがって、右線形正規文法のそれぞれの生成規則1→rの形は、
l∈Vかつr∈{ε}∪Σ∪ΣV
で形式的に特徴付けられる。
一般に、プログラミング言語の語彙構造は、3型文法を使用して定義することができる。その結果、Lnが、n型の文法によって構成される言語を記述する場合、これら4種類の文法の関係は
L0⊃L1⊃L2⊃L3
と記述することができる。
言語の能力は、0型から3型へと減少する。したがって、2型言語(文脈自由文法の言語)は、3型文法を有する正規言語の拡張である。しかし、オートマトンの構成のためには、これが、正規言語のみを受理すると仮定されるが、それは引数の内容が単純な文字列であるからである。しかしながら、構成されたオートマトンは、ファクトの依存関係を解決するためにいくつかの高度な機能を有している場合がある。
【００９９】
非決定性有限オートマトン(NFA)は、一度に複数の状態をとりうる有限オートマトンである。これにより、その入力に関して何かを「推測する」ことが可能になる。例えば、ファクトがさらに多くの引数を有している、または有していないと「推測する」ことができる。NFAに関して興味深いのは、これらが、対応するDFAに比べて設計が容易になる場合があるとしてもDFAと同じ言語を受理できることである。NFAの定義は、DFAの定義に類似しており、
NFA=(Q;Σ;δ;q0;F)
である。
【０１００】
さらに、正規表現を処理するNFAの言語は、
【０１０１】
【数９】
2013120605.tif 000013
【０１０２】
として定義される。つまり、L(NFA)は、拡張遷移関数
【０１０３】
【数１０】
2013120605.tif 000014
【０１０４】
が少なくとも1つの最終状態を含み、最終状態の集合が空でないようなΣ*内の文字列wの集合である。NFAとDFAの主な違いは、遷移関数δが返す値の型である。DFAは1つの状態を返すが、NFAは状態の集合を返す。さらに、それぞれの状態から出る遷移がなくてもよく、これは、状態列が「死んでいる」可能性があることを意味する。しかし、拡張遷移関数は、1つの状態の次の状態が最後の入力記号でラベル付けされているこの状態から出るすべての弧に従うことによって決定されることを除き、DFAに類似している。
【０１０５】
NFAおよびDFAの違いを考えると、両方が同じ言語をどのように受理することができるかという疑問が生じる。上で述べたように、NFAによって記述されるすべての言語は、最悪の場合であっても、ある種のDFAによって記述することもできるが、DFAは、対応するNFAよりも多くのjほうたいを有する。通常は、DFAは、NFAとほぼ同じ数の状態を有するが、さらに多くの遷移を有することができる。与えられたNFAに対する対応するDFAを見つけるために、部分集合構成と呼ばれるプロシージャを使用しなければならない。部分集合構成の基礎は、NFA N=(QN;Σ;δN;q0;FN)である。この目的は、L(D)=L(N)となり、両方のオートマトンのアルファベット(Σ)が同じになるようにDFA D=(QD;Σ;δD;{q0};FD)を構成することである。部分集合構成の主な考え方は、DFAの構成された状態がNFAの状態の集合であるというものである。例えば、Dの開始状態は、Nの開始状態を表す集合に含まれる唯一の状態である。Dの他の要素の構成は、次のようにして行われる。
DFAの状態の集合QDは、QNの部分集合の集合である。QNがn個の状態を有する場合、QDは2n個の状態を有する。しかし、アクセス不可能な状態が「ゴミになっている」可能性があるので、その開始状態から到達できない状態がQD内にある。これは、遷移図には示されないことを意味する。その結果、QD内の状態量は、2nよりかなり小さくなることがある。
受理状態の集合FDは、DFAの1つまたは複数の、ただし、少なくはない、状態を含むNFAの部分集合の集合である。したがって、FDは、S∩FN≠φとなるようなQNの部分集合Sの集合である。
QNの部分集合および与えられた引数aからδDを計算するために、部分集合からの1つの状態がaとラベル付けされている弧上で入るすべての状態の和集合を取る。より形式的には、それぞれの部分集合S_QNについて、またΣ内のそれぞれの入力記号について、
【０１０６】
【数１１】
2013120605.tif 000015
【０１０７】
が決定される。
部分集合構成は、通常、遷移表を使用して行われる。しかし、これは時間が非常にかかるように思われるので、「遅延評価」と呼ぶアプローチを使用し、部分集合に対して実行することができる。
1.NFAの開始状態のみからなり、開始時点ではアクセス可能である単元集合がある。
2.それぞれの入力記号aについてアクセス可能な状態の集合Sを決定した後、状態の集合δD(S; a)を計算する。これらの状態も、すべての同様にアクセス可能である。
ε-非決定性有限オートマトン(ε-NFA)は、上で説明されているNFAと同様にして
ε-NFA = (Q;Σ;δ;q0;F)
と定義される。
定義のすべての構成要素は、2つの引数をとる関数となっている、δを除き、NFAと同じように解釈することができる。最初に、Qから、このオートマトンの「元になっている」状態である、1つの状態を取り出す。第2に、アルファベットからの入力記号、または記号Σである、S∪{ε}の要素をとる。この定義では、空文字列であるεは、アルファベットΣの要素ではない。
【０１０８】
いわゆるε-遷移は、ε-NFAが次の状態に、自然発生的に、つまり、入力なしで、進むことを可能にする。この可能性は、オートマトンによって受理される言語を変えないが、オートマトンの構成に何らかの「便宜」をもたらす。例えば、オプションの入力記号をこの方法でモデル化することができる。
【０１０９】
しかし、新しい入力記号があると、それらを取り扱うための新しいプロシージャもある。したがって、拡張遷移関数を定義するためにε-クロージャを導入する必要がある。形式的に、ε-クロージャは、再帰によって定義される。
基底:状態qは、ENCLOSE(q)内にある。
帰納ステップ:状態pが、ENCLOSE(q)内にあり、pからεとラベル付けされた別の状態rへの弧がある場合、rはENCLOSE(q)内にある。したがって、ENCLOSE(q)は、δ(p,ε)内のすべての状態も含む。
【０１１０】
これは、状態のε-クロージャが、εと排他的にラベル付けされた弧によりこの状態から到達できるすべての状態を含むことを意味する。標準のNFAと同様に、ε-NFAの拡張遷移関数は、オートマトンがアルファベットΣからの記号からなる文字列wの入力に対して行う内容を反映する。したがって、
【０１１１】
【数１２】
2013120605.tif 000016
【０１１２】
は、εがw寄与しない場合のラベルがwを形成するパスにそって到達する状態の集合である。
【０１１３】
ファクト検証のためのε-NFAの構成では、DFA、NFA、およびε-NFAに関する知識を利用することができ、ファクトを検証するオートマトンを設計することが可能である。以下の帰納法は、ε-NFAを構成し、ファクトを検証することができる。
定理:ファクトを検証するε-NFAが存在する。
証明:この帰納法により、ファクトを検証することができるε-NFAが存在することを証明する。このε-NFAは、以下の特性を有する。
1. ちょうど1つの受理状態。
2. 初期状態に入る弧はない。
3. 受理状態から出る弧はない。
それぞれのファクトは少なくとも1つの引数を有し、他のファクトに応じて引数のないファクトは少なくとも1つあると仮定して、オートマトンの入力に対する構造帰納法によって証明を行う。
【０１１４】
引数は2種類あり、1つは通常の引数、もう1つは検証されるファクトのレベルよりレベルが低いファクトに依存する引数である。これらの2種類の引数は、図13に示されている。図13は、2種類の引数検証のグラフ表現1300である。引数検証は2種類あり、第1の種類は、通常の引数であり、第2の種類は、別のファクトに依存する引数である。オートマトンの基本入力は、検証すべき引数であると仮定する。
【０１１５】
入力が通常の引数であれば、オートマトンは、引数が有効である場合かつその場合に限り第1の状態1302から次の状態1304に進む。その一方で、他のファクトに依存する引数は、下位レベルのファクトが有効である場合かつその場合に限り有効である。無効である場合、引数も無効である。したがって、下位レベルのファクトは、遷移関数で検証されなければならない。このファクト検証は、有効なファクトに対して状態1308から1310に遷移する図13の点線の辺によって示される。辺が点線であるのは、このオートマトンでは複数の初期状態と1つの最終状態がありうるからである。
【０１１６】
ファクトの引数の量nに応じて異なる場合が2つある。図14は、ファクト検証のグラフ表現1400である。ファクトのそれぞれの引数について1つの引数検証がある。
n=1:ファクトが引数を1つしか有しない場合、この引数は検証される。図14の点線の辺は、有効な引数の入力上の状態1402から1404への遷移を表す。これは、ただ1つの引数であるので、オートマトンは、ε-遷移を使用してその最終状態1406に自然に移る。その一方、引数が無効である場合、オートマトンは、引数検証ボックスの第1の状態1402内にとどまる。
n>1:第1の引数について、オートマトンは第1の場合のように振る舞う。しかし、第1の引数が検証された後、オートマトンは、e-遷移を使用して引数検証ボックス内の第1の状態1402に進み、次の引数を検証する。
【０１１７】
両方の場合において、1つの引数が無効になるやいなや、オートマトンは、非最終状態のどれかで動かなくなる。続く引数が有効であるか有効でないかに関係なく、オートマトンはその最終状態にもはや到達できない。したがって、受理状態は、ファクト検証の成功を示す指標として解釈されうる。
【０１１８】
ファクトは、引数のリストからなるので、ファクトの検証は、このリストの検証を含む。引数は、必須であるか、またはオプションであるものとしてよい。後者の場合、検証は、ε-遷移によってスキップされる。しかし、引数が必須である場合、通常のファクトの検証(通常の遷移)、または別のファクトに依存するファクトの検証がある(小さな「ファクトの検証」ボックス)。1つの引数が有効でなくなるやいなや、オートマトンは、その状態で動かなくなり、最終状態にはもはや決して到達しない。上記の帰納法で構成された完全なε-NFAは、図15に示されている。図15は、ファクトを検証するため完全に構成されたε-NFAのグラフ表現1500である。この図は、ファクトボックス1502の検証を引数ボックス1504のリストの検証内に埋め込むことを示している。ファクトボックス1502の検証は、2つの状態1506および1508を含む。点線は、複数の初期状態および1つの最終状態の可能性があることを示すための線である。オートマトンは、ε-遷移を使用して状態1510に戻り、次の引数を検証する。
【０１１９】
与えられたファクトをその入力として持つオートマトンの最終状態1512を決定するために、構成されたε-遷移は、対応するDFAに最初に変換されなければならない。これは、部分集合構成によって行われる。部分集合構成の基底であると仮定されるオートマトンは、図16に示されている。図16は、部分集合構成に使用されるファクト検証ε-NFAのグラフ表現1600である。これは、図14と同じオートマトンであるが、その状態は、一意的に識別するためにアルファベット順に命名されている。
【０１２０】
部分集合構成を適用すると、対応するDFAの第1の状態は、εーNFAの開始状態およびこの状態以降からε-遷移によって到達できるすべての状態を含む状態の集合である。したがって、DFAの開始状態の集合は、状態a 1602およびb 1604を含む。入力が有効な引数である場合、ε-NFAは、状態b 1604から状態c 1606に進む。c 1606から、ε-遷移によって状態b 1604およびd 1608に到達できる。したがって、DFAの次の状態は、状態b 1604、c 1606、およびd 1608を含む。この状態から、オートマトンは他の有効な引数の入力上の同じ状態に進む。有効な引数のみがあった場合、検証の最後に、最後のε-遷移を使用してε-NFAはその受理状態に進む。したがって、DFAの状態{b,c,d}は、受理状態である。
【０１２１】
第1の引数が無効である場合、ε-NFAは、そのε-遷移を使用して状態bに進む。次いで、入力が有効な引数である場合には状態cにしか進みえないので、この状態にとどまる。したがって、対応するDFAは、非受理状態である、状態{b}に進む。これは、続く引数が有効であろうとなかろうと、この状態にとどまる。すべての前の引数が有効であったが、次の引数は有効でない場合、ε-NFAは状態bにとどまる。したがって、DFAは、再び、{a,b} 1706から状態{b} 1704に進む。そこで、ファクトは、第1の引数であろうと他の引数であろうと、無効な引数の入力上で無効となる。構成されたDFAが、図17に示されている。図17は、部分集合構成によって生成されるファクト検証DFAのグラフ表現1700である。オートマトンは、ファクトが有効な引数のみからなる場合に{b,c,d} 1702、または少なくとも1つの引数が無効である場合に{b} 1704のいずれかでファクト検証を終了する。
【０１２２】
DFAをε-NFAから構成した後の拡張遷移関数について、両方のオートマトンがファクト検証に関して等価であるかどうかという疑問が生じる。検証DFAは、ε-NFAと全く同様に、少なくとも1つの引数を持つファクトを受理する。両方のオートマトンのファクト検証の成功は、これらがその検証を終了する際に入っている状態によって表される。しかし、与えられた引数について、どの状態がこの最後の状態であろうか?オートマトンが検証を終了する際に入っている状態を決定するために、拡張遷移関数を使用しなければならない。文字列を処理する、通常のDFAとは異なり、検証DFAはDatalogファクトを処理する。しかしながら、拡張遷移関数
【０１２３】
【数１３】
2013120605.tif 000017
【０１２４】
は、文字列の代わりにファクトを、記号の代わりに引数を使用することによって同様に定義される。
基底:オートマトンが検証を開始していなかった場合、つまり、検証すべきファクトがない場合、これは、それがたった今入っている状態である、状態qにとどまり、
【０１２５】
【数１４】
2013120605.tif 000018
【０１２６】
である。
帰納ステップ:n>=1、a1, ::,an-1,anがファクトの引数であるとして、ファクトf(a1,.::,an-1,an)がある場合:
【０１２７】
【数１５】
2013120605.tif 000019
【０１２８】
となる。
【０１２９】
これは、
【０１３０】
【数１６】
2013120605.tif 000020
【０１３１】
を決定するために、
【０１３２】
【数１７】
2013120605.tif 000021
【０１３３】
である、すべての引数をan-1まで処理した後にオートマトンが入る状態が最初に決定されることを意味している。この状態はpと称されていると仮定すると、
【０１３４】
【数１８】
2013120605.tif 000022
【０１３５】
となる。
【０１３６】
したがって、
【０１３７】
【数１９】
2013120605.tif 000023
【０１３８】
は、引数anを持つpからの遷移の後にオートマトンが入る状態を記述する。この結果、
【０１３９】
【数２０】
2013120605.tif 000024
【０１４０】
となる。
【０１４１】
そこで、拡張遷移関数
【０１４２】
【数２１】
2013120605.tif 000025
【０１４３】
は、
【０１４４】
【数２２】
2013120605.tif 000026
【０１４５】
として定義することができ、これは、ファクトを検証するオートマトンの最後の状態を決定するために、ファクトの最後から2番目の引数の検証の後にオートマトンが入っている状態を最初に決定しなければならないことを意味している。
【０１４６】
次に、拡張遷移関数の定義後の検証DFAおよびε-NFAの等価性については、DFAおよびε-NFAの等価性を証明することが可能である。したがって、両方のオートマトンが同じ言語を受理することが示されなければならない。
証明:E=(QE;f,δE;a;FE)をε-NFAとし、D=(QD;f,δD;a;FD)をqDが部分集合構成によって生成されるDFAの開始状態である場合とする。DFAに対してL=L(D)、ε-NFAに対してL=L(E)であると仮定すると、
L(D)=L(E)
であることを示すことができる。
【０１４７】
これは、ファクトf(a1,a2,...,an)の入力に対する両方のオートマトンの拡張遷移関数が同じである、つまり
【０１４８】
【数２３】
2013120605.tif 000027
【０１４９】
を示すことによって行われる。
記号aは、ε-NFAの開始状態を表していることに留意されたい。fが、少なくとも1つの引数aiからなり、この引数が、有効である(avalidとして表される)か、または無効である(ainvalid)かのいずれかとすることができると仮定すると、オートマトンの等価性は、引数の量に関する帰納法によって示される。
基底:最初に、1つの単一引数を持つファクトの入力を仮定する。引数の有効性に応じて、検証は成功か、そうでないかのいずれかとなる。
1. 引数が有効である場合、ε-NFAは、b(ε-遷移を使用してaから進んだ先)からcに進む。そこから、ε-遷移を使用して、bおよびdに進むこともできる。ただ1つの入力引数があると仮定されているので、ε-NFAは、dにおいて有効なファクトの検証を終了する。DFAは、有効な引数の入力上で{b,c,d}に進む。両方のオートマトンが検証を終了する際に入っている状態は、両方とも受理状態であり、したがって、検証は成功である。
2. しかし、入力引数が無効である場合、ε-NFAは、ε-遷移を使用してaから進んだ先である、非受理状態bにとどまっている。DFAは、{b}に進む。両方のオートマトンが非受理状態において検証を終了し、したがって、検証は不成功であったということであり、ファクトは無効である。
両方の場合において、両方のオートマトンの検証の結果は同じである。したがって、単一引数を持つファクトの入力について、これらのオートマトンは等価である。
帰納ステップ:複数の引数を持つファクトの入力を仮定する。ファクトの有効な引数と無効な引数の異なる群が生じうる。
1. 第1の引数は無効であり、多数の有効なまたは無効な引数が続く。この場合、続く引数が有効であろうとなかろうと問題にならない。ε-NFAは、中で動けなくなり、DFAが{b}にとどまっている間、ファクトの検証を停止する。
2. 第1の引数は有効であり、1つまたは複数の有効な引数が続く。ファクトのすべての引数が有効である場合、ε-NFAは、常に、引数検証にbからcへの遷移を使用する。検証すべき引数がまだある限り、cからbに戻るε-遷移を使用する。もう引数がなければ、自然に、受理状態である、dに進む。DFAは、任意の数の有効な引数の入力上で、受理状態である{b,c,d}に進む。
3. 第1の引数は有効であり、1つの無効な引数が続く。この場合、ε-NFAは、非受理状態bにとどまるが、DFAは、非受理状態{b}にとどまる。
4. 第1の引数は有効であり、第2の引数は無効であり、次の引数は、有効または無効のいずれかである。これが生じた場合、両方のオートマトンは、3で説明されているように振る舞う。
両方のオートマトンが複数の引数を含むファクトのすべての場合において同じように振る舞うので、これらは等価である。その結果、DFAは、ファクト検証に使用することができる。
【０１５０】
実装の選択について、以下で説明する。オートマトンの実装は、構造的およびオブジェクト指向アプローチを含む。構造的アプローチでは、オートマトンの状態は、整数変数として実装される。変数は、実際の状態を保存するために使用される。ファクトを検証するときに、実際の状態を最初に探索し、それに応じて、検証を実行する。例えば、以下は、構造を使用してdataファクトを検証するオートマトンのクラス図を示す。
【０１５１】
【表３】
2013120605.tif 000028
【０１５２】
それぞれの引数(つまり、状態)について、整数引数が1つある。実際の状態は、actualState変数内に保存される。goToNextStateメソッドで、遷移関数が実装される。
【０１５３】
dataファクトのそれぞれの引数について、整数定数によって表される1つの状態がある。その時点においてオートマトンが入っている状態は、actualState整数変数内に保存される。遷移関数は、実際の状態を探索し、実際の状態に(および引数にそれぞれ)応じて対応する遷移を実行するgoToNextStateメソッドで実装される。同じ構造(つまり、述語)を持つファクトしかない場合、このアプローチはうまく機能する。しかし、述語の数が増えると、維持すべきオートマトンの量も増大する。さらに、ファクトの引数構造が変化した場合、goToNextStateメソッドもまた、正しい引数検証が確実に行われるように調節されなければならない。例えば、dataファクトの引数データおよび出所を異なる方法で検証するとする。依存関係のモデルにおいてこれら2つの引数を切り替える場合、クラス全体(整数定数および遷移関数を含む)も同様に変更しなければならない。さらに、多くの引数が同様にして検証されうる。例えば、dataファクトのデータ、コンテンツの型、および出所は、すべて、特別な制限のないオプション引数である。しかし、遷移関数は、引数に依存するので、3回(引数毎に1回)実装されなければならない。そのため、このアプローチに対する保守労力は非常に大きなものとなる。
【０１５４】
そのため、保守労力を軽減し、可読性を改善するために状態を再利用できる技術があるかどうかが問題となる。これらの問題を解決する一方法は、オブジェクト指向アプローチのメインアイデアである、遷移を複数の状態にカプセル化するというものである。さらに、これらの状態は、検証のためのオートマトンと同じ共通インターフェースを有することができる。したがって、引数が検証されることが想定されている場合、オートマトンは検証を実際の状態にデリゲートする。設計パターンに関していえば、文脈がFVAであり、具体的状態は検証をモデル化するために必要とされるすべての状態である。それぞれの状態の遷移関数は、オートマトンが進むべき次の状態を返す。しかし、オートマトンは次の状態に進む制御権を有するが、これは実際の状態によって「示唆される」状態である場合も、ない場合もある。設計パターンの実装の主要な利点は、保守性と再利用性が改善されていることである。特に、類似の特性(例えば、そのオプション性)を持つ複数の引数を有する依存関係のモデルのファクトに対しては、1つの状態実装を同じ特性を持つすべての引数に対して、それらがどのファクトに属していようと、再利用することができる。オブジェクト指向アプローチの保守性および再利用性は、構造的アプローチに勝っているので、これ以降オブジェクト指向アプローチを基本とする。その結果、遷移関数は、特定の状態に付随することになる。さらに、オートマトンは、1つのファクト型(つまり、同じ述語を持つファクト)を検証することができるだけでなく、むしろ、異なる述語を持つ多くのファクトを検証することができる。
【０１５５】
上で述べたように、それぞれの引数は、引数がオプションであるか、必須であるかを指示する基数を有する。したがって、1つの状態の遷移関数は、引数の検証をスキップしなければならない。しかし、引数が必須である場合、これは検証されなければならない。
【０１５６】
それが単純引数である場合、遷移関数は、それが指定されている(つまり、空でない文字列)か、そうでないかをチェックするだけでよい。しかし、引数が、下位レベルのファクトを参照するURIである場合、このファクトもまた検証されなければならない。したがって、以下の状態が実装されている。
引数検証:この状態の遷移関数において、引数は明確に検証され、それが指定されているかどうかをチェックする。引数が空文字列を含む場合、遷移関数は、オートマトンがその時点に入っている状態を返す。そうでない場合、次の状態を返す。
スキップ引数検証:この遷移関数は、引数があることを単に認識するだけであり、それを検証しない。引数が空文字列であろうとなかろうと問題にならない。したがって、この遷移関数は、常に、次の状態を返す。
特定のファクトの特定の引数の検証:この遷移関数では、ファクト特有の、また引数特有の検証が実装される。例えば、255文字未満の空でない文字列として定義される、systemファクトの名前を検証するだけの1つの遷移関数がある。
エラー状態:この状態は、任意の種類の予想外の入力を表す。例えば、与えられたファクトに対するファクトモデルを見つけられない場合、オートマトンの開始状態は、この状態となる。ファクトに、対応するモデルよりも多い引数がある場合、この状態は、オートマトンの最後の状態である。いずれの場合も、オートマトンがこの状態に入ると、ファクトはもはや有効とはなりえない。その結果、この状態の遷移関数は、任意の入力上で同じ状態を返す。
ファクト検証:この遷移関数は、実際のファクトが依存するすべてのファクトを検証しなければならないので最も高度な関数である。この機能について、以下でさらに詳しく説明する。しかし、オートマトンの遷移関数に至ったときには、検証オートマトンがより強力な遷移関数を有するので標準のDFAとはいくつか異なる点がある。これは、オートマトンが受理する言語の、正規言語から2型言語への拡張の結果である。その結果、検証オートマトンの遷移関数は、以下のことを実行しなければならない複雑な関数である。
1. 引数が空でない文字列であるかどうかをチェックする。
2. 引数の検証をスキップして、何も実行しない。
3. ファクト特有の、および引数特有の何らかの検証を行う(例えば、システム名が255個以下の文字からなる空でない文字列かどうかをチェックする)。
4. ファクトのURIを検証する、つまり、対応する下位レベルのファクトが存在するかどうかをチェックする。
5. すべての場合において、検証が成功した場合には検証オートマトンの次の状態を返し(以下のアルゴリズム4を参照)、上で述べた検証のどれかが失敗した場合にはエラー状態を返す。
遷移1から3までは引数文字列の長さに関する単純な検査であるが、遷移4は、別のFVAのコールを含むのでより複雑である。一般に、遷移関数およびその状態は、Java(登録商標)で実装される。したがって、変数宣言、条件、およびループなど、あらゆる種類のJava(登録商標)構成体を使用することが可能であるだけでなく、他のFVA、RFC、またはSAPシステムへのアクセスのコールを使用することも可能である。これと、Java(登録商標)が文脈自由言語であるというファクトから、結果として、オートマトンは文脈自由という性質を有する。しかし、これは、それでも、検証の終了を保証するために、使用されるJava(登録商標)構成体の数が、変数宣言、条件、および有限ループに限られているので正規言語を受理するDFAである。他の構成体は、終了しない場合があるので、使用すべきでない。例えば、RFCは、リモートロケーション上でフリーズする可能性がある。したがって、応答がなくなり、オートマトンは遷移関数内にとどまり、したがって実際の状態にとどまる。ファクトは、RFCが失敗したというだけで、正しい可能性があるとしても、拒否されることもありうる。したがって、この実装には、そのような「安全でない」構成体はない。この制限により、それぞれのオートマトンのコールが終了することが保証される。その結果、遷移関数における別のオートマトンのコールも、ファクトモデルが正しく構成されている、つまり、異なるファクトモデル間に循環参照がない限り、クリティカルでない。
【０１５７】
すべてのファクトは、セマンティックモデルでモデル化され、いったん構成されると、これはファクトの依存関係を表す。抽象ファクトおよび引数モデルは、図18に示されている。図18は、セマンティックモデル1800のグラフ図である。このクラス図は、セマンティックモデル1800を示している。ファクトモデルは、多数の引数モデルからなる。一般に、セマンティックモデルは、上で説明されている統合モデルである、領域モデルの部分集合である。より正確には、セマンティックモデルは、統合モデルのEDB(つまり、データベース)表現である。
【０１５８】
ファクトモデルは、述語とファクトのアリティとに関する情報を含む。引数モデルのリストは、名前によって識別される、引数モデルからなる。基数は、引数がオプション(値0で表される)であるか、または必須(1)であるかを指示するものである。isRef変数は、引数が参照の集合(refSet)に含まれる、他のファクトに依存するかどうかを指示する。さらに、それぞれのファクトモデルは、ファクトを一意に識別する引数を指定するキー値を有する。最後に、それぞれのファクトは、FVAが通る、状態のリスト(stateList)を有する。
【０１５９】
情報は、検証特有の情報であり、そのため、ファクトを検証したいユーザーは、それらを指定しなければならない。そこで、外部ドメイン固有言語(DSL)が開発された。一般に、DSLは、特定の領域に絞られた限定された表現力を持つコンピュータプログラム言語である。さらに、外部DSLは、主プログラムの言語から分離されている。外部DSLは、カスタム構文を有するか、または他の言語(多くの場合、XML)とすることができる。この場合、カスタム言語が定義されている。定義ファイルは、セマンティックモデルを記述するようにDSLで書かれていなければならない。定義ファイルを作成し、修正し、使用するプロセスについては、上で説明されている。
【０１６０】
一般に、検証オートマトンは、1つのファクトを検証することができるだけではなく、ファクトの集合を検証することもできる。実際、通常のユーザーは、むしろ、単一のファクトの検証よりもファクトの集合の検証を必要としているが、ファクト検証を必要とする主な理由は、ファクトの依存関係にある。単一のファクトを検証は、オートマトンそれ自体によってもっぱら使用される。したがって、検証プロセスは、検証オートマトンが与えられたファクトの集合を検証するプロセスとして定義される。
【０１６１】
いくつかの準備を考える。例えば、セマンティックモデルの作成は、検証フレームワークの多くのコンポーネントによって必要とされる。したがって、検証フレームワークが開始したときに、定義ファイルが解析され、セマンティックモデルが作成される。上で述べたように、ファクトモデルは、引数に関する情報を含むだけでなく、特定のファクトを検証するためにオートマトンが必要とする状態リストも含む。状態リストの作成は、アルゴリズム1において示されており、これは、ファクトの依存関係を解決するために対応するファクトモデルを入力として必要とする。アルゴリズム1は、ファクトに対する状態リストを決定するための例示的なアルゴリズムである。
【０１６２】
すべての引数モデルについて、第1のステップは、引数がオプションであるかどうかをチェックすることである(2行目を参照)。この場合、引数の検証をスキップする必要がある。引数が必須である場合、次のステップは、引数が他のファクトモデルを参照しているかどうかをチェックすることである(5行目を参照)。他のファクトへの参照がない場合、このアルゴリズムは、特定の命名を有する、ファクト特有および引数特有の状態を探索する。そのような状態がある場合、アルゴリズムはそれを選ぶ(7行目)。そうでない場合、これは、引数検証のためにデフォルトの状態を使用する(9行目)。しかし、下位レベルのファクトへの依存関係がある場合、ファクト検証に対する状態が追加される(12行目)。最後に、すでに決定されている、受理状態が、状態リストに追加され(15行目および17行目)、状態リストが返される(18行目)。
【０１６３】
次いで、オートマトンの準備しなければならない。これは、ファクトを検証できるようになる前にある種の情報を必要とすることを意味する。これは、ファクトを検証するときの文脈を必要とする。一般に、ファクト集合は、同じ述語を有するファクト、または有しえないファクトを多数含む。ファクトが同じ述語を有していない場合、これらは互いに依存していることがある。後で検証されるファクトの集合は、文脈または文脈それ自体の部分集合である。
ValidationFactSet⊇Context
例えば、文脈Cが、それぞれが対応するdataファクト(DSおよびDH)を有するsystemファクト(S)およびhostファクト(H)を伴うruns_onファクトRからなるファクト集合であるものとすると、次のようになる。
C={R, S, H, DS, DH}
この文脈の部分集合である、ファクト集合S1は、
S1 = {S}
であるものとしてよい。
すべてのファクトの引数が有効である場合、ファクト集合S1も有効であるが、それは、systemファクトについては、文脈内に対応するdataファクトがあるからである。次に、別の部分集合S2を
S2= {R, I}
とする。
ただし、Iは、インカミング構成ファクトである。ファクト集合S2は、すべてのファクトの引数が有効であるとしても、有効にはならないが、それは、インカミング構成のconfrgURIとマッチするdataファクトDIがないからである。最後のファクト集合S3を
S3={R,S,H,DS,DH)=C
とする。
ファクト集合S3は、ファクト集合それ自体の中に対応する下位レベルのファクトがあるので、有効となる。したがって、オートマトンは、文脈内のファクトの集合を検証することができるだけでなく、文脈全体を検証することもできる。
【０１６４】
検証ファクト集合において、文脈内の他のファクトに応じて多数のファクトがありうる。その結果、ファクトを検証するために異なる戦略がある。第1の可能なアプローチは、ランダムアプローチであり、このアプローチでは、ファクトは、検証されるべきファクトの集合から取り出されるときに検証される。しかし、依存関係の階層においてファクトのレベルを使用して検証順序を決定する他のアプローチが2つある。レベルの計算は、ファクトモデル上で適用される再帰関数である(アルゴリズム2を参照)。アルゴリズム2は、ファクトモデルのレベルを決定するための例示的なアルゴリズムである。
【０１６５】
デフォルトのレベルは、0である(1行目)。ファクトモデルのレベルを計算するために、実際のファクトモデルが依存する、それぞれのファクトモデルのレベルに1を加える(9行目)。次いで、その和を現在までに求められた最上位のレベルと比較する。和が求められた最上位レベルより高い場合、これを新しいレベルとみなす(11行目)。すべてのファクトモデルについて反復した後、計算されたレベルが返される(18行目)。計算されたレベルは、2つの異なる検証アプローチに使用することができる。上位レベルのファクトを最初に検証することができる。これは、トップダウンアプローチと呼ばれる。
【０１６６】
上位レベルのファクトが検証される場合、それが依存するファクトが、依存するファクトの検証中に検証される。例えば、systemファクトの検証中に、対応するdataファクトが存在しているかどうかをチェックする必要がある。この検査中に、dataファクトを検証するオートマトンがコールされる。これは、対応するdataファクトを検証し、それが有効であれば、次の状態を親(システム)オートマトンに返す。したがって、下位レベルのファクトの大半は、上位レベルのファクトの検証中に検証される。それとは対照的に、ボトムアップアプローチがあり、この場合は、下位レベルのファクトが最初に検証される。したがって、上位レベルのファクトが検証される場合、それらが依存するファクトは、再度検証されなくてよい。これらはスキップされる。
【０１６７】
トップダウンおよびボトムアップアプローチが、効果的に使用されると想定される場合、共有メモリを使用しなければならない。図19は、共有メモリ1902の例示的な実装1900を示す概略図である。無効なファクトを格納する、ローカルメモリ1906に加えて、それぞれのFVA(例えば、FVA1 1904)は、共有メモリ1902の一部を使用して有効なファクトを格納する。これらのスポットは、複数のオートマトンによっても使用できる。実装される共有メモリは、すでに検証が済んでいるすべてのファクトの格納を円滑にする。その結果、それぞれのFVAは、それが使用すると想定されている共有メモリ1902の部分のIDを必要とする。これにより、共有メモリ1902のこの部分にすべての有効なファクトを格納することが可能になる。下位レベルのすでに検証済みのファクトのどれかが再び検証されると想定される場合、オートマトンはこの検証をスキップすることができる。したがって、サブオートマトンがコールされるときにはいつでも、共有メモリ1902のセクションのIDを入力として受け取る。その結果、親オートマトンが使用する共有メモリ1902の同じ部分にもすべての有効なファクトを格納する。これにより、異なるオートマトンの間に分散されるファクト検証が円滑に行える。さらに、それぞれのオートマトンは、ローカルメモリ1906を有し、そこに、検証に成功しなかったすべてのファクトを格納する。その結果、無効なファクトを再び検証することが想定される場合に、オートマトンは、このファクトが無効であることをすでに「知っている」ため、検証をスキップすることができる。
【０１６８】
オートマトンが必要とするすべての情報を取得した後速やかに、ファクトの集合の検証を開始することができる。上で述べたように、与えられたアプローチを使用してそれを行う。このアプローチでは、検証の順序を決定し、オートマトンが、このアプローチによって定義される順序でファクトを次々に検証してゆく。しかし、実際の検証が開始できる前に、ファクトを検証するために必要なすべての条件が満たされているかどうかをチェックする、何らかの前処理を行わなければならない(アルゴリズム3を参照)。
【０１６９】
アルゴリズム3は、ファクト検証に対する前処理を行うための例示的なアルゴリズムである。開始時に、オートマトンは、実際のファクトの検証をスキップできるかどうかをチェックするが、それは、共有メモリに格納されており、したがって前に検証されているからである(2行目)。そうでない場合、オートマトンは以下を確認する。
ファクトが以前に無効であるとマークされていない。
ファクトと同じ述語を有するファクトモデルがある。
ファクトは、少なくとも1つの引数を有する。
ファクトのアリティは、引数の数に等しい。
このエラーチェックは、アルゴリズム3の5行目に示されている。最後のステップは、オートマトンの開始状態を決定し(8行目)、設定する(9行目)ことである。開始状態の決定は、アルゴリズム4に示されている。
【０１７０】
アルゴリズム4は、オートマトンに対する次の状態を決定するための例示的なアルゴリズムである。一般に、引数リスト内のインデックスiを持つそれぞれの引数aiについて、i=jとなるような対応する遷移関数を含む状態リスト内の状態Sjがある。これは、次の引数を検証する遷移関数を含む状態を取得するために、インデックスが実際の引数のインデックスより1だけ高い、状態Sj=I+1を返す(3行目)。i=jとなるような引数aiに対して状態Sjがない場合、これは、ファクトに、対応するファクトモデルより多い引数があるか、またはオートマトンがすでにその最終状態に入っており、したがってより多くの引数を期待しないことを意味している。したがって、エラー状態が返される(5行目)。特定のファクトに対する開始状態を決定するために、いかなる引数もまだ検証されていない限り、実際の引数のインデックスは-1であると仮定する。この場合、「次の」状態は、オートマトンの開始状態である。
【０１７１】
開始状態の決定後、実際のファクト検証が開始しうる。これは、アルゴリズム5に示されている。アルゴリズム5は、ファクトの検証のための例示的なアルゴリズムである。ファクトのそれぞれの引数について、実際の状態の遷移関数がコールされる(3行目)。これは、検証の成功に応じた状態を返す。このリターン状態が、オートマトンがその時点において入っているのと同じ状態である場合、引数の検証は成功していなかったということである。次いで、1つの引数が無効である場合、ファクトはもうそれ以上有効になりえないため、その引数に関するループが停止される(5行目)。そうでなければ、実際の状態は、実際の状態によって返される状態に設定される(7行目)。
【０１７２】
ファクトが検証された後(つまり、すべての引数が有効であるか、または1つの引数が有効でなかったことで検証が停止されたかのいずれかである)、何らかのと処理がある。これは、もっぱら、ファクト集合の検証の成功を追跡する変数を設定することを含む。この後処理は、アルゴリズム6に示されている。
【０１７３】
アルゴリズム6は、ファクト検証後処理のための例示的なアルゴリズムである。オートマトンの実際の状態がその受理状態であれば、ファクトの検証は成功したということである。もしそうであれば、また有効なファクトが、すでに検証されている第1のファクトである場合、成功した変数は真に設定される(3行目)。これは、成功した変数のデフォルト値が偽であるため第1のファクトについてのみ実行されることに留意されたい。これの理由は、いかなるファクトもまだ検証されていない場合、検証は成功ではありえないということである。さらに、ファクトを、検証が成功した場合かつその場合に限りすべての有効なファクトを格納する共有メモリに追加される(5行目)。しかし、ファクトが無効である場合、成功した変数は、偽に設定され(7行目)、ファクトは、無効なファクトのローカル集合に追加される(8行目)。
【０１７４】
「現在までのFVAの階層的コール」は、実際のファクトが依存する下位レベルのファクトの検証を受け持つ遷移関数であり、これについては、これ以上説明しなかった。しかし、上で述べたように、この遷移関数は、他のオートマトンがコールされたときに他の遷移関数とは異なる。ファクト検証遷移関数が、アルゴリズム7に示されている。
【０１７５】
アルゴリズム7は、ファクト検証遷移関数の例示的なアルゴリズムである。まず最初に、ローカルのFVAの文脈が、親FVAが検証するファクト集合、親FVAの文脈、および親FVAによってすでに検証されているすべてのファクトを格納する共有メモリの合併集合として定義される(1行目)。親FVAは、別のオートマトン(この場合、ローカルFVA)をコールする遷移関数に対するオートマトンである。次いで、実際の引数が依存するすべての下位レベルのファクトが、決定される(2行目)が、これはアルゴリズム8に示されている。
【０１７６】
アルゴリズム8は、引数の依存関係ファクトを決定するための例示的なアルゴリズムである。引数モデルが依存するすべてのファクトモデルについて、実際の引数モデルが決定された後(1行目)、同じ述語を持つ文脈内のすべてのファクトが、見込み依存関係(prospect dependency)ファクトの集合に追加される(3行目)。これは、実際のファクトが依存しうるすべてのファクトが後で検証されるべきであることを意味する(アルゴリズム7、3行目)。
【０１７７】
したがって、このプロシージャは、ファクトがすでに検証されている場合に検証がスキップされるので、一般ファクト検証に類似している(アルゴリズム5)。この場合、親オートマトンの次の状態が、リターン状態リストに追加され(アルゴリズム7、5行目)、これにより最終リターン状態を決定するためにすべてのローカルのFVAのリターン状態を収集する。
【０１７８】
ファクトがまだ検証されていない場合、ローカルFVAがコールされ、検証が実行される(7行目)。検証が成功した場合、ファクトが共有メモリに追加され、次の状態がリターン状態集合に追加される(9行目および10行目)。しかし、下位レベルのファクトが有効でない場合、ローカルのFVAの無効なファクト集合に追加され、実際のファクトは、親FVAの無効なファクト集合に追加される(12行目)。さらに、実際の状態は、プロスペクトリターン状態の集合に追加される(13行目)。終わりに、プロスペクトリターン状態の集合からのリターン状態が決定される(17行目)。これは、アルゴリズム9に示されている。
【０１７９】
アルゴリズム9は、ファクト検証遷移関数のリターン状態を決定するための例示的なアルゴリズムである。リターン状態の集合がただ1つの状態を含む場合、この状態が返される(2行目)。プロスペクトリターン状態の集合内にさらに多くの状態がある場合、その集合内に1つあればエラー状態が返されるが(4行目)、それは、これが生じた場合、ローカルのFVAの検証時にエラーが発生しているからである。しかし、この集合が実際の状態を含む場合、このことは下位レベルのファクトが有効でないことを意味しているので、その状態が返される(6行目)。述べられている場合のどれもが発生しない場合、任意の状態が返される(8行目)。次いで、親FVAは、その検証プロセスを続けることができる。
【０１８０】
オートマトンのランタイム上で実行することができる検証プログラムに対するモデルとともに、プログラミングモデルの定義を記述することができる。プログラミングモデルは、図20に示されている。図20は、オートマトン2002の例示的なプログラミングモデル2000のグラフ表現である。オートマトン2002は、ファクト2008および定義ファイル2006を入力として受け取る。セマンティックモデル2004は、定義ファイル2006を使用して構築される。このモデルを使用して、オートマトン2002は、ファクトの集合を検証することができる。出力は、テキストログ2010およびドットグラフ2012として実現される。
【０１８１】
最初に、入力の集合があり、検証フレームワークによって処理される場合もあれば、処理されない場合もある。この定義ファイルを使用してセマンティックモデルを作成する。これは、与えられたファクトを検証するオートマトンによって使用される。検証の終わりに、検証の結果を診断するために使用することができるある種の出力がある。
【０１８２】
上で説明されているように、定義ファイルは、外部ドメイン固有言語で書かれており、これを使用してセマンティックモデルを作成する。したがって、モデルは、設計時に定義ファイル内に記述されていなければならない。このことは、ユーザーがファクト、その述語、引数、およびそれらの間の関係を指定することを意味する。定義ファイルを書くのに使用される言語は、以下の文法で定義される。
<ファクト述語>[<キーインデックス>]:<引数リスト>
キーインデックスは、ファクトを一意的に識別する引数リスト内の引数のインデックスを示す整数値である。したがって、ほとんどの場合において、これはURIである。キーインデックスは、systemURlとhostURlの両方の引数によってしか一意的に識別されえない、単一のキー引数を有しないファクト、例えばruns_onファクトがあるときにオプション値である。ファクトのキーインデックスは、ブラケット([])で囲んで書かれる。さらに、引数リスト内の引数は、カンマ(,)によって区切られる。1つの引数の定義を以下に示す。
<引数名>({<引数が依存するファクト述語>},<基数>)
引数が複数のファクトに依存する場合、下位レベルのファクトの述語は、カンマ(,)で区切られる。1つのファクトの定義の後に、ファクト定義の終わりをマークするドット(.)がある。次いで、次のファクトを、次の行で定義することができる。カンマを含めるには、シャープ記号(#)を使用する。定義ファイルからの抜粋が、リスティング1に示されている。
【０１８３】
リスティング1は、定義ファイルからの例示的な抜粋である。リスティング1は、data_discxファクトおよびsystem_discxファクトの定義、さらには2つのコメントを示している。1行目には、あるレベル0のファクトの定義が続くことを示すコメントがある。2行目には、data_discxファクトが定義されている。そのキー引数はURIであり、他の3つの引数はオプションである。さらに、これらの引数のどれも、他のファクトに依存しない。次の行に、最後の行のsystem_discxファクトの定義が続く別のコメントがある。このファクトの名前は、基数が1なのでオプションではないが、記述はオプションである。最後の引数は、引数リストのインデックス2におけるsystemURlであり、これは、有効でマッチするdata_discxファクトに依存する必須引数である。
【０１８４】
ファクトおよび引数モデルの定義の際に、まだ実装されていない特別な検証プロシージャを必要とする引数がありうる。例えば、ユーザーは、システム名を空でない文字列にしたいだけでなく、文字列の長さを255文字未満にもしたい場合がある。したがって、新しい遷移関数(それゆえ、新しい状態)を実装しなければならない。このような新しい状態は、検証フレームワークによって見つけられ、検証フレームワークによって使用されるように厳格な命名方式に従わなければならない。状態は、以下のスキーマを使用して命名されるJava(登録商標)クラスである。
Validate<ファクト述語><引数名>
名前は、リテラル「Validate」から始まり、その後にファクト述語とこの状態に対する引数の名前が続く。例えば、システム名を検証する状態に対する名前は、以下のようになる。
ValidateSystem_discxName
ファクト述語および引数名が、定義ファイル内で定義されたものであることが非常に重要である。上の例では、ファクト述語および引数名の最初の文字は、大文字である。その理由は、読みやすさである。しかし、検証フレームワークは、小文字の述語および名前も認識する。
【０１８５】
検証プログラムのログ作成および使用は、デバッグを目的として(いくつかの実施形態ではリアルタイムで)行うことができる。検証が完了すると、検証の結果は、成功か、成功していないかのいずれかである。検証結果を分析するために、オートマトンは、それが行う内容のロギングを円滑にする。以下のイベントをログに記録することができる。
1. ファクトの集合の検証の開始。
2. ファクトの検証の開始。
3. 引数の検証の開始。
4. 引数の検証の終了。
5. ファクトの検証の終了。
6. ファクトの集合の検証の終了。
7. 例外の発生。
上で述べたイベントのどれかが発生した場合、オートマトンは、Visitor設計パターンの実装であり、イベントをログに記録する、ロガーをコールする。ロガーは、オートマトンへの参照を有するので、ユーザーが出力を望む仕方で有益なログを作成するために必要なすべての情報にアクセスすることができる。
【０１８６】
ログ出力には2種類あり、テキストとグラフである。テキスト出力は、オートマトンがその時点において行う内容、つまり、検証のどの部分を終了したばかりであるかの記述である。例えば、オートマトンが1つのdataファクトを検証する場合、出力は、リスティング2に示されているような出力となる。
【０１８７】
リスティング2は、有効なdataファクトに対するオートマトンの例示的なテキスト出力である。ロガーは、オートマトンの開始、dataファクトの検証の開始、引数の検証、ファクトとオートマトンの終了をログに記録する。これは、1つのファクトとすべてのファクトの検証が成功したかどうかについてもログに記録する。
【０１８８】
最初に、ロガーは、オートマトンの開始および検証すべきファクト集合内にファクトがいくつあるかをログに記録する。次いで、dataファクトの検証の開始をログに記録する。次に、引数の検証およびその成功をログに記録する。この後、dataファクトの検証の終わり、およびそれが有効であるかどうかをログに記録する。この後、すべてのファクトが検証された後、オートマトンの終了および検証全体のステータス、つまり、すべてのファクトが有効であるかどうかをログに記録する。
【０１８９】
ロギングの第2の方法は、ドットグラフを使用して実装される、グラフ出力である。一般に、ドットは、「有向グラフを階層として描画する」ために使用される。したがって、これは、特定の形式のグラフの記述を含む、テキストファイルを読み込み、異なるグラフ形式で作図する。リスティング3は、有効なdataファクトに対するドットグラフの記述を含むテキストファイルを示している。
【０１９０】
リスティング3は、有効なdataファクトに対するドットグラフの例示的な説明である。リスティング3は、ドットで記述されたFVAの状態および遷移を含む。1行目のグラフGは、グラフGが有向グラフであると想定されることを意味する。中括弧を使用して、グラフのどの部分がプログラミング言語の場合と同様に一緒に属すかをマークする。2行目の、rankdir = LR;は、グラフが左から右に描画されることを予想するものである。セミコロンは、命令を終了させるために使用され、これはある種のプログラミング言語(例えば、Java(登録商標))にも類似している。3行目の部分グラフは、主グラフ内の節点と辺の新しい部分集合の作成を表す。部分グラフに名前を付けるために、コマンドラベル「[...];」が使用される。その結果、エンティティは、一意的な名前でラベル付けされず、むしろ、指定されたラベルを付けられる。グラフ、部分グラフ、または節点の一意的な名前と異なり、ラベルは、一意的でなくてもよい。例えば、部分グラフのラベルは、4行目で定義されている。節点を部分グラフに割り当てるために、節点の一意的な名前を部分グラフの本体に書き込まなければならない。部分グラフと同様に、節点もラベル付けすることができる。リスティング3では、部分グラフに割り当てられる節点が5つある。ロギングのため、それぞれの節点は、オートマトンが入っていた1つの状態を表す。辺は、オートマトンの遷移を表す。ドットグラフのテキスト記述では、辺は、主グラフの端に定義される。2つの節点間の有向辺を定義するために、第1の節点を行の始めに書き下し、その後に矢印(→)を続けなければならない。行の終わりで、有向辺が進む先の節点があり、その後にセミコロンが続き、コマンドを終了させる。例えば、オートマトンの第1の状態と第2の状態との間の辺は、12行目で定義されている。dataファクトの引数の検証後、オートマトンは、次の状態に移り(SkipArgumentValidation)、したがって、これら2つの状態は、矢印によって連結された。
【０１９１】
グラフを表示し、グラフの記述だけを表示しないようにするために、グラフ可視化ソフトウェア、例えば、オープンソースソフトウェアのGraphviz1に含まれるドットグラフビューアである、dottyを使用しなければならない。リスティング3で定義されているドットグラフのグラフ出力は、図21に示されている。図21は、例示的なdataファクトのグラフ出力2100である。dataファクトの検証のために、オートマトンは、最初に、dataURIを検証しなければならず、次いで、3つのオプション引数の検証をスキップしなければならない。これらの検証中にエラーが発生しなければ、最終状態が、重なり合う正方形で表される。
【０１９２】
ドットグラフのテキスト記述の3行目のdataファクトに対する部分グラフのラベル(リスティング3)は、グラフの最上部におけるラベルである。これは、検証されたファクトを含む。検証中にオートマトンが通った状態は、ドットグラフの節点によって表される。dataファクトがURI、data引数、content type、およびoriginを有しているので、URIは、最初に検証されている。したがって、第1の節点は、ValidateArgumentと呼ばれる。この状態は、オートマトンがURIの検証を終了した後に、ロガーによってログに記録された。オートマトンの次の3つの引数は、オプションであり、したがって検証をスキップすることができる。引数の検証をスキップした後、対応する状態がログに記録される。オートマトンは、ファクトの検証を終了するとすぐに、このイベントをログに記録するロガーをコールする。グラフィカルロガーは、オートマトンがファクトを検証するのに成功したかどうかを分析する。もしそうであれば、最終状態が重なり合う正方形で表される。ファクトを検証した後にオートマトンが入っている状態が受理状態でない場合、状態は、重なり合う三角形で表される。したがって、検証が成功したかどうかを判定するためにドットグラフを使用すると都合がよい。検証すべきファクトが、レベルが0より高いファクトである場合、別のファクトのキーである引数を検証する遷移関数においてオートマトンのコールがありうる。この場合、オートマトンが通った「パス」は、実線の矢印で示される。別のオートマトンのコールがなかった場合にそのオートマトンが通ったであろうパスは、ドット矢印で表される。例えば、runs_onファクト、ならびに対応するシステムおよびホストファクトがあり、それぞれ対応するdataファクトを有しているものとする。通常は、この場合、ドットグラフも、どのオートマトンがコールされたかを示す。有効な下位レベルのファクトが再び検証されると想定される場合、オートマトンは、検証をスキップし、ドットグラフは、1つの状態、受理状態(AllArguments Validated)のみを有するオートマトンを示す。
【０１９３】
オートマトンが、ファクトの集合内で無効なファクトを見つけることが重要なだけではなく、それらのファクトがなぜ有効でないかを調べることも重要である。したがって、オートマトンは、ファクトの集合、単一のファクト、または引数を検証するときには必ずログに記録する。現在まで、検証オートマトンは、実行内容をログに記録する2つの異なる可能性を有し、ロギングの1つの方法はその時点で実行している内容を短い説明で書き出すことによるテキストの方法であり、もう1つの方法はドットグラフを出力することによるグラフによる方法である。オートマトンをデバッグするために、両方の出力を結合して、検証すべきファクトにある問題を見つけることができる。有用なグラフ出力を作成するために、すべての場合において、トップダウンアプローチを使用した。
【０１９４】
知識ベース内に注入するruns_onファクトを作成しようとするユーザーがいるものとする。このユーザーは、述語およびsystemURl引数をタイプすることによってruns_onファクトを作成し始める。次いで、ユーザーは、systemファクトも作成しなければならないことに気づき、そこで、ユーザーはruns_onファクトの作業を停止し、代わりにsystemファクトの作業を開始する。ユーザーは、システム名「HXPCLNT001」を別の場所からコピーして、自分のテキストエディタに貼り付ける。しかし、ユーザーは、貼り付けボタンを47回「うっかり」押してしまうことがある。それは、システム名引数がシステム名を47回含むからである。ユーザーは、システムの説明およびURIもタイプする。最終ファイルは、リスティング4に示されている。可読性のために、システム名の一部のみが示されていることに留意されたい。
【０１９５】
リスティング4は、無効なsystemファクトを伴うruns_onファクトに対する例示的な定義ファイルである。名前が長すぎる対応するシステムを有するruns_onファクトがある。そのため、それは無効であり、runs_onファクトも同様に無効になる。次いで、ユーザーは、ファイルの検証を開始する。オートマトンが、図21に表示されているドットグラフをログに記録した。3つのファクトが図21に示されている。まず最初に、検証オートマトンの開始状態である単一状態を持つruns_onファクト2102がある。この状態から、対応するsystemファクト2104を検証するためにコールされたオートマトンの開始状態に向かう有向辺がある。これは、オートマトンが対応するsystemファクトを見つけたことを意味する。しかし、この例では、システムの名前を検証しようとしたときに、何か間違いが起きた。ユーザーが、無効なシステム名が検証失敗の理由であることに気づかないので、ユーザーは、テキスト出力を見てこの検証を調べる(リスティング5を参照)。
【０１９６】
リスティング5は、無効なsystemファクトを伴うruns_onファクトに対するオートマトンの例示的なテキスト出力である。オートマトンは、システムの名前が無効であることに気づき、したがってファクトが無効であることに気づいた。その結果、runs_onファクトも同様に無効である。ログに記載されているように、検証の失敗の理由は、許容される長さを超える、システムの名前である。
【０１９７】
その結果、オートマトンの出力をさらに分析した、ユーザーは、システム名を変更することによって記述ファイル内の自分の誤りを修正した。ユーザーは、自分が訂正する修正済みのsystemファクトに対するdataファクトを追加することも忘れる場合がある。修正された記述ファイルは、リスティング6に示されている。リスティング6は、対応するsystemファクトを伴い、dataファクトがない、runs_onファクトに対する例示的な定義ファイルである。
【０１９８】
しかし、このときに、ユーザーは、1の代わりにURIの最後の文字としてうっかり2をタイプしたときにデータディスクのURIを追加した場合に間違いを犯した。
【０１９９】
この定義ファイルの検証のグラフ出力は、図22に示されている。図22は、対応するsystemファクト2204が対応するdataファクトを有しないruns_onファクト2202に対する例示的なオートマトンのグラフ出力2200である。systemファクト2204を検証するオートマトンは、有効なdataファクト2206があるとしてもマッチするdataファクトを見つけることができなかった。しかし、このdataファクトのURIは、systemURlと異なり、そのため、検証は成功しない。図21と同様に、オートマトンは、runs_onファクト2202の検証から開始した。この検証中に、これは、対応するsystemファクトの検証を受け持つ別のオートマトンをコールした。このオートマトンは、システム名を検証する状態を渡すことに成功し、したがってシステム名の修正は成功した。しかし、このときに、オートマトンは、ValidateFact状態2208で動けなくなっているオートマトンによって表示される、systemファクト2204と同じURIを持つdataファクトを見つけることができなかった。
【０２００】
実際、このファクト集合内にdataファクトがあり、また検証され(成功し)ているが、そのURIは、systemファクトのURIと異なる。したがって、オートマトンは、それが2つのファクトの間の関係を見つけることができない。これは、テキストログによっても示される。これは、リスティング7に示されている、テキストログによっても示される。
【０２０１】
リスティング7は、無効なsystemファクトを伴うruns_onファクトに対するオートマトンの例示的なテキスト出力である。問題は、対応するsystemファクトがマッチするdataファクトを有していないことである。dataファクトは1つしかないが、これは、URIの最後の文字が異なるので、システムと異なるURIを有する。テキスト出力の1つの適切な部分は、以下のものである(リスティング7の6行目)。
system_discx : Could not find a valid data_discx with the same key systemURI : corn .sap .bnm .nd. discovery .ale . facts . internal . AleFactsProviderHXPCLNT001 ).
オートマトンが、同じURIを持つdataファクトを見つけることができなかったことを示している。これは、検証の失敗の理由である。ここでもまた、ユーザーは、自分の間違いに気づき、dataファクトのURIを変更してsystemファクトとマッチするようにした。ここでもまた、ユーザーは、オートマトンにファクトを検証させる。グラフ出力が、図23に示されている。図23は、ホストURIが指定されていないruns_onファクト2302に対する例示的なオートマトンのグラフ出力2300である。runs_onファクト2302のsystemURlとマッチするsystemファクト2304を検証して成功した後、オートマトンは、hostURIを検証することができなかったが、これは実際には指定されていなかった。したがって、オートマトンは、(非最終的)状態ValidateFact内にとどまる。グラフ内の有向辺を辿り、オートマトンは、runs_onファクト2302の検証を開始した。次に、systemファクトおよびその対応するdataファクトを検証するために別のオートマトンをコールした。これらの検証が成功したので、制御権は主オートマトンに返され、最終的に、hostURIを検証することを試みた。明らかに、オートマトンはこの状態で動けなくなる。多分、テキスト出力は、hostURIの問題が何であったかを示している。完全な出力が、リスティング8に示されている。
【０２０２】
リスティング8は、無効なruns_onファクトに対するオートマトンの例示的なテキスト出力である。問題は、hostURIが指定されていないことである。オートマトンは、マッチするsystemファクトを検証することができなかった。runs_onファクトのhostURIを検証しようとしたときに、それが空の文字列を含んでいることに気づいた。したがって、検証は失敗であった。ログの最も重要な部分を以下に示す(リスティング8の17行目)。
runs_on_discx: No hostURl specified.
この出力を使用して、ユーザーは、hostRUIをruns_onファクトに追加することによって自分の定義ファイルを変更した。ユーザーがそれを行うときに、ホストファクトをまだ作成していないことに気づいた。再び同じ間違いをするのを避けるために、ユーザーは、ホストファクトおよびその対応するdataファクトも作成する。次いで、定義ファイルは、リスティング9に示されているような形である。リスティング9は、有効なruns_onファクトに対する例示的な定義ファイルである。対応するシステムおよびホストファクトがそれぞれマッチするdataファクトを有しているruns_onファクトがある。
【０２０３】
オートマトンのロガーによって生成されるドットグラフが図24に示されている。図24は、有効なruns_onファクト2402に対する例示的なオートマトンのグラフ出力2400である。runs_on 2402、system2404、およびdata2406ファクトの検証はすべて成功しており、したがって、すべての最終状態は、重なり合う正方形で表される。このグラフでは、すべてのオートマトンの最終状態は、重なり合う正方形で表され、すべてのファクトが有効であることを意味する。リスティング10は、有効なruns_onファクトに対するオートマトンの例示的なテキスト出力である。テキスト出力の最終メッセージ(リスティング10の45行目)は以下のとおりである。
Validation Successful
すべてのファクトが有効であるので、ファクト集合の検証は成功である。したがって、ユーザーは、自分が作成したファクトを注入することができた。
【０２０４】
一般に、ファクトの集合が非常に小さい場合(上記の例のように)、検証を見渡すためにドットグラフを最初に見るのはよい考えである。赤色にマークされた多数の状態がある場合、テキストログは、エラーのより詳細な説明は表示するので有用であることがある。より大きなファクト集合がある場合、テキスト出力の最後の行を最初にみ見るがよい。これは、ファクト集合の検証が成功したかどうかを知らせる。成功しない場合、グラフ出力が、検証オートマトンが動けなくなった状態を見つけるのに役立つ。この情報が、いずれも役立たない場合、それでも、それぞれの引数の検証の成功の情報を含む、詳細なテキストログがある。その結果、グラフ出力とテキスト出力との組み合わせを使用して、オートマトンをデバッグすることができ、したがって、検証を可能な失敗に対する理由を見つけることができる。
【０２０５】
図25は、知識のコンテンツベースの検証に対する例示的なシステムレベルのシステム2500を示す概略図である。図25は、例示的な取引環境システム2500を例示している。システム2500は、マーケットプレース管理環を境備えることができる。一実施形態では、システム2500は、小売店、仕入れ先、顧客、銀行などの1つまたは複数のクライアント2502に結合されたサーバー2504を備えることができ、少なくとも一部はネットワーク2530越しに通信している。クライアント2502は、システム2500に関連付けられているデータの受信、送信、処理、または格納を行う動作が可能な電子コンピュータデバイスを備える。図25は、本開示とともに使用することができるコンピュータの単なる一例を示すものであり、そのようなものとして、それぞれの例示されているコンピュータは、好適な処理デバイスを包含することを一般的に意図されていることは理解されるであろう。例えば、図25は、1つのサーバー2504を例示しているけれども、システム2500は、サーバー以外のコンピュータ、さらには、サーバープールを使用して実装されうる。実際、システム2500は、例えば、ブレードサーバー、汎用パーソナルコンピュータ(PC)、Macintosh、ワークステーション、UNIX(登録商標)ベースのコンピュータ、または他の好適なデバイスなどの任意のコンピュータもしくは処理デバイスとすることができる。言い換えると、本開示では、従来のオペレーティングシステムを持たないコンピュータを含む汎用コンピュータ以外のコンピュータも企図する。システム2500は、Linux(登録商標)、UNIX(登録商標)、Windows(登録商標) Server、または他の好適なオペレーティングシステムを含む任意のオペレーティングシステムを実行するように構成されうる。一実施形態によれば、システム2500は、ウェブサーバーおよび/またはメールサーバーを備えるか、またはそれらと通信可能なように結合することも可能である。
【０２０６】
例示されているように、システム2500は、リモートリポジトリ2506と通信可能なように結合されうる。リポジトリ2506は、システム2500用のストレージバックボーンを形成する1つまたは複数の永続的なストレージデバイス(例えば、ハードドライブなど)を備えることができる。リポジトリ2506は、企業内、企業間、地域、全国、または実質的に国内的な電子ストレージデバイス設備、データ処理センター、またはアーカイブを含みうる。別の実施形態では、リポジトリ2506は、Integrated Drive Electronics(IDE)接続、Small Computer Systems Interface(SCSI)接続、Serial ATA(SATA)接続、または他の好適な通信可能な接続などの、直接的接続を介して、システム2500に、内部的にまたは外部的に、結合される1つまたは複数のハードディスクドライブ、半導体メモリ、および同様のものを備えることができる。
【０２０７】
リポジトリ2506は、仮想プライベートネットワーク(VPN)、セキュアシェル(SSH)トンネル、または他の安全なネットワーク接続を介してシステムイン2500に通信可能なように結合された中央データベースとすることができる。リポジトリ2506は、システム2500に関連付けられている情報を格納し、そのようなデータをシステム2500に伝達するように動作可能な限り、例示的な企業またはオフショアの1つを含む適切な場所に物理的にまたは論理的に配置されうる。例えば、リポジトリ2506は、データストアまたはウェアハウスを含むことができる。
【０２０８】
リポジトリ2506を使用することで、システム2500および/または1つもしくは複数の取引参加企業がリポジトリ2506に命令2505もしくはファクト2507を動的に格納し、また取り出すことができる。例えば、命令2505は、システム2500によって実行されたときにセマンティックモデル2512から検証プログラムを生成するコードを含むものとしてよい。命令2505は、ネットワーク2530を介してウェブ実行可能であるコード(例えば、Java(登録商標)コード)を含むものとしてよい。例えば、クライアントシステム2502は、ネットワーク2530を介して命令2505からコードを実行することができる。検証を受けうるファクト2507を生成することができる。リポジトリ2506は、クラウドベースのメモリであってもよい。これは、ネットワーク2530越しにアクセスされる分散型メモリであるものとしてよい。リポジトリ2506は、図19に示されているような共有メモリとすることもできる。
【０２０９】
命令2505は、ソフトウェア、ファームウェア、配線されたもしくはプログラムされたハードウェア、またはこれらの組み合わせを適宜含みうる。実際、命令140は、C、C++、Java(登録商標)、J#、Visual Basic、アセンブラ、Perl、4GLの好適な任意のバージョン、さらにはその他のものを含む、適切なコンピュータ言語で書くことができるか、または記述することができる。例えば、命令140は、Enterprise Java(登録商標) Beans (「EJB」)として実装することができるか、または設計時コンポーネントが、J2EE (Java(登録商標) 2 Platform、Enterprise Edition)、ABAP (Advanced Business Application Programming)オブジェクト、または特に、Microsoftの.NETなどのランタイム実装を異なるプラットフォーム内に生成する機能を備えることができる。さらに、リポジトリ2506および/またはシステム2500の内部にように例示されているが、命令に関連付けられている1つまたは複数のプロセスを、リモートに格納するか、リモートへ参照するか、またはリモートで実行することができる。例えば、命令2505の一部は、リモートでコールされる(例えば、小売店システムによって)ウェブサービスを作成することができるが、命令2505の別の部分は、クライアント(例えば、取引参加企業の1つ)で処理するためにバンドルされたインターフェースオブジェクトであってもよい。別の例では、命令の大半は、取引参加企業の1つに常駐する-またはその処理が実行される-ものであってもよい。さらに、本開示の範囲から逸脱することなく、命令2505は、別のソフトウェアモジュールまたは企業アプリケーション(図示せず)の子もしくはサブモジュールであってもよい。
【０２１０】
リポジトリ2506は、保存ファクト2510を格納することもできる。ファクト2510は、ビジネス、企業、アプリケーション、または取引参加企業が関わる他の取引データおよびメタデータを含むことができる。例えば、ファクト2510は、上で述べたような、購入履歴、購入傾向情報、マスターカタログ内のエントリ、ビジネスプロファイル、他のビジネス属性、および/またはビジネス格付け、さらには、他の好適なマーケットプレース関係データを含むことができる。そのようなものとして、システム2500は、取引参加企業間のマッチ(つまり、新しい潜在的関係)を識別するために必要とされ使用される情報を求めてリポジトリ2506のマイニングを行うことができる。
【０２１１】
システム2500は、プロセッサ2508をさらに備えることができる。プロセッサ2508は、システム2500のオペレーションを実行するために命令を実行しデータを操作する。さまざまな構成において、プロセッサ2508は、例えば、中央演算処理装置(「CPU」)、ブレード、特定用途向け集積回路(「ASIC」)、フィールドプログラマブルゲートアレイ(「FPGA」)、または他の好適な論理デバイスとすることができる。図25は、システム2500内の単一プロセッサ2508を例示しているけれども、特定のニーズに応じて複数のプロセッサを使用することができ、プロセッサ2508への参照は、適用可能な場合に複数のプロセッサを含むことが意図されている。
【０２１２】
システム2500は、ローカルメモリ2511も備える。図示されているように、メモリ2511は、それぞれ命令2505およびファクト2507の部分集合であってもよい、命令2512およびファクト2510を格納することができる。当業者であれば、命令2512およびファクト2510は、プロセッサ2508によって実行もしくは操作される前にメモリにコピーすることができることを理解するであろう。メモリ2511は、任意のメモリもしくは他のコンピュータ可読ストレージモジュールであってもよく、限定はしないが、磁気媒体、光媒体、ランダムアクセスメモリ(「RAM」)、リードオンリーメモリ(「ROM」)、取り外し可能媒体、または他の好適なローカルもしくはリモートのメモリコンポーネントを含む、揮発性もしくは不揮発性のメモリの形態をとりうる。メモリ2511は、システム2500に内部的にまたは外部的に結合することができる。
【０２１３】
システム2500は、ネットワーク2530を介して、他の取引参加企業などの、他のコンピュータシステムと通信するためのインターフェース2514を備えることもできる。いくつかの実施形態では、システム2500は、メモリ2511内に格納するため、リポジトリ2506に格納するため、および/またはプロセッサ2508によって処理するために、インターフェース2514を通じて内部もしくは外部の送り手からデータを受信する。一般に、インターフェース2514は、好適な組み合わせでソフトウェアおよび/またはハードウェア内に符号化され、ネットワーク2530と通信する動作が可能なロジックを備える。より具体的には、インターフェース2514は、ネットワーク2530に関連付けられている1つまたは複数の通信プロトコルをサポートするソフトウェアまたは物理的信号を伝達するように動作可能なハードウェアを備えることができる。
【０２１４】
ネットワーク2530は、システム2500と取引参加企業などの、他のローカルもしくはリモートコンピュータとの間でワイヤレスまたは有線による通信を円滑に行えるようにする。ネットワーク2530は、企業の、もしくは安全なネットワークの全部または一部とすることができる。別の例では、ネットワーク2530は、有線リンクまたはワイヤレスリンク越しの取引参加企業のうちの1つまたは複数との間だけのVPNとすることができる。このような例示的なワイヤレスリンクは、802.11a、802.11b、802.11g、802.11n、802.20、WiMax、および他の無線リンクを利用するものであってよい。単一の、または連続するネットワークとして例示されているが、ネットワーク2530は、ネットワーク2530の少なくとも一部がシステム2500と取引参加企業のうちの少なくとも1つとの間の通信を円滑にすることができる限り、本開示の範囲から逸脱することなく、さまざまなサブネットまたは仮想ネットワークに論理的に分割することができる。
【０２１５】
ネットワーク2530は、システム2500内のさまざまなコンピューティングコンポーネントの間の通信を円滑にする動作が可能である内部もしくは外部のネットワーク、ネットワーク、サブネットワーク、またはこれらのネットワークの組み合わせを含む。ネットワーク2530は、例えば、インターネットプロトコル(「IP」)のパケット、フレームリレーのフレーム、非同期転送モード(「ATM」)のセル、音声、ビデオ、データ、および他の好適な情報をネットワークアドレス間で伝達することができる。ネットワーク2530は、1つまたは複数のローカルエリアネットワーク(「LAN」)、無線アクセスネットワーク(「RAN」)、メトロポリタンエリアネットワーク(「MAN」)、ワイドエリアネットワーク(「WAN」)、インターネットとして知られている地球規模のコンピュータネットワークのすべてまたは一部、および/または1つもしくは複数の場所にある他の1つまたは複数の通信システムを含むことができる。いくつかの実施形態では、ネットワーク2530は、企業およびいくつかのもしくはリモートのクライアントに関連付けられている安全なネットワークであってもよい。
【０２１６】
クライアント2502は、通信リンクを使用してシステム2500またはネットワーク2530に接続もしくは通信するように動作可能なコンピューティングデバイスを備えることができる。高水準では、取引参加企業のそれぞれは、少なくともグラフィカルユーザーインターフェース(「GUI」)2516を備えるか、または実行することができ、システム2500に関連付けられている適切なデータの受信、送信、処理、および格納を行うように動作可能な電子コンピューティングデバイスを備える。わかりやすくするために、取引参加企業のそれぞれは、1人のユーザーが使用することに関して説明されている。しかし、本開示は、多くのユーザーが1台のコンピュータを使用すること、または1人のユーザーが複数のコンピュータを使用することを企図している。いくつかの状況において、ユーザーは、所有者、経理担当者、さらには第三者もしくは外部の会計士を含むものとしてよい。
【０２１７】
GUI 2516は、クライアント2502のユーザーが、アプリケーションまたは他の取引データを閲覧するなど、適当な目的のために、システム2500の少なくとも一部とインターフェースすることを可能にするように動作可能なグラフィカルユーザーインターフェースを備える。一般に、GUI 2516は、システム2500によって供給される、またはシステム2500内で伝達されるデータを特定のユーザーに効率よく、わかりやすく提示するための手段である。GUI 2516は、ユーザーによって操作されるインタラクティブなフィールド、プルダウンリスト、およびボタンを持つ複数のカスタマイズ可能なフレームもしくはビューを備えることができる。例えば、GUI 2516は、検証プロセスのグラフおよび/またはテキスト出力などの、いくつかの要素を表示するように動作可能である。GUI 2516は、複数のポータルもしくはダッシュボードを提示することもできる。例えば、GUI 2516は、ユーザーが検証プログラムのモデル化および検証のデバッグを表示し、作成し、管理することを可能にするポータルを表示することができる。しかし、GUI 2516は、システム2500内の情報を処理し、その結果をユーザーに効率よく提示する、汎用のウェブブラウザまたはタッチスクリーンなどの、グラフィカルユーザーインターフェースを企図していることは理解されるであろう。GUI 2516は、ウェブブラウザ(例えば、Microsoft Internet ExplorerまたはNetscape Navigator)を介してシステム2500または取引参加企業からデータを受け取り、ネットワーク2530を使用して適切なHTMLまたはXML応答を返すことができる。
【０２１８】
図26は、ファクトを検証する段階のプロセスフロー図2600である。検証に対するファクトを識別することができる(2602)。ファクトを表すセマンティックモデルを作成することができる(2604)。ファクトに関連付けられている文脈を識別することができる(2606)。検証プログラムをセマンティックモデルから生成することができ、セマンティックモデルはドメイン固有言語で書かれている(2608)。セマンティックモデルから実行時にオートマトンの生成を円滑に行う検証プログラムがファクトを検証する(2610)。検証のグラフおよび/またはテキストログを出力することができる(2612)。グラフおよび/またはテキストログをリアルタイムでのデバッグに使用することができる(2614)。
【０２１９】
これで本発明の多数の実施形態が説明された。しかしながら、本発明の精神および範囲から逸脱することなくさまざまな修正を加えることができることは理解されるであろう。例えば、統合モデルと異なるターゲットモデルを使用することができる。別の実行時/検証プログラムを具現化したものを使用することができる。つまり、SATソルバーまたは他の非オートマトンベースの実装を使用することができるということである。それに加えて、オートマトンを定義する他の方法も企図される。例えば、オートマトンは、連鎖オートマトンなど、非埋め込みであってもよい。デバッグプロセスに、異なる出力方法を使用することができる。内部DSLおよびFluent APIなどの、外部DSLと異なる、検証プログラムの表現方法も企図されている。それに加えて、本開示では、個別に所有されるセマンティックモデルを企図している。したがって、他の実施形態は、請求項の範囲内に収まる。
【符号の説明】
【０２２０】
100  アクティビティ図
102  ネットワーク/カスタマーランドスケープレイヤ
104  ネットワークソースレイヤ
106  非武装地帯(DMZ)
108  ネットワーク統合レイヤ
109  リンクデータエンジン
110  ネットワーク統合モデルレイヤ
112  ビジネスグラフユーザーインターフェース/アプリケーション
114  「データを発見する」コンポーネント
116  「データを抽出する」コンポーネント
118  「ファクトに対してデータ分析を処理する」コンポーネント
120  「分析ファクトを公開する」コンポーネント
121  ネットワーク統合メタモデル(NIMM)リソースグラフ
122  NIMMモデル
124  推論アルゴリズム
140  命令
【図１】
2013120605.tif 000029
【図２】
2013120605.tif 000030
【図３】
2013120605.tif 000031
【図４】
2013120605.tif 000032
【図５】
2013120605.tif 000033
【図６】
2013120605.tif 000034
【図７】
2013120605.tif 000035
【図８】
2013120605.tif 000036
【図９】
2013120605.tif 000037
【図１０】
2013120605.tif 000038
【図１１】
2013120605.tif 000039
【図１２】
2013120605.tif 000040
【図１３】
2013120605.tif 000041
【図１４】
2013120605.tif 000042
【図１５】
2013120605.tif 000043
【図１６】
2013120605.tif 000044
【図１７】
2013120605.tif 000045
【図１８】
2013120605.tif 000046
【図１９】
2013120605.tif 000047
【図２０】
2013120605.tif 000048
【図２１】
2013120605.tif 000049
【図２２】
2013120605.tif 000050
【図２３】
2013120605.tif 000051
【図２４】
2013120605.tif 000052
【図２５】
2013120605.tif 000053
【図２６】
2013120605.tif 000054
【図２７】
2013120605.tif 000055
【図２８】
2013120605.tif 000056
【図２９】
2013120605.tif 000057
【図３０】
2013120605.tif 000058
【図３１】
2013120605.tif 000059
【図３２】
2013120605.tif 000060
【図３３】
2013120605.tif 000061
【図３４】
2013120605.tif 000062
【図３５】
2013120605.tif 000063
【図３６】
2013120605.tif 000064
【図３７】
2013120605.tif 000065
【図３８】
2013120605.tif 000066
【図３９】
2013120605.tif 000067
【図４０】
2013120605.tif 000068
【図４１】
2013120605.tif 000069
【図４２】
2013120605.tif 000070
【図４３】
2013120605.tif 000071
【図４４】
2013120605.tif 000072
【図４５Ａ】
2013120605.tif 000073
【図４５Ｂ】
2013120605.tif 000074
【外国語明細書】
2013120605000001.pdf