0

I need help with a project that I am working on: How do I calculate left and right in a Nested Set Model assuming all inputs come in in no particular order.

4 forms are distributed, each form brings 4 people and each 4 people bring another four people. The network grows downword until 7 generations. How can i find downliners and upliners assuming i decide to pick a node at any level?

     A
|    |   |   |
B    C   D   E 
             |
         ------------
         |   |   |   |
         F   G   H    J
         |
     ----------
     |   |  |  |
     W   X  Y  Z

Explanation:

A brings A B C D
E then brings F G H J
F brings WXYZ

and so on and so forth. At 7th generation we experience an halt. Meanwhile each node begins a lineage downwords.

Dan D.
  • 73,243
  • 15
  • 104
  • 123
dasersoft
  • 155
  • 2
  • 13

1 Answers1

2

Calculating left and right visitation numbers is an iterative, procedural operation. It can't be done in a single query, but you can do it with a single procedure that calls itself recursively.

Your procedure needs to have two parameters:

  • ID of the node you are working on
  • Highest visitation number used so far (the next LEFT is this + 1)

The procedure needs to return the highest visitation number it has applied (the last RIGHT).

Within the procedure, you run a query to find all of the children of the node with the given ID. If they are in order, you can sort accordingly - or you can use an arbitrary order. For each child found, set the left number and then call the procedure recursively on that child. When the recursive call returns, use the return code to set the right visitation number.

Joe Celko has a whole chapter in a book dedicated to how to be clever and efficient with visitation number calculations. If your data set is really big and is edited frequently, you might want to read up on that - otherwise you can just recalculate all of your visitation numbers with every edit to your node list.

Joel Brown
  • 14,123
  • 4
  • 52
  • 64
  • Thank you Joel Brown. I have been going through somethings now on stackoverflow about Closure Table authoured by Bill Karwin. Do you think this really fits into my model? http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462 – dasersoft May 02 '12 at 07:21
  • @dasersoft - Closure Table is another solution which works fine. You'll need to add a `depth` attribute to your nodes if you want to use a closure table to answer questions like which nodes are up and which nodes are down and which nodes are siblings from a given node in a single query. – Joel Brown May 02 '12 at 11:37
  • i did implemented it and it fine now. Using the closure table – dasersoft May 02 '12 at 22:03