(57)【要約】データ集約は、レコードを含む第１データセットを受け取るステップを含み、各レコードは、複数のフィールドのそれぞれに対する値を保持する。第２データセットは、第１データセットから生成される。第２データセットは、フィールドのサブセット内の値と一致する第１データセットからの一つ以上のレコードとそれぞれが対応する一つ以上の集約レコードを含む。第３データセットは、第２データセットから生成される。第３データセットは、フィールドのサブセット内の値と一致する第１データセットの一つ以上の集約レコードとそれぞれが対応する一つ以上の集約レコードを含む。第３データセット内の集約レコードと関係付けられる集約値は、第１データセットからの複数のレコードと関係付けられる値に、非カスケード演算を実行した結果を表す。
2008547131.tif 000002
【特許請求の範囲】
【請求項１】
データを集約するための方法であって：
第１データセット（５０２）を受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットから第２データセット（５１２）を生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセット（５２０）を生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算を実行した結果を表す、方法。
【請求項２】
請求項１に記載の方法において、
前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算を実行することは、前記値間の幾つかの異なる値を決定すること、前記値の中央値を決定すること、前記値全体の複数の極値の合計値を決定すること、及び、前記値の複数の合計値の極値を決定すること、からなるグループの内の一つである、
方法。
【請求項３】
請求項１に記載の方法において、
前記非カスケード演算は、一セットのオペランドに対して前記非カスケード演算を実行した結果が、前記オペランドの第１サブセットに対して前記演算を実行した第１結果及び前記オペランドの第２サブセットに対して前記演算を実行した第２結果、に対して前記演算を実行した結果に分解しないようなものであり、前記第１サブセット及び第２サブセットは、相互に排他的かつ包括的である、
方法。
【請求項４】
請求項１に記載の方法において、
前記複数のフィールドの内の少なくとも一つは、前記複数のフィールドの内の別のフィールドに少なくとも部分的に関数従属する、
方法。
【請求項５】
請求項４に記載の方法において、
前記複数のフィールドの内の少なくとも一つと関連する少なくとも幾つかの値は、前記複数のフィールドの内の別のフィールドと関連する対応値に従属する、
方法。
【請求項６】
請求項１に記載の方法において、
前記第２データセットから前記第３データセットを生成するステップは、前記第２データセットの集約レコードのフローを受け取るステップを含む、
方法。
【請求項７】
コンピュータ可読媒体上に格納されるソフトウエアであって：
第１データセット（５０２）を受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持している、ステップ；
前記第１データセットから第２データセット（５１２）を生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセット（５２０）を生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；
の各ステップをコンピューターシステムに実行させるための命令を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算を実行した結果を表す、  ソフトウエア。
【請求項８】
データを集約するためのシステムであって：
第１データセット（５０２）を受け取るための手段であって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、手段；
前記第１データセットから第２データセット（５１２）を生成するための手段であって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、手段；及び、
前記第２データセットから第３データセット（５２０）を生成するための手段であって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、手段；を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に、非カスケード演算を実行した結果を表す、システム。
【請求項９】
複数のレコードを含むデータを集約するための方法であって、各レコードは複数のフィールドのそれぞれに対する値を保持し、前記方法は、フィールド間の関数従属性を考慮に入れて、非カスケード演算を用いることにより、このようなレコード内のフィールドのマルチステージ集約を実行するステップを含む、方法。
【請求項１０】
請求項９に記載の方法において、
前記非カスケード演算は、前記値間の幾つかの異なる値を決定するステップ、前記値の中央値を決定するステップ、前記値全体の複数の極値の合計値を決定するステップ、及び、前記値の複数の合計値の極値を決定するステップから構成されるグループの内の一つである、
方法。
【請求項１１】
請求項９に記載の方法において、
前記非カスケード演算は、一セットのオペランドに対して前記非カスケード演算を実行した結果が、前記オペランドの第１サブセットに対して前記演算を実行した第１結果及び前記オペランドの第２サブセットに対して前記演算を実行した第２結果、に対して前記演算を実行した結果に分解しないようなものであり、前記第１サブセット及び第２サブセットは、相互に排他的かつ包括的である、
方法。
【請求項１２】
データを集約するための方法であって：
第１データセット（３０２）を受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットのレコードと、第１の複数のキーセット（３０４）と、のデカルト積（３０６）を生成するステップであって、各キーセットは前記第１データセットの前記フィールドのサブセットを表す、ステップ；
前記生成されたデカルト積から第２データセット（３１０）を生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセット（３１８）を生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；
を含む方法。
【請求項１３】
請求項１２に記載の方法において、
前記第３データセットを生成する前記ステップは、前記生成されたデカルト積と、前記第１の複数のキーセットの一つを表す第１の値及び第２の複数のキーセットの一つを表す第２の値をそのレコードが含むデータセットと、に結合演算を実行するステップを含み、前記第２の複数のキーセットのそれぞれは前記第２データセットの前記フィールドのサブセットを表し、前記結合演算は一致するキーセットを有するレコードを結合する、
方法。
【請求項１４】
請求項１３に記載の方法において、
前記第３データセットを生成する前記ステップは、少なくとも幾つかの結合されたレコードに対して、前記フィールドの少なくとも一つに対する値をワイルドカードの値と置き換えるステップを含む、
方法。
【請求項１５】
請求項１２に記載の方法において、
前記第２データセットを生成するステップは、前記生成されたデカルト積の内の少なくとも幾つかのレコードに対して、前記フィールドの少なくとも一つに対する値をワイルドカードの値と置き換えるステップを含む、
方法。
【請求項１６】
コンピュータ可読媒体上に格納されるソフトウエアであって：
第１データセット（３０２）を受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットのレコードと第１の複数のキーセット（３０４）とのデカルト積（３０６）を生成するステップであって、各キーセットは前記第１データセットの前記フィールドのサブセットを表す、ステップ；
前記生成されたデカルト積から第２データセット（３１０）を生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセット（３１８）を生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；の各ステップをコンピューターシステムに実行させるための命令を含む、ソフトウエア。
【請求項１７】
データを集約するためのシステムであって：
第１データセット（３０２）を受け取るための手段であって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、手段；
前記第１データセットのレコードと第１の複数のキーセット（３０４）とのデカルト積（３０６）を生成するための手段であって、各キーセットは、前記第１データセットの前記フィールドのサブセットを表す、手段；
前記生成されたデカルト積から第２データセット（３１０）を生成するための手段であって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、手段；及び、
前記第２データセットから第３データセット（３１８）を生成するための手段であって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、手段；を含む、システム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
背景
本発明は、複合演算によるデータ集約に関する。
【０００２】
データベース内に格納された多次元データをユーザが分析できるようにする様々なオンライン分析処理（ＯＬＡＰ）技法がある。一般に、そのデータベースは、「ファクトテーブル」を含む。ファクトテーブルは、多次元データへのインデックスとして役立つ値を格納する数多くの次元（つまり「キーフィールド」）と、他の値を格納する数多くの属性（つまり「非キーフィールド」）と、を有する。ユーザは、多次元データの集約計算にかかわるデータに関するクエリーを実行できる。このようなクエリーの効率を向上させるために、典型的なＯＬＡＰ手法は、可能性がある集約計算の幾つかを事前に行っておく。
【０００３】
概要
一般的な態様において、本発明は、データを集約するための方法、対応するソフトウエア及びシステムを特徴とする。本方法は、第１データセットを受け取るステップを含んでいて、その第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する。第２データセットは第１データセットから生成され、その第２データセットは一つ以上の集約レコードを含む。前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する。第３データセットは前記第２データセットから生成され、その第３データセットは一つ以上の集約レコードを含む。第３データセットの各集約データは、第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する第１データセットの一つ以上の集約レコードと対応する。第３データセット内の集約レコードと関連する集約値は、第１データセットからの複数のレコードと関連する値に対して非カスケード演算を実行した結果を表す。
【０００４】
本態様には、一つ以上の以下の特徴を含めることができる。
【０００５】
第１データセットからの複数のレコードと関連する値に関する非カスケード演算を実行するステップは、前記値間の幾つかの異なる値を決定するステップ、前記値の中央値を決定するステップ、前記値全体の複数の極値の合計値を決定するステップ、及び、前記値の複数の合計値の極値を決定するステップから構成されるグループの内の一つのステップである。
【０００６】
前記非カスケード演算は、一セットのオペランドに対してその非カスケード演算を実行した結果が、そのオペランドの第１サブセットに対してその演算を実行した第１結果及びそのオペランドの第２サブセットに対してその演算を実行した第２結果、に対してその演算を実行した結果に分解されないようなものであり、第１サブセット及び第２サブセットは、相互に排他的かつ包括的である。
【０００７】
複数のフィールドの内の少なくとも一つは、複数のフィールドの内の別のフィールドに少なくとも部分的に関数従属する。
【０００８】
複数のフィールドの内の少なくとも一つと関連する少なくとも幾つかの値は、その複数のフィールドの内の別のフィールドと関連する対応値（関連付けられた対応する値）に従属する。
【０００９】
第２データセットから第３データセットを生成するステップは、第２データセットの集約レコードのフローを受け取るステップを含む。
【００１０】
別の一般的な態様において、本発明は、複数のレコードを含むデータを集約するための方法を特徴とし、各レコードは複数のフィールドのそれぞれに対する値を保持する。本方法は、フィールド間の関数従属性を考慮に入れて非カスケード演算を用いることにより、このようなレコード内のフィールドのマルチステージ集約を実行するステップを含む。
【００１１】
この態様には、以下の特徴の内の一つ以上を含めることができる。
【００１２】
その非カスケード演算は、前記値間の幾つかの異なる値を決定するステップ、前記値の中央値を決定するステップ、前記値全体の複数の極値の合計値を決定するステップ、及び、前記値の複数の合計値の極値を決定するステップから構成されるグループの一つである。
【００１３】
前記非カスケード演算は、一セットのオペランドに対してその非カスケード演算を実行した結果が、そのオペランドの第１サブセットに対してその演算を実行した第１結果及びそのオペランドの第２サブセットに対してその演算を実行した第２結果、に対してその演算を実行した結果に分解されないようなものであり、第１サブセット及び第２サブセットは、相互に排他的かつ包括的である。
【００１４】
別の一般的な態様において、本発明は、データを集約するための方法、対応するソフトウエア及びシステムを特徴とする。本方法は、第１データセットを受け取るステップを含んでいて、第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する。本方法は、第１データセットのレコードと第１の複数のキーセットとのデカルト積（直積）を生成するステップを含む。各キーセットは第１データセットのフィールドのサブセットを表す。本方法は、生成されたデカルト積から第２データセットを生成するステップを含んでいて、その第２データセットは一つ以上の集約レコードを含み、各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する第１データセットからの一つ以上のレコードと対応する。本方法は、第２データセットから第３データセットを生成するステップを含んでいて、第３データセットは一つ以上の集約レコードを含み、第３データセットの各集約レコードは、第３データセットの集約レコードと関連するフィールドのサブセット内の値と一致する第１データセットの一つ以上の集約レコードと対応する。
【００１５】
この態様は、以下の特徴の内の一つ以上を含むことができる。
【００１６】
第３データセットを生成するステップは、生成されたデカルト積と、第１の複数のキーセットの一つを表す第１の値及び第２の複数のキーセットの一つを表す第２の値をそのレコードが含むデータセットと、に結合演算を実行するステップを含んでいる。第２の複数のキーセットのそれぞれは、第２データセットのフィールドのサブセットを表し、ここで、結合演算は、一致するキーセットを有するレコードを結合する。
【００１７】
第３データセットを生成するステップは、少なくとも幾つかの結合されたレコードに対して、少なくとも一つのフィールドに対する値をワイルドカードの値と置き換えるステップを含む。
【００１８】
第２データセットを生成するステップは、生成されたデカルト積の少なくとも幾つかのレコードに対して、少なくとも一つのフィールドに対する値をワイルドカードの値と置き換えるステップを含む。
【００１９】
本発明の態様は以下の利点の内の一つ以上を含み得る。
【００２０】
データセット内のフィールド間（例えば、キーフィールドと、演算されているフィールドとの間）の関数従属性を利用することにより、集約計算をマルチステージ（複数のステージ）に分解することができる。関数従属性を考慮に入れるマルチステージ集約を用いることにより、非カスケード演算に基づいてデータを集約できる。集約計算をマルチステージに分解することにより、集約計算のサイズを低減できる。
【００２１】
本発明の他の特徴及び利点は以下の説明及び請求項から明らかとなろう。
【００２２】
説明
１  概観
図１を参照すると、データ集約システム１０は、データ記憶装置（データストア）１６内の入力テーブル１４内の情報を処理することにより、集約テーブル１８に格納するための情報を生成するデータ集約器１２を含む。場合によっては、データ集約器１２は、ユーザ２０がユーザーインターフェース２２上で作成したクエリーに基づいて、集約テーブル１８を生成する。他の場合には、データ集約器１２は、事前計算方式に従って集約テーブル１８を生成する。この集約は、ユーザ２０に有用な入力テーブル１４内のデータの要約を提供する。
【００２３】
図２Ａを参照すると、テーブル１００の行１〜７は、集約データを生成する元となる多次元データセットのレコードを表す。テーブル１００は。キーフィールド「Product（製品）」、「Distributor（代理店）」、「Year（年）」及び「Location（場所）」を表す４列と、非キーフィールド「Number Sold（販売数）」及び「Price（価格）」を表す２列と、を含む４次元データセットである。ユーザークエリーは、「Number Sold」の合計を「Year」、「Product」及び「Location」により分解し、「Distributor」について集約したものを求めることができる。この集約は、元の４つのキーフィールドの内の３つのキーフィールドを残しながら１つのキーフィールドについて行われるので、３次元集約と呼ばれる。集約の基となる演算に従って、残りのキーフィールドの同一値を有するレコードを組み合わせることを「集約演算」と称する。この場合、集約演算は非キーフィールド内の値の合計である。図２Ｂは、この例に対して得られた３次元集約データを表すテーブル１１０を示す。
【００２４】
別の例として、ユーザは、「Number Sold」又は「Price」の合計を「Product」により分解し、「Year」、「Distributor」及び「Location」について集約したものを求めることができる（１次元集約）。この場合、集約は、単一の残りのキーフィールド「Product」の同一値を有する行を組み合わせることになる。図２Ｃは、得られた１次元集約データセットを表すテーブル１２０を示す。「Number Sold」及び／又は「Price」の合計を４つのキーフィールド総てについて集約すると、図２Ｄのテーブル１３０で表される０次元集約（即ち、単一の「グローバル集約」値）を生み出す。
【００２５】
ユーザへ集約データを提供する一つのアプローチは、多次元データのクエリーで用いられる可能性がある幾つかの或いは総ての集約を事前計算することである。このような事前計算は、かなりの時間を要することになる大規模な計算を伴う。例えば、１４次元の多次元データセットから４つ以下の次元を有する集約の総てについての事前計算は、14C4＋14C3＋14C2＋14C1＋14C0＝1471通りの集約を伴う。仮に、そのデータセットが107行のデータを有する場合、事前計算は1.471×1010行ものデータ処理を伴う。
【００２６】
多次元集約の事前計算に要する計算量を低減させる一方法は、マルチ（複数の）ステージで集約を生成し、より高次元の集約に基づいて低次元の集約を計算するステップを含む。例えば、14C4の４次元集約の内の１５通りは、単一の６次元集約から、その６次元集約の内の２次元についての集約を6C2＝15回行うことにより計算することができる。仮に、その６次元集約が、例えば、104のデータ行を有する場合、これらの１５通りの４次元集約の事前計算は、107行のデータを処理して６次元集約を生成し、次いで、15×104＝150,000行のデータを処理することにより１５通りの４次元集約を生成することを伴い、合計10,150,000行のデータを処理する必要があろう。比較のため、１４次元データからこれらの１５通りの４次元集約をそれぞれ独立して事前計算すると、15×10,000,000＝150,000,000行のデータを処理する必要があろう。
【００２７】
（例えば、事前計算のため及び／又はユーザークエリーに応えて）多次元データを処理して集約データを生成するためのシステム１０は、必要な演算が「カスケード可能」であるか否かに応じて、マルチステージ集約のための異なるアプローチを用いる。一セットのオペランドに演算を実行した結果が、（ａ）そのオペランドの第１サブセットにその演算を実行した第１結果、及び、（ｂ）そのオペランドの第２サブセットにその演算を実行した第２結果（ここで、その第１サブセット及びその第２サブセットは、相互に排他的且つ包括的である）、に実行される演算の結果へ分解できる場合、演算は、カスケード可能である。例えば、加算は、加算の結合法則：(a+b+…+z)＝(a+b+…+m)＋(n+o+…+z)が成り立つので、カスケード可能である。
【００２８】
カスケード演算の例には、合計値を計算すること、及び、データ行内の最大値又は最小値（即ち、「極値」）を決定すること、が含まれる。上記の例では、テーブル１３０（図２Ｄ）内の「Number Sold」及び「Price」フィールド内の値の合計は、テーブル１００内の元のデータセットから単一のステージにおいて計算でき、或いは、代替として、テーブル１１０（図２Ｂ）又はテーブル１２０（図２Ｃ）内のデータセットのような、中間集約データセットを用いてマルチ（複数の）ステージにおいて計算できる。関与する合計演算がカスケード可能であるので、このようなマルチステージの使用が可能であり、システム１０は、セクション２．２で更に詳述するように、集約すべきフィールドを中位の次元の複数のセットへ分解する第１マルチステージ集約処理を用いることができる。
【００２９】
多次元データセット内のレコードを集約するために用いることができる非カスケード演算の例には：そのレコードのフィールドに対して幾つかの異なる値を決定すること、フィールド内の値の中央値を決定すること、複数の値を有する複数のセット全体に対して複数の極値の合計値（例えば、場所毎の最も高価な製品の合計値）を決定すること、及び、複数の値の複数の合計値の極値（例えば、最大年間合計販売高）を決定することが含まれる。従って、単一の結合演算（加算又は最大値を求める等）はカスケード可能ではあるが、上記の「極値の合計値」及び「合計値の極値」の例のように、二つの結合演算を含む複合演算はカスケード可能ではない場合がある。
【００３０】
図２Ｅ及び図２Ｆは、非カスケード演算に基づく集約データの例を示す。図２Ｅは、「Product」フィールドの異なる値の数を「Distributor」により分解してカウントする演算に基づいて、テーブル１００のレコードを「Product」、「Year」及び「Location」について集約した結果を表すテーブル１４０を示す。図２Ｆは、「Product」フィールドの異なる値の数を「Year」により分解してカウントする演算に基づいて、テーブル１００のレコードを「Product」、「Distributor」及び「Location」について集約した結果を表すテーブル１５０を示す。
【００３１】
図２Ｇは、「Product」フィールドの異なる値の数の包括的集約値を表すテーブル１６０を示す。この例では、テーブル１００のレコードを集約することにより決定されるように、３つの異なる製品Ａ、Ｂ及びＣがある。この「異なる値をカウント」する演算は非カスケード演算なので、その包括値は、テーブル１４０内又はテーブル１５０内のデータのような中間集約データから得られるとは限らない。この例では、テーブル１４０内の中間的な「異なる製品」値の合計は、テーブル１００内の元データの関数従属性により、３つの異なる製品という正しい結果をもたらす。しかし、テーブル１５０内の中間的な「異なる製品」値の合計は、６つの異なる製品という正しくない結果をもたらす。
【００３２】
システム１０は、セクション２．４で更に詳細に説明するように、関数従属性を利用し、第２マルチステージ集約処理を用いることによる非カスケード演算に基づいてマルチステージ集約のデータ行を処理することができる。この例では、各製品は、単一の代理店（Distributor）を有するので、「Distributor」と「Product」との間には関数従属性がある（即ち、「Distributor」の値は「Product」の値に関数的に従属する）。この関数従属性により、中間データを適切に選択しながらの非カスケード演算に基づいて、中間データからこの集約に対する正しい結果を得ることができる。
【００３３】
２  データフローグラフを用いるデータ集約
システム１０においては、多次元データの計算は、計算要素がグラフの頂点と関係付けられ、且つ、その要素間のデータフローがグラフのリンク（弧、辺）と対応する、有向グラフによるデータフローとして表される。このようなグラフをベースとした計算を実装するシステムは、米国特許第５，９６６，０７２号の「グラフとして表された計算の実行」に記載されている。システム１０内の集約器１２を実装するための多次元データセットの集約計算の例は、このような「データフローグラフ」を用いることにより以下に記述される。
【００３４】
２．１  単一ステージ集約
図３を参照すると、単一ステージ集約を計算するためのデータフローグラフ２００は、入力データセット２０２（例えば、入力テーブル１４）及び出力データセット２１０（例えば、集約テーブル１８）を含む。入力データセット２０２は、一セットのフィールドに対する値をそれぞれが含む一連のレコードのソースである。幾つかのフィールドは、入力データセット２０２内の多次元データに対するキーフィールドである。「Prepare（準備）」要素２０６は、「Rollup（ロールアップ）」要素２０８での処理に備えてレコードを処理する。その「Prepare」要素２０６は、データ集約に用いられる一つ以上のキーセットを特定する「キーセット」入力ファイル２０４に基づいて、レコードを処理する。その「Rollup」要素２０８は、選択された演算に基づいて複数の入力レコードからの情報を結合し、複数の入力レコードの代わりに単一の出力レコードを生成する。その「Rollup」要素２０８からの集約レコードのフローは、出力データセット２１０内に格納される。
【００３５】
単一ステージ集約を実行する一実施例において、グラフ２００は、二つのキーフィールド「key0」及び「key1」、並びに一つの非キーフィールド「attribute（属性）」に対する整数値を有する行として下記のテーブル内に表された２次元入力データセット２０２内のレコードを処理する。
【表１】
2008547131.tif 000003
【００３６】
グラフ２００は、一方の次元（キーフィールド）により分解されるとともに他方の次元について集約された「attribute」フィールド内の値の合計に基づいて、二つの１次元集約データセットを生成する。「キーセット」入力ファイル２０４は、第１集約（「key1」を除去し、単一セット{0}により「key0」を保持する）及び第２集約（「key0」を除去し、単一セット{1}により「key1」を保持する）を規定する。
【００３７】
大規模な数の集約（大規模な数のキーセットで示される）を計算するときの時間を節約するために、「Prepare」要素２０６は、計算されている総ての集約を実行するために用いられ得る「synthetic（合成）key」値を有するレコードのフローを生成する。例えば、「Prepare」要素２０６は、入力ファイル２０４内のキーセットと入力データセット２０２内のレコードとのデカルト積に基づいて（例えば、空値{}についての「結合」演算を用いて）、「key0」及び「key1」の値から構成される「synthetic key」を有するレコードを生成する。この例に対してこのようなデカルト積を実行した結果は以下のテーブルで与えられる。
【表２】
2008547131.tif 000004
【００３８】
「Prepare」要素２０６は、対応するキーセットの一部ではないレコード（行）のキーフィールド内の値に対して、「ワイルドカード」値（例えば、「*」）を導入する。本例についてワイルドカード値を導入した結果は、次のテーブルで与えられる。
【表３】
2008547131.tif 000005
【００３９】
次いで、「Prepare」要素２０６による生成の結果として得られたレコードのフローは、「Rollup」要素２０８により処理される。「Rollup」要素２０８は、その合成キー値が一致するレコードについてattributeフィールド内の値を合計する（ワイルドカード値は他のワイルドカード値だけと一致する）。グラフ２００による生成の結果得られた二つの１次元集約データセットを含む出力データセットは、次のテーブルで表される。
【表４】
2008547131.tif 000006
【００４０】
最初の２行は、「key0」により分解し、「key1」について集約した「attribute」フィールド内の値の合計を表す。最後の２行は、「key1」により分解し、「key0」について集約した「attribute」フィールド内の値の合計を表す。
【００４１】
データフロー内のレコードと関係付けられる（関連する）合成キーを格納するために、多様な表現の何れかを用いることができる。例えば、本例で用いるキーフィールド値（その内の幾つかはワイルドカードである）のアレイの代わりに、それぞれのレコードは、非ワイルドカード値に対するキー値の対のアレイ（データセットの次元がキーセットの次元と比較して大きい場合、より一層効率的な表現である）と関係付けることができる。
【００４２】
２．２  カスケード演算のためのマルチステージ集約
図４を参照すると、マルチステージ集約を計算するためのデータフローグラフ３００は、入力データセット３０２及び出力データセット３１８を含んでいる。入力データセット３０２は、データ集約のために用いられる一つ以上のキーセットの内の第１セットを規定する入力ファイル３０４に基づいて、「Prepare」要素３０６及び「Rollup」要素３０８により処理される予定の一連のレコードのソースである。「Rollup」要素３０８の出力は、入力データセット３０２と出力データセット３１８の次元の中間次元である集約データセットを表すレコード３１０のフローである。この中間データは、後のクエリー又はデータの処理で用いることができるようにデータセット内に格納され得、又は代替として、必ずしもファイルに格納されないでレコードのフローのままであってもよい。レコード３１０は、データ集約のために用いられる一つ以上のキーセットの内の第２セットを規定する入力ファイル３１４に基づいて、「Prepare」要素３１２及び「Rollup」要素３１６により処理される。「Rollup」要素３１６からの集約レコードのフローは、出力データセット３１８内に格納される。
【００４３】
カスケード可能な演算に対するマルチステージ集約を実行する実施例においては、グラフ３００は、４つのキーフィールド「key0」、「key1」、「key2」及び「key3」ならびに一つの非キーフィールド「attribute」に対して整数値を有する行として、下記テーブルに表される４次元入力データセット３０２内のレコードを処理し、全部で６つの２次元合計集約を含むデータセットを生成する。
【表５】
2008547131.tif 000007
【００４４】
入力ファイル３０４及び３１４は、入力ファイル３０４内の６つの第１ステージキーセット及び入力ファイル３１４内の６つの第２ステージキーセットを含む「rollup plan（ロールアップ計画）」を規定する。詳細には、本例において、グラフ３００は、２次元（キーフィールド）により分解し、他の２次元について集約した「attribute」フィールド内の値の合計に基づいて、６つの２次元集約データセットを生成する。下記の６つの第１ステージキーセットそれぞれは、３つの３次元中間集約データセット（レコード３１０内の）の内の一つに残っている３つのキーフィールドを表す：
key set 1-1：{0,1,2}
key set 1-2：{0,1,2}
key set 1-3：{0,1,2}
key set 1-4：{0,1,3}
key set 1-5：{0,1,3}
key set 1-6：{0,2,3}
【００４５】
下記の６つの第２ステージキーセットそれぞれは、６つの２次元出力集約データセットの内の一つに残っている二つのキーフィールドを表す：
key set 2-1：{0,1}
key set 2-2：{0,2}
key set 2-3：{1,2}
key set 2-4：{0,3}
key set 2-5：{1,3}
key set 2-6：{2,3}
【００４６】
第２ステージキーセット内のキーフィールドそれぞれは、対応する第１ステージキーセット内のキーフィールドから選択される（「key set 2-n」は（「key set 1-n」に対応する）。第１ステージキーセット内のキーフィールドは、二つのフィールドの可能性のある６つの組み合わせそれぞれを第２ステージキーセット内にて表わせるように選択される。入力ファイル３１４は、詳細を以下に説明するように、合成キー値を生成する際に使用するために、第２ステージキーセットのそれぞれ（例えば、「key set 2-1」）を、それが関係付けられた第１ステージキーセット（例えば、「key
set 1-1」）とともに、レコード内に格納する。
【００４７】
場合によっては、第１及び第２ステージで集約されている次元数に応じて、どの第１ステージキーセットを使用すべきかの選択は、所与の数の出力集約データセットを計算するのに幾つの中間集約データセットの生成が必要か、ということに影響する（これは全体の計算効率に影響する）。本例においては、３つの中間集約データセットが、４つの可能性のある中間集約データセットの内のどの３つが選択されるかとは無関係に、６つの出力集約データセットを計算するのに必要である。場合によって必要な中間集約データセットの数を低減するような第１ステージキーセットを選択するための手順は、セクション２．３で説明する。「Prepare」要素３０６は、入力ファイル３０４内の異なるキーセット（この場合３つの異なるキーセット）と、入力データセット３０２内のレコードと、のデカルト積に基づいて、第１ステージ合成キーを有するレコードを生成する。「Prepare」要素３０６は、また、対応キーセットの一部ではないレコード（行）のキーフィールド内の値に対しワイルドカード値を導入する。本例について、このようなデカルト積を実行するとともにワイルドカード値を導入した結果を以下のテーブルに示す。
【表６】
2008547131.tif 000008
【００４８】
次いで、「Prepare」要素３０６による生成の結果得られたレコードのフローは、「Rollup」要素３０８により処理される。「Rollup」要素３０８は、合成キー値（ワイルドカード値を含む）が一致するレコードについてattributeフィールド内の値を合計する。得られた中間レコード３１０を以下のテーブルに示す。
【表７】
2008547131.tif 000009
【００４９】
最初の２行は、「key0」、「key1」及び「key2」により分解し、「key1」について集約した「attribute」フィールド内の値の合計を表す。次の２行は、「key0」、「key1」及び「key3」により分解し、「key2」について集約した「attribute」フィールド内の値の合計を表す。最後の３行は、「key0」、「key2」及び「key3」により分解し、「key1」について集約した「attribute」フィールド内の値の合計を表す。
【００５０】
「Prepare」要素３１２は、上記テーブルに表される中間レコード３１０と、下記テーブルに表される入力ファイル３１４内のキーセットレコードと、に結合演算を実行することにより、第２ステージ合成キーを有するレコードを生成する。「key set 1」の値は、その結合演算に対するキーとして用いられる。
【表８】
2008547131.tif 000010
【００５１】
「Prepare」要素３１２から「Rollup」要素３１６へ送られる結合の結果得られたレコード（第２ステージキーセットにないキーフィールドに対するワイルドカード値を含む）は、下記テーブルで表される。
【表９】
2008547131.tif 000011
【００５２】
「Rollup」要素２０８は、合成キー値（ワイルドカード値を含む）が一致するレコードに対してattributeフィールド内の値を合計する。グラフ３００による生成の結果得られた６つの２次元集約データセットを含む出力データセットは、下記テーブルで表される。
【表１０】
2008547131.tif 000012
【００５３】
上記テーブル内の行は、整数値を含むキーフィールドにより分解し、ワイルドカード値を含むキーフィールドについて集約した「attribute」フィールド内の値の合計を表す。
【００５４】
２．３  キーセットの選択
以下は、中間集約データセットのフィールドを表す第１ステージキーセットを選択するための、データフローグラフの「Prepare」要素が用いる例示の手順である。この手順は、選択が、必要とされる中間集約数に影響を与える例に関して記述される。この例は、５次元データ（キーフィールド0,1,2,3,4を有する）から、３次元の中間集約を介して生成される２次元データについてのものであり、可能性がある１０の２次元出力集約データセットを生み出す（5C2=10 であるから）。
【００５５】
まず、その要素は、第１中間集約データセット内のフィールドを表す、任意の第１の３次元キーセット：{4,3,2}を選択する。その要素は、どの出力集約データセットが、前記第１中間集約データセットから生成できるかを決定する：{4,3}、{4,2}、{3,2}。次いで、その要素は、最大数の残りの出力集約データセットを生成できる第２キーセットを検索する：{4,1}、{4,0}、{1,0}を生成できる{4,1,0}。このステップを全ての２次元出力集約データセットが生成されるまで繰り返すと、追加のキーセット{3,2,1}及び{3,2,0}が生み出され、合計４つの第１ステージキーセットが得られる。
【００５６】
第１ステージキーセットの他の選択は、総ての２次元の出力集約データセットが生成され得る高次数を生み出す。例えば、以下の順序：{4,3,2}、{4,3,1}、{4,3,0}、{4,2,1}、{4,2,0}、{3,2,0}で第１ステージキーセットを選択すると、６つの第１ステージキーセットが生み出される。従って、可能性のある中間キーセットが数百、数千とある場合、上記説明の手順によるキーセット選択により、生成する必要がある中間集約データセットの数を低減することができることがある。
【００５７】
２．４  非カスケード演算のための集約
非カスケード演算に基づく多次元データの集約計算では、集約を計算するために必要な幾つかの情報が中間次元の集約で失われるので、場合によっては、所望の集約の大部分を元のデータセットから直接計算する必要がある。しかし、他の場合には、中間次元の集約は、幾つかの集約を計算するために必要な情報を含んでいる。このようなケースの一つは、あるキーフィールドの値が別のキーフィールドの値に従属（依存）するデータセットに対する場合である。
【００５８】
２．４．１  関数従属性のない単一ステージ集約
関数従属性を用い、集約計算をマルチステージへ分解することにより集約計算のサイズを低減するケースを説明する前に、「target」フィールドに対して実行される演算であって非カスケードの「異なるものをカウント」する演算、に基づいて、集約計算するための単一ステージのアプローチを説明することが有用である。
【００５９】
図５を参照すると、単一ステージの集約を計算するためのデータフローグラフ４００は、入力データセット４０２及び出力データセット４１２を含む。グラフ４００は、入力ファイル４０４に基づいてレコードを処理し、所望の集約に対応する合成キーを含むレコードのフローを生成する「Prepare」要素４０６を含む。このグラフ４００は、「Rollup」要素４０８及び「Rollup」要素４１０を用いて、「異なるものをカウント」する演算を実行するよう構成されている。「Rollup」要素４０８は、それぞれの異なる値が合成キーの各値に対して一度現れるように、「target」フィールドの値に基づいてレコードを組み合わせる。この第１のロールアップ演算は、「Rollup」要素４１０が、一致する合成キーを有するレコードの数をカウントして、「target」フィールド内の異なる値の数を決定することを可能にする。「Rollup」要素４１０からの集約レコードのフローは、出力データセット４１２内に格納される。
【００６０】
このデータフローグラフ４００は、複数のロールアップ要素を含むが、データフローグラフ４００が実行する集約計算は、出力が中間次元のデータに基づいて生成されないので、単一ステージ集約である。
【００６１】
非カスケードの「異なるものをカウント」する演算に基づいて単一ステージ集約を実行する実施例では、グラフ４００は、二つのキーフィールド「key0」及び「key1」、ならびに「異なるものをカウント」する演算の対象である一つの非キーフィールド「target」に対して整数値を有する行として、下記テーブルに表される２次元入力データセット４０２内のレコードを処理する。
【表１１】
2008547131.tif 000013
【００６２】
グラフ４００は、「target」フィールドに実行される「異なるものをカウント」する演算に基づいて、二つの１次元集約データセット及びグローバル集約を生成する。入力ファイル４０４は、対応するキーセットを、１次元集約については{0}及び{1}として、グローバル集約については{}として特定する。
【００６３】
「Prepare」要素４０６は、入力ファイル４０４内のこれらのキーセットと、キーセット内にないキーフィールドに対してワイルドカード値をもつ入力データセット４０２内のレコードと、のデカルト積に基づいて、合成キー値を有するレコードのフローを生成する。それは、次のテーブルで表される。
【表１２】
2008547131.tif 000014
【００６４】
「Rollup」要素４０８は、合成キーの値と「target」フィールドの値との一致に基づいてレコードを組み合わせ、重複レコードを除去する。得られたレコードを以下のテーブルに示す。
【表１３】
2008547131.tif 000015
【００６５】
「Rollup」要素４１０は、合成キー値（「key0」及び「key1」）が一致するレコードを組み合わせ、組み合わされたレコード数をカウントして、幾つかの異なる「target」フィールド値を生成する。グラフ４００による生成の結果得られた、二つの１次元集約データセット及びグローバル集約を含む出力データセットを、以下のテーブルにより表す。
【表１４】
2008547131.tif 000016
【００６６】
最初の３行は、「key0」により分解し、「key1」について集約した「target」フィールド内の異なる値の数を表す。その次の２行は、「key1」により分解し、「key0」について集約した「target」フィールド内の異なる値の数を表す。最後の行は、両キーフィールドについて集約した「target」フィールド内の異なる値の合計数を表す。
【００６７】
２．４．２  関数従属性に基づくステージ
非カスケード演算のための本マルチステージ手法において、中間次元の集約に基づいて所望の集約を生成するために必要とされる情報がその中間次元の集約に含まれることを確実にするためには、キーフィールドの少なくとも一つは別のキーフィールドと少なくとも部分的に関数従属していなければならない。フィールドの値間の（例えば、キーフィールドと「target」フィールドとの間の）関数従属性は、様々な型式のデータで発生し得る。例えば、あるフィールドの値が個人（例えば、顧客ＩＤ）を表す場合、性別、民族、又は生年月日のような属性を表す別のフィールドの値は、そのフィールドの値と関数従属している。セクション３．１で詳細に後述するように、関数従属性に例外がある場合、あるフィールドは「部分的に」又は「近似的に」別のフィールドに関数従属していることになる。
【００６８】
図６は、入力データセット５０２と比べて次元数を低減した集約レコード５１２を生成する第１ステージを含むデータフローグラフ５００を示す。その第１ステージは、グラフ４００について上述したように機能する「Prepare」要素５０６及び二つの「Rollup」要素５０８，５１０を含む。入力ファイル５０４は、集約演算の「target」フィールドに従属しない「非従属」キーフィールドを含むキーセットを含む。グラフ５００は、また、「target」フィールドに従属する「従属」キーフィールドを含む入力ファイル５１６内のキーセットに基づいて、レコード５１２を更に集約する第２ステージも含む。即ち、「target」フィールドに従属するフィールドはどれも、最後のステージで集約される。
【００６９】
非カスケードな「異なるものをカウント」する演算に基づいてマルチステージ集約を実行する例において、グラフ５００は、二つのキーフィールド「key0」及び「key1」、並びに「異なるものをカウント」する演算の対象である一つの非キーフィールド「target」について整数値を有する行として、下記テーブルに表される２次元の入力データセット５０２内のレコードを処理する。キーフィールド「key0」は、「target」フィールドに関数従属している。
【表１５】
2008547131.tif 000017
【００７０】
グラフ５００は、「target」フィールドについて実行した「異なるものをカウント」する演算に基づいて、二つの１次元集約データセット及びグローバル集約を生成する。入力ファイル５０４、５１６は、入力ファイル５０４内の３つの第１ステージキーセット及び入力ファイル５１６内の３つの第２ステージキーセットを含む「rollup plan」を規定する。第１ステージは、第１ステージキーセットに含まれる非従属キーフィールド「key1」の値に基づくロールアップを含む。
key set 1-1：{}
key set 1-2：{}
key set 1-3：{1}
【００７１】
非カスケード演算に対するこのマルチステージアプローチでは、第２ステージキーセット内のキーフィールドは、必ずしも、対応する第１ステージキーセット内のキーフィールドからのみ選択されるとは限らない。しかし、第１ステージ及び第２ステージのキーセット内のキーフィールドは、この例におけるように、非従属次元が第１ステージ内で集約可能となり且つ従属次元が第２ステージ内で集約可能となるように選択される。本例では、第２ステージは、第２ステージキーセット内に含まれる従属キーフィールド「key0」の値に基づくロールアップを含む。
key set 2-1：{0}
key set 2-2：{}
key set 2-3：{1}
【００７２】
「Prepare」要素５０６は、入力ファイル５０４内の第１ステージキーセットと、第１ステージキーセット内にない非従属キーフィールドに対してワイルドカード値をもつ入力データセット５０２内のレコードと、のデカルト積に基づいて、合成キー値を有するレコードのフローを生成する。それは、下記テーブルで表される。
【表１６】
2008547131.tif 000018
【００７３】
「Rollup」要素５０８は、合成キーの値と「target」フィールドの値との一致に基づいてレコードを組み合わせ、重複レコードを除去する。オプションとして、従属キーフィールド「key0」は、その値が「target」フィールドの値に従属しているので、第１ステージ合成キーから外すこと（即ち、一致を考慮しないこと）ができる。得られたレコードを以下のテーブルに示す。
【表１７】
2008547131.tif 000019
【００７４】
「Rollup」要素５１０は、合成キー値（「key0」及び「key1」）が一致するレコードを組み合わせ、その組み合わされたレコードの数をカウントして、幾つかの異なる「target」フィールド値を生成する。その得られた組み合わせレコード内に「target」フィールドの値を含むことは必ずしも必要でない。以下のテーブルに表される得られた中間レコード５１２は、１次元集約レコード及び２次元集約レコードを含む。
【表１８】
2008547131.tif 000020
【００７５】
「Prepare」要素５１４は、上記テーブルに表された中間レコード５１２と、以下のテーブルに表された入力ファイル５１６内のキーセットレコードと、に結合演算を実行することにより、第２ステージ合成キーを有するレコードを生成する。「key set 1」の値は、その結合演算に対するキーとして用いられる。
【表１９】
2008547131.tif 000021
【００７６】
「Prepare」要素５１４から「Rollup」要素５１８へ送られる結合の結果得られたレコード（第２ステージキーセットにないキーフィールドに対してはワイルドカード値を含む）は、下記テーブルに表される。
【表２０】
2008547131.tif 000022
【００７７】
「Rollup」要素５１８は、一致する合成キー値（「key0」及び「key1」）をもつレコードを組み合わせ、「異なるものをカウント（target）」するフィールド内の対応する値を合計して、異なる「target」フィールド値を幾つか生成する。下記テーブルに表される得られた出力レコードは、出力データセット５２０内に格納される。
【表２１】
2008547131.tif 000023
【００７８】
上記テーブル内の行は、整数値を含むキーフィールドにより分解し、ワイルドカード値を含むキーフィールドについて集約した「target」フィールドの異なる値の数を表す。
【００７９】
２．４．３  追加ステージの追加
上述したマルチステージ集約によりもたらされる計算時間の節減は、集約の追加ステージに拡張することができる。従属及び非従属のキーフィールドは、下記実施例におけるように、各集約ステージで適切に取り扱われるべきである。例えば、データセットの次元を低減するために、ワイルドカードの値を、除去するべきキーフィールドへ追加することができる。非従属のキーフィールドに対しては、非従属キーフィールド内のワイルドカードの値及び特定の値のパターンは、合成キー及び「target」フィールドに対する初期ロールアップにより一旦パターンが設定されたら、変更すべきではない。この初期ロールアップ中に、非従属キーフィールドがワイルドカードの値を取得した場合、そのキーフィールドは、そのキーフィールドを省略する後続のロールアップ演算に対して値を一致させるためにのみ、用いるべきである。もし、初期ロールアップ中に非従属キーフィールドが特定の値を保持しているのであれば、そのキーフィールドは、そのキーフィールドを含む後続のロールアップ演算に対して値を一致させるためにのみ、用いるべきである。上述した実施例でのように、もし、対応する第１ステージ及び第２ステージのキーセットが、従属キーフィールド内でのみ異なるのであれば、ワイルドカードの値は、第２ステージの処理中に非従属キーフィールドへ導入されず、それにより正しい結果が生じる。
【００８０】
図７は、３ステージの集約計算を実装する例示のデータフローグラフ６００を示す。「Prepare」要素６０６は、非従属キーフィールドを含む入力ファイル６０４内のキーセットに基づいて、入力データセット６０２のレコードを処理する。「Rollup」要素６０８は、「target」フィールドと合成キーとに基づいてレコードを組み合わせ、「Rollup」要素６０９は、中間レコード６１０が入力データセット６０２と同じ次元を有するように、全てのキーフィールドに基づいてレコードを組み合わせる。入力ファイル６１４内の第２ステージキーセットは、中間データセット６１８が特定の次元となるように、非従属のキーフィールド及び必要に応じてオプションで幾つかの従属キーフィールドを含む。入力ファイル６２２内の第３ステージキーセットは、所望の低次元の出力データセット６２６を生成するための最終キーフィールドを含む。
【００８１】
例えば、入力データセット６０２は、４次元を有し、その内の２次元は従属であり（「key0」及び「key1」）、２次元は非従属である（「key2」及び「key3」）。出力データセット６２６は、３次元中間データセット６１８に基づく２次元以下の次元を有する集約を含む。本例の適切な３ステージロールアッププランは、下記テーブルで表される。
【表２２】
2008547131.tif 000024
【００８２】
上述したように、非従属キーフィールドの有無は、ステージ１とステージ３の間では変化しない。
【００８３】
場合によっては、セクション２．３で説明した手順のように、キーセットの選択は、可能性のある適切な次元の総てのキーセットを評価し、それらから生成され得る所望の集約の数の観点からそれらをランク付けし、最高ランクをもつキーセットを選択することにより決定される。
【００８４】
３  代替法
３．１  近似的な関数従属性
関数従属性を用いて集約計算のサイズを低減するためのアプローチは、関数従属性が例外の存在により厳密でない場合に対しても適用され得る。例えば、小売りチェーンにおいては、全顧客の８０％が一店舗でのみ買い物をしたことがあるといったような、「顧客ＩＤ」と「店舗」との間に弱い関数従属性が存在することがある。また、データセット内に単一の取引しか有していない「一回限りの客（singleton）」が存在し、従って、その顧客に対するフィールド総てがその顧客ＩＤに関数従属している場合がある。一回限りの客の数及び様々な関数従属性の強度を判定することにより、入力データセットを適切に取り扱うことができる幾つかのカテゴリに分割できる。
【００８５】
３．２  より高次の関数従属性
場合によっては、より高次の関数従属性を用いて計算を低減することが可能なことがある。幾つかのキーフィールドは、「target」フィールドと別のフィールドとの組み合わせに関数従属していることがある。
【００８６】
例えば、４つの非従属次元があり、２次元集約の総てが所望される場合、１０ロールアップ演算と対応する１０集約となる。しかし、次元１〜３が次元０と「target」フィールドとの組み合わせに従属している場合、次元０に関わる４つのロールアップ演算は、単一のロールアップ演算にまとめることができるので、ロールアップ演算のセットは１０から７へ低減することができる。
【００８７】
３．３  実装
上述のデータ集約アプローチは、コンピュータ上で実行するためのソフトウエアを用いて実装できる。例えば、本ソフトウエアは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム（揮発性及び不揮発性メモリ及び／又は記憶素子を含む）、少なくとも一つの入力装置又はポート、及び、少なくとも一つの出力装置又はポートをそれぞれが含む、一台以上のプログラム済み又はプログラム可能なコンピューターシステム（分散型、クライアント／サーバ型、又はグリッド型のような各種アーキテクチャを備えるシステム）上で実行される、一つ以上のコンピュータープログラムに手順を形成する。本ソフトウエアは、例えば、計算グラフの設計及び構成に関連する他のサービスを提供するような、大規模なプログラムの内の一つ以上のモジュールを形成してもよい。グラフのノード及び要素は、コンピュータ可読媒体に格納されるデータ構造、又はデータ収納庫内に格納されるデータモデルに準拠する他の体系化されたデータとして実装することができる。
【００８８】
本ソフトウエアは、汎用又は専用のプログラム可能なコンピュータにより可読なＣＤ−ＲＯＭ等の媒体上で提供されるか、又は本ソフトウエアが実行される場所となるコンピュータにネットワークを介して配送する（伝送信号に符号化して配送する）ことができる。機能は全て、専用コンピュータ上で、又はコプロセッサのような専用ハードウエアを用いて、実行することができる。本ソフトウエアは、本ソフトウエアが規定する計算の異なる部分が異なるコンピュータにより実行される、分散方法で実装することができる。このようなコンピュータープログラムはそれぞれ、汎用又は専用のプログラム可能なコンピュータにより可読な記憶媒体又は装置（例えば、固体のメモリもしく媒体、又は磁気もしく光学の媒体）へ格納又はダウンロードされ、記憶媒体又は装置がコンピューターシステムにより読み出される際に本明細書で説明した手順を実行すべく、コンピュータを構成し、動作させることが好ましい。本発明のシステムはまた、コンピュータープログラムにより構成されるコンピュータ可読記憶媒体として実装されるようにも考えられていて、そのように構成された記憶媒体により、コンピューターシステムは、本明細書で説明した機能を実行するよう特定かつ所定の方法で動作する。
【００８９】
言うまでもなく、上記説明は説明を意図したものであり、本発明の範囲を制限する意図はなく、その範囲は付帯のクレームの範囲により定義される。例えば、上記説明の幾つかの機能ステップは、全体の処理に実質的に影響を与えることなく異なる順序で実行され得る。他の実施の形態は特許請求の範囲内にある。
【図面の簡単な説明】
【００９０】
【図１】データ集約システムである
【図２Ａ】多次元データを表すテーブルである。
【図２Ｂ】図２Ａのデータに基づく集約データを表すテーブルである。
【図２Ｃ】図２Ａのデータに基づく集約データを表すテーブルである。
【図２Ｄ】図２Ａのデータに基づく集約データを表すテーブルである。
【図２Ｅ】図２Ａのデータに基づく集約データを表すテーブルである。
【図２Ｆ】図２Ａのデータに基づく集約データを表すテーブルである。
【図２Ｇ】図２Ａのデータに基づく集約データを表すテーブルである。
【図３】単一ステージ集約のデータフロー図である。
【図４】マルチステージ集約のデータフロー図である。
【図５】単一ステージ集約のデータフロー図である。
【図６】マルチステージ集約のデータフロー図である。
【図７】マルチステージ集約のデータフロー図である。
【図１】
2008547131.tif 000025
【図２Ａ】
2008547131.tif 000026
【図２Ｂ】
2008547131.tif 000027
【図２Ｃ】
2008547131.tif 000028
【図２Ｄ】
2008547131.tif 000029
【図２Ｅ】
2008547131.tif 000030
【図２Ｆ】
2008547131.tif 000031
【図２Ｇ】
2008547131.tif 000032
【図３】
2008547131.tif 000033
【図４】
2008547131.tif 000034
【図５】
2008547131.tif 000035
【図６】
2008547131.tif 000036
【図７】
2008547131.tif 000037
【手続補正書】
【提出日】平成20年5月22日(2008.5.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを集約するための方法であって：
第１データセットを受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットから第２データセットを生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；
前記第２データセットから第３データセットを生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応するステップ；を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算に基づく計算を実行した結果を表し、更に、
前記データセットを格納するステップ又はユーザーインターフェース上に前記データセットに基づく結果を提示するステップ；を含む、方法。
【請求項２】
請求項１に記載の方法において、
前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算を実行することは、前記値間の幾つかの異なる値を決定すること、前記値の中央値を決定すること、前記値全体の複数の極値の合計値を決定すること、及び、前記値の複数の合計値の極値を決定すること、からなるグループの内の一つである、
方法。
【請求項３】
請求項１に記載の方法において、
前記非カスケード演算は、一セットのオペランドに対して前記非カスケード演算を実行した結果が、前記オペランドの第１サブセットに対して前記演算を実行した第１結果及び前記オペランドの第２サブセットに対して前記演算を実行した第２結果、に対して前記演算を実行した結果に分解しないようなものであり、前記第１サブセット及び第２サブセットは、相互に排他的かつ包括的である、
方法。
【請求項４】
請求項１に記載の方法において、
前記複数のフィールドの内の少なくとも一つは、前記複数のフィールドの内の別のフィールドに少なくとも部分的に関数従属する、
方法。
【請求項５】
請求項４に記載の方法において、
前記複数のフィールドの内の少なくとも一つと関連する少なくとも幾つかの値は、前記複数のフィールドの内の別のフィールドと関連する対応値に従属する、
方法。
【請求項６】
請求項１に記載の方法において、
前記第２データセットから前記第３データセットを生成するステップは、前記第２データセットの集約レコードのフローを受け取るステップを含む、
方法。
【請求項７】
コンピュータ可読媒体上に格納されるソフトウエアであって：
第１データセットを受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持している、ステップ；
前記第１データセットから第２データセットを生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセットを生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；
の各ステップをコンピューターシステムに実行させるための命令を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に対して非カスケード演算に基づく計算を実行した結果を表す、ソフトウエア。
【請求項８】
データを集約するためのシステムであって：
第１データセットを受け取るための手段であって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、手段；
前記第１データセットから第２データセットを生成するための手段であって、前記第２データセットは一つ以上の集約レコードを含み、前記第２データセットの各集約レコードは、その集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、手段；及び、
前記第２データセットから第３データセットを生成するための手段であって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、手段；を含み、
前記第３データセット内の集約レコードと関連する集約値は、前記第１データセットからの複数のレコードと関連する値に、非カスケード演算に基づく計算を実行した結果を表す、システム。
【請求項９】
複数のレコードを含むデータを集約するための方法であって、各レコードは複数のフィールドのそれぞれに対する値を保持し、前記方法は、フィールド間の関数従属性を考慮に入れて、非カスケード演算を用いることにより、このようなレコード内のフィールドのマルチステージ集約を実行するステップを含む、方法。
【請求項１０】
請求項９に記載の方法において、
前記非カスケード演算は、前記値間の幾つかの異なる値を決定するステップ、前記値の中央値を決定するステップ、前記値全体の複数の極値の合計値を決定するステップ、及び、前記値の複数の合計値の極値を決定するステップから構成されるグループの内の一つである、
方法。
【請求項１１】
請求項９に記載の方法において、
前記非カスケード演算は、一セットのオペランドに対して前記非カスケード演算を実行した結果が、前記オペランドの第１サブセットに対して前記演算を実行した第１結果及び前記オペランドの第２サブセットに対して前記演算を実行した第２結果、に対して前記演算を実行した結果に分解しないようなものであり、前記第１サブセット及び第２サブセットは、相互に排他的かつ包括的である、
方法。
【請求項１２】
データを集約するための方法であって：
第１データセットを受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットのレコードと、第１の複数のキーセットと、のデカルト積を生成するステップであって、各キーセットは前記第１データセットの前記フィールドのサブセットを表す、ステップ；
前記生成されたデカルト積から第２データセットを生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；
前記第２データセットから第３データセットを生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；及び、
前記データセットを格納するステップ又はユーザーインターフェース上に前記データセットに基づく結果を提示するステップ；を含む、方法。
【請求項１３】
請求項１２に記載の方法において、
前記第３データセットを生成する前記ステップは、前記生成されたデカルト積と、前記第１の複数のキーセットの一つを表す第１の値及び第２の複数のキーセットの一つを表す第２の値をそのレコードが含むデータセットと、に結合演算を実行するステップを含み、前記第２の複数のキーセットのそれぞれは前記第２データセットの前記フィールドのサブセットを表し、前記結合演算は一致するキーセットを有するレコードを結合する、
方法。
【請求項１４】
請求項１３に記載の方法において、
前記第３データセットを生成する前記ステップは、少なくとも幾つかの結合されたレコードに対して、前記フィールドの少なくとも一つに対する値をワイルドカードの値と置き換えるステップを含む、
方法。
【請求項１５】
請求項１２に記載の方法において、
前記第２データセットを生成するステップは、前記生成されたデカルト積の内の少なくとも幾つかのレコードに対して、前記フィールドの少なくとも一つに対する値をワイルドカードの値と置き換えるステップを含む、
方法。
【請求項１６】
コンピュータ可読媒体上に格納されるソフトウエアであって：
第１データセットを受け取るステップであって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、ステップ；
前記第１データセットのレコードと第１の複数のキーセットとのデカルト積を生成するステップであって、各キーセットは前記第１データセットの前記フィールドのサブセットを表す、ステップ；
前記生成されたデカルト積から第２データセットを生成するステップであって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、ステップ；及び、
前記第２データセットから第３データセットを生成するステップであって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、ステップ；の各ステップをコンピューターシステムに実行させるための命令を含む、ソフトウエア。
【請求項１７】
データを集約するためのシステムであって：
第１データセットを受け取るための手段であって、前記第１データセットはレコードを含み、各レコードは複数のフィールドのそれぞれに対する値を保持する、手段；
前記第１データセットのレコードと第１の複数のキーセットとのデカルト積を生成するための手段であって、各キーセットは、前記第１データセットの前記フィールドのサブセットを表す、手段；
前記生成されたデカルト積から第２データセットを生成するための手段であって、前記第２データセットは一つ以上の集約レコードを含み、各集約レコードは、前記集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットからの一つ以上のレコードと対応する、手段；及び、
前記第２データセットから第３データセットを生成するための手段であって、前記第３データセットは一つ以上の集約レコードを含み、前記第３データセットの各集約レコードは、前記第３データセットのその集約レコードと関連するフィールドのサブセット内の値と一致する前記第１データセットの一つ以上の集約レコードと対応する、手段；を含む、システム。
【国際調査報告】
2008547131.tif 000038