JP7843374B2 - グラフを記憶及び再構成する方法 - Google Patents

Description

本発明は記憶装置にグラフを記憶する方法に関する。

ネットワーク、特に有向ネットワークは、複数のエンティティに沿ったシステムパラメータのフローを符号化する。ネットワークの一例はサプライチェーンネットワークであり、システムパラメータは、材料若しくは計画された配送、又はそれらの組み合わせであり得る。ネットワークの別の例はプロセスネットワークであり、システムパラメータは、材料若しくはビジネス文書又はそれらの任意の組み合わせなどのプロセスステップの出力であり得る。

サプライチェーンネットワークでは、材料及び／若しくは商品がどのように流れているか、並びに／又は材料がどのように配送されるように計画されているかを理解することが重要である。サプライチェーンネットワークにおける材料の流れ及び／又は計画された配送は、様々なユースケース、例えば、原材料不足によりどの完成品が影響され得るかの推定、又は製品の部品、それぞれの部品などに基づいて製品のカーボンフットプリントの計算を促進する。これらのネットワークは、任意の数の施設及び材料の組み合わせを含むことができ、以下では在庫管理単位（ＳＫＵ；stock keeping unit）と表される。

サプライチェーンネットワークの典型的なシナリオでは、いくつかのＳＫＵが、生産段階並びに商品の配送における異なる段階を表す複数のレイヤに関与する。実際、生産及び流通はいずれも、複数の製造業者に散在している場合が多い。ＳＫＵのレイヤは、部分的に生産された製品にわたる原材料から完成品自体までの範囲に及び得る。原材料と完成品との間の様々なレイヤに起因して、通常、サプライチェーンネットワークにまたがる多くのＳＫＵが含まれる。

同様に、ビジネスプロセス（例えば、注文プロセス）又は技術的製造プロセス（例えば、サプライチェーンネットワークのＳＫＵで実行されるプロセス）などの単一のプロセスは、実際には、多くの場合、（大規模な）プロセスネットワークの一部である。これにより、プロセスは、コンピュータシステムにおいて又はコンピュータシステムを用いて実行され、いくつかのプロセスステップを含み得る。プロセスの実行は、プロセスインスタンスと呼ばれる。各プロセスステップは、実行中にデータを作成でき、このデータは、プロセスが実行されるコンピュータシステムに記憶される、又はプロセスが実行されるコンピュータシステムを用いて記憶される。

プロセスインスタンスをそれらのプロセスステップと共にプロセスプロトコルに記憶することが知られており、そこから、古典的なプロセスマイニング技法を使用して単一のプロセスインスタンスを効率的に分析することができる。しかし、現実的なシナリオでは、異なるプロセスのインスタンスは、互いに分離されているとは考えにくい。異なるプロセスのインスタンスは、むしろプロセスネットワークにおいて接続されている。しかし、プロセスネットワークにおいて、古典的なプロセスマイニングは、２つ以上の異なるプロセスのプロセスインスタンス間の相互作用を分析することができない。実際には、プロセスネットワークは広範に分散し、ほとんどの組織が独立した連続するプロセスのセットを実行するだけでなく、むしろ互いにかつ他の組織のプロセスと相互作用している多くのプロセスを含んでいる。

技術的には、サプライチェーンネットワーク又はプロセスネットワークなどのネットワークは、グラフを使用して表され得る。グラフは、通常、ノード及びエッジからなり、ノードは、個別のネットワークのエンティティを表すことができ、エッジは、個別のネットワーク内のエンティティ間の相互作用を表すことができる。

実際には、ノード（エンティティ）は、通常、切り離されて記憶される。例えば、サプライチェーンネットワークでは、ＳＫＵは通常、異なる（リレーショナル）データテーブルに編成される。プロセスネットワークでは、単一のプロセスはプロセスプロトコルに互いに独立して記憶される。

実際には、現代のネットワークにおける相互接続されたＳＫＵ及び／又は相互接続されたプロセスのランドスケープは、絶えず変化する。したがって、１つのＳＫＵを別のＳＫＵに（例えば、リレーショナルデータベース内のテーブルを結合することを介して）手動で接続するか、又は１つのプロセスインスタンスを別のプロセスインスタンスに手動で接続するかのいずれかである従来のアプローチは、非常に非効率的であり、エラーを起こしやすい。そのため、最新のネットワーク、特にサプライチェーンネットワーク及び／又はプロセスネットワークを表すグラフを記憶するための通常のアプローチは直接的に、そのようなネットワークの不正確な再構築及びその後の分析をもたらす場合がある。

そのようなネットワークに含まれる大量のデータに起因して、ネットワーク内のエンティティを表す、グラフ内のノードの手動による接続は計算上の要求が非常に多いので、ネットワークを表すグラフを記憶するための従来のアプローチは、更に、タイムアウトをもたらす場合が多い。

したがって、本発明の目的は、効率的な方法で、グラフの構成要素、すなわちそのノード及び／又はエッジの柔軟な操作を可能にするように、ネットワークを表すグラフを記憶装置に記憶する方法を提供することである。

本発明によれば、この目的は、独立請求項に記載の方法によって解決される。本発明の好ましい実施形態及び更なる発展形態は、従属請求項において定義される。

したがって、グラフを記憶装置に記憶するための、コンピュータにより実行される方法が提供される。グラフは複数のノード及び複数の有向エッジを含む。各有向エッジは開始ノードと終端ノードとを接続し、各有向エッジは終端ノードに接続された入力エッジと開始ノードに接続された出力エッジとから構成される。

グラフはネットワークを表し、各ノードはネットワークのエンティティを表す。各有向エッジは２つのエンティティ間の関係を表す。

この方法は、
記憶装置を用いて記憶されたデータ構造の第１のレコードに各開始ノードを記録し、データ構造の第２のレコードに各終端ノードを記録することを含む。各レコードは少なくとも、
－ノードの識別子が記憶されるいくつかの第１の属性の組み合わせと、
－入力エッジの識別子が記憶されるいくつかの第２の属性の組み合わせと、
－出力エッジの識別子が記憶されるいくつかの第３の属性の組み合わせと、を含む。

方法は、第１のレコードに、いくつかの第１の属性の組み合わせにおける開始ノードの識別子と、いくつかの第３の属性の組み合わせにおける一意関係識別子とを記憶することを更に含む。一意関係識別子はネットワーク内の経路に沿ったステップを表す。言い換えれば、一意関係識別子はネットワークの２つのエンティティ間の相互作用を表す。

方法は、第２のレコードに、いくつかの第１の属性の組み合わせにおける終端ノードの識別子と、いくつかの第２の属性の組み合わせにおける一意関係識別子とを記憶することを更に含む。

第１のレコードのいくつかの第３の属性の組み合わせの値と一致する第２のレコードのいくつかの第２の属性の組み合わせの値は、開始ノードと終端ノードとの間の有向エッジを定義する。

好ましくは、本方法は、グラフを生成するために、第２のレコードのいくつかの第２の属性の組み合わせの値を、第１のレコードのいくつかの第３の属性の組み合わせの値と一致させることによって、開始ノードと終端ノードとの間の有向エッジを決定することを更に含む。

本発明による方法は、ネットワークを表すグラフを、どのノードがどのノードに隣接しているか、すなわち、ノードの近傍についての先験的知識なしに、記憶装置に記憶することができるという技術的利点を有する。データ構造は、ノードが接続される入力エッジ又は出力エッジに割り当てられる一意関係識別子を作成するための所定の規則に従って、異なる個々の生データソースからノードとともに記録することができる。データ構造を記録する時点では、グラフの有向エッジはまだ定義されていない。有向エッジ及び有向エッジを有するグラフ自体は、記録されたデータ構造からしか出現しない、すなわち、第２のレコードのいくつかの第２の属性の組み合わせ及び第１のレコードのいくつかの第３の属性の組み合わせに割り当てられた同一の一意関係識別子を見つけることからしか出現しない。更なる技術的な利点は、ノードの（すなわちノード間の）先行－後続関係が明示的に記憶される必要がないことであり、これにより、データの量を大幅に低減する。

従来、グラフは、最初に決定され、すなわち、その構造が知られ、それに応じて固定され、その後、グラフを記憶装置に記憶することができる。対照的に、本発明によれば、ネットワーク内のエンティティを記述するデータのみが、ネットワーク内の関係の知識なしに、データ構造に記録される。ネットワークを表すグラフは、最終的にデータ構造から得られる。

したがって、本発明によるグラフの記憶は非常に柔軟である。グラフの構造及びスキーマを予め決定する必要はない。更に、典型的には複数の生データテーブルをもたらすグラフデータを、いかなる結合演算も必要とせずにデータ構造に記録できるので、本発明によるグラフの記憶は非常に効率的でロバストである。データ構造を記録するために、どのノードが開始ノード及び／又は終端ノードであるかを知る必要があるだけである。これは、典型的には、関連する生データのメタデータから導出される。

本発明による方法を使用してグラフを記憶する柔軟性により、（急速に）変化する生データに常に適合したグラフを効率的に記憶することが可能になる。

データ構造に記憶された各一意関係識別子について、第２のレコードのいくつかの第２の属性の組み合わせの値を第１のレコードのいくつかの第３の属性の組み合わせの値と一致させることによって、データ構造に記憶されたグラフが得られる。実際には、データ構造に記録された各一意関係識別子についてマッチングステップを処理した後に、データ構造から２つ以上のグラフが得られる可能性がある。

一実施形態では、データ構造は、ネットワークを表示するためのグラフ視覚化デバイスに提供される。

ネットワークを表示するために、データ構造からグラフを読み出すことができ、開始ノードと終端ノードとの間の有向エッジは、第２のレコードの第２の属性及び第１のレコードの第３の属性を一意関係識別子に対して一致させることによって形成される。

一実施形態では、データ構造はテーブルであり、特にリレーショナルデータテーブルである。テーブルは、（リレーショナル）データモデルに関連付けられている。

一実施形態では、ネットワークはサプライチェーンネットワークであり、エンティティは、材料と施設の組み合わせ、特に在庫管理単位（ＳＫＵ）である。サプライチェーンネットワーク内の２つのエンティティ間の関係は、材料表（bill of materials）及び／又は配送表（bill of distributions）を使用することによって確立される。

典型的には、材料表は生産ネットワークを定義し、配送表は配送ネットワークを定義する。本発明の実施形態によれば、本方法はまた、組み合わされた生産及び配送ネットワークを表すグラフの記憶を可能にする。本実施形態では、一意関係識別子は、２つのエンティティ間の関係を特徴付けるデータ、特に、材料表識別子、代替材料表識別子及び施設識別子、並びに／又は受入施設識別子及び材料識別子を含む。

一意関係識別子は、生データから所定の規則に従って構築される。生産ネットワークの場合、在庫管理単位を互いに接続するために、材料表識別子、代替材料表識別子、及び施設識別子の組み合わせ、特に連結（concatenation）を使用することが有用であることが証明されている。配送ネットワークの場合、受入施設識別子及び材料識別子の組み合わせ、特に連結から一意関係識別子を構築することが特に有用であることが証明されている。記憶されるグラフによって表されるネットワークのコンテキストに応じて、一意関係識別子はまた、生データに見出される異なる識別子から構築されてもよい。

一実施形態では、ノード識別子はケースキーを含む。

サプライチェーンネットワークの場合、ケースキーは、材料識別子と施設識別子との組み合わせであり得る。

一実施形態では、少なくとも１つのノードは、少なくとも１つの入力エッジに接続された終端ノードと、少なくとも１つの出力エッジに接続された開始ノードの両方である。この方法は、少なくとも１つのノードの各ノードを少なくとも１つのレコードに記録することを更に含む。少なくとも１つのレコードの各レコードにおいて、各ノードの識別子は、いくつかの第１の属性の組み合わせに割り当てられ、１つの入力エッジの第１の一意関係識別子は、いくつかの第２の属性の組み合わせに割り当てられ、１つの出力エッジの第２の一意関係識別子は、いくつかの第３の属性の組み合わせに割り当てられる。

好ましくは、少なくとも１つのレコードの各レコードにおいて、１つの入力エッジの第１の一意関係識別子が、いくつかの第２の属性の組み合わせに割り当てられるか、又は１つの出力エッジの第２の一意関係識別子が、いくつかの第３の属性の組み合わせに割り当てられる、のいずれかである。

好ましい実施形態は、ノードが起点又は目的地である有向エッジの数にかかわらず、１つのノードで記録されたちょうど１つの入力エッジ又は出力エッジが常に存在するという利点を有する。その結果、本発明によるグラフを記憶するのに必要なレコードの数が減少する。

一実施形態では、いくつかの第１の属性の組み合わせにおける第１の属性の数は１であり、及び／又はいくつかの第２の属性の組み合わせにおける第２の属性の数は１であり、及び／又はいくつかの第３の属性の組み合わせにおける第３の属性の数は１である。

一実施形態では、ネットワークはプロセスネットワークであり、プロセスネットワークは、異なるプロセスの２つ以上のプロセスインスタンスと、少なくとも２つの異なるプロセスのプロセスインスタンスのプロセスステップ間の相互作用とを含む。各ノードは、プロセスインスタンスのプロセスステップを表す。一意関係識別子は、第１のプロセスのプロセスインスタンスの一部を形成する開始ノードと第２のプロセスのプロセスインスタンスの一部を形成する終端ノードとの間の信号、特に、終端ノードに提供される開始ノードの出力を表す。データ構造は、データ構造が拡張プロセスプロトコルを形成するように、プロセスインスタンス内のプロセスステップのシーケンスが記憶される第４の属性を更に含む。

実際には、プロセスネットワークはユビキタスであるが、プロセスデータの従来の記憶は、異なるプロセスのインスタンス間の相互作用を欠いている。したがって、入力エッジ及び出力エッジを記憶する属性によるプロセスプロトコルの拡張は、プロセスインスタンスの線形シーケンスを非線形に接続して（プロセス）グラフを形成できるという利点を有する。

一般的なネットワークについて上記で概説したように、プロセスネットワークを表すグラフの特性（すなわち、構造／スキーマ）は、グラフが記憶装置に記憶される時点では未知であり得る。その代わりに、実行されたプロセスインスタンスによって生成された生データは、データ構造内に記憶され、ネットワークのエンティティ間の相互作用を表すための一意関係識別子（それぞれの入力エッジ及び出力エッジによって表される）が、生データから作り上げられる。（プロセス）グラフは、データ構造から効率的に生成され、続いて分析され得る。更に、（プロセス）グラフは、効率的に、すなわち、単にデータ構造内のレコードを作成、更新、及び／又は削除することによって、適合させることもできる。

本実施形態では、いくつかの第１の属性の組み合わせは、個別のプロセスステップのプロセスインスタンスの一意識別子が記憶される、ケース属性と、個別のプロセスステップの識別子が記憶される、アクティビティ属性とを含む。

好ましくは、データ構造は、記憶装置の揮発性メモリに排他的に記憶される。

更に、ネットワーク内のフローを制御する方法が提供され、ネットワークはグラフによって表され、グラフは本発明に従って記憶される。

本発明の詳細及び特徴、並びに本発明の具体的な実施形態は、図面に関連する以下の説明から導き出すことができる。

図１は、ネットワークを表すグラフの有向エッジの視覚化であって、グラフが本発明の実施形態に従って記憶されている、視覚化を示す図である。 図２は、製品が２つの部品から生産される基本的な生産ネットワークを表すグラフの視覚化を示す図である。 図３は、ある製品が別の製品を生産するのに使用される生産ネットワークを表すグラフの視覚化を示す図である。 図４は、基本的な配送ネットワークを表すグラフの視覚化を示す図である。 図５は、組み合わされた生産及び配送ネットワークの例を表すグラフの視覚化を示す図である。 図６は、本発明の実施形態によるネットワークを表すグラフを記憶する方法のフローチャートである。 図７は、プロセスネットワークを表すグラフの視覚化を示す図である。 図８は、プロセスネットワークを表すグラフのシーケンス図であって、グラフが本発明の実施形態に従って記憶されている、シーケンス図である。 図９は、第１のデータ構造に記憶されたグラフにフィルタリングする方法の実施形態のフローチャートである。 図１０は、図９の方法の実施形態のステップＢのフローチャートである。

ネットワークは、情報を効率的に編成し通信するために産業全体にわたって使用される。ネットワークに含まれる情報を分析するには、ネットワークを記憶装置に記憶でき、例えばネットワーク上での計算をしばしば繰り返し実行することによってネットワークを評価できるように、ネットワークの技術的表現が必要とされている。

通常、グラフは、ネットワークの技術的表現として機能する。グラフの各エッジは、開始ノード及び終端ノードを接続又はリンクする。ノードは、ネットワークのエンティティの技術的表現であり、エッジは、ネットワーク内の２つのエンティティ間の関係の技術的表現である。

技術レベルでは、有向ネットワークは有向グラフによって表すことができる。有向グラフは複数のノード及び複数の有向エッジを含み、有向エッジは有向エッジが接続している２つのノードのうちの１つを指す。

開始ノードと終端ノードとの間の有向エッジは、開始ノードと終端ノードとの間の関係を表すことができ、この関係は、開始ノードから発行され、終端ノードによって受信される信号など、方向によって特徴付けられる。したがって、（有向）グラフの複数のリンクされた有向エッジは、ネットワークにわたる信号の経路を表すことができ、信号は、ネットワークの１つのエンティティを別のエンティティにリンクする。

図１は、ネットワークを表すグラフの有向エッジの視覚化を示しており、グラフは本発明の実施形態に従って記憶されている。

図１に示す有向エッジ１５；２５は、開始ノード１０を終端ノード２０に接続し、エッジ１５；２５は、開始ノード１０から終端ノード２０を指すように向けられている。サプライチェーンネットワークを表すグラフ１では、例えば、開始ノード１０は原材料／部品と施設との組み合わせを表すことができ、終端ノード２０は中間部品／製品と施設との組み合わせを表すことができる。プロセスネットワークを表すグラフ１では、例えば、開始ノード１０は第１のプロセスインスタンスのプロセスステップを表すことができ、終端ノード２０は第２のプロセスインスタンスのプロセスステップを表すことができる。

有向エッジ１５；２５は、開始ノード１０に接続された出力エッジ１５と、終端ノード２０に接続された入力エッジ１５と、から構成される。出力エッジ１５及び入力エッジ２５の両方に、一意関係識別子３０がそれぞれ割り当てられる。図１の場合のように、出力エッジ１５の一意関係識別子が入力エッジ２５の一意関係識別子とぴったり一致する場合、有向エッジ１５；２５が形成される。このように、一意関係識別子は、開始ノード１０と終端ノード２０とのペアを形成する接続手段として機能する。

一意関係識別子３０は、２つのエンティティ間の関係を特徴付けるデータ、特にネットワークの２つのエンティティをリンクする信号を含む。サプライチェーンネットワークでは、例えば、一意関係識別子３０は、材料表（ＢＯＭ）識別子及び代替材料表（代替ＢＯＭ）識別子及び施設識別子を含むことができる。材料の計画された配送をサプライチェーンネットワーク上にマッピングするために、一意関係識別子３０は、受入施設識別子及び材料識別子を含むことができる。グラフ１がプロセスネットワークを表す一実施形態では、一意関係識別子３０は、シリアル番号及び／又は注文、インボイス、返品などの参照番号などのビジネス文書に関連付けられた識別子を含むことができる。

一意関係識別子３０の技術的機能は、ネットワーク内のエンティティ間の組織内リンク／接続及び組織間リンク／接続の両方を確立することである。したがって、グラフ１が生産ネットワークを表す一実施形態では、施設識別子は、ＳＫＵが１つの施設内で正しく接続されることを保証するので、一意関係識別子３０の重要なパラメータである。グラフ１が計画された配送ネットワークを表す一実施形態では、異なる施設／工場のＳＫＵが正しく、すなわち、基礎となる配送表（ＢＯＤ）に従って、接続されていることを保証するために、受入施設識別子は、一意関係識別子３０の重要なパラメータである。グラフ１が製造プロセスネットワークを表す一実施形態では、シリアル番号は、製造プロセスにおける材料及び／又は部品の流れが、例えば製造プロセス全体の異なるプロセスインスタンスのプロセスステップ間で正しく確立されることを保証するので、一意関係識別子３０の重要なパラメータである。同様に、グラフ１がビジネスプロセスネットワークを表す一実施形態では、ビジネス文書に通常関連付けられた識別子は、一意関係識別子３０のための重要なパラメータである。一実施形態では、グラフ１は、サプライチェーンネットワーク、配送ネットワーク、及びプロセスネットワークの任意の組み合わせを表すことができる。

本発明によれば、図１に示す有向エッジ１５；２５は、対応する一意関係識別子３０とともにデータ構造内に開始ノード１０及び終端ノード２０を記録することから出現する。データ構造は、後に第１のデータ構造としても参照される。

一実施形態では、データ構造は、（リレーショナル）データテーブルであり、開始ノード１０及び終端ノード２０は、データテーブルの２つの行に記録される。データテーブルは、後に信号リンクテーブルとして参照される。図１の開始ノード１０及び終端ノード２０を信号リンクテーブルに記憶するのに必要な最小データセットを表１に示す。

表１のデータ構造の各レコードは、少なくとも、ノードの識別子が記憶されるいくつかの第１の属性の組み合わせと、入力エッジの識別子が記憶されるいくつかの第２の属性の組み合わせと、出力エッジの識別子が記憶されるいくつかの第３の属性の組み合わせと、を含む。表１において、第１の属性の数は１であり、すなわち、「ノード」とラベル付けされた１つの第１の属性が存在する。同様に、第２の属性の数及び第３の属性の数は１つである。この最小の例では、ノードは「Ａ」及び「Ｂ」によって識別される。他の例では、グラフ内のノードを識別する資格を有するいくつかの第１の属性は、グラフ内のノードを一意に参照するために組み合わされる必要があり得る。

表１の第２の属性は、「Ｓｉｇｎａｌ＿Ｉｎ」とラベル付けされている。第２の属性には、同じレコードの終端ノード２０に接続されている入力エッジ２５の一意関係識別子が記録される。ノードに接続された入力エッジは、そのノードが目的地である有向エッジである。図１の例では、終端ノード２０は、一意関係識別子「ＸＹＺ」を有する入力エッジ２５の目的地である。

表１の第３の属性は、「Ｓｉｇｎａｌ＿Ｏｕｔ」とラベル付けされている。第３の属性には、同じレコードの開始ノード１０に接続されている出力エッジ１５の一意関係識別子が記憶される。ノードに接続された出力エッジは、接続されたノードが起点である有向エッジである。図１の例では、一意関係識別子「ＸＹＺ」を有する出力エッジ１５の起点は、開始ノード１０である。

したがって、信号リンクテーブル内の第２の行の「Ｓｉｇｎａｌ＿Ｉｎ」属性の値が信号リンクテーブル内の第１の行の「Ｓｉｇｎａｌ＿Ｏｕｔ」属性の値と一致するので、有向エッジ１５；２５は、開始ノード１０に接続された出力エッジ１５と終端ノード２０に接続された入力エッジ２５とによって形成される。このようにして、データ構造に記憶されたグラフを確立し、分析のために準備／提供することができる。

複数の第２の属性及び／又は第３の属性に基づく複合一意関係識別子３０は、同一のデータ構造からの異なるグラフの生成を可能にし、グラフは、特に２つのノード間の有向エッジにおいて異なる。すなわち、ネットワーク内の２つのエンティティ間の様々な関係に関する洞察を効率的に得ることができる。

一実施形態では、図１に示す有向エッジ１５；２５は、プロセスネットワークにおける関係を表すことができる。表２は、有向エッジ１５；２５が出現するような、開始ノード１０及び終端ノード２０を記憶するのに必要なデータ構造の例を示し、この有向エッジ１５；２５はプロセスネットワークにおける関係を表す。

本例では、第１の属性の数は２である。第１の属性の組み合わせは、プロセスインスタンスが記憶される「ケースＩＤ」属性と、プロセスインスタンスに関連するプロセスステップが記憶される「アクティビティ」属性とから作成される。したがって、開始ノード１０は「１Ａ」によって識別され、終端ノード２０は「２Ｂ」によって識別される。

表２の例では、各ノード１５；２５は、２つの異なる相互接続されたプロセスインスタンスのプロセスステップを表す。表２に示すデータ構造の第２の属性及び第３の属性は、表１に提示されるデータ構造の第２の属性及び第３の属性に対応する。表２は、表１の属性「タイムスタンプ」によって表される、プロセスインスタンス内のプロセスステップのシーケンスが記憶される第４の属性を更に含む。

属性「ケースＩＤ」、「アクティビティ」、及び「タイムスタンプ」を含むプロセスプロトコルが知られている。本発明の実施形態によれば、プロセスプロトコルは、第２の属性「Ｓｉｇｎａｌ＿Ｉｎ」及び第３の属性「Ｓｉｇｎａｌ＿Ｏｕｔ」によって拡張され、これらは、プロセスグラフがプロセスプロトコルから出現するように、どのプロセスステップが別のプロセスステップに接続されるかについての情報を提供する。

図２は、製品が２つの部品から生産される基本的な生産ネットワークを表すグラフの視覚化を示す。

以下では、本発明の実施形態によるデータ構造からの図２に示すグラフ１の出現は、ＳＫＵ、すなわちサプライチェーンネットワークの施設及び材料の組み合わせに関する情報を含む生データテーブルから導出される。

本例では、図２のグラフ１が記憶されることになるデータ構造は、２つの生データテーブル（いずれも以下に提示する表３及び表４）から作成されたレコードが代入される。

表３は、材料表（ＢＯＭ）をＳＫＵにリンクする。これを達成するために、表３は、製品又は半製品を、それらのＢＯＭ識別子及びそれらの代替ＢＯＭ識別子とともに列挙している。したがって、表３のＳＫＵは、終端ノード２０によって技術的に表される。

表４は、個々のＢＯＭ及びその部品についての情報を含む。すなわち、表４は、ＢＯＭ（及び関連する代替ＢＯＭ）を、製品が製造されるＳＫＵにリンクする。したがって、表４のＳＫＵは、開始ノード１０によって技術的に表される。表４のカウンタ属性は、主キーを作成するために導入されていることに留意されたい。

本発明の実施形態では、一意関係識別子３０は、所定の規則、例えば、表３及び表４の各ノード１０；２０についての施設識別子、ＢＯＭ識別子、及び代替ＢＯＭ識別子の組み合わせ、特に連結に従って作成される。表３及び表４のノードは、データ構造に記録され、個別のノード識別子は、データ構造の第１の属性に記録される。各ノードについて、個別のノードに関連付けられた作成された一意関係識別子３０は、個別のノードが開始ノード１０であるか、それとも終端ノード２０であるかに応じて、第３の属性又は第２の属性に記録される。結果として得られる信号リンクテーブルを以下の表５に提示する。

ノード識別子は、材料識別子と施設識別子との組み合わせである。結果として生じる属性は、「ケースキー」とラベル付けされる。「ケースキー」属性では、材料識別子、例えば「Ｐ＿１２３」が、施設識別子、例えば「１００」と組み合わされている。

図２のグラフのノード１０；２０に接続された入力エッジ２５及び出力エッジ１５の一意関係識別子３０はそれぞれ、表３の、かつ表４の施設識別子（表５の下線）、ＢＯＭ識別子、及び代替ＢＯＭ識別子（表５の二重下線）を含む。

図２に視覚化されたグラフ１は、生産ネットワークを表すグラフを表示するために表５によるデータ構造が提供されるグラフ視覚化デバイスの出力であり得る。

図２の基本的な例は、従来のアプローチに対する本発明によるグラフ１を記憶する方法の技術的利点を説明する。生データテーブル、すなわち表３及び表４は、本質的にネットワークのエンティティに関するデータを含むが、従来のアプローチは、ネットワークを表すグラフを最初に作成し、次いで記憶するために、エンティティがネットワーク内でどのように接続されているかに関する更なる情報（例えば、構造及び／又はスキーマ情報）を必要とする。特に、接続は従来、データベース内の関連テーブルを結合することによって確立される。図２の例では、２つの生データテーブルしか存在しないが、実際には、ネットワークのエンティティを表す、数千ではなくても数百のデータテーブルが存在し得る。したがって、グラフを記憶するための本発明による方法を使用することは、複雑な結合演算が不要になるという技術的利点を有する。グラフ１のノード１０；２０は、独立して、すなわち、それらの近傍の知識なしに、基礎となるグラフ構造に正確にマッピングするデータ構造に記憶することができる。特に、全ての終端ノード２０は、それが接続される入力エッジ２５と共に記録され、全ての開始ノード１０は、それが接続される出力エッジ１５と共に記録される。その結果、グラフ１は、視覚化及び／又は分析が必要なときに、データベース内のテーブルを結合するなどの複雑な操作を必要とせずに、データ構造から簡単に読み出すことができる。

図２の基本的な例は、本発明によるグラフ１の記憶の効率性も示している。図２のグラフは、２つの有向エッジ１５；２５しか含まない。しかし、有向エッジはいずれも、ノード「Ｐ＿１２３－１００」への入力エッジ２５を含み、したがって、それは重複されている。しかし、本発明による方法は、ノード１０；２０及び入力エッジ２５又は出力エッジ１５の組み合わせの複製された記録などの冗長データを自動的に除去する。したがって、表５の３つのレコードは、図２に示すノード１０；２０及び出力／入力エッジ１５；２５の３つの組み合わせに正確に対応している。

図３は、ある製品が別の製品を生産するのに使用される生産ネットワークを表すグラフの視覚化を示す。

図３に示すグラフ１は、図２の例の拡張と考えることができる。２つの部品「Ｃ＿１２３」及び「Ｃ＿４５６」から生産される製品「Ｐ＿１２３」は、製品「Ｐ＿４５６」を生産するために更に使用される。したがって、製品「Ｐ＿１２３」は、１つの入力エッジ２５及び１つの出力エッジ１５の両方に接続されている。図３に示すグラフ１が出現するデータ構造の例を表６に与えられている。

表６は、５つのレコード、すなわち、入力エッジ２５又は出力エッジ１５を有するノード１０；２０のあらゆる組み合わせに対してちょうど１つのレコードを含む。したがって、第２の属性に記憶された第１の一意関係識別子を有する終端ノードとしてのノード「Ｐ＿１２３－１００」の１つのレコードと、第３の属性に記憶された第２の一意関係識別子を有する開始ノードとしてのノード「Ｐ＿１２３－１００」の１つのレコードと、が存在する。本例では、第１の一意関係識別子及び第２の一意関係識別子は、それらが構成される識別子（ＩＤ）によって単に表される。

