(57)【特許請求の範囲】
【請求項１】
データベース内の少なくとも三つのテーブルのセットから、結合属性のセットＳにおける結合条件に基づいてレコードを結合する方法であって、
前記結合属性ＳをシーケンスＳ０のオーダーに配列し、
スコープＣを空に初期化し、 
前記テーブルのセットからシーケンスＳ０の最初のオーダーの結合属性Ａを含むテーブルを特定し、
前記シーケンスＳ０から結合属性Ａを除いた新規のシーケンスＳ'を生成し、
そのインデックスキーが前記シーケンスＳ０のオーダーで特定されたテーブルの全ての結合属性を含む、当該特定された各テーブルのツリーインデックス構造に基づいて、前記結合属性Ａのオーダーに従い、前記特定されたテーブルのそれぞれに対して反復し、
前記反復中の結合属性の一致した値ｖのそれぞれに対して、前記スコープＣに「Ａ＝v」を追加して新しいスコープＣｖを生成し、
前記シーケンスＳ'が空かどうかを判定し、
前記シーケンスＳ'が空の場合は、各ｖに対して前記スコープＣｖに対応したタプルを出力し、
前記シーケンスＳ'が空でない場合は、シーケンスＳ０をシーケンスＳ'にセットし、それぞれのスコープＣｖに対して、スコープＣをスコープＣｖにセットし、再帰的に、前記特定ステップ、生成ステップ、反復ステップ、追加ステップ、判定ステップ、出力ステップを呼び出すことを特徴とする方法。
【請求項２】
前記シーケンスＳ０は、非プレフィックスコヒーレントのオーダーを有する請求項１に記載の方法。
【請求項３】
フィルタリング条件を満たす前記データベーステーブルの列は、前記反復の際にスキップされる請求項１に記載の方法。
【請求項４】
さらに、ツリーインデックス構造を構成するステップを含む請求項１に記載の方法。
【請求項５】
前記ツリーインデックス構造は、Ｂ木構造である請求項１に記載の方法。
【請求項６】
前記ツリーインデックス構造は、トライ木構造である請求項１に記載の方法。
【請求項７】
前記データベーステーブルから非結合属性が前記タプルと共に出力される請求項１に記載の方法。
【請求項８】
前記シーケンスを決定する際にクエリオプティマイザーが使用される請求項１に記載の方法。
【請求項９】
データベース内の少なくとも三つのテーブルのセットから、結合属性のセットＳにおける結合条件に基づいてレコードを結合するシステムであって、
コンピューター可読コンピューター指令を有するメモリと、
前記コンピューター可読指令を実行して次の方法を実施するためのプロセッサーとを備えるとともに、当該方法は、
前記結合属性ＳをシーケンスＳ０のオーダーに配列し、
スコープＣを空に初期化し、
前記テーブルのセットからシーケンスＳ０の最初のオーダーの結合属性Ａを含むテーブルを特定し、
前記シーケンスＳ０から結合属性Ａを除いた新規のシーケンスＳ'を生成し、
そのインデックスキーが前記シーケンスＳ０のオーダーで特定されたテーブルの全ての結合属性を含む、当該特定された各テーブルのツリーインデックス構造に基づいて、前記結合属性Ａのオーダーに従い、前記特定されたテーブルのそれぞれに対して反復し、
前記反復中の結合属性の一致した値ｖのそれぞれに対して、前記スコープＣに「Ａ＝v」を追加して新しいスコープＣｖを生成し、
前記シーケンスＳ'が空かどうかを判定し、
前記シーケンスＳ'が空の場合は、各ｖに対して前記スコープＣｖに対応したタプルを出力し、
前記シーケンスＳ'が空でない場合は、シーケンスＳ０をシーケンスＳ'にセットし、それぞれのスコープＣｖに対して、スコープＣをスコープＣｖにセットし、再帰的に、前記特定ステップ、生成ステップ、反復ステップ、追加ステップ、判定ステップ、出力ステップを呼び出すことを特徴とするシステム。
【請求項１０】
前記シーケンスＳ０は、非プレフィックスコヒーレントのオーダーを有する請求項９に記載のシステム。
【請求項１１】
フィルタリング条件を満たす前記データベーステーブルの列は、前記反復の際にスキップされる請求項９に記載のシステム。
【請求項１２】
前記方法はさらに、ツリーインデックス構造を構成するステップを含む請求項９に記載のシステム。
【請求項１３】
前記ツリーインデックス構造は、Ｂ木構造である請求項９に記載のシステム。
【請求項１４】
前記ツリーインデックス構造は、トライ木構造である請求項９に記載のシステム。
【請求項１５】
前記データベーステーブルから非結合属性が前記タプルと共に出力される請求項９に記載のシステム。
【請求項１６】
前記シーケンスを決定する際にクエリオプティマイザーが使用される請求項９に記載のシステム。
【請求項１７】
コンピューター可読プログラムコードが実装されるコンピューター可読記憶媒体であって、コンピュータープロセッサーによって実行される際に、前記コンピュータープロセッサーが次の方法を実施するとともに、当該方法は、
結合属性ＳをシーケンスＳ０のオーダーに配列し、
スコープＣを空に初期化し、
テーブルのセットからシーケンスＳ０の最初のオーダーの結合属性Ａを含むテーブルを特定し、
前記シーケンスＳ０から結合属性Ａを除いた新規のシーケンスＳ'を生成し、
そのインデックスキーが前記シーケンスＳ０のオーダーで特定されたテーブルの全ての結合属性を含む、当該特定された各テーブルのツリーインデックス構造に基づいて、前記結合属性Ａのオーダーに従い、前記特定されたテーブルのそれぞれに対して反復し、
前記反復中の結合属性の一致した値ｖのそれぞれに対して、前記スコープＣに「Ａ＝v」を追加して新しいスコープＣｖを生成し、
前記シーケンスＳ'が空かどうかを判定し、
前記シーケンスＳ'が空の場合は、各ｖに対して前記スコープＣｖに対応したタプルを出力し、
前記シーケンスＳ'が空でない場合は、シーケンスＳ０をシーケンスＳ'にセットし、それぞれのスコープＣｖに対して、スコープＣをスコープＣｖにセットし、再帰的に、前記特定ステップ、生成ステップ、反復ステップ、追加ステップ、判定ステップ、出力ステップを呼び出すことを特徴とするコンピューター可読記憶媒体。
【請求項１８】
前記シーケンスＳ０は、非プレフィックスコヒーレントのオーダーを有する請求項１７に記載のコンピューター可読記憶媒体。
【請求項１９】
フィルタリング条件を満たす前記データベーステーブルの列は、前記反復の際にスキップされる請求項１７に記載のコンピューター可読記憶媒体。
【請求項２０】
前記ツリーインデックス構造は、トライ木構造である請求項１７に記載のコンピューター可読記憶媒体。
【請求項２１】
前記データベーステーブルから非結合属性が前記タプルと共に出力される請求項１７に記載のコンピューター可読記憶媒体。
【請求項２２】
前記シーケンスを決定する際にクエリオプティマイザーが使用される請求項１７に記載のコンピューター可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本出願は、「Ｌｅａｐｆｒｏｇ  Ｔｒｅｅ−Ｊｏｉｎ（リープフロッグツリージョイン）」と題する、２０１２年９月２７日出願の米国仮特許出願第６１／７０６，４８４号の利益を主張し、その全体を本明細書に参照として組み込む。
【０００２】
本発明は、データベース操作に関し、特に、リレーショナルデータベーステーブル上の結合（ジョイン）操作に関する。
【背景技術】
【０００３】
データベース管理システムにより、ユーザーは大量の情報を記録し更新することができ、かつ、その情報に対して行われるクエリをサポートする。複数のテーブルからデータを組み合わせることは、データベースクエリを実行する際にリレーショナルデータベース管理によって行われる基本的な操作である。結合操作では、クエリ結果を生成するために、一つ又は複数の条件によって、それぞれのテーブルにおいて列がどのように関連付けられるべきかが特定される。結合処理の出力によって、さらにクエリ結果を生成する必要があっても、結合処理のコストは、概して時間的観点及び空間的観点から優位である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ソートマージジョイン、ネステッドループジョイン、インデックスネステッドループジョイン、ハッシュジョイン等を含む結合処理を実行するための種々のアルゴリズムが提案されている。これらのアルゴリズムは、一度に二つのテーブルを結合するために用いられており、その際にはペアワイズ結合のシーケンスに分解されたより複雑なジョインクエリが使用されている。
【課題を解決するための手段】
【０００５】
本実施形態は、データベース内の複数のテーブルのレコードを、結合属性のセットＳにおける複数のジョイン条件に基づいて結合するための方法、システム及びコンピュータープログラム製品に関する。本発明の一態様は、結合属性Ｓをオーダー付きのシーケンスＳ０に配列し、スコープＣを空に初期化することを含む。また、データベースのテーブルセットから、シーケンスＳ０内の最初の結合属性Ａを含むテーブルを特定する。シーケンスＳ０から結合属性Ａを除いた結合属性の新しいシーケンスＳ’を生成する。そして、結合属性Ａの順序に従い、特定された各テーブルに対して反復して実行する。この反復は、インデックスキーがＳ０オーダーで特定されたテーブルの全ての結合属性を含む、当該特定された各テーブルのツリーインデックス構造に基づいている。さらに、反復実行中の結合属性の一致した値ｖのそれぞれに対して、スコープＣに「Ａ＝ｖ」を追加して新しいスコープＣｖを生成する。さらに、シーケンスＳ’が空かどうかを判定し、空である場合はスコープＣに対応したタプルを出力する。シーケンスＳ’が空でない場合は、それぞれのスコープＣｖのシーケンスＳ０をシーケンスＳ’にセットし、スコープＣをＣｖにセットし、再帰的に、特定、生成、反復、追加、判定の各ステップを呼び出して繰り返す。
【０００６】
更なる特徴及び効果は、本発明の技術を通じて実現される。他の実施形態及び発明の態様は、明細書中に詳細に記載され、請求の範囲に記載の発明の一部として理解される。本発明の効果及び特徴についてより理解するために、詳細な説明及び図面が参照される。
【図面の簡単な説明】
【０００７】
本発明として捉えられる主要な特徴は、明細書の結論として請求の範囲に記載され、明白に請求されている。前述の本発明の他の特徴及び効果は、添付の図面と合わせた以下の詳細な説明によって明らかとなる。
【０００８】
【図１】本実施形態による代表的な方法のフローチャートである。
【図２】本実施形態によるリープフロッグツリージョインが実行されるシステムのブロック図である。
【発明を実施するための形態】
【０００９】
本明細書において「リープフロッグツリージョイン」と称する新規な技術に関する代表的な実施形態について説明する。リープフロッグツリージョインは、一度に複数のデータベーステーブルの結合処理を行うものであり、共通の属性を有する任意の数のテーブルに対して同時にイクイジョイン（等結合）を実行するものである。以下に記載される実施形態によれば、ペアワイズジョイン操作の組み合わせよりも高い計算量の限界を実現できる（例えば、入力が大きくなっても少ないステップで実行できる）。
【００１０】
マージジョインアルゴリズムの実行について以下に説明する。最初の仮定として、属性ｖを含む複数のテーブルセットＲ１、Ｒ２、…、Ｒｒが考えられる。各テーブルは、属性ｖが増えていくように物理的にソートされる。属性ｖに対するテーブルのマージジョインは、カーソルを用いて各テーブルをスキャンすることで得られる。カーソルＣｒで最も小さい値の属性ｖを有するテーブルＲは、カーソルＣｒの値が少なくとも任意のカーソルにおける最大の属性値ｖとなるまで進められる。全てのテーブルが一つの属性値ｖと一致したときに、出力レコードは、クエリ内で必要とされる各テーブルから属性値ｖと他の属性値とを組み合わせることで生成される。従来のマージジョインでは、テーブル内に属性値ｖを有するレコードが複数存在することによって、単一の属性値ｖに対する出力レコードが複数生成される。
【００１１】
さらなる仮定として、属性ｖによるソートに加えて、上記各テーブルは属性ｖに対してツリーインデックスを有する。本実施形態では、Ｂ木構造が用いられるが、これに限らず、トライ木等の他の木構造を用いても良い。木構造を用いる場合、マージジョインは全ての属性ｖについてスキャンする必要がないことから、より効率的に実行することができる。例えば、テーブルＲ１がキー群｛１、２、３、…、１０００｝を有し、テーブルＲ２がキー群｛１、７５０｝を有すると仮定する。この場合、アルゴリズムが属性ｖ＝１を実行した後、任意のカーソルに対する最大値はｖ＝７５０となる。テーブルＲ１をｖ＝７５０までリニアにスキャンすることなく、本システムでは、テーブルＲ１での属性ｖのインデックス内で７５０を検索することができる。次のアイテム（品目）を検索する際の最悪計算量は、テーブルのサイズに応じて線形的な変化から対数的に落ち込んでいく。サイズｎのテーブル内のキーの増加するシーケンスに対するｍシークのトータルコストは、直線的な木構造の走査技術を用いた場合の計算量Ｏ（ｍ  ｌｏｇ（ｎ／ｍ））として表される。
【００１２】
本明細書に記載されるように、カーソルジョインと呼ばれるマージジョインの変形を本実施形態に用いることも可能である。カーソルジョインは、上述のツリーインデックスを利用し、結合の「スコープ」に対応する属性値のタプル（ＳＣ）を入力に用いる。スコープは、所定の属性値を参加テーブル内から特定し、結合操作内でこれらの属性値と一致するもののみをレコードする。
【００１３】
結合属性を処理するそれぞれの入力リレーションのカーソルは、ＳＣ内で示した属性上のＳＣに一致するテーブルの最初の列を見つけることにより決定される。各入力テーブルに適したインデックスが与えられるとすると、これらのカーソル位置が効率的に発見され得る。ジョインは、カーソルのうちの一つが、スコープの範囲外の属性値を持つ（つまり、ＳＣ内の属性値に対応する値と異なる）入力レコードを指したときに終了する。カーソルジョインは、出力の生成方法を除いてマージンジョインと同様に振る舞う。カーソルジョインが新規な値、つまり、全てのテーブルが少なくとも一つの一致するレコードを有する結合属性に関する値ｖに当たると、新規のスコープＳＣ∪｛Ａ＝ｖ｝を出力する（ここで、Ａは結合属性を示している）。属性値ｖがテーブル内の多くのレコード内に存在しても、属性値ｖを含む唯一のスコープインスタンスが出力される。
【００１４】
いくつかの実施形態において、リープフロッグツリージョインは、任意の数のテーブルＲ１、Ｒ２、…、Ｒｒに対して、いかなる状態の属性も共有することで、同時にイクイジョイン（等結合）を実行する。例えば、クエリ（Ｑ＝Ｒ（Ａ，Ｂ），Ｓ（Ｂ，Ｃ），Ｔ（Ａ，Ｃ））が3つの結合属性Ａ、Ｂ、Ｃを有する。一般的には、Ａ１、…、Ａｋが結合属性となる（言い換えれば、結合表現に二つ以上の関連がある結合属性である）。はじめに、属性の順序（オーダー）が選択される。このオーダーは、リープフロッグツリージョイン内の処理の順序を決定する。異なるオーダーは、要素テーブル内のデータの分散に応じて、異なるランニングタイムとなる。クエリオプティマイザーは、結合操作のコストモデルに基づいて予想コスト、及び、すでに存在しない要求されたインデックスを構成するコストを最小にするオーダーを選択する。説明を簡単にし、かつ、一般性を失わないために、選択されたオーダーをＯｒｄ＝＜Ａ１，…，Ａｋ＞と表す。
【００１５】
いくつかの実施形態において、リープフロッグツリージョインのアルゴリズムは、それぞれの関連テーブルＲについて、オーダーＯｒｄと矛盾のない順序で、テーブルＲからの結合属性の組み合わせにインデックスが存在すると仮定する。上記クエリＱ及び結合属性のオーダーＡ、Ｂ、Ｃに対して、Ｒに対する（Ａ，Ｂ）のインデックス、Ｓに対する（Ｂ，Ｃ）のインデックス、Ｔに対する（Ａ，Ｃ）のインデックスが予想される。これらのインデックスが結合操作の前に存在していない場合、リープフロッグツリージョインのアルゴリズムを適用するべくインデックスが作成される。アクセスの局所参照性を向上するために、クエリに要求される非結合属性も結合属性後にインデックスされた属性に含まれても良い。このように非結合属性を含むことで、インデックスのみを用いた方式を採用できる。インデックスを二次記憶に保存する必要がある場合は、末端の葉ノードが順番に近くに隣接されて記憶されるように割り当てられる。
【００１６】
リープフロッグツリージョインは、一番目の結合属性Ａ１を用いてテーブルを結合することで開始される。属性の中にＡ１を含む全てのテーブルがＡ１の統合カーソルジョインに組み込まれる。最初のカーソルジョインに対するスコープは、［］で表されるからのスコープである。Ａ１に対する各値ａ１がカーソルジョインによって生成される間、Ａ１の外部結合の実行が中断され、Ａ２の内部カーソルジョインが、スコープ［Ａ１＝ａ１］と共に、Ａ２を含む全てのテーブル内で開始される。Ａ１も含む内部結合のテーブルにおいて、スコープ［Ａ１＝ａ１］は、内部結合をリレーションのａ１フラグメントのみに限定する。インデックスはオーダー＜Ａ１，…，Ａｋ＞内の各リレーションに存在することに起因して、カーソルジョインは、各階層で各インデックスに対して順番に続行することができ、各呼び出しに対してカーソルを指して再特定する必要がないからである。
【００１７】
結合の残りは、上述と同様の方法で再帰的に続行される。Ａｊに対する値ａｊが生成されるとき、実行が中断され、Ａｊ＋１に対する内部カーソルジョインは、［Ａｊ＝ａｊ］に拡張されたスコープと共に開始される。最後の段Ａｋに到達すると、出力タプルは、クエリによって要求される全ての属性を含む（ａ１，…，ａｋ）の形式でカーソルジョインによって生成される。最後の段階の出力がリープフロッグツリージョインの出力である。Ａｊ＋１に対するカーソルジョインがそれぞれ完了した後、Ａｊのカーソルジョインに戻る。Ａｊのカーソルジョインでは、属性Ａｊに対して次に一致する値が特定され、Ａｊ＋１に対する新しいカーソルジョインが開始される、このアルゴリズムは、Ａ１に対して最後の一致する値が処理され、最外のカーソルジョインが終了した後に完了する。
【００１８】
リープフロッグツリージョインの結合属性に対するオーダーＯｒｄ＝＜Ａ１，…，Ａｋ＞は、結合に参加する全てのテーブルに対してテーブル内の結合属性が、ｊ≦ｋにおいて（異なるテーブルは異なるｊの値を有してもよい）、オーダーのプレフィックス＜Ａ１，…，Ａｊ＞を形成する場合に、プレフィックスコヒーレントと呼ばれる。プレフィックスコヒーレントの構成としては、リープフロッグツリージョインの実施形態によって、二重のレコードを生成することなく、参加するテーブルに対してインデックスに支援されたマージジョインを効果的に実行することができる。なお、本明細書に記載されるリープフロッグツリージョインの実施形態に対する処理の利点は、プレフィックスコヒーレントでない場合にも実現可能である。例えば、Ｒ（Ａ，Ｂ）、Ｓ（Ｂ，Ｃ）、Ｔ（Ａ，Ｃ）の結合が、結合属性のプレフィックスコヒーレントのオーダーでない場合でも良い。
【００１９】
リープフロッグツリージョインのアウトプットは、重複することのない結合属性のみの組み合わせを含むことから、キーに基づいた結合インデックスに似ていると言える。以下の実施例は、サンプルのデータベースにリープフロッグツリージョインの操作を実行した例を示す。
【００２０】
図１を参照して、リープフロッグツリージョインを実行する代表的な方法１００のフローチャートについて説明する。方法１００は、以下に示すように、一つ又は複数の要素、装置、システムによって実行される。方法１００は、一つ又は複数のデータベーステーブルから結合属性セットＳを用いてレコードを結合する際に用いることができる。
【００２１】
図示した例では、データベースは、多数のサプライヤを示すオンライン小売業者に対する顧客によるオーダーを示している。概要は以下の通りである。
【００２２】
Ｃｕｓｔｏｍｅｒ（ＣＩｄ，Ｓｔａｔｅ，Ａｇｅ）は、顧客ＩＤ、居住州、顧客の年齢を示す。
【００２３】
Ｓｕｐｐｌｉｅｓ（ＳＩｄ，Ｐｒｏｄｕｃｔ，Ｓｔａｔｅ）は、各州からサプライヤによって出荷される商品を示す。
【００２４】
Ｏｒｄｅｒｓ（ＣＩｄ，ＳＩｄ，Ｐｒｏｄｕｃｔ）は、サプライヤの商品に対する顧客の注文を示す。
【００２５】
Ｍｅｔａｌｌｉｃ（Ｐｒｏｄｕｃｔ）は、商品が大きい金属部品を含むか否かを示す。
【００２６】
次のテーブルは、本実施例に関連するデータベース内に記憶されたレコードを示す。
【表１】
0006312685.tif 000002
【表２】
0006312685.tif 000003
【表３】
0006312685.tif 000004
【表４】
0006312685.tif 000005
本実施例において、以下のＳＱＬクエリによって、同一州内で発送される金属製品を注文した顧客を特定する。
Ｓｅｌｅｃｔ  ＣＩｄ，ＳＩｄ，Ｐｒｏｄｕｃｔ，Ｓｔａｔｅ
Ｆｒｏｍ  Ｃｕｓｔｏｍｅｒ  Ｃ，Ｓｕｐｐｌｉｅｓ  Ｓ，Ｏｒｄｅｒｓ  Ｏ，Ｍｅｔａｌｌｉｃ  Ｍ
Ｗｈｅｒｅ  Ｃ．ＣＩｄ＝Ｏ．ＣＩｄ  ａｎｄ  Ｃ．Ｓｔａｔｅ＝Ｓ．Ｓｔａｔｅ  ａｎｄ  Ｏ．ＳＩｄ＝Ｓ．ＳＩｄ  ａｎｄ  Ｏ．Ｐｒｏｄｕｃｔ＝Ｓ．Ｐｒｏｄｕｃｔ  ａｎｄ  Ｏ．Ｐｒｏｄｕｃｔ＝Ｍ．Ｐｒｏｄｕｃｔ
【００２７】
ブロック１０２では、結合属性のセットＳがオーダー付きのシーケンスＳ０に開始される。本例では、リープフロッグツリージョインは結合属性に対して、オーダー、つまりシーケンスＳ０を選択する。シーケンスＳ０は、非プレフィックスコヒーレントのオーダーである。本実施形態では、シーケンスＳ０は、属性のアルファベット順のオーダーである。クエリオプティマイザーは、シーケンスＳ０のオーダーを選択する。
【００２８】
ブロック１０３では、スコープＣを空のスコープに初期化する。
【００２９】
ブロック１０４では、結合属性のセットＳ内の一番目の結合属性Ａを含むテーブルが特定される。本例を参照すると、Ｃｕｓｔｏｍｅｒに対する（ＣＩｄ，Ｓｔａｔｅ）のインデックス、Ｓｕｐｐｌｉｅｓに対する（ＳＩｄ，Ｐｒｏｄｕｃｔ，Ｓｔａｔｅ）のインデックス、Ｍｅｔａｌｌｉｃに対する（Ｐｒｏｄｕｃｔ）のインデックス、及びＯｒｄｅｒｓに対する（ＣＩｄ，ＳＩｄ，Ｐｒｏｄｕｃｔ）のインデックスが想定される。一番目の結合属性ＣＩｄを含むテーブルは、Ｃｕｓｔｏｍｅｒ及びＯｒｄｅｒｓテーブルを含む。
【００３０】
ブロック１０６では、結合属性に関する新しいシーケンスＳ’が決定され、直前のシーケンスＳ０から一番目の結合属性Ａ（例えばＣＩｄ）が除外される。本例を参照すると、新しく決定されたシーケンスＳ’は＜ＳＩｄ，Ｐｒｏｄｕｃｔ，Ｓｔａｔｅ＞である。
【００３１】
ブロック１０８では、結合属性Ａのオーダーで特定された各テーブルに対して、同様にイタレーションが実行される。この際、ツリーインデックス構造の支援を受けて、キーがＳ０のオーダーでテーブル上の全ての結合属性を含んでいる各テーブルに対してイタレーションが実行される。本例では、統合されたイタレーションは、ＣＩｄオーダーのＣｕｓｔｏｍｅｒ及びＯｒｄｅｒｓに対して実行される。一番目の一致は、ＣＩｄ＝Ａｌｉｃｅである。
【００３２】
ステップ１１０では、Ｏｒｄｅｒｓ及びＳｕｐｐｌｉｅｓの間のＳＩｄに対する二番目の階層の再帰的なカーソルジョインが、スコープ［ＣＩｄ＝Ａｌｉｃｅ］を有して開始される。このスコープに対する一番目（かつ唯一の）一致はＳＩｄ＝Ａｃｍｅであり、Ｐｒｏｄｕｃｔに対する三番目の階層の再帰的なカーソルジョインは、スコープ［ＣＩｄ＝Ａｌｉｃｅ，ＳＩｄ＝Ａｃｍｅ］を有することとなる。
【００３３】
Ｏｒｄｅｒｓ、Ｓｕｐｐｌｉｅｓ、Ｍｅｔａｌｌｉｃの三つのテーブルが三番目の階層のカーソルジョインに参加する。再度、その中の一つ（Ｐｒｏｄｕｃｔ＝Ｈａｍｍｅｒ）が一致する。Ｓｔａｔｅに関する四番目の階層のカーソルジョインは、スコープ［ＣＩｄ＝Ａｌｉｃｅ，ＳＩｄ＝Ａｃｍｅ，Ｐｒｏｄｕｃｔ＝Ｈａｍｍｅｒ］を有して開始される。四番目の階層のカーソルジョインは、Ｓｔａｔｅ＝ＧＡで一致し、残りの結合属性がない、つまり、Ｓ’が空であることから、ステップ１１０でタプル（Ａｌｉｃｅ，Ａｃｍｅ，Ｈａｍｍｅｒ，ＧＡ）を出力する。四番目、三番目、二番目の階層のカーソルジョインが完了すると、アルゴリズムは、一番目のカーソルジョインの結果の次のＣＩｄ＝Ｂｏｂに移行する。
【００３４】
ブロック１１０に示されるように、処理は、全ての参加するテーブル内の属性値Ａに対して一致したそれぞれの値ｖに対して同様に継続される。シーケンスＳ’が空であれば、ブロック１１０の再帰的なインスタンスのそれぞれで特定された一致した値に対応するタプルが出力される。他方、ブロック１０４−１１０は、シーケンスセットＳをＳ’とし、かつ、結合属性に応じた一致した値に基づいたスコープを有して、再帰的に実行される。
【００３５】
再度実施例に戻って説明すると、Ａｌｉｃｅに対する処理が完了すると、Ｂｏｂに対して類似の処理（ブロック１０４−１１０に示される処理）が実行される。ただし、本例では四番目の階層のカーソルジョインが一致を探せない場合がある。これは、ＢｏｂのＳｔａｔｅ（ＭＡ）が、彼がＴａｃｋｓを注文したＧｏｏｄｓｔｏｒｅのＳｔａｔｅ（ＮＹ）と一致しないためである。アルゴリズムは、最上位の階層のカーソルジョインの結果の中の次のＣＩｄ＝Ｊｏｅに移行する。なお、ＦｒｅｄがＣｕｓｔｏｍｅｒテーブルに存在していてもＦｒｅｄは注文していないため、Ｆｒｅｄはスキップされる。
【００３６】
［ＣＩｄ＝Ｊｏｅ］に対する二番目の階層のカーソルジョインでは、ＳＩｄ＝Ａｃｍｅでの一致が特定される。一致する行が三つあるが、同一のＳＩｄを共有する行であるため、一致する値はＳＩｄの一つである。三番目の階層のカーソルジョインは、スコープ［ＣＩｄ＝Ｊｏｅ，ＳＩｄ＝Ａｃｍｅ］を有して開始される。この結合では、二つの一致があり、［ＣＩｄ＝Ｊｏｅ，ＳＩｄ＝Ａｃｍｅ，Ｐｒｏｄｕｃｔ＝Ｔａｃｋｓ］と［ＣＩｄ＝Ｊｏｅ，ＳＩｄ＝Ａｃｍｅ，Ｐｒｏｄｕｃｔ＝Ｈａｍｍｅｒ］二つの独立した四番目の階層のカーソルジョインが実行される。（ＪｏｅがＴａｐｅを注文したとしても、ＴａｐｅはＭｅｔａｌｌｉｃではないため、Ｐｒｏｄｕｃｔ＝Ｔａｐｅは三番目の階層のカーソルジョインの結果に含まれない。）これらのスコープは何れも四番目の階層のカーソルジョインで一致するものがあり、その結果、（Ｊｏｅ，Ａｃｍｅ，Ｔａｃｋｓ，ＧＡ）と（Ｊｏｅ，Ａｃｍｅ，Ｈａｍｍｅｒ，ＧＡ）のタプルが出力される。処理は、一番目のカーソルジョインに戻り、リープフロッグツリージョインの実行を完了して終了する。
【００３７】
いくつかの実施形態では、生成された結合属性値のタプルセットは、トラバースすることも可能である。結合属性値の各タプルＴに対して、少なくとも一つの結合されたテーブルを、結合属性のタプルＴに一致するレコードから、追加的に選択された非結合属性値を決定するために問い合わせることができる。その一例では、属性「Ａｇｅ」をＳＱＬクエリのＳｅｌｅｃｔ文節に追加的に含めることが想定される。Ｃｕｓｔｏｍｅｒテーブル上の（ＣＩｄ，Ｓｔａｔｅ）インデックスは、結合結果の（ＣＩｄ，Ｓｔａｔｅ）のペアに対応するＣｕｓｔｏｍｅｒレコードを発見し、Ａｇｅの値を検索するために用いることができる。選択された非結合属性値を有するタプルＴの全ての連結が、問い合わせを受けたテーブルのそれぞれのレコードから出力される。
【００３８】
いくつかの実施形態では、フィルタリングの条件を方法１００に関連して適用することも可能である。例えば、ブロック１０８の一部で、フィルタリング条件に違反する行を無視することができる。結合属性に対するフィルタリング条件は、その結合属性値がすでに読まれたものである場合に即座に適用することができる。そして、その条件に合致しない値は単純にスキップされる。非結合属性のフィルタリング条件は種々の実施形態の一つに組み込むことも可能である。
【００３９】
非結合属性のフィルタリングを説明するために、本例のクエリが追加の条件「Ａｇｅ＞２５」をＳＱＬクエリのＷｈｅｒｅ文節に含むように修正する。フィルタリングの一実施形態では、上記にＡｇｅ属性を含めて全ての結合結果を処理し、最終ステップでＡｇｅの条件に違反するレコードを除外する。
【００４０】
別実施形態では、アルゴリズムがＣｕｓｔｏｍｅｒテーブルからＡｇｅ値を拾うよりも早い段階で、Ｃｕｓｔｏｍｅｒテーブルの（ＣＩｄ，Ｓｔａｔｅ）のインデックスに用いる。結合属性の異なるオーダー＜ＣＩｄ，Ｓｔａｔｅ，Ｐｒｏｄｕｃｔ，ＳＩｄ＞の条件下で、Ａｇｅ値の検索を二番目の階層のカーソルジョインの後に行うことができ、Ａｇｅ値の分類を有しない（ＣＩｄ，Ｓｔａｔｅ）のペアを、三番目の階層のカーソルジョインを処理する前の段階でスキップすることができる。
【００４１】
さらに別の実施形態では、拡張インデックス構造を用いることができる。本例では、（ＣＩｄ，Ｓｔａｔｅ）のインデックスに代えて、システムはＣｕｓｔｏｍｅｒテーブル上の（ＣＩｄ，Ｓｔａｔｅ，Ａｇｅ）のインデックスを有することが想定される。この（ＣＩｄ，Ｓｔａｔｅ，Ａｇｅ）のインデックスは、Ａｇｅ値が問い合わされ、フィルターされた範囲内でＡｇｅのレコードのみが結合アルゴリズムの次のステップに進むように、トラバースされる。
【００４２】
いくつかの実施形態では、ツリーインデックスはＢ木構造を有する。
【００４３】
いくつかの実施形態では、ツリーインデックスはトライ木構造を有する。
【００４４】
テーブルが、結合内で一致する異なる属性名を有する場合、一致した属性は同等であるとみなされ、その属性名の一つは、スコープ、属性オーダー、アルゴリズムの他のステップを定義する際に任意に選択することができる。
【００４５】
リープフロッグツリージョインの実施形態では、対数的な要因の範囲内で、他のジョイン操作と同じように最悪計算量の限界が存在し得る。対数的な要因は、ハッシュインデックスを介して直接ルックアップすることよりもむしろツリーインデックスのトラバースに起因する。実際に、ツリーのより上位の階層は、比較的小さいメモリのフットプリントであり、より速いメモリ（例えば、ランダムアクセスメモリ：ＲＡＭ）にキャッシュされる。一方でリーフノード及びベーステーブルは、遅いメモリ（例えば、磁気ディスク）に記憶される。結果として、ツリーをトラバース検索する際にかかる余分なステップは、大きなパフォーマンスのオーバーヘッドを有しない。
【００４６】
数ある例の中で、リープフロッグツリージョインは、現存、つまり現代の結合方法及び結合技術に対して、顕著に良いパフォーマンスを有する。この比較を強調するために、現代の結合アルゴリズムの重要なステップについて概説する。現代の結合アルゴリズムがデータを二つの関係（つまり、サブ結合結果）Ｒ及びＳを組み合わせる場合、一度にＲとＳのフラグメントを考慮する。例えば、現存の結合アルゴリズムによって、Ｓ（Ｂ，Ｃ）とＴ（Ａ，Ｃ）をＣに基づいて組み合わせる場合、直前のステップは、可能性のある分類（Ａ，Ｂ）のセットＶを生成する。Ｖの各ペア（ａ，ｂ）に対して、Ｂ＝ｂとするＳのフラグメントＦＳ，ｂ、がＡ＝ａとするＴのフラグメントＦＴ，ａと結合される。ＦＳ，ｂがＦＴ，ａよりも小さい場合、ＦＳ，ｂ内の値はＦＴ，ａのハッシュインデックスを探索するために使用される。反対に、ＦＴ，ａがＴＳ，ｂよりも小さい場合は、ＦＴ，ａの値がＦＳ，ｂのハッシュインデックスを探索するために使用される。このように、より小さいフラグメントのサイズに応じて処理が行われる。
【００４７】
リープフロッグツリージョインの実施形態に対応するステップは、カーソルジョインを用いてＦＳ，ｂとＦＴ，ａを組み合わせる。例えば、整数ｋ及びｍを用いて、ＦＳ，ｂ内のＣの値が｛−ｋｍ，−（ｋ−１）ｍ，…，−ｍ，１，２，…，ｋ｝であり、ＦＴ，ａ内のＣの値が｛−ｋ，−（ｋ−１），…，−１，ｍ，２ｍ，…，ｋｍ｝である場合を考える。各入力のサイズは２ｋであり、現在の結合アルゴリズムは、２ｋのハッシュインデックスのルックアップを実行する。実際の結合結果は、２［ｋ／ｍ］の結果を含む（ここで、［ｘ］はｘの整数部分を示す）。カーソルジョインがシークする回数は、２［ｋ／ｍ］に比例することから、Ｏ（ｍ／ｌｏｇ（ｍ））の因数を現存の結合アルゴリズムに対して向上することが可能である。ｌｏｇ（ｍ）の因数は、木構造を用いたＯ（ｍ）要素をスキップするコストである。
【００４８】
リープフロッグツリージョインの他の効果は、バンド結合を扱う直接法に拡張できることである。テーブルＲ及びＳに対するバンド結合の条件の一例としては、定数ｃ１、ｃ２を用いて「Ｒ．Ａ−ｃ１≦Ｓ．Ａ≦Ｒ．Ａ＋ｃ２」と表される。レコードは結合属性オーダーにインデックスされるため、マッチングは、対応するカーソルジョインの最中に高速メモリにキャッシュされるバンドにローカライズされる。ハッシュインデックスを用いるアルゴリズムでは、このようにマッチングをローカライズすることはできない。
【００４９】
いくつかのクエリに対して、結合属性を超える追加的な属性が要求される。いくつかの実施形態では、リープフロッグツリージョインは、一つ又は複数の非結合属性がカーソルジョインステップで検索されるように拡張することができる。このような検索は、結合属性と必要とされる非結合属性を含むインデックスのような好適なインデックスに支援される場合に効果的である。フィルタリング条件が非結合属性Ｒｉ．Ｂの値を限定するときは、Ｒｉ．Ｂが検索されるやいなやフィルターを適用して、行を取り除き、リープフロッグツリージョインの残りの処理を減らすことができる。
【００５０】
検索された非結合属性は、結合属性に並べて出力するように、スコープに記録しても良い。しかしながら、リープフロッグツリージョインに非結合属性を含むことは、アルゴリズムの計算量を増加させることとなる。以下に示す実施例では、結合属性値が入力リレーション内に（異なる非結合属性と共に）多数存在し、リープフロッグツリージョインでこれらの非結合属性を追跡し続ける必要のあるブックキーピングが多くなる。リープフロッグツリージョインの次の段階で結果から結合属性値を除去することから、このブックキーピングは無駄である。
【００５１】
具体的な例としては、非結合属性Ｄを用いた結合Ｒ（Ａ，Ｂ，Ｄ），Ｓ（Ｂ，Ｃ），Ｔ（Ａ，Ｃ）が考えられる。ここで、テーブルＲは、（１，１，ｉ（ｉ＝１，…，ｎ））のｎ個のレコードを有し、テーブルＳは、単一のレコード（１，２）を有し、テーブルＴは、単一のレコード（１，１）を有するとする。また、リープフロッグツリージョインに対して選択されたオーダーは、＜Ａ，Ｂ，Ｃ＞であり、Ｄは中間カーソルジョインのスコープであり、Ａ及びＢを含むスコープに含まれるとする。Ａに基づくＲとＴの一番目のカーソルジョインにより一つのスコープレコード［Ａ＝１］が生成される。二番目の階層で、アルゴリズムは、ｎに比例する処理によって、ｎ個のスコープレコード［Ａ＝１，Ｂ＝１，Ｄ＝ｉ］を生成する。最後の階層でのＣに基づくカーソルジョインは全て空であることから、出力結果は空となる。スコープからＤを除外すると、処理量はｎに比例することがない。
【００５２】
リープフロッグツリージョインで非結合属性を含むことは、効果的ではないことから、アルゴリズムは、リープフロッグツリージョインが完了する後まで非結合属性の検索を延ばすことができる。リープフロッグツリージョインの出力は、追加される非結合属性を検索するために、各テーブルの結合属性のインデックスと関連して用いることができる。
【００５３】
また、結合処理の前にフィルタリング条件を適用することでアルゴリズムの負荷を低減することもできる。クエリＱ’＝σＤ＞５０（Ｒ（Ａ，Ｂ），Ｓ（Ｂ，Ｃ），Ｔ（Ａ，Ｃ，Ｄ）を仮定する。ＤのツリーインデックスがＴで利用できる場合、条件Ｄ＞５０は、Ｔの行から適したサブセットＴ’を特定する。インデックスがない場合でも、Ｔの全てをスキャンすることでＴ’を構成することが可能である。Ｔ’は、記憶され次のリープフロッグツリージョインで（Ａ，Ｃ）としてインデックスされる。条件が十分に選択可能であれば、事前のフィルタリングの負荷は、結合の負荷と相殺され得る。
【００５４】
一つの実施形態では、クエリオプティマイザーによって適した属性オーダーが選択される。クエリオプティマイザーは、データベースシステムのコンポーネントとして周知のものである。属性オーダーは、リープフロッグツリージョインのカーソルジョインステップのオーダーを決定する。従来のリレーショナルデータベースでは、結合オーダーを選択することは複雑な問題であり、種々の発見的なアルゴリズムが提案されている。データベーステーブルを記述する統計は、記憶されて維持される。これらの統計は、中間結果の関係の中の組の個数を推定するために用いられることで、不必要に大きい中間結果が回避される。リープフロッグツリージョインのオーダリングの問題は、従来のデータベースと類似しており、同様の発見的方法が様々なオーダー下での処理コストを推定するために用いられる。
【００５５】
複雑なクエリでは、リープフロッグツリージョインは全ての参加テーブルの結合を計算するために用いられる。その他、リープフロッグツリージョインはテーブルのサブセット、及び、結合結果と残りのテーブルを組み合わせるためのアルゴリズムに適用することもできる。単一のクエリは、複数のリープフロッグツリージョインを用いることで評価することができ、その際、それぞれのリープフロッグツリージョインは、参加テーブルのサブセット及び／又は中間結果を分離するために適用される。一つの実施形態でのリープフロッグツリージョインの出力は、＜Ａ１，…，Ａｋ＞のオーダーであり、その特性は次の結合又は集約演算子に利用される。
【００５６】
リープフロッグツリージョインの変形例は、イクイジョインを除いた処理を計算するために用いることができる。ｎ個のテーブルのカーソルジョインは、単純に任意の入力に見られる属性値Ａを含むことで、入力の集合（属性値Ａに基づくもの）を生成するために一般化することができる。差集合及び「ｎ個のうちｊ個の一致（１≦ｊ≦ｎ）」等の他の処理は、若干の計算量の増加だけで実装することが可能である。
【００５７】
いくつかの実施形態では、一つ又は複数の方法は、一つ又は複数の種類のメモリにアクセスする一つ又は複数のプロセッサに対する指令のセットで具現化される。これらの指令は、ハードウェア又はソフトウェアにコード化される。コンピューター、携帯電話、タブレット端末、ゲームコンソール、ネットワーク管理装置、フィールドプログラマブルゲートアレイ、クラウド型コンピューターシステム等、これらに限定されるものではないが、多数種のプラットフォームが利用可能である。本発明の態様は、同時処理のために複数のデバイスに配置されても良い。実施形態は、データベース管理システム等の大きなシステムの一部として用いることも可能である。
【００５８】
図２を参照して、一度に複数のテーブルの結合を計算処理する代表的なシステム２００の概要を説明する。システム２００は、ホストシステム２０４上に配置される一つ又は複数のコンピュータープログラムによって実行されるリープフロッグツリージョインのアルゴリズム２１０を有する。一実施形態では、リープフロッグツリージョインアルゴリズム２１０の全て又は一部がホストシステム２０４のデータベース管理システムの一部である。別の実施形態では、リープフロッグツリージョインアルゴリズム２１０の全て又は一部がトランザクション及びクエリをサポートするシステムのコンポーネントである。
【００５９】
図２に示されるシステム２００は、一つ又は複数のユーザーシステム２０２を有し、それを通じて、一箇所又は複数箇所で、ユーザー（例えば、エンドユーザー、データベース管理者）がデータベースクエリ及び／又はトランザクションを実行するプログラムを開始することができる。ユーザーシステム２０２は、ネットワーク２０６を介してホストシステム２０４と接続される。各ユーザーシステム２０２は、ここに記載されたプロセスを実行するためのコンピュータープログラムを実行する多目的コンピューターによって実行される。ユーザーシステム２０２としては、例えばラップトップ、タブレットコンピューター、携帯電話等のパーソナルコンピューター、若しくはホストに接続された端末が挙げられる。ユーザーシステム２０２がパーソナルコンピューターである場合、本例の処理はユーザーシステム２０２とホストシステム２０４に共有される。ユーザーシステム２０２としては、ゲームコンソール、ネットワーク管理装置、フィールドプログラマブルゲートアレイ等を含んでも良い。さらに、複数のユーザーシステム２０２及び／又はホストシステム２０４で同時にリープフロッグツリージョインを実行しても良い。
【００６０】
ネットワーク２０６としては、ワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、グローバルネットワーク（インターネット）、バーチャルプライベートネットワーク（ＶＰＮ）、クラウドネットワーク、イントラネット等、これらに限定されるものではないが、よく知られたネットワークを適用できる。ネットワーク２０６は、ワイヤレスネットワーク若しくは周知の物理ネットワーク機器を用いて実行することも可能である。ユーザーシステム２０２は、必ずしも全てのユーザーシステム２０２が同一のネットワークを介してホストシステム２０４に接続することなく、複数のネットワーク（携帯電話及びインターネット）を通じてホストシステムに接続しても良い。一つ又は複数のユーザーシステム２０２及びホストシステム２０４は、ワイヤレスでネットワーク２０６に接続することも可能である。一つの実施形態では、ネットワークはインターネットであり、一つ又は複数のユーザーシステム２０２がウェブブラウザ等のユーザーインターフェースアプリケーションを実行することで、ネットワーク２０６を介してホストシステム２０４に接続される。他の代表的な実施形態では、ユーザーシステム２０２は直接（ネットワーク２０６を介さずに）ホストシステム２０４に接続される。さらに他の実施形態では、ホストシステム２０４は、記憶装置２０８に直接接続される、又は記憶装置２０８を備えている。
【００６１】
記憶装置２０８は、複数のテーブルを一度に結合処理するためのデータを含み、電子情報を記憶する様々な装置によって実装される。一つの実施形態では、記憶装置２０８に記憶されたデータは、これらに限定されるものではないが、一つ又は複数のデータベース、データベーステーブル、ツリーインデックス、本例に記載された実施形態で利用される他のデータ等を含む。なお、記憶装置２０８は、ホストシステム２０４に含まれるメモリに実装されるものでも良いし、別の物理装置であっても良い。記憶装置２０８は、ネットワーク２０６を含む分散された環境を横断して集約されたデータソースとして論理的にアドレス可能である。記憶装置２０８に記憶される情報は、ホストシステム２０４及び／又はユーザーシステム２０２を介して検索されて操作される。
【００６２】
図２に示されるホストシステム２０４は、サーバーによってアクセス可能な記憶媒体に記憶されるコンピュータープログラムに応答して動作する一つ又は複数のサーバーを用いて実装しても良い。ホストシステム２０４は、ユーザーシステム２０２と通信するネットワークサーバーとして動作してもよい。ホストシステム２０４は、ユーザーシステム２０２に情報を送るとともにユーザーシステム２０２から情報を受け取り、関連したタスクを実行する。ホストシステム２０４は、ホストシステム２０４への不正なアクセスを防止するファイアウォールを含み、権限のあるアクセスに制限することができる。例えば、管理者は全てのシステムにアクセスでき、システムの一部を修正する権限を有する。ファイアウォールは、従来の公知のハードウェア及び／又はソフトウェアを用いて実装できる。
【００６３】
ホストシステム２０４は、アプリケーションサーバーとして動作しても良い。ホストシステム２０４は、リープフロッグツリージョインアルゴリズム２１０を含み、本実施形態の態様を提供する一つ又は複数のコンピュータープログラムを実行する。ユーザーシステム２０２にアプリケーションを提供するために、ユーザーシステム２０２とホストシステム２０４に処理を共有させることもできる。別実施形態としては、ユーザーシステム２０２は、本明細書に記載される処理の一部又は全てを実行するスタンドアローン型のソフトウェアアプリケーションを含む。前述のように、独立したサーバーを用いてネットワークサーバーの機能及びアプリケーションサーバーの機能を実装しても良い。他の実施形態としては、ネットワークサーバー、ファイアウォール及びアプリケーションサーバーは、必須の機能を実行するコンピュータープログラムを実行する単一のサーバーに実装することもできる。
【００６４】
当業者によって理解されるように、本発明の態様は、システム、方法又はコンピュータープログラム製品として実施可能である。従って、本発明の態様は、全てのハードウェア形態、全てのソフトウェア形態（ファームウェア、常駐ソフトウェア、マイクロコードを含む）、若しくは、ここで一般的に「回路」、「モジュール」又は「システム」と称されるソフトウェア及びハードウェアを組み合わせた形態を採ることができる。さらに、本発明の態様は、コンピューター可読プログラムコードを有する一つ又は複数のコンピューター可読媒体としての形態を採ることができる。
【００６５】
一つ又は複数のコンピューター可読媒体の組み合わせを利用することができる。コンピューター可読媒体は、コンピューター可読信号媒体又はコンピューター可読記憶媒体であっても良い。コンピューター可読記憶媒体は、例えば、これらに限定されるものではないが、電子、磁気、光学、電磁気、赤外線又は半導体システム、装置又はデバイス、若しくは、これらの組み合わせである。コンピューター可読記憶媒体のさらに詳細な例（完全に網羅しているわけではないが）では、一つ又は複数のワイヤを有する電気的な接続、ポータブルのコンピューターディスケット、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、リードオンリメモリ（ＲＯＭ）、消去可能プログラマブル読取専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、光ファイバー、ポータブルのコンパクトディスク読取専用メモリ（ＣＤ−ＲＯＭ）、光学記憶装置、磁気記憶装置、若しくはこれらの組み合わせを有する。本出願の文脈では、コンピューター可読記憶媒体は、指令実行システム、装置又はデバイスによって使用される又は関連するプログラムを含む又は記憶する有形的表現媒体である。
【００６６】
コンピューター可読信号媒体は、例えば、ベースバンド内又は搬送波の一部としてコンピューター可読プログラムコードを有した伝搬されたデータ信号を含む。そのような伝搬されたデータ信号は、電磁気、光学、若しくはこれらの組み合わせ等、これらに限定されるものではないが、種々の形態を採用することができる。コンピューター可読信号媒体は、コンピューター可読記憶媒体ではなく、かつ、指令実行システム、装置又はデバイスによって、若しくは、それらに関連して用いられるプログラムを伝送し、伝搬し、又は転送できるあらゆるコンピューター可読媒体を適用できる。
【００６７】
コンピューター可読媒体に実装されるプログラムコードは、ワイヤレス、ワイヤライン、光学ファイバーケーブル、ＲＦ等、若しくは、これらの組み合わせ等、これらに限定されるものではないが、適切な媒体を用いて転送される。
【００６８】
本発明の態様の動作を実施するコンピュータプログラムコードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のオブジェクト指向のプログラム言語、Ｃ言語等の従来の手続き型プログラム、又は類似のプログラム言語等のうち、一つ又は複数のプログラム言語の任意の組み合わせで記述しても良い。プログラムコードは、ユーザーコンピューター上で全て実行される、スタンドアローン型のソフトウェアパッケージとして部分的にユーザーコンピューター上で実行される、ユーザーコンピューター上で部分的に実行される、リモートコンピューター上で部分的に実行される、若しくは、リモートコンピューター又はサーバー上で全部実行される。後者のシナリオでは、リモートコンピューターは、ローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）を含む任意のネットワークタイプを介してユーザーコンピューターに接続される、又は、外部コンピューター（例えば、インターネットサービスプロバイダを用いてインターネットを介して）に接続される。
【００６９】
本発明の実施形態に基づいた方法、装置（システム）及びコンピュータープログラム製品のフローチャート及び／又はブロック図を参照して、本発明の態様について説明した。フローチャート及び／又はブロック図、及び、それらの組み合わせにおける各ブロックは、コンピュータープログラム指令に実装される。これらのコンピュータープログラム指令は、汎用コンピューターのプロセッサ、専用コンピューター、又は、機械を製造するための他のプログラマブルデータ処理装置等に提供される。コンピューター又は他のプログラマブルデータ処理装置のプロセッサを介して実行する指令によって、フローチャート及び／又はブロック図、又はそれらのブロックに詳述されるファンクション／アクトを実装する手段を生成する。
【００７０】
これらのコンピュータープログラム指令は、コンピューター可読媒体に記憶される指令によって、フローチャート及び／又はブロック図、又はそれらのブロックに詳述されるファンクション／アクトを実装する指令を含む製品が製造されるように、特定の方法で機能するコンピューター、他のプログラマブルデータ処理装置、又はその他のデバイスに指示するコンピューター可読媒体に記憶される。
【００７１】
コンピュータープログラム指令は、一連の処理工程を引き起こすために、コンピューター、他のプログラマブルデータ処理装置、又は他のデバイスにロードされ、コンピューターを製造するために、コンピューター、他のプログラマブルデータ処理装置、又は他のデバイス上で実行される。そして、コンピューター又は他のプログラマブル装置上で実行する指令は、フローチャート及び／又はブロック図、又はそれらのブロックに特定されるファンクション／アクトを実装するための処理を提供する。
【００７２】
図示されるフローチャート及びブロック図は、本発明の種々の実施形態に基づいたシステム、方法及びコンピュータープログラム製品に対する可能な具体化に関する構成、機能及び操作を説明している。この点において、フローチャート又はブロック図の各ブロックは、特定の論理的な機能を実装するための一つ又は複数の実行可能な指令を備えたモジュール、セグメント又はコードの一部を表している。いくつかの代替的な具体例では、ブロック内に記載される機能は、図面に記載されたオーダーから生じても良い。例えば、連続する二つのブロックは、実際として、略同時に実行しても良く、それに含まれる機能に応じて、逆の順で実行しても良い。また、ブロック図及び／又はフローチャートの各ブロック、並びに、ブロック図及び／又はフローチャートの組み合わせのブロックは、特定の機能又は行為を実行する専用ハードウェアベースシステム、又は専用ハードウェアの組み合わせ、コンピューター指令によって実行される。
【００７３】
本明細書で使用される技術は、特定の実施形態を記載する目的で使用されるものであり、本発明を限定する目的ではない。本明細書で使用されるように、単数形（「ａ」、「ａｎ」及び「ｔｈｅ」）は、文脈中に明確に示しているわけではないが、複数形を含むものを意図している。さらに、「備える（ｃｏｍｐｒｉｓｅｓ及び／又はｃｏｍｐｒｉｓｉｎｇ）」は、本明細書で使用される場合、上述した特徴の存在、完全形、工程、操作、要素、及び／又は構成物について特定するものであり、一つ又は複数の特徴の存在、完全形、工程、操作、要素、及び／又は構成物の追加を排除するものではない。
【００７４】
請求の範囲に記載されている機能で特定される全ての手段又は工程における、構成、マテリアル、アクト及び同等物は、請求の範囲で特定される他の構成要素と組み合わせた機能を実行できる任意の構成、マテリアル又はアクトを含むことを意図されている。本発明の明細書は、図示及び説明の目的に記載されるものであるが、開示されている発明を網羅し、限定することを意図するものではない。多くの修正例、変形例を本発明の範囲及び思想から外れることなく実施できることは当業者にとって明白である。実施形態は、本発明の原則及び実践的な適用について最適に説明し、当業者にとって想定される特定の使用法に適するように、種々の修正を加えた種々の実施形態に対する本発明を理解するために選ばれ、記載されるものである。
【００７５】
本明細書で記載されるフロー図は、あくまで一例である。本発明の思想から外れることなく、このフロー図、つまり本明細書で記載される工程（操作・処理）に対する色々な変形例が存在する。例えば、ステップを異なる順序で実行したり、ステップを追加、削除、修正したりすることができる。これらの変形例は全て、請求の範囲に記載された発明の一部として理解されるものである。
【００７６】
本発明の好ましい実施形態が記載されているが、現在及び将来において、当業者が請求の範囲に記載される範囲内の種々の改良を加えることも可能である。これらの請求の範囲は、最初に記載された発明の適した保護を維持するために構成されている。
【図１】
0006312685.tif 000006
【図２】
0006312685.tif 000007