Property Graphs

In the property graph (also known as labeled property graph) model, each vertex consists of the following:

• A unique identifier

• A label (string) to describe the type of object this vertex represents

• A set of outgoing edges

• A set of incoming edges

• A collection of properties (key-value pairs)

Each edge consists of the following:

• A unique identifier

• The vertex at which the edge starts (the tail vertex)

• The vertex at which the edge ends (the head vertex)

• A label to describe the kind of relationship between the two vertices

• A collection of properties (key-value pairs)

You can think of a graph store as consisting of two relational tables, one for vertices and one for edges, as shown in Example 3-3 (this schema uses the PostgreSQL jsonb datatype to store the properties of each vertex or edge). The head and tail vertices are stored for each edge; if you want the set of incoming or outgoing edges for a vertex, you can query the edges table by head_vertex or tail_vertex, respectively.

Example 3-3. Representing a property graph with a relational schema

CREATE TABLE vertices (
    vertex_id   integer PRIMARY KEY,
    label       text,
    properties  jsonb
);

CREATE TABLE edges (
    edge_id     integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id),
    head_vertex integer REFERENCES vertices (vertex_id),
    label       text,
    properties  jsonb
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Some important aspects of this model are as follows:

• Any vertex can have an edge connecting it with any other vertex. There is no schema that restricts which kinds of things can or cannot be associated.

• Given any vertex, you can efficiently find both its incoming and its outgoing edges and thus traverse the graph (i.e., follow a path through a chain of vertices) both forward and backward. (That’s why Example 3-3 has indexes on both the tail_vertex and head_vertex columns.)

• By using different labels for different kinds of vertices and relationships, you can store several kinds of information in a single graph, while still maintaining a clean data model.

The edges table is like the many-to-many associative, or join, table we saw in “Many-to-One and Many-to-Many Relationships”, generalized to allow many types of relationship to be stored in the same table. There may also be indexes on the labels and the properties, allowing vertices or edges with certain properties to be found efficiently.

Note

A limitation of graph models is that an edge can associate only two vertices with each other, whereas a relational join table can represent three-way or even higher-degree relationships by having multiple foreign-key references on a single row. Such relationships can be represented in a graph by creating an additional vertex corresponding to each row of the join table and edges to/from that vertex, or by using a hypergraph.

Those features give graphs a great deal of flexibility for data modeling, as illustrated in Figure 3-6. The figure shows a few things that would be difficult to express in a traditional relational schema, such as different kinds of regional structures in different countries (France has départements and régions, whereas the US has counties and states), quirks of history such as a country within a country (ignoring for now the intricacies of sovereign states and nations), and varying granularity of data (Lucy’s current residence is specified as a city, whereas her place of birth is specified at only the level of a state).

You could imagine extending the graph to also include many other facts about Lucy and Alain, or other people. For instance, you could use the graph to indicate any food allergies they have (by introducing a vertex for each allergen, and an edge between a person and an allergen to indicate an allergy), and link the allergens with a set of vertices that show which foods contain which substances. Then you could write a query to find out what is safe for each person to eat. Graphs are good for evolvability: as you add features to your application, a graph can easily be extended to accommodate changes in the application’s data structures.