論文 / 著書情報
Article / Book Information
論題(和文)

更新処理を考慮したXMLラベルにおける構造情報の抽出手法

Title(English)

Structural Information Extraction Method for Update-conscious XML
Labeling

著者(和文)

高橋 昭裕, 梁 文新, 横田 治夫

Authors(English)

Akihiro Takahashi, Wenxin Liang, Haruo Yokota

出典(和文)

電子情報通信学会論文誌, Vol. J93-D, No. 6, pp. 795-804

Citation(English)

IEICE Transaction on Information & Systems, Vol. J93-D, No. 6, pp.
795-804

発行日 / Pub. date2010, 6

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2010 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

情報爆発論文特集

論 文

更新処理を考慮した XML ラベルにおける構造情報の抽出手法
高橋 昭裕† a)梁

文新†† b)

横田 治夫† c)

Structural Information Extraction Method for Update-conscious XML Labeling
Akihiro TAKAHASHI†a) , Wenxin LIANG††b) , and Haruo YOKOTA†c)

あらまし 近年，XML データベースの格納や検索処理のために XML 木の各ノードに構造ラベルを付ける研究が注目されている．XML 文書の更新が起こる場合，単純なラベリング手法では更新コストが高くなる．そこ
で，文書更新時のコスト低減を目的とした DO-VLEI ラベリング手法と，DO-VLEI ラベルの格納容量削減を目的とした圧縮 bit 列 DO-VLEI が提案されている．本論文では圧縮 bit 列 DO-VLEI コードを用いた XML 問合せを実現するために，ラベルから構造問合せ処理に必要となる情報を抽出する手法を提案する．圧縮 bit 列
DO-VLEI コードでは先頭からの走査をせずに構造情報を取り出すことが可能であるため，高速な問合せ処理が可能となる．更に，同様のラベリング手法である ORDPATH と構造情報抽出処理の実行時間を比較し，その優位性を示す．
キーワード

XML，性能評価，ラベリング，構造情報

1. ま え が きに大規模なラベルの付け替えが必要となる．そこで，大量の XML 文書を効率良く管理するために，RDBて，浮動小数点数法 [5] や範囲ラベリング法 [6]，範囲に格納する方法が注目されている [1]．XML 文書は，

ラベリング法を改良した更新に強い節点ラベル付け手

更新時のラベル付け替えのコストを抑える手法とし一組のタグをノードとして扱うことで木構造とみなす

法 [2]，などが提案されている．しかし，これらの手法ことができる [2]．図 1 に XML 文書を木構造とみなしにおいても同じ箇所に多数のノードが挿入された場合

た XML 木を示す．XML 文書を RDB に格納する際，にはラベルの付け替えが必要である．

XML 文書の木構造情報を保持するための方法としてこのようなラベル付け替えが発生する問題に対して，

XML 文書の各ノードにラベルを割り当て，ラベルと我々は他ノードのラベルを変更することなく無制限に

ノード情報をタプルとして格納する方法がある．ラベ

ノードを挿入することができる VLEI コード (Variable

ルの規則性により各ノード間の包含関係など，ノード

Length Endless Insertable code) と，VLEI コードをの XML 木における位置判定を可能にする．このよう用いたラベル付け手法を提案し，更新・検索処理に関なノードにラベルを付けることによって構造情報を保する改良を行ってきた [7]〜[10]．[7] では VLEI コード

持する手法をラベル付け手法と呼ぶ．

を前順後順法に適用した PP-VLEI と，Dewey Order

ラベル付け手法として，前順後順法 [3] や Deweyに適用した DO-VLEI を提案した．[8] では，包含関係

Order [4] などが提案されている．しかし，これらのの判定において，子孫ノードのラベルは必ず先祖ノー

ラベル付けに単純な連続する整数を用いると，更新時

ドのラベルよりも長いという特徴を利用することで，†検索処理の性能改善を行った．[9], [10] では，ラベル
東京工業大学，東京都
Tokyo Institute of Technology, 2–12–1 Ookayama, Meguro-††

大連理工大学，大連市
Dalian University of Technology, Development Zone, Dalian
116620, Chinaa) E-mail: akihiro@de.cs.titech.ac.jpb) E-mail: wxliang@dlut.edu.cnc) E-mail: yokota@cs.titech.ac.jp

電子情報通信学会論文誌

格納に必要な記憶容量低減を企図し，DO-VLEI コー
ドを bit 列で表現する，圧縮 bit 列 DO-VLEI コード

ku, Tokyo, 152–8552 Japan(Compressed-bit-string DO-VLEI code) を提案した．
XML の構造情報は，代表的なクエリ記述言語のXPath [11] や索引処理などに有用である．本論文では，圧縮 bit 列 DO-VLEI を用いて XPath の軸を用

c （社）電子情報通信学会 2010
D Vol. J93–D No. 6 pp. 795–804 

795

電子情報通信学会論文誌 2010/6 Vol. J93–D No. 6

いた構造に対するクエリを処理するために，XPath のを単純に整数とすると，兄弟間にノードを挿入する際各軸が表すノード集合を得るための手法を考案し，そなどにラベルの付け替えが必要となり，コストがかかの際に必要となる各ラベルに埋め込まれている情報をるという問題がある．

高速に抽出する手法を提案する．具体的にはそれぞれ

2. 2 VLEI コードの定義のノードに割り当てられた圧縮 bit 列 DO-VLEI コー

VLEI コードは 1 から始まる 0,1 の可変長 bit 列でドから木構造におけるノードの位置を知ることができ，あり，特殊な大小関係をもつ．以下に VLEI コードのまた，二つのノードの位置関係を知ることが可能とな定義を示す．

る．例えば二つの圧縮 bit 列 DO-VLEI コードを比較

定義 1．VLEI コードすることにより，二つのノードが親子関係にあるかをv を 1 から始まる {0,1} からなる bit 列とし，以下の調べることが可能である．その際にワード長分の bit

大小関係を満足する場合に VLEI コードと呼ぶ．

を同時処理することで高速に処理を行う．また，同様の情報を取得でき，DO-VLEI と同様に要素挿入に強いラベル付け手法である ORDPATH と処理時間について比較を行う．
本論文の構成は次のとおりである．まず，2. で DO-

VLEI 及び，圧縮 bit 列 DO-VLEI について説明し，3.
では関連研究として比較実験の対象となる ORDPATH
について説明する．4. で圧縮 bit 列 DO-VLEI コードによる XPath 処理手法について述べ，5. では圧縮

bit 列 DO-VLEI コードによるラベルの構造情報抽出
手法について説明する．6. で圧縮 bit 列 DO-VLEI と

ORDPATH のラベル構造情報抽出性能について比較を行う．最後に 7. でまとめと今後の課題を述べる．

2. 予 備 知 識
我々がこれまで提案してきた VLEI コードと，VLEI
コードに Dewey Order を組み合わせた DO-VLEI，

DO-VLEI コードを bit 列に変換する圧縮 bit 列 DOVLEI，更に圧縮 bit 列 DO-VLEI の性質について説明する．

2. 1 Dewey Order
Dewey Order では，親ノードのラベルの末尾に，デリミタ（区切り文字）と兄弟ノード間の順序を表現するコード（兄弟コード）とを加えて，子ノードのラv · 0 · {0|1}∗ ≺v v ≺v v · 1 · {0|1}∗
すなわち，あるラベル v に対して，右に 0 の付くもの
は v よりも小さく，1 の付くものは v よりも大きい．
ここで ≺v は VLEI コードによる比較を，· は文字列，
数字の連結を意味する．

VLEI コードでは，任意の二つの VLEI コードの間に存在する新しい VLEI コードを無制限に作り出すことができるため，他ノードのラベルを付け替える必要がない．よって，更新コストの低いラベル付けが可能となる．

2. 3 DO-VLEI
DO-VLEI では Dewey Order の兄弟コードに VLEI
コードを用いる．
定義 2．DO-VLEI（ 1 ） root ノードの DO-VLEI ラベルを Droot = 1とする．
（ 2 ） あるノードの兄弟ノード間の順序を VLEI
コード vchild の大小関係で表す．このとき，親ノードの DO-VLEI ラベルを Dparent とすると，兄弟ノード間の順序を表す VLEI コードが vchild であるノードの

DO-VLEI ラベル Dchild は次のようになる．
Dchild = Dparent . vchild

ベルを表現する．Dewey Order でラベル付けされたXML 木を図 1 に示す．Dewey Order の兄弟コード

Fig. 1796

図 1 XML 木
An example XML tree.

図 2 に DO-VLEI によってラベル付けされた XML

図 2 DO-VLEI コードによるラベル付け
Fig. 2 Labeling by DO-VLEI code.

論文／更新処理を考慮した XML ラベルにおける構造情報の抽出手法
表 1 XPath の軸
Table 1 XPath axes.
軸ancestor
precedingdecendant
followingparentpreceding-siblingchild
following-sibling

軸の説明
祖先ノード（親ノードを再帰的に取得することで得られる集合）
文書順でコンテクストノードより前 ∩ 祖先ノード以外
子孫ノード（子ノードを再帰的に取得することで得られる集合）
文書順でコンテクストノード以降 ∩ 子孫ノード以外
親ノードが存在する場合，親ノード
コンテクストノードの前にあるすべての兄弟ノード
子ノード
コンテクストノードの後ろにあるすべての兄弟ノード

木を示す．

係を指定するための用語である．例えばあるノード A

2. 4 圧縮 bit 列 DO-VLEI

をコンテクストノードとしたとき，軸 ancestor によっ

圧縮 bit 列 DO-VLEI は DO-VLEI コードをビットて A の祖先ノードすべてを選択することが可能である．

列表現に変換することにより，実際に扱うラベルのサ

主要な軸の説明を表 1 に示す．XML 文書の各ノード

イズを小さくし，また，bit 列による操作を可能にすは軸 ancestor, preceding, decendant, following のいる．なお，以降「」で囲まれている 0，1 及び．の列ずれかに属する．また，軸 parent, preceding-sibling,

は DO-VLEI コード，() で囲まれている 0，1 の列はchild, following-sibling によって選択されるノード集

bit 列であるとする．

合は，それぞれ ancestor, preceding, descendant, fol-

2. 4. 1 DO-VLEI コードの構成要素

lowing によって選択されるノード集合のサブセット

DO-VLEI コードは「.」と「1」と「0」の三つの記である．これに対してラベル付け手法による XML 文号から構成される文字列である．そして，三つの記号

書格納では各ノードに付加されたラベルが構造の情から構成される文字列が DO-VLEI コードであるため報を保持しており，この情報を利用することによっにはいくつかの条件が存在する．

て XPath の軸によるクエリに対する応答を行う．各（ 1 ）「.」は連続しない．

ノードが圧縮 bit 列 DO-VLEI を用いてラベル付け（ 2 ）「.」がラベルの末尾にあることはない．

されている場合，すべてのコードを DO-VLEI コー（ 3 ） VLEI コードは「1」で始まる．

