(57)【要約】データの記憶及びデータへのアクセスを行うためのシステム及び方法。照会言語ステートメントが、複数のデータセットを参照することができ、データセット間の複数の代数的関係を、照会言語ステートメントから組み立てることができる。代数的関係を使用して、新しいデータセットを定義すると共に、データセットへのアクセスを最適化することができる。代数的関係の記憶を時間と共に蓄積することができる。代替の代数的関数の集まりを生成し、評価して、要求データセットを計算し提供するに当たって使用するために最適な最適化代数的関係の集まりを決定することができる。最適化は、記憶装置から基礎データセットを検索するのではなく、代数的関係を使用して実行することができる。その結果、最適化をプロセッサ速度で実行して、より低速の記憶装置からデータを検索するために要する時間量を最小化することができる。【特許請求の範囲】
【請求項１】
照会言語ステートメントから代数的関係を確立するための方法であって、
データセット間の代数的関係を記憶する関係ストアを提供することと、
複数のデータセットを参照する照会言語ステートメントを受け取ることと、
前記照会言語ステートメントにおいて指定された前記データセットを参照する複数の代数的関係を組み立てることと、
前記複数の代数的関係を前記関係ストアに記憶することと、
を含む方法。
【請求項２】
前記照会言語ステートメントにおいて指定される前記データセットのうちの少なくとも１つを参照する代数的関係を組み立てることにより、少なくとも１つの新しいデータセットを定義することと、
前記新しいデータセットの前記代数的関係を前記関係ストアに記憶することと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記照会言語ステートメントにおいて指定される前記データセットは、少なくとも１つの明示的なデータセットを含み、前記方法は、
前記データセットに関する情報を記憶するデータセット情報ストアを提供することと、
前記明示的なデータセットにデータセット識別子を関連付けることと、
前記データセット識別子を前記データセット情報ストアに記憶することと、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記データセットのうちの少なくともいくつかを記憶するためのデータストアをさらに含み、前記照会言語ステートメントにおいて指定される前記データセットのうちの少なくとも１つは、前記照会言語ステートメントの受け取り時に前記データストアに記憶されていない、請求項１に記載の方法。
【請求項５】
前記データセットに関する情報を記憶するデータセット情報ストアを提供することをさらに含み、前記データセットに関する情報が前記データセット情報ストアに追加された時間を示す時間的情報が、前記データセット情報ストア内の各データセットに関連付けられる、請求項１に記載の方法。
【請求項６】
前記データセットに関する情報を記憶するデータセット情報ストアを提供することをさらに含み、前記データセット情報ストアは、当該データ情報ストア内の各データセットに関連付けられた一意の識別子及び外部識別子を含み、前記外部識別子は、前記データセットのうちの少なくともいくつかに対して同じである、請求項１に記載の方法。
【請求項７】
前記データセット情報ストアは、当該データ情報ストア内の各データセットに関連付けられた一意の識別子及び外部識別子を含み、前記外部識別子は、前記データセットのうちの少なくともいくつかに対して同じである、請求項５に記載の方法。
【請求項８】
指定された時間よりも前の時間的情報に関連付けられたデータセットを前記データセット情報ストアから除去することにより、前記データセット情報ストアを時間的に再定義することをさらに含む、請求項５に記載の方法。
【請求項９】
前記データセット情報ストアから除去された前記データセットを参照する代数的関係を、前記関係ストアから除去することをさらに含む、請求項８に記載の方法。
【請求項１０】
前記データセットのうちの少なくともいくつかを記憶するデータストアをさらに備え、前記データセット情報ストアは、前記関係ストア内の代数的関係によって定義され、前記データストア内に記憶されていない少なくとも１つのデータセットに関する情報を含む、請求項１に記載の方法。
【請求項１１】
前記データセットのうちの少なくともいくつかを記憶するデータストアをさらに備え、前記データセット情報ストアは、前記データセットストアに記憶されておらず、前記指定された時間よりも前の時間的情報を有するデータセットを参照する前記関係ストア内の代数的関係によって定義される少なくとも１つの実現化されていないデータセットに関する情報を含み、前記データセット情報ストアを時間的に再定義するステップは、前記指定された時間よりも前の時間的情報を有する前記データセットを前記データセット情報ストアから除去する前に、前記実現化されていないデータセットを前記データセットストアに記憶することをさらに含む、請求項９に記載の方法。
【請求項１２】
前記照会言語ステートメントから組み立てられた前記複数の代数的関係は、単一の演算子及び１〜３の範囲内のいくつかのオペランドを有する、請求項１に記載の方法。
【請求項１３】
前記新しいデータセットの前記代数的関係は、単一の演算子及び１〜３の範囲内のいくつかのオペランドを有する、請求項２に記載の方法。
【請求項１４】
前記照会言語ステートメントは、関係データモデルに基づく、請求項１に記載の方法。
【請求項１５】
前記照会言語ステートメントは、構造化照会言語（ＳＱＬ）フォーマットで受け取られる、請求項１に記載の方法。
【請求項１６】
前記照会言語ステートメントは、マークアップ言語モデルに基づく、請求項１に記載の方法。
【請求項１７】
前記照会言語ステートメントは、ＸＱｕｅｒｙフォーマットで受け取られる、請求項１に記載の方法。
【請求項１８】
前記照会言語ステートメントは、提供対象のデータセットを要求し、前記方法は、前記照会言語ステートメントから組み立てられる前記複数の代数的関係のうちの少なくともいくつかを使用して、前記要求データセットを提供することをさらに含む、請求項１に記載の方法。
【請求項１９】
前記照会言語ステートメントは、提供対象のデータセットを要求し、前記関係ストアは、前記照会言語ステートメントから組み立てられないデータセットの他の代数的関係を含み、前記方法は、前記他の代数的関係のうちの少なくともいくつかを使用して、前記要求データセットを提供することをさらに含む、請求項１に記載の方法。
【請求項２０】
前記照会言語ステートメントは、提供対象のデータセットを要求し、前記関係ストアは、前記照会言語ステートメントから組み立てられないデータセットの他の代数的関係を含み、前記方法は、前記他の代数的関係のうちの少なくともいくつかを使用して、前記要求データセットを提供することをさらに含む、請求項１８に記載の方法。
【請求項２１】
前記照会言語ステートメントは、提供対象のデータセットを要求し、前記方法は、
前記要求データセットに等しい結果を定義する代数的関係の複数の集まりを提供することと、
最適化基準を適用して、前記代数的関係の集まりのうちの１つを選択することと、
前記選択された代数的関係の集まりを使用して、前記要求データセットを提供することと、
をさらに含む、請求項１に記載の方法。
【請求項２２】
前記要求データセットに等しい結果を定義する代数的関係の複数の集まりを提供することと、
最適化基準を適用して、前記代数的関係の集まりのうちの１つを選択することと、
前記選択された代数的関係の集まりを使用して、前記要求データセットを提供することと、
をさらに含む、請求項２０に記載の方法。
【請求項２３】
代数的関係の各集まりのそれぞれを、ツリーデータ構造で記憶する、ことをさらに含む、請求項２１に記載の方法。
【請求項２４】
前記選択された集まりからの前記代数的関係を、並列処理のための処理リソースに割り当てることをさらに含む、請求項２１に記載の方法。
【請求項２５】
前記最適化基準は、コストアルゴリズムを含む、請求項２１に記載の方法。
【請求項２６】
前記最適化基準は、コストアルゴリズムを含み、前記選択される代数的関係の集まりは、前記コストアルゴリズムによる最小コストを有する、請求項２２に記載の方法。
【請求項２７】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために必要なデータセットを記憶装置から検索するために要する時間の推定に基づく、請求項２１に記載の方法。
【請求項２８】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために記憶装置から検索すべきデータ量に基づく、請求項２１に記載の方法。
【請求項２９】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために必要な前記データセットを検索する前記データチャネルの転送速度の推定に基づく、請求項２２に記載の方法。
【請求項３０】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために必要なデータセットを記憶装置から検索するためのコストに基づき、
個々の前記データセットが代数的関係の集まり内で２回以上参照される場合、前記最適化基準は、記憶装置から個々のデータセットを１回のみ検索するためのコストを割り当てる、請求項２１に記載の方法。
【請求項３１】
前記複数の代数的関係の集まりを提供するステップは、
前記要求データセットを定義する代数的関係を前記関係ストアから検索することと、
前記検索された代数的関係と代数的に等価である複数の代数的関係の集まりを生成することと、
を含む、請求項２１に記載の方法。
【請求項３２】
前記複数の代数的関係の集まりは、代数的に互いに等価ではないが、両方とも前記要求データセットに等しい結果を提供する少なくとも２つの代数的関係の集まりをさらに含む、請求項２１に記載の方法。
【請求項３３】
前記複数の代数的関係の集まりを提供するステップは、物理フォーマットが異なるが論理的に同じデータを含む等価のデータセットを区別する代数的関係の集まりを生成することを含む、請求項２１に記載の方法。
【請求項３４】
前記異なる物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項３３に記載の方法。
【請求項３５】
前記複数の代数的関係の集まりを提供するステップは、記憶ロケーションが異なるが論理的に同じデータを含む等価のデータセットを区別する代数的関係の集まりを生成することを含む、請求項２１に記載の方法。
【請求項３６】
前記等価のデータセットのうちの少なくともいくつかは、異なるデータチャネルを介して利用可能である、請求項３５に記載の方法。
【請求項３７】
前記代数的関係の集まりは、物理フォーマットが異なるが論理的に同じデータを含む少なくとも２つの等価のデータセットを参照し、
前記最適化基準を適用するステップは、記憶装置から前記等価のデータセットを取得するために要する転送時間を推定することと、前記等価のデータセットのうちから、最小の推定転送時間を有するデータセットを選択することと、をさらに含む、請求項２１に記載の方法。
【請求項３８】
前記代数的関係の集まりは、記憶ロケーションが異なるが論理的に同じデータを含む少なくとも２つの等価のデータセットを参照し、
前記最適化基準を適用するステップは、記憶装置から前記等価のデータセットを取得するために要する転送時間を推定することと、前記等価のデータセットのうちから、最小の推定転送時間を有するデータセットを選択することと、をさらに含む、請求項２１に記載の方法。
【請求項３９】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、代数的関係を計算するための複数の関数を提供することと、
前記関数のうちの少なくともいくつかを使用して、前記要求データセットを提供することと、
をさらに含む、請求項２１に記載の方法。
【請求項４０】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、代数的関係を計算するための複数の関数を提供することと、
記憶装置から検索すべき前記選択された等価のデータセットの前記フォーマットに基づいて、前記代数的に等価の関数のうちの１つを選択することと、
前記代数的に等価の関数からの前記選択された関数を含め、前記関数のうちの少なくともいくつかを使用して、前記要求データセットを実現化することと、
をさらに含む、請求項３７に記載の方法。
【請求項４１】
要求データセットを提供する方法であって、
前記要求データセットを要求しない複数の照会言語ステートメントを受け取ることと、
前記照会言語ステートメントに基づいて、データセットの複数の代数的関係を組み立てることと、
少なくとも部分的に、前記照会言語ステートメントから組み立てられる前記複数の代数的関係に基づいて、前記要求データセットを提供することと、
を含む方法。
【請求項４２】
前記照会言語ステートメントは、少なくとも１つの明示的なデータセットを指定し、前記方法は、
前記データセットに関する情報を記憶するデータセット情報ストアを提供することと、
前記明示的なデータセットにデータセット識別子を関連付けることと、
前記データセット識別子を前記データセット情報ストアに記憶することと、
をさらに含む、請求項４１に記載の方法。
【請求項４３】
前記データセットのうちの少なくともいくつかを記憶するデータストアを提供することをさらに含み、前記照会言語ステートメントは、前記要求データセットに対する要求の受け取り時に前記データストアに記憶されていなかった少なくとも１つのデータセットを指定する、請求項４１に記載の方法。
【請求項４４】
前記照会言語ステートメントから組み立てられる前記代数的関係のうちの少なくともいくつかを使用して、前記要求データセットを計算することは、前記要求データセットに対する要求の受け取り時に前記データストアに記憶されていなかった少なくとも１つのデータセットを使用することをさらに含む、請求項４３に記載の方法。
【請求項４５】
前記各代数的関係は、単一の演算子及び１〜３の範囲内のいくつかのオペランドを有する、請求項４１に記載の方法。
【請求項４６】
前記照会言語ステートメントは、関係データモデルに基づく、請求項４１に記載の方法。
【請求項４７】
前記照会言語ステートメントは、マークアップ言語モデルに基づく、請求項４１に記載の方法。
【請求項４８】
前記照会言語ステートメントのうちの少なくとも１つは関係データモデルに基づき、前記照会言語ステートメントのうちの少なくとも１つはマークアップ言語モデルに基づく、請求項４１に記載の方法。
【請求項４９】
要求データセットを提供する方法であって、
複数の照会言語ステートメントから組み立てられる複数の代数的関係を含む関係ストアを提供することと、
前記関係ストアからの前記代数的関係のうちの少なくともいくつかを使用して、前記要求データセットに等しい結果を定義する代数的関係の集まりを組み立てることと、
前記代数的関係の集まりから前記要求データセットを計算することと、
を含む方法。
【請求項５０】
前記要求データセットを要求する照会言語ステートメントを受け取ることと、
前記要求データセットを要求する前記照会言語ステートメントに基づいて、複数の追加の代数的関係を組み立てることと、
前記追加の代数的関係のうちの少なくともいくつかを使用して、前記代数的関係の集まりを組み立てることと、
をさらに含む、請求項４９に記載の方法。
【請求項５１】
前記照会言語ステートメントにおいて参照される前記データセットの部分に基づいて代数的関係を組み立てることにより、少なくとも１つの新しいデータセットを定義することと、前記新しいデータセットの前記代数的関係を前記関係ストアに記憶することと、をさらに含む、請求項５０に記載の方法。
【請求項５２】
要求データセットを提供する方法であって、
複数の照会言語ステートメントから組み立てられる複数の代数的関係を含む関係ストアを提供することと、
前記関係ストアからの前記代数的関係のうちの少なくともいくつかを使用して、前記要求データセットに等しい結果を定義する代数的関係の複数の集まりを組み立てることと、
最適化基準を適用して、前記代数的関係の集まりのうちの１つを選択することと、
前記選択された代数的関係の集まりを使用して、前記要求データセットを計算することと、
を含む方法。
【請求項５３】
代数的関係の各集まりのそれぞれを、ツリーデータ構造で記憶することをさらに含む、請求項５２に記載の方法。
【請求項５４】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために必要なデータセットを記憶装置から検索するために要する時間の推定に基づく、請求項５２に記載の方法。
【請求項５５】
前記最適化基準は、少なくとも部分的に、前記代数的関係の各集まりを計算するために必要なデータセットを記憶装置から検索するためのコストに基づき、
個々の前記データセットが代数的関係の集まり内で２回以上参照される場合、前記最適化基準は、記憶装置から個々のデータセットを１回のみ検索するためのコストを割り振る、請求項５２に記載の方法。
【請求項５６】
前記選択された集まりからの前記代数的関係を、並列処理のための処理リソースに割り当てることをさらに含む、請求項５２に記載の方法。
【請求項５７】
前記複数の代数的関係の集まりを提供するステップは、物理フォーマットが異なるが論理的に同じデータを含む等価のデータセットを区別する代数的関係の集まりを生成することを含む、請求項５２に記載の方法。
【請求項５８】
前記代数的関係の集まりは、物理フォーマットが異なるが論理的に同じデータを含む少なくとも２つの等価のデータセットを参照し、
前記最適化基準を適用するステップは、記憶装置から前記等価のデータセットを取得するために要する転送時間を推定することと、前記等価のデータセットのうちから、最低の推定転送時間を有するデータセットを選択することと、をさらに含む、請求項５２に記載の方法。
【請求項５９】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、複数の関数を提供することと、
前記関数のうちの少なくともいくつかを使用して、前記要求データセットを提供することと、
をさらに含む、請求項５６に記載の方法。
【請求項６０】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、複数の関数を提供することと、
前記等価なデータセットのうちの選択されたデータセットの前記フォーマットに基づいて、前記代数的に等価の関数のうちの１つを選択することと、
前記代数的に等価の関数のうちの選択された関数を含む前記関数のうちの少なくともいくつかを使用して、前記要求データセットを実現化することと、
をさらに含む、請求項５８に記載の方法。
【請求項６１】
要求データセットを提供するための方法であって、
複数のデータセットの関係を定義する複数の代数的関係を提供することと、
前記複数の代数的関係のうちの少なくともいくつかを使用して、前記要求データセットに等しい結果を定義する複数の代数的関係の集まりを組み立てることと、
前記複数の代数的関係の各集まりのそれぞれのコストであって、少なくとも部分的に、前記代数的関係の集まりから前記要求データセットを計算するために必要なデータセットを検索するために要する転送時間の推定に基づくコスト、を決定することと、
最低コストを有する前記代数的関係の集まりを選択することと、
前記選択された代数的関係の集まりを使用して、前記要求データセットを提供することと、
を含む方法。
【請求項６２】
前記複数の代数的関係の集まりを組み立てることは、前記複数の代数的関係のうちの少なくともいくつかを使用して、前記要求データセットが最初に要求されたときにそれまでは利用可能でなかった新しい代数的関係を生成することをさらに含む、請求項６１に記載の方法。
【請求項６３】
前記複数の代数的関係の集まりを組み立てることは、前記要求データセットを定義する少なくとも１つの代数的関係を組み立てることと、前記要求データセットを定義する前記少なくとも１つの代数的関係と代数的に等価である複数の代数的関係の集まりを生成することと、をさらに含む、請求項６１に記載の方法。
【請求項６４】
前記複数の代数的関係の集まりは、代数的に互いに等価ではないが、両方とも前記要求データセットに等しい結果を提供する少なくとも２つの代数的関係の集まりをさらに含む、請求項６１に記載の方法。
【請求項６５】
代数的関係の各集まりのそれぞれを、ツリーデータ構造で記憶することをさらに含む、請求項６１に記載の方法。
【請求項６６】
前記選択された集まりからの前記代数的関係を、並列処理のための処理リソースに割り当てることをさらに含む、請求項６１に記載の方法。
【請求項６７】
前記コストを決定するステップは、個々の前記データセットが代数的関係の集まり内で２回以上参照される場合、個々のデータセットを検索するコストを１回のみ割り当てることをさらに含む、請求項６１に記載の方法。
【請求項６８】
前記複数の代数的関係の集まりを組み立てることは、物理フォーマットが異なるが論理的に同じデータを含む等価のデータセットを区別する代数的関係の集まりを生成することをさらに含む、請求項６１に記載の方法。
【請求項６９】
前記異なる物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項６８に記載の方法。
【請求項７０】
前記複数の代数的関係の集まりを組み立てることは、記憶ロケーションが異なるが論理的に同じデータを含む等価のデータセットを区別する代数的関係の集まりを生成することをさらに含む、請求項６１に記載の方法。
【請求項７１】
前記等価のデータセットのうちの少なくともいくつかは、異なるデータチャネルを介して利用可能である、請求項７０に記載の方法。
【請求項７２】
前記代数的関係の集まりは、物理フォーマットが異なるが論理的に同じデータを含む少なくとも２つの等価のデータセットを参照し、
前記コストを決定するステップは、記憶装置から前記等価のデータセットを取得するために要する転送時間を推定することをさらに含み、
前記最低コストを有する前記代数的関係の集まりを選択するステップは、最小の推定転送時間を有する前記等価のデータを参照する前記代数的関係の集まりを選択することをさらに含む、請求項６１に記載の方法。
【請求項７３】
前記代数的関係の集まりは、記憶ロケーションが異なるが論理的に同じデータを含む少なくとも２つの等価のデータセットを参照し、
前記コストを決定するステップは、記憶装置から前記等価のデータセットを取得するために要する転送時間を推定することをさらに含み、
前記最低コストを有する前記代数的関係の集まりを選択するステップは、最小の推定転送時間を有する前記等価のデータセットを参照する前記代数的関係の集まりを選択することをさらに含む、請求項６１に記載の方法。
【請求項７４】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、代数的関係を計算するための複数の関数を提供することと、
前記関数のうちの少なくともいくつかを使用して、前記要求データセットを提供することと、
をさらに含む、請求項６１に記載の方法。
【請求項７５】
異なる物理フォーマットのデータセットに対して作用する少なくとも２つの代数的に等価の関数を含む、代数的関係を計算するための複数の関数を提供することと、
少なくとも部分的に、前記選択された代数的関係の集まりにおいて参照される前記データセットの前記フォーマットに基づいて、前記代数的に等価の関数のうちから関数を選択することと、
前記代数的に等価の関数から選択された関数を含め、前記関数のうちの少なくともいくつかを使用して、前記要求データセットを実現化することと、
をさらに含む、請求項６８に記載の方法。
【請求項７６】
前記等価のデータセットは、第１のフォーマットの第１のデータセット及び前記第１のフォーマットよりも大きなサイズを有する第２のフォーマットの第２のデータセットを含み、前記最低コストを有する前記代数的関係の集まりを選択するステップは、前記第２のデータセットが、前記第１のデータセットよりも高速の転送速度を有するデータチャネルを介して利用可能な場合、前記第２のデータセットを参照する前記データの集まりを選択することをさらに含む、請求項６８に記載の方法。
【請求項７７】
前記等価のデータセットは、第１のフォーマットで不揮発性記憶装置内にある第１のデータセット及び前記第１のフォーマットよりも大きなサイズを有する第２のフォーマットで揮発性メモリ内にある第２のデータセットを含み、前記最低コストを有する前記代数的関係の集まりを選択するステップは、前記第２のデータセットを参照する前記代数的関係の集まりを選択することをさらに含む、請求項６８に記載の方法。
【請求項７８】
指定データセットを記憶するための方法であって、
複数のデータセットの関係を定義する複数の代数的関係を提供することと、
前記複数の代数的関係のうちの少なくともいくつかを使用して、前記指定データセットに等しい結果を定義する複数の代数的関係の集まりを組み立てることと、
前記複数の代数的関係の各集まりのそれぞれのコストであって、少なくとも部分的に、前記代数的関係の集まりから前記要求データセットを計算するために必要なデータセットを検索するために要する転送時間の推定に基づくコスト、を決定することと、
最低コストを有する前記代数的関係の集まりを選択することと、
前記選択された代数的関係の集まりを使用して、前記指定データセットを計算することと、
前記選択された代数的関係の集まりから計算された前記指定データセットを記憶することと、
を含む方法。
【請求項７９】
前記複数の代数的関係の集まりを組み立てることは、前記指定データセットが最初に指定されたときにはそれまで利用可能でなかった新しい代数的関係を生成することをさらに含む、請求項７８に記載の方法。
【請求項８０】
前記複数の代数的関係の集まりを組み立てることは、前記指定データセットを定義する少なくとも１つの代数的関係を組み立てることと、前記指定データセットを定義する前記少なくとも１つの代数的関係と代数的に等価である複数の代数的関係の集まりを生成することと、をさらに含む、請求項７８に記載の方法。
【請求項８１】
要求データセットを提供するための方法であって、
データセットを記憶する記憶システムを提供することと、
前記要求データセットに等しい結果をそれぞれ定義する少なくとも２つの代替の代数的関係であって、前記記憶システムに記憶されている第１のデータセットの集まりに基づく第１の代数的関係及び前記記憶システムに記憶されている第２のデータセットの集まりに基づく第２の代数的関係を含む代数的関係、を組み立てることと、
少なくとも部分的に、前記第１の代数的関係を使用して前記要求データセットを計算するために、前記記憶システムから前記第１のデータセットの集まりを検索するために要する転送時間の推定、及び前記第２の代数的関係を使用して前記要求データセットを計算するために、前記記憶システムから前記第２のデータセットの集まりを検索するために要する転送時間の推定に基づいて、前記第１の代数的関係か前記第２の代数的関係かを選択することと、
前記選択された代数的関係を使用して、前記要求データセットを計算することと、
を含む方法。
【請求項８２】
要求データセットを提供するための方法であって、
データセットを記憶する記憶システムを提供することと、
前記要求データセットに等しい結果をそれぞれ定義する少なくとも２つの代替の代数的関係であって、前記記憶システムに記憶されている少なくとも第１のデータセットに基づく第１の代数的関係及び前記記憶システムに記憶されている少なくとも第２のデータセットに基づく第２の代数的関係を含み、かつ、前記第１のデータセット及び前記第２のデータセットが、異なる物理フォーマットで記憶された論理的に同じデータを含む代数的関係、を組み立てることと、
少なくとも部分的に、前記第１のデータセットの前記物理フォーマット及び前記第２のデータセットの前記物理フォーマットに基づいて、前記第１の代数的関係か前記第２の代数的関係かを選択することと、
前記選択された代数的関係を使用して、前記要求データセットを計算することと、
を含む方法。
【請求項８３】
前記第１のデータセットの前記物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項８２に記載の方法。
【請求項８４】
前記第２のデータセットの前記物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項８３に記載の方法。
【請求項８５】
前記第１のデータセットの前記物理フォーマットのデータセットに対して作用する第１の関数及び前記第２のデータセットの前記物理フォーマットのデータセットに対して作用する第２の関数を含み、かつ、前記第１の関数及び前記第２の関数が、代数的に等価である、代数的関係を計算するための複数の関数を提供することと、
前記選択された代数的関係を使用して、前記要求データセットを計算するステップは、前記第１の代数的関係が選択される場合には前記第１の関数を使用し、前記第２の代数的関係が選択される場合には前記第２の関数を使用することをさらに含む、請求項８２に記載の方法。
【請求項８６】
前記記憶システムは、複数のデータチャネルを含み、前記第１のデータセット及び前記第２のデータセットは、異なるデータチャネルを介して利用可能である、請求項８２に記載の方法。
【請求項８７】
前記第１の物理フォーマットの前記第１のデータセットは、第１のサイズを有し、第１のデータ転送速度を有する第１のデータチャネルを介して利用可能であり、前記第２の物理フォーマットの前記第２のデータセットは、第２のサイズを有し、第２のデータ転送速度を有する第２のデータチャネルを介して利用可能であり、前記方法は、
少なくとも部分的に、前記第１のサイズ及び前記第１のデータ転送速度に基づいて第１のコストを決定することと、
少なくとも部分的に、前記第２のサイズ及び前記第２のデータ転送速度に基づいて第２のコストを決定することと、
前記第１のコストが前記第２のコストよりも低い場合、前記要求データセットを計算するために、前記第１の代数的関係を選択することと、
をさらに含む、請求項８６に記載の方法。
【請求項８８】
要求データセットを提供するための方法であって、
データセットを記憶するための記憶システムであって、揮発性メモリ及び不揮発性記憶媒体を含む記憶システム、を提供することと、
前記要求データセットに等しい結果をそれぞれ定義する少なくとも２つの代替の代数的関係であって、前記記憶システムに記憶されている少なくとも第１のデータセットに基づく第１の代数的関係及び前記記憶システムに記憶されている少なくとも第２のデータセットに基づく第２の代数的関係を含み、かつ、前記第１のデータセット及び前記第２のデータセットが、異なる物理フォーマットで記憶された同じ論理データを含むとともに、前記第１のデータセットが、第１のサイズを有する第１の物理フォーマットで記憶され、かつ、前記第２のデータが、前記第１のサイズよりも小さな第２のサイズを有する第２の物理フォーマットで記憶される代数的関係、を組み立てることと、
前記第１のデータセットが前記揮発性メモリにおいて利用可能であると決定することと、
前記要求データセットを計算するために、前記第１の代数的関係を選択することと、
を含む方法。
【請求項８９】
要求データセットを提供するための方法であって、
複数の物理フォーマットでデータセットを記憶する記憶システムを提供することと、
前記複数の物理フォーマットの前記データセットに対して作用する複数の関数であって、前記物理フォーマットのそれぞれ１つの少なくとも１つのオペランドに対して作用するように構成される、複数の関数を提供することと、
前記要求データセットに等しい結果を定義する代数的関係であって、前記記憶システムに記憶されている少なくとも第１のデータを参照する、代数的関係を提供することと、
前記物理フォーマットの個々で前記第１のデータセットを検索することと、
前記複数の関数のうち、前記第１のデータセットの前記各物理フォーマットのオペランドに対して作用するように構成される関数を選択することと、
前記選択された関数を使用して、代数的関係から前記要求データセットを計算することと、
を含む方法。
【請求項９０】
前記代数的関係は少なくとも１つの演算を指定し、前記選択される関数は前記指定される演算に対応する、請求項８９に記載の方法。
【請求項９１】
前記複数の関数は、異なる物理フォーマットのオペランドに対して作用するように構成される代数的に等価の関数を含む、請求項８９に記載の方法。
【請求項９２】
前記代数的関係を提供するステップは、前記要求データセットに等しい結果をそれぞれ定義する複数の代数的関係から前記代数的関係を選択することをさらに含む、請求項８９に記載の方法。
【請求項９３】
前記代数的関係を提供するステップは、前記要求データセットに等しい結果をそれぞれ定義する複数の代数的関係から前記代数的関係を選択することをさらに含む、請求項９１に記載の方法。
【請求項９４】
前記代数的関係を選択するステップは、少なくとも部分的に、前記記憶システムから前記第１のデータセットを検索するために要する時間の推定に基づいて、前記代数的関係を選択することをさらに含む、請求項９３に記載の方法。
【請求項９５】
前記代数的関係は、前記記憶システムに記憶されている少なくとも第２のデータセットを参照し、前記方法は、前記第２のデータセットを前記物理フォーマットの個々で検索することをさらに含む、請求項８９に記載の方法。
【請求項９６】
前記選択される関数は、少なくとも前記第２のデータセットの前記各物理フォーマットの第２のオペランドに対して作用するように構成される、請求項９５に記載の方法。
【請求項９７】
前記代数的関係は少なくとも１つの演算を指定し、前記選択される関数は前記指定される演算に対応する、請求項９５に記載の方法。
【請求項９８】
前記複数の関数は、異なる物理フォーマットのオペランドに対して作用するように構成される代数的に等価の関数を含む、請求項９５に記載の方法。
【請求項９９】
前記代数的関係を提供するステップは、前記要求データセットに等しい結果をそれぞれ定義する複数の代数的関係から前記代数的関係を選択することをさらに含む、請求項９５に記載の方法。
【請求項１００】
前記代数的関係を選択するステップは、少なくとも部分的に、前記記憶システムから前記第２のデータセットを検索するために要する時間の推定に基づいて、前記代数的関係を選択することをさらに含む、請求項９９に記載の方法。
【請求項１０１】
前記代数的関係を提供するステップは、前記要求データセットに等しい結果をそれぞれ定義する複数の代数的関係から前記代数的関係を選択することをさらに含む、請求項９８に記載の方法。
【請求項１０２】
要求データセットを提供するための方法であって、
第１のデータモデルに基づく第１のスキーマと第２のデータモデルに基づく第２のスキーマとの間のマッピングを提供することと、
前記第１のスキーマに基づく第１のステートメントを受け取ることと、
前記第１のステートメントに基づく複数のデータセット間についての複数の代数的関係を組み立てることと、
前記要求データセットを要求する前記第２のスキーマに基づく第２のステートメントを受け取ることと、
前記第１のステートメントから組み立てられる前記代数的関係のうちの少なくとも１つ、及び、前記第１のスキーマと前記第２のスキーマとの間のマッピングを使用して、前記要求データセットを提供することと、
を含む方法。
【請求項１０３】
前記第１のデータモデルは、関係データモデルである、請求項１０２に記載の方法。
【請求項１０４】
前記第２のデータモデルは、マークアップ言語データモデルである、請求項１０３に記載の方法。
【請求項１０５】
前記第１のデータモデルは、マークアップ言語データモデルである、請求項１０２に記載の方法。
【請求項１０６】
前記第２のデータモデルは、関係データモデルである、請求項１０５に記載の方法。
【請求項１０７】
前記第１のステートメントは、構造化照会言語（ＳＱＬ）フォーマットの照会ステートメントである、請求項１０２に記載の方法。
【請求項１０８】
前記第２のステートメントは、ＸＱｕｅｒｙフォーマットの照会言語ステートメントである、請求項１０７に記載の方法。
【請求項１０９】
前記第１のステートメントは、ＸＱｕｅｒｙフォーマットの照会言語ステートメントである、請求項１０２に記載の方法。
【請求項１１０】
前記第２のステートメントは、構造化照会言語（ＳＱＬ）フォーマットの照会言語ステートメントである、請求項１０９に記載の方法。
【請求項１１１】
前記第１のステートメントは、集合記法ステートメントである、請求項１０２に記載の方法。
【請求項１１２】
前記第２のステートメントは、構造化照会言語（ＳＱＬ）フォーマットの照会ステートメントである、請求項１１１に記載の方法。
【請求項１１３】
前記第２のステートメントは、集合記法ステートメントである、請求項１０７に記載の方法。
【請求項１１４】
前記第２のステートメントは、ＸＱｕｅｒｙフォーマットの照会言語ステートメントである、請求項１１１に記載の方法。
【請求項１１５】
前記第２のステートメントは、集合記法ステートメントである、請求項１０９に記載の方法。
【請求項１１６】
第１のスキーマに基づく要求データセットを提供するための方法であって、
第１のデータモデルに基づく第１のスキーマと第２のデータモデルに基づく第２のスキーマとの間のマッピングを提供することと、
前記第２のスキーマに基づく複数のデータセット間についての第１の複数の代数的関係を提供することと、
少なくとも部分的に、前記第１の複数の代数的関係に基づいて、前記要求データセットに等しい結果を定義する代数的関係を組み立てることと、
前記要求データセットに等しい結果を定義する前記代数的関係及び前記第１のスキーマと前記第２のスキーマとの間の前記マッピングを使用して、前記要求データセットを提供することと、
を含む方法。
【請求項１１７】
前記第１の複数の代数的関係は、前記第２のスキーマに基づく第１の複数のステートメントから組み立てられる、請求項１１６に記載の方法。
【請求項１１８】
前記第１のスキーマに基づく複数のデータセット間についての第２の複数の代数的関係を提供することをさらに含み、前記要求データセットに等しい結果を定義する前記代数的関係は、少なくとも部分的に、前記第２の複数の代数的関係に基づく、請求項１１６に記載の方法。
【請求項１１９】
前記第１の複数の代数的関係は、前記第２のスキーマに基づく第１の複数のステートメントから組み立てられる、請求項１１８に記載の方法。
【請求項１２０】
前記第２の複数の代数的関係は、前記第１のスキーマに基づく第２の複数のステートメントから組み立てられる、請求項１１８に記載の方法。
【請求項１２１】
前記第２の複数の代数的関係は、前記第１のスキーマに基づく第２の複数のステートメントから組み立てられる、請求項１１９に記載の方法。
【請求項１２２】
前記第１のデータモデルは、関係データモデルである、請求項１１６に記載の方法。
【請求項１２３】
前記第２のデータモデルは、マークアップ言語データモデルである、請求項１２２に記載の方法。
【請求項１２４】
前記第１のデータモデルは、マークアップ言語データモデルである、請求項１１６に記載の方法。
【請求項１２５】
前記第２のデータモデルは、関係データモデルである、請求項１２４に記載の方法。
【請求項１２６】
データセットを記憶するための方法であって、
データストアを提供することと、
各データセットが前記データストア内で実現化されているか否かを特定する情報を含む、複数のデータセットに関する情報を記憶するデータセット情報ストアを提供することと、
前記データセット間の複数の代数的関係を記憶する関係ストアを提供することと、
前記データセット情報ストアにおいてデータセットを仮想化する基準を確立することと、
前記データストア内で実現化され、前記仮想化の基準を満たす少なくとも１つのデータセットを識別することと、
前記関係ストアが、前記データストア内で実現化されている少なくとも１つの他のデータセットに基づいて、前記識別されたデータセットを定義する少なくとも１つの代数的関係を含むと判断することと、
前記データストアから前記識別されたデータセットを除去することと、
前記識別されたデータセットが前記データストア内で実現化されていないことを示すように、前記データセット情報ストア内の前記識別されたデータセットに関する前記情報を変更することと、
を含む方法。
【請求項１２７】
前記仮想化の基準は、個々の前記データセットのサイズを含む、請求項１２６に記載の方法。
【請求項１２８】
前記仮想化の基準は、前記データセットが参照された回数を含む、請求項１２６に記載の方法。
【請求項１２９】
前記仮想化の基準は、個々の前記データセットが前記データストア内でアクセスされた頻度を含む、請求項１２６に記載の方法。
【請求項１３０】
前記識別されたデータセットを定義する前記代数的関係は、前記データストア内で実現化されている少なくとも２つの他のデータセットを参照する、請求項１２６に記載の方法。
【請求項１３１】
前記識別されたデータセットを定義するために使用される前記少なくとも１つの他のデータセットは、物理フォーマットが異なるが論理的に同じデータを含む、請求項１２６に記載の方法。
【請求項１３２】
前記識別されたデータセットが記憶される前記物理フォーマットは、前記少なくとも１つの他のデータセットの前記物理フォーマットよりも大きい、請求項１３１に記載の方法。
【請求項１３３】
前記識別されたデータセットが記憶される前記物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項１３２に記載の方法。
【請求項１３４】
前記少なくとも１つの他のデータセットが記憶される前記物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項１３２に記載の方法。
【請求項１３５】
前記識別されたデータセットを定義する前記代数的関係を使用して、前記識別されたデータセットを実現化することなく要求データセットを提供することをさらに含む、請求項１２６に記載の方法。
【請求項１３６】
前記識別されたデータセットを定義する前記代数的関係を使用して、前記要求データセットを提供するステップは、
前記要求データセットを定義する複数の代数的関係の集まりであって、前記識別されたデータを定義する前記代数的関係が、前記代数的関係の集まりのうちの少なくとも１つを組み立てるために使用される、前記複数の代数的関係の集まりを組み立てることと、
最適化基準を適用して、前記要求データセットを計算するための前記代数的関係の集まりのうちの１つを選択することと、
前記選択された代数的関係の集まりを使用して、前記要求データセットを計算することと、
をさらに含む、請求項１３５に記載の方法。
【請求項１３７】
前記識別されたデータを定義する前記代数的関係は、前記代数的関係の集まりのうちの少なくとも１つにおいて、前記識別されたデータセットへの参照の代替として使用される、請求項１３６に記載の方法。
【請求項１３８】
データセットを記憶するための方法であって、
データストアを提供することと、
各データセットが前記データストア内で実現化されているか否かを特定する情報を含む、複数のデータセットに関する情報を記憶するデータセット情報ストアを提供することと、
前記データセット間の複数の代数的関係を記憶する関係ストアを提供することと、
前記データストア内で実現化されている少なくとも１つのデータセットを前記データセット情報ストアから選択することと、
前記選択されたデータセットのサブセットであるデータセットを前記データセット情報ストアに追加し、前記追加されたデータセットを前記データストア内で実現化することと、
前記追加されたデータセットに基づいて、前記選択されたデータセットを定義する代数的関係を前記関係ストアに追加することと、
前記選択されたデータセットを前記データストアから除去することと、
前記選択されたデータセットが前記データストア内で実現化されていないことを示すように、前記データセット情報ストア内の前記選択されたデータセットに関する前記情報を変更することと、
を含む方法。
【請求項１３９】
前記選択されたデータセットを参照する表現を含む、要求データセットを要求するステートメントを受け取ることと、
前記要求データセットに等しい結果を有する代数的関係であって、前記選択されたデータセットを参照する前記表現の代替として前記追加されたサブセットのうちの少なくとも１つを参照する表現を含む、代数的関係を組み立てることと、
前記代数的関係を使用して、前記要求データセットを計算することと、
をさらに含む、請求項１３８に記載の方法。
【請求項１４０】
前記追加されたデータセットは、同じ濃度を有する前記選択されたデータセットの部分である、請求項１３８に記載の方法。
【請求項１４１】
前記追加されたデータセットは、前記選択されたデータセットに含まれるデータアイテムのスカラー値範囲によって定義されるサブセットである、請求項１３８に記載の方法。
【請求項１４２】
データセットを記憶するための方法であって、
データセット間の代数的関係を記憶する関係ストアを提供することと、
少なくとも第１のデータセット、第２のデータセット、及び第３のデータセットを含むデータセットを記憶するデータストアを提供することと、
少なくとも前記第２のデータセット及び前記第３のデータセットを使用して、前記第１のデータセットを定義する代数的関係を組み立てることと、
前記代数的関係を前記関係ストアに追加することと、
前記代数的関係が前記関係ストアに追加された後、前記データストアから前記第１のデータセットを除去することと、
を含む方法。
【請求項１４３】
前記第２のデータセット及び前記第３のデータセットのうちの少なくとも一方は、前記第１のデータセットが前記データストアに記憶される前記物理フォーマットとは異なる物理フォーマットで前記データストアに記憶される、請求項１４２に記載の方法。
【請求項１４４】
前記第１のデータセットが記憶される前記物理フォーマットは、カンマ区切り値フォーマット、タブ区切り値フォーマット、バイナリストリングフォーマット、固定オフセットフォーマット、及びマークアップ言語フォーマットからなる群から選択される、請求項１４３に記載の方法。
【請求項１４５】
前記第１のデータセット、前記第２のデータセット、及び前記第３のデータセットが前記データストア内で実現化されていることを示す情報を含む、複数のデータセットに関する情報を記憶するデータセット情報ストアを提供することと、
前記第１のデータセットが前記データストア内で実現化されていないことを示すように、前記データセット情報ストア内の前記第１のデータセットに関する前記情報を変更することと、
をさらに含む、請求項１４２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
相互参照
本願は以下の同時係属中の特許出願、即ち２００６年５月１５日に出願された米国特許出願第１１／３８３，４７６号明細書、２００６年５月１５日に出願された米国特許出願第１１／３８３，４７７号明細書、２００６年５月１５日に出願された米国特許出願第１１／３８３，４７８号明細書、２００６年５月１５日に出願された米国特許出願第１１／３８３，４７９号明細書、２００６年５月１５日に出願された米国特許出願第１１／３８３，４８０号明細書、及び２００６年５月１５日に出願された米国特許出願第１１／３８３，４８２号明細書に関連し、これら各米国特許出願は参照により本明細書に援用される。
【０００２】
発明の背景
Ｉ．分野
本発明の分野は、データの記憶及びアクセスを行うためのシステム及び方法に関し、より詳細には、データ記憶、データベース照会、及びデータ検索に関する。
【背景技術】
【０００３】
ＩＩ．背景
多くのデータベース及びデータ記憶システムは、データが受信されると、そのデータに対して構造を付与する所定のスキーマを有する。スキーマは、データが当初提供された状態のままでは、データの構造に関する情報を取り込まないことがある。これに加えて、スキーマは、データが実際に提供又は照会される様式に向けて最適化されていない予め規定された関係に則って設計されていることがある。スキーマに固有の論理的関係は、データが実際に記憶される様式に向けて最適化されていないデータベース構造にも繋がる恐れがある。さらに、スキーマ及び／又はそれに関連するデータベース構造に固有の論理的関係は、データクエリにおいて指定することができる論理関係の種類を制限する恐れがある。単一のクエリが記憶装置に複数回アクセスする必要があり得、特に処理速度と記憶装置アクセス速度との開きが広がることから、大きな非効率性が生じる。多大な努力が、関係（リレーショナル）データベース及び他の従来のデータベースのアクセス方法を改良するために払われてきたが、そういった方法は本質的に、予め規定される関係、その結果としてデータに付与される構造によって制限される。多くのデータベースのこういった関係と構造との密結合は、フラットファイル、カンマ区切り値（ＣＳＶ）ファイル、及び拡張可能マークアップ言語（ＸＭＬ）を使用して定義されたデータ等の様々な異なる形式（フォーマット）で提供されるデータの取り込み、変換、及び処理を効率的に行うことを難しくさせもする。
【発明の概要】
【課題を解決するための手段】
【０００４】
発明の概要
本発明の諸態様は、データの記憶及びアクセスを行うためのシステム及び方法を提供する。実施形態例は、データセットを記憶するデータストア、データセットに関する情報を記憶するデータセット情報ストア、データセット間の代数的関係を記憶する代数的関係ストア、代数的関係を使用して、データストアからのデータセットの記憶及びアクセスを最適化するオプティマイザ、及び代数的関係を計算してデータセットを提供するセットプロセッサを含むことができる。実施形態例では、モジュールが、ハードウェア、ファームウェア、及び／又はソフトウェアの組み合わせによって提供されてよく、実施形態例によっては並列処理及び分散記憶を利用してもよい。
【０００５】
本発明の一態様は、クエリ（照会）言語ステートメント（文）からデータセット間の代数的関係を組み立てるための方法を提供する。別の態様は、要求データセットを提供するための方法を提供する。照会言語ステートメントをシステムに提示することができる。例えば、照会言語ステートメントは、関係データモデルを使用する構造化照会言語（ＳＱＬ）フォーマットであってもよく、又はマークアップ言語フォーマットを使用するＸＱｕｅｒｙフォーマットであってもよい。次に、照会言語ステートメントから複数の代数的関係を組み立て、代数的関係ストアに記憶することができる。このようにして、ステートメントがシステムに提示される都度、データセット間の代数的関係を時間と共に関係ストアに蓄積することができる。実施形態例によっては、照会言語ステートメントは要求データセットを要求しないが、それでも要求データセットの提供に当たって有用な代数的関係を組み立てるために使用されることがある。こういった代数的関係のうちの少なくともいくつかは、関係ストアから検索することができ、要求データセットを提供するために使用することができる。
【０００６】
さらなる一態様では、データセット間の代数的関係は、ステートメントがシステムに提示される都度、時間と共に関係ストアに蓄積することができる。代数的関係の代替の集まり（コレクション）を生成して評価し、要求データセットの計算及び提供に使用するために最適な代数的関係の集まりを判断することができる。この最適化は、記憶装置から基礎をなすデータセットを検索するのではなく、代数的関係を使用して実行することができる。その結果、最適化をプロセッサ速度で実行することができ、低速の記憶装置からデータを検索するために要する時間量が最小化される。
【０００７】
別の態様では、照会言語ステートメントが、提供されるべきデータセットを要求し、関係ストアが、照会言語ステートメントから組み立てられないデータセットの他の代数的関係を含む。例によっては、照会言語ステートメントから組み立てられた代数的関係及び関係ストア内の他の代数的関係の両方が、要求データセットの提供に使用され得る。さらなる一態様では、オプティマイザを使用して、要求データセットに等しい結果を定義する代数的関係の複数の集まりを生成することができ、最適化基準を適用して、要求データセットの提供に使用する、複数の代数的関係の集まりのうちの１つを選択することができる。実施形態例によっては、最適化基準は、記憶装置から転送する必要のあるデータ量及び／又は代数的関係の集まりを計算するために記憶装置からデータセットを転送するために要する時間量の推定に基づくことができる。別の例では、最適化基準は、異なる物理フォーマットの又はデータストア内で異なる位置にある同じ論理データを含む等価データセットを識別することができる。
【０００８】
別の態様は、要求データセットに等しい結果をそれぞれ定義する少なくとも２つの代替の代数的関係を組み立てることができる、要求データセットを提供するための方法を提供する。データセットは、異なる物理フォーマットで且つ／又はデータストア内の異なる場所に記憶されている同じ論理データを含むことができる。例えば、データセットは、カンマ区切り値（ＣＳＶ）フォーマット、バイナリストリング符号化（ＢＳＴＲ）フォーマット、固定オフセット（ＦＩＸＥＤ）フォーマット、タイプ符号化データ（ＴＥＤ）フォーマット、及び／又はＸＭＬ若しくは他のマークアップ言語フォーマットで記憶媒体に記憶することができる。タイプ符号化データ（ＴＥＤ）は、データ及びそのようなデータのフォーマットを指す関連値を含むファイルフォーマットである。これらは単なる例にすぎず、他の実施形態では、他の物理フォーマットを使用してもよい。データセットは、分散記憶システム内の異なるディスクドライブ等の、データストア内の異なる場所に記憶してもよく、異なるデータ転送速度及び／又は異なる利用可能帯域幅を有する異なるデータチャネルを介してアクセス可能であることとしてもよい。代数的関係のうちの１つを、少なくとも部分的に、代数的関係内で参照されるデータセットの物理フォーマット及び／又は場所に基づいて、要求データセットの提供に使用されるものとして選択することができる。他の例では、代数的関係は、少なくとも部分的に、代数的関係内で参照されるデータセットの検索に使用されるチャネルの速度及び利用可能帯域幅に基づいて選択することができる。
【０００９】
別の態様は、異なる物理フォーマットのオペランドに対して作用する関数を使用して、要求データセットを提供するための方法を提供する。データセットは、カンマ区切り値（ＣＳＶ）フォーマット、バイナリストリング符号化（ＢＳＴＲ）フォーマット、固定オフセット（ＦＩＸＥＤ）フォーマット、タイプ符号化データ（ＴＥＤ）フォーマット、及び／又はＸＭＬ若しくは他のマークアップ言語フォーマット等の複数の物理フォーマットで記憶することができる。データセットをオペランドとして使用する関数が定義される。論理的に等価の関数を、オペランドに使用することができる物理フォーマットの異なる組み合わせに対して定義することができる。要求データセットを提供するために、要求データセットに等しい結果を定義する代数的関係を組み立てることができる。代数的関係は、記憶装置内のデータセットを参照することができる。代数的関係から要求データセットを計算するために、参照データセットは記憶装置から検索され、関数がそのデータセットに対して適用されて、代数的関係において指定される演算が実行される。代数的関係の計算に使用される関数は、データセットが検索される物理フォーマットに対応するように選択することができる。このようにして、別個のフォーマットへの変換を必要とせずに、データセットが検索された物理フォーマットに最適な関数を使用することができる。
【００１０】
さらなる一態様では、要求データセットに等しい結果を定義する複数の代数的関係が組み立てられる。代数的関係のうちのいくつかは、物理フォーマットが異なるが論理的に同じデータを参照することができる。データセットの物理フォーマット、それらフォーマットのデータセットに対する動作に利用可能な関数、及び／又は計算に必要とされ得るあらゆるフォーマット変換を考慮した最適化基準を代数的関係に適用することができる。代数的関係は、最適化基準に基づいて選択され、要求データセットの提供に使用することができる。次に、フォーマット固有関数が使用されて、選択された代数的関係が計算される。関数のうちの少なくともいくつかは、代数的関係内で参照されるデータセットの物理フォーマットに基づいて選択される。
【００１１】
別の態様では、代数的関係を使用して、新しいデータセットを定義することができる。一実施形態例では、データセットに関する情報を記憶するデータセット情報ストアを提供することができる。新しいデータセットは、データセット識別子をデータセットに関連付け、そのデータセット識別子をデータ情報ストアに記憶することによって作成することができる。例によっては、新しいデータセットは、照会言語ステートメントの部分としてシステムに提示される明示的なデータセットであってよい。
【００１２】
別の態様では、照会言語ステートメントは、同照会言語ステートメントの受け取り時にデータストアにまだ記憶されていないデータセットのうちの１つ又は複数を指定することができる。実施形態によっては、データセットは、記憶装置内にデータセットを実現化せずに、代数的関係によって定義することができる。
【００１３】
別の態様では、データセットが作成されたときを示す一時的な情報がデータセット情報ストアに記憶される。さらなる一態様では、指定時間前に一時的な情報に関連するデータセットをデータセット情報ストアから除去することにより、データセット情報ストアを一時的に再定義することができる。実現化されていないデータセットが、指定時間前に一時的な情報を有するデータを参照する場合、参照されるデータセットが除去される前に、そのデータセットを実現化してデータストアに記憶することができる。
【００１４】
別の態様は、スキーマ間のマッピングを使用して要求データセットを提供するための方法を提供する。マッピングは、異なるデータモデルに基づいて複数のスキーマ間に提供することができる。ステートメントは、異なるスキーマ及びデータモデルに基づいてシステムに提示することができる。例えば、ステートメントは、関係データモデルに基づく構造化照会言語（ＳＱＬ）フォーマット及び／又は拡張可能マークアップ言語（ＸＭＬ）データモデルに基づくＸＱｕｅｒｙフォーマットの照会言語としてシステムに提示することができる。これらステートメント及びデータモデルは単なる例にすぎず、他の例では、他のステートメント及びデータモデルをサポートすることもできる。異なるスキーマ及びデータモデルに基づいてシステムに提示されるステートメントから、データセット間の代数的関係を組み立てることができる。データセットが特定のスキーマ及びデータモデルに基づいて要求される場合、マッピングにより、他のスキーマ及びデータモデルに基づく代数的関係を、要求データの提供に使用することができる。
【００１５】
さらなる一態様では、要求データセットに等しい結果を定義する複数の代数的関係を組み立てることができる。最適化基準を使用して、要求データセットを計算する代数的関係のうちの１つを選択することができる。代数的関係は、異なるスキーマ及びデータモデルに基づくステートメントから組み立てることができる。マッピングは、異なるデータモデルに基づいてスキーマ間に提供することができる。その結果、最適化をより広い代数的関係候補の集合（セット）にわたって実行して、要求データセットを提供することができる。代数的関係は、異なるデータモデルを使用して異なるスキーマに基づくステートメントから組み立てられた場合であっても考えることができる。例えば、代数的関係は、関係データモデルに基づく構造化照会言語（ＳＱＬ）フォーマット及び拡張可能マークアップ言語（ＸＭＬ）モデルに基づくＸＱｕｅｒｙフォーマットの両方でシステムに提示される照会ステートメントから組み立てることができる。そして、続く照会ステートメントがシステムに提示されたことに応答して、これら代数的関係を最適化に使用することができる。例えば、ＳＱＬステートメントから組み立てられた代数的関係を、ＸＱｕｅｒｙステートメントに応答して使用することができる。同様に、ＸＱｕｅｒｙから組み立てられた代数的関係を、ＳＱＬステートメントに応答して使用することもできる。これらは単なる例にすぎず、他の例では、他の種類のステートメント及びデータモデルを使用してもよい。
【００１６】
別の態様は、仮想化を使用してデータセットを記憶するための方法を提供する。データセットは、データストアから除去し、関係ストア内の代数的関係によって定義することができる。データセット情報は、各データセットがデータストアにおいて実現化されているか否かを特定する情報を含むことができる。データセットをいつ仮想化すべきかを判断するための基準を確立することができる。例えば、基準は、データセットのサイズ、参照された回数、及び／又はデータセットがデータストア内でアクセスされた頻度に基づくことができる。データストアにおいて実現化されており、この基準を満たすデータセットについては、データストアからの除去から考えることができる。実施形態例では、データストアにおいて実現化されている他のデータセットに基づいてデータセットを定義する代数的関係（直接的であるか、実現化されているデータセットに直接又は間接的に基づく他の代数的関係を参照することによって間接的であるかに関わらず）が関係ストア内にある場合、これらデータセットを除去することができる。データセットが除去された後、データセット情報ストア内のそのデータセットに関する情報を、識別されたデータセットがデータストア内で実現化されていないことを示すように変更することができる。
【００１７】
さらなる一態様では、データセットを部分集合（サブセット）に分割し、次にそのデータセットをデータ記憶装置から除去することによって仮想化することにより、最適化のためのデータセットを選択することができる。例えば、選択されたデータセットのサブセットであるデータセットをデータストアに追加することができる。例によっては、サブセットは、等しい濃度を有する、選択されたデータセットの部分であってもよく、又は選択されたデータセット内のデータアイテムのスカラー値範囲に基づいて定義してもよい。これらは単なる例にすぎず、他の例では、他のサブセットを定義してもよい。データストアに追加されたサブセットの集合体に基づいて、選択されたデータセットを定義する代数的関係を組み立てることができる。次に、選択されたデータセットをデータストアから除去し、データセット情報ストア内の情報を、選択されたデータセットがデータセットで実現化されていないことを示すように変更することができる。
【００１８】
さらなる一態様では、仮想データセットを参照する代数的関係を使用して、要求データセットをシステムから検索することができる。例えば、選択されたデータセットは、データストアから除去し、選択されたデータセットを定義する代数的関係で置換することができる。選択されたデータセットがもはやデータストア内で実現化されていない場合であっても、要求された他のデータセットを提供するに当たって使用するために、代数的関係を関係ストアにおいて提供することができる。例えば、要求データセットを定義する代数的関係の複数の集まりを組み立てることができる。これら代数的関係のうちのいくつかは、選択されたデータセットを定義する代数的関係を使用して、（仮想的な）選択されたデータセットへの参照の置換を実行することによって組み立てることができる。例えば、選択されたデータセットを参照する表現を、データストアで実現化される１つ又は複数のサブセットを参照する表現で置換することができる。次に、最適化基準を適用して、要求データセットを計算する、代数的関係の集まりのうちの１つを選択することができる。
【００１９】
別の態様では、本発明の上記態様のうちの１つ又は複数を実行するようにプログラムされた１つ又は複数のプロセッサを有するコンピュータシステムが提供される。コンピュータシステムは、データセットストアを提供する揮発性記憶装置及び／又は不揮発性記憶装置を含むことができる。別の態様では、１つ又は複数のハードウェアアクセラレータ又は他の回路が、本発明の上記態様のうちの１つ又は複数を実行するように構成される。別の態様では、本発明の上記態様のうちの１つ又は複数を実行するための実行可能命令を有するコンピュータ可読媒体が提供される。
【００２０】
本発明の上記各態様は、単独で使用してもよく、又は上記若しくは以下の説明において説明される本発明の他の態様と組み合わせてもよいことが理解される。
【００２１】
参照による援用
本明細書において述べる公開物及び特許出願はすべて、個々の各公開物又は特許出願がとりわけ個々に参照により本明細書に援用されると示されているかのように、参照により本明細書に同じ程度で援用される。
【００２２】
本発明の新規の特徴は、特に添付の特許請求の範囲に記載される。本発明の特徴及び利点のよりよい理解が、本発明の原理が利用される例示的な実施形態を記す以下の詳細な説明及び添付図面を参照することによって得られる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態例に関連して使用することができるコンピュータシステムの第１の構造例を示すブロック図である。
【図２】本発明の実施形態例に関連して使用することができるコンピュータネットワークを示すブロック図である。
【図３】本発明の実施形態例に関連して使用することができるコンピュータシステムの第２の構造例を示すブロック図である。
【図４Ａ】本発明の一実施形態例の論理的構造を示すブロック図である。
【図４Ｂ】本発明の一実施形態例のセットマネージャモジュールに記憶される情報を示すブロック図である。
【図５】本発明の一実施形態例による、データセットを提出するための方法のフローチャートである。
【図６】本発明の一実施形態例による、ステートメントを提出するための方法のフローチャートである。
【図７】ステートメント及び図６の方法のＸＳＮツリーの例を示す。
【図８】本発明の一実施形態例による、データセットを実現するための方法のフローチャートである。
【図９Ａ】本発明の一実施形態例による、代数的及び演算的に最適化するための方法のフローチャートである。
【図９Ｂ】本発明の代替の実施形態例による、代数的及び演算的に最適化するための方法のフローチャートである。
【図９Ｃ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図９Ｄ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図９Ｅ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図９Ｆ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図９Ｇ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図９Ｈ】本発明の実施形態例による、総合的に最適化するための方法を示す。
【図１０Ａ】ＯｐｔｏＮｏｄｅ構造の一例フィールドを示す。
【図１０Ｂ】本発明の一実施形態例によるＯｐｔｏＮｏｄｅ構造の一例のブロック図である。
【図１１】本発明の一実施形態例による、代数的関係からデータセットを計算するための方法のフローチャートである。
【図１２Ａ】本発明の一実施形態例によるＸＳＮツリー例のブロック図である。
【図１２Ｂ】本発明の一実施形態例によるＸＳＮツリー例のブロック図である。
【図１３Ａ】記憶装置マネージャの実施形態例において使用することができるバッファ連鎖の実施態様例を示すブロック図である。
【図１３Ｂ】記憶装置マネージャの実施形態例において使用することができるバッファ連鎖の実施態様例を示すブロック図である。
【図１３Ｃ】記憶装置マネージャの実施形態例において使用することができるバッファ連鎖の実施態様例を示すブロック図である。
【図１３Ｄ】記憶装置マネージャの実施形態例において使用することができるバッファ連鎖の実施態様例を示すブロック図である。
【図１４Ａ】一実施形態例による関係データからＸＭＬへの変換のブロック図である。
【図１４Ｂ】一実施形態例による関係データから有向グラフへの変換のブロック図である。
【発明を実施するための形態】
【００２４】
詳細な説明
本発明は様々な変更及び代替の構造に開かれているが、図面に示される実施形態をここで詳細に説明する。しかし、本発明を開示される特定の形態に制限する意図がないことを理解されたい。逆に、本発明が、添付の特許請求の範囲において表される本発明の趣旨及び範囲内にある変更、均等物、及び代替の構造をすべて包含することが意図される。
【００２５】
本発明の実施形態例は、拡張集合処理及び代数最適化を使用してデータを記憶し処理するためのシステム及び方法を提供する。一例では、拡張集合理論に基づく汎用データモデルを使用して、広範囲の異種フォーマットで提供されるデータからスカラー情報、構造情報、及び時間的情報を取り込むことができる。例えば、固定フォーマット、カンマ区切り値（ＣＳＶ）フォーマット、拡張可能マークアップ言語（ＸＭＬ）及び他のフォーマットのデータを、情報の損失なしで取り込み、効率的に処理することができる。これら符号化は、物理フォーマットと呼ばれる。同じ論理データを、任意の数の異なる物理フォーマットで記憶することができる。実施形態例は、同じ論理データを保持しながら、これらフォーマット間でシームレスに変換することができる。
【００２６】
厳密な数学的データモデルを使用することにより、実施形態例は、データ及びデータの相互関係の代数的完全性を維持し、時間的不変性（temporal invariance）を提供し、適応データ再構築を可能にすることができる。
【００２７】
代数的完全性により、代数的関係がモデリングする情報の操作をその代数的関係の操作で置換することが可能になる。例えば、様々なデータセットを記憶装置からはるかに遅い速度で検索して調べることを必要とせずに、代数表現をプロセッサ速度で評価することにより、クエリを処理することができる。
【００２８】
時間的不変性は、情報がシステムから破棄されるまで、情報の一定の値、構造、及び場所を維持することによって提供することができる。「ｉｎｓｅｒｔ」機能、「ｕｐｄａｔｅ」機能、及び「ｄｅｌｅｔｅ」機能等の標準的なデータベース演算により、部分的に、システムにおいてすでに識別されているデータへの参照を含む代数的表現として定義される新しいデータが作成される。このような演算は元のデータを変更しないため、実施形態例は、システムに含まれる情報を、記録されている履歴に存在するそのままの形態で随時調べる能力を提供する。
【００２９】
代数的完全性と組み合わせた適応データ再構築は、情報の論理的構造及び物理的構造を、論理的構造と物理的構造との間の厳密な数学的マッピングを維持しながら、変更することを許容する。実施形態例において、適応データ再構築は、クエリ処理を加速化すると共に、不揮発性記憶装置と揮発性記憶装置との間のデータ転送を最小化するのに用いることができる。
【００３０】
実施形態例は、これら特徴を使用して、ＸＭＬフォーマットで提供されるか、関係フォーマットで提供されるか、それとも他のデータフォーマットで提供されるかに関わりなく、動的に変化するデータのアクセス、統合、及び処理に当たって劇的な効率を提供することができる。特に、実施形態例は以下を提供することができる。
・あらゆる種類の企業情報を、等しい設備で、また、大規模なプログラミングなしで、数学的にモデリングして処理できるようにする、情報構造からの独立性
・データの事前構築化及びデータベースの抽出、変換、及びロード動作、並びに大半のデータベースインデックス構造及びそれに関連する記憶容量の解消
・冗長動作をなくすと共に、適応再構築作業データセットによって不揮発性／揮発性記憶装置境界性能バリアにわたるデータ転送を低減する適応最適化を介しての高速クエリ処理
・スケーラブルであり、超並列計算・記憶システムを十分に利用する高度に非同期かつ並列的な内部動作
・ステートレスエンティティ記録ひいては逐次再利用可能リソースの最小化による性能の向上及び耐故障性の増大
・記録履歴内にそれまでに存在したそのままの状態でデータベースを照会する能力
【００３１】
数学的データモデルにより、実施形態例を広範囲のコンピュータ構造及びシステムに使用することが可能であり、ありのままで超並列計算・記憶システムに役立つ。実施形態例に関連して使用することができるコンピュータ構造及びシステムのいくつかの例についてこれより説明する。
【００３２】
図１は、本発明の実施形態例に関連して使用することができるコンピュータシステム１００の第１の構造例を示すブロック図である。図１に示すように、コンピュータシステム例は、Intel Xeon（商標）プロセッサ、AMD Opteron（商標）プロセッサ、又は他のプロセッサ等の命令を処理するプロセッサ１０２を含むことができる。複数の実行スレッドを並列処理のために使用することができる。実施形態によっては、単一のコンピュータシステム内にあるのか、クラスタ内にあるのか、又はネットワークを経由してシステムに分散されているかに関わりなく、複数のプロセッサ又は複数のコアを有するプロセッサを使用してもよい。
【００３３】
図１に示すように、高速キャッシュ１０４をプロセッサ１０２に接続するか、又はプロセッサ１０２内に組み込んで、プロセッサ１０２が最近使用した、又は頻繁に使用する命令又はデータの高速メモリを提供することができる。プロセッサ１０２は、プロセッサバス１０８によってノースブリッジ１０６に接続される。ノースブリッジ１０６は、メモリバス１１２によってランダムアクセスメモリ（ＲＡＭ）１１０に接続され、プロセッサ１０２によるＲＡＭ１１０へのアクセスを管理する。ノースブリッジ１０６は、チップセットバス１１６によってサウスブリッジ１１４にも接続される。そして、サウスブリッジ１１４は周辺バス１１８に接続される。周辺バスは、例えば、ＰＣＩ、ＰＣＩ−Ｘ、ＰＣＩ  Ｅｘｐｒｅｓｓ、又は他の周辺バスであってよい。ノースブリッジ及びサウスブリッジは、プロセッサチップセットと呼ばれることが多く、プロセッサ、ＲＡＭ、及び周辺バス１１８上の周辺構成要素の間でのデータ転送を管理する。代替の構造によっては、別個のノースブリッジチップを使用する代わりに、ノースブリッジの機能をプロセッサ内に組み込んでもよい。
【００３４】
実施形態によっては、システム１００は、周辺バス１１８に取り付けられたアクセラレータカード１２２を含むことができる。アクセラレータは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）又は特定の処理を加速させる他のハードウェアを含むことができる。例えば、アクセラレータは、適応データ再構築又は拡張集合処理に使用される代数的表現の評価に使用することができる。
【００３５】
ソフトウェア及びデータは外部記憶装置１２４に記憶され、プロセッサによる使用のためにＲＡＭ１１０及び／又はキャッシュ１０４にロードすることができる。システム１００は、Linux又は他のオペレーティングシステム等のシステムリソースを管理するためのオペレーティングシステム及び本発明の実施形態例によるデータ記憶及び最適化を管理するための、オペレーティングシステムの上で実行されるアプリケーションソフトウェアを含む。
【００３６】
この例では、システム１００は、周辺バスに接続され、ネットワーク接続ストレージ（ＮＡＳ）等の外部記憶装置及び分散並列処理に使用できる他のコンピュータシステムへのネットワークインタフェースを提供するネットワークインタフェースカード（ＮＩＣ）１２０及び１２１も含む。
【００３７】
図２は、複数のコンピュータシステム２０２ａ、２０２ｂ、及び２０２ｃ並びにネットワーク接続ストレージ（ＮＡＳ）２０４ａ、２０４ｂ、及び２０４ｃを有するネットワーク２００を示すブロック図である。実施形態例では、コンピュータシステム２０２ａ、２０２ｂ、及び２０２ｃは、ネットワーク接続ストレージ（ＮＡＳ）２０４ａ、２０４ｂ、２０４ｃに記憶されているデータへのデータ記憶を管理すると共に、ＮＡＳ２０４ａ、２０４ｂ、及び２０４ｃへのデータアクセスを最適化することができる。数学的モデルは、データに用いることができ、コンピュータシステム２０２ａ、２０２ｂ、及び２０２ｃにわたる分散並列処理を使用した評価に用いることができる。コンピュータシステム２０２ａ、２０２ｂ、及び２０２ｃは、ネットワーク接続ストレージ（ＮＡＳ）２０４ａ、２０４ｂ、及び２０４ｃに記憶されているデータの適応データ再構築に並列処理を提供することもできる。これは単なる例にすぎず、広範囲の他のコンピュータ構造及びシステムを使用することが可能である。例えば、並列処理を提供するために、ブレードサーバを使用してもよい。バックプレーン経由でプロセッサブレードを接続して、並列処理を提供することができる。記憶装置はまた、バックプレーンに接続してもよいし、又は別個のネットワークインタフェース経由のネットワーク接続ストレージ（ＮＡＳ）としてもよい。
【００３８】
実施形態例では、プロセッサは別個のメモリ空間を保持し、他のプロセッサによる並列処理のために、ネットワークインタフェース、バックプレーン、又は他のコネクタを通してデータを送信してもよい。他の実施形態では、プロセッサのうちのいくつか又はすべてが、共有仮想アドレスメモリ空間を使用することができる。
【００３９】
図３は、実施形態例による共有仮想アドレスメモリ空間を使用するマルチプロセッサコンピュータシステム３００のブロック図である。システムは、共有メモリサブシステム３０４にアクセス可能な複数のプロセッサ３０２ａ〜３０２ｆを含む。システムは、複数のプログラマブルハードウェアメモリアルゴリズムプロセッサ（ＭＡＰ）３０６ａ〜３０６ｆをメモリサブシステム３０４に組み込む。各ＭＡＰ３０６ａ〜３０６ｆは、メモリ３０８ａ〜３０８ｆ及び１つ又は複数のフィールドプログラマブルゲートアレイ（ＦＰＧＡ）３１０ａ〜３１０ｆを含むことができる。ＭＡＰは構成可能な機能ユニットを提供し、各プロセッサと密に連携して処理するための特定のアルゴリズム又はアルゴリズムの部分をＦＰＧＡ３１０ａ〜３１０ｆに提供することができる。例えば、実施形態例では、ＭＡＰを使用して、データモデルに関する代数的表現を評価し、適応データ再構築を実行することができる。この例では、各ＭＡＰは、こうった目的のために、すべてのプロセッサからグローバルにアクセス可能である。一構成では、各ＭＡＰはダイレクトメモリアクセス（ＤＡＭ）を使用して関連メモリ３０８ａ〜３０８ｆにアクセスし、それにより、各マイクロプロセッサ３０２ａ〜３０２ｆから独立して、かつ各プロセッサ３０２ａ〜３０２ｆと非同期にタスクを実行することが可能である。この構成では、ＭＡＰは、結果を別のＭＡＰに直接供給して、アルゴリズムのパイプライン化及び並列実行を行うことができる。
【００４０】
上記コンピュータ構造及びシステムは単なる例にすぎず、汎用プロセッサ、コプロセッサ、ＦＰＧＡ、及び他のプログラマブル論理素子、システムオンチップ（ＳＯＣ）、特定用途向け集積回路（ＡＳＩＣ）、他の処理要素及び論理要素の任意の組み合わせを使用するシステムを含め、広範囲の他のコンピュータ構造及びシステムを実施形態例に関連して使用することができる。データ管理・最適化システムの全部又は部分をソフトウェア又はハードウェアに実装してよく、ランダムアクセスメモリ、ハードドライブ、フラッシュメモリ、テープドライブ、ディスクアレイ、ネットワーク接続ストレージ（ＮＡＳ）、及び他のローカル又は分散データ記憶装置及びシステムを含め、様々なあらゆるデータ記憶媒体を実施形態例に関連して使用してよいことが理解される。
【００４１】
実施形態例では、データ管理・最適化システムは、上記又は他のコンピュータ構造及びシステムのうちの任意のもので実行されるソフトウェアモジュールを使用して実施することができる。他の実施形態では、システムの機能は、ファームウェア、図３において参照されるようなフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブル論理素子、システムオンチップ（ＳＯＣ）、特定用途向け集積回路（ＡＳＩＣ）、又は他の処理要素及び論理要素に部分的又は完全に実装することができる。例えば、セットプロセッサ及びオプティマイザは、図１に示すアクセラレータカード１２２等のハードウェアアクセラレータカードの使用を通してハードウェアアクセラレータと共に実装することができる。
【００４２】
図４Ａは、ソフトウェアモジュール４００の論理的構造例を示すブロック図である。ソフトウェアは、コンポーネントベースであり、図４Ａに示すように特定の機能をカプセル化したモジュールに編制される。これは単なる例にすぎず、他のソフトウェア構造も同様に使用可能である。
【００４３】
この実施形態例では、１つ又は複数の様々な物理フォーマットで内部で記憶されたデータをシステムに提示することができる。システムは、拡張集合理論に基づいてデータの数学的表現を作成し、システム内で一意に識別するためのグローバル一意識別子（ＧＵＩＤ）をこの数学的表現に割当てることができる。この実施形態例では、データは、内部では１つ又は複数のデータセットに適用される代数的表現の形態で表現され、ここで、データは、代数的表現の作成時に定義されていてもよく、又は定義されていなくてもよい。データセットは、データセットのメンバと呼ばれるデータ要素セットを含む。一実施形態例では、要素は、演算子（operators）、値、及び／又は他のデータセットの組み合わせから形成されるデータ値又は代数的表現であることができる。この例では、データセットは代数的表現のオペランドである。様々なデータセット間の関係を定義する代数的関係は、セットマネージャ４０２ソフトウェアモジュールによって記憶、管理される。この実施形態では、すべてのデータセットが特定の代数的関係を通して関連するため、代数的完全性（algebraic integrity）が保持される。特定のデータセットがシステムに記憶されてもよく、又はされなくともよい。データセットによっては、他のデータセットとの代数的関係のみによって定義され、システムからそのデータセットを検索するために計算する必要があるものもある。データセットによっては、システムにまだ提供されていないデータセットを参照する代数的関係によって定義され、まだ提供されていないデータセットがいつか将来に提供されるまで計算することができないものさえある。
【００４４】
一実施形態例では、代数的関係及び代数的表現内で参照されるＧＵＩＤは、作成されてセットマネージャ４０２に記憶された後は変更されない。これは、他の同時管理装置をロックすることを気にせず及び関連するオーバーヘッドなしでのデータ管理を可能にする時間的不変性を提供する。対応するデータセットの代数的関係及びＧＵＩＤは、セットマネージャ４０２においてのみ添付され、新しい動作の結果として除去又は変更されない。これにより、オペランド及び代数的関係の拡大し続ける世界が生まれ、記録履歴内の情報のいかなるときの状態も再現することができる。この実施形態では、別個の外部識別子を使用して、論理データが経時変化しても同じ論理データを指すことができるが、一意のＧＵＩＤが、特定の時間に存在するそのままの状態のデータセットの各インスタンスを参照するために使用される。セットマネージャ４０２は、ＧＵＩＤに外部識別子及びＧＵＩＤがシステムに追加された時間を示すタイムスタンプを関連付けることができる。セットマネージャ４０２は、ＧＵＩＤに特定のデータセットに関する特定の情報を関連付けることもできる。この情報は、セットマネージャ４０２内に、リスト、テーブル、又は他のデータ構造（この実施形態例では、セットユニバースと呼ばれる）で記憶することができる。データセット間の代数的関係も、セットマネージャ４０２内のリスト、テーブル、又は他のデータ構造（この実施形態例では、代数キャッシュと呼ばれる）に記憶することができる。
【００４５】
実施形態によっては、セットマネージャ４０２は、不必要又は冗長的な情報をパージ（消去）することができると共に、記録履歴の時間範囲を制限するように時間的に再定義することができる。例えば、不必要又は冗長的な情報を自動的にパージすることができ、ユーザ設定又はコマンドに基づいて、時間的情報を定期的に潰すことができる。これは、指定時間よりも前のタイムスタンプを有するすべてのＧＵＩＤをセットマネージャ４０２から除去することによって達成することができる。これらＧＵＩＤを参照するすべての代数的関係もセットマネージャ４０２から除去される。他のデータセットが、これらＧＵＩＤを参照する代数的関係によって定義されている場合、代数的関係がセットマネージャ４０２から除去される前に、これらデータセットを計算して記憶する必要があり得る。
【００４６】
一実施形態例では、データセットを記憶装置からパージすることができ、システムは、必要であれば、後に代数的関係に頼ってそのデータセットを再び作成することができる。このプロセスは仮想化と呼ばれる。実際のデータセットがパージされると、かかるデータセットに関連する記憶容量を解放することができるが、システムは、同システムに記憶されている代数的関係に基づいてそのデータセットを識別する能力を保持する。一実施形態例では、大きいか、又は参照される回数が特定の回数閾値未満のデータセットを自動的に仮想化することができる。他の実施形態は、最近殆ど又は全く使用されなかったデータセットの仮想化、より高速のメモリ又は記憶容量を解放するためのデータセットの仮想化、又はセキュリティ強化のためのデータセット仮想化（仮想化後は、代数的関係にアクセスせずにデータセットにアクセスするのはより困難であるため）を含めた他の仮想化基準を使用することができる。こういった設定は、ユーザ構成可能又はシステム構成可能であることができる。例えば、セットマネージャ４０２がデータセットＡ並びにＡがデータセットＢとＣとの共通部分に等しいという代数的関係を含む場合、システムは、データセットＡをセットマネージャ４０２からパージし、必要であれば、データセットＢ及びＣ並びに代数的関係に頼ってデータセットＡを識別するように構成することができる。別の実施形態例では、２つ以上のデータセットが互いに等しい場合、そのデータセットのうちの１つを残してすべてをセットマネージャ４０２から削除することができる。これは、複数のセットが論理的に等しいが、異なる物理フォーマットである場合に発生し得る。このような場合、そのデータセットのうちの１つを残してすべてを除去し、物理的な記憶空間を節約することができる。
【００４７】
データセットの値をシステムによって計算又は提供する必要がある場合、オプティマイザ４１８が、データセットを定義する代数的関係をセットマネージャ４０２から検索することができる。オプティマイザ４１８は、セットマネージャ４０２からの代数的関係を使用して、データセットを定義する等価の追加の代数的関係を生成することもできる。この場合、次に、最も効率的な代数的関係を、データセットを計算するために選択することができる。
【００４８】
セットプロセッサ４０４ソフトウェアモジュールは、代数的表現で表されるデータセットの値を計算し、代数的関係を評価するために必要な算術的及び論理的な演算及び関数を実行するエンジンを提供する。セットプロセッサ４０４は、適応データ再構築も可能にする。データセットは、セットプロセッサ４０４の演算及び関数によって操作される際、物理的及び論理的に処理されて、続く演算及び関数を高速化する。セットプロセッサ４０４の演算及び関数は、一実施形態例では、ソフトウェアルーチンとして実装される。しかし、このような演算及び関数は、ファームウェア、図３において参照されるようなフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブル論理素子、システムオンチップ（ＳＯＣ）、特定用途向け集積回路（ＡＳＩＣ）、又は他のハードウェア又はこれらの組み合わせに部分的又は完全に実装することができる。
【００４９】
図４Ａに示すソフトウェアモジュールについてこれよりさらに詳細に説明する。図４Ａに示すように、ソフトウェアは、セットマネージャ４０２及びセットプロセッサ４０４並びにＳＱＬコネクタ４０６、ＳＱＬトランスレータ４０８、ＸＳＮコネクタ４１０、ＸＭＬコネクタ４１２、ＸＭＬトランスレータ４１４、ＸＳＮインタフェース４１６、オプティマイザ４１８、ストレージマネージャ４２０、エグゼクティブ４２２、及び管理者インタフェース４２４を含む。
【００５０】
図４Ａの実施形態例では、データセットについてのクエリ及び他のステートメントは、３つのコネクタのうちの１つ、即ちＳＱＬコネクタ４０６、ＸＳＮコネクタ４１０、又はＸＭＬコネクタ４１２を通して提供される。各コネクタは、特定のフォーマットでステートメントを受信及び提供する。一例では、ＳＱＬコネクタ４０６は、ユーザアプリケーション及びＯＤＢＣ準拠のサードパーティの関係データベースシステムを使用するための標準ＳＱＬ９２準拠ＯＤＢＣコネクタを提供し、ＸＭＬコネクタ４１２は、ユーザアプリケーション、対応サードパーティのＸＭＬシステム、及びソフトウェア４００の同じ又は他のシステム上の他のインスタンスを使用するための標準ウェブサービスＷ３Ｃ  ＸＱｕｅｒｙ準拠のコネクタを提供する。ＳＱＬ及びＸＱｕｅｒｙは、照会言語ステートメントをシステムに提供するためのフォーマット例であるが、他のフォーマットを使用してもよい。これらフォーマットで提供される照会言語ステートメントは、ＳＱＬトランスレータ４０８及びＸＭＬトランスレータ４１４により、システムが使用する拡張集合記法（ＸＳＮ：extended set notation）に変換される。ＸＳＮコネクタ４１０は、ステートメントをＸＳＮフォーマットで直接受け取るためのコネクタを提供する。拡張集合記法の一例について、以下、本明細書の末尾で説明する。拡張集合記法のこの例は、拡張データセットに関するステートメントをシステムに提示することができるという構文を含む。拡張集合記法のこの例は単なる例にすぎず、他の実施形態では、他の表記を使用してもよい。他の実施形態は、システムに提供されるステートメントから情報を取り込むために、異なる種類及びフォーマットのデータセット及び代数的関係を使用してもよい。
【００５１】
ＸＳＮインタフェース４１６は、コネクタからのすべてのステートメントに単一エントリポイントを提供する。ステートメントは、ＳＱＬトランスレータ４０８、ＸＭＬトランスレータ４１４、又はＸＳＮコネクタ４１０からＸＳＮフォーマットで提供される。ステートメントは、拡張集合記法のテキストベースの記述を使用して提供される。ＸＳＮインタフェース４１６は、テキスト記述を、システムが使用する内部表現に変換するパーサ（parser）を提供する。一例では、内部表現は、さらに後述するようにＸＳＮツリーデータ構造を使用する。ＸＳＮステートメントが解析されると、ＸＳＮインタフェース４１６はセットマネージャ４０２を呼び出して、ステートメント中で参照されるデータセットにＧＵＩＤを割当てることができる。ＸＳＮステートメントを表す全体的な代数的関係は、それぞれが代数関係である要素に解析することもできる。一実施形態例では、これら要素は、１〜３のデータセットから参照する、単一の演算で構成される表現を有する代数的関係であってよい。各代数的関係は、セットマネージャ４０２内の代数キャッシュに記憶することができる。各新しい代数的表現に、代数的表現によって定義されるデータセットを表すＧＵＩＤをセットユニバースに追加することができる。これにより、ＸＳＮインタフェース４１６は、システムに提示されたステートメントにおいて指定されるデータセットを参照する複数の代数的関係並びにステートメントを解析する際に作成することができる新しいデータセットを組み立てる。このようにして、ＸＳＮインタフェース４１６及びセットマネージャ４０２は、システムに提示されたステートメントから情報を取り込む。そして、システムがデータセットを計算する必要がある場合には、これらデータセット及び代数的関係を代数的最適化に使用することができる。
【００５２】
セットマネージャ４０２は、この例ではセットユニバースと呼ばれる、システムにとって既知のデータセットに関する情報を記憶するデータセット情報ストアを提供する。セットマネージャ４０２は、この例では代数キャッシュと呼ばれる、システムにとって既知のデータセット間の関係を記憶する関係ストアも提供する。図４Ｂは、一実施形態例によるセットユニバース４５０及び代数キャッシュ４５２内に保持される情報を示す。他の実施形態は、データセットに関する情報を記憶するために異なるデータセット情報記憶装置を使用してもよく、又はシステムにとって既知の代数関係に関する情報を記憶するために異なる関連ストアを使用してもよい。
【００５３】
図４Ｂに示すように、セットユニバース４５０は、システムにとって既知のデータセットのＧＵＩＤリストを保持することができる。各ＧＵＩＤは、システム内のデータセットの一意の識別子である。セットユニバース４５０は、特定のデータセットについての情報にも各ＧＵＩＤを関連付けることができる。この情報は、例えば、コネクタを通して提示されるステートメント内のデータセットを参照するために使用される外部識別子（特定のデータセットに対して一意であってもよく、又は一意でなくてもよい）、データセットがシステムにとって既知となった時間を示す日／時インジケータ、データセットのフォーマットを示すフォーマットフィールド、及びデータセットのタイプを示すフラグを有するセットタイプを含み得る。フォーマットフィールドは、システム内のデータセットの論理−物理変換モデルを示すことができる。例えば、同じ論理データを、システム内の記憶媒体に異なる物理フォーマットで記憶することが可能である。本明細書において使用する物理フォーマットとは、データが記憶媒体に記憶される際に論理データを符号化するフォーマットを指すものであり、使用される物理的な記憶媒体の特定の種類（例えば、ディスク、ＲＡＭ、フラッシュメモリ等）を指すものではない。フォーマットフィールドは、論理データが記憶媒体上で物理フォーマットにどのようにマッピングされるかを示す。例えば、データセットは、カンマ区切り値（ＣＳＶ）フォーマット、バイナリストリング符号化（ＢＳＴＲ）フォーマット、固定オフセット（ＦＩＸＥＤ）フォーマット、タイプ符号化データ（ＴＥＤ）フォーマット、及び／又はマークアップ言語フォーマットで記憶媒体に記憶することができる。タイプ符号化データ（ＴＥＤ）は、データ及びかかるデータのフォーマットを示す関連する値を含むファイルフォーマットである。これらは単なる例にすぎず、他の実施形態では、他の物理フォーマットを使用してもよい。セットユニバースは、データセットについての情報を記憶するが、基礎データは、この実施形態例では、他のどこにでも、例えば図１の記憶装置１２４、図２のネットワーク接続ストレージ２０４ａ、２０４ｂ、及び２０４ｃ、図３のメモリ３０８ａ〜３０８ｆ、又は他の記憶装置に記憶することができる。データセットによっては物理的な記憶装置に存在せず、システムにとって既知の代数的関係から計算されるものもある。場合によっては、データセットは、システムにまだ提供されていないデータセットを参照する代数関係によって定義され、いつか将来にそれらデータが提供されるまで計算できないことがある。セットタイプは、実現化と呼ばれる、データセットが記憶装置内で利用可能であるか否か、又は仮想化と呼ばれる、データセットが他のデータセットとの代数的関係によって定義されるか否かを示すことができる。実施形態によっては、作成過程中又はシステムからの除去過程中のデータセットを示す遷移タイプ等の他のタイプもサポートすることが可能である。これらは単なる例にすぎず、他の実施形態では、データセットについての他の情報をデータセット情報ストアに記憶してもよい。
【００５４】
図４Ｂに示すように、代数キャッシュ４５２は、あるデータセットを別のデータセットに関連付ける代数的関係のリストを保持することができる。図４Ｂに示す例では、代数的関係は、データセットが、１〜３つの他のデータセットに対して実行される演算又は関数に等しいことを指定することができる（図４Ｂでは「ｇｕｉｄ  ＯＰ  ｇｕｉｄ  ｇｕｉｄ  ｇｕｉｄ」として示される）。演算及び関数の例としては、射影関数、逆関数、濃度関数、結合関数、及び制約関数が挙げられる。追加の例を、拡張集合記法例の部分として本明細書の末尾において述べる。代数的関係は、データセットが別のデータセットに対して特定の関係を有することも指定することができる（図４Ｂでは「ｇｕｉｄ  ＲＥＬ  ｇｕｉｄ」として示される）。関係演算子の例としては、拡張集合記法例の部分として本明細書の末尾にさらに説明されるように、等しい、サブセット、及び互いに素並びにそれらの論理否定が挙げられる。これらは単なる例にすぎず、他の実施形態では、４つ以上のデータセットに対して作用する関数を含め、他の演算、関数、及び関係演算子を使用してもよい。
【００５５】
他のモジュールがセットマネージャ４０２にアクセスして、データセットの新しいＧＵＩＤを追加することができ、セットマネージャ４０２は、他の代数的関係の最適化及び評価に使用するためにデータセット間の既知の関係を検索することができる。例えば、システムは、第１のデータセットＡと第２のデータセットＢとの積集合であるデータセットを指定する照会言語ステートメントを受け取り得る。システムは、結果として得られるデータセットＣを決定し、返すことができる。この例では、この要求を処理しているモジュールは、セットマネージャ４０２を呼び出して、データセットＡとデータセットＢとの積集合の評価に有用であり得るデータセットＡ及びＢの既知の関係を代数キャッシュから得ることができる。記憶システムからデータセットＡ及びＢの基礎データを実際に検索せずに、既知の関係を使用して結果を特定することが可能であり得る。セットマネージャ４０２は、データセットＣの新しいＧＵＩＤを作成し、その関係を代数キャッシュに記憶することもできる（即ち、データセットＣはデータセットＡとデータセットＢとの積集合に等しい）。この関係が代数キャッシュに追加されると、将来の最適化及び計算に使用できるようになる。すべてのデータセット及び代数的関係はセットマネージャ４０２に保持することができ、時間的不変性を提供することができる。既存のデータセット及び代数的関係は、システムが新しいステートメントを受け取る際に削除又は変更されない。変更されずに、新しいステートメントが受信されると、新しいデータセット及び代数的関係が組み立てられ、セットマネージャ４０２に追加される。例えば、データをデータセットから除去するように要求される場合、新しいＧＵＩＤをセットユニバースに追加し、元のデータセット及び除去すべきデータとの差として代数キャッシュにおいて定義することができる。
【００５６】
オプティマイザ４１８は、代数的表現をＸＳＮインタフェース４１６から受け取り、計算に向けて最適化する。データセットを計算する必要がある場合（例えば、記憶システム内で実現化するため、又はユーザからの要求に応答して返すために）、オプティマイザ４１８は、そのデータセットを定義する代数的関係を代数キャッシュから検索する。そして、オプティマイザ４１８は、等価のデータセットを定義する他の代数的関係の複数の集まりを生成することができる。代数的置換は、代数キャッシュからの他の代数的関係を使用して行うことができ、代数的演算を使用して、代数的に等価の関係を生成することができる。一実施形態例では、可能な代数関係の集まりがすべて、指定されたデータセットに等しいデータセットを定義する代数キャッシュ内の情報から生成される。
【００５７】
次に、オプティマイザ４１８は、代数的関係の各集まりからデータセットを計算するための推定コストを判断することができる。コストは、コスト関数を代数的関係の各集まりに適用することによって判断することができ、コストの最も低い代数的関係の集まりを使用して、指定されたデータセットを計算することができる。一実施形態例では、コスト関数は、代数的関係の各集まりを計算するために必要なデータセットを記憶装置から検索し、その結果を記憶装置に記憶するために要する推定時間を判断する。同じデータセットが、代数的関係の集まり内で２回以上参照される場合、データセットを検索するコストは、最初に検索された後はメモリ内で利用可能になるため、その割り当ては１度だけでよい。この例では、要するデータ転送時間が最小の代数的関係の集まりが、要求されたデータセットを計算するために選択される。
【００５８】
オプティマイザ４１８は、異なるデータチャネルを介して異なる物理ロケーションに、且つ／又は異なる物理フォーマットで記憶されている同じ論理データを参照する代数的関係の異なる集まりを生成することができる。データは論理的に同じであるが、異なるＧＵＩＤを有する異なるデータセットを使用して、場所又はフォーマットが異なるが論理的には同じデータを区別することができる。代数的関係の異なる集まりは、異なる場所から、且つ／又は異なるフォーマットのデータセットを検索するためにかかる時間が異なり得るため、異なるコストを有し得る。例えば、論理的に同じデータが、同じデータチャネルを介して異なるフォーマットで利用可能であり得る。フォーマットの例としては、カンマ区切り値（ＣＳＶ）フォーマット、バイナリストリング符号化（ＢＳＴＲ）フォーマット、固定オフセット（ＦＩＸＥＤ）フォーマット、タイプ符号化データ（ＴＥＤ）フォーマット、及びマークアップ言語フォーマットを挙げることができる。他のフォーマットを使用してもよい。データチャネルが同じ場合、最小サイズを有する（ひいては記憶装置から転送するためのバイト数が最小の）物理フォーマットを選択することができる。例えば、カンマ区切り値（ＣＳＶ）フォーマットは、多くの場合、固定オフセット（ＦＩＸＥＤ）フォーマットよりも小さい。しかし、より大きなフォーマットがより高速のデータチャネルを介して利用可能な場合、より小さなフォーマットよりもより大きなフォーマットが選択され得る。特に、一般に、ディスクドライブ又はフラッシュメモリ等のより低速の不揮発性記憶装置で利用可能なより小さなフォーマットよりも、ＤＲＡＭ等の高速不揮発性メモリで利用可能なより大きなフォーマットが選択される。
【００５９】
このようにして、オプティマイザ４１８は、データ記憶装置からデータセットの基礎データにアクセスせずに、高速のプロセッサ速度をうまく利用して、代数的関係を最適化する。命令を実行するプロセッサ速度は、多くの場合、記憶装置からのデータアクセス速度よりも高い。代数的関係を計算前に最適化することにより、記憶装置からの不必要なデータアクセスを回避することができる。オプティマイザ４１８は、多数の等価の代数的関係及び最適化技法をプロセッサ速度で考慮し、表現を実際に評価するために必要なデータアクセスの効率を考慮することができる。例えば、システムは、データセットＡ、Ｂ、及びＤの積集合であるデータを要求するクエリを受け取り得る。オプティマイザ４１８は、これらデータセットに関する既知の関係をセットマネージャ４０２から取得し、評価前に表現を最適化することができる。例えば、データセットＣがデータセットＡとＢとの積集合に等しいことを示す既存の関係を代数キャッシュから取得することができる。データセットＡ、Ｂ、及びＤの積集合を計算するのではなく、オプティマイザ４１８は、データセットＣとＤとの積集合を計算して、等価の結果を得るほうが効率的であると判断することができる。この判断を下すに当たり、オプティマイザ４１８は、データセットＣがデータセットＡ及びＢよりも小さく、記憶装置からより高速に取得できることを考慮するか、又はデータセットＣが最近の演算に使用されており、より高速のメモリ又はキャッシュにすでにロードされていることを考慮することができる。
【００６０】
オプティマイザ４１８は、セット及び代数キャッシュの解析を通して発見された追加の関係及びセットの提示を介して、セットマネージャ４０２内の情報を継続的に充実化することもできる。このプロセスは、総合的最適化（comprehensive optimization）と呼ばれる。例えば、オプティマイザ４１８は、使用されていないプロセッササイクルを利用して関係及びデータセットを解析して、将来の要求の評価を最適化するに当たって有用であると予想される新しい関係を代数キャッシュに追加すると共に、セットをセットユニバースに追加することができる。関係が代数キャッシュに入力されてしまえば、セットプロセッサ４０４によって実行されている計算が完了していない場合であっても、オプティマイザ４１８は、後続するステートメントを処理しながらそれら計算を利用することができる。有用であり得る総合的最適化のための多くのアルゴリズムがある。これらアルゴリズムは、最近の時間期間中の使用パターン又は使用傾向を示す、限られた数のセットに対して繰り返される計算の発見に基づくことができる。
【００６１】
セットプロセッサ４０４は、最適化後に、代数的関係の選択された集まりを実際に計算する。セットプロセッサ４０４は、代数的拡張集合表現で指定されるデータセットを実現するために必要な算術的及び論理的な処理を提供する。一実施形態例では、セットプロセッサ４０４は、代数的関係において参照される演算及び関数を計算するために使用できる関数の集まりを提供する。関数の集まりは、特定の物理フォーマットのデータセットを受け取るように構成された関数を含み得る。この例では、セットプロセッサ４０４は、データセットに対して作用する複数の異なる代数的に等価の関数を提供し、結果を異なる物理フォーマットで提供することができる。代数的関係を計算するために選択される関数（オプティマイザ４１８によって最適化中に選択することができる）は、代数的関係内で参照されるデータセットのフォーマットに対応する。実施形態例では、セットプロセッサ４０４は複数の同時演算の並列処理が可能であり、ストレージマネージャ４２０を介して、データの入出力をパイプライン化して、不揮発性／揮発性記憶装置境界を渡る必要のあるデータ総量を最小化することができる。特に、選択された集まりからの代数的関係は、並列処理のために様々な処理リソースに割り当てることができる。こういった処理リソースは、図１に示すプロセッサ１０２及びアクセラレータ１２２、図２に示す分散コンピュータシステム、図３に示す複数のプロセッサ３０２及びＭＡＰ３０６、又は上記のうちの任意のものでのマルチスレッド実行を含むことができる。これらは単なる例に過ぎず、他の実施形態では、他の処理リソースを使用してもよい。
【００６２】
エグゼクティブ４２２は、実行の全体的なスケジューリング、計算リソースの管理及び割り当て、並びに適切なスタートアップ及びシャットダウンを実行する。
【００６３】
管理者インタフェース４２４は、システムを管理するためのインタフェースを提供する。実施形態例では、これは、データセットをインポート又はエクスポートするためのインタフェースを含むことができる。データセットはコネクタを通して追加することができるが、管理者インタフェース４２４は、多数のデータセット又はサイズの非常に大きなデータセットをインポートするための代替のメカニズムを提供する。データセットは、インタフェースを通してデータセットの場所を指定することによってインポートすることができる。次に、セットマネージャ４０２は、ＧＵＩＤをデータセットに割当てることができる。しかし、データにアクセスする必要がある要求を受け取るまで、基礎データにアクセスする必要はない。これにより、データをインポートして特定の構造に再フォーマットする必要なく、システムの非常に高速な初期化が可能になる。むしろ、データが実際に照会されるとき、データセット間の関係が定義されて、セットマネージャ４０２内の代数キャッシュに追加される。その結果、最適化は、（テーブルセット又は他の予め規定されたデータ構造に内蔵される予め規定された関係ではなく）データが使用される実際の方法に基づく。
【００６４】
大量データの管理に、実施形態例を使用することができる。例えば、データストアは、１テラバイト超、１００テラバイト、又は１ペタバイト以上のデータを含むことができる。データストアは、大容量の記憶容量を有する記憶アレイ又は分散記憶システムによって提供することができる。そして、データセット情報記憶ストアは多数のデータセットを定義することができる。場合によっては、データ情報記憶装置内には定義された１００万超、１０００万以上のデータセットがあり得る。一実施形態例では、ソフトウェアは２６４データセットスケールであるが、他の実施形態はより小さな又は大きなデータセットユニバースを管理してもよい。これらデータセットの多くは仮想的であってよく、他はデータストア内で実現化することができる。データセット情報ストア内のエントリを時折スキャンして、追加のデータセットを仮想化すべきか否か、又はデータセットを除去して、データセット情報ストアに取り込まれたデータセットを時間的に再定義するか否かを判断することができる。関係ストアは、データセット間の多数の代数的関係を含むこともできる。場合によっては、１００万超、１０００万以上の代数的関係が関係ストアに含まれ得る。場合によっては、代数的関係の数は、データセットの数よりも大きいことがある。多数のデータセット及び代数的関係は、データストア内のデータセットについて取り込むことができる膨大な量の情報を表し、拡張集合処理及び代数的最適化を使用して、極めて大量のデータの効率的な管理を可能にする。上記は単なる例にすぎず、他の実施形態は、異なる数のデータセット及び代数的関係を管理してもよい。
【００６５】
図５は、システムへの情報のインポートを容易にするために実装されるソフトウェアモジュールの一実施形態例を示すブロック図である。従来のデータベースシステムと異なり、本例のシステムは、提示されたデータセットに対してすぐには作用しない。むしろ、システムは、新しいデータセットへの参照をデータセット情報ストアに記憶する。一実施形態例では、これは、新しいＧＵＩＤをセットユニバースに追加することによって達成される。データセットがセットユニバースにとって既知になった後、システムはデータセットを使用することができる。
【００６６】
既述のように、情報は、管理者インタフェース４２４内に含まれる関数を通してシステムに追加することができ、これについて以下にさらに詳述する。情報をシステムに追加するこのような一方法は、情報セット５０６をインポートするためのコマンド５０１をインポート関数５０２に対して発行することによる。一実施形態では、コマンドは、インポート対象のデータセットの物理ロケーション、外部識別子、及びデータセットが記憶に向けてデータを符号化するために利用する論理−物理マッピングを示す値を含む。カンマ区切り値（ＣＳＶ）ファイル、拡張可能マークアップ言語（ＸＭＬ）ファイル、固定長ファイル（ＦＩＸＥＤ）、ＸＳＮフォーマットファイル、及び他を含めた様々な物理フォーマットをサポートすることができる。これに加えて、情報セットは様々な不揮発的又は揮発的記憶媒体に配置してよく、ローカルに接続されてもよく、又はネットワーク又は他の通信方法を介してリモートアクセスされてもよい。情報セットは、複数の異なる物理的な記憶媒体に分散してもよく、又はネットワークを介して受信されるデータパケット若しくはユーザからの入力（例えば、エンドユーザによってリアルタイムに入力される）等のリアルタイムデータストリームから提供されてもよい。コマンドが発行された後、インポート関数５０２は、コマンドを解析し、セットマネージャ５０３に関連する外部識別子及び物理フォーマット値と共にデータセットを作成せしめる。次に、セットマネージャ５０３は、関連するデータセットのＧＵＩＤを作成し、物理フォーマットタイプ値、外部識別子、関連するＧＵＩＤ、及びＧＵＩＤが実現化されていることを含む様々な情報をセットユニバースに入力する。次に、インポート関数５０２は、ストレージマネージャ５０４を呼び出して、データセットの物理ロケーション識別子とセットマネージャ５０３によって割当てられたＧＵＩＤとの関連（association）を作成する。詳細には、ストレージマネージャ５０４は、データと関連するＧＵＩＤとの物理的なパスを含むストレージマップ５０５にインデックス記録を追加する。データセット５０６は、ここで、システム内にインポートされ、制御権が呼び出し側に戻される。データセットが記憶装置に実現化されていない（即ち、仮想化されている）場合であっても、システムは、データセットについての情報を取り込むことができる。例えば、データセットＣがデータセットＡとＢとの積集合として定義され得る。データセットＡ及びＢは記憶装置内で実現化されているが、データセットＣは、代数キャッシュ内の関係「C=A UNION B」によってのみ定義され、データセットＣのＧＵＩＤがセットユニバースに追加されたときに、記憶装置内で実現化されていないことがある。
【００６７】
ステートメントの提出は、割当て又は関係をシステムに提供するプロセスである。ステートメントは、様々なインタフェースを通してシステムに提出することができる。一実施形態例では、３つのインタフェースが提供される。即ち、標準ＳＱＬ９２準拠ステートメントを提出するためのＳＱＬコネクタ、ＸＳＮを使用してステートメントを提出するためのＸＳＮコネクタ、及びウェブサーバＷ３Ｃ  ＸＱｕｅｒｙ準拠ステートメント及び他のＸＭＬベースのステートメントを提出するためのＸＭＬコネクタである。
【００６８】
図６は、システムへのステートメントの提出を容易にするソフトウェアモジュールをどのように実装することができるかの一実施形態例を示すブロック図である。この例では、標準ＳＱＬコマンドが、ＳＱＬコネクタ６０１を通してシステムに提出される。ＳＱＬコマンドは、もう１つの標準ＳＱＬ９２準拠ＳＱＬステートメントを含むことができる。ＳＱＬコネクタ６０１はまず、提出時間を取り込み、提出されたステートメント内に含まれるすべてのセットに時間値を確立する。次に、コマンドは解析されて、ＳＱＬステートメントの構文が正しいことを検証する。構文エラー又は準拠エラーがあった場合、エラーメッセージが呼び出し側に返され、提出は停止される。エラーがない場合、ＳＱＬコネクタ６０１は、ＳＱＬコマンドの内部ナビゲート可能表現を構築し、これがＳＱＬトランスレータ６０２に出力される。ＳＱＬトランスレータ６０２は、次に、ＳＱＬコマンドの内部ナビゲート可能表現を適切な等価のＸＳＮステートメントに変換する。変換後、結果として生成されたＸＳＮステートメントは、将来の処理のためにＸＳＮインタフェース６０３に渡される。次に、各ステートメントは、そのテキストＸＳＮ表現をＸＳＮツリーと呼ばれる内部構造に変換される。ＸＳＮツリーは、ＸＳＮステートメントのメンバをプログラム的に調べる手段及びステートメントの要素をナビゲートする手段を提供する。
【００６９】
次に、ＸＳＮツリーが調べられて、ステートメントが割当て又は関係を表すか否かが判断される。ステートメントが割当てである場合、ＧＵＩＤがセットマネージャ４０２によってステートメント内で指定される代数的表現に割当てられる。次に、ＸＳＮツリーが調べられて、ＧＵＩＤが、表現内のすべてのデータセット及び演算に割当てられ、表現が任意の明示的な集合又は任意の冗長的割当てを含むか否かが判断される。明示的な集合とは、標準ＳＱＬ「ｉｎｓｅｒｔ」ステートメントのコンテキスト内で発生し得るような、ステートメントの部分としてシステムに入力される集合のことである。冗長的割当てとは、代数キャッシュ内にすでにある演算及び引数を含む割当てのことである。明示的な集合の場合、セットマネージャ４０２はこれら集合に新しいＧＵＩＤを割当て、これら集合はセットプロセッサ４０４によってすぐに実現化される。冗長的割当ての場合、同じ演算及び右値（ｒｖａｌｕｅ）を含む表現を探して代数キャッシュを探索することによって発見され、代数キャッシュ内の既存の割当てエントリの左値（ｌｖａｌｕｅ）のＧＵＩＤが、セットマネージャ４０２から検索され、表現内の助長的割当てのｌｖａｌｕｅに割当てられる。割当てが冗長的ではない場合、新しいＧＵＩＤが、セットマネージャ４０２からの割当てに提供され、表現内の割当てのｌｖａｌｕｅに割当てられる。ステートメントによって指定される複雑な代数的関係は、原始的（原子的）な関係及び割当ての集まりに分解することもできる。ＧＵＩＤをこれら関係及び割当てに提供することができ、対応する代数的関係を代数キャッシュに追加することができる。
【００７０】
すべての明示的な集合及び割当てのｌｖａｌｕｅにＧＵＩＤが割当てられると、制御権がＳＱＬコネクタ６０１に戻される。必要であれば、次に、第２の呼び出しがＸＳＮインタフェース６０３に対して行われて、呼び出し側に戻すものと予想されるあらゆる集合が実現化される。そして、実現化された集合は、呼び出し側に返される。
【００７１】
図７は、図６の方法でシステムに提出することができるステートメントの一例を示す。この例では、ユーザは、標準的な商業取引に関する特定の情報を探してデータベースを照会している。要求は、標準ＳＱＬステートメント７０１によって表される。この事例で要求されているＯＲＤＥＲＫＥＹは「１２３４５」である。詳細には、この例のユーザは、品物の割引き、発送日、及び品物に対するコメントを特定の顧客注文番号「１２３４５」で要求している。情報は、２つのテーブル、即ちＬＩＮＥＩＴＥＭ及びＯＲＤＥＲＳから取得される。Ｌ＿ＯＲＤＥＲＫＥＹフィールドがＯ＿ＯＲＤＥＲＫＥＹに等しいことに基づいて、２つのテーブルが結合される。ＳＱＬステートメント７０１は、ユーザによってＳＱＬコネクタ６０１に渡される。ＳＱＬトランスレータ６０２は、ＳＱＬステートメントの内部ナビゲート可能表現を適切な等価のＸＳＮステートメント７０２に変換する。ＬＩＮＥＩＴＥＭテーブル及びＯＲＤＥＲＳテーブルの列又はフィールドが、関係データベースに固有ではない表現に変換されたことに留意する。特に、ＬＩＮＥＩＴＥＭテーブルの列又はフィールドは、ここでは、「１」〜「１６」のドメインによって表されており、ＯＲＤＥＲＳテーブルの列又はフィールドは、ここでは、「１７」以上のドメインによって表されている。表現内の最も内側の関数から開始して、ＳＱＬステートメント７０１の結合演算が、ｒｄｍＪｏｉｎ演算に変換され、ＬＩＮＥＩＴＥＭ、ＯＲＤＥＲＳ、及びＮＵＬＬが３つのパラメータとして渡される。次に、ｒｄｍＪｏｉｎの結果はｒｄｍＲｅｓｔに渡され、ｒｄｍＲｅｓｔは、結合演算の結果であるデータを、ＬＩＮＥＩＴＥＭデータセットのＬ＿ＯＲＤＥＲＫＥＹドメインであるドメイン「１」が定数「１２３４５」に等しく、ＬＩＮＥＩＴＥＭデータセットからのＬ＿ＯＲＤＥＲＫＥＹフィールドであるドメイン「１」もＯＲＤＥＲＳデータセットからのＯ＿ＯＲＤＥＲＫＥＹドメインのドメイン「１７」に等しいデータのみに制限する。次に、ＸＳＮステートメント７０２は、将来の処理のために、ＸＳＮインタフェースに渡される。
【００７２】
ＸＳＮインタフェース６０３は、提出時間を記録して、提出されたステートメント内に含まれる集合に時間的な値を確立する。次に、ステートメントは、ＸＳＮステートメント７０２からＸＳＮツリー７０３に変換される。ＸＳＮツリーの構造については、図１２Ａ及び図１２Ｂに関連してさらに後述する。従来のプロセスの一環として、ＧＵＩＤが作成されるか、又はセットマネージャ４０２から検索され、対応する集合のＸＳＮツリー７０３内に挿入する。次に、制御権はＳＱＬコネクタ６０１に戻される。
【００７３】
この事例の実施形態例は結果集合を要求したため、次に、第２の呼び出しがＸＳＮインタフェース６０３に対して行われ、呼び出し側に返すものと予想されるあらゆる集合が実現化される。ＸＳＮツリー７０３は、次に、オプティマイザ６０４に戻され、ここでＸＳＮツリー７０３が効率に関して最適化され、最適化ＸＳＮツリー７０４が生成される（ここでは、単に例示のために、ツリーフォーマットではなく表現フォーマットで示されている）。この事例では、オプティマイザが効率のためにｒｄｍＲｅｓｔをｒｄｍＪｏｉｎに併合することに留意する。最適化ＸＳＮツリー７０４は、次に、セットプロセッサ６０５に渡され、ここで、ＸＳＮツリー内の代数的関係の集まりが計算される。そして、実現化された集合が呼び出し側に戻される。
【００７４】
図８は、集合実現化を容易にするために実装されるソフトウェアモジュールの一実施形態例を示すブロック図である。集合実現化とは、集合のメンバシップを計算し、このような集合の物理的表現を記憶装置内で実現化するプロセスである。集合実現化は、ＳＱＬコネクタ又はＸＭＬコネクタ等の実現化をサポートするシステムの外部インタフェースから、又はセットエクスポートプロシージャの一部としてエグゼクティブソフトウェアモジュールから起動することができる。この実施形態例では、エクスポートコマンドがエグゼクティブ８０１に発行される。コマンドは、エクスポートする外部識別子又はＧＵＩＤを記憶パスと共に識別することができる。そして、エグゼクティブ８０１は、外部識別子又はＧＵＩＤをＸＳＮインタフェース８０２に渡す。外部識別子がコマンド内で識別された場合、ＸＳＮインタフェース８０２は、外部識別子をセットマネージャ８０３に渡す。セットマネージャ８０３は、外部識別子に関連付けられたＧＵＩＤを判断し、そのＧＵＩＤをＸＳＮインタフェース８０２に返す。この参照は、ＧＵＩＤに関連付けられた時間値に相対して行われる。ユーザによる別段の指定がない限り、実施形態例は、外部識別子に関連付けられた最新のＧＵＩＤを使用する。関連付けられたＧＵＩＤが特定されると、外部識別子が、関連付けられたＧＵＩＤで置換される。実現化すべきＧＵＩＤは、コマンド内で直接指定されるか、それとも外部識別子から取得されるかに関わらず、次に、セットマネージャ８０３に渡され、実現化されるか否かが判断される。ＧＵＩＤに関連付けられたデータセットが既に実現化されている場合、制御権はエグゼクティブ８０１に戻される。ＧＵＩＤに関連付けられたデータセットが実現化されていない場合、ＧＵＩＤはオプティマイザ８０４に提出されて、実現化される。次に、オプティマイザ８０４は、ＧＵＩＤに関連付けられたデータセットを表す代数的関係の最適な集まりを判断する。次に、この代数的関係の集まりはセットプロセッサ８０５に渡され、セットプロセッサ８０５において計算される。代数的関係の集まりがセットプロセッサ８０５に提出されると、制御権はエグゼクティブ８０１に戻される。次に、エグゼクティブ８０１は、ストレージマネージャがデータセットからのデータをエグゼクティブ８０１に提供することを要求し、エグゼクティブ８０１は次に、エクスポートコマンド内で指定されるパス名を使用してデータを記憶装置に記憶する。
【００７５】
図９Ａは、代数的及び演算的なオプティマイザソフトウェアモジュールの一実施形態例を示すブロック図である。オプティマイザは、セットプロセッサ９０９に提出する前に、代数的関係の集まりを処理して、代数的及び演算的に最適化する。システム環境及びシステムに関連する様々な制限又は性能の弱点に基づいて、代数的関係のどの集まりが最も効率的であるかを判断するために使用可能な多くの方法がある。
【００７６】
図９Ａの実施形態例では、オプティマイザは、２つの基本的な原理に関して動作する。第１は、前に実現化されているデータセットを単に再利用するコストよりも低いコストを有するデータセット実現化代替プランがないことである。第２は、記憶装置境界性能バリアを越えて検索されるデータ量を最小化すべきことである。他の実施形態例では、特に最新技術は変化するため、他の原理を適用することも可能である。上記基本原理は、実施形態例では、３つの最適化ルーチン、即ちｆｉｎｄＡｌｔＯｐｓルーチン９０４、ｆｉｎｄＭｅｔａＧｕｉｄｓルーチン９０５、及びｆｉｎｄＡｌｔＧｕｉｄｓルーチン９０６を通して実現される。他の最適化ルーチンを使用してもよく、より多数又は少数の最適化ルーチンがシステムに存在してよいことに留意することが重要である。実施形態例では、最適化ルーチンは、可能な限り高速でコストの十分に低い代数的関係の集まりをもたらす可能性がより高い最適化を試みるように設計される特定の順序で実行される。
【００７７】
ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３は、さらに後述するように、最適化ルーチンが実行される前、及び各最適化ルーチンが実行された後に実行される。代数的関係の特定の集まりの実行に関するコストは、システムが代数的関係の集まりを計算するために必要なデータセットを記憶装置から検索するためにかかる時間を推定することによって決定される。推定検索時間は、情報を各Ｉ／Ｏ記憶装置バリアを越えて検索することができる速度及びかかる記憶装置バリアを越えて検索する必要のある推定情報量に基づいて計算することができる。コスト決定は、情報が同じＩ／Ｏチャネルを介して読み出されるのか、それとも異なるＩ／Ｏチャネルを介して読み出されるのか、及び特定の情報が表現の複数のサブパーツに使用されているか否か等の他の要因を考慮することもでき、これらは両方とも性能に影響し得る。これら最適化技法は、最適化ルーチン実行時のシステムの状態に応じて異なる最適化結果となり得る。例えば、同じ論理データを有する異なるデータセットが、異なるサイズを有する異なるデータフォーマットで提供され得る。これらが同じＩ／Ｏチャネルを介して利用可能な場合、最も小さいフォーマットを有するデータセットが選択され得る。しかし、最近アクセスされ、高速メモリ又はキャッシュ内に既に利用可能なデータセットについては、より大きなフォーマットが選択され得る。
【００７８】
実施形態例では、ＸＳＮインタフェース９０１は、代数的関係の集まりに関連するセットを実現化するために、オプティマイザソフトウェアモジュールを呼び出す。ＸＳＮインタフェース９０１は、実現化すべき集合のＧＵＩＤをオプティマイザソフトウェアモジュール内のｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２に渡す。ｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２は、代数キャッシュからＧＵＩＤによって識別される１つ又は複数の集合を定義する１つ又は複数のオリジナルの代数的関係を検索する。これら代数的関係は、始原表現（genesis expression）と呼ぶことができる。次に、ｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２は、かかる始原表現のＯｐｔｏＮｏｄｅツリー表現を構築する。ＯｐｔｏＮｏｄｅツリーをさらに詳細に後述し、より原始的な代数的関係の集まりとして代数的関係を表すために使用することができる。次に、オプティマイザソフトウェアモジュールは、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３を実行して、最低コスト始原表現を決定する。ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３により、コストが最低であると分かった始原表現が、実行するのに十分に安価であると判断した場合、さらなる最適化は中止され、かかる始原表現の代数的関係が、後述するｒｅａｌｉｚｅＮｏｄｅルーチン９０８に提出される。
【００７９】
ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３が、コストが最低であると分かった始原表現が、実行するのに十分に安価ではないと判断した場合、ｆｉｎｄＡｌｔＯｐｓルーチン９０４が実行されて、代替の演算を見つける。このルーチンは、拡張集合理論代数を使用して始原表現の代替版を合成する。合成された代替表現は、潜在的に実行コストがより低く、且つ代数キャッシュ内で容易に識別されるように構築される。表現合成は、表現の「形態」の認識及び代数的に等価であるが、計算コストがより低く、且つ／又は代数キャッシュ内で認識される可能性がより高い他の形態の置換に基づいて行われる。簡単な例は、２つの結合集合に対する制限である。何らかの表記省略表現を使用して、これはSETA=R(J(a,b,c),d)と表現することができる。しかし、結合演算は制限を行うことも可能であり、等価表現はSETA=J(a,b,CP(c,d))である。これら形態は両方とも、計算に同量の入力データを必要とするが、第２の形態は、より少ない出力データを生成する。これは、第２の形態がより少ない計算及びＩ／Ｏリソースを必要とすることを意味する。第２の形態が第１の形態よりも好ましいか否かは、代数キャッシュから何が利用可能であるか、及びどの集合が不揮発性記憶装置ですでに実現化されているかに依存する。しかし、オプティマイザ４１８内で両形態を探ることにより、より効率的な代替を見つける確率を高くすることができる。
【００８０】
ｆｉｎｄＡｌｔＯｐｓルーチン９０４が、代替の表現が発見されたことを示す場合、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３が再び実行されて、最小コスト始原表現及び代替表現に基づいて最小コスト表現が見つけられる。ここでも、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３が、コストが最低であると分かった表現が、実行するのに十分に安価であると判断した場合、さらなる最適化は中止され、かかる表現の代数的関係が、後述するｒｅａｌｉｚｅＮｏｄｅルーチン９０８に提出される。最適化を中止するための閾値は、処理リソースの相対速度及びデータチャネル及び／又は他のシステム特質に基づいて決定することができる。一例では、閾値は１０ＭＢのデータ転送に設定される。この例では、通常、１０ＭＢのデータを約１／１０秒で転送することができるため、さらなる最適化は中止され、集合は単純に表現から計算される。
【００８１】
始原表現及びｆｉｎｄＡｌｔＯｐｓルーチン９０４によって識別される始原表現の代替のいずれも、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３の実行によって決定されるように、実行には十分に安価ではなかった場合、次の最適化ルーチンが実行される。実施形態例では、次の最適化ルーチンは、ｆｉｎｄＭｅｔａＧｕｉｄｓルーチン９０５である。ｆｉｎｄＭｅｔａＧｕｉｄｓルーチン９０５は、増分的に小さなコストを有するすべての表現を見つけて、実行のためにセットプロセッサに提出する。増分的に小さなコストを有する表現は、多くの場合、メタデータのみを含む。低コスト演算の例としては、述語クロス積（predicate cross product）（ＣＰ演算）、出力範囲変換（output scope transform）（ＯＳＴ演算）、及び左右（ｒｄｍＳＦＬ演算及びｒｄｍＳＦＲ演算）の関係データモデルソートドメインが挙げられる。これら演算は、典型的には、ユーザデータモデル内のメタデータに対して作用し、追加のメタデータを生成する。物理的な集合サイズは、典型的には、５００バイト程度未満であり、オプティマイザ４１８の実行閾値よりもはるかに低い高速計算の最有力候補になる。したがって、これら演算は、最小閾値を満たすか否かをテストせずに、単にオプティマイザ４１８からすぐに実行することができる。次に、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３が再び呼び出されて、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３に対する前の呼び出しから決定された最小費用表現（least expensive expression）とｆｉｎｄＭｅｔａＧｕｉｄｓルーチン９０５からの表現との間として最小コスト表現（least-costly expression）が選択される。再び、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３により、コストが最低であると分かった表現が、実行するのに十分に安価であると判断された場合、さらなる最適化は中止され、かかる表現の代数的関係が、後述するｒｅａｌｉｚｅＮｏｄｅルーチン９０８に提出される。
【００８２】
ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３によって識別された最低コスト表現が、まだ十分に安価な実行費用ではない場合、ｆｉｎｄＡｌｔＧｕｉｄルーチン９０６が実行される。ｆｉｎｄＡｌｔＧｕｉｄｓルーチン９０６は、１つ又は複数の下位表現（subexpression）を、前に実現化された集合を記述する代替の表現で置換できるか否かを判断する。実現化された集合を再使用するコストは常に、かかる集合を実現化するために必要な表現を実行するコストよりも低いため、このルーチンを使用して、さらなるコスト削減を提供することができる。かかる置換の一例について関係データモデルを使用して説明することができる。テーブル（ボックス（ＢＯＸＥＳ）と呼ばれる）内の特定のフィールド（サイズ（ＳＩＺＥ）と呼ばれ、テーブルの３番目のフィールド）が、１〜１００の範囲の値を有するものと仮定する。次に、ユーザが、５０未満のサイズのすべてのボックスを要求するクエリ（Ｑ１）を発行する。これは、ＸＳＮでＱ１＝ｒｄｍＲＥＳＴ（ＢＯＸＥＳ，｛｛｛“ＬＴ”．＜”３”，”ＣＯＮＳＴ”．”５０”｝｝｝）として表現される。しばらくしてから、ユーザは、サイズが２５未満のすべてのボックスを要求する。これは、Ｑ２＝ｒｄｍＲＥＳＴ（ＢＯＸＥＳ，｛｛｛“ＬＴ”．＜”３”，”ＣＯＮＳＴ”．”２５”＞｝｝｝）として提出される。これら両クエリにおいて、提出されたまま実行される場合、ボックスデータセット全体を読み出して、結果Ｑ１及びＱ２を特定しなければならない。しかし、メタデータセット｛｛｛“ＬＴ”．＜”３”，”ＣＯＮＳＴ”．”５０”｝｝｝及び｛｛｛“ＬＴ”．＜”３”，”ＣＯＮＳＴ”．”２５”＞｝｝｝の数学的検査により、第２の集合によって制限されるいずれの集合も第１のサブセット（部分集合）であることが示された。したがって、代数的置換を行うことができ、次の表現が生成された。Ｑ２＝ｒｄｍＲＥＳＴ（Ｑ１，｛｛｛“ＬＴ”．＜”３”，”ＣＯＮＳＴ”．”２５”＞｝｝｝）。Ｑ１が不揮発性記憶装置ですでに実現化されている場合、これは、Ｑ１のサイズがボックスのサイズ未満でなければならず、したがって、転送のために必要なＩ／Ｏコストがより低いことを示すことができる。そして、Ｑ１がすでに実現化されている場合、これは、当初提出された表現よりもＱ２を評価する全体的により安価な手段を提供する。
【００８３】
下位表現が任意の適した代替表現で置換された後、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３が再び実行されて、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３に対する前の呼び出しから決定された最小費用表現とｆｉｎｄＡｌｔＧｕｉｄｓルーチン９０６からの表現との間として最小コスト表現が選択される。ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３により、コストが最低であると分かった表現が、実行するのに十分に安価であると判断された場合、さらなる最適化は中止され、かかる表現が、後述するｒｅａｌｉｚｅＮｏｄｅルーチン９０８に提出される。
【００８４】
上述した最適化作業が完了した後、オプティマイザはｒｅａｌｉｚｅＮｏｄｅルーチン９０８を呼び出す。ｒｅａｌｉｚｅＮｏｄｅルーチン９０８は、ｏｐｔｏＮｏｄｅツリーをＸＳＮツリーに変換し、ｓｐＰｒｏｃｅｓｓＸｓｎＴｒｅｅルーチンを呼び出して、ＸＳＮツリーを実行のためにセットプロセッサ９０９に提出し、ＸＳＮツリーを削除し、制御権をオプティマイザソフトウェアモジュールに戻し、そして、オプティマイザソフトウェアモジュールは制御権をＸＳＮインタフェース９０１に戻す。
【００８５】
図９Ｂは、代数的及び演算的なオプティマイザソフトウェアモジュールの別の実施形態例を示すブロック図である。図９Ａに提示した実施形態例と異なり、この実施形態例での最適化ルーチンは、各ＯｐｔｏＮｏｄｅツリーにリーフからルートに進んで適用される。この手法は、各最適化ルーチンの結果を表現に対する引数として提供し、最適化のさらなる機会を発生させるが、実行時間の増大を代償とする。大幅な最適化をさらに行うことができる状況下では、この手法が好ましいであろう。
【００８６】
この実施形態例での実施態様は、２つのみの最適化ルーチン、即ちｆｉｎｄＯｐｅｒａｔｉｏｎａｌルーチン９１３及びｆｉｎｄＡｌｇｅｂｒａｉｃルーチン９１４を使用する。前の実施形態例と異なり、ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３は、ｆｉｎｄＯｐｅｒａｔｉｏｎａｌルーチン９１３及びｆｉｎｄＡｌｇｅｂｒａｉｃルーチン９１４が両方とも実行された後でのみ実行される。ｆｉｎｄＬｅａｓｔＣｏｓｔルーチン９０３の機能は、前の実施形態例において述べた機能と同じである。
【００８７】
前の実施形態でのように、ＸＳＮインタフェース９０１はオプティマイザソフトウェアモジュールを呼び出し、実現化すべき集合のＧＵＩＤをｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２に渡す。ｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２は、前の実施形態例において述べたものと同じである。ｂｕｉｌｄＥｘｐｒｅｓｓｉｏｎｓルーチン９０２が表現のＯｐｔｏＮｏｄｅツリーを構築した後、ｆｉｎｄＯｐｅｒａｔｉｏｎａｌルーチン９１３が実行されて、代替の演算が見つけられる。このルーチンは、前の実施形態例において述べたｆｉｎｄＡｌｔＯｐｓルーチン９０４と同一の機能を実行する。
【００８８】
ｆｉｎｄＯｐｅｒａｔｉｏｎａｌルーチン９１３が完了した後、変更されたＯｐｔｏＮｏｄｅツリーがｆｉｎｄＡｌｇｅｂｒａｉｃルーチン９１４に渡されて、追加の代替表現が見つけられる。ｆｉｎｄＡｌｇｅｂｒａｉｃルーチン９１４は、ＯｐｔｏＮｏｄｅツリー上で右から左に、且つ最も内側の表現から最も外側の表現に向かって繰り返される。この繰り返し順序は、追加の代替表現を見つける潜在性を最大化する。各表現は、１つの演算及び１〜３つの引数を含む場合、引数と演算との各組み合わせが、１度に１つずつｆｉｎｄＥｘｐｅｒｓｓｉｏｎｓルーチン９１５に提示される。次に、ｆｉｎｄＥｘｐｒｅｓｓｉｏｎｓルーチン９１５は、代替の表現の発見又は合成を意図して、表現の演算に特定のコードを実行する。演算に特定のコードは、代数キャッシュからの引数の代数的置換を実行し、表現内に含まれる低コスト表現の計算を実行し、表現自体を計算し、表現又は任意の表現の引数の代替形態を合成することができる。次に、代替表現はいずれも、演算に特定のコードによってＯｐｔｏＮｏｄｅツリーの適切な場所に追加される。
【００８９】
上述した最適化作業が完了した後、オプティマイザは、前の実施形態例でのｒｅａｌｉｚｅＮｏｄｅルーチンと同じｒｅａｌｉｚｅＮｏｄｅルーチン９０８を呼び出す。次に、制御権がＸＳＮインタフェース９０１に戻される。
【００９０】
システムは、総合的最適化も実行することができる。総合的最適化は、関係及びデータセットを解析して、将来の要求の評価を最適化するに当たって有用であると予想される新しい関係を代数キャッシュに追加すると共に、集合をセットユニバースに追加する。これは、システムに対する過去の要求のパターンに基づいて実行することができ、このパターンを使用して、将来の同様の要求を予想して最適化を実行することができる。この総合的最適化は、予備プロセッササイクルを使用することによってバックグラウンドで実行することができる。図９Ｃ、図９Ｄ、図９Ｅ、図９Ｆ、図９Ｇ、及び図９Ｈは、総合的最適化方法の例を示す。しかし、様々な他の総合的最適化も可能であり、これら実施形態例は、本発明内のほんの少数の例にすぎない。
【００９１】
図９Ｃは、個々のスカラー値又は自由範囲のスカラー値がサブセット（部分集合）のメンバシップを識別する一例を示す。この性質のクエリは、データを等濃度の集合に分割する部分集合であって、特定の範囲の値をそれぞれ含む部分集合を作成することから恩恵を受けることができる。例えば、データセットは、図９Ｃにおいて９５０で示すデータ分布を有し得る。このデータセットは、図９Ｃにおいて９５０で示す部分集合１〜６等の等濃度の複数のデータセットに分割することができる。この一例は、特定のデータの後又は前に発生するすべてのトランザクションを要求することである。この最適化は、セットプロセッサが同様の性質の将来の部分集合を計算するために調べなければならないデータ量を低減するという利点を有する。総合的最適化ルーチンは、代数キャッシュの検査によりある範囲のスカラー値を使用する特定の集合から相当数の関係制約を検出することにより、この状況を識別する。これらエントリから、オプティマイザは、分割すべきスカラー値の範囲を確立するための最大スカラー値及び最小スカラー値を決定する。次に、オプティマイザは、分割部分集合数を、利用可能なＩ／Ｏチャネルの平均数に等しくなるように決定する。最後に、オプティマイザは、各分割部分集合につき、適切な関係を代数キャッシュに挿入すると共に、集合をセットユニバースに挿入する。オプティマイザは、部分集合の和集合が集合に等しいことを示す関係を挿入し、セットプロセッサを呼び出して各分割部分集合を計算することもできる。
【００９２】
図９Ｄは、分割部分集合内のメンバシップの基準が特定の範囲内に入るスカラー値に基づくことを除き、図９Ｃの最適化と同様の総合的最適化の一例を示す。この一例は、所望の範囲の顧客年齢に対して所望の部分集合を判断することである。例えば、データセット内のデータが、図９Ｄにおいて９５４で示される特定の範囲内に入り得る。このデータセットは、図９Ｄにおいて９５６で示されるように、これら各範囲を含む部分集合１〜５に分割することができる。他の総合的最適化例と同じように、この種類の分割は、セットプロセッサによって調べるべきデータを少なくすることができ、結果として、必要とされる計算時間及びリソースの低減を介して改良に繋がる。
【００９３】
図９Ｅは、総合的最適化の別の形態を示すが、この最適化例は、スカラー値ではなく集合のメンバのドメインに基づく。この例では、オプティマイザは、有用な部分集合を生成するために特定のドメインのみが必要とされ、他のドメインは必要ないと判断する。例えば、図９Ｅのデータセット９５８は列１〜５を有するが、オプティマイザは、多くの要求が列１、３、及び４のみの使用を要すると判断し得る。次に、オプティマイザは、対象ドメインのみを含むメンバを有する部分集合を生成するためのエントリをセットマネージャ内に作成し、セットプロセッサを呼び出してこの部分集合を生成する。例えば、図９Ｅの９６０で示される列１、３、及び４のみを有するデータセットを作成することができる。
【００９４】
図９Ｆは、対象ドメインのスカラー値が比較的低い濃度を有すると判断される一例を示す。一例は、９６２で示されるようにスカラー値の真（ＴＲＵＥ）及び偽（ＦＡＬＳＥ）を有するバイナリドメインである。この場合、オプティマイザは、結果として生成される部分集合からドメインをなくしながら、このドメインが、ドメイン内に存在する各値に対して単調である部分集合の関係を作成する。例えば、９６４に示すように、当初のデータセットのうち、ドメインの値が偽であるすべてのメンバに対して部分集合を作成することができ、ドメインの値が真であるすべてのメンバに対して別個の部分集合を作成することができる。この最適化は、バイナリフィールドでさえも１００％の平均性能向上を提供するため、大きな性能恩恵を有することができる。
【００９５】
図９Ｇは、集合が２つの集合の関係結合で構成される一例を示す。結合により、コストが当初の２つの集合以下のデータセットが生成される条件では、オプティマイザは結合を実行する。この一例は、関係集合間に対応しない主キー及び外部キーが存在する関係内部結合である。例えば、第１のデータセット９６６が３列（図９Ｇにおいてデータセット９６６の列１、２、及び３として示される）を含み、第２のデータセット９６８が４列（図９Ｇにおいてデータセット９６８の列１、２、３、及び４として示される）を含み得る。これら２つのデータセットを結合して、７列（図９Ｇにおいてデータセット９７０の列１、２、３、４、５、６、及び７として示される）を有する第３のデータセット９７０を作成することができる。
【００９６】
図９Ｈは、ベクタードマルチページ処理（vectored multipaging）の一例を示す。ユーザが特定の方法で情報にアクセスする（例えば、電話番号が、ある人物の氏名及び住所情報を探すために使用される）ことが多い場合、オプティマイザは、新しいデータセットを自動的に定義し、一次元配列の複数ページ（ベクタードマルチページ）を作成することにより、新しい関係（例えば、電話番号、氏名、及び住所のみを含むデータセットを定義する）を代数キャッシュに追加して、これら要求をより効率的にすることができる。例えば、オプティマイザは、電話番号の要素である３桁のエリアコード、３桁のプリフィックス、及び４桁のポストフィックスをベクタードマルチページ処理に使用すべきであると決定することができる。次に、オプティマイザは、とり得る１，０００個のエリアコード（０００〜９９９）のそれぞれに対応する１，０００個の部分集合９７４を含む集合９７２を作成する。これら各部分集合は、とり得る各プリフィックス値（０００〜９９９）の部分集合を参照する１，０００個のＧＵＩＤを含み、これら各部分集合は、４桁の各ポストフィックスにつき人物についての指名及び住所情報を有する１０，０００個のメンバを含む。すべてのコードが埋まっている場合、エリアコード及び電話番号プリフィックスに基づいて１００，０００個の部分集合を作成することができる。しかし、多くのエリアコードとプリフィックスとの組み合わせが使用中ではないため、これらエントリを単にヌル（ＮＵＬＬ）集合と呼ぶ。これら集合が作成されると、セットプロセッサはこれら集合を利用して、単にエリアコードをエリアコード集合内のオフセット（ベクター）として使用し、適切なプリフィックス部分集合を表すＧＵＩＤを検索し、それからプリフィックスをオフセットとして使用して、適切なポストフィックス部分集合のＧＵＩＤを判断することにより、電話番号に基づいて個人を素早く見つけることができる。最終的に、電話番号のポストフィックスがオフセットとして使用されて、個人のデータが見つけられる。
【００９７】
図１０Ａは、ＯｐｔｏＮｏｄｅツリー構造の図である。ＯｐｔｏＮｏｄｅツリーは、オプティマイザが処理中の関係、表現、及び引数を追跡するために使用される。ツリーのルートにはＯｐｔｏＮｏｄｅ１００１があり、これは複数のＯｐｔｏＥｘｐｒｅｓｓｉｏｎｓ１００２のリストである。リスト内の各ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００２は、同じリスト内のその他の表現の数学的に等価の変形に関する情報を含む。詳細には、実施形態例では、各ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００２は、演算タイプ、表現を識別するＧＵＩＤ、様々なフラグ（これらブールフラグは、ＯｐｔｏＥｘｐｒｅｓｓｉｏｎがＧＵＩＤを有するか否か、表す表現が代数キャッシュ内にあるか否か、及びＯｐｔｏＥｘｐｒｅｓｓｉｏｎがＧＵＩＤの代替表現の部分として使用されるか否かを示す）、コスト情報（このＯｐｔｏＥｘｐｒｅｓｓｉｏｎのコストの評価に使用すべきコストを示す値及び含まれている表現の残りの部分から独立して実現化される場合の表現のコストを示す値）、及び最大で３つまでのＯｐｔｏＮｏｄｅ引数を含む。オプティマイザは、所望の表現を評価するのに最も効率的な方法を決定するために、１つ又は複数のＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００２を作成する。上述したように、オプティマイザは、各ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００２を解析し、表現の評価に関連付けられたコストを判断する。次に、オプティマイザは、効率のためにどのＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００２を使用すべきかを決定することができる。
【００９８】
図１０Ｂは、ＯｐｔｏＮｏｄｅツリーの一例を示す。ツリーのルートには、数学的に等価の表現を表すＯｐｔｏＥｘｐｒｅｓｓｉｏｎのリストであるＯｐｔｏＮｏｄｅ１００４がある。各ＯｐｔｏＥｘｐｒｅｓｓｉｏｎは、その表現の引数のリストを含む。例えば、ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００６は３つの引数Ａｒｇ［０］、Ａｒｇ［１］、Ａｒｇ［２］を含む。そして、各引数は、特定の引数に使用できる代替の表現を列挙したＯｐｔｏＮｏｄｅを参照する。例えば、ＯｐｔｏＮｏｄｅ１００８は、ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１００６のＡｒｇ［２］に使用できる表現リスト（Ｌｉｓｔ［０］、Ｌｉｓｔ［１］、Ｌｉｓｔ［２］、…）を参照する。そして、これら表現は、ＯｐｔｏＥｘｐｒｅｓｓｉｏｎ１０１０、１０１２、及び１０１４によって表される。これら各表現は、ＯｐｔｏＮｏｄｅ１００６によって表される表現の引数Ａｒｇ［２］に使用された場合、数学的等価の結果を提供する。このＯｐｔｏＮｏｄｅツリー構造では、複数の等価表現をツリーの各レベルに列挙することができる。例えば、オプティマイザ内のｆｉｎｄＡｌｇｅｂｒａｉｃルーチン９１４（図９Ｂ参照）をＯｐｔｏＮｏｄｅツリー上で繰り返して、追加の代替表現を見つけて、ＯｐｔｏＮｏｄｅツリーに追加することができる。次に、ＦｉｎｄＬｅａｓｔＣｏｓｔルーチン９１５は、ＯｐｔｏＮｏｄｅツリーを探索（トラバース）して、最小コストで全体結果を計算するために使用できる特定の表現の集まりを識別することができる。次に、選択された表現の集まりが、ＸＳＮツリーに変換され、計算のためにセットプロセッサに送られる。
【００９９】
セットプロセッサは、システムがデータセットに対して実行するすべての計算及び論理値比較を担当する。一実施形態例では、セットプロセッサは、複数のプロセッサ、及び、システムメモリと不揮発性記憶装置との間の複数の独立した非競合Ｉ／Ｏチャネルを含むシステムを利用するように設計されるマルチスレッドリエントラントソフトウェア本体であってよい。セットプロセッサは、演算間のデータパイプライン化を利用するように設計することもできる。即ち、ある演算の結果を次の入力として、かかる結果を不揮発性記憶装置に中間的に記憶することなくそのまま渡すことができる。データパイプライン化は、Ｉ／Ｏ性能バリアを越える（クロスする）データ量を低減すると共に、不揮発性記憶装置からのデータの取得を担当するストレージマネージャに対する負荷を低減することにより、セットプロセッサの効率を大幅に向上させることができる。
【０１００】
様々な演算の実行は、スレッドプールとして既知のオブジェクトによって監視される。スレッドプールは、ＰｒｏｃｅｓｓＯｐルーチンによって要求される各演算の実行スレッドの開始、それらの実行の監視、及びその成功又は失敗の報告を担当する。スレッドプールはエグゼクティブとも協働して、システムリソースを管理するために必要なエンジン内で実行されている現在のスレッド数を制限する。スレッドは、異なる数のハードウェア及びソフトウェアプラットフォームを使用して実施してもよい。例えば、図１のプロセッサ１０２等の従来のシングルコアプロセッサを、マルチプロセッシングをシミュレートするMicrosoft Windows（登録商標）等のオペレーティングシステムと併せて使用してもよい。代替の実施形態では、マルチプロセッサ又はマルチコアプロセッサを使用してよく、１つ又は複数のスレッドが各プロセッサに割当てられる。別の実施形態では、図３に示すようなマルチプロセッサシステムを使用してもよく、実行スレッドが各ＭＡＰ３０６ａ〜３０６ｆに割当てられる。システムの物理的な実施態様に関わりなく、実施形態例でのセットプロセッサは、性能を増大させるために、あるスレッドからの出力が別のスレッドの入力になるように、リスト、ツリー、又は他の構造を使用して各演算を互いに連鎖させることができる。
【０１０１】
セットプロセッサ内の各演算は、１つ又は複数の入力データに対して計算を実行し、出力データセットを生成するように設計された個々のルーチンである。これら演算は、データ処理に有用であることが分かっている拡張集合演算及び関数と等価である。セットプロセッサは、広範な物理−論理フォーマットマッピングをサポートするために、各演算に対してアルゴリズムの複数の実施態様を有することもできる。演算ルーチンを物理データフォーマット用に適合させることにより、処理のためにすべてのデータを単一の物理表現に変換することよりも、より高い効率及び性能を達成することができる。一実施形態例は、例えば、データをカンマ区切り値（ＣＳＶ）フォーマット、バイナリストリング符号化（ＢＳＴＲ）フォーマット、固定オフセット（ＦＩＸＥＤ）フォーマット、タイプ符号化データ（ＴＥＤ）フォーマット、及び／又はマークアップ言語フォーマット間でマッピングできるように、異なるフォーマット間の論理−物理マッピングをサポートする。これにより、システムは、すべてのデータを共通のフォーマットに変換する必要なく、データを処理することができる。例えば、システムは、ＣＳＶフォーマットの第１のデータセットとＸＭＬフォーマットの第２のデータセットとの結合の結果を計算する必要がある場合、いずれのデータも別のフォーマットに変換する必要なく、マッピングを使用して結果を計算し、かかる結果をＣＳＶフォーマット、ＸＭＬフォーマット、又は別の選択されたフォーマットで返すことができる。これに加えて、一実施形態例は、文字列、３２ビット整数、６４ビット整数、浮動小数点数、通貨、ブール値、日時値、及びインターバル値等の原子値用のいくつかの論理−物理マッピングも同様に含む。これらマッピングは、データフォーマットマッピングと同様に使用することができる。システムは、サポートされる様々なデータフォーマット及び原子フォーマットに対する潜在的なマッピングをすべて含んでもよく、又は選択されたマッピングのみを含んでもよい。例えば、実施形態例が５つのデータフォーマットをサポートする場合、各マッピングルーチンにつき５つの入力及び５つの出力があり、結果として、ソフトウェアルーチンの１２５個の潜在的なバージョンがある。実施形態例では、様々なフォーマット間をマッピングするためのソフトウェアルーチンは、効率の実質的な増大がある場合のみ含まれる。実質的な増大が結果として生じない場合、実施形態例は、マッピング関数を使用する代わりに、データを共通のフォーマットに変換する。
【０１０２】
セットプロセッサの別の機能は、プログラム全体を通して使用される共通集合スキーマのオブジェクト指向データモデルのインスタンスを提供することである。これは、特定の定義を満たし、プログラムによって実行される代数的及び計算的処理内で有用な構造である述語集合、ドメイン集合、濃度集合、及びその他を含む。
【０１０３】
図１１は、セットプロセッサソフトウェアモジュールの一実施形態例を示す。例では、オプティマイザは、ｓｐＰｒｏｃｅｓｓＸｓｎＴｒｅｅルーチン１１０２を通して評価するために、ＸＳＮツリーをセットプロセッサに提示する。ｓｐＰｒｏｃｅｓｓＸｓｎＴｒｅｅルーチン１１０２は、ＸＳＮツリーを調べ、ＸＳＮツリーが割当て又は関係ステートメントを表すか否か、又はＸＳＮツリーが明示的な集合を表すか否かを判断する。
【０１０４】
割当ステートメントの場合、ＰｒｏｃｅｓｓＸｓｎＡｓｓｉｇｎｍｅｎｔルーチン１１０５は、ステートメントの左値（ｌｖａｌｕｅ）がＸＳＮ集合であると確認されるか否かを判断する。ｌｖａｌｕｅが集合ではない場合、ルーチンは失敗コードを返す。次に、右値（ｒｖａｌｕｅ）が調べられて、演算であるか、それとも明示的な集合であるかが判断される。ｒｖａｌｕｅが明示的な集合である場合、ｌｖａｌｕｅに関連する外部識別子に、ｒｖａｌｕｅのＧＵＩＤが関連付けられる。ｒｖａｌｕｅが演算でもなく、明示的な集合でもない場合、ルーチンは失敗コードを返す。ｒｖａｌｕｅが演算である場合、ＰｒｏｃｅｓｓＸＳＮルーチン１１０７が呼び出されて、処理が続けられる。
【０１０５】
関係ステートメントの場合、ＰｒｏｃｅｓｓＸＳＮＲｅｌａｔｉｏｎルーチン１１０６が、ｌｖａｌｕｅ及びｒｖａｌｕｅが演算であることを調べて確認する。いずれか一方又は両方が演算である場合、ＰｒｏｃｅｓｓＸＳＮルーチン１１０６が呼び出されて、いずれか一方又は両方に対する処理が続けられる。ｌｖａｌｕｅ又はｒｖａｌｕｅが演算ではない場合、単純に無視される。この目的は、典型的には、ただし非制限的に、オプティマイザをサポートするために関係を評価できるように、関係ステートメント内で参照される任意の集合を実現化することである。
【０１０６】
明示的な集合を実現化する要求の場合、ｓｐＰｒｏｃｅｓｓＸｓｎＴｒｅｅルーチン１１０２は、ルーチン１１０３において集合を即座に実現化し、実現化された集合を識別するＧＵＩＤを返す。
【０１０７】
ＰｒｏｃｅｓｓＸＳＮルーチン１１０７は、ＸＳＮツリーのルートにある現在の演算から開始してＸＳＮツリーのすべてのメンバを調べ、すべての演算に対してそれ自体を繰り返し呼び出す。実行すべき各演算は、ＸＳＮツリーのルート演算が、下位の演算よりも前に開始されて、適切なデータのパイプライン化の確立を保証するような順序でＰｒｏｃｅｓｓＯＰルーチン１１０８に渡される。
【０１０８】
ＰｒｏｃｅｓｓＯｐルーチン１１０８は、各演算をとり、すべての集合の適切なＧＵＩＤが実行されるべき演算に関連付けられた状態でスレッドプール１１０９内に挿入する。次に、スレッドプール１１０９は、ＰｒｏｃｅｓｓＸＳＮルーチン１１０７に提示されるステートメント内の各演算に対する個々の実行スレッドを開始する。次に、これら実行スレッドは、動作が完了するまで、適切な演算１１１０を呼び出すことによって独立して実行される。これら各スレッドが完了すると、スレッドプール１１０９にスレッドの完了が通知され、スレッドプール１１０９は、スレッドをアクティブスレッドリストから除去することを含む適切なクリーンアップ及びエラー処理を提供する。
【０１０９】
セットプロセッサは、集合に対して論理的演算を実行するように設計されるｓｐＬｏｇｉｃａｌルーチンとして知られる関数も含む。これら論理的演算は、セットプロセッサのｓｐＰｒｏｃｅｓｓＸｓｎＴｒｅｅルーチン１１０２によって実行される計算演算とは本質的に異なる。ｓｐＬｏｇｉｃａｌルーチンは、ｓｐＬｏｇｉｃａｌＥｑｕａｌ、ｓｐＬｏｇｉｃａｌＰｒｅｄｉａｔｅＥｑｕａｌ、及びｓｐＬｏｇｉｃａｌＰｒｅｄｉｃａｔｅＳｕｂＳｅｔを含み、通常、バイナリＸＳＮ記法で記憶される２つのデータセットを比較して、互いの論理的関係を判断するように設計される。これら関係は、相等、部分集合、上位集合、及び互いに素を含む。これら関数は、代替の表現を決定する際にオプティマイザによって使用される。
【０１１０】
図１２Ａは、ＸＳＮ表現の一例をシステムにおいて表現するために使用できるＸＳＮツリー構造の図である。ＸＳＮツリーは、システム内でＸＳＮ表現を処理するために都合のよいフォーマットを提供する。図１２Ａは、表現A REL OP(B,C,D)のＸＳＮツリーを示す。この表現は、関係（REL）によってデータセットＡをデータセットＢ、Ｃ、及びＤで実行される演算（OP）に関連付ける。ＸＳＮツリーは、関係ノード１２０１、演算ノード１２０５、複数のメンバノード１２０２、１２０３、１２０６、１２０７、及び１２０８、並びに複数のデータセット１２０４、１２０９、１２１０、及び１２１１で構成される二重リンクリストである。関係ノード１２０１は、等号、未満、超等の表現の関係を指定する。関係ノード１２０１はメンバノード１２０２にリンクされ、メンバノード１２０２はその左側の子としてデータセットＡ  １２０４（ステートメントの左値）へのリンクを有し、その右側の子としてメンバノード１２０３へのリンクを有する。メンバノード１２０３は、その左側の子として演算ノード１２０５にリンクされる。動作ノード１２０５は、射影、制限、結合等の実行すべき演算を識別される。演算ノード１２０５はメンバノード１２０６にリンクされ、メンバノード１２０６は、その左側の子としてデータセットＢ  １２０９へのリンクを有し、その右側の子として別のメンバノード１２０７へのリンクを有する。メンバノード１２０７は、その左側の子としてデータセットＣ  １２１０へのリンクを有し、その右側の子としてメンバノード１２０８を有する。メンバノード１２０８は、データセットＤ  １２１１にリンクされる。
【０１１１】
図１２Ｂは、ＸＳＮ割当ステートメントの一例をシステムにおいて表現するために使用できるＸＳＮツリー構造の図である。図１２Ｂは、割当ステートメントSQL1 = rdmPROJ(rdmREST(A, C1), C2)に対するＸＳＮツリーを示す。このステートメントは、英数字識別子ＳＱＬ１を表現rdmPROJ(rdmREST(A, C1), C2)に割当てる。ＸＳＮツリーは、割当てノード１２５１、英数字識別子１２５４、複数のメンバノード１２５２、１２５３、１２５６、１２５７、１２６０、及び１２６１、演算ノード１２５５及び１２５８、並びに複数のデータセット１２５９、１２６２、及び１２６３で構成される二重リンクリストである。割当てノード１２５１はメンバノード１２５２にリンクされ、メンバノード１２５２は、その左側の子として英数字識別子ＳＱＬ１  １２５４へのリンクを有し、その右側の子としてメンバノード１２５３へのリンクを有する。メンバノード１２５３は、その左側の子として演算ノード１２５５（ｒｄｍＰＲＯＪ）にリンクされる。演算ノード１２５５は、実行すべき演算（この場合、射影）を識別する。演算ノード１２５５はメンバノード１２５６にリンクされ、メンバノード１２５６は、その左側の子として演算ノード１２５８（この場合、制限演算ｒｄｍＲＥＳＴ）へのリンクを有し、その右側の子として別のメンバノード１２５７へのリンクを有する。メンバノード１２５７は、その左側の子としてデータセットＣ２  １２５９へのリンクを有する。演算ノード１２５８はメンバノード１２６０にリンクされ、メンバノード１２６０は、その左側の子としてデータセットＡ  １２６２へのリンクを有し、その右側の子として別のメンバノード１２６１へのリンクを有する。メンバノード１２６１はデータセットＤ  １２６３にリンクされる。実施形態例では、これらＸＳＮツリーは、アレイとしてシステム内部に記憶することができる。
【０１１２】
ストレージマネージャ４２０が、各集合を含む実際のデータを保持し、不揮発性記憶装置と揮発性記憶装置との間での効率的な転送を提供する。
【０１１３】
図１３Ａ、図１３Ｂ、図１３Ｃ、及び図１３Ｄは、データのパイプライン転送及びバッファ連鎖（チェイン）を通してのデータ共有を可能にするために、バッファチェインをストレージマネージャ４２０においてどのように使用できるかを示す。これは単なる一実施形態例にすぎず、バッファチェインあり又はなしでストレージマネージャ４２０を実装することができる様々な方法があることに留意する。ストレージマネージャ４２０は、ＳｅｔＢａｓｅと呼ばれるクラスの別個のサブクラスであるＳｅｔＲｅａｄｅｒクラス及びＳｅｔＷｒｉｔｅｒクラス（略してリーダ及びライタと呼ばれる）の形態の簡易なメカニズムを介してセットデータへのアクセスを提供する。リーダは記憶装置からデータを読み出し、ライタはデータを記憶装置に書き込み、リーダとライタが一緒になって、ストレージマネージャ４２０のより複雑な機能をカプセル化する。
【０１１４】
このカプセル化により、異なるプラットフォーム又はストレージシステムに対して異なり得る柔軟なストレージマネージャ４２０の実装が可能になる。これに加えて、土台をなすストレージマネージャ４２０が、演算間のパイプライン化を提供して、物理的な記憶装置から転送しなければならないデータ量を最小化することも可能になる。この意味で、パイプライン化とは、データが書き込まれているか、それとも読み出されているかに関わりなく、土台をなすデータバッファの共有である。一例として、演算Ａ（ＯｐＡ）及び演算Ｂ（ＯｐＢ）を考える。但し、ＯｐＡはデータを生成し（ひいては記憶し）、ＯｐＢはそのデータを読み出す必要がある。非パイプライン手法では、別個の動作で、ＯｐＡが単にデータを書き込み、ＯｐＢがそのデータを記憶装置から読み出す。それに代えて、ストレージマネージャ４２０の設計では、ＯｐＡがデータを書き込み、ＯｐＢが、データが生成されているときに、実際には、多くの場合でデータが実際に記憶装置に書き込まれる前に、そのデータにアクセスすることができる。ＯｐＢは、ＳｅｔＲｅａｄｅｒインタフェースしか知らないため、データが実際には、記憶装置からではなくＯｐＡの出力から生じるものであることを知る必要がない。第２の例として、両方とも同じ集合からデータを読み出す必要があるＯｐＣ及びＯｐＤを考える。パイプライン化されたストレージマネージャ４２０は、両演算に関してデータを一度だけ読み出す。
【０１１５】
このメカニズムを図１３Ａ、図１３Ｂ、図１３Ｃ、及び図１３Ｄに示す。データセットは、セットプロセッサの動作によって生成されるか、又はストレージマネージャを介してディスクから検索される。いずれの場合でも、ライタが使用されて、データがバッファチェインとして知られるＲＡＭバッファのリンクリスト内に順次配置される。セットプロセッサの動作がデータセットからのデータを要求すると、リーダが使用されて、演算に使用するために、データがＲＡＭバッファのリンクリストから順次検索される。一実施形態例では、データセットは、たった１つのライタを有するが、任意の数のリーダを有し得る。これを図１３Ａに示し、図１３Ａは、４つのシリアルバッファＤｂｕｆ１、Ｄｂｕｆ２、Ｄｂｕｆ３、及びＤｂｕｆ４を含むバッファチェイン１３０２を示す。ライタ１３０４を使用して、バッファチェイン１３０２内のデータを書き込むべきバッファを指す。ライタ１３０４はバッファチェインを通して順次進み、追加データがライタによりバッファチェインに添付された場合、新しいバッファが作成される。リーダ１３０６及び１３０８を使用して、データをバッファチェイン１３０２から読み出すことができるバッファを指す。
【０１１６】
セットプロセッサ内の動作の性質により、２つ以上のリーダによって読み出されているデータセットが、データを通して異なるペースで進むリーダを有する可能性が高い。例えば、図１３Ａに示すように、低速リーダ１３０８がＤｂｕｆ１を読み出し中であるのに対して、別のリーダ１３０６はすでにＤｂｕｆ３の読み出しを完了している。ライタ及びリーダがバッファチェインを通して進むにつれて、ライタは追加のバッファを作成し、リーダは、セットプロセッサ内の動作によって要求されるペースが何であれ、そのペースでデータを通して自由に進むことができる。図１３Ｂは、図１３Ａに示すリーダとライタとの同じ組み合わせを示すが、ライタ１３０４はＤｂｕｆ７に進んでおり、リーダ１３０６はＤｂｕｆ６に進んでおり、低速リーダ１３０８はＤｂｕｆ１のままである。
【０１１７】
セットプロセッサの動作が続くにつれ、図１３Ｃに示すように、低速リーダ１３０８とその先にあるライタ１３０４及びリーダ１３０６との間に長い一連のバッファが作成される可能性がある。バッファチェイン１３０２が成長するにつれ、データをメモリに保持するために消費されるＲＡＭの空き容量も多くなる。ある時点で、使用中のＲＡＭ量が、追加のＲＡＭを必要とする他のルーチンのニーズにより過度になり、これら他のルーチンが使用できるようにするために、ＲＡＭのいくつかを解放しなければならなくなる。この状況が検出された場合、バッファチェインブレークを開始することができる。
【０１１８】
バッファチェインブレークは、データセットに関連付けられた追加のバッファチェインを作成することによって達成される。図１３Ｄに示す例では、ここではＤｂｕｆ２に進んだ低速リーダ１３０８が新しいバッファチェイン１３１０にコピーされる。この新しいバッファチェイン１３１０にも、新しいライタ１３１２が割当てられて、ディスクからシリアルデータを提供する。既存のバッファチェイン１３０２は、ここではＤｂｕｆ３〜Ｄｂｕｆ１２を含み、ライタ１３０４のみを含む。ライタ１３０４の背後にはもうリーダがないため、Ｄｂｕｆ３〜Ｄｂｕｆ１１は、ストレージマネージャによってもはや使用されていないＲＡＭバッファを解放する別個の非同期ルーチンであるＤｏＣｌｅａｎｕｐルーチンによって除去される。バッファ数は相当大きくなり得るため、これは、追加のＲＡＭを要求する他のルーチンが使用できる相当量のＲＡＭを提供する。
【０１１９】
最適化されたデータの記憶及び検索を提供することに加えて、実施形態例は、異なるデータモデルを使用する異なるスキーマ間での要求及びステートメントの変換及びマッピングのために使用することもできる。例えば、システムは、ＳＱＬデータモデル、ＸＭＬデータモデル、ＸＳＮデータモデル、又は他のデータモデル等の異なるデータモデルを使用するスキーマ間でのマッピングを含むことができる。ステートメントは、異なるデータモデルを使用するスキーマに基づいて提供することができる。例えば、第１のスキーマに基づくいくつかの照会言語ステートメントを、ＳＱＬフォーマット等の第１のフォーマットで提供することができる。上述したように、これらステートメントは、ＸＳＮフォーマットに変換することができ、これらステートメントからのデータセット及び代数的関係をセットマネージャ４０２において組み立てて記憶することができる。後に、ステートメントをＸＱｕｅｒｙフォーマット等の第２のフォーマットで受け取り得る。これもＸＳＮフォーマットに変換し、このステートメントからのデータセット及び代数的関係をセットマネージャ４０２において組み立てて記憶することができる。特に、このステートメントは、第２のデータモデルを使用するスキーマに基づくデータセットの提供を要求し得る。すべてのステートメントは統一されたＸＳＮデータモデルに変換されるため、オプティマイザ４１８は、第１のフォーマットで受け取ったステートメントから組み立てられるデータセット及び代数的関係を使用して、第２のフォーマットで要求されたデータセットを計算するために最適化された代数的関係の集まりを判断することができる。代数キャッシュに記憶される代数的関係及びスキーマ間のマッピングにより、第１のフォーマットのステートメントから取り込まれたデータセット及び関係を、第２のフォーマットで要求されたデータセットの最適化及び計算に使用することが可能になる。これにより、複数の異なるデータモデルを単一のシステムでサポートすることが可能になる。ステートメントからの全情報は、セットマネージャによってデータセット及び代数的関係として取り込まれるため、システムはモデル間で変換を行うことができる。さらに、この情報を使用して、部分表現（subexpression）の置換及び上述したようにオプティマイザにより使用される他の最適化技法を含め、他のデータモデルに関してデータセットの計算に使用されている代数的関係を最適化することもできる。データモデルは、関係データモデル、マークアップ言語データモデル、集合記法データ（set notation data）モデル、又は他のデータモデルであってよい。システムに提出されるステートメントのフォーマットは、標準照会言語ステートメント、ＸＱｕｅｒｙステートメント、集合記法ステートメント、又は他のフォーマットを含み得る。
【０１２０】
例として、図１４Ａに提示する関係テーブル及びＸＭＬ文書を考える。関係テーブルは、数学的に拡張集合として表すことができる。関係テーブルを表す拡張集合のメンバは一般に、関係テーブル内の行と呼ばれる。関係テーブル内の行も数学的に拡張集合として表すことができる。関係テーブル内の行を表す拡張集合のメンバは一般に、フィールドと呼ばれる。行に共通するフィールドは列と呼ばれる。したがって、関係テーブルは、＜＜ｆ１１，ｆ１２，ｆ１３，…，ｆ１ｃ＞＞，…，＜ｆｒ１，ｆｒ２，ｆｒ３，…，ｆｒｃ＞＞という形態の拡張集合で表すことができる。但し、ｆはフィールドの値を表し、添え字ｒ及びｃは、一意の行及び列の計数値を表す。
【０１２１】
ＸＭＬ文書も数学的に拡張集合として表すことができる。ＸＭＬ文書を表す拡張集合のメンバは一般に、ＸＭＬフラグメントと呼ばれ、データを表すタグ及び値を含む。これらＸＭＬフラグメントの値は、文字列又は別のＸＭＬフラグメントであってよい。したがって、ＸＭＬ文書は、＜ｔ１．｛ｖ１｝，…，ｔｎ．｛ｖｎ｝＞という形態の拡張集合で表すことができる。但し、ｔはＸＭＬフラグメントのタグを表し、ｖはＸＭＬフラグメントの値を表す。
【０１２２】
適宜定義された拡張集合を使用して、関係テーブルを表す拡張集合の変換関数ｇＲＸ（）のメンバは、ＸＭＬ文書を表す拡張集合のメンバにマッピングすることができ、関係フォーマット又はＸＭＬフォーマットでのデータのトランスペアレントな表現を可能にする。変換関数は、関係テーブル内のフィールドとＸＭＬ文書内のフラグメントとの間の構造的関係を提供し、関係テーブルの拡張集合表現に対して動作する。この情報の結果として、関係表現の値及び構造と同じデータのＸＭＬ表現の値及び構造との間の機能マッピングが提供される。
【０１２３】
変換関数は、関係テーブルとＸＭＬフラグメントの集まりとの間の関係の集まりとして代数キャッシュ内に記憶することができる。ＸＭＬ文書から関係テーブルにマッピングするには、図１４ＡにおいてｇＲＸ（）として示される関数ｆＸＲ（）の敬意が使用される。これら関数が適切なマッピングを提供するには、項及び項の関係に対する制約が有効でなければならない。これら制約は、図１４Ａにおいてｗｈｅｒｅ節として列挙される。ｘ及びｚがＢ内にあり、Ｂ及びＤがＣ内にあるというメンバシップ制約と共に、ａがｓ．｛ｘ｝に等しくなければならないという制約は、ＸＭＬフラグメントがたった１つのみの値を含まなければならないことを示す。さらに、ｘ及びｙがＡ内にあるというメンバシップ制約と共に、ｂがｓ．ｘに等しくなければならないとう制約は、特定の行内の関係フィールドがたった１つのみの値を有しなければならないことを示す。これら制約は一緒になって、ＸＭＬフラグメントから関係テーブル内のフィールドへの一意のマッピングを保証する。
【０１２４】
別の例は、関係データテーブルへの有向（directed）グラフのベクター表現のマッピングである。図１４Ｂに示す有向グラフは、パス及び接合点で構成される。各接合点において、１つ又は複数のパスが接合点に入ると共にそこから出て行き、例外は、そこから出るパスのみを有する有向グラフの始点及びそこに入るパスのみを有する有向グラフの終点である。有向グラフの各接合点及び各接合点に入って出て行くパスは、｛ｆｒｏｍ．｛ｐ１，ｐ２，…，ｐｍ｝，ｔｏ．｛ｐｍ＋１，ｐｍ＋２，…，ｐｎ｝｝という形態の拡張集合として表すことができる。値ｐ１〜ｐｍは接合点からのパスを一意に識別し、値ｐｍ＋１〜ｐｎは接合点へのパスを一意に識別する。したがって、有向グラフは、拡張集合｛ｊ１．｛ｆｒｏｍ．｛ｐ１１，ｐ１２，…，ｐ１ｍ｝，ｔｏ．｛ｐ１ｍ＋１，ｐ１ｍ＋２，…，ｐ１ｎ｝｝，ｊ２．｛ｆｒｏｍ．｛ｐ２１，ｐ２２，…，ｐ２ｍ｝，ｔｏ．｛ｐ２ｍ＋１，ｐ２ｍ＋２，…，ｐ２ｎ｝｝，…，ｊｋ．｛ｆｒｏｍ．｛ｐｋ１，ｐｋ２，…，ｐｋｍ｝，ｔｏ．｛ｐｋｍ＋１，ｐｋｍ＋２，…，ｐｋｎ｝｝で表すことができる。この場合、変換関数はｆＮＲ（）である。有向グラフを関係テーブルに完全にマッピングする変換関数は、図１４Ｂに提示されるように明示的に定義される。関係からＸＭＬへのマッピングの場合と同様に、各モデルの規則を施行すると共に、モデル間での値及び構造のマッピングを提供するために、制約が必要である。有向グラフは、拡張集合Ｎで完全に表される。拡張集合Ｎは、グラフのｋ個すべての接合点のパスを表す項ｎｋ．Ｊｋの和集合である。パスｎｋ．Ｊｋは、各接合点のフロムパスｆ．Ｆｋ及びツーパスｔ．Ｔｋに関して定義される。関係テーブルは、拡張集合Ｒで表される。拡張集合Ｒは、から（from）、まで（to）、及びパスの各フィールドを含む関係テーブルの各行を表す項Ｒｉｊｋの和集合である。残りの制約は、項と項自体に対する制約との間の関係を定義する。これは、ｆ、ｔ、及びｐが存在しなければならず、互いに等しくあってはならないという制約、関係テーブルフィールドと有向グラフのパスとの間の関係を定義するために、Ｆｋが｛ｘｉ｝に等しくなければならず且つＴｋが｛ｙｊ｝に等しくなければならないという制約、パスを表すＦｋとＴｋとの対が一意でなければならないという制約、及びＪｋで表される各パスの範囲ｆ及び範囲ｔに一意の１つの値があるという制約を含む。
【０１２５】
上記フォーマット、スキーマ、及びマッピングが単なる例示に過ぎず、他の実施形態では、他のフォーマット、スキーマ、及びマッピングを使用してもよいことが理解されよう。
【０１２６】
拡張集合記法の例
上述したように、拡張集合記法（ＸＳＮ）を実施形態例において使用することができる。以下において、使用可能な拡張集合記法（ＸＳＮ）の一例について説明する。これは、拡張集合記法の可能な実施形態の１つにすぎず、他の実施形態は、以下と異なる用語、集合タイプ、構文、パラメータ、演算、及び関数を使用してもよい。拡張集合記法の例は、近代の計算システムの環境内で拡張集合数学に基づいて表現を指定し操作するための単純で使用しやすい構文を提供する。この記法は、標準ＡＳＣＩＩキャラクタで表現可能であり、値、集合、演算、関係、及び表現をコンピュータベースの操作及び処理に適したように表すための標準構文を提供する。この記法は、標準ＡＳＣＩＩキャラクタが機械可読形態で代数的拡張集合表現を指定する能力を提供する。
【０１２７】
ＸＳＮの主要構成要素を説明し識別するために使用される用語を以下の表１において定義する。
【０１２８】
【表１】
2009537906.tif 000002
【０１２９】
構文：ＸＳＮシステムは、集合を指定する象徴的手段並びに表現及びステートメントを定式化するための文法を含む。以下の説明中、括弧（［］）で囲まれた用語は、任意選択の構文を示す。例えば、範囲が要求されない場合、要素は［範囲］．構成要素として表される。省略記号（．．．）は、一連の任意の長さの表現を示す。例えば、＜”１”，”２”，”３”，…＞である。
【０１３０】
シンボル。構文は、以下の表２に記載する特定の共通するシンボルを利用する。読みやすくするために、所望であれば、任意選択的なスペースを句読点間に挿入してもよい。明確にするために、改行がステートメント、表現、又は集合内のどこであっても発生し得る。
【０１３１】
【表２】
2009537906.tif 000003
【０１３２】
値：値は、二重引用符内で値を明示的に記述することによって指定される。値の例としては、“Curly”、 “１２３”、及び“＄２，３４３．７６”が挙げられる。値が二重引用符（“）を含む場合、その前に二重引用符を挿入することによって区切ることができる。例えば、“John said“”shoot”” when he saw the moose.”。ヌル値が、””等の２つの連続した二重引用符によって指定される。
【０１３３】
英数字識別子。英数字識別子によって識別される集合は、割当ステートメントによって指定される。指定されると、英数字識別子を、その英数字識別子が割当てられた表現と同義で使用することができる。例えば、集合に英数字識別子NDCENSUS1960が割当てられた場合、NDCENSUS1960を、任意の表現内で、NDCENSUS1960が割当てられた集合を参照するために使用することができる。
【０１３４】
範囲、構成要素（Constituents）、及び要素（Elements）：範囲及び構成要素は、値、英数字識別子、要素、又は集合で表すことができる。要素の構文は、[範囲.]構成要素である。範囲は、ピリオドの使用を通して構成要素から分離され、ピリオドの左側の項は範囲を表し、ピリオドの右側は構成要素を表す。例えば、範囲が値“１”を有し、構成要素が値“Bob”を有する要素は、適切な記法では“1”.”Bob”と表される。
【０１３５】
要素は、少なくとも１つの範囲及び１つの構成要素を必要とする複合構造を有する範囲又は構成要素である。構成要素は明示的に記述されなければならないが、範囲に対するヌル値は、明示的に記述されず、暗黙的に示される。上記例では、要素“1”.”Bob”は、範囲“1”及び構成要素“Bob”を有する。しかし、範囲及び構成要素は両方とも、英数字識別子、要素、及び集合であってもよく、結果として潜在的に複雑な表現になり得る。
【０１３６】
こういった潜在的に複雑な表現から発生する一問題は、範囲及び構成要素に関する優先順位である。例えば、要素“integer”.”sum”.”5”が与えられた場合、範囲と構成要素との区切りに問題が生じる。すなわち、範囲は“integer”なのか、それとも“integer”.”sum”なのか、という問題である。また、構成要素は“5”なのか、それとも“sum”.”5”なのか、という問題である。このＸＳＮ例での規則により、最初のピリオドの左側の項は範囲であり、右側の項は構成要素である。すると、これは、“integer”が範囲であり、“sum”.”5”が構成要素であることを示す。しかし、“integer”.”sum”を範囲にし、“5”を構成要素にしたい場合、これは、要素(“integer”.”sum”).”5”のように丸括弧の使用を通して指定することができる。
【０１３７】
メンバ及び集合。メンバは、集合内に含まれる要素、集合、又は表現である。集合は、表現により、又は個々のメンバを列挙することによって指定され、メンバのうちのいくつか又はすべては要素、集合、又は表現であることができる。任意の順序で列挙される同じメンバを含む任意の集合は、同じ集合である。
【０１３８】
多くの場合、集合のメンバは、自然数の集合に属する範囲を含む。場合によっては、これら範囲は連続し、一意であり、値１を含む。こういった場合、集合を順序付き集合と呼ぶことができる。これら基準を満たさないすべての集合は、非順序付き集合と呼ぶことができる。
【０１３９】
集合は、｛member［,member［,...］］}として表現される。非順序付き集合のメンバは、{″a″，″x″，″b″，″g″}又は{″Groucho″，″Harpo″，″Gummo″}のように中括弧で囲まれる。順序付き集合のメンバは、＜″a″，″b″，″x″，″g″＞のように山括弧で囲まれる。順序付き集合のメンバは、その仕様において列挙される暗黙的な順序を有する。順序付き集合の連続した各メンバの範囲は、自然数の集合の対応するメンバである。したがって、＜″a″，″b″，″x″，″g″＞は、｛″1″．″a″，″2″．″b″，″3″．″x″，″4″．″g″｝と等価である。
【０１４０】
例えば、順序付き集合は、任意の数のデータフィールドを有するデータ記録であって、集合のメンバが記録のフィールドを表し、メンバの範囲が、対応するフィールドの記録内の順序位置であるデータ記録を表すことができる。以下の表の最初の行内のカンマ区切り値は、処理のために集合として指定することができる。データは、多くの異なる方法で階層に群化することができる。以下の表３はいくつかの可能性を示す。
【０１４１】
【表３】
2009537906.tif 000004
【０１４２】
元のカンマ区切り値は４つの値シーケンスを含み、各値シーケンスは３つの値を有する。
【０１４３】
集合１は、４つのメンバの非順序付き集合として指定され、各メンバは３つのメンバの非順序付き集合を含む。
【０１４４】
集合２は、４つのメンバの順序付き集合として指定され、各メンバは３つのメンバの非順序付き集合を含む。
【０１４５】
集合３は、４つのメンバの非順序付き集合として指定され、各メンバは３つのメンバの順序付き集合を含む。
【０１４６】
集合４は非順序付きとして指定される。集合４は、範囲を使用して、集合の各メンバの、その集合のその他のメンバに相対する位置を示す。
【０１４７】
集合の中身及び構造は、時として、特に集合が関数及び演算の引数として使用される場合、集合の目的によって決定される。これら決定される構造のうちのいくつかは、ＸＳＮ例を仕様して関係データ演算を記述する場合に頻繁に発生する。こういった共通集合によっては、通常、述語集合、マッピング集合、変換集合、又は集約集合と呼ばれ、以下でより詳細に考察する。
【０１４８】
述語集合：述語集合は、ある集合のメンバと別の集合のメンバとの間のマッピングの仕様を提供する。述語集合は、真を判断するために入れ子式条件表現を記述する。ＲＤＭＲＥＳＴ関数で使用されるような条件表現の場合、基本条件は、″condition″.＜element1，element2＞と表現される。
【０１４９】
要素は、″列値″又は″ｃｏｎｓｔ″．″スカラー値″として指定することができる。条件は、等号（″ＥＱ″）、非等号（″ＮＥＱ″）、未満（″ＬＴ″）、以下（″ＬＥ″）、超（″ＧＴ″）、以上（″ＧＥ″）、同様（″ＬＫ″）、又は非同様（″ＮＬＫ″）として指定される。ＲＤＭＲＥＳＴ関数の場合、各要素は、条件で比較すべき列又は範囲″ｃｏｎｓｔ″によって示される定数スカラー値を指定する。
【０１５０】
例えば、条件がＥＱであり、第１の要素が列の名称であり、第２の要素が定数値を提供する条件句″EQ″．＜″2″，″const″．″MI″＞は、第２の列が値″ＭＩ″に等しいすべてのメンバ（行）が出力集合に含まれることを示す。
【０１５１】
以下の例では、単一の条件が、ＲＤＭＲＥＳＴ関数の述語集合に対して指定される。結果として生成される集合は、集合ｚｉｐｃｉｔｙｓｔａｔｅからの第３の列に値″ＩＮ″を含むメンバ（行）のみを含む。追加の２組の中括弧に留意する。
RDMREST（zipcitystate，｛｛｛″EQ″．＜″3″，″const″．″IN″＞}}}）
【０１５２】
これらは、後述するＡＮＤ演算及びＯＲ演算の構築をサポートするために必要である。
【０１５３】
ＡＮＤステートメント：条件集合がＡＮＤステートメントであり、リスト内の全条件が一緒にＡＮＤ演算される。すべて真の場合、全体条件は真である。これは、ＡＮＤ構造の一例である。
｛｛″EQ″．＜″2″，″const″．″MI″＞｝，｛″GE″．＜″5″，″const″．″49000″＞｝，｛″LT″．＜″5″，″const″．″51000″＞｝｝
【０１５４】
３つの条件区が、１組の中括弧で囲まれて、ＡＮＤステートメントを区切る。
【０１５５】
ＯＲステートメント：ＯＲステートメントは、２つ以上のＡＮＤステートメントを組み合わせることによって作成される。任意のＡＮＤステートメントの結果が真の場合、ステートメント全体は真である。ここで、一例は、
｛｛｛″GE″．＜″1″，″const″．″10000″＞｝｝，｛｛″GT″．＜″3″，″const″．″AK″＞｝，｛″LT″．＜″3″，″const″．″CA″＞｝｝，｛｛″EQ″．＜″2″，″const″．″Pasadena″＞｝｝｝）
である。
【０１５６】
この例では、３つのＯＲステートメントがある。第１のＯＲステートメントは１つの条件句を含み、第２のＯＲステートメントは２つのＡＮＤ条件句を含み、最後のＯＲステートメントは単一の条件句を含む。このようにして、複雑な条件表現を構築して、演算を定義することができる。
【０１５７】
マッピング集合：演算及び関数によっては、集合がマッピングを提供する必要がある。大半の場合、範囲及び構成要素が使用されて、入力集合と出力集合との関係を提供する。例えば、ＲＤＭＰＲＯＪ演算では、集合が、入力集合の列と出力集合の列とのマッピングを提供する。範囲値は出力集合の列を示し、構成要素は入力集合の列を示す。例えば、
＜″3″，″5″，″1″＞
である。
【０１５８】
この述語集合は、入力集合の第３、第５、及び第１の列を出力集合の第１、第２、及び第３の列にマッピングすべきであることを示す。
【０１５９】
変換集合：変換表現は、集合からの１つ又は複数の入力値を出力集合内の値に変換するために使用される。変換は、減算（“ＳＵＢ”）、加算（“ＡＤＤ”）、除算（“ＤＩＶ”）、及び乗算（“ＭＵＬ”）等の演算を含む。追加の変換演算は、定数（“ＣＯＮＳＴ”）である。変換表現は、通常、ＲＤＭＭＡＴＨ等の関係演算と共に使用されて、出力集合のメンバを定義する。例えば、出力集合の第１の列が、入力集合の第１の列と第２の列との和として設計された場合、これを指定するために、以下の変換集合が使用される。
＜″ADD″．＜″1″，″2″＞＞
【０１６０】
これは、入力集合の第１及び第２の列を、加算変換の第１及び第２の引数として使用して、出力の第１の列の値を生成すべきであることを示す。変換は深く入れ子にして、仕様を提供することができる。例えば、計算（ＣＯＬ１＋ＣＯＬ２）／（ＣＯＬ３−１）で出力集合内の列１を表したく、入力集合の列５及び列６が列２及び列３にマッピングされた場合、変換集合は、
＜″DIV″．＜″ADD″．＜″1″，″2″＞，″SUB″．＜″3″，″CONST″．″1″＞＞，″5″，″6″＞
である。
【０１６１】
変換集合は、特定のスカラードメイン修飾子を含むこともできる。例えば、数学が整数ドメインにおいて行われる場合、＜″ADD″．＜″1″，″2″＞＞の例は、
＜（″int64″．″ADD″）．＜″1″，″2″＞＞
として表現される。
【０１６２】
これは、列１及び２のスカラー値を、整数値であるかのように一緒に加算することを示す。結果も整数スカラードメインにおいて生成される。関数名及び演算名のように、スカラードメイン識別子は大文字と小文字とが区別されない。
【０１６３】
集約集合：集合はＲＤＭＧＲＯＵＰ関数にも使用されて、集約を提供する。集約演算は、加算（“ＳＵＭ”）、平均（“ＡＶＧ”）、計数（“ＣＮＴ”）、最小（“ＭＩＮ”）、及び最大（“ＭＡＸ”）を含む。これら関数は、ＲＤＭＧＲＯＵＰ関数によって作成される各群内の集合のメンバに対して実行すべき演算を指定する。例えば、
＜″1″，″3″，″COUNT″．″1″，″AVG″．″1″＞
である。
【０１６４】
これは、入力の第１及び第３の列が群の基礎を提供し、出力の第１及び第２の列として含まれることを示す。出力の第３の列は、群内の列１からのメンバの計数であり、第４の列は、群の列１内のメンバの平均である。
【０１６５】
変換集合のように、平均集合は、演算を実行すべきスカラードメインを指定することができる。例えば、上記を文字列ドメインで実行すべき場合、指定される集合は、
＜″1″，″3″，″（″STRING″．″COUNT″）．″1″，（″STRING″．″AVG″）．″1″＞
である。
【０１６６】
関数及び演算：関数及び演算は明示的に指定され、関数又は演算により、その関数又は演算に引数を提供する１〜３つの集合と組み合わせて指定される集合を定義する。他の実施形態では、異なる数の引数が可能であり得る。演算は原子的であり、拡張集合数学において指定される。関数は１つ又は複数の演算の組み合わせであり、頻繁に実行される演算の組み合わせの都合のよい記法である。
【０１６７】
関数及び演算は、予め規定された英数字識別子、丸括弧、及び１〜３つの集合引数を介して表現される。一例は、濃度集合｛″1″，″2″，″3″｝である集合を表すCRD（｛″1″，″2″，″3″｝）である。
【０１６８】
一般に、関数は、関数（表現１［，表現２［，表現３［,...］］）として指定される。但し、引数の数は関数に依存する。特に、単項関数は１つの引数を必要とし、二項関数は２つの引数を必要とし、三項関数は３つの引数を必要とする。関数によっては、最後の引数は、マッピング及び変換の指定に使用される集合である。集合に使用される英数字識別子と異なり、関数名及び演算名では大文字と小文字との区別がない。
【０１６９】
以下は、関数のいくつかの例である。
【０１７０】
RDMPROJ（ASet，＜″7″，″1″，″2″，″3″＞）−−ＲＤＭＰＲＯＪは、関係データモデル（ＲＤＭ）射影関数である。ＡＳｅｔという名称の集合が、関係テーブルを表す演算への引数である。第２の集合は、結果として生成される集合内の列として使用されるべきＡＳｅｔからのメンバ（列）のマッピングを指定する集合である。
【０１７１】
INV（OldSet）−−ＩＮＶは反転関数であり、集合のメンバの範囲と構成要素とを交換させる。ＯｌｄＳｅｔという名称の集合は演算の引数であり、出力を生成するために反転する。
【０１７２】
CRD（MySet）−−ＣＲＤは濃度関数であり、入力引数集合の濃度集合を生成する。ＭｙＳｅｔという名称の集合は入力であり、出力集合の生成に使用される。
【０１７３】
RDMJOIN（cities_and_states,states_and_zips，｛｛｛″EQ″．＜″2″，″3″＞｝｝｝）−−ＲＤＭＪＯＩＮは、関係データモデル（ＲＤＭ）結合関数である。cities_and_states、states_and_zipsという名称の第１の２つの集合は、演算によって結合される対象である。第３の集合に定提供される明示的な述語集合が、結果として得られる結合集合のメンバを選択するために使用される条件を指定する。この場合、述語集合は、第１の集合の第２の列が第２の集合の第１の列（州列）に等しく、行を出力集合では結合すべきであることを指定する。
【０１７４】
RDMREST（zips，｛｛｛″GE″．＜″1″，″const″．″10000″＞｝，｛″LE″．＜″1″，″const″．″14999″＞｝｝，｛｛″GT″．＜″3″，″const″．″AK″＞｝，｛″LT″．＜″3″，″const″．″CA″＞｝｝｝）−−ＲＤＭＲＥＳＴは、関係データモデル（ＲＤＭ）制限関数である。ｚｉｐｓという名称の第１の集合は、関係テーブルを表す演算の引数である。第２の引数は、どのメンバ（行）が制限付き出力集合に含まれるべきかを指定する述語集合である。
【０１７５】
この例では、ＲＤＭ（関係データモデル）で始まる名称を有する関数は、関係データを集合として操作するように特に設計される。例えば、ＲＤＭＳＯＲＴは、ソート順及びプロシージャを示す第２の引数の集合内のメンバを使用して、第１の引数の集合をソートするバイナリ関数である。
【０１７６】
表現：表現は、集合を指定する象徴的表現である。集合を表す英数字識別子は、表現の最も単純な形態である。表現は、多くの関数、演算、及び集合で構成することもできる。表現のいくつかの例としては、
CRD（SetA）
rdmPROJ（SetA，＜″1″，″5″，″23″＞）
CRD（rdmPROJ（SetA，＜″1″，″5″，″23″＞））
が挙げられる。
【０１７７】
関係及び関係演算子：関係演算子は、２つの表現の関係を指定する象徴的表現である。関係演算子は、相等、部分集合、及び互いに素、並びにそれらの否定を含む。これらは、値“ＥＱ”、“ＳＵＢ”、“ＤＩＳ”、“ＮＥＱ”、“ＮＳＢ”、及び“ＮＤＳ”を使用して指定され、関係演算子を使用するいくつかの文例としては、
SetA EQ CRD（SetB）
SetC SUB SetB
が挙げられる。
【０１７８】
割り当て：割り当ては、英数字識別子を表現に割当てるステートメントである。構文的に、割り当ては、英数字識別子＝表現として指定される。例えば、
NewSet=<"1","2","12","4">
SetA=SS（SETB）
SetC＝＜″b″，″c″，″a″，″x″＞
SetD＝｛″Larry″，″Moe″，″Curly″｝
SetG=NULL
である。
【０１７９】
関係データモデル：関係（リレーショナル）データモデル（ＲＤＭ）は、ＸＳＮを使用して記述することができる拡張集合データモデルの部分集合である。関係テーブルは、順序付き集合の集合であるとみなされ、テーブルの行がこれら順序付き集合によって表される。行を表す集合のメンバは、行内の列（フィールド）の値である。３行を有し、各行が４列を含む関係テーブルは、構造：
＜＜a1，b1，c1，d1＞，＜a2，b2，c2，d2＞，＜a3，b3，c3，d3＞＞
を有する集合によって表される。
【０１８０】
テーブル及び個々の行は両方とも、順序付き集合として表されるが、関係テーブルを、
｛＜a1，b1，c1，d1＞，＜a2，b2，c2，d2＞，＜a3，b3，c3，d3＞＞｝
等の順序の付いていないメンバを含む集合として表現することも可能である。
【０１８１】
濃度集合：集合が順序付きとして提示される場合、集合の順序を示す情報が提示されなければならない。関係データモデルの追加の特徴のうちのいくつかを保持するため、且つＸＳＮ表現の処理の最適化に有用な濃度情報を提供するために、通常、濃度集合が、関係テーブルを表す集合に対して指定される。上記非順序付き集合の濃度集合は、
＜″3″，＜″4″，＜Ca，Cb，Cc，Cd＞＞＞
である。
【０１８２】
濃度集合は入れ子集合である。最も外側の集合は、集合の濃度（この例では、テーブルが３行を含むため、３である）を含み、次に、行を表すメンバの濃度集合が続く。Ｃａ〜Ｃｄは、行を表す集合のメンバを構成する値の濃度を表す値である。各値のＣｎは、その特定のメンバの最大濃度を表す。濃度集合は、濃度関数：
CardinalityOfSetA＝CRD（SetA）
を介して生成される。
【０１８３】
ＲＤＭ関数：標準的な関係データモデルは８つの演算で構成される。しかし、関係モデル全体を実施するために５つのみが必要とされ、通常、４つのみが実際の実施に使用されることが分かる。ＸＳＮは、拡張集合数学の枠組み内でのこれら関数の記法を提供する。
【０１８４】
これら関数は、関係データモデルの和（ＲＤＭＵＮＩＯＮ）、射影（ＲＤＭＰＲＯＪ）、制限（ＲＤＭＲＥＳＴ）、結合（ＲＤＭＪＯＩＮ）、差（ＲＤＭＤＩＦＦ）、及び商（ＲＤＭＤＩＶ）の拡張集合版である。これら関数に加えて、３つの追加の関数がＸＳＮの下で利用可能である。これらは、ＲＤＭＳＯＲＴ、ＲＤＭＰＩＶＯＴ、及びＲＤＭＧＲＯＵＰを含む。
【０１８５】
ＲＤＭＤＩＦＦ関数。ＲＤＭＤＩＦＦは、関係的Ａ−Ｂ演算と等価の非順序付き集合を定義する。結果として生成される集合は、Ｂ内にないＡのすべてのメンバを含む。以下は、この関数のフォーマット例及び説明である。
RDMDIFF（A，B）＝＝｛｝
【０１８６】
引数：
Ａ−非順序付き集合
Ｂ−結果を生成するために、メンバがＡから除外される非順序付き集合
【０１８７】
結果：異なる関数の条件によって指定されるＢのメンバではないＡのメンバを含む非順序付き集合
【０１８８】
備考：列メンバのすべての値が等価である必要がある標準関係差への拡張として、ＸＳＮバージョンでは、等価関係を定義する述語集合を指定することが可能である。ヌルが条件述語集合に提供される場合、標準のＲＤＭ関数が実行される。Ａ  ＥＱ  Ｂの場合、結果はヌル集合になる。ＡとＢとの積集合がヌル集合の場合、結果はＡになる。
【０１８９】
要件：集合ＡはＲＤＭ集合でなければならない。これら条件が満たされない場合の結果はヌル集合である。Ａ及びＢは、同じメンバ列濃度を有さなければならない。
【０１９０】
例：
A＝｛＜″a″，″b″，″c″＞，＜″d″，″b″，″r″＞｝
B＝｛＜″3″，″c″，″8″＞｝
RDMDIFF（A，B）＝＝｛＜″a″，″b″，″c″＞｝
【０１９１】
ＲＤＭＧＲＯＵＰ関数。ＲＤＭＧＲＯＵＰは、列が、１つ又は複数の列のメンバによって識別される指定群に基づいて集約される非順序付き集合を定義する。集約述語集合と併せて、この関数は、加算、計数、平均、最小、及び最大（ＳＣＡＭＭ）の各値を生成する能力を提供する。以下は、この関数のフォーマット例及び説明である。
RDMGROUP(A, Z)
【０１９２】
引数：Ａ−順序付き又は非順序付き集合
【０１９３】
結果：集合Ａ及び指定された集約述語集合Ｚの列のメンバの集約関数及びに基づいて生成されたメンバを含む非順序付き集合
【０１９４】
備考：ＲＤＭＧＲＯＵＰは、述語集合において指定されるメンバ列の値の一意の各組み合わせにつき１つのメンバ行を生成する。集約するメンバ列は、範囲なしで述語集合内に列挙することによって指定される。出力集合に含めるべき他のメンバは、出力集合を生成するために、どのＳＣＡＭＭ値を実行すべきかを示すべきである。
【０１９５】
要件：集合ＡはＲＤＭ集合でなければならない。集合Ｚは集約述語集合でなければならない。これら条件が満たされない場合の結果はヌル集合である。
【０１９６】
例：A＝＜＜″3″，″Tom″，″a″＞，
＜″2″，″Sam″，″c″＞，
＜″6″，″Harry″，″a″＞，
＜″7″，″Harry″，″a″＞＞
Z＝＜″3″，
″COUNT″．″2″，
″SUM″．″1″＞
RDMGROUP（A，Z）−＞｛＜″a″，″3″，″16″＞，＜″c″，″1″，″2″＞｝
【０１９７】
ＲＤＭＪＯＩＮ関数。ＲＤＭＪＯＩＮは、メンバ行が集合Ａからの１つのメンバ行と集合Ｂからの１つのメンバ行とを、これら２つのメンバ行間で条件述語集合Ｚが満たされることによって決定される場合に連結したものである非順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
RDMJOIN（A，B，Z）＝＝｛｝
【０１９８】
引数：
Ａ−結果として生成されるメンバ行の左側として結合される非順序付き集合
Ｂ−結果として生成されるメンバ行の右側として結合される非順序付き集合
Ｚ−結合するメンバを決定するための条件集合を含む述語集合
【０１９９】
結果：条件述語集合Ｚにおいて指定される条件に整合するメンバがＡからの１つのメンバ行及びＢからの１つのメンバ行から作成される非順序付き集合。述語集合Ｚにおいて指定される条件を満たす集合Ａからのメンバ行及び集合Ｂからのメンバ行が見つかった場合、結果として生成される集合のメンバが生成される。結果として生成されるメンバ行は、集合Ａからのメンバ行のメンバ列の後に集合Ｂのメンバ行からのメンバ列を含む順序付きメンバである。
【０２００】
備考：条件述語集合Ｚは、集合Ａのメンバ行と集合Ｂのメンバ行との間で保たれなければならない条件を指定する。
【０２０１】
要件：集合Ａ及び集合ＢはＲＤＭ集合でなければならない。集合Ｚは条件述語集合でなければならない。これら条件が満たされない場合の結果はヌル集合である。述語集合Ｚは、条件用に定義されたスキーマを有さなければならない。述語集合内のメンバの範囲は、集合Ａのメンバ列を指定し、述語集合内のメンバの構成要素は、集合Ｂからのメンバ列を指定する。
【０２０２】
例：
A＝｛＜″sales″，″Tom″＞，
＜″sales″，″Sam″＞，
＜″shipping″，″Bill″＞，
＜″shipping″，″Sally″＞｝
B＝｛＜″Bldg 1″，″sales″＞，
＜″Bldg 2″，″shipping″＞｝
Z＝｛｛｛″EQ″．＜″1″，″2″＞｝｝｝
RDMJOIN（A，B，Z）−＞｛
＜″sales″，″Tom″，″Bldg 1″，″sales″＞，
＜″sales″，″Sam″，″Bldg 1″，″sales″＞，
＜″shipping″，″Bill″，″Bldg 2″，″shipping″＞，
＜″shipping″，″Sally″，″Bldg 2″，″shipping″＞｝
【０２０３】
ＲＤＭＰＩＶＯＴ関数。ＲＤＭＰＩＶＯＴ関数は、指定された集合のメンバ列とメンバ行とを交換する順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
RDMPIVOT（A）＝＝＜＞
【０２０４】
引数：
Ａ−順序付き集合
【０２０５】
結果：結果として生成される集合は、集合Ａのメンバ列で構成されるメンバ行を含む。集合は、集合Ａ内のメンバ列の順序によって順序づけられる。
【０２０６】
備考：極めて大きな集合を回転させることは、コストがかかると共に時間がかかる恐れがあり、集合を処理する他の手段を見つけることができない場合のみ行われるべきである。
【０２０７】
要件：集合ＡはＲＤＭ集合でなければならない。これら条件が満たされない場合の結果は、ヌル集合である。
【０２０８】
例：
A＝｛＜″3″，″Tom″，″a″＞，
＜″2″，″Sam″，″c″＞，
＜″6″，″Harry″，″a″＞，
＜″7″，″Harry″，″a″＞｝
RDMPIVOT（A）−＞＜
＜″3″，″2″，″6″，″7″＞，
＜″Tom″，″Sam″，″Harry″，″Harry″＞，
＜″a″，″c″，″a″，″a″＞＞
【０２０９】
ＲＤＭＰＲＯＪ関数。ＲＤＭＰＲＯＪは、変換述語集合を通して指定されるメンバ列を除く、引数集合のすべてのメンバ行からのメンバで構成される非順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
RDMPROJ(A,Z) == {}
【０２１０】
引数：
Ａ−射影すべき非順序付き集合
Ｚ−射影のための変換述語集合
【０２１１】
結果：結果として生成される集合は、変換述語集合によって指定されるメンバ列を除き、Ａの各メンバ行のメンバ行を含む。
【０２１２】
備考：集合Ｚを適宜指定する方法の情報については、変換述語集合についての仕様を参照のこと。
【０２１３】
要件：集合ＡはＲＤＭ集合でなければならない。集合Ｚは変換述語集合でなければならない。これら条件が満たされない場合の結果は、ヌル集合である。
【０２１４】
例：
A＝｛＜″3″，″Tom″，″a″，″b″，″s″＞，
＜″2″，″Sam″，″c″，″b″，″s″＞，
＜″6″，″Harry″，″a″，″z″，″s″＞｝
Z＝＜″3″，″2″＞
RDMPROJ（A，Z）−＞｛＜″a″，″Tom″＞，
＜″c″，″Sam″＞，
＜″a″，″Harry″＞｝
【０２１５】
ＲＤＭＲＥＳＴ関数。ＲＤＭＲＥＳＴ関数は、メンバ行が条件述語集合内で指定される条件を満たすものに制限される非順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
【０２１６】
RDMREST（A，Z）＝＝｛｝ 
【０２１７】
引数：
Ａ−制限されるべき非順序付き集合
Ｚ−制限の条件を指定する条件述語集合
【０２１８】
結果：結果として生成される集合は、条件述語集合Ｚによって指定される条件を満たす、集合Ａからのメンバ行のみを含む。
【０２１９】
備考：集合Ｚを指定する方法の情報については、条件述語集合の仕様を参照のこと。
【０２２０】
要件：集合Ａは、ＲＤＭ集合の要件を満たさなければならない。集合Ｚは条件述語集合でなければならない。これら条件が満たされない場合、結果はヌル集合になる。
【０２２１】
例：
A＝｛＜″3″，″Tom″，″a″，″b″，″s″＞，
＜″2″，″Sam″，″c″，″f″，″s″＞，
＜″6″，″Harry″，″a″，″z″，″s″＞｝
Z＝｛｛｛″EQ″．＜″2″，″const″．″Tom″＞｝｝，
｛｛″EQ″．＜″2″，″const″．″Harry″＞｝，｛″EQ″．＜″4″，″const″．″f″＞｝｝｝
RDMREST（A，Z）−＞｛＜″3″，″Tom″，″a″，″b″，″s″＞｝
【０２２２】
ＲＤＭＳＯＲＴ関数。ＲＤＭＳＯＲＴは、非順序付き集合Ａ及び述語集合Ｚによって指定される順序に基づく順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
RDMSORT（A，Z）＝＝＜＞
【０２２３】
引数：
Ａ−非順序付き集合
Ｚ−結果集合のソート順を記述するマッピング集合
【０２２４】
結果：マッピング集合Ｚにおいて指定される順序によってソートされる集合Ａのすべてのメンバ行を含む順序付き集合
【０２２５】
備考：Ｚは、昇順のソート順を決定する最上位メンバ〜最下位メンバを指定するメンバ列の範囲を含むマッピング集合である。
【０２２６】
要件：述語集合Ｚは、要素が、それぞれ集合Ａの濃度未満のＮＡＴのメンバである順序付き集合でなければならない。集合ＡはＲＤＭ集合でなければならない。これら条件が満たされない場合、結果はヌル集合である。
【０２２７】
例：
A＝｛＜″3″，″Tom″，a″，″b″，″s″＞，
＜″2″，″Sam″，″c″，″b″，″s″＞，
＜″6″，″Harry″，″a″，″z″，″s″＞｝
Z＝＜″3″，″2″＞
RDMSORT（A，Z）−＞＜＜″6″，″Harry″，″a″，″z″，″s″＞，
＜″3″，″Tom″，″a″，″b″，″s″＞，
＜″2″，″Sam″，″c″，″b″，″s″＞＞
【０２２８】
ＲＤＭＵＮＩＯＮ関数。ＲＤＭＵＮＩＯＮは、集合Ａ及びＢのすべてのメンバ行を含む非順序付き集合を定義する。以下は、この関数のフォーマット例及び説明である。
RDMUNION（A，B）＝＝｛｝
【０２２９】
引数：
Ａ−非順序付き集合
Ｂ−非順序付き集合
【０２３０】
結果：Ａ又はＢのメンバ行を含む非順序付き集合
【０２３１】
備考：なし
【０２３２】
要件：Ａ及びＢはＲＤＭ集合でなければならず、且つ同じメンバ列濃度を有さなければならない。これら条件が満たされない場合、結果はヌル集合である。
【０２３３】
例：
A＝｛＜″a″，″b″，″c″＞｝
B＝｛＜″3″，″c″，″8″＞｝
RDMUNION（A，B）−＞｛＜″a″，″b″，″c″＞，
＜″3″，″c″，″8″＞｝
【０２３４】
上記関数、フォーマット、及び引数は単なる例にすぎず、他の実施形態では異なってもよい。例えば、他の実施形態では、異なる又は追加の関数を使用してもよい。
【０２３５】
本発明の好ましい実施形態を本明細書において図示し説明したが、かかる実施形態が単なる例として提供されることが当業者には明らかであろう。これから、当業者は、本発明から逸脱することなく多くの変形、変更、及び置換を思いつくであろう。本発明を実施するに際して、本明細書において述べた本発明の実施形態に対する様々な代替を利用し得ることを理解されたい。以下の特許請求の範囲が本発明の範囲を規定し、これら請求項及びそれらの均等物の範囲内にある方法及び構造が特許請求の範囲に包含されることが意図される。
【図１】
2009537906.tif 000005
【図２】
2009537906.tif 000006
【図３】
2009537906.tif 000007
【図４Ａ】
2009537906.tif 000008
【図４Ｂ】
2009537906.tif 000009
【図５】
2009537906.tif 000010
【図６】
2009537906.tif 000011
【図７】
2009537906.tif 000012
【図８】
2009537906.tif 000013
【図９Ａ】
2009537906.tif 000014
【図９Ｂ】
2009537906.tif 000015
【図９Ｃ】
2009537906.tif 000016
【図９Ｄ】
2009537906.tif 000017
【図９Ｅ】
2009537906.tif 000018
【図９Ｆ】
2009537906.tif 000019
【図９Ｇ】
2009537906.tif 000020
【図９Ｈ】
2009537906.tif 000021
【図１０Ａ】
2009537906.tif 000022
【図１０Ｂ】
2009537906.tif 000023
【図１１】
2009537906.tif 000024
【図１２Ａ】
2009537906.tif 000025
【図１２Ｂ】
2009537906.tif 000026
【図１３Ａ】
2009537906.tif 000027
【図１３Ｂ】
2009537906.tif 000028
【図１３Ｃ】
2009537906.tif 000029
【図１３Ｄ】
2009537906.tif 000030
【図１４Ａ】
2009537906.tif 000031
【図１４Ｂ】
2009537906.tif 000032
【国際調査報告】
2009537906.tif 000033