図面 (/)

技術 XMLデータ処理装置、XMLデータ処理方法、XMLデータ処理プログラムおよびXMLデータ処理プログラムを記録した記憶媒体

出願人 日本電信電話株式会社
発明者 江田毅晴鬼塚真山室雅司
出願日 2005年2月21日 (14年5ヶ月経過) 出願番号 2005-044744
公開日 2006年8月31日 (12年10ヶ月経過) 公開番号 2006-228155
状態 特許登録済
技術分野 文書処理装置 検索装置 文書処理装置 計算機におけるファイル管理 機械翻訳
主要キーワード 枝ノード ラベル無し イテレータ 対話型インタフェース ジョイン 検索コスト イベントシーケンス 関係データベース管理システム
関連する未来課題
重要な関連分野

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

図面 (20)

課題

XMLデータに対する問合せにおいて、無駄なリンクの参照をなくして、効率よく問合せの処理を行う装置を提供することを目的とする。

解決手段

検索の対象となるXMLデータの登録時に、XMLデータローダ部230が、XMLデータの要約情報を構成し、前記要約情報に範囲ラベルを付与して、二次記憶装置130に記憶する。検索時に、XMLデータに対する問合せと要約情報を入力として、問合せ解析部150が、前記問合せを木構造に変換して値の部分を削除した問合せ木構造部を生成し、問合せ実行部170が、中間問合せ木と要約情報を照合して中間要約木集合を生成し、前記XMLデータに対して前記中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、前記XMLデータに対して、前記実体中間木の集合に対応する値の部分を用いてフィルタ処理を行い、問合せ結果を出力する。

概要

背景

XMLデータ処理を高速化するための技術は、すでにいくつか公開されている。例えば、非特許文献1は、XMLデータに対する高速な構造ジョインアルゴリズムを提案している。ここで、構造ジョインとは、関係データベースジョイン演算に類似した演算で、複数の検索結果を組み合わせる演算である(詳細は後記する)。また、非特許文献2では、ラベルを用いることで先祖子孫関係および親子関係を指定したデータベース検索を高速化している。そして、非特許文献3では、XMLデータの統計情報を用いることで、構造ジョイン演算の実行順序を最適化して検索を高速にする方法を提案している。
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 Bongki Moon著、"Indexing and Querying XML Data for Regular Path Expressions",(米国) In Proc. VLDB (2001)
Yuqing Wu, Jignesh M. Patel, and H. V. Jagadish著、"Structural Join Order Selection for XML Query Optimization", (米国) In Proc. ICDE (2003)

概要

XMLデータに対する問合せにおいて、無駄なリンクの参照をなくして、効率よく問合せの処理を行う装置を提供することを目的とする。検索の対象となるXMLデータの登録時に、XMLデータローダ部230が、XMLデータの要約情報を構成し、前記要約情報に範囲ラベルを付与して、二次記憶装置130に記憶する。検索時に、XMLデータに対する問合せと要約情報を入力として、問合せ解析部150が、前記問合せを木構造に変換して値の部分を削除した問合せ木構造部を生成し、問合せ実行部170が、中間問合せ木と要約情報を照合して中間要約木集合を生成し、前記XMLデータに対して前記中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、前記XMLデータに対して、前記実体中間木の集合に対応する値の部分を用いてフィルタ処理を行い、問合せ結果を出力する。

目的

そこで、本発明では、前記した問題を解決し、高速なXMLデータ処理を実現するXMLデータ処理装置、XMLデータ処理方法、XMLデータ処理プログラムおよびXMLデータ処理プログラムを記録した記憶媒体を提供することを目的とする。

効果

実績

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

この技術が所属する分野

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

請求項1

演算手段と記憶手段を少なくとも備えた計算機を用いて実現するXMLデータ処理装置であって、前記XMLデータ処理装置が、XMLデータ解析する手段とXMLデータを記憶する手段を備え、検索の対象となるXMLデータの登録時に、前記XMLデータを解析する手段が、前記XMLデータの構成および統計に関する情報を含む要約情報を構成し、前記要約情報に前記XMLデータのノード間の先祖子孫関係を判定可能なラベルを付与し、前記XMLデータを記憶する手段が、前記XMLデータ、前記要約情報および前記ラベルを記憶することを特徴とするXMLデータ処理装置。

請求項2

前記演算手段が、XMLデータのSAXイベントシーケンスを入力として、SAXイベントごとに対応するノード情報が前記要約情報に含まれるか否かを判定し、前記ノード情報が前記要約情報に含まれていない場合に、前記XMLデータを解析する手段が、前記ノード情報を前記要約情報に追加することによって、所定の回数走査で要約情報を構成することを特徴とする請求項1に記載のXMLデータ処理装置。

請求項3

前記先祖子孫関係を判定可能なラベルが、木構造の中で検索の対象となるノードを特定する機能を持つ範囲ラベルであることを特徴とする請求項1または請求項2に記載のXMLデータ処理装置。

請求項4

演算手段と記憶手段を少なくとも備えた計算機を用いて実現するXMLデータ処理装置であって、前記XMLデータ処理装置が、XMLデータに対する問合せを解析する手段と、前記問合せを実行する手段とを備え、前記問合せとXMLデータの構成および統計に関する情報を含む要約情報を入力として、前記問合せを解析する手段が、前記問合せを木構造に変換して属性値またはノードの値の部分を削除した問合せ木構造部を生成し、前記問合せを実行する手段が、前記問合せ木の構造部の部分である中間問合せ木と要約情報とを照合して要約情報の一部の情報を含む中間要約木集合を生成し、前記XMLデータに対して前記中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、前記XMLデータに対して、前記実体中間木の集合に対応する値の部分を用いてフィルタ処理を行い、問合せ結果を得ることを特徴とするXMLデータ処理装置。

請求項5

前記問合せを記述する検索言語がXPathであることを特徴とする請求項4に記載のXMLデータ処理装置。

請求項6

前記問合せを解析する手段が、前記要約情報に対して、イベントシーケンスを作成することを特徴とする請求項4または請求項5に記載のXMLデータ処理装置。

請求項7

前記XMLデータ処理装置が、複数の検索結果を組み合わせる構造ジョインの演算を行う手段をさらに備え、前記構造ジョインの演算を行う手段が、前記中間要約木に対して構造ジョインの演算を用いることで前記実体中間木の集合に変換することを特徴とする請求項4ないし請求項6のいずれか1項に記載のXMLデータ処理装置。

請求項8

前記XMLデータ処理装置が、問合せを最適化する手段をさらに備え、前記問合せを最適化する手段が、前記中間要約木を実体化したデータを含む前記実体中間木の集合に変換する処理である実体化処理の方法と前記実体中間木の集合に対応する値の部分を用いてフィルタ処理の方法を組み合わせた実行プランコストを計算して、最適な実行プランを決定することを特徴とする請求項4ないし請求項7のいずれか1項に記載のXMLデータ処理装置。

請求項9

前記XMLデータ処理装置が、データベースを管理する手段をさらに備え、データベースを管理する手段が、前記XMLデータを管理することを特徴とする請求項4ないし請求項8のいずれか1項に記載のXMLデータ処理装置。

請求項10

前記XMLデータ処理装置が、XMLデータを解析する手段とXMLデータを記憶する手段をさらに備え、検索の対象となるXMLデータの登録時に、前記XMLデータを解析する手段が、前記XMLデータの構成および統計に関する情報を含む要約情報を構成し、前記要約情報に前記XMLデータのノード間の先祖子孫関係を判定可能なラベルを付与し、前記XMLデータを記憶する手段が、前記XMLデータ、前記要約情報および前記ラベルを記憶することを特徴とする請求項4ないし請求項9のいずれか1項に記載のXMLデータ処理装置。

請求項11

前記演算手段が、XMLデータのSAXイベントシーケンスを入力として、SAXイベントごとに対応するノード情報が前記要約情報に含まれるか否かを判定し、前記ノード情報が前記要約情報に含まれていない場合に、前記XMLデータを解析する手段が、前記ノード情報を前記要約情報に追加することによって、所定の回数の走査で要約情報を構成することを特徴とする請求項10に記載のXMLデータ処理装置。

請求項12

前記先祖子孫関係を判定可能なラベルが、木構造の中で検索の対象となるノードを特定する機能を持つ範囲ラベルであることを特徴とする請求項10または請求項11に記載のXMLデータ処理装置。

請求項13

演算手段と記憶手段を少なくとも備えた計算機が実行するXMLデータ処理方法であって、請求項1ないし請求項12のいずれか1項に記載のXMLデータ処理装置を実現することを特徴とするXMLデータ処理方法。

請求項14

演算手段と記憶手段を少なくとも備えた計算機が実行するプログラムであって、請求項1ないし請求項12のいずれか1項に記載のXMLデータ処理装置を実現することを特徴とするXMLデータ処理プログラム

請求項15

演算手段と記憶手段を少なくとも備えた計算機が実行するプログラムであって、請求項1ないし請求項12のいずれか1項に記載のXMLデータ処理装置を実現するXMLデータ処理プログラムを記録していることを特徴とする記憶媒体

技術分野

0001

本発明は、XML(eXtensible Markup Language)データを高速に処理するXMLデータ処理装置XMLデータ処理方法、XMLデータ処理プログラムおよびXMLデータ処理プログラムを記録した記憶媒体に関する。

背景技術

0002

XMLデータ処理を高速化するための技術は、すでにいくつか公開されている。例えば、非特許文献1は、XMLデータに対する高速な構造ジョインアルゴリズムを提案している。ここで、構造ジョインとは、関係データベースジョイン演算に類似した演算で、複数の検索結果を組み合わせる演算である(詳細は後記する)。また、非特許文献2では、ラベルを用いることで先祖子孫関係および親子関係を指定したデータベース検索を高速化している。そして、非特許文献3では、XMLデータの統計情報を用いることで、構造ジョイン演算の実行順序を最適化して検索を高速にする方法を提案している。
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 Bongki Moon著、"Indexing and Querying XML Data for Regular Path Expressions",(米国) In Proc. VLDB (2001)
Yuqing Wu, Jignesh M. Patel, and H. V. Jagadish著、"Structural Join Order Selection for XML Query Optimization", (米国) In Proc. ICDE (2003)

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

0003

しかしながら、これらの技術は、XMLデータが持っている構造を充分に活用切れておらず、まだ、高速化する余地が残っていた。特に、コストが高い構造ジョイン演算の回数を減らすという点では、充分な対応が取られていないという問題があった。

0004

そこで、本発明では、前記した問題を解決し、高速なXMLデータ処理を実現するXMLデータ処理装置、XMLデータ処理方法、XMLデータ処理プログラムおよびXMLデータ処理プログラムを記録した記憶媒体を提供することを目的とする。

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

0005

前記の目的を実現するために、本発明(請求項1)では、演算手段と記憶手段を少なくとも備えた計算機を用いて実現するXMLデータ処理装置であって、前記XMLデータ処理装置が、XMLデータを解析する手段とXMLデータを記憶する手段を備え、検索の対象となるXMLデータの登録時に、前記XMLデータを解析する手段が、前記XMLデータの構成および統計に関する情報を含む要約情報を構成し、前記要約情報に前記XMLデータのノード間の先祖子孫関係を判定可能なラベルを付与し、前記XMLデータを記憶する手段が、前記XMLデータ、前記要約情報および前記ラベルを記憶する。

0006

この構成によれば、XMLデータの要約情報を構成することができる。

0007

また、本発明(請求項2)では、前記演算手段が、XMLデータのSAXイベントシーケンスを入力として、SAXイベントごとに対応するノード情報が前記要約情報に含まれるか否かを判定し、前記ノード情報が前記要約情報に含まれていない場合に、前記XMLデータを解析する手段が、前記ノード情報を前記要約情報に追加することによって、所定の回数の走査で要約情報を構成する。

0008

この構成によれば、所定の回数の走査で要約情報を構成することができる。

0009

