CODEWITHSUNDEEP
database-designadjacency-list-model
dasersoft
dasersoft

Reputation: 155

building a nested set

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.

Upvotes: 0

Views: 183

Answers (1)

Joel Brown
Joel Brown

Reputation: 14408

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.

Upvotes: 2

Related Questions