図面 (/)

技術 検索実行プラン最適化方法及び装置及びプログラム

出願人 日本電信電話株式会社
発明者 兵藤正樹榎本俊文山室雅司
出願日 2008年3月28日 (12年0ヶ月経過) 出願番号 2008-087887
公開日 2009年10月22日 (10年5ヶ月経過) 公開番号 2009-244970
状態 拒絶査定
技術分野 検索装置
主要キーワード 処理プラン コストベース ノードインデックス 検索演算 最適化プログラム カーディナリティ ノード値 RDBMS
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2009年10月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

MLDBにおける検索高速化が可能で、XMLデータに対して行われる特有の検索を可能にする。

解決手段

本発明は、入力されたXMLデータをchild軸毎構文解析して得られた全てのパスが格納されたデータガイド記憶手段のデータとノードインデックス記憶手段のデータから統計情報を計算し、データガイド記憶手段に登録し、検索式を分解することによりシングルパス群を生成し、各シングルパスに基づいて、データガイド記憶手段から取得した統計情報から、全てのXMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする。

概要

背景

一般的なリレーショナルデータベース(RDB)では、検索実行時に、検索処理実行プランを最適に構築することで、検索処理を高速化している(例えば、非特許文献1参照)。

また、検索処理実行プランを最適に構築する手法として、ルールベース手法コストベース手法が存在する。ルールベース手法は、予め決められたルールで、検索処理実行プランを構築する方法で、コストベース手法は、予め取得した蓄積データの統計情報を用いることで、選択度(各検索処理過程処理コスト)を計算し、検索処理実行プランを構築する手段である。一般に、ルールベース手法は、コストベース手法に比べ、平均して検索処理速度が遅くなることが知られている(例えば、非特許文献2参照)。

一方、XMLDBとは、構造化データであるXMLデータを蓄積・検索することができる情報処理システムである(例えば、非特許文献3参照)。XMLデータの検索処理には木構造データに対する特有な検索が用いられる(例えば、非特許文献4参照)。XMLデータに対して検索を行うとき、RDBに検索をかける場合と違い、descendantやワイルドカード(*)といったXMLデータに対する検索特有の文法が存在する。XMLDBでは、これらを用いた検索に対応しなくてはならない。
特開2007−193642号公報
RDBMS解剖学」、pp. 82-84, JSBN4-7981-0864-2
最新データベース技術マスタリングハンドブック」 pp.355-356, ISBN4-7980-0422-7
XMLデータベース入門」pp.231-236 ISBN4-320-12162-7.
標準XML完全解説下」pp.68-69, ISBN4-7741-1302-6江田毅晴、鬼塚真、山室雅司、「XMLデータの要約情報を用いた高速なXPath処理方式電子情報通信学会論文誌, Vol. J89-D No.2, pp.139-150, 2006

概要

XMLDBにおける検索の高速化が可能で、XMLデータに対して行われる特有の検索を可能にする。本発明は、入力されたXMLデータをchild軸毎構文解析して得られた全てのパスが格納されたデータガイド記憶手段のデータとノードインデックス記憶手段のデータから統計情報を計算し、データガイド記憶手段に登録し、検索式を分解することによりシングルパス群を生成し、各シングルパスに基づいて、データガイド記憶手段から取得した統計情報から、全てのXMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする。

目的

本発明は、上記の点に鑑みなされたもので、XMLDBにおける検索の高速化が可能で、木構造データに対して行われる特有の検索(ワイルドカードやdescendant軸)の選択度が高い精度で予測でき、現実的な時間で必要な統計情報の取得が可能なXMLデータベースにおける検索実行プラン最適化方法及び装置及びプログラムを提供することを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

XML(Extensible Markup Language)データベース検索する検索実行プランを最適化するための検索実行プラン最適化方法であって、XMLの構造をパスID、パス、統計情報をデータガイド記憶手段に保持するものとし、入力されたXMLデータの各ノードのタグと該データガイド記憶手段の該パスIDと関連付けられるパスID−Nと値をノードインデックス記憶手段に保持するものとし、統計情報算出手段において、XMLデータを取得すると、該XMLデータをchild軸毎構文解析して得られた全てのパスに対し、パスIDを発行し、前記データガイド記憶手段に格納し、前記データガイド記憶手段からパスIDを取り出し、前記ノードインデックス記憶手段から該パスIDに対応するパスID−Nの値を取得して、該パス毎に該XMLデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、前記データガイド記憶手段に登録する統計情報計算ステップと、選択度計算手段において、検索条件を取得して、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、前記データガイド記憶手段を参照し、前記統計情報を取得する統計情報取得ステップと、取得した前記統計情報から、全ての前記XMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算ステップと、を行うことを特徴とする検索実行プラン最適化方法。

請求項2

前記統計情報計算ステップにおいて、前記データガイド記憶手段のパスIDに基づいて、前記ノードインデックス記憶手段から対応するパスID−Nの値を取得し、統計情報を計算する際に、前記XMLデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、XMLデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出処理と、XMLデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出処理と、XMLデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化ヒストグラムとするヒストグラム算出処理と、を行う請求項1記載の検索実行プラン最適化方法。

請求項3

前記統計情報取得ステップにおいて、前記XMLデータに対して行われる特有の検索のために、child軸(//)、descendant軸(//)、ワイルドカード(*)、末端にのみ述語記述されているXPath式のいずれかを含む前記シングルパスを抽出する請求項1記載の検索実行プラン最適化方法。

請求項4

前記選択度計算ステップにおいて、前記データガイド記憶手段から取り出した前記統計情報について、前記検索条件のテキストが前記統計情報のコモン値のテキストと一致するか否かに基づいて前記選択度を求める一致検索処理、または、前記統計情報のヒストグラムから前記選択度を求める範囲検索処理、のいずれかを行う請求項1乃至3記載の検索実行プラン最適化方法。

請求項5

XMLデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化装置であって、XMLの構造をパスID、パス、統計情報を保持するデータガイド記憶手段と、入力されたXMLデータの各ノードのタグと該データガイド記憶手段の該パスIDと関連付けられるパスID−Nと値を保持するノードインデックス記憶手段と、前記XMLデータが入力されると、該XMLデータをchild軸毎に構文解析して得られた全てのパスに対し、パスIDを発行し、前記データガイド記憶手段に格納するパステーブル生成手段と、前記データガイド記憶手段からパスIDを取り出し、前記ノードインデックス記憶手段から該パスIDに対応するパスID−Nの値を取得して、該パス毎に該XMLデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、前記データガイド記憶手段に登録する統計情報計算手段と、検索条件が入力されると、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、前記データガイド記憶手段を参照し、前記統計情報を取得し、前記統計情報から、全ての前記XMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算手段と、を有することを特徴とする検索実行プラン最適化装置。

請求項6

前記統計情報計算手段は、前記データガイド記憶手段のパスIDに基づいて、前記ノードインデックス記憶手段から対応するパスID−Nの値を取得する手段と、前記XMLデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、XMLデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出手段と、XMLデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出手段と、XMLデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出手段と、を含む請求項5記載の検索実行プラン最適化装置。

請求項7

前記選択度計算手段は、前記XMLデータに対して行われる特有の検索のために、child軸(//)、descendant軸(//)、ワイルドカード(*)、末端にのみ述語が記述されているXPath式のいずれかを含む前記シングルパスを抽出する請求項1記載の検索実行プラン最適化方法。

請求項8

前記選択度計算手段は、前記データガイド記憶手段から取り出した前記統計情報について、前記検索条件のテキストが前記統計情報のコモン値のテキストと一致するか否かに基づいて前記選択度を求める一致検索手段、または、前記統計情報のヒストグラムから前記選択度を求める範囲検索手段、のいずれかを含む請求項5乃至7記載の検索実行プラン最適化装置。

請求項9

請求項5乃至8のいずれか1項に記載の検索実行プラン最適化装置を構成する各手段としてコンピュータを機能させるための検索実行プラン最適化プログラム

技術分野

0001

本発明は、検索実行プラン最適化方法及び装置及びプログラム係り、特に、構造化データである多数のXML文書蓄積検索するデータベースの分野で、蓄積したXMLデータを要約した構造情報統計情報を用いることで、XMLデータベースにおける検索実行時処理実行プランを最適化するための検索実行プラン最適化方法及び装置及びプログラムに関する。

背景技術

0002

一般的なリレーショナルデータベース(RDB)では、検索実行時に、検索処理実行プランを最適に構築することで、検索処理を高速化している(例えば、非特許文献1参照)。

0003

また、検索処理実行プランを最適に構築する手法として、ルールベース手法コストベース手法が存在する。ルールベース手法は、予め決められたルールで、検索処理実行プランを構築する方法で、コストベース手法は、予め取得した蓄積データの統計情報を用いることで、選択度(各検索処理過程処理コスト)を計算し、検索処理実行プランを構築する手段である。一般に、ルールベース手法は、コストベース手法に比べ、平均して検索処理速度が遅くなることが知られている(例えば、非特許文献2参照)。

0004

一方、XMLDBとは、構造化データであるXMLデータを蓄積・検索することができる情報処理システムである(例えば、非特許文献3参照)。XMLデータの検索処理には木構造データに対する特有な検索が用いられる(例えば、非特許文献4参照)。XMLデータに対して検索を行うとき、RDBに検索をかける場合と違い、descendantやワイルドカード(*)といったXMLデータに対する検索特有の文法が存在する。XMLDBでは、これらを用いた検索に対応しなくてはならない。
特開2007−193642号公報
RDBMS解剖学」、pp. 82-84, JSBN4-7981-0864-2
最新データベース技術マスタリングハンドブック」 pp.355-356, ISBN4-7980-0422-7
「XMLデータベース入門」pp.231-236 ISBN4-320-12162-7.
標準XML完全解説下」pp.68-69, ISBN4-7741-1302-6江田毅晴、鬼塚真、山室雅司、「XMLデータの要約情報を用いた高速なXPath処理方式電子情報通信学会論文誌, Vol. J89-D No.2, pp.139-150, 2006

発明が解決しようとする課題

0005

近年、様々なデータがXMLによって記述されるようになり、蓄積されたXMLデータを高速に検索する技術が求められるようになってきた。

0006

一般的なRDBと同様、XMLDBにおける検索実行時にも検索処理実行プランを構築し、プランに従って検索処理を実行する。このとき、検索処理実行プランを最適に構築することにより、検索の高速化が実現できる。

0007

検索処理実行プランを最適に構築する手法として、ルールベース手法とコストベース手法が存在する。一般に、ルールベース手法は、コストベース手法に比べ、平均して検索処理速度が遅くなることが知られている。

0008

しかし、コストベース手法を用いた検索処理実行プランを用いてXMLDB検索を実現するために、XMLデータに対して行われる特有の検索(ワイルドカードやdescendant軸)に関して、予め統計情報を取得しておくことができない、という問題がある。なぜなら、ワイルドカードやdescendant軸を用いた全てのパス組み合わせは膨大であり、その全ての統計情報を予め集計しておくことは現実的に不可能だからである。

0009

従って、単純にコストベース手法をXMLDBの検索実行時のプラン構築に用いることができない。しかし、ルールベース手法を用いた検索処理実行プランを用いて、XMLDB検索を実現するためには、「XMLデータに対して行われる特有の検索(ワイルドカードやdescendant軸)に関して、最適な検索処理実行プランを構築できるルールが作成できないという問題がある。なぜなら、ワイルドカードやdescendant軸を用いた検索はルールで選択度を算出するには複雑すぎる処理である。

0010

従って、XMLデータに対して行われる特有の検索(ワイルドカードやdescendant軸を用いた検索)に関して、最適な検索処理実行プランを構築できる技術が必要であるといえる。

0011

本発明は、上記の点に鑑みなされたもので、XMLDBにおける検索の高速化が可能で、木構造データに対して行われる特有の検索(ワイルドカードやdescendant軸)の選択度が高い精度で予測でき、現実的な時間で必要な統計情報の取得が可能なXMLデータベースにおける検索実行プラン最適化方法及び装置及びプログラムを提供することを目的とする。

課題を解決するための手段

0012

図1は、本発明の原理を説明するための図である。

0013

本発明(請求項1)は、XMLデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化方法であって、
XMLの構造をパスID、パス、統計情報をデータガイド記憶手段に保持するものとし、入力されたXMLデータの各ノードのタグと該データガイド記憶手段の該パスIDと関連付けられるパスID−Nと値をノードインデックス記憶手段に保持するものとし(ステップ1,2)、
統計情報算出手段が、入力された該XMLデータをchild軸毎構文解析して得られた全てのパスに対し、パスIDを発行し、データガイド記憶手段に格納し(ステップ3)、
データガイド記憶手段からパスIDを取り出し、ノードインデックス記憶手段から該パスIDに対応するパスID−Nの値を取得して、該パス毎に該XMLデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、データガイド記憶手段に登録する統計情報計算ステップ(ステップ4)と、
検索手段が、入力された(ステップ5)検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、データガイド記憶手段を参照し、統計情報を取得する統計情報取得ステップ(ステップ6)と、
取得した統計情報から、全てのXMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算ステップ(ステップ7)と、を行う。

0014

また、本発明(請求項2)は、統計情報計算ステップ(ステップ6)において、
データガイド記憶手段のパスIDに基づいて、ノードインデックス記憶手段から対応するパスID−Nの値を取得し、
統計情報を計算する際に、
XMLデータの各パスに対して存在する全てのノード数を求めるノード数算出処理と、
XMLデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出処理と、
XMLデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出処理と、
XMLデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化ヒストグラムとするヒストグラム算出処理と、を行う。

0015

また、本発明(請求項3)は、統計情報計算ステップ(ステップ4)において、
XMLデータに対して行われる特有の検索のために、child軸(//)、descendant軸(//)、ワイルドカード(*)、末端にのみ述語が記述されているXPath式のいずれかを含むシングルパスを抽出する。

0016

また、本発明(請求項4)は、選択度計算ステップ(ステップ7)において、
データガイド記憶手段から取り出した統計情報について、
検索条件のテキストが統計情報のコモン値のテキストと一致するか否かに基づいて選択度を求める一致検索処理、
または、
統計情報のヒストグラムから選択度を求める範囲検索処理、のいずれかを行う。

0017

図2は、本発明の原理構成図である。

0018

本発明(請求項5)は、XMLデータベースを検索する検索実行プランを最適化するための検索実行プラン最適化装置であって、
XMLの構造をパスID、パス、統計情報を保持するデータガイド記憶手段110と、
入力されたXMLデータの各ノードのタグと該データガイド記憶手段の該パスIDと関連付けられるパスID−Nと値を保持するノードインデックス記憶手段120と、
XMLデータが入力されると、該XMLデータをchild軸毎にchild軸毎に構文解析して得られた全てのパスに対し、パスIDを発行し、データガイド記憶手段に格納するパステーブル生成手段150と、
データガイド記憶手段110からパスIDを取り出し、ノードインデックス記憶手段120から該パスIDに対応するパスID−Nの値を取得して、該パス毎に該XMLデータの性質や傾向を数量的に表した統計情報を計算し、入力値と共に、データガイド記憶手段に登録する統計情報計算手段130と、
検索条件が入力されると、検索式を分解し、複数のシングルパスからなるシングルパス群を生成し、該シングルパスに基づいて、データガイド記憶手段110を参照し、統計情報を取得し、統計情報から、全てのXMLデータから何件マッチするか予測される数である選択度を計算し、該選択度の小さい方を検索実行処理プランとする選択度計算手段140と、を有する。

0019

また、本発明(請求項6)は、統計情報計算手段130において、
データガイド記憶手段のパスIDに基づいて、ノードインデックス記憶手段から対応するパスID−Nの値を取得する手段と、
XMLデータの各パスに対して存在する全てのノード数を求めるノード数算出処理、
XMLデータのリーフノードに格納されている値やテキストを比較し、ユニークである値またはテキストの種類を求めるカーディナリティとして求めるカーディナリティ算出手段と、
XMLデータのリーフノードに格納されている値やテキストが重複しているノード数をカウントし、重複数の多い値・テキストとノード数をペア値とし、コモン値を求めるコモン値算出手段と、
XMLデータの各パスのリーフノードの値、テキストをソートし、一定間隔で値を抜き出してリスト化しヒストグラムとするヒストグラム算出手段と、を含む。

0020

また、本発明(請求項7)は、選択度計算手段において、
XMLデータに対して行われる特有の検索のために、child軸(//)、descendant軸(//)、ワイルドカード(*)、末端にのみ述語が記述されているXPath式のいずれかを含むシングルパスを抽出する。

0021

また、本発明(請求項8)は、選択度計算手段において、
データガイド記憶手段から取り出した統計情報について、
検索条件のテキストが統計情報のコモン値のテキストと一致するか否かに基づいて選択度を求める一致検索手段、
または、
統計情報のヒストグラムから選択度を求める範囲検索手段、
のいずれかを含む。

0022

本発明(請求項9)は、請求項5乃至8のいずれか1項に記載の検索実行プラン最適化装置を構成する各手段としてコンピュータを機能させるための検索実行プラン最適化プログラムである。

発明の効果

0023

上記のように本発明によれば、XMLデータはデータガイド(DATAGUIDE)記憶手段に、ノード情報はノードインデックス記憶手段に格納し、XMLデータが持つchild軸(/)のパス毎に統計情報を収集することで、ワイルドカードやdescendant軸が含まれた検索の選択度を算出可能とし、現実的な時間で統計情報の集計・格納を可能とする。

0024

また、本発明は、入力された検索式で指定されているパスにワイルドカードやdescendant軸が含まれている場合に、指定されたパスにマッチし、データガイド記憶手段に格納されているデータに存在するパスの検索式に分解し、分解された検索式に対して統計情報を用いて選択度(ヒット件数)を計算し、当該選択度を比較することにより小さい検索式から検索を実行するように検索順序を決定することができる。

発明を実施するための最良の形態

0025

以下、図面と共に本発明の実施の形態を説明する。

0026

まず、以下に用いられる用語について説明する。

0027

クエリプランの最適化」とは、検索条件が複数存在する場合、より検索演算に係る計算コストを小さくするために、どの検索条件から検索演算を行うかを決定することである。本実施の形態では、「統計情報」を用いて「選択度計算」を行うことで検索演算の計画を立てる。図3にそのイメージを示す。例えば、『2006年に発行され、タイトルが"XML" 』である本データを検索するものとする。蓄積データの中に2006年に発行された本データが100万件、タイトルが"XML"である本が20件である場合、2006年に発行された本を最初に検索し、その結果の中からタイトルが"XML"である本を探索することにより、タイトルが"XML"である本を最初に検索し、その結果の中から2006年に発行された本を探索する方が演算コストが小さいことがわかる。

0028

「統計情報」とは、蓄積されたXMLデータの性質や傾向を数量的に示した情報である。本実施の形態では、XMLデータの各パスに対して計測できる統計情報を記録し、選択度を計算する。代表的な統計情報に、カーディナリティやヒストグラム等が挙げられる。

0029

「選択度」とは、対象の検索式が、全XMLデータから何件マッチするか予測される数のことである。複数の検索式を実行する場合、より選択度の小さい検索式を先に処理することで検索処理の総コストを小さくできる。

0030

「シングルパス」とは、Child軸(/),descendant軸(//),ワイルドカード(*)と末端にのみ述語が記述されているXPath式を指す。

0031

「XMLデータ特有の問い合わせ」とは、XMLデータに対して検索を行うとき、RDBに検索をかける場合と違い、図4に示すように、descendant(例1)ワイルドカード(例2)といったXMLに対する検索特有の文法が存在する。XMLDBでは、これらを用いた検索に対応しなくてはならず、同様に選択度計算も可能としなくてはならない。

0032

最初に最適化装置の構成について説明する。

0033

図5は、本発明の一実施の形態におけるXMLデータベースにおける最適化装置の構成を示す。

0034

同図に示す最適化装置100は、XMLの構造をパス単位で管理するDATAGUIDE(データガイド)部110、各ノードのタグとデータを管理するノードインデックス部120、各パスの統計情報を計算する統計情報算出部130、検索処理を行う検索処理部140から構成され、XMLデータ入力部10がデータガイド部110、ノードインデックス部120、統計情報算出部130に接続され、クエリ入力部20と出力部30が検索処理部140に接続されている。

0035

データガイド部110は、メモリディスク等の媒体上に構築され、図6(a)、図7(a)に示すように、パスID、パス、統計情報のカラムからなるテーブルから構成される。

0036

ノードテーブルインデックス部120は、メモリやディスク等の媒体上に構築され、図6(b),図7(b)に示すように、タグ、パスID、値からなるテーブルで構成される。ノードインデックスに格納される全ノードはパスIDによって、データガイド部110の情報と関連付けられている。

0037

データガイド部110は、蓄積されたXMLデータの全てとパスと、統計情報算出部130で求められた各パスの統計情報を格納する(図8(a))。ノードインデックス部120は、蓄積されたXMLデータの全てのノードのタグとデータを格納する(図8(b))。統計情報算出部130は、ノードインデックス部120に格納されたデータからXMLデータの全パス毎の統計情報(ノード数、カーディナリティ、コモン値、ヒストグラム)を算出し、データガイド部110のパステーブルに格納する。

0038

ここで、「統計情報」について説明する。

0039

統計情報としては、ノード数、カーディナリティ、コモン値がある。

0040

「ノード数」とは、本実施の形態では、XMLデータの各パスに対して、存在する全てのノード数を統計情報のノード数として算出し、データガイド部110のパステーブルに格納する。

0041

「カーディナリティ」とは、ユニークな値の種類数であり、本実施の形態では、リーフノードに格納されている値やテキストを比較し、ユニークである値・テキストの種類を統計情報のカーディナリティとして、データガイド部110のパステーブルに格納する。

0042

「コモン値」とは、本実施の形態では、リーフノードに格納されている値や、図9に示すように、テキストが重複しているノード数をカウントし、重複の多い値・テキストとノード値をペア値とし、統計情報のコモン値として、データガイド部110のパステーブルに格納する。

0043

「ヒストグラム」とは、値の大まかな分布情報であり、本実施の形態では、図10に示すように、各パスのリーフノードの値・テキストをソートし、一定間隔で値を抜き出してリストにすることで統計情報のヒストグラムとして、データガイド部110のパステーブルに格納する。

0044

検索処理部140は、クエリ入力部20から入力された検索クエリを個別の単一条件の式に分解する(これを、シングルパスという)。検索クエリにワイルドカードやdescendant軸などのXMLデータ特有の検索が含まれている場合、マッチする全てのパスをデータガイド部110から探しだし、シングルパスに分解する。次に、検索処理部140は、各シングルパスの選択度を算出する。算出された選択度を比較し、値の小さい選択度を最適な検索処理プランとして出力部30に出力する。検索処理部140の詳細な処理については後述する。

0045

次に、上記の構成における動作を説明する。

0046

図11、12は、本発明の一実施の形態における最適化装置における動作概要フローチャートである。

0047

ステップ110)XMLデータ入力部10からXMLデータが入力される。

0048

ステップ120)統計情報算出部130は、入力されたXMLデータを受け取ったデータ及び統計情報をデータガイド部110、ノードインデックス部120に格納する。

0049

ステップ130)クエリ入力部20からクエリが入力される。

0050

ステップ140)検索処理部140は、入力されたクエリに基づいて、検索実行処理プランを構築する。

0051

ステップ150)検索処理部140は、検索実行処理プランに沿って検索処理を実行し、検索結果を出力部30に出力する。具体的な処理としては、例えば、「江田毅晴、鬼塚真、山室雅司、「XMLデータの要約情報を用いた高速なXPath処理方式」電子情報通信学会論文誌, Vol. J89-D No.2, pp.139-150, 2006」等の技術を用いることが可能である。

0052

次に、上記のステップ120の処理について説明する。

0053

図13は、本発明の一実施の形態におけるデータ及び統計情報格納処理のフローチャートである。

0054

ステップ121)統計情報算出部130は、入力されたXMLデータからパスを取り出す。

0055

ステップ122) データガイド部110のパスカラムをチェックし、入力値と同じパスが既に格納されているかを判定し、格納されている場合にはステップ124に移行し、含まれていない場合は、ステップ123に移行する。

0056

ステップ123) 新たなパスIDを発行し、入力値と共に、データガイド部110の同じレコードのパスIDカラム、パスカラムにそれぞれ格納する。

0057

ステップ124) 入力されたXMLデータの最後までchild軸毎に構文解析しているか否かを確認して、終了している場合には、ステップ125に移行し、未処理のパスがある場合にはステップ121に移行する。

0058

ステップ125) データガイド部110のパステーブルに格納されたパス毎に統計情報を計算し、データガイド部110のパステーブルに格納する。

0059

次に、上記のステップ125の処理について説明する。

0060

図14は、本発明の一実施の形態における統計情報の研鑽及び格納のフローチャートである。

0061

ステップ1251) データガイド部110のパステーブルからパスIDを一つ取り出す。

0062

ステップ1252)パスIDを用いて、マッチするレコードをノードインデックス部120のノードテーブルから探し出し、統計情報(例えば、ノード数など)を算出し、データガイド部110に出力する。

