Database calculation using parallel-computation in a directed acyclic graph
First Claim
Patent Images
1. A method of database calculation, the method comprising:
- identifying dependency of tasks;
converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the tasks into layers of tasks; and
performing the database calculation, wherein the database calculation computes in parallel the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed.
2 Assignments
0 Petitions
Accused Products
Abstract
Disclosed herein are technologies related to database calculation that utilizes parallel-computation of tasks in a directed acyclic graph. In accordance with one aspect, dependency of tasks is converted into a directed acyclic graph that topologically orders the tasks into layers of tasks. A database calculation may be performed, wherein the database calculation computes in parallel the tasks in each layer of the layers of tasks.
-
Citations
20 Claims
-
1. A method of database calculation, the method comprising:
-
identifying dependency of tasks; converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the tasks into layers of tasks; and performing the database calculation, wherein the database calculation computes in parallel the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. One or more computer-readable media storing processor-executable instructions that when executed cause one or more processors to perform operations that facilitate calculation logic comprising:
-
identifying dependency of tasks; converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the identified tasks into layers of tasks; and performing a database calculation, wherein the database calculation utilizes parallel-computation of the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A system that facilities calculation logic, the system comprising:
-
one or more processors that are configured to perform; identifying dependency of tasks; converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the identified tasks into layers of tasks; performing a database calculation, wherein the database calculation utilizes parallel-computation of the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed; and an output interface configured to the one or more processors, that provides results of the database calculation. - View Dependent Claims (20)
-
Specification