19

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?
Improve this question
2
  • 3
    What kind of queries do you need to do? That might change the way you store them... Commented Jun 3, 2010 at 19:15
  • 4
    By "database" do you actually mean "relational database"? If not, a Graph Database would be the obvious choice. Commented Jun 4, 2010 at 7:33

4 Answers 4

Reset to default
33

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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

Improve this answer

1 Comment

Trees are a bit different than directed or undirected graphs but this is a good reference if you need trees.
1

I have stored multiple "TO" nodes in a relational representation of a graph structure. I was able to do this because my graph was directed. This meant that if I wanted to know what nodes "A" was connected to, I only needed to select a single record from my table of connections. I stored the TO nodes in an easy-to-parse string and it worked great, with a class that could manage the conversion from string to collection and back.

Improve this answer

Comments

0

I recommend looking at dedicated graph databases, as nawroth suggests. One example would be the "Trinity" Database, suited for very large datasets. But there are others.

Listen to the podcast by Scott Hanselman on Hanselminutes about Trinity. Here is the text transcript.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.