Forum OpenACS Q&A: Nested set solution

OK, a while ago I've read about nested set model in Celko's book. Unfortunately, I don't have the book at hand, but I was fiddling with it this morning and it seems that things work 😊

This sample table is taken from ACS 4.0. acs_object_types implements classic child-parent relationships through object_type and supertype columns. Here's the DDL:

create table acs_object_types (
        object_type     varchar(100) not null
                        constraint acs_object_types_pk primary key,
        supertype       varchar(100) constraint acs_object_types_supertype_fk
                        references acs_object_types (object_type),
        abstract_p      char(1) default 'f' not null
                        constraint acs_obj_types_abstract_p_ck
                        check (abstract_p in ('t', 'f')),
        pretty_name     varchar(100) not null
                        constraint acs_obj_types_pretty_name_un
                        unique,
        pretty_plural   varchar(100) not null
                        constraint acs_obj_types_pretty_plural_un
                        unique,
        table_name      varchar(30) not null
                        constraint acs_object_types_tbl_name_un unique,
        id_column       varchar(30) not null,
        package_name    varchar(30) not null
                        constraint acs_object_types_pkg_name_un unique,
        name_method     varchar(30),
        type_extension_table varchar(30),
        l_node          integer not null,
        r_node          integer not null
);

There is separated trigger/procedure for INSERT, UPDATE and DELETE. Let's review them one by one.

INSERT

This is fairly trivial, the only thing we have to do is to locate the parent of newly inserted record, if such exists.

create function nested_set_insert_node () returns opaque as '
declare
    rightmost_node    acs_object_types.r_node%TYPE;
    parent_r_node     acs_object_types.r_node%TYPE;
begin
    --  We differentiate two cases, depending on whether the newly
    --  inserted has parent or not.
    if new.supertype is null then
        --  New node is added at the end of the nested set list.
        select coalesce(max(r_node),0) into rightmost_node from acs_object_types;
        new.l_node := rightmost_node + 1;
        new.r_node := rightmost_node + 2;
    else
        --  New node is inserted at the right node of the parent,
        --  shifting everything two places to the right.
        select r_node into parent_r_node from acs_object_types
          where object_type = new.supertype;
        update acs_object_types
          set l_node = l_node + 2
          where l_node > parent_r_node;
        update acs_object_types
          set r_node = r_node + 2
          where r_node >= parent_r_node;
        new.l_node := parent_r_node;
        new.r_node := parent_r_node + 1;
    end if;
    return new;
end;
' language 'plpgsql';

create trigger nested_set_insert_tr before insert
  on acs_object_types for each row
  execute procedure nested_set_insert_node() ;