Finding an optimum edit script between an XML document and a DTD
Finding an optimum edit script between an XML document and a DTD
复制标题
在 XML 文档和 DTD 之间寻找最佳编辑脚本
DOI：
10.1145/1066677.1066825
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Nobutaka Suzuki
中科院分区：
文献类型：
--
作者：
Nobutaka Suzuki
在数据检索和数据转换过程中，如何在数据之间找到一个最佳的编辑脚本是一个重要的问题。迄今为止，已经提出了许多在两个XML文档之间寻找最佳编辑脚本的方法，但是很少有人研究在XML文档和DTD之间寻找最佳编辑脚本。在本文中，我们首先展示了一个多项式时间算法，找到一个最佳的XML文档（建模为有序树）和DTD之间的编辑脚本。我们接下来证明，如果在树中的一个节点上的操作的成本可能取决于其他节点，那么相应的决策问题成为强NP完全的。
Finding an optimum edit script between data plays an important role in data retrieval and data transformation. Many methods for finding an optimum edit script between two XML documents have been proposed so far, but few studies on finding an optimum edit script between an XML document and a DTD have been made. In this paper, we first show a polynomial-time algorithm that finds an optimum edit script between an XML document (modeled as an ordered tree) and a DTD. We next prove that, if the cost of an operation on a node in a tree may depend on the other nodes, then the corresponding decision problem becomes strongly NP-complete.