Count the total tree structure

Question

I've got a table which contains object_id, object_name, derived_from_object_id

What function(s) do I need to look at to be able to provide a total count of derivations based on a provided object_id?

Example

1    object1    0  
2    object2    1  
3    object3    1  
4    object4    0  
5    object5    3  
6    object6    2  
7    object7    3  
8    object8    5  

There is no defined maximum number of derivations from an object or the children. So if I wanted a total count from objectid 1 the result would be 7.

I've thought about writing a stored procedure which simply returned a count for each object id, it would then call itself for each id that there was a child for. Whilst I think this would work I think it's completely the wrong direction to go.

Answer 1

You could use a recursive common table expression to find all the derivations from a particular starting point.

Table and Data

DROP TABLE IF EXISTS dbo.ObjectTree;

CREATE TABLE dbo.ObjectTree
(
    [object_id] integer NOT NULL
        CONSTRAINT [PK dbo.ObjectTree object_id]
        PRIMARY KEY CLUSTERED,
    [object_name] varchar(50) NOT NULL
        CONSTRAINT [UQ dbo.ObjectTree object_name]
        UNIQUE NONCLUSTERED,
    derived_from_object_id integer NULL
        CONSTRAINT [FK object_id]
        FOREIGN KEY (derived_from_object_id)
        REFERENCES dbo.ObjectTree ([object_id]),

    INDEX [IX dbo.ObjectTree derived_from_object_id] (derived_from_object_id)
);

INSERT dbo.ObjectTree
    ([object_id], [object_name], derived_from_object_id)
VALUES
    (1, 'object1', NULL),  
    (2, 'object2', 1),  
    (3, 'object3', 1),  
    (4, 'object4', NULL),  
    (5, 'object5', 3),  
    (6, 'object6', 2),  
    (7, 'object7', 3),  
    (8, 'object8', 5);

Recursive Query

-- Where to start
DECLARE @ObjectID integer = 1;

WITH R AS
(
    -- Anchor
    SELECT
        OT.[object_id]
    FROM dbo.ObjectTree AS OT
    WHERE
        OT.[object_id] = @ObjectID

    UNION ALL

    -- Recursive
    SELECT
        OT.[object_id]
    FROM R
    JOIN dbo.ObjectTree AS OT
        ON OT.derived_from_object_id = R.[object_id]
) 
SELECT
    derivations = COUNT_BIG(*)
FROM R
OPTION MAXRECURSION(0);

This returns 7 for [object_id] = 1.

Try it at db<>fiddle.

Using MAXRECURSION

The MAXRECURSION query hint can be used to prevent a poorly formed recursive CTE from entering into an infinite loop. If that is a concern for you, use a suitable maximum recursion level instead of the zero (no limit) above. The default (no hint) is 100.