DEIM Forum 2017 I2-2

木文法に基づき圧縮された XML 文書に対するデータ値を考慮した直接更新法
高山隆之介†

橋本

健二†

浩之†

関

† 名古屋大学 大学院情報科学研究科 〒 464–8603 名古屋市千種区不老町
E-mail: †takayama@trs.cm.is.nagoya-u.ac.jp, {k-hasimt, seki}@is.nagoya-u.ac.jp
あらまし XML 文書の圧縮法の 1 つとして木文法に基づく手法が知られている．また，その手法による圧縮文書に対して解凍せずに更新を行う手法が提案されている．しかし，これらの手法では要素の階層構造のみに注目しているため，要素がもつデータ値は考慮されておらず，更新位置の指定には構造に関する条件しか利用できない．本稿では，
木文法を用いた既存の圧縮法および直接更新法を拡張し，構造情報だけでなく，データ値の参照，およびそれらに依存した構造やデータ値の更新が可能な手法を提案する．また，提案手法の評価実験として，更新に要した時間・メモ
リについて計測し，代表的な XML データベース管理システムの 1 つである BaseX 上での更新との比較を行った結果について報告する．
キーワード XML, 木オートマトン, 木文法, 圧縮, 更新
るための選択木オートマトンや更新位置の検索アルゴリズム，

1. ま え が き

更新アルゴリズムを拡張することで，構造情報だけでなくデー

XML は構造化データの一つであり，タグによって構造を

タ値の参照，およびそれらに依存した構造やデータ値の更新が指定するデータの交換・蓄積書式である．XML 文書には同可能な手法を提案する．また，データ値を扱うための工夫としじ構造が頻出することが多く，サイズが大きくなりやすい．

てデータ値部分に関する情報の分割を行い，高速化を図る．ま

そのため，XML 文書に対する圧縮法が盛んに研究されていた，いくつかの XML 文書に対して提案手法に基づいて実装しる [4] [5] [8] [9] [10]．

たシステムを用いて評価実験を行った．更新に要した時間・メ

圧縮された XML 文書に対して更新を行う場合，一度解凍しモリ量について計測し，代表的な XML データベース管理シスてから更新し，再圧縮するという方法は実行時間，使用メモリ

テムの１つである BaseX [1] 上での更新との比較結果について

において非常に非効率的である．Straight-Line Context-Free Tree

報告する．

Grammar (SLCFTG) [5] に基づいて圧縮された XML 文書は圧縮以降の構成は次の通りである．まず 2 節では諸定義を与えされた状態のまま走査が可能であり [8]，その性質を利用して解る．3 節では XML 文書の圧縮について述べ，4 節では想定する

凍せずに直接更新を行う手法が提案されている [12] [13] [14]．

更新ならびに直接更新を行うアルゴリズムについて説明する．

5 節では実際の XML 文書に対する実験の結果を述べる．6 節
ではまとめと今後の展望について述べる．

2. 準

備

2. 1 デ ー タ 木
ランクとよばれる自然数をもつ記号の有限集合 Σ をランク付
きアルファベットとよぶ．記号 a ∈ Σ のランクを rank(a) と表
図 1 解凍 → 更新 → 再圧縮

図2 直接更新

記し，Σn = {a ∈ Σ | rank(a) = n} とする． Att を属性とよばれる記号の集合とする．

圧縮したまま処理を行うことで，同じ構造をもつために共有［定義 2.1］ (Σ, Att) 上のラベル付き順序データ木（以降，デーされている部分に対して重複した処理を回避することができ，タ木）は以下を満たす 3 項組 t = (D, λ, δ) である．

効率よく更新を行うことができる (図 1，2)．しかし，それらは（ 1 ） D ⫅ N∗+ ．ただし，N+ = {1, 2, 3, . . .}．

XML 文書に含まれるデータ値（属性値や CDATA）は考慮され（ 2 ） λ は D から Σ への全域関数である．

ていなかった．具体的に，更新位置を指定する際には構造に関（ 3 ） δ は D × Att から N への部分関数である．

する条件のみしか指定できず，文書に含まれているデータ値に（ 4 ） w = vv ′ ∈ D かつ v, v ′ ∈ N∗+ のとき，v ∈ D ．

関しての条件を指定することができなかった．また，データ値（ 5 ） v ∈ D かつ λ(v) ∈ Σn のとき，1 ≦ i ≦ n である全ての自体を更新することもできなかった．

i について vi ∈ D．

本稿では，既存手法 [14] で用いられていた更新位置を指定す□

D の要素を t の頂点（または位置）とよぶ． λ をラベル付け

関数，δ をデータ値関数とよぶ．頂点 v, vi ∈ D（v ∈ N∗+, i ∈ N+ ） ［定義 2.3］ A = (Σ, Q b, Q t , qb0, qt0, ∆b, ∆t , S) をデータ木オーについて，vi を v の i 番目の子頂点，v を vi の親頂点とよぶ．

トマトンとする． (Σ, Att) 上のデータ木 t = (Dt , λ t , δ) に対して，子頂点をもたない頂点を葉とよぶ．また，ϵ を t の根頂点といΣ × Q b × Q t 上の木 r = (Dr , λ r ) が以下の条件を満たすとき，rう．頂点 v ∈ D を根頂点とする t の部分木を t v と表す．δ(v, a)

は A による t の受理実行木であるという．

が定義されていてかつ δ(v, a) = d のとき，頂点 v は属性 a に関•Dr = Dt

するデータ値 d をもつという． (Σ, Att) 上のデータ木からデー•

各頂点 p ∈ Dt は以下を満たす．

タ値を除いたものを Σ 上の木とよぶ．Σ 上の木 t は，データ木–

p が 葉 で あ る と き ，あ る 状 態 qt ∈ Q t が 存 在 し ての定義から δ を除いて，t = (D, λ) のように 2 項組で表す．

λ r (p) = (#, qb0, qt ) ．

XML 文書は，頂点のラベルによってその子頂点の数が固定–

p が葉でないとき， λ t (p)(qb, qt ) → (qt1, qt2 ) ∈ ∆t と(λ t (p), qb1, qb2 ) → (a, φ)?qT : qF ∈ ∆b が存在して，されないランクなしラベル付き順序木でモデル化できる．ラン
クなし木は fcns 符号化 [6] によって 2 分木に符号化できること

λ r (p) = (λ t (p), qb, qt )が知られている．fcns 符号化によって， (Σ, Att) 上のランクなしデータ木を (Σ ∪ {#}, Att) 上の 2 分木に符号化できる．ここ∧ ∃w1 .λ r (p1) = (w1, qb1, qt1 )で，# は rank(#) = 0 かつ Σ に含まれない記号であり，2 分木に∧ ∃w2 .λ r (p2) = (w2, qb2, qt2 )符号化された木における Σ 中の記号 a はすべて rank(a) = 2 で∧ (φ(δ(p, a)) ⇒ qb = qT ) ∧ (¬φ(δ(p, a)) ⇒ qb = qF )ある．以下の図 3 のランクなし木に fcns 符号化を施すことで，
図 4 の 2 分木を得ることができる．以降，fcns 符号化によってボトムアップ遷移規則について，その右辺にある φ が恒真である

2 分木化されたデータ木を扱う．

場合，w(qb1, qb2 ) → qT のように略記する．A は決定性である
ので，A による t の受理実行木は葉頂点のラベルの第 3 成分を除

dblp
article□thesisき高々 1 つである．r が A による t の受理実行木であるとき，Athesisによって選択される t の頂点集合を A(t) = {p ∈ Dt | λ r (p) ∈ S}
title

authorauthortitle

authortitle

authorとする．
データ木オートマトン A = (Σ, Q b, Q t , qb0, qt0, ∆b, ∆t , S) に対

図 3 ランクなし木の例

し，A b = (Σ, Q b, qb0, ∆b ) を A に付随するボトムアップ木オーdblp

トマトンという．A b による受理実行木を同様に定義する．

#

articlethesisthesis

#

3. 圧

title

authorauthor# titleauthor# titleauthor

#

#

#

#

#

#

#

#

縮

3. 1 文法による木構造圧縮Σ ∩ X = ∅ であるような変数の可算集合を X = {x 1, x 2, . . .}としたとき，X に属する変数をランクが 0 の記号として含図 4 fcns 符号化された 2 分木の例

む木の全体集合を T (Σ, X) と表記する．t ∈ T (Σ, X) 中のど

2. 2 データ木オートマトンの変数も高々 1 回しか出現しないとき，t は線形であると本稿で扱うデータ木オートマトンは，ボトムアップ先読み付き

いう．t ∈ T (Σ, {x 1, . . . , x n }), t 1, . . . , t n ∈ T (Σ, X) としたとき，

決定性選択トップダウン木オートマトン (Deterministic Selectingi ∈ {1, 2, . . . , n} について， λ t (pi ) = x i である頂点 pi を木 t i で

Top-down tree automaton with Bottom-up look-ahead, DSTA B ) [14]置き換えて得られた木を t[x 1 /t 1, . . . , x n /t n ] と表記する．つまにデータ値の比較を追加したものである．

り，[x 1 /t 1, . . . , x n /t n ] で σ(x i ) = t i (1 ≦ i ≦ n) であるような代［定義 2.2］ 2 分木上のデータ木オートマトンは 8 項組 A =入 σ を表す． z < (Σ ∪ X) について，z がちょうど１度だけ出現(Σ, Q b, Q t , qb0, qt0, ∆b, ∆t , S) である．ここで，するような木 C ∈ T (Σ, X ∪ {z}) を文脈とよぶ．C[z/t] の代わり•

Σ はランク付きアルファベットに C[t] と表記する．

•

Q b, Q t は状態の有限集合［定義 3.1］ 文脈自由木文法 (Context-Free Tree Grammar，CFTG)•

qb0 ∈ Q b, qt0 ∈ Q t は開始状態•∆b は w(qb1, qb2 ) → (a, φ)?qT : qF という形のボトム

は 4 項組 G = (N, Σ, P, S) である．ここで，アップ遷移規則の有限集合，ただし，w ∈ Σ, qT , qF , qb1, qb2 ∈Q b, a ∈ Att, φ は頂点のもつ属性 a のデータ値に関する述語•∆t は (w, qb, qt ) → (qt1, qt2 ) という形のトップダウン遷

移規則の有限集合，ただし，w ∈ Σ, qt , qt1, qt2 ∈ Q t , qb ∈ Q b（ 2 ） Σ はランク付きアルファベット（ 3 ） P は A(x 1, . . . , x n ) → t という形の生成規則の有限集合．ここで，A ∈ N, rank( A) = n, t ∈ T (Σ ∪ N, {x 1, . . . , x n }) であり，t には x 1, . . . , x n が現れる．
（ 4 ） S ∈ N は rank(S) = 0 の開始非終端記号．

•

S ⫅ Σ × Q b × Q t は選択指定の有限集合•∆b, ∆t それぞれにおいて，任意の異なる２つの遷移規則

は同一の左辺を持たない（ 1 ） N は非終端記号の有限集合□□生成規則 A(x 1, . . . , x n ) → t ∈ P(ただし rank( A) = n), 文脈 C ∈T (Σ∪N, X∪{z}) ，s = C[A(t 1, . . . , t n )]，s ′ = C[t[x 1 /t 1, . . . , x n /t n ]]

で あ る よ う な 木 t 1, . . . , t n ∈ T (Σ ∪ N, X) が 存 在 す る と き ，T (Σ ∪ N, X) 上の関係 s ⇒ G s ′ が成り立つと定義し，⇒ G の反射推移閉包を ⇒∗G と書く．また，G によって生成される木言語
を L(G) = {t ∈ T (Σ) | S ⇒∗G t} と定義する．さらに，2 項関係

4. 直接更新法
4. 1 更新の定義与えられた木のどの頂点をどのように変更するのかを指定す⇝ G を {( A, B) ∈ N × N | A → t ∈ P かつ B が t に現れる} で定るため，更新を 2 項組 (A, op) で指定する．ここで，A はデー

義する．

タ木オートマトンであり，更新対象の木を t = (D, λ, δ) とすると

［定義 3.2］ 直 線 的 文 脈 自 由 木 文 法 (Straight-Line CFTG，き，A の選択する頂点集合 A(t) が更新位置集合となる．また，

SLCFTG) は以下の条件を満たすような CFTG G = (N, Σ, P, S)

op は更新操作を表し，relabel, delete, insert-before, insert-after,

である．

update-value のどれかである．それぞれの操作は fcns 符号化を

（ 1 ） 全 て の A ∈ N に つ い て ，た だ １ つ の 生 成 規 則

行う前のランクなし木における “自然な” 更新操作に対応してA(x 1, . . . , x n ) → t ∈ P が存在し，t が線形である

いる．

（ 2 ） 関係 ⇝ G は非循環

relabel(s ′ )非終端記号 A ∈ N を左辺にもつ生成規則の右辺の木を t A と表する．

□

delete()記する．

本稿では一般性を失うことなく，規則の右辺の木 t においてp ∈ A(t) である全ての p について， λ t (p) = s ′ と

p ∈ A(t) である全ての p について， p 以下の部分木

t p = λ t (p)(t 1, t 2 ) を t 2 に置き換える．

変数は左から右に x 1, . . . , x n の順番で現れると仮定する．また，

insert-before(t i = r (t i1, #))関係 ⇝ G の推移閉包を ⇝+G と書き， A ⇝+G B のとき， A は下

p 以下の部分木 t p = λ t (p)(t 1, t 2 ) を r (t i1, λ t (p)(t 1, t 2 )) に置きの階層に B をもつという．

換える．

G が SLCFTG であるとき，G によって生成される木言語
L(G) の要素はただ 1 つとなる．与えられた木 t のみを生成す

insert-after(t i = r (t i1, #))p ∈ A(t) である全ての p について，

p ∈ A(t) である全ての p について，

p 以下の部分木 t p = λ t (p)(t 1, t 2 ) を λ t (p)(t 1, r (t i1, t 2 )) に置きる SLCFTG G ，すなわち L(G) = {t} を満たす G を t の圧縮と換える．

いう．与えられた t から L(G) = {t} を満たす G を構成するこ

update-value(attr, opr, v)とを，t を圧縮するという．逆に G から t を計算することを，δ(p, attr) を opr (δ(p, attr), v) で上書きする．

G を解凍するという．

relabel, delete, insert-before, insert-after は ，選 択 頂 点 を post-p ∈ A(t) である全ての p について，［例 3.1］ G = ({S, A, B}, {dbl p, article, thesis, title, author, #}, P, S) order(帰りがけ順) で更新していき，update-value は pre-order(行きがけ順) で更新する．

は図 4 の 2 分木を圧縮した例である．ここでdelete, insert-before, insert-after については，構造が変更され
S → dbl p(article( A(B), thesis( A(#), thesis( A(#), #))), #) 






ることにより位置が変化する頂点が存在するため，
δ の更新が





P=
A(x)
→
title(#,
author(#,x))
必要となる．











 4. 2 提 案 手 法
B→author(#,#)
□
3. 2 圧縮データ木(Σ, Att) 上のデータ木を圧縮する際，木構造部分とデータ値部分を分離したものを考える．
［定義 3.3］ t = (D, λ, δ) をデータ木とし，t を木構造圧縮して得られた SLCFTG を G とする．このとき，2 項組 (G, δ) をデー
タ木 t に対する圧縮データ木とよぶ．

δ の表現として，次のような位置と属性の組をキーとするようなマップを考える．文書の構造にもよるが，fcns 符号化を
表 1 データ値関数 δ の表現
位置

属性

データ値

12

lang

jp

121
..
.

from
..
.

us
..
.

この節では，(Σ, Att) 上のデータ木 t = (D, λ, δ) に対する圧縮

データ木 t ′ = (G, δ) とデータ木オートマトン A が与えられた
ときに，t ′ を解凍することなく A によって選択される t の頂点集合を求め，その選択頂点に対して更新を行う手法を提案する．[14] と同じように，更新位置の検索と更新処理の 2 段階で行われる．

4. 2. 1 更新位置の検索
更新位置の検索の基本方針は，G の開始規則の右辺 t S の各頂点に状態を割り当てながら受理実行木を構成することである．
このとき，頂点のラベルが非終端記号の場合は，その非終端記
号を左辺にもつ生成規則の右辺の木に移り同様に受理実行木を構成していく．
更新位置の検索は，[14] と同じようにアルゴリズム bu_evalと td_eval の 2 段階で行われる．bu_eval は，与えられた木を

post-order で再帰的に評価し，A に付随する A b による受理実
行木を構成し ARmap というマップに記憶していく．td_eval は，行っていることから位置には “2” が頻出するためラン・レング

bu_eval の結果に基づき A のトップダウン部の評価を行う．たス符号化を施し圧縮する．

だし，構造情報だけでなくデータ値も参照するように拡張する．

bu_eval の擬似コードを Algorithm 1 に示す．[14] のように構造情報だけを考える場合は，非終端記号の引数に割り当てられた状態が全て等しいとき，構成される受理実行木は等しくなり

Algorithm 1 bu_eval(t : 木, p : t 上の位置, σ : X → Q b , (ℓ: 非終

重複回避が可能である．しかし，データ値も考慮する場合は，非端記号, c: データ木上の位置), π: データ木上の現在位置)

終端記号の引数に割り当てられた状態が全て等しくても，デー

1: s = λ t (p) ∈ Σ n, 各 i(1 ≦ i ≦ n) について qbi = λ t (p · i)[2] とお

く．また，qb1 · · · qb n = qb s とおく．

タ値の条件判定を行った結果に依存して，異なる受理実行木が構成されることがある．

2: if s が非終端記号 then

非終端記号の引数に割り当てられた状態から，データ値の条

3:

件判定が行われないとわかり，かつその引数に割り当てられた4:状態に対して受理実行木が構成済みの場合は，既存研究と同じように受理実行木の構成を回避することができる．それ以外の場合はまず受理実行木を構成し，その後構成した受理実行木と5:

for i = 1 to n do
bu_eval(t, p · i, σ, (ℓ, c), π · Vmap(s, i))end for

6: else if s が終端記号かつ s , # then7:

bu_eval(t, p · 1, σ, (ℓ, c), π · 1)

8:

bu_eval(t, p · 2, σ, (ℓ, c), π · 2)

同じものがすでに構成済みであれば，その受理実行木を削除する

9: end if

ことで同じ受理実行木がメモリ上に存在しないようにする．非10: if s が変数 then

終端記号とデータ値の条件判定が適用された頂点の状態列，引11:数の状態列の組が定まれば受理実行木は一意に定まるので，これらの組を ARmap のキーとすることで A b による同一の受理実行木の構成を回避する．また，G を走査する際には，δ によっ

λt (p) = (s, σ(s)) に上書き

12: else if s が終端記号 then
13:
14:
15:

if s = # thenλt (p) = (#, qb0 ) に上書き
returnてデータ値を参照するためにもとのデータ木上での位置を計算

16:

end if

しながら走査する．非終端記号 A の子頂点の位置は t A におけ17:

if s(qb1, qb2 ) → (a, φ)?qT : qF ∈ ∆ b then

る変数の位置に対応するため，Vmap( A, i) を非終端記号 A ∈ N

18:の i 番目の変数の位置としてあらかじめ計算しておく．ここで，

19:

非終端記号 A の変数 x i の位置は， A(x 1, . . . , x i, . . . , x n ) ⇒∗G t

20:

かつ，t ⇒ G t ′ である t ′ が存在しない（すなわち t に非終端記号が出現しない）t における変数 x i の位置である．Jmap(A, π)

21:を左辺にもつ規則の右辺 t A を評価したときに，条件判定をも25:

つ遷移規則が適用された頂点に割り当てられた状態列を記憶す26:

るためのマップであり，ARmap(A, ·, ·) の第 2 成分を決定するた

27:

SLCFTG G = (N, Σ, P, S) が与えられたとき，まず bu_eval を実引数値 (t S , ϵ, ⊥, (S, ϵ ), ϵ) で呼び出して A b による受理実行木を29:

規則の左辺の非終端記号，c は ℓ のデータ木上の位置，π は pのデータ木上の位置を表す．

Jmap(ℓ, c) に qF を追加
end ifelse if s(qb1, qb2 ) → qb ∈ ∆ b thenλt (p) = (s, qb ) に上書き
end ifif ARmap(A, ϵ, qb s ) が未記憶 then30:

A(x1, ..., x n ) → t A ∈ P である t A について31:

bu_eval(t A, ϵ, [x1 /qb1, . . . , x n /qb n ], ( A, π), π)32:

A b による t A の受理実行木 t ′A を ARmap(A, Jmap( A, π), qb s )33:

Jmap( A, π) が ϵ でなかったら，λt ′ (ϵ )[2] を Jmap(ℓ, c) に追

に記憶
A

加する

し（2-9 行目）
，その後，次のように頂点 p を評価する．σ は変数に割り当てる状態を表す代入，ℓ は t = t ℓ を右辺にもつ生成λt (p) = (s, qF ) に上書き

28: else if s が非終端記号 A then構成する．一般に bu_eval(t, p, σ, (ℓ, c), π) は第 1 引数で与えられた木 t の頂点 p の子頂点に対して bu_eval を再帰的に呼び出

Jmap(ℓ, c) に qT を追加
else

23:
24:

データ木オートマトン A = (Σ, Q b, Q t , qb0, qt0, ∆b, ∆t , S) とλt (p) = (s, qT ) に上書き

22:は，データ木上の位置 π に対応する非終端記号 A に対して Aめに用いる．

if φ(δ(π, a)) then34:

end if35:

λt (p) = (s, λt ′ (ϵ )[2]) に上書きA

36: end if（ 1 ） p のラベルが変数 x のとき（10-11 行目）
代入 σ を用いて状態 σ(x) を割り当てる．

るので，代入 [x 1 /qb1, . . . , x n /qbn ] を構成して bu_eval を実引（ 2 ） p のラベルが終端記号のとき（12-27 行目）

数値 (t A, ϵ, [x 1 /qb1, . . . , x n /qbn ], ( A, π), π) で呼び出す．もし，∆b に従い状態を割り当てる．ただし，ラベルが#のときは初

ARmap(A, ϵ, qbs ) が記憶済みなら，t A の再評価は行わない．t A

期状態である qb0 を割り当てる．このとき，データ値の条件判定をもつ遷移規則によって状態 qb が割り当てられた場合はJmap(ℓ, c) に qb を追加する．

の評価後に ARmap(A, Jmap( A, π), qbs ) に得られた A b による受理実行木を記憶する．もし，ARmap(A, Jmap( A, π), qbs ) が記憶済みなら，同一の受理実行木が構成済みであるため，得られた（ 3 ） p のラベルが非終端記号 A のとき（28-34 行目）

受理実行木を削除する．Jmap( A, π) が ϵ でなかったら，t A の根

生成規則 A(x 1, . . . , x n ) → t A ∈ P の右辺 t A を再帰的に評頂点に割り当てられた状態を Jmap(ℓ, c) に追加する．

価する．t p = A(t 1, . . . , t n ) とするとき，t A 中に現れる変数

x 1, . . . , x n に 割 り 当 て る 状 態 は 部 分 木 t 1, . . . , t n の 根 頂 点 に割り当てられた状態 (左から順に qb1, . . . , qbn とする) とな

td_eval は ARmap に記憶された A b による受理実行木を preorder で再帰的に評価して A による受理実行木を構成し，選択
頂点を UDmap というマップに記憶していく．非終端記号のボ
トムアップでデータ値の条件判定が適用された頂点の状態列と各引数に割り当てられた状態列，非終端記号にトップダウンでファイルを関連付けるための属性を導入する．これは関係デー

割り当てられた状態が全て等しいとき，構成される A によるタベースにおける 2 次キーに相当する．また，ファイルを表 2

受理実行木は等しくなる．そこで，それらを UDmap のキーとのような表形式で表すことを前提とすると，属性分割は垂直分することで同一の受理実行木の重複した構成を回避する．

割ということもできる．

重複回避のために UDmap は 4 つの要素 (リスト V ，リスト

表2 分 割 前 δT ，リスト N ，L) を記憶する．V は t A 中の変数に割り当てられた状態のリスト，T は t A 中の選択頂点の位置のリスト，Nは t A 中の非終端記号で下の階層に選択頂点をもつ非終端記号と割り当てられた状態と位置の組のリストである． L は更新を行う際に使用する．UDmap を辿ることで，選択頂点までの経路を得ることができる．

位置

属性名

データ値

11

text

long text

112

text

long long text

1122
..
.

text
..
.

super long text..
.

[14] と同様に ARmap に記憶されたボトムアップの受理実行
木を，データ木上の位置を計算しながら再帰的に評価し，受理実
行木を構成していく．その際は，Jmap の情報を用いて ARmap

表 3 分 割 後 δ1

表 4 分 割 後 δ2

位置

属性名

ID

ID

から bu_eval で構成したボトムアップの受理実行木を得て評価

11

text

1

1

long text

していき，必要な情報を UDmap に記憶していく．bu_eval の

112

text

2

2

long long text

終了後，td_eval を実引数値 (t S , qt0, ϵ, (S, ϵ, ϵ, qt0 )) で呼び出して

1122
..
.

text
..
.

3
..
.

3
..
.

super long text..
.

A による選択頂点集合を求める．

データ値

4. 2. 2 更 新 処 理
入力の圧縮データ木 (G, δ) と更新 (A, op) に対して，bu_eval

4. 3. 2 レコード分割と tu_eval によって得られた UDmap を用いて，A による各選

レコード分割は，データ値関数の定義域を複数の部分集合に択頂点に更新操作 op を適用した結果の圧縮データ木 (G ′, δ ′ ) を分割し，その分割にしたがって定まる複数のデータ値関数ご構成する．G から G ′ への木文法の更新については文献 [14] にとにデータ値関数を保存する方法である．属性分割と同様，レあるアルゴリズム update と同様に実行できる．

コード分割により，データ値の更新において必要な部分だけを今回新たに追加した update-value(att, opr, v) については，す

読み込むことにより更新処理の効率化を図る．属性分割を垂直べての選択頂点 p に対して，δ(p, attr) を opr (δ(p, attr), v) で上

分割ともよぶのに対して，レコード分割を水平分割とよぶこと書きすることで実現する．

もある．

また，delete, insert-before, insert-after によって構造情報が更A新された場合に δ の更新が必要となる．選択頂点前後への挿入や削除が，選択頂点と子孫関係にある頂点の位置を変化させる

dblp

#
B

からである．具体的には，delete, insert-after は選択頂点の右の部分木以下の位置，insert-before は選択頂点以下の部分木の位

article

置が変化する．各選択頂点につきその頂点での更新に影響を受けるすべての頂点位置を毎回更新していくのは非効率であるの

122

thesis

11

title

1212

title

#

article

#

1221

title

thesis122212#title

で，各頂点につき位置の更新は一回で済むようにする．UDmap
を用いることで選択頂点位置は pre-order で列挙可能であるの

#

#

#

#

で，その順で δ 中の位置を更新していく．その際に，更新しようとしている位置より先祖での更新による位置のずれを覚えて表5おくことによって一度の走査で更新可能である．

,1212)δ (ϵA

表6

4. 3 データ値関数の分割

位置

属性

データ値

XML 文書が多くのデータ値を含む場合，それらを 1 つのファ

11
..
.

text
..
.

a
..
.

イルにまとめておくと更新には不要な部分の読込みや書込みに(122,122212)
δB

位置

属性

データ値

1
..
.

text
..
.

c
..
.

時間がかかる場合がある．そのため，データ値関数のファイル
を複数に分割しておくことにより，なるべく必要な部分のファ
イルだけを読み込んで更新するようにする．

4. 3. 1 属 性 分 割
属性分割では，データ値関数を実現するデータ構造（ファイル）を属性にしたがって分割し，更新時に必要なファイルのみを読み込むことで，更新処理の効率を向上させる．表 2 を属性分割した例を，表 3,4 に示す．これらに示すとおり，分割後のデータ値関数をレコード分割する際にいくつに分割されたかを分割数とよぶ．分割された各データ値関数 δ はそれに含まれるレコードの位置集合 Pδ について以下の条件をみたすようにする．

•

ある位置 proot が存在して，他のどの位置 p ′ ∈ Pδ もproot の子孫である．

#

•どの位置 p ∈ Pδ についても， p の左の子 p1 の子孫はす

表 8 更新位置と更新操作

べて Pδ に含まれる．

# 文書名

更新位置を表す XPath 式

位置 pr oot を根の位置とよび， Pδ 中で辞書式順序に関して最

1 BaseBall

大のものを δ の終端位置とよぶ．分割された各データ値関数 δ2 BaseBall//PLAYER[HOME_RUNS >= 10]//LEAGUE//
PLAYER[WINS >= 15]

ごとにこれらの 2 つの絶対位置を記憶することによって，選択

3 Shakespeare //ACT[text() = ACT I]

deleterelabeldelete4 Shakespeare //ACT[text() = ACT III]//dataset[@subject = astronomy]
5 Nasa/altname[1]頂点がどのデータ値関数に含まれているかを決定することができる．また，各レコードの位置は根の位置に対する相対位置として記憶する．根の位置の（真の）先祖頂点において構造の更6 DBLP

新が起こった場合は，この根の位置と終端位置を修正すればよ

7 SwissProt

8 TreeBankが見込める．

験

update-value
insert-after//proceedings[year >insert-before= 2000]/url//Entry[@seqlen > 2500]/Species update-value/FILE[@name = "head.cmb"]//VP[.//S//NP//VP
delete//PP//NP//NP//NNP]//_PERIOD_

く，各レコードを読み込む必要がないので位置の更新の効率化

5. 実

更新操作

表 9 圧縮文書に対する実験結果
更新
トップ 更新ダウン (構造) (データ値)
合計
(ms)
(ms)
(ms)
(ms)

#

ボトム
アップ
(ms)

1

29

0

2

25

56

3,380

2

16

0

0

0

16

2,813

3

22

14

0

35

71

14,436

4

21

18

0

23

62

14,129タ値関数を保持するファイルを分割しなかった場合の結果や分

5

89

30

0

2,210

2,329

65,903

割数を変化させた時の結果も示し，分割や分割数の効率への影

6

289

434

0

19,891 20,614 326,457

響を考察する．代表的な XML データベース管理システムの 1

7

531

835

39

21,481 22,886 411,673

つである BaseX とも更新に要した時間，最大使用メモリを比較

8

804

1,084

53

16,064 18,005 501,133

#

解凍

ボトム
アップ
(ms)

トップ
ダウン
(ms)

更新
(構造)
(ms)

更新
(データ値)
(ms)

圧縮
(ms)

合計
(ms)

使用
メモリ
(kB)

1

22

18

10

2

24

51

129

12,365

2

22

15

14

0

0

48

147

14,251で表したものと行った更新操作を表 8 に示す．なお，XML 文

3

222

30

56

0

48

462

818

54,687

書の圧縮には，圧縮ツール TreeRePair [8] を使用し，分割数は

4

222

30

56

0

21

462

791

56,992

1-4 の文書が 50，5-8 の文書が 100 となるようにした．圧縮前

5

397

136

216

0

6,499

1,066

8,314

214,587のサイズ，圧縮後のサイズの定義は文献 [14] による．

6

8,390

2,323

2,890

0

19,121

12,38145,105

1,087,122

7

9,547

3,290

3,850

9

21,436

15,702

53,834

1,158,403

8

12,601

5,652

6,537

15

17,084

15,04156,9301,337,513

本節では，ベンチマークとなる XML 文書 [3] を圧縮して得られた圧縮データ木 (以降，圧縮文書) に対して，提案手法で更新
位置を検索し更新を行った際に要した時間および最大使用メモ
リなどを示す．また，一旦解凍した XML 文書 (以降，非圧縮文書) に対して更新を行った場合の結果も示し，比較する．デー

使用
メモリ
(kB)

する．
表 10

5. 1 実験環境と用いたデータ実験に用いた実行環境は OS: Ubuntu 14.04 LTS，プロセッサ:

Intel® Core™ i5-2400 3.10GHz，メモリ: 8GB である．用いたXML 文書に関する情報を表 7 に，更新位置の指定を XPath 式

文書名表 7 実験に用いたデータ
ファイルサイズ(kB)
圧縮前のサイズ

非圧縮文書に対する実験結果

圧縮後のサイズ

BaseBall652

28,305500間で更新が行えると言える．これは，圧縮文書に対しては同じ

Shakespeare

7,710

179,689

17,747

状態割当になることがわかっている部分木に対しては状態割当

Nasa

25,212476,645

22,781を行わずに結果を再利用することができるためである．

DBLP

134,315

3,332,129

150,720

SwissProt

115,467

2,977,030

247,873

TreeBank

87,4662,437,665

524,743

5. 2 非圧縮文書と圧縮文書に対する更新の比較
圧縮文書に対する実験結果を表 9 に，非圧縮文書に対する実験結果を表 10 に示す．
表 9 と表 10 の最大使用メモリを比較すると全ての更新において圧縮文書に対する更新の方が少ないメモリ使用量で行えることがわかる．これは，非圧縮文書の場合はデータ木をメモリ上に展開する必要があるのに対して，圧縮文書は同一の受理実
行木はメモリ上に複数存在することがないためである．
実行時間についても非圧縮文書よりも圧縮文書の方が短い時

5. 3 分割による更新の効率への影響
以下の表 11 に，分割をしなかった場合 (分割数 1) の結果を示す．表 11 と表 9 を比較すると，5-8 の文書に対してデータ値の更新に多くの時間がかかっている．これは，文書のサイズが大きいことや，データ値としてテキストデータを持っているた
め，データ値部分に関する情報が巨大になっており，加えて，分割されていないため更新に関係がないデータを大量に読み込んでしまうからである．分割することで更新に関係がない部分についてはある程度読み込まずに済ますことができるようになり，効率が向上することがわかる．
以下の表 12 に分割数を変化させたときの更新に要した時間を示す．なお，1-4 の文書に関しては，分割数を変化させてもあまり変化が見られなかったので省略した．

ボトム
アップ
# (ms)

トップ
ダウン
(ms)

表 11 分 割 な し
更新
更新(構造) (データ値)
(ms)
(ms)

に BaseX で作成した DB に対して更新を行ったときの結果を示
合計
(ms)

使用
メモリ
(kB)

す．また，表 15 に木構造圧縮したときの結果，表 16 に圧縮文書に対して直接更新法を行ったときの結果を示す．

1

38

0

2

23

63

3,208

2

19

0

0

0

19

2,987

3

25

16

0

42

83

15,229

4

24

18

0

26

68

15,924

BaseBall623

70,812

5

95

30

0

6,328

6,492

68,885

Shakespeare

1,006

100,040

6

295

447

0

45,152 45,894 354,113

Nasa

2,099

160,204

7

533

870

37

44,831 46,271 418,437

DBLP

11,928766,008

8

814

1,077

49

49,845 51,785 490,057

SwissProt

12,049819,354

TreeBank

9,230

1,022,877

表 13 DB 作成 (パース，索引付け)
時間 使用メモリ
文書名
(ms)
(kB)

表 12 分割数 n による効率への影響
n = 25 n = 50 n = 100 n = 200# (ms)
(ms)
(ms)
(ms)

5

2,003

2,127

2,329

2,459

6

27,93826,032

20,614

21,201

7

27,49823,54022,88622,421

8

23,13021,43718,005

17,165

表 14 XQuery 実行
時間 使用メモリ
#
(ms)
(kB)

1

842

108,7642875

110,2123

1,207

131,828

表 12 を見ると，5 の文書に関しては，更新位置が文書全体に

4

1,215

129,708

広がっており，結局分割したものすべてを読み込む必要があり，

5

3,923

211,020

分割数が少ないほうが効率が良くなったと考えられる．

6 15,930

また，6-8 の文書に関しては非常に大規模な文書であり，分割された 1 つ 1 つのサイズが大きくなり，更新の際に必要ない

863,592

7

8,402

1,011,542

8

5,359

1,072,793

情報を読み込んでしまう．そのため，ある程度分割数を大きくしたほうが効率よく更新が行えると考えられる．6 の文書については分割数が 200 のときよりも，100 のときの方が若干速く更新が行えている．これは，更新位置が文書の前半部分に集中して出現しており，分割数を増やしたことによって連続して出現している更新位置が途中で分断され，より多くの情報を読み込んでしまったためだと考えられる．

表 15 圧縮 (木構造圧縮，データ値抽出)
時間 使用メモリ
文書名
(ms)
(kB)

BaseBall159

Shakespeare

971

3,396
9,816

Nasa

2,388

12,972

DBLP

14,212

72,916

この結果から文書の構造やどの位置の頂点を更新するかなど

SwissProt

22,767

180,548

によって最適な分割数は変化すると考えられる．現状，あらかTreeBank

21,665

159,768

じめ分割されたものに対して問い合わせを行っているため，問い合わせによっては分割したことにより，分割しなかった場合
よりも時間がかかる場合も考えられる．どのように分割するかについてはなるべく効率が良くなるような方法を検討する必要

表 16 圧縮文書に対する直接更新（表 9 抜粋）
時間 使用メモリ
#
(ms)
(kB)

がある．例えば，更新位置と文書構造を見てから効率が良くな

156

るように分割することや，あらかじめユーザが行うであろう問

2

16

2,813

い合わせを予測した上で分割しておくことなどを考えている．

3

71

14,4364

62

14,12952,329

65,903

6 20,614

326,457

7 22,886

411,673

8 18,005

501,133

6. BaseX との比較
BaseX [1] は軽量，高速，高機能な XML データベース管理シ
ステムである．ここでは BaseX と更新に要する時間と使用メモ

3,380

リの観点から比較を行う．

BaseX は，まず XML 文書を読み込んで DB を作成してから，それに対して XML に対する問い合わせ言語である XQuery [2]を実行して更新を行う．実験時の Java 仮想マシンの最大ヒープ
サイズは 2048MB とした (-Xmx2048m)．以下の表 13 に BaseX
で XML 文書を読み込んで DB を作成したときの結果，表 14

表 14,16 を比較すると，使用メモリの点では，提案手法がより少ないメモリで更新できているが，更新に要した時間は，巨大なXML 文書である DBLP, SwissProt, TreeBank に対して，BaseXの方がより速く更新できており，とくに SwissProt と TreeBankに対しては更新に要した時間が大幅に短い．これらは，BaseX

の優れた XQuery の最適化や索引付け [7] [11] によるものだと考えられる．提案手法ではデータ値の更新が大部分を占めており，この部分を改善することができれば，大幅に更新に要する時間を削減することができる．

7. あ と が き
本稿では，木文法によって圧縮された XML 文書に対して解凍を行わずに，既存手法を拡張する形で文書の構造情報だけでなく文書に含まれるデータ値を考慮し，それらに依存した更新
位置の検索と更新を行う手法を提案した．
実験結果から，解凍してから更新するよりも，提案手法を利用して圧縮した状態のまま処理を行った方が少ないメモリで高速に更新できることが分かった．また，巨大なデータ値部分に関する情報を分割することでより高速に更新が行えることを確認した．BaseX との比較では，要した時間に関しては大きな文書に対しては BaseX がより高速に動作したが，要したメモリに関しては提案手法を利用して更新を行ったほうが少ないメモリ量で更新が行えた．
今後の研究では，実用化に向けて，高速化や省メモリ化を目
指し，より良いデータ値の表現方法や，圧縮の方法，分割の方法などを検討，考察していきたいと考えている．

文

献[1] BaseX | the xml database. http://basex.org.
[2] W3C XML Query (XQuery). https://www.w3.org/XML/Query/.
[3] XMLCompBench. http://xmlcompbench.sourceforge.net/
Dataset.html.
[4] S. Böttcher, M. Grohe, and C. Krislin. Clux - clustering XML subtrees. In Proc. of the 12th International Conference on Enterprise
Information Systems (ICEIS 2010), Vol. 1, pp. 142–150, 2010.
[5] G. Busatto, M. Lohrey, and S. Maneth. Eﬃcient memory representation of XML document trees. Information Systems, Vol. 33,
pp. 456–474, 2008.
[6] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez,
C. Löding, S. Tison, and M. Tommasi. Tree automata techniques
and applications, 2008. http://tata.gforge.inria.fr/.
[7] L. Kircher, M. Grossniklaus, C. GrÃĳn, and M. H. Scholl. Eﬃcient
structural bulk updates on the pre/dist/size xml encoding. In Proc. ofthe 31st International Conference on Data Engineering (ICDE 2015),
pp. 447–458, 2015.
[8] M. Lohrey, S. Maneth, and R. Mennicke. XML tree structure compression using RePair. Information Systems, Vol. 38, pp. 1150–1167,
2013.
[9] M. Lohrey, S. Maneth, and E. Noeth. XML compression via DAGs.
In Proc. of the 16th International Conference on Database Theory(ICDT 2013), pp. 18–22, 2013.
[10] S. Maneth and G. Busatto. Tree transducers and tree compressions. In
Proc. of the 7th International Conference on Foundations of Software
Science and Computation Structures (FoSSaCs 2004), pp. 363–377,
2004.
[11] L. Wörteler, M. Grossniklaus, C. Grün, and Marc H. Scholl. Function inlining in XQuery 3.0 optimization. In Proc. of the 15th Symposium on Database Programming Languages (DBPL 2015), pp. 45–48,
2015.
[12] 尾上栄浩, 橋本健二, 関浩之, 伊藤実. 木文法による圧縮 XML
文書に対する問合せと更新手法. 信学技報, Vol. 114, No. 271,
SS2014-28, pp. 17–22, 2014.
[13] 後藤健志, 尾上栄浩, 橋本健二, 関浩之. 木文法に基づく XML 圧
縮文書に対する直接更新手法の評価. 信学技報, Vol. 114, No. 416,

SS2014-45, pp. 73–78, 2015.
[14] 後藤健志, 高山隆之介, 橋本健二, 関浩之. 圧縮構造化文書のための更新手法の拡張とその実験的評価. 信学技報, Vol. 115, No. 486,
LOIS2015-75, pp. 69–74, 2016.