Supporting tuples in log-based representations of graph databases
During operation, a system for processing queries of a graph database executes a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates. When a query of the graph database is received, the system obtains, from the query, a compound comprising a compound type and a set of identity-giving nodes. Next, the system uses the compound to access a tuple for storage in a log-based representation of the graph database, wherein the tuple includes the compound type and the identity-giving nodes. The system then uses the tuple to generate a result of the query and provides the result in a response to the query.
1. A method, comprising:
executing a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges representing relationships between pairs of nodes in the set of nodes, and a set of predicates wherein each predicate labels a respective relationship represented by a respective edge; and
when a query of the graph database is received, using one or more of the processes to process the query by:
obtaining, from the query, a compound representing a compound relationship specified by two or more edges in the set of edges, wherein
the compound is structured as a tuple which comprises a compound type representing a data type of the compound, and a set of identity-giving nodes,
each identity-giving node in the set of identity-giving node includes a predicate in the set of predicates and a corresponding node in the set of nodes, and
the tuple does not include any edge in the two or more edges;
using the compound type and the set of identity-giving nodes to search the tuple in the graph database;
if the tuple is located in the graph database, using the tuple to generate a result of the query; and
providing the result in a response to the query.
2. The method of claim 1 , further comprising:
obtaining a non-assertion of the compound from the query; and
using the non-assertion to modify the result of the query.
3. The method of claim 2 , wherein the using the non-assertion to modify the result comprises:
when the tuple does not exist in the graph database:
adding the tuple and an attribute that refers to the compound to the graph database; and
including an indication of the non-assertion in the tuple.
4. The method of claim 3 , wherein the using the non-assertion to modify the result further comprises:
including, in the result, an offset of the tuple as an identifier for the compound.
5. The method of claim 2 , wherein the using the non-assertion to modify the result comprises:
when the tuple exists in the graph database, adding an attribute that refers to the compound to the graph database without modifying a state of the tuple in the graph database.
6. The method of claim 5 , wherein the state of the compound is at least one of:
the non-assertion;
an addition; and
a deletion.
7. The method of claim 1 , wherein the using the tuple to generate the result of the query comprises:
writing the tuple to a log-based representation of the graph database according to a pre-specified ordering of the set of identity-giving nodes in the compound.
8. The method of claim 1 , wherein the using the tuple to generate the result of the query further comprises:
transforming the set of identity-giving nodes in the tuple into a set of edges; and
including the set of edges resulted from the transforming in the result.
9. The method of claim 1 , wherein each node in the set of identity-giving nodes comprises a predicate-object pair.
10. The method of claim 9 , wherein the tuple further comprises a cardinality associated with a predicate in the predicate-object pair.
11. The method of claim 1 , wherein the tuple further comprises a length.
12. An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
execute one or more processes for providing a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges representing relationships between pairs of nodes in the set of nodes, and a set of predicates wherein each predicate labels a respective relationship represented by a respective edge;
obtain, from a query of the graph database, a compound the set of edges, wherein
the compound is structured as a tuple which comprises a compound type representing a data type of the compound, and a set of identity-giving nodes,
each identity-giving node in the set of identify-giving nodes includes a predicate in the set of predicates and a corresponding node in the set of nodes, and
the tuple does not include any edge in the two or more edges;
use the compound type and the set of identity-giving nodes to search the tuple in the graph database;
if the tuple is located in the graph database, use the tuple to generate a result of the query; and
provide the result in a response to the query.
13. The apparatus of claim 12 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
obtain a non-assertion of the compound from the query; and
use the non-assertion to modify the result of the query.
14. The apparatus of claim 13 , wherein the using the non-assertion to modify the result comprises:
when the tuple does not exist in the graph database:
adding the tuple and an attribute that refers to the compound to the graph database; and
including an indication of the non-assertion in the tuple.
15. The apparatus of claim 14 , wherein the using the non-assertion to modify the result further comprises:
including, in the result, an offset of the tuple as an identifier for the compound.
16. The apparatus of claim 13 , wherein the using the non-assertion to modify the result comprises:
when the tuple exists in the graph database, adding an attribute that refers to the compound to the graph database without modifying a state of the tuple in the graph database.
17. The apparatus of claim 16 , wherein the state of the compound is at least one of:
the non-assertion;
an addition; and
a deletion.
18. The apparatus of claim 12 , wherein the tuple further comprises:
a length; and
a cardinality associated with a predicate in the set of identity-giving nodes.
19. A system, comprising:
a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges representing relationships between pairs of nodes in the set of nodes, and a set of predicates wherein each predicate labels a respective relationship represented by a respective edge; and
a processing module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to use one or more of the processes to process a query of the graph database by:
obtaining, from the query, a compound representing a compound relationship specified by two or more edges in the set of edges, wherein
the compound is structured as a tuple which comprises a compound type representing a data type of the compound, and a set of identity-giving nodes,
each identity-giving node in the set of identity-giving node includes a predicate in the set of predicates and a corresponding node in the set of nodes, and
the tuple does not include any edge in the two or more edges;
using the compound type and the set of identity-giving nodes to search the tuple in the graph database;
if the tuple is located in the graph database, using the tuple to generate a result of the query; and
providing the result in a response to the query.
20. The system of claim 19 , wherein the tuple further comprises:
an indication of a non-assertion of the tuple;
a length; and
a cardinatity associated with a predicate in the set of identity-giving nodes.