著者

堀江和磨 鈴木伸崇

雑誌

研究報告情報基礎とアクセス技術(IFAT)

巻号頁・発行日

vol.2012-IFAT-107, no.12, pp.1-8, 2012-07-25

---

XML は Web 上の標準的なデータ記述フォーマットとして広く普及している.XML データをデータベース等で継続的に蓄積・管理する場合,格納すべきデータの構造をスキーマで定義しておき,それに沿った構造のデータを作成・格納することが一般的である.利用状況の変化により格納すべきデータの構造や種類が変化するため,それに応じてスキーマ定義も更新されることが多い.その場合,スキーマの更新履歴の管理やスキーマの更新に応じた XML データの修正等が必要となるため,スキーマ間の差分抽出アルゴリズムが有用である.そこで本稿では,正規木文法のための差分抽出問題について考察し,同問題が計算困難であること,および,同問題が効率良く解けるための十分条件を示す.また,その十分条件の下で動作する多項式アルゴリズムを求め,このアルゴリズムに関する評価実験を行う.