JP5745932B2 - グラフデータに写像の像であるオブジェクトに対する操作を反映する方法、プログラム、および、システム - Google Patents

Description

本発明は、一般的には、データ操作のための情報処理技術に関し、より特定的には、グラフデータにその写像の像であるオブジェクトに対する操作を反映する方法、プログラム、および、システムに関する。

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

当分野の背景技術として、特開１９９７−００１６３８９号公報（特許文献１）は、プログラム部品自動生成装置を開示する。装置は、仕様に応じてプログラム部品案を生成する手段と、生成されたプログラム部品案を逐次整理保存し、かつ変更履歴を管理する部品ライブラリと、部品ライブラリ内に存在するプログラム部品がそれぞれもつ機能の一部を変換する手段とを有し、検索要求に適合する新たな機能を持つプログラム部品を生成する。

他の背景技術として、特開２０１０−００３３５００号公報（特許文献２）は、GUIデータ変換方法を開示する。方法は、変換元のGUIオブジェクトから変換先のGUIオブジェクトへの変換で1対多の関係が起こりうるGUIリソースデータを変換するGUIデータ変換システムにおいて、変換元のGUIツールで作成された変換元GUIリソースデータを入力し、変換元GUIオブジェクトの変換先GUIオブジェクトへの変換規則を含む変換テーブルを生成し、前記変換テーブルを解釈して前記変換元GUIオブジェクトに対する変換処理を特定し、前記変換元GUIリソースデータに対して前記特定された変換処理を施し、前記変換先GUIリソースデータとして書き出す。

他の背景技術として、特開２００８−０１５８７５９号公報（特許文献３）は、プログラムモジュール同士の並列処理の関係を記述した並列実行制御記述から、個々の前記プログラムモジュールに関連する部分を抽出した先行情報と後続情報を含むグラフデータ構造生成情報に基づいて所定のプログラムモジュールを抽出し、これを依存関係に従ってグラフデータ構造に追加更新し、先行するノードすべてが処理済であるノードから実行する処理方法とするプログラミング方法を開示する。

他の背景技術として、特開２０１０−０２５６９７８号公報（特許文献４）は、コンフィグレーションデータ検証装置を開示する。装置は、システムのコンフィグレーションデータからシステムを構成するコンポーネント間の依存関係を抽出し、当該依存関係を表す関係グラフを生成する関係グラフ生成部と、予め与えられた基準関係グラフと生成された関係グラフとに基づいて、コンフィグレーションデータの妥当性を検証する関係グラフ検証部とを有している。

他の背景技術として、特開２００６−０１８５２１１号公報（特許文献５）は、プログラム解析装置を開示する。装置は、対象プログラムを１ステップずつ実行し、この１ステップごとに、オブジェクトのフィールドの変更履歴とその変更の原因となったオブジェクトのフィールドの情報を取得して、各オブジェクトの状態単位での因果関係を抽出する因果関係抽出部１０と、所定のオブジェクトを検証対象とし、因果関係抽出部１０により抽出されたオブジェクト間の因果関係に基づき、検証対象のオブジェクトに対する因果関係を分析して原因に当たるオブジェクトを検出し、検出対象のオブジェクトと原因であるオブジェクトとの間に設定されるテストのアサーションに基づいて、テストを実行するテスト実行部２０とを備える。

他の背景技術として、特開２００５−０１００４０２号公報（特許文献６）は、オブジェクト指向プログラムが、指定された領域内でオブジェクトを作成するように修正され、メモリ割り当て解除が、領域全体に対して同時に起こるようにする。内容、および領域の間の関連づけが、プログラムコードの分析から作成される１つまたは複数の形状グラフによって記述される。形状グラフによって格納される領域関連づけメタデータは、領域ベースのメモリ管理を行わせ、渡される各オブジェクトに対するメソッドに１つの領域のみが渡されることを要求する、メモリ管理方法を開示する。

