Forum OpenACS Q&A: Nested set solution

Collapse
7: Nested set solution (response to 1)
Posted by Sebastian Skracic on
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() ;