(57)【要約】【課題】階層的に編成されたシステムをエミュレートするための方法およびメカニズムが提供される。【解決手段】エミュレートされる階層的システムに任意の子を有する各項目は、インデックス中にインデックスエントリを有する。インデックス中のインデックスエントリは、インデックスエントリに関連付けられた項目間の階層的関係を反映するように互いにリンクされる。パスネーム分解は、パスネーム内のファイル名のシーケンスに従って、パスネームにおける項目に関連付けられるインデックスエントリ間の直接のリンクを辿ることによって行なわれる。インデックスエントリがこのようにリンクされているインデックスを使用することにより、それらのパスネームに基づいて項目にアクセスするプロセスが、大きく加速され、そのプロセス中に行なわれるディスクアクセスの数が、大きく低減される。【選択図】図１
2010152916.tif 000002
【特許請求の範囲】
【請求項１】
階層に属する複数個の項目をリレーショナルシステムにおいてインデックス付けするための方法であって、前記方法は、
インデックスを生成するステップと、
複数個の項目の第１の項目のための第１のインデックスエントリをインデックスに記憶するステップとを含み、前記第１の項目は、前記階層において第２の項目の子であり、前記方法はさらに、
複数個の項目の第２の項目のための第２のインデックスエントリをインデックスに記憶するステップを含み、前記インデックスエントリは、前記第１のインデックスエントリを前記インデックス中に位置づけるために前記第１のインデックスエントリへのリンクを含む、方法。
【請求項２】
前記第２の項目は、階層に複数個の子を有し、当該方法は、配列エントリの配列を前記第２のインデックスエントリ内に記憶するステップをさらに含み、配列エントリの前記配列は、前記第２の項目の子項目の各々のための配列エントリを含む、請求項１に記載の方法。
【請求項３】
前記インデックスに自身のインデックスエントリを有する子項目に対応する前記配列の各配列エントリに、子項目のためのインデックスエントリへのリンクを記憶するステップをさらに含む、請求項２に記載の方法。
【請求項４】
第１の項目に関連付けられる第１の名前および第２の項目に関連付けられる第２の名前を含む名前のシーケンスを受取るステップと、
前記第２の名前を用いて前記第２のインデックスエントリを位置付けるステップと、
前記第１の名前を用いて、前記第１の項目のための配列エントリを前記第２のインデックスエントリにおける前記配列内に位置付けるステップと、
前記第１の項目のための前記配列エントリから前記第１のインデックスエントリへの前記リンクを読出すステップと、
前記第１のインデックスエントリへの前記リンクを辿るステップとをさらに含む、請求項２に記載の方法。
【請求項５】
複数個の項目は、前記第２の項目の子である第３の項目を含み、前記方法は、
前記第３の項目のための第３のインデックスエントリを前記インデックス中に記憶するステップと、
前記第３の項目へのリンクを前記第２のインデックスエントリに記憶するステップとを含む、請求項１に記載の方法。
【請求項６】
第１のインデックスエントリは、前記第１の項目を位置付けるための情報を含み、
第２のインデックスエントリは、前記第２の項目を位置付けるための情報を含む、請求項１に記載の方法。
【請求項７】
第１の項目は前記インデックスの外部に記憶され、
第２のインデックスエントリは、前記インデックスの外部に前記第１の項目を位置付けるための情報を含む、請求項１に記載の方法。
【請求項８】
配列エントリの前記配列を、それらが関連付けられる子項目に基づいてソートされた順で保守するステップをさらに含む、請求項２に記載の方法。
【請求項９】
階層に従って互いに関連する複数個の項目にアクセスするためのインデックスが記憶されているコンピュータ読出可能媒体であって、前記複数個の項目の各項目は、ゼロまたはそれ以上の子項目を有し、
前記インデックスは、複数個のインデックスエントリを含み、
前記複数個のインデックスエントリの各インデックスエントリは、
前記複数個の項目の項目に対応し、かつ
前記項目の子項目に対応する、インデックス内のすべてのインデックスエントリにリンクされる、コンピュータ読出可能媒体。
【請求項１０】
複数個の項目は、前記インデックスの外部に電子的に記憶され、
前記複数個のインデックスエントリの各インデックスエントリは、前記インデックスの外部にインデックスエントリに対応する項目を位置付けるためのデータを記憶する、請求項９に記載のコンピュータ読出可能媒体。
【請求項１１】
複数個の項目は、テーブルの行に記憶され、
前記複数個のインデックスエントリの前記複数個の各インデックスエントリは、インデックスエントリに対応する項目のための行を前記テーブルに位置付けるためのデータを記憶する、請求項１０に記載のコンピュータ読出可能媒体。
【請求項１２】
複数個の項目は、前記インデックスの外部に電子的に記憶され、
前記複数個のインデックスエントリの各インデックスエントリは、前記インデックスの外部にインデックスエントリに対応する項目の子項目を位置付けるためのデータを記憶する、請求項９に記載のコンピュータ読出可能媒体。
【請求項１３】
複数個の項目は、テーブルの行に記憶され、
前記複数個のインデックスエントリの前記複数個の各インデックスエントリは、インデックスエントリに対応する項目の子項目のための行を前記テーブル中に位置付けるためのデータを記憶する、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１４】
子項目を有する項目に対応する各インデックスエントリは、配列エントリの配列を含み、配列における各配列エントリは、項目の子項目についての情報を記憶する、請求項９に記載のコンピュータ読出可能媒体。
【請求項１５】
各子項目のための配列エントリは、子項目のための名前を記憶する、請求項１４に記載のコンピュータ読出可能媒体。
【請求項１６】
配列内の配列エントリは、子項目の名前に基づいてソートされた順で保守される、請求項１４に記載のコンピュータ読出可能媒体。
【請求項１７】
各子項目のための配列エントリは、
インデックスの外部に子項目を位置付けるためのデータと、
自身のインデックスエントリを有する各子項目について、子項目のインデックスエントリへのリンクとを記憶する、請求項１４に記載のコンピュータ読出可能媒体。
【請求項１８】
項目間の親子関係を確立する階層に属する項目を位置付けるための方法であって、前記方法は、
ターゲット項目への階層を通るパスを識別する識別子のシーケンスを受取るステップと、
階層的インデックスを用いて、
前記階層的インデックス内に第１の項目のためのインデックスエントリを位置付けるステップを行い、前記第１の項目は前記識別子のシーケンス中に第１の識別子によって識別される項目であり、さらに、
前記第１の項目のための前記インデックスエントリで始まり、前記識別子のシーケンスによって決められるシーケンスにおいて、インデックスエントリ間のリンクを辿り、ターゲット項目についての情報がどこに位置するかを示す特定のインデックスエントリに達するステップを行なうことによって前記ターゲット項目についての情報を位置付けるステップと、
前記特定のインデックスエントリ中の情報を用いて前記ターゲット項目についての前記情報を位置付けアクセスするステップとを含む、方法。
【請求項１９】
リンクを辿るステップは、
親項目のためのインデックスエントリ内で、配列を探索して特定の子項目のための配列エントリを位置付けるステップを含み、配列は、親項目の各子項目のための配列エントリを含む、請求項１８に記載の方法。
【請求項２０】
親項目は、前記識別子のシーケンス中の識別子に対応し、
特定の子項目は、前記識別子のシーケンス中の識別子に対応し、
前記親項目のための識別子は、前記識別子のシーケンス中の前記特定の子項目のための識別子のすぐ前に置かれる、請求項１９に記載の方法。
【請求項２１】
項目間の親子関係を確立する階層に属する項目を位置付けるための命令のシーケンスが記憶されるコンピュータ読出可能媒体であって、命令のシーケンスは、
ターゲット項目への階層を通るパスを識別する識別子のシーケンスを受取るステップと、
階層的インデックスを用いて、
前記階層的インデックス内に第１の項目のためのインデックスエントリを位置付けるステップを行い、前記第１の項目は、前記識別子のシーケンス中の第１の識別子によって識別される項目であり、さらに、
前記第１の項目のための前記インデックスエントリで始まり、前記識別子のシーケンスによって決められるシーケンスにおいて、インデックスエントリ間のリンクを辿り、ターゲット項目についての情報がどこに位置するかを示す特定のインデックスに達するステップを行なうことによって前記ターゲット項目についての情報を位置付けるステップと、
前記特定のインデックスエントリ中の情報を用いて前記ターゲット項目についての前記情報を位置付けアクセスするステップとを行なうための命令を含む、コンピュータ読出可能媒体。
【請求項２２】
リンクを辿るステップは、
親項目のためのインデックスエントリ内で、配列を探索して特定の子項目のための配列エントリを位置付けるステップを含み、配列は、親項目の各子項目のための配列エントリを含む、請求項２１に記載のコンピュータ読出可能媒体。
【請求項２３】
親項目は、前記識別子のシーケンス中の識別子に対応し、
特定の子項目は、前記識別子のシーケンス中の識別子に対応し、
前記親項目のための識別子は、前記識別子のシーケンス中の前記特定の子項目のための識別子のすぐ前に置かれる、請求項２２に記載のコンピュータ読出可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、一般的にはデータベースシステムに関し、特に、リレーショナルデータベースシステムにおいて、階層的に編成された情報にアクセスするために階層的インデックスを使用することに関する。
【０００２】
人は、情報をカテゴリに編成する傾向がある。情報が編成されているカテゴリはそれ自体、典型的には、何らかの形の階層に互いに相関して編成されている。たとえば、個々の動物は、種に属し、種は属に属し、属は科に属し、科は目に属し、目は網に属する。
【０００３】
コンピュータシステムの到来により、階層的編成に対するこの人間の要望を大きく反映した、電子的情報を記憶するための技術が開発されてきた。たとえば、従来のコンピュータファイルシステムは、典型的には、階層ベース編成の原理を用いて実現されている。具体的には、典型的なファイルシステムは、階層状に配置されたディレクトリと、ディレクトリに記憶されたドキュメントとを有する。理想的には、ディレクトリ間の階層的関係は、ディレクトリに割当てられている意味間の、何らかの直感でわかる関係を反映している。同様に、各ドキュメントが、ドキュメントの内容とドキュメントが記憶されているディレクトリに割当てられている意味との間の何らかの直感でわかる関係に基づいて、ディレクトリに記憶されることが理想的である。
【０００４】
図１は、典型的なファイルシステムの一例を示す。例示されるファイルシステムは、階層状に配置された多くのディレクトリを含む。２つのドキュメント１１８および１２２がディレクトリに記憶されている。具体的には、ドキュメント１１１８および１２２は、その両方が“Example.doc”と題されているが、それぞれ“Word”および“App4”と題されているディレクトリ１１６および１２４にそれぞれ記憶される。
【０００５】
ディレクトリ階層において、ディレクトリ１１６は、“Windows”と題されるディレクトリ１１４の子であり、ディレクトリ１１４はディレクトリ１１０の子である。同様に、ディレクトリ１２４は、“ＶＭＳ”と題されるディレクトリ１２６の子であり、ディレクトリ１２６はディレクトリ１１０の子である。ディレクトリ１１０は、すべての他のディレクトリが下に降りていくディレクトリであるので、“ルート”ディレクトリと呼ばれる。多くのシステムにおいて、記号“／”は、ルートディレクトリを参照するために使用される。
【０００６】
電子的情報が階層状に編成されるとき、情報の各項目は、項目を含むエンティティへの階層を通る“パス”を辿ることによって位置付けされ得る。階層的ファイルシステム内で、項目へのパスは、ルートディレクトリにおいて始まり、ディレクトリの階層を下り、やがて関心のある項目を含むディレクトリに達する。たとえば、ファイル１１８へのパスは、ディレクトリ１１０、１１４および１１６から、この順でなる。
【０００７】
階層的記憶システムは、しばしば、異なった項目が同じ名前を有することを可能にする。たとえば、図１に示すファイルシステムにおいて、ドキュメント１１８および１２２の両方が“Example.doc”と題される。したがって、所与のドキュメントを明白に識別するために、単にドキュメントの名前以上のものが必要とされる。
【０００８】
階層的記憶システムに記憶された情報の特定の項目を識別しかつ位置付けるための便利な方法は、“パスネーム”の使用によるものである。パスネームは、項目への階層を通るパスに基づいて項目を一意に識別する簡便な方法である。パスネームは、名前のシーケンスから構成される。ファイルシステムにおいては、名前のシーケンスにおける各名前が“ファイル名”である。ディレクトリおよびドキュメントの両方が“ファイル”であると見なされるので、“ファイル名”という言葉は、ディレクトリの名前およびドキュメントの名前の両方のことをいう。
【０００９】
ファイルシステム内では、所与のパスネームにおけるファイル名のシーケンスは、ルートディレクトリの名前で始まり、ルートディレクトリから関心のある項目へのパスに沿ってすべてのディレクトリの名前を含み、関心のある項目の名前で終わる。典型的には、横方向に向かうディレクトリのリストは、互いに連結され、パスネームを作るためにいくつかの種類の分離文字句読点（たとえば、′／′，′＼′または′；′）を伴う。したがって、ドキュメント１１８のためのパスネームは、/Windows/Word/Example.docであり、ドキュメント１２２のためのパスネームは、/VMS/App4/Example.docである。
【００１０】
ディレクトリ（ファイル）とそれらに含まれた内容との関係は、異なった種類の階層的に編成されたシステム間で大きく異なる。Windows（Ｒ）およびＤＯＳファイルシステムなどの、さまざまな実現化例によって採用されるモデルの１つは、各ファイルが正確に１つの親を有し、ツリーを形成することを必要とする。より複雑なモデルにおいて、ハードリンクが使用されるＵＮＩＸ（Ｒ）ファイルシステムにおいてのように、階層は、有向グラフの形を取り、ファイルは複数の親を有することができる。
【００１１】
電子的情報を編成するための階層的方策とは対照的に、リレーショナルデータベースは、行と列とから構成されるテーブルに情報を記憶する。各行は、一意のRowＩＤによって識別される。各列は、レコードの属性を表わし、各行は、特定のレコードを表わす。データは、データベースを管理するデータベース管理システム（ＤＢＭＳ）にクエリーを提出することによりデータベースから検索される。
【００１２】
各種の記憶システムは、利点および限界を有する。階層的に編成された記憶システムは、簡素で、直感でわかり、かつ実現するのに簡単であり、ほとんどのアプリケーションプログラムによって使用されている標準のモデルである。残念ながら、階層的編成の簡素さは、複雑なデータ検索操作に必要とされるサポートを提供しない。たとえば、特定のファイル名を有する特定の日に生成されたすべてのドキュメントを検索するために、あらゆるディレクトリの内容が調べられなければならないことがある。すべてのディレクトリが探索されなければならないので、階層的編成は、検索プロセスを容易にする役には立たない。
【００１３】
リレーショナルデータベースシステムは、大量の情報を記憶し、かつ非常に柔軟な態様でデータにアクセスするのによく適している。階層的に編成されたシステムに対して、さらに複雑な探索基準に一致するデータでも、リレーショナルデータベースシステムから簡単かつ効率的に検索され得る。しかしながら、クエリーを公式化しデータベースサーバに提出するプロセスは、ディレクトリの階層を単に移ることより直感的ではなく、多くのコンピュータユーザの技術的に快適なレベルを超えている。
【００１４】
過去には、階層的に編成されたシステムとリレーショナルに編成されたシステムとは、互換性のない異なった態様で実現されていた。しかしながら、あるさらなる処理により、リレーショナルに編成されたシステムは、階層的に編成されたシステムをエミュレートすることができる。この種のエミュレーションは、リレーショナルシステムの記憶能力および柔軟性が必要とされるが、階層的システムの直感性および遍在性が所望されるとき、特に望ましい。
【００１５】
そのようなエミュレーションは、２つのリレーショナルテーブル：“File”テーブルおよび“Directory＿links”テーブルの使用により実現され得る。Fileテーブルは、エミュレートされる階層的システムにおける各ファイルに関連する情報を記憶する。ドキュメントであるファイルについて、Fileテーブルは、（ラージバイナリオブジェクト（ＢＬＯＢ）の形で）ファイルのボディ、またはドキュメントのボディへのポインタのいずれかをさらに記憶する。Directory＿linksテーブルは、ファイル間の親子関係を示すリンク情報のすべてを記憶する。
【００１６】
階層的記憶システムをエミュレートするためにこれらの２つのテーブルがいかに使用され得るかを例示するために、図１の階層的構造を有するファイルシステムがデータベースにおいて実現されていると仮定する。図１のファイルシステムを以下のように例示することができる（括弧内に示す一意のＩＤが、各ファイルを一意に識別するためにシステムによって割当てられる）。
【００１７】
【数１】
2010152916.tif 000003
【００１８】
図２はファイルテーブル２１０を示し、図３はディレクトリリンクテーブル３１０を示すが、これらは、リレーショナルデータベースシステムにおいて、図１のファイルシステムをエミュレートするためにコンピュータシステムによって使用され得る。ファイルテーブル２１０は、システム中の各ファイルのためのエントリを含む。各エントリは、RowＩＤ、ファイルＩＤ、名前、およびボディ列、および、修正データ列（加えて、生成日、アクセス許可情報などの他のシステム維持情報）を含む。
【００１９】
FileＩＤは、システムによって各ファイルに割当てられた一意のＩＤであり、名前は、ファイルに割当てられた名前であるが、一意である必要はなく、ボディは、ファイルの内容が記憶されているフィールドである。ボディフィールドは、バイナリラージオブジェクト（ＢＬＯＢ）の形でファイルの実際の内容を記憶するか、または、ファイルの内容へのポインタを記憶し得る。エントリが内容を有さないファイル（たとえばディレクトリ）のためのものである場合、ボディフィールドはヌルである。上記の例では、Example.docと題する２つのみのドキュメントが内容を有し、したがって、他のエントリのすべてのためのボディフィールドはヌルである。
【００２０】
ディレクトリリンクテーブル３１０において、各エントリは、図１のファイルシステムにおけるファイル間の各リンクごとに記憶される。各エントリは、親ＩＤ、子ＩＤおよびchild＿nameフィールドを含む。各リンクごとに、親ＩＤフィールドは、そのリンクのための親ファイルであるファイルを特定し、子ＩＤフィールドは、そのリンクのための子ファイルであるファイルを特定し、child＿nameフィールドは、そのリンクにおける子ファイルの名前を特定する。したがって、たとえば、ルートディレクトリ１１０とWindowsディレクトリ１１４との間のリンクのためのエントリにおいて、ディレクトリリンクテーブル３１０は、Ｘ１（ルートディレクトリのFileＩＤ）が親ＩＤであり、Ｘ２（Windows）ディレクトリのFileＩＤ）が子ＩＤであり、“Windows”がchild＿nameであることを特定する。
【００２１】
図１のファイルシステムを実現するためにこれらの２つのテーブルの情報がいかに使用され得るかを例示するために、ドキュメント１１８にアクセスする必要があると仮定する。上述したとおり、ドキュメント１１８は、パス：/Windows/Word/Example.docを有する。このファイルにアクセスするために、ＤＢＭＳは、ディレクトリリンクテーブル３１０の最初のスキャンを行ない、ルートディレクトリ１１０が親ファイルでありかつWindowsディレクトリ１１４が子ファイルであるエントリを見付ける。これを行なうために、ＤＢＭＳは、以下のＳＱＬステートメントのようなものを実行する。
【００２２】
【数２】
2010152916.tif 000004
【００２３】
このクエリーは、この場合には（Windowsディレクトリ１１４のための）Ｘ２である、子ファイルのＩＤを戻す。子ファイルのＩＤを獲得した後、ＤＢＭＳは、ディレクトリリンクテーブル３１０の第２のスキャンを行ない、今回は、親ファイルがWindowsディレクトリ１１４でありかつ子ファイルがWordディレクトリ１１６であるエントリを探す。これは、以下のセレクトステートメントを実行することによって達成される。
【００２４】
【数３】
2010152916.tif 000005
【００２５】
このクエリーは、この例ではＸ３である、Wordディレクトリ１１６のＩＤを戻す。この情報により、ＤＢＭＳは、ディレクトリリンクテーブル３１０の第３のスキャンを行ない、今回は、親ファイルがWordディレクトリ１１６でありかつ子ファイルがExample.docドキュメント１１８であるエントリを探索する。これは、以下のセレクトステートメントにより達成される。
【００２６】
【数４】
2010152916.tif 000006
【００２７】
このプロセスの終わりに、ドキュメント１１８のＩＤが決定されることになる。このＩＤを主キーとして用いて、ファイルテーブル２１０における適切なエントリが位置付けられ、ドキュメント１１８の内容がボディフィールドからアクセスされる。したがって、この技術を用いて、テーブル２１０などのリレーショナル構造に実際に記憶されているファイルが、それらが階層的に編成された構造に記憶されたかの如く、パスネームを用いて位置付けられアクセスされ得る。パスネームを提出してファイルを位置付けるユーザは、リレーショナルシステムの複雑さを理解する必要がない。反対に、ファイルはリレーショナルシステムに記憶されているので、ファイルは、リレーショナルシステムに慣れているユーザによってより洗練された方法で効率的にアクセスされ得る。
【００２８】
上に概略したプロセスは、パスネーム分解のプロセスであり、ファイルのパスネームが、ファイルデータが記憶されているディスク上の場所に分解される。記載される方法は、リレーショナルデータベースを用いてファイルシステムを実現するのに有効であり、リレーショナル理論に適した方法である。しかし、残念ながら、このプロセスは、複数のクエリーの実行を必要とし、そのため、ディレクトリリンクテーブル３１０の複数のスキャンを必要とする。具体的には、ファイルのパスを分解するために“ｉ”回のスキャンが必要である、ただし、ｉは、パスのレベルの数である（各中間のディレクトリがレベルを加える）。これは、性能上の問題となり得る。
【００２９】
性能評価を簡素化する目的で、パスネーム分解の性能が、アクセスされなければならないディスクブロックの数に直接比例するものと仮定する。（これは、ディスクアクセスがメモリアクセスより１００倍遅いオーダであり、大きいファイルシステムについては、データのほとんどがディスク上にあるものと仮定できるからである。）従来のＢＴＲＥＥインデックスがdirectory＿linksテーブル３１０に構築されていると仮定すると、ＤＢＭＳがテーブルの１回のスキャンにおいて行なわなければならないディスクブロックアクセスの回数は、ｌｏｇ（ｎ）／ｍであり、ただし、ｎはテーブル中のエントリの数であり、ｍはブロック当りのエントリの数である。したがって、上述のパスネーム分解技術を用いると、ＤＢＭＳがファイルにアクセスするのに行なわければならないアクセスの平均回数は、ｉ＊ｌｏｇ（ｎ）／ｍとなる。
【００３０】
多数のリンクおよび多数のリンクレベルを有する複雑なファイルシステムについては、ディスクアクセスの回数はかなり大きいものとなる可能性がある。Ｉ／Ｏ動作は、他の種類の動作と比べて非常に遅いので、多数のディスクアクセスを有することは、システム性能を大きく落とす可能性がある。一般的には、記載した、パスネーム分解方法は、大きくて複雑なファイルシステムに適用されるとかなり遅い。
【００３１】
テーブルのデータ構造は、リレーショナルアプリケーションからファイルシステムデータへの簡単なアクセスについて適切であるが、データベースによって使用される標準のタイプのインデックスは、この態様で編成されたデータへの、効率的なパスネームベースのアクセスについては遅すぎる。そこで、必要とされるのは、リレーショナルに編成されたシステムを用いて階層的に編成されたシステムをエミュレートするが、それらのパスネームに基づいてそれらがアクセスされるときシステム中の項目を位置付けるのに必要なディスクアクセスの数を低減する、装置、システムまたは方法である。
【発明の概要】
【発明が解決しようとする課題】
【００３２】
パスネームに基づいてリレーショナルシステム中の情報に効率的にアクセスするために、階層的インデックスを生成、保守および使用し、それにより階層的に編成されたシステムをエミュレートするための方法およびメカニズムが提供される。
【課題を解決するための手段】
【００３３】
この発明のある局面に従えば、エミュレートされる階層的システムに任意の子を有する各項目は、インデックス中にインデックスエントリを有する。インデックス中のインデックスエントリは、インデックスエントリと関連付けられた項目間の階層的関係を反映するように互いにリンクされる。具体的には、２つのインデックスエントリに関連付けられた項目間に親子関係が存在するならば、親項目に関連付けられたインデックスエントリは、子項目に関係付けられたインデックスエントリへの直接のリンクを有する。
【００３４】
この発明の別の局面に従えば、パスネーム分解は、パスネーム内のファイル名のシーケンスに従って、パスネーム中の項目と関連付けられるインデックスエントリ間の直接のリンクを辿ることにより行なわれる。インデックスエントリがこのようにリンクされているインデックスを用いることにより、それらのパスネームに基づいて項目にアクセスするプロセスは、大きく加速され、そのプロセス中に行なわれるディスクアクセスの数は、大きく低減される。
【００３５】
この発明は、添付の図面の、同様の参照番号が同様の要素を参照する、図において、例として例示されるが、限定されるものではない。
【図面の簡単な説明】
【００３６】
【図１】階層的に編成されたファイルシステムを例示するブロック図である。
【図２】リレーショナルに編成されたシステムにおいて階層的に編成されたシステムをエミュレートするために使用され得るファイルテーブル２１０の図である。
【図３】図２のファイルテーブル２１０に関連して、階層的に編成されたシステムをエミュレートするために使用され得るディレクトリリンクテーブル３１０の図である。
【図４】この発明のある実施例に従って階層的インデックスを実現するために使用され得るデータベースシステムを例示するブロック図である。
【図５】リレーショナルシステム内でエミュレートされた階層的システムの性能を向上させるために使用され得る階層的インデックスの図である。
【図６Ａ】項目の生成の際に階層的インデックス５１０がいかにして保守されるかを例示する流れ図である。
【図６Ｂ】項目の削除の際に階層的インデックス５１０がいかにして保守されるかを例示する流れ図である。
【図７】この発明の実施例に従って階層的インデックス５１０を用いてパスネームを分解するためのプロセスを示す流れ図である。
【図８】この発明に従う装置、システムおよび方法を実現するために使用され得るハードウェアシステムの一例を例示するブロック図である。
【発明を実施するための形態】
【００３７】
リレーショナルシステムに記憶されたデータへの、効率的なパスネームベースのアクセスを提供するための方法および装置が記載される。以下の説明において、説明の目的のために、多くの特定の詳細が、この発明を完全に理解するために述べられる。しかしながら、当業者には、この発明がこれらの特定の詳細なしに実施され得ることが明らかである。他の場合には、この発明を不必要に不明瞭にすることを回避するために、周知の構造および装置がブロック図に示される。
【００３８】
機能概要
パスネームに基づいてリレーショナルシステムにおける情報に効率的にアクセスするために階層的インデックスを生成、保守および使用し、それにより階層的に編成されたシステムをエミュレートするための技術をここに記載する。エミュレートされる階層的システム中に任意の子を有する各項目は、インデックス中にインデックスエントリを有する。インデックス中のインデックスエントリは、インデックスエントリに関連付けられた項目間の階層的関係を反映するように互いにリンクされる。具体的には、２つのインデックスエントリに関連付けられた項目間に親子関係が存在するならば、親項目に関連付けられたインデックスエントリは、子項目に関連付けられたインデックスエントリへの直接のリンクを有する。
【００３９】
したがって、パスネーム分解は、パスネーム内のファイル名のシーケンスに従って、パスネーム中の項目に関連付けられたインデックスエントリ間の直接のリンクを辿ることにより行なわれる。インデックスエントリがこのようにリンクされたインデックスを用いることにより、それらのパスネームに基づいて項目にアクセスするプロセスは、大きく加速され、そのプロセス中に行なわれるディスクアクセスの数は、大きく低減される。
【００４０】
データベースアーキテクチャ
図４は、この発明の原理に従って階層的インデックスを生成、使用および保守するために使用され得るデータベースアーキテクチャを示すブロック図である。アーキテクチャは、ユーザインターフェイス４１０と、ＤＢＭＳ４１２と、データベース４１４とを含む。ＤＢＭＳ４１２は、ユーザインターフェイス４１０を介してユーザと対話し、ユーザ入力に従ってデータベース４１４にアクセスし保守する。ＤＢＭＳ４１２は、他のシステム（図示せず）とも対話し得る。
【００４１】
ＤＢＭＳ４１２は、この発明の原理に従ってデータベース４１４において階層的インデックスを生成、使用および保守する。階層的インデックスの生成、使用および保守を、以下により詳細に記載する。
【００４２】
一般的には、ＤＢＭＳ４１２は、１つ以上のテーブルに情報を編成することによりデータベースを生成する。テーブルの編成を定義と呼ぶ。インデックスは、テーブル中の特定の情報により速くアクセスするために使用される構造である。したがって、テーブル定義は、データへのいかなるアクセスメカニズム（名前、ＩＤ、日付などによる探索）をもサポートし、それに対しインデックスは、特定のアクセス方法のために設計される。インデックス自体は、一般的には、データの正式のソースではなく、正式のデータを記憶するテーブルのディスクアドレスへのポインタを含む。
【００４３】
階層的インデックス
この発明に従う階層的インデックスは、パスネームによって特定されるとおり、親項目からそれらの子へ移動する、階層的システムのパスネームベースのアクセス方法をサポートする。ある実施例に従えば、この発明の原理に従う階層的インデックスは、以下の３つのフィールド：RowＩＤ、FileＩＤ、およびDir＿entry＿list（配列として記憶される）を含むインデックスエントリを採用する。
【００４４】
図５は、データベース中の階層的記憶システムをエミュレートするために使用され得る、この発明に従う階層的インデックス５１０を示す。階層的インデックス５１０は、テーブルである。RowＩＤ列は、ＤＢＭＳ４１２がディスク上に行を位置付けることを可能にするディスクアドレスを特定する、システム生成Ｉｄを含む。リレーショナルデータベースシステムに依存して、RowＩＤは、ディスクドライブ上に記憶されたデータを位置付けるためにＤＢＭＳが使用する、暗黙的に定義されたフィールドであり得る。インデックスエントリのFileＩＤフィールドは、インデックスエントリに関連付けられるファイルのFileＩＤを記憶する。
【００４５】
この発明のある実施例に従えば、階層的インデックス５１０は、子を有する項目のためのインデックスエントリのみを記憶する。したがって、エミュレートされる階層的ファイルシステムにおいては、階層的インデックス５１０中にインデックスエントリを有する項目は、他のディレクトリへの親でありかつ／または現在のところドキュメントを記憶しているディレクトリのみである。子を有さない項目（Example.doc、Access、App1、App2、App3）は、好ましくは、含まれない。所与のファイルのためのインデックスエントリのDir＿entry＿listフィールドは、配列状に、所与のファイルの子ファイルの各々のための“配列エントリ”を記憶する。
【００４６】
たとえば、インデックスエントリ５１２は、Windowsディレクトリ１１４のためのものである。Wordディレクトリ１１６およびAccessディレクトリ１２０は、Windowsディレクトリ１１４の子である。したがって、Windowsディレクトリ１１４のためのインデックスエントリ５１２のDir＿entry＿listフィールドは、Wordディレクトリ１１６のための配列エントリおよびAccessディレクトリ１２０のための配列エントリを含む。
【００４７】
ある実施例に従えば、Dir＿entry＿listフィールドが各子ごとに記憶している特定の情報は、子のファイル名および子のFileＩＤを含む。階層的インデックス５１０に自身のエントリを有する子について、Dir＿entry＿listフィールドは、子のインデックスエントリのRowＩＤも記憶する。たとえば、Wordディレクトリ１１６は、階層的インデックス５１０中にそれ自身のエントリ（エントリ５１４）を有する。したがって、インデックスエントリ５１２のDir＿entry＿listフィールドは、ディレクトリ１１６の名前（“Word”）と、階層的インデックス５１０におけるディレクトリ１１６のためのインデックスエントリのRowＩＤ（“Ｙ３”）と、ディレクトリ１１６のFileＩＤ（“Ｘ３”）とを含む。より詳細に記載するように、Dir＿entry＿listフィールド中に含まれる情報は、パスネームに基づく情報のアクセスをより高速かつ簡単なものにする。
【００４８】
階層的インデックスのいくつかの主要な原理は以下のとおりである。
・最も頻繁に使用されるファイルシステム動作（パスネーム分解、ディレクトリリスティング）は、特定のディレクトリが参照されるたびにそのディレクトリにおけるエントリの多くを見る必要があるので、所与のディレクトリのためのインデックスエントリ中のDir＿entry＿list情報は、可能な限り少数のディスクブロック内にともに保持される。言い換えれば、ディレクトリエントリは高い、参照の局所性を有するべきである、というのも特定のディレクトリエントリが参照されるとき、同じディレクトリ中の他のエントリも参照されやすいからである。
【００４９】
・階層的インデックスのインデックスエントリに記憶された情報は、特定のディスクブロックにおけるエントリの最大数に適合するために、最小に保持されなければならない。ディレクトリエントリを配列状にともにグループ化することは、それらが存在しているディレクトリを識別するキーを複製する必要がないということを意味する；ディレクトリ中のエントリのすべては、同じキーを共有する。これは、Directory＿linksテーブル（テーブル３１０）に示す典型的なリレーショナルテーブルモデルとは対照的なものである。
【００５０】
・パスネームを分解するために必要とされる時間は、ファイルシステムにおけるファイルの総数ではなく、パスにおけるディレクトリの数に比例するべきである。これにより、ユーザは、頻繁にアクセスされるファイルを、ファイルシステムのツリーの上方へ保持することが可能であり、アクセス時間が低減される。
【００５１】
これらの要素はすべて、ｉ個のノードおよびディレクトリからなるＵＮＩＸ（Ｒ）システムなどの、典型的なファイルシステムディレクトリ構造に存在している。ここに記載するような、階層的インデックスの使用は、これらの目的をリレーショナルデータベースが理解しかつ問合せすることのできる構造と両立させ、データベースサーバが、パスネーム分解において使用されるもの以外の態様でファイルの特別な探索を行なうことを可能にする。これを行なうために、インデックスというデータベース概念：特定の方法（この場合には、階層ツリーにおけるパスネームの分解）によりアクセスを最適化するよう設計されるのとは異なった態様で別個のデータ構造に配置された、下にある情報（この場合には、ファイルデータ）の部分の複製、を使用しなければならない。
【００５２】
階層的インデックスの使用
階層的インデックス１５０をいかにして使用して、ファイルのパスネームに基づいてファイルにアクセスするかを、図７のフローチャートを参照して記載する。説明の目的のために、ドキュメント１１８は、そのパスネームを介してアクセスされるべきものと仮定する。このファイルのためのパスネームは、/Windows/Word/Example.docであるが、以下これを“入力パスネーム”と呼ぶ。このパスネームが与えられると、パスネーム分解プロセスは、階層的インデックス５１０内に、入力パスネームにおける第１の名前のためのインデックスエントリを位置付けることにより開始する。ファイルシステムの場合には、パスネームにおける第１の名前は、ルートディレクトリである。したがって、エミュレートされるファイルシステム内にファイルを位置付けるためのパスネーム分解プロセスは、ルートディレクトリ１１０のインデックスエントリ５０８を位置付けることにより始まる（ステップ７００）。すべてのパスネーム分解動作は、ルートディレクトリのインデックスエントリ５０８にアクセスすることにより始まるので、ルートディレクトリ１１０のためのインデックスエントリ（インデックスエントリ５０８）の場所を示すデータは、探索ごとの開始においてルートディレクトリのインデックスエントリ５０８をす速く位置付けるために、階層的インデックスの外部の便利な場所に維持され得る。
【００５３】
ルートディレクトリ１１０のためのインデックスエントリ５０８が位置付けられると、ＤＢＭＳは、入力パスネームにさらにファイル名があるかどうかを判断する（ステップ７０２）。入力パスネームにさらにファイル名がなければ、制御はステップ７２０に進み、インデックスエントリ５０８に記憶されたFileＩＤを用いて、ファイルテーブル２１０におけるルートディレクトリエントリを参照する。
【００５４】
この例では、ファイル名“Windows”は、入力パスネームにおけるルートディレクトリ記号“／”の後に続く。したがって、制御はステップ７０４に進む。ステップ７０４において、次のファイル名（たとえば、“Windows”）が入力パスネームから選択される。ステップ７０６において、ＤＢＭＳは、インデックスエントリ５０８のDir＿entry＿list列を調べて、選択されたファイル名に付随する配列エントリを位置付ける。
【００５５】
この例では、入力パスネームにおいてルートディレクトリの後に続くファイル名は、“Windows”である。したがって、ステップ７０６は、ファイル名“Windows”のための配列エントリのためにインデックスエントリ５０８のDir＿entry＿listを探索することを伴う。Dir＿entry＿listが、選択されたファイル名のための配列エントリを含んでいなければ、制御はステップ７０８からステップ７１０に進み、ここでエラーが生成され、入力パスネームが有効でないことを示す。この例では、インデックスエントリ５０８のDir＿entry＿listは、“Windows”のための配列エントリを含んでいる。したがって、制御はステップ７０８からステップ７２２へ移る。
【００５６】
インデックスエントリ５０８のDir＿entry＿listにおける情報は、ルートディレクトリ１１０の子の１つが実際に“Windows”と名付けられたファイルであることを示す。さらに、Dir＿entry＿list配列エントリは、この子についての以下の情報を含む：それは、RowＩＤ  Ｙ２に位置するインデックスエントリを有し、そのFileＩＤはＸ２である。
【００５７】
ステップ７２２において、入力パスネームにさらにファイル名があるかどうかが判断される。さらにファイル名がなければ、制御はステップ７２２からステップ７２０へと移る。この例では、“Windows”は最後のファイル名ではないので、制御は代わりにステップ７２４へと移る。
【００５８】
“Windows”は、入力パスの最後のファイル名ではないので、Dir＿entry＿listに含まれるFileＩＤ情報は、このパス分解動作中に使用されない。Windowsディレクトリ１１４は、特定されたパスの一部にすぎず、ターゲットではないので、ファイルテーブル２１０は、この時点では調べられない。代わりに、ステップ７２４において、インデックスエントリ５０８のDir＿entry＿listに見付けられる、“Windows”のためのRowＩＤ（Ｙ２）を用いて、Windowsディレクトリ１１４のためのインデックスエントリ（インデックスエントリ５１２）を位置付ける。
【００５９】
インデックスエントリ５１２のDir＿entry＿listを調べると、システムは、入力パスネームにおける次のファイル名を探索する（ステップ７０４および７０６）。この例において、ファイル名“Word”は、入力パスネームにおいてファイル名“Windows”の後に続く。したがって、システムは、“Word”のための配列エントリのために、インデックスエントリ５１２のDir＿entry＿listを探索する。そのようなエントリはインデックスエントリ５１２のDir＿entry＿listに存在し、“Windows”が“Word”と名付けられた子を実際に有することを示す（ステップ７０８）。ステップ７２２において、入力パスにさらにファイル名が存在することが判断され、制御はステップ７２４へ進む。
【００６０】
“Word”のための配列エントリを見付けると、システムは、配列エントリ中の情報を読出し、Wordディレクトリ１１６のためのインデックスエントリをRowＩＤ  Ｙ３で階層的インデックス５１０中に見付けることができ、Wordディレクトリ１１６に付随する特定の情報を行Ｘ３でファイルテーブル２１０中に見付けることができることを判断する。Wordディレクトリ１１６は特定されたパスの一部にすぎずターゲットではないので、ファイルテーブル２１０は調べられない。代わりに、システムは、RowＩＤ（Ｙ３）を用いて、Wordディレクトリ１１６のためのインデックスエントリ５１４を位置付ける（ステップ７２４）。
【００６１】
階層的インデックス５１０のRowＩＤ  Ｙ３において、システムはインデックスエントリ５１４を見付ける。ステップ７０４において、次のファイル名“Example.doc”が入力パスネームから選択される。ステップ７０６において、インデックスエントリ５１４のDir＿entry＿listを探索し、“Example.doc”のための配列エントリがあるのを見つけ（ステップ７０８）、“Example.doc”がWordディレクトリ１１６の子であることを示す。システムは、Example.docが階層的インデックス５１０中にインデックス付情報を有していないこと、および、Example.docに付随する特定の情報をFileＩＤ  Ｘ４を用いてファイルテーブル２１０中に見付けることができることも見出す。Example.docが、アクセスされるべきターゲットファイル（すなわち、入力パスの最後のファイル名）であるので、制御は、ステップ７２０に移り、ここでシステムはFileＩＤ  Ｘ４を使用し、ファイルテーブル２１０中の適切な行にアクセスし、かつその行のボディ列に記憶されたファイルボディ（ＢＬＯＢ）を抽出する。このように、Example.docファイルがアクセスされる。
【００６２】
このファイルにアクセスする際、階層的インデックス５１０のみが使用された。テーブルのスキャンは必要ではなかった。典型的なサイズのブロックおよび典型的なファイル名長さでは、少なくとも１００個のディレクトリエントリがディスクブロックに収まり、典型的なディレクトリは、１００エントリ未満を有する。これは、所与のディレクトリ中のディレクトリエントリのリストが、典型的には、単一のブロックに収まることを意味する。言い換えれば、インデックスエントリのDir＿entry＿list配列全体を含む、階層的インデックス５１０のどの単一のインデックスエントリも、典型的には、完全に単一のブロックに収まり、したがって、単一のＩ／Ｏ動作で読出可能である。
【００６３】
階層的インデックス５１０においてインデックスエントリからインデックスエントリに移動する際、インデックス中のさまざまなインデックスエントリが異なったディスクブロックに存在するならば、いくつかのディスクアクセスが行なわれる必要がある可能性がある。しかしながら、各インデックスエントリが全体として単一のブロックに収まるのであれば、ディスクアクセスの数は多くともｉとなるであろう。言い換えれば、パスにおける各ディレクトリについて１回のディスクアクセスが使用される。平均的なインデックスエントリのサイズが単一のディスクブロックに収まらず、２または３ブロックを必要とするとしても、これは定数項であり、ファイルシステムにおけるファイルの総数とともに増加するものではない。先行の方法と異なって、ディスクＩ／Ｏの数は、ｉ＊ｌｏｇ（ｎ）／ｍとはならない。したがって、この発明を用いるファイルアクセスはより高速なものとなる。
【００６４】
階層的インデックスの生成
上に説明したように、ファイル名は、ディレクトリに記憶されたいずれかのファイルを参照するために使用される名前であり、パスネームの構成要素である。たとえば、パスネーム“/Windows/Word/Example.doc”において、“Windows”はディレクトリのファイル名であり、“Word”は“Windows”内のディレクトリのファイル名であり、“Example.doc”は“Word”ディレクトリに記憶されたドキュメントのファイル名である。なお、分離文字は、パスネーム内のファイル名を分割する。分離文字は、個々のファイルシステム実現化例によって異なってもよい。たとえば、Microsoft（Ｒ）ファイルシステムは、一般的にはバックスラッシュ（“＼”文字）を使用しており、ＵＮＩＸ（Ｒ）ファイルシステムは、フォワードスラッシュを使用し、Apple Macintoshファイルシステムは、コロン（“：”）を使用してファイル名を分離している。
【００６５】
ある実施例に従えば、FileＩＤは、実際のファイルデータが記憶されているファイルテーブル２１０における主キーである。したがって、各ファイルごとに記憶されているデータを参照するいずれかの主キーを、FileＩＤの代わりに階層的インデックスにおいて使用することが可能である。この場合にはFileＩＤは、階層的インデックス５１０において“外部キー”と普通言われているものである。
【００６６】
最初には、ルートディレクトリ（／）以外にファイルシステム中にファイルは存在しない。したがって、階層的インデックスは、ルートディレクトリのためにインデックス５１０（図５）に１行挿入することにより生成される。この時点ではルートディレクトリにはファイルは存在しないので、ルートディレクトリのインデックスエントリのDir＿entry＿listフィールドは、空のままであるはずである。階層的インデックスのユーザは、ルートエントリのRowＩＤを別個の場所（たとえば、ダイナミックメモリまたは、１つのみのエントリを備えるデータベースにおける別個のテーブル）に保持するべきである。ルートエントリは、階層的インデックス５１０のあらゆる使用についての開始点であるので、そのエントリの場所を直ちに利用可能とすることが重要である。新しいファイルがファイルシステムに加えられるので、階層的インデックス５１０は、“階層的インデックスの保守”と題する以下の項において記載されるように、更新される。
【００６７】
階層的インデックス５１０が、ファイルシステムが置かれた後に生成されるべきものであれば、それは、“階層的インデックスの保守”に記載される方法に従って、ファイルがシステムにちょうど加えられたかのような態様で、ファイルシステム全体を移し、ファイルシステムに存在するファイルの各々について階層的インデックスエントリを加えることによって生成され得る。
【００６８】
階層的インデックスの保守
階層的インデックスのある実施例の保守を図６Ａおよび図６Ｂを参照して記載する。図６Ａを参照し、それは、階層的インデックスを使用するリレーショナルシステムにおいてエミュレートされるファイルシステムにおいてファイルが生成されるのに応答して行なわれるステップを例示するフローチャートである。ステップ６００において、新しいファイルが生成される。ステップ６０２において、新しいファイルが、その親として指定されているファイルの最初の子であるかどうかが判断される。たとえば、ドキュメントDoc1.docがApp1ディレクトリに生成されると仮定する。現在、App1は、いかなる子も有していないので、Doc1.docがその最初の子であり、制御はステップ６０４に移る。
【００６９】
ステップ６０４において、インデックスエントリがその親について生成される。この例では、インデックスエントリは、“App1”のために生成されるものである。ステップ６１０において、親の親のためのインデックスエントリに存在する、親のための配列エントリが、新しく生成されたインデックスエントリへのリンクを含むように更新される。この例では、“Unix”のためのインデックスエントリ５１６に存在する“App1”のための配列エントリ５１８が、階層的インデックス５１０内に、“App1”のための新しく生成されたインデックスエントリのRowＩＤを含むように更新される。ステップ６０６において、新ファイルDoc1.docのための配列エントリが、“App1”のための新しく生成されたインデックスエントリのDir＿entry＿listに挿入される。
【００７０】
生成されるファイルが指定された親の最初の子でなければ、制御はステップ６０８に移る。ステップ６０８において、指定された親のためのインデックスエントリが位置づけられ、ステップ６０６において、新ファイルのための配列エントリが、親のインデックスエントリのDir＿entry＿listに挿入される。
【００７１】
図６Ｂは、ファイルが削除されるのに応答して階層的インデックスを更新するためのステップを例示するフローチャートである。ステップ６５０において、ファイルが削除される。ステップ６５２において、ファイルが親の唯一の子であったかどうかが判断される。削除されたファイルが親の唯一の子であったならば、親のためのインデックスエントリがインデックスから除去され（ステップ６５４）、親の親のインデックスエントリに存在する親のための配列エントリが、親がインデックス中にインデックスエントリをもはや有していないことを反映するように更新される（ステップ６６０）。子が親のための唯一のインデックスエントリでなかったならば、削除されたファイルのための配列エントリが、親のDir＿entry＿listから除去される。
【００７２】
削除されたファイルがその親の唯一の子であったかどうかにかかわらず、削除されたファイルのためのいずれのインデックスエントリも、および、削除されたファイルの子孫のためのインデックスエントリも削除される（ステップ６５８）。
【００７３】
ファイルが階層におけるある場所から別の場所へ移動されるとき、階層的インデックスは、その古い親のDir＿entry＿listからそのファイルのための配列エントリを除去し、その新しい親のDir＿entry＿listにその項目のための配列エントリを加えることによって、更新される。
【００７４】
DIR＿ENTRY＿LIST配列の探索
上述したとおり、パスネーム分解プロセスのステップの１つは、特定の子の配列エントリのためにDir＿entry＿list配列を探索することを伴う（図７、ステップ７０６）。ある実施例に従えば、この探索プロセスは、配列エントリをアルファベット順に各Dir＿entry＿list配列に記憶することによって促進される。配列エントリを順に記憶することにより、バイナリサーチなどのより効率的な探索技術を用いて、所与の子のためのエントリを見つけ得る。しかしながら、配列エントリをソートされた順で保守することは、さらなる保守のオーバーヘッドを招く。したがって、ある実施例では、しきい値の数よりも多い配列エントリを有する配列のみが順序付けされる。
【００７５】
変形
特定の実施例を用いて、リレーショナルシステムにおいて階層的データにアクセスするための階層的インデックスの使用を例示した。しかしながら、この発明は、記載された実施例に限られるものではない。たとえば、階層的インデックス５１０は、少なくとも１つの子を有する項目のためのインデックスエントリのみを有する。しかしながら、階層的インデックスは、任意で、それらが子を有するかどうかにかかわらずすべての項目のためのインデックスエントリを含んでもよい。
【００７６】
例示したように、階層的インデックス５１０におけるインデックスエントリのDir＿entry＿list配列エントリは、ファイルテーブルに子を位置づけるために使用され得るFileＩＤを含む。しかしながら、各Dir＿entry＿list配列エントリに記憶される実際のフィールドは、実現化例によって異なってもよい。たとえば、Dir＿entry＿listは、付加的にまたは代替的に、ファイルテーブルにおける対応する行のRowＩＤ、または、ファイルテーブルに対応するエントリを位置づけるために使用可能である任意の他の一意のヌル（NULL）でないキーを含んでもよい。
【００７７】
ある実施例に従えば、FileＩＤは典型的には、ディスクブロックアドレスに基づくrowidと対照的に、シーケンシャルに生成される。エクスポートするデータベースによって使用されるRowＩＤは、インポートするデータベースがディレクトリをロードするのにディスク上に異なった場所を見つけるならば、インポートするデータベースによって同じ行について使用されるRowＩＤと異なる可能性があるので、FileＩＤ値は、（たとえば、バックアップ／リストアの目的で）データベースにディレクトリをインポート／エクスポートするのに有用である。
【００７８】
ある実施例に従えば、階層的インデックスは、図５に示すとおり、別個のFileＩＤ列を有していない。代わりに、ターゲット項目のFileＩＤが、ターゲット項目の親のDir＿entry＿listに位置する、ターゲット項目のための配列エントリから抽出される。親を有していない、ルートディレクトリのFileＩＤは、階層的インデックスとは別個に記憶されてもよい。
【００７９】
加えて、Dir＿entry＿listエントリを用いて、それらが対応する項目についての有用な情報を“キャッシュ”してもよい。そのような付加的な情報は、たとえば、項目に関連づけられるセキュリティ特権についての情報を含んでもよい。いくつかの場合において、項目のための配列エントリに記憶される付加的情報は、項目を参照するクエリを満足させるのに必要とされる情報のすべてを含み、それにより、項目のファイルテーブル情報にアクセスする必要を回避してもよい。しかしながら、Dir＿entry＿listに有用な情報をキャッシュする要望は、各インデックスエントリを読出すのに必要とされるＩ／Ｏの数を低減するためにDir＿entry＿listのサイズを制限する必要と比較考量されなければならない。
【００８０】
この発明の実施例は、ファイルシステムについて記載された。しかしながら、ここに記載された技術は、リレーショナルに編成されたシステム内で、いかなる階層的に編成された情報の記憶装置にも適用可能である。たとえば、リレーショナルシステムは、動物についてのレコードを記憶するのに使用されてもよく、その場合、動物のレコードは、動物が属する網、目、科および種からなる階層的“パス”に基づいてアクセスされるべきである。
【００８１】
ハードウェア概要
図８は、この発明の実施例が実現され得るコンピュータシステム８００を例示するブロック図である。コンピュータシステム８００は、情報をやりとりするためのバス８０２または他の通信メカニズムと、情報を処理するためにバス８０２に結合されるプロセッサ８０４とを含む。コンピュータシステム８００は、プロセッサ８０４によって実行されるべき命令および情報を記憶するためにバス８０２に結合される、ランダムアクセスメモリ（ＲＡＭ）または他のダイナミック記憶装置などの主メモリ８０６も含む。主メモリ８０６は、プロセッサ８０４によって実行されるべき命令の実行中一時的変数または他の中間情報を記憶するためにも使用されてよい。コンピュータシステム８００はさらに、プロセッサ８０４のために静的情報および命令を記憶するためにバス８０２に結合されるリードオンリメモリ（ＲＯＭ）８０８または他の静的記憶装置を含む。磁気ディスクまたは光ディスクなどの記憶装置８１０が、情報および命令を記憶するために設けられバス８０２に結合される。
【００８２】
コンピュータシステム８００は、コンピュータユーザに情報を表示するための、陰極線管（ＣＲＴ）などのディスプレイ８１２にバス８０２を介して結合されてもよい。アルファベット数字および他のキーを含む入力装置８１４が、プロセッサ８０４に情報およびコマンド選択を交信するためにバス８０２に結合される。ユーザ入力装置の他のタイプは、マウス、トラックボールまたはカーソル方向キーなどのカーソル制御８１６であり、プロセッサ８０４に方向情報およびコマンド選択を交信し、かつディスプレイ８１２上でカーソル移動を制御する。この入力装置は、典型的には、装置が平面における位置を特定することを可能にする、第１の軸（たとえばｘ）および第２の軸（たとえばｙ）の２つの軸において２自由度を有する。
【００８３】
この発明は、リレーショナルシステムに記憶された階層的に編成された情報にアクセスするためのコンピュータシステム８００の使用に関する。この発明のある実施例に従えば、コンピュータシステム８００は、主メモリ８０６に含まれる１つ以上の命令の１つ以上のシーケンスを実行するプロセッサ８０４に応答して、階層的インデックスを生成、保守および使用する。そのような命令は、記憶装置８１０などの別のコンピュータで読出可能な媒体から主メモリ８０６に読出され得る。主メモリ８０６に含まれる命令のシーケンスの実行により、プロセッサ８０４は、ここに記載されたプロセスステップを行なう。代替の実施例では、この発明を実現するためにソフトウェア命令の代わりにまたはこれと組合わせて、ハードワイヤード回路が使用されてもよい。したがって、この発明の実施例は、ハードウェア回路およびソフトウェアのいずれの特定の組合せにも限られるものではない。
【００８４】
ここに使用される“コンピュータ読出可能媒体”という言葉は、プロセッサ８０４に命令を与え実行させるのに関与する任意の媒体のことをいう。そのような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むがこれに限られるものではない、多くの形をとり得る。不揮発性媒体は、たとえば、記憶装置８１０などの光ディスクまたは磁気ディスクを含む。揮発性媒体は、主メモリ８０６などのダイナミックメモリを含む。伝送媒体は、バス８０２を含むワイヤを含む、同軸ケーブル、銅線および光ファイバを含む。伝送媒体は、無線通信および赤外線データ通信の際生成されるものなど、音波または光波の形をとってもよい。
【００８５】
コンピュータ読出可能媒体のよくある形は、たとえば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、もしくは任意の他の磁気媒体、ＣＤ−ＲＯＭ、任意の他の光学媒体、パンチカード、ペーパーテープ、孔のパターンを備える任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップもしくはカートリッジ、以下に記載するような搬送波、またはコンピュータが読出すことのできる任意の他の媒体を含む。
【００８６】
コンピュータ読出可能媒体のさまざまな形は、１つ以上の命令の１つ以上のシーケンスをプロセッサ８０４に運び実行させるのに関係し得る。たとえば、命令は、最初に遠隔コンピュータの磁気ディスク上に担持され得る。遠隔コンピュータは、命令をそのダイナミックメモリにロードし、モデムを用いて電話線を介して命令を送信することができる。コンピュータシステム８００にローカルなモデムは、電話線でデータを受取り、赤外線送信機を用いてデータを赤外線信号に変換することができる。赤外線検出器が、赤外線信号で運ばれるデータを受取ることができ、適切な回路が、データをバス８０２に与えることができる。バス８０２は、データを主メモリ８０６に運び、プロセッサ８０４は命令をそこから取出し実行する。主メモリ８０６によって受取られた命令は、任意で、プロセッサ８０４によって実行される前または後のいずれかに記憶装置８１０上に記憶されてもよい。
【００８７】
コンピュータシステム８００は、バス８０２に結合される通信インターフェイス８１８も含む。通信インターフェイス８１８は、ローカルネットワーク８２２に接続されるネットワークリンク８２０に結合する双方向のデータ通信を提供する。たとえば、通信インターフェイス８１８は、データ通信接続を対応するタイプの電話線に与えるための、統合サービスデジタル網（ＩＳＤＮ）カードまたはモデムであってもよい。別の例として、通信インターフェイス８１８は、データ通信接続を互換可能なＬＡＮに与えるための、ローカルエリアネットワーク（ＬＡＮ）カードであってもよい。ワイヤレスリンクが実現されてもよい。任意のそのような実現化例において、通信インターフェイス８１８は、さまざまな種類の情報を表わすデジタルデータストリームを運ぶ電気信号、電磁信号または光信号を送信および受信する。
【００８８】
ネットワークリンク８２０は、典型的には、１つ以上のネットワークを介してデータ通信を他のデータ装置に与える。たとえば、ネットワークリンク８２０は、ローカルネットワーク８２２を介してホストコンピュータ８２４またはインターネットサービスプロバイダ（ＩＳＰ）８２６によって操作されるデータ機器への接続を与えてもよい。ＩＳＰ８２６は、現在通常“インターネット”８２８と呼ばれているワールドワイドパケットデータ通信ネットワークを介してデータ通信サービスを提供する。ローカルネットワーク８２２およびインターネット８２８はどちらも、デジタルデータストリームを運ぶ電気信号、電磁信号または光信号を使用する。さまざまなネットワークを介する信号と、コンピュータシステム８００へおよびこれからデジタルデータを運ぶ、ネットワークリンク８２０上および通信インターフェイス８１８を介する信号とは、情報を運ぶ搬送波の例示の形である。
【００８９】
コンピュータシステム８００は、ネットワーク、ネットワークリンク８２０および通信インターフェイス８１８を介してプログラムコードを含む、メッセージを送信しかつデータを受信することができる。インターネットの例では、サーバ８３０は、インターネット８２８、ＩＳＰ８２６、ローカルネットワーク８２２および通信インターフェイス８１８を介してアプリケーションプログラムのための要求されたコードを伝送し得る。
【００９０】
受取られたコードは、受取られたときにプロセッサ８０４によって実行されても、および／または、後の実行のために記憶装置８１０または他の不揮発性記憶装置に記憶されてもよい。この態様では、コンピュータシステム８００は、搬送波の形でアプリケーションコードを獲得し得る。
【００９１】
前の明細書において、この発明は、その特定の実施例を参照して記載された。しかしながら、この発明のより広い精神および範囲から逸脱することなしに、これにさまざまな変形および変更がなされ得ることが明らかである。したがって、明細書および図面は、限定の意味ではなく例示的な意味にみなされるべきものである。
【図１】
2010152916.tif 000007
【図２】
2010152916.tif 000008
【図３】
2010152916.tif 000009
【図４】
2010152916.tif 000010
【図５】
2010152916.tif 000011
【図６Ａ】
2010152916.tif 000012
【図６Ｂ】
2010152916.tif 000013
【図７】
2010152916.tif 000014
【図８】
2010152916.tif 000015