半構造XMLデータからのスキーマ抽出及び変換アルゴリズムの開発

本研究のスキーマ抽出は,構造の類似したXMLデータ同士を同じクラスに分類し,同じクラスに属するデータを共通の構造に変換する,という手順で行われる.これを実現するため,本研究では構造の異なる2個のXMLデータを同じ構造に変換(この処理を以下では併合と呼ぶ)するアルゴリズムの開発等を行った(このようなアルゴリズムが得られれば,クラスタリング的手法と本アルゴリズムを組み合わせることによりスキーマ抽出を行うことができる).本研究では,XMLデータをラベル付き順序木とみなす.前年度,報告者は2個のXMLデータを併合するためのアルゴリズムを構成したが,このアルゴリズムでは併合の際に用いる操作が(1)頂点の追加,(2)頂点の削除,(3)頂点のラベルの変更,という3種のものに限定されていた(各操作にはコストが付与される).今年度は,これら3種の操作に加えて(4)部分木の移動,という操作を追加した上で,2個のXMLデータを併合する問題について考察した.本研究で得られた結果は次の通りである.まず,2個のXMLデータおよび操作系列が与えられた場合に,その操作系列をXMLデータに適用して併合を行う多項式時間アルゴリズムを構成した.次に,2個のXMLデータおよび整数Kに対して,それらXMLデータがコストK以下で併合可能か否かを決定する問題がNP完全であることを示した.最後に,「部分木の移動」のコストが移動対象の頂点にのみ依存し,かつ,操作系列に含まれる「部分木の移動」操作の数がある定数以下に抑えられている場合,併合を行うための操作系列でコスト最小のものが多項式時間で得られることを示した.

本研究のスキーマ抽出は,構造の類似したXMLデータ同士を同じクラスに分類し,同じクラスに属するデータを共通の構造に変換する,という手順で行われる.これを実現するため,本研究では構造の異なる2個のXMLデータを同じ構造に変換(この処理を以下では併合と呼ぶ)するアルゴリズムの開発等を行った(このようなアルゴリズムが得られれば,クラスタリング的手法と本アルゴリズムを組み合わせることによりスキーマ抽出を行うことができる).本研究では,XMLデータをラベル付き順序木とみなす.前年度,報告者は2個のXMLデータを併合するためのアルゴリズムを構成したが,このアルゴリズムでは併合の際に用いる操作が(1)頂点の追加,(2)頂点の削除,(3)頂点のラベルの変更,という3種のものに限定されていた(各操作にはコストが付与される).今年度は,これら3種の操作に加えて(4)部分木の移動,という操作を追加した上で,2個のXMLデータを併合する問題について考察した.本研究で得られた結果は次の通りである.まず,2個のXMLデータおよび操作系列が与えられた場合に,その操作系列をXMLデータに適用して併合を行う多項式時間アルゴリズムを構成した.次に,2個のXMLデータおよび整数Kに対して,それらXMLデータがコストK以下で併合可能か否かを決定する問題がNP完全であることを示した.最後に,「部分木の移動」のコストが移動対象の頂点にのみ依存し,かつ,操作系列に含まれる「部分木の移動」操作の数がある定数以下に抑えられている場合,併合を行うための操作系列でコスト最小のものが多項式時間で得られることを示した.