JP5287071B2 - データベース管理システムおよびプログラム - Google Patents

Description

本発明は、索引を用いて所望のレコードを検索するためのデータベース管理システムおよびプログラムに関するものである。

データベース管理システムでよく使われる索引構造として、Ｂ木索引がある。たとえばＢ＋木で例をあげると、その構造は、リーフと呼ばれる最下層のノードと、ルートと呼ばれるノードと、ブランチと呼ばれるそれらノード間のノードとからなり、リーフにはエントリとしてキーとバリューとのペアが格納され、ブランチにはエントリとしてリーフのエントリに子ノードへのポインタを付加したデータが格納される。ここで、キーとは、索引作成対象列のデータを指し、バリューとは、テーブルの行を一意に識別するための識別子（以下、ＲＯＷＩＤと称する）を指す。

このような木構造は、キーがユニークである場合やキーの種類が多い場合に適している。しかし、キーの種類が少ない場合には、同じキーを複数格納してしまうため、ページの使用効率はよくない。

また、他の索引構造として、ビットマップ索引がある。ビットマップ索引では、キーごとにビットマップを作成し、バリューをその値に対応する位置にビットが立っているかどうかで表す。この索引は、Ｂ木索引に比べて高速に照合できる場合もあるが、更新処理の同時実行には適していないというデメリットもある。

また、ページの使用効率を高める別の方法として、階層化された複数のデータ構造体を組み合わせたり、キーを圧縮したりする方法も提案されている。例えば、特許文献１は、決定グラフと呼ばれる一段目のデータ構造体と結論セットと呼ばれる二段目のデータ構造体からなる階層化されたデータ構造体による索引を提案している。特に、この特許文献１では、「該ノードに関連するキーの全体を記憶しない」、「前記結論セット内の各エントリは、・・・前記結論セット内のエントリに関連するキーの厳密な値を保持するキーフィールドと、・・・とを備える」、「前記結論セットに記憶されるキーは圧縮形態で記憶される」などといった記述に見られるように、重なるキーを格納しないようにしたり、キーを圧縮して格納したりしている。

特表２００４−５２７８１３号公報

しかしながら、特許文献１に開示された方式によっても、二段目のデータ構造体にキーを格納していることに変わりはないので、ページの使用効率という点ではまだ不十分である。

また、従来のデータベース管理システムでは、ＮＵＬＬの扱いもページの仕様効率を低くする一因となっていた。あるデータがＮＵＬＬであるかどうかを表すには二通りの方法がある。一つは、データの値域の中の特定の値を内部的にＮＵＬＬとみなす方法であり、他の一つは、データがＮＵＬＬかどうかのフラグを追加する方法である。

しかしながら、前者の方法はその特定の値をユーザが使えなくなることを意味するので、常に利用できる方法ではない。また、後者の方法は、そのような制限がないものの、本来格納したいデータ以外にフラグのための領域も必要とするので、ページの使用効率を低下させる。

本発明は、上記に鑑みてなされたものであって、ページ使用効率およびキャッシュの効果を高めることのできるデータベース管理システムおよびプログラムを提供することを目的の一つとする。

また、本発明の別の態様にかかるデータベース管理システムは、複数のレコード間において所定のフィールドに登録されうる第１の値および第２の値と該第１の値および該第２の値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた索引を作成するデータベース管理システムであって、前記第１の値と前記位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられ、前記第２の値と前記位置情報とが前記第１のデータ構造体と第３のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体と該第３のデータ構造体を作成する索引作成手段と、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体とを索引として格納する記憶手段と、を備え、前記第１のデータ構造体は、前記第１の値と該第１の値に対応付けられた前記第２のデータ構造体の位置情報とをエントリとして含むとともに、前記第２の値に対応付けられた前記第３のデータ構造体の位置情報をエントリとして含み、前記第２のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まず、前記第３のデータ構造体は、前記第２の値と該第２の値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とする。

また、本発明のさらに別の態様にかかるデータベース管理システムは、複数のレコード間において所定のフィールドに登録されうるＮＵＬＬ値および非ＮＵＬＬ値と該ＮＵＬＬ値および該非ＮＵＬＬ値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた索引を作成するデータベース管理システムであって、前記ＮＵＬＬ値と前記位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられ、前記非ＮＵＬＬ値と前記位置情報とが前記第１のデータ構造体と第３のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体と該第３のデータ構造体を作成する索引作成手段と、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体とを索引として格納する記憶手段と、を備え、前記第１のデータ構造体は、前記ＮＵＬＬ値に対応付けられた前記第２のデータ構造体の位置情報をエントリとして含むとともに、前記非ＮＵＬＬ値に対応付けられた前記第３のデータ構造体の位置情報をエントリとして含み、前記第２のデータ構造体は、前記ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該ＮＵＬＬ値自体をエントリとして含まず、前記第３のデータ構造体は、前記非ＮＵＬＬ値と該非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とする。

また、本発明のさらに別の態様にかかるデータベース管理システムは、複数のレコード間において第１のフィールドに登録されうる第１の値と該第１の値を前記第１のフィールドに含んだレコードの第１の位置情報とを対応付け、且つ、前記複数のレコード間において第２のフィールドに登録されうる第２の値と該第２の値を前記第２のフィールドに含んだレコードの第２の位置情報とを対応付けた索引を作成するデータベース管理システムであって、前記第１の値と前記第１の位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体を作成する索引作成手段と、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体とを索引として格納する記憶手段と、を備え、前記第１のデータ構造体は、前記第１の値と該第１の値に対応付けられた前記第２のデータ構造体の位置情報とをエントリとして含み、前記第２のデータ構造体は、前記第２の値と該第２の値を前記第２のフィールドに含んだレコードの前記第２の位置情報とをエントリとして含み且つ前記第１の値自体をエントリとして含まないことを特徴とする。

また、本発明のさらに別の態様にかかるプログラムは、複数のレコード間において所定のフィールドに登録されうる第１の値および第２の値と該第１の値および該第２の値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、所望のキーが前記第１の値を示す場合に、前記索引を構成する第１のデータ構造体から当該所望のキーを検索することによって、前記索引を構成し且つ該第１の値に対応付けられた第２のデータ構造体の位置情報を取得する工程と、前記所望のキーが前記第２の値を示す場合に、前記第１のデータ構造体から当該所望のキーを検索することによって、前記索引を構成し且つ該第２の値に対応付けられた第３のデータ構造体の位置情報を取得する工程と、前記所望のキーが前記第１の値を示す場合に、取得した前記位置情報に対応付けられた第２のデータ構造体から、前記第１の値を前記所定のフィールドに含んだレコードの位置情報を取得する工程と、前記所望のキーが前記第２の値を示す場合に、取得した前記位置情報に対応付けられた第３のデータ構造体から、前記第２の値を検索することによって、該第２の値を前記所定のフィールドに含んだレコードの位置情報を取得する工程と、を含み、前記第２のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まず、前記第３のデータ構造体は、前記第２の値と該第２の値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とする。

また、本発明のさらに別の態様にかかるプログラムは、複数のレコード間において所定のフィールドに登録されうるＮＵＬＬ値および非ＮＵＬＬ値と該ＮＵＬＬ値および該非ＮＵＬＬ値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、所望のキーがＮＵＬＬ値を示す場合に、前記索引を構成する第１のデータ構造体から、該ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報を取得する第１工程と、所望のキーが非ＮＵＬＬ値を示す場合に、前記索引を構成する第２のデータ構造体から当該非ＮＵＬＬ値を検索することによって、該非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報を取得する第２工程と、を含み、前記第１のデータ構造体は、前記ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該ＮＵＬＬ値自体をエントリとして含まないことを特徴とする。

また、本発明のさらに別の態様にかかるプログラムは、複数のレコード間において第１のフィールドに登録されうる第１の値と該第１の値を前記第１のフィールドに含んだレコードの第１の位置情報とを対応付け、且つ、前記複数のレコード間において第２のフィールドに登録されうる第２の値と該第２の値を前記第２のフィールドに含んだレコードの第２の位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、前記索引を構成する第１のデータ構造体から前記第１の値を示す第１のキーを検索することによって、前記索引を構成し且つ該第１の値に対応付けられた第２のデータ構造体の位置情報を取得する第１工程と、取得した前記位置情報に対応付けられた前記第２のデータ構造体から、前記第２の値を示す第２のキーを検索することによって、前記第２の値を前記所定のフィールドに含んだレコードの位置情報を取得する第２工程と、を含み、前記第２のデータ構造体は、前記第１の値をエントリとして含まないことを特徴とする。

本発明によれば、同一のフィールドにおいて取りうる各値（キー）で特定されるレコードの索引を、少なくとも二段構造で構成し、かつ後段の索引が前段の索引のキーをエントリとして含まないので、ページ使用効率およびキャッシュの効果を高めることができ、さらに、後段のデータ構造体にビットマップ索引で使われるようなデータ構造体の使用を避けることによって、更新処理の同時実行性能をも落とさないことができるという効果を奏する。

以下に添付図面を参照して、この発明にかかるデータベース管理システムおよびプログラムの最良な実施の形態を詳細に説明する。

図１は、後述する実施の形態間で共通するデータベース管理システムの構成を示す概略図である。図１に示すように、データベース管理システム１００は、ＰＣ（Personal Computer）などのコンピュータによって実現することができる。具体的には、データベース管理システム１００は、データベース管理システム１００の各部を集中的に制御するＣＰＵ（Central Processing Unit）１０２と、ＣＰＵ１０２を動作させるプログラムやＣＰＵ１０２の処理対象となる種々のデータを格納する一次記憶装置１０５と、データベースを格納した二次記憶装置１０６と、を備えて構成され、これらの各部間は、データバス１１４を介してデータを送受信する。なお、一次記憶装置１０５は、ＲＯＭ（Read Only Memory）１０３及びＲＡＭ（Random Access Memory）１０４等のアクセス速度の高速な半導体記憶装置からなり、二次記憶装置１０６は、高容量の磁気記憶装置であるＨＤＤ（Hard Disk Drive）１０７からなる。

また、本発明の実施の形態にかかるデータベース管理システム１００は、データベース管理を行うに際して必要な処理要求の受け付けや処理結果の出力を可能にするための入出力手段を備える。その入出力手段は、ネットワークインターフェース１１０によって実現しても良いし、汎用的なＰＣが備えた構成、すなわち、ＣＤ−ＲＯＭやＦＤ等の可搬性を有する記憶媒体１０８ａを駆動するリムーバブルディスク装置１０８、ＣＲＴ（Cathode Ray Tube）やＬＣＤ（Liquid Crystal Display）等の表示装置１１１、操作者がＣＰＵ１０２に命令や情報等を入力するためのキーボード１１２やポインティングデバイス１１３によって実現しても良い。また、図示するように、データベース管理システム１００は、これらすべてをデータバス１１４に接続して備えても良い。なお、ネットワークインターフェース１１０によって入出力手段を実現する場合には、データベース管理システム１００は、データウェアハウスのサーバのように機能させることができる。

上記した構成のように、データベース管理システム１００が行う種々の処理は、ＣＰＵ１０２によって実行される。より具体的には、それは、一次記憶装置１０５のＲＡＭ１０４上に展開されたデータベース管理プログラムが担う。該データベース管理プログラムは、機能分担された複数のモジュールからなり、これらモジュールはデータベース管理システム１００の構成要素とも言える。なお、そのデータベース管理プログラムは、ＲＯＭ１０３やＨＤＤ１０７に予め格納されていても良いし、記憶媒体１０８ａによって提供されても良いし、ネットワークインターフェース１１０によって外部装置からネットワーク１０９を介して提供されてもよい。

図２は、上記したモジュール構成の観点で示したデータベース管理システム１００の概略構成図である。図２に示すように、データベース管理システム１００は、ＨＤＤ１０７等に格納されたデータベース２５と、ＳＱＬ命令等の処理要求を受け付けて該処理要求の構文解析や最適化などを行う処理解析部２１と、処理解析部２１によって解析された処理要求に応じてデータベース２５を検索してその検索結果を得る検索部２２と、処理解析部２１によって解析された処理要求に応じてデータベース２５を更新する更新部２３と、検索部２２による検索結果や更新部２３による更新結果等の処理結果を出力する出力部２４と、を備える。なお、図２示したモジュール構成は、データベース管理システム１００に検索処理および更新処理を実行させるための最小の構成を指すが、データベース管理システム１００は、後述する各実施の形態の特徴と言える多段構造の索引を作成するための手段（例えば、索引作成部）をも備える。

以下に説明する各実施の形態は、上記構成を有するデータベース管理システム１００の処理を示すものであるが、各実施の形態の特徴の理解を容易にするために、データベース２５に、図３に示すようなテーブルが格納されていることを想定し、データベース管理システム１００はそのテーブルに対して各種の処理を行うこととする。

図３に示すテーブルは、８つのレコードからなり、各レコードは、「ＲＯＷＩＤ」、「文書名」、「状況」、「作業者」の４つのフィールドからなる。このテーブルは、種々の文書について作成から最終的に承認を受けるまでの作業進捗状況を表すものである。

図３に示すテーブルにおいて、「文書名」フィールドは、作業対象となる文書の名前を格納する欄である。「状況」フィールドは、文書の作業進捗に応じて、その値が作成中→審査中→承認中→承認済と変化する限られたデータの欄であり、比較的更新が頻繁に発生する。「作業者」フィールドは、その文書に対する現在の作業者が格納される欄であり、その値として、たとえば、作成中なら作成者、審査中なら審査者、承認中なら承認者が格納される。この「作業者」フィールドもまた、「状況」フィールドと同様に、更新が頻繁に発生する。

特に、「作業者」フィールドのデータは、以下の特徴を有する。
・作業者は社員の数だけありえるのでデータの種類が多い。
・承認済の文書に対しては、作業者は存在しないので「無名」が格納されているとする。
・作業者には偏りがある。例：管理職の社員は作業者になることが多い。承認済文書は多数存在するので「無名」の作業者も多い。

以下に、データベース管理システム１００が、図３に示すテーブルに対して実行するデータベース管理方法について、異なる実施の形態毎に説明する。

（第１の実施の形態）
図４は、第１の実施の形態にかかるデータベース管理システム１００によって予め作成される索引の概念図である。図４に示すように、索引は二段に階層化されている。１段目の索引は、複数の異なるキーと、各キーに対応付けられた別のデータ構造体の位置情報（ポインタ）とをエントリとしたデータ構造体を示す。一方、２段目の索引は、１段目のデータ構造体の各キーに対応付けられたポインタによって特定されるデータ構造体であり、対応したキーを含んだレコードのＲＯＷＩＤをエントリとしている。特に、２段目のデータ構造体には、キー情報がなく、ＲＯＷＩＤの情報のみからなる。

この二段の索引は、「状況」フィールドのように頻繁に更新され且つその取りうる値の種類の少ない値をキーとする場合に特に有効である。図４の例で言えば、１段目の索引は、「状況」フィールドのすべての取りうる値のうち実際にそれを含んだレコードが存在する値と各値の位置情報であるポインタとのペアをエントリとしたデータ構造体を示す。そのデータ構造体は、具体的には、「作成中」とポインタ０ｘ０ａ０１とのペアと、「審査中」とポインタ０ｘ０ｂ０１とのペアと、「承認済」とポインタ０ｘ０ｅ０１とのペアとを含んでいる。また、図４の例では、２段目の索引は、「作成中」を値として含むレコードのＲＯＷＩＤ１，７，８をエントリとしたデータ構造体（ポインタ０ｘ０ａ０１で識別される）と、「審査中」を値として含むレコードのＲＯＷＩＤ２をエントリとしたデータ構造体（ポインタ０ｘ０ｂ０１で識別される）と、「承認済」を値として含むレコードのＲＯＷＩＤ４，５をエントリとしたデータ構造体（ポインタ０ｘ０ｅ０１で識別される）と、を含んでいる。

このような索引は、データベース管理システム１００によって作成され、ＨＤＤ１０７やリムーバブルディスク装置１０８などの所定の記憶手段に格納される。なお、ネットワークインターフェース１１０を介して接続される外部装置をその索引を格納する記憶手段として利用しても良い。

次に、第１の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図５は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、頻繁に更新され且つその取りうる値の種類の少ない値であるキーを、図４に示した構造の索引から検索することとする。そこで、そのキーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ１０１）。つぎに、検索部２２は、その１段目のデータ構造体から、指定されたキーを検索し（ステップＳ１０２）、検索されたキーに対応する２段目のデータ構造体のポインタを取得する（ステップＳ１０３）。続いて、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ１０４）。これにより、目的としたキーを含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図４の例で言えば、「審査中」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ２が取得され、ＲＯＷＩＤ２で特定されるレコードが検索結果として出力されるという工程を辿る。

このように、２段目の各データ構造体は、同じキーに対するＲＯＷＩＤ情報を保持しているので、それら各データ構造体にキーを格納する必要がない。

なお、各データ構造体に適用される構造には特に制限はなく、Ｂ木索引構造でもハッシュテーブル構造でも構わない。ただし、更新処理の同時実行性能を落とさないために、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。

また、データの追加は、検索時と同様に１段目のデータ構造体に対して、追加先になる２段目のデータ構造体のポインタを取得し、取得したデータ構造体に対して新たなデータを追加することにより行う。データの削除も同様で、１段目のデータ構造体に対して、削除されるデータが格納されている２段目のデータ構造体のポインタを取得し、取得したデータ構造体からデータを削除する。

以上に説明したように、第１の実施の形態にかかるデータベース管理方法によれば、２段目のデータ構造体において、キーを重ねて登録しないことで、ページ使用効率を高めることが可能になり、また、キャッシュの効果を高めることも可能になる。さらに、２段目のデータ構造体としてビットマップ索引で使われるようなデータ構造体を使用しないことで、更新処理の同時実行性能を落とさないこともできる。

（第２の実施の形態）
図６は、第２の実施の形態にかかるデータベース管理システム１００によって予め作成される索引の概念図である。図６に示すように、索引は第１の実施の形態と同様に二段に階層化されている。１段目の索引は、２種類のエントリからなるデータ構造体を示す。その２種類のうちの一つ（第１の種類）は、第１の実施の形態にかかるデータベース管理方法にかかる１段目の索引と同様なエントリである。すなわち、それは、複数の異なるキーと、各キーに対応付けられた別のデータ構造体の位置情報（ポインタ）とをペアとしたエントリである。特に、このエントリに含めるキーは、複数のキーのうち実際に登録されることの多いキーであることが好ましい。図３に示すテーブルの例で言えば、「作業者」フィールドの「無名」や管理職社員の名前などがそのようなキーに該当する。もう一つの種類（第２の種類）は、第１の種類以外のすべてのキーとそれらに対応付けられた別のデータ構造体の位置情報（ポインタ）とをペアとしたエントリである。なお、複数のキーに対していずれを第１の種類または第２の種類に属させるかは例えば決定木に従う。

一方、２段目の索引は、１段目の第１の種類のエントリの各キーに対応付けられたポインタによって特定されるデータ構造体と、第２の種類のエントリの各キーに対応付けられたポインタによって特定されるデータ構造体とからなる。第１の種類のエントリに対応するデータ構造体は、第１の実施の形態の２段目のデータ構造体と同様に、対応したキーを含んだレコードのＲＯＷＩＤをエントリとしている。一方、第２の種類のエントリに対応するデータ構造体は、各キーとそれに対応するＲＯＷＩＤとのペアをエントリとしている。

図６の例で言えば、１段目の索引は、第１の種類のデータ構造体として、「作業者」フィールドの値のうち、値が登録されていないことを示す「無名」とポインタ０ｘ０９０１とのペアと、「鈴木」とポインタ０ｘ００１１とのペアなどを含んでおり、第２の種類のデータ構造体として、第１の種類に含まれないその他の値に対応付けられた別の構造体の位置情報（ポインタ）のみを含んでいる。また、図６の例では、２段目の索引は、１段目の第１の種類のエントリに対応するデータ構造体として、「無名」の登録を意味するレコードのＲＯＷＩＤ４，５をエントリとしたデータ構造体（ポインタ０ｘ０９０１で識別される）と、「鈴木」を値として含むレコードのＲＯＷＩＤ３，６をエントリとしたデータ構造体（ポインタ０ｘ００１１で識別される）と、を含んでいる。さらに、図６の例では、２段目の索引は、１段目の第２の種類のエントリ（その他）に対応するデータ構造体として、「作業者」フィールドの「佐藤」とその値を含むレコードのＲＯＷＩＤ８とのペアと、「作業者」フィールドの「山田」とその値を含むレコードのＲＯＷＩＤ１とのペアと、「作業者」フィールドの「山田」とその値を含むレコードのＲＯＷＩＤ７とのペアと、をエントリとしたデータ構造体（ポインタ０ｘ０ｆ０１で識別される）を含んでいる。

この第２の実施の形態において使用される索引もまた、第１の実施の形態と同様に、データベース管理システム１００によって作成され、所定の記憶手段に格納される。

次に、第２の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図７は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、決定木から得られるように値に偏りが存在するようなキーを、図６に示した構造の索引から検索することとする。そこで、そのキーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ２０１）。つぎに、検索部２２は、１段目の第１の種類のデータ構造体から、指定されたキーを検索する（ステップＳ２０２）。指定されたキーが１段目の第１の種類のデータ構造体において見つかれば（ステップＳ２０３，Ｙｅｓ）、そのキーに対応する２段目のデータ構造体のポインタを取得し（ステップＳ２０４）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ２０５）。

一方、ステップＳ２０３において、指定されたキーが１段目の第１の種類のデータ構造体において見つからなければ（ステップＳ２０３，Ｎｏ）、その他のエントリに対応する２段目のデータ構造体のポインタを取得し（ステップＳ２０６）、そのデータ構造体から、指定されたキーを検索する（ステップＳ２０７）。そして、その検索の結果、キーと一致したエントリのＲＯＷＩＤを取得する（ステップＳ２０８）。以上のようにして、目的としたキーを含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図６の例で言えば、「鈴木」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ３，６が取得され、それらＲＯＷＩＤ３，６で特定されるレコードが検索結果として出力されるという工程を辿る。他の例として、「山田」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ１，７が取得され、それらＲＯＷＩＤ１，７で特定されるレコードが検索結果として出力されるという工程を辿る。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

２段目の各構造体を、そこに格納されるエントリ数を無視して作成すると、ページの使用効率がかえって悪くなることがある。たとえば、構造体に一件しかエントリが入っていなくとも、その構造体のために１ページが確保されてしまうので、そのような構造体が多数存在すると、２段目においてキーを格納しないことによる効果が薄くなってしまう。このような場合でも、以上に説明したように、第２の実施の形態にかかるデータベース管理方法によれば、１段目の第２の種類のエントリに対応する２段目のデータ構造体のように、少数のエントリしか入らない構造体をまとめることで、ページ使用効率を高くすることができる。

また、キーの種類が多い場合、全てのキーに対してエントリを作成していると、１段目の構造体での検索コストは無視できなくなる。このような場合でも、第２の実施の形態にかかるデータベース管理方法によれば、１段目において、使用頻度の低いキーに対して逐一エントリを格納しないことで、１段目のデータ構造体のエントリ数を抑え、検索コストも抑えることができる。

（第３の実施の形態）
図８は、第３の実施の形態にかかるデータベース管理システム１００によって作成される索引の概念図である。図８に示すように、索引は第１の実施の形態と同様に二段に階層化されている。１段目の索引は、２種類のエントリからなるデータ構造体を示す。その２種類とは、ＮＵＬＬを示すキーに対応付けられた別のデータ構造体の位置情報（ポインタ）のエントリと、非ＮＵＬＬを示すキーに対応付けられたさらに別のデータ構造体の位置情報（ポインタ）のエントリである。

一方、２段目の索引は、１段目のＮＵＬＬのエントリに対応付けられたポインタによって特定されるデータ構造体と、非ＮＵＬＬに対応付けられたポインタによって特定されるデータ構造体とからなる。前者のデータ構造体は、第１の実施の形態の２段目のデータ構造体と同様に、対応したキーを含んだレコードのＲＯＷＩＤをエントリとしている。一方、後者のデータ構造体は、各キーとそれに対応するＲＯＷＩＤとのペアをエントリとしている。

この索引は、図３に示すテーブルにおいて、「状況」フィールドが「承認済」の値を示す場合に、「作業者」フィールドに値としてＮＵＬＬを格納するような場合に適している。

図８の例で言えば、１段目の索引は、データ構造体として、ＮＵＬＬのエントリに対応付けられた別の構造体のポインタ０ｘ０２０１と、非ＮＵＬＬのエントリに対応付けられた別の構造体のポインタ０ｘ０８０１とを含んでいる。また、図８の例では、２段目の索引は、１段目のＮＵＬＬのエントリに対応するデータ構造体として、ＲＯＷＩＤ４，５をエントリとしたデータ構造体（ポインタ０ｘ０２０１で識別される）を含んでいる。さらに、図８の例では、２段目の索引は、１段目の非ＮＵＬＬのエントリに対応するデータ構造体として、「作業者」フィールドの「佐藤」とその値を含むレコードのＲＯＷＩＤ８とのペアと、「作業者」フィールドの「山田」とその値を含むレコードのＲＯＷＩＤ１とのペアと、「作業者」フィールドの「山田」とその値を含むレコードのＲＯＷＩＤ７とのペアと、をエントリとしたデータ構造体（ポインタ０ｘ０８０１で識別される）を含んでいる。

