Representing compound relationships in a graph database

Patent metadata

Field	Value
Publication number	US-9378303-B1
Application number	US-201514858225-A
Country	US
Kind code	B1
Filing date	Sep 18, 2015
Priority date	Sep 18, 2015
Publication date	Jun 28, 2016
Grant date	Jun 28, 2016

Abstract

In order to facilitate efficient storage and extraction of data, a system may represent a compound relationship in a graph stored in a graph database. In particular, the system (or a user) may define the compound relationship based on two or more predicates associated with two or more edges between two or more nodes in the graph. Then, the system may generate, in the graph, a hub node that corresponds to the compound relationship and that has an identifier that is hidden from users of the graph so that the identifier of the hub node is not visible external to the graph database. Moreover, the identifier of the hub node may be specified in a query using the two or more predicates, thereby allowing data associated with the compound relationship to be readily identified, modified and/or extracted.

First claim

What is claimed is:

1. A computer-system-implemented method for representing a compound relationship in a graph stored in a graph database, the method comprising:
defining the compound relationship based on two or more predicates associated with two or more edges between two or more nodes in the graph;
generating, in the graph, a hub node that corresponds to the compound relationship and that has an identifier that is hidden from users of the graph;
adding an edge associated with an attribute predicate between the hub node and a node that includes an attribute of one of the two or more nodes; and
when a cardinality of the attribute predicate is equal to one, replacing the attribute with an updated attribute of the one of the two or more nodes.

2. The method of claim 1 , wherein the method further comprises generating a query with edges that include the two or more predicates; and
wherein the two or more predicates specify the identifier of the hub node.

3. The method of claim 2 , wherein the method further comprises executing the query against the graph database.

4. The method of claim 1 , wherein the method further comprises assigning to the hub node the identifier, which is a local identifier, based on the two or more predicates.

5. The method of claim 4 , wherein the method further comprises adding an edge associated with an identifier predicate between the hub node and a node that includes the local identifier.

6. The method of claim 1 , wherein the method further comprises, when a cardinality of the attribute predicate is greater than one, adding another edge associated with the attribute predicate between the hub node and another node that includes an updated attribute of the one of the two or more nodes.

7. The method of claim 1 , wherein the identifier of the hub node is hidden from the users of the graph so that the identifier of the hub node is not visible external to the graph database.

8. The method of claim 1 , wherein the graph comprises the nodes, the edges between the nodes and the predicates to represent and store data with index-free adjacency.

9. An apparatus, comprising:
one or more processors;
memory; and
a program module, wherein the program module is stored in the memory and, during operation of the apparatus, is executed by the one or more processors to represent a compound relationship in a graph stored in a graph database, the program module including:
instructions for defining the compound relationship based on two or more predicates associated with two or more edges between two or more nodes in the graph;
instructions for generating, in the graph, a hub node that corresponds to the compound relationship and that has an identifier that is hidden from users of the graph;
instructions for adding an edge associated with an attribute predicate between the hub node and a node that includes an attribute of one of the two or more nodes; and
instructions for, when a cardinality of the attribute predicate is equal to one, replacing the attribute with an updated attribute of the one of the two or more nodes.

10. The apparatus of claim 9 , wherein the program module further comprises instructions for generating a query with edges that include the two or more predicates; and
wherein the two or more predicates specify the identifier of the hub node.

11. The apparatus of claim 10 , wherein the program module further comprises instructions for executing the query against the graph database.

12. The apparatus of claim 9 , wherein the program module further comprises instructions for assigning to the hub node the identifier, which is a local identifier, based on the two or more predicates.

13. The apparatus of claim 12 , wherein the program module further comprises instructions for adding an edge associated with an identifier predicate between the hub node and a node that includes the local identifier.

14. The apparatus of claim 9 , wherein the program module further comprises instructions for, when a cardinality of the attribute predicate is greater than one, adding another edge associated with the attribute predicate between the hub node and another node that includes an updated attribute of the one of the two or more nodes.

15. The apparatus of claim 9 , wherein the identifier of the hub node is hidden from the users of the graph so that the identifier of the hub node is not visible external to the graph database.

16. A system, comprising:
a processing module comprising a non-transitory computer readable medium storing instructions that, when executed, cause the system to:
define a compound relationship representing a compound relationship in a graph stored in a graph database, wherein the compound relationship is based on two or more predicates associated with two or more edges between two or more nodes in the graph;
generate, in the graph, a hub node that corresponds to the compound relationship and that has an identifier that is hidden from users of the graph;
add an edge associated with an attribute predicate between the hub node and a node that includes an attribute of one of the two or more nodes; and
when a cardinality of the attribute predicate is equal to one, replace the attribute with an updated attribute of the one of the two or more nodes.

Assignees

• Linkedin Corp

Inventors

• Shankar Shyam
• Parikh Karan R
• Carter Andrew J
• Meyer Scott M
• Shankar Srinath

Classifications

• G06F17/30336

  Physics · mapped topic

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30554

  Physics · mapped topic

• G06F17/30604

  Physics · mapped topic

• G06F16/288 Primary

  Entity relationship models · CPC title