(57)【要約】  グラフ型計算におけるパラメータの順序付け方法であって、計算グラフのグラフ要素に関係付けられるパラメーターセットの所望する第１順序を決定するステップ（２６０２）と；パラメーターセットに対する順序制約を決定するステップ（２６０４）と；所望する第１順序に基づいて順序制約を満たすパラメーターセットの第２順序を決定するステップ（２６０４）とを含む方法である。
2008547134.tif 000002
【特許請求の範囲】
【請求項１】
グラフ型計算におけるパラメータを順序付けるための方法であって：
計算グラフのグラフ要素に関係付けられるパラメーターセットの所望する第１順序を決定するステップ（２６０２）と；
前記パラメーターセットに対する順序制約を決定するステップ（２６０４）と；
前記所望する第１順序に基づいて前記順序制約を満たす前記パラメーターセットの第２順序を決定するステップ（２６０６）とを含む方法。
【請求項２】
前記計算グラフの仕様を受け入れるステップを更に含み、前記所望の第１順序付けが、前記仕様に現れる前記グラフ要素の順序に基づく、
請求項１の方法。
【請求項３】
前記グラフは前記順序制約を課されている、
請求項１の方法。
【請求項４】
前記第２順序に基づいて前記パラメータの値を決定するステップを更に含む、
請求項１の方法。
【請求項５】
前記パラメータの値を決定するステップは、ユーザ入力を促すステップを含む、
請求項４の方法。
【請求項６】
前記促されたユーザの応答に基づいて、前記パラメータの内の第１パラメータの値を決定するステップと；
前記第１パラメータの値として決定された前記パラメータ値を用いて前記グラフを実行するステップとを更に含む、
請求項５の方法。
【請求項７】
前記順序制約を決定するステップは、前記パラメータ値間の従属関係を決定するステップを含む、
請求項１の方法。
【請求項８】
前記順序制約は、第１パラメータが第２パラメータに従属している場合、前記第１パラメータを前記第２パラメータの後へ順序付けるステップを含む、
請求項７の方法。
【請求項９】
前記順序制約は、一つ以上の有向非循環グラフに対応し、前記一つ以上の有向非循環グラフの各頂点は、前記セット内のパラメータに対応する、
請求項１の方法。
【請求項１０】
前記第２順序を決定するステップは、前記順序制約に基づいて前記セット内の前記パラメータのトポロジカルソートを実行するステップを含む、
請求項１の方法。
【請求項１１】
前記所望する第１順序に基づいて前記順序制約を満たすステップは、前記順序制約を満たすために再順序付けをする必要がない少なくとも幾つかのパラメータに対して、前記第１順序との類似性を保つステップを含む、
請求項１の方法。
【請求項１２】
グラフ型計算におけるパラメータを順序付けるためのコンピュータ読取り可能な媒体上に格納されるソフトウエアであって、コンピューターシステムに：
計算グラフのグラフ要素に関係付けられるパラメーターセットの所望する第１順序を決定するステップ（２６０２）と；
前記パラメーターセットに対する順序制約を決定するステップ（２６０４）と；
前記所望する第１順序に基づいて前記順序制約を満たす前記パラメーターセットの第２順序を決定するステップ（２６０６）とを実行させるための命令を含むソフトウエア。
【請求項１３】
グラフ型計算におけるパラメータを順序付けるためのシステムであって：
計算グラフのグラフ要素に関係付けられるパラメーターセットの所望する第１順序を決定するための手段（２６０２）と；
前記パラメーターセットに対する順序制約を決定するための手段（２６０４）と；
前記所望する第１順序に基づいて前記順序制約を満たす前記パラメーターセットの第２順序を決定するための手段（２６０６）とを含むシステム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
技術の分野
本発明は、データ処理システムにおける計算の制御に関し、より詳細には、グラフ型計算のためのパラメータ管理に関する。
【０００２】
背景
複雑なビジネスシステムは、一つの段階で生成した結果を次の段階へ送ることにより多段階でデータを処理するのが普通である。このようなシステムを通る情報の全体的な流れは、成分（データファイルまたはプロセスのいずれでもよい）を表すグラフの頂点、および成分間の流れを示すグラフのリンクまたは「辺」を有する有向データフローグラフを用いて記述することができる。
【０００３】
それと同じ形式のグラフ表現を用いて、並列処理システムを記述することができる。説明にすぎないが、この並列処理システムは、多数の中央処理ユニット（ＣＰＵ）を用いるコンピューターシステムの何らかの構成を含み、ローカル（例えば、ＳＭＰコンピュータのようなマルチプロセッサシステム）、もしくはローカル分散型（例えば、クラスタまたはＭＰＰとして結合されたマルチプロセッサ）、またはリモートもしくはリモート分散型（例えば、ＬＡＮまたはＷＡＮネットワークを介して結合されるマルチプロセッサ）、またはこれらの任意の組み合わせのいずれでもよい。繰り返しになるが、グラフは成分（データファイルまたはプロセス）およびフロー（グラフの辺またはリンク）から成る。明示的または黙示的にグラフ要素（成分およびフロー）を複製することにより、システム内の並列処理を表すことができる。
【０００４】
グラフを用いて、計算を直接起動させることができる。マサチュセッツ州レキシントンのＡｂ  Ｉｎｉｔｉｏ  Ｓｏｆｔｗａｒｅ  Ｃｏｒｐｏｒａｔｉｏｎが提供するグラフ開発環境（ＧＤＥ）による「ＣＯ＞ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ（登録商標）」は、このようなシステムを具体化している。このシステムにより作成されるグラフは、グラフ成分により表される個々のプロセスの入出力情報を取得して、プロセス間で情報を移動させ、そしてプロセスの実行順序を定義するための方法を提供する。このシステムは、プロセス間の通信方法を選択するアルゴリズムとプロセス実行のスケジュールを組むアルゴリズムとを含み、グラフ実行の監視も提供する。
【０００５】
開発者は、「ランタイム」時（すなわち、グラフを実行する時）にグラフコンパイラにより実行可能命令へ変換される命令（例えば、シェルスクリプト）の生成が可能な、環境変数またはコマンドライン引数の使用を介して、何らかの形で制御されるグラフを作製することが非常に多い。従って、環境変数およびコマンドライン引数は、ファイル名、データ選択式、およびキー（例えば、ソートキー）のような情報を規定するためのその場限り（アドホック）のパラメータとなるので、アプリケーションは更にフレキシブルになる。しかし、ユーザは生成されたシェルスクリプトを読み出し、環境変数およびコマンドライン引数を参照するためにそれを検索して、特定グラフの実行を制御するパラメーターセットを見つけなければならない。
【０００６】
概要
一般的な態様では、本発明は、グラフ型計算におけるパラメータを順序付けるための方法、ならびに対応するソフトウエアおよびシステムを特徴とする。本方法は、計算グラフのグラフ要素に関係付けられるパラメーターセットの所望する第１順序を決定するステップと；パラメーターセットに対する順序制約を決定するステップと；所望する第１順序に基づいて順序制約を満たすパラメーターセットの第２順序を決定するステップとを含む。
【０００７】
本態様には下記特徴の内の一つ以上を含むことができる。すなわち：
本方法は、計算グラフの仕様を受け入れるステップを更に含み、所望の第１順序付けが、その仕様に現れるグラフ要素の順序に基づく。
グラフは順序制約を課されている。
本方法は、第２順序に基づいてパラメータの値を決定するステップを更に含む。
パラメータの値を決定するステップは、ユーザ入力を促すステップを含む。
本方法は、促されたユーザの応答に基づいて、パラメータの内の第１パラメータの値を決定するステップと；第１パラメータの値として決定されたパラメータ値を用いてグラフを実行するステップとを更に含む。
順序制約を決定するステップは、パラメータ値間の従属関係を決定するステップを含む。
順序制約は、第１パラメータが第２パラメータに従属している場合、第１パラメータを第２パラメータの後へ順序付けるステップを含む。
順序制約は、一つ以上の有向非循環グラフに対応し、一つ以上の有向非循環グラフの各頂点は、セット内のパラメータに対応する。
第２順序を決定するステップは、順序制約に基づいてセット内のパラメータのトポロジカルソートを実行するステップを含む。
所望する第１順序に基づいて順序制約を満たすステップは、順序制約を満たすために再順序付けをする必要がない少なくとも幾つかのパラメータに対して、第１順序との類似性を保つステップを含む。
【０００８】
本発明の各態様は下記の利点の内の一つ以上を含むことができる：
ランタイムパラメータに関するグラフインターフェースは、入力フォーム化されている。グラフインターフェースは、どのパラメータを供給する必要があるか、およびそれらパラメータをどのように指示すべきかを知ることができるように、システムにとって十分に良く定義されている。
成分を制御するメタデータは、ランタイムパラメータにより、直接的または間接的に規定または計算することができる。
グラフ構造は、成分の有無をユーザが選択できるように、条件付き成分を制御するランタイムパラメータの値に基づいて修正することができる。
グラフのランタイムパラメータ化の利点は、ビジネスアナリストおよび統計モデラーのようなエンドユーザが、彼らの必要に見合うデータをリクエストできるように十分充実した、アプリケーションのパラメータ化ができることである。近年の企業のデータ環境の複雑さは、データ収集および事前解析変換の処理に、膨大な量の直接的な人の関与を日常的に必要とする状況をもたらしている。本発明は、専門のデータアナライザがいなくても、それぞれのクエリー形式に対するクリティカルパスに、エンドユーザが望むデータを定義し、検索できる強力なツールを提供する。
【０００９】
グラフ内を伝搬させられるメタデータは、他のメタデータの関数として定義されるメタデータのような、関数的に変換されるメタデータを含むことができる。例えば、伝搬はグラフ実行の前の編集時に行うことがある。変換されるメタデータの伝搬を可能にすることにより、グラフを実行する前であってもメタデータを見たりおよび／または操作するユーザ能力が強化される。
【００１０】
ランタイムパラメータを伴う再利用可能な（相互接続可能な）成分のライブラリがあってもよい。グラフは、グラフ内のランタイムパラメータ全てに対して自動的に決定される実行指示順序により、これらの成分から作成できる。場合によっては、パラメータを再順序化して、ある種の制約を満たす必要がある。所望の順序（例えば、開発者が規定する順序）に基づいて、これらの制約を満たすようにパラメータを再順序化すると、所望の順序から著しく外れた順序でパラメータをユーザに催促する可能性が減少する。
【００１１】
本発明の他の特徴および利点は、以下の説明およびクレームから明らかになる。
【００１２】
詳細な説明
概観
図１Ａは、主要素の相互関係を示す本発明の一実施の形態のブロック図である。グラフ開発環境（ＧＤＥ）１０２は、実行可能なグラフを創成し、グラフ成分に対するパラメータを定義するためのユーザーインターフェースを提供する。ＧＤＥは、例えば、本発明の譲受人から入手可能なＣＯ＞ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ（登録商標）のＧＤＥとすることができる。ＧＤＥ１０２は、収納庫１０４および並列オペレーティングシステム１０６と通信する。収納庫１０４および並列オペレーティングシステム１０６は、ウェブインターフェース１０８および実行部１１０にも結合されている。
【００１３】
収納庫１０４は、グラフ型アプリケーションの開発および実行、ならびにグラフ型アプリケーションと他のシステム（例えば、他のオペレーティングシステム）との間のメタデータ相互交換をサポートするよう設計された拡張可能オブジェクト指向データベースシステムであることが好ましい。収納庫１０４は、あらゆる種類のメタデータに対する格納システムであり、（限定はしないが）文書化、レコードフォーマット、変換関数、グラフ、ジョブ、および監視情報を含む。収納庫は、当該技術分野では周知である。例えば、米国特許第５，９３０，７９４号、第６，０３２，１５８号、および第６，０４４，３７４号を参照。
【００１４】
並列オペレーティングシステム１０６は、ＧＤＥ１０２で生成されたデータフローグラフ表現を受け入れ、処理ロジックと、グラフが定義するリソースとに対応するコンピュータ命令を生成する。並列オペレーティングシステム１０６は、次いで、複数のプロセッサ（同質でなくてもよい）上でこれらの命令を実行するのが典型的である。適切な並列オペレーティングシステムは、本発明の譲受人から入手可能なＣＯ＞ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ（登録商標）である。
【００１５】
ウェブインターフェース１０８は、収納庫１０４の内容のウェブブラウザ型ビューを提供する。ウェブインターフェース１０８を用いて、ユーザは、オブジェクトを閲覧し、新規オブジェクトを創成し、既存のオブジェクトを変更し、アプリケーションパラメータを規定し、ジョブをスケジュール化する等が可能である。ウェブインターフェース１０８は、グラフのランタイムパラメータについての収納庫１０４内の格納情報に基づいてパラメータ化したグラフに対する、入力フォーム型ユーザーインターフェースを自動的に創成する。
【００１６】
実行部１１０は、ウェブインターフェース１０８を介してアクセスされるオプションの収納庫型ジョブスケジュールシステムである。実行部１１０は、収納庫１０４内にジョブと、オブジェクトとしてのジョブ待ち行列とを維持し、ウェブインターフェース１０８は、ジョブとジョブ待ち行列のビューを提供し、その操作を容易にする。
【００１７】
図１Ｂは、フィルタ成分１２６へフロー１２４により接続される入力データセット１２２を有する単純なデータフローグラフ１２０を示す。フィルタ成分１２６は、フロー１２８により出力データセット１３０へ接続される。データセットは、例えば、データフローグラフが実行する計算のための、データ（例えば、入力データセット）を提供するか、またはデータ（例えば、出力データセット）を受け取るファイルまたはデータベーステーブルを含むことができる。
【００１８】
データフローグラフ内の「フロー（流れ）」により表されるデータフローは、離散的なデータ要素へ組織化することができる。例えば、要素は、レコード（または行）およびフィールド（または列）内に組織化されるデータセットからのレコードを含むことができる。レコード内の値に対応するフィールドおよびデータ形式のシーケンスを記述するメタデータは、「レコードフォーマット」と呼ばれる。
【００１９】
グラフ内の成分およびデータセットは、フローへ接続するための入力および／または出力ポートを有する。フロー１２４およびフロー１２８の「ソースエンド」は、入力データセット１２２の出力ポートおよびフィルタ成分１２６の出力ポートに、それぞれインターフェース（接続）する。フロー１２４およびフロー１２８の「シンクエンド」は、フィルタ成分１２６の入力ポートおよび出力データセット１３０の入力ポートに、それぞれインターフェース（接続）する。データセットまたは成分の入力または出力ポートは、ポートに流れ込むデータまたはポートから流れ出るデータに対するレコードフォーマットのような、メタデータに関係付けられる。
【００２０】
ポートに対するレコードフォーマット、または成分に関係付けられる他のメタデータを含む、パラメータは、パラメータースコープの規則に基づいて値へバインドされる。パラメータは、設計時または実行時に（すなわち、後述する「ランタイムパラメータ」）値へバインドすることができる。パラメータの値は、例えば、ユーザーインターフェース上で（例えば、プロンプトに応答して）、ユーザが定義するか、ファイルから定義するか、または同一コンテクストもしくは異なるコンテクスト内の別のパラメータに関して定義することができる。例えば、パラメータは、パラメータを別のパラメータに対して「同一」の関連性を有するように指定することにより、異なるコンテクストからエクスポートする（例えば、異なる成分のコンテクストで評価されるパラメータを）ことも可能である。
【００２１】
グラフ内で用いる成分は、「サブグラフ」を形成するフローと相互接続される他の成分を用いて実装できる。サブグラフを別のグラフの成分として用いる前に、成分の入力および／または出力ポートのような、成分の様々な特性を定義する。場合によっては、サブグラフ成分間の関連性と協調させなければならない成分の特性は、グラフ内でその成分を用いる前に規定するのがよい。例えば、サブグラフ成分のランタイムパラメータに対して実行を促す順序を選択する必要がある。グラフ内の成分のランタイムパラメータに対する実行を促す順序を選択するための手法について、以下に詳細に説明する。
【００２２】
メタデータ伝搬
レコードフォーマットパラメータのような、ポートに関係付けられるメタデータの値は、「伝搬」により取得することができる。メタデータ伝搬は、「外部から」または「内部で」発生させることができる。外部メタデータ伝搬に関しては、第１成分のポートに対するレコードフォーマットパラメータの値は、フローにより第１成分へ接続される第２成分のポートに対するレコードフォーマットの値を伝搬させることにより、値を取得できる。その値は、フローのソースエンドからシンクエンドへの下流方向、またはフローのシンクエンドからソースエンドへの上流方向の何れに伝搬させることもできる。メタデータは、メタデータを定義済みのポートから、メタデータを未定義のポートへ伝搬させる。
【００２３】
内部メタデータ伝搬に関しては、成分の一ポートに対して定義したメタデータを、その成分を実装するサブグラフに基づいてその成分の別のポートへ伝搬させる。場合によっては、内部メタデータ伝搬が「非変換」内部データパス上で発生する。例えば、ユーザは、ソート成分へ流れ込むレコードのデータ形式を規定するソート成分入力ポートに対してメタデータを提供してもよい。ソート成分は順序を付け直すもののレコードを変換しないので、データ形式はソート成分により変更されず、データ形式は、ソート成分から流れ出るレコードのデータ形式を正確に記述するソート成分の出力ポートへ、変更されずに伝搬される。
【００２４】
しかし、成分によっては、その成分を通って流れるデータを変換する（またはオプションで変換する）。例えば、フィルタ成分へ流れ込むレコードのフィールドを規定するフィルタ成分入力ポートに、ユーザはメタデータを提供できる。フィルタ成分は、各レコードから与えられるフィールドの値を削除できる。メタデータ定義を用いて、フィルタ成分の出力ポートに対するメタデータが、その成分のフィルタ作用に基づいて、入力ポートのメタデータに関連付けられるように規定することができる。例えば、レコードフィールドを規定するメタデータから、フィルタ処理されたフィールドを削除できる。既に入力ポートメタデータが既知であっても、このようなメタデータ定義を提供できる。従って、ポートに関係付けたメタデータを、詳細に後述するように別のポートに対するメタデータを含むが、一つ以上のパラメータの関数として規定することにより、メタデータを内部データパス変換を超えてでも伝搬させることができる。
【００２５】
設計時にグラフを構築しているときに、ユーザがグラフ内の幾つかの成分の幾つかのポートに対するメタデータを提供しながら、内部および外部のメタデータ伝搬を発生させるようオプションで構成することができる。代替として、ランタイム時、またはランタイム直前を含め、グラフの構築後に、メタデータ伝搬を発生させることもできる。
【００２６】
ランタイムパラメータ
ランタイムパラメータは、アプリケーション構築者がパラメータ設定（例えば、ソート関数のキーパラメータ、ファイル名称、レコードフォーマット、変換関数等）の値をランタイム時（例えば、コンピューターシステム上でプログラムを実行する時またはその直前）まで延期することができる。ランタイムパラメータの値は、エンドユーザが提供するか、または他のランタイムパラメータもしくはオブジェクト収納庫に格納されたオブジェクトの組み合わせから導くことができる。
【００２７】
ランタイムパラメータは、アプリケーションへ一定量のフレキシビリティを与える。付加されるフレキシビリティは、これらのパラメータを用いて、オンデマンドでメタデータ（データフォーマットつまりtypes（形式）、およびプログラムロジックつまりtransform（変換））を計算することにより達成される。形式および変換は、他の形式および変換、ユーザ提供のパラメータ値、および格納された（例えば、収納庫からの）オブジェクトと同期させることができる。これにより、任意の形式の入力データで機能するとともに、ランタイムパラメータ値を通じて直接または間接的にその構造が制御される一連の変換を介して、データを生成する「標準の」アプリケーションを構築できるようになる。
【００２８】
実施によっては、ランタイムパラメータを創成しまたは編集する場合、開発者は、各パラメータに対してプロンプトおよびそのプロンプトを表示する条件を規定できる。このシステムは、提示するプロンプト指令を解釈して、条件が適合すると、パラメータ値を受け取るためのグラフィカルユーザーインターフェース（ＧＵＩ）制御を提示する。
【００２９】
ランタイムパラメータ指定
ランタイムパラメータは、開発者がグラフ実行時（すなわち、ランタイム時）に外部入力に基づいてグラフの振る舞いを修正するメカニズムを提供する。好適な実施の形態では、これらの外部の値はユーザの直接入力により提供される。しかし、これら外部の値は、環境変数およびコマンドラインパラメータを含む幾つかの異なるソースからもたらされてもよい。ＧＤＥ１０２は、これらの状況全てを扱うための正しいコードを生成し、グラフをＧＤＥから直接実行する場合にテスト値を開発者に催促する。ランタイムパラメータを用いて、開発者は、例えば、入力ファイルのパスが特定名称を有する環境変数により提供されること；次いで、その環境変数がグラフインターフェースの既知の一部となること；を明示的に宣言できる。従って、このようなパラメータに対して明確に定義されるインターフェースが存在する。例えば、生成されたシェルスクリプトを読み出し、環境変数およびコマンドライン引数を参照するためにそれを検索して、特定グラフの実行を制御する一セットのパラメータを見つけなくてもよい。
【００３０】
図２は、指定されたランタイムパラメータを有するロールアップ成分２０２およびソート成分２０４を有する代表的なグラフ２００のブロック図である。ランタイムパラメータ（ソート成分２０４用のキーおよびロールアップ成分２０２用の規則）は、入力用インターフェース２０６でユーザへ提示される。以下では、ランタイムパラメータの指定方法、およびユーザ入力を促すランタイムパラメータ提示用の統合ユーザーインターフェースの創成方法を説明する。
【００３１】
ランタイムパラメータを幾つかの方法で指定または定義することができる。その一方法は、ＧＤＥ１０２で表示されるランタイムパラメーターグリッドを使用する方法である。図３は、グラフに関係するランタイムパラメーターグリッド３００を表すグラフダイアログの一実施の形態の図である。新規ランタイムパラメータは適切なフィールド内へ単に記入するだけで創成される。それぞれのランタイムパラメータに関係付けられるオブジェクトは、収納庫１０４内に創成され、そのパラメータを利用する全てのグラフ成分へリンクされる。例えば、グラフソート成分のためのソートキーがランタイムパラメータとして定義される場合、ソートキーパラメータを表すオブジェクトは収納庫１０４内に格納され、関係するソート成分へリンクされる。ランタイムパラメータ定義の代替方法は、グラフ成分の既存パラメータに特別にフラグを立てて、他の成分に対してそれが「見える」（それをエクスポートする）ようにすることである。これら方法の組み合わせを用いてもよい。例えば、成分を創成する場合、開発者は、その成分の特定パラメータをランタイムパラメータとして指定できる。開発者は、次いで、パラメーターグリッドを用いて、グラフに対するランタイムパラメータ全ての既定値および他の特性を設定でき、新規ランタイムパラメータを定義できる。
【００３２】
グラフを実行すると、ユーザ入力または外部のプログラム的ソース（例えば、コマンドラインパラメータまたは環境変数）からの、各パラメータに対する値を取得するようパラメータが処理される。図示の実施の形態では、ランタイムパラメーターグリッド３００は下記フィールドを含む：
Name（名称）３０２  −  このフィールドはランタイムパラメータの名称を含む。「Score_threshold」は名称例である。
Type（形式）３０４  −  このフィールドはランタイムパラメータに許容される値の形式を含む。「Integer（整数）」は形式例である。図示の実施の形態におけるサポートされる形式は：
・ブール代数  −  値は真または偽の何れかとすることができる；
・選択  −  値は、値リストの内の一つである；
・照合者  −  キーパラメータ値；
・データセット  −  外部データファイル名称および場所；
・日付  −  日付けの値；
・式  −  算術、論理、および／または条件式（例えば、選択式）；
・浮動小数点  −  浮動小数点の値；
・整数  −  整数値；
・レイアウト  −  並列または直列のレイアウト定義；
・レコードフォーマット  −  レコード記述またはレコード記述を含むファイル；
・文字列  −  任意の文字列；
・変換  −  変換記述または変換記述を含むファイル；
Location（Loc）（場所）３０６  −  このフィールドはレコードフォーマットおよび変換形式により用いられる。形式フィールド３０４が、ファイル場所を記述するか、または組み込まれた記述を含むかどうかを規定する。サポートされる場所は：
・埋込型  −  パラメータはレコードまたは変換記述を含む；
・ホスト  −  パラメータはホストマシン上のファイル参照を含む；
・ローカル  −  パラメータはローカルマシン上のファイル参照を含む；
・収納庫  −  パラメータは収納庫変換またはレコードフォーマット参照を含む；
Default Value（既定値）３０８  −  このフィールドは、（１）他の値が外部プログラム的ソースから提供されない場合に用いられるランタイムパラメータの既定値、または（２）ユーザ入力からランタイム値を導く方法もしくはグラフを実行するユーザからの相互作用による情報を取得する方法、を記述する規則もしくは式の何れかを含む。後者の場合、ユーザが入力値を提供しない場合、第２既定値のフィールド（不図示）を用いて、ランタイムパラメータの値を提供することができる。「ブール代数」および「選択」の形式では、フィールドはユーザに正当な選択しかさせない。「レイアウト」形式では、フィールドは読み出しのみで、現在定義されているレイアウト定義を表示する。その他全ての形式では、フィールドは、ユーザが正当な文字列をタイプ入力する単純なテキストエディタとするのが好ましい。
Edit（編集）３１０  −  パラメータ行の編集スペース３１０（または、アイコン、例えば、鉛筆アイコン）をクリックすると、より進化した編集ウィンドウが現れ、ユーザは既定値のフィールド３０８を編集するための様々なオプションを選択して回る。図示の実施の形態では、関係付けられる形式に対して下記のエディタを利用できる：
・単行エディタ  −  整数、浮動小数点、日付および文字列形式；
・選択ダイアログ  −  ブール代数および選択形式；
・キーエディタ  −  照合者形式；
・ファイルブラウザ  −  データセット形式用、レコードフォーマット用、および場所が埋込型でない場合の変換形式用；
・変換エディタ  −  埋込型の場所を有する変換形式用；
・レコードフォーマットエディタ  −  埋込型の場所を有するレコードフォーマット形式用；
・式エディタ  −  式形式用；
・レイアウトエディタ  −  レイアウト形式用；
上記エディタは、種類フィールド値（下記参照）が「ＰＬ」（パラメータ言語の）でなければ起動される。この場合、ユーザは、グラフ実行時にパラメータ値を導き出す、または促すための規則を定義するためのエディタを提示される。
Description（記述）３１２  −  これは、開発者がランタイムパラメータの予測値を記述する自由フォーマットのフィールドである。既定値がユーザに入力値を要請するための規則を含む場合、ランタイム時のプロンプトとして用いられる。
Kind（種類）３１４  −  このフィールドは、グラフ実行時に、関係するパラメータの値を取得することになる場所を定義する。サポートされる種類のフィールド３１４の値は：
・環境（Environment）  −  ランタイムパラメータの値が、同一名称の環境変数内に見いだせると予測される。環境変数が定義されていない場合、値は既定値フィールド３０８内の値が用いられる。パラメータが要求される場合（すなわち、エクスポートされるパラメータ）、および既定値フィールド３０８が空の場合、ランタイムエラーが生成され、グラフ実行は停止される；
・位置的（Positional）  −  ランタイムパラメータの値が、アプリケーションを呼び出すコマンドライン上の相対的位置で予測される。例えば、ランタイムパラメータが、定義された第３位置のランタイムパラメータの場合、そのパラメータ値は、実行スクリプト内の第３位置のコマンドライン引数と予測される。規定された位置パラメータはどれも提供されねばならず、一つでも欠けるとランタイムエラーを生ずる。
・キーワード（Keyword）  −  ランタイムパラメータの値がキーワードコマンドラインパラメータと予測される。図示の実施の形態では、キーワードパラメータは次の形をとる：
-<parameter name><parameter value>
キーワードパラメータはオプションであり、ランタイムエラーが生じるのは、キーワードパラメータが提供されない場合、既定値のフィールド３０８が空白の場合、および対応するエクスポートパラメータが要求される場合に限られる。
・固定（Fixed）  −  パラメータのランタイム値は常に既定値である。これは二つ以上のランタイムパラメータ間で定数値を共有するのに有用である。
・ＰＬ  −  ランタイムパラメータの既定値は、グラフ実行時に、他のパラメータからランタイムパラメータの値を導き出すよう解釈されるか、または追加入力をユーザに促すよう解釈されるＰＬ式を含む。本発明のどれか特定の実施の形態で用いるために選択される成分記述言語は、広く利用できるオブジェクト指向スクリプト言語「Ｐｙｔｈｏｎ」のような任意の適切なスクリプト言語であってよい。このようなスクリプトは、プログラム制御のもとでメタデータ（形式および変換）を構築し、条件付きテスト、比較、データ変換、算術演算および論理演算、文字列およびリスト操作、ならびにユーザ入力に関する他の機能、外部のプログラムで供給される入力、ならびに他のランタイムパラメータを実行し、どのランタイムパラメータにも最終的な値を生成できる。
【００３３】
図示の実施の形態では、ランタイムパラメーターグリッド３００上で直接創成されているランタイムパラメータを参照するための有用な取り決めは、ドル符号「＄」を先頭に付したパラメータ名称を入力するだけでよい。例えば、$keyは、keyと名称を付けたランタイム変数を参照する。図示の実施の形態では、新規ランタイムパラメータは、「文字列」形式を既定値とし、先進のオプションダイアログに基づく既定の種類は、既定値のランタイム種類（既定値のランタイム種類は「環境」）とする。
【００３４】
ランタイムパラメータ値はランタイムに決定でき、ＰＬスクリプトは条件付きテストを提供できるので、「条件付き」ランタイムパラメータを創成できる。条件付きランタイムパラメータは、ランタイムに決定されるパラメータに対する条件全てを有効化している場合に限り、ユーザ入力のためのプロンプトを生成させる。従って、例えば、データセットを「ＮＯ」でソートすべきかどうかを要求する第１プロンプトへユーザが応答する場合、ソートキーを要求する第２の条件付きプロンプトを表示する必要はない。
【００３５】
従って、設計段階（「設計時間」）の間に、開発者はグラフ成分の特定パラメータを「ランタイム」パラメータとして指定する。そのグラフ成分に関係付けられるオブジェクトは、次に、関連するパラメーターデータ（例えば、図３のパラメーターグリッド３００からの情報の形式）とともに格納される。
【００３６】
図４は、ランタイムパラメータを用いるプロセスを要約したフローチャートである。ランタイム中に、実行対象のアプリケーションに対応するパラメーターオブジェクトが（例えば、収納庫から）取り出される（ステップ４００）。ユーザ入力が指示されるかどうかについて、それらオブジェクト毎に判定される（ステップ４０２）。Ｙｅｓの場合、プロンプト表示の何らかの条件が満たされているかどうかについて判定され（ステップ４０３）、それには以前のプロンプトに対するユーザ入力の評価を含んでもよい。Ｎｏの場合、既定値を用いる（ステップ４０８）。代替として、パラメータ値はなくてもよく（例えば、ユーザがソート関数をアクティブ化するよう選択しなかった場合、ソートキーは不要となろう）、従って、無視してもよい。さもなければ、ユーザ入力のためにプロンプトを生成する（ステップ４０４）。
【００３７】
ユーザが特定パラメータの値を入力しない場合（ステップ４０６）、パラメータの既定値を選択できる（ステップ４０８）。代替として、ユーザ入力がないことを示すためにエラー状態を発生させることができる。どのイベントでも（ユーザ入力がないことによるエラー状態ではないと仮定する）、入力の変換ならびに他のパラメータに基づく従属関係および条件を考慮してパラメータの最終値が決定される（ステップ４１０）。
【００３８】
ユーザ入力が特定パラメータに対して指示されないと判定された場合（ステップ４０２）、そのパラメータが、環境変数またはコマンドラインパラメータのように、外部からプログラム的にもたらされるべきかどうかに関しての判定が行われる（ステップ４１２）。Ｎｏの場合、パラメータに対する既定値が選択される（ステップ４１４）。代替として、エラー状態を発生させて、規定形式の利用できる入力がないことを指示するようにしてもよい。どのイベントでも（外部入力がないことによるエラー状態ではないと仮定する）、入力の変換ならびに他のパラメータに基づく従属関係および条件を考慮してパラメータの最終値が決定される（ステップ４１０）。
【００３９】
最終的にパラメータが決まると、オプションのステップとして、全ての条件付き成分（後述する）を完全に、またはフロー（すなわち、グラフのリンクまたは辺）により置換するかのいずれかで、上記説明の規定の条件および規則に基づいて削除できる（ステップ４１６）。演算グラフ構造が最終化され、最終パラメータ値が決まると、グラフは従来方法で実行される（ステップ４１８）。
【００４０】
テスト値
ランタイムパラメータを伴うグラフを創成し、テストを行う間に開発者をサポートするために、ＧＤＥ１０２の好ましい実施の形態は、ランタイムパラメータのテスト値もサポートする。開発者がランタイムパラメータを伴うグラフを実行する場合、またはグラフ成分に影響を与える基底のコードを見たい場合、ＧＤＥ１０２は、関係するテストパラメーターグリッドを表示し、ユーザは一つ以上のランタイムパラメータの新規テスト値をそこに入力できる。好ましくは、用いられるテスト値の最後のセットを記憶しグラフとともに保存する。
【００４１】
ランタイムパラメータ毎に、開発者はテスト値の列に所望のテスト値を入力する。編集フィールドをテスト値の列に関係付けてもよい。テスト値フィールドおよび編集フィールドは、パラメータの種類がＰＬの場合を除いて、ランタイムパラメーターグリッド２００の既定値フィールドおよび編集フィールドと同様に振る舞う。
【００４２】
特定ランタイムパラメータの値に対してユーザを促すべきであるとＰＬの式が指示する場合、テスト値フィールドおよび編集の振る舞いは関係するＰＬの式の解釈に基づく。ＰＬの式が他の入力に基づいて値を単に導き出すだけの場合、ランタイムパラメータは、通常モードではテスト値のグリッドに表示されない。
【００４３】
ランタイムパラメータがその値を取得する方法の規定
パラメータがランタイムパラメータとして指定された後、対応するオブジェクトが収納庫１０４内に創成される。ランタイムパラメータが種類フィールド２１４に「ＰＬ」値を有する場合、パラメータの既定値フィールド３０８は、下記の好適な形を持つ「prompt_for」擬似関数を含む：
【数１】
2008547134.tif 000003
上記に示すように、prompt_for擬似関数は、プロンプトを以前の入力に基づいて表示すべきかどうかを判定する条件付きの式の一部とすることができる。
【００４４】
このようなオブジェクトでは、ユーザーインターフェースを用いて、入力したランタイムパラメータをユーザに直接提示する。好ましい実施の形態では、ウェブインターフェース１０８が、この機能を提供する。特に、ランタイム中は、それぞれのランタイムパラメーターオブジェクトのそれぞれのprompt_for擬似関数は、ウェブインターフェース１０８により構文解析されて、対応するユーザープロンプトを有するウェブページを（例えば、ＨＴＭＬで）生成する。（代替として、このウェブページをランタイムの前に生成して、ランタイム時に単に提示するだけとすることができる。しかし、このウェブページのランタイム生成は、より大きなフレキシビリティを提供する。特に、ページの内容を以前のユーザ入力に依存させることができる）。ウェブインターフェース１０８は、このようなウェブページを表示し、ユーザ入力を受け取る従来のウェブブラウザと併せて用いることができる。
【００４５】
prompt_for擬似関数は、パラメータ値に対するプロンプトの方法をウェブインターフェース１０８へ指し示す。特に、文字列定数のprompt_kindパラメータは、どの種類のユーザーインターフェース（ＵＩ）要素（テキストボックス、ドロップダウンリスト等）を提示するかを指し示す。キーワードをコンマで区切ったリストの文字列のmodifiers（修飾子）部分は、各種プロンプトに共通な幾つかのオプションを提供する。図示の実施の形態では、修飾子文字列内のスペースは意味をもたない。修飾子キーワードは下記のように解釈される：
・キーワード「in place」は、アプリケーションに対する要約レベルのユーザーインターフェースで、要素を直接提示すべきことを宣言し、低位レベルまで「掘り下げ」ずに値が提供されるようにする。in placeが規定されない場合、単純な「編集」ボタンを要約レベルインターフェースで提示し、パラメータ値を提供する別のページへユーザを導く。
・キーワード「blank ok」は、ユーザが値を提供しなくてもよいことを宣言する。アプリケーションは、合理的な方法で既定値を処理する。blank okが規定されない場合、ユーザは、何らかの値を提供しないと、アプリケーションを実行できない。
【００４６】
以下、異なる種類の修飾子を持つprompt_forコールの実施例を幾つか挙げる：
【数２】
2008547134.tif 000004
【００４７】
本項のこれ以降では、各種prompt-kindsおよびそれに対応するoptionsをリストアップし、それぞれがウェブインターフェース１０８により生成されるウェブページにどのように現れるかを説明する。
【００４８】
text [size]  −  従来の一行テキストボックスの文字幅sizeを提示する（sizeが提供されない場合、ブラウザのテキストボックスの既定値のサイズとする）。
【００４９】
radio choice-list [description-list]  −  choice-listの要素毎に一つのボタンとする一セットのラジオボタンの形式で、従来の「一つを選択してください」プロンプトを提示する。description-listが提供される場合、対応する記述（description）でそれぞれの選択にラベル付けし；提供されない場合は、choice-listからの対応項目の文字列形式で、その選択にラベル付けする。
【００５０】
radioplus choice-list [description-list]  −  radioと同様ではあるが、テキストボックスに続く追加ボタンを提示して、choice-listにない「書き込み」値をユーザに選択させる。
【００５１】
checkbox choice-list [description-list]  −  choice-listの要素毎に一つのボタンとする一セットのチェックボックスの形式で、従来の「ゼロ以上を選択してください」プロンプトを提示する。description-listが提供される場合、対応する記述（description）でそれぞれの選択にラベル付けし；提供されない場合は、choice-listからの対応項目の文字列形式で、その選択にラベル付けする。
【００５２】
dropdown choice-list [description-list, size]  −  choice-listの要素に対してドロップダウンリストの形式で、従来の「一つ選択してください」プロンプトを提示する。description-listが提供される場合、対応する記述（description）でそれぞれの選択にラベル付けし；提供されない場合は、choice-listからの対応項目の文字列形式で、その選択にラベル付けする。sizeが提供される場合、多数の選択を一度に見ることができ、提供されない場合は一つしか見えない。
【００５３】
multidropdown choice-list [description-list, size]  −  choice-listの要素に対してドロップダウンリストの形式で、従来の「一つ選択してください」プロンプトを提示する。description-listが提供される場合、対応する記述（description）でそれぞれの選択にラベル付けし；提供されない場合は、choice-listからの対応項目の文字列形式で、その選択にラベル付けする。sizeが提供される場合、多数の選択を一度に見ることができ、提供されない場合はブラウザの既定値の数の項目が示される。
【００５４】
key type-obj [size]  −  所与のtype-objからのフィールドを作成するキー（照合者としても知られる）のプロンプトを提示する。キーは、type-obj内のフィールドを既定値とするsizeと同じ程度の多数の部品をもつことができる。図５は、Keyプロンプトにより生成されるグラフダイアログ５００の一実施の形態の図である。以下は３つの入力keyプロンプトに対するスクリプトテキストの実施例であり、ファイル「/datasets/fixed」は、ドロップダウンボックス５０２に示す利用できるキーの内容を定義する：
【数３】
2008547134.tif 000005
図示の実施の形態では、通常の照合順序は昇順であるが、ユーザは、関係するチェックボックス５０４にチェックを付すことにより、キーに対して降順の照合を選択することができる。
【００５５】
fiter type-obj −所与のtype-objの各フィールドの条件から成るフィルタの式のプロンプトを提示する。「blank ok」修飾子は、フィルタに影響せず；ブランクフィルタは、「真」の式を生じる。図６は、Filterプロンプトにより生成されるグラフダイアログ６００の一実施の形態の図である。それぞれの式のテキスト編集ボックス６０４に関係付けられる利用可能なフィールド名称６０２は、type-objにより定義される。比較値をテキスト編集ボックス６０４に記入し、比較演算子（例えば、等号、より大きい、より小さいまたは、と等しい）を、対応するドロップダウンリストコントロール６０６から選択する。
【００５６】
flexifilter type-obj  −  filterプロンプトと同様であるが、所与のtype-objの各フィールドの条件を作成するフィルタ式のためのプロンプトを提供し、それぞれのラインのフィールド名称はドロップダウンリストから選択可能である。これにより多数の条件に対して同一フィールド（例えば、field STATE=MA OR field STATE＝CA）を用いることが可能になる。
【００５７】
rollup type-obj key [size]  −  所与のキーによりロールアップされる所与のtype-objのフィールドに基づいて、ロールアップ計算のためのプロンプトを提示する。ロールアップは、type-obj内のフィールド数を既定値とするsizeと同じ程度の多数の規則を持つことができる。blank ok修飾子はロールアップに影響を与えず；ブランクロールアップは各グループの値だけを提供するパッケージを生み出す。図７は、Rollupプロンプトにより生成されるグラフダイアログ７００の一実施の形態の図である。図示の実施の形態では、ドロップダウンボックス７０２の列は、利用できるロールアップ計算関数（例えば、合計、最小値、最大値）を定義する。それぞれの計算に関係付けられる利用可能フィールド名称７０４をtype-objにより定義する。それぞれのロールアップ規則は、所望の式のユーザ定義に関係付けられるテキスト編集ボックス７０６、ソース値が計算に参加する基準を定義する（ブール代数式により）ための「場所（where）」テキスト編集ボックス７０８、および計算結果を受け取るフィールドを指定するための出力フィールドテキスト編集ボックス７１０を有する。それを明らかに導き出せる場合には、出力フィールドの名称は規定しなくてもよい。
【００５８】
reformat type-obj [size]  −  type-objのフィールドに基づいて再フォーマット計算のためのプロンプトを提示する。再フォーマットは、type-obj内のフィールド数を既定値とするsizeと同じ程度の多数の規則をもつことができる。図８は、Reformatプロンプトにより生成されるグラフダイアログ８００の一実施の形態の図である。図示の実施の形態では、reformatプロンプトは、同一名称の出力フィールド（チェックボックスボタンを用いて個々に、またはSelect All（全て選択）もしくはSelect None（どれも選択しない）ボタンを用いて集合的に、選択／非選択するか）へ入力フィールドをコピーするだけのために、セクション８０２を含む。プロンプトの第２セクションは、再フォーマットの式（例えば、total=revenue_1−revenue_2）の定義ができるテキスト編集ボックス８０４の列を含む。それぞれの規則は、再フォーマットされた結果を受け取るフィールドを指定するための、関係する出力フィールドテキスト編集ボックス８０６を有する。
【００５９】
outputspec  −  出力データセット仕様のためのプロンプトを提示する。表示されるボタンは、利用できるフォーマットオプションを提示するためのドロップダウンボタン、および出力データセットの特定事例の名称を入力するためのテキスト編集ボックスを含む。blank ok修飾子は出力データセット仕様に影響を与えない。
【００６０】
fpath starting-point  −  ファイルパスに対するプロンプトを提示する。プロンプトは基本的にテキストボックスであるが、その隣りに、ファイルパスを閲覧するためのポップアップウィンドウを出現させる「閲覧（Browse）」ボタンを有する。テキストボックスが空白でない場合、閲覧操作の開始点としてそれを用いる。空白の場合はstarting-point引数を用いる。
【００６１】
rpath starting-point  −  収納庫パスに対するプロンプトを提示する。プロンプトは基本的にテキストボックスであるが、その隣りに、閲覧するためのポップアップウィンドウを出現させる「閲覧（Browse）」ボタンを有する。テキストボックスが空白でない場合、閲覧操作の開始点としてそれを用いる。空白の場合はstarting-point引数を用いる。
【００６２】
radiofpath choice-list [description-list]  −  radioplusと同様であるが、「書き込み（write-in）」スロット内にfpath型のbox-plus-browseボタンを提示する。
【００６３】
radiorpath choice-list [description-list]  −  radioplusと同様であるが、「書き込み（write-in）」スロット内にrpath型のbox-plus-browseボタンを提示する。
【００６４】
条件付き成分
実施によっては、パラメータ値および算出メタデータに基づくグラフの成分およびフローの構造への変更を可能にする条件付き成分メカニズムを含む。グラフの各成分は、その成分がランタイム時にグラフに出現するかどうかの条件を有する。その条件は、ランタイムパラメータを介して直接的または間接的に計算できる。条件付き成分を様々な目的に用いて、例えば、グラフを最適化または専用化することができる。最適化のために、アプリケーションは、特定データセットからの値を使用しない場合、そのデータセットの処理を省略して、グラフをより効率的に実行させることもある。専用化では、アプリケーションは所望の詳細レベルに基づいて幾つかの異なる出力データセットを生成する条件を付けるか、またはグラフの幾つかのオプション部分のどれかを実行可能にすることもある。
【００６５】
図９Ａは、マージ結合（MergeJoin）成分９００が、ファイルＡおよびＢからのデータを結合し、その結果を出力ファイル９０２へ出力する第１グラフのブロック図である。図９Ｂは、ロールアップ成分９０４がファイルＡからのデータを集約し、その結果を出力ファイル９０２へ出力する第２グラフのブロック図である。図９Ｃは、マージ結合成分９０６が、ファイルＡおよびＢからのデータを結合し、その得られたデータをロールアップ成分９０８が集約し、最終結果を出力ファイル９０２へ出力するグラフのブロック図である。条件付き成分を用いて、これら３つのグラフを単一グラフへ組み合わせることができる。この単一グラフは図９Ｃのグラフと最初は同じように見えるが、その正確な構造はランタイムまで決定されない。適切な条件を設定することにより、ロールアップ成分９０８を接続（フロー）により置換できるので、図９Ａのグラフと同様なランタイムグラフが得られる。同様に、適切な条件を設定することにより、マージ結合成分９０６をファイルＡへの接続（フロー）により置換できるので、図９Ｂのグラフと同様なランタイムグラフが得られる。
【００６６】
図示の実施の形態では、条件付き成分は、頂点を定義する任意のグラフ成分（すなわち、入力／出力ファイルのようなデータセット成分、再フォーマットもしくはソート成分のような処理成分、またはサブグラフとして知られる他のグラフ）とすることができる。好ましい実施の形態では、条件付き成分は二つの特殊なパラメータ：Condition（条件）およびCondition-interpretation（条件解釈）により制御される。条件は、ブール代数式、または、ランタイムまで評価を保留する値である。図示の実施の形態では、値「偽」および「０」は、偽の条件を規定し、他の全ての値（空を含む）は真の条件を示す。条件解釈パラメータは相互に排他的な値を許容する二つ、すなわち、Remove Completely（完全削除）およびReplace With Flow（フローで置換）を有する。
【００６７】
図１０は、Condition-interpretation（条件解釈）制御１００４を有するCondition（条件）１００２を表すグラフダイアログ１０００の一実施の形態の図である。Condition-interpretation（条件解釈）制御１００４により、Remove Completely（完全削除）解釈１００６またはReplace With Flow（フローで置換）解釈１００８の何れかの選択が可能となる。
【００６８】
Remove Completely（完全削除）：この解釈では、Condition（条件）を満たす場合、成分および全てのその接続フロー（すなわち、グラフのリンクまたは辺）はグラフから削除されることになる。アクティブなRemove Completely（完全削除）条件は、成分および全てのその直接接続フローをグラフから機能的に削除する。Remove Completely（完全削除）条件は、任意の成分について用いることができる。
【００６９】
グラフから削除される条件付き成分は、条件付き成分の存在によっては他の接続される成分を汚染させる（poison）ことがあり、それらを削除してしまうことがある。図１１は、そのような汚染が発生する状況を示すグラフ１１００の図である。入力ファイル成分１１０２に関する条件が削除を指示し、その対応する条件解釈がRemove Completely（完全削除）である場合、入力ファイル成分１１０２およびその接続フローはともにグラフ１１００から削除される。これは、次いで、ソート成分１１０４を汚染させ、その入力は必須の入力ポートであるのに、それに接続されるデータフローはもう何もないので、ソート成分を削除する。これは次に、ロールアップ成分１１０６を汚染させ、その入力は必須の入力ポートであるのに、それに接続されるデータフローはもう何もないので、ロールアップ成分を削除する。この「消失汚染」を停止させる唯一の方法は、下流成分のオプションのポートまたはカウントされるポート（counted port）への接続である。従って、全体のソート−ロールアップグラフの分流１１０８は、入力ファイル成分１１０２に関する条件が削除を指示すると、グラフ１１００から効果的に削除される。図１１の結果は、元のグラフ構造の公称３入力の結合成分１１１０がランタイム時に２入力の結合成分となる、ということである。
【００７０】
一実施では、汚染（「黙示条件」としても知られる）の詳細な構文は下記の通りである：
・成分が必須のポートを有し、それに接続される活きたフローが存在しない場合、成分およびそれに接続される全てのフローはグラフから削除される。
・成分をグラフから完全に削除する場合、そのポートに接続される全てのフローはグラフから削除される。
・成分をフローで置換する場合、その成分のdesignated input port（指定入力ポート）およびdesignated output port（指定出力ポート）以外の全てのポートへ接続される全てのフローはグラフから削除される。
・必須のインデックス付きポートが、それに接続される活きたフローを持たない場合、同一インデックスを有する対応するオプションのインデックス付きポート毎に、その対応するポートへ接続されるどれかのフローをグラフから削除する。
【００７１】
これらの規則には驚くべき結論がある。例えば、オプションのポートだけを有する成分は、汚染が原因で削除されることはない。従って、所望する場合は、明示的に削除しなければならない。
【００７２】
図１２は、Remove Completely（完全削除）条件付き成分を含むグラフのランタイム準備のプロセスを要約するフローチャートである。Condition-interpretation（条件解釈）がRemove Completelyで、かつCondition（条件）が満たされない場合（ステップ１２００）、条件付きCOMPONENT（成分）はグラフから削除されない（ステップ１２０２）。Condition（条件）が満たされる場合（ステップ１２００）、条件付きCOMPONENT（成分）は、その成分へ接続される全てのフローと併せてグラフから削除される（ステップ１２０４）。次いで、全ての「汚染された」成分およびフローは、上記説明の規則に基づいてグラフから削除される（ステップ１２０６）。
【００７３】
Replace With Flow（フローで置換）：この解釈では、Condition（条件）を満たす場合、成分は、フローで置換されることになる（例えば、グラフの辺）。Replace With Flow（フローで置換）の条件解釈は追加情報を必要とする。図１０を参照すると、ユーザは、成分をグラフから削除する場合に接続を行う入力ポート１０１０（または、カウントされるポートのファミリー）および出力ポート１０１２（または、カウントされるポートのファミリー）を指定する。既定値により、厳密に一つの必須の入力ポートまたはカウントされるポートがあり、厳密に一つの必須の出力ポートまたはカウントされるポートがある場合、これらは、指定されたフロースルー接続ポートである（それぞれ、designated input port（指定入力ポート）およびdesignated output port（指定出力ポート）と呼ぶ）。必須のポートは、接続対象の少なくとも一つのフローを要求するポートである。
【００７４】
図１３は、本発明の特定の実施の形態に対するReplace With Flow（フローで置換）条件付き成分を含むグラフのランタイム準備のプロセスを要約するフローチャートである。図示の実施の形態（ＣＯ＞ＯＰＥＲＡＴＩＮＧ
ＳＹＳＴＥＭ（登録商標）で利用できる成分に基づく）における特定の利用可能な入力および出力の幾つかの成分の従属関係に応じて、幾つかの規則が、この実装およびReplace With Flow（フローで置換）条件の使用に適用される。
・Condition-interpretation（条件解釈）がReplace With Flow（フローで置換）であって、Condition（条件）が満たされない場合（ステップ１３００）、条件付き成分はグラフから削除されない（ステップ１３０２）。
・指定された入力ポートおよび指定された出力ポートを有する成分は、その指定された入力ポートへ接続される厳密に一つの活きた正しいフロー、およびその指定された出力ポートへ接続される厳密に一つの活きた正しいフローがある場合、フローで置換できる（「活きた」フローとは、ランタイム時に削除されなかったフローのことである）（ステップ１３０４）。Ｙｅｓの場合、成分自体をグラフから削除し、その指定された入力ポートへ接続される活きた正しいフロー、およびその指定された出力ポートへ接続される活きた正しいフローを互いにリンクする（ステップ１３０６）。削除される成分の他のポートへ直接リンクされる他のフローはどれも（すなわち、特別に指定された入力および出力ポート以外の全てのポート）、グラフから削除される。削除された成分へ接続された「汚染された」成分およびフローはどれも、上記説明のように削除される（ステップ１３０８）。
・Replace With Flow（フローで置換）条件を有する成分が、カウントされる入力のファミリー内の二つ以上の指定された入力ポートへ取り付けられる活きたフローを有する場合（ステップ１３１０）、グラフを正当なものにするためにはその成分が必要なので、グラフから削除しない（ステップ１３１２）。
・必須入力に活きたファンインフローを有する成分は、特殊な扱いが必要である。「活きたファンインフロー」は、その成分が、必須入力ポートへ接続される活きたファンインフローもしくは全て対全てのフローを有するか、または単一の必須入力ポートへ接続される二つ以上の活きた正しいフローを有することを意味する。そのような成分では、Replace With Flow（フローで置換）条件の解釈は、条件付き成分を活きた入力フロー全てを集める集約成分で置換すべきである（ステップ１３１４）。置換した成分へ接続された「汚染された」フローおよび成分は、上記説明のように、どれも削除される（ステップ１３１６）。
【００７５】
メタデータ伝搬の態様
グラフのメタデータは、例えば、グラフ開発者、グラフユーザにより、またはグラフの別の部分からの伝搬により、提供される。データまたはデータの計算に関係付けられるメタデータを含む各種のメタデータ、例えば：ポートに対するレコードフォーマット（例えば、ポートへ流れ込むかまたはポートから流れ出るレコードのフィールドシーケンスおよびデータの形式）、ソート性、圧縮法、文字セット、バイナリ表現（ビッグエンディアン(big-endian)、リトルエンディアン(little-endian)）、パーティション化、成分がどの計算リソース（例えば、プロセッサ、一時的ディスクスペース）を用いるか、データ変換、および成分が使用できるメモリ量、を伝搬させることができる。グラフ構造の多様な態様がメタデータ伝搬に影響を与える。これらの内の二つの態様を以下に説明する。
【００７６】
成分削除後の伝搬
実施によっては、グラフ成分を削除した後にフローが生成される場合、そのようなフロー内のデータを定義するメタデータを修正後のグラフへどのように伝搬させるべきかを選択しなければならない。メタデータはフローの両端のどちらからでも利用できる。実施によっては、フローの上流端からのメタデータが好ましい。
【００７７】
フローの上流端が削除された成分（または、集約成分で置換された成分）の場合、ＧＤＥ１０２は、まだ削除されていない成分を見つけるまで、グラフの上流を「歩く」ことにより、そのフローのためのメタデータを見つける。その上流成分により曝されたメタデータを用いて、生成されたフローのためのデータの特性を定義する。
【００７８】
変換したメタデータの伝搬
上記説明のように、メタデータは、あるポートに関係付けられるメタデータを別のポートに対するメタデータを含む一つ以上のパラメータの関数として規定することにより、内部変換データパスを越えてでも伝搬することができる。図２３Ａは、データセット２３０２およびデータセット２３０４からのデータに対して結合操作を計算するグラフ２３００を示す。この実施例では、グラフ開発者はデータセットの出力ポートでメタデータを提供する。次いで、このメタデータは、入力データセットのレコードに対して結合操作を計算する「スマート結合」成分２３０６へ伝搬される。例えば、メタデータは、出力ポート２３０８から入力ポート２３１０へ伝搬する。次いで、メタデータは、「スマート結合」成分２３０６により変換され、「スマート結合」成分２３０６の出力ポート２３１６からフィルタ成分２３１８の入力ポート２３１７へ伝搬する。
【００７９】
図２３Ｂは、「スマート結合」成分２３０６を実装するサブグラフを示す。成分２３０６は、結合成分２３５０が実行する結合操作のキーフィールドをその値が表すkey_field パラメータを用いる。成分２３０６は条件付きソート成分２３５４および２３５６を含むための条件としてもkey_field パラメータを用いる。入力ポート２３１０へ流れ込むレコードがkey_field に関して既にソートされている場合、ソート成分２３５４は条件を取り消される。同様に、入力ポート２３１４へ流れ込むレコードがkey_field に関して既にソートされている場合、ソート成分２３５６は条件を取り消される。入力レコードのどちらかのフローがkey_field に関してまだソートされていない場合、ソート成分２３５４および２３５６は、レコードをソートしてから結合成分２３５０へ流し込む。
【００８０】
変換されたメタデータの伝搬をこの「スマート結合」成分を通じて可能にするために、グラフ開発者は、「スマート結合」成分２３０６の出力ポート２３１６に対するメタデータ（例えば、フィールドを記述するためのメタデータ）を、第１入力ポート２３１０に対するメタデータinput0.metadata、第２入力ポート２３１４に対するメタデータinput1.metadata、およびキーフィールドパラメータkey_field、の関数として定義する：
output.metadata=metadata_join(key_field,input0.metadata, input1.metadata)
【００８１】
出力ポートメタデータは関数の引数を値（適切なコンテクストに関して）にバインドし、その結果に関数metadata_joinを実行することにより決定する。この実施例では、ポート２３１０および２３１４に対するメタデータは未定義なので、伝搬メタデータは、メタデータパラメータinput0.metadataとinput1.metadataとへ結合される。ユーザは、ポート２３０８から、「スマート結合」成分２３０６の入力ポート２３１０へ流れるレコードに対するフィールド「Ａ」および「Ｂ」を規定する出力ポート２３０８に対するメタデータを提供する。ユーザは、同様に、出力ポート２３１２から、「スマート結合」成分２３０６の入力ポート２３１４へ流れるレコードに対するフィールド「Ａ」および「Ｃ」を規定する出力ポート２３１２に対するメタデータを供給する。このユーザ供給メタデータはポート２３１０および２３１４へ伝搬する。結合操作のためのキーフィールドはフィールドＡなので、「公式パラメータ」key_fieldは値「Ａ」へバインドされる。
【００８２】
関数metadata_joinは、key_fieldパラメータの値が、input0.metadataおよびinput1.metadataにより規定されるフィールドの両セットのメンバーかどうかを最初に決定することにより、出力メタデータを決定する。そうであるなら、出力メタデータは二セットのフィールドの和集合である。そうでなければ、出力メタデータはフィールドの空集合を示す。
【００８３】
メタデータが「スマート結合」成分２３０６の入力ポートへ伝搬した後（または、例えば、ユーザが提供した後）、「スマート結合」成分２３０６の出力ポートの変換されたメタデータは、フィールドＡ、Ｂ、およびＣを含む。次いで、この変換されたメタデータを、他の成分へ伝搬させることができる。この実施例では、変換メタデータはフィルタ成分２３１８へ伝搬する。
【００８４】
メタデータは、ユーザが提供するか、またはポート間を伝搬するかにかかわらず、ユーザに表示することができる。例えば、ユーザは入力装置（例えば、マウス）を用いて成分の一部を、そのメタデータの値を見るために選択できる。メタデータ伝搬はそのようなユーザ選択に応じて始動させることもできる。
【００８５】
例示のメタデータ伝搬プロセス
図２４は、例示のメタデータ伝搬プロセス２４００のフローチャートである。プロセス２４００は、例えば、グラフ内の変更がある度に、ユーザのアクションに応じて、および／またはグラフを実行する直前に、実行することができる。プロセス２４００は、フローが決定する部分的な順序に基づいて順序付けられたグラフ内の各成分により作業リストを生成する（例えば、成分Ａは、成分Ａから成分Ｂへのフローがある場合、成分Ｂの前にくる）。フローが二つの成分間の一意の順序を決定しない状況では、成分ラベルのアルファベット順を均衡を破るために用いることができる。これは、作業リスト内の成分の安定な順序付けを提供する（成分ラベルが一意であると仮定する）。伝搬プロセス２４００がグラフに対して繰り返される場合（例えば、新規成分の追加後）、新規作業リストは、以前の作業リスト内の成分間の順序と同一の順序を維持する。
【００８６】
プロセス２４００は、作業リストの開始で始動し、作業リスト内の成分毎に、プロセス２４００は、成分を実装するサブグラフの仕様（例えば、サブグラフ内のデータフロー）に基づいて、２４０４にて内部（例えば、入力ポートから出力ポートまで、または出力ポートから入力ポートまで）でメタデータを伝搬させる。この内部のメタデータ伝搬は、非変換データパスのどちらかの端にある複数ポート間に非変換メタデータを転送するステップを含む。内部メタデータ伝搬は、上記説明のように、グラフのパラメータおよび／または他のポートのメタデータを参照するメタデータ定義を有するポートに対してメタデータを導き出すステップも含む。プロセス２４００がこのようなメタデータ定義に出会った場合、プロセス２４００は、メタデータを導き出すのにその値が必要な何れかのパラメータを評価する。
【００８７】
作業リスト上の成分に対する内部メタデータ伝搬を実行した後、プロセス２４００は、メタデータを有する成分の各ポートから、２４０６にてメタデータを持たない関連成分のポートへメタデータを外部伝搬させる。この外部伝搬によりメタデータを取得する成分はどれも、２４０８にて作業リストの最後へ移動する。プロセス２４００は、２４１０にて作業リストの最後の成分を処理した後に終了する。
【００８８】
この種類の外部メタデータ伝搬をサポートする成分間の、ある種類の関連性は、二つの成分のポート間（例えば、入力ポートから出力ポートまで、または出力ポートから入力ポートまで）のデータフローリンクである。
【００８９】
この種類の外部メタデータ伝搬をサポートする成分間の、別の種類の関連性は、あるポートに対するメタデータを別のポートに用いることもできることを示すリンクである。この種類の「メタデータリンク」は必ずしもデータフローリンクに対応するとは限らない。例えば、ポートは、特にどれかのポートに関係付けられないグラフ内のメタデータへのメタデータリンクを持つことができる。
【００９０】
成分化したサブグラフのランタイムパラメータ
サブグラフを別のグラフの成分として用いるために「成分化」する前に、成分の入力および／または出力ポートのような成分の各種特性を定義する。ランタイムパラメータを持つ成分を含むサブグラフでは、ランタイムパラメータのプロンプト順序を選択するのがよい。グラフ内の成分は必ずしもシーケンシャルな順序とは限らないので、ユーザを促すための、ランタイムパラメータの多くの可能性のあるグローバル順序付けがあり得る。グローバル順序の幾つかは、各成分に関係付けられる元の順序と一致しない。各成分のパラメータの順序をできるだけ維持する、プロンプトのためのグローバル順序を生成する一方で、従属関係を考慮するのにふさわしい場合は再順序付けすることも有用である。例えば、成分は、「処理したデータをどこに格納しますか？」と質問するプロンプトの前に、「どのデータを処理しますか？」と質問するプロンプトを順序付けることができる。どの順序でプロンプトを提供できるとしても、この順序でプロンプトを提供することが望ましい。
【００９１】
プロンプトされるランタイムパラメータを評価するプロセスで、プロンプトされないランタイムパラメータを評価する必要があるかもしれないので、プロンプト化の順序は、全てのランタイムパラメータの評価順序から得られる。グラフのランタイムパラメータ（どの成分とも関係付けられないグラフのパラメータを含む）の評価順序を決定するための一手法は、パラメータ間の従属関係を表す一つ以上の有向非循環グラフに基づいて、トポロジカルなソートを実行するステップを含む。しかし、トポロジカルなソートアルゴリズムによっては、不必要にパラメータを再順序付けすることがあり、ランタイムパラメータに対する好ましくないプロンプト化順序が生じてしまう。
【００９２】
ソート実施例１
第１実施例では、パラメーターソートプロセスは、二つのグラフ成分、すなわち、Component（成分）Ｉ、およびComponent（成分）Ｉへ接続されるComponent（成分）ＩＩ、のパラメータに対する最初のパラメータリストを提供する。この実施例では、パラメータは「成分内」従属関係だけを有する。すなわち、成分のパラメータは、同一成分内の他のパラメータにのみ従属する。パラメータは下記のように定義される：
Component（成分）Ｉは下記パラメータを含む：
【数４】
2008547134.tif 000006
Component（成分）ＩＩは下記パラメータを含む：
【数５】
2008547134.tif 000007
【００９３】
パラメータをリストアップする順序は、ユーザに値を促す所望順序を定義する。パラメータの最初のリストは、成分毎のこの「最初の順序付け」を維持する。「序数」が各パラメータへ割り当てられて、最初の順序付けのそのパラメータの順序を示す。下記の表は、この最初の順序付けにおけるパラメータをリストアップする。
【表１】
2008547134.tif 000008
【００９４】
「従属関係」の列は、リストにあるパラメータが従属する他のパラメータを示す。従属関係は、パラメータ評価に順序付けの制約を課す。すなわち、パラメータを別のパラメータが使用する（例えば、参照する）前に、それを定義する必要がある。
【００９５】
「共通トポロジカルソート」アルゴリズムは、従属関係を持たないパラメータを転送するリストを通って、それぞれを通るたびに順序付けした出力リストへ行く。それぞれを通った後、転送されるパラメータを、どれも従属関係の列から削除する。この処理は全てのパラメータが転送されてしまうまで繰り返される。これらの他のパラメータを評価してから、他のパラメータに従属するパラメータを評価するように、出力リスト内のパラメータ順序は「最終的な順序付け」を表す。
【００９６】
この実施例では、１回目に通ったとき、パラメータｘ、ｑ、ａおよびｃを出力リストに転送する。２回目に通ったとき、パラメータｙおよびｂを出力リストに転送する。３回目および最終的に通ったとき、パラメータｚを出力リストに転送する。従って、パラメータに対する最終的な順序付けは：ｘ、ｑ、ａ、ｃ、ｙ、ｂ、ｚである。この順序付けは、パラメータ従属関係により課される順序付けの制約を満たすが、それはパラメータを不必要に再順序付けすることにもなる。この実施例では、最初の順序付けは、パラメータ従属関係により課される順序付けの制約も満たす。
【００９７】
順序付けの制約を満たすグラフのパラメータに対する評価順序を決定するための他の手法は、最初の順序付けを尊重する。例えば、幾つかの手法は、パラメータを順序付けて、順序付けの制約を満たし、最初の順序付けに基づく基準によって順序付けを選択する。基準には、最初の順序付けに近い順序を保持するのを優先的に扱う多様な基準（例えば、最初の順序付けへの変更に基づいて尺度を最小化する）のどれかを含めることができる。場合によっては、多数の順序付けが、どれも良好に基準に基づいて所与の基準を満たすことができるので、唯一の「最良」の順序付けが存在しないこともある。
【００９８】
最初の順序付けを尊重する手法の一実施例は、「修正トポロジカルソート」手法である。この手法では、最初の順序付けに基づく基準は、最初のリストから転送されるパラメータの数を最小化してから、転送されないパラメータのどれにも従属しない先行するパラメータを転送する。換言すると、「修正トポロジカルソート」は、従属関係の列から転送されるパラメータを削除してから、従属関係がゼロの次のパラメータを転送する。上記実施例では、「修正トポロジカルソート」手法は、最初の順序付けｘ、ｙ、ｚ、ｑ、ａ、ｂ、ｃと同一の最終的順序付けを生成する。
【００９９】
最初の順序付けを尊重する修正トポロジカルソートプロセス
パラメータ毎に割り当てられた序数により決定されるように、両方が最初の順序付けを尊重する二つの例示の「修正トポロジカルソート」プロセスについて、擬似コードを以下に示す。第２プロセスは、幾つかの場合に対する時間効率を改良する最適化を含む。このプロセスは、パラメータに対する入力データから生成されるデータ構造を操作する。
【０１００】
順序付けられるべきＮ個のパラメータがあると仮定すると、入力データは、一意のパラメータ名称、名称を付されたパラメータが従属する一セットのパラメータ（「従属関係セット」と呼ばれる）、および名称を付されたパラメータに関連する情報を格納するオプションの属性データオブジェクト、からなるＮ×３個（Ｎ triples）のリストを含む。
【０１０１】
この入力データに関係付けられるのは、パラメータ間の従属関係を表す一つ以上の非循環グラフであり、「従属関係グラフ」と呼ばれる。それぞれの一意のパラメータ名称は、従属関係グラフのノードに対応し、関係する従属関係セットは、他のノードからそのノードへのリンクセットに対応する。従って、リンクは、第１パラメータに対する第１ノードから、第１パラメータに従属する第２パラメータに対する第２ノードに向いている。代替として、リンクの方向とパラメータ従属関係との間の対応を逆にすることができる。
【０１０２】
パラメータを評価した後、最初の順序付けに近い順序を保つのを優先しながら、別のパラメータを評価するために用いることができるように、出力データ構造result_listは、（必要な場合）再順序付けされた入力データからのＮ個のパラメータのリストを含む。出力データ構造result_listを生成するために、このプロセスは、作業データ構造param_listから出力データ構造result_listへ、一つずつパラメータを転送することによりパラメータを「除去」する。出力データ構造は、全てのパラメータを除去した後に完成する。
【０１０３】
第１の「修正トポロジカルソート」プロセスは二つの段階を含む。第１段階で、このプロセスは、ソートした出力データ構造を生成する際に用いるために、入力データに基づいて作業データ構造を作成する。第２段階で、このプロセスは、これらの作業データ構造により表される従属関係の制約に基づいてパラメータを繰り返しソートし、除去する。
【０１０４】
このプロセスが第１段階で作成する作業データ構造の幾つかは、ハッシュ化に基づくデータ構造の辞書である。辞書の項目には、時間O(logN)で効率的にアクセスできる。以下の例示のデータ構造は第１段階で作成される：
parm_list[index]：番号index（index = 0はリスト内の第１項目と対応する）によりインデックス化された、除去されないパラメータ名称を順序付けたリスト。このデータ構造は「動的」である（すなわち、プロセスの実行中に変化する）。項目をリストの中央から削除する場合、それに合わせて削除項目の後の項目のインデックスが移動するように、リストは位置によりインデックス化する。
n_dependencies_dict[name]：パラメータ名称（name）により入力される辞書であり、そのエントリは、入力されるパラメータが従属するパラメータの数を含む。この辞書は動的である。
dependers_dict[name]：パラメータ名称（name）により入力される辞書であり、そのエントリは、入力されるパラメータに従属するパラメーターセットを表す辞書である（パラメータ名称によっても入力される）。この辞書は静的である（すなわち、プロセス実行中に変化しない）。
order_dict[name]：パラメータ名称（name）により入力される辞書であり、最初の順序付けにおけるパラメータの序数付き位置、０〜Ｎ−１の整数を格納する。この辞書は静的である。
attribute_dict[name]：パラメータ名称（name）により入力される辞書であり、入力されるパラメータに対するオプションの属性データオブジェクトを格納する。この辞書は静的である。
result_list[index]：プロセスの出力を表すパラメータ名称および属性の順序付けたリストであり、番号のindexによりインデックス化される（index = 0はリスト内の第１項目に対応する）。このデータ構造は最初は空である。この辞書は動的である。
【０１０５】
プロセスの時間効率を解析するために、従属関係グラフの平均「程度」（または、ノードからのリンク数）をzと仮定する。これらのデータ構造を作成するには、時間O(N)が必要である。但し、時間O(N*z)を要するn_dependencies_dictおよびdependers_dictを除く。
【０１０６】
第２段階で、このプロセスは、これらが従属する除去されないパラメータの数により（すなわち、n_dependencies_dictの値だけ）、最低から最高まで、次いで、これらの序数により（すなわち、order_dictの値により）、最低から最高まで、最初にパラメータを順序付けるby_n_deps_and_orderによるソート基準に基づいてparam_listデータ構造内のパラメータをソートする。次いで、このプロセスは、ソートしたparam_list内の第２パラメータを除去する。このパラメータに対するn_dependencies_dictの値はゼロにすべきである。（ソートしたparam_list内の第１パラメータに対するn_dependencies_dictの値がゼロでない場合、エラーフラグが立てられる）。
【０１０７】
パラメータを除去するために、このプロセスは、それを（どれかの対応する属性と併せて）result_listに追加し、従属するもの全ての（すなわち、dependers_dict内のパラメータ）従属関係カウント（すなわち、n_dependencies_dictの値）を１だけ減じる。最終的にそのパラメータはparm_listから消去される。得られた第１パラメータのソートおよび除去を、全てのパラメータが除去されてしまうまで繰り返す。
【０１０８】
以下は、eliminate（除去）手順のための擬似コード定義である：
【数６】
2008547134.tif 000009
【０１０９】
eliminate（除去）手順の引数は、list（その値は、例えばparam_listである）およびindexである。関数result_list.appendは、関係する属性と併せて、位置indexに指示されるlist項目をresult_listに追加する。次いで、この手順は、除去されるパラメータに関して入力されるdependers_dictデータ構造のメンバーである各パラメータdependerに対するn_dependencies_dictの値を１だけ減じる。次いで、この手順は、listからパラメータを消去する。eliminate（除去）手順のランタイムは、O(zlogN)である。
【０１１０】
以下は、第１「修正トポロジカルソート」プロセスに対するソート／除去ループのための擬似コードである：
【数７】
2008547134.tif 000010
【０１１１】
このプロセスは、最初に、上記説明したソート基準by_n_deps_and_orderに基づいてparam_listのパラメータを順序付ける関数parm_list.sort(by_n_deps_and_order)を用いてparam_listの最初のソートを実行する。次いで、このプロセスは、param_listが空になるまで、param_listの別のソートが続くeliminate（除去）手順を実行する。このプロセスは、param_list内の第１パラメータ（index =0を有する）に対する従属関係の数を確認するためにチェックする。Ｎｏの場合、このプロセスは、パラメータを削除し、循環エラーを記録し、そして継続する。ソートはO(NlogN)を要し、ループ範囲はNなので、ループに対する全体のランタイムに対する評価はO(N2logN)である。
【０１１２】
第２の「修正トポロジカルソート」プロセスは、z << Nのような従属関係グラフがまばらな場合に利点がある。ある最初のソート後、このプロセスは、他のどのパラメータにも従属しないパラメータのリストcandidates（候補）のソート性を維持することができる。これは、後述するように、この予想されるランタイムを短縮する。
【０１１３】
以下は、第２「修正トポロジカルソート」プロセスに対する擬似コードである：
【数８】
2008547134.tif 000011
【０１１４】
このプロセスは、最初に、上記説明したソート基準by_n_deps_and_orderに基づいてparam_listのパラメータを順序付ける関数parm_list.sort(by_n_deps_and_order)を用いてparam_listの最初のソートを実行する。次いで、このプロセスは、三つのセクション（ラベル付きの「＃セクション１」、「＃セクション２」、および「＃セクション３」）を有するループを実行する。
【０１１５】
セクション１で、このプロセスは、従属関係がゼロのパラメータだけを含むcandidates（候補）リストを作成する。このプロセスは、parm_list内の全てのパラメータをスキャンし、それらをcandidates（候補）に追加し、それらの相対的な順序を保存する。
【０１１６】
セクション２で、このプロセスは、candidates（候補）からのパラメータを消去し、新規パラメータをcandidates（候補）内に結合するループを実行する。this_parmとして保存されたcandidates（候補）内の第１パラメータは、candidates（候補）から除去され、param_listから消去される。関数get_new(this_parm)は、新規に除去されたthis_parmに対するdependers_dictのメンバーであるパラメータ名称のリストを返し、ゼロの従属関係を残す。次いで、削除された最後の従属関係を持っているパラメータを表すこれらのパラメータを、（それぞれの序数に基づいて順序付けられたことを確認するため）by_n_deps_and_orderに基づいてソートし、candidates（候補）内に結合する。従って、candidates（候補）リストは、序数によりソートされるゼロ従属関係パラメータのリストのままである。
【０１１７】
セクション３は、例えば、二つのパラメータが互いに対して定義される場合に発生する「循環エラー」がある場合に参加するだけである。この場合、このプロセスは、parm_listを再びソートし、parm_list内の第１パラメータがゼロでない従属関係を有する場合、それを消去し、ループをセクション１で繰り返す。
【０１１８】
循環エラーが存在しないと仮定すると、Nパラメータのリストparm_listを開始時のみソートし、O(NlogN)のソート時間を生じる。この後は、candidates（候補）リストの先頭でパラメータを除去することにより得られる、新規に生成された従属関係のないパラメータの、ずっと小さなリストについてソートを行うだけでよい。このリストのサイズは（平均で）z未満であり、ソート時間O(zlogz)およびマージ時間O(z)が得られる。従って、ループの一回の繰り返しはO(zlogz)であり、全体時間はO(Nzlogz + NlogN)である。zがNの増加とともに増加しない場合には、この時間はO(NlogN)と効率的になる。
【０１１９】
ソート実施例２
別の実施例では、パラメータソートプロセス（例えば、第１または第２「修正トポロジカルソート」プロセス）は、図２５Ａに示すように、グラフ成分２５０２、２５０４および２５０６を有するグラフ２５００に対する、ランタイムパラメータの最初のリストを決定する。グラフ２５００は、入力データセット２５１０の出力ポート２５０８および出力データセット２５１４の入力ポート２５１２に関係付けられるランタイムパラメータも有する。この実施例では、パラメータは、「成分内」従属関係および「成分間」従属関係の両方を有する。すなわち、成分のパラメータは、同一成分内のパラメータおよび他の成分内のパラメータに従属する。この実施例では、成分間の従属関係は、幾つかのパラメータが従属するメタデータの伝搬を可能とする成分間のフローにより発生する。
【０１２０】
従属関係を、図２５Ａに、第１パラメータまたはポートから第２パラメータまたはポートまでの矢印で示す。ポートへの矢印は、リンクされるパラメータの値が、そのポートから下流のポートへ伝搬することを示す。あるポートからの矢印は、値が上流ポートから、リンクされるパラメータへ伝搬することを示す。第１パラメータから第２パラメータへの矢印は、第２パラメータの値が第１パラメータの値に従属する（例えば、参照する）ことを示す。
【０１２１】
図２５Ｂは、グラフ２５００に基づくパラメータｐ０、ｐ１、ｐ２、ｐ４、ｐ５およびｐ６間の順序付け制約を表す従属関係グラフ２５５０を示す。図２５Ｃは、グラフ２５００に基づくパラメータｐ３、ｐ７、ｐ８およびｐ９間の順序付け制約を表す従属関係グラフ２５５２を示す。
【０１２２】
パラメータソートプロセスは、グラフ２５００内の要素配置の順序に基づいて、様々なグラフ要素に対する１０個のパラメータｐ０、ｐ２、…ｐ９それぞれに序数を割り当てる。図２５Ａでは、グラフ２５００へ追加される（例えば、ＧＤＥ１０２を用いてユーザにより）第１グラフ要素は、パラメータｐ０、ｐ１およびｐ２を有する成分２５０２である。追加される第２要素は、パラメータｐ３、ｐ４およびｐ５を有する成分２５０６である。追加される第３要素は、パラメータｐ６を有するデータセット２５１０である。追加される第４要素は、パラメータｐ７を有するデータセット２５１４である。追加される最後の要素は、ランタイムパラメータを持たないデータセット２５１６である。以下の表は割り当てられた序数により定義された最初の順序付けでパラメータをリストアップする。
【表２】
2008547134.tif 000012
【０１２３】
処理の様々な段階におけるparam_listおよびresult_list内のパラメータの以下のリストは、上記説明の第１「修正トポロジカルソート」プロセスに対応する。それぞれの段階におけるby_n_deps_and_orderにより、ソート基準に基づいてソートされるparam_listを示す。
【表３】
2008547134.tif 000013
【０１２４】
処理の様々な段階におけるcandidates（候補）およびresult_list内のパラメータの以下のリストは、上記説明の第２「修正トポロジカルソート」プロセスに対応する。パラメータがそれぞれの段階における同一順序内に残っているので、段階の間のcandidates（候補）をソートしなくてもよい。
【表４】
2008547134.tif 000014
【０１２５】
従って、図２６を参照すると、「修正トポロジカルソート」プロセス２６００は、ランタイムパラメータの値をユーザに促す順序の所望の第１順序付け２６０２、およびパラメータに対する順序付け（例えば、従属関係グラフ２５５０および２５５２）の制約２６０４を入力としてとる。プロセス２６００は、所望の第２順序付け２６０２に基づいて順序付け制約を満たすパラメーターセットの新規順序付け２６０６を提供する。
【０１２６】
典型的な使用法
典型的には、ユーザは、ウェブインターフェース１０８の前に座り、ユーザが実行したいアプリケーションのグラフを収納庫１０４内に見つける。アプリケーショングラフに関係付けられるオブジェクト全てをスキャンすることにより、ウェブインターフェース１０８は、ユーザがアプリケーションのランタイムパラメータの値を規定できるウェブページ入力フォームを生成する。全てランタイムパラメータを規定し終わると、アプリケーションとパラメータ設定との組み合わせは、ジョブとしてまとめられ、実行部１１０が実行するようスケジュール化される。ジョブ実行の時間がくると、実行部１１０は、既知の方法で、並列オペレーティングシステム１０６のもとで実行するためにアプリケーションを待ち行列に並ばせる。並列オペレーティングシステム１０６は、ユーザおよび運営者がジョブの進行および性能を追跡できるように、追跡情報およびジョブステータスを収集し、この情報を収納庫１０４に格納する。
【０１２７】
実施例
図１４は、ランタイムパラメータがないロールアップアプリケーションを表すグラフ１４００の図である。このグラフは、それぞれの種類のアカウントの数を計算し、その結果を出力ファイルへ書き込む。本アプリケーションの全ての態様、すなわち、入力ファイル成分１４０２の名称、入力データのフォーマット、ハッシュロールアップ成分１４０４内のデータをロールアップするために用いるキーと変換規則、出力フォーマット、および出力ファイル成分１４０６の名称は、グラフ開発者が決定したものである。ユーザは定義に従って正確にこのグラフを実行するだけでよい。
【０１２８】
図１５は、図１４のロールアップアプリケーションのランタイムパラメータ化バージョンを表すグラフ１５００の図である。このアプリケーションのデータフローグラフ構造は、非ランタイムパラメータ化バージョンと非常に類似しているが、このアプリケーションの方がよりフレキシブルである。ランタイムパラメータを通じて、エンドユーザは抽象化された入力データセット１５０２（入力ファイル名称およびフォーマットが導き出される収納オブジェクト）の名称、ハッシュロールアップ成分１５０４に対するロールアップキーおよびロールアップ規則、および出力ファイル成分１５０６の名称を規定できる。
【０１２９】
図１６は、図１５のアプリケーション例に対するランタイムパラメーターグリッド１６００を表すグラフダイアログの一実施の形態の図である。これは、図２に示すパラメーターグリッドの記入バージョンである。注意すべきは、上記説明のように、幾つかの既定パラメータがprompt_for擬似関数を用いて定義される、ということであり、従って、ウェブインターフェース１０８を介するユーザ入力を必要とする。このグラフの外観は、非ランタイムパラメータ化アプリケーショングラフとほとんど違わないが、一つ以上のパラメーターグリッド（または、他の適切な制御）により、開発者は、グラフの実行を制御する全てのパラメータを完全に追跡することができる。
【０１３０】
図１７Ａは、図１６のパラメーターグリッド１６００内の情報から、ウェブインターフェース１０８により生成される入力フォーム１７００を表すグラフダイアログの一実施の形態の図である。この実施例では、入力フォーム１７００は、ユーザ入力の４つのランタイムパラメータ、すなわち、入力データセット収納庫パス１７０２、ロールアップキー１７０４、ロールアップ規則１７０６、および出力パス１７０８を表す。図１７Ｂは、ユーザがパラメータ値を記入した図１７Ａの入力フォーム１７００の図である。直接記入および／またはランタイムパラメータ１７０２〜１７０８に関係付けられる編集またはブラウザ操作ボタンを用いて、ユーザは、関係グラフを実行するための対応するパラメータ値１７１０〜１７１６を提供する。
【０１３１】
図１８は、ランタイムパラメータ化したロールアップおよび結合アプリケーションを表すグラフの図である。図１９は、図１８のアプリケーション例に対するランタイムパラメーターグリッド１９００を表すグラフダイアログの一実施の形態の図である。ここで、このアプリケーションの幾つかの態様がパラメータ化されているが、結合キーおよび入力データセットを含むほとんどは固定されたままである。図２０は、図１９のパラメーターグリッド１９００内の情報からウェブインターフェース１０８により生成される入力フォーム２０００を表すグラフダイアログの一実施の形態の図である。注意すべきは、ロールアップへの入力形式は上位の入力フォームが表示された時点で既知となるので、ロールアップ規則２００２を所定の位置に指示することができることである。
【０１３２】
図２１は、ランタイムパラメータ化したロールアップ−結合−ソートアプリケーションを表すグラフ２１００の図である。図１８の実施例と同様であるが、条件付きソート成分２１０２がグラフ２１００へ追加されている。図２２は、図２１に示すアプリケーション例に対するランタイムパラメーターグリッド２２００を表すグラフダイアログの一実施の形態の図である。sort_keyランタイムパラメータ２２０２は、ソートを望んでいることをユーザが示す場合のみ、記入を促される。この効果を得るために、開発者は、sort_keyランタイムパラメータ２２０２の既定値２２０４に対するif条件付きテスト内にprompt_for擬似関数を置く。if条件付きテストは、第２のランタイムパラメータ、do_sort２２０６を参照する。do_sortパラメータ２２０６の既定値フィールド２２０８および記述フィールド２２１０を定義して、テキストプロンプト「データをソートすべきでしょうか？」に対する真／偽またはＹｅｓ／Ｎｏの回答をユーザに質問するradioプロンプトを生成する。do_sortパラメータ２２０６に提供される値が「真」の場合、ソート成分２１０２はランタイム時にグラフの一部として含まれる。「偽」の場合、ソート成分２１０２は、その規定した条件解釈に応じて、グラフから完全に削除されるか、またはフローで置換される。
【０１３３】
スクリプト実装
ＧＤＥ１０２は、パラメータ化したグラフの構築を容易にするが、時には、入力フォーム型インターフェースを提供したいと望まれる非グラフ形プログラムが存在する。アプリケーションレベルＰＬおよび収納庫１０４を用いて、任意のシェルスクリプトをパラメータ化できる。例えば、アプリケーションの記述を下記に類似な構造を有するファイルへ書き込むことができる：
【数９】
2008547134.tif 000015
【０１３４】
汎用コンピュータ実装
本発明は、ハードウエアもしくはソフトウエア、または両者の組み合わせ（例えば、プログラマブルロジックアレイ）で実装することができる。他に言及しない限り、本発明の一部として含まれるアルゴリズムは、何らかの特定コンピュータまたは他の装置と本質的には関連していない。特に、各種の汎用マシンを、本明細書の教示に基づいて書かれたプログラマブルにより用いることができ、または、より専用化した装置を構築して、要求される方法ステップを実行すると一層便利になる。しかし、本発明は、一台以上のプログラマブルコンピューターシステム上で実行する一台以上のコンピュータープログラムで実装することが好ましい。それぞれのシステムは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム（揮発性メモリおよび不揮発性メモリおよび／または記憶素子を含む）、少なくとも一つの入力装置またはポート、および少なくとも一つの出力装置またはポートを備える。プログラムコードをプロセッサ上で実行して、本明細書で説明した機能を実行する。
【０１３５】
このようなプログラムはそれぞれ、任意の所望するコンピュータ言語（機械語、アセンブリ言語、または高級プロシージャ言語、論理言語、もしくはオブジェクト指向プログラミング言語を含む）で実装して、コンピューターシステムと通信することができる。どの場合でも、言語はコンパイル型またはインタプリート型言語とすることができる。
【０１３６】
このようなコンピュータープログラムはそれぞれ、汎用もしくは専用のプログラマブルコンピュータが読み取り可能な格納媒体または装置（例えば、固体、磁気、または光の媒体）に格納して、格納媒体または装置をコンピューターシステムが読み出し、本明細書で説明した手順を実行する時にコンピュータを構成し、動作させることが好ましい。進歩性のあるこのシステムは、コンピュータープログラムで構成されたコンピュータが読み取り可能な格納媒体として実装し、そのように構成される格納媒体が、コンピューターシステムを規定の方法、所定の方法で動作させて、本明細書で説明した機能を実行させると考えることもできる。
【０１３７】
本発明の幾つかの実施の形態を説明してきた。にもかかわらず、言うまでもないのは、本発明の精神および範囲から逸脱することなく多様な修正を行うことができるということである。例えば、上記説明の機能ステップの幾つかは、全体の処理に実質的に影響を与えることなく異なる順序で実行してもよい。例えば、図４のステップ４０２および４１２は順序を逆にしても実行可能である。従って、他の実施の形態は以下のクレームの範囲内にある。
【図面の簡単な説明】
【０１３８】
【図１Ａ】図１Ａは、主要素の相互関係を示す本発明の一実施の形態のブロック図である。
【図１Ｂ】図１Ｂは、データフローグラフのブロック図である。
【図２】図２は、指定されたランタイムパラメータを有するロールアップ成分およびソート成分２０４を有する代表的なグラフのブロック図である。
【図３】図３は、グラフに関係付けられるランタイムパラメーターグリッドを表すグラフダイアログの一実施の形態の図である。
【図４】図４は、ランタイムパラメータを用いるプロセスを要約したフローチャートである。
【図５】図５は、Key（キー）プロンプトにより生成されるグラフダイアログの一実施の形態の図である。
【図６】図６は、Filter（フィルタ）プロンプトにより生成されるグラフダイアログの一実施の形態の図である。
【図７】図７は、Rollup（ロールアップ）プロンプトにより生成されるグラフダイアログの一実施の形態の図である。
【図８】図８は、Reformat（再フォーマット）プロンプトにより生成されるグラフダイアログの一実施の形態の図である。
【図９Ａ】図９Ａは、マージ結合成分がファイルＡおよびＢからのデータを結合し、その結果を出力ファイルへ出力する第１グラフのブロック図である。
【図９Ｂ】図９Ｂは、ロールアップ成分がファイルＡからのデータを集約し、その結果を出力ファイルへ出力する第２グラフのブロック図である。
【図９Ｃ】図９Ｃは、マージ成分が、ファイルＡおよびＢからのデータを結合し、ロールアップ成分が、得られたデータを集約し、最終結果を出力ファイルへ出力するグラフのブロック図である。
【図１０】図１０は、Condition-interpretation（条件解釈）制御を有するCondition（条件）を表すグラフダイアログの一実施の形態の図である。
【図１１】図１１は、汚染（poison）が発生する状況を示すグラフの図である。
【図１２】図１２は、Remove Completely（完全削除）条件付き成分を含むグラフのランタイム準備のプロセスを要約するフローチャートである。
【図１３】図１３は、本発明の特定実施の形態に対するReplace With Flow（フローで置換）条件付き成分を含むグラフのランタイム準備のプロセスを要約するフローチャートである。
【図１４】図１４は、ランタイムパラメータがないロールアップアプリケーションを表すグラフの図である。
【図１５】図１５は、図１４のロールアップアプリケーションのランタイムパラメータ化バージョンを表すグラフの図である。
【図１６】図１６は、図１５の例示のアプリケーションに対するランタイムパラメーターグリッドを表すグラフダイアログの一実施の形態の図である。
【図１７Ａ】図１７Ａは、図１６のパラメーターグリッド内の情報からウェブインターフェースにより生成される入力フォームを表すグラフダイアログの一実施の形態の図である。
【図１７Ｂ】図１７Ｂは、ユーザがパラメータ値を記入した図１７Ａの入力フォームの図である。
【図１８】図１８は、ランタイムパラメータ化したロールアップおよび結合アプリケーションを表すグラフの図である。
【図１９】図１９は、図１８の例示のアプリケーションに対するランタイムパラメーターグリッドを表すグラフダイアログの一実施の形態の図である。
【図２０】図２０は、図１９のパラメーターグリッド内の情報からウェブインターフェースにより生成される入力フォームを表すグラフダイアログの一実施の形態の図である。
【図２１】図２１は、ランタイムパラメータ化したロールアップ−結合−ソートアプリケーションを表すグラフの図である。
【図２２】図２２は、図２１に示すアプリケーション例に対するランタイムパラメーターグリッドを表すグラフダイアログの一実施の形態の図である。
【図２３Ａ】図２３Ａは、メタデータが伝搬されるグラフの図である。
【図２３Ｂ】図２３Ｂは、図２３Ａのグラフ内の成分に対するサブグラフの図である。
【図２４】図２４は、メタデータ伝搬プロセスのフローチャートである。
【図２５Ａ】図２５Ａは、成分内および成分間の従属関係を有するパラメータを含むグラフである。
【図２５Ｂ】図２５Ｂは、図２５Ａのグラフのパラメータ間の従属関係を表す従属関係グラフである。
【図２５Ｃ】図２５Ｃは、図２５Ａのグラフのパラメータ間の従属関係を表す従属関係グラフである。
【図２６】図２６は、修正トポロジのソートプロセスの図である。  各図面の同一符号は同一要素を表す。
【図１Ａ】
2008547134.tif 000016
【図１Ｂ】
2008547134.tif 000017
【図２】
2008547134.tif 000018
【図３】
2008547134.tif 000019
【図４】
2008547134.tif 000020
【図５】
2008547134.tif 000021
【図６】
2008547134.tif 000022
【図７】
2008547134.tif 000023
【図８】
2008547134.tif 000024
【図９Ａ】
2008547134.tif 000025
【図９Ｂ】
2008547134.tif 000026
【図９Ｃ】
2008547134.tif 000027
【図１０】
2008547134.tif 000028
【図１１】
2008547134.tif 000029
【図１２】
2008547134.tif 000030
【図１３】
2008547134.tif 000031
【図１４】
2008547134.tif 000032
【図１５】
2008547134.tif 000033
【図１６】
2008547134.tif 000034
【図１７Ａ】
2008547134.tif 000035
【図１７Ｂ】
2008547134.tif 000036
【図１８】
2008547134.tif 000037
【図１９】
2008547134.tif 000038
【図２０】
2008547134.tif 000039
【図２１】
2008547134.tif 000040
【図２２】
2008547134.tif 000041
【図２３Ａ】
2008547134.tif 000042
【図２３Ｂ】
2008547134.tif 000043
【図２４】
2008547134.tif 000044
【図２５Ａ】
2008547134.tif 000045
【図２５Ｂ】
2008547134.tif 000046
【図２５Ｃ】
2008547134.tif 000047
【図２６】
2008547134.tif 000048