The search functionality is under construction.
The search functionality is under construction.

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

Nobutaka SUZUKI

  • Full Text Views

    0

  • Cite this

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