(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、該コンピュータのデータ記憶システムに記憶されたインデックスキーに基づき、該データ記憶システムに記憶された第１テーブル及び第２テーブルを含むリレーショナルデータベースにおける該第１テーブルのインデックスを形成するための方法において、
前記インデックスキーに基づいて、前記リレーショナルデータベースから、インデックスキー値と、該インデックスキー値に関連付けられた前記第１テーブルのレコードとを、検索するステップと、
前記検索されたインデックスキー値を、前記第１テーブルの前記検索されたレコードを識別するレコード識別子と関連付けて前記第１テーブルのインデックスに記録するステップとを有し、
前記インデックスキーが、前記リレーショナルデータベースの、少なくとも前記第２テーブルを参照することを特徴とする方法。
【請求項２】
前記リレーショナルデータベースが、更に、第３テーブルを含み、前記インデックスキーが、更に、第３テーブルを参照することを特徴とする、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、リレーショナルデータベースシステムに係り、より詳細には、リレーショナルデータベースシステムにおけるインデックス動作に係る。
【０００２】
【従来の技術】
ユーザは、リレーショナルデータベースをテーブルの集合体と理解しており、各テーブルは、項目及び項目属性のデータを行及び列に配列するもので、テーブルの行は、項目（記録と称する）に対応し、そしてテーブルの列は、項目の属性（フィールドと称する）に対応する。テーブルの記録は、一般的に、その記録が記憶されたページ及びページ内のオフセットを指示する記録識別子（ＲＩＤ）により識別することができる。
【０００３】
図１ないし３は、リレーショナルデータベースにおけるテーブルの例を示す。テーブルに記憶されたデータは、図４ないし６に示されたようなインデックスを用いてアクセスすることができ、これらインデックスは、テーブル記録の論理的なオーダー（順序）を与えることによりデータをアクセスするのに役立つ。図４は、顧客名４１０ａをインデックスキーとして使用する図１のＣＵＳＴテーブル１００における従来のインデックス４００を示す。インデックス４００は、顧客名１２０によりＣＵＳＴテーブル１００の記録のアルファベット式オーダーを与え、各名前４１０ａを、ｃｕｓｔ ｎａｍｅフィールド１２０に顧客名を有するテーブル記録の記録識別子４１０ｂと関連付ける。
【０００４】
Ｓｍｉｔｈという名前の顧客の電話番号の問合せは、通常は、関連記録識別子４４０ｂを用いてキー値「Ｓｍｉｔｈ」４４０ａを有するエントリーのインデックス４００をサーチしてＣＵＳＴテーブル１００における記録を検索し、そしてその検索された記録のｃｕｓｔ ｐｈｏｎｅフィールド１４０のデータを抽出することにより処理される。インデックス４００は、顧客名によりオーダーされるので、インデックスサーチは、インデックスなしに要求されるＣＵＳＴテーブル１００の直線的なサーチよりも高速である。インデックスは、Ｂツリー及びハッシュ機能のような種々の方法を用いて実施される。
【０００５】
インデックス４００で例示されたように、インデックスエントリーは、一般的に、インデックスキー値、及びテーブル記録の記録識別子の２つの属性を有している。インデックスキーは、一般に、テーブルからのフィールド又はフィールドの組み合わせであり、そして各インデックスエントリーは、キー値をテーブル記録の記録識別子と関連付ける。
【０００６】
従来のインデックスは、テーブルフィールドに基づくキー値を、その同じテーブルの記録の記録識別子に関連付ける単一テーブルである。図４のインデックス４００は、単一テーブルインデックスの一例である。単一テーブルインデックスは、種々の形式が存在する。図７は、テーブル記録の１つ以上のフィールドを用いた表現としてインデックスキーを定義することにより形成された「仮想列」インデックスの一例を示す。例えば、割引を含む価格により図２のオーダーテーブル（ＯＲＤテーブル）の記録をオーダーするために、インデックスキー（ＯＲＤ．ｐｒｉｃｅ−ＯＲＤ．ｄｉｓｃｏｕｎｔ）を用いて仮想列インデックスが形成される。
【０００７】
別の形式の単一テーブルインデックスは、指定の条件を満足するテーブル記録のみをインデックスする「部分インデックス」である。例えば、図８は、ＯＲＤ．ｄａｔｅの値を、少なくとも＄５０，０００．００の価格を有するテーブル記録の記録識別子のみに関連付けるインデックスを示している。
【０００８】
リレーショナルデータベースシステムにおいて、インデックスは、マルチテーブルであって、そのインデックスキーの第１テーブルからのフィールドを使用しそしてインデックスキー値を第２テーブルの記録の記録識別子に関連付けるものであってもよい。マルチテーブルインデックスは、一般に、連結インデックスと称する。
【０００９】
図４ないし６は、ＣＵＳＴテーブル１００からの名前フィールド１２０をインデックスキー（ＣＵＳＴ．ｃｕｓｔ ｎａｍｅ）として使用してＩＴＥＭテーブル３００（図３）に形成された顧客名に基づくインデックス記録を検索するためのインデックスを実施を示す。図示されたように、このインデックスは、３つのレベルを有する。第１のレベル（インデックス４００、図４）は、ＣＵＳＴ．ｃｕｓｔ ｎａｍｅ４１０ａの値をＣＵＳＴテーブル４１０ｂの記録の記録識別子に関連付け、第２のレベル（インデックス５００、図５）は、ＣＵＳＴ．ｃｕｓｔ ｎｏ５１０ａの値を、そのＯＲＤ．ｃｕｓｔ ｎｏに対して同じ値を有するＯＲＤテーブル５１０ｂの記録の記録識別子に関連付け、そして第３のレベル（インデックス６００、図６）は、ＯＲＤ．ｏｒｄ ｎｏ６１０ａの値を、ＩＴＥＭ．ｏｒｄ ｎｏに対して同じ値を有するＩＴＥＭテーブル６１０ｂの記録の記録識別子に関連付ける。
【００１０】
インデックス４００ないし６００は、顧客名に対応する項目記録を検索する上で役立つ。例えば、顧客Ｓｍｉｔｈの項目記録を検索するためには、インデックス４００は、Ｓｍｉｔｈ（００２）に対応するＣＵＳＴ記録のＣＵＳＴ．ｃｕｓｔ ｎｏ（１００２）を検索するのに使用され、インデックス５００は、ＣＵＳＴ．ｃｕｓｔ ｎｏ（１００２）に対応するＯＲＤ記録（１０１、１０２）のＯＲＤ．ｏｒｄ ｎｏ（００２、００３）を検索するのに使用され、そして最後にインデックス６００は、ＯＲＤ．ｏｒｄ ｎｏ（００２、００３）に対応するＩＴＥＭ記録（２０１、２０２、２０３）を検索するのに使用される。
【００１１】
【発明が解決しようとする課題】
このようなマルチテーブルインデックスは、リレーショナルデータベースシステムのデータを簡単にアクセスするが、リレーショナルデータベースの従来のインデックスには制約がある。例えば、第１テーブルのフィールドのキー値を第２テーブルの記録の記録識別子に関連付ける従来のインデックスは、一般に、図４ないし６に示すように、２つ以上のレベルを有する。
【００１２】
マルチテーブルインデックスにおいて多数のレベルを有する結果として、このようなインデックスは、単一テーブルインデックスよりも多量のメモリスペースを必要とする。更に、多数のレベルを有する結果として、問合せを処理するのに多量の処理が必要となる。例えば、顧客名Ｓｍｉｔｈに対応する項目記録を検索する場合に、多数の処理段階が必要となる。
【００１３】
【課題を解決するための手段】
一般に、本発明は、その１つの特徴において、インデックスキー及びインデックス条件に基づきマルチテーブルのリレーショナルデータベースにおける第１テーブルのインデックスを形成するためのコンピュータ実施方法であって、インデックスキー値を決定し、インデックスキーが第１テーブル以外のテーブルを参照する場合には、他のテーブルからのデータを検索してインデックスキー値を決定することを含み；更に、各々の決定されたインデックスキー値を、インデックス条件を満足する第１テーブルの記録の記録識別子と関連させ、インデックス条件が第１テーブル以外のテーブルを参照する場合には、他のテーブルからのデータを検索して、関連する記録識別子を決定することを含み；そしてインデックスキー値及び関連する記録識別子をインデックスに記憶するという段階を備えた方法を提供する。
【００１４】
本発明の実施形態は、次の特徴の１つ以上を含む。インデックスキーは、少なくとも第２テーブル及び第３テーブルを参照する。インデックス条件は、少なくとも第２テーブル及び第３テーブルを参照する。インデックスキーは、少なくとも第２テーブルを参照する表現である。
【００１５】
本発明は、その別の特徴において、インデックスキーに基づきマルチテーブルのリレーショナルデータベースにおける第１テーブルのインデックスを形成するためのコンピュータ実施方法であって、インデックスキー値を決定し、インデックスキーは、少なくとも第２テーブルを参照する表現を含み；各々の決定されたキー値を第１テーブルの記録の記録識別子と関連させ；そしてインデックスキー値及び関連する記録識別子をインデックスに記憶するという段階を備えた方法も提供する。
【００１６】
本発明は、その更に別の特徴において、マルチテーブルのリレーショナルデータベースにおける問合せを処理するためのインデックスの適用性を決定するコンピュータ実施方法であって、上記インデックスは、インデックスキー及びインデックス条件に基づいてインデックステーブルをインデックスし、上記問合せは、１組の問合せテーブルを参照する問合せ条件に基づくものであり、そして各々のテーブルは、マルチテーブルのリレーショナルデータベースのテーブルであるような方法も提供する。この方法は、インデックステーブルが問合せテーブルの１つであるかどうか決定し；インデックス条件が問合せ条件に比して等しく限定的であるか又はそれ以下であるかを決定し；そしてインデックステーブルが問合せテーブルの１つでありそしてインデックス条件が問合せ条件に比して等しく限定的であるか又はそれ以下である場合には、問合せを処理するのにインデックスを適用できると決定するという段階を備えている。
【００１７】
本発明の実施形態は、インデックス条件が問合せ条件に比して等しく限定的であるか又はそれ以下であるかを決定する段階が、各インデックス条件が少なくとも１つの問合せ条件により満足されるかどうか決定することを含むような方法も包含する。
【００１８】
本発明は、その更に別の特徴において、リレーショナルデータベースの１組の問合せテーブルに対して問合せを処理するコンピュータ実施方法であって、インデックスキー値を有するインデックスエントリーと、上記１組の問合せテーブルにおける第１問合せテーブルの記録の関連記録識別子とを含むインデックスを検索し、上記インデックスエントリーと、その関連記録識別子との関係は、少なくとも上記１組の問合せテーブルにおける第２の問合せテーブル及び第３の問合せテーブルに基づくものであり；上記問合せに基づいてインデックスキー値を決定し；その決定されたインデックスキー値に対応するインデックスエントリーを決定し；そしてその決定されたインデックスエントリーの関連記録識別子に基づいて第１問合せテーブルの記録を検索するという段階を備えた方法も提供する。
【００１９】
本発明は、その更に別の特徴において、リレーショナルデータベースの１組の問合せテーブルに対して問合せを処理するコンピュータ実施方法であって、インデックスキー値を有するインデックスエントリーと、上記１組の問合せテーブルにおける第１問合せテーブルの記録の関連記録識別子とを含むインデックスを検索し、上記インデックスキー値は、少なくとも上記１組の問合せテーブルにおける第２の問合せテーブルを参照する表現に基づくものであり；上記問合せに基づいてインデックスキー値を決定し；その決定されたインデックスキー値に対応するインデックスエントリーを選択し；そしてその選択されたインデックスエントリーに基づいて第１問合せテーブルの記録を検索するという段階を備えた方法も提供する。
【００２０】
本発明は、その更に別の特徴において、プログラム可能なプロセッサがインデックスキー及びインデックス条件に基づいてマルチテーブルのリレーショナルデータベースの第１テーブルの記録をオーダーできるようにプロセッサ読み取り可能な媒体に記憶されたインデックスであって、インデックスキー値と、インデックス条件を満足する第１テーブルの記録に対する関連記録識別子とを備え、上記インデックスキー及びインデックス条件の少なくとも１つは、マルチテーブルのリレーショナルデータベースの第２及び第３テーブルを参照するようなインデックスも提供する。
【００２１】
本発明は、その更に別の特徴において、プログラム可能なプロセッサがインデックスキーに基づいてマルチテーブルのリレーショナルデータベースの第１テーブルの記録をオーダーできるようにプロセッサ読み取り可能な媒体に記憶されたインデックスであって、インデックスキー値と、第１テーブルの記録に対する関連記録識別子とを備え、上記インデックスキーは、少なくともマルチテーブルのリレーショナルデータベースの第２テーブルを参照する表現であるようなインデックスも提供する。
【００２２】
本発明の効果は、次の通りである。この一般化されたキーインデックスシステムは、単一レベルで実施することができ、効率的な記憶を達成すると共に、効率的な問合せ処理を可能にする。又、一般化されたキーインデックスは、例えば、２つ以上のテーブルのフィールドを用いた表現を含む種々のキーインデックスに対してインデックスすることができる。
【００２３】
更に、この一般化されたキーインデックスは、従来の単一テーブルインデックスを含む種々のインデックスフォーマットを包含するに充分なほどの融通性がある。リレーショナルデータベースシステムは、一般化されたキーインデックス及び従来のインデックスの両方を形成しそして取り扱うように容易に適用できる。
【００２４】
本発明の更に別の目的及び効果は、以下の説明から、又は本発明の実施により明らかとなろう。本発明の目的及び効果は、特許請求の範囲に特に指摘する手段及びその組み合わせにより実現することができよう。
【００２５】
【発明の実施の形態】
以下、添付図面を参照して、本発明の好ましい実施形態を詳細に説明する。本発明は、リレーショナルデータベースシステムにおけるインデックスの一般化された使用を提供する。一般化されたキーインデックス（ＧＫインデックス）は、仮想列インデックス及び部分インデックスのような単一テーブルインデックス、並びにマルチテーブルインデックスを含む従来のインデックスを包含し、そして従来のインデックスに使用された異なる技術を単一のインデックスに結合できるようにする。更に、ＧＫインデックスは、効率的に記憶されるカスタマイズされたインデックスを形成しそして効率的な問合せ処理を行えるようにする改良された能力を提供する。
【００２６】
１つの実施形態において、ＧＫインデックスは、次の一般的フォーマットを有するユーザコマンドにより形成される。
CREATE GK-INDEX     <index-name>
ON                  <table-name>
(SELECT AS KEY  <key-list>
FROM           <other-table-list>
WHERE          <condition-list>)
但し、パラメータは、次の通りである。
index-name:       形成されているインデックスを識別する。
table-name:       記録がインデックスされているテーブルを識別する。
【００２７】
key-list:         リレーショナルデータベースの１つ以上のテーブルからの１つ以上のフィールドを含む。
other-table-list: テーブル名に対応するテーブル以外のテーブルであって、キーリスト又は条件リストのいずれかで参照されたフィールドを有する各テーブルを含む。形成されているインデックスが単一テーブルインデックスである場合には、このリストは、空となる。
condition-list:   満足されるべき０以上の条件（表現）を含む。このリストは空である。
【００２８】
１つの実施形態は、問合せを処理しそしてその結果を記憶するようなステートメントからＧＫインデックスを形成する。例えば、ＧＫインデックスを形成する一般的フォーマットは、問合せとして表される。
SELECT            <key-list>, <table-name>. RID
FROM              <other-table-list>, <table-name>
WHERE             <condition-list>
ORDER BY          <order-list>
但し、<table-name>. RID は、テーブル記録を参照し、そして<order-list>は、一般に、キーリストにおいてオーダーされたフィールドを反映する。
【００２９】
ＧＫインデックスは、仮想列インデックス及び部分インデックスを含む従来の単一テーブルインデックスを形成するのに使用することもできる。上記フォーマットを用いた実施においては、単一テーブルＧＫインデックスは、次のようなステートメントにより形成される。
CREATE GK-INDEX:    <index-name>
ON                  <table-name>
(SELECT AS KEY  <key-list>
WHERE          <condition-list>)
これは、次のように問合せとして表される。
SELECT            <key-list>, <table-name>. RID
FROM              <table-name>
WHERE             <condition-list>
ORDER BY          <order-list>
【００３０】
従って、例えば、名前によりＣＵＳＴテーブルをインデックスする図４を参照して述べた標準的な１テーブルインデックスは、次のようなステートメントによって形成される。
CREATE GK-INDEX     Cust Name Index
ON                  Cust
(SELECT AS KEY CUST.cust  name)
これは、次のように問合せとして表される。
SELECT            CUST.cust  name, CUST.RID
FROM              CUST
ORDER BY          CUST.cust  name
【００３１】
図７を参照して上記した仮想列インデックス７００は、次のステートメントによって形成される。
CREATE GK-INDEX   VC Index
ON                ORD
(SELECT AS KEY (ORD.price - ORD.discount)
これは、次のように問合せとして表される。
0004132136.tif 000002
【００３２】
同様に、図８を参照して述べた部分インデックス８００は、次のように形成される。
CREATE GK-INDEX   Partial  Index
ON                ORD
(SELECT AS KEY ORD.date
WHERE         ORD.price ≧ 50,000.00)
これは、次のように問合せとして表される。
SELECT            ORD.date, ORD.RID
FROM              ORD
WHERE             ORD.price ≧ 50,000.00
ORDER BY          ORD.date
【００３３】
上記のように、ＧＫインデックスは、従来の単一テーブルインデックスを包含する。又、ＧＫインデックスは、マルチテーブルであってもよい。マルチテーブルＧＫインデックスに対応する問合せを処理する際には、ＧＫインデックスキー値と、インデックスされたテーブルの記録の記録識別子との最終的な関連を決定するのに中間テーブルが参照されるが、ＧＫインデックスは、最終的な結果を記憶する。
【００３４】
問合せ処理方法は、広範囲に研究されており、「Create GK Index （ＧＫインデックスを形成する）」コマンドに対応する問合せを処理するのに種々の方法を使用することができる。
【００３５】
図９は、ＧＫインデックスを形成する方法を示すフローチャートである。ステップ９１０において、インデックスキーＫ（<key-list>として上記した）及びインデックス条件｛Ｃ｝（<condition-list>として上記した）を使用して、テーブルＴ（<table-name>として上記した）にＧＫインデックスＧＫＩを形成するコマンドを受け取った後に、ステップ９２０においてインデックスキーＫの値が決定される。ステップ９３０において、各インデックスキー値に対し、条件｛Ｃ｝を満足するテーブルＴの関連記録識別子が決定される。ステップ９４０において、インデックスキー値及びそれらの関連記録識別子が記憶される。
【００３６】
インデックスキー値に対してテーブルＴの記録の関連記録識別子を決定するときには、テーブルＴではなく、中間テーブル（<other-table-list>のテーブルの１つ）を参照することができる。例えば、<other-table-list>のテーブルがインデックスキーにより又は｛Ｃ｝の条件において参照される場合には、他のテーブルからのデータを検索する必要がある。しかしながら、中間テーブルが参照されるかどうかに関わりなく、インデックスは、インデックスキー値を、インデックスされたテーブルＴの記録の関連記録識別子に直接関連させるマッピングの結果を記憶する。
【００３７】
図１０は、顧客名を項目記録の記録識別子に関連付けて、図４ないし６のインデックスと同じ機能を実行するＧＫインデックス１０００を示す。次のようなコマンドの結果、
0004132136.tif 000003
それに対応する問合せ
0004132136.tif 000004
が処理され、図１０のＧＫインデックス１０００を形成する。
【００３８】
図４のインデックス４００と同様に、ＧＫインデックス１０００は、顧客名を項目記録の記録インデックスに関連付ける。しかしながら、図示されたように、ＧＫインデックス１０００は、ＣＵＳＴテーブルからの顧客名の値をＩＴＥＭテーブルの記録の記録識別子に直接関連付ける単一のレベルしかもたず、ＯＲＤテーブルへの参照を排除する。
【００３９】
図４ないし６のインデックスのような従来のマルチテーブルインデックスは、キー値をテーブル記録の記録識別子に関連付けるために中間記録を参照する多数のレベルを有している。多数のレベルは、多量のメモリを必要としそしてアクセス時間を遅くするだけでなく、形成することのできるインデックスの形式にある程度の制約を課する。例えば、従来のマルチレベルマルチテーブルインデックス動作は、インデックスキーが２つ以上のテーブルのフィールドに基づくことを許さない。
【００４０】
これに対して、ＧＫインデックスは、ＧＫインデックスキー値をテーブル記録の記録識別子に直接関連させる単一レベルしかもたないので、ユーザは、関連をいかに定めるかを決定する上で著しい融通性をもつ。例えば、ＧＫインデックスキーは、第２テーブルの１つ以上のフィールドを用いる表現を含むインデックスキーを使用して第１テーブルに形成することができる。図１ないし３のテーブルを参照すれば、特定の全価格を有する単一オーダー購入を行った顧客を決定するために、図１１のＧＫインデックスは、次のように形成される。
0004132136.tif 000005
これは、次のように処理される。
【００４１】
0004132136.tif 000006
【００４２】
又、ＧＫインデックスキーは、２つ以上のテーブルからのフィールドに形成することもできる。例えば、次のコマンドは、顧客名及びオーダー日付の組み合わせを、そのオーダーで購入した項目の記録識別子に関連付ける図１２のＧＫインデックス１２００を形成する。
0004132136.tif 000007
これは、次により形成される。
【００４３】
0004132136.tif 000008
【００４４】
これらの例は、ユーザの特定のニーズに対してカスタマイズされたインデックスを形成するための一般化されたキーインデックス動作の融通性を示している。
【００４５】
ＧＫインデックスを形成するために参照されたテーブルにおいてデータが追加され、削除され又は変更された後にＧＫインデックスの精度の継続を確保するために、ＧＫインデックスは、データ変更が生じた後にそのエントリーが依然として正確であることを照合するために更新されねばならない。
【００４６】
種々の更新方法が存在し、ＧＫインデックスを更新するのに適用できる。１つの実施形態では、参照されたフィールドのいずれかが変更されたときにＧＫインデックスが再構成されるか、又はその変更がＧＫインデックスに適合しない場合にはＧＫインデックスが削除される（例えば、不適合のデータ形式に対しフィールドが削除されるか又は変更される）。この方法は、データが頻繁に更新されないデータウェアハウス（倉庫）環境に特に適している。
【００４７】
データベースシステムは、ＧＫインデックスを使用し、ＧＫインデックス内のＧＫインデックスキー値を見出して、関連テーブル記録への関連記録識別子に従うことにより、データをアクセスする。例えば、Ｓｍｉｔｈという名前の顧客に対する項目記録を見つけるために図１０のＧＫインデックス１０００を使用する場合に、Ｓｍｉｔｈのエントリー１０３０ａに対してＧＫインデックス１０００が最初にサーチされ、そしてそれに対応する記録識別子１０３０ｂにより項目記録が検索される。
【００４８】
インデックスを使用するために、リレーショナルデータベースシステムは、最初に、所与の問合せを処理するためにその特定のインデックスが適切に使用されるかどうか決定する。典型的に、データベースシステムは、所与の問合せを処理するのにどのインデックスが使用されるかを決定する役目を果たす問合せ最適化手段を有している。
【００４９】
一般に、問合せ最適化手段は、（１）インデックスを問合せに適用できるかどうか及び（２）問合せを処理するようにインデックスが最適に使用されるかどうかを決定することにより、所与の問合せに対し特定のインデックスを使用すべきかどうか決定する。例えば、次の問合せＱについて考える。
SELECT         <query-select-list>
FROM           <query-table-list>
WHERE          <query-condition-list>
更に、次のように形成されるＧＫインデックスＧＫＩについて考える。
CREATE GK-INDEX       GKI
ON                    T
(SELECT AS KEY   <index-key-list>
FROM            <index-other-table-list>
WHERE           <index-condition-list>
【００５０】
一般に、ＧＫインデックスを問合せに適用できるためには、それがインデックスするテーブルが問合せにより参照されねばならない。図１３は、適用性を決定する１つの実施形態におけるプロセスを示すフローチャートである。ステップ１３１０において、ＧＫインデックスＧＫＩによりインデックスされたテーブルＴが<query-table-list>のテーブルの１つでない場合には、ＧＫインデックスＧＫＩは問合せに適用できない（ステップ１３１５）。同様に、ステップ１３２０において、<index-condition-list>が<query-condition-list>より制約がある場合には、ＧＫインデックスＧＫＩは問合せに適用できない（ステップ１３１５）。さもなくば、ＧＫインデックスＧＫＩは、問合せに適用できる（ステップ１３２５）。
【００５１】
制約度の評価（ステップ１３２０）は、インデックスＧＫＩの使用が不完全な結果を生じないように確保し、問合せにより要求される以上に制約のある条件でインデックスＧＫＩが形成される場合には不完全な結果が生じる。１つの実施形態では、制約度の条件を満足するかどうかは、<index-condition-list>の各条件が<query-condition-list>の少なくとも１つの条件により満足されるかどうかを評価することにより決定される。
【００５２】
以下の例は、適用性の考え方を示すものである。図１ないし３のテーブルを用いて、次のインデックスが形成される。
（１）cust items インデックス：図１０に示すように、cust items インデックス１０００は、顧客名を、その顧客が購入した項目に対する項目記録の記録識別子と関連させる。
（２）cust big  items インデックス：図１４に示すように、cust big  items インデックス１４００は、顧客名を、少なくとも＄５０，０００．００の価格のオーダーでその顧客が購入した項目に対する項目記録の記録識別子と関連させる。このインデックスは、次のように形成される。
0004132136.tif 000009
（３）cust many big  items インデックス：図１５に示すように、cust many big  items インデックス１５００は、顧客名を、少なくとも＄５０，０００．００の価格のオーダーでその顧客により購入されそして少なくとも１０の量で購入された項目に対する項目記録の記録識別子と関連させる。このインデックスは、次のように形成される。
【００５３】
0004132136.tif 000010
【００５４】
次の問合せは、図１ないし３のテーブルを含むデータベースに基づいて送られる。
（１）Ｑ１：顧客Ｓｍｉｔｈによるオーダーにおいて項目番号及び項目量を見出す。この問合せは、次のようにフォーマットされる。
0004132136.tif 000011
（２）Ｑ２：顧客Ｓｍｉｔｈによる少なくとも＄６０，０００．００のオーダーにおいて項目番号及び項目量を見出す。この問合せは、次のようにフォーマットされる。
【００５５】
0004132136.tif 000012
（３）Ｑ３：顧客Ｓｍｉｔｈによる少なくとも＄６０，０００．００の少なくとも２５の量のオーダーにおいて購入した項目番号及び項目量を見出す。この問合せは、次のようにフォーマットされる。
0004132136.tif 000013
【００５６】
問合せＱ１、Ｑ２及びＱ３に対するインデックス１０００、１４００及び１５００の適応性は、図１６に示されている。Ｑ１は、Ｓｍｉｔｈにより購入された全ての項目に関する情報を要求する。インデックス１０００のみを適用できる。というのは、インデックス１４００及び１５００のインデックス条件は、問合せ条件よりも限定的であり、完全な結果を生じないからである。ORD.price ≧ 50,000 というインデックス１４００の条件は、Ｑ１の条件により満足されない。従って、インデックス１４００は、少なくとも＄５０，０００．００のオーダーにおいてＳｍｉｔｈが購入した項目しか指示しない。インデックス１５００は、ORD.price ≧ 50,000 及びITEM.quantity ≧ 10 の両方の条件を含み、そのいずれもＱ２によって満足されない。従って、インデックス１５００は、少なくとも＄５０，０００．００のオーダーにおいてＳｍｉｔｈが購入した項目のみを指示する。
【００５７】
この例も、問合せ条件よりも限定的な条件を有するインデックスは誤った結果を招くことを示している。即ち、Ｓｍｉｔｈが購入した全ての項目を要求するＱ１に対する適切な応答は、項目２０１、２０２、２０３に対応し、インデックス１４００は、項目２０１及び２０２のみを生じ、インデックス１５００は、項目２０１のみを生じる。
【００５８】
適用性の概念は、問合せＱ２及びＱ３によって更に示される。Ｑ２は、少なくとも＄６０，０００．００のオーダーにおいてＳｍｉｔｈが購入した項目を要求する。インデックス１４００は、ORD.price ≧ 50,000.00というその条件がORD.price ≧ 60,000.00というＱ２問合せ条件により満足されるので、Ｑ２に適用することができる。インデックス１５００は、ORD.price ≧ 50,000 というその条件は満足されるが、ORD.quantity  ≧ 10 というその条件がＱ２の条件によって満足されないので、適用できない。
【００５９】
Ｑ３は、少なくとも＄６０，０００．００のオーダーにおいて２５より大きな量でＳｍｉｔｈ氏が購入した項目を要求する。インデックス１４００は、Ｑ２に対して適用できるという同じ理由で適用できる。インデックス１５００も、ITEM.quantity ≧ 10 というその条件がITEM.quantity ≧ 25 というＱ３問合せの条件により満足されるので、適用できる。
【００６０】
インデックスが所与の問合せに適用できることを決定すると、問合せ最適化手段は、一般に、その問合せを処理するのにインデックスが最適に使用されるかどうか決定する。最適化方法は、問合せ最適化手段の間で異なるが、一般的に使用される方法は、Ｐ．Ｇ．セリンガー氏等の「リレーショナルデータベースシステムのためのアクセス仕様言語(An Access Specification Language for a Relational Data Base System)」、１９７９  ＡＣＭ  ＳＩＧＭＯＤ  INT'L CONF. ON MANAGEMENT OF DATA 23-34 （１９７９年５月／６月）に記載されたセリンガーの最適化アルゴリズムに基づいている。
【００６１】
セリンガーアルゴリズムの基本的な考え方は、所与の問合せを処理するための考えられる実行プランを列挙し、各考えられるプランのコストを推定し、そして最良のプラン（最もコストの安いプラン）を選択することである。従って、次の問合せを処理する場合、
SELECT         <query-select-list>
FROM           <query-table-list>
WHERE          <query-condition-list>
<query-table-list>をセット｛T1,T2,...Tn ｝とすれば、<query-table-list>の全てのテーブルを接合することが必要となる。１つの考えられるセリンガー最適化手段は、問合せテーブルセットのテーブルの全ての順列に対するプランを形成し、そしてその順列の第１テーブルでスタートしてそのテーブルを第２テーブルと接合するコストを推定し、そのコストを、上記第１接合の結果を第３テーブルに接合するコストの推定値に加算し、テーブルセットの全てのテーブルを接合し続けそして累積された推定コストを計算することにより、各順列に対するコストを推定する。又、総コストは、いかなる接合も必要としない単一テーブル条件を組み込むコストも考慮する。このプロセスが各々の考えられる順列に対して繰り返される。
【００６２】
インデックスは、プランのコストを減少することができる。セリンガー最適化手段は、一般に、インデックスを用いて、テーブルを接合するコストを減少するか、又は単一テーブルに対して条件を決定するコストを減少する。
【００６３】
図１ないし３のテーブル１００、２００、３００を参照し、次の問合せについて考える。
0004132136.tif 000014
【００６４】
テーブルセットは、｛CUST, ORD, ITEM ｝であり、プランは、次のような考えられる順列を含む。
（１）｛CUST, ORD, ITEM ｝
（２）｛CUST, ITEM, ORD ｝
（３）｛ORD, CUST, ITEM ｝
（４）｛ORD, ITEM, CUST ｝
（５）｛ITEM, CUST, ORD ｝
（６）｛ITEM, ORD, CUST ｝
【００６５】
図１７のインデックス１７００は、フィールドITEM.quantity をITEM.RIDと関連付け、そして条件ITEM.quantity ≧ 25 を処理するのに有用である。この条件は、ＩＴＥＭテーブルのみを参照し、それ故、他のテーブルを予め接合する必要はない。従って、インデックス１７００は、ＩＴＥＭテーブルが追加されるときに上記プラン（１）ないし（６）の各々に使用することができる。
【００６６】
図１８のインデックス１８００は、フィールドITEM.ord noをITEM.RIDと関連付け、そして条件ORD.ord  no = ITEM.ord  noを遂行して、ＩＴＥＭテーブルを共通のord  noフィールドによりＯＲＤテーブルに接合するのに有用である。しかしながら、この条件はＯＲＤテーブルを参照するので、インデックス１８００は、ＯＲＤテーブルが既に接合された場合にＩＴＥＭテーブルを接合することのみに使用される。従って、インデックス１８００は、プラン（１）、（３）及び（４）のみに使用される。
【００６７】
ＧＫインデックスをいつ使用するかを決定する種々の方法を用いて、ＧＫインデックスをこのアルゴリズムに組み込むようにセリンガー最適化手段を適応させることができる。例えば、１つの実施形態において、従来の単一テーブルインデックスと同様に、テーブルＴにおける単一テーブルＧＫインデックスは、そのテーブルが接合されるときに、常に考慮される。マルチテーブルＧＫインデックスは、キーリストに参照された全てのテーブルが既に接合されたときに、考慮される。
【００６８】
セリンガーアルゴリズム以外のアルゴリズムをベースとする問合せ最適化手段も、ＧＫインデックスを処理するのに同様に適応できるが、特定の異なる変更が行われる。
【００６９】
本発明の特許請求の範囲内において他の実施形態も考えられる。例えば、他の実施形態は、異なる更新方法を使用してもよい。ある実施形態は、その基礎となるテーブルが変更されるときにＧＫインデックスを削除するのではなく、インデックスを更新又は再計算する。
【００７０】
他の考えられる変更は、異なる形式のデータ構造を使用して、ｂツリー及びビットマップインデックスを含むＧＫキーインデックスを表すことを含む。
【００７１】
本発明は、ソフトウェアでの実施について説明したが、ハードウェア又はソフトウェア或いはその両方の組み合わせで実施することもできる。本発明は、プロセッサ、データ記憶システム、入力装置及び出力装置を備えたプログラム可能な処理システムにおいて実行されるソフトウェアプログラムで実施されるのが好ましい。
【００７２】
図１９は、ＣＰＵバス１９４０により接続されたＣＰＵ１９１０、ＲＡＭ１９２０及びＩ／Ｏコントローラ１９３０を含むプログラム可能な処理システム１９００を示している。Ｉ／Ｏコントローラ１９３０は、Ｉ／Ｏバス１９５０によりキーボード１９６０のような入力装置、及びディスプレイ１９７０のような出力装置にも接続される。
【００７３】
以上、本発明を好ましい実施形態について説明したが、本発明は、これに限定されるものではなく、特許請求の範囲のみによって限定されるものとする。
【図面の簡単な説明】
【図１】リレーショナルデータベースのテーブルを示す図である。
【図２】リレーショナルデータベースのテーブルを示す図である。
【図３】リレーショナルデータベースのテーブルを示す図である。
【図４】インデックスを示す図である。
【図５】インデックスを示す図である。
【図６】インデックスを示す図である。
【図７】インデックスを示す図である。
【図８】インデックスを示す図である。
【図９】一般化されたキーインデックスを形成する方法のフローチャートである。
【図１０】インデックスを示す図である。
【図１１】インデックスを示す図である。
【図１２】インデックスを示す図である。
【図１３】一般化されたキーインデックスの適用性を決定する方法のフローチャートである。
【図１４】インデックスを示す図である。
【図１５】インデックスを示す図である。
【図１６】所与の問合せに対するインデックスの適用性を示す図である。
【図１７】インデックスを示す図である。
【図１８】インデックスを示す図である。
【図１９】プログラム可能な処理システムを示す図である。
【符号の説明】
１０００、１４００、１５００  ＧＫインデックス
１９００  プログラム可能な処理システム
１９１０  ＣＰＵ
１９３０  Ｉ／Ｏコントローラ
１９４０  ＣＰＵバス
１９５０  Ｉ／Ｏバス
１９６０  キーボード
１９７０  ディスプレイ
【図１】
0004132136.tif 000015
【図２】
0004132136.tif 000016
【図３】
0004132136.tif 000017
【図４】
0004132136.tif 000018
【図５】
0004132136.tif 000019
【図６】
0004132136.tif 000020
【図７】
0004132136.tif 000021
【図８】
0004132136.tif 000022
【図９】
0004132136.tif 000023
【図１０】
0004132136.tif 000024
【図１１】
0004132136.tif 000025
【図１２】
0004132136.tif 000026
【図１３】
0004132136.tif 000027
【図１４】
0004132136.tif 000028
【図１５】
0004132136.tif 000029
【図１６】
0004132136.tif 000030
【図１７】
0004132136.tif 000031
【図１８】
0004132136.tif 000032
【図１９】
0004132136.tif 000033