Thick Database Tree Widget

Dr. Paul Dorsey

Dulcian, Inc.

July 12, 2006

With sincere apologies to Joyce Kilmer

But if Ogden Nash can do it, so can I.

I think that I shall never see

a thing as tough to model as a tree.

A tree whose hungry nodes are queried

Against the users' flowing needs;

A tree that looks to change all day,

And expands her branching folders just to play;

A tree that may in future wear

Completed requirements in her hair;

Upon whose bosom my brain has lain;

Which will ultimately die from strain.

Models are made by fools like me,

But only users can spec a tree.

----------------------------------------

Everyone has seen tree controls in applications. Those of us who have tried to code them have seen relatively simple looking structures balloon into significant programming efforts requiring 10,000-20,000 lines of code.

Use of a tree widget for screen navigation can greatly reduce the number of screens required for an application. Consider that the single tree control replaces most of the browse screens in an application. If a tree control could be easily built, (or even better-- generated), then the overall complexity of the application could be greatly reduced. As long as the number of objects required in the tree is small, the tree control can be quite easy to design and build.

Tree controls lend themselves perfectly to a thick database approach. The tree can be completely controlled by the database and the user interface (UI) can be kept very thin. The thick database approach is usually only discussed in papers in relatively general terms. This paper will define the exact implementation details for handling one of the most complex portions of the UI as well as describe the technology-independent APIs to define a tree control.

Why use a thick database approach for a tree control?

The tree can be coded in a variety of ways. There is no reason why it must be built as a thick database object; however, there are several reasons that it should be:

A tree is usually a database intensive object. Since each node can be a separate query, a simple tree refresh might require many round trips.
The queries populating the tree nodes may be very complex and are probably best handled in the database.
Changes to the tree can be affected without redeploying to the application server.
Coding the tree as a technology-independent set of APIs divides the problem into logic and presentation areas and simplifies development

Tree APIs

All interaction from the UI to the tree engine is done through APIs. The engine responds with XML files that tell the UI how to populate or alter the tree.

All calls to the tree are made to the tree library package. The various calls are discussed in turn.

Initial population of the tree

The initial population of the tree occurs when the application first wants to display the application or when there is a requirement for a full tree refresh. The command to do this is:

