Why graphs: property graphs, RDF and Neo4j

A graph, in the slides' words

Three kinds of question are graph questions. Neighbourhoods: who are A's friends, and how many? Paths: can a message travel from A to O, and by which shortest route? Patterns: where does a shape occur — two bank accounts sharing one phone number, a sailor who reserved a red boat? Part 1 of the deck (pp. 218–249) supplies the vocabulary; what the text below does not explain, a table lists in the slides' wording.

Informally a graph is "a set of nodes joined by a set of lines or arrows" (p. 224). Formally (p. 225) it is an ordered triple \(G = (V, E, f)\): \(V\) is the set of vertices (nodes), \(E\) the set of edges, and \(f\) a function that "maps each element of E to an unordered pair of vertices in V" — the two endpoints of the edge. Lines are undirected edges. Arrows give a directed graph, in which "An edge is an ordered pair of nodes" (p. 234). Numbers on the edges — distances, costs — make a weighted graph, with a weight function \(w: E \to \R\) (p. 233).

Walk on the left graph of Fig. 1. A path is "a sequence of vertices such that there is an edge from each vertex to its successor", and it is simple "if each vertex is distinct" (p. 229). The slide's example is [1, 2, 4, 5]: 5 is reachable from 1. A path that comes back to its start is a cycle (p. 230): the two arrows between 4 and 5 form one, and so does 1 → 2 → 4 → 1. On the right graph, the degree of a node is the "Number of edges incident on a node" (p. 240); with arrows it splits into in-degree and out-degree, and "Degree = indegree + outdegree" (p. 241): "The in degree of 2 is 2 and the out degree of 2 is 3."

Two definitions are easy to blur. A graph is connected if "any two nodes are connected by a path"; a directed graph is strongly connected if "there is a directed path from any node to any other node" (p. 231) — a path, not a direct edge. And a graph is sparse if \(|E| \approx |V|\), dense if \(|E| \approx |V|^2\) (p. 232). A social network is sparse: fifty friends each, among a million people.

One family deserves a closer look, because its slide has a slip. A complete graph \(K_n\) is one in which "Every pair of vertices are adjacent" (p. 236).

Last, the slides store the graph as a data structure, four ways (pp. 245–247): an incidence matrix (edges × vertices), an adjacency matrix (\(|V| \times |V|\), \(a_{ij} = 1\) "if \((i, j) \in E\) and 0 otherwise"), an edge list ("pairs (ordered if directed) of vertices", "Optionally weight and other data") and an adjacency list, every node with the list of its neighbours.

Hold on to that difference. An edge list is a relational table Edge(from, to): finding a node's neighbours means searching it. An adjacency list on disk, every node carrying its own connections, is what the next slides call a graph database.

Following a relationship: a search or a step

After the provocation of the hook (p. 251), part 2 defines its subject (p. 252): a graph database is a "Database that uses graph structures with nodes, edges and properties to store data"; it "Provides index-free adjacency"; its "Edges hold most of the important information".

Index-free adjacency is the technical core. The slide glosses it as "Every node is a pointer to its adjacent element"; read it as: every node stores direct references to its own relationships, and through them to its neighbours. Moving to a neighbour follows a reference — no search, so the cost does not depend on how many other nodes the database holds. In a relational database the same move is a join: the row's key is looked up in an index over the whole table, a search whose cost grows with the table (about \(\log_2\) of its rows), repeated for every row at every hop.

The slide on indexes (p. 272) draws the contrast with two captions. Relational: "Use index scans to look up rows in tables and join them with rows from other tables". Graph: "Use indexes to find the starting points for a query". The widget turns them into numbers.

The model isolates the two effects behind the hook's gap: the join plan carries every repeat of its rows and pays a whole-table search for each; the traversal pays only for the neighbourhood it explores. The measured times have the same shape: close at two hops, far apart from three on.

The slide's list of advantages (p. 253) follows from the same mechanism. "When there are relationships that you want to analyze, Graph databases become a very nice fit because of the data structure"; they "are very fast for associative data sets — Like social networks"; and they "Map more directly to object oriented applications — Object classification and Parent->Child relationships": objects that reference each other already form a graph, with nothing to flatten into junction tables.

Index-free adjacency: each node stores its own relationships, so a hop is a step and not a search; the index is used once, to find where to start.

"Foreign Keys? No thanks": from tables to a property graph

The deck makes the argument on one example, the Sailors database (p. 254): Sailor(sid, sname, rating, age), Boat(bid, bname, color) and Reserve(sid, bid, day), with the keys underlined — all three columns for Reserve. Reserve is a junction table, the relational way to store a many-to-many relationship: two foreign keys plus the relationship's own attribute, day.

Page 255 redraws the tables as a generic graph, every table, row, attribute and value an oval: possible, and unreadable. Page 256 gives the "Actual Graph Model" in one line, (:Sailor) –[:reserves]-> (:Boat), and page 257 the reason, "Foreign Keys? No thanks": the reservation links directly to its sailor and its boat, so its copies of sid = 22 and bid = 101 are crossed out and only day stays. In the property graph the reservation is a relationship, and the day its property.

