NoSQL for Mere Mortals (2015)

---

The “follows” relation is the only relation between developers in the simple model (see Figure 14.2). If Robert Smith follows Andrea Wilson, then Robert will see all of Andrea’s posts when he logs on to the NoSQL social network. The site designers believe the followers of a developer might be interested in who that developer follows as well. For example, if Andrea follows Charles Vita, then Robert should see Charles’s posts as well. You can imagine adding posts from the developers Charles follows, but that could start to overwhelm Robert’s feed.

Figure 14.2 Sample set of “follows” relations in a NoSQL developer social network.

The designers do not have to decide now how deep of a path to pursue looking for posts to show to Robert. The way graph databases are designed makes it easy to alter application features with minor changes to queries. No change in the underlying model is required.

The relation between developers and posts is “created”; that is, developers create posts. This implies a reverse relationship; that is, that posts are “created by” developers. There are two ways to model this:

• A designer could create a directed edge of type “created” from the developer vertex to the post vertex and another directed edge from the post to the developer of type “created by,” as shown in Figure 14.3(a).

Figure 14.3 Developer and post with two directed edges (a); one edge not directed (b).

• Because one of these relations always implies the other, you can avoid using two directed edges by using a single, possibly undirected, edge, as shown in Figure 14.3(b).

Queries Drive Design (Again)

There is no one correct way to model a graph database for all possible problems. If you have queries that frequently involved gathering posts and then looking up the creators of those posts, it makes sense to have a created by relation.

By creating such an edge, you implement a direct link between the post and the developer. It is this feature that allows graph database designers to avoid working with joins to retrieve data from related entities. Following edges between vertices is a simple and fast operation, so it is possible to follow long paths or a large number of paths between vertices without adversely impacting performance.

At first glance, the post-relation-post may not appear useful. After all, posts do not create other posts. However, there is no rule that says all relations between entities need to be the same type. In fact, one of the powerful features of graph database modeling is the ability to use different types of relations. For example, a post may be created in response to another post. This is particularly useful for questions.

Imagine that Robert posted the question: Is there a faster way than Dijkstra’s algorithm to find the shortest path (see Figure 14.4)? Andrea and Charles might each reply with their own answers. Robert then posts another question to clarify his understanding of Andrea’s response. Andrea responds with additional details. Meanwhile, Edith Woolfe adds additional details to Charles’s post. The resulting graph of posts is a tree with Robert’s initial post as the root and branches that follow the two parts of the conversation thread.

Figure 14.4 A conversation thread started with Robert posting a question.

Let’s return the queries that reference vertices and edges and rewrite them in terms of the NoSQL social network example.

As Table 14.1 shows, abstract queries map to useful queries about graph databases. Some queries are based on paths, such as the distance between two nodes; for example, “How many follows relations are between Developer A and Developer B?” Other queries take into account the global structure of the graph, such as “If a developer left the social network, would there be disconnected groups of developers?”

Table 14.1 Mapping from Graph-Specific Queries That Apply to Any Graph to Queries That Apply to a Social Network Graph

When you design graph databases, you start with domain-specific queries. Ultimately, you will want to map these domain-specific queries to graph-specific queries that reference vertices, edges, and graph measures, like centrality and betweenness.

When you have your domain-specific queries mapped to graph-specific queries, you have the full range of graph query tools and graph algorithms available to you to analyze and explore your data.

The following are the basic steps to getting started with graph database design:

• Identify the queries you would like to perform.

• Identify entities in the graph.

• Identify relations between entities

• Map domain-specific queries to more abstract queries so you can implement graph queries and use graph algorithms to compute additional properties of nodes.

Queries drive the design of graph databases. The next sections delve into details about how to perform those queries.

Querying a Graph

The motto of the Perl programing language is “There is more than one way to do it.” The same statement applies to querying graphs.

The Cypher query language provides a declarative, SQL-like language for building queries. Cypher is used with the Neo4j graph database (neo4j.com). Alternatively, developers can use Gremlin, a graph traversal language that works with a number of different graph databases.

The goal in this section is not to teach you the details of these query languages, but to give you a flavor for how each works and show examples of how each language is used.

Cypher: Declarative Querying

Before you can query a graph, you must create one. Cypher statements to create vertices for the preceding NoSQL social network include

CREATE (robert:Developer { name: 'Robert Smith' })
CREATE (andrea:Developer { name: 'Andrea Wilson' })
CREATE (charles:Developer { name: 'Charles Vita' })

These three statements create three vertices. The text robert: Developer creates a developer vertex with a label of robert. The text { name: 'Robert Smith' } adds a property to the node to store the name of the developer.

