(57)【要約】コンピュータシステム内のデータを記憶するためのデータベース構造において、第１のタイプの少なくとも１つのデータ要素が設けられており、これにはデータベースエントリを表す第２のタイプのデータ要素と、この第２の要素のデータ要素に対応づけられた第３のタイプのデータ要素が対応づけられている。その際、第２のタイプのデータ要素は第１のツリー構造内に配置されており、第３のタイプのデータ要素は第２のツリー構造内に配置されている。
2004518225.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステム内のデータを記憶するためのデータベース構造において、
第１のタイプ（ＩｎｆｏＣｌｕｓｔｅｒ）の少なくとも１つのデータ要素が設けられており、
該データ要素には、データベースエントリを表す第２のタイプ（ＩｎｆｏＴｙｐｅ）のデータ要素と、該第２のタイプ（ＩｎｆｏＴｙｐｅ）のデータ要素に対応づけられた第３のタイプ（ＩｎｆｏＣｏｕｒｓｅ）のデータ要素が対応づけられており、
前記第２のタイプ（ＩｎｆｏＴｙｐｅ）のデータ要素は第１のツリー構造内に配置されており、前記第３のタイプ（ＩｎｆｏＣｏｕｒｓｅ）のデータ要素は第２のツリー構造内に配置されていることを特徴とする、
コンピュータシステム内のデータを記憶するためのデータベース構造。
【請求項２】
ツリー構造の末端セクションはリンク要素を介して少なくとも個々のツリー構造の開始セクションとリンクされている、請求項１記載のデータ構造。
【請求項３】
前記第２のタイプ（ＩｎｆｏＴｙｐｅ）の同様のデータ要素の複数のオカレンスは、リンク要素を介して相互にリンクされたデータ要素の集合をもつ１つのセルフリング内に配置されており、該集合における１つのデータ要素はそのまま個々のツリー構造の一部分である、請求項１または２記載のデータ構造。
【請求項４】
１つのツリーのデータ要素には、個々のデータ要素のもとでツリー構造中に配置されたデータ要素数を表す数が設けられている、請求項１から３のいずれか１項記載のデータ構造。
【請求項５】
第１のタイプのデータ要素と第２のタイプのデータ要素との間のノードは第３のタイプ（ＩｎｆｏＣｅｌｌ）の要素により形成される、請求項１から４のいずれか１項記載のデータ構造。
【請求項６】
請求項１から５のいずれか１項記載のデータベース構造のためのデータ要素において、
第１のポインタペア（ＬＳＲ， ＲＳＲ）と第２のポインタペア（ＬＨＲ， ＲＨＲ）と第３のポインタペア（ＬＶＲ， ＲＶＲ）が設けられていることを特徴とするデータ要素。
【請求項７】
ＩＦポインタ（ＩＦ）が設けられている、請求項６記載のデータ要素。
【請求項８】
データベースクエリの最適化方法において、
１つのサーチ規準を複数のセクションに分解するステップと、
各セクションごとに目下のデータベース構造におけるヒット数を求めるステップと、
各セクションごとに求められたヒット数に従いデータベースクエリパスを選択するステップとを有することを特徴とする、
データベースクエリの最適化方法。
【発明の詳細な説明】
【０００１】
本発明は、データシステムなど情報記憶システムのためのデータ構造に関する。コンピュータをベースとするデータ記憶システムの場合、メモリやハードディスクドライブなど何らかの媒体にデータが記憶され、そこからデータが取り出される。公知のシステムの場合、データはたとえばリレーショナルモデルをベースとした構造をもつようなデータ構造に格納される。公知のデータ記憶システムを使用して格納されているデータは、記憶させて探索し取り出すことができるけれども、取り出しに要する時間がかなりかかる可能性があり、複合的なクエリの倍には殊に相当な時間がかかる可能性がある。さらに効率的なデータモデルを構成するのは手間がかかり、したがってコストが嵩む。データベースレイアウトまたはデータモデルが定義されてしまうと、あとから改変するのは実装が困難であり、それによってたいていはパフォーマンスの損失が引き起こされてしまう。
【０００２】
データベースに対するクエリにかかるレスポンスタイムをスピードアップするためにクエリオプティマイザが使用されることが多く、これはたとえばルールベースのオプティマイザであるかまたはコストベースのオプティマイザである。ルールベースのオプティマイザはまえもって定義されたルールセットを使用する。コストベースのオプティマイザはクエリを構成するデータに関する統計的な情報を使用し、これは各クエリコンポーネントのセレクティビティ（ｓｅｌｅｃｔｉｖｉｔｙ）を推定し、最もセレクティブなコンポーネントに沿ったサーチパスを最初に導くことによって行われる。公知のオプティマイザを使用すると平均レスポンスタイムを短くすることができるけれども、どのような特定のクエリでも最適化するオプティマイザに対するニーズが存在する。
【０００３】
本発明の１つの課題は、セットアップならびにメンテナンスの簡単なデータ記憶システムを提供することにある。本発明の別の課題は、データの高速な検索を可能にするデータ記憶システムを提供することにある。さらに本発明の別の課題は、クエリを決定論的に最適化できるデータ記憶システムを提供することにある。
【０００４】
これらの課題は、請求項１記載のデータベースシステムを提供することによって解決される。
【０００５】
請求項に記載されている構造を利用すればデータベースを簡単に構築することができる一方、変更が簡単に実施される。
【０００６】
さらに本発明によれば請求項６記載のクエリオプティマイザが提供される。１つのクエリセクション内で見つけられた目下のデータ要素の決定により、特定のクエリに対する目下のクエリパスの決定論的分析を行うことができる。したがって各クエリのための最良のパスを決定することができ、その結果、各クエリのためのクエリタイムが最適化される。
【０００７】
その他の特徴ならびに利点は、本発明の実施形態に関する以下の説明を通して明らかにさせるつもりである。従属請求項には有利な実施形態が示されている。
【０００８】
図面の簡単な説明
図１は、本発明によるシステムの階層構造を概略的に示す図である。
【０００９】
図２は、本発明によるデータ形式を示す図である。
【００１０】
図３は、アンカおよびインフォセルＩｎｆｏＣｅｌｌをもつインフォタイプＩｎｆｏＴｙｐｅ構造を示す図である。
【００１１】
図４は、本発明による２つのＩｎｆｏＣｅｌｌを示す図である。
【００１２】
図５は、バイナリツリーコンフィグレーションにおける３つのＩｎｆｏＴｙｐｅを備えたインフォクラスタＩｎｆｏＣｌｕｓｔｅｒを示す図である。
【００１３】
図６は、ＩｎｆｏＴｙｐｅ識別番号により記憶されたバイナリツリーとしてＩｎｆｏＣｏｕｒｓｅを示す図である。
【００１４】
図７は、４次元でリンクされたＩｎｆｏＣｅｌｌ要素のサブ構造を表された内容のテーブルとともに示す図である。
【００１５】
図８は、ダブルリンクセルフリングｄｏｕｂｌｅ ｌｉｎｋ Ｓｅｌｆ Ｒｉｎｇをリングの要素カウンタの番号とともに示す図である。
【００１６】
図９は、多次元構造の要素カウンタに対する番号を示す図である。
【００１７】
図１０は、テーブルを６次元構造として示す図である。
【００１８】
図１１は、インフォブリッジＩｎｆｏＢｒｉｄｇｅをカスケードした様子を示す図である。
【００１９】
図１２は、８つのフラグをもつインフォブリッジＩｎｆｏＢｒｉｄｇｅを示す図である。
【００２０】
図１３は、ツリー構造の一例を示す図である。
【００２１】
図１４は、図１３を簡単にした図である。
【００２２】
図１５は、第１の例を示す図である。
【００２３】
図１６は、第２の例を示す図である。
【００２４】
図１７は、第３の例を示す図である。
【００２５】
図１８は、図１７による例を示す図である。
【００２６】
図１９は、図１７による例を示す図である。
【００２７】
図２０は、図１７による例を示す図である。
【００２８】
図２１は、第４の例を示す図である。
【００２９】
図２２は、第５の例を示す図である。
【００３０】
図２３は、第６の例を示す図である。
【００３１】
詳細な説明
次に、本発明によるデータ記憶システムの実施形態の一例について説明する。本発明による実施形態の以下の説明はリレーショナルデータベースモデルに従いインプリメントされているが、本発明によるシステムは公知のリレーショナルデータベースアーキテクチャの枠内での利用に制限されるものではない。とはいうものの本発明は、主としてリレーショナルデータベースのルールに従ってインプリメントされる可能性がある。本発明の要素を公知のリレーショナルデータベース理論の用語に大雑把に当てはめると、以下のとおりとなる（本発明による定義を左側に示す）。
【００３２】
インフォシステム ＩｎｆｏＳｙｓｔｅｍ ← マネージメントシステム
インフォエリア ＩｎｆｏＡｒｅａ ← データベース
インフォクラスタ ＩｎｆｏＣｌｕｓｔｅｒ ← テーブル
インフォタイプ ＩｎｆｏＴｙｐｅ ← 属性
インフォコース ＩｎｆｏＣｏｕｒｓｅ ← データレコード
インフォセル ＩｎｆｏＣｅｌｌ ← フィールド
インフォブリッジ ← 利用不可能
なお、本発明によるインフォブリッジＩｎｆｏＢｒｉｄｇｅ（これについてはあとで説明する）に該当する用語は、リレーショナルデータベースフィールド中には存在しない。
【００３３】
図１には、本発明によるデータベースシステムのスタティックな階層が示されている。このデータベースシステムの最上位レベルはインフォシステムＩｎｆｏＳｙｓｔｅｍのレベルである。この最上位レベルにから下に降りると、１つまたは複数のインフォエリアがインフォシステムＩｎｆｏＳｙｓｔｅｍにリンクされている。ＩｎｆｏＳｙｓｔｅｍによりシステムに対し、そのオペレーティングに必要とされるアルゴリズムがランタイムに提供される。ＩｎｆｏＳｙｓｔｅｍはリンク要素を介して何らかの個数のＩｎｆｏＡｒｅａとリンクされており、このリンク要素を以下ではアンカａｎｃｈｏｒと称する。これらのＩｎｆｏＡｒｅａはたとえばＩｎｆｏＳｙｓｔｅｍの論理ユニットを参照することができる。
【００３４】
各ＩｎｆｏＡｒｅａはリンク要素（これも以下ではアンカと称する）を介してインフォクラスタＩｎｆｏＣｌｕｓｔｅｒとリンクされている。他方、各ＩｎｆｏＣｌｕｓｔｅｒはアンカのような個々のリンク要素を介して、少なくとも１つのインフォコースＩｎｆｏＣｏｕｒｓｅおよび少なくとも１つのインフォタイプＩｎｆｏＴｙｐｅとリンクされている。ＩｎｆｏＴｙｐｅをテーブルの属性とみなすことができる。ＩｎｆｏＣｏｕｒｓｅは常にＩｎｆｏＣｌｕｓｔｅｒにおいてスタートする。ＩｎｆｏＣｏｕｓｅｒが、アドレッシングされたそのインフォセルＩｎｆｏＣｅｌｌ要素（これはテーブルのフィールドに相応する）とともにＩｎｆｏＣｌｕｓｔｅｒ内でとどまっているならば、これはテーブルのレコードと同様である。
【００３５】
ＩｎｆｏＣｏｕｒｓｅとＩｎｆｏＴｙｐｅの下にはＩｎｆｏＣｅｌｌが示されている。これはこの階層構造において最下位レベルの要素である。ＩｎｆｏＴｙｐｅのインスタンスに生成に応じてアンカが生成され、これはＩｎｆｏＣｅｌｌタイプのインスタンスでもある。このアンカは後続のＩｎｆｏＣｅｌｌ要素の構造を表す機能をもっている（図２参照）。アンカはＩｎｆｏＣｅｌｌ情報キャリアとして７つのポインタを有しており、これについてはあとで説明する。
【００３６】
ＩｎｆｏＡｒｅａよりも下位のレベルすなわちＩｎｆｏＣｌｕｓｔｅｒ， ＩｎｆｏＣｏｕｒｓｅ， ＩｎｆｏＴｙｐｅ， ＩｎｆｏＣｅｌｌをインプリメントするために、図２に示されている本発明のデータ要素が用いられる。データ要素は概略的にアンカとして示されており、これには複数のポインタが設けられている。この例ではデータ要素は３つのポインタペアと１つの単独のポインタを有している。図２に示されている初期状態ではすべてのポインタはアンカを指している。この初期状態は考えられる得るリング構造のうち最も単純なものである。この構造中のすべてのポインタは有効なアドレスをもっており、未定義のポインタ（ヌルポインタ）が生じる状況が回避される。
【００３７】
第１のポインタペアには参照符号ＬＶＲとＲＶＲ（それぞれＬｅｆｔ Ｖｅｒｔｉｃａｌ Ｒｉｎｇ， Ｒｉｇｈｔ Ｖｅｒｔｉｃａｌ Ｒｉｎｇ）が付されており、第２のポインタペアには参照符号ＬＨＲ， ＲＨＲ（それぞれＬｅｆｔ Ｈｏｒｉｚｏｎｔａｌ Ｒｉｎｇ， Ｒｉｇｈｔ Ｈｏｒｉｚｏｎｔａｌ Ｒｉｎｇ）が、第３のポインタペアには参照符号ＬＳＲ， ＲＳＲ（それぞれＬｅｆｔ Ｓｅｌｆ Ｒｉｎｇ， Ｒｉｇｈｔ Ｓｅｌｆ Ｒｉｎｇ）が、さらに単独のポインタにはＩＦ（ＩｎＦｏｒｍａｔｉｏｎ ｂｒｉｄｇｅ）が付されている。ポインタＬＳＲ， ＲＳＲ， ＩＦは基本的にオプションである。
【００３８】
図７にはテーブルＡが示されており、このテーブルには名前と年齢と体重に関するデータが含まれている。このテーブルに対しＩｎｆｏＣｌｕｓｔｅｒが生成される。さらに３つのＩｎｆｏＴｙｐｅが生成され、これらはそれぞれ名前と年齢と体重を表す。
【００３９】
図３には、ＩｎｆｏＴｙｐｅのインプリメントのために使用されるデータ要素が示されている。Ｉｎｆｏｔｙｐｅのセマンティックな情報はデータ型（この例では”ＩＮＴＥＧＥＲ”）、指標（この例では「年齢」）等から成る。ＩｎｆｏＴｙｐｅはＩｎｆｏＴｙｐｅに対応づけられたアンカである。このアンカはそのＲＶＲポインタによって、目下の情報キャリアすなわちＩｎｆｏＣｅｌｌを指している。ＩｎｆｏＣｅｌｌは上述のようにデータシステム内で最下位レベルのエンティティである。ＩｎｆｏＣｅｌｌは図３に示されているような情報を保持しており、この例では「年齢」を３０としてＩＮＴＥＧＥＲ型で保持している。
【００４０】
ＩｎｆｏＣｅｌｌには上述のようにＬＶＲ／ＲＶＲポインタペアが設けられている。図３に示されているようにＩｎｆｏＣｅｌｌのＲＶＲポインタはアンカを指しており、ＬＶＲポインタもアンカを指している。したがってアンカのリングコンフィギュレーションが維持されている。
【００４１】
図４には、別のＩｎｆｏＣｅｌｌをデータ構造に加える様子が示されている。ここでは（値「２５」をもつ）ＩｎｆｏＣｅｌｌが最初のＩｎｆｏＣｅｌｌの後ろでＬＶＲリング中に挿入される。ＩｎｆｏＣｅｌｌのＬＶＲとＲＶＲポインタは、閉じたリングが維持されるようアンカを参照している。
【００４２】
ＩｎｆｏＣｅｌｌの編成順序はそれらの値に左右される。値が小さければそのＩｎｆｏＣｅｌｌはＬＶＲ側におかれ、さもなければＲＶＲ側におかれる。このやり方は従来技術においてバイナリツリーの構築として知られている。有利にはバイナリツリーは、周知のバランスツリーまたはＡＶＬツリーの手法として組織される。この種のツリーによりツリー構造内のレベル数が最小化され、アクセスタイムが最短になる。有利にはデータシステム内のすべてのツリー構造は使用中ダイナミックにバランスがとられ、それにより最適なアクセスタイムが保証される。
【００４３】
図５には、テーブルＡのすべてのＩｎｆｏＴｙｐｅがデータ構造に入れられた場合に得られる構造が示されている。全体として、年齢と名前と体重という３つのＩｎｆｏＴｙｐｅが存在している。なお、個々のツリーにおける最後の要素各々の最終ポインタは示されていない。ＩｎｆｏＴｙｐｅのアンカ各々の下にはＩｎｆｏＣｅｌｌがバイナリツリーとして組織されている。ＩｎｆｏＣｌｕｓｔｅｒはアンカを指しており、このアンカ自体は最初のＩｎｆｏＴｙｐｅを指している。さらにこのＩｎｆｏＴｙｐｅは他の２つのＩｎｆｏＴｙｐｅを指している。各ＩｎｆｏＴｙｐｅはアンカを指している。アンカはマーカの付加的な機能を有しており、これをブレークサインまたはリターンサインとしてアクセスやクエリのプロセスにより用いることができる。
【００４４】
テーブルのインプリメンテーションを完成させるためには、各ＩｎｆｏＴｙｐｅ間の関係を作成しなければならない。この目的でＩｎｆｏＣｏｕｒｓｅが導入される。図６にはＩｎｆｏＣｏｕｒｓｅが示されており、これにはテーブルにおける４番目の行に関するデータが含まれている。ここではＬＨＲポインタとＲＨＲポインタが用いられる。最終ポインタは再びＩｎｆｏＣｏｕｒｓｅのアンカに戻り、これによってリング構造が維持される。なお、ＩｎｆｏＣｏｕｒｓｅは、ＩｎｆｏＴｙｐｅのＩＤ番号によりソートされたバイナリツリーも形成する。ＩｎｆｏＴｙｐｅのＩＤ番号はユニークであり、整数値が用いられる。
【００４５】
図７には、テーブルＡに関してＩｎｆｏＣｏｕｒｓｅのパスがすべて示されている（たとえばポインタを使用してインプリメントされる）。この場合、すべてのＩｎｆｏＣｅｌｌはトップセクションにおかれ、これには個々のＩｎｆｏＴｙｐｅが設けられ、それによってＬＨＲ／ＲＨＲポインタを介したＩｎｆｏＣｏｕｒｓｅのバイナリツリーコンフィギュレーションが組織される。
【００４６】
１つのＩｎｆｏＴｙｐｅのためのツリー構築中、ＩｎｆｏＣｅｌｌのインスタンスが複数のオカレンス（ｏｃｃｕｒｒｅｎｃｅ）をもつときには以下のメカニズムが使用されて、ツリー構造中に同様のインスタンスが２つ以上出現するのが回避される。図９には、名前Ｂｏｂが３つのオカレンスをもち名前Ａｌｅｘが２つのオカレンスをもつ事例が示されている。ＬＳＲ／ＲＳＲのポインタペアを用いて後続の複数のエントリがリング状に加えられ、これはリングがデータ構造の要素レベル内にとどまることからここではセルフリングｓｅｌｆ ｒｉｎｇと呼ばれる。最後に加えられた要素はリングのマスタ要素となる。この場合、マスタ要素はツリー構造の一部分である。各要素の下方のセクションに示されているように、リング内における目下の全体要素数はマスタ要素内に格納される。他のもっと古い要素はヒストリックな値（すなわちもっと少ない値）をもつ。なぜならばこれらの値はリングの新しい要素の挿入によっても更新されないからである。このことは実際的見地からみて利点をもち、それによれば数字によってその要素がリング内で古い方なのか新しい方なのかが表される。このことが役立つのは、殊に実践においてリング中をナビゲートするときにいっそう新しいデータがいっそう頻繁にアクセスされるときである。ある要素がその周囲にセルフリングが形成されないことを表すリング値０をもつときは、図８も参照されたい。この情報はサーチクエリの高速化に利用できる。
【００４７】
他の特徴は、ＩｎｆｏＣｅｌｌ各々に属性として要素カウンタが与えられていることである。要素カウンタは図９中、要素の隣りに示されたボックス内で表されている。要素カウンタは、ポインタＬＶＲ／ＲＶＲおよびＬＳＲ／ＲＳＲを介して到達可能な要素の総数として定義されており、これはセルフリング内の要素数＋（もしあれば）個々の要素の下のツリー中の要素数である。セルフリング内の要素数はマスタ要素自体において既知であり、ツリー下方の要素は単純に、ＬＶＲポインタとＲＶＲポインタにより指示された要素の要素カウンタから得られる。基本的に、関連する要素の個数を求めるためにツリー全体を実際に通り抜ける必要がない。要素カウンタとセルフリングカウンタは最初にデータ構造のマウント中に求められ、要素が追加または削除されたときにも求められる。この種の要素カウンタは、その要素について可能性のあるサーチが行われるときにサーチされるべき潜在的な要素数あるいはそのようなサーチに必要とされるリソースを表している。基本的に片方向のポインタセルフリングだけを使用すれば十分であるけれども、双方向のポインタリングを使用すると付加的な利点が得られる。
【００４８】
図１０にはテーブルＢが６次元構造として示されている。すべてのカウンタおよび識別番号が各ノードごとに示されている。ここではアンカ要素やアンカに対応づけられたポインタ（たとえば閉ループ構造を成すポインタ）は示されていない。
【００４９】
ＩｎｆｏＴｙｐｅの構造はまえもって定義されたセットの機能をもつことができるので、いかなるＩｎｆｏＣｏｕｒｓｅにも含まれていないＩｎｆｏＴｙｐｅツリー中に要素が現れる可能性がある。１つのＩｎｆｏＴｙｐｅ中の１つの要素が２つ以上のＩｎｆｏＣｏｕｒｓｅにより必要とされているならば、各ＩｎｆｏＣｏｕｒｓｅごとに付加的なＩｎｆｏＴｙｐｅを生成して構造が有限にとどまるようにするのが有利である。本発明によるデータ要素のポインタＩＦを、どのようなオブジェクトタイプのインスタンス各々のためにも使うことができる。ポインタＩＦはどのようなタイプのインスタンスでも指すことができる。それが指し示すインスタンスのタイプはコンテキストまたは指標によって決定できる。これはたとえば（図１２に示されているような）フラグのリストであってもよいし、（理論から知られているような）各ノードごとの条件グラフであってもよい。ポインタはあまり多くのビットを要求しないのでいっそう効率的であるのに対し、条件グラフの利点はデータ構造向上のためのセマンティックな情報を含めることができる点にある。
【００５０】
ＩＦポインタを利用してどのようなインスタンスに対してもリンクを確立することができる。これはたとえばＩｎｆｏＢｒｉｄｇｅを介して行うことができる。本発明によるＩｎｆｏＢｒｉｄｇｅは、Ｙアダプタのように見えるリンク要素であり、これはカスケードすることができる（図１１）。オプションとしてＩｎｆｏＢｒｉｄｇｅを双方向にすることができ、それにより基本構造を介してどのようなネットワークでも表現することができる。
【００５１】
ポインタＩＦはさらに別の用途をもつ。データ構造内のオペレーションによって非常に多くのデータ要素に対し同時に変更が行われる。しかしミクロレベルでは、すべての変更はシーケンシャルに行われる。たとえばオペレーションはコミット作業またはロールバックによって実行される（これらのオペレーションはＳＡＰ Ｒ／３ ｓｙｓｔｅｍによって知られている）。つまりこの場合、トランザクションが完全に完了してしまうまでは（変更されていない）元の値と目的となる（変更された）値の双方が一時的に記憶装置内に保持されていなければならない。ＩｎｆｏＢｒｉｄｇｅは双方の値を互いに結びつけるために用いられる。図１２にはその例が示されている。上方のＩｎｆｏＢｒｉｄｇｅは２つのＩｎｆｏＣｅｌｌを相互にリンクしている。１つのＩｎｆｏＢｒｉｄｇｅを加えたときにすべての機能が維持され、図１２に破線で示されているようにカスケードにより増やすことができる。ここではＹコンフィギュレーションをもつ１つのコネクタだけしか示されていないが他のコンフィギュレーションを使用してもよく、たとえば３つよりも多くのコネクションをもつコンフィギュレーションを使用してもよい。
【００５２】
また、図示されている例によればＩｎｆｏＣｏｕｒｓｅはテーブルに表されているデータレコード定義に係わるものであるが、ＩｎｆｏＣｏｕｒｓｅの使用がこれに限定されるわけではない。ＩｎｆｏＣｏｕｒｓｅはたとえば、様々なＩｎｆｏＣｌｕｓｔｅｒそれどころかＩｎｆｏＡｒｅａにおける制約のないＩｎｆｏＴｙｐｅにわたって拡張することができる。このようにして参照一貫性を保証することもできる。たとえばテストテーブルの値をアプリケーションテーブルにコピーする必要がない（これは公知のデータベースにとっては一般的である）。その代わりに個々のＩｎｆｏＣｅｌｌに対し、テストテーブルとして使用されるＩｎｆｏＣｌｕｓｔｅｒのＩｎｆｏＣｅｌｌへのポインタが値として与えられることになる。
【００５３】
最短推定ランタイムをもつクエリルートを求めるためにクエリオプティマイザが使用される。
【００５４】
上述のシステムのインプリメンテーションは、公知のどのような適切な方式やプログラミング言語を使用しても行える。ここで有用であるのは、インプリメンテーションの言語がポインタをサポートすることである。プログラミング言語がオブジェクト指向であればさらに役に立つけれども、それは本質的なことではない。たいていのインプリメンテーションでは一時的な要素をもつ付加コントロール構造が必要とされるが、そのようなインプリメンテーションの詳細は知られており、当業者の能力範囲の及ぶところである。本発明の実験的なインプリメンテーションはＣ＋＋でプログラミングしたが、この言語はポインタおよびオブジェクトならびにオブジェクトクラスを使えるという付加的な利点をもっている。
【００５５】
本発明をたとえばランダムアクセスメモリ（ＲＡＭ）にインプリメントすることができ、そこではアドレスをランダムにアクセスできる。ランダムアクセスメモリの使用により得られる利点はさらに、データ構造に対する変更によってもどのようなかたちにせよ効率に作用が及ぼされないことでもある。本発明は有利にはランダムアクセスメモリにインプリメントされるけれども、インプリメンテーションがこの形態に限定されるわけではなく、記憶装置における別のインプリメンテーションも可能である。
【００５６】
例
以下の例では、ＩｎｆｏＣｅｌｌに対しどのようなアクセスが行われるかが示されている。例示のためだけに、１つのＩｎｆｏｔｙｐｅに属するＩｎｆｏＣｅｌｌｗが使用される。図１３には、もっと大きいデータセットのうちの一部分を成す構造が示されている。
【００５７】
この構造中のデータ要素をアクセスするためにリングポインタ構造が使用され、これにはリング（ＬＶＲ／ＲＶＲ）に戻るポインタとセルフリングとが含まれている。図１３ではポインタは小さいアンカシンボルによって表されている。図１４には、図１３の構造がその基礎を成すバイナリツリー構造の関係によって示されており、これは複数の同一の要素がないとした事例である。以下ではサーチクエリのいくつかの例について示すことにする。
【００５８】
例１：クエリ（ｋｅｙ ＝ ５４）
目的はキー５４をもつデータ要素を見つけることである。サーチはポジション１からスタートし（図１５に矢印１で示す）、そこは図１３に示されているアンカのすぐ後である。その後はバイナリツリーにおけるサーチと同様であり、ＩｎｆｏＣｅｌｌを順々に巡り、つまりツリーを下に降りていく。ここでは連続するＩｎｆｏＣｅｌｌが矢印１〜５で表されている。矢印５によって個々の要素が見つけられる。
【００５９】
ＩｎｆｏＣｅｌｌには他のＩｎｆｏＣｅｌｌと同様、ポインタペアＬＨＲ， ＲＨＲが設けられている。ＩｎｆｏＣｅｌｌに隣接するセマンティック情報からＩｎｆｏＣｏｕｒｓｅを得ることができる。ＩｎｆｏＣｏｕｒｓｅポインタもリングツリーとして組織されているので、ＩｎｆｏＣｏｕｒｓｅの開始アンカに必ず到達できる。この開始アンカからＩｎｆｏＣｏｕｒｓｅ構造内のすべての要素に到達できる。パフォーマンスをさらに高めるため、このＩｎｆｏＣｏｕｒｓｅアンカをダイレクトに指示する付加的なポインタを各ＩｎｆｏＣｅｌｌに加えることができる。このポインタを用いれば、このアンカに到達するためにＩｎｆｏＣｏｕｒｓｅツリーをくまなく通って降りていく必要がない。
【００６０】
ある値（たとえば図１５の矢印６のところに示す５３）を挿入する目的で、ポイント６に到達するために上述のものと同じ方法が用いられ、このポイント６のところに新たなＩｎｆｏＣｅｌｌが加えられる。ＩｎｆｏＣｅｌｌの付加後、必要であればバイナリツリーのバランスをとるためにソートしなおすことができる。このようなリソート手法は従来技術でよく知られている。
【００６１】
例２：クエリ（ｋｅｙ ＜ ２０）
この例ではクエリは、ツリーのうちハッチングされた部分集合をみつけるということであり（図１６）、その部分集合は条件キー＜２０を満たすものである。やはりサーチはポジション１から始められ、（前述のとおり公知の技術を使用して）ポジション３の末端までツリーが下に向かって辿られる。なお、ここではツリーの構造上、ツリーのこの末端より下のすべての要素は上述の条件を満たすものである。ツリーにおけるこのセクションの要素数は（ツリーの下位のセクションを通ってサーチする必要なく）既知である。それというのもＩｎｆｏＣｅｌｌ １０には要素カウンタ（ｘ１）指標が設けられているからであり、これによっていくつの要素がツリーのこのセクションに続くかが精確に伝えられる。
【００６２】
例３：クエリ（ｋｅｙ ＜ ２８）
この例（図１７）では、データベース構造のサーチのためどのようにしてヒット数を求めることができるかを示す。ツリーにおけるサーチはポジション１からスタートし、クエリ規準を満たすポジション２へ向かう。しかし要素カウンタｘ１をそのまま使うことはできない。それというのもそこには規準を満たさないセルも含まれているからである（つまり３０と３５）。パスはポジション２からポジション３へと続き（図１８）、このポジションで要素カウンタｙ１がみつけられる。このポジションからパスはさらにポジション４へと続き、そこにおいて要素カウンタｘ２がみつけられる（図１９）。ここでサーチは完了し、みつかった要素カウンタｘ１， ｙ１， ｘ２をそれぞれ加算および減算することにより、クエリキー（＜２８）に対する正確なヒット数を計算することができる。これによってセルのターゲットグループを表すハッチングエリア内のセル数が得られる。このようにかなり僅かな回数のステップでツリー構造を１つのパスを降りていきながら、クエリにより生じるヒット数が決定論的に求められ、これによりセルの精確な個数が得られる。
【００６３】
与えられたクエリに対するヒット数の情報をベースとして、サーチオプティマイザは実状に基づきサーチプランをたてることができる。
【００６４】
例４：クエリ（ｋｅｙ ＞ １０）
図２１には例３で行ったのと同じ論理分析が別の例に関して示されており、ここではクエリはキー＞１０である。ポジション１からサーチがスタートし、このポジションでただちにハッチングエリアとして示す第１の結果が生じる。ついでサーチはポジション２に進み、ここでは第２のハッチングエリアが求められる。その後、サーチはポジション３で終わる。ここでは右側のパス中のすべてのセルを（ポジション３自体のセル１０を除いて）考慮に入れる必要がある。クエリキーが＞＝であったならば、このセルも考慮されたはずである。前述の例と同じやり方でヒット数が計算され、つまり考慮すべきか否かに応じて要素カウンタを加算および減算することによって計算が行われる。
【００６５】
例５：クエリ（ｋｅｙ ｂｅｔｗｅｅｎ ２４ ａｎｄ ５４）
図２２に示されているクエリによれば、ヒット数を求めるためツリー構造を通り抜けて２つのサーチが必要とされる。ツリーは４０で始まるので、左右の分岐両方をサーチしなければならず、つまり詳しくいうと、２４という小さい方の値をもつ左側の分岐と、５４という大きい方の値をもつ右側の分岐の両方である。その結果、クエリの規準を満たすセルから成る円で囲まれた集合が識別される。択一的にクエリを２つの基本クエリ（ｋｅｙ ＞＝ ２４ ａｎｄ ｋｅｙ ＜＝ ５４）に分けてもよいが、結果は同じである。
【００６６】
例６：アクセスパスの最適化
この例ではいっそう複雑なサーチが示されており、さらにここではある特定のクエリに対するヒット数を求める上述の方法を利用した最適化方法も示す。
【００６７】
この例では、
ｋｅｙ＿１ ＜ ２８ ａｎｄ ｋｅｙ＿２ ＞＝ ｖａｌｕｅ＿２ ａｎｄ ｋｅｙ＿３ ＜ ｖａｌｕｅ＿３
という複合クエリ規準を使う。このような複合ステートメントを実行するため本発明によるオプティマイザは、クエリの各セクションにおいてどれだけ多くのヒットが得られるかを求める。このヒット数に基づきオプティマイザは、最小ヒット数のクエリセクションをまずはじめに処理するようにし、それよりも多いヒット数のクエリセクションはそのあとで処理しようとする。
【００６８】
クエリの各セクションごとのヒット数を求めるため、上述の例で示したようにセクションごとに１回ツリーをサーチする必要がある。
【００６９】
代案として、すでにみつけられたツリー中のノードの開始アドレスを記憶することができる。（要素カウンタのような）それらの開始アドレスのもつ情報に基づき、クエリのサブセクションのためにツリーの一部分をサーチする必要がない。なぜならばすでに記憶されている情報からそれを導き出せるからである。
【００７０】
クエリの最初のセクションは図１７に示されている例にマッチする。この例ではポジション２に到達すると、ガイド型のオブジェクトの一時的なインスタンスが生成され、これによりポジション２のアドレスが記憶される。さらに反復値Ｉｔが生成され（これは図２３と同様）、これはサブツリー内の目下の有効なセルの個数を記憶する。この値Ｉｔを、サブツリーを辿るアルゴリズムに対する最終基準としてあとで用いることができる。これはセルの値に対しサーチ規準を比較する役割を果たす。それというのもこのツリーセクション内のすべての有効なセルを辿った後、この最終基準に達するからである。Ｉｔは整数型であるので、ロングキャラクタチェーンとなるであろうセルの目下の値の比較よりも高速である。
【００７１】
図１９によればポジション４（２５）において明確であるのは、規準（ｋｅｙ＿１ ＜ ２８）がオプティマイザにより最初の規準としてあとで使われるのであれば、まだ辿らなければならないさらに別のツリーが存在することである。この目的でさらに別のガイドが導入され、これによりセル２５の開始アドレスと反復値Ｉｔが記憶され、この事例ではこの値はｘ２と同様である。
【００７２】
非常に大規模なツリー構造を用いて、有効なヒットを含む多くのサブツリーを１回辿る間に識別することができる。この種のサブツリーのトップ要素各々について、開始アドレスと要素のＩｔ値を含むガイドが生成される。すべてのガイドはリンクされた１つの線形リストを成しており、これが個々の規準に加えられる。
【００７３】
ＡＮＤチェーンのすべてのパートがそれらヒット数（Ｍ）についてサーチされ、オプティマイザが最小ヒット数の選択基準部分を選んだ後、オプティマイザは有効なセルをもつツリーをダイレクトにアクセスするためにガイドの線形リストを使うことができる。規準の他の部分に対する線形リストは廃棄されるが、それによっても処理時間が増すわけではない。
【００７４】
本発明のオプティマイザによれば、サーチ規準の個々の部分によって得られるヒット数の正確な決定に基づきサーチパスが求められる。このようにサーチパスを求めることで最も最適な選択が常に得られる。
【図面の簡単な説明】
【図１】
本発明によるシステムの階層構造を概略的に示す図である。
【図２】
本発明によるデータ形式を示す図である。
【図３】
アンカおよびインフォセルＩｎｆｏＣｅｌｌをもつインフォタイプＩｎｆｏＴｙｐｅ構造を示す図である。
【図４】
本発明による２つのＩｎｆｏＣｅｌｌを示す図である。
【図５】
バイナリツリーコンフィグレーションにおける３つのＩｎｆｏＴｙｐｅを備えたインフォクラスタＩｎｆｏＣｌｕｓｔｅｒを示す図である。
【図６】
ＩｎｆｏＴｙｐｅ識別番号により記憶されたバイナリツリーとしてＩｎｆｏＣｏｕｒｓｅを示す図である。
【図７】
４次元でリンクされたＩｎｆｏＣｅｌｌ要素のサブ構造を表された内容のテーブルとともに示す図である。
【図８】
ダブルリンクセルフリングｄｏｕｂｌｅ ｌｉｎｋ Ｓｅｌｆ Ｒｉｎｇをリングの要素カウンタの番号とともに示す図である。
【図９】
多次元構造の要素カウンタに対する番号を示す図である。
【図１０】
テーブルを６次元構造として示す図である。
【図１１】
インフォブリッジＩｎｆｏＢｒｉｄｇｅをカスケードした様子を示す図である。
【図１２】
８つのフラグをもつインフォブリッジＩｎｆｏＢｒｉｄｇｅを示す図である。
【図１３】
ツリー構造の一例を示す図である。
【図１４】
図１３を簡単にした図である。
【図１５】
第１の例を示す図である。
【図１６】
第２の例を示す図である。
【図１７】
第３の例を示す図である。
【図１８】
図１７による例を示す図である。
【図１９】
図１７による例を示す図である。
【図２０】
図１７による例を示す図である。
【図２１】
第４の例を示す図である。
【図２２】
第５の例を示す図である。
【図２３】
第６の例を示す図である。
【図１】
2004518225.tif 000003
【図３】
2004518225.tif 000004
【図４】
2004518225.tif 000005
【図５】
2004518225.tif 000006
【図６】
2004518225.tif 000007
【図７】
2004518225.tif 000008
【図９】
2004518225.tif 000009
【図１０】
2004518225.tif 000010
【図１１】
2004518225.tif 000011
【図１２】
2004518225.tif 000012
【国際公開パンフレット】
2004518225.tif 000013
2004518225.tif 000014
2004518225.tif 000015
2004518225.tif 000016
2004518225.tif 000017
2004518225.tif 000018
2004518225.tif 000019
2004518225.tif 000020
2004518225.tif 000021
2004518225.tif 000022
2004518225.tif 000023
2004518225.tif 000024
2004518225.tif 000025
2004518225.tif 000026
2004518225.tif 000027
2004518225.tif 000028
2004518225.tif 000029
2004518225.tif 000030
2004518225.tif 000031
2004518225.tif 000032
2004518225.tif 000033
2004518225.tif 000034
2004518225.tif 000035
2004518225.tif 000036
2004518225.tif 000037
2004518225.tif 000038
2004518225.tif 000039
2004518225.tif 000040
2004518225.tif 000041
2004518225.tif 000042
2004518225.tif 000043
2004518225.tif 000044
2004518225.tif 000045
2004518225.tif 000046
2004518225.tif 000047
2004518225.tif 000048
2004518225.tif 000049
2004518225.tif 000050
2004518225.tif 000051
2004518225.tif 000052
2004518225.tif 000053
2004518225.tif 000054
2004518225.tif 000055
【国際公開パンフレット（コレクトバージョン）】
2004518225.tif 000056
【国際調査報告】
2004518225.tif 000057
2004518225.tif 000058
2004518225.tif 000059