他の背景技術として、特開１９９３−０１５８６７６号公報（特許文献７）は、単一、集束又はターミネータノードに接続された拡散ノードを有する木構造においてそのすべての段階でいかなるグラフも描写するデータ構造を定義しかつ記憶し、その頂部が前記データ構造に記載された構文構造である内部の表示とスクリーン上の外部グラフ表示との間の一致の表を作成し、前記データ構造において定義された要素の連続挿入及び／又は破壊演算を実施することによりグラフを有効に作成し、前記挿入及び／又は破壊が挿入又は破壊されるべき要素が配置される領域を超えて配置されるグラフ要素をシフトする連続演算によりスクリーンの所望の領域に適用され、その結果変更は再作成されるべき部分のみに関連し、前記グラフをその作成及び変更の間表示し、内部記載及び一致表を更新する方法を開示する。

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

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

アプリケーションの目的に応じたオブジェクトのすべての部分がグラフデータの準同型写像（homomorphism）の像である場合、前者に対する操作と後者に対する操作を一対一で対応させることができる。しかし、オブジェクトの一部がグラフデータからの準同型写像となっていない場合がある。そのような場合、オブジェクトに対する操作をグラフデータに反映することについて、注意を要する場合がある。

例えば、複数のオブジェクトに関連し得るノードがグラフデータ内に存在するものとする。この場合に、当該グラフデータ内のノードに関連するあるオブジェクトに対して追加・削除等の操作をすると、グラフデータにおいても当該ノードが追加・削除等されてしまう可能性がある。その結果、当該グラフデータ内のノードに関連する他のオブジェクトに関連して不適切な影響が生じる場合がある。

したがって、本発明の目的の１つは、グラフデータにオブジェクトに対する操作を効果的に反映するための方法、プログラム、および、システムを提供することである。

上記の目的を達成するために、ノードとエッジを含むグラフデータの少なくとも一部の写像の像であるオブジェクトに対して行った操作を、グラフデータに反映するための方法を提供する。方法は、操作によって変更されるオブジェクトに関連するグラフデータのノードのうち、他のオブジェクトにも関連し得るノードである共有ノードを特定するステップと、共有ノードが変更されないようにグラフデータに操作を反映するステップを含む。

好ましくは、方法は、データ構造に含まれるオブジェクトに対応するグラフ・マッチング・パターンを提供するステップをさらに含む。さらに好ましくは、変更されたオブジェクトに対応するグラフ・マッチング・パターンを特定するステップと、特定されたグラフ・マッチング・パターンに基づいて、共有ノードを特定するためのクエリを生成するステップを含む。

好ましくは、操作を反映するステップが、グラフ・マッチング・パターンに含まれるノード変数とそれにマッチするグラフデータ内のノードとの対応関係をエントリとして含むテーブルを用いて、グラフデータに操作を反映するステップを含む。

好ましくは、操作がオブジェクトの生成であり、操作を反映するステップが、ノードを新たに生成することなく、特定された共有ノードに対してリンクを形成することによって、グラフデータに操作を反映するステップを含む。好ましくは、操作がオブジェクトの生成であり、生成されたオブジェクトに対応するテーブルを新たに生成するステップをさらに含む。特定された共有ノードに対応するエントリをテーブルに追加するステップか、および／または、グラフ・マッチング・パターンに含まれる代表ノード変数に対応するエントリを新たに生成されたテーブルに追加するステップをさらに含む。また、グラフ・マッチング・パターンに含まれる代表ノード変数および共有ノード変数以外のノードに対応するエントリが生成されたテーブルに追加され、当該テーブルがすべて充填されたことを条件に、グラフデータに操作が反映されるようにすることができる。

好ましくは、操作がオブジェクトの更新であり、変更されたオブジェクトに対応するテーブルを特定するステップと、特定されたテーブルにオブジェクトに対して実行されたオブジェクトの更新を反映するステップを含む。

好ましくは、操作がオブジェクトの削除であり、操作を反映するステップが、特定された共有ノードが削除されないようにグラフデータに操作を反映するステップを含む。操作がオブジェクトの削除であり、変更されたオブジェクトに対応するテーブルを特定するステップと、テーブルに含まれる共有ノードの情報以外の情報に基づいて、共有ノードが削除されないようにグラフデータに操作を反映するステップを含むようにすることができる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. ノードとエッジを含むグラフデータの少なくとも一部の写像の像であるオブジェクトに対して行った操作を、前記グラフデータに反映するための方法であって、
   前記操作によって変更されるオブジェクトに関連するグラフデータのノードのうち、他のオブジェクトにも関連し得るノードである共有ノードを特定するステップと、
   前記共有ノードが変更されないように前記グラフデータに前記操作を反映するステップと、
   前記オブジェクトに対応するグラフ・マッチング・パターンを提供するステップと、
   前記変更されたオブジェクトに対応するグラフ・マッチング・パターンを特定するステップと、
   特定されたグラフ・マッチング・パターンに基づいて、共有ノードを特定するためのクエリを生成するステップと、
   を含む、方法。
