(57)【要約】【課題】  暗黙の述部を使用する改良されたクエリ・オプティマイザを提供すること。【解決手段】  このシステムを用いると、クエリ最適化コンポーネントは、以下のことを容易に可能にする追加の述部をクエリに円滑に導入できるようになる。すなわち、追加の述部を用いることによって、オリジナルのクエリと同じ結果を与えること、最適化コンポーネントに渡されるルール、すなわち新規述部が（旧述部に置き換わる）等価か、あるいは（旧述部が保存される）含意か、を指定するルールの指示に従って使用されること、コスト・ベースの代替述部であって有用でない場合には捨てられること、インデックスの使用に結びつくこと、および標準インデックスおよび多値インデックスの両方を考慮できること、などが容易に実施できるようになる。【選択図】  図１
2005267612.tif 000002
【特許請求の範囲】
【請求項１】
データ・リポジトリにおいてクエリの最適化を容易にするシステムであって、
前記データ・リポジトリのデータを対象に処理される、オリジナルの述部を含むクエリを受信するクエリ・コンポーネントと、
前記オリジナルの述部を処理して、暗黙の述部を含む１つまたは複数の新規述部に変換する述部コンポーネントと
を備え、前記データを対象に前記暗黙の述部を処理して、全体の評価コストが大幅に削減されるような最適解を返すことを特徴とするシステム。
【請求項２】
前記述部コンポーネントは、前記オリジナルの述部を処理して等価述部を得ることを特徴とする請求項１に記載のシステム。
【請求項３】
前記述部コンポーネントは、前記オリジナルの述部を処理して残余述部を得ることを特徴とする請求項１に記載のシステム。
【請求項４】
前記クエリは、以前に処理されアンマッチであったクエリであることを特徴とする請求項１に記載のシステム。
【請求項５】
前記１つまたは複数の新規述部は、標準インデックスおよび多値インデックスに使用される可能性があることを特徴とする請求項１に記載のシステム。
【請求項６】
前記１つまたは複数の新規述部は、前記評価コストが削減される場合にだけ使用され、そうでない場合には捨てられるコスト・ベースの代替述部だと見なされることを特徴とする請求項１に記載のシステム。
【請求項７】
前記１つまたは複数の新規述部は、インデックスの利用に関連付けられることを特徴とする請求項１に記載のシステム。
【請求項８】
前記クエリは、インデックス不可能型のデータ型を対象に処理されることを特徴とする請求項１に記載のシステム。
【請求項９】
請求項１に記載のシステムによることを特徴とするデータ・リポジトリ・オプティマイザ。
【請求項１０】
データ・リポジトリにおいてクエリの最適化を容易にするシステムであって、
前記データ・リポジトリのデータを対象に処理される、オリジナルの述部を含むクエリを受信するクエリ・コンポーネントと、
前記オリジナルの述部を処理して、暗黙の述部、等価述部、および残余述部のうちの少なくとも１つを含む新規述部に変換する述部コンポーネントと
を備え、前記データを対象に前記暗黙の述部または前記等価述部のいずれかを処理して全体の評価コストが大幅に削減されるような最適解を返すことを特徴とするシステム。
【請求項１１】
前記暗黙の述部および前記等価述部は、前記評価コストが削減されない場合には捨てられるコスト・ベースの代替述部だと見なされることを特徴とする請求項１０に記載のシステム。
【請求項１２】
請求項１０に記載のシステムを実施するためのコンピュータ実行可能な命令を格納していることを特徴とするコンピュータ可読の媒体。
【請求項１３】
請求項１０に記載のシステムを使用することを特徴とするサーバ。
【請求項１４】
前記述部コンポーネントは、前記１つまたは複数の新規述部を使用して式を生成し、前記式を使用して所与のカラムと所与のカラムの関数の少なくとも一方に関連付けられた含意ルールを得ることを特徴とする請求項１０に記載のシステム。
【請求項１５】
前記述部コンポーネントは、前記所与のカラムと前記所与のカラムの関数の少なくとも一方が比較される前記式、および利用できる標準インデックスのリストとの提供に応答して、前記含意ルールを要求することを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記１つまたは複数の新規述部は、インデックス選択の期間に解析されることを特徴とする請求項１０に記載のシステム。
【請求項１７】
前記クエリのコスト・ベース評価、基数見積り、および複雑さのうちの少なくとも１つに関連する１つまたは複数のパラメータに基づく推論を行うことによって、前記システムの１つまたは複数の機能の自動化を容易にするクラシファイアをさらに備えることを特徴とする請求項１０に記載のシステム。
【請求項１８】
前記全体の評価コストは、最適化が促進される場合にのみ前記１つまたは複数の新規述部を使用することを含むことを特徴とする請求項１０に記載のシステム。
【請求項１９】
前記クエリは、検索述部とインデックス・キーの間に正確なマッチがないクエリであることを特徴とする請求項１０に記載のシステム。
【請求項２０】
前記暗黙の述部は、インデックス・キーに正確にマッチすることを特徴とする請求項１０に記載のシステム。
【請求項２１】
検索クエリを最適化する方法を実施するためのコンピュータ実行可能な命令を有するコンピュータ可読の媒体であって、前記方法は、
オリジナルの述部がインデックス・キーに正確にマッチしないクエリを受信すること、
前記オリジナルの述部を、暗黙の述部と等価述部の少なくとも一方に還元すること、
データ・リポジトリのデータを対象に、前記暗黙の述部と前記等価述部の少なくとも一方を処理して検索結果を得ること、および
前記検索結果を解析して最適解を求めること
を備えることを特徴とする媒体。
【請求項２２】
カラムまたはカラムの関数に対する含意ルールを要求することをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２３】
カラムまたはカラムの関数が比較される式、および使用される可能性がある標準インデックスまたは多値インデックスのリストのうちの少なくとも一方を送信することをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２４】
前記暗黙の述部が前記標準インデックスと前記多値インデックスのどちらをも使用しない場合に、前記暗黙の述部を削除することをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２５】
前記オリジナルの述部の個々の演算子ごとに新規のアドホックな検索ルールを使用することをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２６】
前記検索ルールを用いて、前記暗黙の述部と前記等価述部の少なくとも一方を解析することをさらに備えることを特徴とする請求項２５に記載の方法。
【請求項２７】
ネストされたクエリを含む述部を有する暫定的な代用述部のリストを要求すること、
前記代用述部を前記クエリに含めて新規の式を形成すること、
前記新規の式を単純化すること、
ネストされたクエリを削除すること、および
前記検索のための新規の代替述部を生成すること
をさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２８】
前記オリジナルの述部を処理して残余述部を生成することによって前記検索を絞り込むことをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２９】
前記暗黙の述部と前記等価述部のうちの少なくとも一方を処理することを実行した後に、前記残余述部を処理することをさらに備えることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記オリジナルの述部に前記暗黙の述部を追加すること、および
前記最適解を探すこと
をさらに備えることを特徴とする請求項２１に記載の方法。
【請求項３１】
前記オリジナルの述部を前記等価述部で置き換えること、および
前記最適解を探すこと
をさらに備えることを特徴とする請求項２１に記載の方法。
【請求項３２】
前記暗黙の述部と前記等価述部のうちの少なくとも一方を使用して基数見積りを実施することをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項３３】
インデックス拡張スキームに基づいてインデックスを生成することをさらに備え、前記スキームは、
インデックスが付けられているデータ型に対応するデータ型のキー・カラムを提供すること、
１組のパラメータを提供すること、および
前記インデックスが付けられているカラムの値のインデックス・エントリを生成するために使用されるテーブル値関数名を提供すること
のうちの少なくとも１つを含むことを特徴とする請求項２１に記載の方法。
【請求項３４】
データ・リポジトリにおいてクエリの最適化を容易にするシステムであって、
オリジナルの述部がインデックス・キーに正確にマッチしないクエリを受信する手段と、
前記オリジナルの述部を、暗黙の述部と等価述部のうちの少なくとも一方に還元する手段と、
カラムまたはカラムの関数に対する含意ルールを要求する手段と、
カラムまたカラムの関数が比較される式と、使用される可能性がある標準インデックスまたは多値インデックスのリストとの少なくとも一方を送信する手段と、
データ・リポジトリのデータを対象に前記暗黙の述部と前記等価述部のうちの少なくとも一方を処理して検索結果を得る手段と、
前記検索結果を解析して最適解を求める手段と、
前記暗黙の述部が前記標準インデックスと前記多値インデックスのどちらをも使用しない場合に、前記暗黙の述部を削除する手段と
を備えることを特徴とするシステム。
【請求項３５】
前記オリジナルの述部の個々の演算子ごとに新規のアドホックな検索ルールを使用する手段をさらに備えることを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記検索ルールを用いて、前記暗黙の述部と前記等価述部のうちの少なくとも一方を解析する手段をさらに備えることを特徴とする請求項３４に記載のシステム。
【請求項３７】
ネストされたクエリを含む述部を有する暫定的な代用述部のリストを要求する手段と、
クエリに前記代入述部を含めて新規の式を形成する手段と、
前記新規の式を単純化する手段と、
ネストされたクエリを削除する手段と、
前記検索のための新規の代替述部を生成する手段と
のうちの少なくとも１つをさらに備えることを特徴とする請求項３４に記載のシステム。
【請求項３８】
前記オリジナルの述部を処理して残余述部を生成することによって、前記検索を絞り込む手段をさらに備えることを特徴とする請求項３４に記載のシステム。
【請求項３９】
前記暗黙の述部と前記等価述部のうちの少なくとも一方を処理した後で、前記残余述部を処理する手段をさらに備えることを特徴とする請求項３８に記載のシステム。
【請求項４０】
前記暗黙の述部と前記等価述部のうちの少なくとも一方を使用して基数を見積もる手段をさらに備え、前記暗黙の述部を使用した場合に、前記オリジナルの述部を満足させることができる行の数の上限が容易に定義されることを特徴とする請求項３４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータベース・システムに関し、より詳細にはデータベース・システムのクエリ最適化に関する。
【背景技術】
【０００２】
データベース・システムのクエリは高水準の宣言型（非手続き型）言語の形で示され、その言語は手続き型の実行計画に翻訳する必要がある。クエリ最適化の目的は、この宣言型の要求を手続き型の計画に翻訳できる方法を探索し、探索した方法の中から最も有効な計画を選択することである。所望のクエリ実行計画は、一連の基本的なデータベース演算子（primitive database operators）から構成することができ、通常は、見積もられた実行コストが最少となるものが選択される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来のクエリ最適化システムの欠点の１つは、制限されたサイズのカラム（column）の値の比較を含むことである。データベースのインデックスには、インデックスへの検索キーとして使用されるフィールドのサイズに実用上の制限がある。この制限は、あるインデックスの検索キーとして使用される可能性があるカラムについての制限を示すものである。一つの実装形態では、各インデックスは長さが９００バイトを超えるキーを持つことができない。例えば、ＶＡＲＣＨＡＲ（Ｘ）型のカラムには、Ｘ＞９００に対しては、インデックスを付けることができない。このようなデータ型をｎｏｎ−ｉｎｄｅｘａｂｌｅ（インデックス不可能）型と呼ぶ。もう１つの欠点は、最適化処理についての計算処理上の複雑さと選択された計画の実行効率に関するものである。さらに、これらの障害に加えて、インデックス選択の標準的なアプローチでは、（例えば、あるカラムの関数を他の値と比較することと対照的に）当該のカラムを他の値と比較する述部だけを考慮することによっても制限される。
【０００４】
クエリ述部に暗黙に含まれる式によってインデックスを活用する改良されたクエリ最適化機構が必要とされている。
【課題を解決するための手段】
【０００５】
本発明のいくつかの態様についての基本的な理解が得られるように、以下に本発明の簡単な要約を示す。この要約は、本発明を幅広く概観するものではない。また、本発明のキー／クリティカル要素を識別すること、あるいは本発明の範囲を示すこと、を意図したものでもない。後で示されるより詳細な説明の序として、本発明のいくつかの概念を簡単な形で示すことだけを目的としたものである。
【０００６】
本明細書で開示し、特許請求の範囲に記載した本発明は、その一側面においては、クエリ最適化コンポーネントが、他の述部条件からインデックスの付けられたカラムに関する単純な比較を容易に推論できるようにするシステムである。このことは、クエリに追加の述部を導入し、その追加の述部により少なくとも以下のことを容易にすることによって実施される。すなわち追加の述部は、オリジナルのクエリと同じ結果を提供し、最適化コンポーネントに渡されるルールの指示に従って使用される。このルールは、新規述部が（旧述部に置き換わることになる）等価（equivalence）の述部であるのか、あるいは（旧述部が保存される）含意（implication）の述部であるのかを指定する。追加の述部はさらにコスト・ベースの代替述部であると見なされ、有用でない場合には捨てられる。この述部はインデックスの使用と結び付けることも可能で、標準のインデックス（standard indices）と多値インデックス（multi-valued indices）の両方を考慮することができる。
【０００７】
これらのサポートにおいて、本発明はデータ・リポジトリにおけるクエリ最適化を容易にするシステムを備える。このシステムは、データ・リポジトリのデータを対象に処理されるクエリを受信するクエリ・コンポーネントを備え、クエリにはオリジナルの述部が含まれる。このシステムは、また、オリジナルの述部を１つまたは複数の新規述部に変換する述部コンポーネントを含み、新規述部は、暗黙の述部（implied predicate）、等価述部（equivalent predicate）、および残余述部（residual predicate）のうちの少なくとも１つを含み、全体の評価コスト（evaluation cost）が大幅に削減されるような最適解を返すように、そのデータを対象に暗黙の述部または等価述部のいずれかが処理される。
【０００８】
本発明の他の態様においては、このシステムはクラシファイア（classifier）の形で人工知能を使用して本発明の１つまたは複数の態様を自動化する。
【０００９】
本発明の他の態様においては、単純な比較に基づく基数見積り（estimating cardinality）を提供して精度を向上させる。この処理は、複雑な条件または述部に基づいてこのような見積り（estimations）を実施するよりも、コスト効率が高い。
【００１０】
前記および関連する目的を達成するために、本明細書では本発明のいくつかの例示的な態様を、以下の記述および添付の図面と併せて説明する。しかし、これらの態様は、本発明の原理が使用される可能性がある様々な方法のうちの数例を示したものに過ぎず、本発明には、これらの態様およびその均等物のすべてが含まれることが意図される。本発明の他の利点および新規な特徴は、以下の本発明の詳細な説明を添付の図面と併せて読むことによって明らかになるはずである。
【発明を実施するための最良の形態】
【００１１】
ここで、図面を参照しながら本発明を説明する。全図面を通して、同一要素の参照には同一参照番号を使用する。以下の説明では、説明の目的で多くの個別の詳細について記載しているが、これは本発明を十分に理解できるように示したものである。しかし、本発明がこのような個別の詳細を必要とせずに実施し得ることは明らかであろう。他の例では、本発明の説明を容易にするために、周知の構造および装置をブロック図の形で示している。
【００１２】
本出願で使用する「コンポーネント」および「システム」という用語は、コンピュータに関連するエンティティを意味するものであり、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、あるいは実行中のソフトウェアのいずれかである。例えばコンポーネントは、これに限るものではないが、プロセッサ上で動作するプロセス、プロセッサ、オブジェクト、実行可能な命令、実行のスレッド、プログラム、および／またはコンピュータなどであってよい。例として、サーバ上で動作するアプリケーションおよびサーバはどちらもコンポーネントになり得る。１つまたは複数のコンポーネントをある実行のプロセスおよび／またはスレッド内部に常駐させることができる。また、１つのコンポーネントを１台のコンピュータ上に配置すること、および／または２台以上のコンピュータ間に分散することもできる。
【００１３】
本明細書で使用する「推論する（infer）」または「推論（inference）」という用語は一般に、イベントおよび／またはデータによって得られた１組の観察結果から、システム、環境、および／またはユーザの状態を推定すること、または推察することを意味する。推論を使用して、例えば、特定のコンテクストまたは動作を識別することができるし、また各状態に関する確率分布を生成することもできる。この推論は確率的であってもよい。すなわち、データとイベントの考慮に基づいた、対象とする各状態に関する確率分布の計算値であっても良い。推論はまた、１組のイベントおよび／またはデータからより高水準のイベントを構成するために使用される技術を意味することもある。この推論は、そのイベントが時間的に極めて密接に相関しているか否か、あるいはそのイベントおよびデータが１つまたは複数のイベントおよびデータのソースから生じたものかどうかにかかわらず、１組の観察されたイベントおよび／または格納されたイベント・データの組から、新規のイベントの構成または動作（action）をもたらす。
【００１４】
次に図１を参照すると、本発明によるシステム１００が示されている。データ・リポジトリ１０４を対象とする検索を最適化するための最適化コンポーネント１０２が提供される。この最適化コンポーネント１０２は、本発明による拡張機能を備えた、データ・リポジトリ１０４に関連するクエリ・オプティマイザ（query optimizer）であってもよい。本発明は、オプティマイザと呼ばれる、ＤＢＭＳ（データベース管理システム）コンパイラの一部を用いて実施できる。オプティマイザは、ＤＢＭＳコンパイラのプロセス・コンポーネントであり、先ず検索クエリを評価し、ＤＢＭＳ実行プログラム（DBMS Executor）のためのキーとなる式（key expressions）を生成する。最適化コンポーネント１０２は、データ・リポジトリ１０４のデータを対象に処理されるクエリ１０６を受信する。以下の説明では、検索用語がそのままではリポジトリのテーブル・データと一致しないという理由で、そのデータ・リポジトリを対象として直接の処理ができないクエリを取り扱う。したがって、検索結果を得るためには、他の処理が必要になる。
【００１５】
この処理をサポートするために、最適化コンポーネント１０２は、クエリ１０６を受信するためのクエリ・コンポーネント１０８をさらに含む。クエリ・コンポーネント１０８はクエリ１０６から１つまたは複数のクエリ述部を抽出し、その１つまたは複数の述部を述部コンポーネント１１０に送る。この説明では、述部は各値に関する事実（fact）を主張する式（expression）とする。式が真（ＴＲＵＥ）だと評価された場合は、関連する条件が満たされる。式が偽（ＦＡＬＳＥ）だと評価された場合は、その条件は満たされない。ここで、最初にこの述部がデータに対して適用され、何の結果も得られなかったものとする。本発明によれば、述部コンポーネント１１０はマッチしない述部を解析し、検索が成功する見込みを大幅に増大させる１つまたは複数の新規の述部１１２を導入する。この１つまたは複数の新規の述部１１２には、暗黙の述部１１４、等価述部１１６、および残余述部１１８のうちの１つ、またはそれらの任意の組合せを含めることができる。
【００１６】
本発明は、最適化コンポーネント１０２が、クエリに１つまたは複数の追加の（または新規の）述部１１２を導入することを可能にする。この述部１１２は以下のこと、すなわちオリジナルのクエリと同じ結果を提供すること、最適化コンポーネント１０２に送られるルール、すなわち新規述部が（旧述部に置き換わることになる）等価な述部なのか、（旧述部が保存される）含意の述部なのかを指定するルールの指示に従って使用される可能性があること、コスト・ベースの代替案と見なされて、有用でない場合には捨てられること、インデックス使用と結び付けられること、および標準インデックスと多値インデックスの両方を考慮すること、などを容易にする。コスト・ベース・オプティマイザ１２０を最適化コンポーネントの一部に含めることによって、この１つまたは複数の新規の述部１１２が検索を成功させることに付随するコストを削減するかどうかが容易に判断される。
【００１７】
インデックスの使用可能性に関する従来の制限は、クエリの性能を低下させる恐れがある。まだいくつかの欠点はあるが、この問題を解決する１つの次善策は以下のとおりである。例えば、Τ１．ｃ＿ｃｈａｒｍａｘおよびＴ２．ｃ＿ｃｈａｒｍａｘと呼ばれるＶＡＲＣＨＡＲ（ＭＡＸ）型の２つのカラムが、それぞれ、テーブルＴ１およびテーブルＴ２に存在するとする。どちらのカラムもｉｎｄｅｘａｂｌｅではないが、ＨＡＳＨ（Τ１．ｃ＿ｃｈａｒｍａｘ）によって計算されたカラムΤ１．ｃ＿ｃｃｏｌｕｍｎにはインデックスが存在する。Τ１．ｃ＿ｃｈａｒｍａｘ＝Ｔ２．ｃ＿ｃｈａｒｍａｘは、ＨＡＳＨ（Τ１．ｃ＿ｃｈａｒｍａｘ）＝ＨＡＳＨ（Ｔ２．ｃ＿ｃｈａｒｍａｘ）を意味し、したがってΤ１．ｃ＿ｃｃｏｌｕｍｎ＝ＨＡＳＨ（Ｔ２．ｃ＿ｃｈａｒｍａｘ）となるので、この後者の述部をクエリ中に明示的に含めることができる。この明示的に書き直されたクエリの結果が下記の２つのクエリであり、それぞれ同一の結果を生ずるという意味で等価である。
【００１８】
【数１】
2005267612.tif 000003
【００１９】
このアプローチは、あるカラムがｎｏｎ−ｉｎｄｅｘａｂｌｅ型であるときに、型がｉｎｄｅｘａｂｌｅ型であるカラムのある種の関数（例えば、ＨＡＳＨ、プレフィックスなど）に基づいてインデックスを定義できる可能性があることを示す。このようなインデックスが定義されると、Τ１．ｃ＿ｃｃｏｌｕｍｎでインデックスの使用が可能になる。しかし、このアプローチにはいくつかの欠点がある。物理的考慮に基づき、プログラマに追加の述部を書かせることは、クエリ言語の「非手続き性」に反することになる。また、Τ１．ｃ＿ｃｃｏｌｕｍｎのインデックスを含む計画は最適でないかもしれず、Τ１．ｃ＿ｃｃｏｌｕｍｎのインデックスがプログラマに知られずに削除される（drop：撤回される）可能性もある。また、この述部を書き換える他の方法が存在するかもしれない。このいずれの場合においても、クエリの実行には、追加の不必要な用語（extra and unnecessary term）についての評価が課せられることになる。
【００２０】
次に、図２を参照すると、本発明の一プロセスのフローチャートが示されている。説明を簡潔にするために、本明細書に示された１つまたは複数の方法が、例えば１本のフローチャートの形で一連の動作として示され説明されているが、本発明によれば、いくつかの動作は本明細書に示し、説明した順序とは異なる順序で、かつ／または他の動作と同時に実施できるので、本発明が動作の順序によって制限されるものではないことを理解し認識されたい。例えば、当業者なら、別法として本方法を状態線図などの形で、一連の相互に関連する状態およびイベントとして表すことができることを理解し認識されよう。さらに、本発明による方法を実装するためには、必ずしも例示したすべての動作が必要になるわけではない。
【００２１】
ステップ２００で、そのままでは検索できないアンマッチのクエリが受け取られる。２０２で最適化コンポーネントは、クエリ述部を、各結合要素（conjunct）に還元（reduce）する、ここで各結合要素の中の１つは、既存のルールで、潜在的に使用される可能性があるものである。ステップ２０４で、最適化コンポーネントは、その結合要素を既存のルールで解析し、最も適合するルール（most compatible rule）を選択する。ステップ２０６で、最適化コンポーネントは、最も適合するルールにマッチする暗黙の述部または等価述部を返す。ステップ２０８で、そのクエリが暗黙の述部または等価述部に基づいて処理される。ステップ２１０で検索結果が処理され、その結果が受け入れ可能かどうかを決定する。Ｎｏの場合、フローは２１２に移行し、そのクエリを削除する。次いでプロセスは停止ブロックに移る。
【００２２】
最初の結果が受け入れ可能である場合は、フローはステップ２１０からステップ２１４に移行し、検索をさらに絞り込む必要があるかどうかを判断する。Ｎｏの場合は、フローはステップ２１６に移行して結果が受け入れ可能かどうかを決定する。Ｎｏの場合は、２１２でクエリを削除する。Ｙｅｓの場合は、停止ブロックで処理を終了する。他方、さらに絞込みが必要な場合は、フローはステップ２１４からステップ２１８に移行し、そこで残余述部が導入され、返された結果に基づいて暗黙の述部または等価述部が処理される。ステップ２１６で、前と同様に結果の受け入れ可能性がチェックされる。
【００２３】
次に図３を参照すると、本発明によるシステム３００が示されている。システムの動作を、標準インデックスのための含意ルールに従って説明する。この場合、最適化コンポーネント１０２はさらに、メタデータ・エンジン３０２と対話し、メタデータ・エンジンは、１組のルールを有するルール・コンポーネント３０４に関連付けられる。最適化コンポーネント１０２は、クエリ述部を取り出し、それを複数の結合要素に分解する。比較のための個々の結合要素のセットは、インデックス選択の期間に解析される。最適コンポーネント１０２は、所与のカラムまたは所与のカラムの関数に対する含意ルールについて存在するものを、メタデータ・エンジン３０２に要求する。この情報が提供できるように、最適化コンポーネント１０２はエンジン３０２に、カラム（またはカラムの関数）が比較される式、および使用される可能性のある標準インデックスのリストを送る。メタデータ・エンジン３０２はルール・コンポーネント３０４にアクセスし、暫定的な代用述部（または、暗黙の比較述部）のリストで応答する。最適化コンポーネント１０２は、オリジナルの述部に、順に、暗黙の述部の付加を試み、最適なインデックスのソリューションを探す。所与の暗黙の述部がインデックスを使用する場合には、結果が戻されさらに処理される。しかし、その暗黙の述部がインデックスを使用しない場合には、最適化コンポーネント１０２は、追加のオーバヘッドが生じないように、その暗黙の述部を削除する。
【００２４】
次に図４を参照すると、本発明による、標準のインデックスを処理する方法の流れ図が示されている。ステップ４００で本発明の最適化コンポーネントが使用される。ステップ４０２で、クエリのオリジナルの述部が各結合要素に還元される。ステップ４０４で、この各結合要素がインデックス選択の期間に解析される。ステップ４０６で、所与のカラムまたは所与のカラムの関数に対する含意ルールをメタデータ・エンジンに要求する。ステップ４０８で、エンジンから応答が受け取れるように、先ずカラム（またはカラムの関数）を比較される式がエンジンに送信される。さらにステップ４１０で、使用される可能性のある標準インデックスのリストがエンジンに送信される。ステップ４１２で、エンジンは暫定的な述部代用物（または、暗黙の比較述部）のリストを返す。ステップ４１４で、最適化コンポーネントはオリジナルの述部に暗黙の述部の追加を試みる。ステップ４１６で、最適コンポーネントは最適な検索ソリューションを探す。ステップ４１８で、最適化コンポーネントは、所与の暗黙の述部がインデックスを使用するかどうかをチェックする。ステップ４２０で、システムは、インデックスが使用される可能性があるかどうかを判断する。Ｙｅｓの場合は、４２４でその述部が使用され、フローは停止ブロックへ移る。しかし、インデックスを使用される可能性がないときには、フローは４２２に移行し、この場合には最適コンポーネントは、追加のオーバヘッドを引き起こさないように暗黙の述部を削除する。次いで、プロセスは停止ブロックに移る。
【００２５】
次に図５を参照すると、本発明による、書き換えルールによって生成された暗黙の述部を有するクエリの初期の演算子（operator）ツリー５００と最終の演算子ツリー５０２が示されている。この例では、ルール１と呼ばれる、標準インデックスに対する含意ルールが存在し、そこには、ｉｆ  ｐ１＝＠ｐ  ｔｈｅｎ  Ｐｒｅｆｉｘ（ｐ１，ｎ）＝Ｐｒｅｆｉｘ（＠ｐ，ｎ）と記載されているものとする。また、以下のように生成されるテーブルがあるとする。
【００２６】
【数２】
2005267612.tif 000004
【００２７】
ここで、次のクエリを考える。
【００２８】
【数３】
2005267612.tif 000005
【００２９】
このクエリが初期の演算子ツリー５００に示されている。この場合、Ｐｒｏｊｅｃｔ（ＩＤ）はＳｅｌｅｃｔノードに分岐し、このノードはＴａｂｌｅ１ノードとＥＱノードに分岐する。ＥＱノードはさらにＰ１と＠Ｐ２ノードに分岐する。
【００３０】
述部、ｐ１＝＠ｐ２に対する含意ルールの生成は、３ステップで行われる。第１ステップで、結合要素を探して、上記の結合要素がＴａｂｌｅ１のｎｏｎ−ｉｎｄｅｘａｂｌｅなカラムと比較されるのか、またはＴａｂｌｅ１のカラムの関数もしくはメソッドと比較されるのかを決定する。当該カラム（ｐ１）を候補カラムと呼ぶ。第２ステップで、インデックスが付いたカラムを探す。候補カラムを使用する、インデックスの付いた計算されたカラムのリストを構築する。候補カラムがｉｎｄｅｘａｂｌｅである場合には、そのインデックスも含める。この例では、どちらもｐ１を使用しているので、カラムＰｒｆｘＣｏｍｐＣｏｌおよびＡｎｏｔｈｅｒＣｏｍｐＣｏｌにインデックスが存在することになる。対応する式は、ＰｒｅｆｉＸ（ｐ１，１０）およびＡｎｏｔｈｅｒＦｕｎｃｔ（ｐ１）である。第３のステップは、代用（substitution）の検索である。以下のパラメータを使用して、アドホック・メタデータ関数を用いることによって可能性のある暗黙の述部を入手する。
【００３１】
【表１】
2005267612.tif 000006
【００３２】
メタデータ関数は、暗黙の述部についての０個を含むそれ以上の式を返す。この例では、１つの式ＰｒｆｘＣｏｍｐＣｏｌ＝Ｐｒｅｆｉｘ（＠ｐ２，１０）である。この式が、ルール１の「ｔｈｅｎ」部分の式と同一になることに留意されたい。
【００３３】
【数４】
2005267612.tif 000007
【００３４】
ただし違いは、Ｐｒｅｆｉｘ（ｐ１，ｎ）が等価なカラムＰｒｆｘＣｏｍｐＣｏｌに変更されたこと、およびルールの右辺の項に、計算されたカラムの式からｐｒｅｆｉｘの長さ（ｎ＝１０）を使用していることである。
【００３５】
この結果が、最終演算子ツリー５０２に示されている。この場合、暗黙の述部は、ＡＮＤノード、右側のＥＱノード、および子ノードであるＰｒｆｘＣｏｍｐＣｏｌとＰｒｅｆｉｘ（＠ｐ２，１０）を含む。ＰｒｆｘＣｏｍｐＣｏｌ（ｐ１，１０）が、インデックスの付いた計算されたカラムに対応し、対応する計算されたカラム（ＰｒｆｘＣｏｍＣｏｌ）に置き換えられていることに留意されたい。また、Ｐｒｅｆｉｘ（＠ｐ２，１０）が、ＰｒｆｘＣｏｍＣｏｌの式からｐｒｅｆｉｘの長さ（すなわち、１０）を使用していることにも留意されたい。
【００３６】
次に図６を参照すると、システム６００のブロック図が示されている。このシステムは、本発明による多値インデックスを処理するものである。この場合、最適化コンポーネント１０２はルール・コンポーネント６０２を含む。このコンポーネントは、個々の演算子（例えば、Ｓｅｌｅｃｔ、Ｊｏｉｎなど）に対する新規の、アドホックな、検索ルールの導入を容易にする。このアドホックなルールの内部では個々の結合要素が解析される。最適化コンポーネント１０２は、メタエンジン３０２にルールを要求し、エンジン３０２に上記とほぼ同一の情報を送る。すなわち、最適化コンポーネント１０２は、エンジン３０２に、カラム（またはカラムの関数）と比較される式と、使用される多値インデックスのリストとを送る。メタデータ・エンジン３０２は、（ネストされたクエリを含む述部を有する）暫定的な代入述部のリストを返す。最後に、最適化コンポーネント１０２は、クエリにその代入述部を含め、新規の式を単純化しネストされたクエリを削除した後で、Ｓｅｌｅｃｔ（または、Ｊｏｉｎなど）への新規の代替述部を生成する。
【００３７】
次に図７を参照すると、本発明による、多値インデックスを処理する方法の流れ図が示されている。ステップ７００で、本発明の最適化コンポーネントが使用される。７０２で、オリジナルのクエリの述部が結合要素に還元される。ステップ７０４で、結合要素がインデックス選択の期間に解析される。ステップ７０６で、最適化コンポーネントは個々の演算子のためのアドホックな検索ルールを提供する。ステップ７０８で、個々の結合要素がアドホックなルールで解析される。ステップ７１０で、最適コンポーネントはまた、メタデータ・エンジンにルールについて存在するものを要求する。また、エンジンから応答を受け取れるように、先ずカラム（またはカラムの関数）と比較される式をエンジンに送る。さらにステップ７１２で、使用される可能性がある多値インデックスのリストをエンジンに送る。ステップ７１４で、エンジンは（ネストされたクエリを含む述部を有する）暫定的な述部代用物を返す。ステップ７１６で、最適化コンポーネントはクエリに代用述部を含め、式を単純化する。ステップ７１８で、最適化コンポーネントはネストされたクエリを削除する。７２０で、最適化コンポーネントは新規の代替述部を生成する。次いでプロセスは停止ブロックに移る。
【００３８】
空間データ型などの複雑なデータ型を処理するアプリケーションは、しばしば、通常のインデックスに合わない特殊なインデックス要件を有する。本発明は、インデックスに関するいくつかの性質や仮定（aspects and assumptions）を緩和することによって、ユーザがサーバのＢ−Ｔｒｅｅインデックス（例えば、ＳＱＬサーバに関連付けられたインデックス）の上にインデックスを構築できるようにし、またユーザが拡張されたインデックスを生成できるようにもする。本発明は、述部または演算子を、拡張インデックスを使用する式にマップする方法も提供する。
【００３９】
拡張インデックスに関して、空間データベース、フル−テキスト・データベース、または一時的データベースなどのアプリケーションによりアドホックなインデックスのニーズが生じる。このニーズは、Ｂ−ｔｒｅｅでは容易に満たすことができず、標準インデックスをその上に順に構築できるいくつかの中間構造の生成を必要とする。標準インデックスは、各テーブル行あたり多くても１つのエントリしか有していない。上記のアプリケーションは、各行あたり、２つ以上のインデックス・エントリ、すなわちTａｂｌｅ−Ｖａｌｕｅｄ  ＵＤＦによって生成されている複数エントリを必要とする。例えば、フル・テキスト用に設計された拡張インデックスは、Tａｂｌｅ−Ｖａｌｕｅｄ  ＵＤＦを使用することが可能であり、テキスト・フィールドに適用されたときには、Tａｂｌｅ−Ｖａｌｕｅｄ  ＵＤＦは、エントリがテキスト中の各語に対応しているテーブルを戻す。拡張クエリの定義付けは、それが生成されるカラムの記述に加えて、その生成を使用するTａｂｌｅ−Ｖａｌｕｅｄ  ＵＤＦの識別を必要とし、またときには、Ｔａｂ  ＵＤＦに含まれる１組のアプリケーション依存パラメータの仕様を必要とする。簡略にいうと、拡張インデックスは、テーブル値が計算されたカラムのインデックスと等価である。
【００４０】
クエリ書き換えルールに関し、これらのルールは、（１）ある種のデータ型または特定のＵＤＦのテーブル・カラムを含む比較演算子に結び付けられ、（２）オリジナルの比較式の結果の（またはそれと等価な）新規のブール式を規定する。新規の式はインデックス（拡張または非拡張）が存在することをうまく使用できる可能性があり、オプティマイザによって代替述部を生成するために使用される。この新規の式を、クエリ書き換えルールがＵＤＦまたは各型に適用して、標準のまたは拡張のインデックスに関連付けることができ、含意か等価のいずれかを表すことができる。
【００４１】
クエリ書き換えルールの式の機能（power：能力）は、それらが標準インデックスに関連付けられるか、あるいは拡張インデックスに関連付けられるか、に依存して変わる。拡張インデックスの書き換えルールは任意のブール式をとることができるが、標準インデックスのルールにはかなり多くの制限がある。
【００４２】
標準インデックスの書き換えルールは、ＳｅｌｅｃｔおよびＪｏｉｎにおいてインデックス・ルックアップ（およびインデックス・ジョイン）の使用の可能性を探る既存のクエリオプティマイザ・ルールのコードに含めることができる。拡張インデックスの書き換えルールは、クエリ・オプティマイザにおける新規の検索ルールによって考慮することができる。
【００４３】
本明細書で示したように、ＳｅｌｅｃｔおよびＪｏｉｎにおいてインデックス・ルックアップの使用可能性を探るルールは、Ｓｅｌｅｃｔ（またはＪｏｉｎ）の比較式を結合要素に分解するクラスを使用する。次に、各ネイティブの結合要素を解析して、インデックス・ルックアップ操作の一部として使用される可能性があるかどうかを判断する。最後にすべてのインデックスを解析し、各インデックスについて、インデックス・シーク操作で使用される可能性がある結合要素を、またはインデックスの内容によってカバーされる結合要素を、リストアップする。そのクラスは、インデックスのある種の組を含むインデックス・ソリューションを見つけると、各インデックスごとにインデックスの式を生成し、これらの各インデックスによって使用される可能性のある、最初に生成された、結合要素を追跡する。タスクの終了時に、このインデックスによって処理されないすべての結合要素に対して、残余述部が生成される。
【００４４】
本発明を含む拡張のリストは以下のとおりである。
インデックス拡張スキーム：インデックス拡張スキームを生成するためのサポートを提供し、次いでその拡張のスキームに基づきインデックスの生成を可能にする。インデックス拡張スキームは以下の内容を指定する。すなわち、インデックスが付けられるデータ型に相当するキー・カラムのデータ型、１組のパラメータ（通常ドメイン指定）、およびテーブル値関数名である。テーブル値関数名は、インデックス生成および維持機構が使用して、インデックスが付けられるカラムの各値ごとのインデックス・エントリを生成する。ここで、インデックスに関する仮定についての主な緩和は、インデックスが付けられる各カラム値が、１つまたは複数のカラムを有する１つまたは複数のインデックス行を生成できることであり、したがってインデックス値を生成するためのテーブル値関数を生成できることである。  
拡張インデックス：上で定義されたインデックス拡張スキームを使用して各カラムのインデックスを生成する機能。  
変換ルール：インデックスは、ある種の演算子を効率的に評価するのに有用である。標準インデックスは、比較演算の効率的な評価が可能になる。同様に、拡張インデックスを使用してドメイン指定演算子または複雑なデータ型に適用可能な比較を効率的に評価することができる。この効率的な評価をサポートするために、ＳＱＬサーバはインデックス・データ型に対する述部（またはブール値関数）を、インデックス値を使用して評価できる式（すなわち、テーブル値関数をインデックス値に適用した結果）にマップする機能をサポートする。  
【００４５】
拡張性に関して、本発明は（ｉ）インデックス値をテーブル上の値にマップすること、および（ｉｉ）対応するテーブル上の値に対して、ＳＱＬの形で表現可能な代替のテーブル上の式に述部をマップすること、によって表すことができるものに限定される。
【００４６】
拡張インデックス
従来の２次的インデックスは以下のカラムの組を有する。  
−  インデックスが付けられたカラム（例えば、ＩＣ）、およびインデックス行が対応するベース・テーブル中の行を一意に識別するカラムの組。ベース・テーブルの各行ごとに、インデックス内に１つの行が存在する。  
−  ベース・テーブルのクラスタ化したキー・カラムを使用するか、またはクラスタ化したインデックスがないテーブルに対してベース行の物理識別子を使用して、ベース行を一意に識別するカラム。
【００４７】
拡張インデックスにおいて、前者の組、すなわちインデックスが付けられたカラムは、そのインデックスが付けられたカラムのユーザ指定関数を使用して生成されるという意味で異なるものである。さらに、そのユーザ指定関数はテーブル値関数なので、ベース・テーブルの各行に対するインデックスに２つ以上の行が存在し得る。
【００４８】
拡張インデックススキームの生成／維持
拡張インデックスは２ステップのプロセスで生成される。第１のステップは、以下の定義をカプセル化するインデックス拡張スキームの生成である。  
−  インデックスが付けられたカラムのデータ型  
−  一般にドメイン指定であるインデックスを生成する上で有用な追加のパラメータ
−  インデックスを生成し、インデックス入力（インデックスが付けられたカラムおよび追加のパラメータ）のテーブル値関数のパラメータへのマップを生成するために使用されるテーブル値関数。  
−  主インデックスに追加してインデックス付けられ、クエリ・オプティマイザがベース・テーブルの主キー・カラムに関して生成するテーブル値インデックスのカラム。
【００４９】
新規のＣＲＥＡＴＥ  ＩＮＤＥＸ  ＥＸＴＥＮＳＩＯＮステートメントを使用してインデックス拡張を生成する。
【００５０】
インデックス拡張スキームが生成されると、この拡張スキームの例に過ぎないが、実際のインデックスをＣＲＥＡＴＥ  ＩＮＤＥＸステートメントへの拡張によって生成することができる。
【００５１】
以下に、ＣＲＥＡＴＥ  ＩＮＤＥＸ  ＥＸＴＥＮＳＩＯＮステートメントの構文と意味（syntax and semantics）を表す。
【００５２】
【数５】
2005267612.tif 000008
【００５３】
ルール
ｃｏｌｕｍｎ＿ｐａｒａｍ＿ｎａｍｅは、インデックスが付けられたデータ値であるプライマリ・インデックス・パラメータを指定する。ｃｏｌｕｍｎ＿ｄａｔａ＿ｔｙｐｅは、そのパラメータのデータ型である。ｃｏｌｕｍｎ＿ｄａｔａ＿ｔｙｐｅは、ＳＱＬサーバによってサポートされる（ｔｉｍｅｓｔａｍｐを除く）任意のスカラ・データ型、またはユーザ定義型とすることができる。ｃｏｌｕｍｎ＿ｔｙｐｅ＿ｓｃｈｅｍａは、オプションでＵＤＴに指定できる。
【００５４】
＠ｐａｒａｍ＿ｎａｍｅは追加のパラメータの名前を指定し、ｐａｒａｍ＿ｄａｔａ＿ｔｙｐｅはそれらに対応するデータ型を指定する。指定されるデータ型は、ＳＱＬサーバによってサポートされるスカラ型（ｔｉｍｅｓｔａｍｐを除く）またはユーザ定義型のどちらでもよい。
【００５５】
［ｔａｂｌｅ＿ｆｕｎｃｔｉｏｎ＿ｓｃｈｅｍａ．］ｔａｂｌｅ＿ｆｕｎｃｔｉｏｎ＿ｎａｍｅは、インデックス拡張が生成されている同一のデータベースにおける既存のテーブル値関数を指定するものである。このテーブル値関数は確定的（deterministic）である。
【００５６】
ＵＳＩＮＧ  ｃｌａｕｓｅの引数リストのすべてのパラメータ名は、ＦＯＲ  ｃｌａｕｓｅで（＠ｃｏｌｕｍｎ＿ｐａｒａｍ＿ｎａｍｅとして）、またはＷＩＴＨ  ＰＡＲＡＭＥＴＥＲＳ  ｃｌａｕｓｅで（＠ｐａｒａｍ  ｎａｍｅとして）定義されたパラメータ名のリストから得られる。これは、インデックス拡張のカラム・データ値および追加のパラメータが与えられたとして、テーブル値関数がどのように呼び出されるかに関する結合を設定するものである。
【００５７】
インデックス拡張スキームの生成は、テーブル値関数上で暗黙のスキーマ結合を生成する。したがってテーブル値関数は、それを使用するインデックス拡張スキームが存在する限り、削除または変更することができない。
【００５８】
ＯＮ  ｃｌａｕｓｅの後ろに指定されるカラムのリストは、指定されたテーブル値関数の結果によって戻されたカラム名である必要がある。このリストは、クエリ・プロセッサがベース・テーブルのプライマリ・キーに常に生成するインデックスに加えて、指定されたカラムの追加のインデックスを指定する。
【００５９】
例１
空間データ型仕様における空間の場合
【００６０】
【数６】
2005267612.tif 000009
【００６１】
インデックス拡張スキームの削除
構文
【００６２】
【数７】
2005267612.tif 000010
【００６３】
ルール
このインデックス拡張スキームに基づくデータベース中に拡張インデックスがある場合は、そのインデックス拡張スキームは削除できない。
【００６４】
拡張インデックスの生成／管理
拡張スキームが生成されると、この生成されたインデックス拡張スキームを使用して１つまたは複数のインデックスを生成することができる。ＣＲＥＡＴＥ  ＩＮＤＥＸは、インデックスが付けられたカラムを指定し、インデックス拡張スキームの一部として指定されるテーブル値関数に提供される追加のパラメータの値も提供する。
【００６５】
構文
【００６６】
【数８】
2005267612.tif 000011
【００６７】
ルール
カラムのデータ型は、インデックス拡張の＠ｃｏｌｕｍｎ＿ｐａｒａｍ＿ｎａｍｅのデータ型と同一である必要がある。
【００６８】
ＰＡＲＡＭＥＴＥＲＳのｉｎｄｅｘ＿ｏｐｔｉｏｎに提供されるパラメータ値は、Ｔ−ＳＱＬのリテラルであり、対応するインデックス拡張のＰＡＲＡＭＥＴＥＲＳ  ｃｌａｕｓｅで指定されたパラメータと、順序およびデータ型の互換性に関して１：１に対応している必要がある。
【００６９】
スカラＵＤＦ（ユーザ定義関数）もまたインデックス拡張スキームで許可されており、この場合、インデックスが付けられる値はカラム値そのものではなく、そのＵＤＦの結果となる。
【００７０】
実装上の注意
インデックスは、次のステートメントが実行された場合のように、インデックス・ビューを生成し維持することによって生成することができる。
【００７１】
【数９】
2005267612.tif 000012
【００７２】
上記のビューは、一意でないクラスタ・インデックスを使用してインデックスが付けられる。
【００７３】
【数１０】
2005267612.tif 000013
【００７４】
この＜ｓｙｓｔｅｍ−ｇｅｎｅｒａｔｅｄ−ｖｉｅｗ＞が与えられると、次の等価関係が真であることに留意されたい。
【００７５】
【数１１】
2005267612.tif 000014
【００７６】
上式で、ｔ．＜ｐｒｉｍａｒｙ−ｋｅｙ＞は、ベース・テーブルのプライマリ・キーへの参照である。
【００７７】
上記のインデックスに加えて、クエリ・プロセッサはＯＮ  ｃｌａｕｓｅによって指定される追加のインデックスも生成する。
【００７８】
例１（続き）
【００７９】
【数１２】
2005267612.tif 000015
【００８０】
上記実装上の注意どおり、これはＳＱＬサーバに以下のインデックス・ビューを生成させることを引き起こす。
【００８１】
【数１３】
2005267612.tif 000016
【００８２】
拡張インデックスの削除
拡張インデックスは、そのインデックスを使用しているルールがない限り、現在存在するＤＲＯＰ  ＩＮＤＥＸステートメントを使用して削除することができる。
【００８３】
含意／等価ルール
他のブール値式（Boolean-valued expression）に関する複雑な述部関数の論理的含意または同値を指定するルールがサポートされており、これは、上記の拡張インデックスを生成するために使用されたのと同じテーブル値関数を使用する。この場合、クエリ・プロセッサ（ＱＰ）は、（拡張インデックス中に存続する）あらかじめ計算されたテーブル値関数を使用してこのブール式を評価することができる。オリジナルの述部関数は、ルールが含意ルールであり、かつブール値式が真である場合にだけ評価されることになる。
【００８４】
構文
【００８５】
【数１４】
2005267612.tif 000017
【００８６】
ルール
［ｏｒｉｇｉｎａｌ＿ｆｕｎｃｔｉｏｎ＿ｓｃｈｅｍａ．］ｏｒｉｇｉｎａｌ＿ｆｕｎｃｔｉｏｎ＿ｎａｍｅによって指定されるスカラユーザ定義関数は、現在のデータベース中に存在しなければならない。
【００８７】
＠ｉｎｄｅｘ＿ａｕｇｕｍｅｎｔは、ａｒｇｕｍｅｎｔ＿ｌｉｓｔ中の引数の１つとマッチしなければならない。
【００８８】
ｂｏｏｌｅａｎ＿ｅｘｐｒｅｓｓｉｏｎは、ａｒｇｕｍｅｎｔ＿ｌｉｓｔの引数または、指定されたインデックス拡張スキームの（ＰＡＲＡＭＥＴＥＲＳ  ｃｌａｕｓｅで定義された）パラメータのどちらかにマッチすべき引数（接頭辞「＠」のついた識別子）への参照を含むことができる。
【００８９】
ｂｏｏｌｅａｎ＿ｅｘｐｒｅｓｓｉｏｎは、指定されたｉｎｄｅｘ＿ｅｘｔｅｎｓｉｏｎ＿ｓｃｈｅｍｅによって使用されるテーブル値関数を参照する必要がある。
【００９０】
ＴＹＰＥ  ＥＱＵＩＶＡＬＥＮＣＥが指定された場合は、ルールは完全な等価を表す。したがって、クエリ・オプティマイザはオリジナルの関数を最後に呼び出す必要はない。ＴＹＰＥ  ＩＭＰＬＩＣＡＴＩＯＮが指定された場合には、クエリ・プロセッサは指定されたブール式が真の場合でもオリジナルの関数を最後に呼び出す必要がある。
【００９１】
クエリ書き換え論理  ＱＰは、以下の条件に合致した場合には、ユーザ定義スカラ関数の所与の呼出しに含意ルールを使用する。ＷＩＴＨ  ＩＮＤＥＸ  ＴＹΡＥ  ｃｌａｕｓｅ中で指定される型の拡張インデックスは、この関数の引数であるカラムとして存在し、またその引数の位置は、＠ｉｎｄｅｘ＿ａｒｇｕｍｅｎｔによって指定された位置にマッチする。
【００９２】
含意ルールが使用された場合、そのルールは関数呼出しを次のように書き換える。  
original-function-name (...,T.col,...)  
上式で、Ｔ．ｃｏｌは、拡張インデックスが存在するインデックス付きのカラムである。次いで、上記関数はそのルールに対応するｂｏｏｌｅａｎ＿ｅｘｐｒｅｓｓｉｏｎとして書き換えられる。この場合、ｂｏｏｌｅａｎ＿ｅｘｐｒｅｓｓｉｏｎ内部に存在する各テーブル値関数は、対応する拡張インデックスに対する次のテーブル式に置き換えられる。
【００９３】
【数１５】
2005267612.tif 000018
【００９４】
クエリ・オプティマイザは、すべての代替述部を個々に（かつ同一の候補に２つ以上を使用することなく）考慮し、最も安価な述部を採用する。
【００９５】
例１（続き）
【００９６】
【数１６】
2005267612.tif 000019
【００９７】
ユーザ・クエリ：
【００９８】
【数１７】
2005267612.tif 000020
【００９９】
は、次のように書き換えられる。
【０１００】
【数１８】
2005267612.tif 000021
【０１０１】
例２
テーブル値関数（ｆｔ＿Ｉｎｄｅｘｇｅｎｔｅｘｔｖａｌ）の結果にインデックスを付けることを利用し、１組の（ｗｏｒｄ、ｆｒｅｑｕｅｎｃｙ、ｌｏｃａｔｉｏｎ）の形の一組の行、そこには、ｔｅｘｔｖａｌ内の各ｗｏｒｄの存在ごとにエントリがある、を返すフルテキスト・インデックス・スキームを考える。各行は、ｗｏｒｄ、そのｆｒｅｑｕｅｎｃｙ、およびｌｏｃａｔｉｏｎを含む。ｆｒｅｑｕｅｎｃｙはドキュメント中に存在する数であり、ｌｏｃａｔｉｏｎは、ｗｏｒｄの存在が突きとめられるｔｅｘｔｖａｌ内のオフセットである。テーブル値関数は以下のように生成できる。
【０１０２】
【数１９】
2005267612.tif 000022
【０１０３】
インデックス拡張は以下のように生成できる。
【０１０４】
【数２０】
2005267612.tif 000023
【０１０５】
述部ＣＯＮＴＡＩＮＳ（＠ｔｅｘｔｖａｌ，＜ｐｈｒａｓｅ＞）を考える。この述部は、＠ｔｅｘｔｕａｌに＜ｐｈｒａｓｅ＞中のすべての語が少なくとも１度現れるときだけ真を返す。以下のルールの論理は、同様に＠ｐｈｒａｓｅ中の語で＠ｔｅｘｔｖａｌに現れない語がない場合にだけＣＯＮＴＡＩＮＳ（＠ｔｅｘｔｖａｌ，＠ｐｈｒａｓｅ）が真になる。
【０１０６】
【数２１】
2005267612.tif 000024
【０１０７】
次に、テーブルＣａｎｄｉｄａｔｅｓ（ＣａｎｄｉｄａｔｅＩＤ，ＬａｓｔＮａｍｅ，ＦｉｒｓｔＮａｍｅ，ＣｏｎｔａｃｔＰｈｏｎｅ，Ｒｅｓｕｍｅ）を考える。Ｒｅｓｕｍｅのカラムは、ＦｕｌｌｔｅｘｔＩｎｄｅｘＳｃｈｅｍｅを使用してそのカラムに生成されたインデックスを有する。
【０１０８】
Ｒｅｓｕｍｅに「Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄａｔａｂａｓｅ」という語を有するすべてのＣａｎｄｉｄａｔｅを探すクエリは、以下のようになる。
【０１０９】
【数２２】
2005267612.tif 000025
【０１１０】
上記のクエリは、拡張インデックスと、ＣＯＮＴＡＩＮＳ関数についての含意ルールが与えられたとすると、オプティマイザによって以下のように書き換えられる。
【０１１１】
【数２３】
2005267612.tif 000026
【０１１２】
次に図８を参照すると、本発明による、人工知能コンポーネント（クラシファイア８０２）を使用するシステム８００が示されている。本発明は、（例えば選択に関連して）本発明の様々な態様を実施するために様々な人工知能ベースのスキームを使用することができる。例えば、ユーザに応じて何時どのように含意ルールに重み付けするかを決定するためのプロセスは、自動クラシファイア・システムおよびプロセス（automatic classifier system and process）によって容易に行うことができる。このプロセスは、制約条件を使用して実施することができる。
【０１１３】
クラシファイアは、入力属性ベクトルｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘｎ）を、あるクラスにその入力が属するという確かさ（confidence）にマップする関数、すなわちｆ（ｘ）＝ｃｏｎｆｉｄｅｎｃｅ（ｃｌａｓｓ）である。この分類は、確率および／または統計に基づいた解析（例えば、解析ユーティリティおよびコストの考慮）を使用して、ユーザが自動的に実施したいと望む動作を予知または推論することができる。
【０１１４】
サポート・ベクトル・マシン（ＳＶＭ）は、使用できるクラシファイアの一例である。ＳＶＭは可能な入力の空間における超曲面を見つけることによって動作する。この超曲面は、トリガ基準を非トリガ・イベントから分離しようと試みる。直感的にこれは、学習データ（training data）に近いが同一ではない試験データの正しい分類を行わせる。例えば、様々な独立のパターンを提供する単純ベイズ
【０１１５】
2005267612.tif 000027
【０１１６】
、ベイズ・ネットワーク（Bayesian networks）、決定木、確率的分類モデルなどを含む、他の有向および無向モデル分類アプローチが使用できる。本明細書で使用する分類は、優先度モデルの開発に使用される統計的回帰も含む。
【０１１７】
本明細書から容易に理解されるように、本発明は（例えば、一般的な学習データによって）明示的に学習されるクラシファイアならびに（例えば、外部情報を受信するユーザ挙動を観察することによって）暗黙に学習されるクラシファイアを使用することができる。例えばＳＶＭのクラシファイアは、クラシファイア・コンストラクタおよび機能選択モジュール（feature selection module）内の学習または訓練フェーズを通して構成される。したがって、これらのクラシファイアを使用して多くの機能を自動的に実施することができる。例えば、アプリケーションがｎｏｎ−ｉｎｄｅｘａｂｌｅ型のデータ型へのものであるかどうかとは無関係に、クラシファイア８０２を単独でまたはコスト・ベースのオプティマイザ１２０と組み合わせて使用して、オリジナルの述部を実行するのが複雑すぎるかまたはコストがかかりすぎる場合に、含意または等価述部がはるかに低コストで実行できるかどうかを決定することができ、クラシファイア８０２は先ず含意または等価述部を使用して検索および結果を評価することができる。その後で、その複雑な検索は、より複雑なまたはコストがかかる検索を実行する前に、その評価に従って絞り込むことができる。
【０１１８】
クラシファイア８０２を使用して、選択性および／または基数見積り（cardinality estimation）についての追加の情報を使用することもできる。したがって、含意ルールを使用して検索を狭めることができるが、例えば基数見積りなどの、見積りを使用して狭めることもできる。次いでこれらの見積りは、実行されないように後で削除することができる。
【０１１９】
暗黙の述部を使用して基数見積りを改善することができる。結局、この改善により、より有効な実行計画が得られる。正確な基数見積りはさらに、より信頼できる実行コストの見積りをサポートし、したがって、よりロバストな実行計画の選択をサポートする。例えば、含意ルールによってＰ１とＰ２とが等価であることが知られており、Ｐ２の見積りがより簡単である場合には、ロバスト性が増したことになる。さらに、Ｐ１がＰ２を含むがＰ１とＰ２とが等価でない場合には、Ｐ２を満たす各行を見積もることによって、Ｐ１を満たす各行に関する上限を決定することができる。これもまた、重要な情報である。
【０１２０】
クラシファイア８０２を使用して、ほんのいくつかの例を挙げれば、検索されるデータのタイプ、検索の時間（the time of the search）、検索されるデータのサイズ、データが分散されているか否か、およびクエリ式の複雑さに関連するパラメータに基づいて推論を行うこともできる。
【０１２１】
次に図９を参照すると、開示されたアーキテクチャを実行するように動作できるコンピュータのブロック図が示されている。図９および以下の説明は、本発明の様々な態様についての追加のコンテクストを提供するために、本発明の様々な態様を実施できる適切なコンピュータ環境９００の簡潔な、一般的な説明を提供することを意図したものである。ここまで本発明を１つまたは複数のコンピュータ上で実行できるコンピュータ実行可能な命令の一般的なコンテクストの中で説明してきたが、当業者なら本発明が、他のプログラム・モジュールとの組合せ、および／またはハードウェアとソフトウェアの組合せとしても実装できることを理解されよう。
【０１２２】
一般にプログラム・モジュールは、ルーチン、プログラム、コンポーネント、データ構造などを含み、特定のタスクを実行するかまたは特定の抽象データ型を処理する。さらに、当業者なら本発明の方法が、例えば、シングル・プロセッサまたはマルチ・プロセッサ・コンピュータ・システム、ミニ・コンピュータ、メインフレーム・コンピュータ、ならびにパーソナル・コンピュータ、ハンドヘルド・コンピュータ装置、マイクロ・プロセッサ・ベースまたはプログラマブルな消費者家電など、それぞれが１つまたは複数の関連する装置に動作可能に結合された他のコンピュータ・システム構成とともに実施し得ることを理解されよう。
【０１２３】
例示した本発明の態様は分散コンピューティング環境においても実施できるものであり、その場合いくつかのタスクは、通信ネットワークによってリンクされたリモート・プロセッシング装置によって実施される。分散コンピューティング環境では、プログラム・モジュールは、ローカルおよびリモートのメモリ記憶装置のどちらに置くこともできる。
【０１２４】
一般に、コンピュータは様々なコンピュータ可読のメディアを含む。コンピュータ可読のメディアは、コンピュータがアクセスできる任意の利用可能なメディアでよく、揮発性および不揮発性のメディア、リムーバブルなおよびリムーバブルでないメディアのどちらをも含むことができる。例として、限定の意味ではなく、コンピュータ可読メディアはコンピュータ記憶メディアおよび通信メディアを含むことができる。コンピュータ記憶メディアは揮発性および不揮発性、リムーバブルなおよびリムーバブルでないメディアのどちらをも含むことができ、それらはコンピュータ可読の命令、データ構造、プログラム・モジュール、その他のデータなどの情報を記憶するための任意の方法および技術で実装される。コンピュータ記憶メディアは、これに限られるものではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリなどのメモリ技術、ＣＤＲＯＭ、ＤＶＤ（デジタル・ビデオ・ディスク）などの光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置などの磁気記憶装置、あるいは所望の情報を記憶するために使用でき、コンピュータによってアクセス可能な任意の他のメディアを含む。
【０１２５】
通信メディアは一般に、コンピュータ可読の命令、データ構造、プログラム・モジュール、その他のデータを、搬送波または他の伝送機構などの変調データ信号の形で実施する。また、通信メディアは任意の情報配送メディアを含む。「変調データ信号」という用語は、信号中に情報をコード化するように設定または変更された、１つまたは複数の特性を有する信号を意味する。例えば通信メディアは、限定の意味ではなく、有線ネットワークや直接有線接続などの有線メディア、および音響、ＲＦ、赤外線などの無線メディアを含む。上記のメディアの任意の組合せもまた、コンピュータ可読メディアの範囲内に含まれるものとする。
【０１２６】
再度図９を参照すると、本発明の様々な態様を実装するための、コンピュータ９０２を含む例示的環境９００が示されており、コンピュータ９０２は、処理ユニット９０４、システム・メモリ９０６、システム・バス９０８を含む。システム・バス９０８は、例えば、これに限られるものではないが、システム・メモリ９０６などを処理ユニット９０４に結合する。処理ユニット９０４は、様々な市販のプロセッサのいずれであってもよい。処理ユニット９０４としてデュアル・マイクロ・プロセッサや他のマルチ・プロセッサのアーキテクチャも使用できる。
【０１２７】
システム・バス９０８は、（メモリ・コントローラ付きの、またはなしの）メモリ・バス、ペリフェラル・バス、および様々な市販のバス・アーキテクチャのいずれかを使用するローカル・バスにさらに相互接続できる、いくつかの種類のバス構造のうちのいずれであってもよい。システム・メモリ９０６は、ＲＯＭ（読み出し専用メモリ）９１０およびＲＡＭ（ランダム・アクセス・メモリ）９１２を含む。ＢＩＯＳ（基本入出力システム）は、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭなどの不揮発メモリ９１０に格納される。このＢＩＯＳは、例えばスタートアップ時に、コンピュータ９０２の各要素間での情報伝送を助ける基本ルーチンを含む。ＲＡＭ９１２は、データをキャッシュするためのスタティックＲＡＭなどの高速ＲＡＭを含むこともできる。
【０１２８】
コンピュータ９０２はさらに、（例えば、ＦＩＤＥ、ＳＡＴＡなどの）内蔵ハードディスク・ドライブ（ＨＤＤ）９１４、（例えば、リムーバブルなディスケット９１８からの読出しまたはそれへの書き込みのための）磁気フロッピー（登録商標）・ディスク・ドライブ（ＦＤＤ）９１６、ならびに（例えば、ＣＤ−ＲＯＭディスク９２２の読出し、またはＤＶＤなど他の大容量光メディアからの読出しまたはそれへの書き込みのための）光ディスク・ドライブ９２０を含む。なお、内蔵ハードディスク・ドライブ９１４は適切なシャーシ（図示せず）に入れて外付けで使用することも可能である。ハードディスク・ドライブ９１４、磁気ディスク・ドライブ９１６、および光ディスク・ドライブ９２０は、それぞれハードディスク・ドライブ・インターフェース９２４、磁気ディスク・ドライブ・インターフェース９２６、および光ドライブ・インターフェースによってシステム・バス９０８に接続できる。外部ドライブ実装のためのインターフェース９２４は、ＵＳＢ（ユニバーサルシリアルバス）およびＩＥＥＥ１３９４インターフェース技術の少なくとも一方または両方を含む。
【０１２９】
ドライブおよびそれに関連するコンピュータ可読のメディアは、データ、データ構造、コンピュータ実行可能な命令などの不揮発記憶を提供する。ドライブおよびメディアは、コンピュータ９０２用の適切なディジタル形式の任意のデータを記憶する。上記のコンピュータ可読メディアの説明では、ＨＤＤ、リムーバブル磁気ディスク、ＣＤやＤＶＤなどのリムーバブル光メディアに言及したが、当業者ならば、例えばｚｉｐドライブ、磁気カセット、フラッシュ・メモリ・カード、カートリッジなど、コンピュータ可読の他の種類のメディアも例示の動作環境で使用できること、さらにまた、このようなメディアに、本発明の方法を実施するためのコンピュータ実行可能な命令を含めることができることを理解されたい。
【０１３０】
ドライブおよびＲＡＭ９１２には、オペレーティング・システム９３０、１つまたは複数のアプリケーション・プログラム９３２、他のプログラム・モジュール９３４、プログラム・データ９３６など多くのプログラム・モジュールを格納することができる。オペレーティング・システム、アプリケーション、モジュール、および／またはデータのすべてまたは一部をＲＡＭ９１２にキャッシュすることもできる。
【０１３１】
本発明が、様々な市販のオペレーティング・システムまたはオペレーティング・システムの組合せで実装できることを理解されたい。
【０１３２】
ユーザは、例えばキーボード９３８など１つまたは複数の有線／無線の入力装置、および例えばマウス９４０などのポインティング・デバイスを介してコマンドおよび情報をコンピュータ９０２に入力することができる。他の入力装置（図示せず）には、マイクロフォン、ＩＲリモート・コントロール、ジョイスティック、ゲームパッド、スタイラス・ペン、タッチ・スクリーンなどがある。これらおよび他の入力装置は、しばしばシステム・バス９０８に結合された入力装置インターフェース９４２を介して処理ユニット９０４に接続されるが、他のインターフェースを介してパラレル・ポート、ＩＥＥＥ１３９４シリアルポート、ゲームポート、ＵＳＢポート、ＩＲインターフェースなどに接続することもできる。
【０１３３】
モニタ９４４または他の種類の表示装置は、ビデオ・アダプタ９４６などのインターフェースを介してシステム・バス９０８に接続することもできる。モニタ９４４の他に、コンピュータは一般に、スピーカやプリンタなどの他の周辺機器出力装置（図示せず）を含む。
【０１３４】
コンピュータ９０２は、１つまたは複数のリモート・コンピュータ、例えばリモート・コンピュータ９４８などへの有線および／または無線通信を介した論理接続を用いて、ネットワーク環境で動作することもできる。リモート・コンピュータ９４８は、例えばワークステーション、サーバ・コンピュータ、ルータ、パーソナル・コンピュータ、ポータブル・コンピュータ、マイクロ・プロセッサ・ベースの娯楽装置、ピア装置、またはその他の共通ネットワーク・ノードであってもよく、簡潔のためにメモリ記憶装置９５０だけを示したが、一般にコンピュータ９０２に関して説明した要素の多くまたはすべてを含む。図示の論理接続には、ＬＡＮ（ローカル・エリア・ネットワーク）９５２および／または大規模ネットワーク、例えばＷＡＮ（ワイド・エリア・ネットワーク）９５４などへの有線／無線の接続が含まれる。このようなＬＡＮおよびＷＡＮのネットワーク環境はオフィスや会社では一般的なものであり、この環境によりイントラネットなど企業規模でのコンピュータ・ネットワークが容易に実現できる。これらのネットワークはすべて、インターネットなどのグローバルな通信ネットワークに接続することができる。
【０１３５】
ＬＡＮネットワーク環境で使用されるとき、コンピュータ９０２は有線／無線ネットワーク・インターフェースまたはアダプタ９５６を介してローカル・ネットワーク９５２に接続される。アダプタ９５６は、ＬＡＮ９５２への有線または無線の通信を容易にすることができる。またＬＡＮ９５２は、その上に配置された、無線アダプタ９５６との通信のための無線アクセス・ポイントを含むこともできる。ＷＡＮネットワーク環境で使用されるとき、コンピュータ９０２はモデム９５８を含むことができ、あるいはＬＡＮ上の通信サーバに接続され、あるいはインターネットなどによる、ＷＡＮ９５４を介した通信を確立する他の手段を有する。モデム９５８は、シリアル・ポート・インターフェース９４２を介してシステム・バス９０８に接続される。モデムは内蔵または外置きの、有線または無線の装置であってもよい。コンピュータ９０２に関連して、またはその一部として図示されているプログラム・モジュールは、ネットワーク環境ではリモートのメモリ／格納装置９５０に格納することができる。図示されたネットワーク接続が例示的なものであり、コンピュータ間の通信リンクを確立する他の手段を使用することができることを理解されたい。
【０１３６】
コンピュータ９０２は、任意の無線装置、または無線通信で動作可能に配置されたエンティティと通信するように動作可能である。これらの無線装置またはエンティティは、例えばプリンタ、スキャナ、デスクトップおよび／またはポータブル・コンピュータ、ポータブル・データ・アシスタント、通信衛星、無線で検出可能なタグに関連する任意の装置またはロケーション（例えば、キオスク、ニュース・スタンド、トイレなど）、電話などである。無線通信には、少なくともＷｉ−ＦｉおよびＢｌｕｅｔｏｏｔｈ（登録商標）無線技術が含まれる。したがって通信は、従来のネットワークと同様の既定の構造であっても、あるいは単なる少なくとも２つの装置間のアドホック通信であってもよい。
【０１３７】
Ｗｉ−Ｆｉ、すなわちＷｉｒｅｌｅｓｓ  Ｆｉｄｅｌｉｔｙ（ワイヤレス・フィディリティー）を使用すると、家庭のソファー、ホテルの部屋のベッド、または職場の会議室から無線でインターネットに接続することができる。Ｗｉ−Ｆｉは携帯電話などの無線技術であり、この技術を用いると、例えばコンピュータなどの装置は、基地局の範囲内にある任意の場所の室内および室外でデータの送受信が可能になる。Ｗｉ−ＦｉネットワークはＩＥＥＥ８０２．１１（ａ、ｂ、ｇ、その他）と呼ばれる無線技術を使用して、セキュアで信頼性のある高速な無線接続を提供する。Ｗｉ−Ｆｉネットワークを使用して、コンピュータを相互に、インターネットに、あるいは（ＩＥＥＥ８０２．３またはイーサネット（登録商標）を使用する）有線ネットワークに接続することができる。Ｗｉ−Ｆｉネットワークは免許不要の２．４ＧＨｚおよび５ＧＨｚ無線帯域で、１１Ｍｂｐｓ（８０２．１１ｂ）または５４Ｍｂｐｓ（８０２．１１ａ）のデータレートで動作し、あるいは両方の帯域を含む（デュアル・バンド）製品で動作する。したがってこのネットワークは、多くのオフィスで使用されている基本の１０ＢａｓｅＴ有線イーサネット（登録商標）ネットワークと同等の実環境性能を提供することができる。
【０１３８】
次に図１０を参照すると、本発明による、例示的コンピュータ環境の概略のブロック図が示されている。システム１０００は、１つまたは複数のクライアント１００２を含む。クライアント１００２は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピュータ装置など）であってもよい。クライアント１００２は、本発明を使用することにより、例えばクッキーおよび／または関連するコンテクスト情報を収容することができる。システム１０００は、１つまたは複数のサーバ１００４を含むこともできる。サーバ１００４もまた、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピュータ装置など）であってもよい。サーバ１００４は、本発明を使用することにより、例えば変換を実施するスレッドを収容することができる。クライアント１００２とサーバ１００４の間の１つの可能な通信は、２つ以上のプロセスの間で送信されるように適合されたデータ・パケットの形で行うことができる。データ・パケットは、例えばクッキーおよび／または関連するコンテクスト情報を含むことができる。システム１０００は、（例えばインターネットなどのグローバル通信ネットワークなどの）通信フレームワーク１００６を含み、このフレームワークを使用してクライアント１００２とサーバ１００４の間の通信を容易に実施することができる。
【０１３９】
通信は、有線（光ファイバを含む）および／または無線技術によって容易に実施できる。クライアント１００２は、１つまたは複数のクライアント・データ記憶装置１００８に動作可能に接続されており、この記憶装置を使用してクライアント１００２固有の情報（例えば、クッキーおよび／または関連するコンテクスト情報など）を格納することができる。同様にサーバ１００４は、１つまたは複数のサーバ・データ記憶装置１０１０に動作可能に接続されており、この記憶装置を使用してサーバ１００４固有の情報を格納することができる。
【０１４０】
ここまで説明してきたものは、本発明のいくつかの例に過ぎない。もちろん、本発明を説明するために、コンポーネントまたは方法の考えられるあらゆる組合せを説明することは不可能だが、当業者なら本発明の他の多くの組合せおよび置き換えが可能であることを理解できるはずである。したがって本発明は、添付の特許請求の範囲の趣旨および範囲に含まれるようなあらゆる代替形態、修正形態、および変形形態を包含することを意図したものである。さらに、「含む（include）」という用語が、詳細な説明あるいは特許請求の範囲で使用される限りにおいて、この用語は、「備える（comprising）」が特許請求の範囲の移行句として使用されるときに解釈される「備える（comprising）」という用語と同様に包含的（inclusive）であることが意図される。
【図面の簡単な説明】
【０１４１】
【図１】本発明によるシステムを示す図である。
【図２】本発明の一プロセスを示す流れ図である。
【図３】本発明によるシステムを示す図である。
【図４】本発明による、標準インデックスを処理する方法を示す流れ図である。
【図５】本発明による、あるクエリの初期の演算子ツリーと書き換え規則によって生成された暗黙の述部を含む最終の演算子ツリーとを示す図である。
【図６】本発明による、多値インデックスを処理するシステムを示すブロック図である。
【図７】本発明による、多値インデックスを処理する方法を示す流れ図である。
【図８】本発明による、人工知能を使用するシステムを示す図である。
【図９】開示のアーキテクチャを実行するように動作可能なコンピュータを示すブロック図である。
【図１０】本発明による、例示的なコンピュータ環境を示す概略ブロック図である。
【符号の説明】
【０１４２】
１００  本発明のシステム
１０２  最適化コンポーネント
１０４  データ・リポジトリ
１０６  クエリ
１０８  クエリ・コンポーネント
１１０  述部コンポーネント
１１４  暗黙の述部
１１６  等価述部
１１８  残余述部
１２０  コスト・ベース・オプティマイザ
３００  本発明によるシステム
３０２  メタデータ・エンジン
３０４  ルール・コンポーネント
５００  書き換えルールによって生成された暗黙の述部を有するクエリの初期の演算子ツリー
５０２  最終の演算子ツリー
６００  多値インデックスを処理するシステム
６０２  ルール・コンポーネント
８００  人工知能コンポーネントを使用するシステム
８０２  クラシファイア
９００  コンピュータ環境
９０２  コンピュータ
９０４  処理ユニット
９０６  システム・メモリ
９０８  バス
９１０  ＲＯＭ
９１２  ＲＡＭ
９１４  ＨＤＤ
９１６  ＦＤＤ
９１８  ディスク
９２０  ＣＤドライブ
９２２  ディスク
９２４、９２６、９２８  インターフェース
９３０  オペレーティング・システム
９３２  アプリケーション
９３４  モジュール
９３６  データ
９３８  キーボード
９４０  マウス
９４２  入力装置インターフェース
９４４  モニタ
９４６  ビデオ・アダプタ
９４８  リモート・コンピュータ
９５０  メモリ／記憶装置
９５２  ＬＡＮ
９５４  ＷＡＮ
９５６  ネットワーク・アダプタ
９５８  モデム
１０００  システム
１００２  クライアント
１００４  サーバ
１００６  通信フレームワーク
１００８  クライアント・データ記憶装置
１０１０  サーバ・データ記憶装置
【図１】
2005267612.tif 000028
【図２】
2005267612.tif 000029
【図３】
2005267612.tif 000030
【図４】
2005267612.tif 000031
【図５】
2005267612.tif 000032
【図６】
2005267612.tif 000033
【図７】
2005267612.tif 000034
【図８】
2005267612.tif 000035
【図９】
2005267612.tif 000036
【図１０】
2005267612.tif 000037