next up previous
Next: A Cost Model Up: Overview and Preliminaries Previous: Edit Operations

Edit Scripts


Informally, an edit script gives a sequence of edit operations that transforms one tree into another. Formally, we say when is the result of applying the edit operation to . Given a sequence of edit operations, we say if there exist such that . A sequence E of edit operations transforms into if and is isomorphic to . (Recall that two trees are isomorphic if they differ only in the identifiers of their nodes.) We call such a sequence of edit operations an edit script of with respect to . Notice that an edit script does not tell us how the original matching between and should be modified to obtain the total matching between and . This will be done as the edit script is generated; see Section 4.



: Applying the edit script of Example 3.1


Sudarshan S. Chawathe
Wed Jun 19 08:22:34 PDT 1996