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

• US 7,734,559 B2
• Filed: 09/27/2006
• Issued: 06/08/2010
• 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: Mair, Douglas M., Huelsman, David L.
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US11/527,637
• Publication Number:
  US 20070094203A1
• Time in Patent Office: 1,350 Days
• Field of Search: 706/47, 703/7
• 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. A method, comprising:

storing instructions in a memory;

configuring a computing device to execute the instructions to;

obtain at least one Exclude zero-suppressed binary decision diagram (ZDD) rule component from a ZDD rule model representing a rule;

identify covers within the Exclude ZDD rule component;

remove identified covers to produce an abridged Exclude ZDD rule component by;

expanding nodes in the Exclude ZDD rule component to include all attributes specified in the rule;

identifying covers within the expanded nodes in the Exclude ZDD rule component;

marking nodes associated with the identified covers in the Exclude ZDD rule component; and

removing identified covers and marked nodes from the Exclude ZDD rule component to produce the abridged Exclude ZDD rule component;

determine satisfiability of the ZDD rule model based on the abridged Exclude ZDD rule component; and

generate one or more signals that provide graphical conflict advice to a user based on the satisfiability of the ZDD rule model to guide the user to achieve satisfiability of the rule.

2. The method of claim 1, further comprising configuring the computing device to execute the instructions to generate the one or more signals that provide the graphical conflict advice to the user based on the abridged Exclude ZDD rule component.

3. The method of claim 2, further comprising configuring the computing device to execute the instructions to NOR the abridged Exclude ZDD rule component with an Include ZDD of the rule to generate overall results.

4. The method of claim 3, further comprising configuring the computing device to execute the instructions to renumber nodes to provide insertion of marker nodes within an index sequence of initial nodes of the Exclude ZDD rule component.

5. The method of claim 4, further comprising configuring the computing device to execute the instructions to:

separately perform removal operations on individual transitive closure sets of the Exclude ZDD rule components; and

combine the results of respective removal operations to produce the abridged Exclude ZDD rule component.

6. The method of claim 5, further comprising configuring the computing device to execute the instructions to:

reorder nodes of the ZDD rule model so that marker node groups appear at a bottom of the ZDD rule model;

remove nodes that point to a same node as the marker node;

remove marker nodes that point to a one node; and

reorder nodes of the ZDD rule model back to an initial index.

7. A computer system, comprising:

a memory to store executable instructions including at least executable instructions to represent a rule using a zero-suppressed binary decision diagram (ZDD) rule model; and

a processor configured to execute the executable instructions stored in the memory to;

obtain at least one Exclude ZDD rule component from the ZDD rule model;

identify covers in the at least one Exclude ZDD rule component;

remove the identified covers from the at least one Exclude ZDD rule component to generate at least one abridged Exclude ZDD rule component by;

expanding nodes in the at least one Exclude ZDD rule component to include all attributes specified in the rule;

identifying covers within the expanded nodes in the at least one Exclude ZDD rule component;

marking nodes associated with the identified covers in the at least one Exclude ZDD rule component; and

removing identified covers and marked nodes from the at least one Exclude ZDD rule component to produce the at least one abridged Exclude ZDD rule component;

determine satisfiability of the ZDD rule model according to the at least one abridged Exclude ZDD rule component; and

provide graphical conflict information based on the determination of satisfiability of the ZDD rule model to achieve satisfiability of the rule represented by the ZDD rule model.

8. The system of claim 7, wherein the processor is further configured to NOR the at least one abridged Exclude ZDD rule component with an Include ZDD of the rule to generate overall results.

9. The system of claim 8, wherein the processor is further configured to renumber nodes to provide insertion of marker nodes within a sequence of initial nodes of the at least one Exclude ZDD rule component.

10. The system of claim 9, wherein the processor is further configured to separately remove individual transitive closure sets of the at least one Exclude ZDD rule component and combine results of respective separate removal operations to produce the at least one abridged Exclude ZDD rule component.

11. The system of claim 9, wherein the processor is further configured to:

reorder nodes of the ZDD rule model so that marker node groups appear at a bottom of the ZDD rule model;

remove nodes that point to a same node as the marker node;

remove marker nodes that point to a one node; and

reorder nodes of the ZDD rule model back to an initial index.

12. A computer-readable medium, comprising executable instructions, the instructions configured to instruct a computing device to:

obtain at least one Exclude ZDD rule component from a ZDD rule model representing a rule;

identify covers within the Exclude ZDD rule component;

remove identified covers to produce an abridged Exclude ZDD rule component by;

expanding nodes in the Exclude ZDD rule component to include all attributes specified in the rule;

identifying covers within the expanded nodes in the Exclude ZDD rule component;

marking nodes associated with the identified covers in the Exclude ZDD rule component; and

removing identified covers and marked nodes from the Exclude ZDD rule component to produce the abridged Exclude ZDD rule component;

determine satisfiability of the ZDD rule model based on the abridged Exclude ZDD rule component; and

provide graphical conflict information based on the satisfiability of the ZDD rule.

13. The computer-readable medium of claim 12, further comprising executable instructions configured to instruct the computing device to provide the graphical conflict information is further based on the abridged Exclude ZDD rule component.

14. The computer-readable medium of claim 12, further comprising executable instructions configured to instruct the computing device to NOR'"'"' the abridged Exclude ZDD with an Include ZDD of the rule to generate overall results.

15. The computer-readable medium of claim 12, further comprising executable instructions configured to instruct the computing device to renumber nodes to provide insertion of marker nodes within an index sequence of initial nodes of the Exclude ZDD rule component.

16. The computer-readable medium of claim 12, further comprising executable instructions configured to instruct the computing device to:

separately perform removal operations on individual transitive closure sets of the Exclude ZDD rule component; and

combine the results of respective removal operations to produce the abridged Exclude ZDD rule component.

17. The computer-readable medium of claim 12, further comprising executable instructions configured to instruct the computing device to:

reorder nodes of the ZDD rule model so that marker node groups appear at a bottom of the ZDD rule model;

remove nodes that point to a same node as the marker node;

remove marker nodes that point to a one node; and

reorder reordering nodes of the ZDD rule model back to an initial index.