How can I generate a hierarchy path in SQL that leads to a given node?

Question

In my MS SQL 2008 R2 database I have this table:

TABLE [Hierarchy]
[ParentCategoryId] [uniqueidentifier] NULL,
[ChildCategoryId] [uniqueidentifier] NOT NULL

I need to write a query that will generate all paths that lead to a given Node.

Lets say it I have the following tree:

A
-B
--C
-D
--C

Which would be stored as:

NULL | A
A    | B
A    | D
B    | C
D    | C

When asking for the Paths for C, I would like to get back two paths (written more or less like this):

A > B > C,
A > D > C

Protoplasm

Which version of SQL Server are you using? The keyword to search that you're looking for is Hierarchical Queries. I'm not too familiar with SQLServer, but that would be a trivial task in Oracle using the connect by and start with operators, and as far as I know the newer versions of SQLServer already have most of the features that Oracle has – Footling

Ah, forgot to mention version, I'll add that to the question but it's MS SQL 2008 R2 – Protoplasm

Check out recursive common table expressions or simply recursive queries. There are tons of example here on SO – Brick

Side bar; Tried to guess at why you would want to know every route available between nodes. Guessed maybe it was so that you could calculate the shortest path. If that is the case: Dijkstra's Algorithm – Ogdon

I need this but for mariadb – Unhook

Answer 1

Here is my solution, Sql Fiddle

DECLARE @child VARCHAR(10) = 'C'

    ;WITH children AS
    (

       SELECT 
         ParentCategoryId,
        CAST(ISNULL(ParentCategoryId + '->' ,'')  + ChildCategoryId AS VARCHAR(4000)) AS Path
       FROM Hierarchy
       WHERE ChildCategoryId =  @child
     UNION ALL
       SELECT 
         t.ParentCategoryId,
         list= CAST(ISNULL(t.ParentCategoryId  + '->' ,'')  + d.Path AS VARCHAR(4000))
       FROM Hierarchy t
       INNER JOIN children  AS d
            ON t.ChildCategoryId = d.ParentCategoryId
     )

    SELECT Path 
    from children c
    WHERE ParentCategoryId IS NULL

Output:

A->D->C 
A->B->C 

---

UPDATE:

@AlexeiMalashkevich, to just get id, you may try this

SQL Fiddle

DECLARE @child VARCHAR(10) = 'C'

;WITH children AS
(

   SELECT 
     ParentCategoryId,
     ChildCategoryId  AS Path
   FROM Hierarchy
   WHERE ChildCategoryId =  @child
 UNION ALL
   SELECT 
     t.ParentCategoryId,
     d.ParentCategoryId 
   FROM Hierarchy t
   INNER JOIN children  AS d
        ON t.ChildCategoryId = d.ParentCategoryId
 )

SELECT DISTINCT PATH
from children c

Heliograph

You get the check for also introducing me to SqlFiddle – Protoplasm

@Heliograph May be you have solution to get only path id's instead of path? Of course, i can parse it, but may be there is more beautiful solution? – Auberge

@AlexeiMalashkevich, could you please give an example of your desired output? – Heliograph

@Heliograph Sure. For previous example it should be 4 rows 'A' 'D' 'B' 'C'. – Auberge

Answer 2

Possible solution is to use recursive CTE as mentioned by @a_horse_with_no_name:

CREATE TABLE [Hierarchy](
[ParentCategoryId] CHAR(1) NULL,
[ChildCategoryId] CHAR(1) NOT NULL
);


INSERT INTO Hierarchy
SELECT NULL, 'A' UNION ALL
SELECT 'A', 'B' UNION ALL
SELECT 'A', 'D' UNION ALL
SELECT 'B', 'C' UNION ALL
SELECT 'D', 'C';


WITH CTE AS (
    SELECT 
        ParentCategoryId, ChildCategoryId, 
        CAST(ISNULL(ParentCategoryId,'') + ChildCategoryId AS VARCHAR(255)) [Path] 
    FROM Hierarchy
    WHERE ParentCategoryId IS NULL

    UNION ALL

    SELECT 
        H.ParentCategoryId, H.ChildCategoryId, 
        CAST(C.[Path] + ' > ' + H.ChildCategoryId AS VARCHAR(255)) [Path] 
    FROM Hierarchy H
    INNER JOIN CTE C ON C.ChildCategoryId = H.ParentCategoryId
) SELECT * FROM CTE;

