(57)【特許請求の範囲】
【請求項１】
プロセッサ上で、
照会ツリー情報および照会ツリー上で実行される動作のうちの少なくとも１つを評価するステップであって、前記照会ツリーは１つまたは複数のノードを含む、評価するステップ、
前記照会ツリー情報および動作のうちの少なくとも１つに基づいてリネージ規則を識別するステップ、および、
前記リネージ規則に基づいて前記照会ツリーのリネージを生成するステップ、
を実行することを含む、照会リネージを生成する方法。
【請求項２】
前記プロセッサ上で、１つまたは複数のリネージ規則を記憶する、リネージ規則データ記憶を維持するステップをさらに実行することを含む、請求項１に記載の方法。
【請求項３】
前記照会ツリー上で前記動作が実行されている間に、前記評価するステップ、前記識別するステップ、および前記生成するステップが実行される、請求項１に記載の方法。
【請求項４】
前記動作が除去タイプの動作である場合、前記プロセッサ上で、リネージ情報を一時的に記憶するステップをさらに実行することを含む、請求項１に記載の方法。
【請求項５】
前記動作が再挿入タイプの動作である場合、前記プロセッサ上で、前記リネージ情報を前記リネージ内に含めるステップをさらに実行することを含む、請求項４に記載の方法。
【請求項６】
前記リネージを生成するステップが、前記照会ツリーの前記リネージを生成するために前記リネージ規則に関連付けられた論理を実行するステップを含む、請求項１に記載の方法。
【請求項７】
前記動作が削除、交換、追加、および移動のうちの少なくとも１つを含む、請求項６に記載の方法。
【請求項８】
前記動作が削除である場合、前記関連付けられた規則が前記照会ツリーの削除されたノードから前記照会ツリーの親ノードへとリネージ情報をコピーする、請求項７に記載の方法。
【請求項９】
前記動作が交換である場合、前記関連付けられた規則が前記照会ツリーのターゲット・ノードから前記照会ツリーの交換されるノードへとリネージ情報をコピーする、請求項７に記載の方法。
【請求項１０】
前記動作が移動である場合、前記照会ツリーの前記ノードが子ノードに関連付けられているかどうかを決定し、前記ノードが子ノードに関連付けられている場合、前記関連付けられた規則が前記ノードから前記子ノードへとリネージ情報をコピーする、請求項７に記載の方法。
【請求項１１】
コンピュータ読み取り可能媒体を備える、照会リネージを生成するためのシステムであって、
前記コンピュータ読み取り可能媒体が、
少なくとも１つのリネージ規則を記憶するリネージ規則データ記憶と、
照会ツリー上で実行される動作および照会ツリー情報のうちの少なくとも１つを評価し、前記照会ツリーは１つまたは複数のノードを含み、前記動作および照会ツリー情報のうちの少なくとも１つと前記リネージ規則データ記憶からのリネージ規則とに基づいて前記照会ツリーのリネージを生成する、リネージ・サービスと、
を含む、システム。
【請求項１２】
前記照会ツリー上で前記動作が実行されている間に、前記リネージ・サービスが前記生成することを実行する、請求項１１に記載のシステム。
【請求項１３】
前記動作が除去タイプの動作である場合、前記リネージ・サービスがリネージ情報を一時的に記憶する、請求項１１に記載のシステム。
【請求項１４】
前記動作が再挿入タイプの動作である場合、前記リネージ・サービスが前記リネージ情報を前記リネージ内に含める、請求項１３に記載のシステム。
【請求項１５】
前記照会ツリーの前記リネージを生成するために前記リネージ規則に関連付けられた論理を実行することによって、前記リネージ・サービスが前記リネージを生成する、請求項１１に記載のシステム。
【請求項１６】
前記動作が削除、交換、追加、および移動のうちの少なくとも１つを含む、請求項１５に記載のシステム。
【請求項１７】
前記動作が削除である場合、前記関連付けられた規則が前記照会ツリーの削除されたノードから前記照会ツリーの親ノードへとリネージ情報をコピーする、請求項１６に記載のシステム。
【請求項１８】
前記動作が交換である場合、前記関連付けられた規則が前記照会ツリーのターゲット・ノードから前記照会ツリーの交換されるノードへとリネージ情報をコピーする、請求項１６に記載のシステム。
【請求項１９】
前記動作が移動である場合、前記照会ツリーの前記ノードが子ノードに関連付けられているかどうかを前記リネージ・サービスが決定し、前記ノードが子ノードに関連付けられている場合、前記関連付けられた規則が前記ノードから前記子ノードへとリネージ情報をコピーする、請求項１６に記載のシステム。
【請求項２０】
請求項１から１０のいずれか一項に記載の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は照会リネージを自動的に生成するためのシステム、方法、およびコンピュータ・プログラムに関する。
【背景技術】
【０００２】
データベース照会に関する実行プランを生成する照会のプランニングおよび最適化段階の間、通常、照会は何らかの形のツリーで表される。照会ツリーには、第１に正しいデータが取り出されること、および第２に、データが効率的かつできる限り迅速に取り出されることを、保証する規則が適用される。これらの規則は、規則の適用前後での照会ツリーの意味的等価を保証するものである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
このプロセス中はいつでも、元の照会における構成体と、照会ツリーの現行状態におけるこれに関するものとの間の関係、および同様に、現行の照会ツリーにおける構成体と元の照会における構成体との間の関係を、決定できることが望ましい場合がある。この情報は「リネージ（lineage）」と呼ばれ、照会ツリー内のいずれのオブジェクトも、元の照会におけるその先行要素（ancestor）（そのリネージ）をさかのぼって追跡できるようにするものである。
【課題を解決するための手段】
【０００４】
例示的実施形態では、照会リネージを生成する方法が提供される。この方法は、プロセッサ上で実行すること、照会ツリー情報および照会ツリー上で実行される動作のうちの少なくとも１つを評価することであって、照会ツリーは１つまたは複数のノードを含む、評価すること、照会ツリー情報および動作のうちの少なくとも１つに基づいてリネージ規則を識別すること、ならびに、リネージ規則に基づいて照会ツリーのリネージを生成することを含む。
【０００５】
第１の態様から見ると、本発明は、プロセッサ上で実行すること、照会ツリー情報および照会ツリー上で実行される動作のうちの少なくとも１つを評価することであって、照会ツリーは１つまたは複数のノードを含む、評価すること、照会ツリー情報および動作のうちの少なくとも１つに基づいてリネージ規則を識別すること、ならびに、リネージ規則に基づいて照会ツリーのリネージを生成することを含む、照会リネージを生成する方法を提供する。
【０００６】
好ましくは、本発明は、１つまたは複数のリネージ規則を記憶する、リネージ規則データ記憶を維持することをさらに含む、方法を提供する。
【０００７】
好ましくは、本発明は、照会ツリー上で動作が実行されている間に、評価すること、識別すること、および生成することが実行される、方法を提供する。
【０００８】
好ましくは、本発明は、動作が除去タイプの動作である場合、リネージ情報を一時的に記憶することをさらに含む、方法を提供する。
【０００９】
好ましくは、本発明は、動作が再挿入タイプの動作である場合、リネージ情報をリネージ内に含めることをさらに含む、方法を提供する。
【００１０】
好ましくは、本発明は、リネージを生成することが、照会ツリーのリネージを生成するためにリネージ規則に関連付けられた論理を実行することを含む、方法を提供する。
【００１１】
好ましくは、本発明は、動作が削除、交換、追加、および移動のうちの少なくとも１つを含む、方法を提供する。
【００１２】
好ましくは、本発明は、動作が削除である場合、関連付けられた規則が照会ツリーの削除されたノードから照会ツリーの親ノードへとリネージ情報をコピーする、方法を提供する。
【００１３】
好ましくは、本発明は、動作が交換である場合、関連付けられた規則が照会ツリーのターゲット・ノードから照会ツリーの交換されるノードへとリネージ情報をコピーする、方法を提供する。
【００１４】
好ましくは、本発明は、動作が移動である場合、照会ツリーのノードが子ノードに関連付けられているかどうかを決定し、ノードが子ノードに関連付けられている場合、関連付けられた規則がノードから子ノードへとリネージ情報をコピーする、方法を提供する。
【００１５】
第２の態様から見ると、本発明は、少なくとも１つのリネージ規則を記憶するリネージ規則データ記憶と、照会ツリー上で実行される動作および照会ツリー情報のうちの少なくとも１つを評価し、照会ツリーは１つまたは複数のノードを含み、動作および照会ツリー情報のうちの少なくとも１つとリネージ規則データ記憶からのリネージ規則とに基づいて照会ツリーのリネージを生成する、リネージ・サービスとを含む、コンピュータ読み取り可能媒体を備える、照会リネージを生成するためのシステムを提供する。
【００１６】
好ましくは、本発明は、照会ツリー上で動作が実行されている間に、リネージ・サービスが生成することを実行する、システムを提供する。
【００１７】
好ましくは、本発明は、動作が除去タイプの動作である場合、リネージ・サービスがリネージ情報を一時的に記憶する、システムを提供する。
【００１８】
好ましくは、本発明は、動作が再挿入タイプの動作である場合、リネージ・サービスがリネージ情報をリネージ内に含める、システムを提供する。
【００１９】
好ましくは、本発明は、照会ツリーのリネージを生成するためにリネージ規則に関連付けられた論理を実行することによって、リネージ・サービスがリネージを生成する、システムを提供する。
【００２０】
好ましくは、本発明は、動作が削除、交換、追加、および移動のうちの少なくとも１つを含む、システムを提供する。
【００２１】
好ましくは、本発明は、動作が削除である場合、関連付けられた規則が照会ツリーの削除されたノードから照会ツリーの親ノードへとリネージ情報をコピーする、システムを提供する。
【００２２】
好ましくは、本発明は、動作が交換である場合、関連付けられた規則が照会ツリーのターゲット・ノードから照会ツリーの交換されるノードへとリネージ情報をコピーする、システムを提供する。
【００２３】
好ましくは、本発明は、動作が移動である場合、照会ツリーのノードが子ノードに関連付けられているかどうかをリネージ・サービスが決定し、ノードが子ノードに関連付けられている場合、関連付けられた規則がノードから子ノードへとリネージ情報をコピーする、システムを提供する。
【００２４】
第３の態様から見ると、本発明は、コンピュータ・システムにロードされ、実行された場合、前述の方法のすべてのステップを実行するためのコンピュータ・プログラム・コードを備える、コンピュータ・プログラムを提供する。
【００２５】
次に、本発明の諸実施形態について、添付の図面を参照しながら単なる例として説明する。
【図面の簡単な説明】
【００２６】
【図１】例示的実施形態に従った、リネージ生成システムを含むコンピューティング・システムを示すブロック図である。
【図２】例示的実施形態に従った、図１のリネージ生成システムを示すデータフロー図である。
【図３】例示的実施形態に従った、図１のリネージ生成システムを示すデータフロー図である。
【図４】例示的実施形態に従った、様々な動作に基づく図１のリネージ生成システムの結果として生じる、様々な照会ツリーおよびリネージを示す図である。
【図５】例示的実施形態に従った、様々な動作に基づく図１のリネージ生成システムの結果として生じる、様々な照会ツリーおよびリネージを示す図である。
【図６】例示的実施形態に従った、様々な動作に基づく図１のリネージ生成システムの結果として生じる、様々な照会ツリーおよびリネージを示す図である。
【図７】例示的実施形態に従った、リネージ生成方法を示す流れ図である。
【発明を実施するための形態】
【００２７】
本発明の例示的実施形態に従った、データベース照会ツリーに関するリネージの生成を自動化する、リネージ生成システムが提供される。理解され得るように、以下の説明は事実上単なる例示であり、本開示、適用範囲、または使用を制限することは意図されていない。図面全体を通じて、対応する参照番号は同様または対応する部分および特徴を示すことを理解されたい。
【００２８】
次に図１を見ると、ブロック図は、本開示に従ったリネージ生成システム（ＬＧＳ）を含む例示的コンピューティング・システム１００を示す。コンピューティング・システム１００は、コンピュータ１０１を含むように示される。理解され得るように、コンピューティング・システム１００は、デスクトップ・コンピュータ、ラップトップ、サーバ、ポータブル・ハンドヘルド・デバイス、または任意の他の電子デバイスを含むがこれに限定されない、任意のコンピューティング・デバイスを含むことが可能である。考察しやすいように、本開示についてはコンピュータ１０１との関連において論じられる。
【００２９】
コンピュータ１０１は、プロセッサ１０２、メモリ・コントローラ１０６に結合されたメモリ１０４、論理入力／出力コントローラ１１２を介して通信可能に結合された１つまたは複数の入力あるいは出力またはその両方（Ｉ／Ｏ）のデバイス１０８、１１０（または周辺デバイス）、および、ディスプレイ１１６に結合されたディスプレイ・コントローラ１１４を含むように示される。例示的実施形態では、従来型のキーボード１２２およびマウス１２４を入力／出力コントローラ１１２に結合することができる。例示的実施形態では、コンピューティング・システム１００は、ネットワーク１２０に結合するためのネットワーク・インターフェース１１８をさらに含むことができる。ネットワーク１２０は、コンピュータ１０１と、本開示のログイン生成システムを同様に含む他のコンピューティング・システム（図示せず）などの外部システムとの間で、データを送受信する。
【００３０】
様々な実施形態では、メモリ１０４は、プロセッサ１０２による実行が可能な命令を記憶する。メモリ１０４に記憶された命令は、１つまたは複数の別々のプログラムを含むことが可能であり、そのそれぞれが論理機能を実施するための実行可能命令の順序付きリストを備える。図１の例では、メモリ１０４に記憶された命令は、好適なオペレーティング・システム（ＯＳ）１２６を含む。オペレーティング・システム１２６は、本質的に、他のコンピュータ・プログラムの性能を制御し、スケジューリング、入力出力制御、ファイルおよびデータ管理、メモリ管理、ならびに通信制御および関連サービスを提供する。
【００３１】
コンピュータ１０１が動作中の場合、プロセッサ１０２は、メモリ１０４内に記憶された命令を実行すること、メモリ１０４との間でデータを通信すること、および、一般に、命令に従ってコンピュータ１０１の動作を制御することを、実行するように構成される。プロセッサ１０２は、任意の特注または市販のプロセッサ、中央処理ユニット（ＣＰＵ）、コンピュータ１０１に関連付けられたいくつかのプロセッサの間の補助プロセッサ、（マイクロチップまたはチップ・セットの形の）半導体ベース・マイクロプロセッサ、マクロプロセッサ、あるいは、命令を実行するための一般に任意のデバイスとすることができる。
【００３２】
プロセッサ１０２は、本開示のリネージ生成システム１２８の命令を実行する。様々な実施形態では、本開示のリネージ生成システム１２８は何らかの形のコンピュータ読み取り可能媒体に組み込まれ、たとえばリネージ生成システム１２８は、メモリ１０４（図示）内に記憶される、ポータブル・ストレージ・デバイス（たとえばＣＤ−ＲＯＭ、ディスケット、FlashDriveなど）（図示せず）から実行される、あるいは、中央サーバ（図示せず）などのリモート位置から実行される、またはそれらすべてが行われる。
【００３３】
概して、リネージ生成システム１２８は、たとえばデータベース上で実行される照会のリネージを生成する。様々な実施形態では、リネージ生成システム１２８は、新規または既存の照会プランニングまたは最適化エンジン内に提供可能である。様々な他の実施形態では、リネージ生成システム１２８は、スタンドアロン型アプリケーション、プラグイン・アプリケーション、あるいは、適用可能であり本開示に従った任意の他のタイプのアプリケーションとして、またはそれらすべてとして、実装可能である。リネージ生成システム１２８は、たとえばエラー・メッセージに関するコンテキスト情報として、または、分析の目的でログ・ファイルに書き込まれたデータとして、システム１２８内で、または他のアプリケーションによって使用可能な、情報を生じさせる。ログ・ファイルは、たとえばリネージ情報を視覚化できるような、リネージ・インターフェース１３０を生成するために使用可能である。
【００３４】
様々な実施形態では、リネージ生成システム１２８は、照会プランニングまたは最適化エンジン内に存在する、ツリー操作ルーチン（たとえば、追加、削除、移動など）あるいはツリー情報またはその両方を使用する。したがって照会リネージ情報は、照会の作成者にトランスペアレントな形で提供可能である。
【００３５】
次に図２を見ると、例示的実施形態に従ったリネージ生成システム１２８が、より詳細に示されている。リネージ生成システム１２８は、１つまたは複数のサブモジュールおよびデータ記憶を含む。理解され得るように、サブモジュールおよびデータ記憶は、１つまたは複数のコンピュータ・システム上に常駐可能である。さらに理解され得るように、図２に示されたサブモジュールは、同様にリネージを生成するために、組み合わせること、あるいはさらに区分すること、またはその両方が可能である。この例では、リネージ生成システム１２８は、リネージ・サービス・モジュール１４０および規則データ記憶１４２を含む。
【００３６】
リネージ・サービス・モジュール１４０は、入力として動作１４４ａを受信する。動作１４４ａは、照会プランニングまたは最適化エンジン（図示せず）との開発者の対話に基づいて生成可能である。一例では、動作は、新しい照会ツリー１４５の構成を示す。動作１４４ａに基づき、リネージ・サービス・モジュール１４０はリネージ・サービス１４６を開始し、リネージ・サービス１４６を特定の照会ツリー１４５のプランニングに関連付ける。リネージ・サービス１４６は、照会に関連付けられた照会ツリー１４５上で実行されるその後の動作１４４ｂ、照会ツリー情報１４７、あるいは動作状況１４８、またはそれらすべてを監視する。動作１４４ｂ、照会ツリー情報１４７、あるいは動作状況１４８、またはそれらすべてに基づき、リネージ・サービス１４６は、照会リネージ１５０を展開するために規則データ記憶１４２とインターフェースする。
【００３７】
規則データ記憶１４２は、１つまたは複数のリネージ規則１５２を記憶する。各リネージ規則１５２は、特定の動作１４４ｂあるいは照会ツリー情報１４７またはその両方と関連付けることができる。リネージ規則１５２は、任意の時点で照会ツリー１４５内に残留しているノードと、元の照会ツリー１４５内のノードとの関係、およびその逆の関係を捕捉するための論理を含むことができる。いくつかのケースでは、リネージ情報は失われる可能性がある（一部の情報は実際には最終照会において重要でない可能性がある）が、多くのケースでは、照会ツリーの現行状態におけるノードと初期の照会ツリー１４５におけるノードとの間に、多対多の関係が存在する。
【００３８】
次に図３を見ると、リネージ・サービス１４６は、たとえば、リネージ初期化モジュール１５４および動作監視モジュール１５６を含む。リネージ初期化モジュール１５４は、入力として初期の動作１４４ａおよび初期の照会ツリー１４５を受信する。初期の動作１４４ａおよび初期の照会ツリー１４５に基づいて、リネージ初期化モジュール１５４は、照会ツリー１４５内の各ノードに初期リネージ１６０を割り当てる。たとえば、各ノードに関するリネージは、ノードの存在が依存し、初期には（そのうちの１つが、初期の照会ツリー内の各ノードに、およびその後のプランニング・プロセス中に生成される各ノードに割り当てられる、初期の照会ツリーのコピー内のノードへの参照／ポインタとして、または、固有の識別子としての）それ自体への参照である、ノードのコンテナを含む。様々な実施形態では、リネージ・サービス１４６が個々の照会ツリー操作動作１４４ｂ全体にわたる情報を保持するため、リネージ・サービス１４６への参照は、照会ツリー１４５の各ノード内で保持される。
【００３９】
その後、動作監視モジュール１５６は、その特定の照会ツリー１４５上で実行され、照会ツリー１４５の変形または操作を表す、他の動作１４４ｂを監視する。動作１４４ｂは、たとえば追加、削除、および移動を含むことができるが、これらに限定されない。動作通知１４４ｂは、典型的には、照会ツリー１４５への各変形または操作の適用開始時に生成される。動作１４４ｂ（たとえばノードの追加、ノードの削除、ノードの移動など）が照会ツリー１４５に適用される間、または適用された後、リネージ・サービス・モジュール１４０は、動作１４４ｂあるいは照会ツリー情報１４７またはその両方に基づいて、さらに規則データ記憶１４２に記憶された１つまたは複数の規則１５２に基づいて、１つまたは複数のノードに関連付けられたリネージ１５０を更新する。
【００４０】
たとえば、動作監視モジュール１５６は、１つまたは複数の動作１４４ｂあるいは照会ツリー情報１４７またはその両方を、特定の規則１５２に関連付ける。規則１５２あるいは規則１５２を実装する論理またはその両方は、規則データ記憶１４２から取り出される。その後、規則１５２あるいは論理またはその両方は、適切なリネージ１５０を決定するために実行される。
【００４１】
一例では、動作１４４ｂが、削除、交換、追加、あるいは移動、またはそれらすべてなどであるが、それらに限定されない、変形を示す場合、以下の規則１５２を定義することができる。削除動作に関連付けられた規則１５２は、削除されたノードのリネージを、削除されたノードの親のリネージに転送する。交換動作に関連付けられた規則１５２は、ターゲット・ノードのリネージを、移動されるノードにコピーする。追加動作に関連付けられた規則１５２は、リネージに対していかなる影響も与えない。移動動作に関連付けられた規則１５２は、リネージに対していかなる影響も与えない。子移動動作に関連付けられた規則１５２は、子ノードを移動する前に、親ノードのリネージを子ノードに転送する。子が存在しない場合、ノードのリネージは親ノードに移動される。
【００４２】
様々な実施形態では、いくつかの動作１４４ｂがリネージの即時転送を生じさせる一方で、その他は遅延の影響を与える。動作が、照会ツリー１４５からの何らかの形のノードの除去（たとえば分離、交換、抽出、削除など）を示すインスタンスでは、同じ変形において、そのノードが照会ツリー１４５内に再挿入される可能性がある。したがって、リネージ１５０の完了は、ノードの再挿入まで遅延される。
【００４３】
たとえば、動作１４４ｂが、照会ツリー１４５からの何らかの形のノードの除去または削除を指定する場合、様々な実施形態では、除去または削除されたノードのリネージ１５０の可能な受信者を決定するための規則１５２が適用される。その後、動作監視モジュール１５６は、ノードが照会ツリー１４５に再挿入されるまで、除去されたノードと共にこの情報を一時的に記憶するか、または、ノードは永続的に削除される。
【００４４】
変形が完了すると、動作監視モジュール１５６には、変形が完了した旨が動作状況１４８を介して通知される。その後、動作監視モジュール１５６は、一時的に記憶された情報に基づいて、変形に関連付けられたリネージ操作を完了する。動作監視モジュール１５６は、いずれかの動作１４４ｂがいずれかの除去されたノードを照会ツリー１４５に再挿入するかどうかを決定する。こうしたケースでは、規則１５２は、リネージ１５０が再挿入されたノードと共に残留するよう規定する。他方で、ノードを照会ツリー１４５に再挿入しないことも可能である。こうしたケースでは、規則１５２は、対応するリネージ１５０が照会ツリー内の他のノードに転送されること、あるいは削除されるべきであること、またはその両方を規定する。
【００４５】
たとえば、除去されたノードが親ノードを有する場合、規則１５２は、除去されたノードのリネージ１５０を親ノードへとコピーする。さもなければ、除去されたノードが親を有さない場合、リネージ１５０は削除される。
【００４６】
様々な実施形態では、規則１５２は、動作１４４ｂではなく照会ツリー情報に基づくものとすることができる。たとえば規則１５２は、ノードのタイプ、またはそれ自体に関連してノードに関する情報に、基づくことができる。
【００４７】
上記の例では、照会ツリー１４５内のノードを移動することはノードのリネージに影響を与えず、リネージは単にノードと共に転送する。しかしながら他の例では、照会ツリー１４５の１つの領域から他の領域へとノードを移動することは、この挙動がもはやその内部では適用可能でない範囲を有する場合があることが、あてはまる可能性がある。
【００４８】
たとえば、タイプ「Ｘ」のノードが、常にタイプ「Ｙ」の他のノードの（直接または直接でない）後続要素として存在する場合、特定の実装は、タイプ「Ｚ」の先行要素が変更されなければ、照会に関するデフォルトの「移動」セマンティクスを適用することができる。関連付けられた規則１５２は、タイプ「Ｚ」の先行要素が移動動作の結果として変更された場合、ノードのリネージはたとえば親に転送されるものとすることができる。この例では、リネージ転送を実行するために使用される規則１５２は、単に実行される動作１４４ｂに基づくだけでなく、ノードまたは内部にノードが存在する照会ツリー１４５に限定されることはない。
【００４９】
理解され得るように、上記の規則１５２は、照会プランニングまたは最適化エンジンの様々な実装に対処するように修正可能である。たとえば、同様の規則を、異なる動作または異なる照会ツリー情報に適用することができる。
【００５０】
図４〜図５は、様々な照会ツリー上で実行される特定の動作の結果として生じる、例示的リネージを示す。理解され得るように、照会ツリー情報あるいは照会ツリーに関連付けられた動作またはその両方に基づいて、同様のリネージを生成することができる。
【００５１】
図４は、１から８までのノードを含む、第１の照会ツリー２００を示す。動作２０２は、ノード４が削除され、ノード５がノード８に再接続されることを示す。結果として生じるリネージ２０６は、親ノード２にコピーされる削除されたノードのリネージを含む。したがって、削除されたノード２０８は、ノード４およびノード６を含む。
【００５２】
図５は、ノード１から６およびノード８を含む、第２の照会ツリー２１０に関するリネージを示す。動作２１２は、ノード４が新規ノードと交換され、ノード６がノード８に接続されることを示す。結果として生じるリネージ２１４は、削除されたノード４および５が新規ノードにコピーされるリネージを含む。したがって、削除されたノード２１６はノード５を含む。
【００５３】
図６は、ノード１から６、ノード８、およびノード１０を含む、第３の照会ツリー２２０に関するリネージを示す。動作２２２は、ノード５が抽出され、再接続されないことを示す。結果として生じるリネージ２２４は、子ノード５、６、および１０にコピーされるノード４に関するリネージを含む。したがって、削除されたノード２２６は、ノード５を含む。
【００５４】
次に、引き続き図２および図３を参照しながら図７を見ると、流れ図は、例示的実施形態に従った、図２および図３のリネージ生成システム１２８によって実行可能なリネージ生成方法を示す。本開示に鑑みて理解され得るように、方法内の動作の順序は、図７に示された実行順序に限定されるものではなく、適用可能であり、本開示に従った、１つまたは複数の変形順序で実行可能である。理解され得るように、本発明の趣旨を変更することなく、１つまたは複数のステップを方法に追加するか、または方法から削除することが可能である。
【００５５】
一例では、方法は３００で開始することができる。たとえば照会のプランニングまたは最適化エンジンからの動作１４４ａが、３１０で監視される。動作１４４ａが、新しい照会ツリー１４５が３１０で構成されたことを示す場合、３２０でリネージ・サービス１４６が開始され、新しい照会ツリー１４５に関連付けられる。しかしながら、３１０で新しい照会ツリー１４５が構成されない場合、方法は、３１０で新しい照会ツリー１４５が構成されるまで、動作１４４ａの監視を続行する。
【００５６】
リネージ・サービス１４６は、いったん開始されると、３３０〜３５０で、照会ツリー１４５あるいは照会ツリー情報１４７またはその両方での、その後のすべての動作１４４ｂを監視する。たとえば、３３０で動作１４４ｂが除去動作を示す場合、３６０で、リネージ１５０は除去されたノードから親ノードにコピーされる。その後、除去されたノードに関するリネージ情報およびノード情報は、３７０で、後続の評価のために一時的に記憶される。しかしながら、３４０で動作１４４ｂが交換動作を示す場合、３８０で、ターゲット・ノードのリネージ１５０は移動されるノードにコピーされる。３５０で、動作が移動動作を示す場合、３９０で、ノードが子を有するかどうかが決定される。３９０でノードが子を有する場合、４００で、親ノードのリネージ１５０が各子ノードに関するリネージ１５０にコピーされる。３９０で、ノードがいかなる子も有さない場合、４１０で、ノードのリネージ１５０は親ノードに移動される。
【００５７】
しかしながら、３３０〜３５０で、動作が除去動作、交換動作、または移動動作を示さない場合、３６５で、動作状況１４８が評価される。３６５で、動作状況１４８が変形の完了したことを示す場合、４２０で、いずれかの除去されたノードが再挿入されたかどうかが決定される。４２０で、除去されたノードが照会ツリー１４５に再挿入された場合、４３０で、リネージ１５０を含むノードに関する一時的に記憶された情報が、再挿入されたノードにコピーされる。その後、方法は４４０で終了することができる。
【００５８】
理解され得るように、図内の流れ図およびブロック図は、本開示の様々な実施形態に従った、システム、方法、およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能、および動作を示す。この関連で、流れ図またはブロック図における各ブロックは、指定された論理機能を実装するための１つまたは複数の実行可能な命令を含む、モジュール、セグメント、またはコードの一部を表すことができる。いくつかの代替の実装では、ブロック内に示された機能は、図内に示された順序とは異なる順序で実行可能であることにも留意されたい。たとえば、連続して示された２つのブロックは、実際にはほぼ同時に実行可能であるか、またはブロックは、含まれる機能に応じて時には逆の順序で実行可能である。ブロック図あるいは流れ図またはその両方の各ブロック、ならびに、ブロック図あるいは流れ図またはその両方におけるブロックの組み合わせは、指定された機能または活動を実行する特定用途向けハードウェア・ベース・システム、あるいは特定用途向けハードウェアおよびコンピュータ命令の組み合わせによって実装可能であることにも留意されよう。
【００５９】
一例として、本開示の１つまたは複数の態様は、たとえばコンピュータ使用可能媒体を有する製造品（たとえば１つまたは複数のコンピュータ・プログラム製品）に含めることが可能である。媒体は、たとえば、本開示の機能を提供および容易にするためのコンピュータ読み取り可能プログラム・コード手段内で具体化される。製造品は、コンピュータ・システムの一部として含めるか、または別々に提供することができる。
【００６０】
加えて、機械によって読み取り可能であり、本開示の機能を実行するために機械によって実行可能な命令の少なくとも１つのプログラムを有形に具体化する、少なくとも１つのプログラム記憶デバイスが、提供可能である。
【００６１】
本発明の動作を実行するためのコンピュータ・プログラム・コードは、オブジェクト指向プログラミング言語など、および、「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続き型プログラミング言語を含む、１つまたは複数のプログラミング言語の任意の組み合わせで作成可能である。プログラム・コードは、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンドアロン型ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上であり部分的にリモート・コンピュータ上で、あるいは、完全にリモート・コンピュータまたはサーバ上で、実行可能である。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む、任意のタイプのネットワークを介して、ユーザのコンピュータに接続可能であるか、あるいは、（たとえば、インターネット・サービス・プロバイダを使用してインターネットを介して）外部コンピュータに接続することができる。
【００６２】
以上、好ましい実施形態について説明してきたが、当業者であれば、現在、また今後においても、以下の特許請求の範囲内に入る様々な改良および機能強化が可能であることを理解されよう。これらの特許請求の範囲は、第１に記載された開示に関する適切な保護を維持するものと解釈されたい。
【００６３】
本明細書で使用される用語は、特定の実施形態を説明するためのみのものであり、本発明を限定することは意図されていない。本明細書で使用される場合、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈が明示的に示していない限り、複数形も含むことが意図されている。以下の特許請求の範囲におけるすべての手段またはステップならびに機能要素の、対応する構造、機能、材料、活動、および等価物は、具体的に請求された他の請求要素と組み合わせて機能を実行するための、任意の構造、材料、または活動を含むことが意図されている。開示は、例示および説明のために提示されてきたが、開示された形の本発明を網羅するかまたはこれに限定されるものとは意図されていない。当業者であれば、本発明の範囲を逸脱することなく、多くの修正および変形が明らかとなろう。諸実施形態は、本発明の原理および実際の適用例を最もよく説明するために、ならびに、企図される特定の用途に好適な様々な修正を伴う様々な実施形態に関して他の当業者が本発明を理解できるようにするために、選択および説明したものである。
【図１】
0005602871.tif 000002
【図２】
0005602871.tif 000003
【図３】
0005602871.tif 000004
【図４】
0005602871.tif 000005
【図５】
0005602871.tif 000006
【図６】
0005602871.tif 000007
【図７】
0005602871.tif 000008