(57)【要約】【課題】周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援すること。【解決手段】  検索装置１００は、パストライを表示して出力ノードと制約ノードが指定された場合に、各ノードの絶対パスから共通接頭辞を判定してクエリの分岐点を判定する。そして、検索装置１００は、出力ノードと制約ノードから複数のクエリを生成可能な場合には、分岐点を基にして必要最低限に拡張したパストライを生成し、各クエリの違いがユーザにわかるように表示して、最適なクエリを選択させるので、周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援することが出来る。【選択図】図１３
2010211540.tif 000002
【特許請求の範囲】
【請求項１】
項目要素と値要素で構成され、項目要素間あるいは項目要素と値要素の関係が木構造となる木構造データを対象として、コンピュータに木構造データの値要素を検索させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータに、
前記木構造データに存在する項目要素について、同一名称の親項目要素に直接関連づけられた同一名称の子項目要素が複数ある場合は一つの子項目要素に集約することで、該木構造データの項目要素間の関係を集約した集約構造情報を作成する準備機能と、
作成した前記集約構造情報を表示装置に出力し、特定の条件を満たす値要素を抽出する制約条件つき検索要求を受け付ける際に、最上位の項目要素から特定の条件に至るまでの項目要素の階層関係を示す条件階層情報、および、最上位の項目要素から抽出すべき値要素に至るまでの項目要素の階層関係を示す出力階層情報を受け付ける受付機能と、
前記条件階層情報と前記出力階層情報に共通する項目要素を特定して、特定した該項目要素が前記集約構造情報において同一名称でかつ同一の親項目要素に関連づけて集約された項目要素であるか否かを判定し、集約されたと判定した場合は、該項目要素が集約されたことを示す再集約構造情報を作成し表示装置に出力し、少なくとも条件階層情報あるいは出力階層情報のいずれかを再び受け付ける再受付機能
を実現させるためのプログラムを記録した記憶媒体。
【請求項２】
前記準備機能において、前記コンピュータが、同一名称でかつ同一の親項目要素に直接関連づけられた複数の同一名称の子項目要素を集約した場合は、該項目要素を集約したことを示す識別情報、または、集約された項目要素の集約数を記録し、前記再受付機能において、前記識別情報または前記集約数を参照することで集約された項目要素であるか否かを判定することを特徴とする請求項１に記載の記憶媒体。
【請求項３】
前記再受付機能において、前記コンピュータが、前記特定した項目要素が関連づけられた前記親項目要素から分岐した条件階層情報と出力階層情報に対応する項目要素を表示する再集約構造情報を作成することを特徴とする請求項２に記載の記憶媒体。
【請求項４】
項目要素と値要素で構成され、項目要素間あるいは項目要素と値要素の関係が木構造となる木構造データから値要素を検索する検索装置が、
前記木構造データに存在する項目要素について、同一名称の親項目要素に直接関連づけられた同一名称の子項目要素が複数ある場合は一つの子項目要素に集約することで、該木構造データの項目要素間の関係を集約した集約構造情報を作成する準備ステップと、
作成した前記集約構造情報を表示装置に出力し、特定の条件を満たす値要素を抽出する制約条件つき検索要求を受け付ける際に、最上位の項目要素から特定の条件に至るまでの項目要素の階層関係を示す条件階層情報、および、最上位の項目要素から抽出すべき値要素に至るまでの項目要素の階層関係を示す出力階層情報を受け付ける受付ステップと、
前記条件階層情報と前記出力階層情報に共通する項目要素を特定して、特定した該項目要素が前記集約構造情報において同一名称でかつ同一の親項目要素に関連づけて集約された項目要素であるか否かを判定し、集約されたと判定した場合は、該項目要素が集約されたことを示す再集約構造情報を作成し表示装置に出力し、少なくとも条件階層情報あるいは出力階層情報のいずれかを再び受け付ける再受付ステップ
を含んだことを特徴とする検索方法。
【請求項５】
前記準備ステップにおいて、前記検索装置が、同一名称でかつ同一の親項目要素に直接関連づけられた複数の同一名称の子項目要素を集約した場合は、該項目要素を集約したことを示す識別情報、または、集約された項目要素の集約数を記録し、前記再受付ステップにおいて、前記識別情報または前記集約数を参照することで集約された項目要素であるか否かを判定することを特徴とする請求項４に記載の検索方法。
【請求項６】
前記再受付ステップにおいて、前記検索装置が、前記特定した項目要素が関連づけられた前記親項目要素から分岐した条件階層情報と出力階層情報に対応する項目要素を表示する再集約構造情報を作成することを特徴とする請求項５に記載の検索方法。
【請求項７】
項目要素と値要素で構成され、項目要素間あるいは項目要素と値要素の関係が木構造となる木構造データから値要素を検索する検索装置であって、
前記木構造データに存在する項目要素について、同一名称の親項目要素に直接関連づけられた同一名称の子項目要素が複数ある場合は一つの子項目要素に集約することで、該木構造データの項目要素間の関係を集約した集約構造情報を作成する準備部と、
作成した前記集約構造情報を表示装置に出力し、特定の条件を満たす値要素を抽出する制約条件つき検索要求を受け付ける際に、最上位の項目要素から特定の条件に至るまでの項目要素の階層関係を示す条件階層情報、および、最上位の項目要素から抽出すべき値要素に至るまでの項目要素の階層関係を示す出力階層情報を受け付ける受付部と、
前記条件階層情報と前記出力階層情報に共通する項目要素を特定して、特定した該項目要素が前記集約構造情報において同一名称でかつ同一の親項目要素に関連づけて集約された項目要素であるか否かを判定し、集約されたと判定した場合は、該項目要素が集約されたことを示す再集約構造情報を作成し表示装置に出力し、少なくとも条件階層情報あるいは出力階層情報のいずれかを再び受け付ける再受付部
を備えたことを特徴とする検索装置。
【請求項８】
前記準備部は、同一名称でかつ同一の親項目要素に直接関連づけられた複数の同一名称の子項目要素を集約した場合は、該項目要素を集約したことを示す識別情報、または、集約された項目要素の集約数を記録し、前記再受付部は、前記識別情報または前記集約数を参照することで集約された項目要素であるか否かを判定することを特徴とする請求項７に記載の検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半構造体データからデータを検索する検索装置等に関する。
【背景技術】
【０００２】
近年、コンピュータで処理される文書データとして、ＸＭＬ（Extensible  Markup  Language）等のマークアップ言語が利用されている。このＸＭＬは、異なる情報システムの間で、特にインターネットを介して、構造化された文書や構造化されたデータの共有を容易にすることができるため、コンピュータにおいてますます多用されてきている。以下、ＸＭＬに基づいて記述された階層構造をなす文書データをＸＭＬデータと表記する。
【０００３】
そして、ＸＭＬデータから所望のデータを検出するものとして、ＸＰａｔｈ（XML  Path  Language）クエリが用いられる。このＸＰａｔｈクエリは、ＸＭＬデータのための標準クエリ言語であり、ＸＭＬの複雑な木構造に対して条件式を記述する能力を持つ。以下の説明において、ＸＰａｔｈクエリを単にクエリと表記する。
【０００４】
ここで、ワードプロセッサ等の分野であれば、ユーザがデータを検索する場合に、自然言語を検索条件として入力すればよく、ユーザはデータ検索を容易に行うことができる（例えば、特許文献１参照）。しかし、ＸＭＬデータからデータを検索する場合には、クエリを条件式で指定する必要があるため、クエリに関する専門知識が無ければ容易にＸＭＬデータのデータ検索を実行することが出来なかった。
【０００５】
そこで、ＸＭＬデータの階層構造を集約した集約構造を画面上に表示し、ユーザが、画面上の集約構造に基づきクエリの検索条件を指定することで、クエリの条件式を自動生成する技術が考案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１９６２７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように、集約構造を画面上に表示し、ユーザが画面上の集約構造に基づいてクエリの検索条件を指定する手法は、直感的で容易である。しかし、かかる手法では、単純な検索条件を指定することは出来ても、制約条件付きの検索条件を指定することが出来ないという問題があった。
【０００８】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援することが出来る記憶媒体、検索方法および検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、この記憶媒体は、項目要素と値要素で構成され、項目要素間あるいは項目要素と値要素の関係が木構造となる木構造データを対象として、コンピュータに木構造データの値要素を検索させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体であって、前記コンピュータに、前記木構造データに存在する項目要素について、同一名称の親項目要素に直接関連づけられた同一名称の子項目要素が複数ある場合は一つの子項目要素に集約することで、該木構造データの項目要素間の関係を集約した集約構造情報を作成する準備機能と、作成した前記集約構造情報を表示装置に出力し、特定の条件を満たす値要素を抽出する制約条件つき検索要求を受け付ける際に、最上位の項目要素から特定の条件に至るまでの項目要素の階層関係を示す条件階層情報、および、最上位の項目要素から抽出すべき値要素に至るまでの項目要素の階層関係を示す出力階層情報を受け付ける受付機能と、前記条件階層情報と前記出力階層情報に共通する項目要素を特定して、特定した該項目要素が前記集約構造情報において同一名称でかつ同一の親項目要素に関連づけて集約された項目要素であるか否かを判定し、集約されたと判定した場合は、該項目要素が集約されたことを示す再集約構造情報を作成し表示装置に出力し、少なくとも条件階層情報あるいは出力階層情報のいずれかを再び受け付ける再受付機能を実現させる。
【発明の効果】
【００１０】
この記憶媒体に記憶されたプログラムをコンピュータが実行することで、周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援することが出来る。
【図面の簡単な説明】
【００１１】
【図１】図１は、ＸＭＬデータの一例を示す図である。
【図２】図２は、ＸＭＬデータの木表現の一例を示す図である。
【図３】図３は、木の用語を補足説明するための図である。
【図４】図４は、クエリの指定箇所を説明するための図（１）である。
【図５】図５は、クエリの指定箇所を説明するための図（２）である。
【図６】図６は、パストライのデータ構造の一例を示す図である。
【図７】図７は、従来技術の問題点を説明するための図である。
【図８】図８は、分岐点判別を説明するための図である。
【図９】図９は、兄弟数出現つきのパストライを示す図である。
【図１０】図１０は、拡張したパストライの一例を示す図である。
【図１１】図１１は、クエリQ4の指定位置を示すパストライを示す図である。
【図１２】図１２は、クエリQ3の指定位置を示すパストライを示す図である。
【図１３】図１３は、本実施例にかかる検索装置の構成を示す図である。
【図１４】図１４は、パストライノード構造体のデータ構造の一例を示す図である。
【図１５】図１５は、パストライを各パストライノード構造体で示した図である。
【図１６】図１６は、クエリ生成テーブルのデータ構造の一例を示す図である。
【図１７】図１７は、クエリ木構造体のデータ構造の一例を示す図である。
【図１８】図１８は、クエリを各クエリ木構造体で示した図（１）である。
【図１９】図１９は、クエリを各クエリ木構造体で示した図（２）である。
【図２０】図２０は、クエリ指定受付部の処理を説明するための図（１）である。
【図２１】図２１は、クエリ指定受付部の処理を説明するための図（２）である。
【図２２】図２２は、分岐点判定処理部の処理を説明するための図である。
【図２３】図２３は、絶対パスから生成されるクエリ木の一例を示す図である。
【図２４】図２４は、クエリ表示処理部の処理を説明するための図である。
【図２５】図２５は、本実施例にかかる検索装置の処理手順を示すフローチャートである。
【図２６】図２６は、パストライ生成処理の処理手順を示すフローチャートである。
【図２７】図２７は、パス登録処理の処理手順を示すフローチャートである。
【図２８】図２８は、兄弟出現数計数処理の処理手順を示すフローチャートである。
【図２９】図２９は、分岐点判定処理の処理手順を示すフローチャートである。
【図３０】図３０は、クエリ生成処理の処理手順を示すフローチャートである。
【図３１】図３１は、クエリ表示処理の処理手順を示すフローチャートである。
【図３２】図３２は、実施例に示した検索装置に対応するコンピュータのハードウェア構成を示す図である。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、この発明に係る記憶媒体、検索方法および検索装置の実施例を詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１３】
まず、本実施例で使用するＸＭＬ（Extensible  Markup  Language）データについて説明する。図１は、ＸＭＬデータの一例を示す図である。同図に示すように、このＸＭＬデータは、要素識別子「＜」、「＜／」等により要素が区切られた階層構造を有している。そして、図１のＸＭＬデータの木表現は、図２のように表すことが出来る。
【００１４】
図２は、ＸＭＬデータの木表現の一例を示す図である。図２に示すように、ＸＭＬの木構造では、ＸＭＬデータはノードＩＤ１，３，４，６，７，９，１０，１２，１３，１５，１６，１８，１９，２１，２２，２４，２５の要素ノードと、ノードＩＤ２，５，８，１１，１４，１７，２０，２３，２６のテキストノードを有している。
【００１５】
以下では、ノードＩＤがnであり、要素名がelemであるような要素ノードを、elemnと表記する。例えば、Syain１は、ノードＩＤが１で要素名がSyainである要素ノードを表す。また、ACT３、１２、２１のように表記する場合は、ノードＩＤがそれぞれ３、１２、２１であるような３つの要素ノード（いずれの要素名もACT）を表すものとする。
【００１６】
そして、ＸＭＬデータは、それぞれの要素ノード、テキストノードをそれぞれ接続している。例えば、要素ノードのSyain１は、テキストノードの「シグマ戦隊中原ジャー」２、要素ノードのACT３，１２，２１に接続されている。このように、ＸＭＬデータに代表される半構造データは、項目間や項目・値間の関係が木構造として表現可能なデータである。なお、項目は、要素ノードに対応し、値はテキストノードに対応する。
【００１７】
本実施例において、図２に示した木構造に含まれる各ノードの説明をする場合に、根ノード、親ノード、子供ノード、兄ノード、弟ノード、先祖ノード、子孫ノードというような用語を用いる場合がある。図３は、木の用語を補足説明するための図である。図３に示すように、木を構成する各ノードのうち、最上層に位置するノードを根ノードと定義する。また、基準ノードのひとつ上の層に存在し、基準ノードに接続されたノードを、基準ノードに対する親ノード（以下、単に親ノード）と定義する。また、基準ノードのひとつ下の層に存在し、基準ノードに接続されたノードを基準ノードに対する子供ノード（以下、単に子供ノード）と定義する。
【００１８】
また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの左側に存在するノードを、基準ノードに対する兄ノード（以下、単に兄ノード）と定義する。また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの右側に存在するノードを、基準ノードに対する弟ノード（以下、単に弟ノード）と定義する。また、根ノードから親ノードに至るパスに存在する各ノードをまとめて先祖ノードと定義する。また、基準ノードの配下に接続された各ノードをまとめて子孫ノードと定義する。
【００１９】
例えば、図２において、基準ノードをchara１５とした場合の根ノードは、Syain１となり、親ノードは、ACT１２となり、兄ノードは、id１３となり、弟ノードは、cast１８となり、子供ノードは、name１６となる。また、基準ノードをchara１５とした場合の先祖ノードは、Syain１、ACT１２となり、子孫ノードは、name１６、シグマブルー１７となる。
【００２０】
上述したＸＭＬデータに対して、クエリを指定することによって、クエリの照合位置のデータをＸＭＬデータから検出することが可能となる。なお、Ｗ３Ｃ（World  Wide  Web  Consortium）によるクエリのサブセットは下記のように定義される。
Path::="/"RPath
RPath::=Step("/"Step)*
Step::=Axis"::"Ntest("["Pred"]")＊
Axis::="child"
Ntest::=tagname|"*"|"text()"|"node()"
Pred::=Expr|"not"Expr
Expr::=RPath|1_func"("RPath")"|n_func"("RPath(","const)+")"
ここで、tagname∈Tag（Tagは、タグ名の集合）とする。また、1_funcは、データ節点Ｖ
から｛０，１｝への一変数関数である。同様に、n_funcは、｛０，１｝を返す任意のｎ変数関数であるが、第一引数以外は定数のみを入力するものとする。定数「const」は、任意の文字列または数値を表す。
【００２１】
図４、５は、クエリの指定箇所を説明するための図である。図４は、クエリが、
Q1=/Syain/ACT[chara/name="シグマブルー"]/cast/name
と指定された場合の指定箇所を示している。クエリ「Q1=/Syain/ACT[chara/name="シグマブルー"]/cast/name」の意味は、/Syain/ACT/cast/nameで指定される要素のうち、ACTから分岐したパスchara/nameの値が「シグマブルー」に一致するものを全て回答せよという意味である。
【００２２】
従って、図４に示すように、クエリ「Q1=/Syain/ACT[chara/name="シグマブルー"]/cast/name」の指定箇所は、name１９となり、「<name>多湖真一郎</name>」が検索結果として出力される。なお、上記クエリの[]は制約条件を表し、例えば、ACT[chara/name="シグマブルー"]は、配下にchara/name="シグマブルー"を有するACTを表す。このように、クエリに制約条件を付与することで、ＸＭＬデータ上の検索対象をより絞り込むことが出来る。
【００２３】
図５は、クエリが、
Q2=/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name
と指定された場合の指定箇所を示している。クエリ「Q2=/Syain[ACT/chara/name="シグマブルー"]/cast/name」の意味は、/Syain/ACT/cast/nameで指定される要素のうち、Syainから分岐したパスACT/cast/nameの値が「シグマブルー」に一致するものを全て回答せよという意味である。
【００２４】
従って、図５に示すように、クエリ「Q2=/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」の指定箇所は、name１０，１９，２５となり、「<name>浅井達哉</name>」、「<name>多湖真一郎</name>」、「<name>永田真彦</name>」が検索結果として出力される。なお、上記クエリの[]は制約条件を表し、例えば、Syain[ACT/chara/name="シグマブルー"]は、配下にACT/chara/name="シグマブルー"を有するSyainを表す。
【００２５】
上述したように、クエリの条件式を指定することで、ＸＭＬデータから所望のデータを検索することが可能である。しかし、クエリの条件式を指定する場合には、木構造、出力ノード、制約条件の集合を組合せる必要があり、クエリの作成作業が大変難しい。かかる問題を解消すべく、背景技術でも述べたとおり、クエリの検索条件を自動生成する技術として、「oXygen」と呼ばれる技術が考案されている。
【００２６】
ここで、「oXygen」の概要について説明する。以下の説明において、「oXygen」と呼ばれる技術を単に従来技術と表記する。従来技術では、まず、ＸＭＬデータの階層構造を集約した集約構造を生成する。例えば、図２に示したＸＭＬデータの集約構造は、図６に示すものとなる。以下の説明において、集約構造で示されたＸＭＬデータをパストライと表記する。図６は、パストライのデータ構造の一例を示す図である。
【００２７】
そして、従来技術では、パストライを画面上に表示し、出力ノードをユーザに指定させる。ここで、出力ノードは、抽出すべき値（テキストノード）に接続されたノードを示す。図６において、castの配下に接続されたnameが出力ノードとしてユーザに指定された場合には、根ノードのSyainから、指定されたnameに至るまでの各ノードを順にクエリの条件式として追加することで、クエリ
Q=/Syain/ACT/cast/name
を作成する。
【００２８】
しかし、従来技術では、制約条件を一つも持たないような、一番単純なタイプのクエリしか作成することができなかった。すなわち、従来技術では、図４および図５で説明したような制約条件を含むクエリQ1、Q2を作成することができない。
【００２９】
なお、仮に図６に示したパストライを用いて出力ノードと制約ノード（制約条件に含まれるノードうち最下層のノード）をユーザに指定させ、制約条件を有するクエリを作成することも考えられる。しかし、従来技術では、パストライ上で出力ノードと制約ノードを指定すると、指定された条件から複数のクエリが生成され、いずれのクエリが適切なクエリであるかを判定することが出来ない。
【００３０】
図７は、従来技術の問題点を説明するための図である。図７に示す例では、出力ノードとして、castの配下に接続されたnameを指定し、制約ノードとして、charaの配下に接続されたnameが指定した場合を示している。図７に示すように、出力ノードと制約ノードが指定された場合には、複数のクエリが考えられ、具体的には
Q3=/Syain/ACT[chara/name="シグマブルー"]/cast/name
Q4=/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name
がクエリの候補となる。
【００３１】
しかし、クエリQ3、Q4とも、根ノードから出力ノードへのパスは、/Syain/ACT/cast/nameであり、根ノードから制約ノードへのパスは、/Syain/ACT/chara/nameとなる。従って、図７に示したパストライ上で各クエリを差別化できず、どちらのクエリが適切なクエリなのかを判定できない。
【００３２】
図７で説明したように、パストライ上では、クエリQ3、Q4とも同一のノードを示している。しかし、パストライはあくまで便宜的にＸＭＬデータを集約したデータに過ぎないので、実際のＸＭＬデータ上でクエリQ3、Q4を指定すると、クエリQ3、Q4では、異なった検索結果がそれぞれ出力されてしまう。
【００３３】
具体的に、クエリ「Q3=/Syain/ACT[chara/name="シグマブルー"]/cast/name」を指定して、図２に示したＸＭＬデータからデータ検索を行うと、name１９がヒットし、「<name>多湖真一郎</name>」が回答される。一方、クエリ「Q4=/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」を指定して、図２に示したＸＭＬデータからデータ検索を行うと、name１０、１９、２５にヒットし、「<name>浅井達哉</name>」、「<name>多湖真一郎</name>」、「<name>永田真彦</name>」が回答される。
【００３４】
このように、図７に示したパストライ上では各クエリが同一のノードを示す場合であっても、実際のＸＭＬデータ上では異なるノードを示すクエリとなっている。従って、パストライ上で複数のクエリが成り立つ場合には、どのクエリが適切なクエリであるかを判断することが重要なポイントとなる。
【００３５】
かかる問題点を解消するためには、パストライを生成することなく、図２に示すようなＸＭＬデータをそのまま表示して、ユーザに出力ノードと制約ノードを指定させればクエリは一通りしか作成されず、上述した問題を解消することが可能ではある。しかし、実際のＸＭＬデータは複雑な構造をしているため、ＸＭＬデータをそのまま表示して、出力ノードと制約ノードを指定する方法ではユーザに負担が増加してしまう。
【００３６】
そこで、パストライ上で複数のクエリが生成される場合には、ＸＭＬデータをそのまま表示するのでは無く、各クエリを区別できる最小限の集約構造をパストライとして表示できれば、ユーザにかかる負担を軽減させつつ、適切なクエリを生成することが可能となる。
【００３７】
ここで、クエリQ3とクエリQ4とを比較すると、各クエリは枝分かれ構造における「分岐点」が異なる。具体的に、クエリQ3は、ACTの直後に制約条件が付加されているので、ACTの位置が分岐点となっており、クエリQ4は、Syainの直後に制約条件が付加されているので、Syainの位置が分岐点となっている。従って、かかる分岐点を利用してパストライ上で各クエリを差別化できれば、パストライ上で、最適なクエリを生成することが出来る。
【００３８】
また、パストライ上に分岐点がｎ（ｎは自然数）個ある場合には、実際のＸＭＬ上に該当する分岐点が存在するかを判定することが重要となる。パストライ上の分岐点（分岐点候補）は、根ノードから出力ノードに至るパスと、根ノードから制約ノードに至るパスに共通するノード（共通接頭辞）となる。図８は、分岐点判別を説明するための図である。図８の左側には、ＸＭＬデータの木構造を示し、図８の右側には、左側のＸＭＬデータに対応するパストライを示している。
【００３９】
図８のパストライにおいて、出力ノードをＦ、制約ノードをＥとすると、共通接頭辞は、ノードＡ，Ｂ，Ｃ，Ｄとなるので、分岐点候補はノードＡ、Ｂ、Ｃ、Ｄとなる。しかし、ＸＭＬデータとパストライを比較すると、分岐点は実際にノードＡ，Ｂしか存在しないことがわかる。従って、パストライ上に存在する各分岐点候補の内、実際の分岐点を判定し、判定した分岐点に基づいて、クエリを差別化すればよい。
【００４０】
次に、本実施例にかかる検索装置の概要について説明する。本実施例にかかる検索装置は、パストライ構築時に、各ノードの兄弟の最大出現数を登録しておく。図９は、兄弟数出現つきのパストライを示す図である。図９に示すパストライは、図２に示したＸＭＬデータのパストライである。
【００４１】
図９に示すように、本実施例にかかるパストライは、各ノードに兄弟の最大出現数が関連づけられている。図２を参照すると、ACTは、Syainの子供ノードとして、兄弟中で３回繰り返し出現しているので、最大出現数が「３」となっている。その他のノードは、それぞれの兄弟において最大１回しか出現しないので、最大出現数が「１」となっている。
【００４２】
続いて、検索装置は、パストライ上で、出力ノードと制約ノードが指定された場合に、指定された条件を満たすクエリを作成する。そして、検索装置は、出力パスと制約パスの共通接頭辞に含まれるノードを分岐点候補として判定する。なお、出力パスは、根ノードから出力ノードまでのパスであり、制約パスは、根ノードから制約ノードまでのパスである。
【００４３】
具体的に、図９において、出力ノードをcastの配下に接続されたnameとすると、出力パスは、/Syain/ACT/cast/nameとなる。また、制約ノードをcharaの配下に接続されたnameとすると、制約パスは、/Syain/ACT/chara/nameとなる。そして、指定された条件を満たすクエリは、
Q3=/Syain/ACT[chara/name="シグマブルー"]/cast/name
Q4=/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name
となる。また、出力ノードと制約ノードを比較すると、分岐点候補となるノードは、Syain、ACTとなる。
【００４４】
続いて、検索装置は、分岐点判別ルールを適用して、分岐点を判定する。分岐点判別ルールは、２つ存在する。第１のルールは、各分岐点候補のうち、最下の分岐点候補を分岐点として判定する。第２のルールは、分岐点候補のうち、子供ノードの兄弟の最大出現数が２以上の分岐点候補を分岐点と判定する。上記のように、分岐点候補がSyain、ACTとなる場合には、ACTが第１のルールに該当するので、ACTが分岐点となる。また、Syainは、第２のルールに該当するので分岐点なる。
【００４５】
そして、検索装置は、クエリの分岐点に基づいて、パストライを拡張する。例えば、Syainで分岐するクエリQ4の指定位置をパストライ上に表示する場合には、Syainの配下に接続された部分木を図１０に示すように拡張する。図１０は、拡張したパストライの一例を示す図である。図１０に示すように、パストライを拡張した後に、検索装置は、クエリQ4の指定位置をパストライ上に表示する。図１１は、クエリQ4の指定位置を示すパストライを示す図である。
【００４６】
また、ACTで分岐するクエリQ4の指定位置をパストライ上に表示する場合には、ACTの配下に接続された部分木を拡張する。しかし、パストライ上ではACTを起点として出力ノードへのパスと制約ノードへのパスが既にcharaとcastに分岐している。このような場合には、検索装置は、パストライを拡張することなく、クエリの指定箇所を表示する。図１２は、クエリQ3の指定位置を表すパストライを示す図である。
【００４７】
図１１と図１２に示したパストライとクエリを表示させれば、ユーザは、各クエリの違いを容易に判断することができる。すなわち、ユーザは、出力ノードと制約ノードを指定した後に、検索装置から表示される各クエリの候補を選択するだけで、所望するクエリを利用することができる。検索装置は、ユーザによって何れかのクエリが選択された場合には、選択されたクエリに対応するデータをＸＭＬデータから検索し、検索結果を出力する。
【００４８】
このように、本実施例にかかる検索装置は、ユーザに指定される出力ノードと制約ノードに基づいて、該当するクエリが複数存在する場合には、必要最低限、パストライを拡張し、各クエリの差別化を図り、ユーザに最適なクエリを選択させるので、周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援することが出来る。
【００４９】
次に、本実施例にかかる検索装置の構成について説明する。図１３は、本実施例にかかる検索装置の構成を示す図である。図１３に示すように、この検索装置１００は、入力部１１０と、出力部１２０と、入出力制御部１３０と、記憶部１４０と、制御部１５０を有する。
【００５０】
このうち、入力部１１０は、出力ノード、制御ノード等の各種の情報を入力する入力部であり、キーボードやマウス、マイク等に該当する。出力部１２０は、クエリ、ＸＭＬデータ、パストライ、検索結果等の各種の情報を出力する出力部であり、モニタ（若しくはディスプレイ、タッチパネル）に該当する。入出力制御部１３０は、入力部１１０、出力部１２０、記憶部１４０、制御部１５０によるデータの入出力を制御する処理部である。
【００５１】
記憶部１４０は、制御部１５０による各種処理に必要なデータおよびプログラムを記憶する記憶部である。この記憶部１４０は、ＸＭＬデータ１４０ａと、パストライ１４０ｂと、クエリ作成テーブル１４０ｃと、クエリ木１４０ｄを有する。
【００５２】
このうち、ＸＭＬデータ１４０ａは、上述したように要素識別子「＜」、「＜／」等により要素が区切られた階層構造を有する文書データである（図１参照）。また、ＸＭＬデータ１４０ａのデータ構造は、図１に示したものに限らず、図２で説明したような木構造で表すことも出来る。パストライ１４０ｂは、上述したようにＸＭＬデータを集約したデータである（図６参照）。
【００５３】
なお、パストライ１４０ｂは、複数のパストライノード構造体を相互に接続している。図１４は、パストライノード構造体のデータ構造の一例を示す図である。図１４に示すように、このパストライノード構造体は、タグ名、絶対パス名、絶対パスを識別する絶対パスＩＤ、最大兄弟数、兄弟数カウンタ、親ノードへのポインタ、子供ノードへのポインタリストを有する。
【００５４】
例えば、図６に示したパストライのACTに該当するパストライノード構造体の場合には、タグ名「ACT」、絶対パス名「/Syain/ACT」、絶対パスＩＤ「２」となる。また、親ノードへのポインタは、タグ名「Syain」のパストライノード構造体に接続されている。また、子供ノードへのポインタはそれぞれ、タグ名「id」、「chara」、「cast」のパストライノード構造体に接続されている。
【００５５】
ここで、図６に示したパストライを複数のパストライノード構造体で示すと、図１５に示す構造となる。図１５は、パストライを各パストライノード構造体で示した図である。なお、図１５に示す各パストライノード構造体では、便宜上、最大兄弟数、兄弟数カウンタを省略している。
【００５６】
クエリ生成テーブルは、上述した出力ノード、制約ノード、分岐点に対応する絶対パス等を管理するテーブルである。図１６は、クエリ生成テーブル１４０ｃのデータ構造の一例を示す図である。図１６に示すように、このクエリ生成テーブル１４０ｃは、出力ノード、制約ノード、分岐点のノードを識別する種別と、絶対パスと、演算子と、値をそれぞれ対応付けて記憶している。
【００５７】
クエリ木１４０ｄは、出力ノードおよび制約ノードが指定されることで、制御部１５０により生成されるクエリの木構造データである。複数のクエリが生成された場合には、かかるクエリ木１４０ｄは、複数のクエリに対応するクエリ木をそれぞれ有しているものとする。クエリ木は、複数のクエリ木構造体を相互に接続している。図１７は、クエリ木構造体のデータ構造の一例を示す図である。図１７に示すように、このクエリ木構造体は、タグ名と、分岐用ポインタと、子供用ポインタとを有する。
【００５８】
具体的に、クエリ「/Syain/ACT[chara/name="シグマブルー"]/cast/name」を、クエリ木構造体を用いて表すと、図１８に示す木構造となる。図１８は、クエリを各クエリ木構造体で示した図（１）である。クエリ「/Syain/ACT[chara/name="シグマブルー"]/cast/name」は、ACTの直後に制約条件が付与されているので、ACTが分岐点となっている。従って、図１８に示すように、ACTの分岐用ポインタに、charaのクエリ木構造体が接続されている。
【００５９】
一方、クエリ「/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」を、クエリ木構造体を用いて表すと、図１９に示す木構造となる。図１９は、クエリを各クエリ構造体で示した図（２）である。クエリ「/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」は、Syainの直後に制約条件が付与されているので、Syainが分岐点となっている。従って、図１９に示すように、Syainの分岐用ポインタにACTのクエリ木構造体が接続されている。
【００６０】
制御部１５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御部である。図１３に示すように、この制御部１５０は、パストライ生成部１５０ａ、兄弟出現数計数部１５０ｂ、データ構造表示部１５０ｃ、クエリ指定受付部１５０ｄ、分岐点判定処理部１５０ｅ、クエリ生成処理部１５０ｆ、クエリ表示処理部１５０ｇ、検索処理部１５０ｈを有する。
【００６１】
このうち、パストライ生成部１５０ａは、ＸＭＬデータ１４０ａ（図１、図２参照）を集約して、パストライ（例えば、図６、１４、１５参照）を作成する処理部である。具体的に、パストライ生成部１５０ａの処理を説明する。まず、パストライ生成部１５０ａは、ＸＭＬデータ１４０ａの木構造データに存在する要素ノードについて、同一タグ名の親ノードに直接関連づけられた同一タグ名の子供ノードが複数存在するか否かを判定する。
【００６２】
そして、パストライ生成部１５０ａは、同一タグ名の親ノードに直接関連づけられた同一タグ名の子供ノードが複数存在する場合には、重複する同一タグ名の親ノードおよび子供ノードを一つの親ノードおよび子供ノードに集約することで、パストライ１４０ｂを生成する。
【００６３】
例えば、図２に示すＸＭＬデータにおいて、同一タグ名の親ノードACTに直接関連づけられた同一タグ名の子供ノードid、chara、castが複数存在している。また、同一のタグ名の親ノードcharaに直接関連づけられた子供ノードnameが複数存在している。また、また、同一のタグ名の親ノードcastに直接関連づけられた子供ノードnameが複数存在している。
【００６４】
従って、パストライ生成部１５０ａは、ACT３、１２、２１を一つのACTに集約し、id４、１３、２２を一つのidに集約し、chara６、１５を一つのcharaに集約し、cast９、１８、２４を一つのcastに集約する。また、パストライ生成部１５０ａは、name７、１６、２５を一つのnameに集約し、name１０、１９を一つのnameに集約する。その結果、図２に示すＸＭＬデータ１４０ａは、図６等に示すパストライ１４０ｂに集約される。なお、この時点において、パストライ１４０ｂのパストライノード構造体に含まれる最大兄弟数および兄弟数カウンタは、Ｎｕｌｌとなっている。
【００６５】
兄弟出現数計数部１５０ｂは、パストライ１４０ｂに含まれる要素ノードと、ＸＭＬデータ１４０ａを基にして、パストライ１４０ｂの要素ノードに該当するＸＭＬデータの要素ノードの兄弟数を判定する処理部である。
【００６６】
具体的に、図２を用いて説明する。ＸＭＬデータ１４０ａの要素ノードSyainは、根ノードであるため、兄弟は存在しない。従って、兄弟出現数計数部１５０ｂは、パストライ１４０ｂにおいて、パストライノード構造体のタグ名Syainに該当する最大兄弟数を１に設定する。
【００６７】
兄弟出現数計数部１５０ｂは、要素ノードACTの兄弟数を判定する。図２を参照すると、同一親ノードに直接対応付けられた要素ノードACTが３つ存在するので、兄弟出現数計数部１５０ｂは、パストライ１４０ｂにおいて、パストライノード構造体のタグ名ACTに該当する最大兄弟数を３に設定する。
【００６８】
兄弟出現数計数部１５０ｂは、その他の要素ノードｉid、chara、cast、nameの兄弟数も判定する。いずれの要素ノードも兄弟は存在しないので、兄弟出現数計数部１５０ｂは、パストライ１４０ｂにおいて、パストライノード構造体のタグ名id、chara、cast、nameに該当する最大兄弟数を１に設定する。
【００６９】
データ構造表示部１５０ｃは、パストライ１４０ｂを出力部１２０に出力し、パストライ１４０ｂをモニタに出力させる処理部である。ユーザは、入力部１１０を操作して、モニタに表示されたパストライ１４０ｂを参照し、出力ノードおよび制約ノードを指定する。
【００７０】
クエリ指定受付部１５０ｄは、ユーザによって出力ノードおよび制約ノードを指定された場合に、クエリ生成テーブル１４０ｃに各種の情報を登録する処理部である。また、クエリ指定受付部１５０ｄは、演算子指定窓および値指定窓を出力部１２０に出力させる。ここで、演算子指定窓は、ユーザが「＝」や、部分一致などの演算子を入力する入力窓であり、値は、各種のテキスト（例えば、シグマブルー）を入力する入力窓である。
【００７１】
以下において、クエリ指定受付部１５０ｄの処理を具体的に説明する。図２０、２１は、クエリ指定受付部１５０ｄの処理を説明するための図である。なお、図２０、２１において、castに直接関連づけられたnameを出力ノードとして指定され、charaに直接関連づけられたnameを制約ノードとして指定される場合について説明するがこれに限定されるものではない。
【００７２】
図２０の上段に示すように、ユーザがcastに直接関連づけられたnameを出力ノードとして指定した場合には、クエリ指定受付部１５０ｄは、根ノードSyainから出力ノードnameに至るまでのタグ名を順に並べることで、絶対パス/Syain/ACT/cast/nameを生成する。ユーザに指定されたノードは出力ノードであるため、クエリ指定受付部１５０ｄは、種別「出力」と、絶対パス「/Syain/ACT/cast/name」を対応付けてクエリ生成テーブル１４０ｃに登録する。
【００７３】
図２０の下段に示すように、ユーザがcharaに直接関連づけられたnameを制約ノードとして指定した場合には、クエリ指定受付部１５０ｄは、根ノードSyainから制約ノードに至るまでのタグ名を順に並べることで、絶対パス/Syain/ACT/chara/nameを生成する。ユーザに指定されたノードは制約ノードであるため、クエリ指定受付部１５０ｄは、種別「制約」と、絶対パス「/Syain/ACT/chara/name」を対応付けてクエリ生成テーブル１４０ｃに登録する。
【００７４】
クエリ指定受付部１５０ｄは、出力ノードと制約ノードを受け付けた後に、演算子指定窓と値指定窓をモニタに表示する（図２１の上段参照）。ユーザは入力部１１０を操作して、演算子指定窓に演算子を入力し、値指定窓に値を入力する。
【００７５】
図２１の下段に示すように、ユーザが演算子指定窓に「＝」を入力し、値指定窓に「シグマブルー」を入力した場合には、クエリ指定受付部１５０ｄは、種別「制約」に対応して、演算子「＝」、値「シグマブルー」をクエリ生成テーブル１４０ｃに登録する。
【００７６】
図１３の説明に戻ると、分岐点判定処理部１５０ｅは、出力ノードと制約ノードが指定された場合に、指定された各ノードから分岐点を判定する処理部である。以下において、分岐点判定処理部１５０ｅの処理を具体的に説明する。図２２は、分岐点判定処理部１５０ｅの処理を説明するための図である。図２２のパストライを構成する各ノードの横に示す（）内の数字は、各ノードの最大兄弟数を示す。すなわち、ACTの最大兄弟数は３、Syain、id、chara、cast、各nameの最大数は１となる。
【００７７】
まず、分岐点判定処理部１５０ｅは、出力ノードの絶対パスと制約ノードの絶対パスとを比較して、共通接頭辞を判定し、判定結果をクエリ生成テーブル１４０ｃに登録する。例えば、図２２の上段に示すように、出力ノードの絶対パス（出力パス）が、「Syain/ACT/cast/name」、制約ノードの絶対パス（制約パス）が「/Syain/ACT/chara/name」の場合には、共通接頭辞に該当するノードは、双方に共通するSyainとACTになる。
【００７８】
続いて、分岐点判定処理部１５０ｅは、分岐点判別ルール（第１、２のルール）に基づいて、共通接頭辞から分岐点となるノードを判定する。ここでは一例として、共通接頭辞として、SyainとACTが判定された場合について説明する。
【００７９】
第１のルールは、共通接頭辞（分岐点候補）のうち、最下の分岐点候補を分岐点候補として判定するものである。ノードSyain、ACTでは、ACTが最下の分岐点候補であるため、分岐点判定処理部１５０ｅは、ACTを分岐点として判定する。
【００８０】
第２のルールは、共通接頭辞のうち、子供ノードの兄弟の最大出現数が２以上の分岐点候補を分岐点と判定する。Syainの子供ノードACTの最大兄弟数は「３」であるため、分岐点判定処理部１５０ｅは、Syainを分岐点として判定する。
【００８１】
分岐点判定処理部１５０ｅは、分岐点として判定したノードの情報をクエリ生成テーブル１４０ｃに登録する。Syainの絶対パスは、「/Syain」となり、ACTの絶対パスは、「/ACT」となる。従って、分岐点判定処理部１５０ｅは、種別「分岐」と、絶対パス「/Syain/ACT」を対応付けて、クエリ生成テーブル１４０ｃに登録する。また、分岐点判定処理部１５０ｅは、種別「分岐」と、絶対パス「/Syain」を対応付けて、クエリ生成テーブル１４０ｃに登録する（図２２の下段参照）。
【００８２】
クエリ生成処理部１５０ｆは、クエリ生成テーブル１４０ｃに基づいて、クエリを生成する処理部である。以下において、クエリ生成処理部１５０ｆの処理を具体的に説明する。クエリ生成処理部１５０ｆは、クエリ生成テーブル１４０ｃを参照し、種別が出力となる絶対パスを抽出する。現在のクエリ生成テーブル１４０ｃの状態を図１６とすると、抽出する絶対パスは、「/Syain/ACT/cast/name」となる。
【００８３】
続いて、クエリ生成処理部１５０ｆは、抽出した絶対パスの各要素に該当するクエリ木構造体（図１７）を生成し、絶対パスにしたがって各クエリ木構造体を接続する。図２３は、絶対パスから生成されるクエリ木の一例を示す図である。図２３に示すように、Syain、ACT、cast、nameに対応するクエリ木構造体がそれぞれ絶対パスの順に接続されている。
【００８４】
また、クエリ生成処理部１５０ｆは、クエリ生成テーブル１４０ｃから、種別が制約となる絶対パスと、種別が分岐となる絶対パスを抽出する。そして、クエリ生成処理部１５０ｆは、図２３に示したクエリ木と、制約、分岐の絶対パスに基づいて、クエリ木にクエリ木構造体を追加する。
【００８５】
例えば、制約の絶対パスが「/Syain/ACT/chara/name」となり、分岐の絶対パスが「/Syain/ACT」の場合には、図１８に示すクエリ木が生成される。すなわち、クエリ生成処理部１５０ｆは、制約の絶対パスから分岐の絶対パスを取り除いた残りのパスに該当するクエリ木構造体を生成する。そして、分岐点のクエリ木構造体ACTを起点として、生成したクエリ木構造体chara、nameを順に接続する。
【００８６】
また、制約の絶対パスが「/Syain/ACT/chara/name」となり、分岐の絶対パスが「/Syain」の場合には、図１９に示すクエリ木が生成される。すなわち、クエリ生成処理部１５０ｆは、制約の絶対パスから分岐の絶対パスを取り除いた残りのパスに該当するクエリ木構造体を生成する。分岐点のクエリ木構造体Syainを起点として、生成したクエリ木構造体ACT、chara、nameを順に接続する。
【００８７】
クエリ生成処理部１５０ｆは、生成したクエリ木を、記憶部１４０に登録する。クエリ生成テーブル１４０ｃに登録されたデータが、図１６に示したものであれば、クエリ生成処理部１５０ｆは、図１８に示したクエリ木と、図１９に示したクエリ木をクエリ木１４０ｄとして登録する。
【００８８】
クエリ表示処理部１５０ｇは、クエリ木１４０ｄ、クエリ生成テーブル１４０ｃに基づいて、パストライ１４０ｂを拡張した後に、パストライを表示させつつクエリの指定箇所を表示して、最適なクエリの選択を受け付ける処理部である。図２４は、クエリ表示処理部１５０ｇの処理を説明するための図である。
【００８９】
具体的に、クエリ表示処理部１５０ｇは、クエリ生成テーブル１４０ｃの分岐（分岐点のノード）に基づいて、パストライ１４０ｂを拡張する。まず、分岐「/Syain」に基づいて、パストライ１４０ｂを拡張する場合について説明する。クエリ表示処理部１５０ｇは、分岐パスの最下に示すノードを判定し、判定したノードの子供ノードを最上とする部分木を複製し、複製した部分木をSyainに接続することで、新たなパストライを生成する。この場合、クエリ表示処理部１５０ｇは、ACTを最上とする部分木を複製する。
【００９０】
そして、クエリ表示処理部１５０ｇは、拡張したパストライの一方の部分木を用いて制約ノードを表示し、もう一方の部分木を用いて出力ノードを表示する。また、クエリ表示処理部１５０ｇは、クエリ生成テーブル１４０ｃの種別「制約」の行に格納された演算子「＝」、「シグマブルー」を制御ノードと関連づけて表示する。また、クエリ表示処理部１５０ｇは、該当するクエリ「/Syain/ACT[chara/name="シグマブルー"]/cast/name」を表示する（図２４の上段参照）。
【００９１】
続いて、分岐「/Syain/ACT」に基づいて、パストライ１４０ｂを拡張する場合について説明する。クエリ表示処理部１４０ｇは、分岐パスの最下に示すノードを判定し、判定したノードの子供ノードを最上とする部分木の複製を試みる。
【００９２】
しかし、パストライ上ではACTから出力ノードへのパスと制約ノードへのパスが既にcharaとcastに分岐している。このような場合には、クエリ表示処理部１５０ｇは、パストライをそのまま表示し、あわせて、制約ノードと出力ノードを表示する。また、クエリ表示処理部１５０ｇは、クエリ生成テーブル１４０ｃの種別「制約」の行に格納された演算子「＝」、「シグマブルー」を制御ノードと関連づけて表示する。また、クエリ表示処理部１５０ｇは、該当するクエリ「/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」を表示する（図２４の下段参照）。
【００９３】
クエリ表示処理部１５０ｇは、図２４に示したパストライ、クエリをモニタに表示し、ユーザにいずれかのクエリを選択させる。クエリ木表示処理部１５０ｇは、クエリの選択を受け付けた場合には、選択されたクエリを検索処理部１５０ｈに出力する。
【００９４】
検索処理部１５０ｈは、クエリ表示処理部１５０ｇからクエリを取得した場合に、クエリに該当するデータをＸＭＬデータから検索し、検索結果を出力部１２０に出力する処理部である。なお、クエリを用いたデータ検索は、どの様な方法を用いて構わない。
【００９５】
例えば、検索処理部１５０ｈは、クエリ「/Syain[ACT/chara/name="シグマブルー"]/ACT/cast/name」を取得した場合には、検索結果として、「<name>多湖真一郎</name>」を出力する（図４参照）。
【００９６】
次に、本実施例にかかる検索装置１００の処理手順について説明する。図２５は、本実施例にかかる検索装置１００の処理手順を示すフローチャートである。図２５に示すように、検索装置１００は、ＸＭＬデータを取得し（ステップＳ１０１）、パストライ生成部１５０ａが、パストライ生成処理を実行する（ステップＳ１０２）。
【００９７】
そして、兄弟出現数計数部１５０ｂが、兄弟出現数計数処理を実行し（ステップＳ１０３）、データ構造表示部１５０ｃが拡張前のパストライを表示し（ステップＳ１０４）、クエリ指定受付部１５０ｄが、出力ノードを受けつけ（ステップＳ１０５）、制約ノードを受け付ける（ステップＳ１０６）。
【００９８】
続いて、分岐点判定処理部１５０ｅが、分岐点判定処理を実行し（ステップＳ１０７）、クエリ生成処理部１５０ｆが、クエリ生成処理を実行し（ステップＳ１０８）、クエリ表示処理部１５０ｆが、クエリ表示処理を実行する（ステップＳ１０９）。
【００９９】
クエリ表示処理部１５０ｆは、クエリの選択を受け付け（ステップＳ１１０）、検索処理部１５０ｈは、選択されたクエリに基づいて検索処理を実行し（ステップＳ１１１）、検索結果を出力する（ステップＳ１１２）。
【０１００】
次に、図２５のステップＳ１０２に示したパストライ生成処理について説明する。図２６は、パストライ生成処理の処理手順を示すフローチャートである。図２６に示すように、パストライ生成部１５０ａは、パストライＴを空の木として初期化し（ステップＳ２０１）、ＸＭＬデータＤに次のタグ「＜」または「＜／」が存在するか否かを判定する（ステップＳ２０２）。
【０１０１】
次のタグが存在しない場合には（ステップＳ２０３，Ｎｏ）、パストライ生成部１５０ａは、パストライＴを出力する（ステップＳ２０４）。一方、次のタグが存在する場合には（ステップＳ２０３，Ｙｅｓ）、タグの種類は開始タグであるか否かを判定する（ステップＳ２０５）。ここで、タグ「＜」は、開始タグを示し、「＜／」は、終了タグを示す。
【０１０２】
タグの種類が終了タグの場合には（ステップＳ２０６，Ｎｏ）、パストライ生成部１５０ａは、パスＰの末端タグをＰから除去し（ステップＳ２０７）、ステップＳ２０２に移行する。一方、タグの種類が開始タグの場合には（ステップＳ２０６，Ｙｅｓ）、パストライ生成部１５０ａは、パスＰの末端にタグを追記する（ステップＳ２０８）。
【０１０３】
そして、パストライ生成部１５０ａは、パスＰがパストライＴに登録済みか否かを判定し（ステップＳ２０９）、登録済みの場合には（ステップＳ２１０，Ｙｅｓ）、ステップＳ２０２に移行する。一方、登録済みではない場合には（ステップＳ２１０，Ｎｏ）、パス登録処理を実行する（ステップＳ２１１）。
【０１０４】
ここで、図２６のステップＳ２１１に示したパス登録処理について説明する。図２７は、パス登録処理の処理手順を示すフローチャートである。図２７に示すように、パストライ生成部１５０ａは、パストライＴは空の木であるか否かを判定する（ステップＳ３０１）。
【０１０５】
パストライＴが空の木である場合には（ステップＳ３０２，Ｙｅｓ）、パストライ生成部１５０ａは、パストライノード構造体Ｎを作成し（ステップＳ３０３）、パストライノード構造体Ｎの絶対パス名にパスＰを登録し（ステップＳ３０４）、パストライノード構造体のタグ名にパスＰに含まれる唯一のタグを登録する（ステップＳ３０５）。
【０１０６】
一方、パストライＴが空の木ではない場合には（ステップＳ３０２，Ｎｏ）、Ｐ＝Ｑ／ｔａｇとなるようなパスＱと末尾タグｔａｇを判定し（ステップＳ３０６）、パストライＴの根ノードから子供ポインタを辿って、絶対パス名がＱとなるノードＮＱを取得する（ステップＳ３０７）。
【０１０７】
そして、パストライ生成部１５０ａは、パストライノード構造体ＮＰを作成し（ステップＳ３０８）、パストライノード構造体ＮＱに子供ポインタを追加してパストライノード構造体ＮＰを指定し、パストライノード構造体ＮＰの親ポインタにパストライノード構造体ＮＱを指定する（ステップＳ３０９）。また、パストライ生成部１５０ａは、パストライノード構造体ＮＰの絶対パス名にパスＰを登録し、タグ名にｔａｇを登録する（ステップＳ３１０）。
【０１０８】
次に、図２５のステップＳ１０３に示した兄弟出現数計数処理について説明する。図２８は、兄弟出現数計数処理の処理手順を示すフローチャートである。図２８に示すように、兄弟出現数計数部１５０ｂは、現在のタグＣｕｒＤを、ＸＭＬデータＤの最初の開始タグで初期化し（ステップＳ４０１）、現在のノードＣｕｔＴを、パストライＴの根ノードで初期化する（ステップＳ４０２）。
【０１０９】
兄弟出現数計数部１５０ｂは、ＸＭＬデータＤに次のタグが存在するか否かを判定し（ステップＳ４０３）、存在しない場合には（ステップＳ４０４，Ｎｏ）、兄弟出現数計数処理を終了する。一方、ＸＭＬデータＤに次のタグが存在する場合には（ステップＳ４０４，Ｙｅｓ）、次のタグが開始タグであるか否かを判定する（ステップＳ４０５）。
【０１１０】
次のタグが終了タグの場合には（ステップＳ４０６，Ｎｏ）、兄弟出現数計数部１５０ｂは、ＣｕｒＴのすべての子供ノードについて、「兄弟数カウンタ」＞「最大兄弟数」の場合に、最大兄弟数の値を兄弟数カウンタの値に置き換える（ステップＳ４０７）。
【０１１１】
兄弟出現数計数部１５０ｂは、ＣｕｒＤを次の終了タグに更新し（ステップＳ４０８）、ＣｕｒＴを、ＣｕｒＴの親ノードに変更し（ステップＳ４０９）、ステップＳ４０３に移行する。
【０１１２】
ところで、ステップＳ４０６において、次のタグが開始タグの場合には（ステップＳ４０６，Ｙｅｓ）、兄弟出現数計数部１５０ｂは、ＣｕｒＤを次の開始タグに更新し（ステップＳ４１０）、ＣｕｒＴを、ＣｕｒＤに対応するＣｕｒＴの子供ノードに置き換える（ステップＳ４１１）。また、兄弟出現数計数部１５０ｂは、ＣｕｒＴの兄弟数カウンタに１を加算し（ステップＳ４１２）、ステップＳ４０３に移行する。
【０１１３】
次に、図２５のステップＳ１０７に示した分岐点判定処理について説明する。図２９は、分岐点判定処理の処理手順を示すフローチャートである。図２９に示すように、分岐点判定処理部１５０ｅは、出力パスＯと制約パスＣの共通接頭辞に含まれるノード集合Ｐを判定し（ステップＳ５０１）、ノード集合Ｐの最下の要素ｖを取り出し、集合Ｒに要素ｖを追加する（ステップＳ５０２）。ステップＳ５０２において、集合Ｒ＝｛ｖ｝とし、ノード集合Ｐ＝Ｐ＼｛ｖ｝とする。
【０１１４】
分岐点判定処理部１５０ｅは、ノード集合Ｐに要素が存在するか否かを判定し（ステップＳ５０４）、要素が存在しない場合には（ステップＳ５０４，Ｎｏ）、集合Ｒを出力し（ステップＳ５０５）、分岐点判定処理を終了する。
【０１１５】
一方、ノード集合Ｐに要素が存在する場合には（ステップＳ５０４，Ｙｅｓ）、ノード集合Ｐから任意の要素ｗを一つ取り出し（ステップＳ５０６）、ｗの最大兄弟数が２以上であるか否かを判定する（ステップＳ５０７）。
【０１１６】
ｗの最大兄弟数が２未満である場合には（ステップＳ５０８，Ｎｏ）、分岐点判定処理部１５０ｅは、ステップＳ５０３に移行する。一方、ｗの最大兄弟数が２以上である場合には（ステップＳ５０８，Ｙｅｓ）、集合Ｒに要素ｗを追加し（ステップＳ５０９）、ステップＳ５０３に移行する。
【０１１７】
次に、図２５のステップＳ１０８に示したクエリ生成処理について説明する。図３０は、クエリ生成処理の処理手順を示すフローチャートである。図３０に示すように、クエリ生成処理部１５０ｆは、クエリ生成テーブル１４０ｃを取得し（ステップＳ６０１）、種別「出力」の絶対パスから、クエリ木を作成する（ステップＳ６０２）。
【０１１８】
クエリ生成処理部１５０ｆは、クエリ生成テーブル１４０ｃに種別「制約」が一つでも存在するか否かを判定し（ステップＳ６０３）、「制約」が存在しない場合には（ステップＳ６０４，Ｎｏ）、クエリを全て処理したか否かを判定する（ステップＳ６０５）。
【０１１９】
クエリを全て処理していない場合には（ステップＳ６０６，Ｎｏ）、クエリ生成処理部１５０ｆは、次のクエリを選択し（ステップＳ６０７）、ステップＳ６０２に移行する。一方、クエリを全て処理している場合には（ステップＳ６０６，Ｙｅｓ）、クエリ生成処理を終了する。
【０１２０】
ところで、ステップＳ６０４において、クエリテーブルに種別「制約」が一つでも存在する場合には（ステップＳ６０４，Ｙｅｓ）、未選択の分岐点を一つ選択し（ステップＳ６０８）、次の「制約」の行の絶対パスを、分岐点まで共通接頭辞が統合され、分岐点から分岐するようにクエリ木に追加する（ステップＳ６０９）。
【０１２１】
そして、クエリ生成処理部１５０ｆは、種別「制約」を全て処理したか否かを判定し（ステップＳ６１０）、全て処理していない場合には（ステップＳ６１１，Ｎｏ）、ステップＳ６０９に移行する。
【０１２２】
一方、種別「制約」を全て処理した場合には（ステップＳ６１１，Ｙｅｓ）、全ての分岐点を選択したか否かを判定し（ステップＳ６１２）、全ての分岐点を選択していない場合には（ステップＳ６１３，Ｎｏ）、ステップＳ６０８に移行する。一方、全ての分岐点を選択している場合には（ステップＳ６１３，Ｙｅｓ）、クエリ木を巡回し、クエリを生成し（ステップＳ６１４）、ステップＳ６０５に移行する。
【０１２３】
次に、図２５のステップＳ１０９に示したクエリ表示処理について説明する。図３１は、クエリ表示処理の処理手順を示すフローチャートである。図３１に示すように、クエリ表示処理部１５０ｇは、未選択の分岐点Ｂを選択し（ステップＳ７０１）、パストライＴの根ノードから子供ポインタを辿り、分岐点Ｂに対応するノードＮＢに移行する（ステップＳ７０２）。
【０１２４】
クエリ表示処理部１５０ｇは、出力パスＯと制約パスＣが、分岐点Ｂから分岐しているか否かを判定する（ステップＳ７０３）。分岐している場合には（ステップＳ７０４，Ｙｅｓ）、パストライ上に出力パスＯおよび制約パスＣを表示し（ステップＳ７０５）、ステップＳ７１１に移行する。
【０１２５】
一方、出力パスＯと制約パスＣが、分岐点Ｂから分岐していない場合には（ステップＳ７０４，Ｎｏ）、クエリ表示処理部１５０ｇは、出力パスＯ、制約パスＣの共通接頭辞において、ノードＮＢの直下にあたるノードをノードＮ１に設定する（ステップＳ７０６）。
【０１２６】
続いて、クエリ表示処理部１５０ｇは、ノードＮ１を根ノードとする部分木を部分木Ｓｕｂ１とし、部分木Ｓｕｂ１を複製して部分木Ｓｕｂ２を作成し（ステップＳ７０７）、ノードＮＢに子供ポインタを追加し、部分木Ｓｕｂ２の根ノードＮ２を指定する（ステップＳ７０８）。
【０１２７】
クエリ表示処理部１５０ｇは、ノードＮ２の親ポインタにノードＮＢを指定し（ステップＳ７０９）、部分木Ｓｕｂ２を含めてパストライＴを表示し、出力パスＯを表す印を部分木Ｓｕｂ１上に表示し、制約パスＣを表す印を部分木Ｓｕｂ２上に表示する（ステップＳ７１０）。
【０１２８】
そして、クエリ表示処理部１５０ｇは、全ての分岐点Ｂを選択したか否かを判定し（ステップＳ７１１）、未選択の分岐点Ｂが存在する場合には（ステップＳ７１２，Ｎｏ）、ステップＳ７０１に移行する。一方、全ての分岐点Ｂを選択した場合には（ステップＳ７１２，Ｙｅｓ）、クエリ表示処理を終了する。
【０１２９】
上述してきたように、本実施例にかかる検索装置１００は、パストライを表示して出力ノードと制約ノードが指定された場合に、各ノードの絶対パスから共通接頭辞を判定してクエリの分岐点を判定する。そして、検索装置１００は、出力ノードと制約ノードから複数のクエリを生成可能な場合には、分岐点を基にして必要最低限に拡張したパストライを生成し、各クエリの違いがユーザにわかるように表示して、最適なクエリを選択させるので、周知技術の直感的な手法を踏襲しつつ、制約条件を含んだ複雑なクエリの作成を支援することが出来る。
【０１３０】
なお、本実施例では、半構造体データとしてＸＭＬデータ、クエリとしてＸＰａｔｈ式を用いて説明した。しかし、半構造体データとクエリの種類はこれらに限定されるものではない。例えば、半構造体データは、ＸＭＬデータの他にも、ＲＤＢのテーブルやＣＳＶデータ等が含まれ、かかるＲＤＢのテーブルやＣＳＶファイルに対しても本願発明を適用することが出来る。
【０１３１】
また、本実施例にかかる検索装置１００は、兄弟出現数計数部１５０ｂがパストライノード構造体に最大兄弟数を登録し、分岐点判定処理部１５０ｅがかかる最大兄弟数を参照して分岐点に該当するか否かを判定していたが、これに限定されるものではない。
【０１３２】
例えば、兄弟出現数計数部１５０ｂは、該当ノードに２以上の兄弟が存在する場合には、パストライノード構造体に２以上の兄弟が存在する旨の識別情報のみを登録してもよい。この場合、分岐点判定処理部１５０ｅは、分岐点を判定する場合に、各分岐点候補のうち識別情報を有するノードを分岐点として判定することが出来る。
【０１３３】
ところで、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１３４】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１３５】
図３２は、実施例に示した検索装置１００に対応するコンピュータのハードウェア構成を示す図である。図３２に示すように、このコンピュータ（検索装置）１０は、入力装置１１、モニタ１２、ＲＡＭ（Random  Access  Memory）１３、ＲＯＭ（Read  Only  Memory）１４、ネットワークを介して他の装置とデータ通信を実行する通信制御装置１５、媒体読取装置１６、ＣＰＵ（Central  Processing  Unit）１７、ＨＤＤ（Hard  Disk  Drive）１８をバス１９で接続している。
【０１３６】
そして、ＨＤＤ１８には、上述した検索装置１００の機能と同様の機能を発揮するクエリ生成表示プログラム１８ｂ、検索プログラム１８ｃが記憶されている。ＣＰＵ１７が、クエリ生成表示プログラム１８ｂ、検索プログラム１８ｃを読み出して実行することにより、クエリ生成表示プロセス１７ａ、検索プロセス１７ｂが起動される。
【０１３７】
ここで、クエリ生成表示プロセス１７ａは、図１３に示したパストライ生成部１５０ａ、兄弟出現数計数部１５０ｂ、データ構造表示部１５０ｃ、クエリ指定受付部１５０ｄ、分岐点判定処理部１５０ｅ、クエリ生成処理部１５０ｅ、クエリ表示処理部１５０ｇに対応する。また、検索プロセス１７ｂは、図１３に示した検索処理部１５０ｈに対応する。
【０１３８】
なお、ＨＤＤ１８は、図１３で示した記憶部１４０に記憶されたデータに対応する各種データ１８ａを記憶している。ＣＰＵ１７は、ＨＤＤ１８に記憶された各種データ１８ａをＲＡＭ１３に読み出し、各種データ１３ａを利用して、クエリの表示およびＸＭＬデータの検索処理を実行する。
【符号の説明】
【０１３９】
１０    コンピュータ（検索装置）
１１    入力装置
１２    モニタ
１３    ＲＡＭ
１３ａ，１８ａ  各種データ
１４    ＲＯＭ
１５    通信制御装置
１６    媒体読取装置
１７    ＣＰＵ
１７ａ  クエリ生成表示プロセス
１７ｂ  検索プロセス
１８    ＨＤＤ
１８ｂ  クエリ生成表示プログラム
１８ｃ  検索プログラム
１９    パス
１００    検索装置
１１０    入力部
１２０    出力部
１３０    入出力制御部
１４０    記憶部
１４０ａ  ＸＭＬデータ
１４０ｂ  パストライ
１４０ｃ  クエリ生成テーブル
１４０ｄ  クエリ木
１５０    制御部
１５０ａ  パストライ生成部
１５０ｂ  兄弟出現数計数部
１５０ｃ  データ構造表示部
１５０ｄ  クエリ指定受付部
１５０ｅ  分岐点判定処理部
１５０ｆ  クエリ生成処理部
１５０ｇ  クエリ表示処理部
１５０ｈ  検索処理部
【図１】
2010211540.tif 000003
【図２】
2010211540.tif 000004
【図３】
2010211540.tif 000005
【図４】
2010211540.tif 000006
【図５】
2010211540.tif 000007
【図６】
2010211540.tif 000008
【図７】
2010211540.tif 000009
【図８】
2010211540.tif 000010
【図９】
2010211540.tif 000011
【図１０】
2010211540.tif 000012
【図１１】
2010211540.tif 000013
【図１２】
2010211540.tif 000014
【図１３】
2010211540.tif 000015
【図１４】
2010211540.tif 000016
【図１５】
2010211540.tif 000017
【図１６】
2010211540.tif 000018
【図１７】
2010211540.tif 000019
【図１８】
2010211540.tif 000020
【図１９】
2010211540.tif 000021
【図２０】
2010211540.tif 000022
【図２１】
2010211540.tif 000023
【図２２】
2010211540.tif 000024
【図２３】
2010211540.tif 000025
【図２４】
2010211540.tif 000026
【図２５】
2010211540.tif 000027
【図２６】
2010211540.tif 000028
【図２７】
2010211540.tif 000029
【図２８】
2010211540.tif 000030
【図２９】
2010211540.tif 000031
【図３０】
2010211540.tif 000032
【図３１】
2010211540.tif 000033
【図３２】
2010211540.tif 000034