正規木文法間の差分抽出アルゴリズムの提案
スポンサーリンク
概要
- 論文の詳細を見る
XML は Web 上の標準的なデータ記述フォーマットとして広く普及している.XML データをデータベース等で継続的に蓄積・管理する場合,格納すべきデータの構造をスキーマで定義しておき,それに沿った構造のデータを作成・格納することが一般的である.利用状況の変化により格納すべきデータの構造や種類が変化するため,それに応じてスキーマ定義も更新されることが多い.その場合,スキーマの更新履歴の管理やスキーマの更新に応じた XML データの修正等が必要となるため,スキーマ間の差分抽出アルゴリズムが有用である.そこで本稿では,正規木文法のための差分抽出問題について考察し,同問題が計算困難であること,および,同問題が効率良く解けるための十分条件を示す.また,その十分条件の下で動作する多項式アルゴリズムを求め,このアルゴリズムに関する評価実験を行う.
- 2012-07-25
著者
関連論文
- A-4-27 大規模ディジタルシステムのSTPNによるモデル化(A-4. ディジタル信号処理)
- D-10-14 メタステーブル動作を考慮したリングアービタのペトリネット表現
- 半構造データにおけるスキーマ抽出問題の計算複雑さ
- D-6-6 高速マルチウィンドウシステムのハードウエアアーキテクチャ
- オブジェクト指向データベースにおける逆行を含む属性集合とその閉包を用いた経路式を経由するクラスの一探索法
- グラフデータベースにおける正規表現及び文脈自由文法を満たす最短経路の一探索法
- 妥当でないXPath式に対するK最適修正候補発見アルゴリズム
- オブジェクト指向データベースにおける逆行を含む経路式の航行可能性に関する考察
- オブジェクト指向データモデルにおける逆行を含む経路式の航行可能性について (時空間データベースおよび一般)
- 1P-3 限定されたXPath構文に関する充足可能性問題について(XMLと応用,学生セッション,データベースとメディア)
- 正規木文法の差分抽出問題に関する研究
- 正規木文法の差分抽出問題に関する研究
- D-001 XPath式の部分クラスに対する充足可能性判定アルゴリズム(データベース,一般論文)
- XML文書と正規木文法との間の最適編集操作列の発見(DE: データ工学理論, データ工学とメディア理解との融合)
- XML文書と正規木文法との間の最適編集操作列の発見(DE: データ工学理論, データ工学とメディア理解との融合)
- 妥当でないXMLデータに関する最適な構造変換を求めるための一手法(インターネット環境のコンテンツ技術及び一般)
- 複合オブジェクトモデルにおける逆行を含む経路式に関する考察
- 部分木の移動を考慮した文書併合アルゴリズム
- 正規木文法間の差分抽出アルゴリズムの提案
- 正規木文法間の差分抽出アルゴリズムの提案
- オンライン目録検索システム構築演習の4年間とこれから
- 部分木の移動を考慮した文書併合アルゴリズム
- 構造化文書のための併合アルゴリズム
- オブジェクト指向データベースにおける逆行を含む属性集合及びその閉包を用いた経路式について (高度データベース論文特集)
- オブジェクト指向データモデルにおける逆行を含む経路式に関する考察
- 選択的継承の可能な複合オブジェクトモデルに関する考察