Figure 1 - A typical hierarchical structure
In my many years as a software engineer I have often come across the requirement for a structure that will hold some sort of hierarchy, as represented in figure 1:
Figure 1 - A typical hierarchical structure
A typical example of a structure like this is an organisational hierarchy, as shown in figure 2:
Figure 2 - An Organisational hierarchy
A structure like this is typically implemented in an Entity-Relationship (E-R) diagram as shown in figure 3:
Figure 3 - A typical E-R diagram
This is perfectly legitimate, but it results in a rigid rather than a flexible structure. How easy would it be to modify this structure for any of the following?:
This type of structure, with its hierarchical nature, is also known as a TREE structure. A common example of this is the view provided by Windows Explorer which shows the hierarchy of folders and the files contained within those folders (although the structure is displayed from left-to-right rather than from top-to-bottom).
A tree contains objects known as NODES and LEAVES. These obey the following rules:
In Windows Explorer the NODES are equivalent to FOLDERS (previously known as DIRECTORIES) with the ROOT NODE representing a drive such as C: or D:, and the LEAVES are equivalent to FILES.
In figure 3 nodes exist at the COMPANY, DEPARTMENT and SECTION levels, with PERSON providing the leaves.
In designing my flexible structure I concentrated solely on the nodes. A leaf can be any other object within the database (eg: a person, a place, or a part), and linking a leaf to a node is as simple as storing the primary key of the node as a foreign key within the details of the leaf. There is no need to include the Tree Type or the Tree Level as these are obtained from the node details.
I wanted a table for NODES, and I needed to be able to relate a node to its parent node.
I needed to organise nodes into various LEVELS, each which its own customisable description.
I needed to have different sets of levels so that I could have more than one TYPE of structure.
This enabled me to produce the database design shown in figure 4:
Figure 4 - My database design
As a TREE_NODE can only have a single parent this can be dealt with by having a field called NODE_ID_SNR which contains the primary key (NODE_ID) of its parent.
These database tables have the following structure:
CREATE TABLE IF NOT EXISTS `tree_type` ( `tree_type_id` varchar(8) NOT NULL default '', `tree_type_desc` varchar(40) default NULL, PRIMARY KEY (`tree_type_id`) ) ENGINE=MyISAM;
| TREE_TYPE_ID | Entered by the user, not generated by the system. |
| TREE_TYPE_DESC | A free-form description. |
This table is subject to the following rules:
CREATE TABLE IF NOT EXISTS `tree_level` ( `tree_type_id` varchar(8) NOT NULL default '', `tree_level_id` tinyint(3) unsigned NOT NULL default '0', `tree_level_seq` tinyint(3) unsigned NOT NULL default '0', `tree_level_desc` varchar(40) default NULL, PRIMARY KEY (`tree_type_id`,`tree_level_id`) ) ENGINE=MyISAM;
| TREE_TYPE_ID | Foreign key to the TREE_TYPE table. |
| TREE_LEVEL_ID | Starts at 1 for each TREE_TYPE_ID, and is incremented by 1 for each new level. |
| TREE_LEVEL_SEQ | Initially starts off with the same value as TREE_LEVEL_ID, but this can be altered later if the levels have to be re-sequenced. |
| TREE_LEVEL_DESC | A free-form description. |
This table is subject to the following rules:
CREATE TABLE IF NOT EXISTS `tree_node` ( `node_id` smallint(5) unsigned NOT NULL default '0', `tree_type_id` varchar(8) default NULL, `tree_level_id` tinyint(3) unsigned NOT NULL default '0', `node_desc` varchar(40) default NULL, `node_id_snr` smallint(5) unsigned default NULL, `external_code` varchar(255) default NULL, PRIMARY KEY (`node_id`), KEY `tree_type_id` (`tree_type_id`,`tree_level_id`), KEY `node_id_snr` (`node_id_snr`) ) ENGINE=MyISAM;
| NODE_ID | Generated by the system as previous highest value plus one. |
| TREE_TYPE_ID | Foreign key to the TREE_TYPE and TREE_LEVEL tables. |
| TREE_LEVEL_ID | Foreign key to the TREE_LEVEL table |
| NODE_DESC | A free-form description. |
| NODE_ID_SNR | This identifies the NODE_ID of the parent of this node. If a node does not have a parent it is an orphan. |
| EXTERNAL_CODE | In my first implementation each node in the tree structure had an equivalent place in the structure of nominal codes in an external accounting system, so the identity of the corresponding nominal code was held here. This made it possible to export data from this system which could then be imported into the external accounting system without the need for any further translation from NODE_ID into NOMINAL_CODE. |
This table is subject to the following rules:
The following screen shots are part of the sample application which is described in A Sample PHP Application. This contain a link to run the application from my website, with another link where you can download all the source code.
First go into the List Tree Type screen by selecting the 'Tree Type' tab in the menu bar at the top of the screen. On a new database this will be empty.
Press the 'New' button in the navigation bar to go into the Insert Tree Type screen.
Other buttons are available for 'read', 'update', 'delete' and 'search'.
From within the List Tree Type screen select an entry and press the 'Tree Level' button to go into the List Tree Level screen.
This will initially be empty, but will show the Tree Type selected in the previous screen, which in this case is 'Organisation'. From here press the 'New' button on the navigation bar to go into the Insert Tree Level screen.
Again this will show the Tree Type we are dealing with, and will set both Level ID and Sequence Number to their next available values for this Tree Type.
Other buttons are available for 'read', 'update', 'delete' and 'search'.
From the List Tree Level screen select a level and press the 'Nodes' button on the navigation bar to go into the List Tree Node screen.
This shows the current Type as 'Organisation' and Level as 'Company'. From here press the 'New' button on the navigation bar to go into the Insert Tree Node screen.
Again the current Tree Type and Tree Level are displayed, and the value for NODE_ID is automatically generated. As each new node is created it does not have a parent, therefore is treated as an orphan.
Other buttons are available for 'read', 'update', 'delete' and 'search'.
From the List Tree Node screen select a node and press the 'Child Nodes' button on the navigation bar to go into the List Node Children screen.
This will list all the child nodes which have the selected node as its parent. To add more child nodes press the 'Link Children' button in the navigation bar to go to the Choose Orphan Node screen.
This will show details of the Level which is immediately below that of the selected parent node, and will list all orphan nodes which currently exist at that level. The 'New' button on the navigation bar can be pressed to create new nodes using the Insert Tree Node screen.
It is possible to select any number of orphan nodes on the current screen, and by pressing the 'Choose' button these will be updated to record the current parent node as their parent. The List Node Children screen will be redisplayed to reflect these updates.
Sometimes it may be necessary to trace a node's ancestry all the way to the top of the tree. From the List Tree Node screen select any desired node and press the 'Parent Nodes' button on the navigation bar to bring up the List Node Parentage screen.
This will show the selected node on the bottom line with its associated level number and description. Immediately above that will be the details for its parent, and its parent's parent and so on until an orphan node is reached. If a root node at level 1 is not shown on the top line it means that a link to a parent node has yet to be defined.
After a structure has been built it may become necessary to add a new Level. When this has been done the new Level will appear at the bottom of the hierarchy, but it will be possible to move it to another position by changing its sequence number. From the List Tree Level screen press the 'Update Seq No' button on the navigation bar to go into the Update TREE LEVEL SEQ screen.
For the selected Tree Type this will show the existing Levels sorted by their sequence numbers. It will then be possible to change the values to produce a new sequence. Note that the numbers must be sequential starting at 1 - there cannot be any duplicates or gaps.
If a new Level is inserted between two existing Levels then all links between those two Levels will be broken - all Nodes on the lower Level will be made into orphans.
Note that in this example a new Level called 'Group' has already been created and moved to the top of the sequence.
This activity is also possible with this design although the steps are a little more involved. This is what you do:
All these steps are required if you remove a level from the middle of the structure. If you remove just the top or bottom level then some of these steps will not be necessary.
Having built a complex tree structure is all well and good, but what is the best way to view it? With other user interfaces it is possible to use a Tree control or a Tree widget, but such a thing does not exist in HTML. I have seen examples where it has been done in javascript, but what happens if the user has javascript turned off? Is it possible to display a complete tree structure with HTML?
The answer is YES (if you are a clever cloggs like me). Not only am I achieving this with PHP, MySQL and HTML, but in the middle I am also using XML and XSL Transformations.
To view a structure go to the List Tree Type screen, select an entry, then press the 'Tree Structure' button in the navigation bar. This will bring up the List Tree Structure screen.
This starts by showing the root nodes for the selected structure. In front of each node may be one of these symbols:
will expand (show) this entry's child nodes.
will collapse (hide) this entry's child nodes.The EXPAND and COLLAPSE buttons at the bottom of the screen will operate on all nodes within the structure.
When a node is expaned the results will resemble the following:
This can continue until there are no children left to expand.
Although this design requires no more than three database tables you can see that it can cater for any number of structure types with any number of levels and any number of nodes. The ability to expand or contract existing structures without changing the database and without changing any software is another powerful benefit that is simply not possible with traditional, less flexible designs.
This software is contained within A Sample PHP Application which can either be run from my website, or you can download the source code and run it in your own environment.