the performance of the match algorithm. Also, the rule specification is error prone if written by the user.  Conversely, the main advantage of the partial-specification rules is that a single rule can represent a complex plan transformation naturally and concisely. The rule can cover a large number of plan structures even if it may occasionally fail. Also, the partial specification rules are much easier to specify and understand by the users of the system.

As we have seen, PbR provides a high degree of flexibility for defining plan-rewriting rules.

## 3.1.3 P Lan - R Ewriting A Lgo Rithm

In this section, first we describe the basic plan-rewriting algorithm in PbR. Second, we prove this algorithm sound and discuss some formal properties of rewriting. Finally, we discuss a family of algorithms for plan rewriting depending on parameters su as the language for defining plan operators, the specification language for the rewriting rules, and the requirements of the search method.

The plan-rewriting algorithm is shown in Figure 13. The algorithm takes two inputs:
a valid plan P t and a rewriting rule R = (qm, Pr, Pc) (qm is the antecedent query, pr is the replaced subplan, and pc is the replacement subplan). The output is a valid rewritten plan P ′ . The matching of the antecedent of the rewriting rule ( qm ) determines if the rule is applicable and identifies the steps and links of interest (line 1). This matching can be seen as subgraph isomorphism between the antecedent subplan and the current plan (with the results then filtered by applying the : constraints ). However, we take a different approach. PbR implements rule matching as conjunctive query evaluation.  Our implementation keeps a relational representation of the steps and links in the current plan similar to the node and link specifications of the rewriting rules. For example, the database for the plan in Figure 4 contains one table for the unstack steps with schema (?n1 ?b1 ?b2) and tuples
(4 C A) and (5 B D), another table for the causal links involving the clear condition with schema (?n1 ?n2 ?b) and tuples (0 1 C), (0 2 B), (0 2 C), (0 3 B), (0 4 C), (0 5 B), (4 3 A) and (5 1 D), and similar tables for the other operator and link types.  The match process consists of interpreting the rule antecedent as a conjunctive query with interpreted predicates, and executing this query against the relational view of the plan structures. As a running example, we will analyze the application of the avoid-move-twice rule of Figure 6 to the plan in Figure 4. Matching the rule antecedent identifies steps 1 and 4. More precisely, considering the antecedent as a query, the result is the single tuple (4 C A 1 D) for the variables (?n1 ?b1 ?b2 ?n2 ?b3).

After choosing a match σ i to work on (line 3), the algorithm instantiates the subplan sseeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee     aaac instantiated subplan p i , from the original plan P (line 5). All the edges incoming and emanating from nodes of the replaced subplan are also removed.  The effects that the replaced plan p i , was achieving for the remainder of the plan ( P - p i , ), the UsefulEffects of p i , will now have to be achieved by the replacement subplan (or other steps of P - p i ). In order to facilitate this process, the AddFlaws procedure records these effects as open conditions. 10