木文法による圧縮XML文書に対する問合せと更新手法
尾上栄浩 (1351026)
XML文書は同じ構造が頻出することが多いため，様々な圧縮法が提案されている.
しかし，圧縮されたXML文書(以下，圧縮XML文書)に対して問合せや更新処理を行う際に，単純に圧縮XML文書を一旦，解凍して問合せを行うことは非常に非効率であるため，圧縮XML文書に対する問合せが可能な圧縮法も提案されている.
本発表では，Straight-line context-free tree grammar (SLCFTG)と呼ばれる木文法に基づく圧縮XML文書を対象とし，圧縮文書に対する問合せ・更新処理を，解凍を行わず効率的に行う手法を提案する.
問い合わせモデルには決定性ボトムアップ木オートマトン (DBTA)を用いる.
更新については，挿入，削除，タグ名の変更などの基本操作を与え，変更箇所の指定にDBTAを用いる.
提案手法を実装し，実際のXML文書に対して問合せを行った評価実験より，問合せは非圧縮のXML文書に対してDBTAを用いた問合せを行う場合と比較して，約2~270倍高速に動作し，最大メモリ使用量は67%-93%減少したことを示す.
また，更新操作が挿入，タグ名の変更の場合，実行効率は問合せの場合と同様，飛躍的に向上する一方で，文法サイズの増加を2%程度に抑えることができたが，
更新操作が削除の場合，圧縮率が高く更新箇所も多い場合は，文法のサイズが70%程度増加する場合もあったことを示す．