また、本発明(請求項3)では、前記先祖子孫関係を判定可能なラベルとして、木構造の中で検索対象となるノードを特定する機能を持つ範囲ラベルを用いる。

0010

この構成によれば、範囲ラベルを用いて効率のよい検索が可能になる。

0011

また、本発明(請求項4)では、演算手段と記憶手段を少なくとも備えた計算機を用いて実現するXMLデータ処理装置であって、前記XMLデータ処理装置が、XMLデータに対する問合せを解析する手段と、前記問合せを実行する手段とを備え、前記問合せとXMLデータの構成および統計に関する情報を含む要約情報を入力として、前記問合せを解析する手段が、前記問合せを木構造に変換して属性値またはノードの値の部分を削除した問合せ木構造部を生成し、前記問合せを実行する手段が、前記問合せ木の構造部の部分である中間問合せ木と要約情報とを照合して要約情報の一部の情報を含む中間要約木集合を生成し、前記XMLデータに対して前記中間要約木の集合を実体化したデータを含む実体中間木の集合に変換し、前記XMLデータに対して、前記実体中間木の集合に対応する値の部分を用いてフィルタ処理を行い、問合せ結果を得る。

0012

この構成によれば、要約情報と問合せを入力して、XMLデータから所望の検索結果を得ることができる。

0013

また、本発明(請求項5)では、前記問合せを記述する検索言語としてXPathを用いる。

0014

この構成によれば、XPathの書式で問合せを行うことができる。

0015

また、本発明(請求項6)では、前記問合せを解析する手段が、前記要約情報に対して、イベントシーケンスを作成する。

0016

この構成によれば、要約情報をイベントシーケンスに変換できる。

0017

また、本発明(請求項7)では、前記XMLデータ処理装置が、複数の検索結果を組み合わせる構造ジョインの演算を行う手段をさらに備え、前記構造ジョインの演算を行う手段が、前記中間要約木に対して構造ジョインの演算を用いることで前記実体中間木の集合に変換する。

0018

この構成によれば、XMLデータへの問合せの中間処理段階を効率化することが可能になる。

0019

また、本発明(請求項8)では、前記XMLデータ処理装置が、問合せを最適化する手段をさらに備え、前記問合せを最適化する手段が、前記中間要約木を実体化したデータを含む前記実体中間木の集合に変換する処理である実体化処理の方法と前記実体中間木の集合に対応する値の部分を用いてフィルタ処理の方法を組み合わせた実行プランのコストを計算して、最適な実行プランを決定する。

0020

この構成によれば、問合せの処理をさらに効率化できる。

0021

また、本発明(請求項9)では、前記XMLデータ処理装置が、データベースを管理する手段をさらに備え、データベースを管理する手段が、前記XMLデータを管理する。

0022

この構成によれば、二次記憶装置保管されているXMLデータを効率よく参照することができる。

0023

また、本発明(請求項10)では、前記XMLデータ処理装置が、XMLデータを解析する手段とXMLデータを記憶する手段をさらに備え、検索の対象となるXMLデータの登録時に、前記XMLデータを解析する手段が、前記XMLデータの構成および統計に関する情報を含む要約情報を構成し、前記要約情報に前記XMLデータのノード間の先祖子孫関係を判定可能なラベルを付与し、前記XMLデータを記憶する手段が、前記XMLデータ、前記要約情報および前記ラベルを記憶する。

0024

この構成によれば、XMLデータに対する事前処理により要約情報を得て、さらに、この要約情報と問合せを与えることにより、問合せを効率よく処理することができる。

0025

また、本発明(請求項11)では、前記演算手段が、XMLデータのSAXイベントシーケンスを入力として、SAXイベントごとに対応するノード情報が前記要約情報に含まれるか否かを判定し、前記ノード情報が前記要約情報に含まれていない場合に、前記XMLデータを解析する手段が、前記ノード情報を前記要約情報に追加することによって、所定の回数の走査で要約情報を構成する。

0026

この構成によれば、効率よく要約情報を構成することができる。

0027

また、本発明(請求項12)では、前記先祖子孫関係を判定可能なラベルとして、木構造の中で検索対象となるノードを特定する機能を持つ範囲ラベルを用いる。

0028

この構成によれば、範囲ラベルを用いて効率のよい検索が可能になる。

発明の効果

0029

このようなXMLデータ処理装置、XMLデータ処理方法、XMLデータ処理プログラムおよびXMLデータ処理プログラムを記録した記憶媒体によれば、検索対象となるXMLデータがもっているデータの構造を活用して、高速なXMLデータの処理が可能になる。

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

0030

次に、本発明の実施形態について、適宜図面を参照しながら詳細に説明する。

0031

<<第1の実施形態>>
システム構成
図1は、本発明の第1の実施形態におけるXMLデータ処理装置100の構成を説明する図である。XMLデータ処理装置100は、主記憶装置110、CPU(Central Processing Unit、中央演算装置)120および二次記憶装置130を備えた計算機にXMLデータを処理するための計算機プログラムが読み込まれることで構成される。

0032

問合せ解析部150は、XMLデータへの問合せ(図5参照)を字句解析および構文解析し、問合せの内部表現である問合せ木(図7参照)を生成する。また、問合せ解析部150は、問合せ木を構造部と値処理部に分離し、中間問合せ木を生成する。

0033

問合せ最適化部160は、問合せ最適化を行う場合に、中間問合せ木から問合せ実行プラン(説明は後記する)を生成し、それぞれの実行プランのコストをXMLデータの構成に関する情報や統計情報などから計算し、その中から最適な実行プランを選ぶ。

0034

問合せ実行部170は、問合せ解析部150から渡された中間問合せ木、または、問合せ最適化部160から渡された実行プランを実行する。このとき、問合せ実行部170は、二次記憶装置130に格納されたXMLデータおよびXMLデータの木構造の情報を要約したデータガイド木(ストロングデータガイド木、請求項における要約情報に該当)240を対象として問い合わせを実行する。なお、二次記憶装置130には、後記するディスクマネージャ部190を介してアクセスし、データガイド木(ストロングデータガイド木)240には、イベントシーケンス生成部210を介してアクセスする。

0035

構造ジョイン演算部180は、既存技術である構造ジョインの演算を行う。そして、このとき、ディスクマネージャ部190を介して二次記憶装置130にアクセスする。

0036

なお、構造ジョインとは、関係データベースのジョイン演算に類似した演算である。関係データベースにおけるジョイン演算では、テーブルの結合処理の際に指定された項目の値が結合する両方のテーブルのエントリタプル)に共通に出現するエントリだけを対象としてその全ての組み合わせに対応するエントリを生成する。それに対して、XMLデータに対する構造ジョインでは、親子関係または先祖子孫関係の問合せを行うときに、個別に2つのタグ名を検索しておいて、これらの検索結果を親子関係または先祖子孫関係に基づいて組み合わせて、所望の検索結果を得るというものである。たとえば、「//Book//person」という問合せを行ったときに、「Book」を検索する演算と「person」を検索する演算を個別に行い、これらの検索結果を組み合わせて、「//Book//person」に対する結果を生成する。この際、親子関係または先祖子孫関係のリンクを辿る通常の方法を用いると全ての対象ノードに対する検索を必要とするが、後記する範囲ラベルを用いて対象ノードを限定して構造ジョインを行えば、効率的に所望のデータが得られる。

0037

ディスクマネージャ部190は、二次記憶装置130に格納されたXMLデータへのアクセス手段を提供する。

0038

結果生成部200は、既存技術を用いて問合せの処理結果を生成する。XPathの問い合わせ処理結果は、結果ノードの指定する部分木であるため、結果生成部200は、このような結果を生成する。

0039

イベントシーケンス生成部210は、データガイド木(ストロングデータガイド木)240からイベントシーケンス(図4参照、説明は後記する)を生成する。なお、データガイド木(ストロングデータガイド木)240については、図8および図9を用いた説明において、後記する。

0040

データガイド木ローダ部220は、二次記憶装置130に記録する前のXMLデータ20、または、記録後のXMLデータ140からデータガイド木(ストロングデータガイド木)240をロードする。

0041

XMLデータローダ部230は、XMLデータ20を二次記憶装置130にロードする。XMLデータローダ部230は、データガイド木ローダ部220と並行して動くことができる。そして、XMLデータローダ部230は、主記憶装置110の容量に応じて、次の3つの方式でデータガイド木240に付与する範囲ラベル(詳細は後記)を格納する。
(1)主記憶装置110の容量が充分に大きい場合、範囲ラベルを主記憶装置110に全て格納する。
(2)主記憶装置110の容量が中程度の場合、範囲ラベルの一部を主記憶装置110に格納し、残りの一部を二次記憶装置130に格納する。
(3)主記憶装置110の容量が小さい場合、範囲ラベルは全て二次記憶装置130に格納する。

0042

この格納方式は、利用者が選択することができる。(1)の場合は、主記憶装置110の中に範囲ラベルを全て保持するため、必要な容量は大きくなるが、構造ジョインが全て主記憶装置110内で完結するため、非常に高速に処理を行うことができる。

0043

(2)の場合は、利用者の問合せに頻出するノードの範囲ラベルを主記憶装置110の中に保持することにより、(1)に比べて必要な一次記憶装置の容量を削減しつつも、頻出する問合せに関しては、効率よく処理できる。

0044

(3)の場合は構造ジョインを実行する際に範囲ラベルを主記憶装置110に取り出す必要があるが、構造ジョイン回数は削減されるため、主記憶装置110の容量が少ない場合にも、効率のよい処理が可能になる。

0045

本実施形態において、利用者10は、XPathの検索式を用いて、プログラミングAPIや対話型インタフェースプログラムなどからデータベースに問合せを行う。利用者10が入力したXPathの検索式は、問合せ解析部150で構文解析されて、問合せ木になり、問合せ木は、図10に示すような構造部300と値処理部310に分解されて、さらに、ストロングデータガイド木と組み合わせて処理されて、問合せ中間要約木に変換される。問合せ最適化部160は、中間木実体化処理および値処理部のフィルタリング処理の実行順序(プラン)を決定する。このとき、二次記憶装置130に格納されたXMLデータの構成に関する情報やXMLデータの統計情報等を用いる。そして、問合せ実行部170が、決定された実行順序(プラン)にそって検索処理を実行する。

0046

問合せ処理
図2の(a)は、XPath処理の前に行うXPath事前処理の概要を説明する図である。そして、図2の(b)は、XPath処理の概要を説明する図である。

0047

図2の(a)に示されているXPath処理に先立って行なわれるXPath事前処理では、予め与えられたXMLデータに対応するストロングデータガイド木を生成する(S100)。そして、このストロングデータガイド木を利用して、後記するXPath処理を行う。

0048

図2の(b)に示されているXPath処理では、まず、ストロングデータガイド木を元にイベントシーケンスを生成する(S110)。なお、このステップS110をXPath事前処理において行ってもよい。

0049

次に、ステップS110において作成したストロングデータガイド木に対応するイベントシーケンスを用いてXPath処理を行う(S120)。ステップS120は、後記する中間要約木を得るまでの処理に該当する。なお、本実施形態では、ステップS110においてストロングデータガイド木からイベントシーケンスに変換し、ステップ120において生成したイベントシーケンスをXPath処理して中間要約木を得る方法を利用しているが、XPath処理方法は、これに限定されない。代わりに既存の各種XPath処理方法を用いても構わない。例えば、問合せをボトムアップに処理することにより、多項式時間で処理可能なXPath処理アルゴリズムなどの公知技術(Georg Gottlob, Christof Koch and Reinhard Pichler著、"Efficient Algorithms for Processing XPath Queries"(米国) In Proc. VLDB(2002)参照)を用いて、ストロングデータガイド木をXML木とみなして、XPath処理を行ってもよい。また、この処理の際には、イベントシーケンスを作成しなくてもよい。

0050

そして、ここまでのXPath処理では行っていない残りのXPath処理を最適化するか否かを判断する(S130)。XPath処理を最適化しない場合には(S130のNo)、二次記憶装置130のXMLデータ140(図1参照)を用いて残りのXPath処理を所定の順序で行う。すなわち、予め固定された処理手順でXMLデータに対する検索を行い、処理を終了する。

0051

残りのXPath処理を最適化する場合には(S130のYes)、残りのXPath処理のコストを見積もり処理順序を決定する(S150)。すなわち、最適な処理順序を決定する。そして、決定された順序で残りのXPath処理を行い(S160)、処理を終了する。

0052

図3は、XMLデータの例を説明する図である。図3に示すように、XMLデータはタグを用いて構造化されている。例えば、図3に含まれている以下の行は、1つのタグのまとまりに該当する。
XML 1
そして、このtitleのタグも、Booklistのタグに含まれる形で構造化されている。XMLデータは、このようなタグによる構造化によってデータを記述している。

0053

図4は、SAX(SimpleAPI for XML)のイベントシーケンスの例を示す図である。なお、SAXは、リアルタイムに少ないメモリで、木を作らずに、XML文書を上から下へと走査して構文解析処理を行う技術である。図4のイベントシーケンスは、図3のXMLデータの例に対してSAXの技術を用いて、イベントを抽出することによって生成したものである。

0054

図5は、図3のXMLデータに対して構築したXML木の例を示す図である。図5に示すようにXML木は1つのタグに対応して1つのノードを定義している。XML木は、枠で囲まれて示しているタグや属性に対応する一番下のノードの下にテキストの値や属性値を示す葉ノードがつながった構造をしている。

0055

図5のXML木においては、Booklistをルートノードとして、その下にBookのノードが3つ出現している。そして、そのBookのノードの下には、それぞれtitleのノードが出現している。このように、もとのXMLデータを単純に変換したXML木では、同様のノードのパターンが複数出現することがある。ストロングデータガイド木は、この繰り返しパターン集約しているため、無駄なく検索を行うために用いることができる。

0056

なお、XML木の中でノード名の記述が「@」からはじまるものは、属性を表すノードであり、その下につながって記載されているのが属性値である。この例では、「@isbn」が属性のノードである。

0057

図6は、XPathによる問合せの例を示す図である。図6には、(1)から(4)まで4つの問い合わせの例を示しているが、問合せにおいては、親子関係だけでなく、先祖子孫関係も用いて検索対象を指定できる。「/」はノード間の親子関係を表し、「//」はノード間の先祖子孫関係を表す。

0058

図6の例のうち、(1)の例は、親子関係を用いた例であり、ルートノードの下にBooklistというノードが親子関係でつながっており、同様にそのBooklistのノードにBookのノードが連なり、さらにBookのノードからauthorsのノード、さらにpersonのノードがそれぞれ親子関係で連なっている構造のデータを検索する問い合わせである。

0059

(2)から(4)の問合せでは、親子関係だけでなく、先祖子孫関係も用いている例である。例えば、(4)の例では、ルートノードとBookの間に先祖子孫関係があるという記述になっている。そして、(2)から(4)の例では、値や属性値を指定する問合せの例になっている。

0060

図7は、図6の問合せ(1)から(4)に対応する問合せ木の例を示す図である。この例のようにXPathの問合せは、木で表現できる。

0061

図8は、図5に示したXML木に対応するストロングデータガイド木の例を示す図である。ストロングデータガイド木は、図5のXML木に示された木構造の情報について要約した情報を表している。すなわち、ノード間の関係を抽出してまとめた情報になっている。ストロングデータガイド木を生成する方法は後記する。

0062

図9は、範囲ラベル付ストロングデータガイド木の例を示す図である。図9に示すように、ストロングデータガイド木の各ノードは1つずつキューを持っていて、左右の2つの数字が並んでいるラベルがそのキューの中に収納される構成になっている。範囲ラベル付ストロングデータガイド木を構成する方法は後記する。

0063

図10は、問合せ木の構造部と値処理部を説明する図である。図10に示す問合せ木は図7の問合せ木と同じものであるが、図10に示すように、構造部300と値処理部310に分けることができる。このとき、値および属性値を持たない問合せ木では、構造部300のみで、値処理部310は存在しないことになる。この問合せ部300と値処理部310を分ける処理は、後記する中間要約木を得る処理において用いられる。

0064

図11は、範囲ラベル無しのストロングデータガイド木を生成する処理を説明する図である。この処理では、SAXイベントを入力して、ラベル無しのストロングデータガイド木を出力する処理である。

0065

まず、最初のあるいは次のSAXイベントを入力して(S200)、処理を開始する。そして、そのSAXイベントが開始イベントか否かを調べる(S210)。開始イベントとは、図4に示した例における「start(Booklist)」のような「start()」という形をしたイベントのことである。

0066

開始イベントでなかった場合は(S210のNo)、入力されたSAXイベントが終了イベントか否かを調べる(S220)。ここで、終了イベントとは、図4に示した例における「end(Booklist)」のような「end()」という形をしたイベントのことである。終了イベントであった場合は(S220のYes)、ストロングデータガイド木における各時点において対象となっているノードである現在ノードをその現在ノードの親ノード(ルートノード側に1つ上がったノード)に移動し(S230)、後記するステップS290に進む。終了イベントでなかった場合は(S220のNo)、そのままステップS290に進む。

0067

ステップS210において、SAXイベントが開始イベントであった場合は(S210のYes)、入力されたSAXイベントのタグ名がストロングデータガイド木に存在するか否かを調べる(S240)。そのタグ名が存在しなかった場合(S240のNo)、そのタグ名で子ノードをストロングデータガイド木に追加し(S250)、ステップS260に進む。そのタグ名が存在した場合(S240のYes)、そのままステップS250を実行せずにステップS260に進む。

0068

ステップS260では、そのノード、すなわち、前記の同じタグ名のノードまたは前記の新たに追加した子ノードに現在ノードを移動する。そして、その入力されたSAXイベントが属性を持つか否かを調べる(S270)。属性を持たない場合は(S270のNo)、そのままステップS290に進み、属性を持つ場合は(S270のYes)、その属性に対応する子ノードの追加処理を行い(S280)、ステップS290へ進む。なお、その属性に対応する子ノードの追加処理については、詳細を後記する。

