(57)【要約】  ベースグラフに基づいて更新されたグラフを生成する方法は、ベースグラフ、各ソースグラフ、及びターゲットグラフ間納佐を識別することを含む。各グラフの仕様は、データを処理する演算を定義するデータ処理コンポーネントを表すノードと、データのフローを表すリンクとを定義する。識別することは、ベースグラフ及びソースグラフの仕様を比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別する、比較することと、ベースグラフとターゲットグラフとの仕様を比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別する、比較することとを含む。方法は、第１の組における差分と第２の組における差分との間の対応性を特徴付けることと、対応性及び第１の組の差分及び第２の組の差分に基づいて１組の結合差分を特定することと、ベースグラフ及び１組の結合差分に基づいて更新されたグラフを生成することとを含む。
2021527249.tif 000002
【特許請求の範囲】
【請求項１】
ベースグラフに基づいて更新データフローグラフを生成する方法であって、
第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別することであって、
前記第１のデータフローグラフは前記ベースグラフを含み、前記第２のデータフローグラフはソースグラフを含み、前記第３のデータフローグラフはターゲットグラフを含み、前記データフローグラフのそれぞれの仕様はノードを定義し、前記ノードの少なくとも１つは、データ処理コンポーネントに提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクは前記ノードを接続し、それぞれがデータのフローを表し、
前記識別することは、
前記ベースグラフの仕様と前記ソースグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ソースグラフとの間の第１の組の差分を識別し、前記第１の組の差分は、第１の削除ノード、第１の削除リンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較すること、及び
前記ベースグラフの仕様と前記ターゲットグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ターゲットグラフとの間の第２の組の差分を識別し、前記第２の組の差分は、第２の削除ノード、第２の削除リンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較すること
を含む、識別することと、
前記第１の組の差分における差分と前記第２の組の差分における差分との間の対応性を特徴付けることであって、（ｉ）前記第２の組の差分において識別されるノード若しくはリンクに対応する前記第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）前記第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない前記第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）前記第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない前記第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、特徴付けることと、
前記特徴付けられた対応性、前記ベースグラフと前記ソースグラフとの間の前記第１の組の差分、及び前記ベースグラフと前記ターゲットグラフとの間の前記第２の組の差分に基づいて１組の結合差分を特定することと、
前記ベースグラフ及び前記１組の結合差分に基づいて前記更新データフローグラフを生成することと、
を含む方法。
【請求項２】
前記ソースグラフ、前記ベースグラフ、前記ターゲットグラフ、及び前記更新データフローグラフは、実行可能データフローグラフである、請求項１に記載の方法。
【請求項３】
前記ソースグラフは、前記ベースグラフの第１の変更バージョンであり、前記ターゲットグラフは、前記ベースグラフの第２の変更バージョンである、請求項１又は２に記載の方法。
【請求項４】
前記第１の組の差分及び前記第２の組の差分を生成することを含み、各組の差分は、組中の各差分について、
前記差分のタイプを識別する情報及び
（ｉ）前記差分に関連する１つ又は複数のノードを示す情報又は（ｉｉ）前記差分に関連する１つ又は複数のリンクを示す情報の１つ又は複数
を含む、請求項１〜３の何れか１項に記載の方法。
【請求項５】
前記差分の前記タイプは、削除、追加、又は変更の１つ又は複数を含む、請求項４に記載の方法。
【請求項６】
前記差分に関連する１つ又は複数のノードを示す情報は、（ｉ）削除、追加、又は変更されたノードを識別する情報と、（ｉｉ）前記削除、追加、又は変更されたノードの上流にあるノードを識別する情報及び（ｉｉｉ）前記削除、追加、又は変更されたノードの下流にあるノードを識別する情報の１つ又は複数とを含む、請求項４又は５に記載の方法。
【請求項７】
前記差分に関連する１つ又は複数のリンクを示す情報は、（ｉ）追加されたリンクを識別する情報及び（ｉｉ）削除されたリンクを識別する情報の１つ又は複数を含む、請求項４〜６の何れか１項に記載の方法。
【請求項８】
前記１組の結合差分を生成することは、前記１組の結合差分に、前記第２の組の差分において識別されるいかなるノード又はリンクにも対応しない前記第１の組の差分において識別されるノード又はリンクを示す情報を含むことを含む、請求項１〜７の何れか１項に記載の方法。
【請求項９】
前記１組の結合差分を生成することは、前記１組の結合差分に、前記第１の組の差分において識別されるいかなるノード又はリンクにも対応しない前記第２の組の差分において識別されるノード又はリンクを示す情報を含むことを含む、請求項１〜８の何れか１項に記載の方法。
【請求項１０】
前記第１の組の差分において識別されるノード又はリンクと前記第２の組の差分において識別される対応するノード又はリンクとの互換性を特定することを含む、請求項１〜９の何れか１項に記載の方法。
【請求項１１】
前記第１の組の差分において識別されるノード又はリンクは、第１の変更ノード又はリンクを含み、前記第２の組の差分において識別されるノード又はリンクは、第２の変更ノード又はリンクを含み、
互換性を特定することは、
前記第１の変更ノード又はリンクに関連する変更が前記第２の変更ノード又はリンクに関連する変更と互換性を有すると判断することと、
前記１組の結合差分に、前記第１の組の差分において識別される前記ノード又はリンク及び前記第２の組の差分において識別される前記ノード又はリンクの両方を示す情報を含むことと、
を含む、請求項１０に記載の方法。
【請求項１２】
前記第１の組の差分において識別されるノード又はリンクは、第１の変更ノード又はリンクを含み、前記第２の組の差分において識別されるノード又はリンクは、第２の変更ノード又はリンクを含み、
互換性を特定することは、
前記第１の変更ノード又はリンクに関連する変更が前記第２の変更ノード又はリンクに関連する変更と互換性を有すると判断することと、
前記第１の変更ノード若しくはリンク、前記第２の変更ノード若しくはリンクを選択するか、又はいずれも選択しないことと、
前記１組の結合差分に前記選択されたノード又はリンクを示す情報を含めることと、
を含む、請求項１０又は１１に記載の方法。
【請求項１３】
前記１組の結合差分を特定することは、
対応すると判断された差分対について、前記差分が互換性を有すると判断することと、
前記１組の結合差分に前記対の両方の差分を示す情報を含めることと、
を含む、請求項１〜１２の何れか１項に記載の方法。
【請求項１４】
前記１組の結合差分を特定することは、
対応すると判断された差分対について、前記差分が競合すると判断することと、
前記対の前記差分の一方を選択することと、
前記１組の結合差分に前記選択された差分を示す情報を含めることと、
を含む、請求項１〜１３の何れか１項に記載の方法。
【請求項１５】
選択基準に基づいて前記差分の一方を選択することを含む、請求項１４に記載の方法。
【請求項１６】
前記対の前記両方の差分を示す情報をユーザインターフェースに提示することと、
ユーザ入力に基づいて前記差分の一方を選択することと、
を含む、請求項１４又は１５に記載の方法。
【請求項１７】
前記更新データフローグラフを生成することは、
前記ベースグラフのコピーを生成することと、
前記１組の結合差分における各差分を前記コピーに適用することと、
を含む、請求項１〜１６の何れか１項に記載の方法。
【請求項１８】
前記ベースグラフの仕様と前記ソースグラフの仕様とを比較することは、前記ベースグラフと前記ソースグラフとの間の対応性を特定することを含む、請求項１〜１７の何れか１項に記載の方法。
【請求項１９】
前記ベースグラフと前記ソースグラフとの間の対応性を特定することは、（１）前記ソースグラフのノード又はリンクに対応する前記ベースグラフの第１のノード又はリンクを識別すること、（２）前記ソースグラフのいずれのノードにも対応しない前記ベースグラフの第２のノード又はリンクを識別すること、及び（３）前記ベースグラフのいずれのノード又はリンクにも対応しない前記ソースグラフの第３のノード又はリンクを識別することの１つ又は複数を含む、請求項１８に記載の方法。
【請求項２０】
前記ベースグラフと前記ソースグラフとの間の第１の組の差分を識別することは、前記ベースグラフの前記第１のノード又はリンクと前記ソースグラフの前記対応するノード又はリンクとの間の差分を識別することを含む、請求項１９に記載の方法。
【請求項２１】
前記第１のノード又はリンクと前記ソースグラフの前記対応するノード又はリンクとの間の差分を識別することは、前記第１のノード又はリンクのパラメータ及びパラメータの表現の１つ又は複数と前記対応する第１のノード又はリンクのパラメータ又はパラメータの表現との間の差分を識別することを含む、請求項２０に記載の方法。
【請求項２２】
前記ベースグラフはベースサブグラフを含み、前記ソースグラフは第１のサブグラフを含み、前記方法は、
前記ベースサブグラフの仕様と前記第１のサブグラフの仕様とを比較して、前記ベースサブグラフと前記第１のサブグラフとの間の１つ又は複数の差分を識別すること
を含む、請求項１〜２１の何れか１項に記載の方法。
【請求項２３】
前記第１のデータフローグラフは前記ベースグラフであり、前記第２のデータフローグラフは前記ソースグラフであり、前記第３のデータフローグラフは前記ターゲットグラフである、請求項１〜２２の何れか１項に記載の方法。
【請求項２４】
前記リンクはノード間のデータのフローを表す、請求項１〜２３の何れか１項に記載の方法。
【請求項２５】
前記リンクは、ノード間の制御信号のフローを表す、請求項１〜２４の何れか１項に記載の方法。
【請求項２６】
前記ベースグラフ、前記ソースグラフ、及び前記ターゲットグラフはデータ処理グラフを含む、請求項１〜２５の何れか１項に記載の方法。
【請求項２７】
前記ベースグラフ、前記ソースグラフ、及び前記ターゲットグラフは制御グラフを含む、請求項１〜２６の何れか１項に記載の方法。
【請求項２８】
前記ベースグラフ、前記ソースグラフ、及び前記ターゲットグラフはプランを含む、請求項１〜２７の何れか１項に記載の方法。
【請求項２９】
前記差分間の前記対応性を特定することは、
（１）前記第１の組の差分及び前記第２の組の差分の一方のみで識別されるノード又はリンクが関わる差分及び（２）前記第１の組の差分及び前記第２の組の差分の両方において識別されるノード又はリンクが関わる差分を識別することを含む、請求項１〜２８の何れか１項に記載の方法。
【請求項３０】
前記１組の結合差分を特定することは、
前記第１の組の差分及び前記第２の組の差分の一方のみで識別されるノード又はリンクが関わる差分の前記第１の組の差分及び前記第２の組の差分のそれぞれについて、その差分を示す情報が前記１組の結合差分に追加されることと、
前記第１の組の差分及び前記第２の組の差分の両方において識別されるノード又はリンクが関わる差分の前記第１の組の差分及び前記第２の組の差分のそれぞれについて、互換性分析が実行されることと、
を含む、請求項１〜２９の何れか１項に記載の方法。
【請求項３１】
前記互換性分析を実行することは、
第１の差分が第２の差分と競合するか否かを判断することであって、競合する差分対は、前記競合する差分対の一方の前記ベース実行可能グラフへの適用が、前記競合する差分対の他方の前記ベース実行可能グラフへの適用を妨げる場合、競合する、判断することを含む、請求項３０に記載の方法。
【請求項３２】
任意の競合する差分対の場合、選択基準に従って前記競合する差分対の一方を選択することにより、前記競合する差分対の競合を解決することと、
前記選択された差分を示す情報を前記１組の結合差分追加することと、
を含む、請求項３１に記載の方法。
【請求項３３】
グラフィカルユーザインターフェースを提供することと、
前記グラフィカルユーザインターフェースを介して、前記競合する差分対を視覚的に表す情報を表示することと、
を含む、請求項３１又は３２に記載の方法。
【請求項３４】
前記グラフィカルユーザインターフェースを介して、前記競合する差分対から選択された１つ又は複数の差分の１つ又は複数の視覚的表現及びそれぞれの前記選択から生じる前記更新データフローグラフのそれぞれの視覚的表現を表示することを含む、請求項３３に記載の方法。
【請求項３５】
ユーザから前記グラフィカルユーザインターフェースを介して、前記視覚的表現の１つの選択、示唆される１つ又は複数の選択を含む入力を受信することであって、前記選択基準は前記入力により定義される、受信することを含む、請求項３４に記載の方法。
【請求項３６】
計算システムに、ベースグラフに基づいて更新データフローグラフを生成させる命令を記憶する非一時的コンピュータ可読媒体であって、前記命令は前記計算システムに、
第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別することであって、前記第１のデータフローグラフは前記ベースグラフを含み、前記第２のデータフローグラフはソースグラフを含み、前記第３のデータフローグラフはターゲットグラフを含み、
前記データフローグラフのそれぞれの仕様はノードを定義し、前記ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクは前記ノードを接続し、各リンクはデータのフローを表し、
前記識別することは、
前記ベースグラフの仕様と前記ソースグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ソースグラフとの間の第１の組の差分を識別し、前記第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較すること、及び
前記ベースグラフの仕様と前記ターゲットグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ターゲットグラフとの間の第２の組の差分を識別し、前記第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較すること
を含む、識別することと、
前記第１の組の差分における差分と前記第２の組の差分における差分との間の対応性を特徴付けることであって、（ｉ）前記第２の組の差分において識別されるノード若しくはリンクに対応する前記第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）前記第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない前記第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）前記第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない前記第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、特徴付けることと、
前記特徴付けられた対応性、前記ベースグラフと前記ソースグラフとの間の前記第１の組の差分、及び前記ベースグラフと前記ターゲットグラフとの間の前記第２の組の差分に基づいて１組の結合差分を特定することと、
前記ベースグラフ及び前記１組の結合差分に基づいて前記更新データフローグラフを生成することと、
を行わせる命令を含む、非一時的コンピュータ可読媒体。
【請求項３７】
ベースグラフに基づいて更新データフローグラフを生成する計算システムであって、
メモリに結合される１つ又は複数のプロセッサ
を含み、前記１つ又は複数のプロセッサ及び前記メモリは、
第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別することであって、前記第１のデータフローグラフは前記ベースグラフを含み、前記第２のデータフローグラフはソースグラフを含み、前記第３のデータフローグラフはターゲットグラフを含み、
前記データフローグラフのそれぞれの仕様はノードを定義し、前記ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクは前記ノードを接続し、データのフローを表し、
前記識別することは、
前記ベースグラフの仕様と前記ソースグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ソースグラフとの間の第１の組の差分を識別し、前記第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較すること、及び
前記ベースグラフの仕様と前記ターゲットグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ターゲットグラフとの間の第２の組の差分を識別し、前記第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較すること
を含む、識別することと、
前記第１の組の差分における差分と前記第２の組の差分における差分との間の対応性を特徴付けることであって、（ｉ）前記第２の組の差分において識別されるノード若しくはリンクに対応する前記第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）前記第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない前記第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）前記第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない前記第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、特徴付けることと、
前記特徴付けられた対応性、前記ベースグラフと前記ソースグラフとの間の前記第１の組の差分、及び前記ベースグラフと前記ターゲットグラフとの間の前記第２の組の差分に基づいて１組の結合差分を特定することと、
前記ベースグラフ及び前記１組の結合差分に基づいて前記更新データフローグラフを生成することと、
を行うように構成される、計算システム。
【請求項３８】
ベースグラフに基づいて更新データフローグラフを生成する計算システムであって、
第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別する手段であって、前記第１のデータフローグラフは前記ベースグラフを含み、前記第２のデータフローグラフはソースグラフを含み、前記第３のデータフローグラフはターゲットグラフを含み、
前記データフローグラフのそれぞれの仕様はノードを定義し、前記ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクは前記ノードを接続し、データのフローを表し、
前記識別することは、
前記ベースグラフの仕様と前記ソースグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ソースグラフとの間の第１の組の差分を識別し、前記第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較すること、及び
前記ベースグラフの仕様と前記ターゲットグラフの仕様とを比較することであって、それにより、前記ベースグラフと前記ターゲットグラフとの間の第２の組の差分を識別し、前記第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較すること
を含む、識別する手段と、
前記第１の組の差分における差分と前記第２の組の差分における差分との間の対応性を特徴付ける手段であって、（ｉ）前記第２の組の差分において識別されるノード若しくはリンクに対応する前記第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）前記第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない前記第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）前記第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない前記第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、特徴付ける手段と、
前記特徴付けられた対応性、前記ベースグラフと前記ソースグラフとの間の前記第１の組の差分、及び前記ベースグラフと前記ターゲットグラフとの間の前記第２の組の差分に基づいて１組の結合差分を特定する手段と、
前記ベースグラフ及び前記１組の結合差分に基づいて前記更新データフローグラフを生成する手段と、
を含む、計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権の主張
本願は、２０１８年６月６日付けで出願された米国特許出願第６２／６８１，３９５号明細書及び２０１８年１０月５日付けで出願された米国特許出願第１６／１５３，３２０号明細書の優先権を主張するものであり、これら両特許出願の内容は全体的に、参照により本明細書に援用される。
【背景技術】
【０００２】
コンピュータプログラムの開発又は実行中、コンピュータプログラムに変更を行うことができる。時に、ある開発者又はある開発者チームが、別の開発者又は別の開発者チームによって行われた変更から独立してコンピュータプログラムに変更を行うことがある。
【発明の概要】
【課題を解決するための手段】
【０００３】
一態様では、ベースグラフに基づいて更新データフローグラフを生成する方法は、第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別することを含む。第１のデータフローグラフはベースグラフを含み、第２のデータフローグラフはソースグラフを含み、第３のデータフローグラフはターゲットグラフを含む。データフローグラフのそれぞれの仕様はノードを定義し、ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクはノードを接続し、各リンクはデータのフローを表す。識別することは、ベースグラフの仕様とソースグラフの仕様とを比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別し、第１の組の差分は、第１の削除ノード、第１の削除リンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較することと、ベースグラフの仕様とターゲットグラフの仕様とを比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別し、第２の組の差分は、第２の削除ノード、第２の削除リンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較することを含む。本方法は、第１の組の差分における差分と第２の組の差分における差分との間の対応性を特徴付けることであって、（ｉ）第２の組の差分において識別されるノード若しくはリンクに対応する第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、特徴付けることを含む。本方法は、特徴付けられた対応性、ベースグラフとソースグラフとの間の第１の組の差分、及びベースグラフとターゲットグラフとの間の第２の組の差分に基づいて１組の結合差分を特定することを含む。本方法は、ベースグラフ及び１組の結合差分に基づいて更新データフローグラフを生成することを含む。
【０００４】
実施形態は以下の特徴の１つ又は複数を含むことができる。
【０００５】
第１の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、ソースグラフ、ベースグラフ、ターゲットグラフ、及び更新データフローグラフは、実行可能データフローグラフである。
【０００６】
第２の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、ソースグラフは、ベースグラフの第１の変更バージョンであり、ターゲットグラフは、ベースグラフの第２の変更バージョンである。
【０００７】
第３の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、本方法は、第１の組の差分及び第２の組の差分を生成することを含む。各組の差分は、組中の各差分について、差分のタイプを識別する情報及び（ｉ）差分に関連する１つ又は複数のノードを示す情報又は（ｉｉ）差分に関連する１つ又は複数のリンクを示す情報の１つ又は複数を含む。
【０００８】
第４の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、差分のタイプは、削除、追加、又は変更の１つ又は複数を含む。
【０００９】
第５の特徴において、第３又は第４の特徴と組み合わせて、差分に関連する１つ又は複数のノードを示す情報は、（ｉ）削除、追加、又は変更されたノードを識別する情報と、（ｉｉ）削除、追加、又は変更されたノードの上流にあるノードを識別する情報及び（ｉｉｉ）削除、追加、又は変更されたノードの下流にあるノードを識別する情報の１つ又は複数とを含む。
【００１０】
第６の特徴において、第３〜第６の特徴の何れか１つと組み合わせて、差分に関連する１つ又は複数のノードを示す情報は、（ｉ）追加されたリンクを識別する情報及び（ｉｉ）削除されたリンクを識別する情報の１つ又は複数を含む。
【００１１】
第７の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、１組の結合差分を生成することは、１組の結合差分に、第２の組の差分において識別されるいかなるノード又はリンクにも対応しない第１の組の差分において識別されるノード又はリンクを示す情報を含むことを含む。
【００１２】
第８の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、本方法は含む１組の結合差分を生成することは、１組の結合差分に、第１の組の差分において識別されるいかなるノード又はリンクにも対応しない第２の組の差分において識別されるノード又はリンクを示す情報を含むことを含む。
【００１３】
第９の特徴において、先の特徴の任意の１つ又は複数と組み合わせて、本方法は、第１の組の差分において識別されるノード又はリンクと第２の組の差分において識別される対応するノード又はリンクとの互換性を特定することを含む。
【００１４】
第１０の特徴において、第９の特徴と組み合わせて、第１の組の差分において識別されるノード又はリンクは、第１の変更ノード又はリンクを含み、第２の組の差分において識別されるノード又はリンクは、第２の変更ノード又はリンクを含む。互換性を特定することは、第１の変更ノード又はリンクに関連する変更が第２の変更ノード又はリンクに関連する変更と互換性を有すると判断することと、１組の結合差分に、第１の組の差分において識別されるノード又はリンク及び第２の組の差分において識別されるノード又はリンクの両方を示す情報を含むこととを含む。
【００１５】
第１１の特徴において、第９又は第１０の特徴と組み合わせて、第１の組において識別されるノード又はリンクは、第１の変更ノード又はリンクを含み、第２の組の差分において識別されるノード又はリンクは、第２の変更ノード又はリンクを含む。互換性を特定することは、第１の変更ノード又はリンクに関連する変更が第２の変更ノード又はリンクに関連する変更と互換性を有すると判断することと、第１の変更ノード若しくはリンク、第２の変更ノード若しくはリンクを選択するか、又はいずれも選択しないことと、１組の結合差分に選択されたノード又はリンクを示す情報を含めることとを含む。
【００１６】
第１２の特徴において、先の任意の特徴と組み合わせて、１組の結合差分を特定することは、対応すると判断された差分対について、差分が互換性を有すると判断することと、１組の結合差分に対の両方の差分を示す情報を含めることとを含む。
【００１７】
第１３の特徴において、先の任意の特徴と組み合わせて、１組の結合差分を特定することは、対応すると判断された差分対について、差分が競合すると判断することと、対の差分の一方を選択することと、１組の結合差分に選択された差分を示す情報を含めることとを含む。
【００１８】
第１４の特徴において、第１３の特徴と組み合わせて、本方法は、選択基準に基づいて差分の一方を選択することを含む。
【００１９】
第１５の特徴において、先の任意の特徴と組み合わせて、本方法は、対の両方の差分を示す情報をユーザインターフェースに提示することと、ユーザ入力に基づいて差分の一方を選択することとを含む。
【００２０】
第１６の特徴において、先の任意の特徴と組み合わせて、更新データフローグラフを生成することは、ベースグラフのコピーを生成することと、１組の結合差分における各差分をコピーに適用することとを含む。
【００２１】
第１７の特徴において、先の任意の特徴と組み合わせて、ベースグラフの仕様とソースグラフの仕様とを比較することは、ベースグラフとソースグラフとの間の対応性を特定することを含む。
【００２２】
第１８の特徴において、第１７の特徴と組み合わせて、ベースグラフとソースグラフとの間の対応性を特定することは、（１）ソースグラフのノード又はリンクに対応するベースグラフの第１のノード又はリンクを識別すること、（２）ソースグラフのいずれのノードにも対応しないベースグラフの第２のノード又はリンクを識別すること、及び（３）ベースグラフのいずれのノード又はリンクにも対応しないソースグラフの第３のノード又はリンクを識別することの１つ又は複数を含む。
【００２３】
第１９の特徴において、第１８の特徴と組み合わせて、ベースグラフとソースグラフとの間の第１の組の差分を識別することは、ベースグラフの第１のノード又はリンクとソースグラフの対応するノード又はリンクとの間の差分を識別することを含む。
【００２４】
第２０の特徴において、第１９の特徴と組み合わせて、第１のノード又はリンクとソースグラフの対応するノード又はリンクとの間の差分を識別することは、第１のノード又はリンクのパラメータ及びパラメータの表現の１つ又は複数と対応する第１のノード又はリンクのパラメータ又はパラメータの表現との間の差分を識別することを含む。
【００２５】
第２１の特徴において、先の任意の特徴と組み合わせて、ベースグラフはベースサブグラフを含み、ソースグラフは第１のサブグラフを含む。本方法は、ベースサブグラフの仕様と第１のサブグラフの仕様とを比較して、ベースサブグラフと第１のサブグラフとの間の１つ又は複数の差分を識別することを含む。
【００２６】
第２２の特徴において、先の任意の特徴と組み合わせて、第１のデータフローグラフはベースグラフであり、第２のデータフローグラフはソースグラフであり、第３のデータフローグラフはターゲットグラフである。
【００２７】
第２３の特徴において、先の任意の特徴と組み合わせて、リンクはノード間のデータのフローを表す。
【００２８】
第２４の特徴において、先の任意の特徴と組み合わせて、リンクは、ノード間の制御信号のフローを表す。
【００２９】
第２５の特徴において、先の任意の特徴と組み合わせて、ベースグラフ、ソースグラフ、及びターゲットグラフはデータ処理グラフを含む。
【００３０】
第２６の特徴において、先の任意の特徴と組み合わせて、ベースグラフ、ソースグラフ、及びターゲットグラフは制御グラフを含む。
【００３１】
第２７の特徴において、先の任意の特徴と組み合わせて、ベースグラフ、ソースグラフ、及びターゲットグラフはプランを含む。
【００３２】
第２８の特徴において、先の任意の特徴と組み合わせて、差分間の対応性を特定することは、（１）第１の組の差分及び第２の組の差分の一方のみで識別されるノード又はリンクが関わる差分及び（２）第１の組の差分及び第２の組の差分の両方において識別されるノード又はリンクが関わる差分を識別することを含む。
【００３３】
第２９の特徴において、先の任意の特徴と組み合わせて、１組の結合差分を特定することは、第１の組の差分及び第２の組の差分の一方のみで識別されるノード又はリンクが関わる差分の第１の組の差分及び第２の組の差分のそれぞれについて、その差分が１組の結合差分に追加されることを示す情報と、第１の組の差分及び第２の組の差分の両方において識別されるノード又はリンクが関わる差分の第１の組の差分及び第２の組の差分のそれぞれについて、互換性分析が実行されることとを含む。
【００３４】
第３０の特徴において、第２９の特徴と組み合わせて、互換性分析を実行することは、第１の差分が第２の差分と競合するか否かを判断することであって、競合する差分対は、競合する差分対の一方のベース実行可能グラフへの適用が、競合する差分対の他方のベース実行可能グラフへの適用を妨げる場合、競合する、判断することを含む。
【００３５】
第３１の特徴において、第３０の特徴と組み合わせて、本方法は、任意の競合する差分対の場合、選択基準に従って競合する差分対の一方を選択することにより、競合する差分対の競合を解決することと、選択された差分を示す情報を１組の結合差分追加することとを含む。
【００３６】
第３２の特徴において、第３０又は第３１の特徴と組み合わせて、本方法は、グラフィカルユーザインターフェースを提供することと、グラフィカルユーザインターフェースを介して、競合する差分対を視覚的に表す情報を表示することとを含む。
【００３７】
第３３の特徴において、第３２の特徴と組み合わせて、本方法は、グラフィカルユーザインターフェースを介して、競合する差分対から選択された１つ又は複数の差分の１つ又は複数の視覚的表現及び選択から生じる更新データフローグラフのそれぞれの視覚的表現を表示することを含む。
【００３８】
第３４の特徴において、第３３の特徴と組み合わせて、本方法は、ユーザからグラフィカルユーザインターフェースを介して、視覚的表現の１つの選択、示唆される１つ又は複数の選択を含む入力を受信することであって、選択基準は入力により定義される、受信することを含む。
【００３９】
一態様では、非一時的コンピュータ可読媒体は、計算システムに、ベースグラフに基づいて更新データフローグラフを生成させる命令を記憶する。命令は、第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を計算システムに識別させる命令を含み、第１のデータフローグラフはベースグラフを含み、第２のデータフローグラフはソースグラフを含み、第３のデータフローグラフはターゲットグラフを含む。データフローグラフのそれぞれの仕様はノードを定義し、ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクはノードを接続し、各リンクはデータのフローを表す。識別することは、ベースグラフの仕様とソースグラフの仕様とを比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別し、第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較することと、ベースグラフの仕様とターゲットグラフの仕様とを比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別し、第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較することを含む。命令は、計算システムに、第１の組の差分における差分と第２の組の差分における差分との間の対応性を特徴付けさせる命令であって、（ｉ）第２の組の差分において識別されるノード若しくはリンクに対応する第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む、計算システムに特徴付けさせる命令を含む。命令は、特徴付けられた対応性、ベースグラフとソースグラフとの間の第１の組の差分、及びベースグラフとターゲットグラフとの間の第２の組の差分に基づいて１組の結合差分を計算システムに特定させる命令と、ベースグラフ及び１組の結合差分に基づいて更新データフローグラフを計算システムに生成させる命令とを含む。
【００４０】
一態様では、ベースグラフに基づいて更新データフローグラフを生成する計算システムは、メモリに結合される１つ又は複数のプロセッサを含む。１つ又は複数のプロセッサ及びメモリは、第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別するように構成され、第１のデータフローグラフはベースグラフを含み、第２のデータフローグラフはソースグラフを含み、第３のデータフローグラフはターゲットグラフを含む。データフローグラフのそれぞれの仕様はノードを定義し、ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクはノードを接続し、データのフローを表す。識別することは、ベースグラフの仕様とソースグラフの仕様とを比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別し、第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較することと、ベースグラフの仕様とターゲットグラフの仕様とを比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別し、第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較することを含む。１つ又は複数のプロセッサ及びメモリは、第１の組の差分における差分と第２の組の差分における差分との間の対応性を特徴付けるように構成され、特徴付けることは、（ｉ）第２の組の差分において識別されるノード若しくはリンクに対応する第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む。１つ又は複数のプロセッサ及びメモリは、特徴付けられた対応性、ベースグラフとソースグラフとの間の第１の組の差分、及びベースグラフとターゲットグラフとの間の第２の組の差分に基づいて１組の結合差分を特定することと、ベースグラフ及び１組の結合差分に基づいて更新データフローグラフを生成することとを行うように構成される。
【００４１】
一態様では、ベースグラフに基づいて更新データフローグラフを生成する計算システムは、第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分を識別する手段を含み、第１のデータフローグラフはベースグラフを含み、第２のデータフローグラフはソースグラフを含み、第３のデータフローグラフはターゲットグラフを含む。データフローグラフのそれぞれの仕様はノードを定義し、ノードの少なくとも１つは、提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表し、１つ又は複数のリンクはノードを接続し、データのフローを表す。識別することは、ベースグラフの仕様とソースグラフの仕様とを比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別し、第１の組の差分は、プラン第１の削除されたノード、第１の削除されたリンク、第１の追加ノード、第１の追加リンク、第１の変更ノード、又は第１の変更リンクの１つ又は複数を示す情報を含む、比較することと、ベースグラフの仕様とターゲットグラフの仕様とを比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別し、第２の組の差分は、第２の削除されたノード、第２の削除されたリンク、第２の追加ノード、第２の追加リンク、第２の変更ノード、又は第２の変更リンクの１つ又は複数を示す情報を含む、比較することを含む。本計算システムは、第１の組の差分における差分と第２の組の差分における差分との間の対応性を特徴付ける手段を含み、特徴付けることは、（ｉ）第２の組の差分において識別されるノード若しくはリンクに対応する第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む。本計算システムは、特徴付けられた対応性、ベースグラフとソースグラフとの間の第１の組の差分、及びベースグラフとターゲットグラフとの間の第２の組の差分に基づいて１組の結合差分を特定する手段を含む。本計算システムは、ベースグラフ及び１組の結合差分に基づいて更新データフローグラフを生成する手段を含む。
【００４２】
本明細書に記載される手法は、データフローグラフ（すなわち、コンピュータプログラム）の複数のバージョンを、各バージョンでの変更を反映した１つの更新データフローグラフに効率的且つ高信頼的に自動的に併合できるようにする。この自動化された併合は、例えば、複数のチームのそれぞれにより独立して実行されたコンピュータプログラムへの開発作業又はデバッグ作業を１つの更新されたコンピュータプログラムに効率的且つ高信頼的に結合するのに使用することができる。この効率的で高信頼的なバージョン管理は、ソフトウェア開発プロセス中、プログラム開発者を助け、したがって、この開発プロセスをもより効率的且つ精密にする。
【図面の簡単な説明】
【００４３】
【図１】データフローグラフの図表現である。
【図２Ａ】データフローグラフの図表現である。
【図２Ｂ】データフローグラフの図表現である。
【図２Ｃ】データフローグラフの図表現である。
【図３】システム図である。
【図４Ａ】データフローグラフの図表現である。
【図４Ｂ】データフローグラフの図表現である。
【図４Ｃ】データフローグラフの図表現である。
【図４Ｄ】データフローグラフの図表現である。
【図５Ａ】フローチャートである。
【図５Ｂ】フローチャートである。
【図６】スクリーンショットである。
【図７】スクリーンショットである。
【図８】スクリーンショットである。
【図９】スクリーンショットである。
【図１０】フローチャートである。
【図１１】データフローグラフを開発するデータ処理システムの図である。
【発明を実施するための形態】
【００４４】
本明細書において、コンピュータプログラムの複数のバージョンを１つの更新されたプログラムに結合する手法について説明する。例えば、データフローグラフ等のコンピュータプログラム、例えばデータ処理グラフ、制御グラフ、又はプランを開発又はデバッグする場合、複数の開発者又は複数の組の開発者はそれぞれ、独立してコンピュータプログラムに対して作業し得る。その結果として、コンピュータプログラムの複数の変更されたバージョンが生成され得る。ベースコンピュータプログラムと、ベースコンピュータプログラムのこれらの変更された各バージョンとの間の差分を識別し、全ての差分の完全な組をベースコンピュータプログラムに適用して、ベースコンピュータプログラムの変更された各バージョンで行われた変更を反映した１つの更新されたコンピュータプログラムを生成することができる。
【００４５】
データフローグラフは、データソース及びデータシンク等のデータ処理コンポーネント及びデータセットを示すノードを含むことができるコンピュータプログラムのグラフ表現である。データセットは、例えば、ファイル、データベーステーブル、又はグラフによる処理若しくはグラフによる処理されたデータの受信のためにデータ（例えば、データレコード）を提供することができる他のタイプのデータソース若しくはシンクであることができる。データ処理コンポーネント及びデータセットは時にまとめてグラフのノードと呼ばれる。グラフの２つのノードを結ぶリンクは、第１のノードと第２のノードとの間のデータ又は制御信号等の情報のフローを表す。そのようなデータフローグラフ（時にグラフと呼ばれる）は、データ処理グラフ、制御グラフ、又はプランであることができる。幾つかの例では、データフローグラフは、情報の処理を実行するために実行することが可能であることができる。幾つかの例では、データフローグラフは実行可能ではなく、例えばなお開発中又はデバッグ中であるコンピュータプログラムの表現であるデータフローグラフである。図１は、データを処理するように構成され、各リンク１４、２０により第１のノード１６にそれぞれ接続されたデータソース１２、１８を含むデータフローグラフ１０を示す。フィルタノード１６は、リンク２４、２８によりデータシンク２２、２６にそれぞれ接続される。
【００４６】
グラフのノードは、リンクを接続することができる入力ポート及び／又は出力ポートを有することができる。図１の例では、リンク１４、２０の上流端部は、対応するデータソース１２、１８の出力ポートに接続される。リンク２４の上流端部はフィルタノード１６の出力ポートに接続される。リンク１４、２０の下流端部は、フィルタノード１６の入力ポートに接続される。リンク２４、２８の下流端部は、対応するデータシンク２２、２６の入力ポートに接続される。
【００４７】
データ処理コンポーネントは、演算を実行して、データを処理又は操作する。ノードは、実行されると、データ処理コンポーネントの演算を実施するプログラミングコードにより定義されるオブジェクトであるデータ処理コンポーネント（例えば、ソフトウェアとハードウェアトの組合せ）の図表現である。データ処理コンポーネントの例には、マッピングコンポーネント、フィルタコンポーネント、重複排除コンポーネント、集計コンポーネント、複製コンポーネント、正規化コンポーネント、パーテーション及びソートコンポーネント、結合コンポーネント、又は他のタイプのデータ処理コンポーネントがある。幾つかの例では、データソースコンポーネント及びデータシンクコンポーネントはデータ処理コンポーネントと見なすことができる。データ処理コンポーネントの演算は、１つ又は複数のパラメータに関して定義することができる。パラメータは、データ処理コンポーネントのコードにより参照されるファイル（例えば、．ｄｍｌファイル）において定義することができる。例えば、ファイルは、データ処理コンポーネントに関連するパラメータの値又は式を含むことができる。グラフがインスタンス化される（例えば、実行時に）場合、パラメータの式は評価されて、時にパラメータの解決と呼ばれることもあるパラメータの値を取得する。パラメータの値又は式は、例えば、ユーザインターフェースを介してユーザにより（例えば、プロンプトに応答して）定義、ファイルから定義、又は同じコンテキスト若しくは異なるコンテキストでの別のパラメータに関して定義することができる。例えば、パラメータは、別のパラメータと「同じ」関係を有するようにパラメータを指定することにより、異なるコンテキスト（例えば、異なるコンポーネントのコンテキストで評価されるパラメータ）からエクスポートすることができる。図１の例では、フィルタノード１６及びその対応するコンポーネントは、関連するパラメータセット１５を有する。
【００４８】
初期の変更されていないデータフローグラフをベース実行可能グラフ又はベースグラフと呼ぶ。ベースグラフと比較して変更されたグラフの第１の変更バージョンをソース実行可能グラフ又はソースグラフと呼ぶ。ベースグラフと比較して変更されたグラフの第２の変更バージョンをターゲット実行可能グラフ又はターゲットグラフと呼ぶ。ソース実行可能グラフ及びターゲット実行可能グラフの両方からの変更を組み込んだグラフを更新データフローグラフと呼ぶ。
【００４９】
差分分析をソースグラフ及びターゲットグラフのそれぞれに実行されて、ベースグラフとソースグラフ及びターゲットグラフのそれぞれとの間の対応する１組の差分を識別する。差分分析の結果は複数の組の差分であり、各組の差分はベースグラフトソースグラフ及びターゲットグラフの一方との間の差分を示す。複数の組の差分は１つの組の結合差分に併合される。１組の結合差分はベースグラフに適用されて、更新グラフを生成する。これは、上述した効率的で高信頼的なバージョン管理の提供に寄与する。
【００５０】
一例では、図１のデータフローグラフ１０はベースグラフである。図２Ａ及び図２Ｂはソースグラフ３０及びターゲットグラフ４０をそれぞれ示す。差分分析をソースグラフ３０及びターゲットグラフ４０のそれぞれに実行して、ベースグラフ１０と各グラフ３０、４０との間の差分を識別する。第１のグラフ及び第２のグラフ（例えば、ベースグラフ１０及びソースグラフ３０）の差分分析は、ソースグラフ３０には存在するが、ベースグラフ１０には存在しないノード（追加ノードと呼ばれる）、ベースグラフ１０には存在するが、ソースグラフ３０には存在しない１つ又は複数のノード（削除ノードと呼ばれる）、及びベースグラフ１０及びソースグラフ３０の両方に存在するが、変更された１つ又は複数のノード（変更ノードと呼ばれる）を識別する。変更ノードは一般に、第１のグラフと第２のグラフとで同様であることができるが、更に後述するように、パラメータ、属性、又はノードに関連する他の特徴が変更されている。差分分析はまた、第１のグラフの１つ又は複数のリンクと第２のグラフの１つ又は複数のリンクとの間の差分を識別することもできる。差分分析の更なる説明を以下に提供する。
【００５１】
図２Ａ及び図２Ｂの例では、ソースグラフ３０への差分分析の結果、追加ノード３２、追加フロー３４、３５、３６、及び削除フロー１４、２０を識別する第１の組の差分が生成される。ターゲットグラフ４０への差分分析の結果、変更されたパラメータセット１５’を有する変更ノード１６、削除ノード２６、及び削除リンク２８を識別する第２の組の差分が生成される。
【００５２】
複数の組の差分は、より詳細に後述する１つの組の結合差分に結合される。図２Ａ及び図２Ｂの例では、１組の結合差分は、追加ノード３２、削除ノード２６、変更ノード１６、並びに追加フロー及び削除フローを識別する。図２Ｃも参照すると、１組の結合差分をベースグラフ１０（又はそのコピー）に適用して、更新グラフ５０を生成する。更新グラフ５０は、１組の結合差分に従って変更されたベースグラフ１０のノード及びリンクを含む。すなわち、ベースグラフと比較してソースグラフ及びターゲットグラフの何れか一方において追加されたノード及びリンクは、更新グラフにおいてベースグラフと比較して追加される（すなわち、生成される）。ベースグラフと比較してソースグラフ及びターゲットグラフの何れか一方において削除されたノード及びリンクは、更新グラフにおいてベースグラフと比較して削除される（すなわち、生成されない）。
【００５３】
図３を参照すると、グラフ更新システム３００は、ベースグラフ３０２とソースグラフ３０４及びターゲットグラフ３０６のそれぞれとの間の差分を識別し、ベースグラフ３０２と比較して両グラフ３０４、３０６において行われた変更を反映した１つの更新グラフ３５０を生成する。グラフ更新システム３００は、差分分析をソースグラフ３０４及びターゲットグラフ３０６のそれぞれに対して実行し、各グラフ３０４、３０６に対応する１組の差分３１２、３１４を出力する差分エンジン３１０を含む。各組の差分はベースグラフ３０２と対応するグラフ３０４、３０６との間の差分を識別する。グラフ更新システム３００はまた、複数の組の差分３１２、３１４を併合して１つの組の結合差分３２２にする併合エンジン３２０も含む。グラフ更新エンジン３３０は、ベースグラフ３０２及び１組の結合差分３２２に基づいて更新グラフ３５０を生成する。
【００５４】
差分分析は、所与のグラフ（例えば、ソースグラフ又はターゲットグラフ）に対して、ソース又はターゲットグラフで削除されたベースグラフ３０２内のノード、ソース又はターゲットグラフに追加されたノード、及びソース又はターゲットグラフで変更されたノードを識別する。幾つかの例では、差分分析はリンクも分析して、削除されたリンク、追加されたリンク、及び変更されたリンクを識別する。差分エンジン３１０は、ベースグラフ３０２の仕様をソースグラフ及びターゲットグラフのそれぞれの仕様と比較して、ベースグラフ３０２内のどのノード（例えば、データ処理コンポーネント、入力データセット、又は出力データセットに対応するノード）がソースグラフ及びターゲットグラフのそれぞれ内のノードに対応するかを特定する。グラフの仕様は、グラフとは別個であり、グラフのノード及びリンク等のグラフの要素を定義するファイルである。
【００５５】
対応するノードは、データグラフ及びソース又はターゲットグラフの両方に何らかの形で関わるが、必ずしも同一である必要はなく、ベースグラフとソース又はターゲットグラフとの間で差分を有することができるが、一般に、両グラフにおいて同じノードとみなすのに十分、類似するノード（関連するパラメータセットが異なるが、他の点は同一のノード等）である。幾つかの例では、差分エンジン３１０は、ノードのタイプ（例えば、データ処理コンポーネント又はデータセット）、ノードの名称、ノードの一意の識別子、又はノードに関連する他のメタデータの１つ又は複数等のノードに関連するメタデータに基づいて、対応するノードを識別する。幾つかの例では、差分エンジン３１０は、ポートの名称若しくは番号、ノードへのデータフローの名称若しくはソース、ノード若しくはコンポーネントからのデータフローの名称若しくは宛先、又はノード若しくはコンポーネント内若しくは外へのデータフローに関連する他の情報等のノード又はコンポーネント内又は外へのデータフローに関連する情報に基づいて、対応するノードを識別する。幾つかの例では、差分エンジン３１０は、特定のノードが他のノードと比較してグラフのどこに位置するか（例えば、１つ又は複数のどのノードが特定のノードの真上又は真下にあるか）等のトポロジ情報に基づいて、対応するノードを識別する。幾つかの例では、差分エンジン３１０は、カンバス上のグラフの図表現におけるノードのロケーション（例えば、ｘ−ｙ座標）に基づいて、対応するノードを識別する。幾つかの例では、例えば、カンバス上のノードのロケーションがノード又はノードを含むグラフの機能に何の影響も有さないため、差分エンジン３１０は、対応するノードを識別するに当たり、ロケーション情報を無視する。
【００５６】
所与のグラフ（例えば、ソースグラフ３０４又はターゲットグラフ３０６）の差分分析において、ソースグラフ３０４又はターゲットグラフ３０６に対応するノードがないベースグラフ３０２内の任意のノードは、そのグラフの１組の差分における削除ノードとして差分エンジン３１０により識別される。ベースグラフ３０２に対応するノードがないソースグラフ３０４又はターゲットグラフ３０６内の任意のノードは、そのグラフの１組の差分において追加ノードとして差分エンジン３１０により識別される。
【００５７】
対応するノードの対は、差分エンジン３１０により更に分析されて、ソースグラフ３０４又はターゲットグラフ３０６内のノードが、ベースグラフ３０２内の対応するノードと比較して任意の差分を有するか否かを判断する。差分が識別される場合、ノードは差分エンジン３１０により変更ノードとして識別される。幾つかの例では、差分エンジン３１０は、グラフの実行に影響することができるノードの特徴及びグラフの実行に影響しないノードの特徴の両方を分析することができる。グラフの実行に影響する特徴は、例えば、パラメータ式又はパラメータ値等のパラメータを含むことができる。グラフの実行に影響しない特徴は、例えば、属性値（例えば、オーサー属性、名称属性、バージョン属性、若しくは他の属性）、コメント、レジェンド、フォーマット（例えば、フォント）、カンバス上のノードのロケーション、又は他の特徴を含むことができる。幾つかの例では、差分エンジン３１０は、グラフの実行に影響することができる特徴のみを分析することができ、グラフの実行に影響しない特徴を無視することができる。
【００５８】
対応するノード対のパラメータの分析は、任意のパラメータが追加されたか（例えばソース又はターゲットグラフのノードに存在するが、ベースグラフの対応するノードに存在しないパラメータ）、それとも削除されたか（例えば、ベースグラフのノードに存在するが、ソース又はターゲットグラフの対応するノードに存在しないパラメータ）を識別することができる。パラメータの分析は、パラメータを定義する式、パラメータの値、又は両方の分析を含むことができる。パラメータの式を分析するために、パラメータ分析を各ノードに対応するソースコードに対して実行することができる。
【００５９】
幾つかの例では、差分分析はまた、ベースグラフ及びソース又はターゲットグラフにより参照される外部ファイルの分析を含むこともできる。幾つかの例では、レコードフォーマットファイル（例えば．ｄｍｌファイル）、変換ファイル（例えば．ｘｆｒファイル）、又は内容がグラフの実行に影響することができる他のタイプのファイル等の特定のタイプのファイルのみが差分エンジン３１０により分析される。
【００６０】
ベースグラフとソース又はターゲットグラフとの間の差分分析の結果は、各差分（ノード削除、ノード追加、及びノード変更のそれぞれ）を示す情報を含む１組の差分（例えば、組３１２、３１４）である。削除ノードを示す情報は、以下の１つ、複数、又は全てを含むことができる：
・ベースグラフにおけるノードを識別し（例えば、ノードの一意の識別子）、ノードの削除を示す情報、
・ベースグラフにおけるノードの上流にあるノードを識別する情報、
・ベースグラフにおけるノードの下流にあるノードを識別する情報、
・上流ノードからベースグラフにおけるノードへの入力フローを識別し、入力リンクの削除を示す情報、
・ベースグラフにおけるノードから下流ノードへの出力を識別し、リンクの削除を示す情報、及び
・上流ノードをソース又はターゲットグラフにおける下流ノードに接続するフローを識別し、リンクの追加を示す情報。
【００６１】
追加ノードを示す情報は、以下の１つ、複数、又は全てを含むことができる：
・ノードの機能を示す情報（例えば、ノードの仕様、ノードのパラメータセット、又はノード機能を示す他の情報）、
・ソース又はターゲットグラフにおける追加ノードの上流にあるノードを識別する情報、
・ソース又はターゲットグラフにおける追加ノードの下流にあるノードを識別する情報、
・上流ノードからソース又はターゲットグラフにおける追加ノードへのリンクを識別し、リンクの追加を示す情報、
・追加ノードからソース又はターゲットグラフにおける下流ノードへのリンクを識別し、リンクの追加を示す情報、及び
・上流ノードからベースグラフにおける下流ノードへのリンクを識別し、リンクの削除を示す情報。
【００６２】
変更ノードを示す情報は、以下の１つ、複数、又は全てを含むことができる：
・ノードを識別する情報及び
・ノードへの変更を示す情報（例えば、更新パラメータリスト）。
【００６３】
差分分析の更なる説明は、２０１７年５月５日付けで出願された米国特許出願第１５／５８７，９８７号明細書において提供され、この特許出願の内容は全体的に、参照により本明細書に援用される。
【００６４】
併合エンジン３２０は、複数の組の差分３１２、３１４を併合して１組の結合差分３２２にする。そうするために、併合エンジン３２０は、差分対３１２、３１４間の対応性を特定して、（１）差分対の１つのみで識別されるノードが関わる差分及び（２）複数の組の差分の２つ以上で識別されるノードが関わる差分を識別する。特定のノードが関わる差分とは、情報が特定のノードを例えば削除ノード、追加ノード、変更ノード、上流ノード、又は下流ノードとして識別する差分を示す差分を意味する。差分対の１つのみで識別されるノードが関わる各差分について、その差分を示す情報は１組の結合差分３２２に追加される。２つ以上の組の差分で識別されるノードが関わる各差分について、併合エンジン３２０は互換性分析を実行する。
【００６５】
互換性分析とは、第１の差分が第２の差分と競合するか、それとも互換性を有するかを判断する分析である。差分対は、ベースグラフのコピーへの差分の１つの適用が、差分の他の１つのコピーへの適用を妨げる場合、競合対と呼ばれる。競合対の一例は、フィルタコンポーネントの削除及びその同じフィルタコンポーネントのパラメータへの変更である。競合対の別の例は、リフォーマットコンポーネントの削除及びフローによるそのリフォーマットコンポーネントに接続されたデータソースの追加である。競合対の別の例は、コンポーネントのパラメータへの第１の変更及びコンポーネントのその同じパラメータへの第２の異なる変更である。
【００６６】
併合エンジン３２０は、差分対を選択することにより各競合対を解決する。選択された差分を示す情報は１組の結合差分３２２に追加される。幾つかの例では、併合エンジン３２０は、選択基準３２４、例えば競合の解決の仕方についてユーザにより提供される指示を参照して各差分対を解決する。例えば、選択基準は、複数の差分対の優先順位を指定し、併合エンジン３２０がより高優先度の差分対から差分を選択すべきことを示し得る。幾つかの例では、併合エンジン３２０は、ユーザが各競合対から差分を手動で選択することができるように、競合対をユーザインターフェース３４０に表示させる。
【００６７】
幾つかの例では、競合対は、テキスト情報として、例えばリストとしてユーザに提示することができる。幾つかの例では、競合対は、例えば、２０１７年５月５日付けで出願された米国特許出願第１５／５８７，９８７号明細書に記載されるように、各差分の図表現を使用してユーザに提示することができ、この米国特許出願の内容は全体的に、参照により本明細書に援用される。
【００６８】
グラフ更新エンジン３３０は、１組の結合差分３２２における差分に基づいて更新グラフ３５０を生成する。例えば、グラフ更新エンジン３３０は、ベースグラフ３０２のコピーを生成し、１組の結合差分における差分をコピーに適用することができる。各差分について、１組の結合差分３２２は、リンクの追加又は削除及びノードの追加、削除、又は変更を含め、行うべき１つ又は複数の変更を識別する。グラフ更新エンジン３３０はこれらの各変更をコピーに適用する。全ての変更が適用されたコピーが更新グラフ３５０である。
【００６９】
幾つかの例では、１組の結合差は互換性がある差分のみを含むことができ、したがって、更新グラフ３５０は互換性のある差分のみを反映する。差分の競合対が解決されると、解決された差分も更新グラフに適用することができる。
【００７０】
図４Ａ〜図４Ｄを参照して、差分を併合する一例を示す。図４Ａは、銀行取引レコードを処理するベースグラフ４００を示す。ベースグラフ４００は、データソース４０２、リフォーマットノード４０４、フィルタノード４０６、及びデータシンク４０８を有する。フィルタノード４０６には、ｔｒａｎｓａｃｔｉｏｎ＿ａｍｏｕｎｔフィールドを識別するｆｉｌｔｅｒ＿ｂｙパラメータを含むパラメータセット４０５が関連付けられる。ノードは、図４Ａに示されるように、リンク４１０、４１２、４１６により接続される。
【００７１】
図４Ｂ及び図４Ｃはそれぞれソースグラフ４２０及びターゲットグラフ４４０である。差分分析は、ソースグラフ４２０において、フィルタノード４０６が削除され、追加のデータソース４２２が追加されたことを識別する。ターゲットグラフ４４０では、フィルタノード４０６には、ｆｉｌｔｅｒ＿ｂｙパラメータがｔｒａｎｓａｃｔｉｏｎ＿ｄａｔｅフィールドである変更パラメータセット４０５’が関連付けられ、追加のソートノード４４２が追加された。
【００７２】
ソースグラフ４２０の１組の差分は以下の情報を含む：
・削除されたフィルタノード４０６を示す情報：
・フィルタノード４０６の識別子、
・ベースグラフ４００においてフィルタノード４０６の上流にあるリフォーマットノード４０４の識別子、
・ベースグラフにおいてフィルタノード４０６の下流にあるデータシンクノード４０８の識別子、
・ベースグラフにおいてリフォーマットノード４０４とフィルタノード４０６との間のリンク４１２及びリンク４１２の削除の指示、
・ベースグラフにおけるフィルタノード４０６とデータシンクノード４０８との間のリンク４１６及びリンク４１６の削除の指示、並びに
・ソースグラフ４２０におけるリフォーマットノード４０４とデータシンクノード４０８との間の新しいリンク４２４の識別子、
・新しいデータソースノード４２２を示す情報：
・データソースノード４２２の仕様、
・ソースグラフ４２０におけるデータソースノード４２２の下流にあるリフォーマットノード４０４の識別子、
・ソースグラフ４２０におけるデータソースノード４２２とリフォーマットノード４０４との間の新しいリンク４２６の識別子。
【００７３】
ターゲットグラフ４４０の１組の差分は以下の情報を含む：
・フィルタノード４０６の変更を示す情報：
・フィルタノード４０６の識別子、
・ターゲットグラフ４４０においてフィルタノード４０６の上流にあるリフォーマットノードの識別子、
・ターゲットグラフ４４０においてフィルタノード４０６の下流にあるソートノードの識別子、
・フィルタノード４０２に接続された各リンク４１２、４４４の識別子、及び
・変更パラメータセット４０５’の仕様、
・ソートノード４４２の追加を示す情報：
・ソートノード４４２の仕様、
・ソートノードのパラメータセットの仕様、
・ターゲットグラフ４４０におけるソートノード４４２の上流にあるフィルタノード４０６の識別子、
・ターゲットグラフ４４０におけるソートノード４４２の下流にあるデータシンクノード４０８の識別子、
・ターゲットグラフ４４０におけるフィルタノード４０６とソートノード４４２との間の新しいリンク４４４の識別子、
・ターゲットグラフにおけるソートノード４４２とデータシンク４０８との間の新しいリンク４４６の識別子、及び
・ベースグラフにおけるフィルタノード４０６とデータシンク４０８との間のリンク４１６の識別子及びリンク４１６の削除の指示。
【００７４】
互換性分析は、ソースグラフ４２０におけるデータソース４２２の追加がターゲットグラフ４４０における全ての差分と互換性があり、ターゲットグラフ４４０におけるソートノード４４２の追加がソースグラフ４２０における全ての差分と互換性があると判断する。データソース４２２の追加及びソートコンポーネント４４２の追加を示す上記列挙した情報は、１組の結合差分に追加される。
【００７５】
互換性分析は、ターゲットグラフ４４０におけるフィルタノード４０６に関連するパラメータセット１５の変更と競合するものとして、ソースグラフ４２０におけるフィルタノード４０６の削除を識別する。この例では、この競合はユーザインターフェースでユーザに提示され、ユーザは、例えば、パラメータセット変更の選択で応答し得る。代替的には、選択基準が自動的にシステム３００により適用し得、同じ選択に繋がり得る。パラメータセットの変更を示す上記列挙した情報は、２組の結合差分に追加される。フィルタノード４０６の削除を示す情報は１組の結合差分に追加されない。
【００７６】
図４Ｄを参照すると、１組の結合差分における差分はベースグラフ４００のコピーに適用されて、更新グラフ４５０を生成する。特に、上記指定したノード及びリンクの追加、削除、及び変更は、ベースグラフ４００のコピーに適用される。例えば、ソートノードの追加をベースグラフのコピーに適用するために、リンク４１６は削除され、ソートノード４４２は追加され、ソートノードを上流ノード及び下流ノードに接続する新しいリンク４４６、４４８が追加される。グラフ４５０における各ノードは対応するコンポーネントを表し、グラフ４５０における各リンクは、コンポーネント間の対応するデータフローを表す。
【００７７】
図５Ａは、ベースグラフ、ソースグラフ、及びターゲットグラフに基づいて更新グラフを生成するプロセスの一例を示す。第１の組の差分が、ベースグラフとソースグラフとの間で特定される（５００）。図５Ｂを参照すると、第１の組の差分を特定するために、ベースノードグラフにおける各ノード又はリンクとソースグラフにおけるノード又はリンクとの間の対応性が特定される（５５０）。ソースグラフにおける第２のノード又はリンクに対応するベースグラフにおける第１のノード又はリンクのそれぞれは、対応する第２のノード又はリンクと比較され（５５２）、第１のノード又はリンクと第２のノード又はリンクとの間の任意の差分が識別される（５５４）。第１のノード又はリンクと第２のノード又はリンクとの間に差分がない場合、第２のノード又はリンクは第１の組の差分に含まれない（５５８）。第１のノード又はリンクと第２のノード又はリンクとの間に差分がある場合（５６０）、第２のノード又はリンクは、第１の組の差分において変更ノード又はリンクとして示される（５６２）。ソースグラフにおけるノード又はリンクに対応しないベースグラフにおけるノード又はリンクは、第１の組の差分において削除ノード又はリンクとして示される（５６４）。ベースグラフにおけるノード又はリンクに対応しないソースグラフにおけるノード又はリンクは、第１の組の差分において追加ノード又はリンクとして示される（５６６）。
【００７８】
第２の組の差分が、ベースグラフとターゲットグラフとの間で特定される（５０２）。第２の組の差分を特定するために、ベースノードグラフにおける各ノード又はリンクとターゲットグラフにおけるノード又はリンクとの間の対応性が特定される。ターゲットグラフにおける第２のノード又はリンクに対応するベースグラフにおける第１のノード又はリンクのそれぞれは、対応する第２のノード又はリンクと比較され、第１のノード又はリンクと第２のノード又はリンクとの間の任意の差分が識別される。第１のノード又はリンクと第２のノード又はリンクとの間に差分がない場合、第２のノード又はリンクは第２の組の差分に含まれない。第１のノード又はリンクと第２のノード又はリンクとの間に差分がある場合、第２のノード又はリンクは、第２の組の差分において変更ノード又はリンクとして示される。ターゲットグラフにおけるノード又はリンクに対応しないベースグラフにおけるノード又はリンクは、第２の組の差分において削除ノード又はリンクとして示される。
【００７９】
第１の組の差分における特定の差分は評価されて、特定の差分と第２の組の差分との間の対応性を特定する（５０４）。第１の組の差分における特定の差分に対応する第２の組の差分における差分がない場合（５０６）、第１の組の差分における特定の差分は、１組の結合差分に追加され（５０８）、対処済みとして示される。第１の組の差分における特定の差分に対応する第２の組の差分における差分がある場合（５１０）、第２の組の差分における対応する差分との特定の差分の互換性が特定される（５１２）。差分が互換性を有すると特定される場合（５１４）、第１の組の差分における特定の差分は１組の結合差分に追加され（５０８）、両差分は対処済みとして示される。差分が互換性を有すると特定される場合（５１６）、各差分の相対優先度が、予め定義されたルールに従って又はユーザ入力に基づいて特定される（５１８）。高優先度の差分は１組の結合差分に追加され（５２０）、両差分は対処済みとして示される。
【００８０】
第１の組の差分はレビューされて、全ての差分が対処されたか否かを判断する（５２２）。対処されていない差分が第１の組の差分に残っている場合（５２４）、第１の組の差分における別の差分が評価される（５０４）。第１の組の差分における全ての差分が対処された場合（５２６）、第２の組の差分における任意の未対処差分が１組の結合差分に追加される（５２８）。１組の結合差分はベースグラフに適用されて、更新グラフを生成する（５３０）。
【００８１】
図６〜図９は、ソースグラフ及びターゲットグラフから更新グラフを生成するユーザインターフェースの一例のスクリーンショットである。
【００８２】
特に図６を参照して、グラフィカルユーザインターフェース６００は、ベースグラフとソースグラフ及びターゲットグラフとの間の差分を併合することにより作成された更新グラフのリストを示す。アイコンは、例えば、更新グラフが互換性問題を有さない（例えば、ｃａｌｃｕｌａｔｅ＿ｉｎｔｅｒｅｓｔ＿ｄａｉｌｙグラフに示されるように）こと又は差分の１つ若しくは複数の競合対を有する（例えば、ａｐｐｌｙ＿ｉｎｔｅｒｅｓｔ＿ｍｏｎｔｈｌｙグラフに示されるように）ことを示す、各更新グラフのステータスを示すことができる。ユーザは、グラフの１つを選択して、グラフについての情報を表示することができる。例えば、差分の１つ又は複数の競合対を有するグラフの場合、ユーザは、ベースグラフとソースグラフ及びターゲットグラフの１つ又は複数との間の差分のグラフ表現を見ることができる。差分の図表現の一例を図７に示す。
【００８３】
図８を参照すると、幾つかの例では、競合はテキストフォーマットで表現することができる。例えば、図８の例では、ソースグラフは「＋４００．００」値を含み、ターゲットグラフは「＋２００．０」値を含む。競合がテキストで表される場合、ユーザはテキストを編集して、所望の内容を残すことができる（例えば、所与の競合でソースグラフ又はターゲットグラフに対応するテキストを削除する）。幾つかの例では、全ての差分がテキストに含まれ、競合する差分は、「＜＜＜＜＜＜＜＜」マーカと「＞＞＞＞＞＞＞＞＞」マーカとの間に挟まれる等のマーカにより示されて、ユーザが全ての競合を容易に見つけられるようにする。
【００８４】
図９を参照すると、幾つかの例では、競合は図で表すことができる。競合に対処するために、ユーザは各競合を選択（例えば、クリック又はタップ）して、競合のテキスト表現にアクセスことができる。幾つかの例では、競合は、図表現を通して直接対処することができる。
【００８５】
図１０は、ベースグラフに基づいて更新グラフを生成する一般的なプロセスを示す。第１のデータフローグラフと第２のデータフローグラフ及び第３のデータフローグラフのそれぞれとの間の差分が識別される（５０）。第１のデータフローグラフはベースグラフを含み、第２のデータフローグラフはソースグラフを含み、第３のデータフローグラフはターゲットグラフを含む。各データフローグラフの仕様は、１つ又は複数のノード及びノードを接続する１つ又は複数のリンクを定義する。ノードの少なくとも１つは、データ処理コンポーネントに提供されるデータを処理するために実行すべき演算を定義するデータ処理コンポーネントを表す。差分を識別すること（５０）は、ベースグラフの仕様とソースグラフの仕様とを比較することであって、それにより、ベースグラフとソースグラフとの間の第１の組の差分を識別すること、例えば、第１の削除ノード、第１の削除フロー、第１の追加ノード、第１の追加フロー、第１の変更ノード、又は第１の変更フローの１つ又は複数を識別することを含む。差分を識別すること（５０）は、ベースグラフの仕様とターゲットグラフの仕様とを比較することであって、それにより、ベースグラフとターゲットグラフとの間の第２の組の差分を識別すること（５４）、例えば、第２の削除ノード、第２の削除フロー、第２の追加ノード、第２の追加フロー、第２の変更ノード、又は第２の変更フローの１つ又は複数を識別することも含む。
【００８６】
第１の組の差分における差分と第２の組の差分における差分との間の対応性が特徴付けられる（５６）。特徴付けることは、（ｉ）第２の組の差分において識別されるノード若しくはリンクに対応する第１の組の差分において識別されるノード若しくはリンク、（ｉｉ）第２の組の差分において識別されるいずれのノード若しくはリンクにも対応しない第１の組の差分において識別されるノード若しくはリンク、又は（ｉｉｉ）第１の組の差分において識別されるいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されるノード若しくはリンクの１つ又は複数を識別することを含む。第１の組の差分において識別されたノード又はリンクと第２の組の差分において識別された対応するノード又はリンクとの間の互換性が特定される（５８）。
【００８７】
１組の結合差分が、特徴付けられた対応性、ベースグラフとソースグラフとの間の第１の組の差分、及びベースグラフとターゲットグラフとの間の第２の組の差分に基づいて特定される（６０）。１組の結合差は、第１の組の差分において識別されたノード若しくはリンクと第２の組の差分において識別された対応するノード若しくはリンクとの間の互換性に基づいて特定することができる。１組の結合差分には、第２の組の差分において識別されたいかなるノード若しくはリンクにも対応しない第１の組の差分において識別されたノード若しくはリンクを示す情報又は第１の組の差分において識別されたいかなるノード若しくはリンクにも対応しない第２の組の差分において識別されたノード若しくはリンクを示す情報を含めることができる。
【００８８】
更新データフローグラフは、ベースグラフ及び１組の結合差分に基づいて生成される（６２）。
【００８９】
幾つかの例では、グラフのコンポーネントは、それら自体がフローと相互接続される１組の他のコンポーネントを使用して実施することができる。グラフのコンポーネントが実施されるこの１組のコンポーネントは、サブグラフと呼ばれ、グラフのノードである。本明細書に記載される手法は、サブグラフを含むグラフ間の差分の併合に使用することができる。
【００９０】
プランとは、複数のグラフの実行が関わるプロセスの視覚的表現である。プランでは、個々のグラフはノードであり、プランのグラフ間のデータフローを示すフローにより相互接続される。
【００９１】
図１１は、開発のためのデータ処理システム１０００及び本明細書に記載される技法を使用することができるデータフローグラフの一例を示す。幾つかの場合、データ処理システム１０００はまた、実行可能データフローグラフを実行するためのものであることもできる。システム１０００は、記憶装置又はオンラインデータストリームへの接続等の１つ又は複数のデータソースを含み得るデータソース１００２を含み、各データソースは、任意の種々のフォーマット（例えば、データベーステーブル、スプレッドシートファイル、平文ファイル、又はメインフレームコンピュータにより使用されるネイティブフォーマット）のデータを記憶又は提供し得る。データは、物流データ、分析データ、又は産業機械データであり得る。実行環境又は実行時環境１００４は、前処理モジュール１００６及び実行モジュール１０１２を含む。実行環境１００４は、例えば、あるバージョンのＵＮＩＸ（登録商標）オペレーティングシステム等の適したオペレーティングシステムの制御下で１つ又は複数の汎用コンピュータでホストし得る。例えば、実行環境１００４は、ローカル（例えば、対称マルチ処理（ＳＭＰ）コンピュータ等のマルチプロセッサシステム）、ローカルに分散（例えば、クラスタとして結合される複数のプロセッサ又は超並列処理（ＭＰＰ）システム、リモート、リモートに分散（例えば、ローカルエリアネットワーク（ＬＡＮ）及び／又は広域ネットワーク（ＷＡＮ）を介して結合される複数のプロセッサ）、又はそれらの任意の組合せのいずれかである、複数の処理ユニット（中央演算処理装置、ＣＰＵ等）又はプロセッサコアを使用するコンピュータシステムの構成を含む複数のノード並列計算環境を含むことができる。
【００９２】
データソース１００２を提供する記憶装置は、実行環境１００４に対してローカル、例えば、実行環境１００４をホストするコンピュータに接続された記憶媒体（例えば、ハードドライブ１００８）に記憶されてもよく、実行環境１００４に対してリモート、例えば、リモート接続（例えば、クラウド計算基盤により提供される）を介して実行環境１００４をホストするコンピュータと通信するリモートシステム（例えば、メインフレームコンピュータ１０１０）でホストされてもよい。
【００９３】
前処理モジュール１００６は、データソース１００２からデータを読み取り、実行に向けてデータ処理アプリケーション（例えば、実行可能データフローグラフ）を準備する。例えば、前処理モジュール１００６は、データ処理アプリケーションをコンパイルし、実行環境１００４がアクセス可能なデータ記憶システム１０１６にコンパイルされたデータ処理アプリケーションを記憶且つ／又は実行環境１００４がアクセス可能なデータ記憶システム１０１６からコンパイルされたデータ処理アプリケーションをロードし、実行に向けてデータ処理アプリケーションを準備する他のタスクを実行する。
【００９４】
実行モジュール１０１２は、前処理モジュール１００６により準備されたデータ処理アプリケーションを実行して、１組のデータを処理し、処理から生じた出力データ１０１４を生成する。出力データ１０１４は、データソース１００２に記憶されてもよく、実行環境１００４がアクセス可能なデータ記憶システム１０１６に記憶されてもよく、又は他の方法で使用されてもよい。データ記憶システム１０１６には、開発者１０２０が実行モジュール１０１２により実行されるデータ処理アプリケーションを設計、編集することが可能な、任意選択的な開発環境１０１８もアクセス可能である。開発環境１０１８は、幾つかの実施態様では、頂点間の有向リンク（作業要素、すなわちデータのフローを表す）により接続される頂点（データ処理コンポーネント又はデータセットを表す）を含むデータフローグラフとしてアプリケーションを開発するシステムである。例えば、そのような環境は「Ｍａｎａｇｉｎｇ  Ｐａｒａｍｅｔｅｒｓ  ｆｏｒ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」と題する米国特許出願公開第２００７／００１１６６８号明細書により詳細に説明されており、この特許出願は参照により本明細書に援用される。そのようなグラフベースの計算を実行するシステムは、「ＥＸＥＣＵＴＩＮＧ  ＣＯＭＰＵＴＡＴＩＯＮＳ  ＥＸＰＲＥＳＳＥＤ  ＡＳ  ＧＲＡＰＨＳ」と題する米国特許第５，９６６，０７２号明細書に記載されており、この米国特許の内容は全体的に、参照により本明細書に援用される。このシステムにより作成されたデータフローグラフは、グラフコンポーネントにより表される個々のプロセス内へ及び個々のプロセスから情報を取得し、情報をプロセス間で移動させ、プロセスの実行順序を定義する方法を提供する。このシステムは、任意の利用可能な方法からプロセス間通信方法を選ぶ（例えば、グラフのリンクに従った通信パスは、ＴＣＰ／ＩＰ若しくはＵＮＩＸドメインソケットを使用することができ、又は共有メモリを使用して、プロセス間でデータを渡すことができる）アルゴリズムを含む。
【００９５】
前処理モジュール１００６は、異なる形態のデータベースシステムを含め、データソース１００２を実施し得る種々のタイプのシステムからデータを受信することができる。データは、可能な場合にはヌル値を含む、各フィールド（「属性」又は「カラム」とも呼ばれる）に値を有するレコードとして編成し得る。データソースからデータを最初に読み取る際、前処理モジュール１００６は通常、そのデータソースにおけるレコードについての何らかの初期フォーマット情報で開始する。幾つかの状況では、データソースのレコード構造は最初、知られていないことがあり、代わりに、データソース又はデータの分析後に特定し得る。レコードについての初期情報は、例えば、別個の値を表すビット数、レコード内のフィールドの順序、及びビットにより表される値の対応タイプ（例えば、文字列、符号付き／符号なし整数）を含むことができる。
【００９６】
換言すれば、本明細書に記載される実行可能データフローグラフに一般に適用可能なように、実行可能データフローグラフは、データソース１００２の１つ又は複数の入力データセットからデータ処理コンポーネントを通して１つ又は複数の出力データセットに流れるデータに対して実行されるグラフベースの計算を実施し、データフローグラフはデータ記憶装置１０１４内のデータ構造により指定され、データフローグラフは、データ構造により指定され、１つ又は複数のリンクにより接続されるデータ処理コンポーネントを表すノードを有し、リンクはデータ構造により指定され、データ処理コンポーネント間のデータフローを表す。実行環境又は実行時環境１００４はデータ記憶装置１０１４に結合され、１つ又は複数のコンピュータでホストされ、実行時環境１００４は、データフローグラフを指定する、記憶されたデータ構造を読み取り、前処理モジュール１００６によりデータフローグラフに割り当てられたデータ処理コンポーネントの計算の実行に向けて計算リソース（例えば、要素、メモリ、ＣＰＵ等）を割り振り構成するように構成された前処理モジュール１００６を含み、実行時環境１００４は、データ処理コンポーネントの計算の実行をスケジュールし制御する実行モジュール１０１２を含む。換言すれば、１つ又は複数のコンピュータでホストされる実行時又は実行環境１００４は、データソース１００２からデータを読み取り、データフローグラフの形態で表される実行可能コンピュータプログラムを使用してデータを処理するように構成される。
【００９７】
上述した手法は、適したソフトウェアを実行する計算システムを使用して実施することができる。例えば、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、少なくとも１つのデータ記憶システム（揮発性及び／又は不揮発性メモリ及び／又は記憶要素を含む）、少なくとも１つのユーザインターフェース（少なくとも１つの入力デバイス又はポートを使用して入力を受信し、少なくとも１つの出力デバイス又はポートを使用して出力を提供する）を含む１つ又は複数のプログラムされた又はプログラム可能な計算システム（分散、クライアント／サーバ、又はグリッド等の種々のアーキテクチャであり得る）で実行される１つ又は複数のコンピュータプログラム内にプロシージャを含み得る。ソフトウェアは、例えば、グラフの設計、構成、及び実行に関連するサービスを提供するより大きなプログラムの１つ又は複数のモジュールを含み得る。プログラムのモジュール（例えば、グラフの要素）は、データリポジトリに記憶されたデータモデルに準拠したデータ構造又は他の編成データとして実施することができる。
【００９８】
ソフトウェアは、ＣＤ−ＲＯＭ若しくは他のコンピュータ可読媒体（例えば、汎用若しくは専用計算システム若しくはデバイスにより可読）等の有形非一時的媒体で提供されてもよく、又はネットワークの通信媒体を介して、実行される計算システムの有形非一時的媒体に送出（例えば、伝播信号に符号化）してもよい。処理の幾つか又は全ては、コプロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又は専用特定用途向け集積回路（ＡＳＩＣ）等の専用コンピュータで実行されてもよく、専用ハードウェアを使用して実行されてもよい。処理は、ソフトウェアにより指定される計算の異なる部分が異なる計算要素により実行される分散様式で実施し得る。そのような各コンピュータプログラムは、好ましくは、汎用又は専用プログラマブルコンピュータがアクセス可能な記憶装置のコンピュータ可読記憶媒体（例えば、固体状態メモリ、固体状態媒体、磁気媒体、又は光学媒体）に記憶又はダウンロードされて、記憶装置媒体がコンピュータにより読み取られると、本明細書に記載された処理を実行するようにコンピュータを構成し動作させる。本発明によるシステムはまた、コンピュータプログラムが構成された有形非一時的媒体として実施されると見なすこともでき、そうして構成された媒体は、特定の予め定義された様式でコンピュータを動作させて、本明細書に記載された処理ステップの１つ又は複数を実行させる。
【００９９】
本発明の幾つかの実施形態について説明した。それにも関わらず、上記説明が例示を意図し、本発明の範囲の限定を意図せず、本発明の範囲が以下の特許請求の範囲により規定されることを理解されたい。したがって、他の実施形態も以下の特許請求の範囲内にある。例えば、本発明の範囲から逸脱せずに種々の変更を行い得る。さらに、上述したステップの幾つかは順序から独立し得、したがって、説明された順序とは異なる順序で実行することができる。
【図１】
2021527249.tif 000003
【図２Ａ】
2021527249.tif 000004
【図２Ｂ】
2021527249.tif 000005
【図２Ｃ】
2021527249.tif 000006
【図３】
2021527249.tif 000007
【図４Ａ】
2021527249.tif 000008
【図４Ｂ】
2021527249.tif 000009
【図４Ｃ】
2021527249.tif 000010
【図４Ｄ】
2021527249.tif 000011
【図５Ａ】
2021527249.tif 000012
【図５Ｂ】
2021527249.tif 000013
【図６】
2021527249.tif 000014
【図７】
2021527249.tif 000015
【図８】
2021527249.tif 000016
【図９】
2021527249.tif 000017
【図１０】
2021527249.tif 000018
【図１１】
2021527249.tif 000019
【国際調査報告】
2021527249.tif 000020
2021527249.tif 000021
2021527249.tif 000022