Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Storing a tree structure in a relational database..

 
Jim Bertorelli
Ranch Hand
Posts: 136
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a handle to the root of a tree (may not be a binary tree). All the node objects are of same class.
The objective is to flatten the tree and store it into an RDB such that, given an id(?) of a node, it is easy to retrieve the branch associated with that node.
Can anybody suggest an approach to do this?

What would be best approach
 
Jason Kilgrow
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Bertorelli:
I have a handle to the root of a tree (may not be a binary tree). All the node objects are of same class.
The objective is to flatten the tree and store it into an RDB such that, given an id(?) of a node, it is easy to retrieve the branch associated with that node.
Can anybody suggest an approach to do this?

What would be best approach

Hmmm...I'm not sure if this is what you are looking for, but here's my thought...
1. each node has an id.
2. the root node has child node(s)
3. I'm thinking of a table that uses self-joins
So, your table may look like:
id number(6) not null
node number(6) not null
The id and node are the primary key. There may be multiple id's but only one id/node combination. So, each id (which is actually a node number) has one or many nodes. Each node has an id.
Here's some SQL:
Select id,node from nodeTable
where id='111'
and node=id;
This should return a list like:
111 222
111 333
111 444
If 222 has child nodes, then you can run the above sql to get those nodes as well.
I would test this quite a bit before I was really comfortable with it. This may not be the best solution but it was the first one to come to mind.
 
Jim Bertorelli
Ranch Hand
Posts: 136
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yeah...I was thinking on similar lines. The table would have
Parant Id, Node Id and other fields. And then just like you said.
To get all the children of node 3(say), I would do:
select node_id, other nodes from nodeTable
where parent_id='3'

But there are a couple of issue with this:
1. Initialy, when the tree is in memory, the nodes won't have row_id and parent id set. So, to store the tree will be a little complicated. First store the root and thus retrieve the node_id (would be database sequence), set it as parent_id for child nodes, recursively store the child nodes.
2. Retriving a tree or a branch would be much more time consuming. As there could be multiple trees stored in the same table, I just can't load up all the rows in the memory (using one query ) and then build the tree. I have to fire one query for each level.
Any suggestions?
thanks,
Jim.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic