DEIM Forum 2017 I2-1

木分割アルゴリズムを用いた XSLT 処理手法
ZHU

YATING†鈴木 伸崇††† 筑波大学 大学院図書館情報メディア研究科 〒 305-8550 茨城県つくば市春日 1-2†† 筑波大学 図書館情報メディア系 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †s1521655@u.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし

本稿では，XSLT のサブセットである木変換機を対象に，効率の良い変換手法を提案する．本手法では，

DTD を用いて XML データを分割すべき箇所を求め，そこで変換処理を切り分けることで，XML データの変換処理を並列化し，処理効率の向上を図る．XML データと比較すると，DTD は十分に小さく，短時間で分割位置を決定できるという利点がある．提案手法の有効性を評価するため，変換規則数が異なる 4 つの木変換機を用いて評価実験を行った．その結果，提案手法を用いた場合，変換処理を並列化しない場合と比べて処理時間を短縮できることを示した．
キーワード

木分割，XML，XSLT

1. は じ め にXML [7](Extensible Markup Language) は Web のデータ形
式における事実上の標準として広く用いられている．ここで，ある程度まとまった量の XML データを管理・蓄積する場合を考える．このような場合，DTD(Document Type Definition) 等

提案アルゴリズムを Java を用いて実装し，評価実験を行った．その結果，本アルゴリズムを用いた場合，並列化しない処
理手法を用いた場合と比較して，処理効率の向上が認められる結果が得られた．

関連研究のスキーマ言語を用いて格納すべきデータの構造を前もって定

本稿に最も関連が強いのは，Rajesh らの研究 [4] である．こ義しておき，それに対して妥当なデータを作成・利用するのが一の研究は，データ分割，クエリ分割，ハイブリッド分割という般的である．データを蓄積・保存する場合，XML は非常に有用

XML データや XPath 式を分割する 3 つの分割実行戦略に基な言語であるが，ユーザに提示する際には HTML(HyperText

づいた，並列化アルゴリズムを提案している．しかし，これら

Markup Language) など他の形式に変換した方が都合がよいのアルゴリズムでは，データの分割位置や XPath 式の分割位

ことが多い．このような変換を行うための変換用言語として，

置を決定するために大量の統計情報を収集する必要がある．しXSLT [8](XML Stylesheet Language Transformations) がよ

たがって，分割位置決定処理の負荷が大きいという問題がある．

く使われている．

また，これらのデータが更新された場合，大量の統計情報を再

ここで，XML データに対して XSLT を用いて変換処理を行計算する必要がある．その他，文献 [3] では，木の各ノードに重うことを考える．近年，サイズの大きな XML データが急速に増みをつけ，木の分割数が最小となるように分割をする木分割線

加しており，そのようなデータに対する変換処理の効率が悪化

形時間アルゴリズムを提案している．文献 [2] では，分散 XMLするという問題が生じている．これまで，サイズの大きい XMLに対する XSLT 実行手法を提案している．これは，分割されてデータの処理に関しては，XPath (XML Path Language) のいる XML データを並列に変換するものである．

実行手法 [4] については研究されているが，XSLT の実行手法

本稿の構成は以下の通りである．2 章では，XML，DTD，に関する研究は行われていない．近年，XML データのサイズ

XSLT，木変換機に関する定義を行う．3 章では，本研究で提案が増加する一方で，計算機プロセッサの性能は大幅に向上してする木分割アルゴリズムについて説明する．4 章では，評価実いる．このため，この状況に応じた効率の良い XSLT 変換手法

験について述べる．5 章では，まとめと今後の課題を述べる．

の重要性が増大している．Java などのプログラミング言語自体
は複数スレッドの生成・実行に対応しているが，XSLT 処理系

2. 諸 定 義

で複数スレッドの実行を考慮して処理効率の向上を図ったもの

本章では，XML，DTD 及び XSLT に関する諸定義を行う．

は著者の知る限り存在しない．

2. 1 XML について

そこで本稿では，並列化によって XSLT 変換をより高速に

2. 1. 1 XML の概要

行うための手法を提案する．より具体的には，DTD を用いてXML とは，文書やデータの意味や構造を記述するためのマー

XML データを分割すべき箇所を求め，そこで変換処理を切りクアップ言語の一つであり，近年，様々なデータの記述フォー

分けることで，XML データの変換処理を並列化し，処理効率のマットとして急速に普及している．マークアップ言語とは「タ向上を図る手法を提案する．XML データと比較すると，DTDグ」という特別な文字列によって文書の一部を囲う，木構造をは十分に小さく，短時間で分割位置を決定できるという利点がした言語であり，文書の意味や構造を記述することができる．

ある．

また，XML は HTML や TEX とは異なり，ユーザが作成する

独自のタグによって，データの意味や構造を表すことができ

2. 2 DTD の概要

る．このため，XML 自身には特定のデータ構造（タグやそのDTD は，XML データの文書構造を定義するスキーマ言語

階層関係）が規定されておらず，ユーザによって様々な構造のである．DTD を用いてデータ構造を定義することによって，

XML データが生成される．しかし，大量の XML データを管XML データの利用における処理の正確性や安全性を向上させ理するために，XML データの構造を統一することが必要な場

ることが可能となる．DTD を用いて定義できるのは，XML合がある．そこで，スキーマ言語を用いて XML データの構造

データ内に記述できる要素やその出現順序，出現回数，要素がを定義し，その定義に従って XML データを生成することによ持つ属性，属性の型などである．ただし，本稿では要素のみをり，XML データの構造を統一する．このスキーマ言語の定義考慮し，属性は扱わないものとする．また，XML データの文書に従って生成された XML データを妥当な XML データと呼ぶ．

構造を定義できるスキーマ言語として，DTD のほか RELAX

本稿では妥当な XML データを対象とする．XML データの例

NG や XML Schema などがあるが，本稿は DTD のみを対象

を図 1 に示す．

とする．DTD の例を図 2 に示す．

