決定性線形下降木変換器における頂点問合せ保存
宮原 一喜 (1151104)
XMLはその柔軟性や拡張性の高さ，Webを介したデータ交換との高い親和性といった利点を持つことから，様々な情報を記述・記録するためのメタ言語として広く用いられている．XMLの文法に従うデータをXML文書と呼ぶが，一般にXML文書の構造を変更する際には，XML文書変換と呼ばれる操作が必要となる．具体的に，XML文書変換とは，あるスキーマに従うXML文書集合を他のスキーマに従う文書集合へ変換することをいう．データ交換やスキーマ更新などに伴って，XML文書変換がしばしば必要になるが，このような場合のXML文書変換においては，変換前の文書集合に含まれる必要な情報がその変換によって失われないことが望ましい．そのような情報保存の1つの定式化として，問合せ保存が提案されている．問合せとは，XML文書の一部またはすべてのデータを取り出す操作であり，問合せ保存とは，与えられた問合せの変換前文書に対する解集合と一致するような，変換後文書に対する解集合を持つ問合せが存在することをいう．
本研究では，問合せ保存問題が決定可能であるような変換クラスと問合せクラスの調査を行った．本発表ではその結果として，変換のクラスを決定性線形下降木変換器とし，問合せのクラスを受理実行n変数問合せとした場合に，問合せ保存問題が決定可能であることを示す．また，問合せが保存されるとき，変換後文書に対する問合せを構成するアルゴリズムを示す．さらに，変換クラスをより能力の高い先読み付き決定性線形下降木変換器とした場合にも問合せ保存問題は決定可能であることを示し，そのクラスを用いた場合の変換後文書への問合せ構築法を示す．