JPH10124533A - 偏り防止結合サイズ評価方法 - Google Patents

Abstract

(57)【要約】 【課題】 ２つのデータベースＴ及びＲの質問サイズの
評価方法を提供する。 【解決手段】 この方法は、データベースを稠密または
疎であるとして類別するためにスレショールドを使用す
る。そこで、２つのデータベースに稠密−稠密手順が適
用され、稠密−稠密評価（Ａ_d ）を作り出す。データベ
ースＴからくるデータアイテムを抑制する疎−何れか手
順が行なわれ、第１の疎−何れか評価（Ａ_s1）を作り出
す。次いで、データベースＲから稠密なデータアイテム
を抑制することによって、第２の疎−何れか評価
（Ａ_s2）が作り出される。最後に、稠密−稠密評価、第
１の疎−何れか評価及び第２の疎−何れか評価を結合す
ることにより、質問サイズ評価が作り出される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データベース質問
評価に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】コンピ
ュータのまん延につれて、コンピュータデータベースも
増加した。近頃のデータベースのサイズは非常に大容量
になることがあり、データベースの中には数百乃至数十
億のデータアイテムを保持しているものがある。これら
のデータベースの内の１つのデータベースの質問では、
あらゆるデータアイテムが質問に合う可能性があり、あ
らゆるデータアイテムを比較しなければならないことが
ある。したがって、これらのデータベースのサイズが増
すにつれて、質問を実行するコストも増加している。

【０００３】データベースは１つ以上のテーブルからな
り、各テーブルは週百乃至数十億のデータ記録を保持し
ている。各データ記録は、情報が入っている１つ以上の
フィールドを含む。これらのフィールド内の情報に基づ
いて、記録をいくつかのタイプのうちの１つのタイプと
して類別することができる。例えば、テーブルは人間の
記録を入れることができ、各記録は、人名を与えるフィ
ールドと、好きなスポーツを与えるフィールドを有す
る。各記録は好きなスポーツで類別することができるの
で、タイプ“野球”、“フットボール”または“ホッケ
ー”とすることができる。

【０００４】データベースのテーブルの質問に早く応答
することができるのが望ましい。共通の質問の１つは等
結合質問である。２つのテーブルＲ及びＴの等結合質問
の結果は、１つの記録がＲからかつもう１つの記録がＴ
からのものであっていずれも同タイプのものである記録
ペアの全てからなるテーブルとなる。例えば、テーブル
Ｒが男性及び彼らが好きなスポーツの記録を含み、かつ
テーブルＴが女性及び彼女らが好きなスポーツの記録を
含む場合は、テーブルＲ及びＴの等結合は、好きなスポ
ーツが同じ男性と女性の記録ペアの全てを含むテーブル
となる。

【０００５】等結合の結果を計算するのは、コストがか
かり過ぎることになる可能性がある。例えば、一方のテ
ーブルがｎ個の記録を持ち、かつ他方のテーブルがｎ個
の記録を持っている場合は、結果の計算はｎ² の記録ペ
アの比較を必要とし得る。ｎ² の比較をそれぞれ実行す
ると、質問コストが増加する。したがって、等結合質問
のコストを下げるのが好適である。

【０００６】大容量データベースにおける費用のかかる
質問の実行のコストを減らす必要性の結果として、デー
タベース評価の分野がポピュラーになってきた。データ
ベース評価において、評価は、データベースにおける質
問の可能な出力（質問の評価と呼ばれる）で作られる。
したがって、質問の評価は、質問を行なう前に計算され
る。その結果、質問を続けてコストを負うべきかまたは
この特定の質問を取り消すべきかに関して決定すること
ができる。データベース評価の問題点は、評価が正確か
つ計算が能率的になるように、特定の質問の評価を計算
することを伴うことである。

【０００７】このデータベース評価の問題点を解決する
試みが以前に行われた。パラメータ法と呼ばれる手法
は、データをとり、データベースにおいてこのデータと
既知のデータモデルを比較するのを試みる。データモデ
ルの作用と性質がデータベースのデータと同じであるこ
とが原理になっている。しかしながら、パラメータ法で
は、データが既知のデータモデルにどのくらい近似して
いるかについての仮定が行われる必要があり、近似（デ
ータの適合）は結果の正確さをはなはだしく変えてしま
うことがある。他の種類の手法は、データベースにおけ
るデータアイテムのサンプル（小さな一組）をとり、こ
れらのサンプルに基づいて評価を行なう。この種の手法
はサンプリング法として知られている。サンプルは、通
常、個々のデータベースの中からとられ、次いで合成さ
れて質問評価を作り出す。サンプリング法は、他のデー
タベース評価法に勝る利点があることが証明された。パ
ラメータ法と違って、サンプリング法は、データの適合
について仮定がより少なく行われるべきことを要する。
さらに、サンプリング法は、常に、統計的確実性と呼ば
れる正確さの確実性を有する。たいていのサンプリング
法の統計的確実性は、典型的に、９０％乃至９９％の範
囲になるのを目指している。

【０００８】サンプリング法もパラメータ法もデータベ
ース評価には好適ではない。しかしながら、サンプリン
グ法は、データベースのデータアイテムが偏っている場
合、パラメータ法より正確な結果を提供することができ
る。例えば、上記に説明したデータベースが同型でない
（同型でないデータベースとは、データベース内のデー
タアイテムが異なるタイプからなる同等でない混合にな
っているデータベースである）場合、パラメータ法は良
好な性能を示すことができない。他のタイプより１つの
タイプのデータアイテムがかなり多い（例えば２０％以
上）場合、データベースは偏っているといわれる。偏っ
たデータベースは、パラメータ法やサンプリング法を実
行する場合に問題があることがわかっている。

【０００９】サンプルが多くの偏ったデータアイテムを
含んでいるかまたはあまり偏っていないデータアイテム
を含んでいるかに依存して、偏ったデータの影響は、サ
ンプリング法の結果に劇的に影響を与えることがある。
サンプリング法を使用する場合、偏ったデータの影響を
考慮することができない大量のサンプルがテーブルＴ及
びテーブルＲからとられる。したがって、偏ったデータ
を考慮してサンプリング法を実行するのは不具合があ
る。

【００１０】

【課題を解決するための手段】本発明は、データの偏り
の可能性に敏感な、データベース質問の評価方法を実行
する。データベース質問の総合評価は、３つの個別評価
を合わせて行われる。まず、評価は、稠密に両データベ
ースＲ及びＴを占める、特定の結合属性を有するデータ
アイテムについて行われる。次に、第１のデータベース
Ｒにある、特定の結合属性値を有する稠密なデータアイ
テムの影響を抑制する評価が行われ、最後に、第２のデ
ータベースＴにある、同じ結合属性値を有する稠密なデ
ータアイテムの影響を抑制する評価が行われる。

【００１１】本発明は、データベース質問の評価へ広範
囲にわたるアプローチをとっている。この広範囲にわた
るアプローチは、２つの異なるデータベースＲ及びＴの
データアイテムの関係を確立することによって作り出さ
れる。この関係は、サブ結合の収集からなる２つの部分
に分かれたグラフとして知られている。各サブ結合は、
この特定の結合属性値を有するデータアイテムの全ペア
からなる。

【００１２】各データベースのランダムなサンプルが収
集される（例えば、Ｒ^* 及びＴ^* は、それぞれデータベ
ースＲ及びＴのランダムなサンプルを示す）。次いで、
ランダムサンプルＲ^* 及びＴ^* におけるサブ結合は、特
定の結合属性値のデータアイテム数がスレショールド値
以上か以下かに基づいて、特定の結合属性値のデータア
イテムの稠密な母集団または特定の結合属性値のデータ
アイテムの疎な母集団を持つように評価される。本発明
の方法では、データアイテムは、その結合属性値が稠密
ならば稠密になり、その結合属性を有するデータアイテ
ムの母集団が疎ならば疎になることがわかる。スレショ
ールド値は、データベースのデータアイテム数の平方根
として定義される。サブ結合の各ペアのデータアイテム
が共に稠密な場合は、サブ結合は稠密−稠密と呼ばれ
る。サブ結合の各ペアにおいて、一方のデータアイテム
が疎なものとして類別され、他方のデータアイテムが稠
密または疎なものとして類別されている場合は、サブ結
合は、疎−何れか（例えば、稠密−疎、疎−稠密または
疎−疎）として類別される。

