正規木文法間の差分抽出アルゴリズムの提案

• 堀江和磨

• 鈴木伸崇

抄録

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

収録刊行物

• 研究報告情報基礎とアクセス技術（IFAT）

  研究報告情報基礎とアクセス技術（IFAT） 2012 (12), 1-8, 2012-07-25

詳細情報

• CRID: 1572824502706779648
• NII論文ID: 110009424989
• NII書誌ID: AN10114171
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles