OpenACS (http://www.openacs.org)에서 사용하는 트리구조형 카테고리 구현 부분입니다.

pl/pgSQL 은 모두 openacs4 의 ACS Kernel 4.2 의 postgresql.sql 에 있는 부분이고요 마지막의 category_insert_tr() 와 category_update_tr() 는 테이블 이름만 category 로 변경한 것입니다.

참고가 되었으면 합니다.

===================이하 sql 문 ==================

create table Category (

Category_ID SERIAL not null,

Category_Name VARCHAR null,

Parent_ID INT4 null,

SortKey VARBIT null,

constraint PK_CATEGORY primary key (Category_ID),

constraint FK_CATEGORY_REFERENCE_CATEGORY foreign key (Parent_ID)

references Category (Category_ID)

on delete restrict on update restrict

);

create index category_parent_id_idx on Category (

Parent_ID

);

create index category_sortkey_idx on Category (

SortKey

);

CREATE OR REPLACE FUNCTION int_to_tree_key ( integer )

RETURNS varbit

AS '

-- Convert an integer into the bit string format used to store

-- tree sort keys. Using 4 bytes for the long keys requires

-- using -2^31 rather than 2^31 to avoid a twos-complement

-- "integer out of range" error in PG - if for some reason you

-- want to use a smaller value use positive powers of two!

-- There was an "out of range" check in here when I was using 15

-- bit long keys but the only check that does anything with the long

-- keys is to check for negative numbers.

declare

p_intkey alias for ;

begin

if p_intkey < 0 then

raise exception ''int_to_tree_key: key must be a positive integer'';

end if;

if p_intkey < 2^7 then

return substring(bitfromint4(p_intkey), 25, 8);

else

return substring(bitfromint4(-2^31 + p_intkey), 1, 32);

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable, isstrict)

;

CREATE OR REPLACE FUNCTION tree_key_to_int ( bit varying, integer )

RETURNS int4

AS '

-- Convert the compressed key for the node at the given level to an

-- integer.

declare

p_tree_key alias for ;

p_level alias for ;

v_level integer default 0;

v_parent_pos integer default 1;

v_pos integer default 1;

begin

-- Find the right key first

while v_pos < length(p_tree_key) and v_level < p_level loop

v_parent_pos := v_pos;

v_level := v_level + 1;

if substring(p_tree_key, v_pos, 1) = ''1'' then

v_pos := v_pos + 32;

else

v_pos := v_pos + 8;

end if;

end loop;

if v_level < p_level then

raise exception ''tree_key_to_int: key is at a level less than %'', p_level;

end if;

if substring(p_tree_key, v_parent_pos, 1) = ''1'' then

return bittoint4(substring(p_tree_key, v_parent_pos + 1, 31));

else

return bittoint4(substring(p_tree_key, v_parent_pos, 8));

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable, isstrict)

;

CREATE OR REPLACE FUNCTION tree_ancestor_key ( bit varying, integer )

RETURNS varbit

AS '

-- Returns a key for the ancestor at the given level. The root is level

-- one.

declare

p_tree_key alias for ;

p_level alias for ;

v_level integer default 0;

v_pos integer default 1;

begin

if tree_level(p_tree_key) < p_level then

raise exception ''tree_ancestor_key: key is at a level less than %'', p_level;

end if;

while v_level < p_level loop

v_level := v_level + 1;

if substring(p_tree_key, v_pos, 1) = ''1'' then

v_pos := v_pos + 32;

else

v_pos := v_pos + 8;

end if;

end loop;

return substring(p_tree_key, 1, v_pos - 1);

end;'

LANGUAGE 'plpgsql' with (iscachable, isstrict)

;

CREATE OR REPLACE FUNCTION tree_root_key ( bit varying )

RETURNS varbit

AS '

-- Return the tree_sortkey for the root node of the node with the

-- given tree_sortkey.

declare

p_tree_key alias for ;

begin

if substring(p_tree_key, 1, 1) = ''1'' then

return substring(p_tree_key, 1, 32);

else

return substring(p_tree_key, 1, 8);

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable, isstrict)

;

CREATE OR REPLACE FUNCTION tree_leaf_key_to_int ( bit varying )

RETURNS int4

AS '

-- Convert the bitstring for the last, or leaf, node represented by this key

-- to an integer.

declare

p_tree_key alias for ;

v_leaf_pos integer default 1;

v_pos integer default 1;

begin

-- Find the leaf key first

while v_pos < length(p_tree_key) loop

v_leaf_pos := v_pos;

if substring(p_tree_key, v_pos, 1) = ''1'' then

v_pos := v_pos + 32;

else

v_pos := v_pos + 8;

end if;

end loop;

if substring(p_tree_key, v_leaf_pos, 1) = ''1'' then

return bittoint4(substring(p_tree_key, v_leaf_pos + 1, 31));

else

return bittoint4(substring(p_tree_key, v_leaf_pos, 8));

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable, isstrict)

;

CREATE OR REPLACE FUNCTION tree_next_key ( bit varying, integer )

RETURNS varbit

AS '

-- Create a new child of the given key with a leaf key number one greater than

-- the child value parameter. If the child value parameter is null, make the

-- child the first child of the parent.

declare

p_parent_key alias for ;

p_child_value alias for ;

v_child_value integer;

begin

if p_child_value is null then

v_child_value := 0;

else

v_child_value := p_child_value + 1;

end if;

if p_parent_key is null then

return int_to_tree_key(v_child_value);

else

return p_parent_key || int_to_tree_key(v_child_value);

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable)

;

CREATE OR REPLACE FUNCTION tree_left ( bit varying )

RETURNS varbit

AS '

-- Create a key less than or equal to that of any child of the

-- current key.

declare

key alias for ;

begin

if key is null then

return ''X00'';

else

return key || ''X00'';

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable)

;

CREATE OR REPLACE FUNCTION tree_right ( bit varying )

RETURNS varbit

AS '

-- Create a key greater or equal to that of any child of the current key.

-- Used in BETWEEN expressions to select the subtree rooted at the given

-- key.

declare

key alias for ;

begin

if key is null then

return ''XFFFFFFFF'';

else

return key || ''XFFFFFFFF'';

end if;

end;'

LANGUAGE 'plpgsql' with (iscachable)

;

CREATE OR REPLACE FUNCTION tree_level ( bit varying )

RETURNS int4

AS '

-- Return the tree level of the given key. The root level is defined

-- to be at level one.

declare

p_tree_key alias for ;

v_pos integer;

v_level integer;

begin

if p_tree_key is null then

return 0;

end if;

v_pos := 1;

v_level := 0;

while v_pos <= length(p_tree_key) loop

v_level := v_level + 1;

if substring(p_tree_key, v_pos, 1) = ''1'' then

v_pos := v_pos + 32;

else

v_pos := v_pos + 8;

end if;

end loop;

return v_level;

end;'

LANGUAGE 'plpgsql' with (iscachable)

;

CREATE OR REPLACE FUNCTION tree_ancestor_p ( bit varying, bit varying )

RETURNS bool

AS '

declare

p_potential_ancestor alias for ;

p_potential_child alias for ;

begin

return position(p_potential_ancestor in p_potential_child) = 1;

end;'

LANGUAGE 'plpgsql' with (iscachable)

;

CREATE OR REPLACE FUNCTION create_tree_ancestor_keys() returns boolean as '

-- PG 7.1 does not allow recursive SQL functions, but David Walker figured out how to

-- get around this with a truly inspired hack he posted to the OpenACS 4 Design Forum.

-- His solution involves a general "create and replace function" function written in

-- Tcl.

-- Rather than use the general solution I have just hacked up a PL/pgSQL function to

-- create the one recursive function we need: tree_ancestor_keys(varbit, integer).

-- PG 7.2 still does not allow recursive SQL functions during CREATE, but you can

-- fool it easily with CREATE OR REPLACE, a new feature in this version. Perhaps

