論文

DBSJ Letters Vol. 4, No. 4

される DFA を用いて処理をする手法も提案されている [8, 9, 18]．
パスプルーニングによる決定性有 我々の手法では，パスプルーニングを用いることで質問式中のパ限オートマトンを用いた XQuery スを具体化し，NFA から DFA へと変換するのではなく，直接，コンパクトな DFA を構成する．
処理の提案
また，本手法を実装し実際の XML データを用いた実験および

A Proposal for XQuery Processor with Deterministic Automaton and Path Pruning

石野明∗

Akira ISHINO

竹田

正幸† ‡

Masayuki TAKEDA

XMark ベンチマーク [14] の結果を示す．
本稿の構成は次の通りである．2 節では，XQuery の部分族，XML
データ走査器，NFA によるパスパターン照合について述べ，本稿における議論の準備をおこなう．3 節では，パスプルーニングとそれによって得られる DFA によってパスパターンの照合が行えることを示す．4 節では DFA に対する処理の割り当てによる XQueryの質問式の処理手法を述べ，5 節では実装と実験の結果を報告す
る．最後に 6 節でまとめを行う．

本稿では，文字列検索技術を応用した単純で高速な XQuery 処
理手法を提案する．XML データから Aho-Corasick 法を拡張した
2. 準備
XML データ走査器によって高速にタグやキーワードの検出を行
い，パスに応じた処理を行うことで XQuery の質問式を処理する． 2.1 XQuery の部分族
特にパスの照合を高速に処理するために，XML データから得ら
本稿では XQuery [16] のすべてを扱うことはせず，XML データ
れるパススキーマを用いることで決定性有限オートマトンを構築 を先頭から順に読み込んで処理が可能な範囲に止める．
するパスプルーニングを提案する．また，実際に本手法の実装を
まず，パスとして子軸と子孫軸のみを扱い，親軸や先祖軸等の行い，その実験結果について述べる．
他の軸は扱わない．親軸や先祖軸を考慮した場合，処理の途中でThis paper describes a simple, efﬁcient XQuery processor by
applying text search methods. First, the processor detects tags andkeywords by using a pattern matching machine, which is based on
the Aho-Corasick method. Second, the processor uses the DFA obtained from path pruning to process the sequence from the patternmatching machine. Finally, the processor outputs the result of aquery. We also validate the processor and provide performance
results.

1. はじめに
今日，科学研究，電子商取引，WWW をはじめとした，様々な分野において XML データが共通のフォーマットとして利用されている．このような大規模な XML データに対して，特定の条件に合致する部分を見つけ出し，それらを特定のフォーマットへと加工したり，ときには集計などの処理結果を出力することは重要な問題である．
そこで本稿では，World Wide Web コンソーシアムによって提案された XML データに対する検索言語 XQuery [16] を文字列検索技術を応用することで処理する手法を提案する．手法は大きく３つの部分からなる．まず最初に，XML データからタグやキーワードの検出を高速に行うために Aho-Corasick 法を拡張した XML デー
タ走査器を用いる．次に，XML データから得られるパススキーマを用い質問式に対してパスプルーニングを行い，決定性有限オー
トマトン（以下，DFA）を構築する．最後に，この DFA を用いてXML データを処理することで検索結果を得る．
DFA を用いて XQuery を処理することによって，XML データの DOM 木への変換や，関係データベースへの格納などの必要がなく，少ない領域で手軽に XML データに対する検索・統計・変換処理を行うことができる．
XQuery 処理に関してはこれまでにも多くの手法が提案されている [3, 4, 10, 11, 12, 13]．これらの手法と比較すると，我々の手法は扱える XQuery が制限されながらも DFA を用いた単純で高速な手法であることが特徴である．
また，XQuery の一部であるパスの照合に関する XPath 処理を
非決定性有限オートマトン（以下，NFA）あるいはそれらから生成∗ 正会員 九州大学 大学評価情報室 ishino.uoc@mbox.nc.kyushu-u.ac.jp† 九州大学大学院システム情報科学研究院情報理学部門

takeda@i.kyushu-u.ac.jp‡ 科学技術振興機構 戦略的創造研究推進事業

1

