(57)【要約】【課題】アイテムのライフタイムとアイテムがファイルシステムの編成構造に含まれることとを融合しない本明細書で説明されているファイルシステムを提供する。さらに、ディレクトリツリーに限定されず、その代わりに、任意の非循環有向グラフ（ＤＡＧ）を使用することができるファイルシステムの編成構造を提供する。【解決手段】アイテムは、ファイルシステム内に格納されると、アイテムがＤＡＧの一部であるか、一部でないかに関係なく、クライアントにより断定的に削除されるまで保持する。アイテムのライフライムを制御し、アイテムをユーザの選択するＤＡＧ構造に編成するため、アイテムをクライアント用の概念的ワークスペースであるファイル領域内に置く。アイテムは、複数のＤＡＧ内に同時に格納することができ、またそれぞれのファイル領域は、１つまたは複数の独立のＤＡＧを持つことができる。【選択図】図７
2006139780.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ読取り可能媒体上に格納されているデータアイテムおよびコンピュータ実行可能命令として実現されるファイルシステムであって、
前記ファイルシステム内に格納された少なくとも第１のデータアイテム、第２のデータアイテム、および第３のデータアイテムに対するアイテムロケーション情報を格納する第１のデータテーブルと、
前記第１のデータアイテムおよび第２のデータアイテムに対する編成情報を格納し、前記第３のデータアイテムに対する編成情報を含まない、第２のデータテーブルと、
を備えることを特徴とするファイルシステム。
【請求項２】
前記第１のテーブルおよび前記第２のテーブルは、別々のテーブルを含むことを特徴とする請求項１に記載のファイルシステム。
【請求項３】
前記第１のテーブルは、データアイテム毎に、前記データアイテムの一意的なアイテムＩＤ、アイテム名、および記憶位置を格納することを特徴とする請求項１に記載のファイルシステム。
【請求項４】
前記第２のテーブルのそれぞれのエントリは、２つの格納されているデータアイテム間の関係を定義することを特徴とする請求項１に記載のファイルシステム。
【請求項５】
前記関係は、親−子関係を含むことを特徴とする請求項４に記載のファイルシステム。
【請求項６】
前記第２のデータテーブルのすべてのエントリは、非循環有向グラフとして集合的に表すことができることを特徴とする請求項５に記載のファイルシステム。
【請求項７】
前記第２のテーブルは、前記第１のデータアイテムを前記第２のデータアイテムの親として識別する第１のエントリを格納することを特徴とする請求項４に記載のファイルシステム。
【請求項８】
前記第２のアイテムは、前記第１のデータアイテムおよび第２のデータアイテムの間の関係に基づき、前記第１のデータアイテムからセキュリティ許可を継承することを特徴とする請求項７に記載のファイルシステム。
【請求項９】
コンピュータ読取り可能媒体上に格納されるコンピュータ実行可能命令として実現されるファイルシステムマネージャのソフトウェアモジュールであって、前記ファイルシステムマネージャは、アイテムロケーションデータおよびアイテム編成データを使用してファイルシステムに格納されたアイテムを管理し、前記ファイルシステムマネージャは、
前記ファイルシステムから第１の指定されたアイテムを削除するための第１のサブルーチンと、
前記ファイルシステムの編成構造から第２の指定されたアイテムを除去するが、前記ファイルシステムから前記第２の指定されたアイテムを削除しない、第２のサブルーチンと、
を備えることを特徴とするファイルシステムマネージャのソフトウェアモジュール。
【請求項１０】
アイテムロケーションデータは、第１のテーブル内に格納され、アイテム編成データは、第２のテーブル内に格納されることを特徴とする請求項９に記載のファイルシステムマネージャ。
【請求項１１】
前記第１のテーブルは前記第２のテーブルと別であることを特徴とする請求項１０に記載のファイルシステムマネージャ。
【請求項１２】
前記第１のサブルーチンは、前記第１の指定されたアイテムへの参照を前記第１のテーブルおよび前記第２のテーブルから削除することを含むことを特徴とする請求項１０に記載のファイルシステムマネージャ。
【請求項１３】
前記第１のサブルーチンは、削除前に、前記第１の指定されたアイテムに関係する前記第２のテーブル内の複数のエントリに基づいて、前記第２のテーブルに新しいエントリを追加することをさらに含むことを特徴とする請求項１２に記載のファイルシステムマネージャ。
【請求項１４】
前記第２のサブルーチンは、前記第２の指定されたアイテムへの参照を前記第２のテーブルから削除するが、前記第２の指定されたアイテムを前記第１のテーブルから削除しないことを含むことを特徴とする請求項１０に記載のファイルシステムマネージャ。
【請求項１５】
前記第１のサブルーチンは、第１のアプリケーションプログラミングインタフェース（ＡＰＩ）を介して呼び出し可能であることを特徴とする請求項９に記載のファイルシステムマネージャ。
【請求項１６】
前記第２のサブルーチンは、前記第１のＡＰＩと異なる第２のＡＰＩを介して呼び出し可能であることを特徴とする請求項１５に記載のファイルシステムマネージャ。
【請求項１７】
前記編成データに基づくセキュリティデータをさらに備えることを特徴とする請求項９に記載のファイルシステムマネージャ。
【請求項１８】
前記ファイルシステムマネージャは、編成データに基づきアイテムのそれぞれについて名前空間を構成することを特徴とする請求項９に記載のファイルシステムマネージャ。
【請求項１９】
ファイルシステムに格納されているアイテムを管理する方法であって、
前記ファイルシステムから第１のアイテムを削除する第１の要求を受け取るステップと、
前記第１の要求に対する応答として、前記ファイルシステムに関連付けられたロケーション情報から、および前記ファイルシステムに関連付けられた編成情報から、前記第１のアイテムへの参照を削除するステップと、
前記ファイルシステムから第２のアイテムを除去する第２の要求を受け取るステップと、
前記第２の要求に対する応答として、前記第２のアイテムへの参照を前記ファイルシステムに関連付けられた前記編成情報から削除し、前記ファイルシステムに関連付けられた前記ロケーション情報からの前記第２のアイテムへの参照を無変更のままにするステップと、
を備えることを特徴とする方法。
【請求項２０】
データアイテムを格納するための、コンピュータ読取り可能媒体上に格納されたコンピュータ実行可能命令として実現されるファイルシステムであって、それぞれのデータアイテムのライフタイムは、前記ファイルシステムに格納された他のデータアイテムに対するそれぞれのデータアイテムの編成と無関係であることを特徴とするファイルシステム。
【請求項２１】
データアイテムを格納するための、コンピュータ読取り可能媒体上に格納されたコンピュータ実行可能命令として実現されるファイルシステムであって、前記ファイルシステムは、データアイテムと前記ファイルシステムに格納された他のデータアイテムとの関係と無関係であるそれぞれのデータアイテムのライフタイムを決定することを特徴とするファイルシステム。
【請求項２２】
データアイテムを格納するための、コンピュータ読取り可能媒体上に格納されたコンピュータ実行可能命令として実現されるファイルシステムであって、前記ファイルシステムは、前記ファイルシステムに格納された他のデータアイテムとの親−子関係を持たない第１のデータアイテムを格納することを特徴とするファイルシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステム用のファイルシステムに関する。より具体的には、本発明は、ファイルシステム内に格納されたアイテムのライフタイムとファイルシステムにより使用される基礎をなす編成構造（ｏｒｇａｎｉｚａｔｉｏｎａｌ  ｓｔｒｕｃｔｕｒｅ）とを融合（ｃｏｎｆｌａｔｅ）しないため、ファイルシステムに格納されたアイテムが、それぞれ、削除されるのを心配せずに、編成構造内に親を０個、１個、または複数個持つことができる。
【背景技術】
【０００２】
本特許明細書の開示の一部は、著作権保護の対象となる資料を含む。著作権所有者は、特許商標庁の特許ファイルまたは記録の記載に従い誰が特許文書または特許開示の複製を行おうと異存はないが、その他の点では、いかなる形であれすべての著作権を留保する。
【０００３】
コンピュータは、ディスクドライブなどの記憶デバイスにファイルを格納する。ディスクドライブは、空のファイルキャビネットのように、データを格納するための場所を提供するだけである。空のファイリングキャビネットには、ファイル用に予め定められたファイリングシステムが付属していない（つまり、ファイリングキャビネットのユーザがファイリングシステムまたは編成構造自体を、例えばファイルをアルファベット順に並べることにより作成しなければならない）のと同様に、デフォルト設定では、ハードドライブも、単なる空の記憶領域である。それだけでは、ハードドライブ上のデータにアクセスするのに、データの物理的位置を指定する（例えば、ファイルが格納されているハードドライブのシリンダ、ヘッド、およびセクタを指定する）か、ディスク上の論理的位置（例えば、２１，６７１番目のブロック）を指定する方法しかない。ハードディスクドライブがコンピュータに装着されると、コンピュータはファイルシステムを使用して、アクセスしやすい方法でハードディスクドライブに格納されているファイルを追跡する。
【０００４】
知られているファイルシステムは、オペレーティングシステムおよびファイルシステムのユーザがファイルシステム内のファイルに行う編成を不当に制限している。つまり、通常、知られているファイルシステムでは、ユーザ側でアイテムをファイルとディレクトリのツリーに編成する（ｏｒｇａｎｉｚｅ）必要があるが、ディレクトリは実際にはファイルシステムによって識別される特別な種類のファイルである。ファイルシステム側で追加的なデータ構造をサポートしているとしても、この機能は、通常は、ファイルシステムのクライアント（つまり、エンドユーザおよびアプリケーション）には公開されない。図２は、既存のファイルシステムの典型的な編成構造２０１の簡単な実施例を示している。図２に例示されているように、知られているファイルシステムでは、ツリーを使用して、ディレクトリ（角の丸い長方形で囲まれている）とファイル（長方形で囲まれている）を編成している。ツリー構造では、アイテムの位置と編成は融合されており、すべてのアイテムはただ１つのディレクトリ内になければならない。これでは、ユーザは自分のファイルを編成しなければならず、ユーザは、１つのアイテムを、アイテムの新しいコピーを作成せずには複数の編成の中に置くことはできない。
【０００５】
典型的なファイルシステムでは、２つのテーブルまたはデータベース同士を連携して使用し、ファイルを編成する。第１のテーブルまたはデータベースは、ファイルが格納されるハードドライブなどの記憶デバイス上の物理的位置を識別するルックアップテーブルである。第２のテーブルは、ファイルの編成構造を定義する。これらのテーブルは、一般的に、本明細書では、ロケーションテーブル（ＬＯＣ）および編成テーブル（ＯＲＧ）とそれぞれ呼ばれる。編成テーブルには、保持リンク（ｈｏｌｄｉｎｇ  ｌｉｎｋｓ）に関する情報、つまり、一方のアイテムが他方のアイテムの親であるという情報が格納される。一部のファイルシステムでは、ロケーションテーブルと編成テーブルとを単一のテーブルまたは構造にまとめることができるが、それでも、ファイルシステムが適切に動作するために両方のテーブルの要素が存在している必要がある。例えば、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ社が販売しているＮＴブランドのファイルシステム、つまりＮＴＦＳでは、マスタファイルテーブルは、ロケーションテーブルと編成テーブルの両方として機能する。同様に、Ｕｎｉｘ（登録商標）ファイルシステム、ＵＦＳでは、ファイル用のロケーションテーブルおよび編成テーブルの両方として機能するｉノードからなるテーブルを使用する。ディレクトリは、特別な種類のファイルとして格納され、ディレクトリ「ファイル」は、ディレクトリとそのそれぞれのｉノード内にファイル名のリストを格納する。
【０００６】
これらおよびその他の知られているファイルシステムでは、ファイルシステムは、ファイルが編成テーブル内の保持リンクにより定義されているような少なくとも１つのロケーションに配置されている限り、つまりそのファイルをポイントしている少なくとも１つの保持リンクがある限り、物理的記憶デバイス上に格納されているファイルを保持する。つまり、ファイルの保持リンクが編成テーブルから削除され、そのファイルをポイントしている保持リンクがもう存在しない場合は、ファイルシステムは、ロケーションテーブル内のファイルのエントリを除去する（そのファイルが記憶デバイス上に物理的に上書きされるかどうかに関係なく）。記憶デバイスでは、その後、その記憶領域を使用して新しいデータを書き込むことができる。例えば、ユーザが図２に示されているファイルＣ：＼ＰＲＯＧＲＡＭＳ＼ＭＩＣＲＯＳＯＦＴ＼ＯＦＦＩＣＥ＼ＷＯＲＤ＼ＦＩＬＥ．ＤＯＣを「削除」する場合、ファイルシステムは、編成テーブルからファイルのエントリを最初に除去する。ファイルがロケーションテーブル内に他のエントリを持たない、つまり、ファイルがさらに他のどこかに格納されていない場合、ファイルシステムは、ロケーションテーブル内のファイルのエントリを除去し、他のデータのために領域を解放する。通常、ファイルシステムは、与えられたアイテムが持つ先祖（「保持リンク」と呼ばれている）の個数の参照カウントを維持する。アイテム上の最後の保持リンクが除去されると、そのアイテムは、ロケーションテーブル内のファイル参照を除去することにより「削除」される。ただし、これは、ファイルシステムが使用できる編成構造を制限するため、エンドユーザの観点からは望ましいことではない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述の制約および制限（例えば、ツリーからファイルを除去した副作用としての削除）のせいで、ファイルシステムでは、クライアント側でディレクトリおよびファイルのツリー状階層以外のデータ構造によってデータを編成することはできない。ユーザは、与えられたアイテムが削除されるのを気にせずに、さまざまな編成データ構造においてアイテムの編成および編成の解放を行えることを望んでいる。アイテムのライフタイムがファイルシステム内のその編成から分離されていれば、当技術分野の進歩となるであろう。つまり、アイテムの編成または編成解放の活動がライフタイムに影響を及ぼさない、アイテムのライフタイムと編成構造との融合を行わないファイルシステムを提供すれば進歩であろう。そこで、オペレーティングシステムおよび／またはユーザがファイルの編成に使用するデータ構造の型を制限しない、また単にファイルがファイルシステム内のすべての編成構造から除去された、またはそのファイルを指す保持リンクがないからといって、ファイルを削除しないファイルシステムを提供することは当技術分野における進歩であろう。
【課題を解決するための手段】
【０００８】
以下では、本発明のいくつかの態様の基本的な内容を理解できるように、発明の概要を簡単に説明する。この発明の開示は、本発明の概要を広範囲にわたって述べたものではない。この要約は、本発明の鍵となる要素や決定的な要素を示したり、本発明の範囲を定めたりすることを目的としていない。以下では、後述の詳細な説明の前置きとして、本発明のいくつかの概念を簡略化した形式で述べる。
【０００９】
上述の従来技術における１つまたは複数の制限を克服するために、および／または本明細書を読み理解した後では明白になるであろう他の制限を克服するために、本発明は、一般に、データアイテムとして実現されるファイルシステムおよびコンピュータ読取り可能媒体上に格納されるコンピュータ実行可能命令を対象とする。データアイテムは、一般に、限定はしないがファイル、フォルダ、データ、音楽などを含む、ファイルシステムに格納可能な任意のデータを意味する。ファイルシステムでは、ファイルシステム内に格納されている少なくとも第１、第２、および第３のデータアイテムに対するアイテムロケーション情報を格納する第１のデータテーブルを使用し、また第１および第２のデータアイテムに対する編成情報を格納するが、第３のデータアイテムに対する編成情報を格納しない第２のデータテーブルを使用する。
【００１０】
ファイルシステムのファイルシステムマネージャのソフトウェアモジュールは、コンピュータ読取り可能媒体上に格納されるコンピュータ実行可能命令として実現することができる。ファイルシステムマネージャは、アイテムロケーションデータおよびアイテム編成データに基づいてファイルシステム内に格納されているデータアイテムを管理する。ファイルシステムマネージャは、ファイルシステムからアイテムを削除するために第１のサブルーチンを使用し、ファイルシステムからアイテムを除去するために第２のサブルーチンを使用する。
【００１１】
ファイルシステムマネージャは、ファイルシステムから第１のアイテムを削除する第１の要求を受け取ることを含む、ファイルシステム内に格納されているアイテムを管理する方法を実行し、その第１の要求に対する応答として、ファイルシステムに関連付けられているロケーション情報から、またファイルシステムに関連付けられている編成情報から第１のアイテムへの参照を削除する。ファイルシステムマネージャは、ファイルシステムから第２のアイテムを除去する第２の要求を受け取り、その第２の要求に対する応答として、ファイルシステムに関連付けられている編成情報から第２のアイテムへの参照を削除するが、ファイルシステムに関連付けられているロケーション情報からは第２のアイテムへの参照を削除しない。
【００１２】
本発明の他の態様では、コンピュータ読取り可能媒体上に格納されているコンピュータ実行可能命令として実現され、データアイテムを格納する、ファイルシステムを提供する。このファイルシステムでは、データアイテムのライフタイムは、ファイルシステム内のデータアイテムの概念的編成内のデータアイテムの位置とは無関係である。
【００１３】
付属の図面と合わせて、以下の説明を参照すると、本発明およびその利点をより完全に理解でき、また類似の参照番号は類似の特徴を示している。
【発明を実施するための最良の形態】
【００１４】
さまざまな実施形態の以下の説明では、一部をなし、本発明を実施できるさまざまな実施形態が図で示されている、付属の図面を参照する。他の実施形態を利用し、本発明の範囲から逸脱することなく機能的な修正を加えることができることは理解されるであろう。
例示されているコンピューティング環境
図１は、本発明を実装できる好適なコンピューティングシステム環境１００の一実施例の図である。コンピューティングシステム環境１００は、好適なコンピューティング環境の一例にすぎず、本発明の用途または機能性の範囲に関する制限を示唆する意図はない。コンピューティング環境１００は、オペレーティング環境例１００に示されている１つのコンポーネントまたはその組み合わせに関係する何らかの依存関係または要求条件がその環境にあるものと解釈すべきでない。
【００１５】
本発明は、他の数多くの汎用または専用コンピューティングシステム環境または構成で動作する。本発明とともに使用するのに適していると思われるよく知られているコンピューティングシステム、環境、および／または構成の例として、限定はしないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家電製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたはデバイスなどを含む分散コンピューティング環境などがある。
【００１６】
本発明は、コンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的背景状況において説明することができる。一般に、プログラムモジュールは、特定のタスクを実行する、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。また、本発明は、通信ネットワークを通じてリンクされているリモート処理装置によりタスクが実行される分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラムモジュールをメモリ記憶デバイスなどのローカルとリモートの両方のコンピュータ記憶媒体に配置できる。
【００１７】
図１を参照すると、本発明を実装する例示されているシステムは、汎用コンピューティングデバイスをコンピュータ１１０の形で備えている。コンピュータ１１０が備えるコンポーネントとしては、限定はしないが、演算処理装置１２０、システムメモリ１３０、およびシステムメモリを備えるさまざまなシステムコンポーネントを演算処理装置１２０に結合するシステムバス１２１などがある。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺機器バス、およびさまざまなバスアーキテクチャを使用するローカルバスを含む数種類のバス構造のうちのいずれでもよい。例えば、限定はしないが、このようなアーキテクチャとしては、ＩＳＡバス、ＭＣＡバス、ＥＩＳＡバス、ＶＥＳＡローカルバス、およびＭｅｚｚａｎｉｎｅバスとも呼ばれるＰＣＩバスがある。
【００１８】
コンピュータ１１０は、通常、さまざまなコンピュータ読取り可能媒体を含む。コンピュータ読取り可能媒体は、コンピュータ１１０によってアクセスされることができる媒体であればどのような媒体でも使用可能であり、揮発性および不揮発性媒体、取り外し可能および取り外し不可能媒体を含む。例えば、限定はしないが、コンピュータ読取り可能媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造体、プログラムモジュール、またはその他のデータなどの情報を格納する方法または技術で実装される揮発性および不揮発性、取り外し可能および取り外し不可能媒体を含む。コンピュータ記憶媒体としては、限定はしないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）またはその他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶デバイス、または情報を格納するために使用することができコンピュータ１１０によりアクセスできるその他の媒体または媒体の組み合わせがある。通信媒体は、通常、コンピュータ可読命令、データ構造体、プログラムモジュール、または搬送波もしくはその他のトランスポートメカニズムなどの変調データ信号によるその他のデータを実現するものであり、任意の情報配信媒体を含む。「変調データ信号」という用語は、信号内に情報を符号化するような方法で特性のうちの１つまたは複数が設定または変更された信号を意味する。例えば、限定はしないが、通信媒体としては、有線ネットワークまたは直接配線接続などの有線媒体、ならびに、音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体がある。
【００１９】
システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動時などにコンピュータ１１０内の要素間の情報伝送を助ける基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）は、通常、ＲＯＭ１３１に格納される。通常、ＲＡＭ１３２は、演算処理装置１２０に直接アクセス可能な、および／または演算処理装置１２０によって現在操作されているデータおよび／またはプログラムモジュールを格納する。例えば、限定はしないが、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、プログラムデータ１３７、およびファイルシステム１３８を例示している。
【００２０】
コンピュータ１１０はさらに、その他の取り外し可能／取り外し不可能な、揮発性／不揮発性コンピュータ記憶媒体を備えることもできる。例にすぎないが、図１は、取り外し不可能な不揮発性磁気媒体の読み書きを行うハードディスクドライブ１４０、取り外し可能な不揮発性磁気ディスク１５２の読み書きを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭまたはその他の光媒体などの取り外し可能な不揮発性光ディスク１５６の読み書きを行う光ディスクドライブ１５５を例示している。例示されているオペレーティング環境で使用できる他の取り外し可能／取り外し不可能な、揮発性／不揮発性コンピュータ記憶媒体としては、限定はしないが、磁気テープカセット、フラッシュメモリカード、デジタル多目的ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどがある。ハードディスクドライブ１４１は、通常、インタフェース１４０などの取り外し不可能なメモリインタフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常、インタフェース１５０などの取り外し可能なメモリインタフェースによりシステムバス１２１に接続される。
【００２１】
図１に例示されている上記のドライブおよび関連コンピュータ記憶媒体は、コンピュータ１１０にコンピュータ可読命令、データ構造体、プログラムモジュール、およびその他のデータを格納する機能を備える。例えば、図１では、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、プログラムデータ１４７、およびファイルシステム１４８を格納するものとして例示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、プログラムデータ１３７、およびファイルシステム１３８と同じである場合もあれば異なる場合もあることに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、プログラムデータ１４７、およびファイルシステム１４８に対しては、図１において異なる番号を割り当てて、例えば、それらが異なるコピーであることを示している。ユーザは、キーボード１６２、およびマウス、トラックボール、またはタッチパッドと一般に呼ばれるポインティングデバイス１６１などの入力デバイスを介してコンピュータ２０にコマンドおよび情報を入力できる。他の入力デバイスとしては、リモートコントロール１６３、マイク、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ（すべてが図に示されているわけではない）などがある。これらの入力デバイスやその他の入力デバイスは、システムバスに結合されているユーザ入力インタフェース１６０を介して演算処理装置１２０に接続されることが多いが、パラレルポート、ゲームポート、またはＵＳＢなどの他のインタフェースおよびバス構造により接続することもできる。モニタ１９１またはその他の種類の表示デバイス（例えば、ＴＶ）も、ビデオインタフェース１９０などのインタフェースを介してシステムバス１２１に接続される。モニタのほかに、コンピュータはさらにスピーカ１９７およびプリンタ１９６などの他の周辺出力デバイスも備えることができ、これらは出力周辺機器インタフェース１９０を介して接続することができる。
【００２２】
いくつかの態様では、手書き入力をデジタル方式で取り込むために、ペンデジタイザ１６５および付属するペンまたはスタイラス１６６が用意される。ペンデジタイザ１６５とユーザ入力インタフェース１６０との間の直接接続が示されているが、実際には、ペンデジタイザ１６５は、演算処理装置１１０に直接、パラレルポートまたはその他のインタフェースに、および無線を含む技術を使用してシステムバス１３０に結合することができる。また、ペン１６６は、ペンに関連付けられているカメラ、カメラにより取り込まれた画像情報をバス１３０とやり取りするインタフェースに無線で送信するトランシーバを備えることができる。さらに、ペンは、加速度計、磁力計、およびジャイロスコープを含む電子インクのストロークを判別するため、カメラに加えて、またはカメラの代わりに、他の検知システムを備えることもできる。
【００２３】
コンピュータ１１０は、リモートコンピュータ１８０などの１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク接続環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の共通ネットワークノードでもよく、通常は、コンピュータ１１０に関係する上述の要素の多くまたはすべてを含むが、メモリ記憶デバイス１８１だけが図１に例示されている。図１に示されている論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含むこともできる。このようなネットワーキング環境は、オフィス、企業全体にわたるコンピュータネットワーク、イントラネット、およびインターネットでは一般的である。さらに、システムは、有線および／または無線機能を備えることができる。例えば、ネットワークインタフェース１７０は、ブルートゥース、ＳＷＬａｎ、および／または組み合わせ機能のＩＥＥＥ８０２．１１クラスを含むことができる。他の無線通信プロトコルを、これらのプロトコルとともに、またはこれらのプロトコルの代わりに使用することができることは理解されるであろう。
【００２４】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、ネットワークインタフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、通常、インターネットなどのＷＡＮ１７３上での通信を確立するためモデム１７２またはその他の手段を備える。モデム１７２は、内蔵でも外付けでもよいが、ユーザ入力インタフェース１６０またはその他の適切なメカニズムを介してシステムバス１２１に接続されうる。ネットワーク接続環境では、コンピュータ１１０またはその一部に関して示されているプログラムモジュールは、リモートメモリ記憶デバイスに格納されうる。例えば、限定はしないが、図１には、リモートアプリケーションプログラム１８５がメモリデバイス１８１に置かれているように例示されている。
【００２５】
図１に示されているネットワーク接続は実施例であり、コンピュータ間の通信リンクを確立するのに他の技術が使用可能であることは理解されるであろう。ＴＣＰ／ＩＰ、Ｅｔｈｅｒｎｅｔ（登録商標）、ＦＴＰ、ＨＴＴＰなどのさまざまなよく知られているプロトコルのいずれか存在していると仮定されており、システムは、クライアントサーバ構成で動作可能であり、これによりユーザはＷｅｂベースのサーバからＷｅｂページを取り出すことができる。さまざまな従来のＷｅｂブラウザを使用することで、Ｗｅｂページ上にデータを表示し、操作をすることができる。
【００２６】
本発明の１つまたは複数の態様は、コンピュータ１１０などの１つまたは複数のコンピュータまたは他のデバイスにより実行される、１つまたは複数のプログラムモジュールなどの、コンピュータ実行可能命令で実現することができる。一般に、プログラムモジュールは、コンピュータまたは他のデバイス内のプロセッサにより実行されたときに、特定のタスクを実行する、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。コンピュータ実行可能命令は、ハードディスク、光ディスク、取り外し可能記憶媒体、ソリッドステートメモリ、ＲＡＭなどのコンピュータ読取り可能媒体上に格納することができる。当業者には周知のことであろうが、プログラムモジュールの機能は、さまざまな実施形態で望まれているように組み合わせるか、または分散させることができる。さらに、機能は、全体または一部を、ファームウェアまたは集積回路、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などのハードウェア等価物により実現できる。
【実施例１】
【００２７】
本発明の例示されている態様によれば、本明細書では、アイテムのライフタイムとファイルシステムの編成構造内でのアイテムの配置とを融合せず、したがって１つまたは複数の非循環有向グラフ（ＤＡＧ）を形成する、両方のプロパティベースの問い合わせ、またリストなどを通じて、アイテムが複数の編成に参加するか、または全くなににも参加することがないファイルシステムについて説明する。ＤＡＧは、アイテムが複数の親を持ち得る編成である。ＤＡＧでは、アイテムは、サイクルを形成することになる、その祖先の１つの親にはなり得ない。
【００２８】
本明細書で説明されているファイルシステムは、コンピュータ読取り可能媒体中に格納されるコンピュータ実行可能命令、例えばファイルシステム１３８および／またはファイルシステム１４８として実現することができる（図１）。図１の他のコンピュータ読取り可能媒体またはメモリは、さらに、ここで説明されているファイルシステムと同じであるか、または異なるファイルシステムを含むこともできる。例えば、媒体１５２および１５６は、さらに、ファイルシステムを含むこともできる。説明のため、このファイルシステムは、本明細書では、ファイルシステム１４８を参照しつつ説明される。
【００２９】
図３および図４を参照すると、ファイルシステム１４８は、主に、ロケーションテーブル（ＬＯＣ）３０１および編成テーブル（ＯＲＧ）４０１の２つのテーブルに依存する。ロケーションテーブル３０１は、ＬＯＣテーブルとも呼ばれ、例えば、ファイル識別子（ＩＤ）３０３、ファイル名３０５、記憶ボリューム３０７、ロケーション３０９、およびファイルサイズ３１１を含む、ファイルシステムに格納されているそれぞれのアイテムの物理的および／または論理的記憶位置に関する情報を格納する。ファイルＩＤ３０３は、それぞれのアイテムを参照するために使用される主なキーまたは参照であり、ファイルシステム１４８に格納されているそれぞれのアイテムに対して一意的なものである。ファイルＩＤは、それぞれのファイルＩＤがファイルシステム１４８内に格納されている単一アイテムを一意に識別する限り、数値、アルファベットテキスト、記号、または任意の組み合わせを含むことができる。
【００３０】
ファイル名３０５は、ファイルシステム１４８のユーザによって与えられたアイテムの短い説明的ファイル名を含むことができる。ファイル名３０５は、それぞれのファイルへのユーザの一次的な概念的参照であるのが好ましく、またファイルをファイル名に基づいてユーザが容易に認識できるような説明的形式でユーザが指定することができる。ファイル名３０５は、制限された長さ、例えば８．３形式、最大長２５６文字、または他の何らかの最大値を持つものとすることができる。ファイル名が互いに重複しているかどうか、さらにはファイル名が必要か、すでに割り当てられているかどうかに関する制約がないことが好ましい。つまり、複数のファイルが、同じディレクトリ、フォルダ、またはリスト内にあっても、それぞれのファイルが一意的なファイルＩＤ３０３を持つ限り、それぞれ「ＲＥＡＤＭＥ．ＴＸＴ」または「Ｒｅａｄ  ｔｈｉｓ  ｆｉｒｓｔ」と名前を付けることができる。これは、親のコンテキスト内ではそれぞれのファイルが一意的な名前を持つことが要求される、以前のファイルシステムとは異なる。
【００３１】
ボリューム３０７、ロケーション３０９、およびサイズ３１１を使用して、物理的または論理的記憶位置からアイテムを取り出すことができる。ボリューム３０７は、物理的または論理的記憶デバイス、例えば、物理的または論理的ハードディスクドライブ、光記憶装置、記憶媒体カード、固体記憶デバイスなどを指し得る。ロケーション３０９は、識別された物理的または論理的ボリューム上のアイテムの実際の開始位置を指し、サイズ３１１は、識別された位置から開始する識別されたボリューム上にアイテムが格納されている空間の大きさの定量的な測度を指し得る。追加または代替的な情報は、含まれる情報がそれぞれの識別された記憶位置からそれぞれの格納されているアイテムを取り出すために使用可能である限りロケーションテーブル３０１内に入れることができる。
【００３２】
編成テーブル４０１は、ＯＲＧテーブルとも呼ばれ、ファイルシステム１４８に格納されているアイテム間の階層関係を格納する。上で簡単に説明したように、ＯＲＧテーブル４０１は、ファイルシステム１４８内でアイテムを概念的に配列するため、１つまたは複数のツリーを含むことができる、１つまたは複数の非循環有向グラフ（ＤＡＧ）を定義することができる。ＯＲＧテーブル４０１は、関係毎に、親４０３および子４０５を含むことができる。図５は、ＬＯＣテーブル３０１の一部分により定義され、またＯＲＧテーブル４０１により定義されているようなＤＡＧ５０１の実施例を示している。ＤＡＧ  ５０１は、アイテムＩ２が「Ｔｏ  Ｄｏ  Ｌｉｓｔ」と「Ｉｔｅｍｓ  Ｆｏｒ  Ｍｙ  Ｔｒｉｐ」の両方を親とし（「中にある」ともいう）、アイテムＩ４が「Ｉｔｅｍｓ  Ｆｏｒ  Ｍｙ  Ｔｒｉｐ」と「Ｋｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓ」の両方を親とするため、ツリーではない。ファイルシステム１４８に格納されているそれぞれのアイテムは、編成構造にＤＡＧが残っている限り、親を１つも持たない、親を１つ持つ、または親を２つ以上持つことがあり得る。
【００３３】
図６は、ファイルシステム１４８内で使用できるソフトウェアモジュールのブロック図を示している。ファイルシステム１４８は、ファイルシステム１４８のオペレーション全体を管理するファイルシステムマネージャのソフトウェアモジュール６０１を備えることができる。マネージャ６０１は、ＤＡＧに課された制約条件（例えば、サイクルを許容しない）に関するルールを実行しながら、本明細書で説明されているようにＬＯＣテーブル３０１およびＯＲＧテーブル４０１を使用して、データストア６１１に格納されているアイテムの追加、更新、削除、および読み取り／問い合わせを実行することができる。マネージャ６０１は、オペレーティングシステムなどのより上位のプログラムがファイルシステム１４８とやり取りするために使用できる１つまたは複数のアプリケーションプログラミングインタフェース（ＡＰＩ）を公開することができる。ＡＰＩは、Ａｄｄ＿Ｉｔｅｍ  ＡＰＩ６０３、Ｕｐｄａｔｅ＿Ｉｔｅｍ  ＡＰＩ６０５、Ｄｅｌｅｔｅ＿Ｉｔｅｍ  ＡＰＩ６０７、およびＱｕｅｒｙ＿Ｉｔｅｍ  ＡＰＩ６０９を含むことができる。
【００３４】
Ａｄｄ＿Ｉｔｅｍ  ＡＰＩ６０３は、新しいアイテムがファイルシステム１４８内に格納される場合に、オペレーティングシステムまたはその他の上位のプログラムまたはアプリケーションにより呼び出され得る。Ａｄｄ＿Ｉｔｅｍ  ＡＰＩ６０３は、ファイル名とともに、オプションにより、意図される記憶ボリュームおよび／または親ＩＤとともに、新しいアイテムの現在の一時的記憶位置を指すポインタを入力として受け付けることができる。Ａｄｄ＿Ｉｔｅｍ  ＡＰＩは、新しく追加されたアイテムに対するファイルＩＤをオプションにより返すことができる。
【００３５】
Ｕｐｄａｔｅ＿Ｉｔｅｍ  ＡＰＩ６０５は、ファイルシステム１４８内にすでに格納されている既存のアイテムを更新するために呼び出すことができ、またファイルＩＤ、およびアイテムの更新されたバージョンへのポインタ、ＯＲＧテーブル４０１内の包含の更新された関係、および／または更新されたファイル名から選択された１つまたは複数のオプションで含まれる情報断片を入力として受け付けることができる。
【００３６】
Ｄｅｌｅｔｅ＿Ｉｔｅｍ  ＡＰＩ６０７を呼び出し、削除するファイルＩＤをＤｅｌｅｔｅ＿Ｉｔｅｍ  ＡＰＩに渡すことにより、ファイルシステム１４８からアイテムを除去することができる。Ｄｅｌｅｔｅ＿Ｉｔｅｍ  ＡＰＩ６０７が明示的に呼び出された場合のみ、ファイルシステム１４８からアイテムが削除される。
Ｑｕｅｒｙ＿Ｉｔｅｍ  ＡＰＩ６０９は、ＯＳまたはアプリケーションで使用するためアイテムをファイルシステムから取り出す必要がある場合に呼び出すことができる。Ｑｕｅｒｙ＿Ｉｔｅｍは、ファイルＩＤを入力として受け付け、要求されたアイテムを返す。上記のＡＰＩは、本発明の例示されている実施形態に含まれるのが好ましいタイプのＡＰＩを表している。ファイルシステム１４８は、システムの要求条件または設計に基づく追加または代替えＡＰＩを含むことができる。
【００３７】
ファイルシステム１４８では、それぞれのアイテムは０個以上の親を持つことができるため、１つのボリュームまたはファイルシステム内に複数の独立したデータ構造（つまり、複数のＤＡＧ）があり得る。これは、通常、クライアント（ユーザまたはアプリケーション）を１つのボリューム単位の単一ツリー内にアイテムを格納することに制限する、既存のファイルシステムとは異なる。したがって、ここで説明されているようにアイテムがファイルシステム内に格納される概念上の空間は、ファイル領域（ＦＲ）と呼ばれる。ファイル領域は、アイテムのライフタイムを制御するために使用される編成領域の高いレベルのユーザ概念を指す。アイテムがファイル領域内にある限り、アイテムは、ＯＲＧテーブル４０１内で定義されている親−子関係が適用されているかどうかに関係なく、削除されない。
【００３８】
ファイル領域は、アイテムが概念的に関係付けられているかどうかにかかわりなく、アイテムを入れることができるボックスとして概念上考えられる。アイテムがファイル領域内に置かれると、アイテムは、ユーザが削除しない限りファイル領域内に残る。アイテムがファイル領域内にある間、アイテムは、アイテムがファイル領域内にあるかどうかに影響を及ぼすことなく、またアイテムのライフタイムに影響を及ぼすことなく、ファイル領域内の１つまたは複数のＤＡＧのどれかに編成することができる。つまり、ファイルは、ユーザがシステムにファイルの削除を断定的に命令しない限り削除されない。ファイル領域は、含まれているすべてのデータストア同士が同じコンピュータ、ネットワークなどの中で物理的に近接しているかどうかに関係なく、データストアがアイテムのライフタイムを保証するために単一ファイル領域として管理されている限り、任意に定義された記憶領域を包含することができる。例えば、ファイル領域は、コンピュータ上のすべての内蔵ハードドライブ、コンピュータ上の単一のハードドライブの一部、ネットワーク接続された単独の、またはローカル記憶装置と組み合わされた記憶装置、またはその他の定義されている記憶領域を包含しうる。
【００３９】
図７および図８は、３つの独立したＤＡＧ５０１、７０３、および７０５を持つファイル領域７０１を例示している。ＤＡＧ５０１、７０３、および７０５の間の唯一必須の関係は、それらが同じファイル領域内に置かれていることであり、それらの間に必須の概念的関係はない。図８は、図７に示されているＤＡＧを記述するＯＲＧテーブル８０１を例示している。図７は、ファイル領域７０１の概念視点を例示しているが、図８は、ファイル領域７０１で使用されている保持リンクを例示している。ファイル領域７０１は、ユーザによって開かれ、その時点で、ファイルシステム１４８は、ファイルシステムによって定義されたファイル領域内での「トップレベル」または「フローティング」アイテムのすべてをユーザに提示することができる。本明細書で使用されているように、アイテムは、ファイル領域に対応するＯＲＧテーブル内の他のアイテムからの保持リンクのリンク先となっていない場合に「トップレベル」または「フローティング」と定義される。したがって、図７では、アイテムｉ１、ｉ７、Ｔｏ  Ｄｏ  Ｌｉｓｔ、およびＩｔｅｍｓ  Ｆｏｒ  Ｍｙ  Ｔｒｉｐは、トップレベルアイテムまたはフローティングアイテムとみなされる。エンドユーザにとっては、リストｉ７は、編成データ構造の形態である。複数の親の概念に基づき、アイテムは複数のリスト内にあってもよい、例えば、アイテムｉ３である。リストは、順序付けられた、または順序付けられていない他のアイテムを保持するアイテムであり、リストは、ユーザが従来のファイルシステムで扱い慣れているフォルダ／ディレクトリを置き換えることができる。リストは、他リスト内にあってもよいし、あるいは他のリストを保持することもできる。
【００４０】
ファイルシステム１４８は、ユーザまたはアプリケーション（クライアントと総称される）が基礎をなす編成構造からアイテムを除去することを望んでいるのか、それともクライアントがファイルシステムからアイテムを完全に削除することを望んでいるのかを区別する。図９および図１０は、ユーザまたはアプリケーションがＫｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓリストからアイテムｉ５を除去した後のファイル領域８０１を例示している。つまり、マネージャ６０１は、Ｕｐｄａｔｅ＿Ｉｔｅｍ  ＡＰＩ６０５を介した要求に基づき、Ｋｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓ（ファイルＩＤ  ０００００７）をアイテムｉ５（ファイルＩＤ  ０００００６）の親として識別するＯＲＧテーブル１００１内の保持リンクを除去する。アイテムｉ５は、アイテムｉ５に関係するすべての保持リンクがＯＲＧテーブル４０１から除去されたため、もはや複数アイテム編成構造の一部ではない。しかし、アイテムｉ５はファイル領域８０１内に残っているため、アイテムｉ５は、ファイルシステム１４８またはＬＯＣテーブル３０１からは削除されない。別の言い方をすると、クライアントはアイテムｉ５を削除する（ｄｅｌｅｔｅ）要求をしなかったが、むしろアイテムｉ５を除去する（ｒｅｍｏｖｅ）ことを要求したため、アイテムｉ５は、データストア６１１およびＬＯＣテーブル３０１から削除されない。クライアントがアイテムｉ５を断定的に選択し、Ｄｅｌｅｔｅ＿Ｉｔｅｍ  ＡＰＩ６０７を介して削除オペレーションを要求した後でしか、マネージャ６０１はアイテムｉ５  （ファイルＩＤ  ０００００６）をデータストア６１１およびＬＯＣテーブル３０１から除去しない。
【００４１】
図１１および図１２を参照すると、ファイルシステム１４８を使用することで、すでに知られているファイルシステムで使用されている編成構造に基づいて、ユーザにおなじみの編成構造、例えば、ディレクトリツリーを模倣することができる。再びＬＯＣテーブル３０１（図３）を参照すると、ファイルＩＤ  ０００３０１〜０００３１２を持つアイテムは、ファイルシステム１４８に格納されているリストの保持リンクを表している。それぞれの順序付けられていないリストは、ファイル領域１２０１（図１２）およびＯＲＧテーブル１１０１（図１）で概念的に表されているディレクトリツリー１２０３において１つのディレクトリを表す。ディレクトリツリー１２０３と以前から知られているディレクトリツリーとの主な違いは、サブディレクトリ「Ｓｈａｒｅｄ」は２つの「Ｕｓｅｒ  Ｄａｔａ」という順序付けされていないリストのうちのいずれかを介してアクセス可能であり、したがって、ファイルシステム１４８の複数の親機能を利用できるという点である。この方法で、ユーザは自分の慣れ親しんだ編成構造を利用しつつ、ユーザ同士の間でディレクトリを簡単に共有することができる。
【００４２】
本発明の例示されている実施形態によれば、ファイルシステム１４８は、ファイルシステム１４８が実装されているコンピュータシステムまたはネットワークのそれぞれの個別ユーザにプライベートワークスペースを用意し、またコンピュータシステムまたはネットワークのすべてのユーザから利用可能な共通の共有ワークスペースも用意する。名前空間は、Ｕｓｅｒ  Ｄａｔａの下にＰｒｉｖａｔｅおよびＳｈａｒｅｄ  Ｆｉｌｅ  Ｒｅｇｉｏｎの両方を持つように形成される。これにより、ユーザがシステムに対して行う問い合わせをＵｓｅｒ  Ｄａｔａによって形成されるアイテムドメインをルートとするようにでき、したがってすべての典型的な問い合わせにおいてプライベートアイテムと共有アイテムの両方を返す。図１２の名前空間を使用すると、ファイルシステム内のアイテムとやり取りする（新しい写真または音楽を取得する、ドキュメントを作成するなど）ときに、ユーザは、「これはプライベートかあるいは共有か？」という質問を概念的に考察して、適切なワークスペース内にそのアイテムを置くだけでよい。その後、Ｓｈａｒｅｄワークスペースのすべてのユーザは、Ｓｈａｒｅｄワークスペースへの共通の可視性を得られる。さらに、一方のユーザが他方のユーザがまだ望んでいたアイテムを削除する場合、第２のユーザがそれを取り出せるようにワークスペース毎に共有リサイクルビンがあり得る。
【００４３】
共通の共有ワークスペースに対するシナリオは、ホームユーザに限られない。企業ドメインでは、知識労働者は、同僚がプロジェクトに関して共同して働けるように共有ワークスペースをセットアップすることができる。ワークスペースには柔軟性があるため、ワークスペースのそれぞれのユーザは、アイテムを編成し、ワークスペース内のアイテムについて問い合わせを行うことができ、それらのアイテムの共通の全体的可視性を実現できる。
【００４４】
図１３は、基礎をなす編成構造からアイテムを除去し、および／またはファイルシステム１４８からアイテムを削除する方法を例示している。最初に、ステップ１３０１において、クライアントは、特定のファイルＩＤを持つアイテムを選択する。次に、ステップ１３０３において、クライアントは、ファイルシステム１４８からそのアイテムを完全に削除したいことを指示するか、または基礎をなす編成構造からそのアイテムを単に除去したいだけなのかを指示する。クライアントがステップ１３０３において「除去」を選択した場合、ステップ１３０５において、ファイルシステムマネージャは、そのアイテムのファイルＩＤが子列内に存在するエントリをＯＲＧテーブルから削除し、その方法は終了する。
【００４５】
クライアントがステップ１３０３において「削除」を選択した場合、ステップ１３０７において、ファイルシステムマネージャ６０１は、そのアイテムのファイルＩＤが親列に存在するＯＲＧテーブルエントリ毎に、その子が子であり、ＩＴＥＭの（複数の）親が親であるエントリをＯＲＧテーブル内に追加するが、ただし、ＯＲＧテーブル内にすでに存在していない場合である。使用可能な擬似コードは以下のとおりである。
For each ORG entry X where Xparent=file_ID(ITEM)
For each ORG entry Y where Ychild=file_ID(ITEM)
If ORG table does not have entry (Yparent, Xchild)
Then Add ORG table entry (Yparent, Xchild)
ＯＲＧテーブルをそれに応じて更新した後、ファイルシステムマネージャは、ステップ１３０９において、アイテムのファイルＩＤを親または子のいずれかとして参照するエントリをＯＲＧテーブルから削除する。最後に、ステップ１３１１において、ファイルシステムマネージャ６０１は、アイテムが格納されている場所を示すエントリをＬＯＣテーブルから削除する。ファイルシステムマネージャ６０１は、さらに、安全消去オペレーションを実行し、アイテムのロケーションに格納されているデータをガーベッジデータで上書きし、アンデリート操作を実行できないようにする。
【００４６】
それとは別に、ファイルシステムマネージャは、ステップ１３０７をスキップし、アイテムが親または子のいずれかであるエントリをステップ１３０９においてＯＲＧテーブルから単に除去することができる。この代替え方法の副作用として、削除されたアイテムのそれぞれの子は、子がファイルシステム１４８の編成構造内に残っている第２のアイテムを親としていない限り、ファイルシステム１４８の編成構造から除去される。
【００４７】
上記の方法は、選択されたアイテムおよびそのアイテムがポイントしている任意のアイテムが、基礎をなす編成構造から除去されるように例示されている。しかし、当業者であれば、編成構造からアイテムが除去されるときに、そのアイテムの子も編成構造から除去されることはない代替的な方法を使用できることを理解するであろう。この除去方法の実行の仕方は、除去と削除は２つの異なるプロセスであるという事実、つまり、削除プロセスは、記憶領域からアイテムをすっかり削除してしまうが、除去プロセスは、アイテムのライフタイムに影響を及ぼすことなく基礎をなす編成構造からアイテムを除去する（つまり、記憶領域からもファイルシステムからもそのアイテムを削除しない）という事実にとっては、派生的なことである。
【００４８】
従来のファイルシステムのナビゲーションツール、例えば、ワシントン州レドモンドのＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ社のＷｉｎｄｏｗｓ（登録商標）ＥＸＰＬＯＲＥＲというシステムナビゲーションツールでは、通常、ファイルシステムの編成構造内にあるファイルを表示するだけである。そのため、クライアントがファイルシステム１４８の編成構造からアイテムを除去した場合、つまり、アイテムがＯＲＧテーブル内に存在していない場合、そのアイテムは、ファイルシステムのナビゲーション表示の中に現れない。しかし、本発明の態様を使用すれば、クライアントは、編成構造内に現在ないアイテムを見つけるために、ファイルシステムマネージャ６０１に、すべてのフローティングまたはトップレベルアイテム（つまり、親のないアイテム）についての問い合わせを行うことができる。
【００４９】
ファイルシステム１４８は、ＯＲＧテーブル４０１により定義された編成構造に基づき、問い合わせドメインおよびセキュリティなどの追加機能を備えることができる。つまり、編成構造を定義することに加えて、ＯＲＧテーブル内の保持リンクは、問い合わせ可能なアイテムドメイン形成するために使用することも、または名前空間として参照することもできる。クライアントは、少なくとも１つの保持リンクに関わっている、親であるアイテムに問い合わせを行うことができる。例えば、図７を参照すると、「Ｉｔｅｍｓ  Ｆｏｒ  Ｍｙ  Ｔｒｉｐ」について問い合わせると、アイテムｉ３、ｉ４、ｉ５およびｉ８、さらにＫｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓが返される。重複アイテムは、一度だけ返されるのが好ましい。例えば、ｉ４は、Ｋｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓを親ともするが、１回だけ返されるのが好ましい。
【００５０】
ファイルシステム１４８の編成構造は、レガシーアプリケーションで使用するため名前空間を伝播するために、また新しいユーザに、ファイルシステム１４８とやり取りするための概念的に認識可能なユーザインタフェースを提供するためにも使用できる。例えば、図１２を参照すると、「Ｕ１」の下のアイテム「Ｕｓｅｒ  Ｄａｔａ」は、クライアントにより、＼Ｕｓｅｒｓ＼Ｕｌ＼Ｕｓｅｒ  Ｄａｔａとして参照されることが可能であり、それにより、概念的に馴染みのあるインタフェースをエンドユーザおよびレガシーアプリケーションに提供することができる。
【００５１】
ＯＲＧ４０１により定義された編成構造は、さらに、ファイルシステム１４８内のセキュリティ情報の伝播のためにも使用できる。つまり、セキュリティテーブル（図に示されていない）は、アイテムに対するセキュリティ情報を提供することが可能である。デフォルト設定では、ユーザが与えられたアイテムに対するアクセス権を持つ場合、ユーザは、デフォルト設定により、直接的か間接的かに関係なく、与えられたアイテムによってポイントされる他のすべてのアイテムへのアクセス権も持つ。
【００５２】
例えば、アイテムＵ１（図１２）に対するセキュリティは、ｕｓｅｒｎａｍｅ＝ＲｏｓｓのユーザのみがＵ１内のファイルにアクセスできることを示すことが可能である。Ｕ１を親とするアイテムＡｐｐ  ＤａｔａおよびＵｓｅｒ  Ｄａｔａに対し異なるセキュリティ情報が与えられない限り、Ｒｏｓｓのみがそれらのアイテムをも見ることができる。Ｐｒｉｖａｔｅ（Ｕ１を親とするＵｓｅｒ  Ｄａｔａを親とする）およびＳｈａｒｅｄについて同じことが成立するであろう。アイテムＵ２に対するセキュリティは、ｕｓｅｍａｍｅ＝ＪｏｒｄａｎのユーザのみがＵ２内のファイルにアクセスできることを示すことがある。Ｕ２を親とするアイテムＡｐｐ  ＤａｔａおよびＵｓｅｒ  Ｄａｔａに対し異なるセキュリティ情報が与えられない限り、Ｊｏｒｄａｎのみがそれらのアイテムをも見ることができる。Ｐｒｉｖａｔｅ（Ｕ２を親とするＵｓｅｒ  Ｄａｔａを親とする）およびＳｈａｒｅｄについて同じことが成立するであろう。アイテムＳｈａｒｅｄは競合するセキュリティ情報を持つように見えるが、セキュリティ情報は加法的であることが好ましい。そのため、アイテムＳｈａｒｅｄは、Ｕ１およびＵ２の両方からセキュリティ情報を受け取り、「ｏｎｌｙ  Ｒｏｓｓ  ａｎｄ  Ｊｏｒｄａｎ」を許可する。それとは別に、アイテムＵ１は「ｏｎｌｙ  Ｒｏｓｓ，ｎｏｔ  Ｔｏｍ」と同等の許可を持っていたと仮定する。アイテムＳｈａｒｅｄは、「ｏｎｌｙ  Ｒｏｓｓ  ａｎｄ  Ｊｏｒｄａｎ，ａｎｄ  ｎｏｔ  Ｔｏｍ」と同様のセキュリティ許可を受け取ることになる。
【００５３】
アイテムがＯＲＧから除去された場合、セキュリティは、除去されたアイテムへの伝播を停止する。例えば、図９に例示されているようにアイテムｉ５が「Ｋｅｙ  Ｓｌｉｄｅ  Ｄｅｃｋｓ」から除去される場合、ユーザは、もはや、ｉ５にアクセスする許可を与えられていない限り、ｉ５へのアクセス権を持たない。ただし、ファイルシステム１４８では、デフォルト設定により、クライアントがアイテムにアクセスすることを特に禁止されていない限り、クライアントはすべてのアイテムにアクセスできることを指定することが可能である。
【００５４】
リストは、上述のように名前空間を形成するので、Ｗｉｎｄｏｗｓ（登録商標）ＸＰまたは他のレガシーマシン（本明細書で説明されているようにファイル領域、ＤＡＧ、またはリストを操作する構成でない可能性のある）からユーザがファイルシステム１４８に接続した場合、そのユーザは、それらのリストをナビゲート可能なフォルダとして見えるものとして参照することができる。同様に、ユーザが（レガシーオペレーティングシステムまたはファイルシステム１４８に対応するシステム上の）リストのコンテキスト内で与えられたアイテムをダブルクリックすると、ファイルシステムは、要求側アプリケーションに、現在のリストにより形成された名前空間を与える。これにより、アプリケーションは必要なコンテキストを利用できる。例えば、ユーザがリスト「Ｔｏ  ｄｏ  Ｌｉｓｔ」を通じてアイテムｉ２を開こうとした場合、ファイルシステムは、「Ｔｏ  ｄｏ  ｌｉｓｔ」、つまり、＼Ｔｏ  Ｄｏ  Ｌｉｓｔ＼ｉ２を通じて形成されるパスをそのアプリケーションに返す。そのため、ユーザがアプリケーション内でコマンド「Ｆｉｌｅ｜Ｓａｖｅ  Ａｓ．．．」を使用することを選択した場合（例えば、アイテムの新しいコピーを作成するために）、アプリケーションは、ユーザに提示する正しいコンテキストを持つことになる。
【００５５】
本発明は、本発明を実施する目下好ましい方法を含む特定の実施例に関して説明されているが、当業者であれば、上述のシステムおよび手法のさまざまな変更形態および置換があることを理解するであろう。そこで、本発明の趣旨および範囲は、付属の請求項によって規定されているとおり、広い意味で解釈すべきである。
【図面の簡単な説明】
【００５６】
【図１】本発明の例示されている実施形態による媒体ユーザインタフェースの実装に好適な一般的オペレーティング環境を例示する図である。
【図２】知られているファイルシステムの典型的編成構造を例示する図である。
【図３】本発明の例示されている実施形態によるロケーションテーブル（ＬＯＣ）を示す図である。
【図４】本発明の例示されている実施形態による編成テーブル（ＯＲＧ）を示す図である。
【図５】図４に示されている編成テーブルによる非循環有向グラフ（ＤＡＧ）の編成構造を例示する図である。
【図６】本発明の例示されている実施形態によるファイルシステムを示すブロック図である。
【図７】本発明の例示されている実施形態によるファイル領域を示す図である。
【図８】図７の編成構造を定義する編成テーブルを例示する図である。
【図９】本発明の例示されている実施形態によるファイル領域を示す図である。
【図１０】図９の編成構造を定義する編成テーブルを例示する図である。
【図１１】本発明の例示されている実施形態による編成テーブルを示す図である。
【図１２】図１１に示されている編成テーブルによるファイル領域を例示する図である。
【図１３】本発明の例示されている実施形態によるファイルシステムに格納されるアイテムを管理する方法を示す図である。
【符号の説明】
【００５７】
１４１  ハードディスクドライブ
１５１  磁気ディスクドライブ
１５５  光ディスクドライブ
１８１  メモリデバイス
１６６  スタイラス
【図１】
2006139780.tif 000003
【図２】
2006139780.tif 000004
【図３】
2006139780.tif 000005
【図４】
2006139780.tif 000006
【図５】
2006139780.tif 000007
【図６】
2006139780.tif 000008
【図７】
2006139780.tif 000009
【図８】
2006139780.tif 000010
【図９】
2006139780.tif 000011
【図１０】
2006139780.tif 000012
【図１１】
2006139780.tif 000013
【図１２】
2006139780.tif 000014
【図１３】
2006139780.tif 000015