We saw earlier that the type of relationships is an important distinguishing feature across data models. If your application has mostly one-to-many relationships (tree-structured data) and few other relationships between records, the document model is appropriate.
But what if many-to-many relationships are very common in your data? The relational model can handle simple cases of many-to-many relationships, but as the connections within your data become more complex, it becomes more natural to start modeling that data as a graph.
A graph consists of two kinds of objects: vertices (also known as nodes or entities) and edges (also known as relationships or arcs). Many kinds of data can be modeled as a graph. Typical examples include the following:
Social graphs
Vertices are people, and edges indicate which people know each other.
The web graph
Vertices are web pages, and edges indicate HTML links to other pages.
Road or rail networks
Vertices are junctions, and edges represent the roads or railway lines between them.
Well-known algorithms can operate on these graphs—for example, map navigation apps search for the shortest path between two points in a road network, and PageRank can be used on the web graph to determine the popularity of a web page and thus its ranking in search results.
Graphs can be represented in several ways. In the adjacency list model, each vertex stores the IDs of its neighbor vertices that are one edge away. Alternatively, you can use an adjacency matrix, a two-dimensional array in which each row and column corresponds to a vertex, where the value is 0 when there is no edge between the row vertex and the column vertex and 1 when there is an edge. An adjacency list is good for graph traversals, and matrices are good for machine learning (see “DataFrames, Matrices, and Arrays”).
In the examples just given, all the vertices in a graph represent the same kind of thing (people, web pages, or road junctions, respectively). However, graphs are not limited to such homogeneous data. An equally powerful use of graphs is to provide a consistent way of storing completely different types of objects in a single database. For example:
-
Facebook maintains a single graph with many types of vertices and edges. Vertices represent people, locations, events, check-ins, and comments made by users; edges indicate which people are friends with each other, which check-in happened in which location, who commented on which post, who attended which event, and so on.
-
Search engines use knowledge graphs to record facts about entities that often occur in search queries, such as organizations, people, and places. This information is obtained by crawling and analyzing the text on websites; some websites, such as Wikidata, also publish graph data in a structured form.
Graphs provide several different, but related, ways of structuring and querying data. In this section we will discuss the property graph model (implemented by Neo4j, Memgraph, KùzuDB, and others) and the triple store model (implemented by Datomic, AllegroGraph, Blazegraph, and others). These models are fairly similar in what they can express, and some graph databases (such as Amazon Neptune) support both.
We will also look at four query languages for graphs (Cypher, SPARQL, Datalog, and GraphQL), as well as SQL support for querying graphs. Other graph query languages exist, such as Gremlin, but these will give us a representative overview.
To illustrate these languages and models, this section uses Figure 3-6 as a running example. It could be taken from a social network or a genealogical database; it shows two people, Lucy from Idaho and Alain from Saint-Lô, France. They are married and living in London. Each person and each location is represented as a vertex, and the relationships between them are represented as edges. This example will help demonstrate some queries that are easy in graph databases but difficult in other data models.
Diagram of graph-structured data showing relationships between two people, Lucy and Alain, with locations such as Idaho and Saint-Lô linked through vertices and edges, illustrating geographical and personal connections.
Figure 3-6. Graph-structured data (boxes represent vertices, arrows represent edges)