0063

ステップ1253) 算出した統計情報をパスIDがマッチするデータガイド部110のレコードに格納する。

0064

ステップ1254) 上記のステップ1251〜1253の処理を、データガイド部110に格納されている全てのパスについて行った場合には当該処理を終了し、未処理のものがある場合にはステップ1251に戻る。

0065

次に、図11のステップ140における検索実行処理プランを構築する処理について説明する。

0066

図15は、本発明の一実施の形態におけるクエリプラン最適化のフローチャートである。

0067

ステップ141)クエリ入力部20からクエリが入力されると、検索処理部140は、検索条件に沿って検索式を分解する。シングルパス(child軸(/)、descendant軸(//)、ワイルドカード(*)と末端にのみ述語が記述されているXPath式)に分解し、シングルパス群を再構成する。シングルパスの分解処理については、例えば、http://www.w3.org/を参照されたい。

0068

例えば、『章番号20未満且つ章タイトルが"惑星"である章を含む本データを検索』というクエリが入力された場合は、
1)章番号20未満である章を含む本データの検索;
2)章タイトルが"惑星"である章を含む本データの検索;
という二つの検索の積から求められる。検索式で表すと図16のようになる。

0069

ステップ142)シングルパス群からシングルパスを順番に1つ抽出する。

0070

ステップ143)シングルパスからデータガイド部110を参照し、統計情報を取り出す。統計情報の取り出し方は、図17に示すように、データガイド部110からシングルパスとマッチするパスを探し(ステップ1431)、マッチするパスと関連付けられた統計情報(例えば、カーディナリティやヒストグラム)を取り出す(ステップ1432)。

0071

ステップ144)統計情報からシングルパスの選択度を計算する。選択度の計算については、例えば、文献「最新データベース技術マスタリングハンドブックp355-356 ISBN4-7980-0422-7」に記載されている方法を用いるものとする。

0072

選択度の計算には、一致検索と範囲検索がある。

0073

一致検索は、検索条件のテキストがコモン値のテキストと一致する場合は、選択度はその値の重複数とし、検索条件のテキストがコモン値とテキストと不一致である場合は、選択度は、
(ノード数a−コモン値の重複数の合計)÷(コモン値ではないユニークな値)
により求める。以下に一致検索の例を図9の統計情報の例を用いて説明する。

0074

例1)あるノードtext()の値が"2006.12.29"と一致する検索式の選択度は、コモン値の配列から"2006.12.29"がヒットし、選択度はペア値である「480」となる。

0075

例2)あるノードtextの値が"2006.06.22"と一致する検索式の選択度は、コモン値の配列には"2006.06.22"がヒットしない。選択度は、
(ノード数a−コモン値の合計940)
÷(コモン値ではない値の数(250−3))=77.2
となる。

0076

また、範囲検索は、ヒストグラムから選択度を計算する。これは、条件テキストx以上、条件テキストy以下を指定した場合、ヒストグラムの配列からx以上y未満の要素をカウントする。範囲検索の例を以下に示す。

0077

例1)あるノードtext()の値が"2006.01.20"以上"2007.06.15"以下の値を含む検索式の選択度を、ヒストグラムから算出する。図18から、
要素数p=48
ヒストグラム帯幅数c=200
選択度=p×c=9600
ステップ145) 全てのシングルパスについて上記の処理を行ったかを判定し、行った場合はステップ146に移行し、そうでない場合はステップ142に移行する。

0078

ステップ146) 算出された選択度から検索実行処理プランを生成する。検索実行処理プラン生成の例として、例えば、「RDBMS解剖学」p.82-84 ISBN4-7981-084-2を参照されたい。

0079

以下に、図15のクエリプランの最適化の処理を具体的に示す。

0080

まず、図16に示すように、「章番号20未満且つ章タイトルが"惑星"である章を含む本データの検索」というクエリに対し、

0081

と検索式が分解される。

0082

図8に示すようなデータガイド部110を参照し、選択度を計算すると、

0083

となり、検索式(/book/chapter/text/text()="惑星")の方が選択度が小さく、絞り込みの度合いが強い。従って、「/book/chapter/text/text()="惑星"」の検索式から検索処理を行うことで、検索にかかる総コストを小さくすることができる。

