Graph Database Concepts

A property graph stores nodes (records with a label and properties) and edges (a relationship type, direction, and properties). With index-free adjacency, the node record points at its incident edges. The first hop does not scan an edges table for from_id—it follows those pointers.

A query is a traversal: start set → expand → filter → expand. Memory and CPU track the frontier, not the number of pattern letters in Cypher. A supernode on the path multiplies work. Sharding introduces hop locality: the pointer may be an RPC.

RDF stores triples and answers SPARQL with covering triple indexes. graph compute runs global algorithms in supersteps. Mixing those with a latency-sensitive neighborhood API on one unplanned store is how graph projects stall.

Relational edge table hop:
  SELECT to_id FROM edges
   WHERE from_id = $id AND type = 'FOLLOWS'
  → B-tree lookup on (from_id, type)
  Fine for low degree; still an index probe per node in the frontier

Index-free adjacency hop:
  node_record.out_edges['FOLLOWS'] → linked records / packed neighbor ids
  → sequential walk of that node's typed list
  Constant factors win when you chain many hops on modest degrees

Both still pay O(degree). Neither makes hop-3 at degree 1e4 cheap.

Packed neighbor arrays (CSR-style, common in analytics graphs) are excellent for scans and terrible for high-churn OLTP edge inserts unless you leave slack or accept rewrites. Pointer-rich object graphs are the opposite: easy local mutation, worse cache behavior for bulk algorithms. Engines pick a side; you should know which you bought.

Properties on edges need a place to live. Fat edge payloads turn a neighborhood walk into a wide-row read. Keep traversal filters on cheap typed edges; store bulky payloads on nodes or in a side KV store keyed by edge id.

A supernode is a modeling problem first. If everyone connects to (:Country {name: US}), you built a star. Split edges by type and time: LIVES_IN_2026, or store the country as a property on the person instead of a hub node when you never traverse through it.

When the supernode is inherent (a celebrity, a popular listing), the engine must not expand all edges in one operator. Techniques: relationship grouping (edges sharded by type and by neighbor id range), approximate sampling for recommendations, precomputed neighborhoods for the hot vertex, and query planners that rewrite MATCH (c)-[]-(n) away from starting at c.

Online traversals have a start vertex, a small depth, and a latency SLO. graph compute has “all vertices,” iterative supersteps, and checkpointed shuffle. PageRank, community detection, and embedding pipelines belong on the compute side; they should write derived properties or tables that the OLTP graph or a KV cache can serve.

Pattern matching (Cypher, Gremlin) sits in between: a selective pattern can be OLTP; a poorly filtered pattern is an unbounded compute job accidentally issued by a product API. Treat query budgets like SQL timeouts, and log expansion counts the way you log rows scanned.

OLTP:
  MATCH (p:Person {id:$id})-[:FOLLOWS]->(f)
        -[:FOLLOWS]->(fof)
  WHERE f.active AND fof.active
  RETURN fof.id LIMIT 50
  Budget: tens of ms, start indexed, types specified

Compute:
  foreach vertex: send rank/degree to neighbors
  iterate until delta < eps
  write pagerank property to serving store

Do not:
  MATCH (n)-[*]-(m) RETURN m
  on the production cluster at noon

Strong fits: authorization graphs, fraud rings, network topology, knowledge graphs with bounded hops, recommendations that are actually path queries. Weak fits: tabular reporting, append-only telemetry, documents that are trees but are always fetched by primary key (a document store already nests trees).

You can implement a graph on relational tables with recursive CTEs or on a KV store with adjacency lists. That is valid when hop depth is 1–2 and degree is modest. Switch when the hop depth and mixed relationship types make adjacency a first-class layout, or when the query language’s pattern matcher is the product.

RDF is a better fit when identity is a URI, predicates are shared vocabularies, and inference matters. Property graphs are a better fit when developers think in labeled nodes and typed edges with ad hoc properties. Translating between them is a project.