(57)【要約】【課題】  構造化データであるＸＭＬデータ群に対して、効率的に結合検索を行う。【解決手段】  本発明は、問い合わせ木をノード情報を利用して実行木に展開し、実行木に従って実行ノードを選択し、実行ノードの結合条件の結合キーノード群について結合を行い、結合したペア毎に結合ＩＤを付与し、検索記憶手段に格納し、ノード記憶手段から検索の単位となる検索ノード群のノード情報を取得し、該検索ノード群に対し、結合キーノード群のノード情報の範囲ラベルに基づいて該当するものをマッチングし、マッチする検索ノード群を当該結合キーノード群の結合ＩＤと共に取得し、該検索ノード群と該結合キーノード群を結合し、検索記憶手段に格納し、検索クエリの指定に基づいて検索記憶手段に格納されている情報から結果を生成する。【選択図】  図１
2010267081.tif 000002
【特許請求の範囲】
【請求項１】
構造化データであるＸＭＬデータ群に対して、蓄積及び検索する装置における情報検索方法であって、
入力された検索クエリで指定された検索パス及び検索キーワードに基づいて、ＸＭＬの構造をパス単位で格納したパスインデクス記憶手段と、ＸＭＬの各ノード間の関係を保持するための、親ノードが子ノードを含むノードＩＤで表される範囲ラベルをノードＩＤとするノード情報を格納したノード記憶手段を参照して、問い合わせ木を生成し、該問い合わせ木の処理対象となるパスに対し、ノード群を取得する処理、それらの先祖子孫関係の判定処理、ノード群の結合処理、最終的な結合結果を生成する結果生成処理の各処理種別のノードを含む実行木を生成する実行木生成ステップと、
前記実行木の各実行ノードにおいて、子ノードがある場合は該子ノードの結果を取得し、当該ノードの処理種別に応じた処理を行い、最終的な結果を出力する検索ステップと、
を行うことを特徴とする情報検索方法。
【請求項２】
前記検索ステップは、
前記実行木の実行ノードが結合条件を有しているとき、該結合条件で指定されているノード群（結合キーノード群）について結合を行い、結合したペア毎に結合ＩＤを付与し、検索記憶手段に格納し、
前記ノード記憶手段から、検索の単位となるノード群（検索ノード群）のノード情報を取得し、該検索ノード群に対し、前記結合キーノード群のノード情報の前記範囲ラベルに基づいて該当するものをマッチングし、マッチする検索ノード群を当該結合キーノード群の結合ＩＤと共に取得し、該検索ノード群と該結合キーノード群を結合し、検索記憶手段に格納し、
前記検索クエリの指定に基づいて前記検索記憶手段に格納されている情報から結果を生成する
請求項１記載の情報検索方法。
【請求項３】
構造化データであるＸＭＬデータ群に対して、蓄積及び検索する装置における情報検索装置であって、
ＸＭＬの構造をパス単位で格納したパスインデクス記憶手段と、
ＸＭＬの各ノード間の関係を保持するための、親ノードが子ノードを含むノードＩＤで表される範囲ラベルをノードＩＤとするノード情報を格納したノード記憶手段と、
入力された検索クエリで指定された検索パス及び検索キーワードに基づいて、前記パスインデクス記憶手段と前記ノード記憶手段を参照して、問い合わせ木を生成し、該問い合わせ木の処理対象となるパスに対し、ノード群を取得する処理、それらの先祖子孫関係の判定処理、ノード群の結合処理、最終的な結合結果を生成する結果生成処理の各処理種別のノードを含む実行木を生成する実行木生成手段と、
前記実行木の各実行ノードにおいて、子ノードがある場合は該子ノードの結果を取得し、当該ノードの処理種別に応じた処理を行い、最終的な結果を出力する検索実行手段と、
を有することを特徴とする情報検索装置。
【請求項４】
前記検索実行手段は、
前記実行木の実行ノードが結合条件を有しているとき、該結合条件で指定されているノード群（結合キーノード群）について結合を行い、結合したペア毎に結合ＩＤを付与し、検索記憶手段に格納する手段と、
前記ノード記憶手段から、検索の単位となるノード群（検索ノード群）のノード情報を取得し、該検索ノード群に対し、前記結合キーノード群のノード情報の前記範囲ラベルに基づいて該当するものをマッチングし、マッチする検索ノード群を当該結合キーノード群の結合ＩＤと共に取得し、該検索ノード群と該結合キーノード群を結合し、検索記憶手段に格納する手段と、
前記検索クエリの指定に基づいて前記検索記憶手段に格納されている情報から結果を生成する手段と、
を含む請求項３記載の情報検索装置。
【請求項５】
請求項３または４記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索方法及び装置及びプログラムに係り、特に、構造化データである多数のＸＭＬデータを蓄積及び検索するデータベース及びインデクスの分野で、結合検索実行時の処理を効率化し、高速に行う情報検索方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
ＸＭＬとは、マークアップ言語の一つで、ＸＭＬで記述されたデータは構造化され、構造に意味を持ったデータである。図１３は、ＸＭＬデータとその構造を示した図である。ＸＭＬデータを構成する要素を識別するために使われるマークをタグと呼び、タグに挟まれた間に値（テキスト）を記述する。タグは入れ子にすることができる。
【０００３】
したがって、ＸＭＬデータはモデル的に木構造で表すことができ、各節をノードと呼ぶ。特に、値のノードをルート要素、値（記述内容）をテキストノード、タグ中に記述されたものを属性と呼ぶ。
【０００４】
各ノードは、"／"の後ろにルート要素からのタグを"／"でつなげた「パス」で指定する。例えば、本のタイトルを示したい場合、パスを「/book/title」と指定する。
【０００５】
ＸＭＬデータに対して効率的な検索を実現しようとした場合、構造の任意の場所にある記述内容を高速に取り出すことが可能でなければならない。一般的には、ＸＭＬデータの構造と記述内容を記述したインデクス（構造インデクス）を予め構築しておく。構造インデクスの構築は様々な方法が存在するが、多くの場合、ＸＭＬデータの持つ全てのパスとパスに指定される記述内容を関係づけるインデクスが構築される。以上のようなＸＭＬデータの効率的な検索を実現する一手法として、ＸＭＬデータの要約情報に範囲ラベルを付与して保持し、検索時に、問い合わせを木構造に変換して値の部分を削除した問い合わせ木の構造部を生成し、中間問い合わせ木と要約情報を照合して中間要約木の集合を生成し、ＸＭＬデータに対して中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、ＸＭＬデータに対して、実体中間も木の集合に対応する値の部分を用いてフィルタ処理を行うことで、ＸＭＬデータの効率的な検索を実現する技術がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２２８１５５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
検索の一パターンとして、２種類（同一種類でも可）のＸＭＬデータ群の結合がある。例えば、図１４に示されるような「クラス情報ＸＭＬ」「受講者ＸＭＬ」の２種類のＸＭＬ群がある場合、受講者のＩＤを示す「クラス情報ＸＭＬ」の
"/course/students/student_id/text()"("text()"はテキストノードを示す)
と「受講者ＸＭＬ」の
【０００８】
【数１】
2010267081.tif 000003
をキーに２つの情報を結合させ、図１５に示すような受講者のプロファイル情報を加えたクラス情報を取得したといった検索が考えられる。
【０００９】
この例の結合の検索クエリは、ＸＭＬ問い合わせ言語１つであるXQueryでは、図１６のように記述できる。
【００１０】
単純な検索処理手法としては、各ＸＭＬデータのルート要素から順次子ノードを辿っていき、検索条件に合ったノード群を探し出す方法があるが、大きなデータや多数のデータ群の場合や、パスが深いところを指している場合などには、走査に時間がかってしまう。そこで、前述の特許文献１に示すような、処理に必要なノード群だけを直接取り出し、それらの親子及び先祖子孫関係を判定することで、効率的な検索が行われる。
【００１１】
しかし、当該手法は、結合検索にまでは言及されておらず、効率的な手法は提案されていない。したがって、結合検索となる双方のＸＭＬデータ群を特許文献１に示すような効率的な検索を行った後、結合処理を単純な手法で一つ一つ突合せていく方法が考えられるが、図１６の例のように結合条件
（"$a/students/student_id/text()=$b/@id"）
以外に条件がない場合などは、中間結果が多くなりすぎて、効率化にはつながらないケースがある。
【００１２】
また、結合処理については、関係データベース（ＲＤＢ：Relational Data Base）においては効率的な手法が実現されているが、ＸＭＬデータの結合は以下の点で異なるため、そのままでは適用できない。
【００１３】
ＲＤＢの場合、結合の単位（タプル）と結合条件となるキーは１対１関係にある（図１７参照）が、ＸＭＬの場合は１対Ｎ関係となる。例えば、上記の例の場合、「クラス情報ＸＭＬ」の結合の単位は、
"/course"
以下の部分木、つまり文書全体であるが、結合条件となるキー
"/course/students/students_id"
は文書内に複数個ある。
【００１４】
つまり、Ｎ個のキー同士のどれかのペアがマッチすれば「真」という結合が必要になる。
【００１５】
本発明は、上記の点に鑑みなされたもので、効率的に結合検索を行うことが可能な情報検索方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
図１は、本発明の原理を説明するための図である。
【００１７】
本発明（請求項１）は、構造化データであるＸＭＬデータ群に対して、蓄積及び検索する装置における情報検索方法であって、
入力された検索クエリで指定された検索パス及び検索キーワードに基づいて、ＸＭＬの構造をパス単位で格納したパスインデクス記憶手段と、ＸＭＬの各ノード間の関係を保持するための、親ノードが子ノードを含むノードＩＤで表される範囲ラベルをノードＩＤとするノード情報を格納したノード記憶手段を参照して、問い合わせ木を生成し（ステップ１）、該問い合わせ木の処理対象となるパスに対し、ノード群を取得する処理、それらの先祖子孫関係の判定処理、ノード群の結合処理、最終的な結合結果を生成する結果生成処理の各処理種別のノードを含む実行木を生成する（ステップ２）実行木生成ステップと、
実行木の各実行ノードにおいて、子ノードがある場合は該子ノードの結果を取得し、当該ノードの処理種別に応じた処理を行い（ステップ３）、最終的な結果を出力する（ステップ４）検索ステップと、を行う。
【００１８】
また、本発明（請求項２）は、検索ステップにおいて、
実行木の実行ノードが結合条件を有しているとき、該結合条件で指定されているノード群（結合キーノード群）について結合を行い、結合したペア毎に結合ＩＤを付与し、検索記憶手段に格納し、
ノード記憶手段から、検索の単位となるノード群（検索ノード群）のノード情報を取得し、該検索ノード群に対し、結合キーノード群のノード情報の範囲ラベルに基づいて該当するものをマッチングし、マッチする検索ノード群を当該結合キーノード群の結合ＩＤと共に取得し、該検索ノード群と該結合キーノード群を結合し、検索記憶手段に格納し、
検索クエリの指定に基づいて検索記憶手段に格納されている情報から結果を生成する。
【００１９】
図２は、本発明の原理構成図である。
【００２０】
本発明（請求項３）は、構造化データであるＸＭＬデータ群に対して、蓄積及び検索する装置における情報検索装置であって、
ＸＭＬの構造をパス単位で格納したパスインデクス記憶手段１と、
ＸＭＬの各ノード間の関係を保持するための、親ノードが子ノードを含むノードＩＤで表される範囲ラベルをノードＩＤとするノード情報を格納したノード記憶手段２と、
入力された検索クエリで指定された検索パス及び検索キーワードに基づいて、パスインデクス記憶手段とノード記憶手段を参照して、問い合わせ木を生成し、該問い合わせ木の処理対象となるパスに対し、ノード群を取得する処理、それらの先祖子孫関係の判定処理、ノード群の結合処理、最終的な結合結果を生成する結果生成処理の各処理種別のノードを含む実行木を生成する実行木生成手段４１と、
実行木の各実行ノードにおいて、子ノードがある場合は該子ノードの結果を取得し、当該ノードの処理種別に応じた処理を行い、最終的な結果を出力する検索実行手段４２と、を有する。
【００２１】
また、本発明（請求項４）の検索実行手段４２は、
実行木の実行ノードが結合条件を有しているとき、該結合条件で指定されているノード群（結合キーノード群）について結合を行い、結合したペア毎に結合ＩＤを付与し、検索記憶手段に格納する手段と、
ノード記憶手段２から、検索の単位となるノード群（検索ノード群）のノード情報を取得し、該検索ノード群に対し、結合キーノード群のノード情報の前記範囲ラベルに基づいて該当するものをマッチングし、マッチする検索ノード群を当該結合キーノード群の結合ＩＤと共に取得し、該検索ノード群と該結合キーノード群を結合し、検索記憶手段に格納する手段と、
検索クエリの指定に基づいて検索記憶手段に格納されている情報から結果を生成する手段と、を含む。
【００２２】
本発明（請求項５）は、請求項３または４記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラムである。
【発明の効果】
【００２３】
上記のように本発明によれば、ＸＭＬの階層構造を順次辿る中間処理を行うことなく、必要最小限のノード群のみを直接取り扱うことで、効率的に結合検索を行うことができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における情報検索装置の構成図である。
【図４】本発明の一実施の形態におけるＸＭＬの結合例である。
【図５】本発明の一実施の形態におけるXQueryの例である。
【図６】本発明の一実施の形態におけるパス情報とノード管理のノード情報の格納例である。
【図７】本発明の一実施の形態におけるノード管理部の範囲ラベルの例である。
【図８】本発明の一実施の形態における検索処理のフローチャートである。
【図９】本発明の一実施の形態におけるノード取得処理のフローチャートである。
【図１０】本発明の一実施の形態における検索部で生成される問い合わせ木の例である。
【図１１】本発明の一実施の形態における検索部で生成される実行木の例である。
【図１２】本発明の一実施の形態における実行例での中間結果である。
【図１３】ＸＭＬデータとその構造の例である。
【図１４】２つのＸＭＬデータの例である。
【図１５】ＸＭＬデータの結合例である。
【図１６】結合のXQuery例である。
【図１７】ＲＤＢでの結合例である。
【発明を実施するための形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
本発明は、ＸＭＬの階層構造を順次辿ることなく、必要最低限のノード群のみを直接取り扱うことで、効率的に結合検索を行う手法（例えば、特許文献１）をベースに、ＲＤＢで実現されている結合処理を組み合わせることで、ＸＭＬデータ群に対する効率的な結合処理を実現するものであある。
【００２７】
図３は、本発明の一実施の形態における情報検索装置の構成を示す。
【００２８】
同図に示す情報検索装置は、ＸＭＬの構造をパス単位で保持するパスインデクス部１、ＸＭＬの各ノード間のＸＭＬ構造における関係を把握するノード管理部２、各ノードの値のインデクスを構築及び管理する値インデクス部３と、（結合）検索を実行する検索部４とを有する。パスインデクス部１とノード管理部２は、前述の背景技術の項における構造インデクスにあたる。
【００２９】
パスインデクス部１は、ＸＭＬデータの持つ全てのパスとパスに指定されるノードを関係付けるインデクスを構築し、内部の記憶手段に格納する。
【００３０】
ノード管理部２は、各ノード間のＸＭＬデータの構造上の関係を内部の記憶手段に保持する。一般的には、構造上の関係を管理するために、ＸＭＬデータの各ノードにＩＤを付与し、ノード間の関係（先祖子孫関係など）を範囲ラベルとして保持する。
【００３１】
値インデクス部３は、テキストノード及び属性の値に対するインデクス（B−Tree、ハッシュ等）を構築し、内部の記憶手段に保持する。検索するだけであれば不要のものであるが、高速検索を実現するためには必要となる。
【００３２】
検索部４の処理は以下の手順で行う。以下、用語として、検索の単位となるノード（群）を「検索ノード（群）」、結合条件となるノード（群）を「結合キーノード（群）」と呼ぶこととする。
【００３３】
前述の図１６のクエリの例の場合、"$a"、"$b"にセットされた全データの"/course"及び"/profile"がそれぞれの検索ノード群であり、where句で条件とされている
"/course/students/student_id/text()"
及び、
【００３４】
【数２】
2010267081.tif 000004
が結合キーノード群となる。
【００３５】
（１）双方の結合キーノード群について、そのノード群の単位で結合処理を行う（以降、当該処理を「キー結合」処理と呼ぶ）。
【００３６】
これは、ＲＤＢと同等の処理方法で実現できる。その際、マッチしたペアを識別できる結合ＩＤ（双方もしくは片方のノードＩＤでも可）を付与し、当該検索部４内のメモリ（図示せず）に保持する。
【００３７】
（２）双方の検索ノード群を取得する。（その際、（１）で得た結合キーノード群を含むXMLデータのみに限定して取得するとより効率的である）。
【００３８】
（３）XMLデータ群ごとに（２）で得た検索ノード群に対し、（１）で得た結合キーノード群から、（ノードIDによる親子及び先祖子孫関係判定を用い）該当するものをマッチングし、マッチする検索ノード群を、結合ＩＤ（群）と共に取得する。
【００３９】
（４）双方の検索ノード群の対応を結合ＩＤ（群）により判定し、結合を行う。但し、この場合、結果の単位（まとめ方）はクエリ指定に依存する。
【００４０】
（５）検索ノードを基軸とし、結果に必要な（return句に指定されている）ノードに取得し、結果を生成し、返却する。
【００４１】
すなわち、結合条件について結合キーノードのレベルでRDBの結合処理と同等の処理を行うことで、候補を絞り込むことができ、更に結合ＩＤを保存しておくことで、最終的な検索ノード同士の結合処理も効率化を図ることができる。
【００４２】
上記の（４）について補足すると、図１６のクエリの場合、"$a"は"for"文で指定されているため、検索ノード"$a"の単位で結果が纏められる（図１５）。一方、図４のように"$b"の単位で結果を得ることも可能で、その場合のXQueryは、図５のように"$b"も"for"文で指定することで、内側の"for"である検索ノード"$b"の単位で結果が纏められる。
【００４３】
また、結合条件が複数ある場合は、それぞれの結合条件に対し、結合ＩＤ(群)を保持し、その組み合わせの判定を（４）において行うことで対応できる。
【００４４】
また、図５のクエリのように、他の絞り込み条件（"$a/meta/grade='初級クラス'"）がある場合は、（１）〜（３）及びその前後の適切なタイミングで絞り込みを行うことで対応できる（適切な順序は、絞り込み条件と対象データ群により変化する）。
【００４５】
以下に、実現方法の一形態として、特許文献１の手法をベースした例を説明する。
【００４６】
図３に示す各構成要素について詳細に説明する。
【００４７】
パスインデクス部１は、パス情報を内部の記憶手段で管理するモジュールで、パスとパスに対応する各データのノードへの関係の保持も含まれる。パス情報の格納例を図６（Ａ）に示す。パスとそのパスに対するＩＤを保持する。
【００４８】
ノード管理部２は、各ノードの情報を内部の記憶手段に格納し管理する。ノードの情報とは、図６（Ｂ）に示すように、パスインデクス部１のパスＩＤに対応するパスＩＤ、データ毎のＩＤ（文書ＩＤ）、ノードＩＤ（範囲ラベル）、タグ、値等から構成される。範囲ラベルは、図７に示すようにノード毎に２値で表され、親ノードが子ノードを含むように付与する。これにより、任意のノード間で親子及び先祖子孫関係を判定可能となる。この例では、文書ＩＤ１０１と２０１の例のみを示しているが、今回の場合は、各ＸＭＬ群で同一の構造であるため、他のＸＭＬに対しても同様の範囲ラベルが付与される（一般的には、同じパスに対しても同一の範囲ラベルとは限らない）。
【００４９】
値インデクス部３は、テキストノード及び属性の値に対するインデクス（B-Tree、ハッシュ等）を構築し、内部の記憶手段に格納・管理する。少なくともパスとその値の制限を条件に、検索が可能な形とする。例えば、パスと値の両方をキーに全てを対象としたインデクスを１つ作成してもよいし、パス毎に別々のインデクス（値がキーとなる）を作成してもよい。
【００５０】
検索部４は、検索クエリを受け取り、指定された検索パス及び検索キーワードにマッチするノードを、パスインデクス部１、ノードインデクス部２、値インデクス部３の各記憶手段から特定し、必要であればデータベース等のデータ管理部（図示せず）から返却結果を取得し、返却する。
【００５１】
検索部４における結合検索の処理を以下に示す。
【００５２】
図８は、本発明の一実施の形態における結合検索の処理のフローチャートである。
【００５３】
ステップ１１０）  検索部４は取得した検索クエリから、問い合わせ木を生成する。
【００５４】
ステップ１２０）  次に、ノード管理部２のノード情報を用いて問い合わせ木に対する実行木を作成する。
【００５５】
ステップ１３０）  実行木に従って、ノード種別「ノード取得」「関係判定」「結合」「結果生成」等の実行ノードを選択する。
【００５６】
ステップ１４０）  実行ノード種別が「ノード取得」である場合は、ステップ１５０に移行し、「関係判定」である場合はステップ１６０に移行し、「結合」の場合はステップ１０７に移行し、「結果生成」の場合はステップ１８０に移行する。
【００５７】
ステップ１５０）  実行ノード種別が「ノード取得」である場合は、パスインデクス部１、ノード管理部２からノード情報を取得し、ステップ１９０に移行する。
【００５８】
ステップ１６０）  実行ノード種別が「関係判定」である場合は、ノード管理部２からノード情報を取得し、範囲ラベルに従って親子／先祖子孫関係を判定し（文書ＩＤの突き合わせ、範囲ラベルによる構造ジョイン）、ステップ１９０に移行する。
【００５９】
ステップ１７０）  実行ノード種別が「結合」である場合は、ノード管理部２からノード情報を取得し、値インデクスも必要に応じ利用し結合を行うと共に、結合ＩＤを付与する。また、同じ結合ＩＤ同士を結合し、ステップ１９０に移行する。
【００６０】
ステップ１８０）  実行ノード種別が「結果生成」である場合は、返却するための結果を生成し、ステップ１９０に移行する。
【００６１】
ステップ１９０）  全ての実行ノードについて、ステップ１３０以降の処理を繰り返す。
【００６２】
次に、上記のステップ１５０について詳細に説明する
図９は、本発明の一実施の形態におけるノード取得処理のフローチャートである。
【００６３】
ステップ１５１）  実行ノード種別が「ノード取得」である場合、結合条件を持つかを判定し、持つ場合には、ステップ１５２に移行し、持たない場合はステップ１５６に移行する。
【００６４】
ステップ１５２）  キー結合が実行済みである場合はステップ１５５に移行し、まだ実行していない場合はステップ１５３に移行する。
【００６５】
ステップ１５３）  パスインデクス部１及びノード管理部２から該当する双方の結合キーノード情報を取得する。
【００６６】
ステップ１５４）  ステップ１５３で取得した結合キーノード情報に基づいて値インデクス部３に問い合わせ、結合キーノード情報に対応するキーＩＤを取得し、キー結合処理を行う。
【００６７】
ステップ１５５）  キー結合結果から結合ＩＤと共に、ノード情報を取得し、当該処理を終了する。
【００６８】
ステップ１５６）  結合条件を持たない場合は、パスインデクス部１、ノード管理部２から該当するノード情報（群）を取得する。
【００６９】
ステップ１５７）  値インデクス部１に問い合わせ、値の制約を満たすものだけに絞り込み、当該処理を終了する。
【００７０】
以下に、上記の図８、図９の処理の具体的な例として図１４のデータ群が図７のラベル付けがされ検索部４のメモリ（図示せず）に格納されている場合に、図５のクエリを実行する手順を示す。
【００７１】
検索部４は、問い合わせ木を生成する。ここで作成する問い合わせ木は、図１０のようになる。同図において二重線の部分（「course」「profile」）が処理対象となるパスを表しており、破線の矢印が指されているパスには値に制約が付いていることを示している。
【００７２】
次に、検索部４は、図１１に示すような実行木を作成する。問い合わせ木の処理対象となるパスに対し、ノード群を取得する処理（ノード取得）を葉とし、それらの先祖子孫関係の判定を節にする。ノード取得には、値の制約が付与される場合があり、結合条件も制約の一種として双方の葉に共通的に付与する。実行木の根には、最終的な結合結果を生成する結果生成処理が配置され、その直下に、クエリ例では、"$a"、"$b"にセットされた２つの検索ノード群の結合処理とする。
【００７３】
木の形は実行順序を表している。複数の選択肢があるため、何らかの実行計画の最適化処理を行うことが望ましいが、本発明では対象外であるのでその説明を省略する。実行ノードを選択し、実行木の葉から根に向かって処理を進めていく。
【００７４】
ノードＩＤを［文書ＩＤ，(範囲ラベル)］の形式で表すと、以下の手順で処理される。
【００７５】
（１）Ｐ５："/course/meta/grade/text()制約：＝'初級クラス'"のノード取得
結合条件は持っていないため、パスインデクス部１、ノード管理部２からパスに該当するノード情報を取得し、値インデクス部３により制約を満たすノードのみに絞り込む。"初級クラス"という値を該当パスに持つものは、文書１０１、及び１０２のノードとなるので、以下が得られる。
【００７６】
'初級クラス'[101,(6,7)]，'初級クラス'[10２,(6,7)]
（２）Ｐ６："/course"のノード取得
結合条件は持っていないため、パスインデクス部１、ノード管理部２から、パスに該当するノード情報を取得する（制約を持たないため、値インデクス部３により絞り込んでも同じ）全ての文書に該当パスを持つノードが存在するため、以下が得られる。
【００７７】
[101,(1,36)]，[102,(1,36)]，[103,(1,36)]*
ただし、上記の[103,(1,36)]*のノードは、（１）の結果から文書ＩＤを利用し、この段階で取り除くことも可能である。なお、以降も、事前の処理結果の文書ＩＤを利用し、同様に取り除くことが可能なノードについては、「＊」を付与する。
【００７８】
（３）Ｐ４：Ｐ５とＰ６の先祖子孫関係判定
この例では、先祖側のＰ６のノードを残す形で、Ｐ６が先祖でＰ５が子孫の関係のノードを取得する。
【００７９】
[101,(1,36)](←子孫101,[6,7])，[102,(1,36)](←子孫102,[6,7])
（４）Ｐ７："/course/students/student_id/text()制約：キー結合"のノード取得
結合条件を持っており、まだキー結合が実行されていないため、まずキー結合を実行する。パスインデクス部１、ノード管理部２からＰ７とＰ９双方のノード情報を取得し、値インデクス部３も必要に応じ利用し、結合を行うと共に、結合ＩＤも付与する。キー結合結果として、以下が得られる。
【００８０】
【表１】
2010267081.tif 000005
本例では、結合ＩＤとしてＰ７の［文書ＩＤ，範囲ラベルの第１値］を利用することとしている（こうすることで、後述の（９）．Ｐ２の結合処理時に効率的な処理が期待できる）。
【００８１】
次に、得られたキー結合結果から、Ｐ７のノードＩＤと結合ＩＤを取り出し、ノード取得結果が得られる。
【００８２】
【表２】
2010267081.tif 000006
（５）Ｐ３：Ｐ４とＰ７の先祖子孫関係判定
先祖側のＰ４のノードを残す形で、Ｐ４が先祖でＰ７が子孫の関係のノードを取得する。その際、結合ＩＤも検索部４の内部のメモリ（図示せず）に保持しておく。
【００８３】
【表３】
2010267081.tif 000007
（６）Ｐ９："/profile/@id制約：キー結合"のノード取得
結合条件を持っており、キー結合結果も（１）で得られているため、キー結合結果から、Ｐ９のノードＩＤと結合ＩＤを取り出し、ノード取得結果を得る。
【００８４】
【表４】
2010267081.tif 000008
（７）Ｐ１０："/profile"のノード取得
結合条件は持っていないため、パスインデクス部１、ノード管理部２から、パスに該当するノード情報を取得する（制約を持たないため、値インデクス部３により絞り込んでも同じ）全ての文書に該当パスを持つノードが存在するため、以下が得られる。
【００８５】
[201,(1,2)]，[202,(1,12)]，[203,(1,12)]，[204,(1,12)]*，[205,(1,12)]*，[206,(1,12)]*，
[207,(,12)]
（８）Ｐ８：Ｐ９とＰ１０の先祖子孫関係判定
先祖側のＰ１０のノードを残す形で、パスインデクス部１、ノード管理部２からＰ１０が先祖でＰ９が子孫の関係のノードを取得する。その際、結合ＩＤも保持しておく。
【００８６】
【表５】
2010267081.tif 000009
（９）Ｐ２：Ｐ３とＰ８の結合
同じ結合ＩＤを含むもの同士で結合を行うが、本例では、"$b"にあたるＰ８側の単位で結合する。
【００８７】
【表６】
2010267081.tif 000010
参考までに、個々までの処理の中間結果を記したものを図１２に示す。
【００８８】
（１０）Ｐ１：結果生成
最後のＰ１でreturn句に従って返却結果を作成すると、図４のようになる。返却対象のノードの取得も、上記手順と類似した方法で行うことができるが、本発明では対象外であるため、その説明を省略する。
【００８９】
なお、図３に示す検索部４の動作をプログラムとして構築し、情報検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９０】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００９１】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９２】
本発明は、構造化データである多数のＸＭＬデータの蓄積や検索技術に適用可能である。
【符号の説明】
【００９３】
１  パスインデクス記憶手段、パスインデクス部
２  ノード記憶手段、ノード管理部
３  値インデクス記憶手段、値インデクス部
４  検索部
４１  実行木生成手段
４２  検索実行手段
４５  メモリ
【図１】
2010267081.tif 000011
【図２】
2010267081.tif 000012
【図３】
2010267081.tif 000013
【図４】
2010267081.tif 000014
【図５】
2010267081.tif 000015
【図６】
2010267081.tif 000016
【図７】
2010267081.tif 000017
【図８】
2010267081.tif 000018
【図９】
2010267081.tif 000019
【図１０】
2010267081.tif 000020
【図１１】
2010267081.tif 000021
【図１２】
2010267081.tif 000022
【図１３】
2010267081.tif 000023
【図１４】
2010267081.tif 000024
【図１５】
2010267081.tif 000025
【図１６】
2010267081.tif 000026
【図１７】
2010267081.tif 000027