Sql-server – Select tree-based structure

recursivesql server

I have a table in my SQL Server database with data like this:

ID  ParentID
--- ---------
1   NULL
2   1
3   1
5   1
5   4
5   6
8   6
7   9
9   10

I need a select statement that will return all the rows that have some relation between them (no matter parent or child). For example for id = 1 I need to get all the rows except last two. The same result must be for id = 2, 3, 4, 5, 6 ,8. And for id = 7 or 9 the statement must return only the last two rows. I tried to solve this issue with recursive CTE but I failed.

Best Answer

I'm not great with recursion either, so don't feel bad. I've had success with structures similar to the following. It's not elegant, but you can see exactly what's going on. Basically you need to gather all the possible values to evaluate against both ID and ParentID for a given ParentID value. This solution assumes integer values. It will get a little more tricky with alphanumric values. The nice thing about this is you can run it as is or modify it to display a hierarchical ordering.

    --create the table for the example
    IF OBJECT_ID('tbl_RecursiveExample','U') IS NOT NULL
        DROP TABLE tbl_RecursiveExample

    CREATE TABLE tbl_RecursiveExample
    (
          ID INT
        , ParentID INT
    )

    INSERT tbl_RecursiveExample
    VALUES   (1,NULL)
           , (2,1)
           , (3,1)
           , (5,1)
           , (5,4)
           , (5,6)
           , (8,6)
           , (7,9)
           , (9,10);


    --change the value to the parentID you are interested in
    DECLARE @ParentIDVal INT=10;

    WITH 
    cteFirstRelationship --Top level relationships
    AS
    (
        SELECT ID RelatedIDs
        FROM tbl_RecursiveExample 
        WHERE ParentID = @ParentIDVal
        UNION
        SELECT ParentID
        FROM tbl_RecursiveExample
        WHERE ID = @ParentIDVal
    ),
    cteSecondRelationship --secondary relationships
    AS
    (
        SELECT ID RelatedIDs
        FROM tbl_RecursiveExample t
            JOIN cteFirstRelationship cf ON cf.RelatedIDs=t.ParentID
        UNION
        SELECT ParentID
        FROM tbl_RecursiveExample t
            JOIN cteFirstRelationship cf ON cf.RelatedIDs=t.ID
    )
    --possible add another level if needed
    SELECT DISTINCT t.* --> Needed due to the match of both values
    FROM tbl_RecursiveExample t
        JOIN
        (       
            SELECT RelatedIDs from cteFirstRelationship
            UNION
            SELECT RelatedIDs from cteSecondRelationship
        )r ON r.RelatedIDs = t.ID OR r.RelatedIDs = t.ParentID

Related Solutions

Postgresql – Tree structure hierarchical query sorting

Efficiently storing, processing and reporting on hierarchical data of mixed/unknown depth in SQL is quite a complex area: whole books (such as Joe Celko's "Trees and Hierarchies in SQL for Smarties") have been written on the subject.

What you have there is often called a "naive tree" (only the parent relationship is noted) which does not allow for easily performing such a sort, or for queries where you want all data from under a particular node. It is common to de-normalise the structure in these cases by adding a path element to each row, so you can perform the sort you are looking for by sorting by theis field (and you can perform "everything under no matter how deep" queries by using filters such as tree_path LIKE '/path/to/target/node/%' (or tree_path LIKE '/path/to/target/node%' if you want to include the node itself). This avoids any need for recursion or an arbitrarily long collection joins, though of course you have the extra work to do maintaining this path when the tree changes. The book I usually recommend to all DB people (devs and admins alike), "SQL Antipatterns", has a chapter on this which covers the basics of this and other alternatives quite clearly (so you don't need to try consume Calko's tome unless you have some more complex requirements!).

If you can't alter the structure then you might be able to produce the path as an output using a recursive CTE (Common Table Expression) - I'll not go into detail here as there are already many good examples out there (in the documentation and StackExchange questions such as https://stackoverflow.com/questions/3307480/postgresql-recursive-with).

If your tree has a fixed depth (all leaf nodes are the same number of levels below root) then a fixed set of joins will do the trick:

SELECT {stuff}
FROM   source_table t1
JOIN   source_table t2 ON t2.id=t1.parent
JOIN   source_table t3 ON t3.id=t2.parent
JOIN   source_table t4 ON t4.id=t3.parent
ORDER BY t1.name, t2.name, t3.name, t4.name

for three levels below your root(s). If your depth is not fixed then this would not work (well, it could be forced to up to an arbitrary depth but the joins and the ordering clause would be pretty hairy to design and inefficient to run) to you need to use the CTE approach or use a modified data structure.

Sql-server – Making a recursive CTE like query, but for many records

Assuming the original table design is somewhat like this:

CREATE TABLE dbo.Area
(
    RowID integer PRIMARY KEY,
    GroupID  integer NOT NULL,
    ParentID integer NULL,
);

Sample data:

INSERT dbo.Area
    (RowID, GroupID, ParentID)
VALUES 
    (1, 1, NULL), -- Root
    (2, 1, 1),
    (3, 1, 2),
    (4, 2, NULL), -- Root
    (5, 2, 4),
    (6, 2, 5),
    (7, 2, 6);

The following recursive CTE query finds roots for the RowID list given in the anchor:

WITH R AS
(
    SELECT
        A.RowID,
        A.RowID AS OriginalRowID,
        A.ParentID
    FROM dbo.Area AS A
    WHERE
        A.RowID IN (3, 7)

    UNION ALL

    SELECT
        A.RowID,
        R.OriginalRowID,
        A.ParentID
    FROM dbo.Area AS A
    JOIN R
        ON R.ParentID = A.RowID
)
SELECT
    R.OriginalRowID,
    R.RowID
FROM R
WHERE
    R.ParentID IS NULL
ORDER BY
    R.OriginalRowID
OPTION (MAXRECURSION 0);

The output shows each supplied RowID and the root for that group:

Output

Best Answer

Related Solutions

Postgresql – Tree structure hierarchical query sorting

Sql-server – Making a recursive CTE like query, but for many records

Related Question