-- someday the PG development group will see the light and just let us CREATE such

-- functions.

-- tree_ancestor_keys(varbit, integer) returns the set of ancestor keys starting at

-- the level passed in as the second parameter down to the key passed in as the first

-- This function should probably only be called from its overloaded cousin

-- tree_ancestor_keys(varbit), which returns the set of tree_sortkeys for all of the

-- ancestors of the given tree_sortkey...

begin

-- create tree_ancestor_keys with a dummy body

execute ''create function tree_ancestor_keys(varbit, integer) returns setof varbit as ''''

select

'''' language ''''sql'''' '';

if version() like ''%7.1%'' then

-- create another function with the body we want

execute ''create function __tree_ancestor_keys(varbit, integer) returns setof varbit as ''''

select tree_ancestor_key(, )

union

select tree_ancestor_keys(, + 1)

where < tree_level()

'''' language ''''sql'''' with (isstrict) '';

-- replace the body for tree_ancestor_keys with the body we want. Slick, eh?

update pg_proc

set prosrc = hack.prosrc, probin = hack.probin

from (select prosrc, probin

from pg_proc

where proname = ''__tree_ancestor_keys'') hack

where proname = ''tree_ancestor_keys'';

execute ''drop function __tree_ancestor_keys(varbit, integer)'';

else

-- The bootstrap installer has made certain that we are running a version >= 7.1 so it is safe

-- at this point to assume create or replace is supported.

execute ''create or replace function tree_ancestor_keys(varbit, integer) returns setof varbit as ''''

select tree_ancestor_key(, )

union

select tree_ancestor_keys(, + 1)

where < tree_level()

'''' language ''''sql'''' with (isstrict) '';

end if;

return true;

end;' language 'plpgsql';

select create_tree_ancestor_keys();

drop function create_tree_ancestor_keys();

CREATE OR REPLACE FUNCTION tree_ancestor_keys ( bit varying )

RETURNS varbit

AS '

-- Return the set of tree_sortkeys for all of the ancestors of the given

-- tree_sortkey ancestors.

-- Here is an example on acs_objects:

-- select o.*

-- from acs_objects o,

-- (select tree_ancestor_keys(acs_objects_get_tree_sortkey(:object_id)) as tree_sortkey) parents

-- where o.tree_sortkey = parents.tree_sortkey;

-- This query will use the index on tree_sortkey to scan acs_objects. The function to grab

-- the tree_sortkey for the node is necessary (and must be defined for each table that uses

-- our hierarchical query scheme) to avoid restrictions on the use of SQL functions that

-- return sets.

-- if you only want the ancestors for a node within a given subtree, do something like this and

-- cross your fingers that Postgres will figure out whether the join on parent or the root is

-- more restrictive and do the right one first:

-- select o.*

-- from acs_objects o,

-- (select tree_sortkey from acs_objects where object_id = :root_id) as root

-- (select tree_ancestor_keys(acs_objects_get_tree_sortkey(:object_id)) as tree_sortkey) parents

-- where o.tree_sortkey = parents.tree_sortkey

-- and o.tree_sortkey >= root.tree_sortkey;

-- DO NOT BE TEMPTED TO REWRITE THE ABOVE QUERIES LIKE THIS:

-- select *

-- from acs_objects

-- where object_id in (select tree_ancestor_keys(object_id)

-- from acs_objects

-- where object_id = :object_id);

-- This is more readable and is certainly cleaner BUT WILL NOT USE THE INDEX ON TREE_SORTKEY

-- when scanning the acs_objects instance referred to by the left operand of the "in" operator. Given

-- that acs_objects will become HUGE on real systems the resulting sequential scan would cripple

-- performance.

-- WARNING: subselects in where clauses that call this function and join on an outer table appear

-- to reliably kill PG 7.1.2, at least if "exists" is involved. PG 7.2 doesn''t die on my test

-- case, so it appears to have been fixed.

select tree_ancestor_keys(, 1)

'

LANGUAGE 'sql' with (isstrict)

