Rule processing methods for automating a decision and assessing satisfiability of rule-based decision diagrams

• US 6,965,887 B2
• Filed: 03/20/2002
• Issued: 11/15/2005
• 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): Knight, Anthony
• Assistant Examiner(s): Bell, Meltin
• Application Number:
  US10/101,151
• Publication Number:
  US 20040260667A1
• Time in Patent Office: 1,336 Days
• Field of Search: 706/925, 706/8, 706 56- 58, 706 46- 48, 706/19, 705/2, 705/7, 705/50, 705/26, 705 36- 37, 703 2- 4, 703/6, 703/17, 703 22- 23, 707/10, 707/102, 707/2, 709/203, 709/219, 715/971, 702/82, 712/216, 340/2.1
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: Y10S 706/925 Business
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of rule processing includes 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 invention 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 computer-implemented method of rule processing comprising:

producing a zero-suppressed binary decision diagram representing a rule,

generating a traversal Zdd from user inputs and applying said traversal Zdd to the binary decision diagram to produce a result indicative of satisfiability of the rule, and

providing at least one of selection and conflict advice along with the result.

2. A computer-implemented method of rule processing comprising:

ordering components of a rule defined by relationships between attributes and enumerations thereof, and by relationships between attributes,

producing a relational representation of order components of the rule suitable for logic processing,

inputting a graphical representation related to the attributes and enumerations, and

applying the graphical representation to the relational representation to produce a result indicative of satisfiability of the rule relative to the inputs.

3. The method of claim 2, further comprising:

providing at least one of selection and conflict advice along with the result.

4. A computer-implemented method of automating a decision based on a rule, said method comprising:

assigning an order to parameters of a rule having multiple interrelated rule components,

providing an ordered, directed acylic graphical representation of the rule wherein said graphic representation includes ordered rule components indicative of the interrelated rule components,

applying to the acylic graphical representation a traversal graphical representation based on a series of user inputs having parameters related to an assigned ordering,

producing a result indicative of satisfaction of the rule relative to the user inputs, and

communicating the result to a help guide in selecting inputs to achieve satisfaction.

5. The method of claim 4, wherein the directed acylic graphic representation comprises zero-suppressed binary decision diagrams.

6. The method of claim 5, further comprising:

providing conflict and selection advice along with the result to guide selection of user inputs.

7. A decision automation method implemented during data processing, said method comprising:

defining a rule to be processed,

constructing a model of the rule that includes a series of ordered components indicative of relationships between attributes and enumerations of the rule,

generating a rule model embodying ordered components,

generating a representation of inputs in the form of a traversal graph, and

applying the traversal graph to the model to produce a result for a user indicative of rule satisfaction.

8. The decision automation method of claim 7, further comprising:

providing at least one of selection and conflict advice to guide a user'"'"'s selection of inputs.

9. The decision automation method of claim 8, wherein the constructing step includes constructing a series of zero-suppressed binary decision diagrams representing the series of ordered components.

10. A computer-implemented method of automating determination of a decision based on a prime rule model based on a set of rule components, said method comprising:

defining attributes and enumeration along with relationships between said attributes and enumerations that characterize the prime rule model,

ordering the attributes and enumerations to provide a basis to uniquely define ordered rule components,

translating the ordered rule components to a reduced canonical polynomial,

accessing the reduced canonical polynomial to build a set of zero-suppressed binary decision diagrams respectively indicative of the rule components and relationships thereof,

combining the binary decision diagrams to produce a representation of the prime rule model to be automated, and

applying inputs to the rule model to produce a result to guide a user.

11. The method of claim 10, further including separating the rule components into include components and exclude components and separately building said zero-suppressed binary decision diagrams for the include and exclude components.

12. The method of claim 11, further comprising:

providing at least one of selection and conflict advice to guide selection of user inputs.

13. The method of claim 12, further including associating messages upon encountering certain conditions during rule processing and communicating said messages to a user.

14. The method of claim 12, further including performing a calculation upon encountering certain conditions obtained during rule processing and communicating results of said calculation to a user.

15. The method of claim 11, further including reordering nodes of the binary decision diagram to reduce the complexity thereof.

16. A computer-implemented method of assessing satisfiability of a rule based on a set of relationships between attributes and enumerations associated with the attributes as well as on a set of relationships between attributes, the method comprising:

converting the rule to a canonical storage database that includes uniquely addressable records indicative of the relationships,

