JPH11353331A - デ―タベ―スの問合せに応答する方法 - Google Patents

Abstract

(57)【要約】 【課題】 データベース問合せに対して高速で高精度の
近似回答を提供する。 【解決手段】 データベースの問合せに応答して、近似
問合せエンジンのメモリ内の複数のデータサンプルを更
新する。データサンプルは、データベースに格納された
データよりも少ないスペースしか必要としない。次に、
問合せが、データベースでのデータの挿入か削除かを判
定する。問合せがデータ挿入の場合、各タプルごとに、
そのタプルの関係を判定し、所定の確率でその関係に関
連する一様ランダムサンプルにそのタプルを追加する。
実際に追加された場合、そのタプルを用いて新しい結合
データサンプルタプルを計算し、その新しい結合データ
サンプルタプルを、前記関係に関連する結合データサン
プルに追加する。一様ランダムサンプルがある最大サイ
ズを超えた場合、一様ランダムサンプル内のタプルのう
ちの１つをランダムに選択して削除する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データベース問合
せ（クエリ）システムに関し、特に、大規模データ記録
ウェアハウス環境における近似問合せ回答システムと、
問合せに対して近似回答を行う関連技術に関する。

【０００２】

【従来の技術】近似問合せ回答とは、データベースシス
テムへの問合せに対して、精度保証付きで（例えば、あ
る誤差範囲で）、推定される回答を行う技術および方法
を指すために用いられる用語である。このようなデータ
ベースシステムは、システムが問合せに応答するのに要
する時間を短縮することによってデータベースシステム
の問合せ応答パフォーマンスを改善するために使用する
ことが可能である。

【０００３】大規模なデータ記録ウェアハウス環境で
は、問合せに対して高速で近似的な回答を行うことが有
効であることが多い。その目標は、正確（厳密）な回答
を計算するのに要する時間よりも１桁短い時間で、推定
される応答を提供することである。これは、ベースデー
タへのアクセスを回避し、またはアクセス数を最小にし
て、ベースデータが利用不能のときでも近似回答を提供
することにより実現される。

【０００４】従来の問合せ処理は、応答時間を最小化し
スループットを最大化するようにして、問合せに対して
厳密回答を行うことのみに注目している。しかし、厳密
回答のための応答時間が、所望のものより遅い環境がい
くつかある。第１に、大規模データ記録ウェアハウス環
境では、複雑な問合せに対して厳密回答を行うことは、
必要なディスクＩ／Ｏの量のために、数分から数時間か
かることがある。テラバイト以上のデータのある環境で
は、データの１回のスキャンにも数十分かかることがあ
る。例えば、各ディスクから２０ＭＢ／ｓで一度に１０
０個のディスクからの並列読み出しを用いて３ＴＢのデ
ータをスキャンするのには２５分かかる。第２に、分散
データ記録ウェアハウス環境では、一部のデータがリモ
ートにあって応答時間が遅いことがあり、また、一部の
データが現在は利用可能でないためにデータが再び利用
可能になるまでは厳密回答は選択肢にならないことがあ
る。このような分散環境については、C. Faloutsos et
al., "Recovering information from summary data", P
roc. 23rd International Conf. on Very Large Data B
ases, pp.36-45, August 1997、に記載されている。最
後に、厳格な応答時間要求の環境では、特定レベルの記
憶階層における１回のアクセスでも、許容できないほど
遅いことがある。例えば、ミリ秒以下の応答時間の場
合、１回のディスクアクセスは遅すぎる。

【０００５】厳密回答を提供すると応答時間が好ましく
ないほど長くなってしまうような環境が、問合せに対し
て近似回答を提供する技術に関する我々の研究の動機で
ある。我々の目標の１つは、ベースデータへのアクセス
を回避し、またはアクセス数を最小にすることによっ
て、厳密回答を計算するのに要する時間より１桁短い時
間で、推定される応答を提供することである。

【０００６】厳密回答が要求されず、高速で近似的な回
答のほうが好まれるような状況はいくつもある。例え
ば、臨時のデータマイニングにおける絞り込み（ドリル
ダウン）問合せシーケンスの間、シーケンスのはじめの
ほうの問合せは、興味深い問合せは何かを判断するため
にのみ使用される（例えば、J. M. Hellerstein et a
l., "Online aggregation", Proc. ACM SIGMOD Interna
tional Conf. on Management of Data, pp.171-182, Ma
y 1997、参照）。近似回答は、問合せがどのくらい適切
にたてられたものであるかに関するフィードバックも与
える。さらに、近似回答は、ベースデータが利用可能で
ないときに問合せに対する仮の回答を提供することも可
能である。もう１つの例は、問合せが数値的回答を要求
し、厳密回答の高い精度が必要でない場合、例えば、総
計、平均、あるいは割合の最初の数桁の精度で十分な場
合（百万を単位とした総計の最初の数桁や、百分率の最
も近い整数部分のような）である。この場合を例示する
ため、地区ごと、および、各地区内の店鋪タイプごとに
グループ化された平均および最低の売上の集計値を問い
合わせる、売上データベースに対する標準ＳＱＬ(Struc
tured Query Language)のＧＲＯＵＰ ＢＹ問合せにつ
いて考える。表１は、このようなＧＲＯＵＰ ＢＹ要求
の結果得られる典型的な厳密回答である。この回答を得
るには、データベース内のあらゆるレコードを探索し、
平均および最低の売上値を計算する必要がある。このよ
うな演算に要する時間は、小規模のローカルデータベー
スの場合の数秒間から、大規模データウェアハウス環境
の数十分間までの範囲に及ぶ可能性がある。これに対し
て、近似回答は、推定値および精度を与える。

【０００７】

【表１】

【０００８】本発明の目標は、問合せに対して高速な近
似回答を提供することである。表２に、表１と同じＧＲ
ＯＵＰ ＢＹ問合せに対して、指定された信頼確率に基
づいて各推定値ごとに信頼区間として精度を与えた、近
似回答の例を示す。注意すべき点であるが、いくつかの
場合には、上限（健全性限界(sanity bound)という。）
が、平均および最低の売上で推定値の代わりに＜５００
として示されている。同じく注意すべき点であるが、近
似回答は、厳密回答では提供されない行（タプル）を含
むこと（この例では、「中部アウトレット」のグルー
プ）があり、その逆の場合もある。タプル（組）とは、
問合せに対する回答における単一の完全な行のことであ
り、例えば、票２の第１タプルは、（東部，リテール，
１２０００±８００，４１００±４００）である。同じ
く注意すべき点であるが、高速近似回答の技術は、問合
せオプティマイザにおける従来の役割として、プランコ
ストを推定するために用いることも可能である。このよ
うなアプリケーションは、非常に高速な応答時間を要求
するが、厳密回答は要求しないからである。

【０００９】

【表２】

【００１０】近似問合せ回答における最近の研究にもか
かわらず、現在の技術は速度、適用範囲および精度にお
いて極めて制限されていると考えられる。

【００１１】Hellerstein et al.は、オンライン集計(o
nline aggregation)という集計問合せの近似回答のため
のフレームワークを提案した。これは、ベースデータが
問合せ時にある順序でスキャンされ、集計問合せに対す
る近似回答がスキャンの進行とともに更新される（連続
的報告）というものである。集計問合せとは、データベ
ースタプルの列に対する述語および集計関数（例えば、
個数(count)、平均(average)、あるいは総計(sum)）を
指定するものである。厳密回答は、述語を満たすすべて
のタプルにわたり集計関数を適用した結果を返す。グラ
フィック表示が、スキャンの進行とともに、回答および
（減少する）信頼区間を図示し、ユーザは任意の時刻に
その進行を停止することができる。維持されるシノプシ
スは、データベース問合せのＧＲＯＵＰ ＢＹ演算にお
いて小さいセットの特殊な処理を可能にするインデック
ス（索引）のみである。シノプシスとは、基礎となるデ
ータベースの小さい、あらかじめ計算された要約データ
構造（サンプル、個数など）である。報告されるタプル
は問合せ時にベースデータから取得されるため（後
述）、応答時間は、本発明よりも数桁遅くなる。「問合
せ時間」は、問合せがなされたときから応答が生成され
るまでの時間である。グループのスキャン順序がランダ
ムである場合、精度保証付きのランダムに選択された確
定タプル（ランダム選択タプル）が報告される。確定タ
プルとは、厳密回答の場合のタプルである。さらに、す
べてのグループを考えると、必要に応じて、小さいセッ
トに偏ったバイアス付きで選択された確定タプル（バイ
アス選択タプル）が報告される。バイアス選択タプルと
は、特定の基準に従って偏った厳密回答で報告されるタ
プルである。ランダムなスキャン順序の欠点は、応答時
間がさらに遅くなることである。スキャン順序がディス
ク上のデータの順序である場合、応答時間はランダム順
序の場合より高速になるが、報告されるタプルは、発見
的精度（極めて精度が低い可能性もある）の任意の確定
タプルとなる。

【００１２】他のシステムは、限定されたオンライン集
計機能しかサポートしない。例えば、Red Brickシステ
ムは、現在（ランニング）の個数、平均、および総計し
かサポートしない。これらの集計を生成するのに用いら
れるスキャン順序はランダムではないため、発見的な精
度のみが可能であり、精度は極めて悪くなる可能性があ
る。タプルは問合せ時にベースデータから取得されるた
め、応答時間は遅い。しかし、維持すべきシノプシスが
ないため、更新時間に寄与するオーバーヘッドはなく、
また、シノプシスのためのフットプリントもない。「更
新時間」とは、データベースに変更が生じたときにシノ
プシスを最新のものに保つのに要する時間であり、「フ
ットプリント」とは、シノプシスを格納するのに要する
メモリのサイズである。

【００１３】最近のいくつかの研究に"fast-first"問合
せ処理に関するものがある。その目標は、問合せ回答の
いくつかのタプルをすばやく提供することである。Baya
rdoand Miranker, "Processing queries for first-few
answers", Proc. 5th International Conf. on Inform
ation and Knowledge Management, pp.45--52, Novembe
r 1996、には、最初の回答が生成されるまでの待ち時間
を最小にするために、パイプライン化されループがネス
トされた結合(join)を用いて問合せを最適化し実行する
技術が記載されている。結合は、データベース問合せに
対する回答を作成する際に、データベース内の相異なる
関係（テーブル）からの対象とする属性（例えば、個々
の部品番号に対する売上数のような特定のフィールドデ
ータ）のみをあるキーに基づいて結合して新たな関係に
おける回答を提供する場合に行われる。Oracle Rdbシス
テムは、fast-first問合せ処理を提供するために、複数
の問合せプランを同時に実行することをサポートする。
これらのシステムはいずれも、問合せ時にベースデータ
にアクセスすることによって、任意の代表的な確定タプ
ルを報告する。それらの代表的タプルには、サイズ評価
やその他のメタ情報は提供されない。シノプシスも維持
される必要がない。

【００１４】VrbskyとLiuによって開発され、S. V. Vrb
sky and J. W. S. Liu, "Approximate---a query proce
ssor that produces monotonically improving approxi
mateanswers", IEEE Trans. on Knowledge and Data En
gineering, 5(6):1056-1068, 1993、に記載されている
近似的問合せプロセッサでは、セットに値をとる（セッ
ト値）問合せに対する近似回答は、直積のサブセットで
ある厳密回答のスーパーセットである。セット値問合せ
とは、厳密回答としてタプルのセットを返すものであ
る。この問合せプロセッサの目標は、処理の進行ととも
にスーパーセットを縮小することによって、単調に改善
する近似回答を生成することである。ベースデータはい
くつかの小さいブロックとして格納され、属性の範囲に
従ってそれらのブロックを分類するさまざまにインデッ
クス付けられたクラス階層が構築される。この問合せプ
ロセッサは、さまざまなクラス階層を用いて、回答に関
連するブロックを反復的にフェッチし、回答に入ること
が確実なタプルを生成するとともに、回答を含む可能な
クラスを狭める。精度に対する限界は提供されず、サイ
ズ評価やその他のメタ情報もなく、代表的タプルは任意
の確定タプルである。他の関連する問合せプロセッサ
（上記のVrbsky and Liuの参考文献参照）も同様に、問
合せ時にベースデータに作用し、セット値問合せに対す
る近似回答を、厳密回答に収束するサブセットおよびス
ーパーセットとして定義する。

【００１５】表３に、従来の研究と本発明の一実施例
（本発明のＡｑｕａシステム。詳細は後述）の比較の要
約を示す。近似問合せエンジンに対して以下の５つの尺
度を用いてこれらのシステムを評価した。 （１）適用範囲：近似回答を提供することが可能な問合
せの範囲。 （２）応答時間：問合せに対して近似回答を提供するた
めの時間。 （３）精度：提供される回答の精度。 （４）更新時間：システムシノプシスを最新のものに保
つ際のオーバーヘッド。 （５）フットプリント：システムシノプシスに必要な記
憶領域。 もちろん、他のシステム（近似システム以外）はいずれ
も、近似問合せエンジンとして設計されたものではない
ので、この比較は不公平である。しかし、これは、本発
明のＡｑｕａシステム以前の近似問合せエンジンにおけ
る技術水準を反映している。

【００１６】

【表３】

【００１７】D. Barbara et al., "The New Jersey dat
a reduction report", Bulletin ofthe Technical Comm
ittee on Data Engineering, 20(4):3-45, 1997、に
は、近似問合せ回答を提供することを含むさまざまな目
的に使用可能なデータ簡約(data reduction)技術の調査
が記載されている。また、ここで、コンサイスサンプル
(concise sample)とカウンティングサンプル(counting
sample)という２つのサンプリングに基づくシノプシス
を紹介する。これらは、同じフットプリントで比較的大
きいサンプルを得ることが可能であり、ホットリスト問
合せに対する近似問合せ回答を改善するために使用可能
であって、P. B. Gibbons and Y. Matias,"New samplin
g-based summary statistics for improving approxima
te queryanswers", Technical Report, Bell Laborator
ies, Murray Hill, NJ, USA, November 1997、および、
P. B. Gibbons et al., "Aqua project white paper",
Technical Report, Bell Laboratories, Murray Hill,
NJ, USA, December 1997、に記載されている。「コンサ
イスサンプル」とは、そのサンプルに複数回現れる値が
１つの値およびカウントとして表されるような、データ
セットの一様ランダムサンプルである。「カウンティン
グサンプル」とは、コンサイスサンプルの変形で、その
サンプルに対してある値が選択された後、データウェア
ハウスに挿入されたその値のすべての出現を追跡するた
めに個数（カウント）が使用されるようなサンプルであ
る。Olken and Rotem, "Maintenance of materialized
viewsof sampling queries", Proc. 8th IEEE Internat
ional Conf. on Data Engineering, pp.632-641, Febru
ary 1992、には、ランダムサンプルのビューを管理する
技術が記載されている。また、 ・Y. Matias et al., "Dynamic generation of discret
e random variates",Proc. 4th ACM-SIAM Symp. on Dis
crete Algorithms, pp.361-370, January 1993 ・Y. Matias et al., "Approximate data structures w
ith applications", Proc. 5th ACM-SIAM Symp. on Dis
crete Algorithms, pp.187-194, January 1994 ・Y. Matias et al., "Performance evaluation of app
roximate priority queues", DIMACS Fifth Implementa
tion Challenge; Priority Queues, Dictionaries, and
Point Sets, October 1996 には、高速な近似回答を提供する近似データ構造が提案
され研究されている。例えば、優先待ち行列データ構造
は、ＩＮＳＥＲＴ、ＦＩＮＤＭＩＮ、およびＤＥＬＥＴ
ＥＭＩＮという演算をサポートする。近似優先待ち行列
は、これらの演算をより少ないオーバーヘッドでサポー
トするとともに、ＦＩＮＤＭＩＮおよびＤＥＬＥＴＥＭ
ＩＮの演算に応じて近似的なＭＩＮ（最小値）を報告す
る。これらのデータ構造は線形スペースのフットプリン
トを有する。

【００１８】近似シノプシスの増分管理(incremental m
aintenance)に関するその他の研究には、 ・P. Flajolet and G. N. Martin, "Probabilistic cou
nting", Proc. 24th IEEE Symp. on Foundations of Co
mputer Science, pp.76-82, October 1983 ・P. Flajolet and G. N. Martin, "Probabilistic cou
nting algorithms fordata base applications", J. Co
mputer and System Sciences, 31:182-209, 1985 ・K.-Y. Whang, B. T. Vander-Zanden, and H. M. Tayl
or, "A linear-time probabilistic counting algorith
m for database applications", ACM Transactions on
Database Systems, 15(2):208-229, 1990 ・P. J. Haas, J. F. Naughton, S. Seshadri, and L.
Stokes, "Sampling-based estimation of the number o
f distinct values of an attribute", Proc.21st Inte
rnational Conf. on Very Large Data Bases, pp.311-3
22, September1995 ・N. Alon, Y. Matias, and M. Szegedi, "The space c
omplexity of approximating the frequency moments",
Proc. 28th ACM Symp. on the Theory of Computing,
pp.20-29, May 1996 ・P. B. Gibbons, Y. Matias, and V. Poosala, "Fast
incremental maintenance of approximate histogram
s", Proc. 23rd International Conf. on Very Large D
ata Bases, pp.466-475, August 1997 ・V. Ganti and V. Poosala, "Space-efficient approx
imation of the datacube", Technical report, Bell L
aboratories, Murray Hill, New Jersey, USA, Novembe
r 1997 がある。最後に、問合せオプティマイザ内で使用するた
めのサンプリングに基づく推定アルゴリズムに関する以
下のような多くの研究がある。 ・W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja, "Stat
istical estimators for relational algebra expressi
ons", Proc. 7th ACM Symp. on Principles ofDatabase
Systems, pp.276-287, March 1988 ・W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja, "Proc
essing aggregate relational queries with hard time
constraints", Proc. ACM SIGMOD International Con
f. on Management of Data, pp.68-77, June 1989 ・R. J. Lipton and J. F. Naughton, "Estimating the
size of generalizedtransitive closures", Proc. 15
th International Conf. on Very Large DataBases, p
p.165-172, August 1989 ・R. J. Lipton and J. F. Naughton, "Query size est
imation by adaptivesampling", Proc. 9th ACM Symp.
on Principles of Database Systems, pp.40-46, April
1990 ・R. J. Lipton, J. F. Naughton, and D. A. Schneide
r, "Practical selectivity estimation through adapt
ive sampling", Proc. ACM SIGMOD International Con
f. on Management of Data, pp.1-12, May 1990 ・W.-C. Hou, G. Ozsoyoglu, and E. Dogdu, "Error-co
nstrained COUNT query evaluation in relational dat
abases", Proc. ACM SIGMOD International Conf. on M
anagement of Data, pp.278-287, May 1991 ・P. J. Haas and A. N. Swami, "Sequential sampling
procedures for query size estimation", Proc. ACM
SIGMOD International Conf. on Management of Data,
pp.1-11, June 1992 ・Y. Ling and W. Sun, "A supplement to sampling-ba
sed methods for query size estimation in a databas
e system", SIGMOD Record, 21(4):12-15, 1992 ・R. J. Lipton, J. F. Naughton, D. A. Schneider, a
nd S. Seshadri, "Efficient sampling strategies for
relational database operations", Theoretical Comp
uter Science, 116(1-2):195-226, 1993 ・P. J. Haas, J. F. Naughton, S. Seshadri, and A.
N. Swami, "Fixed-precision estimation of join sele
ctivity", Proc. 12th ACM Symp. on Principles of Da
tabase Systems, pp.190-201, May 1993 ・P. J. Haas, J. F. Naughton, and A. N. Swami, "On
the relative cost of sampling for join selectivit
y estimation", Proc. 13th ACM Symp. on Principles
of Database Systems, pp.14-24, May 1994 ・R. J. Lipton and J. F. Naughton, "Query size est
imation by adaptivesampling", J. Computer and Syst
em Sciences, 51(1):18-25, 1995 ・P. J. Haas, J. F. Naughton, S. Seshadri, and L.
Stokes, "Sampling-based estimation of the number o
f distinct values of an attribute", Proc.21st Inte
rnational Conf. on Very Large Data Bases, pp.311-3
22, September1995 ・S. Ganguly, P. B. Gibbons, Y. Matias, and A. Sil
berschatz, "Bifocalsampling for skew-resistant joi
n size estimation", Proc. 1996 ACM SIGMODInternati
onal Conf. on Management of Data, pp.271-281, June
1996

【００１９】これらの従来の研究のいずれにも、本発明
の新規技術を使用しているものはない。

【００２０】

【発明が解決しようとする課題】従って、データベース
における関係ごとにあらかじめ計算された結合結果のサ
ンプル（「結合サンプル」という。）を維持することに
よって、（１）結合サンプルに基づく結合問合せに対し
て、および、（２）あらかじめ計算されたグループ項目
のバイアス付きサンプルに基づくＧＲＯＵＰ ＢＹ問合
せに対して、高速な近似回答を提供するシステムおよび
新しい技術が必要とされている。

【００２１】

【課題を解決するための手段】従来の近似問合せ回答シ
ステムの問題点および欠点は、本発明の原理および本発
明による近似問合せ回答（ＡＱＵＡ：Approximate QUer
y Answering）システムの開発によって克服される。Ａ
ＱＵＡは、広範なクラスの集計およびセット値問合せに
対して高速で高精度の近似回答を提供するように設計さ
れた最初のシステムであると思われる。このシステム
は、一般に問合せ時のディスクアクセスを回避すること
によって、従来のシステムよりも数桁短い応答時間で近
似回答を提供する。これは、以下のようにして実現され
る。 （１）データに関するいくつかのシノプシスを保持す
る。 （２）主に新規データがデータウェアハウスにロードさ
れるのを観測することによってそれらのシノプシスを更
新する。 （３）離散的報告（利用可能なすべてのシノプシスから
決定される単一の近似回答）を提供する。 （４）データ分布、データベースがロードされている順
序、あるいはディスク上のデータの物理的配置に関する
いかなる事前の仮定もせずに精度保証を提供する。 （５）問合せに応答するために頻繁に更新もしくは使用
またはその両方がなされるシノプシスをメモリ常駐にす
ることによりデータウェアハウスよりも数桁小さいフッ
トプリントを有する。 現在、このシステムは、ＳＥＬＥＣＴ（選択）、ＡＧＧ
ＲＥＧＡＴＥ（集計）、ＧＲＯＵＰ ＢＹ、あるいはＪ
ＯＩＮ（結合）（特に、オンライン分析処理（ＯＬＡ
Ｐ）でよく知られているマルチウェイ外部キー結合）を
有する問合せに対して高速な近似回答を提供する。

【００２２】本発明のシステムは、新規データがデータ
ウェアハウスにロードされるのを観測し、小さいシノプ
シスデータ構造（サンプル、カウントなど）を管理する
近似問合せエンジンを提供する。これらのシノプシスデ
ータ構造を用いて、問合せ時にデータベースにアクセス
することなく、問合せに対する高速な近似回答を提供す
ることができる。

【００２３】本発明のシステムは、いくつかの新しい技
術を用いて、このクラスの問合せに対する近似問合せ回
答の精度を改善する。第１に、本発明のシステムは、結
合サンプリングを用いて、近似品質を大幅に改善する。
結合サンプリングとは、非巡回データウェアハウススキ
ーマにおいて、外部キー結合の確率的サンプリングを用
いて、個々の基底関係ごとに単一の結合サンプルを作成
し管理することである。第２に、本発明のシステムは、
バイアス付きサンプリングを用いて、ＧＲＯＵＰ ＢＹ
演算における小さいグループの問題を克服する。バイア
ス付きサンプリング(biased sampling)とは、データベ
ースのＧＲＯＵＰ ＢＹ演算の結果として得られるグル
ープによりサンプルにバイアス（偏り）をつけることに
よって、グループのテーブルを作成し管理することであ
る。最後に、本発明のシステムは、システムで用いられ
る結合サンプル、バイアス付きサンプル、およびその他
のすべてのシノプシスの増分管理のための効率的なアル
ゴリズムを使用する。増分管理とは、データの挿入およ
び削除のようなデータベースへの更新を反映するように
シノプシスを更新することである。

