Determining an execution ordering

• US 9,305,058 B2
• Filed: 10/31/2011
• Issued: 04/05/2016
• Est. Priority Date: 10/31/2011
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Gupta, Chetan Kumar, Wang, Song, Mehta, Abhay, Liu, Mo, Rundensteiner, Elke A.
• Primary Examiner(s): Vo, Truong
• Application Number:
  US13/285,785
• Publication Number:
  US 20130110820A1
• Time in Patent Office: 1,618 Days
• Field of Search: 707/716, 707/797
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

There is provided a computer-implemented method of determining an execution ordering. An exemplary method comprises generating a directed graph based on a hierarchy. The hierarchy includes a plurality of pattern queries. The method also includes determining a minimum spanning tree of the directed graph. The method further includes determining an execution order of the pattern queries based on the minimum spanning tree.

Claims

1. A computer-implemented method of determining an execution ordering, comprising:

generating a directed graph based on a hierarchy comprising a plurality of pattern queries;

determining a minimum spanning tree of the directed graph; and

determining an execution order of the pattern queries based on the minimum spanning tree.

2. The method recited in claim 1, wherein the hierarchy comprises a plurality of parent-child relationships between the plurality of pattern queries, wherein a child pattern query refines data processed by a parent of the child pattern query.

3. The method recited in claim 1, wherein the directed graph comprises:

a plurality of vertices corresponding to the plurality of pattern queries;

a virtual ground vertex comprising a root of the directed graph;

a plurality of first edges corresponding to the plurality of parent-child relationships, wherein each of the first edges is associated with a weight corresponding to a cost of processing a first pattern query, at which, the first edge is directed; and

a plurality of second edges directed from the virtual ground vertex to the plurality of vertices, wherein each of the second edges is associated with a weight corresponding to a cost of processing the first pattern query, at which the second edge is directed.

4. The method recited in claim 3, wherein the cost comprises a cost of processing the first pattern query independently if the associated edge is directed from the virtual ground vertex.

5. The method recited in claim 4, wherein the first pattern query is processed using a stack-based join.

6. The method recited in claim 3, wherein the cost comprises a cost of processing the first pattern query after processing a previously executed pattern query from which the associated edge is directed.

7. The method recited in claim 6, wherein the first pattern query is a child of the previously executed pattern query, and the first pattern query is conditionally computed using a general to specific evaluation.

8. The method recited in claim 6, wherein the first pattern query is a parent of the previously executed pattern query, and the first pattern query is conditionally computed using a specific to general evaluation.

9. A computer system for determining an execution ordering, the computer system comprising:

a processor that is adapted to execute stored instructions; and

a memory device that stores instructions, the memory device comprising;

computer-implemented code adapted to generate a directed graph based on a hierarchy comprising a plurality of pattern queries, wherein the hierarchy comprises a plurality of parent-child relationships between the plurality of pattern queries, wherein a child pattern query refines data processed by a parent of the child pattern query;

computer-implemented code adapted to determine a minimum spanning tree of the directed graph; and

computer-implemented code adapted to determine an execution order of the pattern queries based on the minimum spanning tree.

10. The computer system recited in claim 9, wherein the directed graph comprises:

a plurality of vertices corresponding to the plurality of pattern queries;

a virtual ground vertex comprising a root of the directed graph;

a plurality of first edges corresponding to the plurality of parent-child relationships, wherein each of the first edges is associated with a weight corresponding to a cost of processing a first pattern query, at which, the first edge is directed; and

a plurality of second edges directed from the virtual ground vertex to the plurality of vertices, wherein each of the second edges is associated with a weight corresponding to a cost of processing the first pattern query, at which the second edge is directed.

11. The computer system recited in claim 10, wherein the cost comprises a cost of processing the first pattern query independently if the associated edge is directed from the virtual ground vertex.

12. The computer system recited in claim 11, wherein the first pattern query is processed using a stack-based join.

13. The computer system recited in claim 10, wherein the cost comprises a cost of processing the first pattern query after processing a second pattern query from which the associated edge is directed.

14. The computer system recited in claim 13, wherein the first pattern query is a child of the second pattern query, and the first pattern query is conditionally computed using a general to specific evaluation.

15. The computer system recited in claim 13, wherein the first pattern query is a parent of the second pattern query, and the first pattern query is conditionally computed using a specific to general evaluation.

16. A tangible, non-transitory, machine-readable medium that stores machine-readable instructions executable by a processor to determine an execution ordering, the tangible, non-transitory, machine-readable medium comprising:

machine-readable instructions that, when executed by the processor, generate a directed graph based on a hierarchy comprising a plurality of pattern queries, wherein the hierarchy comprises a plurality of parent-child relationships between the plurality of pattern queries, wherein a child refines data processed by a parent of the child pattern query, and wherein the directed graph comprises;

a plurality of vertices corresponding to the plurality of pattern queries;

a virtual ground vertex comprising a root of the directed graph;

a plurality of first edges corresponding to the plurality of parent-child relationships, wherein each of the first edges is associated with a weight corresponding to a cost of processing a first pattern query, at which, the first edge is directed; and

a plurality of second edges directed from the virtual ground vertex to the plurality of vertices, wherein each of the second edges is associated with a weight corresponding to a cost of processing the first pattern query, at which the second edge is directed;

machine-readable instructions that, when executed by the processor, determine a minimum spanning tree of the directed graph; and

machine-readable instructions that, when executed by the processor, determine an execution order of the pattern queries based on the minimum spanning tree.

17. The tangible, machine-readable medium recited in claim 16, wherein the cost comprises a cost of processing the first pattern query independently if the associated edge is directed from the virtual ground vertex.

18. The tangible, machine-readable medium recited in claim 17, wherein the first pattern query is processed using a stack-based join.

19. The tangible, machine-readable medium recited in claim 16, wherein the cost comprises a cost of processing the first pattern query after processing a second pattern query from which the associated edge is directed.

20. The tangible, machine-readable medium recited in claim 19, wherein, if the first pattern query is a child of the second pattern query, the first pattern query is conditionally computed using a general to specific evaluation, and wherein, if the first pattern query is a parent of the second pattern query, the first pattern query is conditionally computed using a specific to general evaluation.