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

DO-VLEIを用いた XML 格納におけるラベルサイズと問い合わせ性能

Title(English)

The Label Size and Query Performance of XML Storage using the DOVLEI

著者(和文)

村上翔一, 小林大, 横田治夫

Authors(English)

Shoichi MURAKAMI, Dai KOBAYASHI, Haruo YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 7B-o2

発行日 / Pub. date

2006, 3

URL

http://search.ieice.org/

権利情報 / Copyright

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

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2006 7B-o2

DO-VLEI を用いた XML 格納におけるラベルサイズと問い合わせ性能

村上

翔一†

小林

大††

横田

治夫†††,††† 東京工業大学 工学部 情報工学科†† 東京工業大学 大学院 情報理工学研究科 計算工学専攻††† 東京工業大学 学術国際情報センター
E-mail: †sho@de.cs.titech.ac.jp, ††daik@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
あらまし

RDB に XML 文書を格納することで RDBMS の様々な機能が容易に利用可能となるため，XML 文書の各

ノード へラベル付けを行い，RDB へ格納するための手法が注目されている．単純な数値を用いたラベリング手法では，更新処理に伴い大規模なラベル付け替えが発生し ，更新コストが高くなる．我々は，更新コストを抑え無制限な挿入ができる VLEI コード と，一つのラベルで包含関係を表せる DeweyOrder とを組み合わせた DO-VLEI を提案し，更新処理と問い合わせ処理の向上を図ってきた．本稿では，DO-VLEI を用いて，ラベルサイズを縮小する手法と，問い合わせ処理性能を向上させる手法を提案する．そして提案手法を用いた DO-VLEI と，O’Neil らによって提案された同様の性質を持つ ORDPATH との比較評価を行い，ラベルの格納に必要な容量と，問い合わせ処理時間における実験結果を報告する．
キーワード

XML, 問い合わせ処理, 性能評価, ラベリング

The Label Size and Query Performance of XML Storage using the DO-VLEI††††††,††
Shoichi MURAKAMI , Dai KOBAYASHI , and Haruo YOKOTA† Department of Computer Science, Faculty of Engineering, Tokyo Institute of Technology†† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology††† Global Scientic Information & Computing Center, Tokyo Institute of Technology
E-mail: †sho@de.cs.titech.ac.jp, ††daik@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
Abstract Techniques labeling each node in an XML document are paid to attention, because various functions in
RDBMS can be used by storing the labeled XML document into an RDB. However, labels using simple numericalvalues make XML document update expensive by large-scale relabeling. We proposed the Variable Length Endless
Insertable (VLEI) code to reduce the update cost, and the DO-VLEI method by combining the VLEI code with
the Dewey Order method capable of expressing ancestor-descendant relationship by using a single label, to realize
efficient XML query processing. In this paper, we propose compression and filtering methods for the DO-VLEI
to reduce the size of labels and improve the query processing performance. We compare the label size and query
processing performance of the proposed methods with the ORDPATH, a similar method proposed by O’Neil. The
experimental results indicate that the DO-VLEI is superior to the ORDPATH for both the size and performance.
Key words XML, query processing, performance evaluation, labeling

1.

はじめに

大量の XML 文書を効率よく管理し，高速に検索するために，

RDB に格納する時に，この XML 文書の木構造を維持するための方法として，XML 文書の各ノード にラベルを割り当て，ラベルとノード をタプルとして格納する方法がある．ラベルの規XML 文書を RDB に格納する方法が注目されている [1]．XML

則性により，各ノード 間の包含関係や，ノード の XML 木にお文書は，タグによって表現された要素間に包含関係があり，一ける位置を判定することができる．

組のタグをノード として扱うことで木構造と見なすことができ

このようなラベル付け手法として，以前から前順後順法 [3]る [2]．図 1 に XML 文書を木構造とみなした XML 木を示す．

や Dewey Order [4] が提案されている．これらの手法を XML 木

Depth 0

BOOKElement nodeISBN

表 1 アルゴ リズム： 挿入要素のコード の決定

Text node

Depth 1SECTION

Attribute node

SECTION

アルゴ リズム InsertVLEI(vl , vr )入力: 挿入する要素の左側のコード vl ,Depth 2

TITEL Nobody… FIGURE

TITEL

All…

BOLD free…

右側のコード vr

CAPTION

Depth 3

love

図1

XML

(但し vl < vr )木

出力: 挿入された要素のコード vi
if length(vl ) <= length(vr )のノード に適用することで，ラベルにより XML 文書の木構造

vi = vr · 0を表現することが可能となる．しかし，それらのラベル付けに

else

単純な連続する整数を用いると，更新に伴って大規模なラベル

vi = vl · 1の付け替えが必要となる．このため，更新時のラベル付け替え

endifのコストを抑える手法として，浮動小数点数法 [5] や，範囲ラreturn vi

ベリング法 [6]，範囲ラベリング法を改良した更新に強い節点ラ
ベル付け手法 [2]，などが提案されている．浮動小数点数法 [5]では理論上は無制限に浮動小数を作り出せるが，コンピュータ
内部のレジスタで表現できる浮動小数には上限が存在するため，
この上限を超えれば大規模なラベルの付け替えが発生する．範
囲ラベリング法を改良した手法 [2] では，小規模なラベル付け
替えを頻繁に行うことで大規模なラベルの付け替えを防ぐが，ラベル付け替えが発生することには変わりがない．
このようなラベル付け替えが発生する問題に対して，我々は他ノード のラベルを変更することなく無制限に挿入することができる VLEI コード (Variable Length Endless Insertable code)と，VLEI コードを用いたラベル付け手法を提案し，更新・検索処理に関する改良を行ってきた [7]〜[9]．[7], [8] では VLEI コー
ド を前順後順法に適用した PP-VLEI と，Dewey Order に適用
し た DO-VLEI を提案し ，簡単な検索と挿入の実験によって，
PP-VLEI，DO-VLEI と，浮動小数点数法 [6]，範囲ラベリング法の改良手法 [2] との比較を行い，VLEI コード を用いたラベ
ル付け手法の有効性を示した．[9] では，包含関係の判定においサイズではなくラベル付けされたノード の深さを絞り込みに用いる手法を提案する．
本稿の構成は次の通りである．まず，2 節で従来の DO-VLEIについて説明し ，3 節では関連研究として DO-VLEI と同様な問題解決案として提案された手法について説明する．次に 4 節
では我々が新しく提案する圧縮 bit 列 DO-VLEI について説明する．そして 5 節では圧縮 bit 列 DO-VLEI のラベルサイズに関する効果を実験によって示す．さらに 6 節ではノード の存在する深さを利用した絞り込み手法を提案し ，7 節では提案手法を用いた絞り込みの効果を測定する．さらにラベルから深さを抽出する字句解析について言及し，実際に字句解析処理の時間を測定しその結果について報告する．最後に 8 節で総括を述べる．
2.

DO-VLEI

我々がこれまで提案してきた VLEI コード と，VLEI コードに Dewey Order を組み合わせた DO-VLEI について説明する．
2. 1

VLEI コード の定義

VLEI コードは 1 から始まる 0,1 の可変長 bit 列であり，特殊な大小関係を持つ．以下に VLEI コード の定義を示す．

て，DO-VLEI の子孫ノード のラベルに先祖ノード のラベルが含まれるために子孫ノード のラベルは必ず先祖ノード のラベルよりもラベルが長いという特徴を活用することで，検索処理の性能改善を行った．
このように，DO-VLEI を用いて更新・検索処理の向上を図っ

定義 1. VLEI コード
v を 1 から始まる {0,1} からなる bit 列とし，以下の大小関係を満足する場合に VLEI コード と呼ぶ．
v · 0 · {0|1}∗< v < v · 1 · {0|1}∗

たが，ラベルサイズに関しては対策を行っていない．DO-VLEIの子孫ノード のラベルが先祖ノード のラベルを含むという特徴

すなわち，あるラベル v に対して，右に 0 のつくものは v よりにより，XML 木において，深いところにあるノード ほど そのも小さく, 1 のつくものは v よりも大きい．

ラベルサイズ (ラベルの長さ) は大きくなる傾向にある．その結表 1 に示すアルゴ リズムにより，任意の 2 つの VLEI コード

果，ラベル格納に必要な記憶容量が増大し，ラベル処理の時間の間に存在する新しい VLEI コード を，無制限に作り出すことも増大するために大規模な XML 文書の処理性能が低下する．

ができる．証明は論文 [7] [8] を参照されたい．

なお，ノード の深さは「 XML 木のルートノード の深さを 0 としたがって，木構造において挿入されるノード のラベルを容し，子ノード の深さは親ノード の深さより 1 大きい」と定義す

易に求めることができ，また他ノード のラベルを付け替える必る．また，[9] で提案したラベルサイズによる絞り込み手法は，要がないため，更新コストの低いラベル付けが可能となる．

先祖子孫関係を示す包含関係に関する問い合わせを効率よく行
うための手法である．しかし，絞り込みに用いるラベルサイズ

2. 2

DO-VLEI

Dewey Order では，親ノード のラベルの末尾に，デリミタ (区が変動しやすく，安定した絞り込みを行うことができないとい

切り文字) と兄弟ノード 間の順序を表現するコード (兄弟コード )う問題がある．

とを加えて，子ノード のラベルを表現する．DO-VLEI では兄

本稿ではラベルサイズを縮小するために，DO-VLEI をデリミ

弟コードに VLEI コード を用いる．

タも含めた内部的な bit 列により表現する圧縮 bit 列 DO-VLEIを提案する．また，より安定した絞り込み手法として，ラベル

定義 2. DO-VLEI（ 1 ） root ノード の DO-VLEI を 1 とする．

表 2 圧縮 bit 列 ORDPATH で用いる接頭辞スキーマ（ 2 ） 兄弟ノード 間の順序を VLEI コード の大小関係で表し，
これを Cchild とする．このとき，親ノード の DO-VLEI を L parentとすると，
DO-VLEI = L parent . C childとなる．

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]

図 2 に DO-VLEI によってラベル付けされた XML 木を示す．

0001

2

[-5, -2]

DO-VLEI ラベルでは，特定ノード のラベルを接頭辞とした

001

1[-1, 0]

ラベルを探すことでそのノード の子孫ノード を探すことができ

01

0[1, 1]

る．また，ラベルの右から n 個目のデリミタから，デリミタを

10

1[2, 3]

含めた右側の文字列を除けば，n 番目の先祖ラベルが得られる．

110

2[4, 7]

1110

4[8, 23]11110

8[24, 279]

1.1

11111012[280, 4375]

SECTION

111111016[4376, 69911]

11111110

20[699912, 1118487]

1

BOOK

ISBN

1.10

SECTION

TITEL Nobody… FIGURE
1.10.101.10.1CAPTION

1.101.11

TITEL

All…

BOLD

free…

1.1.100

1.1.10 1.1.101

1.1.1

love

3.

ORDPATH におけるノード の挿入

ORDPATH は初期のラベル付けにおいて，正の奇数のみを用

1.1.101.1

図2

3. 2

いている．これは，負の整数や偶数を，後で XML 木に挿入が行われたときに用いるためである．また兄弟順を決定する兄弟

DO-VLEI ラベルによるラベル付け

コードは必ず奇数で終了する．例えば，1.3.1 と 1.3.3 の間に新関連研究

DO-VLEI 同様に，他ノード のラベルを付け替えることなく無制限にノード の挿入を行うことのできる，新しいラベル付け
手法がいくつか提案されている．素数を用いた手法 [10] は素数の積によってラベル付けを行い，挿入時には未使用の素数と親し く挿入されるノード の ORDPATH は 1.3.2 のあとに，1 を加えた，1.3.2.1 となる．
3. 3

圧縮 bit 列 ORDPATH

ORDPATH は内部では 0,1 の bit 列表現により実装される．こラベルの積をとることで新しいラベルを作る．そして素因数分

れを圧縮 bit 列 ORDPATH と呼ぶこととする．表 2 のような接解を行うことで，その先祖ラベルを抽出することができる．ま頭辞スキーマを用いて，整数を bit 列に変換する．一つの整数をた，O'Niel らによって提案された ORDPATH [11] では，Dewey
Order を基本に，初期のラベル付けには奇数を用いて，挿入には偶数を用いる．そして奇数と偶数の区別によって先祖ラベルを抽出する．本節では以下，ORDPATH について簡単に説明すは頭から逐次解析することで決定する bit 列であり，続く Oi の
bit 数と整数の範囲を接頭辞スキーマにより決定する．そしてOi は Li によって指定される範囲の数を 2 進数によって表す．例

る．詳しくは [11] を参照されたい．
3. 1

表すために，一組の bit 列コンポーネント Li -Oi を用いる．i はデリミタで区切られた整数のラベル中における順番である．Li

えば圧縮 bit 列 ORDPATH(0111001) は，表 2 の接頭辞スキーマ

ORDPATH の概要

ORDPATH は，DO-VLEI ラベルと同様に，他のラベルを付を用いた逐次解析により，(01,110-01) に分割され，表 2 の対応

け替えることなく挿入を無制限に行うことのできるラベル付けする Oi value range を基に「 1 」と「 5 」に変換されて ORDPATH

である．Dewey Order を基本とするため DO-VLEI 同様に，親「 1.5 」が得られる．

ノード の ORDPATH に，デリミタと兄弟コード を付け加えるこ

圧縮 bit 列 ORDPATH は bit 列を接頭辞スキーマに従って区とで，新しい ORDPATH を作ることができる．例えば，親ノー切ることで，デリミタを表現し，ラベルサイズの圧縮を行ってド の ORDPATH が 1.3 であるとき，1.3.1 や 1.3.7 はその子ノーいる．図 4 に，圧縮 bit 列 ORDPATH によるラベル付けの例を

ド であり，兄弟コードは 1 と 7 である．兄弟コード を比較する

示す．

と，1.3.1 の後に 1.3.7 があることが分かる．図 3 に ORDPATH

4.

圧縮 bit 列 DO-VLEI

Dewey Order を基にしたラベル付け手法では，扱う XML 文

によってラベル付けされた XML 木を示す．

書の規模が増すにつれ，ラベル表現のための格納容量が増加す
1

BOOK

ISBN

1.1

01

1.3

SECTIONBOOK

SECTION

ISBN

0101

01101

SECTION

TITEL

Nobody…

FIGURE

1.1.1

1.1.3

1.1.5

図3

CAPTION

TITEL

All…

BOLD

free…

1.3.1

1.3.3

1.3.5
All…
1.3.5.1

1.3.7

ORDPATH によるラベル付け

TITEL

Nobody…

FIGURE

0101010101101

010111001

SECTION
CAPTION

TITEL
0110101

All…

BOLD

free…

01101101 0110111001 0110111011
All…
011011100101

図 4 圧縮 bit 列 ORDPATH によるラベル付け

るため，ラベルサイズをできるだけ小さくすることが重要であ(11) と (10) にラベルサイズの差異はない．しかし，連続するる．我々が新しく提案する圧縮 bit 列 DO-VLEI は，ラベルが内(1) の数を数えることで DO-VLEI へ変換することなくデリミタ

部的に bit 列で表されることを利用し，DO-VLEI をデリミタもを抽出することができる．ゆえに「 .1 」に (11) を，「 1 」に (10)含めて全て bit 列によって表現することで，ラベルサイズの縮を割り当てる．図 5 に，圧縮 bit 列 DO-VLEI でラベル付けし小を行う．

た XML 木を示す．

4. 1

DO-VLEI の構成要素

5.

DO-VLEI は「 . 」と「 1 」と「 0 」の三つの記号から構成され

ラベルサイズ比較実験

圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH を用いて実際にる文字列である．そして，三つの記号から構成される文字列がXML 文書にラベル付けを行い RDB に格納する．ここでは，そDO-VLEI であるためにはいくつかの条件が存在する．

れぞれの手法によって付けられるラベルの長さの総和を求め，（ 1 ）「 . 」は連続しない．

比較する．

（ 2 ）「 . 」がラベルの末尾にあることはない．

5. 1（ 3 ） VLEI コードは「 1 」で始まる．
条件 (1)(2) から「 . 」の後には「 1 」か「 0 」が存在し ，条件 (3)から「 . 」の後には必ず VLEI コード の先頭の文字「 1 」が存在する．ゆえに，「 . 」と「 1 」をセットとして扱い，DO-VLEI は「 .1 」と「 1 」と「 0 」の三つの記号から構成されると言い換えることができる．
4. 2

使用する XML 文書のデータ構造

XMark [13] は XML 文書における代表的なベンチマークとして知られる．XMark 用の XML 文書生成プ ログラムである
xmlgen [14] から生成された XML 文書を実験に用いる．xmlgen

では文書の規模を表す scale factor を設定することで，構造の定まった任意の規模の XML 文書を生成できる．図 6 に，このXML 文書の基本的な構造を示す．scale factor を大きくすると，

圧縮 bit 列 DO-VLEI の定義

図 6 にある ∗ の付いた項目の数が増える．

以下に圧縮 bit 列 DO-VLEI の定義を示す．
site

定義 3. 圧縮 bit 列 DO-VLEI
DO-VLEI において，「 .1 」を bit 列 (11) に ，「 1 」を bit 列 (10)regions

people(africa,asia,...)

person*open_auctions

closed_auctions

catgraph

categoriesに，「 0 」を bit 列 (0) に変換したものを，圧縮 bit 列 DO-VLEI と
呼ぶ．

name

homepage profile

annotation

incomedescription

三つの記号「 .1 」
「 1」
「 0 」それぞれに，語頭符号 [12] となる
bit 列 (0)，(10)，(11) を割り当て，bit 列に符号化する．語頭符

closed_auction*

item*

price

category

itemref

description
edge

open_auction*

号は互いが互いの接頭辞 (語頭) とはならないため，任意の符号語から成る列に対して先頭から 1bit づつ逐次的に解析して

namelocation description
annotation

いくことで個々の符号語に一意に分離できる．したがって，分

特に符号語 (0) は，1bit で表現されるため，ラベルサイズをできる限り小さくするためにはもっとも出現頻度の高い記号に割り当てる必要がある．まず，挿入が行われると兄弟コード である VLEI コード の長さが増大し，デリミタの個数が増大することは少ないため，デリミタが含まれる記号「 .1 」の出現率は低いと考える．ゆえに (0) に割り当てる候補として「 .1 」は除外
する．insertVLEI アルゴ リズム (表 1) では，比較するラベルサ
イズが等しいときに「 0 」付け加えることになるため，挿入時には「 0 」の出現率が高くなると予想する．したがって「 0 」に(0) を割り当てることにする．

itemref

XMark で用いる auction.xml の構造

ラベル付け

XML 文書を DOM (Document Object Model) 木として取り込

み，要素ノード テーブル，属性ノード テーブル，テキストノー
ド テーブルの 3 種類のテーブルに分けて RDB に格納する．用
いる 3 種類のテーブルのスキーマは表 3 のようになる．ラベル
付けは XML 文書の要素ノード とテキストノードに対して行い，属性ノード へのラベル付けは行わない．一つの要素に付随する
複数の属性間には順番が存在しないため，どの要素に付随しているかのみが重要である．
圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH の 2 種類のラ
ベル付け手法によりラベル付けを行う．これらのラベル付け手法では，ルートノード のラベルを除く全てのラベルが，その親ラベルを接頭辞として持っているため，全てのラベルはルート

10

BOOK

図6
5. 2

次に，三つの記号にどの符号語を割り当てるかが問題となる．

initialdescription increase

離されたそれぞれの符号語を対応する記号に変換すれば一意の
DO-VLEI へと復元ができる．

bidderISBN

ノード のラベルを接頭辞として持つ．ゆえに，ルートノード の

10110

1011

SECTION

ラベルは省略する．実際に RDB に格納されるラベルの例とし

SECTIONて，図 1 の要素ノード BOLD につけるラベルを表 4 に挙げる．
TITEL Nobody… FIGURE
10110110 1011011

1011011110

CAPTION

TITEL

BOLD

free…

10111100 1011110 101111010

101111

All…

love
10111101011

図 5 圧縮 bit 列 DO-VLEI によるラベル付け

図 2〜5 を併せて参照されたい．
5. 3

挿入操作

挿入操作によるラベルサイズへの影響は重要であると考える．
挿入のパターンには次の 2 つのパターンを仮定する．(i) 兄弟

表3

RDB の各テーブルスキーマ

表5

要素ノード テーブルid

INTEGER

自分の idparentINTEGER

親要素ノード の id

label

TEXT

lengthINTEGER

5bit で表現可能なラベル

圧縮 bit 列 DO-VLEI 圧縮 bit 列 ORDPATH

ノード 固有のラベル
label の長さ (ラベルサイズ )depth

INTEGER

デリミタの数 (DO-VLEI), 奇数の数 (ORDPATH)

name

TEXT

要素名

(11000)=「 .1000 」(01100)=「 .1.2 」(01101)=「 .1.3 」(11010)=「 .101 」(10001)=「 .2.1 」(10101)=「 .3.1 」(11011)=「 .10.1 」(11000)=「 .4 」

(11001)=「 .5 」

(11100)=「 .110 」(11010)=「 .6 」

(11011)=「 .7 」

(11110)=「 .1.10 」

縮 bit 列 ORDPATH の 80%以下のラベルサイズであることが分

テキストノード テーブル

かる．圧縮 bit 列 ORDPATH が初期状態では偶数と負の整数にid

INTEGER

自分の idelementid

INTEGER

親要素ノード の id

label

TEXT

ノード 固有のラベル

lengthINTEGERlabel の長さ (ラベルサイズ )depth

INTEGER

デリミタの数 (DO-VLEI), 奇数の数 (ORDPATH)

ようになる．圧縮 bit 列 DO − VLEI では，5 個がラベルとして

content

TEXT

テキストの内容成立する．一方圧縮 bit 列 ORDPATH では 8 個がラベルとしてよるラベル付けを行わないために，特定のラベルサイズで表現できるラベルの数が少なくなり，全体のラベルサイズが増大するためと考える．例えば，5bit での表現可能ラベル数は表 5 の成立するが，このうち偶数を含むラベルは初期状態のラベル付

属性ノード テーブル
elementid

INTEGER

親要素ノード の id

けでは使われないため，実際に初期のラベル付けで使われるラ

name

TEXT

属性名

ベルは 4 個である．ラベルの数が一定であれば，そのラベルサ

value

TEXT

属性値

イズ比は 4:5 となると推察する．

表 4 実験で用いるラベル付けの例
ラベル付け手法

格納されるラベル

圧縮 bit 列 DO-VLEI

1111010(参考) DO-VLEI.1.101

圧縮 bit 列 ORDPAHT

10111001(参考) ORDPATH.3.5

挿入を行うと，徐々に圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH の比率が増大する．すなわち，挿入に対して圧縮 bit 列
DO-VLEI の方がラベルサイズの増加量が大きい．圧縮 bit 列
DO-VLEI では初期状態において，bit 数に対して最適なラベル

サイズを与えるようなラベル付けを施す．このとき，連続する兄弟ノード の一つおきに最長のラベルサイズを持つ兄弟ノード

順序の末尾に挿入する場合 (あるいは先頭に挿入する場合)．(ii)が存在する．全ての兄弟ノード 間に挿入を行うと，表 1 の挿入

兄弟間に均等に挿入する場合．

アルゴ リズムから必ず兄弟内の最長ラベルサイズよりも長いラ

さらにそれぞれのパターンに 2 つのパターンを仮定する．(a)ベルが付されたノードを挿入することになる．ゆえに，圧縮 bit

一つの要素ずつ挿入する場合．(b) 部分木の塊で挿入する場合．

列 DO-VLEI で挿入される部分木ルートノード のラベルは既存

本稿では (ii) のように兄弟間に均等に，かつ，(b) のように部の兄弟ノードらよりも必ず 1〜2bit 増大する．一方，圧縮 bit 列

分木の塊で挿入する場合を考える．このような挿入パターンが

ORDPATH では，初期状態で未使用の偶数や負の整数を用いた起こり得る実例としては，広くインターネット上で活用される

ラベルを挿入時に使うため，ラベルサイズの増加量は圧縮 bit

wiki [15] などがある．wiki は閲覧者が自由に情報を追加するこ

列 DO-VLEI と比較して小さい．

とのできるシステムであり，文書中に情報の追加が頻繁に行わ

図 7 に記してある挿入回数以降の，ラベルサイズ比率の変化れる．文書としての構造を維持するため，XML 文書の同じ 深が挿入回数に対して比例であると仮定して, ラベルサイズ比率

さに偏りなく挿入が行われやすい．

が 100%になるとき，すなわち，ラベルサイズが等し くなると

図 6 のようなデータ構造において，データの更新時には ∗ のきの挿入回数とデータ規模を試算した．結果を表 6 に示す．結ついている要素を追加するのが自然である．実験ではこれら ∗果から，実験に使用した scale factor において最小でも 59 回ののついた要素ノードをルートノードとした XML 文書を用意し，



これを部分木と見立て，部分木ごと挿入する．挿入される部分

 

木のルート要素名は，∗ のついたものと同じである．偏りの少てに挿入を行うことを，一回の挿入とみなす．例えば，item 要
素が 5 個並んでいれば，それぞれの item 要素間とその前後の計6 箇所それぞれに，item 要素をルートとする部分木を挿入する．
5. 4

ラベルサイズ比較実験結果

ratio of label size

ない挿入を実現するため，複数存在する ∗ のついたノード 間全




 

初期状態から挿入を何回か行った状態までのラベルサイズ総

和を測定した．図 7 は圧縮 bit 列 ORDPATH のラベルサイズを



100%としたときに，圧縮 bit 列 DO-VLEI のラベルサイズ比率















 



insertion countが挿入に伴いどのように変化するか表したグラフである．
初期状態 (挿入回数 0) においては圧縮 bit 列 DO-VLEI は圧

図7

挿入に伴うラベルサイズ比率の変化




 

 

 

 


 












表 6 ラベルサイズが等しくなるときの挿入回数とデータ規模
scale factor

CPU

AMD Opteron(tm) Processor 248 × 2

86

2.97 × 10

B (2.97 × 10

GB)

HDD

SEAGATE ST336607LC 37GB

0.001

73

1.46 × 10

B (1.46 × 10

GB)

Memory

6.1GB

0.01

59

3.21 × 10

B (3.21 × 10

GB)

OS

RedHat Linux 3.3.2-1

0.1

63

1.27 × 10

B (1.27 × 10

GB)

DBMS

PostgreSQL 7.3.4-RH

67

1.53 × 10

B (1.53 × 10

GB)

java

jdk1.5.0 05

0

0.3

30
27
25
26
27

21
18
16
17
18

挿入回数でデータ規模にして 32yotta byte にもなることが分かる．これは，現在のデータベースにおいて現実的なデータ規模ではないので，圧縮 bit 列 DO-VLEI は圧縮 bit 列 ORDPATH よりもラベルサイズが小さいと言える．

DO-VLEI では ，深さはデ リミタの個数に相当する．また，
ORDPATH では奇数の個数が深さに相当する．

深さによる絞込みのアルゴ リズムは以下の通りである．まず，
特定のノード A のラベルから深さ d を算出する．次に，ノード深さによる絞り込み

6.

表7 実験環境

挿入回数 データ規模

A の子かど うかを判別したい全ての候補ノード の位置する深さ

ラベルサイズによる絞り込み手法 [9] は，先祖子孫関係を示を調べ，d 以下のノード を，候補から除外する．最後に，残っす包含関係に関する問い合わせを効率よく行うための手法であた候補ノード のラベルと，ノード A のラベルとでマッチング判

るが，いくつかの欠点がある．それらの欠点を解決する手法と定を行い，ノード A の子孫ノード を決定する．

問い合わせ処理時間の比較実験

して，XML 木の各ノード の存在する深さに着目した絞り込み

7.

手法を提案する．

深さによる絞り込み手法は，まずラベルから深さを抽出し ，

ラベルサイズによる絞り込みの欠点

6. 1

次に深さを用いて絞り込む，という二段階構成になっている．

ラベルサイズによる絞り込み手法 [9] は，特定のノード A の

ここでは，最初に深さによる絞り込みの効果について，次にラ子孫ノード を求める問い合わせ処理における絞り込み手法であベルから深さを抽出する処理について，それぞれ検証する．
絞り込み処理時間の比較実験

る．絞り込みを行わない場合，全てのノードに対して，特定の7. 1

ノード A の子孫であるかをラベル同士のマッチングにより判別

二つのラベル付け手法によってラベル付けされたデータに対する．ラベルサイズを用いた絞り込みでは，まずノード A のラ

して，三つの絞り込み手法により問い合わせ処理行い，その絞

ベルサイズ l を求め，l 以下のラベルサイズをもつノード を調り込みの効果を測定する．

査の対象から除外することで，マッチング判定の回数を減らし，
問い合わせ速度を向上させる．

7. 1. 1

実験準備

表 7 に実験環境を示す．使用するデータ，RDB のスキーマ，

しかしこの手法には特定のノード A においては効率的な絞挿入操作は 5 節と同様である．この実験では深さの絞り込み

り込みが行われないという欠点がある．XML 木において同じがどの程度の効果を得るかを測定するため，ラベルから深さを深さに存在するノード であっても，付されるラベルサイズは異抽出する処理を省き，表 3 に示す様に，深さを保持する RDB

なる．そして，特定のノード A のラベルサイズ l が短いとき，スキーマの属性をラベル付けを行う際に各タプルに持たせる．

そのノード の子孫ノードになりえない，同一の深さに存在するラベルから深さを抽出する処理については 7. 1. 2 節を参照され

ノード も，問い合わせ時の候補として挙げられる．また，挿入

たい．

を行うと，挿入されたノード のラベルは既にあるノード のラベ

6 節で述べたアルゴ リズムを表現した SQL を以下に示す．

ルよりも長い場合が多いため，同様の理由から挿入されたノー（ 1 ） 条件を満たす特定のノード A の深さを求める．

ドが候補として残ることが多くなる．さらに，特定のノードがCREATAE TABLE d AS

A1 ，A2 のように複数ある場合に，これらのノード のラベルサイ(SELECT depth FROM nodeTable WHERE 条件);ズ lA と lA が等し くなければ ，lA と lA のそれぞれを用いて
1

2

1

2

（ 2 ） d より深さが大きいノード を，子孫ノード 候補とする．

絞り込みの処理が行われるため，絞り込みの処理が 2 倍に増え

(深さが小さいものを候補から除外する)

る．lA ，lA のうち，短い方のみを絞り込みに用いると絞り込

CREATE TABLE candidate AS

1

2

み処理の回数は減るが，これによりもっとも短い l を選択する処理が発生する．
6. 2

深さによる絞り込み

このような問題を解決するため，XML 木中のノード の存在する深さを用いた手法を提案する．深さによる絞り込みでは，
ルート ノード の深さを 0 とし ，特定のノード A の深さを d と(SELECT ∗ FROM nodeTable WHERE depth > d);（ 3 ） マッチング判定を行う．
(ここでは部分文字列を使ったマッチング判定を用いる)
SELECT candidate.∗ FROM candidate,nodeTabel as parentNode
WHERE parentNode.label || '.'すると，深さ 0 から深さ d を含めた範囲に存在するノード を，= substring(candidate.label, 1, parentNode.legnth + 1);

確実に子孫ノード の候補から除外することができる．この手法

問い合わせ処理には XMark [13] で使用する 20 個のクエリを用いることで，包含関係を求める問い合わせにおいて，子孫セットの中から，上記の SQL に適合できるクエリを選び ，そノード の候補をより少なく絞り込むことができ，マッチング判のクエリを SQL に変換したものを用いる．

定の回数を減らすことができる．

表 8 初期状態における問い合わせ処理時間の平均値
単位 : ms
Query1

表9

3 回挿入を行った状態における問い合わせの処理時間の平均値

単位 : ms

scaling factor
0.001

0.01

0.1

0.3

Query1

scaling factor
0.001

0.01

0.1

0.3

non-

C-DO-VLEI

176

521

2056

5866

non-

C-DO-VLEI

464

1807

16866

51671

SelectC-ORDPATH

198

511

2076

6003

SelectC-ORDPATH

463

1827

16950

51806

by

C-DO-VLEI

220

534

2074

5999

by

C-DO-VLEI

450

1845

16981

52556

LengthC-ORDPATH

219

533

2087

6207

LengthC-ORDPATH

421

1885

17368

53062

by

C-DO-VLEI

232

517

1510

4066

by

C-DO-VLEI

410

1245

10907

32027

Depth

C-ORDPATH

232

538

1532

4103

Depth

C-ORDPATH

405

1248

11021

32400

Query5

Query5

未測定

non-

C-DO-VLEI

153

2180

192298(1)1700755(1)non-

C-DO-VLEI

2041

147552(1)14572182(1)SelectC-ORDPATH

158

2188

195300(1)1724641(1)SelectC-ORDPATH

2036

148901(1)14856354(1)byC-DO-VLEI

354

799

7561

38804

by

C-DO-VLEI

635

6134

222119(10)1721354(1)LengthC-ORDPATH

384

660

5714

33713

LengthC-ORDPATH

695

6501

251350(10)1953786(1)byC-DO-VLEI

391

625

4209

25932

by

C-DO-VLEI

445

1522

27765

190695(1)Depth

C-ORDPATH

388

614

4757

30144

Depth

C-ORDPATH

477

1587

32061

225197(1)Query6

未測定

Query6non-

C-DO-VLEI

180

353

954

2243

non-

C-DO-VLEI

212

806

6515

19094

SelectC-ORDPATH

185

339

975

2280

SelectC-ORDPATH

208

856

6592

19207

by

C-DO-VLEI

198

345

956

2286

by

C-DO-VLEI

200

856

6527

19200

LengthC-ORDPATH

201

355

959

2288

LengthC-ORDPATH

213

874

6570

19506

by

C-DO-VLEI

205

345

950

2269

by

C-DO-VLEI

230

828

6140

18089

Depth

C-ORDPATH

207

335

969

2320

Depth

C-ORDPATH

254

836

6137

18287

7. 1. 2

絞り込み処理時間の実験結果

また，Query1 では深さによる絞り込みにおいて，圧縮 bit 列

初期状態における実験結果を表 8 に，三回挿入を行った状

DO-VLEI と圧縮 bit 列 ORDPATH の差はなかった．ノード の深態における実験結果を表 9 に示す．基本的には 100 回の測定

さがど ちらの手法を用いても同じであるため，絞り込みの効果の平均値を取ったが ，複数回の測定において値のばらつきはが同程度であることが理由である．ところが Query5 では深さに少なかったため ，時間のかか るものは 測定回数を 減らし た．

よる絞り込みにおいて，scale factor が増すにつれて圧縮 bit 列

C-DO-VLEI が圧縮 bit 列 DO-VLEI，C-ORDPATH が圧縮 bit 列

DO-VLEI の方が圧縮 bit 列 ORDPATH より速くなった．scale

ORDPATH，non-Select が絞り込みを行わない状態での問い合わ

factor が 0.3 の時では圧縮 bit 列 ORDPATH の約 15% 速い．こせ，by Length がラベルサイズを用いた絞り込み手法，by Depth

れは大きなラベルサイズを扱う方が substring 関数などを扱う上が深さを用いた絞り込み手法である．なお，表 9 の Query5 にで効率が悪いことが一因と考える．
ラベル字句解析処理

おいて，scaling factor が 0.3 の non-Select の問い合わせ処理は

7. 2

時間がかかりすぎるため，今回は測定を行わなかった．

問い合わせ処理では深さによる絞りこみ手法において二つの表 8，表 9 の Query1，Query5 では，ラベルサイズによる絞り込みよりも深さによる絞り込みの方が処理が速い．深さによる絞り込みの方が値のばらつきが少ないため効果的に絞り込み

ラベル付け手法に有意な差は得られなかった．そこで，ラベルから深さを抽出するための字句解析処理について考える．
7. 2. 1

字句解析の要求を行うことができるためである．表 8 の Query6 では，絞り込

RDB に XML 文書を格納する際に，できるだけ格納に必要なみ手法による有意差は得られなかった．元々の問い合わせに存容量を小さくしたいという要求があるため，必要最小限の RDB在する子孫ノード の条件が，絞り込みによる候補削減よりも強スキーマが求められる．例えば，表 3 では要素ノード テーブル

い絞り込みを行っているために，ラベルサイズや深さの絞り込

が (id,parent,label,length,depth,name) という 5 つの属性を持ってみの効果がなかったと考える．しかし，挿入が行われた状態でいるが，label は一意の値をもつため ID の代わりになり，またある表 9 の Query6 では，ラベルサイズによる絞り込みに比べparent や length，depth は label から抽出できる内容である．ゆ

平均 7%の処理時間が削減されており，その効果が確認できる．

えに最小限の RDB スキーマを考えると (label, name) の二つの圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH を比較すると，属性があればよい．この状態で問い合わせを行うためには label

表 8 の Query5 では，ラベルサイズによる絞り込みで圧縮 bit 列を字句解析して depth などの値を抽出する必要がある．したがっORDPATH の方が平均 15% 速い．圧縮 bit 列 ORDPATH は接頭て，容量を極力抑えるような状況においては，字句解析にかか

辞スキーマ (表 2) にあるように定まった bit 長で値を表現する

る時間の差異が問い合わせ処理時間に影響すると考える．

部位があるためラベルサイズにばらつきが少ない．したがって，

7. 2. 2

絞り込みに用いる長さの個数が減り，結果として絞り込み処理

圧縮 bit 列 DO-VLEI ではデ リミタの数がそのノード の存在

圧縮 bit 列 DO-VLEI の深さ抽出の回数が減る．しかし ，表 9 では逆に圧縮 bit 列 DO-VLEI のする深さに相当する．そして，「 .1 」を表す (11) を，label から探方が速い．これは挿入操作によって，圧縮 bit 列 ORDPATH のし出すことでデリミタの数は求めることができる．

ラベルサイズにおけるばらつきが増加したことが一因であると

7. 2. 3考える．

圧縮 bit 列 ORDPATH では奇数の数が深さに相当する．以下

圧縮 bit 列 ORDPATH の深さ抽出表 10 RDB に収められたラベルから深さを求める処理時間
初期状態
単位：ms
scaling factor
C DO-VLEI (A)C ORDPATH (B)A / B × 100%

0.001

0.01

0.1

0.3

1.68

19.35

202.06549.05

2.78

26.99

299.22939.96

60.4%

71.7%

67.5%

63.2%

三回の挿入後場合は，圧縮 bit 列 DO-VLEI の方が優れていることを示した．
今後の課題として，素数を利用したラベリング手法 [10] などの挿入無制限なラベリング手法が他にも提案されているため，
これらの手法とも比較を行う必要がある．また，今回挿入パ
ターンは偏りなく行ったが，より広い事例に対応するために，現実的な使用環境で想定される挿入パターンにおいても検討を

単位：ms

C DO-VLEI (A)

20.02

193.022143.477031.31行う必要がある．また，今回は DOM によって XML 文書を取C ORDPATH (B)30.82

305.853282.5410537.91

り込んでいるため，scale factor 0.3 までの文書しか メモリ上にA / B × 100%

65.9%

63.1%

65.3%

66.7%

乗らなかった．そこで，DOM ではなく SAX による実装を行の手順によって label から奇数の数を求める．まず label の先頭から逐次的に解析を行い Li を算出する．続いて接頭辞スキー
マ (表 2) を用いて Oi の bit 長を決定する．Oi から一組の Li -Oi
が表す 10 進数の値を求める．最後に負の整数も考慮に入れて，2 乗してから 2 で割り，余りが 1 であれば奇数として数える．
7. 2. 4

深さを求める処理時間実験

い，より大規模な文書に対して挙動を確認する必要がある．

謝

辞本研究の一部は，文部科学省科学研究費補助金特定領域研究(16016232)，独立行政法人科学技術振興機構 CREST，および東京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」の助成により行われた．
文

先の実験と同様の実験環境で行った．圧縮 bit 列 DO-VLEI の
デリミタの数と，圧縮 bit 列 ORDPATH の奇数の数をそれぞれ[1]

sundaram, Eugene J. Shekita, and Chun Zhang. Storing and queryingの label 属性から抽出する処理時間を測定した．結果を表 10 に示す．結果から，深さを求める処理にかかる時間は，平均 35%，
圧縮 bit 列 DO-VLEI が速いことが分かった．これは，圧縮 bit

ordered xml using a relational database system. In Proc. of SIGMOD
Conf., pp. 204215, 2002.
[2]

列 ORDPATH をスキーマに照会する処理と，そこから得た 10進数の偶奇性判定が圧縮 bit 列 DO-VLEI には存在しないため，

122127, 1982.
[4]結http://www.oclc.org/oclc/fp/about/about the ddc.htm.
[5]707, 2002.
[6]のような Web 上の文書形式を更新することを想定し，XML 文

[7]

[9]

[10]

処理を行うときに深さを抽出するラベル字句解析を必要とする

Wynne Hsu Xiaodong Wu and, Mong Li Lee and. A prime number

Patrick O'Neil, Elizabeth O'Neil, Shankar Pal, Istvan Cseri, andceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, pp. 903908, 2004.
[12]

韓 太舜 , 小林欣吾 , 金谷文夫 , 山本博資 , 横尾英俊 , 鈴木譲 , 森
田啓義 , 佐藤創 , 伊藤秀一. 情報源符号化 無歪みデータ圧縮. 情
報理論とその応用シリーズ 1-1. 培風館, 1998.

[13]

Albrecht Schmidt, Florian Waas, Martin Kersten, and Daniela Florescu. The xml benchmark project. Technical report, Technical Re-のラベルからノード の深さを抽出する処理時間を測定・比較し平均 35% 処理にかかる時間が少なかった．ゆえに，問い合わせ小林一仁 , 横田治夫. 挿入制限のないコード vlei を用いた xml ラ
ベリング手法の検討とその評価. 第 15 回電子情報通信学会デー
タ工学ワークショップ (DEWS2004) 論文集, 2004.
長良香子 , 小林一仁 , 小林大 , 横田治夫. Xml データベースのラ
ベル付け手法 vlei の評価. 第 16 回電子情報通信学会データ工学
ワークショップ (DEWS2005) 論文集, 2005.

Gideon Schaller. Ordpaths:insert-friendly xml node labels. In Pro-縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH にほとんど 差が出たところ，圧縮 bit 列 DO-VLEI の方が圧縮 bit 列 ORDPATH の

Akitsugu

An efficient labeling

2004.
[11]

る絞り込みがラベルサイズによる絞り込みよりも絞り込みの効なかった．そこで圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATH

Dai Kobayashi,

Vlei code:labeling schema for dynamic ordered xml trees. In ICDE, pp. 6678,

り込みを適用し，処理時間を比較した．これにより，深さによ
果が高いことを示したが，また深さによる絞り込みにおいて圧Wenxin Liang,

method for handling xml documents in an rdb. In ICDE, 2005.
[8]

手法を提案した．圧縮 bit 列 DO-VLEI と圧縮 bit 列 ORDPATHの二手法に対して深さによる絞り込みとラベルサイズによる絞

Kazuhito Kobayashi,

Watanabe, and Haruo Yokota.

よりもラベルサイズが小さいということを示した．
また問い合わせ処理の向上を図るため，深さによる絞り込み

In Proceedings of the twenty-rst ACM SIGMOD-SIGACT-SIGART, pp. 271281, 2002.

書全体に偏りなく挿入を行った状態においても比較を行った．
その結果，現実的なデータ規模において圧縮 bit 列 ORDPATH

Edith Cohen, Haim Kaplan, and Tova Milo. Labeling dynamic xml
trees.

較を行い，初期のラベル付けにおいて圧縮 bit 列 ORDPATH の80%以下のラベルサイズを維持することを示した．さらに，wiki

In 19th In-

ternational Conference on Data Engineering (ICDE 2003), pp. 705

ラベルサイズの縮小を図った圧縮 bit 列 DO-VLEI を提案した．
同様に無制限な挿入を可能とする圧縮 bit 列 ORDPATH との比Toshiyuki Amagasa, Masatoshi Yoshikawa, and Shunsuke Uemura.
Qrs: A robust numbering scheme for xml documents.

論

挿入無制限なラベル付け手法である DO-VLEI を前提として，

Online Computer Library Center. Introduction to the dewey decimalclassication.

DO-VLEI は圧縮 bit 列 ORDPATH より優れている．

8.

Paul F. Dietz. Maintaining order in a linked list. In Proceedings ofthe fourteenth annual ACM symposium on Theory of computing, pp.

を行うことを前提とすれば，深さを得るためのラベル字句解析の処理コストの差により，問い合わせ処理において圧縮 bit 列

江田毅晴 , 天笠俊之 , 吉川正俊 , 植村俊亮. Xml 木のための更新に強い節点ラベル付け手法. In DBSJ Letters,No.1 in Vol.1,2002,
2002.

[3]

処理時間に差が出たと考える．
以上のことから，格納量を重視し，問い合わせ時に字句解析

献

Igor Tatarinov, Stratis Viglasand Kevin S. Beyer, Jayavel Shanmuga-

port INS-R0103, http://monetdb.cwi.nl/xml/index.html, April 2001.
[14]

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

[15]

B.Leuf and W.Cunningham. The Wiki Way:Quick Collaboration on
the Web. Addison-Wesley, 2001.