Rule processing system

• US 7,188,091 B2
• Filed: 03/20/2002
• Issued: 03/06/2007
• Est. Priority Date: 03/21/2001
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Resolution EBS, Inc.
• Inventors: Mair, Douglas M., Huelsman, David L., Love, Sharon E.
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US10/101,154
• Publication Number:
  US 20030220926A1
• Time in Patent Office: 1,812 Days
• Field of Search: 706/47, 706/46, 706/14
• 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 processing device comprising:

a digital representation of a zero-suppressed binary decision diagram (Zdd) representing a rule,

an execution engine comprising a processor that generates a traversal Zdd (¶

¶

62, 106) according to inputs of a user to traverse the zero-suppressed binary decision diagram in order to produce a result indicative of satisfiability of the rule, and

an advice module operative to provide to said user at least one of selection and conflict advice along with the result in order to guide the user in obtaining satisfiability of the rule according to various inputs where conflict advice (¶

¶

112, 109, 47) identifies at least one user input preventing satisfiability and selection advice identifies at least one other input establishing satisfiability.

2. A rule processing system comprising:

a digital representation of a rule defined by ordering of respective relationships between attributes of components of said rule and enumerations of said attributes, as well as ordering of relationships between said attributes,

a relational representation of said ordering in the form of a decision diagram,

an input device that obtains variable inputs from a user related to said attributes and enumerations, and

an execution engine including a processor responsive to the inputs and the relational representation to produce and communicate to said user a result indicative of satisfiability of the rule relative to the inputs of said user.

3. The system of claim 2, wherein said execution engine provides at least one of selection and conflict advice along with the result.

4. A rule processing system that automates determination of a decision based on a rule, said system comprising:

a rule definition device that enables assignment of an order to parameters of a rule having multiple interrelated rule components,

a rule packaging device that produces an ordered, directed acyclic graphic representation of the rule in a digital form wherein said graphic representation includes ordered rule components indicative of the interrelated rule components, and

an execution engine including a processor operative to traverse the acyclic graphical representation with a traversal directed acyclic graphic representation derived from a series of variable user inputs related to an assigned ordering in order to generate and communicate to a user a result indicative of satisfaction of the rule according to inputs of said user.

5. The system of claim 4, wherein each of said directed acyclic graphic representations comprises a zero-suppressed binary decision diagram.

6. The system of claim 5, wherein the execution engine provides conflict and selection advice along with the result to guide said user in selecting inputs that satisfy the rule.

7. A decision automation apparatus comprising:

a digital representation of a rule that comprises a series of ordered parameters indicative of relationships between or among attributes and enumerations of the rule,

a set of user inputs being associated with the ordered parameters, and

an execution engine that includes a processor that generates a traversal diagram from the set of user inputs to traverse the representation in order to produce a result indicative of rule satisfaction.

8. The apparatus of claim 7, wherein said execution engine provides at least one of selection and conflict advice to guide a user in a selection of inputs.

9. The apparatus of claim 7, wherein the representation comprises a zero-suppressed binary decision diagram.

10. A decision automation system that determines the outcome of a decision processing using a prime rule model derived from a set of rule components, said system comprising:

a rule entry module to enable definition of a first set of relationships between attributes and enumerations of said attributes along with a second set of relationships between relationships of said first set in order to characterize the rule components,

a packaging module that orders the attributes and enumerations to provide a basis to uniquely define ordered rule components indicative of said prime rule model,

a translation module that translates the ordered rule components along with the first and second sets of relationships to a digital representation of a reduced canonical polynomial,

a packaging module that accesses the reduced canonical polynomial to build a set of zero-suppressed binary decision diagrams respectively indicative of the rule components and relationships thereof in order to produce a representation of the prime rule model, and

an execution module that applies a representation of user inputs to the prime rule model to produce a result.

11. The system of claim 10, wherein the rule components comprise include components and exclude components, and said packaging module includes program instructions to separately build respective sets of zero-suppressed binary decision diagrams from the include and exclude components.

12. The system of claim 11, wherein said execution module provides at least one of selection and conflict advice to guide a user in selecting said inputs.

13. The system of claim 11, wherein said packaging module includes program instructions to effect reordering of nodes of the binary decision diagram to reduce the complexity thereof.

14. The system of claim 12, wherein the execution module communicates messages to said user in response to certain conditions obtained during rule processing.

15. The system of claim 12, wherein the execution module performs a calculation in response to certain conditions obtained during rule processing and communicates results of said calculation to said user.

16. A computer-readable medium to enable computer assessment of satisfiability of a rule based on variable inputs of a user and a set of relationships between attributes and enumerations of said rule, the medium comprising:

a first program module that converts the rule to a canonical storage database that includes uniquely addressable records indicative of the relationships,

a second program module that produces a series of binary decision diagrams based on records of the canonical storage database,

