the embedding is already specified in the rule consequent, and the replacement subplan is simply added to the current plan. If the rule is partially specified, our algorithm can compute all the valid embeddings.

The choice of one versus all rewritings affects both the antecedent matching and the embedding of rule consequent. The rule matches can be computed either all at the same time, as in bottom-up evaluation of logic databases, or one-at-a-time as in Prolog, depending on whether the search strategy requires one or all rewritings. If the rule is fully-specified only one embedding per match is possible. But, if the rule is partially-specified multiple embeddings may result from a single match. If the search strategy only requires one rewriting, it must also provide a mechanism for choosing which rule is applied, which match is computed, and which embedding is generated ( rPOP can stop at the first embedding or compute all embeddings).  Our implemented rewriting algorithm has a modular design to support different combinations of these choices.

## 3.1.4 Complexity Of Plan Rewriting

The complexity of plan rewriting in PbR originates from two sources: matching the rule antecedent against the plan, and computing the embeddings of the replacement plan. In order to analyze the complexity of matching plan-rewriting rules, we introduce the following database-theoretic definitions of complexity (Abiteboul et al., 1995):
Data Complexity: complexity of evaluating a fixed query for variable database inputs.

Expression Complexity: complexity of evaluating, on a fixed database instance, the queries specifiable in a given query language.

Data complexity measures the complexity with respect to the size of the database.

Expression complexity measures the complexity with respect to the size of the queries (taken from a given language). In our case, the database is the steps and links of the plan and the queries are the antecedents of the plan-rewriting rules.

Formally, the language of the rule antecedents described in Section 3.1.1 is conjunctive queries with interpreted predicates. The worst-case combined data and expression complexity of conjunctive queries is exponential (Abiteboul et al., 1995). That is, if the size of the query (rule antecedent) and the size of the database (plan) grow simultaneously, there is little hope of mating efficiently. Fortunately, relationally-complete languages have a data complexity contained in Logarithmic Space, which is, in turn, contained in Polynomial Time
(Abiteboul et al., 1995). Thus our conjunctive query language has at most this complexity. This is a very encouraging result that shows that the cost of evaluating a fixed query grows very slowly as the database size increases. For PbR this means that matching the antecedent of the rules is not strongly affected by the size of the plans. Moreover, in our experience useful rule antecedents are not very large and contain many constant labels (at least, the node and edge predicate names) that help to reduce the size of the intermediate results and improve the efficiency of matching. This result also indicates that we could extend the language of the antecedent to be relationally complete without affecting significantly the performance of the system. 11 Another possible extension is to use datalog with stratified negation, which also has polynomial time data complexity. Graph-theoretic properties of