ドにすることによってクエリの処理を行うことが可条件 (1)〜(3) から「.」の後には必ず VLEI コードの能であるが，すべての圧縮 bit 列 DO-VLEI コードを先頭の文字「1」が存在する．ゆえに，DO-VLEI コー

DO-VLEI コードに読み替えるのは効率的ではない．

ドは「.1」と「1」と「0」の三つの記号から構成されそこで，DO-VLEI コードを意識せずに利用可能であると言い換えることができる．

る圧縮 bit 列 DO-VLEI コードの性質の説明をする．

これら三つの記号にビット列を割り当てることにより，圧縮 bit 列 DO-VLEI コードを生成する．
定義 3．圧縮 bit 列 DO-VLEI

2. 5. 1 圧縮 bit 列 DO-VLEI コードの Dewey Order に起因する性質
圧縮 bit 列 DO-VLEI における DO-VLEI コードか

DO-VLEI コードにおいて，「.1」を bit 列 (10) に，「1」

ら bit 列への変換では，DO-VLEI の構成要素を最小「0」を bit 列 (0) に変換したものを，を bit 列 (11) に，単位ごとに bit 列に変換を行っている．そのため，圧圧縮 bit 列 DO-VLEI コードと呼ぶ．

縮 bit 列 DO-VLEI コードは子ノードラベルが頭に親
ノードラベルを含むという，Dewey Order の性質を保三つの記号「.1」「1」「0」それぞれに，語頭符号 [12]となる bit 列 (10)，(11)，(0) を割り当て，符号化する．図 2 の XML 木に圧縮 bit 列 DO-VLEI を示す．

2. 5 XML のノード情報取得と軸先述したとおり，XML 文書の構造に対するクエリ記
述手法として XPath の軸 (axis) を利用しながら問合せを記述する方法がある．軸とは XPath において，選持している．具体的には，あるノードのラベルがそのノードの親ノードのラベルの右にデリミタとなる「.1」を表す記号と兄弟番号を示す VLEI コードを加えたものになっている．そのため，各ラベルから次の三つの情報を取得可能である．

DO-1 ノードの深さDO-2 親ノードのラベル

択するノードとコンテクストノードとの間の木構造関797

電子情報通信学会論文誌 2010/6 Vol. J93–D No. 6
表 2 ビット操作の表記
Table 2 Bit operation notation.
表記
xy
u
xy
x
x&y
x|y

説明
左シフト
右シフト（論理シフト）
ビット単位の否定
ビット単位の積
ビット単位の和

図3

圧縮 bit 列 DO-VLEI コードの数直線
ancestor, preceding, decendant, following
Fig. 3 Code range for ancestor, preceding,decendant, following.

Algorithm 1とする．

圧縮 bit 列 DO-VLEI コードの大小比較

また，ある圧縮 bit 列 DO-VLEI コード a の child

入力: 圧縮 bit 列 DO-VLEI コード v,w(length(v)≤length(w))
出力: v が w より大きいかどうか
1: l ← length(w) − length(v)

2: v ← v · 1 · {0}ノードの圧縮 bit 列 DO-VLEI コードは a·10·{11|0}∗である．よって，圧縮 bit 列 DO-VLEI コード a の

decendant ノードの圧縮 bit 列 DO-VLEI コード b は

l −1



3: if v ≥ w thena · 10 · {0}∗ v b v a · 10 · {1}∗ となる．更に最右辺にreturn true
5: else6:
return false
7: end if
4:

1 を足すと，最後の 1 が何個続いているかにかかわらず
a·11·{0}∗ となるので a·10·{0}∗ v b ≺v a·11·{0}∗となり，すなわちa <CDV b <CDV a · 1

DO-3 祖先ノードのラベル
Dewey Order ラベルの構成方法から，親ノードのラベルはラベルから最後に出現するデリミタ以降を削除することで得られる．祖先ノードは親ノードを再帰的に得ることによって漏れなく得ることが可能である．
更に，深さは祖先ノードの数がそれに当たる．

2. 5. 2 圧縮 bit 列 DO-VLEI コードの数値比較による性質
圧縮 bit 列 DO-VLEI コードでは DO-VLEI コー
ドの構成要素である「.1」「0」「1」にそれぞれ bit 列を割り当てることによって DO-VLEI コードを bit 列で表現しているので，これを「0」= v0 ，「.1」= vd ，「1」= v1 と表すとする．このとき，

1 · v0 ≺v 1 ≺v 1 · vd ≺v 1 · v1

(2)

である．ここで <CDV は Algorithm 1 を用いた大小比較の結果である．
以上の数値比較による性質をまとめると図 3 のよ
うになり，XML 文書のラベルを，カレントノードの
ラベル a と a · 1 を用いて，I ancestor∪preceding，IIdescendant，III following，の三つの範囲に分けることができる．

3. 関 連 研 究
圧縮 bit 列 DO-VLEI と同様に，他ノードのラベルを付け替えることなく無制限にノードの挿入を行う
ことのできるラベル付け手法として，素数を用いた手(1)

法 [14] や Dewey Order を用いた手法 [15]〜[17] などが提案されている．本論文ではラベルの性能比較実験が成り立つならば Algorithm 1 を用いて圧縮 bit 列の比較対象としてよく用いられる ORDPATH を比較

DO-VLEI コードを大小比較をすることにより，昇順

対象とする．

が XML 文書における文書順と等しくなる．これはす

ORDPATH は内部では 0,1 の bit 列で表現され

なわち，ある圧縮 bit 列 DO-VLEI コードがあったとる．これを圧縮 bit 列 ORDPATH(Compressed-bit-

きに，それより大きい圧縮 bit 列 DO-VLEI コードのstring ORDPATH) と呼ぶこととする．圧縮 bit 列

ノードは descendant 若しくは following のどちらか

ORDPATH では表 3 の接頭辞符号化スキームを用いに属するノードであり，同様に小さいとされたノードて，整数を bit 列に変換する．

は ancesotor 若しくは preceding に属するノードである．証明は [13] を参照されたい．

圧縮 bit 列 ORDPATH では一つの整数を表すために，一組の bit 列コンポーネント Li -Oi を用いる．i

なお，アルゴリズム中で出現するビット操作は表 2

はデリミタで区切られた整数のラベル中における順番のようになっている．以降，v0 = 0, vd = 10, v1 = 11

である．Li は頭から逐次解析することで決定する bit798

論文／更新処理を考慮した XML ラベルにおける構造情報の抽出手法
表 3

圧縮 bit 列 ORDPATH で用いる接頭辞符号化ス
キーム
Table 3 Preﬁx encoding scheme for compressed-bitstring ORDPATH.
Li Bitstring

Oi length

Oi value range

000000001

20[-1118485, -69910]

00000001

16[-69909, -4374]

000000112[-4373, -278]

0000018[-277, -22]

00001

4

[-21, -6]0001

2[-5, -2]001

1[-1, 0]01

0[1, 1]

10

1[2, 3]

110

2[4, 7]

1110

4[8, 23]11110

8[24, 279]

11111012[280, 4375]

111111016[4376, 69911]

11111110

20[699912, 1118487]

図 4 圧 縮 bit 列 DO-VLEI コ ー ド の 数 直 線 parent,
preceding-sibling, child, following-sibling
Fig. 4 Code range for parent, preceding-sibling,child, following-sibling.
表 4 圧縮 bit 列 DO-VLEI コードによる各軸に対応するノード集合の取得方法
Table 4 XPath axis extraction methods.
軸
ancestor
precedingdecendant
followingparentpreceding-sibling

列であり，続く Oi の bit 数と整数の範囲を接頭辞符号化スキームにより決定する．そして Oi は Li によっ

childて指定される範囲の数を 2 進数によって表すことでラ

following-shibling

ベルサイズの圧縮を行っている．

圧縮 bit 列 DO-VLEI コードによるノー
ドラベル取得方法
DO-3 を用いる（範囲 III の集合） - ancestor
範囲 II の集合
範囲 III の集合
DO-2 を用いる
ノードの範囲 II∩ 範囲 I∩ 深さがカレントノードと同じ
範囲 II∩ 深さがカレントノードの深さ +1 のノード
親ノードの範囲 II∩ 範囲 III∩ 深さがカレン
トノードと同じ

圧縮 bit 列 ORDPATH は圧縮 bit 列 DO-VLEI と同様に Dewey Order による性質と数値比較による性が表すノード集合を除外すればよい．

質を利用することができるものの，コード化の方式が次 に parent, preceding-sibling, child, following-

異なることにより，DO-1〜DO-3 の判定アルゴリズ

shibling が表すノード集合を取得する方法について

ムが異なる．詳しくは [15] を参照されたい．

4. 圧縮 bit 列 DO-VLEI による XPath
処理

説明する．これらがが表すノード集合はそれぞれ an-

cestor, preceding, decendant, following が表すノード集合のサブセットである．このうち parent が表すノード集合は DO-2 で得ることができることを既に

まず，XML 文書を四つに分割する ancestor, preced-

説明している．カレントノードとその parent が表す

ing, decendant, following のノード集合を取得する処

ノード集合のラベルを用いて他の三つの軸が表すノー理について説明し，そのあとにそれぞれのサブセットとド集合を圧縮 bit 列 DO-VLEI コードの数直線上になるノード集合を取得する parent, preceding-sibling,表すと図 4 のようになる．更に，following-sibling，

child, following-sibling について説明する．

preceding-sibling が表すノード集合はカレントノード

図 3 が示すとおり数値比較により XML 文書をと深さが同じであり，child が表すノード集合はカレ

I〜III の三つの範囲に分けることが可能である．II

ントノードより深さが 1 大きい．これらをまとめるとの範囲にあるノードすべてを求めることで descen-

表 4 の最右欄のようになる．

dant が表すノード集合を得ることが可能であり，III

5. 構造情報抽出手法の範囲にあるノードすべてを求めることで following が表すノード集合を得る．一方，I の範囲にあるノード集

2. 5. 1 で述べた DO-1〜DO-3 の情報を圧縮 bit

合は ancestor∪preceding であるためこの二つを分離

列 DO-VLEI コードから抽出する手法を説明する．

する必要がある．ここで，DO-3 の性質から ancestor

Dewey Order では各ノードのラベル構造は（親ノードノードのラベルはカレントノードのラベルから生成がラベル）·（デリミタ）·（兄弟番号）のようになってお可能である．よって，preceding が表すノード集合を求り，圧縮 bit 列 DO-VLEI コードで DO-1〜DO-3 のめる場合は I の範囲にあるノード集合のうち ancestor

情報を抽出する際に，デリミタの位置や数を知ること
799

電子情報通信学会論文誌 2010/6 Vol. J93–D No. 6

Fig. 5図 5 圧縮 bit 列 DO-VLEI コードの例
An example fragment of a compressed-bitstring DO-VLEI code.

図 6 圧縮 bit 列 DO-VLEI コードと endPointOfOneの加算
Fig. 6 An example of delimiter detection.

が重要になる．ここで，圧縮 bit 列 DO-VLEI コード

Algorithm 2は語頭符号により bit 列化されている．よって，コー

圧縮 bit 列 DO-VLEI によるデリミタ判定

ドを頭から逐次読み込むことにより復号可能であり，デリミタとなる記号「.1」に割り当てられているビット列 (10) が出現する場所を検出することができる．しかし，この方法ではラベルの長さが長くなったときに非常に効率が悪い．そこで，レジスタ長の bit 列を一

入力: 圧縮 bit 列 DO-VLEI コード v
出力: v の深さ
1: endPointOfOne ← v&v  1
2: delimiterEven ←v&(v+(endPointOfOne&0x5555))&0xAAAA
u
3: v  ← v 1u
4: endPointOfOne ← endPointOfOne 1
5: delimiterOdd ←v &(v + (endPointOfOne &0x5555))&0xAAAA
6: delimiter ← delimiterEven|delimiterOdd

斉に処理し，デリミタの位置を調べる方法を示す．
まずはじめに，bit 列の中でどのようなところがデリミタになっているのかを考察する．デリミタに対応

うに，ビット列中に存在する 1 の列の最後の 1 のとこするビット列は (10) であるため，左から読んだとき

ろに 1 を足すと繰り上がりによって影響が伝搬され，に (1) から (0) に変わる場所がデリミタの候補となる．

1 の列の一つ左の 0 が 1 になることを利用している．

しかし，DO-VLEI コードで「10」とならんでいるとなお，endPointOfOne は x&x  1 とすることで得きのビット列も (110) となり，(10) が出現する．このることができる．

二つを見分けるために (1) がいくつ並んだあとに (0)ここで，1 を足した場所からその足した影響で 0 がが出てくるかに着目する．具体的には図 5 のように，

1 になった場所までの距離が奇数であれば 1 が奇数個

(1) が奇数個並んだあとに (0) が出てきた場合は最後並んでいることになる．更にこれを場合分けすると，の bit 列 (10) はデリミタを表し，偶数個並んだあとはビット列を頭から 0, 1 · · · と番号付けしたときにデリミタではなく「10」である．よって，ビット列の（ 1 ） 奇数番で足したときは偶数番が 0 から 1 に中で 1 が奇数個並んでいる箇所を数えることによって変化

深さを調べることができる．
本章では以降簡単のため，圧縮 bit 列 DO-VLEI
コードは 2 Byte 以下の bit 列とし，2 Byte の固定長

（ 2 ） 偶数番で足したときは奇数番で 0 から 1 に変化の二つのときに 1 が奇数個並んでいるといえる．ビッ

bit 列として格納されているとする．なお，今回実験

ト列全体で奇数番目の箇所だけで足したときは，0 かで用いる実装では，レジスタ長ごとに bit 列を分けてら 1 に変化した箇所のうち偶数番目の箇所を抽出す計算を行っている．

る．同様に偶数番目のときも行うことですべての 1

5. 1 深 さ 判 定の列を検査することができる．なお，奇数番目，偶まず圧縮 bit 列 DO-VLEI コードを用いた深さ判定

数番目の 1 のみを抽出するためにはそれぞれ即値での方法を説明する．次の二つのステップで調べる．

D-1 奇数個 1 が並んでる箇所の数分ビットが ONになっているビット列を生成

D-2 ビット列の中で ON になってるビット数を数

0x5555, 0xAAAA と AND をとることで実現可能であり，0 から 1 に変化した箇所は before&after とする
ことで得ることができる．

D-2 次にビット列の中で ON になっているビット

える

数を数えるアルゴリズムである Algorithm 3 を説明

以下で D-1，D-2 の説明をする．

する．この問題に対しては分割統治法を用いたアルゴ

D-1 奇数個ならんでいる箇所の数だけビット数がリズムを利用する．まずビット列を 2 ビットごとに区ON になっているビット列をつくるアルゴリズムを切り，その中での ON になっているビット数を数え，Algorithm 2 に示す．このアルゴリズムでは図 6 のよ

もとの 2 ビットの中に格納する，次に 2 ビットの区

800

論文／更新処理を考慮した XML ラベルにおける構造情報の抽出手法

Algorithm 4
先頭から続く 1 の長さ判定

Fig. 7図 7 label と pointOfDelimiter の例
An example label and pointOfDelimiter.

入力: v (16 bit unsigned integer)
出力: 頭から続く 1 の数
1: v ←v
2: n ← 16
3: c ← 8
4: repeatu

Algorithm 35:x ← v c

ON ビット数のカウント

6:

if x = 0 then7:n ← n−c

入力: v (16 bit unsigned integer)
出力: v 中の ON ビットの数
u1: v ← v − ((v 1)&0x5555)
u
2: v ← (v&0x3333) + ((v 2)&0x3333)
u
3: v ← ((v + (v 4))&0x0F0F)
u
4: v ← v + (v 8)u5: v ← v + (v 16)
6: depth ← v&0x001F
7: return depth

8:

v ← x

9:

end if10:c ← c 1u

11: until c = 0
12: return n − x

る．これを反転させることによって最右の 1 を含むそれより左のビットがすべて 1 となる．更にこのビット切り二つ分の数値を足し合わせて 4 ビットの中で ON

列ともとのラベルと OR を取ることにより，最右のデになっている数を求める．これを繰り返すことによっリミタの箇所までが 1 で，そこで初めて 0 が出現するて全体で ON になっているビット数を数える．詳細

bit 列を得ることができる．

は [18] を参照されたい．

P-3 次のステップでは先頭から続く 1 の数を数える

5. 2 親ノードラベルを生成する関数

ことにより，親ノードラベルの長さを得る．アルゴリ

親ノードラベルを得るためには最後のデリミタの場

ズムの例を Algorthm 4 に示す．このアルゴリズムで所を知る必要がある．ここで，深さを調べる際の最初はレジスタ長に対する二分探索法を用いている．レジのステップで Algorithm 2 を用いて生成したビット列

スタ長を固定とすることでループを排除し，より高速（以降 pointOfDelimiter とする）を用いることを考えなアルゴリズムとすることが可能である．詳細は [18]る．最後のデリミタの影響によって pointOfDelimiterを参照されたい．

で ON になるビットは右から左へ見たときに最初に出現する ON ビットである．この ON ビットが i 番目のビットだったとするともとのラベルで i + 1 番目から

5. 3 祖先ノードラベルを生成する関数
祖先ノードラベルは親ノードラベルを再帰的に計算することにより得ることができる．Algorithm 2 に始まる 1 の列の最後の 1 と続く 0 がデリミタである．

よって得られた pointOfDelimiter を x&(x − 1) とす

ここが何番目かを知るために次のステップを用いる．

ることにより，最右の 1 が 0 になるので，これを利用

P-1 奇数個 1 が並んでる箇所の数分ビットが ON にし，前節の P-2，P-3 を繰り返す．

なっているビット列を生成

P-2 左から読んだときにデリミタの箇所で初めて 0

6. 実装と実験が出現するビット列を生成

2.〜4. で述べたとおり，圧縮 bit 列 ORDPATH は

P-3 頭から続く 1 の数を数える

圧縮 bit 列 DO-VLEI と同様に Dewey Order による最初のステップは深さを調べる際と同様なのでここで性質と数値比較による性質を利用することができ，このは省略する．

二つの性質の組合せにより，XPath の軸が表すノード

P-2 最初のステップでは図 7 の mask を作る．

集合を得る処理を網羅できる．圧縮 bit 列 ORDPATH(pointOfDelimiter& − pointOfDelimiter) − 1|labelと圧縮 bit 列 DO-VLEI の XPath 処理において異なとすることで得ることができる．x& − x とすること

DO-3 の判定アルゴリズムである．深さ及び親ノーで x の中で最右の 1 のみを抽出可能であり，これからドラベル判定においては圧縮 bit 列 DO-VLEI がラベ

1 を引くことで最右の 1 より右のビットのみが 1 とな

ルの深さによらず一定の実行速度となる一方，圧縮る点は，Dewey Order に起因する性質である DO-1〜

801

電子情報通信学会論文誌 2010/6 Vol. J93–D No. 6
表 6 XML 文書一覧
Table 6 XML documents.
size (byte)elements

max-depth

avg-depth

max-fanout

avg-fanout

SwissProt.xml

114820211

297703153.556711

50000

2.034511

dblp.xml

133862772

3332130

62.902279

3288581.943555

ebay.xml

35525

156

5

3.75641380

5.391305

item0.xml (xmlgen SF=1)118552713

166631512

5.547796

25500

2.10692

item1.xml (xmlgen SF=0.1)

11875066

16786512

5.5482442550

2.103751

item2.xml (xmlgen SF=0.01)

118254717132

125.506012

255

2.102092

item3.xml (xmlgen SF=0.001)

1182741729

12

5.717756

25

2.04965

lineitem.xml

32295475

10229763

2.941175

60175

1.941175

nasa.xml

25050288

4766468

5.5831412435

2.000728

orders.xml

5378845

1500013

2.899987

15000

1.899987

part.xml

61818120001

32.899905

2000

1.899905

partsupp.xml

224186848001

32.833295

8000

1.833295

psd7003.xml

716853012

2130581875.15147

2625261.818513

28361910546

43.199791

703

1.809579

treebank e.xml

86082517

243766636

7.872788

56384

1.571223

uwm.xml

233752266729

53.952435

2112

1.952276

wsu.xml

164786474557

43.157866

3924

2.077534

reed.xml

bit 列 ORDPATH はラベルの深さによって実行速度が

表 5 実験システムの構成
Table 5 Experimental environment.

遅くなる性質がある．そこで，圧縮 bit 列 DO-VLEI
コードと圧縮 bit 列 ORDPATH コードのラベルの深さ，親ノードラベル，祖先ノードラベル判定の実行速度比較し，圧縮 bit 列 DO-VLEI の優位性を示す．

6. 1 実装圧縮 bit 列 DO-VLEI を用いて RDB に XML 文書を格納し，各ラベルから DO-1〜DO-3 の情報を抽CPU:
Memory:Dual-Core Intel Xeon 5110 (1.60 GHz)
DDR2 ECC FB-DIMM 9 GB (2 GB×4,
512 MB×2)
Storage:
D-RAID RAID 0 + 1
HDD:
SEAGATE ST3750640AS (750 GB, 7200 rpm,
3.5 inch)
OS:
Linux 2.6.18 CentOS 5 (Finlal)
Compiler: gcc (Red Hat 4.1.1-52)
RDB:
PostgreSQL 8.2.4

出できるよう，前節で説明したアルゴリズムをもとに実装を行った．RDB には PostgreSQL を利用し，ラベルは可変長 bit 列 (bit varying) で格納した．各情文書単位での実行速度と，ラベルの深さに起因する実報抽出手法は PostgreSQL のユーザ定義関数として C

行速度を明確にするために，文書ごとのテーブルと各言語による実装を行った．また，比較実験を行うため

ラベルの深さごとのテーブルを作成した．例えば深さに ORDPATH についても圧縮 bit 列 DO-VLEI 同様

1 のラベルを集めたテーブルには今回利用した XMLに各ラベルから深さ，親ノードラベル，祖先ノードラ

文書の深さ 1 のノードに付加されるラベルがすべて格

ベルを得られるようにした．

納されている．

6. 2 実験

なお，今回の実験においてはテーブルごとに実行時

5. で説明した関数の実行時間を測定し ORDPATH

間を計測した．例えば深さの実行時間を計測する際にと DO-VLEI の比較を行った．実験では，作成したは，ある一つのテーブルすべてのラベルに対し深さをXML 文書のラベルすべてに対し，深さ，親ノードラ

判定する時間を計測した．この場合，関数実行以外の

ベル，祖先ノードラベルを抽出する関数を実行し，実時間が含まれてしまうため，何も行わない関数をすべ

行時間を計測した．実験環境は表 5 のとおりである．

てのラベルに対して実行した時間も計測し，深さ判定

XMark [19] 用の XML 文書作成ツールである xml-

時間より引くことで深さ判定に必要な時間とした．

gen [20] によって作成した XML 文書と，XMLData

6. 3 実 験 結 果

Repository [21] の XML 文書を利用した．実際に実験実験結果は図 8，図 9 のグラフのようになった．なに使用した XML 文書の情報を表 6 に示す．これらのお，それぞれのグラフでは圧縮 bit 列 ORDPATH の

XML 文書を DO-VLEI 及び ORDPATH でラベル付値によって正規化している．

けを行い，ラベルのみを RDB に格納した．また，各802

図 8 はラベルの深さごとにすべてのラベルに対して

論文／更新処理を考慮した XML ラベルにおける構造情報の抽出手法

圧縮 bit 列 ORDPATH の処理時間の約 75%と 85%となった．一方 ancestor の結果は横軸を深さとしたとき同様圧縮 bit 列 ORDPATH と圧縮 bit 列 DO-VLEIの結果はほぼ同等である．今回は初期状態のラベルを用いて実験を行っているが，圧縮 bit 列 ORDPATH
において要素挿入が起こると深さより多くのビット列
コンポーネントを解析する必要があるため，更に性能が低下すると考えられる．
図8

圧縮 bit 列 ORDPATH を 1 としたときの圧縮 bit
列 DO-VLEI のクエリ実行時間（横軸：ラベルの深さ）
Fig. 8 Execution time ratio of compressed-bit-string
DO-VLEI to compressed-bit-string ORDPATH (horizontal axis: depth of node).

実験の結果，深さが深いノード程圧縮 bit 列 DO-

VLEI の方が性能がよく，平均で depth 及び parent の実行時間がそれぞれ圧縮 bit 列 ORDPATH の 75%と85%程度になることを確認できた．一方 ancestor に関しては圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH
であまり差が出なかった．

7. む す び
本論文では圧縮 bit 列 DO-VLEI を用いた XPath
処理方法を述べたあと，その際に必要な圧縮 bit 列

DO-VLEI から情報を抽出する手法を提案した．更に同様の処理が可能である ORDPATH と情報抽出処理の実行時間比較を行い，depth，parent の情報を抽出する操作において圧縮 bit 列 DO-VLEI を用いた場合
図9の方が圧縮 bit 列 ORDPATH を用いた場合に比べて圧縮 bit 列 ORDPATH を 1 としたときの圧縮 bit
列 DO-VLEI のクエリ実行時間（横軸：ドキュメ
ント）Fig. 9 Execution time ratio of compressed-bit-string
DO-VLEI to compressed-bit-string ORDPATH (horizontal axis: XML document).

示した．これは，圧縮 bit 列 ORDPATH においては処理を行ったときの実行時間である．このグラフでは，操作においては操作性能に違いはないことから XPath

ラベルの深さが深くなると圧縮 bit 列 DO-VLEI のの処理性能において圧縮 bit 列 DO-VLEI が圧縮 bit

depth 及び parent の結果が良くなっている．これは，

列 ORDPATH に対し優位であることを示した．

実行時間がそれぞれ 25%と 15%程度短くなることを
コードを頭から逐次解析する必要があるのに対し，圧縮 bit 列 DO-VLEI ではレジスタ長の bit 列を一斉に処理するためである．また，他の XPath に利用する

圧縮 bit 列 DO-VLEI の情報抽出アルゴリズムが深さ

今後，XPath の処理を実装し，ORDPATH 以外のによらず一定の処理時間で行えるのに対し，圧縮 bit

ラベル付け手法との実行時間比較を行う必要がある．

列 ORDPATH では接頭辞符号化スキームを用いていまた，今回は述べなかったが，偏った要素挿入が起こっるため，デリミタを知る際にコードの頭から逐次解析

た場合，ラベルが長くなってしまう可能性があるので，しなくてはならず，深さの分だけビット列コンポーネ

それに対する対策を考案する必要がある．

ント Li − Oi を読み取って偶数なのか奇数なのかを判

謝辞 本研究の一部は，文部科学省科学研究費補助

定しなくてはならないためである．一方 ancestor は

金特定領域研究 (19024028)，独立行政法人科学技術振すべての祖先ノードを深さの数だけ出力するため，圧興機構 CREST，及び東京工業大学 21 世紀 COE プ

縮 bit 列 ORDPATH と圧縮 bit 列 DO-VLEI の差がログラム「大規模知識資源の体系化と活用基盤構築」

あまり出ない．

の助成により行われた．
文

図 9 は各文書ごとにすべてのラベルに対して処理を行ったときの実行時間である．圧縮 bit 列 DO-VLEIにおける depth と parent の平均処理時間はそれぞれ[1]

献

I. Tatarinov, S.V.K.S. Beyer, J. Shanmugasundaram,
E.J. Shekita, and C. Zhang, “Storing and querying803

電子情報通信学会論文誌 2010/6 Vol. J93–D No. 6ordered XML using a relational database system,”
Proc. SIGMOD 2002, pp.204–215, 2002.
[2]

[3]
[4]

Professional, 2003.
[19]

江田毅晴，天笠俊之，吉川正俊，植村俊亮，“XML 木のための更新に強い節点ラベル付け手法，” DBSJ Letters,

A. Schmidt, F. Waas, M. Kersten, and D. Florescu,“The XML benchmark project,” Technical Report
INS-R0103, 2001.

vol.1, pp.35–38, 2002.

[20]

xmlgen. http://monetdb.cwi.nl/xml/downloads.html

P.F. Dietz, “Maintaining order in a linked list,” Proc.

[21]

XML Data Repository.

STOC1982, pp.122–127, 1982.

http://www.cs.washington.edu/research/

Online Computer Library Center. Introduction to thexmldatasets/.

Dewey Decimal Classiﬁcation. http://www.oclc.org/（平成 21 年 9 月 7 日受付，22 年 1 月 4 日再受付）

oclc/fp/about/about the ddc.htm[5]

T. Amagasa, M. Yoshikawa, and S. Uemura, “QRS:
A robust numbering scheme for XML documents,”
ICDE, pp.705–707, 2002.

[6]

E. Cohen, H. Kaplan, and T. Milo, “Labeling dynamic XML trees,” Proc. 21st ACM SIGMOD-

昭裕

Watanabe, and H. Yokota, “VLEI code: An eﬃcient

平 18 東工大・工・情報工学卒．平 20 同大大学院・情報理工・計算工・修士課程了．
現在（株）エヌ・ティ・ティ・データ．XML

labeling method for handling XML documents in an

インデキシングに関する研究に従事．

SIGACT-SIGART, pp.271–281, 2002.
[7]

高橋

K.

Kobayashi,W.

Liang,

D.

Kobayashi,A.

RDB,” Proc. ICDE2005, 2005.
[8]

[9]

長良香子，小林一仁，小林 大，横田治夫，“XML デー” 第 16 回電子
タベースのラベル付け手法 VLEI の評価，
情報通信学会データ工学ワークショップ (DEWS2005) 論文集，2005.
村上翔一，小林 大，横田治夫，“DO-VLEI を用いた
XML 格納におけるラベルサイズと問い合わせ性能，”
第 17 回 電 子 情 報 通 信 学 会 デ ー タ 工 学 ワ ー ク ショップ
(DEWS2006) 論文集，2006.

梁文新平 10 中国西安交通大・工・電子情報卒．
平 13 同大大学院・電子情報理工学研究科・修士課程了．平 18 東工大・大学院情報理工学研究科・博士課程了．CREST 研究員．

2009, LNCS 5690, pp.7–22. 2009.

東工大・特別研究員．平 21 中国大連理工大・准教授，現在に至る．博士（工学）．主として XML データベース，Web に関する情報検索，マルチメ
ディア等に関する研究に従事．日本データベース学会，IEEE，[11]

World Wide Web Consortium. XML path language.

ACM SIGMOD 各会員．

[12]

韓 太舜，小林欣吾，金谷文夫，山本博資，横尾英俊，鈴木譲，森田啓義，佐藤 創，伊藤秀一，情報源符号化無ひず[10]

W. Liang, A. Takahashi, and H. Yokota, “A lowstorage-consumption xml labeling method for eﬃcient structure information extraction,” Proc. DEXA

http://www.w3.org/TR/xpath, 1999.

[13]

みデータ圧縮，情報理論とその応用シリーズ 1-1，培風館，
1998.
高橋昭裕，梁 文新，横田治夫，“挿入によって他ラベル” 情処
変更を起こさない可変長 XML ラベルの容量評価，
学研報，DBS-143(17), pp.97–102, July 2007.

[14]

[15]

平 10 東工大・大学院情報理工・助教授．平

ICDE, pp.66–78, 2004.

情報理工学研究科教授，現在に至る．工博．主として分散イン

P. O’Neil, E. O’Neil, S. Pal, I. Cseri, G. Schaller,

デキシング，データ工学向けアーキテクチャ，高機能ストレー
ジシステム，ディペンダブルシステム等に関する研究に従事．
元本会データ工学研究専門委員会委員長．ACM SIGMOD 日

M.P. Haustein, T. Härder, C. Mathis, and M.
agement of XML documents,” SBBD, pp.85–99,
2005.
C. Li and T.W. Ling, “QED: A novel quaternary encoding to completely avoid re-labeling in XML updates,” Proc. CIKM2005, pp.501–508, 2005.

804

昭 55 東工大・工・電物卒．昭 57 同大大学院・情報・修士課程了．同年富士通（株）．
同年 6 月（財）新世代コンピュータ技術開発機構研究所 (ICOT)．昭 61（株）富士通研究所．平 4 北陸先端大・情報・助教授．
13 東工大・学術国際情報センター・教授，平 22 東工大大学院

Wagner, “Deweyids — The key to ﬁne-grained man-[18]

（正員：フェロー）labeling schema for dynamic ordered XML trees,”

node labels,” Proc. SIGMOD2004, pp.903–908, 2004.

[17]

治夫

X. Wu, M.L. Lee, and W. Hsu, “A prime number

and N. Westbury, “ORDPATHs: Insert-friendly XML
[16]

横田

Jr. Guy L Steele, Hacker’s Delight, Addison-Wesley

本支部長．日本データベース学会理事．情報処理学会フェロー．
人工知能学会，IEEE，ACM 各会員．