0069

ステップS290では、その時点で全てのSAXイベントを入力済みか否かについて調べる。その結果、未入力のSAXイベントがある場合は(S290のNo)、ステップS200から処理を繰り返す。全てのSAXイベントが入力済みである場合には(S290のYes)、その時点までに作成したストロングデータガイド木を出力して(S300)、処理を終了する。

0070

図12は、範囲ラベル無しのストロングデータガイド木に属性に対応する子ノードを追加する処理を説明する図である。なお、図12は、図11におけるステップS280の処理を詳細に示したものである。

0071

まず、処理の対象となる属性名Aを入力する(S400)。そして、その属性名Aに対応する「@A」を名前とする子ノードが現在ノードに存在するか否かを調べる(S410)。例えば、属性名Aが「isbn」であった場合は、「@isbn」という名前の子ノードが存在するか否かを調べる。存在しない場合は(S410のNo)、属性名Aに対応する「@A」を名前とする子ノードを現在ノードに追加して(S420)、ステップS430に進む。存在する場合は(S410のYes)、そのままステップS430に進む。

0072

ステップS430では、その時点で全ての属性を処理したか否かを調べる(S430)。全ての属性を処理し終わっている場合は(S430のYes)、そのまま処理を終了し、未処理の属性が残っている場合は(S430のNo)、ステップS400に戻って処理を繰り返す。

0073

図13は、範囲ラベル付きのストロングデータガイド木を生成する処理を説明する図である。
範囲ラベルは、図9に示したように左右2つの値の組をラベルとして用いるが、まず、このラベルを管理するためのラベルの左の値leftと右の値rightを初期化する(S500)。例えば、それぞれの値を1にしてもよい。そして、ルートノードを作成し、現在ノードをルートノードに設定する(S510)。これは、ストロングデータガイド木の初期化に該当するものである。

0074

そして、最初の、または、次のSAXイベントを入力する(S520)。そして、そのSAXイベントに応じて範囲ラベルつきストロングデータガイド木を構築する処理を行う(S530)。このステップS530の処理についての詳細は後記する。

0075

そして、その時点までに全てのSAXイベントを入力済みか否かについて調べる(S540)。その結果、未入力のSAXイベントがある場合には(S540のNo)、ステップS520から処理を繰り返す。全てのSAXイベントが入力済みの場合は(S540のYes)、その時点までに作成した範囲ラベル付きストロングデータガイド木を出力して(S550)、処理を終了する。

0076

図14は、1つのSAXイベントに応じて範囲ラベル付きストロングデータガイド木を構築する処理を説明する図である。図14で説明する処理は、図13のステップS530の処理に該当し、図14における入力や変数を引き継いで処理するサブルーチン役割を果たす。

0077

まず、入力されたSAXイベントが開始イベントか否かを調べる(S600)。開始イベントだった場合(S600のYes)、図13の処理で説明したleftの値を変数lに保存し、leftの値を増やす(S610)。このとき、leftの値を増やすときの増分は所定の値であればよい。例えば、その所定の増分を1や10にしてもよい。

0078

そして、そのSAXイベントの開始タグ名TAGを名前とする子ノードが存在するか否かを調べる(S620)。例えば、SAXイベントの開始タグ名が「title」だったとすると、それと同じ「title」という名前の子ノードがあるか否かを調べる。SAXイベントの開始タグ名TAGと同じ名前の子ノードが存在しない場合(S620のNo)、現在ノードにそのTAGを名前とする子ノードを追加する(S630)。例えば、「title」という開始タグ名の場合は、「title」という名前の子ノードを追加する。そして、次のステップS640に進む。既に同じ名前の子ノードが存在する場合は(S620のYes)、そのままステップS640に進む。

0079

ステップS640では、現在ノードをその子ノードに移動する(S640)。すなわち、子ノードを追加した場合はその子ノードに、同じ名前の子ノードが存在した場合はその子ノードに、現在ノードを移動する。そして、SAXイベントが属性を持つか否かを調べる(S650)。属性を持つ場合は(S650のYes)、属性子ノード追加および範囲ラベル付与処理を行い(S660)、ステップS670の処理に進む。なお、このステップS660の処理の詳細については、後記する。属性を持たない場合は(S650のNo)、そのままステップS670に進む。

0080

ステップS670では、現在ノードのキューの最後にステップS610で保存した変数lの値を用いて(l,NULL)のラベルを追加し、処理を終了する。なお、NULLは、有効なラベルの値が入っていないことを表す特別な値である。

0081

ステップS600においてSAXイベントが開始イベントではなかった場合(S600のNo)、次に、そのSAXイベントが終了イベントか否かを調べる(S680)。終了イベントではない場合は(S680のNo)、SAXイベントがテキストノードイベントか否かを調べる(S690)。なお、テキストノードイベントとは、図4に示したイベントシーケンスに出現している「text(“XML 1”)」と同じ「text()」という形をしたイベントを指す。調べた結果、テキストノードイベントではない場合は(S690のNo)、そのまま処理を終了し、テキストノードイベントであった場合は(S690のYes)、テキストノードのラベルの左側にleft、右側にrightの値を入れて、そのラベルを現在ノードのキューに入れる(S700)。そして、leftとrightの値を増やして(S710)、処理を終了する。

0082

ステップS680においてSAXイベントが終了イベントだった場合(S680のYes)、現在ノードのキューの中で、ラベルの右側の値がNULLになっている最後のラベルの右にrightの値を入れて、このラベルをキューに入れる(S720)。そして、rightの値を増やす(S730)。そして、現在ノードを現在ノードの親ノードに移動して(S740)、処理を終了する。

0083

図15は、属性子ノード追加および範囲ラベル付与処理を説明する図である。なお、この処理は、図14のステップS660の処理に該当し、入力や変数を引き継いで処理するサブルーチンの役割を果たす。

0084

