Forum OpenACS Development: Calculating LEVEL

Oracle's CONNECT BY internally generates LEVEL pseudocolumn which holds the nesting depth while it recursively chases parent-child links down to the leaf nodes. This is highly usable in any kind of report generation. There is another Oracle pseudocolumn, ROWNUM, available in all SELECT constructs. As its name implies, it holds ordinary number of currently fetched row. It is also worth mentioning that CONNECT BY queries have severe impact on ordering of output, since it will resemble the order in which the parent-child links have been built. Therefore most probably you won't want to change the ordering produced by CONNECT BY.

OTOH, in nested set model, we are forced to do these neat things manually. Fortunately, simply ordering by l_node will give us the same ordering as with Oracle's CONNECT BY:

  select object_type, supertype, l_node, r_node
  from acs_object_types
  order by l_node

   object_type   | supertype  | l_node | r_node
-----------------+------------+--------+--------
 acs_object      |            |      1 |     20
 relationship    | acs_object |      2 |      3
 party           | acs_object |      4 |     11
 person          | party      |      5 |      8
 user            | person     |      6 |      7
 group           | party      |      9 |     10
 membership_rel  | acs_object |     12 |     13
 composition_rel | acs_object |     14 |     15
 journal_entry   | acs_object |     16 |     17
 site_node       | acs_object |     18 |     19
(10 rows)

However, in nested set model we can't calculate LEVEL of recursion (nesting depth) directly. By "directly" I mean based on information available in current row. Instead we must resort to some scripting language (either inside or outside DBMS). It turns out not to be too difficult:

proc nested_set_compute_level {level r_node} {

  #    Maintain array holding level boundaries at caller's level
  upvar boundary boundary

  #    Now traverse down the $boundary array until we find which level
  #  this entry belongs to.  For this purpose we'll use r_node
  #  which we will successively compare to $boundary($level),
  #  $boundary($level-1) etc until we find the level the current row
  #  is bounded with.  When found, adjust the $level and its
  #  boundary.
  
  for {set i $level} {$i > 0} {incr i -1} {
      if {$r_node < $boundary($i)} {
          break
      }
  }
  set level [expr $i + 1]
  set boundary($level) $r_node

  return $level
}

Here's one simple example:

...

set db [ns_db gethandle]
set row [ns_db select $db "select object_type, supertype, l_node, r_node
      from acs_object_types order by l_node"]

set level 0
while {[ns_db getrow $db $row]} {

  set object_type [ns_set get $row object_type]
  set supertype [ns_set get $row supertype]
  set l_node [ns_set get $row l_node]
  set r_node [ns_set get $row r_node]

  set level [nested_set_compute_level $level $r_node]

  set ident_html ""
  regsub -all . [format "%*s" $level { }] {  } ident_html

  append return_html "

    <tr>
      <td>$ident_html $object_type</td>
      <td>$supertype</td>
      <td>$level</td>
      <td>$l_node</td>
      <td>$r_node</td>
    </tr>

  "
}

ns_return ...

Previously displayed record set now appears as:

object_type	supertype	level	l_node	r_node
acs_object		1	1	20
relationship	acs_object	2	2	3
party	acs_object	2	4	11
person	party	3	5	8
user	person	4	6	7
group	party	3	9	10
membership_rel	acs_object	2	12	13
composition_rel	acs_object	2	14	15
journal_entry	acs_object	2	16	17
site_node	acs_object	2	18	19