JP5847578B2 - 個別にアクセス可能なデータユニットの記憶の取り扱い方法 - Google Patents

Description

本発明は、個別にアクセス可能なデータユニットの記憶の取り扱いに関する。

データベースシステムは、個別にアクセス可能な、複数のデータユニット又は「複数のレコード（記録）」を、種々の形式（フォーマット）にて、記憶することができる。それぞれのレコードは、クレジットカードの取引等の論理要素（logical entity）に対応することができ、一般的にはそのレコードを一意に特定するために使用される関連する主キーを有する。レコードは、レコードフォーマット（記録形式）の対応するフィールド（領域）に関連付けられた多数の値を含むことができる。複数のレコードは、一つ又はそれ以上のファイル（例えば、フラットファイル、又は、ＸＭＬファイル等の構造化データファイル）内に記憶され得る。圧縮されたデータベースシステムにおいて、個別のレコード又はレコード内の値は、そのシステムの必要メモリを低減するために、記憶時に圧縮され且つアクセスされたときに解凍され得る。

概して、一つの態様における方法は、ファイルの長さを決定すること、及び、そのファイルの長さを第１記憶場所（first memory location）内に記憶すること、を含む。そのファイル内の最後の完全なレコードの終了点が決定され、その終了点は第２記憶場所（second memory location）内に記憶される。第１記憶場所内に記憶されたファイルの長さは、そのファイルの現在の長さと比較され、そのファイルの現在の長さが第１記憶場所内に記憶されているそのファイルの長さを超える場合には、そのファイルと関連付けられているデータの構造が更新（アップデート）され、その更新は前記終了点から開始する。

本発明の態様は、一つ又はそれ以上の以下に述べる特徴を含むことができる。データ構造は、ハッシュ表（hash table）又は二分木（binary tree）等の結合データ構造（associative data structure）であり得る。前記終了点は前記ファイルの終了をも表し得る。前記終了点は前記ファイル内の不完全な（完結していない）レコードの前に位置するであろう。前記ファイルはエラーを有するか否かのチェックが為されてもよい。そのファイルがエラーを有するかどうかをチェックすることは、そのファイルの現在の長さが第１記憶場所内に記憶されたそのファイルの長さよりも小さいか否かを決定することを含み得る。そのファイルは圧縮されていないデータファイルであってもよい。

概して、本発明の他の態様における方法は、データストリームからのデータを、第１ファイル及びバッファに同時に追加する（加える）ことを含む。そのバッファに関連付けられるデータは、予め定義された条件が満足された後に一つの圧縮ファイルへ移動させられる。そのバッファからのデータがその圧縮されたデータに移動させられた後、第２のファイルが生成され前記データストリームからデータを受けとる。

本発明の態様は、一つ又はそれ以上の以下に述べる特徴を含むことができる。前記第１ファイルは、前記バッファからのデータが前記圧縮されたファイルへと移動された後に削除され得る。ステータス情報は、前記第１ファイルがアクティブであるか否かを特定し得る。そのステータス情報は、前記バッファに関連付けられたデータが前記圧縮されたファイルに移動させられている間、ロックされ得る。そのステータス情報は更新され、前記第２ファイルの生成、前記第１ファイルの削除、及び、前記バッファと前記圧縮されたファイル間のデータの転送を反映する。ステータス情報がロックされている間、そのステータス情報は、インデックス付与動作又は検索動作によってはアクセスすることができない。そのステータス情報は、そのステータス情報が更新された後、開かれる（ステータス情報のロックが解除される）。前記第１ファイルは、前記ステータス情報が更新された後に削除され得る。前記予め定義された条件は時間に基づくことができる。前記予め定義された条件は前記第１ファイルのサイズに基づくことができる。前記予め定義された条件はレコードの数に基づくことができる。

概して、他の態様は、装置信号からの値を取得する際に使用される実行可能な指示を記憶するコンピュータ可読媒体であって、前記指示はコンピュータに、ファイルの長さを決定し、且つ、前記ファイルの前記長さを第１記憶場所に記憶させる、媒体である。前記ファイル内の最後の完全なレコードの終了点が決定され、且つ、その終了点は第２記憶場所に記憶され得る。前記第１記憶場所に記憶された前記ファイルの長さは、前記ファイルの現在の長さと比較され得る。前記ファイルの現在の長さが前記第１記憶場所に記憶された前記ファイルの長さを超えているのであれば、前記ファイルと関連するデータ構造は前記終了点を開始位置として更新されることができる。

本発明の態様は、一つ又はそれ以上の以下に述べる特徴を含むことができる。前記データ構造は、ハッシュ表又は二分木等の結合データ構造であり得る。前記終了点は前記ファイルの終わりをも表すことができる。前記終了点はそのファイル内の不完全なレコードの前に位置するであろう。前記指示は、前記コンピュータに更に前記ファイルにエラーがないかどうかチェックすることを行わせる指示であることができる。前記ファイルにエラーがないかどうかチェックすることは、前記ファイルの前記現在の長さが前記第１記憶場所に記憶された前記ファイルの前記長さよりも短いか否かを判定することを含むことができる。前記ファイルは非圧縮データファイルであってもよい。

概して、他の態様は、装置信号からの値を取得する際に使用される実行可能な指示を記憶するコンピュータ可読媒体であって、前記指示はコンピュータに、データストリームからのデータを第１ファイルとバッファとに同時に追加させる指示である、媒体である。予め定義された条件が満足された後、前記バッファに関連付けられた前記データは圧縮されたファイルに移動させられる。前記バッファからの前記データが前記圧縮されたファイルに移動させられた後、第２ファイルが生成され、前記データストリームからデータを受け取る。

本発明の態様は、一つ又はそれ以上の以下に述べる特徴を含むことができる。前記バッファからの前記データが前記圧縮されたファイルに移動させられた後、前記第１ファイルは削除され得る。ステータス情報は前記第１ファイルがアクティブであるか否かを特定することができる。前記バッファに関連付けられた前記データが前記圧縮されたファイルに移動させられている間、前記ステータス情報はロックされ得る。前記ステータス情報は、前記第２ファイルの生成、前記第１ファイルの削除、及び、前記バッファと前記圧縮されたファイルとの間のデータの移動を反映するために更新され得る。前記ステータス情報がロックされている間、前記ステータス情報は前記インデックス付与動作又は検索動作によってアクセスされることができない。前記ステータス情報のロックは、前記ステータス情報が更新された後に解除され得る。前記ステータス情報が更新された後、前記第１ファイルが削除され得る。前記予め定義された条件は時間に基づくことができる。前記予め定義された条件は前記第１ファイルのサイズに基づくことができる。前記予め定義された条件はレコードの数に基づくことができる。

概して、他の態様において、システムは、ファイルの長さを決定し、且つ、前記ファイルの前記長さを第１記憶場所に記憶する手段を含む。そのシステムは、更に、前記ファイル内の最後の完全なレコードの終了点を決定し、且つ、前記終了点を第２記憶場所に記憶する手段を含む。そのシステムは、更に、前記第１記憶場所に記憶された前記ファイルの前記長さを前記ファイルの現在の長さと比較する手段、及び、前記ファイルの前記現在の長さが前記第１記憶場所に記憶された前記ファイルの前記長さを超える場合、前記終了点にて開始する前記ファイルに関連付けられたデータ構造を更新する手段、を含む。

概して、他の態様におてい、システムは、データストリームからのデータを第１ファイルとバッファとに同時に追加する手段を含む。そのシステムは、更に、予め定義された条件が満足された後、前記バッファに関連付けられた前記データを圧縮されたファイルに移動させる手段、及び、前記バッファからの前記データが前記圧縮されたファイルに移動された後、第２ファイルを作って前記データストリームからデータを受け取る手段、を含む。

レコードを記憶し且つ読み出すシステムのブロック図である。 前記システムにより処理され且つ記憶されるデータの概略図である。 前記システムにより処理され且つ記憶されるデータの概略図である。 前記システムにより処理され且つ記憶されるデータの概略図である。 前記システムにより処理され且つ記憶されるデータの概略図である。 種々のシグナチャサイズに対する虚偽の肯定的可能性を示す表である。 種々のシグナチャサイズに対する虚偽の肯定的可能性を示す表である。 レコードを検索するための手続きのフローチャートである。 レコードを検索するための手続きのフローチャートである。 レコードの問い合わせを行うための手続きのフローチャートである。 付加可能なルックアップファイルの概略図である。 付加可能なルックアップファイルの概略図である。 付加可能なルックアップファイルの問い合わせを行うための手続きのフローチャートである。 データを記憶するための手続きのフローチャートである。

図１を参照すると、レコードの記憶及び読出しシステム１００は、例えばソースＡ乃至ソースＣといった一つ又はそれ以上のソース（情報源）からデータを受け取る。そのデータは、個別にアクセス可能なデータの単位（ユニット）として表され得る情報を含む。例えば、クレジットカード会社は、様々な小売業者からの個々の取引を表すデータを受信することができる。それぞれの取引は、カスタマーの名前、日付、購入額等の複数の属性を表す複数の値と関連付けられる。レコード処理モジュール１０２は、そのデータが所定のレコードフォーマット（記録形式）に応じてフォーマットされていることを保証し、それによって一つの取引と関連付けられている複数の値が一つのレコード内に記憶（格納）される。いくつかの場合において、このことは前記ソースからのデータを前記レコードフォーマットに従って変換することを含み得る。他の場合において、一つ又はそれ以上のソースは、前記レコードフォーマットに従って既にフォーマットされているデータを提供することができる。

レコード処理モジュール１０２は、記憶用のレコードを、例えば、記憶された複数のレコードに迅速にアクセスする必要があるかも知れないか否か等の様々なファクタに応じた様々なタイプのデータ構造にて準備する。付加可能なルックアップファイル（appendable lookup file）における早いアクセサビリティのためのレコードを準備する場合、前記処理モジュール１０２は、後に詳述するように、レコードがその付加可能なルックアップファイル内に到着したときにそのレコードを付け足し、且つ、メモリー内インデックス（in-memory index）をメンテナンスする。圧縮されたレコードファイル内で圧縮記憶用の複数のレコードを準備する場合、前記処理モジュール１０２は、その複数のレコードを、各レコードを特定する主キー値（例えば、単一のレコードを特定する唯一のキーか、あるいは、一つのレコードの更新された複数のバージョンを特定する一つのキー等）によってソートし、且つ、前記処理モジュール１０２はその複数のレコードを、主キー値が重なることのない範囲に対応する複数のレコードの複数のセットへ、と分割する。例えば、複数のレコードのセットのそれぞれは、所定数のレコード（例えば１００のレコード）に対応し得る。

ファイル管理モジュール１０４は、前記付加可能なルックアップファイル（それらが使用される場合において）及び圧縮されたルックアップファイルの両者を扱う（管理する）。圧縮されたレコードファイルを扱う場合、ファイル管理モジュール１０４はレコードのセットのそれぞれを圧縮されたデータのブロックへと圧縮する。これらの圧縮されたブロックはレコード記憶装置１０６内（例えば、一つまたはそれ以上のハードディスクドライブ等の不揮発性記憶媒体内）の圧縮されたレコードファイル内に記憶される。

システム１００はインデックス付与及び検索モジュール１０８も含み、そのインデックス付与及び検索モジュール１０８は一つの圧縮されたレコードファイル内の複数のブロックのそれぞれに対する入り口（entry）を含むインデックス（索引）を提供する。そのインデックスは、後に詳述するように、所与のレコードを含むことができるブロックの位置を探し出すために使用される。そのインデックスは、インデックス記憶装置１１０内のインデックスファイル内に記憶され得る。例えば、前記インデックスファイルは前記圧縮されたレコードファイルと同じ記憶媒体内に記憶され得るが、前記インデックスファイルは一般的に圧縮されたレコードファイルよりも非常に小さいことから、前記インデックスファイルは好ましくは相対的により早いメモリ（例えば、ダイナミックランダムアクセスメモリのような揮発性媒体）内に記憶され得る。前記インデックスはメモリ内データ構造として維持されるダイナミックインデックス１１４であってもよい。ダイナミックインデックス１１４の幾つかの例は、ハッシュ表（hash table）、二分木（binary tree）及びｂ−ツリー（b-tree）である。インデックス付与及び検索モジュール１０８は、また、後に詳述するように、付加可能なルックアップファイルを検索するためのインターフェーを提供する。

システム１００の別の実施形態において、レコードのセットは処理され、圧縮に加え又は圧縮に代え、他の機能を使用するブロックを発生し、複数のレコードを何がしかの方法で結合する（即ち、ブロックは単なる連結されたレコードのセットではない）。例えば、いくつかのシステムは複数のレコードからなる一つのセットを処理して暗号化されたデータの複数のブロックを発生させることができる。

インターフェースモジュール１１２は、前記記憶されたレコードへのアクセスを、例えば、エージェントＡ乃至エージェントＤ等の人間及び／又はコンピュータエージェントに提供する。例えば、インターフェースモジュール１１２は、クレジットカードのカスタマーが彼らの取引について監視するためのオンライン口座システムを実現することができる。様々なクライテリアを満たす取引情報に対する要求はシステム１００によって処理され、且つ、対応するレコードがレコード記憶装置１０６内に記憶された圧縮されたブロック内から読み出され得る。

一つ又はそれ以上のソースからの入ってくるレコードの流れは、圧縮されたレコードファイルを発生するように処理される前に一時的に記憶されてもよい。

図２Ａ−２Ｄ、３Ａ−３Ｂ及び４Ａ−４Ｂは、圧縮されたレコードファイル内において複数のレコードを扱う（管理する）例を示す。図５及び図６Ａ−６Ｂは、付加可能なルックアップファイルを用いて複数のレコードを扱う例を示す。図２Ａを参照すると、システム１００は圧縮されたレコードファイル内に記憶されるべき複数のレコードのセット２００を受け取り、且つ、その複数のレコードを主キーの値に応じてソート（分類）する。

一つの主キー値は、一つ又はそれ以上のレコードにより表され得る一つのデータベース内の所与の一つのアイテムを一意に特定することができる（例えば、所与の主キー値を有する各レコードはそのアイテムの異なった更新バージョンに対応してもよい）。主キーは、一つのレコードの一つ又はそれ以上の存在している領域（フィールド）に対応する「自然のキー」であってもよい。各アイテムに対して一意であることが保証される領域がない場合、主キーは一つのレコードの複数の領域（その複数の領域は一緒になって各アイテムに対して一意であることが保証されるか又は一意である確からしさが高い）を備える複合キーであり得る。代替として、主キーは各レコードが受け取られた後に各レコードに割り当てられることができる「人工キー」であってもよい。例えば、システム１００は、一意の主キー値を連続的にインクリメントされる整数に指定し、又は他の単調に進む値を有する数列（例えば、タイムスタンプ）に指定する。この場合、同じアイテムの異なるバージョンを表す複数のレコードには異なる人工キー値が割り当てられるであろう。整数が用いられる場合、主キー値が取ることが可能な範囲（例えば、使用されるビット数により決定されるように）は十分に大きく、従って、主キーがロールオーバーすると（繰り越すと、roll over）、所与の主キー値が先に割り当てられている如何なるレコードも圧縮されたレコードファイルから取り除かれてしまっている。例えば、古い取引は取り除かれ且つアーカイブされるか又は破棄される。

図２Ａに示された例においては、レコード２００はアルファベット順にソートされた主キー値：Ａ，ＡＢ，ＣＺ，…により特定される。システム１００は主キー値Ａ−ＤＤを有するＮ個のレコードからなる第１のセットを圧縮し、ＢＬＯＣＫ１の名前が付けられた対応する圧縮されたブロックを生成する。次のレコードのセットは、主キー値ＤＸ−ＧＦを有するソートされた次のＮ個のレコードを含む。ファイル管理モジュール１０４は、様々な無損失データ圧縮アルゴリズム（例えば、Ｌｅｍｐｅｌ−Ｚｉｖタイプアルゴリズム）の如何なるものをも使用することができる。各連続する圧縮されたブロックは結合され、圧縮されたレコードファイル２０２が形成される。

一つの圧縮されたブロックを生成するために使用されるレコードの個数Ｎは、圧縮効率と解凍スピードとの間の得失評価（トレードオフ）に基づいて選択され得る。圧縮は、平均的には圧縮されているデータの性質及び圧縮されているデータのサイズに依存する所与のファクタＲ（例えば、Ｒは一般的にはより多くのデータが圧縮されているときほど小さくなる）だけデータのサイズを減じることができる。圧縮はまた、平均的大きさがＯである関連するオーバーヘッド（例えば、圧縮関連データ）を有する。各サイズがＸであるＭ個のレコードから生成された圧縮レコードファイルの平均サイズは、［Ｍ／Ｎ］（ＲＮＸ＋Ｏ）として表されることができ、多くの数のブロックに対しては、ＲＭＸ＋ＯＭ／Ｎと近似され得る。それ故、Ｎの値が大きくなるほど、いくつかの場合において、Ｒを減じること及びファイルのサイズに対するオーバーヘッドの負担を減じることの両者によって、より大きい圧縮がもたらされる。Ｎの値が小さくなるほど、所与の圧縮ブロック内に含まれているであろう一つのレコードにアクセスするためにそのブロックを解凍するのに必要な時間が短くなる。

他の実施形態において、異なる圧縮されたブロックは異なる数のレコードを含むことができる。各ブロックは、所定の範囲に応じたレコードの数を有することができる。例えば、第１のブロックは主キー値１〜１０００を有するレコードを含み、第２のブロックは主キー値１００１〜２０００等を有するレコードを含む。圧縮されたブロックにおけるレコードの数はこの例において異なり得る。それは、必ずしも総ての主キー値が存在するとは限らないからである（例えば、一つの自然のキーとして使用される一つの存在している数値的領域の場合）。

いくつかの実施形態では、いくつかの場合において異なる圧縮されたブロックはレコードの目標数を含むことができ、例外的な場合においてはより多くの又はより少ないレコードを含むことができる。例えば、複数のレコードの一つのセットが、その主キー値が、記憶された順において後続しているレコードの主キー値と異なるレコードで終了する場合、これらのレコードは一つの圧縮されたブロックを生成するために使用される。複数のレコードの一つのセットが、その主キー値が、記憶された順において後続しているレコードの主キー値と同じレコードで終了する場合、その主キー値を有している総ての追加的レコードはそのセットに追加される。このようにして、同じ主キー値は、一つの圧縮されたブロックから次のブロックへとクロスオーバーしない（ブロックの枠を超えない）。

インデックス付与及び検索モジュール１０８は、圧縮されたブロックのそれぞれに対してインデックスファイル２０４内に入り口（entry）を生成する。そのインデックスの入り口は、各圧縮されたブロックを、例えば、対応する圧縮されていないレコードのセットにおける最初のレコードの主キー値により、特定するキー領域２０６を含む。入り口は、また、圧縮されたレコードファイル２０２内におけるその特定された圧縮ブロックの記憶場所を特定する場所領域２０８を含む。例えば、場所領域は、レコード記憶装置１０６内の絶対アドレスの形式のポインタを含むことができ、或いは、レコード記憶装置１０６における圧縮されたレコードファイル２０２の開始アドレスからのオフセットの形式のポインタを含むことができる。

圧縮されたレコードファイル２０２内で所与の一つのレコードを検索するために、モジュール１０８は、キー領域２０６に基づいてインデックスファイル２０４の検索（二分検索）を実行することができる。ある与えられたキー値に対して（例えば、前記エージェントの一つにより提供されるキー値に対して）、モジュール１０８は、その与えられたキー値を含む複数のキー値からなる一つの範囲に対応する複数のレコードを含む一つのブロックを見つけ出す。前記与えられたキー値を有するレコードは、その見つけ出されたブロックを生成するのに使用された複数のレコードのセット内に含まれていたかもしれないし含まれていなかったかもしれないが、もし、そのレコードがレコード２００内に存在したのであれば、レコード２００は主キー値によってソートされたのであるから、そのレコードは（そのブロックに）含まれているであろう。モジュール１０８は、それからその見つけ出されたブロックを解凍し、その与えられたキー値を有する一つのレコードを検索する。主キー値が各レコードに対して一意的出ない場合、モジュール１０８はその与えられたキー値を有する複数のレコードをその圧縮されたブロック内に見つけるかもしれない。キー領域２０６が一つのセットにおける最初のレコードの主キー値を含む本例の場合、モジュール１０８は二つの連続するインデックス入り口であって、その与えられたキー値よりも早い及び遅いキー値をそれぞれ有する二つのインデックス入り口を検索し、そのより早いキー値を有する入り口に対応するブロックに戻る。いくつかの場合、前記与えられたキー値は一つのインデックス入り口のキー値と同じであり得、その場合、モジュール１０８はその入り口に対応するブロックに戻る。

異なる実施形態において、インデックスファイル２０４における入り口が、その対応するブロックが生成された複数のレコードに対応する複数のキー値の範囲を特定するための、異なる方法が存在する。図２Ａに示された実施形態において見られるように、複数のキー値の範囲は、一つのブロックを生成するのに使用された複数のレコードの二つの極値（例えば、アルファベットの主キー値のソートされた並びにおける最初及び最後、或いは、数値の主キー値のソートされた並びにおける最小及び最大）の間の範囲であり得る。そのインデックス入り口は、その範囲を規定する極値のいずれか一方または両方を含むことができる。ある実施形態において、そのインデックス入り口が所与の一つのブロックの範囲を規定する最小のキー値を含んでいるであれば、一つの圧縮レコードファイルにおいてその最後のブロックに関連付けられている最後のインデックス入り口は、そのブロックの範囲を規定する最大キー値を含み得る。この最大キー値は、その圧縮されたレコードを検索する際に使用されることができ、所与のキー値がいつ領域外となるのかを決定する。

代替として、キー値の範囲は、一つのブロックを生成するのに使用された複数のレコードのキー値を越えて広がっている範囲であり得る。例えば、１と１０００との間の数値的主キー値を有する複数のレコードから生成された一つのブロックの場合、その複数のレコードにおいて表される最小のキー値は１よりも大きく、その複数のレコードにおいて表された最大のキー値は１０００よりも小さいであろう。インデックス入り口は、その範囲を規定する極値１及び１０００の何れか一方又は両方を含むことができる。

最初の複数のレコードのグループが一つの圧縮されたレコードファイルを生成するために処理された後に追加的な複数のレコードが到着すると、それらのレコードはバッファ内に記憶され且つ圧縮されない形において検索され得る。代替として、追加的なレコードのグループは、増加的に処理され、且つ、追加的インデックスファイルによりアクセス可能な追加的な圧縮されたレコードファイルとして記憶される。いくつかの場合、僅かな個数の追加的レコードを圧縮することが、記憶サイズのより多くの減少をもたらさないかもしれないときでさえ、レコードをアクセスするための統一のとれた手続きを維持するために、その追加的レコードを圧縮することは依然として好都合である。追加的レコードは、通常の時間間隔（例えば、３０秒毎、又は、５分毎）で繰り返し処理され得、或いは、所定数の追加的レコードが受け取られた後（例えば、１０００レコード毎、又は、１００００レコード毎）に繰り返し処理され得る。もし、入ってくるレコードが時間間隔に基づいて処理されるのであれば、いくつかの時間間隔においては、入ってくるレコードが全くないか、又は、単一の圧縮されたブロックへと総てが圧縮される程度の少ない数のレコードが存在する。

図２Ｂを参照すると、最初の圧縮されたレコードファイル２０２が発生された後に追加的なレコードがシステム１００によって受け取られる例において、追加的な圧縮レコードファイル２１０がその最初の圧縮されたレコードファイル２０２に付加されることができ、合成された圧縮レコードファイル２１１が形成される。システム１００は、主キー値によりその追加的なレコードをソートし、且つ、Ｎ個のレコードからなる複数のセットを圧縮して圧縮されたレコードファイル２１０の圧縮された複数のブロックを生成する。付加されたファイル２１０内の第１の圧縮されたブロックであってブロック９１との名前が付けられたブロックは、主キー値ＢＡ−ＦＦを有する。モジュール１０８は、付加されたファイル２１０内において表された付加的なレコードを検索するために使用され得る入り口を含む追加的なインデックスファイル２１２を生成する。その新しいインデックスファイル２１２は先のインデックスファイル２０４に付加され得る。

圧縮されたレコードファイルはいくつでも付加されることができ、一つの合成圧縮レコードファイルが形成される。インデックス付与及び検索モジュール１０８が、一つの合成圧縮レコードファイル内において所与のキー値を有する一つのレコードを検索しているのであれば、モジュール１０８は、その対応するインデックスファイルを用いて、その付加された圧縮レコードファイルのそれぞれの内部においてそのレコードを検索する。代替として、一つの所与のレコードを要求するエージェントは、検索されるべき合成圧縮レコードファイルを有する圧縮レコードファイルの幾つかの数（例えば、最近生成された１０個、又は、最近１時間以内において生成されたもの総て）を特定することができる）。

所与の時間の経過後（例えば、２４時間毎）、又は、所与の数の圧縮レコードファイルが付加すれた後、システム１００はその複数のファイルを合併し、一つの合成圧縮レコードファイルと一つの新しい対応するインデックスファイルとからなる単一の圧縮レコードファイルを生成することができる。合併の後、単一のインデックスが検索され、所与のレコードを含むかもしれない圧縮されたブロックを探し出すことができる。合併を行うとき、システム１００は圧縮されたレコードファイルを解凍してソートされた複数のレコードの対応する複数のセットを回復し、そのレコードを主キー値によりソートし、新しい圧縮されたレコードファイルとインデックスとを生成する。回復されたレコードのセットのそれぞれは既にソートされているので、単一のソートされたレコードのセットを生成するために主キー値に従って先にソートされたリストを合併することにより、その複数のレコードは効率的にソートされることができる。

図２Ｃを参照すると、前記合成圧縮レコードファイル２１１は、最初の圧縮レコードファイル２０２、追加的な圧縮レコードファイル２１０、及び、幾つかの追加的圧縮レコードファイル２２０、２２１、…その数はいくつの追加的レコードが到着し且つどのくらの頻度でそのレコードが処理されたかに依存するのだけれども、を含む。各圧縮レコードファイルは、関連するインデックスファイルであってその圧縮レコードファイルの複数の圧縮されたブロック内において所与のレコードを検索するために使用され得るインデックスファイル、を有することができる。この例において、圧縮されたレコードファイルのうちの一つであるファイル２２０は十分に小さいので、単一の圧縮されたブロック（ブロック９５）のみを有し、それ故、関連付けられたインデックスファイルを必ずしも必要としないが、そのブロック内における主キー値の範囲及び記憶装置内の場所を示す関連するデータを有することができる。合併の後、その異なる付加された圧縮レコードファイルから回復された複数のレコードは処理され、単一の圧縮されたレコードファイル２３０が生成される。

単調に割り当てられた主キーの場合、レコードは、圧縮されたレコードファイル内のみならず、一つのファイルから次のファイルへと、自動的にソートされ、単一インデックス検索において一つのレコードにアクセスするためにファイルを合併する必要性が取り除かれる。図２Ｄを参照すると、システム１００は、そのレコードの主キー値として到着順に割り当てられた連続する整数によって特定される複数のレコード２５０のセットを受け取る。よって、レコード２５０は主キーにより自動的にソートされる。最初の圧縮されたレコードファイル２５２は、この例においてそれぞれが１００個のレコードを含んでいる圧縮されたブロックを含み、インデックスファイル２５４は、一つの圧縮されたブロックの最初のレコードの主キー値に対するキー領域２５６と、対応する記憶場所を特定する場所領域２８５と、を含む。最初の圧縮されたレコードファイル２５２が生成された後に到着する複数のレコードは自動的に後にソートされる順である主キー値を有するであろうから、付加された圧縮レコードファイル２６０及び対応するインデックスファイル２６２は、単一のインデックス検索に基づいた効率的なレコードへのアクセスを可能とするために合併される必要はない。例えば、インデックスファイル２６２は、単にインデックスファイル２５４に付加されることができ、両インデックスは一つの圧縮されたブロックを圧縮されたレコードファイル２５２又は２６０の何れかにおいて探しだすために一緒に検索され得る（例えば、単一の二分探索において）。

合成圧縮レコードファイル２６１は、オプションで、合併され、圧縮レコードファイル２５２の最後に挿入されたかもしれない不完全なブロックが排除される。そのような合併においては、最初のファイル２５２における最後の圧縮されたブロックのみが解凍される必要があり、複数のレコードの解凍されたセットを合併する代わりに、複数のレコードのセットは単に鎖状に連結され得、１００個のレコードのセットに分割されそれから再び圧縮されて一つの新しい圧縮レコードファイルを形成する、新たなソートされたレコードのセット、を形成する。

連続する整数の合成の主キー値を用いることの他の有利な点は、複数のレコードが主キー値に基づいて分割されようとしているのであれば、キー値間にはギャップがないので、その分割は自動的にバランスが保たれ得ることである。

レコードを更新するために、及び、圧縮されたレコードファイル内に存在するかもしれないレコードの先のバージョンを無効化するために、色々な技法の何れもが使用され得る。いくつかの場合において、レコードは、取り去られる或いは個別に更新される必要はない（例えば、ログ、取引、通話）。これらの場合において、古いレコードは、取り去られ且つ破棄され、或いは、所定数の圧縮されたブロックのグループ毎に、例えば、一つの圧縮されたレコードファイルの最初から、アーカイブ化され得る。いくつかの場合において、圧縮されたレコードファイルの全体が除去され得る。

いくつかの場合において、一つの圧縮されたブロック内に記憶するために新しい更新されたレコードを加えることにより一つのレコードの一つ又はそれ以上の値が更新され、先に受け取られたレコードのバージョン（同じ主キー値を有する）は異なる圧縮されたブロック内に記憶されたままにされ得る。そのため、一つのレコードの複数のバージョンがあることになるので、何らかの技法が用いられてどれがそのレコードの有効なバージョンであるかを決定する。例えば、圧縮されたレコードファイル内に現れる最後の（最も近々において受信された）バージョンは、暗黙のうちに或いは明白に有効なバージョンとして示されことができ、且つ他のバージョンは総て無効である。この場合において、所与の主キーを有するレコードの検索は、その主キーにより特定されるレコードであって現れた順において最後のレコードを見つけることを含むことができる。代替として、一つのレコードは、新しいレコードのバージョンを必ずしも追加しなくても、そのレコードの先のバージョンは総て有効でないということを示す「レコードを無効化せよ」と書くことより無効化され得る。

システム１００は、種々のプロセスによりレコード記憶装置１０６内に記憶された圧縮されたレコードファイルへのアクセスをとりなす。一つ又はそれ以上の圧縮されたレコードファイル内において圧縮されたブロックへのアクセスをとりなすため、様々な同期化の技法のどれでもが使用され得る。システム１００は、ファイルを（例えば、データを付加したり或いは合併（統合）したりすることにより）修正する如何なる処理も互いに干渉しないことを保証する。例えば、合併が発生しているときに新しいレコードが到着すると、システム１００は、その合併処理が終了するまで待つことができ、或いは、圧縮されたブロックを発生し且つそれらを存在する圧縮されたレコードファイルへと付加する前にそれらを一時的に記憶することができる。一つの圧縮されたレコードファイルから読み込む処理は、完全であるファイルの一部をロードすることができ、且つ、修正を受けているであろう不完全な如何なる部分をも無視することができる。

システム１００は、主キー以外のレコードの特性に基づいてレコードを検索することを可能にする追加的なデータを記憶する。一つの圧縮されたレコードファイルに対する補助的な（第２の）インデックスは、セカンダリーキー（二次的キー）として指定された特性値に基づいて一つまたはそれ以上の主キー値を提供する情報を含む。セカンダリーキーとして指定される特性のそれぞれは、対応するセカンダリーインデックスと関連付けされ得る。例えば、セカンダリーインデックスのそれぞれは、その関連付けされたセカンダリーキーによりソートされた行を有する表として体系化され得る。各行は、一つのセカンダリーキー値と、一つ又はそれ以上のレコードの主キー値であってセカンダリーキー値を含む主キー値と、を含む。従って、エージェントが所与のセカンダリーキー値を含むレコードの検索を開始すると、システム１００は、そのレコードを含む圧縮されたブロックに対する圧縮されたレコードファイルのインデックスを検索するために使用する主キーを調べる。第２のインデックスは大きいかもしれないし（例えば、レコードの数のオーダー程度）、いくつかの場合においては、前記圧縮されたレコードファイルを記憶する記憶媒体に記憶され得る。

いくつかの場合において、一つのセカンダリーキーとして指定される一つの特性の複数の値は、各レコードに対して唯一（一意）であり得る。そのような場合、そのセカンダリーキーとその主キーとの間には１対１対応が存在し、インターフェースモジュール１１２はセカンダリーキー特性を、そのセカンダリーキー特性があたかもエージェントに対して主キーであるかのように提示することができる。

セカンダリーインデックス（二次的インデックス）のそれぞれは、新しい圧縮されたレコードファイルが合成圧縮レコードファイルに付加されるときに更新され得る。代替として、セカンダリーキーは、圧縮されたレコードファイルのそれぞれに対して異なるセカンダリーインデックスと関連付けされ得る。そして、複数のセカンダリーインデックスは、圧縮されたレコードファイルが合併（統合）されるときに単一のセカンダリーインデックスへと合併（統合）され得る。

スクリーニングデータ構造は、所与の特性値を含む一つのレコードが一つの圧縮されたファイルのブロック内に含まれる可能性を決定するために、圧縮されたレコードファイルと関連付けられ得る。例えば、スクリーニングデータ構造としての重複コード化シグナチヤー（overlap encoded signature、ＯＥＳ）は、システム１００が、一つの所与のキー値（主キー又はセカンダリーキー）を有する一つのレコードが間違いなく存在しない（「否定的」結果）と決定すること、或いは、その所与のキー値を有するレコードが存在している可能性がある（「肯定的」結果）か否かを決定すること、を可能とする。肯定的結果に対しては、システムは適切な圧縮ブロックにアクセスして、そのレコードを読み取るか（「確認済み肯定的」結果）又はそのレコードが存在しないと決定する（「虚偽の肯定的」結果）。否定的結果に対しては、存在していないレコードに対する圧縮されたブロックを解凍し且つ検索することに時間を費やす必要なしに、システムはエージェントに否定的結果を与えることができる。そのＯＥＳのサイズは、どのくらいの頻度で肯定的結果が虚偽の肯定的結果であるかに影響を与える。一般には、より大きいＯＥＳのサイズはより少ない虚偽の肯定的結果を生む。ＯＥＳサイズが所与のサイズである場合、一般に、区別できる可能性のあるキー値が少ないほど（fewer distinct possible key values）、虚偽の肯定的結果はより少なくなる。

他のタイプのスクリーニングデータ構造も可能である。一つの所与の主キー又はセカンダリーキーに対する一つのスクリーニングデータ構造は、圧縮されたレコードファイルのそれぞれに対して提供され得る。代替として、一つのキーに対するスクリーニングデータ構造は、圧縮されたブロックのそれぞれに対して提供され得る。

図３Ａ及び図３Ｂは、典型的なＯＥＳスクリーニングデータ構造の様々なサイズ（列）、及び、圧縮されたレコードファイルにおいて表される区別可能なキー値の様々な数（行）、について、一つのキー値に対する虚偽の肯定的結果を得る確率値を提供する表を示す。一つのＯＥＳに対し、そのＯＥＳのサイズ及び区別可能なキー値の数に依存するのであるが、一つ以上のキー値の存在がそのＯＥＳの同じ部分において示され、それは、もし残りが存在するのであれば、潜在的にはそれらのキー値の一つに対する虚偽の肯定的結果につながる。この典型的なＯＥＳのサイズは、２^１０＝１０２４ビット（図３Ａの表において）から２^２８＝２５６Ｍビット（図３Ｂの表において）までの範囲で変化する。区別可能なキー値の数は、１００（図３Ａの表において）から１００，０００，０００（図３Ｂの表において）までの範囲で変化する。両方の表に関して、右上における空欄は０％に対応し、左下における空欄は１００％に対応している。虚偽の肯定の可能性が低い（例えば、略零）セルに関し、スクリーニングデータ構造は十分なスクリーニングを提供するのに必要な大きさ以上に大きいかもしれない。虚偽の肯定の可能性が高い（例えば、５０％よりも大きい）セルに関し、スクリーニングデータ構造は非常に小さいので十分なスクリーニングを提供することができない。この例は、一つのキー値あたり４つのハッシュコードを用いるＯＥＳを生成する技法に対応する。ＯＥＳスクリーニングデータ構造の他の例は、区別可能なキーの所与の数値に対して虚偽の肯定の可能性が異なる表を生み出す。

一つの圧縮されたレコードファイルにおいて表される区別可能なキー値の数を知ることができないので、システム１００は、その圧縮されたレコードファイルに対するスクリーニングデータ構造のサイズを、ファイルが生成されたレコードの数に基づいて、選択することができる。サイズを選択する際、虚偽の肯定的可能性を減じることとスクリーンデータ構造を記憶するのに必要なメモリ領域（空間）との間でトレードオフ（二律背反）がある。このトレードオフにおける一つのファクタは不在のキー値を検索する可能性である。もし、捜される予定のキー値の殆どが解凍されたレコード内に存在していそうであるならば、スクリーニングデータ構造は全く必要がないかもしれない。もし、キー値が見つからない可能性が非常に高いのならば、比較的大きいスクリーニングデータ構造に記憶領域を割り当てることは、かなりの時間を節約するかもしれない。

ひとつの圧縮されたレコードファイルに関連付けられたスクリーニングデータ構造のサイズは、そのファイルが最初又は合併されたレコードの大きいデータベースに対応しているか、或いは、より大きいデータベースに対する、より小さいアップデート（更新）に対応しているのか、に依存する。相対的により小さいスクリーニングデータ構造のサイズは、正規の（レギュラーな）間隔の更新中に付加された圧縮されたレコードファイルに対して使用され得る。一般的には、各更新における区別可能なキー値はより少ないからである。また、小さいサイズのものは、多くの更新後に圧縮されたレコードファイルの数が大きくなるにつれて必要となる記憶領域を減少させることができる。スクリーニングデータ構造のサイズは、一つの更新において予想される「レコード及び／又は区別可能なキー値」の数に基づくことができ、且つ、予想される更新の数に基づくことができる。例えば、更新されたファイルが２４時間の期間を通して５分毎に付加される場合、一日の終わりの時点で圧縮されたレコードファイルが２８８個となるであろう。少なくとも一つの虚偽の肯定的結果の可能性は、図３Ａ及び図３Ｂの表から得られる適切な値を２８８倍した値となるであろう（異なる更新についての結果は独立していると仮定した場合）。合併後においては、より大きいスクリーニングデータ構造が、その合併された圧縮されたレコードファイルに適しているであろう。区別可能なキー値の数が顕著に増加するかもしれないからである。

一つの圧縮されたレコードファイルは、主キー及び各セカンダリーキー、或いは、キーのサブセットに対して、一つのスクリーニングデータ構造を有することができる。例えば、システム１００は、主キー値について、且つ、レコードの検索において最も頻繁に使用されることが期待される複数のセカンダリーキーのみについて、一つのスクリーニングデータ構造を提供することができる。

図４Ａは、所与の一つの主キー値を有する一つ又はそれ以上のレコードを検索（サーチ）するための手続き４００についてのフローチャートを示す。手続き４００は、４０２にて、第１の圧縮されたレコードファイルに関連付けられたスクリーニングデータ構造があるか否かを判定する。もしあれば、手続き４００は４０４にてそのスクリーニングデータ構造を処理し、肯定的結果又は否定的結果の何れかを取得する。前記所与の主キー値がそのスクリーニングを通過しないのであれば（否定的結果）、手続き４００は４０６にて次の圧縮されたレコードファイルがあるかをチェックし、且つ、そのファイルが存在しているのであればそのファイル上で繰り返す。その所与の主キー値がスクリーニングを通過するのであれば（肯定的結果）、手続き４００は４０８にてその所与の主キー値を有するレコードを含むかもしれない一つのブロックに対するインデックスを検索する。前記圧縮されたレコードファイルに関連付けられたスクリーニングデータ構造がなければ、手続き４００は４０８にてスクリーニングを実施することなく前記インデックスを検索する。

４０８での検索の後、前記所与の主キー値を含むキー値の範囲と関連付けられた一つの圧縮されたブロックが４１０で見つかると、手続き４００は４１２にてインデックス入り口により特定される場所のブロックを解凍し、４１４にて前記所与の主キー値を有する一つ又はそれ以上のレコードに対して結果として生じるレコードを検索する。手続きは、それから４１６にて次の圧縮されたレコードファイルをチェックし、そのファイルが存在すればそのファイルについて繰り返す。圧縮されたブロックが見つからなければ（例えば、前記所与の主キー値が第１ブロック内の最小のキー値よりも小さいか、又は、最後のブロック内の最大のキー値よりも大きい場合）、手続き４００は４１６にて次の圧縮されたレコードファイルをチェックし、そのファイルが存在すればそのファイルについて繰り返す。

図４Ｂは、所与の一つのセカンダリーキー値を有する一つ又はそれ以上のレコードを検索（サーチ）するための手続き４５０についてのフローチャートを示す。手続き４５０は、４５２にて、第１の圧縮されたレコードファイルに関連付けられたスクリーニングデータ構造があるか否かを判定する。もしあれば、手続き４５０は４５４にてそのスクリーニングデータ構造を処理し、肯定的結果又は否定的結果の何れかを取得する。前記所与のセカンダリーキー値がそのスクリーニングを通過しないのであれば（否定的結果）、手続き４５０は４５６にて次の圧縮されたレコードファイルをチェックし、且つ、そのファイルが存在しているのであればそのファイル上で繰り返す。その所与のセカンダリーキー値がスクリーニングを通過するのであれば（肯定的結果）、手続き４５０は４５８にてその所与のセカンダリーキーを含むレコードに対応する主キーを調べる。前記圧縮されたレコードファイルに関連付けられたスクリーニングデータ構造がなければ、手続き４５０は４５８にてスクリーニングを実施することなく前記主キーを調べる。

見つかった複数の主キーのそれぞれに関し、手続き４５０は４６０にて前記所与の主キー値を有する一つのレコードを含むかもしれない一つのブロックに対するインデックスを検索する。４６０でのインデックスの検索後、前記所与の主キー値を含むキー値の範囲と関連付けられている圧縮されたブロックが４６２にて見つかると、手続き４５０は４６４にてインデックス入り口により特定される場所のブロックを解凍し、４６６にて前記所与の主キー値を有する一つ又はそれ以上のレコードについて結果として生じるレコードを検索する。手続きは、それから４６８にて次の圧縮されたレコードファイルをチェックし、そのファイルが存在すればそのファイルについて繰り返す。圧縮されたブロックが見つからなければ、手続き４５０は４６８にて次の圧縮されたレコードファイルをチェックし、そのファイルが存在すればそのファイルについて繰り返す。

一つの所与の「主キー又はセカンダリーキー」を有する複数のレコードが見つかると、それらは手続き４００又は４５０により、現れた順で戻される。或いは、いくつかの場合、そのレコードの最後のバージョンのみが戻される。

ファイル管理モジュール１０４は、また、レコードの記憶及びアクセスを、付加可能なルックアップファイルを用いて管理する。付加可能なルックアップファイルを用いる一つの例において、システム１００は大きな主データセット（例えば、何百テラバイトの主データを包含する）を管理する（扱う）。この主データセットは、通常、一つ又は一連の複数の圧縮されたレコードファイル（場合により一つの合成圧縮レコードファイルへと連結されるファイル）内に記憶されるであろう。しかしながら、データが、到着後直ちに（例えば、一分又はそれ以下で）可視（visible）となることが必要である場合、一つの付加可能なルックアップファイルを有する圧縮されたレコードファイルを補足することは有益である。その付加可能なルックアップファイルは、新しいデータが到着した時点と、そのデータが種々の問い合わせ処理（query processes）に利用可能となる時点と、の間の待ち時間を減じることができる。その新しいデータは、例えば、積極的にデータをそのファイルに書き込む他の処理に起因しているかもしれない。システム１００は、また、不完全であるかもしれない部分的な付加可能なルックアップファイルへのアクセスを管理する（扱う）ことができる。いくつかの場合において、一つの問い合わせ処理が一つの部分的ファイルに遭遇するとしたなら、一つのプログラムエラーが起こるであろう。このプログラムエラーを回避するため、これらのシステムの幾つかは、ファイルが問い合わせを受ける毎にそのファイルと関連付けられているインデックスをリロードするであろう。その問い合わせ毎のインデックスのリロードは、いくつかの場合において非効率であり、かなりの量のシステムリソースを消費するかもしれない。

