Systems Engineering and RDBMS

Traversing the hierarchy – Part I

Posted by decipherinfosys on April 25, 2008

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.

One Response to “Traversing the hierarchy – Part I”

  1. […] Traversing the hierarchy – Part I […]

Sorry, the comment form is closed at this time.

 
%d bloggers like this: