JP5689361B2 - グラフデータの一部を準同型写像の像であるデータ構造に変換する方法、プログラム、および、システム - Google Patents

Description

本発明は、一般的には、データ構造の変換のための情報処理技術に関し、より特定的には、グラフデータの一部をその準同型写像の像であるデータ構造に変換する方法、プログラム、および、システムに関する。

複数のノードとノード間の連結関係を表すエッジグラフ構造のデータ（以下、単に「グラフデータ」と称することがある）を用いて、実世界のモデルをコンピュータ上で表現することが一般的に行われている。一般的に、グラフデータは、ＲＤＦ（Ｒｅｓｏｕｒｃｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｆｒａｍｅｗｏｒｋ）のような標準化された形式にしたがって記述され、グラフ・リポジトリと称されるデータベースに記憶される。グラフ・リポジトリに格納されたグラフデータは、その一部または全部が各種のアプリケーション・プログラムによって呼び出され利用される。業界の各社は、そのようなグラフデータをハンドリングするためのソフトウェアを研究開発している。

当分野の背景技術として、特開２０１０−０２５６９７８号公報（特許文献１）は、コンフィグレーションデータの検証を簡易に行うことができるようにするためのコンフィグレーションデータ検証装置を開示する。装置は、システムのコンフィグレーションデータから該システムを構成するコンポーネント間の依存関係を抽出し、該依存関係を表す関係グラフを生成する関係グラフ生成部と、予め与えられた基準関係グラフと生成された関係グラフとに基づいて、コンフィグレーションデータの妥当性を検証する関係グラフ検証部とを備える。関係グラフ検証部は、基準関係グラフと生成された関係グラフとが同型である場合には、コンフィグレーションデータが妥当であるものと判定し、それ以外の場合には、コンフィグレーションデータは失当であるものと判定する。

他の背景技術として、特開２００７−００２６２１０号公報（特許文献２）は、改良されたツリー表示プログラムを開示する。当該プログラムでは、ツリー構造上、最上位階層に位置する実際のルートノード１から展開表示されているツリーの中から表示対象とするノード４がユーザにより指定されると、そのノード４を仮想的なルートノードとして、ノード４を最上位階層に配置した無向グラフとしてみた場合には同型であるようなツリー構造を形成し表示する。ノード４の親ノードであるノード２の引き出し線に矢印アイコン４０を所定の向きで付加することによって、ノード２がノード４の親ノードであることを示す。また、仮想的なルートノード４から実際のルートノード１まで間の経路上に所定の向きで矢印アイコン４２を付加することで、仮想的なルートノード４と実際のルートノード１との相対的な位置関係を示す。

他の背景技術として、特開２００３−００３０２２７号公報（特許文献３）は、データマイニングの前処理の際に様々なタイプのデータ集合を一元的に取扱い、ユーザからのインタラクションを反映してデータ集合やデータの構造を動的に変更することが可能な方法を開示する。方法は、XMLデータから、当該XMLデータの属性を葉ノードあるいは非葉ノードとし、属性値を含まず属性間の関係を表現し、ノード間の冗長な親子関係をマージして最適化したツリー構造である階層ユニットツリーを作成するステップと、階層ユニットツリーに対して変更を加えるステップと、階層ユニットツリーに対して加えられた変更を反映するようにXMLデータを変換するステップとを含む。

他の背景技術として、特許３１３７５９０号（特許文献４）は、要素工程が与えられた際にノード接続手段で初期グラフを作成し、初期必須ノード選択手段で必須となるノードを選択し、初期グラフ作成手段で各要素工程に対応したノードと有向枝とから構成される初期グラフを作成し、依存グラフ作成手段で初期グラフを変形して依存グラフを作成し、工程表現木作成手順によって依存グラフを変形して、実行可能な製造手順を表現する工程表現木を作成する製造手順決定装置を開示する。

他の背景技術として、特開２００１−０１４２９３７号公報（特許文献５）は、回路のスケジューリングの正当性をチェックする方法、及び、回路のビヘイビア記述に対して回路のスケジュールを検証する方法を開示する。ビヘイビア記述から得られる回路のスケジューリングの正当性をチェックする方法は、ループが回路内にあるときに非巡回スレッドの十分なセットを決定するためにループ不変項を抽出し、ループ不変項を抽出するためにシンボリックシミュレーションを実行し、非巡回スレッドの等価性を証明する。回路のビヘイビア記述に対して回路のスケジュールを検証する方法は、スケジュールからループを含む可能性のある実行のスケジュールスレッドを選択し、ビヘイビア記述から対応するビヘイビアスレッドを識別し、スケジュールスレッド及びビヘイビアスレッドの無条件等価性を証明し、実行のすべてのスレッドについて以上が繰り返される。

他の背景技術として、特開１９９３−０２３３２９８号公報（特許文献６）は、２つの環が体上有限次元のとき、全単射な準同型写像の存在を計算機によって効率的に調べ得る環同型判定方式を提供する。この方式では、任意の２つの環Ａ，Ｂに対して線形空間基底を計算し、環Ａから環Ｂへの線形写像φを定義し、該線形写像φの定数項除去によってφ＊を定義し、φ＊の行列式ｆおよび環Ａ，Ｂの基本関係式と線形写像φの準同型としての作用からイデアルＩからイデアルＪを定義し、該イデアルのグレブナ基底ＧJ
に基づいて同型であるか否かを判定する。

他の背景技術として、特開１９９８−０１５４９７６号公報（特許文献７）は、外部から物理的衝撃を加えて内部回路を誤動作させその出力を観察して装置内部の秘密情報を推測する攻撃法に対して防御可能なタンパーフリー装置を提供する。装置は、内部に外部からの入力データに対して所定のデータ変換処理を施して出力するための手段を備え、内部情報への不正アクセスを防止するために内部回路全体を物理的手段により外部から保護したタンパーフリー装置であって、データ変換処理の誤動作を検出する手段と、誤動作が検出された場合に処理の出力に所定の規制を施す出力規制手段とを備える。

他の背景技術として、特開２００８−０２０３９６４号公報（特許文献８）は、以下のクラスタリング技術を開示する。事象間の正しい因果関係を保ちつつ、複数の事象をクラスタリングすることによって、因果関係ネットワークを分かりやすく要約させる。自然言語で記述された文書である自然言語文から抽出された互いに異なる複数の事象間の因果関係に対して、事象を構成する単語の一部が同一でかつ、共通の原因または結果事象を持つ事象群がクラスタ対象選択部にてクラスタリングの対象として選択され、クラスタリング対象の事象全てで共通の因果関係のみが統合されるデータ構造を持つ因果関係グラフが因果関係記憶部に格納され、因果関係グラフの構造の複雑さがクラスタリングスコアとして数値化され、クラスタリングスコアが最小となるようにクラスタ対象選択部によって選択された事象群が事象クラスタ評価部にてクラスタリングされる。

特開２０１０−０２５６９７８号公報 特開２００７−００２６２１０号公報 特開２００３−００３０２２７号公報 特許３１３７５９０号 特開２００１−０１４２９３７号公報 特開１９９３−０２３３２９８号公報 特開１９９８−０１５４９７６号公報 特開２００８−０２０３９６４号公報 特開１９９７−００１６３８９号公報 特開２０１０−００３３５００号公報 特開２００８−０１５８７５９号公報 特開２００６−０１８５２１１号公報 特開２００５−０１００４０２号公報 特開１９９３−０１５８６７６号公報

あるアプリケーションがグラフ・リポジトリに記憶されたグラフデータを利用する場合、当該アプリケーションの観点からグラフデータが複雑過ぎたり、不要な詳細まで含まれていたりすることがある。そのため、直接グラフデータ全体にアクセスするのではなく、グラフデータの写像の像であるユーザが定義する各アプリケーションの目的に応じたオブジェクトに変換してグラフデータの一部または全部を利用したいという要請がある。この場合、変換されたオブジェクトに対する各種アプリケーションにおける操作を元のグラフデータに正しく反映することができることが好ましい。

しかし、かかるオブジェクトに対する各種アプリケーションにおける操作を元のグラフデータに正しく反映することができるオブジェクトにグラフデータを変換することは、いずれの背景技術によっても実現をすることができていない。

したがって、本発明の目的の１つは、アプリケーションによるオブジェクトの操作を元のグラフデータに反映することができるデータ構造に変換する、方法、プログラム、および、システムを提供することである。

上記の目的を達成するために、１以上のグラフ・マッチングのためのパターンを用いてノードとエッジを含むグラフデータの少なくとも一部をその準同型写像（ｈｏｍｏｍｏｒｐｈｉｓｍ）の像（ｉｍａｇｅ）であるデータ構造に変換する方法が提供される。方法は、パターンに１つ存在する代表ノード変数であって、当該代表ノード変数にマッチしたグラフデータのノードが高々１つで、かつ他のパターンのノード変数にマッチすることが禁止されるという第１の制約を有する代表ノード変数を含むパターンを提供するステップと、グラフデータとパターンのマッチング処理を行い、第１の制約を含む制約に違反しないマッチング結果を得るステップと、制約に違反しないマッチング結果に対応するデータ構造を生成するステップを含む。

好ましくは、マッチング処理を行うステップは、パターンにマッチするグラフデータのサブセットに関する情報をマッチング結果として得るステップと、制約に違反するグラフデータのサブセットに関する情報をマッチング結果から除去するステップと、を含む。さらに好ましくは、グラフデータのサブセットに関する情報が、パターンに含まれるノード変数とそれにマッチしたグラフデータ内のノードとの対応関係をエントリとして含むテーブルとすることができる。好ましくは、マッチング結果から除去するステップが、制約に違反するグラフデータのサブセットに対応するテーブルを除去するステップを含む。

好ましくは、代表ノードが、他のパターンに属するノードとの間のインターリンクの端点となり得る。好ましくは、マッチング処理を行うステップにおいて代表ノードがマッチした複数のパターンが継承関係にある場合、継承した側のマッチング結果に対応するデータ構造が生成される。

好ましくは、パターンは、１以上の第２の種類のノード変数を含み、第２の種類のノード変数にマッチするグラフデータのノードがパターンの代表ノード変数にマッチするグラフデータのノードにユニークに対応しなければならないという第２の制約を有し、第１の制約および第２の制約に違反しないマッチング結果に対応するデータ構造が生成される。さらに好ましくは、第２の種類のノード変数にマッチしたノードが、他のパターンに属するノードとの間のインターリンクの端点となり得る。

好ましくは、マッチング処理を行うステップは、パターンに対応するグラフ・クエリをグラフデータに対して実行するステップを含む。好ましくは、マッチング処理を行うステップは、異なるパターンに属するノードを接続するインターリンクのマッチング処理を行うステップを含む。好ましくは、マッチング処理を行うステップは、ノード変数に関するマッチング結果と整合しないインターリンクのマッチング結果を除去するステップを含む。好ましくは、マッチング処理を行うステップは、インターリンクのマッチング処理結果をノード変数のマッチング処理結果にマージするステップを含む。

好ましくは、データ構造を生成するステップは、パターンに対応するデータ構造のクラス定義をインスタンス化することによってデータ構造を生成するステップを含む。好ましくは、方法は、生成したデータ構造をアプリケーションに引渡し、ユーザに提示するステップをさらに含む。

以上、データ構造を変換する方法として本発明の概要を説明したが、本発明は、プログラム、プログラム製品、ソフトウェア、ソフトウェア製品、システム、装置などとして把握することもできる。プログラム製品ないしソフトウェア製品は、例えば、前述のプログラム、ソフトウェアを格納した記憶媒体を含め、あるいはプログラム、ソフトウェアを伝送する媒体を含めることができる。

上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーションまたはサブコンビネーションもまた、発明となり得ることに留意すべきである。

本発明の実施形態おけるデータ処理システムの全体像の一例を示した図である。 本発明の実施形態におけるデータ処理システムの機能ブロック図である。 本発明の実施形態におけるデータ処理システムの動作を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのオブジェクトデータ生成の動作を表現するフローチャートである。 本発明の実施形態における正規化の処理の動作の一例を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのオブジェクトを操作した場合の動作を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのオブジェクトの生成（ＣＲＥＡＴＥ）処理に対応するＤＢＴ処理の動作を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのオブジェクトの更新（ＵＰＤＡＴＥ）処理に対応するＤＢＴ処理の動作を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのオブジェクトの削除（ＤＥＬＥＴＥ）処理に対応するＤＢＴ処理の動作を表現するフローチャートである。 本発明の実施形態におけるデータ処理システムのグラフデータ変更処理の動作を表現するフローチャートである。 本発明の実施形態におけるカーネル・パターンのデータ・セットの一例である。 本発明の実施形態におけるオブジェクト定義のデータ・セットの一例である。 本発明の実施形態におけるグラフデータの一例である。 本発明の実施形態におけるＳＰＡＲＱＬ言語に従うカーネル・パターンのグラフ・クエリである。 本発明の実施形態におけるＳＰＡＲＱＬに従うカーネル・パターンのグラフ・クエリによる照会結果である。 本発明の実施形態における代表ノードの型割り当て表の一例を示した図である。 本発明の実施形態におけるオブジェクトデータの一例を示した図である。 本発明の実施形態におけるグラフデータから生成されたオブジェクトデータの一例である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例を示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例の操作ログを示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例に応じたＤＢＴの変化を示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第１の例を反映したグラフデータである。 本発明の実施形態におけるオブジェクト操作の流れの第２の例を示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例の操作ログを示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例に応じたＤＢＴの変化を示した図である。 本発明の実施形態におけるオブジェクト操作の流れの第２の例を反映したグラフデータである。 本発明の実施形態におけるデータ処理システムを実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。

以下、本発明を実施するための形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲に記載された発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

また、本発明は多くの異なる態様で実施することが可能であり、実施の形態の記載内容に限定して解釈されるべきものではない。実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。

図１は、本発明の実施形態おけるデータ処理システムの全体像の一例を示した図である。データ処理システムは第１のユーザが操作する第１の端末１００、第２のユーザが操作する第２の端末１０５、および、グラフデータを記憶するグラフ・リポジトリを備えるサーバ１１０を含む。これらの各端末１００、１０５およびサーバ１１０はネットワーク１１５で相互に接続され、電子データである情報のやり取りをすることができる。典型的には、ネットワーク１１５はインターネットないしイントラネットである。

本発明の実施形態では、ユーザが操作する端末１００、１０５にはオブジェクト・ハンドリング・ソフトウェアがインストールされている。本発明の実施の形態による端末１００、１０５は、ユーザが操作し、また情報を提示されるための入出力デバイスであるキーボード、マウスのような入力デバイス、および表示装置を備える。

本発明の実施形態では、ユーザは、端末１００、１０５の表示装置に作業状況の情報などを視覚的に提示するウィンドウ・ベースのグラフィカル・ユーザ・インターフェースを通じて、キーボード、マウスなどの入力デバイス用いてアプリケーション・プログラムを操作する。

各ユーザは自己が操作する端末１００、１０５において実行されるアプリケーション・プログラムを用いて操作するグラフデータをサーバ１１０にネットワーク１１５を介して要求することができ、サーバ１１０はグラフ・リポジトリに記憶されたグラフデータのサブセット（一部分）を要求されたグラフデータとしてネットワーク１１５を介して返送する。本発明の実施形態では、それぞれの端末には、グラフ・リポジトリに格納されたグラフデータを操作するということでは共通するが、その目的が異なるアプリケーション・プログラムが導入されているものとする。

本発明の実施形態では、グラフ・リポジトリから受信したグラフデータに関して、準同型写像の像であるデータ構造に変換できる部分と、それ以外の部分とが区別される。本発明の実施形態では、前者について、各端末はグラフ・リポジトリから受信したグラフデータの少なくとも一部をその準同型写像（ｈｏｍｏｍｏｒｐｈｉｓｍ）の像（ｉｍａｇｅ）に変換してオブジェクトデータを生成する。ここで、準同型（ｈｏｍｏｍｏｒｐｈｉｃ）とは、複数の構造の間の類似性を表す概念であり、ある構造が他の構造の準同型写像の像である場合、前者に対する操作と後者に対する操作を一対一で対応させることができる。この性質について、準同型写像は、構造を保存（ｓｔｒｕｃｔｕｒｅ ｐｒｅｓｅｒｖｉｎｇ）する、構造と両立（ｃｏｍｐａｔｉｂｌｅ ｗｉｔｈ ｓｔｒｕｃｔｕｒｅ）する、などと表現される。

グラフデータは、あらかじめユーザが定義したグラフ・マッチング・パターンの一種（以下、「カーネル・パターン」と称することがある）にマッチしたグラフデータのサブセットを、あらかじめユーザが定義したオブジェクトのクラス定義（以下、単に「オブジェクト定義」と称することがある）に従ってインスタンス化することによって、そのユーザが使用するアプリケーション・プログラムの目的に適したオブジェクトデータに変換される。

次いで、本発明の実施形態ではユーザはオブジェクトデータを端末に導入されたアプリケーション・プログラム上で操作する。本発明の実施形態では、オブジェクトデータに対する操作は、上述したオブジェクトデータの準同型的性質を利用してサーバ１１０のグラフ・リポジトリに格納された元のグラフデータに反映される。本発明の実施形態では、このグラフデータへの反映は、操作がされた後のオブジェクトと、その操作を反映したグラフデータから写像して得られるオブジェクトが同じになるように正しく実施されることとなる。

図２は、本発明の実施形態のユーザ端末１００およびサーバ１１０を含むデータ処理システムの機能ブロック図である。なお、図２の機能ブロック図に示す各要素は、図１８に例示したハードウェア構成を有する情報処理装置において、ハードディスク装置１３などに格納されたオペレーティング・システムやオブジェクト・ハンドリング・ソフトウェアなどのコンピュータ・プログラムをメインメモリ４にロードした上でＣＰＵ１に読み込ませ、ハードウェア資源とソフトウェアを協働させることによって実現することができる。

本発明の実施形態のサーバ１１０は、グラフ・リポジトリ２７５を含む。本発明の実施形態のグラフ・リポジトリ２７５は、グラフデータを記憶する機能を備える。本発明の実施形態のグラフデータは、ノードとノード間の連結関係を表す有向または無向のエッジを含み、それぞれのノードおよびエッジに対して属性値を付与することができる。本発明の実施形態では、グラフデータはＷ３Ｃ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｎｓｏｔｉｕｍ）勧告として標準化されたＲＤＦ（Ｒｅｓｏｕｒｃｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｆｒａｍｅｗｏｒｋ）フォーマットにしたがって記述されるものとする。

また、グラフ・リポジトリ２７５は、ユーザ端末１００のリポジトリ・アクセス部２０５からＷ３Ｃ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｎｓｏｔｉｕｍ）勧告として標準化されたＳＰＡＲＱＬ（ＳＰＡＲＱＬ Ｐｒｏｔｏｃｏｌ ａｎｄ ＲＤＦ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ）言語に従うクエリを受信し、クエリに記述された条件に合致したグラフデータの全部または一部をリポジトリ・アクセス部２０５に返送する機能をも有する。返送されたグラフデータの一例は、図１３等を用いて後で詳細に説明される。なお、そのようなグラフデータを格納するためのグラフ・リポジトリ２７５は、本明細書を読んだ当業者が適宜実装することができるので、これ以上の詳細は本明細書では説明されない。

本発明の実施形態の端末１００は、リポジトリ・アクセス部２０５、パターン・マッチング部２１０、正規化部２１５、オブジェクトデータ生成部２２０、オブジェクト定義記憶部２２５、カーネル・パターン記憶部２３０、データ・バインディング・テーブル（ＤＢＴ）記憶部２３５、オブジェクトデータ記憶部２４０、オブジェクトデータ操作部２４５、グラフデータ変更部２５０、操作ログ記憶部２５５、アプリケーション部２６０、および、入出力部２６５を備える。

本発明の実施形態のリポジトリ・アクセス部２０５は、後述するグラフデータ変更部２５０を介して受けたアプリケーション部２６０からの命令に従って、サーバ１１０のグラフ・リポジトリ２７５に記憶されたグラフデータを照会するクエリを生成する機能を備える。リポジトリ・アクセス部２０５は、生成したクエリをグラフ・リポジトリ２７５にネットワーク１１５を介して送信し、クエリの結果であるグラフデータを受領することができる。

本発明の実施形態では、リポジトリ・アクセス部２０５は、グラフ・リポジトリに記憶されたグラフデータにアクセスし、少なくともグラフデータの問合せ、グラフデータの変更をする機能を有するものとする。本発明の実施形態では、グラフ・リポジトリへのアクセスのためのクエリは、ＳＰＡＲＱＬ言語に従うものとして実装されるが、他の任意のグラフデータ問合せ言語を採用することが可能であることは当然である。本発明の実施形態のリポジトリ・アクセス部２０５は、グラフデータの問合せの結果としてグラフ・リポジトリ２７５から得たグラフデータをパターン・マッチング部２１０に引き渡す。

本発明の実施形態のパターン・マッチング部２１０は、リポジトリ・アクセス部２０５から引き渡されたグラフデータを、カーネル・パターン記憶部２３５に記憶されたカーネル・パターンとマッチングする。カーネル・パターンの例は、図１１を用いて後で詳細に説明される。マッチングは、カーネル・パターンごとに用意され、または、カーネル・パターンに基づいて生成されたＳＰＡＲＱＬ言語に従うクエリを対象となるグラフデータに関して問い合わせることで実施する。カーネル・パターンに対応するクエリの例は図１３を用いて後で詳細に説明される。また、パターン・マッチング部２１０は、カーネル・パターンごとのクエリの結果を用いて初期データ・バインディング・テーブル（ｉｎｉｔｉａｌ ＤＢＴｓ）を形成し、データ・バインディング・テーブル（ＤＢＴ）記憶部２３５に記憶させる。なお、初期ＤＢＴの例は、図１４を用いて後で詳細に説明される。

本発明の実施形態の正規化部２１５は、パターン・マッチング部２１０が生成し、ＤＢＴ記憶部２４０に記憶させた初期ＤＢＴに処理を施して、後でＤＢＴを参照して生成されるオブジェクトデータがグラフデータの準同型写像（ｈｏｍｏｍｏｒｐｈｉｓｍ）の像（ｉｍａｇｅ）となるようにされる。かかるＤＢＴに対する処理を本明細書では「正規化」と称し、図５を用いて後で詳細に説明される。

本発明の実施形態のオブジェクトデータ生成部２２０は、ＤＢＴ記憶部２３５に格納されたＤＢＴ、および、オブジェクト定義記憶部３３０に記憶されたオブジェクト定義を参照して、リポジトリ・アクセス部２０５によって取得されたグラフデータをオブジェクトデータに変換する。グラフデータは、ユーザが使用するアプリケーション・プログラムの目的に適した形となるように変換され、生成されたオブジェクトデータは、オブジェクトデータ記憶部２４０に格納される。

本発明の実施形態のオブジェクト定義記憶部２２５は、ユーザによって定義されたオブジェクトのクラス定義（すなわち、オブジェクト定義）を記憶する。オブジェクト定義はオブジェクトデータ生成部２２０がグラフデータをオブジェクトデータに変換するために参照される。オブジェクト定義の例は、図１２を用いて後で詳細に説明される。

本発明の実施形態のパターン記憶部２３０は、パターン・マッチング部２１０によるマッチングに使用されるカーネル・パターンを記憶する。データ・バインディング・テーブル（ＤＢＴ）記憶部２３５は、パターン・マッチング部２１０によって生成されたＤＢＴ等を記憶する。既に述べた通り、ＤＢＴ記憶部２４０に記憶されたＤＢＴは正規化部２１５などによって処理され、また、オブジェクトデータ生成部によって参照される。

本発明の実施形態のオブジェクトデータ記憶部２４０は、オブジェクトデータ生成部２２０によってグラフデータを変換することによって生成されたオブジェクトデータを記憶する。オブジェクトデータ記憶部２４０に記憶されるオブジェクトデータは、ユーザが定義したオブジェクト定義をインスタンス化して生成されるので、それぞれのユーザが操作するアプリケーション・プログラムの目的に適したデータ構造となっている。オブジェクトデータ記憶部２４０に記憶されたオブジェクトデータはアプリケーション部２６０から直接、または、オブジェクトデータ操作部２４５を介して操作され得る。

本発明の実施形態のグラフデータ変更部２５０は、アプリケーション部２６０におけるユーザのアプリケーション・プログラムの操作、または、操作ログ記憶部２５５に記憶されたアプリケーション部２６０におけるアプリケーション・プログラムの操作ログに基づいて、グラフ・リポジトリ２７５に記憶されたグラフデータの問合せ、グラフデータの変更を実施するようにリポジトリ・アクセス部２０５に命令する。

本発明の実施形態の操作ログ記憶部２５５は、アプリケーション部２６０におけるアプリケーションの操作ログを記憶する。アプリケーション部２６０は、ユーザが操作するアプリケーションが実行されている。入出力部２６５は、ユーザから受けた操作をアプリケーション部２６０に引渡し、また、アプリケーション部２６０から受領したオブジェクトデータの表示等をユーザに提供する。

図３は、本発明の実施形態におけるデータ処理システムの動作を表現するフローチャート３００である。処理はステップ３０５でスタートし、ステップ３１０でカーネル・パターンがユーザによって定義される。カーネル・パターンは、グラフデータとのマッチング処理をするために参照されるグラフ・マッチング・パターンの一種である。本発明の実施形態では、カーネル・パターンの定義は、ユーザがカーネル・パターン定義機能を備えるアプリケーション・プログラムを対話的に操作することによって実施され、または事前にユーザにより用意されるものとする。

図１１は、本発明の実施形態におけるカーネル・パターンのデータ・セットの一例である。この例では、４種類のカーネル・パターン１１０５、１１１０、１１１５、１１２０が定義されている。本発明の実施形態では、これらのカーネル・パターンは、それぞれα、β、γ、δというラベルが付されて識別されているものとする。それぞれのカーネル・パターンは、複数のノードパターンとそれらを相互に繋ぐエッジを含む。本発明の実施形態では、エッジは有向エッジであるものとする。また、異なるカーネル・パターンに属するノードパターンの間でもエッジが存在する場合がある。本明細書では、かかる異なるカーネル・パターンに属する要素の間のエッジを「インターリンク」と称する。例えば、図１０に示す例では、カーネル・パターンα、βの要素”$A”と”$B”を繋ぐインターリンク１１２５が示されている。それぞれのノードパターンおよびエッジには属性値が付されることができる。

カーネル・パターンのノード変数の一部には後で詳細に説明するカーネル・パターンのマッチング結果（具体的には、初期ＤＢＴ）の一部を除去するために使用される制約条件が記述される。本発明の実施形態では、以下の２種類の制約条件が存在する。

第１の制約条件は、それぞれのカーネル・パターンのノード変数の種類のうち一つだけに付される。なお、第１の制約条件を付されたカーネル・パターンのノード変数を「代表ノード変数」と呼び、代表ノード変数にマッチするノードを「代表ノード」と称することがある。第１の制約条件の内容は、代表ノード変数にマッチしたグラフデータのノードが高々１つで、かつ他のカーネルのノード変数にマッチすることが禁止される、というものである（ただし、そのカーネル・パターンと他のカーネルのパターンが継承関係にある場合は除く）。また、本発明の実施形態では、代表ノード変数にマッチしたノードは、他のカーネルに属するノードとの間のインターリンクの端点となり得るものとする。本発明の実施形態では、カーネル・パターンのノード変数の名前に”$”という接頭辞を付することによって、当該ノード変数を代表ノード変数として設定するものとする。

また、第２の制約条件は、カーネル・パターンの任意のノード変数に付され得るが、カーネル・パターンは、必ずしも第２の制約条件が付されたノードを含む必要はない。なお、第２の制約条件を付されたカーネル・パターンのノード変数を「ユニーク・ノード変数」と称することがある。第２の制約条件の内容は、第２の制約条件が付されたユニーク・ノード変数にマッチするグラフデータのノードは、カーネルの代表ノードに「ユニークに対応」しなければならない、というものである。本発明の実施形態では、ユニーク・ノード変数にマッチしたノードは、他のカーネルに属するノードとの間のインターリンクの端点となり得るものとする。本発明の実施形態では、カーネル・パターンのノード変数の名前に”#”という接頭辞を付することによって、当該ノードをユニーク・ノード変数として設定するものとする。

上述の代表ノード変数およびユニーク・ノード変数にマッチするグラフデータのノードは、準同型写像の像であるデータ構造に変換できる部分であり、上述の第１および第２の制約条件は準同型写像の像であるデータ構造への変換を可能とするために使用される。

また、本発明の実施形態では、カーネル・パターンは、代表ノード変数およびユニーク・ノード変数以外に、グラフデータ内のノードをURL等の識別子により直接指定する直接指定ノード、「値」そのものが付されたリテラル・ノード、ノードに制約無くマッチするノード変数である一般ノード変数を含み得る。直接指定ノードは、ノードの名前としてグラフデータ内のノードの識別子を直接指定することによって設定するものとする。また、リテラル・ノードは、ノードの名前をダブルクオート（“”）で囲んだ「値」とすることによって設定するものとする。一般ノード変数は、ノード変数の名前の前に”?”という接頭辞を付することによって設定するものとする。）なお、本発明の実施形態では、リテラル・ノードは単一のノードとのみエッジによって接続されるものする。

このようにして、本発明の実施形態では、グラフ・リポジトリから受信したグラフデータに関して、準同型写像の像であるデータ構造に変換できる部分と、それ以外の部分とが区別される。

次に、処理はステップ３１５に進み、ユーザが端末を操作することによってオブジェクト定義が設定される。本発明の実施形態では、オブジェクト定義は、ユーザがオブジェクト定義機能を備えるアプリケーション・プログラムを対話的に操作することによって実施され、または事前にユーザにより用意されるものとする。本発明の実施形態におけるオブジェクト定義とは、カーネル・パターンにマッチングしたグラフのサブセットをオブジェクトデータに変換するために参照されるクラスを定義したものである。すなわち、オブジェクト定義は各オブジェクトの構造を表現し、カーネル・パターンにマッチングしたグラフのサブセット部分を、対応するオブジェクト定義をインスタンス化することによってグラフデータがオブジェクトデータへと変換されることとなる。

図１２は、本発明の実施形態におけるオブジェクト定義のセットの一例である。オブジェクト定義のセットは、カーネル・パターンに対応するオブジェクト定義１２０５、１２１０、１２１５、１２２０を含み、これらは図１１に示されているカーネル・パターン１１０５、１１１０、１１１５、１１２０にそれぞれ対応する。また、本発明の実施形態の例では、インターリンクに対応するオブジェクト定義１２２５をも含み、これは、図１１に示されているインターリンク１１２５に対応する。

具体的には、オブジェクト定義１２０５は、その名称が”Member”であり、カーネル・パターンαにマッチングしたときにインスタンス化され、カーネル・パターン内のノード変数”#N1”にマッチしたノードに付された文字列（String）を属性値とする”name”という属性を有することが示されている。モデル１２１０は、その名称が”Group”であり、カーネル・パターンβにマッチングしたときにインスタンス化され、カーネル・パターン内のノード変数”#J”にマッチしたノードに付された整数値（Int）を属性値とする”budget”という属性を有することが示されている。なお、オブジェクト定義１２１０がオブジェクト定義１２０５を継承したクラスであることが継承関係を表現するエッジ１２３５によって表現されている。オブジェクト定義１２１０とオブジェクト定義１２０５の間には”members”という関連１２２５が存在し、それはインターリンク１１２５に対応する。関連１２２５に付された”*”記号１２３０は当該関連の許容多重度（何本まで関連を形成することが許されるか）であり、”*”は多重度に制限がないことを意味している。

オブジェクト定義１２１５は、その名称が”C”であり、カーネル・パターンγにマッチしたときにインスタンス化され、カーネル・パターン内のノード変数”#X”にマッチしたノードに付された文字列（String）を属性値とする”x”という属性を有することが示されている。オブジェクト定義１２２０は、その名称が”D”であり、カーネル・パターンδにマッチしたときにインスタンス化され、カーネル・パターン内のノード変数”#Y”にマッチしたノードに付された文字列（String）を属性値とする”y”という属性を有することが示されている。これらのモデル定義がどのようにオブジェクトデータの生成に使用されるかは後で詳述される。

処理はステップ３２０へ進み、ユーザは、アプリケーション・プログラムを操作することによって、データ処理システム上のアプリケーション部２６０からグラフデータ変更部２５０、リポジトリ・アクセス部２０５を介して作業対象のグラフデータの問合せをグラフ・リポジトリ２７５に対して行う。かかるグラフデータの問合せはアプリケーション・プログラム上のグラフデータ問合せ操作を検出して解釈し、ＳＰＡＲＱＬ言語に従うクエリを生成し、グラフ・リポジトリ２７５に送信することによって実行される。

次いで、ステップ３２５においてリポジトリ・アクセス部２０５が入手したグラフデータが当該ユーザの操作するアプリケーション・プログラムの目的に適した形式となるように、パターン記憶部２３０に記憶されたカーネル・パターン、オブジェクト定義記憶部２２５に記憶されたオブジェクト定義を用いて、グラフデータがオブジェクトデータへ変換される。既述の通り、変換され生成されたオブジェクトデータは、オブジェクトデータ記憶部２４０に記憶される。当該オブジェクトデータへの変換は、図４、図５を用いて後で詳細に説明される。

処理はステップ３３０に進み、ステップ３２５において得られ、オブジェクトデータ記憶部２４０に記憶されたオブジェクトデータに対する操作が実行される。本発明の実施形態では、オブジェクトデータに対する操作は、オブジェクトデータの有する準同型的性質を利用してグラフ・リポジトリ２７０に記憶されたグラフデータに反映されることとなる。かかる処理は、図６、７、８、９、１０を用いて後で詳述される。

次いで、ステップ３３５において作業対象のオブジェクトデータに対する操作が完了したかどうかが判断される。ステップ３３５において作業対象のオブジェクトデータに対する操作が完了していないと判断された場合、処理はＮＯの矢印を通じてステップ３３０へ戻り、オブジェクトデータに対する操作が継続される。ステップ３３５において作業対象のオブジェクトデータに対する操作が完了したと判断された場合、処理はＹＥＳの矢印を通じてステップ３４０へ進む。

ステップ３４０においては、他のグラフデータに対する操作を行うかどうかが判定される。ステップ３４０で他のグラフデータに対する操作を行うと判断された場合、処理はＹＥＳの矢印を介してステップ３２０に戻り、当該他のグラフデータの部分がグラフ・リポジトリ２７５から読み出され、以降同様の処理が繰り返される。ステップ３４０で他のグラフデータに対する操作を行わないと判断された場合、処理はＮＯの矢印を介してステップ３４５に進み終了する。

次に、図４のフローチャート３２０を使用して、図４のステップ３２０におけるグラフデータからオブジェクトデータへの変換処理の一例をより詳細に説明する。図４は、本発明の実施形態におけるデータ処理システムのオブジェクトデータ生成動作を表現するフローチャート３２０である。処理は、ステップ４０５でスタートし、ステップ４１０でグラフ・レポジトリ２７５にＳＰＡＲＱＬ言語に従うクエリを用いてグラフデータの問い合わせを行う。図１３は、本発明の実施形態におけるグラフ・レポジトリから読み出され返送されたグラフデータ１３００である。本発明の実施形態では、かかる一例としてのグラフデータ１３００がグラフ・レポジトリに記憶されており、ＳＰＡＲＱＬ言語に従うクエリを用いて作業対象として読み出されて、オブジェクトデータに変換されるものとする。

次に、処理はステップ４１５に進み、ステップ４１０において得られたグラフデータ１２００に対して、カーネル・パターン記憶部２３０に記憶されたカーネル・パターンを用いてパターン・マッチングを行う。本発明の実施形態では、このパターン・マッチングは、ユーザが操作する端末上でカーネル・パターンごとに用意されたＳＰＡＲＱＬ言語に従うクエリを作業対象となるグラフデータに関して実行することで実施する。

図１４は、本発明の実施形態におけるカーネル・パターンごとに用意されたＳＰＡＲＱＬ言語に従うグラフ・クエリのセット１４００である。グラフ・クエリのセット１４００に含まれるクエリ１４０５、１４１０、１４１５、１４２０、１４２５は、それぞれ図１０に示すカーネル・パターン１１０５、１１１０、１１１５、１１２０およびインターリンク１１２５に対応する。このクエリをそれぞれステップ４１０において得られたグラフデータに対して実行することによってそれぞれのカーネル・パターンにマッチするグラフデータ１３００のサブセットに関する情報が得られることとなる。

処理はステップ４２０に進み、ステップ４１５で得られたカーネル・パターンにマッチするグラフデータ１２００のサブセットに関する情報としてデータ・バインディング・テーブル（ＤＢＴ）と称されるテーブル構造のデータが形成される。ＤＢＴは、対応するカーネル・パターンに含まれるノードとそれにマッチしたグラフデータ内のノードとの対応関係をエントリとして含む。

図１５は、本発明の実施形態における、カーネル・パターンに対応するＳＰＡＲＱＬ言語に従うグラフ・クエリによる照会結果である初期ＤＢＴｓの一例である。本発明の実施形態では、カーネル・パターンαに関しては、グラフデータのサブセットが５つマッチングに成功している（テーブル１５０５、１５１０、１５１５、１５２５）。カーネル・パターンβに関しては、１つマッチングに成功している（テーブル１５３０）。カーネル・パターンγについては、１つマッチングに成功している（テーブル１５３５）。カーネル・パターンδについては、グラフデータのサブセットはマッチせず、ＤＢＴは形成されていない。インターリンクmembersについては、２つのエッジがマッチングに成功している（テーブル１５４０、１５４５）。

処理はステップ４２５に進み、正規化の処理が実施される。ここで、図５のフローチャート４２５を使用して、図５のステップ４２５におけるＤＢＴの正規化の処理の一例をより詳細に説明する。まず、処理はステップ５０５でスタートし、ステップ５１０でステップ４２０において得られた初期ＤＢＴをスキャンし、複数のＤＢＴにおいて代表ノード（カーネル・パターンにおいて”$”の接頭辞が付されたノード）とマッチしたグラフデータ内のノードを特定する。本発明の実施形態では、ノードb1（ＤＢＴ１５１０およびＤＢＴ１５３０おいて代表ノードとマッチしている）およびノードu1（ＤＢＴ１５０５およびＤＢＴ１５３５において代表ノードにマッチしている）が特定される。

次いで、ステップ５１５において、ステップ５１０で特定されたノードが含まれないＤＢＴ、すなわち、そのＤＢＴの代表ノードにマッチしたグラフデータのノードが他のＤＢＴにおいて代表ノードにマッチしていないＤＢＴに関して、代表ノードに対応するオブジェクト定義が割り当てられる。その結果、ＤＢＴ１５１５、１５２０、１５２５の代表ノード（すなわち、a1、a2、a3）にはそれぞれオブジェクト定義１２０５（名称：”Member”）が割り当てられる。

処理はステップ５２０に進み、ステップ５１０において特定されたノードが含まれているＤＢＴ（複数存在する）について、当該ＤＢＴに対応するオブジェクト定義の間に継承関係にある場合に、継承された側のオブジェクト定義に対応するＤＢＴを除去したうえで、継承をした側のオブジェクト定義に対応するＤＢＴに対応するオブジェクト定義を代表ノードに割り当てる。本発明の実施形態では、ＤＢＴ１５１０とＤＢＴ１５３０について、それぞれに対応するオブジェクト定義１２０５、１２１０は継承関係にあるので、継承された側であるＤＢＴ１５１０が除去され、継承した側であるＤＢＴ１５３０が残され、代表ノード（すなわち、b1）対応するオブジェクト定義１２１０（名称：”Group”）が割り当てられる。

次いでステップ５２５において、ステップ５１０特定されたノードが含まれているＤＢＴについて、当該ＤＢＴに対応するオブジェクト定義の間に継承関係にない場合に、当該ＤＢＴのすべてが除去される。本発明の実施形態では、ＤＢＴ１５０５、ＤＢＴ１５３５が除去される。

上述したステップ５１０ないし５２５が実行されることによって、第１の制約条件を用いたＤＢＴの除去および代表ノードへのオブジェクト定義の割り当てが実現する。その結果、本発明の実施形態では、ＤＢＴ１５０５、１５１０、１５３５が除去され、ＤＢＴ１５１５、１５２０、１５２５、１５３０、ＤＢＴ１５４０、ＤＢＴ１５４５がＤＢＴ記憶部２３５に残されることとなる。なお、本発明の実施形態では、上述のＤＢＴの除去およびオブジェクト定義の割り当ては、図１６に示すオブジェクト定義割り当てテーブル１６００を生成し、処理することによって実施される。

処理はステップ５３０に進み、上述したカーネル・パターン内の第２の制約条件を用いたＤＢＴの除去が実行される。本発明の実施形態では、カーネル・パターン１１０５の第２の制約条件を表す接頭辞”#”が付されているユニーク・ノード”#N1”について、ＤＢＴ１５１５、１５２０でノード”n1”が対応している。ユニーク・ノードである”#N1”はカーネル・パターン１１０５の代表ノード”$A”にマッチするノードにユニークに対応していなければならないので、ＤＢＴ１５１５およびＤＢＴ１４２０が除去されることとなる。その結果として、ＤＢＴ１５２５、ＤＢＴ１５３０、ＤＢＴ１５４０、ＤＢＴ１５４５がＤＢＴ記憶部２３５に残されることとなる。

次いで、ステップ５３５において、インターリンクに対応するＤＢＴの除去が実行される。具体的には、それまでのカーネル・パターンに対応するＤＢＴの正規化処理（ステップ５０５〜５３０）を実行した結果としてＤＢＴ記憶部２３５に残っているＤＢＴを参照し、それらの内容と整合しないインターリンクに対応するＤＢＴを除去する。本発明の実施形態では、ＤＢＴ１５４０がＤＢＴ１５２５、ＤＢＴ１５３０に対応しないので除去される。その結果、ＤＢＴ１５２５、１５３０、１５４５がＤＢＴ記憶部２３５に残ることとなる。

処理はステップ５４０に進み、インターリンクの多重度がオブジェクト定義に記述された許容多重度を満たしているかどうかが判定される。また、ステップ５４０では、許容多重度を満たしていなかった場合の処理も実施される。かかる処理は、たとえば、ユーザに警告を提示してどのインターリンクをインスタンス化するかを選択させる、あるいは、そこで処理を停止するなど様々なやり方が考えられるが、当業者は適宜かかる処理を実施することができるのでここでは詳細な説明は省略する。

次いでステップ５４５において、インターリンクに対応するＤＢＴの内容が、当該インターリンクの参照元であるオブジェクトに対応するＤＢＴに反映される。具体的には、当該インターリンクの名称と参照先ノードの名称の対応を含むエントリが参照元であるオブジェクトに対応するＤＢＴに追加される。本発明の実施形態では、ＤＢＴ１５４５の内容がＤＢＴ１５３０に追加される。処理はステップ５４４に進み終了する。本発明の実施形態における正規化処理が実施されたＤＢＴの内容を図１７に示す。

図４に説明を戻し、ステップ４３０において、ステップ４２５で正規化されたＤＢＴ記憶部２４０に記憶されたＤＢＴと、オブジェクト定義記憶部２３０に記憶されたオブジェクト定義を参照し、グラフデータをオブジェクトデータに変換する、つまり、オブジェクト定義をインスタンス化することによって、オブジェクトデータを生成してオブジェクトデータ記憶部２４５に記憶する。図１８に、本発明の実施形態における生成されたオブジェクトデータの例を示す。次いで処理はステップ４３５に進み、オブジェクトデータがアプリケーション部２６０のアプリケーション・プログラムに送られ、入出力部２７０を介してユーザに視覚的に提示される。そして、ステップ４４０において処理は終了する。

次に、図６のフローチャート３３０を使用して、図３のステップ３３０におけるオブジェクトデータの操作処理およびそれに伴うグラフ・リポジトリ内のグラフデータへの反映処理の一例をより詳細に説明する。図５は、本発明の実施形態におけるデータ処理システムのオブジェクトを操作した場合の動作を表現するフローチャートである。処理は、ステップ６０５からスタートし、ステップ６１０において操作ログ記憶部２５５が、ユーザがアプリケーション・プログラムにおいて実行したオブジェクトデータ操作のログ（本明細書において、単に「操作ログ」という）をアプリケーション部２６０から受け取り、記憶する。

処理はステップ６１５に進み、ステップ６１０において操作ログ記憶部２５５に記憶された操作ログから１つ操作を読み込む。次いで処理はステップ５２０に進み、読み込んだ操作がオブジェクトの生成（ＣＲＥＡＴＥ）、オブジェクトの更新（ＵＰＤＡＴＥ）、オブジェクトの削除（ＤＥＬＥＴＥ）のいずれであるかを判定する。本発明の実施形態において、オブジェクトの生成（ＣＲＥＡＴＥ）操作は、新たにオブジェクトを追加することを含む。また、オブジェクトの更新（ＵＰＤＡＴＥ）操作は、既に存在するオブジェクトの属性値の変更、オブジェクト間の関連の追加または削除を含む。さらに、オブジェクトの削除（ＤＥＬＥＴＥ）操作は、既に存在するオブジェクトを削除することを含む。

ステップ６２０において、ステップ６１５で読み込んだ操作がオブジェクトの生成（ＣＲＥＡＴＥ）であると判定された場合、処理はＣＲＥＡＴＥのラベルが付された矢印を介してステップ６２５へ進み、ステップ６１５で読み込んだ操作の対象であるオブジェクトに対応するＤＢＴに対してＣＲＥＡＴＥ操作に対応するＤＢＴ処理が実行され、次いでステップ６４０に進む。このＣＲＥＡＴＥ操作に対応するＤＢＴ処理は、図７のフローチャートを用いて後で詳細に説明される。

ステップ６２０において、ステップ５１５で読み込んだ操作がオブジェクトの更新（ＵＰＤＡＴＥ）であると判定された場合、処理はＵＰＤＡＴＥのラベルが付された矢印を介してステップ６３０へ進み、ステップ６１５で読み込んだ操作の対象であるオブジェクトに対応するＤＢＴに対してＵＰＤＡＴＥ操作に対応するＤＢＴ処理が実行され、次いでステップ６４０に進む。このＵＰＤＡＴＥ操作に対応するＤＢＴ処理は、図８のフローチャートを用いて後で詳細に説明される。

ステップ６２０において、ステップ６１５で読み込んだ操作がオブジェクトの削除（ＤＥＬＥＴＥ）であると判定された場合、処理はＤＥＬＥＴＥのラベルが付された矢印を介してステップ６３５に進み、ステップ６１５で読み込んだ操作の対象であるオブジェクトに対応するＤＢＴに対してＤＥＬＥＴＥ操作に対応するＤＢＴ処理が実行され、次いでステップ６４０に進む。このＤＥＬＥＴＥ操作に対応するＤＢＴ処理は、図９のフローチャートを用いて後で詳細に説明される。

ステップ６４０では、ステップ６１５で読み込まれた操作の対象であるオブジェクトに対応するＤＢＴのエントリがすべて埋まっているかどうかが判定される。ステップ６４０でＤＢＴのエントリが埋まっていると判定されなかった場合、処理はＮＯの矢印を介してステップ６５０に進む。

ステップ６４０でＤＢＴのエントリが埋まっていると判定された場合、処理はステップ６４５に進み、ＤＢＴを用いたグラフ・リポジトリ２７５内のグラフデータの変更が実施される。このグラフデータの変更処理は、図１０のフローチャートを用いて後で詳細に説明される。

処理はステップ６５０に進み、操作ログにまだ操作が残っているかどうかが判定される。ステップ６５０で残っていると判定された場合は、処理はＹＥＳの矢印からステップ６１５に戻り、操作ログ内の次の一つの操作について同様の処理を繰り返す。ステップ６５０で残っていないと判定された場合、処理はＮＯの矢印からステップ６５５へ進み終了する。

次に、図７のフローチャート６２５を使用して、図６のステップ６２５におけるオブジェクトデータ内のオブジェクトの生成（ＣＲＥＡＴＥ）操作に対応するＤＢＴ処理の一例をより詳細に説明する。図６は、本発明の実施形態におけるデータ処理システムのオブジェクトの生成（ＣＲＥＡＴＥ）操作に対応するＤＢＴ処理の動作を表現するフローチャートである。処理はステップ７０５からスタートし、ステップ７１０においてステップ６１５で読み込んだ生成（ＣＲＥＡＴＥ）操作の対象となるオブジェクトに対応するカーネル・パターンを特定する。

次いで、ステップ７１５において、対象オブジェクトに対応するカーネル・パターンの代表ノードにマッチするノードのための識別子を決定する。次に、ステップ７２０において当該カーネル・パターンに対応するＤＢＴを新規に生成し、ステップ７２５において新規に生成されたＤＢＴにカーネル・パターンの代表ノードと、当該代表ノードにマッチするグラフデータ内のノード（ステップ７１５で生成した識別子によって表される）のエントリを追加する。

処理はステップ７３０において共有ノードを問い合わせるためのＳＰＡＲＱＬ言語に従うクエリをカーネル・パターンから生成する。共有ノードとは、あるオブジェクトに関連するグラフデータのノードのうち、他のオブジェクトにも関連し得るノードをいうものとする。すなわち、共有ノードは、グラフデータの準同型写像の像であるデータ構造に変換できない部分である。本発明の実施形態では、一般ノード変数、直接指定ノード、リテラル・ノードのみから成るパターンにマッチするノードが共有ノードとなり得る。

本発明の実施形態では、グラフ・リポジトリ２７５には２つのノードとそれらを接続するエッジの組の集合としてＲＤＦフォーマットに従うグラフデータが記憶されているものとする。したがって、共有ノードを問い合わせるためのクエリは、カーネル・パターン内の（１）２つの一般ノード変数とそれらを接続するエッジの組（２）一般ノード変数と直接指定ノードおよびそれらを接続するエッジの組（３）一般ノード変数とリテラル・ノードおよびそれらを接続するエッジの組（４）２つの直接指定ノードとそれらを接続するエッジの組（５）直接指定ノードとリテラル・ノードおよびそれらを接続するエッジの組、を抽出して、これらの条件を満たすノードを問い合わせるようなクエリを生成するとよい。

次いでステップ７３５において、ステップ７３０で生成したクエリをグラフ・リポジトリ２７５に送信し、返送されてきた共有ノードの情報に基づいて、ステップ７２５において生成したＤＢＴに共有ノードに対応するエントリを追加する。そして、処理はステップ７４０に進み、終了する。この時点で、代表ノードと共有ノード（存在する場合）についてのみエントリが存在し、残余のノード等については空のエントリとなっているＤＢＴが形成されることとなる。

