Efficiently committing large transactions in a graph database
First Claim
1. A computer-implemented method, comprising:
- receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database;
representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction;
partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising a respective two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the respective two or more operations of the transaction subgraph, wherein the partitioning the transaction graph into the two or more transaction subgraphs comprises;
partitioning the transaction graph into two or more intermediate transaction subgraphs; and
extracting from the two or more intermediate transaction subgraphs two or more residual vertices representing one or more dependencies between the two or more intermediate transaction subgraphs;
wherein the two or more transaction subgraphs are independent of one another; and
executing the transaction on the graph database, wherein the executing the transaction comprises;
applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database;
inserting each extracted residual vertex into a residual subgraph; and
synchronously applying the residual subgraph to the graph database.
2 Assignments
0 Petitions
Accused Products
Abstract
A computer-implemented method includes receiving a transaction, where the transaction includes a plurality of operations and is applicable to a graph database. The transaction is represented by a transaction graph, which is a dependency graph representing dependencies among the plurality of operations of the transaction. The transaction graph is partitioned, by a computer processor, into two or more transaction subgraphs. Each of the two or more transaction subgraphs includes two or more operations of the transaction, and each of the two or more transaction subgraphs is a dependency graph representing dependencies among the two or more operations of the transaction subgraph. The two or more transaction subgraphs are independent of one another. The two or more transaction subgraphs are applied to the graph database in parallel, where applying each transaction subgraph to the graph database includes applying the two or more operations of the transaction subgraph to the graph database.
13 Citations
15 Claims
-
1. A computer-implemented method, comprising:
-
receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database; representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction; partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising a respective two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the respective two or more operations of the transaction subgraph, wherein the partitioning the transaction graph into the two or more transaction subgraphs comprises; partitioning the transaction graph into two or more intermediate transaction subgraphs; and extracting from the two or more intermediate transaction subgraphs two or more residual vertices representing one or more dependencies between the two or more intermediate transaction subgraphs; wherein the two or more transaction subgraphs are independent of one another; and executing the transaction on the graph database, wherein the executing the transaction comprises; applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database; inserting each extracted residual vertex into a residual subgraph; and synchronously applying the residual subgraph to the graph database. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system comprising:
-
a memory having computer readable instructions; and one or more processors for executing the computer readable instructions, the computer readable instructions comprising; receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database; representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction; partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the two or more operations of the transaction subgraph, wherein the partitioning the transaction graph into the two or more transaction subgraphs comprises; partitioning the transaction graph into two or more intermediate transaction subgraphs; and extracting from the two or more intermediate transaction subgraphs two or more residual vertices representing one or more dependencies between the two or more intermediate transaction subgraphs; wherein the two or more transaction subgraphs are independent of one another; and executing the transaction on the graph database, wherein the executing the transaction comprises; applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database; inserting each extracted residual vertex into a residual subgraph; and synchronously applying the residual subgraph to the graph database. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A computer program product for applying a transaction to a graph database, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
-
receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database; representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction; partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the two or more operations of the transaction subgraph, wherein the partitioning the transaction graph into the two or more transaction subgraphs comprises; partitioning the transaction graph into two or more intermediate transaction subgraphs; extracting from the two or more intermediate transaction subgraphs two or more residual vertices representing one or more dependencies between the two or more intermediate transaction subgraphs; wherein the two or more transaction subgraphs are independent of one another; and inserting each extracted residual vertex into a residual subgraph; and executing the transaction on the graph database, wherein the executing the transaction comprises; applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database; and synchronously applying the residual subgraph to the graph database. - View Dependent Claims (12, 13, 14, 15)
-
Specification