【００２４】本発明の一実施例は、コンピュータ実行可
能な命令を有するコンピュータ読み取り可能な媒体とし
て実現される。コンピュータ実行可能な命令は、データ
ベースの問合せに応答して、近似問合せエンジンのメモ
リ内の複数のデータサンプルを更新する。データサンプ
ルは、データベースに格納されたデータよりも少ないス
ペースしか必要としない。さらに、コンピュータ実行可
能な命令は、問合せが、データベースにデータを挿入す
るものか、それとも、データベースからデータを削除す
るものかを判定する。問合せがデータを挿入するもので
ある場合、各タプルごとに、（ａ）そのタプルのデータ
ベース関係を判定し、（ｂ）所定の確率に基づいてその
関係に関連する一様ランダムサンプルにそのタプルを追
加し、（ｃ）そのタプルが一様ランダムサンプルに追加
された場合、（ｉ）そのタプルを用いて新しい結合デー
タサンプルタプルを計算し、（ｉｉ）その新しい結合デ
ータサンプルタプルを、前記関係に関連する結合データ
サンプルに追加し、（ｉｉｉ）一様ランダムサンプルが
ある最大サイズを超えた場合、（１）一様ランダムサン
プル内のタプルのうちの１つをランダムに選択し、
（２）ランダムに選択されたタプルを一様ランダムサン
プルから削除し、（３）結合データサンプルから前記タ
プルに関連する結合データサンプルタプルを削除する。
問合せがデータを削除するものである場合、（ａ）前記
タプルの関係を判定し、（ｂ）前記タプルが既存の一様
ランダムサンプルにある場合、（ｉ）そのタプルをその
一様ランダムサンプルから削除し、（ｉｉ）関連する結
合データサンプルからそのタプルに関連する結合データ
サンプルタプルを削除し、（ｃ）複数の一様ランダムサ
ンプルのうちのいずれかが所定の最小要求サイズより小
さくなった場合、所定最小要求サイズより小さくなった
それぞれの一様ランダムサンプルに、データベースから
の新しいタプルを加える。

【００２５】

【発明の実施の形態】図１に、従来のデータウェアハウ
スシステムを示す。データベースはデータウェアハウス
１１０に存在する。データウェアハウス１１０は、新規
データ１２０が到着すると更新され、問合せ１３０は、
データウェアハウスから計算される厳密応答１４０によ
って解答される。

【００２６】図２に、近似問合せ回答システムを示す。
このシステムは、問合せ１３０とデータウェアハウス１
１０の間に配置された近似問合せエンジン２１０を有す
る。本発明の発明者は、この近似問合せエンジンをＡＱ
ＵＡと命名した。これは本発明の一実施例に過ぎず、Ａ
ＱＵＡの考察から他の構成も考えることができる。問合
せ１３０に解答することを容易にするため、近似問合せ
エンジン２１０は、データに関するさまざまな要約情報
を格納することができる。この情報をシノプシスデータ
構造あるいは単にシノプシスという。シノプシスデータ
構造（シノプシス）は、基礎となるデータベースからあ
らかじめ計算された小さい要約データ構造（サンプル、
個数など）である。シノプシスデータ構造は、データに
関する重要な情報を簡潔な表現で捕捉する。すなわち、
これはデータの「シノプシス（概要）」を提供する。注
意すべき点であるが、シノプシスデータ構造は、データ
ベースに見出される情報の要約であって、単なる複製で
はない。関係データウェアハウスに対するシノプシスの
例には、大きい関係のヒストグラムおよびサンプル行
や、重要な列に射影された小さい関係のすべての行があ
る。これらのシノプシスは、（１）新規データ１２０が
データウェアハウス１１０にロードされるのを観測する
こと、（２）データウェアハウス１１０に定期的に戻っ
て情報を更新すること、あるいは（３）問合せ時にデー
タウェアハウス１１０に戻ることによって、管理するこ
とができる。

【００２７】問合せ１３０は、近似問合せエンジン２１
０に送られる。可能な限り、近似問合せエンジン２１０
は、問合せに対して、そのシノプシスを用いて、近似回
答および精度（例えば、数値的回答の場合には９５％信
頼区間）からなる応答２２０を返す。連続的報告（Barb
ara et al.では"progressive resolution refinement"
と呼ばれたもの）では、近似問合せエンジン２１０は、
問合せに対して（近似回答，精度）の対の列を提供し続
ける。それぞれの対は後のほうほど精度の高い回答を提
供する（Hellerstein et al.の場合と同様）。離散的報
告では、１個または数個のみのそのような対が近似問合
せシステム２１０によって提供される。また、近似問合
せシステム２１０は、近似問合せシステム２１０あるい
は従来の問合せオプティマイザによって決定される厳密
回答を計算するための推定時間を返すことも可能であ
る。問合せ１３０をしたユーザは、問合せ処理を中断し
て現在の近似回答で満足するか、それとも、次の近似、
あるいは、ベースデータからの厳密回答まで進むかを決
定することができる。あるいは、ユーザは、近似回答を
さらに検証するために、現在の問合せ１３０を継続した
まま、新たな問合せをすることも可能である。

【００２８】図３に、地区ごと、および、各地区内の店
鋪タイプごとにグループ化された平均および最低の売上
の集計値を問い合わせる、売上データベースに対する標
準的なＧＲＯＵＰ ＢＹ問合せに対する例示的な厳密回
答３００を示す。この回答は、データベース内のデータ
から計算された厳密置を有するｎ行のデータ（タプル）
のセット３１０−ｊ（ｊ＝１，２，...，ｎ）を返す。

【００２９】図４に、図３の結果を得るために用いたの
と同じ標準的なデータベース問合せに対する例示的な近
似回答４００を示す。この回答は、近似問合せエンジン
２１０によって管理されるシノプシスデータ構造から導
出された近似値を有するｎ行のデータ（タプル）のセッ
ト４１０−ｊ（ｊ＝１，２，...，ｎ）を返す。回答が
集計値（例えば、ＡＶＧ、ＳＵＭ、ＣＯＵＮＴの結果）
であるような問合せの場合、近似回答の概念は直観的な
ものである。すなわち、近似回答は単に、回答の推定値
および精度である。これは、ＳＱＬのＧＲＯＵＰ ＢＹ
演算で生じるような、集計値４１０の集まりに拡張する
ことができる。この場合、近似回答は、それぞれのその
ような集計値に対する（推定値，精度）の対４２０であ
り、その集計値（グループ）を定義する属性でラベルさ
れる。図４では、近似回答は、各推定値ごとに信頼区間
として精度を提供し、この精度は、同じく指定される何
らかの信頼確率に対するものである（例えば、９５％信
頼区間）。注意すべき点であるが、いくつかの場合に
は、上限（健全性限界４３０という。）が、推定値の代
わりに提供される。同じく注意すべき点であるが、近似
回答４００は、厳密回答にはないタプルを含むこと（こ
の例では、「中部アウトレット」のグループ４１０−
４）があり、その逆の場合もある。

【００３０】セット値問合せの場合、近似回答とは何か
ということはあまり直観的ではない。厳密回答内のタプ
ルの数は極めて多いことがあるため、効率化のため、シ
ステムは、厳密回答内の各タプルごとにタプルを返さな
いことがある。非常に高速な応答時間を保証するため
に、システムは、少数の代表的なタプルのみを、タプル
のセット全体に関するメタ情報とともに返そうとする。
すなわち、近似回答は、厳密回答内のタプルの個数の推
定される（または実際の）カウントを含む、厳密回答の
メタ情報に関する推定値と、厳密回答からの代表的タプ
ルの両方からなる。各メタ情報推定値は、精度を含む。
代表的タプルは、当業者に周知のように、そのタプルが
厳密回答内にあることを近似エンジンが確証しているか
否かに応じて、確定または可能と分類される。可能タプ
ルは、厳密回答内のタプルとの類似性の何らかの尺度と
ともに報告される。例としては、ある与えられた信頼確
率で厳密回答に入るタプルや、問合せによって計算され
る（ＭＩＮやＭＡＸのような）選択基準を満たさないが
それに近いタプルがある。

【００３１】確定タプルは、報告されるタプルが出力タ
プルのセットの一様ランダムサンプルである場合にラン
ダム選択タプルとして分類され、報告されるタプルが特
定の基準（バイアス基準）に従って偏っている場合にバ
イアス選択タプルとして分類され、あるいは、任意タプ
ルとして分類される。ランダム選択タプルは、出力タプ
ルのセット全体を一様に代表するという利点を有する。
バイアス選択タプルは、バイアス基準が「最も重要な」
出力タプルに沿っている場合、例えば、問合せがあるし
きい値より上のタプルを要求し、報告されるタプルが最
大量だけそのしきい値を超えるもののほうに偏っている
場合に、有利である。このような場合、バイアス選択の
ほうが、ランダム選択よりも好ましいことがある。他
方、出力タプルが重要であるための基準が未知の場合、
あるいは、相反する基準がある場合、一様ランダムサン
プルが自然な選択である。代表タプルは、完全タプルに
おけるすべての列を含むことも含まないことも可能であ
る。

【００３２】近似回答の精度には、問合せのタイプに依
存して、いくつかの可能性がある。数値的回答の場合、
自然な精度は、精度区間［ａ，ｂ］および信頼確率ｐか
らなる信頼区間である。信頼区間は、また、近似回答
を、厳密値の不偏推定値とする、すなわち、近似回答の
期待値が厳密値に等しくなるようにすると有効である。
精度および類似性の尺度は、（証明可能に）保証付きで
あるか、それとも、発見的であるかのいずれかに分類す
ることが可能である。一般的な発見的尺度には、ヒスト
グラムバケット内の値の分布に関する仮定に基づくも
の、属性の独立性に基づくもの、結合の一様性に基づく
もの、および、ディスクからシーケンシャルに読み出さ
れるタプルのランダム性に基づくものがある。保証付き
尺度のほうが好ましいが、場合によっては、厳密に保証
付きの限界を得ることは困難であり、発見的尺度のほう
が適当なこともある。

【００３３】図５に、厳密回答のタイプと、それらに対
応する厳密回答との間の関係の一例を示す。集計値５１
０の場合、近似回答は、精度付きの推定値または健全性
限界を含む。ここで、精度は信頼区間である。セット値
問合せ５２０の場合、近似回答は、厳密回答に関する推
定メタ情報と、代表タプルのセットである。「メタ情
報」とは、厳密回答のサイズの推定値および信頼区間で
あり、代表タプルは、問合せに依存して、タイプ
（ａ）、（ｂ）、（ｃ）または（ｄ）のものである。

【００３４】図６に、各基底関係を頂点とする有向非巡
回グラフＧ（６００）を示す。頂点ｕから頂点ｖへの有
向辺は、ｖ（に対応する関係）に対する外部キーを形成
する属性がｕ（に対応する関係）に含まれる場合に存在
する。これは、データベース内の関係の間の関係を示
す、データベーススキーマの図形的表現の例である。こ
の例は、ＴＰＣ−Ｄベンチマークに対するスキーマを例
示している。

