"データを記憶するデータベースを有する複数のスレーブサーバと、前記データベースの管理情報を記憶し、問合せクエリに基づいて前記データを検索するマスターサーバとが接続される分散データベース検索装置の検索方法であって、前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成するステップと、前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加するステップと、当該分散プランから、前記スレーブサーバに関連するプランを抽出するステップと、前記抽出されたプランに含まれる前記分割クエリ結合演算分及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するステップと、生成された前記ローカルプラン候補に含まれる前記分割クエリ結合演算分及び分割クエリ結合演算に関連するデータの送受信演算を変更した新たなローカルプラン候補を生成するステップと、生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するステップと、前記選択されたローカルプランに基づいて、前記分散プランを更新するステップと、を備える検索方法。データを記憶するデータベースを有する複数のスレーブサーバと、問合せクエリに基づいて前記データベースを検索するマスターサーバとが接続される分散データベース検索装置であって、前記マスターサーバは、前記スレーブサーバの有する各データベースの管理情報を記憶する記憶部と、前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する分散プラン生成部と、前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する分割クエリ結合演算追加部と、前記スレーブサーバから受信したローカルプランに基づいて、前記分散プランを更新する分散プラン更新部と、を具備し、前記スレーブサーバは、前記分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる前記分割クエリ結合演算分及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するローカルプラン候補生成部と、生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するローカルプラン選択部と、を備える分散データベース検索装置。前記サーバ間演算において、送受信されるデータのカラムが前記マスターサーバと前記スレーブサーバとで異なる場合、前記カラムを可変長のデータが記憶されたカラムとするスキーマ変更部を備える請求項2に記載の分散データベース検索装置。データを記憶するデータベースを有する複数のスレーブサーバと接続され、入力された問合せクエリに基づいて前記データベースを検索する分散データベース装置を構成するマスターサーバであって、前記スレーブサーバの有する各データベースの管理情報を記憶する記憶部と、前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する分散プラン生成部と、前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する分割クエリ結合演算追加部と、前記スレーブサーバから受信したローカルプランに基づいて、前記分散プランを更新する分散プラン更新部と、を備えるマスターサーバ。データベースを具備し、入力された問合せクエリに基づいて前記データベースを検索するマスターサーバと複数接続されて分散データベース検索システムを構成するスレーブサーバであって、マスターサーバから受信した分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる前記分割クエリ結合演算分及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するローカルプラン候補生成部と、生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するローカルプラン選択部と、を備えるスレーブサーバ。前記ローカルプラン選択部が算出する前記ローカルプラン候補の演算コストに、前記分割クエリ結合演算追加部で追加された分割クエリ結合演算の演算コストも含める請求項5に記載のスレーブサーバ。データを記憶するデータベースを有する複数のスレーブサーバと、前記データベースの管理情報を記憶し、問合せクエリに基づいて前記データを検索するマスターサーバとが接続される分散データベース検索装置のプログラムであって、コンピュータに、前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する機能と、前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する機能と、前記スレーブサーバから受信したローカルプランに基づいて、前記分散プランを更新する機能と、前記分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる前記分割クエリ結合演算分及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成する機能と、生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択する機能と、を実現させるプログラム。本発明が解決しようとする課題は、マスターサーバ側の仕組みを複雑化することなく効率的な検索を実現する分散データベース検索装置を提供することである。実施形態の分散データベース検索装置は、入力された問合せクエリに基づいてデータベースを検索するマスターサーバと、データベースを具備する複数のスレーブサーバとを接続して構成され、スレーブサーバは、マスターサーバとデータの送受信を行う第2の送受信部と、受信した分散プランに基づいてローカルプラン候補を生成するローカルプラン候補生成部と、生成されたローカルプラン候補に基づいて最も演算コストが低いローカルプランを決定するローカルプラン選択部と、を備える。以下、実施形態の分散データベース検索装置について図面を参照して説明する。第1の実施形態図1は第1の実施形態の分散データベース検索装置の機能構成を示す構成図である。本実施形態の分散データベース検索装置は、ユーザから入力される検索式以下、問合せクエリというに基づいて検索を行い、検索結果を出力する。図1に示すように、本実施形態の分散データベース検索装置は、マスターサーバとして機能する計算機0と、スレーブサーバとして機能する計算機1~計算機Nとが接続して構成されている。マスターサーバである計算機0は、構文解析部11と、クエリ分割部12と、分散プラン生成部13と、分割クエリ結合演算追加部14と、分散プラン更新部15と、分散プラン実行部16と、送受信部17第1の送受信部と、情報記憶部20第1の記憶装置とを備える。情報記憶部20は、スレーブサーバ群情報を格納するスレーブサーバ群情報記憶部21と、後述する分散プランを格納する分散プラン記憶部22とを備える。なお、スレープサーバ群情報とは全てのスレーブサーバの名前や位置、及び登録件数等スレーブサーバが持つデータベースに関する情報であり、スレーブサーバが持つデータベースの情報の一部である。マスターサーバはこのスレーブサーバ群情報に基づいてスレーブサーバにどのデータを送信するかを決定する。構文解析部11は、ユーザから与えられた問合せクエリ51を構文解析する。クエリ分割部12は、問合せクエリ51を分割する機能を備え、構文解析部11による問合せクエリ51の構文解析結果と、スレーブサーバ群情報テーブル21とに基づいて、サーバ内演算及びサーバ間演算の単位で問合せクエリ51を分割する。分割した問合せクエリ51を部分クエリという。なお、サーバ内演算とは問合せクエリ51を各スレーブサーバ内で処理することである。また、サーバ間演算とは複数のスレーブサーバからデータを集めてマスターサーバ内で演算する処理である。分散プラン生成部13は、分散プラン生成手段として機能するものであり、クエリ分割部12により得られた部分クエリと、スレーブサーバ群情報テーブル21の情報とに基づいて分散プランを生成する。すなわち、分散プラン生成部13は、スレーブサーバ群情報記憶部21に格納されているスレーブサーバの名前や位置、及び登録件数等に基づいて、分割されたサーバ内演算とサーバ間演算の、演算順序、演算実行場所及びサーバ間で送受信するデータの内容を決定した分散プランを生成する。なお、サーバ間で送受信するデータの内容とは、例えばスレーブサーバのデータ、スレーブサーバのデータの一部、平均値等のスレーブサーバのデータの演算結果、もしくは最大値や複数のスレーブサーバのデータの組合せ等のサーバ間演算の結果である。分散プラン生成部13は分割クエリ結合演算追加部14と分散プラン更新部15とを備える。分割クエリ結合演算追加部14は、分散プラン生成部13により得られた分散プランを図10のフローチャートに示す分割クエリ結合演算追加処理に従って修正する。以下、修正された分散プランを修正分散プランという。分割クエリ結合演算追加処理については後述する。分散プラン更新部15は、分散プラン更新手段として機能するものでありローカルプラン選択部、スレーブサーバから送られてきたローカルプランに基づいて修正分散プランを更新する分散プラン更新処理を行う。分散プラン修正処理については後述する。分散プラン実行部16は、分散プラン更新部15によって更新された分散プランに基づいて演算を実行する。送受信部17は、データ送受信手段として機能を有する。続いてスレーブサーバである計算機1~Nについて説明する。計算機1~Nはスレーブサーバとして機能するものであり、ローカルプラン選択部31と、ローカルプラン候補生成部32と、ローカルプラン実行部33と、送受信部34第2の送受信部と、情報記憶部40第2の記憶装置とを備える。情報記憶部40は、格納したデータのスキーマ情報や件数等の統計情報などのデータベースに格納されたデータに関する情報であるデータベース情報を保持するデータベース情報記憶部41と、ローカルプランを保持するローカルプラン記憶部42と、検索対象の実際のデータ以下、格納データというを保持する格納データ記憶部43と、を備える。ローカルプラン選択部31は、ローカルプラン生成手段として機能するものであり、ローカルプラン候補生成部32を備える。ローカルプラン選択部31は、分割クエリ結合演算追加部14により得られた修正分散プランの内、自身のサーバに関連する部分プランからなるローカルプランを生成する。ローカルプラン選択部が生成したローカルプランに基づいて、ローカルプラン候補生成部3がローカルプランの候補をさらに作成する。ローカルプラン選択部31は、自身が作成したローカルプランとローカルプラン候補生成部32に作成されたローカルプラン候補の中から、見積もり実行時間または見積もり実行計算量からなる演算コストを計算する。ローカルプラン選択部31は、算出した演算コストが最小となるプランをローカルプランとして決定する。ローカルプラン実行部33は、ローカルプラン選択部31によって得られたローカルプランに基づいて演算を実施する。送受信部34はマスターサーバの送受信部17と同一の機能を持つ。ここで、図2及び図3に、スレーブサーバの格納データ記憶部43に登録されるデータの一例を示す。なお、本実施形態のスレーブサーバの格納データ記憶部43に登録されるデータはXMLフォーマット形式で記述されている。なお、図2に示すデータは、書籍の発行年数、タイトル、著者、価格に関するデータである。図3に示すデータは、ある賞の受賞年度、受賞者、受賞した書籍のタイトル、受賞者の性別に関するデータである。図4は、スレーブサーバのデータ情報記憶部41が保持するデータベースの情報の一例である。図4に示すように、データベース情報は、登録ノード112と、登録数113と、索引情報114の項目を有するデータベース情報テーブル111として保持される。登録ノード112は、スレーブサーバの格納データ記憶部43に登録されたXMLデータが有するノード名を示すものであり、ここではどのノードの下にあるかを含めて記述する。なお、ノードとはXMLデータを構成する要素や属性などである。登録数113は、スレーブサーバの格納データ記憶部43に登録されたXMLデータ中に各登録ノード112が出現した回数を示す。索引情報114は、登録ノード112に対して設定した索引の種類を記述したものである。索引の種類は、例えば数値索引や文字索引である。なお、図4には、一例として計算機1乃至計算機4のデータベース情報テーブル111-1~111-4を示している。図5は、マスターサーバである計算機0が保持するスレーブサーバ群情報記憶部21に保存されたスレーブサーバ群情報21の一例である。図5に示すように、スレーブサーバ群情報はサーバ名122、Collection情報123、登録文書数124という項目を有するスレーブサーバ群情報テーブル121として保持される。サーバ名122にはスレーブサーバの名称が格納される。Collection情報123には登録するXMLデータの格納場所の名前以下、Collection名というが格納される。本実施形態の分散データベースは異なるスレーブサーバでも同じCollection情報123を持つことができるため、ユーザはCollection名を指定することで特定のXMLデータの集合内を検索することが可能となる。登録文書数124はCollectionに登録されたXMLデータの数が格納される。ここで、図6乃至図25を参照して、本実施形態の分散データベース検索装置の処理について説明する。図6は、本実施形態の分散データベース検索装置の検索処理の一例を示すフローチャートである。なお、本実施形態の分散データベース検索装置は、計算機1~4のデータベース情報記憶部41に、図4に示したデータベース情報が格納されているとする。まず、ユーザによってマスターサーバに検索式である問合せクエリ51が入力されるステップS1。ここで、図7に、ユーザによって入力される問合せクエリ51の一例を示す。図7に示す問合せクエリ51は、XMLデータの問い合わせ言語であるXQueryによって記述されている。なお、図7に示す問合せクエリ51は、過去の受賞歴がある男性作家の著書のうち1990年以降に出版された本のタイトルと値段を出力せよという意味である。入力された問合せクエリ51の1行目のforから始まる1文はpublisherというCollectionに登録されているbookの名前を持つノードのうち、属性ノードyearの値を数値化したものが1990以上のノードを変数xに格納している。これにより1990年以降に出版した本の一覧を取得している。なお、XQueryにおいて変数はで始まる文字列として表現される。次に2行目のforから始まる1文はprizeWinnersというCollectionに登録されているprizeWinnerの名前を持つノードのうち、genderという子ノードの値を文字列化したものがmaleという文字列と等しいものを選択した後、その子ノードであるnameを変数yに格納しており、これにより受賞歴のある男性作家の名前の一覧を取得している。次に3、4、5行目のletから始まる1文で1行目に取得したbookの子ノードであるauthor、title、priceのノードを各々変数z、u、vに格納しており、これにより本の著者名とタイトルと値段を取得している。次に6行目のwhereから始まる1文で男性作家の名前と本の著者名が一致するものの組合せを取得している。最後に7行目のreturnから始まる1文で、6行目で取得した組合せに対してListの名前のノードで囲んだXMLを作りだしてユーザに返却している。これにより条件を満たした本のタイトルと値段を取得している。図7に示す問合せクエリ51がマスターサーバに入力されると、マスターサーバの構文解析部11は、問合せクエリ51を構文解析するステップS2。構文解析部11による構文解析結果は、マスターサーバのクエリ分割部12に送信される。構文解析結果を受信したクエリ分割部12は、スレーブサーバ群情報テーブル21の情報に基づいて、問合せクエリ51を各スレーブサーバ内で処理するサーバ内演算及び複数スレーブサーバからデータを集めて演算するサーバ間演算の単位の部分クエリに分割する問合せクエリ51分割処理を行うステップS3。すなわち、クエリ分割部12は、構文解析部11の構文解析の結果に基づいて、問合せクエリ51を部分クエリに分割する。クエリ分割部12は、スレーブサーバ群情報テーブル121を参照して、これらの部分クエリ毎に、部分クエリの内容がサーバ間演算かサーバ内演算を判定する。ここで、クエリ分割部12による分割結果である部分クエリの一覧である部分クエリ一欄テーブル131の一例を図8に示す。図8に示した部分クエリ一覧テーブル131は、部分クエリに順次振られる番号を格納する番号132、分割して得られた部分クエリを格納する部分クエリ内容133、部分クエリがサーバ内演算かサーバ間演算であるかを格納するサーバ間/サーバ内演算134、演算に必要なデータを保存した計算機名を格納する対応サーバ135の項目を有する。以下に、クエリ分割部12による問合せクエリの分割処理について、図7乃至図8を参照して具体的に説明する。クエリ分割部12は、スレーブサーバ群情報テーブル121に基づいて、部分クエリごとの演算に用いるデータを保持する計算機を特定する。図8では図7に示した問合せクエリ51におけるCollectionpublisherとCollectionprizeWinnerの2つのCollection情報に着目する。すなわち、これらのCollection情報を用いて図5に示したスレーブサーバ群情報テーブル121を検索する。すなわち、クエリ分割部12は、Collectionpublisherは計算機1乃至3に存在し、CollectionprizeWinnerは計算機4に存在すると判定する。さらにクエリ分割部12はCollectionに対して実施する/、//、>=、=といったXQueryの演算に注目し、演算が複数の異なる計算機からの値が必要かどうかを判定する。演算が複数の異なる計算機からの値を必要とする場合、この演算をサーバ間演算と判定する。なお、一つの計算機からの値で行われる演算の場合、この演算をサーバ内演算と判定する。図8に示すように、問合せクエリ51においては/、//、>=1990といった演算は全て入力となったデータの計算機上で実施できるためx、z、u、vは全て同一計算機上に演算したデータが格納される。なお、サーバ内演算については幾つかの演算単位で分割する。図8ではfor、letといった代入文が発生する単位で分割しており番号1~5の部分クエリが発生する。なお、for、letという代入文の単位で分割したのは1例であり、実際にはもっと細かい演算単位で分割しても良いし、もっと大きな演算単位で分割しても良い。一方、wherey=zという演算において、yは計算機4のデータであり、zは計算機1から3にあるデータであるためサーバ間演算であるとする。続いて、次のreturn<List>{u}{v}</List>の演算は最終結果を返却する演算であるため、u、vのデータを持つ計算機1から3のデータを集めて演算するサーバ間演算が必要だと判定する。続いて、分散プラン生成部13が、図8に示した部分クエリ一覧テーブル131と図5に示したスレーブサーバ群情報テーブル121とに基づいて分散プランを生成するステップS4。生成した分散プランは分散プランテーブル141に格納される。図9に、分散プランテーブル141の一例を示す。分散プランテーブル141は演算番号142、部分クエリ番号143、演算内容144、事前実行演算番号145、実行場所146、送信場所147、入力変数148、出力変数149の項目を有する。演算番号142は、演算毎に割り当てられた番号を示す。部分クエリ番号143は、図8に示した部分クエリテーブル131における部分クエリ番号132の項目で割り当てられた番号を格納する。部分クエリ番号132が割り当てられていない場合は空欄とする。演算内容144は、各演算の内容を格納する。ここでは、分散プラン生成部13は、図8に示した部分クエリ一覧テーブル131におけるサーバ内演算は、そのままサーバ内演算とし、部分クエリ一覧テーブル131におけるサーバ間演算は、具体的な操作を表す演算内容を記述する。さらに、部分クエリ一覧テーブル131におけるサーバ間演算の前後では、データの送信、データ受信の演算が必要となるため、新たに加える。事前実行演算番号145は、その演算を実行する前に必ず実行しなければならない演算がある場合に、その演算番号を格納する。実行場所146は、演算を実行する場所計算機を格納する。データの送信とデータ受信の演算の場合は、演算結果のデータの送信先を送信場所147に格納する。すなわち、実行場所146はデータの送信元の計算機であり、送信場所147はデータの送信先の計算機である。入力変数148は、演算に入力データが必要な場合に格納され、そのデータが格納された変数の名前のリストを格納する。出力変数149は、演算が新しい値を作成する場合、その格納先の変数の名前のリストを格納する。なお、図9に示した分散プランテーブル141の演算番号1乃至5は、図8に示した部分クエリ一覧テーブル131の番号1乃至5に対応する。また、分散プランテーブル141の演算番号10及び11は、図8に示した部分クエリ一覧テーブル131の番号6、7に対応する。また、部分クエリ一覧テーブル131でサーバ内/サーバ間演算134にサーバ間演算と格納されている部分クエリ番号6の演算は、演算内容144にサーバ間JOINと格納される。すなわち、部分クエリ内容133に基づいた具体的な演算内容が格納される。同様に、部分クエリ番号7の演算は、演算内容144に返却データ作成という具体的な演算が格納されている。なお、サーバ間JOINとは2つの変数に格納されたデータのうち値の等しい組合せを残す演算であり、返却データ作成とは入力されたデータを利用して新しいXMLデータを作る演算である。分散プラン生成部13は、サーバ間演算にのみ着目し、実行順序や実行場所を決定する。具体的には、図9に示した分散プランテーブル141は、サーバ間演算の演算内容144はサーバ間JOINと返却データ作成の2種類であるため、返却データ作成演算はサーバ間JOINを実行した後の方が対象となるデータが少なくなり効率が良いと判断する。また、本実施形態では、サーバ間演算はマスターサーバで実施するものとして実行場所を決定する。なお、サーバ間演算をマスターサーバで実行するためには各スレーブサーバにあるデータを集める必要がある。そのため分散プラン生成部13は、分散プランテーブル141の演算番号6および演算番号8を追加し、それぞれの演算内容144にスレーブサーバがマスターサーバにデータを送る演算であるデータ送信を格納する。続いて、演算番号6および8において送信されたデータをマスターサーバが受信するために、演算番号7および9を追加し、それぞれの演算内容144にマスターサーバがスレーブサーバからデータを受信する演算であるデータ受信を格納する。なお、本実施形態ではサーバ間演算をマスターサーバで実行するように決定しているが、マスターサーバではなく、例えば複数のスレーブサーバで実行するように決定しても良い。分散プラン生成部13は、図8に記載した部分クエリ内容133に基づいて、入力変数148および出力変数149を格納する。例えば、for~in、let~:=の~に書かれた変数が出力変数149であり、それ以外の場所で書かれた変数は入力変数148とする。また、データ送信演算においては入力変数148が出力変数149になる。さらにデータ受信演算においてはデータ送信演算の出力変数149が入力変数148と出力変数149になる。なお、サーバ内演算は、分散プラン生成部13によって順序関係が崩れないように任意の順序に配置される。このように、本実施形態の分散プラン生成部13は、部分クエリ一覧テーブル131のサーバ間演算のみを検討する。これにより検討範囲が限定されるため、分散プラン生成部131は容易に分散プランを生成可能である。次に、分割クエリ結合演算追加部14が、分散プラン生成部13が生成した分散プランに対して分割クエリ結合演算を追加し、分散プランの修正を行う分割クエリ結合演算追加処理を行うステップS5。ここで、図10を参照して、分割クエリ結合演算追加部14が、図9に示した分散プランテーブル141に格納された分散プランに対して、分割クエリ結合演算追加処理を行う際の動作について具体的に説明する。なお、この分割クエリ結合演算追加処理ではiおよびjという変数を用いる。iは1以上の整数であり、対象の分散プランの演算番号以下である1≦i≦分散プランの演算番号の最大値。また、分割クエリ結合演算追加処理の開始時点ではi=1である。また、分散プランの演算番号の最大値をmaxとする。また、演算番号142がiの分散プランの演算を演算Eとする。なお、jはiと同様の性質の変数であり、演算番号142がjの分散プランの演算を演算Sとする。分割クエリ結合演算追加部14は、分散プラン生成部13から分散プランを受信すると、まず、初期化処理としてi=1、分散プランの演算番号の最大値=maxとするステップS10。分割クエリ結合演算追加部14は、図9に記載した分散プランテーブル141における演算番号iの演算Eを取得するステップS20。次に、分割クエリ結合演算追加部14は、取得した演算Eがサーバ間演算であり、かつi≠maxであるか否かを判定するステップS30。取得した演算Eがサーバ間演算であり、かつi≠maxである場合、すなわち演算Eが最後の演算以外の場合ステップS30がYes、j:=1とするステップS40。次に、分散プランテーブル141の演算番号jの演算Sを取得するステップS50。分割クエリ結合演算追加部14は、演算Sの演算内容144がデータ送信であり、かつ送信場所147に格納された計算機がスレーブサーバであるか否かを、図9の分散プランテーブル141を参照して判定するステップS60。演算Sの演算内容144がデータ送信であり、かつ送信場所147の計算機がスレーブサーバの場合ステップS60がYes、分割クエリ結合演算追加部14は、演算Sの入力変数147と演算Eの入力変数147とに共通して現れる変数を格納したリスト以下、varListというを作成するステップS70。次に演算Sの入力変数147からvarListにある変数を除いた変数を格納したリスト以下、newVarListというを作成するステップS80。分割クエリ結合演算追加部14は、作成したvarListが空でなく、かつこのvarListに含まれる変数が、演算Sの入力変数147と完全に一致しない、かつvarlistの変数を出力する演算とnewVarListの変数を出力する演算とが並列実行可能かを判定するステップS90。なお、ここで図9に示した分散プランテーブル141において、varlistの変数を出力する演算とnewVarListの変数を出力する演算とが並列実行可能かどうかの判定方法について説明する。この方法は、一方の演算の事前実行演算番号145及びこの事前実行演算番号145の演算の事前実行演算番号145を繰り返し遡って調べた際に、もう一方の演算が事前実行演算番号として存在しない場合に、2つの演算は並列実行可能と判定する。すなわち、演算Aの事前実行演算番号145に演算Bの演算番号がある場合は、演算Bを実行した後に演算Aを実行しなくてはいけないため、並列実行できないと判定する。図10のステップS90の説明に戻る。varListが空でなく、かつこのvarListに含まれる変数が、演算Sの入力変数147と完全に一致しない、かつvarlistの変数を出力する演算とnewVarListの変数を出力する演算とが並列実行可能な場合ステップS90がYes、次の5つの演算を演算Eの後に挿入し、挿入後、iにi5を代入するi:=i5ステップS100。1つ目の演算は、演算内容144がデータ送信、入力変数148と出力変数149がvarListに含まれる変数、実行場所146が演算Sの送信場所147、送信場所147が演算Sの実行場所146である。2つ目の演算は、演算内容144がデータ受信、入力変数148と出力変数149がvarListに含まれる変数、実行場所146が演算Sの送信場所147、送信場所147が演算Sの実行場所146である。3つ目の演算は、演算内容144が分割クエリ結合、入力変数148がvarListに含まれる変数、実行場所146が演算Sの実行場所146である。なお、演算内容が分割クエリ結合とは、ある変数に対して別々に並行して処理を行った結果を再び1つにする演算である。4つ目の演算は、演算内容144がデータ送信、入力変数148と出力変数149がnewVarListに含まれる変数、実行場所146が演算Sの実行場所146、送信場所147が演算Sの送信場所147である。5つ目の演算は、演算内容144がデータ受信、入力変数148と出力変数149がnewVarList、実行場所146が演算Sの実行場所146送信場所147が演算Sの送信場所である。次に、演算Sで送信する変数を変更するために3つの処理を実施するステップS110。1つ目は演算Sの入力変数148と出力変数149の内容をvarListの値に変更する。2つ目は演算Sの次の演算Rを取得する。演算Rは演算Sに対応する演算内容144データ受信の演算である。3つ目にRの入力変数148と出力変数149リストの内容をvarListの値に変更する。その後ステップS120へ進む。なお、演算Sがデータ送信ではない、または実行場所146の計算機がスレーブサーバでない場合ステップS60がNoも、ステップS120へと進む。またvarListが空、または演算Sの入力変数リストと完全に一致する、かつvarlistの変数を出力する演算とnewVarListの変数を出力する演算とが並列実行可能でない場合ステップS90がNoの場合も、ステップS120に進む。ステップS120では、分割クエリ結合演算追加部14は、jにj1を代入するj:=j1ステップS120。すなわち、ステップS120はステップS60がNoの場合もしくはステップS90がNoの場合もしくはステップS110に続いて行われる。ステップS120に続いて、分割クエリ結合演算追加部14は、jがiより小さいかを判定するステップS130。jがiより小さい場合ステップS130がYesはステップS50に戻り処理を繰り返す。jがiより小さくない場合ステップS130がNoはステップS140に進みiにi1を代入するi:=i1ステップS140。演算Eがサーバ間演算ではない、またはi=maxの場合ステップS30がNo、ステップS140に進む。すなわち、ステップS140の処理はステップS130がNoの場合もしくはステップS30がNoの場合に続いて行われる。ステップS140に続いて、分割クエリ結合演算追加部14は、iがmax以下かを判定するステップS150。すなわち、すべての部分クエリに対して分割クエリ演算追加処理を行ったかを判定する。iがmax以下である場合ステップS150がYes、分割クエリ結合演算追加部14は、ステップS20に戻り処理を繰り返す。iがmaxよりも大きい場合ステップS150がNo、分割クエリ結合演算追加部14は処理を終了する。ここで、図11に、図9に示した分散プランに対して、分割クエリ結合演算追加部14が上述した分割クエリ結合演算追加処理を行った結果、修正された分散プラン以下、修正分散プランというの一例を示す。図9の分散プランテーブル141に記載された分散プランは、演算1乃至10はサーバ間演算ではないため、分割クエリ結合演算追加部14、はiが10になるまで1ずつ増やしていく図10のステップS20、ステップS30、ステップS140、ステップS150。i=10になると、演算Eがサーバ間演算であるためステップS30がYes、変数jに1を代入するステップS40。なお、演算Eがサーバ間演算かどうかの判定は、演算Eの部分クエリ番号に基づいて分散プランテーブル141を参照して行われる。次にjが6になるまではデータ送信ではないためjを1ずつ増やしていくステップS50、ステップS60がNo、ステップS120、ステップS130。jが6になると、演算Sの演算内容がデータ送信で実行場所146の計算機がスレーブサーバであるためステップS60がYes、演算番号6の入力変数148と演算番号10の入力変数148に共通で現れる変数zを格納した変数リストvarListを作成するステップS70。取得した演算番号6の入力変数148からvarListの変数リストを除いた変数u、変数yを格納した変数リストnewVarListを作成するステップS80。varListが空ではなく、演算番号6の入力変数リストとも完全に一致しない、かつvarlistとnewVarListの変数を出力する演算が並列実行可能であるため図11の演算番号11-15の5つの演算を追加した後iを5加えて15を代入するステップS90、ステップS100。次に演算番号6のデータ送信と演算番号7のデータ送信の入力変数148と出力変数149にvarListの値変数zを代入するステップS110。次にjが8になるまではデータ送信ではないため単純に変数jを1ずつ増やしていくステップS50、ステップS60、ステップS120、ステップS130。jが8の場合は演算内容144がデータ送信で実行場所146がスレーブサーバであるため、演算番号8の入力変数と演算番号10の入力変数リストに共通で現れる変数y格納した変数リストvarListを取得するステップS70。取得したvarListは空ではないが、演算番号8の入力変数リストと完全に一致するためステップS90がNo、jに1を加えるステップSS120。以降データ送信演算はないためiを1増やして16を代入するステップS120、ステップS130、ステップS140、ステップS150。次にiが16における演算はサーバ間演算であるが、iがmaxと等しいためステップS150がYes、ステップS20にもとり、処理を繰り返す。そして、iの値がmaxを超えるとステップS150がNo、分割クエリ結合演算追加部14は処理を終了する。その結果、分散プランが作成される。図11に修正された分散プランのテーブル151を示す。すなわち、分散プラン結合演算追加部14は、サーバ間演算とその他の演算はできるだけ並列に実行して、後で結合する形にプランを書き換える。上述したように、分割クエリ結合演算追加部14が分散プランを修正すると、マスターサーバの送受信部17はスレーブサーバに修正された修正分散プランを送信する。このとき、全てのスレーブサーバに修正分散プランを送信してもよい。また、実行場所を参照して、関連のあるスレーブサーバにのみ修正分散プランを送信してもよい。スレーブサーバのローカルプラン選択部31は、受信した分割クエリ結合手順追加部14により修正された分散プランの内、自身のサーバに関連する部分に対するローカルプラン候補を生成するステップS6。ここで、ローカルプラン選択部31によって生成されたローカルプランの候補を図12に例示する。図12に示したローカルプラン候補2は、計算機2であるスレーブサーバのローカルプラン選択部31が、図11に記載した分散プランと図4に記載したデータベース情報111とに基づいて生成した、計算機2に関するローカルプラン候補の一例である。図12に示したローカルプラン候補2示すように、ローカルプラン候補2は演算番号302、部分クエリ番号303、演算内容304、事前実行演算番号305、実行場所306、送信場所307、入力変数308、出力変数309の項目を有する。なお、本実施形態のローカルプラン候補および後述するローカルプランが有する項目302~309は、本実施形態の分散プランテーブルが有する項目142~149と同一である。なお、図12に示したローカルプラン候補2において、計算機2では図4のデータベース情報からのbookの下のyear属性ノードに対して数値索引が設定されている。そのため、最初の演算番号1で部分クエリ番号1の部分クエリに該当する処理を演算数値索引によって実現する。演算数値索引はノードが持つ値を数値化したものを索引化した数値索引を設定したノードに対して、与えられた数値との比較条件を満たすノード若しくはそのノードを所有する文書の最初のノードを高速に取得する演算である。具体的には、ローカルプラン選択部31は、属性ノードyearの値が1990以上の条件を満たすbookノードを数値索引内から探し出して変数xに格納する。演算番号2、4、5は各々部分クエリ番号3、4、5の部分クエリを処理する演算TRAVERSEトラバースを実施する。なお、演算TRAVERSEとはXML内の或るノード入力から或るノード出力へ辿っていく演算である。具体的には演算番号1で求めたxに格納されたbookノードから、子ノードであるauthor、title、priceを取得して各々変数z、u、vに格納する。演算番号3、6、7、8は分散プランで作成したデータ送信、データ受信、分割クエリ結合演算をそのまま残したものである。次に、図13を参照して、図12のローカルプラン候補2に基づいてローカルプラン候補生成部32がさらにローカルプラン候補を生成するローカルプラン候補生成処理について説明する図6のステップS7。図13はローカルプラン候補生成処理の一例を示すフローチャートである。なお、このローカルプラン候補生成処理はiという変数を用いる。iは1以上であり、かつ、対象のローカルプラン選択部31が生成したローカルプラン候補のリスト以下、inputPlanListという内の要素数以下である1≦i≦inputPlanList内の要素数。まず、ローカルプラン候補生成部32は、図12に示すローカルプラン候補を取得するステップS200。ローカルプラン候補生成部32は、i=1、inputPlanList内の要素数=maxとするステップS210。続いてローカルプラン候補生成部32はinputPlanListからi番目のローカルプラン候補planを取得するステップS220。ローカルプラン候補生成部32は、取得したplanに基づいて、後述する分割クエリ結合の実施変数の組合せパターン生成処理を実施し、このplanを含む新規のローカルプラン候補リストを作成するステップS230。分割クエリ結合の実施変数の組合せパターン生成処理とは、分割クエリ結合前後で実施する演算を変化させて様々なローカルプラン候補を生成する処理であり、図14のフローチャートにより詳細を後述する。ローカルプラン候補生成部32は、分割クエリ結合の実施変数の組合せパターン生成処理によって得られた新規のローカルプラン候補リスト以下、nextPlanListというを取得するステップS240。ここで、jという変数を用いる。jは1以上であり、かつ、nextPlanList内の要素数以下である1≦j≦nextPlanList内の要素数。また、この時j=1であり、nextPlanList内の要素数=finalMaxとするステップS250。次に、ローカルプラン候補生成部32は、nextPlanListからj番目のローカルプラン候補nextPlanを取得するステップS260。ローカルプラン候補生成部32は、取得したnextPlanに基づいて分割クエリ結合の実施場所パターン生成処理を実施しnextPlanを含む新規のローカルプラン候補リストを作成するステップS270。分割クエリ結合の実施場所パターン生成処理とは、分割クエリ結合演算の実行場所を変化させることで様々なローカルプラン候補を生成する処理であり、図15のフローチャートにより詳細を後述する。ローカルプラン候補生成部32は、分割クエリ結合の実施場所パターン生成処理結果に基づいて新規のローカルプラン候補リストfinalPlanListを作成するステップS280。作成したfinalPlanList内のローカルプラン候補を最終出力である出力候補プランリストoutputListに追加するステップS290。次に、ステップS300に進み、jにj1を代入するj:=j1ステップS300。ローカルプラン候補生成部32は、このjがfinalMax以下であるかを判定するステップS310。jがfinalMax以下の場合ステップS310がYes、ステップS260に戻り処理を繰り返す。jがfinalMaxより大きい場合ステップS310がNo、ステップS320に進みiにi1を代入するi:=i1ステップS320。次にiがmax以下かを判定するステップS330。iがmax以下の場合ステップS330がYesはステップS220に戻り処理を繰り返す。iがmaxよりも大きい場合は終了する。最終出力はoutputListに格納されたローカルプラン候補リストであり、ローカルプラン選択部31はこのローカルプラン候補リストの中から最終的に1つのローカルプランを選択する。次に、図14のフローチャートに従って、ローカルプラン候補生成部32による、図13のステップS230における分割クエリ結合の実施変数の組合せパターン生成処理について説明する。なお、この分割クエリ結合の実施変数の組合せパターン生成処理はiという変数を用いる。iは1以上であり、かつ、入力対象のローカルプラン候補planの演算番号以下である1≦i≦planの演算番号の最大値。まず、ローカルプラン候補生成部32は、planを最終出力である一時候補リストnextPlanListに登録するステップS400。また、ローカルプラン候補生成部32は、i=1、planの演算番号の最大値=maxとするステップS410。続いて、ローカルプラン候補生成部32は入力されたローカルプラン候補planの演算番号iの演算Eを取得するステップS420。取得した演算Eが分割クエリ結合演算の場合ステップS430がYes、planの演算番号i1番目のデータ送信演算Sを取得し、さらに演算Sの入力変数の全組合せパターンのリストvarPatternListを取得するステップS440。次に、j:=1とし、nextPlanList内の要素数=nextMaxとするステップS450。次に、nextPlanListのj番目のプランnextPlanを取得するステップS460。次に、k:=1とし、varPatternList内の要素数=vtMaxとするステップS470。次に、nextPlanの内容をコピーした新しいローカルプラン候補newPlanを作成するステップS480。次に、ローカルプラン候補生成部32は、次の3つの処理を実施するステップS490。1つ目はvarPatternListのk番目の要素targetVarsを取得する処理であり、2つ目はnewPlanの演算番号i1番目のデータ送信演算ASを取得する処理であり、3つ目はnewPlanの演算番号i-1番目のデータ受信演算ARを取得する処理である。次に演算ASの入力変数リストとtargetVarsの内容が一致するかを判定するステップS500。演算ASの入力変数リストが空の場合ステップS500がYes、演算E、演算AS、演算ARは不要であるため各演算内容をdummyに変更する。dummyは何もしない演算であり、後で削除する。ここでは演算番号がずれるため削除しない。次に、分割クエリ結合をしない変数を事前に送るように、演算Eより前にあるデータ送信演算の入出力変数と事前実行演算番号を変更するために次の4つの処理を実施するステップS520。1つ目は演算Eの入力変数を入力変数とするデータ送信演算BSを取得する処理であり、2つ目はBSの入出力変数リストへtargetVarsに含まれる変数を追加する処理であり、3つ目はtargetVarsの変数を出力する演算の演算番号リストpreExeListを取得する処理であり、4つ目はBSの事前実行演算番号にpreExeListの値を代入する処理である。ローカルプラン候補生成部32は、ステップS520の処理を行ったnewPlanをnewPlanListに追加するステップS530。その後、kにk1を代入しk:=k1ステップS540、kがvtMax以下であるかを判定するステップS550。kがvtMax以下の場合ステップS550がYes、ステップS480に戻り処理を繰り返す。kがvtMaxより大きい場合ステップS550がNo、ステップS560に進みjにj1を代入するj:=j1ステップS560。ローカルプラン候補生成部32は、jがnextMax以下であるかを判定するステップS570。jがnextMax以下の場合ステップS570がYes、ステップS460に戻り処理を繰り返す。jがnextMaxより大きい場合ステップS570がNo、ステップS580に進みnewPlanList内の要素をnextPlanListに全て移すステップS580。その後、ステップS590へと進み、iにi1を代入するi:=i1ステップS590。なお、演算Eが分割クエリ結合ではない場合もステップS430がNo、ステップS590に進みiにi1を代入するi:=i1ステップS590。すなわちステップS590の処理はステップS430がNoまたはステップS580に続いて行われる。ローカルプラン候補生成部32は、iがmax以下であるかを判定するステップS600。iがmax以下の場合ステップS600がYes、ステップS420に戻り処理を繰り返す。iがmaxより大きい場合は終了する。処理の終了後の最終出力はnextPlanListに格納されたローカルプラン候補リストであり、図13のステップS240に戻ってローカルプラン候補生成部32の処理が続けられる。次に、図15のフローチャートに従って分割クエリ結合の実施場所パターン生成処理について説明する。なお、この分割クエリ結合の実施場所パターン生成処理はiという変数を用いる。iは1以上であり、かつ、入力対象のローカルプラン候補nextPlanの演算番号以下である1≦i≦nextPlanの演算番号の最大値。ローカルプラン候補生成部32は、nextPlanを最終出力である最終候補リストfinalPlanListに登録するステップS700。また、処理の開始時点ではi=1、nextPlanの演算番号の最大値=maxとするステップS710。まず、分割クエリ結合の実施場所パターン生成処理は入力されたローカルプラン候補nextPlanの演算番号iの演算Eを取得するステップS720。取得した演算Eが分割クエリ結合演算の場合ステップS730がYes、nextPlanの演算番号i1番目の演算Sを取得するステップS740。次に、j:=1とし、finalPlanList内の要素数=finalMaxとするステップS750。次に、finalPlanListのj番目のプランfinalPlanを取得するステップS760。次に、finalPlanの内容をコピーした新しいローカルプラン候補newPlanを作成するステップS770。次にローカルプラン候補生成部32は、分割クエリ結合の実行場所をマスターサーバに変更するために次の5つの処理を実施するステップS780。1つ目は分割結合演算Eの直後の送信データ演算Sを取得する処理である。2つ目は分割クエリ結合演算Eの直前の受信データ演算Rを取得する処理である。3つ目は演算Rの演算内容を送信データ演算に、入出力変数にSの入力変数を追加したものに、実行場所を演算Sの送信先→Sの送信元に変更する処理である。4つ目の処理は不要になった演算Sの演算内容をdummyに変更する処理である。5つ目の処理は、演算Eの実行場所をSの送信元に変更する処理である。次に、ステップS790に進みステップS780で修正したnewPlanを新規プランリストnewPlanListに追加するステップS790。次に、ステップS800に進みjにj1を代入するj:=j1ステップS800。次にjがfinalMax以下であるかを判定するステップS810。jがfinalMax以下の場合ステップS810がYes、ステップS760に戻り処理を繰り返す。jがfinalMaxより大きい場合ステップS810がNo、ステップS820に進みnewPlanList内の要素を全てfinalPlanListに移すステップS820。さらにステップS830へと進む。また演算Eが分割クエリ結合ではない場合もステップS730がNo、ステップS830に進みiにi1を代入するi:=i1ステップS830。すなわちステップS830の処理はステップS730がNoまたはステップS820に続いて行われる。次にiがmax以下であるかを判定するステップS840。iがmax以下の場合ステップS840がYes、ステップS720に戻り処理を繰り返す。iがmaxより大きい場合はステップS850に進む。ステップS850はfinalPlanList内にある全てのローカルプラン候補内の演算で、演算内容がdummyとなっているものを削除して終了するステップS850。最終出力はfinalPlanListに格納されたローカルプラン候補リストであり、図13のステップS280に戻ってローカルプラン候補生成部32の処理が続けられる。図12に示したローカルプラン候補2が、ローカルプラン選択部31で得られたローカルプラン候補の場合において、上述したローカルプラン候補生成処理が行われた結果、得られる新たなローカルプラン候補2-1乃至2-6を図16乃至図21に示す。ローカルプラン候補生成部32が、これらのローカルプラン候補2-1乃至2-6を生成する処理を具体的に説明する。まず、図12のローカルプラン候補2が、分割クエリ結合の実施変数の組合せパターン処理の入力として渡される図13のステップS200、S210、S220、S230。次に分割クエリ結合の実施変数の組合せパターン処理において、入力された図12のローカルプラン候補2以下、planとするを一時候補リスト以下、nextPlanListとするに登録する図14のステップS400。次にplanではiが7になるまでは分割クエリ結合演算ではないので変数iを1ずつ増やしていくステップS420、S430、S550、S540。iが7の時の演算Eは分割クエリ結合であるため演算番号が8の演算Sを取得し、Sの入力変数u、vの全組合せとして3つの組合せu、v、u、vをvarPatternListに格納するステップS440。次に、j:=1としてnextPlanList内の1番目の要素として最初に登録した図12のplanをnextPlanとして取得するステップS450、S460。次にnextPlanをコピーしたnewPlanを作成するステップS480。次に、varPatternListの1番目の要素uを取得し、newPlanの演算番号8のデータ送信演算ASと演算番号6のデータ受信演算ARを取得するステップS490。ASの入力変数u、vとuは一致しないため、分割クエリ結合の入力変数を送信する演算番号3のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数uを追加する。さらに変数uを出力する演算番号4を演算番号3の事前実行演算番号に追加するステップS500、S520。これによって得られたnewPlanをnewPlanListに追加するステップS530。newPlanであるローカルプラン候補2-1の内容を図16に示す。但し図16に示したローカルプラン候補2-1では演算内容dummyの演算は削除済みである。次にkに2を代入し再び図12のplanをコピーしたnewPlanを作成するステップS480。次に、varPatternListの2番目の要素vを取得し、newPlanの演算番号8のデータ送信演算ASと演算番号6のデータ受信演算ARを取得するステップS490。ASの入力変数u、vとvは一致しないため、分割クエリ結合の入力変数zを送信する演算番号3のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数vを追加する。さらに変数vを出力する演算番号5を演算番号3の事前実行演算番号に追加するステップS500、S520。これによって得られたnewPlanをnewPlanListに追加するステップS530。newPlanであるローカルプラン候補2-2の内容を図17に示す。但し図17に示したローカルプラン候補2-2では演算内容dummyの演算は削除済みである。次にkに3を代入し再び図12のplanをコピーしたnewPlanを作成するステップS480。次に、varPatternListの3番目の要素u、vを取得し、newPlanの演算番号8のデータ送信演算ASと演算番号6のデータ受信演算ARを取得するステップS490。ASの入力変数u、vとvarPatternListの3番目の要素u、vは完全に一致するため、演算E、AS、ARの演算内容をdummyに変更するステップS510。次に分割クエリ結合の入力変数を送信する演算番号3のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数u、vを追加する。さらに変数u、vを出力する演算番号4、5を演算番号3の事前実行演算番号に追加するステップS520。これによって得られたnewPlanをnewPlanListに追加するステップS530。このnewPlanであるローカルプラン候補2-3の内容を図18に示す。但し図18に示したローカルプラン候補2-3では演算内容dummyの演算は削除済みである。次にkに4を代入するステップS540。次にvarPatternListは要素数が3までしかないためjに2を代入するステップS590、S580。次にnextPlanListは要素数が1しかないため、今まで得られたnewPlanList内の3つのローカルプラン候補図16、17、18に示したローカルプラン候補をnextPlanListに移すステップS570、S560。nextPlanListはこの時点で図12、図16乃至図18のローカルプラン候補を要素として持つ。次にiに8以降の値を代入しても分割クエリ結合は存在しないため分割クエリ結合の実施変数の組合せパターン生成処理を終了するステップS550、S540、S420、S430。次に分割クエリ結合の実施変数の組合せパターン生成処理の出力リストとして図12、図16乃至図18のローカルプラン候補を格納したnextPlanListを取得する図13のステップS240。次にjに1を代入し、nextPlanListの1番目の要素である図12のローカルプラン候補nextPlanを取得するステップS250、S260。次にnextPlanは分割クエリ結合の実施場所パターン生成処理の入力として渡されるステップS270。次に、分割クエリ結合の実施場所パターン生成処理の入力として渡された図12のローカルプラン候補nextPlanを、最終候補リストfinalPlanListに登録する図15のステップS700。次にiに1を代入するステップS710。nextPlanではiが7になるまでは分割クエリ結合演算ではないので変数iを1ずつ増やしていくステップS720、S730、S830、S840。iが7の時の演算Eは分割クエリ結合であるため演算番号が8のデータ送信演算Sを取得するステップS740。次にjに1を代入し、finalPlanList内の1番目の要素として最初に登録した、図12に示したローカルプラン候補nextPlanをfinalPlanとして取得するステップS750、S760。次にfinalPlanをコピーしたnewPlanを作成するステップS770。部分クエリ番号の実行場所をマスターサーバに変更するために以下の処理を行うステップS780。最初に演算番号8の送信データ演算Sと演算番号6の受信データ演算Rを取得する。次にRを送信データ演算に、入出力変数はSの入力変数u、vを加えたものに、実行場所を計算機2→0に変更する。さらにSの演算内容をdummyに変更する。最後にEの実行場所を計算機0に変更する。次に、これによって得られたnewPlanをnewPlanListに追加するステップS790。newPlanであるローカルプラン候補2-4の内容を図19に示す。但し図19に示したローカルプラン候補2-4では演算内容dummyの演算は削除済みである。次にjに2を代入するが、finalPlanListは要素数が1しかないため、今まで得られたnewPlanList内の1つのローカルプラン候補2-4をfinalPlanListに移すステップS800、S810、S820。次にiに8以降の値を代入しても分割クエリ結合は存在しないため、今までfinalPlanListで得られた各ローカルプラン候補内に存在する演算内容がdummyの演算を削除して分割クエリ結合の実施場所パターン生成処理終了するステップS830、S840、S850。次に分割クエリ結合の実施場所パターン生成処理の出力リストとして図12、図19のローカルプラン候補を格納したfinalPlanListを取得する図13のステップS280。次にfinalPlanList内の要素図12、図19のローカルプラン候補を出力候補プランリストoutputListに移すステップS290。次にjに2を代入し、nextPlanListの2番目の要素である図16のローカルプラン候補nextPlanを取得するステップS300、S310、S260。次にnextPlanは分割クエリ結合の実施場所パターン生成処理の入力として渡されるステップS270。分割クエリ結合の実施場所パターン生成処理において図16に示したローカルプラン候補2-1は、図12に示したローカルプラン候補2とプランの形が入出力変数149を除きほぼ同じであり、図12に示したローカルプラン候補2が入力の場合と同じ動作となるため図16に示したローカルプラン候補2-1が入力の場合の詳細は省略する。分割クエリ結合の実施場所パターン生成処理の出力リストfinalPlanListの内容は図16、図20のローカルプラン候補リストとなる。次にfinalPlanList内の要素図16、図20のローカルプラン候補を出力候補プランリストoutputListに移すステップS290。次にjに3を代入し、nextPlanListの3番目の要素である図17のローカルプラン候補nextPlanを取得するステップS300、S310、S260。次に、nextPlanは分割クエリ結合の実施場所パターン生成処理の入力として渡されるステップS270。分割クエリ結合の実施場所パターン生成処理において図17に示したローカルプラン候補2-2は図12に示したローカルプラン候補2とプランの形が入出力変数149を除きほぼ同じであり、図12に示したローカルプラン候補2が入力の場合と同じ動作となるため図17に示したローカルプラン候補2-2が入力の場合の詳細は省略する。分割クエリ結合の実施場所パターン生成処理の出力リストfinalPlanListの内容は図17、図21のローカルプラン候補リストとなる。finalPlanList内の要素図17、図21のローカルプラン候補を出力候補プランリストoutputListに移すステップS290。次にjに4を代入し、nextPlanListの4番目の要素である図18のローカルプラン候補nextPlanを取得するステップS300、S310、S260。次にnextPlanは分割クエリ結合の実施場所パターン生成処理の入力として渡されるステップS270。分割クエリ結合の実施場所パターン生成処理の入力として渡された図18のローカルプラン候補nextPlanを最終候補リストfinalPlanListに登録する図15のステップS700。次にiに1を代入するステップS720。次にnextPlanでは変数iを1ずつ増やしていくが最後まで分割クエリ結合演算が存在しないのでステップS850に移るステップS720、S730、S830、S840。ステップS850でfinalPlanListに登録された図18に示したローカルプラン候補2-3内において存在する演算内容がdummyの演算を削除して分割クエリ結合の実施場所パターン生成処理終了するステップS850。分割クエリ結合の実施場所パターン生成処理の出力リストfinalPlanListの内容は、図19のローカルプラン候補リストとなる。finalPlanList内の要素図19のローカルプラン候補2-4を出力候補プランリストoutputListに移すステップS290。次にjに5を代入するステップS300。nextPlanListに登録された要素数は4しかないためiに2を代入するステップS310、S320。inputPlanListの要素数は1しかないためローカルプラン候補生成処理を終了する。最終的に得られたローカルプラン候補リストoutputListに登録されたローカルプラン候補は図16乃至図21である。図12のローカルプラン候補2では、サーバ間演算に必要な為演算番号3のデータ送信演算によって送信される変数zとサーバ間演算と並列に実行する演算4,5によって得られる変数u,vを演算番号7によって計算機2で分割結合している。図16に示したローカルプラン候補2-1は、図12に示したローカルプラン候補2に対し演算番号4をサーバ間演算と並列実行しないことで演算番号3のデータ送信演算において変数zとuを送信し、演算番号7の分割結合でvと分割結合するようにしたローカルプラン候補である。図17に示したローカルプラン候補2-2、図12に示したローカルプラン候補2に対し演算番号5をサーバ間演算と並列実行しないことで演算番号3のデータ送信演算において変数zとvを送信し、演算番号7の分割結合でuと分割結合するようにしたローカルプラン候補である。図18に示したローカルプラン候補2-3は、図12に示したローカルプラン候補2に対し、演算番号4、5をサーバ間演算と並列実行しないことで演算番号3のデータ送信演算において変数zとvとuを送信し分割結合をしないようにしたローカルプラン候補である。図19に示したローカルプラン候補2-4は、図12に示したローカルプラン候補2に対し実行場所が計算機2ではなく計算機0の場合のローカルプラン候補である。図20に示したローカルプラン候補2-5は、図16に示したローカルプラン候補2-1に対し実行場所が計算機2ではなく計算機0の場合のローカルプラン候補である。図21に示したローカルプラン候補2-6は、図17に示したローカルプラン候補2-2に対し実行場所が計算機2ではなく計算機0の場合のローカルプラン候補である。以上のようにして、図12及び図16乃至図21に示したローカルプラン候補では、分割結合演算をする場合としない場合のローカルプラン候補、及び分割結合演算をする場合は分割結合する際に対象となる全ての変数の組合せと分割結合の実施場所がマスターサーバかスレーブサーバかの組合せを網羅したローカルプラン候補が生成される。ローカルプラン選択部31はこれらのローカルプラン候補の中から見積もり実行時間または見積もり実行計算量からなるコストを計算し、コストが最小となるローカルプランを選択するステップS8。ここで、ローカルプラン候補の見積もり実行時間算出の一例を説明する。ローカルプラン候補の見積もり実行時間は、例えば、図22に挙げた各演算の処理見積もり時間用のパラメータと、ローカルプランに含まれる演算に基づいて算出される。各演算のパラメータは、例えば、数値索引:0.001msec/出力変数の件数、TRAVERSE:1msec/入力変数の件数、分割クエリ結合:1msec/入力変数の件数、サーバ間JOIN:1msec/入力変数の件数、データ送信5msec0.001msec/入力変数の件数×変数の数、データ受信5msec0.001msec/入力変数の件数×変数の数、などである。なお、演算内容によって出力変数に格納する件数をあらかじめ設定する。ここで、図12に示したローカルプラン候補2における見積もり時間の算出処理の一例を以下に説明する。なお、図4から計算機2では1万件のXMLデータが登録されていることがわかるため、これにより各演算の見積もり実行時間を計算する。1数値索引で>=演算を利用する場合は、全体の10がヒットすると見積もる。そのため1万件の10で1000件ヒットすると見積もる。したがって、数値索引の見積もり計算時間は、0.001msec/出力変数の件数×1000件=1msecとなる。2TRAVERSEの入力変数の件数は1の結果から1000件と見積もる。出力は変わらないものと想定して1000件と見積もる。したがって、TRAVERSEの見積もり計算時間は、1msec/入力変数の件数×1000件=1000msecとなる。3データ送信の入力変数の件数は、2の結果から1000件と見積もる。したがって、データ送信の見積もり計算時間は、5msec0.001msec/入力変数の件数×1000×1=6msecとなる。4TRAVERSEの入力変数の件数は2の結果から1000件と見積もる。出力は変わらないものと想定して1000件と見積もる。したがって、TRAVERSEの見積もり計算時間は、1msec/入力変数の件数×1000件=1000msecとなる。5TRAVERSEの入力変数の件数は4の結果から1000件と見積もる。出力は変わらないものと想定して1000件と見積もる。したがって、TRAVERSEの見積もり計算時間は、1msec/入力変数の件数×1000件=1000msecとなる。6データ受信の入力変数の件数は、マスターサーバでサーバ間JOINが実行されて40に削減されて400件と見積もる。したがって、データ受信の見積もり計算時間は、5msec0.001msec/入力変数の件数×400×1≒6msecとなる。7分割クエリ結合の入力件数は5,6から計1400件と見積もる。したがって、分割クエリ結合の見積もり計算時間は、1msec/入力変数の件数×1400件=1400msecとなる。83でマスターサーバへデータ送信後、マスターサーバでは図11の分散プランの演算番号10のサーバ間JOINが実行される。ここではサーバ間JOINの見積もり計算時間は、分散プラン生成部13でローカルプラン候補の見積もり計算時間と同様の考え方で計算された後、スレーブサーバに分散プランと共に送られているものとする。分散プラン生成部13では、サーバ間JOINの入力件数は各スレーブサーバの登録データ数の1/3程度と仮定して計算する。したがって、サーバ間JOINの見積もり時間は1msec/入力変数の件数×11250件÷3=3750msecとなる。なお、図11において、分割クエリ結合演算追加部14により演算番号10のサーバ間JOINと並列に実行可能な演算として挙げられた、演算番号4,5のサーバ内演算は、ローカルプラン候補2の演算番号4,5のTRAVERSEに該当する。このため演算番号4,5と、演算番号3,6及びサーバ間JOINは並行して実施することが分かるので、ローカルプラン候補2の見積もり時間は以下の2つの見積もり時間の長い方になる。123867=6163msec12457=4401msec結果として6163msecと見積もる。別の例としてローカルプラン候補2-3を計算機2で実行する際は全処理が並列に実行できないので、見積もり時間は、1、2、3、4、および5の演算とサーバ間JOINを合わせたものになる。すなわち、1msec1000msec1000msec1000msec6msec3750msec=6757msecとなりローカルプラン候補2の方がサーバ間JOINを含めると速くなると計算される。このようにローカルプラン候補の見積もり計算時間に、マスターサーバで実行するサーバ間演算の見積もり時間も加えることで、分割クエリ結合演算追加部で追加した分割クエリ結合による最適化が有効かを判断できる。本実施形態では、計算機1は図18に示すローカルプラン候補2-3を、計算機2は図12に示すローカルプラン候補2を、計算機3は図19に示すローカルプラン候補2-4をそれぞれローカルプランとして選んだものとする。各計算機のローカルプラン選択部31は、選択したローカルプランをマスターサーバの分散プラン更新部15に送信する。ローカルプラン選択部31が、選択したローカルプランを分散プラン更新部15に送信すると、スレーブサーバは、対象のローカルプランを実行するステップS9。スレーブサーバの行うステップS9と並行して、ローカルプランを受信したマスターサーバの分散プラン更新部15は分散プラン更新処理を行うステップS10。ここで、マスターサーバの分散プラン更新部15が、図11の分散プランに対し、計算機1、計算機2、計算機3がそれぞれ図18、図12、図19のローカルプラン候補を選んだ場合に、図23のフローチャートに従って分散プランの更新を行う場合の分散プラン更新処理について説明する。なお、この分散プラン更新処理はiという変数を用いる。iは1以上であり、かつ、対象のスレーブサーバ数以下である1≦i≦スレーブサーバ数。処理の開始時点ではi=1である。また、スレーブサーバ数=maxとするステップS900。分散プラン更新部15は、計算機番号iのローカルプランLPlanを取得するステップS910。次に分散プランとローカルプランの分割クエリ結合に関する差分をチェックするステップS920。差分チェックによりLPlanでは分割クエリ結合が完全に削除されているかを判定するステップS930。LPlanで分割クエリ結合が完全に削除されていた場合ステップS930がYes、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算の実行場所から計算機iを削除するステップS940。次に削除した結果分割クエリ結合演算の実行場所が空かを判定するステップS950。分割クエリ結合演算の実行場所が空の場合ステップS950がYes、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算を削除するステップS960。次に、ステップS970に進む。また分割クエリ結合演算の実行場所が空でない場合ステップS950がNo、ステップS970に進む。さらにLPlanで分割クエリ結合が完全に削除されていない場合ステップS930がNo、ステップS970に進む。すなわちステップS970の処理は、ステップS930がNoの場合、もしくはステップS950がNoの場合、もしくはステップS960に続いて行われる。ステップS970では、LPlanで分割クエリ結合の実行場所が変更されたかを判定する。LPlanで分割クエリ結合の実行場所が変更された場合ステップS970がYes、分散プランにある分割クエリ結合、その前後にあるデータ送信演算、およびデータ受信演算の実行場所から計算機iを削除するステップS980。次に削除した結果分割クエリ結合演算の実行場所が空かを判定するステップS990。分割クエリ結合演算の実行場所が空の場合ステップS990がYes、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算を削除するステップS1000。次に、ステップS990に進む。また分割クエリ結合演算の実行場所が空でない場合ステップS990がNo、ステップS1010に進む。すなわちステップS1010の処理はステップS990がNoの場合もしくはステップS1000に続いて行われる。ステップS1010ではLPlanの実行場所を変更した分割クエリ結合が分散プラン内に既に存在するかを判定する。LPlanの実行場所を変更した分割クエリ結合が分散プラン内に既に存在しない場合ステップS1010がNo、実行場所を変更した分割クエリ結合、及びその前後にあるデータ送信、データ受信の演算を分散プランに追加するステップS1030。次にステップS1040に進む。またLPlanの実行場所を変更した分割クエリ結合が分散プラン内に既に存在する場合ステップS1010がNo、実行場所に計算機iを追加するステップS1020。次にステップS1040に進む。さらにLPlanで分割クエリ結合の実行場所が変更なかった場合ステップS970がNo、ステップS1040に進む。すなわちステップS1040の処理はステップS970がNoの場合、またはステップS1020に続いて、またはステップS1030に続いて行われる。ステップS1040ではiにi1を代入するi:=i1ステップS1040。次にiがmax以下かを判定するステップS1050。iがmax以下の場合ステップS1050がYes、ステップS910に戻り処理を繰り返す。iがmaxより大きい場合は終了する。図11に示した分散プランに対して、計算機1、2、3のローカルプランがそれぞれローカルプラン候補2-3、ローカルプラン候補2、ローカルプラン候補2-4の場合において、上述した分散プラン更新処理が行われた結果、得られる分散プランを図24に示す。図24に示した分散プラン3は、演算番号312、部分クエリ番号313、演算内容314、事前実行演算番号315、実行場所316、送信場所317、入力変数318、出力変数319の項目を有する。この分散プラン3は有する項目312乃至319は、分散プランテーブル141の有する項目142乃至149及びローカルプラン候補2、2-1乃至2-6が有する項目302乃至309と同一である。まずiに1を代入して、計算機1の選択したローカルプランであるローカルプラン候補2-3と図11の分散プランの分割クエリ結合に関する差分をチェックするステップS900、S910、S920。ローカルプラン候補2-3では、計算機1の分割クエリ結合は完全に削除されているため、図11の分散プランの分割クエリ結合及びその前後にあるデータ送信、データ受信演算図24の演算番号11-15の実行場所から計算機1を削除するステップS940。次に、分散プラン更新部15は分割クエリ結合の実行場所は空ではないため、ローカルプラン候補2-3をチェックして分割クエリ結合の実行場所が変更されていないかチェックするステップS950、S970。実行場所は変更されていないため、iに2を代入するステップS1040、S1050。次にiが2として図11の分散プランと、計算機2の選択したローカルプランであるローカルプラン候補2とにおける分割クエリ結合に関する差分をチェックするステップS920。図12に示したローカルプラン候補2は、計算機2の分割クエリ結合は削除もされず、実行場所も変わらないため、iに3を代入するステップS930、S970、S1040、S1050。次にiが3として図11の分散プランと計算機3の選択したローカルプランであるローカルプラン候補2-4の分割クエリ結合に関する差分をチェックするステップS920。ローカルプラン候補2-4は、計算機3の分割クエリ結合は削除されていないため、次に分割クエリ結合の実行場所が変更されているかをチェックするステップS930、S970。また、ローカルプラン候補2-4は、分割クエリ結合の実行場所が変更されているため、分散プランの分割クエリ結合及びその前後にあるデータ送信、データ受信演算図24の演算番号11-15の実行場所から計算機3を削除するステップS980。分割クエリ結合の実行場所は空ではないため、分散プラン更新部15は、次に実行場所を変更した分割クエリ結合が分散プランに挿入されているかを確認するステップS980、S1010。分散プランには挿入されていないため、実行場所を変更した分割クエリ結合及びその前後にあるデータ送信、データ受信演算を分散プランに挿入する図24の演算番号14、15、16ステップS1030。次にiに4を代入するが、計算機数は3までなので処理を終了するステップS1040、S1050。最終的に図24の分散プラン3が得られる。分散プラン実行部16は、分散プラン3の演算を実行する図6のステップS11。なお、分散プラン3の実行と、スレーブサーバのローカルプラン実行部33の実行とは、お互いデータの送受信で依存関係にあり、例えば並列に実行したり、相手からデータが送信されるのを待ったりする。すなわち、マスターサーバの送受信部17とスレーブサーバの送受信部34とがデータのやり取りを行いながら分散プランは実行される。上述したように、本実施形態によれば、ユーザによってマスターサーバに入力された問合せクエリに対して、マスターサーバは部分クエリの結合処理を除いたサーバ間演算に関連する部分の最適化のみを実施し、部分クエリの結合の最適化はスレーブサーバが実施する。すなわち、マスターサーバは部分クエリの結合処理を最適化の範囲から除外することが可能となるため、全てをマスターサーバ側で最適化する場合と比較して単純な仕組みで実現することが可能となる。すなわち、マスターサーバはスレーブサーバが決定する部分クエリの結合処理に依存しない形で部分クエリの結合処理を仮に決定する。スレーブサーバは、サーバ毎のデータベース情報に基づいて部分クエリの結合処理を最適化する。さらに、マスターサーバは、スレーブサーバがこの部分クエリの結合処理の結果をマスターサーバに通知することよって、効率の良い分散プランを生成する。また、分割クエリ結合演算に関してスレーブサーバ側が最適化するため、各スレーブサーバに適した効率のよいプランの生成が可能となる。したがって、本発明の実施形態によれば、問合せクエリ51について、マスターサーバが決定する分散プランの範囲から、分割クエリ結合演算に関する演算を取り除くことで、マスターサーバの分散プラン最適化の仕組みを簡素化した上で、スレーブサーバが各々に最適な形で上記の範囲の最適化を実施する。これにより、効率的なクエリ処理を実現することが可能となる。第2の実施形態第2の実施形態の分散データベース検索装置について図面を参照して説明する。なお、第1の実施形態の分散データベース検索装置と同一の構成には同一の符号を付し、説明は省略する。図25は、第2の実施形態の分散データベース検索装置の機能構成を示す構成図である。図25に示すように、本実施形態の分散データベース検索装置は、図1に示した分散データベース検索装置の構成にスキーマ生成部18、35とスキーマ変更部19、36をさらに有する構成である。スキーマとは格納するデータの種類や位置情報を保持するものデータの構造のことである。スキーマ生成部18、35は各サーバにおいて行われる演算の結果、入出力されるデータのスキーマを生成する。例えば、マスターサーバが備えるスキーマ生成部18は、分散プランの各演算の入出力データのスキーマを生成する。また、スレーブサーバが備えるスキーマ生成部35は、ローカルプランの各演算の入出力データのスキーマを生成する。スキーマ変更部19、36は、分散プランまたはローカルプランの各演算によって得られたデータを次の演算に渡す際に、当該データのスキーマを変更する。マスターサーバのスキーマ変更部19は、分散プランまたはローカルプランの各演算の出力によって得られたデータを、分散プランの次の演算の入力に渡す際にデータのスキーマを変更する。スレーブサーバのスキーマ変更部36は、分散プランまたはローカルプランの各演算の出力によって得られたデータを、ローカルプランの次の演算に渡す際に、当該データのスキーマを変更する。ここで、図26に本実施形態におけるスキーマ変更部19によって変更される前のスキーマに含まれる項目の一例を示す。変更される前のスキーマとは、すなわち後述するスキーマ生成部18によって生成されるスキーマである。スキーマとは格納するデータの種類や位置情報を保持するものであり、図26に示すように本実施形態では、可変領域401と、変数~402-iiは1以上の整数と拡張変数eV1,Vn403の項目を有する。拡張変数eV1,Vn403のeは変数~402-iの~に一致しない一意の文字列が入り、V1,Vnには,で区切られたn個の一意になる任意の文字列が入る。可変領域401とはサーバ間でデータを送る際にカラム数の違いを吸収するためのデータを格納する項目である。変数~402-iは各変数のデータを格納する項目で拡張変数eV1,Vn403は変数V1から変数Vnの全変数のデータを格納する項目である。なお、変数~402-iは入出力されるデータ毎にさまざまな変数が格納される。ここで、図27を参照して、本実施形態の分散データベース検索装置の検索処理の一例について説明する。図27は、本実施形態の分散データベース検索装置の検索処理の一例を示すフローチャートである。なお、ステップS1至S8及び,S10の処理については図6に示したフローチャートと同じであるため説明を割愛する。ローカルプラン選択部37は、図27のステップS1-S8でローカルプランを決定した後、決定したローカルプランに実行順序が非決定的な部分を確定するローカルプラン順序決定処理を実施するステップS12。ここで、実行順序が非決定的な部分とはローカルプランの各演算の事前実行番号が等しい演算の集合である。これらの演算はどの順序で実行するかの指定がないため任意の順序で実行可能である。すなわち、ローカルプラン順序決定処理によって、でこれらの演算の実行順序を一意に決定される。図28に、図12で示したローカルプラン候補2がローカルプラン順序決定処理ステップS12により非決定的な演算集合の順序を一意に決定された結果を示す。図12に示したローカルプラン候補2では演算番号2、4、5の各演算の事前実行番号は1であり実行順序が非決定的である。図29では演算番号2、4、5の順序で実行するように決定し、演算番号4の事前実行番号を1から2、演算番号5の事前実行番号を1から4に書き換えている。ステップS12におけるローカルプラン順序決定処理後、演算の順序が決定されたローカルプランは送信部34によってマスターサーバに送信される。マスターサーバは当該ローカルプランを受信すると、分散プラン更新部10が分散プラン更新処理を行うステップS10。ステップS10と並行して、スレーブサーバのスキーマ生成部35が、当該ローカルプラン内の各演算の入力スキーマおよび出力スキーマ以下、入出力スキーマというを生成するステップS14。入力スキーマとは、入力されるデータのスキーマである。出力スキーマとは演算で出力されるデータのスキーマである。ここで図29を参照して、スキーマ生成部35が、図28に示したローカルプランに対して、スキーマ生成処理ステップS14を行う際の動作について具体的に説明する。なお、このスキーマ生成処理ではiという変数を用いる。iは1以上の整数であり、対象のローカルプランの演算番号以下である1≦i≦ローカルプランの演算番号の最大値。また、スキーマ生成処理の開始時点ではi=1である。また、ローカルプランの演算番号の最大値をmaxとする。また、演算番号301がiのローカルプランの演算を演算Sとする。スキーマ生成部35は、ローカルプラン選択部31からローカルプランを受信すると、まず、初期化処理としてi=1、ローカルプランの演算番号の最大値=maxとするステップS1110。次に、iがmax以下であるか否かを判定するステップS1110。iがmax以下である場合ステップS1110がYes、演算番号iの演算Sを取得するステップS1120。次に演算Sに出力変数があるかを判定するステップS1130。演算Sに出力変数がある場合ステップS1130がYes、演算Sの出力変数を出力スキーマと変数リストVLに追加する。さらに変数毎に到達番号リストRLと利用番号リストULを用意するステップS1140。次に各演算の事前実行番号から、演算Sと演算Sより後に実行される演算番号のリストALを取得するステップS1150。次に、演算Sの各出力変数に対して、変数毎に用意した到達演算番号リストRLにリストALに格納された演算番号を登録するステップS1160。その後ステップS1170に進む。なお、演算Sに出力変数がない場合ステップS1130がNoもステップS1170に進む。ステップS1170では演算Sに入力変数があるかを判定するステップS1170。演算Sに入力変数がある場合ステップS1170がYes、演算Sの事前実行演算番号を辿り、演算Sより前に実行される演算番号のリストBLを取得するステップS1180。次に演算Sの各入力変数に対して、変数毎に用意した利用演算番号リストULにリストBLに格納された演算番号を登録するステップS1200。その後ステップS1210に進む。なお、演算Sに入力変数がない場合ステップS1170がNoもステップS1210に進む。ステップS1210ではiにi1を代入するi:=i1ステップS1210。次にステップS1110に戻る。iがmaxより大きい場合ステップS1110がNo、ステップS1220に進む。ここで、jという変数を用いる。jは1以上であり、かつ、変数リストVL内の要素数以下である1≦j≦VL内の要素数。また、この時j=1であり、VL内の要素数=vmaxとするステップS1220。次に、jがvmax以下であるか否かを判定するステップS1230。jがvmax以下である場合ステップS1230がYes、変数リストVLからj番目の変数varを取得するステップS1240。次に変数varの到達演算番号リストRLと利用番号リストULに共通して出現する演算番号リストCLを取得するステップS1250。次にリストCL内の演算番号の各演算の出力スキーマに変数varを追加するステップS1260。次にjにj1を代入するj:=j1ステップS1270。次にステップS1230に戻る。jがvmaxより大きい場合ステップS1230がNo、iに1を代入するi:=1ステップS1280。次に、iがmax以下であるか否かを判定するステップS1290。iがmax以下である場合ステップS1290がYes、演算番号iの演算Sを取得するステップS1300。次に演算Sの入力スキーマに事前実行演算番号の演算の出力スキーマをコピーするステップS1310。次に演算Sの出力スキーマの先頭に可変領域を、最後尾に拡張変数eを追加するステップS1320。次にiにi1を代入するi:=i1ステップS1330。次にステップS1290に戻る。iがmaxより大きい場合ステップS1290がNo、処理を終了する。なお、図29で示したフローチャートは、スレーブサーバのスキーマ生成部18におけるスキーマ生成処理S15においても対象がローカルプランであるか分散プランであるかの違いのみで同様に動作する。ここで、図30に、図28で示したローカルプラン順序決定処理で得られたローカルプランにおいて、上述したスキーマ生成処理が行われた結果得られる入出力スキーマの一例を示す。図30に示した入出力スキーマテーブル500は、演算番号500、入力スキーマ1、入力スキーマ2、出力スキーマ502の項目を示す。入出力スキーマテーブル500の演算番号501には、スキーマ生成処理が行われたプランの演算番号と対応した演算番号が格納される。入力スキーマ1は、スキーマ生成処理において生成された入力スキーマの1つ目が格納される。入力スキーマ2は、スキーマ生成処理において生成された入力スキーマの2つ目の入力スキーマが格納される。出力スキーマ504は、スキーマ生成処理において生成された出力スキーマが格納される。スキーマ生成処理部18が、この入出力スキーマテーブル500を算出する処理を具体的に説明する。まず図28のローカルプランが、スキーマ生成処理の入力として渡される。次にiに1を、maxに8を代入するステップS1100。次にiがmax以下であるため演算番号1の演算Sを取得するステップS1110、S1120。演算Sは出力変数xを持つ為xを出力スキーマ504と変数リストVLに追加する。さらにxに対する到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号1と演算Sより後に実行される演算番号2-8を到達番号リストRLに格納するステップS1150、S1160。演算Sは入力変数を持たないためiに2を代入し、演算番号2の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数zを持つ為zを出力スキーマ504と変数リストVLに追加する。さらにzに対する到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号2と演算Sより後に実行される演算番号3-8を到達番号リストRLに格納するステップS1150、S1160。次に演算Sは入力変数xを持つ為、Sより前に実行された演算番号1を利用演算番号ULに登録する。ステップS1170、S1180、S1200。次に演算番号3の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数zを持つ為zを出力スキーマ504と変数リストVLに追加する。さらにzに対する到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号3と演算Sより後に実行される演算番号3、6-8を到達番号リストRLに格納するステップS1150、S1160。次に入力変数zを持つ為、Sより前に実行された演算番号1、2をzの利用演算番号ULに登録する。ステップS1130、S1170、S1180、S1200。次に演算番号4の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数uを持つ為uを出力スキーマ504と変数リストVLに追加する。さらにuに対する到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号4と演算Sより後に実行される演算番号5、7、8を到達番号リストRLに格納するステップS1150、S1160。次に演算Sは入力変数xを持つ為、Sより前に実行された演算番号1、2を利用演算番号ULに登録する。ステップS1170、S1180、S1200。次に演算番号5の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数vを持つ為vを出力スキーマ504と変数リストVLに追加する。さらにvに対する到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号5と演算Sより後に実行される演算番号7、8を到達番号リストRLに格納するステップS1150、S1160。次に演算Sは入力変数xを持つ為、Sより前に実行された演算番号1、2、4を利用演算番号ULに登録する。ステップS1170、S1180、S1200。次に演算番号6の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数zを持つ為zを出力スキーマ504と変数リストVLに追加する。さらにzに対する。到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号6と演算Sより後に実行される演算番号7、8を到達番号リストRLに格納するステップS1150、S1160。次に、入力変数zを持つ為、Sより前に実行された演算番号1-3をzの利用演算番号ULに登録する。ステップS1130、S1170、S1180、S1200。次に演算番号7の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数を持たず、入力変数zを持つ為、Sより前に実行された演算番号1-6をzの利用演算番号ULに登録する。ステップS1130、S1170、S1180、S1200。次に演算番号8の演算Sを取得するステップS1210、S1110、S1120。演算Sは出力変数uとvを持つ為uとvを出力スキーマ504と変数リストVLに追加する。さらにuとvに対する。到達番号リストRLと利用番号リストULを用意するステップS1130、S1140。次に事前実行番号を辿り演算Sの演算番号8を到達番号リストRLに格納するステップS1150、S1160。次に、入力変数u、vを持つ為、Sより前に実行された演算番号1-7をu、vの利用演算番号ULに登録する。ステップS1130、S1170、S1180、S1200。次にiがmaxを超えたためjに1を、vmaxにVLの要素数4を代入するステップS1210、S1110、S1220。次に変数リストの1番目の要素である変数xを取得するステップS1230,S1240。変数xの利用番号リストULの各要素は1、2、4、到達演算番号RLは1-8であるため共通して出現する演算番号1、2、4の出力スキーマ504にxを追加するステップS1250、S1260。次にVLの2番目の変数zを取得するステップS1270、S1230、S1240。変数zの利用番号リストULの各要素は1-6、到達演算番号RLは2-8であるため共通して出現する演算番号2-6、の出力スキーマ504にzを追加するステップS1250、S1260。次にVLの3番目の変数uを取得するステップS1270、S1230、S1240。変数uの利用番号リストULの各要素は1-7、到達演算番号RLは4、5、7、8であるため共通して出現する演算番号4、5、7、の出力スキーマ504にuを追加するステップS1250、S1260。次にVLの4番目の変数vを取得するステップS1270、S1230、S1240。変数vの利用番号リストULの各要素は1-7、到達演算番号RLは5、7、8であるため共通して出現する演算番号5、7、の出力スキーマ504にvを追加するステップS1250、S1260。次にiに1を代入し、演算番号1の演算Sを取得するステップS1270、S1230、S1280。演算番号1は入力がないため、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号2の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号2の入力スキーマ1に演算番号1の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号3の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号3の入力スキーマ1に演算番号2の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号4の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号4の入力スキーマ1に演算番号2の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号5の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号5の入力スキーマ1に演算番号4の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号6の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号6の入力スキーマ1に演算番号3の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号7の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号7の入力スキーマ1に演算番号5の出力スキーマ504を、入力スキーマ2に演算番号6の出力スキーマ504を各々コピーし、出力スキーマ504に可変領域と拡張変数eを追加して、演算番号8の演算Sを取得するステップS1300-S1320、S1280、S1290。演算番号8の入力スキーマ1に演算番号7の出力スキーマ504をコピーし、出力スキーマ504に可変領域と拡張変数eを追加して終了するステップS1300-S1320、S1280、S1290。スキーマ生成処理の出力結果の一例は、図30にした入出力スキーマテーブル500である。なお、図30では入力スキーマが1つだけの場合は入力スキーマ1の項目に、2つある場合は2つ目を入力スキーマ2の項目に格納しているが、入力スキーマの項目は必要に応じて増やしたり減らしたりしても良い。ここで、ステップS14と並行して実行されるマスターサーバの処理について説明する。分散プラン生成部23は、分散プラン更新処理を行いステップS10、分散プランを更新した後、更新した分散プランに基づいて実行順序が非決定的な部分を確定する分散プラン順序決定処理を実施するステップS13。ステップS13の分散プラン順序決定処理は対象のプランがローカルプランではなく分散プランである以外はステップS12と同じである。次に、スキーマ生成部18は、決定した分散プラン内の各演算の入出力スキーマを生成するステップS15。ステップS15のスキーマ生成処理は対象のプランがローカルプランではなく分散プランである以外はステップS14と同じである。マスターサーバとスレーブサーバのそれぞれで、スキーマ生成処理が行われると、マスターサーバとスレーブサーバのそれぞれは生成された入出力スキーマに基づいてプランを実行する。すなわち、スレーブサーバのローカルプラン実行部36は、スキーマ生成処理ステップS14で生成された入出力スキーマを元にローカルプランを実行するステップS9。また、マスターサーバの分散プラン実行部16は、スキーマ生成処理ステップS15で生成されたスキーマを元に、分散プランを実行するステップS11。ローカルプラン実行ステップS9では、ローカルプラン実行部33は、ローカルプランの各演算を実施する際に、入力されるデータと用意した入力スキーマをスキーマ変更部36に渡してスキーマ変更処理を実施するステップS16。また分散プラン実行ステップS11においても同様に、分散プラン実行部16が分散プランの各演算を実施する際に、入力されるデータと用意した入力スキーマをスキーマ変更部19に渡してスキーマ変更処理を実施するステップS16。ここで、図31を参照して、ステップS16においてマスターサーバのスキーマ変更部19が、分散プランを実行する際に行うスキーマ変更処理について説明する。スキーマ変更部19は、分散プラン実行部16が次に実行する演算の入力であるスキーマSを持つデータDと、スキーマ生成部18で予め用意した演算の入力スキーマTを取得するステップS1400。次にスキーマSとスキーマTの変数の項目が一致しているかを判定するステップS1410。スキーマSとスキーマTの変数の項目が一致していない場合ステップS1410がNo、スキーマSの拡張変数eの変数リストVLを取得し、リストが空であるかを判定するステップS1420。スキーマSの拡張変数eの変数リストVLが空でない場合ステップS1420がNo、拡張変数リストVL内の各変数をスキーマSの変数の項目として追加し、VLを空に変更するステップS1430。次にスキーマSに存在し、スキーマTに存在しない変数の項目のリストDLを取得するステップS1430。次にステップS1450に進む。なお、スキーマSの拡張変数eの変数リストVLが空の場合ステップS1420がYesも、ステップS1450に進む。ステップS1450では、変数の項目リストDL内の変数がスキーマSにおいて非連続に並んでいるかを判定するステップS1450。変数の項目リストDL内の変数がスキーマSにおいて非連続に並んでいる場合、ステップS1450がYes、変数の項目リストDL内の変数が連続するようにスキーマSとデータDの各データを書き換えるステップS1460。次にステップS1470に進む。なお、変数の項目リストDL内の変数がスキーマSにおいて非連続に並んでいない場合ステップS1420がNoも、ステップS1470に進む。ステップS1470では、スキーマSの変数の項目からリストDL内の変数を削除し、拡張変数eの変数リストに追加するステップS1470。次にデータDの可変領域の項目にリストDL内の変数の合計サイズを格納して終了するステップS1480。なおスキーマSとスキーマTの変数の項目が一致している場合ステップS1410がYesも終了する。なお、図31で示したフローチャートは、ローカルプラン実行部33における演算に対するスキーマ変更部36の処理時においても、対象がローカルプランであるか分散プランであるかの違いのみで同様に動作する。ここで図31を参照して、スキーマ変更部19が、図26に示した、計算機0の演算番号7の入力スキーマと、計算機1、計算機2、計算機3から送信された各データのスキーマに対し、スキーマ変更処理を行う際の動作について具体的に説明する。このスキーマ変更処理は分散プランが図24、計算機1、計算機2、計算機3のローカルプランが図12、図18、図16に示したローカルプラン候補における分散プランの演算番号7の受信演算の実施時に行うものである。まず図26の計算機0の演算番号7の入力スキーマTと、計算機1から送信されたデータのスキーマSを取得するステップS1400。スキーマSとスキーマTの変数項目が一致しているため処理を終了するステップS1410。次に計算機0の演算番号7の入力スキーマTと、計算機2から送信されたデータのスキーマSを取得するステップS1400。スキーマSとスキーマTの変数項目が一致せず、Sの拡張変数eの変数リストが空であるためスキーマSに存在し、スキーマTに存在しない変数としてuとvを取得するステップS1410、ステップS1420、ステップS1440。変数uとvはスキーマSにおいて連続して並んでいる為、スキーマSの項目から変数uとvを削除し、拡張変数eの変数リストに追加するステップS1450、ステップS1470。最後にuとvの変数の合計サイズを拡張領域に格納するステップS1480。次に計算機0の演算番号7の入力スキーマTと、計算機3から送信されたデータのスキーマSを取得するステップS1400。スキーマSとスキーマTの変数項目が一致せず、Sの拡張変数eの変数リストが空であるためスキーマSに存在し、スキーマTに存在しない変数としてuを取得するステップS1410、ステップS1420、ステップS1440。変数uはスキーマSにおいて連続して並んでいる為、スキーマSの項目から変数uを削除し、拡張変数eの変数リストに追加するステップS1450、ステップS1470。最後にuの変数の合計サイズを拡張領域に格納するステップS1480。スキーマ変更処理の結果を図32に示す。図32は、スキーマ変更処理後のスキーマが含む項目を示す一例である。図32に示すように本実施形態では、スキーマ変更処理後は、可変領域401と、変数~402と拡張変数eV1,Vn403の項目を有する。なお上記のスキーマ変更処理は、マスターサーバの分散プランの演算とスレーブサーバのローカルプランの演算でデータを受け渡す際に実施する事例を説明したが、同一サーバ内、或いはスレーブサーバ間の演算でデータを受け渡す際にも適用できる。図24では演算番号6のサーバ間JOINの前に変数zを受信することになっている。しかしながら図18、図12、図19のローカルプラン候補から分かるように、計算機1は変数z、u、vの3組のデータを、計算機2は変数zを、計算機3は変数z、uの2組のデータを送信している。このため、そのままではカラム数の異なるテーブルを扱うことになってしまう。したがってマスターサーバのスキーマ変更部18では、図26に示す各計算機のデータのスキーマを、図32に示すように全ての計算機のデータが同じスキーマとみなすことができるようにスキーマを変更している。図24では演算番号6のサーバ間JOINでは変数zのみ必要であるため、他に変数が含まれていた場合は全て1つの可変長データを格納した拡張変数eのカラムとして扱うようになっている。そして可変領域で可変長領域のサイズを記憶している。これによりサーバ間JOINの実行時に全て同じ形のテーブルとして扱うことが可能になっている。本実施形態の分散データベース検索装置によると、スレーブサーバ毎にローカルプランを作成するため、スレーブサーバ毎に分散プランの一部が異なる可能性がある。すなわち、スレーブサーバ毎に送られるデータのスキーマが異なる可能性がある。本実施形態は、このような場合に、スキーマ変更部18、20においてデータを受け渡す際に送信する側のデータのスキーマ入力スキーマと、受信するデータのスキーマ出力スキーマの違いを変更することで、同一スキーマのデータとして扱うことを実現する。すなわち、スレーブサーバ毎に効率の良いローカルプランを作成する場合、複数の異なるスキーマのデータが存在する場合がある。このように、スレーブサーバ毎に効率の良いローカルプランを作成する場合は、複数の異なるスキーマのデータを統一的に扱う処理が必要になる。上述のように本実施形態によると、複数の異なるスキーマのデータを統一的に扱うことが可能となる。また、本実施形態ではスキーマのみ、あるいはスキーマとデータの一部の領域の書き換えのみで複数の異なるスキーマのデータを統一的に扱うこと実現することが可能である。以上、本発明の実施形態を説明したが、これら実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。"