java - Algorithm to detect redundant rules -

java - Algorithm to detect redundant rules -

i looking algorithm observe redundant rules.

rules have fixed number of input parameters , each parameter has distinct domain.

consider 3 rule parameters color, material , size:

color: red, green, blue material: wood, glass, aluminium size: small, medium, large

each rule can match on multiple values of parameter or match on value. first rule matches all parameters values selected. there no negation rules, domain fixed, negation can achieved added others.

+--------------------------------------------------++----------------- | rule parameters || rule action +----------------+------------------+--------------++----------------- | color | material | size || ==> cost +----------------+------------------+--------------++----------------- rule 1 | reddish | wood, glass | big || $100 rule 2 | reddish | aluminium | big || $200 rule 3 | bluish or greenish | wood | medium || $300 rule 4 | reddish | ** ** | big || $400 <== redundant rule 5 | ** ** | ** ** | ** ** || $500

rule 4 redundant due combination of rule 1 , 2. redundant rule rule never matched due (a combination) of rules defined before rule. rule action not evaluated in redundancy check.

how implement efficiently (in java)? should back upwards 1000 rules 10 parameters 100 values each. rules, parameters , parameter values read database (ie. cannot hard-coded).

the issue efficiency there 100^10 combinations of input parameters (each parameter has domain of 100 values). algorithm needed in rule editor gui, back upwards user creating rules. should find redundant rules within seconds.

github

i've created repository test proposed solutions: https://github.com/qlp/redundant-rules bdd implementation, failing problem of size. maybe bdd implementation can improved?

essentially, you're tasked implementing decision tree. each level of tree corresponds each parameter, , @ each level, there node each value parameter hold. @ leaf level, store rule action applicable.

for example, @ color level, you'd have 3 nodes, red, blue, green. each of have 3 children (on material level) wood, glass, aluminum. each of have 3 children (small, medium, large). build tree based on learning parameters , values database.

once tree constructed, you'd read rules database, 1 @ time, , store 'rule action' @ each of leaves (in case, @ size level). if there rule wanted apply @ leaf had action, there ambiguity rule apply. problem stated you'd take first rule applied - not alter rule stored.

if there rule, each of leaves had action there defined action, rule 'redundant' according example.

java algorithm math pattern-matching discrete-mathematics