図８のフローチャート６３０を使用して、図６のステップ６３０におけるオブジェクトデータ内のオブジェクトの更新（ＵＰＤＡＴＥ）操作に対応するＤＢＴ処理の一例をより詳細に説明する。図７は、本発明の実施形態におけるデータ処理システムのオブジェクトの更新（ＵＰＤＡＴＥ）操作に対応するＤＢＴ処理の動作を表現するフローチャートである。処理はステップ８０５からスタートし、ステップ８１０においてステップ６１５で読み込んだ更新（ＵＰＤＡＴＥ）操作の対象となるオブジェクトに対応するＤＢＴを特定する。

次いで、ステップ８１５においてステップ６１５で読み込んだ更新（ＵＰＤＡＴＥ）操作の内容に応じて、ステップ８１０において特定したＤＢＴのエントリを更新する。処理はステップ８２０に進み、ステップ８１５において更新したエントリに更新マークが付けられ、ステップ８２５にて処理が終了する。

図９のフローチャート６３５を使用して、図６のステップ６２５におけるオブジェクトデータ内のオブジェクトの削除（ＤＥＬＥＴＥ）操作に対応するＤＢＴ処理の一例をより詳細に説明する。図８は、本発明の実施形態におけるデータ処理システムのオブジェクトの削除（ＤＥＬＥＴＥ）操作に対応するＤＢＴ処理の動作を表現するフローチャートである。処理はステップ９０５からスタートし、ステップ９１０においてステップ６１５で読み込んだ削除（ＤＥＬＥＴＥ）操作の対象となるオブジェクトに対応するＤＢＴを特定する。次いで、ステップ９１５においてステップ９１０で特定されたＤＢＴに削除マークが付され、ステップ９２０にて処理が終了する。

次に、図１０のフローチャート６４５を使用して、図６のステップ６４５におけるＤＢＴに基づくグラフ・リポジトリ内のグラフデータの変更処理の一例をより詳細に説明する。図１０は、本発明の実施形態におけるデータ処理システムのグラフデータ変更処理の動作を表現するフローチャートである。処理はステップ１００５からスタートし、ステップ１０１０で、ステップ６１５で読み込んだ操作の対象となるオブジェクトに対応するカーネル・パターンを特定する。

処理はステップ１０１５に進み、ステップ６１５で読み込んだ操作の対象となるオブジェクトに対応するＤＢＴに削除マークが付されているかどうかが判定される。ステップ１０１５においてにＤＢＴに削除マークが付されていると判定された場合、処理はＹＥＳの矢印からステップ１０２０に進む。

ステップ１０２０では、ステップ１０１０において特定されたカーネル・パターンを用いて、操作対象のオブジェクトに含まれるグラフデータのノードのうち、共有ノードではないノードを特定する。具体的には、ステップ７３０とともに説明した共有ノードを問い合わせるクエリを生成してグラフ・リポジトリ２７５に送信して、共有ノードを特定し、操作対象のオブジェクトに含まれるグラフデータのノードから特定された共有ノードを除外するとよい。

次いで、ステップ１０２５において、ステップ１０２０で特定された共有ノードでないノードの集合からノードを一つ取り出し、処理はステップ１０３０に進む。ステップ１０３０においては、ステップ１０２５で取り出されたノードに関連するグラフデータのノードおよび／またはエッジを、グラフ・リポジトリに問合せを行うことによって削除する。ステップ１０３５において、ステップ１０２０で特定されたノードがまだ残っているかどうかが判定される。残っていると判定された場合は、ＹＥＳの矢印を介してステップ１０２５に戻り、同様の処理が繰り返される。残っていないと判定された場合は、ＮＯの矢印からステップ１０６０に進み、処理は終了する。

ステップ１０１５においてにＤＢＴに削除マークが付されていると判定されなかった場合、処理はＮＯの矢印からステップ１０４０に進む。ステップ１０４０では、ステップ６１５で読み込んだ操作の対象となるオブジェクトに対応するＤＢＴ内の更新マークが付けられたエントリが特定される。

次いで、ステップ１０４５において、ステップ１０４０で特定された更新マークが付けられたエントリの集合からエントリを一つ取り出し、処理はステップ１０５０に進む。ステップ１０５０においては、ステップ１０４５で取り出されたエントリの内容に従って、グラフ・リポジトリ内のグラフデータのノードおよび／またはエッジを更新する。ステップ１０５５において、ステップ１０４０で特定されたエントリがまだ残っているかどうかが判定される。残っていると判定された場合は、ＹＥＳの矢印を介してステップ１０４５に戻り、同様の処理が繰り返される。残っていないと判定された場合は、ＮＯの矢印からステップ１０６０に進み、処理は終了する。

以上、オブジェクトデータの操作処理およびそれに伴うグラフ・リポジトリ内のグラフデータへの反映処理を説明したが、以下に２つの例によってオブジェクト操作とそれに伴うＤＢＴの処理等を示す。

図１９は、オブジェクト操作の流れの第１の例である。この第１の例では、図１８に示されたオブジェクトデータに新たにオブジェクト１９０５（"Member”）が生成（ＣＲＥＡＴＥ）され、次いで、生成されたオブジェクト１９０５に属性値”Yamada”が入力され（ＵＰＤＡＴＥ）、次いで、オブジェクト１８１０およびオブジェクト１９０５の間に関連１９１５が追加された（ＵＰＤＡＴＥ）ものとする。

図２０は、オブジェクト操作の流れの第１の例の操作ログである。上述のオブジェクト生成操作、属性値の入力操作、関連の追加操作がそれぞれ操作ログ２００５、２０１０、２０１５として記録されている。

図２１は、オブジェクト操作の流れの第１の例に応じて変化するＤＢＴを示している。まず、オブジェクト１９０５の生成に対応する操作ログ２００５を読み込んでＤＢＴ処理をすることによって、代表ノード変数（”$A”）と一般ノード変数（”?S1”）のエントリのみが存在するＤＢＴ２１０５が生成される。次いで、属性値”Yamada”の入力に対応する操作ログ２０１０を読み込んでＤＢＴ処理を行うことによって、ＤＢＴ２１０５のユニーク・ノード”#N”のエントリが更新される。そして、すべてのエントリが存在することとなったＤＢＴ２１０５に基づいて、グラフ・リポジトリ２７５内のグラフデータの変更が実施される。

次いで、関連１９１５の追加に対応する操作ログ２０１５を読み込んでＤＢＴ処理をすることによって、ＤＢＴ１５３０のインターリンク”members”のエントリに関連１９１５に対応する情報２１１０が追加される。そして、ＤＢＴ１５３０に基づいて、グラフ・リポジトリ２７５内のグラフデータの変更が実施される。これらの変更がされた結果のグラフ・リポジトリ２７５内のグラフデータを図２２に示す。

図２３は、オブジェクト操作の流れの第２の例である。この第２の例では、図２２に示された第１の例の操作が施された後のオブジェクトデータに対して、まず既存のオブジェクト２３０５の属性値を”Suzuki”から”Suzuta”に変更（ＵＰＤＡＴＥ）し、次いで、関連１９１５の削除（ＵＰＤＡＴＥ）およびオブジェクト１９０５の削除（ＤＥＬＥＴＥ）を行ったものとする

図２４は、オブジェクト操作の流れの第２の例の操作ログである。上述のオブジェクト属性値の変更操作、関連の削除捜査、オブジェクトの削除操作がそれぞれ操作ログ２４０５、２４１０、２４１５として記録されている。

図２５は、オブジェクト操作の流れの第２の例に応じて変化するＤＢＴを示している。まず、オブジェクト２３０５の属性値変更に対応する操作ログ２４０５を読み込んでＤＢＴ処理をすることによって、ＤＢＴ１５２５の属性値２５０５が変更される。そして、ＤＢＴ１５２５に基づいて、グラフ・リポジトリ２７５内のグラフデータの変更が実施される。

次いで、関連１９１５の削除に対応する操作ログ２４１０を読み込んでＤＢＴ処理をすることによって、ＤＢＴ１５３０のインターリンク”members”のエントリに関連１９１５に対応する情報２１１０が削除される。そして、ＤＢＴ１５３０に基づいて、グラフ・リポジトリ２７５内のグラフデータの変更が実施される。さらに、オブジェクト１９０５の削除操作に対応する操作ログ２４１５を読み込んでＤＢＴ処理をすることによって、ＤＢＴ２１０５に削除マーク２５１０が付される。この削除マーク２５１０が付されたＤＢＴ２１０５に基づいて、グラフ・リポジトリ２７５内のグラフデータの変更が実施される。これらの変更がされた結果のグラフ・リポジトリ２７５内のグラフデータを図２６に示す。

図２７は、本発明の実施の形態による端末１００、１０５、サーバ１１０等を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。情報処理装置は、バス２に接続されたＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、およびＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフロッピーディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。

フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。メインメモリ４にロードされることによってコンピュータ・プログラムは実行される。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。

情報処理装置は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。情報処理装置は、視覚データをユーザに提示するための表示装置１１にＤＡＣ／ＬＣＤＣ１０を経由して接続される。

情報処理装置は、ネットワーク・アダプタ１８（イーサネット（Ｒ）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。図示はされていないが、パラレルポートを介してプリンタと接続することや、シリアルポートを介してモデムを接続することも可能である。

以上の説明により、本発明の実施の形態によるデータ処理システムを実現するのに好適な情報処理装置は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、または、これらの組み合わせによって実現されることが容易に理解されるであろう。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。

本発明の実施の形態において使用される情報処理装置の各ハードウェア構成要素を、複数のマシンを組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。

本発明の実施の形態のデータ処理システムは、マイクロソフト・コーポレーションが提供するＷｉｎｄｏｗｓ（Ｒ）オペレーティング・システム、アップル・コンピュータ・インコーポレイテッドが提供するＭａｃＯＳ（Ｒ）、Ｘ Ｗｉｎｄｏｗ Ｓｙｓｔｅｍを備えるＵＮＩＸ（Ｒ）系システム（たとえば、インターナショナル・ビジネス・マシーンズ・コーポレーションが提供するＡＩＸ（Ｒ））のような、ＧＵＩ（グラフィカル・ユーザー・インターフェース）マルチウインドウ環境をサポートするオペレーティング・システムを採用する。

以上から、本発明の実施の形態において使用されるデータ処理システムは、特定のマルチウインドウ・オペレーティング・システム環境に限定されるものではないことを理解することができる。

以上、本発明の実施形態によれば、グラフデータを各種アプリケーションによる操作を元のグラフデータに反映することができるデータ構造に変換する、効率的なシステム、ソフトウェア、および方法が実現される。従って、オブジェクト・ハンドリング・システムを操作してオブジェクトデータを操作することによってグラフ・リポジトリに格納されたグラフデータを編集するユーザの生産性を高めることができることが容易に理解できる。

また、本発明は、ハードウェア、ソフトウェア、またはハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアの組み合わせによる実行において、所定のプログラムを有するデータ処理システムにおける実行が典型的な例として挙げられる。かかる場合、該所定プログラムが該データ処理システムにロードされ実行されることにより、該プログラムは、データ処理システムを制御し、本発明にかかる処理を実行させる。このプログラムは、任意の言語・コード・表記によって表現可能な命令群から構成される。そのような命令群は、システムが特定の機能を直接、または１．他の言語・コード・表記への変換、２．他の媒体への複製、のいずれか一方もしくは双方が行われた後に、実行することを可能にするものである。

もちろん、本発明は、そのようなプログラム自体のみならず、プログラムを記録した媒体もその範囲に含むものである。本発明の機能を実行するためのプログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ハードディスク装置、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。かかるプログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システムからダウンロードしたり、他の記録媒体から複製したりすることができる。また、かかるプログラムは、圧縮し、または複数に分割して、単一または複数の記録媒体に格納することもできる。また、様々な形態で、本発明を実施するプログラム製品を提供することも勿論可能であることにも留意されたい。

上記の実施の形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。例えば、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。

Claims (17)

1. パターン記憶部と、処理部と、生成部とを備えるコンピュータにより、１以上のグラフ・マッチングのためのパターンを用いて、ノードとエッジを含むグラフデータの少なくとも一部をその準同型写像の像であるデータ構造に変換する方法であって、
   前記パターン記憶部により、パターンに１つ存在する代表ノード変数であって、当該代表ノード変数にマッチしたグラフデータのノードが高々１つで、かつ他のパターンのノード変数にマッチすることが禁止されるという第１の制約を有する代表ノード変数を含むパターンを提供するステップと、
   前記処理部により、前記グラフデータと前記パターンのマッチング処理を行い、前記第１の制約を含む制約に違反しないマッチング結果を得るステップと、
   前記生成部により、前記制約に違反しないマッチング結果に対応するデータ構造を生成するステップと、
   を含む、方法。
2. 前記マッチング処理を行うステップは、前記処理部により、前記パターンにマッチするグラフデータのサブセットに関する情報をマッチング結果として得るステップと、前記処理部により、前記制約に違反するグラフデータのサブセットに関する情報をマッチング結果から除去するステップと、を含む請求項１に記載の方法。
3. グラフデータのサブセットに関する情報が、パターンに含まれるノード変数とそれにマッチしたグラフデータ内のノードとの対応関係をエントリとして含むテーブルである、請求項２に記載の方法。
4. 前記マッチング結果から除去するステップが、前記処理部により、前記制約に違反するグラフデータのサブセットに対応する前記テーブルを除去するステップを含む、請求項３に記載の方法。
5. 前記代表ノードが、他のパターンに属するノードとの間のインターリンクの端点となり得る、請求項１に記載の方法。
6. 前記マッチング処理を行うステップにおいて代表ノードがマッチした複数のパターンが継承関係にある場合、前記生成部により、継承した側のパターンへのマッチング結果に対応するデータ構造が生成される、請求項１に記載の方法。
7. 前記パターンは、１以上の第２の種類のノード変数を含み、前記第２の種類のノード変数にマッチするグラフデータのノードがパターンの代表ノード変数にマッチするグラフデータのノードにユニークに対応しなければならないという第２の制約を有し、前記生成部により、前記第１の制約および第２の制約に違反しないマッチング結果に対応するデータ構造が生成される、請求項１に記載の方法。
8. 前記第２の種類のノード変数にマッチするノードが、他のパターンに属するノードとの間のインターリンクの端点となり得る、請求項１に記載の方法。
9. 前記マッチング処理を行うステップは、前記処理部により、パターンに対応するグラフ・クエリを前記グラフデータに対して実行するステップを含む、請求項１に記載の方法。
10. 前記マッチング処理を行うステップは、前記処理部により、異なるパターンに属するノードを接続するインターリンクのマッチング処理を行うステップを含む、請求項１に記載の方法。
11. 前記マッチング処理を行うステップは、前記処理部により、ノード変数に関するマッチング結果と整合しないインターリンクのマッチング結果を除去するステップを含む、請求項１０に記載の方法。
12. 前記マッチング処理を行うステップは、前記処理部により、インターリンクのマッチング処理結果をノード変数のマッチング処理結果にマージするステップを含む、請求項１０に記載の方法。
13. 前記データ構造を生成するステップは、前記生成部により、前記パターンに対応するデータ構造のクラス定義をインスタンス化することによってデータ構造を生成するステップを含む、請求項１に記載の方法。
14. 前記コンピュータは入出力部を更に備え、生成したデータ構造をアプリケーションに引渡し、前記入出力部を介してユーザに提示するステップをさらに含む、請求項１に記載の方法。
15. 請求項１ないし１４のいずれかに記載の方法のすべてのステップをコンピュータに実行させることができる、プログラム。
16. １以上のグラフ・マッチングのためのパターンを用いて、ノードとエッジを含むグラフデータの少なくとも一部をその準同型写像の像であるデータ構造に変換するためのプログラムであって、
    パターンに１つ存在する代表ノード変数であって、当該代表ノード変数にマッチしたグラフデータのノードが高々１つで、かつ他のパターンのノード変数にマッチすることが禁止されるという第１の制約を有する代表ノード変数を含むパターンを提供するステップと、
    前記グラフデータと前記パターンのマッチング処理を行い、前記第１の制約を含む制約に違反しないマッチング結果を得るステップと、
    前記制約に違反しないマッチング結果に対応するデータ構造を生成するステップと、
    をコンピュータに実行させる、プログラム。
17. １以上のグラフ・マッチングのためのパターンを用いて、ノードとエッジを含むグラフデータの少なくとも一部をその準同型写像の像であるデータ構造に変換する装置であって、
    パターンに１つ存在する代表ノード変数であって、当該代表ノード変数にマッチしたグラフデータのノードが高々１つで、かつ他のパターンのノード変数にマッチすることが禁止されるという第１の制約を有する代表ノード変数を含むパターンを記憶するパターン記憶部と、
    前記グラフデータと前記パターンのマッチング処理を行い、前記第１の制約を含む制約に違反しないマッチング結果を得る処理部と、
    前記制約に違反しないマッチング結果に対応するデータ構造を生成する生成部と、
    を備える、装置。

Images