Boolean network rule engine

• US 7,313,552 B2
• Filed: 08/10/2004
• Issued: 12/25/2007
• Est. Priority Date: 03/19/2004
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Jin, Jihong, Lorenz, Brian K.
• Primary Examiner(s): Knight; Anthony
• Assistant Examiner(s): Kennedy; Adrian L.
• Application Number:
  US10/710,885
• Publication Number:
  US 20050246302A1
• Time in Patent Office: 1,232 Days
• Field of Search: 706/2, 706/47, 706/48, 706/25, 706/900
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A Boolean Network rule engine for evaluation of rules is described that comprises: a rules interface for receiving a set of rules, each rule having at least one condition; a network builder for building a Boolean Network representation of the set of rules including transducers linked by logic gates, each transducer generating a Boolean value based on evaluating an item of input data against a condition of a rule; and a runtime evaluation engine for receiving input data, detecting changed items of input data, activating links among transducers and logic gates of the Boolean Network representation based on the changed items of input data so as to utilize transducers and logic gates of the Boolean Network representation relevant to rule evaluation outcome, evaluating rules based on the input data and active transducers and logic gates and returning results of rule evaluation.

Claims

1. A system for evaluation of a set of rules based on input data, the system comprising:

a rules interface for receiving a set of rules from a user, each rule having at least one condition;

a network builder for building a Boolean Network representation of the set of rules in a computing system, the Boolean Network representation including transducers linked by logic gates, each transducer generating a Boolean value based on evaluating an item of input data against a condition of a rule;

wherein said network builder assigns weights to links between transducers and logic gates of the Boolean Network representation for establishing an order in which transducers and logic gates are activated; and

a runtime evaluation engine for receiving input data, detecting changed items of input data, activating links among transducers and logic gates of the Boolean Network representation based on said changed items of input data so as to utilize transducers and logic gates of the Boolean Network representation relevant to rule evaluation outcome, evaluating rules based on the input data and active transducers and logic gates of the Boolean Network representation, and returning results of evaluation of said set of rules;

wherein said runtime evaluation engine activates transducers and logic gates for evaluation based on results of evaluation of items of input data and said weights.

2. The system of claim 1, wherein said logic gates of the Boolean Network representation include OR gates.

3. The system of claim 1, wherein said logic gates of the Boolean Network representation include conjunctive logic gates and disjunctive logic gates.

4. The system of claim 1, wherein said rules interface receives rules written in RuleML.

5. The system of claim 1, wherein said rules interface comprises a JSR 94 interface.

6. The system of claim 1, wherein said network builder factors the set of rules for common expressions so as to remove redundancies from the Boolean Network representation.

7. The system of claim 1, wherein said network builder creates groups of related transducers so as to provide for more efficient evaluation of input data.

8. The system of claim 7, wherein said related transducers comprise transducers evaluating a common item of input data.

9. The system of claim 8, wherein said groups of related transducers are grouped based on transducer condition.

10. The system of claim 9, wherein evaluation of one transducer in a group of related transducers enables the runtime evaluation engine to imply a result of evaluation of at least some other related transducers in the group.

11. The system of claim 1, wherein said runtime evaluation engine listens on a first link into an AND logic gate and only activates a second link into the AND logic gate if the Boolean value of TRUE is received through the first link.

12. The system of claim 1, wherein a transducer harvests an input item of data when activated.

13. A system for evaluation of a set of rules based on input data, the system comprising:

a rules interface for receiving a set of rules from a user, each rule having at least one condition;

a network builder for building a Boolean Network representation of the set of rules in a computing system, the Boolean Network representation including transducers linked by logic gates, each transducer generating a Boolean value based on evaluating an item of input data against a condition of a rule; and

a runtime evaluation engine for receiving input data, detecting changed items of input data, activating and passivating links among transducers and logic gates of the Boolean Network representation based on said changed items of input data so as to utilize transducers and logic gates of the Boolean Network representation relevant to rule evaluation outcome, evaluating rules based on the input data and active transducers and logic gates of the Boolean Network representation, and returning results of evaluation of said set of rules;

