【手続補正書】
【提出日】平成18年2月20日(2006.2.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項1】  データ処理システム上で実行されるデータベースファイル管理システムにより使用されるデータ構造であって、
ブロックに配列され、データレコードと関連しており、キーまたは複数のキーによりデータレコードのアクセスまたは更新を可能にし、ブロックの不均衡の構造の影響を受けやすい基本区分インデックスを含む階層インデックスＩｏ，．．．，Ｉｈを含み、
前記階層インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの均衡構造を構成する、データ構造。
【請求項２】  前記基本区分インデックスがパトリシアトリーに基づいている、請求項１に記載のデータ構造。
【請求項３】  データ処理システム上で実行されるデータベースファイル管理システムにより使用されるデータ構造であって、
データレコードに関連し、キーまたは複数のキーによる前記データレコードのアクセスまたは更新を可能にし、ブロックの不均衡の構造の影響を受けやすい基本区分インデックスを有し、ブロックに配列され、前記データレコードのキーの上に構築されるインデックスを含み、
前記インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの均衡した構造を構成する、データ構造。
【請求項４】  データ処理システムで実行されるデータベースファイル管理システムにより使用されるデータ構造であって、
データレコードに関連し、キーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの不均衡な構造に影響を受けやすいトリーを含み、ブロックに配列され、データレコードのキーの上で構築されているインデックスを含み、
前記インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの均衡した構造を構成する、データ構造。
【請求項５】  階層インデックスＩｏ，．．．，Ｉｈを含み、ｊ ＞ 0及び≦ ｈに対するＩｊはＩｊ−１を超えるインデックスである、請求項１に記載のデータ構造。
【請求項６】  データレコードをアクセスし、データ処理システムで実行されるためのデータファイル管理システムに使用され、ブロックに配列される階層インデックスＩｏ，．．．，Ｉｈを構築する方法であって、データレコードは、ブロックに配列される基本区分インデックスと関連し、記憶媒体の中に記憶され、基本区分インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの不均衡な構造に影響を受けやすく、
（ａ）前記基本区分インデックスＩｏを提供するステップと、
（ｂ）前記基本区分インデックスの代表キーの上で代表インデックスを構築し、前記階層インデックスがキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの平行した構造を構成するステップとでなる、階層インデックスＩｏ，．．．，Ｉｈを構築するための方法。
【請求項７】  前記基本区分インデックスがパトリシアトリーに基づいている、請求項６に記載の階層インデックス。
【請求項８】  データレコードのキー上にブロックに配置されるインデックスを構築する方法であって、データレコードにアクセスし、データ処理システムで実行されるためのデータベースファイル管理システムに使用され、データレコードは、ブロックの中に配列されている基本区分インデックスと関連し、記憶媒体の中で記憶され、基本区分インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの不均衡な構造に影響をうけやすく、
（ａ）前記基本区分インデックスを提供するステップと、
（ｂ）インデックスを前記基本区分インデックスの代表キー上に構築するステップとを含み、前記基本区分インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの均衡した構造を構成する、方法。
【請求項９】  データレコードのキー上にブロックに配置されるインデックスを構築する方法であって、データレコードにアクセスし、データ処理システムで実行されるためのデータファイル管理システムに使用され、データレコードがブロックの中に配列されているトリーに関連し、記憶媒体の中に記憶され、トリーがキーまたは複数のキーによるデータレコードのアクセスまたは更新を可能にし、ブロックの不均衡な構造に影響を受けやすく、
（ａ）トリーを提供するステップと、
（ｂ）インデックスを前記トリーの代表キーの上に構築するステップとを含み、前記インデックスはキーまたは複数のキーによるデータレコードのアクセスまたは構築を可能にし、ブロックの均衡した構造を構成する、方法。
【請求項１０】  パトリシアトリーに基づいており、ブロックに区分される、データレコード上のインデックス構造を用いて、ブロックの実質的均衡した構造を作成する方法であって、前記ブロックの代表キーを索引することを含む、方法。
【請求項１１】  トリーに基づいており、ブロックに区分される、データレコード上のインデックス構造を用いて、キーに従って前記インデックスに導く方法であって、インデックスの路を探索するステップと、間違いの場合、ａ．異なる誘導路が開始できるインデックスの位置に戻ること、ｂ．誘導が正しくなるまでステップ１を繰り返すことを実行するステップとを含む、方法。
【請求項１２】  データレコードのキー上にインデックスを含むデータ構造であって、前記インデックスがトリーに基づいており、ブロックに区分され、指定器が前記キーの１つの一部を形成する、データ構造。
【請求項１３】  前記データレコードは第２型データレコードが第1型データレコードに従属させるように少なくとも２つの型でなる、請求項１２のデータ構造。
【請求項１４】  データ処理システムで実行されるデータベースファイルによって使用される記憶媒体において、トリーインデックス構造に基づくデータ構造が可変長キー端を保持し、ゼロラベル化リンクを含む、記憶媒体。
【請求項１５】  複数のトリーブロック及び前記トリーブロックに少なくとも１つのノードを索引する構造により構成され、インデックスを実施するコンピュータ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０２１０
【補正方法】変更
【補正の内容】
【０２１０】
ｉ．３  データレコードに到達した場合は（以下「参照データレコード」と称す）、求められているデータレコードの検索キーを全般的に参照データレコードのキーと比較する、
ｉ．３．１  「発見された」に戻った等価の場合は（「検索」の場合は、またデータレコード全体を戻す）、検索手続きを打ち切るか、あるいは
ｉ．３．２  整合せず「見あたらない」に戻った場合は、検索手続きを打ち切る。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０２３５
【補正方法】変更
【補正の内容】
【０２３５】
図７Ｃの中で、ブロック１４１の中のノードＡと、またブロック１４８Ａの中のノードＣが、オプションとして切り放されており、同様に１４８ＡのノードＣと、また１４８ＢのノードＧが、オプションとして切り放されていることに留意しなければならない。明らかに示されているとおり、ノードＡ’とＣ’は、ブロック１４０の中で接続され、（結合されている）トリーを形成しており、また、従ってノードＡ’と直接リンク１５６を経由してブロック１４１を、またノードＡ’、Ｃ’と直接リンク１５５を経由してブロック１４８Ｂを、またノードＡ’、Ｃ’と直接リンク１５４を経由してブロック１４８Ｂにアクセスすることが可能である。ノードＡ’とＣ’の間（ブロック１４０の中の）のリンクの数値が、ノードＡとＣの間の元の数値と同じであることに注目する必要がある（図７Ａの中のリンク１４９参照）。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０２３７
【補正方法】変更
【補正の内容】
【０２３７】
図７の特定の実施形態により、代表インデックスとトリー（基本区分インデックスの実施形態の一つとしての）は、同じインデックススキーム、即ちＰＡＩＦとほぼ一致する。下記に図７Ｇを参照して説明されるとおり、「ほぼ」同じスキームにより、一部の差があることを意味する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０２４６
【補正方法】変更
【補正の内容】
【０２４６】
ここで、本発明の技術の本発明の他の実施形態に対する応用を例示している関連する２個の図を示している図８Ａ−８Ｂに注目する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０２４８
【補正方法】変更
【補正の内容】
【０２４８】
図８Ａの中で図示されているデータレコードｂにアクセスするための１個のブロック（あるいは３個の入出力オペレーション）と比較して、データレコードｋにアクセスするための、追加の一個の出入力オペレーション（あるいは３個の出入力オペレーション）、即ち、３ブロックにアクセスすることが、均衡が取られていると見なされていることに留意しなければならない。一部の実生活のシナリオの中で、全く同じ数の出入力オペレーションを必ずしも本発明を応用することを必要としない。言うまでもなく、本発明の技術で処理されないと、これ以上のデータレコードの挿入が、より高い「均衡が失われた」程度を生み出す恐れがあり、前記で詳しく説明されたとおり（従来の技術を参照して）、劣化した性能を招く（不均衡構造のために）。図８Ｂは、本発明の一つの可能な実施形態を示している。図示されているとおり、１個のブロック２７０（Ｉ１を形成している）から成る代表インデックスは、ルートブロック２７０から全てのより低いレベルの垂直ツリー（後者は不均衡なツリーを構成している）が、出入力オペレーションを経由してアクセスされるルートブロック２７０を有する水平的に均衡が取れているツリーが得られるという結果で構成されている。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０２４９
【補正方法】変更
【補正の内容】
【０２４９】
図示されているとおり、最初の垂直ツリー（トリーとしての）の中の諸ブロックに対する実際のアクセスは、各々のブロックの共通キー数値によって達成される。これ以上進む前に、共通項キーは、図８Ｂを参照して例示されている。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０２５１
【補正方法】変更
【補正の内容】
【０２５１】
ブロック２６０からアクセスできる全てのデータレコードが、前記で規定されている共通キーのプレフィックスを共有していることに留意しなければならない。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０２５２
【補正方法】変更
【補正の内容】
【０２５２】
同じ方法で、下記のテーブルは、各ブロックの共通キーの概略を記載している：
【表１】
2002501256.tif 000001
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０２５８
【補正方法】変更
【補正の内容】
【０２５８】
下記の数字の中で、階層インデックスは、連続的に下記の仕分けされていないデータレコードＡ−Ｆ（説明を簡素にするために、ブロックの一部を構成している）を挿入することで構成されている。データのストリングは、１ビットの部分が１を表しているビットの連続で示されている：
Ａ＝００１００００１１
Ｂ＝１１００１１１００
Ｃ＝０１１０１１１１１
Ｄ＝０１１０１１０１１
Ｅ＝１０１０１０１０１
Ｆ＝１１１１１１１１１
第１ステップの中で（図９Ａ）、レコードＡが、後でブロック３００である挿入され、数値０を有するリンク３０２を経由して第１レコードＡと関連するオフセット０を有するノード３０１から成る。この段階で、ツリーは、たった一個のノードを有するブロック３００から成る。インデックススキームは、それぞれリンク３０２とノード３０１上で図示されているとおり、データレコードＡへの検索が、オフセット０の数値０に従って決定されるように支配する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０２７１
【補正方法】変更
【補正の内容】
【０２７１】
特定の故障を解決するために、求められているデータレコードのキーの共通プレフィックスのサイズとデータレコードのキーが、計算される、ブロック（３１０）の共通キーは、実際のデータレコードＣのキーのプレフィックス部分である。従って、共通プレフィックスのサイズはゼロである。次にツリーを、直接リンクを有する共通プレフィックスのサイズに等しいかそれ以下の数値を有するアクセスパスの中でノードまで遡る。後者の必要条件が、満たされない場合は、即ち、全てのノードが、計算されたプレフィックスのサイズより大きい数値を有している場合は、直接リンクを有しているアクセスパスの中の第１ノードから（インデックスＩｉ−ｌの第１ブロックを指していなければならない）。ここで、ノード３１４から直接リンク３１６によってより低いレベルの垂直に向いているツリーに（即ち、層Ｉｉ−ｌに）に移動し、ここから、検索スキームで指定されている検索パスに続く。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０２９１
【補正方法】変更
【補正の内容】
【０２９１】
図７から１０の全てを参照して説明された階層インデックスは、必ずトリーと代表インデックススキームの双方に対して同じインデックススキームを保持する（上記の図９Ｅを参照して説明されたとおり、インデックスを経由してデ−タレコードにアクセスするときに遭遇する可能性があるエラー処理に対するものを除く）。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０２９３
【補正方法】変更
【補正の内容】
【０２９３】
図１１は、均衡が失われたトリーの代表的キー上の代表インデックスとしての従来のＢツリーを使用する、図８Ａ（即ち階層インデックスを構築している）の均衡が失われたツリーを均衡させるもう一つのアプローチを示している。このようにして得られた水平指向の均整が取れたツリー（階層インデックス）は、上位レベル（インデックス層Ｉ２）のブロック２７２，と下位のレベル（インデックス層Ｉ２）の２７０と２７１とまた均衡が失われた垂直指向の図８Ａの最も低い所の（ブロック２６０、２６１、２６２、２６４）インデックス層Ｉ０のツリーの元のブロックから成る。図１１は、代表インデックスのインデックススキームが、元の均衡が失われているトリーのスキ−ムと必ずしも同じでないことを実証している。所望なら、全体的にＢツリー（代表インデックスを形成してる）を、インデックス層Ｉ１として見なすことができる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０３１８
【補正方法】変更
【補正の内容】
【０３１８】
データを検索するとき、図１３Ｅのデータの構造は、従属させられているデータレコードが、「親」レコードにリンクされていると言う事実からから生ずるこれ以外の利点を例示している。タイプＡからのレコードが、クライアントであり、タイプＢからのレコードが、インボイスである場合、通常、クライアントの詳細と共にインボイの明細にアクセスすることが必要である。インボイスからクライアントへのリンクにより、クライアントの詳細の検索を省くことができる。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０３２９
【補正方法】変更
【補正の内容】
【０３２９】
この例の中で、書籍とその要約の間の一対一関係は、Ａｘｘｘを、Ａの指定されたキーとし、Ｋを、レコードＫの指定子として、ＫのキーをＡｘｘｘＫとなるように定義することで維持される。書籍とカテゴリーの間の一対多数の関係は、Ａｘｘｘを、Ａの指定されたキーとし、Ｌをキーの指定子とし、またｙｙｙをレコードＬのキーフィールド（複数を含む）として、ＬのキーをＡｘｘｘＬｙｙｙとなるように定義することで維持される。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０３４３
【補正方法】変更
【補正の内容】
【０３４３】
指定されたインデックスによるオブジェクト指向によるクライアントサーバモデルの実施
クライアント／サーバモデルで、相関関係モデルの効率的なインプリメンテーションができる。このモデルに従って、全てのデータは、中央コンピュータの中に常駐し（サーバと呼ばれる）、またアプリケーションプログラムは、コンピュータ以外の所で実行される（クライアントと呼ばれる）。アプリケーションがデータを必要とするときは、アプリケーションは、クライアントによりサーバに送信されるＳＱＬ照会を形成する。サーバは、照会を査定して、結果として生じたテーブルをクライアントに戻す。