Andy Kramek

Modeling Hierarchies (Part 2)

In the last article I gave the theoretical background to using mapping to model complex hierarchies. In this article I will work through an example that is intended to illustrate how the use of the mapping approach can solve some of the key issues associated with managing hierarchies in an application environment.

For the purpose of this example consider the position of a sales representative, named Amanda Barry, who works out of the Massillon plant for a Company which has plants in various parts of the country. She is actually a member of  three separate hierarchies simultaneously. These are:

• Sales Team
• Plant Organization
• Customer

We’ll examine each in turn and model them accordingly

The Sales Team hierarchy

The company Sales Force is organized into teams which are based in geographic territories. The hierarchy describing this structure is shown at Figure 1, Note that these nodes represent not only logical groupings, but in some case are also actual positions within the company and have people associated with them. For example, Amanda is a member of the “Great Lakes” team, which has a Manager (Charlie Davis). But the Great Lakes team is considered a part of the “Northern Sub-Division” which is merely a convenient way of sub-dividing the four teams which comprise the Eastern Division . There is actually no real person associated with the “Northern Sub-Division” Node.

To model this structure will require a minimum of two tables, as described above, one for the Node Definitions, and one for the Mapping data (the rip table). Since we already know that we will want to define multiple hierarchies, we will add a third table to the structure, to allow us to categorize nodes. The structure we will use is at Figure 2:

Figure 2: Basic table structure for mapping hierarchies

To map the structure we require entries in these tables as shown at Table 2

Now we can map the structure to the structure table by tracing the paths. Once all of the paths have been defined the data can be added to the hierarchy (the Node PKs are shown below the descriptions in Figure 1). The actual data is at Table 2.

NOTE: We use the “*” character not only to separate, but also to terminate, the key references in the rip field. The reason is so that we can query this field later and avoid issues associated with partial matches on key references when querying the table using the LIKE operator on the rip field.
Consider the following pair of rip fields: “10*20*30” and “10*20*300”.
Clearly they are not referring to the same node but if we were to query where the value is LIKE “10*20*30%” we would get both. By using a termination character we avoid this problem.

The final task is to link our people to the appropriate node in the hierarchy. For the purpose of this illustration we are not concerned with how the Employee data is stored, but simply assume that somewhere there are tables that include a key value for each employee and the usual associated information (Name, Title, Date Joined etc). This data is represented by the “Person” table in Figure 3.

We use an allocation table to allow us to link a single employee to different nodes (we already know that Amanda is a member of three hierarchies, so she will have to be associated with at least three nodes, one in each hierarchy).

The crucial point to notice is that this allocation table links people to the structure table, not to the node!

The reason for this is simply that the node table is only a look-up which allows us to give a meaningful name to a node in the hierarchy. It has no significance whatsoever and indeed, the same name may be used in many places in different hierarchies (how many “Admin” departments are there in the world?). If we were to attach people directly to the node record we would require a separate node record for each individual occurrence of a node in a hierarchy, thereby making the relationship between a node and its structure one-to-one, forcing us back into a very rigid structure.

Now we can add the necessary records to the allocation table for the people that we know about so far, plus the Vice President in Charge of Sales Nationally (Jane Kingsland) and the head of the Eastern Division (Martin Niles) and the manager and a sales representative for the Mid-West team :

What does this give us?

It now allows us to create static views that query the hierarchy and return matching members. Here are the necessary definitions for two views. The first returns the rip field associated with a given node description:

IF EXISTS (SELECT * FROM sysobjects WHERE id = object_id('v_GetRip') and sysstat & 0xf = 2)
  DROP VIEW v_GetRip
GO

CREATE VIEW v_GetRip AS
 SELECT NN.node_pk, NN.node_dsc, RTRIM( RF.node_path) + '%' AS rip_field
   FROM node_stru RF 
        INNER JOIN node_def NN ON RF.node_fk = NN.node_pk

A simple query is now all that is needed to return the appropriate rip field mask that defines the starting point for data selection. The important thing to recognize is that this ‘mask’ allows to extract information from any level of the hierarchy without the need to know anything about the level or the relationships between the nodes. For example:

SELECT rip_field FROM v_getrip WHERE node_dsc = ‘Great Lakes’
RETURNS “1*2*4*9*%”

