ACM SIGMOD Record · 1996 · 164 citations · 5 references
ManagementChange ManagementComputer ScienceData ManagementData StructuresDatabasesChange DetectionData Structure AlgorithmsDatabase ManagementStructural ChangeVersion ControlVersion Control Systems
Detecting and representing changes to data is important for active databases, data warehousing, view maintenance, and version and configuration management. Most previous work in change management has dealt with flat-file and relational data; we focus on hierarchically structured data. Since in many cases changes must be computed from old and new versions of the data, we define the hierarchical change detection problem as the problem of finding a "minimum-cost edit script" that transforms one data tree to another, and we present efficient algorithms for computing such an edit script. Our algorithms make use of some key domain characteristics to achieve substantially better performance than previous, general-purpose algorithms. We study the performance of our algorithms both analytically and empirically, and we describe the application of our techniques to hierarchically structured documents.
5
AnO(ND) difference algorithm and its variations
Eugene W. Myers · Algorithmica · 1986 · 899 citations
View maintenance in a warehousing environment
Yue Zhuge, Héctor García-Molina, Joachim Hammer et al. · 1995 · 431 citations
Fast algorithms for the unit cost editing distance between trees
Dennis Shasha, Kaizhong Zhang · Journal of Algorithms · 1990 · 119 citations · Full text
A database interface for file update
Serge Abiteboul, Sophie Cluet, Tova Milo · 1995 · 35 citations · Full text