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 "
      SELECT
      c.*,
      o.context_id,
      tree_level(o.tree_sortkey)
      FROM
      blog_categories c,
      acs_objects o
      WHERE
      c.category_id = o.object_id
      ORDER BY
      o.tree_sortkey"
    

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:

      SELECT 
      children.*,
      tree_level(children.tree_sortkey) -
        tree_level(parent.tree_sortkey) as level
      FROM 
      some_table parent, 
      some_table children
      WHERE 
      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 substract 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:

      SELECT
      subtree.*,
      tree_level(subtree.tree_sortkey) -
        tree_level(parent.tree_sortkey) as level
      FROM some_table parent, some_table subtree
      WHERE 
      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:

      SELECT
      p.item_id,
      repeat(:indent_pattern, (tree_level(p.tree_sortkey) - 5)* :indent_factor) as indent,
      p.parent_id as folder_id,
      p.project_name
      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.

View comments on this page at openacs.org