Rule processing method and apparatus providing exclude cover removal to simplify selection and/or conflict advice

• US 20070094203A1
• Filed: 09/27/2006
• Published: 04/26/2007
• Est. Priority Date: 09/28/2004
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Verde Sabor Assets LLC (Intellectual Ventures LLC)
• Inventors: Huelsman, David, Mair, Douglas
• Granted Patent: US 7,734,559 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

An improvement in a computer-implemented rule processing method that provides conflict or selection advice to help guide a user achieve satisfiability of a business or engineering rule represented by a zero-suppressed binary decision diagram (ZDD) rule model. The improvement comprises obtaining at least one Exclude ZDD rule component from the ZDD rule model, identifying covers within the Exclude ZDD rule component, removing covers identified in the identifying step thereby to produce abridged Exclude ZDD rule component, determining satisfiability of the rule model utilizing the abridged Exclude ZDD component, and utilizing results of the determining step during automated decision support to help guide the user to attain satisfiability of the rule. An apparatus that implements the aforementioned method is also disclosed.

Claims

1. In a computer-implemented rule processing method that provides conflict or selection advice to help guide a user achieve satisfiability of a business or engineering rule represented by a zero-suppressed binary decision diagram (ZDD) rule model, an improvement comprising:

obtaining at least one Exclude ZDD rule component from the ZDD rule model,

identifying covers within said Exclude ZDD rule component,

removing covers identified in said identifying step thereby to produce an abridged Exclude ZDD rule component,

determining satisfiability of said rule model utilizing said abridged Exclude ZDD component, and

utilizing results of said determining step during automated decision support to help guide said user to attain satisfiability of said rule.

2. The improvement recited in claim 1, further comprising:

utilizing said abridged Exclude ZDD rule component to provide conflict and/or selection advice to said user.

3. The improvement recited in claim 2, wherein said removing step comprises the steps of:

expanding nodes in the Exclude ZDD to include all attributes specified in the business or engineering rule,

marking nodes associated with covers in said Exclude ZDD, and

removing covers and marked nodes from the Exclude ZDD thereby to produce said abridged Exclude ZDD.

4. The improvement recited in claim 3, further comprising NOR'"'"'ing the abridged Exclude ZDD with an Include ZDD of said business or engineering rule thereby to generate overall results for said conflict and selection advice.

5. The improvement recited in claim 4, wherein said expanding step includes renumbering nodes to provide insertion of marker nodes within an index sequence of initial nodes of said Exclude ZDD component.

6. The improvement of claim 5, wherein said removing step is carried out by separately performing removal operations on individual transitive closure sets of Exclude ZDD components and then combining the results of respective removal operations to produce the abridged Exclude ZDD.

7. The improvement of claim 6, wherein the step of removing covers and marked nodes comprises reordering nodes of the ZDD so that marker node groups appear at bottom of ZDD, removing nodes that point to same node as the marker node, removing marker nodes that point to a one node, and then reordering nodes of the ZDD back to initial index.

14. The improvement of claim 6 wherein said removal of covers and marked nodes comprises reordering nodes of the ZDD so that marker node groups appear at bottom of ZDD, removing nodes that point to same node as the marker node, removing marker nodes that point to a one node, and then reordering nodes of the ZDD back to initial index.

8. In a computer-implemented rule processing apparatus that provides conflict or selection advice to help guide a user achieve satisfiability of a business or engineering rule represented by a zero-suppressed binary decision diagram (ZDD) rule model, an improvement comprising:

cover removal module to remove covers in the ZDD rule model, said cover removal module including program instructions to effect in said processing apparatus the identification of covers within said Exclude ZDD rule component, the removal of covers so identified thereby to produce an abridged Exclude ZDD rule component, the determination of satisfiability of said rule model utilizing said abridged Exclude ZDD component, and the utilization of results of said determination during automated decision support to help guide said user to achieve satisfiability of said rule.

9. The improvement of claim 8 wherein said cover removal module effects utilization of said abridged Exclude ZDD rule component to provide conflict and/or selection advice to said user.

10. The improvement of claim 9 wherein said cover removal module effects removal by:

expanding nodes in the Exclude ZDD to include all attributes specified in the business or engineering rule,

marking nodes associated with covers in said Exclude ZDD, and

removing covers and marked nodes from the Exclude ZDD thereby to produce said abridged Exclude ZDD.

11. The improvement of claim 10 wherein said cover removal module effects NOR'"'"'ing of the abridged Exclude ZDD with an Include ZDD of said business or engineering rule thereby to generate overall results for said conflict and selection advice.

12. The improvement of claim 11 where said expanding includes renumbering nodes to provide insertion of marker nodes within a sequence of initial nodes of said Exclude ZDD component.

13. The improvement of claim 12 wherein said removing step is carried out by separately performing removal operations on individual transitive closure sets of Exclude ZDD components and then combining the results of respective removal operations to produce the abridged Exclude ZDD.

15. In a computer-implemented rule processing system that determines for a user satisfiability of a ZDD rule model indicative of a business or engineering rule, an apparatus comprising:

a first program module to obtain at least one Exclude ZDD rule component from said ZDD rule model,

a second program module to identify and remove cover details within said Exclude ZDD rule component whereby to produce an abridged Exclude ZDD rule component, and

an execution engine to determine satisfiability of said ZDD rule model utilizing said abridged Exclude ZDD rule component to provide results of said satisfiability to a user.

16. In a computer-implemented rule processing system to provide a determination of satisfiability of a business rule represented by a ZDD rule model, a computer-implemented method of reducing complexity of said determination comprising:

obtaining an Exclude ZDD representation of said rule model,

removing at least one cover from said Exclude ZDD representation thereby to generate an abridged Exclude ZDD representation, and

providing results of said determination to a user utilizing said abridged Exclude ZDD representation.