Boolean Network Rule Engine

• US 20050246302A1
• Filed: 08/10/2004
• Published: 11/03/2005
• 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.
• Granted Patent: US 7,313,552 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A Boolean Network rule engine is described. In one embodiment, for example, a system for evaluation of a set of rules based on input data 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, 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 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, and evaluating rules based on the input data and active transducers and logic gates of the Boolean Network representation.

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, each rule having at least one condition;

a network builder for building a Boolean Network representation of the set of rules, 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 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, and evaluating rules based on the input data and active transducers and logic gates of the Boolean Network representation.

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 network builder assigns weights to links between nodes of the Boolean Network representation for establishing an order in which transducers and logic gates are activated.

12. The system of claim 11, 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.

13. 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.

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

15. The system of claim 1, 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.

16. The system of claim 15, 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.

17. The system of claim 15, 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.

18. The system of claim 15, 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.

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

20. A method for evaluating a set of rules based on input data, the method comprising:

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

building a Boolean Network representation of the set of rules, 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;

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

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

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

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

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

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

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

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

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

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

29. The method of claim 28, 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.

30. The method of claim 20, wherein said building step includes assigning weights to links between nodes of the Boolean Network representation for establishing an order in which transducers and logic gates are activated.

31. The method of claim 30, wherein said activating step includes activating transducers and logic gates based on results of evaluation of items of input data and said weights.

32. The method of claim 20, 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.

33. The method of claim 20, 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.

34. The method of claim 33, 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.

35. The method of claim 20, 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.

36. The method of claim 35, 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.

37. The method of claim 20, 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.

38. The method of claim 37, 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.

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

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

41. A downloadable set of processor-executable instructions for performing the method of claim 20.