まず、leftとrightの値を引き継いで(S800)、処理を開始する。そして、まず、属性名Aを入力する(S810)。そして、現在ノードに属性名Aに対応する「@A」を名前とする子ノードが存在するか否かを調べる(S820)。その結果、そのような子ノードが存在しない場合は(S820のNo)、「@A」を名前とする子ノードを現在ノードに追加し(S830)、ステップS840に進む。同じ名前の子ノードが存在する場合は(S820のNo)、そのままステップS840に進む。

0085

ステップS840では、属性名Aに対応する「@A」を名前とする子ノードに対して、(left,right)のラベルをキューに入れる(S840)。そして、leftとrightの値をそれぞれ増加させる(S850)。そして、この時点で全ての属性を処理したか否かを調べる(S860)。既に全ての属性を処理している場合には(S860のYes)、処理を終了する。まだ処理されていない属性がある場合には(S860のNo)、ステップS810に戻って処理を繰り返す。

0086

図16は、ストロングデータガイド木からイベントシーケンスを構築する処理を説明する図である。図17は、ストロングデータガイド木に対するイテレータの探索例を説明する図である。図16に加えて、適宜、図17も参照しつつ、イベントシーケンスを構築する処理について説明する。

0087

この処理では、まず、ストロングデータガイド木を入力し、そのルートノードを現在ノードとする(S900)。そして、現在ノードのイテレータが下降する方向に動くか否かを調べる(S910)。なお、下降するとは、ルートノードから遠ざかる動きをすることを指す。また、ここでのイテレータとは、ストロングデータガイド木のような木構造データなどを扱うための処理モジュールを指し、イテレータは、最初はルートノードに位置していて、図17の例に示すように、木構造を下降したり、上昇したりしながら、木全体を探索する動きをするものである。

0088

ステップS910で調べた結果、イテレータが下降する方向に動く場合は(S910のYes)、現在ノードのノード名Nを用いて、「start(N)」を出力し(S940)、ステップS970に進む。このとき、例えば、ノード名Nが「authors」だった場合には、「start(authors)」が出力される。

0089

ステップS910で調べた結果、イテレータが下降する方向に動かない場合は(S910のNo)、次に、現在ノードのイテレータが上昇する方向に動くか否かを調べる(S920)。上昇する方向に動く場合は(S920のYes)、現在ノードのノード名Nを用いて、「end(N)」を出力し(S950)、ステップS970に進む。

0090

ステップS920で調べた結果、イテレータが上昇する方向に動かない場合は(S920のNo)、現在ノードのイテレータが属性を認識するか否かを調べる(S930)。属性を認識した場合は(S930のYes)、現在ノードのノード名Nを用いて、「attr@(N)」を出力し(S960)、ステップS970へ進む。属性を認識しない場合は(S930のNo)、そのままステップS970に進む。

0091

ステップS970では、現在ノードのイテレータに次のイベントを設定し(S970)、この時点で全てのノードを処理してルートノードに戻ったか否かを調べる(S980)。なお、このとき、イテレータからNULLの値が返ってくれば全てのノードを処理してルートノードに戻ったということを意味している。全ての処理が終わっていれば(S980のYes)、処理を終了し、まだ処理が残っていれば(S980のNo)、ステップS910に戻って、処理を繰り返す。

0092

図18は、ストロングデータガイド木により問合せて中間要約木を得る処理を説明する図である。
まず、ストロングデータガイド木とXPathによる問合せを入力する(S1000)。そして、XPathによる問合せの構造部を取り出す(S1010)。なお、この問合せの構造部とは、図10において記載されている構造部300と同様のものを指す。

0093

そして、ストロングデータガイド木をXMLデータとみなし、前記構造部のXPath処理を実行し、内部マッチ木の列を得る(S1020)。それから、内部マッチ木から分岐ノード枝ノードの組からなる中間要約木列を取り出して出力し(S1030)、処理を終了する。

0094

図19は、中間要約木から実態中間木を生成する処理を説明する図である。
まず、中間要約木を入力し(S1100)、中間要約木の全てのノード間に対する構造ジョインを行い、実体中間木を生成する(S1110)。

0095

その後、全ての中間要約木を処理したか否かを調べて(S1120)、処理が終わっていない場合は(S1120のNo)、ステップS1100に戻って処理を繰り返す。全ての中間要約木を処理し終わっている場合は(S1120のYes)、それまでの処理で得られた実体中間木列を出力し(S1130)、処理を終了する。

0096

図20は実体中間木列にフィルタ条件を適用してXPath問合せ結果を得る処理を説明する図である。
まず、実体中間木列を入力し、この処理の過程で生じるアウトプットノードを入れるキューQOを用意する(S1200)。そして、実体中間木列に値処理部があるか否かを調べる(S1210)。このとき、実体中間木列の中の実体中間木の1つ以上に値処理部があれば、実体中間木列に値処理部があるとし、1つもなければ、値処理部がないとする。

0097

この結果、値処理部がなければ(S1210のNo)、そのままステップS1250に進む。値処理部があった場合は(S1210のYes)、問合せ木の値処理部のフィルタ条件を二次記憶装置130から取り出して実体中間木の葉ノード(一番末端のノード)に適用する(S1220)。そして、出力されたノードをキューQOに追加する(S1230)。そして、この時点で全ての実体中間木を処理したか否かを調べて(S1240)、処理が終わっていない場合には(S1240のNo)、ステップS1220から処理を繰り返し、処理が終わっている場合には、ステップS1250に進む。

0098

ステップS1250では、ここまでの処理でノードを追加したキューQOの中で重複するラベルを除去する(S1250)。ここでは、この処理で得られたアウトプットノードの中に同じラベルがある可能性があるので、同一のラベルは1つだけ残すようにして、他の重複したラベルは全て削除する。そして、QOのラベルを用いて二次記憶装置130から検索結果を取り出して出力し(S1260)、処理を終了する。

0099

図21は、実行プラン群を生成して最小コストを求める処理を説明する図である。この処理は、図19(実体化プラン)および図20(フィルタ条件適用)を用いて説明したような所定の実行プランに代替できる実行プランを決定する処理である。このとき、様々な実体化プランとフィルタ条件の組み合わせを調べてその最小コストのものを実行プランと決定する。

