Method and system for sequential compilation and execution of rules

• US 7,809,666 B2
• Filed: 12/07/2006
• Issued: 10/05/2010
• Est. Priority Date: 12/07/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Citeau, Hugues
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US11/635,918
• Publication Number:
  US 20090228421A1
• Time in Patent Office: 1,398 Days
• Field of Search: 706 45- 47, 717101-102, 717106-108, 717114-118, 717/136, 717137-140, 717/148
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

Systems and methods for matching objects against a set of rules are described. The present invention is a novel rule execution algorithm that generally operates with greater efficiency than known algorithms. The algorithm uses a test analyzer to determine the relationships that exist between pairs of tests within a ruleset. Each rule is then translated into loops and tests, and merged into a unified series of loops and tests using the output of the test analyzer. The algorithm then generates pattern matching code corresponding to the unified series of loops and tests for evaluation by a virtual machine, and auxiliary code that provides object manipulations and rule actions at the service of the pattern matching code. In its runtime, the algorithm loads objects into the pattern matching code through an access interface. The pattern matching code is then executed by the virtual machine against the loaded objects.

Claims

1. A method, within a computer hardware system, for processing a ruleset,

the ruleset including a plurality of rules,

each individual rule of the plurality of rules including a condition and a rule action responsive to the condition being met,

each condition within an individual rule including a plurality of tests,

the method comprising:

identifying a plurality of relationships, each identified relationship is between a plurality of tests respectively associated with different conditions;

translating, by the computer hardware system, each individual rule of the plurality of rules into a coded series of one or more loops and tests; and

unifying, by the computer hardware system, the loops and the test from each individual rule of the plurality of rules into a unified series of loops and tests for the ruleset, wherein

the unifying based upon the identified plurality of relationships.

2. The method of claim 1, wherein

one of the identified plurality of relationships is a disjoint.

3. The method of claim 2, wherein

the plurality of tests respectively associated with the disjoint relationship are unified into a switch test.

4. The method of claim 1, further comprising

translating the unified series of loops and tests into a pattern matching code for the ruleset;

and

evaluating an object set using the pattern matching code for the ruleset.

5. The method of claim 4, further comprising

generating auxiliary code, distinct from the pattern matching code, including coded object manipulations and rule actions;

and

performing the object manipulations and the rule actions on an object in the object set using the auxiliary code.

6. The method of claim 1, wherein

each identified relationship having a type selected from the group consisting of equality, complement, subsumption, disjoint, and unrelated.

7. A computer hardware system for processing a ruleset,

the ruleset including a plurality of rules,

each individual rule of the plurality of rules including a condition and a rule action responsive to the condition being met,

each condition within an individual rule including a plurality of tests,

the computer hardware system comprising:

a memory;

at least one processor connected to the memory, the at least one processor configured to perform

identifying a plurality of relationships, each identified relationship is between a plurality of tests respectively associated with different conditions;

translating each individual rule of the plurality of rules into a coded series of one or more loops and tests; and

unifying the loops and the test from each individual rule of the plurality of rules into a unified series of loops and tests for the ruleset, wherein

the unifying based upon the identified plurality of relationships.

8. The method of claim 7, wherein

one of the identified plurality of relationships is a disjoint.

9. The method of claim 8, wherein

the plurality of tests respectively associated with the disjoint relationship are unified into a switch test.

10. The computer hardware system of claim 7, wherein

the at least one processor is further configured to perform

translating the unified series of loops and tests into a pattern matching code for the ruleset;

and

evaluating an object set using the pattern matching code for the ruleset.

11. The computer hardware system of claim 10, wherein

the at least one processor is further configured to perform

generating auxiliary code, distinct from the pattern matching code, including coded object manipulations and rule actions;

and

performing the object manipulations and the rule actions on an object in the object set using the auxiliary code.

12. The computer hardware system of claim 7, wherein

each identified relationship having a type selected from the group consisting of equality, complement, subsumption, disjoint, and unrelated.

13. A computer-readable storage medium having stored therein computer usable program code for processing a ruleset,

the ruleset including a plurality of rules,

each individual rule of the plurality of rules including a condition and a rule action responsive to the condition being met,

each condition within an individual rule including a plurality of tests,

the computer usable program code, upon being executed by a computer hardware system, causing the computer hardware system to perform

identifying a plurality of relationships, each identified relationship is between a plurality of tests respectively associated with different conditions;

translating each individual rule of the plurality of rules into a coded series of one or more loops and tests; and

unifying the loops and the test from each individual rule of the plurality of rules into a unified series of loops and tests for the ruleset, wherein

the unifying based upon the identified plurality of relationships.

14. The computer-readable storage medium of claim 13, wherein

one of the identified plurality of relationships is a disjoint.

15. The computer-readable storage medium of claim 14, wherein

the plurality of tests respectively associated with the disjoint relationship are unified into a switch test.

16. The computer-readable storage medium of claim 13, further comprising

translating the unified series of loops and tests into a pattern matching code for the ruleset;

and

evaluating an object set using the pattern matching code for the ruleset.

17. The computer-readable storage medium of claim 16, further comprising

generating auxiliary code, distinct from the pattern matching code, including coded object manipulations and rule actions;

and

performing the object manipulations and the rule actions on an object in the object set using the auxiliary code.

18. The computer-readable storage medium of claim 13, wherein

each identified relationship having a type selected from the group consisting of equality, complement, subsumption, disjoint, and unrelated.