Cypher: nodes, relationships, patterns and paths

Cypher is ASCII art

The session opens with a definition worth an exam answer: Neo4j "is a graph database management system implemented in Java. It is A.C.I.D. compliant. It has its own query language, named Cypher" (p. 1332). Cypher "focuses on the clarity of expressing what to retrieve from a graph, not on how to retrieve it" (p. 1383): it is declarative, like SQL. The property graph itself is the subject of lesson 10; here you learn to write it down.

The slide that introduces Cypher is a drawing: a circle "You", an arrow ARE_LEARNING, a circle "Cypher". Cypher types that drawing on the keyboard: round brackets for a node, square brackets inside an arrow for a relationship (Fig. 1).

A node pattern holds a variable, zero or more labels after colons, and properties in curly braces (p. 1336); every part is optional. The variable is a name that lives inside one query; a label is a type tag, and a node may carry several; the property map is a set of equality conditions in MATCH and of values to store in CREATE.

A relationship pattern has the same three parts, but a relationship has exactly one type. The colon is the whole difference between a name and a filter: [relatedTo] is a variable that matches a relationship of any type, [:ACTED_IN] is a type filter without a name, and [r:ACTED_IN] is both. The slides drop this colon once themselves, on p. 1365; the red pen is in lesson 12.

No colon, no filter: [ACTED_IN] is a variable that matches any relationship; [:ACTED_IN] matches ACTED_IN only.

The arrow head is a filter too. -[:MANAGES]-> and <-[:MANAGES]- fix the direction, and one relationship can be written from either end: (a:Employee)<-[:MANAGES]-(b:Manager) is "a is managed by b" (p. 1344). Leave the head out, -[:KNOWS]-, and the relationship may point either way. Chain them and you have a path pattern: (p)-[:KNOWS]-(friend)-[:KNOWS]-(foaf) is the slide's "Friend-of-a-friend relationship" — in SQL, a Knows table joined with itself.

Writing the graph: CREATE, MERGE, SET, DELETE

CREATE "allows the creation of nodes and relationships" (p. 1334); the slide labels the parts "Variable : Node Label", "Node Properties", "Node - Identified by the parenthesis".

// creates 1 node with the label Person and 3 properties
CREATE (ee:Person { name: "Emil", from: "Sweden", klout: 99 })

One CREATE can write several nodes, separated by commas, and a property may hold a list (p. 1335):

// creates 3 Person nodes; Francis's "from" is a list
CREATE (ee:Person { name: "Emil", from: "Sweden", klout: 99 }),
  (a:Person { name: "Richard", from: "UK", klout: 80 }),
  (j:Person { name: "Francis", from: ["Sweden","UK"], klout: 75 })

The same slide writes a node with two labels and one with none, and returns what it has just created. Double and single quotes both delimit strings; a list holds values of one type, and a property cannot hold a nested map.

// 2 nodes: one :Person:Fisherman, one with no label
CREATE (ee:Person:Fisherman), (a)

// returns 1 row: "Andy"
CREATE (a {name: 'Andy'}) RETURN a.name

A relationship needs its two end nodes first. Page 1339 creates Mark and Mike, finds them, and draws the arrow:

// creates 2 Person nodes, Mark and Mike
CREATE (e:Person {name: "Mark"}), (a:Person {name: "Mike"})

// returns 1 row: "KNOWS"
MATCH
  (a:Person),
  (b:Person)
WHERE a.name = 'Mike' AND b.name = 'Mark'
CREATE (a)-[r:KNOWS]->(b)
RETURN type(r)

Neo4j adds two rules the slide leaves implicit: in CREATE a relationship needs a direction ("Only directed relationships are supported in CREATE") and exactly one type ("Exactly one relationship type must be specified for CREATE"). In MATCH both may be left out.

Now run the same MATCH with a second CREATE (p. 1340):

// returns "KNOWS"; Mike now has two KNOWS and one BEFRIEND to Mark
MATCH
  (a:Person),
  (b:Person)
WHERE a.name = 'Mike' AND b.name = 'Mark'
CREATE (a)-[r:KNOWS {since: 2015}]->(b), (a)-[h:BEFRIEND]->(b)
RETURN type(r)

The slide insists: "N.B. The two KNOWS relationships we created are different even though they have the same name". CREATE never looks before it writes. The create-if-absent clause is MERGE, which lecture 06 shows "ID-based" on p. 270: MERGE (player:Player {id: row.playerUri}) finds the player with that id or creates it, and its ON CREATE SET part runs only on creation.

// creates a KNOWS from Mike to Mark only if none exists;
// a second run finds it and writes nothing
MATCH (a:Person {name: 'Mike'}), (b:Person {name: 'Mark'})
MERGE (a)-[:KNOWS]->(b)

SET changes what exists: SET p.age = 30 writes a property, SET p:Manager adds a label (p. 1367 tags actors this way), REMOVE p:Manager takes it off.

// 1 row: Emil, now :Person:Fisherman with klout 100
MATCH (ee:Person {name: "Emil"})
SET ee:Fisherman, ee.klout = 100
RETURN labels(ee), ee.klout

Deleting starts from a MATCH: you delete what a variable points to. Page 1342 deletes Ben's KNOWS relationships, leaving the far end anonymous, (); page 1337 deletes Ben.

// deletes Ben's outgoing KNOWS relationships, not the nodes
MATCH (n {name: 'Ben'})-[r:KNOWS]->() DELETE r

// deletes the node Ben, but only if no relationship touches him
MATCH (n:Person {name: 'Ben'}) DELETE n

If Ben still knows someone, the second statement fails and nothing changes: "Cannot delete node<…>, because it still has relationships." A graph never keeps an arrow with a missing end. DETACH "removes all the relationships before removing the nodes" (p. 1343):

// deletes every node with all its relationships: an empty graph
MATCH (n) DETACH DELETE n

Reading the graph: the movie database

Reading clauses come in a fixed order (p. 1338):

// 1 row: the node Emil
MATCH (ee:Person) WHERE ee.name = "Emil" RETURN ee;

The slide says "the MATCH clause returns all the nodes that match the conditions". Sharpen it: MATCH finds every way the pattern fits and makes one row per way, WHERE keeps the rows whose condition is true, RETURN picks the columns. "One row per way" is the key to the hook.

The exercises then switch to Neo4j's movie graph (p. 1353), the one :play movies loads into the Neo4j Browser. The slide lists "Actors", "Directors" and "Films – title, release, tagline"; in the data every person is a :Person and every film a :Movie, acting and directing are relationships, not labels, and the year is released.

The node queries of pp. 1354–1355 show two ways of filtering. A property map is an equality test, a label narrows the search, LIMIT caps the rows:

// 1 row: Tom Hanks (no label: every node is checked)
MATCH (tom {name: "Tom Hanks"}) RETURN tom

// 1 row: the film Cloud Atlas
MATCH (cloudAtlas {title: "Cloud Atlas"}) RETURN cloudAtlas

// 10 rows: the names of 10 people
MATCH (people:Person) RETURN people.name LIMIT 10

Anything other than equality needs WHERE:

// 20 rows: the films released from 1990 to 1999
MATCH (nineties:Movie)
WHERE nineties.released >= 1990 AND nineties.released < 2000
RETURN nineties.title

// 1 row: 106
MATCH (person:Person)
WHERE person.born < 1970
RETURN COUNT(person.name)

Pattern queries put relationships to work (pp. 1356–1359). Read each aloud: "Tom Hanks, acted in, some movie".

// 12 rows: Tom Hanks and one of his films per row
MATCH (tom:Person {name: "Tom Hanks"})-[:ACTED_IN]->(tomHanksMovies)
RETURN tom,tomHanksMovies

The slide's picture also shows a DIRECTED arrow to That Thing You Do: the Browser draws every relationship between the nodes on screen (Tom Hanks also directed it), but the twelve rows hold only ACTED_IN matches.

// 3 rows: Tom Tykwer, Lilly Wachowski, Lana Wachowski
MATCH (cloudAtlas {title: "Cloud Atlas"})<-[:DIRECTED]-(directors)
RETURN directors.name

The "Inverse Relationship" of p. 1357 is the same arrow read from the film: (directors)-[:DIRECTED]->(cloudAtlas …) gives the same names. Two arrows meeting in one node find co-actors (p. 1358):

// 39 rows but 34 different people: Meg Ryan comes back 3 times
MATCH (tom:Person {name:"Tom Hanks"})-[:ACTED_IN]->(m)
      <-[:ACTED_IN]-(coActors)
RETURN coActors.name

The shared film (m) does the work of a join. Tom Hanks is never his own co-actor: inside one pattern each relationship is used at most once, and his ACTED_IN to m is taken by the left arm. Meg Ryan returns three times: three shared films, three rows. Last, a relationship with a variable and no type (p. 1359):