この第３の実施の形態において使用される索引もまた、第１の実施の形態と同様に、データベース管理システム１００によって作成され、所定の記憶手段に格納される。

次に、第３の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図９は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、ＮＵＬＬと非ＮＵＬＬのいずれかに識別されるキーを、図８に示した構造の索引から検索することとする。そこで、そのキーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ３０１）。つぎに、検索部２２は、指定されたキーがＮＵＬＬか非ＮＵＬＬかを判断する（ステップＳ３０２）。指定されたキーがＮＵＬＬであれば（ステップＳ３０２，Ｙｅｓ）、ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ３０３）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ３０４）。

一方、ステップＳ３０２において、指定されたキーが非ＮＵＬＬであれば（ステップＳ３０２，Ｎｏ）、非ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ３０５）、そのデータ構造体から、指定されたキーを検索する（ステップＳ３０６）。そして、その検索の結果、キーと一致したエントリのＲＯＷＩＤを他のエントリに対応する２段目のデータ構造体のポインタを取得する（ステップＳ３０７）。以上のようにして、目的としたキーを含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図８の例で言えば、ＮＵＬＬがキーとして指定されているとすると、最終的に、ＲＯＷＩＤ４，５が取得され、それらＲＯＷＩＤ４，５で特定されるレコードが検索結果として出力されるという工程を辿る。他の例として、非ＮＵＬＬの「山田」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ１，７が取得され、それらＲＯＷＩＤ１，７で特定されるレコードが検索結果として出力されるという工程を辿る。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

以上に説明したように、第３の実施の形態にかかるデータベース管理方法によれば、キーをＮＵＬＬのキーを持つデータ構造体を非ＮＵＬＬのデータ構造体と分けて用意しているので、ＮＵＬＬの状態を示すフラグを格納せずに済み、結果的に、ページの使用効率を高くすることができる。

（第４の実施の形態）
第４の実施の形態にかかるデータベース管理システム１００は、第１の実施の形態に示した索引と第３の実施の形態に示した索引とを組み合わせた索引を作成し、それを用いた検索を行うことを特徴とする。具体的には、１段目の索引と２段目の索引を第３の実施の形態で示した１段目の索引と２段目の索引のように構成し、２段目の非ＮＵＬＬに対応する索引と３段目の索引を第１の実施の形態で示した１段目の索引と２段目の索引のように構成する。

図１０は、第４の実施の形態にかかるデータベース管理方法によって予め構築される索引の概念図である。図１０において、１段目の索引と２段目の索引については、非ＮＵＬＬに対応するデータ構造体のエントリが、各キーに対してＲＯＷＩＤではなくポインタが対応付けられている点を除き、図８に示した二段の索引構造に対応するため、ここではその説明を省略する。また、図１０において、２段目の索引の非ＮＵＬＬに対応する索引と３段目の索引についても、図４に示した二段の索引構造の概念と同じであるため、ここではその説明を省略する。

次に、第４の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図１１は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、ＮＵＬＬと非ＮＵＬＬのいずれかに識別されるキーを、図１０に示した構造の索引から検索することとする。そこで、そのキーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ４０１）。つぎに、検索部２２は、指定されたキーがＮＵＬＬか非ＮＵＬＬかを判断する（ステップＳ４０２）。指定されたキーがＮＵＬＬであれば（ステップＳ４０２，Ｙｅｓ）、ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ４０３）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ４０４）。

一方、ステップＳ４０２において、指定されたキーが非ＮＵＬＬであれば（ステップＳ４０２，Ｎｏ）、非ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ４０５）、そのデータ構造体から、指定されたキーを検索する（ステップＳ４０６）。そして、検索されたキーに対応する３段目のデータ構造体のポインタを取得し（ステップＳ４０７）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ４０８）。これにより、目的としたキーを含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図１０の例で言えば、ＮＵＬＬがキーとして指定されているとすると、最終的に、ＲＯＷＩＤ４，５が取得され、それらＲＯＷＩＤ４，５で特定されるレコードが検索結果として出力されるという工程を辿る。他の例として、「山田」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ１，７が取得され、それらＲＯＷＩＤ１，７で特定されるレコードが検索結果として出力されるという工程を辿る。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

以上に説明したように、第４の実施の形態にかかるデータベース管理方法によれば、第１の実施の形態で示した索引構造と第３の実施の形態で示したで示した索引構造とを組み合わせることにより、三段構造の索引を作成し、またそれを用いた検索を可能としたので居、両実施の形態にかかるデータベース管理方法の効果を享受することができる。

（第５の実施の形態）
第５の実施の形態にかかるデータベース管理システム１００は、第２の実施の形態に示した索引と第３の実施の形態に示した索引とを組み合わせた索引を作成し、それを用いた検索を行うことを特徴とする。具体的には、１段目の索引と２段目の索引を第３の実施の形態で示した１段目の索引と２段目の索引のように構成し、２段目の非ＮＵＬＬに対応する索引と３段目の索引を第２の実施の形態で示した１段目の索引と２段目の索引のように構成する。

図１２は、第５の実施の形態にかかるデータベース管理方法によって予め構築される索引の概念図である。図１２において、１段目の索引と２段目の索引については、非ＮＵＬＬに対応するデータ構造体のエントリが、各キーに対してＲＯＷＩＤではなくポインタが対応付けられている点と第２の実施の形態に示したように２種類のデータ構造体を有するという点を除き、図８に示した二段の索引構造に対応するため、ここではその説明を省略する。また、図１２において、２段目の索引の非ＮＵＬＬに対応する索引と３段目の索引についても、図６に示した二段の索引構造の概念と同じであるため、ここではその説明を省略する。

次に、第５の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図１３は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、ＮＵＬＬと非ＮＵＬＬのいずれかに識別されるキーを、図１２に示した構造の索引から検索することとする。そこで、そのキーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ５０１）。つぎに、検索部２２は、指定されたキーがＮＵＬＬか非ＮＵＬＬかを判断する（ステップＳ５０２）。指定されたキーがＮＵＬＬであれば（ステップＳ５０２，Ｙｅｓ）、ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ５０３）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ５０４）。

一方、ステップＳ５０２において、指定されたキーが非ＮＵＬＬであれば（ステップＳ５０２，Ｎｏ）、非ＮＵＬＬに対応する２段目のデータ構造体のポインタを取得し（ステップＳ５０５）、そのデータ構造体から、指定されたキーを検索する（ステップＳ５０６）。指定されたキーが非ＮＵＬＬに対応する２段目の第１の種類のデータ構造体において見つかれば（ステップＳ５０７，Ｙｅｓ）、そのキーに対応する３段目のデータ構造体のポインタを取得し（ステップＳ５０８）、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ５０９）。

一方、ステップＳ５０７において、指定されたキーが２段目の第１の種類のデータ構造体において見つからなければ（ステップＳ５０７，Ｎｏ）、その他のエントリに対応する３段目のデータ構造体のポインタを取得し（ステップＳ５１０）、そのデータ構造体から、指定されたキーを検索する（ステップＳ５１１）。そして、その検索の結果、キーと一致したエントリのＲＯＷＩＤを取得する（ステップＳ５１２）。以上のようにして、目的としたキーを含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図１２の例で言えば、ＮＵＬＬがキーとして指定されているとすると、最終的に、ＲＯＷＩＤ４，５が取得され、それらＲＯＷＩＤ４，５で特定されるレコードが検索結果として出力されるという工程を辿る。他の例として、「山田」がキーとして指定されているとすると、最終的に、ＲＯＷＩＤ１，７が取得され、それらＲＯＷＩＤ１，７で特定されるレコードが検索結果として出力されるという工程を辿る。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

以上に説明したように、第５の実施の形態にかかるデータベース管理方法によれば、第２の実施の形態で示した索引構造と第３の実施の形態で示したで示した索引構造とを組み合わせることにより、三段構造の索引を作成し、またそれを用いた検索を可能としたので居、両実施の形態にかかるデータベース管理方法の効果を享受することができる。

（第６の実施の形態）
第６の実施の形態にかかるデータベース管理システム１００は、第１〜第５の実施の形態において、異なる複数のキーを用いて検索すること、いわゆる複合検索を可能にした索引を作成し、それを用いた検索を行うことを特徴とする。

ここでは、説明を簡単にするため、第１の実施の形態において示した索引に対して、異なる２つのキーが与えられた場合の形態を説明する。

図１４は、第６の実施の形態にかかるデータベース管理方法によって予め構築される索引の概念図である。図１４に示すように、索引は二段に階層化されている。１段目の索引は、第１の実施の形態で示した図４の１段目と同じデータ構造体を示すが、２段目のデータ構造体は、１段目のキーとは異なるキーのそれぞれとＲＯＷＩＤとをペアとしたエントリを含んでいる。換言すれば、図４に示した２段目のデータ構造体の各エントリに、キーが対応付けられている。

次に、第６の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図１５は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、頻繁に更新され且つその取りうる値の種類の少ない値である第１キーと、決定木から得られるように値に偏りが存在するような第２キーとり両方含むレコードを、図１４に示した構造の索引から検索することとする。そこでまず、第１キーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ６０１）。つぎに、検索部２２は、その１段目のデータ構造体から、指定された第１キーを検索し（ステップＳ６０２）、検索された第１キーに対応する２段目のデータ構造体のポインタを取得する（ステップＳ６０３）。続いて、そのデータ構造体から、指定された第２キーを検索し（ステップＳ６０４）、その検索の結果、第２キーと一致したエントリのＲＯＷＩＤを取得する（ステップＳ６０５）。これにより、目的とした第１キーおよび第２キーの両方を含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図１４の例で言えば、第１キーとして「状況」フィールドの値である「作成中」が指定され、第２キーとして「作業者」フィールドの値である「山田」が指定されているとすると、最終的に、ＲＯＷＩＤ１，７が取得され、これらＲＯＷＩＤ１，７で特定されるレコードが検索結果として出力されるという工程を辿る。

このように、少なくとも、２段目の各データ構造体には、第１キーを格納する必要がない。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

以上に説明したように、第６の実施の形態にかかるデータベース管理方法によれば、複合検索に対しても、第１の実施の形態による効果を享受することができる。

（第７の実施の形態）
第７の実施の形態にかかるデータベース管理システム１００は、第６の実施の形態の変形例である。具体的には、第６の実施の形態に示した２段目のデータ構造体にさらに第１の実施の形態に示した二段の索引構造を適用することによって三段の索引構造を作成し、その索引を用いた検索を行うことを特徴とする。換言すれば、第１キーの索引と第２キーの索引とにそれぞれ第１の実施の形態に示した二段の索引構造を適用する。

図１６は、第７の実施の形態にかかるデータベース管理方法によって予め構築される索引の概念図である。図１６において、１段目の索引については、図１４に示した１段目の索引に対応し、２段目の索引については、各データ構造体のエントリが、各キーに対してＲＯＷＩＤではなくポインタが対応付けられている点を除き、図１４に示した２段目の索引に対応するため、ここではその説明を省略する。また、図１６において、２段目の索引と３段目の索引との関係についても、図４に示した二段の索引構造と同じであるため、ここではその説明を省略する。

次に、第７の実施の形態にかかるデータベース管理方法に従った検索処理について説明する。図１７は、その検索処理を示すフローチャートである。まず、処理解析部２１は、ＳＱＬ文等の処理要求を受け付けて、その解析および最適化を行う。ここでは、その解析および最適化の結果、検索部２２が、頻繁に更新され且つその取りうる値の種類の少ない値である第１キーと、決定木から得られるように値に偏りが存在するような第２キーとり両方含むレコードを、図１６に示した構造の索引から検索することとする。そこでまず、第１キーが属するフィールドをエントリとした１段目のデータ構造体のポインタを取得する（ステップＳ７０１）。つぎに、検索部２２は、その１段目のデータ構造体から、指定された第１キーを検索し（ステップＳ７０２）、検索された第１キーに対応する２段目のデータ構造体のポインタを取得する（ステップＳ７０３）。続いて、そのデータ構造体から、指定された第２キーを検索し（ステップＳ７０４）、検索された第２キーに対応する３段目のデータ構造体のポインタを取得する（ステップＳ７０５）。そして、取得したポインタに格納されるデータ構造体のすべてのＲＯＷＩＤを取得する（ステップＳ７０６）。これにより、目的とした第１キーおよび第２キーの両方を含んだすべてのレコード、すなわち検索結果を取得することができ、その検索結果は出力部２４から出力される。

この検索は、図１６の例で言えば、第１キーとして「状況」フィールドの値である「作成中」が指定され、第２キーとして「作業者」フィールドの値である「佐藤」が指定されているとすると、最終的に、ＲＯＷＩＤ８が取得され、これらＲＯＷＩＤ８で特定されるレコードが検索結果として出力されるという工程を辿る。

このように、少なくとも、２段目の各データ構造体には、第１キーを格納する必要がなく、また３段目の各データ構造についても第２キーを格納する必要がない。

なお、第１の実施の形態と同様に、各データ構造体に適用される構造には特に制限はないが、ビットマップ索引で使われるようなデータ構造体を使用しないことが好ましい。また、データの追加および削除については、第１の実施の形態に説明した通りである。

また、上述した説明では、２段目と３段目の索引に対して、第１の実施の形態の索引構造を適用したが、他の実施の形態の索引構造を適用しても良い。

以上に説明したように、第７の実施の形態にかかるデータベース管理方法によれば、複合検索に対しても、第１〜第５の実施の形態にかかる索引構造を適用することができ、それら実施の形態による効果を享受することができる。

上述した第１〜第７の実施の形態にかかるデータベース管理システム１００によって実行されるデータベース管理方法は、ＰＣ等のコンピュータにインストール可能な形式又は実行可能な形式のファイル形態のコンピュータプログラムとして、ＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供されることができる。

また、そのようなコンピュータプログラムは、インターネット等のネットワークに接続されたコンピュータ上に格納されて、ネットワーク経由でＰＣ等にダウンロードされることにより提供されても良い。

本発明の実施の形態にかかるデータベース管理システム、データベース管理方法およびプログラムは、荷物の配送状況のように状況データが頻繁に更新される荷物配送管理システム等の管理システムに適用するとより効果的である。

本発明の実施の形態にかかるデータベース管理システムの構成を示す概略図である。 本発明の実施の形態にかかるデータベース管理システムのモジュール構成図である。 索引対象となるテーブルの例を示す図である。 第１の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第１の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第２の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第２の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第３の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第３の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第４の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第４の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第５の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第５の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第６の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第６の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。 第７の実施の形態にかかるデータベース管理システムによって形成される索引の概念図である。 第７の実施の形態にかかるデータベース管理方法による検索処理を示すフローチャートである。

符号の説明

２１ 処理解析部
２２ 検索部
２３ 更新部
２４ 出力部
２５ データベース
１００ データベース管理システム
１０２ ＣＰＵ
１０３ ＲＯＭ
１０４ ＲＡＭ
１０５ 一次記憶装置
１０６ 二次記憶装置
１０７ ＨＤＤ
１０８ リムーバブルディスク装置
１０８ａ 記憶媒体
１０９ ネットワーク
１１０ ネットワークインターフェース
１１１ 表示装置
１１２ キーボード
１１３ ポインティングデバイス
１１４ データバス

Claims (12)

1. 複数のレコード間において所定のフィールドに登録されうる第１の値および第２の値と該第１の値および該第２の値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた索引を作成するデータベース管理システムであって、
   前記第１の値と前記位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられ、前記第２の値と前記位置情報とが前記第１のデータ構造体と第３のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体と該第３のデータ構造体を作成する索引作成手段と、
   前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体とを索引として格納する記憶手段と、
   を備え、
   前記第１のデータ構造体は、前記第１の値と該第１の値に対応付けられた前記第２のデータ構造体の位置情報とをエントリとして含むとともに、前記第２の値に対応付けられた前記第３のデータ構造体の位置情報をエントリとして含み、
   前記第２のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まず、
   前記第３のデータ構造体は、前記第２の値と該第２の値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とするデータベース管理システム。
2. 複数のレコード間において所定のフィールドに登録されうるＮＵＬＬ値および非ＮＵＬＬ値と該ＮＵＬＬ値および該非ＮＵＬＬ値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた索引を作成するデータベース管理システムであって、
   前記ＮＵＬＬ値と前記位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられ、前記非ＮＵＬＬ値と前記位置情報とが前記第１のデータ構造体と第３のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体と該第３のデータ構造体を作成する索引作成手段と、
   前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体とを索引として格納する記憶手段と、
   を備え、
   前記第１のデータ構造体は、前記ＮＵＬＬ値に対応付けられた前記第２のデータ構造体の位置情報をエントリとして含むとともに、前記非ＮＵＬＬ値に対応付けられた前記第３のデータ構造体の位置情報をエントリとして含み、
   前記第２のデータ構造体は、前記ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該ＮＵＬＬ値自体をエントリとして含まず、
   前記第３のデータ構造体は、前記非ＮＵＬＬ値と該非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とするデータベース管理システム。
3. 前記索引作成手段は、前記非ＮＵＬＬ値と前記位置情報とが前記第１のデータ構造体と前記第３のデータ構造体と第４のデータ構造体との組み合わせによって対応付けられるように該第３のデータ構造体と該第４のデータ構造体を作成し、
   前記記憶手段は、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体と前記第４のデータ構造体とを索引として格納し、
   前記第３のデータ構造体は、前記非ＮＵＬＬ値と該非ＮＵＬＬ値に対応付けられた前記第４のデータ構造体の位置情報とをエントリとして含み、
   前記第４のデータ構造体は、前記非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該非ＮＵＬＬ値自体をエントリとして含まないことを特徴とする請求項２に記載のデータベース管理システム。
4. 前記非ＮＵＬＬ値は、第１の値と第２の値に分類され、
   前記索引作成手段は、前記第１の値と前記位置情報とが前記第３のデータ構造体と第４のデータ構造体との組み合わせによって対応付けられ、前記第２の値と前記位置情報とが前記第３のデータ構造体と第５のデータ構造体との組み合わせによって対応付けられるように該第３のデータ構造体と該第４のデータ構造体と該第５のデータ構造体を作成し、
   前記記憶手段は、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体と前記第４のデータ構造体と前記第５のデータ構造体とを索引として格納し、
   前記第３のデータ構造体は、前記第１の値と該第１の値に対応付けられた前記第４のデータ構造体の位置情報とをエントリとして含むとともに、前記第２の値に対応付けられた前記第５のデータ構造体の位置情報をエントリとして含み、
   前記第４のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まず、
   前記第５のデータ構造体は、前記第２の値と該第２の値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とする請求項２に記載のデータベース管理システム。
5. 複数のレコード間において第１のフィールドに登録されうる第１の値と該第１の値を前記第１のフィールドに含んだレコードの第１の位置情報とを対応付け、且つ、前記複数のレコード間において第２のフィールドに登録されうる第２の値と該第２の値を前記第２のフィールドに含んだレコードの第２の位置情報とを対応付けた索引を作成するデータベース管理システムであって、
   前記第１の値と前記第１の位置情報とが第１のデータ構造体と第２のデータ構造体との組み合わせによって対応付けられるように該第１のデータ構造体と該第２のデータ構造体を作成する索引作成手段と、
   前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体とを索引として格納する記憶手段と、
   を備え、
   前記第１のデータ構造体は、前記第１の値と該第１の値に対応付けられた前記第２のデータ構造体の位置情報とをエントリとして含み、
   前記第２のデータ構造体は、前記第２の値と該第２の値を前記第２のフィールドに含んだレコードの前記第２の位置情報とをエントリとして含み且つ前記第１の値自体をエントリとして含まないことを特徴とするデータベース管理システム。
6. 前記索引作成手段は、前記第２の値と該第２の位置情報とが前記第２のデータ構造体と第３のデータ構造体との組み合わせによって対応付けられるように該第２のデータ構造体と該第３のデータ構造体を作成し、
   前記記憶手段は、前記索引作成手段によって作成された前記第１のデータ構造体と前記第２のデータ構造体と前記第３のデータ構造体とを索引として格納し、
   前記第２のデータ構造体は、前記第２の値と該第２の値に対応付けられた前記第３のデータ構造体の位置情報とをエントリとして含み且つ前記第１の値をエントリとして含まず、
   前記第３のデータ構造体は、前記第２の値を前記第２のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第２の値自体をエントリとして含まないことを特徴とする請求項５に記載のデータベース管理システム。
7. 複数のレコード間において所定のフィールドに登録されうる第１の値および第２の値と該第１の値および該第２の値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、
   所望のキーが前記第１の値を示す場合に、前記索引を構成する第１のデータ構造体から当該所望のキーを検索することによって、前記索引を構成し且つ該第１の値に対応付けられた第２のデータ構造体の位置情報を取得する工程と、
   前記所望のキーが前記第２の値を示す場合に、前記第１のデータ構造体から当該所望のキーを検索することによって、前記索引を構成し且つ該第２の値に対応付けられた第３のデータ構造体の位置情報を取得する工程と、
   前記所望のキーが前記第１の値を示す場合に、取得した前記位置情報に対応付けられた第２のデータ構造体から、前記第１の値を前記所定のフィールドに含んだレコードの位置情報を取得する工程と、
   前記所望のキーが前記第２の値を示す場合に、取得した前記位置情報に対応付けられた第３のデータ構造体から、前記第２の値を検索することによって、該第２の値を前記所定のフィールドに含んだレコードの位置情報を取得する工程と、
   を含み、
   前記第２のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まず、
   前記第３のデータ構造体は、前記第２の値と該第２の値を前記所定のフィールドに含んだレコードの位置情報とをエントリとして含むことを特徴とするプログラム。
8. 複数のレコード間において所定のフィールドに登録されうるＮＵＬＬ値および非ＮＵＬＬ値と該ＮＵＬＬ値および該非ＮＵＬＬ値を前記所定のフィールドにそれぞれ含んだレコードの位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、
   所望のキーがＮＵＬＬ値を示す場合に、前記索引を構成する第１のデータ構造体から、該ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報を取得する第１工程と、
   所望のキーが非ＮＵＬＬ値を示す場合に、前記索引を構成する第２のデータ構造体から当該非ＮＵＬＬ値を検索することによって、該非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報を取得する第２工程と、
   を含み、
   前記第１のデータ構造体は、前記ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該ＮＵＬＬ値自体をエントリとして含まないことを特徴とするプログラム。
9. 前記第２工程は、前記所望のキーが非ＮＵＬＬ値を示す場合に、前記索引を構成する第２のデータ構造体から該非ＮＵＬＬ値を検索することによって、前記索引を構成し且つ該非ＮＵＬＬ値に対応付けられた第３のデータ構造体の位置情報を取得し、取得した該位置情報に対応付けられた前記第３のデータ構造体から、該非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報を取得することを含み、
   前記第３のデータ構造体は、前記非ＮＵＬＬ値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該非ＮＵＬＬ値自体をエントリとして含まないことを特徴とする請求項８に記載のプログラム。
10. 前記非ＮＵＬＬ値は、第１の値と第２の値に分類され、
    前記第２工程は、前記所望のキーが前記第１の値を示す場合に、取得した前記位置情報に対応付けられた第３のデータ構造体から、前記第１の値を前記所定のフィールドに含んだレコードの位置情報を取得し、前記所望のキーが前記第２の値を示す場合に、前記索引を構成し且つ取得した前記位置情報に対応付けられた第４のデータ構造体から、前記第２の値を検索することによって、該第２の値を前記所定のフィールドに含んだレコードの位置情報を取得することを含み、
    前記第３のデータ構造体は、前記第１の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第１の値自体をエントリとして含まないことを特徴とする請求項８に記載のプログラム。
11. 複数のレコード間において第１のフィールドに登録されうる第１の値と該第１の値を前記第１のフィールドに含んだレコードの第１の位置情報とを対応付け、且つ、前記複数のレコード間において第２のフィールドに登録されうる第２の値と該第２の値を前記第２のフィールドに含んだレコードの第２の位置情報とを対応付けた、記憶手段に格納された索引を用いて、コンピュータに所望のレコードを検索させるためのプログラムであって、
    前記索引を構成する第１のデータ構造体から前記第１の値を示す第１のキーを検索することによって、前記索引を構成し且つ該第１の値に対応付けられた第２のデータ構造体の位置情報を取得する第１工程と、
    取得した前記位置情報に対応付けられた前記第２のデータ構造体から、前記第２の値を示す第２のキーを検索することによって、前記第２の値を前記所定のフィールドに含んだレコードの位置情報を取得する第２工程と、
    を含み、
    前記第２のデータ構造体は、前記第１の値をエントリとして含まないことを特徴とするプログラム。
12. 前記第２工程は、取得した前記位置情報に対応付けられた前記第２のデータ構造体から、前記第２のキーを検索することによって、前記索引を構成し且つ前記第２の値に対応付けられた第３のデータ構造体の位置情報を取得し、取得した該位置情報に対応付けられた前記第３のデータ構造体から、該第２の値を前記所定のフィールドに含んだレコードの位置情報を取得することを含み、
    前記第３のデータ構造体は、前記第２の値を前記所定のフィールドに含んだレコードの位置情報をエントリとして含み且つ該第２の値自体をエントリとして含まないことを特徴とする請求項１１に記載のプログラム。

Images