producing a series of binary decision diagrams based on the canonical storage database to represent the rule in an ordered form,

combining the binary decision diagrams to form a prime binary decision diagram indicative of multidimensional relationships,

generating a graphic representation of user inputs indicative of components of said rule, and

using the graphic representation to traverse the prime binary decision diagram to determine a condition of satisfiability of the rule for the purpose of testing the primary binary decision diagram using said user inputs.

17. The method of claim 16, wherein said combining step includes reordering nodes thereof to minimize complexity of the multidimensional relationship.

18. The method of claim 16, further comprising separately processing include rules, exclude rules, and relationships between attributes during the producing step.

19. The method of claim 18, further comprising providing conflict and selection advice.

20. A computer-implemented method of automating determination of a decision that is based on a complex rule predicated on a set of rule components each of which defines a relationship between one or more attributes and properties, the method comprising:

developing 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,

generating 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 in the respective relationship diagrams;

forming a master interrelationship diagram representative of a combined set of component rules by combining the respective binary decision diagrams representative of the rule components;

forming a traversal binary decision diagram based on user inputs; and

applying the traversal binary decision diagram to the master interrelationship diagram to provide decision support to a user via an indication of satisfiability of said complex rule relative to a given set of attributes and properties of the rule components.

21. A computer-implemented method of rule processing to automate determination of a result that is based on a complex rule predicated on a set of rules each of which defines a relationship between first and second attributes, the method comprising:

segmenting the complex rule into component rules that represent relationships between first and second attributes and properties,

developing a number of relationship diagrams representing the component rules by forming positional entries in a matrix representation, said entries being indicative of inclusion, exclusion, or a null condition relative to a relationship between at least one of the first and second attributes,

generating 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 in the respective relationship diagrams;

forming a master interrelationship diagram representative of the combined set of component rules by combining the respective binary decision diagrams representative of the rule components; and

deploying the master interrelationship diagram in a decision processor to provide decision support to a user via an indication of satisfiability of said primary rule relative to a given set of first and second attributes.

22. The method of claim 21, wherein the deploying step comprises:

enabling access to the decision processor via a user interface,

displaying a set of attributes associated with the rule components,

providing selectable choices among said attributes,

processing choices selected by a user to test satisfiability of said set of rules using the selected choices, and

communicating to the user an indicia of satisfiability of said rule with the selected attribute choices.

23. The method of claim 22, wherein said communicating step includes providing an indication of conflict between selected attributes.

24. The method of claim 22, further including providing selection advice that identifies which attributes change to render the complex rule satisfied.

25. The method of claim 22, further including communicating one or more messages and calculations associated with choices selected by the user.

26. The method of claim 22, further including communicating to the user via a network.

27. The method as recited in claim 22, wherein the developing step includes:

providing a user interface,

receiving first entries at the interface that represent the attributes, and

receiving second entries at the interface the represent properties of the attributes.

28. The method of claim 21, wherein the generating step includes generating zero-suppressed binary decision diagrams based on the relationship diagrams.

29. The method of claim 21, wherein the deploying step includes deploying the master interrelationship diagram to said decision processor via an Internet communication link.

30. A computer-implemented rule-based processing method of automating a decision for a user, said method comprising producing a representation of a master interrelationship diagram that represents a business rule composed of a set of interrelated rule components where each rule component defines a relationship between at least one attribute and at least one property of said attribute, generating a rule-based binary decision diagram based on the interrelationship diagram, forming an input-based binary decision diagram, and applying the input-based binary decision diagram to the ruled-based binary decision diagram to test satisfiability thereof and to communicate results of said test to said user in accordance with variation of a rule component.

31. The method of claim 30, wherein the generating step includes converting the binary decision diagram to a zero-suppressed binary decision diagram before the applying step.

32. The method of claim 31 wherein the producing step includes defining relationships between attribute and property pairs as one of valid, invalid, and null.

33. The method of claim 32, wherein the applying step includes providing an indication of which rule component creates a conflict in response to testing said rule-based binary decision diagram with a variation in a the rule component.

34. The method of claim 33, wherein the applying step includes providing at least one selectable option to vary another rule component to render the zero-suppressed binary decision diagram satisfied in response to the variation of the rule component.

35. The method of claim 32, wherein the applying step includes providing at least one selectable option to vary another rule component to render the zero-suppressed binary decision diagram satisfied in response to the variation of the rule component.

36. A computer-implemented rule-based processing method comprising obtaining a representation of a zero-suppressed binary decision diagram that represents a business rule, traversing the representation with an input-based representation to determine a condition of satisfiability of the rule under a given set of inputs that represent parameters of the rule, and providing a result of said traversing step to a user.

37. A computer-implemented rule-based processing method comprising obtaining a representation of a binary decision diagram that represents a rule, testing the representation with an input-based binary decision diagram to determine a condition of satisfiability under a given set of inputs representing parameters of the rule, and in response to an unsatisfied condition, providing to a user a selection of at least one parameter that renders the representation satisfied.

38. A computer-implemented rule-based processing method comprising obtaining a representation of a zero-suppressed binary decision diagram that represents a business rule, testing the representation with a user input based zero-suppressed binary decision diagram to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to said testing, identifying for a user a relationship with respect to parameters that renders the representation satisfied or unsatisfied.

39. A computer-implemented rule-based processing method comprising producing obtaining a representation of a binary decision diagram that represents a rule, testing the representation with a user-based set inputs to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to the testing, identifying for said user at least one other parameter that renders the representation satisfied or unsatisfied.

40. A computer-implemented rule-based processing method comprising producing a representation of a series of relational diagrams that represent multiple rule components, converting the series of relational diagrams to a directed acylic graph representing a prime rule, testing the prime rule with user-based inputs 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, identifying to a user at least one other parameter that renders the master rule satisfied.

41. A computer-implemented method of rule processing comprising:

obtaining from a user a set of inputs indicative of parameters that potentially satisfy a rule model represented by a binary decision diagram (BDD),

utilizing said inputs to generate a traversal BDD that is applied to said rule model to generate a result indicative of satisfiability of the rule model, and

communicating the result to said user.

42. The computer-implemented method of claim 41, further comprising, prior to the obtaining step, providing an interface to enable a rule modeler to generate the rule model.

43. The computer-implemented method of claim 42, wherein said BDD rule model and said traversal BDD each comprises a zero-suppressed binary decision diagram (ZDD).

44. The computer-implemented method of claim 43, further including the step of further utilizing said traversal BDD to provide at least one of selection and conflict advice to help guide the user in selecting alternative inputs to achieve satisfiability of said ZDD rule model when said result fails to indicate satisfiability.

45. The computer-implemented method of claim 44, wherein

said obtaining step includes obtaining inputs related to the attributes and enumerations of a rule, and

said utilizing step includes ordering components of the rule model to define relationships between attributes and enumerations thereof as well as relationships between attributes;

producing a relational representation of ordered components of the rule model suitable for logic processing; and

applying the inputs to the relational representation to produce the result.

46. The computer-implemented method of claim 45, wherein the rule model characterized by a zero-suppressed binary decision diagram comprises include rule components that indicate a positive relationship and exclude rule components that indicate a negative relationship, and said producing step includes building zero-suppressed binary decision diagrams separately for each of said include and exclude rule components.

47. The computer-implemented method of claim 45, wherein

said producing step comprises defining attributes and enumerations along with relationships between said attributes and enumerations to characterize the rule model, ordering the attributes and enumerations to provide a basis to uniquely define ordered rule components, translating the ordered rule components to a reduced canonical polynomial, accessing the reduced canonical polynomial to build said zero-suppressed binary decision diagrams indicative of said rule components, and combining the rule components to produce a representation of the ZDD rule model;

and

said utilizing step includes applying the inputs to the ZDD rule model to produce the result.

48. The computer-implemented method of claim 47, further including reordering nodes of the zero-suppressed binary decision diagrams to reduce the complexity thereof.

49. The computer-implemented method of claim 48, further including associating messages with components of said zero-suppressed binary decision diagrams and to communicate said messages to a user upon certain conditions of said inputs.

50. The computer-implemented method of claim 48, further including performing a calculation upon encountering certain input conditions obtained during rule processing and communicating results of said calculation to a user.

51. The computer-implemented method of claim 44, further including

converting the rule model to a canonical storage database that includes uniquely addressable records indicative of the relationships between attributes and enumerations that characterize the rule model,

producing a series of zero-suppressed binary decision diagrams based on the canonical storage database to represent relationships of the rule model in an ordered form,

combining the zero-suppressed binary decision diagrams to form a prime ZDD indicative of multidimensional relationships, and

processing the prime ZDD to determine a condition of satisfiability of the rule model based on a set of attributes and enumerations supplied thereto.