我正在寻找一种算法来检测冗余规则。
规则有固定数量的输入参数，每个参数有一个不同的域。
考虑三个规则参数Color, Material和Size:
- Color: Red, Green, Blue
- 材料:木材，玻璃，铝 大小
- :小型,中型,大型
每个规则可以匹配一个参数的多个值，也可以匹配任何值。选择匹配所有参数值的第一条规则。没有否定规则，但是域是固定的，因此可以通过添加所有其他规则来实现否定。
+--------------------------------------------------++-----------------
| Rule Parameters || Rule Action
+----------------+------------------+--------------++-----------------
| Color | Material | Size || ==> Price
+----------------+------------------+--------------++-----------------
Rule 1 | Red | Wood, Glass | Large || $100
Rule 2 | Red | Aluminium | Large || $200
Rule 3 | Blue or Green | Wood | Medium || $300
Rule 4 | Red | ** Any ** | Large || $400 <== Redundant
Rule 5 | ** Any ** | ** Any ** | ** Any ** || $500
由于规则1和规则2的组合，规则4是冗余的。冗余规则是指由于在之前定义了的规则(组合)，因此永远不会匹配的规则。在冗余检查中不评估规则操作。
如何有效地实现这个(在Java中)?它应该支持1000条规则和10个参数，每个参数有100个值。规则、参数和参数值是从数据库中读取的。它们不能硬编码)。效率的问题是输入参数有100^10个组合(每个参数有100个值的域)。规则编辑器gui中需要该算法，以支持正在创建规则的用户。它应该在几秒钟内找到所有多余的规则。
<标题> GITHUB h1> 已经创建了一个存储库来测试建议的解决方案:https://github.com/qlp/redundant-rules目前只有一个BDD实现，由于这个规模的问题而失败。也许我的BDD实现可以改进?本质上，您的任务是实现决策树。树的每一层都对应于每一个参数，在每一层，参数可以保存的每一个值都有一个节点。在叶级，您将存储适用的规则操作。
例如，在颜色级别，你有3个节点，红，蓝，绿。每一个都有3个孩子(在材料层面上)木材，玻璃，铝。每个人将有3个孩子(小，中，大)。您将基于从数据库中学习的参数和值来构建此树。
一旦构建了树，您将从数据库中读取规则，每次读取一条，并将"规则操作"存储在每个叶子上(在本例中，存储在Size级别)。如果有一条规则想要应用于已经有动作的叶子，那么应用哪条规则就存在歧义。对于您的问题，您声明将采用应用的第一条规则—因此不会更改存储的规则。
如果存在一个规则，其中每个叶子都有一个动作，因为已经有一个定义的动作，那么根据你的例子，该规则将是"多余的"。
编辑完全重写由于评论。(注意，这实际上可能与Khaled A Khunaifer写的相似，但它是在同一时间创建的)
一种可能的方法是找到规则的"逻辑"描述。这些规则有一个非常规则的形式，即总是一个断词的合词。规则可以写成
(Red) AND (Wood OR Glass) AND (Large)
(Red) AND (Aluminium) AND (Large)
...
现在，可以应用复杂的优化和最小化(如Quine McCluskey或任何其他形式的最小化)。然而，我在这里勾画了一个非常简单的实现。当规则只在一个析取中不同时，它们可以被"合并"。例如，上面的规则可以合并到
(Red) AND (Wood OR Glass OR Aluminium) AND (Large)
现在，如果像
这样的规则(Red) AND (Wood OR Glass OR Aluminium) AND (Medium)
时，它可以与前一个合并为
。(Red) AND (Wood OR Glass OR Aluminium) AND (Large OR Medium)
如果我们找到了像
这样的规则(Red) AND (Glass OR Aluminium) AND (Medium)
可以标记为"冗余"，因为它是由前一个隐含的。
再次强调这一点:这个实现相当"粗糙"，远非"优雅"，当然还有许多可能的改进。但也许它至少表明了总体思路是可行的。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
public class RulesChecker
{
public static void main(String[] args)
{
List<Rule> rules = new ArrayList<Rule>();
List<Set<String>> domains = new ArrayList<Set<String>>();
domains.add(setOf("Red", "Green", "Blue"));
domains.add(setOf("Wood", "Glass", "Aluminium"));
domains.add(setOf("Small", "Medium", "Large"));
// Rule 1 | Red | Wood, Glass | Large || $100
// Rule 2 | Red | Aluminium | Large || $200
// Rule 3 | Blue or Green | Wood | Medium || $300
// Rule 4 | Red | ** Any ** | Large || $400 <== Redundant
// Rule 5 | ** Any ** | ** Any ** | ** Any ** || $500
rules.add(new Rule("$100", disOf("Red") , disOf("Wood", "Glass"), disOf("Large")));
rules.add(new Rule("$200", disOf("Red") , disOf("Aluminium") , disOf("Large")));
rules.add(new Rule("$300", disOf("Blue", "Green"), disOf("Wood") , disOf("Medium")));
rules.add(new Rule("$310", disOf("Blue") , disOf("Wood") , disOf("Medium")));
rules.add(new Rule("$350", disOf("Green") , disOf("Aluminium") , disOf("Medium")));
rules.add(new Rule("$400", disOf("Red") , disOf(domains.get(1)) , disOf("Large")));
rules.add(new Rule("$500", disOf(domains.get(0)) , disOf(domains.get(1)) , disOf(domains.get(2))));
System.out.println("Rules: ");
for (Rule rule : rules)
{
System.out.println(rule);
}
List<Rule> mergedRules = new ArrayList<Rule>();
mergedRules.add(rules.get(0));
for (int i=1; i<rules.size(); i++)
{
add(mergedRules, rules.get(i));
}
}
private static void add(List<Rule> mergedRules, Rule newRule)
{
for (int i=0; i<mergedRules.size(); i++)
{
Rule oldRule = mergedRules.get(i);
if (implies(oldRule, newRule))
{
System.out.println("Redundant "+newRule);
System.out.println(" due to "+oldRule);
return;
}
int mergeIndex = mergeIndex(oldRule, newRule);
if (mergeIndex != -1)
{
Rule mergedRule = merge(oldRule, newRule, mergeIndex);
mergedRules.set(i, mergedRule);
System.out.println("Merging "+oldRule);
System.out.println(" and "+newRule);
System.out.println(" gives "+mergedRule);
return;
}
}
mergedRules.add(newRule);
}
private static boolean implies(Rule oldRule, Rule newRule)
{
Conjunction c0 = oldRule.conjunction;
Conjunction c1 = newRule.conjunction;
List<Expression> es0 = new ArrayList<Expression>(c0.terms);
List<Expression> es1 = new ArrayList<Expression>(c1.terms);
for (int i=0; i<es0.size(); i++)
{
Disjunction d0 = (Disjunction) es0.get(i);
Disjunction d1 = (Disjunction) es1.get(i);
if (!d0.terms.containsAll(d1.terms))
{
return false;
}
}
return true;
}
private static Disjunction disOf(String ... ss)
{
return disOf(Arrays.asList(ss));
}
private static Disjunction disOf(Collection<String> ss)
{
List<Variable> list = new ArrayList<Variable>();
for (String s : ss)
{
list.add(new Variable(s));
}
return new Disjunction(list);
}
private static int mergeIndex(Rule r0, Rule r1)
{
Conjunction c0 = r0.conjunction;
Conjunction c1 = r1.conjunction;
List<Expression> es0 = new ArrayList<Expression>(c0.terms);
List<Expression> es1 = new ArrayList<Expression>(c1.terms);
int different = 0;
int mergeIndex = -1;
for (int i=0; i<es0.size(); i++)
{
Expression e0 = es0.get(i);
Expression e1 = es1.get(i);
if (!e0.equals(e1))
{
mergeIndex = i;
different++;
if (different > 1)
{
return -1;
}
}
}
return mergeIndex;
}
private static Rule merge(Rule r0, Rule r1, int index)
{
Conjunction c0 = r0.conjunction;
Conjunction c1 = r1.conjunction;
List<Expression> es0 = new ArrayList<Expression>(c0.terms);
List<Expression> es1 = new ArrayList<Expression>(c1.terms);
Set<Disjunction> rc = new LinkedHashSet<Disjunction>();
for (int i=0; i<es0.size(); i++)
{
Disjunction d0 = (Disjunction) es0.get(i);
Disjunction d1 = (Disjunction) es1.get(i);
if (i == index)
{
Set<Expression> merged = new LinkedHashSet<Expression>();
merged.addAll(d0.terms);
merged.addAll(d1.terms);
Disjunction d = new Disjunction(merged);
rc.add(d);
}
else
{
rc.add(d0);
}
}
return new Rule("TRUE", new Conjunction(rc));
}
private static Set<String> setOf(String ... s)
{
return new LinkedHashSet<String>(Arrays.asList(s));
}
static class Expression
{
}
static class Variable extends Expression
{
final String name;
Variable(String name)
{
this.name = name;
}
@Override
public String toString()
{
return name;
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Variable other = (Variable) obj;
if (name == null)
{
if (other.name != null)
return false;
}
else if (!name.equals(other.name))
return false;
return true;
}
}
static class Disjunction extends Expression
{
private final Set<Expression> terms;
Disjunction(Collection<? extends Expression> expressions)
{
this.terms = new LinkedHashSet<Expression>(expressions);
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("(");
int n = 0;
for (Expression e : terms)
{
sb.append(e);
n++;
if (n < terms.size())
{
sb.append(" + ");
}
}
sb.append(")");
return sb.toString();
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((terms == null) ? 0 : terms.hashCode());
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Disjunction other = (Disjunction) obj;
if (terms == null)
{
if (other.terms != null)
return false;
}
else if (!terms.equals(other.terms))
return false;
return true;
}
}
static class Conjunction
{
private final Set<Expression> terms;
Conjunction(Collection<? extends Expression> expressions)
{
this.terms = new LinkedHashSet<Expression>(expressions);
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("(");
int n = 0;
for (Expression e : terms)
{
sb.append(e);
n++;
if (n < terms.size())
{
sb.append(" * ");
}
}
sb.append(")");
return sb.toString();
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((terms == null) ? 0 : terms.hashCode());
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Conjunction other = (Conjunction) obj;
if (terms == null)
{
if (other.terms != null)
return false;
}
else if (!terms.equals(other.terms))
return false;
return true;
}
}
private static class Rule
{
Conjunction conjunction;
String action;
@SafeVarargs
Rule(String action, Disjunction ... disjunctions)
{
this.action = action;
this.conjunction = new Conjunction(Arrays.asList(disjunctions));
}
Rule(String action, Conjunction conjunction)
{
this.action = action;
this.conjunction = conjunction;
}
@Override
public String toString()
{
return conjunction+" -> "+action;
}
}
}
一种可能性是使用二元决策图。这允许对布尔公式进行有效的操作。正如别人提到的，你可以把规则想象成一个二元公式:规则1是(r OR (w AND g) OR l)，规则2是(r AND a AND l)，要判断规则4是否冗余，我们需要检查(Rule4 AND (NOT (Rule1 OR Rule2 OR Rule3))是否有解。此外，需要使用(NOT (w and g))这样的子句来禁止无效输入。有许多可用的求解器，虽然不能保证运行时间或内存使用不会爆炸，但它们通常可以很好地处理实际输入。
每个规则表示一个布尔条件。不清楚你的规则符号的表达能力如何(我能说"不是Wood"吗?)，但规则1似乎是
Color==Red and (Material==Wood or Material==Glass) and Size==Large
你也可能有一些"域约束"，C(k)，大概是这样的形式:
Color==Red ==> Not(Color==Green)
，其中==>为逻辑蕴涵运算符。
你似乎想知道的是，粗略地说，如果对于某些i和j, R(i)表示"with Rule":
R(i) ==> R(j)
在实践中，您需要知道是否:
R(i) and C(1) and C(2) and ... C(K) ==> R(j)
你可以(而且必须)通过布尔代数来解决这个问题。这实际上是相对简单的，例如，将整个方程(包括隐含运算符)视为实际的符号公式，并应用布尔代数定律。
让我们用代数方法来处理你的例子(较长)
首先，对于您的示例规则系统，域约束C(i)是:
Color==Red ==> Not(Color == Green)
Color==Red ==> Not(Color == Blue)
Color==Blue ==> Not(Color == Green)
Color==Blue ==> Not(Color == Red)
Color==Green ==> Not(Color == Red)
Color==Green ==> Not(Color == Blue)
(Color==Red or Color==Blue or Color===Green) <==> true [if only these 3 colors exist]
，同样适用于材料(木材，玻璃，铝)和尺寸(小，中，大)。
对于您的具体示例，R(1)为:
Color==Red and (Material==Wood or Material==Glass) and Size==Large
和R(4)为:
Color==Red and (true) and Size==Large
你想知道的是:
R(1) and <domainconstraints> ==> R(4)
这是一个相当庞大的公式，但这实际上只是计算机的问题。在这种特殊情况下，我们不需要域约束(我，oracle，说)，所以我要把它去掉，以摆脱巨大:
R(1) and true ==> R(4)
还是
R(1) ==> R(4)
(实现提示:在尝试R(i)和==> R(j)之前，您总是可以先尝试R(i) ==> R(j)，因为第一个暗示了第二个。这可以用于在检测到冗余时降低术语的大小)。
"a ==> b"运算符是布尔值，相当于"~a或b"，所以你想知道这个公式是否为真:
Not(R(1)) or R(4)
代入R(1)和R(4)的定义:
Not(Color==Red and (Material==Wood or Material==Glass) and Size==Large) or (Color==Red and (true) and Size==Large)
利用DeMorgan定律简化"and (true)":
Not(Color==Red) or Not( (Material==Wood or Material==Glass) ) or Not( Size==Large) or Color==Red and Size==Large
第二次应用DeMorgan定律(我们真的不需要这个，因为red会驱动答案，但我们还不应该知道这个):
Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large) or Color==Red and Size==Large
一个事实:
a and b ==> a
对于任意b，
a and b or a == a
当a为Not(Color==Red)， b为Size==Large时使用:
Not(Color==Red) and Size==Large or Not(Color==Red) or or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large) or Color==Red and Size==Large
现在我们将相似项分组:
Not(Color==Red) and Size==Large or Color==Red and Size==Large or Not(Color==Red) or or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)
合并Size==Large:
( Not(Color==Red) or Color==Red) and Size==Large Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)
使用a或~ a == true:
( true ) and Size==Large or Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)
简化和分组大小条款:
(Size==Large or Not(Size==Large)) or Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass)
给(呼)
(true) or ...
产生true，因此R(1) ==> R(4)，因此R(4)是冗余的。
实现(或TL;DR)
显然你不想手工做这个。您可以将公式编码为布尔表达式(您已经做了类似的事情，以便能够将它们存储在系统中)。你想知道的是这个表述作为一个整体是否是一个重言式;对此，你可以使用王的推理规则。这实现起来有点笨拙，但是是可行的。
二元决策图(糟糕的名字)是为公式编码"真值表"的一种方式。你要做的是确定一个公式的真值表是否总是为真。正如另一个海报所指出的，你可以得到BDD包。如果你为这个隐含方程构建BDD，并且它在任何地方都是"TRUE"(也就是说，你得到一个平凡的BDD)，那么隐含为真，你就有了冗余。
检查这个的运行时间可能会变得很昂贵。你既可以忍受这种开销，也可以简单地设置每次尝试的CPU上限;它要么产生"无冲突"、"冲突"或"超时"的答案，其中"超时"被解释为"无冲突"。然后你可以让它运行得尽可能快，取模有时不会消除冗余规则。
因为你的规则是独立的声明，如果你有N个规则，你需要做这个测试大约N^2次。(好消息是，如果你已经建立了一个包含N条规则的可信数据库，那么添加一条新规则只需要N次测试)。
在强类型函数式语言的模式匹配领域有大量的工作。它到底是什么这个问题在stackoverflow上已经讨论过了。
Luc Maranget的发布页面包含许多关于该主题的文章，其中一些文章作为OCaml模式匹配算法的基础。
他关于编译模式匹配到好的决策树的论文可能是你问题的一个明确的灵感来源。它还提供了关于同一主题的先前文章的参考。基本原理是将模式匹配集描述为整数矩阵，以及代数运算。
我还强烈建议尝试ocaml，或任何小的实现，以感受ML语言家族的核心特性。您也可以看看scala，它实现了类似的功能。
这个问题中的规则数量相当大，但是值的数量是有限的。这就是为什么我认为按规则评估不会给出最快的结果。如果规则按值分组，则可以同时评估多个规则。我提出的算法仍然可以爆炸，但我希望这种可能性较小。
样本数据:
Rule #: [Color (R,G,B),Material (W,G,A),Size (S,M,L)]
Rule 1: [[1,0,0],[1,1,0],[0,1,0]]
Rule 2: [[1,0,0],[0,0,1],[0,1,0]]
Rule 3: [[0,1,1],[1,0,0],[0,0,1]]
Rule 4: [[1,0,0],[1,1,1],[0,1,0]]
Rule 5: [[1,1,1],[1,1,1],[1,1,1]]
步骤1:根据参数1
的值拆分规则根据参数1的值对集合中的规则进行分组。可能需要启发式方法来选择最佳的第一个参数。现在我只是按顺序挑选它们。
Result:
Rules in Set R: 1,2,4,5
Rules in Set G: 3,5
Rules in Set B: 3,5
步骤2:合并相等集合
集合G和集合B在这一层包含相同的规则，因此可以合并。
Result:
Rules in Set R: 1,2,4,5
Rules in Set GB: 3,5
步骤3:根据参数2
的值划分组对于所有的设置规则现在检查参数2。对于每个不同的值，集合被分成子集。步骤2的集合不再相关。
Result:
Rules in Set (R ,W): 1,4,5
Rules in Set (R ,G): 1,4,5
Rules in Set (R ,A): 2,4,5
Rules in Set (GB,W): 3,5
Rules in Set (GB,G): 5
Rules in Set (GB,A): 5
步骤4:删除单个规则
规则5现在被证明是相关的。它单独捕获(G, G, *) (B, G, *), (G, A *)和(B, A *)。集合(GB,G)和(GB,A)可以从求值中删除，因为它们不再需要证明任何东西。步骤5:合并相等集合
Result:
Rules in Set (R ,WG): 1,4,5
Rules in Set (R ,A ): 2,4,5
Rules in Set (GB,W ): 3,5
步骤3:根据参数3
的值划分组Result:
Rules in Set (R ,WG, S): 5
Rules in Set (R ,WG, M): 1,4,5
Rules in Set (R ,WG, L): 5
Rules in Set (R ,A ,S): 5
Rules in Set (R ,A ,M): 2,4,5
Rules in Set (R ,A ,L): 5
Rules in Set (GB,W ,S): 5
Rules in Set (GB,W ,M):5
Rules in Set (GB,W ,L): 3,5
规则5被清楚地证明是有用的，没有计数规则序列。1 2 3被证明了，因为在这个集合中有最高的优先级。规则4从来没有被证明过，是多余的。
伪代码:
void getProven(RuleList rulelist, RuleList provenlist, ParameterIterator i)
{
ValuesToRulelistMap subsets = new ValuesToRulelistMap();
Parameter parameter = i.next();
for (Rule rule : rulelist) {
Valuelist valuelist = rule.getValuesByParameter(parameter);
for (Value value : valueslist) {
subsets.addToListInMap(value, rule);
}
KeyList doneKeys = new KeyList();
for (RuleList subset : subsets.getRuleLists()) {
if (subset.length == 0) {
// No rule for this case!!!
} else
if (subset.length == 1) {
// Singly proven
provenlist.add(subset.getFirst());
} else
if (!i.hasNext()) {
// Proven by priority
provenlist.add(subset.getFirst());
} else
Key key = subset.combineRulesInListToKey()
if (!doneKeys.containts(key)) {
getProven(subset, provenlist, i);
doneKeys.add(key);
}
}
}
}
}
首先，让我们看一下您的示例，我们将所有选项
替换为**ANY** +---------------------------------++--------------
| Rule Parameters || Rule Action
+----------+-----------+----------++--------------
| Color | Material | Size || Price
+----------+-----------+----------++--------------
Rule 1 | R | W,G | L || $100
Rule 2 | R | A | L || $200
Rule 3 | B,G | W | M || $300
Rule 4 | R | A,W,G | L || $400
Rule 5 | R,B,G | A,W,G | S,M,L || $500
接下来，我们需要定义一个规则如何可以是冗余的，下面是我的定义
一个规则是冗余的，如果它等于除它自己以外的任何k个规则的归并。
因此，基于这个定义(注意1 <= k < n，其中n是规则的数量)，我们可以看到找到所有冗余规则将花费大量时间。
所以，如果我们的规则集中有n = 100 rules，这个暴力破解将围绕n^3 * n!，即Time ~ 100^3 * (1! + 2! + .. + 100!) = 10^6 * 9.4 * 10^158 = 9.333 * 10^164。
这是我的暴力检查的版本，它需要O(n^3 * SUM { k! | k = 1..n } ):
boolean isRedundant (RuleList R, Rule d)
{
// R is the set of rules
// T is a copy of the set, without the rule to be checked
// d is the rule to be checked
T = new RuleList(R);
T.remove(d);
for (int i=0; i<T.size(); i++) // check single rules
if (T.get(j).equal(d))
return true;
for (int k=1; k<R.size(); k++) // 1 <= k < n
{
// merge every k-permutation to check
for (RuleList permutation : T.getPermutations(k))
{
Rule r = new Rule ();
for (Rule p : permutation)
r.merge(p);
if (r.equal(d))
return true;
}
}
return false;
}
class Rule
{
public boolean [3] color; // R,G,B
public boolean [3] material; // A,W,G
public boolean [3] size; // S,M,L
public Rule ()
{
color = { false, false, false };
material = { false, false, false };
size = { false, false, false };
}
public void merge (Rule r)
{
color[0] = and(color[0], r.color[0]);
color[1] = and(color[1], r.color[1]);
color[2] = and(color[2], r.color[2]);
material[0] = and(material[0], r.material[0]);
material[1] = and(material[1], r.material[1]);
material[2] = and(material[2], r.material[2]);
size[0] = and(size[0], r.size[0]);
size[1] = and(size[1], r.size[1]);
size[2] = and(size[2], r.size[2]);
}
public boolean equal (Rule r)
{
return (color[0]==r.color[0]
&& color[1]==r.color[1]
&& color[2]==r.color[2]
&& material[0]==r.material[0]
&& material[1]==r.material[1]
&& material[2]==r.material[2]
&& size[0]==r.size[0]
&& size[1]==r.size[1]
&& size[2]==r.size[2]);
}
public boolean and(boolean a, boolean b)
{
return (a && b);
}
}
替代解决方案
假设我们有代表每个参数的集合，那么我们可以从规则总数中减少要检查的规则数量，这也可以优化时间复杂度，因为我们将从那个角度将所有成员视为一个，然后通过一个简单的匹配算法。
+---------------------------------++--------------
| Rule Parameters || Rule Action
+----------+-----------+----------++--------------
| Color | Material | Size || Price
+----------+-----------+----------++--------------
Rule 1 | R | W,G | L || $100
Rule 2 | R | A | L || $200
Rule 3 | B,G | W | M || $300
Rule 4 | R | A,W,G | L || $400
Rule 5 | R,B,G | A,W,G | S,M,L || $500
我们有以下内容:
Color_R = { 1, 2, 4, 5 }
Color_B = { 3, 5 }
Color_G = { 3, 5 }
Material_A = { 2, 4, 5 }
Material_W = { 1, 3, 4, 5 }
Material_G = { 1, 4, 5 }
Size_S = { 5 }
Size_M = { 3, 5 }
Size_L = { 1, 2, 4, 5 }
现在，对于每个规则，我们取其参数集，然后不查看同一规则进行匹配。
的例子:
Rule_4 = { Color_R, Material_A, Material_W, Material_G, Size_L }
Color_R = { 1, 2, x, 5 }
Material_A = { 2, x, 5 }
Material_W = { 1, 3, x, 5 }
Material_G = { 1, x, 5 }
Size_L = { 1, 2, x, 5 }
我们检查匹配所有成员关系的规则集:
Matched = { 5, 1+2 }
然后我们将它们与选定的规则进行比较，通过集差查找phi:
Rule_5 - Rule_4 = { Color_B, Color_G, Size_S, Size_M }
> Rule_5 does not match
(Rule_1 + Rule2) - Rule_4 = { }
> (Rule_1 + Rule2) match
最后，我们得出结论:
(Rule_1 + Rule2) = Rule_4
> Rule_4 is redundant