0100

まず、実体化プランとフィルタ条件の組を出力する(S1300)。そして、実体化プランとフィルタ条件の組を一つの実行プランとして、そのコストを求める(S1310)。このときのコストは、例えば、二次記憶装置130に対するアクセスの回数などをコストとしてもよいが、検索コストを反映する指標であればなんでもよい。

0101

そして、全ての実体化プランとフィルタ条件の組(実行プラン)を入力したか否かを調べる(S1320)。まだ、未入力のものがある場合は(S1320のNo)、ステップS1300に戻って処理を繰り返し、全ての組を入力し終わっている場合には(S1320のYes)、求めたコストの中で最小となる実行プランを出力し(S1330)、処理を終了する。

0102

なお、実際の検索では、この処理の後に、この実行プランに基づいて、図19および図20において説明した処理に対応する処理(実際に検索結果を得る処理)を行うことになる。例えば、図19および図20で説明した処理も、最小コストであれば、その処理の例となり得る。最小コストの実行プランの具体的な処理については、説明を省略する。

0103

ここまで、第1の実施形態について説明してきたが、この実施形態によれば、XMLデータの構造を集約して予め要約情報(ストロングデータガイド木)として持っておくことにより、XMLデータの木構造の中から無駄なく効率的に問合せに対応する検索を行うことができる。しかも、XMLデータ処理装置100の主記憶装置110の容量にあわせて、その構成に応じて最適なデータ配置をとることで、効率的な問合せ処理を行うことができる。

0104

<<第2の実施形態>>
図22は、第2の実施形態におけるXMLデータ処理装置の構成を説明する図である。
第1の実施形態では、XMLデータ140は、二次記憶装置130に記録してあって、ディスクマネージャ部190が管理していたが、この二次記憶装置130に記録してあるXMLデータ140をより効率的に管理するために関係データベース管理システムを導入し、XMLデータ140を関係データベースとして記録、管理する実施形態をとることもできる。この第2の実施形態は、関係データベース管理システムに関する部分以外の構成は、第1の実施形態と同じであるので、説明を省略し、ここでは、第1の実施形態と異なる構成要素について説明する。

0105

第2の実施形態では、二次記憶装置130の中に記録されているXMLデータ140Aは関係データベース(RDB)として記録されている。また、第2の実施形態では、ディスクマネージャ部190に替えて、関係データベース管理システムのプログラミングAPI250が導入され、関係データベースとして記録されているXMLデータ140Aに対するアクセスを管理している。

0106

第2の実施形態における問合せ処理は、第1の実施形態と同じなので説明を省略する。ただし、前記したように二次記憶装置130に記録されているXMLデータ140Aに対するアクセスの方式だけが異なっている。

0107

第2の実施形態によれば、第1の実施形態と同様に、XMLデータの構造を集約して予め要約情報(ストロングデータガイド木)として持っておくことにより、XMLデータの木構造の中から無駄なく効率的に問合せに対応する検索を行うことができる。さらに、第2の実施形態では、二次記憶装置に記録されているXMLデータに対するアクセスが効率化されるので、さらに効率的な問合せ処理が可能になる。

0108

ここまで、本発明の実施形態について説明してきたが、本発明の趣旨から逸脱しない範囲内で実施形態の変更が可能である。例えば、XMLデータを二次記憶装置に記録するかわりに主記憶装置の容量を大きくして、全てのXMLデータをそこに記録したり、二次記憶装置を半導体で構成されたディスク装置に変更したりしてもよい。なお、本実施形態におけるXMLデータ処理装置は、演算手段を用いてプログラムで実現されており、所定の機能を備えた計算機に所定のプログラムを読み込む事で動作できる状態になる。そして、このプログラムを記憶媒体に記録しておいて、これを計算機に読み込ませることでXMLデータ処理装置を実現してもよい。

図面の簡単な説明

0109

第1の実施形態におけるXMLデータ処理装置の構成を説明する図である。
(a)は、XPath処理の前に行うXPath事前処理の概要を説明する図であり、図2の(b)は、XPath処理の概要を説明する図である。
XMLデータの例を説明する図である。
SAXのイベントシーケンスの例を示す図である。
図3のXMLデータに対して構築したXML木の例を示す図である。
XPathによる問合せの例を示す図である。
図6の問合せの例に対応する問合せ木の例を示す図である。
図5に示したXML木に対応するストロングデータガイド木の例を示す図である。
範囲ラベル付ストロングデータガイド木の例を示す図である。
問合せ木の構造部と値処理部を説明する図である。
範囲ラベル無しのストロングデータガイド木を生成する処理を説明する図である。
範囲ラベル無しのストロングデータガイド木に属性に対応する子ノードを追加する処理を説明する図である。
範囲ラベル付きのストロングデータガイド木を生成する処理を説明する図である。
1つのSAXイベントに応じて範囲ラベル付きストロングデータガイド木を構築する処理を説明する図である。
属性子ノード追加および範囲ラベル付与処理を説明する図である。
ストロングデータガイド木からイベントシーケンスを構築する処理を説明する図である。
ストロングデータガイド木に対するイテレータの探索例を説明する図である。
ストロングデータガイド木により問合せて中間要約木を得る処理を説明する図である。
中間要約木から実態中間木を生成する処理を説明する図である。
実体中間木列にフィルタ条件を適用してXPath問合せ結果を得る処理を説明する図である。
実行プラン群を生成して最小コストを求める処理を説明する図である。
第2の実施形態におけるXMLデータ処理装置の構成を説明する図である。

符号の説明

0110

10利用者
20XMLデータ(記録前)
100XMLデータ処理装置
110主記憶装置
120 CPU
130二次記憶装置
140、140A XMLデータ(記録後)
150問合せ解析部
160 問合せ最適化部
170 問合せ実行部
180 構造ジョイン演算部
190ディスクマネージャ部
200 結果生成部
210イベントシーケンス生成部
220 データガイド木ローダ部
230 XMLデータローダ部
240 データガイド木(ストロングデータガイド木)
250プログラミングAPI

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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