本発明による方法を使用して、グラフ１によって表すことができる生産ネットワークを定義するＢＯＭを、専用データ構造に記憶することができる。データ構造は、計算的に効率的かつロバストな方法で（例えば、複雑な結合演算を回避することによって）グラフ１を記憶デバイス上に完全にマッピングすることができ、ノードを他のノードに接続することができ、それにより、生産ネットワークのＳＫＵを他のＳＫＵに接続し、両方が生産の入力又は出力として機能し得る。

図４は、基本的な配送ネットワークを表すグラフの視覚化を示す。

図４に示すグラフ１は、図２に示すグラフ１に非常に類似しているが、図４のグラフ１は、配送ネットワークを表し、図２のグラフ１は生産ネットワークを表す。配送ネットワークにおいて接続を確立するために、一意関係識別子３０は、受入施設識別子及び材料識別子の組み合わせ、特に連結から作成される。

図４に示すグラフ１は、施設「２００」の製品「Ｐ＿４５６」を外部調達する、すなわち施設「１００」及び施設「２００」から供給される例である。したがって、ノード「Ｐ＿４５６－２００」は、２つの有向エッジを介してノード「Ｐ＿４５６－１００」及びノード「Ｐ＿４５６－４００」に接続される。グラフ１を再構築できるデータ構造を表７に記載する。

図５は、組み合わされた生産及び配送ネットワークの例を表すグラフの視覚化を示す。

図５のグラフ１は、表６を表７で拡張したものであり、逆もまた同様である。本例は、特に、本発明の実施形態による記憶装置を用いて記憶されたグラフの拡張／適応が計算上非常に効率的であることを実証する。グラフを記憶する従来のアプローチでは、生データからグラフを作成するためのスキーマは、各ノードの近傍を計算するために適合される必要があり、近傍の計算は、複数の生データテーブルの結合を伴う。

本発明の実施形態によれば、図５のグラフは、以下に提示する表８に記憶することができる。

表８から出現するグラフ１は、組み合わされた生産及び組織間配送ネットワークを表す。本発明の実施形態に従って記憶されたグラフ１によって表される（サブ）ネットワークのコンテキストは、入力エッジ２５及び／又は出力エッジ１５に割り当てられる一意関係識別子３０を構築／作成するために、所定の規則を切り替えることによって簡単に切り替えることができる。したがって、ＢＯＭ接続論理は、ＢＯＤ接続論理と簡単にマージすることができる。

図５に示すようなグラフ１は、サプライチェーンネットワークにわたるＳＫＵの反復接続を提供し、これは、組織が、サプライチェーンネットワークの任意のＳＫＵにおいて生じる問題によって引き起こされるネットワーク内の影響を識別することを可能にする。例えば、購入注文が施設「１００」においてコンポーネント「Ｃ＿１２３」に対して遅れて実行されている場合、これは、製品「Ｐ＿１２３」を生産する施設「１００」の能力に影響を及ぼす。したがって、その後、遅れて実行されるこの購入注文は、施設「１００」から施設「２００」への製品「Ｐ＿１２３」の供給を中断させる可能性がある。

組織内で利用可能なデータソースに応じて、本発明によるグラフ１を記憶するこの全く同じアプローチを使用して、供給者ＥＲＰシステムからの供給データ、又は顧客ＥＲＰシステムからの顧客需要を表すノードなど、更に多くのノードをグラフに含めることができる。

図６は、本発明の実施形態による、ネットワークを表すグラフを記憶する方法のフローチャートを示す。

本発明の実施形態によれば、グラフを記憶装置に記憶する方法は、以下に概説するように、ステップＡ～Ｄに従い、任意選択のステップＥを伴う。

ステップＡにおいて、第１の属性、第２の属性及び第３の属性を含むデータ構造を初期化する。

ステップＢにおいて、グラフの各ノードに対してノード識別子を作成する。

ステップＣにおいて、グラフの各ノードに対して、ノードが接続される入力エッジ２５及び／又は出力エッジ１５のための一意関係識別子３０を作成する。

ステップＤにおいて、ノード識別子をデータ構造の第１の属性に記録し、個別の一意関係識別子３０を第２の属性又は第３の属性に記録する。

任意選択的に、ステップＥにおいて、グラフによって表されるネットワークを表示するために、データ構造をグラフ視覚化デバイスに提供する。

図７は、プロセスネットワークを表すグラフの視覚化を示す。

図１に関して説明したように、本発明の一実施形態では、データ構造から出現するグラフ１は、プロセスネットワークを表すことができる。単一のプロセスインスタンスは、アクティビティ又はプロセスステップの線形シーケンスからなるが、異なるプロセスインスタンスのプロセスステップは、信号によって接続されて、プロセスネットワークを形成することができる。信号は、１つのプロセスインスタンス又はケースから別のプロセスインスタンス又はケースへの直接送信をマークする。信号は、例えば、１つのプロセスによって作成され、別のプロセスによって消費される商品、又は新しいプロセスとして生じる電話呼を表すことができる。一般に、信号は、第２のプロセスのインスタンスへの入力となる第１のプロセスのインスタンスからの出力である。プロセスネットワークにおいて、信号は、１つ以上のアクティビティによって生まれ、１つ以上のアクティビティによって消費され得る。技術的には、信号は一意関係識別子３０によって表される。

プロセスインスタンスにおけるアクティビティの線形シーケンスを説明するために、本発明の実施形態によるデータ構造は、第４の属性によって拡張される。第４の属性には、プロセスインスタンス内のプロセスステップのシーケンスが記憶される。

図７に視覚化されたグラフ１が出現するデータ構造の例は、以下の表９に記載される。

表９のデータ構造は、拡張プロセスプロトコルに似ている。「ケースＩＤ」、「アクティビティ」、及び「タイムスタンプ」属性を含む古典的プロセスプロトコルは、プロセスネットワーク内の異なるプロセスのプロセスインスタンス間の相互作用を表すために、出力エッジ１５及び入力エッジ２５を記録するための「Ｓｉｇｎａｌ＿Ｉｎ」属性及び「Ｓｉｇｎａｌ＿Ｏｕｔ」属性によって拡張される。

本例では、３つのプロセスインスタンス又はケースが示されており、それぞれが異なるプロセスの実行から生じる。ＩＤ「１」を有するケース「ケース１」では、ネジが生産され、それは「ケース２」では更に椅子を生産するために使用され、「ケース３」では顧客に直接販売される。表９のデータに基づいて、図７に視覚化されたプロセスグラフ１を生成でき、プロセスグラフ１の有向エッジ１５；２５についての計算を実行することができる。

本発明の実施形態によれば、信号はまた、複数の拡張プロセスプロトコルにわたってケースを接続することもできる。信号は、拡張されたプロセスプロトコルとは無関係に、一意関係識別子３０によって識別される。

図７に示すグラフ１は、アクティビティ間の２つのタイプのリンクを含む。第１のタイプのアクティビティは、それが一部を形成するケース又はプロセスインスタンスのみに関連する。二重線のエラーで表された直接エッジ１５；２５によって接続される、第２のタイプのアクティビティは、２つの異なるケース間の一意関係識別子「１０」を有する信号によって接続される。第１のタイプのアクティビティに属するこれらのレコードは、何ら一意関係識別子を第２の属性及び第３の属性に割り当てずに、表９に示す信号リンクテーブルに記憶される。第２のタイプのアクティビティに属するレコードは、開始ノード１０又は終端ノード２０のいずれかを記憶する。したがって、一意関係識別子３０は、信号リンクテーブル内の対応するレコードの第３の属性又は第２の属性に記録される。本例では、一意関係識別子３０の値「１０」は、ねじのシリアル番号によって与えられる。

