Eager evaluation of tasks in a workflow system

• US 7,370,325 B1
• Filed: 02/19/1999
• Issued: 05/06/2008
• Est. Priority Date: 02/19/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kumar, Bharat, Llirbat, Francois, Hull, Richard Baxter, Zhou, Gang
• Primary Examiner(s): Flynn; Nathan
• Assistant Examiner(s): ENGLAND, DAVID E
• Application Number:
  US09/251,998
• Time in Patent Office: 3,364 Days
• Field of Search: 709/200, 37921001-21401, 718100-108
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

An object-focused workflow system for processing a received object in accordance with a declarative workflow specification. The specification includes modules and attributes, where module execution results in the evaluation of attributes, and may include the initiation of a side-effect action performed by an external component. Whether modules are to be executed for a particular received object is determined by associated enabling conditions. Attributes may be evaluated in accordance with computation rules and a combining policy, where the computation rules specify how values are to be contributed to an attribute, and the combining policy indicates how those contributed values are combined in order to assign a value to the attribute. Tasks in the workflow system may be executed eagerly in order to improve the performance of the workflow system. The eager evaluation of tasks includes the determination of whether such tasks are eligible for eager evaluation, and whether the tasks are unneeded or necessary for the processing of the received event. Workflows which satisfy described design properties allow for improved algorithms for the determination of the whether tasks are eligible, eager, and/or necessary. A graphical user interface is provided for displaying a representation of the evaluation status of the modules and attributes during workflow execution.

Claims

1. A method for operation of a workflow system for processing an object by executing a plurality of tasks, one or more of said tasks each having one or more associated enabling conditions indicating whether the task is to be executed for said object, and wherein execution of at least one of said tasks results in initiation of a side-effect action performed by a component external to said workflow system, said method comprising the steps of:

determining whether a task is eligible for eager execution by considering at least (1) a state of the task and (2) whether execution of the task results in the initiation of a side-effect action; and

executing the task using eager execution if the task is determined to be eligible for eager execution.

2. The method of claim 1 wherein the step of determining whether a task is eligible for eager execution further comprises the step of:

determining that a particular task whose execution results in the initiation of a side-effect action is eligible for eager execution only if it is determined that the one or more enabling conditions associated with the particular task will evaluate to true as determined by the state of the particular task.

3. The method of claim 1 wherein the step of determining whether a task is eligible for eager execution further comprises the step of:

determining that a particular task whose execution does not result in the initiation of a side-effect action is eligible for eager execution prior to determining that the one or more enabling conditions associated with the particular task will evaluate to true as determined by the state of the particular task.

4. The method of claim 1 wherein said step of determining whether a task is eligible for eager execution further comprises the step of:

partially evaluating one or more enabling conditions associated with said task.

5. The method of claim 1 wherein said step of determining whether a task is eligible for eager execution is performed by also considering (3) whether the task contributes to the production of a target value.

6. The method of claim 1 further comprising the step of:

determining that a particular task is unneeded for processing of the object based at least in part on partial evaluation of an enabling condition of a second task, wherein said second task'"'"'s enabling condition depends on one or more outputs of said particular task.

7. The method of claim 1 further comprising the step of:

determining that a particular task is necessary for processing of the object based at least in part on evaluation of enabling conditions for a number of tasks wherein said tasks'"'"' enabling conditions depend on said particular task.

8. The method of claim 1 further comprising the step of:

determining that a particular task is necessary for processing of the object based at least in part on evaluation of enabling conditions for a number of tasks, wherein said tasks'"'"' enabling conditions depend on one or more outputs of said particular task.

9. The method of claim 1 wherein said step of determining is performed repeatedly during the processing of the object.

10. The method of claim 1 wherein a memory of said workflow system stores a graph representing data flow dependencies and enabling flow dependencies between tasks and enabling conditions, said method further comprising the step of:

propagating changes through said graph based on new outputs of completed tasks.

11. The method of claim 10 wherein said step of propagating changes is based on predefined propagation rules.

12. A workflow system for processing an object by executing a plurality of tasks, one or more of said tasks each having one or more associated enabling conditions indicating whether the task is to be executed for said the object, and wherein execution of at least one of said tasks results in initiation of a side-effect action performed by a component external to said workflow system, said system comprising:

means for determining whether a task is eligible for eager execution by considering at least (1) a state of the task and (2) whether execution of the task results in the initiation of a side-effect action; and

means for executing the task using eager execution if the task is determined to be eligible for eager execution.

13. The workflow system of claim 12 wherein the means for determining whether a task is eligible for eager execution her comprises:

means for determining that a particular task whose execution results in the initiation of a side-effect action is eligible for eager execution only if it is determined that the one or more enabling conditions associated with the particular task will evaluate to true as determined by the state of the particular task.

14. The workflow system of claim 12 wherein the means for determining whether a task is eligible for eager execution further comprises:

means for determining that a particular task whose execution does not result in the initiation of a side-effect action is eligible for eager execution prior to determining that one or more enabling conditions associated with the particular task will evaluate to true as determined by the state of the particular task.

15. The workflow system of claim 12 wherein said means for determining whether a task is eligible for eager execution further comprises:

means for partially evaluating one or more enabling conditions associated with said task.

16. The workflow system of claim 12 wherein said means for determining whether a task is eligible for eager execution further comprises:

means for determining whether the task contributes to the production of a target value.

17. The workflow system of claim 12 further comprising:

means for determining that a particular task is unneeded for processing of the object based at least in part on partial evaluation of an enabling condition of a second task, wherein said second task'"'"'s enabling condition depends on one or more outputs of said particular task.

18. The workflow system of claim 12 further comprising:

means for determining that a particular task is necessary for processing of the object based at least in part on evaluation of enabling conditions for a number of tasks, wherein said tasks'"'"' enabling conditions depend on said particular task.

19. The workflow system of claim 12 further comprising:

means for determining that a particular task is necessary for processing of the object based at least in part on evaluation of enabling conditions for a number of tasks, wherein said tasks'"'"' enabling conditions depend on one or more outputs of said particular task.

20. The workflow system of claim 12 further comprising:

a memory for storing a graph representing data flow dependencies and enabling flow dependencies between tasks and enabling conditions; and

means for propagating changes through said graph based on new outputs of completed tasks.

21. The workflow system of claim 20 wherein said memory stores predefined propagation rules and wherein said means for propagating changes further comprises means for propagating changes based on said predefined propagation rules.