Graph databases

In short: A graph database such as Neo4j stores nodes and relationships instead of tables, and Cypher queries match patterns and paths through them.

Problem

People who bought coffee also bought

Under every product the shop wants a line “People who bought this also bought”. For the coffee beans the query on the SQL database is this:

SQLdatabase: shop

SELECT p2.name, COUNT(DISTINCT o2.customer_id) AS buyers
FROM products p1
JOIN order_items i1 ON i1.product_id = p1.id
JOIN orders o1 ON o1.id = i1.order_id AND o1.status <> 'cancelled'
JOIN orders o2 ON o2.customer_id = o1.customer_id AND o2.status <> 'cancelled'
JOIN order_items i2 ON i2.order_id = o2.id
JOIN products p2 ON p2.id = i2.product_id
WHERE p1.name = 'Coffee beans' AND p2.id <> p1.id
GROUP BY p2.id, p2.name
ORDER BY buyers DESC, p2.name
LIMIT 5;

SELECT p2.name, COUNT(DISTINCT o2.customer_id) AS buyers FROM products p1 JOIN order_items i1 ON i1.product_id = p1.id JOIN orders o1 ON o1.id = i1.order_id AND o1.status <> 'cancelled' JOIN orders o2 ON o2.customer_id = o1.customer_id AND o2.status <> 'cancelled' JOIN order_items i2 ON i2.order_id = o2.id JOIN products p2 ON p2.id = i2.product_id WHERE p1.name = 'Coffee beans' AND p2.id <> p1.id GROUP BY p2.id, p2.name ORDER BY buyers DESC, p2.name LIMIT 5;

▶ RunRestore the queryFresh database

It walks through six tables: from the product to the order lines, to the orders, to the customer, to their other orders, to the lines of those, and to the products. orders and order_items take part twice each. The next wish is heavier still: “the products of the people whose recommendations you follow, and of the people they follow”. Every step is more joins, and “up to three steps” needs WITH RECURSIVE. The question is about connections between things, and in tables the connections are scattered across foreign keys.

The idea

Nodes and relationships

A graph database keeps the data as a graph: nodes (the things, such as a customer and a product) and relationships between them. Every relationship has a type (BOUGHT) and a direction (from the customer to the product). Nodes have labels (:Customer), and both nodes and relationships have properties (name, price, quantity). The relationship is stored in the database, not looked up with a JOIN in every query: from a node the database goes straight to its neighbours.

The best known graph database is Neo4j, and its language is Cypher. Its patterns are drawings made of characters: (c:Customer) is a node, and -[:BOUGHT]-> is an arrow.

graph (like Neo4j)simulator

CREATE (m:Customer {name: 'Maria Ivanova', city: 'Sofia'})
CREATE (k:Product {name: 'Coffee beans', price: 14.90})
CREATE (m)-[:BOUGHT {quantity: 2}]->(k);

MATCH (c:Customer)-[b:BOUGHT]->(p:Product)
RETURN c.name, b.quantity, p.name;

CREATE (m:Customer {name: 'Maria Ivanova', city: 'Sofia'}) CREATE (k:Product {name: 'Coffee beans', price: 14.90}) CREATE (m)-[:BOUGHT {quantity: 2}]->(k); MATCH (c:Customer)-[b:BOUGHT]->(p:Product) RETURN c.name, b.quantity, p.name;

▶ RunRestore the commandsFresh database

The query ends with ;, so it can span several lines. CREATE makes nodes and relationships. MATCH finds everything that fits the pattern, and RETURN says what to show. Under the output the simulator draws the nodes and relationships it found.

More precisely, if you are curious

The simulator knows part of Cypher: MATCH, WHERE, CREATE, MERGE, SET, DELETE, DETACH DELETE, RETURN, ORDER BY, SKIP, LIMIT and a few functions. There is no WITH, OPTIONAL MATCH, UNWIND, no indexes and no constraints. The output looks like the cypher-shell console, without the line with the query time, and the error messages are shorter. The simulator shows the prompt before every line of a query. Neo4j Browser does not need ; at the end and draws the result by itself. Without ORDER BY the simulator returns the rows in the order the nodes were made, and Neo4j promises no order at all.

Try it

Georgi and the bread

The database is empty. Record that the customer Georgi Petrov bought white bread: a node labelled Customer with a name property, a node labelled Product with a name property, and a BOUGHT relationship from the customer to the product.

graph (like Neo4j)simulator

CREATE (g:Customer {name: 'Georgi Petrov'});

CREATE (g:Customer {name: 'Georgi Petrov'});

Check▶ Run

The idea

Patterns

From here on the database is the shop: 20 customers, 25 products in 6 categories and 109 BOUGHT relationships, one for every customer and product from the orders that were not cancelled. They come from the course's SQL database. A product is connected to its category with an IN relationship.

A pattern can be as long as you need: from the customer through the product to the category, without a single join.

graph (like Neo4j)simulator

MATCH (c:Customer {name: 'Elena Dimitrova'})-[:BOUGHT]->(p:Product)-[:IN]->(cat:Category)
RETURN p.name, p.price, cat.name
ORDER BY p.name;

MATCH (c:Customer {name: 'Elena Dimitrova'})-[:BOUGHT]->(p:Product)-[:IN]->(cat:Category) RETURN p.name, p.price, cat.name ORDER BY p.name;

▶ RunRestore the commandsFresh database

The direction in the pattern has to match the direction of the relationship:

graph (like Neo4j)simulator

// The arrow points from the customer to the product. The other way there is nothing:
MATCH (:Product {name: 'Coffee beans'})-[:BOUGHT]->(c:Customer)
RETURN c.name;

// The same relationship, read from the other end:
MATCH (:Product {name: 'Coffee beans'})<-[:BOUGHT]-(c:Customer)
RETURN c.name, c.city
ORDER BY c.name;

// The arrow points from the customer to the product. The other way there is nothing: MATCH (:Product {name: 'Coffee beans'})-[:BOUGHT]->(c:Customer) RETURN c.name; // The same relationship, read from the other end: MATCH (:Product {name: 'Coffee beans'})<-[:BOUGHT]-(c:Customer) RETURN c.name, c.city ORDER BY c.name;

▶ RunRestore the commandsFresh database

There are no BOUGHT arrows from the product to a customer, so the first query finds nobody. <-[:BOUGHT]- reads the same relationship from its other end. -[:BOUGHT]- without an arrowhead finds the relationship in either direction.

More precisely, if you are curious

The graph does not keep the individual orders: a BOUGHT relationship only says that the customer has bought the product. If you need the orders too, they become nodes: (:Customer)-[:PLACED]->(:Order)-[:CONTAINS {quantity: 2}]->(:Product). What is a node and what is a relationship depends on the questions you will ask, just like the schema of an SQL database.

See it

The same question, one pattern

Here is “people who bought coffee also bought” in Cypher:

graph (like Neo4j)simulator

MATCH (:Product {name: 'Coffee beans'})<-[:BOUGHT]-(c:Customer)-[:BOUGHT]->(p:Product)
RETURN p.name, count(c) AS buyers
ORDER BY buyers DESC, p.name
LIMIT 5;

MATCH (:Product {name: 'Coffee beans'})<-[:BOUGHT]-(c:Customer)-[:BOUGHT]->(p:Product) RETURN p.name, count(c) AS buyers ORDER BY buyers DESC, p.name LIMIT 5;

▶ RunRestore the commandsFresh database

The answer is the same as the SQL query's at the start, row by row. The pattern reads from left to right: the coffee, bought by a customer who also bought another product. The coffee is not counted against itself: in one MATCH the same relationship cannot take part twice, and the relationship to the coffee is already taken. In SQL that was a separate condition (p2.id <> p1.id). Only three people bought coffee, so all five products have two buyers each and are ordered by name.

The difference is not only the length. The SQL database looks up every join in an index or in the whole table. The graph database starts from the coffee and follows only its relationships: the work depends on how many relationships are around the coffee, not on how many orders the shop has.

The idea

Variable-length paths

Say the shop has profiles, and every customer can follow the recommendations of other customers: (:Customer)-[:FOLLOWS]->(:Customer). These relationships are invented for the lesson; the SQL database does not have them.

-[:FOLLOWS*1..2]-> is a path of one to two FOLLOWS steps. p = … gives the whole path a name, and length(p) is its number of steps:

graph (like Neo4j)simulator

// All routes of one or two steps. Viktoria is there twice: two paths lead to her
MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer)
RETURN f.name;

// Every person once, with the shortest path to them
MATCH p = (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..3]->(f:Customer)
WHERE f <> me
RETURN f.name, min(length(p)) AS steps
ORDER BY steps, f.name;

// All routes of one or two steps. Viktoria is there twice: two paths lead to her MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer) RETURN f.name; // Every person once, with the shortest path to them MATCH p = (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..3]->(f:Customer) WHERE f <> me RETURN f.name, min(length(p)) AS steps ORDER BY steps, f.name;

▶ RunRestore the commandsFresh database

In the first result Viktoria is there twice: Elena follows Maria and Dimitar, and both of them follow Viktoria. MATCH returns every path, not every person. In the second query WHERE f <> me removes Elena herself: in three steps the path comes back to her (Elena, Maria, Viktoria, Elena).

Who is on the path shows with nodes(p):

graph (like Neo4j)simulator

MATCH p = (:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*2]->(:Customer {name: 'Aleksandar Iliev'})
RETURN [n IN nodes(p) | n.name] AS route;

MATCH p = (:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*2]->(:Customer {name: 'Aleksandar Iliev'}) RETURN [n IN nodes(p) | n.name] AS route;

▶ RunRestore the commandsFresh database

