(57)【要約】      （修正有）【課題】データベースの法科学分析の分野において、ログ先行書き込み（ＷＡＬ）を用いてデータベースの前の状態にロールバックを行う。【解決手段】装置４０１は、メモリ４０３及びプロセッサ４０２を備える。プロセッサは、ＷＡＬ１０２に記録されたフレームの集合において、対応する特定のページの特定の改訂されたコンテンツを表す特定のフレームを選択する。フレームの集合において、特定のフレームおよびそれにゼロ以上時系列で先行するフレームを含む、フレームの第一の部分集合を識別する。データベースのページの集合から、ページの第一の部分集合を抽出する。フレームの第一の部分集合の対応するページから、ページの第二の部分集合を抽出する。ページの第一の部分集合のコンテンツおよびページの第二の部分集合の改訂されたコンテンツに基づいて、特定のページの改訂されたコンテンツを含む前の状態へのデータベース１０１のロールバックを行う。【選択図】図４
2016224921.tif 000002
【特許請求の範囲】
【請求項１】
データベース（１０１）はページの第一の集合（Ｄ＝｛１，...，Ｎ｝，Ｎ≧１，１１０）を備え、
前記データベースは、ページの第二の集合（Ｄ´＝｛Ｐ´１，...｝，１３０）の改訂されたコンテンツを表すフレームの集合（Ｓ＝｛Ｆ１，...｝，１２０）が記録されたログ先行書き込み（１０２）ＷＡＬと関連し、各フレーム（Ｆｊ，ｊ≧１）は、対応するページ（Ｐ´ｊ∈［１，Ｌ］，Ｌ≧Ｎ）の改訂されたコンテンツを表し、
前記データベースはさらに、少なくとも一つのぺージの改訂されたコンテンツが、少なくとも一つのチェックポイントの集合（Ｃ＝｛ｃ１，...｝）で前記ＷＡＬから前記データベースに転送されたことを示すチェックポイント情報と関連しており、各チェックポイント（ｃｌ，ｌ≧１）は時点に対応し、前記フレームの集合の各フレームは、前記少なくとも一つのチェックポイントの一つに対応し、
前記ＷＡＬは、前記フレームを時系列順にする情報をさらに備えた、前記データベースの前の状態へデータベースロールバックするためのコンピュータ実施方法（３００）であって、
前記フレームの集合において、対応する特定のページ（ＰＭ）の特定の改訂されたコンテンツを表す特定のフレーム（ＦＭ）を選択する工程（Ｓ３０１）であって、前記特定のフレームは、前記少なくとも一つのチェックポイントの集合（Ｃ）において、ゼロ以上のチェックポイントに時系列で先行するチェックポイントに対応する工程と、
前記フレームの集合において、前記特定のフレームおよびそれに時系列でゼロ以上先行するフレームを含む、フレームの第一の部分集合（Ｓｆ⊆Ｓ）を識別する工程（Ｓ３０２）と、
前記ページの第一の集合から、ページの第一の部分集合（Ｄ１⊆Ｄ）を抽出する工程（Ｓ３０３）と、
前記フレームの第一の部分集合（Ｓｆ）の前記対応するページから、ページの第二の部分集合（Ｄ´ｆ⊆Ｄ´）を抽出する工程（Ｓ３０４）と、
前記ページの第一の部分集合（Ｄ１）の前記コンテンツおよび前記ページの第二の部分集合（Ｄ´ｆ）の前記改訂されたコンテンツに基づいて、前記特定のページ（ＰＭ）の前記特定の改訂されたコンテンツを含む前の状態への前記データベースのロールバックを行う工程（Ｓ３０５）と、を備えた方法において、
前記特定のフレームが、前記少なくとも一つのチェックポイントの集合（Ｃ）において一つより多いチェックポイントに時系列で先行するチェックポイントに対応することと、
前記方法はさらに、
前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の一部でない少なくとも一つのページ（数式２）を含む（ＰＢ∈Ｄ）かどうかを決定する工程と、
【数２】
2016224921.tif 000004
前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の一部でない少なくとも一つのページ（数式３）を含む（ＰＢ∈Ｄ）ことを決定すると、前記前の状態は真の前の状態でないことを示す工程と、
【数３】
2016224921.tif 000005
を備えることと、を特徴とする、方法。
【請求項２】
前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の部分集合であること（Ｄ⊆Ｄ´ｆ）を決定すると、前記前の状態は真の前の状態であることを示す工程をさらに備える、請求項１に記載の方法。
【請求項３】
前記データベースは、ＳＱＬｉｔｅデータベースもしくはその派生のものである、請求項１または２に記載の方法。
【請求項４】
前記チェックポイント情報は、前記ＷＡＬ、共有メモリファイルもしくは両者の組み合わせにおいて見つかる、請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
前記フレームを時系列順にする前記情報は、フレームが前記ＷＡＬに書き込まれる順、ソルト値、計数指標、もしくはそれらの組み合わせを備える、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
処理能力を有する装置によって実行された際、請求項１乃至５のいずれか一項に記載の方法を実行するようになされた命令を含むコンピュータ可読記憶媒体を備えるコンピュータプログラム製品。
【請求項７】
データベース（１０１）は、ページの第二の集合（１３０）の改訂されたコンテンツを表すフレームの集合（１２０）が記録されたログ先行書き込み（１０２）ＷＡＬと関連し、各フレームは、対応するページの改訂されたコンテンツを表し、
前記データベースはさらに、少なくとも一つのぺージの改訂されたコンテンツが、少なくとも一つのチェックポイントの集合で前記ＷＡＬから前記データベースに転送されたことを示すチェックポイント情報と関連しており、各チェックポイントは時点に対応し、前記フレームの集合の各フレームは、前記少なくとも一つのチェックポイントの一つに対応し、
前記ＷＡＬは、前記フレームを時系列順にする情報をさらに備えた、ページの第一の集合（１１０）を備える前記データベース（１０１）の前の状態へのデータベースロールバックを行うよう構成された装置（４０１）であって、
前記装置は、前記データベースおよびそれと関連した前記ＷＡＬおよびチェックポイント情報にアクセスするようになされ、
前記装置は、
メモリ（４０３）と、
プロセッサ（４０２）であって、
要求により、前記フレームの集合において、対応する特定のページの特定の改訂されたコンテンツを表す特定のフレームを選択するよう構成され、前記特定のフレームは、前記少なくとも一つのチェックポイントの集合において一つより多いチェックポイントに時系列で先行するチェックポイントに対応し、
前記フレームの集合において、前記特定のフレームおよびそれにゼロ以上時系列で先行するフレームを含む、フレームの第一の部分集合を識別するよう構成され、
前記ページの第一の集合から、ページの第一の部分集合を抽出するよう構成され、
前記フレームの第一の部分集合の前記対応するページから、ページの第二の部分集合を抽出するよう構成され、
前記ページの第一の部分集合の前記コンテンツおよび前記ページの第二の部分集合の前記改訂されたコンテンツに基づいて、前記特定のページの前記特定の改訂されたコンテンツを含む前の状態への前記データベースのロールバックを行うよう構成された、プロセッサと、を備え、
前記プロセッサはさらに、
前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の一部でない少なくとも一つのページ（数式４）を含む（ＰＢ∈Ｄ）かどうかを決定するよう構成され、
【数４】
2016224921.tif 000006
前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の一部でない少なくとも一つのページ（数式５）を含む（ＰＢ∈Ｄ）ことを決定すると、前記前の状態は真の前の状態でないことを示すよう構成されたこと、
【数５】
2016224921.tif 000007
を特徴とする、装置。
【請求項８】
前記プロセッサはさらに、前記ページの第一の集合（Ｄ）が、前記ページの第二の部分集合の部分集合であること（Ｄ⊆Ｄ´ｆ）を決定すると、前記前の状態は真の前の状態であることを示すよう構成された、請求項７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示される発明は、データベースの法科学分析の分野に関し、特に、ログ先行書き込みを用いたデータベースの前の状態へのデータベースロールバックを行うための方法および装置に関する。
【背景技術】
【０００２】
通常、データベース回復を行う必要は、停電もしくはシステムクラッシュの後等、データベースシステムが故障した後に生じる。データベースに格納されたデータの完全性を保持するために、データベースシステムは、故障より先に存在していた最新の安定した状態にデータベースを戻さなければならない。例えば、銀行の二つの口座間での資金移動の途中にシステムクラッシュが起こった場合は、回復の正当な方法は、データベースを資金移動が始まる直前の状態にリセットし、その後移動を再びやり直すことである。そうでなければ、銀行は、例えばクラッシュの前に一方の口座にお金が届いていなかったにも関わらず、お金が他方の口座から引き出されなかったことを保証できないことがありうる。
【０００３】
上記に加えて、データベース回復を行う必要は、他の理由でも生じうる。そのような理由の一つは、自主的に削除もしくは修正されたであろうデータを回復する必要が時々重要になる、法科学分析上の理由である。データを含むファイルが、例えばハードドライブから削除もしくはハードドライブ上で修正された際、動作システムは通常、例えばハードドライブ上の特定のファイルの場所が格納された、そのファイルシステムメタデータを更新するのみである。ファイルが削除された場合、メタデータは更新されるが、ファイルの実際のデータはそのまま（ハードドライブに書き込まれたまま）残される。このように、ファイルシステムメタデータが更新されても、もしくは欠落しても、法科学分析は、ファイルカービング等の方法を用いて、削除されたもしくは修正されたファイルの元のデータの場所を特定して読み取ろうと試みることができる。例えばパターンサーチ等の、データカービングの多くの方法は、複雑であることが多く、複雑なモデルおよびヒューリスティックスの両方に依存する。散乱（または断片）データの異なる可能な順列の数が大きいことが多いという問題に加えて、これらの方法はまた、結果が必ずしも正しいと保証されないという弊害もありうる。データカービング方法は、いくつかの異なるファイルからいくつかの断片を継ぎ合わせて、単一のファイルと思われるものにすることに終わってしまうことがあり、したがって、誤った結果（フォールス・ポジティブ）を生みうる。フォールスポジティブの数が大きくなりすぎると、法科学分析の仕事が難しくなり、結果の信用性が早く低下しうる。
【０００４】
データベースにおける意図的に削除されたまたは修正されたデータを回復するための、より信頼できる方法は、多くのデータベースシステムに用いられることが多いロギング機能を使用することでありうる。データベースを前の状態に戻す（すなわちデータベースロールバックを行う）ことが出来るように、データベースシステムは、所謂ログ先行書き込み（ＷＡＬ）を用いて、データベース上で行われるアクション（すなわちデータベースへの変更）を追跡しうる。アクションがデータベース上で起こりそうな際は、ＷＡＬを用いたデータベースシステムは、データベースを直接更新しない。その代わり、データベースシステムは、アクションの結果を判定して、データベースに為されたであろう変更を、代わりにログに記録する。アクションが行われる間にシステム障害が起こった際、データベースは既に安定した状態にあり、データベースシステムは、容易にＷＡＬを確認して、システムが故障する前にアクションがどれ程進んだかを確かめ、そこからどのように処理するかを決定しうる。ＷＡＬが大きくなりすぎないために、ＷＡＬに記録された変更は、定期的（各アクションがうまく完了した後もしくは、希望であればそれよりももっと低頻度で等）もしくは手動でトリガーされた際のいずれかに、データべースに送り返すことができる。そのような動作は、チェックポイント動作として知られ、通常は、新たな変更が、チェックポイントに、ＷＡＬの始めから再び記録されるようリセットされたＷＡＬが続く。
【０００５】
システム障害からデータベースを回復するためにＷＡＬを用いる方法は、ＵＳ８，６８３，２６２に開示されている。それでは、ＷＡＬは、計算量を減らすために不適切なアクション（例えば、他の、続いて起こるアクションによって後に無効にされるアクション）が無視されるよう、まずフィルターされる。フィルターされたＷＡＬを用いて、データベースは、フィルターされたＷＡＬの残りのアクションに応答することで、回復状態から通常動作状態へと遷移される。開示された方法の主な焦点は故障の後にデータベースを回復することであるため、法科学分析には、この方法がほとんどもしくは全く役に立たない状況が起こりうる。
【０００６】
上記に照らして、ＷＡＬを用いてデータベースの前の状態へのデータベースロールバックを行うための、改良された、よりフレキシブルで、より信頼でき、法科学分析により適切な方法が求められる。
【発明の概要】
【０００７】
本発明の目的は、したがって、上述の要件を少なくとも部分的に満たすことである。本発明の、この、および他の目的は、独立クレームに定義される発明によって少なくとも部分的に満たされるが、好適な実施形態は、従属クレームに記される。本発明は、ログ先行書き込みは、前のデータベース状態についての情報を抽出するための法科学分析を可能にする情報を含んでおり、前の状態の時間は、ＷＡＬのチェックポイントのいずれかに対応し、ある状況において抽出された前の状態は、真の前の状態であると保証されうる（よって、フォールスポジティブを得るリスクを排除する）という見識に基づく。
【０００８】
本発明の第一の態様では、データベースの前の状態へのデータベースロールバックのコンピュータ実施方法が提供される。データベースはページの第一の集合を含み、データベースは、ページの第二の集合の改訂されたコンテンツを表すフレームの集合が記録されたログ先行書き込み（ＷＡＬ）と関連する。本明細書で用いられるように、データベース“ページ”は、データベースのコンテンツを格納する際データベースシステムによって使用されるデータの単位を表す。データベースに格納されたデータのサイズが単一のページのデータのサイズを超える場合は、データベースデータは、好ましくは全てのページが固定のサイズを有する複数のページに配布もしくは格納される。情報が追加、更新、もしくは削除される際等、データベースの変更がなされた際は、データベースシステムは、影響されたページのみをＷＡＬに格納することを選択しうる。ＷＡＬでは、更新もしくは改訂されたページのコンテンツが“フレーム”に被包される。フレームは、ページの更新されたコンテンツ自体とともに、例えば更新されたのはデータベースのどのページか、および更新がいつ起こったかについての情報等、ログを読み取る際に有用でありうる他の特性を含みうる。ＷＡＬでは、フレームの集合の各フレームはしたがって、対応するページの改訂されたコンテンツを示し、ＷＡＬはさらに、ＷＡＬの読み手がどの順でフレームが記録されたかを把握しうるよう、フレームが時系列順に分類されるようにする情報を含む。
【０００９】
データベースはさらに、少なくとも一つのページの改訂されたコンテンツが、少なくとも一つのチェックポイントの集合で、ＷＡＬからデータベースに転送されたことを示すチェックポイント情報と関連しうる：各チェックポイントは時点に対応しており、フレームの集合の各フレームは、該チェックポイントの一つに対応する。本明細書で用いられるように、“チェックポイント”は、例えば所定の値よりも大きくなったＷＡＬへのレスポンスとして、もしくは例えばある時間間隔の経過へのレスポンスとして、データベースシステム自体によって開始することができる。チェックポイントはまた、ユーザがあるコマンドを与えることによって、またはコンピュータプログラムによって、またはデータにアクセスする同様のものによって、開始することができる。通常、チェックポイントは、ＷＡＬからデータベースに、ＷＡＬのフレーム内で見つかったページの（時間的に）最近改訂されたコンテンツを転送することによってデータベースを更新することと、その後、スペースを節約するためにＷＡＬを後続の更新によって上書きできるよう、ＷＡＬの“リセット”を行うこととを含む。チェックポイントはまた、そのようなＷＡＬの後続のリセットを行わずに、ページのいくつかの改訂されたコンテンツのみを転送することを含みうる。後者の例は、データベースのユーザが例えばＷＡＬのフレームの一つ以上をロックしている状況を含みうる。そのような状況では、いくつかのフレームのみがすぐにデータベースに転送され、他のフレームは、必要であれば後で転送されうる。データベースが作成されたばかりの場合、もしくはチェックポイント動作がまだ起こっていない場合は、データベースの作成がチェックポイントとしてカウントされうる。ページの最近の改訂のみがチェックポイント動作中にデータベースに転送されることを確実にするために、ＷＡＬの各フレームは通常、あるチェックポイントに対応し、また、あるフレームがどのチェックポイントに対応するかについての情報は、通常フレーム自体に含まれる。通常、最新のチェックポイントに対応するフレームのみが、新たなチェックポイント動作中に転送されると見なされる。
【００１０】
第一の態様では、本方法は、ＷＡＬに記録されたフレームの集合において特定のフレームを選択するステップを備えうる。特定のフレームは、対応する特定のページの改訂されたコンテンツを表し、チェックポイント情報に示される少なくとも一つのチェックポイントの集合においてゼロ以上のチェックポイントに時系列で先行するチェックポイントに対応する。特定のフレームがゼロチェックポイントに先行する場合は、特定のフレームは最新のチェックポイント動作の後にＷＡＬに記録されており、特定のページの改訂されたコンテンツは、まだデータベースに転送されていない。特定のフレームが一つ以上のチェックポイントに先行する場合は、フレームは最新のチェックポイントの前にＷＡＬに記録されており、特定のページの改訂されたコンテンツは、前のチェックポイント動作中に既にデータベースに転送済みでありうる。
【００１１】
本方法はさらに、第一の部分集合が、特定のフレームおよびそれに時系列でゼロ以上先行するフレームを含むよう、フレームの集合においてフレームの第一の部分集合を識別するステップを備えうる。本方法が、（特定のフレームが記録された）ある特定の時間でデータベースが（部分的に）どのようになっていたかを復旧しようとする際は、特定の時間よりも先に起こったことについてのナリッジが必要となる。これは、特定のフレームおよび、より早い時間にＷＡＬに記録されたフレームのみがフレームの第一の部分集合に含まれることに反映される。特定のフレームが最新のチェックポイントに時系列で後続する場合は、フレームの第一の部分集合は、好ましくは、特定のフレームに先行するフレームの集合におけるフレームの対応するページをできるだけ多く含むよう識別される。これは、特定のフレームが最新のチェックポイントに先行する場合にもあてはまるが、好ましくは、第一の部分集合が、同じチェックポイントのみに対応するフレームを含むという条件が加えられる。これは、図２に関連してさらに説明される。
【００１２】
本方法はまた、ページの第一の集合からページの第一の部分集合を抽出するステップを備えうる。このページの部分集合は、例えば特定の時間、およびチェックポイント情報に示される最新のチェックポイントにどのように関係するかに依って、ページの第一の集合で見つかったページの全てまたはいくつかを含みうる、もしくはどれも含まないかのいずれかになる。例えば、特定のページの改訂されたコンテンツが、（データベースで見つかった）ページの第一の集合における対応するページのコンテンツよりも古い場合は、特定のページの改訂されたコンテンツを含む前の状態へのロールバックは、ページの第一の集合における特定の対応するページが、抽出されたページの第一の部分集合に含まれていることを必要としなくてよい。
【００１３】
本方法は、ページの第二の部分集合を、フレームの第一の部分集合の対応するページから抽出するステップを備え、本方法はさらに、特定のページの特定の改訂されたコンテンツを含む前の状態へのデータベースのロールバックを行うステップを備えうる。ロールバックは、ページの第一の部分集合のコンテンツおよびページの第二の部分集合の改訂されたコンテンツに基づく。
【００１４】
フレームおよびページの各部分集合を適切に選択すること、各フレーム（およびページのコンテンツ）がログに記録された時間を考慮すること、およびこれらの時間をデータベースが最後に更新された時（つまり、チェックポイント動作が最後に行われた時）と比較することによって、データベースの前の状態が、ロールバック中に作成されうる。これはまた、図２に関連してさらに説明される。
【００１５】
本明細書で用いられるように、フレームの集合は、同じページの多くの改訂されたコンテンツを含みうる。例として、ＷＡＬが、第一のページの改訂されたコンテンツを表す３２のフレームを含む場合、それらの３２のフレームは、尚同じ第一のページを表すとされる。
【００１６】
一つの例示の実施形態では、特定のフレームは、少なくとも一つのチェックポイントの集合において一つのチェックポイントに時系列で先行するチェックポイントに対応しうる。そのようなフレームは、最新のチェックポイントの前であるが、最新のチェックポイントの直前のチェックポイントの後に記録されている。特定のフレームと同じチェックポイントに対応および特定のフレームに時系列で後続し、特定のページと同じ対応するページの改訂されたコンテンツを表すフレームがＷＡＬに存在すれば、特定のページのコンテンツは、データベースで現在見つかる対応するページのコンテンツよりも古い。最新のチェックポイントに先行する情報を抽出できることは、最新のチェックポイントに先行するアクションを含め、行われたアクションのデータベース上での延長したタイムラインが想定されうるという点で、有利である。
【００１７】
一つの例示の実施形態では、本方法は、フレームの集合において、特定のフレームに時系列でゼロ以上後続するフレームを含むフレームの第二の部分集合を識別し、フレームの第二の部分集合は、ページの第三の部分集合に対応するステップをさらに備えうる。本方法は、ページの第三の部分集合が、ページの第二の部分集合の一部でない少なくとも一つのページを含むことを決定し、前の状態が真の前の状態でないことを示すステップを備えうる。法科学的な観点から、そのような実施形態は、前の情報が少なくとも部分的に抽出されうるという点で、および法科学分析者が、抽出された状態がデータベースの前の状態に部分的にのみ一致しうることに気づかされうるという点で有利である。他の例示の実施形態では、本方法は、ページの第三の部分集合が、ページの第二の部分集合の部分集合であることを決定し、前の状態が真の前の状態であることを示すステップを備えうる。法科学分析者は、抽出された情報がデータベースの前の状態と一致することに気づかされることで利益を得うる。
【００１８】
一つの例示の実施形態では、特定のフレームは、少なくとも一つのチェックポイントの集合において、一つより多いチェックポイントに時系列で先行するチェックポイントに対応しうる。そのようなフレームは、最新のチェックポイントおよび最新のチェックポイントの直前のチェックポイントの両方の前に、ＷＡＬに記録された。そのような特定のフレームが選択されると、数チェックポイント早くにデータベースに為された変更についての情報が抽出され、したがってデータベースがどれほど修正されたかについてのより長いタイムラインが構築されうるので、法科学の観点から有益である。
【００１９】
さらなる例示の実施形態では、本方法は、ページの第一の集合が、ページの第二の部分集合の一部でない少なくとも一つのページを含むことを決定し、前の状態が真の前の状態でないことを示すステップをさらに備えうる。真の前のデータベース状態が作成されていなくても、少なくともいくつかのデータの検索は有益でありうるし、該データが真の前の状態でないとマークされれば尚有益でありうる。他の例示の実施形態では、本方法は、ページの第一の集合がページの第二の部分集合の部分集合であることを決定し、前の状態が真の前の状態であることを示すステップを備えうる。
【００２０】
本明細書において“真の前の状態”とは、（再）作成された状態が、特定のフレームがＷＡＬに記録された特定の時間のデータベースの状態と一致すること、および前の特定の時間にデータベースから抽出された情報が、本発明の第一の態様の方法を用いて抽出された情報と一致したであろうことを意味する。これは、特定のページのコンテンツおよびデータベースの全ての他のページのコンテンツがの両方が、特定の時間におけるそれらと等しいことを含む。
【００２１】
一つの例示の実施形態では、データベースは、ＳＱＬｉｔｅデータベースもしくはその派生のものでありうる。ＳＱＬｉｔｅは、例えば携帯電話もしくはタブレットコンピュータにおけるアプリケーションのためのデータベースとして用いられることが多い。結果として、本発明は、そのような装置の法科学分析に用いることができる。
【００２２】
一つの例示の実施形態では、チェックポイント情報は、ＷＡＬ、共有メモリファイルもしくは両者の組み合わせにおいて見つかりうる。
【００２３】
一つの例示の実施形態では、フレームを時系列順にする情報は、フレームがＷＡＬに書き込まれる順、ソルト値、計数指標、もしくはそれらの組み合わせを備えうる。
【００２４】
本発明の第二の態様においては、コンピュータプログラム製品が提供される。コンピュータプログラム製品は、処理能力を有する装置によって実行された際、本発明の第一の態様による方法を実行するようになされた命令を含むコンピュータ可読記憶媒体を備える。
【００２５】
本発明の第三の態様においては、データベースの前の状態へのデータベースロールバック行うよう構成された装置が提供される。データベースは、ページの第一の集合を備え、かつデータベースは、ページの第二の集合の改訂されたコンテンツを表すフレームの集合が記録され各フレームが対応するページの改訂されたコンテンツを表す、ＷＡＬと関連する。データベースはさらに、少なくとも一つのぺージの改訂されたコンテンツが、少なくとも一つのチェックポイントの集合でＷＡＬからデータベースに転送されたことを示すチェックポイント情報と関連しており、各チェックポイントは時点に対応し、フレームの集合の各フレームは、該少なくとも一つのチェックポイントの一つに対応する。ＷＡＬは、フレームを時系列順にする情報をさらに備え、装置は、データベースおよびそれと関連するＷＡＬおよびチェックポイント情報にアクセスするようになされる。そのようなアクセスは、ネットワーク、バスもしくは任意の他の適切な通信を介して提供されうる。装置は、メモリおよびプロセッサを備え、メモリは、一時的または永久的に、ＷＡＬおよびチェックポイント情報の少なくとも一部を格納するのに用いられうる。プロセッサはさらに、特定のフレームが対応する特定のページの特定の改訂されたコンテンツを表し、かつ特定のフレームが、少なくとも一つのチェックポイントの集合においてゼロ以上のチェックポイントに時系列で先行するチェックポイントに対応するフレームの集合において、要求により特定のフレームを選択するよう構成されうる。プロセッサはまた、フレームの集合において、特定のフレームおよびそれに時系列でゼロ以上先行するフレームを含むフレームの第一の部分集合を識別するよう構成されうる。プロセッサは、ページの第一の集合からページの第一の部分集合を抽出するよう構成され、プロセッサはまた、フレームの第一の部分集合の対応するページからページの第二の部分集合を、抽出しうる。プロセッサは、ページの第一の部分集合のコンテンツおよびページの第二の部分集合の改訂されたコンテンツに基づいて、特定のページの特定の改訂されたコンテンツを含む前の状態へのデータベースのロールバックを行うよう構成されうる。
【００２６】
第二および第三の態様は、第一の態様に準じて具現することができ、第一の態様の定義で述べられた利点は、第二および第三の態様にも等しく適用可能である。尚、本発明は、相互に異なるクレームに記載されていても、特徴の全ての組み合わせに関する。
【図面の簡単な説明】
【００２７】
本発明は、付属の図面を参照して、より十分に、ここで説明される。
【図１ａ】ページの集合を備えるデータベースの線図。
【図１ｂ】データベースに関連したログ先行書き込み（ＷＡＬ）およびチェックポイント情報の線図。
【図２】例示的なデータベース、ＷＡＬおよびチェックポイント情報の線図。
【図３】例示の実施形態による、データベースの前の状態へのデータベースロールバックを行う方法のフローチャート。
【図４】例示の実施形態による、データベースの前の状態へのデータベースロールバックを行うための装置のブロック図。  別段に明記しない限り、図面は、例示の実施形態を図示するのに必要な要素のみを示し、他の要素は、明確性のために、省略または単に示唆されうる。
【発明を実施するための形態】
【００２８】
データベース１０１の線図が、図１ａに示される。データベースの情報は、ページ１１０ａ−１１０ｎの集合Ｄ＝｛１，２，３，...，Ｎ｝として格納され、Ｎ≧１は、現在集合にあるページの数に対応した整数である。例えば、より多くの情報がデータベース１０１に追加されると、必要とされるページ１１０の数は増えうる。同様に、情報がデータベース１０１から取り除かれると、もしくは“真空”コマンドが発行されると、必要とされるページ１１０の数は減りうる。概して、データベース１０１のページ１１０の数は力学量であり、どの情報がどのページで見つけられるかを追跡するのは、例えばデータシステム次第である。
【００２９】
データベース１０１で行われたアクションを留保するために、ログ先行書き込み（ＷＡＬ）を使用したデータベースシステムは、新たなアクションが行われた際、データベースを直接更新しない。その代わりに、アクションの結果がＷＡＬにログされ、そのようなＷＡＬ１０２の線図が図１ｂに示される。アクションがデータベース１０１で行われた際、データベースシステムは、そのアクションによって影響を受ける、データベース１０１のページ１１０のいずれかを決定する。ページが影響を受けると、データベースシステムは、そのページの改訂されたコンテンツをフレームに格納し、そのフレームをＷＡＬに記録する。図１ｂに示されるＷＡＬ１０２は、ページ１３０の集合Ｄ´＝｛Ｐ´１，...｝の改訂されたコンテンツを表す、そのような記録されたフレーム１２０の集合Ｓ＝｛Ｆ１，...｝を備え、各フレームＦｊ（ｊ≧１）１２０ｊは、対応するページＰ´ｊ（Ｐ´ｊ∈〔１，Ｌ〕およびＬ≧Ｎ）１３０ｊの改訂されたコンテンツを表す。
【００３０】
データベース１０１のあるページで見つけられた情報へのクエリが為されると、データベースシステムは、現在のデータベース１０１で見つけられたページのコンテンツを読み取る代わりに、ＷＡＬ１０２をチェックして、あるページのより最近の（改訂された）バージョンがそこで見つかるか確かめうる。見つかった場合は、データベースシステムは、あるページのこの改訂されたバージョンを代わりに使用しうる。ＷＡＬ１０２があるページのより最近のバージョンを含まない場合は、データベース１０１自体で見つかったページが代わりに使用される。そうすることで、実際のデータベース自体は更新されていなくても、クエリの結果は、データベースの最新の状態を表す。データベース１０１の最新の更新を引き起こしたアクションが留保されるべきであれば、データベースシステムは、ＷＡＬ１０２で見つかったページの最新（改訂された）バージョンを無視してもよく、その代わりに、ＷＡＬ１０２で見つかった同じページの別のバージョンもしくはデータベース１０１自体のページのいずれかを使用しうる。
【００３１】
さらに多くのアクションがデータベース上で行われた場合、ＷＡＬ１０２のサイズは、さらに多くのフレーム（対応するページの改訂されたコンテンツを表す）がＷＡＬ１０２に記録されるにつれて、大きくなる。ＷＡＬ１０２が大きくなりすぎないために、“チェックポイント”動作と称される動作が行われうる。チェックポイント動作の間、ＷＡＬ１０２で見つかったページの改訂されたコンテンツは、データベースに転送され、引き起こしたアクションは永久のものとされうる。チェックポイント動作の間に、ページのより最近の（改訂された）バージョンがＷＡＬ１０２で見つかった場合は、そのページの改訂されたコンテンツが、現在データベースで見つかった同じページのコンテンツに取って替わる。チェックポイント動作が完了すると、ＷＡＬ１０２は、新たなフレームがＷＡＬ１０２の最初に加えられうるよう“リセット”され、必要であれば、チェックポイント動作が起こる前に記録されたフレームを上書きしうる。データベース用語では、ＷＡＬ１０２に記録されたフレームは、トランザクション中に行われたアクションに対応するので、ＷＡＬ１０２のフレームは、同じトランザクションに属するアクションがコミットされる“コミット”動作に対応するとしてマークされうる。ＷＡＬ１０２は、複数のトランザクションに対応するフレームを含みうるかつ含むことが多い。
【００３２】
データベースシステムが、例えば最新のチェックポイント動作の後に記録されたフレームがどれかを知るために、データベースは、少なくとも一つのページの改訂されたコンテンツが、ＷＡＬ１０２からデータベース１０１に、各チェックポイントｃｋ（ｋ≧１）が時点に対応するチェックポイントの集合Ｃ＝｛ｃ１，...，｝で転送されたことを示すチェックポイント情報と関連しうる。各フレームを、集合Ｃの対応するチェックポイントと関連させる（すなわち、各フレームＦｊはチェックポイントｄｊと関連し、ｄｊ∈Ｃである）ことで、どのチェックポイントの後に、もしくはどの組のチェックポイントの間に、あるフレームが記録されたか、および、どのくらい最近、対応するページの改訂されたコンテンツが、例えば現在データベース１０１にある同じページのコンテンツと比較されたかを、例えばデータベースシステムが把握することが可能になりうる。各チェックポイントは、対応する一意のＩＤを与えられ、一意のＩＤは、チェックポイント動作と次のチェックポイント動作との時間間隔中にＷＡＬ１０２に記録されたフレームに示されうる。新たなチェックポイント動作が行われると、一意のＩＤは変更され、したがって各フレームは、ある時間間隔に接続されうる。同じ間隔に接続されたフレームは、それらがＷＡＬに記録された順序を考慮することで、個々に時系列順に並びうる。時系列順を追跡する別の方法は、全てのチェックポイントに、チェックポイント動作が行われた時間に対応する時間スタンプを与えること、および全てのフレームに、フレームがＷＡＬ１０２に記録された時間に対応する時間スタンプを与えることを含みうる。時間スタンプを比較することによって、時系列順が確立されうる。
【００３３】
発明者は、ＷＡＬ１０２がリセットされていたとしても、最新のチェックポイント動作よりも先のチェックポイント動作の後に記録されたフレームはまだＷＡＬ１０２に残っていること、およびデータベースの前の状態についての情報は、よって抽出されうることを理解している。
【００３４】
データベースの前の状態へのデータベースロールバックのコンピュータ実施方法がどのように実行されうるかを図示するために、以下の例が考察されうる（図２を参照）。合計Ｎ＝４ページを有するデータベースは、最近以下の動作を通った：
１）チェックポイントｃ３で、チェックポイント動作が完了し、データベースが更新され、ＷＡＬがリセットされた。
【００３５】
２）ページ１、２、１、３、３、４、１、４、３、３、２、４、１、２、３および１が（所定の時系列順に）更新され、対応するページの改訂されたコンテンツがＷＡＬに記録された。
【００３６】
３）チェックポイントｃ２で、時間的にｃ３に続いて、別のチェックポイント動作が完了し、データベースが更新され、ＷＡＬがリセットされた。
【００３７】
４）ページ４、１、２、１、２、１、１、３、３、１、および２が（所定の時系列順に）更新され、対応するページの改訂されたコンテンツがＷＡＬに記録された。
【００３８】
５）チェックポイントｃ１で、時間的にｃ２に続いて、最後のチェックポイント動作が完了し、データベースが更新され、ＷＡＬがリセットされた。
【００３９】
６）ページ２、１、１、および３が（所定の時系列順に）更新され、対応するページの改訂されたコンテンツがＷＡＬに記録された。
【００４０】
上記にリストした全ての動作を通った後の、データベース１０１およびＷＡＬ１０２の現在の状態が図２に図示される。データベース１０１はページの第一の集合Ｄ＝｛１，２，３，４｝を備え、ＷＡＬ１０２は、記録されたフレームの集合Ｓ＝｛Ｆ１，Ｆ２，...，Ｆ１６｝を備え、フレームは、対応するページの第二の集合Ｄ´＝｛２，１，１，３，２，１，１，３，３，１，２，４，１，２，３，１｝の改訂されたコンテンツを表す。第二の動作は合計１６ページのコンテンツを改訂することを含んだため、これらのページの改訂されたコンテンツを表すフレームのいくつかは、まだＷＡＬ１０２に残っている。これは、合計１６ページ以上を更新することを含んだ後続の動作がなく、１６ページのうちいくつかは、そのような後続の動作によって上書きされなかったためである。第四の動作は合計１１ページのコンテンツを改訂することを含み、第六の動作が四ページのみのコンテンツを改訂することを含んだので、対応するフレームのいくつかはまた、まだＷＡＬ１０２に存在する。最新のチェックポイント動作中、データベース１０１は、データベースの第一のページ１１０ａのコンテンツが、ＷＡＬ１０２のフレームＦ１０で見つかったページの改訂されたコンテンツに対応するように更新された（つまり、Ｆ１０→１）。また、第二のページ１１０ｂのコンテンツは、フレームＦ11で見つかったページの改訂されたコンテンツに対応し（Ｆ11→２）、第三のページ１１０ｃのコンテンツは、フレームＦ９で見つかったページの改訂されたコンテンツに対応する（Ｆ9→３）。データベース１０１の第四のページ１１０ｄのコンテンツは、ＷＡＬ１０２のフレームには見つからないが、上述のように、第四のページ１１０ｄは、最新のチェックポイント動作中に更新されたものの、対応するフレームは、以来、後続の更新中（例えば第六の動作中）に上書きされた。
【００４１】
図に示されるように、ＷＡＬ１０２の各フレームは、チェックポイントの集合Ｃ＝｛ｃ１，ｃ２，ｃ３｝のチェックポイントに対応し、同じチェックポイントに対応するフレームがＷＡＬ１０２に記録される順を考慮することで、フレームは時系列で分類されうる。各フレームは、例えばその対応するチェックポイントに対応するインデックスを含み、データベース１０１自体は、データベースシステムが、ＷＡＬ１０２のうち“アクティブ”もしくは“生き”なフレーム（つまり、データベース１０１に現在格納されたページの改訂されたコンテンツよりも最近のページの改訂されたコンテンツを今まさに含むフレーム、すなわちＷＡＬ１０２のフレームＦ１からＦ４）を決定するために、最新で行われたチェックポイント動作への参照（例えばＳＡＬＴ値）を含みうる。
【００４２】
データベース１０１の前の状態についての情報を抽出するために、本発明の例示の実施形態による方法３００（図３のフローチャートで図示される）は、まず、特定のフレームＦＭを選択Ｓ３０１することからなりうる。現在の例では、特定のフレームは、Ｍ＝１０かつＦＭ＝Ｆ１０となるように選択され、特定のフレームは、一つのチェックポイントｃ１∈Ｃに時系列で先行するチェックポイントｃ２に対応すると想定される。次に、第一の部分集合Ｓｆ⊆Ｓが、Ｓｆが特定のフレームＦＭを含み、それにゼロ以上時系列で先行するフレームを含むよう、識別Ｓ３０２される。例では、Ｓｆは、Ｓｆ＝｛Ｆ５，Ｆ９，Ｆ１０｝となるよう選択される。ページの第一の集合Ｄから、第一の部分集合Ｄ１＝｛４｝が抽出Ｓ３０３され、ページの第二の部分集合Ｄ´ｆ＝｛１，２，３｝は、フレームの第一の部分集合Ｓｆの対応するページから抽出Ｓ３０４される（Ｆ５→２、Ｆ9→３、Ｆ１０→１）。Ｄ１のページのコンテンツおよびＤ´ｆのページの改訂されたコンテンツに基づいて、特定のページＰ１０の特定の改訂されたコンテンツ（特定のフレームＦ１０で表される）を含む前の状態へのデータベースのロールバックが、実行Ｓ３０５されうる。前の状態のデータベース１０１の最初の三ページ１１０ａ−１１０ｃのコンテンツは、Ｄ´ｆで見つけられ、前の状態のデータベース１０１の第四のページ１１０ｄのコンテンツは、Ｄ１で見つけられる。
【００４３】
上記の例では、特定のフレームは、その対応するチェックポイントが、チェックポイントの集合Ｃの一つの他のチェックポイントだけに先行するように選択された。一つの例示の実施形態によると、特定のフレームは、その対応するチェックポイントが、一つの他のチェックポイントだけに先行するように、意図的に選択されうる。ＷＡＬ１０２を用いたデータベースロールバックの従来の方法は、最新のチェックポイントと時間的に等しいまたは後続の状態を抽出するのみであるが、本発明による方法は、このように、ＰＭの改訂されたコンテンツを含む、前のデータベース状態についての情報、最新で行われたチェックポイント動作に先行する状態を抽出することができる。
【００４４】
他の例示の実施形態では、本方法は、ＦＭをその対応するチェックポイントがＣの一つの他のチェックポイントだけに先行するように選択するのに加え、フレームの第二の部分集合Ｓｌ＝｛Ｆ１１｝が、フレームの集合Ｓにおいて、Ｓｌが、特定のフレームＦ１０にゼロ以上後続するフレームを含むよう識別され、Ｓｌは、ページの第三の部分集合Ｄ´ｌ＝｛２｝に対応するステップをさらに含みうる。本方法は、それから、ページの第三の部分集合Ｄ´ｌがページの第二の部分集合Ｄ´ｆの部分集合であることを決定し、本方法によって抽出された前の状態が“真の”前の状態であることを示しうる。特定のフレームＦ１０が選択されると、フレームＦ１１で見つかったページ２の改訂されたコンテンツは、無視され、フレームＦ１１の記録に導いたアクションが行われる前のものと取り替えられなければならない。（ページ２の）所望の改訂されたコンテンツは、フレームＦ５で（すなわちＤ´ｆで）見つかり、よって前の状態は、前の状態のページの全てのコンテンツが、Ｆ１０がＷＡＬ１０２に記録されたばかりの時と同じであるという意味で、真の状態である。
【００４５】
他の例示の実施形態では、本方法は代わりに、他のページの第三の部分集合Ｄ´ｌを識別し、この部分集合がページの第二の部分集合Ｄ´ｆの部分集合でないことを決定しうる。これは、Ｄ´ｌが、ページの第二の部分集合の一部でない少なくとも一つのページ（数式１）を含むことＰＡ∈Ｄ´ｌを決定することによって達成されうる。
【００４６】
【数１】
2016224921.tif 000003
【００４７】
本方法はそれで、抽出された前の状態が、真の前の状態でないことを示しうる。図示したように、先の例の特定のフレームが代わりにＭ＝７およびＦＭ＝Ｆ７となるように選択された場合は、可能なさらなる選択は、Ｓｆ＝｛Ｆ５，Ｆ７｝、Ｄ１＝｛４｝、およびＤ´ｆ＝｛１，２｝（Ｆ５→１、Ｆ７→２）となりうる。（Ｄ´１＝｛１，２，３｝となるように）Ｓｌ＝｛Ｆ８，Ｆ１０，Ｆ１１｝である場合は、Ｄ´ｌのページ３（Ｆ８→３）がＤ´ｆで見つからないのは明らかである。このように、フレームＦ８を記録に導いたアクションは、ページ３の改訂されたコンテンツについての正確なナレッジが入手できないため、取り消すことが出来ない。しかしながら、抽出された前の状態のページの少なくともいくつか（例えばページ１、２、および４）のコンテンツは、Ｆ７が記録されたばかりの時とまだ同じであるため、真の前の状態でない前の状態の抽出はなお有用性があることに留意されたい。
【００４８】
他の例示の実施形態では、特定のフレームは、例えばＭ＝１５およびＦＭ＝Ｆ１５となるように選択されうる。その場合、Ｆ１５はチェックポイントｃ１およびｃ２の両方に先行するため、対応するチェックポイントは、Ｃのうち一つより多いチェックポイントに先行する。部分集合の可能な選択は、Ｓｆ＝｛Ｆ１２，Ｆ１３，Ｆ１４，Ｆ１５｝、Ｄ１＝φ、およびＤ´ｆ＝｛１，２，３，４｝（Ｆ１３→１、Ｆ１４→２、Ｆ１５→３、およびＦ１２→４）となり、Ｐ１５を含む前の状態へのデータベースロールバックが行われ、ページのコンテンツは全てＤ´ｆで見つかりうる。
【００４９】
一実施形態では、本方法はさらに、ページの第一の集合Ｄがページの第二の部分集合Ｄ´ｆの部分集合であること（Ｄ⊆Ｄ´ｆ）を決定するステップを含み、本方法によって抽出された前の状態が真の前の状態であることを示しうる。前の例示の実施形態のように、Ｄ´ｆは、Ｄで見つかった全てのページの改訂されたバージョンを含むため、抽出された前の状態が真の前の状態であることは確かである。
【００５０】
他の実施形態では、本方法は、ページの第一の集合Ｄが、ページの第二の部分集合Ｄ´ｆの部分集合でないことを決定するステップを含みうる。これは、Ｄ´ｆで見つからない少なくとも一つのページをＤが含むことを決定することによって達成することができる。その場合、本方法は、抽出された前の状態が真の前の状態でないことを示しうる。例えば、フレームＦ１４が（ページ２の代わりに）ページ１の改訂されたコンテンツを表した場合、ページ２の改訂されたコンテンツについてのナレッジは入手不可能となり、例えばフレームＦ５（ページ２の改訂されたコンテンツを表すフレーム）の記録に導いたアクションは取り消すことができない。それでも、抽出された前の状態は真の状態ではないが、ページの少なくとも一つ（ＰＭ）のコンテンツはＦＭが記録された直後と同じであるため、なお有用でありうる。
【００５１】
他の例では、特定のフレームが、その対応するチェックポイントが任意の他のチェックポイントに時系列で先行しないよう選択される場合は（すなわち、特定のフレームが、最新のチェックポイント動作の後にＷＡＬ１０２に追加された場合は）、特定のページの特定の改訂されたコンテンツを含む前の状態へのデータベース１０１のロールバックは簡単である。そのようにするための方法は、図２に示した例を尚用いて、Ｍ∈｛１，２，３，４｝となるような特定のフレームを選択することを備えうる。例えば、Ｍ＝３およびＦＭ＝Ｆ３の場合は、部分集合の可能な選択は、Ｓｆ＝｛Ｆ１，Ｆ３｝、Ｄ１＝｛３，４｝、およびＤ´ｆ＝｛１，２｝（Ｆ３→１、Ｆ１→２）となり、その後、Ｐ３を含む前の状態へのロールバックが行われうる。そのような対応する特定のフレームを有する前の状態は、（データベース、ＷＡＬ、もしくはチェックポイント情報のいずれも破損していないという想定の下で）常に真の前の状態でありうる。
【００５２】
データベース１０１の前の状態へのデータベースロールバックを行うよう構成された、例示の実施形態による装置が、図４に示される。装置４０１は、データベース１０１およびそれに関連したＷＡＬ１０２およびチェックポイント情報にアクセスするようになされる。このアクセスは、例えばネットワーク、ローカルバス、ワイヤ、ワイヤレスリンク、または任意の他の、それに適切なタイプでありうるアクセス手段４０４によって提供される。装置は、メモリ４０３およびプロセッサ４０２を備え、プロセッサは、ＷＡＬ１０２のフレームの集合から、要求により特定のフレームを選択するよう構成される。特定のフレームは、対応する特定のページの特定の改訂されたコンテンツを表し、特定のフレームは、少なくとも一つのチェックポイントの集合においてゼロ以上のチェックポイントに時系列で先行するチェックポイントに対応する。プロセッサ４０２は、フレームの集合において、特定のフレームおよびそれに時系列でゼロ以上先行するフレームを含む、フレームの第一の部分集合を識別するよう、さらに構成される。プロセッサ４０２はまた、ページの第一の集合からページの第一の部分集合を抽出するよう、およびフレームの第一の部分集合の対応するページからページの第二の部分集合を抽出するよう構成される。プロセッサ４０２は、特定のページの特定の改訂されたコンテンツを含む前の状態へのデータベース１０１のロールバックを行うよう構成され、ロールバックは、ページの第一の部分集合のコンテンツおよびページの第二の部分集合の改訂されたコンテンツに基づいて行われる。必要な際は、プロセッサは、一時的および永久的に情報を格納するために、メモリ４０３を使用しうる。データベース１０１（および／またはＷＡＬ１０２）は、装置４０１が別の場所から利用可能でありうる、もしくは装置４０１およびデータベース（および／またはＷＡＬ１０２）は、一体化されうる（すなわち、データベース１０１および／またはＷＡＬ１０２は、例えば装置４０１自体に具備された媒体に格納されうる）。
【００５３】
データベースの削除されたまたは修正されたデータについての情報を抽出するためにデータカービング等の方法を用いるのとは対照的に、本発明の方法は本質的に統計的でなく、結果の信用性は、（データベースおよび／またはＷＡＬが破損されていなければ）確定的に知ることができる。同じデータベースに属するデータを継ぎ合わせる際の問題に加え、カービングベースの方法は、データベースのどの表に何のデータが属するかを把握しようとする際、さらに大きな問題に直面しうる（特に、表のいくつかが同じ列の配列を共有している場合）。本発明の方法を用いると、ＷＡＬが必要な情報を含むため、これは問題ではない。本発明による方法はまた、いくつかの時間インスタンスに、データベースがどのようになっているかを示すことができうるが、ある時点のあるデータ片を特定する能力のないカービング方法には適さないタスクである。データベースがそのデータベーススキーマ（例えばその表および列の配列）を変更した場合も同じことが言える。例えば、表が新たな列を与えられた場合もしくは列の順が変更された場合、カービングベースの方法は、表の変更が為された時よりも先に挿入されたデータを分析する妥当な機会がない。本発明を利用した方法では、各時間インスタンスの現在のスキーマ（すなわち、表および列の配列）がＷＡＬで見つかる。カービングベースの方法はまた、二つの表間の接続は通常データカービングが行われようとする時に失われるので、表がどうにか互いに関係するデータベースに属するデータを分析しようとする際に問題に直面しうる。全てのメインデータが単一のキー値表に格納され、人間が読み取り可能な情報を抽出するために、異なるキー値を結合するのに追加の表が用いられる断片データベース等、法科学分析を妨げるよう構造が意図的に適合されたデータベースにも同じことが言える。本発明を利用する方法は、そのような意図的な妨げが起こりにくい。
【００５４】
本発明のさらな実施形態は、上記の明細書を検討すれば、当業者には明らかになる。本明細書および図面は実施形態および例を開示するが、本発明は、これらの特定の例に制限されない。多くの修正および変形が、付属のクレームによって定義される本発明の範囲から逸脱することなく為すことができる。クレームに見られる任意の参照記号は、それらの範囲を限定するとは解されない。
【００５５】
上記の明細書に開示した装置および方法は、ソフトウェア、ファームウェア、ハードウェア、またはそれらの組み合わせとして実装されうる。方法のステップは、明確性の理由から順次リストされるが、ステップのいくつかもしくは全ては、適切であれば、平行して行われうる。ハードウェアの実装においては、上記の説明にある機能的なユニット間のタスクの分割は、必ずしも物理的なユニットへの分割に対応せず、逆に、一つの物理的な構成要素は複数の機能を有してよく、一つのタスクはいくつかの物理的な構成要素によって協働して実行されてよい。  ある構成要素もしくは全ての構成要素は、デジタル信号プロセッサまたはマイクロプロセッサによって実行されるソフトウェアとして実装されうるか、もしくはハードウェアとしてまたは用途特定集積回路として実装されうる。そのようなソフトウェアは、コンピュータ記憶媒体（もしくは非一時媒体）および通信媒体（もしくは一時媒体）を備えうるコンピュータ可読媒体に配布されうる。当業者には周知のように、コンピュータ記憶媒体という文言は、コンピュータ可読インストラクション、データ構造、プログラムモジュール、もしくは他のデータ等の情報を記憶するための任意の方法もしくは技術に実装される、揮発性および不揮発性の両方の、リムーバブルおよび非リムーバブル媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光学ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶装置、もしくは所望の情報を格納するのに用いることができ、コンピュータによってアクセスできる任意の他の媒体を含むが、それらに限定されない。さらに、通信媒体が概して、コンピュータ可読インストラクション、データ構造、プログラムモジュール、もしくは他のデータを、搬送波または他の搬送機構等の変調データ信号で具現し、任意の情報配達媒体を含むことは、当業者には周知である。
【図１ａ】
2016224921.tif 000008
【図１ｂ】
2016224921.tif 000009
【図２】
2016224921.tif 000010
【図３】
2016224921.tif 000011
【図４】
2016224921.tif 000012
【外国語明細書】
2016224921000001.pdf