IEICE TRANSACTIONS on Information
An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E93-D No.8 pp.2198-2212
- Publication Date
- 2010/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E93.D.2198
- Type of Manuscript
- PAPER
- Category
- Data Engineering, Web Information Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nobutaka SUZUKI, "An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 8, pp. 2198-2212, August 2010, doi: 10.1587/transinf.E93.D.2198.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.2198/_p
Copy
@ARTICLE{e93-d_8_2198,
author={Nobutaka SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD},
year={2010},
volume={E93-D},
number={8},
pages={2198-2212},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.2198},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - An Algorithm for Inferring K Optimum Transformations of XML Document from Update Script to DTD
T2 - IEICE TRANSACTIONS on Information
SP - 2198
EP - 2212
AU - Nobutaka SUZUKI
PY - 2010
DO - 10.1587/transinf.E93.D.2198
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2010
AB - 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.
ER -
English
