Determining an execution ordering

Patent metadata

Field	Value
Publication number	US-9305058-B2
Application number	US-201113285785-A
Country	US
Kind code	B2
Filing date	Oct 31, 2011
Priority date	Oct 31, 2011
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

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.

First claim

What is claimed is:

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.

Assignees

• Gupta Chetan Kumar
• Wang Song
• Mehta Abhay
• Liu Mo
• Rundensteiner Elke A
• Hewlett Packard Entpr Dev Lp

Inventors

• Gupta Chetan Kumar
• Wang Song
• Mehta Abhay
• Liu Mo
• Rundensteiner Elke A

Classifications

• G06F17/30516 Primary

  Physics · mapped topic

• G06F16/2456

  Join operations · CPC title

• G06F16/24568 Primary

  Data stream processing; Continuous queries · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title