Graph Data Models

A graph data model represents information as a set of nodes (also called vertices, representing entities) connected by edges (also called relationships, representing associations between entities). Unlike a relational table, where a relationship between two rows must be reconstructed at query time by matching a foreign key against a primary key index, a graph database stores the relationship itself as a physical structure. Each node maintains a list of the edges incident to it, so that from any node, all of its neighbors are reachable by following stored references rather than by searching an index. The property graph model extends this basic node/edge structure by allowing both nodes and edges to carry arbitrary key-value properties, and by allowing nodes to carry one or more labels (types, such as `Person` or `Product`) and edges to carry a relationship type (such as `FOLLOWS` or `PURCHASED`) plus a direction. This makes the property graph expressive enough to model rich, schema-flexible domains directly: a `Person` node might have properties `{name: "Ava", age: 29}`, connected by a `FOLLOWS` edge (itself carrying a property `since: 2021`) to another `Person` node. Property graphs are queried with declarative pattern-matching languages — Cypher (Neo4j, openCypher, and the emerging ISO GQL standard), or Gremlin, a graph traversal language usable across many backends via Apache TinkerPop. The RDF (Resource Description Framework) triple model, standardized by the W3C, takes a more atomic approach: every fact is a triple of the form `(subject, predicate, object)`, e.g., `(:Ava, :follows, :Ben)`. There is no separate notion of node properties versus edges — everything, including what a property graph would call a node attribute, is itself expressed as a triple, e.g., `(:Ava, :age, "29")`. Collections of triples form a directed labeled graph, queried with SPARQL. RDF's uniformity makes it well-suited to knowledge graphs that must merge data from many independent sources under a shared vocabulary (an ontology), and it supports formal inference (deriving new triples from schema rules), which property graphs generally do not natively provide. The tradeoff is verbosity: what a property graph expresses as one node with five properties, RDF expresses as five separate triples.

The mechanism that makes graph databases efficient is called index-free adjacency. In a relational database, finding "all edges from node A" means querying an index (e.g., a B-tree on a foreign key column) — a cost that grows with the logarithm of the table size, `O(log n)`, per lookup, and this cost is paid again for every hop and every intermediate row. In a native graph engine, each node stores a physical list (or pointer) directly to its adjacent edges, and each edge stores direct references to its two endpoint nodes. Traversing from a node to its neighbors means dereferencing these stored pointers — an operation whose cost is proportional only to the node's degree (number of incident edges), not to the total size of the database.

Physical layout (typical native graph store). Nodes and relationships are usually stored in fixed-size records in separate files. A node record holds: a pointer to its label(s), a pointer to its property list, and a pointer to the first relationship record in its adjacency chain. Each relationship record stores: its type, its two endpoint node IDs, a pointer to its own properties, and four "next" pointers — the next relationship in the chain for its start node (incoming and outgoing) and the next relationship in the chain for its end node. This turns each node's adjacency list into a doubly-linked list of relationship records, threaded through the relationship store, so walking from a node to all its neighbors is a pointer-chase, not a search.

Query execution — pattern matching. A Cypher query such as: ``` MATCH (a:Person {name: "Ava"})-[:FOLLOWS]->(b:Person)-[:LIKES]->(g:Genre {name: "Jazz"}) RETURN b.name ``` is executed by the query planner as a sequence of expansions: start at the node(s) matching the anchor pattern (`a:Person {name:"Ava"}`, found via a label+property index in `O(log n)` or `O(1)` with a hash index), then expand along `FOLLOWS` edges to reach candidate `b` nodes (cost proportional to `a`'s out-degree), then expand again along `LIKES` edges from each `b` to check for a `Genre` node named "Jazz" (cost proportional to each `b`'s out-degree). No relational-style join over the entire relationship table ever occurs; the traversal only ever touches nodes and edges actually reachable from the anchor.

Pseudocode: pattern-matching traversal engine

``` function MATCH_PATTERN(graph, pattern):

# pattern = sequence of (nodeConstraint, edgeType, direction) steps

# e.g. [(Person,name=Ava), (FOLLOWS,OUT), (Person,*), (LIKES,OUT), (Genre,name=Jazz)] anchors = INDEX_LOOKUP(graph, pattern.step[0]) # O(log n) or O(1) results = [] for start_node in anchors: EXPAND(start_node, pattern, step_index = 1, bindings = {0: start_node}, results) return results

function EXPAND(current_node, pattern, step_index, bindings, results): if step_index >= length(pattern): results.append(bindings) # full match found return (edgeType, direction) = pattern.step[step_index] (nextConstraint) = pattern.step[step_index + 1]

# index-free adjacency: walk the relationship chain stored on current_node for rel in ADJACENCY_LIST(current_node, edgeType, direction): # cost = degree neighbor = OTHER_ENDPOINT(rel, current_node) if SATISFIES(neighbor, nextConstraint): new_bindings = bindings.copy() new_bindings[step_index + 1] = neighbor EXPAND(neighbor, pattern, step_index + 2, new_bindings, results)

function ADJACENCY_LIST(node, edgeType, direction):

# native graph storage: follow the linked chain of relationship records rel = node.first_relationship_pointer[direction] chain = [] while rel is not NULL: if rel.type == edgeType: chain.append(rel) rel = rel.next_pointer_for(node, direction) # O(1) pointer dereference return chain ``` The key structural fact embedded in `ADJACENCY_LIST`: each iteration is a single pointer dereference (`O(1)`), and the loop runs once per relationship actually attached to `node` — never once per row in some global relationship table.

RDF triples for the same data. The identical facts, expressed as a triple store, look like: ``` :Ava :follows :Ben . :Ava :follows :Cleo . :Ben :likes :Jazz . :Cleo :likes :Jazz . ``` A SPARQL query mirroring the Cypher pattern above: ``` SELECT ?name WHERE { :Ava :follows ?person . ?person :likes :Jazz . ?person :name ?name . } ``` SPARQL execution conceptually joins triple patterns using a triple index (most RDF stores maintain six permutations of subject/predicate/object indexes — SPO, SOP, PSO, POS, OSP, OPS — so any triple pattern with any combination of bound/unbound positions can be answered by a direct index range scan). This is not literally pointer-chasing like a native property graph, but it achieves similarly fast lookups because every access pattern has a dedicated sorted index, avoiding full-table scans.

Single-hop traversal. Given a node with degree `d` (number of incident edges), retrieving all neighbors via index-free adjacency costs `O(d)` — each relationship record is visited exactly once via a direct pointer, with no search structure involved. This is optimal: any correct traversal must at minimum examine each of the `d` edges once, so `O(d)` is a tight lower bound as well as the achieved upper bound.

k-hop pattern query. For a path pattern of length `k` (as in the `MATCH_PATTERN` pseudocode), the worst-case cost is: ``` O( |anchors| · d_avg^k ) ``` where `d_avg` is the average out-degree along the matched edge types. This is exponential in `k` in the worst case — a graph engine does not magically avoid combinatorial explosion — but crucially the base `d_avg` is the local branching factor of the graph, not the total database size `n`. Compare this to a relational equivalent: joining `k` tables for a `k`-hop path, using hash joins, costs roughly `O(k · n)` in the worst case if the join must materialize intermediate results proportional to full table sizes, and query planners commonly cannot avoid scanning entire join tables when foreign-key selectivity is not precisely known. In practice, for sparse, highly selective patterns (an anchor with a specific name, a bounded number of hops, moderate average degree), the graph traversal's `d_avg^k` term is small and the query finishes in time proportional to the answer size, not the database size — this is the core practical efficiency claim, sometimes called the graph database's answer being index-free and instance-proportional rather than schema-proportional.

Anchor lookup. Finding the starting node(s) for a pattern (e.g., `Person {name: "Ava"}`) uses a conventional index — a B-tree gives `O(log n)`, a hash index gives expected `O(1)`. This part of the cost is identical in spirit to relational indexing and is not a graph-specific innovation; the innovation is entirely in what happens after the anchor is found.

Space complexity. A property graph with `V` nodes and `E` edges requires `O(V + E)` space for structure, plus space proportional to the total size of all stored properties. The relationship-chain design roughly doubles per-edge storage overhead compared to a bare adjacency list (each relationship record stores four "next" pointers instead of one), trading space for the guarantee of `O(1)`-per-step traversal in either direction from either endpoint.

Correctness argument (pattern matching). The `MATCH_PATTERN`/`EXPAND` algorithm is a depth-first search over the space of partial variable bindings, and its correctness rests on two invariants maintained by induction on `step_index`: 1. Soundness invariant — every binding produced by `EXPAND` at depth `step_index` satisfies all pattern constraints (labels, edge types, directions, properties) for steps `0..step_index`. This holds because each recursive call only extends `bindings` after `SATISFIES(neighbor, nextConstraint)` has been checked, and the base structural constraints (edge type, direction) are enforced by `ADJACENCY_LIST` filtering before `neighbor` is even considered. 2. Completeness invariant — every valid full match in the graph is discovered. This holds because `ADJACENCY_LIST` enumerates all relationships of the required type/direction incident to the current node (the chain traversal does not stop early), so no candidate neighbor satisfying the next constraint is ever skipped; by induction, if a valid partial match of length `step_index` exists, `EXPAND` will be called on it (from the corresponding invocation at `step_index - 1`, by the completeness of that shallower level), and it will correctly extend it whenever a satisfying neighbor exists. Together these establish that the algorithm returns exactly the set of bindings satisfying the full pattern — no false positives (soundness), no missed matches (completeness). Termination follows because `step_index` strictly increases on each recursive call and the pattern length is finite, and because real graphs have finite degree, so `ADJACENCY_LIST` always terminates.

Honest tradeoffs. Graph engines are not uniformly superior. For aggregate analytics over large, non-recursive scans ("average order value across all transactions last quarter"), columnar and relational engines with vectorized execution and compression outperform graph traversal engines, which are optimized for deep, narrow, relationship-following access patterns rather than wide, flat scans. Graph databases also historically lag in horizontal write-scalability, because maintaining globally consistent adjacency pointers across a sharded, distributed cluster is harder than sharding rows independently — many native graph systems favor single-machine or master-replica architectures, or accept eventual consistency for sharded deployments. Finally, schema flexibility in property graphs is a double-edged sword: the absence of a rigid schema (similar to the tradeoff discussed in the NoSQL Data Models Overview) means data quality and consistency checks must often be enforced at the application layer.

Consider a small fraud-detection graph: five `Account` nodes and `TRANSFER` edges (with a `amount` property), where we want all accounts that received money, directly or through one intermediary, from a flagged account `A1`.

Graph data:

Query (Cypher-style): ``` MATCH (a:Account {id:"A1"})-[:TRANSFER]->(b:Account)-[:TRANSFER*0..1]->(c:Account) RETURN DISTINCT c.id ``` (This asks for all accounts reachable from `A1` in one or two hops.)

Trace through `MATCH_PATTERN` / `EXPAND`:

Final `DISTINCT` result: `{A2, A4, A3, A5}` — every account except `A1` itself.

Cost accounting: the anchor lookup was one index hit; the traversal touched exactly `deg(A1) + deg(A2) + deg(A3) = 2 + 1 + 2 = 5` relationship records — not the full edge set of 6, and critically not proportional to however many total accounts and transfers exist in a bank with millions of customers. A relational equivalent would require a self-join of the `transfers` table up to two levels deep, filtered by `from = 'A1'`, and — absent very selective indexing and an optimizer smart enough to push the filter before the join — could scan large fractions of the transfers table at each join level.

Contrast case — dense hub node. Now suppose `A1` is a payment-processor hub with degree 500,000 (a common real-world pattern: a small number of "super-node" accounts with enormous fan-out). The same two-hop query now costs at least `O(500,000)` just to enumerate `A1`'s direct neighbors, before even considering their neighbors. This demonstrates the honest limit of the complexity claim: index-free adjacency guarantees cost proportional to actual degree, and when degree is large, "constant per hop" does not mean "fast in absolute terms." Real graph engines mitigate this with degree-aware query planning (choosing to expand from the lower-degree side of a pattern first) and with specialized indexes on relationship properties to prune early.

:::warning[Unbounded variable-length path queries are the single most dangerous mistake: a query like `MATCH (a)-[*]->(b)` with no hop limit can silently attempt to enumerate an exponential number of paths on a graph with cycles or high-degree hubs, turning a millisecond query into a resource-exhausting outage — always bound the traversal depth explicitly.]

The graph data model's theoretical roots lie in graph theory itself, but its productization as a database model emerged from two separate lineages: the semantic web's triple-based knowledge representation, and industrial property-graph engines built for operational, transactional graph workloads.

Graph data models power systems wherever relationships, not just entities, are the object of interest. Social networks use property graphs for friend/follow relationships and feed-ranking traversals. Fraud detection systems at banks and payment processors (a direct generalization of the worked example above) use graph traversal to find rings of accounts transferring money in suspicious cycles — a pattern that is a natural graph query but an awkward, expensive relational join. Recommendation engines traverse "customers who bought X also bought Y" graphs, and knowledge graphs — Google's Knowledge Graph, Wikidata, enterprise semantic layers — use RDF triples to unify facts from disparate sources under a shared ontology, enabling question-answering and inference. Network and IT infrastructure management models servers, dependencies, and configurations as a graph to answer "what will break if this service goes down" queries via traversal. Identity and access management systems model permission inheritance (users, roles, groups, resources) as a graph so that "can user U access resource R" becomes a reachability query. As data platforms increasingly combine specialized engines — a graph store for traversal, a columnar warehouse for aggregation, a document store for semi-structured records — graph databases take their place as one tool among several in the broader Big Data Systems Landscape, each engine chosen for the access pattern it serves best.

Ask the tutor: How would you redesign a graph schema to avoid the super-node traversal bottleneck in a fraud-detection system?