(57)【要約】  元のグラフデータに新たな単位データが追加された場合、計算機システムは、縮約グラフデータのメタ情報から、新たな単位データ内の第１ノード値に対応した縮約値である第１の縮約値と、新たな単位データ内の第２ノード値に対応した縮約値である第２の縮約値とを特定し、第１の縮約値と、第２の縮約値と、第１の縮約値から第２の縮約値へのエッジ（新たな単位データ内のエッジと同じエッジ）との組合せである新たな単位縮約データを、縮約グラフデータに追加する。
2015125230.tif 000002
【特許請求の範囲】
【請求項１】
元のグラフデータが縮約されたデータである縮約グラフデータを用いて前記元のグラフデータからデータを検索するシステムにおいて使用されるデータ更新方法であって、
前記元のグラフデータは、複数の単位データの集合であり、
各単位データは、第１ノード値、第２ノード値と、前記第１ノード値から前記第２ノード値へのエッジとの組合せであり、
前記縮約グラフデータは、複数の単位縮約データの集合であり、
各単位縮約データは、第１ノード値の縮約値と、第２ノード値の縮約値と、前記第１ノード値の縮約値から前記第２ノード値の縮約値へのエッジとの組合せであり、
前記データ更新方法は、
前記元のグラフデータに新たな単位データが追加された場合、前記縮約グラフデータのメタ情報から、前記新たな単位データ内の第１ノード値に対応した縮約値である第１の縮約値と、前記新たな単位データ内の第２ノード値に対応した縮約値である第２の縮約値とを特定し、
前記第１の縮約値と、前記第２の縮約値と、前記第１の縮約値から前記第２の縮約値へのエッジであって前記新たな単位データ内のエッジと同じエッジとの組合せである新たな単位縮約データを、前記縮約グラフデータに追加する、
データ更新方法。
【請求項２】
前記メタ情報は、第１及び第２のサブメタ情報を含み、
前記第１のサブメタ情報は、前記元のグラフデータにおけるエッジ毎に縮約値と前記元のグラフデータにおける末端ノード値の範囲との関係を表す情報であり、
前記第２のサブメタ情報は、前記元のグラフデータに含まれる複数の非末端ノード値にそれぞれ対応した複数の縮約値を表す情報である、
請求項１記載のデータ更新方法。
【請求項３】
前記新たな単位データ内の第２ノード値が末端ノード値であり、前記新たな単位データ内のエッジの種類が前記第１のサブメタ情報に登録されていない場合、前記新たな単位データ内のエッジと、新たな縮約値と、前記新たな単位データ内の第２ノード値に従い決定された値範囲との第１の組合せを、前記第１のサブメタ情報に追加し、
前記第２の縮約値は、前記第１の組合せを含んだ前記第１のサブメタ情報から特定される、
請求項２記載のデータ更新方法。
【請求項４】
前記新たな単位データ内の第２ノード値が非末端ノード値であり、前記新たな単位データ内の第１ノード値及び第２ノード値の少なくとも一方が前記第２のサブメタ情報に登録されていない場合、前記新たな単位データ内の第１ノード値及び第２ノード値の少なくとも一方であり前記第２のサブメタ情報に登録されていない値と、新たな縮約値との第２の組合せを、前記第２のサブメタ情報に追加し、
前記第１の縮約値は、前記第２の組合せを含んだ前記第２のサブメタ情報から特定される、
請求項２記載のデータ更新方法。
【請求項５】
前記元のグラフデータから単位データが削除されても、前記縮約グラフデータを更新しない、
請求項１記載のデータ更新方法。
【請求項６】
検索性能が劣化したとみなされる所定の条件の入力を受け付け、
前記所定の条件が満たされた場合に、前記元のグラフデータを縮約することにより新たに縮約グラフデータを生成する、
請求項１記載のデータ更新方法。
【請求項７】
前記所定の条件が満たされたとは、（ａ）直前回に新たに縮約グラフデータを生成してから所定時間が経過した、（ｂ）現時点が所定時刻になった、（ｃ）現時点の元のグラフデータのサイズが過去の或る時点の元のグラフデータのサイズに比べて所定倍率以上になった、（ｄ）前記元のグラフデータからデータを検索する性能が所定値以下に低下した、（ｅ）複数の末端ノード値範囲にそれぞれ属する複数の末端ノード数の偏りが所定偏り以上になった、のうちの少なくとも１つである、
請求項６記載のデータ更新方法。
【請求項８】
元のグラフデータが縮約されたデータである縮約グラフデータのメタ情報を記憶する記憶資源と、
前記記憶資源に接続されており前記縮約グラフデータを用いて前記元のグラフデータからデータを検索するプロセッサと
を有し、
前記元のグラフデータは、複数の単位データの集合であり、
各単位データは、第１ノード値、第２ノード値と、前記第１ノード値から前記第２ノード値へのエッジとの組合せであり、
前記縮約グラフデータは、複数の単位縮約データの集合であり、
各単位縮約データは、第１ノード値の縮約値と、第２ノード値の縮約値と、前記第１ノード値の縮約値から前記第２ノード値の縮約値へのエッジとの組合せであり、
前記元のグラフデータに新たな単位データが追加された場合、前記プロセッサは、
前記新たな単位データ内の第１ノード値に対応した縮約値である第１の縮約値と、前記新たな単位データ内の第２ノード値に対応した縮約値である第２の縮約値とを前記メタ情報から特定し、
前記第１の縮約値と、前記第２の縮約値と、前記第１の縮約値から前記第２の縮約値へのエッジであって前記新たな単位データ内のエッジと同じエッジとの組合せである新たな単位縮約データを、前記縮約グラフデータに追加する、
計算機システム。
【請求項９】
前記メタ情報は、第１及び第２のサブメタ情報を含み、
前記第１のサブメタ情報は、前記元のグラフデータにおけるエッジ毎に縮約値と前記元のグラフデータにおける末端ノード値の範囲との関係を表す情報であり、
前記第２のサブメタ情報は、前記元のグラフデータに含まれる複数の非末端ノード値にそれぞれ対応した複数の縮約値を表す情報である、
請求項８記載の計算機システム。
【請求項１０】
前記新たな単位データ内の第２ノード値が末端ノード値であり、前記新たな単位データ内のエッジの種類が前記第１のサブメタ情報に登録されていない場合、前記プロセッサは、前記新たな単位データ内のエッジと、新たな縮約値と、前記新たな単位データ内の第２ノード値に従い決定された値範囲との第１の組合せを、前記第１のサブメタ情報に追加し、
前記第２の縮約値は、前記第１の組合せを含んだ前記第１のサブメタ情報から特定される、
請求項９記載の計算機システム。
【請求項１１】
前記新たな単位データ内の第２ノード値が非末端ノード値であり、前記新たな単位データ内の第１ノード値及び第２ノード値の少なくとも一方が前記第２のサブメタ情報に登録されていない場合、前記プロセッサは、前記新たな単位データ内の第１ノード値及び第２ノード値の少なくとも一方であり前記第２のサブメタ情報に登録されていない値と、新たな縮約値との第２の組合せを、前記第２のサブメタ情報に追加し、
前記第１の縮約値は、前記第２の組合せを含んだ前記第２のサブメタ情報から特定される、
請求項９記載の計算機システム。
【請求項１２】
前記元のグラフデータから単位データが削除されても、前記プロセッサは、前記縮約グラフデータを更新しない、
請求項８記載の計算機システム。
【請求項１３】
前記プロセッサは、
検索性能が劣化したとみなされる所定の条件の入力を受け付け、
前記所定の条件が満たされた場合に、前記元のグラフデータを縮約することにより新たに縮約グラフデータを生成する、
請求項８記載の計算機システム。
【請求項１４】
前記所定の条件が満たされたとは、（ａ）直前回に新たに縮約グラフデータを生成してから所定時間が経過した、（ｂ）現時点が所定時刻になった、（ｃ）現時点の元のグラフデータのサイズが過去の或る時点の元のグラフデータのサイズに比べて所定倍率以上になった、（ｄ）前記元のグラフデータからデータを検索する性能が所定値以下に低下した、（ｅ）複数の末端ノード値範囲にそれぞれ属する複数の末端ノード数の偏りが所定偏り以上になった、のうちの少なくとも１つである、
請求項１３記載の計算機システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、グラフデータの更新に関する。
【背景技術】
【０００２】
グラフデータは、例えば、データベースの少なくとも一部分に使用され、検索の範囲とされる。グラフデータとして、例えば、ＲＤＦデータ（ＲＤＦ（Resource  Description  Framework）と呼ばれる形式のデータ）が知られている。ＲＤＦデータの縮約に関し、特許文献１に開示の技術が知られている。特許文献１によれば、元のＲＤＦデータが縮約された縮約ＲＤＦデータが生成される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第2013/111287号パンフレット
【発明の概要】
【発明が解決しようとする課題】
【０００４】
元のＲＤＦデータにデータが追加された場合、縮約ＲＤＦデータを通じてＲＤＦデータから追加されたデータを取得できるようにするためには、データ追加後の元ＲＤＦデータから新たに縮約ＲＤＦデータを作成することになる。【０００５】
しかし、ＲＤＦデータのようなグラフデータの縮約には、そのグラフデータのサイズに準じた時間がかかる。
【課題を解決するための手段】
【０００６】
元のグラフデータは、複数の単位データの集合であり、各単位データは、第１ノード値、第２ノード値と、第１ノード値から第２ノード値へのエッジとの組合せである。縮約グラフデータは、複数の単位縮約データの集合であり、各単位縮約データは、第１ノード値の縮約値と、第２ノード値の縮約値と、第１ノード値の縮約値から第２ノード値の縮約値へのエッジとの組合せである。元のグラフデータに新たな単位データが追加された場合、計算機システムは、縮約グラフデータのメタ情報から、新たな単位データ内の第１ノード値に対応した縮約値である第１の縮約値と、新たな単位データ内の第２ノード値に対応した縮約値である第２の縮約値とを特定し、第１の縮約値と、第２の縮約値と、第１の縮約値から第２の縮約値へのエッジ（新たな単位データ内のエッジと同じエッジ）との組合せである新たな単位縮約データを、縮約グラフデータに追加する。
【発明の効果】
【０００７】
元のグラフデータに新たなデータが追加されてもデータ追加後の元グラフデータから新たに縮約グラフデータを作成することなく、データ追加後のＲＤＦデータから追加されたデータを縮約ＲＤＦデータを通じて検索できる。
【図面の簡単な説明】
【０００８】
【図１】実施形態に係る計算機システムの構成を示す。
【図２】元ＲＤＦデータ１１５の表形式の構造を示す。
【図３】単位ＲＤＦデータの構成を示す。
【図４】図２の元ＲＤＦデータ１１５が表す木構造を示す。
【図５】元ＲＤＦデータ１１５に対する単位ＲＤＦデータの追加例を示す。
【図６】元ＲＤＦデータ１１５を基に縮約基準表１０１を作成する流れの概要を示す。
【図７】縮約基準表１０１を用いて縮約ＲＤＦデータ１１６を作成する流れの概要を示す。
【図８】縮約ＲＤＦデータ１１６の表形式の構造を示す。
【図９】縮約ＲＤＦデータ１１６を用いた検索処理の一例を示す。
【図１０】差分更新処理のフローチャートである。
【図１１】縮約ＲＤＦ更新処理（図１０のステップ１００４）のフローチャートである。
【図１２】縮約値決定処理（図１１のステップ１１０２）のフローチャートである。
【図１３】図１２のステップ１２０３の結果の一例を示す。
【図１４】図１２のステップ１２１３の結果の一例を示す。
【図１５】図１１のステップ１１０３の結果の一例を示す。
【図１６】データ整理処理のフローチャートである。
【図１７】縮約条件設定画面の一例を示す。
【発明を実施するための形態】
【０００９】
以下、グラフデータとしてＲＤＦデータが採用された一実施形態を説明する。
【００１０】
なお、以下の説明では、「ｋｋｋ表」の表現にて情報を説明することがあるが、情報は、表以外のデータ構造で表現されていてもよい。データ構造に依存しないことを示すために「ｋｋｋ表」を「ｋｋｋ情報」と呼ぶことができる。
【００１１】
また、以下の説明では、「プログラム」を主語として処理を説明する場合があるが、プログラムは、プロセッサによって実行されることで、定められた処理を、適宜に記憶資源（例えば、メモリ）及び／又は通信インターフェイスデバイス（例えば、通信ポート）を用いながら行うため、処理の主語がプロセッサとされてもよい。逆に、プロセッサが主語となっている処理は、１以上のプログラムを実行することにより行われると解釈することができる。
【００１２】
図１は、実施形態に係る計算機システムの構成を示す。
【００１３】
計算機システム１００は、１以上の計算機を含んだシステムである。１以上の計算機は、少なくとも１つの物理計算機を含み、１以上の仮想計算機を含んでよい。計算機システム１００は、入力デバイス１１１、出力デバイス１１２、通信インターフェイスデバイス（Ｉ／Ｆ）１１３、記憶資源１０３及びそれらに接続されたプロセッサ１１０を有する。入力デバイス１１１及び出力デバイス１１２のうちの少なくとも１つは、計算機システム１００に接続された遠隔の表示用計算機（図示せず）に存在してもよい。
【００１４】
入力デバイス１１１は、１以上の入力デバイスであり、例えば、キーボード及びポインティングデバイスでよい。出力デバイス１１２は、表示デバイスを含む１以上の出力デバイスであり、例えば、液晶ディスプレイでよい。入力デバイス１１１及び出力デバイス１１２は、タッチパネルのように一体であってもよい。
【００１５】
Ｉ／Ｆ１１３は、１以上の通信インターフェイスデバイスであり、例えば、ＬＡＮ（Local  Area  Network）コントローラ及びＨＢＡ（Host  Bus  Adapter）のうちの少なくとも１つでよい。Ｉ／Ｆ１１３に、外部ストレージ装置１１４が接続される。外部ストレージ装置１１４は、ＳＳＤ（Solid  State  Drive）又はＨＤＤ（Hard  Disk  Drive）のような記憶デバイスであってもよいし、複数の記憶デバイスで構成された１以上のＲＡＩＤ（Redundant  Arrays  of  Inexpensive  （or  Independent）  Disks）グループを有するストレージ装置であってもよい。外部ストレージ装置１１４が、元ＲＤＦデータ１１５と、元ＲＤＦデータ１１５を縮約した結果である縮約ＲＤＦデータ１１６とを記憶する。本実施形態において、縮約ＲＤＦデータの元のデータと言う意味で、ＲＤＦデータを「元ＲＤＦデータ」と称する。元ＲＤＦデータ１１５及び縮約ＲＤＦデータ１１６は、例えばデータベース中のデータでよい。外部ストレージ装置１１４が無く、インメモリデータベースのように、元ＲＤＦデータ１１５及び縮約ＲＤＦデータ１１６が記憶資源１０３に格納されてもよい。
【００１６】
記憶資源１０３は、揮発性又は不揮発性メモリを含む１以上の記憶デバイスである。記憶資源１０３は、元ＲＤＦデータ１１５の縮約の際に作成された縮約基準表１０１及び縮約表１０２を記憶する。縮約基準表１０１及び縮約表１０２は、縮約ＲＤＦデータ１１６のメタ情報の一例である。また、記憶資源１０３は、初めて縮約ＲＤＦデータ１１６を作成する初期縮約プログラム１０４、入力された元クエリを縮約クエリに変換し縮約クエリを処理するクエリ処理プログラム１０５、縮約ＲＤＦデータ１１６を更新する差分更新プログラム１０６、及び、所定の条件に適合した場合にも元ＲＤＦデータ１１５を基に新たに縮約ＲＤＦデータを作成するデータ整理プログラム１０７を記憶する。これらのプログラム１０４〜１０７は、プロセッサ１１０により実行される。例えば、差分更新プログラム１０６は、後述する縮約ＲＤＦ更新処理及び縮約値決定処理を行うことができる。
【００１７】
プロセッサ１１０は、１以上のプロセッサである。プロセッサは、ＣＰＵ（Central  Processing  Unit）のようなマイクロプロセッサであってもよいし、ＣＰＵコアのようなプロセッサコアであってもよいし、それらのうちの少なくとも１つに加えて一部の処理（例えば、暗号化／復号化、又は、圧縮／伸張）を実行するハードウェア回路を含んでもよい。
【００１８】
図２は、元ＲＤＦデータ１１５の表形式の構造を示す。
【００１９】
図２に示すように、元ＲＤＦデータ１１５は、表形式であり、複数の単位ＲＤＦデータにそれぞれ対応した複数のレコードで構成される。各レコードは、そのレコードに対応した単位ＲＤＦデータが有する主語、述語及び目的語のそれぞれの値を有する。なお、この元ＲＤＦデータ１１５は、Ａ、Ｂ、Ｃ、ＤおよびＥの５つの国のランク（rank）、度数（degree）、名前（name）及び友好関係（friend）を表している。
【００２０】
図３に示すように、単位ＲＤＦデータは、「主語」、「述語」及び「目的語」と呼ばれる３つの要素（値）で構成されている。グラフデータの単位データは、第１ノード値、第２ノード値と、第１ノード値から第２ノード値へのエッジとの組合せであるが、単位ＲＤＦデータでは、主語が、第１ノード値の一例であり、述語が、エッジの一例であり、目的語が、第２ノード値の一例である。単位ＲＤＦデータは、「トリプル」と呼ばれることもある。
【００２１】
図３のような単位ＲＤＦデータの組合せによって、図４に示すような木構造の元ＲＤＦデータ１１５が構築される。言い換えれば、図２の表が、図４の木構造を表す。グラフデータは、一般に、複数のノードと複数のエッジの集合であるが、元ＲＤＦデータ１１５も同様の構成である。元ＲＤＦデータ１１５において、主語及び目的語の両方になれるノード（非末端ノードの一例）が「リソース」と呼ばれ、目的語のみになれるノード（末端ノードの一例）が「リテラル」と呼ばれることがある。
【００２２】
元ＲＤＦデータ１１５に対して、図５に示すように、単位ＲＤＦデータが追加されることがある。具体的には、図２の元ＲＤＦデータ１１５に、追加される単位ＲＤＦデータに対応したレコードが追加されることがある。このように、元ＲＤＦデータ１１５に対する単位ＲＤＦデータの追加は容易である。
【００２３】
しかし、追加された単位ＲＤＦデータを元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を用いて取得できるようにするためには、従来技術によれば、単位ＲＤＦデータ追加後の元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を新たに作成しなければならない。
【００２４】
本実施形態では、単位ＲＤＦデータが追加の元ＲＤＦデータ１１５に追加された場合、必要に応じて縮約基準表１０１及び縮約表１０２が更新され、縮約基準表１０１及び縮約表１０２から、追加された単位ＲＤＦデータにおける主語及び目的語の縮約値がそれぞれ取得される。そして、取得された２つの縮約値とそれらを繋ぐ述語（追加された単位ＲＤＦデータ内の述語と同じ述語）とを含んだ単位縮約ＲＤＦデータが、縮約ＲＤＦデータ１１５に追加される。これにより、単位ＲＤＦデータ追加後の元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を新たに作成することなく、追加された単位ＲＤＦデータを元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を用いて取得できる。なお、本実施形態において、「縮約値」とは、一意な何らかの値でよい。
【００２５】
以下、本実施形態をより詳細に説明する。
【００２６】
まず、図６及び図７を参照して、縮約ＲＤＦデータ１１６の作成の流れの概要を説明する。図６は、元ＲＤＦデータ１１５を基に縮約基準表１０１を作成する流れの概要を示し、図７は、縮約基準表１０１を用いて縮約ＲＤＦデータ１１６を作成する流れの概要を示す。
【００２７】
図６に示すように、初期縮約プログラム１０４は、同じ述語を持つ複数のリソースを元ＲＤＦデータ１１５から選び出すことで、複数の同一構造のＲＤＦデータ部を作成する。各ＲＤＦデータ部は、リソース（主語）と、そのリソースから延びた２つの述語（rank、degree）と、２つの述語にそれぞれ接続された目的語とを有する。初期縮約プログラム１０４は、複数のＲＤＦデータ部から目的語の値集合を取り出し、各グループ（目的語の値範囲）に所属する値集合（目的語の数）が例えば均等になるように、値集合を分割する。値集合は、アクセス頻度に基づいて分割される等、他の規則に従い分割されてもよい。初期縮約プログラム１０４は、分割した際の閾値（値集合の最大値及び最小値）から、縮約基準表１０１の縮約範囲（目的語の値範囲）を作成する。例えば、値が文字列でも、辞書順や文字コード順のような所定の規則に従って並べることで、最大値と最小値を決定することができる。初期縮約プログラム１０４は、各縮約範囲に、一意に対応する縮約値を生成して関連付け、述語を、基準述語として関連付けて管理する。このようにして作成された縮約基準表１０１は、複数のリテラルを縮約値に対応づけるために定めた基準を表す。図６に示す縮約基準表１０１によれば、基準述語「rank」について、値が２未満の目的語は、縮約値「c1」に変換され、値が２以上の目的語は、縮約値「c2」に変換されることになる。
【００２８】
次に、図７に示すように、初期縮約プログラム１０４は、複数の同一構造のＲＤＦデータ部の各々のリテラル（目的語）を、縮約基準表１０１（図６参照）を用いて縮約値に変換する。そして、初期縮約プログラム１０４は、同じ縮約値を含んだ２以上のＲＤＦデータ部のリソースを集約することで、リソース集合を作成する。初期縮約プログラム１０４は、各リソース集合に、一意に対応する縮約値を生成して関連付け、その対応関係を縮約表１０２に登録する。つまり、初期縮約プログラム１０４は、元ＲＤＦデータ１１５におけるすべてのリテラルについて、縮約基準表１０１に基づいて縮約値を求め、元のリソースと縮約値との対応関係を表す縮約表１０２を作成する。主語となるリソースが複数存在し、各リソースが、同じ縮約した目的語（リテラルの縮約値）に接続されていれば、同じ縮約値に接続されるリソースは、同じ縮約値となり、その対応関係が縮約表で管理される。縮約表１０２は、元ＲＤＦデータ１１５に含まれる複数のリソースをそれぞれひとつの縮約値に対応付ける情報である。初期縮約プログラム１０４は、縮約表１０２を基に、各リソースの値を縮約値に変換する。このようなリソース変換（リソースの値を縮約値に変換すること）及びリテラル変換（リテラルの値を縮約値に変換すること）を元ＲＤＦデータ１１５に対して実行した結果として、縮約ＲＤＦデータ１１６が作成される。なお、リソースの縮約値を用い、その縮約値を述語とするリソース集合を求めることで、再び縮約値を決定することができる。この操作を繰り返すことで、元ＲＤＦデータ１１５の全てのノードをそれぞれ縮約値に変換することができる。図８は、作成された縮約ＲＤＦデータ１１６の表形式の構造を示す。なお、図８において、リテラル（目的語）の値が、文字列の場合、数値と異なり、降順や昇順などの順番を付けられない。また、文字列間の距離も定義できないため、値範囲を設定することもできない。そのため、リテラルの値が文字列の場合、縮約ＲＤＦデータ１１６において、そのリテラルの値は無効な値（例えば「other」）とされ、そのリテラルについては、縮約の対象外とされる。ただし、文字列を文字コードやその他のルールによって数値に変換することで、文字列が値のリテラルについても縮約がされてもよい。
【００２９】
計算機システム１００は、縮約ＲＤＦデータ１１６を用いて、元ＲＤＦデータ１１５からデータを検索することができる。
【００３０】
例えば、計算機システム１００は、図９に示すクエリ（以下、元クエリ）９０１を、クエリ発行元から受けたとする。クエリ発行元は、計算機システム１００において実行されるアプリケーションプログラム（図示せず）であってもよいし、計算機システム１００の外部の計算機（図示せず）であってもよい。また、前述したプログラム１０４〜１０７は、データベース管理システムに含まれていてもよい。元クエリ９０１は、述語「rank」の目的語の値が４以上、且つ、述語「degree」の目的語の値が１であるリソースを探す要求である。
【００３１】
まず、クエリ処理プログラム１０５が、元クエリ９０１を縮約クエリ９０２に変換する。縮約クエリ９０２は、元クエリ９０１における条件値が縮約値に変換されたクエリである。
【００３２】
具体的には、例えば、クエリ処理プログラム１０５は、述語「rank」及び「degree」にそれぞれ繋がるリテラルを、縮約基準表１０１を用いて縮約値に変換する。この結果、「rank」についての「4以上」は、縮約値「c2」に変換され、「degree」についての「1」は、縮約値「c3」に変換される。また、クエリ処理プログラム１０５は、リソースに値あれば、そのリソースの値を、縮約表１０２を用いて変換する。ここまでの変換により、縮約クエリ９０２が生成される。
【００３３】
クエリ処理プログラム１０５は、この縮約クエリ９０２と、縮約ＲＤＦデータ１１６のパターンマッチを実行する。その結果、リソース「c6」、リテラル「c2」及び「c3」の縮約ＲＤＦデータ部を発見できる。その後、クエリ処理プログラム１０５は、縮約表１０２及び元クエリ９０１を用いて、縮約値を元の値に戻す。これにより、縮約値「c6」はリソース「B」又は「D」に戻され、縮約値「c2」は「4以上」に戻され、縮約値「c3」は「1」に戻される。クエリ処理プログラム１０５は、その情報（リソースの値に「B」又は「D」が代入された元クエリ９０１）を用いて、元ＲＤＦ１１５を検索する。つまり、クエリ処理プログラム１０５は、リソースが「B」で「rank」について「4以上」且つ「degree」について「1」に該当するデータ、及び、リソースが「D」で「rank」について「4以上」且つ「degree」について「1」に該当するデータを、元ＲＤＦデータ１１５から探索する。結果、リソースが「B」で「rank」について「7」且つ「degree」が「1」のデータが見つかる。
【００３４】
このように、縮約ＲＤＦデータ１１６を利用することで、大量にあるリソース候補を「B」と「D」に絞り込むことができる。この絞り込みにより、「B」と「D」以外のリソースを探索する必要がなく、検索時間を短縮することができる。
【００３５】
本実施形態では、このような計算機システム１００において、縮約ＲＤＦデータ１１６の更新、及び、そのメタ情報（縮約基準表１０１及び縮約表１０２）の更新が可能である。以下、それについて詳細に説明する。
【００３６】
図１０は、差分更新処理のフローチャートである。
【００３７】
差分更新プログラム１０６は、元ＲＤＦデータ１１５に対する差分を入力として取得する（ステップ１００１）。差分は、元ＲＤＦデータ１１５に対する単位ＲＤＦデータの追加、又は、元ＲＤＦデータ１１５からの単位ＲＤＦデータの削除である。なお、或る単位ＲＤＦデータにおける値が別の値に更新される場合は、その或る単位ＲＤＦデータの削除と、更新後の値を含んだ単位ＲＤＦデータの追加の両方が行われる。
【００３８】
差分更新プログラム１０６は、データベースをロックする（ステップ１００２）。データベースのロックとは、例えば、クエリ処理プログラム１０５が元クエリを処理しない状態でよい。データベースがロックされることにより、更新後のデータベースにおけるデータがクエリ発行元に返されないといったエラーが生じることを回避できる。
【００３９】
その後、差分更新プログラム１０６は、ステップ１００１で入力された差分に従い、元ＲＤＦデータ１１５を更新する（ステップ１００３）。例えば、差分が、単位ＲＤＦデータの追加であれば、差分更新プログラム１０６は、追加対象の単位ＲＤＦデータに対応したレコードを元ＲＤＦデータ１１５に追加する。また、例えば、差分が、単位ＲＤＦデータの削除であれば、差分更新プログラム１０６は、削除対象の単位ＲＤＦデータに対応したレコードを元ＲＤＦデータ１１５から削除する。
【００４０】
差分更新プログラム１０６は、縮約ＲＤＦ更新処理を行う（ステップ１００４）。
【００４１】
その後、差分更新プログラム１０６は、データベースをアンロックする（ステップ１００５）。以後、クエリ処理プログラム１０５が元クエリを処理できる。
【００４２】
なお、データベースのロック／アンロックの代替例として、次の代替例１及び２が考えられる。代替例１では、差分更新プログラム１０６は、元ＲＤＦデータ１１５及び縮約ＲＤＦデータ１１６のそれぞれについてスナップショットをとり、差分更新処理中に元クエリを処理する場合には、元ＲＤＦデータ１１５及び縮約ＲＤＦデータ１１６のそれぞれのスナップショットを参照してよい。代替例２では、差分更新プログラム１０６は、ステップ１００１で入力された差分について縮約ＲＤＦ更新処理（ステップ１００４）が終わるまでは、参照について、縮約技術を利用しないで元ＲＤＦデータ１１５に対してフォールバックを行ってよい。
【００４３】
図１１は、縮約ＲＤＦ更新処理（図１０のステップ１００４）のフローチャートである。
【００４４】
差分更新プログラム１０６は、差分（図１０のステップ１１０１での入力）が削除であるかどうかを判断する（ステップ１１０１）。
【００４５】
差分が追加の場合（ステップ１１０１：Ｎｏ）、差分更新プログラム１０６は、縮約値決定処理を行う（ステップ１１０２）。これにより、追加された単位ＲＤＦデータ内の主語及び目的語のそれぞれが、縮約値に変換され、また、必要に応じて、縮約基準表１０１又は縮約表１０２が更新される。そして、差分更新プログラム１０６は、主語の縮約値である第１の縮約値から、目的語の縮約値である第２の縮約値へと、追加された単位ＲＤＦデータ内の述語と同じ述語で繋ぎ、第１の縮約値と、第２の縮約値と、それらを繋ぐ述語との組合せである単位縮約ＲＤＦデータに対応したレコードを、縮約ＲＤＦデータ１１６に追加する（ステップ１１０３）。これにより、縮約ＲＤＦ更新処理が終了する。
【００４６】
差分が削除の場合（ステップ１１０１：Ｙｅｓ）、差分更新プログラム１０６は、ステップ１１０２及び１１０３を実行することなく、縮約ＲＤＦ更新処理を終了する。つまり、差分が削除の場合、縮約ＲＤＦデータ１１６もそのメタ情報も更新されない。言い換えれば、縮約ＲＤＦデータ１１６は、元ＲＤＦデータ１１５における接続関係を不足なく含んでいれさえすればよい。縮約ＲＤＦデータ１１６から、元ＲＤＦデータ１１５に無いノードの縮約値が特定され、その縮約値が使用されても、元ＲＤＦデータ１１５から該当するデータが見つからないだけで、クエリ発行元に対して不具合を生じさせることはない。このような観点から、差分が削除の場合、ステップ１１０２及び１１０３がスキップされるので、縮約ＲＤＦ更新処理が短時間で終了する。
【００４７】
なお、単位ＲＤＦデータにおける値の更新の場合、差分は、前述したように、削除と追加の両方である。この場合、差分が削除の場合の処理は非実行とされ、差分が追加の場合の処理のみが実行されてよい。
【００４８】
図１２は、縮約値決定処理（図１１のステップ１１０２）のフローチャートである。この処理は、追加された単位ＲＤＦデータの主語と目的語の各々について行われる。従って、１つの単位ＲＤＦデータにつき、図１２の処理は２回行われる。
【００４９】
差分更新プログラム１０６は、追加された単位ＲＤＦデータ内の目的語がリテラルかどうかを判断する（ステップ１２０１）。
【００５０】
目的語がリテラルの場合（ステップ１２０１：Ｙｅｓ）、差分更新プログラム１０６は、縮約基準表１０１を基に、追加された単位ＲＤＦデータ内の述語について縮約済かどうかを判断する（ステップ１２０２）。追加された単位ＲＤＦデータ内の述語と同じ基準述語が縮約基準表１０１に登録されていれば、ステップ１２０２の判断結果は真（縮約済）である。
【００５１】
ステップ１２０２の判断結果が偽の場合（ステップ１２０２：Ｎｏ）、差分更新プログラム１０６は、追加された単位ＲＤＦデータ内の述語を基準述語としたレコードを、縮約基準表１０１に追加する（ステップ１２０３）。追加されたレコードには、その述語に対して差分更新プログラム１０６により割り振られた縮約値と、追加された単位ＲＤＦデータ内の目的語（値）を閾値とした縮約範囲とが登録される。図１３が、ステップ１２０３の結果の一例、すなわち、縮約基準表１０１に追加されたレコード（破線枠内のレコード）の一例を示す。この例は、図５に例示した追加（破線枠内の単位ＲＤＦデータ）に対応する。ステップ１２０３の後、差分更新プログラム１０６は、縮約基準表１０１から、追加された単位ＲＤＦデータ内の目的語に対応した縮約値を決定する（ステップ１２０４）。つまり、差分更新プログラム１０６は、追加された単位ＲＤＦデータ内の主語及び目的語をそれぞれ縮約値に変換する。
【００５２】
ステップ１２０２の判断結果が真の場合（ステップ１２０２：Ｙｅｓ）、差分更新プログラム１０６は、ステップ１２０３を行うことなく、追加された単位ＲＤＦデータ内の主語及び目的語のそれぞれについて縮約値を決定する（ステップ１２０４）。
【００５３】
目的語がリテラルでない場合（ステップ１２０１：Ｎｏ）、差分更新プログラム１０６は、縮約表１０２を基に、追加された単位ＲＤＦデータ内の主語又は目的語が新しいリソースかどうかを判断する（ステップ１２１２）。追加された単位ＲＤＦデータ内の主語（値）又は目的語（値）がリソースとして縮約表１０２に登録されていなければ、ステップ１２１２の判断結果は真（新リソース）である。
【００５４】
ステップ１２１２の判断結果が真の場合（ステップ１２１２：Ｙｅｓ）、差分更新プログラム１０６は、追加された単位ＲＤＦデータ内の主語又は目的語を新リソースとしたレコードを、縮約表１０２に追加する（ステップ１２１３）。追加されたレコードには、その新リソースに対して差分更新プログラム１０６により割り振られた縮約値が登録される。図１４が、ステップ１２１３の結果の一例、すなわち、縮約表１０２に追加されたレコード（破線枠内のレコード）の一例を示す。この例は、図５に例示した追加（破線枠内の単位ＲＤＦデータ）に対応する。なお、追加された単位ＲＤＦデータ内の主語及び目的語の両方が新リソースに該当する場合、縮約表１０２には主語及び目的語にそれぞれ対応した２つのレコードが追加される。ステップ１２１３の後、差分更新プログラム１０６は、縮約表１０２から、追加された単位ＲＤＦデータ内の主語又は目的語に対応した縮約値を決定する（ステップ１２１４）。つまり、差分更新プログラム１０６は、追加された単位ＲＤＦデータ内の主語及び目的語をそれぞれ縮約値に変換する。
【００５５】
ステップ１２１２の判断結果が偽の場合（ステップ１２１２：Ｎｏ）、差分更新プログラム１０６は、ステップ１２１３を行うことなく、追加された単位ＲＤＦデータ内の主語又は目的語のそれぞれについて縮約値を決定する（ステップ１２１４）。
【００５６】
ステップ１２０４又は１２１４により、縮約値決定処理（図１１のステップ１１０２）が終了する。その後、図１１のステップ１１０３が行われる。図１５が、ステップ１１０３の結果の一例、すなわち、縮約ＲＤＦデータ１１６に追加されたレコード（破線枠内のレコード）の一例を示す。この例は、図５、図１３及び図１４に例示した追加（破線枠内の単位ＲＤＦデータ）に対応する。
【００５７】
以上のようにして、縮約ＲＤＦデータ１１６の更新、及び、そのメタ情報（縮約基準表１０１及び縮約表１０２）の更新が行われる。これにより、元ＲＤＦデータ１１５が更新されても、更新後の元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を新たに作成することなく、更新後の元ＲＤＦデータ１１５から縮約ＲＤＦデータ１１６を用いてデータを取得できる。
【００５８】
以上のようにして縮約ＲＤＦデータ１１６の更新を続けていくと、検索性能が劣化する可能性がある。
【００５９】
具体的には、例えば、縮約ＲＤＦデータ１１６の作成において、リテラルの数が均等になるようにリテラル値範囲（縮約範囲）が分割される。例えば、１０００個のリテラルがあり、１０００個のリテラルの値が１〜１０００と連続した整数の場合、リテラルの値範囲は、１〜２５０、２５１〜５００、５０１〜７５０、及び７５１〜１０００と分割されてよい。これにより、各値範囲に属するリテラル数は２５０個と均等であり、縮約ＲＤＦデータ１１６を用いて検索範囲を絞り込んだ場合に、絞り込み先に含まれる要素数（リテラル数）の偏りを防ぐことができ、以って、適度な検索性能を維持できる。しかし、本実施形態では、縮約ＲＤＦデータ１１６及びそのメタ情報は更新されるものの、値範囲（縮約範囲）の再分割は行われない。このため、差分が増えると、複数の値範囲にそれぞれ対応する複数のリテラル数の偏り（偏り）が増え、十分な絞り込み効果を得られず、以って、検索性能が劣化する可能性がある。
【００６０】
そこで、本実施形態では、データ整理プログラム１０７が、図１６に示すデータ整理処理を行う。具体的には、データ整理プログラム１０７は、検索性能が劣化したとみなされる所定の条件である縮約条件が満たされた場合に（ステップ１６０１：Ｙｅｓ）、元ＲＤＦデータ１１５から最新の縮約ＲＤＦデータを作成する（ステップ１６０２）。ステップ１６０２の後、旧い縮約ＲＤＦデータは外部ストレージ装置１１４からデータ整理プログラム１０７により削除されてよい。
【００６１】
縮約条件は、変更不可能に予め決められていてもよいし、管理者（手動）により変更されてもよいし、自動により（例えば、縮約ＲＤＦデータ１１６を用いた検索処理に関する履歴情報を基に）変更されてもよい。例えば、データ整理プログラム１０７は、出力デバイス（表示デバイス）１１２に、縮約条件を入力するための縮約条件設定画面を表示する。
【００６２】
図１７は、縮約条件設定画面の一例を示す。
【００６３】
縮約条件設定画面は、例えばＧＵＩ（Graphical  User  Interface）であり、５つの条件のうちのいずれを縮約条件として採用するかを指定するツール（例えばチェックボックス）と、各条件について関連付けられる閾値の入力欄とを有する。データ整理プログラム１０７は、この縮約条件設定画面を通じて入力された縮約条件を表す縮約条件情報を記憶資源１０３に設定する。
【００６４】
縮約条件は、前述したように、下記５つの条件のうちの少なくとも１つで構成される。
【００６５】
（１）頻度
【００６６】
頻度は、直前回にステップ１６０２（新たに縮約グラフデータを生成すること）が行われてからの経過時間である。つまり、縮約条件としての「頻度」は、ステップ１６０２が周期的に行われることを意味する。頻度に対応した閾値は、ステップ１６０２の実行周期（例えば「毎週土曜」）であり、その実行周期を、頻度に対応した閾値入力欄に入力可能である。データ整理プログラム１０７は、閾値として設定された周期毎に、新たに縮約グラフデータを生成する。なお、データ整理プログラム１０７は、ステップ１６０２の実行時刻と、検索性能（例えば、１つの元クエリを受け付けてからその元クエリに従う検索結果をクエリ発行元に返すまでの時間）の時系列変化と、プロセッサ１１０の負荷の時系列変化とのうちの少なくとも１つを含む履歴情報を記憶資源１０３（又は外部ストレージ装置１１４）に格納し、その履歴情報を基に、頻度に対応した閾値を更新してもよい。縮約ＲＤＦデータ１１６を新たに作成する際には、元のＲＤＦデータ１１５を全件検査する処理が含まれるため、データ整理プログラム１０７は、元のＲＤＦデータ１１５のサイズも更に基にして、頻度に対応した閾値を更新してよい。
【００６７】
（２）時刻
【００６８】
時刻は、ステップ１６０２（新たに縮約グラフデータを生成すること）が行われる時刻（例えば年月日時分）である。つまり、縮約条件としての「時刻」は、ステップ１６０２が指定時刻に行われることを意味する。時刻に対応した閾値は、ステップ１６０２の実行時刻であり、その実行時刻（例えば「2014/02/12/02:00」）を、時刻に対応した閾値入力欄に入力可能である。データ整理プログラム１０７は、閾値として時刻に現時点が達した場合に、新たに縮約グラフデータを生成する。なお、データ整理プログラム１０７は、ステップ１６０２の直前回の実行時刻と、検索性能の時系列変化と、プロセッサ１１０の負荷の時系列変化とのうちの少なくとも１つを含む履歴情報を記憶資源１０３（又は外部ストレージ装置１１４）に格納し、その履歴情報を基に、時刻に対応した閾値を決定してもよい。データ整理プログラム１０７は、元のＲＤＦデータ１１５のサイズも更に基にして、時刻に対応した閾値を決定してよい。
【００６９】
（３）差分容量比
【００７０】
差分容量比とは、過去の或る時点の元のグラフデータのサイズに対して現時点の元のグラフデータのサイズの倍率を意味する。元グラフデータが更新されなければ、複数の値範囲（縮約範囲）にそれぞれ対応した複数のリテラル数（要素数）の偏りは発生しない。リテラル数が偏っていない状態で元ＲＤＦデータ１１５を縮約しても無駄な処理となる。そこで、縮約条件の一要素として、差分容量比が採用される。差分容量比に対応した閾値は、差分容量比としての上記倍率であり、その倍率（例えば「２００％」）を、差分容量比に対応した閾値入力欄に入力可能である。データ整理プログラム１０７は、過去の或る時点の元のグラフデータのサイズに対して現時点の元のグラフデータのサイズの倍率が、閾値として設定された倍率に達した場合に、新たに縮約グラフデータを生成する。なお、データ整理プログラム１０７は、差分容量比の時系列変化と検索性能の時系列変化とを含む履歴情報を記憶資源１０３（又は外部ストレージ装置１１４）に格納し、その履歴情報を基に、差分容量比に対応した閾値を更新してもよい。データ整理プログラム１０７は、元のＲＤＦデータ１１５のサイズも更に基にして、差分容量比に対応した閾値を更新してよい。
【００７１】
（４）検索性能
【００７２】
検索性能に対応した閾値は、検索性能としての上記時間であり、その時間（例えば「1sec」）を、検索性能に対応した閾値入力欄に入力可能である。データ整理プログラム１０７は、検索性能を監視してよい。データ整理プログラム１０７は、検索性能が所定回数以上（例えば１回でも）閾値として設定された検索性能より低下した場合に（検索にかかる時間が閾値としての時間よりも長くなった場合に）、新たに縮約グラフデータを生成する。
【００７３】
（５）偏り
【００７４】
前述したように、縮約ＲＤＦデータ１１６の作成時点では、各値範囲（縮約範囲）に属するリテラル数は均等である。値範囲毎のリテラル数が、初期縮約プログラム１０４又はデータ整理プログラム１０７により記憶資源１０３に格納されてよい。データ整理プログラム１０７又は差分更新プログラム１０６は、元ＲＤＦデータ１１５を更新（データ追加又はデータ削除）の都度に、追加又は削除されたデータに含まれるリテラルが属する値範囲を特定し、その特定した値範囲に対応したリテラル数を更新してよい。リテラル数（要素数）の偏りとして、閾値入力欄には、例えば、リテラル数の最大値に対するリテラル数の最小値の割合が入力可能である。データ整理プログラム１０７は、複数の値範囲にそれぞれ対応した複数のリテラル数の偏りが、入力された閾値としての偏り以上になった場合、新たに縮約グラフデータを生成する。
【００７５】
以上、一実施形態を説明したが、これは本発明の説明のための例示であって、本発明の範囲をこの実施形態にのみ限定する趣旨ではない。本発明は、他の種々の形態でも実施することが可能である。例えば、元ＲＤＦデータ１１５の各レコードに、縮約ＲＤＦデータ１１６からのリンク情報（インデックス）が追加されてよい。リンク情報は、主語及び目的語にそれぞれ対応した縮約値を含んでよい。この場合、クエリ処理プログラム１０５は、縮約値をキーに元ＲＤＦデータ１１５からリソースを特定できる。
【符号の説明】
【００７６】
１００…計算機システム
【図１】
2015125230.tif 000003
【図２】
2015125230.tif 000004
【図３】
2015125230.tif 000005
【図４】
2015125230.tif 000006
【図５】
2015125230.tif 000007
【図６】
2015125230.tif 000008
【図７】
2015125230.tif 000009
【図８】
2015125230.tif 000010
【図９】
2015125230.tif 000011
【図１０】
2015125230.tif 000012
【図１１】
2015125230.tif 000013
【図１２】
2015125230.tif 000014
【図１３】
2015125230.tif 000015
【図１４】
2015125230.tif 000016
【図１５】
2015125230.tif 000017
【図１６】
2015125230.tif 000018
【図１７】
2015125230.tif 000019
【国際調査報告】
2015125230.tif 000020
2015125230.tif 000021
2015125230.tif 000022
2015125230.tif 000023