// 10 rows: 4 ACTED_IN, 3 DIRECTED, WROTE, PRODUCED, REVIEWED
MATCH (people:Person)-[relatedTo]-(:Movie {title: "Cloud Atlas"})
RETURN people.name, Type(relatedTo), relatedTo

type() returns the type's name (function names ignore case, so Type works); the film has "No variable name" because nothing is returned from it. Try every mark of these four drawings:

Rows are paths: DISTINCT, COUNT and the plan

Back to the hook. The first dataset of the session is the graph of Neo4j's getting-started guide (the slides show only the queries): Emil, Johan, Ian, Rik and Allison, joined by seven KNOWS relationships. "Let's find all of Emil's friends" (p. 1345):

// 2 rows: Emil with Johan, Emil with Ian
MATCH (ee:Person)-[:KNOWS]-(friends)
WHERE ee.name = "Emil" RETURN ee, friends

Then "a new friend that can teach surf to Johan" (p. 1346): a friend of a friend, with an anonymous middle node () because nobody needs its name.

// 1 row: Allison
MATCH (js:Person)-[:KNOWS]-()-[:KNOWS]-(surfer)
WHERE js.name = "Johan" AND surfer.hobby = "surfing"
RETURN DISTINCT surfer

"What would happen if we remove the DISTINCT clause from the query?" (p. 1347). With RETURN COUNT(surfer) the answer is 3, with RETURN COUNT(DISTINCT surfer) it is 1. Three different paths of two KNOWS relationships lead from Johan to Allison: through Ian over the arrow Johan→Ian, through Ian over the arrow Ian→Johan (a second relationship, accepted by the head-less pattern), and through Rik. MATCH makes one row per path; COUNT(x) counts the rows in which x is not null, COUNT(DISTINCT x) the different values. Two numbers, two questions: how many ways, how many people.

A row is one way the drawing fits: COUNT(x) counts paths, COUNT(DISTINCT x) counts things.

One rule keeps the counting finite: within one pattern each relationship is used at most once per row, while nodes may repeat — relationship uniqueness. Johan can be his own friend-of-a-friend, out to Ian over one arrow and back over the other, but never over the same arrow twice.

How does Neo4j turn the pattern into rows? PROFILE "executes the query and provides a detailed execution plan" (p. 1348). Fig. 4 redraws the plan of p. 1349: each box is an operator, and the numbers between the boxes are the rows flowing from one to the next.

The filter not anon_0 = anon_2 is relationship uniqueness written out, and the literal "Johan" has become the parameter $autostring_0 ("Use parameters instead of literals", p. 282). "Estimated rows" are a guess from statistics; "rows" and "db hits" are measured. EXPLAIN shows the same tree without running the query, estimates only: "Use PROFILE / EXPLAIN to analyze the performance of your queries" (p. 282).

Variable-length paths and shortest paths

A star inside the brackets repeats the relationship. "Movies and actors up to 4 "hops" away from "Kevin Bacon"" (p. 1360):

// 135 rows: the nodes 1 to 4 relationships away
// (297 paths before DISTINCT)
MATCH (bacon:Person {name:"Kevin Bacon"})-[*1..4]-(hollywood)
RETURN DISTINCT hollywood

The callouts give the rules: "Distance computed w.r.t. relationships", "Any node", and "Distinct clause, as many paths may lead to the same node". "Movies and actors" undersells it: (hollywood) has no label and the brackets no type, so directors, writers, producers and reviewers come too — and Kevin Bacon himself, around a cycle of four different relationships through Apollo 13, Ron Howard and Frost/Nixon.

The defaults matter: [*] means one or more relationships, never zero; [*0..] also matches the zero-length path, whose ends are one node; the type comes before the star, [:FRIEND*1..3]. And the rule to keep: "Always set an upper limit for your variable length patterns. It's easy to have a query touch all nodes in a graph by mistake" (p. 282).

The Browser underlines risky queries in yellow: "WARNINGS may arise … some operators may be deprecated or the query is performing a lot of operations e.g., cartesian products among the nodes or unbound number of relationships" (p. 1390). A warning is not an error; the query runs. MATCH (a:Person), (b:Person) of p. 1339 is two patterns with no relationship between them: its rows are all pairs of persons, a cartesian product, and only the WHERE narrows them to Mike and Mark (Neo4j filters each side first, so there the product is 1 × 1 and harmless). An unbounded [*] may walk the whole graph.

The shortest path between two people is a built-in function (p. 1361):

// 1 row: one path of length 4
// (six paths tie; Neo4j returns one of them)
MATCH p = shortestPath(
(bacon:Person {name:"Kevin Bacon"})-[*]-
(meg:Person {name:"Meg Ryan"})
)
RETURN p

p = … binds the whole path to a variable; RETURN p gives the "start node, end node and path". shortestPath returns one shortest path, and when several tie you cannot choose which; allShortestPaths returns all of them, and lecture 06 writes both with a bound, [*..6] (p. 280):

// 6 rows: every shortest path, all of length 4
MATCH p = allShortestPaths(
(bacon:Person {name:"Kevin Bacon"})-[*..6]-
(meg:Person {name:"Meg Ryan"})
)
RETURN p

Page 1362 binds both people first and allows one relationship type:

// as printed on p. 1362: no rows on the movie graph
MATCH (KevinB:Person {name: 'Kevin Bacon'} ),
      (Al:Person {name: 'Al Pacino'}),
      p = shortestPath((KevinB)-[:ACTED_IN*]-(Al))
WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL)
RETURN p

Page 1363 takes the WHERE apart: relationships(p) "returns a list containing all the relationships in a path", IN walks r through it, and all() "returns TRUE if the predicate holds for all elements in the given list". Relatives: nodes(p), length(p) (the number of relationships), any(), none().

How Neo4j plans a shortest path

Pages 1368–1373 ask how the shortest path is searched, following Neo4j's manual: "Depending on the predicates to be evaluated, Neo4j plans the shortest path in different ways."

• "By default, Neo4j uses a Fast Bidirectional Breadth-first Search Algorithm if the conditions can be evaluated whilst searching for the path" — "e.g., all nodes must have the Person label", "e.g., no nodes should have a name property".
• "If the predicates need to inspect the whole path before deciding on whether it is valid or not, Neo4j may have to resort to using a Slower Exhaustive Depth-first Search Algorithm" — "e.g., at least one node contains the property name = "Kevin Bacon"".
• "When the Exhaustive Search is planned, it is still only executed when the Fast Algorithm fails to find any matching paths."

Why two algorithms? Breadth-first search grows one ring of neighbours at a time — here from both ends, until the two searches meet — so the first path it completes is a shortest one. A condition on every node or relationship is checked the moment an element is reached: a Movie node fails "all nodes must have the Person label", and everything behind it is "Excluded a priori" (p. 1369). A condition on at least one node cannot be: a branch through a Movie may still reach Kevin Bacon, so it "Cannot be excluded a priori" (p. 1370). Only whole paths can be judged, enumerated depth-first, one branch to its end before the next.

Pages 1371–1373 compare three queries (the tabs below). WHERE length(p) > 1 needs the whole path, so the plan includes the exhaustive fallback: if the path the fast search finds fails the predicate, the exhaustive search returns the shortest one that passes — "Predicates used in the WHERE clause that apply to the shortest path pattern are evaluated before choosing the shortest matching path" (p. 1371). Put WITH p in between and the predicate leaves the pattern: "the query plan will not include the fallback to the Slower Exhaustive Search Algorithm" (p. 1372). The fast search returns its one path; if that path is a direct link of length 1, WHERE throws it away and nothing is left.

A predicate inside the shortest-path MATCH steers the search; after WITH p it only filters the one path already found.

// fast search; "Always returns a result, if exists"
MATCH (KevinB:Person {name: 'Kevin Bacon'} ),
      (Al:Person {name: 'Al Pacino'}),
      p = shortestPath((KevinB)-[:ACTED_IN*]-(Al))
WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL)
RETURN p

// exhaustive fallback planned; "Always returns a result, if exists"
MATCH (KevinB:Person {name: 'Kevin Bacon'}),
      (Al:Person {name: 'Al Pacino'}),
      p = shortestPath((KevinB)-[*]-(Al))
WHERE length(p) > 1
RETURN p

// fast search only;
// "Not guaranteed to return a result, even if it exists"
MATCH (KevinB:Person {name: 'Kevin Bacon'}),
      (Al:Person {name: 'Al Pacino'}),
      p = shortestPath((KevinB)-[*]-(Al))
WITH p
WHERE length(p) > 1
RETURN p

On the movie graph the three cannot be told apart (the first once role is read as roles): Kevin Bacon and Al Pacino are not linked directly, so every path between them is longer than 1, and each query returns a path of length 6. The point is the guarantee, and a toy graph with a direct link shows it. The second puzzle is solved: two words moved the predicate out of the pattern.