Automatically Generating Execution Sequences for Workflows

Patent metadata

Field	Value
Publication number	US-2016103706-A1
Application number	US-201414511027-A
Country	US
Kind code	A1
Filing date	Oct 9, 2014
Priority date	Oct 9, 2014
Publication date	Apr 14, 2016
Grant date	—

Abstract

The present disclosure relates to automatically generating execution sequences from workflow definitions. One example method includes receiving a workflow definition including a plurality of operations, each of the plurality of operations including input attributes each associated with an input value and output attributes each associated with an output value; determining an execution sequence for the workflow defining relationships between the plurality of operations, the determining based at least in part on the one or more input attributes and associated input values, and the output attributes and associated output values for each operation, and at least in part on one or more semantic rules defining dependencies of each of the plurality of operations; and generating a directed acyclic graph representing the execution sequence including nodes each representing an operation from the plurality of operations, and vertices each representing a relationship between the plurality of operations defined by the execution sequence.

First claim

What is claimed is:

1 . A computer-implemented method executed by one or more processors, the method comprising:
receiving a workflow definition including a plurality of operations, each of the plurality of operations including one or more input attributes each associated with an input value and one or more output attributes each associated with an output value; determining an execution sequence for the workflow defining relationships between the plurality of operations, the determining based at least in part on the one or more input attributes and associated input values, and the one or more output attributes and associated output values for each operation, and at least in part on one or more semantic rules defining dependencies of each of the plurality of operations; and generating a directed acyclic graph representing the execution sequence, the direct acyclic graph including one or nodes each representing an operation from the plurality of operations, and one or more vertices each representing a relationship between the plurality of operations defined by the execution sequence.

2 . The method of claim 1 , further comprising instructing a plurality of computing devices connected by a network to execute the workflow based on the execution sequence represented by the directed acyclic graph.

3 . The method of claim 1 , further comprising generating user interface data defining a user interface and that causes the definition of the workflow to be received via the user interface, the user interface configured to allow a user to specify the plurality of operations, the input value for each of the one or more input attributes for each operation, and the output value for each of the one or more output attributes for each operation.

4 . The method of claim 3 , wherein the user interface is configured to allow the user to create a new operation, and to select an output value for a particular operation from the plurality of operations as an input value for the new operation.

5 . The method of claim 3 , wherein the user interface is configured to allow the user to specify the plurality of operations, the input value for each of the one or more input attributes for each operation, and the output value for each of the one or more output attributes for each operation from a mobile device.

6 . The method of claim 5 , wherein the user interface is configured to present the workflow definition as a tree structure derived from the determined relationships between the plurality of operations.

7 . The method of claim 6 , wherein a first operation having a single input value is represented as a child of a second operation having an output value matching the single input value.

8 . The method of claim 6 , wherein a first operation having a plurality of input values corresponding to output values of a plurality of second operations is represented as a child of the second operation the highest tree rank property of the plurality of second operations.

9 . The method of claim 1 , wherein the one or more input attributes represent files and the associated input value for each input attribute represents a file identifier of a file to read as input by the operation during execution.

10 . The method of claim 9 , wherein the file identifier includes a file name identifying the file within a file system.

11 . The method of claim 1 , wherein the one or more output attributes represent files and the associated output value for each output attribute represents a file identifier of a file to which the operation writes output during execution.

12 . The method of claim 11 , wherein the file identifier includes a file name identifying the file within a file system.

13 . The method of claim 1 , wherein the one or more input attributes represent data streams and the associated input value for each input attribute represents a steam identifier of a data stream to read as input by the operation during execution.

14 . The method of claim 13 , wherein the stream identifier includes a Uniform Resource Identifier (URI) identifying the data stream.

15 . The method of claim 1 , wherein the one or more output attributes represent data streams and the associated output value for each output attribute represents a stream identifier of a data stream to which the operation writes output during execution.

16 . The method of claim 1 , further comprising presenting, by a display device, a graphical representation of the generated directed acyclic graph.

17 . The method of claim 1 , wherein each relationship between the plurality of operations represents an output resource generated by a first operation from the plurality of operations and used as input by second operation from the plurality of operations different than the first operation.

18 . The method of claim 1 , wherein each operation is associated with a software program and the one or more input attributes and output attributes associated with the operation are retrieved from a program description associated with the software program.

19 . A non-transitory, computer-readable medium storing instructions operable when executed to cause at least one processor to perform operations comprising:
receiving a workflow definition including a plurality of operations, each of the plurality of operations including one or more input attributes each associated with an input value and one or more output attributes each associated with an output value; determining an execution sequence for the workflow defining relationships between the plurality of operations, the determining based at least in part on the one or more input attributes and associated input values, and the one or more output attributes and associated output values for each operation, and at least in part on one or more semantic rules defining dependencies of each of the plurality of operations; and generating a directed acyclic graph representing the execution sequence, the direct acyclic graph including one or nodes each representing an operation from the plurality of operations, and one or more vertices each representing a relationship between the plurality of operations defined by the execution sequence.

20 . A system comprising:
memory for storing data; and one or more processors operable to perform operations comprising:
receiving a workflow definition including a plurality of operations, each of the plurality of operations including one or more input attributes each associated with an input value and one or more output attributes each associated with an output value;
determining an execution sequence for the workflow defining relationships between the plurality of operations, the determining based at least in part on the one or more input attributes and associated input values, and the one or more output attributes and associated output values for each operation, and at least in part on one or more semantic rules defining dependencies of each of the plurality of operations; and
generating a directed acyclic graph representing the execution sequence, the direct acyclic graph including one or nodes each representing an operation from the plurality of operations, and one or more vertices each representing a relationship between the plurality of operations defined by the execution sequence.

Assignees

• Google Inc

Inventors

• Novaes Marcos

Classifications

• G06Q10/06 Primary

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title

• G06Q10/10

  Office automation; Time management · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title