【００１３】次いで、一連の３つの評価がデータベース
で行われる。手順はまず、稠密−稠密評価（Ａ_d ）を決
定するためにランダムサンプルに適用される。次いで、
Ｒの結合属性値を有する稠密データアイテムを抑制する
疎−何れか（Ａ_S1）評価が行われ、次に、Ｔの結合属性
値を有する稠密データアイテムを抑制する疎−何れか
（Ａ_S2）評価が行われる。最後に、稠密−稠密評価と、
Ｒの稠密データアイテムを抑制する疎−何れか評価と、
Ｔの稠密データアイテムを抑制する疎−何れか評価とを
結合することによって、データベース質問評価（Ａ）が
作られる。

【００１４】稠密−稠密評価と疎−何れか評価は、特定
のデータベース質問に対して、他のランダムサンプル
（例えばＴ^* ）と適合する可能性のある一方のランダム
サンプル（例えばＲ^* ）における結合属性値を有するデ
ータアイテムを評価することにより行われる。上述のよ
うに、特定の結合属性値を有するデータアイテムの適合
はこの方法ではサブ結合と呼ばれる。したがって、各結
合属性値に関して、その値と関連したサブ結合のサイズ
が評価される。次いで、サブ結合の評価の和が全ての結
合属性値に関して加算され、これらの和（例えば、稠密
−稠密評価、疎−何れか評価）は組み合わさってデータ
ベース質問評価を作り出す。

【００１５】本発明の目的、利点及び新規な特徴は、添
付図面に関して読まれる以下の詳細な説明からより十分
に明らかになるだろう。

【００１６】

【発明の実施の形態】本発明では、等結合データベース
質問サイズの評価方法が実行される。まず、質問基準が
定義される。各データベースからのデータアイテムは質
問基準にしたがってグループ分けされる。次いで、“稠
密−稠密”手順及び“疎−何れか”として知られる評価
手順が、定義されたグループの各々に適用され、データ
ベースの全体評価を決定する。

【００１７】詳細には、この方法は、２つのデータベー
スの稠密−稠密評価（Ａ_d ）を行なうことによってデー
タベースＲ及びＴの等結合評価（Ａ）を行なう。次い
で、Ｒの稠密なデータアイテムを抑制する疎−何れか手
順が行われ、第１の疎−何れか評価（Ａ_S1）を作り出
す。次いで、Ｔの稠密なデータアイテムを抑制する疎−
何れか手順が行われ、第２の疎−何れか評価（Ａ_S2）を
作り出す。最後に、Ａ_d ，Ａ_S1及びＡ_S2を組み合わせる
（加算する）ことによって、２つのデータベースの等結
合評価（Ａ）が計算される。

【００１８】本発明の方法を示す手段として、図１は、
説明を容易にするために用いることができる概念的モデ
ルを表わしている。図１において、１００で示された第
１のデータベース（Ｒ）及び２００で示された第２のデ
ータベース（Ｔ）が示されている。第１のデータベース
Ｒ及び第２のデータベースＴは共に、異なる結合属性値
（例えば、それぞれ１０１，１０２，１０３及び２０
１，２０２，２０３）を有する多数のデータアイテムを
有している。また、２つのデータベースサンプルが示さ
れている。第１のランダムサンプル（Ｒ^* ）は１５０で
示され、第２のランダムサンプル（Ｔ^* ）は２５０で示
されている。両ランダムサンプル１５０及び２５０は、
原データベースＲ及びＴからのデータアイテムのランダ
ムサンプリングを含んでいるだろう。したがって、１５
０で示された第１のランダムサンプル（Ｒ^* ）はデータ
アイテム１０１，１０２及び１０３を含み、２５０で示
された第２のランダムサンプル（Ｔ^* ）はデータアイテ
ム２０１，２０２及び２０３を含む。

【００１９】図１に表わされた概念的モデルの直観的な
理解を発展させるために、データベースＲのデータアイ
テムは、好きなスポーツを持っている男性の母集団を表
わすと仮定する（好きなスポーツは結合属性値となるだ
ろう）。したがって、データアイテム１０１，１０２及
び１０３は各々、特定のスポーツが好きな特定の男性を
表わす。次に、データベースＴは、好きなスポーツを持
っている女性の母集団を表わすと仮定する。したがっ
て、各データアイテム２０１，２０２及び２０３は、特
定のスポーツが好きな女性の男性を表わす。さらに、簡
単にするために、安静または女性の各々が好きなスポー
ツ（結合属性値）は、ベースボール、フットボールまた
はホッケーのどれかであると仮定する。したがって、デ
ータベースＲは、好きなスポーツがベースボール、フッ
トボールまたはホッケーである男性の母集団を表わし、
データベースＴは、好きなスポーツがベースボール、フ
ットボールまたはホッケーである女性の母集団を表わ
す。

【００２０】データベースＲ及びＴの可能な質問（等結
合）は、（１）ベースボールが好きな男性と女性、
（２）フットボールが好きな男性と女性、（３）ホッケ
ーが好きな男性と女性に適合することができる。このタ
イプの質問は、評価技術なしに行われる場合は３ステッ
プで達成することができる。まず、データベースＲは、
好きなスポーツがベースボールである全男性についてサ
ーチされるだろう。次に、データベースＴは、好きなス
ポーツがベースボールである全女性についてサーチされ
るだろう。最後に、好きなスポーツがベースボール（フ
ットボール及びホッケー）である男性と女性の好一対が
作られる。データベースＲ及びＴが共にｎデータアイテ
ムを含んでいる場合、好きなスポーツが同じである男生
と女性を組み合わせるのはｎ² の作業になる。

【００２１】本発明の方法論では、ランダムサンプルＲ
^* 及びＴ^* は、それぞれデータベース（Ｒ）及び（Ｔ）
から取られる。次いで、サンプルは結合属性値で類別さ
れる。結合属性値でデータアイテムを類別するために、
好きなスポーツは各々、それと関連する番号（例えば、
ベースボール“１”、フットボール“２”及びホッケー
“３”）を持っていると仮定する。そこで、特定のスポ
ーツが好きな男性と女性の好一対は、図１の２つの部分
に分かれたグラフで表わすことができる。図１Ｂにおい
て、図１ＡのランダムサンプルＲ^* 及びＴ^* からの各デ
ータアイテムは、その上に好きなスポーツの番号を伴っ
て示されている。例えば、データアイテム１０１は、
（データアイテム１０１上の数字が１なので）ベースボ
ールが好きな、ランダムサンプルＲ^* からの男性であ
る。図１Ｂのデータアイテム２０１はランダムサンプル
Ｔ^* からのデータアイテムである。したがって、図１Ｂ
のデータアイテム２０１は、（その上に２があるので）
フットボールが好きな女性である。

【００２２】そこで、特定のスポーツが好きな男性と女
性をペアにして、２つに別れたグラフとして表わすこと
ができ、このグラフには、各男性及び女性を表わすノー
ドと、男性と女性が好きなスポーツが同じ場合の、男性
を表わすノードと女性を表わすノード間の線（データア
イテム間に引かれた線）とがある。図１Ｂにおいて、デ
ータアイテム１０１，１０２及び１０３は、（それぞ
れ、１，３及び２で表わされるスポーツが好きな）３人
の男性の記録を表わし、データアイテム２０１，２０２
及び２０３は、（それぞれ、２，１及び２で表わされる
スポーツが好きな）３人の女性の記録を表わす。３０
２，３０４，３０６で示された線は、１０３で示された
男性（ベースボールが好きな男性）を（ベースボールが
好きな）３人の女性とペアにする。

【００２３】一般に、各結合属性値（例えば、ベースボ
ール、フットボール、ホッケー）について、この属性値
（例えば１，２，３）を有する男性の各々を同じ属性値
（例えば１，２，３）を有する女性とペアにする線があ
る。ある特定の結合属性値のデータアイテムと線を１組
にして、サブ結合として示されている。正確には、各結
合属性値（例えば１で示されたベースボール、２で示さ
れたフットボール及び３で示されたホッケー）に対して
１つのサブ結合がある。例えば、ベースボールが好きな
男性と女性のサブ結合は、データアイテム１０３，１０
４と、線３０２，３０３，３０４，３０５，３０６，３
０７と、データアイテム２０１，２０３及び２０４とか
らなるだろう。

【００２４】個々のデータベースのスレショールド値を
用いて、本発明は、稠密−稠密及び疎−何れか（すなわ
ち、稠密−疎、疎−稠密及び疎−疎）のような関係を定
義する。スレショールド値は、ランダムサンプルを稠密
なデータタイプの母集団の表現にすることが可能などん
な値でも良いことがわかる。この関係は次のように定義
される。

