(57)【要約】【課題】複製の同期を保証しないデータベースシステムであっても、ユーザに整合性の取れた検索結果を提示することができる検索情報選択装置を提供する。【解決手段】複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得したデータを特定する情報をユーザに対して出力する検索情報選択装置であって、複数のデータベースのそれぞれから受信したデータを特定する情報に対してマージソートを実行するともに、データを特定する情報を削除した後、出力する条件に応じた件数のデータを特定する情報を選択して出力する。【選択図】図１
2011113204.tif 000002
【特許請求の範囲】
【請求項１】
複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置であって、
前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力することを特徴とする検索情報選択装置。
【請求項２】
前記データを特定する情報にバージョン情報が含まれている場合に、最新のバージョン情報を持つ前記データを特定する情報のみを出力することを特徴とする請求項１に記載の検索情報選択装置。
【請求項３】
前記複製データベースは、前記データを削除すると、削除したデータに対して最新のバージョン情報を与えるとともに削除済みであること示す情報を保存しておき、前記削除済みのデータに対して要求があったときは、前記バージョン情報と削除済みであること示す情報を返し、
一部のデータベースのみから前記データを特定する情報を受信した場合に、他のデータベースに対して、前記データが削除済みであるか否かを問い合わせ、削除済みであれば前記ユーザに対して出力するべき前記データを特定する情報の中から前記削除済みで有るデータを特定する情報を除去することを特徴とする請求項１または２に記載の検索情報選択装置。
【請求項４】
複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置における検索情報選択方法であって、
前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力することを特徴とする検索情報選択方法。
【請求項５】
前記データを特定する情報にバージョン情報が含まれている場合に、最新のバージョン情報を持つ前記データを特定する情報のみを出力することを特徴とする請求項４に記載の検索情報選択方法。
【請求項６】
前記複製データベースは、前記データを削除すると、削除したデータに対して最新のバージョン情報を与えるとともに削除済みであること示す情報を保存しておき、前記削除済みのデータに対して要求があったときは、前記バージョン情報と削除済みであること示す情報を返し、
一部のデータベースのみから前記データを特定する情報を受信した場合に、他のデータベースに対して、前記データが削除済みであるか否かを問い合わせ、削除済みであれば前記ユーザに対して出力するべき前記データを特定する情報の中から前記削除済みであるデータを特定する情報を除去することを特徴とする請求項４または５に記載の検索情報選択方法。
【請求項７】
複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置上のコンピュータに検索情報の選択を行わせる検索情報選択プログラムであって、
前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力する処理を前記コンピュータに行わせることを特徴とする検索情報選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データベースにおける検索結果の整合性を管理する検索情報選択装置、検索情報選択方法及び検索情報選択プログラムに係わり、特にデータが複製された分散データベースシステムを対象として順序づけられた検索結果の整合性を保持する技術に関する。
【背景技術】
【０００２】
従来から、保存対象のデータを複製して使用するデータベースシステムでは、複製状態がそれぞれ異なっている可能性があるため、伝統的なリレーショナルデータベースなどでは、２相コミットなどの技術によって、複製の同期を保証している（例えば、特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】アンドリュー・Ｓ・タネンバウム，マールテン・ファン・スティー，”分散システム  原理とパラダイム  第２版”，ピアソン・エデュケーション，ｐｐ．３５９−３６４，２００９
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、データを複製して運用するデータベースシステムでは、更新要求の脱落や処理遅延などにより、データの複製がそれぞれ異なっている可能性がある。従来の伝統的なリレーショナルデータベースはこの不整合を避けるために、２相コミットなどを用いて書き込みを行うことで、複製の同期を保証している。
【０００５】
しかしながら、２相コミットはシステム規模の拡大が難しいため、近年では、システム規模を拡大するためにあえて  ２相コミットを避け、複製同期を保証しないことがある。このような状況では、それぞれの複製データから異なる検索結果を得る可能性があり、検索結果の整合性が失われてしまうという問題がある。
【０００６】
本発明は、このような事情に鑑みてなされたもので、複製の同期を保証しないデータベースシステムであっても、ユーザに整合性の取れた検索結果を提示することができる検索情報選択装置、検索情報選択方法及び検索情報選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置であって、前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力することを特徴とする。
【０００８】
本発明は、前記データを特定する情報にバージョン情報が含まれている場合に、最新のバージョン情報を持つ前記データを特定する情報のみを出力することを特徴とする。
【０００９】
本発明は、前記複製データベースは、前記データを削除すると、削除したデータに対して最新のバージョン情報を与えるとともに削除済みであること示す情報を保存しておき、前記削除済みのデータに対して要求があったときは、前記バージョン情報と削除済みであること示す情報を返し、一部のデータベースのみから前記データを特定する情報を受信した場合に、他のデータベースに対して、前記データが削除済みであるか否かを問い合わせ、削除済みであれば前記ユーザに対して出力するべき前記データを特定する情報の中から前記削除済みで有るデータを特定する情報を除去することを特徴とする。
【００１０】
本発明は、複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置における検索情報選択方法であって、前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力することを特徴とする。
【００１１】
本発明は、前記データを特定する情報にバージョン情報が含まれている場合に、最新のバージョン情報を持つ前記データを特定する情報のみを出力することを特徴とする。
【００１２】
本発明は、前記複製データベースは、前記データを削除すると、削除したデータに対して最新のバージョン情報を与えるとともに削除済みであること示す情報を保存しておき、前記削除済みのデータに対して要求があったときは、前記バージョン情報と削除済みであること示す情報を返し、一部のデータベースのみから前記データを特定する情報を受信した場合に、他のデータベースに対して、前記データが削除済みであるか否かを問い合わせ、削除済みであれば前記ユーザに対して出力するべき前記データを特定する情報の中から前記削除済みであるデータを特定する情報を除去することを特徴とする。
【００１３】
本発明は、複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させて取得した前記データを特定する情報をユーザに対して出力する検索情報選択装置上のコンピュータに検索情報の選択を行わせる検索情報選択プログラムであって、前記複数のデータベースのそれぞれから受信した前記データを特定する情報に対してマージソートを実行するともに、前記データを特定する情報を削除した後、出力する条件に応じた件数の前記データを特定する情報を選択して出力する処理を前記コンピュータに行わせることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、複製の同期を保証しないデータベースシステムであっても、ユーザに整合性の取れた検索結果を得ることができるという効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態の構成を示すブロック図である。
【図２】図１に示す装置の動作を示すシーケンス図である。
【図３】図１に示す装置の動作を示す説明図である。
【図４】図１に示す装置の動作を示すシーケンス図である。
【図５】図１に示す装置の動作を示すシーケンス図である。
【図６】図１に示す装置の動作を示す説明図である。
【図７】図１に示す装置の動作を示すシーケンス図である。
【図８】図１に示す装置の動作を示すシーケンス図である。
【図９】図１に示す装置の動作を示すシーケンス図である。
【図１０】図１に示す装置の動作を示すシーケンス図である。
【図１１】図１に示す装置の動作を示すシーケンス図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して、本発明の一実施形態による検索情報選択装置を説明する。図１は同実施形態の構成を示すブロック図である。この図において、符号１、２、３は、３つの複製データベースシステム（以下、ＤＢ１、ＤＢ２、ＤＢ３と称する）であり、検索要求に応じて検索結果を返す。符号４は、コンピュータ装置で構成するクライアントであり、３つのＤＢ１〜３との間はコンピュータネットワーク（以下、単にネットワークと称する）Ｎで接続されている。
【００１７】
符号４１は、ネットワークＮを介して、３つのＤＢ１〜３との間で情報通信を行う通信部である。符号４２は、検索結果の文書データの中から整合性が取れるように文書データを選択する文書選択部である。符号４３は、記憶媒体で構成し、検索結果を保存する結果保存部である。符号４４は、検索結果の複数の文書データのバージョン情報を比較して、古いバージョンの文書データを削除する処理を行うバージョン比較・除去部である。符号４５は、検索結果の複数の文書データのうち、重複する文書データを除去する処理を行う重複除去部である。符号４６は、検索結果の文書データをマージソート処理するマージソート部である。
【００１８】
なお、図１に示す装置の構成例では文書データの検索結果に対する処理をクライアント４で行うものとして説明するが、クライアント・サーバ間に設置されるコンポーネントが代理で行っても構わないし、いずれかの複製データベースで行ってもよい。
【００１９】
次に、図２、図３を参照して、図１に示す各装置の動作を説明する。クライアント４は、３つのＤＢ１、ＤＢ２、ＤＢ３のそれぞれに対して検索要求を送信する。実際には、クライアント４はユーザの指示によって検索要求を発行するが、公知の処理手順であるのでここでは詳細な説明を省略する。ここでは、あるキーワードを含むレコードをスコアの降順にソートし、先頭（Ｎ＝１）から３件（Ｄ＝３）の文書データを返す検索要求を送信したものとする。ここで、Ｎは、検索結果の先頭から数えて何件目であるかを示す変数である。また、Ｄは、Ｎ件目から何件分出力するかを示す変数である。なお、スコアの決定方法は任意である。この検索要求を受けて、３つのＤＢ１、ＤＢ２、ＤＢ３は文書データの検索を実行し、先頭から３件（Ｎ＝１、Ｄ＝３）をクライアント４に返す。図２において、文書Ａ〜Ｅは、文書データを一意に識別可能な文書ＩＤを示し、文書ＩＤの後に続く数値は、その文書データのスコア値を示している。ここでは文書ＩＤとスコア値のみを返しているが、文書データなどを一緒に返すようにしてもよい。図２に示す例では、ＤＢ１から文書Ｂ、Ｃ、Ｅが返され、ＤＢ２から文書Ａ、Ｃ、Ｄが返され、ＤＢ３から文書Ａ、Ｂ、Ｄが返されることになる（図３参照）。
【００２０】
マージソート部４６は、通信部４１を介して、検索結果を取得すると、その和集合をスコアの降順に並べる（図３参照）。複数のソート済みデータ集合をソートすることをマージソートというため、以下の説明においてはマージソートと称する。そして、マージソート部４６は、スコアを降順に並べた結果の情報を重複除去部４５へ出力する。重複除去部４５は、重複している文書を除去して、文書選択部４２へ出力する（図３参照）。文書選択部４２は、検索要求が、先頭（Ｎ＝１）から３件（Ｄ＝３）の文書データを返す要求であるので、先頭３件（図３に示す例では、スコア値が１０の文書Ａ、スコア値が９の文書Ｂ、スコア値が８の文書Ｃが該当する）をユーザに出力し（例えば、図示しない表示装置に表示する）、残りの文書（スコア値が７の文書Ｄとスコア値が６の文書Ｅ）は次の検索に備えて、結果保存部４３に保存しておく。
【００２１】
次に、図４を参照して、４件目から６件目（Ｎ＝４、Ｄ＝３）の検索を行う動作を説明する。まず、クライアント４は、４件目から６件目（Ｎ＝４、Ｄ＝３）の検索要求を３つのＤＢ１、ＤＢ２、ＤＢ３のそれぞれに対して送信する。この検索要求を受けて、３つのＤＢ１、ＤＢ２、ＤＢ３は文書データの検索を実行し、先頭から数えて４件目から６件目（Ｎ＝４、Ｄ＝３）をクライアント４に返す（図４参照）。図４に示す例では、ＤＢ１から文書Ｆ、Ｇ、Ｈが返され、ＤＢ２から文書Ｅ、Ｆ、Ｇが返され、ＤＢ３から文書Ｅ、Ｆ、Ｇが返されることになる。
【００２２】
マージソート部４６は、通信部４１を介して、検索結果を取得すると、マージソートして、スコアを降順に並べた結果の情報を重複除去部４５へ出力する。重複除去部４５は、重複している文書を除去して、文書選択部４２へ出力する（図３参照）。文書選択部４２は、検索要求が、先頭から数えて４件目（Ｎ＝４）から３件（Ｄ＝３）の文書データを返す要求であるので、先頭３件（図４に示す例では、スコア値が７の文書Ｄ、スコア値が６の文書Ｅ、スコア値が５の文書Ｆが該当する）をユーザに出力し、残りの文書（スコア値が４の文書Ｇとスコア値が３の文書Ｈ）は次の検索に備えて、結果保存部４３に保存しておく。
【００２３】
このように、３つのＤＢ１、ＤＢ２、ＤＢ３のそれぞれからの検索結果を取得し、ソートマージした後に、重複を除去するようにしたため、ユーザ対してに整合性の取れた検索結果を出力することが可能になる。
【００２４】
次に、図５、図６を参照して、３つの複製データベース（ＤＢ１、ＤＢ２、ＤＢ３）が、レコードのバージョンを管理して、検索結果にレコードのバージョンを含めて返す処理について説明する。なお、ここではバージョン番号として自然数を用いるが、他にもクロックやタイムスタンプなどの比較可能な数値を用いることが可能である。
【００２５】
まず、クライアント４は、３つのＤＢ１、ＤＢ２、ＤＢ３に対して検索要求を送信する。ここでは、あるキーワードを含むレコードをスコアの降順にソートし、先頭から３件（Ｎ＝１、Ｄ＝３）を返すものとする。３つのＤＢ１、ＤＢ２、ＤＢ３それぞれは検索要求に応じて検索を実行し、先頭から３件をクライアント４に返す。このとき、各レコードにバージョン番号を付与する。図５中のｖ１はバージョン１を意味する。
【００２６】
バージョン比較・除去部４４は、通信部４１を介して、検索結果を取得すると、同じバージョンの文書が複数存在するときは、ひとつの文書だけを残すとともに、文書ごとに最新バージョン（バージョン番号の値が大きいもの）のみを残して、マージソート部４６へ出力する。マージソート部４６は、それらの和集合をスコアの降順に並べるマージソートを行い、文書選択部４２へ出力する（図６参照）。文書選択部４２は、検索要求が、先頭（Ｎ＝１）から３件（Ｄ＝３）の文書データを返す要求であるので、先頭３件（図５に示す例では、スコア値が１０でバージョンｖ１の文書Ａ、スコア値が９でバージョンｖ１の文書Ｂ、スコア値が８でバージョンｖ２の文書Ｄが該当する）をユーザに出力し、残りの文書（スコア値が７でバージョンｖ２の文書Ｃとスコア値が６でバージョンｖ１の文書Ｅ）は次の検索に備えて、結果保存部４３に保存しておく。なお、最新バージョンのみを残す処理はマージソート後に行ってもよい。
【００２７】
このように、３つのＤＢ１、ＤＢ２、ＤＢ３のそれぞれからの検索結果を取得し、同じバージョンの文書が複数存在するときは、ひとつの文書だけを残すとともに、文書ごとに最新バージョンのみを残すようにしたため、ユーザに対しては最新バージョンのみの検索結果を出力することが可能になる。
【００２８】
次に、図７〜図１１を参照して、３つの複製データベース（ＤＢ１、ＤＢ２、ＤＢ３）において削除されたレコードに対してもバージョンを管理する場合について説明する。図７は、ＤＢ１からデータを削除するときの動作を示す図である。クライアント４が文書Ａの削除要求を送信すると、ＤＢ１は文書Ａの内容を「削除済み」に書き換え、バージョン番号を更新する（１から２へ変更する）。このように、削除されたことを証明する情報をdormant death certificateという。
【００２９】
次に、図８、図９を参照して、文書検索動作を説明する。まず、クライアント４は、３つのＤＢ１、ＤＢ２、ＤＢ３に対して検索要求を送信する。ここでは、あるキーワードを含むレコードをスコアの降順にソートし、先頭から３件（Ｎ＝１、Ｄ＝３）を返すものとする。３つのＤＢ１、ＤＢ２、ＤＢ３それぞれは検索要求に応じて検索を実行し、先頭から３件をクライアント４に返す。このとき、各レコードにバージョン番号を付与する。
【００３０】
バージョン比較・除去部４４は、通信部４１を介して、検索結果を取得する。ここで、文書Ａは高いスコアを持ち、ユーザに対して出力される候補であるが、ＤＢ１から結果を得られていない。このため、バージョン比較・除去部４４は、ＤＢ１に文書Ａを要求する。すると、ＤＢ１は、文書Ａが削除済みであることをバージョン番号（ｖ２）とともに返す。このバージョン番号は、他の複製データベース（ＤＢ２、ＤＢ３）のバージョン番号（ｖ１）よりも大きい。このため、バージョン比較・除去部４４は文書Ａが削除済みであると判断し、検索結果から除去して、その結果をマージソート部４６へ出力する。
【００３１】
マージソート部４６は、それらの和集合をスコアの降順に並べるマージソートを行い、文書選択部４２へ出力する。文書選択部４２は、検索要求が、先頭（Ｎ＝１）から３件（Ｄ＝３）の文書データを返す要求であるので、先頭３件（図９に示す例では、スコア値が９でバージョンｖ１の文書Ｂ、スコア値が８でバージョンｖ２の文書Ｄ、スコア値が７でバージョンｖ２の文書Ｃが該当する）をユーザに出力し、残りの文書（スコア値が６でバージョンｖ１の文書Ｅ）は次の検索に備えて、結果保存部４３に保存しておく。
【００３２】
一方、削除済みレコードを除去した結果、Ｄ件に満たないときは、特別な処理が必要になる。例えば、図７に示したようにＤＢ１の文書Ａが削除済みであるのに加え、ＤＢ２の文書Ｂも削除済みであるとし、ＤＢ１、ＤＢ２、ＤＢ３は図１０に示すような検索結果を返したとする。バージョン比較・除去部４４は、ＤＢ１とＤＢ２に対して、それぞれ文書Ａ、文書Ｂを要求する。すると、ＤＢ１はいずれも削除済みであるとの応答を返す。この検索結果から文書Ａ、Ｂを除去すると、文書Ｃと文書Ｄの２件しか残らない。これは、Ｄの値が３であることを満たさない。ここで、不足している文書数をα＝３−２＝１と表すことにする。
【００３３】
クライアント４は不足文書を補うために、（Ｎ←Ｎ＋Ｄ、Ｄ←α；←は代入を表す）として検索を再実行し、マージソート部４６によりマージソートなどを行って結果をユーザに出力する（図１１、Ｎ＝４、Ｄ＝１）。このようにして、検索結果の整合性を維持する。また、以降の検索においては、ユーザが指定するＮにαを加算して検索を実行する。例えばユーザは次に（Ｎ＝４、Ｄ＝３）の検索要求を送信すると予想されるが、Ｎ＝４の検索はすでに行っているため、（Ｎ＝５、Ｄ＝３）に変換してからＤＢ１、ＤＢ２、ＤＢ３に送信する。
【００３４】
以上説明したように、複製されたデータを蓄積する複数のデータベースのそれぞれに対して、検索処理を実行させ、その結果のうち、先頭から数えて第Ｎ件から第Ｎ＋Ｄ−１件までを出力させ、各データベースから取得した検索結果をユーザに対して出力するクライアント装置において、各データベースから受信した検索結果、および第Ｎ件より前の検索結果のうち、ユーザに提示していない結果についてマージソートを実行し、重複した結果を削除した後、先頭からＤ件をユーザに出力するようにしたため、複製の同期を保証しないデータベースシステムであっても、ユーザに整合性の取れた検索結果を出力することができる。また、同じバージョンの文書が複数存在するときは、ひとつの文書だけを残すとともに、文書ごとに最新バージョンのみを残すようにしたため、ユーザに対しては最新バージョンのみの検索結果を出力することが可能になる。また、レコードの削除を正しく反映するために、複製データベースにデータの削除状況を管理させ、削除されたはずのデータが検索結果に表れないようにしたため、ユーザに整合性の取れた検索結果を出力することができる。
【００３５】
なお、図１に示すクライアント４の各処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより検索情報選択処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００３６】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【産業上の利用可能性】
【００３７】
複製の同期を保証しないデータベースシステムにおいてユーザに整合性の取れた検索結果を出力することが不可欠な用途に適用できる。
【符号の説明】
【００３８】
１、２、３・・・データベース（ＤＢ）、４・・・クライアント（端末装置）、４１・・・通信部、４２・・・文書選択部、４３・・・結果保存部、４４・・・バージョン比較・除去部、４５・・・重複除去部、４６・・・マージソート部、Ｎ・・・コンピュータネットワーク
【図１】
2011113204.tif 000003
【図２】
2011113204.tif 000004
【図３】
2011113204.tif 000005
【図４】
2011113204.tif 000006
【図５】
2011113204.tif 000007
【図６】
2011113204.tif 000008
【図７】
2011113204.tif 000009
【図８】
2011113204.tif 000010
【図９】
2011113204.tif 000011
【図１０】
2011113204.tif 000012
【図１１】
2011113204.tif 000013