(57)【要約】【課題】複数回出現していないパスを対象とした検索をより効率的に行う。【解決手段】本発明は、検索パスに基づいて問い合わせ木を作成し、同一パスで複数出現しない問い合わせノード群を統合し、問い合わせノードを葉とし、親子・先祖子孫関係を示す関係判定ノードからなる実行木を生成し、問い合わせノードに基づいて、ノード関係情報及びノード情報を取得し、同一の文書ＩＤを参照して、関係判定ノードの先祖となる問い合わせノードが複数出現している場合には、当該先祖となる問い合わせノードのノード情報による親子・先祖子孫関係を判定し、適切な組み合わせを選択し、該問い合わせノードが１つの場合は同一データのものを組み合わせる。【選択図】図１
2010108192.tif 000002
【特許請求の範囲】
【請求項１】
構造化データであるＸＭＬ文書群の検索を行うＸＭＬデータ検索方法であって、
ＸＭＬデータの構造と記述内容を管理するノード管理手段と、該ＸＭＬデータの持つ全てのパスと、該パスに指定されるノードを関係付けるインデクスを構築し、保持するパスインデクス手段と、入力された検索クエリに含まれる検索パス及び検索キーワードに基づいて検索を行う検索手段と、を有する装置において、
前記ノード管理手段が、取得した前記ＸＭＬ文書毎に文書ＩＤを付与し、該ＸＭＬデータの各節である各ノードにノードＩＤを付与し、パスを特定し、該ノード間の親子・先祖子孫関係をノード情報としてノード情報記憶手段に格納するノード関係構築ステップを行い
前記パスインデクス手段が、前記ノード管理手段から前記パス、前記文書ＩＤ、前記ノード情報を取得し、前記ＸＭＬデータの持つ全てのパスと、該パスに指定されるノードを関係付けるノード関係情報を生成し、該パスが同一データで既出のパスである場合には、該パスに複数出現している旨の複数出現パス情報を付与し、パスインデクス記憶手段に格納するパスインデクス作成ステップを行い、
前記検索手段が、
前記検索パスに基づいて問い合わせ木を作成し、同一パスで複数出現しない問い合わせノード群を統合し、問い合わせノードを葉とし、親子・先祖子孫関係を示す関係判定ノードからなる実行木を生成する実行木作成ステップと、
前記問い合わせノードに基づいて、前記パスインデクス記憶手段と、前記ノード情報記憶手段から前記ノード関係情報及び前記ノード情報を取得するノード情報取得ステップと、
同一の文書ＩＤを参照して、前記関係判定ノードの先祖となる問い合わせノードが複数出現している場合には、当該先祖となる問い合わせノードの前記ノード情報による親子・先祖子孫関係を判定し、適切な組み合わせを選択し、該問い合わせノードが１つの場合は同一データのものを組み合わせる関係判定ステップと、
を行うことを特徴とするＸＭＬデータ検索方法。
【請求項２】
前記関係判定ステップにおいて、
前記ＸＭＬデータの木構造におけるテキストノード及び属性の値に対するインデクスを値インデクス記憶手段に保持しておき、
前記検索クエリに含まれる同一の検索パスに複数の制約があり、該検索パスが単一出現であれば、前記値インデクス記憶手段を参照して、該制約を満たすテキストノードを選択する
請求項１記載のＸＭＬデータ検索方法。
【請求項３】
構造化データであるＸＭＬ文書群の検索を行うＸＭＬデータ検索装置であって、
取得した前記ＸＭＬ文書毎に文書ＩＤを付与し、該ＸＭＬデータの各節である各ノードにノードＩＤを付与し、パスを特定し、該ノード間の親子・先祖子孫関係をノード情報としてノード情報記憶手段に格納するノード管理手段と、
前記ノード管理手段から前記パス、前記文書ＩＤ、前記ノード情報を取得し、前記ＸＭＬデータの持つ全てのパスと、該パスに指定されるノードを関係付けるノード関係情報を生成し、該パスが同一データで既出のパスである場合には、該パスに複数出現している旨の複数出現パス情報を付与し、パスインデクス記憶手段に格納するパスインデクス手段と、
入力された検索クエリに含まれる検索パス及び検索キーワードに基づいて検索を行う検索手段と、を有し、
前記検索手段は、
前記検索パスに基づいて問い合わせ木を作成し、同一パスで複数出現しない問い合わせノード群を統合し、問い合わせノードを葉とし、親子・先祖子孫関係を示す関係判定ノードからなる実行木を生成する実行木作成手段と、
前記問い合わせノードに基づいて、前記パスインデクス手段の前記パスインデクス記憶手段と、前記ノード管理手段の前記ノード情報記憶手段から前記ノード関係情報及び前記ノード情報を取得するノード情報取得手段と、
同一の文書ＩＤを参照して、前記関係判定ノードの先祖となる問い合わせノードが複数出現している場合には、当該先祖となる問い合わせノードの前記ノード情報による親子・先祖子孫関係を判定し、適切な組み合わせを選択し、該問い合わせノードが１つの場合は同一データのものを組み合わせる関係判定手段と、
を有することを特徴とするＸＭＬデータ検索装置。
【請求項４】
前記実行木作成手段は、
前記ＸＭＬデータの木構造におけるテキストノード及び属性の値に対するインデクスを値インデクス記憶手段に保持しておき、前記検索クエリに含まれる同一の検索パスに複数の制約があり、該検索パスが単一出現であれば、前記値インデクス記憶手段を参照して、該制約を満たすテキストノードを選択する
手段を含む
請求項３記載のＸＭＬデータ検索装置。
【請求項５】
請求項３または、４に記載のＸＭＬデータ検索装置を構成する各手段としてコンピュータを機能させるためのＸＭＬデータ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬデータ検索方法及び装置及びプログラムに係り、特に、構造化データである多数のＸＭＬデータを蓄積・検索するデータベース／インデクスの分野で、蓄積したＸＭＬデータの要約した構造情報を用いることで、検索実行時の処理を効率化することで、検索を高速に行うＸＭＬデータ検索方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
ＸＭＬとはマークアップ言語の一つで、ＸＭＬで記述されたデータは構造化され、構造に意味を持ったデータである。図１７は、ＸＭＬデータとその構造を示した図である。ＸＭＬデータを構成する要素を識別するために使われるマークを「タグ」と呼び、タグに挟まれた間に値（テキスト）を記述する。タグは入れ子にすることができる。
【０００３】
したがって、ＸＭＬデータは木構造で表すことができ、各節を「ノード」と呼ぶ。特に、根のノードを「ルート要素」（"book"）、値（記述内容）を「テキストノード」("宇宙の不思議")、タグ中に記述されたものを「属性」（"no=１"）と呼ぶ。
【０００４】
各ノードは、"／"の後ろにルート要素からのタグを"／"で繋げた「パス」で指定する。例えば、本のタイトルを対象としたい場合、パスを「/book/title」と指定する。
【０００５】
ＸＭＬデータに対して効率的な検索を実現しようとした場合、構造から記述内容を高速に取り出すことが可能でなければならない。一般的には、ＸＭＬデータの構造と記述内容を記録したインデクス（構造インデクス）を予め構築しておく。構造インデクスの構築は様々な方法が存在するが、多くの場合、ＸＭＬデータの持つ全てのパスと、該パスに指定される記述内容を関係付けるインデクスが構築される（例えば、特許文献１参照）。
【特許文献１】特開２００６−２２８１５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ＸＭＬデータの検索の検索クエリには、パスとその値の制約が検索条件として指定される。例えば、XPath（ＸＭＬデータ中の特定の要素を指し示す記述方法）では、以下のような記述がなされる。
【０００７】
/book/chapter[title='惑星とは']
これは、［/book/chapter/title］パスの値（テキスト）が「惑星とは」と記述されている[/book/chapter]を指している。
【０００８】
単純な検索手法としては、各ＸＭＬデータのルート要素から順次子ノードを辿っていき、検索条件に合ったノード群を探し出す方法があるが、大きなデータや多数のデータ群の場合や、パスが深いところを指している場合などには、走査に時間がかかってしまう。
【０００９】
そこで、前述の特許文献１に示すような、処理に必要なノード群だけを直接取り出し、それらの親子／先祖子孫関係を判定することで、効率的な検索が行われる。ノード間の親子／先祖子孫関係の判定は、ＸＭＬデータの柔軟性から、１つのＸＭＬデータ中に同一パスが繰り返し出現したり（図１７の「/book/chapter」）、同一タグが再帰的に出現したり（図１３の「title」）といった複雑な構造があり得るため、必要なものである。しかし実際には、１つのデータ中に１度しか出現しないパス・タグも多く、そのようなパスについても同等に処理を行うのは非効率である。
【００１０】
本発明は、上記の点に鑑みなされたもので、複数回出現していないパスを対象とした検索をより効率的に行うことが可能なＸＭＬデータ検索方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
図１は、本発明の原理を説明するための図である。
【００１２】
本発明（請求項１）は、構造化データであるＸＭＬ文書群の検索を行うＸＭＬデータ検索方法であって、
ＸＭＬデータの構造と記述内容を管理するノード管理手段と、該ＸＭＬデータの持つ全てのパスと該パスに指定されるノードを関係付けるインデクスを構築し、保持するパスインデクス手段と、入力された検索クエリに含まれる検索パス及び検索キーワードに基づいて検索を行う検索手段と、を有する装置において、
ノード管理手段が、
取得したＸＭＬ文書毎に文書ＩＤを付与し、該ＸＭＬデータの各節である各ノードにノードＩＤを付与し、パスを特定し、該ノード間の親子・先祖子孫関係をノード情報としてノード情報記憶手段に格納するノード関係構築ステップ（ステップ１）を行い、
パスインデクス手段が、
ノード管理手段からパス、文書ＩＤ、ノード情報を取得し、ＸＭＬデータの持つ全てのパスと、該パスに指定されるノードを関係付けるノード関係情報を生成し、該パスが同一データで既出のパスである場合には、該パスに複数出現している旨の複数出現パス情報を付与し、パスインデクス記憶手段に格納するパスインデクス作成ステップ（ステップ２）を行い、
検索手段が、
検索パスに基づいて問い合わせ木を作成し、同一パスで複数出現しない問い合わせノード群を統合し、問い合わせノードを葉とし、親子・先祖子孫関係を示す関係判定ノードからなる実行木を生成する実行木作成ステップ（ステップ３）と、
問い合わせノードに基づいて、パスインデクス記憶手段と、ノード情報記憶手段からノード関係情報及びノード情報を取得するノード情報取得ステップ（ステップ４）と、
同一の文書ＩＤを参照して、前記関係判定ノードの先祖となる問い合わせノードが複数出現している場合には、当該先祖となる問い合わせノードの前記ノード情報による親子・先祖子孫関係を判定し、適切な組み合わせを選択し、該問い合わせノードが１つの場合は同一データのものを組み合わせる関係判定ステップ（ステップ５）と、を行う。
【００１３】
また、本発明（請求項２）は、関係判定ステップ（ステップ５）において、
ＸＭＬデータの木構造におけるキストノード及び属性の値に対するインデクスを値インデクス記憶手段に保持しておき、
検索クエリに含まれる同一の検索パスに複数の制約があり、該検索パスが単一出現であれば、値インデクス記憶手段を参照して、該制約を満たすテキストノードを選択する。
【００１４】
図２は、本発明の原理構成図である。
【００１５】
本発明（請求項３）は、構造化データであるＸＭＬ文書群の検索を行うＸＭＬデータ検索装置であって、
取得したＸＭＬ文書毎に文書ＩＤを付与し、該ＸＭＬデータの各節である各ノードにノードＩＤを付与し、パスを特定し、該ノード間の親子・先祖子孫関係をノード情報としてノード情報記憶手段１２１に格納するノード管理手段１２０と、
ノード管理手段１２０からパス、文書ＩＤ、ノード情報を取得し、ＸＭＬデータの持つ全てのパスと、該パスに指定されるノードを関係付けるノード関係情報を生成し、該パスが同一データで既出のパスである場合には、該パスに複数出現している旨の複数出現パス情報を付与し、パスインデクス記憶手段１１１に格納するパスインデクス手段１１０と、
入力された検索クエリに含まれる検索パス及び検索キーワードに基づいて検索を行う検索手段１４０と、を有し、
検索手段１４０は、
検索パスに基づいて問い合わせ木を作成し、同一パスで複数出現しない問い合わせノード群を統合し、問い合わせノードを葉とし、親子・先祖子孫関係を示す関係判定ノードからなる実行木を生成する実行木作成手段１４１と、
問い合わせノードに基づいて、パスインデクス手段１１０のパスインデクス記憶手段１１１と、ノード管理手段１２０のノード情報記憶手段１２１からノード関係情報及びノード情報を取得するノード情報取得手段１４２と、
同一の文書ＩＤを参照して、前記関係判定ノードの先祖となる問い合わせノードが複数出現している場合には、当該先祖となる問い合わせノードの前記ノード情報による親子・先祖子孫関係を判定し、適切な組み合わせを選択し、該問い合わせノードが１つの場合は同一データのものを組み合わせる関係判定手段１４３と、を有する。
【００１６】
また、本発明（請求項４）は、関係判定手段１４３は、
ＸＭＬデータの木構造におけるテキストノード及び属性の値に対するインデクスを値インデクス記憶手段に保持しておき、検索クエリに含まれる同一の検索パスに複数の制約があり、該検索パスが単一出現であれば、値インデクス記憶手段を参照して、該制約を満たすテキストノードを選択する
手段を含む。
【００１７】
本発明（請求項５）は、請求項３または、４に記載のＸＭＬデータ検索装置を構成する各手段としてコンピュータを機能させるためのＸＭＬデータ検索プログラムである。
【発明の効果】
【００１８】
上記のように本発明によれば、ＸＭＬの木構造の親または先祖子孫関係となるノードが単一出現する場合には、同一データのものを組み合わせることで、検索を高速化することができる。
【００１９】
また、検索パスに制約条件がある場合に、テキストノード及び属性の値に対するインデクスの走査を一度に行うことができる。
【発明を実施するための最良の形態】
【００２０】
以下、図面と共に本発明の実施の形態を説明する。
【００２１】
図３は、本発明の一実施の形態における検索装置の構成を示す。
【００２２】
同図に示す検索装置１００は、ＸＭＬの構造をパス単位で管理するパスインデクス部１１０と、ＸＭＬの各ノード間のＸＭＬ構造における関係を把握するノード管理部１２０と、各ノードの値のインデクスを構築・管理する値インデクス部１３０と、検索を実行する検索部１４０と、を有する。パスインデクス部１１０とノード管理部１２０が、前述の背景技術で説明した構造インデクスに相当する。
【００２３】
パスインデクス部１１０は、ＸＭＬデータの持つ全てのパスと、当該パスに指定されるノードを関連付けるインデクスを構築し、パスインデクス記憶部１１１に保持する。構築の際には、パスが同一データ中で複数回出現したかについてもチェックし、パスインデックスと共に出現回数もパスインデクス記憶部１１１に格納する。
【００２４】
ノード管理部１２０は、各ノード間のＸＭＬデータの構造上の関係を管理する。一般的には、構造上の関係を管理するために、ＸＭＬデータの各ノードにＩＤを付与し、ノード間の関係（先祖子孫関係など）をノード情報としてノード情報記憶部１２１に格納する。当該ノード情報としては、「範囲ラベル」がある。具体的な「範囲ラベル」の例としては、例えば特許文献１の技術を用いることができる。
【００２５】
値インデクス部１３０は、テキストノード及び属性の値に対するインデクス（B−Tree、ハッシュ、等）を構築し、値インデクス記憶部１３１で管理する。検索するだけであれば不要のものであるが、高速検索を実現するためには必要となる。
【００２６】
検索部１４０は、要求された検索クエリに含まれる検索パス及び検索キーワードに基づいて以下の手順を行う。
【００２７】
手順１．検索パスにマッチするノード（群）へのノード関係情報をパスインデクス部１１０から取得し、同時に、各パスが単一出現かどうかの情報も取得する。
【００２８】
手順２．上記のノード（群）に関するノード情報をノード管理部１２０から取得する。
【００２９】
（ａ）制約がある場合は、値インデックス部１３０から該当するノード（群）のみを選択する。この際、同一検索パスに対し、複数の制約がある場合は、パスが単一出現であれば、一度に走査できる場合がある。 "惑星とは"を制約の例とした場合、値（テキストノード）が"惑星とは"と完全一致しているという制約を持った「/book/chapter/title ノード群」であり、また、制約は「１以上 AND ２以下」と複数となることもある。
【００３０】
手順３．親子／先祖子孫関係の判定を行う。ノード管理部１２０のノード記憶部１２１を参照して、親／先祖となるノード群が、単一出現か複数出現かにより処理を以下に分岐させる。
【００３１】
（ａ）複数出現ありの場合、親子／先祖子孫関係を判定し、適切な組み合わせのものを選択する（従来処理）；
（ｂ）単一出現の場合、同一データのものを組み合わせる；
という処理を行う。
【００３２】
すなわち、親／先祖候補のノード群が、複数出現する場合は従来通りの処理を行うが、単一出現の場合は、同一データに出現したかどうかを判定するだけ（上記３．（ｂ））でよく、より高速な検索を実現できる。また同時に、複数の制約がある場合に、値インデクス部１３０の値インデクス記憶部１３１の走査を一度に行うことができ、高速化できる場合もある。
【００３３】
以下に具体的な例を示す。図１３のデータに対し、
【００３４】
【数１】
2010108192.tif 000003
というXPathを処理する場合、以下の手順で行う（XPathでは属性は
【００３５】
【数２】
2010108192.tif 000004
をつけて表現する）
手順１．「/book/chapter」に相当するノード（３つ）を取得する。
【００３６】
手順２．
【００３７】
【数３】
2010108192.tif 000005
で値が１以上のノード（３つ）を取得する。
【００３８】
手順３．
【００３９】
【数４】
2010108192.tif 000006
で値が２以下のノード（２つ）を取得する。
【００４０】
手順４．上記の手順１のノードで、手順２と手順３の双方を子孫ノードに持つものを選択する。
【００４１】
これは、「/book/chapter」が複数回出現しており、候補となるノードも複数であるため、従来の処理手順である。
【００４２】
これに対し、
/book[date/text()>='2008/01/01' and date/text()<='2008/12/31']
というXPathを処理する場合は、以下のような手順で行う（テキストノードは"text()"と表現する）。
【００４３】
手順１．「/book」に相当するノード（１つ）を取得する。
【００４４】
手順２．「/book/date」で値（テキストノード）が'2008/01/01'から'2008/12/31'のノード（１つ）を取得する。
【００４５】
手順３．手順１のノードで、手順２と同一データのものを選択する。
【００４６】
「/book/date/text()」が単一出現であるため、前述の例では、２回の手順となっていた制約付きノード取得が、手順２の１回で済んでおり、「/book」が単一出現であるため、手順３のノード選択も同一データかどうかのみの判定となっている。
【００４７】
同一データかどうかのみの判定でよい理由は、単一出現の場合、パスで親子／先祖子孫関係が自明であるため、省略できるからである。上記の例では、「/book/date/text()」が１つしかないのであれば、同一文書の「/book」の子孫でしかありえない。
【実施例】
【００４８】
本発明の実施例として、前述の特許文献１の手法をベースに改良した例を説明する。
【００４９】
本実施例における検索装置は、図３に示すように、パスインデクス部１１０、ノード管理部１２０、値インデクス部１３０からなる。
【００５０】
パスインデクス部１１０は、特許文献１の「要約情報」を管理するモジュールで、パスと、該パスに対応する各データのノードへの関係をパスインデクス記憶部１１１で保持し、加えて、単一出現かどうかの情報も保持する。
【００５１】
ノード管理部１２０は、図４に示すようなテーブルで各ノードの情報を管理する。図４に示すノード情報は、文書ＩＤ，preorder値、postorder値、タグ、値（value）からなる。なお、ノード情報は、図４に示すテーブル構成に限定されるものではなく、木構造の中で検索対象となるノードを特定する機能を持ち、先祖子孫関係を判定可能なものであればよい。以下では、「範囲ラベル」として、図５に示すように、ノード毎に２値(preorder値、postorder値)で表され、親ノードが子ノードを含むように付与する。これにより、任意のノード間で親子／先祖子孫関係を判定可能となる。
【００５２】
値インデクス部１３０は、テキストノード及び属性の値に対するインデクス（B-Tree、ハッシュ等）を構築・管理する。少なくともパスとその値の制限を条件に、検索が可能な形とする。例えば、パスと値の両方をキーに全てを対象としたインデクスを１つ作成してもよいし、パス毎に別々のインデクス（値がキーとなる）を作成してもよい。
【００５３】
検索部１４０は、検索クエリを受け取り、指定された検索パス及び検索キーワードにマッチするノードを、パスインデクス部１１０、ノード管理部１２０、値インデクス部１３０に問い合わせて特定し、当該ノードを検索結果として返却する。
【００５４】
以下に、ＸＭＬ文書の「格納フェイズ」、「検索フェイズ」からなる動作を説明する。
【００５５】
＜格納フェイズ＞
当該格納フェイズでは、与えられたＸＭＬ文書群から、各種インデクスを作成する。
【００５６】
ＸＭＬ文書群に対し、パスインデクス部１１０、ノード管理部１２０、値インデクス部１３０のそれぞれが処理を行う。
【００５７】
図６は、本発明の一実施例の全体フローを示す。
【００５８】
ステップ１１０）  ＸＭＬ文書記憶装置１０からＸＭＬ文書を読み出す。
【００５９】
ステップ１２０）  読み出したＸＭＬ文書毎に文書ＩＤを付与する。
【００６０】
ステップ１３０）  ノード管理装置１２０において、以下の処理を行う。ノード管理装置１２０の動作を図７に示す。
【００６１】
ノード管理装置１２０は、文書からノードを取り出し（ステップ１３１）、パスを特定し、パスインデックス部１１０に伝える（ステップ１３２）。次に、各ノード毎にノード間の関係（先祖子孫関係など）を表すノードＩＤ（範囲ラベル）を付与して（ステップ１３３）、ノード情報記憶部１２１に文書ＩＤ，ノードＩＤ等を格納する（ステップ１３４）。当該処理を全ノードについて繰り返す。
【００６２】
ステップ１４０）パスインデクス部１１０において、以下の処理を行う。パスインデクス部１１０の動作を図８に示す。
【００６３】
パスインデクス部１１０は、ノード管理部１２０からパス、文書ＩＤ、ノード情報を受け取る（ステップ１４１）。ノード管理部１２０から受け取ったパスは同一データで既出のパスであるかをパスインデクス記憶部１１１を参照して判定し（ステップ１４２）、既出のパスでない場合は（ステップ１４２、Ｎｏ）、全データで既出のパスかを判定する（ステップ１４３）。既出のパスでない場合は（ステップ１４３、Ｎｏ），当該パスをパスインデクス記憶部１１１に新規登録する（ステップ１４４）。同一データで既出のパスである場合は（ステップ１４２、Ｙｅｓ）、当該パスに複数出現（multi）情報（"true"）を付与する（ステップ１４６）。さらに、図１０に示すように、要約情報のパスとそれに相当するノード関係を保持する（ステップ１４５）。また、ステップ１４３において全データで既出のパスである場合（ステップ１４３、Ｙｅｓ）も、当該パスとノード情報の関連を保持する（ステップ１４５）。
【００６４】
なお、上記のステップ１４２において、既出のパスであるか否かを判定する際に、パスインデクス記憶部１１１の「multi」欄が"false"か"true"のいずれであるかにより判定する方法以外に、パス毎の出現回数を管理することも可能である。
【００６５】
図１１に、インデクス記憶部１１１のストロングデータガイドの例を示す。ストロングデータガイドは、ＸＭＬ文書群の出現したパスを抽出してまとめたもので、パスの出現数や順序などは省略した要約情報である。図１１のストロングデータガイドに上記のmulti情報を付与した例を図１２に示す。
【００６６】
＜検索フェイズ＞
図１３は、本発明の一実施例の検索フェイズのフローを示す。
【００６７】
ステップ２０１）  検索部１４０は、図１４に示すような問い合わせ木を作成する。
【００６８】
ステップ２０２）  同一パスで複数出現していない問い合わせノード群を統合する。
【００６９】
ステップ２０３）  問い合わせノードを葉とし、先祖子孫関係を示す関係判定ノードを作成することにより、問い合わせ木に対する実行木を作成する。
【００７０】
ステップ２０４）  問い合わせノードを選択する。
【００７１】
ステップ２０５）  パスインデクス部１１０、ノード管理部１２０から該当するノード情報（群）を取得する。
【００７２】
ステップ２０６）  値インデクス部１３０に問い合わせ値の制約を満たすものだけに絞り込む。
【００７３】
ステップ２０７）  全ての問い合わせノード分、ステップ２０４以降の処理を繰り返す。
【００７４】
ステップ２０８）  関係判定ノードを選択する。
【００７５】
ステップ２０９）  先祖となる問い合わせノードが複数出現しているかを判定し、出現している場合には、ステップ２１０に移行し、ステップ２１１に移行する。
【００７６】
ステップ２１０）  ノード管理部１２０から取得したノード群情報（範囲ラベル）に夜から構造ジョインにより、親子／先祖子孫関係を判定し、ステップ２１２に移行する。
【００７７】
ステップ２１１）  ステップ２０９において、先祖となる問い合わせノードが単数の場合は文書ＩＤのみのマッチングを行う。
【００７８】
ステップ２１２）  全ての関係判定ノードに対して上記のステップ２０８以降の処理を繰り返す。
【００７９】
ステップ２１３）  結果を組み立て、返却する。
【００８０】
以下に、具体的な例として、図１７のデータに対し、
【００８１】
【数５】
2010108192.tif 000007
という２つのXPathにより検索を行った場合を、図１３のフローに沿って説明する。
【００８２】
XPathの問い合わせ木は、木で表現でき、図１４のようになる（ステップ２０１）。同図において、二重線で囲まれている楕円のノードが、問い合わせノードを表している。同図（Ｂ）の例の場合、「/book/date/text()」の２つのノードが単一出現であることが図１２からわかるため統合できる（ステップ２０２）。統合を行うことで、値インデクス部１３０に対する問い合わせ・絞込み処理が１回で行うことができる。
【００８３】
次に、実行木を作成する（ステップ２０３）。図１５に示すように、問い合わせノードを葉とし、先祖子孫関係を示す関係判定ノードを作成していく（ステップ２０４）。
【００８４】
次に、実行木に沿って、各処理を行っていく。まずは、葉ノードである問い合わせノードに対応するノード情報（範囲ラベル）をノード管理部１２０から取得する（ステップ２０５）。文書ＩＤを"001"、範囲ラベルを図５に示す例とした場合、対応するノードは、図１６に示すようになる。
【００８５】
取得したノード情報群に対し、図１６（Ａ）の場合は、従来通り範囲ラベルによる構造ジョインを行って関係判定を行う（ステップ２０８、ステップ２０９，ステップ２１０）。ここで、「構造ジョイン」とは、直接親子関係だけでなく先祖子孫関係に対し、判別の組み合わせを選択することを指す。図１６（Ｂ）の場合は、文書ＩＤ（この場合は"００１"の合致）により判定を行う（ステップ２０８，ステップ２０９、ステップ２１１）。
【００８６】
最終的に得たノード情報から検索結果を組み立てて返却する（ステップ２１３）。
【００８７】
なお、上記の実施の形態及び実施例における検索装置の構成要素の動作をプログラムとして構築し、検索装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００８８】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８９】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９０】
本発明は、ＸＭＬデータ処理に適用可能である。
【図面の簡単な説明】
【００９１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における検索装置の構成図である。
【図４】本発明の一実施例のノード情報をテーブル格納した例である。
【図５】本発明の一実施例の範囲ラベルの例である。
【図６】本発明の一実施例の格納フェイズの全体フローである。
【図７】本発明の一実施例のノード管理部のフロー（格納フェイズ）である。
【図８】本発明の一実施例のパスインデクス部のフロー（格納フェイズ）である。
【図９】本発明の一実施例のパスインデクス記憶部に要約情報（ストリングデータガイド）をmulti情報も含めテーブル格納した例である。
【図１０】本発明の一実施例の要約情報とノード情報の関連を示す図である。
【図１１】ストロングデータガイド例である。
【図１２】本発明の一実施例の複数出現情報を付与したストロングデータガイドの例である。
【図１３】本発明の一実施例の検索フェイズのフローである。
【図１４】本発明の一実施例の問い合わせ木の例である。
【図１５】本発明の一実施例の実行木の例である。
【図１６】本発明の一実施例の実行例である。
【図１７】ＸＭＬデータとその構造の例である。
【符号の説明】
【００９２】
１０  ＸＭＬデータ記憶装置
１００  検索装置
１１０  パスインデクス手段、パスインデクス部
１１１  パスインデクス記憶手段、パスインデクス記憶部
１２０  ノード管理手段、ノード管理部
１２１  ノード情報記憶手段、ノード情報記憶部
１３０  値インデクス部
１３１  値インデクス記憶部
１４０  検索手段、検索部
１４１  実行木作成手段
１４２  ノード情報取得手段
１４３  関係判定手段
【図１】
2010108192.tif 000008
【図２】
2010108192.tif 000009
【図３】
2010108192.tif 000010
【図４】
2010108192.tif 000011
【図５】
2010108192.tif 000012
【図６】
2010108192.tif 000013
【図７】
2010108192.tif 000014
【図８】
2010108192.tif 000015
【図９】
2010108192.tif 000016
【図１０】
2010108192.tif 000017
【図１１】
2010108192.tif 000018
【図１２】
2010108192.tif 000019
【図１３】
2010108192.tif 000020
【図１４】
2010108192.tif 000021
【図１５】
2010108192.tif 000022
【図１６】
2010108192.tif 000023
【図１７】
2010108192.tif 000024