Rule selection engine

• US 7,433,858 B2
• Filed: 01/26/2004
• Issued: 10/07/2008
• Est. Priority Date: 01/26/2004
• Status: Active Grant

• Current Assignee: Trigent Software Ltd.
• Original Assignee: Trigent Software, Inc.
• Inventors: Rehberg, Charles Patrick, Porter, Steve Sherwood
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US10/765,461
• Publication Number:
  US 20050165707A1
• Time in Patent Office: 1,716 Days
• Field of Search: 706/45, 706/50, 706/55, 706/47, 706/61, 706/59, 395/52
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A rules-based system makes use of a specification that is similar to those used in earlier systems, such as in OPS5, but does not require the computational complexity of implementations such as Rete. In some such implementations, matching of the applicable rules given a set of facts is simplified by providing preallocated storage locations for the Boolean values of the condition elements for each rule. The Boolean values are set by direct processing of each of the facts. These preallocated storage locations are arranged to allow efficient evaluation of the overall condition of each of the rules in a manner that is significantly more efficient than implementations of earlier rule-based systems.

Claims

1. A computer-implemented method for processing rules, the method comprising:

providing a static data structure (125) and a dynamic data structure (135) for processing rules,

wherein the static data structure represents rules in a rules base and the dynamic data structure includes storage locations for working data produced by processing external facts according to the rules represented in the static data structure,

wherein each rule in the rules base is specified according to a set of condition elements, and for each rule the static data structure includes a data vector (256) for said rule such that each element (257) of said vector is associated with a different one of the condition elements according to which the rule is specified, and

the dynamic data structure includes a corresponding vector of storage locations (242) for said rule such that each storage location (243) of said vector corresponds to a different one of the elements (257) of the data vector (256) for said rule in the static data structure (125) and is associated with a different one of the condition elements according to which the rule is specified;

processing a plurality of facts, including accepting a current fact (200) and storing values resulting from evaluation of condition elements that depend on the current fact in storage locations (243) of the dynamic data structure (135) associated with said condition elements; and

determining whether a rule of the rules base is applicable by comparing the elements (257) of the data vector (256) in the static data structure (125) for said rule with the values stored in the corresponding storage locations (243) in the dynamic data structure (135) for said rule.

2. The method of claim 1 wherein each data vector (256) comprises a bit vector such that each element (257) of the bit vector for a rule in the static data structure (125) is represented as a single bit and each vector of storage locations (242) comprises a storage bit vector such that each storage location (243) of the storage bit vector in the dynamic data structure consists of a single bit location;

and

wherein comparing the elements (257) of the data vector (256) for a rule with the values stored in the vector of storage locations (242) in the dynamic data structure (135) for said rule comprises comparing two bit vectors.

3. The method of claim 1 wherein the static data structure (125) further includes a condition element table (230) that includes a plurality of condition element entries (232) such that each condition element entry is associated with a condition element and identifies one or more storage locations (243) in the dynamic data structure (135) that are associated with said condition element;

and

wherein processing the plurality of facts further includes identifying the storage locations (243) for storing the values resulting from evaluation of the condition elements using condition element entries (232) of the condition element table.

4. The method of claim 1 wherein the static data structure (125) further includes a feature table (220) that includes a plurality of entries (222) such that each entry is associated with a different identifier/attribute and includes one or more elements (226) that each identifies a condition element represented in the static data structure (125) that depends on said identifier/attribute;

and

wherein processing the plurality of facts further includes determining entries (222) of the feature table (220) associated with the current fact and determining condition elements for evaluation according to the elements (226) of said entries (222).