(57)【要約】【課題】  ＸＭＬデータに対する問合せにおいて、無駄なリンクの参照をなくして、効率よく問合せの処理を行う装置を提供することを目的とする。【解決手段】  検索の対象となるＸＭＬデータの登録時に、ＸＭＬデータローダ部２３０が、ＸＭＬデータの要約情報を構成し、前記要約情報に範囲ラベルを付与して、二次記憶装置１３０に記憶する。検索時に、ＸＭＬデータに対する問合せと要約情報を入力として、問合せ解析部１５０が、前記問合せを木構造に変換して値の部分を削除した問合せ木の構造部を生成し、問合せ実行部１７０が、中間問合せ木と要約情報を照合して中間要約木の集合を生成し、前記ＸＭＬデータに対して前記中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、前記ＸＭＬデータに対して、前記実体中間木の集合に対応する値の部分を用いてフィルタ処理を行い、問合せ結果を出力する。【選択図】      図１
2010192001.tif 000002
【特許請求の範囲】
【請求項１】
演算手段と記憶手段を少なくとも備えた計算機を用いて実現するＸＭＬデータ処理装置であって、
前記ＸＭＬデータ処理装置が、
ＸＭＬデータを解析する手段とＸＭＬデータを記憶する手段を備え、
検索の対象となるＸＭＬデータの登録時に、前記ＸＭＬデータを解析する手段が、前記ＸＭＬデータの構成に関する木構造の要約情報を作成し、
前記要約情報に前記ＸＭＬデータのノード間の先祖子孫関係を判定可能なラベルを付与し、
前記ＸＭＬデータを記憶する手段が、前記ＸＭＬデータ、前記要約情報および前記ラベルを記憶し、
前記ＸＭＬデータを解析する手段は、
ＸＭＬデータのＳＡＸイベントシーケンスを入力として、
ＳＡＸイベントが開始イベントであり当該ＳＡＸイベントのタグ名が前記要約情報に含まれていない場合には、そのタグ名で子ノードを前記要約情報に追加して追加した子ノードを現在ノードとし、
ＳＡＸイベントが開始イベントであり当該ＳＡＸイベントのタグ名が前記要約情報に含まれている場合には、そのタグ名の子ノードを現在ノードとし、
ＳＡＸイベントが終了イベントである場合には、現在ノードを現在ノードの親ノードに移動することによって、前記ＸＭＬデータの要約情報を作成する
ことを特徴とするＸＭＬデータ処理装置。
【請求項２】
前記先祖子孫関係を判定可能なラベルが、木構造の中で検索の対象となるノードを特定する機能を持つ範囲ラベルである
ことを特徴とする請求項１に記載のＸＭＬデータ処理装置。
【請求項３】
演算手段と記憶手段を少なくとも備えた計算機が実行するＸＭＬデータ処理方法であって、
請求項１または請求項２に記載のＸＭＬデータ処理装置を実現することを特徴とするＸＭＬデータ処理方法。
【請求項４】
演算手段と記憶手段を少なくとも備えた計算機が実行するプログラムであって、
請求項１または請求項２に記載のＸＭＬデータ処理装置を実現することを特徴とするＸＭＬデータ処理プログラム。
【請求項５】
演算手段と記憶手段を少なくとも備えた計算機が実行するプログラムを記録した記憶媒体であって、
請求項１または請求項２に記載のＸＭＬデータ処理装置を実現するＸＭＬデータ処理プログラムを記録していることを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬ（eXtensible Markup Language）データを高速に処理するＸＭＬデータ処理装置、ＸＭＬデータ処理方法、ＸＭＬデータ処理プログラムおよびＸＭＬデータ処理プログラムを記録した記憶媒体に関する。
【背景技術】
【０００２】
ＸＭＬデータ処理を高速化するための技術は、すでにいくつか公開されている。例えば、非特許文献１は、ＸＭＬデータに対する高速な構造ジョインアルゴリズムを提案している。ここで、構造ジョインとは、関係データベースのジョイン演算に類似した演算で、複数の検索結果を組み合わせる演算である（詳細は後記する）。また、非特許文献２では、ラベルを用いることで先祖子孫関係および親子関係を指定したデータベース検索を高速化している。そして、非特許文献３では、ＸＭＬデータの統計情報を用いることで、構造ジョイン演算の実行順序を最適化して検索を高速にする方法を提案している。
【非特許文献１】Shurug Al-Khalifa, H. V. Jagadish, Nick Koudas, Jignesh M. Patel, Divesh Srivastava, and Yuqing Wu著、 "Structural Joins: A Primitive for Efficient XML Query Pattern Matching", （米国） In Proc. ICDE (2002)
【非特許文献２】Quanzhong Li and BongkiMoon著、 "Indexing and Querying XML Data for Regular Path Expressions", （米国） In Proc. VLDB (2001)
【非特許文献３】Yuqing Wu, JigneshM. Patel, and H. V. Jagadish著、 "Structural Join Order Selection for XML Query Optimization", （米国） In Proc. ICDE (2003)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、これらの技術は、ＸＭＬデータが持っている構造を充分に活用し切れておらず、まだ、高速化する余地が残っていた。特に、コストが高い構造ジョイン演算の回数を減らすという点では、充分な対応が取られていないという問題があった。
【０００４】
そこで、本発明では、前記した問題を解決し、高速なＸＭＬデータ処理を実現するＸＭＬデータ処理装置、ＸＭＬデータ処理方法、ＸＭＬデータ処理プログラムおよびＸＭＬデータ処理プログラムを記録した記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【０００５】
前記の目的を実現するために、本発明では、
演算手段と記憶手段を少なくとも備えた計算機を用いて実現するＸＭＬデータ処理装置であって、
前記ＸＭＬデータ処理装置が、
ＸＭＬデータを解析する手段とＸＭＬデータを記憶する手段を備え、
検索の対象となるＸＭＬデータの登録時に、前記ＸＭＬデータを解析する手段が、前記ＸＭＬデータの構成に関する木構造の要約情報を作成し、
前記要約情報に前記ＸＭＬデータのノード間の先祖子孫関係を判定可能なラベルを付与し、
前記ＸＭＬデータを記憶する手段が、前記ＸＭＬデータ、前記要約情報および前記ラベルを記憶し、
前記ＸＭＬデータを解析する手段は、
ＸＭＬデータのＳＡＸイベントシーケンスを入力として、
ＳＡＸイベントが開始イベントであり当該ＳＡＸイベントのタグ名が前記要約情報に含まれていない場合には、そのタグ名で子ノードを前記要約情報に追加して追加した子ノードを現在ノードとし、
ＳＡＸイベントが開始イベントであり当該ＳＡＸイベントのタグ名が前記要約情報に含まれている場合には、そのタグ名の子ノードを現在ノードとし、
ＳＡＸイベントが終了イベントである場合には、現在ノードを現在ノードの親ノードに移動することによって、前記ＸＭＬデータの要約情報を作成する。
【０００６】
この構成によれば、ＸＭＬデータの要約情報を構成することができる。
【０００７】
【０００８】
【０００９】
また、本発明では、  前記先祖子孫関係を判定可能なラベルが、木構造の中で検索の対象となるノードを特定する機能を持つ範囲ラベルを用いる。
【００１０】
この構成によれば、範囲ラベルを用いて効率のよい検索が可能になる。
【００１１】
【００１２】
【００１３】
【００１４】
【００１５】
【００１６】
【００１７】
【００１８】
【００１９】
【００２０】
【００２１】
【００２２】
【００２３】
【００２４】
【００２５】
【００２６】
【００２７】
【００２８】
【発明の効果】
【００２９】
このようなＸＭＬデータ処理装置、ＸＭＬデータ処理方法、ＸＭＬデータ処理プログラムおよびＸＭＬデータ処理プログラムを記録した記憶媒体によれば、検索対象となるＸＭＬデータがもっているデータの構造を活用して、高速なＸＭＬデータの処理が可能になる。
【発明を実施するための最良の形態】
【００３０】
次に、本発明の実施形態について、適宜図面を参照しながら詳細に説明する。
【００３１】
<<第１の実施形態>>
［システム構成］
図１は、本発明の第１の実施形態におけるＸＭＬデータ処理装置１００の構成を説明する図である。ＸＭＬデータ処理装置１００は、主記憶装置１１０、ＣＰＵ（Central Processing Unit、中央演算装置）１２０および二次記憶装置１３０を備えた計算機にＸＭＬデータを処理するための計算機プログラムが読み込まれることで構成される。
【００３２】
問合せ解析部１５０は、ＸＭＬデータへの問合せ（図５参照）を字句解析および構文解析し、問合せの内部表現である問合せ木(図７参照)を生成する。また、問合せ解析部１５０は、問合せ木を構造部と値処理部に分離し、中間問合せ木を生成する。
【００３３】
問合せ最適化部１６０は、問合せ最適化を行う場合に、中間問合せ木から問合せ実行プラン（説明は後記する）を生成し、それぞれの実行プランのコストをＸＭＬデータの構成に関する情報や統計情報などから計算し、その中から最適な実行プランを選ぶ。
【００３４】
問合せ実行部１７０は、問合せ解析部１５０から渡された中間問合せ木、または、問合せ最適化部１６０から渡された実行プランを実行する。このとき、問合せ実行部１７０は、二次記憶装置１３０に格納されたＸＭＬデータおよびＸＭＬデータの木構造の情報を要約したデータガイド木（ストロングデータガイド木、請求項における要約情報に該当）２４０を対象として問い合わせを実行する。なお、二次記憶装置１３０には、後記するディスクマネージャ部１９０を介してアクセスし、データガイド木（ストロングデータガイド木）２４０には、イベントシーケンス生成部２１０を介してアクセスする。
【００３５】
構造ジョイン演算部１８０は、既存技術である構造ジョインの演算を行う。そして、このとき、ディスクマネージャ部１９０を介して二次記憶装置１３０にアクセスする。
【００３６】
なお、構造ジョインとは、関係データベースのジョイン演算に類似した演算である。関係データベースにおけるジョイン演算では、テーブルの結合処理の際に指定された項目の値が結合する両方のテーブルのエントリ（タプル）に共通に出現するエントリだけを対象としてその全ての組み合わせに対応するエントリを生成する。それに対して、ＸＭＬデータに対する構造ジョインでは、親子関係または先祖子孫関係の問合せを行うときに、個別に２つのタグ名を検索しておいて、これらの検索結果を親子関係または先祖子孫関係に基づいて組み合わせて、所望の検索結果を得るというものである。たとえば、「//Book//person」という問合せを行ったときに、「Book」を検索する演算と「person」を検索する演算を個別に行い、これらの検索結果を組み合わせて、「//Book//person」に対する結果を生成する。この際、親子関係または先祖子孫関係のリンクを辿る通常の方法を用いると全ての対象ノードに対する検索を必要とするが、後記する範囲ラベルを用いて対象ノードを限定して構造ジョインを行えば、効率的に所望のデータが得られる。
【００３７】
ディスクマネージャ部１９０は、二次記憶装置１３０に格納されたＸＭＬデータへのアクセス手段を提供する。
【００３８】
結果生成部２００は、既存技術を用いて問合せの処理結果を生成する。ＸＰａｔｈの問い合わせ処理結果は、結果ノードの指定する部分木であるため、結果生成部２００は、このような結果を生成する。
【００３９】
イベントシーケンス生成部２１０は、データガイド木（ストロングデータガイド木）２４０からイベントシーケンス（図４参照、説明は後記する）を生成する。なお、データガイド木（ストロングデータガイド木）２４０については、図８および図９を用いた説明において、後記する。
【００４０】
データガイド木ローダ部２２０は、二次記憶装置１３０に記録する前のＸＭＬデータ２０、または、記録後のＸＭＬデータ１４０からデータガイド木（ストロングデータガイド木）２４０をロードする。
【００４１】
ＸＭＬデータローダ部２３０は、ＸＭＬデータ２０を二次記憶装置１３０にロードする。ＸＭＬデータローダ部２３０は、データガイド木ローダ部２２０と並行して動くことができる。そして、ＸＭＬデータローダ部２３０は、主記憶装置１１０の容量に応じて、次の３つの方式でデータガイド木２４０に付与する範囲ラベル（詳細は後記）を格納する。
（１）主記憶装置１１０の容量が充分に大きい場合、範囲ラベルを主記憶装置１１０に全て格納する。
（２）主記憶装置１１０の容量が中程度の場合、範囲ラベルの一部を主記憶装置１１０に格納し、残りの一部を二次記憶装置１３０に格納する。
（３）主記憶装置１１０の容量が小さい場合、範囲ラベルは全て二次記憶装置１３０に格納する。
【００４２】
この格納方式は、利用者が選択することができる。（１）の場合は、主記憶装置１１０の中に範囲ラベルを全て保持するため、必要な容量は大きくなるが、構造ジョインが全て主記憶装置１１０内で完結するため、非常に高速に処理を行うことができる。
【００４３】
（２）の場合は、利用者の問合せに頻出するノードの範囲ラベルを主記憶装置１１０の中に保持することにより、（１）に比べて必要な一次記憶装置の容量を削減しつつも、頻出する問合せに関しては、効率よく処理できる。
【００４４】
（３）の場合は構造ジョインを実行する際に範囲ラベルを主記憶装置１１０に取り出す必要があるが、構造ジョイン回数は削減されるため、主記憶装置１１０の容量が少ない場合にも、効率のよい処理が可能になる。
【００４５】
本実施形態において、利用者１０は、ＸＰａｔｈの検索式を用いて、プログラミングＡＰＩや対話型インタフェースプログラムなどからデータベースに問合せを行う。利用者１０が入力したＸＰａｔｈの検索式は、問合せ解析部１５０で構文解析されて、問合せ木になり、問合せ木は、図１０に示すような構造部３００と値処理部３１０に分解されて、さらに、ストロングデータガイド木と組み合わせて処理されて、問合せ中間要約木に変換される。問合せ最適化部１６０は、中間木実体化処理および値処理部のフィルタリング処理の実行順序（プラン）を決定する。このとき、二次記憶装置１３０に格納されたＸＭＬデータの構成に関する情報やＸＭＬデータの統計情報等を用いる。そして、問合せ実行部１７０が、決定された実行順序（プラン）にそって検索処理を実行する。
【００４６】
［問合せ処理］
図２の（ａ）は、ＸＰａｔｈ処理の前に行うＸＰａｔｈ事前処理の概要を説明する図である。そして、図２の（ｂ）は、ＸＰａｔｈ処理の概要を説明する図である。
【００４７】
図２の（ａ）に示されているＸＰａｔｈ処理に先立って行なわれるＸＰａｔｈ事前処理では、予め与えられたＸＭＬデータに対応するストロングデータガイド木を生成する（Ｓ１００）。そして、このストロングデータガイド木を利用して、後記するＸＰａｔｈ処理を行う。
【００４８】
図２の（ｂ）に示されているＸＰａｔｈ処理では、まず、ストロングデータガイド木を元にイベントシーケンスを生成する（Ｓ１１０）。なお、このステップＳ１１０をＸＰａｔｈ事前処理において行ってもよい。
【００４９】
次に、ステップＳ１１０において作成したストロングデータガイド木に対応するイベントシーケンスを用いてＸＰａｔｈ処理を行う（Ｓ１２０）。ステップＳ１２０は、後記する中間要約木を得るまでの処理に該当する。なお、本実施形態では、ステップＳ１１０においてストロングデータガイド木からイベントシーケンスに変換し、ステップ１２０において生成したイベントシーケンスをＸＰａｔｈ処理して中間要約木を得る方法を利用しているが、ＸＰａｔｈ処理方法は、これに限定されない。代わりに既存の各種ＸＰａｔｈ処理方法を用いても構わない。例えば、問合せをボトムアップに処理することにより、多項式時間で処理可能なＸＰａｔｈ処理アルゴリズムなどの公知技術（Georg Gottlob, Christof Koch and Reinhard Pichler著、 "Efficient Algorithms for Processing XPathQueries" (米国) In Proc. VLDB (2002)参照）を用いて、ストロングデータガイド木をＸＭＬ木とみなして、ＸＰａｔｈ処理を行ってもよい。また、この処理の際には、イベントシーケンスを作成しなくてもよい。
【００５０】
そして、ここまでのＸＰａｔｈ処理では行っていない残りのＸＰａｔｈ処理を最適化するか否かを判断する（Ｓ１３０）。ＸＰａｔｈ処理を最適化しない場合には（Ｓ１３０のＮｏ）、二次記憶装置１３０のＸＭＬデータ１４０（図１参照）を用いて残りのＸＰａｔｈ処理を所定の順序で行う。すなわち、予め固定された処理手順でＸＭＬデータに対する検索を行い、処理を終了する。
【００５１】
残りのＸＰａｔｈ処理を最適化する場合には（Ｓ１３０のＹｅｓ）、残りのＸＰａｔｈ処理のコストを見積もり、処理順序を決定する（Ｓ１５０）。すなわち、最適な処理順序を決定する。そして、決定された順序で残りのＸＰａｔｈ処理を行い（Ｓ１６０）、処理を終了する。
【００５２】
図３は、ＸＭＬデータの例を説明する図である。図３に示すように、ＸＭＬデータはタグを用いて構造化されている。例えば、図３に含まれている以下の行は、１つのタグのまとまりに該当する。
<title>XML 1</title>
そして、このｔｉｔｌｅのタグも、Ｂｏｏｋｌｉｓｔのタグに含まれる形で構造化されている。ＸＭＬデータは、このようなタグによる構造化によってデータを記述している。
【００５３】
図４は、ＳＡＸ（Ｓｉｍｐｌｅ  ＡＰＩ  ｆｏｒ  ＸＭＬ）のイベントシーケンスの例を示す図である。なお、ＳＡＸは、リアルタイムに少ないメモリで、木を作らずに、ＸＭＬ文書を上から下へと走査して構文解析処理を行う技術である。図４のイベントシーケンスは、図３のＸＭＬデータの例に対してＳＡＸの技術を用いて、イベントを抽出することによって生成したものである。
【００５４】
図５は、図３のＸＭＬデータに対して構築したＸＭＬ木の例を示す図である。図５に示すようにＸＭＬ木は１つのタグに対応して１つのノードを定義している。ＸＭＬ木は、枠で囲まれて示しているタグや属性に対応する一番下のノードの下にテキストの値や属性値を示す葉ノードがつながった構造をしている。
【００５５】
図５のＸＭＬ木においては、Ｂｏｏｋｌｉｓｔをルートノードとして、その下にＢｏｏｋのノードが３つ出現している。そして、そのＢｏｏｋのノードの下には、それぞれｔｉｔｌｅのノードが出現している。このように、もとのＸＭＬデータを単純に変換したＸＭＬ木では、同様のノードのパターンが複数出現することがある。ストロングデータガイド木は、この繰り返しパターンを集約しているため、無駄なく検索を行うために用いることができる。
【００５６】
なお、ＸＭＬ木の中でノード名の記述が「＠」からはじまるものは、属性を表すノードであり、その下につながって記載されているのが属性値である。この例では、「＠ｉｓｂｎ」が属性のノードである。
【００５７】
図６は、ＸＰａｔｈによる問合せの例を示す図である。図６には、（１）から（４）まで４つの問い合わせの例を示しているが、問合せにおいては、親子関係だけでなく、先祖子孫関係も用いて検索対象を指定できる。「／」はノード間の親子関係を表し、「／／」はノード間の先祖子孫関係を表す。
【００５８】
図６の例のうち、（１）の例は、親子関係を用いた例であり、ルートノードの下にＢｏｏｋｌｉｓｔというノードが親子関係でつながっており、同様にそのＢｏｏｋｌｉｓｔのノードにＢｏｏｋのノードが連なり、さらにＢｏｏｋのノードからａｕｔｈｏｒｓのノード、さらにｐｅｒｓｏｎのノードがそれぞれ親子関係で連なっている構造のデータを検索する問い合わせである。
【００５９】
（２）から（４）の問合せでは、親子関係だけでなく、先祖子孫関係も用いている例である。例えば、（４）の例では、ルートノードとＢｏｏｋの間に先祖子孫関係があるという記述になっている。そして、（２）から（４）の例では、値や属性値を指定する問合せの例になっている。
【００６０】
図７は、図６の問合せ（１）から（４）に対応する問合せ木の例を示す図である。この例のようにＸＰａｔｈの問合せは、木で表現できる。
【００６１】
図８は、図５に示したＸＭＬ木に対応するストロングデータガイド木の例を示す図である。ストロングデータガイド木は、図５のＸＭＬ木に示された木構造の情報について要約した情報を表している。すなわち、ノード間の関係を抽出してまとめた情報になっている。ストロングデータガイド木を生成する方法は後記する。
【００６２】
図９は、範囲ラベル付ストロングデータガイド木の例を示す図である。図９に示すように、ストロングデータガイド木の各ノードは１つずつキューを持っていて、左右の２つの数字が並んでいるラベルがそのキューの中に収納される構成になっている。範囲ラベル付ストロングデータガイド木を構成する方法は後記する。
【００６３】
図１０は、問合せ木の構造部と値処理部を説明する図である。図１０に示す問合せ木は図７の問合せ木と同じものであるが、図１０に示すように、構造部３００と値処理部３１０に分けることができる。このとき、値および属性値を持たない問合せ木では、構造部３００のみで、値処理部３１０は存在しないことになる。この問合せ部３００と値処理部３１０を分ける処理は、後記する中間要約木を得る処理において用いられる。
【００６４】
図１１は、範囲ラベル無しのストロングデータガイド木を生成する処理を説明する図である。この処理では、ＳＡＸイベントを入力して、ラベル無しのストロングデータガイド木を出力する処理である。
【００６５】
まず、最初のあるいは次のＳＡＸイベントを入力して（Ｓ２００）、処理を開始する。そして、そのＳＡＸイベントが開始イベントか否かを調べる（Ｓ２１０）。開始イベントとは、図４に示した例における「ｓｔａｒｔ（Ｂｏｏｋｌｉｓｔ）」のような「ｓｔａｒｔ（）」という形をしたイベントのことである。
【００６６】
開始イベントでなかった場合は（Ｓ２１０のＮｏ）、入力されたＳＡＸイベントが終了イベントか否かを調べる（Ｓ２２０）。ここで、終了イベントとは、図４に示した例における「ｅｎｄ（Ｂｏｏｋｌｉｓｔ）」のような「ｅｎｄ（）」という形をしたイベントのことである。終了イベントであった場合は（Ｓ２２０のＹｅｓ）、ストロングデータガイド木における各時点において対象となっているノードである現在ノードをその現在ノードの親ノード（ルートノード側に１つ上がったノード）に移動し（Ｓ２３０）、後記するステップＳ２９０に進む。終了イベントでなかった場合は（Ｓ２２０のＮｏ）、そのままステップＳ２９０に進む。
【００６７】
ステップＳ２１０において、ＳＡＸイベントが開始イベントであった場合は（Ｓ２１０のＹｅｓ）、入力されたＳＡＸイベントのタグ名がストロングデータガイド木に存在するか否かを調べる（Ｓ２４０）。そのタグ名が存在しなかった場合（Ｓ２４０のＮｏ）、そのタグ名で子ノードをストロングデータガイド木に追加し（Ｓ２５０）、ステップＳ２６０に進む。そのタグ名が存在した場合（Ｓ２４０のＹｅｓ）、そのままステップＳ２５０を実行せずにステップＳ２６０に進む。
【００６８】
ステップＳ２６０では、そのノード、すなわち、前記の同じタグ名のノードまたは前記の新たに追加した子ノードに現在ノードを移動する。そして、その入力されたＳＡＸイベントが属性を持つか否かを調べる（Ｓ２７０）。属性を持たない場合は（Ｓ２７０のＮｏ）、そのままステップＳ２９０に進み、属性を持つ場合は（Ｓ２７０のＹｅｓ）、その属性に対応する子ノードの追加処理を行い（Ｓ２８０）、ステップＳ２９０へ進む。なお、その属性に対応する子ノードの追加処理については、詳細を後記する。
【００６９】
ステップＳ２９０では、その時点で全てのＳＡＸイベントを入力済みか否かについて調べる。その結果、未入力のＳＡＸイベントがある場合は（Ｓ２９０のＮｏ）、ステップＳ２００から処理を繰り返す。全てのＳＡＸイベントが入力済みである場合には（Ｓ２９０のＹｅｓ）、その時点までに作成したストロングデータガイド木を出力して（Ｓ３００）、処理を終了する。
【００７０】
図１２は、範囲ラベル無しのストロングデータガイド木に属性に対応する子ノードを追加する処理を説明する図である。なお、図１２は、図１１におけるステップＳ２８０の処理を詳細に示したものである。
【００７１】
まず、処理の対象となる属性名Ａを入力する（Ｓ４００）。そして、その属性名Ａに対応する「＠Ａ」を名前とする子ノードが現在ノードに存在するか否かを調べる（Ｓ４１０）。例えば、属性名Ａが「ｉｓｂｎ」であった場合は、「＠ｉｓｂｎ」という名前の子ノードが存在するか否かを調べる。存在しない場合は（Ｓ４１０のＮｏ）、属性名Ａに対応する「＠Ａ」を名前とする子ノードを現在ノードに追加して（Ｓ４２０）、ステップＳ４３０に進む。存在する場合は（Ｓ４１０のＹｅｓ）、そのままステップＳ４３０に進む。
【００７２】
ステップＳ４３０では、その時点で全ての属性を処理したか否かを調べる（Ｓ４３０）。全ての属性を処理し終わっている場合は（Ｓ４３０のＹｅｓ）、そのまま処理を終了し、未処理の属性が残っている場合は（Ｓ４３０のＮｏ）、ステップＳ４００に戻って処理を繰り返す。
【００７３】
図１３は、範囲ラベル付きのストロングデータガイド木を生成する処理を説明する図である。
範囲ラベルは、図９に示したように左右２つの値の組をラベルとして用いるが、まず、このラベルを管理するためのラベルの左の値ｌｅｆｔと右の値ｒｉｇｈｔを初期化する（Ｓ５００）。例えば、それぞれの値を１にしてもよい。そして、ルートノードを作成し、現在ノードをルートノードに設定する（Ｓ５１０）。これは、ストロングデータガイド木の初期化に該当するものである。
【００７４】
そして、最初の、または、次のＳＡＸイベントを入力する（Ｓ５２０）。そして、そのＳＡＸイベントに応じて範囲ラベルつきストロングデータガイド木を構築する処理を行う（Ｓ５３０）。このステップＳ５３０の処理についての詳細は後記する。
【００７５】
そして、その時点までに全てのＳＡＸイベントを入力済みか否かについて調べる（Ｓ５４０）。その結果、未入力のＳＡＸイベントがある場合には（Ｓ５４０のＮｏ）、ステップＳ５２０から処理を繰り返す。全てのＳＡＸイベントが入力済みの場合は（Ｓ５４０のＹｅｓ）、その時点までに作成した範囲ラベル付きストロングデータガイド木を出力して（Ｓ５５０）、処理を終了する。
【００７６】
図１４は、１つのＳＡＸイベントに応じて範囲ラベル付きストロングデータガイド木を構築する処理を説明する図である。図１４で説明する処理は、図１３のステップＳ５３０の処理に該当し、図１４における入力や変数を引き継いで処理するサブルーチンの役割を果たす。
【００７７】
まず、入力されたＳＡＸイベントが開始イベントか否かを調べる（Ｓ６００）。開始イベントだった場合（Ｓ６００のＹｅｓ）、図１３の処理で説明したｌｅｆｔの値を変数ｌに保存し、ｌｅｆｔの値を増やす（Ｓ６１０）。このとき、ｌｅｆｔの値を増やすときの増分は所定の値であればよい。例えば、その所定の増分を１や１０にしてもよい。
【００７８】
そして、そのＳＡＸイベントの開始タグ名ＴＡＧを名前とする子ノードが存在するか否かを調べる（Ｓ６２０）。例えば、ＳＡＸイベントの開始タグ名が「ｔｉｔｌｅ」だったとすると、それと同じ「ｔｉｔｌｅ」という名前の子ノードがあるか否かを調べる。ＳＡＸイベントの開始タグ名ＴＡＧと同じ名前の子ノードが存在しない場合（Ｓ６２０のＮｏ）、現在ノードにそのＴＡＧを名前とする子ノードを追加する（Ｓ６３０）。例えば、「ｔｉｔｌｅ」という開始タグ名の場合は、「ｔｉｔｌｅ」という名前の子ノードを追加する。そして、次のステップＳ６４０に進む。既に同じ名前の子ノードが存在する場合は（Ｓ６２０のＹｅｓ）、そのままステップＳ６４０に進む。
【００７９】
ステップＳ６４０では、現在ノードをその子ノードに移動する（Ｓ６４０）。すなわち、子ノードを追加した場合はその子ノードに、同じ名前の子ノードが存在した場合はその子ノードに、現在ノードを移動する。そして、ＳＡＸイベントが属性を持つか否かを調べる（Ｓ６５０）。属性を持つ場合は（Ｓ６５０のＹｅｓ）、属性子ノード追加および範囲ラベル付与処理を行い（Ｓ６６０）、ステップＳ６７０の処理に進む。なお、このステップＳ６６０の処理の詳細については、後記する。属性を持たない場合は（Ｓ６５０のＮｏ）、そのままステップＳ６７０に進む。
【００８０】
ステップＳ６７０では、現在ノードのキューの最後にステップＳ６１０で保存した変数ｌの値を用いて（ｌ，ＮＵＬＬ）のラベルを追加し、処理を終了する。なお、ＮＵＬＬは、有効なラベルの値が入っていないことを表す特別な値である。
【００８１】
ステップＳ６００においてＳＡＸイベントが開始イベントではなかった場合（Ｓ６００のＮｏ）、次に、そのＳＡＸイベントが終了イベントか否かを調べる（Ｓ６８０）。終了イベントではない場合は（Ｓ６８０のＮｏ）、ＳＡＸイベントがテキストノードイベントか否かを調べる（Ｓ６９０）。なお、テキストノードイベントとは、図４に示したイベントシーケンスに出現している「ｔｅｘｔ（“ＸＭＬ  １”）」と同じ「ｔｅｘｔ（）」という形をしたイベントを指す。調べた結果、テキストノードイベントではない場合は（Ｓ６９０のＮｏ）、そのまま処理を終了し、テキストノードイベントであった場合は（Ｓ６９０のＹｅｓ）、テキストノードのラベルの左側にｌｅｆｔ、右側にｒｉｇｈｔの値を入れて、そのラベルを現在ノードのキューに入れる（Ｓ７００）。そして、ｌｅｆｔとｒｉｇｈｔの値を増やして（Ｓ７１０）、処理を終了する。
【００８２】
ステップＳ６８０においてＳＡＸイベントが終了イベントだった場合（Ｓ６８０のＹｅｓ）、現在ノードのキューの中で、ラベルの右側の値がＮＵＬＬになっている最後のラベルの右にｒｉｇｈｔの値を入れて、このラベルをキューに入れる（Ｓ７２０）。そして、ｒｉｇｈｔの値を増やす（Ｓ７３０）。そして、現在ノードを現在ノードの親ノードに移動して（Ｓ７４０）、処理を終了する。
【００８３】
図１５は、属性子ノード追加および範囲ラベル付与処理を説明する図である。なお、この処理は、図１４のステップＳ６６０の処理に該当し、入力や変数を引き継いで処理するサブルーチンの役割を果たす。
【００８４】
まず、ｌｅｆｔとｒｉｇｈｔの値を引き継いで（Ｓ８００）、処理を開始する。そして、まず、属性名Ａを入力する（Ｓ８１０）。そして、現在ノードに属性名Ａに対応する「＠Ａ」を名前とする子ノードが存在するか否かを調べる（Ｓ８２０）。その結果、そのような子ノードが存在しない場合は（Ｓ８２０のＮｏ）、「＠Ａ」を名前とする子ノードを現在ノードに追加し（Ｓ８３０）、ステップＳ８４０に進む。同じ名前の子ノードが存在する場合は（Ｓ８２０のＮｏ）、そのままステップＳ８４０に進む。
【００８５】
ステップＳ８４０では、属性名Ａに対応する「＠Ａ」を名前とする子ノードに対して、（ｌｅｆｔ，ｒｉｇｈｔ）のラベルをキューに入れる（Ｓ８４０）。そして、ｌｅｆｔとｒｉｇｈｔの値をそれぞれ増加させる（Ｓ８５０）。そして、この時点で全ての属性を処理したか否かを調べる（Ｓ８６０）。既に全ての属性を処理している場合には（Ｓ８６０のＹｅｓ）、処理を終了する。まだ処理されていない属性がある場合には（Ｓ８６０のＮｏ）、ステップＳ８１０に戻って処理を繰り返す。
【００８６】
図１６は、ストロングデータガイド木からイベントシーケンスを構築する処理を説明する図である。図１７は、ストロングデータガイド木に対するイテレータの探索例を説明する図である。図１６に加えて、適宜、図１７も参照しつつ、イベントシーケンスを構築する処理について説明する。
【００８７】
この処理では、まず、ストロングデータガイド木を入力し、そのルートノードを現在ノードとする（Ｓ９００）。そして、現在ノードのイテレータが下降する方向に動くか否かを調べる（Ｓ９１０）。なお、下降するとは、ルートノードから遠ざかる動きをすることを指す。また、ここでのイテレータとは、ストロングデータガイド木のような木構造データなどを扱うための処理モジュールを指し、イテレータは、最初はルートノードに位置していて、図１７の例に示すように、木構造を下降したり、上昇したりしながら、木全体を探索する動きをするものである。
【００８８】
ステップＳ９１０で調べた結果、イテレータが下降する方向に動く場合は（Ｓ９１０のＹｅｓ）、現在ノードのノード名Ｎを用いて、「ｓｔａｒｔ（Ｎ）」を出力し（Ｓ９４０）、ステップＳ９７０に進む。このとき、例えば、ノード名Ｎが「ａｕｔｈｏｒｓ」だった場合には、「ｓｔａｒｔ（ａｕｔｈｏｒｓ）」が出力される。
【００８９】
ステップＳ９１０で調べた結果、イテレータが下降する方向に動かない場合は（Ｓ９１０のＮｏ）、次に、現在ノードのイテレータが上昇する方向に動くか否かを調べる（Ｓ９２０）。上昇する方向に動く場合は（Ｓ９２０のＹｅｓ）、現在ノードのノード名Ｎを用いて、「ｅｎｄ（Ｎ）」を出力し（Ｓ９５０）、ステップＳ９７０に進む。
【００９０】
ステップＳ９２０で調べた結果、イテレータが上昇する方向に動かない場合は（Ｓ９２０のＮｏ）、現在ノードのイテレータが属性を認識するか否かを調べる（Ｓ９３０）。属性を認識した場合は（Ｓ９３０のＹｅｓ）、現在ノードのノード名Ｎを用いて、「ａｔｔｒ＠（Ｎ）」を出力し（Ｓ９６０）、ステップＳ９７０へ進む。属性を認識しない場合は（Ｓ９３０のＮｏ）、そのままステップＳ９７０に進む。
【００９１】
ステップＳ９７０では、現在ノードのイテレータに次のイベントを設定し（Ｓ９７０）、この時点で全てのノードを処理してルートノードに戻ったか否かを調べる（Ｓ９８０）。なお、このとき、イテレータからＮＵＬＬの値が返ってくれば全てのノードを処理してルートノードに戻ったということを意味している。全ての処理が終わっていれば（Ｓ９８０のＹｅｓ）、処理を終了し、まだ処理が残っていれば（Ｓ９８０のＮｏ）、ステップＳ９１０に戻って、処理を繰り返す。
【００９２】
図１８は、ストロングデータガイド木により問合せて中間要約木を得る処理を説明する図である。
まず、ストロングデータガイド木とＸＰａｔｈによる問合せを入力する（Ｓ１０００）。そして、ＸＰａｔｈによる問合せの構造部を取り出す（Ｓ１０１０）。なお、この問合せの構造部とは、図１０において記載されている構造部３００と同様のものを指す。
【００９３】
そして、ストロングデータガイド木をＸＭＬデータとみなし、前記構造部のＸＰａｔｈ処理を実行し、内部マッチ木の列を得る（Ｓ１０２０）。それから、内部マッチ木から分岐ノードと枝ノードの組からなる中間要約木列を取り出して出力し（Ｓ１０３０）、処理を終了する。
【００９４】
図１９は、中間要約木から実態中間木を生成する処理を説明する図である。
まず、中間要約木を入力し（Ｓ１１００）、中間要約木の全てのノード間に対する構造ジョインを行い、実体中間木を生成する（Ｓ１１１０）。
【００９５】
その後、全ての中間要約木を処理したか否かを調べて（Ｓ１１２０）、処理が終わっていない場合は（Ｓ１１２０のＮｏ）、ステップＳ１１００に戻って処理を繰り返す。全ての中間要約木を処理し終わっている場合は（Ｓ１１２０のＹｅｓ）、それまでの処理で得られた実体中間木列を出力し（Ｓ１１３０）、処理を終了する。
【００９６】
図２０は実体中間木列にフィルタ条件を適用してＸＰａｔｈ問合せ結果を得る処理を説明する図である。
まず、実体中間木列を入力し、この処理の過程で生じるアウトプットノードを入れるキューＱＯを用意する（Ｓ１２００）。そして、実体中間木列に値処理部があるか否かを調べる（Ｓ１２１０）。このとき、実体中間木列の中の実体中間木の１つ以上に値処理部があれば、実体中間木列に値処理部があるとし、１つもなければ、値処理部がないとする。
【００９７】
この結果、値処理部がなければ（Ｓ１２１０のＮｏ）、そのままステップＳ１２５０に進む。値処理部があった場合は（Ｓ１２１０のＹｅｓ）、問合せ木の値処理部のフィルタ条件を二次記憶装置１３０から取り出して実体中間木の葉ノード（一番末端のノード）に適用する（Ｓ１２２０）。そして、出力されたノードをキューＱＯに追加する（Ｓ１２３０）。そして、この時点で全ての実体中間木を処理したか否かを調べて（Ｓ１２４０）、処理が終わっていない場合には（Ｓ１２４０のＮｏ）、ステップＳ１２２０から処理を繰り返し、処理が終わっている場合には、ステップＳ１２５０に進む。
【００９８】
ステップＳ１２５０では、ここまでの処理でノードを追加したキューＱＯの中で重複するラベルを除去する（Ｓ１２５０）。ここでは、この処理で得られたアウトプットノードの中に同じラベルがある可能性があるので、同一のラベルは１つだけ残すようにして、他の重複したラベルは全て削除する。そして、ＱＯのラベルを用いて二次記憶装置１３０から検索結果を取り出して出力し（Ｓ１２６０）、処理を終了する。
【００９９】
図２１は、実行プラン群を生成して最小コストを求める処理を説明する図である。この処理は、図１９（実体化プラン）および図２０（フィルタ条件適用）を用いて説明したような所定の実行プランに代替できる実行プランを決定する処理である。このとき、様々な実体化プランとフィルタ条件の組み合わせを調べてその最小コストのものを実行プランと決定する。
【０１００】
まず、実体化プランとフィルタ条件の組を出力する（Ｓ１３００）。そして、実体化プランとフィルタ条件の組を一つの実行プランとして、そのコストを求める（Ｓ１３１０）。このときのコストは、例えば、二次記憶装置１３０に対するアクセスの回数などをコストとしてもよいが、検索コストを反映する指標であればなんでもよい。
【０１０１】
そして、全ての実体化プランとフィルタ条件の組（実行プラン）を入力したか否かを調べる（Ｓ１３２０）。まだ、未入力のものがある場合は（Ｓ１３２０のＮｏ）、ステップＳ１３００に戻って処理を繰り返し、全ての組を入力し終わっている場合には（Ｓ１３２０のＹｅｓ）、求めたコストの中で最小となる実行プランを出力し（Ｓ１３３０）、処理を終了する。
【０１０２】
なお、実際の検索では、この処理の後に、この実行プランに基づいて、図１９および図２０において説明した処理に対応する処理（実際に検索結果を得る処理）を行うことになる。例えば、図１９および図２０で説明した処理も、最小コストであれば、その処理の例となり得る。最小コストの実行プランの具体的な処理については、説明を省略する。
【０１０３】
ここまで、第１の実施形態について説明してきたが、この実施形態によれば、ＸＭＬデータの構造を集約して予め要約情報（ストロングデータガイド木）として持っておくことにより、ＸＭＬデータの木構造の中から無駄なく効率的に問合せに対応する検索を行うことができる。しかも、ＸＭＬデータ処理装置１００の主記憶装置１１０の容量にあわせて、その構成に応じて最適なデータ配置をとることで、効率的な問合せ処理を行うことができる。
【０１０４】
<<第２の実施形態>>
図２２は、第２の実施形態におけるＸＭＬデータ処理装置の構成を説明する図である。
第１の実施形態では、ＸＭＬデータ１４０は、二次記憶装置１３０に記録してあって、ディスクマネージャ部１９０が管理していたが、この二次記憶装置１３０に記録してあるＸＭＬデータ１４０をより効率的に管理するために関係データベース管理システムを導入し、ＸＭＬデータ１４０を関係データベースとして記録、管理する実施形態をとることもできる。この第２の実施形態は、関係データベース管理システムに関する部分以外の構成は、第１の実施形態と同じであるので、説明を省略し、ここでは、第１の実施形態と異なる構成要素について説明する。
【０１０５】
第２の実施形態では、二次記憶装置１３０の中に記録されているＸＭＬデータ１４０Ａは関係データベース（ＲＤＢ）として記録されている。また、第２の実施形態では、ディスクマネージャ部１９０に替えて、関係データベース管理システムのプログラミングＡＰＩ２５０が導入され、関係データベースとして記録されているＸＭＬデータ１４０Ａに対するアクセスを管理している。
【０１０６】
第２の実施形態における問合せ処理は、第１の実施形態と同じなので説明を省略する。ただし、前記したように二次記憶装置１３０に記録されているＸＭＬデータ１４０Ａに対するアクセスの方式だけが異なっている。
【０１０７】
第２の実施形態によれば、第１の実施形態と同様に、ＸＭＬデータの構造を集約して予め要約情報（ストロングデータガイド木）として持っておくことにより、ＸＭＬデータの木構造の中から無駄なく効率的に問合せに対応する検索を行うことができる。さらに、第２の実施形態では、二次記憶装置に記録されているＸＭＬデータに対するアクセスが効率化されるので、さらに効率的な問合せ処理が可能になる。
【０１０８】
ここまで、本発明の実施形態について説明してきたが、本発明の趣旨から逸脱しない範囲内で実施形態の変更が可能である。例えば、ＸＭＬデータを二次記憶装置に記録するかわりに主記憶装置の容量を大きくして、全てのＸＭＬデータをそこに記録したり、二次記憶装置を半導体で構成されたディスク装置に変更したりしてもよい。なお、本実施形態におけるＸＭＬデータ処理装置は、演算手段を用いてプログラムで実現されており、所定の機能を備えた計算機に所定のプログラムを読み込む事で動作できる状態になる。そして、このプログラムを記憶媒体に記録しておいて、これを計算機に読み込ませることでＸＭＬデータ処理装置を実現してもよい。
【図面の簡単な説明】
【０１０９】
【図１】第１の実施形態におけるＸＭＬデータ処理装置の構成を説明する図である。
【図２】（ａ）は、ＸＰａｔｈ処理の前に行うＸＰａｔｈ事前処理の概要を説明する図であり、図２の（ｂ）は、ＸＰａｔｈ処理の概要を説明する図である。
【図３】ＸＭＬデータの例を説明する図である。
【図４】ＳＡＸのイベントシーケンスの例を示す図である。
【図５】図３のＸＭＬデータに対して構築したＸＭＬ木の例を示す図である。
【図６】ＸＰａｔｈによる問合せの例を示す図である。
【図７】図６の問合せの例に対応する問合せ木の例を示す図である。
【図８】図５に示したＸＭＬ木に対応するストロングデータガイド木の例を示す図である。
【図９】範囲ラベル付ストロングデータガイド木の例を示す図である。
【図１０】問合せ木の構造部と値処理部を説明する図である。
【図１１】範囲ラベル無しのストロングデータガイド木を生成する処理を説明する図である。
【図１２】範囲ラベル無しのストロングデータガイド木に属性に対応する子ノードを追加する処理を説明する図である。
【図１３】範囲ラベル付きのストロングデータガイド木を生成する処理を説明する図である。
【図１４】１つのＳＡＸイベントに応じて範囲ラベル付きストロングデータガイド木を構築する処理を説明する図である。
【図１５】属性子ノード追加および範囲ラベル付与処理を説明する図である。
【図１６】ストロングデータガイド木からイベントシーケンスを構築する処理を説明する図である。
【図１７】ストロングデータガイド木に対するイテレータの探索例を説明する図である。
【図１８】ストロングデータガイド木により問合せて中間要約木を得る処理を説明する図である。
【図１９】中間要約木から実態中間木を生成する処理を説明する図である。
【図２０】実体中間木列にフィルタ条件を適用してＸＰａｔｈ問合せ結果を得る処理を説明する図である。
【図２１】実行プラン群を生成して最小コストを求める処理を説明する図である。
【図２２】第２の実施形態におけるＸＭＬデータ処理装置の構成を説明する図である。
【符号の説明】
【０１１０】
１０    利用者
２０    ＸＭＬデータ（記録前）
１００  ＸＭＬデータ処理装置
１１０  主記憶装置
１２０  ＣＰＵ
１３０  二次記憶装置
１４０、１４０Ａ  ＸＭＬデータ（記録後）
１５０  問合せ解析部
１６０  問合せ最適化部
１７０  問合せ実行部
１８０  構造ジョイン演算部
１９０  ディスクマネージャ部
２００  結果生成部
２１０  イベントシーケンス生成部
２２０  データガイド木ローダ部
２３０  ＸＭＬデータローダ部
２４０  データガイド木（ストロングデータガイド木）
２５０  プログラミングＡＰＩ
【図１】
2010192001.tif 000003
【図２】
2010192001.tif 000004
【図３】
2010192001.tif 000005
【図４】
2010192001.tif 000006
【図５】
2010192001.tif 000007
【図６】
2010192001.tif 000008
【図７】
2010192001.tif 000009
【図８】
2010192001.tif 000010
【図９】
2010192001.tif 000011
【図１０】
2010192001.tif 000012
【図１１】
2010192001.tif 000013
【図１２】
2010192001.tif 000014
【図１３】
2010192001.tif 000015
【図１４】
2010192001.tif 000016
【図１５】
2010192001.tif 000017
【図１６】
2010192001.tif 000018
【図１７】
2010192001.tif 000019
【図１８】
2010192001.tif 000020
【図１９】
2010192001.tif 000021
【図２０】
2010192001.tif 000022
【図２１】
2010192001.tif 000023
【図２２】
2010192001.tif 000024