(57)【要約】【課題】  クエリオプティマイザのシステムおよび方法を提供すること。【解決手段】  オプティマイザ／ノーマライザを使用して、ＸＭＬ入力クエリなどの入力クエリの最適化された中間言語表現を生成する。中間言語の形での入力クエリの最適化の一方法は、入力クエリを受け取り、最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先方式で各ノードを調べ、入力クエリの中間言語表現の全体が調べられるまで識別されたコードパターンにタグ付けし、中間言語表現の先頭からタグ付けされたコードパターンを探索し、入力クエリの最適表現を形成するために改善されたコードパターンを用いてタグ付けされたコードパターンを調整することを含む。オプティマイザ／ノーマライザへの入力は、コードパターンおよび各々がそれぞれのノード型を有するノードを含む中間言語表現に変換された入力クエリであると想定される。【選択図】  図２
2005018767.tif 000002
【特許請求の範囲】
【請求項１】
入力クエリの最適表現を構築する方法であって、
各々がノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
最適化の対象であるノード型を識別するために左深さ優先方式で前記ノードを調べるステップと、
識別されたノード型に対応するノードにタグ付けするステップと、
前記入力クエリの前記中間言語表現の全体が調べられるまで上方の次のノードに移動するステップと、
前記中間言語表現の先頭からタグ付けされたノードを探索し、最適化される関連コードパターンを識別するステップと、
前記入力クエリの最適表現を形成するために、改善されたコードパターンを用いて識別されたコードパターンを調整するステップと
を含むことを特徴とする方法。
【請求項２】
前記受け取るステップは意味的中間言語表現を受け取るステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記意味的表現はノードを含むグラフ構造を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とする請求項１に記載の方法。
【請求項５】
入力クエリの最適表現を構築する方法を実施するコンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記方法は、
コードパターンおよび各々がノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先方式で前記ノードを調べるステップと、
前記入力クエリの前記中間言語表現の全体が調べられるまで識別されたコードパターンにタグ付けするステップと、
前記中間言語表現の先頭からタグ付けされたコードパターンを探索するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記タグ付けされたコードパターンを調整するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項６】
入力クエリの最適化表現を生成するコンピュータシステムであって、
入力クエリを受け取る入力装置、
ノードを含む中間言語表現が前記入力クエリから生成される１つまたは複数の中間言語コンパイラ、および
各々がノード型を有するノードを含む中間言語表現である前記入力クエリを受け取る動作と、
最適化の対象であるノード型を識別するために左深さ優先方式で前記ノードを調べる動作と、
識別されたノード型に対応するノードにタグ付けする動作と、
前記入力クエリの前記中間言語表現の全体が調べられるまで上方の次のノードに移動する動作と、
前記中間言語表現の先頭からタグ付けされたノードを探索し、最適化される関連コードパターンを識別する動作と、
前記入力クエリの最適表現を形成するために、改善されたコードパターンを用いて識別されたコードパターンを調整する動作と
を実行するオプティマイザと
を備えたことを特徴とするコンピュータシステム。
【請求項７】
クエリ結果を形成する最適化後処理部分をさらに含み、該最適化後処理部分は
前記最適表現がターゲットクエリを形成する１つまたは複数のターゲット表現に変換される１つまたは複数のターゲットジェネレータと、
クエリ先の１つまたは複数のデータソースと、
クエリ結果を生成するために前記ターゲットクエリが前記１つまたは複数のデータソースに対して実行される１つまたは複数の実行エンジンと
を備えたことを特徴とする請求項６に記載のシステム。
【請求項８】
１つまたは複数の入力クエリのＸＭＬ中間言語表現の最適化表現を生成するコンピュータシステムであって、
１つまたは複数の入力クエリを受け取る１つまたは複数の入力装置、
各コンパイラが入力クエリの中間言語表現を生成する１つまたは複数の中間言語コンパイラ、
各中間言語表現を単一のＸＭＬ中間言語表現に結合する式アキュムレータ、および
コードパターンおよび各々がノード型を有するノードを含む中間言語表現である前記入力クエリを受け取る動作と、
最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先方式で前記ノードを調べる動作と、
前記入力クエリの前記中間言語表現の全体が調べられるまで前記識別されたコードパターンにタグ付けする動作と、
前記中間言語表現の先頭からタグ付けされたコードパターンを探索する動作と、
入力クエリの最適表現を形成するために改善されたコードパターンを用いて前記タグ付けされたコードパターンを調整する動作と
を実施するオプティマイザ
を備えたことを特徴とするコンピュータシステム。
【請求項９】
前記１つまたは複数の入力クエリは、１つまたは複数のＸＭＬクエリおよびＸＭＬビューを含むことを特徴とする請求項８に記載のシステム。
【請求項１０】
クエリ結果を形成する最適化後処理部分をさらに含み、
前記最適化表現がターゲットクエリを形成する１つまたは複数のターゲット表現に変換される１つまたは複数のターゲットジェネレータと、
クエリ先の１つまたは複数のデータソースと、
クエリ結果を生成するために前記ターゲットクエリが前記１つまたは複数のデータソースに対して実行される１つまたは複数の実行エンジンと
を含むことを特徴とする請求項８に記載のシステム。
【請求項１１】
入力クエリの最適表現を構築する方法であって、
各々がノード型を有するノードを含む中間言語表現である前記入力クエリを受け取るステップと、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べるステップと、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して検査済みコードパターンを比較するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンの１つまたは複数を調整するステップと
を含むことを特徴とする方法。
【請求項１２】
前記受け取るステップは、意味的中間言語表現を受け取るステップを含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記意味的表現は、ノードを含むグラフ構造を含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とする請求項１１に記載の方法。
【請求項１５】
入力クエリの最適表現を構築する方法を実施するコンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記方法は、
各々がノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べるステップと、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して検査済みコードパターンを比較するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンのうち１つまたは複数を調整するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項１６】
１つまたは複数の入力クエリのＸＭＬ中間言語表現の最適化表現を生成するコンピュータシステムであって、
１つまたは複数の入力クエリを受け取る１つまたは複数の入力装置、
各コンパイラが入力クエリの中間言語表現を生成する１つまたは複数の中間言語コンパイラ、
各中間言語表現を単一のＸＭＬ中間言語表現に結合する式アキュムレータ、および
各ノードがそれぞれのノード型を有するノードを含む中間言語表現である前記入力クエリを受け取る動作と、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べる動作と、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して前記検査済みコードパターンを比較する動作と、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンのうちの１つまたは複数を調整する動作と
を実施するオプティマイザ
を含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ソフトウェアクエリの最適化の分野に関し、より詳細には、ＸＭＬクエリ言語およびビュー定義言語に対する最適化に関する。
【背景技術】
【０００２】
言語最適化はあらゆるプログラマーの目標である。効率のよいコードは実行速度がより速く、コンピュータリソースの消費がより少なく、よりコンパクトである。これらの特性は、コンピュータのハードウェアおよびソフトウェアに優れた性能を望むコードのコンシューマにとって魅力的である。コード最適化という目標は、コードを使用してリレーショナルデータベースなどの大規模データベース全体にわたって問い合わせることができるクエリ言語アプリケーションを含む、大部分のアプリケーションで望ましいものである。クエリ実行用システムが、複数の言語を使用して複数のデータベースに問い合わせるタスクを引き受けたときに問題はより深刻になる。この状況では、効率のよいコード生成は、非最適化コードより速く、より一貫性の高いクエリ結果を返すことによって、そのクエリに益をもたらす。最適化が必要とされる一例は、ＸＳＬＴ、ＸＱｕｅｒｙ、ＸＰａｔｈなどのＸＭＬ関連言語クエリ、またはビュー定義言語が、ＳＱＬデータベース全体にわたるクエリ実行のためにシステムに入力され得るシステムでの場合である。そうしたシステムでは、オプティマイザの役割は、実行コードの効率を高めることにある。
【０００３】
ＸＭＬクエリの正規化および最適化には、少なくとも４つの障壁、すなわちノード識別、順序付け、副作用および構築の問題がある。データベースおよび関数型プログラミングの最適化で一般的な一技法は、置換を実施することによって変数を除去することである。しかし、置換を実施するときは、単純な置換でさえも適切に機能しないことがあるので、十分に注意する必要がある。
【０００４】
１つの問題は、多くのＸＭＬクエリ言語が、明示的または暗黙的に、ノード識別に依存していることである。例えば、以下のＸＱｕｅｒｙを考察する。  
let $a := <foo/>
return $a is $a
このＸＱｕｅｒｙは単一のＸＭＬ要素を構築し、次いで、それがそれ自体と同じ識別を有するかどうかテストする。このクエリは真を返すべきである。これを、置換（すなわち＄ａのあらゆるインスタンスをその値で置換する）から生じるはずのクエリと対比する。 
<foo/> is <foo/>
このクエリは２つの要素を構築し、その場合それらは相互に異なるため、クエリは偽を返す。この問題は、文書順序で暗黙的にソートし、または識別によって重複ノードを除去する演算子ではより明白になり得る。
【０００５】
正規化および最適化での別の問題は、ＸＭＬが順序付けされることである。この順序付けは文書インスタンス全体にわたって安定していることが望ましい。以下のコード移動技法の例を考察する。この例は、ループの内側に式（expression）を押し込むこと、またはそれらがループと無関係なときには、それらをループから引き出すことを含む。  
以下のクエリを想定する。  
for $i in $e1
where $condition1
return
for $j in $e2
where $condition2
return $k
典型的な書き換えは以下のようになる。
for $i in $el
for $j in $e2
where $condition1
and $condition2
return $k
この書き換えは、結果の順序付けおよび位置に悪影響を及ぼす。この書き換えは一見したところ正しく見えるが、その内部条件は、この書き換えで変更されているそのループ内の位置を参照することがある。式の順序を異なるようにすることになるどんな最適化も、その位置を保存する必要がないときにだけ適用すべきである。そうでない場合には、誤った書き換えが発生する。
【０００６】
プログラミング言語最適化で一般的な一技法は、一時的な式を、その結果が必要とされないときに除去することである。しかし、たとえ一時的なＸＭＬクエリ言語式の除去でさえ、副作用が全くないものとすることはできない。中には、ＸＱｕｅｒｙのｅｒｒｏｒ（）関数など、エラーで評価を終了させる式もある。ＸＳＬＴの<xsl:message/>演算子など、出力にメッセージを送る一時的な式もある。一部の一時的な式は、そのクエリ言語のセマンティクスがそれを許容する場合に限り除去され得る。２つの例として、以下でＸＱｕｅｒｙ  ｅｒｒｏｒ（）およびｆａｌｓｅ（）、ＸＳＬＴパス式を考察する。  
document('malformed.xml')//foo［false()］
これらの言語の厳密な実装では、オプティマイザが常にｆａｌｓｅ（）状態となる故に両式を除去することを望む場合であっても、両エラーがレポートされることを必要とすることがある。好都合なことに、ＸＱｕｅｒｙは、そのオペランドの１つがエラーになることがあるときでも、ＡＮＤ演算子が短絡することを許容する。ＸＳＬＴは、ｄｏｃｕｍｅｎｔ（）関数がそうしたエラーを処理しようとするときに空のリストを返すことを許容する。したがって、両式はコンパイル時に、空のリストに最適化され得る。例えば以下のようなＸＱｕｅｒｙ式を考察する。  
(<x dupe="1" dupe="2">can you get here?</x>)//text()
この例では、オプティマイザは無効な一時的要素を除去し、テキストノードだけを返そうとすると考えられる。また、これらのクエリが最適化されなかった場合、それらは実行時にエラーを生じることになるが、最適化されるとエラーが生じないこともあることもわかる。市販用実装形態では、他のプログラミング言語との相互動作性が最優先となる可能性がある。しかし、別のプログラミング言語で書かれた関数を呼び出すと、恐らく副作用を含む、未知の影響を生じることがあり、それが最適化への障壁となり得る。
【０００７】
別の問題は、ＸＭＬの不完全な構築が望ましくない副作用をもたらす可能性があることである。ＸＭＬ構築は、通常、その内容を複製することを意味し、このノード同一性に対する変更は書き換えおよび実行を通して保存される必要がある。以下のＸＱｕｅｒｙを考察する。  
foo((<x><y/></x>)//y)
このクエリは、単に＜ｙ／＞要素にすぎない、式（＜ｘ＞＜ｙ／＞＜／ｘ＞）／／ｙの結果を関数に渡すことによって関数ｆｏｏ（）を呼び出す。オプティマイザは、明らかに不要なＸＭＬ構築およびナビゲーションを除去し、選択された＜ｙ／＞要素だけを渡そうとする。しかし、ｆｏｏ（）が親ノードにアクセスしようとし、かつ関数
foo($y) ｛ $y/.. ｝
を定義した場合、およびオプティマイザが＜ｘ＞を除去した場合は、このクエリは誤った結果を生成することになる。構築の問題を回避するためには、外部関数に渡される構築済みＸＭＬの全体を保存することが望ましいと思われる。同様の問題は、
(<x:x xmlns:x="x"><y/></x>)//y
など、範囲内の名前空間宣言、および一時的なＸＭＬ式で見られることのある他のメタデータ命令でも発生する。ＸＳＬＴなどの言語では、この言語が合成的（compositional）ではないために構築の副作用はあまり問題にならないと考えられるが、そうした構築の問題は、ＸＱｕｅｒｙなどの最適化、または構築済みＸＭＬビューでのＸＭＬクエリ実施時に、著しく影響を及ぼす。
【０００８】
【非特許文献１】Grinev，他１名，“Towards an Exhaustive Set of Rewriting Rules for XQuery Optimization: BizQuery Experience”，［online］，The Institute for System Programming of the Russian Academy of Sciences，［2003年6月23日検索］，インターネット＜http://www.ispras.ru/~grinev/mypapers/rewriting-extended.pdf＞
【非特許文献２】Jason McHugh，他１名，“Query Optimization for XML”，（エディンバラ，スコットランド），Proceedings of the 25th VLDB Conference，1999年，p.315-326
【非特許文献３】YuqingWu，他２名，“Structural Join Order Selection for XML Query Optimization” ，［online］，University of Michigan Department of Electrical Engineering and Computer Science，［2003年6月23日検索］，インターネット＜http://www.eecs.umich.edu/~jignesh/publ/XML-opt.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、ＸＭＬオプティマイザが、誤った置換を回避し、最適化されたＸＭＬ式で順序が重要であるときには書き換えられた式の順序を変更する書き換えを回避し、一時的な式の除去および複数言語の使用による副作用を回避し、並びに構築の問題を回避すれば、有利なはずである。本発明は、前述した必要性に対応し、クエリを最適化するための他の利点も提供する様々なシステム、方法および技法を用いてそれらを解決する。
【課題を解決するための手段】
【００１０】
本発明は、ＸＭＬ入力クエリなどの入力クエリの最適化された中間言語表現を生成する、オプティマイザ／ノーマライザおよび関連する技法を対象とする。本発明は、独立型オプティマイザとしても、ＸＭＬクエリランタイムシステムなどを含む大規模なシステムの一部としても利用することができる。
【００１１】
本発明は、入力クエリを受け取り、最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先（left-depth first）方式で各ノードを調べ、その入力クエリの中間言語表現が完全に調べられるまで識別されたコードパターンにタグ付けし、中間言語表現の先頭からタグ付けされたコードパターンを探索し、入力クエリの最適表現を形成するために、改善されたコードパターンを用いてタグ付けされたコードパターンを調整することによって、入力クエリの最適表現を構築する第１の例示的方法を含む。オプティマイザ／ノーマライザへの入力は、コードパターンおよび各ノードがそれぞれのノード型を有するノードを含む中間言語表現に変換された入力クエリであると想定される。
【００１２】
入力クエリの最適表現を構築する第２の例示的方法は、入力クエリを受け取り、それぞれのノード型に関連するコードパターンを検査するための各ノードを調べ、非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して検査済みコードパターンを比較し、入力クエリの最適表現を形成するために、改善されたコードパターンを用いて非最適化コードパターンおよび検査済みコードパターンの１つまたは複数を調整することを含む。入力クエリは、この場合もやはり、各ノードがそれぞれのノード型を有するノードを含む中間言語表現である。
【００１３】
本発明は、ＸＭＬ中心の実行時クエリ処理方法を含む例示的システムで実施することができる。この方法は、複数のＸＭＬクエリを取り込んでそれらを中間言語表現に変換し、最適化を実施し、次いで、そのクエリを、データソース形式と互換性のある形にコンパイルし直すことを伴う。
【００１４】
前述の概要、ならびに以下の好ましい実施形態の詳細な説明は、添付の図面と併せて読めばよりよく理解されるものである。本発明を説明するために、図面に本発明の例示的構成を示すが、本発明は開示の具体的方法および手段に限定されるものではない。
【発明を実施するための最良の形態】
【００１５】
オプティマイザ／ノーマライザ概要
クエリオプティマイザ／ノーマライザの一例では、冗長な形を除去し、クエリ実行速度を向上させることによってクエリ効率を高める。ノーマライザ機能の一例では、冗長な形を除去し、したがって、バックエンドが処理するために準備する必要のあるクエリの種類の数を低減させることによって、バックエンドコンパイラの実装形態を簡単にする。それによってより優れたシステム性能が実現される。オプティマイザ／ノーマライザは独立型コンポーネントとして使用するように設計することも、より大規模なシステムの一部として使用するように設計することもできる。
【００１６】
最適化での誤った置換の問題は、ノード識別を考慮する際に正しくない置換またはその他の書き換えを実施しないことによって回避される。これは、クエリのノード指向の中間言語表現を入力として利用することによって実施される。したがって、ノード特性を最適化プロセスの一部として分析することができる。入力クエリの中間言語表現の一部の書き換えは、好ましくは、再順序付けがその中間表現のどの部分式にも影響を与えないときに限り実施される。式の順序は、入力クエリの曖昧でない中間言語表現の使用を通じて順序付けの影響を受けやすい式を明白に識別することによって影響を受けないことが望ましい。総じて、最適化エラーおよび関連する問題は、最適化障壁、明示的演算子および適切に作成された書き換え規則への十分な注意を組み合わせることによって回避することができる。
【００１７】
本発明は、コンピュータシステムにおいて１つまたは複数のハードウェア要素およびソフトウェア要素のセットで実装することができる。したがって、本発明を含むことのできるコンピュータシステムの一例を以下で説明する。
【００１８】
計算処理装置の例
図１および以下の説明は、本発明を実装することのできる適当な計算処理環境の簡単で一般的な説明を行うためのものである。ただし、本発明との関連での使用するために、ハンドヘルド、携帯用その他の計算処理装置およびあらゆる種類の計算処理オブジェクトが企図されていることを理解すべきである。したがって、以下では汎用コンピュータについて述べるが、これは一例にすぎず、本発明は、ネットワーク／バス相互インターオペラビリティおよびインタラクションを有するクライアントなど、他の計算処理装置を用いて実装することもできる。したがって、本発明は、クライアントリソースがほとんど関係しない、または最小限のクライアントリソースが関係する、ネットワーク接続され、ホスティングされたサービスの環境、例えば、クライアント装置が、単に、電気器具に配置されたオブジェクトなどのように、ネットワーク／バスや、その他の計算処理装置およびオブジェクトへのインターフェースとして働くだけのネットワーク化環境などで実装することもできる。本質的に、データを記憶することができ、またはそこからデータを取り出すことのできるどんな場所でも、本発明による動作に望ましい、または適した環境である。
【００１９】
必須ではないが、本発明は、装置またはオブジェクト用のサービスの開発者による使用のために、オペレーティングシステムを介して実装することができ、かつ／または本発明に従って動作するアプリケーションソフトウェアに組み込むこともできる。ソフトウェアは、クライアントワークステーション、サーバその他の装置など、１つまたは複数のコンピュータによって実行される、プログラムモジュールなど、コンピュータ実行可能命令の一般的状況で説明することができる。一般に、プログラムモジュールには、個々のタスクを実行し、または個々の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。通常は、プログラムモジュールの機能は、様々な実施形態で、所望に応じて組み合わせ、または分散させることができる。さらに、本発明を、他のコンピュータ構成を用いて実施することもできることを当分野の技術者は理解するであろう。本発明での使用に適すると考えられる他の公知の計算処理システム、環境および／または構成には、それだけに限らないが、パーソナルコンピュータ（ＰＣ）、現金自動預入支払機、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能家庭用電化製品、ネットワークＰＣ、電気器具、照明器具、環境制御要素、ミニコンピュータ、メインフレームコンピュータなどが含まれる。本発明は、通信ネットワーク／バスその他のデータ伝送媒体を介してリンクされたリモート処理装置によってタスクが実行される分散計算処理環境で実施することもできる。分散計算処理環境では、プログラムモジュールは、ローカルとリモート両方の、メモリ記憶装置を含むコンピュータ記憶媒体に位置することができ、クライアントノードもまた、サーバノードとして振舞うこともできる。
【００２０】
したがって、図１には本発明を実装することのできる適当な計算処理システム環境１００の一例を示すが、上記で明らかにしたように、この計算処理システム１００は、適当な計算処理環境の一例にすぎず、本発明の使用または機能の範囲についてのどんな限定も示唆するものではない。また、この計算処理環境１００は、例示的動作環境１００に示すコンポーネントのいずれか１つまたはその組み合わせに関連するどんな依存性も要件も持つものではないと解釈すべきである。
【００２１】
図１を参照すると、本発明を実装する例示的システムは、コンピュータシステム１１０の形で汎用計算処理装置を含む。コンピュータシステム１１０のコンポーネントには、それだけに限らないが、処理ユニット１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１が含まれ得る。システムバス１２１は、様々なバスアーキテクチャのいずれかを使用するメモリバスまたはメモリ制御機構、周辺機器バス、およびローカルバスを含むいくつかの種類のバス構造のいずれでもよい。例をあげると、そうしたアーキテクチャには、それだけに限らないが、ＩＳＡバス、ＭＣＡバス、拡張ＩＳＡ（ＥＩＳＡ）バス、ＶＥＳＡローカルバス、およびＰＣＩバス（メザニンバスともいう）が含まれる。
【００２２】
コンピュータシステム１１０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータシステム１１０からアクセスできる任意の使用可能媒体とすることができ、揮発性と不揮発性両方、取り外し可能と取り外し不能両方の媒体を含む。例をあげると、それだけに限らないが、コンピュータ可読媒体にはコンピュータ記憶媒体および通信媒体が含まれ得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータなどの情報の記憶のための任意の方法または技術で実装された、揮発性および不揮発性、取り外し可能および取り外し不能媒体が含まれる。コンピュータ記憶媒体には、それだけに限らないが、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的消去書込み可能読み取り専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリその他のメモリ技術、コンパクトディスク読み取り専用メモリ（ＣＤＲＯＭ）、書き換え可能コンパクトディスク（ＣＤＲＷ）、デジタル多用途ディスク（ＤＶＤ）その他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶その他の磁気記憶装置、または所望の情報の記憶に使用することができ、コンピュータシステム１１０からアクセスすることのできる他の任意の媒体が含まれる。
【００２３】
通信媒体は、通常、搬送波その他の搬送機構などの変調データ信号としてコンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータを実施し、任意の情報送達媒体を含む。「変調データ信号」という用語は、信号中に情報を符号化するようにその特性の１つまたは複数が設定または変更された信号を意味する。例をあげると、それだけに限らないが、通信媒体には、有線ネットワークや直接配線接続などの有線媒体、および音響、無線周波数、赤外線その他の無線媒体などの無線媒体が含まれる。また、上記のいずれかの組み合わせもコンピュータ可読媒体の範囲内に含むべきである。
【００２４】
システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性および／または不揮発性メモリの形でコンピュータ記憶媒体を含む。基本入出力システム１３３（ＢＩＯＳ）は、起動時などに、コンピュータシステム１１０内の要素間での情報転送を支援する基本ルーチンを含み、通常は、ＲＯＭ１３１に記憶される。ＲＡＭ１３２は、通常、処理ユニット１２０から直ちにアクセス可能であり、かつ／または現在それによって操作されているデータおよび／またはプログラムモジュールを含む。例をあげると、それだけに限らないが、図１にはオペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７が示されている。
【００２５】
コンピュータシステム１１０は、その他の取り外し可能／取り外し不能、揮発性／不揮発性コンピュータ記憶媒体を含むこともできる。例としてあげるにすぎないが、図１には、取り外し不能、不揮発性磁気媒体の読取りおよび書込みを行うハードディスクドライブ１４１、取り外し可能、不揮発性磁気ディスク１５２の読取りおよび書込みを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤその他の光媒体などの取り外し可能、不揮発性光ディスク１５６の読取りおよび書込みを行う光ディスクドライブ１５５が示されている。この例示的動作環境で使用することのできる他の取り外し可能／取り外し不能、揮発性／不揮発性コンピュータ記憶媒体には、それだけに限らないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭなどが含まれる。ハードディスクドライブ１４１は、通常、インターフェース１４０などの取り外し不能メモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常、インターフェース１５０などの取り外し可能メモリインターフェースによってシステムバス１２１に接続される。
【００２６】
図１に示す前述の各ドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータシステム１１０用のコンピュータ可読命令、データ構造、プログラムモジュールおよびその他のデータの記憶を提供する。図１では、例えば、ハードディスクドライブ１４１はオペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７を記憶するものとして示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでも、異なっていてもよい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７には、それらが少なくとも異なる複製であることを示すために、ここでは異なる番号が付されている。ユーザは、キーボード１６２、および、一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティング装置１６１を介してコンピュータシステム１１０にコマンドおよび情報を入力することができる。他の入力装置（図示せず）には、マイク、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナなどが含まれる。上記その他の入力装置は、しばしば、システムバス１２１に結合されたユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されるが、並列ポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースおよびバス構造によって接続されてもよい。システムバス１２１には、ビデオメモリ（図示せず）と交替でやりとりすることのできる、ビデオインターフェース１９０などのインターフェースを介してモニタ１９１または他の種類の表示装置を接続することもできる。モニタ１９１以外に、コンピュータシステムは、スピーカ１９７および印刷装置１９６など他の周辺出力装置を含むこともでき、出力周辺インターフェース１９５を介してそれらを接続することができる。
【００２７】
コンピュータシステム１１０は、リモートコンピュータ１８０など、１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク化または分散環境で動作することもできる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置またはその他一般のネットワークノードとすることができ、通常は、コンピュータシステム１１０に関して前述した要素の多くまたはすべてを含むが、図１ではメモリ記憶装置１８１だけが示されている。図１に示す論理接続はローカルエリアネットワーク（ＬＡＮ）１７１、広域ネットワーク（ＷＡＮ）１７３を含むが、他のネットワーク／バスを含むこともできる。そうしたネットワーク環境は、家庭、事務所、企業規模のコンピュータネットワーク、イントラネットおよびインターネットでは一般的である。
【００２８】
ＬＡＮネットワーク環境で使用されるときは、コンピュータシステム１１０は、ネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境で使用されるときは、コンピュータシステム１１０は、通常、インターネットなどのＷＡＮ１７３を介して通信を確立するモデム１７２またはその他の手段を含む。モデム１７２は、内蔵でも外付けでもよく、ユーザ入力インターフェース１６０、またはその他適当な機構によってシステムバス１２１に接続することができる。ネットワーク化環境では、コンピュータシステム１１０に関連して示したプログラムモジュール、またはその一部は、リモートのメモリ記憶装置に記憶することもできる。例をあげると、それだけに限らないが、図１にはリモートアプリケーションプログラム１８５がメモリ装置１８１上にあるものとして示されている。図示のネットワーク接続は例示的なものであり、コンピュータ間で通信リンクを確立する他の手段を使用することもできることが理解されるであろう。
【００２９】
パーソナルコンピューティングとインターネットのコンバージェンスに照らして様々な分散計算処理フレームワークが開発されており、また開発中である。個人もビジネスユーザも同様に、アプリケーションおよび計算処理装置用のシームレスに相互運用可能な、Ｗｅｂ対応のインターフェースを備え、計算処理活動をますますＷｅｂブラウザやネットワーク指向のものとしている。
【００３０】
例えば、米国ワシントン州９８０５２、レドモンド、ワンマクロソフトウェイのマイクロソフト社（Microsoft Corporation, One Microsoft Way, Redmond, Washington 98052）から入手可能なＭＩＣＲＯＳＯＦＴ（登録商標）．ＮＥＴ（商標）プラットフォームは、サーバ、Ｗｅｂベースのデータ記憶などの構成要素サービス、およびダウンロード可能なデバイスソフトウェアを含む。本明細書では例示的実施形態を計算処理装置上にあるソフトウェアとの関連で説明するが、本発明の１つまたは複数の部分を、オペレーティングシステム、アプリケーションプログラミングインターフェース（ＡＰＩ）、またはコプロセッサと表示装置と要求側オブジェクトのいずれかの間の「仲介者（middle man）」オブジェクトを介して実装し、それによって、本発明による動作を．ＮＥＴ（商標）言語およびサービスのすべてによって実施し、そこでサポートし、あるいはそれらを介してアクセスすることもでき、他の分散計算処理フレームワークでも同様である。
【００３１】
最適化の説明および本発明の例示的実施形態
ＸＭＬクエリでの効率低下の２つの主要な原因は、バッファリングと型変換である。バッファリングは、演算子をストリームすることができず、何らかのデータがメモリに大量にキャッシュされて、その演算子を評価するためにそれが１回または複数回トラバースされるときに発生する。これが発生すると、パイプライン処理が停止し、メモリの割り振りおよび複数の受け渡しが行われることがある。したがって、データを２回処理するクエリを、データを１回だけ処理するクエリにすることが、望ましい最適化である。
【００３２】
バッファリングは、主として、物理的クエリ計画の一側面であり、そのクエリをどのように実施するかに密接に結合されている。しかし、論理的クエリ計画には検出し、書き換えることのできるパターンが存在する。例えば、クエリsum($x)div count($x)は、avg($x)と等価とすることができる。前者の式は$xを２回評価することを必要とするが、後者はその計算を１回の受け渡しで実施することができる。
【００３３】
ＸＭＬでは、型変換は、一般に、文字列表現から機械型（整数など）にまたはその逆に移行することを伴う。リレーショナルデータベースは、従来方式では、そうしたクエリを適切には最適化しない。というのは、それらが、データが機械型としてすでに記憶されている関係ドメインでは、比較的まれであるためである。ＸＭＬクエリの実装では、特に関係データに対して、また通常のＸＭＬデータの場合でも、可能な限り多くの型変換および型テストを除去することが望ましいと考えられる。
【００３４】
例えば、クエリCustomer ［@CustomerID='ALFKI'］は、暗黙的に、CustomerIDノードを文字列に変換することを求めることができる。ノードがすでにｘｓ：ｓｔｒｉｎｇと類別されている場合は、そのノードの文字列値は依然として取り出すことができるが、変換は必要とされない。ノードが、nvarcharなどのＳＱＬ型を有するカラムにマッピングされる場合も、やはり、関係データからＸＭＬデータへの変換は必要とされない。CustomerIDが索引付けされていたとすると、これら２つの型変換を除去することによって、そのＳＱＬクエリ計画は索引走査から索引シークに移行される。この計画は、１０倍の性能向上を達成することができる。
【００３５】
これらの最適化は、一般に、性質上物理的なものである。不要なＳＱＬ／ＸＭＬ変換を除去することはできるが、論理的クエリ計画ですでに可能な最適化もある。一手法として、最適化プロセスの間に型を絞り込むことによって型変換および型テストを除去するものが考えられる。あるクエリに関する静的型情報をより正確に知り、理解するほど、より多くの演算子を静的に除去することができる。
【００３６】
本発明の一実施形態では、クエリ中で機能演算を識別するノードからなるグラフ構造を有する中間言語表現を利用する。したがって、それは、クエリの意味論的意味を表す。この中間言語はクエリ中間言語であり、ＱＩＬと呼ばれる。クエリ中間言語定義の一例は、ワシントン州レドモンドのマイクロソフト社に譲渡された、「QUERY INTERMEDIATE LANGUAGE METHOD AND SYSTEM」という名称の２００３年６月２３日に出願された米国特許出願の明細書に提供されている。
【００３７】
パターン検出を使用して、正規化および最適化の候補を識別する。そうした中間言語によって作成されたパターンは、恣意的複雑度を有するものではない。一般に、それらのパターンは、大部分が、浅いパターンであり、個々のノード型をルートとしており、すべてのバックエッジが知られている場所で発生するように制約される。したがって、この表現にパターンマッチアルゴリズムを容易に適応させることができる。
【００３８】
ＱＩＬと呼ばれるＸＭＬ中間言語は、ＸＭＬクエリまたはビューの一表現である。このクエリ中間言語は、あるＸＭＬクエリの意味の明示的表現である。このクエリ中間言語を、すべてのＸＭＬクエリおよびビュー言語コンパイラで共通の意味表現と見ることもできる。ＱＩＬは通常の抽象構文ツリー（ＡＳＴ）に類似するが、ＱＩＬが言語の構文ではなく、クエリのセマンティクス、あるいは意味を捉えるという点で異なる。別の違いは、ＱＩＬがグラフ構造であり、ＡＳＴのようなツリー構造ではない点である。
【００３９】
ＱＩＬは、様々な異なるターゲットデータソース（関係データや非関係データなど）にわたる、複数の異なるＸＭＬクエリ言語およびビュー定義言語（ＸＰａｔｈ、ＸＳＬＴ、ＸＱｕｅｒｙなど）の抽象化を可能にする。したがって、ＱＩＬは、互換性のあるＸＭＬ言語のすべてをサポートする共通構造を可能にする。あらゆる演算は明示的であり、しかも曖昧ではない。
【００４０】
ＱＩＬによって生成され、オプティマイザによって検出されるパターンは、ルートノード型でグループ化され、次いで、パターン識別および最適化実装のためのサブクラスの生成に使用される。それらのサブクラスは、ＱＩＬグラフ上で左深さ優先（すなわちボトムアップ）受け渡しを実施し、各パターンを順に所与のノード型に突き合わせしようとする。マッチするパターンがない場合は、そのノード（およびすでに調べたそのサブグラフ全体）を複製する。そうでない場合は、指示された最適化置換を実施する。
【００４１】
この手法の最悪の複雑度はＯ（ｇｎ２）であり、ただしｇは文法中のパターン数であり、ｎはグラフ中のノード数である。オプティマイザは、各パターンを突き合わせするために各ノードおよびすべての子孫を考察するが、実際には、各パターンは１レベルの深さしかないことが多く、そのためその平均時間は、より正確には、Ｏ（ｇｎ）に近似される。
【００４２】
図２に、本発明の諸側面を実施するシステムアーキテクチャの一例の構成図を示す。中間言語コンパイラおよびターゲット実行エンジンを含む、クエリランタイムアーキテクチャ２００を示す。このアーキテクチャは、複数のデータソース上でＸＭＬクエリのためにデータを受け取り、コンパイルし、解釈し、それにアクセスするために実装された基本的ブロックの例を示す。ＸＭＬまたはＸＭＬ関連の標準に適合する複数のフロントエンド言語コンパイラ２１０を実現することができる。元のまたは入力クエリは、図１に示すような複数の入力装置のいずれかから受け取られ、または入力されることができる。
【００４３】
図２に戻ると、フロントエンドコンパイラ２１０は、入力装置（図２には示さず）を介してＸＭＬクエリ、ＸＭＬビューまたはその他のＸＭＬ言語照会を受け取り、その入力クエリの複合の意味のコンパイル済みＸＭＬ中間言語表現２１５を生成することができる。フロントエンドコンパイラ２１０用の典型的な言語の種類には、ワールドワイドウェブコンソーシアム（Ｗ３Ｃ（登録商標））によって公開されている、ＸＰａｔｈ、ＸＭＬスタイルシート言語（ＸＳＬ）、ＸＳＬＴおよびＸＭＬクエリ言語（ＸＱｕｅｒｙ）の標準が含まれる。ＸＭＬビューコンパイラを使用することもでき、特に、ＸＱｕｅｒｙのＷ３Ｃ（登録商標）ＸＭＬ標準ビューを含むこともできる。クエリおよびビュー言語と複数のターゲットモデルとの間の中間言語抽象化により、仮想ＸＭＬデータのみならず、Ｍｉｃｒｏｓｏｆｔ（登録商標）．ＮＥＴ（商標）からのものなど、実ＸＭＬデータもデータソースとして使用できるようになる。
【００４４】
ＸＭＬ中間言語表現２１５は、クエリオプティマイザ／ノーマライザ２２０への入力である。オプティマイザの機能は、クエリ性能を向上させ、入力中間言語表現内の冗長な形を除去することである。オプティマイザは、最適化済みＸＭＬクエリ表現をバックエンドターゲットジェネレータ２３０に配信する前に、サイズを縮小し、ＸＭＬ中間言語表現の複雑度を低減する多数のアルゴリズムを実行することによってシステム性能を向上させるように働く。
【００４５】
多様な関連ターゲットクエリ言語実行エンジン２４０をサポートするための複数のバックエンドターゲットジェネレータ２３０を置くことができる。バックエンドターゲットジェネレータ２３０はそれぞれ、それらが、サポートされる各データソース内のデータのモデルに適合してデータソース上で効率よく機能するように構築することができる。例えば、ＳＱＬデータベースソース用のターゲットクエリ言語ジェネレータを、ＳＱＬデータベース管理システムを用いたリレーショナルデータベースへのクエリの際の効率のために最適化することができる。したがって、例えば、中間言語表現２１５を特定のデータソース２５０と互換性のあるターゲット機械語に変換するために、ターゲットクエリ言語ジェネレータ２３０ａを実行エンジン２４０ａと組み合わせることもできる。任意選択で、ターゲットジェネレータは、ＸＭＬ中間言語表現２１５を、例えばＭｉｃｒｏｓｏｆｔ（登録商標）中間言語（ＭＳＩＬ）など、別の中間言語に変換し、それによって、実行エンジンが、１つまたは複数のデータソース２５０に直接クエリを行えるようにすることもできる。
【００４６】
コンパイル済みクエリの実行に際して、実行エンジンは、普通、例えば、その後の処理、記憶、ユーザへの表示、あるいは後続のソフトウェアアプリケーションへの提供などに使用可能なクエリ結果２６０を生じる。ターゲットコンパイラ２３０および対応する実行エンジン２４０は、いくつか例をあげると、ＸＭＬやＳＱＬなどのクエリ言語を含むことができる。
【００４７】
このアーキテクチャの別の側面はデータの有用性のモジュール性である。例えば、最適化済みＸＭＬクエリ表現が生成される（例えば、ターゲットジェネレータ２３０への入力）点において、最適化済みＸＭＬクエリ中間言語表現自体が、別のシステムで使用でき、または遅延されたターゲットコンパイルに使用できるように、出力を生成することもできる。また、最適化済みＸＭＬクエリ中間言語自体を、最初に特定の非ＸＭＬ命令クエリに実際に変換せずに、直接実行することもできる。したがって、最適化済みＸＭＬクエリ中間言語表現を実行するように特に適合された実行エンジンを使用して、コンパイラなしで、１つまたは複数のデータソースにクエリを行うためにＸＭＬ中間言語を使用することもできる。システム出力での別のオプションとして、ターゲットコンパイラ出力を、別のシステムによるまたは別の非システムアプリケーションによる実行のための出力として使用することもできる。
【００４８】
図２の例示的アーキテクチャは、クエリ構築に際して、本質的に、高い柔軟性を有することに留意すべきである。このクエリアーキテクチャは、複数のクエリからなる最適化済みＸＭＬ中間言語を生成できるように、複数のクエリの入力を可能にする。さらに、複数のバックエンドターゲットコンパイラおよび実行エンジンを適切に使用して、異なるデータモデルのデータソースにクエリすることもできる。アーキテクチャ２００は、フロントエンドとバックエンドの順列数の低減も可能にする。図２には、Ｍ個のフロントエンドコンパイラとＮ個のバックエンドコンパイラが示されており、ＭおよびＮは整数である。普通、この組み合わせによって、合計Ｍ×Ｎ通りの可能なシステムパスが生じるはずである。しかし、共通の中間言語の利用により、順列の数は、有利にも、Ｍ＋Ｎ通りに低減される。
【００４９】
図３は、本発明による最適化の流れの一例を表す流れ図である。最初に、クエリの中間言語表現を受け取る（３１０）。この中間言語表現は、前述のクエリ中間言語とすることも、ＭＳＩＬなど他の何らかの中間言語とすることもできる。この中間言語は、グラフ構造またはノード構造のものであると想定する。次いで、プロセス３００は、ノード型およびコードパターンを判定するために中間言語内のノードを調べる（３２０）。ノード型およびコードパターンが識別されると、最適化できるパターンを識別するためにそれらのパターンを分析する（３３０）。この比較は、最適化の候補を識別することのできる事前に記憶されたノード型および／またはコードパターンのセットを比較することによって実施することができる。別法として、アルゴリズムをノード型識別と併せて用いることによって最適化のためのコードパターンを識別することもできる。
【００５０】
そのノード型の検出されたパターンを最適化できる場合は、置換によってそのコードパターンを最適化する（３４０）。あるいは、不要な反復が検出された場合は、その反復を結果として除去することのできる正規化を実施することもできる（３４０）。正規化または最適化の結果、変更済みおよび未変更のコードの各部分が収集（３６０）、集約される。
【００５１】
そのノード型の検出されたパターンが、ノード型またはコードパターンとマッチしないために最適化できない（３３０）場合は、その検査済みコードを次に受け渡して（３５０）そのコードが収集（３６０）されるようにする。
【００５２】
コードが収集される（３６０）と、プロセス３００は、その中間言語表現が正規化／最適化のために完全に調べられたかどうか判定する。そのコードが完全に調べられていない場合は、次のノードを調べ（３２０）、検査および最適化のプロセスを反復する。プロセス３００が中間言語表現ノードの検査を完了した場合は、集約されたコードが次に受け渡され、最適化済みクエリがもたらされる（３８０）。
【００５３】
図４は、最適化および正規化のために、図３のプロセスの流れの別法として利用することのできる例示的プロセス４００を示す流れ図である。最初に、最適化のための事前コンパイル済みパターン４０５をアクセス可能なメモリ記憶に記憶させることができる。次いで、プロセス４００は、中間言語表現を受け取る（４１０）ことができる。前述のように、この中間言語表現は、ＱＩＬ、ＭＳＩＬ、または他の何らかのグラフまたはノード型の表現とすることもできる。ここで、この中間言語表現は、グラフ４２０の下部から上に向かって調べられる。プロセス４００が各ノードを調べるにつれて、可能な正規化および最適化が発見され、属性でタグ付けされる（４３０）。それらの属性を使用してどのような正規化または最適化が望ましいかを識別する。
【００５４】
次いで、プロセス４００は、グラフ全体が調べられたかどうかチェックする（４４０）。プロセスが完了していない場合は、プロセス４００はグラフの上方に移動して（４４５）次のノードをテストし、可能な最適化を識別する（４３０）。
【００５５】
中間表現のグラフ全体をチェックするプロセスが完了した場合（４４０）は、プロセス４００はグラフ先頭に移動し、ノードにタグ付けされた属性を探索する（４５０）。タグ付けされた属性の中には、反復ノードなど正規化の属性のものもあれば、置換コードなど最適化のものもある。それらの属性は、必要とされる動作の種類（すなわち、冗長性削除、最適化置換など）を示すことができる。プロセス４００は、タグ付けされたノード位置において先頭から下に向かって、タグ付けされたノードでの最適化／正規化を実行する（４６０）。最適化の実装の実行の最後に、ノード型表現および最適化済みクエリ（４７０）結果からそのクエリ全体を再構築することができる。
【００５６】
基礎となる中間言語表現に対するクエリ書き換えを説明する注釈を設けると好都合である。書き換えは、関連するノード型に依存することがあり、時折、書き換えを実施するために、型または値に関する条件など、その他の条件を満たすことが望ましいこともある。本発明の実施形態では、好ましくは、ノード中心であるが、その他の条件を指定することもできる構文を使用する。
【００５７】
当分野の技術者であれば理解するであろうが、ノード名は、ＬＩＳＰ言語でのノードのように、括弧で括ることができる。あるノードに子があれば、その名前の後に続けることができる。したがって、（Ｘ）は単一ノードＸを示し、（ＸＹＺ）は２つの子ノード、ＹおよびＺを持つノードＸを示す。子の順序は有意である。ツリー表現の一例、１＋１＝２は以下のように書くことができる。  
(Eq (Plus (Integer 1) (Integer 1)) (Integer 2))
【００５８】
書き換えでは、置換構造は、マッチパターンの後に、それらを隔てるためのトークン＝＞を使用して書くことができる。全体規則の前には角括弧で括った名前も置かれる。この名前は記述的でよい。一実施形態では、コード最適化での柔軟性のために、そうした規則を選択的に有効または無効にすることができる。書き換え規則の一例として以下が考えられる。  
［EliminateOr］
(Or (True) (False)) => (True)
【００５９】
コードパターンは、パターンを任意のノードの種類にマッチさせることもできる。これはワイルドカードマッチ（*）を使用して示される。通常は、その前に変数（$variableName）およびコロン（:）を置くことによって、どんなパターンにもラベル付けすることができる。その場合その変数名を、マッチパターン中または置換中の他の所にあるノードの代わりに使用することができる。ラベルは、一般に、逆参照を表す唯一の方法を提供する。逆参照およびワイルドカードを含むグラフの一例として以下が考えられる。  
(Sort $i:(For (List)) (Desc (Negate $x:*))) => (Sort $i (Asc $x))
【００６０】
具体的な注釈を用いてその他の条件を表すこともできる。ノードパターンの後に波括弧に入れたコードを続けることもできる。このコードは範囲内にある任意の変数を参照することができる。コード条件を持つグラフの一例として以下が考えられる。  
(IsEmpty $x:* ｛ $x.IsEmpty ｝ ) => (True)
【００６１】
以下に、パターン文法の拡張ＢＮ記法（ＥＢＮＦ）の記述を示し、パターン文法を提示する。
P := Pattern*
Pattern := Descr Match '=>' Action
Descr := '［' Ident '］'
Action := Replace | Code
Code := '｛' (Code | ［^｛｝］)* '｝'
Match := (Label ':')? (Node | Wildcard | String | Number) Code?
Label := '$' Ident
Node := '(' Ident Match* ')'
Replace := Label | PatNode
PatNode := '(' Ident Action* ')'
Wildcard := '*'
Ident := ［_A-Za-z］ ［_A-Za-z0-9＼-］*
String := '"'［^"］* '"'
Number := ［0-9］+
【００６２】
図５は、式の書き換えによって中間言語コードの最適化が可能になる最適化の一例を表す。元のコード５１０はＸＭＬクエリのクエリ中間言語表現の一実施形態である。結果として生じる最適化５２０は、特定の部分が書き換えられた同じコードである。例えば、中間言語表現５１０の点線を付した部分５１５は、最適化された形５２０に変換することができる。これらの最適化は、書き換え５２０中の点線を付した挿入部５２５であるとみなすことができる。
【００６３】
通常は、図５に示すような書き換えは一度には実施されず、それぞれがグラフの一部を操作するより小さい書き換えに分割される。図６に示すように、これらのより小さい書き換えは、好ましくは、所望の全体的効果を生み出すように段階的に実施される。
【００６４】
図６に、段階的に行われる一連の書き換えの例を表す。元のテキスト６１０の第１の部分を、以下の規則で示す親の除去による変換６１２を使用した最適化６１５として書き換えることができる。  
［EliminateParent］
(Parent (For (Content $x:*))) => $x
【００６５】
次いで、中間コード表現の次の部分６２０を、以下の規則で示すタプルの除去による変換６２２を使用した最適化６２５として書き換えることができる。  
［EliminateTuple］
(Tuple $i: (For $x:*) (True) $j:*) ｛ $i == $j ｝ => $x
【００６６】
書き換えられたコード６３０をさらに処理すると、以下の規則で示すループ不変コード移動による変換６３２を使用した書き換え６３５が生じる。  
［IntroduceNTimes］
(Tuple $i:* $w:* $r:*) ｛ !DependsOn($r, $i) ｝ 
=> (NTimes $r (Length (Tuple $i $w $i)))
【００６７】
その結果生じる書き換えをクエリコード６４０に挿入することができ、以下の規則で示すタプル書き換えによる変換６４２を使用してさらに書き換える（６４５）ことができる。  
［EliminateNTimes］
(DocOrderDistinct $t:(Tuple * * *))
=> ｛
QilTuple last = $t.LastTuple;
if (last.Retum.Type == QilNodeType.NTimes) ｛
QilBinary ntimes = (QilBinary)last.Retun;
QilList list = f.List();
list.Type = f.TypeFactory.Sequence(QilCardinality.Zero, ntimes.Type);
last.Return = Replace($0.EliminateNTimes, ntimes,
f.Conditional(f.Gt(ntimes.Right, f.Int32(0)), ntimes.Left, list));
｝
｝
【００６８】
その結果生じるコードの構造を、元の中間表現６５０に挿入するときに、以下の規則で示す論理的書き換えによる変換６５２によってさらに最適化（６５５）することができる。  
［IntroduceExists］
(Gt (Length $x:*) (LiteralInt32 0)) => (Not (IsEmpty $x))
【００６９】
全体の結果コード６６０のさらなる書き換えを、以下の規則で示すタプル書き換えの変換６６２によって最適化（６６５）することができる。  
［FoldTupleConditional)
(Tuple $i:* $w:* (Conditional $cond:* $return:* $list:(List)
｛ $list.QilType.IsEmpty ｝))
=> (Tuple $i (And $w $cond) $return)
【００７０】
この結果６６５を図５の元の中間言語クエリ５１０に挿入すると、図５の最適化された中間コード５２０に示す最適化が結果として生じる。したがって、本発明の最適化プロセスでは、複数の書き換えを使用することができる。
【００７１】
最適化および正規化の説明
最適化は、通常、局所的最適化または大域的最適化に分類される。定数畳み込みなどの局所的最適化は、グラフの小さな接続された領域を調べることによって実施される。不要コードの除去などの大域的最適化は、グラフ全体を調べることによって実施される。本発明の諸側面に従って実施される最適化の例を以下に要約する。  
定数畳み込み
論理的書き換え
基本パス書き換え（子、属性）
その他のパス書き換え（ルート、親、ノード自体、子孫など）
ループ不変コード移動
タプル書き換え
位置書き換え
射影書き換え
タプルおよびリスト交換
ベンチマーク（ＸＳＬＴ、ＸＭａｒｋなど）
関数境界にまたがる複合
型畳み込み
関数インライン化
共通部分式の除去
不要な関数の除去
ソートの除去／グループ化
【００７２】
実施された局所的正規化は、いくつかの異なるカテゴリにグループ化することができる。それらは、定数畳み込み、交換、パス書き換え、共通部分式の除去、関数インライン化およびその他の正規化である。最適化規則および技法のサンプル例を添付の付録Ｉに示す。
【００７３】
定数畳み込みによる最適化
定数畳み込みには、特定のコンパイル時の定数の除去することを含む。これらの最適化は、クエリサイズを縮小し、生成されるコードのサイズを縮小し、ループ状況での性能に大幅に影響を与えることができる。定数畳み込みパターンは、オプティマイザによって実施されるパターンの大部分を構成する。
【００７４】
論理的書き換えによる最適化
書き換えの中には正確には定数を畳み込むのではなく、式の論理的複雑度を低減させるものがある。ＳＱＬに直接書き直すことができない２つの論理式の比較など、不規則な形を規則的な形に変換するものもある。そうした規則的な形は、ＳＱＬに直接書き直すことのできる論理式で論理演算を行う。
【００７５】
基本パス書き換え（子、属性）による最適化
ナビゲーション最適化は、クエリ性能の一因となり得る。というのは、ＸＱｕｅｒｙが合成的である（すなわち、他のＸＱｕｅｒｙ式へのナビゲーションをサポートする）からである。ＱＩＬなど中間言語中のパスは、一様に単一の演算子では表されない。したがって、パス書き換えは、例えば、EliminateNameOfといった、定数畳み込みパターンなどの多くのより小さい書き換えで構成することができる。さらに、一部のパス書き換えには、ElementCtorやAttributeCtorなどの構成演算子を用いてContentやAttributeなどのナビゲーション演算子を畳み込むことを含む。
【００７６】
ループ不変コード移動による最適化
ループ不変コード移動は、ループ時に変化しない（すなわちループ不変の）ループ中で行われる計算を計算から除外（すなわちコード移動）することのできる、一般的な最適化技法である。この方法では、計算は、ループの反復回数分ではなく、１回だけ実施される。
【００７７】
交換による最適化
交換は、コレクションの反復や反復の反復を解くことを伴う書き換えのクラスである。そうした書き換えは、一般に、ＡＢ＝＞ｆ（Ｂ）ｇ（Ａ）の形の交換である。すなわち、ＡのＢへの適用は、ＢのＡへの適用、あるいはＢのＡの何らかの関数への適用、もしくはＢの各メンバに順に適用されるＡのリストに書き換えられる。交換パターンの中には、複雑すぎてパターン言語を用いて完全に表現できないものもある。したがって、それらのパターンは、普通、その後にその置換を実施するコード動作が続くマッチパターンをもつことができる。
【００７８】
タプル書き換え
ＱＩＬでは、タプルおよびフィルタノード型（および既存のタプルノード型）は特別な役割を担い、したがって、それらに関連する、他のどんなカテゴリにも分類されない特別な書き換えを持つ。
【００７９】
位置書き換え
本明細書で前述したように、位置を保持することは最適化への障壁となることがある。したがって、位置演算子を除去することは非常に価値のある最適化である。また、位置演算子はある種の制約条件を満たす。例えば、それは必ず少なくとも１であり、多くともそのセットの長さである。さらに、位置を使用するある種の複雑なパターンは、それを保持するようにさらに書き換えることもできる。
【００８０】
ベンチマーク
ベンチマークは、周知のように、現実の諸条件を表さないが、オプティマイザにとっては、これは大きな問題ではない。すなわち、ベンチマークはやはり最適化の機会を表す。
【００８１】
ソート除去／グループ化
ソートパターンには主に２種類ある。一方の種類のソートパターンは、例えば、文書順序を、すでに文書順序中にある式に適用するなどの不要なソートを除去する。他方のソートパターンは、複数の受け渡しを使用するバックエンドコンパイラによって実行され得るグループ化パターンを認識することができる。
【００８２】
前述のように、本発明の例示的実施形態を、様々な計算処理装置およびソフトウェアアーキテクチャとの関連で説明してきたが、その基礎をなす概念は、コードオプティマイザを実装することが望ましいどんな計算処理装置またはシステムにも適用することができる。したがって、本発明の方法およびシステムは、様々なアプリケーションおよび装置に適用することができる。本明細書では、様々な選択を表すものとして、例示的プログラミング言語、名称および実例が選択されているが、それらの言語、名称および実例は、限定のためのものではない。本発明によって実現されるものと同じ、類似の、または等価のシステムおよび方法を実現するオブジェクトコードを提供する多数の方法があることを、当分野の技術者は理解するであろう。
【００８３】
本明細書で述べた様々な技法は、ハードウェアまたはソフトウェアとして、または適切な場合には、両者の組み合わせとして実装することができる。したがって、本発明の方法および装置、またはそのある種の側面または部分は、フロッピー（登録商標）ディスケット、ＣＤ−ＲＯＭ、ハードドライブまたはその他任意の機械可読記憶媒体などの有形の媒体で実施されたプログラムコード（すなわち命令）の形を取ることができ、そのプログラムコードが、コンピュータなどのマシンにロードされ、それによって実行されると、そのマシンは本発明を実施する装置となる。プログラム可能コンピュータ上でのプログラムコード実行の場合には、その計算処理装置は、一般に、プロセッサ、プロセッサによる読取りが可能な（揮発性および不揮発性メモリおよび／または記憶素子を含む）記憶媒体、少なくとも１つの入力装置、および少なくとも１つの出力装置を含む。本発明の信号処理サービスを、例えば、データ処理ＡＰＩなどの使用によって利用することのできる１つまたは複数のプログラムは、好ましくは、コンピュータとやりとりするために、高水準手続き型言語またはオブジェクト指向プログラミング言語で実装される。ただし、そのまたはそれらのプログラムは、必要に応じて、アセンブリ言語または機械語で実装することもできる。いずれにしても、その言語は、コンパイル済みまたは解釈済み言語とすることができ、ハードウェア実装形態と組み合わせることができる。
【００８４】
本発明の方法および装置は、電気配線またはケーブル、光ファイバ、その他任意の伝送形態など、何らかの伝送媒体を介して伝送されるプログラムコードの形で実施された通信を介して実施することもでき、そのプログラムコードが、ＥＰＲＯＭ、ゲートアレイ、プログラム可能論理デバイス（ＰＬＤ）、クライアントコンピュータ、ビデオ記録装置などのマシンに受け取られ、それにロードされ、それによって実行されると、上記の例示的実施形態で述べたような信号処理機能を有する受け取り側マシンは、本発明を実施する装置となる。汎用プロセッサ上で実装されると、このプログラムコードはプロセッサと相まって、本発明の機能を呼び出すように動作する独自の装置を提供する。また、本発明と一緒に使用されるどんな記憶技法も、必ず、ハードウェアとソフトウェアの組み合わせとすることができる。
【００８５】
以上、本発明を様々な形態の好ましい実施形態との関連で説明してきたが、他の類似の実施形態を使用することもでき、あるいは、本発明から逸脱することなく本発明と同じ機能を実施するために、前述の実施形態に改変および付加を行うこともできることを理解すべきである。さらに、特に無線ネットワーク接続装置の数が急増し続けているため、ハンドヘルド装置オペレーティングシステムやその他のアプリケーション別オペレーティングシステムを含めて、様々なコンピュータプラットフォームが企図されていることを強調しておく必要がある。したがって、本発明は、どんな単一の実施形態にも限るものではなく、添付の特許請求の範囲による幅と範囲で解釈すべきである。
【００８６】
付録Ｉ
以下に添付資料には、本発明による例示的実施形態の一部とすることのできる最適化の実例が含まれる。このリストは例示のためのものにすぎず、本発明の範囲および要旨に含まれるさらに多くの例が可能である。
【００８７】
定数畳み込み型最適化の例
論理演算子のための定数畳み込みパターン：
【００８８】
【表１】
2005018767.tif 000003
【００８９】
【表２】
2005018767.tif 000004
【００９０】
コレクション演算子のための定数畳み込みパターン：
【００９１】
【表３】
2005018767.tif 000005
【００９２】
【表４】
2005018767.tif 000006
【００９３】
算術演算子のための定数畳み込みパターン：
【００９４】
【表５】
2005018767.tif 000007
【００９５】
【表６】
2005018767.tif 000008
【００９６】
【表７】
2005018767.tif 000009
【００９７】
【表８】
2005018767.tif 000010
【００９８】
文字列演算子のための定数畳み込みパターン：
【００９９】
【表９】
2005018767.tif 000011
【０１００】
値比較演算子のための定数畳み込みパターン：
【０１０１】
【表１０】
2005018767.tif 000012
【０１０２】
【表１１】
2005018767.tif 000013
【０１０３】
【表１２】
2005018767.tif 000014
【０１０４】
【表１３】
2005018767.tif 000015
【０１０５】
ＸＭＬノード特性のための定数畳み込みパターン：
【０１０６】
【表１４】
2005018767.tif 000016
【０１０７】
【表１５】
2005018767.tif 000017
【０１０８】
【表１６】
2005018767.tif 000018
【０１０９】
【表１７】
2005018767.tif 000019
【０１１０】
【表１８】
2005018767.tif 000020
【０１１１】
型演算子のための定数畳み込みパターン：
【０１１２】
【表１９】
2005018767.tif 000021
【０１１３】
ＸＰａｔｈ演算子のための定数畳み込みパターン：
【０１１４】
【表２０】
2005018767.tif 000022
【０１１５】
【表２１】
2005018767.tif 000023
【０１１６】
論理的書き換えのパターン：
【０１１７】
【表２２】
2005018767.tif 000024
【０１１８】
【表２３】
2005018767.tif 000025
【０１１９】
【表２４】
2005018767.tif 000026
【０１２０】
基本パス書き換えのパターン：
【０１２１】
【表２５】
2005018767.tif 000027
【０１２２】
【表２６】
2005018767.tif 000028
【０１２３】
その他のパス書き換えのパターン：
【０１２４】
【表２７】
2005018767.tif 000029
【０１２５】
ループ不変書き換えのパターン：
【０１２６】
【表２８】
2005018767.tif 000030
【０１２７】
【表２９】
2005018767.tif 000031
【０１２８】
タプル書き換えのパターン：
【０１２９】
【表３０】
2005018767.tif 000032
【０１３０】
【表３１】
2005018767.tif 000033
【０１３１】
【表３２】
2005018767.tif 000034
【０１３２】
位置書き換えのパターン：
【０１３３】
【表３３】
2005018767.tif 000035
【０１３４】
交換パターン：
【０１３５】
【表３４】
2005018767.tif 000036
【０１３６】
【表３５】
2005018767.tif 000037
【０１３７】
【表３６】
2005018767.tif 000038
【０１３８】
【表３７】
2005018767.tif 000039
【０１３９】
型畳み込みパターン：
【０１４０】
【表３８】
2005018767.tif 000040
【０１４１】
ソート除去／グループ化のパターン：
【０１４２】
【表３９】
2005018767.tif 000041
【０１４３】
【表４０】
2005018767.tif 000042
【図面の簡単な説明】
【０１４４】
【図１】本発明の諸側面を実装することのできる計算処理環境の一例を示す構成図である。
【図２】本発明の諸側面を実装することのできるアーキテクチャの一例を示す構成図である。
【図３】本発明の最適化方法の実施形態を示す流れ図である。
【図４】本発明の最適化方法の別の実施形態を示す流れ図である。
【図５】本発明の実施形態に対応する中間言語最適化の一例を示す図である。
【図６】本発明の実施形態に対応する中間言語の一例の区分的最適化を示す図である。
【符号の説明】
【０１４５】
１００  計算処理環境
１２０  処理ユニット
１２１  システムバス
１３０  システムメモリ
１３４，１４４  オペレーティングシステム
１３５，１４５  アプリケーションプログラム
１３６，１４６  その他のプログラムモジュール
１３７,１４７  プログラムデータ
１４０  取り外し不能不揮発性メモリインターフェース
１５０  取り外し可能不揮発性メモリインターフェース
１６０  ユーザ入力インターフェース
１６１  マウス
１６２  キーボード
１７０  ネットワークインターフェース
１７１  ローカルエリアネットワーク
１７２  モデム
１７３  広域ネットワーク
１８０  リモートコンピュータ
１８５  リモートアプリケーションプログラム
１９０  ビデオインターフェース
１９１  モニタ
１９５  出力周辺インターフェース
１９６  印刷装置
１９７  スピーカ
２１０  ＸＭＬ言語コンパイラ
２１５  ＸＭＬ中間言語表現
２２０  オプティマイザ／ノーマライザ
２３０  ターゲットジェネレータ
２４０  実行エンジン
２５０  データソース
２６０  クエリ結果
【図１】
2005018767.tif 000043
【図２】
2005018767.tif 000044
【図３】
2005018767.tif 000045
【図４】
2005018767.tif 000046
【図５】
2005018767.tif 000047
【図６】
2005018767.tif 000048