a third program module operative to combine the binary decision diagrams to form a prime binary decision diagram indicative of multidimensional relationships of said rule, and

a fourth program module to enable traversal of the prime binary decision diagram by a traversal binary decision diagram defined by said variable inputs to determines a condition of satisfiability of the rule and to communicate said condition to said user, said representation being based on a set of attributes and enumerations of said rule selected by said user.

17. The computer-readable medium of claim 16, including a fifth program module that reorders nodes of the prime binary decision diagram to minimize complexity of the multidimensional relationship.

18. The computer-readable medium of claim 16, including a sixth program module that separately produces binary decision diagrams from said canonical storage database according to include rules, exclude rules, and relationships between attributes.

19. The computer-readable medium of claim 18, further including a seventh program module that provides conflict and selection advice to a user to help guide said user in obtaining satisfiability of said rule.

20. A decision automation system that provides decision support for a complex rule predicated on a set of component rules each of which defining a relationship between one or more attributes and properties of said attributes, the system comprising:

a rule entry device the enables development of a series of relationship diagrams representing the component rules by forming ordered entries in a matrix, said entries being indicative of inclusion, exclusion, or a null condition relative to a relationship between at least one attribute and at least one property of said attribute,

a BDD module that generates respective binary decision diagrams for each of the respective component rules based on the relationship diagrams, said binary decision diagrams including respective node representations that correspond to the ordered entries of the respective relationship diagrams;

a packaging module that forms a master interrelationship diagram representative of the combined set of component rules by combining the respective binary decision diagrams representative of the component rules; and

an execution module that deploys the master interrelationship diagram in a decision processor to provide said decision support to a user via an indication of satisfiability of said complex rule relative to a variable set of attributes and properties supplied by a said user.

21. A system that provides rule processing to automate determination of a result of processing a complex rule predicated on a set of component rules each of which defining a relationship between attributes and properties of said attributes, the system comprising:

a segmenting routine that segments the complex rule into component rules that represent relationships between said attributes and properties,

a relational diagram module that develops a number of relationship diagrams representing the component rules by forming positional entries in a matrix representation, said entries being indicative of an inclusive, exclusive, or a null condition relative to a relationship between said attributes and properties,

a BDD module that generates respective binary decision diagrams for each of the respective component rules based on the relationship diagrams, said binary decision diagrams including respective nodal representations that correspond to the positional entries of the respective relationship diagrams;

a prime rule module that forms a master interrelationship diagram representative of the combined set of component rules by combining the respective binary decision diagrams representative of the component rules; and

an execution module that deploys a digital representation of the master interrelationship diagram in a decision processor to provide decision support to a user via an indication of satisfiability of said master interrelationship diagram relative to a given set of attributes and properties supplied by said user.

22. The system of claim 21, wherein the execution module:

enables said user to access the decision processor via a user interface,

displays a set of parameters associated with the component rules,

provides selectable choices among said parameters,

processes choices selected by said user to test satisfiability of said master interrelationship diagram, and

communicates to the user an indicia of satisfiability according to a selected choice of parameters.

23. The system of claim 22, wherein the execution module provides an indication of conflict between selected parameters.

24. The system of claim 22, wherein the execution module provides selection advice that identifies which parameters to change to render the master interrelationship diagram satisfied.

25. The system of claim 22, wherein the execution module communicates to said user one or messages and calculations associated with choices selected by the user.

26. The system of claim 21, wherein the BDD module generates zero-suppressed binary decision diagrams based on the master relationship diagrams.

27. A rule-based processing system that obtains a representation of a master interrelationship diagram representing a business rule that comprises a set of interrelated rule components defining a relationship between at least one attribute and at least one property of said attribute, generates binary decision diagram based on various sets of inputs supplied by a user, and uses said binary decision diagrams to test satisfiability of the master interrelationship diagram and to communicate results of tests to said user.

28. The rule-base processing system of claim 27, wherein said binary decision diagram comprises a zero-suppressed binary decision diagram.

29. The rule-base processing system of claim 28, that further provides an indication of which rule component creates incompatibility among inputs supplied by said user when satisfiability is not achieved.

30. The rule-base processing system of claim 29, that further provides at least one selectable option to said user to vary a parameter of a rule component to render the master interrelationship diagram satisfied.

31. A rule-based processing apparatus comprising a program module that produces a representation of a binary decision diagram representing a rule, that tests the representation to determine a condition of satisfiability under multiple sets of inputs representing parameters of the rule, and in response to an unsatisfied condition for each said set, that indicates to a user a selection of at least one parameter that renders the representation satisfied.

32. A computer-readable medium comprising a stored program module executable by a computer to obtain a representation of a zero-suppressed binary decision diagram representing a rule, to test the representation to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to a testing, to indicate to a user a relationship with respect to parameters of said rule to render the representation satisfied or unsatisfied.

33. A rule-based processing system comprising a first executable module that obtains a representation of a binary decision diagram (Bdd) representing a rule, a second executable module that tests the representation to determine and provide to a user a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to the testing, a third executable module that further provides to said user at least one other parameter to change in order to render the representation satisfied or unsatisfied.

34. A rule-based processing system comprising a first executable module that produces a representation of a series of relational diagrams that represent multiple rule components, a second executable module that converts the series of relational diagrams to a directed acyclic graph (DAG) representing a prime rule, a third executable module that tests the DAG to determine a condition of satisfiability under a given set of inputs representing parameters of the multiple rule components, and in response to an unsatisfied condition, a fourth executable module that provides to a user least one other parameter to change in order to render the multiple rule components satisfied.

35. A system that determines compliance of a rule, said system comprising a digital representation of a zero-suppressed binary decision diagram to represent the rule, said zero-suppressed binary decision diagram being derived from components of said rule that indicate an inclusive, exclusive, or a null condition relative to relationships between one or more parameters of said rule, and an execution engine that separately accesses and processes include and exclude representations of the zero-suppressed binary decision diagram to determine compliance of the rule based on a given set of input parameters supplied by a user and to communicate an indication of said compliance to said user.

36. The system as recited in claim 35, wherein the parameters comprise attributes and enumerations of said attributes.

37. The system of claim 35, wherein said execution engine effects further testing of the zero-suppressed binary decision diagram to determine conflicting and satisfying rule parameters for communication to said user.

38. The system of claim 35, wherein said execution engine provides messages associated with certain conditions.

39. A system that automates determination of a decision in accordance with a prime rule, the system comprising a computer-implemented rule processing module that obtains a representation defining relationships between at least one attribute and a property of said attribute in the form of a zero-suppressed binary decision diagram, an execution module that tests for a condition of satisfiability of said prime rule via a traversal of said zero-suppressed binary decision diagram by a secondary traversal Zdd defined by inputs of a user, and a communication module that indicates said condition of satisfiability to a user.

40. A rule compliance system that analyzes a set of parameters of a business rule in order to determine compliance, said system comprising:

a retrieval module that accesses a digital representation of a binary decision diagram (Bdd) indicative of said business rule,

a user access terminal to enable a user to supply inputs via a user interface, and

an execution engine responsive to the retrieval module and the user access terminal to produce a result, that provides said user with selectable choices of parameters of said business rule, that processes choices selected by the user to generate a traversal Bdd based on said choices to test satisfaction of said business rule, and that communicates to the user an indicia of compliance or non-compliance of a selected choice of parameters.

41. The system of claim 40, wherein said execution engine further provides an indication of conflict between selected parameters.

42. The system of claim 40, wherein said binary decision diagrams are zero-suppressed.

43. A rule-based processing system that automates determination of a decision, said system comprising a representative form of a binary decision diagram (Bdd) indicative of a business rule, said business rule comprising a set of interrelated rule components that defines a relationship between at least one attribute and at least one property of said attribute, a database that stores a representation of said binary decision diagram, an execution engine that accesses said database and tests for conditions of satisfiability of the binary decision diagram using a secondary traversal Bdd defined by a user, and an output that indicates said conditions of satisfiability to a user.

44. The processing system of claim 43, wherein the binary decision diagram comprises a zero-suppressed binary decision diagram (Zdd).

45. The processing system of claim 43, wherein the execution engine provides to said user on a display monitor an indication of which rule component creates a conflict in response to a test of satisfiability.

46. The processing system of claim 43, wherein the execution engine provides said user with at least one selectable option to vary a property of a rule component of said business rule to render the Zdd satisfied.

47. The processing system of claim 44, wherein the execution engine provides the user with at least one selectable option to vary a property of a rule component of said business rule to render the Zdd satisfied.

48. A rule-based processing system that processes a digital representation of a zero-suppressed binary decision diagram (Zdd) that represents a rule, said system comprising a user terminal that enables access to said Zdd to determine a condition of satisfiability under a given set of inputs representing parameters of the rule, and in response to an unsatisfied condition, that indicates to a user a selection of a relationship with respect to at least one parameter of said rule that renders the rule satisfied.

49. A rule-based processing system comprising a digital representation in a memory of a zero-suppressed binary decision diagram that represents a rule, a program module that effects accessing the memory to invoke a test of whether the rule is satisfied under a given set of inputs that represent relationships among parameters of the rule, and in response to said test, said program module effects a routine that indicates to a user at least one parameter to change in order to render the rule satisfied.

50. A rule-based processing system comprising a representation of a series of binary decision diagrams that respectively represent multiple rule components, a first program module that effects conversion of the series of binary decision diagrams to a master binary decision diagram representing a master rule, a second program module that effects testing of the master rule through the master binary decision diagram to determine a condition of satisfiability under a given set of inputs representing parameters of the multiple rule components, and in response to an unsatisfied condition, a third program module that effects identification for a user of at least one other parameter that renders the master rule satisfied.