(57)【要約】【課題】互いに異なるインスタンスおよびオブジェクト間の関係を有するオブジェクトによって形成された情報システム。【解決手段】本システムにおいて、クエリが結果（５１４）を生成するか否かを予想するプロセスが提供される。インスタンスからオブジェクトへのビットマップ（５１２）は、クエリがユーザによって生成される前にオフラインで演算される。ビットマップはデータベースのインスタンスから他のオブジェクトまでの関係パスの存在を表すために用いられる。クエリが生成されるとビットマップがアクセスされてインスタンスからオブジェクトへの関係が存在するか否か、すなわちクエリが結果を発行するか否かが予想される。このプロセスは、ユーザが実行時間を消費することなくクエリ（５１８）を中止することを可能にする。このプロセスはさらに結果を生成する関係を示唆しながらユーザを案内してウェブページなどをナビゲーションさせる。【選択図】図５
2006172491.tif 000002
【特許請求の範囲】
【請求項１】
計算手段と格納手段とを備えた情報システムであって、該格納手段は、複数のオブジェクトと、該複数のオブジェクトの各々に対する複数のオブジェクトインスタンスとを格納し、該複数のオブジェクトインスタンスの各々は、該複数のオブジェクトの対応する１つのインスタンスであり、該格納手段は、各オブジェクトインスタンスに対するビットベクトルをさらに格納し、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスのビットベクトルは、該第１のオブジェクトインスタンスと該第１のオブジェクトを除く該複数のオブジェクトの各々との間に関係が存在するか否かを示す、情報システムにおいて、
該第１のオブジェクトインスタンスと該複数のオブジェクトのうちの第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在するかを示す否かを決定する方法であって、
該方法は、
該計算手段が、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスと第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在するか否かを要求するクエリを受信するステップと、
該計算手段が、該第１のオブジェクトインスタンスのビットベクトルを走査することにより、該第１のオブジェクトインスタンスと該第２のオブジェクトとの間に関係が存在するかどうかを決定するステップと、
該第１のオブジェクトインスタンスと該第２のオブジェクトとの間に関係が存在すると該計算手段が決定した場合には、該計算手段が、該第１のオブジェクトインスタンスと該第２のオブジェクトの該複数のオブジェクトインスタンスのいずれかとの間の関係が存在することを示す結果を生成するステップと
を包含する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関係出願への相互参照）
本特許出願は、１９９９年７月２日に出願された米国仮特許出願シリアル番号６０／１４２，１３８の優先権を主張し、その全体を、あらゆる目的のために本明細書中で参考として援用する。
【背景技術】
【０００２】
（発明の背景）
本発明は概して、オブジェクトおよびオブジェクト間の関係を含む情報システムにおいて、クエリの成功を予測するシステムおよび方法に関する。より詳細には、本発明は、実際のクエリを実行せずに、インスタンスがオブジェクトに関係するかどうかを予測するシステムおよび方法に関する。
【０００３】
情報システム、特にデータベースシステムが、大きくなればなる程（例えば、テラバイトの域に）、効率的にデータベースをクエリするコストも上がる。ユーザがデータベースを複雑なクエリでヒットし、長い間待って「該当なし」しか得られないということは珍しくない。これらの空クエリは、何も有益な結果を生み出さずに、貴重なサーバ資源を摂取する。
【０００４】
ウェブが大衆化するにつれて、このような情報システムに同時にアクセスまたはヒットすることが可能なユーザの数は劇的に増えている。いくつかのウェブサイトは、一日当り数百万のヒットがある。空クエリが貴重な資源を消費する前に、空クエリを検出し、そしてフィルターにかけることは、ますます重要になってきている。
【０００５】
クエリがレコードを生み出すかどうかを予測することに付随するいくつかの問題は、インスタンスがオブジェクトに関係するかどうか（言い換えると、オブジェクトのインスタンスで本来のインスタンスに関係するものがあるか）を事前にどのように知るか、そしてランタイムに情報システムまたはデータベースにアクセスせずにどのようにしてこれを行うかを決定することを含む。他の問題は、特定のインスタンスが関係するオブジェクトをすべて列挙することである。
【０００６】
現在当該分野で公知のいくつかのデータベースは、いくつかの種類のクエリコスト分析および予測を支持する。テーブル、インデックスおよび結合インデックスのサイズに基づき、データベースは、クエリを実行するのに必要な時間を予測可能である。賢いクライアントは、時間がかかり過ぎるクエリを中止する。これにより、コストに基づいてクエリを中止する選択権がユーザに与えられ、一方で本発明は、予測される結果に基づいてユーザがクエリを中止することを可能にする。
【０００７】
多くのデータベースはさらに、インスタンスからインスタンス（ｉｎｓｔａｎｃｅ−ｔｏ−ｉｎｓｔａｎｃｅ）へのインデックステーブルを保持する。外部キー（ｆｏｒｅｉｇｎ  ｋｅｙ）／基本キーの関係を通して２つのテーブルが関係すれば、データベースは通常、Ｂ−ｔｒｅｅインデックスを保持する。Ｂ−ｔｒｅｅインデックスは、基本キーのインデックスファイルを示す数を含むリーフ（ｌｅａｆ）を含む外部キーを有する。これによりデータベースは、特定の外部キーが関係するすべての基本キーをすばやく見つけることができる。しかし、これらのＢ−ｔｒｅｅインデックスの問題は、クエリに答えるように設計されているが、クエリが実行される前にクエリの結果を予測するように設計されていないことである。さらに、これらのテーブルは通常、すぐ隣接するオブジェクト（すなわち、直接的な関係が存在する）のために保持される。
【０００８】
１９９８年１２月８日にＳｃｈｅｉｎｋｍａｎらに発行された米国特許第５，８４８，４２４号は、すべての目的のために本明細書中で参考として援用され、データ誘導インタフェースを開示する。誘導とは、ドラッグ可能要素およびドロップターゲットの機能である。インタフェースは、ドラッグおよびドロップパラダイムに基づき、そのためユーザはドラッグ可能要素をドラッグし、そしてドロップターゲット要素の上にドロップし、クエリを生成し得る。ユーザは、システムによってデータベースが生成される度に必ずしも予想されない任意の特別なクエリを簡単に作り出す（ｇｅｎｅｒａｔｅ）ことが可能になる。オブジェクトからオブジェクト（ｏｂｊｅｃｔ−ｔｏ−ｏｂｊｅｃｔ）への関係が格納される場所は、格納部（ｒｅｐｏｓｉｔｏｒｙ）またはマトリックスに基づく。マトリックスの各入力は、２つのクラスのオブジェクトの間の関係のタイプを表す。１つのクラスは、入力のコラムに対応し、他のクラスは入力のラインに対応する。マトリックスへの入力の存在、つまりマトリックスのラインおよびコラムの交差点におけるビットの存在は、オブジェクトから他のオブジェクトまでの関係を表す。オブジェクトからオブジェクトへの関係が存在するとしても、特定のインスタンスが存在するかどうかはそれだけで決定しない。しかし、第２のオブジェクトに関係する第１のオブジェクトのインスタンスが存在することは保障する。事実、両方のオブジェクトは、全くインスタンスを有し得ず、それでも格納部は、それらの間の関係を示す。
【０００９】
このようなシステムは、Ｓａｎ  Ｊｏｓｅ  ＣａｌｉｆｏｒｎｉａのＴｏｐＴｉｅｒ  Ｓｏｆｔｗａｒｅによって所有および発明されたＨｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒに具体化される。ウェブハイパーテキストメタフォア（ｍｅｔａｐｈｏｒ）に基づくシステムとは違い、ＴｏｐＴｉｅｒ  Ｈｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒがあれば、ユーザは、任意の特別なクエリを作り出し得る。このシステムは、ユーザが簡単に任意のクエリを作り出すために必要な解決策を提供するが、上に列挙する問題、特にクエリの結果を予測する問題に対する解決策は提供しない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
したがって、必要なのは、情報システムのクエリが空セットになるかどうかを、実際にクエリを実行することなく予測するシステムおよび方法である。
【課題を解決するための手段】
【００１１】
（発明の要旨）
本発明は、インスタンスからオブジェクト（ｉｎｓｔａｎｃｅ−ｔｏ−ｏｂｊｅｃｔ）へのビットマップを作り出し、そしてインスタンスからオブジェクトへのビットマップを用いて、クエリが結果を生み出すかどうかを予測する方法および装置に関する。より詳細には、オブジェクトおよび関係を有するデータベースを含む情報システムにおいて、本発明は、クエリが結果を生み出すかどうかを予測する方法を提供する。この方法は、オブジェクトのインスタンスがデータベース内の他のオブジェクトに関係するかどうかを示すインスタンスからオブジェクトへのビットマップを提供することを含み、そしてビットマップにアクセスし、クエリが結果を生み出すかどうかを決定することを含む。
【００１２】
インスタンスからオブジェクトへのビットマップは、オブジェクトのインスタンスから隣接するオブジェクトのインスタンスへの経路を決定し、インスタンスから隣接するオブジェクトへの経路を演算することで、オフラインで作り出され得る。そして、インスタンスから近隣しないオブジェクトへの経路は、第１のオブジェクトのインスタンスから第２のオブジェクトのインスタンスへの経路を、該第２のオブジェクトの該インスタンスから該近隣しないオブジェクトへの演算された経路と共に併合することで作り出され得る。これは、インスタンスから遠隔なオブジェクトへの経路が決定されるまで繰り返され得る。本発明の１つの実施形態によると、インスタンスから遠隔なオブジェクトへの経路の長さは、所定の長さに限定され得る。例えば、最大限の経路の長さ５が用いられ得る。
【００１３】
本発明の１つの実施形態によると、インスタンスからオブジェクトへのビットマップは、ＴｏｐＴｉｅｒのＨｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒを用いて、ドラッグ可能要素をドロップターゲットにドラッグすることがクエリの結果を生み出すかどうかを決定し得る。
【００１４】
本発明の別の実施形態によると、インスタンスからオブジェクトへのビットマップを、簡単に用いて、オブジェクトからオブジェクトへの確率マトリックスを生成し得、それは他のオブジェクトに関係する任意のインスタンスの可能性を決定するために用いられ得る。このようにして、通常のより大きなビットマップを用いずにクエリが結果を生み出すかどうかを明確に予測し、確率マトリックスは、このようなクエリが結果を生み出す可能性を見積もるために用いられ得る。
【００１５】
本発明のさらに完璧な理解は、好適な実施形態の詳細な説明および請求項を参照し、それらを図面と結びつけて考慮すれば得られ得る。図面中、同じ参照番号は同様の項目を参照する。
【発明を実施するための最良の形態】
【００１６】
（特定の実施形態の詳細）
本発明は、オブジェクトおよび関係を含む情報システムにおいて、クエリの結果を予測することを提供する。本発明はさらに、レコードを作り出さない（すなわち、空セットの）クエリを検出し、そしてフィルターにかけるための方法および装置を提供する。本発明は、関係型、オブジェクト指向、または他の適したデータベースと共に、そしてそれらのデータベースを変更することなく用いられ得る。
【００１７】
本明細書の残りにおいて、ＯＬＴＰデータベースを用いて本発明を説明する。しかし、本発明はこのようなデータベースに限定されないが、オブジェクト、インスタンスおよびそれらの間の関係を含む任意のタイプのシステムに適用され得るということは、明らかであるべきである。例えば、ＯＬＴＰオブジェクトとインスタンスとの間、ＯＬＡＰオブジェクトとインスタンスとの間、ウェブ構成要素またはオブジェクト、および／または文章構成要素またはオブジェクトの関係は、ほんの数例でああるが、熟考される。このようなシステムにおいて、各オブジェクトは通常、複数のインスタンスを含む。
【００１８】
本発明の１つの実施形態は、データベースのインスタンスからオブジェクトへのビットマップを作り出し、そして用いることが好ましい。システムにおける各オブジェクトの各インスタンスのビット−ベクトルを保持することで、作用する。ビット−ベクトルは、インスタンスから全ての他のクラスまたはオブジェクトまでの関係の存在を表す。本発明の１つの実施形態において、ベクトルまたはビットマップは、クエリが作り出される前に「オフライン」で演算される。クエリが要求される場合、ベクトルまたはビットマップは、ランタイムに低コストでアクセスされ得、そしてクエリを実行するために実際に必要となるよりもはるかに少ないランタイムで、クエリの結果を予測することを可能とする。
【００１９】
本発明はまた、インスタンスからオブジェクトへのビットマップを演算する方法も提供する。以下により詳細に説明するように、ビットマップを演算または生成するのにかかる演算時間は、Ｏ（Ｎ）（Ｎは、システム中のインスタンスの総数）である。
【００２０】
以下、データベースのインスタンスからオブジェクトへのビットマップと、このインスタンスからオブジェクトへのビットマップの使用とについてより詳細に説明する。以下の例において、大文字の文字（例えば、Ａ、Ｂ等）は、データベース中のオブジェクトまたはクラスを示す。クラスまたはオブジェクトのインスタンスは、大文字の文字の後に続く添え字によって示す。従って、Ａiは、クラスＡにおけるインスタンスを示す。加えて、Ａ→Ｂにすると、これは、クラスまたはオブジェクトＡおよびＢ間の関係を示す。米国特許第５，８４８，４２４号に開示された種類のＴｏｐＴｉｅｒ  Ｈｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒにおいて、このようなクラス対クラス関係の種類は、格納部（ｒｅｐｏｓｉｔｏｒｙ）に格納される。
【００２１】
Ａi→Ｂとすると、これは、ＡにおけるインスタンスとオブジェクトＢとの間の関係を示す；さらに、Ａi→Ｂjとすると、これは、関係Ａ→Ｂが適用された場合に、インスタンスＡiからインスタンスＢjが得られることを示す。最後に、２重矢印→→にすると、これは、間接的な関係経路を示す。
【００２２】
ここで図１を参照して、サンプルデータベース中の様々なオブジェクトおよびインスタンスの関係を示すブロック図が示される。簡潔にするため、この特定の例は、４つのオブジェクトまたはクラスＡ〜Ｄのみを提供する。図示のように、ＡからＢへ、ＢからＣへ、そしてＣからＤへと、クラス対クラス関係またはオブジェクト対オブジェクト関係が存在する。各オブジェクトの下に、各オブジェクトのサンプルインスタンスが図示されている。図１の例において、オブジェクトＡの１つのインスタンスＡ1のみが示され、一方、オブジェクトＤの８つのインスタンスＤ1〜Ｄ8が示されている。図１中の例は、インスタンス対インスタンスの関係を有する、オブジェクトＡ〜Ｄのいくつかのインスタンスのみを示す。言い換えると、データベース中に、オブジェクトＡの他のインスタンスＡ2〜Ａn、オブジェクトＤの他のインスタンスＤ9〜Ｄm等が存在し得る。また、他のインスタンス対インスタンス関係も存在し得るが、簡潔にするため、図示していない。
【００２３】
ユーザが、Ａ1が関連するインスタンスＤ全てについて問い合わせしたい場合を仮定する。典型的には、Ａ1が関連する各Ｂiを入手するためにクエリを行う必要がある。次いで、その結果得られた各Ｂiについて、新規のクエリを行って、各Ｂiが関連する１組のＣi,kを得るように実行する必要がある。次いで、これらを別個に結合して、１組のＣkを生成する必要がある。インスタンスＣkが関連する別個の１組のＤjを得るために、このプロセスを１回以上繰り返す必要がある。言い換えれば、Ａ1からオブジェクトＤのインスタンスＤjへの間接的な関係は、インスタンスＡ1からインスタンスＢiへの関係、インスタンスＢiからインスタンスＣkへの関係、およびインスタンスＣkからインスタンスＤjへの関係と等しい。
【００２４】
Ａ1→→Ｄj＝Ａ1→ＢiおよびＢi→ＣkおよびＣk→Ｄj
このような関係の計算の桁は、経路の長さの累乗に対するインスタンスの数である。スキーマ全体について−あらゆる可能な関係において−演算時間は、オブジェクトの数の累乗（これは、経路の長さを示す）に対するインスタンスの総数を、（各別個のソースに対する）オブジェクト数で乗算した値と等しい。メモリ要件は、重複のレコードが返送され得るという事実のために、さらに高い。従って、演算時間は以下のようになる：
Ｏ（Ｖ*ＮV）
周知の数学的表記法Ｏ（ｘ）を用いて、Ｖはオブジェクト数であり、Ｎ＝Σi=l...V｜Ｖｉ｜は、インスタンスの総数である。
【００２５】
さらに、この種類の計算を行うためには、複数のデータベースへのアクセスを何度も行う必要があり得る。典型的には、データベース時間は貴重かつ不足している資源である。データベースが混雑している間、ユーザ（例えば、クエリを実行しているユーザ）は全て、待機しなければならない。上記の例において、１つのインスタンスを計算するために、少なくとも３回のアクセスが必要となる。
【００２６】
従って、本発明は、結果を生成しない演算のランタイムを回避することを支援する。本発明は、クエリが何らかのレコードが生成するか否かを予測するために用いられるデータベースのインスタンスからオブジェクトへのビットマップを提供することにより、上記支援を行う。このビットマップは、システム中の各オブジェクトの各インスタンスのためのビットベクトルであり得る；ビットベクトルは、インスタンスから、システム中の他のクラスまたはオブジェクトのいくつかまたは全てに対する関係の存在を示す。図１の例において、インスタンスＡiに対して、インスタンスからオブジェクトへのビットマップは、以下を示す：
インスタンスＡiからオブジェクトＢに対する関係の存在または不在；
インスタンスＡiからオブジェクトＣに対する関係の存在または不在；および
インスタンスＡiからオブジェクトＤに対する関係の存在または不在。
【００２７】
インスタンスからオブジェクトへのビットマップは、クエリに対する結果が存在するか否かを効率的かつ敏速に演算することを可能にする。図１の例において、インスタンスＡ1に対するビットマップベクトルを調べることは、インスタンスＡ1からオブジェクトＤへの経路が存在することの証拠となるため、Ａ1が関連を有するインスタンスＤについてのクエリの全てにおいて、少なくとも１つの結果が返送されることの証拠となる。インスタンスからオブジェクトへのビットマップへのアクセスは、何分の１秒で可能であり、クエリを実際に終了する場合よりも非常に高速である。他の全てのインスタンスＡi（ｉ≠１）について、ビットマップは、オブジェクトＢ〜Ｄのいずれに対する関係も存在しないことを示す。
【００２８】
このようにして、本発明は、クエリの結果を予測すること（あるいはより詳細に言えば）所与のクエリが結果を生成するか否かを予測することを可能にする。これにより、ユーザまたはユーザによって実行されるクライアントプログラムが、クエリを選択することまたは結果を生成しないクエリをいずれかのデータベースアクセスが行なわれる前に中止することが可能となる。
【００２９】
インスタンスからオブジェクトへのビットマップは、関係が存在するか否かのみを答えることはできないが、副産物として、ランタイムにおいて所与のインスタンスについて実行可能な関係全てを列挙することもできる。この文脈において、実行可能な関係は、結果を生成する関係である。この技術によってイネーブルされたシステムは、リレーショナルデータベース環境または他のデータベース環境におけるナビゲーション中のユーザを先導して、実際に結果を生成する経路のみを提案または可能にすることができる。この能力は、ＴｏｐＴｉｅｒ’ｓ  Ｈｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒまたは他のあらゆるデータベースアクセス技術と共に用いられ得る。例えば、ＴｏｐＴｉｅｒ’ｓ  Ｈｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  Ｓｅｒｖｅｒの場合、ユーザがインターフェース中の要素をドラッグして、その要素をドロップターゲットに持ってくるたびに、システムは、ターゲットが強調表示されて、クエリが実際に結果を提供することを示すように、構成され得る。このことは、ユーザが１つの要素をドロップターゲット上にドロップしたときにその要素がクエリ結果を生成しないことをユーザに知らせることにより、ユーザがインターフェースをナビゲートする作業を支援し、これにより、ユーザがこのようなクエリに関わって時間を無駄にする事態を回避する。もちろん、クエリが結果を生成するか否かについてユーザに指示する他の方法も、企図され得る。
【００３０】
本発明の別の実施形態によれば、本発明のシステムおよび方法は、特定のインスタンスが関係を有するオブジェクト全てをリスト化することができる。そのため、ユーザに対して、結果を生成する実行可能なクエリを列挙して、これにより、特定のデータを通じたガイド付きナビゲーションを提供することが可能である。これは、所与のインスタンスについてベクトルビットマップを走査して、所与のインスタンスとの関係を有するオブジェクトのリストを表示することにより、行なわれ得る。当業者であれば理解するように、このリストは、様々な形態でユーザに提示され得る。例えば、図２および図３は、この情報をユーザに提示する１つの方法を示す。図２は、複数のインスタンス２０２および複数のオブジェクトまたはドロップターゲット２０４をリスト化したウェブページ２００リストを示す。図２の例において、インスタンス２０２−３は、ドロップターゲット２０４上にドラッグされている。ドロップターゲットまたはオブジェクト２０４の隣に有るチェックマーク２０６は、インスタンス２０２−３とオブジェクトまたはドロップターゲットとの間に関係が有ることを意味し、従って、インスタンス２０２−３をオブジェクト２０４のうちいずれかの上にドロップすると、クエリ結果が生成される。インスタンスとオブジェクトとの間に関係が存在しない場合、「Ｘ」２０８を用いて、関係が存在しないことをユーザに示す（図３を参照）。図３に示すように、インスタンス２０２−４は、チェックマーク２０６によって示されるように、オブジェクト２０４−３、２０４−４および２０４−５と関係を有するが、「Ｘｓ」２０８によって示されるように、オブジェクト２０４−１、２０４−２、２０４−６、２０４−７、２０４−８または２０４−９とは関係を有さない。
【００３１】
本発明のさらに別の実施形態によれば、関係ビットマップは、所定の長さの経路分だけ格納され得る。これは、ビットマップのオフライン演算時間を低減し、通常の環境において、ユーザにいかなる問題も与えない。実際、ほとんどのリレーショナルデータベースにおいて、長さの長い経路は通常は重要度が低くなるようである。本発明の一実施形態によれば、所定の数の経路長さは５である。従って、この場合において、インスタンスから最終オブジェクトまでの経路が５つのオブジェクト以下である場合においては、関係が、インスタンスからオブジェクトビットマップに格納されるのみである。
【００３２】
本発明のインスタンスからオブジェクトへのビットマップは、様々な様態で実現され得る。上述したように、インスタンスからオブジェクトへのビットマップは、ベクトル（Ｐi,ｉ＝１．．．Ｖ）として格納され得、ここで、Ｐiは、インスタンスからオブジェクト数ｉまでの経路の存在を示す。この場合、ベクトルのサイズは、インスタンスから他のオブジェクトへの可能な経路の数である。本発明の他の実施形態によれば、インスタンスからオブジェクトへのビットマップは、マトリックスまたは他のあらゆる適切な形態でも格納され得る。
【００３３】
本発明のインスタンスからオブジェクトへのビットマップは、基本的に、既存のインスタンス対インスタンス添え字表と極めて異なる。上述したように、本発明を用いて、結果が存在するか否かを予測することが可能であり、一方、インスタンス対インスタンス添え字表は典型的には、クエリに対する回答を提供するために用いられる。図１の例において、インスタンス対インスタンス表は、オブジェクトＡのインスタンスＡ1が、オブジェクトＢのインスタンスＢ1およびＢ2に関連することを示す。これは、「インスタンスＡ1とオブジェクトＢとはどのように関係するか」というクエリに対して回答Ｂ1およびＢ2を提供することを可能にする。本発明のインスタンスからオブジェクトへのビットマップは、クエリに対する回答が存在することを予測することを可能にするが、回答は提供しない。本発明のインスタンスからオブジェクトへのビットマップが典型的には、従来技術のインスタンス対インスタンス添え字表よりも少ない情報を提供する場合、本発明のインスタンスからオブジェクトへのビットマップは典型的には、インスタンス対インスタンス添え字表よりもずっと小さく、これにより、メモリおよび／または格納スペースの占有量がずっと少なくなる。例えば、上記にて示した例において、従来技術のインスタンス対インスタンス添え字表は、Ａ1とＢ1との間に関係があり、また、Ａ1とＢ2との間にも関係があることを示す。しかし、本発明のインスタンスからオブジェクトへのビットマップは、Ａ1からオブジェクトＢに対して関係が存在することのみを示すが、その関係の内容は示さない。
【００３４】
以下、インスタンスからオブジェクトへのビットマップの演算または生成について説明する。詳細には、本発明のビットマップは、様々な方法を用いて演算され得る。本発明の一実施形態によれば、ビットマップは、クエリを実行して、全てのインスタンス対オブジェクト関係を決定するだけで、演算され得る。しかし、上述したように、全てのクエリに必要な実行時間はＯ（Ｖ*ＮV）であり、これは、かなりの長さの時間である。
【００３５】
従って、本発明の別の実施形態によれば、インスタンスからオブジェクトへのビットマップの演算を容易化および加速化するプロセスがある。本発明のこの実施形態によれば、インスタンスからオブジェクトへのビットマップの「オフライン」演算のためのアルゴリズムが提供される。このアルゴリズムは、そのオンライン対応物に比べて有意に高速に動作する。従って、インスタンスからオブジェクトへのビットマップを確立するために必要な演算時間が好適には短縮され、時間が節約される。このコンテキストにおいて、「オフライン」は、ビットマップを用いてクエリの結果を予測する前に、ビットマップを演算することのみを意味する。当業者であれば、ビットマップが生成される間にシステムを他の目的に動作させてもよいことを理解する。
【００３６】
本発明のある実施形態によると、インスタンスからオブジェクトへのビットマップは、添え字完了（ｓｕｆｆｉｘ  ｃｏｍｐｌｅｔｉｏｎ）によって発生する。添え字完了は、インスタンスＡiからオブジェクトＤまでの間接的関係経路Ａi→→Ｄを計算するために、まずＢj→→Ｄを計算し、その後Ａi→Ｂjを計算し、最終的に２つをマージすることが可能であるという観察に基づく。この方法は、アルゴリズムが、より長い経路を計算するために既に演算された経路を再利用することを可能にする。
【００３７】
次に、図４を参照しながら、添え字完了の一例を説明する。図４は、様々なオブジェクトの関係を示すブロック図である。図４の実施形態において、５つのオブジェクトＡ〜Ｅには、その間に４つの関係が提供される。４つの関係とは、ＡからＢ、ＢからＣ、ＣからＤ、および、ＥからＢの関係である。この例において、インスタンスＢjからオブジェクトＤまでの間接的な関係経路Ｂj→→Ｄの演算は、インスタンスＡiからオブジェクトＤまでの間接的関係路Ａi→→Ｄ、およびインスタンスＥmからオブジェクトＤまでの間接的な関係経路Ｅm→→Ｄの両方の演算用の予め演算された添え字として機能を果たす。このようにして、インスタンスからオブジェクトへの関係の完全なセットが、インスタンスの数のオーダーで演算され得る。
【００３８】
次に、インスタンスからオブジェクトへのビットマップを演算する方法の１つの実施形態をさらに詳細に示す。まず、情報システムにおいて、それぞれのインスタンスについて、隣接するオブジェクトが判定される。これは、例えば、当該分野において公知のタイプのインスタンスからインスタンスへのインデックステーブルを用いることによって行われてもよいし、これらの関係を判定するためにクエリが用いられてもよい。
【００３９】
次の工程において、長さが２のインスタンスからオブジェクトへの関係経路が演算される。これは、以前の工程において演算されたインスタンスから隣接するオブジェクトへの関係経路を用いて行われ得る。その後、これらの予め演算された関係経路は、より長い関係経路を演算する添え字として用いられる。同じ工程は、より長い長さのインスタンスからオブジェクトへの関係経路を発生するために必要な回数繰り返され得る。工程が繰り返されるたび、新たなインスタンスからオブジェクトへの関係経路が加えられ、新たな経路は、それぞれ、以前の工程で演算された関係経路よりオブジェクト１つ分長さが長い。例えば、図４の例において、インスタンスＢjからオブジェクトＤまでのインスタンスからオブジェクトへの関係経路は、長さが２である。その後、これらの経路は、インスタンスＡiからオブジェクトＤまでのインスタンスからオブジェクトへの関係経路、およびインスタンスＥmからオブジェクトＤまでのインスタンスからオブジェクトへの関係経路の演算において用いられ得る。これらの関係経路は、長さが３である。
【００４０】
それぞれの工程で、演算時間は、インスタンスの数のオーダーである。最もひどい場合には、全てのインスタンスがインスタンスからオブジェクトへの関係経路の開始点として用いられ得る。従って、その場合、完全な処理の演算時間は、Ｏ（Ｎ）である。ここで、Ｎ＝Σi=1...V│Ｖｉ│は、インスタンスの総数である。
【００４１】
上述したように、アルゴリズムの深さを所定の長さより短い経路まで制限することは、プロセスにおける工程の数を制限することによって、演算時間をさらに低減し得る。深さ５は、上記の例と同様に、長さが５オブジェクトを越えない経路のためにだけ、関係ビットマップを格納するようにアルゴリズムを制限する。これは、関係の完全なセットを演算しないが、通常、長さが増大した経路は重要度が低いので、所望され得る。
【００４２】
ビットマップの演算時間を短縮するために、インスタンスからオブジェクトへのビットマップが演算されている間、情報システムへのアクセスを制限することが所望され得る。すなわち、上述したように、インスタンスからオブジェクトへのビットマップは、おそらく、予測が必要なクエリを発生する前に、「オフライン」で演算される。しかし、当業者であれば理解するように、情報システムは、他の目的のため、例えば、予測が必要ないクエリのために用いられ得る。従って、情報システムへのロードを最小限にすることは、重要であり、特に、サーバ利用可能性が最も重要であるリアルタイム処理データベースにおいて重要である。
【００４３】
本発明の他の実施形態において、関係マップのキャッシュが用いられて、ビットマップの「オフライン」演算の速度が増大し得る。当業者であれば理解するように、関係マップは、キーの対のテーブルである。関係のオブジェクトにつき、それぞれ１つのキーがある。関係データベースにおいて、結合が調査される２つのテーブルの内部結合である。システムにおける関係のそれぞれについて、このマップをキャッシュすることによって、アルゴリズムは、関係１つにつきシステムを１度以上クエリする必要がないので、システム上のロードは、大幅に最小化される。例えば、Ａi→Ｄを計算するため、アルゴリズムは、上述したように、結合Ｃk→Ｄ、Ｂj→Ｃ、その後、Ａi→Ｂについて、データベースにクエリする。反対の関係Ｄl→Ａを計算するために、再度データベースにクエリする必要はない。各２つの隣接するテーブルの間の結合テーブルは、既にアルゴリズムによってローカルにキャッシュされている。
【００４４】
同様に、キャッシュされた結合テーブルは、クエリされた後、分類され得る。これは、ビットマップをより速くマージすることを可能にする。例えば、全てのインスタンスＢjの（オブジェクトＣおよびＤへの）ビットマップを計算した後、アルゴリズムは、Ａi→Ｂjについてクエリする。アルゴリズムは、インスタンスＡiのオーダーでこのリストを分類し、（現在結合から戻っているものだけではなく）全てのインスタンスＡi上で実行し、ＡiがＢjとの関係を有する、キャッシュされた結合テーブルにおいて発生を全て探す。アルゴリズムは、関連する発生を見つけた場合、ビットマップを、Ｂにおける関連するインスタンスのビットマップで論理和演算する。このようにしてキャッシュされた結合テーブルを用いることによって、サーチは、Ｏ（Ｎ）ではなくＯ（ｌｏｇ  Ｎ）を取る。
【００４５】
次に、図５のフローチャート５００を参照しながら、インスタンスからオブジェクトへのビットマップを演算し、それを用いてクエリの結果を予測するプロセスまたは方法を説明する。フローチャートの第１の部分、開始から工程５０８までは、インスタンスからオブジェクトへのビットマップの演算に相当する。プロセスの第２の部分、工程５１０から５１８までは、クエリの予測された結果を実行する。開始の後、工程５０２で、データベースのインスタンスのそれぞれについて、隣接するオブジェクトへの関係経路が決定される。変数Ｌは１に設定される。
【００４６】
工程５０４で、長さＬの添え字経路のそれぞれについて、長さＬ＋１のインスタンスからオブジェクトへの関係経路が演算される。プロセスは、工程５０６に進む。ここで、Ｌは、１増大する。
【００４７】
次の工程５０８で、所定の最大長Ｌmaxに達するかどうかが判定される。達している場合、プロセスは、工程５１０に進む。そうでない場合には、工程５０４に戻る。工程５０４、５０６、および５０８を通じてループすることによって、増大した長さのインスタンスからオブジェクトへの関係経路が加えられる。それぞれのループで、新たな経路の数は、減少する可能性が高い。いずれにしても、最終的には、インスタンスからオブジェクトへの関係のビットマップが入手される。
【００４８】
工程５１０で、新たなクエリが予想される。クエリのリクエストが受信される場合、プロセスは、工程５１２へと進む。ここで、インスタンスからオブジェクトへのビットマップがアクセスされる。インスタンスからオブジェクトへのビットマップにアクセスすることによって、システムは、クエリリクエストが結果を有するクエリを発生するかどうかを予測し得る。工程５１４で、結果があることが予測される場合、プロセスは、工程５１６に進む。そうでない場合には、プロセスは、工程５１８に進む。工程５１６で、クエリは実行され、プロセスは工程５１０に戻る。工程５１８で、クエリは中止され、プロセスは工程５１０に戻る。
【００４９】
図５のフローチャート５００は、本発明の可能な実施形態のうちの１つの例示に過ぎない。本発明の他の実施形態によると、ビットマップを発生するプロセスは、クエリの結果を予測するためにビットマップを用いるプロセスと完全に分離される。すなわち、図５を参照すると、フローチャート５００の上部分は、フローチャート５００の下部分から、分離され、異なるときに実行される。いずれにしても、本発明は、例示した実施形態に限定されない。
【００５０】
次に、図６を参照しながら、本発明の他の実施形態を説明する。本発明のこの特定の実施形態によると、インスタンスからオブジェクトへのビットマップを用いて、関係が有るかどうか、またはクエリが結果を生成するかどうかを判定する代わりに、オブジェクトからオブジェクトへの確率マトリックスが用いられる。オブジェクトからオブジェクトへの確率マトリックスは、特定のインスタンスが他のオブジェクトに関連するかどうかを示さないが、インスタンスがオブジェクトに関連するかどうかの可能性または確率を単に示す。これは、第２のオブジェクトに関連する第１のオブジェクトのインスタンスの数を、第１のオブジェクトのインスタンスの総数で割ることによって達成される。インスタンスからオブジェクトへのビットマップが用いられて、第１のオブジェクトにおける第２のオブジェクトに関連するインスタンスの数が判定され得る。
【００５１】
依然、図６を参照しながら、特定の例が示される。図６に示すように、オブジェクトＡは、４つのインスタンスを含む。しかし、２つのインスタンス（Ａ1およびＡ2）のみが、オブジェクトＢと関連する。従って、オブジェクトＡにおける任意のインスタンスがオブジェクトＢと関連する可能性または確率は、５０％（２／４）である。同様に、オブジェクトＢは、６つのインスタンスを含み、そのうち４つがオブジェクトＣと関連し、オブジェクトＣは、６つのインスタンスを含み、そのうち５つがオブジェクトＤと関連する。従って、オブジェクトＢにおける任意のインスタンスがオブジェクトＣと関連する可能性または確率は、６６％（４／６）であり、オブジェクトＣにおける任意のインスタンスがオブジェクトＤと関連する可能性または確率は、８３．３％（５／６）である。
【００５２】
経路長が１より長いオブジェクトの関係の確率を計算するため、より短い経路の確率が共に乗じられる。例えば、オブジェクトＡにおける任意のインスタンスがオブジェクトＣと関連する可能性は、オブジェクトＡとオブジェクトＢとの間の確率にオブジェクトＢとオブジェクトＣとの間の確率を乗じることによって、計算される。この例においては、オブジェクトＡにおける任意のインスタンスがオブジェクトＣと関連する可能性は、５０％＊６６％＝３３％である。同様に、オブジェクトＡにおける任意のインスタンスがオブジェクトＤと関連する可能性は、２７．７８％（５０％＊６６％＊８３．３％）であり、オブジェクトＢにおける任意のインスタンスがオブジェクトＤと関連する可能性は、５５．５６％（６６％＊８３．３％）である。
【００５３】
結果として、本発明は、実行時間中に、クエリを実行またはデータベースにアクセスすることなく、特定のクエリ（例えば、Ｔｏｐ−ＴｉｅｒのＨｙｐｅｒ−Ｒｅｌａｔｉｏｎａｌ  ＳｅｒｖｅｒにおけるＤｒａｇ−ａｎｄ−Ｒｅｌａｔｅ動作）が結果または記録を生成しないことを、ユーザに通知するシステムおよび方法を提供する。さらに、本発明は、ある特定のインスタンスについて可変ナビゲーションターゲットを列挙するために用いられ得、結果を返す関係の確率を示すために用いられ得る。さらに、本発明は、インスタンスからオブジェクトへのビットマップ、およびオブジェクトからオブジェクトへの確率マトリックスのオフライン演算の方法を提供する。本発明の好適な実施形態の詳細な説明を上で行ったが、様々な変更例、改変例、および均等物が当業者にとって明らかである。例えば、本発明のアルゴリズムは、ＯＬＴＰデータベース用に用いられるとして提示されているが、ＯＬＴＰに限定されるものではない。本発明は、オブジェクトおよびオブジェクト間の関係の周りに構築される任意のシステムと共に用いられ得る。従って、上記の説明は、本発明の範囲を限定するものではなく、本発明は、添付の特許請求の範囲によって規定される。
【図面の簡単な説明】
【００５４】
【図１】図１は、さまざまなオブジェクトおよびオブジェクトのインスタンスの関係を示すブロック図である。
【図２】図２は、インスタンスと他のオブジェクトとの間に関係が存在することを、ウェブページがどのように示すかを図示するウェブページの図解である。
【図３】図３は、インスタンスと他のオブジェクトとの間に関係が存在するまたは存在しないことを、ウェブページがどのように示すかを図示するウェブページの別の図解である。
【図４】図４は、さまざまなオブジェクトの関係を示すブロック図である。
【図５】図５は、インスタンスからオブジェクトへのビットマップを演算し、そしてそれを用いてクエリの結果を予測するためのプロセスのフローチャートである。
【図６】図６は、さまざまなオブジェクトおよびオブジェクトのインスタンスの関係を示すブロック図である。
【図１】
2006172491.tif 000003
【図２】
2006172491.tif 000004
【図３】
2006172491.tif 000005
【図４】
2006172491.tif 000006
【図５】
2006172491.tif 000007
【図６】
2006172491.tif 000008
【手続補正書】
【提出日】平成18年1月12日(2006.1.12)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2006172491.tif 000009
【図２】
2006172491.tif 000010
【図３】
2006172491.tif 000011
【図４】
2006172491.tif 000012
【図５】
2006172491.tif 000013
【図６】
2006172491.tif 000014
【手続補正書】
【提出日】平成18年4月6日(2006.4.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
計算手段と格納手段とを備えた情報システムであって、該格納手段は、複数のオブジェクトと、該複数のオブジェクトの各々に対する複数のオブジェクトインスタンスとを格納し、該複数のオブジェクトインスタンスの各々は、該複数のオブジェクトの対応する１つのインスタンスであり、該格納手段は、各オブジェクトインスタンスに対するビットベクトルを更に格納し、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスのビットベクトルは、該第１のオブジェクトインスタンスと該第１のオブジェクトを除く該複数のオブジェクトの各々との間に関係が存在するか否かを示す、情報システムにおいて、
該第１のオブジェクトインスタンスと該複数のオブジェクトのうちの第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在するか否かを決定する方法であって、
該方法は、
該計算手段が、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスと第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在するか否かを要求するクエリを受信するステップと、
該計算手段が、該第１のオブジェクトインスタンスのビットベクトルを走査することにより、該第１のオブジェクトインスタンスと該第２のオブジェクトとの間に関係が存在するか否かを決定するステップと、
該第１のオブジェクトインスタンスと該第２のオブジェクトとの間に関係が存在すると該計算手段が決定した場合には、該計算手段が、該第１のオブジェクトインスタンスと該第２のオブジェクトの該複数のオブジェクトインスタンスのいずれかとの間に関係が存在することを示す結果を生成するステップと
を包含する、方法。
【請求項２】
前記計算手段が、前記第１のオブジェクトインスタンスに対する関係であって、結果を生成するすべての関係を示すことを更に包含する、請求項１に記載の方法。
【請求項３】
前記計算手段が、前記第１のオブジェクトインスタンスのビットベクトルを走査することにより、該第１のオブジェクトインスタンスと前記第１のオブジェクトを除く前記複数のオブジェクトの各々との間に関係が存在するか否かを決定することと、
該計算手段が、該複数のオブジェクトのうち該第１のオブジェクトインスタンスとの間に関係が存在するすべてのオブジェクトをリストにすることと
を更に包含する、請求項１および２のいずれかに記載の方法。
【請求項４】
前記複数のオブジェクトと前記複数のオブジェクトインスタンスとがウェブページに表示され、
該複数のオブジェクトのうち前記第１のオブジェクトインスタンスとの間に関係が存在するすべてのオブジェクトをリストにすることが、前記第１のオブジェクトとの間に関係が存在する該複数のオブジェクトについての表示を該ウェブページ上に提供することを包含する、請求項３に記載の方法。
【請求項５】
前記複数のオブジェクトと前記複数のオブジェクトインスタンスとがウェブページに表示され、
前記第１のオブジェクトとの間に関係が存在する前記複数のオブジェクトを除く複数のオブジェクトについての表示が該ウェブページ上に提供される、請求項３に記載の方法。
【請求項６】
前記ビットベクトルが所定の長さを有している、請求項１に記載の方法。
【請求項７】
前記ビットベクトルが、クエリを実行することにより、前記複数のオブジェクトと前記複数のオブジェクトインスタンスとの間のすべての関係を決定することによって計算される、請求項１に記載の方法。
【請求項８】
計算手段と格納手段とを備えた情報システムであって、該格納手段は、複数のオブジェクトと、該複数のオブジェクトの各々に対する複数のオブジェクトインスタンスとを格納し、該複数のオブジェクトインスタンスの各々は、該複数のオブジェクトの対応する１つのインスタンスであり、該格納手段は、各オブジェクトインスタンスに対するビットベクトルを更に格納し、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスのビットベクトルは、該第１のオブジェクトインスタンスと該第１のオブジェクトを除く該複数のオブジェクトの各々との間に関係が存在する確率を示す、情報システムにおいて、
該第１のオブジェクトインスタンスと該複数のオブジェクトのうちの第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在する確率を決定する方法であって、
該方法は、
該計算手段が、第１のオブジェクトのインスタンスである第１のオブジェクトインスタンスと第２のオブジェクトの複数のオブジェクトインスタンスのいずれかとの間に関係が存在する確率を要求するクエリを受信するステップと、
該計算手段が、該第１のオブジェクトインスタンスの該ビットベクトルを走査することにより、該第１のオブジェクトインスタンスと該第２のオブジェクトとの間に関係が存在する確率を決定するステップと、
該計算手段が、該第１のオブジェクトインスタンスと該第２のオブジェクトの該複数のオブジェクトインスタンスのいずれかとの間に関係が存在する確率を示す結果を生成するステップと
を包含する、方法。
【請求項９】
前記複数のオブジェクトは、第３のオブジェクトを含み、
該第３のオブジェクトに対応する前記複数のオブジェクトインスタンスは、前記第２のオブジェクトと関係を有する少なくとも１つのオブジェクトインスタンスと、該第２のオブジェクトと関係を有さない少なくとも１つのオブジェクトインスタンスとを含み、
該方法は、
前記計算手段が、該第３のオブジェクトに含まれるオブジェクトインスタンスのうち該第２のオブジェクトと関係を有するオブジェクトインスタンスの数を該第３のオブジェクトに対応するオブジェクトインスタンスの総数で割ることによって、（ｉ）該第３のオブジェクトに対応する該複数のオブジェクトインスタンスのうちの第１のインスタンスと（ｉｉ）該第２のオブジェクトとの間に関係が存在する確率である第１の確率を決定することを更に包含する、請求項８に記載の方法。
【請求項１０】
前記第１のオブジェクトに対応する前記複数のオブジェクトインスタンスは、前記第３のオブジェクトと関係を有する少なくとも１つのオブジェクトインスタンスと、該第３のオブジェクトと関係を有さない少なくとも１つのオブジェクトインスタンスとを含み、
該方法は、
前記計算手段が、該第３のオブジェクトと関係を有する該第１のオブジェクトのインスタンスの数を該第１のオブジェクトのインスタンスの総数で割ることによって、（ｉ）該第１のオブジェクトに対応する該複数のオブジェクトインスタンスのうちの第１のインスタンスと（ｉｉ）該第３のオブジェクトとの間に関係が存在する確率である第２の確率を決定することを更に包含する、請求項９に記載の方法。
【請求項１１】
前記計算手段が、前記第１の確率に前記第２の確率を乗じることによって、（ｉ）前記第１のオブジェクトに対応する前記複数のオブジェクトインスタンスのうちの前記第１のインスタンスと（ｉｉ）前記第２のオブジェクトとの間に関係が存在する確率である第３の確率を決定することを更に包含する、請求項１０に記載の方法。
【請求項１２】
前記第３の確率は、前記第１のオブジェクトインスタンスのビットベクトルに提供され、前記第１のオブジェクトインスタンスと前記第２のオブジェクトとの間に関係が存在する確率を決定するために走査される、請求項１１に記載の方法。