MacLochlainns Weblog

Michael McLaughlin's Technical Blog

Site Admin

T-SQL Hierarchical Query

with 5 comments

Playing around with Microsoft SQL Server 2008 Express edition, I’ve sorted through a bunch of tidbits. One that I thought was interesting, is how to perform a recursive or hierarchical query. This describes how you can perform the magic.

The official name of the WITH clause in Oracle’s lexicon (otherwise known as Oraclese) is a subquery factoring clause. You can find more on that in this earlier blog post. Microsoft has a different name for the WITH clause. They call it a Common Table Expression or CTE.

You perform recursive queries in Microsoft SQL Server 2008 by leveraging CTEs. I’ve modified the setup code from that earlier blog post to run in SQL Server 2008. You’ll find it at the bottom of this blog post.

Unless you want to write your own C# (.NET is the politically correct lingo) equivalent to Oracle’s SQL*Plus, you’ll need to run this script in the SQL Server Management Studio. Actually, you can use Microsoft SQL Server 2008′s command-line utility, which is called sqlcmd.exe but it is much less robust than SQL*Plus. In the Management Studio, you click File, then Open, and File… to load the file for execution, and then click the Execute button. You need to be careful you don’t click the Debug button, which is the green arrow to the right of the Execute button.

se2008executebutton

This is the magic query in the illustration. You can also find it in the source code. At the end of the day, I’m hard pressed to understand why they’d use a UNION ALL to support recursion.

tsql_recursivequery

The top-most CTE, or subquery factoring clause, simply joins the ORGANIZATION_NAME to the ORG_PARENT_ID and ORG_CHILD_ID columns to provide a single working source. The second CTE performs the recursion. The top-query sets the starting row, and the second query recursively navigates the tree. After all children are found, the first query moves to the next element in the table and recursively searches for its children.

You should note that the CTE self-references itself from inside the second query. Then, the external query (the non-CTE query) returns the results by querying the same CTE.

This logic behaves more like a nested loop, and actually fails to move down branches of the tree like a recursive program. Otherwise line 19 would be line 14 in the output. You could write another CTE to fix this shortfall, thereby mirroring a true recursive behavior, or you can write a stored procedure.

The illustrated query outputs the following hierarchical relationship, which navigates down the hierarchical tree:

tsql_recursiveresults

You can also go up any branch of the tree by changing some of the logic. You’ll find the query to navigate up the tree as the second query in the setup script at the end of the blog. It renders the following output:

tsql_recursiveresultsleafup

The blog will be updated if I discover the equivalent to the LEVEL in Oracle’s self-referencing semantics. If you know it, please share it with everybody.

Setup Script

Microsoft SQL Server 2008 Join Script

USE student;
 
BEGIN TRAN;
 
-- Conditionally drop tables when they exist.
IF OBJECT_ID('dbo.ORGANIZATION','U') IS NOT NULL DROP TABLE dbo.ORGANIZATION;
IF OBJECT_ID('dbo.ORG_STRUCTURE','U') IS NOT NULL DROP TABLE dbo.ORG_STRUCTURE;
 
-- Create the organization table. 
CREATE TABLE ORGANIZATION
( organization_id INT
, organization_name VARCHAR(10));
 
-- Seed the organizations. 
INSERT INTO dbo.ORGANIZATION VALUES
 (1,'One'), (2,'Two'), (3,'Three'), (4,'Four'), (5,'Five')
,(6,'Six'), (7,'Seven'), (8,'Eight'), (9,'Nine'), (10,'Ten')
,(11,'Eleven'), (12,'Twelve'), (13,'Thirteen'), (14,'Fourteen'), (15,'Fifteen')
,(16,'Sixteen'), (17,'Seventeen'), (18,'Eighteen'), (19,'Nineteen'), (20,'Twenty');
 
-- Create the organization structure table that holds the recursive key. 
CREATE TABLE org_structure
( org_structure_id INT
, org_parent_id INT
, org_child_id INT );
 
-- Seed the organization structures. 
INSERT INTO org_structure VALUES
 ( 1, 0, 1),( 1, 1, 2),( 1, 1, 3),( 1, 1, 4),( 1, 2, 5)
,( 1, 2, 6),( 1, 3, 7),( 1, 3, 8),( 1, 4, 9),( 1, 4,10)
,( 1, 5,11),( 1, 5,12),( 1, 6,13),( 1, 6,14),( 1, 7,15)
,( 1, 8,16),( 1, 8,17),( 1, 9,18),( 1, 9,19),( 1,14,20);
 
COMMIT TRAN;
 
-- Navigating down the tree from the root node.
WITH org_name AS
 (SELECT   os.org_parent_id AS org_parent_id
  ,        o1.organization_name AS org_parent_name
  ,        os.org_child_id AS org_child_id
  ,        o2.organization_name AS org_child_name
  FROM     dbo.organization o1 RIGHT JOIN dbo.org_structure os 
  ON       o1.organization_id = os.org_parent_id RIGHT JOIN dbo.organization o2
  ON       o2.organization_id = os.org_child_id)
