Introduction

We study the problem of detecting and representing changes to hierarchically structured information. Detecting changes to data (henceforth referred to as deltas) is a basic function of many important database facilities and applications, including active databases [WC96], data warehousing [HGMW95,IK93,ZGMHW95], view maintenance [GM95], and version and configuration management [HKG94].

For example, consider the World-Wide Web. A user may visit certain (HTML) documents repeatedly and is interested in knowing how each document has changed since the last visit. Assuming we have saved the old version of the document (which many web browsers do already for efficiency), we can detect the changes by comparing the old and new versions of the document. In addition, we are interested in presenting the changes in a meaningful way. For example, a paragraph that has moved could be marked with a ``tombstone'' in its old position and be highlighted in its new position. Similarly, insertions, deletions, and updates could be marked using changes in colors and fonts.

The work on change detection reported in this paper has four key characteristics:

• Nested Information. Our focus is on hierarchical information, not ``flat'' information (e.g., files containing records or relations containing tuples). With flat information deltas may be represented simply as sets of tuples or records inserted into, deleted from, and updated in relations [GHJ93,LGM95]. In hierarchical information, we want to identify changes not just to the ``nodes'' in the data, but also to their relationships. For example, if a node (and its children) is moved from one location to another, we would like this to be represented as a ``move'' operation in the delta.

• Object Identifiers Not Assumed. For maximum generality we do not assume the existence of identifiers or keys that uniquely match information fragments across versions. For example, to compare structured documents, we must rely on values only since sentences or paragraphs do not come with identifying keys. Similarly, objects in two different design configurations may have to be compared by their contents, since object-ids may not be valid across versions. Of course, if the information we are comparing does have unique identifiers, then our algorithms can take advantage of them to quickly match fragments that have not changed.

• Old, New Version Comparison. Although some database systems, particularly active database systems, build change detection facilities into the system itself [WC96], we focus on the problem of detecting changes given old and new versions of the data. We believe that a common scenario for change detection, especially for applications such as data warehousing, or querying and browsing over changes, involves ``uncooperative'' legacy databases (or other data management systems), where the best we can hope for is a sequence of data snapshots or ``dumps'' [HGMW95,LGM95].

• High Performance. Our goal is to develop high performance algorithms that exploit features common to many applications and can be used on very large structures. In particular, [ZS89,SZ90] present algorithms that always find the most ``compact'' deltas, but are expensive to run, especially for large structures. (The running time is at least quadratic in the number of objects in each structure compared. The properties of these algorithms are described in more detail in Section 2.) Our algorithms are significantly more efficient (intuitively, our running time is proportional to the number of objects times the number of changes), but may sometimes find non-minimal, although still correct, deltas. We show that if the application domain has a certain property---very intuitively, that there are not ``too many duplicate objects,''---then our algorithm also always generates minimal deltas. Our empirical studies suggest that this property does hold in practice.

To describe a delta between two versions of hierarchical data, we use the notion of a minimum cost edit script. The minimum cost edit script for two trees is defined using node insert, node delete, node update, and subtree move as the basic editing operations. An interesting feature of our approach is that there is a clean separation of the change detection problem into two subproblems: (1) finding a matching between objects in the two versions, and (2) computing an edit script. If objects have unique identifiers, the first problem is simplified, and we can use this property to achieve a speed-up.

Although a minimum cost edit script is a good formal notion of the delta between two trees, it is not always the most convenient method for displaying or querying deltas. We have developed a second, equivalent representation scheme called a delta tree for this purpose. Due to lack of space, we do not describe delta trees in this paper; they are described in [CRGMW95].

To demonstrate our approach and algorithms, we have implemented a system to detect, mark, and display changes in structured documents, based on their hierarchical structure. Our system, called LaDiff, takes two versions of a Latex document as input and produces as output a Latex document with the changes marked. We have used this system to experimentally evaluate the performance of our algorithms; results are presented in Section 6.2. We have also implemented our algorithms in change detection modules for HTML pages and for a simple nested-object model [PGMW95].

The remainder of the paper is organized as follows. We discuss related work in Section 2. Section 3 describes our general approach, divides our problem into two distinct subproblems, and provides preliminary definitions. Our algorithms for solving the two subproblems are discussed in Sections 4 and 5. Section 6 describes the application of our techniques to hierarchically structured documents and presents our empirical performance study. Conclusions and ongoing work are covered in Section 7. Due to space constraints, several details and proofs of theorems are not presented in this paper, and may be found in [CRGMW95].