0084

次に、XML特有の検索に対する選択度の計算方法を説明する。

0085

まず、descendantを用いた検索の場合の選択度計算を説明する。

0086

クエリ入力部20から入力された検索式は、「/book/title[.text()="惑星の秘密"」であるとし、データガイド部110のパステーブルは、図19であるとする。

0087

検索式「/book/title/text()」を満たすパスを図19のパステーブルから探し出す。その結果、以下の2つのパスを取り出すことができる。

0088

1)/book/title/text()
2)/book/chapter/title/text()
従って、検索式「/book/title[.text()="惑星の秘密"」の選択度は、
1)/book/title[.text()="惑星の秘密"
2)/book/chapter/title[.text()="惑星の秘密"]
の2つの式の選択度和で求められる。

0089

次に、ワイルドカード(*)を用いた場合の選択度計算を説明する。

0090

クエリ入力部20から入力された検索式は、/book/chapter/*[.text()="地球"]であるとし、データガイド部110のパステーブルは、図19であるとする。

0091

検索式「/book/chapter/*/text()」を満たすパスを図19のパステーブルから探し出す。その結果、以下の2つのパスを取り出すことができる。

0092

1)/book/chapter/title/text()
2)/book/chapter/text/text()
従って、検索式「/book/title[.text()="惑星の秘密"」の選択度は、
1)/book/chapter/title[.text()="地球"]
2)/book/chapter/text[.text()="地球"]
の2つの式の選択度の和で求められる。

