Meaningful change detection in structured data
Meaningful change detection in structured data
复制标题
结构化数据中有意义的变化检测
DOI：
10.1145/253260.253266
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
H. Garcia
中科院分区：
文献类型：
--
作者：
S. Chawathe;H. Garcia
通过比较数据快照来检测更改是差异查询、活动数据库以及版本和配置管理的重要要求。在本文中，我们专注于检测有意义的变化，分层结构的数据，如嵌套对象数据。这个问题比关系数据或平面文件数据的相应问题更具挑战性。为了更好地描述变化，我们的工作不仅基于传统的“原子”插入，删除，更新操作，而且还基于移动整个子树的节点和复制整个子树的操作。这些操作允许我们以语义上更有意义的方式描述变化。由于这种变化检测问题是NP难的，在本文中，我们提出了一个启发式的变化检测算法，产生接近“最小”的变化的描述，并具有比以前的算法更少的限制。我们的算法是基于转换的变化检测问题的问题，计算最小成本的二分图的边缘覆盖。我们研究我们的算法产生的解决方案的质量，以及运行时间，分析和实验。
Detecting changes by comparing data snapshots is an important requirement for difference queries, active databases, and version and configuration management. In this paper we focus on detecting meaningful changes in hierarchically structured data, such as nested-object data. This problem is much more challenging than the corresponding one for relational or flat-file data. In order to describe changes better, we base our work not just on the traditional “atomic” insert, delete, update operations, but also on operations that move an entire sub-tree of nodes, and that copy an entire sub-tree. These operations allows us to describe changes in a semantically more meaningful way. Since this change detection problem is NP-hard, in this paper we present a heuristic change detection algorithm that yields close to “minimal” descriptions of the changes, and that has fewer restrictions than previous algorithms. Our algorithm is based on transforming the change detection problem to a problem of computing a minimum-cost edge cover of a bipartite graph. We study the quality of the solution produced by our algorithm, as well as the running time, both analytically and experimentally.