Algorithm to detect redundant rules

Question

I am looking for an algorithm to detect redundant rules.

Rules have a fixed number of input parameters and each parameter has a distinct domain.

Consider three rule parameters Color, Material and Size:

• Color: Red, Green, Blue
• Material: Wood, Glass, Aluminium
• Size: Small, Medium, Large

Each rule can match on multiple values of a parameter or match on any value. The first rule that matches all parameters values is selected. There are no negation rules, but the domain is fixed, so a negation can be achieved by added all others.

       +--------------------------------------------------++-----------------
       |                   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

Rule 4 is redundant due to a combination of Rule 1 and 2. A redundant rule is a rule that will never be matched due to (a combination) of rules defined before that rule. The rule action is not evaluated in the redundancy check.

How to implement this efficiently (in Java)? It should support 1000 rules with 10 parameters with 100 values each. The rules, parameters and parameter values are read from a database (ie. they cannot be hard-coded).

The issue with efficiency is that there are 100^10 combinations of input parameters (each parameter has a domain of 100 values). The algorithm is needed in the rule editor gui, to support the user that is creating the rules. It should find all redundant rules within seconds.

GITHUB

I've created a repository to test proposed solutions: https://github.com/qlp/redundant-rules Currently only a BDD implementation, which is failing with a problem of this size. Maybe my BDD implementation can be improved?

Answer 1

Essentially, you're tasked with implementing a decision tree. Each level of the tree corresponds to each parameter, and at each level, there will be a node for each value that the parameter could hold. At the leaf level, you would store the rule action that was applicable.

For example, at the Color level, you'd have 3 nodes, Red, Blue, Green. Each of those would have 3 children (on the Material level) Wood, Glass, Aluminum. Each of those would have 3 children (Small, Medium, Large). You would construct this tree based on learning the parameters and values from the database.

Once the tree is constructed, you'd read the rules from the database, one at a time, and store the 'rule action' at each of the leaves (in this case, at the Size level). If there was a rule that wanted to apply at a leaf that already had an action, then there is an ambiguity about which rule would apply. For your problem you stated that you'd take the first rule that applied - so you would not change the rule stored.

If there was a rule, where for each of the leaves it had an action for there already was a defined action, then that rule would be 'redundant' according to your example.

Answer 2

EDIT Completely rewritten due to the comments. (Note that this might actually be similar to what Khaled A Khunaifer wrote, but it has been created at the same time)

One possible approach could be to find a "logical" description of the rules. The rules have a quite regular form, namely always a conjunction of disjunctions. The rules can be written as

(Red) AND (Wood OR Glass) AND (Large)
(Red) AND (Aluminium) AND (Large)
...

Now, one could apply sophisticated optimizations and minimizations (like Quine McCluskey or any other form of minimization). However, I sketched a very simple implementation here. Rules can be "merged" when they only differ in one of the disjunctions. For example, the rules above could be merged to

(Red) AND (Wood OR Glass OR Aluminium) AND (Large)

Now, if a rule like

(Red) AND (Wood OR Glass OR Aluminium) AND (Medium)

was encountered, it could be merged with the previous one to

(Red) AND (Wood OR Glass OR Aluminium) AND (Large OR Medium)

If we then found a rule like

(Red) AND (Glass OR Aluminium) AND (Medium)

it could be marked as "redundant", because it is implied by the previous one.

To emphasize this again: This implementation is rather "hacky" and far from being "elegant", and there are certainly many possible improvements. But maybe it shows that the general idea is feasible, at least.

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;
        }
    }
}