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 .
展开▼
机译：DTD根据现实世界的变化不断更新。假设 t是对DTD D有效的XML文档，并假定 D由更新脚本<i> s更新。通常，我们不能唯一地“推断”从 s到 t的变换，即，我们不能唯一地确定 t中应删除的元素和/或 t中的位置新元素应插入。在本文中，我们考虑从推断出 t的 K个最佳变换，以便用户更容易地找到最理想的变换。我们首先显示，即使 K = 1，从更新脚本推断XML文档的 K个最佳转换的问题也是NP-难的。然后，假设更新脚本的长度为1，则显示用于解决问题的算法，该算法以| D |，| t |和 K的时间多项式运行。
展开▼
