本発表では, XML木のための動的範囲ラベル付け手法について説明する.
大量のXMLデータを効率良く管理するため, XMLデータベースが 開発されてきた. データベースに格納されたデータを検索する ための問合せ言語も, 同時に開発及び標準化がすすんでいる. XMLデータはラベル付き順序木であるため, 木の経路をとらえる経路式 がそうした問合せ言語の中核を占める. ところが, パスの長さを任意とする経路式を実行するにはデータの全検索が 必要となり, ディスクに格納されたデータに対しては 高速に処理することができなかった. そこで, 全検索を避けるために 範囲ラベル付け手法が開発されてきた. 範囲ラベル付け手法では, データを格納する際に, XML木の全ての節点に順序木における前置順と後置順を保存 するラベルを付ける. このラベルは順序木の構造を保持するのに十分 であり, 任意の節点間の先祖子孫関係がラベルの比較のみで実現できる. これにより, パスの長さを任意とする経路式を全検索をせずに処理することができる.
一方, 大量のXMLデータを更新したいという要求があり, 問合せ言語も更新への対応が叫ばれている. しかしながら, 範囲ラベル付け手法のXMLの更新への対応は まだそれほど研究されていない. そこで本研究では, XMLデータの更新に対して動的にラベルを 管理する, 動的範囲ラベル付け手法を提案する. ラベルの配置を簡単なアルゴリズムにより, 更新の度に微調整 することにより, 大規模なラベルの付け直しを避けることができる. 数値シミュレーションの実験結果により, 更新箇所の 分布が一様の場合には, 大規模なラベルの付け直しを避けられる ことが分かった. また, 更新箇所が偏る場合でも, 挿入と 削除の頻度が同じ場合には大規模なラベルの付け直しを避ける ことができる.
そこで, 本研究ではさらに範囲ラベル付け手法をXMLデータの関係データベース への格納手法であるXRelへの適用について議論する. 元々のXRelに採用されていた, ファイル中での先頭からのバイト数の対を 利用したラベルを, 提案手法のラベルに置き換えることにより, 更新の 際の大規模なラベルの付け直しを回避する. また, バイト数を利用しないことにより, XMLファイルから 結果部分木を抽出することができないが, 逆に, 関係データベースに格納 された情報のみから, 結果部分木を構築する方法を開発した.