(57)【要約】【課題】１つのサーバと複数のクライアントを有する改良された情報検索システムを提供すること。【解決手段】サーバは、１つ以上のデータ記憶媒体に対するアクセスを有し、この媒体に、サーバがデータベースを保持する。データベースは、キー値に基づいてサーチすることができる複数のレコードを有する。サーバは、データベースに加えてページ定義テーブルを保持する。ページ定義テーブルは、キー値の対を各々示す複数のエントリを有する。情報サーチを実行するため、クライアントは、サーバに対しサーチ値を提出する。サーバは、そのサーチ値に対応するページ定義テーブルからの１つのエントリを識別することにより応答する。サーバは、次に、識別したエントリの前記対のキー値が限定するキー値を有する１つのデータベース・レコード集合を識別する。これらデータベース・レコードからのデータは、サーチ結果としてクライアントに返す。【選択図】図３
2010044777.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが複数のレコードからなる複数のデータベース・レコード集合を格納しているデータベースから、与えられたサーチ値に基づいてデータベース・レコード集合を見つける方法であって、前記方法が、
上側キー値および下側キー値からなる第１および第２のキー値対を含む複数のエントリを有するサーチ可能なテーブルを参照して、前記サーチ値をその規定する範囲に含む前記第１のキー値対を含む前記エントリを識別するステップと、
前記識別したエントリに含まれる前記第２のキー値対によって囲まれる前記データベース・レコード集合を識別するステップと
を含み、
先頭の前記エントリの前記第１のキー値対の下側キー値は最小値であり、最後尾の前記エントリの上側キー値は最大値であり、前記最後尾のエントリを除く前記各エントリの前記第１のキー値対の上側キー値は、後続のエントリの前記下側キー値と同じであり、前記各エントリの前記第２のキー値対の下側キー値、上側キー値は、前記各データベース・レコード集合の下側レコード、上側レコードとそれぞれ同値であることを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記各エントリの前記第１のキー値対の下側キー値、上側キー値と前記第２のキー値対の下側キー値、上側キー値とは同値であることを特徴とする方法。
【請求項３】
請求項１記載の方法において、前記第２のキー値対は、同じエントリの前記第１のキー値対が規定する範囲を含むより広い範囲を規定することを特徴とする方法。
【請求項４】
請求項１記載の方法であって、
前記識別された第１のキー値対の規定する範囲に含まれる値の内少なくとも１つを第２のサーチ値とし、前記テーブルを参照して、前記第２のサーチ値をその規定する範囲に含む第１のキー値対を含む第２のエントリを識別するステップと、
前記第２のエントリに含まれる第２のキー値対の規定する範囲に含まれる第２のデータベース・レコード集合を識別するステップと
をさらに含むことを特徴とする方法。
【請求項５】
１つのサーバと複数のクライアントを有するコンピュータ・システムにおいて、複数のレコードからなる複数のデータベース・レコード集合を格納しているサーバ保持のデータベースから、与えられたサーチ値に基づいてデータベース・レコード集合を見つける方法であって、
上側キー値および下側キー値からなる第１および第２のキー値対を含む複数のエントリを有するサーチ可能なテーブルを、前記サーバにおいて保持するステップと、
前記クライアントが前記与えられたサーチ値を前記サーバに提出するステップと、
前記サーバが、前記テーブルを参照して、前記サーチ値をその規定する範囲に含む前記第１のキー値対を含む前記エントリを識別するステップと、
前記サーバが前記識別したエントリに含まれる前記第２のキー値対によって囲まれる前記データベース・レコード集合を識別するステップと、
前記サーバが前記識別したデータベース・レコード集合を前記クライアントに返すステップと、
を含み、先頭の前記エントリの前記第１のキー値対の下側キー値は最小値であり、最後尾の前記エントリの上側キー値は最大値であり、前記最後尾のエントリを除く前記各エントリの前記第１のキー値対の上側キー値は、後続のエントリの前記下側キー値と同じであり、前記各エントリの前記第２のキー値対の下側キー値、上側キー値は、前記各データベース・レコード集合の下側レコード、上側レコードと同値であることを特徴とする方法。
【請求項６】
請求項５記載の方法において、前記各エントリの前記第１のキー値対と前記第２のキー値対とは同じであることを特徴とする方法。
【請求項７】
請求項５記載の方法において、前記第２のキー値対は、同じエントリの前記第１のキー値対が規定する範囲を含むより広い範囲を規定することを特徴とする方法。
【請求項８】
請求項５記載の方法であって、前記サーバが、前記クライアントに対し、前記識別したデータベース・レコード集合と共に、前記第１のキー値対を返すステップをさらに含むことを特徴とする方法。
【請求項９】
請求項５記載の方法であって、前記サーバが、前記クライアントに対し、前記識別したデータベース・レコード集合と共に、前記第２のキー値対を返すステップをさらに含むことを特徴とする方法。
【請求項１０】
請求項５記載の方法であって、
前記サーバが、前記識別したデータベース・レコード集合と共に、前記識別した１つの前記第１のキー値対を前記クライアントに返すステップと、
前記クライアントが前記返された第１のキー値対の規定する範囲に含まれる値の内少なくとも１つを前記第２のサーチ値を前記サーバに提出するステップと、
前記サーバが、前記テーブルを参照して、前記第２のサーチ値をその規定する範囲に含む第１のキー値対を含む第２のエントリを識別するステップと、
前記サーバが、前記第２のエントリに含まれる第２のキー値対の規定する範囲に含まれる第２のデータベース・レコード集合を識別するステップと
をさらに含むことを特徴とする方法。
【請求項１１】
情報検索システムであって、
１つ以上のデータ記憶媒体に対するアクセスを有するサーバと、
前記１つ以上のデータ記憶媒体に保持したデータベースであって、複数のレコードからなる複数のデータベース・レコード集合を格納している前記データベースと、
前記１つ以上のデータ記憶媒体に保持したサーチ可能なテーブルであって、上側キー値および下側キー値からなる第１および第２のキー値対を含む複数のエントリを有する前記テーブルと、
前記サーバに対しサーチ値を提出するクライアントと、
を備え、
先頭の前記エントリの前記第１のキー値対の下側キー値は最小値であり、最後尾の前記エントリの上側キー値は最大値であり、前記最後尾のエントリを除く前記各エントリの前記第１のキー値対の上側キー値は、後続のエントリの前記下側キー値と同じであり、前記各エントリの前記第２のキー値対の下側キー値、上側キー値は、前記各データベース・レコード集合の下側レコード、上側レコードとそれぞれ同値であり、
前記サーバが、
サーチ値の提出に応答することにより、前記テーブルを参照して、前記提出されたサーチ値を囲む前記第１のキー値対を有する前記エントリを識別し、
前記識別したエントリに含まれる第２のキー値対の規定する範囲に含まれる前記データベース・レコード集合を識別し、
前記識別したデータベース・レコード集合を前記クライアントに返す
ことを特徴とする情報検索システム。
【請求項１２】
請求項１１記載の情報検索システムにおいて、前記各エントリの前記第１のキー値対の下側キー値、上側キー値と前記第２のキー値対の下側キー値、上側キー値とは同値であることを特徴とする情報検索システム。
【請求項１３】
請求項１１記載の情報検索システムにおいて、前記第２のキー値対は、同じエントリの前記第１のキー値対が規定する範囲を含むより広い範囲を規定することを特徴とする情報検索システム。
【請求項１４】
請求項１１記載の情報検索システムにおいて、前記サーバが、前記クライアントに対し、前記識別したデータベース・レコード集合と共に、前記第１のキー値対を返すことを特徴とする情報検索システム。
【請求項１５】
請求項１１記載の情報検索システムにおいて、前記サーバが、前記クライアントに対し、前記識別したデータベース・レコード集合と共に、前記第２のキー値対を返すことを特徴とする情報検索システム。
【請求項１６】
請求項１１記載の情報検索システムにおいて、
前記サーバが、前記識別したデータベース・レコード集合と共に、前記識別した１つの前記第１のキー値対を前記クライアントに返し、
前記クライアントが前記返された第１のキー値対の規定する範囲に含まれる値の内少なくとも１つを前記第２のサーチ値を前記サーバに提出し、
前記サーバが、
前記テーブルを参照して、前記第２のサーチ値をその規定する範囲に含む第１のキー値対を含む第２のエントリを識別し、
前記第２のエントリに含まれる第２のキー値対の規定する範囲に含まれる第２のデータベース・レコード集合を識別し、
前記第２の識別したデータベース・レコード集合を前記クライアントに返す
ことを特徴とする情報検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースをリモートのクライアントを使用してサーチしブラウズする方法に関するものである。
【背景技術】
【０００２】
大きなデータベース・アプリケーションは、通常は、あるフィーチャをサポートしていて、これによりユーザは、このユーザがサーチして求めようとしている実際の値にわずかに近似するに過ぎないサーチ・キーをエンターできるようにしている。しばしば、これは、“＊”のような“ワイルドカード”キャラクタを使って行われている。この“＊”キャラクタは、可能性のある全てのキャラクタ・ストリングを表す。このため、“jon＊”に対するサーチは、ストリング“jon”で始まりそして任意の他のストリングのキャラクタが続くあらゆる値を検索することになる。“Jon”，“Jones”，“Jonathan”は全て、“jon＊”をサーチ・キーとして使用した結果として検索されることになる。
【０００３】
このサーチ方法の利点は、フレキシブルであり、ユーザに対し説明が容易であり、また実施が容易である点である。しかし、この方法は、幾分限定されたものである。例えば、あるサーチから返ってきた値がサーチしている値を含んでいない場合、この質問（query）を拡張または変更して“手近な”値を見つけ出すための明解な方法がない。さらに、この方法は、ユーザが知らないであるいは故意に、過大に広い質問、データベースの受け入れられない程大きな部分が返されるような広い質問をするのを許容する。例えば、あるユーザが“ａ＊”と質問をタイプするとすると、これは、“ａ”で始まる全ての値が返ってくることになる。
【０００４】
今日、データベースは、インターネットを介して質問を受けることが増大してきており、サーチ結果をユーザに対し比較的小さな部分で返すこともより重要となってきている。サービス・プロバイダの中には、計測した長さでサーチ結果を提供するプロバイダがある。例えば、サーチの最初の２０個のヒットのみを返し、そしてユーザには、次の２０個のヒットを要求するオプションを与える。しかし、このようなサービス・プロバイダは、その次の２０個のヒットが要求されたときに、全く新たなサーチを開始し、そしてこの結果から第２のグループの２０個のヒットを選択するようにしていることが多い。この理由は、サーバにおいて、あるデータベースを任意の所与の時刻にアクセスすることのある数千ものユーザに関して、状態情報を保持することが実際的ではないからである。このため、多くのソートされた行を返す質問は、サーバに対する各要求に関して完全に実行されることになる。これは、データをサーチし、ソートしそしてクライアントに伝送するため、サーバ・リソースのかなりの量を浪費する。
【０００５】
この従来技術は、データベース・ルックアップ技法を含み、この技法は、これらの問題にある程度対処している。この従来技術の技法によれば、２つのテーブルが、実際のデータベースに加えて保持されていた。第１のテーブルは、複数の行を有し、その各行がデータ・レコードの個々の集合に対応していた。各行は、３つの値、すなわち、最初（first）の値、最後（last）の値、そしてＩＤに対するフィールドを含んでいた。この最初と最後の値は、電話帳または辞書のトップにあるインデックス・エントリに類似のデータの集合またはページを定義していた。ある特定のテーブル・エントリに対応する１つのデータ・ページは、最初の値と最後の値との間の範囲内のデータ値を全て引っくるめて含むことになる。
【０００６】
このデータ・ページは、予め生成した別のページ内に置かれた。
【０００７】
１つの例として、以下のラスト・ネームのデータベースについて考えることにする。
【０００８】
【表１】
2010044777.tif 000003
【０００９】
【表２】
2010044777.tif 000004
【００１０】
これに対応するテーブル（ページ定義テーブル（page definition table）と呼ぶ）は、以下のテーブル１に示すように現れることになる。
【００１１】
【表３】
2010044777.tif 000005
【００１２】
このテーブルによれば、ＩＤ０（ページ０）を有する情報ページは、“Ableson”で始まりそして“Baxter”で終わる１０個のネームを含んでいる。ページ１は、“Beaver”で始まりそして“Bowman”で終わる次の１０個のネームを有する。このページ定義テーブルは、各ページがほぼ等しい数のネームを有するように作成されていた。
【００１３】
第２のテーブルも保持されていた。このテーブルは、ＩＤ番号で配列した、データベースからの実際のデータを有していた。上記例では、このようなテーブル（ページ・データ・テーブル（page data table）と呼ぶ）は、以下のように現れることになる。
【００１４】
【表４】
2010044777.tif 000006
【００１５】
このテーブルのＩＤ値は、ページ定義テーブル（テーブル１）のＩＤ値に対応している。PAGEDATA値は、データベースから取った、特定のページに関しユーザに返すべき実際のデータから成っている。ここでの例においては、このデータは、単にネーム自体から成っている。実際のアプリケーションにおいては、電話番号や住所のような他のデータも含ませることがある。
【００１６】
この技法の下でサーチを実行するには、ユーザは、ネームの開始部分、あるいはこのネームに近似しているとユーザが考える何等かのストリングをエンターする。例えば、ユーザがサーチ・ストリングとして“fle”をエンターするとする。このストリングは、テーブル１を質問するのに使用されて、このサーチ・ストリングに渡る（span）行のＩＤを見つけ出す。ＳＱＬフォーマットを使用すると、このサーチは、以下のようになる。
【００１７】
select ID from page_definition_table where FIRST<=‘fle’and LAST>=‘fle’
ここで、“page_definition_table”はテーブル１を指している。
【００１８】
この場合、６がその適当なＩＤであり、これは、ページ６をユーザに返すべきことを示す。その適当なデータを見つけ出すには、第１のサーチで識別したＩＤ番号を使用することにより、テーブル２に対し第２の質問を実行する。これを達成するＳＱＬ質問は、以下の通りとなる。
【００１９】
select PAGEDATA from page_data_table where ID==X
ここで、“page_data_table”は、テーブル２を指し、Ｘは第１の質問から返されたＩＤ値である。PAGEDATA値は、そのＩＤ値と共にユーザに返されていたものである。このＩＤ値を使用することにより、ユーザは、テーブル２に対する質問を減分したあるいは増分したＩＤを使用して行うことにより、前のあるいは後のページをブラウズすることができていた。
【発明の概要】
【発明が解決しようとする課題】
【００２０】
この技法には、いくつかの深刻な問題がある。１つの問題は、ユーザが、ページ定義テーブルの互いに隣接する行の最初の値と最後の値との間に入るサーチ・ストリングを提出したときに起きていた。例えば、“grant”のサーチ・ストリングは、テーブル１内に示したページ定義テーブルの行７と行８との間に入ることになる。これは、このサーチを失敗とさせ、したがってデータが全くユーザに返されないことになる。
【００２１】
別の問題は、新たなデータのどのような挿入も、それらテーブルの両方の再生成を必要とすることであった。さらにまた、テーブル２のその構造のため、そのテーブルの生成の前にPAGEDATAフィールドを定義しなければならなかった。あるサーチから返されたこれらフィールドを変化させることは、PAGEDATAテーブル全体の再生成を必要としていた。これに関係する１つの問題は、そのような生成が、任意のサイズのデータベースを取り扱うときに、非常にかなりの量の時間を必要としたことである。サンプルのアプリケーションにおいては、再生成は、６時間以上の計算時間を必要としていた。
【００２２】
この従来技術の技法の別の問題は、ユーザ指定のサーチ・ストリング（これは、選択しそしてユーザに対し強調する）に対する“最も近い”一致が、サーチ結果内において、返されたデータの初めから予測できないオフセット場所にて現れていたことである。使い易さを向上させるには、このデータを、サーチ結果の初めかあるいはサーチ結果のおよそ中間の所のようなもっと予測できる場所に位置付けるのがより望ましい。
【００２３】
本願発明者は、上記の従来技術の方法に対する改良法を見い出したのであって、この改良法により、ユーザは、質問を提出し、そして小グループのデータを、最も近い一致が返された結果内のおよそ中央となったソートされたフォーマットで受けることができる。また、本発明は、ユーザが、１グループの値からこれに隣接のグループへと容易にブラウズすることができるようにする。これら望ましいフィーチャを備えていても尚、データを、どのテーブルの再生成も必要とせずにデータベースに加えることができる。さらに、サーチをすることが非常に効率的であり、したがってサーバがユーザに関する状態情報を記憶することを必要とされない。
【課題を解決するための手段】
【００２４】
本発明にしたがい、ユーザは、サーチ値をサーバまたはサービス・プロバイダに提出する。このサーチ値は、探そうとしているデータに関しユーザが最も良いと思っているものである。ワイルドカードをユーザが入力することは必要でない。
【００２５】
サーバは、在来のフォーマットでデータベースを保持する。このデータベースは、複数のフィールドを各々含む複数のレコードを有する。各レコードの少なくとも１つのフィールドには、キー・フィールドがあり、これは、データベースのそれらレコードをサーチするのに使用する。このデータベースに対し、指定のキー値を使用することにより、標準の質問を実行することができる。
【００２６】
また、サーバは、ページ定義テーブルに複数のページ定義も保持する。各ページ定義は、下側キー値と上側キー値でデータベース・レコードの１つのページを定める。１つの実施形態においては、各ページ定義は、単一の対の下側キー値および上側キー値を示す。サーチ値の受け取りに応答して、サーバは、それらページ定義を調べることにより、そのサーチ値を囲むキー値を有する１つを見つける。次に、これらキー値を使用してデータベースをサーチし、そしてそのページ定義のそれらキー値間に入るキー値を有する全てのレコードを見つける。
【００２７】
従来技術とは対照的に、ページ定義の上側キー値と下側キー値とは、ユーザに返すべきデータベース・レコードの最初と最後のキー値を指定しない。この代わりに、下側キー値は、返すべき最初のデータベース・レコードのキー値を指定する一方、上側キー値は後続のページのレコードの最初のデータベース・レコードのキー値を指定する。
【００２８】
別の実施形態においては、各ページ定義は、２つのキー値、すなわち、サーチ値に対応するページ定義を識別するのに使用する第１の対と、一旦正しいページ定義を見つけた後にデータベースに質問するのに使用する第２の対と、を有する。この実施形態を使用すると、ユーザに返す情報は、ページ定義を識別するのに使用するインデックス法に範囲が一致する必要がなくなる。これにより、クライアントに返す集合をより構成可能にできる。代表的には、第１対は、第２対が定める範囲の部分集合であるキー値範囲を定める。
【図面の簡単な説明】
【００２９】
【図１】本発明による情報検索システムのブロック図である。
【図２】本発明によるクライアントまたはサーバのコンピュータの関連するコンポーネントを示すブロック図である。
【図３】本発明による好ましいステップを示すフローチャートである。
【発明を実施するための形態】
【００３０】
図１は、本発明の１つの実施形態による情報検索コンピュータ・システムを示しており、全体を参照番号１０で指示している。情報検索システム１０は、サーバ１２と、複数のクライアント１４とを含んでいる。これらクライアントとサーバとの間の通信は、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークあるいはインターネットのようなパブリックのネットワークのようなデータ通信ネットワークを介して提供する。
【００３１】
サーバ１２は、ハードディスクまたはハードディスク・アレイのような１つ以上のデータ記憶媒体を有するか、あるいはこれらへのアクセスを有する。サーバは、これらハードディスクの内の１つにデータベース１６を保持している。このデータベースは、従来のフォーマットでフォーマッティングし配列して、複数のデータベース・レコードを有する。各レコードは、可変のデータを包含する複数のフィールドを有する。これらレコードに対し、１つ以上のキー・フィールド内に含まれた値に基づいて、サーチおよびソートの一方または両方を行うことができる。キー・フィールド内の値は、本文ではキー値と呼ぶ。サーバは、このデータベースを操作するためのデータベース管理システム（ＤＢＭＳ）１８を有する。質問は、ＤＢＭＳに対し、ＳＱＬ（標準照会言語）フォーマットであるいはリレーショナル・データベースへのアクセスを可能にするそれと類似の言語で提出することができる。
【００３２】
図２は、全体を参照番号４０で指示した例示のクライアント・コンピュータの関連するハードウェア・コンポーネントを示している。コンピュータ４０は、セットトップ・ボックス、ハンドヘルド・コンピュータまたはポケット・コンピュータ、インターネット端末、デスクトップ・コンピュータ、およびラップトップ・コンピュータもしくはノートブック・コンピュータのような、コンシューマ機器を含む種々の異なったタイプのデバイスの内の任意の１つとすることができる。サーバ・コンピュータは、図２のコンフィギュレーションと同様のコンフィギュレーションとするが、ただし、ファイル・アクセス、アプリケーション・シェアリングおよびデータベース・アクセスのようなサーバ機能に対し最適化する。
【００３３】
コンピュータ４０は、マイクロプロセッサ４１と、電子メモリ４２のようなコンピュータ読み取り可能な記憶媒体とを含む。プロセッサ４０は、インテル社（Intel Corporation of Santa Clara，California）製造のx86シリーズのマイクロプロセッサのような従来の在庫がありすぐに入手可能なマイクロプロセッサである。図２は、たった１つのプロセッサしか示していないが、本システムは、複数のプロセッサを含むこともでき、これらは、複数の異なったプロセスまたはタスクであってその各々が１つ以上の実行スレッドを有するものが使用する。また、コンピュータ・システム４０は、他の代表的なコンピュータ・ハードウェア、例えばインターフェース電子回路を含むＩ／Ｏコンポーネント３８、並びにオーディオおよびビデオのコンポーネントのようなマルチメディア・レンダリング・デバイス３９も含む。
【００３４】
物理メモリ４２は、好ましくは、ランダム・アクセス可能な読み書き電子メモリ(ＲＡＭ)、並びに磁気ハードディスクあるいはその他のデータ記録媒体のような二次記憶装置から構成している。メモリ４２はまた、他のタイプのコンピュータ読み取り可能な記憶媒体（これに実行可能のコンポーネントを分配させ記憶させる）も含むことができ、これは、フロッピー・ディスク、ＣＤ−ＲＯＭ、ＥＰＲＯＭのような不揮発性の電子メモリを含む。データベース１６は、メモリ４２内に、あるいはネットワーク・リソースを介してのみアクセス可能な他のディスク・ベースのメモリ内に格納することができる。
【００３５】
従来のコンピュータ・システムにしたがい、コンピュータ・システム４０は、オペレーティング・システム４３と、このオペレーティング・システムと共に実行する１つ以上のアプリケーション４４とを備える。マイクロソフト社(Microsoft Corporation of Redomond, Washington)から入手可能な
【００３６】
2010044777.tif 000007
【００３７】
オペレーティング・システムは、クライアント・コンピュータにおいて使用するのに適したオぺレーティング・システムの１つの例である。マイクロソフト社の
【００３８】
2010044777.tif 000008
【００３９】
オペレーティング・システムは、サーバ・コンピュータに適したオペレーティング・システムの１つの例である。
【００４０】
複数のアプリケーション・プログラムは、代表的には、メモリ４２から実行する。クライアントにおいては、アクティブのアプリケーション・プログラムは、マイクロソフト社のInternet ExplorerTMのようなインターネット・ブラウザを含む。サーバにおいては、アクティブのアプリケーションは、SQL*Server，OracleおよびInternet Information Server（インターネット情報サーバ）のようなデータベース管理システムを含む。
【００４１】
再び図１を参照すると、本発明は、サーバが保持するデータベース１６内のデータを見つけ出す方法を包含している。一般には、クライアント１４の１つは、サーチ値をサーバ１２に提出する。このサーチ値は、データベース・レコードのキー・フィールドの内の１つに含まれた情報タイプのものである。サーバは、このサーチ値の提出に応答して、提出されたサーチ値に最も近く一致するであろうデータベース・レコードの限られた１つの集合を識別し、そしてそれからのデータを返す。このような１つのデータベース・レコード集合は、１ページのデータベース・レコードと呼び、このレコード・ページから返されたデータは、データ・ページと呼ぶ。
【００４２】
１つのサーチ値に応答してたった１つのレコード・ページを識別するため、サーバは、複数のページ定義を保持しそしてこれを参照する。各ページ定義は、少なくとも１対のキー値を示す。ある特定のサーチ値が与えられたときには、サーバは、ページ定義の内のそのサーチ値に対応する１つのものを識別するステップを実行する。次に、サーバは、データベースをサーチすることにより、識別したページ定義が示すキー値により限定（bound）されたキー値を有する１つのページすなわち１つのデータベース・レコード集合を見つける。これらレコードからのデータは、次に、１つのデータ・ページとしてクライアントに返す。これらレコードは、オプションとして、ユーザに返す前にソートする。例えば、ネームは、ユーザに返す前に、アルファベット順にソートすることもできる。
【００４３】
ページ定義は、好ましくは、サーバによりアクセス可能でありかつＤＢＭＳがサービスする記憶媒体にサーチ可能なテーブルで格納し、そしてこれは、本文ではページ定義テーブルと呼ぶ。このようなテーブルは、図１に参照番号２０で指示している。ページ定義テーブルは、複数の個別のエントリあるいは行を有する。各エントリは、１対のキー値、すなわち、下側（LOWER）キー値および上側(UPPER)キー値を含む。本発明のこの実施形態においては、これらキー値は、インデックス・キー値およびバウンド・キー値の両方として使用する。これらタイプのキー値間の差は、本発明の第２実施形態に関する以下の説明から明かとなる。
【００４４】
テーブル３は、上記説明において使用した例示のデータベースに対応するページ定義テーブルの１例を示している。
【００４５】
【表５】
2010044777.tif 000009
【００４６】
このページ定義テーブルの各エントリは、このエントリの下側と上側のキー値により限定したキー値を有する１つのデータベース・レコード集合に対応している。より具体的には、ページ定義テーブルのある１つの特定のエントリに対応する単一のデータベース・レコード集合は、（ａ）このエントリの下側キー値に等しいかあるいはこれより大きく、しかも（ｂ）このエントリの上側キー値より小さい、キー値を有する全てのレコードから成っている。
【００４７】
上の例示のテーブル３において、第１のエントリは、“ａ”の下側キー値を有するが、それは、“ａ”が、このシステムにおける辞書学的に最初の可能なキー値であるからである（この値は、データのタイプに依存して異なる）。これは、“Beaver”の上側キー値を有する。したがって、このエントリに対応する１つのデータベース・レコード集合は、アルファベット順のリスト内のBeaverより前の全てのネームを含む。第２のエントリに対応する１つのデータベース・レコード集合は、“Beaver”と“Bowman”との間の範囲内の全てのネームを含む(“Bowman”は、データベース内の“Bratsanos”に先行するネームである)。一般的には、第１エントリに対する下側キー値は、任意の可能なサーチ値に等しいかあるいはこれより小さい値である。このテーブルの最後のエントリに対する上側キー値は、任意の可能なサーチ値に等しいかあるいはこれより大きい値である(再び、この値は、データベース内に含まれるデータのタイプに依存して異なる)。
【００４８】
ページ定義テーブルは、情報の所望のサイズおよび分割に基づいて定義する。
【００４９】
アルファベット順の情報では、これは、アルファベットの各文字に対する単一のページを有することが望ましいことがあり、これは、ページ定義テーブルに対する必要を取り除くことになる。しかし、より粗いあるいはより微細の分割を有することにより、適当な量のデータあるいはおよそ等しい量のデータが各ページ・テーブル・エントリに対応するようにすることが望ましい場合がある。これは、大きなデータ集合に対しては特に当てはまる。単一のページ定義テーブルの良い例は、辞書または住所録のタブ（A-B XYZ等）である。
【００５０】
尚、このテーブルは、テーブル１内の上に示したテーブルとは異なっていることに注意されたい。例えばテーブル３は、ＩＤ番号を指定しない。単に下側キー値と上側キー値とを指定する。加えて、各行の上側キー値は、次の行の下側キー値と同じである。これは、ある種のサーチ値がテーブル・エントリとテーブル・エントリとの間に入るのを防ぐ、すなわち、任意の可能なしかも許可されたサーチ値が、それらエントリの内の１つのキー値内に入ることになる。
【００５１】
クライアントがデータに対する要求の１部分としてサーチ値を提出したとき、サーバは、ページ定義テーブルをサーチすることにより、そのサーチ値に対応する１つの行あるいはエントリを識別する。詳細には、サーバは、そのサーチ値を囲む下側キー値と上側キー値とを有するエントリを見つける。さらに詳細には、サーバは、（ａ）そのサーチ値が当該エントリの下側キー値に等しいかあるいはそれより大きいこと、かつ（ｂ）そのサーチ値が当該エントリの上側キー値よりも厳密に小さいこと、が当てはまる単一のエントリを見つける。
【００５２】
一旦、１つのエントリを見つけると、そのキー値をバウンド値として使用することにより、その対応するデータベース・レコード集合を識別する。詳細には、サーバは、データベースのサーチまたは質問を実行して、その識別したテーブル・エントリのキー値により限定したキー値を有するデータベース・レコード集合を識別する。この集合は、（ａ）当該エントリの下側キー値に等しいかあるいはこれより大きく、かつ（ｂ）当該エントリの上側キー値よりも小さい、キー値を有する全てのレコードから成っている。これらレコードからのデータは、クライアントのデータ要求への応答として返す。
【００５３】
ページ定義テーブルはキー値をリストするが、データベースは、ほとんどの場合、キー・フィールド以外の複数のフィールドを有することになる。クライアントに返す値は、必ずしも、その識別したデータベース・レコード集合からのキー値である必要はない。むしろ、一旦適当なデータベース・レコード集合を識別したならば、任意のグループのフィールド値を、データベース・レコード集合から返すことができる。しかし、ほとんどの場合、各レコードに対し返すそのグループのフィールド値は、キー・フィールドからの値を含むことになる。
【００５４】
所望のデータを返すことに加え、サーバは、そのデータベース・レコード集合を識別するのに使用した下側キー値および上側キー値を返す。この状態情報は、次に、クライアントが記憶し、そしてクライアントが使用する最初に見つけた集合に隣接する追加の集合またはページのデータベース・レコードを見つけるための後続の質問または要求を定式化するのにクライアントが使用する。これは、クライアントが保持する状態情報に基づいてデータベース情報の諸ページ間をブラウズできるようにし、この状態情報を保持するためにサーバ・リソースを消費することはない。加えて、ある範囲内に入る多くのレコードがある場合(例えば、ベートーベン（Beethoven）から始まる作品は、音楽データベースでは１０００のエントリを含み、したがって１００の集合が返される)、この技術により、本システムは、良好に機能し、しかも依然としてユーザがそのデータをブラウズできるようにする。
【００５５】
尚、好ましくはサーチ値の何等かの事前処理があることに注意されたい。例えば、全ての値は、小文字に変換し、しかも先行するスベースは除去する。“The”または“A”のようなキー・ワードもまた除去する。ここで、オリジナルのデータは、ある種のフィールドに対する“キー”値を有することがあることに注意されたい。例えば、オリジナル・データが“The Beatles”であるとした場合、これは、サーチのために使用する追加の列“beatles,the”も含むことができる。
【００５６】
この例においては、そのサーチ・キー・データは、返さないが、オリジナルの“実際”のデータを返すことになる。ページ定義テーブル内の値は、これと同じ方法で処理する。
【００５７】
図３は、本発明による好ましいステップを示す。ステップ１００は、サーバからクライアントへのサーチ値の提出から成っている。このサーチ値は、サーバが保持するデータベース内の１つのキー・フィールドに対応している。このサーチ値の提出に応答して、サーバは、複数のページ定義を参照することによりその供給されたサーチ値に対応するページ定義の内の１つを識別するステップ１０２を実行する。既に説明したように、各ページ定義は、１対のキー値を示し、これにおいて、各対は、上側キー値と下側キー値とを含んでいる。ページ定義は、好ましくは１つのテーブル内にエントリとして格納する。これが当てはまるときには、ステップ１０２は、供給されたサーチ値を囲む１対のキー値を有するテーブル・エントリをサーチすることから成っており、ここで、そのサーチ値は、下側キー値と上側キー値とにより定まる下側キー値を含む範囲内に入る。
【００５８】
ステップ１０４は、データベースをサーチすることにより、ステップ１０２で識別したページ定義のキー値により限定されたキー値を有する１つのデータベース・レコード集合を見つけることから成る。詳細には、このステップは、その識別したページ定義の下側キー値と上側キー値との間（下側キー値を含む）のキー値を有する全てのレコードを返すように定式化する。
【００５９】
ステップ１０６は、識別したデータベース・レコード集合からのデータをクライアントに返すことから成る。このステップは、ステップ１０２で識別したページ定義からのキー値を返すことを含んでいる。クライアントは、この返されたキー値に基づいて新たなサーチ値を得ることができる。このような新たなサーチ値は、データベース・レコードの異なったページ中をブラウズするために、サーバに対し提出する。
本技法は、上述の従来技術の技法に対する大きな改善となるものである。その最も顕著な利点は、レコードをテーブルに追加するときに、テーブルの再生成を全く必要としないことである。レコードをデータベースに追加することは、事実上、異なった数のレコードを有するレコード・ページをもたらすことがあるが、これは、重要な関心事ではない。大きなデータベースでは、相対的なサイズは、およそ等しいままであり、小さな統計学上の変動を受けるに過ぎない。あるポイントでは、全てのレコード・ページをおよそ等しいサイズにセットするため、ページ定義テーブルを再生成あるいは再計算することが望ましくなることがある。
【００６０】
しかし、これは、比較的小さなタスクであり、従来技術において必要とされていたページ・データ・テーブルを再生成するタスクに比較すれば特にである。加えて、ページ定義テーブルの定義または再生成のときに、データベース・レコードのランダムのサンプリングを使用することにより、等しいサイズのレコード集合を定義することができる。これは、さらに、再生成に必要な時間を減少させる。
【００６１】
もっと重要なことは、ページ・データ・テーブルが必要でないことである。データベース自体への参照は、下側と上側のバウンド（bound）をページ定義テーブルから識別した後に、この技術を使って行う。ここで、サーチは、多数のページ定義テーブルを保持することにより、異なったデータベース・フィールドに基づかせることができる。これは、従来技術では多数のページ・データ・テーブルを必要とするものであった、， この技法を使用するサーチは、素早くかつ効率的であって、ページ定義テーブル内の簡単なインデックス付きルックアップと、データベース内の後続のインデックス付き質問のみを必要とするだけである。サーチ値として“fle”を使用する例示の質問は、ＳＱＬフォーマットでは以下のように現れる。
【００６２】
select LOWER,UPPER from page_definition_table where LOWER<=FLE'and UPPER>FLE' select name,address from database_table where key value>=FANG'and key_value<FRANCEOUR'
ここで、key_valueは各レコードに対するキー値を含むデータベース・フィールドを指し、database_tableは、この既存のデータベース内の１つの適当なテーブルを指す。“境界”条件に関する適当なチェックは、行を全く返さない質問をチェックすることにより行う。
【００６３】
ここで、２つの先行する質問文の内の後者は、データベース・レコードに含まれる任意のデータを、どのようなテーブルの再生成も必要とせずに、返すことができることに注意されたい。その返すフィールドを予め定義することは、従来技術におけるのと同じように必要はない。この場合、その質問は、選択したページのデータベース・レコード内における各レコードに対しフルネームと住所とを返すように定式化する。
【００６４】
これら質問は、サーバにより定式化しそして提出するか、あるいはさもなければ、これらは、クライアントから直接定式化しそして提出することができる。好ましい実施形態においては、質問は、サーバが実行し、そしてデータをＨＴＭＬフォーマットで返す。
【００６５】
本発明の別の重要な特徴は、サーバではなくクライアントが保持する状態情報を使用して、１つのデータ・ページからこれに隣接のデータ・ページへブラウズすることができるようにするである。この理由は、データベースの質問を定式化するのに使用するキー値をクライアントに与えるからである。例えば、上記例では、“Fang”“Francoer”が返されたことになる。前の集合またはページのデータへとブラウズするには、クライアントは、これら値の内の１つに基づいて新たなサーチを提出することになる。例えば、前のページのデータベース・レコードに対する新たな上側キー値と下側キー値とは、以下の形態の質問を実行することにより見つける。
【００６６】
select LOWER,UPPER from page_definition_table where UPPER=previous_lower 
後続の１つのデータベース・レコードに対する上側キー値および下側キー値は、以下の通りに見つける。
【００６７】
select LOWER,UPPER from page_definition_table where LOWER-previous_upper 
本発明が対処する別の問題は、返されたデータについてのユーザに対し都合の良い提示に関するものである。クライアントがある特定のレコードをサーチしているとき、このレコードは、一般に、返されかつソートされたデータ内にランダムに配置される。それは、その返されたレコードの初めに、あるいはその返されたレコードの終わりに、もしくはその中間にあることがある。しかし、所望ならば、ページ定義テーブルは、より小さなエントリに分割することにより、各データ・ページが比較的小さなものとなるようにすることができる。このとき、複数のデータ・ページをクライアントに返すことができ、そのデータ・ページが、返されたページ内に任意の配置されたサーチ値に対応する。この方法を使用すると、サーチ値に最も近い一致を、返されたデータの初め付近、真ん中付近、あるいは終わり付近に一貫して配置することができるが、ただし、代表的には、初め付近にそのデータを表示することが望ましいであろう。例えば、一旦ターゲットのデータ・ページを決定したなら、このデータ・ページおよびこれに続くデータ・ページを返すことができる。さらにユーザの便宜のため、ユーザ指定のキー値に最も近い一致を強調することも望ましい。
【００６８】
以上に説明した技法に対する強化法として、ページ定義が、２対のキー値、すなわち、１対のインデックス・キー値と、１対のバウンド・キー値とを含むように構成することができる。インデックス・キー値は、サーチ値に対応するページ定義を見つけるのに使用し、そしてバウンド・キー値は、クライアントに返すべきデータベース・レコードのバウンドを定めるのに使用する。このようにして、返されるレコードの範囲は、こうしなければ上述の技法を使って返されることになる範囲を超えて拡張することができる。この代替技法は、初め、真ん中、終わりの付近のような、返されるデータ内の任意の場所付近に、最も近く一致するレコードを配置するために使用することもできる。
【００６９】
以下のテーブル５は、本発明のこの代替の実施形態によるページ定義テーブルを示している。
【００７０】
【表６】
2010044777.tif 000010
【００７１】
ページ定義テーブルの各エントリは、１対のインデックス・キー値と１対のバウンド・キー値との両方を含んでいる。インデックス・キー値は、あるサーチ値にどのテーブル・エントリが対応するかを識別するときに使用する。詳細には、下側のインデックス・キー値がサーチ値に等しいかそれ未満でありかつその上側インデックス・キー値がそのサーチ値よりも大きいエントリは、このサーチ値に対応するエントリである。
【００７２】
これらインデックス・キー値は、テーブル３内に示したのと全く同じように構成する。すなわち、それら対が順番になったシーケンスを形成し、これにおいて、ある特定の対の上側キー値は、後続の対の下側キー値と同じである。これは、サーチ値がインデックス・キー値の各対間に入るのを防止する。
【００７３】
バウンド・キー値は、１つのレコード集合を求めてデータベースに質問するときに使用する。一旦、テーブル・エントリを識別したなら、そのデータベースに対し、その識別したテーブル・エントリのバウンド・エントリ間に入るキー値を有する全てのレコードを求めて質問する。
【００７４】
この技法を使用するとき、ある特定のテーブル・エントリのバウンド値は、好ましくは同じエントリのインデックス・エントリに渡る。例えば、テーブル４の第３エントリについて考えてみる。そのインデックス・キーは、“Bratsanos”と“Cheng”とである。これら値（“Bratsanos”を含む）間のサーチ値は、その結果として、このテーブル・エントリが選択されることになる。しかし、返されるデータは、“Borgman”と“Conway”との間のキー値を有する全てのデータベース・レコードに対応することになる。したがって、バウンド範囲は、どの特定のエントリに対するインデックス範囲よりも大きい。ある種の場合には、ある特定のエントリに対するバウンド・キーは、このエントリに対するインデックス・キー値と同じとすることもできる。この特別な場合は、テーブル３の前の例により実際に実施しており、これにおいては、インデックス・キー値とバウンド・キー値とは、互いに等しく、一方の対の値のみをページ定義テーブル内にリストすることしか必要でない。
【００７５】
この方法を使用すると、サーチ値に最も近く一致するデータは、そのサーチ結果の１つの部分に向かって偏らせることができる。例えば、下側バウンド・キー値が下側インデックス・キー値に等しく、かつ上側バウンド・キー値が上側インデックス・キー値よりもはるかに大きい場合、最も近い一致は、返されるデータの初めに向かって偏らせることになる。
【００７６】
データを返すとき、バウンド・キーおよびインデックス・キーのいずれか、あるいはその両方をクライアントに返す。これにより、クライアントは、上述のように、別の異なったデータベース・レコード集合にブラウズするため、それら値に基づいて、新たなサーチ規準をサーバに提出することができる。好ましくは、返されたインデックス・キー値は、新たなサーチ質問を定式化するのに使用する。
【００７７】
この強化法は、クライアントが指定したキー値に対し相対的に、クライアントに返されるデータ集合を制御するのに有用である。この他にも利点がある。先ず、サーバは、クライアントに返されたデータ内におけるサーチしたワードの位置を制御することができる。もし、キー値（またはその最も近い一致）が返される最初のレコードとなるように希望する場合、それより前のレコードは、単に、返すサーチ結果から省くことができる。言い換えれば、それら前のレコードは、第２の質問の結果から、これをクライアントに返す前に“切り捨てる”ことができる。これを行うためには、“前の”レコードを選択することが、切り捨てたそれらレコードを返さなければならない。こうすることにより、前の１つのレコード集合に対する第１の要求が、おそらくその前レコードを返すことにならず、むしろオリジナルの切り捨てられていない最初の集合を返すことになる。これは、クライアントが記憶しそしてサーバに送り戻す単一の状態フラグで実現することができる。第２に、ブラウズすることは、データ集合をオーバーラップさせることにより強化することができ、これにより次または前の集合をビューする間においてあるコンテキストが存在するようにする。
【００７８】
法令に従い、本発明について多少なりとも具体的な用語でその構造および方法上の特徴について以上に説明した。しかし、理解されるべきであるが、本発明は、記述したこの特定の特徴に限定されるものではないが、それは、本文に開示した手段は、本発明を実施に移す好ましい形態を構成するものであるからである。
【００７９】
したがって、本発明について、均等論に従い適切に解釈される添付の請求の範囲の適正な範囲内に入るその形態および変更のいずれにおいても、その保護を請求するものである。
【図１】
2010044777.tif 000011
【図２】
2010044777.tif 000012
【図３】
2010044777.tif 000013