(57)【特許請求の範囲】
【請求項１】
プログラム可能なコンピュータにおいて、複数の順次のデルタ・ストリーム(30、32、34)をオリジナルのデータストリーム(36)とマージして上記オリジナルのデータストリームを更新する更新データストリーム(52)を作成する方法であって、上記複数の順次デルタ・ストリームおよびオリジナルのデータストリームは、順次媒体上に記憶されており、
a)上記更新データストリームを構成するためのデータ・バイトを上記複数の順次のデルタ・ストリームから取り出す検索要求を起動するステップと、
b)上記検索要求に応じて、上記複数の順次のデルタ・ストリームのうち上記更新データストリームを構成するためのデータ・バイトを供給する最新の順次のデルタ・ストリームから順に上記複数の順次のデルタ・ストリームにわたって上記更新データストリームを構成するためのデータ・バイトを取り出すステップと、
c) 上記検索要求に応じて、上記複数の順次のデルタ・ストリームから上記更新データストリームを構成するためのデータ・バイトを取り出すことができないとき、上記オリジナル・データストリームから更新データストリームを構成するためのデータ・バイトを取り出すステップと、
d)上記検索要求に対してこれ以上の出力すべきデータがなくなるまで、上記a)からc)のステップを繰り返すことによって上記更新データストリームを完成させるステップと、
を含む更新データストリーム作成方法。
【請求項２】
プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリーム(30、32、34)をオリジナルのデータストリーム(36)とマージして上記オリジナルのデータストリームを更新する更新データストリーム(52)を作成する方法であって、上記複数の順次デルタ・ストリームおよびオリジナルのデータストリームは、順次媒体上に記憶されており、
a)上記複数の順次デルタ・ストリームに対応し、上記オリジナル・データストリームに対する最新リビジョンが最大の番号を持ち、上記オリジナル・データストリームに対する最初のリビジョンが最小の番号を持ち、その間の順次リビジョンに対応して順次番号が付せられた、複数のトランザクション・エレメント(24、26、28)からなるトランザクション連鎖(38)を構築するステップと、
b)上記更新データストリームを構成するための複数のデータ・バイトを上記トランザクション連鎖から取り出す検索要求を起動するステップと、
c)上記検索要求に応じて、上記更新データストリームを構成するためのデータ・バイトを供給する、上記トランザクション連鎖内の最大番号のトランザクション・エレメントから上記更新データストリームを構成するためのデータ・バイトを取り出すステップと、
d)上記検索要求に応じて、上記トランザクション連鎖内のトランザクション・エレメントから上記更新データストリームを構成するためのデータ・バイトを取り出すことができないとき、上記オリジナル・データストリームから更新データストリームを構成するためのデータ・バイトを取り出すステップと、
e)上記検索要求に対してこれ以上の出力すべきデータがなくなるまで、上記a)からd)のステップを繰り返すことによって上記更新データストリームを完成させるステップと、
を含む更新データストリーム作成方法。
【請求項３】
上記オリジナル・データストリームを順次媒体から直接読み取るステップを更に含む請求項２に記載の更新データストリーム作成方法。
【請求項４】
プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをオリジナルのデータストリームとマージする際に負のデルタ・ストリームを構築して上記オリジナルのデータストリームを更新する更新データストリームを作成する方法であって、上記複数の順次デルタ・ストリームおよび上記オリジナルのデータストリームは、順次媒体上に記憶されており、
a)合致デルタ・フレームおよびデータ・デルタ・フレームの一方または両方を含むデルタ・ストリームから、更新データストリームを構成するためのデータ・バイトを取り出す検索要求を起動するステップと、
b)上記デルタ・ストリームの現在時デルタ・フレームが空であれば、上記デルタ・ストリームの次のデルタ・フレームを現在時デルタ・フレームとしてロードするステップと、
c)上記デルタ・ストリームに関連するオリジナル・データストリーム位置をモニタするステップと、
d)合致フレームである次のデルタ・フレームをロードした後、実行する次のi)からv)のステップと、
i)合致フレームのソース合致位置とデルタ・ストリームのオリジナル・データストリーム位置の差として先行ストリーム遅れカウントを計算し、
ii)該先行ストリーム遅れカウントに等しいバイト数を上記オリジナル・データストリームから上記負のデルタ・ストリームへデータ・フレームの形式で転送し、
iii)上記合致フレームの反転を作成し、
iv)該反転合致フレームを上記負のデルタ・ストリームに記録し、
v)上記オリジナル・データストリーム位置を上記先行ストリーム遅れカウントに等しい数だけ増分させる、
e)上記検索要求に応じて、上記デルタ・ストリームがデータ・フレームである現在時フレームから上記更新データストリームを構成するためのデータ・バイトを供給できる場合、上記現在時フレームからの、更新データストリームを構成するためのデータ・バイトを取り出すステップと、
f)上記検索要求に応じて、上記デルタ・ストリームから上記更新データストリームを構成するためのデータ・バイトを取り出すことができないとき、上記オリジナル・データストリームから更新データストリームを構成するためのデータ・バイトを取り出すステップと、
g)上記オリジナル・データストリームによって上記更新データストリームに提供された更新データストリームを構成するためのデータ・バイトの数だけ上記オリジナル・データストリーム位置を増分させるステップと、
h)上記検索要求に対してこれ以上の出力すべきデータがなくなるまで、上記a)からg)のステップを繰り返すことによって上記更新データストリームを完成させるステップと、
を含む更新データストリーム作成方法。
【請求項５】
プログラム可能なコンピュータにおいて、順次媒体上に記憶された複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する方法であって、
a)上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを上記複数の順次デルタ・ストリームから取り出す検索要求を起動するステップと、
b)上記検索要求に応じて、上記複数の順次デルタ・ストリームのうち上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを供給する最新の順次デルタ・ストリームから上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを取り出すステップと、
c)上記検索要求に応じて、上記複数の順次デルタ・ストリームから上上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを取り出すことができないとき、合致フレームを構築して上記コンパイルされたデルタ・ストリームに転送するステップと、
d)上記検索要求に対してこれ以上の出力すべきデータがなくなるまで、上記a)からc)のステップを繰り返すことによって上記コンパイルされたデルタ・ストリームを完成させるステップと、
を含むコンパイルされたデルタ・ストリーム作成方法。
【請求項６】
プログラム可能なコンピュータにおいて、順次媒体上に記憶された複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する方法であって、
a)上記複数の順次デルタ・ストリームに対応し、上記オリジナル・データストリームに対する最新リビジョンが最大の番号を持ち、上記オリジナル・データストリームに対する最初のリビジョンが最小の番号を持ち、その間の順次リビジョンに対応して順次番号が付せられた複数のトランザクション・エレメントからなるトランザクション連鎖を構築するステップと、
b)上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを上記トランザクション連鎖から取り出す検索要求を起動するステップと、
c)上記検索要求に応じて、上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを供給する、上記トランザクション連鎖内の最大番号のトランザクション・エレメントから上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを取り出すステップと、
d)上記検索要求に応じて、上記トランザクション連鎖内のトランザクション・エレメントから上記コンパイルされたデルタ・ストリームを構成するためのデータ・フレームを取り出すことができないとき、合致フレームを構築して上記コンパイルされたデルタ・ストリームに転送するステップと、
e)上記検索要求に対してこれ以上の出力すべきデータがなくなるまで、上記a)からd)のステップを繰り返すことによって上記コンパイルされたデルタ・ストリームを完成させるステップと、
を含むコンパイルされたデルタ・ストリーム作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オリジナル・データストリームに対する変更を表すデルタ・ストリームまたは先行デルタ・ストリームに対する変更を表すデルタ・ストリームを含む複数の順次デルタ・ストリームをマージするコンピュータ装置および方法に関するものであり、具体的には、１)オリジナル・データストリームに対する複数の順次デルタ・ストリームをマージして更新データストリームを作成する、２)複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する、あるいは、３)１つまたは複数のデルタ・ストリームがオリジナル・データストリームとマージされる時または相互にマージされる時１つまたは複数の負のデルタ・ストリームを作成する、装置および方法に関するものである。本発明の方法および装置は、コンピュータ・バックアップ・プロセス、バージョン管理プログラム等と連係して使用される場合がある。
【０００２】
【従来の技術】
１９９３年３月３０日出願の米国特許出願第08/039,702号は、オリジナルおよび更新されたコンピュータ・ファイルに関する変更リストを作成する方法および装置を開示している。この方法および装置は、ＣＰＵ上のハッシュ生成機構を利用してオリジナル・ファイルに関するトークン・セットを作成する。その後、ＣＰＵ上の比較機構が、そのトークン・セットおよウィンドウ操作技術を使用して、オリジナルおよび更新されたファイル内の共通ページの位置を特定する。次に、比較機構が、共通ページ情報および更新されたファイル(あるいはオリジナル・ファイルの)残りの非共通部分を使用して、オリジナル・ファイルと更新されたファイルの間の差分を表すデルタを作成する。デルタは、別のコンピュータに伝送されオリジナル・ファイルのバックアップ・コピーと結合され、更新されたファイルのバックアップ・コピーが作成される。オリジナル・ファイルおよび一連のデルタを使用することによって、履歴ファイル情報がコスト効率よく保持される。
【０００３】
上記引用の特許出願に記載のデルタのマージを必要とするバックアップ操作は、変更増分のマージを必要とする場合に比較して大幅に能率化されている。例えば、種々のタイプが混合した１ギガバイトのファイルがその情報の０.５％毎日変更されると仮定する場合、同一の変更がそのファイルの１５％に及ぶことがある。上記引用の特許出願の方法を使用して作成される毎日のデルタ・ファイルは０.５％変更を表すために約５メガバイトのサイズでよいが、一方、毎日の増分変更ファイルはファイルの１５％に当たる変化部分を表さなければならず、１５０メガバイト以上のサイズを必要とする。毎週の全面バックアップおよび毎日の増分バックアップを仮定すれば、１年に７８ギガバイトの情報が書き込まれ、各増分変更バックアップに約３時間を要する。毎日デルタ・バックアップを使用するとすれば、年間わずか２ギガバイトが書き込まれるだけで、各バックアップ・セッションの所要時間は約５分である。
【０００４】
このような時間および記憶空間の節約は、１ギガバイトのデータベースにおける０.５％の変更の場合に一層明確となる。データベースにおいては、０.５％の変更が、データベースの１００％に及ぶことがあり、上記引用特許出願に記載のデルタ・ファイルを使用するバックアップ操作は時間、記憶空間およびコストの一層顕著な節約を生む。
【０００５】
【発明が解決しようとする課題】
上記引用の特許出願に記載の装置および方法が独特の利点を有するとはいえ、デルタ・ファイルをバックアップ・ファイルのコピーと順次マージする方法は、特に毎日数千のファイルとデルタをマージするためバックアップ・レポジトリが必要とされる場合、バックアップ・レポジトリ処理に長いＣＰＵ時間を必要とするという欠点がある。従って、バックアップ・レポジトリによって実行される動作の数を減少させる方法を提供することが本発明の主目的である。
【０００６】
デルタ・ファイルがバックアップ・レポジトリによって保存されることを上記引用特許出願が開示しているが、各デルタに対して負のデルタを作成し、バックアップ・レポジトリに負のデルタを保存することには利点がある。負のデルタを保存することによって、バックアップ・レポジトリが、その現在のバックアップ・コピーと１つまたは複数の負のデルタをマージさせることが可能となり、それによって前のバージョンのファイルを再構築することができる。従って、本発明の更に別の目的は、負のデルタの作成を可能にし、それにより先行バージョンのファイルの取り出しを可能にする方法および装置を提供することである。
【０００７】
非常に多数のデルタ・ファイルを管理するのは厄介であるので、あまりに多数になった時デルタ・ファイル(特に古いデルタ・ファイル)の数を周期的に減らすことが望ましい。しかし、単にＮ番目毎のデルタを削除しても、複数デルタ間の必要な順序関係が破壊される。従って、いくつかのデルタをマージしてコンパイルされたデルタを作成し、バックアップ・レポジトリの管理の必要性を減少させる装置および方法を提供することが本発明の更に別の目的である。上記引用の特許出願に開示されているデルタ・ファイルは、１)（例えばコンピュータ・ファイルのような)オリジナル・データストリームと(例えばコンピュータ・ファイルの改訂版コピーのような)更新されたデータストリームの間、あるいは、２)２つの連続する更新データストリームの間における合致および変更セグメントを示す情報を含む。ストリームは、データが順次の関係を持つという事実に依存する。すべてのデルタ・ファイル(変更ファイル)が順次的関係を持つわけではない。
【０００８】
アクセスの容易さのため、また、順次記憶媒体が非順次(シーク型)媒体より大幅に廉価であるため、順次ファイルを順次媒体に記憶することは望ましい。順次媒体の例は磁気テープであり、シーク型媒体の例には、フロッピーディスク、ハードディスクおよびＣＤ−ＲＯＭが含まれる。現在までのところ、上述の諸目的を達成する方法および装置は開発されていない。
【０００９】
デルタ・ファイルをマージする既存の方法の１つは、反復的作成方法である。反復的作成システムは、基本ファイルを１つまたは複数のデルタ・ファイルと連続的にマージする。複数のデルタ・ファイルは、基本ファイルと同時並行的にマージされない。反復的作成方法は、マージを実行するＣＰＵの入出力(Ｉ／Ｏ)動作を減少させない。基本ファイルは、マージすべきデルタ・ファイルの各々について一度読み書きされなければならない。このように、Ｎ個のデルタ・ファイルを基本ファイルとマージするためのＩ／Ｏ動作の数は、((Ｎ＊２)＋１)＊(基本ファイルのバイト数)に等しい。反復的作成システムは、シーク型媒体についてのみ機能し、従って順次媒体上に記憶されたデルタ・ストリームをマージするために使用されたことはない。反復的作成システムを使用して順次媒体上に記憶されたデルタ・ストリームをマージしなければならない場合は、先ずデルタ・ストリームをシーク型媒体にコピーしなければならず、そのため、ＣＰＵのＩ／Ｏ動作数が増加する。反復的作成システムを使用して負のデルタ・ファイルを作成するシステムは知られていない。
【００１０】
反復的作成方法の１つのバリエーションは反復的作成パイプライン方法である。基本ファイルが、１つのデルタ・ファイルに関連する更新プロセスに供給される。更新プロセスの出力が別の更新プロセスに供給され、次々とパイプ上に連結して最後に最終的更新ファイルが作成される。反復的作成パイプライン方式は、マルチタスキング・システムの出現によって可能にされたもので、マルチタスキング・システム上でのみ機能する。このシステムの利点はＩ／Ｏが減少することである。このシステムにおいてＮ個の変更ファイルを基本ファイルとマージするためのＩ／Ｏ動作の数は、２＊(基本ファイルのバイト数)に等しい。しかしながら、次のようないくつかの欠点がある。第１に、パイプライン方式は、パイプ・バッファがいっぱいになる度毎に文脈的プログラム切り替えが必要となる。多数の(たぶん大規模な)デルタ・ファイルとマージされる大規模基本ファイルの場合、多くの文脈的切り替えが起き、システムの処理性能が低下する。第２に、反復作成パイプライン・システムはマルチタスキング・システム環境においてのみ機能する。第３に、この方法は負のデルタ・ファイルの作成をサポートしない。最後に、この方法はもう一度デルタ・ファイルがシーク型媒体に記憶されることを要求する。
【００１１】
デルタ・ファイルをマージする最終的方法が、Foster氏らに付与の米国特許第45,278,979号に開示されている。この特許は、ポインタを使用するバージョン管理システムを開示している。このシステムにおいても、ポインタを機能させるため、ファイルはシーク型(非順次)媒体にコピーされなければならない。この特許は、バージョンの後方向比較によって前のバージョンを取り出す能力を開示している。これは、(１回パスですべて実行する)前方向マージの間に逆向き経路を作成することとは全く相違する。上記Foster氏らの特許の方法は、１)大規模な基本およびデルタ・ファイルに関する貧弱な処理性能(この方法は各々が典型的には１メガバイト以下のデータを伴う複数のバージョンのプログラム・ソース・データを記憶することを目的とする)、および２)「行」に対する変更を処理する文脈上の制限(データは文脈上の規則に従わなければならず、行を越える連続ストリームとして取り扱われない)という欠点を含む。従って、デルタ・マージ、バックアップおよびバージョン管理システムの上述のような欠点を克服することが、本発明の更にまた別の目的である。
【００１２】
【課題を解決するための手段】
上記諸目的を達成するため、本発明は、順次配列された複数のデルタ・ストリームをマージするコンピュータ装置および方法を提供する。本発明の装置および方法を使用して、１)オリジナル・データストリームに対する複数の順次デルタ・ストリームをマージして更新データストリームを作成し、２)複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成し、あるいは、３)１つまたは複数のデルタ・ストリームがオリジナル・データストリームとマージされる時または相互にマージされる時１つまたは複数の負のデルタ・ストリームを作成する装置および方法を提供する。本発明の方法および装置は、コンピュータ・バックアップ・プロセス、バージョン管理プログラム等と連係して使用されることができる。
【００１３】
要約すれば、本発明の装置および方法を使用するコンピュータは、先ず、順次配列された複数のデルタ・ストリームをオリジナルのデータストリームとマージするため、複数の順次デルタ・ストリームに対応するトランザクション・エレメントの連鎖を構築する。この連鎖において、最小の番号をつけられたトランザクション・エレメントが、オリジナルのデータストリームに対する最初のリビジョン(すなわち修正版)を表すデルタ・ストリームに対応し、その後に順次ふられた番号のトランザクション・エレメントが、オリジナルのデータストリームに対する後続のそれぞれのリビジョンに対応する。使用者プロセスが更新データストリームに伝送すべきデータ・バイトをトランザクション連鎖の範囲内で探し求める検索要求を起動する。検索要求は、先ず(オリジナルのデータストリームに対する最新リビジョンを表す)末尾トランザクション・エレメントに対して起動される。検索要求に対して、１)データ・バイトを供給できるトランザクション連鎖の中の最大番号のデルタ・ストリームによって提供されるデータ・バイトが応答されるか、または、２)トランザクション連鎖が検索要求に応じることができない場合オリジナル・データストリームによって提供されるデータ・バイトが応答される。検索要求に対してなにも応答されなくなると、更新データストリーム構築動作が終了する(更新データストリームが完成する)。
【００１４】
オプションとして、各デルタ・ストリーム毎に先行ストリーム位置が監視される。これによって、コンピュータ装置が、特定のデルタ・ストリームのソース合致位置が特定のデルタ・ストリームの先行ストリーム位置より大きい時、特定のデルタ・ストリームの１つまたは複数の先行するストリームから該特定のデルタ・ストリームに関連する負のデルタ・ストリームへデータ・フレームを転送することを可能にする。ソース合致位置は、デルタ・ストリームのあらゆる合致フレームに関するもので、特定の合致フレームがロードされる時までに、先行ストリームがどれほど消費されたかを示す。先行ストリーム部分の消費が不十分な場合、それは連続するデルタ・ストリームの間に発生したファイル削除が原因であるので、削除された情報が負のデルタ・ストリームに記録される。データ・フレームが負のデルタ・ストリームに転送された後、反転合致フレームが負のデルタ・ストリーム中に作成される。
【００１５】
本発明の方法のバリエーションの１つは、更新データ・ファイルを複数の順次配列された負のデルタ・ストリームとマージし、所望の先行データストリーム(おそらくオリジナル・データストリーム)を作成することを含む。本発明の方法の別のバリエーションは、いくつかのデルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成することを含む。
【００１６】
本発明の方法および装置の利点は、(デルタ・ストリームによって表現される)デルタ・ファイルを、順次記憶媒体に記憶されている(オリジナルのデータストリームである)ファイルとマージすることができる能力である。その他の利点には、１)ファイルの以前のバージョンを再構築することができるように負のデルタ・ストリームを作成することができる能力、２）ＣＰＵによって実行されるＩ／Ｏ動作数が２＊(基本ファイルのバイト数)に限定されるように単一パスで多数のデルタ・ストリームをマージして負のデルタ・ストリームを作成することができる能力、３)複数のデルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成し、それによってＣＰＵに課せられた管理負荷を減少させる能力、４)マルチタスクをサポートしないコンピュータ・システム環境においても効果的に動作できる能力、および５)大規模なデータストリームとデルタ・ストリームのマージを管理する能力が含まれる。
【００１７】
本明細書に記述の本発明の方法および装置が順次記憶媒体の使用に関する特定の利点を提供しているが、本発明の方法および装置はシーク型記憶媒体使用の場合もまた有効である。
【００１８】
デルタ・ストリームがファイル全体に比較して小さい(ファイル全体のサイズの約０.５％)ので、複数デルタ・ストリームの記憶に際しては、中央のレポジトリにおける記憶に加えて、ローカルのＰＣハードディスクに記憶することができる点は理解されるであろう。上述の装置をファイル・システムまたはアプリケーション・プログラムへ適応させることによって、ファイルを上書きすることに代わる形態としてデルタ・ストリームを生成することができる。このように、ユーザは、大規模なディスク記憶空間を使用せずに、ドキュメントのいくつかのバージョンをローカルに保持することが可能である。
【００１９】
発明の課題を解決する手段として、本発明は、プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをオリジナルのデータストリームとマージして更新データストリームを作成するため、上記更新データストリームに伝送すべきデータ・バイトを上記複数の順次デルタ・ストリームの範囲内から取り出す検索要求を起動するステップ、上記データ・バイトを供給できる複数の順次デルタ・ストリームの最後のデルタ・ストリームによって提供されるデータ・バイトで上記要求を充足させるステップ、上記複数の順次デルタ・ストリームが上記検索要求を充足させることができない場合、上記オリジナル・データストリームによって提供されるデータ・バイトで上記検索要求を充足させるステップ、および検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足のステップを繰り返すことによって上記更新データストリームを完成させるステップからなる方法を含む。
【００２０】
【発明の実施の形態】
図１には、複数の順次デルタ・ストリーム３０、３２、３４をオリジナルのデータストリーム３６とマージする一般的コンピュータ装置２０のブロック図が示されている。この装置には、トランザクション・エレメント２４、２６、２８の各々が複数の順次デルタ・ストリーム３０、３２、３４に対応するデルタ・ストリーム入力４２、４４、４６を持つ複数の順次トランザクション・エレメント２４、２６、２８を含むトランザクション連鎖３８、およびトランザクション連鎖３８の末尾エレメント２４に接続する使用者プロセス２２が含まれ、また、使用者プロセスに対するオリジナルのデータストリーム３６の入力４８および更新データストリーム５２の出力５０が含まれる。複数の順次デルタ・ストリーム３０、３２、３４をオリジナル・データストリーム３６とマージする方法は、図２ないし図８の流れ図に一般的に示されているように、更新データストリーム５２へ転送すべきデータ・バイトに関して複数の順次デルタ・ストリーム３０、３２、３４の範囲内での検索要求１０２を始動するステップ（ステップ１０２）、データ・バイトを供給することができる複数の順次デルタ・ストリーム３０、３２、３４内の最後のデルタ・ストリームによって提供されるデータ・バイトを上記検索要求に回答するステップ（ステップ１１０）、複数の順次デルタ・ストリーム３０、３２、３４が上記検索要求に対しデータ・バイトを回答することができない場合、オリジナル・データストリーム３６によって提供されるデータ・バイトを上記検索要求に回答するステップ（ステップ１１２）、および、検索要求に対してデータ・バイトが回答されなくなるまで上記ステップ１１０および１１２を繰り返すことによって、最終的に更新データストリームを完成させるステップ（ステップ１０６）を含む。
【００２１】
複数の順次デルタ・ストリーム３０、３２、３４をオリジナルのデータストリーム３６とマージする装置２０および方法を一般的に上述したが、以下に更にその詳細を記述する。本発明の１つの好ましい実施形態において、装置２０のトランザクション・エレメント２４、２６、２８の各々は、更に、デルタ・ストリーム読み取り機構、先行トランザクション・エレメント・インデックス、先行ストリーム位置モニタ、現在時フレーム・バッファおよび検索要求実行Ｉ／Ｏインターフェース６６、６８、７０を含む。使用者プロセス２２は、データ・ストリーム更新のためトランザクション・エレメントにおけるトランザクション連鎖３８からデータを取り出す(ステップ１０２)責任がある。使用者プロセス２２の検索要求１０２をトランザクション連鎖３８を通して伝播する際にトランザクション・エレメント２４、２６、２８の先行トランザクション・エレメント・インデックスが使用される。検索要求１０２の各々は、トランザクション連鎖３８の末尾エレメント２４(ＴＥ２)またはオリジナル・データストリーム３６の最後のリビジョン３０に対応するエレメントに対して実行される。トランザクション・エレメント２４、２６、２８の先行トランザクション・エレメント・インデックスに応じて、オリジナル・データストリーム３４の最初のリビジョンに対応するトランザクション・エレメント２８(０−エレメントすなわちＴＥ０)に到達するまで、オリジナル・データストリーム３６の初期リビジョン４０へ順次検索要求１０２が伝播される。対応するデルタ・ストリーム３０、３２、３４からトランザクション・エレメントの現在時フレーム・バッファ１７０へデルタ・フレーム(すなわち合致フレームやデータ・フレーム)を順次ロードするように、トランザクション・エレメント２４、２６、２８のデルタ・ストリーム入力４２、４４、４６は制御される(ステップ１６０)。特定のトランザクション・エレメント２４、２６、２８のデルタ・ストリーム入力４２、４４、４６を制御するステップの詳細は、図４を参照して後述する。
【００２２】
合致フレームがトランザクション・エレメント２４、２６、２８の現在時フレーム・バッファへロードされる(ステップ１７０)時、当該フレームに関するソース合致位置が、トランザクション・エレメント２４、２６、２８によって監視される先行ストリーム位置と比較される。トランザクション・エレメント２４、２６、２８の先行ストリーム位置モニタは、トランザクション・エレメント２４、２６、２８の先行ストリーム３２、３４、３６の消費されたバイト数を示す。トランザクション・エレメント２４、２６、２８の先行ストリーム３２、３４、３６は、トランザクション・エレメント２４、２６、２８の先行トランザクション・エレメント・インデックスによって識別される。ソース合致位置は、特定の合致フレームがそのトランザクション・エレメント２４、２６、２８にロードされる時までに消費されていなければならない先行ストリーム４０のバイト数を示す(合致フレーム内に含まれる)数値である。先行ストリーム位置１７２よりソース合致位置が大きい場合、ソース合致位置と先行ストリームの間の差(先行ストリーム遅れカウント)に等しい位置(ステップ１７２)に先行ストリーム３２、３４、３６のストリーム位置を進めて第２の検索要求が発せられる(ステップ１９６)。このルーチンの流れの概要は図５に示されている。
【００２３】
デルタ・ストリーム読み取り機構は、デルタ・ストリーム３０、３２、３４の(合致フレームおよび／またはデータ・フレームを含む)デルタ・フレームが、トランザクション・エレメント２４、２６、２８の現在時フレーム・バッファへロードされ次第(ステップ１２０)、それらを読み取る責任がある。そのデータ・フレームによって、使用者プロセス２２によって(検索実行Ｉ／Ｏインターフェース６６、６８、７０を経由して)始動された検索要求１０２を満たすたことができる可能性がある。合致フレームによって、検索要求１０２が先行トランザクション・エレメント２６、２８へ渡されることが可能となる(ステップ１４６)か、または、合致フレームがトランザクション連鎖３８の最後のトランザクション・エレメント２８の現在時フレーム・バッファ中にある時、合致フレームによってオリジナル・データストリーム３６からのデータで使用者プロセス２２の要求１０２に応答することできる場合もある。検索要求１０２が先行トランザクション・エレメント２６、２８へ渡される時、トランザクション・エレメント２４、２６、２８の先行トランザクション・エレメント２６、２８のインデックスを使用して、トランザクション・エレメント２６、２８のどちらに検索要求１０２を渡すかが決定される(ステップ１４６)。デルタ・フレーム読み取りルーチンによって実行されるステップの概要が図３に示されている。
【００２４】
トランザクション・エレメント２４、２６、２８の各々の中に負のデルタ・ストリーム書き込み機能６０、６２、６４を含むことは、コンピュータ装置２０の好ましい実施形態に対する重要な追加である。負のデルタ・ストリーム書き込み機構６０、６２、６４なしでは、先行ストリームを進めている間にスキップされる先行ストリーム３２、３４、３６のデータ・バイト１７２が失われる。負のストリーム書き込み機構６０、６２、６４が、先行ストリームの前進によって呼び出され、スキップされたデータ・バイト１７２が特定のデルタ・ストリーム３０、３２、３４に関連する負のデルタ・ストリーム５４、５６、５８に（データ・フレームの形式で）書き込まれる(ステップ２０４)。負のデルタ・ストリーム５４、５６、５８へデータ・フレームを書き込んだ後、新しくロードされた合致フレームの反転合致フレームが同じ負のデルタ・ストリーム５４、５６、５８へ書き込まれる(ステップ１７８)。このようにして、負のデルタ・ストリーム５４、５６、５８は、（オリジナル・データストリーム３６であろうがあるいはオリジナル・データストリームの中間リビジョンであろうが）所望の先行データストリーム２８４を取り出すため複数の負の順次デルタ・ストリーム５４、５６、５８を更新されたデルタ・ストリーム５２とマージするためトランザクション連鎖３８を構築する情報を提供する。データ・フレームおよび反転合致フレームを負のデルタ・ストリーム５４、５６、５８に転送するルーチン(ステップ２０４、１７８)の流れ図がそれぞれ図６および図７に示されている。
【００２５】
図１の装置２０はプログラム可能なコンピュータとして実施することができるであろうが、装置２０はそのような実施形態に限定されない。装置２０は、フロッピーディスク、ＣＤ−ＲＯＭ、テープ等のような物理的記憶媒体で実施することもできるであろう。上述の好ましい実施形態の処理ステップおよびルーチンを以下に詳細に記述する。
【００２６】
使用者プロセス
使用者プロセス２２が更新データストリーム５２を構築する。図２に示されるように、使用者プロセス２２は、トランザクション連鎖３８(トランザクション・エレメントの連鎖)からのデータを繰り返し要求する(ステップ１０２)。要求１０２のすべては、トランザクション連鎖３８の末尾エレメント２４(０−エレメント)に対して発せられる(ステップ１００)。末尾エレメント２４を用いて、オリジナルのデータストリーム３６、ファイル、データベース等に対する最新のリビジョンを表すデルタ・ストリーム３０が読み取られる。
【００２７】
トランザクション・エレメント２４、２６、２８は、使用者プロセス２２の要求１０２に対して２つの方法の１つで応答することができる(ステップ１４４、１３６)。現在時データ・フレーム(ＣＵＲＦＲＡＭＥＢＵＦ)からデータを戻す(ステップ１３４)か、さもなければ、オリジナル・データストリーム３６から更新されたデータストリーム５２へ転送される(ステップ１１２)べきデータ・バイトの数を表す数値を返す(ステップ１４４)ことによって、トランザクション・エレメント２４、２６、２８は要求１０２に回答する。使用者プロセス２２によって(トランザクション連鎖３８を介して)受け取られる(ステップ１０８)いずれのデータも更新データストリーム５２に転送される(ステップ１１０、１１２)。トランザクション連鎖３８が要求１０２に応じることができなくなるまで(ステップ１０４)、使用者プロセス２２はデータに対する要求１０２を出し続け、最後にデータストリームの更新が完了する(ステップ１０６)。
【００２８】
使用者プロセスの好ましい処理の流れが図２に示されている。トランザクション文脈インデックス(略してＴＣＩ)を使用して、要求１０２を出す相手先のトランザクション・エレメント２４が識別される(ステップ１００)。使用者プロセス２２に関する限り、要求１０２は常に末尾エレメント２４に対しなされる。従って、使用者プロセス２２は、トランザクション文脈インデックスをトランザクション・カウント(すなわちトランザクションＣＮＴ)より１少ない値、または、トランザクション・エレメント２４、２６、２８におけるトランザクション連鎖３８の総数に設定する。オリジナル・データストリーム３６に対する最初のリビジョンを表すデルタ・ストリーム３０に情報を与えるトランザクション・エレメント２４が０−エレメントと表記されている点に注意する必要がある。
【００２９】
ＧＯＴＣＮＴは、単一の使用者プロセス２２の要求１０２に応答して、更新データストリーム５２へ転送する(ステップ１１０、１１２)ことができるデータ・バイトの最大数を表す。データがトランザクション・エレメント２４、２６、２８によって返される場合(ステップ１３４)、ＧＯＴＣＮＴは返される(ステップ１３６)データ・バイトの全数を表す。データ・バイトは、リターン・バッファ(ＲＥＴＵＲＮＢＵＦ)を通して返される(ステップ１３４)。トランザクション連鎖３８がその現在時フレームからデータを供給することができないが、データがまだオリジナル・データストリーム３６内に残っている場合、ＧＯＴＣＮＴは、オリジナル・データストリーム３６から更新データストリーム５２へ転送されるべき(ステップ１１２)データ・バイトの数を表す。使用者プロセス２２が検索要求１０２を起動する時、ＧＯＴＣＮＴは0xFFFFFFFFに設定される。このように、使用者プロセス２２は、可能な限り多数のバイトを返すようにトランザクション連鎖３８に要求する(ステップ１３６、１４４)。
【００３０】
デルタ・フレームの読み取り
フレーム読み取りルーチンは、すべてのトランザクション・エレメント２４、２６、２８によって種々の文脈で呼び出される。例えば、使用者プロセス２２の検索要求１０２に応答して、あるいは、その先行ストリーム位置を進めようとしている別のトランザクション・エレメント２４、２６、２８の検索要求１９６に応答して、トランザクション・エレメント２４、２６、２８の現在時フレームからバイトを読み取ることができる。フレーム読み取りルーチンに関する好ましい処理の流れが図３に示されている。
【００３１】
トランザクション連鎖３８が供給することができる最大数のデータ・バイトに対する要求１０２を使用者プロセス２２が起動すると、その要求１０２は、トランザクション連鎖３８の末尾エレメント２４へ先ず渡される(ステップ１１４)。末尾エレメント２４は、デルタ・フレーム(データおよび合致フレーム)の読み取りルーチンを起動する。図３に示されるように、トランザクション・エレメント２４、２６、２８の現在時フレームによって表されたバイト１１６のすべてが使用されたなら(ステップ１１８)、新しいフレームが、トランザクション・エレメント２４、２６、２８の現在時フレーム・バッファ(ＣＵＲＦＲＡＭＥＢＵＦ)にロードされる(ステップ１２０)。フレーム・ロード・ルーチンがファイル終了(ＥＯＦ)条件を戻すなら(ステップ１２２)、０のＧＯＴＣＮＴが使用者プロセス２２へ返され(ステップ１２４)、特定の更新データストリームの構築が完了する(ステップ１０６)。さもなければ、新しいフレームのロードによって、現在時フレームの未使用バイトの数(ＵＮＵ)が新しくロードされたフレームの長さ(ＣＦＬ)にリセットされる(ステップ１２６)。
【００３２】
現在時フレームがロードされ、あるフレームのバイトが消費しつくされなかったと確認される(ステップ１１８)と、(ＧＯＴＣＮＴ要求変数を更新するために使用されるフレーム読み取りルーチンの局所変数である)ＧＥＴＣＮＴが、検索において要求された(ステップ１０２)バイトの数の最小数または、現在時フレームにおいて使用可能なバイト数(ステップ１１６、１２６)に設定される(ステップ１２８)。現在時フレームがデータ・フレームであれば(ステップ１３０)、データ・バイトのＧＥＴＣＮＴ数が、ＲＥＴＵＮＢＵＦにコピーされ(ステップ１３４)、使用者プロセス２２へ戻される(ステップ１３６)。現在時フレームがデータ・フレームでなければ(ステップ１３０)、使用者プロセス２２の要求１０２が先行トランザクション・エレメント２６へ次々と渡され(ステップ１４６)、(１)使用者プロセス２２へ返されるデータがトランザクション・エレメント２４、２６、２８の現在時フレーム内に見つけられるか、または、(２)トランザクション・エレメント２４、２６、２８のどれもデータを供給することができないと判断されオリジナル・データストリーム３６から更新データストリーム５２へデータが転送されねばならないことを示す正のＧＥＴＣＮＴが使用者プロセスへ戻されるか、いずれかの場合となるまでこの動作が継続される。使用者プロセス２２の要求１０２が先行トランザクション・エレメント２６、２８へ転送されると、そのエレメント２６、２８は、末尾エレメントによって実行されたものと同じデルタ・フレーム読み取りルーチンを実行する(ステップ１４８)。しかしながら、フレーム読み取りルーチンがトランザクション・エレメント２４、２６、２８によって始動される度毎に、そのルーチンに関連する局所変数のユニークなコピーが、特定のトランザクション・エレメント２４、２６、２８のトランザクション文脈内に記憶される。トランザクション文脈の変数には、ＴＣＩ、ＣＦＬ、ＵＮＵ、ＣＦＵおよびＰＳＰが含まれる。
【００３３】
ＴＣＩは、上述のようにトランザクション文脈インデックスとして定義される。ＣＦＵは、現在時フレームにおける使用されたバイト(文字)の数を表す。検索要求が渡されるあらゆるトランザクション・エレメントのＣＦＵは、返される(ステップ１３６、１５８)ＧＥＴＣＮＴまたはＧＯＴ数によって増分される(ステップ１３２、１５４)。
【００３４】
ＰＳＰは、トランザクション・エレメント２４、２６、２８に関連する先行ストリーム位置を表し、(詳細は後述する)先行ストリームの位置を進める際の重要な変数である。しかし、検索要求が渡されるあらゆるトランザクション・エレメントのうち、検索要求１０２に応答するトランザクション・エレメント２４、２６、２８のＰＳＰは、 使用者プロセス２２またはその他の要求元エンティティ２４、２６、２８へ返されるバイト数(ＧＥＴＣＮＴまたはＧＯＴ)によって進められる(ステップ１５６)点に注意する必要がある。
【００３５】
フレーム読み取りルーチンにおいて参照されるその他の変数は、F2_BEG、F2_ENDおよびCF.F2_BEGである。F2_BEGおよびF2_ENDは、現在時合致フレームによって参照される更新データストリームの開始および終了アドレスを表し、CF.F2_BEGは、更新データストリーム５２において次に書き込まれるべきアドレスを表す。負のデルタ・ストリーム５４、５６、５８へ書き込む(ステップ１７８)ため反転合致フレームを作成する際に、あるいは、コンパイルされたデルタ・ストリーム２９４に書き込むため合致フレームを構築する際に、これらの変数は重要な機能を果たす。
【００３６】
デルタ・フレームのロード
トランザクション・エレメント２４、２６、２８の現在時デルタ・フレームにおいて未使用のバイト(すなわちＵＮＵ)の数がゼロであると判断される時(ステップ１１８)、トランザクション・エレメント２４、２６、２８の現在時フレームとして新しいフレームがロードされなければならない(ステップ１２０)。新しいデルタ・フレームをロードするルーチンは図４の流れ図に示されている。
【００３７】
デルタ・ストリーム３０、３２、３４のデルタ・フレーム・シーケンスにおけるデルタ・フレームの各々はフレーム・ヘッダの後に続くように配置される(代替的には、ヘッダ情報はフレーム内に含まれる)。合致フレーム、データ・フレームまたはＥＯＦフレームに出会ったか否かを判断するためフレーム・ヘッダが読み取られる(ステップ１６０)。更新データトリーム５２が完了したことを使用者プロセス２２へ知らせるためのＥＯＦフレームがロードされる場合(ステップ１６２)、デルタ完了ルーチン(ステップ１６４)によって、トランザクション・エレメント２４、２６、２８のそれぞれすべてがＥＯＦフレームに出会うまでそのデルタ・ストリーム３０、３２、３４を読み続けることが保証される。このようにして、負のデルタ・ストリーム５４、５６、５８が未完成の状態で残されることはない。
【００３８】
新しくロードされたフレームがデータ・フレームである場合(ステップ１６８)、トランザクション・エレメント２４、２６、２８の現在時フレーム・バッファ(ＣＵＲＦＲＡＭＥＢＵＦ)にそのフレームのデータ・バイトがロードされる。合致フレームがロードされた場合(ステップ１６８)、合致フレームに関連するソース合致位置(すなわちＳＭＰ)が、ロードしているトランザクション・エレメント２４、２６、２８のＰＳＰと比較される(ステップ１７２)。ソース合致位置は、特定のＳＭＰに関連するフレームがロードされる時までに、直前の先行トランザクション・エレメント２６、２８に関連するストリーム３２、３４、３６のバイトが既に使用された数を示す。従って、合致フレームのＳＭＰがそのトランザクション・エレメントのＰＳＰを上回れば、使用者プロセス２２の現行検索要求１０２の処理を進める前に、その差(ＰＳＬＣすなわち先行ストリーム遅れカウント）に相当するバイト数が先行ストリーム３２、３４、３６から消費されなければならない(ステップ１７４)。先行ストリームが進められ、(オリジナル・データストリームの連続的なリビジョンの間に削除されたデータである)ＰＳＬＣに相当するデータ・バイトが、特定の負のデルタ・ストリーム５４、５６、５８へ転送された(ステップ２０４、１９４、２０２)後、新しくロードされた合致フレームを反転させ、該反転合致フレームを特定のトランザクション・エレメント２４、２６、２８の負のデルタ・ストリーム５４、５６、５８に書き込む(ステップ１７８)機能を有するルーチンが呼び出される(ステップ１７６)。合致フレーム反転は逆の合致条件(すなわち、更新データストリーム５２のデータ・バイトのどれが先行データストリーム２８４のバイトに合致するか)を示すフレームである。
【００３９】
トランザクション・エレメント２４、２６、２８の新たな現在時フレームとしてデータ・フレームまたは合致フレームがロードされた(ステップ１２０)か否かに関係なく、現在時フレームの使用済みバイト数(すなわちＣＦＵ)がゼロへリセットされ(ステップ１８０)、現在時フレームの長さ(ＣＦＬ)が新しいフレームによって参照されるバイトの数を表すように設定される(ステップ１８２)。
【００４０】
先行ストリームによって消費されるバイト数を進めるルーチン
合致フレームのロードによって正のＰＳＬＣが作成される(ステップ１７２)時は必ず、先行トランザクション・エレメント２６、２８のデルタ・ストリーム３２、３４から消費されるバイトの数がＰＳＬＣの数だけ進められなければならない。
【００４１】
図５に示されている流れ図は、トランザクション・エレメント２６、２８の先行ストリーム３２、３４を進める際のルーチンを示し、オリジナル・データストリーム３６によって消費されるバイト数を進める場合の手順は図６に示されている。正のＰＳＬＣが残り(ステップ１８６)、先行トランザクション・エレメント２６、２８が存在する(ステップ１９２)場合、使用者プロセス２２の検索要求１０２が保留されている間に第２の検索要求１９６が起動される。第２の検索要求において要求されている(ステップ１９６)データ・バイト数は、初期的にＰＳＬＣと等しく設定されるＳＫＩＰＣＮＴ変数によって定義される。第２の検索要求１９６は、図３のフレーム読み取りルーチンのインスタンスの追加実行を必要とする。データ・バイトのＳＫＩＰＣＮＴ数を求める要求に応ずる(ステップ１３６、１４４)処理を実行する際に、第２の検索要求１９６の一部として、フレーム読み取りルーチンがそれ自体を呼び出すことがある点に注意する必要がある。データは、ＲＥＴＵＲＮＢＵＦを介して当該ルーチンに返される(ステップ２００)。データが返されると(ステップ２００)、データは特定の負のデルタ・ストリーム５４、５６、５８にデータ・フレームの形式で書き込まれる(ステップ２０４)。正のＧＯＴＣＮＴが返されたがＲＥＴＵＲＮＢＵＦが空であれば、オリジナル・データ転送ルーチンが使用され(ステップ２０２)、オリジナル・データストリーム３６から特定の負のデルタ・ストリーム５４、５６、５８にデータが転送される(ステップ２１２)。第２の検索要求がデータ・バイトのＧＯＴＣＮＴ数によって部分的に充足される(ステップ２０４)場合、ＳＫＩＰＣＮＴがＧＯＴＣＮＴ数だけ減じられ(ステップ２０６)、先行ストリーム前進ルーチンが繰り返される。第２の検索要求を起動するトランザクション・エレメント２４、２６、２８の数以下であるがその検索要求を充足するトランザクション・エレメント２４、２６、２８の数を上回るトランザクション連鎖３８における位置数を持つあらゆるトランザクション・エレメント２４、２６、２８の先行ストリーム位置が、特定の負のデルタ・ストリーム５４、５６、５８へ転送される(ステップ２０４、１９４、２０２)バイト数だけ増分される(ステップ１８８、２０８)。
【００４２】
オリジナル・データストリーム転送ルーチンは先行ストリーム前進ルーチンに密接に関係する。前述のように、特定のエレメント２４、２６、２８に対して先行するトランザクション連鎖３８のエレメント２４、２６、２８がＰＳＬＣ(ＳＫＩＰＣＮＴ)数のデータ・バイトを求める要求（ステップ１７４)を満たすことができない時、オリジナル・データストリーム転送ルーチンが呼び出される。オリジナル・データストリーム転送ルーチンは、複数の順次デルタ・ストリーム３０、３２、３４をオリジナル・データストリーム３６とマージする場合に余分のように見えるかもしれないが、コンパイルされたデルタ・ストリーム２９４を作成するため複数の順次デルタ・ストリーム３０、３２、３４をマージする時、オリジナル・データストリーム３６が使用できないこともある。従って、負のデルタ・ストリーム２８８、２９０、２９２に、消失したオリジナル・データストリーム３６を参照するトークン２１０、２１２を含むことが必要である。オリジナル・データストリーム３６が存在すれば、オリジナル・データストリーム３６からのデータ・バイトを使用して、基本(すなわちオリジナルの)ストリーム参照トークンが作成される。ＰＡＳＳＣＮＴはオリジナル・データストリーム転送ルーチンの局所変数であって、その呼び出し元ルーチンのＰＳＬＣまたはＳＫＩＰＣＮＴのいずれかに等しい。
【００４３】
反転合致フレームの作成
図７は、反転合致フレームまたは合致フレーム反転を作成するルーチンの流れを示す。このルーチンは単純な反転アルゴリズム(ステップ２１８)を含み、オリジナル・データストリーム３６に対する先行リビジョンを表す先行デルタ・ストリーム３４、３６におけるセグメントに合致するデルタ・ストリーム３０、３２、３４のセグメントを示すフレームが「反転」され、負のデルタ・ストリーム５４、５６、５８において記録された(ステップ１７８)反転合致フレームが、更新データストリーム５２に対する先行リビジョンを表す負のデルタ・ストリーム５４、５６、５８におけるセグメントに合致する負のデルタ・ストリーム５４、５６、５８におけるセグメントを示す。
【００４４】
すべてのフレームを読み取ったことの確認
トランザクション・エレメント２４、２６、２８がファイル終了(ＥＯＦ)フレームに達する時までに、更新データストリーム５２は完成する(ステップ１０６)。しかし、１つまたは複数のデルタ・ストリーム３０、３２、３４の最終フレームが読み取られていないことがある。すべての負のデルタ・ストリーム５４、５６、５８が完了したことを確認するため、図８のデルタ完了ルーチンが起動される。ＥＯＦフレームは、先行トランザクション・エレメント５６、５８のデルタ・ストリーム３２、３４における最後のバイトを参照するＳＭＰを含む。先行ストリーム遅れカウント(ＰＳＬＣ)が、ＥＯＦフレームのＳＭＰとＥＯＦフレームをロードするトランザクション・エレメント２４、２６、２８のＰＳＰの間の差として計算される(ステップ２２２)。先行ストリーム４０は、デルタ・ストリーム３２、３４、３６において読み出すべきものとして残されているバイト数であるＰＳＬＣを使用して図５の先行ストリーム前進ルーチンを呼び出すことによって進められる(ステップ２２４)。先行ストリーム４０におけるＥＯＦフレームに出会うと、デルタ完了ルーチンのインスタンスが追加実行され、それによって、すべてのデルタ・ストリームのすべてのフレームが読み取られたことを保証する(ステップ２３２)波及効果が起きる。
【００４５】
実例
図９に示される例によって、複数の順次デルタ・ストリーム２４、２６、２８をオリジナル・データストリーム３６とマージする本発明の方法および装置２０が一層理解されるであろう。図９は、"THIS_IS_A_TEST_PAGE."という単純なテキスト・ファイル２３８に対する３つのリビジョン２４０、２４２、２４４を示している。３つのリビジョン２４０、２４２、２４４に対応し、米国特許出願第08/039,702号に記載されている方法を適用することによって３つのデルタ・ストリームが作成される。 データ・フレームは、追加されたデータ(すなわち調整項)を含む。合致フレームは、ソース合致位置(以前のファイル・インデックス)、および先行ファイルのセグメントと合致する更新ファイルのセグメントの開始(更新ファイルオフセット)ならびに終了バイトを含む。
【００４６】
３つのデルタ・ストリーム、オリジナルのテキスト・ファイル２３８、およびそれらをマージする上記装置２０および方法を使用して、図９の最終更新ファイル２４４を構築することができる。マージのプロセスは、トランザクション連鎖３８が構築され、すべての大域変数およびトランザクション文脈変数が初期化されることから始まる。デルタ・ストリーム０、１および２として表されている図９の３つのリビジョン２４０、２４２、２４４は、図１のトランザクション・エレメント０、１および２に対応する。
【００４７】
使用者プロセス２２は、トランザクション連鎖３８が供給することができる限りの数のデータ・バイトを要求し(ステップ１０２)、末尾トランザクション・エレメント２４(ＴＥ２)におけるその検索１０２を始動する。ＴＥ２の現在時フレームが未定義であるので、対応するデルタ・ストリーム３０の最初のフレーム２５８がＴＥ２の現在時フレームとしてロードされる(ステップ１２０)。フレーム２５８をロードする際に、反転合致フレームが、ＴＥ２の負のデルタ・ストリーム５４に記録される(ステップ１７８)。ロードされた合致フレーム２５８のソース合致位置(ＳＭＰ)がゼロであるので、先行ストリーム前進は起きない。合致フレーム２５８が１０バイトを含むので、１０バイトをＴＥ１へ転送すべき検索要求１０２が出される。ＴＥ１がその最初のフレーム２５２をロードし(ステップ１２０)、その反転合致フレームをその対応する負のデルタ・ストリーム５６に記録する(ステップ１７８)。ここでも、新しいフレームのＳＭＰはゼロであり、先行ストリーム前進は起きない。ＴＥ１の新たにロードされたフレーム２５２は５バイトの合致フレームであるので、検索要求１０２は、ＴＥ０へ渡される前に、(５データ・バイトに)再び修正される(ステップ１２８)。最後に、ＴＥ０が、１０バイトの合致フレームである最初のデルタ・フレーム２４６をロードする(ステップ１２０)。反転合致フレームがＴＥ０の負のデルタ・ストリーム５８に記録されるが(ステップ１７８)、先行ストリーム前進は起きない。ＴＥ０の現在時フレーム長(１０バイト)が要求されたデータ・バイト数より大きいので、ＴＥ０は、検索要求１０２を修正しない。しかし、ＴＥ０は供給すべきデータを持たないので、５という数をトランザクション連鎖３８を通して戻すことによって、５データ・バイトを求める修正検索要求１０２を使用者プロセス２２へ返す(ステップ１４４)。５という数が各トランザクション・エレメント２６、２４へ返される時(ステップ１４４、１５８)、各トランザクション・エレメント２６、２４の先行ストリーム位置(ＰＳＰ)が５だけ増分される(ステップ１５６)。その未充足検索要求１０２を受け取ると、使用者プロセス２２は、オリジナルのテキスト・ファイル２３８の最初の５データ・バイト(すなわちTHIS_)を更新テキスト・ファイル５２へ転送する(ステップ１１２)。
【００４８】
ここで別の検索要求１０２が使用者プロセス２２によって起動される。ＴＥ２の現在時フレームが５個の未使用バイトを持つ合致フレーム２５８であるので、検索要求１０２は修正され(ステップ１０２)一緒に渡される(ステップ１４６)。その現在時合致フレーム２５２の５バイトを費消したＴＥ１は、そのデルタ・ストリーム３２の第２のデルタ・フレーム２５４をロードさせる(ステップ１２０)。第２のフレーム２５４はデータ・フレームであり、検索要求１０２には５データ・バイト(すなわちCOULD)が与えられる(ステップ１３４、１３６)。データがトランザクション連鎖３８を通して返されると、ＴＥ２のＰＳＰが５から１０へ増加される。
【００４９】
使用者プロセス２２の第３の要求１０２の間、ＴＥ２は新しいデルタ・フレームをロードしなければならない。新しいフレーム２６０がデータ・フレームであるので、その内容全体(すなわち_B)が使用者プロセス２２へ返される(ステップ１３４)。ここで、更新テキスト・ファイル５２は"THIS_COULD_B"となる。
【００５０】
使用者プロセス２２の次の要求１０２によって、ＴＥ２はそのデルタ・ストリーム３０の第３のフレーム２６２をロードする。フレーム２６２が合致フレームであるので、フレーム２６２のＳＭＰが、ＴＥ２のＰＳＰと比較され、ＴＥ２に先行するストリーム３２が５バイト(すなわち１５−１０＝５）進められる必要があると判断される(ステップ１７２)。５バイトを求める第２の検索要求１９６がＴＥ２に先行するストリーム４０において始められる。ＴＥ１の現在時データ・フレーム２５４が第２の検索１９６で要求された５バイト全体を供給することができ、ＴＥ２のＰＳＰの必要な前進を満たすことができるので、第２の検索要求１９６は終了する(ステップ１９０)。ＴＥ１によって返された５バイト(すなわちN'T_B)がＴＥ２の負のデルタ・ストリーム５４に書き込まれる(ステップ２０４)。そのＰＳＰを１５へ進めた後、ＴＥ２はその新しくロードされた合致フレーム２６２の反転フレームをその負のデルタ・ストリーム５４に記録し(ステップ１７８)、使用者プロセスの要求バイト数を(その現在時合致フレーム長である)１５へ減少させ、検索要求１０２をＴＥ１へ渡す(ステップ１４６)。ＴＥ１は、その現在時データ・フレーム２５４から４データ・バイト(すなわちE_A_)を供給することができる。データが使用者プロセス２２へ返されると(ステップ１３６)、ＴＥ２のＰＳＰが１９へ増加される(ステップ１５６)。
【００５１】
次の使用者プロセス２２の要求１０２がＴＥ２を通して渡され(ステップ１４６)、１１へ減少される(ステップ１２８)。今やＴＥ１は新しいデルタ・フレームをロードしなければならない(１２０)。その次の使用可能フレームが合致フレーム２５６であるので、新しいフレーム２５６のＳＭＰがそのＰＳＰより大きい(１０−５＝５)と判断され、先行ストリームは５バイトだけ進められなければならない(ステップ１７４)。ＴＥ０がその合致フレーム２４６の５バイトを残しているので、オリジナルのテキスト・ファイルの次の５バイト(すなわちIS_A_)が、ＴＥ１の負のデルタ・ストリーム５６へ転送されなければならない(ステップ１９４)。トランザクション連鎖３８を通してデータを戻す際に、ＴＥ０のＰＳＰは１０に増加され、ＴＥ１のＰＳＰもまた１０へ増加される(ステップ１５６)。ＴＥ１の新しい合致フレームの反転フレーム２５６がその負のデルタ・ストリーム５６に記録される(ステップ１７８)。ＴＥ１の新しくロードされた合致フレーム２５６が１１バイトより長いので、使用者プロセス２２の検索要求１０２は未修正のままＴＥ０へ渡される(ステップ１４６)。そのデルタ・ストリーム３４の次のフレーム２４８をロードする(ステップ１２０)ようにＴＥ０は要求される。フレーム２４８は８バイト・データ・フレームであるので、検索要求１０２は修正され(ステップ１２８)、８データ・バイト(すなわちRADICAL_)がトランザクション連鎖３８を通して返される(ステップ１３６)。ＴＥ１のＰＳＰが１８に増加され(ステップ１５６)、ＴＥ２のＰＳＰが２７に増加される(ステップ１５６)。使用者プロセス２２によって作成されつつある更新テキスト・ファイル５２は、今や、"THIS_COULD_BE_A_RADICAL_"である。
【００５２】
ＴＥ２に渡される時、使用者プロセスの要求１０２は３データ・バイトを要求するように減少される(ステップ１２８)。３データ・バイトを求める要求１０２は無修正でＴＥ１を通過する(ステップ１４６)。ＴＥ０へ到達すると、ＴＥ０がそのデルタ・ストリーム３４の最後のフレームをロードする(ステップ１２０)ので、検索要求１０２は保留される。ロードされた合致フレーム２５０のＳＭＰがＴＥ０のＰＳＰに等しい(１０＝１０)ので、先行ストリーム前進は起きない。しかし、反転合致フレームがＴＥ０の負のデルタ・ストリーム５８に記録される(ステップ１７８)。３データ・バイトを求める要求１０２が充足されないまま使用者プロセス２２へ戻される(ステップ１４４)。戻され次第、ＴＥ１のＰＳＰは２１へ、ＴＥ２のＰＳＰは３０へ増加される。オリジナルのテキスト・ファイル２３８の次の３バイト(すなわちTES)が、更新テキスト・ファイル５２へ転送される(ステップ１１２)。
【００５３】
使用者プロセス２２の次の要求１０２は、ＴＥ２の新しくロードされたデータ・フレーム２６４の２バイト(すなわちT.)によって充足される(ステップ１３４、１３６)。使用者プロセス２２の最終的要求１０２は充足されないまま戻され、ＴＥ２がそのデルタ・ストリーム３０のＥＯＦに達したことを認識した時(ステップ１２２)その要求はゼロにされる。このようにして、使用者プロセスは、"THIS_COULD_BE_A_RADICAL_TEST."という更新テキスト・ファイル２４４の構築を完了する。
【００５４】
ＴＥ２がそのデルタ・ストリーム３０のＥＯＦに達した(ステップ１２２)ことを認識する時、他のトランザクション・エレメント２６、２８がそれら自身のデルタ・ストリーム３２、３４の読み取りを完了し(ステップ２２４)、それらの負のデルタ・ストリーム５６、５８の構築を完了する(ステップ２３２)という波及効果が起きる。このプロセスにおいて、オリジナルのテキスト・ファイル２３８の最後の７文字(すなわちT_PAGE.)がＴＥ２の負のデルタ・ストリーム５４にデータ・フレームとして書き込まれる。
【００５５】
上記の例が３つのデルタ・ストリーム３０、３２、３４をオリジナルのデータストリーム３６とマージさせる要求を起動させたが、上記方法および装置が単一ないし複数のデルタ・ストリームを１つのオリジナル・データストリームと容易にマージすることができる点は理解されるべきであろう。マージされるストリームの数は、所与のＣＰＵの能力によってのみ制限される。上記のマージ・プロセスを逆進させ、更新テキスト・ファイル２４４および負のデルタ・ストリーム５４、５６、５８のみを使用して図９のオリジナル・テキスト・ファイル２３８を再構築する必要がある場合、本発明のコンピュータ装置２０は、図１０のトランザクション連鎖３８を構築することができる。負のデルタ・ストリーム５４、５６、５８はトランザクション・エレメント２４、２６、２８に逆順に連結されること、および負のデルタ・ストリーム５４、５６、５８の反転ストリームは作成されない(実際には負のデルタ・ストリーム書き込みルーチンが無効な装置に連結される)ことに注意する必要がある。図２ないし図８の手順を用いて、オリジナルのテキスト・ファイル２３８を再構築することができる。同様に、負のデルタ・ストリーム２および１だけを含むトランザクション連鎖を使用して、オリジナルのテキスト・ファイル２３８に対する第１のリビジョン２４０(所望の先行データストリーム２８４)を再構築することもできる。
【００５６】
また、上述の方法および装置２０は、若干の小幅な修正を行えば、複数の順次デルタ・ストリーム３０、３２、３４をマージしてコンパイルされたデルタ・ストリーム２９４を作成するため使用することができる。データ・バイトを更新データストリーム５２へ転送するのではなく、(データまたは合致の)デルタ・フレームがコンパイルされたデルタ・ストリーム２９４へ転送される(ステップ３０６、３０８)。図１の装置２０に対してなされるべき変更には、使用者プロセス２２および更新データストリーム５２の接続をコンパイラ使用者プロセス２８６およびコンパイルされたデルタ・ストリーム２９４の接続に置き換えることが含まれる。これらの変更は、図１１の装置３３４に示されている。その上、オリジナルのデータストリーム４８の接続が削除されている。方法に関する唯一の変更は、以下に概述するように、コンパイラ使用者プロセス２８６内の動作の流れの変更である。
【００５７】
コンパイラ使用者プロセス
コンパイラ使用者プロセス２８６(図１２)は、コンパイルされたデルタ・ストリーム２９４を構築する責任があり、更新データストリーム５２を構築する使用者プロセス２２とほとんどの点で類似している。コンパイラ使用者プロセスも、また、トランザクション・エレメント連鎖３８からのデータを繰り返して要求し(ステップ２９８)、すべての要求２９８は、連鎖３８の末尾エレメント２４に対して発せられる(ステップ２９６)。トランザクション・エレメント２４、２６、２８は、使用者プロセス２２からの要求２２に応答する場合と同様の形態でコンパイラ使用者プロセス２８６に応答する。しかし、いくつかのわずかな差が存在する。データがトランザクション・エレメント２４、２６、２８によって返される(ステップ３０４)場合、それはデータ・フレームとしてコンパイルされたデルタ・ストリーム２９４にコピーされる(ステップ３０６)。データ・フレームのデータ・バイトは取り出されない。これは、コンパイルされるのは「データストリーム」５２ではなく「デルタ・ストリーム」２９４であるという事実によるためである。トランザクション連鎖３８が正のＧＯＴＣＮＴ数を返せば、そのストリームへの連結が存在しないので、データはオリジナルのデータストリーム３６から転送されない。オリジナルのデータストリーム３６からのデータ転送の代わりに、オリジナルのデータストリーム３６を参照する合致フレームが、コンパイルされたデルタ・ストリーム２９４に書き込まれる(ステップ３０８)。コンパイラ使用者プロセス２８６は、トランザクション・エレメント２４、２６、２８がそれらのデルタ・ストリーム３０、３２、３４の終端に達し、要求２９８を充足することができない(ステップ３０２)あるいは正のＧＯＴＣＮＴ数を返すことができない(ステップ３０８)状態になるまで、要求２９８を起動し続ける。
【００５８】
図１１のコンパイラ使用者プロセスに関する好ましい動作の流れが図１２に示されている。図１２の流れ図における変数は図２の使用者プロセスのものと同一である。コンパイラ使用者２８６によって呼び出されるフレーム読み取りルーチンは、前述のフレーム読み取りルーチンと同一である。しかし、前述の場合は使用されなかった合致フレーム構築ルーチンの結果３１２が、今回は、コンパイルされたデルタ・ストリーム２９４へ合致フレームを書き込む(ステップ３０８)時使用される。コンパイルされたデルタ・ストリーム２９４においては、オリジナルのデータストリーム３６からコンパイルされたデルタ・ストリーム２９４へデータを転送する代わりに、合致フレームが構築される(ステップ１４０)。コンパイルされたデルタ・ストリーム２９４において合致フレームを構築する(ステップ３１０)ルーチンを以下に記述する。
【００５９】
合致フレームの構築
コンパイラ使用者プロセス２８６の要求２９８がトランザクション連鎖３８に渡されるが、トランザクション・エレメント２４、２６、２８のいずれもコンパイラ使用者プロセスへデータを返すことができない場合、コンパイルされたデルタ・ストリーム２９４が使用者プロセス２２にオリジナルのデータストリーム３６からデータを取り出すべき時点を指示することができるように合致フレームが構築されなければならない(ステップ３１０)。
【００６０】
合致フレーム構築ルーチンに関する動作の流れが図１３に示されている。図３のフレーム読み取りルーチンによって示されているように、合致フレーム構築ルーチンは、トランザクション連鎖３８の終わりにあるトランザクション・エレメント２８であるＴＥ０によって常に呼び出される。合致フレーム構築ルーチンは、それを呼び出すトランザクション・エレメント２８のトランザクション文脈変数と末尾エレメント２４(図１１のＴＥ２)のトランザクション文脈変数の組み合わせを活用する。図１３に特有の変数定義は次の通りである。
SERVCNT: 構築された合致フレームによって表現される文字の数。
CF.F2_BEG: (図１１のＴＥ２である)末尾トランザクション・エレメント２８に関する現在時デルタ・フレームの開始アドレス。
【００６１】
実例
複数の順次デルタ・ストリーム３０、３２、３４をマージしてコンパイルされたデルタ・ストリーム２９４を作成する方法および装置３３４に対する一層の理解が、図１４の例から得られるであろう。例は、図９の単純なテキスト・ファイル２３８に対する３つのリビジョン２４０、２４２、２４４に基づいている。米国特許出願第08/039,702号に記載の方法の適用によって作成された３つのデルタ・ストリーム３０、３２、３４が図１４に再掲されている。３つのデルタ・ストリーム３０、３２、３４およびそれらをマージする上述の装置３３４および方法を使用して、図１４のコンパイルされたデルタ・ストリーム２９４を構築することができる。このマージ・プロセスもまた、トランザクション連鎖３８の構築およびすべての大域および文脈変数の初期設定から始まる。デルタ・ストリーム０、１、２は、図１１のトランザクション・エレメント０、１、２に対応する。
【００６２】
コンパイラ使用者プロセス２８６は、トランザクション連鎖３８が供給することができる限りの数のデータ・バイトを要求し(ステップ２９８)、末尾トランザクション・エレメントＴＥ２における検索２９８を起動させる(ステップ２９６)。デルタ・ストリーム３０、３２、３４をオリジナル・データストリーム３６とマージさせる場合と同様に、コンパイラ使用者プロセス２８６の最初の要求２９８によって、連鎖３８における各トランザクション・エレメント２４、２６、２８がその最初のデルタ・フレーム２４６、２５２、２５８をロードし、反転合致フレーム２６６、２７０、２７６をその対応する負のデルタ・ストリーム２８８、２９０、２９２に書き込む(ステップ１７８)。(５データ・バイトを求める要求２９８に修正された(ステップ１２８))検索要求２９８がＴＥ０に到着し充足されない場合、オリジナル・データストリーム３６を参照する合致フレーム３１８が構築され(ステップ１４０)、５データ・バイトを求めるように修正された検索要求２９８が、トランザクション連鎖３８を経由してコンパイラ使用者プロセス２８６へ戻される。数５が各トランザクション・エレメント２４、２６、２８へ戻されると、各トランザクション・エレメント２４、２６、２８の先行ストリーム位置(ＰＳＰ)が５だけ増加させられる(ステップ１５６)。その未充足検索要求２９８を受け取り次第、コンパイラ使用者プロセス２８６は構築された合致フレームをコンパイルされたデルタ・ストリーム２９４に記録する(ステップ３０８)。
【００６３】
別の検索要求２９８がコンパイラ使用者プロセス２８６によって起動される。ＴＥ２の現在時フレームが５未使用バイトを持つ合致フレーム２５８であるので、検索要求２９８は修正され(ステップ１２８)、一緒に渡される(ステップ１４６)。その現在時合致フレームの５バイトを費消したＴＥ１は、そのデルタ・ストリーム３２の第２のデルタ・フレーム２５４をロードする。第２のフレーム２５４はデータ・フレームであり、検索要求２９８は、５バイトのデータ(COULD)３２０で充足される(ステップ１３４、１３６)。データ・バイトの数がトランザクション連鎖３８を通して戻されると、ＴＥ２のＰＳＰは５から１０へ増やされる(ステップ１５６)。
【００６４】
コンパイラ使用者プロセス２８６の第３の要求２９８の間に、ＴＥ２は新しいデルタ・フレームをロードしなければならない。新しいフレーム２６０がデータ・フレームであるので、その内容全体(すなわちB_)がコンパイラ使用者プロセス２８６へ返され(ステップ１３４)、コンパイルされたデルタ・ストリーム２９４へデータ・フレーム３２２として書き込まれる(ステップ３０６)。
【００６５】
コンパイラ使用者プロセス２９８の次の要求２９８によって、ＴＥ２が、そのデルタ・ストリーム３０の第３のフレーム２６２をロードする。フレーム２６２が合致フレームであるので、フレームのＳＭＰがＴＥ２のＰＳＰと比較され、ＴＥ２に先行するストリーム３２が５バイト(１５−１０＝５）だけ進められる必要があると判断される(ステップ１７２)。５バイトを求める第２の検索要求１９６がＴＥ２に先行するストリーム３２、３４に出される。ＴＥ１の現在時データ・フレーム２５４が第２の検索１９６において要求された５バイト全体を供給し、ＴＥ２のＰＳＰの必要な前進を充足することができるので、第２の検索要求２９６は終了される。ＴＥ１によって返された５バイト(すなわちN'T_B)が、データ・フレーム２７８の形式で負のＴＥ２ののデルタ・ストリーム２８８に書き込まれる(ステップ２０４)。そのＰＳＰを１５へ進めた後、ＴＥ２は、その負のデルタ・ストリーム２８８にその新しくロードされた合致フレームの反転フレーム２６２を記録し(ステップ１７８)、コンパイラ使用者プロセスが要求したバイト数を(その現在時合致フレーム２６２の長さである)１５へ減少させ(ステップ１２８)、その要求２９８をＴＥ１へ渡す(ステップ１４６)。ＴＥ１は、その現在時データ・フレーム２５４から４バイトのデータ(すなわちE_A_)を供給することができる。データ３２４がコンパイラ使用者プロセス２８６へ返される時、ＴＥ２のＰＳＰが１９へ増加させられる(ステップ１５６)。
【００６６】
コンパイラ使用者プロセス２８６の次の要求２９８は、ＴＥ２を経由して渡され、１１に減じられる(ステップ１２８)。ここで、ＴＥ１は新しいデルタ・フレームをロードしなければならない(ステップ１２０)。次に使用可能なフレームは合致フレーム２５６であるので、新しいフレーム２５６のＳＭＰがそのＰＳＰより大きい(１０−５＝５)と判断され(ステップ１７２)、先行ストリーム３４が５バイトだけ進められなければならない。ＴＥ０が、その合致フレーム２４６に５バイト残し、データを供給することができないので、オリジナルのデータストリーム３６の参照トークンが、ＴＥ１の負のデルタ・ストリーム２９０に記録されなければならない(ステップ２１２)。オリジナル・データストリーム３６をコンパイルされたデルタ・ストリーム２９４とマージすると、ＴＥ１の負のデルタ・ストリーム２９０に記録された参照トークンに、オリジナル・データストリーム３６からの適切なデータが記入される(ステップ２１４)。トランザクション連鎖３８を通して参照トークンのバイト数を返す際に、ＴＥ０のＰＳＰが１０へ、ＴＥ１のＰＳＰが１０へ増加させられる(ステップ１５６)。新しい反転合致フレーム２５６がその負のデルタ・ストリーム２９０に記録される(ステップ１７８)。ＴＥ１の新しくロードされた合致フレーム２５６が１１バイトより長いので、コンパイラ使用者プロセス２８６の検索要求２９８は、無修正でＴＥ０へ渡される(ステップ１４６)。ＴＥ０は、そのデルタ・ストリーム３４の次のフレーム２４８をロード(ステップ１２０)させなければならない。フレーム２４８は、８バイトのデータ・フレームである。検索要求２９８は修正され(ステップ１２８)、８データ・バイト(すなわちRADICAL_)がトランザクション連鎖３８を経由して返される。ＴＥ１のＰＳＰが１８へ増加させられ、ＴＥ２のＰＳＰが２７へ増加させられる(ステップ１５６)。返された８データ・バイトが、コンパイルされたデルタ・ストリーム２９４にデータ・フレーム３２６として記録される(ステップ３０６)。
【００６７】
更に３バイトを求めるように減少された要求２９８がＴＥ２を経由して渡される(ステップ１４６)。３データ・バイトを求める要求２９８がＴＥ１を通して無修正で渡される(ステップ１４６)。ＴＥ０に到達すると、ＴＥ０がそのデルタ・ストリーム３４の最後のフレーム２５０をロードする間、検索要求２９８は保留される。ロードされた合致フレーム２５０のＳＭＰがＴＥ０のＰＳＰに等しい(１０＝１０)ので、先行ストリーム前進は起きない。ロードされた合致フレーム反転２５０が、負のデルタ・ストリーム２９２に記録される(ステップ１７８)。ＴＥ０は、オリジナル・データストリーム３６を参照する合致フレームを構築する(ステップ１４０)。３データ・バイトを求める要求２９８は、未充足のままコンパイラ使用者プロセス２８６へ戻される。それが戻されると、ＴＥ１のＰＳＰが２１へ、ＴＥ２のＰＳＰが３０へ増加される(ステップ１５６)。構築された合致フレーム３２８が、コンパイルされたデルタ・ストリーム２９４に記録される(ステップ３０８)。
【００６８】
コンパイラ使用者プロセス２８６の次の要求２９８は、ＴＥ２の新しくロードされたデータ・フレーム２６４の２バイト(すなわちT.)を表しているデータ・フレーム３３０で充足される。コンパイラ使用者プロセス２８６の最終要求が未充足のまま返され、ＴＥ２がそのデルタ・ストリーム３０の終端に到達したことを認識した(ステップ１２２)時要求はゼロにされる。このようにして、コンパイラ使用者プロセス２８６はそのコンパイルされたデルタ・ストリーム２９４の構築を完了する(ステップ３０２)。
【００６９】
デルタ・ストリーム３０、３２、３４をオリジナル・データストリーム３６とマージさせる場合と同様に、ＴＥ２がそのデルタ・ストリーム３０の終端に到達したことを認識する(ステップ１２２)時、波及効果として、他のトランザクション・エレメント２６、２８がそれら自身のデルタ・ストリーム３２、３４の読み取りを終了して(ステップ２２４)、それらの負のデルタ・ストリーム２９０、２９２の構築を完了する。このプロセスの間、オリジナル・データストリーム３６の最後の７バイトを参照するもう１つの参照トークン３１６が、ＴＥ２の負のデルタ・ストリーム２８８に記録される(ステップ２０４)。
【００７０】
上述のデルタ・ストリーム３０、３２、３４が合致または追加のデータ・バイトを参照するデルタ・フレームを含んでいたが、合致または追加のデータ行を参照するデルタ・ストリームに関連した本発明の方法および装置２０、３３２、３３４を当業者が容易に使用することができるであろう。従って、この場合合致フレームの特性をバイト・アドレスでなく行アドレスに対応するものと言い換えることができるであろう。
【００７１】
以上、複数の順次デルタ・ストリーム３０、３２、３４をマージする方法および装置２０、３３２、３３４を記述した。デルタ・ストリーム３０、３２、３４が一連のオーバーラップしない合致フレームおよびデータ・フレームから構成されているので、すべてのストリーム３０、３２、３４が順次型記憶媒体に記憶される場合本システムは特有の成果を生む。順次記憶媒体だけを含む環境で動作するデルタ・マージ・システムは知られていない。
【００７２】
本発明の方法および装置２０、３３２、３３４の好ましい実施形態を以上詳細に記述したが、本発明の概念が上記実施形態に限定されることなく種々の形態で実施することが可能である点は理解されるべきである。
【００７３】
本発明には、例として次のような実施様態が含まれる。
（１）プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをオリジナルのデータストリームとマージして更新データストリームを作成する方法であって、上記更新データストリームに伝送すべきデータ・バイトを上記複数の順次デルタ・ストリームの範囲内から取り出す検索要求を起動するステップと、上記データ・バイトを供給できる複数の順次デルタ・ストリームの最後のデルタ・ストリームによって提供されるデータ・バイトで上記要求を充足させるステップと、上記複数の順次デルタ・ストリームが上記検索要求を充足させることができない場合、上記オリジナル・データストリームによって提供されるデータ・バイトで上記検索要求を充足させるステップと、検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足のステップを繰り返すことによって上記更新データストリームを完成させるステップと、を含む更新データストリーム作成方法。
（２）プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをオリジナルのデータストリームとマージして更新データストリームを作成する方法であって、各々が上記複数の順次デルタ・ストリームに対応し、上記オリジナル・データストリームに対する最新リビジョンが最大の番号を持ち、上記オリジナル・データストリームに対する最初のリビジョンが最小の番号を持ち、その間の順次リビジョンに対応して順次番号が付せられた複数のトランザクション・エレメントからなる連鎖を構築するステップと、上記更新データストリームに伝送すべきデータ・バイトを上記トランザクション連鎖の範囲内から取り出す検索要求を起動するステップと、上記データ・バイトを供給できる上記トランザクション連鎖内の最大番号を持つトランザクション・エレメントによって提供されるデータ・バイトで上記要求を充足するステップと、上記トランザクション連鎖内のトランザクション・エレメントが上記検索要求を充足させることができない場合、上記オリジナル・データストリームによって提供されるデータ・バイトで上記検索要求を充足させるステップと、検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足のステップを繰り返すことによって上記更新データストリームを完成させるステップと、を含む更新データストリーム作成方法。
（３）オリジナル・データストリームを順次記憶媒体から直接読み取るステップを更に含む上記（２）に記載の更新データストリーム作成方法。
【００７４】
（４）プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをオリジナルのデータストリームとマージする際に負のデルタ・ストリームを構築する方法であって、合致デルタ・フレームおよび／またはデータ・デルタ・フレームを含むデルタ・ストリームの範囲内から、更新データストリームに伝送すべきデータ・バイトを取り出す検索要求を起動するステップと、上記デルタ・ストリームの現在時デルタ・フレームが空であれば、上記デルタ・ストリームの次のデルタ・フレームを現在時デルタ・フレームとしてロードするステップと、上記デルタ・ストリームに関連するオリジナル・データストリーム位置をモニタするステップと、合致フレームである次のデルタ・フレームをロードした後、合致フレームのソース合致位置とデルタ・ストリームのオリジナル・データストリーム位置の間の差として先行ストリーム遅れカウントを計算し、該先行ストリーム遅れカウントに等しいバイト数を上記オリジナル・データストリームから上記負のデルタ・ストリームへデータ・フレームの形式で転送し、上記合致フレームの反転を作成し、該反転合致フレームを上記負のデルタ・ストリームに記録し、上記オリジナル・データストリーム位置を上記先行ストリーム遅れカウントに等しい数だけ増分させるステップと、上記デルタ・ストリームがデータ・フレームである現在時フレームから上記データ・バイトを供給できる場合、上記現在時フレームから提供されるデータ・バイトで上記検索要求を充足させるステップと、上記デルタ・ストリームが上記検索要求を充足させることができない場合、上記オリジナル・データストリームによって提供されるデータ・バイトで上記検索要求を充足させるステップと、上記オリジナル・データストリームによって上記更新データストリームに提供されたデータ・バイトの数だけ上記オリジナル・データストリーム位置を増分させるステップと、検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足のステップを繰り返すことによって上記更新データストリームを完成させるステップと、を含む負のデルタ・ストリーム構築方法。
【００７５】
（５）プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する方法であって、上記コンパイルされたデータストリームに伝送すべきデータ・フレームを上記複数の順次デルタ・ストリームの範囲内から取り出す検索要求を起動するステップと、データ・フレームを供給できる複数の順次デルタ・ストリームの最後のデルタ・ストリームによって提供されるデータ・フレームで上記要求を充足させるステップと、上記複数の順次デルタ・ストリームが上記検索要求を充足させることができない場合、合致フレームを構築して上記コンパイルされたデルタ・ストリームに転送するステップと、検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足、および合致フレーム構築と転送の諸ステップを繰り返すことによって上記コンパイルされたデルタ・ストリームを完成させるステップと、を含むコンパイルされたデルタ・ストリーム作成方法。
（６）プログラム可能なコンピュータにおいて、複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する方法であって、各々が上記複数の順次デルタ・ストリームに対応し、上記オリジナル・データストリームに対する最新リビジョンが最大の番号を持ち、上記オリジナル・データストリームに対する最初のリビジョンが最小の番号を持ち、その間の順次リビジョンに対応して順次番号が付せられた複数のトランザクション・エレメントからなる連鎖を構築するステップと、上記コンパイルされたデルタ・ストリームに伝送すべきデータ・フレームを上記トランザクション連鎖の範囲内から取り出す検索要求を起動するステップと、データ・フレームを供給できる上記トランザクション連鎖内の最大番号を持つトランザクション・エレメントによって提供されるデータ・フレームで上記要求を充足させるステップと、上記トランザクション連鎖内のトランザクション・エレメントが上記検索要求を充足させることができない場合、合致フレームを構築して上記コンパイルされたデルタ・ストリームに転送するステップと、検索要求に対する充足ができなくなるまで、上記検索要求の起動と充足、および合致フレーム構築と転送の諸ステップを繰り返すことによって上記コンパイルされたデルタ・ストリームを完成させるステップと、を含むコンパイルされたデルタ・ストリーム作成方法。
【００７６】
（７）複数の順次デルタ・ストリームをオリジナルのデータストリームと１回のパスでマージして更新データストリームを作成するようにプログラムされたコンピュータであって、上記複数の順次デルタ・ストリームの１つに対応するデルタ・ストリーム入力を各々が持つ複数の順次トランザクション・エレメントからなるトランザクション連鎖と、上記トランザクション連鎖の末尾エレメントに接続し、上記オリジナル・データストリームを受け取る入力部および上記更新データストリームへの出力を行う出力部を有する使用者プロセスと、を備えたコンピュータ。
（８）複数の順次デルタ・ストリームをオリジナルのデータストリームと１回のパスでマージしてコンパイルされたデルタ・ストリームを作成するようにプログラムされたコンピュータであって、上記複数の順次デルタ・ストリームの１つに対応するデルタ・ストリーム入力を各々が持つ複数の順次トランザクション・エレメントからなるトランザクション連鎖と、上記トランザクション連鎖の末尾エレメントに接続し、上記コンパイルされたデルタ・ストリームへの出力を行う出力部を有するコンパイラ使用者プロセスと、を備えたコンピュータ。
【００７７】
（９）複数の順次デルタ・ストリームをオリジナルのデータストリームと１回のパスでマージして更新データストリームを作成するコンピュータを制御するようにプログラムされた物理的記憶媒体であって、上記複数の順次デルタ・ストリームの１つに対応するデルタ・ストリーム入力を各々が持つ複数の順次トランザクション・エレメントからなるトランザクション連鎖を作成する手段と、上記オリジナル・データストリームを受け取る入力部および上記更新データストリームへの出力を行う出力部を有する使用者プロセスと、上記使用者プロセスを上記トランザクション連鎖の末尾エレメントへ接続させる手段と、を備えた物理的記憶媒体。
（１０）複数の順次デルタ・ストリームをオリジナルのデータストリームと１回のパスでマージしてコンパイルされたデルタ・ストリームを作成するコンピュータを制御するようにプログラムされた物理的記憶媒体であって、上記複数の順次デルタ・ストリームの１つに対応するデルタ・ストリーム入力を各々が持つ複数の順次トランザクション・エレメントからなるトランザクション連鎖を作成する手段と、上記コンパイルされたデルタ・ストリームへの出力を行う出力部を有するコンパイラ使用者プロセスと、上記コンパイラ使用者プロセスを上記トランザクション連鎖の末尾エレメントへ接続させる手段と、を備えた物理的記憶媒体。
【００７８】
【発明の効果】
本発明の方法および装置によって、(デルタ・ストリームによって表現される)デルタ・ファイルを、順次記憶媒体に記憶されている(オリジナルのデータストリームである)ファイルとマージすることが可能にされ、更に、１)ファイルの以前のバージョンが再構築されるように負のデルタ・ストリームを作成することができ、２）ＣＰＵによって実行されるＩ／Ｏ動作数が２＊(基本ファイルのバイト数)に限定されるように単一パスで多数のデルタ・ストリームをマージして負のデルタ・ストリームを作成することができ、３)複数のデルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成し、それによってＣＰＵに課せられた管理負荷を減少させることができ、４)マルチタスクをサポートしないコンピュータ・システム環境においても効果的に作動させることができ、５)大規模なデータストリームとデルタ・ストリームのマージを管理することが可能となる。従って、本発明の方法および装置によって、ユーザは、大規模なディスク記憶空間を使用することなく、ドキュメントのいくつかのバージョンをローカルの順次記憶媒体に保持することが可能となる。
【図面の簡単な説明】
【図１】複数の順次デルタ・ストリームをオリジナルのデータストリームとマージしてデータストリーム・リビジョンを作成する装置のブロック図である。
【図２】図１の装置を使用するプロセスの動作の流れ図である。
【図３】図１のトランザクション・エレメントが対応するデルタ・ストリームを読み取る際の動作の流れ図である。
【図４】図１のトランザクション・エレメントが対応するデルタ・ストリームのデルタ・フレームをロードする際の動作の流れ図である。
【図５】図１のトランザクション・エレメントが先行デルタ・ストリームのストリーム位置を前進させる際の動作の流れ図である。
【図６】図１のトランザクション・エレメントがオリジナル・データストリームから負のデルタ・ストリームへデータを転送する際の動作の流れ図である。
【図７】図１のトランザクション・エレメントが負のデルタ・ストリームに関して反転合致フレームを作成する際の動作の流れ図である。
【図８】図１のトランザクション・エレメントがその対応するデルタ・ストリームの最終フレームをロードする際の動作の流れ図である。
【図９】図１の装置によって生成することができるものの例として、１つの単純な文に対する３つのリビジョン、上記リビジョンを表す３つのデルタ・ストリームおよび３つの負のデルタ・ストリームを示す図である。
【図１０】複数の負の順次デルタ・ストリームを更新されたデータストリームとマージして所望の先行データストリームを再構築する装置のブロック図である。
【図１１】複数の順次デルタ・ストリームをマージしてコンパイルされたデルタ・ストリームを作成する装置のブロック図である。
【図１２】図１１の装置がコンパイルされたデルタ・ストリームを作成するプロセスの動作の流れ図である。
【図１３】コンパイルされたデルタ・ストリームに合致フレームを作成する際の図１１のトランザクション・エレメントの動作の流れ図である。
【図１４】図９の３つのデルタ・ストリームのマージの間に図１１の装置によって作成されるコンパイルされたデルタ・ストリームおよび３つの負のデルタ・ストリームを示す図である。
【符号の説明】
２０、３３２、３３４    コンピュータ装置
２２    使用者プロセス
２４、２６、２８    トランザクション・エレメント
３０、３２、３４    デルタ・ストリーム
３６    オリジナル・データストリーム
３８    トランザクション連鎖
４０、２８４    先行リビジョン
４２、４４、４６    デルタストリーム読み取り機構
４８    入力
５０    出力
５２    更新データストリーム
５４、５６、５８、２８８、２９０、２９２    負のデルタ・ストリーム
６０、６２、６４    負のデルタ・ストリーム出力機構
６６、６８、７０    検索要求実行Ｉ／Ｏインターフェース
２４６、２５２、２５８    合致フレーム
２４８、２５４、２６０    データ・フレーム
２８６    コンパイラ使用者プロセス
２９４    コンパイルされたデルタ・ストリーム
【図１】
0004165912.tif 000002
【図２】
0004165912.tif 000003
【図３】
0004165912.tif 000004
【図４】
0004165912.tif 000005
【図５】
0004165912.tif 000006
【図６】
0004165912.tif 000007
【図７】
0004165912.tif 000008
【図８】
0004165912.tif 000009
【図９】
0004165912.tif 000010
【図１０】
0004165912.tif 000011
【図１１】
0004165912.tif 000012
【図１２】
0004165912.tif 000013
【図１３】
0004165912.tif 000014
【図１４】
0004165912.tif 000015