JPH117454A - 濃度を利用した結合順序付け方法 - Google Patents
濃度を利用した結合順序付け方法Info
- Publication number
- JPH117454A JPH117454A JP10119252A JP11925298A JPH117454A JP H117454 A JPH117454 A JP H117454A JP 10119252 A JP10119252 A JP 10119252A JP 11925298 A JP11925298 A JP 11925298A JP H117454 A JPH117454 A JP H117454A
- Authority
- JP
- Japan
- Prior art keywords
- join
- concentration
- graph
- key
- vertex
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2453—Query optimisation
- G06F16/24534—Query rewriting; Transformation
- G06F16/24542—Plan optimisation
- G06F16/24544—Join order optimisation
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99932—Access augmentation or optimizing
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Operations Research (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【課題】 最適結合順序を推定するための効率的かつ正
確な方法を提供する。 【解決手段】 結合濃度に基づいて結合質問の処理を最
適化する方法及び装置である。実施例は、リレーショナ
ルデータベース管理システムにおける質問最適化装置に
おける方法をインプリメントする。多重結合質問に対す
る良好な結合順序は、全体として候補結合順序の相対的
な利点を比較するメトリックで見出される。実施例は、
参加している表の両方が一つの基本表の基本または固有
キーに関して外部キーであるような、外部キー−外部キ
ー結合の結合選択性を推定する。質問のグラフ表現は、
基本キー−外部キー結合及び外部キー−外部キー結合の
あらゆる組合せを含む、任意の非常に多数のフィルタ及
び結合の結合濃度を推定するために処理される。
確な方法を提供する。 【解決手段】 結合濃度に基づいて結合質問の処理を最
適化する方法及び装置である。実施例は、リレーショナ
ルデータベース管理システムにおける質問最適化装置に
おける方法をインプリメントする。多重結合質問に対す
る良好な結合順序は、全体として候補結合順序の相対的
な利点を比較するメトリックで見出される。実施例は、
参加している表の両方が一つの基本表の基本または固有
キーに関して外部キーであるような、外部キー−外部キ
ー結合の結合選択性を推定する。質問のグラフ表現は、
基本キー−外部キー結合及び外部キー−外部キー結合の
あらゆる組合せを含む、任意の非常に多数のフィルタ及
び結合の結合濃度を推定するために処理される。
Description
【０００１】
【産業上の利用分野】本発明は、データベースシステム
における質問処理の最適化に関し、特にリレーショナル
データベースシステムにおける結合順序付けの最適化に
関する。
における質問処理の最適化に関し、特にリレーショナル
データベースシステムにおける結合順序付けの最適化に
関する。
【０００２】
【従来の技術】データベースは、情報の集合である。リ
レーショナルデータベースは、表の集合としてそのユー
ザによって認められるデータベースである。各表は、行
及び列に項目及び項目の属性をそれぞれ配列している。
各表の行は、項目（記録またはタプルとも呼ばれる）に
対応し、かつ各表の列は、項目の属性（フィールドまた
はより正確には、属性の型またはフィールドの型と呼ば
れる）に対応する。表Ｔの濃度(cardinality) は、それ
が含む記録の数であり、｜Ｔ｜で表される。表に対する
“基本キー（１次キー(primary key) ）”は、表の記録
を独自に識別する単純または複合属性である。キーは、
本来的に独自でなけらばならないし、かつ特定の時点で
単に独自ではない。ことは、独自の識別子だけが表の全
ての属性から構成されている複合属性であるような表を
有することは、可能であるが、一般的ではない。二つ以
上の独自の識別子を有する表は、可能であるが、一般的
ではない。そのような場合、表は、その一つが選択され
かつ基本キーとして指定され；次いで、残りの候補が代
替キーと言われうる、多重候補キーを有すると言われる
であろう。基本及び代替キーは、二つの時間独立特性を
満足しなければならない。まず、表の二つの記録は、キ
ーに対して同じ値を有することがない。第２に、キーが
複合であれば、独自性特性を破壊することなくキーのコ
ンポーネントを削除できない。
レーショナルデータベースは、表の集合としてそのユー
ザによって認められるデータベースである。各表は、行
及び列に項目及び項目の属性をそれぞれ配列している。
各表の行は、項目（記録またはタプルとも呼ばれる）に
対応し、かつ各表の列は、項目の属性（フィールドまた
はより正確には、属性の型またはフィールドの型と呼ば
れる）に対応する。表Ｔの濃度(cardinality) は、それ
が含む記録の数であり、｜Ｔ｜で表される。表に対する
“基本キー（１次キー(primary key) ）”は、表の記録
を独自に識別する単純または複合属性である。キーは、
本来的に独自でなけらばならないし、かつ特定の時点で
単に独自ではない。ことは、独自の識別子だけが表の全
ての属性から構成されている複合属性であるような表を
有することは、可能であるが、一般的ではない。二つ以
上の独自の識別子を有する表は、可能であるが、一般的
ではない。そのような場合、表は、その一つが選択され
かつ基本キーとして指定され；次いで、残りの候補が代
替キーと言われうる、多重候補キーを有すると言われる
であろう。基本及び代替キーは、二つの時間独立特性を
満足しなければならない。まず、表の二つの記録は、キ
ーに対して同じ値を有することがない。第２に、キーが
複合であれば、独自性特性を破壊することなくキーのコ
ンポーネントを削除できない。
【０００３】“外部キー(foreign key) ”は、その値が
ある表の基本キーの値にマッチすることを要求される表
の潜在的複合属性であり、一般的であるが、外部キーが
定義される表とは必ずしも異なることを要しない。外部
キーの値は、参照された記録またはターゲット記録と呼
ばれうる、マッチング基本キー値を含んでいる記録への
参照を表す。外部キーを含む表は、参照しているまたは
外部表と呼ばれうるしかつ対応基本キーを含む表は、参
照されたまたはターゲットまたは基本表と呼ばれうる。
リレーショナルデータベースのデータを探索すること
は、質問により行われる。質問は、質問がデータベース
から探索すべき情報を特定する一つ以上の述語を含む。
結合質問は、二つ以上の表から情報を要求する質問であ
る。例えば、一つの表に電話帳（テレフォンディレクト
リ）情報を記憶しかつ別の表に雇用情報を記憶するデー
タベースでは、結合質問は、同じ市内に住みかつ働く全
ての人々の名前を要求しうる。
ある表の基本キーの値にマッチすることを要求される表
の潜在的複合属性であり、一般的であるが、外部キーが
定義される表とは必ずしも異なることを要しない。外部
キーの値は、参照された記録またはターゲット記録と呼
ばれうる、マッチング基本キー値を含んでいる記録への
参照を表す。外部キーを含む表は、参照しているまたは
外部表と呼ばれうるしかつ対応基本キーを含む表は、参
照されたまたはターゲットまたは基本表と呼ばれうる。
リレーショナルデータベースのデータを探索すること
は、質問により行われる。質問は、質問がデータベース
から探索すべき情報を特定する一つ以上の述語を含む。
結合質問は、二つ以上の表から情報を要求する質問であ
る。例えば、一つの表に電話帳（テレフォンディレクト
リ）情報を記憶しかつ別の表に雇用情報を記憶するデー
タベースでは、結合質問は、同じ市内に住みかつ働く全
ての人々の名前を要求しうる。
【０００４】結合質問は、二つの表からの記録を選択す
るために用いられる基準を特定する少なくとも一つの
“結合述語”を含まなければならない。また、結合質問
は、個々の表からの記録を選択するために一つ以上の単
一表述語を含みうる（例えば、その家の電話番号が８７
６交換にある雇い人（従業員））。結合質問の結合選択
率は、結合された表の濃度の生成に対する結合の結果と
して生ずるマッチの数の比である。表Ｐの基本キーは
Ｐ．Ｐｋで表される。ある基本キーに関する表Ｓの外部
キーは、Ｓ．Ｆｋで表される。基本キー−外部キー結合
は、Ｐｋ−Ｆｋ結合で表される。同じ基本キーに関して
両方が外部キーである二つのキーの結合は、Ｆｋ−Ｆｋ
結合で表される。
るために用いられる基準を特定する少なくとも一つの
“結合述語”を含まなければならない。また、結合質問
は、個々の表からの記録を選択するために一つ以上の単
一表述語を含みうる（例えば、その家の電話番号が８７
６交換にある雇い人（従業員））。結合質問の結合選択
率は、結合された表の濃度の生成に対する結合の結果と
して生ずるマッチの数の比である。表Ｐの基本キーは
Ｐ．Ｐｋで表される。ある基本キーに関する表Ｓの外部
キーは、Ｓ．Ｆｋで表される。基本キー−外部キー結合
は、Ｐｋ−Ｆｋ結合で表される。同じ基本キーに関して
両方が外部キーである二つのキーの結合は、Ｆｋ−Ｆｋ
結合で表される。
【０００５】結合質問を行う繊細な方法は、いずれかの
記録が結合述語を満足するかどうかを決定するために第
１の表における各記録に対して第２の表の全ての記録を
調べることである。そのような記録は、マッチすると呼
ばれる。次いで、データベースシステムは、互いに結合
されたマッチング記録を含んでいる中間（または最終）
結果を構築しうる。大きなデータベース上で多重結合質
問を行うことは、時間を浪費しかつ資源が集中される。
多重結合を有する結合質問をより効率的に行う一つの方
法は、表が結合される順序を最適化することによってで
ある。良好な結合順序は、成された比較の数または中間
結果の大きさを低減することができ、それにより、拡張
した資源及び質問全体を行うために必要な合計時間を減
少させる。
記録が結合述語を満足するかどうかを決定するために第
１の表における各記録に対して第２の表の全ての記録を
調べることである。そのような記録は、マッチすると呼
ばれる。次いで、データベースシステムは、互いに結合
されたマッチング記録を含んでいる中間（または最終）
結果を構築しうる。大きなデータベース上で多重結合質
問を行うことは、時間を浪費しかつ資源が集中される。
多重結合を有する結合質問をより効率的に行う一つの方
法は、表が結合される順序を最適化することによってで
ある。良好な結合順序は、成された比較の数または中間
結果の大きさを低減することができ、それにより、拡張
した資源及び質問全体を行うために必要な合計時間を減
少させる。
【０００６】
【発明が解決しようとする課題】しかしながら、良好な
結合順序を得ることは、一般的に困難である。通常の結
合順序最適化装置(optimizers)は、中間結果の濃度の推
定にかなり依存する。また、これらの濃度の推定は、一
般に困難である。通常用いられる方法は、最良でも概略
でありかつある場合にはかなり不正確でありうる。従っ
て、最適結合順序を推定するためのより効率的かつ正確
な方法が望ましい。本発明の上記従来の問題点に鑑み、
最適結合順序を推定するためのより効率的かつ正確な方
法を提供することをその課題とする。
結合順序を得ることは、一般的に困難である。通常の結
合順序最適化装置(optimizers)は、中間結果の濃度の推
定にかなり依存する。また、これらの濃度の推定は、一
般に困難である。通常用いられる方法は、最良でも概略
でありかつある場合にはかなり不正確でありうる。従っ
て、最適結合順序を推定するためのより効率的かつ正確
な方法が望ましい。本発明の上記従来の問題点に鑑み、
最適結合順序を推定するためのより効率的かつ正確な方
法を提供することをその課題とする。
【０００７】
【課題を解決するための手段】本発明の上述した課題
は、二つ以上の結合操作を有している質問に対する結合
順序を選択するためのコンピュータ実装式の方法であっ
て：全ての可能な結合順序を考慮し；可能な結合順序の
それぞれに対してＳｉｇｍａメトリックの値を演算し；
かつ Ｓｉｇｍａメトリックの最小演算値を有している
結合順序を選択する段階を具備する方法によって達成さ
れる。本発明の方法では、結合順序に対するＳｉｇｍａ
の値は、それが結合順序で行われるときの各結合の濃度
の推定の結合順序における全ての結合にわたる合計であ
り、結合の濃度は、結合の結果として生ずるタプルの数
であるように構成してもよい。
は、二つ以上の結合操作を有している質問に対する結合
順序を選択するためのコンピュータ実装式の方法であっ
て：全ての可能な結合順序を考慮し；可能な結合順序の
それぞれに対してＳｉｇｍａメトリックの値を演算し；
かつ Ｓｉｇｍａメトリックの最小演算値を有している
結合順序を選択する段階を具備する方法によって達成さ
れる。本発明の方法では、結合順序に対するＳｉｇｍａ
の値は、それが結合順序で行われるときの各結合の濃度
の推定の結合順序における全ての結合にわたる合計であ
り、結合の濃度は、結合の結果として生ずるタプルの数
であるように構成してもよい。
【０００８】本発明の方法では、可能な結合順序の中か
ら結合順序を選択し；選択した結合順序における各コン
ポーネント結合の濃度の推定を取得し；濃度推定のそれ
ぞれを合計することによってＳｉｇｍａに対する値を計
算する段階を更に具備するように構成してもよい。本発
明の方法では、各コンポーネント結合の濃度を取得する
段階は、グラフ表現方法を用いて濃度を推定する段階を
具備するように構成してもよい。本発明の方法では、各
コンポーネント結合の濃度を取得する段階は、コンポー
ネント結合の一つの濃度として予め演算した値を検索す
る段階を具備するように構成してもよい。本発明の方法
では、Ｓ．ｆｋとＴ．ｆｋの両方が一つの基本表Ｒの一
つの基本または代替キーに関して外部キーである、結合
述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであるような結合で
ある、外部キー−外部キー結合としてコンポーネント結
合を識別し；かつ、ここで｜Ｒ｜が表Ｒの濃度を表す、 （｜Ｓ｜・｜Ｔ｜）／｜Ｒ｜ として外部キー−外部キー結合の濃度を推定する段階を
更に具備するように構成してもよい。
ら結合順序を選択し；選択した結合順序における各コン
ポーネント結合の濃度の推定を取得し；濃度推定のそれ
ぞれを合計することによってＳｉｇｍａに対する値を計
算する段階を更に具備するように構成してもよい。本発
明の方法では、各コンポーネント結合の濃度を取得する
段階は、グラフ表現方法を用いて濃度を推定する段階を
具備するように構成してもよい。本発明の方法では、各
コンポーネント結合の濃度を取得する段階は、コンポー
ネント結合の一つの濃度として予め演算した値を検索す
る段階を具備するように構成してもよい。本発明の方法
では、Ｓ．ｆｋとＴ．ｆｋの両方が一つの基本表Ｒの一
つの基本または代替キーに関して外部キーである、結合
述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであるような結合で
ある、外部キー−外部キー結合としてコンポーネント結
合を識別し；かつ、ここで｜Ｒ｜が表Ｒの濃度を表す、 （｜Ｓ｜・｜Ｔ｜）／｜Ｒ｜ として外部キー−外部キー結合の濃度を推定する段階を
更に具備するように構成してもよい。
【０００９】本発明の方法では、Ｓ．ｆｋとＴ．ｆｋの
両方が一つの基本表Ｒの一つの基本または代替キーに関
して外部キーである、結合述語が実質的にＳ．ｆｋ＝
Ｔ．ｆｋであるような結合である、外部キー−外部キー
結合としてコンポーネント結合を識別し；かつ、ここで
｜Ｒ｜が表Ｒの濃度を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率を推定する
段階を更に具備するように構成してもよい。また、本発
明の上述した課題は、Ｓ．ｆｋとＴ．ｆｋの両方が一つ
の基本表Ｒの一つの基本または代替キーに関して外部キ
ーである、結合述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであ
るような結合である、外部キー−外部キー結合の結合選
択率を推定する方法であって：｜Ｒ｜が表Ｒの濃度を表
す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率の推定を計
算する段階を具備する方法によって達成される。
両方が一つの基本表Ｒの一つの基本または代替キーに関
して外部キーである、結合述語が実質的にＳ．ｆｋ＝
Ｔ．ｆｋであるような結合である、外部キー−外部キー
結合としてコンポーネント結合を識別し；かつ、ここで
｜Ｒ｜が表Ｒの濃度を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率を推定する
段階を更に具備するように構成してもよい。また、本発
明の上述した課題は、Ｓ．ｆｋとＴ．ｆｋの両方が一つ
の基本表Ｒの一つの基本または代替キーに関して外部キ
ーである、結合述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであ
るような結合である、外部キー−外部キー結合の結合選
択率を推定する方法であって：｜Ｒ｜が表Ｒの濃度を表
す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率の推定を計
算する段階を具備する方法によって達成される。
【００１０】更に、本発明の上述した課題は、二つ以上
の結合操作を有する質問に対する結合順序を選択するシ
ステムであって：全ての可能な結合順序のそれぞれに対
してＳｉｇｍａメトリックの値を演算する手段；及びＳ
ｉｇｍａメトリックの最小の演算された値を有する結合
順序を選択する手段を備えているシステムによって達成
される。本発明のシステムでは、結合順序に対するＳｉ
ｇｍａの値は、それが結合順序で行われるときの各結合
の濃度の推定の結合順序における全ての結合にわたる合
計であり、結合の濃度は、結合の結果として生ずるタル
プの数であるように構成してもよい。本発明のシステム
では、可能な結合順序の中から結合順序を選択する手
段；選択した結合順序における各コンポーネント結合の
濃度の推定を取得する手段；及び濃度推定のそれぞれを
合計することによってＳｉｇｍａに対する値を計算する
手段を更に具備するように構成してもよい。
の結合操作を有する質問に対する結合順序を選択するシ
ステムであって：全ての可能な結合順序のそれぞれに対
してＳｉｇｍａメトリックの値を演算する手段；及びＳ
ｉｇｍａメトリックの最小の演算された値を有する結合
順序を選択する手段を備えているシステムによって達成
される。本発明のシステムでは、結合順序に対するＳｉ
ｇｍａの値は、それが結合順序で行われるときの各結合
の濃度の推定の結合順序における全ての結合にわたる合
計であり、結合の濃度は、結合の結果として生ずるタル
プの数であるように構成してもよい。本発明のシステム
では、可能な結合順序の中から結合順序を選択する手
段；選択した結合順序における各コンポーネント結合の
濃度の推定を取得する手段；及び濃度推定のそれぞれを
合計することによってＳｉｇｍａに対する値を計算する
手段を更に具備するように構成してもよい。
【００１１】本発明のシステムでは、各コンポーネント
結合の濃度を取得する手段は、グラフ表現方法を用いて
濃度を推定する手段を備えているように構成してもよ
い。本発明のシステムでは、各コンポーネント結合の濃
度を取得する手段は、コンポーネント結合の一つの濃度
として予め演算された値を検索する手段を備えているよ
うに構成してもよい。本発明のシステムでは、結合述語
が、Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一
つの基本または代替キーに関して外部キーである実質的
にＳ．ｆｋ＝Ｔ．ｆｋであるような結合である、外部キ
ー−外部キー結合としてコンポーネント結合を識別する
手段；及び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の濃度を推定する手段を
更に備えているように構成してもよい。
結合の濃度を取得する手段は、グラフ表現方法を用いて
濃度を推定する手段を備えているように構成してもよ
い。本発明のシステムでは、各コンポーネント結合の濃
度を取得する手段は、コンポーネント結合の一つの濃度
として予め演算された値を検索する手段を備えているよ
うに構成してもよい。本発明のシステムでは、結合述語
が、Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一
つの基本または代替キーに関して外部キーである実質的
にＳ．ｆｋ＝Ｔ．ｆｋであるような結合である、外部キ
ー−外部キー結合としてコンポーネント結合を識別する
手段；及び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の濃度を推定する手段を
更に備えているように構成してもよい。
【００１２】本発明のシステムでは、結合述語が、Ｓ．
ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一つの基本
または代替キーに関して外部キーである実質的にＳ．ｆ
ｋ＝Ｔ．ｆｋであるような結合である、外部キー−外部
キー結合としてコンポーネント結合を識別する手段；及
び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の選択率を推定する手段
を更に備えているように構成してもよい。
ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一つの基本
または代替キーに関して外部キーである実質的にＳ．ｆ
ｋ＝Ｔ．ｆｋであるような結合である、外部キー−外部
キー結合としてコンポーネント結合を識別する手段；及
び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の選択率を推定する手段
を更に備えているように構成してもよい。
【００１３】本発明の上述した課題は、結合述語が、
Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一つの
基本または代替キーに関して外部キーである実質的に
Ｓ．ｆｋ＝Ｔ．ｆｋであるような結合である、外部キー
−外部キー結合の結合選択率を推定するシステムであっ
て：Ｆｋ−Ｆｋ結合として述語を識別する手段；及び｜
Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の結合選択率の推定を計
算する手段を備えているシステムによって達成される。
Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの基本表Ｒの一つの
基本または代替キーに関して外部キーである実質的に
Ｓ．ｆｋ＝Ｔ．ｆｋであるような結合である、外部キー
−外部キー結合の結合選択率を推定するシステムであっ
て：Ｆｋ−Ｆｋ結合として述語を識別する手段；及び｜
Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の結合選択率の推定を計
算する手段を備えているシステムによって達成される。
【００１４】また、本発明の上述した課題は、リレーシ
ョナルデータベース表の多重結合質問の濃度を推定する
コンピュータ実装式の方法であって：多重結合質問の結
合グラフを表すデータを計算し、結合グラフは、頂点の
セット及びエッジのセットを有し、頂点のセットは、多
重結合質問の表と一対一に対応し、エッジのセットは、
質問で表現されかつ暗示された結合述語と一対一に対応
し；かつ多重結合質問の濃度を推定するために結合グラ
フを表すデータを用いる段階を具備する方法によって達
成される。本発明の方法では、多重結合質問における全
ての表現されかつ暗示された結合述語を識別し；かつ各
結合述語に対してグラフにおいて一対の頂点及び接続エ
ッジを供給する段階を更に具備するように構成してもよ
い。
ョナルデータベース表の多重結合質問の濃度を推定する
コンピュータ実装式の方法であって：多重結合質問の結
合グラフを表すデータを計算し、結合グラフは、頂点の
セット及びエッジのセットを有し、頂点のセットは、多
重結合質問の表と一対一に対応し、エッジのセットは、
質問で表現されかつ暗示された結合述語と一対一に対応
し；かつ多重結合質問の濃度を推定するために結合グラ
フを表すデータを用いる段階を具備する方法によって達
成される。本発明の方法では、多重結合質問における全
ての表現されかつ暗示された結合述語を識別し；かつ各
結合述語に対してグラフにおいて一対の頂点及び接続エ
ッジを供給する段階を更に具備するように構成してもよ
い。
【００１５】本発明の方法では、述語が親キー−外部キ
ーであれば、対応接続エッジは、基本表から外部表に向
かって指向され、さもなければ、エッジは、未指向さ
れ、方法は、縮小されたグラフを形成すべくグラフから
末尾頂点を削除し；かつ多重結合質問の濃度を推定する
ために縮小されたグラフを表すデータを用いる段階を更
に具備するように構成してもよい。本発明の方法では、
末尾頂点を削除する段階は、グラフを通るパスにおける
各頂点を検査し、かつ頂点が末尾頂点であれば、該頂点
及び当該頂点に隣接する全てのエッジを除去し；かつい
ずれかの末尾頂点がグラフを通るパスの間で除去された
ならば、末尾頂点を除去するためにグラフを通る別のパ
スを作成する段階を具備するように構成してもよい。
ーであれば、対応接続エッジは、基本表から外部表に向
かって指向され、さもなければ、エッジは、未指向さ
れ、方法は、縮小されたグラフを形成すべくグラフから
末尾頂点を削除し；かつ多重結合質問の濃度を推定する
ために縮小されたグラフを表すデータを用いる段階を更
に具備するように構成してもよい。本発明の方法では、
末尾頂点を削除する段階は、グラフを通るパスにおける
各頂点を検査し、かつ頂点が末尾頂点であれば、該頂点
及び当該頂点に隣接する全てのエッジを除去し；かつい
ずれかの末尾頂点がグラフを通るパスの間で除去された
ならば、末尾頂点を除去するためにグラフを通る別のパ
スを作成する段階を具備するように構成してもよい。
【００１６】本発明の方法では、多重結合質問の濃度を
推定する段階は、各エッジによって表される結合の選択
率、各頂点によって表される表の濃度、及び各頂点によ
って表される表の個々の選択率を積算するように構成し
てもよい。更に、本発明の上述した課題は、リレーショ
ナルデータベース表の多重結合質問の濃度を推定するシ
ステムであって：多重結合質問の結合グラフを表すデー
タを計算する手段、結合グラフは、頂点のセット及びエ
ッジのセットを有し、頂点のセットは、多重結合質問の
表と一対一に対応し、エッジのセットは、質問で表現さ
れかつ暗示された結合述語と一対一に対応し；及び多重
結合質問の濃度を推定するために結合グラフを表すデー
タを用いる手段を具備するシステムによって達成され
る。
推定する段階は、各エッジによって表される結合の選択
率、各頂点によって表される表の濃度、及び各頂点によ
って表される表の個々の選択率を積算するように構成し
てもよい。更に、本発明の上述した課題は、リレーショ
ナルデータベース表の多重結合質問の濃度を推定するシ
ステムであって：多重結合質問の結合グラフを表すデー
タを計算する手段、結合グラフは、頂点のセット及びエ
ッジのセットを有し、頂点のセットは、多重結合質問の
表と一対一に対応し、エッジのセットは、質問で表現さ
れかつ暗示された結合述語と一対一に対応し；及び多重
結合質問の濃度を推定するために結合グラフを表すデー
タを用いる手段を具備するシステムによって達成され
る。
【００１７】本発明のシステムでは、多重結合質問にお
ける全ての表現されかつ暗示された結合述語を識別する
手段；及び各結合述語に対してグラフにおいて一対の頂
点及び接続エッジを供給する手段を更に備えているよう
に構成してもよい。本発明のシステムでは、述語が親キ
ー−外部キーであれば、対応接続エッジは、基本表から
外部表に向かって指向され、さもなければ、エッジは、
未指向され、システムは、縮小されたグラフを形成すべ
くグラフから末尾頂点を削除する手段；及び多重結合質
問の濃度を推定するために縮小されたグラフを表すデー
タを用いる手段を更に備えて構成してもよい。本発明の
システムでは、末尾頂点を削除する手段は、グラフを通
るパスにおける各頂点を検査し、かつ頂点が末尾頂点で
あれば、該頂点及び当該頂点に隣接する全てのエッジを
除去する手段を備えて構成してもよい。
ける全ての表現されかつ暗示された結合述語を識別する
手段；及び各結合述語に対してグラフにおいて一対の頂
点及び接続エッジを供給する手段を更に備えているよう
に構成してもよい。本発明のシステムでは、述語が親キ
ー−外部キーであれば、対応接続エッジは、基本表から
外部表に向かって指向され、さもなければ、エッジは、
未指向され、システムは、縮小されたグラフを形成すべ
くグラフから末尾頂点を削除する手段；及び多重結合質
問の濃度を推定するために縮小されたグラフを表すデー
タを用いる手段を更に備えて構成してもよい。本発明の
システムでは、末尾頂点を削除する手段は、グラフを通
るパスにおける各頂点を検査し、かつ頂点が末尾頂点で
あれば、該頂点及び当該頂点に隣接する全てのエッジを
除去する手段を備えて構成してもよい。
【００１８】本発明のシステムでは、多重結合質問の濃
度を推定する段階は、各エッジによって表される結合の
選択率、各頂点によって表される表の濃度、及び各頂点
によって表される表の個々の選択率を積算する手段を備
えて構成してもよい。
度を推定する段階は、各エッジによって表される結合の
選択率、各頂点によって表される表の濃度、及び各頂点
によって表される表の個々の選択率を積算する手段を備
えて構成してもよい。
【００１９】
【作用】一つの形態では、本発明は、代替結合順序の相
対的効率を比較するために設計されたメトリックのイン
プリメンテーションを介して多重結合質問において良好
な結合順序を計算するためのコンピュータ実装式方法に
関する。別の形態では、本発明は、Ｆｋ−Ｆｋ結合、即
ち、Ｒ．ｒ及びＳ．ｓの両方が一つの基本表の一つの基
本または交互(alternate) キーに関して外部キーであ
る、実質的にＲ．ｒ＝Ｓ．ｓの形の結合述語との結合、
の結合選択率を推定するためのコンピュータ実装式方法
に関する。別の形態では、本発明は、Ｐｋ−Ｆｋ結合及
びＦｋ−Ｆｋ結合のあらゆる組合せを含む、任意の大き
な数の多重結合の結合濃度を効率的に推定するためのコ
ンピュータ実装式方法に関する。
対的効率を比較するために設計されたメトリックのイン
プリメンテーションを介して多重結合質問において良好
な結合順序を計算するためのコンピュータ実装式方法に
関する。別の形態では、本発明は、Ｆｋ−Ｆｋ結合、即
ち、Ｒ．ｒ及びＳ．ｓの両方が一つの基本表の一つの基
本または交互(alternate) キーに関して外部キーであ
る、実質的にＲ．ｒ＝Ｓ．ｓの形の結合述語との結合、
の結合選択率を推定するためのコンピュータ実装式方法
に関する。別の形態では、本発明は、Ｐｋ−Ｆｋ結合及
びＦｋ−Ｆｋ結合のあらゆる組合せを含む、任意の大き
な数の多重結合の結合濃度を効率的に推定するためのコ
ンピュータ実装式方法に関する。
【００２０】本発明の利点の中で、結合質問性能の速さ
及び効率が改良される。本発明の更なる利点は、以下の
説明中に示され、かつ説明及び特許請求の範囲から明ら
かになるであろう。
及び効率が改良される。本発明の更なる利点は、以下の
説明中に示され、かつ説明及び特許請求の範囲から明ら
かになるであろう。
【００２１】
【実施例】本発明は、リレーショナルデータベースシス
テムにおける結合順序処理を最適化する方法及び装置を
供給する。図１は、本発明による濃度を利用した結合最
適化を取り入れたリレーショナルデータベースシステム
２６を支援するために適する汎用コンピュータプラット
フォーム１０を示す。プラットフォームは、（パーソナ
ルコンピュータまたはワークステーションのような）デ
ィジタルコンピュータ１２、ディスプレイ１４、（フロ
ッピディスクドライブ、ハードディクスドライブ、消去
可能ＣＤ−ＲＯＭドライブ、または磁気光学ディスクド
ライブのような）大容量記憶装置１６、キーボード１
８、及びマウス２０または他の入力装置を含む。コンピ
ュータ１２は、通常の構造のものでありかつメモリ２
２、プロセッサ２４、及びメモリバス及び周辺バス（図
示省略）のような、他の通常のコンポーネントを含む。
また、コンピュータ１２は、コンピュータ１２が、それ
によって通信リンク３６上の他のコンピュータ４０にコ
ンピュータネットワーク３８上で接続されうる通信ハー
ドウェア及びソフトウェア（図示省略）も含む。
テムにおける結合順序処理を最適化する方法及び装置を
供給する。図１は、本発明による濃度を利用した結合最
適化を取り入れたリレーショナルデータベースシステム
２６を支援するために適する汎用コンピュータプラット
フォーム１０を示す。プラットフォームは、（パーソナ
ルコンピュータまたはワークステーションのような）デ
ィジタルコンピュータ１２、ディスプレイ１４、（フロ
ッピディスクドライブ、ハードディクスドライブ、消去
可能ＣＤ−ＲＯＭドライブ、または磁気光学ディスクド
ライブのような）大容量記憶装置１６、キーボード１
８、及びマウス２０または他の入力装置を含む。コンピ
ュータ１２は、通常の構造のものでありかつメモリ２
２、プロセッサ２４、及びメモリバス及び周辺バス（図
示省略）のような、他の通常のコンポーネントを含む。
また、コンピュータ１２は、コンピュータ１２が、それ
によって通信リンク３６上の他のコンピュータ４０にコ
ンピュータネットワーク３８上で接続されうる通信ハー
ドウェア及びソフトウェア（図示省略）も含む。
【００２２】データベースシステム２６は、データベー
スを管理する。データベース２８は、一つのコンピュー
タに集中化されるか、またはコンピュータネットワーク
３８間に分配されうる。一般に、データベース２８は、
永久的または一時的に、データベースにリンクされるコ
ンピュータ上で実行されるデータベースシステム２６に
よって管理される。この説明では、データベース管理シ
ステムは、コンピュータ１２で実行されるものとして示
される。先に示したように、リレーショナルデータベー
スシステムの設計及び実現における問題点の一つは、結
合最適化、即ち、多重結合質問において表を結合するた
めの最適順序を計算することである。表が結合される順
序は、結合の結果に影響を及ぼさないが、同じ質問に対
する異なる結合順序は、異なる量の時間及び他の資源を
消費しうる。
スを管理する。データベース２８は、一つのコンピュー
タに集中化されるか、またはコンピュータネットワーク
３８間に分配されうる。一般に、データベース２８は、
永久的または一時的に、データベースにリンクされるコ
ンピュータ上で実行されるデータベースシステム２６に
よって管理される。この説明では、データベース管理シ
ステムは、コンピュータ１２で実行されるものとして示
される。先に示したように、リレーショナルデータベー
スシステムの設計及び実現における問題点の一つは、結
合最適化、即ち、多重結合質問において表を結合するた
めの最適順序を計算することである。表が結合される順
序は、結合の結果に影響を及ぼさないが、同じ質問に対
する異なる結合順序は、異なる量の時間及び他の資源を
消費しうる。
【００２３】表Ｒ、Ｓ、及びＴ、表Ｒ、Ｓ、及びＴが結
合されるような結合質問、及び二つの可能な結合順序：
（１）表Ｒ及びＳを結合し、そして結果を表Ｔと結合
し、かつ（２）表Ｓ及びＴを結合し、そして結果を表Ｒ
と結合する、を含むリレーショナルデータベースを考え
る。まず結合順序（１）を考える。｜（ＲがＳを結合す
る）｜＝２０かつ｜（ＲがＳを結合する）Ｔを結合する
｜＝６０ならば、合計質問の計算中に生成されたタプル
の合計数は、８０（２０＋６０）である。次に、結合順
序（２）を考える。｜（ＲがＴを結合する）｜＝５００
かつ｜（ＳがＴを結合する）Ｒを結合する｜＝６０なら
ば、合計質問の計算中に生成された記録の合計数は、５
６０（５００＋６０）である。結合順序の選択は、特に
大きな表を含む多重結合で、重要でありうる。
合されるような結合質問、及び二つの可能な結合順序：
（１）表Ｒ及びＳを結合し、そして結果を表Ｔと結合
し、かつ（２）表Ｓ及びＴを結合し、そして結果を表Ｒ
と結合する、を含むリレーショナルデータベースを考え
る。まず結合順序（１）を考える。｜（ＲがＳを結合す
る）｜＝２０かつ｜（ＲがＳを結合する）Ｔを結合する
｜＝６０ならば、合計質問の計算中に生成されたタプル
の合計数は、８０（２０＋６０）である。次に、結合順
序（２）を考える。｜（ＲがＴを結合する）｜＝５００
かつ｜（ＳがＴを結合する）Ｒを結合する｜＝６０なら
ば、合計質問の計算中に生成された記録の合計数は、５
６０（５００＋６０）である。結合順序の選択は、特に
大きな表を含む多重結合で、重要でありうる。
【００２４】新しいメトリック、Ｓｉｇｍａ（シグマ）
は、多重結合質問における可能な結合順序の中から結合
順序を選ぶために用いられる。Ｓｉｇｍａは、それが結
合順序で行われるときの各結合からの結果として生じる
べく推定されたタプルの数の和として定義される。Ｓｉ
ｇｍａメトリックを用いて、全ての結合順序の中で最も
小さいＳｉｇｍａを有している結合順序が最適として選
択されかつ結合を行うために用いられる。競合する結合
順序の間のタイ（同等性）は、例えば、費用推定計算に
更に基づくであろう、ある他の発見（heuristic ）を用
いて壊されうる。上記の例では、結合順序（１）に対す
るＳｉｇｍａは、８０であり、結合順序（２）に対する
Ｓｉｇｍａは、５６０であって、順序（２）に対して順
序（１）が好ましいということを示している。
は、多重結合質問における可能な結合順序の中から結合
順序を選ぶために用いられる。Ｓｉｇｍａは、それが結
合順序で行われるときの各結合からの結果として生じる
べく推定されたタプルの数の和として定義される。Ｓｉ
ｇｍａメトリックを用いて、全ての結合順序の中で最も
小さいＳｉｇｍａを有している結合順序が最適として選
択されかつ結合を行うために用いられる。競合する結合
順序の間のタイ（同等性）は、例えば、費用推定計算に
更に基づくであろう、ある他の発見（heuristic ）を用
いて壊されうる。上記の例では、結合順序（１）に対す
るＳｉｇｍａは、８０であり、結合順序（２）に対する
Ｓｉｇｍａは、５６０であって、順序（２）に対して順
序（１）が好ましいということを示している。
【００２５】図２は、表Ｔ＝｛Ｔ１、Ｔ２、Ｔ
３、．．．、Ｔｎ｝を含む結合質問に対して可能な結合
順序の中から結合順序を選ぶためにＳｉｇｍａメトリッ
クを用いるコンピュータ実装式処理１１０を示す。ま
ず、可能な結合順序の中から結合順序が選択される（ス
テップ１２０）。次に、結合順序における各コンポーネ
ント結合の濃度を得る（ステップ１３０）。これは、予
め計算された値を検索することにより、または他の方法
により、以下に説明するグラフ表現方法を用いて濃度を
推定することによって行うことができる。これらの濃度
が特定の方法を用いて計算されるということは、Ｓｉｇ
ｍａの計算に必要ない。Ｓｉｇｍａの値は、これらの濃
度推定のそれぞれを合計することによって計算される。
このＳｉｇｍａ値がそれまでに発生したＳｉｇｍａの最
小値であるならば、Ｓｉｇｍａの値及び対応結合順序の
両方が記憶される（ステップ１５０）。結合順序が検査
されために残っているならば、処理は、次の可能な結合
順序に対して繰り返される（ステップ１６０）。さもな
ければ、結合質問を行うためにＳｉｇｍａの最小値を有
する結合順序が用いられる（ステップ１７０）。
３、．．．、Ｔｎ｝を含む結合質問に対して可能な結合
順序の中から結合順序を選ぶためにＳｉｇｍａメトリッ
クを用いるコンピュータ実装式処理１１０を示す。ま
ず、可能な結合順序の中から結合順序が選択される（ス
テップ１２０）。次に、結合順序における各コンポーネ
ント結合の濃度を得る（ステップ１３０）。これは、予
め計算された値を検索することにより、または他の方法
により、以下に説明するグラフ表現方法を用いて濃度を
推定することによって行うことができる。これらの濃度
が特定の方法を用いて計算されるということは、Ｓｉｇ
ｍａの計算に必要ない。Ｓｉｇｍａの値は、これらの濃
度推定のそれぞれを合計することによって計算される。
このＳｉｇｍａ値がそれまでに発生したＳｉｇｍａの最
小値であるならば、Ｓｉｇｍａの値及び対応結合順序の
両方が記憶される（ステップ１５０）。結合順序が検査
されために残っているならば、処理は、次の可能な結合
順序に対して繰り返される（ステップ１６０）。さもな
ければ、結合質問を行うためにＳｉｇｍａの最小値を有
する結合順序が用いられる（ステップ１７０）。
【００２６】多重−結合質問における結合濃度は、質問
のグラフ表現を用いて推定することができる。しかしな
がら、結合グラフを用いる方法を説明する前に、個々の
結合濃度及び結合選択率を推定することについて説明す
る。Ｐｋ−Ｆｋ結合Ｒ．Ｐｋ＝Ｓ．Ｆｋを考える。各外
部キー値が基本表の一つの記録と正確にマッチするの
で、そのような結合の濃度は、外部の表（この例では、
表Ｓ）の濃度に等しい。例えば、大学教授の表Ｐ及び教
授が教えているクラス（授業）の表Ｓを含むデータベー
スを考える。Ｐ．ｐｒｏｆＩＤは、各教授を独自に識別
する基本キーである。Ｓ．ｔｅａｃｈｅｒは、クラスを
教えている一人の教授を識別する属性である。従って、
Ｓ．ｔｅａｃｈｅｒは、Ｐに対する外部キーである。
Ｓ．Ｆｋ＝Ｐ．Ｐｋの形である、結合述語Ｓ．ｔｅａｃ
ｈｅｒ＝Ｐ．ｐｒｏｆＩＤを有する結合質問は、各クラ
スが確実に一人の教授によって教えられるので、｜Ｓ｜
に等しい濃度を有する。
のグラフ表現を用いて推定することができる。しかしな
がら、結合グラフを用いる方法を説明する前に、個々の
結合濃度及び結合選択率を推定することについて説明す
る。Ｐｋ−Ｆｋ結合Ｒ．Ｐｋ＝Ｓ．Ｆｋを考える。各外
部キー値が基本表の一つの記録と正確にマッチするの
で、そのような結合の濃度は、外部の表（この例では、
表Ｓ）の濃度に等しい。例えば、大学教授の表Ｐ及び教
授が教えているクラス（授業）の表Ｓを含むデータベー
スを考える。Ｐ．ｐｒｏｆＩＤは、各教授を独自に識別
する基本キーである。Ｓ．ｔｅａｃｈｅｒは、クラスを
教えている一人の教授を識別する属性である。従って、
Ｓ．ｔｅａｃｈｅｒは、Ｐに対する外部キーである。
Ｓ．Ｆｋ＝Ｐ．Ｐｋの形である、結合述語Ｓ．ｔｅａｃ
ｈｅｒ＝Ｐ．ｐｒｏｆＩＤを有する結合質問は、各クラ
スが確実に一人の教授によって教えられるので、｜Ｓ｜
に等しい濃度を有する。
【００２７】結合質問の結合選択率は、結合した表の濃
度のプロダクトに対する結合（即ち、結合濃度）の結果
として生ずるマッチの数の比率である。それゆえに、Ｐ
ｋ−Ｆｋ結合の結合選択率は、Ｒが基本表であるよう
な、以下の式によって与えられる： Ｆｋ−Ｆｋ結合の濃度及び選択率を推定するために、Ｆ
ｋ−Ｆｋ結合を含んでいる以下のＳＱＬ質問を考える： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｓ，Ｔ ［例１］ ＷＨＥＲＥ Ｓ．Ｆｋ＝Ｔ．Ｆｋ この例では、Ｒ．Ｐｋは、Ｓ．Ｆｋ及びＴ．Ｆｋの両方
に対して基礎を成す基本キーである。そのような質問で
用いるキーの値がそれらの表において実質的に均等に分
配され、かつ基本キー値が外部キーの中で実質的に全て
見出されるならば、各別個の基本キー値に対して、｜Ｓ
｜／｜Ｒ｜は、Ｓ．Ｆｋにおける値の発生数の良好な推
定であり、｜Ｔ｜／｜Ｒ｜は、Ｔ．Ｆｋにおける値の発
生数の良好な推定である。従って、
度のプロダクトに対する結合（即ち、結合濃度）の結果
として生ずるマッチの数の比率である。それゆえに、Ｐ
ｋ−Ｆｋ結合の結合選択率は、Ｒが基本表であるよう
な、以下の式によって与えられる： Ｆｋ−Ｆｋ結合の濃度及び選択率を推定するために、Ｆ
ｋ−Ｆｋ結合を含んでいる以下のＳＱＬ質問を考える： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｓ，Ｔ ［例１］ ＷＨＥＲＥ Ｓ．Ｆｋ＝Ｔ．Ｆｋ この例では、Ｒ．Ｐｋは、Ｓ．Ｆｋ及びＴ．Ｆｋの両方
に対して基礎を成す基本キーである。そのような質問で
用いるキーの値がそれらの表において実質的に均等に分
配され、かつ基本キー値が外部キーの中で実質的に全て
見出されるならば、各別個の基本キー値に対して、｜Ｓ
｜／｜Ｒ｜は、Ｓ．Ｆｋにおける値の発生数の良好な推
定であり、｜Ｔ｜／｜Ｒ｜は、Ｔ．Ｆｋにおける値の発
生数の良好な推定である。従って、
【００２８】 としてＳ．Ｆｋ＝Ｔ．Ｆｋの結合濃度を推定しうる。結
合選択率の定義及び先に示した仮定から、 として、Ｆｋ−Ｆｋ結合の結合選択率を推定しうる。Ｐ
ｋ−Ｐｋ結合及びＦｋ−Ｆｋ結合の両方において、推定
した結合選択率は、｜Ｒ｜が基本キー表の濃度であるよ
うな、１／｜Ｒ｜に等しいということに注目する。
合選択率の定義及び先に示した仮定から、 として、Ｆｋ−Ｆｋ結合の結合選択率を推定しうる。Ｐ
ｋ−Ｐｋ結合及びＦｋ−Ｆｋ結合の両方において、推定
した結合選択率は、｜Ｒ｜が基本キー表の濃度であるよ
うな、１／｜Ｒ｜に等しいということに注目する。
【００２９】図３に示すように、コンピュータ実装式処
理２００は、Ｖが質問における表と一対一で対応する頂
点のセットであり、かつＥが質問における結合述語（表
現及び暗黙に定義された）と一対一で対応するエッジの
セットであるような、結合グラフＧ＝（Ｖ，Ｅ）として
多重結合質問を表現するために用いることができる。処
理を理解するために、以下の結合質問を考える： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例２］ ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ ＡＮＤ Ｒ．Ｐｋ＝Ｔ．Ｆｋ この結合を表現している結合グラフを形成するために、
第１の段階は、全ての表現結合述語を収集することであ
る（ステップ２２０）。例２では、二つのそのような述
語が存在する：Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．
Ｆｋ。次の段階は、暗黙に定義された全ての結合述語を
収集することである（ステップ２３０）。例２では、
Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．Ｆｋは、Ｓ．Ｆ
ｋ＝Ｔ．Ｆｋを暗黙に定義する。
理２００は、Ｖが質問における表と一対一で対応する頂
点のセットであり、かつＥが質問における結合述語（表
現及び暗黙に定義された）と一対一で対応するエッジの
セットであるような、結合グラフＧ＝（Ｖ，Ｅ）として
多重結合質問を表現するために用いることができる。処
理を理解するために、以下の結合質問を考える： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例２］ ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ ＡＮＤ Ｒ．Ｐｋ＝Ｔ．Ｆｋ この結合を表現している結合グラフを形成するために、
第１の段階は、全ての表現結合述語を収集することであ
る（ステップ２２０）。例２では、二つのそのような述
語が存在する：Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．
Ｆｋ。次の段階は、暗黙に定義された全ての結合述語を
収集することである（ステップ２３０）。例２では、
Ｒ．Ｐｋ＝Ｓ．Ｆｋ及びＲ．Ｐｋ＝Ｔ．Ｆｋは、Ｓ．Ｆ
ｋ＝Ｔ．Ｆｋを暗黙に定義する。
【００３０】次に、一対の頂点及びそれらを接続するエ
ッジは、収集された各述語に対するグラフに追加される
（ステップ２４０−２９０）。述語がＰｋ−Ｆｋである
ならば、対応エッジは、基本表から外部表に向かって指
向される（ステップ２７０）。述語がＦｋ−Ｆｋまたは
他の型の結合であれば、対応エッジは、指向されない
（ステップ２８０）。例２の結合質問に対応する結合グ
ラフを図４に示す。結合している列が独立であるような
結合質問の濃度は、（１）コンポーネント結合の選択率
のプロダクト、（２）結合における個別の表の濃度のプ
ロダクト、及び（３）結合における表での個別の選択の
選択率のプロダクトを積算することによって推定するこ
とができる。結合している列の独立は、全ての通常の最
適化装置(optimizers)に行われる想定である。形Ｐ．Ｐ
ｋ＝Ｓ．Ｆｋ及びＳ．Ｆｋ＝Ｔ．Ｆｋのコンポーネント
結合の選択率は、上述した方法を用いて推定されうる。
データベースシステム質問最適化装置は、それが他の種
類の結合の選択率を計算しまたは推定するために利用可
能であるあらゆる他の方法を用いうる。
ッジは、収集された各述語に対するグラフに追加される
（ステップ２４０−２９０）。述語がＰｋ−Ｆｋである
ならば、対応エッジは、基本表から外部表に向かって指
向される（ステップ２７０）。述語がＦｋ−Ｆｋまたは
他の型の結合であれば、対応エッジは、指向されない
（ステップ２８０）。例２の結合質問に対応する結合グ
ラフを図４に示す。結合している列が独立であるような
結合質問の濃度は、（１）コンポーネント結合の選択率
のプロダクト、（２）結合における個別の表の濃度のプ
ロダクト、及び（３）結合における表での個別の選択の
選択率のプロダクトを積算することによって推定するこ
とができる。結合している列の独立は、全ての通常の最
適化装置(optimizers)に行われる想定である。形Ｐ．Ｐ
ｋ＝Ｓ．Ｆｋ及びＳ．Ｆｋ＝Ｔ．Ｆｋのコンポーネント
結合の選択率は、上述した方法を用いて推定されうる。
データベースシステム質問最適化装置は、それが他の種
類の結合の選択率を計算しまたは推定するために利用可
能であるあらゆる他の方法を用いうる。
【００３１】このフォーミュラを結合グラフ４００に適
用することにより（図４）、質問濃度は、 であるべく計算される。通常の結合順序最適化装置は、
この結果をもたらすが、更に良い推定が見出される、具
体的には： であるべく計算される。これは、表Ｓ及びＴがまず結合
されたならばＮタプルが結果として生ずるということに
注目することによって確認することができる。（Ｓ，
Ｔ）の全ての行においてＳ．Ｆｋ＝Ｔ．Ｆｋなので、全
てのそのようなタルプは、Ｒの一つのタルプと確実に結
合し、それゆえに、追加のタルプを結果として生じな
い。
用することにより（図４）、質問濃度は、 であるべく計算される。通常の結合順序最適化装置は、
この結果をもたらすが、更に良い推定が見出される、具
体的には： であるべく計算される。これは、表Ｓ及びＴがまず結合
されたならばＮタプルが結果として生ずるということに
注目することによって確認することができる。（Ｓ，
Ｔ）の全ての行においてＳ．Ｆｋ＝Ｔ．Ｆｋなので、全
てのそのようなタルプは、Ｒの一つのタルプと確実に結
合し、それゆえに、追加のタルプを結果として生じな
い。
【００３２】図５に示すように、結合グラフ表現を用い
ている多重結合の濃度を推定するためのコンピュータ実
装式処理５００は、このインサイト（洞察力）を引き出
しかつ推定手順におけるグラフを変更することによって
正しい結果に到達する。まず、結合質問のグラフ表現
が、例えば、手順２００を用いることによって形成され
る（図３）。次に、全ての末尾頂点は、グラフから除去
される（ステップ５３０−５７０）。末尾頂点は、グラ
フの他の頂点がポイントしない頂点である。例えば、図
４では、頂点Ｒ４１０は、末尾頂点である。末尾頂点を
除去するために、手順５００は、グラフの各頂点を検査
する（ステップ５４０）。頂点が末尾頂点であれば、そ
れに隣接するそれ及び全てのエッジは、削除される（ス
テップ５５０）。このパスがグラフを通る間中に末尾頂
点が削除されるならば、末尾頂点を除去することは、別
の末尾頂点を生成しうるので、別のパスが次いでなされ
る（ステップ５７０）。
ている多重結合の濃度を推定するためのコンピュータ実
装式処理５００は、このインサイト（洞察力）を引き出
しかつ推定手順におけるグラフを変更することによって
正しい結果に到達する。まず、結合質問のグラフ表現
が、例えば、手順２００を用いることによって形成され
る（図３）。次に、全ての末尾頂点は、グラフから除去
される（ステップ５３０−５７０）。末尾頂点は、グラ
フの他の頂点がポイントしない頂点である。例えば、図
４では、頂点Ｒ４１０は、末尾頂点である。末尾頂点を
除去するために、手順５００は、グラフの各頂点を検査
する（ステップ５４０）。頂点が末尾頂点であれば、そ
れに隣接するそれ及び全てのエッジは、削除される（ス
テップ５５０）。このパスがグラフを通る間中に末尾頂
点が削除されるならば、末尾頂点を除去することは、別
の末尾頂点を生成しうるので、別のパスが次いでなされ
る（ステップ５７０）。
【００３３】一度全ての末尾頂点が除去されたならば、
オリジナル結合の結合濃度は、（１）各エッジによって
表現される結合の選択率、（２）各頂点によって表現さ
れる表の濃度、及び（３）各頂点によって表現される表
の個々の選択率を乗算することによって、残っているグ
ラフを用いて除去することができる（ステップ５８
０）。上記したように、この推定は、結合している列が
独立していることを想定する。
オリジナル結合の結合濃度は、（１）各エッジによって
表現される結合の選択率、（２）各頂点によって表現さ
れる表の濃度、及び（３）各頂点によって表現される表
の個々の選択率を乗算することによって、残っているグ
ラフを用いて除去することができる（ステップ５８
０）。上記したように、この推定は、結合している列が
独立していることを想定する。
【００３４】末尾頂点を除去することの効果は、以下の
質問の処理において説明される： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例３］ ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ ＡＮＤ Ｓ．Ｐｋ＝Ｔ．Ｆｋ
質問の処理において説明される： ＳＥＬＥＣＴ＊ＦＲＯＭ Ｒ，Ｓ，Ｔ ［例３］ ＷＨＥＲＥ Ｒ．Ｐｋ＝Ｓ．Ｆｋ ＡＮＤ Ｓ．Ｐｋ＝Ｔ．Ｆｋ
【００３５】結果の濃度は、｜Ｔ｜である。ＲとＳを結
合することは、Ｓの全ての行をマッチさせ、そしてＳと
Ｔを結合することは、Ｔの全ての行をマッチし、結果の
濃度は、｜Ｔ｜である。同じ結果は、図５の方法を用い
てグラフ表現を評価することによって得られる。図６の
結合グラフ６００は、例３の質問を表す。エッジ６２
０、６４０は、対応結合述語によって印が付けられる。
頂点Ｒ６１０は、末尾頂点である。頂点Ｒ６１０及びそ
れに隣接するエッジ６２０が取り除かれるとき、残った
ものは、頂点Ｓ６３０と頂点Ｔ６５０を接続している単
一エッジ６４０である。頂点Ｓ６３０は、いま末尾頂点
であり、そこで頂点Ｓ６３０及びそれに隣接するエッジ
６４０が取り除かれて、頂点Ｔ６５０だけを残す。結合
結果の濃度は、従って｜Ｔ｜である。本発明は、実施例
により説明された。しかしながら、本発明は、表示しか
つ説明した実施例に限定されない。例えば、本発明は、
ソフトウェアインプリメンテーションにより記述され
る；しかしながら、本発明は、ソフトウェアまたはハー
ドウェアまたはファームウェア、或いは３つのの組合せ
でインプリメントされうる。本発明の範疇は、特許請求
の範囲によって定義される。
合することは、Ｓの全ての行をマッチさせ、そしてＳと
Ｔを結合することは、Ｔの全ての行をマッチし、結果の
濃度は、｜Ｔ｜である。同じ結果は、図５の方法を用い
てグラフ表現を評価することによって得られる。図６の
結合グラフ６００は、例３の質問を表す。エッジ６２
０、６４０は、対応結合述語によって印が付けられる。
頂点Ｒ６１０は、末尾頂点である。頂点Ｒ６１０及びそ
れに隣接するエッジ６２０が取り除かれるとき、残った
ものは、頂点Ｓ６３０と頂点Ｔ６５０を接続している単
一エッジ６４０である。頂点Ｓ６３０は、いま末尾頂点
であり、そこで頂点Ｓ６３０及びそれに隣接するエッジ
６４０が取り除かれて、頂点Ｔ６５０だけを残す。結合
結果の濃度は、従って｜Ｔ｜である。本発明は、実施例
により説明された。しかしながら、本発明は、表示しか
つ説明した実施例に限定されない。例えば、本発明は、
ソフトウェアインプリメンテーションにより記述され
る；しかしながら、本発明は、ソフトウェアまたはハー
ドウェアまたはファームウェア、或いは３つのの組合せ
でインプリメントされうる。本発明の範疇は、特許請求
の範囲によって定義される。
【００３６】
【発明の効果】本発明の方法は、二つ以上の結合操作を
有している質問に対する結合順序を選択するためのコン
ピュータ実装式の方法であって：全ての可能な結合順序
を考慮し；可能な結合順序のそれぞれに対してＳｉｇｍ
ａメトリックの値を演算し；かつ Ｓｉｇｍａメトリッ
クの最小演算値を有している結合順序を選択する段階を
具備するので、より効率的かつ正確に最適結合順序を推
定することができる。本発明の方法は、Ｓ．ｆｋとＴ．
ｆｋの両方が一つの基本表Ｒの一つの基本または代替キ
ーに関して外部キーである、結合述語が実質的にＳ．ｆ
ｋ＝Ｔ．ｆｋであるような結合である、外部キー−外部
キー結合の結合選択率を推定する方法であって：｜Ｒ｜
が表Ｒの濃度を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率の推定を計
算する段階を具備するので、より効率的かつ正確に最適
結合順序を推定することができる。
有している質問に対する結合順序を選択するためのコン
ピュータ実装式の方法であって：全ての可能な結合順序
を考慮し；可能な結合順序のそれぞれに対してＳｉｇｍ
ａメトリックの値を演算し；かつ Ｓｉｇｍａメトリッ
クの最小演算値を有している結合順序を選択する段階を
具備するので、より効率的かつ正確に最適結合順序を推
定することができる。本発明の方法は、Ｓ．ｆｋとＴ．
ｆｋの両方が一つの基本表Ｒの一つの基本または代替キ
ーに関して外部キーである、結合述語が実質的にＳ．ｆ
ｋ＝Ｔ．ｆｋであるような結合である、外部キー−外部
キー結合の結合選択率を推定する方法であって：｜Ｒ｜
が表Ｒの濃度を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率の推定を計
算する段階を具備するので、より効率的かつ正確に最適
結合順序を推定することができる。
【００３７】本発明のシステムは、二つ以上の結合操作
を有する質問に対する結合順序を選択するシステムであ
って：全ての可能な結合順序のそれぞれに対してＳｉｇ
ｍａメトリックの値を演算する手段；及びＳｉｇｍａメ
トリックの最小の演算された値を有する結合順序を選択
する手段を備えているので、より効率的かつ正確に最適
結合順序を推定することができる。本発明のシステム
は、結合述語が、Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの
基本表Ｒの一つの基本または代替キーに関して外部キー
である実質的にＳ．ｆｋ＝Ｔ．ｆｋであるような結合で
ある、外部キー−外部キー結合の結合選択率を推定する
システムであって：Ｆｋ−Ｆｋ結合として述語を識別す
る手段；及び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の結合選択率の推定を計
算する手段を備えているので、より効率的かつ正確に最
適結合順序を推定することができる。
を有する質問に対する結合順序を選択するシステムであ
って：全ての可能な結合順序のそれぞれに対してＳｉｇ
ｍａメトリックの値を演算する手段；及びＳｉｇｍａメ
トリックの最小の演算された値を有する結合順序を選択
する手段を備えているので、より効率的かつ正確に最適
結合順序を推定することができる。本発明のシステム
は、結合述語が、Ｓ．ｆｋ及びＴ．ｆｋの両方が一つの
基本表Ｒの一つの基本または代替キーに関して外部キー
である実質的にＳ．ｆｋ＝Ｔ．ｆｋであるような結合で
ある、外部キー−外部キー結合の結合選択率を推定する
システムであって：Ｆｋ−Ｆｋ結合として述語を識別す
る手段；及び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の結合選択率の推定を計
算する手段を備えているので、より効率的かつ正確に最
適結合順序を推定することができる。
【００３８】本発明の方法は、リレーショナルデータベ
ース表の多重結合質問の濃度を推定するコンピュータ実
装式の方法であって：多重結合質問の結合グラフを表す
データを計算し、結合グラフは、頂点のセット及びエッ
ジのセットを有し、頂点のセットは、多重結合質問の表
と一対一に対応し、エッジのセットは、質問で表現され
かつ暗示された結合述語と一対一に対応し；かつ多重結
合質問の濃度を推定するために結合グラフを表すデータ
を用いる段階を具備するので、より効率的かつ正確に最
適結合順序を推定することができる。本発明のシステム
は、リレーショナルデータベース表の多重結合質問の濃
度を推定するシステムであって：多重結合質問の結合グ
ラフを表すデータを計算する手段、結合グラフは、頂点
のセット及びエッジのセットを有し、頂点のセットは、
多重結合質問の表と一対一に対応し、エッジのセット
は、質問で表現されかつ暗示された結合述語と一対一に
対応し；及び多重結合質問の濃度を推定するために結合
グラフを表すデータを用いる手段を具備するので、より
効率的かつ正確に最適結合順序を推定することができ
る。
ース表の多重結合質問の濃度を推定するコンピュータ実
装式の方法であって：多重結合質問の結合グラフを表す
データを計算し、結合グラフは、頂点のセット及びエッ
ジのセットを有し、頂点のセットは、多重結合質問の表
と一対一に対応し、エッジのセットは、質問で表現され
かつ暗示された結合述語と一対一に対応し；かつ多重結
合質問の濃度を推定するために結合グラフを表すデータ
を用いる段階を具備するので、より効率的かつ正確に最
適結合順序を推定することができる。本発明のシステム
は、リレーショナルデータベース表の多重結合質問の濃
度を推定するシステムであって：多重結合質問の結合グ
ラフを表すデータを計算する手段、結合グラフは、頂点
のセット及びエッジのセットを有し、頂点のセットは、
多重結合質問の表と一対一に対応し、エッジのセット
は、質問で表現されかつ暗示された結合述語と一対一に
対応し；及び多重結合質問の濃度を推定するために結合
グラフを表すデータを用いる手段を具備するので、より
効率的かつ正確に最適結合順序を推定することができ
る。
【図１】本発明による汎用コンピュータプラットフォー
ムプログラマブルでありリレーショナルデータベースを
含むブロック図である。
ムプログラマブルでありリレーショナルデータベースを
含むブロック図である。
【図２】リレーショナルデータベースシステムにおける
結合質問の表の所与のセットに対する最適結合順序を計
算するためのコンピュータ実装型方法のブロック図であ
る。
結合質問の表の所与のセットに対する最適結合順序を計
算するためのコンピュータ実装型方法のブロック図であ
る。
【図３】多重結合質問のグラフ表現を生成するためのコ
ンピュータ実装型方法のブロック図である。
ンピュータ実装型方法のブロック図である。
【図４】結合グラフの図である。
【図５】結合質問のグラフ表現を用いて多重結合質問の
結合濃度を推定するためのコンピュータ実装型方法のブ
ロック図である。
結合濃度を推定するためのコンピュータ実装型方法のブ
ロック図である。
【図６】結合グラフの図である。
１０ 汎用コンピュータプラットフォーム １２ ディジタルコンピュータ １４ ディスプレイ １６ 大容量記憶装置 １８ キーボード ２０ マウス ２２ メモリ ２４ プロセッサ ２６ リレーショナルデータベースシステム ２８ データベース ３６ 通信リンク ３８ コンピュータネットワーク ４０ コンピュータ
Claims (26)
- 【請求項１】 二つ以上の結合操作を有している質問に
対する結合順序を選択するためのコンピュータ実装式の
方法であって：全ての可能な結合順序を考慮し；可能な
結合順序のそれぞれに対してＳｉｇｍａメトリックの値
を演算し；かつＳｉｇｍａメトリックの最小演算値を有
している結合順序を選択する段階を具備することを特徴
とする方法。 - 【請求項２】 結合順序に対する前記Ｓｉｇｍａの値
は、それが結合順序で行われるときの各結合の濃度の推
定の結合順序における全ての結合にわたる合計であり、
結合の濃度は、結合の結果として生ずるタプルの数であ
ることを特徴とする請求項１に記載の方法。 - 【請求項３】 可能な結合順序の中から結合順序を選択
し；前記選択した結合順序における各コンポーネント結
合の濃度の推定を取得し；濃度推定のそれぞれを合計す
ることによってＳｉｇｍａに対する値を計算する段階を
更に具備することを特徴とする請求項１に記載の方法。 - 【請求項４】 各コンポーネント結合の濃度を取得する
段階は、グラフ表現方法を用いて濃度を推定する段階を
具備することを特徴とする請求項３に記載の方法。 - 【請求項５】 各コンポーネント結合の濃度を取得する
段階は、コンポーネント結合の一つの濃度として予め演
算した値を検索する段階を具備することを特徴とする請
求項３に記載の方法。 - 【請求項６】 Ｓ．ｆｋとＴ．ｆｋの両方が一つの基本
表Ｒの一つの基本または代替キーに関して外部キーであ
る、結合述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであるよう
な結合である、外部キー−外部キー結合としてコンポー
ネント結合を識別し；かつ、ここで｜Ｒ｜が表Ｒの濃度
を表す、 （｜Ｓ｜・｜Ｔ｜）／｜Ｒ｜ として外部キー−外部キー結合の濃度を推定する段階を
更に具備することを特徴とする請求項２に記載の方法。 - 【請求項７】 Ｓ．ｆｋとＴ．ｆｋの両方が一つの基本
表Ｒの一つの基本または代替キーに関して外部キーであ
る、結合述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであるよう
な結合である、外部キー−外部キー結合としてコンポー
ネント結合を識別し；かつ、ここで｜Ｒ｜が表Ｒの濃度
を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率を推定する
段階を更に具備することを特徴とする請求項２に記載の
方法。 - 【請求項８】 Ｓ．ｆｋとＴ．ｆｋの両方が一つの基本
表Ｒの一つの基本または代替キーに関して外部キーであ
る、結合述語が実質的にＳ．ｆｋ＝Ｔ．ｆｋであるよう
な結合である、外部キー−外部キー結合の結合選択率を
推定する方法であって：｜Ｒ｜が表Ｒの濃度を表す、 １／｜Ｒ｜ として外部キー−外部キー結合の結合選択率の推定を計
算する段階を具備することを特徴とする方法。 - 【請求項９】 二つ以上の結合操作を有する質問に対す
る結合順序を選択するシステムであって：全ての可能な
結合順序のそれぞれに対してＳｉｇｍａメトリックの値
を演算する手段；及び前記Ｓｉｇｍａメトリックの最小
の演算された値を有する結合順序を選択する手段を備え
ていることを特徴とするシステム。 - 【請求項１０】 結合順序に対する前記Ｓｉｇｍａの値
は、それが結合順序で行われるときの各結合の濃度の推
定の結合順序における全ての結合にわたる合計であり、
前記結合の濃度は、前記結合の結果として生ずるタルプ
の数であることを特徴とする請求項９に記載のシステ
ム。 - 【請求項１１】 前記可能な結合順序の中から結合順序
を選択する手段；前記選択した結合順序における各コン
ポーネント結合の濃度の推定を取得する手段；及び前記
濃度推定のそれぞれを合計することによってＳｉｇｍａ
に対する値を計算する手段を更に具備することを特徴と
する請求項９に記載のシステム。 - 【請求項１２】 前記各コンポーネント結合の濃度を取
得する手段は、 グラフ表現方法を用いて濃度を推定する手段を備えてい
ることを特徴とする請求項１１に記載のシステム。 - 【請求項１３】 前記各コンポーネント結合の濃度を取
得する手段は、 前記コンポーネント結合の一つの濃度として予め演算さ
れた値を検索する手段を備えていることを特徴とする請
求項１１に記載のシステム。 - 【請求項１４】 前記結合述語が、Ｓ．ｆｋ及びＴ．ｆ
ｋの両方が一つの基本表Ｒの一つの基本または代替キー
に関して外部キーである実質的にＳ．ｆｋ＝Ｔ．ｆｋで
あるような結合である、外部キー−外部キー結合として
コンポーネント結合を識別する手段；及び｜Ｒ｜が表Ｒ
の濃度を示す、 として外部キー−外部キー結合の濃度を推定する手段を
更に備えていることを特徴とする請求項１０に記載のシ
ステム。 - 【請求項１５】 前記結合述語が、Ｓ．ｆｋ及びＴ．ｆ
ｋの両方が一つの基本表Ｒの一つの基本または代替キー
に関して外部キーである実質的にＳ．ｆｋ＝Ｔ．ｆｋで
あるような結合である、外部キー−外部キー結合として
コンポーネント結合を識別する手段；及び｜Ｒ｜が表Ｒ
の濃度を示す、 として外部キー−外部キー結合の選択率を推定する手段
を更に備えていることを特徴とする請求項１０に記載の
システム。 - 【請求項１６】 結合述語が、Ｓ．ｆｋ及びＴ．ｆｋの
両方が一つの基本表Ｒの一つの基本または代替キーに関
して外部キーである実質的にＳ．ｆｋ＝Ｔ．ｆｋである
ような結合である、外部キー−外部キー結合の結合選択
率を推定するシステムであって：Ｆｋ−Ｆｋ結合として
述語を識別する手段；及び｜Ｒ｜が表Ｒの濃度を示す、 として外部キー−外部キー結合の結合選択率の推定を計
算する手段を備えていることを特徴とするシステム。 - 【請求項１７】 リレーショナルデータベース表の多重
結合質問の濃度を推定するコンピュータ実装式の方法で
あって：前記多重結合質問の結合グラフを表すデータを
計算し、 前記結合グラフは、頂点のセット及びエッジのセットを
有し、 前記頂点のセットは、前記多重結合質問の前記表と一対
一に対応し、 前記エッジのセットは、前記質問で表現されかつ暗示さ
れた結合述語と一対一に対応し；かつ前記多重結合質問
の前記濃度を推定するために前記結合グラフを表すデー
タを用いる段階を具備することを特徴とする方法。 - 【請求項１８】 前記多重結合質問における全ての表現
されかつ暗示された結合述語を識別し；かつ各結合述語
に対して前記グラフにおいて一対の頂点及び接続エッジ
を供給する段階を更に具備することを特徴とする請求項
１７に記載の方法。 - 【請求項１９】 前記述語が親キー−外部キーであれ
ば、対応接続エッジは、前記基本表から前記外部表に向
かって指向され、さもなければ、前記エッジは、未指向
され、前記方法は、 縮小されたグラフを形成すべく前記グラフから末尾頂点
を削除し；かつ前記多重結合質問の前記濃度を推定する
ために前記縮小されたグラフを表すデータを用いる段階
を更に具備することを特徴とする請求項１８に記載の方
法。 - 【請求項２０】 前記末尾頂点を削除する段階は、 前記グラフを通るパスにおける各頂点を検査し、かつ前
記頂点が末尾頂点であれば、該頂点及び当該頂点に隣接
する全てのエッジを除去し；かついずれかの末尾頂点が
前記グラフを通るパスの間で除去されたならば、末尾頂
点を除去するために前記グラフを通る別のパスを作成す
る段階を具備することを特徴とする請求項１９に記載の
方法。 - 【請求項２１】 前記多重結合質問の前記濃度を推定す
る段階は、 各エッジによって表される前記結合の前記選択率、各頂
点によって表される前記表の前記濃度、及び各頂点によ
って表される前記表の個々の選択率を積算することを特
徴とする請求項１９に記載の方法。 - 【請求項２２】 リレーショナルデータベース表の多重
結合質問の濃度を推定するシステムであって：前記多重
結合質問の結合グラフを表すデータを計算する手段、 前記結合グラフは、頂点のセット及びエッジのセットを
有し、 前記頂点のセットは、前記多重結合質問の前記表と一対
一に対応し、 前記エッジのセットは、前記質問で表現されかつ暗示さ
れた結合述語と一対一に対応し；及び前記多重結合質問
の前記濃度を推定するために前記結合グラフを表すデー
タを用いる手段を具備することを特徴とするシステム。 - 【請求項２３】 前記多重結合質問における全ての表現
されかつ暗示された結合述語を識別する手段；及び各結
合述語に対して前記グラフにおいて一対の頂点及び接続
エッジを供給する手段を更に備えていることを特徴とす
る請求項２２に記載のシステム。 - 【請求項２４】 前記述語が親キー−外部キーであれ
ば、対応接続エッジは、前記基本表から前記外部表に向
かって指向され、さもなければ、前記エッジは、未指向
され、前記システムは、 縮小されたグラフを形成すべく前記グラフから末尾頂点
を削除する手段；及び前記多重結合質問の前記濃度を推
定するために前記縮小されたグラフを表すデータを用い
る手段を更に備えていることを特徴とする請求項２３に
記載の方法。 - 【請求項２５】 前記末尾頂点を削除する手段は、 前記グラフを通るパスにおける各頂点を検査し、かつ前
記頂点が末尾頂点であれば、該頂点及び当該頂点に隣接
する全てのエッジを除去する手段を備えていることを特
徴とする請求項２４に記載のシステム。 - 【請求項２６】 前記多重結合質問の前記濃度を推定す
る段階は、 各エッジによって表される前記結合の前記選択率、各頂
点によって表される前記表の前記濃度、及び各頂点によ
って表される前記表の個々の選択率を積算する手段を備
えていることを特徴とする請求項２４に記載のシステ
ム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/850246 | 1997-05-02 | ||
| US08/850,246 US6138111A (en) | 1997-05-02 | 1997-05-02 | Cardinality-based join ordering |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JPH117454A true JPH117454A (ja) | 1999-01-12 |
| JPH117454A5 JPH117454A5 (ja) | 2008-01-10 |
| JP4397978B2 JP4397978B2 (ja) | 2010-01-13 |
Family
ID=25307638
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11925298A Expired - Lifetime JP4397978B2 (ja) | 1997-05-02 | 1998-04-28 | 濃度を利用した結合順序付け方法 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US6138111A (ja) |
| EP (1) | EP0875838B1 (ja) |
| JP (1) | JP4397978B2 (ja) |
| AU (1) | AU730251B2 (ja) |
| BR (1) | BR9801531A (ja) |
| CA (1) | CA2236494A1 (ja) |
| DE (1) | DE69838158T2 (ja) |
Families Citing this family (31)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6009432A (en) * | 1998-07-08 | 1999-12-28 | Required Technologies, Inc. | Value-instance-connectivity computer-implemented database |
| US7076507B1 (en) * | 1998-07-08 | 2006-07-11 | Required Technologies, Inc. | Value-instance-connectivity computer-implemented database |
| US6377943B1 (en) * | 1999-01-20 | 2002-04-23 | Oracle Corp. | Initial ordering of tables for database queries |
| US6738755B1 (en) * | 1999-05-19 | 2004-05-18 | International Business Machines Corporation | Query optimization method for incrementally estimating the cardinality of a derived relation when statistically correlated predicates are applied |
| JP4428488B2 (ja) * | 1999-05-31 | 2010-03-10 | 株式会社ターボデータラボラトリー | 表形式データの結合方法、上記方法を実現するプログラムを記憶した記憶媒体、および、表形式データを結合する装置 |
| US6397204B1 (en) * | 1999-06-25 | 2002-05-28 | International Business Machines Corporation | Method, system, and program for determining the join ordering of tables in a join query |
| US6446063B1 (en) | 1999-06-25 | 2002-09-03 | International Business Machines Corporation | Method, system, and program for performing a join operation on a multi column table and satellite tables |
| US6374235B1 (en) | 1999-06-25 | 2002-04-16 | International Business Machines Corporation | Method, system, and program for a join operation on a multi-column table and satellite tables including duplicate values |
| US7890491B1 (en) | 1999-12-22 | 2011-02-15 | International Business Machines Corporation | Query optimization technique for obtaining improved cardinality estimates using statistics on automatic summary tables |
| US7620615B1 (en) * | 2001-10-26 | 2009-11-17 | Teradata Us, Inc. | Joins of relations in an object relational database system |
| US6915290B2 (en) * | 2001-12-11 | 2005-07-05 | International Business Machines Corporation | Database query optimization apparatus and method that represents queries as graphs |
| US7085754B2 (en) * | 2002-03-04 | 2006-08-01 | International Business Machines Corporation | System and a two-pass algorithm for determining the optimum access path for multi-table SQL queries |
| JP3861044B2 (ja) * | 2002-10-24 | 2006-12-20 | 株式会社ターボデータラボラトリー | 連鎖したジョインテーブルのツリー構造への変換方法、および、変換プログラム |
| US7076477B2 (en) * | 2002-12-19 | 2006-07-11 | International Business Machines Corporation | Fast and robust optimization of complex database queries |
| US7171398B2 (en) * | 2003-10-16 | 2007-01-30 | International Business Machines Corporation | Outer and exception join to inner join normalization |
| US7478080B2 (en) * | 2004-09-30 | 2009-01-13 | International Business Machines Corporation | Canonical abstraction for outerjoin optimization |
| US7536379B2 (en) * | 2004-12-15 | 2009-05-19 | International Business Machines Corporation | Performing a multiple table join operating based on generated predicates from materialized results |
| US7565342B2 (en) * | 2005-09-09 | 2009-07-21 | International Business Machines Corporation | Dynamic semi-join processing with runtime optimization |
| US7882121B2 (en) * | 2006-01-27 | 2011-02-01 | Microsoft Corporation | Generating queries using cardinality constraints |
| US8285677B2 (en) | 2006-06-30 | 2012-10-09 | International Business Machines Corporation | Method and apparatus for propagating tables while preserving cyclic foreign key relationships |
| US9229982B2 (en) | 2008-12-23 | 2016-01-05 | SAP France S.A. | Processing queries using oriented query paths |
| US8244715B2 (en) | 2009-04-09 | 2012-08-14 | Paraccel, Inc. | System and method for processing database queries |
| US20110246476A1 (en) * | 2010-04-06 | 2011-10-06 | Salesforce.Com, Inc. | Method and system for performing a search of a feed in an on-demand enterprise services environment |
| US9177026B2 (en) | 2012-09-27 | 2015-11-03 | LogicBlox, Inc. | Leapfrog tree-join |
| US9720966B2 (en) * | 2012-12-20 | 2017-08-01 | Teradata Us, Inc. | Cardinality estimation for optimization of recursive or iterative database queries by databases |
| US9183201B1 (en) * | 2012-12-20 | 2015-11-10 | Emc Corporation | Policy based over sampling with replacement |
| US20140214886A1 (en) | 2013-01-29 | 2014-07-31 | ParElastic Corporation | Adaptive multi-client saas database |
| KR101951999B1 (ko) * | 2016-08-31 | 2019-05-10 | 재단법인대구경북과학기술원 | 낮은 데이터 중복으로 빠른 쿼리 처리를 지원하는 관계형 데이터베이스 저장 시스템, 저장 방법 및 관계형 데이터베이스 저장 방법에 기초한 쿼리를 처리하는 방법 |
| CN110188124A (zh) * | 2019-05-10 | 2019-08-30 | 中国银行股份有限公司 | 一种数据获取方法及装置 |
| US11544264B2 (en) | 2020-04-29 | 2023-01-03 | Hewlett Packard Enterprise Development Lp | Determining query join orders |
| US20250139092A1 (en) * | 2023-10-26 | 2025-05-01 | Oracle International Corporation | Histogram-augment dynamic sampling for join cardinality estimation |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5379419A (en) * | 1990-12-07 | 1995-01-03 | Digital Equipment Corporation | Methods and apparatus for accesssing non-relational data files using relational queries |
| US5345585A (en) * | 1991-12-02 | 1994-09-06 | International Business Machines Corporation | Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations |
| US5412804A (en) * | 1992-04-30 | 1995-05-02 | Oracle Corporation | Extending the semantics of the outer join operator for un-nesting queries to a data base |
| US5469568A (en) * | 1993-01-07 | 1995-11-21 | International Business Machines Corporation | Method for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization |
| US5664171A (en) * | 1994-04-14 | 1997-09-02 | International Business Machines Corporation | System and method for query optimization using quantile values of a large unordered data set |
| DE19515020A1 (de) * | 1994-07-01 | 1996-01-04 | Hewlett Packard Co | Verfahren und Vorrichtung zum Optimieren von Abfragen mit Gruppieren-nach-Operatoren |
| US5671403A (en) * | 1994-12-30 | 1997-09-23 | International Business Machines Corporation | Iterative dynamic programming system for query optimization with bounded complexity |
| US5758335A (en) * | 1996-09-27 | 1998-05-26 | Bull Hn Information Systems Inc. | Optimizing table join ordering using graph theory prior to query optimization |
-
1997
- 1997-05-02 US US08/850,246 patent/US6138111A/en not_active Expired - Lifetime
-
1998
- 1998-04-24 AU AU63568/98A patent/AU730251B2/en not_active Ceased
- 1998-04-28 JP JP11925298A patent/JP4397978B2/ja not_active Expired - Lifetime
- 1998-04-30 BR BR9801531A patent/BR9801531A/pt not_active IP Right Cessation
- 1998-05-01 CA CA002236494A patent/CA2236494A1/en not_active Abandoned
- 1998-05-05 DE DE69838158T patent/DE69838158T2/de not_active Expired - Lifetime
- 1998-05-05 EP EP98303480A patent/EP0875838B1/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0875838B1 (en) | 2007-08-01 |
| BR9801531A (pt) | 1999-03-30 |
| CA2236494A1 (en) | 1998-11-02 |
| DE69838158D1 (de) | 2007-09-13 |
| US6138111A (en) | 2000-10-24 |
| AU730251B2 (en) | 2001-03-01 |
| DE69838158T2 (de) | 2008-04-24 |
| JP4397978B2 (ja) | 2010-01-13 |
| EP0875838A3 (en) | 2000-12-27 |
| AU6356898A (en) | 1998-11-05 |
| EP0875838A2 (en) | 1998-11-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4397978B2 (ja) | 濃度を利用した結合順序付け方法 | |
| JPH117454A5 (ja) | ||
| US6850925B2 (en) | Query optimization by sub-plan memoization | |
| Simitsis et al. | State-space optimization of ETL workflows | |
| US6947927B2 (en) | Method and apparatus for exploiting statistics on query expressions for optimization | |
| US20080222634A1 (en) | Parallel processing for etl processes | |
| JPH0855138A (ja) | 関係データベースの質問を最適化する方法 | |
| US7409401B2 (en) | Method and system for supporting multivalue attributes in a database system | |
| US20080288444A1 (en) | Evaluating Multi-Table Join Selectivity in a Computer Database | |
| US7685098B2 (en) | Estimating the size of a join by generating and combining partial join estimates | |
| JPH1185769A (ja) | 対象の集団から選択可能な特性を有する対象群を発見する方法 | |
| JPH09190452A (ja) | データベース質問をコンピュータで実行する方法 | |
| US20110022581A1 (en) | Derived statistics for query optimization | |
| CN111913986B (zh) | 一种查询优化方法及装置 | |
| CN110580291B (zh) | 基于erp客户服务知识图谱的智能搜索方法及计算机设备 | |
| JP2005100392A (ja) | クエリ処理操作中に補助属性を用いてクエリをリライトするための方法および装置 | |
| CN115328883A (zh) | 一种数据仓库建模方法和系统 | |
| JPH10124533A (ja) | 偏り防止結合サイズ評価方法 | |
| CN107133281B (zh) | 一种基于分组的全局多查询优化方法 | |
| CN110147396B (zh) | 一种映射关系生成方法及装置 | |
| CN110597857B (zh) | 一种基于共享样本的在线聚集方法 | |
| Margoor et al. | Improving join reordering for large scale distributed computing | |
| US7127457B1 (en) | Method and system for executing database queries | |
| CN114936219A (zh) | 多表连接执行计划的选择方法、存储介质与计算机设备 | |
| MXPA98003441A (en) | Union ordering based on cardinali |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A711 Effective date: 20040227 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20041228 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070227 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070227 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080618 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20080918 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20081111 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090206 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20090324 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20090609 |
|
| RD12 | Notification of acceptance of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7432 Effective date: 20090611 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20090612 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20090611 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20090722 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20090728 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20090817 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20090825 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090915 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20091020 |
|
| RD14 | Notification of resignation of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7434 Effective date: 20091020 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20091022 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121030 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121030 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131030 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131030 Year of fee payment: 4 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131030 Year of fee payment: 4 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |