Method and system for sequential compilation and execution of rules

• US 20090228421A1
• Filed: 12/07/2006
• Published: 09/10/2009
• Est. Priority Date: 12/07/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Citeau, Hugues
• Granted Patent: US 7,809,666 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• 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 software arrangement operable on a processor, the software arrangement comprising at least one computer program which configures the processor to:

utilize a test analyzer to process a ruleset, the ruleset comprising a set of rules, each individual rule of the ruleset having conditions, each condition having tests, each pair of the tests having a relationship, the test analyzer having an output comprising a set of relationships between the tests;

temporarily store the output of the test analyzer;

translate each individual rule from the ruleset into a series of loops and tests; and

unify the loops and tests from each individual rule into a unified series of loops and tests using the temporarily stored output of the test analyzer and the relationships between the conditions.

2. The software arrangement of claim 1, wherein the at least one computer program further configures the processor to:

translate the unified series of loops and tests into a pattern matching code for evaluation by a virtual machine that processes the pattern matching code;

generate an auxiliary code, comprising a plurality of coded object manipulations and rule actions;

pass a plurality of objects to the virtual machine;

utilize the virtual machine to execute the pattern matching code upon the plurality of objects; and

utilize the virtual machine to call the auxiliary code to perform object manipulations and rule actions upon the plurality of objects.

3. The software arrangement of claim 1, wherein the set of relationships between the tests comprises equality, complement, subsumption, disjoint, and unrelated.

4. The software arrangement of claim 1, wherein the processor is further configured to:

temporarily store the output of the test analyzer in a data structure.

5. The software arrangement of claim 1, wherein the unified series of loops and tests further comprises an activation guard test step.

6. The software arrangement of claim 2, wherein the processor is further configured to:

write the pattern matching code in an int code.

7. The software arrangement of claim 2, wherein the pattern matching code comprises at least one of the following commands:

push-value, hash-jump, pop-value, jump, binary-jump, test-jump, type-jump, table-jump, value-foreach, value-next, push-memories, pop-memories, push-store, pop-store and rule-then.

8. The software arrangement of claim 2, wherein the processor is further configured to:

write the pattern matching code in an int-code, the int-code comprising at least the following commands;

push-value, hash-jump, pop-value, jump, binary-jump, test-jump, type-jump, table-jump, value-foreach, value-next, push-memories, pop-memories, push-store, pop-store and rule-then.

9. The software arrangement of claim 2, wherein the processor is further configured to:

utilize the virtual machine to call the auxiliary code by referring to an index assigned to each individual coded object manipulation and rule action.

10. The software arrangement of claim 2, wherein the processor is further configured to:

generate the auxiliary code in a byte code.

11. The software arrangement of claim 2, wherein the virtual machine is written in Java.

12. The software arrangement of claim 2, wherein the processor is further configured to:

generate the auxiliary code as Java byte code.

13. A method comprising:

utilizing a test analyzer to process a ruleset, the ruleset comprising a set of rules, each individual rule of the ruleset having conditions, each condition having tests, each pair of the tests having a relationship, the test analyzer having an output comprising a set of relationships between the tests;

temporarily storing the output of the test analyzer;

translating each individual rule from the ruleset into a series of loops and tests; and

unifying the loops and tests from each individual rule into a unified series of loops and tests using the temporarily stored output of the test analyzer and the relationships between the conditions.

14. The method of claim 13, further comprising the steps of:

translating the unified series of loops and tests into a pattern matching code for evaluation by a virtual machine that processes the pattern matching code;

generating an auxiliary code, comprising a plurality of coded object manipulations and rule actions;

passing a plurality of objects to the virtual machine; and

utilizing the virtual machine to execute the pattern matching code upon the plurality of objects; and

utilizing the virtual machine to call the auxiliary code to perform object manipulations and rule actions upon the plurality of objects.

15. The method of claim 13, wherein the set of relationships between the tests comprises equality, complement, subsumption, disjoint, and unrelated.

16. The method of claim 13, wherein the output of the test analyzer is temporarily stored in a data structure.

17. The method of claim 13, wherein the unified series of tests and loops further comprises an activation guard test step.

18. The method of claim 14, wherein the pattern matching code is written in an int code.

19. The method of claim 14, wherein the pattern matching code has at least one of the following commands:

push-value, hash-jump, pop-value, jump, binary-jump, test-jump, type-jump, table-jump, value-foreach, value-next, push-memories, pop-memories, push-store, pop-store and rule-then.

20. The method of claim 14, wherein the pattern matching code is written in an int-code, the int-code having at least the following commands:

push-value, hash-jump, pop-value, jump, binary-jump, test-jump, type-jump, table-jump, value-foreach, value-next, push-memories, pop-memories, push-store, pop-store and rule-then.

21. The method of claim 14, wherein the virtual machine calls the auxiliary code by referring to an index assigned to each individual coded object manipulation and rule action.

22. The method of claim 14, wherein the auxiliary code is generated in a byte code.

23. The method of claim 14, wherein the virtual machine is written in Java.

24. The method of claim 14, wherein the auxiliary code is generated as Java byte code.