【００２５】稠密−稠密−データベース（Ｒ）における
ある結合属性値を有するデータアイテムの数とデータベ
ース（Ｔ）における同じ結合属性値を有するデータアイ
テムの数が各々、平方根（ｎ）より大きいかまたは等し
い関係。ここで、ｎはデータベースのデータアイテム数
である。

【００２６】稠密−疎−データベース（Ｒ）におけるあ
る結合属性値を有するデータアイテムの数が平方根
（ｎ）より大きいかまたは等しく、かつデータベース
（Ｔ）におけるデータアイテムの数が平方根（ｎ）より
小さい関係。ここで、ｎは各データベースのデータアイ
テム数である。

【００２７】疎−稠密−データベース（Ｒ）における特
定の結合属性値を有するデータアイテムの数が平方根
（ｎ）より小さく、かつデータベース（Ｔ）におけるデ
ータアイテムの数が平方根（ｎ）より大きいかまたは等
しい関係。ここで、ｎは各データベースのデータアイテ
ム数である。

【００２８】疎−疎−データベース（Ｒ）及びデータベ
ース（Ｔ）における特定の結合属性値を有するデータア
イテムの数が平方根（ｎ）より小さい関係。ここで、ｎ
は各データベースのデータアイテム数である。

【００２９】本発明の方法論では、ある結合属性値ｖを
有する１組のデータアイテムについて、“ｍｕｌｔ_T
（ｖ）”は、その結合属性値を有するＴにおけるデータ
アイテムの数と定義される。Ｒにおいて、“ｍｕｌｔ_R
（ｖ）”がｎの平方根より大きいかまたは等しければ、
結合属性値は稠密であると定義され、また、“ｍｕｌｔ
_R （ｖ）”がｎの平方根より小さければ、結合属性値が
疎であると定義される。さらに、サブ結合（ｖ）は、ｖ
がＲ及びＴの両方で稠密ならば、稠密−稠密サブ結合と
なる。サブ結合（ｖ）は、ｖがＲ及びＴの両方で疎なら
ば、疎−疎サブ結合となる。

【００３０】本発明の方法論では、ｎは各関係における
データアイテム数であり、ｍ₁ は稠密−稠密手順のサン
プルサイズであり、Ｍ₂ は疎−何れか手順のサンプルサ
イズであり、δは稠密−稠密手順で使用されるスレショ
ールド値である。上記に定義された変数を仮定すれば、
各評価は次のように定義することができる。

【００３１】Ａ_d ：＝ｆ_d （ｎ，ｍ₁ ，δ） Ａ_s1：＝ｆ_s （Ｒ，Ｔ，ｎ，ｍ₂ ） Ａ_s2：＝ｆ_s （Ｔ，Ｒ，ｎ，ｍ₂ ） Ａ：＝Ａ_d ＋Ａ_s1＋Ａ_s2

【００３２】ここで、ｆ_d （ｘ）及びｆ_s （ｘ）はｘの
関数であり、Ａは総合データベース評価であり、Ａ_d は
稠密−稠密データベース評価であり、Ａ_s1は、Ｒの稠密
なデータアイテムを抑制する疎−何れかデータベース評
価であり、Ａ_s2はＴの稠密なデータアイテムを抑制する
疎−何れか評価である。Ａ＜ｎｌｏｇｎならば、この方
法は、質問サイズの上限である健全な限界（Ｓ）：＝ｎ
ｌｏｇｎも提供する。開示された実施例では、ｍ１＝
（平方根（ｎ）＋ｌｏｇｎ）＊ｌｏｇｎ，ｍ₂ ＝平方根
（ｎ）＋ｌｏｇｎ、δ＝ｌｏｇｎとなる。

【００３３】本発明では、各データベースのランダムサ
ンプルがとられる。２つのデータベースからとられたラ
ンダムサンプルはほとんどｍ₁ ＋ｍ₂ であり、ｍ₁ は、
稠密−稠密評価を行なう場合に（個別的に）Ｒ及びＴか
らサンプリングされたデータアイテム数であり、ｍ₂
は、疎−何れか評価を行なう場合に（個別的に）Ｒ及び
Ｔからサンプリングされたデータアイテム数である。サ
ンプルがとられると、稠密−稠密評価（Ａ_d ）が引き出
され、Ｒの稠密なデータアイテムを抑制する疎−何れか
評価（Ａ_s1）が計算され、Ｔの稠密なデータアイテムを
抑制する疎−何れか評価（Ａ_s2）が計算される。最後
に、Ａ_d ，Ａ_s1及びＡ_s2を結合することにより、質問サ
イズの評価を行なうことができる。

