Rule processing system

• US 20030220926A1
• Filed: 03/20/2002
• Published: 11/27/2003
• Est. Priority Date: 03/21/2001
• 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., Love, Sharon E.
• Granted Patent: US 7,188,091 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 set of zero-suppressed binary decision diagram representing a rule,

an execution engine that receives user inputs for application to the set of binary decision diagram to produce a result indicative of satisfiability of the rule, and

an advice module that provides at least one of selection and conflict advice along with the result.

2. A rule processing system comprising:

a rule defined by ordering of respective relationships between attributes and enumeration thereof as well as ordering of relationships between respective attributes,

a relational representation of said ordering suitable for logic processing,

an input device that obtains a series of inputs related to said attributes and enumerations, and

an execution engine responsive to the inputs and the relational representation to produce a result indicative of satisfiability of the rule relative to the inputs.

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 comprising:

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

a rule packaging device that produces an ordered, directed acylic graphic representation of the rule wherein said graphic representation includes ordered rule components embedded therein indicative of the interrelated rule components, and

an execution engine that applies to the acylic graphical representation a series of user inputs having parameters related to an assigned ordering in order to produce a result indicative of satisfaction of the rule relative to the user inputs.

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

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

7. A decision automation apparatus comprising:

a 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 applies the set of user inputs to the representation to produce of 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'"'"'s 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 based on a prime rule model having a set of rule components, said system comprising:

a rule entry module to enable definition of attributes and enumeration along with relationships between said attributes and enumeration tot characterize the prime rule model,

a packaging module that orders the attributes and enumerations to provide a basis to uniquely define ordered rule components,

a translation module that translates the ordered rule components to a reduced canonical polynomial, and

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 and combines the binary decision diagrams to produce a representation of the prime rule model to be automated, and

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

11. The system of claim 10, wherein the rule components are separated into include components and exclude components and said zero-suppressed binary decision diagrams are separately build for the include and exclude rules.

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

13. The system of claim 11, wherein said packaging module reorders nodes of the binary decision diagram to reduce the complexity thereof.

14. The system of claim 12, wherein the execution module communicates messages to an end 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 communicating results of said calculation to a user.

16. An apparatus that assesses 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 apparatus comprising:

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

a second module that produces a series of binary decision diagrams based on the canonical storage database to represent relationships of the rule in an ordered form,

a third module that combines the binary decision diagrams to form a prime binary decision diagram indicative of multidimensional relationships, and

a fourth modules that executes the prime binary decision diagram in an decision processor to determines a condition of satisfiability of the rule by testing the primary binary decision diagram using a set of attributes and enumerations supplied thereto.

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

18. The apparatus of claim 16, including a sixth module that separately processes include rules, exclude rules, and relationships between attributes during the producing step.

19. The apparatus of claim 18, further including a seventh module that provides conflict and selection advice.

20. A decision automation system that provides decision based on a complex rule predicated a set of rule components each of which defining a relationship between one or more attributes and properties, 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,

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 in 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 rule components; and

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

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

a segmenting routine that segments the complex rule into component rules that represent relationships between first and second 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 inclusion, exclusion, or a null condition relative to a relationship between at least one of the first and second attributes,

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

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 rule components; and

an execution modules that deploys the master interrelationship diagram in a decision processor to provide decision support via an indication of satisfiability of said master interrelationship diagram relative to a given set of first and second attributes

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

enables access to the decision processor via a user interface,

displays a set of parameters associated with the rule components,

provides selectable choices among said parameters,

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

communicates to the user an indicia of satisfiability of said rule with the 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 modules provides selection advice that identifies which parameters to change to render the primary rule satisfied.

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

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

27. A rule-based processing system that produces 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, generates a binary decision diagram based on the interrelationship diagram, and tests satisfiability the binary decision diagram in accordance with variation of a rule component.

28. The rule-base processing system of claim 27, that converts the binary decision diagram to a zero-suppressed binary decision diagram before the testing step.

29. The rule-base processing system of claim 28, that further provides an indication of which rule component creates a conflict in response to said testing with a variation in of the rule component.

30. The rule-base processing system of claim 29, that further provides at least one selectable option to vary a rule component to render the zero-suppressed binary decision diagram satisfied in response to the variation of the rule component.

31. A rule-based processing apparatus that produces a representation of a zero-suppressed binary decision diagram to represent a rule and that tests the representation to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule.

32. A rule-based processing apparatus comprising a module that produces a representation of a binary decision diagram that represents a rule, that tests the representation 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 identifies a selection of at least one parameter that renders the representation satisfied.

33. A rule-based processing system comprising a modules that produces a representation of a zero-suppressed binary decision diagram to represent a rule, that tests the representation to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to said testing, that identifies a relationship with respect to parameters to render the representation satisfied or unsatisfied.

34. A rule-based processing system comprising a first module that produces a representation of a binary decision diagram that represents a rule, a second module that tests the representation to determine a condition of satisfiability under a given set of inputs that represent parameters of the rule, and in response to the testing, a third module that identifies at least one other parameter that renders the representation satisfied or unsatisfied.

35. A rule-based processing system comprising a first module that produces a representation of a series of relational diagrams that represent multiple rule components, a second modules that converts the series of relational diagrams to a directed acylic graph representing a prime rule, a third module that tests the prime rule 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 module that identifies least one other parameter that renders the master rule satisfied.

36. A system that determines compliance of a rule, said system comprising a zero-suppressed binary decision diagram to represent the rule, said zero-suppressed binary decision diagram being derived from rule components that indicate inclusion, exclusion, or a null condition relative to relationships between one or more parameters, and an execution engine that accesses the zero-suppressed binary decision diagram to determine compliance of the rule based on a given set of input parameters.

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

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

39. The system of claim 36, wherein said rule processing engine provides messages associated with certain conditions.

40. A system that automates a decision in accordance with a prime rule, the system comprising a rule processing module characterizing relationships among a set of rules that define relationships between at least one attribute and a property thereof, said rule processing module being representative of a zero-suppressed binary decision diagram, and an execution module that tests for a condition of satisfiability of said primey rule via the zero-suppressed binary decision diagram in accordance with selected attribute-properties relationship pairs of a rule.

41. A rule compliance system that analyzes a set of parameters to determine compliance with a set of rules, said system comprising:

a rule processing engine utilizing binary decision diagrams to represent the set of rules,

an access terminal that provides access to the rule processing engine to enable inputting of said rules via a user interface, and

an execution station that provides a result, said execution station including a monitor that communicates a set of parameters associated with the rules, that provides selectable choices among said parameters, that processing choices selected by the user by testing satisfaction of said set of rules, and that communicates the user an indicia of compliance or non-compliance of a selected choice of parameters.

42. The system of claim 41, wherein said execution station provides an indication of conflict between selected parameters.

43. The system of claim 41, wherein said binary decision diagrams are zero-suppressed.

44. A rule-based processing system for automating a decision comprising a rule processing engine that employs a representative form of an binary diagram interrelationship indicative of a business rule, said 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, a database that stores a representation of said interrelationship diagram, and a testing platform that tests for conditions of satisfiability of the binary interrelationship diagram in accordance with variation of said interrelated rule components.

45. The processing system of claim 44, wherein the binary diagram comprises a zero-suppressed binary decision diagram.

46. The processing system of claim 44, wherein the testing platform provides an indication of which rule component creates a conflict in response to said testing.

47. The processing system of claim 44, wherein the testing platform includes 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.

48. The processing system of claim 44, wherein the testing platform includes 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.

49. A rule-based processing system comprising a representation of a binary decision diagram that represents a rule, testing platform that determines a condition of satisfiability under a given set of inputs representing parameters of the rule, and in response to an unsatisfied condition, identifying a selection of a relationship with respect to at least one other parameter that renders the representation satisfied.

50. A rule-based processing system comprising a digital representation in a memory of a binary decision diagram that represents a rule, a routine that effects accessing the memory to invoke a test of whether the rules is satisfied under a given set of inputs that represent relationships among parameters of the rule, and in response to the testing, said routine initiates an identification of at least one other parameter that renders the representation satisfied.

51. A rule-based processing system comprising a representation of a series of binary decision diagrams that represent multiple rule components, a first routine that converts the series of binary decision diagrams to a master binary decision diagram representing a master rule, a second routine that tests 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 routine that identifies at least one other parameter that renders the master rule satisfied.