FUNCTIONAL EQUIVALENCE OF TUPLES AND EDGES IN GRAPH DATABASES

1 . A method, comprising:

executing, on a computer system, one or more processes for providing 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; and

when a query of the graph database is received, using one or more of the processes to process the query by:

matching the query to a tuple comprising a compound type and a set of identity-giving nodes in the graph database;

transforming the tuple into a subset of the edges;

using the subset of the edges 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:

matching an additional query to the subset of the edges;

transforming the subset of the edges into the tuple; and

using the tuple to process the additional query.

3 . The method of claim 2 , wherein transforming the subset of edges into the tuple comprises:

transforming the subset of the edges into a pre-specified ordering of the identity-giving nodes in the tuple.

4 . The method of claim 1 , wherein matching the query to the tuple comprises:

obtaining a compound representing the tuple as a nested statement within the query.

5 . The method of claim 1 , wherein transforming the tuple into the subset of the edges comprises:

obtaining, from the tuple, a set of predicate-object pairs representing the identity-giving nodes; and

including the predicate-object pairs in the subset of the edges.

6 . The method of claim 5 , wherein transforming the tuple into the subset of the edges further comprises:

including a hub node representing the tuple as a subject shared by the subset of the edges.

7 . The method of claim 6 , wherein an identifier of the hub node comprises an offset of the tuple in a log-based representation of the graph database.

8 . The method of claim 1 , wherein using the subset of the edges to generate the result of the query comprises:

propagating a write operation associated with the tuple to the subset of the edges.

9 . The method of claim 8 , wherein the write operation is at least one of:

an addition;

a deletion; and

a non-assertion.

10 . The method of claim 1 , wherein transforming the tuple into the subset of the edges comprises:

obtaining a rule for a compound comprising the compound type; and

using the rule to transform the tuple into the subset of the edges.

11 . A method, comprising:

executing, on a computer system, one or more processes for providing 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; and

when a query of the graph database is received, using one or more of the processes to process the query by:

matching the query to a subset of the edges in the graph database;

transforming the subset of the edges into a tuple comprising a compound type and a set of identity-giving nodes;

using the tuple to generate a result of the query; and

providing the result in a response to the query.

12 . The method of claim 11 , further comprising:

matching an additional query to an additional subset of the edges;

transforming the additional subset of the edges into another tuple; and

using the other tuple to process the additional query.

13 . The method of claim 11 , wherein transforming the subset of the edges into the tuple comprises:

obtaining a set of predicate-object pairs from the subset of the edges; and

including the predicate-object pairs in the identity-giving nodes of the tuple.

14 . The method of claim 13 , wherein including the predicate-object pairs in the identity-giving nodes of the tuple comprises:

populating the tuple with a pre-specified ordering of the identity-giving nodes.

15 . The method of claim 13 , wherein transforming the subset of the edges into the tuple further comprises:

obtaining a hub node as a subject shared by the subset of the edges; and

using the hub node to identify the tuple.

16 . The method of claim 13 , wherein using the tuple to generate the result of the query comprises:

propagating a write operation associated with the subset of the edges to the tuple.

17 . The method of claim 16 , wherein the write operation is at least one of:

an addition;

a deletion; and

a non-assertion.

18 . 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 between pairs of nodes in the set of nodes, and a set of predicates;

obtain a first query comprising a first tuple and a second query comprising a first subset of the edges, wherein the first tuple comprises a compound type and a set of identity-giving nodes in the graph database;

transform the first tuple into a second subset of the edges and the first subset of the edges into a second tuple;

use the second subset of the edges to generate a first result of the first query and the second tuple to generate a second result of the second query; and

provide the first result in a first response to the first query and the second result in a second response to the second query.

19 . The apparatus of claim 18 , wherein transforming the first tuple into the second subset of the edges comprises:

obtaining, from the first tuple, a set of predicate-object pairs representing the identity-giving nodes;

including the predicate-object pairs in the second subset of the edges; and

including a hub node representing the first tuple as a subject shared by the second subset of the edges.

20 . The apparatus of claim 18 , wherein transforming the first subset of the edges into the second tuple comprises:

populating the second tuple with a pre-specified ordering of predicate-object pairs from the first subset of the edges.