An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD

DOI 機関リポジトリ 機関リポジトリ (HANDLE) Web Site 参考文献23件 オープンアクセス
  • SUZUKI Nobutaka
    Graduate School of Library, Information and Media Studies, University of Tsukuba

この論文をさがす

説明

DTDs are continuously updated according to changes in the real world. Let t be an XML document valid against a DTD D, and suppose that D is updated by an update script s. In general, we cannot uniquely “infer” a transformation of t from s, i.e., we cannot uniquely determine the elements in t that should be deleted and/or the positions in t that new elements should be inserted into. In this paper, we consider inferring K optimum transformations of t from s so that a user finds the most desirable transformation more easily. We first show that the problem of inferring K optimum transformations of an XML document from an update script is NP-hard even if K = 1. Then, assuming that an update script is of length one, we show an algorithm for solving the problem, which runs in time polynomial of |D|, |t|, and K.

収録刊行物

参考文献 (23)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