(57)【要約】  データサブセット化のための装置、コンピュータ読み取り可能媒体及びコンピュータにより実現される方法であって、複数の表からのデータのサブセットに対する要求を受け取るステップと、当該複数の表に対応するエンティティグラフがサイクルを含むか否かを判定するステップと、含む場合にはサイクル的サブセット処理を実行するステップと、含まない場合にはエンティティグラフを展開し、展開されたエンティティグラフがサイクルを有さない場合には非サイクル的サブセット処理を実行し、展開されたエンティティグラフがサイクルを有する場合にはサイクル的サブセット処理を実行するステップと、を含む。【選択図】図３
2016505956.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の計算装置によって実行されるデータサブセット化方法であって、前記方法は、
前記１つ以上の計算装置のうちの少なくとも１つによって、複数の表からのデータのサブセットに対する、サブセット基準を含む要求を受け取るステップと、
前記１つ以上の計算装置のうちの少なくとも１つによって、前記複数の表に対応するエンティティグラフがサイクルを含むか否かを判定するステップと、を含み、前記エンティティグラフは、
各々が前記複数の表のうちの１つの表を表す複数のエンティティと、
前記エンティティ間の複数のエッジに対応するエッジデータと、を含み、前記エッジデータは親エンティティ及び子エンティティを特定し、各エッジは子エンティティから親エンティティに延び、前記エンティティグラフは更に、
前記エンティティ間の複数の関係に対応し、前記親エンティティと前記子エンティティとの間の関係が大関係であるか小関係であるかを特定する関係データ、を含み、前記方法は更に、
前記エンティティグラフがサイクルを含む場合、
前記１つ以上の計算装置のうちの少なくとも１つによって、前記エンティティグラフを用いてサイクル的サブセット処理を実行するステップと、
前記エンティティグラフがサイクルを含まない場合、
前記１つ以上の計算装置のうちの少なくとも１つによって、前記エンティティグラフを展開して展開エンティティグラフを生成する工程と、
前記１つ以上の計算装置のうちの１つ以上によって、前記展開エンティティグラフがサイクルを含む場合に前記展開エンティティグラフを用いてサイクル的サブセット処理を実行する工程と、
前記１つ以上の計算装置のうちの１つ以上によって、前記展開エンティティグラフがサイクルを含まない場合に前記展開エンティティグラフを用いて非サイクル的サブセット処理を実行する工程と、を実行するステップと、を備える、方法。
【請求項２】
請求項１に記載の方法であって、前記１つ以上の計算装置のうちの少なくとも１つによって、前記エンティティグラフを展開して展開エンティティグラフを生成する工程は、
前記エンティティグラフにおける各々全ての大関係について、
複製子エンティティを作成するステップと、
前記親エンティティから前記複製子エンティティへのエッジを作成するステップと、
当該関係における前記子エンティティ及び前記親エンティティ間のエッジ以外の前記子エンティティからの各々全ての延出エッジを削除するステップと、
前記子エンティティから削除した各々全ての延出エッジを、前記複製子エンティティからの延出エッジとして追加するステップと、を含む、方法。
【請求項３】
請求項１に記載の方法であって、前記非サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち、前記エンティティによって表される表の中にある部分を規定し、１つ以上の表現を含む、エンティティ・サブセット定義を生成するステップと、
前記要求されたデータのサブセットに対応する１つ以上の最終サブセット表を計算するために必要な１つ以上の演算子及び１つ以上の中間表現を含むプラン空間を、前記エンティティ・サブセット定義に基づいて生成するステップと、
前記１つ以上の演算子及び前記１つ以上の中間表現と等価の１つ以上の追加の演算子及び１つ以上の追加の中間表現を生成することによって前記プラン空間を展開するステップと、
前記プラン空間の中から、前記１つ以上の最終サブセット表を計算するために用いられ得る１群の演算子を選択するステップと、
前記選択された１群の演算子を用いて前記１つ以上の最終サブセット表を計算するステップと、を含む、方法。
【請求項４】
請求項３に記載の方法であって、前記１群の演算子を選択するステップは、
前記プラン空間における前記演算子の各々にコストを割り当てるステップと、
最も低い合計コストを有する群の演算子を選択するステップと、を含む、方法。
【請求項５】
請求項１に記載の方法であって、前記サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち前記表の中にある部分を規定し、１つ以上の表現を有する、エンティティ・サブセット定義を生成するステップと、
サブセット化すべき表に対応する各々全てのエンティティについて、前記表からステージング表を生成するステップと、を含み、前記ステージング表は、当該エンティティについての前記エンティティ・サブセット定義における前記１つ以上の表現を評価するために必要なデータの列と、前記最終サブセットに特定の行を含めるべきか否かを表すフラグ値の列と、のみを含み、各々のフラグ値は、最初に、当該行における前記データ値が前記サブセット基準を満たす場合には真に設定され、満たさない場合には偽に設定され、前記サイクル的サブセット処理は更に、
各々のエンティティ・サブセット定義における各々全ての表現を再帰的に評価し、前記ステージング表の各々における前記表現を満足する前記行の各々について前記フラグ値を真に変更するステップと、
前記ステージング表の中で真のフラグ値を有する行に対応する、前記複数の表からの行の全てをコンパイルすることにより、１つ以上の最終サブセット表を生成するステップと、を含む、方法。
【請求項６】
データサブセット化装置であって、
１つ以上のプロセッサと、
前記１つ以上のプロセッサのうちの少なくとも１つに動作的に結合され、命令を記憶して有する１つ以上のメモリと、を備え、前記命令は、前記１つ以上のプロセッサのうちの少なくとも１つによって実行されたときに、前記１つ以上のプロセッサのうちの少なくとも１つに対し、
複数の表からのデータのサブセットに対する、サブセット基準を含む要求を受け取るステップと、
前記複数の表に対応するエンティティグラフがサイクルを含むか否かを判定するステップと、を実行させ、前記エンティティグラフは、
各々が前記複数の表のうちの１つの表を表す複数のエンティティと、
前記エンティティ間の複数のエッジに対応するエッジデータと、を含み、前記エッジデータは親エンティティ及び子エンティティを特定し、各エッジは子エンティティから親エンティティに延び、前記エンティティグラフは更に、
前記エンティティ間の複数の関係に対応し、前記親エンティティと前記子エンティティとの間の関係が大関係であるか小関係であるかを特定する関係データ、を含み、前記命令は更に、
前記エンティティグラフがサイクルを含む場合、
前記エンティティグラフを用いてサイクル的サブセット処理を実行するステップと、
前記エンティティグラフがサイクルを含まない場合、
前記エンティティグラフを展開して展開エンティティグラフを生成する工程と、
前記展開エンティティグラフがサイクルを含む場合に前記展開エンティティグラフを用いてサブセット処理を実行する工程と、
前記展開エンティティグラフがサイクルを含まない場合に前記展開エンティティグラフを用いて非サイクル的サブセット処理を実行する工程と、を実行するステップと、を実行させる、装置。
【請求項７】
請求項６に記載の装置であって、前記エンティティグラフを展開して展開エンティティグラフを生成する工程は、
前記エンティティグラフにおける各々全ての大関係について、
複製子エンティティを作成するステップと、
前記親エンティティから前記複製子エンティティへのエッジを作成するステップと、
当該関係における前記子エンティティ及び前記親エンティティ間のエッジ以外の前記子エンティティからの各々全ての延出エッジを削除するステップと、
前記子エンティティから削除した各々全ての延出エッジを、前記複製子エンティティからの延出エッジとして追加するステップと、を含む、装置。
【請求項８】
請求項６に記載の装置であって、前記非サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち、前記エンティティによって表される表の中にある部分を規定し、１つ以上の表現を含む、エンティティ・サブセット定義を生成するステップと、
前記要求されたデータのサブセットに対応する１つ以上の最終サブセット表を計算するために必要な１つ以上の演算子及び１つ以上の中間表現を含むプラン空間を、前記エンティティ・サブセット定義に基づいて生成するステップと、
前記１つ以上の演算子及び前記１つ以上の中間表現と等価の１つ以上の追加の演算子及び１つ以上の追加の中間表現を生成することによって前記プラン空間を展開するステップと、
前記プラン空間の中から、前記１つ以上の最終サブセット表を計算するために用いられ得る１群の演算子を選択するステップと、
前記選択された１群の演算子を用いて前記１つ以上の最終サブセット表を計算するステップと、を含む、装置。
【請求項９】
請求項８に記載の装置であって、前記１群の演算子を選択するステップは、
前記プラン空間における前記演算子の各々にコストを割り当てるステップと、
最も低い合計コストを有する群の演算子を選択するステップと、を含む、装置。
【請求項１０】
請求項６に記載の装置であって、前記サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち前記表の中にある部分を規定し、１つ以上の表現を有する、エンティティ・サブセット定義を生成するステップと、
サブセット化すべき表に対応する各々全てのエンティティについて、前記表からステージング表を生成するステップと、を含み、前記ステージング表は、当該エンティティについての前記エンティティ・サブセット定義における前記１つ以上の表現を評価するために必要なデータの列と、前記最終サブセットに特定の行を含めるべきか否かを表すフラグ値の列と、のみを含み、各々のフラグ値は、最初に、当該行における前記データ値が前記サブセット基準を満たす場合には真に設定され、満たさない場合には偽に設定され、前記サイクル的サブセット処理は更に、
各々のエンティティ・サブセット定義における各々全ての表現を再帰的に評価し、前記ステージング表の各々における前記表現を満足する前記行の各々について前記フラグ値を真に変更するステップと、
前記ステージング表の中で真のフラグ値を有する行に対応する、前記複数の表からの行の全てをコンパイルすることにより、１つ以上の最終サブセット表を生成するステップと、を含む、装置。
【請求項１１】
コンピュータ読み取り可能な命令を記憶した少なくとも１つの非一時的コンピュータ読み取り可能媒体であって、前記命令は、１つ以上の計算装置によって実行されたときに、前記１つ以上の計算装置のうちの少なくとも１つに対し、
複数の表からのデータのサブセットに対する、サブセット基準を含む要求を受け取るステップと、
前記複数の表に対応するエンティティグラフがサイクルを含むか否かを判定するステップと、を実行させ、前記エンティティグラフは、
各々が前記複数の表のうちの１つの表を表す複数のエンティティと、
前記エンティティ間の複数のエッジに対応するエッジデータと、を含み、前記エッジデータは親エンティティ及び子エンティティを特定し、各エッジは子エンティティから親エンティティに延び、前記エンティティグラフは更に、
前記エンティティ間の複数の関係に対応し、前記親エンティティと前記子エンティティとの間の関係が大関係であるか小関係であるかを特定する関係データ、を含み、前記命令は更に、
前記エンティティグラフがサイクルを含む場合、
前記エンティティグラフを用いてサイクル的サブセット処理を実行するステップと、
前記エンティティグラフがサイクルを含まない場合、
前記エンティティグラフを展開して展開エンティティグラフを生成する工程と、
前記展開エンティティグラフがサイクルを含む場合に前記展開エンティティグラフを用いてサブセット処理を実行する工程と、
前記展開エンティティグラフがサイクルを含まない場合に前記展開エンティティグラフを用いて非サイクル的サブセット処理を実行する工程と、を実行するステップと、を実行させる、非一時的コンピュータ読み取り可能媒体。
【請求項１２】
請求項１１に記載の少なくとも１つの非一時的コンピュータ読み取り可能媒体であって、前記エンティティグラフを展開して展開エンティティグラフを生成する工程は、
前記エンティティグラフにおける各々全ての大関係について、
複製子エンティティを作成するステップと、
前記親エンティティから前記複製子エンティティへのエッジを作成するステップと、
当該関係における前記子エンティティ及び前記親エンティティ間のエッジ以外の前記子エンティティからの各々全ての延出エッジを削除するステップと、
前記子エンティティから削除した各々全ての延出エッジを、前記複製子エンティティからの延出エッジとして追加するステップと、を含む、非一時的コンピュータ読み取り可能媒体。
【請求項１３】
請求項１１に記載の少なくとも１つの非一時的コンピュータ読み取り可能媒体であって、前記非サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち、前記エンティティによって表される表の中にある部分を規定し、１つ以上の表現を含む、エンティティ・サブセット定義を生成するステップと、
前記要求されたデータのサブセットに対応する１つ以上の最終サブセット表を計算するために必要な１つ以上の演算子及び１つ以上の中間表現を含むプラン空間を、前記エンティティ・サブセット定義に基づいて生成するステップと、
前記１つ以上の演算子及び前記１つ以上の中間表現と等価の１つ以上の追加の演算子及び１つ以上の追加の中間表現を生成することによって前記プラン空間を展開するステップと、
前記プラン空間の中から、前記１つ以上の最終サブセット表を計算するために用いられ得る１群の演算子を選択するステップと、
前記選択された１群の演算子を用いて前記１つ以上の最終サブセット表を計算するステップと、を含む、非一時的コンピュータ読み取り可能媒体。
【請求項１４】
請求項１３に記載の少なくとも１つの非一時的コンピュータ読み取り可能媒体であって、前記１群の演算子を選択するステップは、
前記プラン空間における前記演算子の各々にコストを割り当てるステップと、
最も低い合計コストを有する群の演算子を選択するステップと、を含む、非一時的コンピュータ読み取り可能媒体。
【請求項１５】
請求項１１に記載の少なくとも１つの非一時的コンピュータ読み取り可能媒体であって、前記サイクル的サブセット処理は、
サブセット化すべき表に対応する各々全てのエンティティについて、前記要求されたデータのサブセットのうち前記表の中にある部分を規定し、１つ以上の表現を有する、エンティティ・サブセット定義を生成するステップと、
サブセット化すべき表に対応する各々全てのエンティティについて、前記表からステージング表を生成するステップと、を含み、前記ステージング表は、当該エンティティについての前記エンティティ・サブセット定義における前記１つ以上の表現を評価するために必要なデータの列と、前記最終サブセットに特定の行を含めるべきか否かを表すフラグ値の列と、のみを含み、各々のフラグ値は、最初に、当該行における前記データ値が前記サブセット基準を満たす場合には真に設定され、満たさない場合には偽に設定され、前記サイクル的サブセット処理は更に、
各々のエンティティ・サブセット定義における各々全ての表現を再帰的に評価し、前記ステージング表の各々における前記表現を満足する前記行の各々について前記フラグ値を真に変更するステップと、
前記ステージング表の中で真のフラグ値を有する行に対応する、前記複数の表からの行の全てをコンパイルすることにより、１つ以上の最終サブセット表を生成するステップと、を含む、非一時的コンピュータ読み取り可能媒体。
【発明の詳細な説明】
【関連出願データ】
【０００１】
本願は、２０１２年１２月１３日付出願の米国特許出願第１３／７１４，３４９号の優先権を主張する。当該出願は、ここにその全体について引用により援用される。
【背景技術】
【０００２】
企業においては、生産データベース及びデータウェアハウスにある多数の表に亘り大量のデータを保管することが多い。データテスト、データ分析、及びデータ報告といったプロセスを効率的に実行するために、多数の表から情報データセットを一度に抽出することが必要となる場合がある。
【０００３】
例えば、図１は、２つの表１０１，１０２を含む顧客データベースを示す。第１の表１０１には、顧客名及び郵便番号が列挙され、第２の表１０２には、ＩＤ、顧客名及び州が列挙される。第２の表１０２においては、州の欄の値が第１の表１０１中の郵便番号の欄の値に依存するようにデータを入力することができる。この場合、ユーザが表１０２から特定のＩＤ、顧客名及び対応の州についてのデータのサブセットを抽出しようとした場合、参照関係の整合性を確保するために表１０１から対応の郵便番号データも抽出する必要がある。このため、例えばユーザがＩＤ＝１に対応する顧客ＩＤについて州の値に対応するデータサブセットを抽出しようとした場合、データサブセットは、「ロバート」及び「ニューヨーク」の値、並びに１１３５７の値を含むことになる。
【０００４】
図１は簡単な例を示すものであり、多数の表の間に多くのデータ依存関係が存在する場合、適切な表全てからコンパイルするために適切なデータのサブセットを判定することは複雑で多くのリソースを消費するタスクとなる場合がある。多くの状況において、表同士の関係から、データサブセットの計算の際に１以上のサイクルが生じる。これらのサイクルの結果、データサブセット化プロセスは、特定のデータサブセットの計算がサイクル的な関係を伴っているか否かに拘らず、多数の表に亘り大きなデータセットについてのデータサブセットを計算するという問題に対して汎用的な再帰的解決策をしばしば利用しなければならない。
【図面の簡単な説明】
【０００５】
【図１】図１は、２つのデータ表であって、その間にデータ依存関係を有し得るものの例を示す図である。
【図２】図２Ａ〜２Ｃは、開示の実施例に従うエンティティグラフ、エンティティグラフに対応するデータ表、及びサブセット基準に対応するサブセット表を示す図である。
【図３】図３は、開示の実施例に従う、データサブセット要求を処理し、サイクル的エンティティグラフから非サイクル的エンティティグラフを分離する態様を示すフローチャートである。
【図４】図４は、開示の実施例に従うサイクルを有するエンティティグラフを示す図である。
【図５】図５は、開示の実施例に従いエンティティグラフを展開して展開エンティティグラフを生成する態様を示すフローチャートである。
【図６】図６Ａ〜６Ｃは、開示の実施例に従い、非サイクル的展開エンティティグラフを生じさせる展開プロセスの一例を示す図である。
【図７】図７Ａ〜７Ｅは、開示の実施例に従いサイクル的展開エンティティグラフを生じさせる展開プロセスの一例を示す図である。
【図８】図８は、開示の実施例に従う非サイクル的データサブセット処理を示すフローチャートである。
【図９】図９Ａ〜９Ｂは、開示の実施例に従う複数のサブセット表に対応するエンティティ・サブセット定義及び対応の説明を示す図である。
【図１０】図１０Ａ〜１０Ｂは、開示の実施例に従う、図９Ａ〜９Ｂのエンティティ・サブセット定義から生成されたプラン空間を示す図である。
【図１１】図１１は、開示の実施例に従うサイクル的データサブセット処理を示すフローチャートである。
【図１２】図１２は、開示の実施例に従うステージング表の生成を示す図である。
【図１３】図１３は、開示の実施例に従う再帰的評価プロセスにおける１ステップを示す図である。
【図１４】図１４は、開示の実施例に従うデータサブセット化方法を実施するために用いられ得る計算環境の一例を示す図である。
【発明を実施するための形態】
【０００６】
詳細な説明
本明細書において、方法、装置及びコンピュータ読み取り可能媒体を具体例及び実施例によって記載するが、当業者であれば、データサブセット化のための方法、装置及びコンピュータ読み取り可能媒体は、記載の実施例又は図面に限定されないことを認識する。これらの図面及び説明は、開示された特定の形態に限定されることを意図したものではないことを理解すべきであり、添付の特許請求の範囲の趣旨及び範囲内のあらゆる変形例、等価例及び代替例を含むことが意図される。本明細書で用いられる見出しは、いずれも単に本文の構成に関する目的のためのものであり、説明又は特許請求の範囲の範囲を限定することを意図したものではない。本明細書においては、「場合がある／得る／ことがある（ｍａｙ）」という用語は、義務的な意味（即ち、「しなければならない」の意）でなく、許可的な意味（即ち、「可能性を有する」の意）で用いる。同様に、「含む（ｉｎｃｌｕｄｅ，ｉｎｃｌｕｄｉｎｇ，ｉｎｃｌｕｄｅｓ）」という用語は、「含むが、これに限定されない」を意味する。
【０００７】
出願人は、データサブセットの計算にサイクル的計算が伴わない使用ケースを分離する手法を発見した。更に、出願人は、サイクル的使用ケースとは異なる態様で非サイクル的使用ケースを処理する最適化されたデータサブセット化によって、非再帰的プロセスを用いて非サイクル的使用ケースに対してより効率的に対応できるようにするための手段を発見した。
【０００８】
データベースにおける各表は、エンティティグラフを用いてモデル化することができ、各表間の関係もまたこのエンティティグラフにおいて表現される。エンティティグラフは、複数の表を表す複数のエンティティから構成することができ、各々全てのエンティティは、いずれもエンティティグラフ内の他のエンティティに関係付けられる。図２Ａは、３つのデータ表を表す３つのエンティティを伴うエンティティグラフの一例を示し、対応する３つのデータ表を図２Ｂに示す。この３つのエンティティは、「部署」表２１１を表す「部署」２０１、「従業員」表２１２を表す「従業員」２０２、及び「従業員住所」表２１３を表す「従業員住所」２０３である。図２Ｂに示すように、「部署」表２１１は、部署ＩＤ（「ＤＩＤ」）についての列と、部署名についての列とを含む。「従業員」表２１２は、従業員ＩＤ（「ＥＩＤ」）、従業員名、及び部署ＩＤについての各列を含む。「従業員住所」表２１３は、従業員住所ＩＤ（「ＥＤＩＤ」）、従業員ＩＤ、及び州についての各列を含む。
【０００９】
図２Ａのエッジ２０４，２０５は、エンティティグラフ内のエンティティ間の関係、及び、各エンティティが表す下層の各表間の関係を表す。例えば、エッジ２０４は「従業員」２０２から「部署」２０１に延びている。これは、「従業員」２０２及び「部署」２０１が親子関係を有し、「従業員」２０２が子エンティティで「部署」２０１が親エンティティであることを示す。子の表が、親の表の一次キーの参照に記載した他表キーを含む場合、子の表から親の表への関係が規定される。図２Ｂに示すように、「従業員」表２１２は、「部署」表２１１の一次キーである他表キーＤＩＤを含むため、「従業員」表は「部署」表の子となる。
【００１０】
同様に、「従業員住所」２０３から「従業員」２０２へ延びるエッジ２０５は、これら２つのエンティティが親子関係を有しており、「従業員住所」２０３が子で「従業員」２０２が親であることを示す。この関係は、図２Ｂを参照して、「従業員住所」表２１３が、「従業員」表２１２についての一次キーである他表キーＥＩＤを有することを確認することで検証することができる。
【００１１】
エンティティグラフ２００において表される更なる情報として、各々の親と子との間の関係の種類がある。この関係は、ここでは「従業員住所」２０３と「従業員」２０２との間の点線２０５で表される大関係である場合と、ここでは「従業員」２０２と「部署」２０１との間の実線２０４で表される小関係である場合とがある。
【００１２】
参照の整合性とは、表間の関係が一定であり続けることを確保するデータベース概念である。大関係とは、親子関係であって、参照の整合性に基づき、各々全ての子レコードの存在に親レコードの存在が伴う必要があるという制約に加えて、各々全ての親レコードの存在に、その親レコードに関係した各々全ての子レコードの存在が伴うことが必要となるような関係である。小関係とは、親子関係であって、子レコードがサブセット内にある場合に親レコードが当該サブセット内にあることのみを要件とする関係である。小関係は、大関係のように親レコードについての全ての子レコードの取り出しを引き起こすものではない。
【００１３】
図２Ａ〜２Ｃは、データサブセット化の際の大関係及び小関係の動作を示す。図２Ａの点線２０６は、「従業員住所」の州＝ＣＡとなるデータのサブセットに対するユーザの要求を表す。図２Ｃに示すように、この要求に対応する「従業員住所」サブセット２２３は、州＝ＣＡであるレコードを含む。このレコードはまた、ＥＤＩＤが４、ＥＩＤが１００であることを特定する。大関係及び小関係の両方が、子レコードに関係した親レコードを含めることを要件とするため、ＥＩＤが１００のレコードもまた「従業員」表２１２から取り出され、「従業員」サブセット２２２に含められる。しかし、「従業員」２０２と「従業員住所」２０３との関係は「従業員」を親とする大関係であるため、この親レコードに関係した各々全ての子レコードもまた当該サブセットに含めなければならない。この状況においては、このことは、「従業員住所」表２１３においてＥＩＤが１００である各々全てのレコードを「従業員住所」サブセット２２３に含めなければならないことを意味するため、ＥＤＩＤが３、ＥＩＤが１００、州がＷＡであるレコードもまたサブセットへと取り出される。
【００１４】
「部署」表２１１に関し、「部署」２０１と「従業員」２０２との関係は小関係であるため、「部署」表２１１のうち、「従業員」サブセット２２２中で子レコードに対応する親レコードのみをサブセットに含めればよい。「従業員」サブセット２２２内の１つの子レコードはＤＩＤが２２であることを特定しているため、ＤＩＤが２２である対応の親レコードが「部署」表２１１から「部署」サブセット２２１へと取り出される。なお、「従業員」２０２と「部署」２０１との関係は大関係ではなく小関係であるため、「従業員」表２１２のうち、ＤＩＤが２２である追加の対応のレコードを「従業員」サブセット２２２へと取り出すことはない。
【００１５】
以上、エンティティグラフの各構成要素と、これらが一組の表に関係する態様とを説明した。続いて、図３は、エンティティグラフを用いて、サイクルを伴わないデータサブセット化要求を分離する方法を示す。ステップ３０１にて、複数の表からのデータのサブセットに対する要求を受け取る。この要求は、データサブセットについての１以上の基準を含み得る。例えば、先の図２Ａの例においては、サブセット基準は「従業員住所」の州の値が「ＣＡ」と等しいことであった。サブセット基準を用いて、フィルタ基準を１以上の表に与えることでどのデータがデータセットの中にある必要があるかを特定することができる。サブセット基準は、１以上の表における必要な行をフィルタリングするための表現を与えることに加えて、更に、結果に含めるよう認定される行の百分率を特定することでデータセットを制限することができる。エンティティを構成する多数の表についての基準が特定されると、ＡＮＤ及びＯＲの結合子を用いてこれらの基準同士を組み合わせ、与えられた各基準をどのように組み合わせて用いて最終データセットを生成するかを特定することができる。
【００１６】
ステップ３０２にて、複数の表に対応するエンティティグラフがサイクル的であるか否か（１以上のサイクルを含むか否か）を判定する。上述のように、エンティティグラフは、複数の表を表す複数のエンティティと、エンティティ間の複数のエッジに対応し、各表間の関係を表し、親エンティティ及び子エンティティを示すエッジデータと、親エンティティ及び子エンティティ間の関係が大関係か小関係かを示す関係データとを含む。
【００１７】
エンティティをＥiで表し、関係エッジを矢印で表すと、Ｅ１→Ｅ２→…→Ｅ１という経路がある場合、エンティティグラフはサイクルを含む。図４は、サイクルを含むエンティティグラフの一例を示す。エッジが子エンティティから親エンティティに延びることから、Ｅ２はＥ１の親であり、Ｅ３はＥ２の親であり、Ｅ４はＥ３の親であり、Ｅ２はＥ４の親であることが分かる。更に、破線のエッジ４０１は、Ｅ１及びＥ１間の関係が大関係であることを示し、実線のエッジ４０２，４０３，４０４は、小関係を示す。このエンティティグラフにおけるサイクルは、Ｅ２→Ｅ３→Ｅ４→Ｅ２である。サイクルの検出は様々な手段で行うことができる。例えば、各々のエンティティからのあらゆる可能な延出経路を探査することで、元のエンティティに戻る経路があるか否かを判定することができる。
【００１８】
再び図３を参照して、複数の表に対応するエンティティグラフがサイクルを含む場合、ステップ３０３にてサイクル的サブセット処理を実行する。エンティティグラフがサイクルを含まない場合、ステップ３０４にてエンティティグラフを展開して展開エンティティグラフを生成する。ステップ３０５にて、展開エンティティグラフがサイクル的であるか否かを判定する。展開エンティティグラフがサイクルを含まない場合、ステップ３０６にて非サイクル的サブセット処理を実行する。一方、展開エンティティグラフが１以上のサイクルを含む場合、ステップ３０３にてサイクル的サブセット処理を実行する。
【００１９】
次に、図５を参照して、エンティティグラフ展開プロセスを説明する。ステップ５０１にて、エンティティグラフにおける各々全ての大関係につき、大関係中の子エンティティから複製子エンティティを作成する。なお、２つの大関係における子エンティティであるエンティティが存在する場合、これは当該エンティティから２つの複製子エンティティが作成されることを意味する。ステップＳ５０２にて、エンティティグラフにおける各々全ての大関係につき、親エンティティから、ステップ５０１で作成された複製子エンティティへ、エッジを作成する。ステップ５０３にて、エンティティグラフにおける各々全ての大関係につき、その関係における子エンティティ及び親エンティティ間のエッジ以外の子エンティティからの各々全ての延出エッジを削除する。ステップ５０４にて、各々全ての大関係につき、削除した延出エッジを、複製子エンティティへの延出エッジとして追加する。
【００２０】
図６Ａ〜６Ｃは、図２Ａを参照して既述したエンティティグラフへの展開ステップの適用を示す。図６Ａは、「従業員」及び「従業員住所」間の大関係と、「部署」及び「従業員」間の小関係とを有するエンティティグラフの初期バージョンを示す。図６Ｂは、ステップ５０１の後のエンティティグラフの中間バージョンを示し、「従業員」と大関係にある子エンティティである「従業員住所」から複製エンティティである「従業員住所＿１」が作成されたことを示す。図６Ｃは、ステップ５０２の後のエンティティグラフを示し、大関係における親エンティティである「従業員」から、複製子エンティティである「従業員住所＿１」へエッジが作成されたことを示す。展開プロセスのステップ５０３，５０４は、親への延出エッジ以外の大関係における子からの延出エッジを伴い、「従業員住所」は他の延出エッジを有していないことから、これらのステップにおいてエンティティグラフに対する変更は行われず、グラフの最終展開バージョンが図６Ｃに示される。この場合、展開エンティティグラフはサイクルを有さず、非サイクル的サブセット処理を実行することができる。
【００２１】
エンティティグラフ展開プロセスから、展開前にはサイクルを示さないエンティティグラフにおいてサイクルが現れる場合がある。その一例として、２つの延出大関係エッジを有するエンティティを含むエンティティグラフがある。図７Ａを参照して、「従業員住所」が２つの大関係における子エンティティであるエンティティグラフを示す。第１の大関係は、図６Ａに示した先のエンティティグラフと同様に、「従業員」エンティティとのものである。第２の大関係は、従業員の住所に基づいた彼らのオフィス配属を含む表を表し得る「従業員オフィス」エンティティとのものである。
【００２２】
図７Ｂは、展開プロセスにおける第１のステップの後のエンティティグラフの中間バージョンを示す。２つの複製「従業員住所」エンティティが作成されており、「従業員住所＿１」は、「従業員住所」が「従業員」と大関係にある子であることの結果として作成された複製に対応し、「従業員住所＿２」は、「従業員住所」が「従業員オフィス」と大関係にある子であることの結果として作成された複製に対応する。
【００２３】
図７Ｃは、展開プロセスにおける第２のステップの後のエンティティグラフの中間バージョンを示す。親である「従業員」から第１の複製子である「従業員住所＿１」へ延出エッジが追加されており、更に、親である「従業員オフィス」から第２の複製子である「従業員住所＿２」へ延出エッジが追加されている。
【００２４】
図７Ｄは、大関係における子エンティティからの延出エッジのうち、この関係における親への延出エッジを除く全ての延出エッジを削除する第３のステップの後のエンティティグラフの中間バージョンを示す。図７Ｃ〜７Ｄを参照してこのステップを更に詳しく説明する。処理される１つの大関係は、「従業員住所」及び「従業員」間の大関係である。「従業員住所」からの他の唯一の延出エッジは、「従業員オフィス」への延出エッジであるため、これを削除する。もう１つの大関係は、「従業員住所」及び「従業員オフィス」間のものである。この関係における子からの他の唯一の延出エッジである「従業員住所」が「従業員」へのエッジであるため、これも削除する。その結果、延出エッジの残らない「従業員住所」が残される。
【００２５】
次に、図７Ｅを参照して、展開プロセスにおける第４のステップの実行後の最終展開エンティティグラフを示す。「従業員住所」→「従業員」の大関係に関して、「従業員住所＿１」が複製子であり、「従業員住所」→「従業員オフィス」が第３のステップで削除された延出エッジであるため、このエッジを複製子への延出エッジとして追加し、その結果「従業員住所＿１」→「従業員オフィス」のエッジとなる。
【００２６】
同様に、「従業員住所」→「従業員オフィス」の大関係に関して、「従業員住所＿２」が複製子であり、「従業員住所」→「従業員」が、第３のステップで削除された延出エッジであるため、このエッジを複製子への延出エッジとして追加し、その結果「従業員住所＿２」→「従業員」のエッジとなる。
【００２７】
エンティティグラフを図７Ｅの展開エンティティグラフへと展開することによって、当該システムは、展開前のエンティティグラフには存在しなかったサイクルである「従業員」→「従業員住所＿１」→「従業員オフィス」→「従業員住所＿２」→「従業員」のサイクルを検出することができる。これは、エンティティグラフにおける各エンティティによって表される各データ表の依存関係がサイクルを伴うものであり、データサブセット化プロセスはサイクル的サブセット処理を用いて実行すべきであることを意味している。
【００２８】
エンティティグラフ及び展開エンティティグラフがサイクルを含まないと判定された場合、データサブセット化は、非サイクル的サブセット処理によって実行することができる。非サイクル的サブセット化処理は、非再帰的手段によって最適化された態様で実行することができる。
【００２９】
次に、図８を参照して、非サイクル的サブセット処理に伴う各ステップを説明する。ステップ８０１にて、サブセット化すべき表に対応する各々全てのエンティティについて、エンティティ・サブセット定義を生成する。エンティティ・サブセット定義とは、要求されたサブセットのうち、エンティティによって表わされた表の中にある部分を規定するものである。換言すると、エンティティ・サブセット定義は、或る入力サブセット基準についての元の複数の表における特定の表のサブセット表を規定する。
【００３０】
図９Ａは、一組のエンティティ・サブセット定義を示す。非サイクル的処理９０１に対して好適な展開エンティティグラフの上述の例と、「従業員住所」の州＝ＣＡの上述のサブセット基準９００とを用いて、対応するエンティティ・サブセット定義９０２を生成する。エンティティ・サブセット定義９０２の各々は、その末尾に「Ｓ」が付加され、１以上の表現によって、要求されたデータのサブセットを含むことになるサブセット表を規定するものとして考えることができる。そのため、例えば、「従業員＿Ｓ」は、「従業員」表の中で、サブセット基準に対応するデータのサブセットを含む表を規定する。
【００３１】
展開エンティティグラフの中で、サブセット化プロセスの一部となるべきエンティティ全て（これには、「従業員住所＿１＿Ｓ」というエンティティ・サブセット定義を有する「従業員住所＿１」といった複製エンティティも含まれる）について、エンティティ・サブセット定義を生成する。サブセット化プロセスに含めるべきエンティティは、例えば、エンティティグラフの中で、サブセット基準が該当するエンティティに接続されているのはどのエンティティかを評価することによって判定することができる。「従業員住所＿１＿Ｓ」といった、複製エンティティに対応するエンティティ・サブセット定義が存在する場合、このエンティティ・サブセット定義は、表のうちサブセット基準９００に対応する最終サブセットを規定する。従って、図９Ａにおいて、「従業員住所＿１＿Ｓ」は、「従業員」アドレスのうち、最終データサブセットの一部となる行についてのサブセット表を定義する。
【００３２】
これらのエンティティ・サブセット定義は、データログ（Ｄａｔａｌｏｇ）プログラムのシンタックス及び形式を用いて示している。データログとは、シンタックス的に論理型プログラミング言語であるプロログ（Ｐｒｏｌｏｇ）のサブセットである宣言型・論理型プログラミング言語である。なお、エンティティ・サブセット定義の生成の際には、いずれの好適な論理型プログラミング言語又は構造を用いても良いことは言うまでもない。図９Ｂを参照して、各々のエンティティ・サブセット定義の普通語での意味をオブジェクト９０３で示す。例えば、「従業員＿Ｓ」によって規定されるサブセットは、「従業員」のうち、ｅｉｄが「従業員住所＿Ｓ」のサブセットのｅｉｄと一致する全ての行を含む。
【００３３】
再び図８を参照して、ステップ８０２にて、エンティティ・サブセット定義を用いて関係型のプラン空間（ｐｌａｎ  ｓｐａｃｅ）を生成する。関係型プラン空間とは、人工知能の分野で用いられる表現で、特定のゴールからの逆方向の探索を表す手法である。この場合のゴールとは、サブセット基準に対応するエンティティ・サブセット定義によって規定されたサブセット表である。
【００３４】
図９Ａのエンティティ・サブセット定義に対応するプラン空間を図１０に示す。このプラン空間は、エンティティ・サブセット定義によって規定される「従業員住所＿Ｓ」、「従業員＿Ｓ」，「従業員住所＿１＿Ｓ」及び「部署＿Ｓ」のサブセット表を示す菱形のノード１００１，１００２，１００３，１００４を含む。ノード１００５といった長方形のノードは、ノード１００６といった楕円形の演算子によって結果が評価される中間表現を表す。ノード１００７といった長方形のノードに多数のエッジが入っていることは、この表現の値が他の中間結果の計算に再使用されることを示す。
【００３５】
プラン空間は、下方から上方への流れであって、結果としてサブセット表となり得る経路を示すものとして考えることができる。例えば、図１０Ｂは、プラン空間のうち、「従業員住所＿Ｓ」のサブセット表１００１に関係する部分を示す。演算子１０１０において、「従業員住所」表からの完全なデータセットを検索することができる。このデータは、中間表現１０１１として表現することができる。この中間表現１１０１は、フィルタ演算子１０１２によって評価することができ、これは州＝ＣＡとなるレコードをフィルタリングする。このフィルタリング演算の結果を中間表現１０１３において表現することができる。中間表現１０１３は、「従業員住所＿Ｓ」についての結果サブセット表であり得る。
【００３６】
図２Ｂの表２１３の中のデータを用いてこれらのステップを評価することにより、図２Ｃのサブセット表２２３の中のレコードのうちただ１つだけが結果サブセットに含まれることが分かる。既述のように、これは「従業員住所＿Ｓ」に対応するサブセット表が、この例におけるサブセット基準に対応する「従業員」表の最終データサブセット表ではないからである。複製子エンティティである「従業員住所＿１」は展開段階で作成されたものであるため、図１０Ａのノード１００３は、「従業員住所」表のうち、サブセット基準及びエンティティグラフに対応する最終データサブセット表を表す。
【００３７】
再び図８を参照して、ステップ８０２にてプラン空間が生成された後、ステップ８０３にてプラン空間を展開することができる。これを行うために、等価規則を用いて既存の演算子及び中間表現と等価の１以上の追加の演算子及び中間表現を生成する。等価規則では、Ｅ１?Ｅ２となり、これは表現Ｅ１が表現Ｅ２と同じ結果を有することを意味する。例えば、標準的な関係代数から、ｓｅｍｉｊｏｉｎ（Ａ，Ｂ）?ｐｒｏｊｅｃｔＡ（ｉｎｎｅｒｊｏｉｎ（Ａ，Ｂ））であることが分かる。
【００３８】
この書き替え規則は、準結合演算が、同じ２つの表間の内結合演算に第１の表の各列の射影（複製の消去を伴う）が続いたものと等価であることを意味する。
【００３９】
なお、プラン空間の展開には様々な等価規則、例えば、論理等価規則及び関係代数等価規則等を用いることができることは言うまでもない。選択演算、射影演算、結合、設定演算、又はその他任意の関連の演算に関係する等価規則を利用することができる。
【００４０】
等価規則を適用してプラン空間を展開することによって、当該プラン空間における各表現についての代替かつ等価の評価手法を伴う、より大きなプラン空間が得られる。換言すると、展開されたプラン空間によって、サブセット化すべき複数の表の各々から最終データサブセットの各々を計算するための多数の異なる経路が得られる。
【００４１】
プラン空間の展開後、ステップ８０４にて一群の演算子を選択し、ステップ８０５にて、これらの演算子を用いてサブセット基準に対応する１以上の最終サブセット表を算出することができる。この例においては、プラン空間における様々な可能な代替（等価）演算子から一群の演算子（及び対応する経路）を選択し、「従業員住所」の州＝ＣＡのサブセット基準及び表間の（大及び小）関係に対応する「従業員住所」サブセット表、「従業員」サブセット表及び「部署」サブセット表の最終サブセット表を生成することができる。
【００４２】
用いる演算子群の選択は、コストに基づくものであり得る。この場合、コスト値が演算子の各々に割り当てられて、この演算子を利用する望ましさ及び／又は計算コストを反映する。プランのコスト評価は、サブセット化プロセスに関わる物理的ソース及び互いに別個であり得るハードウェア資源を把握した上で実行することができる。例えば、サブセット化対象の各表が互いに対して関係的である場合、この演算における各オペランドは既に互いに関係付けられて格納されているため、下のデータベースへの演算の最大プッシュダウンを達成することが目標であり得る。一方、プッシュダウンが不可能な場合（入力ソースが非関係的、又は結合の両側が異なる物理的ソースに由来する場合）、インフォーマティカ（Ｉｎｆｏｒｍａｔｉｃａ）社のパワーセンター（ＰｏｗｅｒＣｅｎｔｅｒ）ワークフローエンジンなどの特定のワークフローエンジンにおいて後続の各演算子を実行するコストに基づいてコストをこれらの演算子に割り当てることができる。なお、１以上のサブセットを計算するために、ソースからデータを検索することができる任意の好適なミドルウェア又はミドルウェアコンポーネントを利用しても良いことは言うまでもなく、演算子のコスト値は、これらのミドルウェア又はミドルウェアコンポーネントを実行するコストに基づくものとすることができる。
【００４３】
本システムは、サブセット化アルゴリズム及びプラン生成を、計算コストの割り当てプロセスから分離することにより、様々な状況及びインフラにおいてデータサブセット化のために最も低いコストのプランが確実に選択されるようにする。コスト割り当てプロセスまでのアルゴリズムは、ソースの物理的位置及び特性を意識していない。これにより、サブセットの計算に必要なコードが統一され、これがソースの特性から独立したものとなる一方、ソースの物理的な特性を考慮した最適な態様で最終評価が実行されることが確実になる。
【００４４】
次に、再び図３を参照して、サイクル的サブセット処理ステップ３０３をより詳細に説明する。図１１は、開示の実施例に従うサイクル的サブセット処理に伴う各ステップを示すフローチャートである。ステップ１１０１にて、サブセット化すべき表に対応する各々全てのエンティティについて、エンティティ・サブセット定義を生成する。このステップは、非サイクル的サブセット処理に対応する図８のステップ８０１と同じであり、本明細書において上に詳述されている。サイクル的処理の場合における結果として生じるエンティティ・サブセット定義における主な相違点は、エンティティグラフ又は展開エンティティグラフにおいてループが存在するため、エンティティ・サブセット定義のうちの少なくとも1つがそれ自身に関して再帰的に規定されることである。
【００４５】
ステップ１１０２にて、サブセット化すべき表に対応する各々全てのエンティティについて、当該表からステージング表を生成する。ステージング表は、ステップ１１０１のエンティティ・サブセット定義を構成する表現を評価するために必要な列のみを含む。更に、ステージング表は、特定の行が最終サブセットに含めるべきである場合を示す値を有するブール（Ｂｏｏｌｅａｎ）列を含む。最初にステージング表をロードする際、サブセット基準を満足させる行のみについてブール値を真に設定する。
【００４６】
図１２は、「従業員住所」表１２０１から生成され、エンティティ・サブセット定義１２０２に基づく「従業員住所」ステージング表１２０３の一例を示す。同様に、「従業員」ステージング表１２０６は、「従業員」表１２０４から生成され、エンティティ・サブセット定義１２０５に基づく。更に、「従業員住所＿１」ステージング表１２０９は、「従業員住所＿１」表１２０７から生成され、エンティティ・サブセット定義１２０８に基づく。「従業員住所」ステージング表１２０３に示すように、「ｅｄｉｄ」の列は消去されている。エンティティ・サブセット定義における表現のいずれの評価にも必要とされないからである。なお、「ｅｉｄ」列は消去されない。「従業員」ステージング表１２０６に対応する「従業員」エンティティ・サブセット定義１２０５の評価に使用されるからである。同様に、「州」列は、エンティティ・サブセット表現１２０２の評価に用いられるため、消去されない。更に、「従業員住所」ステージング表１２０３及び「従業員」ステージング表１２０６におけるフラグ列は、ステージング表における特定の行が、最終サブセットに含めるべき行に対応するか否かを示す。図１２に示すように、州が「ＣＡ」に等しい行についてのフラグは、「従業員住所」ステージング表１２０３において「１」即ち真に設定されるが、それはこの行が初期サブセット基準を満たすからである。「従業員」ステージング表１２０６におけるフラグは、初期サブセット基準が「従業員」表１２０４を伴わないため、いずれも真に設定されない。「従業員住所＿１」ステージング表１２０９は、ｅｉｄに対応する列及びフラグ列のみを含む。ｅｉｄが関連のエンティティ・サブセット定義１２０８の評価に用いられる唯一の列であるからである。この例においては、表は３つしかなく、「部署」表又は「部署」エンティティ・サブセット定義が存在しないため、「従業員」ステージング表１２０６から「従業員」表１２０４の「ｄｉｄ」列も削除することができる。
【００４７】
再び図１１を参照して、ステップ１１０３にて、各々のエンティティ・サブセット定義における各々全ての表現を再帰的に評価し、対応するステージング表におけるフラグ値を更新して、エンティティ・サブセット定義における各表現を満足する行のフラグが真に設定されるようにする。
【００４８】
図１３は、図１２の３つのステージング表において実行される再帰的評価の一例を示す。初期状態１３０１は、最初にデータを入力された時のステージング表を示し、「従業員住所」ステージング表における州＝「ＣＡ」の行についてのフラグのみが真に設定され、３つの表における他の全てのフラグは偽、即ち「０」に設定される。初期状態１３０１の後、全てのステージング表についてのエンティティ・サブセット定義における各表現を評価する。「従業員」サブセット表についてのエンティティ・サブセット定義は、「従業員住所」サブセット表の中にあるｅｉｄに対応する行が「従業員」サブセット表にあることになることを特定する。フラグ値が真であることは行がサブセット表の中にあることを示し、ｅｉｄが１００の行は真のフラグ値を有するため、ステップ１３０２にて、「従業員」表のうち、やはりｅｉｄが１００である全ての行についてのフラグ値が真に設定される。その結果、ステージング表は、第２の状態１３０３へと更新される。この後、エンティティ・サブセット定義中の全ての表現を再び評価し、ステップ１３０４にて、「従業員住所＿１」ステージング表のうちｅｉｄが１００の行のフラグ値全てが真に設定される。これら３つの表がこの例における表全てであり、エンティティ・サブセット規則は複雑でないため、第３の状態１３０５が最終状態であり、このサブセットについては、再帰的解決策における状態はこれ以上存在しない。
【００４９】
しかし、より多くの状態が存在する場合は、プロセスは係属してフラグを更新し、フラグの変更がなくなるまでエンティティ・サブセット定義を再チェックする場合もある。ステージング表において変化がなくなれば、図１１のステップ１１０４を実行して、サブセット基準に対応する最終データサブセット内の正のフラグ値を有する行全てをコンパイルすることができる。
【００５０】
正のフラグを有する行全てのコンパイルは、ステージング表と、ステージング表の生成に用いる元の入力表との結合演算によって実行することができ、フラグ値が真である行のみが目標の表にコピーされるようにすることができる。なお、ステージング表におけるフラグ値を用いて元の表から関連のある行を抽出又はコンパイルすることで最終サブセットを生成するのに他の手法が存在することは言うまでもなく、ここに開示するシステムはいずれの一技術にも限定されない。
【００５１】
上述の技術のうちの１又はそれ以上は、１以上のコンピュータシステムにおいて実現する、又はこれらを伴うことができる。図１４は、計算環境１４００の一般化した一例を示す。計算環境１４００は、記載の実施例の使用又は機能の範囲についての限定を何ら示唆することを意図したものではない。
【００５２】
図１４を参照して、計算環境１４００は、少なくとも１つの処理部１４１０及びメモリ１４２０を含む。処理部１４１０は、コンピュータ実行可能な命令を実行し、現実又は仮想のプロセッサであり得る。多重処理システムにおいては、多数の処理部がコンピュータ実行可能な命令を実行することで処理能力を増大させる。メモリ１４２０としては、揮発性メモリ（例えばレジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えばＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ等）、又はこれら２つの何らかの組み合わせを用いることができる。メモリ１４２０は、１つ以上のプロセッサによって実行された際に記載の技術を実現するためのソフトウェア命令１４８０を記憶することができる。メモリ１４２０は、１つのメモリデバイスであっても、多数のメモリデバイスであっても良い。
【００５３】
計算環境は更に追加の特徴を有しても良い。例えば、計算環境１４００は、記憶部１４４０、１つ以上の入力装置１４５０、１つ以上の出力装置１４６０、及び１つ以上の通信接続部１４９０を含む。相互接続機構１４７０、例えばバス、コントローラ、又はネットワークが計算環境１４００の各構成要素を相互接続する。一般的には、オペレーティングシステムソフトウェア又はファームウェア（図示せず）によって、計算環境１４００において実行される他のソフトウェアのための動作環境が与えられ、計算環境１４００の各構成要素の作業が調整される。
【００５４】
記憶装置１４４０は、取り外し可能であっても取り外し不可能であっても良く、磁気ディスク、磁気テープ又はカセット、ＣＤ−ＲＯＭ，ＣＤ−ＲＷ、ＤＶＤ，又はその他情報の格納に用いることができ計算環境１４００内でアクセス可能な任意の媒体を含む。記憶部１４４０は、ソフトウェア１４８０のための命令を格納することができる。
【００５５】
入力装置１４５０としては、タッチ式入力装置、例えばキーボード、マウス、ペン、トラックボール、タッチスクリーン、若しくはゲームコントローラ、音声入力装置、スキャン装置、デジタルカメラ、リモコン、又はその他計算環境１４００に入力を行う装置を用いることができる。出力装置１４６０としては、ディスプレイ、テレビ、モニタ、プリンタ、スピーカ、又はその他計算環境１４００から出力を行う装置を用いることができる。
【００５６】
通信接続部１４９０は、通信媒体を介して別の計算エンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令、音声若しくは映像情報、又はその他変調されたデータ信号におけるデータといった情報を伝達する。変調されたデータ信号とは、信号内に情報を符号化するようにその特性の１又はそれ以上が設定又は変更された信号である。一例として（これに限定されない）、通信媒体は、有線又は無線技術であって、電気的、光学的、無線周波、赤外線、音響又はその他のキャリアによって実現されるものを含む。
【００５７】
コンピュータ読み取り可能媒体という一般的なコンテキストで各実現例を記述することができる。コンピュータ読み取り可能媒体は、計算環境内でアクセス可能な任意の利用可能な媒体である。一例として（これに限定されない）、計算環境１４００内において、コンピュータ読み取り可能媒体は、メモリ１４２０、記憶部１４４０、通信媒体、及びこれらのいずれかの組み合わせを含む。
【００５８】
なお、図１４が計算環境１４００、表示装置１４６０、及び入力装置１４５０を別個の装置として示しているのは、特定を容易にするために過ぎないことは言うまでもない。計算環境１４００、表示装置１４６０、及び入力装置１４５０は、別個の装置（例えばパーソナルコンピュータをワイヤでモニタ及びマウスに接続したもの）であっても、単一の装置に統合したもの（例えばスマートホン又はタブレットといったタッチ式ディスプレイを備えた移動装置）であっても、又は装置の任意の組み合わせ（例えば、計算装置をタッチスクリーン表示装置に動作的に結合したもの、複数の計算装置を単一の表示装置及び入力装置に装着したもの等）であっても良い。計算環境１４００としては、セットトップボックス、パーソナルコンピュータ、又は１つ以上のサーバ、例えばネットワーク化されたサーバのファーム、クラスタ化されたサーバ環境、若しくは計算装置のクラウドネットワークを用いることができる。
【００５９】
以上、記載の実施例に関して本発明の各原理を説明及び例示したが、記載の実施例は、このような原理から逸脱することなく構成及び詳細において変更を加えることができることが認識される。ここに記載のプログラム、プロセス、又は方法は、特に明記しない限りいずれの特定の種類の計算環境に関連付け又は限定されることはないことが理解されるべきである。様々な種類の汎用又は専用の計算環境が、ここに記載の教示事項に従う各動作とともに使用されたり、又はこれらを実行したりすることができる。ソフトウェアとして示した記載の実施例の一部の要素をハードウェアで実現しても良く、その逆も可能である。
【００６０】
本発明の各原理を適用できる多数の可能な実施例に鑑み、添付の特許請求の範囲及びその等価物の範囲及び趣旨の中に属することのできる全ての実施例を本発明として請求する。  
【図１】
2016505956.tif 000003
【図２Ａ】
2016505956.tif 000004
【図２Ｂ】
2016505956.tif 000005
【図２Ｃ】
2016505956.tif 000006
【図３】
2016505956.tif 000007
【図４】
2016505956.tif 000008
【図５】
2016505956.tif 000009
【図６Ａ】
2016505956.tif 000010
【図６Ｂ】
2016505956.tif 000011
【図６Ｃ】
2016505956.tif 000012
【図７Ａ】
2016505956.tif 000013
【図７Ｂ】
2016505956.tif 000014
【図７Ｃ】
2016505956.tif 000015
【図７Ｄ】
2016505956.tif 000016
【図７Ｅ】
2016505956.tif 000017
【図８】
2016505956.tif 000018
【図９Ａ】
2016505956.tif 000019
【図９Ｂ】
2016505956.tif 000020
【図１０Ａ】
2016505956.tif 000021
【図１０Ｂ】
2016505956.tif 000022
【図１１】
2016505956.tif 000023
【図１２】
2016505956.tif 000024
【図１３】
2016505956.tif 000025
【図１４】
2016505956.tif 000026
【国際調査報告】
2016505956.tif 000027