Why Every Relational Database is a Graph: Rows are Nodes, Foreign Keys are Edges

Every relational database is a graph. This is not an analogy. It is a direct mathematical mapping. Take any relational database schema with tables and foreign key constraints. Each table defines a node type. Each row in a table is a node of that type. Each foreign key relationship between two tables defines an edge type. Each row referencing another row via a foreign key creates an edge between the two corresponding nodes.

The resulting graph is heterogeneous (multiple node types, multiple edge types) and carries rich features (column values on each node). This graph already exists implicitly in every SQL database. Making it explicit unlocks graph neural network-based learning.

The mapping in detail

-- Relational database schema
CREATE TABLE customers (
    customer_id INT PRIMARY KEY,
    name VARCHAR, age INT, city VARCHAR
);

CREATE TABLE orders (
    order_id INT PRIMARY KEY,
    customer_id INT REFERENCES customers(customer_id),
    amount DECIMAL, order_date DATE
);

CREATE TABLE products (
    product_id INT PRIMARY KEY,
    name VARCHAR, price DECIMAL, category VARCHAR
);

CREATE TABLE order_items (
    order_id INT REFERENCES orders(order_id),
    product_id INT REFERENCES products(product_id),
    quantity INT
);

-- Graph interpretation:
-- Node types: customer, order, product, order_item
-- Edge types: customer -[places]-> order
--             order -[contains]-> order_item
--             order_item -[of_product]-> product
-- Node features: column values of each row

Tables become node types

Each table in the schema corresponds to a node type in the graph. The customers table produces customer nodes. The orders table produces order nodes. The products table produces product nodes. Each node type has its own set of features (the table's columns).

Rows become nodes

Each row in a table becomes a specific node. Customer Alice (row 1 in customers) becomes node Alice with features {name: “Alice”, age: 32, city: “NYC”}. Order #1001 becomes node 1001 with features {amount: 67.50, date: “2024-01-15”}.

Foreign keys become edges

Each foreign key relationship creates edges between nodes. If order #1001 has customer_id = 1 (Alice), there is an edge from Alice to order #1001 of type “places.” If order_item row references order #1001 and product #55, there are edges connecting these three nodes.

Many-to-many relationships

Many-to-many relationships use junction tables. Students enroll in courses through a student_courses table with student_id and course_id foreign keys. Two graph representations are possible:

• Junction node: the enrollment becomes a node with edges to both student and course. Use this when the junction carries features (enrollment date, grade, status).
• Direct edge: skip the junction and create a direct student-enrolled-in-course edge. Use this when the junction is featureless (pure relationship).

What the graph enables that SQL cannot

SQL can express joins and aggregations. But some patterns are natural in graphs and extremely awkward in SQL:

• Multi-hop path queries: “Find customers who bought products from the same category as products returned by customers who previously churned.” This is a 4-hop path. In SQL, it requires multiple self-joins and subqueries. In a graph, it is 4 layers of message passing.
• Structural similarity: “Find customers with similar purchasing patterns.” In the graph, customers with similar neighborhoods (same products, same categories) will have similar GNN embeddings. No manual similarity metric needed.
• Neighborhood aggregation: “Compute a feature for each customer that summarizes their orders, their products, and the behavior of other customers who bought those products.” This is one GNN forward pass. In SQL, it is a complex chain of GROUP BY operations.

Scale considerations

Enterprise databases are large: millions of rows become millions of nodes. The graph representation does not require materializing the full adjacency matrix. PyG uses sparse edge index representations (two arrays of source and target node IDs) that scale linearly with the number of foreign key references, not quadratically with the number of rows.

For very large databases, graph mini-batching and graph partitioning enable training on subgraphs without loading the entire database into memory.