XMLデータの要約情報を用いた高速なXPath処理方法

江田 毅晴  鬼塚 真  山室 雅司  

誌名
電子情報通信学会論文誌 D   Vol.J89-D   No.2   pp.139-150
発行日: 2006/02/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (データ工学論文特集)
専門分野: 問合せ処理
キーワード: 
XML,  XPath,  XMLデータベース,  構造ジョイン,  

本文: PDF(443.9KB)
>>論文を購入


あらまし: 
XMLが普及したため,大量のXMLデータを扱うXMLデータベースのニーズが高まっている.XMLデータにおけるノード間の先祖子孫関係を判定可能な範囲ラベルを利用したXPath処理手法は,大規模XMLデータ検索の基盤手法として広く研究されている.本論文では,長いXPath問合せを構造ジョインを用いて処理する際に,構造ジョインが多段になり処理速度の低下を招く問題を回避する方法を提案する.提案手法では,XMLデータの要約情報であるストロングDataGuideを利用することにより,構造ジョインの回数を削減し,かつ一次記憶に読み出すノード数を削減することができる.シングルパス問合せ(XP(/,//,*))は構造ジョインを行うことなく,小枝パターン(XP(/,//,*,[]))の場合でも,問合せを木構造表現した際に分岐となるノードと葉ノード間の構造ジョインのみでXPathを処理することができる.評価実験の結果,111 MByteのXMLデータに対して既存の構造ジョインを用いた最適化手法と比較し,2から数百倍の高速化を達成した.