The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Os DTDs são continuamente atualizados de acordo com as mudanças no mundo real. Deixar t ser um documento XML válido em relação a um DTD D, e suponha que D é atualizado por um script de atualização s. Em geral, não podemos “inferir” de forma única uma transformação de t da s, ou seja, não podemos determinar exclusivamente os elementos em t que devem ser eliminados e/ou as posições em t onde novos elementos devem ser inseridos. Neste artigo, consideramos inferir K transformações ótimas de t da s para que o usuário encontre mais facilmente a transformação mais desejável. Primeiro mostramos que o problema de inferir K transformações ideais de um documento XML a partir de um script de atualização são NP-difíceis, mesmo que K = 1. Então, assumindo que um script de atualização tem comprimento um, mostramos um algoritmo para resolver o problema, que roda em tempo polinomial de |D|, |t|, e K.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -