(57)【要約】結論セット（２０、２２、２４、２６、２８および３０）が階層的な一連のレベル（レベル１、レベル２、レベル３）に分割されるデータベースが提供される。データは、第１レベル（レベル１）の結論セットがフルになるような時まで、この第１レベルの結論セットに追加される。その後、データは、その結論セット（２０）からその下位の結論セット（２４、２６）に移動される。したがって、複数のエントリが、比較的少ないディスクアクセス操作で移動されるので、データをデータベースに追加するのに必要なディスクのアクセス量が削減される。
2004528634.tif 000002
【特許請求の範囲】
【請求項１】
データベース（２）のデータの記憶を編成する方法であって、
前記データベースの結論セット（２０、２４、２６、２８、３０、４０、５０、６０）は、階層的構造体に配置され、
前記結論セットは、項目の数が第１レベルの位（レベル１）の選択された結論セットの閾値に達するまで、項目が該選択された結論セットに挿入されるように配置され、その後、前記選択された結論セットの内容が、下位の結論セットに移動され、これにより、前記選択された結論セットが空にされる、方法。
【請求項２】
それぞれの結論セット（２０、２４、２６、２８、３０）は、０個、１個または２個のすぐ下位の結論セットを有する、請求項１に記載の方法。
【請求項３】
移動中、前記すぐ下位の結論セットのいずれにエントリを転送するかを選択するために、前記選択された結論セットの前記データは、探索基準と比較される、請求項１または２に記載の方法。
【請求項４】
前記データベースは、決定グラフを含み、前記探索基準は、事実上、前記決定グラフの延長である、請求項３に記載の方法。
【請求項５】
前記結論セットの階層的構造体は、層状の構造体に配置される、前記請求項のいずれか１項に記載の方法。
【請求項６】
前記層状の構造体は、Ｌ個のレベルを備え、第１レベルから第（Ｌ−１）レベルまでの各結論セットは、それぞれ第２レベルから第Ｌレベルの２つのすぐ下位の結論セットを有する、請求項５に記載の方法。
【請求項７】
Ｎを１から（Ｌ−１）までのある整数とすると、第Ｎレベルの所定の結論セットが、所定の個数のエントリを有すると、該結論セットの内容は、そのすぐ下位の結論セットに移動される、請求項６に記載の方法。
【請求項８】
所定の値より上の階層的な位を有する結論セットは、使用に際して、高速メモリに記憶される、前記請求項のいずれか１項に記載の方法。
【請求項９】
前記結論セット（４０、５０、６０）は、前記データベースの決定グラフの全体にわたって分散される、請求項１に記載の方法。
【請求項１０】
前記決定グラフは、前記決定グラフの大部分にわたって、指定された結論セット間の距離を維持するように構築される、請求項１または９に記載の方法。
【請求項１１】
結論セットからのデータの移動中、該データは、その具体的なデータの内容に基づいて、下位の結論セットに移動される、請求項９または１０に記載の方法。
【請求項１２】
結論セットの前記内容は、一斉に移動される、請求項１、９、１０または１１に記載の方法。
【請求項１３】
データベースの結論セットが、階層的構造体に配置され、前記結論セットは、項目の数が第１レベルの位の選択された結論セットの閾値に達するまで、項目が該選択された結論セットに挿入されるように配置され、その後、前記選択された結論セットの内容が、下位の結論セットに移動され、これにより、前記選択された結論セットが空にされる、データベース。
【請求項１４】
前記結論セット（４０、５０、６０）は、決定グラフの全体にわたって分散される、請求項１３に記載のデータベース。
【請求項１５】
請求項１ないし１２のいずれか１項に記載の方法をデータプロセッサに実施させるコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース内のデータを編成する方法およびこのような方法を実施するデータベースに関する。
【背景技術】
【０００２】
本出願人の同時係属中の英国特許出願ＧＢ００２９２３８．３に記載されたタイプのデータベースであろうと、他の既知のタイプのデータベースであろうと、通常、「Ｂ木」構造体のようなデータベースは、探索基準と一致するデータを記憶する結論セットを指し示す決定グラフまたは他のインデックスを有する。これに加えて、かつ／または、その代わりとして、結論セットは、探索キーと一致するデータの場所を指し示すポインタを記憶してもよい。
【０００３】
いかなる妥当なサイズのいかなるデータベースでも、結論セットは、大容量記憶媒体に記憶され、この大容量記憶媒体は、現在のところ、通常は、ハードディスクドライブを意味する。ハードディスクデバイスは、傾向としては、半導体メモリよりもかなり遅い。その結果、データベースの性能は、これらの大容量記憶デバイスによるこれらの入出力（Ｉ／Ｏ）操作を実行しなければならないことによって損なわれることがある。インデックスのオーバヘッドが最小の場合でさえ、データベースは、通常、読み出し、変更、および再書き込みサイクルの一部として２回のＩ／Ｏ操作を実行して、インデックスおよび結論セットにデータを挿入しなければならない。
【発明の開示】
【０００４】
本発明の第１の態様によれば、データベースのデータの記憶を編成する方法であって、上記データベースの結論セットは、階層的構造体に配置され、上記結論セットは、項目の数が第１レベルの位の選択された結論セットの閾値に達するまで、項目が当該選択された結論セットに挿入されるように配置され、その後、上記選択された結論セットの内容が、下位の結論セットに移動され、これにより、上記選択された結論セットが空にされる方法が提供される。
【０００５】
このように、決定グラフの出力に直ちに追従する結論セットの数を大幅に減少させる、変更された結論セットの構造体を提供することができる。
【０００６】
さらに、結論セットを決定グラフ内に分散させることも可能である。
【０００７】
従来技術のデータベースは、決定グラフからアクセス可能な単一の「レイヤ」の結論セットを有するであろう。結論セットに挿入されたすべての新しいデータの項目は、そのデータを含めるのに、少なくとも２回のＩ／Ｏ操作を必要とするであろう（これは、当該データが１つの結論セットのみに属し得る場合であり、挿入されるデータが２つ以上の結論セットに属し得る場合には、より多くのＩ／Ｏ操作が必要になる可能性がある）。
【０００８】
結論セットを階層的構造体に編成することにより、決定グラフから直接アクセス可能な結論セットの数を大幅に削減することができる。実際には、階層的に最も上位（すなわち最上位レベル）の結論セットを、半導体メモリのような高速メモリに保持することが可能になる。これは、結論セットが決定グラフの全体にわたって分散される本発明の実施の形態では特によく当てはまる。
【０００９】
最上位レベルの結論セットを半導体メモリに保持することにより、データをデータベースに挿入する時に、Ｉ／Ｏコストがかからない。したがって、キーおよびデータの挿入操作の間、データベースの性能に大幅な改善をもたらすことができる。
【００１０】
高いレベルの結論セットは、その結論セットがフルになるか、または、その結論セットのエントリ数が所定のレベルを超えるような時になるまで、データを有効にキャッシュすることが有利である。その後、その結論セットは、下位の結論セットにその内容を移動することによって空にされる。移動プロセスの間、データは、探索基準、すなわち探索キーを参照して記憶される。その結果、データは、すぐ下位の結論セット間にランダムに分散されることを予想することができる。この充填および移動のプロセスは、結論セットの構造体内の複数の階層レベルに対して繰り返すことができる。
【００１１】
データの移動は、大容量媒体記憶に保持された１つまたは２つ以上の結論セット間のデータの転送を必要とすることがあり、実際に多くの場合、必要とする。したがって、ディスク読み出し操作およびディスク書き込み操作が行われるが、これらは、結論セット内のそれぞれの個々の項目に対してではなく、結論セットの全体に対して行われる。その結果、１つのエントリあたりのＩ／Ｏコストは、大幅に削減される。
【００１２】
キー探索または削除の間、その決定基準が探索キーと一致する適切な最上位レベルの結論セットおよびそれぞれの下位の結論セットは、一致するデータがそこに記憶されているかどうかを調べるために、検査されることが有利である。このように、データベース照会のオーバヘッドは、従来技術のデータベースと比較すると増加するが、これは、挿入回数は多いが、照会回数が比較的少ないいくつかのデータベース構造体では受け入れることができる。
【００１３】
結論セットが決定グラフの全体にわたって分散される本発明の実施の形態では、結論セットがあまりにも頻繁に発生するのを防止するために、結論セット間の距離に制約を課すことができる。
【００１４】
結論セットの距離パラメータは、整数Ｑによって定義されるのが有利である。Ｑは、０以上の数値を取ることができる。したがって、例えば、データベースを次のように作成することができる。
【００１５】
Ｑ＝０：結論セットをすべての分岐ノードに形成することができる。
Ｑ＝１：結論セットを１つおきの分岐ノードに形成することができる。
Ｑ＝２：結論セットを２つおきの分岐ノードに形成することができる。
以下同様。
【００１６】
決定グラフの最後のＱ個のレイヤに達するまで、これらのルールは、決定グラフの全体にわたって保持することができる。この最後のＱ個のレイヤでは、この結論セット間の階層的な距離に関するルールは、強制できなくなり、したがって、厳格には適用されない。
【００１７】
本発明の第２の態様によれば、データベースであって、データベースの結論セットが、階層的構造体に配置され、上記結論セットは、項目の数が閾値に達するまで、項目が選択された結論セットに挿入されるように配置され、その後、上記選択された結論セットの内容が、下位の結論セットに移動され、これにより、上記選択された結論セットが空にされるデータベースが提供される。
【００１８】
本発明の第３の態様によれば、本発明の第１の態様にしたがってデータプロセッサを動作させるコンピュータプログラム製品が提供される。
【００１９】
本発明は、添付図面を参照しながら、例を用いてさらに説明される。
【発明を実施するための最良の形態】
【００２０】
図１に示すデータベースは、インデックス２を有し、インデックス２は、決定グラフ４および複数の結論セット６、８、１０、１２および１４を備える。それぞれの結論セットには、決定グラフを通る唯一のパスが到達する。一方で、それぞれの結論は、次に、データストア１６内の関連エントリを指し示す。
【００２１】
決定グラフ４は、複数の決定ノードを備える。決定ノードでは、決定グラフを通るどのパスを取るべきかを決定するために、探索キーが決定基準と照合される。決定グラフ内のキーの内部編成は、本発明の一部を構成しない。したがって、この内部編成について、本明細書で詳述する必要はない。しかしながら、Ｂ木インデックスのような従来技術のインデックス構造体を、決定グラフ内に利用してもよい。
【００２２】
図１に示す配置では、すべての結論セット６、８、１０、１２および１４が、等しい位を有する。したがって、どの結論セットも、他のいずれの結論セットより階層的に上位ではなく、実際には、何百あるいは何千もの結論セットが、存在することがある。
【００２３】
図２に示す配置では、結論セットは、階層的構造体で配置される。図示した配置では、３つのレベルの結論セットが存在する。レベル１は、階層的に最上位であり、レベル３は、階層的に最下位である。したがって、この配置では、レベル１の結論セットは、レベル３の結論セットの４分の１の個数しか存在しない。この例では、１つのレベル１の結論セットは、６つの他の結論セットへのエントリを指示する。明らかに、所定の最下位レベルの結論セットの個数に対して、レベル数が増加すると、それに伴い、レベル１の結論セットの個数は、次第に減少する。
【００２４】
次に、データベースにエントリを挿入する場合について考える。決定グラフが、従来技術のデータベースの場合と同様に、エントリの挿入キーにしたがってナビゲートされ、そのエントリがどの結論セットに属するかが見つけ出される。図１に示すデータベースでは、この結果は、一意に識別される１つの結論セットになる。一方、本発明では、この結果は、識別されるいくつかのレベル１の結論セット（分かり易くするために、２つの結論セット２０および２２のみが示されている）の中の１つの結論セット２０になる。結論セット２０にデータを挿入する時間のオーバヘッドが、従来のデータベースの結論セット６、８、１０、１２および１４の１つにデータを挿入するのに要する時間に比べて小さくなるように、レベル１の結論セット２０および２２も、高速メモリ、すなわち、高速の大容量媒体記憶デバイスまたはさらに良いものとして半導体メモリのいずれかに保持されることが有利である。実際には、レベル１の結論セット２０および２２は、半導体メモリに保持され、その結果、これらの結論セットへの書き込み時に、Ｉ／Ｏコストはかからない。
【００２５】
動作中、データが、データベースに多く挿入されるにしたがい、結論セット２０は、フルになり始める。結論セット２０のエントリの個数が、フルになっている結論セットに対応する所定の個数に達すると、結論セット２０のエントリは、階層的構造体のレベル２に属するすぐ下位の結論セット２４および２６に移動される。
【００２６】
下位レベルの結論セット２２および２４のいずれが、レベル１の結論セット２０からエントリを受信するかについての決定は、決定グラフ４内に存在するナビゲーションルールを継続することにより求められる。したがって、例えば、決定グラフ４が、昇順のビット番号の個々のビットの値に基づくルールを有する場合には、最上位レベルの結論セットから第２レベルの結論セット２４または２６へデータを移動するルールは、探索キーの次のビットを用いて、結論セット２４または２６のいずれがデータの各項目の受信者になるべきかを決定する。この移動プロセスの間に、結論セット２０は空になる。
【００２７】
第Ｎレベルから第Ｎ＋１レベルへの移動プロセスは、結論セット階層内のそれぞれのレベルにおいて、そのレベルの各結論セットが一杯になると、そのそれぞれのレベルで発生する。したがって、次に、結論セット２６がフルになると、結論セット２６は、階層の第３レベルに位置するその下位結論セット２８および３０へ、そのデータを移動させる。この例では、第３レベルは、階層の最下位レベルであり、結論セット２８および３０は、それらのデータを下位結論セットに渡すことができない。しかしながら、４つ以上の結論セットのレベルが、この階層的構造体に含まれるならば、結論セット２８および３０は、フルになった場合、確かに、それらのデータをそれら自体の下位結論セットに移動させることができる。キーのランダムな分散を仮定すると、移動中、結論セット２０のエントリの半分は、結論セット２４に行き、他の半分は、結論セット２６に行くことが予想され得る。エントリのすべてが、下位レベルの結論セットのすべてにわたってほぼ均等に分散されるように、このプロセスは、移動の各レベルで繰り返される。
【００２８】
移動のＩ／Ｏコストは、結論セット２６から結論セット２８および３０へのデータの移動操作で説明することができる。このプロセスでは、データは、結論セット２６から読み出されなければならず、これは、ディスクからの１回の読み出しを必要とする。下位レベルの結論セット２８および３０も、それらのデータをディスクから読み出さなければならず、これは、２回の読み出し操作を必要とする。次に、結論セット２６からのデータは、行き先のセット２８または３０を正確に指し示すように記憶され、続いて、それらエントリは、更新され、その後、２つの下位レベルの結論セット２８および３０のデータはディスクに再び書き込まれ、これは、２回の書き込み操作を必要とする。次に、結論セット２６は空にされ、これは、１回の書き込み操作を必要とする。したがって、これは、１回の移動あたりのトータルのコストとして、６回の入出力操作を与える。しかしながら、この単一の移動は、何百ものエントリを実行することができる。最上位レベルの結論セット２０は、通常、メモリに常駐し、その結果、セット２４および２６に対する２回の読み出しおよびこれらのセット２４および２６に対する書き込みのみを実行しなければならないので、最上位レベルの結論セット２０からの移動は、より少なくなることにも留意すべきである。
【００２９】
図２に示すような階層的構造体を仮定し、結論セットが、Ｓ個のサブレベル（ここで、このケースではＳ＝２であり、Ｌをレベル数とすると、Ｓ＝（Ｌ−１）である）を有するものとすると、最下位レベルへエントリを移動させるのに必要なＩ／Ｏ操作回数は、６Ｓ回である。しかしながら、それぞれの移動操作が、Ｅ個のエントリを含む（フルの）結論セット全体を移動させるので、１つのエントリあたりのＩ／Ｏコストは、以下の式で与えられる。
【００３０】
Ｉ／Ｏコスト＝６Ｓ／Ｅ
【００３１】
したがって、Ｅが十分大きく、かつ／または、Ｓが十分小さいならば、Ｉ／Ｏコストは、１つのエントリあたりのＩ／Ｏコストが２である図１に示す従来技術の方式と比較すると、大幅に削減することができる。これにより、１００個のエントリおよび結論セットの深さ８を保持する結論セットによると、１回の挿入あたりのＩ／Ｏコストは、６×８÷１００＝０．４８となる。
【００３２】
一定のインデックスサイズに対して、Ｓを減少させることは、挿入スループットを増加させることになる一方、実現のためにメモリに保持されなければならない結論セットの個数を増加させることにもなることに留意すべきである。
【００３３】
ある特定のキーのインデックスに照会を行うと、最下位の結論セットに達する単一のパス内の各結論セットが、照会の対象にならなければならない。したがって、階層的構造体が、Ｌ個のレベルからなる場合には、そのキーは、その階層内のあらゆるレベルに存在し得るので、Ｌ個の結論セットが、そのキーと一致するすべての結果を見つけ出すために、照会の対象にならなければならない。このように、このインデックス方式は、照会の性能が劣化することを犠牲にして、スループット、または、エントリをインデックスに追加し得る容易さを増大させる。しかしながら、このトレードオフは、大量のデータを受け入れなければならないが、データへの照会はまれにしか行われないあらゆる用途で受け入れることができる。このような用途の一例は、の不正検知システムである。このシステムは、あらゆるトランザクションをロードしなければならないが、疑わしいアクティビティに関するトランザクションへの照会のみを行う。
【００３４】
このように、結論セットの構造体を階層構造体に変更することにより、改善されたデータベースの性能を提供することができる。
【００３５】
本発明者は、結論セットのすべてが、データベース構造体の最下位レベルに位置する必要がないことを実現した。上述したように、図２に示す分散型構造体では、データは、見つけ出された第１の結論セット、すなわちレベル１の結論セットに挿入され、その後、下位レベルに次第に移動される。
【００３６】
このように、結論セットが、決定インデックス構造体の全体にわたって分散される場合には、挿入のオーバヘッドをさらに削減することができる。
【００３７】
図３は、結論セットが階層的構造体に配置される、変更されたデータベースを示している。このデータベースでは、この構造体が、決定グラフ内に延長されている。
【００３８】
図３は、決定グラフの一部を示している。この図では、結論セット４０、５０および６０が、３つ目の分岐ノードごとに割り当てられるように、この決定グラフは、結論セット間の距離Ｑ＝３で構築されている。データベースに含まれるデータが、結論セット４０をちょうど生成したが、結論セット５０および６０をまだ生成していないような時に、データベースに参加した場合について仮定してみる。
【００３９】
使用中、データが、データベースに追加され、そのデータの内容は、結論セット４０がフルになるようなものである。結論セット４０がフルになると、この結論セット内の情報は、一斉に再分散される。この再分散は、下位レベルのノード４２および任意選択的にノード４３を生成し、かつ、結論セット４０から、図３に輪郭で示された新しい一時的な結論セット４４および４５にデータを分散させることにより行われる。その後、結論セット４０が再び一杯になるまで、データベースの充填は続く。その後、結論セット４０は、その内容を、その下位の結論セットに再分散することを試みる。この再分散は、今度は、その下位の結論セットの１つをフルにすることがあるため、フルになった一時的な結論セットをノード４２の出口パスから除去し、１つまたは２つ以上のさらに別のノードおよび追加の結論セットを必要に応じて挿入することが必要になる。
【００４０】
これは、結論セット５０が、ノード４６の出口として確立されるような時まで続けることができる。これにより、この時、結論セット４０と結論セット５０との間の結論セット間距離は、データベースの設計者またはユーザによって指定された距離Ｑに対応する。これらの状況下で、中間の結論セットが、ノード４１とノード４６との間に伸びる決定パスに存在するかどうかを調べるために、チェックが行われる。この決定パスのあらゆる結論セットは、除去され、それらの内容は、結論セット５０に移動される。
【００４１】
結論セット５０が一杯になると、結論セット６０が生成されるような時まで、新しい一時的な結論セットが生成されることがある。以下、同様のことが繰り返される。このように、決定インデックスの最下位レイヤにはない結論セットと結論セットとの間の結論セット間距離を、指定された結論セット間の間隔に維持することが可能になる。図３に示す配置では、結論セット６２および７０は、データベースの最下位レイヤを表す。実際には、結論セット６０、６２および７０は、図２に示す配置のレベル１、２および３の結論セットを表すことができる。
【００４２】
既に述べたように、結論セットのエントリを下位レベルの結論セットへ大量に再分散した結果、ディスクの入出力のペナルティは、個々のデータの項目の書き込みと比較して削減される。さらに、見つけ出された最初の結論セットにエントリが挿入されるので、図３に示す構造体へのデータエントリコストは、さらに削減される。その後、フルとなった結論セットからの各エントリは、適切な下位レベルの結論セットに移動される。適切な下位レベルの結論セットは、移動されるエントリを介して、フルとなった結論セットから決定グラフに従うことにより見つけ出される。
【００４３】
データベースに照会を行うと、関連するキーについての決定パスが、最下位レベルの結論セットにまっすぐにナビゲートされなければならない。途中で見つけ出された各結論セットも、探索キー基準と一致するデータを含むことがあるので、これら各結論セットにも照会が行われなければならない。
【図面の簡単な説明】
【００４４】
【図１】従来の方法で配置された結論セットを有するデータベースを概略的に示す図である。
【図２】本発明により配置された結論セットを有するデータベースを概略的に示す図である。
【図３】決定グラフ内に分散された結論セットを有し、本発明の実施の形態を構成するデータベースを概略的に示す図である。
【図１】
2004528634.tif 000003
【図２】
2004528634.tif 000004
【図３】
2004528634.tif 000005
【国際公開パンフレット】
2004528634.tif 000006
2004528634.tif 000007
2004528634.tif 000008
2004528634.tif 000009
2004528634.tif 000010
2004528634.tif 000011
2004528634.tif 000012
2004528634.tif 000013
2004528634.tif 000014
2004528634.tif 000015
2004528634.tif 000016
2004528634.tif 000017
2004528634.tif 000018
2004528634.tif 000019
2004528634.tif 000020
【国際公開パンフレット（コレクトバージョン）】
2004528634.tif 000021
2004528634.tif 000022
【国際調査報告】
2004528634.tif 000023
2004528634.tif 000024
2004528634.tif 000025