注目しているある場所の前方や後方を調べる必要があるため，処理時間がパスの大きさに対して指数関数的に増大するケースがあることが知られている [6]．
また，条件式はパスは最後だけに現れるものとする．例えば，パス /dblp/www[year=”2001”]/title は，条件式がパスの途中に出現しており，パスの最後ではない．このパスは本質的に/dblp/www/tilte[../year=”2001”] と同じであり，先に述べた親軸に関する問題に帰着される．条件式中には，比較演算，算術演算，論理演
算および count や max などの統計関数を考える．最後に，FLOWR(for-let-order-where-return) 形式のうち基本となる for-return 文を扱う．入れ子になった for, return 中のパスは，外の for で指定されたパスの子軸あるいは子孫軸に制限される．
多くの NFA を用いた XPath 処理手法では，パスが検出されたことを NFA の状態を用いて表現している [8, 9, 18]．しかし，条件式の処理は単純な NFA では行えない．さらに統計関数や for 文を扱うためには，それ以上の情報をパスの検知と同時に保持せねばならない．

2.2 XML データ走査器によるストリーム処理
XML データを高速に走査し，タグの検出と同時に，与えられたキーワードのパターン照合も行いたい．このような目的のために，
タグ文字列（<name>や</email>など）やキーワードの検出のために，複数文字列照合アルゴリズムのひとつである Aho-Corasick
法 [1] を応用する．しかし，タグ文字列は，不定長の空白文字列を含んでいたり，属性に関する記述を含んでおり，単純な文字列ではない．また，当然ながらタグ名とキーワードは区別されなけ
ればならない．そのため，Aho-Corasick 法をそのまま適用することができない．
文献 [15, 17] において，著者らは，拡張語頭符号法のもとで表現された文字列に対しても，Aho-Corasick 法が拡張できることを示した．この手法を適用すれば，単一の XML データ走査器によって，キーワードとタグの検出を効率的に行うことができる．XML
データ走査器の状態数および構築時間は，いずれも入力である質問式のサイズに関して線形である．
XML データ走査器は字句解析とタグやキーワードの検出は同時に行う．それにも関わらず，XML データ走査器は SAX パーサと同等の速度で動作する．

2.3 NFA によるパスパターンの照合
XQuery の質問式は，パスによって示される部分に対する操作を記述したものといえる．一般に，XQuery によって処理の対象と日本データベース学会 Letters Vol 4, No.4

論文

DBSJ Letters Vol. 4, No. 4

なる部分はデータ全体のうち僅かな部分であり，それらの部分を 3.1 パススキーマ
見つけた後の処理をどうするかよりも，それらの部分をいかに高
パススキーマとは，ある XML データに含まれるすべてのパス
速に見つけるかということが重要である．つまり，パスを高速に の種類を表したものである．形式的には次のように定義される．
処理することが XQuery の処理の高速化に直接，結びつく．
最初にパス p1 [p2 ] をパスの基本形として考える．ここで，p1 , 定義 1 XML データ d に対するパススキーマ s とは，d 中のすべ
p2 は，いずれも条件式を含まないパスであるとする．このパスは ての根からのパスをただ一つだけ持ち，かつ，s 中のすべての根根からの経路が p1 である節点 x のうち，x からの経路が p2 とな からのパスは d 中に現れるもののことである．
る節点 y が存在する，そのような節点 x を指定している．このとパススキーマの定義はデータガイド [5] およびグラフスキーマ [2]き，パス p1 のことを親パスといい，パス p2 のことを子パスと呼を基にしている．データガイドやグラフスキーマは，グラフ構造
ぶことにする．また，質問式中のパスには//で表されるワイルド
カード文字が含まれることがある．そこで，質問式中のパスをパ によってデータベースにおけるデータの構造を示したものである．
それに対して，XML データは木構造をしており，パススキーマはスパターンと呼んで，//を含まない通常のパスと区別する．
XML
データ中に現れるすべてのパスの接頭辞木となる．
パスパターン p1 [p2 ] に対する NFA によるパスパターン照合器はパススキーマは質問処理に先立ってあらかじめ入力されたXML
次の 2 つの非決定性有限オートマトン (NFA) Np1,p2 , Np2R からな
る．Np1 をパスパターン p1 に対する NFA であり，Np2 を p2 に データを読み込むことによって構築される．パススキーマ構築に対する NFA であるとすると，Np1,p2 は Np1 と Np2 を ε 遷移で繋 かかる時間は入力 XML データのサイズに対して線形時間であり，入力が固定されれば構築は質問式によらず１度だけである．
いだものである．Np2R はパスパターン p2 の転置パターン pR
2 に
一般に，パススキーマは対象となっている XML データが「しっ対する NFA である．
あるタグの系列 T に対してパスパターン p1 [p2 ] に対応した かりとした」構造を持つほど元のデータサイズに比してずっと小Np1,p2 が受理状態となった場合は，T の先頭からあるタグ x まで さなものとなる．
がパス p1 に対応し，x から T の最後までが p2 となる対応が必ず 3.2 パスプルーニング存在する．しかし，そのような x は必ずしも一意には定まらない．
ここでは，パススキーマを用いることによってパス中の曖昧さ
また，T の先頭からタグ x までがパス p1 に対応したからといっ を解消し，その結果，ただ 1 つの DFA だけを用いてパスパターて，x 以降の T の系列が p2 に対応するとは限らない．このこと ンの照合を高速に処理する手法を提案する．
から Np2R が必要となっている．
まず，パススキーマを根から走査することによって，XML デー
例えば，a, b をタグ名とするとき，パスパターン a//b[a//b] を タが入力されたときと同様に，開始タグと終了タグの系列を得る
考える．パスパターン a//b[a//b] に対する NFA によるパスパター ことができる．例えば，次の出力をパススキーマから得たとする．
ン照合器を図 1 に示す．このとき，パスパターン a//b[a//b] とパ
ス abbaabab の対応を考えると，abb[aabab] と abbaab[ab] の２つ 1: START TAG: employeesが考えられる．また，親パス a//b に対して ab が対応するが，残り 2: START TAG: empの baabab に対して子パス a//b は対応しない．さらに接尾辞 abab 3: START TAG: nameに対して小パス a//b が対応するが，残りの接頭辞 abba に対して 4: END TAG:
name
親パス a//b は対応しない．
5: START TAG: email
6: END TAG:
email
N p1,p2 ,7: START TAG: ssn
8: END TAG:
ssn
N p2
N p1
9: END TAG:
emp
10: END TAG:
employees

合を行えばよい．例えば，パスパターン
れも条件式を含まないパス
合を行えばよい．例えば，パスパターン
は，いずれも条件式を含まないパス
は根からの経路がであというパスに対しては，タグの系列する．このパスは根からの経路がであ というパスに対しては，タグの系列合を行えばよい．例えば，パスパターン
スが行目が行目と 行目がの経路がとなる節点というパスに対しては，タグの系列が となる 行目と となるのうち， からの経路がとなる節点あ一致する．同様にというパスパターンに対し節点を指定している（図というパスパターンに対しる，そのような節点を指定している（図がとなる 行目と一致する．同様に行目が行目が一致する．特に重点のことを親パスといい，パては，ては，のとき，パスのことを親パスといい，パというパスパターンに対し 行目と 行目が一致する．特に重図 一致する．同様に 要なのは，開始タグに対応する行目と，行目と 行目と，よぶことにする．また，質要なのは，開始タグに対応することを子パスとよぶことにする．また，質ては，行目が一致する．特に重パ終了タグに対応する行目と 行目である．
されるワイルドカード文字
終了タグに対応する行目と 行目である．
パスにはで表されるワイルドカード文字
行目と行目と，
質 要なのは，開始タグに対応する
一般にパス中に含まれるタグ名に重複があり，かれを含まないパスと区別す
一般にパス中に含まれるタグ名に重複があり，かる．そこで，それを含まないパスと区別す
終了タグに対応する行目と行目である．
字
合を行えばよい．例えば，パスパターン
ないパスつ，パスパターンにワイルドカード文字が含まれるをパスパターンと呼ぶこと
つ，パスパターンにワイルドカード文字が含まれる
質問式中のパスをパスパターンと呼ぶこと
す であ 一般にパス 中に含まれるタグ名に重複があり，かというパスに対しては，タグの系列
とき，パスに対するパスパターンのマッチングが一とき，パス行目がに対するパスパターンのマッチングが一と つ，パスパターンにワイルドカード文字が含まれるがとなる 行目とる節点
意に定まらないことがある．例えば，をタグ名と をタグ名と意に定まらないことがある．例えば，に対するパスパターンのマッチングが一一致する．同様にというパスパターンに対しいる（図とき，パスするとき，パスとパスパターン
するとき，パスとパスパターンをタグ名と とては，行目が一致する．特に重いい，パ意に定まらないことがある．例えば，の対応を考えると．
の２の対応を考えると．
との２とパスパターン行目と要なのは，開始タグに対応する
行目と，また，質するとき，パスつが考えられる．
つが考えられる．
と 行目である．
の２
終了タグに対応するこのような対応を新たなタグが入力されるごとに，行目とード文字の対応を考えると．
このような対応を新たなタグが入力されるごとに，
一般にパス 中に含まれるタグ名に重複があり，かと区別すつが考えられる．
先頭から調べていたのでは効率が悪い．そこで，パ先頭から調べていたのでは効率が悪い．そこで，パ
つ，パスパターンにワイルドカード文字が含まれる呼ぶこと このような対応を新たなタグが入力されるごとに，
スパターンに対応したを構成し，基本的にはスパターンに対応したを構成し，基本的には先頭から調べていたのでは効率が悪い．そこで，パとき，パス に対するパスパターンのマッチングが一
タグが入力されるごとに状態を１つずつ遷移させる
タグが入力されるごとに状態を１つずつ遷移させる
ターン
図 スパターンに対応した
パスパターンを構成し，基本的には意に定まらないことがある．例えば，をタグ名とことで，効率よくパスとパスパターンの対応をとる
タグが入力されるごとに状態を１つずつ遷移させる
するとき，パス ことで，効率よくパスとパスパターンの対応をとるとパスパターン
ことを考える．なお，の構成に関しては文献の構成に関しては文献木を構築することなく，
うな節点を，
木を構築することなく，ことで，効率よくパスとパスパターンの対応をとるの対応を考えると．
とことを考える．なお，の２を参考にされたい．
を参考にされたい．
列を逐次処理することに
ム走査の出力系列を逐次処理することにことを考える．なお，
つが考えられる． の構成に関しては文献
く，
木の節点を巡回することを仮想的に木の節点を巡回することを パスパターン パスパターン
に対するパスパ に対するパスパ
このような対応を新たなタグが入力されるごとに，を参考にされたい．
にクを用意する．ストリーム
まず，空スタックを用意する．ストリーム
ターン照合機械は次のつのターン照合機械は次のつの かか先頭から調べていたのでは効率が悪い．そこで，パをパスパターンに対するパスパ検出されるたびに，そのタって開始タグが検出されるたびに，そのタらなる．
をパスパターンに対する であらなる．か をパスパターン
に対する であスパターンに対応した
ム ターン照合機械は次のつの を を構成し，基本的にはックにプッシュし，終了タグが検出される
し，終了タグが検出される
り，
を
に対する
であるとすると，り，に対するであるとすると，タグが入力されるごとに状態を１つずつ遷移させる
タ らなる． をパスパターン に対する であップする．このようにするとスタックの内ようにするとスタックの内と を 遷移で繋いだものである．
はと を は遷移で繋いだものである．
はは であるとすると，るり， ことで，効率よくパスとパスパターンの対応をとる
を に対する パスパターン
ら順にみていくと，根から現在いる節点まと，根から現在いる節点ま
パスパターンの転置パターンに対するの転置パターンに対することを考える．なお，の構成に関しては文献ことなく，
内 は と を 遷移で繋いだものである．
中の節点の系列となることが分かる．
となることが分かる．
である．これらつの とスタックを用いパスパを参考にされたい．
である．これらに対するつの はとスタックを用いパスパることにま
パスパターンの転置パターン
この出力をもとに
2.3 節で述べた NFA によるパスパターン照合， 節で上げたの出力例に対応したることをの出力例に対応しターン照合機械は次のように動作する．
スター
ターン照合機械は次のように動作する．
スター 器によるパスの照合を行い，各パスパターンに対するパスパ
NFA が終了状態となるパスを調である．これら
つのとスタックを用いパスパ
クの変化は次のようになる．
ようになる．
トタグが入力されたとき，現在のの状態をス //name というパスパターンに対して構成されトタグが入力されたとき，現在のの状態をス べ上げる．例えば，
トリーム
ターン照合機械は次のつの タックに積み，入力タグによって, N かし ターン照合機械は次のように動作する．
スター
を遷移させ
タックに積み，入力タグによってを遷移させ る NFA，そのタトタグが入力されたとき，現在のに上記の出力を与えると３行目で終了状態となる，すなわ
らなる． をパスパターン
に対する
であ
の状態をス
る．
エンドタグが入力されたとき，スタックにる．
エンドタグが入力されたとき，スタックにち，パスパターン//name に対してパス/employees/emp/name が対出されるタックに積み，入力タグによってり， を に対する であるとすると，を遷移させ応することが分かる．同様に，//emp[//email] というパスパターン
記録されている状態へと戻す．
の終了状
の終了状
ックの内る． はエンドタグが入力されたとき，スタックにと を 記録されている状態へと戻す．
遷移で繋いだものである． はに対して構成されるNFAに上記の出力を与えると
5 行目，すなわ態に達したとき，パスパターン照合機械はを態に達したとき，パスパターン照合機械はを ち/employees/emp/email で終了状態となる．このとき，親パスおよる節点ま記録されている状態へと戻す．
図 1. パスパターン
a//b[a//b] に対するパスパターン照合器．
パスパターンの転置パターン
に対するの終了状
見つけたことになる．このとき，親パスの場所
見つけたことになる．このとき，親パスの場所 び子パスの位置はそれぞれ/employees/emp と/employees/emp/email
る． 態に達したとき，パスパターン照合機械はである．これらつのFig. 1. A pathpattern とスタックを用いパスパ
matching machine
を for a//b[a//b].
を見つけるために，をスタックのタグを見つけるために，をスタックのタグに対応し見つけたことになる．このとき，親パス
ターン照合機械は次のように動作する．の場所スターであることが分かる．
のトップからボトム へとタグを順に入力する
のトップ
からボトム
へとタグを順に入力する
このようにして，すべての終了状態となるパスを調べ上げる．
トタグが入力されたとき，現在のの状態をスを見つけるために，をスタックのタグことで遷移させ，
で が受理状態となり，かそうして得られたパスは，質問式中のパスパターンとは異なり，ワことで遷移させ，でが受理状態となり，かタックに積み，入力タグによってを遷移させ
3.
パスプルーニングとDFAによるパスパターンのトップへとタグを順に入力する
つ，その次のタグ
が の受理状態であるとき，
イルドカード文字//あるいは*を持たないものとなる．このようにつ，その次のタグ
が の受理状態であるとき，る． からボトム
エンドタグが入力されたとき，スタックに照合ことで遷移させ，でが受理状態となり，かパススキーマを用いてワイルドカード文字を含むパスパターンを
そのタグの場所を出力する．
そのタグの場所を出力する．
記録されている状態へと戻す．
の終了状
つ，その次のタグ
がの受理状態であるとき，NFA によるパスパターン照合器は，質問式中に含まれる各パス
具体的なパスへと変換する操作をパスプルーニングと呼ぶことに態に達したとき，パスパターン照合機械はをに対するパスパター
に対するパスパター
パスパターン パスパターン
ごとに用意する必要があり，かつ，それらすべてを開始タグや終する．パスプルーニングされたパスに対しては，図 2 に示される
そのタグの場所を出力する．
見つけたことになる．このとき，親パスの場所
ン照合機械の出力は．
．
．である．
了タグが現れるたびに動作させる必要がある．結果，質問式中にように容易にDFA によるパスパターン照合器を構築することが．．である．
パスパターンン照合機械の出力は．
に対するパスパターを見つけるために，をスタックのタグ
現れるパスの数に比例して検索時間がかかることになる．
できる．
パスパターンについて考える．このとパスパターンについて考える．このとン照合機械の出力は．
．．である．
そこで，対象とする
XML
データからパススキーマを抽出し，そパスプルーニングを行った結果，XML データ走査器の出力に
のトップ
からボトム
へとタグを順に入力する
グの系列を文字列に見立ててパターン照き，およびは図1 のようになる．
列に見立ててパターン照
き，
および
は図
のようになる．
のパススキーマを用いて質問式中のすべてのパスに対してただ対してただ 1 つの DFA を遷移させるだけでパスパターンの照合ことで遷移させ，でが受理状態となり，かパスパターンについて考える．このとDFA を構成する手法を述べる．これにより，質問式中に現れが行えるようになる．
つ，その次のタグが照 き， つのおよびは図 の受理状態であるとき，のようになる．
るパスの数に検索時間が依存することはなく，またDFA のみを用
すべてのパスはパススキーマ上に現れることから，DFA は高々そのタグ の場所を出力する．
いるため高速な検索が可能となる．
パススキーマのサイズ程度の状態数となり，かつ，遷移に用いら
パスパターンに対するパスパター
2
日本データベース学会 Letters Vol 4, No.4
ン照合機械の出力は．．．である．
パスパターンについて考える．このとターン照 き，および は図 のようになる．
0

