Forum OpenACS Development: Multiple parents
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
- read
- admin
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';
