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

Search this Article

Abstract

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

Journal

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

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

Codes

  • NII Article ID (NAID)
    110009424989
  • NII NACSIS-CAT ID (NCID)
    AN10114171
  • Text Lang
    JPN
  • Article Type
    Technical Report
  • Data Source
    NII-ELS 
Page Top