Graph Data Modeling

Some questions are about links. Who bought what? Who brought in a new customer?

Which table feeds which table? That is a question about links too.

A graph stores data as things and the links between them. This chapter shows how to model a graph and how to ask it questions. It also shows when plain tables are still the better choice.

Recap: Entities, Relationships & Cardinality showed how things link. Keys & Identity gave each thing an id.

Normalization & Denormalization showed that a join rebuilds a link at query time. NoSQL & Access-Pattern Modeling named graph stores as one of four kinds of NoSQL store. This chapter covers that kind.

What you will learn

1. Nodes, relationships, labels and properties.
2. Cypher: how to ask a graph a question.
3. When a fact is a node, a relationship, or a property.
4. Walks of many hops, in Cypher and in a SQL recursive CTE.
5. When a graph helps, and when plain tables are enough.

Most graph databases use the property graph model. You need four words:

• A node is one thing, such as a customer or a product.
• A label is the type of a node, such as Customer or Product.
• A relationship, also called an edge, links two nodes. It has a type, such as BOUGHT, and a direction.
• A property is a named value on a node or on a relationship, such as name or quantity.

Now draw the shared shop as a graph. Customers are nodes, products are nodes, and each row of order_items becomes a link. Here are the 10 nodes:

And here are the 7 BOUGHT relationships. Each one points from a customer to a product. The order id and the quantity are properties of the link:

Omar is a node with no links, because he has no orders. Order 105 has no items, so it adds no link.

Cypher is the query language many graph databases use. This is how you create one customer, one product and one link:

CREATE (asha:Customer {customer_id: 1, name: 'Asha'})
CREATE (pen:Product {name: 'Pen'})
CREATE (asha)-[:BOUGHT {order_id: 101, quantity: 2}]->(pen);

The direction is stored. Asha BOUGHT Pen does not say that Pen BOUGHT Asha.

A second graph model is RDF, the Resource Description Framework. It stores each fact as a triple: subject, predicate, object, such as Asha, bought, Pen.

A plain triple has no room for a property like quantity, so RDF needs an extra step for it. The rest of this chapter uses the property graph.

In Cypher you draw the shape you want to find. Nodes go in round brackets. A relationship goes in square brackets, with an arrow.

MATCH finds every place in the graph where your shape fits. RETURN says which values to show. The short names c, b and p let you use a part in RETURN.

MATCH (c:Customer)-[b:BOUGHT]->(p:Product {name: 'Pen'})
RETURN c.name AS customer, b.quantity AS quantity
ORDER BY customer;

Now ask a question with two hops. A hop is one step along a relationship. Customers who bought a Pen also bought what?

Start at Pen. Step back along BOUGHT to a customer, then forward to another product. The arrow <- walks a link backwards:

MATCH (:Product {name: 'Pen'})<-[:BOUGHT]-(c:Customer)-[:BOUGHT]->(other:Product)
WHERE other.name <> 'Pen'
RETURN other.name AS product, count(DISTINCT c) AS customers
ORDER BY product;

In SQL the links live in a table. Here is bought, with one row for each customer and product. The same question needs a self-join, which joins a table to itself:

SELECT b2.product, COUNT(DISTINCT b2.customer_id) AS customers
FROM bought b1
JOIN bought b2
  ON b2.customer_id = b1.customer_id
 AND b2.product <> b1.product
WHERE b1.product = 'Pen'
GROUP BY b2.product
ORDER BY b2.product;

GQL is the standard language for graph queries from ISO, the International Organization for Standardization. ISO published it in 2024 as ISO/IEC 39075. Its patterns look much like Cypher.

For each fact, you choose: node, relationship, or property. Start from the questions, as in NoSQL & Access-Pattern Modeling. Nouns usually become nodes, and verbs become relationships.

Use this table as a guide:

A fact becomes a node when you want to walk to it, or when it joins three or more things. Order 106 joins Dev, Chair and Lamp.

Say you give each order its own node. The meaning of "bought together" changes. It now means in the same order, not by the same customer:

// (Dev)-[:PLACED]->(:Order)-[:CONTAINS {quantity}]->(:Product)
MATCH (:Product {name: 'Lamp'})<-[:CONTAINS]-(o:Order)-[:CONTAINS]->(other:Product)
WHERE other.name <> 'Lamp'
RETURN o.order_id AS order_id, other.name AS product;

One more habit helps. Give each meaning its own relationship type, such as BOUGHT or PLACED. One RELATED_TO type with a "kind" property makes every query check that property.

A traversal is a walk along relationships. A variable-length path matches any number of hops in a range. In Cypher you write a star: *1..3 means one to three hops.

To try it, add made-up REFERRED links. Each link means one customer brought in another. They are not part of the shared shop:

Who did Asha bring in, directly or through others? The star with no upper limit walks as far as the links go:

MATCH p = (:Customer {name: 'Asha'})-[:REFERRED*1..]->(c:Customer)
RETURN c.name AS customer, length(p) AS hops
ORDER BY hops, customer;

In SQL, a fixed join chain needs one more join for each hop. A recursive CTE has no such limit. A CTE is a named query that starts with WITH.

CTEs, Subqueries & Query Structure in the SQL module teaches recursive CTEs. In short, a start query finds the first hop. A step query joins the rows found last round to the table.

SQL repeats the step until no new rows appear:

WITH RECURSIVE downline (customer_id, hops) AS (
  SELECT new_customer_id, 1
  FROM referrals
  WHERE referrer_id = 1
  UNION ALL
  SELECT r.new_customer_id, d.hops + 1
  FROM referrals r
  JOIN downline d ON r.referrer_id = d.customer_id
)
SELECT c.name AS customer, d.hops
FROM downline d
JOIN customers c ON c.customer_id = d.customer_id
ORDER BY d.hops, c.name;

Busy nodes

A busy node has a huge number of links. People call it a super-node.

Imagine a Pen bought by a million customers. A walk through it reaches a million nodes.

Four habits help:

• Limit the number of hops.
• Filter on a property of the link early, such as quantity.
• Start from the small side of the question and walk toward the busy node.
• Do not run an unbounded walk from a busy node.

Two things decide it: how many hops, and what you want back. Here are five kinds of question:

Most questions in the first three rows do not need a graph database. A graph database pays off when deep walks are your main work. That is when a recursive CTE gets hard to write or to keep fast.

A model or a database

A graph model is a way to think about your data. You can keep it in tables and walk it with a recursive CTE. A graph database stores nodes and relationships directly and has a graph query language.

Neo4j is a graph database that uses Cypher.

Amazon Neptune is a graph database that Amazon Web Services (AWS) runs for you. Its property graphs use openCypher, an open form of Cypher, or Gremlin, another graph language. Its RDF graphs use SPARQL, the query language for RDF.

A second database means a second copy of your data to keep in sync. Totals over many rows stay in the warehouse. Many teams use both.

Five ideas to keep:

1. A property graph has labelled nodes and typed, directed relationships. Both can have properties.
2. The arrow in your query must match the stored direction, or you get no rows.
3. Make a fact a node when you walk to it or when it joins three or more things.
4. A star walks many hops. A recursive CTE does the same in SQL. Stop loops with a limit.
5. Use joins for fixed hops, a recursive CTE for an occasional deep walk, and a warehouse for totals. Use a graph database when deep walks are your main work.

Check yourself

• In the shop graph, which way does BOUGHT point? What does the other arrow return?
• How many hops is it from Asha to Omar in the REFERRED data?
• Why does an Order node change what "bought together" means?

Each exercise opens a canvas for an entity-relationship diagram (ERD). You draw the model, and the review checks it against sample rows.

Start with the first one. Write down the questions first. Then decide which facts are nodes, links or properties.