(57)【特許請求の範囲】
【請求項１】
コンピューティングシステムにおいて系統情報を管理するための方法であって、
前記方法は、前記コンピューティングシステムのプロセッサによって実施され、
複数のノードと、前記複数のノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様をデータストレージシステムに記憶するステップであって、前記ノードの少なくとも一部が、複数のタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、前記複数のタグ識別子のうちの少なくとも１つのタグ識別子が、複数の可能なタグ値を有する、前記記憶するステップと、
前記複数のノードのうちの第１のノードに関するデータ系統の表現を求める要求を少なくとも１つのプロセッサを使用して処理するステップであって、
前記第１のノードと前記複数のタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、前記第１のタグ識別子の複数の可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定することと、
前記第１のノードに関するデータ系統を決定するために、前記第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、前記データ系統が、（１）前記第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）前記第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、前記データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的に前記トラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、前記データ系統に前記トラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることとを含む、前記処理するステップを含む、前記方法。
【請求項２】
データ系統を決定することが、それぞれのトラバースされるノードに関して、
前記トラバースされるノードが第１のタグ識別子に関連付けられないか、若しくは前記トラバースされるノードが前記第１のタグ識別子に関連付けられ、第１のサブセットの少なくとも１つのタグ値に関連付けられる場合に前記データ系統に前記トラバースされるノードを追加すること、又は
前記トラバースされるノードが前記第１のタグ識別子に関連付けられ、前記第１のタグ識別子の複数の可能なタグ値の前記第１のサブセットの少なくとも１つのタグ値に関連付けられない場合に前記データ系統から前記トラバースされるノードを除外することを含む、請求項１に記載の方法。
【請求項３】
データ系統からトラバースされるノードを除外すると、第１の系統のパスのトラバースを終了するステップをさらに含む、請求項２に記載の方法。
【請求項４】
第１のタグ識別子に関連付けられ、前記第１のタグ識別子の複数の可能なタグ値の第１のサブセットの少なくとも１つのタグ値に関連付けられない複数のノードの第１のサブセットを決定するために、前記複数のノードのうちのノードをトラバースする前に前記複数のノードを分析するステップをさらに含む、請求項１に記載の方法。
【請求項５】
データ系統にトラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することが、前記トラバースされるノードが複数のノードの第１のサブセットに含まれるかどうかを決定することを含む、請求項４に記載の方法。
【請求項６】
データ系統にトラバースされるノードを追加すべきかどうかを決定することが、前記トラバースされるノードが複数のノードの第１のサブセットに含まれない場合に前記データ系統に前記トラバースされるノードを追加し、前記トラバースされるノードが前記複数のノードの前記第１のサブセットに含まれる場合に前記データ系統から前記トラバースされるノードを除外することを含む、請求項５に記載の方法。
【請求項７】
複数のノードの少なくとも一部のノードが、前記複数のノードのその他のノードの中に入れ子にされる、請求項１に記載の方法。
【請求項８】
ノードの入れ子にされた階層のより低いレベルのノードに関連するタグ識別子及びタグ値の前記タグ識別子に関連するサブセットが、ノードの前記入れ子にされた階層のより高いレベルのノードに関連するタグ識別子及びタグ値の前記タグ識別子に関連するサブセットを上回る優先度を与えられる、請求項７に記載の方法。
【請求項９】
第１の系統のパスに沿ってノードをトラバースすることが、第１のノードから始まる前記ノードを有向リンクの方向と反対の方向にトラバースすることを含む、請求項１に記載の方法。
【請求項１０】
有向グラフの仕様を生じさせるステップであって、複数のノードのうちの１又は２以上が計算を表し、前記複数のノードのうちの１又は２以上が計算の実行中に受け取られるか又は計算によって生成されるデータ要素を表し、有向リンクが計算とデータ要素との間の系統の関係を表す、前記ステップをさらに含む、請求項１に記載の方法。
【請求項１１】
複数のノードのうちの１又は２以上が、前記複数のノードのうちの１又は２以上のその他のノードのグループ分けを表す、請求項１０に記載の方法。
【請求項１２】
第１のタグ識別子の複数の可能なタグ値の第１のサブセットが、第１のノードに関連付けられる１又は２以上のタグ値からなる、請求項１に記載の方法。
【請求項１３】
第１のタグ識別子の複数の可能なタグ値の第１のサブセットが、ユーザ入力から受け取られる１又は２以上のタグ値からなる、請求項１に記載の方法。
【請求項１４】
第１のノードに関するデータ系統を決定するために前記第１のノードから有向リンクの複数の系統のパスに沿ってノードをトラバースするステップであって、前記データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的に前記トラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、前記データ系統に前記トラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することを含む、前記ステップをさらに含む、請求項１に記載の方法。
【請求項１５】
デフォルトでデータ系統に第１のノードを追加するステップをさらに含む、請求項１に記載の方法。
【請求項１６】
コンピュータ可読媒体に記憶された、コンピューティングシステムにおいて系統情報を管理するためのプログラムであって、コンピューティングシステムに、
複数のノードと、前記複数のノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様をデータストレージシステムに記憶することであって、前記ノードの少なくとも一部が、複数のタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、前記複数のタグ識別子のうちの少なくとも１つのタグ識別子が、複数の可能なタグ値を有する、前記記憶することと、
前記複数のノードのうちの第１のノードに関するデータ系統の表現を求める要求を少なくとも１つのプロセッサを使用して処理することであって、
前記第１のノードと前記複数のタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、前記第１のタグ識別子の複数の可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに
前記第１のノードに関するデータ系統を決定するために、前記第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、前記データ系統が、（１）前記第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）前記第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、前記データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的に前記トラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、前記データ系統に前記トラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む、前記処理することとを行わせるための命令を含む、前記プログラム。
【請求項１７】
系統情報を管理するためのコンピューティングシステムであって、
複数のノードと、前記複数のノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様を記憶するデータストレージシステムであって、前記ノードの少なくとも一部が、複数のタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、前記複数のタグ識別子のうちの少なくとも１つのタグ識別子が、複数の可能なタグ値を有する、前記データストレージシステムと、
前記複数のノードのうちの第１のノードに関するデータ系統の表現を求める要求を処理するように構成された少なくとも１つのプロセッサであって、前記処理することが、
前記第１のノードと前記複数のタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、前記第１のタグ識別子の複数の可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに
前記第１のノードに関するデータ系統を決定するために、前記第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、前記データ系統が、（１）前記第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）前記第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、前記データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的に前記トラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、前記データ系統に前記トラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む、前記プロセッサとを含む、前記コンピューティングシステム。
【請求項１８】
系統情報を管理するためのコンピューティングシステムであって、
複数のノードと、前記複数のノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様を記憶するための手段であって、前記ノードの少なくとも一部が、複数のタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、前記複数のタグ識別子のうちの少なくとも１つのタグ識別子が、複数の可能なタグ値を有する、前記記憶するための手段と、
前記複数のノードのうちの第１のノードに関するデータ系統の表現を求める要求を処理するための手段であって、前記処理することが、
前記第１のノードと前記複数のタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、前記第１のタグ識別子の複数の可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに
前記第１のノードに関するデータ系統を決定するために、前記第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、前記データ系統が、（１）前記第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）前記第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、前記データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的に前記トラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、前記データ系統に前記トラバースされるノードを追加すべきか又は前記データ系統から前記トラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む、前記処理するための手段を含む、前記コンピューティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２０１５年２月１１日に出願した米国特許出願第６２／１１４，６８４号の優先権を主張するものである。
【０００２】
この説明は、データ系統図(data lineage diagrams)のフィルタリングのための系統タグ(lineage tags)に関する。
【背景技術】
【０００３】
データ処理システムにおいては、データがシステムを通過するときにデータの系統の視覚的表現に特定の種類のユーザがアクセスすることができることが望ましいことが多い。そのような「データ系統図」は、データ及びそれらのデータの間の依存関係を処理するためのシステムにおけるそれらのデータ及びエンティティ(entities)の図式的表現を含む可能性がある。極めて広く、多くの用途の中でもとりわけ、そのようなデータ系統図は、リスクを減らし、規制遵守義務を確認し、ビジネスプロセスを能率化し、データを保護するために使用され得る。データ系統図は正しく且つ完全であることが重要である。
【０００４】
データ系統図を生じさせ、表示することができる一部のシステムは、データアイテムとそれらのデータアイテムを消費するか又は生じさせる処理エンティティ(processing entities)を表すアイテムとの表現を示すエンドツーエンド(end-to-end)のデータ系統図を自動的に提示することができる。一部の例において、特定のアイテムから上流の系統のパス(a lineage path upstream)は、そのアイテムに関する「ディペンデンシー系統」（dependency lineage）と呼ばれることがあり、特定のアイテムから下流の系統のパス(a lineage path downstream)は、そのアイテムに関する「インパクト系統」（impact lineage）と呼ばれることがある。その他の例において、特定のアイテムから上流の系統のパスは、「系統」(lineage)又は「ディペンデンシー」(dependency)と呼ばれ、特定のアイテムから下流の系統のパスは、「インパクト」(impact)又は「インパクト分析」(impact analysis)と呼ばれる。本明細書において使用されるとき、「データ系統図」は、任意の所与のアイテムに関連する上流ディペンデンシー系統及び／又は下流インパクト系統を含む可能性がある。データ系統図を生じさせ、表示することができる一部のシステムは、ユーザがデータ系統図内のアイテムの論理的及び／又は物理的グループを単一の要素にまとめることを可能にする。データ系統図を生じさせ、表示することができる一部のシステムは、データ品質の採点などの充実したデータ情報によってデータ系統図を改善することができる。
【発明の概要】
【課題を解決するための手段】
【０００５】
一態様においては、概して、コンピューティングシステムにおいて系統情報を管理するための方法が、いくつかのノード(nodes)と、ノードの間のそれぞれの系統の関係を表す有向リンク(directed links)とを含む有向グラフ(directed graph)の仕様をデータストレージシステムに記憶するステップであって、ノードの少なくとも一部が、いくつかのタグ識別子(tag identifiers)のうちの１又は２以上のタグ識別子に関連付けられ、タグ識別子のうちの少なくとも１つのタグ識別子が、いくつかの可能なタグ値(tag values)を有する、前記記憶するステップと、いくつかのノードのうちの第１のノードに関するデータ系統の表現を求める要求を少なくとも１つのプロセッサを使用して処理するステップとを含む。前記処理するステップは、第１のノードといくつかのタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、第１のタグ識別子のいくつかの可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセット(subset)を決定すること、及び第１のノードに関するデータ系統を決定するために、第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースする（traverse）ことを含む。データ系統は、（１）第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含む。データ系統を決定することは、それぞれのトラバースされるノードに関して、少なくとも部分的にトラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することを含む。
【０００６】
態様は、以下の１又は２以上の特徴を含み得る。
【０００７】
データ系統を決定することは、それぞれのトラバースされるノードに関して、トラバースされるノードが第１のタグ識別子に関連付けられないか、若しくはトラバースされるノードが第１のタグ識別子に関連付けられ、第１のサブセットの少なくとも１つのタグ値に関連付けられる場合にデータ系統にトラバースされるノードを追加すること、又はトラバースされるノードが第１のタグ識別子に関連付けられ、第１のタグ識別子のいくつかの可能なタグ値の第１のサブセットの少なくとも１つのタグ値に関連付けられない場合にデータ系統からトラバースされるノードを除外することを含む可能性がある。
【０００８】
データ系統からトラバースされるノードを除外すると、第１の系統のパスのトラバースが、終了される可能性がある。前記方法は、第１のタグ識別子に関連付けられ、第１のタグ識別子のいくつかの可能なタグ値の第１のサブセットの少なくとも１つのタグ値に関連付けられないいくつかのノードの第１のサブセットを決定するために、いくつかのノードのうちのノードをトラバースする前にいくつかのノードを分析するステップを含む可能性がある。データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することは、トラバースされるノードがいくつかのノードの第１のサブセットに含まれるかどうかを決定することを含む可能性がある。データ系統にトラバースされるノードを追加すべきかどうかを決定することは、トラバースされるノードがいくつかのノードの第１のサブセットに含まれない場合にデータ系統にトラバースされるノードを追加し、トラバースされるノードがいくつかのノードの第１のサブセットに含まれる場合にデータ系統からトラバースされるノードを除外することを含む可能性がある。
【０００９】
いくつかのノードの少なくとも一部のノードが、いくつかのノードのその他のノードの中に入れ子にされる(nested)可能性がある。ノードの入れ子にされた階層のより低いレベルのノードに関連するタグ識別子及びタグ値のタグ識別子に関連するサブセットが、ノードの入れ子にされた階層のより高いレベルのノードに関連するタグ識別子及びタグ値のタグ識別子に関連するサブセットを上回る優先度を与えられる可能性がある。第１の系統のパスに沿ってノードをトラバースすることは、第１のノードから始まるノードを有向リンクの方向と反対の方向にトラバースすることを含む可能性がある。
【００１０】
前記方法は、有向グラフの仕様を生じさせるステップであって、いくつかのノードのうちの１又は２以上が計算を表し、いくつかのノードのうちの１又は２以上が計算の実行中に受け取られるか又は計算によって生成されるデータ要素を表し、有向リンクが計算とデータ要素との間の系統の関係を表す前記ステップをさらに含む可能性がある。いくつかのノードのうちの１又は２以上は、いくつかのノードのうちの１又は２以上のその他のノードのグループ分けを表す可能性がある。第１のタグ識別子のいくつかの可能なタグ値の第１のサブセットは、第１のノードに関連付けられる１又は２以上のタグ値からなる可能性がある。
【００１１】
第１のタグ識別子のいくつかの可能なタグ値の第１のサブセットは、ユーザ入力(user input)から受け取られる１又は２以上のタグ値からなる可能性がある。前記方法は、第１のノードに関するデータ系統を決定するために第１のノードから有向リンクのいくつかの系統のパスに沿ってノードをトラバースするステップであって、データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的にトラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することを含む前記ステップをさらに含む可能性がある。前記方法は、デフォルトでデータ系統に第１のノードを追加するステップをさらに含む可能性がある。
【００１２】
別の態様においては、概して、コンピュータ可読媒体に記憶された、コンピューティングシステムにおいて系統情報を管理するためのソフトウェアが、前記コンピューティングシステムに、いくつかのノードと、いくつかのノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様をデータストレージシステムに記憶することであって、ノードの少なくとも一部が、いくつかのタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、いくつかのタグ識別子のうちの少なくとも１つのタグ識別子が、いくつかの可能なタグ値を有する、前記記憶することと、いくつかのノードのうちの第１のノードに関するデータ系統の表現を求める要求を少なくとも１つのプロセッサを使用して処理することとを行わせるための命令を含む。前記処理することは、第１のノードといくつかのタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、第１のタグ識別子のいくつかの可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに第１のノードに関するデータ系統を決定するために、第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、データ系統が、（１）第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的にトラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む。
【００１３】
別の態様においては、概して、系統情報を管理するためのコンピューティングシステムが、いくつかのノードと、いくつかのノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様を記憶するデータストレージシステムであって、ノードの少なくとも一部が、いくつかのタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、いくつかのタグ識別子のうちの少なくとも１つのタグ識別子が、いくつかの可能なタグ値を有する、前記データストレージシステムと、いくつかのノードのうちの第１のノードに関するデータ系統の表現を求める要求を処理するように構成された少なくとも１つのプロセッサとを含む。前記処理することは、第１のノードといくつかのタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、第１のタグ識別子のいくつかの可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに第１のノードに関するデータ系統を決定するために、第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、データ系統が、（１）第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的にトラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む。
【００１４】
別の態様においては、概して、系統情報を管理するためのコンピューティングシステムが、いくつかのノードと、いくつかのノードの間のそれぞれの系統の関係を表す有向リンクとを含む有向グラフの仕様を記憶するための手段であって、ノードの少なくとも一部が、いくつかのタグ識別子のうちの１又は２以上のタグ識別子に関連付けられ、いくつかのタグ識別子のうちの少なくとも１つのタグ識別子が、いくつかの可能なタグ値を有する、前記記憶するための手段と、複数のノードのうちの第１のノードに関するデータ系統の表現を求める要求を処理するための手段とを含む。前記処理することは、第１のノードといくつかのタグ識別子のうちの少なくとも第１のタグ識別子との間の関連付けを決定し、第１のタグ識別子のいくつかの可能なタグ値のうちの少なくとも１つ且つ全数未満の第１のサブセットを決定すること、並びに第１のノードに関するデータ系統を決定するために、第１のノードから有向リンクの第１の系統のパスに沿ってノードをトラバースすることであって、データ系統が、（１）第１のノードの上流の有向リンクの一方向の上流の系統のパスからなるディペンデンシー系統、及び（２）第１のノードの下流の有向リンクの一方向の下流の系統のパスからなるインパクト系統のうちの片方又は両方を含み、データ系統を決定することが、それぞれのトラバースされるノードに関して、少なくとも部分的にトラバースされるノードに関連するいずれかのタグ識別子又はタグ値に基づいて、データ系統にトラバースされるノードを追加すべきか又はデータ系統からトラバースされるノードを除外すべきかを決定することを含む、前記トラバースすることを含む。
【００１５】
態様は、１又は２以上の以下の利点を含む可能性がある。
【００１６】
いくつかの包括的な態様においては、本明細書において説明される手法が、ユーザが系統タグの形態の追加的な情報によってノードを拡張した系統図に適用され得る。フィルタリングによって選択されたオブジェクトに隣接するか又はフィルタリングによって選択されたオブジェクトの直接の系統又はインパクトパス(impact path)内のオブジェクトだけに系統を制限することなく特定のユーザ定義の次元（dimension）が目標にされ得るように系統図をフィルタリングするために、系統タグが使用される。
【００１７】
本明細書において説明される手法は、その他の技術（例えば、単純なフィルタリング又は系統要約（Lineage Summarization））よりも選択的な方法で複雑性を減らすために使用され得る。例えば、一部の系統図の複雑性の１つの原因は、正規化及び非正規化動作を実行するノードであり、系統タグの使用は、本明細書においてより詳細に説明されるように、そのような系統図の複雑性を減らすのに役立つ可能性がある。
【００１８】
手法は、それぞれが列挙値(enumerated values)の独自の組を有する異なる種類のタグをユーザが定義することを可能にすることによって選択性を実現する。それぞれの種類のタグは、独自の独立したフィルタリングの次元として働く。また、タグは、正規化及び非正規化を実行するノードなどに関する系統図の構成に基づいて自動的に定義され得る。
【００１９】
一部の例においては、どのノードをフィルタリングされたデータ系統図に含め、どのノードをフィルタリングされたデータ系統図から除外すべきかを選択するためのアルゴリズムが、系統図のノードを歩き（walk）、（タグに関連付けられたすべてのノードの）遭遇したタグをアクティブなタグの組と比較することによって何を実行すべきかを決定する。
【００２０】
利点の中でもとりわけ、本明細書において説明される手法は、図を、アクティブなタグを有するアイテムの上流及び下流のノードに単純に制限しない。その代わりに、タグのないノードも、図の中に残る。したがって、手法は、列挙型の組(an enumerated set)の望ましくないメンバーの上流又は下流にあるノードの極めて正確な削除を可能にする。有利なことに、この選択性は、単純なフィルタリング又は系統要約（例えば、データ若しくは過剰に詰め込まれたオブジェクト（overloaded object）の正規化／非正規化）によって解決され得ない問題を解決する能力を提供する。
【００２１】
データ処理システムの複雑さが増したので、データ系統図も次第に複雑になっており、単一のビューの中にそれぞれのアイコンによって表される多くのノード（例えば、集合的に「ノード」と呼ばれるデータノード及びデータ変換ノード）を提示する。データ系統図においてユーザに対して提示されるノードの数が増えるにつれて、データ系統図は理解するのが難しくなる可能性がある。
【００２２】
一部の例において、データ処理グラフは、多くの部分的に重なり合うデータ系統のパスを含み、概して、ユーザは、それらのデータ系統のパスのうちの数個に関心がある。例えば、データ処理グラフの上流の部分においては、例えば、地理的領域に基づいてデータを処理する多くの異なるシステムが存在する可能性がある。データ処理グラフの中間の部分においては、グラフの上流の部分からのデータが、グループ分けされ、グラフの下流の部分においては、グループ分けされたデータが、処理される。ユーザは、単一の地理的領域に関する系統のパスを分析することに関心がある可能性がある。
【００２３】
本明細書において説明される手法は、所与のデータ処理システム内で、互いに関連する特定のノードはユーザが見ることに関心がある同じノードであることが多いという認識を利用する。本明細書において説明される手法においては、互いに関連するノードの組が、系統タグを使用して関連付けられる。そのとき、ノードは、ユーザが見ることに関心のあるノードのみを含むフィルタリングされたデータ系統図をユーザが生じさせることを可能にするために、系統タグに基づいてフィルタリングされ得る。
【００２４】
本発明のその他の特徴及び利点は、以下の説明及び請求項から明らかになるであろう。
【図面の簡単な説明】
【００２５】
【図１】系統のフィルタリングの特徴を含むデータ処理システムのブロック図である。
【図２ａ】系統タグを有するノードを含むデータ系統図である。
【図２ｂ】Ｒｅｇｉｏｎ：ＵＳに関する第１のフィルタリングされたデータ系統図である。
【図３】フィルタリングアルゴリズムのブロック図である。
【図４】選択されたノード及びブラックリストに追加されたノードを有する図２ａのデータ系統図である。
【図５】第１のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図６】第２のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図７】第３のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図８】第４のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図９】第５のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図１０】第６のデータ系統のパスがトラバースされる図２ａのデータ系統図である。
【図１１】無関係なノードが除外される図２ａのデータ系統図である。
【図１２】Ｒｅｇｉｏｎ：ＵＳ，ＭＥＸに関する第２のフィルタリングされたデータ系統図である。
【図１３】データ正規化及び非正規化を実行するように構成されたコンピュータプログラムのデータ系統図である。
【図１４】いくつかのノードに関連する系統タグを含む図１３のデータ系統図である。
【図１５】ブラックリストに追加された特定のノードを有する図１３のデータ系統図である。
【図１６】系統タグに基づくフィルタリングのプロセス中の図１３のデータ系統図である。
【図１７】フィルタリングされたデータ系統図である。
【発明を実施するための形態】
【００２６】
図１は、系統タグに基づくデータ系統フィルタリング技術が使用され得るデータ処理システム１０の例を示す。システム１０は、ストレージデバイス、又はオンラインデータストリームへの接続などのデータの１又は２以上のソースを含み得るデータソース１２を含み、それらの１又は２以上のソースのそれぞれは、さまざまなフォーマット（例えば、データベーステーブル(database tables)、スプレッドシートファイル(spreadsheet files)、フラットテキストファイル(flat text files)、又はメインフレーム(mainframe)によって使用されるネイティブフォーマット(native format)）のいずれかでデータを記憶又は提供し得る。実行環境１４は、実行モジュール１３を含む。実行環境１４は、例えば、ＵＮＩＸオペレーティングシステムのバージョンなどの好適なオペレーティングシステムの制御下の１又は２以上の多目的コンピュータ上でホストされる可能性がある。例えば、実行環境１４は、ローカルの（例えば、対称型マルチプロセッシング（ＳＭＰ，symmetric multi-processing）コンピュータなどのマルチプロセッサシステム）又はローカルに分散された（例えば、クラスタ若しくは超並列処理（ＭＰＰ，massively parallel processing）システムとして接続された複数のプロセッサか、或いは遠隔の又は遠隔に分散された（例えば、ローカルエリアネットワーク（ＬＡＮ，local area network）及び／若しくは広域ネットワーク（ＷＡＮ，wide-area network）を介して接続された複数のプロセッサ）か、或いはこれらの任意の組合せかのいずれかの複数の中央演算処理装置（ＣＰＵ，central processing unit）或いはプロセッサコアを用いるコンピュータシステムの構成を含むマルチノード並列コンピューティング環境(multiple-node parallel computing environment)を含む可能性がある。
【００２７】
データソース１２を提供するストレージデバイスは、実行環境１４のローカルにあり、例えば、実行環境１４をホストするコンピュータに接続されたストレージ媒体（例えば、ハードドライブ１８）に記憶される可能性があり、又は実行環境１４のリモートにあり、例えば、（例えば、クラウドコンピューティングインフラストラクチャによって提供される）リモート接続を介して実行環境１４をホストするコンピュータと通信するリモートシステム（例えば、メインフレーム２０）上でホストされる可能性がある。
【００２８】
システム１０は、開発者３０がデータ処理コンピュータプログラム２７（例えば、データフローグラフ）を規定し、実行環境１４によってアクセスされ得るデータストレージシステム２６にプログラムを記憶することができる開発環境２８を含む。実行モジュール１３は、コンピュータプログラム２７に従ってデータソースからのデータを処理して出力データ２４を生じさせる。出力データ２４は、データソース１２若しくはデータストレージシステム２６に戻して記憶されるか、又はそれ以外の方法で使用される可能性がある。開発環境２８は、一部の実施形態において、（データ処理構成要素又はデータセットを表す）頂点間の（作業要素（work element）、すなわち、データのフローを表す）有向リンクによって接続された頂点を含むデータフローグラフとしてアプリケーションを開発するためのシステムである。例えば、そのような環境は、参照により本明細書に組み込まれる「Managing Parameters for Graph-Based Applications」（グラフに基づくアプリケーションのパラメータ管理）と題された米国特許出願公開第２００７／００１１６６８号明細書により詳細に説明されている。そのようなグラフに基づく計算を実行するためのシステムは、参照により本明細書に組み込まれる「EXECUTING COMPUTATIONS EXPRESSED AS GRAPHS」（グラフとして表現される計算の実行）と題された米国特許第５，９６６，０７２号明細書に説明されている。このシステムによって作成されるデータフローグラフは、プロセス間で情報を移動するため及びプロセスに関する実行の順序を定義するためにグラフの構成要素によって表される個々のプロセスに情報を出し入れするための方法を提供する。このシステムは、任意の利用可能な方法からプロセス間通信の方法を選択するアルゴリズムを含む（例えば、グラフのリンクに従った通信系統のパスは、ＴＣＰ／ＩＰ若しくはＵＮＩＸドメインソケットを使用するか、又はプロセス間でデータを渡すために共有メモリを使用する可能性がある）。
【００２９】
システム１０は、ユーザ３１（例えば、企業ユーザ又はデータ設計者）がデータ系統図を要求し、見ることができる企業環境２９を含む。データ系統図を生じさせるために、企業環境２９は、コンピュータプログラム２７の異なる部分に対応する計算を表すデータ変換ノード（例えば、異なるデータフローグラフ又はデータフローグラフ内の異なる構成要素）を特徴付けるメタデータ(metadata)と、データ系統図を生じさせるためにコンピュータプログラム２７によってアクセスされるか又は生じさせられるデータノード（例えば、データソース１２からのデータセット又は出力データ２４に対応するデータセット）を特徴付けるメタデータとを含むシステムメタデータを分析するデータ系統モジュール２５を含む。
【００３０】
一部の例において、データ変換ノード及び／又はデータノードを特徴付けるメタデータは、（「系統タグ」と呼ばれることがある）データ系統タグを含む。極めて広く、各系統タグは、タグ識別子と、いくつかの可能なタグ値とを有する。例えば、１つの例示的な系統タグは、タグ識別子「Ｒｅｇｉｏｎ」及び可能なタグ値「Ｕ．Ｓ．，Ｕ．Ｋ．，Ｍｅｘｉｃｏ，Ｃａｎａｄａ」を有する可能性がある。
【００３１】
コンピュータプログラム２７のノード（すなわち、データ変換ノード及び／又はデータノード）の少なくとも一部は、１又は２以上の系統タグ及び系統タグの可能なタグ値のサブセットに関連付けられ、サブセットは、１又は２以上の系統タグの可能なタグ値のうちの少なくとも１つ且つ全数未満を含む。
【００３２】
図２ａを参照すると、コンピュータプログラム２７に関する例示的なエンドツーエンドのデータ系統図１００は、いくつかのデータノード１０２、いくつかのデータ変換ノード１０４、及びいくつかのコンテナノード１０６を含み、これらのすべてのノードは、有向リンク１０８によって相互接続される。
【００３３】
特に、図１００は、第１のデータ変換ノード１１０、第２のデータ変換ノード１１２、第３のデータ変換ノード１１４、第４のデータ変換ノード１１６、第５のデータ変換ノード１１８、第６のデータ変換ノード１２０、第７のデータ変換ノード１２２、第８のデータ変換ノード１２４、第９のデータ変換ノード１２６、第１０のデータ変換ノード１２８、第１１のデータ変換ノード１３０、第１２のデータ変換ノード１３２、及び第１３のデータ変換ノード１３４を含む。図１００は、第１のデータノード１３６及び第２のデータノード１３８を含む。図１００は、第１のコンテナノード１４０、第２のコンテナノード１４２、第３のコンテナノード１４４、及び第４のコンテナノード１４６を含む。
【００３４】
第１のデータ変換ノード１１０は、「Ｒｅｇｉｏｎ」系統タグに関連付けられる。この例において、「Ｒｅｇｉｏｎ」系統タグは、３つの可能なタグ値「ＵＳ，ＣＡ，ＭＥＸ」を有する。第１の変換ノード１１０は、「ＵＳ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットに関連付けられる。第３のデータ変換ノード１１４は、「Ｒｅｇｉｏｎ」系統タグと、「ＭＥＸ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第４のデータ変換ノード１１６は、「Ｒｅｇｉｏｎ」系統タグと、「ＵＳ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第５のデータ変換ノード１１８は、「Ｒｅｇｉｏｎ」系統タグと、「ＣＡ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第６のデータ変換ノード１２０は、「Ｒｅｇｉｏｎ」系統タグと、「ＵＳ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。
【００３５】
第７のデータ変換ノード１２２は、「Ｒｅｇｉｏｎ」系統タグと、「ＣＡ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第８のデータ変換ノード１２４は、「Ｒｅｇｉｏｎ」系統タグと、「ＭＥＸ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第９のデータ変換ノード１２６は、「Ｒｅｇｉｏｎ」系統タグと、「ＵＳ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第１３のデータ変換ノード１３４は、「Ｒｅｇｉｏｎ」系統タグと、「ＣＡ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。
【００３６】
第１のデータノード１３６は、「Ｒｅｇｉｏｎ」系統タグと、「ＵＳ，ＭＥＸ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。第２のデータノード１３８は、「Ｒｅｇｉｏｎ」系統タグと、「ＣＡ」を含む「Ｒｅｇｉｏｎ」系統タグの可能なタグ値のサブセットとに関連付けられる。
【００３７】
１  フィルタリングされたデータ系統の生成
一部の例において、図２ａのエンドツーエンドのデータ系統図１００は、フィルタリングされたデータ系統図を生じさせるためにデータ系統モジュール２５によって処理される。図２ｂを参照すると、フィルタリングされたデータ系統図２０１の一例は、「Ｒｅｇｉｏｎ」系統タグ及び「ＵＳ」系統タグ値に従ってフィルタリングされるエンドツーエンドのデータ系統図１００のバージョンである。図に見られるように、フィルタリングされたデータ系統図２０１は、「Ｒｅｇｉｏｎ」系統タグ識別子に関連付けられ、「ＣＡ」のみ又は「ＭＥＸ」のみを含む系統タグ値を有するノードがデータ系統から除外されるので図２ａのエンドツーエンドのデータ系統図１００に比べて大幅に簡素化される。
【００３８】
図３〜１２を参照して以下で詳細に説明されるように、図１２の第１のフィルタリングされたデータ系統図２００などのフィルタリングされたデータ系統図に至るために、ユーザは、ノードを選択し、ノードに関するフィルタリングされたデータ系統を決定するようにデータ系統モジュール２５に命令する。データ系統モジュール２５は、まず、選択されたノードと１又は２以上のタグ識別子との間の関連付けを決定する。選択されたノードに関連する各タグ識別子に関して、データ系統モジュール２５は、タグ識別子の可能なタグ値のうちのどのタグ値が選択されたノードに関連付けられるかを決定する。概して、ユーザは、選択されたノードに関連付けられるべき任意の数のタグ値を選択し得る。選択されたタグ値は、単一のタグ値（例えば、図２ｂの例と同様に「ＵＳ」）又は複数のタグ値（例えば、図１２の例と同様に「ＵＳ」及び「ＭＥＸ」）などの可能なタグ値のサブセットを表す可能性がある。概して、タグ識別子に関連する可能なタグ値の全数未満の一部のある数のタグ値が、選択される。
【００３９】
それから、データ系統モジュール２５は、選択されたノードから始まる１又は２以上の系統のパスをトラバースして、選択されたノードに関するフィルタリングされたデータ系統を決定する。概して、それぞれの系統のパスは、有向リンクによって接続された１又は２以上のノードを含む。データ系統モジュール２５は、１又は２以上のノードをトラバースするとき、１又は２以上のトラバースされるノードに関連するすべてのタグ識別子又はタグ値に基づいて、フィルタリングされたデータ系統にノードを追加すべきか又はフィルタリングされたデータ系統からノードを除外すべきかを判断する。
【００４０】
図３を参照すると、一部の例において、データ系統モジュール２５が系統のパスをトラバースするとき、系統のパスに沿ったノードがフィルタリングされたデータ系統図に含めるためにマークされる(marked)べきか又はフィルタリングされたデータ系統図から除外するためにマークされるべきかを決定するためにフィルタリングアルゴリズム３００が使用される。
【００４１】
特に、データ系統モジュール２５が系統のパス上の訪問先ノード３５０に至るとき、訪問先ノード３５０及び選択されたノード３５２が、フィルタリングアルゴリズム３００に与えられる。
【００４２】
フィルタリングアルゴリズム３００の第１のステップ３５４において、訪問先ノード３５０に関連するいずれかの系統タグ識別子が選択されたノード３５２に関連する系統タグ識別子に一致するかどうかを決定するためのテストが実施される。系統タグ識別子のいずれも一致しない場合、アルゴリズムは、第２のステップ３５６に進み、第２のステップ３５６において、訪問先ノード３５０は、フィルタリングされたデータ系統図に含めるためにマークされる。訪問先ノード３５０と選択されたノード３５２との両方に関連する１又は２以上の系統タグ識別子が一致する場合、アルゴリズムは、第３のステップ３５８に進む。
【００４３】
第３のステップ３５８において、それぞれの特定された一致する系統タグ識別子に関して、系統タグ識別子に関する訪問先ノード３５０に関連する１又は２以上の系統タグ値が、系統タグ識別子に関する選択されたノード３５２に関連する１又は２以上の系統タグ値に一致するかどうかを決定するためのテストが実施される。系統タグ識別子に関する訪問先ノード３５０に関連する１又は２以上の系統タグ値が系統タグ識別子に関する選択されたノード３５２に関連する１又は２以上の系統タグ値に一致する場合、アルゴリズムは、第２のステップ３５６に進み、第２のステップ３５６において、訪問先ノード３５０は、フィルタリングされたデータ系統図に含めるためにマークされる。
【００４４】
或いは、系統タグ識別子に関する訪問先ノード３５０に関連する系統タグ値のうちのいずれも系統タグ識別子に関する選択されたノード３５２に関連する系統タグ値のうちのいずれとも一致しない場合、アルゴリズムは、第４のステップ３６０に進み、第４のステップ３６０において、訪問先ノード３５０は、フィルタリングされたデータ系統図から除外するためにマークされる。
【００４５】
一部の例において、フィルタリングアルゴリズム４００は、データ系統モジュール２５がエンドツーエンドのデータ系統内の系統のパスをトラバースするときに実施される。その他の例においては、ノードがデータ系統の計算のために選択されると、いずれの系統のパスがトラバースされるよりも前に、選択されたノード以外のエンドツーエンドのデータ系統内のすべてのノードにフィルタリングアルゴリズムが適用される。フィルタリングアルゴリズム３００がフィルタリングされたデータ系統図から除外するためにマークするすべてのノードは、「ブラックリスト」に追加される。それから、データ系統モジュール２５は、選択されたノードから始まる系統のパスをトラバースする。データ系統モジュール２５によって訪問される各ノードにおいて、データ系統モジュール２５は、ブラックリストを検索して、訪問先ノードがブラックリストに載っているかどうかを決定する。訪問先ノードがブラックリストに載っている場合、系統のパスのトラバーサル(traversal)は、終了され、訪問先ノードは、フィルタリングされたデータ系統に含められない。
【００４６】
図４を参照すると、ユーザは、フィルタリングされたデータ系統の生成のために図２ａのエンドツーエンドのデータ系統図１００の第１のデータノード１３６を選択済みである。上述のように、第１のデータノード１３６は、「Ｒｅｇｉｏｎ」系統タグ識別子に関連付けられ、「ＵＳ，ＭＥＸ」を含み、系統タグ値「ＣＡ」を含まない「Ｒｅｇｉｏｎ」系統タグ識別子の可能なタグ値のサブセットに関連付けられる。
【００４７】
「Ｒｅｇｉｏｎ」系統タグ識別子の「ＣＡ」系統タグ値は第１のデータノード１３６に関連する系統タグ値のサブセットに含まれないので、データ系統モジュール２５は、「Ｒｅｇｉｏｎ」系統タグ識別子に関連付けられ、且つ「ＣＡ」のみを含むタグ値のサブセットを有するノードをデータ系統から除外するように構成される。
【００４８】
一部の例においては、第１のデータノード１３６の選択を受け取った後、データ系統モジュール２５は、エンドツーエンドのデータ系統図１００を処理して、ブラックリストを生じさせる。上述のように、ブラックリストは、第１のデータノード１３６以外のすべてのノードを調べて、「Ｒｅｇｉｏｎ」系統タグ識別子に関連し、「ＣＡ」のみを含むタグ値のサブセットを有するノードを特定することによって生じさせられる。図４のエンドツーエンドのデータ系統にフィルタリングアルゴリズム３００を適用することは、第５のデータ変換ノード１１８、第７のデータ変換ノード１２２、第１３のデータ変換ノード１３４、及び第２のデータノード１３８がブラックリストに追加される結果をもたらす。図４において、ブラックリストに追加されるノードは、斜線のパターンによって塗りつぶされる。
【００４９】
ブラックリストが生じさせられると、第１のデータノード１３６から始まる系統のパス（つまり、有向リンク１０８によって接続されたノード）のそれぞれは、エンドツーエンドの系統図１００の端のノードが訪問されるか、又はブラックリストのノードが訪問されるかのどちらかまでトラバースされる。エンドツーエンドのデータ系統図１００の端のノードが到達される場合、ノードにつながり、ノードを含む系統のパス全体が、フィルタリングされたデータ系統に含められる。ブラックリストのノードが到達される場合、系統のパスのトラバーサルが、終了され、ブラックリストのノードにつながっているがそのノードを含まない系統のパスが、フィルタリングされたデータ系統に含められる。
【００５０】
図５を参照すると、第１のデータノード１３６と第９のデータ変換ノード１２６との間の第１の系統のパスが、データ系統モジュール２５によってトラバースされる。第１のデータノード１３６がユーザによって選択されたので、第１のデータノード１３６は、デフォルトでフィルタリングされたデータ系統に含めるためにマークされる。そして、第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８が、トラバースされる。それから、ブラックリストが第１０のデータ変換ノード１２８を含むかどうかを決定するために、ブラックリストが検索される。第１０のデータ変換ノード１２８は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。それから、第１０のデータ変換ノード１２８と第９のデータ変換ノード１２６との間の有向リンク１０８が、トラバースされる。そして、ブラックリストが第９のデータ変換ノード１２６を含むかどうかを決定するために、ブラックリストが検索される。第９のデータ変換ノード１２６は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第９のデータ変換ノード１２６はエンドツーエンドの系統図１００の端にあるので、第１の系統のパスのトラバーサルは完了している。
【００５１】
図６を参照すると、第１のデータノード１３６と第１のデータ変換ノード１１０との間に延びる第２の系統のパスが、データ系統モジュール２５によってトラバースされる。第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８は既にトラバースされたので、データ系統モジュール２５は、第１０のデータ変換ノード１２８と第４のデータ変換ノード１１６との間の有向リンク１０８をトラバースすることによってそのデータ系統モジュール２５のトラバーサルを始める。
【００５２】
系統モジュール２５が第４のデータ変換ノード１１６に到達するとき、ブラックリストが第４のデータ変換ノード１１６を含むかどうかを決定するために、ブラックリストが検索される。第４のデータ変換ノード１１６は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第４のデータ変換ノード１１６は、第１のコンテナノード１４０に入れ子にされる第２のコンテナノード１４２に含まれることに留意されたい。第１のコンテナノード１４０も第２のコンテナノード１４２も、いかなる系統タグ識別子にも関連付けられず、したがって、どちらも、ブラックリストに含まれない。第２の系統のパスは第１のコンテナノード１４０及び第２のコンテナノード１４２の境界をトラバースし、どちらのコンテナノードもブラックリスト内にないので、第１のコンテナノード１４０と第２のコンテナノード１４２との両方が、フィルタリングされたデータ系統に含めるためにマークされる。一部の例において、コンテナノードが系統タグ識別子及び値によってマークされる場合、そのコンテナノードの子孫ノード（すなわち、子ノード及びそのまた子）のすべては、同じ系統タグ識別子及び値によってマークされることに留意されたい。したがって、ブラックリストは、最も低いレベルのノードに基づいて構築される可能性がある。
【００５３】
それから、データ系統モジュール２５は、第４のデータ変換ノード１１６と第１のデータ変換ノード１１０との間の有向リンク１０８をトラバースする。系統モジュール２５が第１のデータ変換ノード１１０に到達するとき、ブラックリストが第１のデータ変換ノード１１０を含むかどうかを決定するために、ブラックリストが検索される。第１のデータ変換ノード１１０は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第１のデータ変換ノード１１０はエンドツーエンドの系統図１００の端にあるので、第２の系統のパスのトラバーサルは完了している。
【００５４】
図７を参照すると、第１のデータノード１３６と第１のデータ変換ノード１１０との間に延びる第３の系統のパスが、データ系統モジュール２５によってトラバースされる。やはり、第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８は既にトラバースされたので、データ系統モジュール２５は、第１０のデータ変換ノード１２８と第６のデータ変換ノード１２０との間の有向リンク１０８をトラバースすることによってそのデータ系統モジュール２５のトラバーサルを始める。
【００５５】
系統モジュール２５が第６のデータ変換ノード１２０に到達するとき、ブラックリストが第６のデータ変換ノード１２０を含むかどうかを決定するために、ブラックリストが検索される。第６のデータ変換ノード１２０は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第６のデータ変換ノード１２０は、第１のコンテナノード１４０に入れ子にされる第３のコンテナノード１４４に含まれることに留意されたい。第１のコンテナノード１４０も第３のコンテナノード１４４も、いかなる系統タグ識別子にも関連付けられず、したがって、どちらも、ブラックリストに含まれない。第２の系統のパスは第１のコンテナノード１４０及び第３のコンテナノード１４４の境界をトラバースし、どちらのコンテナノードもブラックリスト内にないので、第１のコンテナノード１４０と第３のコンテナノード１４４との両方が、フィルタリングされたデータ系統に含めるためにマークされる。
【００５６】
それから、データ系統モジュール２５は、第６のデータ変換ノード１２０と第１のデータ変換ノード１１０との間の有向リンク１０８をトラバースする。系統モジュール２５が第１のデータ変換ノード１１０に到達するとき、ブラックリストが第１のデータ変換ノード１１０を含むかどうかを決定するために、ブラックリストが検索される。第１のデータ変換ノード１１０は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第１のデータ変換ノード１１０は系統図１００の端にあるので、第３の系統のパスのトラバーサルは完了している。
【００５７】
図８を参照すると、第１のデータノード１３６と第２のデータ変換ノード１１２との間に延びる第４の系統のパスが、データ系統モジュール２５によってトラバースされる。第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８は既にトラバースされたので、データ系統モジュール２５は、第１０のデータ変換ノード１２８と第５のデータ変換ノード１１８との間の有向リンク１０８をトラバースすることによってそのデータ系統モジュール２５の横断を始める。
【００５８】
系統モジュール２５が第５のデータ変換ノード１１８に到達するとき、ブラックリストが第５のデータ変換ノード１１８を含むかどうかを決定するために、ブラックリストが検索される。第５のデータ変換ノード１１８は、ブラックリストに載っているので、フィルタリングされたデータ系統から除外される。第５のデータ変換ノード１１８がブラックリストに載っていると決定されたので、第４の系統のパスのトラバーサルが、終了される。
【００５９】
図９を参照すると、第１のデータノード１３６と第３のデータ変換ノード１１４との間に延びる第５の系統のパスが、データ系統モジュール２５によってトラバースされる。第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８は既にトラバースされたので、データ系統モジュール２５は、第１０のデータ変換ノード１２８と第８のデータ変換ノード１２４との間の有向リンク１０８をトラバースすることによってそのデータ系統モジュール２５のトラバーサルを始める。
【００６０】
系統モジュール２５が第８のデータ変換ノード１２４に到達するとき、ブラックリストが第８のデータ変換ノード１２４を含むかどうかを決定するために、ブラックリストが検索される。第８のデータ変換ノード１２４は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第８のデータ変換ノード１２４は、第１のコンテナノード１４０に入れ子にされる第４のコンテナノード１４６に含まれることに留意されたい。第１のコンテナノード１４０及び第４のコンテナノード１４６のどちらも、いかなる系統タグ識別子にも関連付けられず、したがって、どちらも、ブラックリストに含まれない。第５の系統のパスは第１のコンテナノード１４０及び第４のコンテナノード１４６の境界をトラバースし、どちらのコンテナノードもブラックリスト内にないので、第１のコンテナノード１４０と第４のコンテナノード１４６との両方が、フィルタリングされたデータ系統に含めるためにマークされる。
【００６１】
それから、データ系統モジュール２５は、第８のデータ変換ノード１２４と第３のデータ変換ノード１１４との間の有向リンクをトラバースする。系統モジュール２５が第３のデータ変換ノード１１４に到達するとき、ブラックリストが第３のデータ変換ノード１１４を含むかどうかを決定するために、ブラックリストが検索される。第３のデータ変換ノード１１４は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。第３のデータ変換ノード１１４は系統図１００の端にあるので、第５の系統のパスのトラバーサルは完了している。
【００６２】
図１０を参照すると、第１のデータノード１３６と第２のデータ変換ノード１１２との間に延びる第６の系統のパスが、データ系統モジュール２５によってトラバースされる。第１のデータノード１３６と第１０のデータ変換ノード１２８との間の有向リンク１０８は既にトラバースされたので、データ系統モジュール２５は、第１０のデータ変換ノード１２８と第１１のデータ変換ノード１３０との間の有向リンク１０８をトラバースすることによってそのデータ系統モジュール２５のトラバーサルを始める。
【００６３】
系統モジュール２５が第１１のデータ変換ノード１３０に到達するとき、ブラックリストが第１１のデータ変換ノード１３０を含むかどうかを決定するために、ブラックリストが検索される。第１１のデータ変換ノード１３０は、ブラックリストに載っていないので、フィルタリングされたデータ系統に含めるためにマークされる。
【００６４】
それから、データ系統モジュール２５は、第１１のデータ変換ノード１３０と第７のデータ変換ノード１２２との間の有向リンクをトラバースする。系統モジュール２５が第７のデータ変換ノード１２２に到達するとき、ブラックリストが第７のデータ変換ノード１２２を含むかどうかを決定するために、ブラックリストが検索される。第７のデータ変換ノード１２２は、ブラックリストに載っているので、フィルタリングされたデータ系統から除外される。第７のデータ変換ノード１２２がブラックリストに載っていると決定されたので、第６の系統のパスのトラバーサルが、終了される。
【００６５】
図１１を参照すると、第１２のデータ変換構成要素１３２、第１３のデータ変換構成要素１３４、及び第２のデータノード１３８は、第１のデータノード１３６から始まる系統のパス上にないので、デフォルトでフィルタリングされたデータ系統から除外される。
【００６６】
第２のデータ変換ノード１１２は、有向リンクのいずれのトラバーサル中にも到達されず、したがって、フィルタリングされたデータ系統から除外されることに留意されたい。
【００６７】
図１２を参照すると、第１のデータノード１３６から始まるすべての系統のパスがトラバースされると、フィルタリングされたデータ系統に含めるためにマークされていないすべてのノードが、エンドツーエンドのデータ系統図１００から削除され、フィルタリングされたデータ系統図２００をもたらす。フィルタリングされたデータ系統図２００は、「Ｒｅｇｉｏｎ」系統タグ識別子に関連し、「ＣＡ」のみを含む系統タグ値を有するノードを除外することに留意されたい。
【００６８】
２  正規化／非正規化
図１３を参照すると、コンピュータプログラム２７の単純で例示的なエンドツーエンドのデータ系統図１３００が、入力フォーム１３６０、正規化データ変換ノード１３６２、データノード１３６４、非正規化データ変換ノード１３６６、及びレポートフォーム１３６８を含む。入力フォーム１３６０及びレポートフォーム１３６８は、より高いレベルのデータ要素内に入れ子にされた異なるデータ要素に対応する複数のデータノードをそれぞれがそれ自体の中に含むデータノードである。この例において、入れ子にされたデータ要素は、各フォームのレコード内の異なるフィールドを表す。
【００６９】
正規化データ変換ノード１３６２は、データノード１３５４によって表されるデータストアに記憶されているデータ要素を正規化する正規化動作を実施し、非正規化データ変換ノード１３６６は、データノード１３５４によって表されるデータストアから取り出されているデータ要素を非正規化する非正規化動作を実施する。正規化動作の「正規化」及び非正規化動作の「非正規化」の特定の実施形態は、変わり得るが、概して、以下の特徴を有する。データ要素を正規化することは、複数のデータ要素に対応するレコードを少なくとも１つのフィールドに関して共通のフォーマットを有する複数のレコードに変換することを含む。データ要素を非正規化することは、少なくとも１つのフィールドに関して共通のフォーマットを有する複数のレコードを複数のデータ要素に対応する単一のレコードに変換することを含む。以下は、データ系統図１３００に関連するそのような動作の例である。
【００７０】
入力フォーム１３６０は、モバイル電話番号を含む第１のフィールド１３７０、職場の電話番号を含む第２のフィールド１３７２、及び家庭の電話番号を含む第３のフィールド１３７４を含む。動作中、正規化データ変換ノード１３６２は、入力フォーム１３６０を受け取り、入力フォーム１３６０に含まれる電話番号をデータノード１３６４に記憶するのに好適な正規化された形態に変換する。一部の例において、正規化データ変換ノード１３６２は、入力フォーム１３６０に含まれる電話番号を［Ｐｈｏｎｅ  Ｎｕｍｂｅｒ  Ｔｙｐｅ，Ｐｈｏｎｅ  Ｎｕｍｂｅｒ］の形態に変換し、Ｐｈｏｎｅ  Ｎｕｍｂｅｒは、３つの値、すなわち、Ｍｏｂｉｌｅ、Ｗｏｒｋ、及びＨｏｍｅを有する列挙データタイプである。本明細書に記載の態様に関連して、データ要素タイプ及びデータ要素値を有するデータ要素をデータ要素タイプフィールド及びデータ要素値フィールドを含むデータ構造に変換する上述のプロセスが、データ要素の「正規化」と呼ばれる。正規化された電話番号は、後で使用するためにデータノード１３６４に記憶される。
【００７１】
非正規化データ変換ノード１３６６は、データノード１３６４から正規化された電話番号を読み、正規化された電話番号を非正規化してそれらの電話番号の元の形態に戻す。本明細書に記載の態様に関連して、正規化されたデータ構造をデータ要素タイプ及びデータ要素値を有するデータ要素に変換して戻す上述のプロセスが、データ要素の「非正規化」と呼ばれる。そして、非正規化データ変換ノード１３６６は、モバイル電話番号を、モバイル電話番号を記憶するためのレポートフォーム１３６８の第４のフィールド１３７６、職場の電話番号を記憶するためのレポートフォーム１３６８の第５のフィールド１３７８、及び家庭の電話番号を記憶するためのレポートフォーム１３６８の第６のフィールド１３８０に書き込む。
【００７２】
上述の正規化／非正規化プロセスは、正規化された列挙データタイプへのデータアイテムの変換及び正規化された列挙データタイプからのデータアイテムの変換が原因で、通常のデータ系統計算システムを扱うことが難しい可能性がある。例えば、ユーザがレポートフォーム１３６８の第４のフィールド１３７６のモバイル電話番号に関するデータ系統図を必要とする場合、通常の方法で生じさせられたデータ系統図は、レポートフォーム１３６８の第４のフィールド１３７６のモバイル電話番号、非正規化データ変換ノード１３６６、データノード１３６４、正規化データ変換ノード１３６２、及び入力フォーム１３６８の第１のフィールド１３７０を含む。
【００７３】
通常の方法で生じさせられたデータ系統図は、入力フォーム１３６０の第２のフィールド１３７２の職場の電話番号及び入力フォーム１３６０の第３のフィールド１３７４の家庭の電話番号も含む。そのような通常のデータ系統図は、第２のフィールド１３７２の職場の電話番号及び第３のフィールド１３７４の家庭の電話番号が実際にはレポートフォーム１３６８の第４のフィールド１３７６のモバイル電話番号に関するデータ系統の一部ではないので正しくない。
【００７４】
図１４を参照すると、正しくないデータ系統図の生成を防止するために、エンドツーエンドのデータ系統図１３００内の（基本的にデータノードである）さまざまなフィールドが、系統タグ識別子「Ｐｈｏｎｅ  Ｎｕｍ」及び可能な系統タグ値「Ｍｏｂｉｌｅ」、「Ｗｏｒｋ」、及び「Ｈｏｍｅ」を有する系統タグによってタグ付けされる(tagged)。特に、第１のフィールド１３７０は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｍｏｂｉｌｅ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。第２のフィールド１３７２は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｗｏｒｋ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。第３のフィールド１３７４は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｈｏｍｅ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。
【００７５】
第４のフィールド１３７６は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｍｏｂｉｌｅ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。第５のフィールド１３７８は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｗｏｒｋ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。第６のフィールド１３８０は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子及び「Ｈｏｍｅ」だけを含む可能な系統タグ値のサブセットを有する系統タグによってタグ付けされる。
【００７６】
図１５を参照すると、ユーザがフィルタリングされたデータ系統図の生成のためにモバイル電話番号を含む第４のフィールド１３７６を選択するとき、データ系統モジュール２５は、まず、第４のフィールド１３７６と１又は２以上の系統タグ識別子との間の関連付けを決定する。この場合、第４のフィールド１３７６は、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子に関連付けられる。それから、データ系統モジュール２５は、「Ｐｈｏｎｅ  Ｎｕｍ」タグ識別子の可能なタグ値のうちのどのタグ値が第４のフィールド１３７６に関連付けられるかを決定する。この場合、「Ｍｏｂｉｌｅ」タグ値は、第４のフィールド１３７６に関連する唯一のタグ値である。
【００７７】
そして、データ系統モジュール２５は、エンドツーエンドのデータ系統図１３００を処理して、ブラックリストを生じさせる。上述のように、ブラックリストは、選択された第４のフィールド１３７６以外のエンドツーエンドのデータ系統図１３００内のすべてのノード及びフィールドを調べて、「Ｐｈｏｎｅ  Ｎｕｍ」系統タグ識別子に関連し、「Ｗｏｒｋ」及び／又は「Ｈｏｍｅ」だけを含むタグ値のサブセットを有するノード及びフィールドを特定することによって生じさせられる。エンドツーエンドのデータ系統図１３００に図３のフィルタリングアルゴリズム３００を適用することは、第２のフィールド１３７２、第３のフィールド１３７４、第５のフィールド１３７８、及び第６のフィールド１３８０がブラックリストに追加される結果をもたらす。図１５において、ブラックリストに追加されるデータ系統のフィールドは、斜線のパターンによって塗りつぶされる。
【００７８】
図１６を参照すると、データ系統モジュール２５は、そのとき、第４のフィールド１３７６から始まるすべての系統のパスをトラバースして、どのノード及びフィールドがフィルタリングされたデータ系統に含められ、フィルタリングされたデータ系統から除外されるのかを決定する。図に見られるように、「Ｗｏｒｋ」及び「Ｈｏｍｅ」系統タグ値のみによってタグ付けされたフィールドは、データ系統モジュール２５によってフィルタリングされたデータ系統から除外するためにマークされ、一方、「Ｍｏｂｉｌｅ」系統タグ値のみによってタグ付けされたフィールドは、フィルタリングされたデータ系統に含めるためにマークされる。
【００７９】
図１７を参照すると、第４のフィールド１３７６から始まるすべての系統のパスがトラバースされると、フィルタリングされたデータ系統に含めるためにマークされていないすべてのノード及びフィールドが、エンドツーエンドのデータ系統図１３００から削除され、フィルタリングされたデータ系統図１７００をもたらす。通常の系統生成技術によってフィルタリングされたデータ系統図に誤って含められる第２のフィールド１３７２及び第３のフィールド１３７４が、フィルタリングされたデータ系統図１７００からは除外されることに留意されたい。
【００８０】
３  代替形態
上の系統タグに基づくフィルタリングの例のデータ系統図のノードは特定の順序でトラバースされるが、トラバーサルの多くの異なる順序が使用され得ることに留意すべきである。例えば、トラバーサルの幅優先順序又はトラバーサルの深さ優先順序が、使用され得る。
【００８１】
上の系統タグに基づくフィルタリングの例においては、最初のノードが選択され、最初のノードに関連する系統タグ及び系統タグ値が系統図をフィルタリングするために使用される。しかし、一部の例においては、ユーザが、最初のノードを選択し、データ系統モジュールが、データ系統図をトラバースして、最初のノードに関する完全なデータ系統を決定し、完全なデータ系統をフィルタリングするために使用され得るすべての系統タグ及び系統タグ値を発見する。そして、最初のノードに関する完全なデータ系統が、発見された系統タグ及び系統タグ値と一緒にユーザに提示される。それから、ユーザは、発見された１又は２以上の系統タグ及び系統タグ値をフィルタリングパラメータとして選択することによって完全なデータ系統をフィルタリングすることができる。その他の例においては、データ系統モジュールがデータ系統図をトラバースするとき、到達された系統タグ及び系統タグ値のリストが、保守される。そして、図の第１の部分をトラバースする間にリストに追加される系統タグ及び系統タグ値の一部又はすべてが、図の第２の部分をフィルタリングするために、図の第２の上流部分をトラバースする間に使用される可能性がある。
【００８２】
上述の手法は、概してデータ系統図の生成に関するが、インパクト分析図を生じさせるためにも使用され得る。
【００８３】
一部の例においては、系統の階層内の異なるレベルの２又は３以上のノード（例えば、コンテナノード及びコンテナノード内のデータ変換ノード）に関連する系統タグが、衝突する可能性がある。一部の例においては、系統の階層内の最も低いレベルのノードが、系統タグとして選択される。
【００８４】
上述の例においては、データ変換ノードが、矢印によって表されるフローによって互いに直接接続されるものとして示されている。しかし、一部の例においては、第１の構成要素の出力を第２の構成要素の入力に接続するフローが、第１の構成要素から出るデータによって書き込まれ、第２の構成要素の入力によって読まれるデータストレージ要素を暗黙的に含む可能性があることに留意すべきである。
【００８５】
４  実施形態
上述のデータ系統生成手法は、好適なソフトウェアを実行するコンピューティングシステムを用いて履行され得る。例えば、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、（揮発性及び／又は不揮発性メモリ及び／又はストレージ要素を含む）少なくとも１つのデータストレージシステム、（少なくとも１つの入力デバイス又はポートを用いて入力を受け取るため、及び少なくとも１つの出力デバイス又はポートを用いて出力を与えるための）少なくとも１つのユーザインターフェースを含む（分散、クライアント／サーバ、又はグリッドなどのさまざまなアーキテクチャである可能性がある）１又は２以上のプログラミングされた又はプログラミング可能なコンピューティングシステム上で実行される１又は２以上のコンピュータプログラムのプロシージャを含み得る。ソフトウェアは、例えば、データフローグラフの設計、構成、及び実行に関連するサービスを提供するより大きなプログラムの１又は２以上のモジュールを含む可能性がある。プログラムのモジュール（例えば、データフローグラフの要素）は、データリポジトリに記憶されたデータモデルに準拠するデータ構造又はその他の編成されたデータとして履行され得る。
【００８６】
ソフトウェアは、ＣＤ−ＲＯＭ又は（例えば、多目的若しくは専用のコンピューティングシステム若しくはデバイスによって読み取り可能な）その他のコンピュータ可読媒体などの有形の非一時的媒体上に提供されるか、或いはそのソフトウェアが実行されるコンピューティングシステムの有形の非一時的媒体にネットワークの通信媒体を介して配信される（例えば、伝搬信号に符号化される）可能性がある。処理の一部又はすべては、専用のコンピュータ上で、又はコプロセッサ若しくはフィールドプログラマブルゲートアレイ（ＦＰＧＡ，field-programmable gate array）若しくは専用の特定用途向け集積回路（ＡＳＩＣ，application-specific integrated circuit）などの専用のハードウェアを使用して実施される可能性がある。処理は、ソフトウェアによって規定された計算の異なる部分が異なるコンピューティング要素によって実施される分散された方法で履行される可能性がある。それぞれのそのようなコンピュータプログラムは、本明細書において説明された処理を実施するためにストレージデバイスの媒体がコンピュータによって読み取られるときにコンピュータを構成し、動作させるために、多目的又は専用のプログラミング可能なコンピュータによってアクセスされ得るストレージデバイスのコンピュータ可読ストレージ媒体（例えば、ソリッドステートメモリ若しくは媒体、又は磁気式若しくは光学式媒体）に記憶されるか又はダウンロードされることが好ましい。本発明のシステムは、コンピュータプログラムで構成された有形の非一時的媒体として履行されると考えられる可能性もあり、そのように構成された媒体は、本明細書において説明された１又は２以上処理ステップを実施するために特定の予め定義された方法でコンピュータを動作させる。
【００８７】
本発明のいくつかの実施形態が、説明された。しかしながら、上述の説明は、添付の請求項の範囲によって画定される本発明の範囲を例示するように意図されており、限定するように意図されていないことを理解されたい。したがって、その他の実施形態も、添付の請求項の範囲内にある。例えば、本発明の範囲を逸脱することなくさまざまな修正がなされ得る。さらに、上述のステップの一部は、順序に依存しない可能性があり、したがって、説明された順序とは異なる順序で実施される可能性がある。
【図１】
0006469878.tif 000002
【図２ａ】
0006469878.tif 000003
【図２ｂ】
0006469878.tif 000004
【図３】
0006469878.tif 000005
【図４】
0006469878.tif 000006
【図５】
0006469878.tif 000007
【図６】
0006469878.tif 000008
【図７】
0006469878.tif 000009
【図８】
0006469878.tif 000010
【図９】
0006469878.tif 000011
【図１０】
0006469878.tif 000012
【図１１】
0006469878.tif 000013
【図１２】
0006469878.tif 000014
【図１３】
0006469878.tif 000015
【図１４】
0006469878.tif 000016
【図１５】
0006469878.tif 000017
【図１６】
0006469878.tif 000018
【図１７】
0006469878.tif 000019