<item><books><book><titile>吾輩は猫である</title><author>夏目漱石</author></book></books></item><!ELEMENT item (books)><!ELEMENT books (book+)><!ELEMENT book (title,subtitle?,author*)><!ELEMENT title (#PCDATA)><!ELEMENT subtitle(#PCDATA)><!ELEMENT author (#PCDATA)>

図 1: XML データの例

図 2: DTD の例

図 1 に示した XML データは，ルートの子要素が item，item

2. 3 XSLT についての子要素が books，books の子要素が book，book の子要素が2. 3. 1 XSLT の概要

title，author である XML データを表している．

XSLT [8] は W3C により標準化された，XML 文書を他の文

2. 1. 2 木と生け垣の定義

書に変換 (transform) する変換用言語である．ここでの変換とXML に関係の深い，木 (tree) 及び生け垣 (hedge) について

は，XML 文書の構造，マークアップ，内容を変更して他の形定義する [6]．

態の文書にすることである．XSLT 処理系は入力として 2 つのノード名（ラベル）の有限集合を Σ とする．Σ で構成された

もの，変換処理の規則を記述した XSLT スタイルシートと入力

木 (Σ-tree) を TΣ と表す．ノード σ ∈ Σ が子として木 w ∈ TΣ木と呼ばれる変換元となる文書を必要とする．そして，XSLTを持つとき，σ(w) と表すことができ，σ(w) も TΣ に属する木

処理系は入力木に XSLT スタイルシートに従って変換を行ってである．上記のように TΣ は Σ 上の文字列及び括弧を表す記文書である出力木を出力する．XSLT スタイルシートはテンプ

号’(’ と’)’ で表現される．本稿では単なる木と表記した場合はレートと呼ばれる単位で変換の規則を記述していく．

全て，ノード名の有限集合 Σ で構成された木 (Σ-tree) のこと

テンプレートに最低限必要な要素は，そのテンプレートがどを指す．生け垣は木の有限の並び (sequence) である．生け垣ののノードに適用するかを決定する match 属性と，変換の際の集合 HΣ は TΣ∗ として定義される. またノード v のノード名を動作モードを指定する mode 属性，そして変換の規則や出力木

label(v) と表し，ノード v の重みを weight(v) と表す．

に出力される要素や文字データが記述される処理内容である．

生け垣 h ∈ HΣ に対して，h を構成するノード集合 Dom(h)は以下のように定義される:•

h = ϵ のとき Dom(h) = ∅ ；•h = t1 ···tn であり, ti ∈ TΣ のとき Dom(h) =が指定できる．mode 属性については省略が可能であるが，省∪ni=1 {iu |u ∈ Dom(ti )}；•match 属性には XPath 式のサブセットである XSLT パターンh = σ(w) のとき Dom(h) = {ϵ} ∪ Dom(w) ．

略された場合には mode 属性がないモードとして処理が行われていく．処理内容には XSLT が標準で用意している関数や命令が使用できるほか，ユーザ自身が定義した関数も使用できる．

2. 3. 2 下降型木変換機の定義

以上の定義により，ルートノードを持つ XML データは木XSLT の基盤をなす下降型木変換機について定義する [6]．

で，ルートノードを持たない XML（部分）データは生け垣で以下，下降型木変換機を単に木変換機と呼ぶ．簡単のため，表すことができる．また本節以降， t, t1 , t2 , · · · は木を表し，ノード名及び変数は全てアルファベット 1 字で表記する．またh, h1 , h2 , · · · は生け垣を表す．また h = t1 · · · tn と表記されてHΣ (Q)(TΣ (Q)) で表される生け垣 (木) は Q に含まれる要素でいた場合，全ての ti は木である．

ラベルされた葉ノードを持つことが可能である．
木変換機は 4 次組 (Q, Σ, q0 , R) で表させる．ここで，•Q は木変換機の状態を示す変数の有限集合，

•Σ は入力及び出力で使用するノード名，•

q0 ∈ Q は木変換機の初期状態，•

R は (q, a) → c(q1 , q2 , …, qn ) の形をした遷移規則の有1.

<?xml version=“1.0”?>2.

限集合．ただし，q1 , q2 , …, qn ∈ Q，a, c ∈ Σ<xsl:stylesheet
xmlns=“http://www.w3.org/1999/XSL/Transform”

である．

version=“1.0”>

T r = (Q, Σ, q0 , R) で定義される木変換機による，状態 q でqの木 t に対する変換は T r (t) として表記され，以下のように再帰的に定義される．

3.
4.
5.

<xsl:template match=“/ ”><xsl:apply-templates mode =“p” />6.

</xsl:template>•t = ϵ のとき，T rq (t) := ϵ である．

7.

•

t = a(t1 · · · tn ) かつ，a(q, a) → h ∈ R が存在するとき，

8.

T rq (t) は h 内の p ∈ Q でラベルされた全てのノード u を生け

9.
10.

<d>
<e/>

11.
12.

</d>
</xsl:template>

13.
14.
15.
16.

<xsl:template match=“a” mode =“q”><c/><xsl:apply-templates mode =“q” />17.

</xsl:template>

18.
19.
20.

<xsl:template match=“b” mode =“p”><c>

垣 T r (t1 ) · ··T r (tn ) に置き換えにることによって得られる．
pp

そのような Q に含まれるアルファベットでラベルされたノード

u は葉ノードにのみ現れる．それゆえ h は下方向にのみ拡張さ
れていく．

•

(q, a) → h ∈ R となる規則が存在しないとき，T r (t) :=qϵ となる．
最後に，T r による t の変換を単に T r(t) と記述した場合，それは初期状態による変換 T rq0 (t) を意味する．

2. 4 制限された XSLTXSLT を木変換機の機能に制限した場合，XSLT テンプレー
トは以下の様に制限される．

•

match 属性に指定できる XSLT バターンは単一のノード名に限定される•処理内容に記述できる関数及び命令は apply-templates

命令に限定される•処理内容に出力される要素の記述は認めるが文字データの記述は認めない2.3.2 節で例として挙げた木変換機 Tr を XSLT スタイルシー
トを表すと図 3 の様になる．

T r の各規則が 1 つのテンプレートに対応している．例え<xsl:template match=“a” mode =“p”>

21.
22.
23.
24.
25.

<xsl:apply-templates mode =“p”><xsl:apply-templates mode =“p”></c></xsl:template>

26.
27.
28.
29.

<xsl:template match=“b” mode =“q”><d><xsl:apply-templates mode =“q” />
</d>

30.
31.

</xsl:template></xsl:stylesheet>

図 3: 木変換機 T r の XSLT スタイルシートによる表現

ば，変換規則 (q, a) → cq の左辺の q は 14∼17 行目のテンプ
レートでの mode 属性に，a は match 属性にあたる．また変が存在することがある．たとえば，図 4 に示す DTD において，

換規則右辺での c ∈ Σ は要素 c にあたり，q ∈ Q は 16 行目のノード item は子孫ノード book を持ち，ノード book は子ノー‘<xsl:apply-templates mode="q"/>’ というノードに対応す

ド item を持っている．これをグラフで表現すると，図 5 に示る．T r での初期状態 p ∈ Q に相当するものとして，ルートノー

すように，ノード item とノード book の間にループがある．しドに appley-templates 命令を適用するテンプレートが 4∼6 行

かし，DTD の木分割処理を行うためには，DTD をループを含目に存在している．

まない木に変換することが必要である．そこで，後述の DTD

3. 提 案 手 法
本章では，木分割アルゴリズムを用いた XSLT 実行手法について述べる．

を木に変換するアルゴリズムにおいては，もしあるノードの祖
先ノード集合の中にそのノードのラベルと同じのノードがあれば，そのノードを削除する．DTD の木分割処理では，DTD を木に変換するアルゴリズムで作成された木に対して，各ノード

3. 1 提案手法の概要に重みを付与する．*や+が付されたノードは XML データにお本手法は，主に DTD に関する処理と変換処理の 2 つの処理

いて出現回数が多い可能性があるため，そのようなノードの重に分けられる．3.1.1 節と 3.1.2 節で詳しく説明する．

みは大きくする．逆に，?や | が付されたノードは XML データ

3. 1. 1 DTD に関する処理において出現回数が少ない可能性があるため，そのようなノーDTD に関する処理は，DTD を木に変換する処理と DTD のドの重みは小さくする．木を分割する際に，数値 k を設定し，木分割処理の 2 つの処理に分けられる．まず，DTD を木に変分割されたそれぞれの部分木の重みが k 以下という条件の下換する処理を説明する．DTD では異なる内容モデルが同じラで，分割数が最小となるように分割する．

ベルを含む場合があるため，グラフで表現した場合に，ループ

DTD を木に変換するアルゴリズムを示す．まず，記号の意

<!ELEMENT item (books,music)><!ELEMENT books (book)><!ELEMENT book (item,isbn)><!ELEMENT music (title, author)><!ELEMENT isbn (#PCDATA)><!ELEMENT title (#PCDATA)><!ELEMENT author (#PCDATA)>
図 4: ループを含む DTD（ 11 ）

let vk be a new node with l(vk ) = lk (j + 1 ≦ k ≦j + n)（ 12 ）

let A(vk ) be a set of ancestor nodes of vk , i.e.,A(vk ) = A(vi ) ∪ {vi } (j + 1 ≦ k ≦ j + n)
（ 13 ）VD ← VD ∪ {vj+1 , ..., vj+n }（ 14 ）ED ← ED ∪ {vi → vj+1 , ..., vi → vj+n }（ 15 ）V ← V ∪ {vj+1 , ..., vj+n }（ 16 ）

j =j+n（ 17 ）

if l(vk ) = l(vm ) for some vm ∈ A(vk ) then

（ 18 ）（ 19 ）

item

books

music

delete vk from V
end if（ 20 ）

end process node

（ 21 ）

return TD = (VD , ED )（ 22 ） end algorithm
次に，DTD の木分割処理のアルゴリズムを示す (文献 [3] の

book

title

author

木分割アルゴリズムを用いる)．k は正整数を表す．ただし，kの値は最小のノードの重みより大きい値とする．分割した辺のisbn

図 5: ループを含む DTD のグラフ表現

集合を C ，ノード v の子ノードの集合を S(v)，重みを w(v) と表す．ノード v を部分木の根とした場合に，この部分木のすべてのノードの重みの和を W ∗ (v) と表す．

味を説明する．Σ をラベル集合とする．Σ 上の正規表現を次のように定義する．

•

ϵ と a ∈ Σ は正規表現である．

•

r1 , · · · , rn を正規表現とする (n >= 1)．このとき，r1 · · · rn

および r1 | · · · |rn は正規表現である．

•r を正規表現とする．このとき，r∗ ，r?，および，r+ は正規表現である．
正規表現 r によって表される言語を L(r) と表す．

DTD を組 D = (d, sl) と定義する．ここで，d は Σ から Σ
上の正規表現集合への写像，sl ∈ Σ は文書要素である．ラベルa ∈ Σ に対して，d(a) を a の内容モデルという．たとえば，図4 の DTD は D = (d, item) と表すことができる．DTD の木構造を TD = (VD ，ED ) と表す．ここで，VD はノードの集合，

ED は辺の集合である．ノード v の祖先ノードの集合を A(v)と表す．

DTD を木に変換するアルゴリズムを以下に示す．
入力：DT D D = (d, sl)
出力：DT D の構造を表す木 TD（ 1 ） begin（2）

VD = ∅; ED = ∅

（3）

j=1

（4）

l(v1 ) = sl; VD ← {v1 }（5）

V ← {v1 }（6）

while V ̸= ∅ do

（7）

begin process node

（8）

choose a node vi from V（9）delete vi from V（ 10 ）

let {lj+1 , lj+2 , ..., lj+n } be the set of elements

appearing in d(l(vi ))DTD の木分割処理のアルゴリズムを以下に示す．
入力：DT D の構造を表す木 TD ，正整数 k
出力：辺集合 C（ 1 ） begin
（2）

C=∅

（3）

assign W ∗ (v) = w(v) to all leaf nodes in TD ;（4）for i=maximum-level-in-T downto 1 do

（5）

begin process i_th level;（6）

while there is an unprocessed node v in level ido（7）

begin process node v:（8）remove heaviest sons of v one by one from S(v)until W ∗ (v) = Σu∈S(v) W ∗ (u) + w(v) ≦ k;
（9）

For every such son w removed, add the edgev → w to C
（ 10 ）（ 11 ）

end process nodeend process level（ 12 ） end algorithm

3. 1. 2 変 換 処 理
変換処理では，上記アルゴリズムで得られた辺集合 C を用いる．XML データの根から変換処理を開始する．変換過程において，C に属する辺に遭遇する度に新たなスレッドを生成し，その辺の始点を根とする部分木を変換する．なお，各スレッドが XML データの必要な部分にアクセスする際，XML データ
は分割せずに，各スレッドが共通の XML データにアクセスして変換処理を行う．ここで，もし各スレッドで処理する XML
データのサイズの差が大きければ，1 つのスレッドの処理時間が長くなってしまい，全体の処理時間も長くなってしまう．DTDの木を分割した後，各部分の重みの和の値が近いため，各部分に対応する XML データのサイズもほぼ同じであり，各スレッ

ドの処理時間もほぼ同じであると期待される．このようにして，<!ELEMENT a(b,f)><!ELEMENT b(c+ ,(d|h) )><!ELEMENT c(e)><!ELEMENT d(e?)><!ELEMENT h(e)*><!ELEMENT f(g*,e)><!ELEMENT g(f|a)*><!ELEMENT e(i)><!ELEMENT i(#PCDATA|i|j|k)*><!ELEMENT j(#PCDATA)><!ELEMENT k(#PCDATA)>

処理効率の向上を図っている．
変換処理のアルゴリズムに出現する記号の意味を説明する．

XML データを Tx ，そのノードの集合を Vx ，辺の集合を Ex と表す．根が v の部分木を T (v) と表す．辺集合 C は DTD の木
分割処理のアルゴリズムの出力の辺集合 C である．

XML データ変換処理のアルゴリズムを以下に示す．
入力：XML データ Tx = (Vx , Ex )，木変換機 Tr ，辺集合 C
出力：変換した木 T ′ = (V ′ , E ′ )（ 1 ） begin（2）T′ = ∅

（3）

n=0

（4）

for i=1 to maximum-level-in-T do（5）begin process i_th level:

図 6: DTD D

a 1.0

while there is an unprocessed node v ∈ Vx in（6）level i do
（7）

b 1.0

begin process node v:（8）let vp be the parent node of v

（9）if vp → v ∈ C then

（ 10 ）

create a new thread and T ′ (v) ← Tr (T (v)) by

the thread（ 11 ）

let r be a rule in Tr applicable to v

（ 13 ）

apply r to v and add the obtained nodes toV ′ and the abtained edges to E ′（ 15 ）

d 0.5

h 0.5 g 2.0

e 1.0

1.0 e

e 0.5

e 2.0

i 2.0

i 1.0

i 1.0

i 2.0
1.0

1.0

j

1.0 1.0

k j1.0 k

j

k

1.0

k 1.0

j

1.0

end if
図 7: DTD から変換した木

end process node

（ 16 ）

end process level（ 17 ）

merge the trees T ′ (v) obtained by threads into T ′（ 18 ）

2.0 c

else

（ 12 ）（ 14 ）

f 1.0

return T

a 1.0′（ 19 ） end algorithm

3. 2 提案手法の具体例
3. 2. 1 DTD に関する処理の具体例
例として，図 6 に示す DT D D を考える．A(g) = {a, f } で

2.0 c

DTD を木に変換するとき，ループを生成しないために，g の子
i を含むため，DTD を木に変換した後，ノード i の子ノードとしてノード i を含まないようにする．DTD を木に変換するアルゴリズムを用いると，図 6 の DTD は図 7 の木に変換するこ

1.0

j

h 0.5

i 2.0

e 0.5

e 2.0

1.0

i 1.0

i 1.0

(1)

k

1.0 1.0

j1.0 kとができる．ノードの重みについて，*や+が付されたノードの重みを 2，?や | が付されたノードの重みを 0.5 に設定している．

f 1.0

d 0.5

1.0 e

あり，ノード g の子ノード a と f が A(g) に属しているため，
ノード a，f を削除する．同様に，ノード i の内容モデルの中に

b 1.0

(2)

j

k

g 2.0

e 1.0
i 2.0
1.0

1.0

k 1.0

j
(3)

図 8: 分割した DTD の木次に，DTD の木分割処理のアルゴリズムを用いて木を分割する．ここで，数値 k を 12 とし，変換した後の木（図 7）を

XML データを図 10 に示す．この XML データを図 9 の交換規入力とした場合，図 8 に示す 3 つの部分木が出力される．部分

則で HTML データに変換する変換結果である．HTML データ

木 (1)，(2)，(3) それぞれの重みの和は 7.0，11.5，8.0 である．

はウェブページで表現できるため，人間に対して，よりやすい

各部分木の重みの合計は k より小さい．

表現形式といえる．

3. 2. 2 変換処理の具体例
例として，図 9 の変換規則を考える．また，すべての要素の変換した後の mode 属性は p とする．初期状態は p とする．

図 12 に，変換処理のイメージ図を示す．XML データを 5 個
スレッドで変換していることが分かる．

(p,a)→html(p)(p,b)→body(p)(p,c)→h1(p)(p,d)→h2(p)(p,e)→span(p)(p,f)→head(p)(p,g)→title(p)(p,h)→h3(p)(p,i)→a(p)(p,j)→b(p)(p,k)→img(p)abj

図 9: 木変換機の変換規則

c

c

c

e

e

e

e

e

i

i

i

i

i

j k

j k

j

k k j

スレッド2

スレッド3

a

c

f

c

g

h

g

h

g

e
i

j

k k k

スレッド1

スレッド4 スレッド5

図 12: 変換処理のイメージ図bcf

クソフトのものを用い，XML データも XMark を用いて作成しg

た．このデータに適用する木変換機を作成した上で，提案手法

e

での XSLT 実行時間と並列処理を行わない場合の XSLT 実行
時間を比較し，提案手法の実行戦略が妥当かどうか，及び，木

e

e

e

e

e

変換機の変換規則の数の違いによる実行時間の変化を評価した．

i

XMark は異なるサイズの XML データを生成できる．実験用

i

i

i

i

i

j

k k

j

k

j k

k

XML データとして，30MB，60MB，90MB，120MB，150MBの 5 つを用意した．また，木変換機は変換規則数が 10，30，50，71 のものを著者が作成した．

j j k jk

4. 2 評価実験の結果
実験環境は以下の通りである．

図 10: XML データの木

CPU：Intel Xeon E5-2623 v3 3.0GHz

html

メモリ：16GB RAM

OS：Linux CentOS 7(64bit)

body
h1

h1

head

h1

title

h3

title

使用言語：Java 1.7.0_79

span

表 1∼ 表 4 に 4 つの木変換機に対する評価実験の結果を示す．
それらをグラフ化したものを図 13∼ 図 16 に示す．DTD 分割

span span span span spana

数が 0 の行は，並列処理を行わない単一スレッドによる実行時間を表す．なお，実行時間の単位はすべて分である．

a

a

a

a

a

b img img img

表 1: 変換規則数が 10 個の場合の実行時間
XML サイズb b img b img b img img b
図 11: 変換結果

4. 評 価 実 験
本章では，提案手法に対する評価実験について述べる．

DTD 分割数

30M

60M

90M

120M 150M

00.058 0.123 0.267

0.420

0.511

4

0.012 0.019 0.050

0.119

0.213

9

0.006 0.008 0.025

0.052

0.104

図 17∼ 図 19 に DTD 分割数が 0，DTD 分割数が 4 の実行
時間と DTD 分割数が 9 の実行時間に示す．

4. 1 評価実験の概要

4. 3 評価実験に関する考察

第 3 章の木分割アルゴリズムを用いた XSLT 実行手法を Java

30MB の XML データに対する変換処理では，XML データを用いて実装した．DTD は XMark [5] と呼ばれるベンチマーのサイズが小さいため，ほとんどの変換処理において並列化

表 2: 変換規則数が 30 個の場合の実行時間
7

XML サイズ
DTD 分割数

30M

60M

90M

6

120M 150M

01.182 2.119 3.182

4.783

5.963

4

0.202 0.343 0.519

0.761

0.894

9

0.097 0.184 0.261

0.394

0.448

5

4

表 3: 変換規則数が 50 個の場合の実行時間

2

XML サイズ
DTD 分割数

30M

60M

3

( )

時
間
分

1

90M

120M

150M

0

1.746 3.073 5.358

8.013

10.06140.736 1.104 1.456

1.908

2.791

9

0.184 0.302 0.521

0.722

0.904

0
0

30

60

90

DTD分割数0120

DTD分割数4

150

DTD分割数9

XMLデータサイズ(MB)

図 14: 変換規則が 30 個の場合の実行時間

表 4: 変換規則数が 71 個の場合の実行時間
XML サイズ
DTD 分割数

30M

60M

90M

120M

150M

0

1.963 4.020 5.672

8.451

10.583

4

0.936 1.233 1.748

2.236

3.379

9

0.368 0.456 0.572

0.792

0.934

12

10

8

6

時
間
分

0.6

( )

4

0.5
2
0.4
0
0

( )

時
間
分

30

60

DTD分割数00.3

90
DTD分割数4120150

DTD分割数9

XMLデータサイズ(MB)
0.2

0.1

図 15: 変換規則が 50 個の場合の実行時間

0030
DTD分割数060

90DTD分割数4120150

DTD分割数9
12

XMLデータサイズ(MB)10

図 13: 変換規則が 10 個の場合の実行時間8の効果が見られなかった．60MB 以上の XML データについてじており，提案手法の効果が確認できる．また，図 13∼ 図 16

( )は，提案手法と並列処理を行わない場合での実行時間に差が生

6

時
間
分

4

2

の「DTD 分割数 4」と「DTD 分割数 9」2 つ折れ線を見ると，

DTD 分割数がより多ければ，すなわちスレッドがより多けれ
ば，実行時間がより小さいことが分かる．

0
0

30

DTD分割数060

90DTD分割数4120150

DTD分割数9

XMLデータサイズ(MB)図 17∼ 図 19 から見ると，並列化の有無にかかわらず，変換規則の数が多いほど，実行時間が長くなる．また，DTD 分割数
が大きくなり，XML データのサイズが増加するに従って，変図 16: 変換規則が 71 個の場合の実行時間

換規則数による実行時間の時間差が大きくなることが分かる．
原因として，スレッドごとに変換する際に，変換に必要な情報を得ることと各スレッドを一つの木にマージすることに多くの時間を要することが考えられる．

5. む す び
本研究では，木分割アルゴリズムを用い，XSLT のサブセッ
トである木変換機の変換処理を並列実行する手法を提案した．

した XML データは XMark で生成し，変換規則も自分で書いたものであるため，実際に使用された XML データや変換規則12に即したものであるとは限らない．より多く，大きいな XML
データを使用した評価実験や，DTD 以外のスキーマ言語への10対応なども今後の課題となる．

8

6

文

( )

時
間
分

4

2

0
0

30

変換規則数1060

変換規則数3090

変換規則数50120150

変換規則数71

XMLデータサイズ(MB)

図 17: DTD 分割数が 0 の場合の実行時間

4
3.5
3
2.5

( )

時
間
分

2
1.5
1
0.5
0
0

30

変換規則数1060

変換規則数3090

変換規則数50120150

変換規則数71

XMLデータサイズ(MB)

図 18: DTD 分割数が 4 の場合の実行時間

1
0.9
0.8
0.7
0.6

( )

時
間
分

0.5
0.4
0.3
0.2
0.1
0
0

30

変換規則数1060

変換規則数3090

変換規則数50120150

変換規則数71

XMLデータサイズ(MB)

図 19: DTD 分割数が 9 の場合の実行時間

提案手法により処理時間を短縮することができたが，変換規則個数によって並列化の効果に差が生じた．本研究は下降型木変換機に限定したため，今後の課題として，より能力の高い木変換機への対応などが挙げられる．また，今回評価実験に使用

献[1] F. Zavoral and J. Dvorakovam , Perfomance of XSLT Processors on Large Data Sets , Applications of Digital Information and Web Technologies, 2009. ICADIWT ’09. Second
Inter-national Conference, no.10905932, pp.110-115, London, UK, Oct. 2009.
[2] H. Mizumoto and N. Suzuki, An XSLT Transformation
Method for Distributed XML , Proceedings of the 4th International Conference on innovative Computing Communication Technology (INTECH 2014), 10p., 2014.
[3] Kundu, Sukhamay, and Jayadev Misra. A linear tree partitioning algorithm .SIAM Journal on Computing 6.1 (1977):
151-154.
[4] R. Bordawekar, L.Lim, A. Kementsietsidis and B.W.
Kok Statistics-based Parallelization of XPath Queriesin Shared Memory Systems , The University of Hawaii,
http://www2.hawaii.edu/ lipyeow/pub/edbt10-xpathmulticore.pdf, January 2015.
[5] Schmidt A, Waas F, Kersten M, Carey M.J, Manolescu I,
and Busse R, XMark: A benchmark for XML data managemet VLDB ’02 Proceedings of the 28th international
conferenceon Very Large Data Bases. Hong Kong, China,
2002–08–20/08-23. VLDB, 2002, p.974–985.
[6] Wim Martens,Frank Neven, Typechecking Top-Down Uniform Unranked Tree Transducers . Lecture Notes in Computer Science, 2002, Volume 2572/2002, p.64-78.
[7] World Wide Web Consortium (W3C). Extensible Markup
Language (XML) 1.0 (Fifth Edition) , (online), available from〈 https://www.w3.org/TR/REC-xml/〉, (accessed 2016-05-28).
[8] World Wide Web Consortium (W3C). XSL Transformations (XSLT) Version 2.0 . (online), available from〈 http://www.w3.org/TR/xslt20/〉, (accessed 2016-05-30).
[9] Y. Wu and N. Suzuki, An Algorithm for Detecting XSLTRules Aﬀected by Schema Updates , 情報処理学会研究報告,2015-DBS-161(6), 6p., 2015.