wherein said runtime evaluation engine passivates links based on results of evaluation of items of input data so as to avoid evaluating other items of input data without affect on rule outcome.

14. The system of claim 13, wherein said runtime evaluation engine passivates a first link into an OR logic gate in response to receiving a Boolean value of TRUE through a second link into the OR logic gate.

15. The system of claim 13, wherein said runtime evaluation engine passivates a first link into an AND logic gate in response to receiving a Boolean value of FALSE through a second link into the AND logic gate.

16. The system of claim 13, wherein said runtime evaluation engine propagates a passivation message from a given input link back through logic nodes and transducers in the Boolean Network representation which flow into the given input link.

17. The system of claim 13, wherein a link is passivated when its source node changes from TRUE to FALSE.

18. A method in a computing system for evaluating a set of rules based on input data, the method comprising:

receiving a set of rules from a user, each rule having at least one condition;

building a Boolean Network representation of the set of rules in the computing system, the Boolean Network representation including transducers linked by logic gates with each transducer generating a Boolean value based on evaluating an item of input data against a condition of a rule;

wherein said building step includes assigning weights

to links between transducers and logic gates of the Boolean Network representation for establishing an order in which transducers and logic gates are activated;

detecting changed items of input data;

in response to changed items of input data, activating links among transducers and logic gates of the Boolean Network representation so as to utilize transducers and logic gates of the Boolean Network representation relevant to rule evaluation outcome;

wherein said activating step includes activating transducers and logic gates based on results of evaluation of items of input data and said weights;

determining results of evaluation of the set of rules based on the input data using active transducers and logic gates of the Boolean Network representation; and

returning said results of evaluation.

19. The method of claim 18, wherein said logic gates of the Boolean Network representation include OR gates.

20. The method of claim 18, wherein said logic gates of the Boolean Network representation include conjunctive logic gates and disjunctive logic gates.

21. The method of claim 18, wherein said receiving step includes receiving a set of rules written in RuleML.

22. The method of claim 18, wherein said receiving step includes receiving a set of rules through a JSR 94 interface.

23. The method of claim 18, wherein said building step includes factoring the set of rules for common expressions so as to remove redundancies from the Boolean Network representation.

24. The method of claim 18, wherein said building step includes grouping related transducers so as to provide for more efficient evaluation of input data.

25. The method of claim 24, wherein said step of grouping related transducers includes grouping transducers evaluating a common item of input data.

26. The method of claim 25, wherein said grouping of related transducers further comprises grouping related transducers based on conditional operator of said related transducers.

27. The method of claim 26, wherein evaluation of one transducer in a group of related transducers implies a result of evaluation of at least some other related transducers in the group.

28. The method of claim 18, further comprising:

passivating links based on results of evaluation of items of input data so as to avoid evaluating other items of input data without affect on rule outcome.

29. The method of claim 18, wherein said activating step includes listening on a first link into an AND logic gate and activating a second link into the AND logic gate if the Boolean value of TRUE is received through the first link.

30. The method of claim 29, wherein said activating step includes propagating an activation message from the AND logic gate back through logic nodes and transducers in the Boolean Network representation which input into the AND logic gate.

31. The method of claim 18, further comprising:

passivating a first link into an OR logic gate in response to receiving a Boolean value of TRUE through a second link into the OR logic gate.

32. The method of claim 31, wherein said passivating step includes propagating a passivation message from the OR logic gate back through logic nodes and transducers in the Boolean Network representation which input into the OR logic gate.

33. The method of claim 18, further comprising:

passivating a first link into an AND logic gate in response to receiving a Boolean value of FALSE through a second link into the AND logic gate.

34. The method of claim 33, wherein said passivating step includes propagating a passivation message from the AND logic gate back through logic nodes and transducers in the Boolean Network representation which input into the AND logic gate.

35. The method of claim 18, wherein a transducer harvests an input item of data when activated.

36. A computer-readable medium having processor-executable instructions for performing the method of claim 18.

37. The method of claim 18, further comprising:

Downloading a set of processor-executable instructions for performing the method of claim 18.