【００３５】図６において、頂点Ｌ６１０、Ｏ６２０、
Ｃ６３０、ＰＳ６４０、Ｐ６５０、Ｓ６６０、Ｎ６７
０、およびＲ６８０は、データベース内の関係に対応す
る。頂点Ｌ６１０とＯ６２０は、Ｏ６２０内の特定のレ
コードを識別する外部キーＯｒｄｅｒ６１２を用いて、
有向辺６１１によって連結されている。別の有向辺６２
５は、外部キーＣｕｓｔ６２６を用いてＯ６２０をＣ６
３０に連結し、さらに別の有向辺６３５は、外部キーＮ
ａｔｉｏｎ６３６を用いてＣ６３０をＮ６７０に連結
し、さらに別の有向辺６７５は、外部キーＲｅｇｉｏｎ
６７６を用いてＮ６７０をＲ６８０に連結している。頂
点Ｌ６１０は、外部キーＰａｒｔ６１４を用いて別の有
向辺６１３によって頂点Ｐ６５０にも連結されている。
さらに、頂点Ｌ６１０は、外部キーＳｕｐｐ６１９を用
いて別の有向辺６１８によって頂点Ｓ６６０に連結さ
れ、Ｓ６６０は、外部キーＮａｔｉｏｎ６６６を用いて
別の有向辺６６５によってＮ６７０に連結されている。
最後に、頂点Ｌ６１０は、組合せ外部キーＰａｒｔ・Ｓ
ｕｐｐ６１６を用いて別の有向辺６１５によって頂点Ｐ
Ｓ６４０に連結され、ＰＳ６４０は、外部キーＰａｒｔ
６４４を用いて別の有向辺６４３によってＰ６５０に連
結され、外部キーＳｕｐｐ６４６を用いて別の有向辺６
４５によってＳ６６０に連結されている。

【００３６】近似問合せエンジン２１０の自然なシノプ
シスのセットは、各基底関係の一様ランダムサンプルを
含むものである。しかし、基底関係のサンプルを用い
て、結合(join)を有する問合せに対して近似回答を提供
する場合の問題点は、一般に、近似の品質が、単一の結
合でも非常に悪くなることである。これは次の２つの理
由で起こる。 １．２つの一様ランダムサンプルの結合は、結合の出力
の一様ランダムサンプルではない。２つの関係に対し
て、各タプルが他方の関係における高々１個のタプルと
しか結合しないという特殊な場合を除いて、結合オペレ
ータは、結合タプル間の依存関係（従属性）を生じる。 ２．２つのランダムサンプルの結合は一般に、結合選択
性がかなり高い場合でも、少数のタプルである。例え
ば、一方の関係内のタプルの大多数がそれぞれ、他方の
関係内のわずかなタプルからなるタプルの固定セットＳ
と結合される場合、高い確率で、これらのタプルがいず
れも、関係のサンプルの結合内にないことになる。その
理由は、Ｓ内のタプルは、高い確率でサンプルに現れな
いからである。 実際、このような近似に対する最も良く知られた信頼区
間は極めて悲観的なものである。例えば、P. J. Haas,
"Large-sample and deterministic confidence interv
als for online aggregation", 9th International Con
f. on Scientificand Statistical Database Managemen
t, 1998、における限界から、結合サイズが大きくない
場合（このような場合が多い）、自明でない信頼区間を
得るには、サンプルサイズは、結合属性の最大値、ある
いは、関係の相当大きな部分の少なくとも２乗でなけれ
ばならないことがわかる。注意すべき点であるが、この
問題は、外部キー結合の場合でも起こる。２ウェイ結合
ｒ₁←→ｒ₂（ｒ₁≠ｒ₂）は、結合属性がｒ₁内の外部キ
ー（すなわち、ｒ₂内のキー）である場合、外部キー結
合である。ｋ≧３に対して、ｋウェイ結合は、結合され
る関係の順序ｒ₁，ｒ₂，...，ｒ_kが、ｉ＝２，
３，...，ｋに対してｓ_i-1←→ｒ_iが２ウェイ外部キー
結合である（ただし、ｓ_i-1はｒ₁，ｒ₂，...，ｒ_i-1を
結合することによって得られる関係である。）ような順
序である場合、外部キー結合である。

【００３７】本発明による結合サンプルという新規な解
決法は、外部キー結合のみを有する任意の非巡回データ
ウェアハウススキーマに対して有効である。このような
スキーマはデータウェアハウスでは一般的であり、実
際、ＴＰＣ−Ｄベンチマークは、この状況をそのスキー
マに反映している（図６参照）。この解決法は、部分的
には、重要な属性のみを格納することによって、およ
び、冗長なサブタプルを除去することによって、さまざ
まな結合の出力からの選択されたタプルのサンプルを効
率的に管理する。基本的な考え方は、各基底関係ごとに
１個の結合サンプルを管理することによって、以下の補
題１および補題２を強化することである。

【００３８】補題１。任意のｋウェイ外部キー結合にお
けるｋ個のノード上のＧのサブグラフは、単一のルート
ノードを有する連結サブグラフでなければならない。

【００３９】証明。上記のｋウェイ外部キー結合の性質
を満たす関係の順序ｒ₁，ｒ₂，...，ｒ_kを考える。証明
は、単一のノードｒ₁を基本的な場合とする帰納法によ
る。１＜ｉ≦ｋ、および、ｓ_i-1＝ｒ₁←→・・・←→ｒ
_i-1とする。ｓ_i-1内のｉ−１個のノード上のサブグラフ
Ｇ_i-1が単一のルートノードｒ₁に連結されていると仮定
する。ｓ_i-1←→ｒ_iは２ウェイ外部キー結合であるた
め、結合属性はｒ_i内のキーでなければならない。従っ
て、Ｇ_i-1内のあるノードからｒ₁へ向かう辺が存在し、
これは、Ｇ_i＝Ｇ_i-1∪ｒ_iがＧの連結サブグラフである
ことを意味する。従って、Ｇ内にｒ₁からｒ_iへの有向パ
スが存在する。Ｇは非巡回で、ｒ_i≠ｒ₁であるため、ｒ
₁（これは、帰納法の仮定によりＧ_i-1内の唯一のルート
ノードである。）は、Ｇ_iの唯一のルートノードであ
る。補題は帰納法により従う。

【００４０】従って、任意のｋウェイ外部キー結合に対
して、１つのルートノードが存在する。これをその結合
のソース関係(source relation)という。例えば、図６
で、Ｐ６５０、ＰＳ６４０、およびＳ６６０の間の３ウ
ェイ外部キー結合において、ソース関係はＰＳ６４０で
ある。

【００４１】補題２。ｒ₁内のタプルと、ソース関係を
ｒ₁とする任意のｋウェイ外部キー結合内のタプルとの
間には一対一対応が存在する。

【００４２】証明。結合の定義により、結合の出力内の
各タプルτに対して、τをｒ₁内の属性に射影したもの
がτ′であるようなタプルτ′がｒ₁内に存在する。逆
に、我々は、ｒ₁内の各タプルτ′に対して、ｋウェイ
外部キー結合内にちょうど１個のタプルτが存在するこ
とを主張する。この主張を帰納法により示す。上記のｋ
ウェイ外部キー結合の性質を満たす関係の順序ｒ₁，
ｒ₂，...，ｒ_kを考える。主張は、単一の関係ｒ₁の基本
的な場合には成立は自明である。１＜ｉ＜ｋ、および、
ｓ_i-1＝ｒ₁←→・・・←→ｒ_i-1とする。帰納的に、ｒ₁
内の各タプルτ′に対して、ｓ_i-1内にちょうど１個の
タプルτが存在すると仮定する。ｓ_i-1←→ｒ_iは２ウェ
イ外部キー結合であるため、結合属性はｒ_i内のキーで
なければならない。従って、ｒ_i内には、ｓ_i-1内の各タ
プルと結合するタプルが高々１個存在し、さらに、外部
キー一貫性制約により、このようなタプルは少なくとも
１個存在する。従って、ｒ₁内の各タプルτ′に対し
て、ｓ_i＝ｓ_i-1←→ｒ_i内にはちょうど１個のタプルτ
が存在する。主張、従って補題は、帰納法により従う。

【００４３】補題１から、各ノードは、Ｇ内の子孫に関
連するｋウェイ外部キー結合に対してのみ、ソース関係
であり得る。各関係ｒに対して、ｒをソース関係とする
ある最大外部キー結合が存在する。例えば、図６で、Ｃ
←→Ｎ←→ＲはＣをソース関係とする最大外部キー結合
であり、Ｌ←→Ｏ←→Ｃ←→Ｎ１←→Ｒ１←→ＰＳ←→
Ｐ←→Ｓ←→Ｎ２←→Ｒ２は、Ｌをソース関係とする最
大外部キー結合である。

【００４４】結合サンプル。Ｇ内の、関係ｒ₁に対応す
る各ノードｕに対して、Ｊ（ｕ）は、ｒ₁をソースとす
る最大外部キー結合ｒ₁←→ｒ₂←→・・・←→ｒ_kの出
力であると定義する。（ｕがＧ内に子孫を有しない場
合、ｋ＝１で、Ｊ（ｕ）＝ｒ₁である。）Ｓ_uを、ｒ₁の
一様ランダムサンプルとする。結合サンプルＪ（Ｓ_u）
を、Ｓ_u←→ｒ₂←→・・・←→ｒ_kの出力と定義する。
我々のシノプシスは、Ｇ内のすべてのｕに対するＪ（Ｓ
_u）からなる。

【００４５】このシノプシスの有用性は以下の定理から
観察することができる。この定理は、補第２の直接の帰
結である。

【００４６】定理３。ｒ₁←→・・・←→ｒ_k（ｋ≧２）
を、ｒ₁をソース関係とする任意のｋウェイ外部キー結
合とする。ｕを、ｒ₁に対応するＧ内のノードとし、Ｓ_u
を、ｒ₁の一様ランダムサンプルとする。Ａを、
ｒ₁，...，ｒ_k内の属性のセットとする。 ・Ｊ（Ｓ_u）は、サイズ｜Ｓ_u｜の、Ｊ（ｕ）の一様ラン
ダムサンプルである。 ・ｒ₁←→・・・←→ｒ_k＝π_AＪ（ｕ）である。すなわ
ち、ｒ₁，...，ｒ_k内の属性上へのＪ（ｕ）の射影であ
る。 ・π_AＪ（Ｓ_u）は、サイズ｜Ｓ_u｜の、ｒ₁←→・・・←
→ｒ_k（＝π_AＪ（ｕ））の一様ランダムサンプルであ
る。 従って、我々のシノプシスから、任意のｋウェイ外部キ
ー結合（ｋ≧２）の出力の一様ランダムサンプルを抽出
することができる。

【００４７】２つの結合は、それらが同じ関係のセット
を結合していない場合に、互いに素であるという。次の
補題は、単一の結合サンプルが、多数の互いに素の結合
に対して、特に、データウェアハウスで一般的なスター
状スキーマに対して使用可能であることを示す。

【００４８】補題４。最大外部キー結合がＫ個の関係で
あるノードに対する単一の結合サンプルから、Ｋ−１〜
２^K-1−１個の外部キー結合の出力の一様ランダムサン
プルを抽出することができる。

【００４９】証明。前者（Ｋ−１個）の場合は、ノード
のすべての子孫がＧ内でラインを形成する場合に起こ
る。後者（２^K-1−１個）の場合は、スタースキーマの
場合のように、ノードがそのすべての子孫からなるスタ
ーのルートである場合に起こる。

【００５０】注意すべき点であるが、補題２は、ソース
関係以外の任意の関係には一般に適用することができな
いため、ソース関係以外の任意の関係ｒ内の結合タプル
は一般にｒの一様ランダムサンプルにはならない。従っ
て、各ノードごとに別個の結合サンプルが必要となる。

【００５１】結合サンプルを管理するこの解決法の制限
は、最悪の場合のスキーマでは、最大外部キー結合のサ
イズはスキーマ内の関係の個数に関して指数関数的にな
りうることである。

【００５２】補題５。ｔ個の関係を有する外部キースキ
ーマであって、最大外部キー結合が４・２^(t-1)/3−３
個の関係を有するものが存在する。

【００５３】証明。ｒ_iをルートとする「コートハンガ
ー」Ｈ_iを考える。Ｈ_i+1はルートｒ_{i +1}を有し、その２
個の子ｌおよびｒはそれぞれｒ_iに結合する。容易に確
認されるように、コートハンガーＨ_iは３ｉ＋１個のノ
ードを有する。Ｈ_(t-1)/3のノードであって、ノード間
の辺が外部キー関係を表すようなｔ個の関係を考える。
すると、容易に確認されるように、最大外部キー結合は
４・２^(t-1)/3−３個の関係を有する。

【００５４】このような場合、問合せに実際に生じる結
合は、最大外部キー結合のうちのどの程度が実体化して
いるかを判定するのに用いられる。

【００５５】必要なスペースの縮小。想起すべき点であ
るが、Ａｑｕａでは、重要な属性と、小さい関係のすべ
てのタプルのみが格納される。これは、結合サンプルタ
プルのために格納される列数を低減する。結合サンプル
のためのフットプリントをさらに縮小するため、Ａｑｕ
ａは、Ｊ（Ｓ_u）内のタプルを、構成要素の関係へと再
正規化し、重複を除去することができる。外部キーが多
対一である限り、これはスペースを縮小する（その場
合、キーは複製されることになるが）。このアプローチ
では、Ｓ_u内のあるタプルが削除されると、次のいずれ
かが可能である。 （１）他の関係内のどのタプルを除去すべきか（もしあ
れば）を線形探索、参照カウントの管理などによって直
ちに決定する。 （２）他のタプルをそのまま残し、その後、定期的にＪ
（Ｓ_u）を実体化し未使用のタプルを捨てることによっ
てガーベジコレクションを行う。あるいは、Ａｑｕａ
は、上記のような再正規化を行うが、すべてのｕに対す
るＪ（Ｓ_u）の、Ｓ_uを除く合併(union)をとり、重複を
除去するということも可能である。

【００５６】補題６。最大外部キー結合がＫウェイ結合
であるような任意のノードｕに対して、再正規化された
結合サンプルＪ（Ｓ_u）内のタプルの個数は高々Ｋ｜Ｓ_u
｜である。

【００５７】証明。（未正規化）Ｊ（Ｓ_u）内の各タプ
ルは、正規化されたＪ（Ｓ_u）（重複除去前）にＫ個の
タプルの寄与をする。

【００５８】例として、図６に対して、ＮおよびＲの単
一のコピーを格納し、それらをＧから除去した場合、
Ｌ、ＰＳ、Ｏ、Ｃ、Ｐ、およびＳに対して、Ｋの値はそ
れぞれ６、３、２、１、１、および１となる。｜Ｓ_u｜
がＧ−｛Ｎ，Ｒ｝内のすべてのｕに対して等しいとする
と、すべてのデータ分布に対して、シノプシス内のタプ
ルの個数は高々１４｜Ｓ_u｜＋｜Ｎ｜＋｜Ｒ｜となる。
外部キーが多対一である限り、スペースはこの上限より
もかなり小さくなりうる。

【００５９】図７に、Ａｑｕａの近似問合せエンジン２
１０において問合せを処理することに関連するステップ
を示す。近似問合せエンジン２１０の重要な特徴は、
（ａ）豊富な問合せオペレータのセットと、（ｂ）容易
な拡張性である。ステップ７１０で、オペレータのツリ
ーを含む問合せプランがシステムに入力される。オペレ
ータは、個々の問合せオペレータ（例えば、選択(selec
t)、ハッシュあるいはネスト化ループ結合、整列(sor
t)、集計(aggregate)、ファイルから読み込み(read-fro
m-file)など）に対応する。すべてのオペレータは、標
準インタフェースを有する繰返し子(iterator)として実
装され、トップダウン方式で実行される。ステップ７１
５で、ｏｐｅｎコールがプランのルートに対して呼び出
される。これは、オペレータ固有のデータを初期化す
る。ステップ７２０で、そのそれぞれの子に対して再帰
的にｏｐｅｎを呼び出す。ステップ７２５で、オペレー
タがさらに子を有するかどうかをチェックする。さらに
子がある場合、処理はステップ７２０にループバックす
る。これ以上子がない場合、ステップ７３０で、ルート
プランをチェックし、さらにオペレータがあるかどうか
を判定する。さらにオペレータがある場合、処理はステ
ップ７１５にループバックする。これ以上オペレータが
ない場合、ステップ７３５で、システムは未処理のオペ
レータを選択する。オペレータは、これ以上結果が生成
されないときに処理済みとなる。ステップ７４０で、オ
ペレータは、いくつかの入力を子から（または、ｆｉｌ
ｅ ｒｅａｄオペレータの場合にはデータベースファイ
ルから）フェッチする。ステップ７４５で、オペレータ
をチェックし、さらに子があるかどうかを判定する。さ
らに子がある場合、処理はステップ７４０にループバッ
クする。これ以上子がない場合、ステップ７５０で、オ
ペレータは関連するオペレーション（もしあれば）を実
行する。ステップ７５５で、オペレータは、オペレーシ
ョンの結果を上位に送り、親がそれをフェッチすること
ができるようにする。ステップ７６０で、プランをチェ
ックし、さらに未処理のオペレータがあるかどうかを判
定する。ある場合、処理はステップ７３５にループバッ
クする。この処理は、問合せに対するすべての入力が取
り尽くされ、これ以上結果が生成されなくなったときに
終了する。これ以上未処理のオペレータがない場合、ス
テップ７６５で、システムは、オペレータに対するｃｌ
ｏｓｅを呼び出す。これは、クリーンアップオペレーシ
ョンを実行する（例えば、開いたテーブルを閉じ、メモ
リを解放する）。ステップ７７０で、プランをチェック
し、さらにｏｐｅｎオペレータがあるかどうかを判定す
る。さらにｏｐｅｎオペレータがある場合、処理はステ
ップ７６５にループバックする。これ以上ｏｐｅｎオペ
レータがない場合、処理は終了する。

【００６０】この設計の重要な特徴は、オペレータが相
互に分離されていることである。すなわち、オペレータ
は、その入力を生成するオペレータの性質を知る必要は
なく、その逆も同様である。例えば、オペレータから見
ると、入力は、単なるファイルスキャンから来ること
も、複雑な問合せから来ることも可能である。この特徴
により、Ａｑｕａは、モジュール的に任意の複雑な問合
せを処理し、局所的な変化を既存の問合せオペレータに
追加（あるいは変更）することが可能となる。これによ
り、さまざまの新規なオペレータの非常に容易な実装が
可能となるため、これはＡｑｕａにおいて非常に有用で
ある。例えば、入力ストリームをサンプリングし、固定
数（当業者に周知のレザボアサンプリング(reservoir s
ampling)を用いて）または入力ストリームの所望の部分
の、ランダムに選択されたタプルを出力するｓａｍｐｌ
ｅオペレータが実装されている。

【００６１】図８に、本発明の方法およびコンピュータ
実装された発明の第１実施例のステップを示す。基本的
なＡｑｕａ近似問合せエンジン２１０は、データに関す
るシノプシスを管理するルーチンにより強化される。シ
ノプシスの多くは通常、システムカタログに格納され、
以下のものを含む。 ・各関係に対して、その関係内のタプルの個数を管理す
る。 ・小さい関係（タプルは数百以下）に対して、その関係
のすべてのタプルを格納する。 ・他のすべての関係に対して、結合サンプルなどのシノ
プシスを格納する。 ・ＡＶＧまたはＳＵＭ集計で用いられる可能性のある各
属性に対して、その範囲の上限および下限を管理する。

【００６２】格納されている各タプルに対して、重要な
属性のみが保持される。保持する属性の最適な選択は、
問合せの内容に依存する。例えば、コメントのような記
述的文字列は、問合せに回答するため、あるいは、メタ
情報を計算するために必要のない場合には捨てられる。
記述的文字列はしばしば多くのバイト数を要するので、
これにより各タプルに必要なフットプリントが縮小す
る。他方、この選択は、システムが、これらの属性に関
して問合せに対し適当な近似回答を提供することができ
ないことを意味する。

【００６３】本発明の方法およびコンピュータ実装され
た発明の第１実施例のステップを図８に示す。ステップ
８１０で、データがデータベースに格納されているとお
りのデータサンプルが取得される。ステップ８２０で、
取得されたデータサンプルは、近似問合せエンジン２１
０のメモリに格納される。近似問合せエンジン２１０に
データサンプルを格納するのに必要なメモリの量は、デ
ータウェアハウス１１０全体より小さい。ステップ８３
０で、近似問合せエンジン２１０は問合せ１３０を受け
取る。ステップ８４０で、近似問合せエンジン２１０
は、近似問合せエンジン２１０のメモリに格納されてい
るデータサンプルで、問合せ１３０に適合するものを検
索する。ステップ８５０で、近似問合せエンジン２１０
は、ステップ８４０で得られた、適合した格納データサ
ンプルを含む応答２２０を出力する。例えば、ステップ
８４０およびステップ８５０の一実施例では、問合せの
ソース関係を判定し、問合せを、この関係に関連する結
合サンプルに適用する。

【００６４】新規データのバッチ到着と、（格納されて
いる）ベースデータへの時折のアクセスに基づいて、Ａ
ｑｕａで用いられるシノプシスを増分管理する新規なア
ルゴリズムが開発されている。このようなアルゴリズム
により、シノプシスは、並行性ボトルネックなしに常に
実質的に最新のものに保つことが可能となる。更新およ
び問合せが交錯するオンライン環境では、Ａｑｕａは、
あらゆるタプル（例えば、属性の最小値および最大値）
を調べることを必要とする最新のシノプシスの管理は、
並行性ボトルネックを生じることなしには不可能であ
る。（注意すべき点であるが、Ａｑｕａにおけるほどん
どのシノプシスはサンプリングに基づくものであるた
め、ときどきの更新しか必要としない。）このような環
境では、管理は定期的にのみ実行される。あらゆるタプ
ルを調べる必要のあるシノプシスに依存する近似回答
は、データの最近の傾向（すなわち、管理が最後に実行
された後に生じたもの）を考慮に入れないことになるた
め、精度保証が大幅に低下する可能性がある。注意すべ
き点であるが、増分管理アルゴリズムは、ベースデータ
を１回スキャンした後、少数のキーに関する索引付き参
照によって、ゼロからすべてのシノプシスを計算するた
めにも（そのような再計算が必要であれば）使用可能で
ある。

【００６５】上記のほとんどのシノプシスは、既知の技
術を用いて管理することができる。カウンタは、タプル
が挿入されるときにインクリメントし、タプルが削除さ
れるときにデクリメントすることによって管理される。
一様ランダムサンプルは、我々の１９９７年８月の論文
（Gibbons et al., "Fast incremental maintenanceof
approximate histograms", Proc. 23rd International
Conf. on Very LargeData Bases, pp.446-475）に記載
されているアルゴリズムを用いてタプルが挿入および削
除されるとともに管理される。属性の最大値および最小
値は、挿入時には、現在の最大または最小と新規タプル
を比較することによって管理される。削除時には、最大
または最小が削除される場合、（１）その削除を無視
し、保守的な限界とするか、（２）関係を再び参照し、
新規の最大または最小を抽出するか、（３）最大値およ
び最小値のセットを保持するか（セット全体が削除され
る場合に実行するのは（１）または（２）のみであ
る。）、または、（４）各範囲内の値の個数に関するヒ
ストグラム（ただし、この範囲は、例えば、２の累乗と
することが可能である。）を管理するか、のいずれかで
ある。（４）により、対数的個数のバケットを用いるだ
けで、（２）にたよることなく、２倍（２分の１）の範
囲内で最大および最小に関する推定値が提供される。

【００６６】図９に、本発明の方法およびコンピュータ
実装された発明の第１実施例において結合サンプルを管
理するステップを示す。関係ｕにおける挿入および削除
時のサンプルＳ_uもまた、上記のアルゴリズムを用いて
管理される。任意の関係における挿入および削除時にす
べてのｕに対してＪ（Ｓ_u）を管理するため、Ａｑｕａ
は、各外部キーに関する一貫性制約に基づいて、より高
速な管理アルゴリズムを可能にしている。

【００６７】各ｕに対する結合サンプルＪ（Ｓ_u）を管
理するアルゴリズムは以下の通りである。ｐ_uを、ラン
ダムサンプルＳ_u内に、関係ｕに対して新たに到着した
タプルを含む現在の確率とする。Ｇ内のノードｕに対応
する基底関係に新規タプルτを挿入する場合には、次の
ことを行う。ｕ←→ｒ₂←→・・・←→ｒ_kを、ｕをソー
スとする最大外部キー結合とする。（１）τをＳ_uに確
率ｐ_uで追加する。（２）τがＳ_uに追加された場合、タ
プル｛τ｝←→ｒ₂←→・・・←→ｒ_kをＪ（Ｓ_u）に追
加する。これは、基底データへの高々Ｋ−１回の参照
（それぞれｒ₂，...，ｒ_kにおける）を行うことによっ
て計算することができる。（既にＪ（Ｓ_u）内にあるキ
ーに対しては、そのキーあるいはその「子孫」に対する
参照は不要である。）（３）τがＳ_uに追加され、Ｓ_uが
その目標サイズを超過した場合、Ｓ_uから除くべきタプ
ルτ′を一様ランダムに選択する。τ′に対応するタプ
ルをＪ（Ｓ _u）から除去する。

【００６８】タプルτをｕから削除する場合には、ま
ず、τがＳ_u内にあるかどうかを判定する。τがＳ_u内に
ある場合、τをＳ_uから削除し、τに対応するタプルを
Ｊ（Ｓ _u）から除去する。Gibbons et al.に記載されて
いるように、サンプルからの多数の削除によりサンプル
が小さくなり過ぎた場合、基底関係を再スキャンするこ
とによりサンプルを再び追加する。

【００６９】注意すべき点であるが、このアルゴリズム
は、（小さい）確率ｐ_uでベースデータへの参照を行う
のみである。また、タプルが基底関係ｕに挿入されると
きに、ｕの先祖に対する結合サンプルは全く更新されな
い。このような更新はコストがかかる。その理由は、こ
のようなオペレーションは、ｕのあらゆる挿入に対し
て、およびあらゆる先祖に対して実行されることになる
からである。その代わりに、システムは、一貫性制約に
基づいて、このようなコストのかかる更新を回避する。

【００７０】定理７。上記のアルゴリズムは、すべての
Ｓ_uを、ｕの一様ランダムサンプルとして正しく保持
し、すべての結合サンプルＪ（Ｓ_u）を正しく保持す
る。

【００７１】証明。一貫性制約により、ｗからｕへの各
辺に対して、常にｕ内には各タプルに結合するちょうど
１個のタプルが存在する。従って、その後のｕへのタプ
ルの挿入は、ｗ内に既にあるタプルと結合することはで
きず、ｕから削除されるタプルは、ｗ内に依然として存
在するタプルと結合していることはない。

【００７２】図９に、上記のアルゴリズムに関連するス
テップを示す。ステップ９１０で、近似問合せエンジン
（ＡＱＵＡ）はデータベース問合せを受け取る。特に、
この問合せは、これからデータベースに挿入される新し
いタプルの情報か、または、データベース内に既にあり
これから削除されるタプルの情報への参照かのいずれか
を含む。ステップ９１５で、問合せをチェックし、実行
すべきオペレーションが挿入であるかまたは削除である
かを判定する。オペレーションが挿入である場合、ステ
ップ９２０で、問合せ情報がデータベース内のどの関係
に関連しているかが判定される。ステップ９３０で、関
連する一様ランダムサンプルに新規タプルを追加する現
在の計算された確率に基づいて、関連する一様ランダム
サンプルにタプルを追加する。タプルが追加された場
合、ステップ９３５で、新しい結合データサンプルタプ
ルを計算する。タプルが追加されない場合（すなわち、
ステップ９３０の判断のＮＯの枝が成立する場合）、処
理はステップ９６０に移る（後述）。ステップ９４０
で、新規計算された結合データサンプルタプルを、関連
する結合データサンプルに追加する。ステップ９４５
で、関連する一様ランダムサンプルのサイズをチェック
し、それが、計算された最大目標サイズを超過したかど
うかを判定する。超過した場合、ステップ９５０で、関
連するランダムサンプルからタプルをランダムに削除す
る。ステップ９５５で、削除したタプルに関連する結合
データサンプルタプルを、関連する結合データサンプル
から削除する。ステップ９６０で、さらに挿入すべきタ
プルが存在するかどうかを判定する。存在する場合、処
理はステップ９２０にループバックする。

【００７３】ステップ９１５におけるチェックで、オペ
レーションは削除であると判定された場合（すなわち、
ステップ９１５の判断のＮＯの枝が成立した場合）、ス
テップ９６５で、削除すべき最初のタプルに関連する関
係を判定する。ステップ９７０で、削除すべきタプルが
既存の一様ランダムサンプル内に存在するかどうかを判
定する。存在する場合、ステップ９７５で、そのタプル
を一様ランダムサンプルから削除する。ステップ９８０
で、ステップ９７５で削除したタプルに関連する結合デ
ータサンプルタプルを、関連する結合データサンプルか
ら削除する。タプルが既存の一様ランダムサンプル内に
存在しない場合（すなわち、ステップ９７０の判定のＮ
Ｏの枝が成立した場合）、処理はステップ９９５（後
述）に移る。ステップ９８５で、関連する一様ランダム
サンプルのサイズをチェックし、最小の計算された目標
サイズより小さくなったかどうかを判定する。小さくな
った場合、ステップ９９０で、基底関係をスキャンする
ことによって、その一様ランダムサンプルを再充填す
る。ステップ９９５で、さらに削除すべきタプルが存在
するかどうかを判定する。存在する場合、処理はステッ
プ９６５にループバックする。

【００７４】図１０に、本発明の方法およびコンピュー
タ実装された発明の第２実施例においてサンプルを管理
する際のステップを示す。ＧＲＯＵＰ ＢＹオペレータ
が、サンプリングに基づく推定で問題となることがあ
る。関係内の比較的少数の要素を有するグループは、一
様ランダムサンプル内に比較的少数の（全く存在しない
可能性もある）要素を有することが期待される。これ
は、このようなグループの推定の精度が極めて悪くなり
うることを意味する。Hellerstein et al.は、オンライ
ン集計に関する彼らの研究においてこの問題を取り扱
い、特殊なＢ木に基づく索引付け機構により、異なるサ
イズのグループが等しい割合でアクセスされることを可
能にしている。

【００７５】Ａｑｕａは、グループによってサンプルに
偏り（バイアス）をつけることによって、特殊な索引付
け機構や（ランダムな）ディスクアクセスなしで、ＧＲ
ＯＵＰ ＢＹにおける近似の精度を改善する。このアプ
ローチでは、ＧＲＯＵＰ ＢＹ属性の事前の知識が存在
することを仮定するが、グループにどのような要素が入
るかに関するその他の情報は仮定する必要がない（例え
ば、どのグループが空になるかは仮定する必要がな
い）。この技術は、問合せのソース関係内の属性に対す
るＧＲＯＵＰ ＢＹに対して有効であるが、他のＧＲＯ
ＵＰ ＢＹでは、バイアス付きサンプルを管理するため
の更新時間オーバーヘッドが大きくなり過ぎる可能性が
ある。

【００７６】１つのこのような事前のＧＲＯＵＰ ＢＹ
（例えば、図３における属性ＲｅｇｉｏｎおよびＴｙｐ
ｅに対するＧＲＯＵＰ ＢＹ）について考える。データ
がデータウェアハウスに挿入されるとき、Ａｑｕａは、
生じているグループのテーブルとともに、現在そのグル
ープ内にあるタプルの個数のカウントを管理する。例え
ば、図３で、グループのテーブルは５個のエントリを有
する。小さいグループにおける十分な表現を保証するた
め、Ａｑｕａは、このようなグループに対して、より高
い割合でサンプリングを行う。

【００７７】新規タプルが関係に挿入されるとき、Ａｑ
ｕａはそのグループを判定する。それが既存のグループ
である場合、Ａｑｕａは、そのグループに対するカウン
トをインクリメントする。そうでない場合、新しいエン
トリが、カウントを１として、テーブルに追加される。
その後、タプルは、グループのサイズに対応する所望の
サンプルレートに従って、サンプルに追加される。

【００７８】各グループはその固有の一様ランダムサン
プルであるため、サンプルレートを決定する際にかなり
の自由度がある（例えば、サンプルレートを均等にする
必要はない）。（未知の個数の）グループ間で均一に分
割された一定の全サンプルサイズｎを保持するため、Ａ
ｑｕａは、ｇ個のグループがある場合に、ｎ／ｇという
目標サンプルサイズが各グループごとに保持されるよう
に、各グループに対してレザボアサンプリングを実行す
る。新規のグループが現れると、Ａｑｕａは目標サンプ
ルサイズを減少させ、既存の各グループからランダムタ
プルを（ゆっくりと）除く。グループの個数が多くなっ
た場合、Ａｑｕａは、最も大きい（要素数の多い）グル
ープのみを追跡することが可能である。いずれのグルー
プが最も大きいかどうかは時間とともに変わるため、Ａ
ｑｕａは、Gibbos and Matiasの１９９７年１１月の論
文におけるアルゴリズムを用いて、（近似的に）最も大
きいグループのリストを管理することができる。

【００７９】バイアス付きサンプルの利点の評価。集計
値に対して信頼区間を小さくする際のバイアス付きサン
プルの利点は解析的に評価することができる。サイズｍ
≫ｎの関係からのサイズｎのサンプルを考える。この関
係内の式に関するＣＯＵＮＴ、ＳＵＭ、およびＡＶＧを
考え、ＭＩＮ≧０およびＭＡＸを、その式の下限および
上限とする。利点は、（１）各グループの個数(count)
を管理すること、（２）すべてのグループがサンプルに
あらわれることを保証すること、および（３）各グルー
プごとにバランスのとれたサンプルサイズが可能となる
こと、から生じる。各利点について順に考える。

【００８０】各グループの個数ｍ′を管理することは、
正確なＣＯＵＮＴ回答を可能にするのみならず、ＳＵＭ
に対するHoeffding信頼限界をも、

【数１】 から、

【数２】 に改善する。ただし、ｎ′＞０は、グループ内のサンプ
ルタプルの個数である。

【００８１】第２の利点は、グループの個数が一様サン
プリングとバイアス付きサンプリングの両方の場合で管
理されることを仮定することによって、第１の利点とは
独立に考察することができる。一様ランダムサンプルの
場合、サイズｍ′の各グループは、サンプル内にｍ′・
ｎ／ｍ回現れることが期待され、サンプル内に確率＞
（１−ｍ′／（ｍ−ｎ））ⁿ≒ｅ^-m'n/mで現れることは
できない。例えば、サイズｍ′＝ｍ／１０ｎのグループ
は、９０％以上の確率でサンプル内に現れない。サンプ
ル内に現れないグループ（すなわち、ｎ′＝０）に対し
て、

【数３】 がＳＵＭの健全性限界（上限）であり、ＳＵＭは決定論
的に［ｍ′・ＭＩＮ，ｍ′・ＭＡＸ］内にある。ＡＶＧ
についていえることは、ＡＶＧは決定論的に［ＭＩＮ，
ＭＡＸ］内にあるということだけである。バイアス付き
サンプリングでは、グループが大きいほどサンプルが少
なくなるという犠牲のもとで、すべてのグループ（ある
いは、グループ数が非常に多い場合には、最も大きいグ
ループ）が、サンプル内にある最小表現を有することを
保証することができる。

【００８２】第３の利点は、一様サンプルに各グループ
の単一のランダム代表元を追加することを仮定すること
によって、最初の２つの利点とは独立に考察することが
できる。この第３の利点は、ＡＶＧ集計値を考察するこ
とによって理解することができる。Haas("Hoeffding in
equalities for join-selectivity estimation and onl
ine aggregation", Technical Report RJ 10040, IBM A
lmaden Research Center, San Jose, CA, USA, 1996)に
よるＡＶＧに対するHoeffding限界により、ｇ＜ｎ個の
グループに関する平均信頼限界は

【数４】 に比例する。ただし、ｎ_iは、グループｉのサンプルの
サイズである。これは、すべてのｉに対してｎ_i＝ｎ／
ｇととることによって最小化される。これは、上記のレ
ザボアサンプリング法を用いたバイアス付きサンプリン
グにより達成される。一様サンプリングでは、ｎ_iはグ
ループサイズに比例すると期待されるため、大幅に変動
しうる。１個のグループ以外のすべてのグループで単一
の代表元という最悪の場合、一様サンプリングでの平均
信頼限界は、バイアス付きサンプリングでｎ_i＝ｎ／ｇ
とした場合よりも約（ｎ／ｇ）^1/2倍悪くなる。

【００８３】図１０に、上記のアルゴリズムに関連する
ステップを示す。ステップ１０１０で、近似問合せエン
ジン２１０はデータベース問合せを受け取る。特に、こ
の問合せは、関係に挿入すべき新規タプルを含む。ステ
ップ１０２０で、この新規タプルが関係内の既存のグル
ープ内に存在するかどうかを判定する。存在する場合、
ステップ１０３０で、そのグループのカウントを１だけ
インクリメントする。ステップ１０４０で、タプルは、
そのグループに対する所望のサンプルレートに基づいて
サンプルに追加される。

【００８４】ステップ１０２０におけるチェックで、タ
プルは関係内にない新しいグループ内にあると判定され
た場合（すなわち、ステップ１０２０の判定のＮＯの枝
が成立した場合）、ステップ１０５０で、新規グループ
がグループのテーブルにカウントを１として追加され
る。ステップ１０６０で、新規タプルがそのグループに
対する所望のサンプルレートに基づいてサンプルに追加
される。ステップ１０７０で、システムが、既存のグル
ープ間で均等に分割した一定のサンプルサイズを保持す
ることにしているかどうかを判定する。一定のサンプル
サイズを保持することにしている場合、ステップ１０８
０で、各グループに対して新規目標サンプルサイズを計
算する。ステップ１０９０で、グループサイズが新規目
標サイズより小さくなるまで、各グループからランダム
なタプルを削除する。

【００８５】サンプルサイズに基づく解析的限界。Ａｑ
ｕａシステムの一実施例は、保証付きの限界を特徴とす
る。これは、ユーザに対して保証を提供するが、場合に
よっては過度に悲観的になる可能性もある。Ａｑｕａ
は、Hoeffding限界に基づいて信頼区間を提供する。Ａ
ｑｕａは結合サンプルＪ（Ｓ_u）を管理しているため、
単一テーブル問合せのみに対するHoeffdingの公式に基
づいて信頼区間を報告することができる。これは、結合
を含む公式よりも計算がずっと高速でずっと精度が高
い。（非外部キー結合を有する問合せに対しては、Ａｑ
ｕａは多重テーブル公式を用いる。）Hoeffding限界を
適用するため、Ａｑｕａが各属性に対する最小値および
最大値に関して管理している限界を使用して、最悪の場
合に属性限界がどのように組み合わされるかを考慮する
ことにより、問合せに生じる式の最小値および最大値に
対する保証付き限界を計算する。問合せ述語が式の部分
式の最小および最大を制限する限り、より良い限界が使
用される。

【００８６】上記の実施例に対して、大サンプル(large
sample)限界も上記のHellersteinの文献で知られてい
る。これは、単なる発見的限界である。大サンプル限界
は、近似的にｐに等しい確率で最終回答を含み、中心極
限定理に基づいている。Hellersteinで指摘されている
ように、真の確率は、公称確率ｐよりもずっと小さい可
能性がある。しかし、この論文では、有限のサンプルが
この限界が成立するほど十分に大きくなるのはいつかを
判定する方法は報告しておらず、実際、必要なサンプル
サイズは、値の分布に依存して大幅に変わりうる。サン
プルに現れる値を観察することはこの点で十分ではな
い。従って、大サンプル限界を考慮することは直接的で
あるかも知れないが、Ａｑｕａはその代わりに保証付き
限界に集中している。

【００８７】サンプルサイズ割当ての評価。以下で、各
関係ごとの結合サンプル間のサンプルサイズの割当ての
有効性を評価するストラテジを提示する。１つの目標
は、広範囲のクラスの問合せが受ける誤差に対する簡単
な解析的限界を提供することである。

【００８８】まず、選択(select)、集計(aggregate)、
ＧＲＯＵＰ ＢＹおよび外部キー結合を有する問合せの
セットＳの以下のような簡単な特徴付けを考える。各関
係Ｒ _iに対して、Ｒ_iが外部キー結合におけるソース関係
であるかまたは結合のない問合せにおける単一の関係で
あるような、Ｓ内の問合せの割合をｆ_iとする。次に、
問合せ内の述語に対する代表（単一テーブル）選択性Ｑ
の範囲を考える。ただし、この選択性は、単一テーブル
の実体化された外部キー結合に基づく。（このような選
択性は、任意の結合選択性以外の追加の述語選択性であ
る。）このような選択性は、問合せ内容によって決定可
能であるが、簡単のためおよび一般性のため、ｑ∈Ｑ′
＝｛．０１，．０２，．０５，．１，．２，．５，１｝
という代表選択性を仮定する。

【００８９】以下では、ＣＯＵＮＴ集計値に注目する。
この集計値は、集計問合せにおける使用に加えて、すべ
てのセット値問合せに対してサイズ推定値を提供するた
めに使用されるので、Ａｑｕａでは最も重要となる。ま
た、これはかなり解析が簡単である。ＣＯＵＮＴ集計値
に対するサンプルの有効性は、相対誤差限界のサイズに
よって測定される。具体的にするため、９０％の確率で
成立することが保証される、相対誤差に対する限界を与
えるHoeffdingの誤差限界を用いる。（未知の）選択性
ｑを有する述語の後の、ｍ個のタプルの関係に関するＣ
ＯＵＮＴを考える。Ｅｒｒｏｒ_q（ｎ）を、サイズｎ≪
ｍのサンプルに基づく推定値に対する相対誤差限界とす
る。ｎ′を、述語を満たすサンプリングされたタプルの
個数とする。すると、μ_n＝ｍ／ｎ・ｎ′は、未知の個
数ｑ・ｍに対する不偏推定量となり、Hoeffdingは、次
式を示した。

【数５】 全体をｑ・ｍで割ると相対誤差が得られ、ｐ＝．９とと
ると次式が得られる。

【数６】 このように、ＣＯＵＮＴに対する相対誤差限界は、サン
プルサイズの平方根とともに減少する。

【００９０】Ｅｒｒｏｒ（ｎ）を、代表選択性Ｑにわた
る平均相対誤差限界、すなわち、

【数７】 とする。例示した代表選択性Ｑ′を用いると、次式を得
る。

【数８】 このように、平均相対誤差限界は、サンプルサイズの平
方根とともに減少し、関係サイズｍとは独立である。さ
らに、２分の１以内の平均誤差限界を有するにはほぼ４
Ｋ個のサンプルで十分である。注意すべき点であるが、
このサンプルサイズは、Hoeffding限界に基づいている
が、これは非常に保守的であることが多い。

【００９１】最後に、平均相対誤差限界の重み付き和と
してすべての関係（ＣＯＵＮＴ集計値に対する）にわた
るサンプルサイズの割当てを評価する。ｎ₁，
ｎ₂，...，ｎ_tを、結合サンプルに対してスキーマ内の
関係Ｒ₁，Ｒ₂，...，Ｒ_tに割り当てられたサンプルサイ
ズとする。すると、重み付き平均相対誤差は次のように
なる。

【数９】

【００９２】

【発明の効果】結論。本明細書では、高速で高精度の近
似問合せ回答を提供するＡｑｕａシステムおよびその方
法の一実施例について説明した。周知のように、結合オ
ペレータは推定精度を大きく劣化させるが、本発明によ
るシステムは、特殊技法を用いて、オンライン分析処理
で良く知られているマルチウェイ外部キー結合を処理す
る。同様に、ＧＲＯＵＰ ＢＹもまた、推定精度を劣化
させることがあるため、本発明によるシステムは、バイ
アス付きサンプリング技術を用いてＧＲＯＵＰＢＹを処
理する。Ａｑｕａは、基礎となるベースデータの小さい
あらかじめ計算されたシノプシスと、Ａｑｕａシステム
で用いられるすべてのシノプシスの増分管理のための新
規で効率的なアルゴリズムを用いて近似回答を提供す
る。本発明によるシステムは、データ分布や、ベースデ
ータがロードされた順序や、ディスク上のデータの配置
に関するいかなる事前の仮定もなしに、精度保証を提供
する。

【００９３】ＴＰＣ−Ｄ問合せに関する解析的限界およ
び実験結果は、データ分布変化があるときでも、Ａｑｕ
ａの有効性を示している。Ａｑｕａは、データウェアハ
ウジング環境で生じる広範囲のクラスの問合せに対する
高速で（問合せ時にベースデータへのアクセスがな
い。）高精度の近似回答を提供する最初のシステムであ
る。

【００９４】Ａｑｕａは、一般にベースデータにアクセ
スせずに回答を提供するため、問合せ中にデータウェア
ハウスから物理的に離れていることが可能であり、それ
により、高い自由度が得られる。例えば、従来のシステ
ム（例えば表３のもの）とは異なり、Ａｑｕａは、ベー
スデータが利用可能でないときにも、近似回答を提供す
ることができる。

【００９５】本発明のシステムのこの実施例は、広範囲
のクラスの問合せに対する回答に注目しているが、特殊
機能をＡｑｕａに追加して、特定のクラスの問合せの精
度を改善することも可能である。この点に関しては、 ・N. Alon, Y. Matias, and M. Szegedi, "The space c
omplexity of approximating the frequency moments",
Proc. 28th ACM Symp. on the Theory of Computing,
pp.20-29, May 1996 ・Gibbons et al., August 1997 ・Barbara et al., 1997 ・Ganti and Poosala, November 1997に報告されてい
る。

【図面の簡単な説明】

【図１】従来のデータウェアハウスシステムの図であ
る。

【図２】本発明の方法を実施することが可能なデータウ
ェアハウスシステムの図である。

【図３】標準的なデータベース問合せに対する例示的な
厳密回答の図である。

【図４】標準的なデータベース問合せに対する例示的な
近似回答の図である。

【図５】厳密回答と近似回答の間の関係を示す図であ
る。

【図６】外部キー結合のみを有する有向非巡回グラフの
図である。

【図７】近似問合せエンジンにおける問合せの処理に関
連するステップを示す図である。

【図８】本発明の方法およびコンピュータ実装された発
明の第１実施例におけるステップを示す図である。

【図９】本発明の方法およびコンピュータ実装された発
明の第１実施例において結合サンプルを管理するステッ
プの図である。

【図１０】本発明の方法およびコンピュータ実装された
発明の第２実施例において結合サンプルを管理するステ
ップの図である。

【符号の説明】

１１０ データウェアハウス １２０ 新規データ １３０ 問合せ １４０ 厳密応答 ２１０ 近似問合せエンジン ３００ 厳密回答 ４００ 近似回答 ４３０ 健全性限界 ６００ 有向非巡回グラフＧ

フロントページの続き (71)出願人 596077259 600 Ｍｏｕｎｔａｉｎ Ａｖｅｎｕｅ, Ｍｕｒｒａｙ Ｈｉｌｌ， Ｎｅｗ Ｊｅ ｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者 フィリップ ビー ジッボンス アメリカ合衆国，07090 ニュージャージ ー，ウエストフィールド，エンブリー コ ート 201 (72)発明者 ヨッシ マチアス イスラエル，69697 テル アビブ，ハミ ッシュマー ハエズラチ 12 (72)発明者 ビスワナス プーサラ アメリカ合衆国，08904 ニュージャージ ー，ハイランド パーク，メイプル コー ト 36 (72)発明者 スリッダー ラマスワミー アメリカ合衆国，07076 ニュージャージ ー，スコッチ プレインズ，スプラス ミ ル レイン 152 (72)発明者 トーステン スエル アメリカ合衆国，07801 ニュージャージ ー，スプリングフィールド，トロイ ドラ イブ 64，アパートメント ビー

Claims (42)

