Request notifications
As we all know, Oracle's CONNECT BY clause enables us to traverse
data in simple hierarchies. In its heart, CONNECT BY establishes
parent-child relationship between two rows based on specified
criterion. To be able to appropriately use CONNECT BY, our data model
must provide 'child' and 'parent' slots:
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),
...
);
Suppose we have hiearchy defined with these entries:
object_type | supertype -----------------+------------ acs_object | relationship | acs_object party | acs_object person | party user | person group | party membership_rel | acs_object composition_rel | acs_object journal_entry | acs_object site_node | acs_objectOr, presented as hierarchy tree:
- acs_object
- relationship
- party
- person
- user
- group
- person
- membership_rel
- composition_rel
- journal_entry
- site_node
In Oracle, querying for all subtypes of 'party' object_type is
performed with:
select
object_type
from
acs_object_types
start with
object_type = 'party'
connect by
object_type = prior supertype;
Shortly, we denote root of subtree we want to take out of
hierarchy
with START WITH clause, and criterion which maps child row to its
parent
with CONNECT BY clause.
Let's build the simple view which will hold all type-supertype mappings, regardless of number of generations involved:
create or replace view acs_object_type_supertype_map
as select ot.object_type, ota.object_type as ancestor_type
from acs_object_types ot, acs_object_types ota
where ota.object_type in (select object_type
from acs_object_types
start with object_type = ot.supertype
connect by object_type = prior
supertype);
select object_type, ancestor_type
from acs_object_type_supertype_map
order by object_type, ancestor_type;
object_type | ancestor_type
-----------------+-----------------
acs_object | acs_object
composition_rel | acs_object
composition_rel | composition_rel
group | acs_object
group | group
group | party
journal_entry | acs_object
journal_entry | journal_entry
membership_rel | acs_object
membership_rel | membership_rel
party | acs_object
party | party
person | acs_object
person | party
person | person
relationship | acs_object
relationship | relationship
site_node | acs_object
site_node | site_node
user | acs_object
user | party
user | person
user | user
(23 rows)
Detailed explanation of handling trees in Oracle is available
at Trees
in Oracle SQL chapter in SQL for Web Nerds.
Nested set model
In contrast to parent-child model of representing trees, nested set model (as described in Celko's SQL for smarties), represents hierarchy by assigning two numbers (left and right node) to each element. Parent elements simply nests its children which can further have its own children etc:
create table acs_object_types (
object_type varchar(100) not null
constraint acs_object_types_pk primary key,
l_node integer not null,
r_node integer not null,
...
);
Previously shown hierarchy can be represented with following entries
in nested set model:
object_type | l_node | r_node -----------------+--------+-------- acs_object | 1 | 20 relationship | 2 | 3 party | 4 | 11 person | 5 | 8 user | 6 | 7 group | 9 | 10 membership_rel | 12 | 13 composition_rel | 14 | 15 journal_entry | 16 | 17 site_node | 18 | 19Or illustrated:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | | | | | | | | | | | | | | | | | | | | | relnshp | | +user+ | +group+ | membrel comp_r jrn_ent sit_nd | | | +-person-+ | | | +--------party--------+ | +---------------------------acs_object---------------------------+Searching for all subtypes of 'party' object_type can be performed by:
select
object_type
from
acs_object_types
where
l_node > 4
and r_node < 11;
object_type
-------------
person
user
group
Similarly, one can search for all supertypes of 'user' object_type:
select
object_type
from
acs_object_types
where
l_node < 6
and r_node > 7;
object_type
-------------
person
party
acs_object
Again, building parent-child mappings spanning multiple generations
is nothing more difficult than with Oracle-specific CONNECT BY:
create view acs_object_type_supertype_map
as select ot.object_type, ota.object_type as ancestor_type
from acs_object_types ot, acs_object_types ota
where ota.object_type in (select object_type
from acs_object_types
where l_node <= ot.l_node
and r_node >= ot.r_node );
Triggers
Fields l_node and r_node are being maintained by triggers firing on all write operations to acs_object_types table.These triggers are written in PostgreSQL's pltcl procedural language, so that they can be reused for any table involving parent-child relationships. They can also be adapted for other databases, except that Oracle will barf on you with famous "table is mutating" error because you want to manipulate rows of the same table the trigger is acting on.
create trigger acs_obj_types_nested_set_ins_tr before insert
on acs_object_types for each row
execute procedure
nested_set_insert_node('acs_object_types', 'object_type',
'supertype');
create trigger acs_obj_types_nested_set_upd_tr after update
on acs_object_types for each row
execute procedure
nested_set_update_node('acs_object_types', 'object_type',
'supertype') ;
create trigger acs_obj_types_nested_set_del_tr before delete
on acs_object_types for each row
execute procedure
nested_set_delete_node('acs_object_types', 'object_type',
'supertype') ;
Each trigger expects three arguments: table name and child and
parent
field column names.
- INSERT trigger
create function nested_set_insert_node () returns opaque as '
set TABLE $1
set COLUMN $2
set PARENT_COLUMN $3
if {![info exists NEW($PARENT_COLUMN)]} {
# New node is added at the end of the nested set list.
spi_exec "select coalesce(max(r_node),0) as rightmost_node
from $TABLE"
set NEW(l_node) [expr $rightmost_node + 1]
set NEW(r_node) [expr $rightmost_node + 2]
} else {
spi_exec "select r_node as parent_r_node from $TABLE
where $COLUMN = ''[quote $NEW($PARENT_COLUMN)]''"
spi_exec "update $TABLE set l_node = l_node + 2
where l_node > $parent_r_node"
spi_exec "update $TABLE set r_node = r_node + 2
where r_node >= $parent_r_node"
set NEW(l_node) $parent_r_node
set NEW(r_node) [expr $parent_r_node + 1]
}
return [array get NEW]
' language 'pltcl';
- UPDATE trigger
create function nested_set_update_node () returns opaque as '
set TABLE $1
set COLUMN $2
set PARENT_COLUMN $3
# We cannot use new.l_node and new.r_node since they can
# be superseded by bunch of UPDATEs in this very trigger
# (this happens if the trigger fires on more than 1 row).
# So we retrieve the actual value of l_node and r_node with this:
spi_exec "select l_node as curr_l_node, r_node as curr_r_node
from $TABLE
where $COLUMN = ''[quote $NEW($COLUMN)]''"
# We have to rearrange nodes only if supertype has been changed.
# There are two main code branches:
# 1. supertype changes from NOT NULL to NULL
# 2. supertype changes from something to NOT NULL
if {![info exists OLD($PARENT_COLUMN)]
&& ![info exists NEW($PARENT_COLUMN)]} {
return "OK"
}
if {[info exists OLD($PARENT_COLUMN)]
&& [info exists NEW($PARENT_COLUMN)]
&& ![string compare $OLD($PARENT_COLUMN)
$NEW($PARENT_COLUMN)]} {
return "OK"
}
# In any case we must shift entire subset out of its parent
# and put it to the right of the rightmost node, to prevent
# it from being overwritten by node adjustments.
spi_exec "select max(r_node) as rightmost_node from $TABLE"
set nested_set_width [expr $curr_r_node - $curr_l_node + 1]
set shift_offset [expr $rightmost_node - $curr_l_node + 1]
# Shift nested subset out of its parent.
spi_exec "update $TABLE
set l_node = l_node + $shift_offset,
r_node = r_node + $shift_offset
where l_node >= $curr_l_node
and r_node <= $curr_r_node"
# It''s good to know that the [$curr_l_node,$curr_r_node]
interval
# is now not occupied by nodes.
#
# Case 1)
#
if {[info exists OLD($PARENT_COLUMN)]
&& ![info exists NEW($PARENT_COLUMN)]} {
# Since we have already lifted our subset out of its
# position, we will simply renumber the nodes to fill the
gaps.
spi_exec "update $TABLE
set l_node = l_node - $nested_set_width
where l_node > $curr_r_node"
spi_exec "update $TABLE
set r_node = r_node - $nested_set_width
where r_node > $curr_r_node"
return "OK"
}
#
# Case 2)
#
if {[info exists NEW($PARENT_COLUMN)]} {
# The tricky part here is that we must pay attention whether
# the gap is to the left or to the right of inserting point.
spi_exec "select l_node as parent_l_node, r_node as
parent_r_node
from $TABLE
where $COLUMN = ''[quote $NEW($PARENT_COLUMN)]''"
# Where will this subset be moved?
if {$parent_r_node < $curr_l_node} {
# Gap is to the right of inserting point
spi_exec "update $TABLE set
l_node = l_node + $nested_set_width
where l_node > $parent_r_node
and l_node < $curr_l_node"
spi_exec "update $TABLE set
r_node = r_node + $nested_set_width
where r_node >= $parent_r_node
and r_node < $curr_l_node"
# Place the subset under its new parent
set shift_offset [expr $rightmost_node - $parent_r_node +
1]
} else {
# The gap is to the LEFT of inserting point
spi_exec "update $TABLE set
l_node = l_node - $nested_set_width
where l_node <= $parent_l_node
and l_node > $curr_r_node"
spi_exec "update $TABLE set
r_node = r_node - $nested_set_width
where r_node < $parent_l_node
and r_node > $curr_r_node"
set shift_offset [expr $rightmost_node + $nested_set_width
- $parent_l_node]
}
spi_exec "update $TABLE set
r_node = r_node - $shift_offset,
l_node = l_node - $shift_offset
where l_node > $rightmost_node"
return "OK"
}
return "OK"
' language 'pltcl';
- DELETE trigger
create function nested_set_delete_node () returns opaque as '
set TABLE $1
set COLUMN $2
set PARENT_COLUMN $3
# We must prevent deletion of non-leaf nodes.
if {[expr $OLD(r_node) - $OLD(l_node)] != 1} {
elog ERROR "Type ''$OLD($COLUMN)'' cannot be deleted, l_node =
$OLD(l_node) r_node = $OLD(r_node)"
return "SKIP"
}
spi_exec "update $TABLE set
l_node = l_node - 2
where l_node > $OLD(r_node)"
spi_exec "update $TABLE set
r_node = r_node - 2
where r_node > $OLD(r_node)"
return "OK"
' language 'pltcl';