I want to store undirected graph edges (for example, for friends). To store and retrieve all friends of node a
, one can use:
Create two rows per edge, query on one column per node:
+--------------------------+
| id | from_node | to_node |
+--------------------------+
| 1 | a | b |
| 2 | b | a |
+--------------------------+
SELECT * FROM `x` WHERE from_node = a
Create one row per edge, use OR
:
+--------------------------+
| id | node_a | node_b |
+--------------------------+
| 1 | a | b |
+--------------------------+
SELECT * FROM `y` WHERE node_a = a OR node_b = a
Which makes for more efficient lookups?
x
with 2n
rows, indices on from_node
and to_node
, lookup on one columny
with n
rows, indices on node_a
and node_b
, lookup on both columns using OR
This is likely to be far too out of date to be useful, but I'll post incase it helps other people!
I store undirected graphs like your second example and have a constraint that node_a has to be less than node_b. You then trivially place a UNIQUE
constraint on the pair and know that the data is consistent. Queries have to a bit more work by compare node_a to the smaller of {a,b} and node_b the other value. PostgreSQL (the DB I know best) provides GREATEST()
and LEAST()
functions that help here.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With