That is the property graph, Neo4j's model. The slide gives it in three bullets — "Nodes – with labels (type) and attributes", "Edges", "Indexes" (p. 266) — and Neo4j's documentation (background) completes it:

• a node has zero or more labels, its types (:Sailor; p. 269 creates one node with two, :Actor:Director), and properties, key-value pairs;
• a relationship — the slides' edge — has exactly one type (:RESERVES), a direction from a start node to an end node, and properties of its own;
• property values are typed: String, Integer, Float, Boolean, Date and the other temporal types, and lists of these.

At the exam the model is written in the notation of p. 256. The paper of 30 Jan 2026 asks for "a written textual representation (no graphical sketches) of the graph model, using the typical Neo4J notation for nodes ( ), edges -[ ]->, and attributes { }. Include data types for attributes." For the Sailors:

// the Sailors of p. 254 as a graph model
(:Sailor {sid: Integer, sname: String,
          rating: Integer, age: Float})
(:Boat {bid: Integer, bname: String, color: String})
(:Sailor)-[:RESERVES {day: Date}]->(:Boat)

Labels in CamelCase, types in capitals, no keys copied onto the edge: "N:N relationship do not need any special treatment" (p. 1385). The full recipe — ISA hierarchies, the past papers — is lesson 12.

A query on such a graph is a shape. "Query: Graph matching approach" (p. 258) draws a small shape found three times inside a large blob of "Facts": you describe a pattern — a sailor, a RESERVES arrow, a red boat — and the database returns every place where it occurs; in Fig. 3, twice. And the graph needs no schema migration: a book that gains a second author gets one more edge ("Easy to Extend", p. 259), and a stored value can be replaced by a node computed from other measurements ("Easy to Change", p. 260).

The same facts as RDF triples

The exam guideline lists, under "Features of Graph DB", two models: "Property graphs (neo4j)" and "Direct labelled graphs (RDF)" — "direct" meaning directed. The slides never name RDF, but they draw it: pages 255 and 257, with every attribute an oval at the end of an arrow, are in the RDF style. What follows on RDF itself is background from the W3C's RDF 1.1 Primer.

In RDF (Resource Description Framework) everything is a triple: "A statement always has the following structure: <subject> <predicate> <object>". Subjects and predicates are IRIs — web identifiers such as http://example.org/sailing#s22, abbreviated :s22 — and an object is an IRI or a literal value. An RDF graph is a set of triples; drawn as arrows from subject to object, labelled with their predicates, they form a directed labelled graph. An attribute is just an arrow that ends in a literal, :s22 :sname "dustin", and a label becomes the triple :s22 rdf:type :Sailor.

The difference shows on the relationship. In the property graph the reservation is one relationship with a property. A triple has three places and no fourth, so to record the day RDF turns the reservation into a resource — reification — with a triple to the sailor, one to the boat and one for the day.

RDF is queried with SPARQL, the W3C's language, whose patterns are triples with variables. One question in three models — the names of the sailors who reserved a red boat. SQL needs two joins:

-- SQL over the tables of p. 254: two joins
SELECT DISTINCT S.sname
FROM Sailor S
JOIN Reserve R ON R.sid = S.sid
JOIN Boat B ON B.bid = R.bid
WHERE B.color = 'red';

In Cypher, Neo4j's query language, the two joins become one arrow — the lesson's only query, a taste of lesson 11:

// returns dustin and rusty (Fig. 3)
MATCH (s:Sailor)-[:RESERVES]->(b:Boat {color: 'red'})
RETURN DISTINCT s.sname

In SPARQL the same pattern is written as triples, one per arrow (here over the triples without the day):

# one triple pattern per arrow
PREFIX : <http://example.org/sailing#>
SELECT DISTINCT ?name
WHERE {
  ?s a :Sailor ;
     :sname ?name ;
     :reserves ?b .
  ?b :color "red" .
}

Neo4j, as the slides present it

Part 3 introduces the product (p. 262): "Developed by Neo Technologies • Most Popular Graph Database • Implemented in Java • Open Source". Its "Salient features" (p. 263): "Neo4j is schema free – Data does not have to adhere to any convention"; "ACID – atomic, consistent, isolated and durable for logical units of work"; easy to use, well documented, and "Support for wide variety of languages — Java, Python, Perl, Scala, Cypher, etc" (Cypher is the query language, the others client languages).

Read the bottom layer with index-free adjacency in mind. Nodes and relationships live in separate record files; in the book Graph Databases (ch. 6, background) a node record points to its first relationship, and each relationship record to the previous and next relationships of both its nodes — the references a traversal follows. The transaction log lets committed work survive a crash: the D of ACID.

"Purpose" (p. 265) is the most quotable slide of part 3: "Meant to be an operational DB, not specifically for analytics • ACID • Efficient on nodes • Not so efficient in whole-graph analysis". Neo4j serves an application with many small transactions that start at a node — who are my friends, add this reservation — cheap thanks to index-free adjacency; ranking every page of the web gains nothing from local pointers. ACID matters in a graph because creating a relationship touches two nodes: only a transaction keeps an edge from pointing at a node that is gone. The course notes add a "traditional CA architecture" (lesson 5); the slides do not.

