Traversing the hierarchy – Part I

Traversing the hierarchy in the user data is a common requirement in most of the software products. You must have faced this requirement when you are:

a) building up a tree for navigation, or
b) whether you are recursively trying to get the employee hierarchy in a HR application module, or
c) whether you are establishing the tree structure for drugs in pharmaceutical inudstry, or
d) you are traversing the hierarchy of the different parts in a manufacturing industry.

Above are just some of the examples. There are many such places where one is required to write code to help with traversing the hierarchy from the top level down to the bottom. If you look at our previous post which explains how to design a M:N recursive relationship within a schema – that example pertains to the pharmaceutical industry. It shows how to model a recursive M:N relationship within an entity into physical tables. We will use that as an example to write up T-SQL (SQL Server) code to show how to traverse through that hierarchy. We will make use of CTEs (Common Table Expressions) which are also present in Oracle and DB2 LUW (with slight differences). In Oracle, one can also make use of the CONNECT BY clause in order to traverse the hierarchy – we will cover that in a later post.

Let us create the view which will have the CTE and the logic for recursion:

IF EXISTS
(
SELECT 1
FROM INFORMATION_SCHEMA.VIEWS
WHERE TABLE_NAME = ‘drug_hierarchy’
AND TABLE_SCHEMA = ‘dbo’
)
BEGIN
PRINT ‘View drug_hierarchy already exists…Dropping it and recreating’
DROP VIEW drug_hierarchy
END
ELSE
BEGIN
PRINT ‘Creating View drug_hierarchy’
END
GO
create view dbo.drug_hierarchy
as
with drug (traverse_path, drug_id, parent_drug_id, drug_name, level, lineage)
as (
select CONVERT(VARBINARY(MAX), drug_name) AS traverse_path,
drug_master_id,
Null as parent_drug_id,
drug_name,
1,
cast((‘/’ + str(drug_master_id,6,0) + ‘/’) as varchar(255))
from dbo.drug_master
where drug_master_id not in (select child_drug_id from dbo.drug_rltn)
/* the highest level in the tree*/

union all

select d.traverse_path + CONVERT(VARBINARY(MAX), dm2.drug_name) as traverse_path,
dr.child_drug_id,
dr.parent_drug_id,
dm2.drug_name,
d.level + 1,
cast((d.lineage + str(dm.drug_master_id,6,0) + ‘/’) as varchar(255))
from dbo.drug_master as dm
inner join dbo.drug_rltn as dr
on dm.drug_master_id = dr.parent_drug_id
inner join dbo.drug_master as dm2
on dr.child_drug_id = dm2.drug_master_id
inner join drug as d
on d.drug_id = dm.drug_master_id
)
select * from drug;
GO

The logic of the view is that we first get the top record in the DRUG_MASTER table as the first record (this one is not a child of any drug – if such a record does not exist, just create a dummy one in your table) and then we do a UNION ALL operation to the recursive tree and use the traverse path as an ordering mechanism so that we can see the actual tree. The trick is to cast the drug name as a VARBINARY(MAX) and keep on appending it so that we can later on order by on it to see the complete tree structure for the drug hierarchy. That helps us to see from the top drug – down to the next one in alphabetical order and their individual drug components immediately down from there till the deepest level is reached. And that is then followed by the next drug under the parent drug and their hierarchy in the same fashion. And this continues that way to show a complete tree representation. The lineage column is used to just show the lineage of the tree.

You can see it by executing the following command:

select * from drug_hierarchy order by traverse_path
GO

Since the output is rather large, we will leave it up to you to execute these in your environment to see it. This is a quick and fast way to recursively build up hierarchy trees in SQL Server 2005 or Oracle and DB2 (with slight syntax differences). SQL Server 2008 also introduces a new data-type for hierarchy which we will cover in a later post.

Tomorrow, we will cover the second part of this post which will go into how to recursively traverse a tree hierarchy by using a 1:N recursive relationship in a table like the Employee structure in an organization.

