(57)【要約】  再書込み能力が制限されている記憶媒体に記憶されているデータフィールドにおいては、頻繁に変更されるデータベースの処理が記憶セグメントの不等な摩耗につながる可能性がある。本発明は、データベースファイル（３１）を変更する方法に関し、この方法ではデータレコード（Ｄ１．．．Ｄ８）の書込みに最後に書込まれたセグメント（Ｓ２，Ｓ４）の後にある次に利用可能なセグメントを使用することによって最大限に分散的なセグメントの摩耗を保証する。本発明はまた読み出し方法に関する。さらに本発明は、バージョン番号を有するレコードを備えたデータベースファイルを包含するデータ担体に関する。
2007501480.tif 000002
【特許請求の範囲】
【請求項１】
セグメント（３２）に編成されており、且つ再書込み能力が制限されている記憶媒体（１２）に記憶されているデータベースファイル（３１）を変更する方法であって、
−前記データベースファイルにおいて、少なくとも１つのタイプのデータレコード（Ｄ１．．．Ｄ８）がそれぞれ書込まれる、所定のサイズおよび位置の少なくとも１つの専用の領域（４２，４３，４４）を確保するステップを有する、データベースファイル（３１）を変更する方法において、さらに、
−前記データベースファイルにおいて、データレコードが最後に書込まれた領域内のセグメントを最後に書込まれたセグメント（Ｓ２）として指示するステップと、
−特定のタイプのデータレコードが前記データベースに書込まれるべき場合には常に、前記特定のタイプの専用の領域において、前記最後に書込まれたセグメントの後にある次に利用可能なセグメントを書込みに使用して分散的な書込みを保証するステップとを有することを特徴とする、データベースファイル（３１）を変更する方法。
【請求項２】
前記データベースファイル（３１）における特定のタイプのデータレコード（Ｄ１．．．Ｄ８）の変更に使用し、
前記データベースファイルは特定のタイプの専用の領域を包含し、さらに、
−前記領域からデータレコードを読み出すステップと、
−読み出した前記データレコードを変更するステップと、
−前記特定のタイプのデータレコードが最後に書込まれた領域内のセグメントを指示する第１の書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記領域内の次のセグメント（Ｓ３）を指示するよう前記第１の書込みアドレス情報を進めるステップと、
−変更された前記データレコードを前記第１の書込みアドレス情報によって指示されたセグメントで始まるセグメントに書込むステップとを有する、請求項１記載の方法。
【請求項３】
前記データレコードはペイロードデータレコード（７３）であり、前記特定のタイプは「ペイロード」タイプであり、前記領域はペイロード領域（４４）であり、前記データベースファイルは付加的に制御領域（４２）を有し、また付加的に、
−前記ペイロードデータレコードに関するアドレス情報が前記制御領域内の制御ブロック（５３）に包含されている場合には、前記制御領域から前記制御ブロックを読み出すステップと、
−前記制御ブロック内のアドレス情報を更新し、前記第１の書込みアドレス情報に反映させるステップと、
−制御ブロックが最後に書込まれた前記制御領域内のセグメントを指示する第２の書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記制御領域内の次のセグメントを指示するよう前記第２の書込みアドレス情報を進めるステップと、
−更新された前記制御ブロックを前記第２の書込みアドレス情報によって指示されたセグメントに書込むステップとを有する、請求項２記載の方法。
【請求項４】
前記データベースファイル（３１）からのペイロードデータレコード（７３）の削除に使用し、前記データベースファイルは制御領域（４２）を包含し、さらに、
−削除されるべき前記ペイロードデータレコードに関連する情報を有する制御ブロック（５３）を前記制御領域から読み出すステップと、
−読み出した前記制御ブロックにおいて、削除すべき前記ペイロードデータレコードを削除されたものとしてマーキングし、変更された制御ブロックを取得するステップと、
−制御ブロックが最後に書込まれた前記制御領域内のセグメントを指示する書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記制御領域内の次のセグメントを指示するよう前記書込みアドレス情報を進めるステップと、
−進められた前記書込みアドレス情報によって指示されたセグメントに変更された前記制御ブロックを書込むステップとを有する、請求項１記載の方法。
【請求項５】
前記分散的な書込みを保証するステップは、
−未使用の空間を有する最後に書込まれたセグメント（Ｓ２，Ｓ４）の後にある次のセグメントを書込みアドレス情報が指示するまで該書込みアドレス情報を増分するサブステップと、
−増分により前記領域の最後を越えるセグメントを指示する書込みアドレス情報が生じた場合には、前記領域の開始に前記書込みアドレス情報をリセットするサブステップとを有する、請求項１から４までのいずれか１項記載の方法。
【請求項６】
前記セグメントのサイズは、前記記憶媒体（１２）における物理的なフォーマットで規定されているセクタまたはＥＣＣブロックのサイズの整数倍に対応する、請求項１から５までのいずれか１項記載の方法。
【請求項７】
前記セグメントは、セクタまたはＥＣＣブロックが位置合わせされるべき前記記憶媒体に割り当てられている、請求項６記載の方法。
【請求項８】
前記指示を、書込まれるべきデータレコードにバージョンカウント値を結合することによって実現し、該バージョンカウント値は各書込みに基づいて増分され、また所定の上限にあるモジューロを取り、バージョンカウントはデータベースに書込まれるデータレコードの一部として前記データベースファイルに書込まれる、請求項１から７までのいずれか１項記載の方法。
【請求項９】
少なくとも１つの前記領域（４２，４３，４４）のサイズは、前記セグメントの平均的な摩耗が等しくなるよう選択されている、請求項１から８までのいずれか１項記載の方法。
【請求項１０】
複数（ｚ）のドキュメントを包含するデータベースファイルにアクセスする並行した検索動作（２２．．．２６）を提供する方法において、
−前記データベースファイル内の前記ドキュメントについての特定の判定基準を検査する新たな検索動作の開始に基づき、アクティブな検索カウンタ（２７，２８）を増分するステップと、
−前記アクティブな検索カウンタが、１つまたは複数の検索動作がアクティブであり、且つドキュメント検索プロセス（２１）がまだ実行し終わっていないことを指示する値を有する場合には、連続的且つ周期的に前記データベースファイル内に包含されている前記ドキュメントを検索し、該ドキュメントに対していずれかのアクティブな検索動作を実施するドキュメント検索プロセスを開始するステップと、
−前記ドキュメント検索プロセスからドキュメントを受け取る、開始された新たな検索動作において、開始後に最初に受信したドキュメントの識別子を第１のドキュメントとして記憶し、受け取ったドキュメントに対して特定の判定基準を適用し、
−前記検索動作が前記第１のドキュメントを２回受け取ると該検索動作を終了し、前記アクティブな検索カウンタを減分するステップと、
−前記アクティブなカウンタがいずれの検索動作もアクティブでないことを指示する値を有する場合には、前記ドキュメントの検索プロセス（２１）を終了するステップとを有することを特徴とする、複数（ｚ）のドキュメントを包含するデータベースファイルにアクセスする並行した検索動作（２２．．．２６）を提供する方法。
【請求項１１】
前記検索動作を異なるソースから開始する、請求項１０記載の方法。
【請求項１２】
レコード（Ｄ１．．．Ｄ８）を包含するデータベースファイル（３１）が記憶されているデータ担体において、
各レコードは、単純に前記レコードが前記データ担体に書込まれた時点に関連する１つの特異なバージョン番号情報を包含することを特徴とするデータ担体。
【請求項１３】
後続のレコードが後続のバージョン番号を持たないレコードのみを有効と見なされるよう事前に規定されている、請求項１２記載のデータ担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は光学的な記録の分野、殊に光学的な記録媒体により課される制約の下でのメタデータを包含するデータベースの保守に関する。
【０００２】
背景技術
メタデータはデータに関するデータを表すものとして公知の術語である。メタデータは構造化されており、そのようなメタデータをデータベースに記憶することができる。将来のマルチメディアアプリケーションにおいてはメタデータのサイズが大きくなり、またメタデータが頻繁に変更されることが見込まれる；これらのメタデータは関連するデータと一緒に再書込み可能な光学的なデータ担体に記憶されることが見込まれる。頻繁に変更される「生きた」データベースの再書込み可能な光学的な媒体への記憶は、そのような媒体が各データセクタに対して制限的な回数の再書込みサイクルしか許容しないという事実によって妨げられている。データセクタに対する過剰な書込みサイクルはセクタを劣化させる。したがって本発明の課題は、再書込みサイクルの環境が制限されている状況に適合されたデータベース管理システムを提供することである。
【０００３】
本発明
本発明においては前述の課題および別の課題は：少なくとも１つのタイプのデータレコードをそれぞれ書込むための所定のサイズおよび位置の少なくとも１つの専用の領域をデータベースファイル内に確保するステップと、データベースファイルにおいて、データレコードが最後に書込まれた領域内のセグメントを最後に書込まれたセグメントとして指示するステップと、特定のタイプのデータレコードがデータベースに書込まれるべき場合には常に、特定のタイプの専用の領域において、最後に書込まれたセグメントの後にある次に利用可能なセグメントを書込みに使用して分散的な書込みを保証するステップとを有する、データベースファイルを変更する方法によって解決される。
【０００４】
この場合有利には、セグメントは先ずデータベース領域内のシーケンシャルな順序で書込まれる。データベース領域の最後のセグメントが書込まれた後には、次の書込み動作がデータベース領域の開始へと再びラップアラウンドされ、またそのデータベースにおいて発見された未使用または無効化されたいずれかのセグメントに書込みを行う。アクティブなセグメント、すなわち有効なデータを有するセグメントは変更または上書きされない。それらのセグメントを無効化することしかできない。変更された内容は書込み可能な次のセグメントの内の１つにのみ書込むことができる。つまり、データベース領域にわたる２回目のパスまたは連続的なパスにおいてさえも、シーケンシャルな書込みが可能な限り維持される。したがって可能な限り分散的な書込みが保証される。
【０００５】
本発明の別の実施形態によれば、データベースファイルにおける特定のタイプのデータレコードの変更は次のステップを有する：関連するデータベース領域からデータレコードを読み出すステップ；読み出したデータレコードを変更するステップ；特定のタイプのデータレコードが最後に書込まれた領域内のセグメントを指示する第１の書込みアドレス情報を取得するステップ；分散的な書込みの保証の一部として、未使用の空間を有する領域内の次のセグメントを指示するよう第１の書込みアドレス情報を進めるステップ；変更されたデータレコードを第１の書込みアドレス情報によって指示されたセグメントに書込むステップ。
【０００６】
データベースは種々の制御ブロックを含む制御領域を有することができる。典型的には、１つまたは複数の隣接するセグメントにおいてこれらの制御ブロックの１つのみが有効になる。そのような制御ブロックは典型的に頻繁な変更にさらされ、またデータベースにおけるペイロード領域内のドキュメントおよびセグメントの妥当性ならびにインデクス領域内のインデクスの妥当性に関する情報を有することができる。データベースの内容が変更されたときには少なくともデータ担体が取り出される前に、新たな制御ブロックを制御領域内の次のセグメントに書込む必要があるか、新たな制御ブロックが書込まれるべきである。このことは制御領域内の全てのセグメントについての制御ブロックに対する書込み動作または再書込み動作の回数を高める。未知のデータ担体が開かれている場合には、データ担体における固定の場所において永続的に変更されるセグメントアドレスを記憶することができないので、唯一の有効な制御ブロックが付属のバージョン番号を調べることによって発見されなければならない。
【０００７】
本発明のこの実施形態によれば、制御領域を含むデータベースファイルからのペイロードデータレコードの削除は次のステップを有する：削除されるべきペイロードデータレコードに関連する情報を有する制御ブロックを制御領域から読み出すステップ；読み出した制御ブロックにおいて、削除すべきペイロードデータレコードを削除されたものとしてマーキングし、変更された制御ブロックを取得するステップ；制御ブロックが最後に書込まれた制御領域内のセグメントを指示する書込みアドレス情報を取得するステップ；分散的な書込みの保証の一部として、未使用の空間を有する制御領域内の次のセグメントを指示するよう書込みアドレス情報を進めるステップ；進められた書込みアドレス情報によって指示されたセグメントに変更された制御ブロックを書込むステップ。
【０００８】
本発明の別の実施形態によれば、分散的な書込みの保証は、未使用の空間を有する最後に書込まれたセグメントの後にある次のセグメントを書込みアドレス情報が指示するまでこの書込みアドレス情報を増分するサブステップと、この増分が領域の最後を越えるセグメントを指示する書込みアドレス情報を発生させた場合には、領域の開始に書込みアドレス情報をリセットするサブステップとを有する。このことは、データベース領域にわたる２回目のパスまたは連続的なパスにおいてさえも可能な限りシーケンシャルな書込みの維持に寄与する。したがって可能な限り分散的な書込みが保証される。また、データベース作成時により大きな領域が設計されるようになればなるほど、この「ラップアラウンド」が生じることはいっそう少なくなり、したがって、その他の変化しないアプリケーションでは、領域のサイズとこの領域内のセグメントの平均的な再書込み回数との間の関係は逆になる。
【０００９】
本発明は、有利には可能な限り同一水準にされるべき各データセクタに対する複数回の再書込み動作を保証する、一般的なデータベースフォーマットならびにデータ担体書込みストラテジに関する。このようにして、データ担体の特定のセクタの劣化は回避される。本発明のシステムは、再書込みサイクルの回数が制限されており、またハードディスクに比べればトラックシーク時間が長い光学的なデータ担体の固有の特性に適合されているという特徴を有する。幾つかの媒体に関しては、約１０００回の再書込みサイクルを想定することが現実的であり、このような回数は使用時の再書込みストラテジを考慮すれば多い回数であり、また通常の使用の場合には到達しないであろう回数である。
【００１０】
図面
本発明の実施例を図面に示し、以下の記述においてさらに詳細に説明する。
【００１１】
図面において：
図１は本発明による領域コンセプトを表す実施例を示し、
図２は本発明により管理されるべき、単一のデータベースにアクセスする種々の並行的な検索動作のタイミングチャートを示し、
図３は本発明によるデータベースの低いレベルでの分割を示し、
図４はデータベースのヘッダが強調されているデータベースファイルを示し、
図５は本発明によるデータベースファイル内の制御領域およびその構造を示し、
図６は本発明によるデータベースファイル内のインデクス領域およびその構造を示し、
図７は本発明によるデータベースファイル内のペイロード領域およびその構造を示し、
図８は本発明によるドキュメント書込みストラテジを表すセグメントの内容を示し、
図９は本発明によるドキュメント編集および削除ストラテジを表すセグメントの内容を示し、
図１０は本発明によるペイロードセグメントの書込みストラテジを表すセグメントの内容を質的に示す。
【００１２】
実施例
本発明の実施形態は、データベース用の利用可能な記憶空間の事前に割り当てられた隣接する領域を使用する。このデータベースはデータ担体のファイルシステムに依存する単純なファイルまたはパーティションであってよい。このデータベースに対する唯一の要求はセグメントで編成することができ、またランダムに読み出しアクセスおよび書込みアクセスできることである。
【００１３】
静的なデータベース情報、例えば全ての領域のサイズ、セグメントサイズおよびバージョンなどを包含する最初のセグメントを除いて、データベースファイルの他の全てのセグメントは種々の異なるデータベース領域、例えば制御領域、インデクス領域、ペイロード領域にグループ化されている。各領域のサイズはアプリケーション固有であり、且つデータベースファイル作成時に指定される。有利にはデータベースファイルの各領域を一定のサイズのセグメントに編成することができ、このような一定のサイズは適切にＥＣＣブロックサイズの倍数にすべきである。誤り訂正符号またはＥＣＣはデータ担体における読み出し可能な最小のブロックを決定する。したがってセグメントの境界にＥＣＣブロックの境界を割り当てることも有利である。アプリケーションは、各領域内の一定ではあるが異なるセグメントサイズを使用することが有利である所にそれぞれ存在することができる。
【００１４】
ドキュメントまたはレコードとも称されるペイロードデータはペイロード領域に記憶される。この領域内のセグメントは１つまたは複数のドキュメントを記憶することができる。ドキュメントはそのサイズにより、またはほぼ一杯のセグメント内の最後の自由な空間が使用されることにより、１つまたは複数のセグメントにわたり広がっていてもよい。完全なドキュメントのみが付加、検索または無効化／「除去」される。「除去」されるドキュメントは実際にデータ担体上で除去されるわけではない。何故ならばセグメントへの付加的な書込みアクセスによりそのような除去が生じるからである。むしろ、ドキュメントは制御ブロックにおいて単に無効化される。セグメント内のあらゆる未使用の部分を、例えば完全に未使用のセグメントの数が小さくなるまで未使用に保つことができる。続いて、部分的に無効化されたセグメント内の残りのドキュメントを有利には集めて、一種の不要部分の整理のように新たなセグメントに置くことができる。このようにして古いセグメントが新たなドキュメントのために利用可能になる。
【００１５】
図１は、この種の書込みストラテジに関して、本発明によるデータベースが記憶空間１２における異なる領域１１に分割されていることを示しており、これらの領域１１は連続的に書込まれ、また領域の全てのセクタが書込まれた場合にのみ再書込みも行われる。その間に幾つかのセクタが未使用とマーキングされたとしても、それらの未使用のセクタは即座に再利用されるのではなく、領域１１の他の全ての未使用のセクタ１３が使用された後にのみ再利用される。ラップアラウンドの後には、全ての自由なセクタが上記と同じやり方で処理される。このようにして、セクタ毎にほぼ等しく且つ少ない回数の再書込みサイクルを達成することができる。
【００１６】
本発明のシステムは、光学的なデータ担体の固有の特性に適合されているにもかかわらず、やはり問題なくハードディスクへの記憶にも使用できることを言及せねばならない。
【００１７】
図２は並列的な検索動作を実行するやり方を示す。検索動作２２，２３，２４，２５，２６のいずれかがアクティブである限り、１つの検索プロセス２１が実行されており、このプロセスは永続的且つ周期的にデータベース内の全てのドキュメント１，．．．，ｚを物理的な順序で読出し、アクティブな全ての検索動作の検索プロセッサを各ドキュメントに対して１回呼び出す。検索プロセスを開始する、または既に実行されている検索プロセスに加わる新たな検索動作はそれぞれ最初のドキュメントの位置を記憶し、この検索プロセスは１回ラップアラウンドした後に同一のドキュメントまたは後続のドキュメントに再び到達した後にのみその活動を開始および終了する。検索プロセス２１はアクティブな検索動作の数２７，２８が０に戻ったとき、すなわちもはやアクティブな検索動作が存在しない場合に終了する。この方法を用いることにより、全ての検索動作を提供するためのデータ担体へのアクセス回数は最小になり、また付加的に、物理的な順序でドキュメントがトラバースされるので、連続的なドキュメント読み出し動作間に含まれるジャンプ時間も最小にされる。
【００１８】
要約すれば、検索動作はデータベースファイル内のペイロードの物理的な順序に関して最適化されている。多数の検索動作の並列的な実行でさえも可能である。このことはマルチユーザアプリケーションを可能にする。基礎となるファイル構造は、全てのセクタに対する非常に制限的でほぼ同数の再書込みサイクルを考慮して、光学的な記録媒体に関して最高のパフォーマンスを保証する。
【００１９】
誤り訂正符号ブロックは光学的なデータ担体において読み出しおよび書込み可能な最小のセグメントである。データベースファイルは有利には、関連するファイルシステムのもとで１つのファイルとして編成されており、これらのＥＣＣブロックの１つの連続的な範囲からなる１つの領域を占有するように設計されている。データ担体においては別のファイルは必要とされない。このデータベースファイルの内部は本発明のシステムによって管理され、本発明の再書込みストラテジを支援する特別なファイルシステムの特徴には依存しない。この設計により、記憶されているデータの細分化を決定および制御することができる。データベースファイルのサイズをデフォルト値にセットすることができ、また必要であれば調節することができる。データベースファイルは何らかの精巧な動作が必要とされることを回避するには十分な大きさであるべきである。さもなければ最悪の場合データベース全体の再編成が必要となる恐れがある。他方では、別のアプリケーションがデータベースファイルの外でデータ担体上により多くの空間を必要とする状況では、データベースのサイズを低減するためのオプションも存在する。
【００２０】
図３は、データベースファイル３１の最下位のレベルにおいて、このデータベースファイル３１が一定サイズのセグメント３２に分割されていることを示している。有利にはセグメントサイズはＥＣＣサイズの整数倍である。セグメントサイズはデータベースファイルの作成時に規定する必要があり、データベースの生存期間中は変更することができない。セグメントサイズを変更する唯一のやり方では、全てのドキュメントが現在のデータベースファイルから適切に設計された新たなデータベースファイルへと完全に転送されることになる。
【００２１】
データ担体の再書込みサイクルの回数が制限されているために、セグメントを変更することができないという規則が存在する。換言すれば、セグメントが読み出され、変更されてデータ担体上の同一の位置に再び記憶されることは決してない。むしろ、セグメントを完全にまたは部分的に無効化することしかできない。変更された内容はその本来の位置において無効化されなければならず、またその後は通常の場合別の位置である書込み可能な次のセグメントに書込まれなければならない。ドキュメントがデータベースファイルに付加されている間、セグメントをその容量が完全に使用されるまで書込みキャッシュすることができる。
【００２２】
図４は、連続するセグメントの領域４１，４２，４３，４４にグループ化されているセグメントを示す。これらの領域の内の１つはただ１つのセグメントからなり、またデータベースの生存期間中には変更されないデータベースの静的な情報を包含するデータベースヘッダ４１のために使用される。後続の領域４２，４３，４４内のセグメントは、各領域内のセグメントに対してほぼ同数の再書込みサイクルを達成するために、データベースファイル内の場所に従い循環的な順序で使用される。データベースヘッダは以下の情報を包含することができる：
・データベースファイルを容易に識別するための開始コード
・バージョン番号
・セグメントサイズ
・制御領域サイズ
・インデクス領域サイズ
・ペイロード領域サイズ
【００２３】
ヘッダセグメント４１は通常の場合、データベースの生存期間中に一度だけ書込まれる。ヘッダセグメントは、例えばセグメントのサイズ、領域のサイズまたは内部データフォーマットの変更によりデータベースヘッダフィールドの内の１つが変更されるように再編成された場合にのみ変更される必要がある。このことは関連する仕様のアップデートに基づき行われる可能性がある。
【００２４】
所定の場合には図５に示されているように、別個の制御領域４２内の制御ブロックを使用することは有利である。データベースのペイロード用のセグメントが種々のドキュメントを包含する状況、またこれらのドキュメントの内の１つを削除する必要がある状況を考察する。セグメントを変更することができないという規則に基づき、この削除動作を管理するための２つのアプローチが存在する。セグメント全体の内容を読み出し、変更し、書込み可能な次のセグメントに再書込みする必要があるか、何らかの制御データを使用して、ペイロードデータとは別個に保持する必要がある。この制御データは削除されたドキュメントを本来のセグメント内の無効なデータとしてマークすることができる。第１のアプローチは細分化の少ないデータベースを生じさせることができるが、例えばセグメント内の最後のドキュメントが１つ以上のセグメントにわたり広がる場合には、これら全てのセグメントを読み出して、変更して同様に最初のセグメントと同様に再書込みする必要がある。したがって有利には第２のアプローチが使用され、この第２のアプローチはデータベースの性能を改善する。必要とされる制御データをセグメント全体が無効化される前に何度も変更することができるので、制御データは制御領域４２に記憶される。制御領域は１つまたは複数の制御ブロック５３を包含し、また頻繁な変更に適合されている。
【００２５】
制御ブロック５３はペイロードまたはインデクスを包含するセグメントに関する情報の起こりうる変更のためのコンテナである。制御ブロックデータは典型的には、データベースが開かれており、またこのデータベースが閉じられるまでメモリ内に保持できる場合にメモリにロードされる。制御ブロックはこの制御ブロックが変更された場合のみデータ担体に再び書込まれなければならない。安全性の理由により、システムエラーの場合のデータ損失に対する障害許容力を改善するために、変更された制御ブロックを１回以上記憶することができる。データベースに関する次の情報を制御ブロックに記憶することができる：
・ヘッダ５４
・インデクス領域およびペイロード領域内の最後に書込まれたセグメントに関する参照
・ペイロードセグメントおよびインデクスセグメントについての妥当性フラグ
・利用可能且つ有効なインデクスに関する情報のようなインデクス制御データ５５
・ペイロードセグメントにおけるドキュメントについての妥当性フラグのようなペイロード制御データ５６または最初の部分もしくは部分の数を指示するフラグのような分割されたドキュメントに関する情報。
【００２６】
また図５は、データ担体の同一の位置への制御ブロック５３の書込みを回避するために、制御ブロックの全ての新しいバージョンが制御領域４２内の１つまたは複数の異なるセグメントに書込まれる様子を示す。暗黙的な規則として、最後に書込まれた制御ブロックのみが有効であると見なされる；このために制御ブロックの全ての新しいバージョンは先行して使用されたバージョンに比べ増分されているバージョン番号を有することができ、その結果最後に書込まれた制御ブロックを制御領域内の制御ブロックのバージョン番号を調べることにより識別することができる。制御領域４２内の全てのセグメントが書込まれた後にのみ、アドレスのラップアラウンドによって最初のセグメントが再び使用され、その結果ほぼ同数の再書込みサイクルがこの領域においても保証されている。もちろん、固定のワード長のデータフィールドに記憶されているバージョン番号を用いる場合には、制御ブロックが十分な頻度でアップデートされると場合によってはこのバージョン番号もラップアラウンドする。しかしながら、制御ブロックの前述の性質に基づき、連続的な制御ブロックの書込みは制御ブロック領域内では常に厳密に周期的となる。したがって、有効な制御ブロックを認識するために、制御ブロック領域が保持することができる制御ブロックの数の素因数よりも大きいか素因数ではない値の範囲からバージョン番号が使用されることを保証すれば十分である。制御領域内の後続の制御ブロックのモジューロが、バージョン番号値領域内の後続のバージョン番号のモジューロを持たないところでは有効な制御ブロックが唯一の制御ブロックであることによって有効な制御ブロックを認識することができる。
【００２７】
制御ブロック５３は１つ以上の隣接するセグメントにわたって広がっていてもよい。有利には制御ブロックが位置合わせされたセグメントに記憶される。すなわち全ての制御ブロックは先行する制御ブロックの最後のセグメントに続くセグメントの開始において始まる。このことは、先行する制御ブロックの最後のセグメントのエンドポイント内に未使用の空間が存在していてもよく、またその空間が未使用のまま残されることを暗示している。セグメントの位置合わせは最後に書込まれたセグメントの識別、したがって現在有効な制御ブロックの識別を容易にする。制御領域４２の残りのセグメントが完全に新たな制御ブロックを記憶するには十分でない場合、制御ブロックはこれらの残りのセグメントを使用し、制御領域の開始へと続く。すなわち制御ブロックは制御領域の境界をラップアラウンドすることができる。
【００２８】
図６はインデクス６２のデータを記憶することができるインデクス領域４３を示す。インデクスのフォーマットは用途固有であり、また制御ブロック５３内の対応するインデクスタイプフィールドによって決定することができる。限定的な再書込みサイクルの制約の下での細分化を阻止するために、インデクス６２をデータ担体上で直接変更することはできない。何故ならば、変更されたインデクス部分を上書きすることができないからである。したがって有利には各インデクスが連続するセグメントの厳密に１つのシーケンスを占有すべきである。アプリケーションは有利には全体のインデクスのみを読出しおよび書込みすべきであり、これらのアプリケーションは完全なインデクスをメモリに保持することができる。
【００２９】
図７は、典型的にデータファイルの大部分を専有するペイロード領域４４を示す。ペイロードセグメント７１と称されるこの領域内の全てのセグメントは同一のフォーマットを有していてもよい。各ペイロードセグメントは、使用されるのであれば、ヘッダ７２および１つまたは複数のドキュメント７３またはドキュメントの一部でさえも包含することができる。
【００３０】
図８は本発明によるドキュメント書込みストラテジを示す。概念上ここでは、実施例のセグメントＳｎ内のドキュメントＤ１からＤ５に関して示されているように、新しい各ドキュメントＤ１．．．Ｄ８は先行するドキュメントの直ぐ後ろに続くペイロードセグメントに記憶されている。目下のセグメントにおける自由な空間が次のドキュメントにとって十分でない場合には、セグメントがパディングバイトでもって充填され、ドキュメントは次のセグメントＳｎ＋１に書込まれる。図８におけるドキュメントＤ７のようにドキュメントが１つのセグメントよりも大きい場合、またはドキュメントがセグメントの残りの空間に適合しない場合には、セグメントＳｎ＋１からＳｎ＋３におけるように、ドキュメントは隣接するセグメントの境界を越えて広がることもできる。セグメントの残りの空間を、分割されているドキュメントの代わりにパディングバイトＰでもって充填してもよい。このことはドキュメントの分割の回数を低減させ、またこれにより不要部分の整理が容易にされ、短いセグメントグループの確率が高まる。しかしながらまた、遊びとして公知でもある未使用のペイロード空間の量も増加させる。各ペイロードセグメントのヘッダデータＨはセグメント内のドキュメントに関する情報、例えば開始アドレスまたはサイズを包含することができる。
【００３１】
図９はドキュメント編集および削除ストラテジを示す。セグメントＳｎ．．．Ｓｍを原位置で変更することはできないが、無効化のみは行われるという規則はドキュメントにも影響を及ぼす。図８と同じ状況から出発して、セクタＳｎに示されているように、ドキュメントＤ１の削除およびドキュメントＤ３の編集が示されている。ドキュメントＤ１は、記憶されているペイロードセグメント内のデータを単に無効化することによって「削除」される。このことは図示していない制御ブロック内のフラグによって行われるので、セグメントＳｎ自体が変更される必要はない。ドキュメントＤ３を編集するためには、その本来のバージョンがメモリに読み出され、メモリ内で変更され、実施例においてはセグメントＳｍである書込み可能な次のセグメントに新しいドキュメントのように記憶されなければならない。本来のドキュメントは「削除」の場合と同様に無効化される。
【００３２】
図１０は本発明によるペイロードセグメント書込みストラテジを示す。異なる連続的な時間ｔで、ペイロード領域全体が図面の各「線」として示されている。セグメントの状態はＳ１が「使用されている」を表し、Ｓ２が「最後に書込まれて使用されている」を表し、Ｓ３が「使用されていない」を表し、またＳ４が「最後に書込まれたが既に無効化されている」を表す。基本的に、ペイロードセグメントはペイロード領域における場所に応じて循環的な順序で書込まれる。「ｔ＝ｔ１」と表されている第１の線は、この意味において連続的に充填されているデータベースを示す。「ｔ＝ｔ２」に示されているように、先行する幾つかのセグメントが仮に無効化されたとしても、「ｔ＝ｔ３」で示されているように、次のセグメントデータはそれにもかかわらず最後に書込まれたセグメントＳ２，Ｓ４に続くセグメントに書込まれる。ペイロード領域の最後に達した場合には、「ｔ＝ｔ５」に示されているように、書込みプロセスはラップアラウンドし、領域の最初の未使用のセグメントにおいて始まる。後続の書込み動作に関しては、次の自由なセグメントが「ｔ＝ｔ６」に示されているように使用される。
【００３３】
次の自由なセグメントが使用されるべきではない１つの例外が存在する：セグメント境界にわたり広がっているドキュメントを記憶するためには、１つ以上の連続するセグメントを使用する必要がある。この場合、そのような記憶にとって十分な大きさではない次の自由なセグメントグループは、使用可能なグループが発見されるまでスキップされなければならない。
【００３４】
択一的に、セグメントよりも小さいにもかかわらず、ドキュメントが偶然にもセグメント境界にわたり広がっているように記憶される特別な事例も存在する。そのようなドキュメントを次の単一の自由なセグメントの開始に記憶することができる。目下のセグメントの残りの自由な空間は未使用のまま残される。
【図面の簡単な説明】
【００３５】
【図１】本発明による領域コンセプトを表す実施例。
【図２】本発明により管理されるべき、単一のデータベースにアクセスする種々の並行的な検索動作のタイミングチャート。
【図３】本発明によるデータベースの低いレベルでの分割。
【図４】データベースのヘッダが強調されているデータベースファイル。
【図５】本発明によるデータベースファイル内の制御領域およびその構造。
【図６】本発明によるデータベースファイル内のインデクス領域およびその構造。
【図７】本発明によるデータベースファイル内のペイロード領域およびその構造。
【図８】本発明によるドキュメント書込みストラテジを表すセグメントの内容。
【図９】本発明によるドキュメント編集および削除ストラテジを表すセグメントの内容。
【図１０】本発明によるペイロードセグメントの書込みストラテジを表すセグメントの内容。
【図１】
2007501480.tif 000003
【図３】
2007501480.tif 000004
【図４】
2007501480.tif 000005
【図５】
2007501480.tif 000006
【図６】
2007501480.tif 000007
【図７】
2007501480.tif 000008
【図８】
2007501480.tif 000009
【図９】
2007501480.tif 000010
【図１０】
2007501480.tif 000011
【図２】
2007501480.tif 000012
【手続補正書】
【提出日】平成17年5月19日(2005.5.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
セグメント（３２）に編成されており、且つ再書込み能力が制限されている記憶媒体（１２）に記憶されているデータベースファイル（３１）を変更する方法であって、
−前記データベースファイルにおいて、少なくとも１つのタイプのデータレコード（Ｄ１．．．Ｄ８）がそれぞれ書込まれる、所定のサイズおよび位置の少なくとも１つの専用の領域（４２，４３，４４）を確保するステップと、
−前記データベースファイルにおいて、データレコードが最後に書込まれた領域内のセグメントを最後に書込まれたセグメント（Ｓ２）として指示するステップと、
−前記データベースに書込まれるべき特定のタイプの特定のデータレコードを、前記特定のタイプの専用の領域における前記最後に書込まれたセグメントの後にある次に利用可能な１つまたは複数のセグメントに書込むステップとを有する、データベースファイル（３１）を変更する方法において、さらに、
−書込みの間に前記領域の最後に達した場合は常に、前記領域の最初に利用可能なセグメントにおいて書込みを継続するステップを有することを特徴とする、データベースファイル（３１）を変更する方法。
【請求項２】
前記データベースファイル（３１）における特定のタイプのデータレコード（Ｄ１．．．Ｄ８）の変更に使用し、
前記データベースファイルは特定のタイプの専用の領域を包含し、さらに、
−前記領域からデータレコードを読み出すステップと、
−読み出した前記データレコードを変更するステップと、
−前記特定のタイプのデータレコードが最後に書込まれた領域内のセグメントを指示する第１の書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記領域内の次のセグメント（Ｓ３）を指示するよう前記第１の書込みアドレス情報を進めるステップと、
−変更された前記データレコードを前記第１の書込みアドレス情報によって指示されたセグメントで始まるセグメントに書込むステップとを有する、請求項１記載の方法。
【請求項３】
前記データレコードはペイロードデータレコード（７３）であり、前記特定のタイプは「ペイロード」タイプであり、前記領域はペイロード領域（４４）であり、前記データベースファイルは付加的に制御領域（４２）を有し、また付加的に、
−前記ペイロードデータレコードに関するアドレス情報が前記制御領域内の制御ブロック（５３）に包含されている場合には、前記制御領域から前記制御ブロックを読み出すステップと、
−前記制御ブロック内のアドレス情報を更新し、前記第１の書込みアドレス情報に反映させるステップと、
−制御ブロックが最後に書込まれた前記制御領域内のセグメントを指示する第1の書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記制御領域内の次のセグメントを指示するよう前記第２の書込みアドレス情報を進めるステップと、
−更新された前記制御ブロックを前記第２の書込みアドレス情報によって指示されたセグメントに書込むステップとを有する、請求項１記載の方法。
【請求項４】
前記データベースファイル（３１）からのペイロードデータレコード（７３）の削除に使用し、前記データベースファイルは制御領域（４２）を包含し、さらに、
−削除されるべき前記ペイロードデータレコードに関連する情報を有する制御ブロック（５３）を前記制御領域から読み出すステップと、
−読み出した前記制御ブロックにおいて、削除すべき前記ペイロードデータレコードを削除されたものとしてマーキングし、変更された制御ブロックを取得するステップと、
−制御ブロックが最後に書込まれた前記制御領域内のセグメントを指示する書込みアドレス情報を取得するステップと、
−分散的な書込みの保証の一部として、未使用の空間を有する前記制御領域内の次のセグメントを指示するよう前記書込みアドレス情報を進めるステップと、
−進められた前記書込みアドレス情報によって指示されたセグメントに変更された前記制御ブロックを書込むステップとを有する、請求項１記載の方法。
【請求項５】
前記セグメントのサイズは、前記記憶媒体（１２）における物理的なフォーマットで規定されているセクタまたはＥＣＣブロックのサイズの整数倍に対応する、請求項１から４までのいずれか１項記載の方法。
【請求項６】
前記セグメントは、セクタまたはＥＣＣブロックが位置合わせされるべき前記記憶媒体に割り当てられている、請求項５記載の方法。
【請求項７】
前記指示を、書込まれるべきデータレコードにバージョンカウント値を結合することによって実現し、該バージョンカウント値は各書込みに基づいて増分され、また所定の上限にあるモジューロを取り、バージョンカウントはデータベースに書込まれるデータレコードの一部として前記データベースファイルに書込まれる、請求項１から６までのいずれか１項記載の方法。
【請求項８】
少なくとも１つの前記領域（４２，４３，４４）のサイズは、前記セグメントの平均的な摩耗が等しくなるよう選択されている、請求項１から７までのいずれか１項記載の方法。
【請求項９】
複数（ｚ）のドキュメントを包含するデータベースファイルにアクセスする並行した検索動作（２２．．．0.26）を提供する方法において、
−前記データベースファイル内の前記ドキュメントについての特定の判定基準を検査する新たな検索動作の開始に基づき、アクティブな検索カウンタ（２７，２８）を増分するステップと、
−前記アクティブな検索カウンタが、１つまたは複数の検索動作がアクティブであり、且つドキュメント検索プロセス（２１）がまだ実行し終わっていないことを指示する値を有する場合には、連続的且つ周期的に前記データベースファイル内に包含されている前記ドキュメントを検索し、該ドキュメントに対していずれかのアクティブな検索動作を実施するドキュメント検索プロセスを開始するステップと、
−前記ドキュメント検索プロセスからドキュメントを受け取る、開始された新たな検索動作において、開始後に最初に受信したドキュメントの識別子を第１のドキュメントとして記憶し、受け取ったドキュメントに対して特定の判定基準を適用し、
−前記検索動作が前記第１のドキュメントを２回受け取ると該検索動作を終了し、前記アクティブな検索カウンタを減分するステップと、
−前記アクティブなカウンタがいずれの検索動作もアクティブでないことを指示する値を有する場合には、前記ドキュメントの検索プロセス（２１）を終了するステップとを有することを特徴とする、複数（ｚ）のドキュメントを包含するデータベースファイルにアクセスする並行した検索動作（２２．．．２６）を提供する方法。
【請求項１０】
前記検索動作を異なるソースから開始する、請求項９記載の方法。
【請求項１１】
レコード（Ｄ１．．．Ｄ８）を包含するデータベースファイル（３１）が記憶されているデータ担体において、
各レコードは、単純に前記レコードが前記データ担体に書込まれ、ラップアラウンドと共に固定のワード長のデータフィールドに記憶された時点に関連する１つの特異なバージョン番号情報を包含することを特徴とするデータ担体。
【請求項１２】
後続のレコードが後続のバージョン番号を持たないレコードのみを有効と見なされるよう事前に規定されている、請求項１１記載のデータ担体。
【国際調査報告】
2007501480.tif 000013
2007501480.tif 000014
2007501480.tif 000015
2007501480.tif 000016
2007501480.tif 000017