Rule processing system

• US 7,430,548 B2
• Filed: 02/27/2007
• Issued: 09/30/2008
• Est. Priority Date: 03/21/2001
• Status: Expired due to Term

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Verde Sabor Assets LLC (Intellectual Ventures LLC)
• Inventors: Mair, Douglas M., Huelsman, David L., Love, Sharon E.
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US11/710,972
• Publication Number:
  US 20070150429A1
• Time in Patent Office: 581 Days
• Field of Search: 706/47, 706/46, 706/14, 716/4
• US Class Current: 706/47
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A rule processing apparatus includes modules for defining/entering attributes, enumerations, and/or relationships; packaging the definitions in a reduced canonical form suitable for propositional logic manipulation using zero-suppressed binary decision diagrams (Zdd) to produce a prime Zdd; and/or (iii) executing the rule by applying a series of user inputs to the prime Zdd to determine a result that preferably includes conflict and selection advice to guide the user to satisfaction. Elective events, such as but not limited to the display of messages or the performance of calculations, may optionally be packaged along with the prime rule or components thereof, and presented during execution to help guide the end user to satisfaction or compliancy when choosing among possible selections. The apparatus automates determination of a complex rule having a combinatorial exploded number of rule components, or a combinatorial number of possible outcomes, exceeding computational capacity of present day computing systems.

Claims

1. A rule model for use in a rule processing system, said rule model comprising a digital representation of a zero-suppressed binary decision diagram (ZDD) formed by manipulatively combining an Include ZDD rule component that indicates inclusive constraints of said rule model, an Exclude ZDD rule component that indicates exclusive constraints of said rule model, and an Attribute Relations ZDD constructed from said Include and Exclude rule components that indicates interrelations between attributes of said Include and Exclude ZDD rule components;

and a memory that stores said rule model for subsequent access during rule processing, said rule model being operative with a digital processor to provide a user with a result in response to user inputs characterizing desired constraints of said rule model.

2. The invention of claim 1, wherein the rule model represents a business or engineering rule and said inclusive constraints comprise included or true relations between an attribute and an enumeration value of said business or engineering rule and said exclusive constraints comprise excluded or false relations between an attribute and an enumeration value of said business or engineering rule.

3. The invention of claim 2, further comprising an Elective Events ZDD component manipulatively combined with said rule model to invoke a data processing event in response to selection by a user of a predetermined combination of constraints of said rule model.

4. The invention of claim 3, wherein said event comprises communicating a message to said user.

5. The invention of claim 3, wherein said event comprises performing a calculation to produce a result and indicating said result to said user.

6. The rule model recited in claim 2, wherein respective Include and Exclude ZDD rule components have associated attributes and enumeration values thereof selected by a rule modeler.

7. The invention of claim 6, wherein attributes and enumeration values thereof have an assigned indexed order and said ZDD rule model is constructed from ordered indices of attributes and enumeration values and stored in said memory in a reduced canonical form according to ordered indices.

8. The invention of claim 7, wherein the ZDD rule model has an initial size defined by a number of nodes, which nodes are subsequently reordered to reduce the size of the ZDD rule model.

9. The invention of claim 8, wherein nodes of the Include and Exclude ZDD components of said ZDD rule model are separately reduced prior to manipulatively combining said Include, Exclude, and Attribute Relations ZDD rule components.

10. A rule model representing a business or engineering rule for use in a rule processing system, said rule model comprising a digital representation of a zero-suppressed binary decision diagram (ZDD) formed by manipulatively combining an Include ZDD rule component that indicates positive constraints of said rule model, an Exclude ZDD rule component that indicates negative constraints of said rule model, and an Attribute Relations ZDD constructed from said Include and Exclude rule components to indicate interrelations of attributes of said Include and Exclude ZDD rule components, and an Elective Events ZDD component that during processing of said rule model invokes an event in response to selection by a user of a predetermined combination of constraints of said rule model, said attributes and enumeration values thereof having an assigned indexed order within said ZDD rule model;

and a memory for storing said ZDD rule model in a memory in reduced canonical form according to said ordered indices.

11. A computer-implemented method to enable a rule modeler to convert a business or engineering rule into a ZDD rule model comprising:

providing a cross-reference table of attributes and enumeration values indicative of rule components of said business or engineering rule,

enabling the modeler to define components of said rule by selecting an inclusive or exclusive relation between said attributes and enumeration values in respective rows and columns of said table,

forming an Include ZDD rule component from said inclusive relations,

forming an Exclude ZDD rule component from exclusive relations,

producing an Attribute Relations ZDD rule component based on said Include and Exclude rule components,

constructing said ZDD rule model based on said Include, Exclude, and Attribute Relations rule components, and

storing said ZDD rule model in a memory for subsequent use in a rule processing system.

12. The method of claim 11, wherein said constructing step include assigning an order to elements of said rule components to established ordered indices and said storing step includes storing said rule model in reduced canonical form according to said ordered indices.

13. The method of claim 12, wherein said table comprises a cross-reference matrix of attributes and related enumeration values.

14. The method of claim 12, further including:

enabling said modeler to define elective events according to a predetermined combination of attribute and enumeration values, which events are operative to invoke data processing to effect display of a message or performance of a calculation for communication to a user.

15. The method of claim 11 wherein said Include and Exclude rule components each have a number of nodes in their respective ZDD representations indicative of complexity and said method further includes reordering the nodes to reduce the complexity of the ZDD representations.

16. The method of claim 15, further comprising reordering said nodes prior to manipulatively combining the components to construct the ZDD rule model.