0

I have structure as below

Parameter -> Condition -> Rule

Let say i need to create a Business rule, Customer Age > 18

I have two parameters, Customer Age (P1) and 18(P2), where P1 is Field Parameter (Ognl) and P2 is constant Parameter with value 18.

So my Condition now is , Customer Age > 18 and so as my Rule.

Problem Statement : Avoid user from creating duplicate parameter/condition and rules.

Solution : Constant Parameters, Field Parameters etc i can check in DB and compare if already present.

Now condition for me,

Customer Age > 18 and 18 < Customer Age is same in business terms.

The above cases can be more complex.

(a + b) * (c + d) is same as (b + a) * (d + c)

I need to validate the above expressions.

First Approach - Load all expression from DB (Can be 10000's) and compare using Stack/Tree Structure, which will really kill my objective.

Second Approach - I was thinking of building power full, let say hashcode generator or we can say one int value against every expression (considering operators/brackets also). this value should be generated in such a way that it validates above expression.

Means a + b and b + a should generate same int value, and a - b and b - a should generate different.

Ankur Singhal
  • 26,012
  • 16
  • 82
  • 116

3 Answers3

1

Maybe a simplified version of your first approach: What about filtering only the relevant expressions by looking for similar content as you are about to insert into the database?

If you know that you are about to insert Customer Age you can find all expressions containing this parameter and build the stack/tree based on this reduced set of expressions.

Florian Blum
  • 648
  • 6
  • 16
  • correct, i can reduce the output/iterations, but still my application uses same parameter in 100's of condition, rules... – Ankur Singhal Dec 02 '14 at 09:01
  • I really like your approach of using a custom hashing function. The problem is that you have to make sure that the hashed values (e.g. the string `Customer Age`) are _exactly_ the same when they are used (not `customer Age`, etc.). – Florian Blum Dec 02 '14 at 09:07
  • i am worried about name, user can give any, the content beneath the parameters, conditions i want to use in hashcode calculation, like Parameter with value 18 can be named as Eighteen or 18 or eighteen etc.. – Ankur Singhal Dec 02 '14 at 09:14
  • If you don't want to mess around with the similarity of "18"/"Eighteen"/"eighteen"/etc you could restrict the user input e.g. by forcing integers to be inserted as numbers and not as text. For properties like "Customer Age" you could also give content assistance by listing similar properties while entering the string :) – Florian Blum Dec 04 '14 at 07:11
1

I think that you cannot avoid writing a parser of expressions, building an AST of the expressions and code rewrite rules to detect expressions equivalence.

It may not be as time consuming as you think.

For the parsing and AST building part, you can start from exp4j: http://www.objecthunter.net/exp4j/

For the rewrite rules, you can have a look at: Strategies for simplifying math expressions

Community
  • 1
  • 1
M. Page
  • 2,694
  • 2
  • 20
  • 35
  • Exactly same thing i mentioned, but more or less it will be very time consuming, at any given time i can have 1000's of rules, 3-5K conditions,..... – Ankur Singhal Dec 02 '14 at 08:59
  • Both cases, i cannot give something to client that takes time to create something. – Ankur Singhal Dec 02 '14 at 09:12
  • might be you are right, and with your past exp, i will prefer if you can edit your answer and explain me in detail, it might help me. My expression are stored in DB, i have entities, using Hibernate, it is server side validation. – Ankur Singhal Dec 02 '14 at 09:16
  • Ooops, I thought you wanted to do this in **Javascript**. I now realize that you don't want to do this in the browser, but in Java. Sorry – M. Page Dec 02 '14 at 09:19
  • Execution time should not be a problem, since it will depend only on parsing time and canonization time. All your expression will be stored in canonized form, and using a hash key as you propose, finding for a canonized expression if an equivalent expression exists can be done in constant time. – M. Page Dec 02 '14 at 09:44
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/66016/discussion-between-m-page-and-ankur-singhal). – M. Page Dec 02 '14 at 09:47
  • i would like you to edit your answer and summarize hat we discussed over chat, and also attach that particular link, so that others can also get some inputs. – Ankur Singhal Dec 02 '14 at 10:12
1

For a 100% safe solution you should analyze the expressions with a computer algebra system to see whether there are mathemiatically equal. But that's not so easy.

A pragmatic approach that can be to test whether two expressions are similar:

  • Check whether they have the same variables
  • Compare their outputs for a number of different inputs, see if the outputs are equal

You can store the variable list and outputs for a predefined set of inputs as a "hash" for the expression. This hash does not give a guarentee that two expresions are equal, but you could present expressions with the same hash to the user asking if this new rule is equal to one of these similar ones.

Jos de Jong
  • 6,602
  • 3
  • 38
  • 58