Integration of declarative rule-based processing with procedural programming

• US 7,665,063 B1
• Filed: 05/26/2004
• Issued: 02/16/2010
• Est. Priority Date: 05/26/2004
• Status: Active Grant

• Current Assignee: Pegasystems Incorporated
• Original Assignee: Pegasystems Incorporated
• Inventors: Hofmann, Andreas G., Trefler, Alan
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): Nguyen; Phillip H
• Application Number:
  US10/854,017
• Time in Patent Office: 2,092 Days
• Field of Search: 717140-144
• US Class Current: 717/111
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

The present invention provides methods and systems for integrating a procedural computational model with a declarative computational model. For example, in one aspect, the present invention provides a method for integrating a plurality of procedural instructions in a procedural computational system with a plurality of declarative rules in a declarative computational system. In such a method, for each of the procedural instructions operating on one or more variables, a hash table indexed by variable names is utilized to determine whether any of these variables participate in at least one of the declarative rules. Upon execution of a procedural instruction that changes a variable participating in a declarative rule, other variables associated with the rule are updated so as to maintain a relationship imposed by the rule among the variables. The updating of the other variables is performed prior to execution of other procedural instructions.

Claims

1. A method of integrating one or more declarative rules into a plurality of procedural instructions in a procedural computational system, the method comprising the steps of:

executing, on a digital data processing system that comprises one or more digital data processors, a procedural sequence that comprises a plurality of procedural instructions,

updating, upon execution of a procedural instruction that causes change to one or more variables, one or more other variables participating in one or more declarative rules so as to maintain relationships imposed by said one or more rules among said variables,

wherein said one or more other variables are those not changed by the execution of that procedural instruction,

and wherein said rules are defined outside that procedural instruction, and

wherein said updating of said one or more other variables is performed by executing said rules on said digital data processing system prior to execution of any other procedural instruction in the sequence.

2. The method of claim 1, wherein said declarative rules are provided as textual expressions.

3. The method of claim 2, further comprising parsing said textual expressions for purposes of identifying input and output variables for one or more declarative rules.

4. The methods of claims 3, wherein said parsing step is accomplished by using a context-free grammar.

5. The method of claim 2, further comprising parsing said textual expressions for automatically generating any of dependency networks and associated hash tables, and rule execution code.

6. The method of claim 5, wherein said parsing step is accomplished by using a context free grammar.

7. The method of claim 5, further comprising utilizing an ATN (Augmented Transition Network) based parser to perform said parsing step.

8. The method of claim 1, wherein said declarative rules are expressed in a tabular form.

9. The method of claim 8, further comprising parsing said tabular form for identifying input and output variables.

10. The method of claim 8, further comprising parsing said tabular form for automated generation of dependency networks and associated hash tables.

11. The method of claim 10, further comprising parsing said textual expressions for automated generation of dependency networks and associated hash tables.

12. The method of claim 10, further comprising parsing said textual expressions for generating rule execution code.

13. The method of claims 10, further comprising using a context-free grammar to perform said parsing step.

14. The method of claim 8, further comprising parsing said tabular form for generating rule execution code.

15. The method of claim 1, wherein said declarative rules are expressed as procedures having defined inputs and outputs.

16. The method of claim 15, further comprising parsing said procedures for identifying input and output variables.

17. The method of claim 15, further comprising parsing said procedures for automated generation of dependency networks and associated hash tables.

18. The method of claim 17, further comprising utilizing an ATN (Augmented Transition Network) based parser to perform said parsing step.

19. The method of claim 15, further comprising parsing said procedures for generating rule execution code.

20. The method of claim 1, further comprising characterizing said declarative rules by a dependency network.

21. The method of claim 20, further comprising utilizing said hash table to determine a location in said dependency network at which a said variable participates in a declarative rule.

22. The method of claim 20, wherein said dependency network comprises a DAG dependency network.

23. The method of claim 22, wherein said step of updating values of other variables participating in said declarative rule comprises performing a forward search of said DAG dependency network.

24. The methods of claims 20, further comprising decompositing disconnected sub-graphs of the dependency network.

25. The method of claim 1, wherein said declarative rules form a simple formula declarative system.

26. The method of claim 25, further comprising characterizing said declarative rules by a DAG dependency network.

27. The method of claim 26, wherein said step of updating said one or more other variables participating in said declarative rule comprises performing a forward search of said DAG dependency network.

28. The method of claim 1, wherein said declarative rules form a multi-source directional declarative system.

29. The method of claim 28, further comprising characterizing said declarative rules by a dependency network.

30. The method of claim 29, further comprising converting said dependency network to a directed acyclic graph (DAG) in order to eliminate loops in said network.

31. The method of claim 30, wherein said updating step includes performing any of a forward and backward search of said DAG.

32. The method of claim 31, wherein said updating step includes utilizing an optimization algorithm with a cost function.

33. The method of claim 1, wherein said one or more declarative rules comprise a constrained declarative system.

34. The method of claim 33, wherein said updating step includes further comprising utilizing a constraint propagation algorithm.

35. The method of claim 34, wherein said constraint propagation algorithm comprises a linear programming algorithm.

36. The methods of claims 33, further comprising detecting unfeasible conditions.

37. The method of claim 36, further comprising generating suggestions for resolution of said unfeasible conditions.

38. The method of claim 37, further comprising saving said modified variables to a persistent storage.

39. The method of claim 38, where said persistent storage is a relational database.

40. The method of claim 38, where said persistent storage is an XML document.

41. The method of claim 38, where persistent storage is a relational database/XML combination.

42. The method of claim 37, where persistent storage is via an object database.

43. The method of claim 1, further comprising ascertaining a type of declarative system formed by said one or more declarative rules.

44. The method of claim 43, wherein said type of declarative system is any of a simple formula, multi-source directional, or a constrained system.

45. The method of claim 1, comprising determining whether said one or more variables participate in a at least one of said declarative rules by employing a hash table indexed by variable name.

46. A method of integrating one or more declarative rules into a procedural computational system supporting object-oriented representation of data, the method comprising the steps of:

executing, on a digital data processing system that comprises one or more digital data processors, a procedural sequence that comprises a plurality of procedural instructions,

updating, upon execution of a procedural instruction that causes change to one or more data in an object, one or more other data participating in one or more declarative rules so as to maintain relationships imposed by said one or more declarative rules among said data,

wherein said one or more other data (i) are those not changed by the execution of that procedural instruction, and (ii) are in said object and/or in other objects,

where said rules are defined outside that procedural instruction,

wherein updating of said one or more other data is performed by executing said rules on said digital data processing system prior to execution of any other procedural instruction in the sequence.

47. The method of claim 46, wherein said one or more declarative rules specify patterns of objects related by said rules.

48. The method of claim 47, further comprising utilizing variable designations to specify said patterns.

49. The method of claim 47, comprising determining whether said object participates in one or more declarative rules through matching of said object to object structure patterns specified in the one or more declarative rules.

50. The method of claim 49, comprising determining whether a said object participates in a declarative rule by utilizing a hash table organized according to the object structure of variable designations in a dependency network representing the rules.

51. The method of claim 46, wherein said one or more declarative rules are provided as textual expressions.

52. The method of claim 51, further comprising parsing said textual expressions for identifying input and output variables for the one or more declarative rules, and identifying required patterns of related objects referred to in such rules.

53. The method of claim 46, wherein said one or more declarative rules are expressed in a tabular form, with the table columns (or rows) representing properties of related objects, and table rows (or columns) representing different values, or ranges of values.

54. The method of claim 53, further comprising parsing said tabular form for identifying input and output variables of said one or more declarative rules.

55. The method of claim 54, wherein the hash table provides a node in the dependency network corresponding to one or more data that have been changed.

56. The method of claim 53, further comprising parsing said tabular form to identify related objects of the object in which the procedural instruction changed one or more data.

57. The method of claim 53, further comprising parsing said tabular form to for automated generation of dependency networks and associated hash tables.

58. The method of claim 53, further comprising parsing said tabular form for generating rule execution code.

59. The method of claim 46, further comprising computing an object property based on other properties in said object and/or based on properties in related objects.

60. The method of claim 46, wherein said one or more declarative rules are expressed as procedures having defined inputs and outputs, the inputs and outputs being properties of related objects.

61. The method of claim 60, further comprising parsing said procedures for any of identifying input and output variables, identifying required related objects, automatically generating dependency networks and associated hash tables, and generating rule execution code.

62. The method of claim 46, further comprising characterizing said one or more declarative rules by a dependency network, where the variables in the network are properties of objects.

63. The method of claim 62, further comprising utilizing a hash table to determine a location in said dependency network based on property designation at which a particular property of a specified object participates in a said declarative rule.

64. The method of claim 62, wherein said dependency network comprises a DAG dependency network.

65. The method of claim 64, wherein said step of updating said one or more other data comprises performing a forward search of said DAG dependency network.

66. The method of claim 62, further comprising decomposing disconnected subgraphs of the dependency network.

67. The method of claim 46, wherein said one or more declarative rules form a simple formula declarative system.

68. The method of claim 67, further comprising characterizing said one or more declarative rules by a DAG dependency network.

69. The method of claim 68, wherein said step of updating said one or more other data comprises performing a forward search of said DAG dependency network.

70. The method of claim 46, wherein said one or more declarative rules comprise a multi-source directional declarative system.

71. The method of claim 70, further comprising characterizing said one or more declarative rules by a dependency network.

72. The method of claim 71, further comprising converting said dependency network to a directed acyclic graph (DAG) in order to eliminate loops in said network.

73. The method of claim 72, wherein said updating step comprises performing forward and/or backward search of said DAG.

74. The method of claim 46, wherein said one or more declarative rules comprise a constrained declarative system.

75. The method of claim 74, wherein said updating step comprises utilizing a constraint propagation algorithm.

76. The method of claim 75, wherein said constraint algorithm comprises a linear programming algorithm.

77. The method of claim 74, wherein said updating step comprises utilizing an optimization algorithm with a cost function to propagate the data modification.

78. The method of claim 77, wherein said type of declarative system can be any of a simple formula, multi-source directional, or a constrained system.

79. The method of claim 74, further comprising detecting unfeasible conditions.

80. The method of claim 79, further comprising generating suggestions for resolution of said unfeasible conditions.

81. The method of claim 46, further comprising ascertaining a type of declarative system formed by said one or more declarative rules.

82. The method of claim 46, comprising determining whether a said data associated with a said object participates in a said declarative rule at runtime subsequent to assignment of a value to that data.

83. The method of claim 46, further comprising loading any selected data corresponding to said object on which a procedural instruction is operated and data corresponding to said other objects from a persistent storage.

84. A method of integrating one or more declarative rules into a procedural computational system, the method comprising the steps of:

executing on a digital data processor a step of compiling, from a sequence of procedural instructions, a procedural instruction for assignment of a value to a variable so as to effect updating, upon execution of such instruction at runtime, of one or more other variables participating in one or more declarative rules so as to maintain consistency of relationships imposed by said one or more declarative rules among said variable to which such value is assigned and said one or more other variables, wherein said one or more other variables are those not changed by the execution of that procedural instruction, wherein said rules are defined outside that procedural instruction, and wherein that updating of the one or more other variables is performed by executing said rules on said digital data processor prior to execution of any other procedural instruction in the sequence.

85. An integrated computational system, comprising

one or more digital data processors that execute

a procedural facility for executing a procedural sequence that comprises a plurality of procedural instructions operating on one or more variables,

a declarative facility coupled to operate on one or more other variables participating in one or more declarative rules so as to maintain one or more relationships defined by said one or more rules among said variables, and

a change tracking facility in communication with said procedural and declarative facilities,

wherein upon execution of a procedural instruction, said change tracking facility detects changes, if any, in one or more variables participating in at least one of said declarative rules and reports one or more said changes to said declarative facility, said declarative facility updating one or more other variables participating in said at least one declarative rule, in response to said reported change, so as to maintain a relationship defined thereby, wherein said one or more other variables are those not changed by execution of that procedural instruction, wherein said rules are defined outside that procedural instruction, and wherein that updating of the one or more other variables is performed prior to execution of any other procedural instruction in the sequence of instructions.

86. The computational system of claim 85, wherein said declarative facility comprises a rule compiler operating on a textual representation of said one or more declarative rules to generate a rule execution code and a dependency network characterizing said rules.

87. The computational system of claim 86, wherein said rule compiler parses said textual representation of said rules according to a context-free grammar.

88. The computational system of claim 87, wherein said rule compiler utilizes an ATN parser to parse textual representations of said one or more declarative rules.

89. The computational system of claim 86, wherein said rule compiler generates hash tables indexed by variable names and variable designations that specify chains of related objects and their properties.

90. The computational system of claim 89, wherein said rule compiler utilizes said dependency network to generate the hash tables.

91. The computational system of claim 86, further comprising a rule interpreter utilizing said rule execution code and said dependency network for updating one or more other variables participating in at least one of the declarative rules, in response to a change in at least one variable participating in said rule by said procedural facility, in accordance with a definition of said rule.

92. A method of integrating one or more declarative rules into a procedural computational system so as to render a plurality of instructions provided by said procedural system and a plurality of declarative rules mutually consistent, the method comprising the steps of:

executing, on a digital data processing system that comprises one or more digital data processors, a procedural sequence that comprises a plurality of procedural instructions,

upon execution of a procedural instruction that causes change to one or more variables,

executing one or more declarative rules to update values of one or more other variables participating in said one or more rules so as to maintain relationships imposed by said one or more rules among said variables, wherein said one or more other variables are those not changed by the execution of that procedural instruction, and wherein said rules are defined outside the procedural sequence,

wherein said updating of values of said other variables is deferred until at least one of said procedural instructions in said procedural sequence requires those one or more other variables.