Function API$Tree.PopulateNew(

i_treeType varchar2,

i_session varchar2,

i_XMLParams CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated. A single application can have multiple trees that are used in different contexts. Each tree is managed separately.

i_session is the session identifier. This must be unique to the user’s login session. It is assumed that the session identifier is established at login and remains statically persistent throughout the life of the session. The database will store persistent information about the tree so the engine needs to know who the user is in order to be able to establish session context.

i_XMLParams allow the UI to pass additional parameters that may affect the population of the tree. These parameters are passed as an XML text file.

Responses to the UI from the tree engine from this and all other API calls are discussed in the Tree Engine Responses section.

Node Expand/Refresh

The initial population of the tree may not populate all nodes. For performance purposes, some nodes may only be populated on demand or may need to be refreshed each time they are accessed. The command to expand a node is as follows:

Function API$Tree.NodeExpand(

i_treeType varchar2,

i_session varchar2,

i_node number,

i_XMLParams CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated.

i_session is the session identifier.

i_node is the ID of the node being expanded. This ID is passed to the UI when the node is initially populated.

i_XMLParams allow the UI to pass additional parameters.

Get Menu

When the user right-clicks the tree node, there may be a set of menu options presented.

The initial population of the tree may not populate all menu nodes. For performance purposes, some menu nodes may only be populated on demand or may need to be refreshed each time they are accessed. The command to retrieve the menu alternatives for a node is as follows:

Function API$Tree.GetMenu(

i_treeType varchar2,

i_session varchar2,

i_node number,

i_XMLParams CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated.

i_session is the session identifier.

i_node is the ID of the node for which the menu is being retrieved.

i_XMLParams allow the UI to pass additional parameters that may affect the menu items returned.

Select Menu Item

When the user selects a menu item, the tree engine may need to be notified.

The command to notify the engine is:

Function API$Tree.SelectMenuItem(

i_treeType varchar2,

i_session varchar2,

i_node number,

i_XMLParams CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated.

i_session is the session identifier.

i_node is the ID of the menu item node.

i_XMLParams allow the UI to pass additional parameters that may affect the menu items returned.

Node Actions Complete

There may have been actions that the UI had to execute as a result of performing some operations on the tree (for example, clicking a menu item). When those actions are complete, notifications to the tree engine may be necessary as shown here:

Function API$Tree.NodeActionsComplete(

i_treeType varchar2,

i_session varchar2,

i_node number,

i_XMLParams CLOB := null,

i_objectsModified CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated.

i_session is the session identifier.

i_node is the ID of the menu item node.

i_XMLParams allow the UI to pass additional parameters.

i_objectsModified are the OIDs and relevant properties of any objects potentially modified by actions that may require updates to the tree.

Tree Notification

If the UI updates objects that appear in the tree, the tree needs to be notified which objects have been updated so the tree can respond accordingly. The code to accomplish this is shown here:

Function API$Tree.TreeNotify(

i_treeType varchar2,

i_session varchar2,

i_objectsModified CLOB := null)

return varchar2;

i_treetype declares the type of tree to be populated.

i_session is the session identifier.

i_objectsModified are the OIDs and relevant properties of any objects potentially modified that may require updates to the tree.

Tree Engine Responses

Reponses to the tree are simple XML files. Each response type is described below.

Initial Population of Tree

The initial population of the tree involves passing the entire tree to the UI. Only the nodes will be populated on the initial load are sent to the UI. It is important to strike a balance between minimizing round trips to the database and managing the amount of data passed upon tree creation. If there are thousands of nodes in the tree, then it is impractical to refresh the entire tree. If the tree is too large to load without a significant impact on performance, initial population of the tree should only involve the nodes that will be used. Child nodes should only be populated on demand.

If there are hundreds of children under a single node, then the tree should be refactored, if possible. If nothing else, the tree can divide the children alphabetically and present an additional layer of nodes. For example a customer tree with hundreds of nodes might look like the following:

Customer

Aardvark

Aaron

…

Zebra

could be refactored to

Customer

A-M

Aardvark

Aaron

…

N-Z

…

Zebra

The tags for a new tree are as follows:

Tag: <actionSet>

Description: All actions passed to the UI use the <actionSet> tag as a wrapper.

Tag: <newTree>

Description:

Parameter	Datatype	Description
TreeType	Character	Type of tree being populated. Project-specific values.

Tag: <treeNode>

Description: A single node in a tree. Child of <newTree> or <treeNode>.

Parameter	Datatype	Description
ID	Number	Unique numeric identifier of node.
display	Text	Display value of node.
expandCode	Text	Tells UI how to handle node expansion. “cache” - query the child nodes once but don’t ever query them again. “query” – re-query child nodes every time they are requested to be displayed. “none” – there are no child nodes. Defaults to “none.”
menuCode	Text	Tells UI how to handle right-click requests for a menu. “cache” - query the menu nodes once but don’t ever query them again. “query” – re-query menu nodes every time they are requested to be displayed. “none” – there are no menu nodes. Defaults to “none.”
icon	Text	The icon file to use with the node. Defaults to “folder.”

Tag: <UIaction>

Description: An action to be executed by the UI when the node is clicked. Child of <treeNode>. May also be a child of <actionSet> indicating that the action should be executed immediately.

Parameter	Datatype	Description
ID	Number	ID of action that user interface will execute.
Others as needed	Varies	Parameter values needed by the UI to execute the action. For example: customerOID = “1234”

Example:

<treeNode ID=”1” display=”Customers” expandCode = “cache”

menuCode =”cache” >

<treeNode ID=”2” display=”Abel, Anne” expandCode = “cache”

menuCode =”cache” >

</treeNode>

<treeNode ID=”3” display=”Baker, Bob” expandCode = “cache”

menuCode =”cache” >

</treeNode>

</newTree>

</actionSet>

Modify Nodes

Actions may result in nodes being added, deleted, or modified in an existing tree.

Tag: <treeUpdate>

Description: Modify nodes in indicated tree.

Parameter	Datatype	Description
treeType	Character	Type of tree being populated. Project specific values.

Tag: <addTreeNode>

Description: Add node to specific place in tree. Child of <treeUpdate> or <addTreeNode>.

Parameter

Datatype

Description

childOfID or

addatabaseelowID

Number

Where to add the new node, either as the first child of the node “childOfID” or as a sibling node directly below the node “addatabaseelowID”.

See description.

All the same parameters as <treeNode>

Tag: <deleteTreeNode>

Description: Delete node from the tree. Also deletes indicated node and all child nodes.

Parameter	Datatype	Description
ID	Number	ID of node to delete.

Tag: <modifyTreeNode>

Description: Delete node from the tree. Also deletes indicated node and all child nodes.

Parameter	Datatype	Description
ID	Number	ID of node to be modified.
See description.		All the same parameters as <treeNode>. If a parameter is passed, it means to update the current node with the new value of the parameter.

Example:

<addTreeNode> ID=”3” display=”Charlie, Carrie”

expandCode = “cache” menuCode =”cache” >

</addtreeNode>

</treeUpdate>

</actionSet>

Tree Engine

The tree engine can be built in several different ways. The APIs define the behavior of the tree and effectively make the tree a black box to the UI. There are several techniques to make development of the tree engine easier.

Stateless Session Variables

Systems frequently include session-specific context variables. These values can be stored in a session table and each time a session event occurs, the session variables are read into memory. As the variables change, they are persistently updated back into the session table.

Store a copy of the tree

The database needs to know what each user’s tree looks like. An entire copy of each user tree is stored in the database. The database-side version of the tree can also store pieces of information that is not present on the client side. The table to store the server-side copy of the tree typically has many more columns than are necessary for the UI display, but are necessary to execute tree actions correctly.

The standard columns that should be expected are shown in Table 1:

Column	Data Type	Description
Session	Text	Session identifier
TreeType	Text	Type of tree
OID	Number	Physical primary key
RFK	Number	Recursive Foreign Key to indicate parent child relationship
ID	Number	ID of node that will be passed to UI (unique within session, treeType)
Display	Text	Display value of node
ICON	Text	Node icon for display
Type	Text	Type of node (Node, Menu item, Action)
ToolTip	Text	The displayed help tooltip for the node.

Table 1: Standard tree columns

Additional columns required for processing are shown in Table 2:

Column	Data Type	Description
ObjectType	Text	If a node represents some type of object from the database, what type of object is it?
ObjectOID	Number	Unique identifier for object of the type in previous column.
Order	Number	Display order of the node
Current_YN	Text	To identify whether or not this is the current node selected in the UI. Used to tell the UI to make a particular node current.
isNew	Boolean	Indicates whether or not the node is new and needs to be sent to the UI.

Table 2: Additional tree columns

Divide the code

In coding the tree, the following are the natural divisions in the code:

1) Main – The core main calling routines and their associated utilities.

2) UserPreferences – Supporting user preferences in the tree control.

3) Population – Initial population of the tree and expanding/refreshing of nodes.

4) TreeUpdates – Code to handle insert/update/delete of nodes

5) XML generation – Once the tree table has been modified, this code loops through the tree and generates the appropriate XML file.

If the tree is coded using this architecture at the outset, the code will stay nicely structured.

Actions are the challenge

The population of the tree is the easy part. The hardest part of the tree to code is responding to all the different types of actions.

A critical realization was that there are three distinct places where you have to consider what to do with a menu item:

1) When the engine sends the menu item to the UI initially, it can provide all of the information necessary to execute the required action. Alternatively, the engine can indicate that if a user clicks the menu item, the UI should ask the tree engine what to do. Only then would the tree engine pass back the action to execute.

2) When the menu item is selected, the UI can notify the engine. The engine can respond directly and/or can tell the UI to execute particular actions.

3) After the UI has completed any action(s), it can notify the tree engine that the action(s) are complete. The engine can then respond accordingly.

Conclusions

Building a tree widget can greatly reduce the complexity of an application. Using a thick database approach can provide excellent performance and reduce the overall amount of code required in the system.

One of the most striking success stories of the thick-database approach involved replacing a tree control written entirely in Java with a thick database tree control built using the architecture described in this paper. The refactored application reduced the amount of code by over 50% (several thousand lines of code) and, on average, performance improved by a factor of five.