(57)【要約】【課題】３以上のデータベース装置によって構成される分散データベースシステムのテーブル等結合処理において、処理時間を低減する技術を提供する。【解決手段】データベース装置１０Ａ，１０Ｂ，１０Ｃの間で、テーブル等結合処理を行う場合、データベース装置１０Ａから、テーブルＡ１の結合対象カラムのＮ個（図１では３個）の対象カラム値を、データベース装置１０Ｂ，１０Ｃへ送信する（ステップ（ｂ））。そして、データベース装置１０Ｂ，１０Ｃは、受信した対象カラム値と自身のテーブルとを用いてソートマージ結合処理を実行し、等しいカラム値が存在する場合には１を付し、等しいカラム値が存在しない場合には０を付して判定ビット列を生成し、判定ビット列をデータベース装置１０Ａに送信する。データベース装置１０Ａは、受信した判定ビット列のＡＮＤ演算を行って、すべてのテーブルに共通のカラム値を算出する。【選択図】図１
2010272030.tif 000002
【特許請求の範囲】
【請求項１】
クライアント装置と、テーブルを記憶する３以上のデータベース装置とが、相互に通信可能にネットワークに接続され、テーブル等結合処理をおこなう分散データベースシステムにおいて用いられるデータベース管理方法であって、
前記データベース装置は、等結合処理の開始起点となる起点のデータベース装置と、等結合相手となる２以上の他のデータベース装置とによって構成され、
前記データベース装置は、それぞれ処理部と、結合対象カラムのカラム値について昇順にソートされたテーブルを記憶する記憶部とを備え、
前記起点のデータベース装置の処理部は、自身のテーブルの結合対象カラムのカラム値Ｎ個を前記他のデータベース装置に送信し、
前記他のデータベース装置の処理部は、受信したＮ個のカラム値それぞれに対して、自身のテーブルの結合対象カラムに同一のカラム値が存在する場合には１を付し、同一のカラム値が存在しない場合には０を付した判定ビット列を生成し、その生成した判定ビット列を前記起点のデータベース装置に返信し、
前記起点のデータベース装置の処理部は、受信した判定ビット列のビットごとにＡＮＤ演算を実行し、その実行結果を結合結果ビット列とし、その結合結果ビット列を前記他のデータベース装置に送信し、
前記起点のデータベース装置および前記他のデータベース装置は、自身のテーブルから、前記結合結果ビット列のビットが１となった前記結合対象カラムのカラム値を含むレコードを抽出して、その抽出したレコードを前記クライアント装置に送信し、
前記クライアント装置は、受信したレコードに含まれる前記結合対象のカラムのカラム値が同一となるレコード同士を結合する
ことを特徴とするデータベース管理方法。
【請求項２】
前記他のデータベース装置の処理部は、自身のテーブルの結合対象カラムから、前記受信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値を取得して、その取得したカラム値を前記起点のデータベース装置に送信し、
前記起点のデータベース装置の処理部は、自身のテーブルの結合対象カラムから抽出した、前記送信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値および前記他のデータベース装置から受信したカラム値の中で最大となるカラム値を抽出し、該最大となるカラム値が自身のものである場合には起点を自身とし、該最大となるカラム値が前記他のデータベース装置のものである場合には該最大となるカラム値を送信してきた前記他のデータベース装置を起点に指定する情報を該他のデータベース装置に送信し、
起点となったデータベース装置が、該最大となるカラム値以降のＮ個のカラム値を前記他のデータベース装置に送信する
ことを特徴とする請求項１に記載のデータベース管理方法。
【請求項３】
前記他のデータベース装置の処理部は、自身のテーブルの結合対象カラムから、前記受信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値を取得して、その取得したカラム値を前記起点のデータベース装置に送信し、
前記起点のデータベース装置の処理部は、自身のテーブルの結合対象カラムから抽出した、前記送信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値および前記他のデータベース装置から受信したカラム値の中で最大となるカラム値を抽出し、
前記起点のデータベース装置の処理部は、自身のテーブルの結合対象カラムから、該最大となるカラム値より大きい範囲の中で最も小さいカラム値以降のＮ個のカラム値を取得し、該取得したＮ個のカラム値を前記他のデータベース装置に送信する
ことを特徴とする請求項１に記載のデータベース管理方法。
【請求項４】
クライアント装置と、テーブルを記憶する３以上のデータベース装置とが、相互に通信可能にネットワークに接続され、テーブル等結合処理をおこなう分散データベースシステムであって、
前記データベース装置は、等結合処理の開始起点となる起点のデータベース装置と、等結合相手となる２以上の他のデータベース装置とによって構成され、
前記データベース装置は、それぞれ処理部と、結合対象カラムについて昇順にソートされたテーブルを記憶する記憶部とを備え、
前記起点のデータベース装置の処理部は、自身のテーブルの結合対象カラムのカラム値Ｎ個を前記他のデータベース装置に送信し、
前記他のデータベース装置の処理部は、受信したＮ個のカラム値それぞれに対して、自身のテーブルの結合対象カラムに同一のカラム値が存在する場合には１を付し、同一のカラム値が存在しない場合には０を付した判定ビット列を生成し、その生成した判定ビット列を前記起点のデータベース装置に返信し、
前記起点のデータベース装置の処理部は、受信した判定ビット列のビットごとにＡＮＤ演算を実行し、その実行結果を結合結果ビット列とし、その結合結果ビット列を前記他のデータベース装置に送信し、
前記起点のデータベース装置および前記他のデータベース装置は、自身のテーブルから、前記結合結果ビット列のビットが１となった前記結合対象カラムのカラム値を含むレコードを抽出して、その抽出したレコードを前記クライアント装置に送信し、
前記クライアント装置は、受信したレコードに含まれる前記結合対象のカラムのカラム値が同一となるレコード同士を結合する
ことを特徴とする分散データベースシステム。
【請求項５】
請求項１ないし請求項３のいずれか一項に記載の前記起点のデータベース装置のデータベース管理方法または前記他のデータベース装置のデータベース管理方法を、コンピュータとしてのデータベース装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３以上のデータベース装置によって構成される分散データベースシステムのテーブル等結合処理において、処理時間を低減する技術に関する。
【背景技術】
【０００２】
データベース技術分野におけるテーブル（表）の等結合処理とは、図７の２段目に示すテーブルように、中間テーブルの商品ＩＤのカラム（列）と発注テーブルの商品ＩＤのカラム（列）とを結合対象カラムとして指定し、その結合対象カラムのカラム値が等しいレコード（行）同士を結合し、その結合したレコードの集合として３段目に示す等結合結果テーブルを作成する処理のことである。
【０００３】
例えば、ネットワーク上に分散した２つのデータベース装置のテーブル間で等結合処理を実行する方法として、セミジョイン法がある（非特許文献１参照）。セミジョイン法では、図７の２段目に示す中間テーブルおよび発注テーブルがそれぞれ異なるデータベース装置に格納されている場合、例えば、中間テーブルの結合対象カラム（商品ＩＤ）の値である対象カラム値を、等結合相手のデータベース装置にすべて送信する。そして、その等結合相手のデータベース装置は、受信した対象カラム値と発注テーブルの結合対象カラムの値とが等しいレコードを抽出して、その抽出したレコード（結合可能レコード）を返信する。そして、返信を受けたデータベース装置は、受信した結合可能レコードに含まれるカラム値と同一のカラム値を含むレコードを中間テーブルから抽出し、受信した結合可能レコードと抽出したレコードとを結合して、等結合結果テーブルを作成する。
【０００４】
例えば、３つのデータベース装置によって構成される分散データベースシステムにおいて、セミジョイン法を用いてテーブルの等結合処理を実行する場合について、図７を用いて説明する。各データベース装置が、図７に示す在庫テーブル、受注テーブル、発注テーブルのいずれかを格納しているものとする。まず、図７の１段目に示す在庫テーブルと受注テーブルとの等結合処理によって中間テーブルが生成される。次に、図７の２段目に示す中間テーブルと発注テーブルとの等結合処理によって、等結合結果テーブルが生成される。このように、セミジョイン法を用いる場合には、２つのテーブルの等結合処理が、多段に実行される必要がある（非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】西川陽一著，“図解・標準  最新データベース技術  マスタリングハンドブック”，株式会社秀和システム，2002年11月11日，p.381-382
【非特許文献２】李華植著，“データベースパフォーマンスアップの教科書  基本原理編（初版第３刷）”，株式会社翔泳社，2007年8月5日，p.466
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前記したように、非特許文献１および非特許文献２に記載の技術を、３以上のデータベース装置によって構成される分散データベースシステムの等結合処理に適用した場合、２つのテーブルについて多段に等結合処理を行うため、テーブルの数の増加に比例して、処理時間が長くなるという問題がある。
【０００７】
また、非特許文献１および非特許文献２に記載の技術では、データベース装置間で送受信される対象カラム値や中間テーブルが一時的に記憶される。そのため、レコード数が膨大な大規模テーブル間の等結合処理を実行する場合、一時的に必要となるメモリ容量が大幅に必要になる。そして、一時的にメモリ容量が足りなくなった場合には処理性能の低下を招く、すなわち、処理負荷が大きくなるために処理時間が長くなるという問題がある。
【０００８】
また、等結合処理において、データベース装置のＣＰＵ（Computer Processing Unit）負荷の大半を占めるのは、受信した対象カラム値と、テーブルの結合対象カラムのカラム値との比較処理である。セミジョイン法では、対象カラム値を受信した片方のデータベース装置だけでこの比較処理が行われるため、処理負荷の大きいデータベース装置で比較処理が行われる場合には処理時間が長くなるという問題がある。
【０００９】
そこで、本発明の課題は、前記した問題を解決するために、３以上のデータベース装置によって構成される分散データベースシステムのテーブル等結合処理において、処理時間を低減する技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記課題を解決するために、請求項１に記載の発明は、クライアント装置と、テーブルを記憶する３以上のデータベース装置とが、相互に通信可能にネットワークに接続され、テーブル等結合処理をおこなう分散データベースシステムにおいて用いられるデータベース管理方法であって、データベース装置が、等結合処理の開始起点となる起点のデータベース装置と、等結合相手となる２以上の他のデータベース装置とによって構成され、データベース装置が、それぞれ処理部と、結合対象カラムのカラム値について昇順にソートされたテーブルを記憶する記憶部とを備え、起点のデータベース装置の処理部が、自身のテーブルの結合対象カラムのカラム値Ｎ個を他のデータベース装置に送信し、他のデータベース装置の処理部が、受信したＮ個のカラム値それぞれに対して、自身のテーブルの結合対象カラムに同一のカラム値が存在する場合には１を付し、同一のカラム値が存在しない場合には０を付した判定ビット列を生成し、その生成した判定ビット列を起点のデータベース装置に返信し、起点のデータベース装置の処理部が、受信した判定ビット列のビットごとにＡＮＤ演算を実行し、その実行結果を結合結果ビット列とし、その結合結果ビット列を他のデータベース装置に送信し、起点のデータベース装置および他のデータベース装置が、自身のテーブルから、結合結果ビット列のビットが１となった結合対象カラムのカラム値を含むレコードを抽出して、その抽出したレコードをクライアント装置に送信し、クライアント装置が、受信したレコードに含まれる結合対象のカラムのカラム値が同一となるレコード同士を結合することを特徴とする。
【００１１】
また、請求項４に記載の発明は、クライアント装置と、テーブルを記憶する３以上のデータベース装置とが、相互に通信可能にネットワークに接続され、テーブル等結合処理をおこなう分散データベースシステムであって、データベース装置が、等結合処理の開始起点となる起点のデータベース装置と、等結合相手となる２以上の他のデータベース装置とによって構成され、データベース装置が、それぞれ処理部と、結合対象カラムについて昇順にソートされたテーブルを記憶する記憶部とを備え、起点のデータベース装置の処理部が、自身のテーブルの結合対象カラムのカラム値Ｎ個を他のデータベース装置に送信し、他のデータベース装置の処理部が、受信したＮ個のカラム値それぞれに対して、自身のテーブルの結合対象カラムに同一のカラム値が存在する場合には１を付し、同一のカラム値が存在しない場合には０を付した判定ビット列を生成し、その生成した判定ビット列を起点のデータベース装置に返信し、起点のデータベース装置の処理部が、受信した判定ビット列のビットごとにＡＮＤ演算を実行し、その実行結果を結合結果ビット列とし、その結合結果ビット列を他のデータベース装置に送信し、起点のデータベース装置および他のデータベース装置が、自身のテーブルから、結合結果ビット列のビットが１となった結合対象カラムのカラム値を含むレコードを抽出して、その抽出したレコードをクライアント装置に送信し、クライアント装置が、受信したレコードに含まれる結合対象のカラムのカラム値が同一となるレコード同士を結合することを特徴とする。
【００１２】
このような構成によれば、受信したカラム値とテーブルのカラム値との比較処理は各データベース装置において並列に行われるため、等結合処理を行うためのテーブルの数の増加に比例して処理時間が長くなるということはなく、処理時間が低減できる。また、テーブルの結合対象カラムのカラム値がソートされているので、カラム値がランダムな場合に比べて、同一のカラム値の比較に掛かる処理時間を短縮できる。また、すべてのテーブルに共通に存在するカラム値の算出は、ＡＮＤ演算によって容易に実行でき、カラム値そのものを用いる比較演算の場合に比べて、処理時間が低減できる。
【００１３】
また、請求項２に記載の発明は、請求項１に記載のデータベース管理方法において、他のデータベース装置の処理部が、自身のテーブルの結合対象カラムから、受信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値を取得して、その取得したカラム値を起点のデータベース装置に送信し、起点のデータベース装置の処理部が、自身のテーブルの結合対象カラムから抽出した、送信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値および他のデータベース装置から受信したカラム値の中で最大となるカラム値を抽出し、該最大となるカラム値が自身のものである場合には起点を自身とし、該最大となるカラム値が他のデータベース装置のものである場合には該最大となるカラム値を送信してきた他のデータベース装置を起点に指定する情報を該他のデータベース装置に送信し、起点となったデータベース装置が、該最大となるカラム値以降のＮ個のカラム値を他のデータベース装置に送信することを特徴とする。
【００１４】
また、請求項３に記載の発明は、請求項１に記載のデータベース管理方法において、他のデータベース装置の処理部が、自身のテーブルの結合対象カラムから、受信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値を取得して、その取得したカラム値を起点のデータベース装置に送信し、起点のデータベース装置の処理部が、自身のテーブルの結合対象カラムから抽出した、送信したＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値および他のデータベース装置から受信したカラム値の中で最大となるカラム値を抽出し、起点のデータベース装置の処理部が、自身のテーブルの結合対象カラムから、該最大となるカラム値より大きい範囲の中で最も小さいカラム値以降のＮ個のカラム値を取得し、該取得したＮ個のカラム値を他のデータベース装置に送信することを特徴とする。
【００１５】
このような構成によれば、次のＮ個のカラム値を決定する際に、各データベース装置の昇順にソートされたテーブルから抽出した、既に結合対象としたＮ個のカラム値の中の最大値より大きい範囲の中で最も小さいカラム値を集めて、その抽出したカラム値同士を比較して最大となるカラム値を取得し、そのカラム値以降のカラム値を対象として等結合処理を開始するため、処理時間が短縮できる。すなわち、抽出したカラム値同士を比較して抽出した最大となるカラム値より小さいカラム値を次のＮ個のカラム値の中に含めたとしても、いずれかのテーブルでは、該次のＮ個のカラム値の一部が存在しないことが明らかであるので、処理時間の無駄となる。その処理時間の無駄を省くことができる。また、請求項２に記載の構成では、起点のデータベース装置を替えることによって、データベース装置間で、ほぼ均等に等結合処理を分担させることができ、処理負荷が大きいデータベース装置に処理が偏ることがなくなるため、処理時間を低減できる。
【００１６】
請求項５に記載の発明は、請求項１ないし請求項３のいずれか一項に記載の起点のデータベース装置のデータベース管理方法または他のデータベース装置のデータベース管理方法を、コンピュータとしてのデータベース装置に実行させるためのプログラムとした。
【００１７】
このようなプログラムをインストールされたコンピュータは、このプログラムに基づいた機能を実現することができる。
【発明の効果】
【００１８】
本発明によれば、３以上のデータベース装置によって構成される分散データベースシステムのテーブル等結合処理において、処理時間を低減する技術を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態の概要を示す図である。
【図２】本実施形態の概要のつづきを示す図である。
【図３】クライアント装置およびデータベース装置の各構成および機能を示す図である。
【図４】データベース装置の処理の流れを示す図である。
【図５】データベース装置の処理の流れを示す図である。
【図６】クライアント装置の処理の流れを示す図である。
【図７】従来技術における等結合処理について示す図である。
【発明を実施するための形態】
【００２０】
次に、本発明を実施するための形態（以降「本実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。
【００２１】
≪概要≫
本実施形態の概要について、図１および図２を用いて説明する。図１に示すように、分散データベースシステムは、各データベース装置１０（１０Ａ，１０Ｂ，１０Ｃ）とクライアント装置２０とがネットワーク６０を介して相互に通信可能に接続されている。各データベース装置１０Ａ，１０Ｂ，１０Ｃはそれぞれ結合対象カラムのカラム値を昇順にソートしたテーブルＡ１，Ｂ１，Ｃ１を格納している。まず、ステップ（ａ）では、クライアント装置２０が、データベース装置１０Ａを等結合処理の起点（結合起点）として指定し、等結合処理の対象となる各データベース装置１０Ａ，１０Ｂ，１０Ｃのデータベース装置名、テーブル名、および結合対象カラム名を示すクエリを、結合起点のデータベース装置１０Ａに送信する。なお、結合対象カラムは、テーブルＡ１についてはカラムｉ、テーブルＢ１についてはカラムｊ、テーブルＣ１についてはカラムｋとする。そして、図１には示していないが、データベース装置１０Ａは、受信したクエリを等結合相手のデータベース装置１０Ｂ，１０Ｃに転送する。
【００２２】
ステップ（ｂ）では、データベース装置１０Ａが、ブロック単位ソートマージジョイン法（須賀他，“情報統合サービスのための分散型情報統合アーキテクチャ及びジョイン方式の提案”，ＤＩＣＯＭＯ２００８，p.168-176）によって、Ｎ個（図１では、３個）の対象カラム値（結合対象カラムのカラム値）を等結合相手のデータベース装置１０Ｂ，１０Ｃに送信する。ただし、各テーブルＡ１，Ｂ１，Ｃ１の各カラムｉ，ｊ，ｋのカラム値は、昇順にソート済になっているものとする。また、Ｎは１以上の整数である。なお、図１では、対象カラム値は、数字で表しているが、文字等であっても構わない。そして、各データベース装置１０Ｂ，１０Ｃは対象カラム値を受信する。
【００２３】
ステップ（ｃ）では、データベース装置１０Ｂが、テーブルＢ１のカラムｊの値と受信した対象カラム値とを比較して、等しいカラム値が存在する場合にはそのカラム値に対して１を付し、等しいカラム値が存在しない場合にはそのカラム値に対して０を付して、受信した対象カラム値に対応する判定ビット列を生成する。例えば、対象カラム値が「２，３，８」であった場合は、「２，３」については、カラムｊにはそのカラム値「２，３」が存在しないので、判定ビットは０となる。対象カラム値が８の場合は、カラムｊにカラム値「８」が存在するので、判定ビットは１となる。すなわち、判定ビット列は０，０，１となる。そして、データベース装置１０Ｂは、その判定ビット列をデータベース装置１０Ａに送信する。
【００２４】
ステップ（ｄ）では、データベース装置１０Ｃが、テーブルＣ１のカラムｋの値と受信した対象カラム値とを比較して、等しいカラム値が存在する場合にはそのカラム値に対して１を付し、等しいカラム値が存在しない場合にはそのカラム値に対して０を付して、受信した対象カラム値に対応する判定ビット列を生成する。例えば、対象カラム値が「２，３，８」であった場合は、「２」については、カラムｋにはそのカラム値「２」が存在しないので、判定ビットは０となる。対象カラム値が３，８の場合は、カラムｊにカラム値「３，８」が存在するので、判定ビットは１となる。すなわち、判定ビット列は０，１，１となる。そして、データベース装置１０Ｃは、その判定ビット列をデータベース装置１０Ａに送信する。
【００２５】
ステップ（ｅ）では、データベース装置１０Ａは、受信した判定ビット列同士のＡＮＤ演算を行って、その結果を、結合結果のビット列として算出する。結合結果のビット列は、０，０，１である。そして、データベース装置１０Ａは、その結合結果のビット列を各データベース装置１０Ｂ，１０Ｃに送信する。そして、図１には記載していないが、各データベース１０Ａ，１０Ｂ，１０Ｃは、それぞれ、結合結果のビットが１となった対象カラム値「８」を含むレコード（結合可能レコード）をクライアント装置２０に送信する。
【００２６】
以上、ステップ（ｂ）〜（ｅ）に示すように、カラム値の比較処理は各データベース装置において並列に行われるため、等結合処理を行うためのテーブルの数の増加に比例して処理時間が長くなるということはなく、先行技術文献に記載の技術を用いた場合に比較して、処理時間が低減できる。また、すべてのテーブルに共通に存在するカラム値（結合可能カラム値）の算出は、ＡＮＤ演算によって容易に実行でき、カラム値そのものを用いる比較演算の場合に比較して、処理時間が低減できる。
【００２７】
図２に移って、ステップ（ｆ）では、データベース装置１０Ｂは、テーブルＢ１における次対象カラム値をデータベース装置１０Ａに送信する。ここでの次対象カラム値は、テーブルにおいて既に比較済みの対象カラム値の最大値より大きくかつその最大値に最も近い値とする。なお、各データベース装置１０Ａ，１０Ｂ，１０Ｃでは、次の対象カラム値の位置を示す位置ポインタを用いて、カラム値の読み出し位置が制御されている。すなわち、データベース装置１０Ｂでは、対象カラム値「２，３，８」が既に等結合処理の対象となっているため、位置ポインタは、８より大きくかつ８に最も近い１２に位置している。したがって、データベース装置１０Ｂは、次対象カラム値として１２をデータベース装置１０Ａに送信する。
【００２８】
ステップ（ｇ）では、データベース装置１０ＣのテーブルＣ１において、対象カラム値「２，３，８」が既に等結合処理の対象となっているため、位置ポインタは、８より大きくかつ８に最も近い１８に位置している。したがって、データベース装置１０Ｃは、次対象カラム値として１８をデータベース装置１０Ａに送信する。
【００２９】
データベース装置１０ＡのテーブルＡ１では、対象カラム値「２，３，８」が既に等結合処理の対象となっているため、位置ポインタは、８より大きくかつ８に最も近い１０に位置している。そこで、ステップ（ｈ）では、データベース装置１０Ａは、各データベース装置１０Ａ，１０Ｂ，１０Ｃの次対象カラム値「１０，１２，１８」を比較して、その中で最大となる次対象カラム値「１８」を抽出する。そして、その抽出した最大のカラム値「１８」を含むテーブルを有するデータベース装置１０Ｃを特定する。
【００３０】
ステップ（ｉ）では、データベース装置１０Ａは、データベース装置１０Ｃを新たな結合起点に指定する情報を、データベース装置１０Ｃに送信する。そして、分散データシステムは、データベース装置１０Ｃを結合起点として、ステップ（ｂ）〜（ｉ）を実行する。この際、ステップ（ｂ）における対象カラム値は、テーブルＣ１から取得され、１８，１９，２２となる。
【００３１】
以上、ステップ（ｈ）に示すように、各テーブルの次対象カラム値が最大となる値から、等結合処理を開始するため、処理時間を短縮することが可能となる。すなわち、最大の次対象カラム値より小さいカラム値を結合対象カラムのカラム値としても、いずれかのテーブルにはその最大の次対象カラム値より小さいカラム値が存在しないことが明らかであるので、処理時間の無駄となる。その処理時間の無駄を省くことができる。また、ステップ（ｉ）のように、結合起点となるデータベース装置１０を替えることによって、データベース装置１０Ａ，１０Ｂ，１０Ｃの中で、ほぼ均等に処理を分担させることができ、処理負荷が大きいデータベース装置１０に処理が偏ることがなくなるため、処理時間を低減できる。
【００３２】
≪クライアント装置≫
次に、クライアント装置の構成および機能について、図３を用いて説明する。クライアント装置２０は、ネットワーク６０を介して、データベース装置１０Ａ，１０Ｂ，１０Ｃと通信可能に接続されている。なお、図３には、クライアント装置２０は、１つしか記載されていないが、２以上であっても構わない。
【００３３】
クライアント装置２０は、処理部２１と記憶部２２とを備える。処理部２１は、コンピュータのＣＰＵとメインメモリとで構成され、記憶部２２に格納されているアプリケーションプログラムをメインメモリに展開して、各機能を具現化する。記憶部２２は、各種プログラムや処理部２１の演算結果を記憶する。処理部２１は、図示しない入力装置を介して、等結合処理の依頼およびどのデータベース装置１０を結合起点とするかを指定する情報を受け付ける。処理部２１は、等結合処理の対象となる複数個のデータベース装置名、テーブル名、および結合対象カラム名を示すクエリを、結合起点に指定されたデータベース装置１０に送信する。なお、処理部２１は、クエリを記憶部２２に記憶する。
【００３４】
処理部２１は、各データベース装置１０から結合可能レコード（すべてのテーブルにおいて結合対象カラムのカラム値が同一であるレコード）を逐次受信し、同一のカラム値を含む結合可能レコード同士を結合して生成した結合結果レコードを記憶部２２に記憶する。なお、結合可能レコードとは、前記したように、結合対象カラムの値が等しいカラム値を含むレコードのことである。また、処理部２１は、データベース装置１０から結合処理完了通知を受信した場合、結合結果レコードを作成する。なお、結合処理完了通知とは、いずれかのデータベース装置１０のテーブルの結合対象カラムの値がすべて等結合処理済になった場合（テーブルの終端に位置ポインタが設定された場合）に、等結合処理が完了したこと通知する情報である。
【００３５】
≪データベース装置≫
次に、データベース装置の構成および機能について、図３を用いて説明する。データベース装置１０Ａ，１０Ｂ，１０Ｃは、ネットワーク６０を介して、クライアント装置２０と通信可能に接続されている。各データベース装置１０Ａ，１０Ｂ，１０Ｃは、同じ構成であるので、データベース装置１０Ａ（１０）を代表させて、詳細な説明を行う。なお、図３には、データベース装置１０は、３つしか記載されていないが、４以上であっても構わない。
【００３６】
データベース装置１０は、処理部１１と記憶部１２とを備える。処理部１１は、コンピュータのＣＰＵとメインメモリとで構成され、記憶部１２に格納されているアプリケーションプログラムをメインメモリに展開して、各機能を具現化する。記憶部１２は、各種プログラムや処理部１１の演算結果を記憶する。
【００３７】
処理部１１の機能は、図３に示すように、結合クエリ送受信部１１１、データ送受信部１１２、ソートマージ結合処理部１１３、判定ビット作成部１１４、結合結果ビット列演算部１１５、結合レコード送信部１１６、位置ポインタ比較部１１７、およびテーブル管理部１１８を備える。
【００３８】
結合起点に指定されているデータベース装置１０の結合クエリ送受信部１１１は、クライアント装置２０からクエリを受信する。そして、結合クエリ送受信部１１１は、受信したクエリを、そのクエリに示されている等結合相手のデータベース装置１０に転送する。なお、等結合相手のデータベース装置１０の結合クエリ送受信部１１１は、転送されたクエリを受信する。
【００３９】
結合起点に指定されているデータベース装置１０のデータ送受信部１１２は、位置ポインタ以降のＮ個の対象カラム値を等結合相手のデータベース装置１０に送信する。また、データ送受信部１１２は、Ｎ個の対象カラム値に対する判定ビット列を等結合相手のデータベース装置１０から受信し、その判定ビット列から算出された結合結果のビット列を等結合相手のデータベース装置１０に送信する。なお、等結合相手のデータベース装置１０のデータ送受信部１１２は、結合起点に指定されているデータベース装置１０から、Ｎ個の対象カラム値および結合結果のビット列を受信し、判定ビット列を結合起点に指定されているデータベース装置１０から送信する。
【００４０】
等結合相手のデータベース装置１０のソートマージ結合処理部１１３は、ソートマージ結合法（例えば、増永良文著，“リレーショナルデータベース入門［新訂版］−データモデル・ＳＱＬ・管理システム−”，株式会社サイエンス社，2003年1月25日，p.227-229）に基づいて、受信した対象カラム値とテーブルの結合対象カラムのカラム値とを比較する。
【００４１】
判定ビット作成部１１４は、ソートマージ結合処理部１１３によって比較されたカラム値に対して、等しいカラム値がある場合にはそのカラム値に対して１を付し、等しいカラム値がない場合にはそのカラム値に対して０を付して、判定ビット列を生成する。
【００４２】
結合起点に指定されたデータベース装置１０の結合結果ビット列演算部１１５は、等結合相手のデータベース装置１０から受信した判定ビット列のＡＮＤ演算を行って、その演算結果を結合結果のビット列として、等結合相手のデータベース装置１０に送信する。
【００４３】
結合レコード送信部１１６は、結合結果ビット列演算部１１５によって算出された結合結果のビット列に基づいて、結合結果のビットが１となっている対象カラム値を含む結合可能レコードを抽出し、その抽出した結合可能レコードをクライアント装置２０に送信する。
【００４４】
結合起点に指定されたデータベース装置１０の位置ポインタ比較部１１７は、自身の次対象カラム値および等結合相手のデータベース装置の次対象カラム値を取得し（図２参照）、その取得したカラム値の大きさを比較し、最も大きなカラム値を送信してきたデータベース装置１０に対して、結合起点に指定する情報を送信する。
【００４５】
テーブル管理部１１８は、記憶部１２に記憶しているテーブルを管理する。具体的には、テーブル管理部１１８は、テーブルのレコード位置を指定するために、位置ポインタを制御する。なお、等結合処理の開始前では、この位置ポインタは、テーブルの先頭のレコードに設定されるものとする。また、位置ポインタは、読み出すカラム値がなくなった場合には、テーブルの終端を示す値に位置する。
【００４６】
≪データベース装置の処理≫
次に、分散データベースシステムにおける各データベース装置１０Ａ，１０Ｂ，１０Ｃの処理の流れについて、結合起点としてデータベース装置１０Ａが指定された場合を代表させて、図４および図５を用いて説明する（適宜図３参照）。図４は、図１に示す概要における処理の詳細を示し、図５は、図２に示す概要における処理の詳細を示している。
【００４７】
まず、図４のステップＳ４０１では、データベース装置１０Ａの結合クエリ送受信部１１１が、クライアント装置２０から、等結合処理の対象となる各データベース装置名、テーブル名、および結合対象カラム名を示すクエリを受信する。ステップＳ４０２では、データベース装置１０Ａの結合クエリ送受信部１１１が、受信したクエリを、等結合相手のデータベース装置１０Ｂ，１０Ｃに転送する。ステップＳ４０３では、データベース装置１０Ｂ，１０Ｃの結合クエリ送受信部１１１が、転送されたクエリを受信する。
【００４８】
ステップＳ４０４では、データベース装置１０Ａのデータ送受信部１１２が、結合対象カラムの位置ポインタ以降のＮ個の対象カラム値を、等結合相手のデータベース装置１０Ｂ，１０Ｃに送信する。ステップＳ４０５では、データベース装置１０Ｂ，１０Ｃのデータ送受信部１１２が、Ｎ個の対象カラム値を受信する。ステップＳ４０６では、データベース装置１０Ｂ，１０Ｃのソートマージ結合処理部１１３が、ソートマージ結合処理を実行し、受信した対象カラム値とテーブルの結合対象カラムのカラム値とを比較する。ステップＳ４０７では、データベース装置１０Ｂ，１０Ｃの判定ビット作成部１１４が、ソートマージ結合処理部１１３によって比較された結果に基づいて、等しいカラム値がある場合には１を付し、等しいカラム値がない場合には０を付して、判定ビット列を生成する。そして、データ送受信部１１２が、生成した判定ビット列を、データベース装置１０Ａに送信する。
【００４９】
ステップＳ４０８では、データベース装置１０Ａのデータ送受信部１１２が、判定ビット列を受信する。ステップＳ４０９では、データベース装置１０Ａの結合結果ビット列演算部１１５が、受信した判定ビット列のＡＮＤ演算を実行し、その演算結果を結合結果のビット列として算出する。そして、データ送受信部１１５が、結合結果のビット列をデータベース装置１０Ｂ，１０Ｃに送信する。ステップＳ４１２では、データベース装置１０Ｂ，１０Ｃのデータ送受信部１１２が、結合結果のビット列を受信する。
【００５０】
ステップＳ４１０およびステップＳ４１３では、結合レコード送信部１１６が、結合結果のビット列に１が含まれているか否かを判定する。結合結果のビット列に１が含まれている場合（ステップＳ４１０，Ｓ４１３でＹｅｓ）、ステップＳ４１１およびＳ４１４では、結合レコード送信部１１６が、結合結果のビット列の１の位置に該当するカラム値を含むレコード（結合可能レコード）をクライアント装置２０へ送信する。また、結合結果のビット列に１が含まれていない場合（ステップＳ４１０、Ｓ４１３でＮｏ）、結合レコード送信部１１６は、ステップＳ４１１，Ｓ４１４をスキップする。
【００５１】
処理は図５に進み、ステップＳ４１５では、データベース装置１０Ａの位置ポインタ比較部１１７が、自身のテーブルの結合対象カラムから次対象カラム値を取得する。そして、ステップＳ４１６では、データベース装置１０Ｂ，１０Ｃの位置ポインタ比較部１１７が、自身のテーブルの結合対象カラムから次対象カラム値を取得し、その取得した次対象カラム値をデータベース装置１０Ａに送信する。ステップＳ４１７では、データベース装置１０Ａの位置ポインタ比較部１１７が、ステップＳ４１５で取得した次対象カラム値およびＳ４１６で送信された次対象カラム値のいずれかが、テーブルの終端を示しているか否かを判定する。そして、テーブルの終端を示すものが無い場合（ステップＳ４１７でＮｏ）、ステップＳ４１８では、位置ポインタ比較部１１７が、次対象カラム値の最大値を抽出する。次に、ステップＳ４１９では、位置ポインタ比較部１１７が、抽出した最大値が自身のテーブルのカラム値か否かを判定する。抽出した最大値が自身のテーブルのカラム値である場合（ステップＳ４１９でＹｅｓ）、処理はステップＳ４０４（図４参照）へ戻る。
【００５２】
抽出した最大値が自身のテーブルのカラム値でない場合（ステップＳ４１９でＮｏ）、ステップＳ４２０では、位置ポインタ比較部１１７が、最大の対象カラム値を送信してきたデータベース装置１０へ結合起点移動通知を送信する。この結合起点移動通知は、結合起点を指定する情報である。その後、ステップＳ４２４に示すように、結合起点移動通知を受信したデータベース装置１０が結合起点となって、データベース装置１０間でステップＳ４０４〜Ｓ４２０と同様の処理が繰り返される。
【００５３】
ステップＳ４１７で、テーブルの終端をしめすものが有った場合（ステップＳ４１７でＹｅｓ）、ステップＳ４２１で、データベース装置１０Ａの位置ポインタ比較部１１７が、クライアント装置２０へ、等結合処理を終了することを意味する結合処理完了通知を送信する。そして、ステップＳ４２２では、位置ポインタ比較部１１７が、結合処理完了通知を、データベース装置１０Ｂ，１０Ｃへ送信し、処理部１１は処理を終了する。ステップＳ４２３では、データベース装置１０Ｂ，１０Ｃの位置ポインタ比較部１１７が、結合処理完了通知を受信し、処理部１１は処理を終了する。
【００５４】
≪クライアント装置の処理≫
次に、クライアント装置２０の処理の流れについて、図６を用いて説明する（適宜図３参照）。ステップＳ６０１では、クライアント装置２０の処理部２１が結合起点のデータベース装置１０にクエリを送信する。そして、送信したクエリは、処理部２１のメインメモリまたは記憶部２２に記憶される。
【００５５】
ステップＳ６０２では、データベース装置１０から結合可能レコードを受信する。ステップＳ６０３では、処理部２１が、各データベース装置１０から受信した結合可能レコードに含まれる結合対象カラムのカラム値が同一のレコード同士を結合処理して、結合結果レコードとして処理部２１のメインメモリまたは記憶部２２に記憶する。なお、この結合処理において、クライアント装置２０は、既にステップＳ６０１において結合対象カラム名を記憶しているので、受信した結合可能レコードの結合可能カラムのカラム値が同一のレコードを選択することができる。
【００５６】
ステップＳ６０４では、処理部２１が、データベース装置１０から結合処理完了通知を受信したか否かを判定する。そして、データベース装置１０から結合処理完了通知を受信した場合（ステップＳ６０４でＹｅｓ）、ステップＳ６０５では、処理部２１が、処理部２１のメインメモリまたは記憶部２２に記憶されている結合結果レコードをまとめ、結合結果テーブルを作成する。また、データベース装置１０から結合処理完了通知を受信していない場合（ステップＳ６０４でＮｏ）、処理は、ステップＳ６０２へ戻る。
【００５７】
（変形例）
本実施形態では、図２のステップ（ｉ）に示すように、結合起点をデータベース装置１０Ａからデータベース装置１０Ｃに移動するようにしたが、変形例では、結合起点を移動しない場合について説明する。変形例では、ステップ（ｈ）において、次対象カラム値の最大値１８を抽出した後、テーブルＡ１のカラムｉにおいてカラム値が１８以上である、２１，２６，３２を対象カラム値として、図１に示すステップ（ｂ）の処理を実行する。言い換えると、テーブルＡ１において、次対象カラム値の最大値「１８」より大きい範囲の中で最も小さいカラム値「２１」に位置ポインタが設定され、その位置ポインタの設定されたカラム値「２１」以降のカラム値「２１，２６，３２」が選択される。この変形例における処理によっても、対象カラム値「１０，１３，１７」を順番に選択する場合に比較して、処理時間を低減することが可能となる。
【００５８】
以上、本実施形態および変形例のデータベース装置１０によれば、ソートマージ結合処理（ステップＳ４０６、図４参照）を、データベース装置１０ごとに並列（同時）に実行することが可能になるため、等結合処理を行うためのテーブルの数の増加に比例して処理時間が長くなるということはなく、先行技術文献に記載の技術を用いた場合に比較して、処理時間が低減できる。また、すべてのテーブルに共通に存在するカラム値（結合可能カラム値）の算出は、ＡＮＤ演算によって容易に実行でき、カラム値そのものを用いる場合に比較して、処理時間の低減に効果がある。また、図５のステップＳ４１８において、各データベース装置１０の次対象カラム値のうち、最大の対象カラム値以降のＮ個の対象カラム値を用いることによって、処理時間を低減することが可能になる。
【００５９】
また、本実施形態のように、結合起点となるデータベース装置１０を替えることによって、データベース装置１０Ａ，１０Ｂ，１０Ｃの中で、確率的にはほぼ均等に処理を分担させることによって、処理負荷が大きいデータベース装置１０に、処理負荷が偏ることがなくなるため、処理時間を低減できる。また、テーブルの結合対象カラムのカラム値のソートは、昇順でなく降順でもかまわない。ただし、カラム値が降順にソートされる場合には、図２のステップ（ｈ）における次対象カラム値の抽出において、最小値を抽出すれば良い。また、判定ビットの１または０は、本実施形態とは逆に、等しいカラム値が存在する場合にはそのカラム値に対して０を付し、等しいカラム値が存在しない場合にはそのカラム値に対して１を付して、結合結果のビットが０となった対象カラム値を含むレコードをクライアント装置２０に送信しても良い。
【００６０】
また、本実施形態において、データベース装置１０（図２参照）の各部の処理は、データベース装置１０をコンピュータで実現したときに搭載されるプログラムによって実現されてもよい。このプログラムは、通信回線を介して提供することもできるし、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）等のコンピュータ読み取り可能な記録媒体に書き込んで配布することも可能である。
【符号の説明】
【００６１】
１０（１０Ａ，１０Ｂ，１０Ｃ）    データベース装置
１１    処理部
１２    記憶部
２０    クライアント装置
２１    処理部
２２    記憶部
６０    ネットワーク
１１１  結合クエリ送受信部
１１２  カラム値ブロック作成部
１１３  データ送受信部
１１４  判定ビット作成部
１１５  結合結果ビット列演算部
１１６  結合レコード送信部
１１７  位置ポインタ比較部
１１８  テーブル管理部
【図１】
2010272030.tif 000003
【図２】
2010272030.tif 000004
【図３】
2010272030.tif 000005
【図４】
2010272030.tif 000006
【図５】
2010272030.tif 000007
【図６】
2010272030.tif 000008
【図７】
2010272030.tif 000009