信号リンクテーブルのレコードは、個別の入力エッジ（２５）及び／又は出力エッジ（１５）を特徴付けるデータが記憶される、いくつかの更なる属性を含むことができる。任意の（有向）エッジＫＰＩを定義し評価することができるように、後続の抽出ステップ及び／又は分析ステップ中に更なる属性にアクセスすることができる。

図７では、表９に示すデータ構造の第４の属性に記憶された順序値（タイムスタンプ）が、水平軸上に視覚化されている。したがって、同じプロセスインスタンス又はケースのアクティビティは、それらが線形シーケンスで実行されるように、横軸に整列されている。開始ノード１０の出力エッジ１５に割り当てられた一意関係識別子３０と、終端ノード２０の入力エッジ２５に割り当てられた一意関係識別子３０との一致によって形成される、異なるプロセスのプロセスインスタンス間の相互作用は、二重線矢印によって視覚化される。

図５のケースと同様に、図７に示すグラフ１により、組織は、プロセスネットワーク内の任意のアクティビティにおいて生じる問題によって引き起こされるネットワーク内の影響を識別することが可能になる。例えば、ねじが「ケース１」のアクティビティ「Ｂ」において倉庫に遅れて登録された場合、これは、「ケース２」において椅子を生産し、「ケース３」において適時にねじを顧客に配送できるかどうかに影響を及ぼす。

信号リンクテーブル及び表９から出現する図７に提示されるグラフ１に含まれる情報を完全に活用するために、プロセスネットワーク、特にプロセスネットワーク内のアクティビティ間の相互作用を分析する。したがって、信号は、プロセスマイニングオペレータによって処理され得るフォーマットに変換される。フォーマットは、例えば、リレーショナルデータベースのテーブルであり得る。

例えば表９のような信号リンクテーブルの、信号、すなわちプロセスグラフ内の２つのノード間の有向エッジの分析を可能にするフォーマットへの変換は、演算子「ＬＩＮＫ＿ＳＯＵＲＣＥ」及び「ＬＩＮＫ＿ＴＡＲＧＥＴ」を用いて実現することができる。第１の演算子「ＬＩＮＫ＿ＳＯＵＲＣＥ」は、ソースアクティビティ、すなわち、開始ノード１０を含むレコードのいくつかの第１の属性の組み合わせ、いくつかの第２の属性の組み合わせ、及び第４の属性の値を第２のデータ構造にプルする。同様に、第２の演算子「ＬＩＮＫ＿ＴＡＲＧＥＴ」は、ターゲットアクティビティ、すなわち終端ノード２０を含むレコードのいくつかの第１の属性の組み合わせ、いくつかの第３の属性の組み合わせ、及び第４の属性を第２のデータ構造にプルする。第２のデータ構造において、第１の演算子及び第２の演算子から得られた値は、一意関係識別子３０上でマージされ、これは、それらが同じ信号に属する場合、それらが同じレコードにプルされることを意味する。信号が複数の終端ノードと開始ノードとの間で確立される場合、レコードのクロス乗積が第２のデータ構造において作成される。

更に、「ＬＩＮＫ＿ＳＯＵＲＣＥ」演算子及び「ＬＩＮＫ＿ＴＡＲＧＥＴ」演算子は、開始ノード１０及び／又は終端ノード２０を含むレコードの任意の属性にアクセスすることができる。特に、それらは、個別の入力エッジ２５及び／又は出力エッジ１５を特徴付けるデータが記憶されているレコードの更なる属性にアクセスすることができる。演算子は、更なる属性に記憶された任意の値を検索し、それを形成された有向エッジ（１５；２５）に割り当てることができる。検索された値は、第２のデータ構造のいくつかの更なる属性にそれぞれ記憶される。

表９の例では、結果として得られる第２のデータ構造（以後、エッジテーブルとして参照される）が表１０に記載されている。

エッジテーブルは、プロセスネットワーク内の異なるプロセスのアクティビティ間の相互作用に関する洞察を得る（例えば、それらのスループット時間を計算する）ために、全ての種類のプロセスマイニングオペレータに使用することができる。

エッジテーブルにおいて、第１の属性には、開始ノード１０のノード識別子が記憶される。第２の属性には、対応する終端ノード２０のノード識別子が記憶される。第３の属性（表１０には示されていない）には、形成された有向エッジ１５；２５の一意関係識別子３０が記憶される。表１０の更なる属性には、開始ノード１０のタイムスタンプと終端ノード２０のタイムスタンプがそれぞれ記憶される。更なる属性には、終端ノード２０に帰属するタイムスタンプと開始ノード１０に帰属するタイムスタンプとの間の時間差などのプロセス性能メトリックを記憶することができる。

エッジテーブルは、図５に示すグラフ１を記憶する信号リンクテーブル（表８）に対して適宜計算することができ、グラフ１はサプライチェーンネットワークを表す。本例では、「ＬＩＮＫ＿ＳＯＵＲＣＥ」演算子は、開始ノード「Ｐ＿４５６－１００」、「Ｐ＿４５６－４００」、「Ｐ＿１２３－１００」、「Ｃ＿１２３－１００」、及び「Ｃ＿４５６－１００」を含むレコードを第２のデータ構造の第１の属性にプルする。「ＬＩＮＫ＿ＴＡＲＧＥＴ」演算子は、「Ｐ＿４５６－２００」、「Ｐ＿４５６－１００」及び「Ｐ＿１２３－１００」を含むレコードを第２のデータ構造の第２の属性にプルする。結果として得られる値は、第２のデータ構造の第３の属性に記憶され得る一意関係識別子３０上でマージされる。

図８は、プロセスネットワークを表すグラフのシーケンス図を示しており、グラフは本発明の実施形態に従って記憶されている。

プロセスにおける問題を効率的に識別するために、ドリルダウン機能、すなわち、プロセスネットワークの特定のより小さい領域を検査する機能が必要とされる。ドリルダウン機能は、所定の条件に従って、プロセスグラフ又はサプライチェーンネットワークを表すグラフからのサブグラフなどの結果セットを制限するフィルタによって可能になる。これらのフィルタは、最終的に、エッジテーブルのレコードの数も制限し、これにより、結果として得られる信号レコードに対する特定の特徴（プロセス性能尺度）をより効率的に計算することが可能になる。

後続のプロセスマイニングのためにエッジテーブルをフィルタリングするために、従来のフィルタ技法は、エッジテーブル内のレコードの基礎となるグラフ構造、及びエッジテーブルが生成される信号リンクテーブルのレコードを取り込むことができないので、十分ではない。

したがって、一実施形態では、特定のフィルタ演算子、特に「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子及び「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」演算子が提供される。フィルタ演算子は、ノードのユーザ定義セットの祖先又は子孫である信号を含む第１のデータ構造（信号リンクテーブル）及び／又は第２のデータ構造（エッジテーブル）のレコードを制限する。

ノードのセットは、ＳＫＵのセット（サプライチェーンネットワーク）、アクティビティのセット（プロセスネットワーク）、又はエンティティの任意のセット（汎用ネットワーク）であり得る。フィルタ演算子が適用される方向は、ユーザ定義入力パラメータを介して決定することができる。

フィルタ演算子は、第１のデータ構造から出現するグラフをトラバースすることによって、第１のデータ構造に記憶されたレコードからサブグラフを生成することができる。以下に、フィルタ演算子の機能を実証するための例を提供する。