Auten

You should start putting the semicolons at the end of the statements: sqlblog.org/2009/09/03/… – Brick

This would exclude top level parents without any children and would require a bit of manipulation to account for the use of uniqueidentifiers as the table datatypes, but the general logic is the same as my answer. You beat me to response by three minutes, kudos. :) – Radiothermy

@Love2Learn - yes, you are right, this is not perfect solution but just as an example to author. 3 minutes is like eternity - your SQL Server has performed billion of operations during this time :) – Auten

Answer 3

That's an interesting hierarchy structure. Seems to allow for parents to possibly be children of their children. If this were to happen this code logic would break, but as long as that doesn't occur this should work.

Create  Function dbo.IdentifyHierarchyPaths (@DeepestChildNode UniqueIdentifier)
Returns @hierarchy Table
(
        Hierarchy Varchar(Max)
)
As
Begin
        ;With   BuildHier As
        (
                Select  Convert(Varchar(Max),h2.ChildCategoryId) As child, Convert(Varchar(Max),h1.ChildCategoryId) + ' > ' +  Convert(Varchar(Max),h2.ChildCategoryId) As hier
                From    Hierarchy h1
                Left    Join Hierarchy h2
                        On  h1.ChildCategoryId = h2.ParentCategoryId
                Where   h1.ParentCategoryId Is Null
                Union   All
                Select  Convert(Varchar(Max),h1.ChildCategoryId) As child, bh.hier + ' > ' +  Convert(Varchar(Max),h1.ChildCategoryId) As hier
                From    BuildHier bh
                Join    Hierarchy h1
                        On  bh.child = h1.ParentCategoryId
        ),      HierWithTopLevel As
        (
                Select  Convert(Varchar(Max),ChildCategoryId) As hierarchy
                From    Hierarchy
                Where   ParentCategoryId Is Null
                Union   
                Select  hier
                From    BuildHier
        )
        Insert  @hierarchy
        Select  hierarchy
        From    HierWithTopLevel
        Where   Right(hierarchy,36) = Convert(Varchar(36),@DeepestChildNode);
        Return;
End;

Radiothermy

Answer 4

I found myself having an eerily similar issue, except that I am not using MS SQL at all! But with MariaDB.

Fortunately a solution was found inspired by @Oleksandr . I of course found this question through google, but in case anyone else has this specific problem and they happen to use MariaDB, fear not. SqlFiddle

WITH RECURSIVE MyTree AS (
    SELECT NULL AS ParentCategoryId, 'A' AS ChildCategoryId UNION ALL
    SELECT 'A', 'C' UNION ALL
    SELECT 'A', 'B' UNION ALL
    SELECT 'A', 'D' UNION ALL
    SELECT 'B', 'E' UNION ALL
    SELECT 'E', 'C' UNION ALL
    SELECT 'D', 'C'
),
CTE AS (
    -- Anchor member: select leaf nodes
    SELECT 
        ChildCategoryId AS Node,
        ParentCategoryId AS Parent,
        CAST(ChildCategoryId AS CHAR(100)) AS NodePath,
        1 AS Level
    FROM MyTree
    WHERE ChildCategoryId NOT IN (SELECT DISTINCT ParentCategoryId FROM MyTree WHERE ParentCategoryId IS NOT NULL)
    
    UNION ALL
    
    -- Recursive member: join to previous results and extend the path
    SELECT 
        CTE.Node,
        mt.ParentCategoryId AS Parent,
        CONCAT(mt.ChildCategoryId, ' > ', CTE.NodePath) AS NodePath,
        Level + 1 AS Level
    FROM CTE
    JOIN MyTree mt ON CTE.Parent = mt.ChildCategoryId
)
-- Final SELECT for the recursive CTE to return results without NULL Parents
SELECT DISTINCT
    TRIM(TRAILING ' > ' FROM NodePath) AS 'FullPath'
FROM CTE
WHERE Parent IS NULL
ORDER BY Level DESC;

Unhook