Determining an execution ordering
View Patent ↗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.
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.