Edges are added with create statements as well. For example:

CREATE (robert)-[FOLLOWS]->(andrea)
CREATE (andrea)-[FOLLOWS]->(charles)

To query nodes in Cypher, use the MATCH command, which returns all developers in the social network:

MATCH (developer:DEVELOPER)
RETURN (developer)

A comparable query in SQL is

SELECT *
FROM developer

SQL is a declarative language designed to work with tables that consist of rows and columns. Cypher is a declarative language designed to work with graphs that consist of vertices and edges, so it is not surprising that there are ways to query based on both. For example, the following returns all developer nodes linked to Robert Smith:

MATCH (robert:Developer {name:'Robert
Smith'})--(developer:DEVELOPER)
RETURN developers

The MATCH operation starts with the node robert and searches all edges that lead to vertices of type DEVELOPER and returns those that it finds.

Cypher is a rich language with support for many graph operations. It also has clauses found in SQL, such as the following:

• WHERE

• ORDER BY

• LIMIT

• UNION

• COUNT

• DISTINCT

• SUM

• AVG

Because Cypher is a declarative query language, you specify the criteria for selecting vertices and edges, but you do not specify how to retrieve them. If you want control over the way your query retrieves vertices and edges, you should consider using a graph traversal language such as Gremlin.

Gremlin: Query by Graph Traversal

Traverse means to travel across or through. Graph traversal is the process of logically moving from one vertex to another over an edge. Instead of querying by specifying criteria for selecting vertices, as in Cypher, you specify vertices and rules for traversing them.

Basic Graph Traversal

Consider the graph in Figure 14.5. The graph has seven vertices and nine directed edges. Some vertices have edges coming in, some have only edges going out, and others have both.

Figure 14.5 Sample directed graph with vertices with only in, out, and both in and out edges.

Let’s assume a graph G is defined with the vertices and edges shown in Figure 14.5. You can create a variable in Gremlin to refer to a particular vertex, such as

v = G.v(1)

Gremlin also has special terms defined to refer to adjacent edges and vertices. These are

• outE—Outgoing directed edges from a vertex

• inE—Incoming directed edges from a vertex

• bothE—Both inward and outward directed edges from a vertex

• outV—Outgoing vertex of an edge

• inV—Incoming vertex of an edge

• bothV—Both incoming and outgoing vertex of an edge

These are useful for querying edges and graphs based on a starting vertex or edge. For example, if you queried v.outE, you would get the following resultset:

[1-follows-2]
[1-follows-5]

Because the variable v is defined as the vertex v(1) and there are two outgoing edges, Gremlin returns a descriptive string representing those two edges.

Consider the following example:

v2 = G.v(2)

v2.outE
Results:
[2-follows-3]
[2-follows-4]
[2-follows-6]

The vertex 2 has five incident edges, but only three edges are listed above. This is because the other two edges are inbound edges, not outbound edges.

If you want to return the vertices at the end of the outbound edge, you can refer to the inbound vertices of the edges listed in the last example with the following code:

v2.outE.inV
Results:
[3]
[4]
[6]

This model of querying allows you to string together additional combinations of edge and vertex specifications, such as v2.outE.inV.outE.inV.

Gremlin supports more complex query patterns as well.

Traversing a Graph with Depth-First and Breadth-First Searches

There will be times when you do not have a specific starting point. Instead, you want to find all nodes that have a particular property. Cypher uses the MATCH statement for retrieving vertices.

In Gremlin, you can traverse the entire graph and as you visit each vertex, you can test it to determine if it meets your search criteria. For example, you could traverse the graph, starting at vertex 1 by visiting vertex 2, then vertex 3, then vertex 4, then vertex 5, then vertex 6, and finally vertex 7. This is an example of a depth-first search of a graph (see Figure 14.6).

Figure 14.6 Example of a depth-first search.

In a depth-first search, you start traversal at one vertex and select adjacent vertices. You then select the first vertex in that resultset and select adjacent vertices to it. You continue to select the first vertex in the resultset until there are no more edges to traverse.

At that point, you visit the next vertex in the latest resultset. If there are incident edges leading to other vertices, you visit those; otherwise, you continue to the next item in the latest resultset. When you exhaust all vertices in the latest resultset, you return to the resultset selected prior to that and begin the process again.

In a breadth-first search, you visit each of the vertices incident to the current vertex before visiting other vertices. Figure 14.7 shows an example of a breadth-first search traversal.

Figure 14.7 Example of a breadth-first search.

Gremlin supports other specialized types of graph traversal, such as the flow rank pattern that allows for queries such as “rank developers by the number of posts we have both commented on.”