【手続補正書】
【提出日】平成19年6月21日(2007.6.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力クエリの最適表現を構築する方法であって、
各々がノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
最適化の対象であるノード型を識別するために左深さ優先方式で前記ノードを調べるステップと、
識別されたノード型に対応するノードにタグ付けするステップと、
前記入力クエリの前記中間言語表現の全体が調べられるまで上方の次のノードに移動するステップと、
前記中間言語表現の先頭からタグ付けされたノードを探索し、最適化される関連コードパターンを識別するステップと、
前記入力クエリの最適表現を形成するために、改善されたコードパターンを用いて識別されたコードパターンを調整するステップと
を含み、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とする方法。
【請求項２】
前記受け取るステップは意味的中間言語表現を受け取るステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記意味的表現はノードを含むグラフ構造を含むことを特徴とする請求項２に記載の方法。
【請求項４】
入力クエリの最適表現を構築する方法をコンピュータに実施させるコンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記方法は、
コードパターンおよび各々がコードパターンおよびノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先方式で前記ノードを調べるステップと、
前記入力クエリの前記中間言語表現の全体が調べられるまで識別されたコードパターンにタグ付けするステップと、
前記中間言語表現の先頭からタグ付けされたコードパターンを探索するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記タグ付けされたコードパターンを調整するステップと
を含み、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とするコンピュータ可読媒体。
【請求項５】
１つまたは複数の入力クエリのＸＭＬ中間言語表現の最適化表現を生成するコンピュータシステムであって、
１つまたは複数の入力クエリを受け取る１つまたは複数の入力装置、
各コンパイラが入力クエリの中間言語表現を生成する１つまたは複数の中間言語コンパイラ、
各中間言語表現を単一のＸＭＬ中間言語表現に結合する式アキュムレータ、および
コードパターンおよび各々がノード型を有するノードを含む中間言語表現である前記入力クエリを受け取る動作と、
最適化の対象であるコードパターンおよびノード型を識別するために左深さ優先方式で前記ノードを調べる動作と、
前記入力クエリの前記中間言語表現の全体が調べられるまで前記識別されたコードパターンにタグ付けする動作と、
前記中間言語表現の先頭からタグ付けされたコードパターンを探索する動作と、
入力クエリの最適表現を形成するために改善されたコードパターンを用いて前記タグ付けされたコードパターンを調整する動作と
を実施するオプティマイザ
を備え、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とするコンピュータシステム。
【請求項６】
前記１つまたは複数の入力クエリは、１つまたは複数のＸＭＬクエリおよびＸＭＬビューを含むことを特徴とする請求項５に記載のシステム。
【請求項７】
クエリ結果を形成する最適化後処理部分をさらに含み、
前記最適化表現がターゲットクエリを形成する１つまたは複数のターゲット表現に変換される１つまたは複数のターゲットジェネレータと、
クエリ先の１つまたは複数のデータソースと、
クエリ結果を生成するために前記ターゲットクエリが前記１つまたは複数のデータソースに対して実行される１つまたは複数の実行エンジンと
を含むことを特徴とする請求項５に記載のシステム。
【請求項８】
入力クエリの最適表現を構築する方法であって、
各々がノード型を有するノードを含む中間言語表現である前記入力クエリを受け取るステップと、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べるステップと、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して検査済みコードパターンを比較するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンの１つまたは複数を調整するステップと
を含み、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とする方法。
【請求項９】
前記受け取るステップは、意味的中間言語表現を受け取るステップを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記意味的表現は、ノードを含むグラフ構造を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
入力クエリの最適表現を構築する方法を実施するコンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記方法は、
各々がノード型を有するノードを含む中間言語表現である入力クエリを受け取るステップと、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べるステップと、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して検査済みコードパターンを比較するステップと、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンのうち１つまたは複数を調整するステップと
を含み、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とするコンピュータ可読媒体。
【請求項１２】
１つまたは複数の入力クエリのＸＭＬ中間言語表現の最適化表現を生成するコンピュータシステムであって、
１つまたは複数の入力クエリを受け取る１つまたは複数の入力装置、
各コンパイラが入力クエリの中間言語表現を生成する１つまたは複数の中間言語コンパイラ、
各中間言語表現を単一のＸＭＬ中間言語表現に結合する式アキュムレータ、および
各ノードがそれぞれのノード型を有するノードを含む中間言語表現である前記入力クエリを受け取る動作と、
それぞれのノード型に関連するコードパターンを検査するために前記ノードを調べる動作と、
非最適化コードパターンを検出するためにパターンマッチアルゴリズムを使用して前記検査済みコードパターンを比較する動作と、
入力クエリの最適表現を形成するために、改善されたコードパターンを用いて前記非最適化コードパターンおよび前記検査済みコードパターンのうちの１つまたは複数を調整する動作と
を実施するオプティマイザ
を含み、
前記改善されたコードパターンは、定数畳み込み、論理的書き換え、パス書き換え、ループ不変コード書き換え、タプル書き換え、位置書き換え、交換、インライン化およびソート除去のうち少なくとも１つを含む１つまたは複数の変換を使用して生成されることを特徴とするシステム。