日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

XPath 問合せの Work Eﬃcient な分散並列評価
森畑 明昌

本稿では XML データに対する XPath 問合せの効率の良い分散並列評価について議論を行う．XPath 問合せは，
XML データの大きさを n，XPath 式の大きさを q として，逐次計算では O(nq) 時間で達成できることが知られている．これに対し，本稿ではまず，既存の 3 つの効率が理論的に保証されている分散・並列 XPath 問い合わせ手法の計算量を詳しく調べる．そして，述語・逆方向軸を含む XPath 式を処理する場合，そのいずれもが最悪時には少なくとも XPath 式の大きさ q の指数関数に比例する総仕事量・総通信量を要することを観察する．特に，Cong
ら（VLDB’06，SIGMOD’07，TODS’12）の「当該手法の仕事量・通信量は q に比例する」との主張に対しては反例を示す．次に，既存手法よりも多い O(q) 回の通信を許すことで，逐次の場合と同じ O(nq) の総仕事量・そして分割数を p として O(pq) の総通信量で分散並列 XPath 問合せを行うことができることを示す．これに加え，提案手法と既存手法との間の通信回数と仕事量のトレードオフについて議論を行い，オートマトンの立場からこのト
レードオフが理解できることを観察する．

持している．ユーザが問合せを行いたいのは，これら

1 はじめに多くのサイトからなる仮想的なデータベースであり，

本稿は XML データに対する XPath 問合せを分散・

この問合せの実現には分散処理が必須である．

並列計算機上で行う手法について議論する．このよう

本稿では主に分散並列問合せ手法の計算量の理論な手法は様々な理由から必要とされている．1 つ目は的な解析を行う．分散並列計算において重要な指標と効率である．現在集積されつつある巨大なデータは，

しては以下のものが挙げられる．

一台の計算機上でメインメモリに収めて処理すること

仕事量 仕事量とは，各プロセッサの行う処理の量はもはや不可能である．そのため，巨大なデータをいの合計である．仕事量はアルゴリズムの効率の

くつかに分割し複数の計算機を用いることなしには，もっとも基本的な見積りを与える．

効率の良い処理は達成できない．2 つ目は，現実には，

通信量 多くの環境では，プロセッサ間のデータ通

問合せを行いたいデータは 1 箇所にまとまって存在

信はデータの処理に比べはるかに大きなコストするわけではなく，既に分散されていることである．

を要する．そのため，通信量は仕事量に匹敵する

例えば，Web 上に存在するデータから，自分の欲し重要な指標である．

い商品の価格情報を検索することを考える．Web 上

通信回数 Web アプリケーション同士の通信など，には複数の価格情報サイトや通販サイトが存在する．

接続の確立等に時間がかかる場合，通信の回数は加えて，大手の価格情報サイトや通販サイトが，より大きなコストの要因となる．このような環境では

小さな，個別のサイトのポータルとしての役割も担っ

通信回数は通信量以上に大きな意味を持つ．

ている場合，詳細な情報はそれら個別のサイトが保以下，これらの指標を，XML データの大きさ n，その分割数 p，XPath 式の大きさ q, その中での述語のWork Eﬃcient Distributed XPath Querying.
Akimasa Morihata, 東 北 大 学 電 気 通 信 研 究 所, Research Institute of Electrical Communication, Tohoku University.

ネストの深さ d を用いて見積もる．
本 稿 で は「navigational XPath」[1] と 呼 ば れ る

XPath の部分集合を扱う（形式的な定義は 2. 2 節

表1XPath 問合せ手法の比較．○は計算量を悪化させずに利用できること，×はその拡張が非自明である
こと，EXP は取扱いに際して q の指数倍以上の仕事量・通信量の悪化を招くことを意味する．

逐次手法 [5] に基づく自明な方法

Suciu の手法 [12]

仕事量

通信量

通信回数

述語

逆方向軸

O(nq)

O(n)

O(1)

○

○

2

O(nq )

2

O(pq )

O(1)

×

○

2

2

松崎らの手法 [8, 9, 16]O(nq )O(pq )

O(d)

○

EXP

Cong らの手法 [2–4]O(nq2q )O(pq2q )

O(1)

○

EXP

提案手法

O(nq)

O(pq)

O(q)

○

○

で与える）．これは，XML 構造の中をノードの情報

かなか得られない．このように，漸近的な仕事量が増を見ながら移動し適切なノードを見つけるものであえることは，速度面では並列計算の恩恵を受けられなり，XPath の中核をなす．この範囲の問合せは，逐いことを意味する．

次アルゴリズムであれば，O(nq) の仕事量で達成で次に分散計算の観点から考える．例えば，ほとん

きることが知られている [5]．よって，XML データがどのケースでは仕事量が O(nq) だが，最悪は仕事量

分散配置されていたとしても，1 箇所にそのデータをO(n2q ) であるような状況を考える．この場合，特定集めて逐次処理することで，O(nq) の仕事量，O(n)の XPath 問合せでは，多大な処理時間や通信量を要の通信量，通信回数 O(1) 回の自明な分散アルゴリズ

し，場合によっては不可解なタイムアウトなどを生ムが得られる．ただし，巨大な XML データを 1 箇所

じ，しかも再試行では解決できない，という状況を生に集めるのは現実的であるとは言い難い．以上の状況をふまえ，本論文の目標は†1

む．このように，処理に要する時間の見積りを行うことができないという状況は，システムの頑健性を大き• 仕事量が O(nq) に近く，く損なうことになる．特に，XPath 問合せを他のシ• 通信量が XML データのサイズ n に依存せず，ステム中のコンポーネントなどとして用いる場合に• 通信回数ができる限り小さいはこの問題は深刻である．このように，分散計算ではアルゴリズムを与えることである．

「多くの例では高速である」ことは救いにならないた

本稿では特に良い仕事量を持つことを保証することに特に重点をおいて議論をする．これは，並列計算，分散計算両方の観点から非常に重要である．

め，再悪時での仕事量が小さいことが保証されていることは非常に重要である．
仕事量・通信量・通信回数の観点から良い性質を持

まず，並列計算の観点から言えば，仕事量の悪化

つと主張している XPath 問合せアルゴリズムは既には，相当数のプロセッサが利用できない限りは速度いくつか存在する [2–4, 8, 9, 12, 16]．本稿では，まず，向上が期待できないことを意味する．例えば，O(nq)これら手法の計算量を詳細に検討する（3 節）．具体的

2

時間で逐次計算できる処理を仕事量 O(nq ) の並列には，Suciu の手法 [12] および松崎らの手法 [8, 9, 16]

アルゴリズムで処理する場合，負荷分散が理想的に行については，XPath 式の大きさの計算量への影響をえるとしても，漸近的には q に比例する程度のプロ解析する．さらに，Cong らの手法 [2–4] に対しては，

セッサがあってはじめて逐次処理に匹敵する効率とな

彼らの「仕事量は O(nq)，通信量は O(pq)」というる．そのため，負荷分散や通信にもコストがかかるこ主張に対し反例を示す．

とを考えると，現実的にはまともな並列速度向上はな

以上の結果をまとめたものが表 1 である．見ての通†1 これらの要件のうち前 2 者は Cong ら [2–4] が与えたものに等しい．Cong らはこれに加え，通信回数が定数回であることを要求している．また，Suciu [12]は第 2 の要件と通信回数が定数回であることを効率的な分散評価の要件としている．

り，既存手法の仕事量は全て逐次計算の O(nq) に比べはっきり大きい．それどころか，これらの手法は，述語と逆方向軸の両方を用いる場合，XPath 式の大きさ q に対して少なくとも指数関数的に大きな仕事

量・通信量を要する．これは，いくら XPath 式が通常 XML データに比べかなり小さく，また指数的な仕2 XML と XPath クエリ

事量の爆発がレアケースであったとしても，やはり深2. 1 XML とその分割刻な問題であるといわざるを得ない．

本稿では，XML を以下のようにグラフ構造として以上の背景をふまえ，本稿では XPath 問合せの新モデル化する．XML はグラフ G = (V, E) であり，

しい分散並列評価手法を与える（4 節）．この手法は，

ここで V は頂点集合，E ⊆ V × V は辺集合である．

仕事量 O(nq)，通信量 O(pq)，通信回数 O(q) で，述さらに，辺集合 E が以下の性質を満たすことを仮定

語・逆方向軸を含む XPath 式による問合せを達成すする．

る．見ての通り，提案手法は通信回数が既存手法に比• E = E⇑ ] E⇓ ] E⇒ ] E⇐ ．

べて多いものの，仕事量および通信量は既存手法に• R ∈ {E⇑ , E⇓ , E⇒ , E⇐ } について，(v, w) ∈ R

比べ小さい．特に，仕事量は漸近的に逐次アルゴリズ

ならば (w, v) ∈ R．ただし E⇑ = E⇓ ，E⇓ = E⇑ ，ムと同等である．また，述語・逆方向軸ともに計算量を悪化させることなく利用できる．さらに，提案手法
は既存手法に比べてもシンプルであり，実装も容易である．
本稿ではさらに，通信回数と仕事量のトレードオフの観点から提案手法を既存手法を比較する．表 1 かE⇒ = E⇐ ，E⇐ = E⇒ ．
• R ∈ {E⇑ , E⇒ , E⇐ } について，(v, w) ∈ R かつ(v, w0 ) ∈ R ならば w = w0 ．
• ある r ∈ V が ∀(r, w) ∈ E : (r, w) ∈ E⇓ かつ∀v ∈ V \ {r} : ∃(v, w) ∈ E⇑ を満たす．この時 rをこの XML のルートと呼ぶ．

ら，松崎らの手法は，Cong らの手法に比べ，O(d)• (v, w) ∈ E⇓ かつ (v, w0 ) ∈ E⇓ ならば，またそ回の通信を行うことで仕事量や通信量を削減したもの時に限り，(w, w0 ) ∈ TC (E⇒ ) ∪ TC (E⇐ )．たの，また Suciu の手法から，O(d) 回の通信を行うこ

だし TC (R) は R の反射推移閉包である．

とで述語の取り扱いを可能にしたものではないか，とそれそれの規則は「各辺は親，子，直上の兄，直下のいう仮説が成り立つ．本稿では，このように，通信弟のいずれかを表す」「すべての辺は対応する逆向き

回数，すなわち計算ステップ数を増やすことで，各スの辺を持つ」「各頂点の親，直上の兄，直下の弟は唯テップの計算に用いるオートマトンの大きさを小さ

一」「親・兄弟を持たない唯一の頂点 (ルート) を除き，くし，仕事量を減らすことができることを指摘する．

すべての頂点は親を持つ」「兄弟関係は親子関係からこのことをふまえると，松崎らの手法を上述の観点

自然に定まる」ことを意味している．よって，XMLから理解でき，さらに提案手法が大きさ O(1) のオーが木構造をなすことを仮定していることになる．

トマトンのみを用いる手法と理解できることを示す．

なお，後の議論，特に XPath 式の意味の理解を容このことは，実際に計算機環境や行う処理に適したア

易にするためグラフ構造を用いて XML をモデル化

ルゴリズムを選ぶ際に一つの指針たりえる．

したが，多くの場面で XML を根付き木構造とみなし

本稿の構成は以下のとおりである．まず 2 節で，本研究で取り扱う XML データ及びその分散配置の状て説明を行う．そのため，「部分木」などの表現を断りなく用いる．

況，そして本研究で取り扱う XPath 式について述べ

分散評価を議論するためには，XML の分割を定める．3 節では，上記 3 種類の先行研究について，そのる必要がある．本稿では以下のかたちで定まる分割を

計算量を解析する．4 節では新しい XPath 問合せア

考える．XML (V, E) に対する分割とは頂点の部分集

ルゴリズムを提案し，その計算量を調べる．5 節では，合 D ⊆ V である．この時，D の各要素を分割点と呼以上見てきた 4 つの手法を比較し，その差異が通信

ぶ．説明の単純のため，ルートは必ず分割点であると回数と仕事量のトレードオフの観点から理解できる

する．XML (V, E) および分割 D に対し，d ∈ D をことを述べる．6 節で本論文のまとめを述べ，今後の根とするセグメントとは，d の子を含み，E で連結し課題を議論する．

分割点を含まない極大な V の部分集合に d を加えた

もののことである．
上記定義によると，1 つのセグメントは，ある分割点または XML のルートをルートとし（これをセグメ(v, v) |=X(v, m) |=X q1(m, w) |=X q2(v, w) |=X q1 /q2

ントのルートと呼ぶ），葉または分割点（これをセグ(v, m) |=X p(v, v) |=X [p]メントの葉をなす分割点と呼ぶ）を末端とする部分木のような構造をなす．以下の議論では，計算量の解析を簡単にするため，1 つのセグメントの葉をなす分割点の個数は O(1) 個であるとする．
以下，各セグメントがそれぞれ唯一のプロセッサに(v, w) ∈ ER
R ∈ {⇓, ⇑, ⇒, ⇐}(v, w) |=(V,E) R(v, w) ∈ TC (ER )R ∈ {⇓, ⇑, ⇒, ⇐}(v, w) |=(V,E) R∗
AP (v)(v, v) |=(V,E) AP

割り当てられているとする．すなわち，プロセッサ数
はセグメント数に一致する．

2. 2 XPath 式
本稿で取り扱う XPath 式を以下に示す．

(v, w) |=X p1(v, w) |=X p2(v, w) |=X p1 ∧ p2
(v, w) |=X pi
i ∈ {1, 2}(v, w) |=X p1 ∨ p2

query ::= step/query |step::= axis | [pred ] | APaxis::= ⇓ | ⇑ | ⇒ | ⇐|pred(v, w) 6|=X p(v, w) |=X ¬p
図1

XPath 問合せの推論規則⇓∗ | ⇑∗ | ⇒∗ | ⇐∗::= ¬pred | pred ∧ pred | pred ∨ pred

表現できるものが多い．例えば，following::a は|⇑∗/⇒/⇒∗/⇓∗/local-name() = a と表現できる．こquery

ここで，AP は頂点に対し真偽値を返す原始述語を表の言語では，木をノードのラベルを確認しながら縦横すメタ変数である．例えば，当該頂点のラベルが l でに走査することが可能である一方，それ以外の情報，あることを確認する local-name() = l は典型的な原例えば 2 つの頂点が一致するかどうかなど，を用い始述語である．なお，計算量の評価のため，原始述語ることはできない．

は通信なしに O(1) 時間で評価できるとする．[pred ]

以下，読みやすさのため，XPath で標準的な略記の形式の XPath 式を「述語」と呼ぶ．また，axis の法を用いる．/l は ⇓ ∗ /local-name() = l を，//l は各要素を「軸」と呼ぶ．特に，⇑・⇑∗・⇐・⇐∗ を「逆⇓ ∗ /local-name() = l をそれぞれ表す．

方向軸」と呼ぶ．

XML データ X に対する XPath 式 q での問合せとは，X のルートを r として，3 既存の結果
本節では，3 つの既存手法についてその計算量を(r, w) |=X q

解析する．具体的には 3. 1 節では Sucui [12] の手法，

なるすべての頂点 w を求めることである．ここで，

3. 2 節では松崎ら [8, 9, 16] の手法，そして 3. 3 節で(v, w) |=X q は「X 中に頂点 v から頂点 w までのあは，Cong ら [2–4] の手法について述べる．

る経路が存在し，それが式 q を満たす」ことを表す．

|= の推論規則を図 1 に示す．

以下では，入力を XML データ G = (V, E)，分割点集合 D，および XPath 式 p とする．

こ の 言 語 は navigational XPath [1] と 呼 ば れ る

XPath 式 に ほ ぼ 自 明 に 対 応 す る ．例 え ば ，⇓ は

3. 1 正規パスによる問合せ

child::*に，⇓∗ は descendant-or-self::*に，⇑∗

3. 1. 1 概要

は ancestor-or-self::*に，それぞれ対応する．直以下 Sucui [12] の手法の概要を説明する．

接 の 対 応 を 持 た な い も の も ，こ の 言 語 で 簡 単 に彼の手法では，グラフ構造をなす半構造データベー

スを扱っている．また，問合せは非決定有限状態オー

トが達成しうる状態遷移の要約を求めておく点にあ

トマトン（NFA）で行う．これは XPath 問合せそのる．これにより，各セグメントに実際に到達する状態

物ではない．しかし，我々も XML をグラフ構造と解を簡単に求めることが出来る．

釈するので，データベースの表現については問題が

3. 1. 2 計算量ない．また，少なくとも述語を含まない XPath 式に

Suciu は，クエリの大きさ q を定数とみなせば，ア

関しては，これを正規言語の問合せと理解するのはルゴリズム 1 は XML データの大きさ n に比例する

簡単である．各軸はそれぞれ，対応する辺にマッチす

仕事量，データの分割数 p に比例する通信量，定数る正規表現と理解する．例えば ⇒ は E⇒ に属する辺回の通信で問合せを達成できると述べている．以下ににマッチし，⇓∗ は E⇓ に属する辺の 0 回以上の繰りより詳細な解析を与える．

返しにマッチする．また，全ての頂点は，その頂点でステップ (1) は単純な処理であり，O(q) 時間の逐ラベル付けられた自分自身への辺を持つとし，この次処理で達成できる．これにより，状態数が O(q) の辺を「頂点ラベルの辺」と呼ぶ．原始述語は，それがNFA が得られる．

真となる頂点ラベルの辺にマッチする．p1 /p2 は正規表現としての p1 と p2 の連接と解釈する．以上より，XPath は XML 上のある経路，即ち辺列に対してマッステップ (2) には，1 回，O(q) の量の通信が必要である．
ステップ (3) は各セグメントに対して分散処理される．セグメント Vi について，各分割点・各状態

チする正規表現，ひいては NFA と解釈できる．
それでは問合せアルゴリズムを示す．以下，各セグに対し，O(|Vi |q) 時間でこの分割点・状態からの遷

メント Vi について，このルートを ri ，この葉をなす移を計算できる．よって，セグメント Vi の処理に

分割点集合を Di ，Ei = E ∪ (Vi × (Vi ∪ Di )) とする．

は合計 O((|Di | + 1)|Vi |q2 ) 時間を要する．この結果

手続き 1.

得られる Ri の大きさは O((|Di | + 1)2 q2 ) である．

点 v1 を状態 s1 で出発したとき辺集合 E 0 のみ

|Di | ∈ O(1) であることをふまえると，全体での仕事
P
量は O( i |Vi |q2 ) = O(nq2 ) である．
P
ステップ (4) には，1 回の，O( i (|Di | + 1)2 q2 ) =を用いて頂点 v2 に状態 s2 で到達しうることを，O(pq2 ) 量の通信が必要である．これにより得られる(v1 , s1 ) ;E 0 (v2 , s2 ) と書くことにする．

グラフの大きさも O(pq2 ) である．

1. p を NFA に変換する．この NFA の初期状態
を i，終了状態の集合を F ，またこの NFA が頂ステップ (5) には O(pq2 ) 時間を要する．到達可能

2. 得られた NFA を各プロセッサに送る．
3. 各 セ グ メ ン ト Vi に 対 し ，{ri } ∪ Di 間 で
あ り 得 る NFA の 状 態 遷 移 を 全 て 計 算 す
る ．す な わ ち ，Ti= {((v1 , s1 ), (v2 , s2 )) |(v1 , s1 ) ;Ei (v2 , s2 ), {v1 , v2 } ⊆ {r} ∪ Di } を求める．

4. 各 Ti を 1 プロセッサに集める．
S∗∗
5.
i Ti を辺集合とするグラフに対し，(r , i)（rは G のルート）から到達可能な頂点集合 V 0 をな状態は，各分割点に対して O(q) である．
ステップ (6) には 1 回の，O(pq) 量の通信で十分である．
ステップ (7) の処理に要する時間はステップ (3) と同P様であり，全体での仕事量は O( i (|Di |+1)|Vi |q2 ) =O(nq2 ) である．
以上をまとめる．総仕事量は O(nq2 ) である．通信
回数は 3 回，総通信量は O(pq2 ) である．

3. 1. 3 特長と問題点求める
06. V を各プロセッサへ分配する．

Suciu の手法の特徴的な点は，グラフに対する NFA|による処理という定式化を用いることで，逆方向軸をv ∈ Vi , v ∈ V , s ∈ F, v ;Ei (v, s)} を求める．
S
i Ri がクエリの結果である．

含む XPath 問合せを問題なく扱えている点である．

手法の要点は，各セグメントに対し，そのセグメンダであり，悪くはない．しかしそれでも，逐次の場

7. 各 セ グ メ ン ト Vi に 対 し ．Ri
0

0

=

{v

0

またその計算量は，q に対し指数ではなく多項式オー合の計算量 O(nq) に比べ，仕事量が漸近的に q 倍になっており，仕事量の観点から効率が良いとは言い難い．

Suciu の手法と同様である．
この手法は，いくつかの技術的な差異，および NFAではなく NFTA を使う点を除いて，Suciu の手法とSuciu の手法の最大の欠点は述語を扱えないことで良く似ている．特に，並列スケルトンを用いて実現しある．この欠点は，述語部分もまとめて一つの NFAている処理は，まさしく Suciu の手法と着想を共有にすることができれば解消すると思われる．しかしそしている．Suciu の手法との大きな差異は，rare アルの手法は自明ではない．かつ，後に 5. 3 節で議論す

ゴリズムを用いて逆方向軸を取り除いている点，そしるが，たとえこれが可能であったとしても，再悪時にて述語を深いものから順に処理することで間接的には状態数の指数以上の爆発は避けられないことを証取り扱っている点である．

明できる．そのため Suciu の手法をベースにして直3. 2. 2 計算量

接述語も扱えるよう拡張するのは現実的ではない．

松崎らは明示的には計算量を与えていない．しかし，各並列木スケルトンの処理は O(1) 回・O(p) 量3. 2 並列木スケルトンを用いた問合せの通信と n に比例する仕事量で実現できることが分

3. 2. 1 概要

かっているため，並列木スケルトンの組み合わせで

松崎ら [8, 9, 16] は並列木スケルトン [11] を用いた

XPath 問合せを実現したこと自体がある種の計算量

XPath 問合せ手法を提案している．

の保証になっている．よって，アルゴリズム全体とし

手続き 2.

て，この手法が，n に比例する仕事量，pd に比例す

1. p に rare アルゴリズム [10] を適用し，逆方向軸を含まない XPath 式 p0 へ書き換える．
02. 以下のステップを p から述語がなくなるまで繰
り返す．

(a) p0 述語のもっとも深いネストに対応する

る通信量，d に比例する通信回数で実現できることは見て取れる．ただし，この見積りは XPath 式の大きさの計算量への影響を加味していない．
実際，この手法の計算量は得られる p0 の大きさに依存する．以下これを m とする．最悪では O(2q ) のXPath 式をすべて取り出し，これらを（ボトものが得られうる [10] ことが知られている．

ムアップ）非決定性有限状態木オートマトン

ステップ (1) の仕事量は O(m) である．

（NFTA）に変換する．変換は簡単である．

ステップ (2) は述語のネストの深さ O(d) 回繰り替(b) uAcc ス ケ ル ト ン を 用 い て ，各 頂 点 がえされる．1 回あたり，Suciu の手法と同様，取り扱

NFTA のどの状態に遷移するかを計算し，われる XPath の部分式の大きさの合計を k として，

この結果を各頂点に加える．具体的な実装はSuciu のものに非常に似たものになる．すな

総仕事量 (nk 2 )・通信回数 3 回・総通信量 O(pk 2 ) である．†2わち，各セグメントに対し，起こしうる遷移

ステップ (3) の計算量も Suciu の手法と同様であの要約を計算し，それを併合し実際に分割点り，取り扱われる XPath の部分式の大きさの合計をに到達しうる遷移を求め，再度各セグメントk として，総仕事量 (nk2 )・通信回数 3 回・総通信量を走査する．

O(pk2 ) である．

(c) p0 中のこのステップで処理された述語を，以上をまとめる．各ステップで取り扱われる XPath「NFTA がその頂点で終了状態に達したかど

部分式の大きさ k の合計が m であることに注意する

うか」を調べる原始述語に置換する．

と，総仕事量は (nm2 )・通信回数は O(d) 回，総通信

3. p0 を（トップダウン）NFTA に変換する．
4. dAcc スケルトンを用いて，各頂点が NFTA のどの状態に遷移するかを計算し，終了状態となりうるものをクエリの解とする．詳細はやはり†2 松崎らの論文中 [8, 9] では行列乗算による実装が示されているが，これをそのまま用いると総仕事量は(nk3 ) になる．しかし，Sucui の手法と同様の実装をすることで，これを上記の計算量に改善することができる．

量は O(pm2 ) である．

ためには，他のセグメントがこの条件を満たせば必3. 2. 3 特徴と問題点

要十分である」という問合せを導出することに対応

この手法の特徴的な点は，述語のネストを逐次的にする．

扱うことで，これをオートマトンにコンパイルした際

以下に Cong らのアルゴリズムの概略を示す．なお，の状態数の爆発を回避していることである．通信回

彼らは逆方向軸を含まない XPath 式を考えている．

数は O(d) に悪化しているが，多くの場合，述語がそ

手続き 3.

れほど深くネストすることはないと想像できるため，
この点はそれほど大きな欠点ではない．
この手法のもっとも大きな問題点は，rare アルゴ

1. p から各部分式を取り出し，部分式の結果からより大きな式の結果を得る形式へと正規化する．
これを p0 とする．

リズムによるクエリの大きさの爆発である．rare ア

2. p0 を各プロセッサに分配する．

ルゴリズムはクエリの大きさを指数的に大きくする可3. p0 に対し当該セグメントの情報をボトムアップ

能性があるため，最悪計算量は総仕事量は (n(2q )2 )，に部分評価し，そのセグメントが各部分式を満た

q 2

総通信量は O(p(2 ) ) となる．

すためには，分割点以降の部分木がどのような条件を満たせば良いかを導出する．

3. 3 部分評価による XPath 問合せ

4. 部分評価結果を 1 つのプロセッサに集める．

3. 3. 1 概要

5. 集められた部分評価結果を分割の構造に従ってCong ら [2–4] は分散 XML データに対する部分評

合成し，XPath クエリの各部分式それぞれに対価 [6] に基づく XPath 問合せ手法を提案した．以下

し，一つの大きな論理式を得る．この論理式を評

では，議論を簡単にするため，「問合せの結果にルー

価し，根が XPath クエリのどの部分式を満たす

トが含まれるかどうかを判定する」というより簡単なかを調べる．このとき，p 全体を満たせば問合せ問題を考える．これは彼らの初期の論文 [2] で議論さ結果は真，そうでなければ偽である．

れたものである．

3. 3. 2 部分評価結果の大きさ

Cong らの手法の概略は以下のとおりである．まず，Cong らのアルゴリズムの計算量を見積もるために

XPath 式からまずすべての部分式を取り出す．そしは，部分評価結果がどのようなものであるか，すなわて，XPath 式を，部分式の結果からより大きな式のち，部分評価によってどのような論理式が得られるか結果を求める 3 番地コードのようなプログラムとしが問題となる．Cong らは，各部分式に対する部分評て解釈する．このプログラムに対し，各プロセッサは

価結果の大きさは，そのセグメントの葉をなす分割点

自分の XML セグメントを部分評価する．すなわち，の数を k として O(k) であると述べている．しかし，そのセグメントを「静的な入力」，他のセグメントのこの洞察は間違っている．

情報を「動的な入力」として，静的な入力を含まない

いま，//a/[b ∨ //c1 ]/[b ∨ //c2 ]/ · · · /[b ∨ //cm ] とプログラムを導出するのである．最後にこの情報を集いう XPath 式を考える．ラベルが a であり，その子

約することで最終的な結果を得る．

が b1 ，孫が b2 ，と続き bm にたどり着く頂点に対し例として問合せ q1 = //a//b を考える．これをまて，この頂点が a/[b ∨ //c1 ]/[b ∨ //c2 ]/ · · · /[b ∨ //cm ]ず，部分クエリを取り出し，q1 = //a/q2 ，q2 = //bを満たすかどうかは，各 //ci に対応する部分クエリと分解する．次に，これを当該セグメントに対し部分評価する．このセグメントがある分割点までの経路上が分割点で成り立つことを表す変数を xi として，
V{xi | bi 6= b} となる．となる（ただし a，b，bi ，各に a を含むが b を含まない場合，その分割点以降でci は互いに相異なるとする）．すなわち，a 以下の子

q1 および q2 が成り立つことを変数 xq1 および xq2 で孫方向のラベルの列で，b でない頂点に対応する変数表すとして，q2 = xq2 ，q1 = xq1 ∨ xq2 を得る．これの論理積となる．よって，当該セグメントが子孫方向は直感的には「この部分木がこの問合せにマッチする

へ一列に伸びる木であり，a から始まり子孫方向に bを任意に含む経路を持つ場合，_ ^xi
I∈S i∈I

3. 3. 4 問題点
Cong らの手法の大きな問題点はその計算量である．

という形式の任意の論理式を生成することができる．

最悪では，逆方向軸を含まない XPath 式に対してでこ の 形 式 の 論 理 式 は 各 xi を 入 力 と す る 単 調 なあっても，q に対して指数以上の仕事量・通信量を要

Boolean 関数と同値である．m 変数の単調な Boolean

する．もちろん，BDD を用いているのだから，現実√/ m) 種類ある [7]．よって，これらすべ√てを表現するためには，少なくとも Θ(2m / m) ビッ