Cypher, the slide says (p. 267), is a "Declarative language", "Easy to formulate queries based on relationships", whose features "stem from improving on pain points with SQL such as join tables": you state the pattern, Neo4j chooses the traversal. Then data comes in. CREATE makes nodes, with several labels if needed — Create (n:Actor:Director {name:'Clint Eastwood'}) (p. 269); LOAD CSV WITH HEADERS ... AS row runs the statement once per line of a file, reading columns as row.Column. Run a CREATE import twice and every node exists twice — hence MERGE, "ID-based" (p. 270):

// p. 270: one Player node per id
LOAD CSV WITH HEADERS FROM "file:///transfers.csv" AS row
MERGE (player:Player {id: row.playerUri})
ON CREATE SET player.name = row.playerName,
              player.position = row.playerPosition

MERGE is match-or-create on the whole pattern, label and properties: a :Player with that id is used if it exists, created otherwise, and ON CREATE SET fills the other properties only when it is created. A player mentioned in many rows still becomes one node. Page 271 then imports the transfers:

// p. 271: a transfer becomes a node
LOAD CSV WITH HEADERS FROM "file:///transfers.csv" AS row
MATCH (player:Player {id: row.playerUri})
MATCH (source:Club {id: row.sellerClubUri})
MATCH (destination:Club {id: row.buyerClubUri})
MERGE (t:Transfer {id: row.transferUri})
ON CREATE SET t.season = row.season, t.rank = row.transferRank,
              t.fee = row.transferFee
MERGE (t)-[:OF_PLAYER { age: row.playerAge }]->(player)
MERGE (t)-[:FROM_CLUB]->(source)
MERGE (t)-[:TO_CLUB]->(destination)

A transfer links three things — a player, a selling club, a buying club — and a relationship joins exactly two nodes, so the transfer becomes a node with three typed relationships: the hyperedge of p. 239, whose "edges can connect any number of vertices", turned into a node. The player's age at the time is a property of OF_PLAYER, the "important information" an edge holds.

Two schema statements follow. An index is "For performance purpose" and "Only for access to initial node of the query" (p. 272): it finds the anchor, say customer 42; later hops follow relationships. A uniqueness constraint (p. 273) forbids two :Customer nodes with the same customerID — the graph's primary key, which keeps a MERGE by id honest. Schema free means nothing has to be declared, not that nothing can be. The slides print Neo4j 3 syntax, which Neo4j 5 rejects; today you write FOR … ON and FOR … REQUIRE, with an optional name:

CREATE INDEX ON
:Customer(customerID);

CREATE CONSTRAINT ON (c:Customer)
ASSERT c.customerID IS UNIQUE;

CREATE INDEX customer_id
FOR (c:Customer) ON (c.customerID)

CREATE CONSTRAINT customer_key
FOR (c:Customer)
REQUIRE c.customerID IS UNIQUE

The next pages show the query language itself. You learn to write it in lesson 11 and lesson 12; here is what the slides print, for a closed question that quotes them.

Four "Hints" (p. 282) close the Cypher part, each with its reason: "Use parameters instead of literals" — with $name in place of 'dustin' the query text stays the same and Cypher re-uses its plan; "Always set an upper limit for your variable length patterns" — every hop multiplies the paths, and "It's easy to have a query touch all nodes in a graph by mistake"; "Return only the data you need"; "Use PROFILE / EXPLAIN". "Stored Procedures" (p. 279) are Java functions: "Simply move your JAR to a folder!", then call them from Cypher — which is also how libraries of whole-graph algorithms are plugged in (background).

When a graph wins — the puzzle resolved

The uses follow from "Efficient on nodes": questions that start somewhere and walk. Social networks, the slide's example (p. 253): in 2016 Facebook found its 1.59 billion users on average 3.57 intermediaries apart — four or five friendships, the depths where the joins of the hook crawled or never finished. Recommendation: people you may know are friends of friends who are not yet friends. Fraud: a ring of fake identities sharing one phone number and one address is a few hops in a graph and a chain of self-joins in SQL. Routing: "Shortest route between two cities" (p. 223) on a weighted graph — on p. 233 the direct edge from 2 to 5 costs 5, the detour through 1 costs 2 + 1 = 3. Investigation: journalists explored the Panama Papers as a Neo4j graph of about 950,000 nodes and 1.2 million relationships.

Now the puzzle. At four friendships the relational query is a chain of four self-joins: for every row produced so far, an index over some fifty million friendship rows is searched, and those rows include every repeat, because friends share friends. Neo4j searches an index once, to find the starting person, then follows the relationships stored with each person it reaches — work proportional to the neighbourhood, not to the database. At two friendships there is little to gain (0.016 s against 0.010 s); each further hop multiplies the relational work. The gap closes when the question stops being local: for every node at once, pointers offer no shortcut — "Not so efficient in whole-graph analysis" (p. 265). The slide's "(incredibly!)" holds for relationships followed many hops deep; joined one level at a time, they are the relational database's daily work.