(57)【特許請求の範囲】
【請求項１】
リレーショナルデータベース表の多重結合質問のカーディナリティを算出する方法であって、コンピュータの演算処理により、
前記多重結合質問の結合グラフを表すデータをメモリに記憶する段階であって、前記結合グラフは、頂点のセット及び暗黙に定義され前記頂点に一対一で対応するエッジのセットとして定義され、前記頂点のセットは、前記多重結合質問の前記表と一対一に対応し、前記エッジのセットは、前記質問で表現された結合述語と一対一に対応しており、前記多重結合質問において表現された全ての結合述語に対して一対の頂点及び接続エッジを形成したデータをメモリに記憶する段階と、
前記メモリから前記結合グラフを表すデータを読み取り前記多重結合質問の前記カーディナリティを算出する段階であって、
前記述語が基本キー外部キーの場合、前記グラフから末尾頂点を削除することにより、縮小されたグラフを形成する段階と、
前記縮小されたグラフを表すデータのカーディナリティを前記多重結合質問の前記カーディナリティとする段階
を具備し、
前記多重結合質問の前記カーディナリティを算出する段階は、各エッジによって表される、基本キーと外部キー結合の結合選択率、各頂点によって表される前記表の前記カーディナリティ、及び各頂点によって表される前記表の個々の結合選択率を乗算する段階を含む方法。
【請求項２】
前記末尾頂点を削除する段階は、前記グラフを通るパスにおける各頂点を検査し、かつ前記頂点が末尾頂点であれば、該頂点及び当該頂点に隣接する全てのエッジを除去する段階と、
いずれかの末尾頂点が前記グラフを通るパスの間で除去されたならば、前記グラフを通る別のパスを作成する段階
を具備する請求項１に記載の方法。
【請求項３】
リレーショナルデータベース表の多重結合質問のカーディナリティをコンピュータが算出するシステムであって、前記システムは、
前記多重結合質問の結合グラフを表すデータをメモリに記憶する手段であって、前記結合グラフは、頂点のセット及び暗黙に定義され前記頂点に一対一で対応するエッジのセットとして定義され、前記頂点のセットは、前記多重結合質問の前記表と一対一に対応し、前記エッジのセットは、前記質問で表現された結合述語と一対一に対応しており、前記多重結合質問において表現された全ての結合述語を識別する手段と、
識別された各結合述語に対して前記グラフにおいて一対の頂点及び接続エッジを形成したデータをメモリに記憶する手段を有し、
前記メモリから前記結合グラフを表すデータを読み取り前記多重結合質問の前記カーディナリティを算出する手段であって、
前記述語が基本キー外部キーの場合、前記グラフから末尾頂点を削除することにより、縮小されたグラフを形成する手段と、
前記縮小されたグラフを表すデータのカーディナリティを前記多重結合質問の前記カーディナリティとする手段
として機能させ、
前記多重結合質問の前記カーディナリティを算出する手段は、各エッジによって表される、基本キーと外部キー結合の結合選択率、各頂点によって表される前記表の前記カーディナリティ、及び各頂点によって表される前記表の個々の結合選択率を乗算する段階を含む、システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、データベースシステムにおける質問処理の最適化に関し、特にリレーショナルデータベースシステムにおける結合順序付けの最適化に関する。
【０００２】
【従来の技術】
データベースは、情報の集合である。リレーショナルデータベースは、表の集合としてそのユーザによって認められるデータベースである。各表は、行及び列に項目及び項目の属性をそれぞれ配列している。各表の行はレコード（記録）またはタプルとも呼ばれ、項目に対応し、かつ各表の列はフィールド、より正確には属性の型またはフィールドの型と呼ばれ項目の属性に対応する。表Ｔのカーディナリティ（cardinality：濃度、多様性、一意な値の個数）とはデータベース分野で周知のようにレコード中の一意な値の個数を指し、｜Ｔ｜で表される。例えば性別データ（男、女）のように値の種類が少ない場合にはカーディナリティが低く、社員番号は高い。表に対する“基本キー（１次キー(primarykey) ）”は、表のレコードを独自に識別する単純または複合属性である。キーは、本来的に独自でなけらばならないし、かつ特定の時点で単に独自ではない。独自の識別子だけが表の全ての属性から構成されている複合属性であるような表を有することは可能であるが一般的ではない。二つ以上の独自の識別子を有する表は可能であるが一般的ではない。そのような場合、表はその一つが選択されかつ基本キーとして指定され、次いで残りの候補が代替キーと言われる多重候補キーを有すると言われる。基本及び代替キーは、二つの時間独立特性を満足しなければならない。まず表の二つのレコードはキーに対して同じ値を有することがない。第２に、キーが複合であれば独自性特性を破壊することなくキーのコンポーネントを削除できない。
【０００３】
“外部キー(foreign key) ”は、その値がある表の基本キーの値にマッチすることを要求される表の潜在的複合属性であり、一般的であるが、外部キーが定義される表とは必ずしも異なることを要しない。外部キーの値は、参照されたレコードまたはターゲットレコードと呼ばれる、マッチング基本キー値を含んでいるレコードへの参照を表す。外部キーを含む表は、参照しているまたは外部表と呼ばれるし、かつ対応基本キーを含む表は、参照されたまたはターゲットまたは基本表と呼ばれる。リレーショナルデータベースのデータを探索することは、質問により行われる。質問は、質問がデータベースから探索すべき情報を特定する一つ以上の述語を含む。結合質問は、二つ以上の表から情報を要求する質問である。例えば、一つの表に電話帳（テレフォンディレクトリ）情報を記憶しかつ別の表に雇用情報を記憶するデータベースでは、結合質問は、同じ市内に住みかつ働く全ての人々の名前を要求できる。
【０００４】
結合質問は、二つの表からのレコードを選択するために用いられる基準を特定する少なくとも一つの“結合述語”を含まなければならない。また、結合質問は、個々の表からのレコードを選択するために一つ以上の単一表述語を含む（例えば、その家の電話番号が８７６交換にある雇い人（従業員））。結合質問の結合選択率は、結合された表のカーディナリティの生成に対する結合の結果として生ずるマッチの数の比である。表Ｐの基本キーはＰ．Ｐｋで表される。ある基本キーに関する表Ｓの外部キーは、Ｓ．Ｆｋで表される。基本キー−外部キー結合は、Ｐｋ−Ｆｋ結合で表される。同じ基本キーに関して両方が外部キーである二つのキーの結合は、Ｆｋ−Ｆｋ結合で表される。
【０００５】
結合質問を行う繊細な方法は、いずれかのレコードが結合述語を満足するかどうかを決定するために第１の表における各レコードに対して第２の表の全てのレコードを調べることである。そのようなレコードは、マッチすると呼ばれる。次いで、データベースシステムは、互いに結合されたマッチングレコードを含んでいる中間（または最終）結果を構築できる。大きなデータベース上で多重結合質問を行うことは、時間を浪費しかつ資源が集中される。多重結合を有する結合質問をより効率的に行う一つの方法は、表が結合される順序を最適化することによってである。良好な結合順序は、成された比較の数または中間結果の大きさを低減することができ、それにより、拡張した資源及び質問全体を行うために必要な合計時間を減少させる。
【０００６】
【発明が解決しようとする課題】
しかしながら、良好な結合順序を得ることは、一般的に困難である。通常の結合順序最適化装置(optimizers)は、中間結果のカーディナリティの推定にかなり依存する。また、これらのカーディナリティの推定は、一般に困難である。通常用いられる方法は、最良でも概略でありかつある場合にはかなり不正確である。従って、最適結合順序を推定するためのより効率的かつ正確な方法が望ましい。本発明の上記従来の問題点に鑑み、最適結合順序を推定するためのより効率的かつ正確な方法を提供することをその課題とする。
【０００７】
【課題を解決するための手段】
本発明の上述した課題は、二つ以上の結合操作を有している質問に対する結合順序を選択するためのコンピュータ実装式の方法であって、全ての可能な結合順序のそれぞれに対して、各結合のカーディナリティの合計値を演算しメモリに記憶する段階と、前記メモリから合計値を読み取り、前期合計値が最小の値を有している結合順序を選択する段階を具備する方法によって達成される。
【０００８】
本発明の方法では、前記結合のカーディナリティは、結合の結果として生じるタプルの数であるように構成してもよい。
【０００９】
本発明の方法では、可能な結合順序の中から結合順序を選択する段階と、前記選択した結合順序における各コンポーネント結合のカーディナリティを取得する段階と、カーディナリティのそれぞれを合計する段階を更に具備するように構成してもよい。
【００１０】
本発明の方法では、各コンポーネント結合のカーディナリティを取得する段階は、グラフ表現方法を用いてカーディナリティを推定する段階を具備するように構成してもよい。
【００１１】
本発明の方法では、各コンポーネント結合のカーディナリティを取得する段階は、コンポーネント結合の一つのカーディナリティとして予め演算した値を検索する段階を具備するように構成してもよい。
【００１２】
【作用】
一つの形態では、本発明は、代替結合順序の相対的効率を比較するために設計されたメトリックのインプリメンテーションを介して多重結合質問において良好な結合順序を計算するためのコンピュータ実装式方法に関する。別の形態では、本発明は、Ｆｋ−Ｆｋ結合、即ち、Ｒ．ｒ及びＳ．ｓの両方が一つの基本表の一つの基本または交互(alternate) キーに関して外部キーである、実質的にＲ．ｒ＝Ｓ．ｓの形の結合述語との結合、の結合選択率を推定するためのコンピュータ実装式方法に関する。別の形態では、本発明は、Ｐｋ−Ｆｋ結合及びＦｋ−Ｆｋ結合のあらゆる組合せを含む、任意の大きな数の多重結合の結合カーディナリティを効率的に推定するためのコンピュータ実装式方法に関する。
【００１３】
本発明の利点の中で、結合質問性能の速さ及び効率が改良される。本発明の更なる利点は、以下の説明中に示され、かつ説明及び特許請求の範囲から明らかになるであろう。
【００１４】
【実施例】
本発明は、リレーショナルデータベースシステムにおける結合順序処理を最適化する方法及び装置を供給する。図１は、本発明によるカーディナリティを利用した結合最適化を取り入れたリレーショナルデータベースシステム２６を支援するために適する汎用コンピュータプラットフォーム１０を示す。プラットフォームは、（パーソナルコンピュータまたはワークステーションのような）ディジタルコンピュータ１２、ディスプレイ１４、（フロッピディスクドライブ、ハードディクスドライブ、消去可能ＣＤ−ＲＯＭドライブ、または磁気光学ディスクドライブのような）大容量記憶装置１６、キーボード１８、及びマウス２０または他の入力装置を含む。コンピュータ１２は、通常の構造のものでありかつメモリ２２、プロセッサ２４、及びメモリバス及び周辺バス（図示省略）のような、他の通常のコンポーネントを含む。また、コンピュータ１２は、コンピュータ１２が、それによって通信リンク３６上の他のコンピュータ４０にコンピュータネットワーク３８上で接続される通信ハードウェア及びソフトウェア（図示省略）も含む。好適にはメモリ２２に本発明の方法で計算されたカーディナリティの値が記憶されその後の処理により読み取られる。
【００１５】
データベースシステム２６は、データベースを管理する。データベース２８は、一つのコンピュータに集中化されるか、またはコンピュータネットワーク３８間に分配される。一般に、データベース２８は、永久的または一時的に、データベースにリンクされるコンピュータ上で実行されるデータベースシステム２６によって管理される。この説明では、データベース管理システムは、コンピュータ１２で実行されるものとして示される。先に示したように、リレーショナルデータベースシステムの設計及び実現における問題点の一つは、結合最適化、即ち、多重結合質問において表を結合するための最適順序を計算することである。表が結合される順序は、結合の結果に影響を及ぼさないが、同じ質問に対する異なる結合順序は、異なる量の時間及び他の資源を消費する。
【００１６】
表Ｒ、Ｓ、及びＴ、表Ｒ、Ｓ、及びＴが結合されるような結合質問、及び二つの可能な結合順序：（１）表Ｒ及びＳを結合し、そして結果を表Ｔと結合し、かつ（２）表Ｓ及びＴを結合し、そして結果を表Ｒと結合する、を含むリレーショナルデータベースを考える。まず結合順序（１）を考える。｜（ＲがＳを結合する）｜＝２０かつ｜（ＲがＳを結合する）Ｔを結合する｜＝６０ならば、合計質問の計算中に生成されたタプルの合計数は、８０（２０＋６０）である。次に、結合順序（２）を考える。｜（ＳがＴを結合する）｜＝５００かつ｜（ＳがＴを結合する）Ｒを結合する｜＝６０ならば、合計質問の計算中に生成されたレコードの合計数は、５６０（５００＋６０）である。結合順序の選択は、特に大きな表を含む多重結合で、重要である。
【００１７】
新しいメトリック、Ｓｉｇｍａ（シグマ）は、多重結合質問における可能な結合順序の中から結合順序を選ぶために用いられる。Ｓｉｇｍａは、それが結合順序で行われるときの各結合からの結果として生じるべく推定されたタプルの数の和として定義される。Ｓｉｇｍａメトリックを用いて、全ての結合順序の中で最も小さいＳｉｇｍａを有している結合順序が最適として選択されかつ結合を行うために用いられる。競合する結合順序がある場合には、例えば、コスト推定計算や、ある他の経験則（heuristic ）を用いて結合順序を選択する。上記の例では、結合順序（１）に対するＳｉｇｍａは、８０であり、結合順序（２）に対するＳｉｇｍａは、５６０であって、順序（２）に対して順序（１）が好ましいということを示している。
【００１８】
図２は、表Ｔ＝｛Ｔ１、Ｔ２、Ｔ３、．．．、Ｔｎ｝を含む結合質問に対して可能な結合順序の中から結合順序を選ぶためにＳｉｇｍａメトリックを用いるコンピュータ実装式処理１１０を示す。まず、可能な結合順序の中から結合順序が選択される（ステップ１２０）。次に、結合順序における各コンポーネント結合のカーディナリティを得る（ステップ１３０）。これは、予め計算された値を検索することにより、または他の方法により、以下に説明するグラフ表現方法を用いてカーディナリティを推定することによって行うことができる。Ｓｉｇｍａの計算には特定のカーディナリティの計算方法に限定されない。Ｓｉｇｍａの値は、これらのカーディナリティ推定のそれぞれを合計することによって計算される。このＳｉｇｍａ値がそれまでに発生したＳｉｇｍａの最小値であるならば、Ｓｉｇｍａの値及び対応結合順序の両方が記憶される（ステップ１５０）。結合順序が検査されために残っているならば、処理は、次の可能な結合順序に対して繰り返される（ステップ１６０）。さもなければ、結合質問を行うためにＳｉｇｍａの最小値を有する結合順序が用いられる（ステップ１７０）。
【００１９】
多重−結合質問における結合カーディナリティは、質問のグラフ表現を用いて推定することができる。しかしながら、結合グラフを用いる方法を説明する前に、個々の結合カーディナリティ及び結合選択率を推定することについて説明する。Ｐｋ−Ｆｋ結合Ｒ．Ｐｋ＝Ｓ．Ｆｋを考える。各外部キー値が基本表の一つのレコードと正確にマッチするので、そのような結合のカーディナリティは、外部の表（この例では、表Ｓ）のカーディナリティに等しい。例えば、大学教授の表Ｐ及び教授が教えているクラス（授業）の表Ｓを含むデータベースを考える。Ｐ．ｐｒｏｆＩＤは、各教授を独自に識別する基本キーである。Ｓ．ｔｅａｃｈｅｒは、クラスを教えている一人の教授を識別する属性である。従って、Ｓ．ｔｅａｃｈｅｒは、Ｐに対する外部キーである。Ｓ．Ｆｋ＝Ｐ．Ｐｋの形である、結合述語Ｓ．ｔｅａｃｈｅｒ＝Ｐ．ｐｒｏｆＩＤを有する結合質問は、各クラスが確実に一人の教授によって教えられるので、｜Ｓ｜に等しいカーディナリティを有する。
【００２０】
結合質問の結合選択率は、結合した表のカーディナリティの積に対する結合（即ち、結合カーディナリティ）の結果として生ずるマッチの数の比率である。それゆえに、Ｐｋ−Ｆｋ結合の結合選択率は、Ｒが基本表であるような、以下の式によって与えられる：
Ｐｋ−Ｆｋ結合の結合選択率  ＝  結合カーディナリティ／（｜Ｒ｜×｜Ｓ｜）
＝  ｜Ｓ｜／（｜Ｒ｜×｜Ｓ｜）
＝  １／｜Ｒ｜
Ｆｋ−Ｆｋ結合のカーディナリティ及び選択率を推定するために、Ｆｋ−Ｆｋ結合を含んでいる以下のＳＱＬ質問を考える：
ＳＥＬＥＣＴ＊ＦＲＯＭ Ｓ，Ｔ ［例１］
ＷＨＥＲＥ Ｓ．Ｆｋ＝Ｔ．Ｆｋ
この例では、Ｒ．Ｐｋは、Ｓ．Ｆｋ及びＴ．Ｆｋの両方に対して基礎を成す基本キーである。そのような質問で用いるキーの値がそれらの表において実質的に均等に分配され、かつ基本キー値が外部キーの中で実質的に全て見出されるならば、各別個の基本キー値に対して、｜Ｓ｜／｜Ｒ｜は、Ｓ．Ｆｋにおける値の発生数の良好な推定であり、｜Ｔ｜／｜Ｒ｜は、Ｔ．Ｆｋにおける値の発生数の良好な推定である。
【００２１】
従って、
Ｆｋ−Ｆｋ結合の結合カーディナリティ  ＝  （|Ｓ|／|Ｒ|）×（|Ｔ|／|Ｒ|）×|Ｒ|
＝  （|Ｓ|×|Ｔ|）／|Ｒ|
としてＳ．Ｆｋ＝Ｔ．Ｆｋの結合カーディナリティを推定できる。結合選択率の定義及び先に示した仮定から、
Ｆｋ−Ｆｋ結合の結合カーディナリティ  ＝  ((|Ｓ|×|Ｔ|)／|Ｒ|)×(１／(|Ｓ|×|Ｔ|))
＝  １／|Ｒ|
として、Ｆｋ−Ｆｋ結合の結合選択率を推定できる。Ｐｋ−Ｐｋ結合及びＦｋ−Ｆｋ結合の両方において、推定した結合選択率は、｜Ｒ｜が基本キー表のカーディナリティであるような、１／｜Ｒ｜に等しいということに注目する。
【００２２】
図３に示すように、コンピュータ実装式処理２００は、Ｖが質問における表と一対一で対応する頂点のセットであり、かつＥが質問における結合述語（表現及び暗黙に定義された）と一対一で対応するエッジのセットであるような、結合グラフＧ＝（Ｖ，Ｅ）として多重結合質問を表現するために用いることができる。処理を理解するために、以下の結合質問を考える：
ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例２］
ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ
ＡＮＤ Ｒ．Ｐｋ＝Ｔ．Ｆｋ
この結合を表現している結合グラフを形成するために、第１の段階は、全ての表現結合述語を収集することである（ステップ２２０）。例２では、二つのそのような述語が存在する：Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．Ｆｋ。次の段階は、暗黙に定義された全ての結合述語を収集することである（ステップ２３０）。例２では、Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．Ｆｋは、Ｓ．Ｆｋ＝Ｔ．Ｆｋを暗黙に定義する。
【００２３】
次に、一対の頂点及びそれらを接続するエッジは、収集された各述語に対するグラフに追加される（ステップ２４０−２９０）。述語がＰｋ−Ｆｋであるならば、対応エッジは、基本表から外部表に向かって指向される（ステップ２７０）。述語がＦｋ−Ｆｋまたは他の型の結合であれば、対応エッジは、指向されない（ステップ２８０）。例２の結合質問に対応する結合グラフを図４に示す。結合している列が独立であるような結合質問のカーディナリティは、（１）コンポーネント結合の選択率の積、（２）結合における個別の表のカーディナリティの積、及び（３）結合における表での個別の選択の選択率の積を積算することによって推定することができる。結合している列の独立は、全ての通常の最適化装置(optimizers)に行われる想定である。Ｐ．Ｐｋ＝Ｓ．Ｆｋ及びＳ．Ｆｋ＝Ｔ．Ｆｋのコンポーネント結合の選択率は、上述した方法を用いて推定される。データベースシステム質問最適化装置は、それが他の種類の結合の選択率を計算しまたは推定するために利用可能であるあらゆる他の方法を用いる。
【００２４】
このフォーミュラを結合グラフ４００に適用することにより（図４）、質問カーディナリティは、
(１/|Ｒ|)×(１/|Ｒ|)×(１/|Ｒ|)×|Ｒ|×|Ｓ|×|Ｔ|  ＝  (|Ｓ|×|Ｔ|)/(|Ｒ|×|Ｒ|)
であるべく計算される。通常の結合順序最適化装置は、この結果をもたらすが、更に良い推定が見出される、具体的には：
（｜Ｓ｜×｜Ｔ｜）／｜Ｒ｜  ＝  Ｎ
であるべく計算される。これは、表Ｓ及びＴがまず結合されたならばＮタプルが結果として生ずるということに注目することによって確認することができる。（Ｓ，Ｔ）の全ての行においてＳ．Ｆｋ＝Ｔ．Ｆｋなので、全てのそのようなタプルは、Ｒの一つのタプルと確実に結合し、それゆえに、追加のタプルを結果として生じない。
【００２５】
図５に示すように、結合グラフ表現を用いている多重結合のカーディナリティを推定するためのコンピュータ実装式処理５００は、このインサイト（洞察力）を引き出しかつ推定手順におけるグラフを変更することによって正しい結果に到達する。まず、結合質問のグラフ表現が、例えば、手順２００を用いることによって形成される（図３）。次に、全ての末尾頂点は、グラフから除去される（ステップ５３０−５７０）。末尾頂点は、グラフの他の頂点がポイントしない頂点である。例えば、図４では、頂点Ｒ４１０は、末尾頂点である。末尾頂点を除去するために、手順５００は、グラフの各頂点を検査する（ステップ５４０）。頂点が末尾頂点であれば、それに隣接するそれ及び全てのエッジは、削除される（ステップ５５０）。このパスがグラフを通る間中に末尾頂点が削除されるならば、末尾頂点を除去することは、別の末尾頂点を生成できるので、別のパスが次いでなされる（ステップ５７０）。
【００２６】
一度全ての末尾頂点が除去されたならば、オリジナル結合の結合カーディナリティは、（１）各エッジによって表現される結合の選択率、（２）各頂点によって表現される表のカーディナリティ、及び（３）各頂点によって表現される表の個々の選択率を乗算することによって、残っているグラフを用いて除去することができる（ステップ５８０）。上記したように、この推定は、結合している列が独立していることを想定する。
【００２７】
末尾頂点を除去することの効果は、以下の質問の処理において説明される：
ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例３］
ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ
ＡＮＤ Ｓ．Ｐｋ＝Ｔ．Ｆｋ
【００２８】
結果のカーディナリティは、｜Ｔ｜である。ＲとＳを結合することは、Ｓの全ての行をマッチさせ、そしてＳとＴを結合することは、Ｔの全ての行をマッチし、結果のカーディナリティは、｜Ｔ｜である。同じ結果は、図５の方法を用いてグラフ表現を評価することによって得られる。図６の結合グラフ６００は、例３の質問を表す。エッジ６２０、６４０は、対応結合述語によって印が付けられる。頂点Ｒ６１０は、末尾頂点である。頂点Ｒ６１０及びそれに隣接するエッジ６２０が取り除かれるとき、残ったものは、頂点Ｓ６３０と頂点Ｔ６５０を接続している単一エッジ６４０である。頂点Ｓ６３０は、いま末尾頂点であり、そこで頂点Ｓ６３０及びそれに隣接するエッジ６４０が取り除かれて、頂点Ｔ６５０だけを残す。結合結果のカーディナリティは、従って｜Ｔ｜である。本発明は、実施例により説明された。しかしながら、本発明は、表示しかつ説明した実施例に限定されない。例えば、本発明は、ソフトウェアインプリメンテーションにより記述される。しかしながら、本発明は、ソフトウェアまたはハードウェアまたはファームウェア、或いは３つのの組合せでインプリメントされる。本発明の範疇は、特許請求の範囲によって定義される。
【００２９】
【発明の効果】
本発明の方法、システムにより、効率的かつ正確に最適結合順序を推定することができる。
【図面の簡単な説明】
【図１】本発明による汎用コンピュータプラットフォームプログラマブルでありリレーショナルデータベースを含むブロック図である。
【図２】リレーショナルデータベースシステムにおける結合質問の表の所与のセットに対する最適結合順序を計算するためのコンピュータ実装型方法のブロック図である。
【図３】多重結合質問のグラフ表現を生成するためのコンピュータ実装型方法のブロック図である。
【図４】結合グラフの図である。
【図５】結合質問のグラフ表現を用いて多重結合質問の結合カーディナリティを推定するためのコンピュータ実装型方法のブロック図である。
【図６】結合グラフの図である。
【符号の説明】
１０ 汎用コンピュータプラットフォーム
１２ ディジタルコンピュータ
１４ ディスプレイ
１６ 大容量記憶装置
１８ キーボード
２０ マウス
２２ メモリ
２４ プロセッサ
２６ リレーショナルデータベースシステム
２８ データベース
３６ 通信リンク
３８ コンピュータネットワーク
４０ コンピュータ
【図１】
0004397978.tif 000002
【図２】
0004397978.tif 000003
【図３】
0004397978.tif 000004
【図４】
0004397978.tif 000005
【図５】
0004397978.tif 000006
【図６】
0004397978.tif 000007