的には指数的な爆発が起こることはまれであろう．しト必要である．この事実は，Cong らの洞察に対するは明らかである．また，BDD のような複雑なデータ

明示的な反例となる．

構造を用いる必要があることが，このアルゴリズムの3. 3. 3 計算量

コストを定数倍とはいえ確実に遅くしている点も見以上見てきたように，部分評価結果は極めて大き

逃せない．

m

関数は Θ(22かし，少なくないコストを払わなければならないことな式となりうる．このことは新たな問題を生む．すな

さらに，逆方向軸を用いた XPath への対処方法がわち，部分評価結果を少ないコストで小さな式へと提示されていない点も問題である．クエリの大きさ

単純化できなければ，計算量は上の観察よりもさらの増加に目をつぶれば，rare アルゴリズムにより逆に悪化する．逆に言えば，単純化をも含めて議論し方向軸を扱うことは可能である．しかし，この手法がなければ，正確な計算量評価はできない．一つの現

XPath 式のサイズに対しては大きなコストを払う必

実的な解は二分決定図（BDD）を用いることであろ要があることを考えると，これは現実的であるとは考う．BDD であれば，m 変数の任意の Boolean 関数

えにくい．

m

を O(2 ) の空間で表現でき，また単純化を含む多くの基本的な操作をその大きさに比例する時間で実現できる．以下この実装の計算量について議論する．
ステップ (1) は O(q) 時間で実現できる．

4 Work Eﬃcient な XPath 問合せ
以上見てきたように，既存の XPath 問合せアルゴ
リズムで，仕事量の観点から十分に効率の良いものはステップ (2) は 1 回・O(q) の量の通信で実現できる．

存在しない．ここでは，既存手法より多い O(q) 回のステップ (3) は，当該セグメントの大きさを ni ，通信を許すことで，仕事量の良いアルゴリズムを与え

こ の セ グ メ ン ト の 葉 を な す 分 割 点 の 数 を ki と することができることを示す．

る と ，各 頂 点・各 部 分 式 あ た り O(2ki q ) の 大 き さの BDD を操作する必要があるので，計算時間はO(ni q2ki q ) = O(ni q2q ) である．
qステップ (4) は O(pq2 ) 量の通信 1 回で実現できる．
ステップ (5) は O(pq2q ) 時間で達成できる．
P
以上から，このアルゴリズムは O( i ni q2q ) =O(nq2q ) の仕事量，O(1) 回・O(pq2q ) 量の通信で実現できる．なお，以上は XPath 問合せそのものを議論したわけではないが，まったく同じ漸近計算量で4. 1 問合せアルゴリズム
それでは提案手法を示す．まずは簡単のため述語を含まない場合を考える．また，以下では直感的な理解のため，分割を意識せずアルゴリズムを記述する．分
割を加味した詳細なアルゴリズムは補題 1 で述べる．
手続き 4 (述語のない場合).

1. W = {r} とする．ここで r は XML のルートである．

2. p が空の場合，W を問合せの結果としアルゴリ

XPath 問合せを実現することができる．詳細は [3, 4]

ズムを終了する．そうでなければ，p = step/p0

を参照せよ．

であるから，step について場合分けを行う．

(a) step = R（ただし R ∈ {⇓, ⇑, ⇒, ⇐}）の場合，W 0 = {v | v 0 ∈ W, (v 0 , v) ∈ ER } とする．

(b) step = R∗（ただし R ∈ {⇓, ⇑, ⇒, ⇐}）の0

0

0場合，W = {v | v ∈ W, (v , v) ∈ TC (ER )}とする．

それでは，手続き 4 と手続き 5 を用いる XPath 問
合せが良い計算量をもつことを示す．

(c) step が AP の 場 合 ，W 0

=

{v

|

v ∈ W, AP (v)} とする．
0

4. 2 計算量補題 1. 手続き 4 および手続き 5 のステップ (2) は，

1. 仕事量 O(n)03. p := p ，W := W とし，ステップ (2) に戻る．

2. 通信量 O(p)3. 通信回数 O(1) 回

手続き 4 はほぼ XPath 式をその意味どおり評価するだけの単純なアルゴリズムである．各ステップでは，それまでの XPath 式でルートから到達可能な頂点にマークをつけている．

Proof. 手続き 4 について示す．手続き 5 の場合も同様である．以下，W および W 0 は各セグメントに分割して保持されているものとする．特に，セグメント述語がある場合には，松崎らの手法と同様，「述語を満たす頂点に，そうだと分かる頂点ラベルを加え，その述語をラベルの確認に置換する」という手法をとる．以下述語の取扱いを示す．
手続き 5 (述語の取扱い). もっとも内側の述語から順に以下の手続きを繰り返し，述語をすべて取り除
く．以下，注目している述語を p とする．

Vi に対し Wi = W ∩ Vi とする．
step の内容により場合分けを行う．
(2-a) まず，各セグメント Vi について，Wi0 ={v | v 0 ∈ Wi , (v, v 0 ) ∈ ER } と す る ．さ ら に ，S
Wi0 = Ŵi0 \ Vi ，W 0 = i Wi とする．最後に，各セグメント Vi について，Wi := (W̌ 0 ∪ Ŵi0 ) ∩ Viとすればよい．

1. q := p，W := V とする．
2. q が空の場合，W 中の頂点についてのみ真とな
る新たな原始述語 AP p を用意し，クエリ中の [p]を AP p に置換し，次の述語の取扱いに移る．そうでなければ，q = q 0 /step であるから，step について場合分けを行う．

(a) step = R（ただし R ∈ {⇓, ⇑, ⇒, ⇐}）の場合，W 0 = {v | v 0 ∈ W, (v 0 , v) ∈ ER } とする．

(b) step = R∗（ただし R ∈ {⇓, ⇑, ⇒, ⇐}）の場合，W 0 = {v | v 0 ∈ W, (v 0 , v) ∈ TC (ER )}とする．

(c) step が AP の 場 合 ，W 0

で行うことができる．

=

{v

|

v ∈ W, AP (v)} とする．
3. q := q 0 ，W := W 0 とし，ステップ (2) に戻る．
手続き 5 は手続き 4 に非常に良く似ている．相違点は，XPath 式を逆向きに確認することで，条件を満たす経路の終点ではなく始点にマークをつける点

このアルゴリズムの正しさは自明である．このP時，仕事量は明らかに O(|W |+ i |Wi0 |) ⊆ O(n)である．W 0 を各プロセッサが知るには，2 回，O(p) 量の通信で充分である．
(2-b) まず，各セグメント Vi について，Wi0 ={v | v ∈ D, v 0 ∈ Wi , (v, v 0 ) ∈ T C(ER )} ∩ D を
S
求め，W 0 = i Wi とする．次に，W 0 = {v |v ∈ D, v 0 ∈ Wi , (v, v 0 ) ∈ T C(ER )} を求める．最後に，各セグメント Vi について，Wi := {v |v ∈ Vi , v 0 ∈ W 0 ∪ Wi , (v, v 0 ) ∈ T C(ER )} とすればよい．
このアルゴリズムでは，まず更新後の Wi に含まれる分割点集合を W 0 を求め，それを用いて各セグメントで新しい Wi を求めている．
P
仕事量は明らかに O(|W | + i |Wi0 |) ⊆ O(n) である．また，W 0 を各プロセッサが知るには，2回，O(p) 量の通信で充分である．

(2-c) この場合は容易である．仕事量は O(|W |)，通信は不要である．

である．
定理 1. XPath 問合せは

1. 仕事量 O(nq)2. 通信量 O(pq)は //[step/AP W ] を，それぞれ実行し，得られた頂

3. 通信回数 O(q) 回点集合を新しい W とすればよい．このことにより，で達成できる．

Proof. 手続き 5 により述語をすべて除去し，しかる
後に手続き 4 を適用すれば良い．この処理のほとんど
は，q 回繰り替えされるステップ (2) であるが，補題

1 に示されているとおり，この部分は要請された計算量で実現できる．また，それ以外の処理は明らかに，O(n + q) の仕事量，O(1) 回・O(q) 量の通信で十分である．

4. 3 特徴
提案手法の特徴は，まず何よりその仕事量 O(nq)である．これは既知の逐次アルゴリズムの仕事量と一致している．この観点から，提案手法は work eﬃcientであると言える．また，提案手法は並列速度向上も期待できる．各セグメントが O(n/p) の大きさであれば，提案手法は明らかに O(nq/p + pq) 時間で問合せを達成できる．この計算量は，現実的な量のプ√
ロセッサ，形式的には p ∈ O( n) の条件の下では，O(nq/p) に一致する．すなわち，理論上は，逐次ア
ルゴリズムに比べ，漸近的にプロセッサ数に比例する
速度向上が得られる．
一方，通信回数は O(q) であり既存手法に比べ明らかに多い．そのため，通信の確立に非常に時間のかかる環境や，また XML データがそれほど大きくない場
合には，この手法はそれほど有効ではないと予想さ

既存の実装を使い回すことができ，実装がより容易になる．さらに，既存の XML データベースでの効率の良い実装を利用することはパフォーマンスの観点からも大きなメリットである．実際，XML データは多くの場合そもそも XML データベースに格納されているだろう．この場合，データをデータベースから読み出し独自の手続きを行うことはあまり現実的とはいえない．

5 各手法の比較
以上，4 つの手法について，その計算量を議論してきた．本節では，これら手法を，通信回数と仕事量のトレードオフの観点から比較する．
議論にあたっては，BSP（Bulk Synchronous Par-

allel）モデル [13] に似たモデルを採用する．具体的には，「有限状態オートマトン†3 によるセグメントの処理と大域通信」を 1 つのステップとし，このステップの繰り返しで問合せを実現することを考える．これは Sucui や松崎らの手法をベースとしている．これにより，通信回数と仕事量のトレードオフを，抽象的に，しかも明示的に議論することができる．通信
回数はステップ数として明示的に現れている．また，

Sucui や松崎らの手法に現れているように，オートマ
トンの状態数が仕事量の見積りを与える．なお，通信量は，通信回数・状態数両方に依存する．

れる．
提案手法のもう一つの特徴は，その単純さである．
提案手法は，概念的には XPath 式をほとんどその意
味通り実行するだけである．そのため，分割点付近の取扱いを除けば，その正しさはほぼ自明に見てとれる．また分割点付近の取扱いもそれほど複雑ではない．
この単純さは実用的な価値も持つ．ステップ (2)は，通信の部分を除けば，既存の XML データベースに対する XPath 問合せで実現できる．すなわち，W中の頂点にのみ真となる原始述語を AP W とすると，
手続き 4 の場合は //AP W /step を，手続き 5 の場合

5. 1 Sucui の手法の解析
Sucui の手法は我々の観点からほぼ自明に理解できる．すなわち，Sucui は XPath 式が述語を含まなければ，その問合せは O(q) の有限状態オートマトンを用いて O(1) ステップで実現できることを述べていることになる．
また，Sucui の手法を述語を含む式に拡張する際の困難も，この観点から理解できる．述語は正規表現の†3 ただし，具体的にどのようなオートマトンを使うかは考慮しない．経路に関する文字列オートマトンを想像するのがおよそ適切であるが，詳細は分割方法などに依存する．

立場からは先読みと理解することができる．文字列に対しては，大きさ n の先読み付き正規表現を大きさ
n

5. 3 Cong らの手法の解析
Cong らの手法は明示的には有限状態オートマトン

O(22 ) の決定的有限状態オートマトンに変換できるを扱っていない．しかし，部分評価の過程で現れる論ことが知られている [15]．木構造では「子供のどれ理式を有限状態オートマトンの状態の表現とみなすこかがこの条件を満たす」という先読みであるため，文とで，この手法を我々の観点から理解することができ

字列向けの手法をそのまま適用できるかどうかは自る．なお，この論理式は，各分割点について XPath

明でない．しかし，利用できたとしても，述語を含め式の各部分式が成り立つか否かを表す変数を入力と1 つの有限状態オートマトンに変換すると，少なくとする真偽値関数を表現するものであった．よって，こも指数的に多くの状態数を要することは間違いなさ

れら真偽値関数は XPath 式が定まればたかだか有限そうである．この点は 5. 3 節でさらに議論する．

種類しか存在しない．そのため，Cong らの手法で現れる「状態」はやはり有限である．また，ここで扱っ

5. 2 松崎らの手法の解析ているのは決定的有限状態オートマトンである．な

松崎さの手法は，XPath 式が逆方向軸を含まなけ

ぜなら，ある真偽値関数に対応する状態 (論理式) かれば，その問合せは O(q) の有限状態オートマトンをら，ある頂点を訪問した際，結果として現れる真偽値

用いて O(d) ステップで実現できることを述べている関数は唯一に定まるからである．

ことになる．

実際，3. 3. 2 節の議論はこの観点に基づいている．

これは，Sucui の手法と比較すると，オートマトン

有限状態オートマトンの観点からは，3. 3. 2 節での議を分割することで，仕事量を減らし通信回数を増やし論は，述語を持つが逆方向軸を持たない大きさ O(q)ている，と理解できる．積構成などに典型的に現れるの XPath 式で，それに対応する決定的有限状態オー

が，状態数 m および n の 2 つの有限状態オートマト

トマトンの状態数が漸近的に q の 2 重指数となるもンによって表現される言語は，往々にして状態数 mnのが存在することを示していることになる．よって，のオートマトンで表現できる．逆に大きな有限状態

この結果は Cong らの手法だけでなく，Sucui の手法

オートマトンを複数の小さな有限状態オートマトンにも同様に成り立つ．そのため，この結果は，Sucuiの組合せに分解することができるならば，通信回数をの手法であっても，述語をもつ XPath 式に対しては犠牲にすることで XPath 問合せの仕事量を減らすこ

指数的な効率の悪化を避けられないことも同時に示とができる．実際，松崎らの手法では，述語のネストしている．

ごとにオートマトンを作ることで仕事量の爆発を避けている．

以上の観点からは，Cong らの手法は，Sucui の手法や松崎らの手法の良く似た変種である．なお，技術

なお，松崎らの手法は，逆方向軸を扱う場合には的には，部分評価を用いることで有限状態オートマト

状態数の指数爆発を起こしうる．しかし，Suciu の結ンを陽に構築しないことは大きな差異となっている．

果から考える限り，逆方向軸の取扱いは，本質的には

この点は，有限状態オートマトンの状態数は莫大であ状態数の爆発は招かないはずだと思われる．そのたるが現実的な入力に対してはそのほとんどを使わな

め，Suciu の手法と松崎らの手法を組み合わせることいような XPath 式に対しては，大きなパフォーマン

で，逆方向軸も述語も扱うことができ，また指数爆発

ス上の利点となる可能性がある．

も起こさない手法も与えることができると予想できる．すなわち，述語はネストの深い順に逐次的に処理

5. 4 提案手法の解析

し，また述語を含まない XPath 式の取扱いは基本的

提案手法は，既存手法に比べ，有限状態オートマトに Sucui の手法にしたがえば良い．このアプローチ

ンの分割による仕事量の削減を徹底的に行ったものとの可能性については今後の課題である．

見ることができる．すなわち，XPath 中の各 step それぞれから状態数 O(1) のオートマトンを構築している．このことが，work eﬃcient な XPath 問合せをには比較不能であり，また実用上の有用性についても今つながっている．

後の議論が必要である．

提案手法中で用いられる有限状態オートマトンは，状態数が高々2 程度の非常に小さなものであり，その6 まとめと今後の課題

ため有限状態オートマトンをほとんど意識すること

本稿では，いくつかの分散 XPath 問合せ手法につなく理解・実装することができる．この点は提案手法

いて議論を行い，既存手法が逐次アルゴリズムに比べの大きな特徴である．しかし，有限状態オートマトン

仕事量の観点から効率が悪いこと，特に述語と逆方の観点を持つことで，より通信回数の少ない実装も向軸の両方を含む場合には最悪で指数以上の計算量考えることができる．すなわち，状態数がそれほどの悪化を招くことを示した．さらに，新しいシンプル

大きくならない程度の XPath 断片をまとめて一つのな分散 XPath 問合せ手法を提案し，この手法が逐次有限状態オートマトンへと変換すれば，その分仕事

アルゴリズムに匹敵する仕事量を持つことを示した．

量は増えるものの通信回数を削減できる．XML デー

加えて，これらアルゴリズム間の関係は，有限状態機

タの分散や処理基盤となる計算機の特性にもよるが，械による複数ステップからなる分散処理だと理解でき

実用的な観点からは，松崎らの手法と同様，述語のネること，また提案手法は，有限状態オートマトンを小ストを一塊として扱うのが現実的な選択ではないか，

さなものの組み合わせへと分解することで，通信回数と予想している．

を犠牲に仕事量を改善したものだと理解できること

なお，提案手法は，任意の正規表現による問合せをを観察した．

扱うことはできない．XPath 式では，閉包演算子やこれらの議論は，いずれも，理論的にはそれほど

選言演算子を任意に用いることができない．そのた

驚くべき結果ではない．多くの洞察は個々の論文のめ，問合せの結合は本質的には連接 q1 /q2 のみであ中で，どの程度明示的であったかはともかく，述べらる．この場合，現在注目している頂点から q1 /q2 で到れ，また用いられてきたものである．また，提案アル達可能な頂点を知るには，この頂点から q1 で到達可

ゴリズムもほぼ自明なものである．しかし，これら能な頂点を知り，その結果から q2 で到達可能な頂点を明示的に述べ，各手法の関係を明かにすることは，を知れば良い．よって，より小さなオートマトンによ今後実用的な分散 XPath 問合せ手法を与える上でのる処理に分割できる．しかし，例えば閉包 q∗ では，

基礎として意義があるだろうと期待している．特に，

現在注目している頂点から q で到達可能な頂点を知

既存手法からも見て取れるように，各セグメントをあるだけでは，q∗ で到達可能な頂点を知ることはでき

る種の有限状態オートマトンで処理し，その遷移をない．よって，一般にはより小さなオートマトンの組

そのセグメントの要約として用いることで分散計算

み合わせへと分割するのは困難である．

を実現するアプローチは，少しずつかたちを変えて逆に，正規表現の部分集合に対してであれば，同過去何度も再発見されている．これが「再発見」であ様のアプローチで work eﬃcient な正規表現マッチンることを議論し，そしてその着想がさらに効率の良グを達成できる．すなわち，先読みや後読みはあるいアルゴリズムにつながりうることをを示すことは，ものの，閉包や選言は制限されたかたち，例えば.*

本稿の大きな目的の一つであった．

や [a-zA-Z]*のようなかたちでしか現れないような

今後の大きな課題としては，実装及び実用的な問

正規表現に対してであれば，O(nq/p + pq) 時間での合せに対する効率の確認が挙げられる．少なくない

正規表現マッチングが可能である．この手法は，正規

XPath 問合せは述語や逆方向軸を含まないと思われ表現に対する前処理がほとんど必要ないこと，また正る．また，もしそれらを含んだとしても，多く場合は

規表現の大きさに対する指数爆発を生まないことな計算量の指数爆発を起こさないと思われる．そのたど，既存手法 [14, 17] と比較してもいくつかの長所をめ，理論上はさておき，実用上どの手法が高速である

もつ．ただし，計算量の観点からは既存手法との得失かは明らかではない．この点の調査は今後の課題である．また，本論文では XPath 式の部分集合しか扱っていない．より広意範囲の XPath 式を効率よく分散
並列評価できるかどうかも興味深い課題である．さらに，XPath 式は多くの場合て XML 変換の一部として利用される．例えば，XPath 問合せの結果を，単なる概念上の頂点集合としてではなく，一つの XMLとしてユーザに提示したい場合が少なくない．よって，XPath 式を含む XML 変換の分散評価も実用上有用な課題として残っている．
謝辞 本研究は日本学術振興会学術研究助成基金助成金（若手研究 (B) 24700019）の助成を受けている．

参 考 文 献[ 1 ] Benedikt, M. and Koch, C.: XPath leashed,
ACM Comput. Surv., Vol. 41, No. 1(2008), pp. 3:1–
3:54.
[ 2 ] Buneman, P., Cong, G., Fan, W., and Kementsietsidis, A.: Using Partial Evaluation in Distributed
Query Evaluation, Proceedings of the 32nd International Conference on Very Large Data Bases, 2006,
ACM, 2006, pp. 211–222.
[ 3 ] Cong, G., Fan, W., and Kementsietsidis, A.:
Distributed query evaluation with performance
guarantees, Proceedings of the ACM SIGMOD International Conference on Management of Data,
2007, ACM, 2007, pp. 509–520.
[ 4 ] Cong, G., Fan, W., Kementsietsidis, A., Li, J.,
and Liu, X.: Partial Evaluation for Distributed
XPath Query Processing and Beyond, ACM Trans.
Database Syst., Vol. 37, No. 4 (2012), pp. 32:1–
32:43.
[ 5 ] Gottlob, G., Koch, C., and Pichler, R.: Efﬁcient algorithms for processing XPath queries,
ACM Trans. Database Syst., Vol. 30, No. 2 (2005),
pp. 444–491.
[ 6 ] Jones, N. D.: An Introduction to Partial
Evaluation, ACM Computing Surveys, Vol. 28,

No. 3(1996), pp. 480–503.
[ 7 ] Kahn, J.: Entropy, Independent Sets, and Antichains: A New Approach to Dedekind’s Problem,
Proceedings of the American Mathematical Society,Vol. 130, No. 2 (2001), pp. 371–378.
[ 8 ] Matsuzaki, K.: Parallel Programming with Tree
Skeletons, PhD Thesis, Graduate School of Information Science and Technology, The University ofTokyo, 2007.
[ 9 ] Matsuzaki, K., Hu, Z., and Takeichi, M.: Towards automatic parallelization of tree reductions
in dynamic programming, SPAA 2006: Proceedingsof the 18th Annual ACM Symposium on Parallel
Algorithms and Architectures, 2006, ACM, 2006,
pp. 39–48.
[10] Olteanu, D., Meuss, H., Furche, T., andBry, F.: XPath: Looking Forward, XML-Based
Data Management and Multimedia Engineering EDBT 2002 Workshops, EDBT 2002 Workshops
XMLDM, MDDE, and YRWS, 2002, Revised Papers, Lecture Notes in Computer Science, Vol. 2490,
Springer, 2002, pp. 109–127.
[11] Skillicorn, D. B.:
Parallel Implementationof Tree Skeletons, J. Parallel Distrib. Comput.,Vol. 39, No. 2 (1996), pp. 115–125.
[12] Suciu, D.: Distributed query evaluation on
semistructured data, ACM Trans. Database Syst.,
Vol. 27, No. 1 (2002), pp. 1–62.
[13] Valiant, L. G.: A Bridging Model for Parallel Computation, Commun. ACM, Vol. 33, No. 8(1990), pp. 103–111.
[14] 松崎公紀, 江本健斗, 劉雨: 正規表現マッチングの並列化とその Hadoop による評価, 情報処理学会論文誌
プログラミング, Vol. 4, No. 4 (2011), pp. 1–11.
[15] 森畑明昌: 先読み付き正規表現の有限状態オート
マトンへの変換, コンピュータソフトウェア, Vol. 29,
No. 1 (2012), pp. 147–158.
[16] 野村芳明, 江本健斗, 松崎公紀, 胡振江, 武市正人:
木スケルトンによる XPath クエリの並列化とその評
価, コンピュータソフトウェア, Vol. 24, No. 3 (2004),
pp. 51–62.
[17] 新屋良磨, 光成滋生, 佐々政孝: 並列化と実行時コード生成を用いた正規表現マッチングの提案, コンピュー
タソフトウェア, (2013). 採録决定済.