3.1.5 A Taxonomy of Plan-Rewriting Rules

In order to guide the user in defining plan-rewriting rules for a domain or to help in designing algorithms that may automatically deduce the rules from the domain specification (see Section 6), it is helpful to know what kinds of rules are useful. We have identified the following general types of transformation rules:

Reorder:

These are rules based on algebraic properties of the operators, such as commutative, associative and distributive laws. For example, the commutative rule that reorders two operators that need the same resource in Figure 10, or the join-swap rule in Figure 29 that combines the commutative and associative properties of the relational algebra.

Collapse:

These are rules that replace a subplan by a smaller subplan. For example, when several operators can be replaced by one, as in the remote-join-eval rule in Figure 29. This rule replaces two remote retrievals at the same information source and a local join operation by a single remote join operation, when the remote source has the capability of performing joins. An example of the application of this rule to a query plan is shown in Figure 30. Other examples are the Blocks World rules in Figure 6 that replace an unstack and a stack operators either by an equivalent single stack operator or the empty plan.

Expand:

These are rules that replace a subplan by a bigger subplan. Although this may appear counter-intuitive initially, it is easy to imagine a situation in which an expensive operator can be replaced by a set of operators that are cheaper as a whole. An interesting case is when some of these operators are already present in the plan and can be synergistically reused. We did not find this rule type in the domains analyzed so far, but Bäckström [12] presents a framework in which adding actions improves the quality of the plans. His quality metric is the plan execution time, similarly to the manufacturing domain of Section 4.1. Figure 16 shows an example of a planning domain where adding actions improves quality (from [12]). In this example, removing the link between Bm and C1 and inserting a new action A' shortens significantly the time to execute the plan.

Figure 16: Adding Actions Can Improve Quality

Parallelize:

These are rules that replace a subplan with an equivalent alternative subplan that requires fewer ordering constraints. A typical case is when there are redundant or alternative resources that the operators can use. For example, the rule punch-by-drill-press in Figure 7. Another example is the rule that Figure 16 suggests that could be seen as a combination of the expand and parallelize types.