データ記憶方法
第１のメモリと第２のメモリを備えるシステムにおけるデータベースにデータを記憶する方法が提供される。この方法は、前記第２のメモリから第１のページを読み出すステップと、前記第２のメモリから読み出したデータの少なくとも一部を変更して、前記データベースに記憶すべき変更されたデータを作成するステップと、前記変更されたデータを、前記第１のメモリのデータの第２のページに書き込むステップと、前記第２のページを、前記第１のメモリから前記第２のメモリへコピーするステップとを有する。前記第２のページのデータは、前記データが変更された順序に基づいて連続的に順序が付けられている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースにデータを記憶するための方法に関するものであり、より詳しくは、リレーショナルデータベースにレコードを更新し、そして、リレーショナルデータベースに新規のレコードを追加するための方法に関するものである。
【背景技術】
【０００２】
多くの現代のアプリケーションは、大量のデータの記憶装置を要求する。一般的には、データは、データベースと呼ばれる、集約的に構造化された１つ以上のデータの集合で記憶される。現代のデータベースに記憶される、大量のデータを管理するために、データベース管理システムを使用して、データベースの作成及びメインテナンスを容易にすることが一般的である。
【０００３】
一般的なタイプのデータベースに、リレーショナルデータベースがある。リレーショナルデータベースは、リレーション（関係）の集合としてデータを表現する。各リレーションは、複数のタプルを備え、各タプルは共通の属性に対して値を提供する。各リレーションは、行及び列で構成されているテーブル（表）によって表現される。テーブルの各行は、リレーションのタプルを表現し、各列は、そのリレーションの属性を表現する。
【０００４】
タプルは、コンピュータシステムでは「レコード」として記憶される。各タプルの属性値は、フィールドと呼ばれる、レコード内のバイトのシーケンスによって表現される。
【０００５】
リレーショナルデータベース管理システム（ＲＤＢＭＳ）は、ユーザアプリケーションによって提供されるクエリー動作を実行する。クエリー動作は、コンピュータのメインメモリに記憶されるデータベースレコードについて実行される。データへの高速アクセスの必要性のために、メインメモリは、一般的には、ランダムアクセスメモリ（ＲＡＭ）によって提供される。必要な高速アクセス時間を提供しながら、メインメモリを提供するために一般的に使用されるＲＡＭのタイプは揮発性記憶技術であり、これは、情報を記憶するための電力を要求する。また、ＲＡＭのコストが相対的に高いことは、合理的な大規模データベースに対しては、メインメモリが、データベースのすべてのテーブルのすべてのレコードを記憶するためには十分に大きくないことを意味する。
【０００６】
このように、データベースのテーブルは、低速ではあるが高容量として一般的に提供されるセカンダリメモリにも記憶され、これは、ハードディスクドライブのような不揮発性記憶装置である。
【０００７】
データベースのレコードを読み出すあるいは変更することが要求される場合、まず、レコードがメインメモリに存在するかどうかが判定される。特定のレコードがメインメモリに存在しない場合、そのレコードは、セカンダリメモリに配置され、処理のためにメインメモリにコピーされる。メインメモリがセカンダリメモリからコピーされる追加のレコードを記憶するために十分な空きスペース（領域）を有していない場合、セカンダリメモリからコピーされる追加のレコードを記憶するためのスペースを作成するために、メインメモリに記憶されるどのレコードを排出するべきかを判定する必要がある。メインメモリから排出するために選択されるレコードがメインメモリ内で変更されている場合、その変更されているレコードは、レコードがメインメモリから排出される場合にその変更が損失しないことを保証するために、セカンダリメモリへコピーされる。
【０００８】
データは、８ビットの集合でメモリに記憶され、それらはそれぞれバイトと呼ばれる。ディスクは、論理的には、固定サイズのグループの所定数のバイトで構成され、一般的には、これは、「ブロック」として知られる。ディスクからのデータを読み出し、また、ディスクへデータを書き込むための動作は、まとめてＩ／Ｏ動作として知られていて、また、一般的には、各Ｉ／Ｏ動作において整数ブロックで読み書きすることがより有効である。
【０００９】
データベースのテーブルに含まれるレコードは、ページと呼ばれるグループに記憶される。時には、データベースのページのサイズは、データベースが記憶されているハードディスクのブロックサイズに一致するように選択され、そうすることで、データベースのレコードは、個々のレコードではなくページ全体で、ハードディスクとメインメモリ間をコピーされ、これによって、メインメモリとセカンダリメモリとの間のレコード転送の効率性を最大にしている。つまり、特定のレコードが要求される場合、そのレコードを含むページがセカンダリメモリからメインメモリへコピーされる。そのレコードが変更される場合、ページ全体（その変更を含む）がメインメモリからセカンダリメモリへコピーされる。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ページがセカンダリメモリからメインメモリへ一旦コピーされる場合では、そのページに含まれるレコード群の１つだけが、あるいはいくつかのサブセットだけが変更されることが多い。それゆえ、セカンダリメモリへページ全体をコピーする必要性は、大量数の未変更のレコードも、セカンダリメモリへ書き込まれることになり、これは、非常に非効率である。
【００１１】
本発明の目的は、上述の課題の少なくとも１つを除去するあるいは軽減することである。
【課題を解決するための手段】
【００１２】
本発明の第１の態様に従えば、第１のメモリと第２のメモリを備えるシステムにおけるデータベースにデータを記憶する方法が提供される。この方法は、前記第２のメモリから第１のページを読み出すステップと、前記第２のメモリから読み出されるデータの少なくとも一部を変更して、前記データベースに記憶すべき変更されたデータを作成するステップと、前記変更されたデータを、前記第１のメモリのデータの第２のページに書き込むステップと、前記第２のページを、前記第１のメモリから前記第２のメモリへコピーするステップとを有し、前記第２のページのデータは、前記データが変更された順序に基づいて連続的に順序付けられている。
【００１３】
前記データの第１のページと前記第２のページは、複数のデータベースのレコードを含んでいても良い。前記変更されたデータは、１つ以上のデータベースのレコードを含んでいても良い。前記第２のページに書き込まれる前記変更されたデータは、前記第１のページのレコード群の内の１つの少なくとも一部に基づくデータを含んでいても良い。
【００１４】
データが変更される順序に基づく順序でデータ（例えば、データベースのレコード）を前記第２のページに記憶することによって、従来のログ取得処理とチェックポイント処理によって使用されるタイプのログファイルを維持する必要性が取り除かれる。
【００１５】
また、本明細書で説明される方法は、第１のメモリから第２のメモリへの要求されるページコピー動作の数を削減するという効果がある。例えば、ページを平均してＫ個のレコードに割り当てることができる場合、提案の発明を用いると、Ｋ個のレコードの変更は、第１のメモリから第２のメモリへコピーされるページは１つだけで済むようになる。近接ランダムアクセスパターンを有する大規模データベースを伴う従来のデータベース管理システムでは、平均して、Ｋ個のレコードの変更は、セカンダリメモリにはＫ個のページがコピーされることになることが予想される。
【００１６】
変更されたデータを第２のページに書き込むことは、第２のページに従前に書き込まれているデータに、その変更されたデータを付加することを含んでいても良い。
【００１７】
インデックスは、前記第２のメモリから読み出される前記第１のページのレコードを参照することができ、この方法は、前記変更されたデータが書き込まれる前記第２のページを参照するための前記インデックスのエントリを変更するステップを更に有していても良い。即ち、本発明の態様に従うデータベースに記憶されるレコードに対するインデックスが存在する場合、そのデータベースのレコードの変更は、そのレコードの新規の位置を示すために更新されるべき、変更されたレコードに対応するインデックスのエントリを要求することができる。例えば、インデックスがページ番号とそのページのオフセットを使用してレコードを参照する場合、上述のレコードの変更は、そのレコードに対応するインデックスのエントリが、そのページ内に記憶されるレコードにおける、その新規のページとそのオフセットを参照するために更新されることを要求することになる。
【００１８】
この方法は、更に、読み出された第１のページに含まれず、かつデータベースに記憶されるべき新規のデータを含む、新規のデータベースのレコードを第２のページに追加することを含んでいても良い。つまり、書き込むデータは、新規のレコードの書き込み、あるいは、既存のレコードの変更を表すデータの書き込みを含んでいても良い。どちらの場合でも、データは、その作成あるいは変更の順序で書き込まれる。
【００１９】
第２のページは、所定量のデータがその第２のページに書き込まれている場合に前記第２のメモリに書き込まれても良い。例えば、第２のページが一杯である（即ち、すべての自身のレコードが、新規に作成されたデータあるいは変更されたデータを含んでいる）場合、それは、第２のメモリを「フラッシュ」することができる。それにより、第２のページは、第１のメモリで空きにすることができる。それゆえ、取り消し（undo）／やり直し（redo）ログを保持する必要がない。なぜなら、第２のページが一杯になると、「フラッシュ」はオンザフライで実行することができるからである。
【００２０】
所定量のデータが前記第２のページに書き込まれる場合、更なる第２のページが作成されても良い。更なる第２のページに記憶されるデータは、データが変更される順序に基づいて連続的に順序付けられていても良い。
【００２１】
データの読出／書込動作に関して、前記第１のメモリは第１の関連アクセス時間を有していても良く、前記第２のメモリは第２の関連アクセス時間を有していても良い。前記第１のアクセス時間は前記第２のアクセス時間よりも遅くても良い。前記第１のメモリは揮発性メモリであっても良く、一方、前記第２のメモリは不揮発性メモリであっても良い。例えば、前記第１のメモリは、例えば、揮発性のランダムアクセスメモリ（ＲＡＭ）であっても良く、前記第１のアクセス時間は、前記第２のアクセス時間よりも１０００倍の桁で高速であっても良い。前記第２のメモリは、例えば、ハードディスクドライブであっても良い。
【００２２】
この方法は、更に、前記第２のメモリに記憶されている複数のページに含まれる同一データの内、旧式のバージョンと旧式でないバージョンを識別するために、前記複数のページを処理するステップと、前記旧式でないデータが隣接して配置されるように、前記複数のページの最初の１つのページ内にデータを再配置するステップと、前記複数のページの別ページから、前記複数のページの前記最初の１つのページへ旧式でないデータをコピーし、前記複数のページの前記最初の１つのページに旧式のデータを上書きし、前記複数のページの前記最初の１つのページに旧式でないデータを維持するステップとを備えていても良い。このような処理は、旧式のデータだけを有する、１つ以上の複数のページを得ることができる。旧式のデータだけを含むページは、前記第２のメモリのスペースを空きにするために「解放」することができる。
【００２３】
この方法は、トランザクションの開始と完了を示すデータを、前記第２のページに記憶するステップを更に備えていても良い。
【００２４】
この方法は、部分的に実行されるトランザクションを識別するために、トランザクションの開始と完了を示す前記データを処理するステップを更に備えていても良い。
【００２５】
この方法は、前記第２のページに記憶される前記データを読み出すステップと、前記第２のページから読み出されるデータを変更するステップと、前記読み出されたデータに影響を与えることなく、前記変更されたデータを、前記第２のページ、あるいは、更なる第２のページへ書き込むステップとを更に備えていても良い。
【００２６】
上述の方法に従ってデータベースにデータを記憶することによって、ログ処理が暗黙的に発生する。なぜなら、新規のレコードの挿入、あるいは既存のレコードの変更は、データが書き込まれる最終ページに新規のレコードを割り当てることになるからである。
【００２７】
本発明の態様は、任意の便利な形式で実現することができることが理解されるであろう。例えば、本発明は、適切なコンピュータプログラムによって実現されても良い。このコンピュータプログラムは、有形の搬送媒体（例えば、ディスク）あるいは無形の搬送媒体（例えば、通信信号）であっても良い、適切な搬送媒体で搬送されても良い。本発明の態様は、適切な装置を使用して実現されても良く、この適切な装置は、本発明を実現するように構成されているコンピュータプログラムを実行するプログラマブルコンピュータの形態をとることができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態が実現されるコンピュータシステムを示す図である。
【図２】上位レベルでの本発明の実施形態の動作を示すフローチャートである。
【図３】図１のコンピュータシステムのメインメモリに、データがどのようにして記憶されるかを示す図である。
【図４】データベースにレコードを追加するために実行される処理を示すフローチャートである。
【図５】データベースのレコードを変更するために実行される処理を示すフローチャートである。
【図６】図１のコンピュータシステムのメインメモリに記憶されるデータに、データのレコードの変更がどのように影響を与えるかを示す図である。
【図７】図１のコンピュータシステムのメインメモリに記憶されるレコードの全体ページを示す図である。
【図８】セカンダリメモリに記憶される冗長レコードを識別し抹消するために実行される処理を示すフローチャートである。
【図９ａ】データベースのページの位置に、図８の処理がどのように影響を与えるかを示す図である。
【図９ｂ】データベースのページの位置に、図８の処理がどのように影響を与えるかを示す図である。
【図１０】トランザクションの原子性を保証するために実行される処理を示すフローチャートである。
【発明を実施するための形態】
【００２９】
図１は、本発明の実施形態を実現するために構成されるコンピュータ１を示している。コンピュータ１は、ＲＡＭによって提供されるメインメモリ２と、ハードディスクドライブによって提供されるセカンダリメモリ３とを備える。プロセッサ４は、メインメモリ２の第１の論理部分５に記憶されている命令を読み出し、実行するように構成されている。これらの命令によって操作されるデータは、メインメモリ２の第２の論理部分６に記憶される。メインメモリ２の第１の論理部分５に記憶される命令は、とりわけ、プロセッサ４を制御して、メインメモリ２の第２の論理部分６とセカンダリメモリ３との間でデータをコピーする。
【００３０】
メインメモリ２の第１の論理部分５に記憶される命令は、セカンダリメモリ３に記憶されるリレーショナルデータベースの一部を形成する、メインメモリ２に記憶されるデータの処理を制御する。このリレーショナルデータベースのデータは、複数のページ７の形式で、メインメモリ２とセカンダリメモリ３の両方に記憶される。ここで、各ページは、データベースのレコードの形式で、所定量のデータを備えている。
【００３１】
特定のデータベースのテーブルの特定のレコードを効率的に配置することを、プロセッサ４によって実行されるユーザアプリケーションに可能にするために、メインメモリ２とセカンダリメモリ３のそれぞれは、インデックス８ａ、８ｂと呼ばれる追加のデータ構造を記憶する。インデックス８ａ、８ｂはそれぞれ、順序付け基準として、いくつかのレコードを使用する、順序付けされたレコードリファレンスのリストである。各データベースのテーブルは、そのデータベースのテーブルのすべてのレコードに渡る走査を可能するための、少なくとも１つのインデックスを有する。インデックスの順序付け基準は、テーブルの、「キー」と呼ばれる、非ヌル値の属性を使用して確立される。レコードがテーブルに挿入されるあるいはテーブルから削除される毎に、関連するテーブルのインデックスが更新される。レコードリファレンスは、インデックスを走査する場合に、各レコードへのアクセスを可能にするために、各インデックスセルに保存される。このリファレンスは、通常は、「ｒｉｄ」（レコード識別子）として知られており、そして、これは、ページ番号と、レコードが割り当てられる場合にページの先頭バイトからの内部バイトオフセットで構成される。例えば、レコードがページ２の第８バイト目に記憶される場合、ｒｉｄは、ページ２とオフセット８を特定することになる。
【００３２】
データは、所定サイズのページで、セカンダリメモリ３とメインメモリ２との間で転送される。プロセッサ４によって実行されるユーザアプリケーションによって要求される場合、データは、セカンダリメモリ３からメインメモリ２へ転送される。データは、永続的な記憶のために、メインメモリ２からセカンダリメモリ３へ転送される。
【００３３】
メモリ２に記憶されるページ７ａは、メインメモリ２からセカンダリメモリ３へコピーされているページである。メインメモリ２に記憶されているページ７ｂは、セカンダリメモリ３に記憶されているレコードに対する変更、及びセカンダリメモリ３に記憶されているレコードに追加されるべきレコードの少なくとも一方を記憶する。このように、ページ７ｂは、メインメモリ２からセカンダリメモリ３へコピーされる必要があるものである。ページ７ａは、セカンダリメモリ３へコピーされる必要はない（ページ７ａがメインメモリ２から削除されるとしても）、これは、これらのページのレコードは既にセカンダリメモリ３に記憶されていて、任意の追加あるいは変更がページ７ｂの１つに記憶されているからである。ページ７ｂは、以下では、ページログと呼ぶことにする。
【００３４】
図２は、データベースにデータを記憶するための、プロセッサ４によって実行される処理を示している。ステップＳ１で、レコード（既存のレコードに対する変更あるいは完全に新規のレコードを表している）は、データが現在追加されているページログのページ７ｂの末尾（最後）に記憶される。このページ７ｂが一杯である場合（即ち、更なるレコードを記憶するための空きスペースがない）、ステップ２で、ページは、永続的な記憶のためにセカンダリメモリ３へコピーされる。ページ７ｂのレコードは、これらのレコードが変更された及び作成されたのいずれか一方が行われた一時的な順序に従って順序付けされる。
【００３５】
図３は、関連するインデックス８ａに付随する、ページ７ｂの詳細を示している。上述のように、また、図３で示されるように、レコードが、それらの作成あるいは変更の順序で、ページ７ｂを構成するページログに追加される。つまり、ページ７ｂは、２０個のレコードを記憶する第１のページ９を備え、この２０個のレコードは、それらの作成あるいは変更の順序でページ９に追加されている。インデックス８ａは、上述の第１のページ９のレコードを参照している。但し、説明を簡単にするために、図３では、リファレンスのサブセットだけを示している。
【００３６】
ページ９が一杯になると、図４を参照して説明するように、それは、メインメモリ２からセカンダリメモリ３へコピーされ、新規のページが作成される。ステップＳ３で、ページ７ｂの１つのレコードへの挿入を要求するコマンドが処理される。この挿入は、新規のレコードの作成、あるいは既存のレコードの変更から生じ得る。ステップＳ４で、挿入対象のレコードを保持するために、ページのログの現在の「最終」ページにスペースがあるかどうかが判定される。スペースがある場合、処理は、ステップＳ５へ進み、そこで、レコードは、「最終」ページに挿入される。そのようなスペースがない場合、処理は、ステップＳ４からステップＳ６へ進み、そこで、新規のページが作成されて（図３では、ページ１０として）、挿入対象のレコードを保持する。そして、このページが、ページログの「最終」ページとなる。処理は、ステップＳ６からステップＳ５へ進み、そこで、レコードは、新規のページに追加される。
【００３７】
レコードが変更される場合に実行される処理について、図５及び図６を参照して説明する。図５をまず参照すると、ステップＳ７で、特定のレコードに対するリクエストが処理され、ステップＳ８で、特定のレコードが、メインメモリ２に現在常駐しているページに記憶されているかどうかを判定するためのチェックが実行される。このチェックは、対象のレコードが記憶されているページを識別するために、インデックス８ａと８ｂを使用して、そして、対象のレコードが記憶されているページがメインメモリ２に常駐しているかどうかを判定することによって実行することができる。対象のページがメインメモリ２に常駐している場合でない場合、ステップＳ９で、対象のページは、セカンダリメモリ３からメインメモリ２へコピーされる。対象のページを受け入れるための、メインメモリ２内の空きスペースが十分でない場合、メインメモリ２に現在常住している１つ以上のページ７ａが、十分な空きスペースを提供するためにメインメモリから排出される。排出するページ（群）７ａをどれにするかの選択は、ファーストインファーストアウト（ＦＩＦＯ）選択ポリシーに基づいていても良い。
【００３８】
図６は、ステップＳ９の処理後の、メインメモリ２の取り得る状態を示している。ページ１１がメインメモリ２に記憶されていることがわかる。ここで、ページ１１は、セカンダリメモリ３からコピーされているものである。このページ１１は、ステップＳ７でリクエストされているレコードを記憶する。これは、インデックス８ａのエントリ１２によって識別される。
【００３９】
対象のページがメインメモリ２に記憶されていて、また、上述の方法で対象のページのコピーの後、処理がステップＳ９からステップＳ１０へ進んでいる場合には、処理は、ステップＳ８から直接ステップＳ１０へ進む。ステップＳ１０で、対象のレコードが変更され、ステップＳ１１で、その変更された値を含むレコードの新規のコピーが作成される。変更された値を含むレコードは、ページログを作成するページ７ｂの１つに記憶されるものである。それゆえ、処理は、ステップＳ１１からステップＳ１２へ進み、そこで、変更された値を含むレコードを保持するために、ページログの「最終」ページにスペースがあるかどうかを判定するためのチェックが実行される。スペースがある場合、処理は、ステップＳ１３へ進み、そこで、変更された値を含むレコードがページログの「最終」ページに記憶される。ページログに変更された値を含むレコードが記憶されると、ステップＳ１４で、インデックス８ａが更新され、そうすることで、図６の破線で示されるように、インデックス８ａのエントリ１２は、ページログの「最終」ページの最終レコードを参照することになる。インデックス８ａのエントリ１２とページ１１のレコードとの間のリンクはこれ以上存在しない。
【００４０】
本発明のいくつかの実施形態では、ステップＳ１１で、インデックスのエントリの現在のｒｉｄは、ステップＳ１４でインデックスが更新される前に、レコードの「前値」フィールドに保存される。図１０を参照して後述するように、これは、例えば、クラッシュのイベント時に、変更をロールバックすることが可能となる。
【００４１】
ステップＳ１２で、ページログの「最終」ページに十分なスペースがないことが判定される場合、上述のステップＳ１３で処理を継続する前に、ステップＳ１５で、ページログの新規のページが作成されることが理解されるであろう。
【００４２】
上述の説明は、セカンダリメモリ３からコピーされるのではなく、ページログの一部を形成しないページに記憶されるレコードの変更に関するものである。いくつかの場合では、メインメモリ２に存在するページログのページに記憶されるレコードが、図５を参照して説明されるタイプの処理によって変更されても良いことが理解されるであろう。例えば、図７を参照すると、ページログを作成するページ７ｂのページ１４に記憶されるレコード１３への変更が要求される場合がある。このような場合、変更を表すレコード１５がページ１６に作成され、そして、インデックス８ａ、より詳しくは、インデックス８ａのエントリ１７が、レコード１５を参照するために更新される。
【００４３】
図７からは、ページ１４が一杯であることがわかる（即ち、レコードを記憶することができるスペースがこれ以上ない）。そのような場合、ページ１４が、メインメモリ２からセカンダリメモリ３へコピーされる。
【００４４】
上述の説明から、データベースのレコードへのすべての変更（新規のレコードの作成及び既存のレコードの変更を含む）が、ページログの現在の「最終」ページへレコードを追加することによって実行されることがわかる。このような場合、セカンダリメモリ３にすべての変更が正しく記憶されることを保証するために、ページログのページだけがメインメモリ２からセカンダリメモリ３へとコピーされる必要がある。
【００４５】
すべての変更が、ページログの現在の「最終」ページに記憶されるならば、他のページに記憶される従前のバージョンのレコード群は旧式のものとなるが、セカンダリメモリ３の記憶スペースを占有し続けることになる。セカンダリメモリ３の記憶容量は典型的には大きい（また、メインメモリ２の記憶容量も大きい）ならば、このことは必ずしも問題とならない。しかしながら、いくつかの実施形態では、旧式のレコード群を識別して、セカンダリメモリから削除するための処理が実現される。これについては、図８及び図９を参照して説明する。以下の説明では、ページ群は、別のページとの間で順序付けられていて、そして、かつ各ページは、自身の直後のページとのリンクを含んでいると想定する。
【００４６】
ステップＳ１６で、処理対象のページが選択される。以下の説明では、選択されたページはページ＃１として参照され、一方、その直後のページはページ＃２として参照される。いくつかの実施形態では、ステップＳ１６で、ページは、そのページ内で旧式となるレコード群（即ち、破棄されるレコード群）の比率に基づいて選択される。このような旧式のレコード群は、例えば、インデックス内の任意のエントリによって参照されないレコード群を識別するインデックスを処理することによって識別することができる。より詳細には、特定のページにおけるレコードとそのオフセットに対して、このインデックスは、そのインデックスがそのページとそのオフセットに対応するｒｉｄを有するエントリを含んでいるかどうかを判定するためにサーチされても良い。そのインデックスがそのような対応するｒｉｄを含んでいない場合、そのレコードは使用されない。選択的には、ステップＳ１６で、各ページと時間とを関連付け、そして、最も古いページを選択することが好ましい場合がある。上述の技術を使用してページが作成されると、ページは、一時的な順序で必然的に作成されることになり、最も古いページのそのような選択は比較的単純なものとなる。
【００４７】
ステップＳ１６でページを選択すると、処理は、ステップＳ１７からステップＳ２０によって定義されるループに進み、そこで、ページ＃１のすべてのレコードが順に処理される。ステップＳ１７で、ページ＃１内に処理対象のレコードが残っているかどうかを判定するためのチェックが実行される。残っている場合、ステップＳ１８で、処理が継続する。ステップＳ１８で、次のレコードが選択され、ステップＳ１９で、レコードが旧式であるかどうかを判定するためのチェックが実行される。そのような場合、処理はステップＳ１７に戻り、ループを継続する。ステップＳ１９で、旧式でないレコードが処理される場合、ステップＳ２０で、このレコードは、旧式のレコードを現在保持している、ページ内の最上位の位置へ移動される。このレコードは、自身の内容をページ内のより上位の位置へコピーすることによって移動され、これにより、そのレコードを保持しているスペースを空きスペースであることを示すようにすることができる。
【００４８】
ステップＳ１７で、ページ＃１内のすべてのレコード群が処理されていると判定される場合、処理はステップＳ２１へ進み、そこで、ページ＃１が任意の旧式のレコードあるいは空きスペース（即ち、ステップＳ２０で、旧式のレコードを現在のレコードと置換することによる結果として）を含んでいるかどうかを判定するためのチェックが実行される。ステップＳ２１で、ページ＃１が旧式のレコードあるいは空きスペースを含んでいると判定される場合、処理はステップＳ２１からステップＳ２２へ進み、そこで、ページ＃１の直後にあるページであるページ＃２に処理対象のレコードが残っているかどうかを判定するためのチェックが実行される。ページ＃２に処理対象のレコードが残っている場合、処理はステップＳ２２からステップＳ２３へ進み、そこで、ページ＃２の次のレコードが処理対象として選択され、その後、ステップＳ２４で処理を継続する。ここでは、選択されたレコードが旧式のものであるかどうかが判定される。選択されたレコードが旧式のものである場合、処理はステップＳ２４からステップＳ２２へ進む。ステップＳ２４で、選択されたレコードが旧式のものでないと判定される場合、選択されたレコードは、ページ＃１の最上位の空き位置（即ち、旧式のレコードを記憶する最上位の位置、あるいは最上位の空きスペース）へ移動される。そして、処理は、ステップＳ２５からステップＳ２１へと進む。
【００４９】
ステップＳ２２で、ページ＃２がこれ以上の処理対象のレコードを含んでいないと判定される場合、処理はステップＳ２２からステップＳ２６へ進む。同様に、ステップＳ２１で、ページ＃１が旧式のレコードあるいは空きスペースを含んでいないと判定される場合、処理はステップＳ２１からステップＳ２６へ進む。
【００５０】
ステップＳ２６で、ページ＃２で任意の現在のレコードを含んでいるかどうかが判定される。即ち、ページ＃２のすべてのレコードが旧式のものであるかどうか（特に、以下では、ページ＃１へレコードをコピーすることができるか）が判定される。ページ＃２のすべてのレコードが旧式のものである場合、ページ＃２は、有用な情報をこれ以上記憶することがないものとして、空きとすることができる。ステップＳ２７で、ページ＃２が空きとなり、ステップＳ２８で、ページ＃１が変更される。そうすることで、従前のページ＃２に続くページとして自身の次のページ（ページ＃３として参照される）を識別する。
【００５１】
ステップＳ２６で、ページ＃２が現在のレコードを含んでいると判定される場合、処理はステップＳ２６からステップＳ２９へ進み、そこで、ページ＃２は、上述の処理（即ち、図８の処理の目的のためにページ＃２はページ＃１となる）を使用して処理される。
【００５２】
従前の処理では、処理対象のページは、セカンダリメモリ３からメインメモリ２へコピーされる。上述の処理によって変更された任意のページは、永続的な記憶のためにセカンダリメモリ３へコピーされる。システムクラッシュのイベント時には、いくつかのレコードがページ間で複製されても良い。そのような複製を識別し、かつ除外することが要望される場合、それは、各レコードとログ番号等を関連付けることによって達成することができる。そのようなログ番号は、図５のステップＳ１１でレコードが作成する場合に初期化されても良い。
【００５３】
図８の処理は、旧式のレコードが時々削除されることを保証するように構成されている優先度の低い処理を使用して実現することができる。これによって、セカンダリメモリ記憶装置の過度の必要条件を回避する。
【００５４】
図９ａと図９ｂは、図８を参照して説明される処理前後のページ＃１とページ＃２の例を示している。
【００５５】
図９ａでは、ページ＃１は６個のレコードを記憶しているが、実際には、これらのレコードの内の３個のレコードは旧式のものである。ページ２は、２つの旧式でないレコード（レコード＃４とレコード＃５）だけを記憶している。図９ｂは、上述の処理後を示していて、レコード＃４とレコード＃５は、ページ＃１へ移動され、そうすることで、ページ＃２は旧式のレコードだけを記憶し、それゆえ、ページ＃２を空きにすることができる。
【００５６】
図９ａと図９ｂは、インデックス８がページ＃１とページ＃２のレコードを参照していることを示している。実行される処理はインデックスのエントリを補正する。例えば、図９ａのページ＃２の自身の位置でレコード＃４を参照するインデックスのエントリは、図９ｂのページ＃１の自身の位置でレコード＃４を参照する。
【００５７】
いくつかの実施形態では、現在のバージョンのレコードが直前のバージョンである場合、そのレコードは旧式のものであるとみなされない。これは、システムクラッシュのイベント時にロールバック動作を正しく実行させることを可能にするためである。例えば、レコードが旧式のものであると見なされない場合、そのレコードは、コミットされないトランザクションの一部となる。このトランザクションについては、以下で詳述する。
【００５８】
ＲＤＢＭＳでは、特定のレコードに影響を与えるいくつかの動作のセットは、原子性、一貫性、完全性及び耐久性（時には、「ＡＣＩＤ」属性と呼ばれる）を保証するような方法で実行される。一般論として、これは、動作のセットが自身で完全に実行されるべきであり、あるいは、不可能である場合には、完全に中断されるべきである。つまり、これらの動作のサブセットだけが実行され、その動作のその他の部分が実行されないことは生じるべきではない。完全に実行されなければならない動作のセットは、時には、トランザクションと呼ばれる。
【００５９】
周知のデータベース管理システムでは、トランザクションの原子性はログファイルを使用して保証される。つまり、既知のデータベース管理システムでは、トランザクションのコミットポイントは、そのトランザクションが正常に実行されて、トランザクションの結果がセカンダリメモリに記憶されるログファイルに記録されるポイントであり、そうすることで、トランザクションの結果を、システム故障のイベント時に再生することができる。一般的には、コミットされるトランザクションの一部を形成する動作がセカンダリメモリのデータベースに書き込まれる場合、クラッシュからＲＤＢＭＳのリカバリー時のログファイル全体を読み出すことを回避するために、チェックポイントのエントリがログファイルに追加される。
【００６０】
トランザクションが完全に実行される場合、コミット手順が実行され、そして、「トランザクションコミット完了」メッセージがユーザアプリケーションに送信されることで、トランザクションに含まれるすべての動作が正常に終了したことと、かつ動作の耐久性を通知する。そうでなければ、すべてのレコードの内容を、トランザクションの実行が開始される直前の値に戻すロールバック手順が起動される。ロールバック手順の終了時には、ユーザアプリケーションにも、トランザクションの実行の失敗が通知される。
【００６１】
本発明のシステムでは、トランザクションのコミットポイントは、そのトランザクションを行う動作のすべてがページログからセカンダリメモリに書き込まれていて、かつ、インデックスが新規のレコードを指し示すように更新されている時点のポイントである。
【００６２】
トランザクションの原子性が必要とされる場合、上述の方法は、単純なチェックポイント手順を提供するように変更されても良く、そうすることで、システムクラッシュからリカバリーする場合にすべてのデータベースのページを読み出すことを回避することができる。これは、トランザクションの開始と完了に関する情報を含む「フェイク」トランザクションレコードをページ内に含ませることによって達成することができる。より詳しくは、これらの「フェイクレコード」は、トランザクションの開始、トランザクションのコミット、及びトランザクションの中止を示している。例えば、「開始トランザクション（スタートトランザクション）」レコードはページログに挿入されて、「開始トランザクション」レコードに続く動作が単一のトランザクションの一部であり、そして、「コミット」レコードがそのトランザクションの最終動作の直後のページログに書き込むことができることを示すことができる。同様に、トランザクションが中止される場合、「中止された」レコードを、トランザクションが中止される前の直前の動作の直後のページログに書き込むことができる。
【００６３】
システムクラッシュが発生すると、対応するトランザクションのコミットレコードあるいはトランザクションのトランザクション中止レコードを持たない、トランザクションの開始レコードを識別することの逆の順序で、レコードが処理される。任意のこのようなトランザクションの開始レコードに遭遇すると、トランザクションの開始レコードに続くすべてのレコードが破棄され、そして、それらのレコードに関連付けられているインデックスのエントリが、レコードの「前値」フィールドを使用して、データベース内のそれらのレコードの従前の位置を示すように設定される。
【００６４】
図１０は、システムクラッシュのイベント時（例えば、電力不足のイベント時）に実行することができる処理の例を示していて、ここではデータがメインメモリ２から損失している。
【００６５】
ステップＳ３０で、セカンダリメモリ３に記憶されているページの最終ページ（つまり、システムクラッシュ前にセカンダリメモリにコミットされる最終ページ）が取得され、そして、現在のページとして設定される。ステップＳ３１で、そのページの最終レコードが現在のレコードとして設定される。ステップＳ３２で、現在のレコードが開始トランザクションレコードであるかどうかが判定される。現在のレコードが開始トランザクションレコードでない場合、処理はステップＳ３３へ進み、そこで、現在のレコードがコミットレコードあるいは中止レコードであるかどうかが判定される。
【００６６】
ステップＳ３３で、現在のレコードがコミットレコードあるいは中止レコードでないと判定される場合、処理はステップＳ３４へ進み、そこで、現在のページに従前のレコードが存在するかどうかが判定される。ステップＳ３４で、現在のページに従前のレコードが存在するかどうかが判定される場合、処理はステップＳ３５へ進み、任意の従前のページが存在するかどうか（即ち、現在のページがセカンダリメモリにコミットされた最初のページであるかどうか、これ以上、従前のページがないかどうか）が判定される、これ以上、従前のページが存在しないと判定される場合、処理はステップＳ３５から最後のステップＳ３８へ進む。
【００６７】
一方、ステップＳ３５で、更なる従前のページが存在すると判定される場合、処理は、ステップＳ３５からステップＳ３６へ進み、従前のページ（即ち、現在のページの直前のページ）が新規の現在のページとして設定される。そして、処理はステップＳ３６からステップＳ３１へ進む。
【００６８】
ステップＳ３４で、現在のページに従前のレコードが存在する場合、処理はステップＳ３７へ進み、そこで、現在のページの現在のレコードの前のレコードが新規の現在のレコードとして設定される。そして、処理は、ステップＳ３７からステップＳ３２へ進む。
【００６９】
ステップＳ３３で、現在のレコードがコミットレコードあるいは中止レコードであると判定される場合、これは、ステップＳ３８で、データベースに記憶されている任意のレコードをロールバックする必要がないことを示し、そして、処理を終了する。つまり、ステップＳ３３で、中止レコードあるいはコミットレコードに遭遇すると、これは、未完了のトランザクションの一部であるレコードはデータベースに存在しないことを示すことになる。
【００７０】
ステップＳ３２で、現在のレコードが開始トランザクションレコードであると判定される場合、処理はステップＳ３９へ進み、そこで、現在のレコードに続くすべてのレコード（即ち、開始トランザクションレコードの後にデータベースに追加されるレコード）がロールバックされる。そして、処理は、ステップＳ３９から最後のステップＳ３８へ進む。
【００７１】
図１０を参照して説明される処理は、暗黙的なチェックポイント手順を含んでいることが理解されるであろう。これは、処理は常にコミットフェイクレコードあるいは中止フェイクレコード時に終了するので、システムクラッシュからのリカバリー時にデータベース内の各レコードを処理する必要がない場合には、処理は常に終了するからである。それゆえ、一般的には、データベース内の各レコードを処理する必要がなくなる。
【００７２】
データベースとコンピュータという用語は、それらの任意の特定の実装に制限されず広く解釈されるべきであることが理解されるであろう。添付の請求項の範囲から逸脱することなく、本発明の様々な変更及び応用がなされることが、本発明の教示から当業者は理解するであろう。
【技術分野】
【０００１】
本発明は、データベースにデータを記憶するための方法に関するものであり、より詳しくは、リレーショナルデータベースにレコードを更新し、そして、リレーショナルデータベースに新規のレコードを追加するための方法に関するものである。
【背景技術】
【０００２】
多くの現代のアプリケーションは、大量のデータの記憶装置を要求する。一般的には、データは、データベースと呼ばれる、集約的に構造化された１つ以上のデータの集合で記憶される。現代のデータベースに記憶される、大量のデータを管理するために、データベース管理システムを使用して、データベースの作成及びメインテナンスを容易にすることが一般的である。
【０００３】
一般的なタイプのデータベースに、リレーショナルデータベースがある。リレーショナルデータベースは、リレーション（関係）の集合としてデータを表現する。各リレーションは、複数のタプルを備え、各タプルは共通の属性に対して値を提供する。各リレーションは、行及び列で構成されているテーブル（表）によって表現される。テーブルの各行は、リレーションのタプルを表現し、各列は、そのリレーションの属性を表現する。
【０００４】
タプルは、コンピュータシステムでは「レコード」として記憶される。各タプルの属性値は、フィールドと呼ばれる、レコード内のバイトのシーケンスによって表現される。
【０００５】
リレーショナルデータベース管理システム（ＲＤＢＭＳ）は、ユーザアプリケーションによって提供されるクエリー動作を実行する。クエリー動作は、コンピュータのメインメモリに記憶されるデータベースレコードについて実行される。データへの高速アクセスの必要性のために、メインメモリは、一般的には、ランダムアクセスメモリ（ＲＡＭ）によって提供される。必要な高速アクセス時間を提供しながら、メインメモリを提供するために一般的に使用されるＲＡＭのタイプは揮発性記憶技術であり、これは、情報を記憶するための電力を要求する。また、ＲＡＭのコストが相対的に高いことは、合理的な大規模データベースに対しては、メインメモリが、データベースのすべてのテーブルのすべてのレコードを記憶するためには十分に大きくないことを意味する。
【０００６】
このように、データベースのテーブルは、低速ではあるが高容量として一般的に提供されるセカンダリメモリにも記憶され、これは、ハードディスクドライブのような不揮発性記憶装置である。
【０００７】
データベースのレコードを読み出すあるいは変更することが要求される場合、まず、レコードがメインメモリに存在するかどうかが判定される。特定のレコードがメインメモリに存在しない場合、そのレコードは、セカンダリメモリに配置され、処理のためにメインメモリにコピーされる。メインメモリがセカンダリメモリからコピーされる追加のレコードを記憶するために十分な空きスペース（領域）を有していない場合、セカンダリメモリからコピーされる追加のレコードを記憶するためのスペースを作成するために、メインメモリに記憶されるどのレコードを排出するべきかを判定する必要がある。メインメモリから排出するために選択されるレコードがメインメモリ内で変更されている場合、その変更されているレコードは、レコードがメインメモリから排出される場合にその変更が損失しないことを保証するために、セカンダリメモリへコピーされる。
【０００８】
データは、８ビットの集合でメモリに記憶され、それらはそれぞれバイトと呼ばれる。ディスクは、論理的には、固定サイズのグループの所定数のバイトで構成され、一般的には、これは、「ブロック」として知られる。ディスクからのデータを読み出し、また、ディスクへデータを書き込むための動作は、まとめてＩ／Ｏ動作として知られていて、また、一般的には、各Ｉ／Ｏ動作において整数ブロックで読み書きすることがより有効である。
【０００９】
データベースのテーブルに含まれるレコードは、ページと呼ばれるグループに記憶される。時には、データベースのページのサイズは、データベースが記憶されているハードディスクのブロックサイズに一致するように選択され、そうすることで、データベースのレコードは、個々のレコードではなくページ全体で、ハードディスクとメインメモリ間をコピーされ、これによって、メインメモリとセカンダリメモリとの間のレコード転送の効率性を最大にしている。つまり、特定のレコードが要求される場合、そのレコードを含むページがセカンダリメモリからメインメモリへコピーされる。そのレコードが変更される場合、ページ全体（その変更を含む）がメインメモリからセカンダリメモリへコピーされる。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ページがセカンダリメモリからメインメモリへ一旦コピーされる場合では、そのページに含まれるレコード群の１つだけが、あるいはいくつかのサブセットだけが変更されることが多い。それゆえ、セカンダリメモリへページ全体をコピーする必要性は、大量数の未変更のレコードも、セカンダリメモリへ書き込まれることになり、これは、非常に非効率である。
【００１１】
本発明の目的は、上述の課題の少なくとも１つを除去するあるいは軽減することである。
【課題を解決するための手段】
【００１２】
本発明の第１の態様に従えば、第１のメモリと第２のメモリを備えるシステムにおけるデータベースにデータを記憶する方法が提供される。この方法は、前記第２のメモリから第１のページを読み出すステップと、前記第２のメモリから読み出されるデータの少なくとも一部を変更して、前記データベースに記憶すべき変更されたデータを作成するステップと、前記変更されたデータを、前記第１のメモリのデータの第２のページに書き込むステップと、前記第２のページを、前記第１のメモリから前記第２のメモリへコピーするステップとを有し、前記第２のページのデータは、前記データが変更された順序に基づいて連続的に順序付けられている。
【００１３】
前記データの第１のページと前記第２のページは、複数のデータベースのレコードを含んでいても良い。前記変更されたデータは、１つ以上のデータベースのレコードを含んでいても良い。前記第２のページに書き込まれる前記変更されたデータは、前記第１のページのレコード群の内の１つの少なくとも一部に基づくデータを含んでいても良い。
【００１４】
データが変更される順序に基づく順序でデータ（例えば、データベースのレコード）を前記第２のページに記憶することによって、従来のログ取得処理とチェックポイント処理によって使用されるタイプのログファイルを維持する必要性が取り除かれる。
【００１５】
また、本明細書で説明される方法は、第１のメモリから第２のメモリへの要求されるページコピー動作の数を削減するという効果がある。例えば、ページを平均してＫ個のレコードに割り当てることができる場合、提案の発明を用いると、Ｋ個のレコードの変更は、第１のメモリから第２のメモリへコピーされるページは１つだけで済むようになる。近接ランダムアクセスパターンを有する大規模データベースを伴う従来のデータベース管理システムでは、平均して、Ｋ個のレコードの変更は、セカンダリメモリにはＫ個のページがコピーされることになることが予想される。
【００１６】
変更されたデータを第２のページに書き込むことは、第２のページに従前に書き込まれているデータに、その変更されたデータを付加することを含んでいても良い。
【００１７】
インデックスは、前記第２のメモリから読み出される前記第１のページのレコードを参照することができ、この方法は、前記変更されたデータが書き込まれる前記第２のページを参照するための前記インデックスのエントリを変更するステップを更に有していても良い。即ち、本発明の態様に従うデータベースに記憶されるレコードに対するインデックスが存在する場合、そのデータベースのレコードの変更は、そのレコードの新規の位置を示すために更新されるべき、変更されたレコードに対応するインデックスのエントリを要求することができる。例えば、インデックスがページ番号とそのページのオフセットを使用してレコードを参照する場合、上述のレコードの変更は、そのレコードに対応するインデックスのエントリが、そのページ内に記憶されるレコードにおける、その新規のページとそのオフセットを参照するために更新されることを要求することになる。
【００１８】
この方法は、更に、読み出された第１のページに含まれず、かつデータベースに記憶されるべき新規のデータを含む、新規のデータベースのレコードを第２のページに追加することを含んでいても良い。つまり、書き込むデータは、新規のレコードの書き込み、あるいは、既存のレコードの変更を表すデータの書き込みを含んでいても良い。どちらの場合でも、データは、その作成あるいは変更の順序で書き込まれる。
【００１９】
第２のページは、所定量のデータがその第２のページに書き込まれている場合に前記第２のメモリに書き込まれても良い。例えば、第２のページが一杯である（即ち、すべての自身のレコードが、新規に作成されたデータあるいは変更されたデータを含んでいる）場合、それは、第２のメモリを「フラッシュ」することができる。それにより、第２のページは、第１のメモリで空きにすることができる。それゆえ、取り消し（undo）／やり直し（redo）ログを保持する必要がない。なぜなら、第２のページが一杯になると、「フラッシュ」はオンザフライで実行することができるからである。
【００２０】
所定量のデータが前記第２のページに書き込まれる場合、更なる第２のページが作成されても良い。更なる第２のページに記憶されるデータは、データが変更される順序に基づいて連続的に順序付けられていても良い。
【００２１】
データの読出／書込動作に関して、前記第１のメモリは第１の関連アクセス時間を有していても良く、前記第２のメモリは第２の関連アクセス時間を有していても良い。前記第１のアクセス時間は前記第２のアクセス時間よりも遅くても良い。前記第１のメモリは揮発性メモリであっても良く、一方、前記第２のメモリは不揮発性メモリであっても良い。例えば、前記第１のメモリは、例えば、揮発性のランダムアクセスメモリ（ＲＡＭ）であっても良く、前記第１のアクセス時間は、前記第２のアクセス時間よりも１０００倍の桁で高速であっても良い。前記第２のメモリは、例えば、ハードディスクドライブであっても良い。
【００２２】
この方法は、更に、前記第２のメモリに記憶されている複数のページに含まれる同一データの内、旧式のバージョンと旧式でないバージョンを識別するために、前記複数のページを処理するステップと、前記旧式でないデータが隣接して配置されるように、前記複数のページの最初の１つのページ内にデータを再配置するステップと、前記複数のページの別ページから、前記複数のページの前記最初の１つのページへ旧式でないデータをコピーし、前記複数のページの前記最初の１つのページに旧式のデータを上書きし、前記複数のページの前記最初の１つのページに旧式でないデータを維持するステップとを備えていても良い。このような処理は、旧式のデータだけを有する、１つ以上の複数のページを得ることができる。旧式のデータだけを含むページは、前記第２のメモリのスペースを空きにするために「解放」することができる。
【００２３】
この方法は、トランザクションの開始と完了を示すデータを、前記第２のページに記憶するステップを更に備えていても良い。
【００２４】
この方法は、部分的に実行されるトランザクションを識別するために、トランザクションの開始と完了を示す前記データを処理するステップを更に備えていても良い。
【００２５】
この方法は、前記第２のページに記憶される前記データを読み出すステップと、前記第２のページから読み出されるデータを変更するステップと、前記読み出されたデータに影響を与えることなく、前記変更されたデータを、前記第２のページ、あるいは、更なる第２のページへ書き込むステップとを更に備えていても良い。
【００２６】
上述の方法に従ってデータベースにデータを記憶することによって、ログ処理が暗黙的に発生する。なぜなら、新規のレコードの挿入、あるいは既存のレコードの変更は、データが書き込まれる最終ページに新規のレコードを割り当てることになるからである。
【００２７】
本発明の態様は、任意の便利な形式で実現することができることが理解されるであろう。例えば、本発明は、適切なコンピュータプログラムによって実現されても良い。このコンピュータプログラムは、有形の搬送媒体（例えば、ディスク）あるいは無形の搬送媒体（例えば、通信信号）であっても良い、適切な搬送媒体で搬送されても良い。本発明の態様は、適切な装置を使用して実現されても良く、この適切な装置は、本発明を実現するように構成されているコンピュータプログラムを実行するプログラマブルコンピュータの形態をとることができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態が実現されるコンピュータシステムを示す図である。
【図２】上位レベルでの本発明の実施形態の動作を示すフローチャートである。
【図３】図１のコンピュータシステムのメインメモリに、データがどのようにして記憶されるかを示す図である。
【図４】データベースにレコードを追加するために実行される処理を示すフローチャートである。
【図５】データベースのレコードを変更するために実行される処理を示すフローチャートである。
【図６】図１のコンピュータシステムのメインメモリに記憶されるデータに、データのレコードの変更がどのように影響を与えるかを示す図である。
【図７】図１のコンピュータシステムのメインメモリに記憶されるレコードの全体ページを示す図である。
【図８】セカンダリメモリに記憶される冗長レコードを識別し抹消するために実行される処理を示すフローチャートである。
【図９ａ】データベースのページの位置に、図８の処理がどのように影響を与えるかを示す図である。
【図９ｂ】データベースのページの位置に、図８の処理がどのように影響を与えるかを示す図である。
【図１０】トランザクションの原子性を保証するために実行される処理を示すフローチャートである。
【発明を実施するための形態】
【００２９】
図１は、本発明の実施形態を実現するために構成されるコンピュータ１を示している。コンピュータ１は、ＲＡＭによって提供されるメインメモリ２と、ハードディスクドライブによって提供されるセカンダリメモリ３とを備える。プロセッサ４は、メインメモリ２の第１の論理部分５に記憶されている命令を読み出し、実行するように構成されている。これらの命令によって操作されるデータは、メインメモリ２の第２の論理部分６に記憶される。メインメモリ２の第１の論理部分５に記憶される命令は、とりわけ、プロセッサ４を制御して、メインメモリ２の第２の論理部分６とセカンダリメモリ３との間でデータをコピーする。
【００３０】
メインメモリ２の第１の論理部分５に記憶される命令は、セカンダリメモリ３に記憶されるリレーショナルデータベースの一部を形成する、メインメモリ２に記憶されるデータの処理を制御する。このリレーショナルデータベースのデータは、複数のページ７の形式で、メインメモリ２とセカンダリメモリ３の両方に記憶される。ここで、各ページは、データベースのレコードの形式で、所定量のデータを備えている。
【００３１】
特定のデータベースのテーブルの特定のレコードを効率的に配置することを、プロセッサ４によって実行されるユーザアプリケーションに可能にするために、メインメモリ２とセカンダリメモリ３のそれぞれは、インデックス８ａ、８ｂと呼ばれる追加のデータ構造を記憶する。インデックス８ａ、８ｂはそれぞれ、順序付け基準として、いくつかのレコードを使用する、順序付けされたレコードリファレンスのリストである。各データベースのテーブルは、そのデータベースのテーブルのすべてのレコードに渡る走査を可能するための、少なくとも１つのインデックスを有する。インデックスの順序付け基準は、テーブルの、「キー」と呼ばれる、非ヌル値の属性を使用して確立される。レコードがテーブルに挿入されるあるいはテーブルから削除される毎に、関連するテーブルのインデックスが更新される。レコードリファレンスは、インデックスを走査する場合に、各レコードへのアクセスを可能にするために、各インデックスセルに保存される。このリファレンスは、通常は、「ｒｉｄ」（レコード識別子）として知られており、そして、これは、ページ番号と、レコードが割り当てられる場合にページの先頭バイトからの内部バイトオフセットで構成される。例えば、レコードがページ２の第８バイト目に記憶される場合、ｒｉｄは、ページ２とオフセット８を特定することになる。
【００３２】
データは、所定サイズのページで、セカンダリメモリ３とメインメモリ２との間で転送される。プロセッサ４によって実行されるユーザアプリケーションによって要求される場合、データは、セカンダリメモリ３からメインメモリ２へ転送される。データは、永続的な記憶のために、メインメモリ２からセカンダリメモリ３へ転送される。
【００３３】
メモリ２に記憶されるページ７ａは、メインメモリ２からセカンダリメモリ３へコピーされているページである。メインメモリ２に記憶されているページ７ｂは、セカンダリメモリ３に記憶されているレコードに対する変更、及びセカンダリメモリ３に記憶されているレコードに追加されるべきレコードの少なくとも一方を記憶する。このように、ページ７ｂは、メインメモリ２からセカンダリメモリ３へコピーされる必要があるものである。ページ７ａは、セカンダリメモリ３へコピーされる必要はない（ページ７ａがメインメモリ２から削除されるとしても）、これは、これらのページのレコードは既にセカンダリメモリ３に記憶されていて、任意の追加あるいは変更がページ７ｂの１つに記憶されているからである。ページ７ｂは、以下では、ページログと呼ぶことにする。
【００３４】
図２は、データベースにデータを記憶するための、プロセッサ４によって実行される処理を示している。ステップＳ１で、レコード（既存のレコードに対する変更あるいは完全に新規のレコードを表している）は、データが現在追加されているページログのページ７ｂの末尾（最後）に記憶される。このページ７ｂが一杯である場合（即ち、更なるレコードを記憶するための空きスペースがない）、ステップ２で、ページは、永続的な記憶のためにセカンダリメモリ３へコピーされる。ページ７ｂのレコードは、これらのレコードが変更された及び作成されたのいずれか一方が行われた一時的な順序に従って順序付けされる。
【００３５】
図３は、関連するインデックス８ａに付随する、ページ７ｂの詳細を示している。上述のように、また、図３で示されるように、レコードが、それらの作成あるいは変更の順序で、ページ７ｂを構成するページログに追加される。つまり、ページ７ｂは、２０個のレコードを記憶する第１のページ９を備え、この２０個のレコードは、それらの作成あるいは変更の順序でページ９に追加されている。インデックス８ａは、上述の第１のページ９のレコードを参照している。但し、説明を簡単にするために、図３では、リファレンスのサブセットだけを示している。
【００３６】
ページ９が一杯になると、図４を参照して説明するように、それは、メインメモリ２からセカンダリメモリ３へコピーされ、新規のページが作成される。ステップＳ３で、ページ７ｂの１つのレコードへの挿入を要求するコマンドが処理される。この挿入は、新規のレコードの作成、あるいは既存のレコードの変更から生じ得る。ステップＳ４で、挿入対象のレコードを保持するために、ページのログの現在の「最終」ページにスペースがあるかどうかが判定される。スペースがある場合、処理は、ステップＳ５へ進み、そこで、レコードは、「最終」ページに挿入される。そのようなスペースがない場合、処理は、ステップＳ４からステップＳ６へ進み、そこで、新規のページが作成されて（図３では、ページ１０として）、挿入対象のレコードを保持する。そして、このページが、ページログの「最終」ページとなる。処理は、ステップＳ６からステップＳ５へ進み、そこで、レコードは、新規のページに追加される。
【００３７】
レコードが変更される場合に実行される処理について、図５及び図６を参照して説明する。図５をまず参照すると、ステップＳ７で、特定のレコードに対するリクエストが処理され、ステップＳ８で、特定のレコードが、メインメモリ２に現在常駐しているページに記憶されているかどうかを判定するためのチェックが実行される。このチェックは、対象のレコードが記憶されているページを識別するために、インデックス８ａと８ｂを使用して、そして、対象のレコードが記憶されているページがメインメモリ２に常駐しているかどうかを判定することによって実行することができる。対象のページがメインメモリ２に常駐している場合でない場合、ステップＳ９で、対象のページは、セカンダリメモリ３からメインメモリ２へコピーされる。対象のページを受け入れるための、メインメモリ２内の空きスペースが十分でない場合、メインメモリ２に現在常住している１つ以上のページ７ａが、十分な空きスペースを提供するためにメインメモリから排出される。排出するページ（群）７ａをどれにするかの選択は、ファーストインファーストアウト（ＦＩＦＯ）選択ポリシーに基づいていても良い。
【００３８】
図６は、ステップＳ９の処理後の、メインメモリ２の取り得る状態を示している。ページ１１がメインメモリ２に記憶されていることがわかる。ここで、ページ１１は、セカンダリメモリ３からコピーされているものである。このページ１１は、ステップＳ７でリクエストされているレコードを記憶する。これは、インデックス８ａのエントリ１２によって識別される。
【００３９】
対象のページがメインメモリ２に記憶されていて、また、上述の方法で対象のページのコピーの後、処理がステップＳ９からステップＳ１０へ進んでいる場合には、処理は、ステップＳ８から直接ステップＳ１０へ進む。ステップＳ１０で、対象のレコードが変更され、ステップＳ１１で、その変更された値を含むレコードの新規のコピーが作成される。変更された値を含むレコードは、ページログを作成するページ７ｂの１つに記憶されるものである。それゆえ、処理は、ステップＳ１１からステップＳ１２へ進み、そこで、変更された値を含むレコードを保持するために、ページログの「最終」ページにスペースがあるかどうかを判定するためのチェックが実行される。スペースがある場合、処理は、ステップＳ１３へ進み、そこで、変更された値を含むレコードがページログの「最終」ページに記憶される。ページログに変更された値を含むレコードが記憶されると、ステップＳ１４で、インデックス８ａが更新され、そうすることで、図６の破線で示されるように、インデックス８ａのエントリ１２は、ページログの「最終」ページの最終レコードを参照することになる。インデックス８ａのエントリ１２とページ１１のレコードとの間のリンクはこれ以上存在しない。
【００４０】
本発明のいくつかの実施形態では、ステップＳ１１で、インデックスのエントリの現在のｒｉｄは、ステップＳ１４でインデックスが更新される前に、レコードの「前値」フィールドに保存される。図１０を参照して後述するように、これは、例えば、クラッシュのイベント時に、変更をロールバックすることが可能となる。
【００４１】
ステップＳ１２で、ページログの「最終」ページに十分なスペースがないことが判定される場合、上述のステップＳ１３で処理を継続する前に、ステップＳ１５で、ページログの新規のページが作成されることが理解されるであろう。
【００４２】
上述の説明は、セカンダリメモリ３からコピーされるのではなく、ページログの一部を形成しないページに記憶されるレコードの変更に関するものである。いくつかの場合では、メインメモリ２に存在するページログのページに記憶されるレコードが、図５を参照して説明されるタイプの処理によって変更されても良いことが理解されるであろう。例えば、図７を参照すると、ページログを作成するページ７ｂのページ１４に記憶されるレコード１３への変更が要求される場合がある。このような場合、変更を表すレコード１５がページ１６に作成され、そして、インデックス８ａ、より詳しくは、インデックス８ａのエントリ１７が、レコード１５を参照するために更新される。
【００４３】
図７からは、ページ１４が一杯であることがわかる（即ち、レコードを記憶することができるスペースがこれ以上ない）。そのような場合、ページ１４が、メインメモリ２からセカンダリメモリ３へコピーされる。
【００４４】
上述の説明から、データベースのレコードへのすべての変更（新規のレコードの作成及び既存のレコードの変更を含む）が、ページログの現在の「最終」ページへレコードを追加することによって実行されることがわかる。このような場合、セカンダリメモリ３にすべての変更が正しく記憶されることを保証するために、ページログのページだけがメインメモリ２からセカンダリメモリ３へとコピーされる必要がある。
【００４５】
すべての変更が、ページログの現在の「最終」ページに記憶されるならば、他のページに記憶される従前のバージョンのレコード群は旧式のものとなるが、セカンダリメモリ３の記憶スペースを占有し続けることになる。セカンダリメモリ３の記憶容量は典型的には大きい（また、メインメモリ２の記憶容量も大きい）ならば、このことは必ずしも問題とならない。しかしながら、いくつかの実施形態では、旧式のレコード群を識別して、セカンダリメモリから削除するための処理が実現される。これについては、図８及び図９を参照して説明する。以下の説明では、ページ群は、別のページとの間で順序付けられていて、そして、かつ各ページは、自身の直後のページとのリンクを含んでいると想定する。
【００４６】
ステップＳ１６で、処理対象のページが選択される。以下の説明では、選択されたページはページ＃１として参照され、一方、その直後のページはページ＃２として参照される。いくつかの実施形態では、ステップＳ１６で、ページは、そのページ内で旧式となるレコード群（即ち、破棄されるレコード群）の比率に基づいて選択される。このような旧式のレコード群は、例えば、インデックス内の任意のエントリによって参照されないレコード群を識別するインデックスを処理することによって識別することができる。より詳細には、特定のページにおけるレコードとそのオフセットに対して、このインデックスは、そのインデックスがそのページとそのオフセットに対応するｒｉｄを有するエントリを含んでいるかどうかを判定するためにサーチされても良い。そのインデックスがそのような対応するｒｉｄを含んでいない場合、そのレコードは使用されない。選択的には、ステップＳ１６で、各ページと時間とを関連付け、そして、最も古いページを選択することが好ましい場合がある。上述の技術を使用してページが作成されると、ページは、一時的な順序で必然的に作成されることになり、最も古いページのそのような選択は比較的単純なものとなる。
【００４７】
ステップＳ１６でページを選択すると、処理は、ステップＳ１７からステップＳ２０によって定義されるループに進み、そこで、ページ＃１のすべてのレコードが順に処理される。ステップＳ１７で、ページ＃１内に処理対象のレコードが残っているかどうかを判定するためのチェックが実行される。残っている場合、ステップＳ１８で、処理が継続する。ステップＳ１８で、次のレコードが選択され、ステップＳ１９で、レコードが旧式であるかどうかを判定するためのチェックが実行される。そのような場合、処理はステップＳ１７に戻り、ループを継続する。ステップＳ１９で、旧式でないレコードが処理される場合、ステップＳ２０で、このレコードは、旧式のレコードを現在保持している、ページ内の最上位の位置へ移動される。このレコードは、自身の内容をページ内のより上位の位置へコピーすることによって移動され、これにより、そのレコードを保持しているスペースを空きスペースであることを示すようにすることができる。
【００４８】
ステップＳ１７で、ページ＃１内のすべてのレコード群が処理されていると判定される場合、処理はステップＳ２１へ進み、そこで、ページ＃１が任意の旧式のレコードあるいは空きスペース（即ち、ステップＳ２０で、旧式のレコードを現在のレコードと置換することによる結果として）を含んでいるかどうかを判定するためのチェックが実行される。ステップＳ２１で、ページ＃１が旧式のレコードあるいは空きスペースを含んでいると判定される場合、処理はステップＳ２１からステップＳ２２へ進み、そこで、ページ＃１の直後にあるページであるページ＃２に処理対象のレコードが残っているかどうかを判定するためのチェックが実行される。ページ＃２に処理対象のレコードが残っている場合、処理はステップＳ２２からステップＳ２３へ進み、そこで、ページ＃２の次のレコードが処理対象として選択され、その後、ステップＳ２４で処理を継続する。ここでは、選択されたレコードが旧式のものであるかどうかが判定される。選択されたレコードが旧式のものである場合、処理はステップＳ２４からステップＳ２２へ進む。ステップＳ２４で、選択されたレコードが旧式のものでないと判定される場合、選択されたレコードは、ページ＃１の最上位の空き位置（即ち、旧式のレコードを記憶する最上位の位置、あるいは最上位の空きスペース）へ移動される。そして、処理は、ステップＳ２５からステップＳ２１へと進む。
【００４９】
ステップＳ２２で、ページ＃２がこれ以上の処理対象のレコードを含んでいないと判定される場合、処理はステップＳ２２からステップＳ２６へ進む。同様に、ステップＳ２１で、ページ＃１が旧式のレコードあるいは空きスペースを含んでいないと判定される場合、処理はステップＳ２１からステップＳ２６へ進む。
【００５０】
ステップＳ２６で、ページ＃２で任意の現在のレコードを含んでいるかどうかが判定される。即ち、ページ＃２のすべてのレコードが旧式のものであるかどうか（特に、以下では、ページ＃１へレコードをコピーすることができるか）が判定される。ページ＃２のすべてのレコードが旧式のものである場合、ページ＃２は、有用な情報をこれ以上記憶することがないものとして、空きとすることができる。ステップＳ２７で、ページ＃２が空きとなり、ステップＳ２８で、ページ＃１が変更される。そうすることで、従前のページ＃２に続くページとして自身の次のページ（ページ＃３として参照される）を識別する。
【００５１】
ステップＳ２６で、ページ＃２が現在のレコードを含んでいると判定される場合、処理はステップＳ２６からステップＳ２９へ進み、そこで、ページ＃２は、上述の処理（即ち、図８の処理の目的のためにページ＃２はページ＃１となる）を使用して処理される。
【００５２】
従前の処理では、処理対象のページは、セカンダリメモリ３からメインメモリ２へコピーされる。上述の処理によって変更された任意のページは、永続的な記憶のためにセカンダリメモリ３へコピーされる。システムクラッシュのイベント時には、いくつかのレコードがページ間で複製されても良い。そのような複製を識別し、かつ除外することが要望される場合、それは、各レコードとログ番号等を関連付けることによって達成することができる。そのようなログ番号は、図５のステップＳ１１でレコードが作成する場合に初期化されても良い。
【００５３】
図８の処理は、旧式のレコードが時々削除されることを保証するように構成されている優先度の低い処理を使用して実現することができる。これによって、セカンダリメモリ記憶装置の過度の必要条件を回避する。
【００５４】
図９ａと図９ｂは、図８を参照して説明される処理前後のページ＃１とページ＃２の例を示している。
【００５５】
図９ａでは、ページ＃１は６個のレコードを記憶しているが、実際には、これらのレコードの内の３個のレコードは旧式のものである。ページ２は、２つの旧式でないレコード（レコード＃４とレコード＃５）だけを記憶している。図９ｂは、上述の処理後を示していて、レコード＃４とレコード＃５は、ページ＃１へ移動され、そうすることで、ページ＃２は旧式のレコードだけを記憶し、それゆえ、ページ＃２を空きにすることができる。
【００５６】
図９ａと図９ｂは、インデックス８がページ＃１とページ＃２のレコードを参照していることを示している。実行される処理はインデックスのエントリを補正する。例えば、図９ａのページ＃２の自身の位置でレコード＃４を参照するインデックスのエントリは、図９ｂのページ＃１の自身の位置でレコード＃４を参照する。
【００５７】
いくつかの実施形態では、現在のバージョンのレコードが直前のバージョンである場合、そのレコードは旧式のものであるとみなされない。これは、システムクラッシュのイベント時にロールバック動作を正しく実行させることを可能にするためである。例えば、レコードが旧式のものであると見なされない場合、そのレコードは、コミットされないトランザクションの一部となる。このトランザクションについては、以下で詳述する。
【００５８】
ＲＤＢＭＳでは、特定のレコードに影響を与えるいくつかの動作のセットは、原子性、一貫性、完全性及び耐久性（時には、「ＡＣＩＤ」属性と呼ばれる）を保証するような方法で実行される。一般論として、これは、動作のセットが自身で完全に実行されるべきであり、あるいは、不可能である場合には、完全に中断されるべきである。つまり、これらの動作のサブセットだけが実行され、その動作のその他の部分が実行されないことは生じるべきではない。完全に実行されなければならない動作のセットは、時には、トランザクションと呼ばれる。
【００５９】
周知のデータベース管理システムでは、トランザクションの原子性はログファイルを使用して保証される。つまり、既知のデータベース管理システムでは、トランザクションのコミットポイントは、そのトランザクションが正常に実行されて、トランザクションの結果がセカンダリメモリに記憶されるログファイルに記録されるポイントであり、そうすることで、トランザクションの結果を、システム故障のイベント時に再生することができる。一般的には、コミットされるトランザクションの一部を形成する動作がセカンダリメモリのデータベースに書き込まれる場合、クラッシュからＲＤＢＭＳのリカバリー時のログファイル全体を読み出すことを回避するために、チェックポイントのエントリがログファイルに追加される。
【００６０】
トランザクションが完全に実行される場合、コミット手順が実行され、そして、「トランザクションコミット完了」メッセージがユーザアプリケーションに送信されることで、トランザクションに含まれるすべての動作が正常に終了したことと、かつ動作の耐久性を通知する。そうでなければ、すべてのレコードの内容を、トランザクションの実行が開始される直前の値に戻すロールバック手順が起動される。ロールバック手順の終了時には、ユーザアプリケーションにも、トランザクションの実行の失敗が通知される。
【００６１】
本発明のシステムでは、トランザクションのコミットポイントは、そのトランザクションを行う動作のすべてがページログからセカンダリメモリに書き込まれていて、かつ、インデックスが新規のレコードを指し示すように更新されている時点のポイントである。
【００６２】
トランザクションの原子性が必要とされる場合、上述の方法は、単純なチェックポイント手順を提供するように変更されても良く、そうすることで、システムクラッシュからリカバリーする場合にすべてのデータベースのページを読み出すことを回避することができる。これは、トランザクションの開始と完了に関する情報を含む「フェイク」トランザクションレコードをページ内に含ませることによって達成することができる。より詳しくは、これらの「フェイクレコード」は、トランザクションの開始、トランザクションのコミット、及びトランザクションの中止を示している。例えば、「開始トランザクション（スタートトランザクション）」レコードはページログに挿入されて、「開始トランザクション」レコードに続く動作が単一のトランザクションの一部であり、そして、「コミット」レコードがそのトランザクションの最終動作の直後のページログに書き込むことができることを示すことができる。同様に、トランザクションが中止される場合、「中止された」レコードを、トランザクションが中止される前の直前の動作の直後のページログに書き込むことができる。
【００６３】
システムクラッシュが発生すると、対応するトランザクションのコミットレコードあるいはトランザクションのトランザクション中止レコードを持たない、トランザクションの開始レコードを識別することの逆の順序で、レコードが処理される。任意のこのようなトランザクションの開始レコードに遭遇すると、トランザクションの開始レコードに続くすべてのレコードが破棄され、そして、それらのレコードに関連付けられているインデックスのエントリが、レコードの「前値」フィールドを使用して、データベース内のそれらのレコードの従前の位置を示すように設定される。
【００６４】
図１０は、システムクラッシュのイベント時（例えば、電力不足のイベント時）に実行することができる処理の例を示していて、ここではデータがメインメモリ２から損失している。
【００６５】
ステップＳ３０で、セカンダリメモリ３に記憶されているページの最終ページ（つまり、システムクラッシュ前にセカンダリメモリにコミットされる最終ページ）が取得され、そして、現在のページとして設定される。ステップＳ３１で、そのページの最終レコードが現在のレコードとして設定される。ステップＳ３２で、現在のレコードが開始トランザクションレコードであるかどうかが判定される。現在のレコードが開始トランザクションレコードでない場合、処理はステップＳ３３へ進み、そこで、現在のレコードがコミットレコードあるいは中止レコードであるかどうかが判定される。
【００６６】
ステップＳ３３で、現在のレコードがコミットレコードあるいは中止レコードでないと判定される場合、処理はステップＳ３４へ進み、そこで、現在のページに従前のレコードが存在するかどうかが判定される。ステップＳ３４で、現在のページに従前のレコードが存在するかどうかが判定される場合、処理はステップＳ３５へ進み、任意の従前のページが存在するかどうか（即ち、現在のページがセカンダリメモリにコミットされた最初のページであるかどうか、これ以上、従前のページがないかどうか）が判定される、これ以上、従前のページが存在しないと判定される場合、処理はステップＳ３５から最後のステップＳ３８へ進む。
【００６７】
一方、ステップＳ３５で、更なる従前のページが存在すると判定される場合、処理は、ステップＳ３５からステップＳ３６へ進み、従前のページ（即ち、現在のページの直前のページ）が新規の現在のページとして設定される。そして、処理はステップＳ３６からステップＳ３１へ進む。
【００６８】
ステップＳ３４で、現在のページに従前のレコードが存在する場合、処理はステップＳ３７へ進み、そこで、現在のページの現在のレコードの前のレコードが新規の現在のレコードとして設定される。そして、処理は、ステップＳ３７からステップＳ３２へ進む。
【００６９】
ステップＳ３３で、現在のレコードがコミットレコードあるいは中止レコードであると判定される場合、これは、ステップＳ３８で、データベースに記憶されている任意のレコードをロールバックする必要がないことを示し、そして、処理を終了する。つまり、ステップＳ３３で、中止レコードあるいはコミットレコードに遭遇すると、これは、未完了のトランザクションの一部であるレコードはデータベースに存在しないことを示すことになる。
【００７０】
ステップＳ３２で、現在のレコードが開始トランザクションレコードであると判定される場合、処理はステップＳ３９へ進み、そこで、現在のレコードに続くすべてのレコード（即ち、開始トランザクションレコードの後にデータベースに追加されるレコード）がロールバックされる。そして、処理は、ステップＳ３９から最後のステップＳ３８へ進む。
【００７１】
図１０を参照して説明される処理は、暗黙的なチェックポイント手順を含んでいることが理解されるであろう。これは、処理は常にコミットフェイクレコードあるいは中止フェイクレコード時に終了するので、システムクラッシュからのリカバリー時にデータベース内の各レコードを処理する必要がない場合には、処理は常に終了するからである。それゆえ、一般的には、データベース内の各レコードを処理する必要がなくなる。
【００７２】
データベースとコンピュータという用語は、それらの任意の特定の実装に制限されず広く解釈されるべきであることが理解されるであろう。添付の請求項の範囲から逸脱することなく、本発明の様々な変更及び応用がなされることが、本発明の教示から当業者は理解するであろう。
【特許請求の範囲】
【請求項１】
第１のメモリと第２のメモリを備えるシステムにおけるデータベースにデータを記憶する方法であって、
前記第２のメモリから第１のページのデータを読み出すステップと、
前記第２のメモリから読み出される前記データの少なくとも一部を変更して、前記データベースに記憶すべき変更されたデータを作成するステップと、
前記変更されたデータを、前記第１のメモリのデータの第２のページに書き込むステップと、
前記第２のページを、前記第１のメモリから前記第２のメモリへコピーするステップとを有し、
前記第２のページのデータは、前記データが変更された順序に基づいて連続的に順序付けられている
ことを特徴とする方法。
【請求項２】
前記書き込むステップは、前記第２のページに書き込まれる前のデータに前記変更されたデータを追加する
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記データの第１のページと前記第２のページは、複数のデータベースのレコードを含み、
前記変更されたデータは、１つ以上のデータベースのレコードを含んでいる
ことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記第２のページに書き込まれる前記変更されたデータは、前記第１のページのレコード群の内の１つの少なくとも一部に基づくデータを含んでいる
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記第２のメモリから読み出される前記第１のページのレコードを参照するインデックスを備え、
前記変更されたデータが書き込まれる前記第２のページを参照するための前記インデックスのエントリを変更するステップを更に有する
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記読み出される第１のページに含まれず、前記データベースに記憶すべき新規のデータを備える、新規のデータベースのレコードを前記第２のページに追加するステップを更に有する
ことを特徴とする請求項３に記載の方法。
【請求項７】
所定量のデータが前記第２のページに書き込まれている場合に、更なる第２のページが作成され、
前記更なる第２のページに記憶されるデータは、前記データが変更される順序に基づいて連続的に順序付けされている
ことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
所定量のデータが前記第２のページに書き込まれている場合に、前記第２のページが前記第２のメモリにコピーされる
ことを特徴とする請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記第１のメモリは第１の関連アクセス時間を有し、
前記第２のメモリは第２の関連アクセス時間を有し、
データの読出／書込動作に関して、前記第１のアクセス時間は前記第２のアクセス時間よりも遅い
ことを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記第２のメモリに記憶されている複数のページに含まれる同一データの内、旧式のバージョンと旧式でないバージョンを識別するために、前記複数のページを処理するステップと、
前記旧式でないデータが隣接して配置されるように、前記複数のページの最初の１つのページ内にデータを再配置するステップと、
前記複数のページの別ページから、前記複数のページの前記最初の１つのページへ旧式でないデータをコピーして、前記複数のページの前記最初の１つのページの旧式のデータを上書きし、前記複数のページの前記最初の１つのページに旧式でないデータを保持するステップと
を有することを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
トランザクションの開始と完了を示すデータを、前記第２のページに記憶するステップを更に有する
ことを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
部分的に実行されるトランザクションを識別するために、トランザクションの開始と完了を示す前記データを処理するステップを更に有する
ことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記第２のページに記憶される前記データを読み出すステップと、
前記第２のページから読み出される前記データを変更するステップと、
前記読み出されたデータに影響を与えることなく、前記変更されたデータを、前記第２のページ、あるいは、更なる第２のページへ書き込むステップと
を更に有することを特徴とする請求項１乃至１２のいずれか１項に記載の方法。
【請求項１４】
請求項１乃至１３のいずれか１項に記載の方法を実行するように構成されているコンピュータ可読命令を記憶するコンピュータ可読媒体。
【請求項１５】
データを記憶するためのコンピュータ装置であって、
第１のメモリと、
第２のメモリと、
請求項１乃至１３のいずれか１項に記載の方法を実行するために、前記第１のメモリと前記第２のメモリと通信して、前記第１のメモリと前記第２のメモリそれぞれに対して、データの読み書きを行うように構成されているプロセッサと
を備えることを特徴とするコンピュータ装置。
【請求項１】
第１のメモリと第２のメモリを備えるシステムにおけるデータベースにデータを記憶する方法であって、
前記第２のメモリから第１のページのデータを読み出すステップと、
前記第２のメモリから読み出される前記データの少なくとも一部を変更して、前記データベースに記憶すべき変更されたデータを作成するステップと、
前記変更されたデータを、前記第１のメモリのデータの第２のページに書き込むステップと、
前記第２のページを、前記第１のメモリから前記第２のメモリへコピーするステップとを有し、
前記第２のページのデータは、前記データが変更された順序に基づいて連続的に順序付けられている
ことを特徴とする方法。
【請求項２】
前記書き込むステップは、前記第２のページに書き込まれる前のデータに前記変更されたデータを追加する
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記データの第１のページと前記第２のページは、複数のデータベースのレコードを含み、
前記変更されたデータは、１つ以上のデータベースのレコードを含んでいる
ことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記第２のページに書き込まれる前記変更されたデータは、前記第１のページのレコード群の内の１つの少なくとも一部に基づくデータを含んでいる
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記第２のメモリから読み出される前記第１のページのレコードを参照するインデックスを備え、
前記変更されたデータが書き込まれる前記第２のページを参照するための前記インデックスのエントリを変更するステップを更に有する
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記読み出される第１のページに含まれず、前記データベースに記憶すべき新規のデータを備える、新規のデータベースのレコードを前記第２のページに追加するステップを更に有する
ことを特徴とする請求項３に記載の方法。
【請求項７】
所定量のデータが前記第２のページに書き込まれている場合に、更なる第２のページが作成され、
前記更なる第２のページに記憶されるデータは、前記データが変更される順序に基づいて連続的に順序付けされている
ことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
所定量のデータが前記第２のページに書き込まれている場合に、前記第２のページが前記第２のメモリにコピーされる
ことを特徴とする請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記第１のメモリは第１の関連アクセス時間を有し、
前記第２のメモリは第２の関連アクセス時間を有し、
データの読出／書込動作に関して、前記第１のアクセス時間は前記第２のアクセス時間よりも遅い
ことを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記第２のメモリに記憶されている複数のページに含まれる同一データの内、旧式のバージョンと旧式でないバージョンを識別するために、前記複数のページを処理するステップと、
前記旧式でないデータが隣接して配置されるように、前記複数のページの最初の１つのページ内にデータを再配置するステップと、
前記複数のページの別ページから、前記複数のページの前記最初の１つのページへ旧式でないデータをコピーして、前記複数のページの前記最初の１つのページの旧式のデータを上書きし、前記複数のページの前記最初の１つのページに旧式でないデータを保持するステップと
を有することを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
トランザクションの開始と完了を示すデータを、前記第２のページに記憶するステップを更に有する
ことを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
部分的に実行されるトランザクションを識別するために、トランザクションの開始と完了を示す前記データを処理するステップを更に有する
ことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記第２のページに記憶される前記データを読み出すステップと、
前記第２のページから読み出される前記データを変更するステップと、
前記読み出されたデータに影響を与えることなく、前記変更されたデータを、前記第２のページ、あるいは、更なる第２のページへ書き込むステップと
を更に有することを特徴とする請求項１乃至１２のいずれか１項に記載の方法。
【請求項１４】
請求項１乃至１３のいずれか１項に記載の方法を実行するように構成されているコンピュータ可読命令を記憶するコンピュータ可読媒体。
【請求項１５】
データを記憶するためのコンピュータ装置であって、
第１のメモリと、
第２のメモリと、
請求項１乃至１３のいずれか１項に記載の方法を実行するために、前記第１のメモリと前記第２のメモリと通信して、前記第１のメモリと前記第２のメモリそれぞれに対して、データの読み書きを行うように構成されているプロセッサと
を備えることを特徴とするコンピュータ装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【公表番号】特表２０１３−５１９１３９（Ｐ２０１３−５１９１３９Ａ）
【公表日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願番号】特願２０１２−５５１５１２（Ｐ２０１２−５５１５１２）
【出願日】平成２２年２月９日（２０１０．２．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５１６０２
【国際公開番号】ＷＯ２０１１／０９８１１８
【国際公開日】平成２３年８月１８日（２０１１．８．１８）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【出願人】（５１１２２７４７３）ウニベルシダッド ポリテクニカ デ マドリッド (4)
【氏名又は名称原語表記】Ｕｎｉｖｅｒｓｉｄａｄ Ｐｏｌｉｔｅｃｎｉｃａ ｄｅ Ｍａｄｒｉｄ
【住所又は居所原語表記】Ｒａｍｉｒｏ ｄｅ Ｍａｅｚｔｕ， ７， Ｅ−２８０４０ Ｍａｄｒｉｄ， ＳＰＡＩＮ
【公表日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願日】平成２２年２月９日（２０１０．２．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５１６０２
【国際公開番号】ＷＯ２０１１／０９８１１８
【国際公開日】平成２３年８月１８日（２０１１．８．１８）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【出願人】（５１１２２７４７３）ウニベルシダッド ポリテクニカ デ マドリッド (4)
【氏名又は名称原語表記】Ｕｎｉｖｅｒｓｉｄａｄ Ｐｏｌｉｔｅｃｎｉｃａ ｄｅ Ｍａｄｒｉｄ
【住所又は居所原語表記】Ｒａｍｉｒｏ ｄｅ Ｍａｅｚｔｕ， ７， Ｅ−２８０４０ Ｍａｄｒｉｄ， ＳＰＡＩＮ
[ Back to top ]