概して、付加可能なルックアップファイルは、そのファイルの最後に追加される部分的レコードに耐性のある非圧縮のデータファイルである。付加可能なルックアップファイルは、不完全なレコードを認識することができ、且つ、問い合わせされたファイルが不完全なレコードを含んでいるときですら、問い合わせ要求を処理することができる。付加可能なルックアップファイルは、圧縮されたレコードファイルについて上述したように、インデックスファイルの形式を有さない。むしろ、付加可能なルックアップファイルは、相対的に速度の速い作業メモリ（例えば、ダイナミックランダムアクセスメモリ等の揮発性記憶媒体）内に記憶された一つのデータ構造における各レコードの場所を位置づける（マップする、map）「ダイナミックインデックス」を有する。例えば、これらのダイナミックインデックスは、ハッシュ表、二分木、ｂ−ツリー、或いは、他のタイプの結合データ構造、であり得る。図５は、付加可能なルックアップファイルが問い合わせを受ける処理例である。付加可能なルックアップファイルの操作に関連するプロセスの流れ５００は、ロード処理５０２と問い合わせ処理５０４とを含む。ファイルが５０６にてロードされた後（例えば、ファイルが問い合わせを受けるとき）、そのファイルの長さが５０８にて決定される。５０８にてそのファイルの長さが決定されると、その決定された長さは５１０にて記憶場所内、例えば、作業メモリ内、に記憶される。

そのシステムは、５１２にて、そのファイル内において最後の完全なレコードの終わりを表す位置である「終了点」を決定する。いくつかの場合において、例えば、そのファイルに書き込まれている新たなデータがない場合、その終了点はそのファイルの最後を単純に表すであろう。終了点は、新たなデータの最初のセグメントの直前である位置を表すこともある（図６を参照。）。５１２にて終了点が５１２で決定された後、５１４にて終了点はメインメモリ内等の記憶場所内に記憶される。

問い合わせ処理５０４の最中、システム１００は、５２２にて問い合わせの処理を行うべきであるか、或いは、５１８にて問い合わせされたファイルと関連付けられている結合データ構造を更新するべきであるか否かを決定する。この決定を行うために、システムは５１６にてそのファイルの現在の長さと以前に決定され且つメモリ内に記憶されたそのファイルの長さとを比較する。この決定は様々な方法により為され得る。例えば、システムは、そのファイルのメタデータ、又は、ファイルのヘッダーを検査し、或いは、改行文字があるかどうかそのファイルを検索することができる。ファイルの長さが先に記憶されたファイルの長さを超えていなければ、新たなデータはそのファイルの最後に追加されておらず、問い合わせは５２２に進む。ファイルの現在の長さが先に記憶されたファイルの長さを超えているのであれば、５１８にて、結合データ構造が更新され、その更新は先に記憶された終了点から開始する。このようにして、その結合データ構造は、リロード又はそれを完全に再構築する必要なく、更新され得る。その代わりに、メモリ内に既にロードされたデータはロードされたままに維持され、新しいデータが、先に記憶された終了点から始まるように付加される。問い合わせの処理前に、そのファイル長さ及び終了点はまた５２０にて更新される。エラーチェック等の他のステップは、このプロセスにおいて実行される。例えば、システムが、現在のファイルの長さが先に記憶されたファイルの長さよりも小さいと決定する場合、エラー警告が出され得る。

図６Ａ及び図６Ｂは、一つのファイル内の終了点（図５のステップ５１２により決定される如くの終了点）の位置の例である。図６Ａにおいて、付加可能なルックアップファイル６００は完全なレコード６０２と不完全なレコード６０４とを含む。この場合、終了点６０６は、付加可能なルックアップファイル６００内における最後の完全なレコードの終わりを表す位置であり、且つ、不完全なレコード６０４の始まりの直前である。

図６Ｂの例において、付加可能なルックアップファイル６５０は、完全なレコード６５２の全体から構成される。この場合、終了点６５４は、付加可能なルックアップファイル６５０内の最後の完全なレコードの終わりを矢張り表すが、終了点６５４はまたそのファイルの終わりをも表す。

データは付加可能ルックアップファイルに連続的に付加され得、付加可能ルックアップファイルは、よって、連続的に更新される。その結果、付加可能ルックアップファイルのサイズは次第に大きくなり、それに応じて付加可能ルックアップファイルをロードするのに必要な時間が増加する。付加可能なルックアップファイルは、他の形式の同時にロード可能なインデックスファイル（dynamically loadable index files）と組み合わせられ、それにより、付加可能なルックアップファイルがあまりに大きくなって望ましい時間内にロードできないということが回避される。

いくつかのアプリケーションにおいて、問い合わせ可能なデータ構造内にロードされる予定のデータの連続的な流れは、高い速度で到着し続けていて、到着後に直ぐにそのデータにアクセスすることが望ましいであろう。データが到着すると、そのデータは二重処理により扱われる。第一に、そのデータは複製され、付加可能なルックアップファイルに追加され（その結果、データはそのファイルシステムに直ちに可視となり、且つ、そのファイルシステムによってアクセス可能となる）、且つ、第２ファイル又は「バッファ」に同時に追加される。そのデータは、予め定義された条件が満足されるまで、その付加可能なルックアップファイル及びそのバッファの両方に蓄積し続ける。その予め定義された条件は、多数のクライテリアである。例えば、予め規定されたクライテリアは、時間の長さ、ファイルのサイズ、データの量、及び、データ内のレコードの数等であってもよい。

予め定義された条件が満足された後、前記バッファ内に蓄積したデータのブロックは、長期記憶のために圧縮されたレコードファイルに追加される。データが圧縮されたレコードファイルに追加された後、新たな付加可能なルックアップファイルが作られ且つそのルックアップファイルはデータストリームからデータを集め始める。古い付加可能なルックアップファイルは終了させられ、圧縮されたレコードファイルが総ての対応するデータを含んだ後に削除される。

データが前記バッファと前記付加可能なルックアップファイルとによって受け取られている間、前記バッファ内のデータは記憶される。データのソートはかなりの時間とシステムリソースを消費するので、データが、圧縮されたレコードファイルへとより迅速に移動させられることを可能にするために、出来るだけ早期にソートの処理を始めることが有利である。

代替として、付加可能なルックアップファイルはバッファとしても使用できる。この実施例においては、この例では、予め定義された条件が満足されるまで、データは付加可能なルックアップファイル内に蓄積される。付加可能なルックアップファイルの中身は、その後、圧縮されたレコードファイルに加えられる。それと同時に、古い付加可能なルックアップファイルは終了させられ、新たな付加可能なルックアップファイルが作られ且つそのルックアップファイルはデータストリームからデータを集め始める。ここでも、古い付加可能なルックアップファイルは、圧縮されたレコードファイルが総ての対応するデータを含んだ後に削除される。

このプロセスの各サイクルにおいて、データを圧縮されたレコードファイルに加えると同時に、付加可能なルックアップファイル内のそのデータの総てを削除することが望ましい。しかしながら、二つの更新は競合状態を引き起こすかもしれないので、古い付加可能なルックアップファイルが削除され且つ圧縮されたレコードファイルはそのデータによってまだ更新されていないというかなりの時間帯が存在するであろう。これは、データを一時的に失うという結果をもたらすかもしれない。これを防止するために、古い付加可能なルックアップファイルは、このプロセスの余分な一サイクルの間、維持されることができる。インデックス付与及び検索モジュール１０８は、複製データが、付加可能なルックアップファイル及び圧縮されたレコードファイルの両方に存在することができる条件を、検出するように構成されている。インデックス付与及び検索モジュール１０８は、問い合わせがこの条件中になされた場合、複製データをフィルタによって除去する。

代替として、ファイル管理モジュール１０４は、ステータス情報を、例えば、ステータス情報ファイル１０７内に維持し、データバッファが圧縮されたルックアップファイルに書かれたか、付加可能なルックアップファイルの中身が圧縮されたルックアップファイルに追加されたか、のいずれかの後に、一つの付加可能なルックアップファイルの引退を調整する。ステータス情報ファイル１０７は、現時点にてアクティブなレコードに関連するデータ構造を特定する。例えば、ステータス情報ファイル１０７は、総ての圧縮されたデータファイルと、現時点においてアクティブな付加可能なルックアップファイルの総てとともに前記圧縮されたデータファイルが含むブロックの数とを特定する。インデックス付与及び検索モジュール１０８は、ステータス情報ファイル内に現れない、付加可能なルックアップファイル、圧縮されたデータファイル、及び、圧縮されたデータファイル内のブロックを無視するであろう。新しい付加可能なルックアップファイルが作られるとき、ファイル管理モジュール１０４により順守されるプロトコルの一例は次のとおりである：ファイル管理モジュール１０４は新しいデータを圧縮されたデータファイルに追加し且つ新しい付加可能なルックアップファイルを作る；ファイル管理モジュール１０４はステータス情報ファイルをロックし、ステータス情報ファイルがインデックス付与及び検索モジュール１０８によってアクセスされることを妨げる；ファイル管理モジュールはステータス情報ファイルを更新し、新しいデータが圧縮されたデータファイルに追加されたこと、古い付加可能なルックアップファイルが除去されたこと、及び、新しい付加可能なルックアップファイルが生成されたこと、を反映する；ファイル管理モジュールはステータス情報ファイルのロックを解除して、ステータス情報ファイルがインデックス付与及び検索モジュール１０８により再びアクセスされることを許容する；ファイル管理モジュール１０４が古い付加可能なルックアップファイルを除去する。

インデックス付与及び検索モジュール１０８は、次の例示のプロトコルに従う：それはステータス情報ファイルをロックし、ファイル管理モジュール１０４がステータス情報ファイルを更新することを妨げ；それは、ステータス情報ファイルにおいて特定された、付加可能なルックアップファイル、及び、圧縮データファイル、に従って問い合わせを実施する；それはステータス情報ファイルのロックを解除して、再びファイル管理モジュール１０４がステータス情報ファイルを更新することを許容する。

ステータス情報ファイル１０７はディスク上に或いはメモリ内の何れかに記憶され得る。このプロトコルは、検索モジュールが、古い付加可能なルックアップファイル及び古い付加可能なルックアップファイルからのデータを組み入れる前の圧縮されたデータファイルを参照すること、或いは、新しい付加可能なルックアップファイル及び更新された圧縮されたデータファイルを参照すること、を保証する。

新しい付加可能なルックアップファイル及び古い付加可能なルックアップファイルの両方が同時に存在しているときに問い合わせがなされる場合、一つの実施形態において、システムはディレクトリー内を見て、どの付加可能なルックアップファイルが現時点においてアクティブであるかを判断する（例えば、新しい付加可能なルックアップファイルは作られてからあるディレイが経過するまでアクティブにはならないかもしれないので、新しい付加可能なルックアップファイルか古い付加可能なルックアップファイルかの何れかはアクティブであろう）。代替として、システムが問い合わせを処理するとき、システムは最初に最も新しい付加可能なルックアップファイルの中を見て、それから、古い付加可能なルックアップファイルの中を見る。問い合わせを受けたデータが依然として見つけられないのであれば、システムは圧縮されたレコードファイルの中を見る。

図７において、システム１００によって実行される手続き７００は、７０２にてファイルの長さを決定し、７０４で第１記憶場所にそのファイルの長さを記憶する。手続き７００は、７０６でそのファイル内の最後の完全なレコードの終了点を決定し、７０８でその終了点を第２記憶場所に記憶する。その手続きは、７１０で第１記憶場所に記憶されたファイルの長さを、そのファイルの現在の長さと比較し、ファイルの現在の長さが第１記憶場所内に記憶されたファイルの長さを超えていれば、７１２で前記ファイルと関連付けられているデータ構造を更新し、その更新は前記終了点にて始まる。

図８において、システム１００により実行される手続き８００は、８０２にて、データストリームからのデータを第１ファイル及びバッファに同時に加え、且つ、８０４にて、予め定義された条件が満足するとそのバッファに関連付けられているデータを圧縮されたファイルへと移動する。手続き８００は、８０６にて、第２ファイルを作り、前記バッファからのデータが前記圧縮されたファイルへと移動された後に前記データストリームからデータを受け取る。

上述したレコードの記憶及び読出しのアプローチは、システム１００の複数のモジュールを含み且つシステム１００によって実行される複数の手続きを含むのであるが、コンピュータ上で実行されるソフトウェアを用いて実現され得る。例えば、そのソフトウェアは、プログラムされた又はプログラム可能な一つまたはそれ以上のコンピュータシステム（分散型、クライアント／サーバー、又は、グリッド等の種々の技法に基づく）であって、それぞれが少なくとも一つのプロセッサ、少なくとも一つのデータ記憶システム（揮発性及び不揮発性メモリ及び／又は記憶素子を含む）、少なくとも一つの入力装置又はポート、及び、少なくとも一つの出力装置又はポートを含んでいるコンピュータシステム上で実行される一つ又はそれ以上のコンピュータプログラムにおける手続きを形成する。ソフトウェアは、より大きなプログラムの一つまたはそれ以上のモジュールを形成する。そのプログラムは例えば計算グラフの設計及び構成に関連する他のサービスを提供する。グラフのノードと要素は、コンピュータ読み取り可能な媒体内に記憶されたデータ構造として或いはデータ収納場所内に記憶されたデータモデルに従う他の組織化されたデータとして、実現され得る。

ソフトウェアは、例えばＣＤ−ＲＯＭ等であって、汎用コンピュータ或いは専用のプログラム可能なコンピュータによって読み取られうる記憶媒体上にて提供され得、或いは、ネットワークの通信媒体を通してソフトウェアが実行されるコンピュータに配信される（伝播される信号に符号化されて）。総ての機能は専用コンピュータ上で実行され得るか、或いは、例えばコプロセッサ等の専用ハードウエアを用いて実行され得る。ソフトウェアは、そのソフトウェアによって特定される計算の異なった部分が異なったコンピュータによって実行されるという分散された方法にて実行され得る。そのようなコンピュータプログラムのそれぞれは、好ましくは記憶媒体又はデバイス（例えば、固体メモリ又は媒体、又は、磁気又は光媒体）であって汎用コンピュータ又は専用のプログラム可能なコンピュータにより読み取られうる記憶媒体又はデバイス上でソートされ又は記憶媒体にダウンロードされることができ、記憶媒体又は記憶装置がコンピュータシステムによって読まれたときコンピュータを構成し且つ作動させて本明細書に記載した手続きを実行する。本発明のシステムは、コンピュータ−読み取り可能記憶媒体として実施するようにも考えられ得る。その記憶媒体はコンピュータプログラムとともに構成され、そのように構成された記憶媒体はコンピュータシステムに特別且つ予め規定した方法で本明細書に記載された機能を実行させる。

本発明の多くの実施例が開示されてきた。それにもかかわらず、本発明の精神及び範囲から離れることなく種々の変形が為され得ることが理解されるであろう。例えば、上述のステップのいくつかは順序に関して独立しているし、それ故、上述とは異なる順序で実行され得る。

先の記述は例示することを意図しており、付加された請求の範囲により規定される本発明の範囲を限定することを意図していないことが理解されるであろう。例えば、上述された多くの機能ステップは、全体の処理に実質的に影響を及ぼすことなく異なった順序にて実行され得る。他の実施例は添付の請求の範囲内である。

Claims (26)

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. 請求項１７に記載のシステムにおいて、前記ファイルは非圧縮データファイルであるシステム。

Images