In SQL the same is WITH RECURSIVE over a follows table: a start, UNION ALL and a step that joins follows with the previous rows, plus a step counter. Here it is *1..3.

See it

A path without a bound

A pattern with no type and no direction, “everything connected to Elena”, with a longer and longer path:

graph (like Neo4j)simulator

// Everything connected to Elena, by any relationship, in any direction
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..2]-(x)
RETURN count(*) AS routes;
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..3]-(x)
RETURN count(*) AS routes;
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..4]-(x)
RETURN count(*) AS routes;

// Without an upper bound
MATCH (:Customer {name: 'Elena Dimitrova'})-[*]-(x)
RETURN count(*) AS routes;

// Everything connected to Elena, by any relationship, in any direction MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..2]-(x) RETURN count(*) AS routes; MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..3]-(x) RETURN count(*) AS routes; MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..4]-(x) RETURN count(*) AS routes; // Without an upper bound MATCH (:Customer {name: 'Elena Dimitrova'})-[*]-(x) RETURN count(*) AS routes;

▶ RunRestore the commandsFresh database

98 routes, then 688, then 4,370. Every step multiplies them by six to seven, because a product like white bread is connected to many customers, and each of them to many products. * without an upper bound tries every route. The simulator stops after 100,000 steps, and Neo4j does not stop by itself: the query runs until it runs out of time or memory. So always write an upper bound, and when you can, the type and direction of the relationship too.

Exercise

Recommendations

1. The cheese also needs a “People who bought this also bought” line.

Which three products did the people who bought white cheese buy most? Show the name and the number of buyers (buyers), from the most down, and by name when the numbers are equal.

graph (like Neo4j)simulator

MATCH (:Product {name: 'White cheese'})<-[:BOUGHT]-(c:Customer)
RETURN c.name;

MATCH (:Product {name: 'White cheese'})<-[:BOUGHT]-(c:Customer) RETURN c.name;

Check▶ Run

2. Maria Ivanova follows a few people, and they follow others.

Show the customers Maria Ivanova reaches through FOLLOWS in one or two steps, each once, ordered by name.

graph (like Neo4j)simulator

MATCH (:Customer {name: 'Maria Ivanova'})-[:FOLLOWS]->(f:Customer)
RETURN f.name;

MATCH (:Customer {name: 'Maria Ivanova'})-[:FOLLOWS]->(f:Customer) RETURN f.name;

Check▶ Run

3. Now the real recommendation.

Find the products bought by the people Elena Dimitrova follows in one or two steps, which she has not bought yet. Show the three bought by the most different people (people), and by name when the numbers are equal.

graph (like Neo4j)simulator

MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer)
RETURN DISTINCT f.name;

MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer) RETURN DISTINCT f.name;

Check▶ Run

The idea

When a graph database, and when not

A graph database is good when the question is about connections, often several steps long: recommendations (“people who bought this also bought”), social networks, fraud detection (accounts that share a phone or an address), routes and dependencies, access rights through groups. It is not good for reports that add up numbers from all records, such as revenue by month: such a query does not follow relationships, it reads everything in a row. That is a job for SQL with GROUP BY or for a database built for reports (OLAP). So a graph usually sits next to the SQL database: the orders and the money stay in SQL, and a copy of the connections goes to the graph for the recommendations.

More precisely, if you are curious

Besides Neo4j, Cypher is understood by Memgraph and Amazon Neptune (there the language is called openCypher; Neptune also understands Gremlin and SPARQL), and the Apache AGE extension adds Cypher to PostgreSQL. In 2024 the international standard GQL (ISO/IEC 39075) came out, largely based on the ideas of Cypher. Another kind of graph database is the RDF store with the SPARQL language, where everything is a triple of “subject, predicate, object”.

Test

Check yourself

1. What does the pattern (c:Customer)-[:BOUGHT]->(p:Product) say?

A node labelled Customer, connected to a node labelled Product by a relationship of type BOUGHT that points to the productThe Customer table is joined with the Product tableThe customers and the products with the same name

2. MATCH (me)-[:FOLLOWS*1..2]->(f) RETURN f.name returns Viktoria twice. Why?

Two different paths lead to her, and MATCH returns every pathThe database has a bugViktoria is stored twice

3. What happens to a pattern -[*]- without an upper bound in a large graph?

The routes multiply like an avalanche and the query may never finishNothing special, it is only a little slowerThe database stops at 3 steps by itself

4. You need the revenue by month for the last two years. Where does this query belong?

In the SQL database (or a column database for reports), with SUM and GROUP BYIn the cacheIn the graph database, because the orders are connected to the customers

Check

Start the lesson over

Related lessons

• Builds on: Trees and sequences: WITH RECURSIVE · Relationship types: 1:1, 1:N, M:N · Indexes · OLTP and OLAP
• Continues in: How to choose a database
• Tasks on this topic: Kinds of databases