(57)【要約】【課題】ＸＭＬＤＢにおける検索の高速化が可能で、ＸＭＬデータに対して行われる特有の検索を可能にする。【解決手段】本発明は、入力されたＸＭＬデータをchild軸毎に構文解析して得られた全てのパスが格納されたデータガイド記憶手段のデータとノードインデックス記憶手段のデータから統計情報を計算し、データガイド記憶手段に登録し、検索式を分解することによりシングルパス群を生成し、各シングルパスに基づいて、データガイド記憶手段から取得した統計情報から、全てのＸＭＬデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする。【選択図】図１
2009244970.tif 000002
【特許請求の範囲】
【請求項１】
ＸＭＬ(Extensible Markup Language)データベースを検索する検索実行プランを最適化するための検索実行プラン最適化方法であって、
ＸＭＬの構造をパスＩＤ、パス、統計情報をデータガイド記憶手段に保持するものとし、入力されたＸＭＬデータの各ノードのタグと該データガイド記憶手段の該パスＩＤと関連付けられるパスＩＤ−Ｎと値をノードインデックス記憶手段に保持するものとし、
統計情報算出手段において、
ＸＭＬデータを取得すると、該ＸＭＬデータをchild軸毎に構文解析して得られた全てのパスに対し、パスＩＤを発行し、前記データガイド記憶手段に格納し、
前記データガイド記憶手段からパスＩＤを取り出し、前記ノードインデックス記憶手段から該パスＩＤに対応するパスＩＤ−Ｎの値を取得して、該パス毎に該ＸＭＬデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、前記データガイド記憶手段に登録する統計情報計算ステップと、
選択度計算手段において、
検索条件を取得して、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、前記データガイド記憶手段を参照し、前記統計情報を取得する統計情報取得ステップと、
取得した前記統計情報から、全ての前記ＸＭＬデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算ステップと、
を行うことを特徴とする検索実行プラン最適化方法。
【請求項２】
前記統計情報計算ステップにおいて、
前記データガイド記憶手段のパスＩＤに基づいて、前記ノードインデックス記憶手段から対応するパスＩＤ−Ｎの値を取得し、
統計情報を計算する際に、
前記ＸＭＬデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、
ＸＭＬデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出処理と、
ＸＭＬデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出処理と、
ＸＭＬデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出処理と、を行う
請求項１記載の検索実行プラン最適化方法。
【請求項３】
前記統計情報取得ステップにおいて、
前記ＸＭＬデータに対して行われる特有の検索のために、child軸（//）、descendant軸（//）、ワイルドカード（*）、末端にのみ述語が記述されているＸPath式のいずれかを含む前記シングルパスを抽出する
請求項１記載の検索実行プラン最適化方法。
【請求項４】
前記選択度計算ステップにおいて、
前記データガイド記憶手段から取り出した前記統計情報について、
前記検索条件のテキストが前記統計情報のコモン値のテキストと一致するか否かに基づいて前記選択度を求める一致検索処理、
または、
前記統計情報のヒストグラムから前記選択度を求める範囲検索処理、
のいずれかを行う請求項１乃至３記載の検索実行プラン最適化方法。
【請求項５】
ＸＭＬデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化装置であって、
ＸＭＬの構造をパスＩＤ、パス、統計情報を保持するデータガイド記憶手段と、
入力されたＸＭＬデータの各ノードのタグと該データガイド記憶手段の該パスＩＤと関連付けられるパスＩＤ−Ｎと値を保持するノードインデックス記憶手段と、
前記ＸＭＬデータが入力されると、該ＸＭＬデータをchild軸毎に構文解析して得られた全てのパスに対し、パスＩＤを発行し、前記データガイド記憶手段に格納するパステーブル生成手段と、
前記データガイド記憶手段からパスＩＤを取り出し、前記ノードインデックス記憶手段から該パスＩＤに対応するパスＩＤ−Ｎの値を取得して、該パス毎に該ＸＭＬデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、前記データガイド記憶手段に登録する統計情報計算手段と、
検索条件が入力されると、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、前記データガイド記憶手段を参照し、前記統計情報を取得し、前記統計情報から、全ての前記ＸＭＬデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算手段と、
を有することを特徴とする検索実行プラン最適化装置。
【請求項６】
前記統計情報計算手段は、
前記データガイド記憶手段のパスＩＤに基づいて、前記ノードインデックス記憶手段から対応するパスＩＤ−Ｎの値を取得する手段と、
前記ＸＭＬデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、
ＸＭＬデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出手段と、
ＸＭＬデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出手段と、
ＸＭＬデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出手段と、
を含む請求項５記載の検索実行プラン最適化装置。
【請求項７】
前記選択度計算手段は、
前記ＸＭＬデータに対して行われる特有の検索のために、child軸（//）、descendant軸（//）、ワイルドカード（*）、末端にのみ述語が記述されているＸPath式のいずれかを含む前記シングルパスを抽出する
請求項１記載の検索実行プラン最適化方法。
【請求項８】
前記選択度計算手段は、
前記データガイド記憶手段から取り出した前記統計情報について、
前記検索条件のテキストが前記統計情報のコモン値のテキストと一致するか否かに基づいて前記選択度を求める一致検索手段、
または、
前記統計情報のヒストグラムから前記選択度を求める範囲検索手段、
のいずれかを含む請求項５乃至７記載の検索実行プラン最適化装置。
【請求項９】
請求項５乃至８のいずれか１項に記載の検索実行プラン最適化装置を構成する各手段としてコンピュータを機能させるための検索実行プラン最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索実行プラン最適化方法及び装置及びプログラムに係り、特に、構造化データである多数のＸＭＬ文書を蓄積・検索するデータベースの分野で、蓄積したＸＭＬデータを要約した構造情報と統計情報を用いることで、ＸＭＬデータベースにおける検索実行時の処理実行プランを最適化するための検索実行プラン最適化方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
一般的なリレーショナルデータベース（ＲＤＢ）では、検索実行時に、検索処理実行プランを最適に構築することで、検索処理を高速化している（例えば、非特許文献１参照）。
【０００３】
また、検索処理実行プランを最適に構築する手法として、ルールベース手法コストベース手法が存在する。ルールベース手法は、予め決められたルールで、検索処理実行プランを構築する方法で、コストベース手法は、予め取得した蓄積データの統計情報を用いることで、選択度（各検索処理過程の処理コスト）を計算し、検索処理実行プランを構築する手段である。一般に、ルールベース手法は、コストベース手法に比べ、平均して検索処理速度が遅くなることが知られている（例えば、非特許文献２参照）。
【０００４】
一方、ＸＭＬＤＢとは、構造化データであるＸＭＬデータを蓄積・検索することができる情報処理システムである（例えば、非特許文献３参照）。ＸＭＬデータの検索処理には木構造データに対する特有な検索が用いられる（例えば、非特許文献４参照）。ＸＭＬデータに対して検索を行うとき、ＲＤＢに検索をかける場合と違い、descendantやワイルドカード（*）といったＸＭＬデータに対する検索特有の文法が存在する。ＸＭＬＤＢでは、これらを用いた検索に対応しなくてはならない。
【特許文献１】特開２００７−１９３６４２号公報
【非特許文献１】「RDBMS解剖学」、pp. 82-84, JSBN4-7981-0864-2
【非特許文献２】「最新データベース技術マスタリングハンドブック」 pp.355-356, ISBN4-7980-0422-7
【非特許文献３】「ＸＭＬデータベース入門」pp.231-236 ISBN4-320-12162-7.
【非特許文献４】「標準ＸＭＬ完全解説下」pp.68-69,  ISBN4-7741-1302-6江田毅晴、鬼塚真、山室雅司、「ＸＭＬデータの要約情報を用いた高速なＸPath処理方式」電子情報通信学会論文誌, Vol. J89-D No.2, pp.139-150, 2006
【発明の開示】
【発明が解決しようとする課題】
【０００５】
近年、様々なデータがＸＭＬによって記述されるようになり、蓄積されたＸＭＬデータを高速に検索する技術が求められるようになってきた。
【０００６】
一般的なＲＤＢと同様、ＸＭＬＤＢにおける検索実行時にも検索処理実行プランを構築し、プランに従って検索処理を実行する。このとき、検索処理実行プランを最適に構築することにより、検索の高速化が実現できる。
【０００７】
検索処理実行プランを最適に構築する手法として、ルールベース手法とコストベース手法が存在する。一般に、ルールベース手法は、コストベース手法に比べ、平均して検索処理速度が遅くなることが知られている。
【０００８】
しかし、コストベース手法を用いた検索処理実行プランを用いてＸＭＬＤＢ検索を実現するために、ＸＭＬデータに対して行われる特有の検索（ワイルドカードやdescendant軸）に関して、予め統計情報を取得しておくことができない、という問題がある。なぜなら、ワイルドカードやdescendant軸を用いた全てのパス組み合わせは膨大であり、その全ての統計情報を予め集計しておくことは現実的に不可能だからである。
【０００９】
従って、単純にコストベース手法をＸＭＬＤＢの検索実行時のプラン構築に用いることができない。しかし、ルールベース手法を用いた検索処理実行プランを用いて、ＸＭＬＤＢ検索を実現するためには、「ＸＭＬデータに対して行われる特有の検索（ワイルドカードやdescendant軸）に関して、最適な検索処理実行プランを構築できるルールが作成できないという問題がある。なぜなら、ワイルドカードやdescendant軸を用いた検索はルールで選択度を算出するには複雑すぎる処理である。
【００１０】
従って、ＸＭＬデータに対して行われる特有の検索（ワイルドカードやdescendant軸を用いた検索）に関して、最適な検索処理実行プランを構築できる技術が必要であるといえる。
【００１１】
本発明は、上記の点に鑑みなされたもので、ＸＭＬＤＢにおける検索の高速化が可能で、木構造データに対して行われる特有の検索（ワイルドカードやdescendant軸）の選択度が高い精度で予測でき、現実的な時間で必要な統計情報の取得が可能なＸＭＬデータベースにおける検索実行プラン最適化方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
図１は、本発明の原理を説明するための図である。
【００１３】
本発明（請求項１）は、ＸＭＬデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化方法であって、
ＸＭＬの構造をパスＩＤ、パス、統計情報をデータガイド記憶手段に保持するものとし、入力されたＸＭＬデータの各ノードのタグと該データガイド記憶手段の該パスＩＤと関連付けられるパスＩＤ−Ｎと値をノードインデックス記憶手段に保持するものとし（ステップ１，２）、
統計情報算出手段が、入力された該ＸＭＬデータをchild軸毎に構文解析して得られた全てのパスに対し、パスＩＤを発行し、データガイド記憶手段に格納し（ステップ３）、
データガイド記憶手段からパスＩＤを取り出し、ノードインデックス記憶手段から該パスＩＤに対応するパスＩＤ−Ｎの値を取得して、該パス毎に該ＸＭＬデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、データガイド記憶手段に登録する統計情報計算ステップ（ステップ４）と、
検索手段が、入力された（ステップ５）検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、データガイド記憶手段を参照し、統計情報を取得する統計情報取得ステップ（ステップ６）と、
取得した統計情報から、全てのＸＭＬデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算ステップ（ステップ７）と、を行う。
【００１４】
また、本発明（請求項２）は、統計情報計算ステップ（ステップ６）において、
データガイド記憶手段のパスＩＤに基づいて、ノードインデックス記憶手段から対応するパスＩＤ−Ｎの値を取得し、
統計情報を計算する際に、
ＸＭＬデータの各パスに対して存在する全てのノード数を求めるノード数算出処理と、
ＸＭＬデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出処理と、
ＸＭＬデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出処理と、
ＸＭＬデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出処理と、を行う。
【００１５】
また、本発明（請求項３）は、統計情報計算ステップ（ステップ４）において、
ＸＭＬデータに対して行われる特有の検索のために、child軸（//）、descendant軸（//）、ワイルドカード（*）、末端にのみ述語が記述されているＸPath式のいずれかを含むシングルパスを抽出する。
【００１６】
また、本発明（請求項４）は、選択度計算ステップ（ステップ７）において、
データガイド記憶手段から取り出した統計情報について、
検索条件のテキストが統計情報のコモン値のテキストと一致するか否かに基づいて選択度を求める一致検索処理、
または、
統計情報のヒストグラムから選択度を求める範囲検索処理、のいずれかを行う。
【００１７】
図２は、本発明の原理構成図である。
【００１８】
本発明（請求項５）は、ＸＭＬデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化装置であって、
ＸＭＬの構造をパスＩＤ、パス、統計情報を保持するデータガイド記憶手段１１０と、
入力されたＸＭＬデータの各ノードのタグと該データガイド記憶手段の該パスＩＤと関連付けられるパスＩＤ−Ｎと値を保持するノードインデックス記憶手段１２０と、
ＸＭＬデータが入力されると、該ＸＭＬデータをchild軸毎にchild軸毎に構文解析して得られた全てのパスに対し、パスＩＤを発行し、データガイド記憶手段に格納するパステーブル生成手段１５０と、
データガイド記憶手段１１０からパスＩＤを取り出し、ノードインデックス記憶手段１２０から該パスＩＤに対応するパスＩＤ−Ｎの値を取得して、該パス毎に該ＸＭＬデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、データガイド記憶手段に登録する統計情報計算手段１３０と、
検索条件が入力されると、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、データガイド記憶手段１１０を参照し、統計情報を取得し、統計情報から、全てのＸＭＬデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算手段１４０と、を有する。
【００１９】
また、本発明（請求項６）は、統計情報計算手段１３０において、
データガイド記憶手段のパスＩＤに基づいて、ノードインデックス記憶手段から対応するパスＩＤ−Ｎの値を取得する手段と、
ＸＭＬデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、
ＸＭＬデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出手段と、
ＸＭＬデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出手段と、
ＸＭＬデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出手段と、を含む。
【００２０】
また、本発明（請求項７）は、選択度計算手段において、
ＸＭＬデータに対して行われる特有の検索のために、child軸（//）、descendant軸（//）、ワイルドカード（*）、末端にのみ述語が記述されているＸPath式のいずれかを含むシングルパスを抽出する。
【００２１】
また、本発明（請求項８）は、選択度計算手段において、
データガイド記憶手段から取り出した統計情報について、
検索条件のテキストが統計情報のコモン値のテキストと一致するか否かに基づいて選択度を求める一致検索手段、
または、
統計情報のヒストグラムから選択度を求める範囲検索手段、
のいずれかを含む。
【００２２】
本発明（請求項９）は、請求項５乃至８のいずれか１項に記載の検索実行プラン最適化装置を構成する各手段としてコンピュータを機能させるための検索実行プラン最適化プログラムである。
【発明の効果】
【００２３】
上記のように本発明によれば、ＸＭＬデータはデータガイド(DATAGUIDE)記憶手段に、ノード情報はノードインデックス記憶手段に格納し、ＸＭＬデータが持つchild軸（/）のパス毎に統計情報を収集することで、ワイルドカードやdescendant軸が含まれた検索の選択度を算出可能とし、現実的な時間で統計情報の集計・格納を可能とする。
【００２４】
また、本発明は、入力された検索式で指定されているパスにワイルドカードやdescendant軸が含まれている場合に、指定されたパスにマッチし、データガイド記憶手段に格納されているデータに存在するパスの検索式に分解し、分解された検索式に対して統計情報を用いて選択度（ヒット件数）を計算し、当該選択度を比較することにより小さい検索式から検索を実行するように検索順序を決定することができる。
【発明を実施するための最良の形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
まず、以下に用いられる用語について説明する。
【００２７】
「クエリプランの最適化」とは、検索条件が複数存在する場合、より検索演算に係る計算コストを小さくするために、どの検索条件から検索演算を行うかを決定することである。本実施の形態では、「統計情報」を用いて「選択度計算」を行うことで検索演算の計画を立てる。図３にそのイメージを示す。例えば、『２００６年に発行され、タイトルが"ＸＭＬ" 』である本データを検索するものとする。蓄積データの中に２００６年に発行された本データが１００万件、タイトルが"ＸＭＬ"である本が２０件である場合、２００６年に発行された本を最初に検索し、その結果の中からタイトルが"ＸＭＬ"である本を探索することにより、タイトルが"ＸＭＬ"である本を最初に検索し、その結果の中から２００６年に発行された本を探索する方が演算コストが小さいことがわかる。
【００２８】
「統計情報」とは、蓄積されたＸＭＬデータの性質や傾向を数量的に示した情報である。本実施の形態では、ＸＭＬデータの各パスに対して計測できる統計情報を記録し、選択度を計算する。代表的な統計情報に、カーディナリティやヒストグラム等が挙げられる。
【００２９】
「選択度」とは、対象の検索式が、全ＸＭＬデータから何件マッチするか予測される数のことである。複数の検索式を実行する場合、より選択度の小さい検索式を先に処理することで検索処理の総コストを小さくできる。
【００３０】
「シングルパス」とは、Child軸（／），descendant軸（／／），ワイルドカード（*）と末端にのみ述語が記述されているＸPath式を指す。
【００３１】
「ＸＭＬデータ特有の問い合わせ」とは、ＸＭＬデータに対して検索を行うとき、ＲＤＢに検索をかける場合と違い、図４に示すように、descendant（例１）ワイルドカード（例２）といったＸＭＬに対する検索特有の文法が存在する。ＸＭＬＤＢでは、これらを用いた検索に対応しなくてはならず、同様に選択度計算も可能としなくてはならない。
【００３２】
最初に最適化装置の構成について説明する。
【００３３】
図５は、本発明の一実施の形態におけるＸＭＬデータベースにおける最適化装置の構成を示す。
【００３４】
同図に示す最適化装置１００は、ＸＭＬの構造をパス単位で管理するDATAGUIDE（データガイド）部１１０、各ノードのタグとデータを管理するノードインデックス部１２０、各パスの統計情報を計算する統計情報算出部１３０、検索処理を行う検索処理部１４０から構成され、ＸＭＬデータ入力部１０がデータガイド部１１０、ノードインデックス部１２０、統計情報算出部１３０に接続され、クエリ入力部２０と出力部３０が検索処理部１４０に接続されている。
【００３５】
データガイド部１１０は、メモリやディスク等の媒体上に構築され、図６（ａ）、図７（ａ）に示すように、パスＩＤ、パス、統計情報のカラムからなるテーブルから構成される。
【００３６】
ノードテーブルインデックス部１２０は、メモリやディスク等の媒体上に構築され、図６（ｂ），図７（ｂ）に示すように、タグ、パスＩＤ、値からなるテーブルで構成される。ノードインデックスに格納される全ノードはパスＩＤによって、データガイド部１１０の情報と関連付けられている。
【００３７】
データガイド部１１０は、蓄積されたＸＭＬデータの全てとパスと、統計情報算出部１３０で求められた各パスの統計情報を格納する（図８（ａ））。ノードインデックス部１２０は、蓄積されたＸＭＬデータの全てのノードのタグとデータを格納する（図８（ｂ））。統計情報算出部１３０は、ノードインデックス部１２０に格納されたデータからＸＭＬデータの全パス毎の統計情報（ノード数、カーディナリティ、コモン値、ヒストグラム）を算出し、データガイド部１１０のパステーブルに格納する。
【００３８】
ここで、「統計情報」について説明する。
【００３９】
統計情報としては、ノード数、カーディナリティ、コモン値がある。
【００４０】
「ノード数」とは、本実施の形態では、ＸＭＬデータの各パスに対して、存在する全てのノード数を統計情報のノード数として算出し、データガイド部１１０のパステーブルに格納する。
【００４１】
「カーディナリティ」とは、ユニークな値の種類数であり、本実施の形態では、リーフノードに格納されている値やテキストを比較し、ユニークである値・テキストの種類を統計情報のカーディナリティとして、データガイド部１１０のパステーブルに格納する。
【００４２】
「コモン値」とは、本実施の形態では、リーフノードに格納されている値や、図９に示すように、テキストが重複しているノード数をカウントし、重複の多い値・テキストとノード値をペア値とし、統計情報のコモン値として、データガイド部１１０のパステーブルに格納する。
【００４３】
「ヒストグラム」とは、値の大まかな分布情報であり、本実施の形態では、図１０に示すように、各パスのリーフノードの値・テキストをソートし、一定間隔で値を抜き出してリストにすることで統計情報のヒストグラムとして、データガイド部１１０のパステーブルに格納する。
【００４４】
検索処理部１４０は、クエリ入力部２０から入力された検索クエリを個別の単一条件の式に分解する（これを、シングルパスという）。検索クエリにワイルドカードやdescendant軸などのＸＭＬデータ特有の検索が含まれている場合、マッチする全てのパスをデータガイド部１１０から探しだし、シングルパスに分解する。次に、検索処理部１４０は、各シングルパスの選択度を算出する。算出された選択度を比較し、値の小さい選択度を最適な検索処理プランとして出力部３０に出力する。検索処理部１４０の詳細な処理については後述する。
【００４５】
次に、上記の構成における動作を説明する。
【００４６】
図１１、１２は、本発明の一実施の形態における最適化装置における動作概要のフローチャートである。
【００４７】
ステップ１１０）  ＸＭＬデータ入力部１０からＸＭＬデータが入力される。
【００４８】
ステップ１２０）  統計情報算出部１３０は、入力されたＸＭＬデータを受け取ったデータ及び統計情報をデータガイド部１１０、ノードインデックス部１２０に格納する。
【００４９】
ステップ１３０）  クエリ入力部２０からクエリが入力される。
【００５０】
ステップ１４０）  検索処理部１４０は、入力されたクエリに基づいて、検索実行処理プランを構築する。
【００５１】
ステップ１５０）  検索処理部１４０は、検索実行処理プランに沿って検索処理を実行し、検索結果を出力部３０に出力する。具体的な処理としては、例えば、「江田毅晴、鬼塚真、山室雅司、「ＸＭＬデータの要約情報を用いた高速なＸPath処理方式」電子情報通信学会論文誌, Vol. J89-D No.2, pp.139-150, 2006」等の技術を用いることが可能である。
【００５２】
次に、上記のステップ１２０の処理について説明する。
【００５３】
図１３は、本発明の一実施の形態におけるデータ及び統計情報格納処理のフローチャートである。
【００５４】
ステップ１２１）  統計情報算出部１３０は、入力されたＸＭＬデータからパスを取り出す。
【００５５】
ステップ１２２）  データガイド部１１０のパスカラムをチェックし、入力値と同じパスが既に格納されているかを判定し、格納されている場合にはステップ１２４に移行し、含まれていない場合は、ステップ１２３に移行する。
【００５６】
ステップ１２３）  新たなパスＩＤを発行し、入力値と共に、データガイド部１１０の同じレコードのパスＩＤカラム、パスカラムにそれぞれ格納する。
【００５７】
ステップ１２４）  入力されたＸＭＬデータの最後までchild軸毎に構文解析しているか否かを確認して、終了している場合には、ステップ１２５に移行し、未処理のパスがある場合にはステップ１２１に移行する。
【００５８】
ステップ１２５）  データガイド部１１０のパステーブルに格納されたパス毎に統計情報を計算し、データガイド部１１０のパステーブルに格納する。
【００５９】
次に、上記のステップ１２５の処理について説明する。
【００６０】
図１４は、本発明の一実施の形態における統計情報の研鑽及び格納のフローチャートである。
【００６１】
ステップ１２５１）  データガイド部１１０のパステーブルからパスＩＤを一つ取り出す。
【００６２】
ステップ１２５２）  パスＩＤを用いて、マッチするレコードをノードインデックス部１２０のノードテーブルから探し出し、統計情報（例えば、ノード数など）を算出し、データガイド部１１０に出力する。
【００６３】
ステップ１２５３）  算出した統計情報をパスＩＤがマッチするデータガイド部１１０のレコードに格納する。
【００６４】
ステップ１２５４）  上記のステップ１２５１〜１２５３の処理を、データガイド部１１０に格納されている全てのパスについて行った場合には当該処理を終了し、未処理のものがある場合にはステップ１２５１に戻る。
【００６５】
次に、図１１のステップ１４０における検索実行処理プランを構築する処理について説明する。
【００６６】
図１５は、本発明の一実施の形態におけるクエリプラン最適化のフローチャートである。
【００６７】
ステップ１４１）  クエリ入力部２０からクエリが入力されると、検索処理部１４０は、検索条件に沿って検索式を分解する。シングルパス（child軸（／）、descendant軸（／／）、ワイルドカード（*）と末端にのみ述語が記述されているＸPath式）に分解し、シングルパス群を再構成する。シングルパスの分解処理については、例えば、http://www.w3.org/を参照されたい。
【００６８】
例えば、『章番号２０未満且つ章タイトルが"惑星"である章を含む本データを検索』というクエリが入力された場合は、
１）章番号２０未満である章を含む本データの検索；
２）章タイトルが"惑星"である章を含む本データの検索；
という二つの検索の積から求められる。検索式で表すと図１６のようになる。
【００６９】
ステップ１４２）  シングルパス群からシングルパスを順番に１つ抽出する。
【００７０】
ステップ１４３）  シングルパスからデータガイド部１１０を参照し、統計情報を取り出す。統計情報の取り出し方は、図１７に示すように、データガイド部１１０からシングルパスとマッチするパスを探し（ステップ１４３１）、マッチするパスと関連付けられた統計情報（例えば、カーディナリティやヒストグラム）を取り出す（ステップ１４３２）。
【００７１】
ステップ１４４）  統計情報からシングルパスの選択度を計算する。選択度の計算については、例えば、文献「最新データベース技術マスタリングハンドブック p355-356 ISBN4-7980-0422-７」に記載されている方法を用いるものとする。
【００７２】
選択度の計算には、一致検索と範囲検索がある。
【００７３】
一致検索は、検索条件のテキストがコモン値のテキストと一致する場合は、選択度はその値の重複数とし、検索条件のテキストがコモン値とテキストと不一致である場合は、選択度は、
（ノード数ａ−コモン値の重複数の合計）÷（コモン値ではないユニークな値）
により求める。以下に一致検索の例を図９の統計情報の例を用いて説明する。
【００７４】
例１）あるノードtext()の値が"2006.12.29"と一致する検索式の選択度は、コモン値の配列から"2006.12.29"がヒットし、選択度はペア値である「４８０」となる。
【００７５】
例２）あるノードtextの値が"2006.06.22"と一致する検索式の選択度は、コモン値の配列には"2006.06.22"がヒットしない。選択度は、
（ノード数ａ−コモン値の合計９４０）
÷（コモン値ではない値の数（２５０−３））＝７７．２
となる。
【００７６】
また、範囲検索は、ヒストグラムから選択度を計算する。これは、条件テキストｘ以上、条件テキストｙ以下を指定した場合、ヒストグラムの配列からｘ以上ｙ未満の要素をカウントする。範囲検索の例を以下に示す。
【００７７】
例１）あるノードtext（）の値が"2006.01.20"以上"2007.06.15"以下の値を含む検索式の選択度を、ヒストグラムから算出する。図１８から、
要素数ｐ＝４８
ヒストグラム帯幅数ｃ＝２００
選択度＝ｐ×ｃ＝９６００
ステップ１４５）  全てのシングルパスについて上記の処理を行ったかを判定し、行った場合はステップ１４６に移行し、そうでない場合はステップ１４２に移行する。
【００７８】
ステップ１４６）  算出された選択度から検索実行処理プランを生成する。検索実行処理プラン生成の例として、例えば、「RDBMS解剖学」p.82-84 ISBN4-7981-084-2を参照されたい。
【００７９】
以下に、図１５のクエリプランの最適化の処理を具体的に示す。
【００８０】
まず、図１６に示すように、「章番号２０未満且つ章タイトルが"惑星"である章を含む本データの検索」というクエリに対し、
【００８１】
【数１】
2009244970.tif 000003
と検索式が分解される。
【００８２】
図８に示すようなデータガイド部１１０を参照し、選択度を計算すると、
【００８３】
【数２】
2009244970.tif 000004
となり、検索式(/book/chapter/text/text()="惑星")の方が選択度が小さく、絞り込みの度合いが強い。従って、「/book/chapter/text/text()="惑星"」の検索式から検索処理を行うことで、検索にかかる総コストを小さくすることができる。
【００８４】
次に、ＸＭＬ特有の検索に対する選択度の計算方法を説明する。
【００８５】
まず、descendantを用いた検索の場合の選択度計算を説明する。
【００８６】
クエリ入力部２０から入力された検索式は、「/book/title[.text()="惑星の秘密"」であるとし、データガイド部１１０のパステーブルは、図１９であるとする。
【００８７】
検索式「/book/title/text()」を満たすパスを図１９のパステーブルから探し出す。その結果、以下の２つのパスを取り出すことができる。
【００８８】
１）/book/title/text()
２）/book/chapter/title/text()
従って、検索式「/book/title[.text()="惑星の秘密"」の選択度は、
１）/book/title[.text()="惑星の秘密"
２）/book/chapter/title[.text()="惑星の秘密"]
の２つの式の選択度和で求められる。
【００８９】
次に、ワイルドカード（*）を用いた場合の選択度計算を説明する。
【００９０】
クエリ入力部２０から入力された検索式は、/book/chapter/*[.text()="地球"]であるとし、データガイド部１１０のパステーブルは、図１９であるとする。
【００９１】
検索式「/book/chapter/*/text()」を満たすパスを図１９のパステーブルから探し出す。その結果、以下の２つのパスを取り出すことができる。
【００９２】
１）/book/chapter/title/text()
２）/book/chapter/text/text()
従って、検索式「/book/title[.text()="惑星の秘密"」の選択度は、
１）/book/chapter/title[.text()="地球"]
２）/book/chapter/text[.text()="地球"]
の２つの式の選択度の和で求められる。
【００９３】
なお、上記の図３に示す最適化装置の構成要素の動作をプログラムとして構築し、最適化装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９４】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００９５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９６】
本発明は、ＸＭＬデータ（ＸＭＬＤＢ）の蓄積や検索に適用可能である。
【図面の簡単な説明】
【００９７】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の処理イメージを説明するための図である。
【図４】本発明の「ＸＭＬに対する検索特有の文法」を説明するための図である。
【図５】本発明の一実施の形態におけるＸＭＬデータベースにおける最適化装置の構成図である。
【図６】本発明の一実施の形態におけるデータガイド（DATAGUDE）部とノードインデックス部のデータ構造である。
【図７】本発明の一実施の形態におけるパステーブルとノードテーブルの例である。
【図８】本発明の一実施の形態における統計情報が格納された例である。
【図９】本発明の一実施の形態における統計情報（コモン値）を説明するための図である。
【図１０】本発明の一実施の形態における統計情報（ヒストグラム）を説明するための図である。
【図１１】本発明の一実施の形態における最適化装置における動作の概要のフローチャート（その１）である。
【図１２】本発明の一実施の形態における最適化装置における動作の概要のフローチャート（その２）である。
【図１３】本発明の一実施の形態におけるデータ及び統計情報格納のフローチャートである。
【図１４】本発明の一実施の形態における統計情報の研鑽及び格納のフローチャートである。
【図１５】本発明の一実施の形態におけるクエリプラン最適化のフローチャートである。
【図１６】本発明の一実施の形態における検索式の分解の例である。
【図１７】本発明の一実施の形態における統計情報取り出しのフローチャートである。
【図１８】本発明の一実施の形態における選択度計算（範囲検索）に用いる要素数である。
【図１９】本発明の一実施の形態におけるDATAGUIDE部のパステーブルの例である。
【符号の説明】
【００９８】
１０  ＸＭＬデータ入力部
２０  クエリ入力部
３０  出力部
１１０  データガイド記憶手段、DATAGUIDE（データガイド）部
１２０  ノードインデックス記憶手段、ノードインデックス部
１３０  統計情報算出手段、統計情報算出部
１４０  選択度計算手段、検索処理部
１５０  パステーブル生成手段
【図１】
2009244970.tif 000005
【図２】
2009244970.tif 000006
【図３】
2009244970.tif 000007
【図４】
2009244970.tif 000008
【図５】
2009244970.tif 000009
【図６】
2009244970.tif 000010
【図７】
2009244970.tif 000011
【図８】
2009244970.tif 000012
【図９】
2009244970.tif 000013
【図１０】
2009244970.tif 000014
【図１１】
2009244970.tif 000015
【図１２】
2009244970.tif 000016
【図１３】
2009244970.tif 000017
【図１４】
2009244970.tif 000018
【図１５】
2009244970.tif 000019
【図１６】
2009244970.tif 000020
【図１７】
2009244970.tif 000021
【図１８】
2009244970.tif 000022
【図１９】
2009244970.tif 000023