, jn AS
 (SELECT   org_parent_id, org_parent_name
  ,        org_child_id, org_child_name
  FROM     org_name
  WHERE    org_parent_id = 1  
  UNION ALL
  SELECT   c.org_parent_id, c.org_parent_name
  ,        c.org_child_id, c.org_child_name
  FROM     jn AS p JOIN org_name AS c
  ON       c.org_parent_id = p.org_child_id)
SELECT   jn.org_parent_id, jn.org_parent_name
,        jn.org_child_id, jn.org_child_name
FROM     jn
ORDER BY 1;
 
-- Navigating up the tree from the 20th leaf-node child.
WITH org_name AS
 (SELECT   os.org_parent_id AS org_parent_id
  ,        o1.organization_name AS org_parent_name
  ,        os.org_child_id AS org_child_id
  ,        o2.organization_name AS org_child_name
  FROM     dbo.organization o1 RIGHT JOIN dbo.org_structure os 
  ON       o1.organization_id = os.org_parent_id RIGHT JOIN dbo.organization o2
  ON       o2.organization_id = os.org_child_id)
, jn AS
 (SELECT   org_parent_id, org_parent_name
  ,        org_child_id, org_child_name
  FROM     org_name
  WHERE    org_child_id = 20  
  UNION ALL
  SELECT   c.org_parent_id, c.org_parent_name
  ,        c.org_child_id, c.org_child_name
  FROM     jn AS p JOIN org_name AS c
  ON       c.org_child_id = p.org_parent_id)
SELECT   jn.org_parent_id, jn.org_parent_name
,        jn.org_child_id, jn.org_child_name
FROM     jn
ORDER BY 1 DESC;

Written by maclochlainn

April 3rd, 2009 at 8:28 pm

5 Responses to 'T-SQL Hierarchical Query'

Subscribe to comments with RSS or TrackBack to 'T-SQL Hierarchical Query'.

  1. Great article. Thanks so much!

    Qmpel

    23 May 12 at 6:30 am

  2. [...] syntax in Microsoft SQL Server as a Common Table Expression (CTE) [...]

  3. Excellent article – very understandable. Modified as follows:

    Version with a single table, where the “organization name” is also held:

    SELECT [ID]
          ,[Model]
          ,[Parent_ID]
      FROM [Model_Definition];

    Nice and compact!!

    WITH org_name AS
     (SELECT   os.parent_id AS org_parent_id
      ,        o1.Model AS org_parent_name
      ,        os.id AS org_child_id
      ,        os.Model AS org_child_name
      FROM     dbo.Model_Definition o1 RIGHT JOIN dbo.Model_Definition os 
      ON       o1.id = os.parent_id
      )
    , jn AS
     (SELECT   org_parent_id, org_parent_name
      ,        org_child_id, org_child_name
      FROM     org_name
      WHERE    org_parent_id = 6  
      UNION ALL
      SELECT   c.org_parent_id, c.org_parent_name
      ,        c.org_child_id, c.org_child_name
      FROM     jn AS p JOIN org_name AS c
      ON       c.org_parent_id = p.org_child_id)
    SELECT   jn.org_parent_id, jn.org_parent_name
    ,        jn.org_child_id, jn.org_child_name
    FROM     jn
    ORDER BY 1;

    KoolMan

    26 Sep 12 at 2:21 pm

  4. Many thanks for showing both directions of the navigation. Other examples, while good, often don’t show that.

    Darryl W

    15 Sep 13 at 10:15 pm

  5. I have a table representing an XML document, with id (identity), tag and parent_id. here is some sample data:

    ID tag parent
    1 ltr NULL
    2 var 1
    3 reg 1
    4 opt 1
    5 prt 4
    6 prt1 5
    7 prt2 5
    8 prt2a 7
    9 polinf 1
    10 pol# 9
    11 drvs 1
    12 drv 11
    13 name 12
    14 rel 12
    15 fax 4
    16 lob 9
    17 prt2b 7

    I want to put the tags into XML hierarchy order, generate a sequence number, and a level looking like this:
    ID tag parent level sequence
    1 Ltr 1 0
    2 Var 1 2 1
    3 reg 1 2 2
    4 Opt 1 2 3
    5 prt 4 3 4
    6 prt1 5 4 5
    7 prt2 5 4 6
    8 prt2a 7 5 7
    17 prt2b 7 5 8
    15 fax 4 3 9
    9 polinf 1 2 10
    10 pol# 9 3 11
    16 LOB 9 3 12
    11 drvs 1 2 13
    12 drv 11 3 14
    13 name 12 4 15
    14 rel 12 4 16

    I need this to be able to generate the XML for a RESTFul service call. The XML would look like this:

    Can this be done?
    THanks.
    -Gary

    Gary Chait

    10 Dec 13 at 2:22 pm

Leave a Reply