Home
The Toolkit for Online Communities
17622 Community Members, 0 members online, 3028 visitors today
Log In Register
OpenACS Home : Forums : OpenACS Development : CONNECT BY solution : One Message

Forum OpenACS Development: Multiple parents

Collapse
2: Multiple parents (response to 1)
Posted by Sebastian Skracic on
So far, everything worked as expected until I've stumbled upon acs-permissions-create.sql which defines:
create table acs_privileges (
        privilege       varchar(100) not null constraint acs_privileges_pk
                        primary key,
        pretty_name     varchar(100),
        pretty_plural   varchar(100)
);

create table acs_privilege_hierarchy (
        privilege       not null constraint acs_priv_hier_priv_fk
                        references acs_privileges (privilege),
        child_privilege not null constraint acs_priv_hier_child_priv_fk
                        references acs_privileges (privilege),
        constraint acs_privilege_hierarchy_pk
        primary key (privilege, child_privilege)
);

create or replace view acs_privilege_descendant_map
as select p1.privilege, p2.privilege as descendant
   from acs_privileges p1, acs_privileges p2
   where p2.privilege in (select child_privilege
                          from acs_privilege_hierarchy
                          start with privilege = p1.privilege
                          connect by prior child_privilege = privilege)
   or p2.privilege = p1.privilege;
Gotcha! Nested set model (as described above) won't work in this case. Nested sets represent flattened hierarchy tree where every item is supposed to appear exactly once.

Back to the privilege hierarchy: each privilege can have arbitrary number of child privileges, but some privileges can be child of (i.e. implied by) more than one parent privileges. For example, 'admin' implies 'read', 'write', 'delete', ... but it makes sense that 'moderate' implies 'read' as well:

  select privilege, child_privilege
    from acs_privilege_hierarchy
    order by privilege, child_privilege;

 privilege | child_privilege
-----------+-----------------
 admin     | create
 admin     | delete
 admin     | read
 admin     | write
 all       | admin
 all       | moderate
 moderate  | read
 moderate  | write
 read      | browse
(9 rows)
The hierarchy tree (actually this is not a tree any more) generated with Oracle's CONNECT BY will look like:
  • all
    • admin
      • create
      • delete
      • read
        • browse
      • write
      • moderate
        • read
          • browse
        • write
      • What we see here is that some subhierarchies are appearing multiple times in this quasi-tree. For example, 'read' privilege implies 'browse' child privilege, but it has two parent privileges: 'moderate' and 'admin'. Every time the 'read' appears as a child of either, it must carry the whole subtree along.

        So, simple nested set model won't help us here because an element can appear multiple times in hierarchy.

        Extended nested set model

        After fiddling with this a little more, I've come up with the solution based on slightly extended nested set data model. In addition to acs_privilege and acs_privilege_hierarchy, I've created additional table to store sets themselves:
        create table acs_privilege_hierarchy_index (
                privilege       varchar(100) not null
                                constraint acs_priv_hier_ndx_priv_fk
                                references acs_privileges (privilege),
                child_privilege varchar(100) not null
                                constraint acs_priv_hier_ndx_child_priv_fk
                                references acs_privileges (privilege),
                l_node          integer not null,
                r_node          integer not null
        );
        
        This table is used to translate quasi-hierarchy tree shown above into the nested set model. Why couldn't we simply put l_node and r_node in acs_privilege_hierarchy? Because a single entry in acs_privilege_hierarchy could generate many elements in quasi-hierarchy. In other words, (privilege, child_privilege) pair cannot uniquely describe position of particular element in quasi-hierarchical tree listing, so there is no point of attaching (l_node, r_node) attribute to it.

        As in the "normal" nested set model, acs_privilege_hierarchy_index is being maintained with triggers for INSERT and DELETE on acs_privilege_hierarchy. acs_privilege_descendant_map can be defined through:

        
          create view acs_privilege_descendant_map
          as select p1.privilege, p2.privilege as descendant
             from
               acs_privileges p1,
               acs_privileges p2
             where p2.privilege in
                                 (select h2.child_privilege
                                    from
                                        acs_privilege_hierarchy_index h1,
                                        acs_privilege_hierarchy_index h2
                                    where
                                      h1.child_privilege = p1.privilege
                                      and h1.l_node <= h2.l_node
                                      and h1.r_node >= h2.r_node) ;
        
          select privilege, descendant
            from acs_privilege_descendant_map
            order by privilege, descendant;
        
         privilege | descendant
        -----------+------------
         admin     | admin
         admin     | browse
         admin     | create
         admin     | delete
         admin     | read
         admin     | write
         all       | admin
         all       | all
         all       | browse
         all       | create
         all       | delete
         all       | moderate
         all       | read
         all       | write
         browse    | browse
         create    | create
         delete    | delete
         moderate  | browse
         moderate  | moderate
         moderate  | read
         moderate  | write
         read      | browse
         read      | read
         write     | write
        (24 rows)
        

        Triggers

        I'm not going to enter into more details right now, I'll simply post the trigger code:
        create trigger acs_privil_hier_nested_set_in_tr before insert
          on acs_privilege_hierarchy for each row
          execute procedure
          multiple_nested_set_insert_node('acs_privilege_hierarchy_index',
            'child_privilege', 'privilege');
        
        
        create trigger acs_privil_hier_nested_set_del_tr after delete
          on acs_privilege_hierarchy for each row
          execute procedure
          multiple_nested_set_delete_node('acs_privilege_hierarchy_index',
            'child_privilege', 'privilege') ;
        
        
        
        create function multiple_nested_set_insert_node () returns opaque as '
        
            set TABLE           $1
            set COLUMN          $2
            set PARENT_COLUMN   $3
        
            set CHILD_ID $NEW($COLUMN)
            set PARENT_ID $NEW($PARENT_COLUMN)
        
            set subset_width 2
            set garbage_collect_p 0
        
            #  Do we have parent already?
        
            spi_exec "select count(*) as parent_p from $TABLE
                where $COLUMN = ''[quote $PARENT_ID]''"
            if {!$parent_p} {
                spi_exec "select coalesce(max(r_node),0) as rightmost_node from $TABLE"
                spi_exec "insert into $TABLE
                                 ($COLUMN, $PARENT_COLUMN, l_node, r_node)
                          values (''[quote $PARENT_ID]'', ''[quote $PARENT_ID]'',
                                  $rightmost_node + 1, $rightmost_node + 2)"
            }
        
            #  Does the children stand on its own in hierarchy?  i.e. is this
            #  its first designated parent?
        
            spi_exec "select l_node as child_l_node, r_node as child_r_node
              from $TABLE
              where $COLUMN = $PARENT_COLUMN and $COLUMN = ''[quote $CHILD_ID]''"
        
            if {[info exists child_l_node]} {
        
                #  We should also garbage collect the space this subset occupied.
                set garbage_collect_p 1
                set subset_width [expr $child_r_node - $child_l_node + 1]
        
            } else {
        
                #    However, our child could still have had its own children,
                #  regardless of standing on top of hierarchy tree.
                #
                spi_exec "select l_node as child_l_node, r_node as child_r_node
                    from $TABLE where $COLUMN = ''[quote $CHILD_ID]''
                                  and $COLUMN <> $PARENT_COLUMN " {
        
                    #  Child patterns should be all the same, so exit on first found
                    set subset_width [expr $child_r_node - $child_l_node + 1]
                    break
                }
            }
            if {![info exists child_l_node]} {
            }
        
            #  Inserting new CHILD node.  We need to lookup its parent and
            #  then insert in appropriate position.
            #     Attention!  There might be multiple parent entries!
            #  Perform this stuff for each parent entry found.
            set i 0
            set adjustment 0
            spi_exec "select r_node as parent_r_node
                from $TABLE where $COLUMN = ''[quote $PARENT_ID]''
                order by r_node" {
        
                incr parent_r_node $adjustment
        
                incr i
                if {$garbage_collect_p} {
                    set garbage_collect_p 0
                    spi_exec "update $TABLE
                      set $PARENT_COLUMN = ''[quote $PARENT_ID]''
                      where $COLUMN = $PARENT_COLUMN and $COLUMN = ''[quote $CHILD_ID]''"
                    spi_exec "update $TABLE set l_node = l_node + $subset_width
                      where l_node > $parent_r_node"
                    spi_exec "update $TABLE set r_node = r_node + $subset_width
                      where r_node >= $parent_r_node"
                    set offset [expr $parent_r_node - $child_l_node]
                    spi_exec "update $TABLE set l_node = l_node + $offset
                      where l_node >= $child_l_node
                        and l_node < $child_r_node"
                    spi_exec "update $TABLE set r_node = r_node + $offset
                      where r_node > $child_l_node
                        and r_node <= $child_r_node"
                    #  We now must renumber nodes to fill in the gaps.
                    #  Gap is bounded by (child_l_node, child_r_node).
                    spi_exec "update $TABLE set l_node = l_node - $subset_width
                      where l_node >= $child_l_node"
                    spi_exec "update $TABLE set r_node = r_node - $subset_width
                      where r_node > $child_l_node"
                } else {
                    #  Allocate $subset_width nodes
                    spi_exec "update $TABLE set l_node = l_node + $subset_width
                      where l_node > $parent_r_node"
                    spi_exec "update $TABLE set r_node = r_node + $subset_width
                      where r_node >= $parent_r_node"
        
                    spi_exec "insert into $TABLE
                      ($COLUMN, $PARENT_COLUMN, l_node, r_node)
                      values
                      (''[quote $CHILD_ID]'', ''[quote $PARENT_ID]'',
                       $parent_r_node, $parent_r_node + $subset_width - 1)"
        
                    incr adjustment $subset_width
        
                    #  Now copy grandchildren (if exist)
                    if {$subset_width > 2} {
                        #  Careful not to locate the row just inserted!
                        spi_exec "select l_node as child_l_node, r_node as child_r_node
                          from $TABLE
                          where $COLUMN = ''[quote $CHILD_ID]''
                          and l_node <> $parent_r_node" {
                            break
                        }
                        set offset [expr $parent_r_node - $child_l_node]
                        spi_exec "insert into $TABLE
                          ($COLUMN, $PARENT_COLUMN, l_node, r_node)
                          select
                            $COLUMN, $PARENT_COLUMN, l_node + $offset, r_node + $offset
                          from $TABLE
                          where
                            l_node > $child_l_node
                            and r_node < $child_r_node"
                    }
                }
            }
        
        
            return OK
        
        ' language 'pltcl';
        
        
        
        
        
        create function multiple_nested_set_delete_node () returns opaque as '
        
            set TABLE           $1
            set COLUMN          $2
            set PARENT_COLUMN   $3
        
            set CHILD_ID $OLD($COLUMN)
            set PARENT_ID $OLD($PARENT_COLUMN)
        
            #  Find all nested subsets carrying ($CHILD_ID, $PARENT_ID) mappings
        
            set more_rows_p 1
            set move_to_the_top_p 1
            while {$more_rows_p} {
                set more_rows_p 0
                spi_exec "select l_node as subset_l_node, r_node as subset_r_node
                    from $TABLE
                    where $COLUMN = ''[quote $CHILD_ID]''
                      and $PARENT_COLUMN = ''[quote $PARENT_ID]''" {
        
                      set more_rows_p 1
                      set subset_width [expr $subset_r_node - $subset_l_node + 1]
                      break
                }
                if {$more_rows_p} {
                    if {$move_to_the_top_p} {
                        #
                        #    Why this check?
                        #
                        #    Because particular subset can appear several times in
                        #  nested set hierarchy, all of these subsets being
                        #  identical.  We only need to preserve one of these,
                        #  say first one found.  All others will be garbage
                        #  collected.
                        #
                        #    There is an exception:
                        #
                        #    Check whether $CHILD_ID has any other parent left.
                        #  If yes, we simply delete the first rec found as all others
                        #  (since remaining parentage line(s) will take care of
                        #  child''s children).  If not, move to the top of hierarchy
                        #  tree, but update the $PARENT_COLUMN field in index entry to
                        #  reflect these (i.e. point to child itself).
                        spi_exec "select count(*) as other_parents_p
                          from $TABLE
                          where $COLUMN = ''[quote $CHILD_ID]''
                          and $PARENT_COLUMN <> ''[quote $PARENT_ID]''"
                        if {$other_parents_p} {
                            set move_to_the_top_p 0
                        }
                    }
                    if {$move_to_the_top_p} {
        
                        set move_to_the_top_p 0
        
                        #  Last minute check: if this child has no children,
                        #  simply delete it from hierarchy.
        
                        if {$subset_width == 2} {
                            spi_exec "delete from $TABLE
                                where $COLUMN = ''[quote $CHILD_ID]''
                                and l_node = $subset_l_node"
                        } else {
                            #  We have $subset_l_node and $subset_r_node
                            spi_exec "update $TABLE
                              set $PARENT_COLUMN = ''[quote $CHILD_ID]''
                                where l_node = $subset_l_node
                                  and r_node = $subset_r_node"
                            spi_exec "select max(r_node) as rightmost_node
                              from $TABLE"
                            set offset [expr $rightmost_node - $subset_l_node + 1]
                            #  Move subset to the top of hierarchy tree.
                            spi_exec "update $TABLE set
                                l_node = l_node + $offset,
                                r_node = r_node + $offset
                              where l_node >= $subset_l_node
                                and r_node <= $subset_r_node"
                        }
        
                    } else {
        
                        spi_exec "delete from $TABLE
                          where l_node >= $subset_l_node
                            and r_node <= $subset_r_node"
                    }
        
                    #  Renumber and we''re all set.
                    spi_exec "update $TABLE set
                        l_node = l_node - $subset_width
                        where l_node > $subset_l_node"
                    spi_exec "update $TABLE set
                        r_node = r_node - $subset_width
                        where r_node > $subset_l_node"
        
                    #  But hey!
                    #  Since we''ve just deleted one entry from $TABLE
                    #  we should delete its parent as well *if* the deleted
                    #  entry had turned out to be its last child and *if*
                    #  the parent has no parents of its own.
                    spi_exec "select
                        l_node as parent_l_node, r_node as parent_r_node
                      from
                        $TABLE
                      where
                        $COLUMN = $PARENT_COLUMN
                        and $PARENT_COLUMN = ''[quote $PARENT_ID]''
                        and r_node = l_node + 1" {
                        
                        spi_exec "delete from $TABLE
                          where l_node = $parent_l_node
                            and r_node = $parent_r_node"
                        spi_exec "update $TABLE set
                          l_node = l_node - 2
                          where l_node > $parent_l_node"
                        spi_exec "update $TABLE set
                          r_node = r_node - 2
                          where r_node > $parent_r_node"
                    }
                }
            }
        
            return OK
        
        ' language 'pltcl';