GRAPH STORE

• US 20100174692A1
• Filed: 01/20/2010
• Published: 07/08/2010
• Est. Priority Date: 03/15/2007
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: MEYER, Scott, Michener, Barak, Giannandrea, John, Degener, Jutta
• Application Number:
  US12/690,642
• Publication Number:
  US 20100174692A1
• Time in Patent Office: Days
• US Class Current: 707/696
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

A new database design is implemented in which everything in the database is modeled with primitives, including the links and nodes for a graph tuple store. A query syntax provides a nested tree of constraints with a single global schema. Various optimization techniques for queries and replication techniques are also described.

Claims

1. A computer implemented method for establishing a primitive-based graph database, comprising the steps of:

a processor configured to providing a plurality of primitives that are identified by globally unique identifiers (GUIDs) which consist of a database id and a primitive id;

wherein, once written, primitives are read only; and

wherein said primitives collectively establish a log-structured or append-only database;

said processor configured for assigning primitive ids to primitives in said database sequentially as said primitives are written; and

said processor configured for providing a plurality of fields for each primitive, wherein any or all of said fields may be null, said fields comprising;

a left field comprising a guid representing a first end of a relationship arrow;

a right field comprising a guid representing a second end of said relationship arrow;

a type field comprising a guid that is used in conjunction with said left field and right field to specify a type of a relationship;

a scope field comprising a guid that identifies a creator of a given primitive; and

a value field comprising a string that carries any of literal values, strings, numbers, and dates;

said processor configured for responding to user interaction with said database to establish one or more primitives that comprise either nodes without a left field or a right field, or links which always have a left field and which can also have a right field;

wherein nodes represent identities and carry no other data; and

wherein links represent properties of an identity, wherein said links comprise either a literal value or a relationship;

wherein a node and its associated links comprise an object with fields (properties) described by one or more types;

said processor configured for modifying a primitive to change said primitive'"'"'s value by writing a new primitive carrying a modification and marking said new primitives as a replacement for the primitive that it is replacing;

said processor configured for deleting a primitive by writing a new primitive which marks the primitive to be deleted as deleted; and

said processor configured for removing deleted or versioned primitives during query execution.

2. The method of claim 1, further comprising the steps of:

said processor configured for positing a query to said database, said query comprising a template expression comprising a parenthesized list of zero or more constraints, wherein one or more of said constraints define which primitives match said query, and wherein one or more of said constraints define instructions that detail what information is returned to query matches and/or how said information is sorted and formatted;

said processor configured, when a query executes, for evaluating each of a plurality of parenthesized nesting levels of templates to a list of primitive components that match said query;

wherein if a constraint holds subconstraints, said subconstraints are evaluated to nested lists of primitives that match a particular subconstraint; and

wherein multiple constraints combine disjunctively; and

said processor configured for generating a plurality of resulting query trees which are expanded to yield query results.

3. The method of claim 1, further comprising the steps of:

said processor configured for creating an index of said primitives on said database;

said processor configured for immediately writing primitives to a log file of said primitives, one after the other, without indexing, on said database;

said processor configured for maintaining an up to date cache of primitives to be written to said index;

said processor configured for delaying flush of said index from said cache to said database; and

said processor configured for writing said index from said cache to said database and, when writing a primitive to said database, performing a series of callbacks to update said index.

4. The method of claim 1, further comprising:

said processor configured for providing primitives that point to other primitives that they version.

5. The method of claim 4, further comprising:

said processor configured for providing lineages of mutual re-versioning primitives that eventually point to an original, said original comprising a primitive that has no previous pointer;

said processor configured for polling said original primitive to find an index that lists all primitives in a lineage; and

said processor configured for identifying a subsequent primitive in said lineage by performing a look up in said index to determine if there is a next entry in said index.

6. The method of claim 4, further comprising:

said processor configured for providing a tombstone mechanism wherein a flag is set relative to a primitive to indicate that said primitive does not exist and wherein it is not possible return said primitive in response to a query.

7. The method of claim 6, wherein said query is satisfied by initially, simultaneously applying at least two different strategies, and wherein a strategy that yields results more quickly is applied to complete said query.

8. The method of claim 2, wherein primitives are nested, stacked, or combined to formulate a query.

9. The method of claim 4, further comprising:

said processor configured for capturing and preserving user input during a long cycle of read/write interactions; and

said processor configured for guaranteeing that writes of connected subgraphs of primitives are atomic and durable;

wherein the user'"'"'s input is always preserved, and, if the user desires, it can easily be re-instated by browsing the modification history.

10. The method of claim 9, said performing of callbacks step further comprising the steps of:

said processor configured for providing a graph server having a time ordered output buffer chain for each connection to each of a plurality of clients comprising data waiting to be sent back in order to a client;

said processor configured for attaching a callback to each individual output buffer in said output buffer chain, said call back comprising a function pointer to a function within said graph server, said call back indicating how up-to-date said data should be at this point in time;

said database maintaining a counter as it executes write operations;

said database executing said write operations;

said database updating said counter to a current state;

said processor configured for comparing a callback value to said counter;

wherein said callback is satisfied when said counter indicates that said database is up-to-date.

11. The method of claim 4, further comprising the steps of:

said processor configured wherein said sequential IDs comprise a virtual time that allows query results to be guaranteed consistent as of any desired virtual time; and

said processor configured for pending said read request until said replica is at least caught up to the entry point encapsulated into said virtual time.

12. The method of claim 11, said processor configured for using a timestamp field in a primitive to transform real time into virtual time.

13. The method of claim 4, further comprising:

when a primitive is written, said processor configured for storing said primitive in an indexed, sequential access database by;

immediately updating said index;

delaying flushing of said index to said database; and

immediately writing a log file of primitives, one after the other, without indexing, to said database; and

in the event of a system failure, rebuilding said index by processing forward from an index location at a time of said system failure to a log file location.

14. The method of claim 13, further comprising:

said processor configured for attaching a callback to individual output buffers comprising said log file of primitives, said callback comprising a function pointer to a function within a graph, wherein said callback comprises an up-to-date index for said database, said database comprising a similar index that is incremented as said primitives are written to said database, wherein said callback is satisfied when said database index is up-to-date, as indicated by a match to said up-to-date index, wherein said callback guarantees that what was written to the database is, in fact, written.