(57)【要約】【課題】共通クエリグラフパターンの数を低減することができる共通クエリグラフパターン生成装置を提供する。【解決手段】共通クエリグラフパターン生成部１２は、生成した検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベース３０から取得し、検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲（例えば、検索サブグラフの数が「２」以上の範囲）に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフから共通クエリグラフパターンを生成する。【選択図】図１
2011100206.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と
を備えることを特徴とする共通クエリグラフパターン生成装置。
【請求項２】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
取得された検索サブグラフにおける所定の概念を有するノードの種類の数を検索クエリグラフパターンごとに求め、所定の範囲に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と
を備えることを特徴とする共通クエリグラフパターン生成装置。
【請求項３】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
取得された検索サブグラフの２つ以上を組み合わせ、且つ、組み合わせ後の検索サブグラフ内の検索サブグラフの数が所定の範囲に属するようにし、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と
を備えることを特徴とする共通クエリグラフパターン生成装置。
【請求項４】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードの数を求め、該ノードの数について当該組み合わせ内の検索クエリグラフパターンの数より多い分の数であるターゲットリソース数を求め、所定の範囲に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と
を備えることを特徴とする共通クエリグラフパターン生成装置。
【請求項５】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードを検出し、該各ノードに含まれるインスタンスの種類の数であるターゲット数を求め、所定の範囲に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と
を備えることを特徴とする共通クエリグラフパターン生成装置。
【請求項６】
ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと
を備えることを特徴とする共通クエリグラフパターン生成方法。
【請求項７】
ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
取得された検索サブグラフにおける所定の概念を有するノードの種類の数を検索クエリグラフパターンごとに求め、所定の範囲に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと
を備えることを特徴とする共通クエリグラフパターン生成方法。
【請求項８】
ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
取得された検索サブグラフの２つ以上を組み合わせ、且つ、組み合わせ後の検索サブグラフ内の検索サブグラフの数が所定の範囲に属するようにし、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと
を備えることを特徴とする共通クエリグラフパターン生成方法。
【請求項９】
ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードの数を求め、該ノードの数について当該組み合わせ内の検索クエリグラフパターンの数より多い分の数であるターゲットリソース数を求め、所定の範囲に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと
を備えることを特徴とする共通クエリグラフパターン生成方法。
【請求項１０】
ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードを検出し、該各ノードに含まれるインスタンスの種類の数であるターゲット数を求め、所定の範囲に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと
を備えることを特徴とする共通クエリグラフパターン生成方法。
【請求項１１】
請求項１ないし５のいずれかに記載の共通クエリグラフパターン生成装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通クエリグラフパターン生成装置、共通クエリグラフパターン生成方法およびコンピュータプログラムに関するものである。
【背景技術】
【０００２】
従来にあっては、グラフ構造データベースからデータを検索するための共通クエリグラフパターンを生成する技術が開示されている（特許文献１を参照）。
【０００３】
この技術では、まず、ユーザから入力された情報または予め設定された情報を基に、グラフ構造データベースから取得した複数のノードまたはプロパティ間に存在するパスを検索するための検索クエリグラフパターンを生成する。そして、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し、取得された検索サブグラフに含まれるグラフ構造およびこのグラフ構造中のプロパティ名の組み合わせの中で複数回出現するものを抽出する。そして、この抽出されたグラフ構造に含まれる任意のノード名およびプロパティ名を変数にすることにより、ユーザにより入力された情報または予め設定された情報に関連する情報が追加されたデータを検索するための共通クエリグラフパターンを生成する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特願２００５−１３６７０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の技術においては、共通クエリグラフパターンの数が多すぎてしまうことがある。その中には、当たり前のデータしか検索できないようなものも多く含まれることがある。
【０００６】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、共通クエリグラフパターンの数を低減することができる共通クエリグラフパターン生成装置、共通クエリグラフパターン生成方法およびコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、第１の本発明に係る共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えることを特徴とする。
【０００８】
第２の本発明に係る共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、取得された検索サブグラフにおける所定の概念を有するノードの種類の数を検索クエリグラフパターンごとに求め、所定の範囲に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えることを特徴とする。
【０００９】
第３の本発明に係る共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、取得された検索サブグラフの２つ以上を組み合わせ、且つ、組み合わせ後の検索サブグラフ内の検索サブグラフの数が所定の範囲に属するようにし、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えることを特徴とする。
【００１０】
第４の本発明に係る共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードの数を求め、該ノードの数について当該組み合わせ内の検索クエリグラフパターンの数より多い分の数であるターゲットリソース数を求め、所定の範囲に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えることを特徴とする。
【００１１】
第５の本発明に係る共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された情報または予め設定された情報を基に、前記グラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得手段と、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードを検出し、該各ノードに含まれるインスタンスの種類の数であるターゲット数を求め、所定の範囲に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えることを特徴とする。
【００１２】
第６の本発明に係る共通クエリグラフパターンの生成方法は、ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップとを備えることを特徴とする。
【００１３】
第７の本発明に係る共通クエリグラフパターンの生成方法は、ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、取得された検索サブグラフにおける所定の概念を有するノードの種類の数を検索クエリグラフパターンごとに求め、所定の範囲に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップとを備えることを特徴とする。
【００１４】
第８の本発明に係る共通クエリグラフパターンの生成方法は、ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、取得された検索サブグラフの２つ以上を組み合わせ、且つ、組み合わせ後の検索サブグラフ内の検索サブグラフの数が所定の範囲に属するようにし、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップとを備えることを特徴とする。
【００１５】
第９の本発明に係る共通クエリグラフパターンの生成方法は、ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードの数を求め、該ノードの数について当該組み合わせ内の検索クエリグラフパターンの数より多い分の数であるターゲットリソース数を求め、所定の範囲に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップとを備えることを特徴とする。
【００１６】
第１０の本発明に係る共通クエリグラフパターンの生成方法は、ユーザから入力された情報または予め設定された情報を基に、グラフ構造を持つデータが格納されているグラフ構造データベースから取得した複数のノード間に存在するパスである検索サブグラフを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、生成された検索クエリグラフパターンにマッチする検索サブグラフを前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせについて、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードを検出し、該各ノードに含まれるインスタンスの種類の数であるターゲット数を求め、所定の範囲に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップとを備えることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、共通クエリグラフパターンの数を低減することが可能になる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施の形態における共通クエリグラフパターン生成装置を用いた検索システム１の構成を示す全体図である。
【図２】本発明の第１の実施の形態などにおけるグラフ構造データベース内のデータを示す説明図である。
【図３】本発明の第１の実施の形態などにおけるグラフ構造データベース内のデータの一部であり、元のリレーショナルデータベースにおけるデータと、このデータをXML形式およびグラフ形式を用いてRDFで表現した状態を示す説明図である。
【図４】本発明の第１の実施の形態などにおけるオントロジデータベース内のデータの一部を示す説明図である。
【図５】本発明の第１の実施の形態における検索システム１の動作を示すシーケンス図である。
【図６】本発明の第１の実施の形態などにおける入力ＧＵＩの一例を示す説明図である。
【図７】本発明の第１の実施の形態などにおける入力ＧＵＩで入力される入力キーワードにつながるプロパティを太線で示したグラフ構造データを示す説明図である。
【図８】本発明の第１の実施の形態などにおける検索クエリグラフパターンの一例を示す説明図である。
【図９】本発明の第１の実施の形態などにおける検索サブグラフの一例を示す説明図である。
【図１０】本発明の第１、第２の実施の形態における検索クエリグラフパターンごとの検索サブグラフの内容を表にして示す説明図である。
【図１１】本発明の第１の実施の形態などにおける組み合わせ後の検索サブグラフの一例を示す説明図である。
【図１２】本発明の第１の実施の形態などにおける検索サブグラフから生成された共通クエリグラフパターンの一例を示す説明図である。
【図１３】本発明の第１の実施の形態などにおける共通クエリグラフパターンの変数ノードにキーワードを入力して生成された共通クエリグラフパターンの一例を示す説明図である。
【図１４】本発明の第１の実施の形態などにおける共通クエリグラフパターンにマッチする共通サブグラフの一例を示す説明図である。
【図１５】本発明の第１の実施の形態などにおける出力用ＧＵＩの一例を示す説明図である。
【図１６】本発明の第３、第４の実施の形態における検索クエリグラフパターンごとの検索サブグラフの内容を表にして示す説明図である。
【図１７】本発明の第６の実施の形態における検索クエリグラフパターンの組み合わせと、対応するターゲットリソース数の一例を示す説明図である。
【図１８】本発明の第６の実施の形態におけるターゲットリソース数を降順にプロットしたグラフＧ１と、グラフＧ１の微分値をプロットしたグラフＧとを示す説明図である。
【図１９】本発明の第７の実施の形態における検索クエリグラフパターンの組み合わせと、対応するターゲットリソース数の一部の例を示す説明図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面を参照して説明する。
【００２０】
［第１の実施の形態］
図１は、本発明の第１の実施の形態における共通クエリグラフパターン生成装置としての共通クエリグラフ生成部１３を有する検索装置１０を用いた検索システム１の構成を示す全体図である。
【００２１】
検索システム１は、検索装置１０と、ユーザ端末２０と、グラフ構造データベース３０と、オントロジデータベース４０とを有する。
【００２２】
検索装置１０は、ユーザ端末２０、グラフ構造データベース３０、およびオントロジデータベース４０にアクセス可能な状態で接続されている。
【００２３】
また、検索装置１０は、ユーザに検索内容の情報を入力させるための入力用ＧＵＩを生成する入力用ＧＵＩ生成部１１と、この入力用ＧＵＩに入力された情報に基づいて共通クエリグラフパターンを生成してこの共通クエリグラフパターンにマッチする情報をグラフ構造データベースから取得する共通クエリグラフパターン生成部１２と、生成された共通クエリグラフパターンを蓄積する共通クエリグラフパターン蓄積部１３と、ユーザに検索結果を提示するための出力用ＧＵＩを生成する出力用ＧＵＩ生成部１４とを有する。
【００２４】
グラフ構造データベース３０は、図２に示すようなグラフ構造を持つデータが格納されている。第１の実施の形態におけるグラフ構造データはラベル付き有向グラフデータであり、データのアーク（ノード間を結ぶ矢印）をRDFの仕様に基づいてプロパティと称する。
【００２５】
図３は、これらのグラフ構造データがどのように既存のリレーショナルデータベースなどで管理されているデータから生成され、グラフ化されているかを示す説明図である。図３はグラフ構造データベース３０に格納される、図２とは別なデータ例の一部を示したものであり、ドキュメント「T-041」とそのドキュメントの著者「山田太郎」と、そのドキュメントの題名「セマンティックWeb入門」と、そのドキュメントのキーワード「セマンティックWeb」とが与えられているデータを、XML形式およびグラフ形式を用いてRDFで表現したものである。
【００２６】
オントロジデータベース４０は、図４に示すようなWeb Ontology Language(OWL)を用いて表現される、言葉の意味や分類体系を定義するためのオントロジデータが格納されている。図４では、プロパティ「rm:キーワード」とプロパティ「ms:用語」とは等価であり、プロパティ「rm:著者」とプロパティ「ms:著者」とは等価であることが示されている。
【００２７】
（検索システム１の動作）
次に、上記のように構成された検索システム１の動作を、図５のシーケンス図を用いて説明する。なお、説明では省略するが、オントロジデータベース４０はプロパティの等価性の判断に使用され、判断結果が適宜処理に利用される。
【００２８】
さて、検索システム１の動作では、まず、入力用ＧＵＩ生成部１１において入力用ＧＵＩが生成される（Ｓ１）。本実施形態において生成される入力用ＧＵＩには、図６に示すように、キーワードを入力するスペースと、概念（クラス）を選択する欄が設けられている。
【００２９】
そして、生成された入力用ＧＵＩがユーザ端末２０に表示され、ユーザによりキーワードの入力および概念が選択される（Ｓ２）。第１の実施の形態においては、ユーザによりキーワードとして「セマンティックWeb」が入力され、概念（クラス）として「人」が選択されている。入力されたキーワードおよび選択された概念のデータは共通クエリグラフパターン生成部１２に出力される。
【００３０】
共通クエリグラフパターン生成部１２では、取得したキーワードを基にグラフ構造データベース３０にアクセスが行われる（Ｓ３）。
【００３１】
そして、グラフ構造データベース３０において、このキーワード「セマンティックWeb」につながるプロパティが抽出される（Ｓ４）。抽出されたプロパティのアークが太線で示され、プロパティ名に下線が引かれたグラフ構造データの例を図７に示す。
【００３２】
さらにグラフ構造データベース３０において、これらの太線で示されたアークのプロパティ「rm:キーワード」、「rm：用語」、「ms：キーワード」または「ms:用語」を基に、このプロパティ「rm:キーワード」、「rm：用語」、「ms：キーワード」または「ms:用語」と、ユーザにより選択されたクラス「Person:人」のインスタンス「Person:佐藤」、「Person:鈴木」、または「Person:田中」との間にあるパスをグラフ構造データベース３０から取得することが可能な検索クエリグラフパターンが全て生成される（Ｓ５）。
【００３３】
図８は、生成された検索クエリグラフパターンの一例を示す説明図である。第１の実施の形態においては図８に示すように、ステップＳ４で抽出されたプロパティ「rm:キーワード」、「rm：用語」、「ms：キーワード」または「ms:用語」と、ユーザにより選択されたクラス「Person:人」と、このクラス「Person:人」のインスタンス「Person:佐藤」、「Person:鈴木」、または「Person:田中」からクラス「Person:人」につながるプロパティ「rdf:type」とが固定された４種類の検索クエリグラフパターンＰ１〜Ｐ４が生成されている。図８において、名称の先頭に「?」マークが記載されているノードは、任意の値が入る可能性がある変数であることを示している。
【００３４】
例えば、「?keyword」は、図７における「セマンティックＷｅｂ」のようなインスタンスに対応する変数である。また、「?x」は、図７における「Ｂプロジェクト」のようなインスタンスに対応する変数である。また、「?p1」は、図７における「pj:担当者」のようなプロパティに対応する変数である。また、「?Person」は、図７における「Person:佐藤」のようなインスタンスに対応する変数である。
【００３５】
次に、生成された４種類の検索クエリグラフパターンを基に、共通クエリグラフパターン生成部１２からグラフ構造データベース３０にアクセスされる（Ｓ６）。
【００３６】
そして、グラフ構造データベース３０においてこの検索クエリグラフパターンにマッチする検索サブグラフ（変数ノード「?keyword」と変数ノード「?Person」との間にパスが存在するサブグラフ）が取得される（Ｓ７）。
【００３７】
図９は、グラフ構造データベース３０から取得された検索サブグラフの一例である検索サブグラフＱ１〜Ｑ１０を示す説明図である。ここでは、図２における位置が上のものから検索サブグラフＱ１〜Ｑ１０としている。
【００３８】
図１０は、検索クエリグラフパターンごとの検索サブグラフの内容を表にして示す説明図である。
【００３９】
検索クエリグラフパターンＰ１にマッチする検索サブグラフとしては、検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８が取得される。その中で「Person:佐藤」を含むものは検索サブグラフＱ１の１つであり、「Person:鈴木」を含むものは検索サブグラフＱ４、Ｑ５の２つであり、「Person:田中」を含むものは検索サブグラフＱ８の１つある。
【００４０】
検索クエリグラフパターンＰ２にマッチする検索サブグラフとしては、検索サブグラフＱ１０が取得される。これは「Person:佐藤」を含むものではなく、「Person:鈴木」を含むものでもなく、「Person:田中」を含む検索サブグラフである。
【００４１】
検索クエリグラフパターンＰ３にマッチする検索サブグラフとしては、検索サブグラフＱ２、Ｑ６、Ｑ９が取得される。その中で「Person:佐藤」を含むものは検索サブグラフＱ２の１つであり、「Person:鈴木」を含むものは検索サブグラフＱ６の１つであり、「Person:田中」を含むものは検索サブグラフＱ９の１つある。
【００４２】
検索クエリグラフパターンＰ４にマッチする検索サブグラフとしては、検索サブグラフＱ３、Ｑ７が取得される。その中で「Person:佐藤」を含むものは検索サブグラフＱ３の１つであり、「Person:鈴木」を含むものは検索サブグラフＱ７の１つであり、「Person:田中」を含むものはない。
【００４３】
次に、共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０から所定の条件を充足しないものを除外する（Ｓ８）。
【００４４】
ここでは、事前にあるいはこれまでの過程で当該目的のための比率（以下、比率Ｒという）が設定されたこととする。比率Ｒは、０〜１の範囲で設定される。ここでは、例として、比率Ｒを０．５とする。
【００４５】
なお、比率Ｒは、例えば、共通クエリグラフパターン生成部１２を動作させるコンピュータプログラムが実行される前に指定され、コンピュータプログラムの実行時において共通クエリグラフパターン生成部１２によって読み込まれる。または、比率Ｒは、例えば、共通クエリグラフパターン生成部１２を動作させるコンピュータプログラムに予め埋め込まれている。後述の比率ＲＵ、比率ＲＬ、比率Ｓ、比率ＳＵ、比率ＳＬ、最大数ＭＡＸ、最小数ＭＩＮ、比率ＫＵ、比率ＫＬ、比率ＴＵおよび比率ＴＬも同様である。
【００４６】
さて、まず、共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０においてクラス「Person:人」のインスタンスに関する種類の数Ｍを算出する。
【００４７】
「Person:人」のインスタンスは、「Person:佐藤」、「Person:鈴木」、「Person:田中」なので、種類の数Ｍは「３」である。
【００４８】
次に、共通クエリグラフパターン生成部１２では、数Ｍに比率Ｒを掛け、結果として、数値「１．５」が得られる。次に、共通クエリグラフパターン生成部１２では、数値「１．５」より大きい最小の整数「２」を求める。
【００４９】
次に、共通クエリグラフパターン生成部１２では、まず、検索クエリグラフパターンＰ１にマッチする検索サブグラフの数「４」が整数「２」以上か否かを判定し、数「４」が整数「２」以上なので、検索クエリグラフパターンＰ１から取得されたＱ１、Ｑ４、Ｑ５、Ｑ８を除外せずに残す。
【００５０】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ２にマッチする検索サブグラフの数「１」が整数「２」以上か否かを判定し、数「１」が整数「２」以上ではないので、検索クエリグラフパターンＰ２から取得された検索サブグラフＱ１０を除外する。
【００５１】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ３にマッチする検索サブグラフの数「３」が整数「２」以上か否かを判定し、数「３」が整数「２」以上なので、検索クエリグラフパターンＰ３から取得された検索サブグラフＱ２、Ｑ６、Ｑ９を除外せずに残す。
【００５２】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ４にマッチする検索サブグラフの数「２」が整数「２」以上か否かを判定し、数「２」が整数「２」以上なので、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７を除外せずに残す。
【００５３】
こうして、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ１０が除外される。
【００５４】
次に、共通クエリグラフパターン生成部１２では、残った検索サブグラフの２つ以上を組み合わせた検索サブグラフを１つ以上生成する。ここでは、検索サブグラフＱ１０を除く検索サブグラフＱ１〜Ｑ９を利用して生成可能な最も多くの組み合わせが生成されたこととする。
【００５５】
図１１は、組み合わせ後の検索サブグラフの一例を示す説明図である。検索サブグラフＱ１、Ｑ２を組み合わせた検索サブグラフは同図に示すようなものとなる。
【００５６】
次に、共通クエリグラフパターン生成部１２では、生成された検索サブグラフにおけるノードを変数（名称の先頭に「?」マークが記載されている）に置き換えた共通クエリグラフパターンを生成する（Ｓ９）。
【００５７】
生成された共通クエリグラフパターンは、共通クエリグラフパターン生成部１２から共通クエリグラフパターン蓄積部１３に送出され蓄積される（Ｓ１０）。
【００５８】
図１２は、生成された共通クエリグラフパターンの一例を示す説明図である。検索サブグラフＱ１、Ｑ２を組み合わせた検索サブグラフから生成された共通クエリグラフパターンは同図に示すようなものとなる。
【００５９】
ここで、「?keyword」は、図７における「セマンティックＷｅｂ」のようなインスタンスに対応する変数である。また、「?x」や「?y」はそれぞれ、図７における「Ｂプロジェクト」のようなインスタンスに対応する変数である。また、「?Person」は、図７における「Person:佐藤」のようなインスタンスに対応する変数である。
【００６０】
次に、図１３に示すように、ステップＳ９で生成された共通クエリグラフパターンの変数ノード「?keyword」にユーザにより入力されたキーワード「セマンティックWeb」を代入し、この共通クエリグラフパターンを基に、共通クエリグラフパターン生成部１２からグラフ構造データベース３０にアクセスされる（Ｓ１３）。
【００６１】
そして、グラフ構造データベース３０においてこのキーワード「セマンティックWeb」が代入された共通クエリグラフパターンにマッチする共通サブグラフが取得される（Ｓ１４）。
【００６２】
図１４は、グラフ構造データベース３０から取得された共通サブグラフの一例を示す説明図である。図１３の共通クエリグラフパターンにマッチする共通サブグラフは図１４に示すようなものとなる。この共通サブグラフは、図１３に示した共通クエリグラフパターンにおける変数「?x」、「?y」、「?Person」をそれぞれ、インスタンス「Ａプロジェクト」、「rm:T-041」、「Person:佐藤」に置き換えたものとなっている。
【００６３】
次に、出力用ＧＵＩ生成部１４は、例えば、図１４の共通サブグラフについて、図１５に示すような表形式の出力用ＧＵＩを生成する（Ｓ１６）。出力用ＧＵＩは、ユーザ端末２０に送信され表示される（Ｓ１７）。
【００６４】
したがって、第１の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲（上記例では検索サブグラフの数が「２」以上の範囲）に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【００６５】
［第２の実施の形態］
次に、第２の実施の形態について説明する。第２の実施の形態は、第１の実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【００６６】
第１の実施の形態では、検索サブグラフの数の下限を設定したのに対し、第２の実施の形態では、検索サブグラフの上下限を設定する。
【００６７】
共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０から所定の条件を充足しないものを除外する（Ｓ８）。
【００６８】
ここでは、事前にあるいはこれまでの過程で当該目的のための比率（以下、比率ＲＵという）と比率（以下、比率ＲＬ）が設定されたこととする。比率は、０〜１の範囲で、且つ、比率ＲＵ＞比率ＲＬとなるように設定される。ここでは、例として、比率ＲＵを０．８、比率ＲＬを０．５とする。なお、一方の比率と比率どうしの差とを設定しておき、その一方の比率と差を使用して、他方の比率を求めてもよい。
【００６９】
まず、共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０においてクラス「Person:人」のインスタンスに関する種類の数Ｍを算出する。
【００７０】
「Person:人」のインスタンスは、「Person:佐藤」、「Person:鈴木」、「Person:田中」なので、種類の数Ｍは「３」である。
【００７１】
次に、共通クエリグラフパターン生成部１２では、数Ｍに比率ＲＵを掛け、結果として、数値「２．４」が得られる。
【００７２】
また、共通クエリグラフパターン生成部１２では、数Ｍに比率ＲＬを掛け、結果として、数値「１．５」が得られる。
【００７３】
次に、共通クエリグラフパターン生成部１２では、数値「２．４」より大きい最小の整数「３」を求める。
【００７４】
また、共通クエリグラフパターン生成部１２では、数値「１．５」より大きい最小の整数「２」を求める。
【００７５】
次に、共通クエリグラフパターン生成部１２では、まず、検索クエリグラフパターンＰ１にマッチする検索サブグラフの数「４」が整数「３」未満且つ整数「２」以上か否かを判定し、数「４」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ１から取得されたＱ１、Ｑ４、Ｑ５、Ｑ８を除外する。
【００７６】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ２にマッチする検索サブグラフの数「１」が整数「３」未満且つ整数「２」以上か否かを判定し、数「１」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ２から取得された検索サブグラフＱ１０を除外する。
【００７７】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ３にマッチする検索サブグラフの数「３」が整数「３」未満且つ整数「２」以上か否かを判定し、数「３」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ３から取得された検索サブグラフＱ２、Ｑ６、Ｑ９を除外する。
【００７８】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ４にマッチする検索サブグラフの数「２」が整数「３」未満且つ整数「２」以上か否かを判定し、数「２」が整数「３」未満且つ整数「２」以上なので、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７を除外せずに残す。
【００７９】
こうして、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ３、Ｑ７以外が除外される。
【００８０】
以下の工程は第１の実施の形態のものと同様であり重複となるので説明を省略する。
【００８１】
したがって、第２の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、取得された検索サブグラフの数を検索クエリグラフパターンごとに求め、所定の範囲（上記例では検索サブグラフの数が「３」未満且つ「２」以上の範囲）に属さない検索サブグラフの数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【００８２】
［第３の実施の形態］
次に、第３の実施の形態について説明する。第３の実施の形態は、第１の実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【００８３】
第１の実施の形態などでは、検索サブグラフの数の下限、上下限を設定したのに対し、第３の実施の形態では、検索サブグラフにおける所定の概念を有するノードの種類の数の下限を設定する。
【００８４】
共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０から所定の条件を充足しないものを除外する（Ｓ８）。
【００８５】
ここでは、事前にあるいはこれまでの過程で当該目的のための比率（以下、比率Ｓという）が設定されたこととする。比率は、０〜１の範囲で設定される。ここでは、例として、比率Ｓを０．５とする。
【００８６】
まず、共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０においてクラス「Person:人」のインスタンスに関する種類の数Ｍを算出する。
【００８７】
「Person:人」のインスタンスは、「Person:佐藤」、「Person:鈴木」、「Person:田中」なので、種類の数Ｍは「３」である。
【００８８】
次に、共通クエリグラフパターン生成部１２では、数Ｍに比率Ｓを掛け、結果として、数値「１．５」が得られる。
【００８９】
次に、共通クエリグラフパターン生成部１２では、数値「０．５」より大きい最小の整数「２」を求める。
【００９０】
次に、共通クエリグラフパターン生成部１２では、まず、各検索クエリグラフパターンＰ１〜Ｐ４にマッチする検索サブグラフにおいてクラス「Person:人」のインスタンスに関する種類の数Ｍ１〜Ｍ４を算出する。
【００９１】
図１６に示すように、検索クエリグラフパターンＰ１にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」、「Person:田中」があるので、種類の数Ｍ１は３である。図１６において、○印は、該当のインスタンスが１以上あることを示し、×印は、該当のインスタンスがないことを示す。
【００９２】
検索クエリグラフパターンＰ２にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:田中」があるので、種類の数Ｍ２は１である。
【００９３】
検索クエリグラフパターンＰ３にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」、「Person:田中」があるので、種類の数Ｍ３は３である。
【００９４】
検索クエリグラフパターンＰ４にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」があるので、種類の数Ｍ４は２である。
【００９５】
次に、共通クエリグラフパターン生成部１２では、数Ｍ１「３」が整数「２」以上か否かを判定し、数Ｍ１「３」が整数「２」以上なので、検索クエリグラフパターンＰ１から取得されたＱ１、Ｑ４、Ｑ５、Ｑ８を除外せず残す。
【００９６】
また、共通クエリグラフパターン生成部１２では、数Ｍ２「１」が整数「２」以上か否かを判定し、数Ｍ２「１」が整数「２」以上でないので、検索クエリグラフパターンＰ２から取得された検索サブグラフＱ１０を除外する。
【００９７】
また、共通クエリグラフパターン生成部１２では、数Ｍ３「３」が整数「２」以上か否かを判定し、数Ｍ３「３」が整数「２」以上なので、検索クエリグラフパターンＰ３からから取得された検索サブグラフＱ２、Ｑ６、Ｑ９を除外せず残す。
【００９８】
また、共通クエリグラフパターン生成部１２では、数Ｍ４「２」が整数「２」以上か否かを判定し、数Ｍ４「２」が整数「２」以上なので、検索クエリグラフパターンＰ４からから取得された検索サブグラフＱ３、Ｑ７を除外せずに残す。
【００９９】
こうして、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ１０が除外される。
【０１００】
以下の工程は第１の実施の形態のものと同様であり重複となるので説明を省略する。
【０１０１】
したがって、第３の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、取得された検索サブグラフにおける所定の概念を有するノード（上記例ではクラス「Person:人」」にプロパティ「rdf:type」でつながるノード）の種類の数（上記例ではクラス「Person:人」」にプロパティ「rdf:type」でつながるノードのインスタンスの種類の数）を検索クエリグラフパターンごとに求め、所定の範囲（上記例では「２」以上の範囲）に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【０１０２】
［第４の実施の形態］
次に、第４の実施の形態について説明する。第４の実施の形態は、第１の実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【０１０３】
第３の実施の形態では、検索サブグラフにおける所定の概念を有するノードの種類の数の下限を設定したのに対し、第４の実施の形態では、検索サブグラフにおける所定の概念を有するノードの種類の数の上下限を設定する。
【０１０４】
共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０から所定の条件を充足しないものを除外する（Ｓ８）。
【０１０５】
ここでは、事前にあるいはこれまでの過程で当該目的のための比率（以下、比率ＳＵという）と比率（以下、比率ＳＬ）が設定されたこととする。比率は、０〜１の範囲で、且つ、比率ＳＵ＞比率ＳＬとなるように設定される。ここでは、例として、比率ＳＵを０．８、比率ＳＬを０．５とする。
【０１０６】
まず、共通クエリグラフパターン生成部１２では、検索サブグラフＱ１〜Ｑ１０においてクラス「Person:人」のインスタンスに関する種類の数Ｍを算出する。
【０１０７】
「Person:人」のインスタンスは、「Person:佐藤」、「Person:鈴木」、「Person:田中」なので、種類の数Ｍは「３」である。
【０１０８】
次に、共通クエリグラフパターン生成部１２では、数Ｍに比率ＳＵを掛け、結果として、数値「２．４」が得られる。
【０１０９】
また、共通クエリグラフパターン生成部１２では、数Ｍに比率ＳＬを掛け、結果として、数値「１．５」が得られる。
【０１１０】
次に、共通クエリグラフパターン生成部１２では、数値「２．４」より大きい最小の整数「３」を求める。
【０１１１】
また、共通クエリグラフパターン生成部１２では、数値「１．５」より大きい最小の整数「２」を求める。
【０１１２】
次に、共通クエリグラフパターン生成部１２では、まず、各検索クエリグラフパターンＰ１〜Ｐ４にマッチする検索サブグラフにおいてクラス「Person:人」のインスタンスに関する種類の数Ｍ１〜Ｍ４を算出する。
【０１１３】
図１６に示すように、検索クエリグラフパターンＰ１にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」、「Person:田中」があるので、種類の数Ｍ１は３である。
【０１１４】
検索クエリグラフパターンＰ２にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:田中」があるので、種類の数Ｍ２は１である。
【０１１５】
検索クエリグラフパターンＰ３にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」、「Person:田中」があるので、種類の数Ｍ３は３である。
【０１１６】
検索クエリグラフパターンＰ４にマッチする検索サブグラフの中にクラス「Person:人」のインスタンスとしては、「Person:佐藤」、「Person:鈴木」があるので、種類の数Ｍ４は２である。
【０１１７】
次に、共通クエリグラフパターン生成部１２では、数Ｍ１「３」が整数「３」未満且つ整数「２」以上か否かを判定し、数Ｍ１「３」が整数「３」未満且つ整数「２」以上でないので、検索クエリグラフパターンＰ１から取得されたＱ１、Ｑ４、Ｑ５、Ｑ８を除外する。
【０１１８】
また、共通クエリグラフパターン生成部１２では、数Ｍ２「１」が整数「３」未満且つ整数「２」以上か否かを判定し、数Ｍ２「１」が整数「３」未満且つ整数「２」以上でないので、検索クエリグラフパターンＰ２から取得された検索サブグラフＱ１０を除外する。
【０１１９】
また、共通クエリグラフパターン生成部１２では、数Ｍ３「３」が整数「３」未満且つ整数「２」以上か否かを判定し、数Ｍ３「３」が整数「３」未満且つ整数「２」以上でないので、検索クエリグラフパターンＰ３からから取得された検索サブグラフＱ２、Ｑ６、Ｑ９を除外する。
【０１２０】
また、共通クエリグラフパターン生成部１２では、数Ｍ４「２」が整数「３」未満且つ整数「２」以上か否かを判定し、数Ｍ４「２」が整数「３」未満且つ整数「２」以上なので、検索クエリグラフパターンＰ４からから取得された検索サブグラフＱ３、Ｑ７を除外せずに残す。
【０１２１】
こうして、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ３、Ｑ７以外が除外される。
【０１２２】
以下の工程は第１の実施の形態のものと同様であり重複となるので説明を省略する。
【０１２３】
したがって、第４の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、取得された検索サブグラフにおける所定の概念を有するノード（上記例ではクラス「Person:人」」にプロパティ「rdf:type」でつながるノード）の種類の数（上記例ではクラス「Person:人」」にプロパティ「rdf:type」でつながるノードのインスタンスの種類の数）を検索クエリグラフパターンごとに求め、所定の範囲（上記例では「３」未満且つ「２」以上の範囲）に属さないノードの種類の数に対応する検索サブグラフを除外し、残った検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【０１２４】
［第５の実施の形態］
次に、第５の実施の形態について説明する。第５の実施の形態は、第１〜第４のいずれかの実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【０１２５】
第５の実施の形態では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する数の検索サブグラフを組み合わせる。
【０１２６】
ここでは、例として、検索サブグラフＱ１〜Ｑ１０から除外されたものがなかったこととする（Ｓ８）。なお、このステップＳ８の処理は省略してもよい。
【０１２７】
また、事前にあるいはこれまでの過程で当該目的のための整数（上記の最大数ＭＡＸである）と整数（上記の最小数ＭＩＮである）が設定されたこととする。ここでは、例として、最大数ＭＡＸを３、最小数ＭＩＮを２とする。
【０１２８】
共通クエリグラフパターン生成部１２では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する整数の１つである「２」に対応すべく２つの検索サブグラフを組み合わせた検索サブグラフを１以上生成する。
【０１２９】
また、共通クエリグラフパターン生成部１２では、当該範囲に属する整数の１つである「３」に対応すべく３つの検索サブグラフを組み合わせた検索サブグラフを１以上生成する。
【０１３０】
以下の工程は第１の実施の形態などのものと同様であり重複となるので説明を省略する。
【０１３１】
したがって、第５の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、取得された検索サブグラフの２つ以上を組み合わせ、且つ、組み合わせ後の検索サブグラフ内の検索サブグラフの数が所定の範囲（上記例では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲）に属するようにし、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【０１３２】
［第６の実施の形態］
次に、第６の実施の形態について説明する。第６の実施の形態は、第５の実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【０１３３】
第６の実施の形態では、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせ、当該各組み合わせについての評価値（後述のターゲットリソース数）を計算する。
【０１３４】
ここでは、事前にあるいはこれまでの過程で比率（以下、比率ＫＵという）と比率（以下、比率ＫＬ）が設定されたこととする。比率は、０〜１の範囲で、且つ、比率ＫＵ＞比率ＫＬとなるように設定される。ここでは、例として、比率ＫＵを０．８、比率ＲＬを０．５とする。なお、一方の比率と比率どうしの差とを設定しておき、その一方の比率と差を使用して、他方の比率を求めてもよい。
【０１３５】
また、事前にあるいはこれまでの過程で最大数ＭＡＸと最小数ＭＩＮが設定されたこととする。ここでは、例として、最大数ＭＡＸを３、最小数ＭＩＮを２とする。
【０１３６】
また、例として、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ２が除外されたこととする（Ｓ８）。また、検索クエリグラフパターンＰ１〜Ｐ４から検索サブグラフＱ２に対応する検索クエリグラフパターンＰ２が除外されたこととする。なお、このステップＳ８の処理は省略してもよい。
【０１３７】
共通クエリグラフパターン生成部１２では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する整数の１つである「２」に対応すべくいずれかの検索クエリグラフパターンを合計で２回使用して、それらを組み合わせたものを１以上生成する。
【０１３８】
ここでは、図１７に示すように、６通りの組み合わせが生成される。
【０１３９】
また、共通クエリグラフパターン生成部１２では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する整数の１つである「３」に対応すべくいずれかの検索クエリグラフパターンを合計で３回使用して、それらを組み合わせたものを１以上生成する。
【０１４０】
ここでは、図１７に示すように、１０通りの組み合わせが生成される。
【０１４１】
次に、共通クエリグラフパターン生成部１２は、合計で１６通りの組のそれぞにつき、ターゲットリソース数を算出する。
【０１４２】
（Ｐ１，Ｐ１の場合）
例えば、検索クエリグラフパターンＰ１、Ｐ１を使用した組の場合は、以下のようにする。まず、組中の検索クエリグラフパターン数ｍを求める。検索クエリグラフパターン数ｍは２である。
【０１４３】
次に、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８（クラス「人」のインスタンスはそれぞれ検索サブグラフＱ１では「Person:佐藤」、検索サブグラフＱ４では「Person:鈴木」、検索サブグラフＱ５では「Person:鈴木」、検索サブグラフＱ８では「Person:鈴木」である。）の１つと、残りの３つの内の１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１４４】
取得された組み合わせ６通り（＝４×３÷２）の内、検索サブグラフＱ４と検索サブグラフＱ５の組み合わせ（以下、組「Ｑ４鈴木、Ｑ５鈴木」と表記する。他の組み合わせも同様に表記する。）、組「Ｑ４鈴木、Ｑ８鈴木」、組「Ｑ５鈴木、Ｑ８鈴木」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:鈴木」のノード）を有する。
【０１４５】
共通クエリグラフパターン生成部１２は、このようなノードの数「３」を求め、該当のノードの数「３」から検索クエリグラフパターン数ｍ「２」を減算し、その結果「１」を得る。このように結果が正の数ならは、その結果「１」がターゲットリソース数である。
【０１４６】
（Ｐ４，Ｐ４の場合）
例えば、検索クエリグラフパターンＰ４、Ｐ４を使用した組の場合は、以下のようにする。まず、組中の検索クエリグラフパターン数ｍを求める。検索クエリグラフパターン数ｍは２である。
【０１４７】
次に、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７（クラス「人」のインスタンスはそれぞれＱ３佐藤、Ｑ７鈴木である。）の１つと、残りの１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１４８】
取得された組み合わせは１通り（＝２×１÷２）であり、それは組「Ｑ４鈴木、Ｑ５鈴木」である。この組み合わせでは、ノードの共有がない。
【０１４９】
共通クエリグラフパターン生成部１２は、このようなノードの数「０」を求め、該当のノードの数「０」から検索クエリグラフパターン数ｍ「２」を減算し、その結果「−２」を得る。このように結果が「０」または負の数ならは、ターゲットリソース数は「０」である。
【０１５０】
（Ｐ１、Ｐ４の場合）
例えば、検索クエリグラフパターンＰ１、Ｐ４を使用した組の場合は、以下のようにする。まず、組中の検索クエリグラフパターン数ｍを求める。検索クエリグラフパターン数ｍは２である。
【０１５１】
次に、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８（クラス「人」のインスタンスはそれぞれ検索サブグラフＱ１では「Person:佐藤」、検索サブグラフＱ４では「Person:鈴木」、検索サブグラフＱ５では「Person:鈴木」、検索サブグラフＱ８では「Person:鈴木」である。）の１つと、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７（クラス「人」のインスタンスはそれぞれ検索サブグラフＱ３では「Person:佐藤」、検索サブグラフＱ７では「Person:鈴木」である。）の１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１５２】
取得された組み合わせ８通り（＝４×２）の内、組「Ｑ４鈴木、Ｑ７鈴木」、組「Ｑ５鈴木、Ｑ７鈴木」、組「Ｑ８鈴木、Ｑ７鈴木」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:鈴木」のノード）を有する。また、組「Ｑ１佐藤、Ｑ３佐藤」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:佐藤」のノード）を有する。
【０１５３】
共通クエリグラフパターン生成部１２は、このようなノードの数「４」を求め、該当のノードの数「４」から検索クエリグラフパターン数ｍ「２」を減算し、その結果「２」を得る。このように結果が正の数ならは、その結果「２」がターゲットリソース数である。
【０１５４】
なお、詳細説明は略すが、共通クエリグラフパターン生成部１２は、他の１３通りの組み合わせについても、同様にターゲットリソース数を算出する。
【０１５５】
次に、共通クエリグラフパターン生成部１２は、ターゲットリソース数の最大値Ｋを算出する。図１７に示すように、ターゲットリソース数の最大値Ｋは、「３」である。
【０１５６】
次に、共通クエリグラフパターン生成部１２では、最大値Ｋに比率ＫＵを掛け、結果として、数値「２．４」が得られる。
【０１５７】
また、共通クエリグラフパターン生成部１２では、最大値Ｋに比率ＫＬを掛け、結果として、数値「１．５」が得られる。
【０１５８】
次に、共通クエリグラフパターン生成部１２では、数値「２．４」より大きい最小の整数「３」を求める。
【０１５９】
また、共通クエリグラフパターン生成部１２では、数値「１．５」より大きい最小の整数「２」を求める。
【０１６０】
次に、共通クエリグラフパターン生成部１２では、まず、検索クエリグラフパターンＰ１、Ｐ１を使用した組のターゲットリソース数「１」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲットリソース数「１」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、残りの３つの内の１つとからなる検索サブグラフの組み合わせを除外する。
【０１６１】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ４、Ｐ４を使用した組のターゲットリソース数「０」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲットリソース数「０」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の組み合わせを除外する。
【０１６２】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ１、Ｐ４を使用した組のターゲットリソース数「２」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲットリソース数「２」が整数「３」未満且つ整数「２」以上なので、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の１つとからなる検索サブグラフの組み合わせを除外せずに残す。
【０１６３】
なお、詳細説明は略すが、共通クエリグラフパターン生成部１２は、他の１３通りの組み合わせについても、同様に検索サブグラフの組み合わせを除外するか否かを判定し、該当する場合は当該検索サブグラフの組み合わせを除外する。
【０１６４】
以下の工程は第１の実施の形態などのものと同様であり重複となるので説明を省略する。
【０１６５】
なお、数値「２．４」より大きい最小の整数「３」や、数値「１．５」より大きい最小の整数「２」は、閾値でり、かかる閾値を求めるには以下のようにしてもよい。
【０１６６】
図１８に示すように、共通クエリグラフパターン生成部１２では、例えば、ターゲットリソース数を降順にプロットしたグラフＧ１を生成し、グラフＧの微分値をプロットしたグラフＧ２を生成し、グラフＧ２の極値に対応するターゲットリソース数ＴＰから閾値を選択してもよい。
【０１６７】
したがって、第６の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせ（上記例では１６通りの各組み合わせ）について、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードの数を求め、該ノードの数について当該組み合わせ内の検索クエリグラフパターンの数より多い分の数であるターゲットリソース数を求め（上記例では、検索クエリグラフパターンＰ１、Ｐ１を使用した組、検索クエリグラフパターンＰ４、Ｐ４を使用した組、検索クエリグラフパターンＰ１、Ｐ４を使用した組についてのターゲットリソース数の例を示した。）、所定の範囲（上記例では、「３」未満且つ「２」以上の範囲）に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【０１６８】
例えば、多数の従業員を擁する会社のデータが格納されたグラフ構造データベース３０を使用した場合、ターゲットリソース数が非常に高くなる傾向がある一方で、そのような高いターゲットリソース数に対応する共通クエリグラフパターンから検索できるデータには、会社を介した共通性を示すもの、つまりは、当たり前のものが多く、有意義ではないが、ターゲットリソース数の上限を設定することは、このような不都合の回避に貢献する。つまり、単にグラフ構造データベース３０を見ただけでは分かりにくい共通性の発見に貢献することができる。
【０１６９】
［第７の実施の形態］
次に、第７の実施の形態について説明する。第７の実施の形態は、第５の実施の形態に対して、共通クエリグラフパターンの生成方法が異なるのでこの点を中心に説明する。
【０１７０】
第７の実施の形態では、第６の実施の形態におけるターゲットリソース数とは別の評価値（後述のターゲット数）を計算する。
【０１７１】
ここでは、事前にあるいはこれまでの過程で比率（以下、比率ＴＵという）と比率（以下、比率ＴＬ）が設定されたこととする。比率は、０〜１の範囲で、且つ、比率ＴＵ＞比率ＴＬとなるように設定される。ここでは、例として、比率ＴＵを０．８、比率ＴＬを０．５とする。なお、一方の比率と比率どうしの差とを設定しておき、その一方の比率と差を使用して、他方の比率を求めてもよい。
【０１７２】
また、事前にあるいはこれまでの過程で最大数ＭＡＸと最小数ＭＩＮが設定されたこととする。ここでは、例として、最大数ＭＡＸを３、最小数ＭＩＮを２とする。
【０１７３】
また、例として、検索サブグラフＱ１〜Ｑ１０から検索サブグラフＱ２が除外されたこととする（Ｓ８）。また、検索クエリグラフパターンＰ１〜Ｐ４から検索サブグラフＱ２に対応する検索クエリグラフパターンＰ２が除外されたこととする。なお、このステップＳ８の処理は省略してもよい。
【０１７４】
共通クエリグラフパターン生成部１２では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する整数の１つである「２」に対応すべくいずれかの検索クエリグラフパターンを合計で２回使用して、それらを組み合わせたものを１以上生成する。
【０１７５】
ここでは、図１９（ａ）に示すように、６通りの組み合わせが生成される。
【０１７６】
また、共通クエリグラフパターン生成部１２では、最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する整数の１つである「３」に対応すべくいずれかの検索クエリグラフパターンを合計で３回使用して、それらを組み合わせたものを１以上生成する。
【０１７７】
ここでは、図１９（ａ）に示すように、１０通りの組み合わせが生成される。
【０１７８】
次に、共通クエリグラフパターン生成部１２は、合計で１６通りの組のそれぞにつき、ターゲット数を算出する。
【０１７９】
（Ｐ１，Ｐ１の場合）
例えば、検索クエリグラフパターンＰ１、Ｐ１を使用した組の場合は、以下のようにする。
【０１８０】
次に、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、残りの３つの内の１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１８１】
取得された組み合わせ６通り（＝４×３÷２）の内、組「Ｑ４鈴木、Ｑ５鈴木」、組「Ｑ４鈴木、Ｑ８鈴木」、組「Ｑ５鈴木、Ｑ８鈴木」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:鈴木」のノード）を有する。
【０１８２】
共通クエリグラフパターン生成部１２は、このインスタンス「Person:鈴木」のようなインスタンスの種類の数「１」を求める。この数「１」がターゲット数である（図１９（ｂ））。
【０１８３】
（Ｐ４，Ｐ４の場合）
例えば、検索クエリグラフパターンＰ４、Ｐ４を使用した組の場合は、以下のようにする。
【０１８４】
次に、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の１つと、残りの１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１８５】
取得された組み合わせは１通り（＝２×１÷２）であり、それは組「Ｑ４鈴木、Ｑ５鈴木」である。この組み合わせでは、ノードの共有がない。
【０１８６】
共通クエリグラフパターン生成部１２は、このようなインスタンスの種類の数「０」を求める。この数「０」がターゲット数である（図１９（ｂ））。
【０１８７】
（Ｐ１、Ｐ４の場合）
例えば、検索クエリグラフパターンＰ１、Ｐ４を使用した組の場合は、以下のようにする。
【０１８８】
次に、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の１つとからなる検索サブグラフの組み合わせを全て取得する。
【０１８９】
取得された組み合わせ８通り（＝４×２）の内、組「Ｑ４鈴木、Ｑ７鈴木」、組「Ｑ５鈴木、Ｑ７鈴木」、組「Ｑ８鈴木、Ｑ７鈴木」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:鈴木」のノード）を有する。また、組「Ｑ１佐藤、Ｑ３佐藤」は、２つ以上の検索サブグラフに共有されるノード（インスタンス「Person:佐藤」のノード）を有する。
【０１９０】
共通クエリグラフパターン生成部１２は、このようなインスタンス「Person:鈴木」、「Person:佐藤」のようなインスタンスの種類の数「２」を求める。この数「２」がターゲット数である（図１９（ｂ））。
【０１９１】
なお、詳細説明は略すが、共通クエリグラフパターン生成部１２は、他の１３通りの組み合わせについても、同様にターゲットリソース数を算出する。
【０１９２】
次に、共通クエリグラフパターン生成部１２は、ターゲット数の最大値Ｔを算出する。例えば、ターゲット数の最大値Ｔは、「３」であることとする。
【０１９３】
次に、共通クエリグラフパターン生成部１２では、最大値Ｔに比率ＴＵを掛け、結果として、数値「２．４」が得られる。
【０１９４】
また、共通クエリグラフパターン生成部１２では、最大値Ｔに比率ＴＬを掛け、結果として、数値「１．５」が得られる。
【０１９５】
次に、共通クエリグラフパターン生成部１２では、数値「２．４」より大きい最小の整数「３」を求める。
【０１９６】
また、共通クエリグラフパターン生成部１２では、数値「１．５」より大きい最小の整数「２」を求める。
【０１９７】
次に、共通クエリグラフパターン生成部１２では、まず、検索クエリグラフパターンＰ１、Ｐ１を使用した組のターゲット数「１」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲット数「１」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、残りの３つの内の１つとからなる検索サブグラフの組み合わせを除外する。
【０１９８】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ４、Ｐ４を使用した組のターゲット数「０」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲット数「０」が整数「３」未満且つ整数「２」以上ではないので、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の組み合わせを除外する。
【０１９９】
同様に、共通クエリグラフパターン生成部１２では、検索クエリグラフパターンＰ１、Ｐ４を使用した組のターゲット数「２」が整数「３」未満且つ整数「２」以上か否かを判定し、ターゲット数「２」が整数「３」未満且つ整数「２」以上なので、検索クエリグラフパターンＰ１から取得された検索サブグラフＱ１、Ｑ４、Ｑ５、Ｑ８の１つと、検索クエリグラフパターンＰ４から取得された検索サブグラフＱ３、Ｑ７の１つとからなる検索サブグラフの組み合わせを除外せずに残す。
【０２００】
なお、詳細説明は略すが、共通クエリグラフパターン生成部１２は、他の１３通りの組み合わせについても、同様に検索サブグラフの組み合わせを除外するか否かを判定し、該当する場合は当該検索サブグラフの組み合わせを除外する。
【０２０１】
以下の工程は第１の実施の形態などのものと同様であり重複となるので説明を省略する。
【０２０２】
なお、数値「２．４」より大きい最小の整数「３」や、数値「１．５」より大きい最小の整数「２」は、閾値でり、かかる閾値を求めるには、第６の実施の形態と同様に、例えば、ターゲット数を降順にプロットしたグラフを生成し、該グラフの微分値をプロットしたグラフを生成し、該グラフの極値に対応するターゲット数ＴＰから閾値を選択してもよい。
【０２０３】
したがって、第７の実施の形態における共通クエリグラフパターン生成装置によれば、検索クエリグラフパターンを生成し（Ｓ５）、生成された検索クエリグラフパターンにマッチする検索サブグラフをグラフ構造データベースから取得し（Ｓ７）、生成された複数の検索クエリグラフパターンの１つ以上を合計で２回以上使用して組み合わせた当該各組み合わせ（上記例では１６通りの各組み合わせ）について、組み合わせ内の各検索クエリグラフパターンから取得された検索サブグラフを組み合わせ、組み合わせ後の検索サブグラフの集合から２つ以上の検索サブグラフに共有されるノードを検出し、該各ノードに含まれるインスタンスの種類の数であるターゲット数を求め（上記例では、検索クエリグラフパターンＰ１、Ｐ１を使用した組、検索クエリグラフパターンＰ４、Ｐ４を使用した組、検索クエリグラフパターンＰ１、Ｐ４を使用した組についてのターゲット数の例を示した。）、所定の範囲に属するターゲット数（上記例では、「３」未満且つ「２」以上の範囲）に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフの２つ以上を組み合わせ、組み合わせ後の検索サブグラフ内の所定のノード名およびプロパティ名を変数とした共通クエリグラフパターンを生成する（Ｓ９）ので、共通クエリグラフパターンの数を低減することができる。
【０２０４】
また、第６の実施の形態と同様に、ターゲット数の上限を設定することは、単にグラフ構造データベース３０を見ただけでは分かりにくい共通性の発見に貢献することができる。
【０２０５】
さて、第１の実施の形態では、「比率Ｒで定まる範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外する」構成（構成１という）を説明した。
【０２０６】
また、第２の実施の形態では、「比率ＲＵ、ＲＬで定まる範囲に属さない検索サブグラフの数に対応する検索サブグラフを除外する」構成（構成２という）を説明した。
【０２０７】
また、第３の実施の形態では、「比率Ｓで定まる範囲に属さないノードの種類の数に対応する検索サブグラフを除外する」構成（構成３という）を説明した。
【０２０８】
また、第４の実施の形態では、「比率ＳＵ、ＳＬで定まる範囲に属さないノードの種類の数に対応する検索サブグラフを除外する」構成（構成４という）を説明した。
【０２０９】
また、第５の実施の形態では、「最小数ＭＩＮ以上且つ最大数ＭＡＸ以下の範囲に属する数の検索サブグラフを組み合わせる」構成（構成５という）を説明した。
【０２１０】
また、第６の実施の形態では、「比率ＫＵ、ＫＬで定まる範囲に属するターゲットリソース数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフを組み合わせる」構成（構成６という）を説明した。
【０２１１】
また、第７の実施の形態では、「比率ＴＵ、ＴＬで定まる範囲に属するターゲット数に対応する組み合わせ内の検索クエリグラフパターンから取得された検索サブグラフを組み合わせる」構成（構成７という）を説明した。
【０２１２】
これら各構成１〜７は、他の構成とは別に単独で実施できる他、構成１〜４の１つと構成５の組み合わせ、構成５と構成６〜７の１つの組み合わせ、構成１〜４の１つと構成６〜７の１つの組み合わせ、構成１〜４の１つと構成５と構成６〜７の１つの組み合わせ、のように組み合わせて実施することができる。
【０２１３】
なお、本実施の形態に係る共通クエリグラフパターン生成装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【０２１４】
１…検索システム
１０…検索装置
１１…入力用ＧＵＩ生成部
１２…共通クエリグラフパターン生成部
１３…共通クエリグラフパターン蓄積部
１４…出力用ＧＵＩ生成部
２０…ユーザ端末
３０…グラフ構造データベース
４０…オントロジデータベース
【図１】
2011100206.tif 000003
【図２】
2011100206.tif 000004
【図３】
2011100206.tif 000005
【図４】
2011100206.tif 000006
【図５】
2011100206.tif 000007
【図６】
2011100206.tif 000008
【図７】
2011100206.tif 000009
【図８】
2011100206.tif 000010
【図９】
2011100206.tif 000011
【図１０】
2011100206.tif 000012
【図１１】
2011100206.tif 000013
【図１２】
2011100206.tif 000014
【図１３】
2011100206.tif 000015
【図１４】
2011100206.tif 000016
【図１５】
2011100206.tif 000017
【図１６】
2011100206.tif 000018
【図１７】
2011100206.tif 000019
【図１８】
2011100206.tif 000020
【図１９】
2011100206.tif 000021