表１１は、４つの異なるプロセスインスタンスのデータ（「ケースＩＤ」）を含む信号リンクテーブルを提供し、各プロセスインスタンスは、所与のシーケンス（「タイムスタンプ」）で実行されるプロセスステップ（「アクティビティ」）のセットを有する。プロセスステップ／アクティビティのいくつかは、第２の属性（「Ｓｉｇｎａｌ＿Ｉｎ」）及び第３の属性（「Ｓｉｇｎａｌ＿Ｏｕｔ」）に帰属するように、信号Ｓ１、Ｓ２、又はＳ３によって相互接続される。第２の属性に割り当てられた値を有するアクティビティ、アクティビティ「Ｂ」、「Ｆ」及び「Ｇ」は、終端ノード２０によって表される。第３の属性に割り当てられた値を有するアクティビティ、アクティビティ「Ａ」、「Ｄ」、及び「Ｅ」は、開始ノード１０によって表される。

図８のシーケンス図では、各プロセスインスタンスは、関連するアクティビティがそれらのタイムスタンプに従って順序付けられている垂直線によって表される。開始ノード１０として表されるアクティビティ及び終端ノード２０として表される対応するアクティビティは、それぞれ、出力エッジ１５及び入力エッジ２５の一致するペアによって定義される相互作用を介して接続される。

表１１の信号リンクテーブルから、表１２に示すエッジテーブルを、上で概説されたように計算することができる。本例では、開始／終端ノードの識別子は、「ケースＩＤ」と「アクティビティ」との組み合わせ、例えば、「１Ａ」／「２Ｂ」又は「２Ｄ」／「３Ｆ」によって与えられ、これらは、それに応じて、第２のデータ構造の対応するレコードの第１の属性又は第２の属性に記録される。形成された有向エッジ１５；２５の一意関係識別子３０は、表１２の例では「信号」属性である、第２のデータ構造の第３の属性に記録される。

本例では、ユーザ定義の初期ノード４０は図８の二重線で囲まれたノード「Ａ」であり、サブグラフの現在のメンバとしてマークされている。例として、フィルタ演算子のユーザ定義の方向は、子孫の方向、すなわち、ネットワークの下流方向である。ノード「Ａ」は、一意関係識別子「Ｓ１」を有する出力エッジ１５に接続された開始ノード１０である。一意関係識別子「Ｓ１」と一致する入力エッジ２５は、ケース「２」の終端ノード「Ｂ」に接続されている。したがって、ノード「Ｂ」は、サブグラフの現在のメンバとしてマークされる。同じプロセスインスタンス、ケース「２」の一部としてノード「Ｂ」に接続されているのは、ノード「Ｃ」及び「Ｄ」であり、そのうちノード「Ｄ」は、一意関係識別子「Ｓ２」を有する出力エッジ１５に接続されている。したがって、ノード「Ｃ」及び「Ｄ」はサブグラフのメンバとしてマークされ、ノード「Ｄ」はサブグラフの現在のメンバとしてマークされる。一意関係識別子「Ｓ２」と一致する入力エッジ２５は、ケース「３」のノード「Ｆ」に接続されている。したがって、ノード「Ｆ」もサブグラフの現在のメンバとしてマークされる。同じプロセスインスタンスの一部としてノード「Ｆ」に接続されるのは、ノード「Ｅ」でもある。「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子によって行われるように、「Ｔｉｍｅｓｔａｍｐ」属性を考慮せずに、ノード「Ｅ」は、一意関係識別子「Ｓ３」を有する出力エッジ１５に接続されているので、サブグラフに挿入され、現在のメンバとしてマークされる。一意関係識別子「Ｓ３」と一致する入力エッジ２５は、ケース「４」のノード「Ｇ」に接続されている。「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子を使用すると、ネットワーク下流方向にノード「Ａ」から始まる図８の結果として得られるサブグラフは、図８のシーケンス図に示す全てのノードを含む。したがって、表１１に示す第１のデータ構造に「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子を適用すると、表１２に示すエッジテーブルから３つの信号「Ｓ１」、「Ｓ２」及び「Ｓ３」の全てが選択される。

同一の初期条件で同じ信号リンクテーブルに適用される第２の演算子「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」は、信号リンクテーブルの第４の属性、すなわち「タイムスタンプ」属性も考慮に入れるので、異なる結果をもたらす。したがって、ノード「Ｅ」は、その関連するタイムスタンプがノード「Ｆ」であるサブグラフの対応する現在のメンバのタイムスタンプより小さいので、サブグラフに挿入される「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」演算子によって拒絶される。したがって、表１１に示す第１のデータ構造からの「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」演算子の結果として生じるサブグラフは、ノード「Ｅ」及びノード「Ｇ」を除いて、図８のシーケンス図に示す全てのノードを含む。その結果、ノード「Ｅ」とノード「Ｇ」との間の有向エッジによって表される信号「Ｓ３」も、サブグラフの一部を形成しない。したがって、「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」演算子から得られたサブグラフによってフィルタリングされたエッジテーブル１２は、信号「Ｓ１」及び信号「Ｓ２」のレコードのみを含む。

サブグラフの検索は、所定のグラフトラバーサルプロトコルに従って少なくとも１つの選択されたノードから選択された方向に開始することによって、第１のデータ構造から生成されたグラフ１のトラバーサルに従って実行される。所定のグラフトラバーサルプロトコルは、レコードの幅優先探索、レコードの深さ優先探索、又はレコードの深さ優先探索を反復的に深くするなど、それらの組み合わせとすることができる。

フィルタ演算子は、サプライチェーンネットワークを表すグラフに同様に適用することができる。例えば、表８の信号リンクテーブルから生成される図５に示すグラフは、「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子を使用してフィルタリングされ、ノード「Ｐ＿４５６－１００」によって表される施設「１００」における製品「Ｐ＿４５６」の全ての供給者を発見することができる。本例では、選択された方向はネットワークの上流方向であり、選択された初期ノードはノード「Ｐ＿４５６－１００」である。「ＬＩＮＫ＿ＦＩＬＴＥＲ」によって発見された結果として得られたサブグラフは、ノード「Ｐ＿４５６－１００」、「Ｐ＿１２３－１００」、「Ｐ＿１２３－１００」、及び「Ｃ＿４５６－１００」を含む。

更に、抽出されたサブグラフのノード４０；１０；２０を下位階層レベルに基づいて集約することができ、形成された有向エッジ１５；２５は、それに応じて集約され、集約サブグラフをもたらす。

例えば、上で検討した例では、下位階層レベルは、機械／施設と、プロセスステップが実行された材料との組み合わせであり得る。異なるプロセスインスタンスのプロセスステップ間の転送時間を分析するために、抽出されたサブグラフは、ノードが下位階層レベル、例えば、施設と材料の組み合わせを表すグラフにマッピングすることができる。その結果、プロセスインスタンス間の平均時間などの更なるプロセス性能インジケータがアクセス可能になる。

図９は、ネットワークを表すグラフが出現する第１のデータ構造をフィルタリングする方法のフローチャートを示す。

図９のフローチャートによって表された実施形態は、第１のデータ構造内に記録されたデータに適用可能であり、そのデータは、任意のタイプのネットワーク、特に、サプライチェーンネットワークのエンティティ又はプロセスネットワーク内のプロセスステップを表し得る。

ステップＡにおいて、第１のデータ構造の少なくとも１つの初期ノード４０と、フィルタが適用される方向とを選択する。

ステップＢにおいて、第１のデータ構造において、所定のグラフトラバーサルプロトコルを使用して、選択された方向への少なくとも１つの初期ノード４０に接続された全てのノード１０；２０を含むサブグラフを発見する。

ステップＣにおいて、ステップＢから得られたサブグラフを抽出し、抽出されたサブグラフの有向エッジに基づいて第２のデータ構造をフィルタリングする。

任意選択のステップＤにおいて、ネットワーク内の異なるエンティティ間の相互作用を含むフィルタリングされた第２のデータ構造をプロセスマイニングシステムに提供して、プロセスネットワークの場合のプロセス性能インジケータなどのネットワーク効果を分析する。

図１０は、図９に示す実施形態のステップＢのためのドリルダウン機能の実施形態を示す。

所定のグラフトラバーサルプロトコルに従って、２つのノード間のリンクは、第１のデータ構造の第２のレコードの第２の属性の値を第１のデータ構造の第１のレコードの第３の属性の値と一致させることによって確立される。サブグラフの現在のメンバと共に選択された方向に沿って有向エッジを形成するノードを含む少なくとも１つのレコードのそれぞれに対して、一致が発見された場合、レコードは、「ＬＩＮＫ＿ＦＩＬＴＥＲ」演算子の場合、サブグラフのメンバとして直接マークすることができる。このオプションは、図１０に破線で示されている。

しかし、「ＬＩＮＫ＿ＦＩＬＴＥＲ＿ＯＲＤＥＲＥＤ」演算子の場合、サブグラフのメンバとしてレコードをマークする前のテストに合格しなければならない。発見されたレコードの第４の属性の順序値が、サブグラフの現在のメンバの第４の属性の順序値よりも大きいか否かがテストされる。肯定的なテスト結果について、レコードはサブグラフのメンバとしてマークされる。否定的なテスト結果の場合、記録はスキップされる。更なるレコードを発見できない場合、サブグラフは完全であり、後続のステップＣにおいて抽出され得る。

要約すると、本発明の主な利点は、データ構造、サプライチェーンネットワーク又はプロセスネットワークなどの相互作用するネットワークを記述するデータによる第１のデータ構造を記録する所定の手順によって与えられ、その相互作用は、必要とされるネットワークの構造に関する事前知識なしにデータ構造に記録される。データ構造から、ネットワークを表すグラフを生成でき、その後、特に、詳細にネットワーク効果に関する洞察にアクセスするドリルダウン及び／又は集約機能を使用して分析することができる。

Claims (14)

1. 記憶装置にグラフ（１）を記憶するために、コンピュータが実行する方法であって、
   前記グラフ（１）は複数のノード（１０；２０）及び複数の有向エッジ（１５；２５）を含み、
   各有向エッジ（１５；２５）は、開始ノード（１０）と終端ノード（２０）とを接続し、各有向エッジ（１５；２５）は、前記終端ノード（２０）に接続された入力エッジ（２５）と、前記開始ノード（１０）に接続された出力エッジ（１５）とから構成され、
   前記グラフ（１）はネットワークを表し、
   各ノード（１０；２０）は前記ネットワークのエンティティを表し、
   各有向エッジ（１５；２５）は２つのエンティティ間の関係を表し、前記方法は、
   前記記憶装置を用いて記憶されたデータ構造の第１のレコードに各開始ノード（１０）を記録し、前記データ構造の第２のレコードに各終端ノード（２０）を記録することであって、
   各レコードは、少なくとも
   ノードの識別子が記憶される１または２以上の第１の属性と、
   入力エッジの識別子が記憶される１または２以上の第２の属性と、
   出力エッジの識別子が記憶される１または２以上の第３の属性と、を含む、記録することと、
   前記第１のレコードに、１または２以上の前記第１の属性における前記開始ノード（１０）の前記識別子と、１または２以上の前記第３の属性における一意関係識別子（３０）とを記憶することであって、前記一意関係識別子（３０）は、前記ネットワーク内の経路に沿ったステップを表す、記憶することと、
   前記第２のレコードに、１または２以上の前記第１の属性における前記終端ノード（２０）の前記識別子と、１または２以上の前記第２の属性における前記一意関係識別子（３０）とを記憶することと、を含み、
   前記第１のレコードの１または２以上の前記第３の属性の値と一致する前記第２のレコードの１または２以上の前記第２の属性の値は、前記開始ノード（１０）と前記終端ノード（２０）との間の前記有向エッジ（１５；２５）を定義しており、
   前記ネットワークはサプライチェーンネットワークであり、前記エンティティは、材料と施設の組み合わせであり、前記２つのエンティティ間の関係は、部品表及び／又は配送表を使用することによって確立されている、方法。
2. 前記グラフ（１）を生成するために、前記第２のレコードの１または２以上の前記第２の属性の値を、前記第１のレコードの１または２以上の前記第３の属性の値と一致させることによって、前記開始ノード（１０）と前記終端ノード（２０）との間の前記有向エッジ（１５；２５）を決定することを更に含む、請求項１に記載の方法。
3. 前記ネットワークを表示するためのグラフ視覚化デバイスに前記データ構造を提供することを更に含む、請求項１又は請求項２に記載の方法。
4. 前記データ構造はテーブルであり、前記テーブルはデータモデルに関連付けられている、請求項１に記載の方法。
5. 前記一意関係識別子（３０）は、前記２つのエンティティ間の関係を特徴付けるデータを含む、請求項１に記載の方法。
6. 前記ノードの識別子はケースキーを含む、請求項１に記載の方法。
7. 前記ケースキーは、材料識別子と施設識別子との組み合わせである、請求項６に記載の方法。
8. 少なくとも１つのノード（１５；２５）は、少なくとも１つの入力エッジ（２５）に接続された前記終端ノード（２０）と、少なくとも１つの出力エッジ（１５）に接続された前記開始ノード（１０）との両方であり、前記方法は、前記少なくとも１つのノードの各ノード（１０；２０）を少なくとも１つのレコードに記録することを更に含み、
   前記少なくとも１つのレコードの各レコードにおいて、各ノード（１０；２０）の前記識別子は、１または２以上の前記第１の属性に割り当てられ、１つの入力エッジ（２５）の第１の一意関係識別子は、１または２以上の前記第２の属性に割り当てられ、１つの出力エッジ（１５）の第２の一意関係識別子は、１または２以上の前記第３の属性に割り当てられる、請求項１に記載の方法。
9. 前記少なくとも１つのレコードの各レコードにおいて、１つの入力エッジ（２５）の前記第１の一意関係識別子が１または２以上の前記第２の属性に割り当てられる、又は、１つの出力エッジ（１５）の前記第２の一意関係識別子が１または２以上の前記第３の属性に割り当てられる、のいずれかである、請求項８に記載の方法。
10. １または２以上の前記第１の属性における第１の属性の数が１であり、かつ／又は１または２以上の前記第２の属性における第２の属性の数が１であり、かつ／又は１または２以上の前記第３の属性における第３の属性の数が１である、請求項１に記載の方法。
11. 前記ネットワークはプロセスネットワークであり、前記プロセスネットワークは、異なるプロセスの２つ以上のプロセスインスタンスと、少なくとも２つの異なるプロセスのプロセスインスタンスのプロセスステップ間の相互作用とを含み、各ノード（１０；２０）はプロセスインスタンスのプロセスステップを表し、前記一意関係識別子（３０）は、第１のプロセスのプロセスインスタンスの一部を形成する前記開始ノード（１０）と第２のプロセスのプロセスインスタンスの一部を形成する前記終端ノード（２０）との間の信号を表し、前記データ構造は、前記データ構造が拡張プロセスプロトコルを形成するように、プロセスインスタンス内の前記プロセスステップのシーケンスが記憶される第４の属性を更に含む、請求項１に記載の方法。
12. １または２以上の前記第１の属性は、個別のプロセスステップの前記プロセスインスタンスの一意識別子が記憶されるケース属性と、前記個別のプロセスステップの識別子が記憶されるアクティビティ属性とを含む、請求項１１に記載の方法。
13. 前記データ構造は、前記記憶装置の揮発性メモリに排他的に記憶される、請求項１に記載の方法。
14. ネットワーク内のフローを制御する方法であって、前記ネットワークがグラフ（１）によって表され、前記グラフ（１）が請求項１に記載の方法に従って記憶される、方法。