2. 前記操作を反映するステップが、前記グラフ・マッチング・パターンに含まれるノード変数とそれにマッチするグラフデータ内のノードとの対応関係をエントリとして含むテーブルを用いて、前記グラフデータに前記操作を反映するステップを含む、請求項１に記載の方法。
3. 前記操作がオブジェクトの生成であり、生成されたオブジェクトに対応する前記テーブルを新たに生成するステップをさらに含む、請求項２に記載の方法。
4. 特定された前記共有ノードに対応するエントリを前記テーブルに追加するステップを含む、請求項３に記載の方法。
5. 前記グラフ・マッチング・パターンに含まれる代表ノード変数に対応するエントリを前記新たに生成されたテーブルに追加するステップをさらに含む、請求項３に記載の方法。
6. 前記グラフ・マッチング・パターンに含まれる代表ノード変数および共有ノード変数以外のノードに対応するエントリが前記生成されたテーブルに追加され、当該テーブルがすべて充填されたことを条件に、前記グラフデータに前記操作が反映される、請求項３に記載の方法。
7. 前記操作がオブジェクトの更新であり、前記変更されたオブジェクトに対応する前記テーブルを特定するステップと、特定された前記テーブルにオブジェクトに対して前記実行されたオブジェクトの更新を反映するステップと、を含む、請求項２に記載の方法。
8. 前記操作がオブジェクトの削除であり、前記操作を反映するステップが、前記特定された共有ノードが削除されないように前記グラフデータに前記操作を反映するステップを含む、請求項２に記載の方法。
9. 前記操作がオブジェクトの削除であり、前記変更されたオブジェクトに対応する前記テーブルを特定するステップと、前記テーブルに含まれる前記共有ノードの情報以外の情報に基づいて、共有ノードが削除されないように前記グラフデータに前記操作を反映するステップと、を含む、請求項２に記載の方法。
10. 請求項１ないし９のいずれかに記載の方法のすべてのステップをコンピュータに実行させることができる、プログラム。
11. ノードとエッジを含むグラフデータの少なくとも一部の写像の像であるオブジェクトに対して行った操作を、前記グラフデータに反映するためのプログラムであって、
    前記操作によって変更されるオブジェクトに関連するグラフデータのノードのうち、他のオブジェクトにも関連し得るノードである共有ノードを特定するステップと、
    前記共有ノードが変更されないように前記グラフデータに前記操作を反映するステップと、
    前記オブジェクトに対応するグラフ・マッチング・パターンを提供するステップと、
    前記変更されたオブジェクトに対応するグラフ・マッチング・パターンを特定するステップと、
    特定されたグラフ・マッチング・パターンに基づいて、共有ノードを特定するためのクエリを生成するステップと、
    をコンピュータに実行させる、プログラム。
12. ノードとエッジを含むグラフデータの少なくとも一部の写像の像であるオブジェクトに対して行った操作を、前記グラフデータに反映するための装置であって、
    前記グラフデータを記憶するグラフ・リポジトリにアクセスする手段と、
    前記操作によって変更されるオブジェクトに関連するグラフデータのノードのうち、他のオブジェクトにも関連し得るノードである共有ノードを特定する手段と、
    前記共有ノードが変更されないように前記グラフデータに前記操作を反映させる手段と、
    前記オブジェクトに対応するグラフ・マッチング・パターンを提供する手段と、
    前記変更されたオブジェクトに対応するグラフ・マッチング・パターンを特定する手段と、
    特定されたグラフ・マッチング・パターンに基づいて、共有ノードを特定するためのクエリを生成する手段と、
    を備える、装置。
    
    
    

Images