Finding similarity among sets of coordinated tasks

• US 7,617,230 B2
• Filed: 07/28/2005
• Issued: 11/10/2009
• Est. Priority Date: 07/28/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Srivastava, Biplav
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): BUCKINGHAM, KELLYE DEE
• Application Number:
  US11/191,672
• Publication Number:
  US 20070027881A1
• Time in Patent Office: 1,566 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The described workflow analysis techniques generalize activity instance information into activity context information so that activities can be analyzed in the presence of other possible activities, and by extension, other workflows. Generalization is made possible by deriving an action model for each activity, in which each model specifies contexts for preconditions and postconditions. These contexts are necessary and sufficient in defining each activity, and can be further populated with metadata. The derived activity contexts can be used for analyses that are not possible using existing approaches.

Claims

1. A computer-implemented method for finding similarity among activities in a Business Process Execution Language for Web Services (BPEL) workflow, said method comprising:

inputting said BPEL workflow to a processor, said BPEL workflow comprising executable basic activities and grouping activities;

automatically building a semantic action model for each of said executable basic activities and said grouping activities in said BPEL workflow using said processor, wherein said semantic action model specifies a context, associated with any of a precondition and a postcondition, for said each of said executable basic activities and said grouping activities;

automatically generating an ordered list of semantic action models corresponding to said executable basic activities and said grouping activities using said processor, based on control flow ordering information inherent to semantics of said grouping activities, and preconditions and postconditions corresponding to links from a predecessor executable basic activity and a successor executable basic activity, respectively;

using ordering information of each of said semantic action models, associated with a precondition or postcondition, as metadata, indicating said context for transforming a representation of said BPEL workflow by replacing sub-workflows with said semantic action models using said processor,

wherein said metadata includes an equivalent causation, a same derived context, and a most constrained semantic action; and

using said metadata to manage a transformed representation of said BPEL workflow and to determine a similarity between said transformed representation of said BPEL workflow and a plurality of stored workflow representations comprising semantic action models using said processor.

2. The method of claim 1, further comprising recursively combining said semantic action models of said representation of said BPEL workflow to build said ordered list of semantic action models corresponding to more activities of said BPEL workflow.

3. The method of claim 2, wherein precondition context metadata relates to initial conditions that enable said BPEL workflow, and postcondition context metadata relates to latest actions that are considered goals of said BPEL workflow.

4. A computer implemented method for automatically analyzing a Business Process Execution Language for Web Services (BPEL) workflow, said BPEL workflow including at least two flows, in which each flow of said at least two flows includes a sequence of activities, said method comprising:

inputting said BPEL workflow to a processor, said BPEL workflow comprising executable basic and grouping activities;

automatically building a semantic action model for each of said executable basic activities and said grouping activities in said BPEL workflow using said processor, wherein said semantic action model specifies a context, associated with any of a precondition and a postcondition, for said each of said executable basic and grouping activities;

automatically generating an ordered list of semantic action models corresponding to said executable basic activities in each said flow of said BPEL workflow using said processor, said ordered list of semantic action models specifying a precondition and a postcondition for said each executable basic activity of each said flow, said precondition and said postcondition corresponding to links from a predecessor executable basic activity and a successor executable basic activity, respectively;

using ordering information from each flow of each of said semantic action models, associated with a precondition or postcondition, as metadata, indicating said context for transforming a representation of said each flow in said BPEL workflow by replacing sub-workflows with said semantic action models using said processor,

wherein said metadata includes an equivalent causation, a same derived context, and a most constrained semantic action; and

using said metadata to manage a transformed representation of said each flow of said BPEL workflow and to determine a similarity between said transformed representation of said BPEL workflow and a plurality of stored workflow representations comprising semantic action models using said processor.

5. The method of claim 4, wherein precondition context metadata relates to initial conditions that enable said BPEL workflow, and postcondition context metadata relates to latest actions that are considered goals of said BPEL workflow.

6. A computer program storage medium readable by a computer, tangibly embodying a program of instructions executable by said computer to perform a method for automatically finding similarity among activities in a Business Process Execution Language for Web Services (BPEL) workflow, said method comprising:

inputting said BPEL workflow, said BPEL workflow comprising executable basic activities and grouping activities;

automatically building a semantic action model for each of said executable basic activities and said grouping activities in said BPEL workflow, wherein said semantic action model specifies a context, associated with any of a precondition and a postcondition, for said each of said executable basic activities and said grouping activities;

automatically generating an ordered list of semantic action models corresponding to said executable basic activities and said grouping activities, based on control flow ordering information inherent to semantics of said grouping activities, and preconditions and postconditions corresponding to links from a predecessor executable basic activity and a successor executable basic activity, respectively;

using ordering information of each of said semantic action models, associated with a precondition or postcondition, as metadata, indicating said context for transforming a representation of said BPEL workflow by replacing sub-workflows with said semantic action models,

wherein said metadata includes an equivalent causation, a same derived context, and a most constrained semantic action; and

using said metadata to manage a transformed representation of said BPEL workflow and to determine a similarity between said transformed representation of said BPEL workflow and a plurality of stored workflow representations comprising semantic action models.

7. A computer system comprising:

a memory for inputting a BPEL workflow, said BPEL workflow comprising executable basic activities and grouping activities; and

a processor configured to;

automatically build a semantic action model for each of said executable basic activities and said grouping activities in said BPEL workflow, wherein said semantic action model specifies a context, associated with any of a precondition and a postcondition, for said each of said executable basic activities and said grouping activities;

automatically generate an ordered list of semantic action models corresponding to said executable basic activities and said grouping activities, based on control flow ordering information inherent to semantics of said grouping activities, and preconditions and postconditions corresponding to links from a predecessor executable basic activity and a successor executable basic activity, respectively;

use ordering information of each of said semantic action models, associated with a precondition or postcondition, as metadata indicating said context for transforming a representation of said BPEL workflow by replacing sub-workflows with said semantic action models,

wherein said metadata includes an equivalent causation, a same derived context, and a most constrained semantic action; and

use said metadata to manage a transformed representation of said BPEL workflow and to determine a similarity between said transformed representation of said BPEL workflow and a plurality of stored workflow representations comprising semantic action models.