Self Referencing Trees...

[phant0m]

Not sure if the title is correct. Anyway, here is what I am trying to do:

 

I have tree data structures.

My table looks something like this

 

nodes

id | tree_id | lft | rgt | other attributes for data

 

What I would like to do now, is to map an other tree B as children of a node in tree A. The question is: How do I manage to do this with the least amount of queries possible.

 

Here's what I've been thinking about it.

 

Just add another attribute to the db indicating the tree_id of the tree to map as children of a certain node.

The problem: Until now, I could fetch an entire tree (or subtree) from the DB using a single query. However, I cannot use self joins because a) I do not know whether the referenced tree has references of its own, and much more importantly: Because I do not want to have seperate rows for each level of inclusion. i.e. level1.lft | level2.lft | level3.lft etc

 

 

A way to partly solve this problem:

I could use some kind of a "lookup table".

tree_id | ref_id | directly

 

Every time I modify a tree, I will update that table. "directly" is used, so that I can see whether a tree A includes an other tree B directly,  or because it includes a tree C which in turn includes tree B.

This should speed things up when I want to know which trees a certain tree A includes directly or indirectly. (only one query needed, but more time required when changing the structure of a tree)

 

I have tried to express everything as clearly as I can

 

any ideas?

[SoccerGloves]

Hi!  I don't think I have any good advice, so don't get to excited about my reply =)  but I just want to make sure I understand what you are trying to do:

 

You have a hierarchy.  You have a list of nodes, and each node fits into a tree. so, for example, you have:

 

> Tree A

> - > Node 1

> - > Node 2

> - > Node 3

> Tree B

> - > Node 4

> - > Node 5

> - > Node 6

> Tree C

> - > Node 7

> - > Node 8

> - > Node 9

 

And in your table of nodes, that would look like:

 

[node id][belongs to tree]

[Node 1][Tree A]

[Node 2][Tree A]

[Node 3][Tree A]

[Node 4][Tree B]

[Node 5][Tree B]

[Node 6][Tree B]

[Node 7][Tree C]

[Node 8][Tree C]

[Node 9][Tree C]

 

And you are trying, now, to allow trees to be inside of other trees, like:

 

> Tree A

> - > Node 1

> - > Node 2

> - > Node 3

> Tree B

> - > Node 4

> - > - > Tree C

> - > - > - > Node 7

> - > - > - > Node 8

> - > - > - > Node 9

> - > Node 5

> - > Node 6

 

Where Tree C now belongs to Node 4 inside of tree B.

 

And you want to come up with a way to make this inter-nesting happen, in a way that uses the fewest database calls possible, right?

[Mchl]

See this presentation:

for some tips.

[phant0m]

@SoccerGloves: Yes, this is exactly what I want to do. (I assume that you made the trees 1D for the sake of simplicity)

 

@Mchl: I've been looking at those slides already. At the moment, I am using the Nested Sets model. Although, I am thinking about using the Closure Tables model instead... (I will have to add an additional attribute though to preserve the order of the nodes, which is what the Nested Sets model provides by itself)

However, I have just been looking at those slides again and I have come to realize that the Closure Tables model is more or less exactly, what I have been thinking about to use to indicate the relationships between the nodes and the trees that they reference...