(57)【要約】【課題】検索処理を高速化する検索システムを提供する。【解決手段】複数のＤＢを管理する複数の情報管理装置２００と、検索装置１００と、を備えた検索システムであって、検索装置１００は、検索要求から検索プランを生成するプラン生成部１０２と、実行情報を情報管理装置２００に送信する要求送信部１０４とを備え、情報管理装置２００は、実行情報を用いて処理を実行する実行部と、取得元のＤＢを識別する取得元情報を実行結果に対応づける対応づけ部と、実行結果を利用する処理を実行する情報管理装置２００に実行結果を転送する転送部とを備え、実行部は、転送された実行結果を利用する処理をさらに実行して実行結果を追加し、対応づけ部は、実行結果に取得元情報をさらに対応づけ、転送部は、対応づけられた取得元情報で識別されるＤＢを管理する情報管理装置に実行結果をさらに転送することを特徴とする。【選択図】        図１
2008084134.tif 000002
【特許請求の範囲】
【請求項１】
情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置とネットワークを介して接続され、前記情報管理装置から前記情報を検索する検索装置と、を備えた検索システムであって、
前記検索装置は、
前記ネットワークに接続されたクライアント端末からの前記情報の検索要求を受付ける受付部と、
受付けた前記検索要求を解析し、複数の前記情報管理装置が実行すべき検索指令を含む検索プランを生成するプラン生成部と、
生成された前記検索プランに含まれる前記検索指令ごとに、前記検索指令の実行に用いる実行情報を、前記検索指令を実行すべき前記情報管理装置に対して送信する要求送信部と、
前記検索指令の実行結果を前記情報管理装置から受信する結果受信部と、
受信した前記実行結果に基づいて検索結果を生成する結果生成部と、
生成した前記検索結果を前記クライアント端末に送信する結果送信部と、を備え、
前記情報管理装置は、
前記実行情報を前記検索装置から受信する受信部と、
受信した前記実行情報を用いて前記検索指令を実行する実行部と、
実行した前記検索指令の前記実行結果に、前記実行結果の取得元である前記データベースを識別する予め定められた取得元情報を対応づける対応づけ部と、
前記取得元情報が対応づけられた前記実行結果を、前記実行結果を利用する前記検索指令を実行すべき他の前記情報管理装置に転送する転送部と、を備え、
前記実行部は、前記他の前記情報管理装置から転送された前記実行結果を利用する前記検索指令をさらに実行し、転送された前記実行結果に、実行した前記検索指令の前記実行結果を追加し、
前記対応づけ部は、実行した前記検索指令の前記実行結果を追加した前記実行結果に、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報をさらに対応づけ、
前記転送部は、前記取得元情報が対応づけられた前記実行結果を、前記実行結果に対応づけられた前記取得元情報で識別される前記データベースを管理する前記情報管理装置にさらに転送すること、
を特徴とする検索システム。
【請求項２】
前記情報管理装置は、
前記実行結果の取得元である前記データベースごとに前記実行結果を記憶可能な結果記憶部をさらに備え、
前記実行部は、転送された前記実行結果に対応づけられた前記取得元情報に基づいて、転送された前記実行結果を、取得元である前記データベースごとに前記結果記憶部に記憶し、記憶した前記実行結果のそれぞれに、実行した前記検索指令の前記実行結果を追加すること、
を特徴とする請求項１に記載の検索システム。
【請求項３】
前記情報管理装置は、
取得元である前記データベースごとの前記実行結果を識別する結果識別情報と、前記実行結果ごとの前記実行結果の取得元の前記データベースを識別する前記取得元情報とを対応づけて記憶可能な対応記憶部をさらに備え、
前記対応づけ部は、実行した前記検索指令の前記実行結果を識別する前記結果識別情報と、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報を対応づけて前記対応記憶部に記憶すること、
を特徴とする請求項２に記載の検索システム。
【請求項４】
前記プラン生成部は、前記実行結果を転送する内容を表す前記検索指令に関する情報を含む前記検索プランを生成し、
前記要求送信部は、前記実行結果を利用する前記検索指令を実行する前記情報管理装置に前記実行結果を転送する内容を表す前記検索指令の前記実行情報を送信し、
前記転送部は、前記実行部が前記実行結果を転送する内容を表す前記検索指令の前記実行情報を受信した場合に、前記実行結果を利用する前記検索指令を実行する前記情報管理装置に前記実行結果を転送すること、
を特徴とする請求項１に記載の検索システム。
【請求項５】
前記要求送信部は、前記実行結果のうち利用する前記実行結果を特定する特定情報を含む前記実行情報を送信し、
前記情報管理装置は、
前記実行部が実行した前記検索指令の前記実行結果のうち、前記実行部が受信した前記実行情報に含まれる前記特定情報で特定される前記実行結果を取得する結果取得部をさらに備え、
前記転送部は、前記結果取得部が取得した前記実行結果を、前記実行結果を利用する前記検索指令を実行する前記情報管理装置に転送すること、
を特徴とする請求項４に記載の検索システム。
【請求項６】
前記要求送信部は、転送先の前記情報管理装置を識別する装置識別情報を含む前記実行情報を送信し、
前記転送部は、前記結果取得部が取得した前記実行結果を、前記実行部が受信した前記実行情報に含まれる前記装置識別情報で識別される前記情報管理装置に転送すること、
を特徴とする請求項５に記載の検索システム。
【請求項７】
前記結果生成部は、生成された前記検索プランに含まれる前記検索指令であって、受信した前記実行結果から前記検索結果を生成する前記検索指令を実行すること、
を特徴とする請求項１に記載の検索システム。
【請求項８】
生成された前記検索プランに基づいて前記検索指令の実行順序を決定する決定部をさらに備え、
前記要求送信部は、決定された前記実行順序で、前記検索指令を実行する前記情報管理装置に対して前記実行情報を送信すること、
を特徴とする請求項１に記載の検索システム。
【請求項９】
情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置とネットワークを介して接続され、前記情報管理装置から前記情報を検索する検索装置と、を備えた検索システムにおける検索方法であって、
前記検索装置によって、前記ネットワークに接続されたクライアント端末からの前記情報の検索要求を受付ける受付ステップと、
前記検索装置によって、受付けた前記検索要求を解析し、複数の前記情報管理装置が実行すべき検索指令を含む検索プランを生成するプラン生成ステップと、
前記検索装置によって、生成された前記検索プランに含まれる前記検索指令ごとに、前記検索指令の実行に用いる実行情報を、前記検索指令を実行すべき前記情報管理装置に対して送信する要求送信ステップと、
前記情報管理装置によって、前記実行情報を前記検索装置から受信する受信ステップと、
前記情報管理装置によって、受信した前記実行情報を用いて前記検索指令を実行する第１実行ステップと、
前記情報管理装置によって、実行した前記検索指令の実行結果に、前記実行結果の取得元である前記データベースを識別する予め定められた取得元情報を対応づける第１対応づけステップと、
前記情報管理装置によって、前記取得元情報が対応づけられた前記実行結果を、前記実行結果を利用する前記検索指令を実行すべき他の前記情報管理装置に転送する第１転送ステップと、
前記情報管理装置によって、前記他の前記情報管理装置から転送された前記実行結果を利用する前記検索指令を実行し、転送された前記実行結果に、実行した前記検索指令の前記実行結果を追加する第２実行ステップと、
前記情報管理装置によって、実行した前記検索指令の前記実行結果を追加した前記実行結果に、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報を対応づける第２対応づけステップと、
前記情報管理装置によって、前記取得元情報が対応づけられた前記実行結果を、前記実行結果に対応づけられた前記取得元情報で識別される前記データベースを管理する前記情報管理装置に転送する第２転送ステップと、
前記検索装置によって、前記実行結果を前記情報管理装置から受信する結果受信ステップと、
前記検索装置によって、受信した前記実行結果に基づいて検索結果を生成する結果生成ステップと、
前記検索装置によって、生成した前記検索結果を前記クライアント端末に送信する結果送信ステップと、
を備えたことを特徴とする検索方法。
【請求項１０】
情報を分散して格納する複数のデータベースを、前記データベースごとに管理する外部情報管理装置と、前記情報を検索する検索装置とにネットワークを介して接続された情報管理装置であって、
前記データベースを記憶する情報記憶部と、
検索指令の実行に用いる実行情報を前記検索装置から受信する受信部と、
受信した前記実行情報を用いて前記検索指令を実行する実行部と、
実行した前記検索指令の前記実行結果に、前記実行結果の取得元である前記データベースを識別する予め定められた取得元情報を対応づける対応づけ部と、
前記取得元情報が対応づけられた前記実行結果を、前記実行結果を利用する前記検索指令を実行すべき前記外部情報管理装置に転送する転送部と、を備え、
前記実行部は、前記外部情報管理装置から転送された前記実行結果を利用する前記検索指令をさらに実行し、転送された前記実行結果に、実行した前記検索指令の前記実行結果を追加し、
前記対応づけ部は、実行した前記検索指令の前記実行結果を追加した前記実行結果に、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報をさらに対応づけ、
前記転送部は、前記取得元情報が対応づけられた前記実行結果を、前記実行結果に対応づけられた前記取得元情報で識別される前記データベースを管理する前記外部情報管理装置にさらに転送すること、
を特徴とする情報管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ネットワーク接続された複数のデータベースにデータを水平分割して登録する分散データベースに対し、与えられた検索条件に従い検索を行う検索システム、検索方法、および情報管理装置に関するものである。
【背景技術】
【０００２】
近年、多数の件数からなるデータを、例えば件数が均等となるように複数の塊に分割し、分割した塊ごとにネットワーク接続された複数のデータベースに登録して処理する水平分割型の分散データベースシステムが広く知られている。
【０００３】
分散データベースの検索処理では、ネットワーク結合されて分散している装置間で検索処理の中間結果を転送し、検索処理の各ステップを継続して実行する必要がある。このような検索処理では、ネットワーク経由の中間結果の転送処理は、ＣＰＵ（Central Processing Unit）での演算、メモリＩ／Ｏ、ディスクＩ／Ｏなどの検索処理に関する他の処理と比較して桁違いに時間コストが高い。このため、極力転送データ量を削減することが検索処理の高速化のために必要となる。
【０００４】
これに対し、従来の水平分割されたデータベースでは、検索処理中のデータ転送の際の無駄な情報転送を避け、処理に必要な情報を適切に判断し転送するアプローチがとられている。例えば、非特許文献１では、パラレル連想ジョインなどのハッシュ関数を用いてデータ転送先を決定し、決定したデータ転送先にのみデータを転送することで無駄な情報転送を回避する技術が提案されている。
【０００５】
具体的には、非特許文献１の方法では、まず、データの属性に関する特定のハッシュ関数をあらかじめ想定しておく。また、その結果のハッシュ値に対応する、中間結果の転送先となる物理データベースをあらかじめ定義しておく。
【０００６】
ここで、ジョイン演算のような、論理データベース上の結果を他の論理データベースに転送して演算を行う場合を考える。各データベースの中間結果を転送する際には、まず、その中間結果に含まれるデータの属性の値について、前記のハッシュ関数を適用した結果得られるハッシュ値を求める。求めたハッシュ値に基づき、ハッシュ値と転送先の物理データベースに関して事前に定義した対応関係に従って、転送する中間結果一つ一つのデータ転送先の物理データベースを決定する。
【０００７】
転送した先の物理データベースでは、ジョイン演算で行う比較演算で、一致する可能性のあるデータだけが、ハッシュ関数により振り分けられて、同一の物理データベース上に集まってくることになる。このようにして、演算の結果破棄されてしまうような、無駄なデータの転送を削減できる。
【０００８】
また、仮にデータの属性Ｂについてジョイン演算を行うことが事前にわかっている場合、データ登録時に事前に上記のハッシュ関数とデータベースの対応関係に従い、データの属性Ｂに関してハッシュ値を求めることで、個々のデータの登録先物理データベースを決定できる。そこで、このような手法で決定した登録先物理データベースに、事前にデータを登録しておく。
【０００９】
このようにして作成した論理データベースＡ上の中間結果と、他の論理データベースＢ上の中間結果との間のジョイン演算の演算を行う場合を考える。この場合、ジョイン演算の演算対象となる中間結果のうち、転送するデータの識別を、片方の論理データベースＢの結果だけに限定できるため、上記に示した中間結果の転送方法と比較して転送データを減少させられる。
【００１０】
なお、非特許文献１の４３８ページ第３段落に示されるように、このような仕組みを用いて中間結果転送を行わない場合は、それぞれの論理データベースの結果すべてを、他方の論理データベースに属する一つの物理データベースに転送することが必要となる。受け取った中間結果に含まれるデータのうち、転送先の物理データベース上のデータと関連するデータは一部のデータに限定されることが多い。したがって、関連しないデータの転送は、無駄なデータの転送であったことになる。
【００１１】
【非特許文献１】Ozsu Valduriez、"Principles of Distributed Database Systems"、Printice Hall、Chapter 13.3.3（P.436-P.444）、Parallel Database Systems.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、非特許文献１の方法では、分散配置するデータを登録するときの処理負担が大きいという問題があった。すなわち、非特許文献１の方法では、登録に先立ってデータベースに登録されるデータ特性を予測評価し、適切なハッシュ関数の設定を行い、検索の前に予め水平分割して登録しておく必要があった。
【００１３】
このため、例えば、データベースシステム運用時にデータ分割の構成を変更する必要が生じた場合、ハッシュ関数を用いてデータの登録先を再設定しなければならず、処理負担が増大するという問題があった。
【００１４】
本発明は、上記に鑑みてなされたものであって、データ登録時の処理負担を軽減しつつ、検索処理における中間的な処理結果の通信コストを削減し、検索処理の高速化を実現できる検索システム、検索方法、および情報管理装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明は、情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置とネットワークを介して接続され、前記情報管理装置から前記情報を検索する検索装置と、を備えた検索システムであって、前記検索装置は、前記ネットワークに接続されたクライアント端末からの前記情報の検索要求を受付ける受付部と、受付けた前記検索要求を解析し、複数の前記情報管理装置が実行すべき検索指令を含む検索プランを生成するプラン生成部と、生成された前記検索プランに含まれる前記検索指令ごとに、前記検索指令の実行に用いる実行情報を、前記検索指令を実行すべき前記情報管理装置に対して送信する要求送信部と、前記検索指令の実行結果を前記情報管理装置から受信する結果受信部と、受信した前記実行結果に基づいて検索結果を生成する結果生成部と、生成した前記検索結果を前記クライアント端末に送信する結果送信部と、を備え、前記情報管理装置は、前記実行情報を前記検索装置から受信する受信部と、受信した前記実行情報を用いて前記検索指令を実行する実行部と、実行した前記検索指令の前記実行結果に、前記実行結果の取得元である前記データベースを識別する予め定められた取得元情報を対応づける対応づけ部と、前記取得元情報が対応づけられた前記実行結果を、前記実行結果を利用する前記検索指令を実行すべき他の前記情報管理装置に転送する転送部と、を備え、前記実行部は、前記他の前記情報管理装置から転送された前記実行結果を利用する前記検索指令をさらに実行し、転送された前記実行結果に、実行した前記検索指令の前記実行結果を追加し、前記対応づけ部は、実行した前記検索指令の前記実行結果を追加した前記実行結果に、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報をさらに対応づけ、前記転送部は、前記取得元情報が対応づけられた前記実行結果を、前記実行結果に対応づけられた前記取得元情報で識別される前記データベースを管理する前記情報管理装置にさらに転送すること、を特徴とする。
【００１６】
また、本発明は、上記装置を実行することができる検索方法である。
【００１７】
また、本発明は、情報を分散して格納する複数のデータベースを、前記データベースごとに管理する外部情報管理装置と、前記情報を検索する検索装置とにネットワークを介して接続された情報管理装置であって、前記データベースを記憶する情報記憶部と、検索指令の実行に用いる実行情報を前記検索装置から受信する受信部と、受信した前記実行情報を用いて前記検索指令を実行する実行部と、実行した前記検索指令の前記実行結果に、前記実行結果の取得元である前記データベースを識別する予め定められた取得元情報を対応づける対応づけ部と、前記取得元情報が対応づけられた前記実行結果を、前記実行結果を利用する前記検索指令を実行すべき前記外部情報管理装置に転送する転送部と、を備え、前記実行部は、前記外部情報管理装置から転送された前記実行結果を利用する前記検索指令をさらに実行し、転送された前記実行結果に、実行した前記検索指令の前記実行結果を追加し、前記対応づけ部は、実行した前記検索指令の前記実行結果を追加した前記実行結果に、実行した前記検索指令の前記実行結果の取得元である前記データベースを識別する前記取得元情報をさらに対応づけ、前記転送部は、前記取得元情報が対応づけられた前記実行結果を、前記実行結果に対応づけられた前記取得元情報で識別される前記データベースを管理する前記外部情報管理装置にさらに転送すること、を特徴とする。
【発明の効果】
【００１８】
本発明によれば、中間結果に対応づけられた取得元の情報を参照して適切な転送先に中間結果を転送できる。このため、データ登録時の処理負担を軽減し、検索処理における中間的な処理結果の通信コストを削減して検索処理の高速化を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明にかかる検索システム、検索方法、および情報管理装置の最良な実施の形態を詳細に説明する。
【００２０】
本実施の形態にかかる検索システムは、中間結果の取得元となったデータベースを特定する情報を中間結果に対応づけ、この情報を参照して、中間結果のうち転送して処理の対象となりえる部分のみを転送するものである。
【００２１】
図１は、本実施の形態にかかる検索システム１０の構成を示すブロック図である。同図に示すように、検索システム１０は、検索装置１００と、複数の情報管理装置２００ａ、２００ｂ、２００ｃ、２００ｄ（以下、単に情報管理装置２００という。）と、ネットワーク３００と、クライアント４００と、を備えている。
【００２２】
クライアント４００は、情報管理装置２００に格納された情報（データ）の検索要求を検索装置１００に送信するものであり、通常のＰＣ（Personal Computer）などにより構成される。
【００２３】
ネットワーク３００は、検索装置１００と、情報管理装置２００と、クライアント４００とを接続するネットワークであり、インターネットやＶＰＮなどのあらゆるネットワーク形態により構成することができる。
【００２４】
また、クライアント４００と検索装置１００とを接続するネットワークと、情報管理装置２００と検索装置１００とを接続するネットワークを別のネットワークで構成してもよい。
【００２５】
検索装置１００は、情報管理装置２００からデータを検索するものであり、受付部１０１と、プラン生成部１０２と、決定部１０３と、要求送信部１０４と、結果受信部１０５と、結果生成部１０６と、結果送信部１０７と、を備えている。
【００２６】
受付部１０１は、クライアント４００からデータの検索要求を受付けるものである。後述するように、本実施の形態では、受付部１０１は、ＸＭＬ（Extensible Markup Language）などの階層化された論理構造を有する構造化文書を対象とする検索要求を受付ける。このような検索要求では、検索結果を構造化文書の形式で返信することを指定することも可能である。検索要求の詳細については後述する。
【００２７】
プラン生成部１０２は、受付けられた検索要求を解析し、各データがいずれの情報管理装置２００に分割配置されているかを表すデータ分割配置情報を参照して、オペレータ群と、各オペレータ間のデータの受け渡し依存関係と、オペレータを実行するノードの割り当てとを含む検索プランを生成するものである。ここで、オペレータとは、検索結果を取得する各過程で実行される検索処理の指令をいう。
【００２８】
決定部１０３は、生成された検索プランを受け取り、検索プランに含まれる各オペレータの実行順序を決定し、決定した順序に従って、オペレータの実行に必要な情報を含むオペレータ実行情報を要求送信部１０４に順次引渡すものである。
【００２９】
すなわち、決定部１０３は、あるオペレータを実行した情報管理装置２００から、オペレータの実行終了を示す情報を受信したあと、次に実行すべきオペレータに関するオペレータ実行情報を生成し、要求送信部１０４に引き渡す。次に実行すべきオペレータが尽きた場合に、検索処理は終了する。
【００３０】
要求送信部１０４は、決定部１０３から受け取ったオペレータ実行情報に従い、オペレータを実行すべき情報管理装置２００に対してオペレータ実行情報を送信するものである。
【００３１】
結果受信部１０５は、オペレータを実行した情報管理装置２００から、オペレータの実行終了を示す情報や、オペレータの実行結果である中間結果を受信するものである。また、結果受信部１０５は、各オペレータの実行終了を示す情報を受け取った場合、決定部１０３に対して指定されたオペレータの実行終了を通知する。
【００３２】
結果生成部１０６は、結果受信部１０５から受信し、最終的に残された中間結果から、検索要求に対する検索結果を生成するものである。例えば、検索要求内に、検索結果をＸＭＬ形式で返信することが指定されていた場合、プラン生成部１０２によりＸＭＬ形式で検索結果を生成するオペレータを含む検索プランが生成されるため、結果生成部１０６は、当該オペレータに従い、中間結果をＸＭＬ形式で表した検索結果を生成する。
【００３３】
結果送信部１０７は、結果生成部１０６により生成された検索結果をクライアント４００に送信するものである。
【００３４】
情報管理装置２００は、データを水平分割して記憶するデータベースを分散して管理し、検索装置１００からの要求に応じてデータ検索を行い、検索結果を検索装置１００に返信するものである。情報管理装置２００は、処理部２１０と、結果記憶部２２１と、対応記憶部２２２と、情報記憶部２３１と、を備えている。
【００３５】
情報記憶部２３１は、検索対象となるデータを水平分割して格納する、物理的に異なる複数のデータベースのそれぞれを記憶するものである。本実施の形態では、４つの情報管理装置２００のうち、情報管理装置２００ａ、２００ｂにそれぞれ備えられた情報記憶部２３１ａ、２３１ｂに、ユーザに関する情報を格納する論理的なデータベース「people」を水平分割する。また、情報管理装置２００ｃ、２００ｄにそれぞれ備えられた情報記憶部２３１ｃ、２３１ｄに、オークションでの取引に関する情報を格納する論理的なデータベース「auction」を水平分割する。
【００３６】
なお、すべての論理的なデータベースが水平分割される必要はなく、少なくとも１つの水平分割されたデータベースを備えていればよい。また、データベースの個数は４つに限られるものではない。
【００３７】
以下では、情報管理装置２００ａ、２００ｂ、２００ｃ、２００ｄに分割配置されたデータベースを、それぞれＤＢ１、ＤＢ２、ＤＢ３、ＤＢ４という。すなわち、ＤＢ１およびＤＢ２によって論理的なデータベース「people」が構成され、ＤＢ３およびＤＢ４によって論理的なデータベース「auction」が構成される。
【００３８】
なお、本実施の形態では、データを分割配置する方法として、非ハッシュ値などを用いた特段の基準を設けずに、格納するデータレコードを順次交互に各データベースに登録するラウンドロビン方式で登録するものとする。これにより、どのようなデータ登録順序であっても、または運用開始後に想定外の新たなデータの登録が発生した場合でも、各データベースには均等な件数のデータを登録することができ、負荷分散を図ることができる。
【００３９】
また、本実施の形態では「people」データベースおよび「auction」データベースにはＸＭＬ形式でデータが格納されているものとする。図２は、「people」データベースに登録されるデータのデータ構造の一例を示す説明図である。同図に示すように、「people」データベースには、ユーザを識別するＩＤ（@id）、ユーザ名（name）、住所（address）などのユーザに関する各種情報を含む「person」データが格納される。
【００４０】
図３は、「auction」データベースに登録されるデータのデータ構造の一例を示す説明図である。同図に示すように、「auction」データベースには、オークションの取引を識別するＩＤ（@id）、取引される商品名の種別（item）、価格（price）などのオークションでの取引に関する各種情報を含む「deal」データが格納される。
【００４１】
結果記憶部２２１は、中間結果の取得元である情報記憶部２３１ごとに分けて中間結果を格納するものである。対応記憶部２２２は、中間結果を識別する結果識別情報と、中間結果に含まれる情報ごとの情報の取得元であるデータベースを識別する取得元情報とを対応づけて記憶するものである。
【００４２】
図４は、結果記憶部２２１および対応記憶部２２２のデータ構造の一例を示す説明図である。同図は、ＤＢ１から「person」データを取得したときの中間結果および取得元情報の一例を表している。
【００４３】
同図に示すように、結果記憶部２２１は、取得した中間結果をテーブル形式で表したバインドテーブル４１を格納している。また、対応記憶部２２２は、バインドテーブル４１を識別する結果識別情報（ＢＴ１）と、取得した中間結果の取得元のデータベースを識別する取得元情報（ＤＢ１）とを対応づけて格納している。
【００４４】
図５は、結果記憶部２２１および対応記憶部２２２のデータ構造の別の例を示す説明図である。同図は、ＤＢ１およびＤＢ２からユーザを識別するＩＤ（@id）を取得したときの中間結果および取得元情報の一例を表している。
【００４５】
同図に示すように、結果記憶部２２１は、取得元であるデータベースごとに、取得した中間結果を格納したバインドテーブル５１、５２を分けて格納している。また、対応記憶部２２２は、バインドテーブル５１、５２をそれぞれ識別する結果識別情報（ＢＴ１、ＢＴ２）と、取得した中間結果の取得元のデータベースを識別する取得元情報（ＤＢ１、ＤＢ２）とをそれぞれ対応づけて格納している。
【００４６】
このように、取得元であるデータベースごとに中間結果を分けて管理することにより、当該中間結果を利用するオペレータを実行する情報管理装置２００に対し、必要な中間結果のみをそれぞれ分離して転送することが可能となる。
【００４７】
図６は、結果記憶部２２１および対応記憶部２２２のデータ構造の別の例を示す説明図である。同図は、図５で示した中間結果を利用して、さらにＤＢ３からオークションの取引を表す「deal」データを取得したときの中間結果および取得元情報の一例を表している。
【００４８】
図６に示すように、結果記憶部２２１は、図５のバインドテーブル５１、５２に対し、それぞれ新たに取得された「deal」データが中間結果として追加されたバインドテーブル６１、６２を格納している。
【００４９】
また、対応記憶部２２２は、バインドテーブル６１、６２をそれぞれ識別する結果識別情報（ＢＴ１、ＢＴ２）に、新たに取得した中間結果の取得元のデータベースを識別する取得元情報（ＤＢ３）をさらに対応づけて格納している。このように、中間結果として取得したデータの属性ごとに取得元情報が異なりうるため、取得元情報はデータの属性ごとに複数格納されうる。
【００５０】
なお、情報記憶部２３１、結果記憶部２２１、および対応記憶部２２２は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００５１】
ここで、受付部１０１により受け付けられる検索要求の詳細について説明する。図７は、検索要求の一例を示す説明図である。同図は、上述のように４つの情報記憶部２３１内にＸＭＬデータを水平分割して格納した分散データベースを対象とし、検索結果としてＸＭＬ形式のデータを返す検索式（検索要求）の例を示している。
【００５２】
同図の検索要求は、住所が「Kawasaki」のユーザ（person）すべてについて、その名前（name）を取得し、さらにオークションで購入した取引情報（deal）を取得し、ユーザが所望する物の種別（watch/@category）と競り落とした商品の種別（item/@category）とが一致しているユーザと、その商品の名前とを取り出して出力することを表している。
【００５３】
図８は、検索結果の出力形式の一例を示す説明図である。同図は、図７に示した検索要求で指定された検索結果の返信形式に対応する検索結果の出力形式を表している。図８に示すように、ユーザ名や商品の種別名をＸＭＬ形式で表した検索結果を出力可能である。
【００５４】
次に、図１の処理部２１０の詳細について説明する。図９は、処理部２１０の詳細な構成を示すブロック図である。同図に示すように、処理部２１０は、受信部２１１と、実行部２１２と、対応づけ部２１３と、結果取得部２１４と、転送部２１５と、を備えている。
【００５５】
受信部２１１は、検索装置１００から、オペレータ実行情報を受信するものである。
【００５６】
実行部２１２は、受信部２１１により受信されたオペレータ実行情報に従って、オペレータを実行するものである。なお、実行部２１２は、受信したオペレータ実行情報が、中間結果の転送を要求するオペレータに関するオペレータ実行情報である場合は、転送部２１５に対して、オペレータ実行情報を引き渡す。この場合のオペレータ実行情報には、転送先となる情報管理装置２００を識別する情報と、転送する中間結果および転送するカラムを特定する情報とが含まれる。
【００５７】
また、実行部２１２は、各オペレータの実行結果を結果記憶部２２１に記憶する。すなわち、実行すべきオペレータがデータ検索である場合は、情報記憶部２３１内のデータベースを検索して得られた結果を中間結果として結果記憶部２２１に記録する。
【００５８】
ＸＭＬデータのノードスキャンなど中間結果の特定のカラム値で示されるノードを基点とした条件に合致するデータを取得するオペレータの場合は、対応するカラム値と同じレコードを構成するような形式で中間結果を記録する。また、ジョインなど複数の中間結果間の演算の場合は、それら中間結果間のカラム値の対応関係をレコードとして表現した中間結果を記録する。
【００５９】
また、実行部２１２は、他の情報管理装置２００から転送された中間結果を受信した場合、受信した中間結果を新規に作成して結果記憶部２２１に記憶する。記憶した中間結果は、この後に実行されるオペレータで利用される。また、実行部２１２は、各オペレータの処理が終了した場合、終了状態を表す情報を検索装置１００に返信する。
【００６０】
対応づけ部２１３は、実行部２１２が実行したオペレータの結果である中間結果に、当該中間結果の取得元であるデータベースの取得元情報を対応づけて対応記憶部２２２に記憶するものである。また、対応づけ部２１３は、他の情報管理装置２００から転送された中間結果を受信した場合、当該中間結果に対応づけられている取得元情報を新規に作成して対応記憶部２２２に記憶する。
【００６１】
結果取得部２１４は、実行部２１２が中間結果の転送を要求するオペレータ実行情報を受け取ったとき、当該オペレータ実行情報に記述されている転送先の情報管理装置２００を識別する情報、転送する中間結果およびカラムを特定する情報を参照して、転送すべき中間結果を結果記憶部２２１から取得するものである。
【００６２】
転送部２１５は、結果取得部２１４により取得された中間結果を、転送が指定された転送先の情報管理装置２００に転送するものである。
【００６３】
次に、このように構成された本実施の形態にかかる検索システム１０による検索処理について説明する。図１０は、本実施の形態における検索処理の全体の流れを示すフローチャートである。
【００６４】
まず、検索装置１００の受付部１０１は、クライアント４００から入力された検索要求を受付ける（ステップＳ１００１）。次に、プラン生成部１０２は、入力された検索要求を解析し、検索プランを生成する（ステップＳ１００２）。
【００６５】
例えば、図７に示したような検索要求が入力された場合、プラン生成部１０２は、まず「people」データベースから住所が「Kawasaki」であるユーザを検索し、次に「auction」データベースからユーザのＩＤに一致するバイヤーのＩＤを有する取引を取得し、次に「people」データベースから取引される商品の種別と一致する物の種別を有するユーザを検索するような検索プランを生成する。
【００６６】
次に、決定部１０３は、各検索プランに含まれるオペレータの実行順序を決定する（ステップＳ１００３）。続いて、決定部１０３は、実行順序に従い、次に実行するオペレータを決定する（ステップＳ１００４）。
【００６７】
次に、要求送信部１０４は、決定されたオペレータを実行する情報管理装置２００に対し、当該オペレータのオペレータ実行情報を送信する（ステップＳ１００５）。
【００６８】
オペレータ実行情報を送信された情報管理装置２００は、当該オペレータ実行情報にしたがってオペレータを実行するオペレータ実行処理を行う（ステップＳ１００６）。オペレータ実行処理の詳細については後述する。
【００６９】
次に、検索装置１００の結果生成部１０６は、検索プランに応じてオペレータの実行を行う（ステップＳ１００７）。なお、結果生成部１０６が実行するオペレータの実行が決定されていない場合は、当該ステップはスキップする。すなわち、例えば、最終的に得られた中間結果から検索結果を生成するオペレータの実行が決定された場合に、結果生成部１０６は、当該オペレータを実行する。
【００７０】
次に、決定部１０３は、すべてのオペレータが実行されたか否かを判断し（ステップＳ１００８）、実行されていない場合は（ステップＳ１００８：ＮＯ）、次に実行するオペレータを決定して処理を繰り返す（ステップＳ１００４）。
【００７１】
すべてのオペレータが実行された場合は（ステップＳ１００８：ＹＥＳ）、結果送信部１０７が検索結果をクライアント４００に送信して（ステップＳ１００９）、検索処理を終了する。
【００７２】
次に、ステップＳ１００６のオペレータ実行処理の詳細について説明する。なお、オペレータ実行処理は、生成された検索プランによってその内容が異なる。例えば、１つの情報管理装置２００でオペレータが実行される場合や、複数の情報管理装置２００間で中間結果を転送してオペレータが実行される場合などが存在しうる。
【００７３】
以下では、他の情報管理装置２００の中間結果を利用しないオペレータの場合（図１１）、中間結果を転送するオペレータの場合（図１２）、および、他の情報管理装置２００の中間結果を利用するオペレータの場合（図１３）に分けて説明する。なお、オペレータ実行処理はこの３つに限られるものではない。例えば、検索装置１００内で実行されるオペレータもありうる。
【００７４】
図１１は、他の情報管理装置２００の中間結果を利用しないオペレータについてのオペレータ実行処理の全体の流れを示すフローチャートである。
【００７５】
まず、受信部２１１が、検索装置１００からオペレータ実行情報を受信する（ステップＳ１１０１）。次に、実行部２１２が、オペレータ実行情報に従いオペレータを実行する（ステップＳ１１０２）。
【００７６】
次に、実行部２１２が、オペレータの実行結果を結果記憶部２２１に記憶する（ステップＳ１１０３）。例えば、情報管理装置２００ａの実行部２１２が、「people」データベースから「person」データを取得するオペレータを実行した場合、取得した「person」データを結果記憶部２２１に記憶する。この場合、図４に示したようなバインドテーブル４１が結果記憶部２２１に記憶される。
【００７７】
次に、対応づけ部２１３が、取得元であるデータベースを識別するための取得元情報を作成し（ステップＳ１１０４）、作成した取得元情報を中間結果と対応づけて対応記憶部２２２に記憶する（ステップＳ１１０５）。
【００７８】
上記例では、対応づけ部２１３は、取得元のデータベースである「ＤＢ１」を取得元情報としてバインドテーブル４１と対応づけた、図５のような情報を対応記憶部２２２に記憶する。
【００７９】
図１２は、中間結果を転送するオペレータについてのオペレータ実行処理の全体の流れを示すフローチャートである。
【００８０】
まず、受信部２１１が、検索装置１００から転送を要求するオペレータ実行情報を受信する（ステップＳ１２０１）。次に、結果取得部２１４が、転送すべき中間結果を取得する処理を実行する。具体的には、まず結果取得部２１４は、オペレータ実行情報内に指定された転送先となる情報管理装置２００を識別する情報を参照し、当該情報管理装置２００で管理するデータベースを取得元情報とする中間結果のバインドテーブルを識別する情報（テーブル識別情報）を対応記憶部２２２から取得する（ステップＳ１２０２）。
【００８１】
次に、結果取得部２１４は、取得したテーブル識別情報で識別される中間結果のうち、オペレータ実行情報内に指定された転送するカラムを特定する情報を参照し、転送するカラムの情報のみを含む中間結果を結果記憶部２２１から取得する（ステップＳ１２０３）。
【００８２】
これにより、必要な情報のみを取得して外部の情報管理装置２００に転送可能となるため、転送処理の負荷軽減を図り検索処理の高速化が実現できる。
【００８３】
次に、転送部２１５が、取得した中間結果と、当該中間結果に対応づけられている取得元情報とを転送先の情報管理装置２００に転送する（ステップＳ１２０４）。
【００８４】
転送先の情報管理装置２００では、受信部２１１が、中間結果と取得元情報とを受信する（ステップＳ１２０５）。そして、実行部２１２が、受信した中間結果を新たに作成し、自装置内の結果記憶部２２１に保存する（ステップＳ１２０６）。
【００８５】
なお、外部の複数の情報管理装置２００から中間結果を受信したときは、それぞれの中間結果を取得元のデータベースごとに分けて結果記憶部２２１内に保存する。例えば、情報管理装置２００ｃが、情報管理装置２００ａ、２００ｂからそれぞれ「people」データベース内の「@id」データを中間結果として受信した場合、図５に示すようにそれぞれの装置に対応する中間結果を２つのバインドテーブル５１、５２に分けて保存する。
【００８６】
次に、対応づけ部２１３が、受信した取得元情報を参照して取得元情報を新たに作成し、作成した取得元情報と、ステップＳ１２０６で作成した中間結果とを対応づけて対応記憶部２２２に保存する（ステップＳ１２０７）。
【００８７】
以上の処理により、他の情報管理装置２００における中間結果を利用するオペレータ実行の準備が整い、次に中間結果を利用するオペレータ実行の要求が検索装置１００から送信された場合にオペレータを実行することが可能となる。
【００８８】
図１３は、他の情報管理装置２００の中間結果を利用するオペレータについてのオペレータ実行処理の全体の流れを示すフローチャートである。
【００８９】
まず、受信部２１１が、検索装置１００から、中間結果を利用するオペレータのオペレータ実行情報を受信する（ステップＳ１３０１）。次に、実行部２１２が、オペレータ実行情報に従いオペレータを実行する（ステップＳ１３０２）。
【００９０】
次に、実行部２１２が、オペレータの実行結果を結果記憶部２２１に記憶する（ステップＳ１３０３）。このとき、事前に結果記憶部２２１に記憶された中間結果に、当該中間結果を利用して得られた中間結果を追加して結果記憶部２２１に記憶する。
【００９１】
次に、対応づけ部２１３が、取得元であるデータベースを識別するための取得元情報を作成し（ステップＳ１３０４）、作成した取得元情報を中間結果と対応づけて対応記憶部２２２に記憶する（ステップＳ１３０５）。
【００９２】
このように、他の情報管理装置２００の中間結果を利用するオペレータの場合は、他の情報管理装置２００から事前に受信した中間結果に、新たに実行したオペレータの実行結果を追加して中間結果を作成し、結果記憶部２２１に記憶していく。この際、取得元のデータベースが異なるごとに中間結果を分けて管理しているため、中間結果をさらに別の情報管理装置２００に転送するとき、必要な中間結果のみを抽出して転送することが可能となる。
【００９３】
次に、このように構成された検索システム１０で転送される中間結果の例について説明する。図１４は、転送される中間結果の一例を示した模式図である。同図は、情報管理装置２００ａ、ｂで「people」データベースから「@id」データを取得し、それぞれに対して情報管理装置２００ｃ、ｄで「deal」データと「item/category」データをさらに取得して、その結果を情報管理装置２００ａ、ｂにされに転送する場合の例を示している。
【００９４】
なお、同図の左上が情報管理装置２００ｃ、右上が情報管理装置２００ｄを表している。また、同図の左下が情報管理装置２００ａ、右下が情報管理装置２００ｂを表している。
【００９５】
例えば、左上の情報管理装置２００ｃでは、２つの取得元（ＤＢ１、ＤＢ２）ごとに中間結果を分けて２つのバインドテーブル１００１、１００２として管理している。このため、これらの中間結果を転送する場合、取得元情報（ＤＢ１、ＤＢ２）に従ってそれぞれ対応する情報管理装置２００ａ、２００ｂのいずれか一方に必要な中間結果のみを転送できる。
【００９６】
同様に、右上の情報管理装置２００ｄでは、２つの取得元（ＤＢ１、ＤＢ２）ごとに中間結果を分けて２つのバインドテーブル１００３、１００４として管理している。結果として、情報管理装置２００ａには、バインドテーブル１００１に対応するバインドテーブル１００５と、バインドテーブル１００３に対応するバインドテーブル１００６と、が転送される。また、情報管理装置２００ｂには、バインドテーブル１００２に対応するバインドテーブル１００７と、バインドテーブル１００４に対応するバインドテーブル１００８と、が転送される。
【００９７】
次に、上述のように構成された検索システム１０における検索処理の具体例について説明する。以下では、図１に示すように「people」データベースがＤＢ１、ＤＢ２に分割配置され、「auction」データベースがＤＢ３、ＤＢ４に分割配置された構成で、図７に示すような条件の検索要求が入力された場合の例について説明する。なお、以下では、各データベース（ＤＢ１〜ＤＢ４）を管理する情報管理装置２００（２００ａ〜２００ｄ）を、単にＤＢｎ（ｎは１〜４）という場合がある。
【００９８】
まず、「people」データベースを対象として住所が「Kawasaki」（address/text（）=「Kawasaki」）のpersonの検索を行い、得られた結果を中間結果として格納する。このときの処理は以下のようになる。
【００９９】
「people」データベースはＤＢ１とＤＢ２に分割して格納されているので、決定部１０３はＤＢ１、ＤＢ２のそれぞれのデータベースの上で「people」データベースを対象として住所が「Kawasaki」（address/text（）="Kawasaki"）である「person」データの検索を行うオペレータ実行情報を生成する（ステップＳ１００４）。
【０１００】
要求送信部１０４は生成されたオペレータ実行情報を受け取り、ＤＢ１、ＤＢ２のそれぞれのデータベースにオペレータ実行情報を送信する（ステップＳ１００５）。オペレータ実行情報を受信したＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。
【０１０１】
図１５〜図１８は、この例の検索処理で生成される中間結果の一例を示す説明図である。各図の上下方向に、処理の流れに従い生成される中間結果のバインドテーブルと取得元情報とが示されている。各図の横方向には、２つの論理データベース「people」、「auction」と、それらを水平分割したデータベースであるＤＢ１〜ＤＢ４とが示されている。各データベースの下部に示された中間結果が、当該データベースを取得元とする中間結果であることを意味する。
【０１０２】
最初の処理では、ＤＢ１、ＤＢ２それぞれのデータベース上の中間結果として得られた「person」データは、それぞれＢＴ１０１およびＢＴ１０２で識別されるバインドテーブルに記憶され、取得元情報としてＤＢ１およびＤＢ２がそれぞれ対応づけられて対応記憶部２２２に記憶される。
【０１０３】
次に、得られた「person」データに関してその名前（name/text（））をデータベースより取得し、得られた結果を中間結果として格納する。このときの処理は以下のようになる。
【０１０４】
まず、決定部１０３は、ＤＢ１、ＤＢ２それぞれで得られている「person」データに関し、「name/text（）」の取得処理をＤＢ１、ＤＢ２それぞれのデータベースの上で実行するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、ＤＢ１、ＤＢ２のそれぞれのデータベースにオペレータ実行情報を送信する（ステップＳ１００５）。
【０１０５】
オペレータ実行情報を受信したＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。この処理では、ＤＢ１、ＤＢ２それぞれのデータベース上の中間結果として得られた「name/text（）」は、ＢＴ１０１およびＢＴ１０２のバインドテーブルに追加され、それぞれＢＴ１０３およびＢＴ１０４のバインドテーブルが作成される。
【０１０６】
次に、得られた「person」データに関してその「id（@id）」データをデータベースより取得し、得られた結果を中間結果として格納する。このときの処理は以下のようになる。
【０１０７】
まず、決定部１０３は、ＤＢ１、ＤＢ２それぞれで得られている「person」データに関し、「@id」データの取得処理をＤＢ１、ＤＢ２それぞれのデータベースの上で実行するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、ＤＢ１、ＤＢ２のそれぞれのデータベースにオペレータ実行情報を送信する（ステップＳ１００５）。
【０１０８】
オペレータ実行情報を受信したＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。この処理では、ＤＢ１、ＤＢ２それぞれのデータベース上の中間結果として得られた「@id」は、ＢＴ１０３およびＢＴ１０４のバインドテーブルに追加され、それぞれＢＴ１０５およびＢＴ１０６のバインドテーブルが作成される。
【０１０９】
ここまでの処理は「people」データベースに閉じた処理であり、中間結果のすべてのカラムはＤＢ１、ＤＢ２のいずれかで閉じている。
【０１１０】
次に、ここまででＤＢ１、ＤＢ２上で得られている「@id」データをキーとして、その値と一致する属性（@buyer）を有する取引情報（deal）の検索を行う。このときの処理は以下のようになる。
【０１１１】
まず、「auction」データベースがＤＢ３、ＤＢ４に格納されているため、決定部１０３はＤＢ１、ＤＢ２の中間結果に保持されているキー情報（@id）をＤＢ３、ＤＢ４に転送するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、転送処理を実行するＤＢ１、ＤＢ２のそれぞれのデータベースにオペレータ実行情報を送信する（ステップＳ１００５）。
【０１１２】
オペレータ実行情報を受信したＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当する転送処理を実行し、中間結果と取得元情報をＤＢ３、ＤＢ４へ転送する（ステップＳ１２０４）。ＤＢ１とＤＢ２のそれぞれは、ＤＢ１とＤＢ２の中間結果のうち後の処理に使用する「@id」カラムのみを、ＤＢ３とＤＢ４のそれぞれへ転送する。
【０１１３】
転送先であるＤＢ３とＤＢ４のそれぞれのデータベース上の実行部２１２は、転送された中間結果を受け取り、中間結果を組み立てる（ステップＳ１２０６）。この際、得られた中間結果それぞれに関して、取得元情報も同時に受け取り、中間結果の取得元情報を対応付けて記録する（ステップＳ１２０７）。
【０１１４】
すなわち、ＤＢ１、ＤＢ２それぞれのデータベースから転送された中間結果である「@id」データは、取得元ごとに区別して管理される。例えば、図１６に示すように、ＤＢ３上では、ＢＴ２０１およびＢＴ２０２のバインドテーブルが作成される。また、ＤＢ４上では、ＢＴ２０３およびＢＴ２０４のバインドテーブルが作成される。
【０１１５】
このように、転送された中間結果を受け取ったＤＢ３とＤＢ４とのそれぞれでは、ＤＢ１とＤＢ２のそれぞれから得られた中間結果を区別して管理し、中間結果のそれぞれのカラムの値がいずれのデータベースから得られたものであるかを知ることが可能となる。
【０１１６】
次に、ＤＢ３、ＤＢ４それぞれについて「@id」の値に一致する「@buyer」属性を持つ「deal」データを検索する。このときの処理は以下のようになる。
【０１１７】
決定部１０３は、ＤＢ３、ＤＢ４のそれぞれで格納されている中間結果の「@id」をキーとして、ＤＢ３、ＤＢ４それぞれのデータベースに関して、「@id」と一致する「@buyer」を有する「deal」データの検索を行うオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、ＤＢ３、ＤＢ４のそれぞれのデータベース対してオペレータ実行情報を送信する（ステップＳ１００５）。
【０１１８】
オペレータ実行情報を受信したＤＢ３、ＤＢ４のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。実行部２１２および対応づけ部２１３は、このとき得られた「deal」データに関して取得元情報を作成し、既存の中間結果および取得元情報に追加する（ステップＳ１３０３〜ステップＳ１３０５）。
【０１１９】
これにより、ＤＢ３に関しては、ＤＢ１から得られた「@id」と、ＤＢ３から得られた「deal」データを有する中間結果（ＢＴ２０５）と、ＤＢ２から得られた「@id」とＤＢ３から得られた「deal」データを有する中間結果（ＢＴ２０６）とがそれぞれ区別して管理される。ＤＢ４に関しても同様に、ＢＴ２０７とＢＴ２０８とで中間結果が区別して管理される。
【０１２０】
次に、ＤＢ３、ＤＢ４のそれぞれについて、後の処理で使用する「item/@category」の値をデータベースより取得する。このときの処理は以下のようになる。
【０１２１】
決定部１０３は、ＤＢ３、ＤＢ４のそれぞれで格納されている中間結果の「deal」を基点として、ＤＢ３、ＤＢ４それぞれのデータベースに関して、「item/@category」の取得を行うオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、オペレータが実行されるＤＢ３、ＤＢ４のそれぞれにオペレータ実行情報を送信する（ステップＳ１００５）。
【０１２２】
オペレータ実行情報を受信したＤＢ３、ＤＢ４のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。また、実行部２１２および対応づけ部２１３は、このとき得られた「item/@category」に関して取得元情報を作成し、既存の中間結果および取得元情報に追加する。
【０１２３】
次に、ＤＢ３、ＤＢ４で得られている中間結果のitem/@categoryに一致する「watch/@category」を有する「person」データを選択する。このときの処理は以下のようになる。
【０１２４】
まず、「people」データベースがＤＢ１、ＤＢ２に格納されているため、決定部１０３は、ＤＢ３、ＤＢ４の中間結果に保持されているキー情報（item/@category）を、ＤＢ１、ＤＢ２に転送するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は生成されたオペレータ実行情報を受け取り、ＤＢ３、ＤＢ４のそれぞれのデータベース対してオペレータ実行情報を送信する（ステップＳ１００５）。
【０１２５】
オペレータ実行情報を受信したＤＢ３、ＤＢ４のそれぞれのデータベース上の実行部２１２は、該当する中間結果を転送する処理を実行し、中間結果をＤＢ１、ＤＢ２に転送する（ステップＳ１２０４）。このとき、ＤＢ３とＤＢ４のそれぞれは、ＤＢ３とＤＢ４で得られている中間結果のうち、ＤＢ１、ＤＢ２のそれぞれで処理の継続可能な中間結果を、対応記憶部２２２を参照して結果記憶部２２１から取得し、取得した有効な中間結果のみをそれぞれ対応するデータベースへ転送する。
【０１２６】
すなわち、ＤＢ３、ＤＢ４のそれぞれで得られている中間結果のうち、後の処理で参照する「person」データが、ＤＢ１、ＤＢ２のいずれから求められた中間結果であるかを取得元情報から決定し、ＤＢ１に対してはＤＢ１から求められた部分が、ＤＢ２に対してはＤＢ２から求められた部分が、それぞれに有効な中間結果となる。このようにして取得元情報を用いて区分管理されている中間結果を区分単位で転送することにより、無駄な転送を排除することが可能となる。
【０１２７】
次に、転送先であるＤＢ１とＤＢ２のデータベース上の実行部２１２は、転送された中間結果を受け取り、転送された中間結果をもとに同じ中間結果を作成する（ステップＳ１２０６）。この際、得られた中間結果それぞれに関して、取得元情報も同時に受け取り、中間結果の取得元情報を対応付けて記録する（ステップＳ１２０７）。
【０１２８】
すなわち、ＤＢ３、ＤＢ４それぞれのデータベースから転送された中間結果は、取得元ごとに区別して管理される。例えば、図１７に示すように、ＤＢ１上では、ＤＢ３上のＢＴ２０９に対応するＢＴ２１３およびＤＢ４上のＢＴ２１１に対応するＢＴ２１４が作成される。また、ＤＢ２上では、ＤＢ３上のＢＴ２１０に対応するＢＴ２１５およびＤＢ４上のＢＴ２１２に対応するＢＴ２１６が作成される。
【０１２９】
このように、転送された中間結果を受け取ったＤＢ１とＤＢ２のそれぞれでは、ＤＢ３とＤＢ４、およびそれ以前にＤＢ１とＤＢ２のそれぞれから得られた中間結果を区別して管理し、中間結果のそれぞれのカラムの値が、いずれのデータベースから得られたものであるかを知ることが可能となる。
【０１３０】
次に、決定部１０３は、別々に演算された結果を一つに統合するために、ＤＢ１とＤＢ２のそれぞれのデータベースで、自身で管理している中間結果と、転送により得られた転送結果を結合（Join）するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は、オペレータ実行情報を受け取り、オペレータを実行するＤＢ１、ＤＢ２のそれぞれに対してオペレータ実行情報を転送する（ステップＳ１００５）。
【０１３１】
転送されたオペレータ実行情報を受け取ったＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を格納する。この結果、ＤＢ１上では、図１５のＢＴ１０５と、図１７のＢＴ２１３およびＢＴ２１４とをそれぞれ統合したＢＴ２１７とＢＴ２１８とが作成される。また、ＤＢ２上では、図１５のＢＴ１０６と、図１７のＢＴ２１５およびＢＴ２１６とをそれぞれ統合したＢＴ２１９とＢＴ２２０とが作成される。
【０１３２】
この際、統合した結果として得られた中間結果の各カラムに関する取得元情報も、それぞれの中間結果に関する取得元情報からカラムごとに抽出しひとつに統合する。
【０１３３】
次に、ＤＢ１とＤＢ２のそれぞれのデータベースで、中間結果の「person」データに関して、中間結果の「item/@category」の値と一致する属性（watch/@category）値を有するものを抽出し、得られた結果を中間結果に反映する。この処理は以下のようになる。
【０１３４】
処理を行うＤＢ１、ＤＢ２のそれぞれのデータベース上にオペレータの実行に必要な中間結果が存在するので、決定部１０３は、ＤＢ１、ＤＢ２のそれぞれに対して、中間結果の「item/@category」の値と一致する属性（watch/@category）値を有する「person」データを抽出するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は、オペレータ実行情報を受け取り、オペレータを実行するＤＢ１、ＤＢ２のそれぞれに対してオペレータ実行情報を転送する（ステップＳ１００５）。
【０１３５】
転送されたオペレータ実行情報を受け取ったＤＢ１、ＤＢ２のそれぞれのデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を格納する。この処理では、ＤＢ１、ＤＢ２それぞれのデータベース上の中間結果として抽出された「person」データは、図１８のＢＴ２２１、ＢＴ２２２、ＢＴ２２３、およびＢＴ２２４のバインドテーブルに格納される。
【０１３６】
なお、この処理で得られた「person」データはＤＢ１、ＤＢ２それぞれのデータベースから得られたデータであるので取得元情報は変化しない。
【０１３７】
次に、「auction」データベースに対して、「deal/name/text（）」を取得する処理を行う。この処理は以下のように行われる。
【０１３８】
処理を行うＤＢ３、ＤＢ４では、取得する際の元となる「deal」データを示す中間結果が存在しないため、決定部１０３は、ＤＢ１とＤＢ２で得られている中間結果のうち、「deal」データのみをＤＢ３、ＤＢ４へ転送するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４はオペレータ実行するＤＢ１、ＤＢ２に対してオペレータ実行情報を転送する（ステップＳ１００５）。
【０１３９】
オペレータ実行情報を受信したＤＢ１、ＤＢ２のデータベース上の実行部２１２は転送部２１５に該当する転送処理を実行させる。このとき、ＤＢ１は、ＤＢ１で得られている中間結果のうち、後の処理で使用する「deal」データがＤＢ３から求められた中間結果を取得元情報から決定し、ＤＢ３へ転送する。同様にＤＢ１で得られている中間結果のうち、後の処理で使用するdealがＤＢ４から求められた中間結果を取得元情報から決定し、ＤＢ４へ転送する。ＤＢ２についても同様である。
【０１４０】
このように、取得元情報を用いて区分管理されている中間結果を区分単位で転送することにより、無駄な転送を排除することが可能となる。
【０１４１】
転送された中間結果を受信したＤＢ３、ＤＢ４のデータベース上の実行部２１２は、受信した中間結果を復元する（ステップＳ１２０６）。この際、得られた中間結果それぞれに関して、取得元情報も同時に受け取り、中間結果の取得元情報を対応付けて記録する（ステップＳ１２０７）。
【０１４２】
すなわち、ＤＢ１、ＤＢ２それぞれのデータベースから転送された中間結果は、取得元ごとに区別して管理される。例えば、図１８に示すように、ＤＢ３上では、ＤＢ１上のＢＴ２２１に対応するＢＴ２２５およびＤＢ２上のＢＴ２２３に対応するＢＴ２２６が作成される。また、ＤＢ４上では、ＤＢ１上のＢＴ２２２に対応するＢＴ２２７およびＤＢ２上のＢＴ２２４に対応するＢＴ２２８が作成される。
【０１４３】
このように、転送された中間結果を受け取ったＤＢ３とＤＢ４のそれぞれでは、ＤＢ１とＤＢ２、およびそれ以前にＤＢ３とＤＢ４のそれぞれから得られた中間結果を区別して管理し、中間結果のそれぞれのカラムの値が、いずれのデータベースから得られたものであるかを知ることが可能となる。
【０１４４】
次に、中間結果で得られている「deal」データに関して、その「item/name/text（）」の値を取得する。この処理は以下のようになる。
【０１４５】
決定部１０３は、ＤＢ３とＤＢ４で、中間結果で得られている「deal」データに関して、その「item/name/text（）」の値を取得するオペレータ実行情報を生成する（ステップＳ１００４）。要求送信部１０４は、生成されたオペレータ情報を受け取り、オペレータを実行するＤＢ３、ＤＢ４に対して送信する（ステップＳ１００５）。
【０１４６】
オペレータ実行情報を受信したＤＢ３、ＤＢ４のデータベース上の実行部２１２は、該当するオペレータを実行して中間結果を作成する。この処理では、ＤＢ３、ＤＢ４それぞれのデータベース上の中間結果として得られた「item/name/text（）」は、ＢＴ２２５〜ＢＴ２２８のバインドテーブルに追加され、それぞれＢＴ２２９〜ＢＴ２３２のバインドテーブルが作成される。
【０１４７】
以上の処理により、分割して格納されたデータベースから検索式に従い横断的に検索を実行でき、最終的に図８に示すような「person/name/text（）」、「person」、および「deal/item/name」のカラムからなる情報の列として検索結果を取得することができる。
【０１４８】
このように、本実施の形態にかかる検索システムでは、中間結果の取得元となったデータベースを特定する情報を中間結果に対応づけ、この情報を参照して、中間結果のうち転送して処理の対象となりえる部分のみを転送することができる。このため、データ登録に先立ち事前に設計する必要のある特定のハッシュ関数などを用いることなく、無駄な通信コストの削減を実現できる。また、この結果、分散データベースシステムにおける検索処理の高速化が可能となる。さらに、転送コストの削減とデータベース運用時におけるデータ分割の変更の容易さを両立させることができる。
【０１４９】
図１９は、本実施の形態にかかる情報管理装置のハードウェア構成を示す説明図である。
【０１５０】
本実施の形態にかかる情報管理装置は、ＣＰＵ５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、ＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）ドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置と、各部を接続するバス５５を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０１５１】
本実施の形態にかかる情報管理装置で実行される情報管理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１５２】
また、本実施の形態にかかる情報管理装置で実行される情報管理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施の形態にかかる情報管理装置で実行される情報管理プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１５３】
また、本実施の形態の情報管理プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１５４】
本実施の形態にかかる情報管理装置で実行される情報管理プログラムは、上述した各部（受信部、実行部、対応づけ部、結果取得部、転送部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１（プロセッサ）が上記記憶媒体から情報管理プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上述した各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０１５５】
以上のように、本発明にかかる検索システム、検索方法、および情報管理装置は、ＸＭＬなどの構造化文書を複数の装置に水平分散配置して管理するシステムに適している。
【図面の簡単な説明】
【０１５６】
【図１】本実施の形態にかかる検索システムの構成を示すブロック図である。
【図２】「people」データベースに登録されるデータのデータ構造の一例を示す説明図である。
【図３】「auction」データベースに登録されるデータのデータ構造の一例を示す説明図である。
【図４】結果記憶部および対応記憶部のデータ構造の一例を示す説明図である。
【図５】結果記憶部および対応記憶部のデータ構造の別の例を示す説明図である。
【図６】結果記憶部および対応記憶部のデータ構造の別の例を示す説明図である。
【図７】検索要求の一例を示す説明図である。
【図８】検索結果の出力形式の一例を示す説明図である。
【図９】処理部の詳細な構成を示すブロック図である。
【図１０】本実施の形態における検索処理の全体の流れを示すフローチャートである。
【図１１】オペレータ実行処理の全体の流れを示すフローチャートである。
【図１２】オペレータ実行処理の全体の流れを示すフローチャートである。
【図１３】オペレータ実行処理の全体の流れを示すフローチャートである。
【図１４】転送される中間結果の一例を示した模式図である。
【図１５】中間結果の一例を示す説明図である。
【図１６】中間結果の一例を示す説明図である。
【図１７】中間結果の一例を示す説明図である。
【図１８】中間結果の一例を示す説明図である。
【図１９】本実施の形態にかかる情報管理装置のハードウェア構成を示す説明図である。
【符号の説明】
【０１５７】
５１  ＣＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５４  通信Ｉ／Ｆ
５５  バス
１０  検索システム
１００  検索装置
１０１  受付部
１０２  プラン生成部
１０３  決定部
１０４  要求送信部
１０５  結果受信部
１０６  結果生成部
１０７  結果送信部
２００  情報管理装置
２１０  処理部
２１１  受信部
２１２  実行部
２１３  対応づけ部
２１４  結果取得部
２１５  転送部
２２１  結果記憶部
２２２  対応記憶部
２３１  情報記憶部
３００  ネットワーク
４００  クライアント
４１  バインドテーブル
５１、５２  バインドテーブル
６１、６２  バインドテーブル
１００１、１００２、１００３、１００４、１００５、１００６、１００７、１００８  バインドテーブル
【図１】
2008084134.tif 000003
【図２】
2008084134.tif 000004
【図３】
2008084134.tif 000005
【図４】
2008084134.tif 000006
【図５】
2008084134.tif 000007
【図６】
2008084134.tif 000008
【図７】
2008084134.tif 000009
【図８】
2008084134.tif 000010
【図９】
2008084134.tif 000011
【図１０】
2008084134.tif 000012
【図１１】
2008084134.tif 000013
【図１２】
2008084134.tif 000014
【図１３】
2008084134.tif 000015
【図１４】
2008084134.tif 000016
【図１５】
2008084134.tif 000017
【図１６】
2008084134.tif 000018
【図１７】
2008084134.tif 000019
【図１８】
2008084134.tif 000020
【図１９】
2008084134.tif 000021