【００３４】稠密−稠密 この方法論、稠密−稠密手順の第１のステップは、以下
のステップを含む。 １．データベースＲ及びＴからランダムサンプルＲ^* 及
びＴ^* がとられる。ランダムサンプルＲ^* 及びＴ^* は各
々サイズｍ₁ からなる。 ２．Ｖ^* はＲ^* 及びＴ^* の両方におけるデータアイテム
の１組の結合属性値とする。 ３．各値ｖ∈Ｖ^* について、ｍｕｌｔ_R*（ｖ）を決定す
る。 ４．各値ｖ∈Ｖ^* について、ｍｕｌｔ_T*（ｖ）を決定す
る。 ５．各値ｖ∈Ｖ^* について、ｍｕｌｔ_R*（ｖ）≧δかつ
ｍｕｌｔ_T*（ｖ）≧δならば、Ａ’：＝Ａ’＋ｍｕｌｔ
_R*（ｖ）＊ｍｕｌｔ_T*（ｖ）となる。ここで、Ａ’は中
間の稠密−稠密評価（Ａ’は初期にゼロに設定される）
であり、“＊”は乗算を示すために使用される記号であ
る。 ６．稠密−稠密評価Ａｄ：＝（ｎ／ｍ₁ ）² ＊Ａ’とな
る。

【００３５】疎−何れか 疎−何れか評価を作り出す方法は以下の手順からなる。 １．データベースＴからランダムサンプルＴ^* がとられ
る。ランダムサンプルＴ^* はサイズｍ₂ からなる。 ２．ｍｕｌｔ_R*（ｖ）が稠密ｖについて多数の計算を必
要とするならば、稠密ｖを抑制するために蓋然論的消去
を使用する。 ２ａ．データベースＲからランダムサンプルＲ^* がとら
れる。ランダムサンプルＲ^* はサイズｍ₂ からなる。 ２ｂ．Ｒ^* に表われる各結合属性値について、Ｔ^* から
結合属性値ｖを有する全てのデータアイテムを削除す
る。 ３．Ｒにおいて疎である残りの結合属性値に基づいて中
間の疎−何れか評価を計算する。 Ｔ^* における各データアイテムｙについて、 ３ａ．ｙと結合する、すなわちｙと同じ結合属性値を有
する、Ｒのデータアイテムの番号ｘを決定する。 ３ｂ．ｘ＜ｎ／ｍ₂ ならば、Ａ’：＝Ａ’＋ｘとなる。
ここで、Ａ’は中間の疎−何れか評価である（Ａ’は初
期にゼロに設定される）。 ４．Ａ_s ：＝ｎＡ’／ｍ₂ となる。ここで、Ａ_s は疎−
何れか評価である。

【００３６】本発明の方法論では、疎−何れか評価は２
度行なわれる。疎−何れか手順が２回行なわれ、１回目
に使用されなかったデータベースの稠密なデータアイテ
ムが抑制される。例えば、データベースＲの稠密なデー
タアイテムが抑制されたならば、１回目に疎−何れか手
順が行なわれ、２回目にデータベースＴの稠密なデータ
アイテムが抑制されるだろう。１回目に疎−何れか評価
が行なわれると、その評価はＡ_s1で示され、２回目に
（ＲとＴの役割が反対にされて）疎−何れか評価が行な
われると、その評価はＡ_s2で示される。稠密−稠密及び
疎−何れかの評価の全てが計算されると、等結合評価
は、Ａ＝Ａ_d ＋Ａ_s1＋Ａ_s2で示される。Ａ＜（ｎ）ｌｏ
ｇ（ｎ）ならば、健全な限界Ｓ＝（ｎ）ｌｏｇ（ｎ）の
出力を計算することができる。ここで、Ｓは健全な限界
である。すなわち、ハットは評価の統計的確信を維持す
る。さらに、等結合評価を計算するために、稠密−稠密
評価、第１の疎−何れか評価及び第２の疎−何れか評価
を追加するべく、等結合評価は、３つの評価を平均する
かまたは３つの評価の最大をとることにより近似するこ
ともできることがわかる。