0093

なお、上記の図3に示す最適化装置の構成要素の動作をプログラムとして構築し、最適化装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

0094

また、構築されたプログラムをハードディスクや、フレキシブルディスクCD−ROM等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

0095

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。

0096

本発明は、XMLデータ(XMLDB)の蓄積や検索に適用可能である。

図面の簡単な説明

0097

本発明の原理を説明するための図である。
本発明の原理構成図である。
本発明の処理イメージを説明するための図である。
本発明の「XMLに対する検索特有の文法」を説明するための図である。
本発明の一実施の形態におけるXMLデータベースにおける最適化装置の構成図である。
本発明の一実施の形態におけるデータガイド(DATAGUDE)部とノードインデックス部のデータ構造である。
本発明の一実施の形態におけるパステーブルとノードテーブルの例である。
本発明の一実施の形態における統計情報が格納された例である。
本発明の一実施の形態における統計情報(コモン値)を説明するための図である。
本発明の一実施の形態における統計情報(ヒストグラム)を説明するための図である。
本発明の一実施の形態における最適化装置における動作の概要のフローチャート(その1)である。
本発明の一実施の形態における最適化装置における動作の概要のフローチャート(その2)である。
本発明の一実施の形態におけるデータ及び統計情報格納のフローチャートである。
本発明の一実施の形態における統計情報の研鑽及び格納のフローチャートである。
本発明の一実施の形態におけるクエリプラン最適化のフローチャートである。
本発明の一実施の形態における検索式の分解の例である。
本発明の一実施の形態における統計情報取り出しのフローチャートである。
本発明の一実施の形態における選択度計算(範囲検索)に用いる要素数である。
本発明の一実施の形態におけるDATAGUIDE部のパステーブルの例である。

符号の説明

0098

10XMLデータ入力部
20クエリ入力部
30 出力部
110 データガイド記憶手段、DATAGUIDE(データガイド)部
120ノードインデックス記憶手段、ノードインデックス部
130統計情報算出手段、統計情報算出部
140選択度計算手段、検索処理部
150パステーブル生成手段

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