Generic Tree Manager

Generic Tree Manager (Draft)

by Aram Kananov on Jan 2001

Introduction

Many kind of data naturally represented as "tree". As good example see "User Profiling and Site Wide categorization" Module for ACS 3.x. And regardless of place there they used, they have common actions like: add node, get children, delete node and so on.

Idea

In fact most of the hierarchical structure implementations in various applications have the same logical methods for manipulate the tree structure data. Using it, I'm trying create some flexible toolset to manipulate them with single API. Also I solved some scalability problems which are exist in User Profiling and Site Wide categorization" Module for ACS 3.x.

Requirements

The module should store metadata about the trees.
Module should provide single API for defining and manupulating tree metadata
Module should provide single API for manupaleting particular tree instance (add node, move node, delete node and so on)
It should be possible to group logicaly related trees to the single tree type (for example various category dimensions for site wide categorisation)
It should be possible to set as node lables of tree intances of various object types.
It should be possible to store differenet labels for the same node(for example english and german lables).
It sould be possible to map the same label into different nodes (for exaple munich as child of "German Cities" and child of "AD Office Locations" - logical multiparenting)
It sould be possible to get unique path to the root nodes of the child node
Sorting should be supported
Different sorting should be supported for the same tree
Nested set model of representing trees should be supported (useful for aggregation)
...

Logical Design

Tree Type is group of trees with same storing, labeling and sorting characteristics.
Tree Instance is the instance of the particular tree type.
Node is given node of tree instance
Label Instance is String value for given node. It's posible to set many labels for the same node (Label Instances)
Label Function is stored function which is used to get particular Label Instance for given node
Sorting Condition is order of sorting nodes according appropriate Label Function
Default Function is Label Function wich is used for geting default Label and Sorting Condition

Physical Design

I've collected some technics about using Hierarchical Trees in Oracle, and wrote small article "Hierarchical Queries (for nerds)". I've used some tricks in this module.Please read it before continiue reading this doc.

Metadata data model

Generic_tree_types table stores meta data about a tree type. All instances of a tree type are stored in the same database table. Each tree type can have a set of Oracle functions for retrieving information (typically name) of the application data that is in the tree.

Column tree_struct_table is the name of the database table where data about tree structure should be stored.
Column generic_tree_types.generated_p is indicates if the database table for storing the tree structure has been created';

Generic_tree_functions is table for storing Oracle functions belonging to a certain tree type. These functions are used to retrieve node labels or other application data structured in the tree.

Column generic_tree_functions.function_no is an unique id for the function for quick look up.
Column generic_tree_functions.ind_expr is function calling syntax (for example - "substr(get_category_name(object_id),1,50)")
Column generic_tree_functions.index_name is name of oracle index which is use this function for quick retrieval.

Generic_trees is Table for storing meta data about tree instances of different types. The actual tree structure is stored in a table (with the name specified in generic_tree_types) generated by the generic tree API.

Column generic_trees.support_nested_set_p - Should tree support nested set model?
Column generic_trees.default_function_no is default function for given tree instance.
Column root_node_id is node id of root node for given tree instance

Metadata API

package generic_tree_type provide function for manupulating tree types

-- create new tree type
FUNCTION new ( 
        type_id         in generic_tree_types.type_id%TYPE	            default null, 
	owner_id            in generic_tree_types.owner_id%TYPE             default null, 
	type_name	    in generic_tree_types.type_name%TYPE, 
	pretty_name	    in generic_tree_types.pretty_name%TYPE, 
	pretty_plural	    in generic_tree_types.pretty_plural%TYPE, 
	tree_struct_table   in generic_tree_types.tree_struct_table%TYPE, 
	default_function_no in generic_tree_types.default_function_no%TYPE  default null,
	creation_date       in acs_objects.creation_date%TYPE		    default sysdate, 
	creation_user       in acs_objects.creation_user%TYPE		    default null, 
	creation_ip         in acs_objects.creation_ip%TYPE		    default null, 
	context_id          in acs_objects.context_id%TYPE		    default null
    ) RETURN generic_tree_types.type_id%TYPE
    ;

-- get tree type name
FUNCTION name (
        object_id           in acs_objects.object_id%TYPE
    ) return varchar2;

-- delete tree type
PROCEDURE delete ( 
	type_id         in acs_objects.object_id%TYPE 
    );

-- check db for possible conflicts before calling generate_db_objects function
FUNCTION check_before_create (
	p_type_id       generic_tree_types.type_id%TYPE,
	error_descr	    in out varchar2
    ) RETURN integer;

-- generate nessesary objects in db for tree type
FUNCTION generate_db_objects (
	p_type_id       generic_tree_types.type_id%TYPE,
	error_descr	    in out varchar2
    ) RETURN integer;

-- drop db objects for tree type
FUNCTION drop_db_objects (
        p_type_id       generic_tree_types.type_id%TYPE,
	errors_descr in out varchar2
    ) RETURN integer;

Tree instance data model

Typically table design of tree instance storage table looks like:

Table for storing the actual tree structure is stored in a table generated by the generic tree API.

Column object_id is object id of node label
Columns left_ind and right_ind are used for supporting nested set model.
Column root_node_id is node id of root node for given tree instance

Tree instance API

Package generic_tree

 
-- Create new tree instance
FUNCTION new ( 
        tree_id		    in generic_trees.tree_id%TYPE		 default null, 
	type_id		    in generic_tree_types.type_id%TYPE,
	tree_name	    in varchar2,
	description	    in varchar2,
	default_function_no in generic_trees.default_function_no%TYPE default null,
	creation_date       in acs_objects.creation_date%TYPE		 default sysdate, 
	creation_user       in acs_objects.creation_user%TYPE		 default null, 
	creation_ip         in acs_objects.creation_ip%TYPE		 default null, 
	context_id          in acs_objects.context_id%TYPE		 default null
    ) RETURN generic_trees.tree_id%TYPE
    ;

-- get instance name
FUNCTION name (
        object_id           in acs_objects.object_id%TYPE
    ) return varchar2;

-- delete tree instance
PROCEDURE delete ( 
	tree_id         in acs_objects.object_id%TYPE 
    );

-- add new node to the tree instance
FUNCTION add_node (
	p_node_id integer default null,
	p_tree_id in generic_trees.tree_id%TYPE, 
	p_object_id  in acs_objects.object_id%TYPE, 
	p_parent_node_id integer
    )	RETURN integer
    ;

-- delete node from tree instance
PROCEDURE del_node (
	p_node_id integer,
	p_tree_id in generic_trees.tree_id%TYPE, 
	p_delete_childs boolean default false 
    )	
    ;

-- copy tree/part of tree structure to the same/another tree instance
PROCEDURE copy_tree (
	      source_tree integer, dest_tree integer, source_node_id integer, dest_parent_node_id integer, depth integer default null
    );

-- move tree/part of tree structure to the same/another tree instance
PROCEDURE move_tree (source_tree integer, dest_tree integer, source_node_id integer, dest_parent_node_id integer)
;

-- index lef_ind and right index columns (nested set model support)
PROCEDURE nested_on (p_tree_id integer);