XML木のための動的範囲ラベル付け手法

IPSJ Web Site 1 Citations 24 References

Bibliographic Information

Other Title
  • XML キ ノ タメ ノ ドウテキ ハンイ ラベル ヅケ シュホウ
  • Dynamic Range Labeling for XML Trees

Search this article

Abstract

本論文は，動的XMLデータのための新しい節点ラベル付け手法について述べる．今日，範囲ラベル付け手法に基づく構造結合は，XML問合せ処理において最も重要な課題の1つと見なされている．XML木中のそれぞれの節点は，木の中での前置順と後置順の順序関係を保存した数の対でラベル付けされる．このラベルを利用すると，任意の節点間の先祖子孫関係が判定できるため，XML問合せ処理を効率的に行うことができる．しかしながら，XMLデータが更新されると，前置順，後置順それぞれの順序関係を保持するために，ラベルを付け直さなければならない．たとえ間隔を空けてラベル付けしたとしても，大量の挿入や大きなXMLデータの挿入があった場合には十分ではないと考えられる．頻繁に更新の起こる動的なXMLデータへの高速な問合せ処理を継続するためには，大規模なラベルの付け直しを避ける必要がある．そこで，本論文では大規模なラベル付け直しのコストを分散させ，小規模なラベルの付け直しでノードのラベルを維持する2つの動的節点ラベル付け手法を提案する．1つは簡単な小規模ラベル付け直し手法であり，もう1つは近似ヒストグラムを用いて更新操作の情報を保持する，より洗練された手法である．これらの2つの手法により，節点のラベルを動的かつ小規模に管理することができる．実験結果により，更新操作を続けていってもコストの高い大規模なラベルの付け直しを回避できることを示す．

This paper presents a new node labeling approach for data-oriented dynamic XML trees. Recently, structural joins based on range labeling schemes have been considered as one of the most important research topics for XML query processing. Each node in an XML tree is labeled with a pair of numbers which preserves the preorder and the postorder in the tree. The ancestor-descendant relationship between any two labeled nodes can be verified by using their labels; consequently, this property leads to efficient evaluation of XML queries. When an XML data set undergoes updating, however, the nodes have to be relabeled in order to keep their order relationships. Moreover, even if “gaps” are used in labels, the gaps may prove to be insufficient if there are many update operations or the insertion of a large XML tree is required. To avoid a “gap” shortfall, we propose two new dynamic node labeling schemes. One is simple local relabeling scheme and the other is more sophisticated in that it uses approximate histograms to keep approximated information of update operations. These two techniques allow node labels to be managed dynamically and locally. Experiments show that bulk relabeling, which is expensive, can be avoided while still permitting update operations.

Journal

Citations (1)*help

See more

References(24)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top