Designing Physical tables for a M:N recursive relationship within an Entity

This requirement is pretty common in some of the industries: Many times, the same entity can have a recursive M:N (Many-to-Many) within itself.  For example:

In the pharmaceutical industry, a drug can be composed of many drugs and vice-versa.  Likewise, in a manufacturing industry, a part can be composed of many parts and vice-versa.  The way to model this logical design into it’s corresponding physical implementation is by splitting the entity out into two physical tables with two 1-n (one-to-many) relationship between the main table and the child table.  This table will only be used to capture the recursive relationship and any other attributes that are specific to that relationship.

Example:

/*********************************************************************************
We will only consider 2 attributes for the sake of the explanation
**********************************************************************************/
CREATE TABLE dbo.DRUG_MASTER (DRUG_MASTER_ID INT NOT NULL IDENTITY, DRUG_NAME NVARCHAR(100), CONSTRAINT PK_DRUG_MASTER PRIMARY KEY (DRUG_MASTER_ID));
CREATE TABLE dbo.DRUG_RLTN (PARENT_DRUG_ID INT NOT NULL, CHILD_DRUG_ID INT NOT NULL, CONSTRAINT PK_DRUG_RLTN PRIMARY KEY (PARENT_DRUG_ID, CHILD_DRUG_ID));

And we will now have two Foreign Keys from the child to the parent table to help support the two 1:N relations that we have put into place:

ALTER TABLE dbo.DRUG_RLTN ADD CONSTRAINT FK_DRUG_RLTN_PARENT_TO_DRUG_MASTER FOREIGN KEY (PARENT_DRUG_ID) REFERENCES dbo.DRUG_MASTER (DRUG_MASTER_ID),
CONSTRAINT FK_DRUG_RLTN_CHILD_TO_DRUG_MASTER FOREIGN KEY (CHILD_DRUG_ID) REFERENCES dbo.DRUG_MASTER (DRUG_MASTER_ID)
GO

Let us insert some data now to show how this all ties up:

SET NOCOUNT ON
GO
SET IDENTITY_INSERT DRUG_MASTER ON
INSERT INTO dbo.DRUG_MASTER (DRUG_MASTER_ID, DRUG_NAME) VALUES (1, ‘DRUG A’);
INSERT INTO dbo.DRUG_MASTER (DRUG_MASTER_ID, DRUG_NAME) VALUES (2, ‘DRUG B’);
INSERT INTO dbo.DRUG_MASTER (DRUG_MASTER_ID, DRUG_NAME) VALUES (3, ‘DRUG C’);
INSERT INTO dbo.DRUG_MASTER (DRUG_MASTER_ID, DRUG_NAME) VALUES (4, ‘DRUG D’);
INSERT INTO dbo.DRUG_MASTER (DRUG_MASTER_ID, DRUG_NAME) VALUES (5, ‘DRUG E’);
SET IDENTITY_INSERT DRUG_MASTER OFF

INSERT INTO dbo.DRUG_RLTN (PARENT_DRUG_ID, CHILD_DRUG_ID) VALUES (1, 2);
INSERT INTO dbo.DRUG_RLTN (PARENT_DRUG_ID, CHILD_DRUG_ID) VALUES (1, 3);
INSERT INTO dbo.DRUG_RLTN (PARENT_DRUG_ID, CHILD_DRUG_ID) VALUES (2, 5);
INSERT INTO dbo.DRUG_RLTN (PARENT_DRUG_ID, CHILD_DRUG_ID) VALUES (5, 4);

As you can see from above, the M:N relationship is being captured in the relationship table DRUG_RLTN.

• DrugA comprises of DrugB and DrugC
• DrugB comprises of DrugE, and
• DrugE comprises of DrugD

In the next post, we will consider how you go about traversing this hierarchy using SQL and will use this as an example.  We will also use the classic employee structure in an organization as an example to show how to traverse hierarchies in SQL Server, Oracle and DB2.