(57)【特許請求の範囲】
【請求項１】
データベースを構成する複数のレコードを記憶するレコード記憶部と、
階層構造を成すとともに、索引情報をインデックスとして保持するB-Tree インデックスに加えて、前記レコード記憶部に記憶されるレコードに応じた、リーフブロック毎のKey 間の平均距離で表す疎密度と、全リーフブロックの前記疎密度の平均値と、全リーフブロックの前記疎密度の標準偏差と、子ノードのレコード数の付加情報を記憶するB-Tree インデックス記憶部と、
ユーザーによる前記データベースからのランダムサンプリングを実行するとのクエリに対応して、サンプリング要求を行うアプリケーションと、
前記アプリケーションからサンプリング要求を受け取り、サンプリング命令に変換する要求変換部と、
前記要求変換部から受け取ったサンプリング命令を解釈してサンプリングレコードを決定し、前記レコード記憶部からサンプリングレコードを取得する場合、前記全リーフブロックの前記疎密度の平均値よりも値の大きな所定値以上の前記疎密度を持つリーフブロックは外れ値を含むとみなして除外し、除外されなかったリーフブロックからレコードを取得するデータ操作部とを、
備えるサンプリング装置。
【請求項２】
前記データベースは、リレーショナルデータベースである請求項１に記載のサンプリング装置。
【請求項３】
前記レコードは１次元のデータに係り、テーブル形式で表される請求項１または請求項２に記載のサンプリング装置。
【請求項４】
前記サンプリング要求では、前記レコード記憶部に記憶される複数のレコード群のうち、サンプリングを実行するレコードの集合として特定される対象レコード記憶領域名と、サンプリングするレコードの数を対象レコード記憶領域の割合で表す取得するレコード数のテーブルに対する割合と、除外するリーフブロックの割合とを指定する請求項１乃至請求項３のいずれか１項に記載のサンプリング装置。
【請求項５】
前記サンプリング要求では、前記レコード記憶部に記憶される複数のレコード群のうち、サンプリングを実行するレコードの集合として特定される対象レコード記憶領域名と、サンプリングするレコードの数と、除外するリーフブロックの数を指定する請求項１乃至請求項３のいずれか１項に記載のサンプリング装置。
【請求項６】
前記リーフブロックは、検索するためのKeyの値とそのKeyに対応するレコードへの前記レコード記憶部上のアドレスの組である請求項１乃至請求項５のいずれか１項に記載のサンプリング装置。
【請求項７】
前記疎密度は、（リーフブロック中のKeyの最大値−リーフブロック中のKeyの最小値）を（リーフブロックのレコード数−１）で除して算出する請求項１乃至請求項６のいずれか１項に記載のサンプリング装置。
【請求項８】
前記リーフブロックの除外判定時の所定値は、（係数×全リーフブロックの前記疎密度の標準偏差）で得られる値を前記全リーフブロックの前記疎密度の平均値に加算したもので、リーフブロックの前記疎密度の分布を正規分布と仮定した場合に、正規分布上で上位の除外する領域を表すのに使用する請求項１乃至請求項７のいずれか１項に記載のサンプリング装置。
【請求項９】
ルートノードで子ノードのレコード数を保持し、ブランチノードでは分岐する範囲毎に子ノードのレコード数を保持し、リーフノードでは現在のレコード数を保持し、子ノードへのランダム・ウォークを行うときに、各子ノードへ移動する確率を計算することにより、各レコードの選択確率を平均化する請求項１乃至請求項８のいずれか１項に記載のサンプリング装置。
【請求項１０】
前記データベースにレコードを新たに挿入してレコードを更新する場合、移動先のレコード数を加算しながら挿入位置を探索し、リーフブロックの個数を２個以下に抑え、子ノードの個数を３個以下に抑えて、挿入位置を決定する請求項１乃至請求項９のいずれか１項に記載のサンプリング装置。
【請求項１１】
前記データ操作部は、除外されなかったリーフブロックからランダムに取得するレコードを決定し、結果セットにまとめて前記アプリケーションに返す請求項１乃至請求項１０のいずれか１項に記載のサンプリング装置。
【請求項１２】
データベースを構成する複数のレコードを記憶するレコード記憶部と、階層構造を成すとともに、索引情報をインデックスとして保持するB-Tree インデックスに加えて、前記レコード記憶部に記憶されるレコードに応じた、リーフブロック毎のKey 間の平均距離で表す疎密度と、全リーフブロックの前記疎密度の平均値と、全リーフブロックの前記疎密度の標準偏差と、子ノードのレコード数の付加情報を記憶するB-Tree インデックス記憶部とを備えるサンプリング装置に、
ユーザーによる前記データベースからのランダムサンプリングを実行するとのクエリに対応して、サンプリング要求を行う機能と、
前記サンプリング要求をサンプリング命令に変換する機能と、
前記サンプリング命令を解釈してサンプリングレコードを決定し、サンプリングレコードを取得する場合、前記全リーフブロックの前記疎密度の平均値よりも値の大きな所定値以上の前記疎密度を持つリーフブロックは外れ値を含むとみなして除外し、除外されなかったリーフブロックからレコードを取得する機能と、
を実現させるためのサンプリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、サンプリング装置およびサンプリングプログラムに関する。
【背景技術】
【０００２】
一般的に、データベースのレコードをランダムサンプリングする場合、多くの外れ値が混入し、元のデータとは分布状況が異なり、正しい解析結果が得られないおそれがある。
【０００３】
元のデータの分布状況を保ったまま、高速にデータのサンプリングを行いたいとの要請に応えるものとして、索引情報を持つB-Tree インデックスを利用して高速にサンプリングを行うことが行われている。
【０００４】
B-Tree インデックスを使用して1次元のデータの外れ値を検出する場合、他の点（レコードのKey 値）間の距離に比べ、点（レコードのKey 値）間の距離が離れている点（レコードのKey 値）が外れ値となる。
【０００５】
厳密に外れ値を検出するためには、全てのレコードについて事前の計算（クラスタリング）が必要である。一般的に、インデックスの情報はサイズの関係上、ハードディスク装置に保持されるので、クラスタリングを行うには、ハードディスク装置からのリードと、Ｏ(nlogn)の計算コストが必要である、という問題があった。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Donald  E. Knuth 「The Art of Computer Programming」 Volume 3   Sorting and Searching,  1973, 723p
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、１次元データをクラスタリングなどで分類すること無く、データの分布を保ったまま、外れ値を除外したランダムサンプリングを高速に行うことができるサンプリング装置およびサンプリングプログラムを提供することである。
【課題を解決するための手段】
【０００８】
実施形態のサンプリング装置は、データベースを構成する複数のレコードを記憶するレコード記憶部と、階層構造を成すとともに、索引情報をインデックスとして保持するB-Tree インデックスに加えて、前記レコード記憶部に記憶されるレコードに応じた、リーフブロック毎のKey 間の平均距離で表す疎密度と、全リーフブロックの前記疎密度の平均値と、全リーフブロックの前記疎密度の標準偏差と、子ノードのレコード数の付加情報を記憶するB-Tree インデックス記憶部と、ユーザーによる前記データベースからのランダムサンプリングを実行するとのクエリに対応して、サンプリング要求を行うアプリケーションと、前記アプリケーションからサンプリング要求を受け取り、サンプリング命令に変換する要求変換部と、前記要求変換部から受け取ったサンプリング命令を解釈してサンプリングレコードを決定し、前記レコード記憶部からサンプリングレコードを取得する場合、前記全リーフブロックの前記疎密度の平均値よりも値の大きな所定値以上の前記疎密度を持つリーフブロックは外れ値を含むとみなして除外し、除外されなかったリーフブロックからレコードを取得するデータ操作部とを、備える。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施形態に係るサンプリング装置の概略構成を示すブロック図である。
【図２】ランダムサンプリングに伴う外れ値を説明する図である。
【図３】除外するリーフブロックを説明する図である。
【図４】正規分布図と除外する割合を説明する図である。
【図５】疎密度を付加したB-Treeインデックスの構造を示した図である。
【図６】特定のリーフブロックへのレコードの偏在を説明する図である。
【図７】選択確率を考慮したB-Treeにおけるランダムサンプリングを説明する図である。
【図８】B-Treeの更新の手順と再計算の範囲を説明する図である。
【図９】B-Treeの更新の手順と再計算の範囲を説明する図である。
【図１０】B-Treeの更新の手順と再計算の範囲を説明する図である。
【図１１】B-Treeの更新の手順と再計算の範囲を説明する図である。
【図１２】B-Treeの更新の手順と再計算の範囲を説明する図である。
【図１３】サンプリング装置におけるB-Tree構築処理の流れを説明するフローチャートである。
【図１４】サンプリング装置におけるランダムサンプリング処理の流れを説明するフローチャートである。
【図１５】実施例におけるサンプリング要求に対する処理を説明する図である。
【図１６】実施例における疎密度の標準偏差の計算を説明する図である。
【図１７】実施例におけるサンプリングレコードの決定を説明する図である。
【図１８】実施例におけるサンプリングレコードの決定およびリーフブロックの除外を説明する図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。
【００１１】
まず、本実施形態で用いる主要な用語について説明する。
【００１２】
「レコード」とは、データベースを構成する単位のひとつで、データの１件分のことである。
【００１３】
「ルートノード」とは、B-Treeの一番上にあるノードをいう。
【００１４】
「リーフノード」とは、B-Tree上の一番下、リーフブロックとつながっているノードをいう。
【００１５】
「ブランチノード」とは、ルートノードとリーフノードの間にあるノードをいう。
【００１６】
「リーフブロック」は、B-Treeインデックスにおいては、リーフノードとつながっている、検索するためのKeyの値とそのKeyに対応するレコードへのアドレスの組を指す。リーフブロックによっては、複数の組を保持する。
【００１７】
「子ノード」とは、自分から枝が出ているノードをいう。自分の上のノードは親ノードである。
【００１８】
「サンプリング」とは、データ分析の際、データが巨大などの理由で一部のレコードを抽出することをいう。無作為にサンプリングを行うことランダムサンプリングという。本実施形態においては、B-Treeインデックスを利用して、リーフブロックからレコードをランダムサンプリングする。
【００１９】
「外れ値」とは、他の値とは大きく異なり、計算によってはデータの傾向がつかめなくなる恐れのあるデータをいう。本実施形態においては、B-Treeインデックスを使用して１次元のデータの外れ値を検出するもので、他の点（レコードのKey 値）間の距離に比べ、点（レコードのKey 値）間の距離が離れている点（レコードのKey 値）が外れ値となる。
【００２０】
「カーソル」とは、B-Tree上で、現在操作しているノードのポインタをいう。B-Treeでは、ルートノードやブランチノードが子ノードへのポインタをもち、カーソルはこの値を元に子ノードへ移動していく。
【００２１】
「結果セット」とは、データベースから取り出されたレコード群（レコードの集合）をいう。データベースにSELECTなどの結果が帰ってくる命令を与えた場合に返却される。
【００２２】
本実施形態においては、B-Treeからリーフブロック毎のKey間の平均距離の情報を疎密度として算出し、相対的に疎密度の値が大きいリーフブロックが外れ値を含むとみなして除外することで、厳密に外れ値を計算せずに、ランダムサンプリングを高速化させるものである。
【００２３】
図１は、本発明の実施形態に係るサンプリング装置の概略構成を示すブロック図である。この装置は汎用のコンピュータ（例えばパーソナルコンピュータ（PC）等）と、同コンピュータ上で動作するソフトウェアとを用いて実現される。コンピュータとしては、CAD（Computer Aided Design）やCAE（Computer Aided Engineering）に好適なエンジニアリングワークステーション（EWS）等も含む。本実施形態はこのようなコンピュータに、データベースを構成する複数のレコードを記憶するレコード記憶部と、階層構造を成すとともに、索引情報をインデックスとして保持するB-Tree インデックスに加えて、レコード記憶部に記憶されるレコードに応じた、リーフブロック毎のKey 間の平均距離で表す疎密度と、全リーフブロックの疎密度の平均値と、全リーフブロックの疎密度の標準偏差と、子ノードのレコード数の付加情報を記憶するB-Tree インデックス記憶部とを備えるサンプリング装置に、ユーザーによるデータベースからのランダムサンプリングを実行するとのクエリに対応して、サンプリング要求を行う機能と、サンプリング要求をサンプリング命令に変換する機能と、サンプリング命令を解釈してサンプリングレコードを決定し、サンプリングレコードを取得する場合、全リーフブロックの疎密度の平均値よりも値の大きな所定値以上の疎密度を持つリーフブロックは外れ値を含むとみなして除外し、除外されなかったリーフブロックからレコードを取得する機能とを、実現させるためのサンプリングプログラムとして実施することもできる。
【００２４】
図１に示すように、本実施形態に係るサンプリング装置１は、主として、アプリケーション１１、要求変換部１２、データ操作部１３、レコード記憶部１４、B-Treeインデックス記憶部１５から構成されている。
【００２５】
レコード記憶部１４は、レコード記憶領域１、レコード記憶領域２、・・・等から成り、データベースを構成する複数のレコードを記憶するものである。データベースとしては、例えば、リレーショナルデータベースが該当するが、これに限定されるものではない。レコードは、例えば、テーブル形式で表すことができる。テーブルは、行と列で表される１次元データの集まりで、データのタイトルを表わす「列（またはカラム）」に対し、縦に並んでいるそれぞれのデータが「行（またはロウ）」であり、１行が１つのデータで、カラムがそれぞれの属性の値を表す。１件分のデータが、レコードである。
【００２６】
データ操作部１３からランダムサンプリングを行うレコード記憶領域が指定された場合に、レコード記憶部１４の該当するレコード記憶領域からレコードが取得される。レコードの取得の詳細については後述する。
【００２７】
アプリケーション１１は、サンプリング装置１のユーザーがコンピュータ上で実行したい作業を実行する機能を直接的に有するソフトウェアであって、本実施形態では、例えば、サンプリング装置１におけるサンプリング取得およびレコード更新の作業を実行させるものである。
【００２８】
アプリケーション１１は、ユーザーによるデータベースからランダムサンプリングを実行するとのクエリに対応して、サンプリングレコード取得時には、要求変換部１２に対してサンプリング要求を行う。サンプリング要求に際しては、（１）対象レコード記憶領域名、（２）取得するレコード数のテーブルに対する割合(％)、（３）除外するリーフブロックの割合(％)、を指定する。ここで、対象レコード記憶領域名は、レコード記憶部１４に記憶される複数のレコード群のうち、サンプリングを実行するレコードの集合として特定されるものである。例えば、“TEST”のように名付けられる。
【００２９】
取得するレコードのテーブルに対する割合(％)は、サンプリングするレコードの数を、指定レコード記憶領域の割合で指定するものである。
【００３０】
除外するリーフブロックの割合(％)は、リーフブロックの疎密度（後ほど詳述する）の分布を正規分布と仮定し、正規分布上で上位何％を除外するかを指定するものである。例えば、ユーザーは大きく外れているリーフブロックだけを除外したい場合には０．１％、確実に外れ値を除外したい場合には５％といった要求を出す。尚、取得するレコード数のテーブルに対する割合(％)に代えて、取得するレコード数そのものを指定することでもよい。さらに、除外するリーフブロックの割合(％) に代えて、除外するリーフブロック数そのものを指定することでもよい。
【００３１】
ユーザーは、例えば、サンプリングレコードの取得をするために、データベース管理システムにおいてデータの操作や定義を行うためのデータベース言語であるSQLの一命令であるSELECT文で、サンプリング要求を次のように記述する。
【００３２】
“SELECT  ＊ FROM TEST, RANDSAMPLE(１０,５);”
このSELECT文では、ランダムサンプリングする対象レコード記憶領域が“TEST”という名のレコード記憶領域であり、サンプリングするレコード数の割合が１０％、外れ値を除外する割合が５％と、指定されている。
【００３３】
アプリケーション１１は、ユーザーによるデータベースに対するレコード更新を実行するとのクエリに対応して、レコード更新時には、要求変換部１２に対してレコード更新要求を出す。レコード更新は、例えば、Key値＝６というレコードを対象レコード記憶領域に新たに挿入する要求である。
【００３４】
要求変換部１２は、サンプリングレコード取得時には、上述のように指定されたサンプリング要求をアプリケーション１１から受け取った後、サンプリング命令に変換する。変換後のサンプリング命令は、データ操作部１３に送られる。
【００３５】
要求変換部１２は、レコード更新時には、レコード更新要求をアプリケーション１１から受け取った後、レコード更新命令に変換する。
【００３６】
データ操作部１３は、サンプリングレコード取得時には、要求変換部１２から受け取ったサンプリング命令を解釈して、サンプリングレコードを決定する。決定されたサンプリングレコードは、レコード記憶部１４の指定されたレコード記憶領域から取得される。データ操作部１３は、B-Tree インデックス記憶部１５から読み込んだB-Tree を自己のメモリ（図示しない）上に構築し、ランダムに移動しながら読み込むレコードを決定する処理を行う。
【００３７】
後述するように、疎密度に応じて除外すると判定されたリーフブロック以外に属するサンプリングレコードが、レコード群である結果セットとしてアプリケーション１１に送られる。
【００３８】
データ操作部１３は、レコード更新時には、要求変換部１２から受け取ったレコード更新命令を解釈して、レコードの更新を実行するレコード記憶領域を決定する。更新レコードは、レコード記憶部１４の指定されたレコード記憶領域に書き込まれる。
【００３９】
データ操作部１３は、更新レコードに応じて、B-Tree を更新するためにデータを生成する。B-Tree を更新するデータは、B-Tree インデックス記憶部１５に送られる。
【００４０】
B-Tree インデックス記憶部１５は、B-Tree を恒久的に保存する場所であり、例えば、ハードディスク記憶装置で構成するのが好適である。B-Tree インデックス記憶部１５には、B-Treeのルートノード、ブランチノード、リーフノード、リーフブロックの全てが保存される。
【００４１】
本実施形態においては、レコード更新時には、データ操作部１３から受け取ったB-Tree を更新するデータに応じて、（１）疎密度（リーフブロックの距離の平均値）、（２）全リーフブロックの疎密度の平均値、（３）全リーフブロックの疎密度の標準偏差、（４）子ノードのレコード数、の情報をB-Tree に付加したB-Tree インデックスを記憶するものである。尚、初期状態では、レコード記憶部１４のレコード記憶領域１、レコード記憶領域２、・・・等に記憶されるレコードに応じた（１）疎密度（リーフブロックの距離の平均値）、（２）全リーフブロックの疎密度の平均値、（３）全リーフブロックの疎密度の標準偏差、（４）子ノードのレコード数の付加情報が記憶されている。
【００４２】
B-Treeを使用する場合には、B-Tree インデックス記憶部１５から一時的にメモリ（図示しない）上 にデータを読み込み、B-Treeを構築し処理を行う。しかし、B-Tree全てをメモリ上に構築するとサイズ制約があり、全リーフブロックをメモリ上に読み込めない場合がある。そこで、メモリ上にはルートノード、ブランチノード、リーフノードのみを構築しておき、必要に応じて、リーフブロックをB-Tree インデックス記憶部１５から読み込む。従来の手法では、全レコードの情報を計算する必要があるため、全てのリーフブロックをハードディスク記憶装置から読み込んでいたが、本実施形態によれば、ランダムに移動した先のリーフブロックだけを読み込むだけでよいので、ハードディスク記憶装置の読み込み回数を減らせることができる。
【００４３】
＜外れ値＞
ランダムサンプリングを実行する場合、外れ値を多く選んでしまい、元のデータとは分布状況が異なってしまい、解析結果がおかしくなる可能性がある。
【００４４】
図２は、ランダムサンプリングに伴う外れ値を説明する図である。図２に示すように、外れ値を多くサンプリングすると、実データとは分布状況大きく異なってしまう場合がある。そこで、１次元データの構造をある程度維持して、外れ値を除外した部分を取得することが重要となる。
【００４５】
本実施形態においては、B-Tree インデックスを使用して、他の点（レコード）間の距離に比べ、点（レコード）間の距離が離れている１次元のデータ（レコード）を外れ値とするもので、疎密度（後述する）の値が大きいリーフブロックをサンプリング対象から除外するものである。
【００４６】
図３は、除外するリーフブロックを説明する図である。ルートノードでは、Key値と下層のブランチノードへのポインタを管理している。Key値が指定された場合に、次にどのブランチノードに進めばよいかがわかる。ブランチノードでは、Key値を更に細かく分割するとともに下層のリーフノードへのポインタを管理している。リーフノードは、最下層のノードであり、Key値とKey値に対応するレコードが記憶されているレコード記憶領域の物理的な位置を管理している。
【００４７】
図３に示す例では、  ルートノードは、Key値＝６１であり、Key値が２９である左側のブランチノードと、Key値が８１である右側のブランチノードへのポインタを管理している。検索Key値が６１よりも小さい場合には、左側のブランチノードに分岐し、検索Key値が６１よりも大きい場合には、右側のブランチノードに分岐する。Key値＝２９の左側のブランチノードでは、Key値が３乃至８である左側のリーフノードと、Key値が５２乃至５７である右側のリーフノードへのポインタを管理している。
【００４８】
検索Key値が２９よりも小さい場合には、左側のリーフノードに分岐し、検索Key値が２９よりも大きい場合には、右側のリーフノードに分岐する。図３に示す最左側のリーフノードでは、検索Key値が３以下の場合のレコード数、検索Key値が３と８の間にある場合のレコード数、検索Key値が８以上の場合のレコード数が管理されている。他のリーフノードでも同様である。リーフノードには、Key値と当該Keyに対応するレコードへのアドレスの組から成るリーフブロックがつながっている。
【００４９】
本実施形態では、リーフブロックの点間の平均距離が他のリーフブロックよりも大きければ外れ値を含む可能性が高いため、除外する。図３に示す例では、Key値が８以上の場合のリーフブロックの範囲は、他のリーフブロックの範囲に比べ大きいので、外れ値を含む可能性があり、除外対象とする。したがって、Key値が８以上の場合のリーフブロックからは、レコードを取得しないことになる。
【００５０】
＜疎密度＞
本実施形態においては、「リーフブロック毎のKey間の平均距離」を疎密度と定義する。具体的には、疎密度は、（リーフブロック中のKeyの最大値−リーフブロック中のKeyの最小値）を（リーフブロックのレコード数-１）で除して得られる。尚、リーフブロック中に1レコードしかない場合は、疎密度の判定は行わない。
【００５１】
疎密度の数値自体が小さければ（Key間の平均距離が短い）、疎密度が高くて密であり、疎密度の数値自体が大きければ（Key間の平均距離が長い）、疎密度が低くて疎である。B-Tree はソートされているため疎密度の数値自体が大きいほど、点間の距離が離れている点を含む可能性が高い。
【００５２】
＜リーフブロックの除外の判定＞
本実施形態では、他のリーフブロックに比べ、相対的に疎なリーフブロックを除外する。他の点間の距離に比べ、点間の距離が離れている点を除外するには、複数のリーフブロック中から、（Keyの最大値−Keyの最小値）の値が大きいリーフブロックを除外する。
【００５３】
換言すれば、疎密度の数値自体が大きいものは疎であるのでサンプリング対象とするリーフブロックから除外し、疎密度の数値自体が小さいものは密であるのでサンプリング対象とするリーフブロックから除外しない。
【００５４】
ユーザーは正規分布上で疎なリーフブロックの上位何％を除外するか、パーセンテージで指定することができる。具体的には、疎密度の全体平均値よりも、ある値以上の疎密度を持つリーフブロックを除外する。
【００５５】
例えば、除外判定の閾値は、以下の式で示される。
【数１】
0006411232.tif 000002
【００５６】
上記した除外判定の閾値以上の疎密度を持つリーフブロックを、サンプリング対象とするリーフブロックから除外する。係数Ｑは、ユーザーから指定されるパーセンテージから求め、リーフブロックの疎密度を正規分布と仮定し、既存の手法で計算する。例えば、統計学の「パーセント点」を用いることが好適であり、正規分布において、上側確率が２．５％となるパーセント点は１．９６である。
【００５７】
図４は、正規分布図と除外する割合を説明する図である。図４に示すように、正規分布図の面積が、その範囲内に疎密度が存在するリーフブロックのパーセンテージとなる。図４に示す正規分布図では、中央値となる全体の疎密度の平均値よりも右側にいくほど、疎密度の数値が大きい（Key間の平均距離が長い）ことを示している。疎密度の数値が小さい（Key間の平均距離が短い）場合は、外れ値を含む可能性が低くサンプリング対象から除外する必要がないため、正規分布図の中央値の左側は全て含む。
0006411232.tif 000003
【００５８】
＜疎密度を付加したB-Tree インデックスの構造＞
図５は、疎密度を付加したB-Tree インデックスの構造を示した図である。図５に示すように、ルートノードでは、Key値と子ノードのレコード数および下層のブランチノードへのポインタを管理している。Key値が指定された場合に、次にどのブランチノードに進めばよいかがわかる。ブランチノードでは、Key値を更に細かく分割するとともに子ノードのレコード数および下層のリーフノードへのポインタを管理している。リーフノードは、最下層のノードであり、Key値、子ノード（リーフブロック）のレコード数、子ノード（リーフブロック）毎の疎密度およびKey値に対応するレコードが記憶されているレコード記憶領域の物理的な位置を管理している。
【００５９】
図５に示す例では、ルートノードのKey値＝６１であり、左側のブランチノードのレコード数は１０個、右側のブランチノードのレコード数は７個で、子ノードのレコード数は合計で１７個となっている。検索Key値が６１よりも小さい場合には、左側のブランチノードに分岐し、検索Key値が６１よりも大きい場合には、右側のブランチノードに分岐する。
【００６０】
同様に、左側のブランチノードでは、Key値＝２９であり、左側のリーフノードのレコード数は６個、右側のリーフノードのレコード数は４個で、子ノードのレコード数は合計で１０個となっている。検索Key値が２９よりも小さい場合には、左側のリーフノードに分岐し、検索Key値が２９よりも大きい場合には、右側のリーフノードに分岐する。図５に示す最左側のリーフノードでは、Key値が３以下の場合の２個のレコード数、Key値が３と８の間にある場合の２個のレコード数、Key値が８以上の場合の２個のレコード数が管理されている。他のリーフノードでも同様である。本実施形態では、Key間の平均距離を表す疎密度がリーフノード毎に管理されている。最左側のリーフノードでは、Key値が３以下の場合の疎密度が２、Key値が３と８の間にある場合の疎密度が３、Key値が８以上の場合の疎密度が２０であると管理されている。さらに、リーフノードには、Key値と当該Keyに対応するレコードへのアドレスの組から成るリーフブロックがつながっている。
【００６１】
＜B-Treeによるランダムサンプリング＞
B-Treeでは、ブランチノードの分岐数やリーフブロック中のレコード数が、ツリーによって異なるため、サンプリング時に移動（分岐方向）をランダムにすると、取得されるレコードに偏りが生じる。
【００６２】
図６は、特定のリーフブロックへのレコードの偏在を説明する図である。尚、図６では、子ノードのレコード数、疎密度は図示していない。図６に示すB-Treeでは、Key値＝２９の左側ブランチノードにぶら下がるリーフ数が６、右側ブランチノードにぶら下がるリーフ数が４と、リーフノードのレコード数にばらつきがある。そのため、ルートノードからKey値＝２９の左側ブランチノードを経て、Key値＝５２乃至５７の右側リーフノードへとランダムに移動してレコードを取得していくと、取得されるレコード数に偏りが生じる。
【００６３】
図７は、選択確率を考慮したB-Treeにおけるランダムサンプリングを説明する図である。尚、図７では、疎密度は図示していない。図７に示すように、ルートノード、ブランチノードで子ノードのレコード数を保持する。すなわち、ブランチノードでは分岐する範囲毎に子ノードのレコード数を保持し、リーフノードでは現在のレコード数を保持し、子ノードへのランダム・ウォークを行うときに、各子ノードへ移動する確率を計算し決定するのが好適である。これにより、各レコードの選択確率を平均化することが可能となる。
【００６４】
＜B-Treeの再構築＞
図８乃至図１２は、B-Treeの更新の手順と再計算の範囲を説明する図である。図８に示すように、疎密度を付加したB-Treeインデックス構造において、Key値＝６という挿入レコードを追加する。図９に示すように、移動先の子ノードのレコード数を加算しながら挿入位置を探索していく。まず、ルートノードから、Key値＝２９の左側ブランチノードに移動する。その結果、ルートノードが保持する子ノードのレコード数は１１となる。同様に、ブランチノードでは、左側のリーフノードに移動していくので、ブランチノードが保持する子ノードのレコード数は７となる。挿入レコードは、Key値＝６であるので、リーフノードのKey値＝３とKey値＝８の間に該当するので、中央のブロックに挿入される。その結果、図９に示すように、中央のリーフノードにつながるリーフブロック数は、３個となる。B-treeを再構築する場合の、適切なリーフノードにつながるリーフブロック数は、ユーザーが任意に設定することができる。尚、図９に示す例では、図を見やすくするため、リーフノードにつながるリーフブロックは最大で２個までにする。
【００６５】
図１０に示すように、全てのリーフノードにつながるリーフブロックが２個になるようにリーフノードを細分化すると、最左側のリーフノードにつながる子ノード（リーフブロック）数は４個となる。さらに、リーフノードの状態の変化に伴い疎密度も変化している。B-treeを再構築する場合の、適切な子ノード（リーフブロック）数は、ユーザーが任意に設定することができる。尚、図１０に示す例では、図を見やすくするため、リーフノードにつながる子ノード（リーフブロック）数は最大で３個までにする。
【００６６】
そこで、図１１に示すように、Key値＝３のリーフノードとKey値＝８のリーフノードに分解する。これに伴い、左側のブランチノードもKey値＝６と、Key＝２９の分岐となるように分解する。この場合、ブランチノードの状態が変化したためレコード数を再計算する必要が生じる。
【００６７】
図１２は、レコードの更新による計算が必要となる箇所を説明する図である。本実施形態では、疎密度の再計算が必要な場所は、通常のB-treeの更新部分と同じである。そのため、更新の計算量はlog(n)となる。
【００６８】
＜B-Tree構築処理の流れ＞
以上のようにして構成されたサンプリング装置１におけるB-Tree構築処理の流れについて説明する。図１３は、サンプリング装置１におけるB-Tree構築処理の流れを説明するフローチャートである。
【００６９】
まず、カーソルをルートノードへ移動する（ステップＳ１３１）。
【００７０】
次に、挿入するKeyの範囲のノードへカーソルを移動する。移動前に移動先ノードのレコード数を１加算する（ステップＳ１３２）。
【００７１】
続いて、カーソルの位置がリーフノードであるか否かを判定する（ステップＳ１３３）。カーソルの位置がリーフノードでなければ（ステップＳ１３３でＮｏ）、ステップＳ１３２に戻り、カーソルの位置がリーフノードであれば（ステップＳ１３３でＹｅｓ）、Keyとレコードのアドレスをリーフブロックに追加する（ステップＳ１３４）。
【００７２】
次に、リーフブロックに規定数以上のレコードがあるか否かを判定する（ステップＳ１３５）。ここで、規定数は、B-Treeを再構築するか否かの閾値となるものである。特定のリーフブロックに多くのレコードが偏在することを避け、各レコードの選択確率を平均化するために、子ノードのレコード数を管理するのが好適である。
【００７３】
リーフブロックに規定数以上のレコードがなければ（ステップＳ１３５でＮｏ）、追加を行ったリーフブロックの疎密度を再計算し、リーフノードへ保存（ステップＳ１３６）し、B-Tree構築処理を終了する。
【００７４】
一方、リーフブロックに規定数以上のレコードがあれば（ステップＳ１３５でＹｅｓ）、B-Treeの再構築を実行する（ステップＳ１３７）。
【００７５】
続いて、再構築の影響を受けた各リーフブロックの疎密度と、子ノードのレコード数を再計算してリーフノードへ保存（ステップＳ１３８）し、B-Tree構築処理を終了する。
【００７６】
＜ランダムサンプリング処理の流れ＞
以上のようにして構成されたサンプリング装置１におけるランダムサンプリング処理の流れについて説明する。図１４は、サンプリング装置１におけるランダムサンプリング処理の流れを説明するフローチャートである。
【００７７】
まず、要求変換部１２は、レコードのサンプリング数と、リーフブロックの除外判定時に必要な係数Qを、ユーザーが指定した入力から決定する（ステップＳ１４０１）。
【００７８】
次に、データ操作部１３は、全てのリーフノードに移動し、全リーフブロックの疎密度の標準偏差σと全リーフブロックの疎密度の平均値を計算する（ステップＳ１４０２）。
【００７９】
次に、カーソルをルートノードへ移動する（ステップＳ１４０３）。
【００８０】
次に、カーソルを子ノードへ移動する（ステップＳ１４０４）。
【００８１】
続いて、カーソルの位置がリーフノードであるか否かを判定する（ステップＳ１４０５）。
【００８２】
カーソルの位置がリーフノードでなければ（ステップＳ１４０５でＮｏ）、ステップＳ１４０４に戻り、カーソルの位置がリーフノードであれば（ステップＳ１４０５でＹｅｓ）、リーフノードにつながっているリーフブロックの１つをランダムに選択する（ステップＳ１４０６）。
【００８３】
次に、選択したリーフブロックの疎密度が、リーフブロックを除外する際の閾値よりも小さいか否かを判定する（ステップＳ１４０７）。
【００８４】
選択したリーフブロックの疎密度が、リーフブロックを除外する際の閾値よりも小さくなければ（ステップＳ１４０７でＮｏ）、当該リーフブロックはサンプリングレコードに適さないので除外し、ステップＳ１４０３に移行する。
【００８５】
一方、選択したリーフブロックの疎密度が、リーフブロックを除外する際の閾値よりも小さければ（ステップＳ１４０７でＹｅｓ）、選択したリーフブロックから取得するレコードをランダムに１つ決定し結果セットへ挿入する（ステップＳ１４０８）。
【００８６】
次に、結果セットに取得したレコードの総数が指定されたサンプリング数に達しているか否かを判定する（ステップＳ１４０９）。
【００８７】
指定されたサンプリング数に達していなければ（ステップＳ１４０９でＮｏ）、引き続きランダムサンプリングを実行するためにステップＳ１４０３に移行する。
【００８８】
一方、指定されたサンプリング数に達していれば（ステップＳ１４０９でＹｅｓ）、結果セットをアプリケーションへ返して（ステップＳ１４１０）、ランダムサンプリング処理を終了する。
【００８９】
［実施例］
次に、本実施形態の実施例について説明する。ここでは、図５に示すB-treeインデックス構造において、ランダムサンプリングを実行する実施例について説明する。図１５は、実施例におけるサンプリング要求に対する処理を説明する図である。
【００９０】
アプリケーション１１は、ユーザーによるデータベースからランダムサンプリングを実行するとのクエリに対応して、要求変換部１２に対して図１５に示すようなサンプリング要求が行われた。ここでは、“TEST”と名付けられた対象レコード記憶領域に対して、サンプリングするレコードの数を指定レコード記憶領域の１０％と指定され、除外するリーフブロックの割合が５％と指定されている。
【００９１】
ルートノード（Key値＝６１）の子ノードのレコード数は１０＋７＝１７なので、サンプリングレコード数を１７×０．１ ≒ ２レコードと決定する。
0006411232.tif 000004
【００９２】
図１６は、実施例における疎密度の標準偏差の計算を説明する図である。図１６に示すように、全てのリーフノードに移動して疎密度を取得する。取得した疎密度に基づき疎密度の標準偏差と平均値を計算する。実施例では、リーフブロックの除外判定の閾値は、６．０＋１．６×６．０＝１５．６となる。
【００９３】
図１７は、実施例におけるサンプリングレコードの決定を説明する図である。図１７に示すように、除外判定の閾値と疎密度を比較する。実施例では、リーフブロックの除外判定の閾値が１５．６であるため、レコードを１つランダムで選択する。取得したレコード総数が、サンプリング数として指定された数でなければルートノードに移動する。
【００９４】
図１８は、実施例におけるサンプリングレコードの決定およびリーフブロックの除外を説明する図である。図１８に示すように、リーフブロックの除外判定の閾値が１５．６であるのに対し 、選択したリーフブロックの疎密度が２０であるため、除外するリーフブロックと判断する。そこで、当該リーフブロックにつながるレコードは、サンプリングレコードとはせずに、ルートノードに移動する。
【００９５】
以上を、取得したレコード総数が、サンプリング数として指定された数に到達するまで繰り返す。
【００９６】
本実施形態によれば、ランダムサンプリングの実行に際して、レコード数をｎとすると、厳密にKeyの外れ値を計算する場合と比べて計算量を１／ｎに少なくすることができる。
【００９７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９８】
１・・・サンプリング装置
１１・・・アプリケーション
１２・・・要求変換部
１３・・・データ操作部
１４・・・レコード記憶部
１５・・・B-tree インデックス記憶部
【図１】
0006411232.tif 000005
【図２】
0006411232.tif 000006
【図３】
0006411232.tif 000007
【図４】
0006411232.tif 000008
【図５】
0006411232.tif 000009
【図６】
0006411232.tif 000010
【図７】
0006411232.tif 000011
【図８】
0006411232.tif 000012
【図９】
0006411232.tif 000013
【図１０】
0006411232.tif 000014
【図１１】
0006411232.tif 000015
【図１２】
0006411232.tif 000016
【図１３】
0006411232.tif 000017
【図１４】
0006411232.tif 000018
【図１５】
0006411232.tif 000019
【図１６】
0006411232.tif 000020
【図１７】
0006411232.tif 000021
【図１８】
0006411232.tif 000022