Definition 8.7 Let ρ1 = hc : v1i and ρ2 = hc : v2i be two rules with context c**. Define the** rule product as ρ1 × ρ2 = hc : v1 · v2i, and the **rule sum** as ρ1 + ρ2 = hc : v1 + v2i.

Note that this definition is restricted to rules with the same **context. We will address this**
issue in a moment. First, we will introduce an additional operation which maximizes a variable from a set of rules, which otherwise share a common context:
Definition 8.8 Let Y be a variable with Dom[Y ] = {y1, . . . , yk}, and let ρi**, for each** i =
1, . . . , k, be a rule of the form ρi = hc ∧ Y = yi: vii**. Then for the rule-based function**
f = ρ1 + · · · + ρk, define the rule maximization over Y as maxY f = hc **: max**i vii .

After this operation, Y **has been maximized out from the scope of the function** f.

These three operations we have just described can only be applied to sets of rules that satisfy very stringent conditions. To make our set of rules amenable to the application of these operations, we might need to refine some of these rules. We therefore define the following operation:
Definition 8.9 Let ρ = hc : vi be a rule, and Y be a variable. Define the **rule split**
Split(ρ6 Y ) of ρ on a variable Y as follows: If Y ∈ Scope[C], then Split(ρ6 Y ) = {ρ};
otherwise, Split(ρ6 Y ) = {hc ∧ Y = yi: vi | yi ∈ **Dom[**Y ]} .

Thus, if we split a rule ρ on variable Y that is not in the scope of the context of ρ**, then we**
generate a new set of rules, with one for each assignment in the domain of Y .

In general, the purpose of rule splitting is to extend the context c of one rule ρ **coincide**
with the context c
′ **of another consistent rule** ρ
′**. Naively, we might take all variables in**
Scope[C′] − Scope[C] and split ρ **recursively on each one of them. However, this process**
creates unnecessarily many rules: If Y is a variable in Scope[C′] − Scope[C**] and we split** ρ on Y , then only one of the |Dom[Y ]| **new rules generated will remain consistent with** ρ
′**: the**
one which has the same assignment for Y **as the one in** c
′**. Thus, only this consistent rule**
needs to be split further. We can now define the recursive splitting procedure that achieves this more parsimonious representation:
Definition 8.10 Let ρ = hc : vi be a rule, and b be a context such that b ∈ **Dom[**B].

Define the recursive rule split Split(ρ6 b) of ρ on a context b **as follows:**
1. {ρ}, if c is not consistent with b**; else,** 2. {ρ}, if Scope[B] ⊆ Scope[C]**; else,**
3. {**Split**(ρi 6 b) | ρi ∈ Split(ρ6 Y )}, for some variable Y ∈ Scope[B] − **Scope[**C] .

In this definition, each variable Y ∈ Scope[B] − Scope[C**] leads to the generation of** k = |Dom(Y )| rules at the step in which it is split. However, only one of these k **rules is used**
in the next recursive step because only one is consistent with b**. Therefore, the size of the**
split set is simply 1 + PY ∈Scope[B]−Scope[C]
(|Dom(Y )| − **1). This size is independent of the**
order in which the variables are split within the operation.