Graph query logic

• US 9,646,028 B2
• Filed: 08/31/2012
• Issued: 05/09/2017
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Schrock, Nicholas Hage, Byron, Lee Williams, Schafer, Daniel L.
• Primary Examiner(s): Le, Debbie
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US13/601,769
• Publication Number:
  US 20140067850A1
• Time in Patent Office: 1,712 Days
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 3/048 Interaction techniques based on graphical user interfaces [GUI]

Abstract

In one embodiment, a method includes storing one or more graphs, each graph comprising one or more nodes arranged in a hierarchical format, each node representing one or more data items; accessing a query requesting one or more specific data items in the graphs, the query being expressed in a language having a hierarchical format; retrieving the specific data items from the graphs; arranging the specific data items in a hierarchical format; and outputting the specific data items in response to the query.

Claims

1. A computer-implemented method comprising:

storing one or more graphs associated with a social-networking system, each graph comprising one or more nodes arranged in a hierarchical format, the one or more nodes representing one or more data items, respectively, each data item being of a particular data type of a plurality of data types;

receiving, from a third-party system, a call to an API, the call comprising a first query requesting a definition of the first data type, the first query being expressed in a language having a first hierarchical format;

sending, to the third-party system in response to the first query, the definition of the first data type, wherein the definition comprises (1) a name for the first data type, (2) a description for the first data type, and (3) for each of one or more fields of the first data type, a name and description of the field;

receiving, from the third-party system, a second query, the second query requesting one or more of the data items associated with the first data type;

retrieving the requested data items of the first data type from the graphs;

validating the retrieved data items by determining whether the retrieved data items are associated with the first data type;

arranging the requested data items of the first data type in a second hierarchical format; and

sending, to the third-party system in response to the second query, the requested data items of the first data type arranged in the second hierarchical format.

2. The computer-implemented method of claim 1, wherein retrieving the requested data items of the first data type from the graphs comprises:

identifying one or more specific nodes representing the requested data items of the first data type from the graphs; and

retrieving the requested data items of the first data type from the specific nodes.

3. The computer-implemented method of claim 1, wherein:

the first and second query are submitted by a user;

the second query requests one or more data items that satisfy one or more criteria; and

retrieving the requested data items of the first data type from the graphs comprises iteratively,

locating the data item from the graphs that satisfies the criteria;

determining whether the user is authorized to access the data item;

if the user is authorized to access the data item, then including the data item as one of the data items to be outputted; and

if the user is not authorized to access the data item, then discarding the data item,

until the one or more data items are located.

4. The computer-implemented method of claim 1, wherein:

the second query requests one or more first data items that satisfy one or more criteria; and

retrieving the requested data items of the first data type from the graphs comprises;

identifying the one or more data items from the graphs that satisfy the criteria; and

recording the last one of the one or more data items identified.

5. The computer-implemented method of claim 4, further comprising:

accessing a third query requesting one or more second data items that satisfy the criteria, the third query being expressed in the language having the hierarchical format;

identifying the one or more second data items from the graphs that satisfy the criteria beginning after the last one of the one or more first data items identified in response to the second query;

arranging the one or more second data items in a hierarchical format; and

outputting the one or more second data items in response to the third query.

6. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

store one or more graphs associated with a social-networking system, each graph comprising one or more nodes arranged in a hierarchical format, the one or more nodes representing one or more data items, respectively, each data item being of a particular data type of a plurality of data types;

receive, from a third-party system, a call to an API comprising a first query requesting a definition of the first data type, the first query being expressed in a language having a first hierarchical format;

sending, to the third-party system in response to the first query, the definition of the first data type, wherein the definition comprises (1) a name for the first data type, (2) a description for the first data type, and (3) for each of one or more fields of the first data type, a name and description of the field;

receive, from the third-party system, a second query, the second query requesting one or more of the data items associated with the first data type;

retrieve the requested data items of the first data type from the graphs;

validate the retrieved data items by determining whether the retrieved data items are associated with the first data type;

arrange the requested data items of the first data type in a hierarchical format; and

send, to the third-party system in response to the second query, the requested data items of the first data type arranged in the second hierarchical format.

7. The media of claim 6, wherein retrieve the requested data items of the first data type from the graphs comprises:

identify one or more specific nodes representing the requested data items of the first data type from the graphs; and

retrieve the requested data items of the first data type from the specific nodes.

8. The media of claim 6, wherein:

the first and second query are submitted by a user;

the second query requests one or more data items that satisfy one or more criteria; and

retrieve the requested data items of the first data type from the graphs comprises iteratively,

locate the data item from the graphs that satisfies the criteria;

determine whether the user is authorized to access the data item;

if the user is authorized to access the data item, then include the data item as one of the data items to be outputted; and

if the user is not authorized to access the data item, then discard the data item,

until the one or more data items are located.

9. The media of claim 6, wherein:

the second query requests one or more first data items that satisfy one or more criteria; and

retrieve the requested data items of the first data type from the graphs comprises;

identify the one or more data items from the graphs that satisfy the criteria; and

record the last one of the one or more data items identified.

10. The media of claim 9, wherein the software is further operable when executed to:

access a third query requesting one or more second data items that satisfy the criteria, the third query being expressed in the language having the hierarchical format;

identify the one or more second data items from the graphs that satisfy the criteria beginning after the last one of the one or more first data items identified in response to the second query;

arrange the one or more second data items in a hierarchical format; and

output the one or more second data items in response to the third query.

11. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

store one or more graphs associated with a social-networking system, each graph comprising one or more nodes arranged in a hierarchical format, the one or more nodes representing one or more data items, respectively, each data item being of a particular data type of a plurality of data types;

receive, from a third-party system, a call to an API comprising a first query requesting a definition of the first data type, the first query being expressed in a language having a first hierarchical format;

retrieve, using the first query, the definition of the first data type, wherein the definition comprises (1) a name for the first data type, (2) a description for the first data type, and (3) for each of one or more fields of the first data type, a name and description of the field;

receive, from the third-party system, a second query, the second query requesting one or more of the data items associated with the first data type;

retrieve the requested data items of the first data type from the graphs;

validate the retrieved data items by determining whether the retrieved data items are associated with the first data type;

arrange the requested data items of the first data type in a hierarchical format; and

send, to the third-party system in response to the second query, the requested data items of the first data type arranged in the second hierarchical format.

12. The system of claim 11, wherein retrieve the requested data items of the first data type from the graphs comprises:

identify one or more specific nodes representing the requested data items of the first data type from the graphs; and

retrieve the requested data items of the first data type from the specific nodes.

13. The system of claim 11, wherein:

the first and second query are submitted by a user;

the second query requests one or more data items that satisfy one or more criteria; and

retrieve the requested data items of the first data type from the graphs comprises iteratively,

locate the data item from the graphs that satisfies the criteria;

determine whether the user is authorized to access the data item;

if the user is authorized to access the data item, then include the data item as one of the data items to be outputted; and

if the user is not authorized to access the data item, then discard the data item,

until the one or more data items are located.

14. The system of claim 11, wherein:

the second query requests one or more first data items that satisfy one or more criteria; and

retrieve the requested data items of the first data type from the graphs comprises;

identify the one or more data items from the graphs that satisfy the criteria; and

record the last one of the one or more data items identified.

15. The system of claim 14, wherein the processors are further operable when executing the instructions to:

access a third query requesting one or more second data items that satisfy the criteria, the third query being expressed in the language having the hierarchical format;

identify the one or more second data items from the graphs that satisfy the criteria beginning after the last one of the one or more first data items identified in response to the second query;

arrange the one or more second data items in a hierarchical format; and

output the one or more second data items in response to the third query.