1

2

3

4

5

p2R

8

7

6

論文

DBSJ Letters Vol. 4, No. 4

パスを p/q ，子パスを r として考え，次に，親パスを p，子パスを q[r] として考える．

図 2. パスプルーニング．

Fig. 2. Path pruning.

np:

output(np ) if v(np , p/q[r]),nq:v(np , p/q[r]) := true if v(nq , p/q/r),

nr:v(nq , p/q/r) := true.

このように再帰的に処理を設定することによって，入れ子のパスも同様に扱うことができる．
関数 count は，p[count(q) > 1] のように用いられるが，このとき子パス q に対する子ノード p において親パス p に対する親ノー
ド np に保存された count(p) の値を 1 ずつ増加させ，親ノードでは保存された値を式の値とすることで処理される．すなわち，

np:

output(v(np , count(q)))

if v(np , count(q)) > 1,
れるタグの種類も入力データにもよるが一般にはその種類数は少
nq : v(np , count(q)) := v(np , count(q)) + 1.
ない．したがって，DFA の実装は単純な表参照を用いた実装でよく，非常に高速に動作が可能である．
代表的な関数として count を取り上げたが，その他の関数 sum,
また，子パスが対応した際に，Np2R を実行し，どこが親パス max, min, avg なども同様にして扱うことができる．
の位置であるかを調べていたが，パスプルーニングを行うことで， 最後に for 文 for $v in p return e は，式 e の値をパス p の予め親パスの位置を特定することができ，親パスの位置を探すと 親ノード n へと保存し，親ノードでは保存された値を式の値す
pいう必要もなくなる．
ることによって処理される．つまり，設定するべき処理は

4. XQuery 処理

np

前節で述べた DFA によるパスパターン照合器を用いると，質問式 p[q] に対して，親パス p と子パス p/q それぞれに対応するノー
ド np と nq を見つけることができる．それらのノードをそれぞれ親ノードと子ノードと呼ぶことにする．
単純な質問式 p[q] の場合は，子ノードが見つかった時点で親ノードを出力すればよい．この処理を形式的には次のように書くこととする．

np:

output(np ) if v(np , p/q),nq:v(np , p/q) := true.

:

output(v(p, e)).

となる．ここで，v(p, e) の値は，e 中の質問式によって設定される．
例えば，次の質問式を考える．

for $a in /dblp/*[year=”2005”]
return $a/title
ここで，p を/dblp/*，q を/dblp/*/year，r を/dblp/*/title とするとき，それらのノードに対して設定される処理は以下の通りとなる．

np:

output(v(np , e)) if v(np , p[year = ”2005”]),

nq : v(np , p[year = ”2005”]) := true
これは，子ノード nq においては，子パス p/q が存在するというこ
if nq = ”2005”,とを親ノード np に記録し，親ノード np においては，子パス p/q
nr : v(np , e) := nr .
が存在することが記録されていたならば親ノード np を出力するということを表している．
なお，親ノード np に設定された処理を行う際には，子ノード 5. 実装
nq に関する処理は終わっていなければならないため，処理は終了
上記の手法を実際に計算機上に実装を行い実験を行った．実験
タグの時点，すなわち帰りがけ順で行われる．
に用いた環境は 1.8GHz Pentium 4, メモリ 1GB, Gentoo Gnu/Linux
このように質問式に応じた処理を設定しておくことで，該当す
2.6.9, J2SE 1.4.2 である．
るパスが見つかった際に，設定された処理を順次，実行すること
本稿で述べた XQuery 処理手法を XMark ベンチマーク [14] をによって質問式に対する回答を得ることができる．同様にして，用いて評価する．XMark ベンチマークは XML 質問処理の性能を質問式に応じた処理を親ノードおよび子ノードに設定することで，評価するための XML データ生成ツールと 20 の質問式からなる．
他の XQuery の質問式に関しても処理が可能であることを示す．
我々の XQuery 処理手法では結合処理とソート処理について実装
質問式中で問題となるのはパスを持つ部分に関してのみである．
を行っていないため，それらの質問式については評価を行ってい
パス以外の部分については数や文字列は定数であり，算術演算，論ない．
理演算，比較演算のいずれの演算結果もその部分式の値によって
XMark ベンチマークの結果は図 3 に示した．100 MB の XML定まる値である．いずれもパスに関する値が求まれば質問式全体
データを例にとると，処理時間は 2.29 秒から 3.47 秒の間となった．
の値が定まる．
いくつかの商業的な XQuery プロセッサや XMLTK では，XML
例えば，論理演算を含むパス p[q and r] に対して，各パス p, q,
データをバイナリ形式に変換することによる実行時間の改善が行r に対するノード np , nq , nr での処理は次の通りとなる．
われている [4, 7]．本手法でも同様にタグ名などのバイナリ形式への変換も行った．また，実行時に DFA が失敗状態に入ったときを
np : output(np ) if v(np , p/q) ∧ v(np , p/r),
考える．このとき，Green ら [7] における NFA と同様に，本稿のnq : v(np , p/q) := true,
手法の DFA においても次の対応する終了タグが現れるまで XML
nr : v(np , p/r) := true.
データを読み飛ばして構わない．なぜなら，その時点まで失敗状
態から DFA が抜け出すことは決してないからである．そこで変パスパターンが入れ子になっている場合，例えば，p[q[r]] といっ換の際に，各開始タグごとに，開始タグから終了タグまでのオフ
た場合は，一番，内側の子パスから再帰的に処理を行う．まず，親3

日本データベース学会 Letters Vol 4, No.4

論文

DBSJ Letters Vol. 4, No. 4

セット値をあらかじめ書き込んでおく．バイナリ形式を用いた場
合は 0.11 秒から 1.03 秒となった．
いずれの場合も，本稿で述べた XQuery 処理手法は入力 XML
データのサイズに対して処理時間は線形に安定して増加していることが確認された．
10
Q1
Q1 (binary format)
Q6
Q6 (binary format)
Q7
Q7 (binary format)
Q13
Q13 (binary format)
Q14
Q14 (binary format)
Q15
Q15 (binary format)
Q16
Q16 (binary format)
Q17
Q17 (binary format)
Q20
Q20 (binary format)

8time (sec)64[6] Gottlob, G., Koch, C. and Pichler, R.: Efﬁcient Algorithms for
Processing XPath Queries, VLDB 2002, pp. 95–106 (2002).
[7] Green, T. J., Gupta, A., Miklau, G., Onizuka, M. and Suciu,
D.: Processing XML streams with deterministic automata andstream indexes, ACM Trans. Database Syst., Vol. 29, No. 4, pp.
752–788 (2004).
[8] Green, T. J., Miklau, G., Onizuka, M. and Suciu, D.: Processing XML Streams with Deterministic Automata, ICDT ’03: Proceedings of the 9th International Conference on Database Theory, Vol. LNCS 2572, pp. 173–189 (2003).
[9] Gupta, A. K. and Suciu, D.: Stream Processing of XPath Queries
with Predicates, Proc. SIGMOD, pp. 431–442 (2003).

2

0
0

50

100

150
input size (MB)

200

250

300

図 3. XMark ベンチマークの結果．

Fig. 3. The results of XMark benchmark queries.

6. まとめ
本稿では，パスプルーニングと決定性有限オートマトン (DFA)を用いて XQuery 質問式を処理する単純で効率の良い手法を提案
した．XML データの構造を縮約したパススキーマを用いたパス
プルーニングによって，質問式中のパスの曖昧さを解消し具体的なパスの集合へと変換することによって，パスパターンの照合がDFA を用いて可能となることを示した．さらに，その DFA の状態に適切な処理を割り当てることによって XQuery の検索・統計・
変換といった処理が行えることを示した．また，本稿の手法を実装し，実際の XML データを用いた実験を行い，本稿で述べた手法がどのような質問式に対しても，入力データのサイズに対して線形時間で出力が得られることをみた．
今後は，大量の質問式に対する同時処理といった大規模な問題に対する応用を考えている．また，同時に本稿では XQuery の部分族を扱うにとどまったが，より豊富な XQuery の取り扱いについても拡張を行っていきたい．

［文献］[1] Aho, A. V. and Corasick, M. J.: Efﬁcient String Matching: an
aid to Bibliographic Search, Commun. ACM, Vol. 18, No. 6, pp.
333–340 (1975).
[2] Buneman, P., Davidson, S. B., Fernandez, M. F. and Suciu, D.:
Adding Structure to Unstructured Data, ICDT ’97: Proceedingsof the 6th International Conference on Database Theory, pp.
336–350 (1997).
[3] Diao, Y. and Franklin, M.: Query Processing for High-Volume
XML Message Brokering, Proc. of the 29th VLDB Conference(2003).
[4] Florescu, D., Hillery, C., Kossmann, D., Lucas, P., Riccardi, F.,
Westmann, T., Carey, M. J. and Sundararajan, A.: The BEA
Streaming XQuery Processor, The VLDB Journal The International Journal on Very Large Data Bases, Vol. 13, No. 3, pp.
294–315 (2004).
[5] Goldman, R. and Widom, J.: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, VLDB

4

’97: Proceedings of the 23rd International Conference on Very
Large Data Bases, Morgan Kaufmann Publishers Inc., pp. 436–
445 (1997).

[10] Ives, Z. G., Halevy, A. Y. and Weld, D. S.: An XML QueryEngine for Network-Bound Data, The VLDB Journal The International Journal on Very Large Data Bases, Vol. 11, No. 4, pp.
380–402 (2002).
[11] Josifovski, V., Fontoura, M. and Barta, A.: Querying XML
streams, The VLDB Journal, Vol. 14, pp. 197–210 (2005).
[12] Koch, C., Scherzinger, S., Schweikardt, N. and Stegmaier, B.:
FluXQuery: An Optimizing XQuery Processor for Streaming
XML Data, Proceedings of the 30th VLDB Conference, pp.
1309–1312 (2004).
[13] Ludäscher, B., Mukhopadhyay, P. and Papakonstantinou, Y.: A
Transducer-Based XML Query Processor, Proceedings of the
28th VLDB Conference (2002).
[14] Schmidt, A., Waas, F., Kersten, M. L., Carey, M. J., Manolescu,
I. and Busse, R.: XMark: A Benchmark for XML Data Management, Proc. of the 28th VLDB conference, pp. 974–985 (2002).
[15] Takeda, M., Miyamoto, S., Kida, T., Shinohara, A., Fukamachi,
S., Shinohara, T. and Arikawa, S.: Processing Text Files as Is:
Pattern Matching Over Compressed Texts, Multi-Byte Character
Texts, and Semi-Structured Texts, SPIRE 2002, Vol. LNCS 2476,
pp. 170–186 (2002).
[16] W3C: XQuery 1.0: An XML Query Language, W3C Working
Draft (2004).
[17] 竹田正幸，石野 明，辻 寿嗣， 宮本：ストリーム指向の高速 XML データ処理技法について，データベースと Web 情報システムに関するシンポジウム (DBWeb2003) 予稿集 (2003).
[18] 森川裕章，浅井達哉，有村博紀：データストリーム処理のための効率良い XPath 問合せ機構，情報処理学会研究報告
DBS-131，Vol. 71, pp. 211–218 (2003).

石野明

Akira ISHINO

九州大学大学評価情報室助手．1999 北海道大学大学院工学研究科
電子情報工学専攻博士課程修了．博士（工学）．半構造データベース，自律型ロボットに関する研究と開発に従事．日本データベース学会会員．

竹田正幸

Masayuki TAKEDA

九州大学大学院システム情報科学研究院情報理学部門教授．科学
技術振興機構戦略的創造研究推進事業．1989 九州大学大学院総合理工学研究科情報システム学専攻修士課程修了．博士（工学）．系
列データの高速パターン照合処理，大規模系列データからの知識発見に関する研究と開発に従事．情報処理学会創立 40 周年記念論文賞，山下記念研究賞などを受賞．

日本データベース学会 Letters Vol 4, No.4