【特許請求の範囲】
1. 【請求項１】 データベースに格納されたデータをサン
   プリングして、該データベースに格納されたデータより
   少ないメモリスペースしか必要としないデータサンプル
   を生成するステップと、 前記データサンプルを近似問合せエンジンのメモリに格
   納するステップと、 前記近似問合せエンジンが、問合せを受け取るステップ
   と、 前記近似問合せエンジンが、格納されているデータサン
   プルで、前記問合せに適合するものを検索するステップ
   と、 前記近似問合せエンジンが、適合した格納されているデ
   ータサンプルにより前記問合せに応答するステップとか
   らなることを特徴とする、データベースの問合せに応答
   する方法。
2. 【請求項２】 前記データサンプルはシノプシスデータ
   構造を含むことを特徴とする請求項１に記載の方法。
3. 【請求項３】 前記適合した格納されているデータサン
   プルの関数により前記問合せに応答するステップをさら
   に有することを特徴とする請求項１に記載の方法。
4. 【請求項４】 応答は、近似回答および精度を含むこと
   を特徴とする請求項３に記載の方法。
5. 【請求項５】 前記精度は保証付き限界を備えることを
   特徴とする請求項４に記載の方法。
6. 【請求項６】 前記保証付き精度は、前記近似回答のま
   わりの誤差限界として定義されることを特徴とする請求
   項５に記載の方法。
7. 【請求項７】 前記誤差限界は最大値および最小値を有
   することを特徴とする請求項６に記載の方法。
8. 【請求項８】 前記近似問合せエンジンが、前記データ
   ベースに定期的に復帰するステップをさらに有すること
   を特徴とする請求項１に記載の方法。
9. 【請求項９】 前記データベースへの復帰は、前記格納
   されているデータサンプルの更新または再充填であるこ
   とを特徴とする請求項８に記載の方法。
10. 【請求項１０】 前記データベースへの復帰は、定期的
    な更新間隔で行われることを特徴とする請求項８に記載
    の方法。
11. 【請求項１１】 前記データベースへの復帰は、問合せ
    のイベントに応じて行われることを特徴とする請求項８
    に記載の方法。
12. 【請求項１２】 前記近似問合せエンジンが、データサ
    ンプルをヒストグラムとして集計する集計ステップをさ
    らに有することを特徴とする請求項１に記載の方法。
13. 【請求項１３】 前記近似回答は、項目のリストの例示
    的項目を含むことを特徴とする請求項４に記載の方法。
14. 【請求項１４】 前記集計ステップは、平均、総和およ
    び個数のうちの１つを含むことを特徴とする請求項１２
    に記載の方法。
15. 【請求項１５】 前記データサンプルは、確率関数に従
    って選択されることを特徴とする請求項１に記載の方
    法。
16. 【請求項１６】 前記確率関数は、前記データベース内
    の少ないタプルを有するグループほど高いレートでサン
    プリングされるように、グループに応じてバイアスが付
    けられることを特徴とする請求項１５に記載の方法。
17. 【請求項１７】 問合せに対する応答において近似回答
    を提供することができない場合、前記データベースをサ
    ンプリングしてシノプシスデータ構造を取得し、取得し
    たシノプシスデータ構造を前記近似問合せエンジンのメ
    モリに格納するステップをさらに有することを特徴とす
    る請求項１に記載の方法。
18. 【請求項１８】 応答は、推定されたメタ情報および代
    表タプルのセットを含むことを特徴とする請求項３に記
    載の方法。
19. 【請求項１９】 前記メタ情報は、厳密回答のサイズの
    推定値および信頼区間を含むことを特徴とする請求項１
    ８に記載の方法。
20. 【請求項２０】 前記代表タプルは、一様ランダムに、
    または、特定の基準に従ってバイアス付きで、厳密回答
    から選択されたタプルであることを特徴とする請求項１
    ８に記載の方法。
21. 【請求項２１】 前記代表タプルは、類似度を有する可
    能タプルであることを特徴とする請求項１８に記載の方
    法。
22. 【請求項２２】 前記代表タプルはそれぞれ、厳密回答
    内のタプルを構成する１個以上のフィールドを含むこと
    を特徴とする請求項１８に記載の方法。
23. 【請求項２３】 前記データサンプルは、結合データサ
    ンプルを含むことを特徴とする請求項８に記載の方法。
24. 【請求項２４】 請求項１に記載の方法のステップを実
    行するコンピュータ実行可能な命令を有するコンピュー
    タ読み取り可能な媒体。
25. 【請求項２５】 請求項３に記載の方法のステップを実
    行するコンピュータ実行可能な命令を有するコンピュー
    タ読み取り可能な媒体。
26. 【請求項２６】 請求項８に記載の方法のステップを実
    行するコンピュータ実行可能な命令を有するコンピュー
    タ読み取り可能な媒体。
27. 【請求項２７】 請求項１２に記載の方法のステップを
    実行するコンピュータ実行可能な命令を有するコンピュ
    ータ読み取り可能な媒体。
28. 【請求項２８】 請求項１７に記載の方法のステップを
    実行するコンピュータ実行可能な命令を有するコンピュ
    ータ読み取り可能な媒体。
29. 【請求項２９】 重み付き平均相対誤差に基づいて前記
    データサンプルのサイズを割り当てるステップをさらに
    有することを特徴とする請求項１に記載の方法。
30. 【請求項３０】 前記重み付き平均相対誤差は、前記デ
    ータサンプルにおいて、前記データサンプル内のすべて
    の関係について、該関係が外部キー結合におけるソース
    関係であるかまたは結合のない問合せにおける唯一の関
    係であるような問合せの割合を、該関係のサンプルサイ
    ズの平方根で割った値に定数値をかけた値として近似さ
    れることを特徴とする請求項２９に記載の方法。
31. 【請求項３１】 データベースの問合せに応答して、該
    データベースに格納されたデータより少ないメモリスペ
    ースしか必要としない、近似問合せエンジンのメモリ内
    の複数のデータサンプルを更新するステップと、 前記問合せが、前記データベースにおけるデータの挿入
    または削除であるかどうかを判定するステップと、 前記問合せがデータの挿入である場合、各タプルに対し
    て、 前記データサンプルに前記タプルを挿入するステップ
    と、 前記問合せがデータの削除である場合、各タプルに対し
    て、 該タプルが前記データサンプル内にある場合、該タプル
    を削除するステップとを実行するコンピュータ実行可能
    な命令を有するコンピュータ読み取り可能な媒体。
32. 【請求項３２】 前記挿入は所定の確率に基づいて実行
    されることを特徴とする請求項３１に記載の媒体。
33. 【請求項３３】 前記データサンプルは、複数のランダ
    ムサンプルおよび複数の結合データサンプルを含むこと
    を特徴とする請求項３１に記載の媒体。
34. 【請求項３４】 前記複数のランダムサンプルは、一様
    に選択されることを特徴とする請求項３３に記載の媒
    体。
35. 【請求項３５】 前記挿入は、 前記タプルのデータベース関係を判定するステップと、 所定の確率に基づいて、前記複数のランダムサンプルの
    うち前記関係に関連するランダムサンプルに前記タプル
    を追加するステップと、 前記タプルが前記ランダムサンプルに追加された場合、 （ａ）前記タプルを用いて新規の結合データサンプルタ
    プルを計算するステップと、 （ｂ）新規結合データサンプルタプルを前記関係に関連
    する結合データサンプルに追加するステップと、 （ｃ）前記ランダムサンプルが最大サイズを超過した場
    合、 （ｉ）前記ランダムサンプル内のタプルのうちの１つを
    ランダムに選択するステップと、 （ｉｉ）ランダムに選択されたタプルを前記ランダムサ
    ンプルから削除するステップと、 （ｉｉｉ）前記結合データサンプルから前記ランダムに
    選択されたタプルに関連する結合データサンプルタプル
    を削除するステップとを含むことを特徴とする請求項３
    ３に記載の媒体。
36. 【請求項３６】 前記挿入は、 前記タプルのデータベース関係を判定するステップと、 所定の確率に基づいて、前記関係に関連する一様ランダ
    ムサンプルに前記タプルを追加するステップと、 前記タプルが前記一様ランダムサンプルに追加された場
    合、 （ａ）前記タプルを用いて新規の結合データサンプルタ
    プルを計算するステップと、 （ｂ）新規結合データサンプルタプルを前記関係に関連
    する結合データサンプルに追加するステップと、 （ｃ）前記一様ランダムサンプルが最大サイズを超過し
    た場合、 （ｉ）前記一様ランダムサンプル内のタプルのうちの１
    つをランダムに選択するステップと、 （ｉｉ）ランダムに選択されたタプルを前記一様ランダ
    ムサンプルから削除するステップと、 （ｉｉｉ）前記結合データサンプルから前記ランダムに
    選択されたタプルに関連する結合データサンプルタプル
    を削除するステップとを含むことを特徴とする請求項３
    ４に記載の媒体。
37. 【請求項３７】 前記削除は、 前記タプルの関係を判定するステップと、 前記タプルが既存のランダムサンプル内にある場合、 （ａ）前記既存のランダムサンプルから前記タプルを削
    除するステップと、 （ｂ）前記関連する結合データサンプルから前記タプル
    に関連する結合データサンプルタプルを削除するステッ
    プとを含み、 前記複数のランダムサンプルのうちのいずれかが所定の
    最小要求サイズより小さくなった場合、 前記所定の最小要求サイズより小さくなった各ランダム
    サンプルを、前記データベースからの新規タプルで再充
    填するステップを含むことを特徴とする請求項３５に記
    載の媒体。
38. 【請求項３８】 前記削除は、 前記タプルの関係を判定するステップと、 前記タプルが既存の一様ランダムサンプル内にある場
    合、 （ａ）前記既存の一様ランダムサンプルから前記タプル
    を削除するステップと、 （ｂ）前記関連する結合データサンプルから前記タプル
    に関連する結合データサンプルタプルを削除するステッ
    プとを含み、 前記複数の一様ランダムサンプルのうちのいずれかが所
    定の最小要求サイズより小さくなった場合、 前記所定の最小要求サイズより小さくなった各一様ラン
    ダムサンプルを、前記データベースからの新規タプルで
    再充填するステップを含むことを特徴とする請求項３６
    に記載の媒体。
39. 【請求項３９】 グループのテーブルにリストされた各
    グループ内のタプルの個数であるサンプルサイズのカウ
    ントを少なくとも含む、生じたグループのテーブルを保
    持するステップと、 所定の最小サイズより小さいサイズのグループに対して
    該グループのサイズが前記所定の最小サイズ以上になる
    まで該グループのサンプリングレートが増大するよう
    に、前記グループのサイズに基づいて各グループのサン
    プリングレートを選択するステップと、 関係に挿入される新規タプルを前記グループのうちの１
    つに追加するステップとを実行するコンピュータ実行可
    能な命令を有するコンピュータ読み取り可能な媒体。
40. 【請求項４０】 前記追加は、 前記関係に挿入される新規タプルがどのグループに属す
    るかを判定するステップと、 前記新規タプルが既存のグループ内にある場合、 （ａ）前記既存のグループのカウントをインクリメント
    するステップと、 （ｂ）前記既存のグループのサンプリングレートに基づ
    いて前記新規タプルを追加するステップとを含み、 前記新規タプルが新規グループに入る場合、 （ａ）前記グループのテーブルに新規グループを、カウ
    ントを１として追加するステップと、 （ｂ）前記既存のグループのサンプリングレートに基づ
    いて前記新規タプルを追加するステップとを含み、 全サンプルサイズが所望のしきい値を超過した場合、 （ａ）前記既存のグループのそれぞれの新規目標サンプ
    ルサイズを計算するステップと、 （ｂ）前記既存のグループのサイズが前記新規目標サン
    プルサイズ以下になるまで前記既存のグループのそれぞ
    れからランダムタプルを除くステップとを含むことを特
    徴とする請求項３９に記載の媒体。
41. 【請求項４１】 生じたグループの個数が所望のしきい
    値を超過した場合、前記グループの個数が該しきい値以
    下になるまで、前記グループのテーブルからグループを
    ランダムに除去するステップをさらに有することを特徴
    とする請求項４０に記載の媒体。
42. 【請求項４２】 前記除去は、カウントの小さいグルー
    プの除去のほうが高い確率になるような確率に従って実
    行されることを特徴とする請求項４１に記載の媒体。