Hierarchical data

by Jade Rubick with help from many people in the OpenACS community

OpenACS docs are written by the named authors, and may be edited by OpenACS documentation staff.

One of the nice things about using the OpenACS object system is that it has a built-in facility for tracking hierarchical data in an efficient way. The algorithm behind this is called tree_sortkey.

Any time your tables are subclasses of the acs_objects table, then you automatically get the ability to structure them hierarchically. The way you do this is currently via the context_id column of acs_objects (Note that there is talk of adding in a parent_id column instead, because the use of context_id has been ambiguous in the past). So when you want to build your hierarchy, simply set the context_id values. Then, when you want to make hierarchical queries, you can do them as follows:

      db_multirow categories blog_categories "
      blog_categories c,
      acs_objects o
      c.category_id = o.object_id
      ORDER BY

Note the use of the tree_level() function, which gives you the level, starting from 1, 2, 3...

Here's an example, pulling all of the children for a given parent:

      tree_level(children.tree_sortkey) -
        tree_level(parent.tree_sortkey) as level
      some_table parent, 
      some_table children
      children.tree_sortkey between parent.tree_sortkey and tree_right(parent.tree_sortkey)
      and parent.tree_sortkey <> children.tree_sortkey
      and parent.key = :the_parent_key;

The reason we subtract the parent's tree_level from the child's tree_level is that the tree_levels are global, so if you want the parent's tree_level to start with 0, you'll want the subtraction in there. This is a reason you'll commonly see magic numbers in tree_sortkey SQL queries, like tree_level(children.tree_sortkey) - 4. That is basically an incorrect way to do it, and subtracting the parent's tree_level is the preferred method.

This example does not include the parent. To return the entire subtree including the parent, leave out the non-equals clause:

      tree_level(subtree.tree_sortkey) -
        tree_level(parent.tree_sortkey) as level
      FROM some_table parent, some_table subtree
      subtree.tree_sortkey between parent.tree_sortkey and tree_right(parent.tree_sortkey)
      and parent.key = :the_parent_key;

If you are using the Content Repository, you get a similar facility, but the parent_id column is already there. Note you can do joins with tree_sortkey:

      repeat(:indent_pattern, (tree_level(p.tree_sortkey) - 5)* :indent_factor) as indent,
      p.parent_id as folder_id,
      FROM pm_projectsx p, cr_items i
      WHERE p.project_id = i.live_revision
      ORDER BY i.tree_sortkey

This rather long thread explains How tree_sortkeys work and this paper describes the technique for tree_sortkeys, although the OpenACS implementation has a few differences in the implementation, to make it work for many languages and the LIKE construct in Postgres.