Skip to content
Jamie Little
Part IA Michaelmas Term

Graph DBMS Optimisations and Convergence

Bacon numbers in Cypher

The “Bacon number” problem (degrees of separation from Kevin Bacon) is a classic graph-traversal benchmark. In Cypher:

MATCH paths = allShortestPaths(
  (m:Person {name: 'Kevin Bacon'})-[:ACTED_IN*]-(n:Person)
)
WHERE n.person_id <> m.person_id
RETURN length(paths) / 2 AS bacon_number,
       COUNT(DISTINCT n.person_id) AS total
ORDER BY bacon_number

The allShortestPaths function finds every shortest path between Bacon and each other person. The edge count is divided by 2 because the path alternates between ACTED_IN edges and their inverse (a path from Person to Movie to Person to Movie to Person has 4 edges but represents a Bacon number of 2).

This is dramatically simpler than the equivalent in SQL, which requires a recursive CTE with explicit cycle detection and shortest-distance tracking:

WITH RECURSIVE BaconPath AS (
  SELECT p2.person_id, 1 AS bacon_number
  FROM acted_in a1
  JOIN acted_in a2 ON a1.movie_id = a2.movie_id
  WHERE a1.person_id = (SELECT person_id FROM people WHERE name = 'Kevin Bacon')
    AND a1.person_id <> a2.person_id
  UNION
  SELECT a4.person_id, bp.bacon_number + 1
  FROM BaconPath bp
  JOIN acted_in a3 ON bp.person_id = a3.person_id
  JOIN acted_in a4 ON a3.movie_id = a4.movie_id
  WHERE a3.person_id <> a4.person_id
    AND bp.bacon_number < 10
)
SELECT bacon_number, COUNT(*) AS total
FROM BaconPath
GROUP BY bacon_number
ORDER BY bacon_number;

The SQL version is longer, harder to read, and more prone to naive implementations causing infinite recursion.

In-core optimisations: pointer-based edges

Graph-oriented DBMSs that operate in-core (the entire graph fits in RAM) can use pointers to implement referential links between nodes. Following an edge becomes an O(1) pointer dereference:

Node struct { type, properties, *edge_list }
Edge struct { type, properties, *target_node, *next_edge }

Traversal from a node to its neighbours is a linked-list walk (or array scan, if edges are stored in a contiguous block). In a relational system, the same operation requires an index lookup (B-tree or hash) on a foreign-key column, which is O(log n) or O(1) with hash but involves more indirection and cache-unfriendly access patterns.

This pointer-based storage is the source of the graph database’s traversal-speed advantage. The cost is that pointer-based structures are harder to serialise to disk, harder to distribute across machines, and harder to make durable under crashes.

Big-data implementations: Pregel

For graphs too large to fit in memory, a different approach is needed. The Pregel model (Google, 2010) processes large graphs in a distributed, vertex-centric way:

  1. The graph is partitioned across many machines.
  2. Computation proceeds in supersteps. In each superstep, every vertex:
    • Receives messages sent to it in the previous superstep.
    • Updates its state.
    • Sends messages to other vertices (to be delivered in the next superstep).
  3. The computation ends when all vertices vote to halt and no messages are in flight.

This is a bulk-synchronous parallel (BSP) model. Edges are streamed past processing elements. The system does not need random access to arbitrary parts of the graph — it processes neighbours in batches.

The Pregel model is not unique to graph databases. Apache Giraph, Apache Spark’s GraphX, and other frameworks implement it as a graph processing layer over general-purpose distributed dataflow engines.

Convergence of graph and relational systems

The database landscape is converging rather than diverging. Key developments:

DimensionGraph → RelationalRelational → Graph
StorageGraph databases add columnar storage and compressionRDBMSs optimise in-core table sets (in-memory OLTP)
Query languageCypher is being standardised as GQL (ISO/IEC 39075), complementing SQLSQL:2023 adds property graph queries (SQL/PGQ)
IndexingGraph databases add B-tree and full-text indexes on propertiesRDBMSs add graph-specific indexes and recursive-CTE optimisation
TransactionsNeo4j added ACID transactions early; others followedRDBMSs have had ACID for decades

SQL/PGQ (Property Graph Queries) is part of the SQL:2023 standard. It allows graph-pattern matching within SQL, blurring the line between relational and graph query languages:

SELECT p1.name, p2.name
FROM GRAPH_TABLE (movie_graph
  MATCH (p1 IS Person)-[a IS ACTED_IN]->(m IS Movie)<-[b IS ACTED_IN]-(p2 IS Person)
  COLUMNS (p1.name, p2.name)
);

This is SQL with graph-pattern syntax. The convergence means that choosing a DBMS is less about the data model and more about the workload, the operational maturity, and the tooling ecosystem.

Course summary

The Databases course has covered multiple data models, each with strengths and weaknesses. Several themes recur:

  • Conceptual modelling matters. Having a conceptual model of data (E/R, relations, documents, graphs) is useful regardless of the implementation technology. Investment in data-model planning pays off well — the cost of fixing a bad schema later is high.

  • There is no universal database. No database system satisfies all possible requirements. Workloads differ in read/write ratio, query complexity, latency requirements, data volume, and consistency needs.

  • Staging is common practice. Staging between a principal storage model (used for updates) and optimised views, clones, or other alternatives for rapid querying is widely used. Materialised views, read replicas, and caching layers are standard architectural patterns.

  • Understand the trade-offs. It is best to understand the pros and cons of each approach and develop integrated solutions. A developer who knows only one database model is poorly equipped for real-world engineering.

The current moment

Today we see enormous churn and creative activity in the database field. The rise of AI has introduced vector databases, embedding-based retrieval, and natural-language-to-SQL translation. Graph databases compete with knowledge graphs and RDF triplestores for the same use cases. NewSQL systems claim to combine the scalability of NoSQL with the ACID guarantees of traditional RDBMSs. The field is not settling down — it is accelerating.

Summary

  • The Bacon number query in Cypher is dramatically simpler than the equivalent recursive SQL.
  • In-core graph databases use pointers for O(1) edge traversal; relational systems use indexes.
  • The Pregel model processes large graphs in distributed supersteps with message passing.
  • The industry is converging: SQL:2023 adds graph-pattern queries; graph databases add relational features.
  • Conceptual data modelling is valuable regardless of the implementation.
  • No single database satisfies all requirements; understanding the trade-offs is essential.
Back to Databases