(57)【特許請求の範囲】
【請求項１】
コンピュータに、
格納部に格納された複数のレコードに含まれる第１のレコード群のうち、第１の検索条件を満たすレコードを抽出する第１の検索処理を実行させ、
前記第１の検索処理の実行中に第２の検索条件を受け付けた場合に、前記格納部に格納された前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードのうち、前記第１の検索条件を満たすレコード及び前記第２の検索条件を満たすレコードを抽出する第２の検索処理を実行させる、
ことを特徴とする検索制御プログラム。
【請求項２】
前記コンピュータに、更に、
前記第２の検索条件を受け付ける前に受け付けた前記第２のレコード群に含まれるレコードを更新対象とする更新要求に応じて、更新対象のレコードの更新前のレコードと更新後のレコードを前記格納部に格納し、
前記第２の検索処理を行なう際に、さらに、前記更新前のレコードが前記第１の検索条件を満たす場合に前記更新前のレコードを抽出し、前記更新後のレコードが前記第２の検索条件を満たす場合に、前記更新後のレコードを抽出する、
ことを実行させることを特徴とする請求項１に記載の検索制御プログラム。
【請求項３】
前記コンピュータに、さらに、
前記更新前のレコード及び前記更新後のレコードを前記格納部に格納する場合に、前記更新前のレコード及び前記更新後のレコードのそれぞれを識別する版情報を、それぞれのレコードに付加し、
前記更新前のレコード及び前記更新後のレコードを抽出する場合に、それぞれのレコードに付加された版情報に応じて抽出するか否かを判断する、
ことを実行させることを特徴とする請求項２に記載の検索制御プログラム。
【請求項４】
コンピュータに、
格納部に格納された複数のレコードを複数のレコード群に分割し、
検索対象のレコード群についての複数の検索要求を受け付け、
分割された前記複数のレコード群のそれぞれについて、受け付けた前記複数の検索要求に基づく一括検索処理を実行し、
前記複数のレコード群のうちの第１のレコード群について前記一括検索処理を実行中に、前記複数のレコード群のうちの第２のレコード群に含まれるレコードについての更新要求を受け付けた場合に、前記第１のレコード群についての前記一括検索処理の終了後であって、前記第２のレコード群についての一括検索処理の開始前に、前記更新要求に応じた更新処理を実行する、
ことを実行させることを特徴とする検索制御プログラム。
【請求項５】
前記コンピュータに、更に、
受け付けた検索要求に基づく検索処理を、前記複数のレコード群のそれぞれについて少なくとも１回実行させる
ことを特徴とする請求項４に記載の検索制御プログラム。
【請求項６】
前記コンピュータに、更に、
前記第１のレコード群について前記一括検索処理を実行中に、前記第２のレコード群に含まれるレコードについての削除要求を受け付けた場合に、第１のレコード群についての前記一括検索処理の終了後までに受け付けた検索要求に応じた一括検索処理を、前記複数のレコード群に少なくとも１回実行した後に、前記削除要求に応じた削除処理を実行させる
ことを特徴とする請求項４に記載の検索制御プログラム。
【請求項７】
格納部に格納された複数のレコードに含まれる第１のレコード群のうち、第１の検索条件を満たすレコードを抽出する第１の検索処理を実行し、
前記第１の検索処理の実行中に第２の検索条件を受け付けた場合に、前記格納部に格納された前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードのうち、前記第１の検索条件を満たすレコード及び前記第２の検索条件を満たすレコードを抽出する第２の検索処理を実行する、
ことを特徴とする検索制御方法。
【請求項８】
前記第２の検索条件を受け付ける前に受け付けた前記第２のレコード群に含まれるレコードを更新対象とする更新要求に応じて、更新対象のレコードの更新前のレコードと更新後のレコードを前記格納部に格納し、
前記第２の検索処理を行なう際に、さらに、前記更新前のレコードが前記第１の検索条件を満たす場合に前記更新前のレコードを抽出し、前記更新後のレコードが前記第２の検索条件を満たす場合に、前記更新後のレコードを抽出する、
ことを特徴とする請求項７に記載の検索制御方法。
【請求項９】
複数のレコードを格納する格納部と、
検索要求を受け付ける要求受付け部と、
前記要求受付け部が第１の検索要求を受け付けた場合に、前記格納部に格納された複数のレコードに含まれる第１のレコード群のうち、第１の検索条件を満たすレコードを抽出する第１の検索処理を実行し、前記第１の検索要求の実行中に前記要求受付け部が第２の検索要求を受け付けた場合に、前記格納部に格納された前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードのうち、前記第１の検索条件を満たすレコード及び前記第２の検索条件を満たすレコードを抽出する第２の検索処理を実行する検索制御部とを含む、
ことを特徴とする検索システム。
【請求項１０】
前記検索制御部が、
前記第２の検索条件を受け付ける前に受け付けた前記第２のレコード群に含まれるレコードを更新対象とする更新要求に応じて、更新対象のレコードの更新前のレコードと更新後のレコードを前記格納部に格納し、
前記第２の検索処理を行なう際に、さらに、前記更新前のレコードが前記第１の検索条件を満たす場合に前記更新前のレコードを抽出し、前記更新後のレコードが前記第２の検索条件を満たす場合に、前記更新後のレコードを抽出する、
ことを特徴とする請求項９に記載の検索システム。
【請求項１１】
コンピュータに、
格納部に格納された複数のレコードに対する検索条件を受け付け、
前記複数のレコードに含まれる第１のレコード群のうち前記検索条件を満たすレコードを抽出する第１の検索処理を実行している間に、前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードに対する更新要求を受け付けると、前記第１の検索処理の終了後に、該更新要求に対応して前記第２のレコード群に含まれるレコードを更新し、
更新された前記第２のレコード群のうち前記検索条件を満たすレコードを抽出する第２の検索処理を実行する、
ことを実行させることを特徴とする検索制御プログラム。
【請求項１２】
コンピュータが、
格納部に格納された複数のレコードに対する検索条件を受け付け、
前記複数のレコードに含まれる第１のレコード群のうち前記検索条件を満たすレコードを抽出する第１の検索処理を実行している間に、前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードに対する更新要求を受け付けると、前記第１の検索処理の終了後に、該更新要求に対応して前記第２のレコード群に含まれるレコードを更新し、
更新された前記第２のレコード群のうち前記検索条件を満たすレコードを抽出する第２の検索処理を実行する、
ことを特徴とする検索制御方法。
【請求項１３】
複数のレコードを格納する格納部と、
検索要求を受け付ける受付け部と、
前記格納部に格納された前記複数のレコードに含まれる第１のレコード群のうち前記検索条件を満たすレコードを抽出する第１の検索処理を実行し、該第１の検索処理を実行している間に、前記複数のレコードの前記第１のレコード群とは異なる第２のレコード群に含まれるレコードに対する更新要求を受け付けると、前記第１の検索処理の終了後に、該更新要求に対応して前記第２のレコード群に含まれるレコードを更新して、更新された前記第２のレコード群のうち前記検索条件を満たすレコードを抽出する第２の検索処理を実行する検索制御部と、
を含むことを特徴とする検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索制御プログラム、検索制御方法、検索システムに関する。
【背景技術】
【０００２】
データベースシステムにおいて、複数の検索要求についての検索処理を行なう場合に、データベースから順次データを読み出し、順次読み出されたデータのそれぞれに対して複数の検索要求を用いた検索を実行する検索（一括検索）技術がある。
【０００３】
なお、データベースの排他制御方法において、データの参照のみを行う検索トランザクションとデータの更新を新たな版の生成により実行する更新トランザクションを混在して実行する場合において、版管理表を設けて、多版実行することが提案されている。
【０００４】
また、データベースへの問い合わせに対するフロントエンドの役割をするデータベースサーバと、データベースに対する操作を行う役割をする複数のデータベース操作サーバで構成され、フロントエンドのデータベースサーバと、データベース操作サーバとはネットワークで繋がる。ＳＱＬ文などの複数のデータベース操作文を含んだ、データベースへの問い合わせを、フロントエンドのデータベースサーバで解析して、同じデータベース操作サーバで一回の起動要求で実行できる１つ以上のデータベース操作文を判定してグループ化し、グループ化したデータベース操作文をデータベース操作サーバにまとめて転送し、転送した複数のデータベース操作文を一回の起動要求で起動することが提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−２２２１９４号公報
【特許文献２】特開平０３−１２３９４６号公報
【特許文献３】特開平１０−０４０１４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一括検索処理を実行した場合に、一括検索処理の実行中にデータベースに到着する新たな検索要求は、一括検索処理が終了するまで、その実行を待たされる。この場合、新たな検索要求の待ち時間は、最大で一括検索処理に要する時間に及ぶ。このため、例えば、一括検索処理の実行の開始直後にデータベースに到着する新たな検索要求に応じた処理のレスポンスは、およそ一括検索処理に要する時間の２倍となる。一方、一括検索処理の実行の終了直前にデータベースに到着する新たな検索要求に応じた処理のレスポンスは、およそ一括検索処理に要する時間となる。従って、検索要求に応じた処理のレスポンスは、検索要求が到着するタイミングに依存して、最大で２倍と大きくばらつく。更新要求についても、同様である。
【０００７】
本発明は、検索要求に応じた処理のレスポンスの遅れを抑制することを目的とする。
【課題を解決するための手段】
【０００８】
開示される検索制御プログラムは、コンピュータに、格納部に格納された複数のレコードに含まれる第１のレコード群のうち、第１の検索条件を満たすレコードを抽出する第１の検索処理を実行させ、第１の検索処理の実行中に第２の検索条件を受け付けた場合に、格納部に格納された複数のレコードの第１のレコード群とは異なる第２のレコード群に含まれるレコードのうち、第１の検索条件を満たすレコード及び第２の検索条件を満たすレコードを抽出する第２の検索処理を実行させる。
【発明の効果】
【０００９】
開示される検索制御プログラムによれば、データベースシステムにおいて実行される一括検索処理の制御において、検索要求に応じた処理のレスポンスの遅れを抑制することができる。
【図面の簡単な説明】
【００１０】
【図１】検索システムの一例を示す図である。
【図２】図１の検索システムに設けられる検索装置の一例を示す図である。
【図３】図２の検索装置のハードウェア構成の一例を示す図である。
【図４】データ構造の説明図である。
【図５】データ構造の説明図である。
【図６】検索処理の説明図である。
【図７】要求受付け処理フローを示す。
【図８】実行要求処理フローを示す。
【図９】実行要求処理の説明図である。
【図１０】更新要求処理フローを示す。
【図１１】更新実行処理フローを示す。
【図１２】更新要求処理の説明図である。
【図１３】検索要求処理フローを示す。
【図１４】検索要求処理の説明図である。
【図１５】検索要求処理の説明図である。
【図１６】一括検索実行処理フローを示す。
【図１７】検索要求処理の他の例の説明図である。
【図１８】検索要求処理フローの他の例を示す。
【図１９】検索要求処理フローの他の例を示す。
【図２０】検索要求処理の更に他の例の説明図である。
【図２１】検索要求処理の更に他の例の説明図である。
【図２２】検索要求処理の更に他の例の説明図である。
【図２３】検索要求処理の更に他の例の説明図である。
【図２４】検索要求処理の更に他の例の説明図である。
【図２５】検索要求処理の更に他の例の説明図である。
【発明を実施するための形態】
【００１１】
図１は、検索システムの一例を示す図である。
【００１２】
検索システムは、検索装置１００と、複数のクライアント２００と、検索装置１００と複数のクライアント２００との間を接続するネットワーク３００とを含む。検索装置１００は、例えばデータベースサーバである。
【００１３】
複数のクライアント２００は、各々、アプリケーション２０１を含む。各々のアプリケーション２０１は、実行要求を発行する実行要求部であり、ネットワーク３００を介して、実行要求を検索装置１００へ送信する。実行要求は、例えば、検索要求、更新要求である。検索要求は、データの参照のみを行う要求である。更新要求は、データの更新を新たな版の生成により実行する要求である。
【００１４】
検索装置１００は、検索要求を受信すると、受信した検索要求を実行して、検索要求に対する応答として、検索結果であるデータを、ネットワーク３００を介して、要求元であるクライアント２００へ返信する。要求元であるクライアント２００は、検索結果であるデータを受信する。検索装置１００は、更新要求を受信すると、受信した更新要求を実行して、データを更新する。
【００１５】
図２は、図１の検索システムに設けられる検索装置の一例を示す図である。
【００１６】
検索装置１００は、要求受付部１と、更新制御部２と、検索制御部３と、更新実行部４と、データ格納部５と、一括検索実行部６と、結果返却部７とを含む。要求受付部１は、更新要求キュー１１と、検索要求キュー１２とを含む。検索制御部３は、一括検索のための制御情報、具体的には、検索要求集合格納部に格納された検索要求集合３１と、検索要求／バージョンＩＤ対応情報格納部に格納された検索要求／バージョンＩＤ対応情報３２と、検索要求／区間ＩＤ対応情報格納部に格納された検索要求／区間ＩＤ対応情報３３と、次の一括検索実施区間情報格納部に格納された次の一括検索実施区間情報３４とを含む。データ格納部５は、一括検索のための制御情報、具体的には、格納データ集合格納部に格納された格納データ集合５１と、最新バージョンＩＤ情報格納部に格納されたバージョンＩＤ情報５２と、バージョンＩＤ／データ対応情報格納部に格納されたバージョンＩＤ／データ対応情報５３と、区間ＩＤ／データ対応情報格納部に格納された区間ＩＤ／データ対応情報５４とを含む。
【００１７】
検索要求集合格納部、検索要求／バージョンＩＤ対応情報格納部、検索要求／区間ＩＤ対応情報格納部、次の一括検索実施区間情報格納部は、検索制御部３に設けられる。格納データ集合格納部、最新バージョンＩＤ情報格納部、バージョンＩＤ／データ対応情報格納部、区間ＩＤ／データ対応情報格納部は、データ格納部５に設けられる。
【００１８】
検索要求集合３１、検索要求／バージョンＩＤ対応情報３２、検索要求／区間ＩＤ対応情報３３、次の一括検索実施区間情報３４、格納データ集合５１、バージョンＩＤ情報５２、バージョンＩＤ／データ対応情報５３、区間ＩＤ／データ対応情報５４については後述する。
【００１９】
検索装置１は、データベースであるデータ格納部５に複数のデータ（レコード）を格納するデータベースサーバである。データ格納部５において、実際のデータは、格納データ集合５１に格納される。検索装置１は、クライアント２００から送信された更新要求に従って、更新制御部２の制御の下で、更新実行部４により、データベースであるデータ格納部５に格納されたデータを更新する。検索装置１は、クライアント２００から送信された検索要求に従って、検索制御部３の制御の下で、一括検索実行部６により、データベースであるデータ格納部５に格納されたデータを一括検索する。
【００２０】
要求受付部１は、クライアント２００のアプリケーション２０１から送信された検索要求を受信、換言すれば、受付けて、検索要求を受信した順に検索要求キュー１２に繋ぐ。検索要求は、例えば、要求の種別「検索」と、検索するデータのバージョンと、検索条件とを含む。検索条件は、例えば検索するデータのデータ名（レコードＩＤ）である。
【００２１】
検索制御部３は、検索要求キュー１２を参照して、検索要求キュー１２に存在する１又は複数の検索要求を取り出し、取り出した１又は複数の検索要求を一括検索のための検索要求集合３１に追加する。また、検索制御部３は、一括検索を実行する対象の区間である一括検索実施区間、換言すれば、次の一括検索実施区間を決定する。そして、検索制御部３は、一括検索実行部６を呼び出して、呼び出した一括検索実行部６に検索要求集合３１を渡して、決定した一括検索実施区間についての一括検索を依頼する。
【００２２】
検索要求集合３１は、例えば、複数の検索要求をＯＲ（論理和）結合した１個の検索式（クエリ）であるが、これに限られない。検索要求集合３１は、複数の検索要求から新たに生成した検索式等であっても良い。複数の検索要求から新たに生成した検索式は、例えば、ハイトラフィック技術などの一括検索技術を適用するために生成した検索要求のグループである。
【００２３】
一括検索実行部６は、検索制御部３から一括検索の依頼を受けると、依頼された一括検索実施区間についての一括検索を実行する。換言すれば、一括検索実行部６は、データベースであるデータ格納部５の格納データ集合５１に格納された複数のデータを一括検索する。一括検索実行部６は、一括検索を実行した結果である検索結果を、一括検索の依頼に対する応答として、検索制御部３に返す。
【００２４】
一括検索処理では、検索対象のデータから取り出したデータについて、複数の検索要求をまとめた「検索要求集合」を用いて照合が行なわれるので、検索対象のデータを取り出すのは１回ずつでよい。これにより、データをスキャンする回数を大きく減らすことができ、その結果、複数の検索要求に応じた検索処理の処理速度が向上する。本実施形態では、決定された実施区間のデータに対して一括検索処理を行なう。
【００２５】
検索制御部３は、一括検索実行部６から検索結果を返されると、返された検索結果を結果返却部７へ送る。結果返却部７は、検索要求の要求元であるクライアント２００のアプリケーション２０１へ、検索結果を送信、換言すれば、返却する。検索制御部３は、格納データ集合５１に格納された複数のデータについての検索を終了した検索要求を、検索要求集合３１から削除する。
【００２６】
また、要求受付部１は、クライアント２００のアプリケーション２０１から送信された更新要求を受信して、更新要求を受信した順に更新要求キュー１１に繋ぐ。更新要求は、例えば、要求の種別「更新」と、更新前のデータのバージョンと、更新前のデータと更新後のデータとの差分とを含む。
【００２７】
更新制御部２は、更新要求キュー１１を参照して、更新要求キュー１１に存在する１又は複数の更新要求を取り出す。また、更新制御部２は、データの新たなバージョン、換言すれば、最新バージョンＩＤを決定する。これにより、データの最新のバージョンが決定される。そして、更新制御部２は、更新実行部４を呼び出して、呼び出した更新実行部４に取り出した１又は複数の更新要求及び最新バージョンＩＤを渡して、データの更新を依頼する。
【００２８】
更新実行部４は、更新制御部２からデータの更新の依頼を受けると、依頼されたデータの更新を実行する。換言すれば、更新実行部４は、１又は複数の更新要求に従って、データベースであるデータ格納部５の格納データ集合５１に格納されたデータを更新する。これにより、更新要求の実行の都度、格納データ集合５１において、データの新しいバージョンが生成される。
【００２９】
複数の検索要求の実行の詳細、及び、更新要求の実行の詳細については、後述する。
【００３０】
図３は、図2の検索装置のハードウェア構成の一例を示す図である。
【００３１】
ＣＰＵ１０１は、ＲＯＭ１０２に格納された制御プログラムに従って、検索装置１００を制御する。ＣＰＵ１０１は、例えば主メモリであるＲＡＭ１０３上の検索プログラムを実行する。これにより、要求受付部１、更新制御部２、検索制御部３、更新実行部４、一括検索実行部６、結果返却部７が実現される。検索プログラムは、例えば、ＣＤ−ＲＯＭやＤＶＤ等の記録媒体１０９に格納され、記録媒体１０９からハードディスク１０６に入力され、ハードディスク１０６からＲＡＭ１０３にロードされる。
【００３２】
データ格納部５は、例えばハードディスク１０６に設けられる。換言すれば、データは、例えばハードディスク１０６に格納される。データは、例えば、ＣＤ−ＲＯＭやＤＶＤ等の記録媒体１０９に格納され、記録媒体１０９からハードディスク１０６に入力され、必要に応じてハードディスク１０６からＲＡＭ１０３にロードされ、更新実行部４又は一括検索実行部６により処理される。
【００３３】
入力装置１０４は、例えばキーボードであり、マウス等を含んでも良い。出力装置１０５は、例えばディスプレイであり、プリンタ等の出力装置を含んでも良い。ＣＰＵ１０１、ＲＯＭ１０２、ＲＡＭ１０３、入力装置１０４、出力装置１０５、及び、ハードディスク１０６、ネットワーク接続部１０７は、バス１０８を介して、相互に接続される。
【００３４】
ネットワーク接続部１０７は、例えば、送受信装置であり、ネットワーク３００に接続され、ネットワーク３００を介して他のコンピュータ、例えばクライアント２００に接続される。これにより、検索装置１００は、クライアント２００との間で通信を行う。
【００３５】
なお、データ格納部５が、検索装置１００とネットワークを介して接続された他の情報処理装置に設けられるようにしても良い。この場合、データ格納部５は、他の情報処理装置の例えばハードディスクに設けられる。データは、例えば、ＣＤ−ＲＯＭやＤＶＤ等の記録媒体に格納され、記録媒体から他の情報処理装置のハードディスクに入力され、必要に応じて他の情報処理装置のハードディスクからＲＡＭにロードされ、ネットワーク接続部から検索装置１００のネットワーク接続部１０７へ送信され、検索装置１００の更新実行部４又は一括検索実行部６により処理される。
【００３６】
以下、説明の便宜上、最初に、図４及び図５を参照して、検索装置１００におけるデータ構造について詳細に説明する。
【００３７】
図４は、データ構造説明図である。図４は、特に、格納データ集合５１と、格納データ集合５１を一括検索するための種々の制御情報について示す。
【００３８】
格納データ集合５１は、データベースであるデータ格納部５に格納されたデータそれ自体である。格納データ集合５１は、「レコード＃１」「レコード＃２」等のように、複数のデータを含む。各々のデータは、「レコード＃１」のようなデータ名、例えばレコードＩＤを持ち、レコードＩＤにより表される。レコードＩＤは、データを一意に定める識別情報である。
【００３９】
格納データ集合５１は、「レコード＃２」「レコード＃２’」等のように、あるデータについての複数のバージョンを含む。「レコード＃２’」は、「レコード＃２」が１回更新されたデータ、換言すれば、「レコード＃２」のバージョンＩＤに１を加えたバージョンＩＤを持つデータである。これにより、検索要求毎に異なるバージョンのデータを検索対象とする場合でも、複数回の一括検索処理ではなく、一回の一括検索処理で検索を完了することができる。
【００４０】
バージョンＩＤ情報５２は、格納データ集合５１に格納されたデータにおける、現在の最も新しいバージョンを表す。データのバージョンは、バージョンＩＤにより表される。バージョンＩＤは、データのバージョンを一意に定める識別情報である。従って、バージョンＩＤ情報５２は、格納データ集合５１に格納されたデータの最新のバージョンＩＤである。
【００４１】
バージョンＩＤは、図４において、格納データ集合５１の右側に数字「１」〜「３」で表される。従って、図４に示す例においては、格納データ集合５１には、バージョン「１」〜「３」のデータが格納されている。
【００４２】
バージョンＩＤ／データ対応情報５３は、「バージョンＩＤとデータとの対応」を示す情報であり、更新処理によって生成されるバージョン（版）と、そのバージョンに含まれるデータの対応関係を表す。図４において、例えば「レコード＃１」とバージョンＩＤ「１」とが、バージョンＩＤ／データ対応情報５３の一部である「線分」で結ばれている。これにより、例えば「レコード＃１」が更新処理によってバージョンＩＤ「１」として生成されたこと、換言すれば、「レコード＃１」はバージョンＩＤ「１」を持つことが表される。
【００４３】
なお、実際には、バージョンＩＤ／データ対応情報５３は、例えばバージョンＩＤ／データ対応テーブルに格納される。この場合、バージョンＩＤ／データ対応テーブルには、「レコード＃１」等のデータに対応して、当該データのバージョンＩＤが格納される。
【００４４】
区間ＩＤ／データ対応情報５４は、「区間ＩＤとデータとの対応」を示す情報であり、格納データ集合をいくつかに分割したそれぞれを示す区間ＩＤと、その区間に分割されたデータの対応関係を表す。
【００４５】
区間ＩＤは、図４において、格納データ集合５１の左側にアルファベット「Ａ」〜「Ｃ」で表される。従って、図４に示す例においては、格納データ集合５１は、区間「Ａ」〜「Ｃ」に分割されている。区間「Ａ」〜「Ｃ」には、各々、複数のデータ（レコード）が含まれる。従って、図４に示す例の格納データ集合５１は、区間「Ａ」〜「Ｃ」に属する複数のレコード群を含む。
【００４６】
図４において、例えば「レコード＃１」と区間ＩＤ「Ａ」とが、区間ＩＤ／データ対応情報５４の一部である「線分」で結ばれている。これにより、例えば「レコード＃１」が更新処理によって区間「Ａ」に分割されたこと、換言すれば、「レコード＃１」は区間ＩＤ「Ａ」を持つことが表される。
【００４７】
なお、実際には、区間ＩＤ／データ対応情報５４は、例えば区間ＩＤ／データ対応テーブルに格納される。この場合、区間ＩＤ／データ対応テーブルには、「レコード＃１」等のデータに対応して、当該データの区間ＩＤが格納される。
【００４８】
データベースであるデータ格納部５は、更新実行部４から更新要求の実行を依頼されると、更新要求を実行する。これにより、データ格納部５は、更新要求の実行の都度に、格納データ集合５１、バージョンＩＤ情報５２、バージョンＩＤ／データ対応情報５３、区間ＩＤ／データ対応情報５４を作成又は更新し、各々の格納部に格納する。
【００４９】
検索要求集合３１は、受付けられた検索要求であって、かつ、まだ検索処理が終了していない検索要求の集合を表す。検索要求集合３１は、「検索要求＃１」「検索要求＃２」等のように、複数の検索要求を含む。各々の検索要求は、「＃１」のような検索要求ＩＤを持ち、検索要求ＩＤにより表される。検索要求ＩＤは、検索要求を一意に定める識別情報である。
【００５０】
検索要求／バージョンＩＤ対応情報３２は、「検索要求と検索対象データバージョンＩＤの対応」を示す情報であり、検索要求が検索対象とするデータのバージョンを表す。図４において、例えば「検索要求＃１」とバージョンＩＤ「１」とが、検索要求／バージョンＩＤ対応情報３２の一部である「点線」で結ばれている。これにより、例えば「検索要求＃１」がバージョンＩＤ「１」を持つデータを検索対象とすることが表される。
【００５１】
なお、実際には、検索要求／バージョンＩＤ対応情報３２は、例えば検索要求／バージョンＩＤ対応テーブルに格納される。この場合、検索要求／バージョンＩＤ対応テーブルには、「検索要求＃１」等の検索要求に対応して、当該検索要求が検索対象とするデータのバージョンＩＤが格納される。
【００５２】
検索要求／区間ＩＤ対応情報３３は、「検索要求と検索開始区間ＩＤの対応」を示す情報であり、当該検索要求の検索が開始された区間の区間ＩＤを表す。図４において、例えば「検索要求＃１」と区間ＩＤ「Ａ」とが、検索要求／区間ＩＤ対応情報３３の一部である「点線」で結ばれている。これにより、例えば「検索要求＃１」が区間ＩＤ「Ａ」から開始されたことが表される。
【００５３】
なお、実際には、検索要求／区間ＩＤ対応情報３３は、例えば検索要求／区間ＩＤ対応テーブルに格納される。この場合、検索要求／区間ＩＤ対応テーブルには、「検索要求＃１」等の検索要求に対応して、当該検索要求が開始された区間ＩＤが格納される。
【００５４】
次の一括検索実施区間情報３４は、「次の一括検索実施区間ＩＤ」を示す情報であり、一括検索実行部６が、次に検索対象とする区間を表す。詳しくは後述するように、一括検索実行部６は、格納データ集合５１を複数の区間に分割し、分割した複数の区間を予め定められた所定の順番で巡回しながら一括検索を行う。従って、次の一括検索実施区間情報３４は、一括検索実行部６により次に一括検索される区間の区間ＩＤである。
【００５５】
検索制御部３は、検索要求キュー１２から検索要求を取り出すと、一括検索を実行するために、検索要求の取出しの都度に、検索要求集合３１、検索要求／バージョンＩＤ対応情報３２、検索要求／区間ＩＤ対応情報３３、次の一括検索実施区間情報３４を作成又は更新し、各々の格納部に格納する。
【００５６】
図５は、データ構造説明図である。図５は、特に、格納データ集合５１におけるデータ（レコード）の追加、更新、削除について示す。
【００５７】
格納データ集合５１において、バージョンＩＤが「１」であるデータは、「レコード＃１」〜「レコード＃４」である。従って、更新実行部４は、最初に、「レコード＃１」〜「レコード＃４」を格納データ集合５１に格納する。この格納処理において、更新実行部４は、区間「Ａ」に「レコード＃１」及び「レコード＃２」を割当て、区間「Ｂ」に「レコード＃３」及び「レコード＃４」を割当てる。これにより、各区間に属するレコードＩＤの数を等しくすることができる。
【００５８】
次に、更新実行部４は、更新要求に従ってデータの一部を更新することにより、バージョンＩＤが「２」であるデータを生成する。図５の例においては、「レコード＃３」が更新（置換）されることにより「レコード＃３’」とされ、「レコード＃５」が追加される。「レコード＃３」の更新要求は置換要求であり、「レコード＃５」の更新要求は追加要求である。
【００５９】
「レコード＃３’」は、区間「Ｂ」に属する「レコード＃３」を更新したデータであるので、区間「Ｂ」に属するようにされる。また、「レコード＃３’」は、現在における最新のバージョンＩＤが「１」であるので、バージョンＩＤ「２」を持つ。なお、最新のバージョンＩＤが「２」にインクリメントされる。一方、「レコード＃５」は、新たに追加されたデータであるので、新たな区間「Ｃ」に属するようにされる。また、「レコード＃５」は、バージョンＩＤ「２」を持つ。
【００６０】
次に、更新実行部４は、新たな更新要求に従ってデータの一部を更新することにより、バージョンＩＤが「３」であるデータを生成する。図５の例においては、「レコード＃２」が更新（置換）されることにより「レコード＃２’」とされ、「レコード＃６」が追加され、「レコード＃４」が削除される。「レコード＃２」の更新要求は置換要求であり、「レコード＃６」の更新要求は追加要求であり、「レコード＃４」の更新要求は削除要求である。
【００６１】
「レコード＃２’」は、区間「Ａ」に属する「レコード＃２」を更新したデータであるので、区間「Ａ」に属するようにされる。また、「レコード＃２’」は、現在における最新のバージョンＩＤが「２」であるので、バージョンＩＤ「３」を持つ。なお、最新のバージョンＩＤが「３」にインクリメントされる。一方、「レコード＃６」は、新たに追加されたデータであるので、区間「Ｃ」に属するようにされる。また、「レコード＃６」は、バージョンＩＤ「３」を持つ。
【００６２】
次に、図６を参照して、検索装置１００における一括検索について説明する。
【００６３】
図６は、検索処理の説明図である。なお、図６において、例えば検索要求＃１を「ｑ１」と表わすこととする。
【００６４】
一括検索実行部６は、複数の区間Ａ〜Ｃに分割された格納データ集合５１を、予め定められた所定の順番で巡回しながら、サイクリックに、一括検索を行う。換言すれば、一括検索実行部６は、区間Ａ、区間Ｂ、区間Ｃの順で一括検索を実行し、これを繰り返す。例えば、ポイントＡ１で区間Ａの一括検索を開始して、ポイントＢ１で区間Ａの一括検索を終了する。ポイントＢ１で区間Ｂの一括検索を開始して、ポイントＣ１で区間Ｂの一括検索を終了する。ポイントＣ１で区間Ｃの一括検索を開始して、ポイントＡ２で区間Ｃの一括検索を終了する。そして、ポイントＡ２以後も、同様に、以上の順番で一括検索を繰り返す。ポイントＡ１からポイントＢ１までが区間Ａであり、ポイントＢ１からポイントＣ１までが区間Ｂであり、ポイントＣ１からポイントＡ２までが区間Ｃである。
【００６５】
検索制御部３は、新たな検索要求が到着すると、到着した検索要求を検索要求集合３１に追加する。例えば、ポイントＡ１以前に「ｑ１」が検索要求キュー１２に到着しているので、「ｑ１」が検索要求集合３１とされる。これにより、一括検索実行部６は、検索要求集合「ｑ１」により、区間Ａについて、一括検索を実行する。検索要求集合「ｑ１」は、１個の検索要求しか含まないが、検索要求集合である。また、区間Ａの一括検索中に、「ｑ２」が検索要求キュー１２に到着するので、新たに「ｑ２」が検索要求集合３１に追加される。従って、一括検索実行部６は、検索要求集合「ｑ１，ｑ２」により、区間Ｂについて、一括検索を実行する。
【００６６】
ある検索要求についての一括検索が終了した場合、換言すれば、格納データ集合５１の複数の区間Ａ〜Ｃの全てについてある検索要求を含む一括検索が終了した場合、検索制御部３は、当該検索要求を検索要求集合３１から削除する。例えば、「ｑ１」の検索はポイントＡ１から開始されるので、ポイントＡ２において、複数の区間Ａ〜Ｃの全てについて検索が終了する。そこで、検索制御部３は、ポイントＡ２において、「ｑ１」を検索要求集合３１から削除する。また、「ｑ２」の検索はポイントＢ１から開始されるので、検索制御部３は、ポイントＢ２において、「ｑ２」を検索要求集合３１から削除する。
【００６７】
従って、検索要求が検索要求キュー１２に到着するタイミングに依存して、異なるポイント及び異なる区間から一括検索が開始される。これにより、一括検索の途中で、新たに検索要求キュー１２に到着した検索要求を検索要求集合３１に加えることができる。
【００６８】
一方、一括検索が複数の区間Ａ〜Ｃについて連続して繰り返し実行されると、一括検索の途中で、新たに更新要求キュー１１に到着した更新要求を実行することができない。そこで、検索処理が途切れるまで更新処理を待たせると共に、検索処理が途切れるポイントが設けられる。具体的には、ポイントＡ１、Ｂ１、Ｃ１等において、換言すれば、格納データ集合５１の複数の区間Ａ〜Ｃの各々についての一括検索が終了する都度に、更新要求キュー１１に到着している１又は複数の更新要求が実行される。
【００６９】
従って、ポイントを通過する都度、ポイントの各々において、終了した一括検索の後処理、更新要求の処理、開始される一括検索の前処理が実行される。終了した一括検索の後処理は、例えば、一括検索の結果が一括検索実行部６から検索制御部３へ返される処理、全ての区間について検索を終了した検索要求を削除する処理である。更新要求の処理は、例えば、更新実行部４が更新要求を実行する処理である。開始される一括検索の前処理は、例えば、新たな検索要求に基づいて検索要求集合３１、検索要求／バージョンＩＤ対応情報３２、検索要求／区間ＩＤ対応情報３３、次の一括検索実施区間情報３４等を生成し、一括検索を一括検索実行部６に依頼する処理である。
【００７０】
以上により、一括検索を実行しつつ更新要求を実行することができる。これにより、一括検索において、1個のバージョンのデータだけを検索するのではなく、検索要求集合３１に含まれる複数の検索要求が検索対象とする複数のバージョンのデータの和集合を検索することができる。これにより、検索するデータからいずれかのバージョンが漏れることを防止することができる。
【００７１】
なお、検索要求集合３１に含まれるある検索要求からみると、当該検索要求自体の検索対象でないバージョンに対する検索結果が含まれることになる。そこで、後述するように、検索結果から、他の検索要求の検索対象であるバージョンを除く。これにより、検索結果に不要な結果が含まれないようにすることができる。
【００７２】
以上の図２〜図６から判るように、複数の検索要求を含む一括検索及び更新要求は、以下のように実行される。
【００７３】
データベースであるデータ格納部５は、図４及び図５に示すように、データの追加、更新、削除の都度に、格納データ集合５１、バージョンＩＤ情報５２、バージョンＩＤ／データ対応情報５３、区間ＩＤ／データ対応情報５４を、データの追加、更新、削除を反映した内容に更新する。
【００７４】
具体的には、データ格納部５は、更新実行部４からの更新要求に従って、格納データ集合５１のデータ（レコード）を追加、更新、削除する。この時、データ格納部５は、図４及び図５に示すように、格納データ集合５１におけるレコードＩＤが定まる。これにより、データ格納部５は、格納データ集合格納部に格納された格納データ集合５１に含まれる複数のデータ、換言すれば、複数のレコードを、複数の区間「Ａ」〜「Ｃ」、換言すれば、複数のレコード群に分割する。
【００７５】
データ格納部５は、格納データ集合５１のデータの追加又は更新の都度に、最新バージョンＩＤを生成して、最新バージョンＩＤ情報に格納する。バージョンＩＤ情報５２は、現在のバージョンＩＤ情報５２を＋１だけインクリメントすることにより生成される。
【００７６】
データ格納部５は、格納データ集合５１のデータの追加又は更新の都度に、バージョンＩＤ／データ対応情報５３を生成して、バージョンＩＤ／データ対応情報格納部に追加する。バージョンＩＤ／データ対応情報５３は、追加又は更新されたデータ（レコード）に、当該追加又は更新に応じて生成された最新バージョンＩＤを対応付けることにより生成される。
【００７７】
データ格納部５は、格納データ集合５１のデータの追加又は更新の都度に、追加又は更新されたデータ（レコード）が検索を開始する区間ＩＤとの対応を示す区間ＩＤ／データ対応情報５４を生成して、区間ＩＤ／データ対応情報格納部に追加する。区間ＩＤ／データ対応情報５４は、追加又は更新されたデータに、当該追加又は更新されたデータが属する区間ＩＤを対応付けることにより生成される。追加又は更新されたデータが属する区間ＩＤは、前述したように、データの追加又は更新の際に定まる。
【００７８】
一方、検索制御部３は、図６に示すように、格納データ集合５１の複数の区間、換言すれば、複数のレコード群について、一括検索を、予め定められた順序で繰り返し実行させる。一括検索は、検索要求集合３１、換言すれば、複数の検索要求を満たすか否かの検索を一括して実行する検索処理である。ここで、複数の検索要求は、検索対象の区間の直前の区間について、換言すれば、検索対象のレコード群の直前のレコード群についての検索の実行中に受付けた検索要求を含む。
【００７９】
検索制御部３は、図４及び図６に示すように、検索要求キュー１２からの検索要求の取出しの都度に、換言すれば、図６に示すポイントの各々において、検索要求集合３１、検索要求／バージョンＩＤ対応情報３２、検索要求／区間ＩＤ対応情報３３、次の一括検索実施区間情報３４を、取出した検索要求を反映した内容に更新する。
【００８０】
ここで、検索要求キュー１２からの検索要求の取出しは、前述したように、１個の区間についての一括検索が終了したポイントにおいて実行される。従って、以下に説明する、検索要求集合３１、検索要求／バージョンＩＤ対応情報３２、検索要求／区間ＩＤ対応情報３３、次の一括検索実施区間情報３４の更新も、１個の区間についての一括検索が終了したポイントにおいて実行される。
【００８１】
具体的には、検索制御部３は、検索要求キュー１２から取出した１又は複数の検索要求を、検索要求集合３１に追加する。換言すれば、検索制御部３は、現在の検索要求集合３１に含まれる１又は複数の検索要求に、検索要求キュー１２から取出した１又は複数の検索要求を追加した、新たな検索要求集合３１を生成する。
【００８２】
この時、複数の検索要求の各々が検索対象とするデータのバージョンは、互いに異なっていても良い。換言すれば、異なるバージョンのデータについても一括検索を実行することができる。これにより、複数の検索要求の間における分離レベルを向上することができる。
【００８３】
検索制御部３は、検索要求集合３１への検索要求の追加の都度に、検索要求／バージョンＩＤ対応情報３２を生成して、検索要求／バージョンＩＤ対応情報格納部に追加する。検索要求／バージョンＩＤ対応情報３２は、検索要求集合３１における検索要求に、当該検索要求が検索対象とするデータのバージョンＩＤを対応付けることにより生成される。検索要求が検索対象とするデータのバージョンＩＤは、例えば、当該検索要求において定められる。
【００８４】
なお、後述するように、検索制御部３が、検索要求が検索対象とするデータのバージョンＩＤを決定するようにしても良い。
【００８５】
検索制御部３は、検索要求集合３１への検索要求の追加の都度に、検索要求／区間ＩＤ対応情報３３を生成して、検索要求／区間ＩＤ対応情報格納部に追加する。検索要求／区間ＩＤ対応情報３３は、検索要求集合３１における検索要求に、当該検索要求が検索を開始する区間ＩＤを対応付けることにより生成される。検索要求が検索を開始する区間ＩＤとしては、以下に説明するように、新たに生成された次の一括検索実施区間情報３４が用いられる。
【００８６】
検索制御部３は、検索要求集合３１への検索要求の追加の都度に、次の一括検索実施区間情報３４を生成して、次の一括検索実施区間情報格納部に格納する。次の一括検索実施区間情報３４は、現在の次の一括検索実施区間情報３４が示す区間ＩＤの次の区間ＩＤを求めることにより生成される。
【００８７】
この後、検索制御部３は、一括検索実行部６を呼び出して、呼び出した一括検索実行部６に一括検索を依頼する。
【００８８】
一括検索実行部６は、検索要求集合３１に含まれる複数の検索要求が検索対象とする１又は複数のバージョンのデータの和集合を求める。そして、一括検索実行部６は、求めたデータの和集合を、検索要求集合３１を用いて一括検索する。一括検索実行部６は、一括検索による検索結果から、検索対象でないバージョンを除く。
【００８９】
図６に示す１個の検索要求「ｑ１」についての検索は、格納データ集合５１に格納された複数のレコードの一部分である１個の区間から、換言すれば、第１のレコード群からレコードを順次読み出し、読み出したレコードが検索要求「ｑ１」を満たすか否かを判定し、判定の結果に応じて検索要求「ｑ１」を満たす１又は複数のレコードを取得する処理である。
【００９０】
ここで、例えば、第１の検索要求「ｑ１」を受け付けた場合に、格納データ集合５１の第１のレコード群について、第１の検索要求「ｑ１」を満たすレコードを取得する、第１の検索が実行される。また、例えば、第１の検索要求「ｑ１」の実行中に第２の検索要求「ｑ２」を受け付けた場合に、第１のレコード群とは異なる第２のレコード群について、第１の検索要求「ｑ１」を満たすレコード及び第２の検索要求「ｑ２」を満たすレコードを取得する、第２の検索が実行される。
【００９１】
従って、例えば、図６に示す第１の検索要求「ｑ１」及び第２の検索要求「ｑ２」を含む検索要求集合３１による一括検索は、格納データ集合５１に格納された複数のレコードの一部分である１個の区間からレコードを順次読み出し、読み出したレコードが第１の検索要求「ｑ１」又は第２の検索要求「ｑ２」を満たすか否かを判定し、判定の結果に応じて第１の検索要求「ｑ１」を満たすレコード及び第２検索要求「ｑ２」を満たすレコードを取得する処理である。例えば、第１の区間について第１の検索要求「ｑ１」の実行中に第２の検索要求「ｑ２」を受け付けた場合、第１の区間とは異なり第１の区間に続く第２の区間について、第１の検索要求「ｑ１」及び第２の検索要求「ｑ２」を含む検索要求集合３１による一括検索が実行される。これにより、検索要求を実行するまでの待ち時間を削減することができ、また、検索要求に対するレスポンスのばらつきを小さくすることができる。
【００９２】
この後、検索制御部３は、格納データ集合５１の全ての区間、換言すれば、複数のレコード群の全てについて例えば検索要求「ｑ１」が実行された後に、図６に示すポイントＡ２において、検索要求「ｑ１」を、検索要求集合３１に含まれる複数の検索要求から除く。検索要求「ｑ１」についての検索処理は、一括検索のための検索要求集合３１に含まれるので、検索要求集合３１についての検索処理に含まれる。検索要求集合３１についての検索処理の実行に応じて、検索制御部３は、検索要求／バージョンＩＤ対応情報３２と、検索要求／区間ＩＤ対応情報３３と、の検索要求「ｑ１」に関する情報を更新する。
【００９３】
一方、複数の区間のいずれかの区間について、換言すれば、複数のレコード群のいずれかのレコード群について一括検索を実行中に、格納データ集合５１の複数のレコードのいずれかについての更新要求が受け付けられる場合がある。この場合、更新制御部２は、当該区間について実行中の一括検索が終了した後であって、実行中の一括検索の対象である区間の次の区間が開始される前に、更新要求を実行させる。換言すれば、更新制御部２は、実行中の一括検索の対象であるレコード群の次に一括検索の対象となるレコード群についての一括検索が開始される前に、図６に示すポイントの各々において、更新要求を実行させる。これにより、更新要求を実行するまでの待ち時間を削減することができ、また、更新要求に対するレスポンスのばらつきを小さくすることができる。
【００９４】
ここで、例えば、図６に示す第１の検索要求「ｑ１」を受け付けてから第２の検索要求「ｑ２」を受け付けるまでの間に、前述の第２のレコード群に含まれるレコードについての更新要求を受け付ける場合がある。この場合、更新実行部４は、更新要求に応じて更新を行なう。これに応じて、データ格納部５は、更新前のレコード及び更新後のレコードのそれぞれと、それぞれを識別するバージョンＩＤ（版情報）とを関連付けて記憶する。また、データ格納部５は、第１の検索要求「ｑ１」と更新前のレコードのバージョンＩＤとを対応付け、第２の検索要求「ｑ２」と更新後のレコードのバージョンＩＤとを対応付けて記憶する。
【００９５】
この後、一括検索実行部６は、第１の検索要求「ｑ１」及び第２の検索要求「ｑ２」を含む検索要求集合３１による一括検索を実行して、第１の検索要求「ｑ１」を満たすレコード及び第２検索要求「ｑ２」を満たすレコードを取得する。更に、検索制御部３は、取得したレコードのうち、更新前のレコード及び更新後のレコードのいずれかであるレコードについて、第１の検索要求「ｑ１」を満たすレコードであるか否かの判定を行い、第２の検索要求「ｑ２」を満たすレコードであるか否かの判定を行う。
【００９６】
また、複数の区間のいずれかの区間について、換言すれば、複数のレコード群のいずれかのレコード群について一括検索を実行中に、格納データ集合５１の複数のレコードのいずれかについての削除要求が受け付けられる場合がある。この場合、更新制御部２は、当該区間について実行中の一括検索が終了した後において、更に、全ての区間、換言すれば、複数のレコード群の全てについて、予め定められた順序に従って、少なくとも１回の一括検索が実行された後に、削除要求を実行させる。
【００９７】
次に、処理フローを参照して、検索処理及び更新処理について説明する。
【００９８】
図７は、要求受付処理フローを示す。
【００９９】
要求受付部１は、クライアント２００のアプリケーション２０１からの要求（実行要求）を受信するまで待つ（Ｓ１１）。要求受付部１は、要求を受信すると、受信した要求が検索要求であるか更新要求であるかを判定する（Ｓ１２）。受信した要求が検索要求である場合、要求受付部１は、受信した検索要求を検索要求キュー１２に追加し（Ｓ１３）、Ｓ１１を繰り返す。受信した要求が更新要求である場合、要求受付部１は、受信した更新要求を更新要求キュー１１に追加し（Ｓ１４）、Ｓ１１を繰り返す。換言すれば、要求受付部１は、受信した要求を検索要求と更新要求とに分類して、各々のキューに追加する。
【０１００】
なお、受信した要求を検索要求と更新要求とに分類することなく、１個のキューに到着順に追加するようにしても良い。
【０１０１】
図８は、実行要求処理フローを示す。
【０１０２】
更新制御部２は、要求受付部１の更新要求キュー１１をチェックして（Ｓ２１）、新たな更新要求が更新要求キュー１１に存在するか否かを判定する（Ｓ２２）。新たな更新要求が更新要求キュー１１に存在する場合（Ｓ２２  Ｙｅｓ）、更新実行部４は、更新要求キュー１１から新たな更新要求を取り出して、取り出した新たな更新要求に基づいて新しいデータの版を作成して、データベースであるデータ格納部５に格納された旧版のデータの更新処理を実行する（Ｓ２３）。新たな更新要求が更新要求キュー１１に存在しない場合（Ｓ２２  Ｎｏ）、更新実行部４は、Ｓ２３の実行を省略する。
【０１０３】
この後、検索制御部３は、要求受付部１の検索要求キュー１２をチェックして（Ｓ２４）、新たな検索要求が検索要求キュー１２に存在するか否かを判定する（Ｓ２５）。新たな検索要求が検索要求キュー１２に存在する場合（Ｓ２５  Ｙｅｓ）、検索制御部３は、更新要求キュー１１から新たな検索要求を取り出して、取り出した新たな検索要求を検索要求集合に加える（Ｓ２６）。新たな検索要求が検索要求キュー１２に存在しない場合（Ｓ２５  Ｎｏ）、検索制御部３は、Ｓ２６の実行を省略する。
【０１０４】
この後、一括検索実行部６は、現在の検索対象である区間を検索要求集合を用いて一括検索することにより、検索要求集合による検索結果（一括検索結果）であるデータの和集合を求め、求めたデータの和集合から不要な検索結果を除く（Ｓ２７）。
【０１０５】
この後、検索制御部３は、検索対象区間を現在の区間の次の区間に設定し（Ｓ２８）、一括検索結果から検索対象でないバージョンのデータを除いた残りを、検索の結果として、結果返却部７に送る（Ｓ２９）。結果返却部７は、受取った検索の結果を、要求元であるクライアント２００のアプリケーション２０１に返信する。この後、検索制御部３は、全区間の検索を終了した検索要求を、検索要求集合から除き（Ｓ２１０）、Ｓ２１を繰り返す。
【０１０６】
なお、Ｓ２１〜Ｓ２１０の処理は、いずれの処理を先に実行するようにしても良い。
【０１０７】
図８の実行要求処理フローにおいて、図９に示すように、一括検索実行部６は、区間Ａ、区間Ｂ、区間Ｃの順に、サイクリックに一括検索を実行する。次の一括検索実施区間情報３４は、区間Ａの一括検索時にはＢとされ、区間Ｂの一括検索時にはＣとされ、区間Ｃの一括検索時にはＡとされる。従って、次の一括検索実施区間情報３４は、一括検索の実行に１区間分だけ先行して、所定の順で、サイクリックに変化する。
【０１０８】
また、バージョンＩＤ情報５２は、更新処理を実行する都度に追加される。また、バージョンＩＤ／データ対応情報５３も、更新処理を実行する都度に追加される。
【０１０９】
また、検索要求集合３１は、検索要求キュー１２から検索要求が取出される都度に増加し、検索要求が全ての区間の検索を終了する都度に減少する。
【０１１０】
図１０は、更新要求処理フローを示す。
【０１１１】
更新制御部２は、要求受付部１の更新要求キュー１１をチェックして（Ｓ３１）、新たな更新要求が更新要求キュー１１に存在するか、又は、更新要求キュー１１が空であるかを判定する（Ｓ３２）。なお、Ｓ３１及びＳ３２は、図８のＳ２１及びＳ２２と同一であり、図１０と図８との関係を明確に示すために、再度、図１０に示される。一方、以下のＳ３３〜Ｓ３８は、図８のＳ２３に相当する。
【０１１２】
新たな更新要求が更新要求キュー１１に存在する場合、更新実行部４は、更新要求キュー１１に存在する全ての更新要求を取り出して（Ｓ３３）、現在のデータバージョンＩＤに基づいて、新しいデータバージョンＩＤを取得する（Ｓ３４）。例えば、更新実行部４は、バージョンＩＤ情報５２、換言すれば、現在のデータバージョンＩＤを参照し、参照したデータバージョンＩＤを＋１だけインクリメントすることにより、新しいデータバージョンＩＤを取得する。次に、更新実行部４は、現在のバージョンに対する「バージョンＩＤとデータの対応」に基づいて、新しいバージョンに対する「バージョンＩＤとデータの対応」を作成する（Ｓ３５）。例えば、更新実行部４は、バージョンＩＤ／データ対応情報５３、換言すれば、現在のバージョンに対する「バージョンＩＤとデータの対応」をコピーする。そして、更新実行部４は、コピーした「バージョンＩＤとデータの対応」における「バージョンＩＤ」を新しいバージョンＩＤに置換する。これにより、新しいバージョンに対する「バージョンＩＤとデータの対応」が作成される。
【０１１３】
この後、更新実行部４は、格納データ集合５１について更新処理を実行した後（Ｓ３６）、ループが終了したか、又は、ループがその途中であるかを判定する（Ｓ３７）。ループがその途中である場合、更新実行部４は、Ｓ３６を繰り返す。ループが終了した場合、更新実行部４は、バージョンＩＤ情報５２、換言すれば、「最新データバージョンＩＤ」を、Ｓ３４において取得した新しいデータバージョンＩＤに更新する（Ｓ３８）。また、Ｓ３８において、更新実行部４は、バージョンＩＤ／データ対応情報５３、換言すれば、「バージョンＩＤとデータの対応」に、Ｓ３５において作成した新しいバージョンに対する「バージョンＩＤとデータの対応」を追加する。
【０１１４】
Ｓ３２において、更新要求キュー１１が空である場合、以下のＳ３３〜Ｓ３８は、省略される。換言すれば、更新実行部４は、処理を実行しない。
【０１１５】
なお、図１０の例においては、更新要求キュー１１から取り出した全ての更新要求について1個のバージョンを生成しているが、更新要求キュー１１から取り出した複数の更新要求の各々について、異なるバージョンを生成するようにしても良い。
【０１１６】
図１１は、更新実行処理フローを示す。
【０１１７】
更新実行部４は、更新要求の種別をチェックし（Ｓ４１）、更新要求が追加要求、更新（置換）要求、削除要求のいずれであるかを判定する（Ｓ４２）。
【０１１８】
更新要求が追加要求である場合、更新実行部４は、追加要求に従って、新しいデータ、換言すれば、追加データを作成して、作成した追加データを格納データ集合５１、換言すれば、「データ集合」に追加する（Ｓ４３）。次に、更新実行部４は、新しいバージョンに対する「バージョンＩＤとデータ」に、追加データについてのバージョンＩＤ及びデータを加える（Ｓ４４）。次に、更新実行部４は、追加データの区間ＩＤを決定し、当該決定に基づいて、「区間ＩＤとデータの対応」に、追加データについての区間ＩＤ及びデータを加える（Ｓ４５）。
【０１１９】
更新要求が更新要求である場合、更新実行部４は、更新要求に従って、データの新しいバージョン、換言すれば、置換後のデータを作成して、作成した置換後のデータを格納データ集合５１、換言すれば、「データ集合」に追加する（Ｓ４６）。次に、更新実行部４は、新しいバージョンに対する「バージョンＩＤとデータ」に、置換後のデータについてのバージョンＩＤ及びデータを加える（Ｓ４７）。次に、更新実行部４は、「区間ＩＤとデータの対応」に、置換後のデータについての区間ＩＤ及びデータを加える（Ｓ４８）。更に、更新実行部４は、新しいバージョンに対する「バージョンＩＤとデータ」から、置換前のデータを除く（Ｓ４９）。
【０１２０】
更新要求が削除要求である場合、更新実行部４は、削除要求に従って、新しいバージョンに対する「バージョンＩＤとデータ」から、削除データを除く（Ｓ４１０）。
【０１２１】
なお、図１１の例においては、更新要求が追加要求である場合には、追加されるデータの持つ属性に従って、追加される区間が決定される。例えば、図５を参照して前述したように、「レコード＃３’」は区間Ｂに属する「レコード＃３」を更新したデータであるので区間Ｂに属するようにされ、「レコード＃５」は新たに追加されるデータであるので新たな区間Ｃに属するようにされる。しかし、例えば、追加されるデータの順に追加先の区間を、区間Ａ、区間Ｂ、区間Ｃのように、順番に変更するようにしても良い。この場合、１個の区間に属するデータの数を予め定めるようにしても良い。
【０１２２】
図１１の更新実行処理フローにおいては、図１２に示すように、バージョンＩＤとデータ（レコード）との対応関係は、新しいバージョンＩＤ（例では３）の1つ前のバージョンＩＤとデータと（例では２）の対応関係に基づいて生成される。
【０１２３】
例えば、図１２に示すように、現在のバージョンＩＤ「２」には、バージョンＩＤ／データ対応情報５３により、レコード＃１、＃２、＃３’、＃４、＃５が対応付けられている。これは、図５に示すバージョンＩＤ「２」の状態である。新しいバージョンＩＤは「３」である。新しいバージョンＩＤ「３」とデータ（レコード）との対応関係は、バージョンＩＤ「２」とデータとの対応関係に基づいて生成される。新しいバージョンＩＤ「３」の状態が、図５に示す状態であるとする。
【０１２４】
この場合、最初に、新しいバージョンＩＤ「３」には、バージョンＩＤ「２」とデータとの対応関係をコピーすることにより、レコード＃１、＃２、＃３’、＃４、＃５が対応付けられる。次に、レコード＃２の更新要求によってレコード＃２がレコード＃２’に置換されるので、レコード＃２との対応が削除され、レコード＃２’との対応が追加される。更に、レコード＃４の削除要求によってレコード＃４との対応が削除され、レコード＃６の追加要求によってレコード＃６との対応が追加される。
【０１２５】
図１３は、検索要求処理フローを示す。
【０１２６】
検索制御部３は、要求受付部１の検索要求キュー１２をチェックして（Ｓ５１）、新たな検索要求が検索要求キュー１２に存在するか、又は、検索要求キュー１２が空であるかを判定する（Ｓ５２）。なお、Ｓ５１及びＳ５２は、図８のＳ２４及びＳ２５と同一であり、図１３と図８との関係を明確に示すために、再度、図１３に示される。一方、以下のＳ５３〜Ｓ５１２は、図８のＳ２６〜Ｓ２１０に相当する。
【０１２７】
新たな検索要求が検索要求キュー１２に存在する場合、検索要求の実行の開始処理が実行される。具体的には、検索制御部３は、検索要求キュー１２に存在する全ての検索要求を取り出して（Ｓ５３）、取り出した検索要求を、検索要求集合３１、換言すれば、検索要求出力へ加える（Ｓ５４）。また、検索制御部３は、取り出した検索要求の検索対象バージョンを、検索要求／バージョンＩＤ対応情報３２、換言すれば、「検索要求と検索対象データバージョンＩＤの対応」に追加し（Ｓ５５）、また、取り出した検索要求に対する「検索要求と検索開始区間ＩＤの対応」を、「次の一括検索実施区間ＩＤ」にする（Ｓ５６）。
【０１２８】
Ｓ５２において、検索要求キュー１２が空である場合、検索制御部３は、Ｓ５３〜Ｓ５６を省略する。
【０１２９】
この後、一括検索実行部６は、「次の一括検索実施区間ＩＤ」の指す区間に対して一括検索処理を実施する（Ｓ５７）。これにより、検索要求キュー１２に新たな検索要求があるか否かに拘らず、１個の区間について一括検索が実行される。
【０１３０】
この後、検索制御部３は、「次の一括検索実施区間」を次の区間に変更する（Ｓ５８）。更に、検索制御部３は、「検索要求と検索開始区間ＩＤの対応」を参照し、検索開始区間が「次の一括検索実施区間」に一致するものがあるかチェックし（Ｓ５９）、検索開始区間が「次の一括検索実施区間」に一致するものがあるか否かを判定する（Ｓ５１０）。検索開始区間が「次の一括検索実施区間」に一致するものがない場合、検索制御部３は、Ｓ５１を繰り返す。
【０１３１】
検索開始区間が「次の一括検索実施区間」に一致するものがある場合、検索要求の実行の終了処理が行われる。このように、検索制御部３の処理は、検索要求の実行の開始処理、一括検索処理、検索要求の実行の終了処理を含む。具体的には、検索制御部３は、一致する検索要求に対する検索結果を、結果返却部７へ送る（Ｓ５１１）。更に、検索制御部３は、一致する検索要求を検索要求集合３１から除き（Ｓ５１２）、Ｓ５１を繰り返す。ここで、検索制御部３は、Ｓ５１２において、一致する検索要求とバージョンＩＤとの対応を示す情報を検索要求／バージョンＩＤ対応情報３２から除き、一致する検索要求と区間ＩＤとの対応を示す情報を検索要求／区間ＩＤ対応情報３３から除く。
【０１３２】
なお、Ｓ５１１においては、検索結果をまとめて結果返却部７へ送るが、これに代えて、１個の区間についての一括検索を終了する都度に、１個の区間における検索結果を結果返却部７に送るようにしてもよい。
【０１３３】
図１３の検索要求処理フローにおいては、図１４に示すように、例えば、次の一括検索実施区間情報３４により示される「次の一括検索実施区間」が区間Ｂである時点で、最新バージョンＩＤ情報により示される最新のデータのバージョンＩＤは「２」である。換言すれば、バージョンＩＤ「３」のデータである、レコード＃２’及びレコード６は存在しない。また、「次の一括検索実施区間」が区間Ｂである時点で、バージョンＩＤ「３」のデータにおいて、レコード＃４は削除されていない。
【０１３４】
一方、「次の一括検索実施区間」が区間Ｂである時点で、換言すれば、区間Ａの一括検索の実行中の時点で、検索要求＃２及び検索要求＃３が、検索要求キュー２１に到着する。そこで、検索要求＃２及び検索要求＃３は、区間Ａの一括検索の終了後、区間Ｂの一括検索から検索要求集合３１に追加される。
【０１３５】
また、区間Ａの一括検索の実行中の時点で、レコード＃２’の更新要求、レコード＃６の追加要求、レコード＃４の削除要求が更新要求キュー１１に到着する。そこで、図１５に示すように、区間Ａの一括検索の終了後、区間Ｂの一括検索の開始前に、バージョンＩＤ「３」のデータが作成される。これにより、レコード＃２’が更新され、レコード＃６が追加され、レコード＃４が削除される。
【０１３６】
この後、図１５に示すように、「次の一括検索実施区間」が区間Ｃに変更されると共に、区間Ｂの一括検索が開始される。この後、「次の一括検索実施区間」が、図１５に示すように、区間Ａ、区間Ｂ、区間Ｃの順で変更され、更に、これが繰り返される。これにより、例えば区間Ａから検索が開始される検索要求＃１が一巡して、再度「次の一括検索実施区間」が区間Ａになると、検索要求＃１は、全ての区間Ａ〜区間Ｃについて検索されたことになる。そこで、検索結果が結果返却部７に送られ、検索要求＃１が検索要求集合３１から除かれる。
【０１３７】
図１６は、一括検索実行処理フローを示す。
【０１３８】
一括検索実行部６は、検索要求集合３１に含まれる複数の検索要求をグループ化する、換言すれば、一括検索のための検索式を生成する（Ｓ６１）。次に、一括検索実行部６は、「検索要求と検索対象データバージョンＩＤの対応」を参照し、検索要求集合３１に含まれる複数の検索要求の全てについて、検索対象とするデータのバージョンＩＤの和集合を取得する（Ｓ６２）。次に、一括検索実行部６は、「バージョンＩＤとデータ集合の対応」を参照し、Ｓ６２において取得した全てのバージョンＩＤに対するデータの和集合を取得する（Ｓ６３）。次に、一括検索実行部６は、「次の一括検索実施区間」に対する「区間ＩＤとデータ集合の対応」を参照し、次の一括検索実施区間に対するデータを取得する（Ｓ６４）。
【０１３９】
この後、一括検索実行部６は、「一括検索対象バージョン集合に対するデータ」と「次の一括検索実施区間に対するデータ」の共通部分（積集合）に含まれるデータを、 一括検索する（Ｓ６５）。
【０１４０】
この後、一括検索実行部６は、一括検索処理の結果を検索要求ごとの結果に振り分ける（Ｓ６６）。次に、一括検索実行部６は、「検索要求と検索対象データバージョンＩＤの対応」と「バージョンＩＤとデータ集合の対応」を参照し、検索要求ごとの検索結果から、 検索対象データ集合に含まれないデータに対する検索結果を除く（Ｓ６７）。次に、一括検索実行部６は、ループが終了したか、又は、ループがその途中であるかを判定する（Ｓ６８）。ループがその途中である場合、一括検索実行部６は、Ｓ６７を繰り返す。ループが終了した場合、一括検索実行部６は、処理を終了する。
【０１４１】
図１６の一括検索実行処理において、図１３と同様に、前処理、一括検索処理、後処理の３個の処理が実行される。前処理は、Ｓ６１〜Ｓ６４であり、検索結果から漏れがないようにするために一括検索処理の入力となる一括検索の対象であるデータ集合を求める処理である。一括検索処理は、Ｓ６５であり、一括検索の対象であるデータ集合について、実際の一括検索を実行する処理である。後処理は、Ｓ６６〜Ｓ６８であり、一括検索の結果から各検索要求にとっての不要な検索結果を除く処理である。
【０１４２】
なお、図１６の例においては、前処理、一括検索処理、後処理が順番に実行されているが、前処理、一括検索処理、後処理を別のプロセス又はスレッドで実行して、並行に実行するようにしても良い。
【０１４３】
ここで、前処理について、図４を参照して説明する。例えば、図４において、区間Ｂについて一括検索を実行するとする。この場合の前処理は、以下のようになる。
【０１４４】
検索要求集合３１に含まれる各々の検索要求が検索対象とするデータのバージョンＩＤの和集合は、｛バージョンＩＤ「１」， バージョンＩＤ「２」｝である（Ｓ６２）。従って、バージョンＩＤ「１」に対応するデータとバージョンＩＤ「２」に対応するデータの和集合は、｛レコード＃１， レコード＃２， レコード＃３， レコード＃３’， レコード＃４， レコード＃５｝である（Ｓ６３）。一方、区間Ｂについての「次の一括検索実施区間に対するデータの和集合」は、｛レコード＃３， レコード＃３’， レコード＃４｝である（Ｓ６４）。従って、以上に述べた２個の和集合の共通部分は｛レコード＃３， レコード＃３’， レコード＃４｝であり、この共通部分について一括検索が実行される。
【０１４５】
次に、後処理について、前処理と同様に、図４を参照して説明する。例えば、図４において、以上の前処理の後に区間Ｂについて一括検索を実行したとする。この場合の後処理は、以下のようになる。
【０１４６】
一括検索の結果において、例えば検索要求＃１にとって、レコード＃３’ は検索要求＃１の検索対象バージョン１に含まれないデータである。そこで、検索要求＃１に対して返却される検索結果から、レコード＃３’が除かれる。検索要求＃２、＃３についても、同様に、各々に返却される検索結果から、各々にとって不要なレコードが除かれる。
【０１４７】
なお、一括検索により得られた検索結果に含まれるデータ（レコード）がある検索要求にとって不要か否かを、以下のように判定するようにしても良い。
【０１４８】
例えば、データ毎の検索結果に、そのデータが含まれるバージョンＩＤの一覧を付加するようにしても良い。例えば、図４のレコード＃１の検索結果に対しては、｛バージョンＩＤ「１」， バージョンＩＤ「２」， バージョンＩＤ「３」｝を、レコード＃２の検索結果に対しては、｛バージョンＩＤ「１」， バージョンＩＤ「２」｝という情報を付加する。なお、バージョンＩＤが番号で表現される場合には、データ毎の検索結果に、「バージョンＩＤ「１」からバージョンＩＤ「３」まで」のように「バージョンＩＤの範囲」を示す情報を付加するようにしても良い。
【０１４９】
また、検索結果に対するバージョンの判定を、検索要求のクエリ（検索式）の一部と見なすようにしても良い。この場合、検索結果が、検索対象であるバージョンに含まれるかどうかを、元の検索要求のクエリに対するＡＮＤ条件（論理積）として追加することができる。例えば、図４の検索要求＃２についてのクエリは「 （検索要求＃２の本来の検索式） ＡＮＤ（バージョンＩＤ「２」） 」のようにクエリに追加する。これにより、一括検索と同時に、不要な検索結果を除去することができる。
【０１５０】
次に、検索要求処理の他の例について説明する。図１７〜図１９は、検索要求処理の他の例の説明図である。
【０１５１】
図１３の検索要求処理においては、検索要求が検索対象とするデータのバージョンはクライアント２００のアプリケーション２０１から送信され、従って、一括検索実行部６は、受信したバージョンを検索対象とする。しかし、検索要求が検索要求キュー１２に到着した時点における最新のデータのバージョンを、当該検索要求の検索対象のバージョンとするようにしても良い。
【０１５２】
この場合、検索要求は常に最新のバージョンを検索するので、古いバージョンにしか含まれないデータは削除することができる。しかし、新しいバージョンのデータが生成され古いバージョンが最新バージョンで無くなった瞬間においては、まだ古いバージョンに対する検索処理が行われている。従って、最新バージョンで無くなった瞬間に、古いバージョンを削除することはできない。換言すれば、削除要求を実行するまで古いバージョンは削除されない。しかし、古いバージョンのデータは、最新バージョンに更新された後に検索を開始した検索処理が全てのデータ、換言すれば、全ての区間について一巡して検索を実行すれば、それ以後、検索対象になることはない。
【０１５３】
そこで、図１７に示すように、検索制御部３は、一括検索のための制御情報として、バージョンＩＤ／区間ＩＤ対応情報３５を保持する。バージョンＩＤ／区間ＩＤ対応情報３５は、検索制御部３のバージョンＩＤ／区間ＩＤ対応情報格納部に格納される。バージョンＩＤ／区間ＩＤ対応情報３５は、「バージョンＩＤと検索終了区間の区間ＩＤとの対応」を示す情報であり、データのバージョン（版）と、そのバージョンのデータが最後に検索される区間ＩＤの対応関係を表す。
【０１５４】
なお、実際には、バージョンＩＤ／区間ＩＤ対応情報３５は、例えばバージョンＩＤ／区間ＩＤ対応テーブルに格納される。この場合、バージョンＩＤ／区間ＩＤ対応テーブルには、「バージョンＩＤ」に対応して、当該バージョンのデータが最後に検索される区間ＩＤが格納される。
【０１５５】
図１７において、例えば、バージョンＩＤ「１」と区間ＩＤ「Ｂ」、及び、バージョンＩＤ「２」と区間ＩＤ「Ｂ」が、バージョンＩＤ／区間ＩＤ対応情報３５の一部である「点線」で結ばれている。これにより、例えばバージョンＩＤ「１」及び「２」のデータが、最終的には、区間「Ｂ」まで検索対象とされることが表される。
【０１５６】
図１８及び図１９は、一体となって、検索要求処理フローの他の例を示す。
【０１５７】
検索制御部３は、図１３のＳ５１〜Ｓ５６と同様に、Ｓ７１〜Ｓ７６を実行する。換言すれば、検索制御部３は、要求受付部１の検索要求キュー１２をチェックして（Ｓ７１）、新たな検索要求が検索要求キュー１２に存在するかを判定する（Ｓ７２）。新たな検索要求が検索要求キュー１２に存在する場合、検索制御部３は、検索要求キュー１２に存在する全ての検索要求を取り出して（Ｓ７３）、取り出した検索要求を検索要求集合３１へ加え（Ｓ７４）、取り出した検索要求の検索対象バージョンを検索要求／バージョンＩＤ対応情報３２に追加し（Ｓ７５）、取り出した検索要求に対する「検索要求と検索開始区間ＩＤの対応」を「次の一括検索実施区間ＩＤ」にする（Ｓ７６）。
【０１５８】
この後、検索制御部３は、各々の検索要求に対し、「検索要求と検索終了区間ＩＤの対応」、換言すれば、検索対象であるデータのバージョンＩＤに対応する検索終了区間ＩＤを、「次の一括検索実施区間ＩＤ」に変更する（Ｓ７７）。
【０１５９】
Ｓ７２において、検索要求キュー１２が空である場合、検索制御部３は、Ｓ７３〜Ｓ７７を省略する。
【０１６０】
この後、一括検索実行部６は、図１３のＳ５７と同様に、「次の一括検索実施中区間ＩＤ」の指す区間に対して一括検索処理を実施する（Ｓ７８）。
【０１６１】
この後、検索制御部３は、図１３のＳ５８〜Ｓ５１２と同様に、Ｓ７９〜Ｓ７１３を実行する。換言すれば、検索制御部３は、「次の一括検索実施区間」を次の区間に変更し（Ｓ７９）、「検索開始区間が「次の一括検索実施区間」に一致するものがあるかチェックし（Ｓ７１０）、判定する（Ｓ７１１）。検索開始区間が「次の一括検索実施区間」に一致するものがない場合、検索制御部３は、Ｓ７１を繰り返す。検索開始区間が「次の一括検索実施区間」に一致するものがある場合、検索制御部３は、一致する検索要求に対する検索結果を、結果返却部７へ送り（Ｓ７１２）、一致する検索要求を検索要求集合３１から除く（Ｓ７１３）。
【０１６２】
この後、検索制御部３は、「バージョンＩＤと検索終了区間ＩＤの対応」を参照し、検索終了区間ＩＤが「次の一括検索実施区間ＩＤ」と等しいバージョンＩＤを求め（Ｓ７１４）、求めたバージョンＩＤが最新バージョンであるか否かを判定する（Ｓ７１５）。
【０１６３】
求めたバージョンＩＤが最新バージョンである場合（Ｓ７１５  Ｙｅｓ）、検索制御部３は、Ｓ７１を繰り返す。これにより、求めたバージョンＩＤが最新バージョンである場合には、当該バージョンＩＤのデータは、検索を終了したバージョンであっても、削除されない。これは、当該バージョンＩＤのデータは、最新バージョンであるので、その後に発行される新たな検索要求の検索対象となるためである。
【０１６４】
求めたバージョンＩＤが最新バージョンでない場合（Ｓ７１５  Ｎｏ）、検索制御部３は、求めたバージョンＩＤについての「バージョンＩＤとデータ集合の対応」を削除する（Ｓ７１６）。更に、検索制御部３は、以上の処理によりどのバージョンＩＤとも対応しなくなったデータのレコードを、格納データ集合５１から削除し（Ｓ７１７）、Ｓ７１を繰り返す。
【０１６５】
以上の処理、特に、Ｓ７７、Ｓ７１４〜Ｓ７１７によれば、検索の開始により、「バージョンＩＤと検索終了区間ＩＤの対応」は、 当該バージョンＩＤについての検索が開始されるたびに上書きされ、かつ、そのときの区間ＩＤが設定される。ここで、「検索を開始するときの区間」は「検索を終了するときの区間」であるので、設定した区間ＩＤは、検索終了のタイミングを示す。また、「バージョンＩＤと検索終了区間ＩＤの対応」は当該バージョンＩＤについての検索の開始の都度に上書きされるので、当該バージョンＩＤについての最も遅い検索が検索を終了する区間ＩＤが設定される。これにより、あるバージョンＩＤを持つデータについて、当該データの検索が終了した時点で、直ちに、当該データを削除することができ、格納データ集合５１を効率よく使用することができる。
【０１６６】
なお、クライアント２００のアプリケーション２０１毎の一連の処理の情報（検索要求の情報）をシステム内に保持し、例えばその一連の処理が開始した時点のバージョンを検索対象とするようにしても良い。この場合も、検索要求は常に最新のバージョンを検索する訳ではないので、あるバージョンが最新バージョンで無くなった瞬間に古いバージョンを削除することはできない。しかし、この場合にも、検索要求が検索要求キュー１２に到着した時点における最新のデータのバージョンを検索対象のバージョンとする場合と同様に、図１７〜図１９を適用することができる。
【０１６７】
次に、検索要求処理の更に他の例について説明する。図２０〜図２５は、検索要求処理の更に他の例の説明図である。
【０１６８】
図１３の実施例では、検索要求キュー１２に新たに到着した検索要求は、そのまま検索要求集合３１に追加される。しかし、検索要求キュー１２に新たに到着した検索要求を検索要求集合３１に追加するかどうかを判定し、予め定められた条件に該当する場合に追加するようにしても良い。
【０１６９】
そこで、追加の判定の条件として、以下に述べる「コストＣ」と「ベネフィットＢ」とを用いる。ここで、検索要求集合３１に新しいバージョンを検索する検索要求を加える場合におけるコストＣは、当該新しいバージョンだけにしか含まれないデータを検索する時間である。例えば、図２１を参照して後述するように、複数のバージョンに対して一括検索処理を行うと、不要なデータを検索することになる。検索要求集合３１に新しいバージョンを検索する検索要求を加える場合におけるベネフィットＢは、追加しようとする検索要求の待ち時間の削減分である。
【０１７０】
ベネフィットＢがコストＣを上回る場合には、新しいバージョンを検索する検索要求を検索要求集合３１に追加する。これにより、検索装置１００の全体として、平均の検索性能が向上することができる。ベネフィットＢがコストＣ以下である場合には、新しいバージョンを検索する検索要求を検索要求集合３１に追加しない。これにより、検索装置１００の全体として、平均の検索性能が低下することを防止することができる。
【０１７１】
以下、検索要求の検索対象を、検索を開始する時点の最新バージョンとして検索を実行する場合における、コストＣとベネフィットＢとを計算する。なお、ここで、更新要求及び検索要求は時間的に均等な間隔で更新要求キュー１１及び検索要求キュー１２に到着するものとし、更新要求によってあるデータが他のデータに置換されるものとし、合計のデータ件数は変わらないものとする。
【０１７２】
例えば、図２０に示すように、データは、区間「Ａ」〜区間「Ｅ」に分割される。検索対象の区間は、「Ａ」から「Ｅ」までこの順に一括検索され、これを繰り返す。１回目の区間「Ａ」の一括検索をＡ［１］と表し、２回目の区間「Ａ」の一括検索をＡ［２］と表し、他の区間についても同様に表すとする。更に、図２０において、区間「Ａ」〜区間「Ｅ」の各々について一括検索を開始する都度に、新たなバージョンの検索要求が加えられる。データのバージョンは、「０」から「９」まで更新される。結果として、図２０は、一括検索の対象であるデータのバージョンの変化を示す。
【０１７３】
具体的には、図２０において、左右に延びる「太線」は、各々、あるバージョンについての検索処理の実施区間を示す。「点線で囲まれた部分」は、各々、ある区間における検索体操であるデータのバージョンの集合を示す。左右に延びる「区間に対応する矢印」は、各々、ある区間の検索中に検索要求キュー１２に到着した検索要求の集合を示す。「区間に対応する矢印」と「太線」とを結ぶ上下に延びる「矢印」は、各々、当該「矢印で表される区間」、換言すれば、検索要求の集合についての検索開始区間及び検索対象であるバージョンを示す。
【０１７４】
例えば、最初のバージョン番号（バージョンＩＤ）「０」に対する一括検索は、区間Ａ［１］から開始される。バージョン番号「０」に対する検索処理は、その後、区間Ｅ［１］の一括検索が終了するまで続く。
【０１７５】
区間Ａ［１］の一括検索が終了すると、区間Ａ［１］の一括検索中に到着した更新要求が実行される。これにより、最新バージョンが「１」に更新される。従って、区間Ａ［１］の一括検索中に到着して区間Ｂ［１］から検索を開始する第２の検索要求集合の検索対象であるバージョンも「１」になる。第２の検索要求集合による検索は、その後、区間Ａ［２］に対する一括検索が終了するまで続く。以上ように、あるバージョンに対する検索要求はオーバラップしながら続いていく。
【０１７６】
ここで、検索要求のオーバラップについて、ある区間に着目すると以下の通りである。例えば、区間Ａ［２］に着目してみると、区間Ａ［２］に対する一括検索において、検索対象となるバージョンの集合は、バージョン番号「１」〜「５」の５個である。同様に、区間Ｂ［２］に着目してみると、区間Ｂ［２］に対する一括検索において、検索対象となるバージョンの集合は、バージョン番号「２」〜「６」の５個である。
【０１７７】
そこで、ある区間において一括検索するデータに着目すると、図２１のようになる。図２１は、例えば区間Ａ［２］に着目して、当該区間Ａ［２］において一括検索されるデータのバージョンを示す。図２１において、Ｕ（１，２）はバージョンが「１」から「２」へ変更された際に更新された部分であり、Ｕ（２，３）はバージョンが「２」から「３」へ変更された際に更新された部分であり、Ｕ（３，４）はバージョンが「３」から「４」へ変更された際に更新された部分であり、Ｕ（４，５）はバージョンが「４」から「５」へ変更された際に更新された部分である。なお、図２１において、図２１における更新を図２３における更新と区別するために、添え字「−１」を付している。
【０１７８】
例えば、Ｕ（１，２）−１がレコード＃２であるとすると、レコード＃２は、バージョンが「１」から「２」へ変更された際に更新された部分「２〜５」と、更新されていない部分「１」とを含む。また、例えば、Ｕ（２，３）−１がレコード＃４であるとすると、レコード＃４は、バージョンが「２」から「３」へ変更された際に更新された部分「３〜５」と、更新されていない部分「１〜２」とを含む。
【０１７９】
図２１において、ある１個の区間についての検索を実行しバージョンが変更される都度に、Δｎ１件のデータが更新される。従って、バージョン番号「１」〜「５」のデータを検索する場合、元のデータに加えて、Δｎ１ ×４件のデータを追加して検索することになる。
【０１８０】
ある１個の区間で変更されるデータ量Δｎ１は、図２１により示されるように、データの全体件数Ｎ（件）、平均検索時間Ｌ（秒）、更新頻度ｒ（件／秒）から求めることができる。最初に、区間の数をＭ個とすると、区間の検索中に更新される件数Δｎ１は、Δｎ１＝Ｌ×ｒ／Ｍで求められる。また、区間の平均検索件数ｎ１は、ｎ１＝Ｎ／Ｍ＋Δｎ１×（Ｍ−１）で求められる。この後、検索速度ｖ（件／秒）が、ｖ＝ｎ１×Ｍ／Ｌで求められる。
【０１８１】
次に、図２０の例において、新たな検索要求を、２回目の区間Ａの検索処理を開始するタイミングであるＡ［２］では追加せずに、次の区間Ｂ［２］で追加する場合について、図２２に示す。
【０１８２】
この場合、バージョン番号「５」のデータは検索されない。従って、２回目の区間Ａ［２］での最新バージョンであるバージョン番号「５」のデータを検索する検索要求が、図２２に示すように、存在しなくなる。このため、区間Ａ［２］及びそれ以降の区間Ｂ［２］、区間Ｃ［２］、区間Ｄ［２］、区間Ｅ［２］の５区間において、検索対象となるバージョンの集合が変化する。一方、バージョン番号「５」のデータは検索されない代わりに、区間Ｂ［２］からバージョン番号「６」のデータが検索される。従って、区間Ｂ［２］から検索を開始する、換言すれば、次のバージョンを検索する検索要求の数は２倍になる。
【０１８３】
検索対象となるバージョンの集合の変化を、図２３に示す。図２３（Ａ）に示すように、影響のある最初の区間Ａ［２］においては、バージョン番号「５」のデータを検索する検索要求が存在しない。このため、バージョン番号「５」だけに含まれるデータを検索しなくてもよい。換言すれば、Ｕ（４，５）−２において、部分「５」は、バージョン番号「５」にしか含まれないので、検索されない。このため、検索データ量がΔｎ１分減少する。
【０１８４】
しかし、次の区間Ｂ［２］においてはバージョン６を検索する検索要求が存在する。このため、図２３（Ｂ）に示すように、バージョン番号「５」だけに含まれるデータが存在しない。換言すれば、Ｕ（４，５）−３において、部分「５〜６」は、バージョン番号「６」のデータの検索において検索される。このため、検索データ量は減少しない。
【０１８５】
バージョン番号「５」のデータを検索しないことによる検索データ量は、バージョン番号「５」が最も新しいバージョンである区間Ａ［２］を検索する場合と、バージョン番号「５」が最も古いバージョンである区間Ｅ［２］を検索する場合について、合わせて２×Δｎ１件の減少となる。
【０１８６】
バージョン番号「５」のデータを検索しない場合において、検索のレスポンスに対する影響を図２４に示す。図２４において、前述したように、検索データ量が減少する区間はＡ［２］及びＥ［２］である。これにより、バージョン番号「１」〜「４」を検索する検索要求の実行の時間と、バージョン番号「６」〜「９」を検索する検索要求の実行の時間とが減少する。以上から、区間Ａ［２］でバージョン番号「５」のデータの検索を行わない場合のレスポンスの総減少量、換言すれば、区間Ａ［２］でバージョン番号「５」のデータの検索を行う場合の検索要求を追加する場合のコストＣが求められる。
【０１８７】
例えば、対象区間の検索時間の減少時間Δｌ（秒）は、Δｌ＝Δｎ１／ｖで求められる。検索要求の到着頻度をｓ（個／秒）とすると、各々の区間で検索を開始する検索要求の数ｑ１（個）は、ｑ１＝ｓ×Ｌ／Ｍで求められる。従って、検索のレスポンスの総減少量Ｃ（個×ｓ）は、Ｃ＝Δｌ×（２×Ｍ−１）×ｑ１で求められる。
【０１８８】
一方、バージョン番号「５」のデータを検索する場合のベネフィットＢは、区間Ｅ［１］に到着したｑ１個の検索要求の検索開始までの待ち時間が１区間分減少することである。
【０１８９】
そこで、コストＣとベネフィットＢとが、図２５に示すように、比較される。具体的には、コストＣは、図２５（Ａ）に示すように求められる。ベネフィットＢは、図２５（Ｂ）に示すように求められる。ここで、コストＣとベネフィットＢとの比較式は、図２５（Ｃ）に示すように、簡単化することができ、ｖ／ｒ＞２Ｍ−１となる。換言すれば、コストＣとベネフィットＢとの比較結果は、更新頻度ｒと検索速度ｖの比と、区間の数Ｍとから求まる定数によって定まることが判る。例えば、更新頻度ｒが多くなると、ｖ／ｒ＞２Ｍ−１が成立しなくなる、換言すれば、コストＣがベネフィットＢよりも小さくなくなる。
【０１９０】
従って、検索制御部３は、更新頻度ｒと検索速度ｖと区間の数Ｍとに基づいて、式ｖ／ｒ＞２Ｍ−１が成立するか否かを判定する。式ｖ／ｒ＞２Ｍ−１が成立する場合、検索制御部３は、コストＣよりベネフィットＢが大きいと判定して、検索要求を途中で追加する。これにより、検索装置１００全体として、レスポンスを向上させることができる。式ｖ／ｒ＞２Ｍ−１が成立しない場合、検索制御部３は、コストＣよりベネフィットＢが小さいと判定して、検索要求を途中で追加しない。これにより、検索装置１００全体として、レスポンスが低下することを防止することができる。
【符号の説明】
【０１９１】
１    要求受付部
２    更新制御部
３    検索制御部
４    更新実行部
５    データ格納部
６    一括検索実行部
７    結果返却部
１１    更新要求キュー
１２    検索要求キュー
３１    検索要求集合
３２    検索要求／バージョンＩＤ対応情報
３３    検索要求／区間ＩＤ対応情報
３４    次の一括検索実施区間情報
５１    格納データ集合
５２    バージョンＩＤ
５３    バージョンＩＤ／データ対応情報
５４    区間ＩＤ／データ対応情報
１００    検索装置
２００    クライアント
２０１    アプリケーション
３００    ネットワーク
【図１】
0005652282.tif 000002
【図２】
0005652282.tif 000003
【図３】
0005652282.tif 000004
【図４】
0005652282.tif 000005
【図５】
0005652282.tif 000006
【図６】
0005652282.tif 000007
【図７】
0005652282.tif 000008
【図８】
0005652282.tif 000009
【図９】
0005652282.tif 000010
【図１０】
0005652282.tif 000011
【図１１】
0005652282.tif 000012
【図１２】
0005652282.tif 000013
【図１３】
0005652282.tif 000014
【図１４】
0005652282.tif 000015
【図１５】
0005652282.tif 000016
【図１６】
0005652282.tif 000017
【図１７】
0005652282.tif 000018
【図１８】
0005652282.tif 000019
【図１９】
0005652282.tif 000020
【図２０】
0005652282.tif 000021
【図２１】
0005652282.tif 000022
【図２２】
0005652282.tif 000023
【図２３】
0005652282.tif 000024
【図２４】
0005652282.tif 000025
【図２５】
0005652282.tif 000026