Skip to content
Jamie Little
Part IA Michaelmas Term

Storing Graphs in Relational Tables

The one-big-graph approach

A simple approach to storing a graph in relational tables uses two tables:

NODES(Town, Country) — one row per node, with type-specific attributes.

EDGES(EID, V1, V2, Form, Distance) — one row per edge, where V1 and V2 reference nodes.

This is a unary relation (endorelation): the schema range and domain type are both towns. Edges go from one town to another, so both ends draw from the same domain.

Inefficiency of the flat edges table

To find the neighbours of a given node using the EDGES table requires a full table scan:

SELECT V2 FROM EDGES WHERE V1 = 'Cambridge';

For undirected searches, both columns must be examined:

SELECT V1 AS neighbour FROM EDGES WHERE V2 = 'Cambridge'
UNION
SELECT V2 AS neighbour FROM EDGES WHERE V1 = 'Cambridge';

This is linear in the number of edges. To avoid scanning, two inverted indexes are needed: one on V1 and one on V2. These indexes let the DBMS look up edges by either endpoint efficiently, but they double the storage overhead for the edges table.

Multi-hop queries in SQL

Queries involving many hops are painful to express in SQL. Finding all towns reachable from a starting town (the transitive closure, or Kleene star from the Algorithms course) requires recursive Common Table Expressions (CTEs):

WITH RECURSIVE Reachable AS (
  SELECT V2 AS town FROM EDGES WHERE V1 = 'Cambridge'
  UNION
  SELECT E.V2 FROM EDGES E
  JOIN Reachable R ON E.V1 = R.town
)
SELECT * FROM Reachable;

Each recursive step scans more rows. The query cost grows with the diameter of the graph. For graphs with millions of nodes and long paths, this becomes impractical. Graph databases optimise path traversal internally, but relational systems with recursive CTEs can still be competitive on moderate-sized graphs.

Bipartite approach: separate node tables

When the graph is bipartite (edges go between different types), separate node tables are cleaner:

TOWNS(Town, Population) LANGUAGES(Language, Core_Vocab, Genders) OFFICIAL_LANGUAGE(Town, Language)

The OFFICIAL_LANGUAGE relation is bipartite: each edge goes from a town to a language. This is identical to the relational representation of a many-to-many relationship covered in the E/R-to-relational mapping notes. The graph model adds nothing that cannot be done in relations.

RDBMS limitations for enormous relations

For enormous, many-to-many relations, RDBMSs are not ideal if the primary workload is graph traversal. A join between two large tables to find connected nodes incurs index lookups, and for path-finding queries the relational engine must iterate. Graph databases can store adjacency information more compactly and traverse it more directly.

For OLAP (analytical) workloads, a denormalised representation would probably be used instead — pre-joining the data into a wide table or a star schema, trading storage space for query speed.

Ternary relations

Modelling ternary relations is awkward in a graph, because edges have exactly two ends. Two approaches exist:

ApproachDescriptionDrawback
Edge attributesStore the third entity’s attributes as properties on the edgeLoses identity of the third entity; cannot easily join to it
ReificationTurn the ternary relationship into a node, with three edges connecting to the participantsBlurs the distinction between entities and relationships; more complex queries

For example, a ternary relationship TEACHES(Lecturer, Course, Term) could be modelled as a node of type TeachingEvent with edges to Lecturer, Course, and Term. This is sometimes called reification — treating a relationship as an entity in its own right.

Summary

  • Storing graphs in relational tables is straightforward but inefficient for multi-hop traversal without indexes.
  • Two inverted indexes on the source and target columns avoid full scans for neighbour lookups.
  • Recursive CTEs can express transitive closure, but the cost grows with graph diameter.
  • Bipartite graphs map cleanly to standard relational many-to-many representations.
  • Ternary relations are awkward in the graph model; reification (making the relationship a node) is the usual workaround.
Back to Databases