representing graph using relational database

Question

I need to represent graph information with relational database.

Let's say, a is connected to b, c, and d.

a -- b
|_ c
|_ d

I can have a node table for a, b, c, and d, and I can also have a link table (FROM, TO) -> (a,b), (a,c), (a,d). For other implementation there might be a way to store the link info as (a,b,c,d), but the number of elements in the table is variable.

• Q1 : Is there a way to represent variable elements in a table?
• Q2 : Is there any general way to represent the graph structure using relational database?

Answer 1

Q1 : Is there a way to represent variable elements in a [database] table?

I assume you mean something like this?

 from | to_1 | to_2 | to_3 | to_4 | to_5 | etc...
 1    | 2    | 3    | 4    | NULL | NULL | etc...

This is not a good idea. It violates first normal form.

Q2 : Is there any general way to represent the graph structure using database?

For a directed graph you can use a table edges with two columns:

nodeid_from nodeid_to
1           2
1           3
1           4

If there is any extra information about each node (such as a node name) this can be stored in another table nodes.

If your graph is undirected you have two choices:

• store both directions (i.e. store 1->2 and 2->1)
• use a constraint that nodeid_from must be less than nodeid_to (i.e. store 1->2 but 2->1 is implied).

The former requires twice the storage space but can make querying easier and faster.

Answer 2

In addition to the two tables route mentioned by Mark take a look at the following link:

http://articles.sitepoint.com/article/hierarchical-data-database/2

This article basically preorders the elements in the tree assigning left and right values. You are then able to select portions or all of the tree using a single select statement.

Node | lft | rght
-----------------
  A  |  0  |  7
  B  |  1  |  2
  C  |  3  |  4
  D  |  5  |  6

EDIT: If you are going to be updating the tree heavily this is not an optimum solution as the whole tree must be re-numbered