分散データベースの質問処理最適化方式
【発明の詳細な説明】
【０００１】
【技術分野】本発明は、分散データベースの質問処理最適化方式に関し、より詳細には、リレーション（Relation：関係）のｎ次の次数の概念を導入し、その定量化を図る分散データベースの質問処理最適化方式に関する。
【０００２】
【従来技術】データベースとしては、集中化して利用するものと、分散化して利用するものとがあり、データベースの間では、必要に応じてデータを取り出すことができるようになっていることが必要である。また、コンピュータシステムやネットワークの技術の進歩につれて、分散データベースの問題が重要になってきている。分散データベースの理論については多くの重要な問題が残されている。分散データベースの質問処理の最適化はその中の一つである。分散データベースは、従来の集中データベースと比べてその挙動が大きく変わっている。質問処理だけを対象としても、通信回線上でのデータ転送に応じて、質問処理の最適化も違う手法を用いざるを得ない。
【０００３】文献■「分散データベースの木質問の最適化」（李紅，佐藤 洋 データベース・システム研究会64-6，プログラミング言語研究会26-3，September 1990.）には、分散データベースの木質問処理の準結合による解法の最適スケジュールを求める問題について述べられている。すなわち、問題を木質問に限り、任意の関係を簡約する（reduce）ための準結合の系列より成るスケジュールを考え、全回線使用時間を最適化する最適化問題について考察している。また、文献■「分散データベースの質問処理の最適化に関する考察」（李紅，佐藤 洋 データベース・システム研究会64-6，March 1988.）には、回線使用時間と応答時間の最適な解を求めるアプローチとして、複数属性による結合・準結合について検討されている。しかし、今までの分散データベースの質問処理の最適化に関する研究は、分散データベースに多く存在する複数属性で結合する質問を考えていない傾向があるが、これは現実と掛け離れている。
【０００４】以下に、複数属性による結合について説明する。リレーションＲ1(a,b,c,…)とリレーションＲ2(a,b,c,…)と属性ａ,ｂ,ｃについて結合をする。これは、十分に研究されていない複数属性による結合の質問である。このような質問は、集中型のデータベースにはあまり現れないものであって、分散データベースに多く現れるものと考えてもよいだろう。集中の関係型データベースの場合は、異なる関係が同じ複数の属性を持つと、データの冗長になりやすいし、処理速度も遅くなりがちでデメリットが多い。また、実際に運用するとき、データベースの首尾一貫性，障害回復，データベースの保守，耐故障性などの面にも問題が出てくる。分散データベースの場合は、共通の属性をもつ関係を異なる場所に置くことはしばしば起こり、極端な例でいうと、水平に分割された関係は、その属性が皆同じである。従って、単一属性の結合のみを最適化の対象とするモデルが不完全だと考えられる。この問題を正面から取り扱う研究はほとんどないようである。
【０００５】次に、結合と準結合からレデューサー（reducer）を求める方法について述べる。通常、分散データベースの質問処理は三つのステップからなっている。（ａ）局所処理（step１），（ｂ）データ転送によるリレーションサイズの減少（step２），（ｃ）結果を求めるノードへのデータ転送と演算（step３）である。（ｂ）において、単一準結合を用いるものはたくさん提案されている。最近では、この段階で結合を導入する提案も見られる。図４（ａ）〜（ｅ）は、結合と準結合を説明するための図である。図（ａ）,（ｂ）はリレーションＡ,Ｂを、図（ｃ）は結合を、図（ｄ）,（ｅ）は準結合を各々示している。リレーションＡ（図(ａ)）とリレーションＢ（図(ｂ)）をａに関し結合すると、図（ｃ）のようになり、すべてのデータが包含される。リレーションＡ（図(ａ)）の属性ａに関し、リレーションＢ（図(ｂ)）へ準結合すると、リレーションＡの属性ａはａ1がリレーションＢの属性ａのａ1と共通するので、図（ｄ）のようになる。また、リレーションＡ（図(ａ)）の属性ｂに関し、リレーションＢ（図(ｂ)）へ準結合すると、リレーションＡの属性ｂのｂ2がリレーションＢの属性ｂのｂ2と共通するので、図（ｅ）のようになり、ｂ3のタプルは除外される。以上のように、準結合は結合による処理よりもデータ量を減らして取扱うことが可能であり、結合をレデューサーに入れることは又準結合で得られない効果があることもわかる。
【０００６】
【目的】本発明は、上述のごとき実情に鑑みてなされたもので、分散データベースの質問処理の最適化に対して、リレーションの次数の概念とその定量化及びこれをベースとした複数属性による準結合を用いた分散データベースの質問処理最適化方式を提供することを目的としてなされたものである。
【０００７】
【構成】本発明は、上記目的を達成するために、（１）ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、複数属性で結合する質問に現れる各リレーション間で、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合をメリットのある準結合として求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合手段とを有し、リレーションを前記次数決定手段で決定された次数毎に分けてリレーション集合を作成し、この最も低い次数のリレーション集合から最も高い次数のリレーション集合に対して順次、サイズの小さいリレーションに対してメリットのある準結合を得て、転送列を得ること、或いは、（２）ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、各ノード内のリレーションに対して、複数属性で結合する質問を射影と選択演算及びノード内での結合として実行する局所処理手段と、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、前記局所処理した各リレーションを次数毎に分けてリレーション集合を作る集合手段と、前記集合手段で求めた最も小さい次数のリレーション集合を除くすべてのリレーション集合から、異なる単一属性に対して最もサイズの小さいリレーションを一つずつ抽出して該最も小さい次数のリレーション集合に付加する抽出手段と、前記リレーション集合内でサイズの最も小さいリレーションから最も大きいリレーションまで順次、該リレーションとこれ以外のリレーション集合内のリレーションに対して、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合を求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合操作手段と、前記準結合操作手段で加えた転送列を次に高い次数のリレーション集合に追加する操作を、最も低い次数のリレーション集合から最も高い次数のリレーション集合まで繰り返して行う制御手段とを備え、前記制御手段は、最後に、結合されていないリレーションを直接に質問を求めるノードに転送するようにしたこと、更には、（３）前記（２）において、前記準結合操作手段は、他のリレーションと準結合を行ってもコストを低くできないとき、そのリレーションをリレーション集合から削除し、他のリレーションと共通の属性を持たないリレーションは削除しないことを特徴としている。
【０００８】まず、図３（ａ）〜（ｄ）に基づき、分散データベースの質問処理について説明する。図（ａ）は、コミュニケーションネットワークを示す図で、ノード（局所：サイト）■〜■を有し、ノード■には分散データベース（ＤＤＢ1：Distributed Data Base 1）を有し、ノード■には分散データベース（ＤＤＢ2）、ノード■には分散データベース（ＤＤＢ3）を各々有している。また、ＤＤＢ1におけるリレーションはＲ1(a,b)（ａ,ｂは属性）を、ＤＤＢ3におけるリレーションはＲ3(a,b)を各々有している。ノード■は質問を提出するノードである。例えば、質問Ｒ(a,b)＝Ｒ1(a,b)＊Ｒ3(a)（＊は結合を示す）があった場合、図（ｂ）〜（ｄ）の転送手順が考えられる。図（ｂ）においては、ノード■からＲ1(a,b)がノード■へ、ノード■よりＲ3(a)がノード■へ転送される。図（ｃ）において、ノード■よりＲ3(a)がノード■へ転送され、準結合を取り、ノード■からＲ1(a,b)がノード■へ転送される。図（ｄ）において、ノード■よりＲ1(a)がノード■へ転送され、準結合を取り、ノード■よりＲ3(a)がノード■へ転送され、準結合を取り、次にノード■よりＲ1(a,b)がノード■へ転送される。図（ｄ）における転送手順は、他の順番も考えられる。コストを最小とするこのような転送手順を提案することが本発明の目的である。
【０００９】次に、分散データベースのモデルとリレーションのｎ次次数の概念について、以下に説明する。
■分散データベースの質問処理最適化方式のモデルと記述法について説明する。本発明における分散データベースの質問処理の環境は、遠隔地に分散されたコンピュータネットワークである。そのため、質問処理のコストは通信にかかるコストのみとする。コストは転送するデータの量の線型関数とし、次の式を用いる。
Ｃ ＝ Ｃ0 ＋ βＸ …（１）
Ｃ0は通信設定のコスト、βは単位データを転送するコスト、Ｘは転送されるデータの量である。簡単のため、β＝１とする。
【００１０】質問の対象となるデータベースは、分散されたリレーショナルデータベースである。質問処理は、まずネットワークの各ノードで行われるものとする。したがって、扱うリレーションはそれぞれ異なるノードに格納されているとする。同じデータが複数存在するときは、事前に一つ選ばれたとする。データはリレーション上に均一に分布されているとし、リレーションの属性は統計的に互いに独立とする。以上の仮定は多くの文献で見られるが、ほとんどの文献では結合する属性は一つであることと仮定しているか、または、一般的な質問であると仮定するが、最適化の課程において、単一属性の結合しか考慮にいれていない。このような仮定は、実際に分散データベースの質問処理の多くに対して最適化の程度を妨げている。すなわち、分散データベース環境に多く現れる複数属性に関する結合が含まれていない。
【００１１】本発明においては、複数属性による結合を含む一般的な質問を最適化の対象とする。ここでは、リレーションをＵ,Ｒ等で表わし、属性をａ,ｂ,ｃ,…で表わす。Ｒ(a,b,c)は属性ａとｂとｃを持つリレーションを表わすことになる。Ｒ(a)はリレーションをａに射影した関係とする。Ｒ(a,b,c)のタプル（Tuple）数はｔまたはＴで記述する。Ｒ(a)のタプル数はｔaまたはｔR(a)で表わす。Ｄaは属性ａの領域の大きさを表わす。Ｒ(a)の選択度はｐaまたはｐRで、ｐ＝ｔa／Ｄaである。また、以下のような記号を使う。
Ｒ(a)：リレーションＲ(a)、または、そのタプル数|Ｒ|：リレーションＲのサイズｔab：属性ａとｂからなるリレーションＲ(a,b)のタプル数Ｒ1→Ｒ2：リレーションＲ1をリレーションＲ2に転送し、Ｒ2のノードで準結合する。
【００１２】■複数属性を持つリレーションの選択度と複数属性による準結合について説明する。従来、リレーションＲ(a,b)の選択度を論じるとき、単一属性に射影したリレーションＲ(a)（Ｒ(b)）の選択度ｐa＝ｔa／Ｄa（ｐb＝ｔb／Ｄb）しか取り扱われていない。ｔabはリレーションＲ(a,b)のタプル数とすると、次のような不等式が成り立つ。
ｔab ≦ ｔa × ｔb …（２）
上記の式の両端をＤa×Ｄbで割ると、次の式が成り立つ。
【００１３】
【数１】
【００１４】複数属性を持つリレーションＲ(a,b)の選択度ｐabは、上記式の左端によって決まる。
ｐab ＝ ｔab／(Ｄa × Ｄb) …（４）
同様に、タプルｔ個を持つリレーションＲ(ａ1，ａ2，…ａn)の選択度ｐは、ｐ ＝ ｔ／(Ｄa1 × Ｄa2 ×…Ｄan) …（５）
となる。後述するように、複数属性を準結合するとき、このように定義した複数属性の選択度を用いる方法は、単一属性のときと同様に合理性を持っている。したがって、タプル数ｔを持つリレーションＲが選択度ｐの複数（単一）属性のリレーションによって準結合された場合、準結合された後のリレーションのタプル数ｔ′がｔ′＝ ｔ × ｐ …（６）
となる。結合されない属性ｂのタプル数の期待値Ｒ′(b)は次の式で計算する。
【００１５】この式は、（６）式の近似式である。
Ｒ′(b) ＝ ｍｉｎ｛ｔ×ｐ，ｔR(b)｝ …（７）
式（２）は次のようになっていることが多い。
ｔab ≪ ｔa × ｔb …（８）
したがって、次式が成り立つ場合が多い。
ｐab ≪ ｐa × ｐb …（９）
この式は、左辺が複数属性（ａ,ｂ）で準結合する場合の選択度であり、右辺が属性ａと属性ｂを別々で準結合する場合の選択度である。複数属性による準結合のほうが、それぞれ単一属性による準結合より結合を受ける関係をより小さくすることを示している。属性の数が多ければ、レデューサーとしての効率も大きくなる。しかし、複数属性においては、その中の単一属性に注目すると、データの重複が存在する。
【００１６】■リレーションのｎ次次数の概念について説明する。前記文献■では、リレーションを１次か２次かについて定性的に述べている。ここで、定性的な意味における１次，２次とは、例えば、社員を特定する場合にコード（社員番号）がわかればコードのみで特定される。すなわち、１つの属性で特定されれば、それが１次である。しかし、コードがわからず、社員名のみで特定しようとすると、同姓同名のものは特定されないので、生年月日を加味して特定するような場合には、属性が２つ必要となり、これが２次である。本発明においては、もっとも一般的なケースに対してリレーションの次数を定量的に規定する。
【００１７】リレーションＲ(ａ1，ａ2，…ａn）のタプル数をＴとし、Ｒ(ａi)(i＝１,２,…ｎ)のタプル数をｔiとする。リレーションＲに対して整数Ｋi(i＝１,２,…ｎ)を次のように計算する。
Ｋ1 ＝ ｍｉｎ｛ｔ1，ｔ2，…ｔn｝
Ｋ2 ＝ ｍｉｎ｛ｔ1×ｔ2，ｔ1×ｔ3…ｔn-1×ｔn｝ …（１０）
… … Ｋn ＝ ｔ1×ｔ2×…×ｔnしたがって、Ｋ1 ≦ Ｋ2 ≦ … ≦ Ｋn …（１１）
Ｋ1 ≦ Ｔ ≦ Ｋn …（１２）
が成り立つ。
Ｋ1 ≦ Ｋ2 ≦ … ≦ Ｋm ≦ Ｔ ＜ Ｋm+1≦ … ≦ Ｋn …（１３）
のとき、リレーションＲの次数をｍとし、次のように書くことにする。
ｄ（Ｒ）＝ ｍ．
以上のことから、次の表１のリレーションＲ(a,b,c)は１次のリレーションである。
【００１８】
【表１】
【００１９】すなわち、表１より ｔ1＝８０，ｔ2＝１００，ｔ3＝６０であるので、Ｋ1 ＝ ｔ3 ＝ ６０Ｋ2 ＝ ｔ3 × ｔ1 ＝ ６０ × ８０ ＝ ４８００Ｋ3 ＝ ｔ1 × ｔ2 × ｔ3 ＝ ６０ × ８０ × １００＝４８００００となり、リレーションＲのタプル数Ｔ＝１００であるので、Ｋ1（＝６０）≦Ｔ（＝１００）＜Ｋ2（＝４８００）
が成り立つので、次数は１次である。次の表２のリレーションＲ(a,b,c)は２次のリレーションである。
【００２０】
【表２】
【００２１】すなわち、表２より、リレーションＲのタプル数Ｔ＝５０００であるので、Ｋ2（＝４８００）≦Ｔ（＝５０００）＜Ｋ3（＝４８００００）
が成り立つので、次数は２次である。
【００２２】次に、リレーションの次数と複数属性の準結合について説明する。前述では、リレーションの次数について説明した。この次数について定性的に説明すると、一般的には、リレーションの各属性のタプル数がリレーションのタプル数と多く違わなければその関係が１次のリレーションであるし、リレーションのタプル数がリレーション内の二つの属性のタプル数の積とほぼ同等なら、その関係は２次のリレーションである。同時に、属性ｎ個のリレーションの次数がｎのとき、リレーションのタプル数は全ての属性のタプルの積に近いであろう。
【００２３】複数の結合属性の持つリレーションを他のノードに転送するときに、次の３つのことに注意しなければならない。第１に転送されるデータの量、いわゆるコスト、第２に転送されるデータによって先方のリレーションはサイズがどのくらい減るか、これは、ベニフィト（benefit）と呼ばれ、転送されるデータの選択度と関係する。第３に転送されるデータの属性間の関連情報である。リレーションを属性に射影してから転送する場合は、射影によって他のデータとの間の対応情報が失われることがあるが、重複するデータの量が減ることになる。選択度は射影するたびに大幅に増える。次数の説明から分かるように、明らかにｎ個の属性を持つリレーションＲはその次数ｄ(Ｒ)が１とｎの間である。
【００２４】リレーションＲのタプル数をＴとし、射影されたリレーションＲ′のタプル数をＴ′とする。次式が成り立つ。
Ｔ′≦ ＴリレーションＲの次数を計算するための整数をＫとし、射影されたリレーションＲ′の次数を計算するための整数をＫ′とすると、前述した次数の説明によって、Ｋ′i ≧ Ｋi （１≦ｉ≦Ｒ′の属性数）
が成り立つ。上記の両式によって、Ｒ′の次数はＲの次数より増えないことを示している。このことから（Ａ）：“リレーションＲ(ａ1，ａ2，…ａn)の任意の射影Ｒ′の次数はＲの次数より増えることはない”ということが言える。実際に、射影した関係Ｒ′の次数はかなり小さくなることが多い。さらに“１次のリレーションの任意の射影は次数が１次である。”も言える。
【００２５】以下に、準結合を取るときのリレーションの次数について説明する。リレーションＲのタプル数をＴとし、リレーションＲ1(a1)の選択度はｐとする。準結合したあとのリレーションをＲ′とし、そのタプル数をＴ′とする。また、Ｒの各属性のタプル数をｔi(ｉ＝１,２,…ｎ)とし、Ｒ′の各属性のタプル数をｔ′i(ｉ＝１,２,…ｎ)とする。したがって、Ｔ′＝ Ｔ × p …（１４）
となる。これから次式が成り立つことを証明する。
Ｔ′＜ Ｋ′m+1 …（１５）
便宜のため、ｔ2≦ｔ3≦ … ≦ｔnとする。したがって、 K′m+1＝ min{t1×ｐ×min{T′,t2}×min{T′,t3}×…×min{T′,tm+1｝, min{T′,t2}×min{T′,t3}×…×min{T′,tm+2}} …（１６）
Ｔ′が式（１６）の右辺の計算結果に現れるなら、式（１５）が成り立つ。そうでないとき、式（１６）は次式になる。
K′m+1＝min｛t1×ｐ×t2×t3×…×tm+1，t2×t3×…×tm+2｝ …（１７）
式（１７）の右辺において、両値のどちらが小さくても、Ｋm+1の定義と式（１４）を考えると、Ｔ′＜Ｋ′m+1が成り立つ。すなわち、単一属性の準結合を受けたリレーションの次数が大きくならないことがわかる。
このことから（Ｂ）： "準結合したリレーションの非結合属性のタプル数の期待値は、式（７）を用いて計算するものとすれば、リレーションＲ(ａ1，ａ2，…ａn)は単一属性のリレーションＲ1(a1)によって準結合を取っても次数は増えない" ということが言える。
【００２６】後述する式（２５）と前記（Ｂ）の説明により、（Ｃ）： "準結合したリレーションの非結合属性のタプル数の期待値は、式（７）を用いて計算するものとすれば、リレーションＲ(a1，a2，…an)は他のリレーションによって準結合を取っても次数は増えない" ことが言える。又、式（１６）でＴ′≦ｔ2が成り立つようにｐを選べば（Ｃ1）：準結合を受けるリレーションは準結合したあとに１次のリレーションにも成り得る。
【００２７】前記（Ａ）と（Ｃ）ではリレーションが射影されること、または、準結合を受けることで次数が小さくなる（大きくはならない）こと、（Ｃ1）では、準結合するときの選択度が小さければ、準結合をしたあとのリレーションの次数も最小限に小さくなることがわかった。リレーションの次数が小さいとき、リレーション内でデータの重複度は少ない。例えば、１次のリレーションでは任意の二つの属性に射影すれば、そのデータは重複しない。一般的にｎ属性のリレーションは次数がｍ(ｍ＞１)のとき、そのリレーション内でタプル数のもっとも小さい単一属性はデータが極めて大きい回数重複する。前記（Ａ）により、このようなリレーションは部分属性に射影することによって次数を減らすことができるし、重複度も減らすことができる。一般的に許される重複度はリレーションの次数とリレーションのサイズの両方に関係する。リレーションの次数だけを考えると、ここで単にｍ＞ｎ／２のときには高次リレーションと呼び、そうでないときは低次リレーションと呼ぶことにする。すなわち、リレーションの各単一属性のタプル数をソートした列を考えるとき、その列の中間にある単一属性のデータが重複しているなら高次リレーションとなる。
【００２８】リレーションの次数の規定はリレーションの全体のタプル数に緊密に依存している。同じ属性を持つリレーションの全体のタプル数が小さいとき、その次数も通常小さい。複数属性による準結合をすることによって、準結合されたリレーションのタプル数は非常に小さくなり、これと同時にそのリレーションの次数も小さくなる。この現象は準結合する複数属性の数に関係する。複数属性の数が多ければ多いほど結合されたリレーションはタプル数と次数が小さくなる。リレーションの次数は、リレーションをどのように射影して転送するかを判断する重要な因子になっている。リレーションは、次数が高い程データが多く重複して、射影されたリレーションの選択度が小さい。このような高次のリレーションを部分属性に分割すると、より低い転送コストが得られる。
【００２９】図１は、本発明による分散データベースの質問処理最適化方式の一実施例を説明するための構成図で、図中、１は局所処理手段、２は集合手段、３は抽出手段、４は準結合操作手段、５は準結合手段、６は次数決定手段、６ａは判断手段、６ｂは分割手段、７は転送列作成手段、８は制御手段である。局所処理手段１は、ネットワークの各ノード内で複数属性による結合を含む質問に現われる各リレーションに対して、射影と選択と結合演算のすべて、あるいはいずれかを処理する。集合手段２は、該局所処理手段１に基づいて得たリレーションを次数毎に分けてリレーション集合を作る。複数属性による結合を含む質問に現われるリレーションの次数を得る。次数決定手段６は、前述した（１０）式〜（１３）式に基づいて決定される。準結合した結果のリレーションの次数が高次リレーションであるかどうかの判断をする判断手段６ａと、該判断手段６ａにより高次であると判断されたときには、部分属性に分割することにより低次のリレーションとする分割手段６ｂとを有する。該分割手段６ｂにより分割された低次のリレーションを、次に大きいサイズのリレーション集合へ付加するようにする。抽出手段３は、前記集合手段２によって作られたリレーション集合の中からサイズの最も小さい異なる単一属性のリレーションを抽出し、該リレーションを新たにリレーション集合に付加する。準結合操作手段４は、前記抽出手段３により付加されたリレーション集合内におけるリレーションから順次にメリットのある準結合を準結合手段５により求め、転送列作成手段７により転送列を得て、次に高い次数のリレーション集合に付加する。制御手段８は、前記各手段の低次から最高次のリレーション集合までの制御を行わせて最終的な転送列を求め、質問を求めるノードへ転送する。
【００３０】次に、図２に基づき、質問処理最適化方式の手順について説明する。これまでは、リレーションの次数の性質について説明したが、ここでは、リレーションの次数の性質を利用した質問処理最適化方式の手順について説明する。リレーションが準結合される場合を検討する。準結合されてから他のノードに転送するほうが、準結合せずに直接に他のノードに転送するよりコストが低い場合、その準結合をメリットのある準結合と呼ぶ。次の手順は、全回線使用時間（total time）を最適化の対象とするものである。
step１： 各ノードで局所処理、すなわちノード内での射影と選択演算及び結合を行う。
step２： 局所処理したリレーションを次数ごとにわけて、ｉ次のリレーションからなる集合をＧiとする。次数のもっとも小さい集合をＧlと書く。
step３： Ｇlを除くすべてのリレーションから、サイズの最も小さい異なる単一属性を一つずつ抽出する。抽出された単一属性のリレーションをＧ1に付加する。
【００３１】step４： リレーション集合Ｇ1から順次に次数のもっとも高いリレーション集合まで、次のような操作を繰り返して行う。
step4-1:集合内でリレーションをサイズの昇順にソートする。
step4-2:集合内でサイズの小さいリレーションからメリットのある準結合を求め、準結合をとり、これを転送列に加える。他のリレーションと準結合を行ってもメリットがないとき、そのリレーションは集合から削除される。ただし、他のリレーションと共通の属性を持たないリレーションは削除しない。
step4-3:準結合した結果のリレーションは、高次リレーションなら、それを適切に低次リレーションに分けて、次にサイズの大きいリレーションに対して準結合をとる。この操作は、この集合のもっともサイズの大きいリレーションまで行われる。
step4-4:上記の操作によって得られた結果は複数のリレーションも有りえる。これらのリレーションを次に高い次数のリレーション集合に追加する。最も次数の高いリレーション集合の場合は、その結果のリレーションを質問を求めるノードに転送する。
step５： 最後に、結合されていないリレーションを直接に質問を求めるノードに転送するか、または、前記step４で得られた結果を適切に射影し、準結合をしてから質問を求めるノードに転送するかを選択する。質問は質問を求めるノードで計算される。図２に示した手順を応答時間を小さくするための手段に直すには、以下のところで並列化を図ればよい。step３では、抽出されたリレーションを適切に全てのリレーション集合に付加する。step４を並列に実行する等の方法を取ればよい。以下の表３に具体的な実施例を示す。
【００３２】
【表３】
【００３３】分散データベースは、リレーションＲ1(a,b)とＲ2(a,b,c)とＲ3(a,b,c)から構成されている。リレーションの次数と次数の高さも前記表３に示している。この分散データベースに対して、リレーションＲ1とＲ2とＲ3を属性（a,b,c）について結合する質問が現れるとき、前記処理手順に従って実行する。通信設定のコストＣ0＝５とする。前記手順のstep２によって次数ごとのリレーション集合は次の通りである。
Ｇ1＝｛Ｒ1｝， Ｇ2＝｛Ｒ2｝， Ｇ3＝｛Ｒ3｝
前記手順のstep３にしたがって、リレーションＲ2とＲ3から単一属性のリレーションＲ2(b)とＲ3(a)とＲ3(c)を抽出し、それをリレーション集合Ｇ1に追加すると、Ｇ1は次のようになる。
Ｇ′1 ＝｛Ｒ3(a)，Ｒ2(b)，Ｒ3(c)，Ｒ1｝
【００３４】このリレーション集合において、前記手順のstep４により、次の転送が選ばれる。
Ｒ3(a) → Ｒ1Ｒ2(b)を使ってメリットのある準結合が得られなかったため、Ｒ2(b)をＧ2に付加しない。Ｒ3(a)とＲ1で結合した結果、Ｒ′1(a,b)とＲ3(c)をＧ2に追加する。Ｒ′1のタプル数は８０×０.３＝２４になる。リレーション集合Ｇ′2は次の通りとなる。
Ｇ′2 ＝｛Ｒ′1(a,b)，Ｒ3(c)，Ｒ2｝
前記手順のstep４にしたがって、Ｒ′1をＲ2に転送して準結合する。その結合結果は低次リレーションなので、リレーション集合Ｇ3に追加し（Ｒ3(c)はＲ2(b)と同じ理由でＧ3に付加せず）、リレーションＲ3と準結合を取る。結果として、次の転送スケジュールが得られる。
転送スケジュール： Ｒ3(a) → Ｒ1 → Ｒ2 → Ｒ3 →そのコストは次の式によって計算できる。
【００３５】
【数２】
【００３６】以下の表４に他の実施例を示す。
【００３７】
【表４】
【００３８】分散データベースは表４の関係から構成されているリレーションＲ1とＲ2とＲ3とＲ4を属性（a,b,c）について結合する質問のスケジュールを前記処理手順で求める。通信設定のコストＣ0＝５とする。前記手順のstep２と３によって、次数ごとのリレーション集合は次の通りである。
Ｇ′1＝｛Ｒ4(a)，Ｒ3(b)，Ｒ4(c)，Ｒ1，Ｒ2｝， Ｇ2＝｛Ｒ3，Ｒ4｝
リレーション集合Ｇ′1において、前記手順のstep４により、次の転送とリレーションが選ばれる。
Ｒ4(a) → Ｒ2 …（１８）
Ｒ3(b)が削除され、Ｇ′1で得られた結果Ｒ′2とＲ4(c)とＲ1をＧ2に付加すると、リレーション集合Ｇ′2は次の通りとなる。
Ｇ′2＝｛Ｒ′2(a,b)，Ｒ4(c)，Ｒ1，Ｒ3，Ｒ4｝
【００３９】前記手順のstep４にしたがって、次の転送スケジュールが選ばれる。
Ｒ′2(a,b) → Ｒ3(a,b) → Ｒ4(a,b,c) → …（１９）
前記手順のstep５では、関係Ｒ′4(b)をＲ1に転送し、準結合をしてから結果の求めるノードに転送する。
Ｒ′4(b) → Ｒ1 → …（２０）
前記（１８）,（１９）,（２０）から、最終転送スケジュールは次のようになる。
転送スケジュール：Ｒ4(a) → Ｒ2(a,b) → Ｒ3(a,b) → Ｒ4(a,b,c) →Ｒ′4(b) → Ｒ1 →そのコストは、次の式によって計算できる。
【００４０】
【数３】
【００４１】次に、複数属性を持つリレーションの選択度について説明する。ここでは、複数属性による準結合を行ったときの選択度について述べる。リレーションＵ(a,b,…)をリレーションＲ(a,b)により準結合を行う。リレーションＲ(a,b)を属性ａ,ｂに分けて別々に結合するのではなく、ａとｂペアを送って準結合するものとする。このとき、Ｒ(a,b)のタプルはＤa×ＤbからランダムにｔR個が選ばれたと考えると、リレーションＲ(a,b)の選択度ｐRは次の式となる。
ｐR ＝ ｔR／(Ｄa×Ｄb) …（２１）
Ｒ(a,b)のタプルをこのように選んだとすると、Ｒ(a,b)のａまたはｂの単一属性のタプル数の期待値が求められる。これを使って、特別の場合の近似式をｔaについてのみ与えると、ｔaの期待値は次のようになる。
【００４２】
【数４】
【００４３】ｔbについても同様である。これから準結合に用いるリレーションＲ(a,b)に関して、そのタプル数ｔの他、単一属性のタプル数ｔa，ｔbが与えられている場合を考える。このとき、ｔ個のタプルはランダムに選ばれるが、ｔaとｔbが与えられているため、前の場合のサブアンサンブルを考える必要があり、その選択度は前記（２１）と一致しない恐れがある。準結合を受けるリレーションＵ(a,b)のあるタプルχを考える。χの属性ａの値，ｂの値が、ａ,ｂの値の中にある確率ｐa，ｐbは、 ｐa ＝ ｔa／Ｄa， ｐb ＝ ｔb／Ｄb …（２３）
である。この条件が満たされた上でχの中のａｂ対の値がＲ(a,b)の中のａｂ対と一致する条件確率ｐabは、Ｒ(a,b)のａｂ対がｔa×ｔb個の対の中からランダムに選ばれると考えて、ｐab ＝ ｔ／(ｔa×ｔb) …（２４）
となる。（２３）のｐaとｐbの積とｐabを掛けて、Ｒ(a,b)の選択度ｐは、 ｐ ＝ ｐa×ｐb×ｐab ＝ ｔ／(Ｄa×Ｄb) …（２５）
となり、（２１）と一致していることが分かる。このようにして、（２１）または（２５）の選択度の公式は、十分な合理性を持つと考えられる。以上は２属性のことを考えたが、属性数が３以上の場合も同様に拡張できる。
【００４４】まず、すべてのもっとも小さい単一属性を考慮に入れる。単一属性のリレーションはサイズが小さくて、すべての情報を持っている。射影されるもっとも小さい単一属性は、高次のリレーションから分離される確率が高いため、転送コストも低い。次に、２次以上のリレーションの準結合を考える。この段階では、複数属性の準結合また結合が導入される。そのため、リレーションの属性の間にある対応情報の損失をかなり小さい程度に押さえることができ、かつ、小さい選択度（複数属性を持つリレーションの選択度）で他のリレーションを有効にレデュースすることができる。
【００４５】すべてのリレーションを単一属性に射影してから結合するという従来の方法について検討してみる。表３に示す分散データベースを例に取ることにする。リレーションＲ2にすべての単一属性を送って結合した結果、リレーションはサイズが216であるが、同様にしてすべての単一属性とリレーションＲ3と準結合した結果、リレーションはサイズが11520である。この数値と前述したすべての転送コスト121との差は明らかに非常に大きい。これは、単一属性の準結合を用いて高次リレーションのサイズが効果的に減らされないことを示している。単一属性の限界とも言える。
【００４６】また、リレーション（複数の属性を持つ）をレデューサーに加わることについて、本発明の手順はできるだけ多くのリレーションをレデューサーに入れている。まず、低次のリレーションを入れて、高次のリレーションを低次にしてから入れるようになっている。このようにして、結合による効果を得ることができる。各ノードのリレーションの次数や複数属性の選択度などの情報を管理しなければならないのは、ネットワークのオーバーヘッドを増やすのではないかという疑問点がある。しかし、実際の分散データベースを考えると、各ノードで多くとも数キロバイトの情報量が増えるだけで、大きい問題はない。
【００４７】
【効果】以上の説明から明らかなように、本発明によると、分散データベースに合うモデルを使って、分散データベースの質問処理最適化方式を提案しているので、複数属性による準結合をレデューサーに入れる方式が非常に有効で、結合演算も取り入れることができた。これらはリレーションのｎ次の次数の概念の導入とその定量化によって実現されている。また、転送コストを小さくすることができ、質問処理に要する全回線使用時間の短縮化が図れる。
【図面の簡単な説明】
【図１】 本発明による分散データベースの質問処理最適化方式の一実施例を説明するための構成図である。
【図２】 本発明による分散データベースの質問処理最適化方式の一実施例を示すフローチャートである。
【図３】 分散データベースの質問処理を説明する図である。
【図４】 リレーションの結合と準結合を説明するための図である。
【符号の説明】
１…局所処理手段、２…集合手段、３…抽出手段、４…準結合操作手段、５…準結合手段、６…次数決定手段、６ａ…判断手段、６ｂ…分割手段、７…転送列作成手段、８…制御手段。
【０００１】
【技術分野】本発明は、分散データベースの質問処理最適化方式に関し、より詳細には、リレーション（Relation：関係）のｎ次の次数の概念を導入し、その定量化を図る分散データベースの質問処理最適化方式に関する。
【０００２】
【従来技術】データベースとしては、集中化して利用するものと、分散化して利用するものとがあり、データベースの間では、必要に応じてデータを取り出すことができるようになっていることが必要である。また、コンピュータシステムやネットワークの技術の進歩につれて、分散データベースの問題が重要になってきている。分散データベースの理論については多くの重要な問題が残されている。分散データベースの質問処理の最適化はその中の一つである。分散データベースは、従来の集中データベースと比べてその挙動が大きく変わっている。質問処理だけを対象としても、通信回線上でのデータ転送に応じて、質問処理の最適化も違う手法を用いざるを得ない。
【０００３】文献
【０００４】以下に、複数属性による結合について説明する。リレーションＲ1(a,b,c,…)とリレーションＲ2(a,b,c,…)と属性ａ,ｂ,ｃについて結合をする。これは、十分に研究されていない複数属性による結合の質問である。このような質問は、集中型のデータベースにはあまり現れないものであって、分散データベースに多く現れるものと考えてもよいだろう。集中の関係型データベースの場合は、異なる関係が同じ複数の属性を持つと、データの冗長になりやすいし、処理速度も遅くなりがちでデメリットが多い。また、実際に運用するとき、データベースの首尾一貫性，障害回復，データベースの保守，耐故障性などの面にも問題が出てくる。分散データベースの場合は、共通の属性をもつ関係を異なる場所に置くことはしばしば起こり、極端な例でいうと、水平に分割された関係は、その属性が皆同じである。従って、単一属性の結合のみを最適化の対象とするモデルが不完全だと考えられる。この問題を正面から取り扱う研究はほとんどないようである。
【０００５】次に、結合と準結合からレデューサー（reducer）を求める方法について述べる。通常、分散データベースの質問処理は三つのステップからなっている。（ａ）局所処理（step１），（ｂ）データ転送によるリレーションサイズの減少（step２），（ｃ）結果を求めるノードへのデータ転送と演算（step３）である。（ｂ）において、単一準結合を用いるものはたくさん提案されている。最近では、この段階で結合を導入する提案も見られる。図４（ａ）〜（ｅ）は、結合と準結合を説明するための図である。図（ａ）,（ｂ）はリレーションＡ,Ｂを、図（ｃ）は結合を、図（ｄ）,（ｅ）は準結合を各々示している。リレーションＡ（図(ａ)）とリレーションＢ（図(ｂ)）をａに関し結合すると、図（ｃ）のようになり、すべてのデータが包含される。リレーションＡ（図(ａ)）の属性ａに関し、リレーションＢ（図(ｂ)）へ準結合すると、リレーションＡの属性ａはａ1がリレーションＢの属性ａのａ1と共通するので、図（ｄ）のようになる。また、リレーションＡ（図(ａ)）の属性ｂに関し、リレーションＢ（図(ｂ)）へ準結合すると、リレーションＡの属性ｂのｂ2がリレーションＢの属性ｂのｂ2と共通するので、図（ｅ）のようになり、ｂ3のタプルは除外される。以上のように、準結合は結合による処理よりもデータ量を減らして取扱うことが可能であり、結合をレデューサーに入れることは又準結合で得られない効果があることもわかる。
【０００６】
【目的】本発明は、上述のごとき実情に鑑みてなされたもので、分散データベースの質問処理の最適化に対して、リレーションの次数の概念とその定量化及びこれをベースとした複数属性による準結合を用いた分散データベースの質問処理最適化方式を提供することを目的としてなされたものである。
【０００７】
【構成】本発明は、上記目的を達成するために、（１）ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、複数属性で結合する質問に現れる各リレーション間で、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合をメリットのある準結合として求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合手段とを有し、リレーションを前記次数決定手段で決定された次数毎に分けてリレーション集合を作成し、この最も低い次数のリレーション集合から最も高い次数のリレーション集合に対して順次、サイズの小さいリレーションに対してメリットのある準結合を得て、転送列を得ること、或いは、（２）ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、各ノード内のリレーションに対して、複数属性で結合する質問を射影と選択演算及びノード内での結合として実行する局所処理手段と、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、前記局所処理した各リレーションを次数毎に分けてリレーション集合を作る集合手段と、前記集合手段で求めた最も小さい次数のリレーション集合を除くすべてのリレーション集合から、異なる単一属性に対して最もサイズの小さいリレーションを一つずつ抽出して該最も小さい次数のリレーション集合に付加する抽出手段と、前記リレーション集合内でサイズの最も小さいリレーションから最も大きいリレーションまで順次、該リレーションとこれ以外のリレーション集合内のリレーションに対して、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合を求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合操作手段と、前記準結合操作手段で加えた転送列を次に高い次数のリレーション集合に追加する操作を、最も低い次数のリレーション集合から最も高い次数のリレーション集合まで繰り返して行う制御手段とを備え、前記制御手段は、最後に、結合されていないリレーションを直接に質問を求めるノードに転送するようにしたこと、更には、（３）前記（２）において、前記準結合操作手段は、他のリレーションと準結合を行ってもコストを低くできないとき、そのリレーションをリレーション集合から削除し、他のリレーションと共通の属性を持たないリレーションは削除しないことを特徴としている。
【０００８】まず、図３（ａ）〜（ｄ）に基づき、分散データベースの質問処理について説明する。図（ａ）は、コミュニケーションネットワークを示す図で、ノード（局所：サイト）
【０００９】次に、分散データベースのモデルとリレーションのｎ次次数の概念について、以下に説明する。
Ｃ ＝ Ｃ0 ＋ βＸ …（１）
Ｃ0は通信設定のコスト、βは単位データを転送するコスト、Ｘは転送されるデータの量である。簡単のため、β＝１とする。
【００１０】質問の対象となるデータベースは、分散されたリレーショナルデータベースである。質問処理は、まずネットワークの各ノードで行われるものとする。したがって、扱うリレーションはそれぞれ異なるノードに格納されているとする。同じデータが複数存在するときは、事前に一つ選ばれたとする。データはリレーション上に均一に分布されているとし、リレーションの属性は統計的に互いに独立とする。以上の仮定は多くの文献で見られるが、ほとんどの文献では結合する属性は一つであることと仮定しているか、または、一般的な質問であると仮定するが、最適化の課程において、単一属性の結合しか考慮にいれていない。このような仮定は、実際に分散データベースの質問処理の多くに対して最適化の程度を妨げている。すなわち、分散データベース環境に多く現れる複数属性に関する結合が含まれていない。
【００１１】本発明においては、複数属性による結合を含む一般的な質問を最適化の対象とする。ここでは、リレーションをＵ,Ｒ等で表わし、属性をａ,ｂ,ｃ,…で表わす。Ｒ(a,b,c)は属性ａとｂとｃを持つリレーションを表わすことになる。Ｒ(a)はリレーションをａに射影した関係とする。Ｒ(a,b,c)のタプル（Tuple）数はｔまたはＴで記述する。Ｒ(a)のタプル数はｔaまたはｔR(a)で表わす。Ｄaは属性ａの領域の大きさを表わす。Ｒ(a)の選択度はｐaまたはｐRで、ｐ＝ｔa／Ｄaである。また、以下のような記号を使う。
Ｒ(a)：リレーションＲ(a)、または、そのタプル数|Ｒ|：リレーションＲのサイズｔab：属性ａとｂからなるリレーションＲ(a,b)のタプル数Ｒ1→Ｒ2：リレーションＲ1をリレーションＲ2に転送し、Ｒ2のノードで準結合する。
【００１２】
ｔab ≦ ｔa × ｔb …（２）
上記の式の両端をＤa×Ｄbで割ると、次の式が成り立つ。
【００１３】
【数１】
【００１４】複数属性を持つリレーションＲ(a,b)の選択度ｐabは、上記式の左端によって決まる。
ｐab ＝ ｔab／(Ｄa × Ｄb) …（４）
同様に、タプルｔ個を持つリレーションＲ(ａ1，ａ2，…ａn)の選択度ｐは、ｐ ＝ ｔ／(Ｄa1 × Ｄa2 ×…Ｄan) …（５）
となる。後述するように、複数属性を準結合するとき、このように定義した複数属性の選択度を用いる方法は、単一属性のときと同様に合理性を持っている。したがって、タプル数ｔを持つリレーションＲが選択度ｐの複数（単一）属性のリレーションによって準結合された場合、準結合された後のリレーションのタプル数ｔ′がｔ′＝ ｔ × ｐ …（６）
となる。結合されない属性ｂのタプル数の期待値Ｒ′(b)は次の式で計算する。
【００１５】この式は、（６）式の近似式である。
Ｒ′(b) ＝ ｍｉｎ｛ｔ×ｐ，ｔR(b)｝ …（７）
式（２）は次のようになっていることが多い。
ｔab ≪ ｔa × ｔb …（８）
したがって、次式が成り立つ場合が多い。
ｐab ≪ ｐa × ｐb …（９）
この式は、左辺が複数属性（ａ,ｂ）で準結合する場合の選択度であり、右辺が属性ａと属性ｂを別々で準結合する場合の選択度である。複数属性による準結合のほうが、それぞれ単一属性による準結合より結合を受ける関係をより小さくすることを示している。属性の数が多ければ、レデューサーとしての効率も大きくなる。しかし、複数属性においては、その中の単一属性に注目すると、データの重複が存在する。
【００１６】
【００１７】リレーションＲ(ａ1，ａ2，…ａn）のタプル数をＴとし、Ｒ(ａi)(i＝１,２,…ｎ)のタプル数をｔiとする。リレーションＲに対して整数Ｋi(i＝１,２,…ｎ)を次のように計算する。
Ｋ1 ＝ ｍｉｎ｛ｔ1，ｔ2，…ｔn｝
Ｋ2 ＝ ｍｉｎ｛ｔ1×ｔ2，ｔ1×ｔ3…ｔn-1×ｔn｝ …（１０）
… … Ｋn ＝ ｔ1×ｔ2×…×ｔnしたがって、Ｋ1 ≦ Ｋ2 ≦ … ≦ Ｋn …（１１）
Ｋ1 ≦ Ｔ ≦ Ｋn …（１２）
が成り立つ。
Ｋ1 ≦ Ｋ2 ≦ … ≦ Ｋm ≦ Ｔ ＜ Ｋm+1≦ … ≦ Ｋn …（１３）
のとき、リレーションＲの次数をｍとし、次のように書くことにする。
ｄ（Ｒ）＝ ｍ．
以上のことから、次の表１のリレーションＲ(a,b,c)は１次のリレーションである。
【００１８】
【表１】
【００１９】すなわち、表１より ｔ1＝８０，ｔ2＝１００，ｔ3＝６０であるので、Ｋ1 ＝ ｔ3 ＝ ６０Ｋ2 ＝ ｔ3 × ｔ1 ＝ ６０ × ８０ ＝ ４８００Ｋ3 ＝ ｔ1 × ｔ2 × ｔ3 ＝ ６０ × ８０ × １００＝４８００００となり、リレーションＲのタプル数Ｔ＝１００であるので、Ｋ1（＝６０）≦Ｔ（＝１００）＜Ｋ2（＝４８００）
が成り立つので、次数は１次である。次の表２のリレーションＲ(a,b,c)は２次のリレーションである。
【００２０】
【表２】
【００２１】すなわち、表２より、リレーションＲのタプル数Ｔ＝５０００であるので、Ｋ2（＝４８００）≦Ｔ（＝５０００）＜Ｋ3（＝４８００００）
が成り立つので、次数は２次である。
【００２２】次に、リレーションの次数と複数属性の準結合について説明する。前述では、リレーションの次数について説明した。この次数について定性的に説明すると、一般的には、リレーションの各属性のタプル数がリレーションのタプル数と多く違わなければその関係が１次のリレーションであるし、リレーションのタプル数がリレーション内の二つの属性のタプル数の積とほぼ同等なら、その関係は２次のリレーションである。同時に、属性ｎ個のリレーションの次数がｎのとき、リレーションのタプル数は全ての属性のタプルの積に近いであろう。
【００２３】複数の結合属性の持つリレーションを他のノードに転送するときに、次の３つのことに注意しなければならない。第１に転送されるデータの量、いわゆるコスト、第２に転送されるデータによって先方のリレーションはサイズがどのくらい減るか、これは、ベニフィト（benefit）と呼ばれ、転送されるデータの選択度と関係する。第３に転送されるデータの属性間の関連情報である。リレーションを属性に射影してから転送する場合は、射影によって他のデータとの間の対応情報が失われることがあるが、重複するデータの量が減ることになる。選択度は射影するたびに大幅に増える。次数の説明から分かるように、明らかにｎ個の属性を持つリレーションＲはその次数ｄ(Ｒ)が１とｎの間である。
【００２４】リレーションＲのタプル数をＴとし、射影されたリレーションＲ′のタプル数をＴ′とする。次式が成り立つ。
Ｔ′≦ ＴリレーションＲの次数を計算するための整数をＫとし、射影されたリレーションＲ′の次数を計算するための整数をＫ′とすると、前述した次数の説明によって、Ｋ′i ≧ Ｋi （１≦ｉ≦Ｒ′の属性数）
が成り立つ。上記の両式によって、Ｒ′の次数はＲの次数より増えないことを示している。このことから（Ａ）：“リレーションＲ(ａ1，ａ2，…ａn)の任意の射影Ｒ′の次数はＲの次数より増えることはない”ということが言える。実際に、射影した関係Ｒ′の次数はかなり小さくなることが多い。さらに“１次のリレーションの任意の射影は次数が１次である。”も言える。
【００２５】以下に、準結合を取るときのリレーションの次数について説明する。リレーションＲのタプル数をＴとし、リレーションＲ1(a1)の選択度はｐとする。準結合したあとのリレーションをＲ′とし、そのタプル数をＴ′とする。また、Ｒの各属性のタプル数をｔi(ｉ＝１,２,…ｎ)とし、Ｒ′の各属性のタプル数をｔ′i(ｉ＝１,２,…ｎ)とする。したがって、Ｔ′＝ Ｔ × p …（１４）
となる。これから次式が成り立つことを証明する。
Ｔ′＜ Ｋ′m+1 …（１５）
便宜のため、ｔ2≦ｔ3≦ … ≦ｔnとする。したがって、 K′m+1＝ min{t1×ｐ×min{T′,t2}×min{T′,t3}×…×min{T′,tm+1｝, min{T′,t2}×min{T′,t3}×…×min{T′,tm+2}} …（１６）
Ｔ′が式（１６）の右辺の計算結果に現れるなら、式（１５）が成り立つ。そうでないとき、式（１６）は次式になる。
K′m+1＝min｛t1×ｐ×t2×t3×…×tm+1，t2×t3×…×tm+2｝ …（１７）
式（１７）の右辺において、両値のどちらが小さくても、Ｋm+1の定義と式（１４）を考えると、Ｔ′＜Ｋ′m+1が成り立つ。すなわち、単一属性の準結合を受けたリレーションの次数が大きくならないことがわかる。
このことから（Ｂ）： "準結合したリレーションの非結合属性のタプル数の期待値は、式（７）を用いて計算するものとすれば、リレーションＲ(ａ1，ａ2，…ａn)は単一属性のリレーションＲ1(a1)によって準結合を取っても次数は増えない" ということが言える。
【００２６】後述する式（２５）と前記（Ｂ）の説明により、（Ｃ）： "準結合したリレーションの非結合属性のタプル数の期待値は、式（７）を用いて計算するものとすれば、リレーションＲ(a1，a2，…an)は他のリレーションによって準結合を取っても次数は増えない" ことが言える。又、式（１６）でＴ′≦ｔ2が成り立つようにｐを選べば（Ｃ1）：準結合を受けるリレーションは準結合したあとに１次のリレーションにも成り得る。
【００２７】前記（Ａ）と（Ｃ）ではリレーションが射影されること、または、準結合を受けることで次数が小さくなる（大きくはならない）こと、（Ｃ1）では、準結合するときの選択度が小さければ、準結合をしたあとのリレーションの次数も最小限に小さくなることがわかった。リレーションの次数が小さいとき、リレーション内でデータの重複度は少ない。例えば、１次のリレーションでは任意の二つの属性に射影すれば、そのデータは重複しない。一般的にｎ属性のリレーションは次数がｍ(ｍ＞１)のとき、そのリレーション内でタプル数のもっとも小さい単一属性はデータが極めて大きい回数重複する。前記（Ａ）により、このようなリレーションは部分属性に射影することによって次数を減らすことができるし、重複度も減らすことができる。一般的に許される重複度はリレーションの次数とリレーションのサイズの両方に関係する。リレーションの次数だけを考えると、ここで単にｍ＞ｎ／２のときには高次リレーションと呼び、そうでないときは低次リレーションと呼ぶことにする。すなわち、リレーションの各単一属性のタプル数をソートした列を考えるとき、その列の中間にある単一属性のデータが重複しているなら高次リレーションとなる。
【００２８】リレーションの次数の規定はリレーションの全体のタプル数に緊密に依存している。同じ属性を持つリレーションの全体のタプル数が小さいとき、その次数も通常小さい。複数属性による準結合をすることによって、準結合されたリレーションのタプル数は非常に小さくなり、これと同時にそのリレーションの次数も小さくなる。この現象は準結合する複数属性の数に関係する。複数属性の数が多ければ多いほど結合されたリレーションはタプル数と次数が小さくなる。リレーションの次数は、リレーションをどのように射影して転送するかを判断する重要な因子になっている。リレーションは、次数が高い程データが多く重複して、射影されたリレーションの選択度が小さい。このような高次のリレーションを部分属性に分割すると、より低い転送コストが得られる。
【００２９】図１は、本発明による分散データベースの質問処理最適化方式の一実施例を説明するための構成図で、図中、１は局所処理手段、２は集合手段、３は抽出手段、４は準結合操作手段、５は準結合手段、６は次数決定手段、６ａは判断手段、６ｂは分割手段、７は転送列作成手段、８は制御手段である。局所処理手段１は、ネットワークの各ノード内で複数属性による結合を含む質問に現われる各リレーションに対して、射影と選択と結合演算のすべて、あるいはいずれかを処理する。集合手段２は、該局所処理手段１に基づいて得たリレーションを次数毎に分けてリレーション集合を作る。複数属性による結合を含む質問に現われるリレーションの次数を得る。次数決定手段６は、前述した（１０）式〜（１３）式に基づいて決定される。準結合した結果のリレーションの次数が高次リレーションであるかどうかの判断をする判断手段６ａと、該判断手段６ａにより高次であると判断されたときには、部分属性に分割することにより低次のリレーションとする分割手段６ｂとを有する。該分割手段６ｂにより分割された低次のリレーションを、次に大きいサイズのリレーション集合へ付加するようにする。抽出手段３は、前記集合手段２によって作られたリレーション集合の中からサイズの最も小さい異なる単一属性のリレーションを抽出し、該リレーションを新たにリレーション集合に付加する。準結合操作手段４は、前記抽出手段３により付加されたリレーション集合内におけるリレーションから順次にメリットのある準結合を準結合手段５により求め、転送列作成手段７により転送列を得て、次に高い次数のリレーション集合に付加する。制御手段８は、前記各手段の低次から最高次のリレーション集合までの制御を行わせて最終的な転送列を求め、質問を求めるノードへ転送する。
【００３０】次に、図２に基づき、質問処理最適化方式の手順について説明する。これまでは、リレーションの次数の性質について説明したが、ここでは、リレーションの次数の性質を利用した質問処理最適化方式の手順について説明する。リレーションが準結合される場合を検討する。準結合されてから他のノードに転送するほうが、準結合せずに直接に他のノードに転送するよりコストが低い場合、その準結合をメリットのある準結合と呼ぶ。次の手順は、全回線使用時間（total time）を最適化の対象とするものである。
step１： 各ノードで局所処理、すなわちノード内での射影と選択演算及び結合を行う。
step２： 局所処理したリレーションを次数ごとにわけて、ｉ次のリレーションからなる集合をＧiとする。次数のもっとも小さい集合をＧlと書く。
step３： Ｇlを除くすべてのリレーションから、サイズの最も小さい異なる単一属性を一つずつ抽出する。抽出された単一属性のリレーションをＧ1に付加する。
【００３１】step４： リレーション集合Ｇ1から順次に次数のもっとも高いリレーション集合まで、次のような操作を繰り返して行う。
step4-1:集合内でリレーションをサイズの昇順にソートする。
step4-2:集合内でサイズの小さいリレーションからメリットのある準結合を求め、準結合をとり、これを転送列に加える。他のリレーションと準結合を行ってもメリットがないとき、そのリレーションは集合から削除される。ただし、他のリレーションと共通の属性を持たないリレーションは削除しない。
step4-3:準結合した結果のリレーションは、高次リレーションなら、それを適切に低次リレーションに分けて、次にサイズの大きいリレーションに対して準結合をとる。この操作は、この集合のもっともサイズの大きいリレーションまで行われる。
step4-4:上記の操作によって得られた結果は複数のリレーションも有りえる。これらのリレーションを次に高い次数のリレーション集合に追加する。最も次数の高いリレーション集合の場合は、その結果のリレーションを質問を求めるノードに転送する。
step５： 最後に、結合されていないリレーションを直接に質問を求めるノードに転送するか、または、前記step４で得られた結果を適切に射影し、準結合をしてから質問を求めるノードに転送するかを選択する。質問は質問を求めるノードで計算される。図２に示した手順を応答時間を小さくするための手段に直すには、以下のところで並列化を図ればよい。step３では、抽出されたリレーションを適切に全てのリレーション集合に付加する。step４を並列に実行する等の方法を取ればよい。以下の表３に具体的な実施例を示す。
【００３２】
【表３】
【００３３】分散データベースは、リレーションＲ1(a,b)とＲ2(a,b,c)とＲ3(a,b,c)から構成されている。リレーションの次数と次数の高さも前記表３に示している。この分散データベースに対して、リレーションＲ1とＲ2とＲ3を属性（a,b,c）について結合する質問が現れるとき、前記処理手順に従って実行する。通信設定のコストＣ0＝５とする。前記手順のstep２によって次数ごとのリレーション集合は次の通りである。
Ｇ1＝｛Ｒ1｝， Ｇ2＝｛Ｒ2｝， Ｇ3＝｛Ｒ3｝
前記手順のstep３にしたがって、リレーションＲ2とＲ3から単一属性のリレーションＲ2(b)とＲ3(a)とＲ3(c)を抽出し、それをリレーション集合Ｇ1に追加すると、Ｇ1は次のようになる。
Ｇ′1 ＝｛Ｒ3(a)，Ｒ2(b)，Ｒ3(c)，Ｒ1｝
【００３４】このリレーション集合において、前記手順のstep４により、次の転送が選ばれる。
Ｒ3(a) → Ｒ1Ｒ2(b)を使ってメリットのある準結合が得られなかったため、Ｒ2(b)をＧ2に付加しない。Ｒ3(a)とＲ1で結合した結果、Ｒ′1(a,b)とＲ3(c)をＧ2に追加する。Ｒ′1のタプル数は８０×０.３＝２４になる。リレーション集合Ｇ′2は次の通りとなる。
Ｇ′2 ＝｛Ｒ′1(a,b)，Ｒ3(c)，Ｒ2｝
前記手順のstep４にしたがって、Ｒ′1をＲ2に転送して準結合する。その結合結果は低次リレーションなので、リレーション集合Ｇ3に追加し（Ｒ3(c)はＲ2(b)と同じ理由でＧ3に付加せず）、リレーションＲ3と準結合を取る。結果として、次の転送スケジュールが得られる。
転送スケジュール： Ｒ3(a) → Ｒ1 → Ｒ2 → Ｒ3 →そのコストは次の式によって計算できる。
【００３５】
【数２】
【００３６】以下の表４に他の実施例を示す。
【００３７】
【表４】
【００３８】分散データベースは表４の関係から構成されているリレーションＲ1とＲ2とＲ3とＲ4を属性（a,b,c）について結合する質問のスケジュールを前記処理手順で求める。通信設定のコストＣ0＝５とする。前記手順のstep２と３によって、次数ごとのリレーション集合は次の通りである。
Ｇ′1＝｛Ｒ4(a)，Ｒ3(b)，Ｒ4(c)，Ｒ1，Ｒ2｝， Ｇ2＝｛Ｒ3，Ｒ4｝
リレーション集合Ｇ′1において、前記手順のstep４により、次の転送とリレーションが選ばれる。
Ｒ4(a) → Ｒ2 …（１８）
Ｒ3(b)が削除され、Ｇ′1で得られた結果Ｒ′2とＲ4(c)とＲ1をＧ2に付加すると、リレーション集合Ｇ′2は次の通りとなる。
Ｇ′2＝｛Ｒ′2(a,b)，Ｒ4(c)，Ｒ1，Ｒ3，Ｒ4｝
【００３９】前記手順のstep４にしたがって、次の転送スケジュールが選ばれる。
Ｒ′2(a,b) → Ｒ3(a,b) → Ｒ4(a,b,c) → …（１９）
前記手順のstep５では、関係Ｒ′4(b)をＲ1に転送し、準結合をしてから結果の求めるノードに転送する。
Ｒ′4(b) → Ｒ1 → …（２０）
前記（１８）,（１９）,（２０）から、最終転送スケジュールは次のようになる。
転送スケジュール：Ｒ4(a) → Ｒ2(a,b) → Ｒ3(a,b) → Ｒ4(a,b,c) →Ｒ′4(b) → Ｒ1 →そのコストは、次の式によって計算できる。
【００４０】
【数３】
【００４１】次に、複数属性を持つリレーションの選択度について説明する。ここでは、複数属性による準結合を行ったときの選択度について述べる。リレーションＵ(a,b,…)をリレーションＲ(a,b)により準結合を行う。リレーションＲ(a,b)を属性ａ,ｂに分けて別々に結合するのではなく、ａとｂペアを送って準結合するものとする。このとき、Ｒ(a,b)のタプルはＤa×ＤbからランダムにｔR個が選ばれたと考えると、リレーションＲ(a,b)の選択度ｐRは次の式となる。
ｐR ＝ ｔR／(Ｄa×Ｄb) …（２１）
Ｒ(a,b)のタプルをこのように選んだとすると、Ｒ(a,b)のａまたはｂの単一属性のタプル数の期待値が求められる。これを使って、特別の場合の近似式をｔaについてのみ与えると、ｔaの期待値は次のようになる。
【００４２】
【数４】
【００４３】ｔbについても同様である。これから準結合に用いるリレーションＲ(a,b)に関して、そのタプル数ｔの他、単一属性のタプル数ｔa，ｔbが与えられている場合を考える。このとき、ｔ個のタプルはランダムに選ばれるが、ｔaとｔbが与えられているため、前の場合のサブアンサンブルを考える必要があり、その選択度は前記（２１）と一致しない恐れがある。準結合を受けるリレーションＵ(a,b)のあるタプルχを考える。χの属性ａの値，ｂの値が、ａ,ｂの値の中にある確率ｐa，ｐbは、 ｐa ＝ ｔa／Ｄa， ｐb ＝ ｔb／Ｄb …（２３）
である。この条件が満たされた上でχの中のａｂ対の値がＲ(a,b)の中のａｂ対と一致する条件確率ｐabは、Ｒ(a,b)のａｂ対がｔa×ｔb個の対の中からランダムに選ばれると考えて、ｐab ＝ ｔ／(ｔa×ｔb) …（２４）
となる。（２３）のｐaとｐbの積とｐabを掛けて、Ｒ(a,b)の選択度ｐは、 ｐ ＝ ｐa×ｐb×ｐab ＝ ｔ／(Ｄa×Ｄb) …（２５）
となり、（２１）と一致していることが分かる。このようにして、（２１）または（２５）の選択度の公式は、十分な合理性を持つと考えられる。以上は２属性のことを考えたが、属性数が３以上の場合も同様に拡張できる。
【００４４】まず、すべてのもっとも小さい単一属性を考慮に入れる。単一属性のリレーションはサイズが小さくて、すべての情報を持っている。射影されるもっとも小さい単一属性は、高次のリレーションから分離される確率が高いため、転送コストも低い。次に、２次以上のリレーションの準結合を考える。この段階では、複数属性の準結合また結合が導入される。そのため、リレーションの属性の間にある対応情報の損失をかなり小さい程度に押さえることができ、かつ、小さい選択度（複数属性を持つリレーションの選択度）で他のリレーションを有効にレデュースすることができる。
【００４５】すべてのリレーションを単一属性に射影してから結合するという従来の方法について検討してみる。表３に示す分散データベースを例に取ることにする。リレーションＲ2にすべての単一属性を送って結合した結果、リレーションはサイズが216であるが、同様にしてすべての単一属性とリレーションＲ3と準結合した結果、リレーションはサイズが11520である。この数値と前述したすべての転送コスト121との差は明らかに非常に大きい。これは、単一属性の準結合を用いて高次リレーションのサイズが効果的に減らされないことを示している。単一属性の限界とも言える。
【００４６】また、リレーション（複数の属性を持つ）をレデューサーに加わることについて、本発明の手順はできるだけ多くのリレーションをレデューサーに入れている。まず、低次のリレーションを入れて、高次のリレーションを低次にしてから入れるようになっている。このようにして、結合による効果を得ることができる。各ノードのリレーションの次数や複数属性の選択度などの情報を管理しなければならないのは、ネットワークのオーバーヘッドを増やすのではないかという疑問点がある。しかし、実際の分散データベースを考えると、各ノードで多くとも数キロバイトの情報量が増えるだけで、大きい問題はない。
【００４７】
【効果】以上の説明から明らかなように、本発明によると、分散データベースに合うモデルを使って、分散データベースの質問処理最適化方式を提案しているので、複数属性による準結合をレデューサーに入れる方式が非常に有効で、結合演算も取り入れることができた。これらはリレーションのｎ次の次数の概念の導入とその定量化によって実現されている。また、転送コストを小さくすることができ、質問処理に要する全回線使用時間の短縮化が図れる。
【図面の簡単な説明】
【図１】 本発明による分散データベースの質問処理最適化方式の一実施例を説明するための構成図である。
【図２】 本発明による分散データベースの質問処理最適化方式の一実施例を示すフローチャートである。
【図３】 分散データベースの質問処理を説明する図である。
【図４】 リレーションの結合と準結合を説明するための図である。
【符号の説明】
１…局所処理手段、２…集合手段、３…抽出手段、４…準結合操作手段、５…準結合手段、６…次数決定手段、６ａ…判断手段、６ｂ…分割手段、７…転送列作成手段、８…制御手段。
【特許請求の範囲】
【請求項１】 ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、複数属性で結合する質問に現れる各リレーション間で、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合をメリットのある準結合として求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合手段とを有し、リレーションを前記次数決定手段で決定された次数毎に分けてリレーション集合を作成し、この最も低い次数のリレーション集合から最も高い次数のリレーション集合に対して順次、サイズの小さいリレーションに対するメリットのある準結合を得て、転送列を得ることを特徴とする分散データベースの質問処理最適化方式。
【請求項２】 ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、各ノード内のリレーションに対して、複数属性で結合する質問を射影と選択演算及びノード内での結合として実行する局所処理手段と、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、前記局所処理した各リレーションを次数毎に分けてリレーション集合を作る集合手段と、前記集合手段で求めた最も小さい次数のリレーション集合を除くすべてのリレーション集合から、異なる単一属性に対して最もサイズの小さいリレーションを一つずつ抽出して該最も小さい次数のリレーション集合に付加する抽出手段と、前記リレーション集合内でサイズの最も小さいリレーションから最も大きいリレーションまで順次、該リレーションとこれ以外のリレーション集合内のリレーションに対して、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合を求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合操作手段と、前記準結合操作手段で加えた転送列を次に高い次数のリレーション集合に追加する操作を、最も低い次数のリレーション集合から最も高い次数のリレーション集合まで繰り返して行う制御手段とを備え、前記制御手段は、最後に、結合されていないリレーションを直接に質問を求めるノードに転送するようにしたことを特徴とする分散データベースの質問処理最適化方式。
【請求項３】 請求項２に記載の分散データベースの質問最適化方式において、前記準結合操作手段は、他のリレーションと準結合を行ってもコストを低くできないとき、そのリレーションをリレーション集合から削除し、他のリレーションと共通の属性を持たないリレーションは削除しないことを特徴とする分散データベースの質問処理最適化方式。
【請求項１】 ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、複数属性で結合する質問に現れる各リレーション間で、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合をメリットのある準結合として求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合手段とを有し、リレーションを前記次数決定手段で決定された次数毎に分けてリレーション集合を作成し、この最も低い次数のリレーション集合から最も高い次数のリレーション集合に対して順次、サイズの小さいリレーションに対するメリットのある準結合を得て、転送列を得ることを特徴とする分散データベースの質問処理最適化方式。
【請求項２】 ネットワークで接続された複数のノードに分散されたリレーショナルデータベースからなる分散データベースシステムにおいて、各ノード内のリレーションに対して、複数属性で結合する質問を射影と選択演算及びノード内での結合として実行する局所処理手段と、リレーションのタプル数が、該リレーション中のｋ個の相異なる任意の単一属性毎のタプル数の積の最小値を超える場合の最大のｋを該リレーションの次数として決定する次数決定手段と、前記局所処理した各リレーションを次数毎に分けてリレーション集合を作る集合手段と、前記集合手段で求めた最も小さい次数のリレーション集合を除くすべてのリレーション集合から、異なる単一属性に対して最もサイズの小さいリレーションを一つずつ抽出して該最も小さい次数のリレーション集合に付加する抽出手段と、前記リレーション集合内でサイズの最も小さいリレーションから最も大きいリレーションまで順次、該リレーションとこれ以外のリレーション集合内のリレーションに対して、準結合してから他のノードに転送する方が、準結合せずに直接他のノードに転送するよりコストが低いような準結合を求めて、これらのリレーション間の準結合を取った結果を転送列に加える操作を行う準結合操作手段と、前記準結合操作手段で加えた転送列を次に高い次数のリレーション集合に追加する操作を、最も低い次数のリレーション集合から最も高い次数のリレーション集合まで繰り返して行う制御手段とを備え、前記制御手段は、最後に、結合されていないリレーションを直接に質問を求めるノードに転送するようにしたことを特徴とする分散データベースの質問処理最適化方式。
【請求項３】 請求項２に記載の分散データベースの質問最適化方式において、前記準結合操作手段は、他のリレーションと準結合を行ってもコストを低くできないとき、そのリレーションをリレーション集合から削除し、他のリレーションと共通の属性を持たないリレーションは削除しないことを特徴とする分散データベースの質問処理最適化方式。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【特許番号】特許第３５２６５８５号（Ｐ３５２６５８５）
【登録日】平成１６年２月２７日（２００４．２．２７）
【発行日】平成１６年５月１７日（２００４．５．１７）
【国際特許分類】
【出願番号】特願平４−８８２０８
【出願日】平成４年３月１２日（１９９２．３．１２）
【公開番号】特開平５−２５７７６８
【公開日】平成５年１０月８日（１９９３．１０．８）
【審査請求日】平成１１年３月３日（１９９９．３．３）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【参考文献】
【文献】疋田 定幸，図解分散型データベースシステム，日本，株式会社オーム社，１９８９年 ５月２５日，第１版，Ｐ．９４〜９５
【登録日】平成１６年２月２７日（２００４．２．２７）
【発行日】平成１６年５月１７日（２００４．５．１７）
【国際特許分類】
【出願日】平成４年３月１２日（１９９２．３．１２）
【公開番号】特開平５−２５７７６８
【公開日】平成５年１０月８日（１９９３．１０．８）
【審査請求日】平成１１年３月３日（１９９９．３．３）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【参考文献】
【文献】疋田 定幸，図解分散型データベースシステム，日本，株式会社オーム社，１９８９年 ５月２５日，第１版，Ｐ．９４〜９５
[ Back to top ]