while

SELECT rip_field FROM v_getrip WHERE node_dsc LIKE ‘Mid%’
RETURNS “1*2*4*8*%”

This view can then be combined with another static view to return a list of people who are members of whatever node we wish to query by:

IF EXISTS (SELECT * FROM sysobjects WHERE id = object_id('v_GetMembers') and sysstat & 0xf = 2)
  DROP VIEW v_GetMembers
GO

CREATE VIEW v_GetMembers AS
SELECT DISTINCT VR.node_dsc keyval, ND.node_pk, ND.node_dsc,PN.title_dsc, PN.fname_nme, PN.lname_nme
  FROM v_GetRip VR
       INNER JOIN ( node_stru NS INNER JOIN node_def ND ON NS.node_fk = ND.node_pk )
            ON NS.node_path LIKE VR.rip_field
       LEFT OUTER JOIN node_psn_alloc AL ON AL.nodestru_fk = NS.nodestru_pk
       LEFT OUTER JOIN person PN ON PN.psn_pk = AL.psn_fk

Simple queries on this view return the list of people who qualify:

SELECT * FROM v_getmembers WHERE node_dsc = 'Great Lakes'
RETURNS
1 Great Lakes Sales Rep     Amanda Barry
2 Great Lakes Sales Manager Charlie       Davis

while

SELECT * FROM v_getmembers WHERE keyval = 'Mid-West'
RETURNS
Mid-West  8  Mid-West      Sales Manager Ellen  Franks
Mid-West  8  Mid-West      Sales Rep     George Harrison

and

SELECT * FROM v_getmembers WHERE node_dsc = 'Northern Sub-Division'
RETURNS
Northern Sub-Division      4      Northern Sub-Division      NULL   NULL   NULL
Northern Sub-Division      8      Mid-West      Sales Manager Ellen  Franks
Northern Sub-Division      8      Mid-West      Sales Rep     George Harrison
Northern Sub-Division      9      Great Lakes   Sales Manager Charlie       Davis
Northern Sub-Division      9      Great Lakes   Sales Rep     Amanda Barry

Any query relating to People is now a simple matter. Assuming that we have sales information related to the ID of the person who made the sale, we can get the total sales for any node in the hierarchy by simply summing the sales associated with the list of people who are related to that node:

SELECT SUM( sales)  FROM sales_data WHERE sales_person_id IN 
   (SELECT psn_pk FROM v_getmembers WHERE node_desc = ‘Great Lakes’ )

The same method can be used to extract the members of a Sales Team

SELECT name FROM emp_data WHERE person_pk IN

   (SELECT psn_pk FROM v_getmembers WHERE node_desc = ‘Great Lakes’ )

The Plant Hierarchy

The second hierarchy of which our notional person is a member is the “plant hierarchy”, part of which is  illustrated in Figure 4.  

We can simply add the data for this hierarchy to our existing tables (Table 4) in exactly the same way as for the Sales Organization detailed above. In this case the Node Category will be "2" and the various plants are added as new nodes – their structure being added to the Node_Stru table as before: 

Now we need to associate the Sales Representatives with the plants which they represent (Table 5). In this case only Amanda Barry (Massillon) and George Harrison (Columbus) are directly associated with plants, so only two new entries are required in the allocation table (obviously there would be other people associated with the plants hierarchy but the objective here is to focus only on the Sales side of the business): 

Our existing views, of course, will work just as well with this hierarchy as with the Sales hierarchy. Thus:

SELECT * FROM v_getmembers WHERE keyval LIKE 'North Ohio%'
RETURNS
North Ohio 15 North Ohio    NULL   NULL   NULL   NULL
North Ohio 17 Cleveland     NULL   NULL   NULL   NULL
North Ohio 18 Massillon     Sales Rep     Amanda Barry  1

Notice that we can now sum our sales by any node in either hierarchy using the same basic query. To get all the sales for all Ohio Plants the query is simply:

SELECT SUM( sales )  FROM sales_data WHERE sales_person_id IN 
     (SELECT psn_pk FROM v_getmembers WHERE keyval = ‘Ohio Plants’ )

and to get a list of representatives who are working out of any given plant, we use exactly the same query as we used to get a sales team:

SELECT SUM( sales )  FROM sales_data WHERE sales_person_id IN 
     (SELECT psn_pk FROM v_getmembers WHERE keyval = ‘Columbus’ )

The Customer Hierarchy

Adding a customer hierarchy is as simple as adding the plant hierarchy. Figure 5 shows a partial hierarchy for a large customer group and shows the entries for the Node and Node_Stru tables directly on the diagram:

One more thing that we need to do to accommodate this new hierarchy is to link our sales people to the appropriate node in the hierarchy. For the sake of illustration, we are mapping our Sales Reps to the lowest level of this hierarchy (Amanda Barry to 'NE Ohio [Node 24]' and George Harrison to SE Ohio[Node 25]), the Division Head to the Region level (Martin Niles to NE US [Node 22]) and our VP to National Level  

The net result is that the VP (Jane Kingsland) is now associated with two structures; first, she is attached to the organization at the National Sales node, and second, to the customer organization at the "Wendy's USA" node. Similarly other members participate in multiple structures, so that our friend Amanda is actually in three. She is associated with the sales tree at the 'Great Lakes' level, with plants at 'Massillon' and customers at 'SE Ohio'. However, no matter how many structures an entity is associated with, we still only ever have one record in the person table and one record in the node definition table!

Maintaining the structure

As can be seen, using the approach detailed here it is very easy to map, and to retrieve the data associated with, any number of hierarchies. By defining simple views to hide the complexity of the actual structure it is possible to support any desired user interface and even to dynamically add and delete entire hierarchies. The structures illustrated here show the bare minimum of information that is necessary to manage the data but do show the principles that underlie the approach. An obvious refinement to the Node Structure table is to add a “level” key, to permit data retrieval across all nodes that lie at a specific level of a hierarchy (for example, this would make implementing a TreeView to display the contents of a hierarchy very easy).

By modifying the node structure table so that it includes an additional foreign key for the parent node, and the level, the structure can be maintained using triggers that, when inserting a new record, generate the rip field and even level automatically based upon the rip field and level of the node to which the new record is being related (Figure 6).  

The resulting table, for all hierarchies is shown at Table 7:

The T-SQL code for the insert trigger is very simple:

To return the data in a form suitable for display in a treeview we need a little more code, but not very much. Here is a stored procedure that accepts either the PK of a node, or the actual Node Description and uses the rip field to get the nodes, and sequence them correctly, so that they can be displayed.

Calling this procedure for "Ohio Plants" returns the data shown in Table 8. Note that the "Has Child" and "Is Leaf" flags are added dynamically. The first is used to indicate that a node has children, the second to indicate that the node is the last node at the current level. These are useful when generating a tree by parsing the data into an array or other structure used by the UI development tool. The PKs are included so that any modifications made can be sent back to the database by referencing the relevant primary key. 

Unlike the Left-Right numbering approach, changes to hierarchies modeled using a rip field affect only those records that are directly involved. There is no need to reconstruct the entire hierarchy whenever a node is added, deleted or moved. All that is necessary is to change any records that include the affected node, replacing the relevant portion of the rip field with the amended version. 

For example, if we were to disband the Southern Sub Division (see Figure 1) and move its “Central” sales team to the Northern Sub Division and the “South West” team to the Western Division, a total of three records in the Node Structure table are affected (Table 9). The process is simple:

• Retrieve the ripfield mask for the node to be removed (OldStru)
• Retrieve the mask for the node to which all child nodes are to be re-assigned (NewStru)
• Update the structure table replacing all occurrences of "OldStru" with "NewStru"
• Delete the one record where the rip field is exactly equal to "OldStru"

Obviously, any tables which included references to the deleted record would also have to be updated, but the key point here is that nothing else has to change. All data which previously aggregated to the “Southern Sub” group is now going to be aggregated into either the “Northern” or “Western” divisions.

Conclusion

The mapping approach described here provides the most flexible and easily maintained method of modeling hierarchical data of any type. By separating structural information from definition the retrieval of hierarchical information is simplified to the point where simple SQL can be used directly instead of requiring table queries, recursive “Tree-Walking” operations or the complex and inflexible left-right numbering which are the only viable alternatives.

NOTE: The sample SQL2005 database used in this article is attached as a zip file. Simply restore the database to your local SQL 2005 instance to see how all this works in practice.