(57)【要約】【課題】シーケンスに関する処理負担を軽減する分散ＤＢ検索システムを提供する。【解決手段】取得すべき項目のデータ構造と項目が満たすべき条件の種類と局所性情報とを対応づけて記憶する局所性判定テーブル１２３と、検索プランを生成するプラン生成部１０２と、シーケンスとして得られる項目のデータ構造および条件の種類に対応する局所性情報を局所性判定テーブル１２３から取得し、項目がデータベースに分散して格納されているか否かを判定する判定部１０４と、分散して格納されていない場合に、論理シーケンスの生成要求を削除して検索プランを更新する更新部１０３と、検索プラン実行要求をスレーブノード２００に対して通知する実行要求部１０５とを備えたマスタノード１００と、実行要求を受付ける実行要求受付部２０１と、検索プランを実行する実行部２０２と、を備えたスレーブノード２００を備えた。【選択図】        図１０
2008243078.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの項目からなる複数の情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置から前記情報を検索する検索装置とがネットワークを介して接続された検索システムであって、
前記検索装置は、
前記項目が満たすべき条件を含む検索要求を受付ける検索要求受付部と、
前記項目に関連する前記データベースのデータ構造と、前記条件の種類と、取得すべき前記項目をリスト構造で表したシーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを表す局所性情報とを対応づけて記憶する局所性記憶部と、
受付けられた検索要求を解析し、前記シーケンス情報の取得要求、および複数の前記データベースから取得された前記シーケンス情報を統合した論理シーケンスの生成要求を含む前記データベースに対する処理要求である検索プランを生成するプラン生成部と、
前記シーケンス情報として得られる前記項目のそれぞれについて、項目に関連する前記データベースのデータ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定する判定部と、
前記項目が複数の前記データベースに分散して格納されていないと判定された場合に、前記論理シーケンスの前記生成要求を削除して前記検索プランを更新する更新部と、
更新された前記検索プランの実行要求を前記情報管理装置に対して通知する実行要求部と、を備え、
前記情報管理装置は、
前記データベースと、
前記実行要求を前記検索装置から受付ける実行要求受付部と、
受付けた前記実行要求に基づいて、前記データベースに対して前記検索プランを実行する実行部と、
を備えたことを特徴とする検索システム。
【請求項２】
前記判定部は、さらに、前記検索要求を解析し、前記シーケンス情報のそれぞれについて、前記シーケンス情報が前記検索要求に対する検索結果として出力されるか否かを判定し、
前記更新部は、さらに、前記シーケンス情報が前記検索結果として出力されないと判定された場合に、前記検索結果として出力されないと判定された前記シーケンス情報を統合した前記論理シーケンスの前記生成要求を削除して前記検索プランを更新すること、
を特徴とする請求項１に記載の検索システム。
【請求項３】
前記項目と、前記項目が前記データベース内で一意の値を取るか否かを表す一意性情報とを対応づけて記憶する一意性記憶部と、
前記情報を前記データベースに分散して格納するときの判断基準とする前記項目を定めた分割情報を記憶する分割情報記憶部と、をさらに備え、
前記局所性記憶部は、前記一意性情報と前記分割情報とを含む前記データ構造と、前記条件の種類と、前記局所性情報とを対応づけて記憶し、
前記判定部は、前記シーケンス情報として得られる前記項目のそれぞれについて、項目に対応する前記一意性情報を前記一意性記憶部から取得し、項目に対応する前記分割情報を前記分割情報記憶部から取得し、取得した前記一意性情報と取得した前記分割情報とを含む前記データ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定すること、
を特徴とする請求項１に記載の検索システム。
【請求項４】
前記局所性記憶部は、前記項目が前記データベース内で一意の値を取らないことを表す前記一意性情報と、前記シーケンス情報として得られる前記項目が前記判断基準とする前記項目でないことを表す前記分割情報と、を含む前記データ構造に対して、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されていることを表す前記局所性情報を対応づけて記憶すること、
を特徴とする請求項３に記載の検索システム。
【請求項５】
前記局所性記憶部は、前記項目が前記データベース内で一意の値を取ることを表す前記一意性情報を含む前記データ構造と、前記条件として前記シーケンス情報以外が指定されていること表す前記条件の種類とに対して、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されていないことを表す前記局所性情報を対応づけて記憶すること、
を特徴とする請求項３に記載の検索システム。
【請求項６】
前記局所性記憶部は、前記シーケンス情報として得られる前記項目が前記判断基準とする前記項目であることを表す前記分割情報を含む前記データ構造と、前記条件として前記シーケンス情報以外が指定されていること表す前記条件の種類とに対して、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されていないことを表す前記局所性情報を対応づけて記憶すること、
を特徴とする請求項３に記載の検索システム。
【請求項７】
前記局所性記憶部は、前記シーケンス情報として得られる前記項目が前記判断基準とする前記項目でないことを表す前記分割情報を含む前記データ構造と、前記条件として前記シーケンス情報が指定されていること表す前記条件の種類とに対して、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されていることを表す前記局所性情報を対応づけて記憶すること、
を特徴とする請求項３に記載の検索システム。
【請求項８】
少なくとも１つの項目からなる複数の情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置から前記情報を検索する検索装置とがネットワークを介して接続された検索システムにおける検索方法であって、
前記検索装置は、前記項目に関連する前記データベースのデータ構造と、検索要求内で前記項目が満たすべき条件の種類と、取得すべき前記項目をリスト構造で表したシーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを表す局所性情報とを対応づけて記憶する局所性記憶部を備え、
前記検索装置によって、前記検索要求を受付ける検索要求受付ステップと、
前記検索装置によって、受付けられた検索要求を解析し、前記シーケンス情報の取得要求、および複数の前記データベースから取得された前記シーケンス情報を統合した論理シーケンスの生成要求を含む前記データベースに対する処理要求である検索プランを生成するプラン生成ステップと、
前記検索装置によって、前記シーケンス情報として得られる前記項目のそれぞれについて、項目に関連する前記データベースのデータ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定する判定ステップと、
前記検索装置によって、前記項目が複数の前記データベースに分散して格納されていないと判定された場合に、前記論理シーケンス情報の前記生成要求を削除して前記検索プランを更新する更新ステップと、
前記検索装置によって、更新された前記検索プランの実行要求を前記情報管理装置に対して通知する実行要求ステップと、
前記情報管理装置によって、前記実行要求を前記検索装置から受付ける実行要求受付ステップと、
前記情報管理装置によって、受付けた前記実行要求に基づいて、前記データベースに対して前記検索プランを実行する実行ステップと、
を備えたことを特徴とする検索方法。
【請求項９】
少なくとも１つの項目からなる複数の情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置にネットワークを介して接続され、前記情報管理装置から前記情報を検索する検索装置であって、
前記項目が満たすべき条件を含む検索要求を受付ける検索要求受付部と、
前記項目に関連する前記データベースのデータ構造と、前記条件の種類と、取得すべき前記項目をリスト構造で表したシーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを表す局所性情報とを対応づけて記憶する局所性記憶部と、
受付けられた検索要求を解析し、前記シーケンス情報の取得要求、および複数の前記データベースから取得された前記シーケンス情報を統合した論理シーケンスの生成要求を含む前記データベースに対する処理要求である検索プランを生成するプラン生成部と、
前記シーケンス情報として得られる前記項目のそれぞれについて、項目に関連する前記データベースのデータ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定する判定部と、
前記項目が複数の前記データベースに分散して格納されていないと判定された場合に、前記論理シーケンス情報の前記生成要求を削除して前記検索プランを更新する更新部と、
更新された前記検索プランの実行要求を前記情報管理装置に対して通知する実行要求部と、
を備えたことを特徴とする検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、多数の件数からなるデータを所定件数ごとの複数の塊に分割し、塊ごとにネットワーク接続された複数のデータベースに登録し処理する水平分割された分散データベースで、与えられた検索条件に従い分散検索を行うシステム、装置、および方法に関するものである。
【背景技術】
【０００２】
近年、ＸＭＬ（eXtensible Markup Language）などで記述された構造化文書情報を記憶・検索する構造化文書データベースが実現されている。構造化文書データベースに対する問合せは、Ｗ３Ｃ（World Wide Web Consortium）が標準化を進めているＸＱｕｅｒｙ（XML Query）という問合せ言語によって行われることが主流となっている。
【０００３】
テーブル形式によるデータ管理を目的としたＲＤＢ（Relational Database）の標準検索言語であるＳＱＬ（Structured Query Language）とは異なり、ＸＭＬデータを対象としたＸＱｕｅｒｙによる検索処理では、リスト状のデータ構造であるシーケンスデータを中間結果として取り扱う必要がある。
【０００４】
一方、多数の件数からなるデータを、例えば件数が均等となるように複数の塊に分割し、分割した塊ごとにネットワーク接続された複数のデータベースに登録して処理する水平分割型の分散データベースシステムが広く知られている。このような分散データベースシステムでＸＱｕｅｒｙによる検索処理を行った場合、中間結果であるシーケンスデータが、分割された複数のデータベース（物理ＤＢ）に部分結果（部分シーケンス）として散在しうる。そこで、これら部分シーケンスを論理的に統合したシーケンスである論理シーケンスとして扱う手段が必要となる。
【０００５】
オブジェクトデータベースに関しては、このような複数の部分シーケンスからなる論理シーケンスの構造と類似した構造を管理する技術が知られている（例えば、特許文献１）。この技術では、個別に存在する部分集合にＩＤを割り当て、割り当てたＩＤからなる集合を作成し、作成した集合に割当てたＩＤによって階層的な集合を含む集合を表現するような管理情報を作成して上記構造を管理する。
【０００６】
【特許文献１】特許第２８２７５６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１のような方法により論理シーケンスを管理する場合、シーケンスの作成、参照などのシーケンスに関する一般的な操作を行う際には、必ず管理情報を参照する必要がある。すなわち、単体のデータベースで実行した場合には不要な、部分シーケンスに関する処理のオーバヘッドが発生するという問題があった。
【０００８】
本発明は、上記に鑑みてなされたものであって、分散データベースの検索で発生しうるシーケンスに関する処理負担を軽減することができるシステム、装置、および方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明は、少なくとも１つの項目からなる複数の情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置と、前記情報管理装置から前記情報を検索する検索装置とがネットワークを介して接続された検索システムであって、前記検索装置は、前記項目が満たすべき条件を含む検索要求を受付ける検索要求受付部と、前記項目に関連する前記データベースのデータ構造と、前記条件の種類と、取得すべき前記項目をリスト構造で表したシーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを表す局所性情報とを対応づけて記憶する局所性記憶部と、受付けられた検索要求を解析し、前記シーケンス情報の取得要求、および複数の前記データベースから取得された前記シーケンス情報を統合した論理シーケンスの生成要求を含む前記データベースに対する処理要求である検索プランを生成するプラン生成部と、前記シーケンス情報として得られる前記項目のそれぞれについて、項目に関連する前記データベースのデータ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定する判定部と、前記項目が複数の前記データベースに分散して格納されていないと判定された場合に、前記論理シーケンスの前記生成要求を削除して前記検索プランを更新する更新部と、更新された前記検索プランの実行要求を前記情報管理装置に対して通知する実行要求部と、を備え、前記情報管理装置は、前記データベースと、前記実行要求を前記検索装置から受付ける実行要求受付部と、受付けた前記実行要求に基づいて、前記データベースに対して前記検索プランを実行する実行部と、を備えたことを特徴とする。
【００１０】
また、本発明は、上記システムを実行することができる方法である。
【００１１】
また、本発明は、少なくとも１つの項目からなる複数の情報を分散して格納する複数のデータベースを、前記データベースごとに管理する複数の情報管理装置にネットワークを介して接続され、前記情報管理装置から前記情報を検索する検索装置であって、前記項目が満たすべき条件を含む検索要求を受付ける検索要求受付部と、前記項目に関連する前記データベースのデータ構造と、前記条件の種類と、取得すべき前記項目をリスト構造で表したシーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを表す局所性情報とを対応づけて記憶する局所性記憶部と、受付けられた検索要求を解析し、前記シーケンス情報の取得要求、および複数の前記データベースから取得された前記シーケンス情報を統合した論理シーケンスの生成要求を含む前記データベースに対する処理要求である検索プランを生成するプラン生成部と、前記シーケンス情報として得られる前記項目のそれぞれについて、項目に関連する前記データベースのデータ構造と、項目が満たすべき前記条件の種類とに対応する前記局所性情報を前記局所性記憶部から取得し、取得した前記局所性情報から、前記シーケンス情報として得られる前記項目が前記データベースに分散して格納されているか否かを判定する判定部と、前記項目が複数の前記データベースに分散して格納されていないと判定された場合に、前記論理シーケンス情報の前記生成要求を削除して前記検索プランを更新する更新部と、更新された前記検索プランの実行要求を前記情報管理装置に対して通知する実行要求部と、を備えたことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、分散データベースの検索で発生しうるシーケンスに関する処理負担を軽減することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１３】
以下に添付図面を参照して、この発明にかかる分散データベースから情報を検索するシステム、装置、および方法の最良な実施の形態を詳細に説明する。
【００１４】
本実施の形態にかかる検索システムは、分散データベースの検索過程で得られたシーケンスが物理ＤＢの１つに局所的に格納されているか、および検索結果として出力されるかを判定し、いずれかを満たす場合に、論理シーケンスを構成する処理を不要とするように検索プランを最適化するものである。
【００１５】
まず、分散データベースの検索処理で扱われるシーケンスの表現形式について図１から図４を用いて説明する。図１は、本実施の形態の検索システムの構成の一例を示す説明図である。図１に示すように、検索システムは、クライアント３００と、マスタノード１００と、複数のスレーブノードとを含んでいる。
【００１６】
クライアント３００は、スレーブノードに格納された情報の検索要求をマスタノード１００に送信するものであり、通常のＰＣ（Personal Computer）などにより構成される。
【００１７】
マスタノード１００は、クライアント３００の検索要求を受け付けて、スレーブノードから情報を検索する検索装置である。マスタノード１００の詳細については後述する。
【００１８】
スレーブノードは、データを水平分割して記憶するデータベースを分散して管理し、マスタノード１００からの要求に応じてデータ検索を行い、検索結果をマスタノード１００に返信する情報管理装置である。図１では、５つのスレーブノードの各物理ＤＢによって、１つの論理ＤＢ４１が構成された例が示されているが、論理ＤＢの構成はこれに限られるものではない。また、複数の論理ＤＢを備えるように検索システムを構成してもよい。
【００１９】
なお、マスタノード１００と、スレーブノードと、クライアント３００とを接続するネットワークは、インターネットやＶＰＮなどのあらゆるネットワーク形態により構成することができる。
【００２０】
図２は、入力される検索式の一例を示す説明図である。図２の検索式は、ＸＱｕｅｒｙの形式で記載された検索要求を表している。なお、同図の検索式は、図１の論理ＤＢ４１はユーザ情報を格納したデータベース「people」であること、および、論理ＤＢ４１の他に、図１に図示していないオークションに関する情報を格納した論理ＤＢ「auctions」が存在することを前提としている。
【００２１】
図３は、図２のような検索式により検索処理を行ったときに得られるシーケンスの表現形式の一例を示す説明図である。図３では、物理ＤＢ−１、物理ＤＢ−２、物理ＤＢ−３には、それぞれａ１ｎ、ａ２ｎ、ａ３ｎ（ｎは整数）で識別されるユーザのデータ（ｐｅｒｓｏｎ）が格納されていることが示されている。
【００２２】
このような構成では、論理ＤＢに対しては１つのシーケンスで表される中間結果が、複数の物理ＤＢに散在する部分シーケンスそれぞれに対応する場合が発生しうる。例えば、同図では、シーケンスＩＤ＝ｓ１に対応するシーケンスである「ａ１１、ａ１５、ａ２１、ａ３２」は、物理ＤＢ−１のシーケンス「ａ１１、ａ１５」（シーケンスＩＤ＝ｓ１１）、物理ＤＢ−２のシーケンス「ａ２１」（シーケンスＩＤ＝ｓ２１）、および物理ＤＢ−３のシーケンス「ａ３２」（シーケンスＩＤ＝ｓ３１）を統合したものであることが示されている。
【００２３】
このような場合、通常は、散在するシーケンスを１つの論理シーケンスとして扱うための管理情報（以下、論理シーケンス管理情報という。）を生成する必要がある。図４は、論理シーケンスを扱うための論理シーケンス管理情報の一例を示す説明図である。図４では、各物理ＤＢでのシーケンスＩＤと論理シーケンスＩＤとを対応づけた論理シーケンス管理情報の例が示されている。このような論理シーケンス管理情報により、例えば、シーケンスＩＤ＝ｓ１１、ｓ２１、ｓ３１に対応するシーケンスは独立して扱わずに、シーケンスＩＤ＝ｓ１で識別される１つのシーケンスとして扱うことを指定できる。
【００２４】
このように、分散データベースに対して、検索結果からリスト状のデータ構造（シーケンス）を構成するような検索条件を処理させる場合、一般的には、分散データベースを構成する各スレーブノード上に断片的な結果が散在して得られる。このような場合、散在する結果のリスト状データのうち、論理的には一体となるリスト状データ同士からなる組合せ情報を管理し、論理的なリスト状データを構成して処理する必要がある。
【００２５】
しかし、このような取り扱いを回避可能な状況も存在する。そこで、本実施の形態では、与えられた検索条件とスキーマ情報とＤＢ分割情報とから上記のような取り扱いの要否を判定し、検索プランの最適化を行う。これにより分散データベース環境で、検索結果データがリスト状のデータ構造をもつ場合の処理オーバヘッドを回避することが可能となる。
【００２６】
次に、マスタノード１００とスレーブノードの詳細な構成について図５〜図１４を用いて説明する。図５は、本実施の形態の検索システムの別の構成例を示す説明図である。図５以降では、それぞれ２つの物理ＤＢから構成される２つの論理ＤＢ「auctions」および「people」を含む検索システムを例として説明する。なお、ＤＢの構成はこれに限られず、３つ以上の物理ＤＢを含むように論理ＤＢを構成してもよい。また、３つ以上の論理ＤＢを含むように検索システムを構成してもよい。
【００２７】
図５に示すように、本実施の形態の検索システムは、クライアント３００と、マスタノード１００と、複数のスレーブノード２００ａ、２００ｂ、２００ｃ、２００ｄとを含んでいる。マスタノード１００、およびクライアント３００の構成は図１と同様であるので同一の符号を付し、説明は省略する。なお、スレーブノード２００ａ、２００ｂ、２００ｃ、２００ｄは、物理ＤＢ内に記憶する情報が異なる以外は同一の構成を有するため、以下では単にスレーブノード２００という場合がある。
【００２８】
図６および図７は、それぞれ論理ＤＢ「people」および「auctions」に格納される情報のデータ形式の一例を示す説明図である。図６および図７に示すように、以下ではＸＭＬ形式で情報が格納されていることを前提とする。
【００２９】
ＸＭＬ形式の情報（ＸＭＬデータ）はタグや属性をノードとする木構造として表現できる。図８および図９は、木構造で表したＸＭＬデータの一例を示す説明図である。図８は、「people」データベースに格納される「person」データを表している。また、図９は、「auctions」データベースに格納される「deal」データを表している。
【００３０】
データベース中では各データの木構造の各ノードにはそれぞれノードＩＤが割り当てて管理される。木のルートである「person」タグを示すノードにはノードＩＤとして900が割り当てられている。このノードＩＤは「people」データベース中でユニークであり、複数の「person」データが格納されている場合でも、このノードＩＤを指定することにより、「person」データを一意に特定することができる。
【００３１】
また、図８に示すように、「/person/watch/@category」属性（「person」タグの直下の子ノードである「watch」タグの直下に存在する「category」属性）は、同図の「person」データ中に２つ存在する。このような場合にも、各ノードに割り当てられているノードＩＤにより、それぞれを特定することができる。ＸＭＬデータの検索は、このように格納されているデータに関して、条件に合致するタグや属性といったノードのノードＩＤを取得する処理を行う一連のオペレータ列の処理を実行することで実現する。なお、オペレータとは、検索結果を求める過程で実行される処理の単位をいう。
【００３２】
図１０は、本実施の形態のマスタノード１００およびスレーブノード２００の詳細な構成を示すブロック図である。図１０に示すように、マスタノード１００は、記憶部１２０と、検索要求受付部１０１と、プラン生成部１０２と、判定部１０３と、更新部１０４と、実行要求部１０５と、転送要求部１０６と、構成管理部１０７と、中間結果管理部１０８と、結果取得部１０９と、を備えている。
【００３３】
記憶部１２０は、検索処理で参照する各種テーブルを格納するものである。具体的には、記憶部１２０は、スキーマテーブル１２１と、分割情報テーブル１２２と、局所性判定表１２３と、作成判定表１２４とを格納している。
【００３４】
スキーマテーブル１２１は、スレーブノード２００の物理ＤＢ２２０（後述）に格納する情報のデータ構造を定めたスキーマ情報を格納するものである。図１１および図１２は、スキーマテーブル１２１に格納されるスキーマ情報のデータ構造の一例を示す説明図である。図１１および図１２に示すように、スキーマテーブル１２１は、物理ＤＢ２２０に格納する情報に含まれる項目と、データ型と、一意性情報とを対応づけて格納している。
【００３５】
データ型には、例えば、ＩＤ型、文字列型、非負整数型、正整数型などのように、項目が取りうる値の形式を定める情報が設定される。一意性情報には、項目が論理データベース内で一意の値を取るか否かを表す情報が設定される。具体的には、一意の値を取る場合に「ユニーク型」が、それ以外の場合に「非ユニーク型」が設定される。
【００３６】
なお、図１１および図１２は、それぞれ「people」データベースおよび「auctions」データベースに格納される情報のスキーマ情報を表している。
【００３７】
図１０に戻り、分割情報テーブル１２２は、格納する物理ＤＢ２２０を判定するための分割基準を規定する分割情報を格納するものである。図１３および図１４は、分割情報のデータ構造の一例を示す説明図である。図１３および図１４は、それぞれ「people」データベースおよび「auctions」データベースについての分割情報を表している。
【００３８】
例えば、図１３では、「people」データベースには、ユニーク型の項目「/person/@id」の値が所定の閾値より大きいか否かによって格納する物理ＤＢ２２０を判定する分割基準が定められている。同様に、図１４では、「auctions」データベースには、ユニーク型の項目「/deal/@id」の値が所定の閾値より大きいか否かによって格納する物理ＤＢ２２０を判定する分割基準が定められている。
【００３９】
なお、スレーブノードＩＤとは、情報の格納先となるスレーブノード２００を識別する情報である。以下では、スレーブノード２００ａ、２００ｂ、２００ｃ、２００ｄのスレーブノードＩＤは、それぞれ１、２、３、４であるものとする。
【００４０】
局所性判定表１２３は、検索処理の過程で得られたシーケンスが、複数の物理ＤＢ２２０に分散して格納されているか否かを表す局所性情報を判定する規則を格納するものである。また、作成判定表１２４は、論理シーケンス管理情報を作成するか否かを判定する規則を格納するものである。
【００４１】
局所性判定表１２３および作成判定表１２４は、後述する判定部１０３が論理シーケンス管理情報を作成するか否かを判定するときに参照するものであるため、各表の詳細は判定部１０３の機能と合わせて説明する。
【００４２】
なお、記憶部１２０は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００４３】
図１０に戻り、検索要求受付部１０１は、クライアント３００から送信された検索要求を受付けるものである。本実施の形態では、検索要求受付部１０１は、ＸＱｕｅｒｙによる検索式を検索要求として受付ける。
【００４４】
図１５は、ＸＱｕｅｒｙによる検索式の一例を示す説明図である。図１５の検索式は、商品カテゴリ番号が「１２３４５」である商品（item）に関するオークションデータ（deal）を取り出し、そのオークション商品の関連商品カテゴリ（related/@category）に興味のあるユーザのＩＤ（@id）を、その関連商品カテゴリごとにひとまとめにして取り出し、さらに、そのユーザが商品を購入したオークションデータ（deal）を出力することを表している。
【００４５】
プラン生成部１０２は、検索要求受付部１０１が受付けた検索式、および分割情報テーブル１２２を参照して、検索処理の実行計画である検索プランを生成するものである。具体的には、プラン生成部１０２は、オペレータ、各オペレータ間のデータの受け渡し依存関係、およびオペレータを実行するスレーブノード２００の割り当てを示す検索プランを生成する。
【００４６】
図１６は、プラン生成部１０２が生成する検索プランの一例を示した説明図である。図１６は、図１５に示すような検索式に対応して生成される検索プランの例を表している。この時点では、論理シーケンス管理情報の作成が不要であるか否かを判定していないため、論理シーケンス管理情報を登録する「registSequence」オペレータが２つ含まれている。
【００４７】
なお、「createTable」などは各オペレータの名称を表している。また、例えばオペレータ名の後の「Slave1」は、スレーブノードＩＤ＝１のスレーブノード２００で実行されるオペレータであることを表している。また、「ＢＴ０」などは中間結果を識別する中間結果ＩＤを表している。そして、記号「->」は、オペレータの実行結果が記号の右側の中間結果ＩＤで識別される中間結果として出力されることを表している。
【００４８】
判定部１０３は、局所性判定表１２３および作成判定表１２４を参照し、論理シーケンス管理情報を作成するか否かを判定するものである。判定部１０３による判定処理では、局所性情報および用途情報が利用される。
【００４９】
局所性情報とは、上述のように、シーケンスが、複数の物理ＤＢ２２０に分散して格納されているかを表す情報である。言い換えると、局所性情報は、あるスレーブノード２００で得られたシーケンスが他のスレーブノード２００上で得られたシーケンスとともに論理シーケンスとして結合されるか否か示す情報である。用途情報とは、検索処理中に得られたシーケンスを一体の論理シーケンスとして参照する必要があるか否かを示す情報である。
【００５０】
まず、局所性情報の求め方について説明する。判定部１０３は、局所性判定表１２３を参照することにより局所性情報を判定する。まず、判定部１０３は、得られたシーケンスのデータ属性と条件値タイプを取得する。
【００５１】
データ属性とは、シーケンスとして得られた項目の属性を表すものである。データ属性には、項目の一意性情報（ユニーク型か、非ユニーク型か）、および項目が物理ＤＢ２２０に分散して格納するときの判断基準として参照されるか否かを表す情報（レンジ分割対象か、非レンジ分割対象か）が含まれる。一意性情報は、図１１および図１２のスキーマテーブル１２１から取得できる。レンジ分割対象か非レンジ分割対象かは、図１３および図１４の分割情報テーブル１２２の分割基準を参照することにより判断できる。
【００５２】
条件値タイプとは、検索条件の中でシーケンスが満たすべき条件の種類を表すものである。条件値タイプとしては、条件値が定数か変数か、および条件値が単独値かシーケンス値かによって、「定数単独値」、「変数単独値」、「定数シーケンス値」、および「変数シーケンス値」の４つの種類が存在する。
【００５３】
条件値が定数か変数かは、検索式を解析することにより判断する。例えば、図１５のような検索式では、１行目の条件値である「１２３４５」は定数であると判断できる。また、２行目の条件値である「＄ｘ」は、１行目で定義された変数であると判断できる。
【００５４】
さらに、判定部１０３は、条件値が単独値かシーケンス値かを検査する。具体的には、判定部１０３は、条件値が定数である場合は、その定数が単独値かシーケンス値かを検索式を解析することにより判断する。また、判定部１０３は、条件値が変数である場合は、検索式中でその条件値が作成される箇所を辿り、シーケンス値を示す変数であるかを判断する。
【００５５】
次に、判定部１０３は、求めたデータ属性と条件値タイプとに対応する局所性情報を、図１７のような局所性判定表１２３から取得することにより、局所性情報を判定する。図１７は、局所性判定表１２３のデータ構造の一例を示す説明図である。判定部１０３は、データ属性および条件値タイプの組合せによって局所性情報を以下のように判定する。
【００５６】
（１）局所性情報「あり」と判定する場合：
（ａ）データ属性が「ユニーク型」または「レンジ分割対象」であり、かつ、条件値タイプが「単独値」である場合。
（ｂ）データ属性が「レンジ分割対象」であり、かつ、条件値タイプが「定数シーケンス値」であり、そのシーケンスに含まれる値がＤＢ分割情報に照らして１つのスレーブに含まれる場合。
（２）局所性情報「不明」と判定する場合：なお、この場合は、検索処理時に条件値を個別に判断して局所性情報が判断される。
（ａ）データ属性が「レンジ分割対象」であり、かつ、条件値タイプが「変数シーケンス値」である場合。
（３）局所性情報「なし」と判定する場合：なお、局所性情報「なし」とは、条件値を参照しても２２０に分散して格納されているか否かを判別できないことを表す。
（ａ）データ属性が「非ユニーク型」かつ「非レンジ分割対象」である場合。
（ｂ）データ属性が「ユニーク型」であり、かつ、条件値タイプが「シーケンス値」である場合。
（ｃ）データ属性が「レンジ分割対象」であり、かつ、条件値タイプが「定数シーケンス値」であり、そのシーケンスに含まれる値がＤＢ分割情報に照らして複数のスレーブノード２００にまたがる場合。
【００５７】
次に、用途情報の求め方について説明する。ＸＱｕｅｒｙの検索式中の中間結果の依存関係は、変数を用いた値の受け渡してとして表現される。例えば、図１５の検索式では、中間結果として「＄ｘ」および「＄ａ」が存在し、「＄ｘ」と「＄ａ」との依存関係は、２行目の式によって表される。
【００５８】
判定部１０３は、このような受け渡し関係を辿ることにより、検索式中で作成される個別のシーケンスが、（１）検索式の最終出力結果の一部となる場合、用途情報＝出力シーケンスと判断する。また、判定部１０３は、個別のシーケンスが、（２）検索式の最終出力結果の一部とならない場合、用途情報＝参照シーケンスと判断する。
【００５９】
図１５の例では、作成されるシーケンスの１つである「＄ｂ」は、最終行の式「return $b」で示されるように、検索式の最終出力結果であると判断できるため、判定部１０３は、用途情報＝出力シーケンスであると判定する。一方、「＄ａ」は、「return」式で出力されるシーケンスではないため、判定部１０３は、用途情報＝参照シーケンスであると判定する。
【００６０】
このようにして、判定部１０３は、局所性情報と用途情報とを求める。そして、判定部１０３は、求めた局所性情報と用途情報とを、図１８のような作成判定表１２４と照合することにより、論理シーケンス管理情報を作成するか否かを判定する。図１８は、作成判定表１２４のデータ構造の一例を示す説明図である。判定部１０３は、論理シーケンス管理情報の作成有無を、用途情報および局所性情報の組合せによって以下のように判定する。
【００６１】
（１）論理シーケンス管理情報を常に作成しないと判定する場合：
（ａ）用途情報が「参照シーケンス」である場合。
（ｂ）用途情報が「出力シーケンス」であり、かつ、局所性情報が「あり」である場合。
（２）論理シーケンス管理情報を作成するか否かを検索処理実行時に条件値を個別に参照して判断すると判定する場合：
（ａ）用途情報が「出力シーケンス」であり、かつ、検索条件に局所性情報が「不明」である場合。
（３）論理シーケンス管理情報を作成すると判定する場合：
（ａ）用途情報が「出力シーケンス」であり、かつ、局所性情報が「なし」の場合。
【００６２】
図１０に戻り、更新部１０４は、判定部１０３によって論理シーケンス管理情報を作成しないと判定されたシーケンスについて、論理シーケンス管理情報を登録するオペレータ（「registSequence」オペレータ）を省略した検索プランを生成し、生成済みの検索プランを更新するものである。
【００６３】
図１９は、更新部１０４により更新された後の検索プランの一例を示す説明図である。図１９は、判定部１０３の結果にしたがい、図１５のような検索式で最初に得られるシーケンスである「＄ａ」に対する「registSequence」オペレータを削除した検索プランの例を表している。
【００６４】
このように、更新部１０４によって、論理シーケンス管理情報を作成する必要がない場合は作成処理を行わないように検索プランの最適化を行うことができるため、検索処理のオーバヘッドを削減することが可能となる。
【００６５】
実行要求部１０５は、スレーブノード２００に対して検索プランを送信することによって検索プランの実行を要求するものである。
【００６６】
転送要求部１０６は、あるスレーブノード２００から中間結果の転送要求を受信したとき、実行可能な転送要求を決定して、転送元のスレーブノード２００に対して転送要求を通知するものである。具体的には、転送要求部１０６は、スレーブノード２００の転送要求通知部２０７（後述）から、中間結果の転送要求を受信して記憶部１２０などに記録する。また、転送要求部１０６は、スレーブノード２００の中間結果作成通知を受けて記録する処理も行う。
【００６７】
図２０は、中間結果の転送要求のデータ構造の一例を示す説明図である。図２０に示すように、中間結果の転送要求には、転送元のスレーブノード２００を識別する転送元スレーブノード情報と、転送先のスレーブノード２００を識別する転送先スレーブノード情報と、転送する中間結果を識別する中間結果ＩＤとが含まれる。
【００６８】
構成管理部１０７は、スレーブノード２００の構成通知部２０８（後述）から各スレーブノード２００のシーケンスＩＤを含む論理シーケンス管理情報を受信して管理するものである。図２１は、論理シーケンス管理情報のデータ構造の一例を示す説明図である。
【００６９】
図２１に示すように、論理シーケンス管理情報には、論理シーケンスを一意に識別する論理シーケンスＩＤと、部分シーケンスＩＤと、シーケンスＩＤを生成したスレーブノード２００のスレーブノードＩＤと、中間結果ＩＤと、キーＩＤとが含まれる。なお、中間結果ＩＤとは、シーケンスを構成する要素の値が格納されている中間結果を識別する識別情報をいう。
【００７０】
部分シーケンスＩＤとは、スレーブノード２００ごとに生成される物理的なシーケンスＩＤをいう。図２２は、部分シーケンスＩＤのデータ構造の一例を示す説明図である。図２２に示すように、部分シーケンスＩＤは、シーケンスを生成するスレーブノード２００のスレーブノードＩＤと、中間結果ＩＤと、中間結果中のカラムを識別するカラム番号と、中間結果中のレコードを識別するレコード番号と、局所シーケンスフラグとを対応づけたデータ構造となっている。
【００７１】
局所シーケンスフラグとは、シーケンスが分散して格納されているかを表すフラグであり、判定部１０３が判定した局所性情報が「あり」のとき「１」、「なし」のとき「０」が設定される。
【００７２】
キーＩＤとは、論理シーケンスを構成するために物理的なシーケンスをグループ化するときのキーとなる情報である。図２３は、キーＩＤのデータ構造の一例を示す説明図である。図２３に示すように、キーＩＤは、中間結果の入力元のスレーブノード２００のスレーブノードＩＤと、入力元の中間結果ＩＤと、入力元の中間結果内の中間結果レコード番号とを対応づけたデータ構造となっている。
【００７３】
中間結果管理部１０８は、各スレーブノード２００の中間結果転送部２０６によって転送された中間結果を受信し、図示しないＲＡＭなどの記憶媒体に保存することにより管理するものである。
【００７４】
結果取得部１０９は、最終的に出力された中間結果を元に各スレーブノード２００からシーケンスの実体データを検索結果として取得して、クライアント３００に送信するものである。
【００７５】
次に、スレーブノード２００について説明する。図１０に示すように、スレーブノード２００は、物理ＤＢ２２０と、実行要求受付部２０１と、実行部２０２と、ＤＢ管理部２０３と、割当部２０４と、中間結果管理部２０５と、中間結果転送部２０６と、転送要求通知部２０７と、構成通知部２０８と、を備えている。
【００７６】
物理ＤＢ２２０は、水平分割された文書を記録する記憶媒体である。本実施の形態では、図６〜図９で説明したように、物理ＤＢ２２０はＸＭＬ形式の文書を格納する。なお、物理ＤＢ２２０は、ＨＤＤ、光ディスク、メモリカード、ＲＡＭなどの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００７７】
実行要求受付部２０１は、マスタノード１００から送信された検索プランの実行要求を受付けるものである。なお、実行要求には実行すべき検索プランが含まれる。
【００７８】
実行部２０２は、実行要求受付部２０１が受付けた実行要求に従い、実行が要求された検索プランを実行するものである。実行部２０２は、まず、検索プランから、実行可能状態テーブルを作成する。実行可能状態テーブルとは、検索プランに記述されたオペレータの入出力依存関係に従い、オペレータを実行するために必要な中間結果の状態に関する条件を定めたテーブルである。
【００７９】
図２４および図２５は、実行可能状態テーブルのデータ構造の一例を示す説明図である。図２４は、図１９に示すような検索プランに対して、スレーブノードＩＤ＝１および２のスレーブノード２００で作成される実行可能状態テーブルの一例を示している。また、図２５は、図１９に示すような検索プランに対して、スレーブノードＩＤ＝３および４のスレーブノード２００で作成される実行可能状態テーブルの一例を示している。
【００８０】
具体的には、実行可能状態テーブルは、入力されるべき中間結果を表す入力中間結果と、入力中間結果が入力されたときに実行可能なオペレータを表す実行オペレータと、オペレータが実行可能か否かを表す実行可能情報とを対応づけて格納している。すなわち、実行可能状態テーブルは、実行するオペレータごとに実行に必要な前提条件である中間結果を表したものである。なお、入力中間結果が「---」となっているオペレータは、実行に必要な中間結果が存在しないオペレータを表す。
【００８１】
実行可能情報には、必要な中間結果が不要な場合、または必要な中間結果が作成済みのため実行可能な場合に「１」が設定される。また、必要な中間結果が作成されていないため実行不可能な場合に「０」が設定される。また、オペレータが実行済みの場合に「２」が設定される。なお、実行可能情報の設定方法はこれに限られるものではなく、次に実行可能なオペレータを判断可能な方法であればあらゆる方法を適用できる。
【００８２】
実行部２０２は、このような実行可能状態テーブルを参照し、実行可能情報が「１」であるオペレータから次に実行すべきオペレータを選択して実行する。なお、次に実行すべきオペレータが尽きた場合に検索処理は終了する。そして、このときに各スレーブノード２００上に残った中間結果が最終的な検索結果として得られる。
【００８３】
なお、実行部２０２は、検索要求に応じた検索プランに含まれうる様々なオペレータに関する処理を実行するものであるが、主に以下のような処理を実行する。
【００８４】
まず、実行部２０２は、オペレータ実行に際し、データベースを管理するＤＢ管理部２０３（後述）に対してデータ取得に関する処理を実行させる。そして、実行部２０２は、オペレータの実行結果情報を、中間結果管理部２０５（後述）が管理する中間結果データに記録する。
【００８５】
また、実行部２０２は、各オペレータを実行し終わると、その結果得られた中間結果が作成済みであることを中間結果作成状態テーブルに記録する。図２６は、中間結果作成状態テーブルのデータ構造の一例を示す説明図である。図２６に示すように、中間結果作成状態テーブルには、作成済みの中間結果の中間結果ＩＤが格納される。
【００８６】
その後、実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。すなわち、中間結果作成状態テーブルに追加された中間結果ＩＤに対応する実行可能情報を、実行済みを表す「２」に更新する。
【００８７】
オペレータ実行時、実行部２０２は、スレーブノード２００上の物理ＤＢ２２０および中間結果管理部２０５が管理している中間結果を対象として処理を行う。ただし、中間結果の転送要求を行うオペレータの場合は、実行部２０２は、転送要求通知部２０７に対して処理を行う。
【００８８】
図１０に戻り、ＤＢ管理部２０３は、物理ＤＢ２２０に対するインデックススキャン、データベーススキャンなどの各種データ取得操作を実行するものである。
【００８９】
割当部２０４は、実行部２０２の指示によって、中間結果として生成されたシーケンスを識別するシーケンスＩＤを割り当てるものである。
【００９０】
中間結果管理部２０５は、生成された中間結果を管理するものである。具体的には、中間結果管理部２０５は、検索プランの実行に伴って生成された中間結果を、図示しないＲＡＭなどの記憶媒体に保存することにより管理する。また、中間結果が転送されたときには、中間結果管理部２０５は、転送された中間結果の複製を作成して記憶媒体に保存する。
【００９１】
中間結果転送部２０６は、他のスレーブノード２００からの中間結果の転送要求を、マスタノード１００の転送要求部１０６を介して受信し、転送要求にしたがって他のスレーブノード２００に対して中間結果を転送するものである。
【００９２】
具体的には、中間結果転送部２０６は、まず転送先スレーブノード情報と中間結果ＩＤとを転送要求から取得する。そして、中間結果転送部２０６は、中間結果ＩＤを参照して転送すべき中間結果を、中間結果管理部２０５を介して記憶媒体から取得する。次に、中間結果転送部２０６は、取得した中間結果を指定された転送先スレーブノード情報で識別されるスレーブノード２００に転送する。
【００９３】
転送要求通知部２０７は、オペレータが中間結果の転送要求を送信するものである場合に、マスタノード１００の転送要求部１０６に指定された中間結果の転送要求を通知するものである。
【００９４】
構成通知部２０８は、割当部２０４によって割り当てられたシーケンスＩＤを含む論理シーケンス管理情報を、マスタノード１００の構成管理部１０７に通知するものである。
【００９５】
次に、このように構成された本実施の形態にかかる検索システムによる検索処理について図２７を用いて説明する。図２７は、本実施の形態における検索処理の全体の流れを示すフローチャートである。
【００９６】
まず、検索要求受付部１０１は、クライアント３００からＸＱｕｅｒｙの検索式を検索要求として受付ける（ステップＳ２７０１）。次に、プラン生成部１０２は、受付けた検索式を解析して、検索プランを生成する（ステップＳ２７０２）。
【００９７】
次に、生成された検索プランから、不要な論理シーケンス管理情報を生成するオペレータを削除して検索プランを最適化する検索プラン最適化処理が実行される（ステップＳ２７０３）。検索プラン最適化処理の詳細については後述する。
【００９８】
次に、実行要求部１０５は、各スレーブノード２００に対して、実行すべき検索プランの実行要求を通知する（ステップＳ２７０４）。
【００９９】
スレーブノード２００の実行要求受付部２０１は、通知された実行要求を受付ける（ステップＳ２７０５）。次に、実行部２０２が、受付けた実行要求に含まれる検索プランを参照して図２５または図２６に示すような実行可能状態テーブルを作成する（ステップＳ２７０６）。
【０１００】
次に、実行部２０２は、実行可能状態テーブルを参照してオペレータごとの実行可能性を判断し、実行できるオペレータを選択する（ステップＳ２７０７）。
【０１０１】
次に、実行部２０２は、論理シーケンスを生成するために論理シーケンス管理情報を通知するオペレータ（「registSequence」オペレータ）であるか否かを判断する（ステップＳ２７０８）。論理シーケンス管理情報を通知するオペレータである場合は（ステップＳ２７０８：ＹＥＳ）、構成通知部２０８は、論理シーケンス管理情報をマスタノード１００に通知する（ステップＳ２７０９）。なお、構成通知部２０８は、それ以前に実行されたオペレータに関連する処理で割当部２０４によって生成されたシーケンスＩＤを含む論理シーケンス管理情報をマスタノード１００に通知する。
【０１０２】
マスタノード１００の構成管理部１０７は、通知された論理シーケンス管理情報を受信してマスタノード１００上の論理シーケンス管理情報に追加登録する（ステップＳ２７１０）。
【０１０３】
ステップＳ２７０８で論理シーケンス管理情報を通知するオペレータでないと判断された場合は（ステップＳ２７０８：ＮＯ）、実行部２０２は、選択したオペレータを実行する（ステップＳ２７１１）。なお、上述のように、このステップでは中間結果の転送を含むさまざまなオペレータが実行されうるが、説明の便宜上、同図では省略している。
【０１０４】
次に、実行部２０２は、オペレータの実行結果を中間結果作成状態テーブルに追加するとともに、実行可能状態テーブルの実行可能情報を更新する（ステップＳ２７１２）。
【０１０５】
次に、実行部２０２は、実行可能状態テーブルを参照してすべてのオペレータが実行されたか否かを判断する（ステップＳ２７１３）。すべてのオペレータが実行されていない場合は（ステップＳ２７１３：ＮＯ）、次に実行可能なオペレータを選択して処理を繰り返す（ステップＳ２７０７）。
【０１０６】
すべてのオペレータが実行された場合は（ステップＳ２７１３：ＹＥＳ）、実行部２０２は、処理結果をマスタノード１００に送信する（ステップＳ２７１４）。
【０１０７】
マスタノード１００の結果取得部１０９は、各スレーブノード２００からの処理結果を統合した検索結果を生成する（ステップＳ２７１５）。そして、結果取得部１０９は、生成した検索結果をクライアント３００に送信して（ステップＳ２７１６）検索処理を終了する。
【０１０８】
次に、ステップＳ２７０３の検索プラン最適化処理の詳細について図２８を用いて説明する。図２８は、本実施の形態における検索プラン最適化処理の全体の流れを示すフローチャートである。
【０１０９】
まず、判定部１０３は、検索式を解析し、オペレータの処理結果として得られるシーケンスを取得する（ステップＳ２８０１）。例えば、図１５に示すような検索式の場合、「＄ａ」および「＄ｂ」が、シーケンスの処理結果として得られることが解析される。
【０１１０】
次に、判定部１０３は、取得したシーケンスの用途情報が参照シーケンスか否かを判断する（ステップＳ２８０２）。上述のように、判定部１０３は、検索式内の値の受け渡し関係を解析することによりシーケンスの用途情報を判定する。図１５の例では、「＄ａ」および「＄ｂ」の用途情報はそれぞれ「参照シーケンス」および「出力シーケンス」と判定される。
【０１１１】
用途情報が参照シーケンスでない場合、すなわち出力シーケンスの場合は（ステップＳ２８０２：ＮＯ）、判定部１０３は、ステップＳ２８０３からステップＳ２８０８で、上述のような判定表を用いた論理シーケンス管理情報の作成有無の判定処理を行う。
【０１１２】
まず、判定部１０３は、スキーマテーブル１２１を参照し、シーケンスの一意性情報を取得する（ステップＳ２８０３）。次に、判定部１０３は、分割情報テーブル１２２を参照し、シーケンスがレンジ分割対象か、非レンジ分割対象かを決定する（ステップＳ２８０４）。
【０１１３】
次に、判定部１０３は、検索式を解析し、シーケンスと比較する条件値が定数か変数かを決定する（ステップＳ２８０５）。続いて、判定部１０３は、条件値が単独値かシーケンス値かを決定する（ステップＳ２８０６）。
【０１１４】
次に、判定部１０３は、決定したデータ属性（一意性情報、およびレンジ分割対象か非レンジ分割対象かを表す情報）、および決定した条件値タイプ（定数か変数か、および単独値かシーケンス値か）に従い、局所性判定表１２３を参照して局所性情報を判定する（ステップＳ２８０７）。
【０１１５】
次に、判定部１０３は、判定された局所性情報と作成判定表１２４とを参照し、論理シーケンス管理情報の作成有無を判定する（ステップＳ２８０８）。例えば、図１８のような作成判定表１２４によれば、局所性情報ありと判定された場合であれば、用途情報が出力シーケンスであっても、論理シーケンス管理情報の作成は不要と判定される。
【０１１６】
ステップＳ２８０２で、用途情報が参照シーケンスであると判断された場合は（ステップＳ２８０２：ＹＥＳ）、判定部１０３は、論理シーケンス管理情報を作成しないと判定する（ステップＳ２８０９）。参照シーケンスの場合は、出力用に論理シーケンスを構成する必要がないため、常に論理シーケンス管理情報の作成は不要と判定することができるためである。
【０１１７】
次に、更新部１０４は、論理シーケンス管理情報の作成が不要である判定されたか否かを判断する（ステップＳ２８１０）。不要と判定された場合は（ステップＳ２８１０：ＹＥＳ）、更新部１０４は、不要と判定されたシーケンスに対応して論理シーケンス管理情報を通知するオペレータを検索プランから削除することにより、検索プランを更新する（ステップＳ２８１１）。
【０１１８】
検索プランの更新後、または、ステップＳ２８１０で、論理シーケンス管理情報の作成が不要でないと判定された場合は（ステップＳ２８１０：ＮＯ）、判定部１０３は、検索式内のすべてのシーケンスを処理したか否かを判断する（ステップＳ２８１２）。
【０１１９】
すべてのシーケンスを処理していない場合は（ステップＳ２８１２：ＮＯ）、次のシーケンスを取得して処理を繰り返す（ステップＳ２８０１）。すべてのシーケンスを処理した場合は（ステップＳ２８１２：ＹＥＳ）、検索プラン最適化処理を終了する。
【０１２０】
このように、検索プラン最適化処理によって、論理シーケンス管理情報の作成が不要な場合には論理シーケンス管理情報を通知するオペレータが検索プランから削除される。これにより、従来はすべてのシーケンスに対して図２７のステップＳ２７０９のように論理シーケンス管理情報を通知するオペレータが実行されていたのに対し、本実施の形態では不要なオペレータの実行を回避して検索処理の処理負担を軽減することが可能となる。
【０１２１】
次に、本実施の形態による検索処理の具体例について説明する。なお、以下では、「registSequence」オペレータを削除することにより、論理シーケンス管理情報を作成しない検索プランに最適化された場合であっても、検索式を満たす検索結果が正しく得られる例について説明する。
【０１２２】
また、以下では、図５の構成を前提とし、マスタノード１００の記憶部１２０には、図１１〜図１４のようなテーブルと、図１７および図１８のような判定表とが記憶され、図１５に示すような検索式が入力された場合を例として説明する。
【０１２３】
なお、図２９〜図５２、図５４〜図６０、および図６２〜図６４は、この例で出力される中間結果の一例を示す説明図である。また、図５３および図６１は、この例で出力される論理シーケンス管理情報の一例を示す説明図である。
【０１２４】
この場合、上述のように、プラン生成部１０２は、図１９に示すような最適化された検索プランを生成する。そして、生成された検索プランに従い、以下の手順で検索処理が実行される。
【０１２５】
まず、スレーブノード１の実行要求受付部２０１は、マスタノード１００の実行要求部１０５からスレーブノード１で実行する検索プランを受け取る。
【０１２６】
なお、スレーブノード１とは、それぞれスレーブノードＩＤ＝１であるスレーブノード２００を表す。以下、同様に、スレーブノードＩＤ＝２、３および４であるスレーブノード２００を、それぞれスレーブノード２、３およびスレーブノード４という。
【０１２７】
スレーブノード１の実行部２０２は、実行要求受付部２０１から検索プランを受け取る。実行部２０２は、受け取った検索プランに記述されたオペレータに関して、入力の中間結果を条件として実行可能条件を表現する図２２のような実行可能状態テーブルを作成する。また、同時に中間結果作成状態テーブルを作成する。なお、初期状態では、中間結果作成状態テーブルにはいずれの中間結果も設定されない。スレーブノード２、スレーブノード３およびスレーブノード４でも、同様に実行部２０２による処理が行われる。
【０１２８】
次に、スレーブノード１の実行部２０２は、実行するオペレータを選択する。この時点では、入力すべき中間結果が存在しないため無条件で実行可能である「createTable」オペレータと「request」オペレータが実行可能である。ここでは、実行部２０２は、まず「request」オペレータを選択するものとする。
【０１２９】
実行部２０２は、中間結果ＢＴ３の転送要求を行う「request」オペレータを実行する。「request」オペレータの実行により、スレーブノード１の転送要求通知部２０７に対して、転送要求通知処理の実行が要求される。転送要求通知部２０７は、マスタノード１００の転送要求部１０６へ転送要求を通知する。マスタノード１００上の転送要求部１０６は、通知された転送要求を受け取り、管理用のテーブルなどに記録することにより転送要求を管理する。スレーブノード２でも同様に中間結果ＢＴ３の転送要求を行うオペレータが実行される。また、スレーブノード３およびスレーブノード４でも、同様の手順によって中間結果ＢＴ２の転送要求を行う「request」オペレータが実行される。
【０１３０】
さらに、スレーブノード１の実行部２０２はオペレータ選択を行い、「createTable」オペレータを選択する。実行部２０２は、検索式で与えられた定数値を記録する中間結果を作成する「createTable」オペレータを実行し、得られた中間結果ＢＴ１を中間結果管理部２０５によって記録する。
【０１３１】
この「createTable」オペレータでは、実行部２０２は、指定された定数値をもつ中間結果を作成する処理を行う。この例では、図１５の検索式のように、定数値として「１２３４５」が指定されている。このため、オペレータ実行の結果、図２９に示す中間結果が作成される。作成された中間結果は１カラムかつ１レコードであり、そのカラム値は「１２３４５」である。
【０１３２】
また、実行部２０２は、作成済み中間結果として、ＢＴ１を中間結果作成状態テーブルに記録する。さらに、実行部２０２は、中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を実行済み（２）に更新する。
【０１３３】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は、実行可能なオペレータとして「select」オペレータを選択し、「select」オペレータを実行する。ここでの「select」オペレータは、図２９の中間結果ＢＴ１のカラム「col1」の値を入力とし、「auctions」データベースに格納されている「deal」データ中の「/deal/item/@category」ノードのうち、入力値「１２３４５」と合致する値をもつノードを検索し、そのノードＩＤを取得する処理を示している。
【０１３４】
実行部２０２は、新たに中間結果ＢＴ１００を作成し、「select」オペレータにより取得された値を中間結果ＢＴ１００のカラム「category」に記録する。さらに作成したＢＴ１００を中間結果管理部２０５によって記録する。「select」オペレータの実行の結果、図３０に示す中間結果が作成される。図３０に示すように、「category」カラム値として、「001」と「002」の２つのノードＩＤが得られている。実行部２０２は、作成済み中間結果として、中間結果ＢＴ１００を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１３５】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「scanAncestor」オペレータを選択し、「scanAncestor」オペレータを実行する。ここでの「scanAncestor」オペレータは、図３０に示す中間結果ＢＴ１００の「category」カラムの値を入力として取り、「auctions」データベースに格納されている「deal」データ中の「/deal」ノードのうち、入力値が示すノード「/deal/item/@category」の祖先ノードとなるノードＩＤを取得する処理を示している。
【０１３６】
実行部２０２は、新たに中間結果ＢＴ１０１を作成し、「scanAncestor」オペレータにより取得された値を中間結果ＢＴ１０１のカラム「deal」に記録する。実行部２０２は、さらに作成した中間結果ＢＴ１０１を中間結果管理部２０５によって記録する。この場合、図３１に示すように、「@category」カラムの値「001」および「002」が示すノードの祖先ノードとして、「deal」カラムの値「003」および「004」がそれぞれ得られる。
【０１３７】
実行部２０２は、作成済み中間結果として、中間結果ＢＴ１０１を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１３８】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「scanDescendant」オペレータを選択し、「scanDescendant」オペレータを実行する。ここでの「scanDescendant」オペレータは、図３１に示す中間結果ＢＴ１０１の「deal」カラムの値を入力とし、「auctions」データベースに格納されている「deal」データ中の「/deal/related/@category」ノードのうち、入力値が示すノード「/deal」の子孫ノードとなるノードのノードＩＤを取得する処理を示している。
【０１３９】
実行部２０２は、新たに中間結果ＢＴ２を作成し、「scanDescendant」オペレータにより取得された値を中間結果ＢＴ２のカラム「category2」に記録する。さらに作成したＢＴ２を中間結果管理部２０５によって記録する。この場合、図３２に示すように、「deal」カラムの値「003」の子孫ノードとして「category2」カラムの値「005」および「006」の２値、「004」の子孫ノードとして「category2」カラムの値「007」および「008」の２値が得られる。
【０１４０】
実行部２０２は、作成済み中間結果として、中間結果ＢＴ２を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１４１】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「notify」オペレータを選択し、「notify」オペレータを実行する。ここでの「notify」オペレータは、中間結果ＢＴ２が作成済み状態であることを示す中間結果作成通知をマスタノード１００の転送要求部１０６に通知する。
【０１４２】
同様にして、スレーブノード２でも、実行部２０２が、スレーブノード１におけるここまでの一連の処理と同様の流れでオペレータを実行する。「createTable」オペレータの実行により図３３に示すＢＴ１が生成される。次に「select」オペレータの実行により図３４に示すＢＴ１００が生成される。次に「scanAncestor」オペレータの実行により図３５に示すＢＴ１０１が生成される。次に「scanDescendant」オペレータの実行により図３６に示すＢＴ２が生成される。その後、「notify」オペレータの実行により、スレーブノード２の実行部２０２は、中間結果ＢＴ２が作成済み状態であることを示す中間結果作成通知をマスタノード１００の転送要求部１０６に通知する。
【０１４３】
次に、マスタノード１００上の転送要求部１０６は、これまでに受け取った中間結果作成通知および転送要求通知をマッチングし、実行が可能な転送要求を決定する。この場合、スレーブノード１およびスレーブノード２で中間結果ＢＴ２が作成済みであるので、スレーブノード３とスレーブノード４に対して、それぞれの中間結果ＢＴ２の転送が可能である決定できる。
【０１４４】
マスタノード１００の転送要求部１０６は、転送する中間結果ＢＴ２を格納している転送元スレーブノード２００の中間結果転送部２０６に対して転送要求を通知して、中間結果の転送を要求する。この例では、マスタノード１００の転送要求部１０６は、転送すべき中間結果ＢＴ２を格納している転送元スレーブノード２００であるスレーブノード１およびスレーブノード２の中間結果転送部２０６に対して、中間結果ＢＴ２を、転送先スレーブノード２００であるスレーブノード３およびスレーブノード４へ転送する転送要求を通知する。
【０１４５】
転送要求を受けたスレーブノード１とスレーブノード２の中間結果転送部２０６は、マスタノード１００上の転送要求部１０６からの転送要求を受け取る。その後、転送要求が示す転送先スレーブノード２００であるスレーブノード３およびスレーブノード４に対する中間結果ＢＴ２の転送を実行する。
【０１４６】
転送を受ける転送先スレーブノード２００であるスレーブノード３の中間結果転送部２０６は、新たに中間結果ＢＴ２を作成する。その後、転送元スレーブノード２００であるスレーブノード１とスレーブノード２から転送される中間結果を受け取り、受け取った中間結果を作成した中間結果ＢＴ２に順次記録する。このとき、各レコードに関してキーＩＤを作成し、中間結果ＢＴ２のキーＩＤカラムに格納する。転送の結果、図３７に示すＢＴ２が作成される。
【０１４７】
図３７に示すように、スレーブノード１の中間結果ＢＴ２（図３２）とスレーブノード２の中間結果ＢＴ２（図３６）の値がマージされた中間結果がスレーブノード３の中間結果ＢＴ２として作成される。実行部２０２は、最終的に作成された中間結果ＢＴ２を中間結果管理部２０５によって記録する。さらに、転送先スレーブノード２００の実行部２０２に対して中間結果ＢＴ２の転送完了通知を行う。実行部２０２は、作成済み中間結果として、中間結果ＢＴ２を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１４８】
転送を受ける転送先スレーブノード２００であるスレーブノード４でも同様の処理が行われ、図３７と同様の中間結果ＢＴ２が作成される。
【０１４９】
更新された実行可能状態テーブルを参照し、スレーブノード３の実行部２０２は実行可能なオペレータとして「Join」オペレータを選択し、「Join」オペレータを実行する。ここでの「Join」オペレータは、図３７に示す中間結果ＢＴ２の「category2」カラムの値を入力とし、「auctions」データベースに格納されている「deal」データ中で入力値が示す「/deal/related/@category」ノードのノード値と、「people」データベースに格納されている「person」データ中の「/person/profile/interest/@category」ノードのノード値とを比較し、入力値が示す「/deal/related/@category」ノードのノード値と一致する値を持つ「/person/profile/interest/@category」ノードのノードＩＤを取得する処理を示している。
【０１５０】
実行部２０２は、新たに中間結果ＢＴ２００を作成し、「Join」オペレータにより取得された値を中間結果ＢＴ２００のカラム「category3」に記録する。実行部２０２は、さらに作成した中間結果ＢＴ２００を中間結果管理部２０５によって記録する。この場合、図３８に示すように、「category2」カラムの値「005」に対しては、「category3」カラムの値として「201」が求められる。同様に、「category2」カラムの値「007」に対しては、「category3」カラムの値として「202」および「203」の２値が求められる。さらに、「category2」カラムの値「106」に対しては、「category3」カラムの値として「204」および「205」の２値が求められる。「category2」カラムのその他の値「006」、「008」、「105」、「107」および「108」に対しては、求められる値がデータベースpeople中に存在しない。
【０１５１】
実行部２０２は、作成済み中間結果として、中間結果ＢＴ２００を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１５２】
更新された実行可能状態テーブルを参照し、スレーブノード３の実行部２０２は実行可能なオペレータとして「scanAncestor」オペレータを選択し、「scanAncestor」オペレータを実行する。ここでの「scanAncestor」オペレータは、図３８に示す中間結果ＢＴ２００の「category3」カラムの値を入力とし、「people」データベースに格納されている「person」データ中の「/person」ノードのうち、入力値が示すノード「/person/profile/interest/@category」の祖先ノードのノードＩＤを取得する処理を示している。
【０１５３】
実行部２０２は、新たに中間結果ＢＴ２０１を作成し、「scanAncestor」オペレータにより取得された値を中間結果ＢＴ２０１のカラム「person」に記録する。この場合、図３９に示す中間結果が求められる。同図では、例えば「category3」カラムの値「201」が示す「/person/profile/interest/@category」ノードの祖先ノードのノードＩＤとして「206」が求められることが示されている。さらに実行部２０２は、作成済み中間結果として、ＢＴ２０１を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１５４】
更新された実行可能状態テーブルを参照し、スレーブノード３の実行部２０２は実行可能なオペレータとして「scanDescendant」オペレータを選択し、「scanDescendant」オペレータを実行する。ここでの「scanDescendant」オペレータは、図３９に示す中間結果ＢＴ２０１の「person」カラムの値を入力とし、「people」データベースに格納されている「person」データ中の「/person/@id」ノードのうち、入力値が示すノード「/person」の子孫ノードとなるノードＩＤを取得する処理を示している。
【０１５５】
実行部２０２は、新たに中間結果ＢＴ２０２を作成し、「scanDescendant」オペレータにより取得された値を中間結果ＢＴ２０２のカラム「id」に記録する。実行部２０２は、さらに作成した中間結果ＢＴ２０２を中間結果管理部２０５によって記録する。この場合、図４０に示す中間結果が求められる。同図では、例えば、「person」カラムの値「206」が示す「/person」ノードの子孫ノードのノードＩＤとして「211」が求められることが示されている。
【０１５６】
さらに、実行部２０２は、作成済み中間結果として、ＢＴ２０２を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１５７】
更新された実行可能状態テーブルを参照し、スレーブノード３の実行部２０２は実行可能なオペレータとして「sequence」オペレータを選択し、「sequence」オペレータを実行する。ここでの「sequence」オペレータは、図４０に示す中間結果ＢＴ２０２を入力とし、入力された中間結果の各レコードに関して、同一の「キーＩＤ」カラム値を持つレコードをグループ化し、「id」カラム値からなるシーケンス、およびそのシーケンスのシーケンスＩＤを求める処理を行う。
【０１５８】
すなわち、実行部２０２は、新たに中間結果ＢＴ３と中間結果ＢＴ１００２とを作成し、中間結果ＢＴ３のカラム「S（id）」に生成されたシーケンスＩＤを記録するとともに、中間結果ＢＴ１００２のカラム「S（id）」とカラム「id」に、生成されたシーケンスＩＤとその要素となる「id」カラム値を対にして記録する。実行部２０２は、さらに作成した中間結果ＢＴ３および中間結果ＢＴ１００２を中間結果管理部２０５によって記録する。この場合、図４１および図４２に示す中間結果ＢＴ３およびＢＴ１００２がそれぞれ求められる。例えば、図４１では、生成された３つのシーケンスのシーケンスＩＤが「S（id）」カラムの値「33411」、「33421」および「33431」として求められている。また、図４２では、このシーケンスＩＤ「33421」が示すシーケンスの実体として、「id」カラムの値「212」および「213」が求められている。すなわち、シーケンスＩＤ「33421」が示すシーケンスは、この２値から構成される。
【０１５９】
なお、このときのシーケンスＩＤは以下の手順で求められる。まず、実行部２０２は、「sequence」オペレータの実行の際に、自身のスレーブノードＩＤ、結果格納先となる中間結果の中間結果ＩＤ、中間結果中のカラム番号、中間結果中のレコード番号、およびプラン生成時に求めた局所性判定結果である局所性情報に対応する局所シーケンスフラグを、割当部２０４に対して一組の入力として与える。割当部２０４は、図２２のフォーマットに従ってシーケンスＩＤを生成し、実行部２０２に返却する。なお、最適化が実行されているため、「registSequence」オペレータは実行されない。
【０１６０】
実行部２０２は、作成済み中間結果として、中間結果ＢＴ３を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１６１】
更新された実行可能状態テーブルを参照し、スレーブノード３の実行部２０２は実行可能なオペレータとして「notify」オペレータを選択し、「notify」オペレータを実行する。ここでの「notify」オペレータは、中間結果ＢＴ３が作成済み状態であることを示す中間結果作成通知をマスタノード１００の転送要求部１０６に通知する。
【０１６２】
同様にして、スレーブノード４でも、実行部２０２が、スレーブノード３におけるここまでの一連の処理と同様の流れでオペレータを実行する。転送実行により図３７と同様のＢＴ２がスレーブノード４上に生成される。次に「Join」オペレータの実行により図４３に示すＢＴ２００が生成される。次に「scanAncestor」オペレータの実行により図４４に示すＢＴ２０１が生成される。次に「scanDescendant」オペレータの実行により図４５に示すＢＴ２０２が生成される。次に「sequence」オペレータの実行により図４６に示すＢＴ３および図４７に示すＢＴ１００２が生成される。その後、「notify」オペレータ実行により、中間結果ＢＴ３が作成済み状態であることを示す中間結果作成通知をマスタノード１００の転送要求部１０６に通知する。
【０１６３】
次に、マスタノード１００上の転送要求部１０６は、これまでに受け取った中間結果作成通知および転送要求通知をマッチングし、実行が可能な転送要求を決定する。この場合、スレーブノード３およびスレーブノード４で中間結果ＢＴ３が作成済みであるので、スレーブノード１とスレーブノード２に対して、それぞれの中間結果ＢＴ３の転送が可能である決定できる。
【０１６４】
マスタノード１００の転送要求部１０６は、転送する中間結果ＢＴ３を格納している転送元スレーブノード２００の中間結果転送部２０６に対して転送要求を通知し、中間結果の転送を要求する。この場合、マスタノード１００の転送要求部１０６は、転送すべき中間結果ＢＴ３を格納している転送元スレーブノード２００であるスレーブノード３およびスレーブノード４の中間結果転送部２０６に対して、中間結果ＢＴ３を転送先スレーブノード２００であるスレーブ１およびスレーブ２へ転送する転送要求を通知する。
【０１６５】
転送要求を受けたスレーブノード３とスレーブノード４の中間結果転送部２０６は、マスタノード１００上の転送要求部１０６からの転送要求を受け取る。その後、転送要求が示す転送先スレーブノード２００であるスレーブノード１とスレーブノード２に対する中間結果ＢＴ３の転送を実行する。
【０１６６】
転送を受ける転送先スレーブノード２００であるスレーブノード１の中間結果転送部２０６は、新たに中間結果ＢＴ３を作成する。その後、転送元スレーブノード２００であるスレーブノード３とスレーブノード４から転送される中間結果を受け取り、受け取った中間結果を作成した中間結果ＢＴ３に順次記録する。転送の結果、図４８に示すＢＴ３が作成される。
【０１６７】
同図に示すように、スレーブノード３の中間結果ＢＴ３（図４１）とスレーブノード４の中間結果ＢＴ３（図４６）の値がマージされた中間結果がスレーブノード１の中間結果ＢＴ３として作成される。実行部２０２は、最終的に作成された中間結果ＢＴ３を中間結果管理部２０５によって記録する。スレーブノード１の実行部２０２は、さらに、転送先スレーブノード２００の実行部２０２に対して中間結果ＢＴ３の転送完了通知を行う。実行部２０２は、作成済み中間結果として、中間結果ＢＴ３を中間結果作成状態テーブルに記録する。実行部２０２は、中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１６８】
転送を受ける転送先スレーブノード２００であるスレーブノード２でも同様の処理が行われ、図４８と同様の中間結果ＢＴ３が作成される。
【０１６９】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「Join」オペレータを選択し、「Join」オペレータを実行する。ここでの「Join」オペレータは、図４８に示す中間結果ＢＴ３の「S（id）」カラムの値を入力とし、「people」データベースに格納されている「person」データ中で、入力値が示す「/person/@id」ノードのノード値と、「auctions」データベースに格納されている「deal」データ中の「/deal/@buyer」ノードのノード値とを比較し、入力値が示す「/person/@id」ノードのノード値と一致する値を持つ「/deal/@buyer」ノードのノードＩＤを取得する処理を示している。
【０１７０】
実行部２０２は、新たに中間結果ＢＴ３００を作成し、「Join」オペレータにより取得された値を中間結果ＢＴ３００のカラム「person」に記録する。実行部２０２は、さらに作成した中間結果ＢＴ３００を中間結果管理部２０５によって記録する。この場合、図４９に示す中間結果が得られる。同図では、例えば、「S（id）」カラムの値「33411」に対する「person」カラムの値として「401」および「402」が求められることが示されている。
【０１７１】
実行部２０２は、作成済み中間結果として、中間結果ＢＴ３００を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１７２】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「scanAncestor」オペレータを選択し、「scanAncestor」オペレータを実行する。ここでの「scanAncestor」オペレータは、図４９に示す中間結果ＢＴ３００の「person」カラムの値を入力とし、「auctions」データベースに格納されている「deal」データ中の「/deal」ノードのうち、入力値が示すノード「/deal/@buyer」の祖先ノードのノードＩＤを取得する処理を示している。
【０１７３】
実行部２０２は、新たに中間結果ＢＴ３０１を作成し、「scanAncestor」オペレータにより取得された値を中間結果ＢＴ３０１のカラム「deal」に記録する。この場合、図５０に示す中間結果が求められる。さらに実行部２０２は、作成済み中間結果として、ＢＴ３０１を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１７４】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「sequence」オペレータを選択し、「sequence」オペレータを実行する。ここでの「sequence」オペレータは、図５０に示す中間結果ＢＴ３０１を入力とし、入力された中間結果の各レコードに関して、同一の「キーＩＤ」カラム値を持つレコードをグループ化し、「deal」カラム値からなるシーケンス、およびそのシーケンスのシーケンスＩＤを求める処理を行う。
【０１７５】
実行部２０２は、新たに中間結果ＢＴ０と中間結果ＢＴ１００４を作成し、中間結果ＢＴ０のカラム「S（deal）」に生成されたシーケンスＩＤを記録するとともに、中間結果ＢＴ１００４のカラム「S（deal）」とカラム「deal」に、生成されたシーケンスＩＤとその要素となる「deal」カラム値を対にして記録する。
【０１７６】
実行部２０２は、さらに作成した中間結果ＢＴ０および中間結果ＢＴ１００４を中間結果管理部２０５によって記録する。この場合、図５１および図５２に示す中間結果が求められる。例えば、図５１では、生成された３つのシーケンスのシーケンスＩＤが「S（deal）」カラムの値「10110」、「10120」および「10130」として求められた例が示されている。
【０１７７】
また、図５２では、このシーケンスＩＤ「10110」が示すシーケンスの実体として、「deal」カラムの値「406」および「407」が求められた例が示されている。シーケンスＩＤ「10110」が示すシーケンスは、この２値から構成される。実行部２０２は、作成済み中間結果として、中間結果ＢＴ０を中間結果作成状態テーブルに記録する。実行部２０２は中間結果作成状態テーブル上で更新された情報をもとに、実行可能状態テーブルの実行可能情報を更新する。
【０１７８】
更新された実行可能状態テーブルを参照し、スレーブノード１の実行部２０２は実行可能なオペレータとして「registSequence」オペレータを選択し、「registSequence」オペレータを実行する。「registSequence」オペレータでは、実行部２０２は、中間結果ＢＴ０に記録されているS（deal）属性に関する論理シーケンス管理情報を構成通知部２０８に渡す。構成通知部２０８は受け取った論理シーケンス管理情報をマスタノード１００の構成管理部１０７に転送する。マスタノード１００上の構成管理部１０７は、受け取った論理シーケンス管理情報を図５３で示される論理シーケンス構成管理テーブルに追加登録する。
【０１７９】
例えば、図５１のＢＴ０に対しては、１レコード目の「S（deal）」カラム値で示されるシーケンスの論理シーケンス管理情報は、（10110,1,1004,111）となる。これは、図５３の１レコード目の論理シーケンス管理情報に対応する。
【０１８０】
同様にして、スレーブノード２でも、実行部２０２が、スレーブノード１におけるここまでの一連の処理と同様の流れでオペレータを実行する。転送実行により図４８と同様のＢＴ３がスレーブノード２上に生成される。次に「Join」オペレータの実行により図５４に示すＢＴ３００が生成される。次に「scanAncestor」オペレータの実行により図５５に示すＢＴ３０１が生成される。次に「sequence」オペレータの実行により図５６に示すＢＴ０および図５７に示すＢＴ１００４が生成される。その後、「registSequence」オペレータ実行により、中間結果ＢＴ０に関する論理シーケンス管理情報をマスタノード１００の構成管理部１０７に転送する。マスタノード１００上の構成管理部１０７は、転送された論理シーケンス管理情報を、図５３のような論理シーケンス構成管理テーブルに追加する。
【０１８１】
以上の、一連の検索プランの実行結果として、データベース検索の検索結果して得られた図５８および図５９の中間結果ＢＴ０は、スレーブノード１およびスレーブノード２の中間結果管理部２０５にそれぞれ保持されている。また、スレーブノード２００をまたがって存在するシーケンスの構成を示す図５３の論理シーケンス構成管理テーブルは、マスタノード１００の構成管理部１０７に保持されている。
【０１８２】
すべての検索プランの実行後、スレーブノード１およびスレーブノード２は最終的に得られた中間結果ＢＴ０をそれぞれの中間結果転送部２０６に渡し、マスタノード１００に転送する。マスタノード１００の中間結果管理部１０８は各スレーブノード２００からの中間結果を受信し、それぞれをマージして図６０に示すようなマスタノード１００上の中間結果ＢＴ０を作成して記録する。
【０１８３】
最終的に検索結果を返却する際には、以下の手順で検索結果である「$b」に相当する「S（deal）」カラムの値（シーケンス値）を取得する。
【０１８４】
まず、検索プランの実行終了後、マスタノード１００上の結果取得部１０９は、図６０のような中間結果ＢＴ０の「S（deal）」カラムからシーケンスＩＤを取り出す。結果取得部１０９は、取り出した値の局所シーケンスフラグの値を参照することにより（末尾の数値が０）、局所性の無い論理シーケンスであることを判断できる。結果取得部１０９は、論理シーケンスを構成する部分シーケンスの実体を取得するために、取り出したシーケンスＩＤをキーとして、構成管理部１０７によって管理される論理シーケンス構成管理テーブルから論理シーケンス管理情報を取得する。
【０１８５】
例えば、「S（deal）」カラム値「10110」の場合、論理シーケンス管理情報の部分シーケンスＩＤを参照することにより、対応する論理シーケンスＩＤとして「１」を取得することができる。図６１は、このようにして得られた論理シーケンス管理情報の一例を示している。結果取得部１０９は、得られた論理シーケンス管理情報から、論理シーケンスを構成する部分シーケンスが存在するスレーブノードＩＤと中間結果ＩＤを取得し、転送要求部１０６に中間結果の転送を要求する。
【０１８６】
転送要求部１０６は、該当するスレーブノード２００へ中間結果ＩＤとシーケンスＩＤを通知し中間結果の転送を要求する。転送要求部１０６から中間結果の転送要求を受けたスレーブノード２００の中間結果転送部２０６は、要求された中間結果をマスタノード１００の中間結果管理部１０８へ転送する。スレーブノード１から転送される中間結果は、例えば、図６２のような中間結果ＢＴ１００６で表される。また、スレーブノード２から転送される中間結果は、例えば、図６３のような中間結果ＢＴ１００７で表される。
【０１８７】
マスタノード１００の中間結果管理部１０８は、受信した中間結果をマージした図６４のような中間結果ＢＴ１００８を作成して記録する。結果取得部１０９は、図６４の中間結果ＢＴ１００８の「deal」カラムの値として、論理シーケンスＩＤ「１」を構成する「/deal」ノードの値を得ることができる。
【０１８８】
以上説明したように、「registSequence」オペレータを実行しないように最適化された検索プランであっても正常に検索結果を取得することができる。すなわち、本実施の形態の手法により、論理シーケンス管理情報を作成する必要がない場合は作成処理を行わないように検索プランを最適化し、その結果として検索処理のオーバヘッドを削減することができる。
【０１８９】
次に、「registSequence」オペレータを省略できないにも関わらず「registSequence」オペレータをスキップするように検索プランを変形したことにより、検索結果が正しく得られない例について説明する。以下では、図６５に示すような検索式が入力された場合を例として説明する。
【０１９０】
なお、図６６は、本来実行されるべき検索プランの一例を示す説明図である。また、図６７は、「registSequence」オペレータをスキップするように変形した検索プランの一例を示す説明図である。また、図６８〜図７４は、この例で出力される中間結果の一例を示す説明図である。また、図７５は、この例で出力される論理シーケンス管理情報の一例を示す説明図である。
【０１９１】
図６５の検索式の場合、シーケンス「$a」は最終出力結果となる出力シーケンスであるため、シーケンス「$a」に関する検索プランに関して「registSequence」オペレータをスキップするようなプラン変形を行うことはできない。
【０１９２】
図６７の最後でＢＴ３を出力するオペレータの実行までは、上述の図１９の検索プランでＢＴ３を出力するオペレータの実行までの流れと同様に、各スレーブノード２００上で一連のオペレータが実行される。スレーブノード３上では図６８に示すような中間結果ＢＴ３が出力される。また、スレーブノード４上では図６９に示すような中間結果ＢＴ３が求められる。
【０１９３】
以上の一連の検索プランの実行結果として得られた図６８および図６９の中間結果ＢＴ３は、スレーブノード３およびスレーブノード４の中間結果管理部２０５にそれぞれ保持されている。すべての検索プランの実行後、スレーブノード３およびスレーブノード４は最終的に得られた中間結果ＢＴ３をそれぞれの中間結果転送部２０６に渡し、マスタノード１００に転送する。
【０１９４】
マスタノード１００の中間結果管理部１０８は各スレーブノード２００からの中間結果を受信し、それぞれをマージして図７０に示すようなマスタノード１００上の中間結果ＢＴ３を作成し、中間結果管理部２０５によって記録する。
【０１９５】
最終的に検索結果の返却する際には、以下の手順で検索結果である「$a」に相当する「S（id）」カラムの値（シーケンス値）を取得する。
【０１９６】
まず、検索プランの実行終了後、マスタノード１００上の結果取得部１０９は、図７０のような中間結果ＢＴ３の「S（id）」カラムからシーケンスＩＤを取り出す。結果取得部１０９は、取り出した値の局所シーケンスフラグの値を参照することにより（末尾の数値が１）、局所性がある論理シーケンスであることを判断できる。
【０１９７】
次に、結果取得部１０９は、得られたシーケンスＩＤから、シーケンスを構成する部分シーケンスが存在するスレーブノード２００と中間結果ＩＤを取得し、転送要求部１０６に中間結果の転送を要求する。例えば、「S（id）」カラム値が「33411」の場合、結果取得部１０９は、図２２に示すようなシーケンスＩＤのフォーマットに従い、スレーブノード３のＢＴ３に存在するシーケンスであることを判断できる。
【０１９８】
転送要求部１０６は、該当するスレーブノード２００へ中間結果ＩＤとシーケンスＩＤを通知し中間結果の転送を要求する。転送要求部１０６から中間結果の転送要求を受けたスレーブノード２００の中間結果転送部２０６は、要求された中間結果をマスタノード１００の中間結果管理部１０８へ転送する。スレーブノード３から転送される中間結果は、例えば、図７１のような中間結果ＢＴ１００２で表される。また、スレーブノード４から転送される中間結果は、例えば、図７２のような中間結果ＢＴ１００２で表される。
【０１９９】
マスタノード１００の中間結果管理部１０８は、中間結果を受信すると、図７３に示すような中間結果ＢＴ１００４を作成して記録する。結果取得部１０９は、図７３の中間結果ＢＴ１００４の「id」カラムの値として、シーケンスＩＤ「33411」を構成する「/person/@id」ノードの値を得ることになる。
【０２００】
しかしながら、ここで得られた検索結果は誤りである。ＢＴ３を得るオペレータの前に実行される「scanDescendant」オペレータによって、図４０および図４５のように各スレーブノード２００で求められた中間結果ＢＴ２０２は、論理的には図７４のように一つである。そのため、例えば「category2」カラム（=$x）の値が「005」の場合に、その値を元に得られるシーケンス「S（id）」カラムの値は、論理的には図７５のように２値の「id」カラムの値からなるシーケンスとなるのが正しい。これに対し、図７３では、「211」のみしか「id」カラムの値として得られていない。
【０２０１】
すなわち、「registSequence」オペレータを排除する最適化を行える条件を満たさないにもかかわらず「registSequence」オペレータを排除するプラン変形を行った場合、誤った結果が求められることになる。言い換えると、本実施のようにシーケンスの局所性および用途を判定して検索プランの最適化を行うことにより、不要な処理を回避して処理負担を軽減しつつ、正しい検索結果を得ることが可能となる。
【０２０２】
以上のように、本実施の形態にかかる検索システムでは、分散データベースの検索過程で得られたシーケンスが物理ＤＢ２２０の１つに局所的に格納されているか、および検索結果として出力されるかを判定し、いずれかを満たす場合に、論理シーケンスを構成する処理を不要とするように検索プランを最適化することができる。このため、分散データベースの検索で発生しうるシーケンスに関する処理負担を軽減することが可能となる。
【０２０３】
次に、本実施の形態にかかるマスタノードおよびスレーブノードのハードウェア構成について図７６を用いて説明する。図７６は、本実施の形態にかかるマスタノードおよびスレーブノードのハードウェア構成を示す説明図である。
【０２０４】
本実施の形態にかかるマスタノードおよびスレーブノードは、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、ＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）ドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置と、各部を接続するバス６１を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０２０５】
本実施の形態にかかるマスタノードおよびスレーブノードで実行されるプログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０２０６】
また、本実施の形態にかかるマスタノードおよびスレーブノードで実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施の形態にかかるマスタノードおよびスレーブノードで実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０２０７】
また、本実施の形態のプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０２０８】
本実施の形態にかかるマスタノードおよびスレーブノードで実行されるプログラムは、上述した各部（「検索要求受付部、プラン生成部、判定部、更新部、実行要求部、転送要求部、構成管理部、中間結果管理部、結果取得部」または「実行要求受付部、実行部、ＤＢ管理部、割当部、中間結果管理部、中間結果転送部、転送要求通知部、構成通知部」）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１（プロセッサ）が上記記憶媒体からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上述した各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０２０９】
以上のように、本発明にかかる分散データベースから情報を検索するシステム、装置、および方法は、ＸＭＬなどの構造化文書を複数の装置に水平分散配置して管理するシステム、装置および方法に適している。
【図面の簡単な説明】
【０２１０】
【図１】本実施の形態の検索システムの構成の一例を示す説明図である。
【図２】入力される検索式の一例を示す説明図である。
【図３】シーケンスの表現形式の一例を示す説明図である。
【図４】論理シーケンス管理情報の一例を示す説明図である。
【図５】本実施の形態の検索システムの別の構成例を示す説明図である。
【図６】論理ＤＢに格納される情報のデータ形式の一例を示す説明図である。
【図７】論理ＤＢに格納される情報のデータ形式の一例を示す説明図である。
【図８】木構造で表したＸＭＬデータの一例を示す説明図である。
【図９】木構造で表したＸＭＬデータの一例を示す説明図である。
【図１０】本実施の形態のマスタノードおよびスレーブノードの詳細な構成を示すブロック図である。
【図１１】スキーマテーブルに格納されるスキーマ情報のデータ構造の一例を示す説明図である。
【図１２】スキーマテーブルに格納されるスキーマ情報のデータ構造の一例を示す説明図である。
【図１３】分割情報のデータ構造の一例を示す説明図である。
【図１４】分割情報のデータ構造の一例を示す説明図である。
【図１５】検索式の一例を示す説明図である。
【図１６】検索プランの一例を示した説明図である。
【図１７】局所性判定表のデータ構造の一例を示す説明図である。
【図１８】作成判定表のデータ構造の一例を示す説明図である。
【図１９】更新された後の検索プランの一例を示す説明図である。
【図２０】中間結果の転送要求のデータ構造の一例を示す説明図である。
【図２１】論理シーケンス管理情報のデータ構造の一例を示す説明図である。
【図２２】シーケンスＩＤのデータ構造の一例を示す説明図である。
【図２３】キーＩＤのデータ構造の一例を示す説明図である。
【図２４】実行可能状態テーブルのデータ構造の一例を示す説明図である。
【図２５】実行可能状態テーブルのデータ構造の一例を示す説明図である。
【図２６】中間結果作成状態テーブルのデータ構造の一例を示す説明図である。
【図２７】本実施の形態における検索処理の全体の流れを示すフローチャートである。
【図２８】本実施の形態における検索プラン最適化処理の全体の流れを示すフローチャートである。
【図２９】中間結果の一例を示す説明図である。
【図３０】中間結果の一例を示す説明図である。
【図３１】中間結果の一例を示す説明図である。
【図３２】中間結果の一例を示す説明図である。
【図３３】中間結果の一例を示す説明図である。
【図３４】中間結果の一例を示す説明図である。
【図３５】中間結果の一例を示す説明図である。
【図３６】中間結果の一例を示す説明図である。
【図３７】中間結果の一例を示す説明図である。
【図３８】中間結果の一例を示す説明図である。
【図３９】中間結果の一例を示す説明図である。
【図４０】中間結果の一例を示す説明図である。
【図４１】中間結果の一例を示す説明図である。
【図４２】中間結果の一例を示す説明図である。
【図４３】中間結果の一例を示す説明図である。
【図４４】中間結果の一例を示す説明図である。
【図４５】中間結果の一例を示す説明図である。
【図４６】中間結果の一例を示す説明図である。
【図４７】中間結果の一例を示す説明図である。
【図４８】中間結果の一例を示す説明図である。
【図４９】中間結果の一例を示す説明図である。
【図５０】中間結果の一例を示す説明図である。
【図５１】中間結果の一例を示す説明図である。
【図５２】中間結果の一例を示す説明図である。
【図５３】論理シーケンス管理情報の一例を示す説明図である。
【図５４】中間結果の一例を示す説明図である。
【図５５】中間結果の一例を示す説明図である。
【図５６】中間結果の一例を示す説明図である。
【図５７】中間結果の一例を示す説明図である。
【図５８】中間結果の一例を示す説明図である。
【図５９】中間結果の一例を示す説明図である。
【図６０】中間結果の一例を示す説明図である。
【図６１】論理シーケンス管理情報の一例を示す説明図である。
【図６２】中間結果の一例を示す説明図である。
【図６３】中間結果の一例を示す説明図である。
【図６４】中間結果の一例を示す説明図である。
【図６５】検索式の一例を示す説明図である。
【図６６】検索プランの一例を示す説明図である。
【図６７】変形した検索プランの一例を示す説明図である。
【図６８】中間結果の一例を示す説明図である。
【図６９】中間結果の一例を示す説明図である。
【図７０】中間結果の一例を示す説明図である。
【図７１】中間結果の一例を示す説明図である。
【図７２】中間結果の一例を示す説明図である。
【図７３】中間結果の一例を示す説明図である。
【図７４】中間結果の一例を示す説明図である。
【図７５】論理シーケンス管理情報の一例を示す説明図である。
【図７６】本実施の形態にかかるマスタノードおよびスレーブノードのハードウェア構成を示す説明図である。
【符号の説明】
【０２１１】
４１  論理ＤＢ
５１  ＣＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５４  通信Ｉ／Ｆ
６１  バス
１００  マスタノード
１０１  検索要求受付部
１０２  プラン生成部
１０３  判定部
１０４  更新部
１０５  実行要求部
１０６  転送要求部
１０７  構成管理部
１０８  中間結果管理部
１０９  結果取得部
１２０  記憶部
１２１  スキーマテーブル
１２２  分割情報テーブル
１２３  局所性判定表
１２４  作成判定表
２００ａ、２００ｂ、２００ｃ、２００ｄ  スレーブノード
２０１  実行要求受付部
２０２  実行部
２０３  ＤＢ管理部
２０４  割当部
２０５  中間結果管理部
２０６  中間結果転送部
２０７  転送要求通知部
２０８  構成通知部
２２０  物理ＤＢ
３００  クライアント
【図１】
2008243078.tif 000003
【図２】
2008243078.tif 000004
【図３】
2008243078.tif 000005
【図４】
2008243078.tif 000006
【図５】
2008243078.tif 000007
【図６】
2008243078.tif 000008
【図７】
2008243078.tif 000009
【図８】
2008243078.tif 000010
【図９】
2008243078.tif 000011
【図１０】
2008243078.tif 000012
【図１１】
2008243078.tif 000013
【図１２】
2008243078.tif 000014
【図１３】
2008243078.tif 000015
【図１４】
2008243078.tif 000016
【図１５】
2008243078.tif 000017
【図１６】
2008243078.tif 000018
【図１７】
2008243078.tif 000019
【図１８】
2008243078.tif 000020
【図１９】
2008243078.tif 000021
【図２０】
2008243078.tif 000022
【図２１】
2008243078.tif 000023
【図２２】
2008243078.tif 000024
【図２３】
2008243078.tif 000025
【図２４】
2008243078.tif 000026
【図２５】
2008243078.tif 000027
【図２６】
2008243078.tif 000028
【図２７】
2008243078.tif 000029
【図２８】
2008243078.tif 000030
【図２９】
2008243078.tif 000031
【図３０】
2008243078.tif 000032
【図３１】
2008243078.tif 000033
【図３２】
2008243078.tif 000034
【図３３】
2008243078.tif 000035
【図３４】
2008243078.tif 000036
【図３５】
2008243078.tif 000037
【図３６】
2008243078.tif 000038
【図３７】
2008243078.tif 000039
【図３８】
2008243078.tif 000040
【図３９】
2008243078.tif 000041
【図４０】
2008243078.tif 000042
【図４１】
2008243078.tif 000043
【図４２】
2008243078.tif 000044
【図４３】
2008243078.tif 000045
【図４４】
2008243078.tif 000046
【図４５】
2008243078.tif 000047
【図４６】
2008243078.tif 000048
【図４７】
2008243078.tif 000049
【図４８】
2008243078.tif 000050
【図４９】
2008243078.tif 000051
【図５０】
2008243078.tif 000052
【図５１】
2008243078.tif 000053
【図５２】
2008243078.tif 000054
【図５３】
2008243078.tif 000055
【図５４】
2008243078.tif 000056
【図５５】
2008243078.tif 000057
【図５６】
2008243078.tif 000058
【図５７】
2008243078.tif 000059
【図５８】
2008243078.tif 000060
【図５９】
2008243078.tif 000061
【図６０】
2008243078.tif 000062
【図６１】
2008243078.tif 000063
【図６２】
2008243078.tif 000064
【図６３】
2008243078.tif 000065
【図６４】
2008243078.tif 000066
【図６５】
2008243078.tif 000067
【図６６】
2008243078.tif 000068
【図６７】
2008243078.tif 000069
【図６８】
2008243078.tif 000070
【図６９】
2008243078.tif 000071
【図７０】
2008243078.tif 000072
【図７１】
2008243078.tif 000073
【図７２】
2008243078.tif 000074
【図７３】
2008243078.tif 000075
【図７４】
2008243078.tif 000076
【図７５】
2008243078.tif 000077
【図７６】
2008243078.tif 000078