著者

SUZUKI Nobutaka

出版者

電子情報通信学会

雑誌

IEICE transactions on information and systems (ISSN:09168532)

巻号頁・発行日

vol.E93.D, no.8, pp.2198-2212, 2010-08

被引用文献数

1 3

---

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