(57)【特許請求の範囲】
【請求項１】
データ要素を処理するためのフローを形成する方法であって、
コンピュータが、各々のフローが前記階層のレベルと関連付けられる、データ要素の複数のフローを形成するステップを含み、
前記形成するステップは、
複数のレベルを含む階層と関連する複数のデータ要素を含む入力データ構造を受け取るステップと、
前記複数のフローのフローそれぞれに、前記入力データ構造の少なくとも幾つかのデータ要素を含め、かつ前記フローのうちの少なくとも幾つかに、前記階層のレベルと関連する階層構造情報を表す一つ以上の構造要素を含め、二つのデータ要素間に含まれる少なくとも一つの構造要素を含めるステップであって、二つ以上かつ全フロー数未満の前記フローそれぞれに、前記階層の共通のレベルと関連する少なくとも一つの構造要素を含めるステップと、
少なくとも一つの他のフローに含まれるデータ要素を処理するために用いられる処理と異なる処理に従って、少なくとも一つのフローに含まれるデータ要素を処理するように、前記形成されたフローのそれぞれを出力するステップと、
を含む方法。
【請求項２】
請求項１に記載の方法であって、
前記構造要素には、一つ以上のデータ要素の隣接するセットを分離する分離要素が一つのフロー内に含まれ、各分離要素は前記階層のレベルと関連付けられ、
二つ以上かつ全フロー数未満の前記フローそれぞれが、前記階層の共通のレベルと関連する少なくとも一つの分離要素を含む、方法。
【請求項３】
請求項２に記載の方法であって、
前記分離要素に少なくとも一部は基づいて、前記入力データ構造に関連する階層データ構造内の前記データ要素の表現と、前記複数のフロー内の前記データ要素の表現との間での変換を行うステップを更に含む、方法。
【請求項４】
請求項３に記載の方法であって、
前記階層データ構造がマークアップ言語によりフォーマットされる、方法。
【請求項５】
請求項４に記載の方法であって、
前記マークアップ言語がＸＭＬである、方法。
【請求項６】
請求項３に記載の方法であって、
前記階層データ構造がプログラミング言語によりフォーマットされる、方法。
【請求項７】
請求項６に記載の方法であって、
前記プログラミング言語がＰＬ／Ｉ、ＣＯＢＯＬ、またはＩＭＳである、方法。
【請求項８】
請求項３に記載の方法であって、
前記表現の間での変換を行うステップには、前記階層データ構造内の前記データ要素の表現から前記複数のフロー内の前記データ要素の表現への変換を行うステップが含まれる、方法。
【請求項９】
請求項８に記載の方法であって、
データ要素の複数のフローを形成するステップには、
前記階層データ構造から、第一レベルと関連する第一データ要素を抽出するステップと、
前記第一データ要素と対応する前記階層データ構造の一部内にネストされた第二レベルと関連する一つ以上のデータ要素を抽出するステップと、
前記第二レベルと関連するフロー内に、前記第二レベルと関連する、前記抽出されたデータ要素のうちの少なくとも幾つかを含めるステップと、
前記第一レベルと関連するフロー内に前記第一データ要素を含め、前記第二レベルと関連する前記フロー内に前記第一レベルと関連する、対応する分離要素を含めるステップと、
が含まれる、方法。
【請求項１０】
請求項８に記載の方法であって、
データ要素の複数のフローを形成するステップには、
複数の階層データ構造のストリームを受け取るステップと、
階層データ構造毎に、
前記階層データ構造からデータ要素を抽出するステップであって、各データ要素は対応するレベルと関連付けられるステップと、
親データ要素と対応する前記階層データ構造の一部内にネストされた一つ以上の子データ要素の所与のセットに対して、
前記子データ要素と対応するレベルと関連するフロー内に、前記子データ要素のセットおよび分離要素を含めるステップと、
前記親データ要素と対応するレベルと関連するフロー内に前記親データ要素を含めるステップと、
が含まれる、方法。
【請求項１１】
請求項１０に記載の方法であって、
前記含められた分離要素が前記親データ要素と対応するレベルと関連付けられる、方法。
【請求項１２】
請求項３に記載の方法であって、
前記表現の間での変換を行うステップには、前記複数のフロー内の前記データ要素の表現から前記階層データ構造内の前記データ要素の表現への変換を行うステップが含まれる、方法。
【請求項１３】
請求項１２に記載の方法であって、
第一レベルと関連するフローから第一データ要素を受け取るステップと、
第二レベルと関連するフローから、前記第一レベルと関連する一つ以上のデータ要素および分離要素を受け取るステップと、
前記階層データ構造の一部に前記第一データ要素を含めるステップと、
前記第一データ要素を含む前記階層データ構造の一部内にネストされた前記第二レベルと関連するフローから受け取った前記データ要素のうち少なくとも幾つかを含めるステップと、
を更に含む、方法。
【請求項１４】
請求項１２に記載の方法であって、
複数の階層データ構造のストリームを生成するステップを更に含み、
階層データ構造毎に、
前記所与のレベルと関連するフローから所与のレベルと関連するデータ要素を受け取るステップと、
第一レベルと関連するフローから受け取ったデータ要素毎に、
前記階層データ構造の一部に前記受け取ったデータ要素を含めるステップと、
他のレベルと関連するフロー内の分離要素に基づいて、前記他のレベルと関連する一つ以上のデータ要素の対応するセットが存在するかどうかを特定するステップと、
前記対応する受け取ったデータ要素を含む前記階層データ構造の一部内にネストされた一つ以上のデータ要素の対応する各セットを含めるステップと、
が含まれる、方法。
【請求項１５】
請求項１４に記載の方法であって、
前記他のレベルと関連するフロー内の前記分離要素は前記第一レベルと関連付けられる、方法。
【請求項１６】
請求項１に記載の方法であって、
前記階層構造情報には、前記階層のレベルの複数のデータ要素のうちの少なくとも一つのデータ要素を一意に識別する、少なくとも幾つかのデータ要素内に含まれる一つ以上のインデックス値が含まれ、各インデックス値は前記階層のレベルと関連付けられ、
前記レベルのうちの少なくとも一つについて、二つ以上かつ全フロー数未満の前記フローに、そのレベルと関連するインデックス値が含まれる、方法。
【請求項１７】
請求項１６に記載の方法であって、
少なくとも幾つかのデータ要素には、前記階層に従って親データ要素を一意に識別するインデックス値が含まれる、方法。
【請求項１８】
請求項１６に記載の方法であって、
前記インデックス値に少なくとも一部は基づいて、階層データ構造内の前記データ要素の表現と前記複数のフロー内の前記データ要素の表現との間での変換を行うステップが更に含まれる、方法。
【請求項１９】
請求項１８に記載の方法であって、
前記階層データ構造がマークアップ言語によりフォーマットされる、方法。
【請求項２０】
請求項１９に記載の方法であって、
前記マークアップ言語がＸＭＬである、方法。
【請求項２１】
請求項１８に記載の方法であって、
前記階層データ構造がプログラミング言語によりフォーマットされる、方法。
【請求項２２】
請求項２１に記載の方法であって、
前記プログラミング言語がＰＬ／Ｉ、ＣＯＢＯＬ、またはＩＭＳである、方法。
【請求項２３】
データ要素に対するフローを形成するシステムであって、
各々のフローが前記階層のレベルと関連付けられる、データ要素の複数のフローを形成する手段を備え、
前記形成する手段は、
複数のレベルを含む階層と関連する複数のデータ要素を含む入力データ構造を受け取り、
前記複数のフローのフローそれぞれに、前記入力データ構造の少なくとも幾つかのデータ要素を含め、かつ前記フローのうちの少なくとも幾つかに、前記階層のレベルと関連する階層構造情報を表す一つ以上の構造要素を含め、二つのデータ要素間に含まれる少なくとも一つの構造要素を含める手段とを含み、
二つ以上かつ全フロー数未満の前記フローそれぞれに、前記階層の共通のレベルと関連する少なくとも一つの構造要素が含まれ、
少なくとも一つの他のフローに含まれるデータ要素を処理するために用いられる処理と異なる処理に従って、少なくとも一つのフローに含まれるデータ要素を処理するように、前記形成されたフローのそれぞれを出力する、
システム。
【請求項２４】
複数のレベルを含む階層と関連するデータ要素を処理するためのフローを形成するグラフベース計算の仕様を処理するコンピュータープログラムを格納するコンピュータで読取り可能な媒体であって、前記コンピュータープログラムは、コンピュータに、
各々のフローが前記階層のレベルと関連付けられるデータ要素の複数のフローを形成させる命令を含み、
前記形成させる命令は、
複数のレベルを含む階層と関連する複数のデータ要素を含む入力データ構造を受け取る命令と、
前記複数のフローのフローそれぞれに、前記入力データ構造の少なくとも幾つかのデータ要素を含め、かつ前記フローのうちの少なくとも幾つかに、前記階層のレベルと関連する階層構造情報を表す一つ以上の構造要素を含め、二つのデータ要素間に含まれる少なくとも一つの構造要素を含めさせる命令であり、
二つ以上かつ全フロー数未満の前記フローそれぞれに、前記階層のレベルと関連する少なくとも一つの構造要素が含まれる命令と、
少なくとも一つの他のフローに含まれるデータ要素を処理するために用いられる処理と異なる処理に従って、少なくとも一つのフローに含まれるデータ要素を処理するように、前記形成されたフローのそれぞれを出力する命令と、
を含むコンピュータで読取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフベースの計算におけるデータフロー管理に関する。
【背景技術】
【０００２】
複雑な計算は、多くの場合、有向グラフによるデータフローとして表すことができ、計算コンポーネントはそのグラフの頂点と関連付けられ、コンポーネント間のデータフローはグラフのリンク（弧、辺）と対応付けられる。このようなグラフベースの計算を実装するシステムは、米国特許第５，９６６，０７２号、「ＥＸＥＣＵＴＩＮＧ  ＣＯＭＰＵＴＡＴＩＯＮＳ  ＥＸＰＲＥＳＳＥＤ  ＡＳ  ＧＲＡＰＨＳ（グラフとして表される計算の実行）」に記載されている。グラフベースの計算を実行する一手法は、グラフの異なる頂点とそれぞれが関連付けられる幾つかのプロセスを実行することと、グラフのリンクに従ってプロセス間の通信経路を確立することである。例えば、通信経路は、ＴＣＰ／ＩＰまたはＵＮＩＸ（登録商標）ドメインソケットを用いるか、または共有メモリを用いてプロセス間でデータを渡すことができる。
【発明の概要】
【０００３】
一態様では、概して、複数のレベルを含む階層と関連するデータ要素を処理するための方法は、各々のフローが階層のレベルと関連付けられるデータ要素の複数のフローを形成するステップと、フローのうちの少なくとも幾つかに、階層のレベルと関連する階層構造情報を含めるステップとを含む。レベルのうちの少なくとも一つにおいて、二つ以上かつ全フロー数未満のフローに、そのレベルと関連する階層構造情報が含まれる。
【０００４】
各態様には以下の特徴の内の一つ以上が含まれる。
【０００５】
階層構造情報には、一つ以上のデータ要素の隣接するセットを分離する分離要素が含まれ、各分離要素は階層のレベルと関連付けられ、レベルのうちの少なくとも一つのレベルについて、二つ以上かつ全フロー数未満のフローがそのレベルと関連する分離要素を含む。
【０００６】
本方法は、分離要素に少なくとも一部は基づいて、階層データ構造内のデータ要素の表現と複数のフロー内のデータ要素の表現との間での変換を行うステップを更に含んでいる。
【０００７】
階層データ構造はマークアップ言語によりフォーマットされる。
【０００８】
マークアップ言語はＸＭＬである。
【０００９】
階層データ構造はプログラミング言語によりフォーマットされる。
【００１０】
プログラミング言語はＰＬ／Ｉ、ＣＯＢＯＬまたはＩＭＳである。
【００１１】
表現の間での変換を行うステップには、階層データ構造内のデータ要素の表現から複数のフロー内のデータ要素の表現への変換を行うステップが含まれる。
【００１２】
データ要素の複数のフローを形成するステップには、階層データ構造から第一レベルと関連する第一データ要素を抽出するステップと、第一データ要素と対応する階層データ構造の一部内にネストされた第二レベルと関連する一つ以上のデータ要素を抽出するステップと、第二レベルと関連するフロー内に、第二レベルと関連する、抽出されたデータ要素のうちの少なくとも幾つかを含めるステップと、第一レベルと関連するフロー内に第一データ要素を含め、第二レベルと関連するフロー内に第一レベルと関連する対応する分離要素を含めるステップとが含まれる。
【００１３】
データ要素の複数のフローを形成するステップには、複数の階層データ構造のストリームを受け取るするステップと、階層データ構造毎に、階層データ構造からデータ要素を抽出するステップであって、各データ要素は対応するレベルと関連付けられる抽出ステップと、親データ要素と対応する階層データ構造の一部内にネストされた一つ以上の子データ要素の所与のセットに対して、子データ要素と対応するレベルと関連するフロー内に、子データ要素のセットおよび分離要素を含めるステップと、親データ要素と対応するレベルと関連するフロー内に親データ要素を含めるステップとが含まれる。
【００１４】
含められた分離要素は、親データ要素と対応するレベルと関連付けられる。
【００１５】
表現の間での変換を行うステップには、複数のフロー内のデータ要素の表現から階層データ構造内のデータ要素の表現への変換を行うステップが含まれる。
【００１６】
本方法は、第一レベルと関連するフローから第一データ要素を受け取るステップと、第二レベルと関連するフローから、第一レベルと関連する一つ以上のデータ要素および分離要素を受け取るステップと、階層データ構造の一部に第一データ要素を含めるステップと、第一データ要素を含む階層データ構造の一部内にネストされた第二レベルと関連するフローから受け取ったデータ要素のうちの少なくとも幾つかを含めるステップとを更に含んでいる。
【００１７】
本方法は、マルチ階層データ構造のストリームを生成するステップを更に含み、階層データ構造毎に、所与のレベルと関連するフローから所与のレベルと関連するデータ要素を受け取るステップを含み、第一レベルと関連するフローから受け取ったデータ要素毎に、受け取ったデータ要素を階層データ構造の一部に含めるステップと、他のレベルと関連するフロー内の分離要素に基づいて、他のレベルと関連する一つ以上のデータ要素の対応するセットが存在するかどうかを特定するステップとを含み、その対応する受け取ったデータ要素を含む階層データ構造の一部内にネストされた一つ以上のデータ要素の対応する各セットを含めるステップとを含んでいる。
【００１８】
他のレベルと関連するフロー内の分離要素は第一レベルと関連付けられる。
【００１９】
階層構造情報には、階層のレベルの複数のデータ要素の内の少なくとも一つのデータ要素を一意に識別する少なくとも幾つかのデータ要素内に含まれる一つ以上のインデックス値が含まれ、各インデックス値は階層のレベルと関連付けられ、レベルのうちの少なくとも一つについて、二つ以上かつ全フロー数未満のフローにそのレベルと関連するインデックス値が含まれる。
【００２０】
データ要素のうちの少なくとも幾つかには、階層に従って親データ要素を一意に識別するインデックス値が含まれる。
【００２１】
本方法は、インデックス値に少なくとも一部は基づいて、階層データ構造内のデータ要素の表現と複数のフロー内のデータ要素の表現との間での変換を行うステップを更に含んでいる。
【００２２】
階層データ構造はマークアップ言語によりフォーマットされる。
【００２３】
マークアップ言語はＸＭＬである。
【００２４】
階層データ構造はプログラミング言語によりフォーマットされる。
【００２５】
プログラミング言語はＰＬ／Ｉ、ＣＯＢＯＬまたはＩＭＳである。
【００２６】
別の態様では、概して、複数のレベルを含む階層と関連するデータ要素を処理するシステムは、各々のフローが階層のレベルと関連付けられるデータ要素の複数のフローを形成する手段と、前記階層のレベルと関連する階層構造情報を、フローのうちの少なくとも幾つかに含める手段とを含み、前記複数のレベルの内の少なくとも一つのレベルについて、二つ以上かつ全フロー数未満のフローに、そのレベルと関連する階層構造情報が含まれる。
【００２７】
別の態様では、概して、コンピュータで読取り可能な媒体上に格納されたグラフベース計算の仕様を処理するためのコンピュータープログラムであって、前記コンピュータープログラムは、コンピュータに、各々のフローが階層のレベルと関連付けられるデータ要素の複数のフローを形成させる命令と、これらのフローのうちの少なくとも幾つかに、階層のレベルと関連する階層構造情報を含めさせる命令とを含み、これらのレベルの内の少なくとも一つについて、二つ以上かつ全フロー数未満のフローに、そのレベルと関連する階層構造情報が含まれる。
【００２８】
各態様は以下の利点の内の一つ以上を有する。
【００２９】
データ要素のフローに階層構造情報を含めるステップにより、グラフベース計算内のコンポーネントは、コンポーネントを連結するリンクにまたがる異なるフロー内のデータ要素間の関連を認識することができるよるになる。階層データ構造の要素は、データ構造全体の表現をメモリ内に格納しなくても、その関連性を保ったまま、データ要素内の合成キーから、または分離要素から抽出することができる。合成キーを用いて、階層からの関連性に基づいてデータ要素をグループ化するステップを含むデータ要素に対する各種の操作を容易にすることができる。例えば、合成キーを、少なくとも幾つかの階層関連性を再構成するか、またはデータ要素を再編成するための、結合操作内におけるキーフィールドとして用いることができる。また、フロー内の分離要素の編成により、コンポーネントは元のデータ構造から少なくとも幾つかの階層関連性を再構成することもできる。幾つかの階層構造は、フロー内の離散的データ要素により黙示的に表されるので、フロー内に分離要素を選択的に挿入すると、全てのデータ要素に挿入される合成キーよりずっと効率的に構造を表すことができる場合もある。例えば、所与のレベルと関連付けられる分離要素を、下位レベルのフローにのみ含めることができ、同位または高位レベルのフロー内に含める必要がない（下位レベルとは、ルートからより遠い、関連する階層のレベルと対応する、より深くネストされているレベルを表す）。同様に、合成キーを用いて階層を効率的に表現するには、所与のレベルと関連する合成キーをも、そのレベルに親を有するデータ要素のフローにのみ含めることができ、異なるレベルに親を有するデータ要素を持つフローに含める必要がない。
【００３０】
本発明の他の特徴および利点は、以下の説明およびクレームから明らとなる。
【図面の簡単な説明】
【００３１】
【図１Ａ】グラフベース計算を実行するためのシステムのブロック図である。
【図１Ｂ】計算グラフの図である。
【図１Ｃ】ネストされたドキュメントの階層を表すツリーの図である。
【図２】計算グラフの図である。
【図３Ａ】計算グラフの図である。
【図３Ｂ】データを処理するためのプロシージャのフローチャートである。
【図３Ｃ】正規化コンポーネントからのフローの図である。
【図４Ａ】計算グラフの図である。
【図４Ｂ】正規化コンポーネントからのフローの図である。
【図４Ｃ】正規化コンポーネントからのフローの図である。
【図４Ｄ】正規化コンポーネントからのフローの図である。
【図４Ｅ】データを処理するためのプロシージャのフローチャートである。
【発明を実施するための形態】
【００３２】
図１Ａを参照すると、グラフベース計算を実行するためのシステム１００には、データ格納１０２に結合される開発環境１０４およびデータ格納１０２に結合されるランタイム環境１０８が含まれる。開発者１０１は開発環境１０２を用いてアプリケーションを構築する。アプリケーションは、開発者が開発環境１０２を使用した成果として、データ格納に書き込まれてもよいデータ格納１０２内のデータ構造により規定される一つ以上の計算グラフと関連付けられる。計算グラフ１０５に対するデータ構造１０３は、例えば、計算グラフの頂点（コンポーネントまたはデータセット）および頂点間のリンク（ワーク要素のフローを表す）を規定する。データ構造には、計算グラフ（「データフローグラフ」とも呼ばれる）のコンポーネント、データセットおよびフローの各種特性を含めることもできる。例えば、データ処理アプリケーションは、一つ以上の入力データセットから、コンポーネント処理グラフを介して、一つ以上の出力データセットまで流れるデータに対して実行される計算を実装する計算グラフと関連付けてもよい。
【００３３】
ランタイム環境１０８は、ＵＮＩＸ（登録商標）オペレーティングシステム等の適切なオペレーティングシステムの管理のもとで、一台以上の汎用コンピュータ上で動作させてもよい。例えば、ランタイム環境１０８には、ローカル（例えば、ＳＭＰコンピュータ等のマルチプロセッサシステム）もしくはローカル分散環境（例えば、クラスタまたはＭＰＰとして結合されるマルチプロセッサ）、またはリモート、もしくはリモート分散環境（例えば、ＬＡＮやＷＡＮネットワークを経由して結合されるマルチプロセッサ）、またはこれらの任意の組合せのいずれかによる複数の中央処理ユニット（ＣＰＵ）を用いるコンピューターシステムの構成を含むマルチノード並列計算環境を含めることができる。ランタイム環境１０８がアクセスする入力、出力または中間データセットは、並列ファイルシステムに（例えば、データ格納１０２、または、ローカルまたは通信リンク経由のリモートでシステム１００に結合される外部データストレージ内に）格納される並列「マルチファイル」とすることができる。
【００３４】
グラフ内の複数のコンポーネントを同時に実行することにより並列処理の一形式が提供される。グラフの各種のコンポーネントを様々な計算ノードに分散させることにより、更なる並列処理を達成できる。グラフの要素（例えば、データセット、コンポーネント、およびフロー）を明示的または黙示的に複製して、ランタイム環境１０８に更なる並列処理を導入できる。
【００３５】
ランタイム環境１０８は、計算を実行し、構成するために、格納されているスクリプトまたはユーザー１０７からの制御入力を受け取るよう構成される。制御入力には、格納されているグラフデータ構造内で規定されている、対応する計算グラフを用いる特定のデータセットを処理するコマンドを含めることができる。ユーザー１０７は、例えば、コマンドラインやグラフィカルインターフェースを用いて、ランタイム環境１０８と交信することができる。
【００３６】
ランタイム環境１０８には、所与の計算グラフを規定する、格納されたグラフデータ構造を読み出して、コンポーネントの計算を実行するためのプロセス（例えば、ホストオペレーティングシステム内部の実行プロセスまたは実行スレッド）等の、計算リソースの割り当て及び構成をする、実行時前モジュール１１０が含まれる。実行時前モジュール１１０は、コンポーネント間のリンクを実装するためのコンポーネント間通信リソース（例えば、いわゆるパイプまたは共有メモリ）も割り当て、プロセスが新規ワーク要素を受け取る準備が整っていないコンポーネントの入力ポートに到着したワーク要素の格納空間を割り当てる。コンポーネント間のリンクを介してワーク要素を渡すリソースは、システム１００の処理および格納のオーバーヘッドに貢献する。
【００３７】
ランタイム環境１０８には、実行時前モジュール１１０が計算グラフに割り当てるプロセスの実行をスケジュール化し、制御する実行モジュール１１２が含まれる。実行モジュール１１２は、グラフコンポーネントと関連する処理の間にアクセスされるデータベースエンジン、データストレージ、または他のモジュール等のシステム１００に結合される外部計算リソースと交信することができる。
【００３８】
図１Ｂを参照すると、４つのリンクされた頂点を有する計算グラフ１０５の単純な実施例には、入力データセット１２０が含まれ、入力データセットは、第一コンポーネント１２２にリンクされ、第一コンポーネントは第二コンポーネント１２４にリンクされ、第二コンポーネントは出力データセット１２６にリンクされている。リンクによりワーク要素はグラフ１０５の頂点間を流れることができる。幾つかのワーク要素はデータ要素１３０（データベースの個々のレコードまたは一つ以上のレコードと関連する値等）と対応し、幾つかのワーク要素は、実際のデータを表すとは限らないがデータ要素を処理するために用いられる処理要素１３２と対応する。例えば、処理要素１３２は、チェックポイント要素、計算ポイント要素、または分離要素を含むことができる。入力データセット１２０および出力データセット１２６は、例えば、データベースシステムと関連するレコードまたはトランザクション処理システムと関連するトランザクションを表してもよい。
【００３９】
本実施例では、コンポーネント１２２及び１２４は、全体の計算グラフ１０５により定義される計算の一部と関連付けられ、入力ポートでリンクを介して受け取る一つ以上の入力データ要素に基づいて計算を実行し、出力ポートからリンクを介して一つ以上の出力データ要素を提供する。出力データ要素は、例えば、入力要素を変換したバージョンであってもよいし、または出力データ要素は、入力データ要素のいずれかと直接対応するとは限らないこともある。コンポーネント１２２と１２４の間のワーク要素の内の幾つかは処理要素１３２である。コンポーネント１２４が受け取った処理要素１３２がチェックポイント要素と対応する場合、コンポーネント１２４はチェックポイントプロシージャを実行して、計算状態を格納し、障害が発生した際に、その計算におけるその時点までグラフ１０５が復元できるようにする。コンポーネント１２４が受け取った処理要素１３２が計算ポイントである場合、コンポーネント１２４は、（例えば、引用により本明細書に取り込まれる、米国特許第６，６５４，９０７号、「Ｃｏｎｔｉｎｕｏｕｓ  ｆｌｏｗ  ｃｏｍｐｕｔｅ  ｐｏｉｎｔ  ｂａｓｅｄ  ｄａｔａ  ｐｒｏｃｅｓｓｉｎｇ（「連続フロー計算ポイントに基づくデータ処理」）に詳細に記載されているように）最後の計算ポイント以降に受け取った一連のデータ要素に基づいて結果を更新する等の計算の所定操作を実行する。計算ポイントは、所与の計算の関連部分と対応する様々なフロー内部の場所をマーキングすることにより、グラフ内のコンポーネント間を同期させる形を提供できる。
【００４０】
分離要素により、同期が可能になるとともに、様々なフロー内のデータ要素間の関連性を各コンポーネントが認識することも可能になる。例えば、分離要素をワーク要素のフロー内で用いて、階層またはネスト構造を有するデータ等の構造化データの様々な部分と関連するデータ要素のグループを分離することができる。階層データ構造の例は、拡張マークアップ言語（ＸＭＬ）等のマークアップ言語に従ってフォーマットされたテキストを含むファイルまたはファイルの一部である。ＸＭＬ文書では、開始と終了の一対のタグを互いの内部でネスト化することができる。階層内のレベルは文書内のタグのネストの深さと対応する。ネスト構造を有するデータの別の例は、計算内部でネストされた繰返しループに対する引数のネスト化リストである。階層データは、ＰＬ／ＩまたはＣＯＢＯＬのようなプログラミング言語、またはＩＢＭ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ（ＩＭＳ）のような階層化データベースにおいて見られるような階層データ構造に従って、フォーマットすることもできる。
【００４１】
場合によっては、入力データセット内のデータが階層化されていてもよく、そのコンポーネントは、（例えば、フロー内のデータ要素としての）データ構造内部のデータ値だけでなく、データ値間の関連性の内の少なくとも幾つかをも受け取る必要があってもよい。これらの関連性は、フロー内の階層構造情報（例えば、分離要素または合成キー）を含めることにより指示できる。入力データセットからの階層データ構造は、データ構造からデータ値を抽出し、階層構造情報を含む一つ以上の出力フローを生成するコンポーネントが受け取ることができる。例えば、他の下流コンポーネントが元のデータ構造から階層関連性の内の少なくとも幾つかを特定できる編成では、分離要素によってデータ要素を分離することができる。あるいは、他の下流コンポーネントが元のデータ構造から階層関連性の内の少なくとも幾つかを特定できる代理キーをデータ要素に含めることができる。かかるコンポーネント（「正規化コンポーネント」と呼ぶ）の例については詳細に後述する。場合によっては、出力データセットに格納されるべき階層データ構造にデータ要素を編成する必要があってもよい。コンポーネントは、一つ以上のフローから受け取った様々なデータ要素をフロー内の分離要素に少なくとも一部は基づいてどのように編成すべきかを特定でき、出力データセットに対して適切なデータ構造を生成することができる。かかるコンポーネント（「非正規化コンポーネント」と呼ぶ）の例については詳細に後述する。
【００４２】
ＸＭＬ文書等の幾つかの階層データ構造は、データ構造内の要素にアクセスするためのインターフェースを提供するパーサを用いて処理することができる。ＸＭＬ文書では、パーサのための様々な手法の内の二つの例は、Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ  Ｃｏｎｓｏｒｔｉｕｍ（ワールドワイドウェブコンソーシアム）（Ｗ３Ｃ）が開発したドキュメントオブジェクトモデル（ＤＯＭ）仕様、およびＪａｖａ（登録商標）とそれに続く他のプログラミング言語のために開発されたＳＡＸ（Ｓｉｍｐｌｅ  ＡＰＩ  ｆｏｒ  ＸＭＬ）である。両手法は、階層を表すネスト構造内に任意の数のＸＭＬ要素を、そのタグ内のコンテンツが含んでいてもよい一対のルート開始と終了のタグを含む「適格な」ＸＭＬ文書のシンタックスに基づいている。ＸＭＬ要素のフォーマットは以下の通りである：
【００４３】
【数１】
0005453273.tif 000002
【００４４】
上記要素は、名前（本例では「ｔａｇ＿ｎａｍｅ」）と、オプションで、開始タグで定義される任意の数の属性とを有する開始と終了のタグにより区切られる。各属性は、名前（本例では「ａｔｔｒｉｂｕｔｅ＿ｎａｍｅ」）と引用符内の値を有する。いずれの対の開始と終了のタグの間にあるコンテンツにも、その一対の開始と終了のタグ内でネストされた他のＸＭＬ要素が含まれていてもよい。タグのネスト化に基づいて、各ＸＭＬドキュメントは、ルートタグと対応する「ルートノード」と、他のタグ内のＸＭＬ要素タグのネスト化と対応する、それぞれの親ノードに接続される幾つかの子ノードの構造をもつツリーによって表すことができる階層と対応する。
【００４５】
例えば、図１Ｃに示すツリー構造１４０は、下記のＸＭＬ文書内にネストされたタグから得られた「階層」を表す。ツリー構造１４０は、レベル１（ルートレベル）の単一ノード、および三つのレベルの深さに広がる子ノードを有する（各レベルは、ルートノードからの異なる距離に対応し、タグのネスト化の異なる深さに対応する）。各ノードは、対応する属性値によってラベルが付される。
【００４６】
【数２】
0005453273.tif 000003
【００４７】
ＳＡＸおよびＤＯＭの手法は、異なる利点を有する。ＸＭＬ文書を構文解析するためのＤＯＭ手法では、パーサは、ＸＭＬ文書のネストされたタグに基づいてノード間の親子関係をもつツリーデータ構造を生成する。ＤＯＭパーサは、このツリーデータ構造をメモリに格納してから要素の処理を開始するので、効率的に処理できるＸＭＬ文書のサイズは、利用可能なメモリ量により制限される。ＸＭＬ文書を構文解析するためのＳＡＸ手法では、パーサは、ＸＭＬ文書を順次トラバースし、タグに基づいて文書の要素を認識しながら、アプリケーションに対する関数呼出を生成する。これらの関数呼出は、メモリ内のＸＭＬ文書全体の表現を格納しなくても、文書をトラバースしながら、要素を処理することができる。従って、（例えば、ＸＭＬツリーの最大深さに基づく）ＳＡＸパーサは、（例えば、ＸＭＬツリー内の全ノード数に基づく）ＤＯＭパーサの場合よりも、メモリ要件より小さくて済むのが普通である。ＳＡＸパーサは特に長い文書では高速化できるが、一方、ＤＯＭパーサは、文書を処理しながら、構造的な関連性の追跡を維持する必要があることに代わり、所定のツリーデータ構造を用いて、より柔軟な処理を実行することができる。
【００４８】
図２に、ＸＭＬ文書等の階層データ構造を処理するための計算グラフ２００の実施例を示す。下記実施例では、説明を簡単にするためにＸＭＬ文書の構造を用いるが、これらの技法は、他の形式の階層データやネストデータに適用することもできる。入力データセット２０２は、ＸＭＬ文書または複数のＸＭＬ文書のストリームを提供する。正規化コンポーネント２０４は、ＸＭＬ文書からデータ要素（例えば、属性、タグ名、および／またはタグ化ＸＭＬ要素のコンテンツ）を抽出し、文書の階層構造の規定レベルからのリンクを介して、所与の出力ポートにデータ要素のフローを提供する。フローには、特定レベルの全データ要素を含めるか、または特定レベルのデータ要素のサブセットを含めることができる（例えば、所与のタグをもつレベルの全要素、および／または所与のタグを伴う親をもつレベルの全要素）。
【００４９】
正規化コンポーネント２０４は、複数の処理モードの内の何れかに従って操作するよう構成することができる。「分離要素処理モード」では、正規化コンポーネント２０４は、詳細に後述するように、所与の出力ポートを介して、どのデータ要素を送るべきかを特定し、階層構造に従って適切な場所に分離要素を挿入する。「合成キー処理モード」では、正規化コンポーネント２０４は、詳細に後述するように、所与の出力ポートを介して、どのデータ要素を送るべきかを特定し、ネスト階層構造内のその位置を示す（例えば、「親」のデータ要素を識別する）合成キー（代理キーとも呼ばれる）をもつ各データ要素を増加させる。合成キーを後で結合操作に用いて、ＸＭＬ文書の元のネスト階層構造の内の幾つか、または全てを再構築することができる。両モードは、メモリに全文書構造のコピーを格納することを必要とすることなく、入力データセット２０２からのＸＭＬ文書を順次処理することにより、ＳＡＸパーサの利点の幾つかを共有する。
【００５０】
分離要素処理モードは、場合によっては、更に幾つかの利点を有する。分離要素処理モードでは、グラフ２００の計算コンポーネント２０６、２０８、２１０がデータ要素を処理する間にデータ要素に対するより効率の高いメモリ格納要件を提供するＸＭＬ文書を再構築するのに、何らかの合成キー値または他の情報をもつデータ要素を増加させる必要はない。また、分離要素は、幾つかのフロー（例えば、ツリーの深さと同じ数のフロー）内にＸＭＬ文書のツリー構造の一部または全てを提供することにより、ＤＯＭパーサの利点の内の幾つかを提供することもできる。
【００５１】
図２に示す実施例では、入力ＸＭＬ文書は、階層構造の三つの異なるレベルと対応するようネストされた三つの異なるタグからなる単純な構造を有する。正規化コンポーネント２０４は、三つの異なるタグの内の一つを有するデータ要素を、三つの計算コンポーネント２０６、２０８、２１０のそれぞれに提供する。三つの計算コンポーネントは、データ要素の属性および／もしくはコンテンツの内の幾つかの変換、タグのリネーム、またはデータ要素の挿入や削除等の受け取ったデータ要素の潜在的な修正を行うことができる。処理されたデータ要素は、非正規化コンポーネント２２０に流れ、出力データセット２２２内に格納のための出力ＸＭＬ文書を構築する。分離要素処理モードでは、それぞれのフロー内のデータ要素間の分離要素の編成を維持しながら、計算コンポーネントがデータ要素を処理できる。非正規化コンポーネント２２０は、分離要素を用いて、元のＸＭＬ文書の階層構造と対応するタグの適切にネスト化された編成内に、処理されたデータ要素を有するＸＭＬ文書を構築することができる。他の実施例では、ＸＭＬ文書の構造を著しく変更すべき場合、例えば、分離要素の編成を変更したり、（分離要素を適切に削除または挿入して）様々なフローのレベルを変更する操作を実行したり、複数のフローを組み合せたり、一つのフローを複数のフローに分割したりできる各種の追加コンポーネントがグラフに含まれてもよい。
【００５２】
図３Ａに、トップレベル（ルートレベル）の「レベル１」、および二つの取りうるタグの内の一つでタグ化された要素を有する下位レベルの「レベル２」をそれぞれ有する一連のＸＭＬ文書を処理するためのグラフ３００の一部を示す。以下の一連の二つのＸＭＬ文書は、入力データセット３０２が提供する文書のストリームの一部の実施例である。
【００５３】
【数３】
0005453273.tif 000004
【００５４】
図３Ｂは、ＸＭＬ文書を分離要素処理モードで処理して、ＸＭＬ文書の階層構造を維持できる適切な分離要素によって分離された文書から、属性値をもつデータ要素のフローを提供するために、正規化コンポーネント３０４が使用する例示的プロシージャ３３０のフローチャートを示す。プロシージャ３３０は、新規ＸＭＬ要素の開始タグを見つけると「抽出」ステップ３３２で開始される再帰的プロシージャとして表されている。このプロシージャ３３０は、見つけたルートのＸＭＬ要素（本実施例では、「レベル１」と関連する「ｔｏｐ」タグを有する）に最初に適用される。コンポーネント３０４は、見つけたＸＭＬ要素の属性および何らかの非タグコンテンツを抽出し（３３２）、対応するフローのデータ要素に適切なフォーマットで一時的に格納する。コンポーネント３０４は、新規開始タグか終了タグである文書内の次の項目を見つける（３３４）。見つけたＸＭＬ要素内に新規開始タグがネストされているのを発見すると、コンポーネント３０４は、プロシージャ３３０を再帰的に適用する。終了タグが見つかった場合、コンポーネント３０４は、所与のレベルと関連するフロー内の、終了タグの所与のレベルと関連する保存されたデータ要素を出力する（３３６）よう進む。コンポーネント３０４は、また、所与のレベル未満のレベル（もしあれば）と関連する他のフローの各々に分離要素を出力する（３３７）。場合によって、分離要素には、終了タグの所与のレベルの指示が含まれ、それにより、様々なレベルの終了タグに基づいて挿入されたフロー内の様々な分離要素を区別することができる。次いで、コンポーネント３０４は、何れかの開始プロシージャが残りの部分を呼び出す場合は再帰呼出を出る（３３８）か、または次の開始ルートタグを見つけるよう進む（３４０）。
【００５５】
図３Ｃに、上記二つのＸＭＬ文書に適用されるプロシージャ３３０の結果を示す。レベル１と関連するフロー３６１は、「ｔｏｐ」タグを有するトップレベルのＸＭＬ要素からの属性値を持つデータ要素を提供する。レベル２と関連するフロー３６２は、「ａ」タグを有するＸＭＬ要素からの属性値を持つデータ要素を提供する。同じくレベル２と関連するフロー３６３は、「ｂ」タグを有するＸＭＬ要素からの属性値を持つデータ要素を提供する。本実施例では、正規化コンポーネント３０４は、トップレベル終了タグ毎にフロー３６２および３６３それぞれにレベル１の分離要素を挿入する。「ａ」および「ｂ」に対する終了タグは最下位レベルフロー（この場合はレベル２）と関連するので、分離要素はこれらの終了タグに対して出力されない。
【００５６】
グラフ３００（図３Ａ）には、どのデータ要素が高位レベルデータ要素のタグ内にネストされたかの指示として分離要素を認識して、ワーク要素のそれぞれのフローを処理するよう構成された計算コンポーネント３０６、３０８、３１０が含まれる。レベル２のフローを処理する計算コンポーネント３０６、３０８は、出力フローをそれぞれの収集コンポーネント３１２、３１４に送る。収集コンポーネント３１２、３１４は、レベル２のフローを処理して分離要素を削除し、対応するデータ要素を収集して、レベル１のフローを提供する。次いで、結合コンポーネント３２０は、三つのフロー全てを処理して、グラフ３００の他の部分での後の処理のために、それらを結合することができる。
【００５７】
図４Ａに、各々がトップ（ルート）レベルの「レベル１」、第二レベルの「レベル２」、および第三レベルの「レベル３」を有する一連のＸＭＬ文書を処理するためのグラフ４００の一部を示す。以下の二連のＸＭＬ文書は、入力データセット４０２が提供するドキュメントのストリームの一部の実施例である。
【００５８】
【数４】
0005453273.tif 000005
【００５９】
図４Ｂに、上記二つのＸＭＬ文書に適用されるプロシージャ３３０の結果を示す。レベル１と関連するフロー４３１は、「ｔｏｐ」タグを有するトップレベルのＸＭＬ要素からの属性値を持つデータ要素を提供する。レベル２と関連するフロー４３２は、「ａ」タグを有するＸＭＬ要素からの属性値を持つデータ要素を提供する。レベル３と関連するフロー４３３は、「ｂ」タグを有するＸＭＬ要素からの属性値を持つデータ要素を提供する。本実施例では、正規化コンポーネント４０４は、トップレベル終了タグ毎にフロー４３２および４３３それぞれにレベル１の分離要素を挿入し、「ａ」終了タグ毎にフロー４３３にレベル２の分離要素を挿入する。「ｂ」に対する終了タグは最下位レベルフロー（この場合はレベル３）と関連するので、分離要素はこれらの終了タグに対して出力されない。
【００６０】
再度図４Ａを参照すると、三つの計算コンポーネント４０６、４０８、４１０は、それぞれフロー４３３、４３２、４３１を処理する。収集コンポーネント４１２は、レベル３のフロー４３１を処理してレベル２の分離要素を削除し、対応するデータ要素を収集してレベル２のフローを提供する。次いで、結合コンポーネント４１４は、得られたレベル２のフローを、計算コンポーネント４０８からのレベル２のフローと一緒に処理して、収集コンポーネント４１６に結合したフローを提供することができる。収集コンポーネント４１６は、レベル１の分離要素を削除し、次いで、結合コンポーネント４２０内で、計算コンポーネント４１０からのレベル１のフローと結合されるレベル１のフローを提供する。
【００６１】
非正規化コンポーネントが使用して、受け取った一つ以上のフローを処理し、ＸＭＬ文書（または、他の階層データ構造）を提供できるプロシージャは、正規化コンポーネントが実行する操作の逆とすることができる。非正規化コンポーネントは、フロー内の分離要素を別のフロー内の対応するデータ要素と一致させて、ＸＭＬ要素をネストさせる方法を特定することができる。例えば、レベルＬの分離要素が一つ以上のデータ要素に続く場合、非正規化コンポーネントは、異なるフロー内の対応するレベルＬのデータ要素を見つけることができ、その一つ以上のデータ要素をレベルＬのデータ要素と対応するＸＭＬ要素内でネストすることができる。
【００６２】
合成キー処理モードも場合によって幾つかの利点を有する。分離要素は合成キー処理モードでは不要である。所与のデータ要素には、所与のデータ要素の内の少なくとも親データ要素を一意に識別する合成キーが含まれる。例えば、データ要素のレコード構造には、合成キーの値を格納する特別なフィールドを含めることができる。階層構造内の関連性を再構築するには、各子データ要素内の親データ要素を識別するだけで十分であるが、合成キーは、オプションとして、階層内の任意の数の祖先を識別することができる。
【００６３】
合成キー処理モードはまた、メモリに全文書構造のコピーを格納することを必要とすることなく、入力データセット２０２からのＸＭＬ文書を順次処理することにより、ＳＡＸパーサの利点の幾つかを提供する。合成キーは、幾つかのフロー（例えば、ツリーの深さと同じ数のフロー）内にＸＭＬ文書のツリー構造の一部または全てを提供することにより、ＤＯＭパーサの利点の内の幾つかを提供することもできる。
【００６４】
合成キーはシーケンシャル値（例えば、数値）とすることができる。実装によっては、各新規データ要素が正規化コンポーネントにより処理されるときに、増加するシーケンシャルインデックス値として、合成キーの値をデータ要素に配置することができる。例えば、正規化コンポーネントは、インデックス値を割り当てるためにグローバルカウンタを維持することができる。階層内の各ノードは一意のインデックス値と関連付けられる。代替として、実装によっては、親ノードを一意に識別するのに全ての合成キーが一意である必要はない。各データ要素のレベルが既知の場合、合成キーの値は、階層の所与のレベルに対して一意とすることができるが、異なるレベルで再び現れてもよい。例えば、カウンタをレベル毎に維持することができ、所与のレベルのデータ要素に、そのレベル用のカウンタを用いて、インデックス値を割り当てることができる。所与のレベルに対してデータ要素が一意のインデックス値をもつ限り、親データ要素は、既知の親レベルおよびインデックス値の組合せにより一意に識別することができる。
【００６５】
ＸＭＬ文書の以下の最初の部分は、合成キー処理モード内で処理されるべき入力データセット４０２が提供する文書の実施例である。この文書は、「ｔｏｐ」タグを持つトップ（ルート）レベル、タグ「Ｈｅａｄ」および「Ｂｏｄｙ」を持つ第二レベル、ならびにそれぞれの親データ要素のタグに依存するタグをもつ第三、第四および第五レベルを有する。
【００６６】
【数５】
0005453273.tif 000006
【００６７】
図４Ｃを参照すると、本実施例では、正規化コンポーネント４０４は、三連の異なるデータ要素をフロー４４１、４４２、４４３に提供する。フロー４４１には「Ｎｏｓｅ」タグを持つデータ要素が含まれる。フロー４４２には「Ａｒｍ」タグを持つデータ要素が含まれる。フロー４４３には、「Ｆｉｎｇｅｒ」タグを持つデータ要素が含まれる。分離要素は本実施例では不要である。各データ要素には、少なくとも同一レベルの他のデータ要素間で一意のインデックス値が割り当てられる。各データ要素には、その親データ要素のインデックス値が含まれているので（親データ要素をもたないルートレベルのデータ要素を除く）、各データ要素が入力データセット４０２からの文書の階層内に属するように、インデックス値を用いて再構築することができる。データフローを受け取る後続のコンポーネントがインデックス値を読み出し、使用して、例えば、フロー間のデータを結合したり参照したりすることもできる。
【００６８】
一実施例では、所与のデータ要素のレコード構造には、データ要素自身に割り当てられたインデックス値のためのフィールド、および親のデータ要素に割り当てられたインデックス値のためのフィールドが含まれる。図４Ｃでは、各データ要素は、自身のインデックス値および親のインデックス値「［ｏｗｎ］／［ｐａｒｅｎｔ］」でラベル付けされている。フロー４４３上のデータ要素には、所与の「Ｎｏｓｅ」データ要素の親の「Ｈｅａｄ」データ要素を一意に識別するインデックス値が含まれる。フロー４４２上のデータ要素には、所与の「Ａｒｍ」データ要素の親の「Ｂｏｄｙ」データ要素を一意に識別するインデックス値が含まれる。フロー４４１上のデータ要素には、所与の「Ｆｉｎｇｅｒ」データ要素の親の「Ｈａｎｄ」データ要素を一意に識別するインデックス値が含まれる。別の実施例では、所与のデータ要素のレコード構造には、そのデータ要素自身に割り当てられたインデックス値のためのフィールド、およびルートレベルまでの祖先のデータ要素に割り当てられるインデックス値のためのフィールドが含まれる。図４Ｄでは、各データ要素は、それ自身のインデックス値およびその祖先のインデックス値「［ｏｗｎ］／［ｐａｒｅｎｔ］／．．．／［ｒｏｏｔ］」でラベル付けされている。図４Ｃおよび図４Ｄの両実施例では、各データ要素の親のインデックスは、全てのフローに同一インデックスを含まなくても、そのデータ要素の階層内の位置を再構築するのに十分である。これにより、階層の幅が広がっても増大しないフロー内の効率的な階層表現が導かれる。図４Ｃの実施例では、各データ要素のためのインデックスフィールドのサイズは階層サイズによらず一定である。図４Ｄの実施例では、各データ要素のためのインデックスフィールドのサイズは階層の深さとともに増大するが、幅に対しては増大しない。
【００６９】
正規化コンポーネント４０４は、フロー上出力される各データ要素内に組み込まれるべき任意の数の子孫データ要素を選択する能力を提供する。場合によっては、所与のノードと関連するデータ（例えば、属性値）だけがデータ要素として出力される。場合によっては、データ要素が文書の元の階層からの子孫ノードの完全または部分的なサブツリーを含めることができるようにする階層構造をデータ要素自体が含む。例えば、上記文書に対して、「Ａｒｍ」タグのレベルと対応するデータ要素は、「Ｈａｎｄ」および「Ｆｉｎｇｅｒ」タグと対応する閉じた子孫ノードの何れかに対するデータを含むこともできる。データ要素自体は階層構造を有するので、子孫ノードから組み込まれたデータに合成キーを割り当てる必要はない。
【００７０】
親または他の祖先ノードを識別するインデックスフィールドに加えて、オプションで親または他の祖先ノードからのデータをデータ要素に含めることができる。例えば、上記文書に対して、「Ｆｉｎｇｅｒ」タグのレベルと対応するデータ要素には、Ｆｉｎｇｅｒの「ｎａｍｅ」属性（例えば、ｎａｍｅ＝”ｐｉｎｋｙ”）だけでなく、Ｈａｎｄの「ｓｔａｔｅ」属性（例えば、ｓｔａｔｅ＝”ｆｉｓｔ”）およびＡｒｍの「ｓｉｄｅ」属性（例えば、ｓｉｄｅ＝”ｒｉｇｈｔ”）を含めることができる。場合によっては、祖先ノードからの情報を含めると、特定の結合操作を実行する必要をなくすことができる。
【００７１】
図４Ｅに、合成キー処理モードでＸＭＬ文書を処理して、文書からの属性値、およびＸＭＬ文書の階層構造の保存を可能にする適切な合成キーを有するデータ要素のフローを提供するために、正規化コンポーネント４０４が使用する例示的プロシージャ４５０のフローチャートを示す。プロシージャ４５０は、新規のＸＭＬ要素の開始タグを見つける度に「抽出」ステップ４５２で開始する再帰的プロシージャとして表されている。プロシージャ４５０は見つけたルートのＸＭＬ要素（本実施例では、「レベル１」と関連する「ｔｏｐ」タグを有する）に最初に適用される。コンポーネント４０４は見つけたＸＭＬ要素の属性および何らかの非タグコンテンツを抽出し（４５２）、対応するフローのデータ要素に適切なフォーマットで一時的に格納する。コンポーネント４０４は、文書内で次の項目（新規の開始タグや終了タグであってもよい）を探す（４５４）。見つかったＸＭＬ要素内で新規の開始タグがネストされているのが発見された場合、コンポーネント４５４はプロシージャ４５０を再帰的に適用する。終了タグが発見された場合、コンポーネント４０４は、終了タグの所与のレベルと関連する保存されたデータ要素を、その所与のレベルと関連するフロー内に出力する（４５６）よう進む。コンポーネント４０４は、親データ要素（もしあれば）を識別するデータ要素内にインデックス値も書き込む（４５７）。次いで、コンポーネント４０４は、何れかの開始プロシージャ呼出が残っている場合は再帰呼出を出る（４５８）か、または次の開始ルートタグを見つけるよう進む（４６０）。
【００７２】
非正規化コンポーネントが使用して、受け取った一つ以上のフローを処理し、ＸＭＬ文書（または、他の階層データ構造）を提供できるプロシージャは、正規化コンポーネントが実行する操作の逆とすることができる。非正規化コンポーネントは、フロー内の合成キー値を別のフロー内の対応する合成キー値と突合して、ＸＭＬ要素をネストさせる方法を特定することができる。
【００７３】
本明細書で説明したデータフロー管理手法は、コンピュータ上で実行するためのソフトウエアを用いて実装することができる。例えば、本ソフトウエアは、プログラムされるか、またはプログラム可能な一つ以上のコンピューターシステム（分散型、クライアント／サーバ型、またはグリッド型等の各種アーキテクチャで構成されてもよい）上で実行される一つ以上のコンピュータープログラム内のプロシージャを形成し、そのコンピューターシステムはそれぞれ、少なくとも一つのプロセッサと、少なくとも一つのデータ格納システム（揮発性または不揮発性メモリおよび／またはストレージ素子を含む）と、少なくとも一つの入力装置またはポートと、少なくとも一つの出力装置またはポートとを備える。本ソフトウエアは、例えば、計算グラフの設計および構成に関連する他のサービスを提供する大規模プログラムの一つ以上のモジュールを形成してもよい。グラフのノードおよび要素は、コンピュータで読取り可能な媒体内に格納されたデータ構造、またはデータリポジトリ内に格納されたデータモデルに準拠する他の組織化されたデータとして実装することができる。
【００７４】
本ソフトウエアは、汎用または専用のプログラム可能コンピュータで読取り可能なＣＤ−ＲＯＭ等の格納媒体上で提供するか、または本ソフトウエアを実行するコンピュータにネットワーク等の通信媒体を介して配布（伝搬信号で符号化）してもよい。全ての機能は、専用コンピュータ、またはコプロセッサ等の専用ハードウエアを用いて実行してもよい。本ソフトウエアは、ソフトウエアが規定する異なる計算部分を異なるコンピュータで実行する分散型で実装してもよい。かかるコンピュータープログラムはそれぞれ、汎用または専用のプログラム可能コンピュータが読み取り可能な格納媒体または格納装置（例えば、固体メモリもしくは媒体、または磁気式もしくは光学式媒体）に格納するか、ダウンロードして、コンピューターシステムが格納媒体または格納装置を読み取って本明細書で説明したプロシージャを実行する際に、コンピュータを構成し、操作するのが好ましい。本発明のシステムは、コンピュータープログラムにより構成されるコンピュータで読み取り可能な格納媒体として実装されると考えてもよく、そのように構成された格納媒体により、コンピューターシステムを特定、かつ所定の方法で操作して、本明細書で説明した機能を実行してもよい。
【００７５】
本発明の幾つかの実施の態様を説明してきた。にもかかわらず、本発明の精神および範囲から逸脱することなく、各種の改変をなすことができるのは言うまでもない。例えば、上記ステップの幾つかは順序とは無関係なので、上記説明と異なる順序で実行してもよい。
【００７６】
言うまでもなく、上記説明は説明を目的としているだけであって、本発明の範囲を制限するものではなく、その範囲は添付の請求の範囲により定義される。例えば、上記の幾つかの機能ステップは、全体の処理に実質的に影響を与えずに、異なる順序で実行してもよい。他の実施の態様は以下のクレームの範囲内にある。
【００７７】
（関連出願のクロスリファレンス）
本願は、２００７年９月２０日出願の米国特許出願第６０／９７３，９７９号の優先権を主張する。
【図１Ａ】
0005453273.tif 000007
【図１Ｂ】
0005453273.tif 000008
【図１Ｃ】
0005453273.tif 000009
【図２】
0005453273.tif 000010
【図３Ａ】
0005453273.tif 000011
【図３Ｂ】
0005453273.tif 000012
【図３Ｃ】
0005453273.tif 000013
【図４Ａ】
0005453273.tif 000014
【図４Ｂ】
0005453273.tif 000015
【図４Ｃ】
0005453273.tif 000016
【図４Ｄ】
0005453273.tif 000017
【図４Ｅ】
0005453273.tif 000018