The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -