Extracting Difference between Regular Tree Grammars
Extracting Difference between Regular Tree Grammars
复制标题
提取正则树语法之间的差异
DOI：
10.1145/2480362.2480527
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kazuma Horie and Nobutaka Suzuki
中科院分区：
文献类型：
--
作者：
泉 朝子;玉本 英夫;横山 洋之;中村隆文，藤村純，小郷克文，樋口裕子，津高健太郎，和田友孝，岡田博美;Kazuma Horie and Nobutaka Suzuki
XML文档通常与其模式一起存储，以便确保文档的结构一致性。通常，模式根据真实的世界中的变化而不断更新。因此，我们必须精确地知道模式是如何更新的，以保持XML文档的有效性。为了了解模式是如何更新的，我们需要提取“旧”模式和“新”模式之间的差异。然而，模式最近变得越来越大，越来越复杂，因此更难知道模式是如何更新的。在本文中，我们考虑的问题，提取之间的差异定期树文法，一个流行的形式化模型的XML模式语言。我们首先证明了这个问题是NP难的。在此基础上，给出了该问题可有效求解的一个充分条件，并在此充分条件下给出了求解该问题的一个多项式时间算法。最后，我们展示了一些实验结果。
An XML document is usually stored with its schema so that the structural consistency of the document is ensured. In general, schemas are continuously updated according to changes in real world. Thus, we have to precisely know how a schema is updated to keep the validity of the XML documents. In order to know how a schema is updated, we need to extract the difference between "old" and "new" schemas. However, schemas are recently becoming larger and more complex, thus it becomes more difficult to know how a schema is updated. In this paper, we consider the problem of extracting the difference between regular tree grammars, a popular formal model of XML schema languages. We first show that the problem is NP-hard. Then we give a sufficient condition under which the problem can be solved efficiently, and present a polynomial-time algorithm for solving the problem under the sufficient condition. Finally, we show some experimental results.