(57)【要約】  データを管理する方法は、個別にアクセス可能なデータユニットであってそれぞれキー値により特定されるデータユニットを受け取るステップ；複数のデータブロックであって少なくともいくつかのデータブロックはそれぞれ、複数のデータユニットを結合することにより生成されるデータブロックを格納するステップ；および、データブロックのそれぞれに対するエントリを含むインデックスを提供するステップ；を含む。エントリの一つ以上は、与えられたキー値を含むキー値範囲に対応するデータユニットを含むブロックの位置決めを、与えられたキー値に基づいて可能にする。【選択図】  図２Ａ【特許請求の範囲】
【請求項１】
データを管理する方法であって、
それぞれが一つのキー値により特定される複数のデータユニットであって個別にアクセス可能な複数のデータユニット、を受け取るステップ、
複数のデータブロックであってその少なくとも幾つかのそれぞれは複数の前記データユニットを結合することにより生成されている複数のデータブロック、を格納するステップ、及び
前記複数のデータブロックのそれぞれに対する入り口を含むインデックスを提供するステップ、を含み、
前記入り口の一つまたはそれ以上は、与えられたキー値に基づいて、その与えられたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を見つけ出すことを可能にする、方法。
【請求項２】
請求項１に記載の方法において、
前記データブロックの少なくともいくつかが、前記キー値に応じて規定された順序に基づいて前記複数のデータユニットを結合することによって生成される、方法。
【請求項３】
請求項２に記載の方法において、
前記規定された順序はアルファベット順であることを特徴とする方法。
【請求項４】
請求項２に記載の方法において、
前記規定された順序は数値順であることを特徴とする方法。
【請求項５】
請求項２に記載の方法において、
それぞれのブロックは複数のデータユニットのそれぞれの組から生成され、前記組は前記規定された順序にしたがって重複することのないキー値範囲に対応している、方法。
【請求項６】
請求項１に記載の方法において、
前記インデックス内の一つ又はそれ以上の入り口は、対応する一つのブロックが生成された複数のデータユニットに対応するキー値範囲を特定する、方法。
【請求項７】
請求項６に記載の方法において、
前記キー値範囲は、前記キー値範囲の少なくとも一つの極値を含む情報によって特定される、方法。
【請求項８】
請求項７に記載の方法において、
前記キー値範囲は、前記インデックスにおける第１の入り口からの第１の極値および前記インデックスにおける第２の入り口からの第２の極値によって特定される、方法。
【請求項９】
請求項６に記載の方法において、
前記キー値範囲は、前記対応するブロックが生成された前記複数のデータユニットに関連付けられた前記複数のキー値の少なくとも一つの極値を含む情報によって特定される、方法。
【請求項１０】
請求項９に記載の方法において、
前記キー値範囲は、前記インデックスにおける第１の入り口からの第１の極値および前記インデックスにおける第２の入り口からの第２の極値によって特定される、方法。
【請求項１１】
請求項６に記載の方法において、
前記インデックスにおける少なくともいくつかの前記入り口のそれぞれは、前記対応するブロックの格納場所を特定する、方法。
【請求項１２】
請求項１に記載の方法において、
複数の前記データユニットを結合させることによって一つのブロックを生成させるステップは、複数のデータユニットの一組を圧縮するステップを含む、方法。
【請求項１３】
請求項１２に記載の方法において、
複数のデータユニットの一組を圧縮することによって生成された一つのブロックを解凍するステップは、前記ブロック全体を処理するステップを含む、方法。
【請求項１４】
請求項１に記載の方法において、
前記データユニットは、対応する領域に関連付けられた一つまたはそれ以上の値をそれぞれが有するレコードである、方法。
【請求項１５】
請求項１４に記載の方法において、
受け取った一つのデータユニットを特定する一つのキー値は、そのデータユニットが受け取られる前にそのデータユニットに関係付けられた一つまたはそれ以上の領域に対応している、方法。
【請求項１６】
請求項１４に記載の方法において、
受け取った一つのデータユニットを特定するキー値は、そのデータユニットが受け取られた後にそのデータユニットに割り当てられる、方法。
【請求項１７】
請求項１６に記載の方法において、
キー値は単調変化するように割り当てられる、方法。
【請求項１８】
請求項１７に記載の方法において、
キー値は連続的に変化するように割り当てられる、方法。
【請求項１９】
請求項１に記載の方法において、
前記格納された複数のデータブロックは、複数のブロックからなる第１の組として格納される、方法。
【請求項２０】
請求項１９に記載の方法において、
前記ブロックの第１の組はファイル内に格納される、方法。
【請求項２１】
請求項１９に記載の方法であって、
一つ又はそれ以上のデータブロックからなる第２の組を格納するステップであって、前記第２の組の少なくともいくつかのデータブロックのそれぞれは、前記第１のブロックの組を格納した後に受け取られる複数のデータユニットから生成されるステップ、をさらに含む、方法。
【請求項２２】
請求項２１に記載の方法であって、
前記第２の組のうちの少なくともいくつかのブロックは、複数のデータユニットの一組を圧縮することによって生成される、方法。
【請求項２３】
請求項２１に記載の方法であって、
前記第２の組のうちのブロックの各々に対する入り口を含むインデックスを提供するステップをさらに含み、一つまたはそれ以上の前記エントリは、提供された一つのキー値に基づいて、前記提供されたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を見つけ出すことを可能にする、方法。
【請求項２４】
請求項２１に記載の方法であって、
前記第１と第２のブロックの組を処理して、それらのブロックが生成された複数のデータユニットを復元するステップ、
前記第１の組から復元されたデータユニットと前記第２の組から復元されたデータユニットとを前記データユニットに対応するキー値に応じた順序にしたがってソートして一組のソートされたデータユニットを生成するステップ、および
複数のブロックからなる第３の組であってその第３の組の中の少なくともいくつかのブロックの各々が前記ソートされた複数のデータユニットを結合することによって生成される第３の組、を生成するステップ、をさらに含む、方法。
【請求項２５】
請求項２４に記載の方法において、
前記第１の組から復元されたデータユニットと前記第２の組から復元されたデータユニットとをソートすることは、これらのデータユニットに対応するキー値に応じた順序にしたがって前記第１の組から復元されたデータユニットと前記第２の組から復元されたデータユニットとを結合して一組のソートされたデータユニットを生成することを含む、方法。
【請求項２６】
請求項２４に記載の方法であって、
前記第３の組の中のブロックの各々に対する入り口を含む前記第３の組に対するインデックスを提供するするステップをさらに含み、一つ又はそれ以上の前記入り口が、提供されたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その提供されたキー値に基づいて、見つけ出すことを可能にする、方法。
【請求項２７】
請求項１に記載の方法であって、
前記複数のブロックが生成された前記複数のデータユニット中に、所与の一つの属性値を含む一つのデータユニットが含まれていたという可能性を決定するために、前記格納された複数のブロックに関連づけられた一つの選別データ構造を提供するステップをさらに含む、方法。
【請求項２８】
請求項２７に記載の方法において、
前記属性値は、一つのデータユニットを特定する一つのキー値を含むことを特徴とする方法。
【請求項２９】
請求項２７に記載の方法において、
前記選別データ構造は、所与の属性値に関し、前記所与の属性値を含んでいる一つのデータユニットが含まれていなかったことが確実であるのか、または、前記所与の属性値を含んでいる一つのデータユニットが含まれていた可能性があるのかを決定することを特徴とする方法。
【請求項３０】
請求項２９に記載の方法において、
前記所与の属性値を含んでいる一つのデータユニットが含まれていなかったときに同データユニットが含まれていた可能性があると前記選別データ構造が決定する確率は、前記データ構造の大きさに依存することを特徴とする方法。
【請求項３１】
請求項３０に記載の方法であって、
前記複数のブロックが生成された複数のデータユニットの個数に基づいて前記選別データ構造の大きさを選択するステップをさらに含む、方法。
【請求項３２】
請求項１に記載の方法であって、
一つの所与の属性値を含む複数のデータユニットの一つまたはそれ以上のキー値を決定するためのインデックスであって前記格納された複数のブロックに関連付けられた二次的なインデックス、を提供するステップをさらに含む方法。
【請求項３３】
請求項３２に記載の方法において、
前記複数のデータユニットは、対応する複数の領域に関係付けられた一つまたはそれ以上の値をそれぞれが有する複数のレコードであり、一つのレコードを特定する前記キー値は一つのプライマリーキー値に対応し、前記二次的なインデックスに関連付けられた前記属性値は一つのセカンダリキー値に対応する、方法。
【請求項３４】
請求項３２に記載の方法において、
前記二次的なインデックスは、前記キー値以外であって前記複数のデータユニット内の複数の属性値によってソートされた行を有する表を含む、方法。
【請求項３５】
データを管理するシステムであって、
個別にアクセス可能な複数のデータユニットであってそれぞれが一つのキー値により特定される複数のデータユニット、を受け取る手段、
複数のデータブロックであってその複数のブロックの少なくとも幾つかのそれぞれが複数の前記データユニットを結合することによって生成されている複数のデータブロック、を格納する手段、および、
前記複数のデータブロックのそれぞれに対する入り口を含むインデックスを提供する手段、を含み、
前記入り口の一つまたはそれ以上は、与えられたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その提供されたキー値に基づいて、見つけ出すことを可能にすることを特徴とするデータを管理するシステム。
【請求項３６】
データを管理するために、コンピュータ読取り可能記録媒体に格納されるコンピュータプログラムであって、前記コンピュータプログラムは、コンピュータが、
個別にアクセス可能な複数のデータユニットであってそれぞれが一つのキー値によって特定される複数のデータユニット、を受け取り、
複数のデータブロックであってその複数のブロックの少なくとも幾つかのそれぞれが複数の前記データユニットを結合することによって生成されている複数のデータブロック、を格納し、および、
前記データブロックのそれぞれに対する入り口を含む一つのインデックスを提供する、
ことを実行させる命令を含み、
前記エントリの一つまたはそれ以上は、与えられたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その与えられたキー値に基づいて見つけ出すことを可能にすることを特徴とする、
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、個別にアクセス可能なデータユニット（data unit）の格納管理に関する。
【背景技術】
【０００２】
データベースシステムは、個別にアクセス可能なデータのユニット（単位：unit）すなわち「レコード」を、種々のフォーマットのいずれかで格納することができる。各レコードは、クレジットカード取引などの論理要素に対応でき、一般には、そのレコードを一意に特定するために使用される関連プライマリーキーを有する。レコードは、レコードフォーマットのそれぞれの領域に関連付けた複数の値を含むことができる。レコードは、一つ又は二以上のファイル（例えば、フラットファイルまたはＸＭＬファイルなどの構造化データファイル）内に格納できる。圧縮データベースシステムにおいては、個々のレコードまたはレコード内の値は、格納時に圧縮され、アクセス時に解凍され、それによりシステムが必要とする記憶容量が削減される。
【発明の概要】
【０００３】
本発明の一態様において、概して、データを管理する方法は、個別にアクセス可能な複数のデータユニットであってそれぞれが一つのキー値によって特定される複数のデータユニットを受け取るステップ；複数のデータブロックであって少なくともその複数のブロックの幾つかは前記複数のデータユニットを結合することにより生成される複数のデータブロックを格納するステップ；および、前記複数のデータブロックのそれぞれに対する入り口を含む一つのインデックスを提供するステップ；を含む。前記入り口の一つまたはそれ以上は、一つの与えられたキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、与えられたキー値に基づいて、見つけ出すことを可能にする。
【０００４】
別の態様において、概して、データを管理するシステムは、個別にアクセス可能な複数のデータユニットであってそれぞれが一つのキー値により特定されるデータユニットを受け取る手段；複数のデータのブロックであってその複数のブロックの少なくとも幾つかのそれぞれが前記データユニットを複数個結合することにより生成されている複数のデータのブロックを格納する手段；および、前記複数のデータブロックのそれぞれに対する入り口を含むインデックスを提供する手段；を含む。その入り口の一つまたはそれ以上は、与えられた一つのキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その与えられたキー値に基づいて、見つけ出すことを可能にする。
【０００５】
別の態様において、概して、コンピュータ読取り可能記録媒体に格納される、データを管理するコンピュータプログラムは、コンピュータが：個別にアクセス可能な複数のデータユニットであってそれぞれが一つのキー値によって特定される複数のデータユニットを受け取り；複数のデータのブロックであって少なくともそのブロックの幾つかのそれぞれが前記データユニットを複数個結合することにより生成されている複数のデータのブロックを格納し；前記データブロックのそれぞれに対する一つの入り口を含む一つのインデックスを提供する；ことを実行させる命令を含む。その入り口の一つまたはそれ以上は、与えられた一つのキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その与えられたキー値に基づいて、見つけ出すことを可能にする。
【０００６】
各態様は、以下の特徴の一つ以上を含むことができる。
【０００７】
少なくとも前記ブロックの幾つかは、前記複数のキー値に応じて規定された順序に基づいて前記複数のデータユニットを結合することによって生成される。
【０００８】
前記規定された順序はアルファベット順である。
【０００９】
前記規定された順序は数値順である。
【００１０】
それぞれのブロックは、複数のデータユニットからなる複数の組からそれぞれ生成され、その複数の組は、その規定された順序にしたがってキー値の重複することのない複数の範囲に対応している。
【００１１】
前記インデックス内の複数の入り口の一つまたはそれ以上は、一つの対応するブロックが生成された複数のデータユニットに対応するキー値範囲を特定する。
【００１２】
前記キー値範囲は、キー値範囲の少なくとも一つの極値を含む情報によって特定される。
【００１３】
前記キー値範囲は、前記インデックス内の第１の入り口からの第１の極値および前記インデックス内の第２の入り口からの第２の極値によって特定される。
【００１４】
前記キー値範囲は、前記対応するブロックが生成された複数のデータユニットに関係付けられた前記複数のキー値の少なくとも一つの極値を含む情報によって特定される。
【００１５】
前記キー値範囲は、前記インデックス内の第１の入り口からの第１の極値および前記インデックス内の第２の入り口からの第２の極値によって特定される。
【００１６】
前記インデックス内の前記複数の入り口の少なくとも幾つかの各々は、対応するブロックの格納場所を特定する。
【００１７】
複数の前記データユニットを結合させることによって一つのブロックを生成させるステップは、複数のデータユニットの一組を圧縮するステップを含む。
【００１８】
複数のデータユニットの一組を圧縮することによって生成されたブロックを解凍するステップは、そのブロック全体を処理するステップを含む。
【００１９】
前記複数のデータユニットは、対応する複数の領域に関連付けられた一つまたはそれ以上の値をそれぞれ有する複数のレコードである。
【００２０】
受け取った一つのデータユニットを特定する一つのキー値は、受け取る前のそのデータユニットに関連付けられた一つまたはそれ以上の領域に対応している。
【００２１】
受け取った一つのデータユニットを特定する一つのキー値は、受け取った後にそのデータユニットに割り当てられる。
【００２２】
キー値は単調変化するように割り当てられる。
【００２３】
キー値は連続変化するように割り当てられる。
【００２４】
前記格納された複数のデータブロックは、複数のブロックからなる第１の組として格納される。
【００２５】
その複数のブロックからなる第１の組は、一つのファイル内に格納される。
【００２６】
一つまたはそれ以上のデータブロックからなる第２の組が格納されるが、その第２の組のうちの少なくとも幾つかのブロックの各々は、前記複数のブロックからなる第１の組を格納した後に受け取られた複数のデータユニットから生成される。
【００２７】
前記第２の組の中の少なくとも幾つかのブロックは、複数のデータユニットからなる一つの組を圧縮することによって生成される。
【００２８】
前記第２の組の中の複数のブロックの各々に対する一つの入り口を含む一つのインデックスが提供され、一つまたはそれ以上の前記エントリは、提供された一つのキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その提供されたキー値に基づいて、見つけ出すことを可能にする。
【００２９】
複数のブロックからなる前記第１及び第２の組は処理され、それらのブロックが生成された複数のデータユニットを復元し；前記第１の組から復元された複数のデータユニットおよび前記第２の組から復元された複数のデータユニットは、これらの複数のデータユニットに対応する複数のキー値に応じた順序にしたがってソートされ、ソートされた複数のデータユニットからなる一組が生成され；第３の組のブロックが生成され、その第３の組の中の少なくともいくつかのブロックはそれぞれ前記ソートされた複数のデータユニットを結合することによって生成される。
【００３０】
前記第１の組から復元された複数のデータユニットおよび前記第２の組から復元された複数のデータユニットをソートするステップは、これらのデータユニットに対応する複数のキー値に応じた順序にしたがって、前記第１の組から復元された複数のデータユニットを前記第２の組から復元された複数のデータユニットと統合し、ソートされた複数のデータユニットからなる一組を生成するステップを含む。
【００３１】
前記第３の組の中の複数のブロックの各々に対する入り口を含む前記第３の組に対するインデックスが提供され、一つまたはそれ以上の前記入り口は、提供された一つのキー値を含むキー値範囲に対応する複数のデータユニットを含む一つのブロックの位置を、その提供された一つのキー値に基づいて、見つけ出すことを可能にする。
【００３２】
前記格納される複数のブロックに関連付けられた選別データ構造は、所与の属性値を含む一つのデータユニットが、前記複数のブロックの生成された複数のデータユニットに含まれていた可能性を決定するために提供される。
【００３３】
前記属性値は、一つのデータユニットを特定する一つのキー値を含む。
【００３４】
選別データ構造は、所与の属性値に対し、その所与の属性値を含む一つのデータユニットが含まれていなかったことが確実であるか、またはその所与の属性値を含む一つのデータユニットが含まれていた可能性があったかを決定する。
【００３５】
前記一つのデータユニットが含まれていない場合、前記所与の属性値を含む一つのデータユニットが含まれていた可能性があると前記選別データ構造が決定する確率は、前記データ構造の大きさ（サイズ）に依存する。
【００３６】
前記選別データ構造の大きさは、前記複数のブロックが生成された複数のデータユニットの個数に基づいて選択される。
【００３７】
前記格納された複数のブロックに関連付けられた二次的なインデックスは、所与の属性値を含む複数のデータユニットの一つまたはそれ以上のキー値を決定するために提供される。
【００３８】
前記複数のデータユニットは、それぞれが対応する複数の領域に関連付けられた一つまたはそれ以上の値を有する複数のレコードであり、一つのレコードを特定する一つのキー値は一つのプライマリーキー値に対応し、前記二次的なインデックスに関連付けられた前記属性値は一つのセカンダリキー値に対応する。
【００３９】
前記二次的なインデックスは、前記キー値以外であって前記複数のデータユニット中の複数の属性値によってソートされた行を有する表を含む。
【００４０】
各態様は、以下の利点の一つ以上を含むことができる。
【００４１】
複数のレコードの一つのブロックを圧縮することによって、その複数のレコードを個別に圧縮するよりも大規模な圧縮を達成することができる。インデックスが付された複数のブロックは、圧縮された複数のレコードの一つのファイルの始まりから解凍することを必要としないで、所与の一つのレコードにアクセスする能力を提供する。複数のブロックのサイズは、大きな圧縮をもたらすために十分大きくなるように選択することができ、また一つのブロック内において所与の一つのレコードにアクセスするために必要な解凍の量を制限するために十分に小さくなるように選択することもできる。各ブロックは、圧縮ブロック内の任意の位置から解凍を開始する能力を提供する必要のない圧縮技術を用いて圧縮することができる。したがって、大規模な圧縮を提供する方法が使用され得る。
【００４２】
対応する一つのブロックが生成された複数のレコードに対応するキー値範囲を特定するインデックスを保存することにより、そのインデックスが各レコードに対する入り口を有する必要がなくなるため、そのインデックスを小さいままにしておくことができる（例えば、十分小さいので比較的高速のメモリ内に収めることができる）。インデックスの複数の入り口は、所望の一つのレコードを検索することができる一組の複数のレコードを復元するために、読み込みや解凍を実施することができる一つまたはそれ以上のブロックの位置を見つけ出すことを可能にする。圧縮ブロックにシグネチャを関連付けることにより、一つの所望のレコードが存在していないことを示すことができ、そのレコードを検索するために圧縮ブロックを読み込む必要がなくなる。
【００４３】
その他の特徴と利点は、以下の記載ならびに特許請求の範囲から明らかになる。
【図面の簡単な説明】
【００４４】
【図１】レコードを格納し、検索するシステムのブロック構成図である。
【図２Ａ】システムによって処理され、システム内に保存されるデータの概念図である。
【図２Ｂ】システムによって処理され、システム内に保存されるデータの概念図である。
【図２Ｃ】システムによって処理され、システム内に保存されるデータの概念図である。
【図２Ｄ】システムによって処理され、システム内に保存されるデータの概念図である。
【図３Ａ】異なるシグネチャサイズに対する誤った肯定の確率を示す表である。
【図３Ｂ】異なるシグネチャサイズに対する誤った肯定の確率を示す表である。
【図４Ａ】レコードの検索手順のフローチャートである。
【図４Ｂ】レコードの検索手順のフローチャートである。
【発明を実施するための形態】
【００４５】
図１を参照すると、レコード格納兼引き出し（検索）システム１００は、ソースＡからソースＣのような、一つまたはそれ以上のソースからデータを受け取る。そのデータは、個別にアクセス可能な複数のデータユニット（データ単位）として表され得る情報を含む。例えば、クレジットカード会社は、さまざまな小売業者から個々の取引を表現するデータを受け取ることができる。各取引は、顧客名、日付、購入額などの属性を表現する値と関連付けられる。レコード処理モジュール１０２は、一つの取引に関連付けられる複数の値が一つのレコード内に格納されるように、前記データが所定のレコードフォーマットに従ってフォーマットされていることを確実にする。場合により、このことは、ソースからのデータをレコードフォーマットに従って変換することを含む。その他の場合においては、一つまたはそれ以上のソースが、前記レコードフォーマットに従って既にフォーマットされているデータを提供してもよい。
【００４６】
レコード処理モジュール１０２は、各レコードを特定する一つのプライマリーキー値（例えば、単一のレコードを特定する一意の一つのキー又は一つのレコードの更新（アップデート）された複数のバージョンを特定する一つのキー）によって複数のレコードをソートし、その複数のレコードをプライマリーキー値の重複しない範囲に対応する複数のレコードからなる複数の組に分割する。例えば、複数のレコードの組のそれぞれは、予め定められた個数のレコード（例えば、１００個のレコード）に対応することができる。圧縮モジュール１０４は、複数のレコードからなる組のそれぞれを圧縮されたデータのブロックへと圧縮する。これらの圧縮ブロックは、レコード記憶装置１０６（例えば、一つまたはそれ以上のハードディスクドライブなどの不揮発性記憶媒体）内の一つの圧縮レコードファイル内に格納される。システム１００は、複数のブロックの各々に対する一つの入り口（エントリ）を含むインデックスを提供するインデックス化兼検索モジュール１０８も含む。そのインデックスは、以下にさらに詳述するように、所与の一つのレコードを含む一つのブロックを探し出すために使用される。そのインデックスは、インデックス記憶装置１１０内の一つのインデックスファイル内に格納され得る。例えば、インデックスファイルは圧縮レコードファイルと同じ記憶媒体に格納され得るが、インデックスファイルは、一般には圧縮レコードファイルよりもはるかに小さいから、比較的高速のメモリ（例えば、ダイナミックランダムアクセスメモリなどの揮発性記憶媒体）に格納されることが好ましい。
【００４７】
システム１００のその他の実施例においては、圧縮に加えてまたは圧縮の代わりに、何らかの仕方によって複数のレコードを結びつける（すなわち、ブロックが単に連結された複数のレコードからなる一つの組ではないようにする）他の機能を使用して複数のレコードからなる複数の組を処理し、複数のブロックを生成することができる。例えば、いくつかのシステムは、複数のレコードからなる組を処理して暗号化されたデータからなる複数のブロックを生成することができる。
【００４８】
インタフェースモジュール１１２は、エージェントＡからエージェントＤのような人間および／またはコンピュータエージェントに対して、格納された複数のレコードに対するアクセスを提供する。例えば、インタフェースモジュール１１２は、クレジットカードの顧客が自分自身の取引を確認するためのオンライン課金システムを実現することができる。さまざまな基準を満たす取引情報に対する要求を、システム１００によって処理することができ、対応するレコードは、レコード記憶装置１０６に格納されている複数の圧縮ブロック内から引き出すことができる。
【００４９】
一つまたはそれ以上のソースから入ってくるレコードの流れは、一つの圧縮レコードファイルを生成するように処理される前に、一時的に格納されてもよい。図２Ａを参照すると、システム１００は、一つの圧縮レコードファイルに格納されるべき複数のレコードからなる一つの組２００を受け取り、プライマリーキーの値にしたがってその複数のレコードをソートする。
【００５０】
一つのプライマリーキー値は、データベース内の、一つまたはそれ以上のレコードによって表現され得る所与のアイテムを一意に特定することができる（例えば、一つの所与のプライマリーキー値を有する各レコードは、そのアイテムの異なる更新された（アップデートされた）バージョンに対応し得る）。プライマリーキーは、一つのレコードの一つまたはそれ以上の既存の領域（フィールド）に対応する「自然なキー」であってもよい。各アイテムに対して一意的であることが保証される領域が存在しない場合、プライマリーキーは、各アイテムに対して一意的であることをまとまって保証するか又は一意的である可能性が極めて高いような「一つのレコードの複数の領域」を含む複合キーであってもよい。あるいは、プライマリーキーは、各レコードが受け取られた後に各レコードに対して割り当てられる「合成キー」であってもよい。例えば、システム１００は、一意のプライマリーキー値を連続的に増加する整数として、または単調に増加する値の他の数列（例えば、タイムスタンプ；時刻印）として割り当ててもよい。この場合、同じアイテムの異なるバージョンを表す複数のレコードに異なる合成キー値を割り当ててもよい。整数が使用される場合、プライマリーキー値の取り得る範囲（例えば、使用されるビット数によって決定される）は、十分大きくすることができ、プライマリーキーが一巡する場合、所与のプライマリーキー値をすでに割り当てられているレコードは、圧縮レコードファイルから取り除かれている。例えば、古い取引は、除去され且つアーカイブ化されるか、または破棄されてもよい。
【００５１】
図２Ａに示す例では、レコード２００は、Ａ，ＡＢ，ＣＺ，・・・のようにアルファベット順にソートされたプライマリーキー値によって特定される。システム１００は、ＡからＤＤまでのプライマリーキー値を有するＮ個のレコードからなる第１の組を圧縮してブロック１と名付けられた一つの対応する圧縮ブロックを生成する。次のレコードの組は、ＤＸからＧＦまでのプライマリーキー値を有する次のＮ個のソートされたレコードを含む。圧縮モジュール１０４は、さまざまな無損失データ圧縮アルゴリズム（例えば、レンペル・ジブアルゴリズム）のいずれをも使用することができる。連続した圧縮ブロックの各々は結合され、一つの圧縮レコードファイル２０２を形成する。
【００５２】
一つの圧縮ブロックを生成するために使用されるレコードの数Ｎは、圧縮効率と解凍速度との間の妥協点で選択することができる。圧縮により、圧縮されるデータの性質および圧縮されるデータの大きさに依存する所与の因子Ｒに応じて平均的にデータの大きさを小さくできる（例えば、より多くのデータが圧縮される場合、Ｒは通常小さい）。圧縮は、平均的な大きさが「Ｏ」である「関連付けられたオーバーヘッド（例えば、圧縮関連データ）」も有することができる。それぞれ大きさがＸであるＭ個のレコードから生成された圧縮レコードファイルの平均的大きさは、［Ｍ／Ｎ］（ＲＮＸ＋Ｏ）と表すことができ、これは、多数のブロックに対しては、ＲＭＸ＋ＯＭ／Ｎと近似できる。したがって、場合によっては、Ｎの値が大きくなるほど、Ｒを減少させるとともにファイルの大きさに対する上記オーバーヘッドの影響を減少させることにより、より大きく圧縮することができる。Ｎの値がより小さいほど、ある圧縮ブロックに含まれているかもしれない一つのレコードにアクセスするためにその圧縮ブロックを解凍するのに必要な時間がより短くなる。
【００５３】
その他の実施例において、異なる圧縮ブロックは、異なる数のレコードを含むことができる。各ブロックは、所定の範囲にしたがい、複数のレコードを有することができる。例えば、第１のブロックは、プライマリーキー値が１から１０００までのレコードを含み、第２のブロックは、プライマリーキー値が１００１から２０００までのレコードを含む等である。この例において、圧縮ブロック内のレコード数は異なっていることもある。これは、すべてのプライマリーキー値が必ずしも存在しないかである（例えば、既存の数値領域が自然なキーとして使用されている場合）。
【００５４】
いくつかの実施例において、場合により、異なる圧縮ブロックは、目標数のレコードを含み、例外的な場合には、より多いまたはより少ないレコードを含むことがある。例えば、複数のレコードからなるレコードの一つの組（一組のレコード）が、ソートされた順序において後続のレコードのプライマリーキー値とは異なるプライマリーキー値をもつレコードで終わっていれば、これらのレコードは、一つの圧縮ブロックを生成するために使用される。もし、一組のレコードが、ソートされた順序において後続のレコードのプライマリーキー値と同じプライマリーキー値をもつレコードで終わっていれば、そのプライマリーキー値を有するすべての追加的なレコードが、その組に追加される。このように、同じプライマリーキー値が一つの圧縮ブロックから次の圧縮ブロックへと領域を超えて存在することはない。
【００５５】
インデックス化兼検索モジュール１０８は、複数の圧縮ブロックの各々に対し、一つのインデックスファイル２０４の中に一つの入り口（エントリ）を生成する。そのインデックスの入り口は、例えば、対応する圧縮されていない一組のレコードにおける最初のレコードのプライマリーキーによって圧縮ブロックのそれぞれを特定するキーフィールド２０６を含む。その入り口は、圧縮レコードファイル２０２内において「特定された圧縮ブロック」の格納場所を特定する格納位置フィールド（a location field）２０８をも含む。例えば、その格納位置フィールドは、レコード記憶装置１０６の絶対アドレスの形式をとるポインタ、またはレコード記憶装置１０６内の圧縮レコードファイル２０２の始まりのアドレスからの差分の形式をとるポインタを含むことができる。
【００５６】
圧縮レコードファイル２０２内の所与の一つのレコードを検索するために、モジュール１０８は、キーフィールド２０６に基づいてインデックスファイル２０４の検索（例えば、二分探索）を実行することができる。与えられたキー値（例えば、エージェントのひとつから与えられるキー値）に対して、モジュール１０８は、その与えられたキー値を含むキー値範囲に対応する複数のレコードを含む一つのブロックを見つける。その与えられたキー値をもつレコードは、その見つけられたブロックを生成するために使用された複数のレコードの組に含まれていたかも知れないし、含まれていなかったかも知れないが、そのレコードが複数のレコード２００内に存在する場合には、レコード２００はプライマリーキー値によってソートされたはずであるので、そのレコードは含まれていたに違いない。次いでモジュール１０８は、その見つけられたブロックを解凍し、その与えられたキー値をもつ一つのレコードを検索する。プライマリーキー値が各レコードに対して一意的でない場合には、モジュール１０８は、その圧縮ブロック内において「その与えられたキー値をもつレコード」を複数見つける可能性がある。キーフィールド２０６が一組の中の最初のレコードのプライマリーキーを含む例においては、モジュール１０８は、与えられたキー値に先行する値又は後続するキー値を有する二個の連続したインデックスの入り口を検索し、先行するキー値をもつ入り口に対応するブロックを戻す。いくつかの場合において、与えられたキー値は、インデックスの入り口のキー値と同じであり、その場合、モジュール１０８はその入り口に対応するブロックを戻す。
【００５７】
様々な実施例において、インデックスファイル２０４における入り口が、対応する一つのブロックが生成された複数のレコードに対応するキー値範囲を特定するための様々な方法がある。図２Ａに示す実施例のように、キー値範囲は、一つのブロックを生成するために使用された複数のレコードの２つの極値キー値間の範囲となることがある（例えば、アルファベット順のプライマリーキー値のソートされた順序における先頭および末尾、または数値からなるプライマリーキー値のソートされた順序における最小値および最大値）。そのインデックスの入り口は、その範囲を規定する極値のどちらか一方、または両方を含むことができる。いくつかの実施例において、インデックスの入り口が一つの所与のブロックに対する範囲を規定する最小のキー値を含む場合、一つの圧縮レコードファイル内の最終のブロックに関連付けられる最後のインデックスの入り口はそのブロックに対する範囲を規定する最大のキー値を含むことができる。その後、この最大のキー値は、圧縮レコードファイルを検索する際に、所与のキー値が、いつ範囲外となるのかを決定するために使うことができる。
【００５８】
代替として、キー値範囲は、一つのブロックを生成するために使用される複数のレコードの複数のキー値を超えて拡張された範囲となることがある。例えば、１と１０００の間にある数値からなるプライマリーキー値をもつ複数のレコードから生成される一つのブロックの場合、その複数のレコードにおいて表される最小のキー値は１よりも大きいことがあり、その複数のレコードにおいて表される最大のキー値は１０００よりも小さいことがある。そのインデックスの入り口は、その範囲を規定する極値である１と１０００との何れか一方、または両方を含むこともできる。
【００５９】
最初の一群のレコードが処理されて一つの圧縮レコードファイルが生成された後に、追加の複数のレコードが到着すると、これらのレコードは、バッファに格納され、圧縮されていない状態にて検索され得る。代替として、複数のレコードからなる複数の追加的なグループは付加的に処理され、追加の複数のインデックスファイルによってアクセス可能な追加の複数の圧縮レコードファイルとして格納され得る。いくつかの場合において、少数の追加レコードを圧縮することが格納サイズを大きく減少させることができない場合であっても、その追加のレコードを圧縮することによりレコードにアクセスするための統一的な手続きを維持することは依然として有利である。追加レコードは、一定の時間間隔（例えば、３０秒毎または５分毎）にて、または所定数の追加レコードを受け取った後（例えば、１,０００個のレコード毎または１０,０００個のレコード毎）に、繰り返し処理され得る。入力されるレコードが時間間隔に基づいて処理される場合、間隔によっては、入力されるレコードがまったく存在しないことや、そのすべてが単一の圧縮ブロックへと圧縮される少数のレコードのみが存在することもある。
【００６０】
図２Ｂに示したように、最初の圧縮レコードファイル２０２が生成された後に追加のレコードがシステム１００によって受け取られる例においては、追加の圧縮レコードファイル２１０がその最初の圧縮レコードファイル２０２に付加されて合成圧縮レコードファイル２１１が形成され得る。システム１００はプライマリーキー値によってその追加のレコードをソートし、Ｎ個のレコードからなる複数の組を圧縮して圧縮レコードファイル２１０の複数の圧縮ブロックを生成する。ブロック９１と名付けた付加ファイル２１０内の最初の圧縮ブロックは、ＢＡからＦＦまでのプライマリーキー値を有する。モジュール１０８は、その付加ファイル２１０内に表されている追加の複数のレコードを検索するために使用される複数の入り口を含む追加の一つのインデックスファイル２１２を生成する。新たなインデックスファイル２１２は、直前のインデックスファイル２０４に付加することができる。
【００６１】
任意の数の圧縮レコードファイルを付加して、一つの合成圧縮レコードファイルを形成することができる。インデックス化兼検索モジュール１０８が、一つの合成圧縮レコードファイル内において所与のキー値をもつ一つのレコードを検索している場合、モジュール１０８は、対応するインデックスファイルを用いて、その付加された圧縮レコードファイル各々の中のレコードを検索する。代替として、所与のレコードを要求するエージェントは、検索される合成圧縮レコード内の圧縮レコードのいくつか（例えば、直近に生成された１０個、または直前の1時間以内に生成された任意のレコード）を特定することができる。
【００６２】
所与の時間の後（例えば２４時間毎）、または所与の個数の圧縮レコードファイルが付加された後、システム１００は、複数のファイルを統合し、一つの合成圧縮レコードファイルから単一の圧縮レコードファイルと対応する新たな一つのインデックスファイルを生成することができる。統合後、単一のインデックスは、所与のレコードを含んでいるかもしれない圧縮ブロックの場所を見つけるために検索されることができ、その結果、いっそう効率的なレコードへのアクセスがもたらされる。統合の際、システム１００は、圧縮レコードファイルを解凍して対応する「ソートされた複数のレコードからなる複数の組」を復元し、プライマリーキー値によってそのレコードをソートし、新しい圧縮レコードファイルとインデックスを生成する。復元されたレコードの複数の組のそれぞれは、既にソートされているので、プライマリーキー値にしたがってすでにソートされたリストを組み合わせることによって、そのレコードを効率的にソートすることができ、ソートされた複数のレコードからなる単一の組を生成することができる。
【００６３】
図２Ｃを参照すると、合成圧縮レコードファイル２１１は、何個の追加のレコードが届いたのか、およびどのくらいの頻度でそのレコードが処理されたのかに応じて、最初の圧縮レコードファイル２０２、追加の圧縮レコードファイル２１０、並びに、多数の追加の圧縮レコードファイル２２０,２２１,・・・を含む。各圧縮レコードファイルは、そのファイルの圧縮ブロック内の所与のレコードを検索するために使用できる「関連付けられたインデックスファイル」を有することができる。この例においては、圧縮レコードファイルの一つであるファイル２２０は、単一の圧縮ブロック（ブロック９５）だけを有する程に小さく、したがって、必ずしも関係付けたインデックスファイルを必要としないが、そのブロック内のプライマリーキー値範囲および記憶装置内での格納場所を示す関連付けられたデータを有することができる。統合の後、異なる付加圧縮レコードファイルから復元されたレコードが処理され、単一の圧縮レコードファイル２３０が生成される。
【００６４】
単調に変化するよう割り当てられたプライマリーキーの場合、複数のレコードは、圧縮レコードファイル内だけではなく、あるファイルから次のファイルへと自動的にソートされるため、一回のインデックス検索において一つのレコードにアクセスするために複数のファイルを統合することは不要となる。図２Ｄを参照すると、システム１００は、レコードのプライマリーキーとして到着順に割り当てられる連続した整数によって特定される複数のレコードの組２５０を受け取る。即ち、レコード２５０はプライマリーキー値によって自動的にソートされる。最初の圧縮レコードファイル２５２は、この例では、それぞれ１００個のレコードを含む複数の圧縮ブロックを含んでおり、インデックスファイル２５４は、一つの圧縮ブロック内の第１のレコードのプライマリーキー値用のキーフィールド２５６と、対応する格納場所を特定する格納位置フィールド２５８とを含む。最初の圧縮レコードファイル２５２が生成された後に到着するレコードは、後にソートされる順序のプライマリーキー値を自動的に有することになるので、付加された圧縮レコードファイル２６０および対応するインデックスファイル２６２は、一回のインデックス検索に基づいて効率的にレコードへアクセスすることを可能ならしめるようにするために、統合される必要がない。例えば、インデックスファイル２６２は、インデックスファイル２５４に単に付加されることができ、いずれのインデックスも、圧縮レコードファイル２５２および２６０のいずれかにおいて一つの圧縮ブロックの場所を見つけるために共に検索することができる（例えば、１回の二分探索によって）。
【００６５】
合成圧縮レコードファイル２６１は、随意に、統合されてもよく、それにより、圧縮レコードファイル２５２の末尾に挿入された可能性のある不完全なブロックを排除することができる。このような統合においては、最初のファイル２５２内の最後の圧縮ブロックだけは解凍する必要がある場合があり、解凍されたレコードの複数の組を合体する代わりに、その解凍されたレコードの組を単純に鎖状につなぎあわせ、新たなソートされた複数のレコードからなる一つの組を形成することができる。その新たなソートされたレコードの組は１００個のレコードからなる複数の組に分割されるものであり、分割された複数の組はその後再び圧縮されて新たな一つの圧縮レコードファイルを形成する。
【００６６】
連続した整数の合成プライマリーキー値を使用することの他の利点は、複数のレコードがプライマリーキー値に基づいて仕切られることになる場合、そのキー値間には欠番（とぎれ）がないので、その仕切りを自動的にバランスさせることができることである。
【００６７】
さまざまな技術のいずれかを使用して、レコードを更新（アップデート）し、一つの圧縮レコードファイルの中に存在し得る「レコードの以前のバージョン」のいずれをも無効にすることができる。場合によっては、レコードは、個別に取り除く必要がなく、或いは、個別に更新したりする必要がない（例えば、ログ、取引、電話）。これらの場合、古い複数のレコードは、例えば一つの圧縮レコードファイルの先頭から所定個数の圧縮ブロックのグループ単位で、取り除かれ且つ廃棄されるか、またはアーカイブ化される。場合によっては、圧縮レコードファイル全体を取り除くことができる。
【００６８】
場合によっては、一つのレコードの一つまたはそれ以上の値は、一つの圧縮ブロック内に格納するように新たな更新された（アップデートされた）レコードを追加することにより更新され、そのレコード（同じプライマリーキー値をもつ）の以前に受け取られたバージョンは、異なる圧縮ブロックに格納されたままであってもよい。従って、一つのレコードの多数のバージョンが存在する可能性があり、なんらかの技法が用いられることによって、どれがそのレコードの有効なバージョンであるのかが決定される。例えば、いずれかの圧縮レコードファイル内に現れる最終バージョン（最も最近に受け取られたバージョン）が暗黙的にまたは明示的に有効なバージョンとして示されることができ、他のいかなるバージョンも無効となる。この場合、所与のプライマリーキーをもつレコードに対する検索は、出現順であるそのプライマリーキーによって特定される最終レコードを見つけることを含むことができる。あるいは、一つのレコードは、そのレコードの以前のどのバージョンも有効ではないことを示す「レコードを無効にせよ」との書き込みによりレコードの新たなバージョンを加えることなく無効にすることができる。
【００６９】
システム１００は、種々のプロセスによってレコード記憶装置１０６に格納された複数の圧縮レコードファイルへのアクセスを調停（mediate）する。種々の同期技術のいずれかを用いて、一つまたはそれ以上の圧縮レコードファイル内の複数の圧縮ブロックに対するアクセスを調停することができる。システム１００は、ファイルを変更するいかなる処理（例えば、データを付加するか、または統合することによる処理）も互いに干渉しないようにすることを確実にする。例えば、統合実行中に新たなレコードが到着する場合、システム１００は、その統合処理が終了するまで待機するか、または圧縮ブロックを生成して、それらを既存の圧縮ファイルに付加する前に、それらを暫定的に格納することができる。圧縮レコードファイルからの読取り処理は、完全なファイルの一部をロードすることができ、変更途中にある可能性のある不完全な部分を無視することができる。
【００７０】
システム１００は、プライマリーキー以外のレコードの属性に基づく「レコードに対する検索」を可能にする追加データを格納する。一つの圧縮レコードファイルに対する二次的なインデックス（セカンダリーインデックス）は、一つのセカンダリキーとして指定される一つの属性値に基づいて、一つ又はそれ以上のプライマリーキー値を提供する情報を含む。一つのセカンダリキーとして指定される各属性は、対応する一つの二次的なインデックスに関連付けられ得る。例えば、各二次的なインデックスは、その関連付けられた二次的なキーによってソートされる行を有するテーブル（表）として構成できる。各行は、一つのセカンダリキーの値、およびそのセカンダリキー値を含む複数のレコードの一つまたはそれ以上のプライマリーキー値を含む。こうして、エージェントが所与のセカンダリキー値を含むいずれかのレコードの検索を開始する場合、システム１００は、その一つ（又は複数）のレコードを含む一つ（又は複数）の圧縮ブロックに対する圧縮レコードファイルのインデックスの検索に使用するための一つ（又は複数）のプライマリーキーを検索（参照）する。二次的なインデックス（セカンダリインデックス）は大きくてもよく（例えば、レコードの個数と同程度）、場合によっては、圧縮レコードファイルを格納する記憶媒体に格納してもよい。
【００７１】
場合によっては、セカンダリキーとして指定される属性値は、各レコードに対して一意的であってもよい。その場合、セカンダリキーとプライマリーキー間には一対一の対応関係があり、インタフェースモジュール１１２は、あたかもエージェントに対するプライマリーキーであるかのようにそのセカンダリキーの属性を提示することができる。
【００７２】
新たな複数の圧縮レコードファイルが一つの合成圧縮レコードファイルに付加されるとき、二次的なインデックスのそれぞれが更新され得る。あるいは、一つのセカンダリキーが、各圧縮レコードファイルに対する個別の二次的なインデックスに関連付けられることができ、複数の圧縮レコードファイルを統合するときには、複数のその二次的なインデックスを単一のセカンダリインデックスへと統合することができる。
【００７３】
選別データ構造を、所与の属性値を含む一つのレコードが一つの圧縮ブロックに含まれる可能性を決定するため、一つの圧縮レコードファイルに関連付けることができる。例えば、選別データ構造としてオーバーラップエンコーデッドシグネチャ（ＯＥＳ）を使用すると、システム１００は、所与のキー値（プライマリーキーまたはセカンダリキー）をもつ一つのレコードが確実に存在していない（「否定的」結果）か、またはその所与のキー値をもつ一つのレコードが存在している可能性がある（「肯定的」結果）か否かを決定できるようになる。肯定的結果に対して、システムは、適切な圧縮ブロックにアクセスし、レコードを取り出すか（「確定された肯定的」結果）、または、レコードが存在していないと決定する（「誤った肯定的」結果）。否定的結果に対して、システムは、存在していないレコードを求めて圧縮ブロックを解凍して検索する時間を費やすことを要するまでもなく、エージェントに対して否定的結果を与えることができる。ＯＥＳのサイズ（大きさ）は、どのくらいの頻度で肯定的結果が誤った肯定となるのかに影響を及ぼすが、一般にＯＥＳのサイズがより大きいほどより少ない誤った肯定的結果をもたらす。所与のＯＥＳサイズに関しては、一般に、別個で可能性のあるキー値が少ないほど、より少ない誤った肯定をもたらすことになる。
【００７４】
その他の種類の選別データ構造も可能である。所与のプライマリまたはセカンダリのキーに対する選別データ構造がそれぞれの圧縮レコードファイルに対して与えられ得る。あるいは、一つのキーに対する一つの選別データ構造が各圧縮ブロックに対して与えられ得る。
【００７５】
図３Ａと３Ｂは、代表的なＯＥＳ選別データ構造のさまざまなサイズ（列）と、圧縮レコードファイル内において表現されるさまざまな数の異なったキー値（行）と、に対する、一つのキー値に対して誤った肯定的結果が得られる確率値を提供する表を示す。ある一つのＯＥＳについては、そのＯＥＳのサイズおよび異なったキー値の数に依存して、一つを超えるキー値が存在することが、そのＯＥＳの同じ部分において示されていて、これらのキー値のうちの一つに対し、残りのキー値が存在している場合には、一つの誤った肯定的結果がもたらされ得る。この代表的なＯＥＳのサイズは、２１０＝１０２４ビット（図３Ａの表）から２２８＝２５６メガビット（図３Ｂの表）まで変化する。異なったキー値の数は１００（図３Ａの表）から１００，０００，０００（図３Ｂの表）まで変化する。どちらの表においても、右上の空白のセルは０％に相当し、左下の空白のセルは１００％に相当する。誤った肯定の確率が低い（例えば、ゼロに近い）セルに対しては、選別データ構造は、適切な選別を達成するために必要とされるよりも大きい可能性がある。誤った肯定の確率が大きい（例えば、５０％超）セルに対しては、選別データ構造は、適切な選別を達成するためには小さすぎる可能性がある。この例は、一つのキー値あたり４個のハッシュコードを使用するＯＥＳを生成する技術に相当する。ＯＥＳ選別データ構造の他の例は、所与の数の異なるキーに対する誤った肯定の確率を有する別の表をもたらすであろう。
【００７６】
一つの圧縮レコードファイル内で表される異なったキー値の数は分からない場合があるので、システム１００は、そのファイルが生成されたレコードの個数に基づいて、その圧縮レコードファイルに対する選別データ構造のサイズを選択することができる。そのサイズを選択する際、誤った肯定の確率を減少させることと、その選別データ構造を格納するために必要な記憶領域との間には、二律背反的な関係がある。この二律背反的な関係の一つのファクターは、欠番となっているキー値を検索する可能性である。検索されるキー値の大部分が解凍されたレコード内に存在している可能性が高い場合、選別データ構造は全く必要ではない可能性がある。キー値が見つけられないことが十分に起こり得る場合には、比較的大きな選別データ構造に対する記憶領域を割り当てることにより、かなりの時間を節約することができる。
【００７７】
一つの圧縮レコードファイルに関係付けられた選別データ構造のサイズは、そのファイルがレコードの初期データベースまたは統合された大容量データベースに対応するのか、あるいは大容量データベースに対するより小容量の更新（アップデート）に対応するのか、という点に依存し得る。各更新（アップデート）内には一般により少ない数の異なったキー値が存在するので、定期更新時に付加される圧縮レコードファイルに対しては比較的小さなサイズの選別データ構造が使用され得る。また、多数の更新の後には圧縮レコードファイルの個数が多くなるので、小さなサイズにすることにより、必要とされる格納領域を減少することができる。選別データ構造のサイズは、予想されるレコードおよび／または更新における異なったキー値の個数、ならびに、予想される更新の回数に基づくことができる。例えば、更新されるファイルが、２４時間の期間において５分毎に付加される場合、一日の終わりには２８８個の圧縮レコードファイルができることになる。少なくとも一つの誤った肯定の結果の確率は、図３Ａおよび図３Ｂの表から得られる適切な値の２８８倍となる（異なる更新に対する結果は独立しているものと仮定する）。統合の後には、異なるキー値の個数は顕著に増加する場合があるため、その統合された圧縮レコードファイルに対してはより大きな選別データ構造が適切であろう。
【００７８】
一つの圧縮レコードファイルは、プライマリーキーおよび各セカンダリキーに対して、あるいはこれらキーの一部に対して、一つの選別データ構造を持つことができる。例えば、システム１００は、プライマリーキー、及び、レコードを検索する際に最も高い頻度で使用されると予想されるセカンダリキーだけに対し、一つの選別データ構造を提供してもよい。
【００７９】
図４Ａは、所与のプライマリーキー値をもつ一つまたはそれ以上のレコードを検索するための手順４００のフローチャートを示す。手順４００は、４０２において最初の圧縮レコードファイルに関連付けられた選別データ構造があるか否かを判定する。データ構造がある場合、手順４００は、４０４において選別データ構造の処理により、肯定的または否定的結果のいずれかを得る。その所与のプライマリーキー値が選別を通過しない（否定的結果である）場合、手順４００は、４０６において次の圧縮レコードファイルをチェックし、それが存在するのであれば、そのファイルに対して処理を繰り返す。その所与のプライマリーキー値が選別を通過する（肯定的結果である）場合、手順４００は、４０８においてその所与のプライマリーキー値をもつ一つのレコードを含んでいる可能性がある一つのブロックに対するインデックスを検索する。いかなる選別データ構造も圧縮レコードファイルに関連付けられない場合、手順４００は、４０８において、選別を実施せずにインデックスを検索する。
【００８０】
４０８においてインデックスを検索した後、４１０において前記所与のプライマリーキー値を含むキー値範囲に関連付けられた圧縮ブロックが見つかった場合、手順４００は、４１２においてインデックスの入り口よって特定される位置にあるのブロックを解凍し、４１４において、前記所与のプライマリーキーをもつ一つまたはそれ以上のレコードを求めて、生じたレコードを検索する。手順は、次いで、４１６において次の圧縮レコードファイルをチェックし、それが存在するのであれば、そのファイルに対して処理を繰り返す。圧縮ブロックが一つも見つからない場合（例えば、前記所与のプライマリーキー値が、最初のブロック内の最小のキー値より小さいか、または最終のブロック内の最大のキー値より大きい場合）、手順４００は、４１６において次の圧縮レコードファイルをチェックし、それが存在しているのであれば、そのファイルに対して処理を繰り返す。
【００８１】
図４Ｂは、所与の一つのセカンダリキー値をもつ一つまたはそれ以上のレコードを検索するための手順４５０のフローチャートを示す。手順４５０は、４５２において最初の圧縮レコードファイルに関連付けられた選別データ構造があるか否かを判定する。データ構造がある場合、手順４５０は、４５４において、選別データ構造の処理により肯定的または否定的結果のいずれかを得る。前記所与のセカンダリキー値が選別を通過しない（否定的結果である）場合、手順４５０は、４５６において、次の圧縮レコードファイルをチェックし、それが存在するのであれば、そのファイルに対して処理を繰り返す。前記所与のセカンダリキー値が選別を通過する（肯定的結果である）場合、手順４５０は、４５８において前記所与のセカンダリキーを含むレコードに対応するプライマリーキーを調べる。いかなる選別データ構造も圧縮レコードファイルに関連付けられていない場合、手順４５０は、４５８において、選別を実施せずにプライマリーキーを調べる。
【００８２】
見つかったプライマリーキーの各々に対して、手順４５０は、４６０において所与のプライマリーキー値をもつ一つのレコードを含む可能性がある一つのブロックに対するインデックスを検索する。４６０においてインデックスを検索した後、４６２において前記所与のプライマリーキー値を含むキー値範囲に関連付けられた圧縮ブロックが見つかった場合、手順４５０は、４６４においてインデックスの入り口によって特定される位置にあるブロックを解凍し、４６６において前記所与のプライマリーキーをもつ一つまたはそれ以上のレコードを求めて、生じたレコードを検索する。その後、手順は、４６８において次の圧縮レコードファイルをチェックし、それが存在するのであれば、そのファイルに対して処理を繰り返す。圧縮ブロックが見つからない場合、手順４５０は、４６８において次の圧縮レコードファイルをチェックし、それが存在するのであれば、そのファイルに対して処理を繰り返す。
【００８３】
所与のプライマリまたはセカンダリキーとともに見つけられた多数のレコードは、手順４００または手順４５０において出現順に戻されることができ、または、場合により、レコードの最後のバージョンだけが戻される。
【００８４】
上述のレコード記憶装置と検索手法は、コンピュータ上で実行されるソフトウェアを使用して実現することができる。例えば、ソフトウェアは、一つまたはそれ以上のプログラムされた又はプログラム可能なコンピュータシステム（分散型、クライアント／サーバ、グリッド型など、さまざまなアーキテクチャに基づくもの）上で実行される一つまたはそれ以上のコンピュータプログラムにおいて手順を形成する。それらのコンピュータシステムのそれぞれは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム（揮発性、不揮発性のメモリおよび／または記憶素子を含む）、少なくとも一つの入力装置またはポート、並びに、少なくとも一つの出力装置またはポート、を含む。ソフトウェアは、例えば、計算グラフのデザインと構成とに関連する他のサービスを提供する、より大きなプログラムの一つ以上のモジュールを形成していてもよい。グラフのノードおよび構成要素は、コンピュータ読取り可能記録媒体に格納されたデータ構造として、またはデータ保存場所に格納されたデータモデルと整合するその他の組織化されたデータとして実装することができる。
【００８５】
ソフトウェアは、汎用の、または特定目的のためのプログラム可能なコンピュータによって読取り可能なＣＤ−ＲＯＭのような記録媒体で提供されてもよいし、またはそれが実行されるコンピュータに対してネットワーク経由で配布してもよい（伝播信号にコード化される）。その機能のすべては、特定目的のためのコンピュータ上か、またはコプロセッサのように、特殊目的のためのハードウェアを使用して実行される。ソフトウェアは、ソフトウェアによって指定される計算の異なる部分が異なるコンピュータによって実施されるような分散された方法で実装してもよい。記憶媒体または装置をコンピュータシステムが読み込んで、本明細書に記載された手順を実施するとき、コンピュータを構成し操作するために、そのような各コンピュータプログラムは、好ましくは、汎用または特定目的のプログラム可能なコンピュータで読取り可能な記憶媒体または装置に格納またはダウンロードされる（例えば、ソリッドステートのメモリもしくは媒体、または磁気的もしくは光学的媒体）。本発明のシステムは、コンピュータプログラムによって構成され、コンピュータ読取り可能記憶媒体として実装してもよい。そのように構成された記憶媒体によって、コンピュータシステムを特定かつ所定の方法で動作させて本明細書に記載する機能を実現する。
【００８６】
本発明の多くの実施の形態について説明した。しかしながら、本発明の趣旨と範囲から逸脱することなくさまざまな改変を行えることは言うまでもない。例えば、上記手順のいくつかは、独立した順序であってもよく、したがって説明とは異なる順序で実施することができる。
【００８７】
上記説明は、付帯する特許請求の範囲によって規定される本発明の範囲を示すことを意図しており、その範囲を制限するものではない。例えば、上記の機能の多くの手順は、全体の処理に実質的に影響を及ぼすことなく、異なる順序で実施してもよい。その他の実施の形態は、後述する特許請求の範囲内にある。
【図１】
2010508606.tif 000002
【図２Ａ】
2010508606.tif 000003
【図２Ｂ】
2010508606.tif 000004
【図２Ｃ】
2010508606.tif 000005
【図２Ｄ】
2010508606.tif 000006
【図３Ａ】
2010508606.tif 000007
【図３Ｂ】
2010508606.tif 000008
【図４Ａ】
2010508606.tif 000009
【図４Ｂ】
2010508606.tif 000010
【国際調査報告】
2010508606.tif 000011