;

CREATE OR REPLACE FUNCTION category_insert_tr ( )

RETURNS OPAQUE

AS '

declare

v_parent_sk varbit default null;

v_max_value integer;

begin

select max(tree_leaf_key_to_int(sortkey)) into v_max_value

from category

where parent_id = new.parent_id;

select sortkey into v_parent_sk

from category

where category_id = new.parent_id;

new.sortkey := tree_next_key(v_parent_sk ,v_max_value);

return new;

end;'

LANGUAGE 'plpgsql'

;

CREATE OR REPLACE FUNCTION category_update_tr ( )

RETURNS OPAQUE

AS '

declare

v_parent_sk varbit default null;

v_max_value integer;

v_rec record;

clr_keys_p boolean default ''t'';

begin

if new.category_id = old.category_id and

((new.parent_id = old.parent_id) or

(new.parent_id is null and old.parent_id is null)) then

return new;

end if;

for v_rec in select category_id, parent_id

from category

where sortkey between new.sortkey and tree_right(new.sortkey)

order by sortkey

LOOP

if clr_keys_p then

update category set sortkey = null

where sortkey between new.sortkey and tree_right(new.sortkey);

clr_keys_p := ''f'';

end if;

select max(tree_leaf_key_to_int(sortkey)) into v_max_value

from category

where parent_id = v_rec.parent_id;

select sortkey into v_parent_sk

from category

where category_id = v_rec.parent_id;

update category

set sortkey = tree_next_key(v_parent_sk, v_max_value)

where category_id = v_rec.category_id;

end LOOP;

return new;

end;'

LANGUAGE 'plpgsql'

;

create trigger category_update_tr after update on category

for each row execute procedure category_update_tr ( );

create trigger category_insert_tr before insert on category

for each row execute procedure category_insert_tr ( );

===================SQL 끝 =================

테스트....

                          version
-----------------------------------------------------------
 PostgreSQL 7.2 on i686-pc-linux-gnu, compiled by GCC 2.96

 category_id | category_name | parent_id |         sortkey
-------------+---------------+-----------+--------------------------
                 1 | 대한민국          |                | 00000000
                 2 | 서울                |         1 | 0000000000000000
                 3 | 부산                |         1 | 0000000000000001
                 4 | 대전                |         1 | 0000000000000010
                 5 | 대구                |         1 | 0000000000000011
                 6 | 광주                |         1 | 0000000000000100
                 7 | 인천                |         1 | 0000000000000101
                 8 | 울산                |         1 | 0000000000000110
                 9 | 중구                |         8 | 000000000000011000000000
               10 | 남구                |         8 | 000000000000011000000001
               11 | 동구                |         8 | 000000000000011000000010
               12 | 북구                |         8 | 000000000000011000000011
               13 | 종로구             |         2 | 000000000000000000000000
               14 | 강남구             |         2 | 000000000000000000000001
               15 | 강서구             |         2 | 000000000000000000000010
               16 | 강북구             |         2 | 000000000000000000000011

 category_id | category_name | parent_id |         sortkey
-------------+---------------+-----------+--------------------------
                 1 | 대한민국         |           | 00000000
                 2 | 서울               |         1 | 0000000000000000
               13 | 종로구            |         2 | 000000000000000000000000
               14 | 강남구            |         2 | 000000000000000000000001
               15 | 강서구            |         2 | 000000000000000000000010
               16 | 강북구            |         2 | 000000000000000000000011
                3 | 부산               |         1 | 0000000000000001
                4 | 대전               |         1 | 0000000000000010
                5 | 대구               |         1 | 0000000000000011
                6 | 광주               |         1 | 0000000000000100
                7 | 인천               |         1 | 0000000000000101
                8 | 울산               |         1 | 0000000000000110
                9 | 중구               |         8 | 000000000000011000000000
               10 | 남구              |         8 | 000000000000011000000001
               11 | 동구              |         8 | 000000000000011000000010
               12 | 북구              |         8 | 000000000000011000000011