【００３７】さらに、本発明の方法論は、どんな数のデ
ータベースにも適用することができる。例えば、３つの
データベースＡ，Ｂ及びＣが含まれている場合は、この
方法論は、まずデータベースＡ及びＢに適用して中間の
評価を作り出し、次いで、この方法論をＣに用いて中間
評価を結合することができる。

【００３８】また、本発明は、データベース質問の正確
で費用のかからない評価を作り出すために適用すること
ができる。この方法は、質問最適化装置に、または並列
もしくは分散データベースの多数のプロセッサにおける
仕事量のバランスを取るのに必要なリソース割当ての決
定時に有効である。さらに、より広範囲の規模に、開示
されたこの方法を、会計監査や統計的研究等の大容量デ
ータベースアプリケーションにも適用することができ
る。

【００３９】本発明のいくつかの実施例が開示されて説
明されているが、本発明の精神または従属請求項の範囲
から逸脱することなく種々の変更を行なうことができる
ことがわかる。

【図面の簡単な説明】

【図１Ａ】母集団Ｒ及びＴとランダムサンプルＲ^* 及び
Ｔ^* の概念図を示す。

【図１Ｂ】ランダムサンプルＲ^* 及びＴ^* の選択された
データアイテムと、結合属性値２のサブ結合の２つの部
分に分かれたグラフを示す。

フロントページの続き (72)発明者 フィリップ ビー．ギボンズ アメリカ合衆国 07090 ニュージャーシ ィ，ウエストフィールド，エンブリー コ ート 201 (72)発明者 ヨッシ マティアス アメリカ合衆国 20854 メリーランド, ポタマック，ロザリンダ ドライヴ 11815 (72)発明者 アブラハム シルバーシャッツ アメリカ合衆国 07901 ニュージャーシ ィ，サミット，ニューイングランド アヴ ェニュー 67エー

Claims (13)

【特許請求の範囲】
1. 【請求項１】 少なくとも２つのデータベースＲ及びＴ
   の等結合を評価することによりデータを管理する方法で
   あって、 Ｒの稠密なデータアイテムとＴの稠密なデータアイテム
   の質問サイズを評価することにより、稠密−稠密評価を
   作り出す工程と、 Ｒの稠密なデータアイテムを抑制する質問サイズを評価
   することにより、第１の疎−何れか評価を作り出す工程
   と、 Ｔの稠密なデータアイテムを抑制する質問サイズを評価
   することにより、第２の疎−何れか評価を作り出す工程
   と、 前記稠密−稠密評価と、前記第１の疎−何れか評価と、
   前記第２の疎−何れか評価を結合することにより、デー
   タベースＲ及びＴの等結合のサイズの評価を作り出す工
   程とからなる方法。
2. 【請求項２】 請求項１記載の方法において、前記結合
   工程は、前記稠密−稠密評価と、前記第１の疎−何れか
   評価と、前記第２の疎−何れか評価を加算することによ
   り行われる方法。
3. 【請求項３】 請求項１記載の方法において、前記結合
   工程は、前記稠密−稠密評価と、前記第１の疎−何れか
   評価と、前記第２の疎−何れか評価を平均することによ
   り行われる方法。
4. 【請求項４】 請求項１記載の方法において、前記結合
   工程は、前記稠密−稠密評価と、前記第１の疎−何れか
   評価と、前記第２の疎−何れか評価のうちの１つを最大
   値として選択することにより行われる方法。
5. 【請求項５】 少なくとも２つのデータベースＲ及びＴ
   のデータベース質問サイズを評価することによりデータ
   を管理する方法であって、 データべースＲにおけるある属性値を有する稠密なデー
   タアイテムと前記属性値を有するＴの稠密なデータアイ
   テムとの評価を行なうことにより、稠密−稠密評価を作
   り出す工程と、 前記データベースＲの稠密なデータアイテムを抑制する
   評価を行なうことにより、Ｒにおける疎−何れか評価を
   作り出す工程と、 Ｔの稠密なデータアイテムを抑制する評価を行なうこと
   により、Ｔにおける疎−何れか評価を作り出す工程と、 前記稠密−稠密評価と、前記Ｔにおける疎−何れか評価
   と、前記Ｒにおける疎−何れか評価を結合することによ
   り、前記データベースＲ及び前記データベースＴのデー
   タベース質問サイズを評価する工程とからなる方法。
6. 【請求項６】 請求項５記載の方法において、前記稠密
   −稠密評価は、 前記データベースＲからデータアイテムをサンプリング
   することにより、サンプルＲ^* を作り出し、 前記データベースＴからデータアイテムをサンプリング
   することにより、サンプルＴ^* を作り出し、 前記サンプルＲ^* におけるある結合属性値（ｖ）を有す
   る多数のデータアイテムを決定することにより、Ｒにお
   いて多数の前記結合属性値（ｖ）を作り出し、 前記サンプルＴ^* における前記結合属性値（ｖ）を有す
   る多数のデータアイテムを決定することにより、Ｔにお
   いて多数の前記結合属性値（ｖ）を作り出し、 前記結合属性値（ｖ）の各々に関して、前記結合属性値
   （ｖ）のサブ結合のサイズの中間の稠密−稠密評価を決
   定し、 前記結合属性値（ｖ）の各々に関して中間の稠密−稠密
   評価を加算し、 前記サブ結合属性値（ｖ）の前記サイズの中間の稠密−
   稠密評価を見積もることにより行なわれる方法。
7. 【請求項７】 請求項６記載の方法において、前記中間
   の稠密−稠密評価は、スレショールド値を確定し、Ｔに
   おける多数の前記結合属性値（ｖ）及びＲにおける多数
   の前記結合属性値（ｖ）を前記スレショールド値と比較
   した後に得られる方法。
8. 【請求項８】 請求項７記載の方法において、前記中間
   の稠密−稠密評価は、Ｔ^* における多数の前記結合属性
   値（ｖ）及びＲ^* における多数の前記結合属性値（ｖ）
   が共に前記スレショールド以上であることを決定した後
   に得られる方法。
9. 【請求項９】 請求項７記載の方法において、前記中間
   の稠密−稠密評価は、Ｔ^* における多数の前記結合属性
   値（ｖ）及びＲ^* における多数の前記結合属性値（ｖ）
   が共に前記スレショールドに等しいことを決定した後に
   得られる方法。
10. 【請求項１０】 請求項５記載の方法において、前記第
    １の疎−何れか評価は、 前記データベースＴからデータアイテムをサンプリング
    することにより、サンプルＴ^* を作り出し、 Ｒにおけるその数がスレショールド以上であるＴ^* のデ
    ータアイテムを抑制し、 前記結合属性値（ｖ）の各々について、Ｔにおいて疎で
    ある、前記結合属性値（ｖ）を有するデータアイテムに
    より中間の疎−何れか評価を計算し、 前記結合属性値（ｖ）の各々について中間の疎−何れか
    評価を加算し、 前記中間の疎−何れか評価を見積もることにより、Ｒに
    おけるＴの疎−何れか評価を作り出すことによって行な
    われる方法。
11. 【請求項１１】 請求項１０記載の方法において、Ｔ^*
    のデータアイテムを抑制する前記工程は、稠密な結合属
    性値（ｖ）を有する、Ｒにおける多数のデータアイテム
    を決定することによって行なわれる方法。
12. 【請求項１２】 請求項１０記載の方法において、Ｔ^*
    のデータアイテムを抑制する前記工程は、Ｒからランダ
    ムサンプルＲ^* をとり、Ｒ^* に表われる各結合属性値
    （ｖ）に関して、Ｔ^* から結合属性値（ｖ）を有する全
    てのデータアイテムを削除することにより行なわれる方
    法。
13. 【請求項１３】 請求項５記載の方法において、前記第
    ２の疎−何れか評価は、 前記データベースＲからデータアイテムをサンプリング
    することにより、サンプルＲ^* を作り出し、 前記結合属性値（ｖ）を有する、Ｒにおける多数のデー
    タアイテムを計算するコストを決定し、 Ｒ^* の各データアイテムについて、前記結合属性値
    （ｖ）を有するＴのデータアイテムの数を決定し、 前記結合属性値（ｖ）の各々について、Ｒにおいて疎で
    ある、前記結合属性値（ｖ）を有するデータアイテムに
    より中間の疎−何れか評価を計算し、 前記結合属性値（ｖ）の各々について中間の疎−何れか
    評価を加算し、 前記中間の疎−何れか評価を見積もる
    ことにより、ＴにおけるＲの疎−何れか評価を作り出す
    ことによって行なわれる方法。