An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD
-
- SUZUKI Nobutaka
- Graduate School of Library, Information and Media Studies, University of Tsukuba
Search this article
Description
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.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E93-D (8), 2198-2212, 2010
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390001204378715520
-
- NII Article ID
- 10027364764
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 2241/107914
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed