BeUndead
BeUndead

Reputation: 3628

Recursion in SQL

So I have a set of tables along the lines of the following

cables:
id (integer) | name (char)

knots:
id (integer) | name (char)

cableKnotAttachments:
id (integer) | sourceCableId (integer) | targetKnotId (integer)

cableCableAttachments:
id (integer) | sourceCableId (integer) | targetCableId (integer)

Where a Cable can be attached to multiple other Cables, and multiple Knots, and a Knot can be attached to multiple Cables.

Given some Cables.Id, I need to find all the Knots which are within that Cable's children. We say a knot is a child of a Cable if it is either directly attached, or it is a child of any Cable which is attached to the Cable.

My attempt thus far is as follows:

SELECT cableKnotAttachments.targetKnotId
    FROM cableKnotAttachments
    WHERE cableKnotAttachments.sourceCableId = 1

UNION

SELECT cableKnotAttachments.targetKnotId
    FROM cableKnotAttachments
    INNER JOIN cableCableAttachments
    ON cableKnotAttachments.sourceCableId = cableCableAttachments.targetCableId
    WHERE cableCableAttachments.sourceCableId = 1;

In pseudo-code what would be nice:

getDirectlyAttachedKnots(cableId) {
    return knots directly attached to cableId
}

getDirectlyAttachedCables(cableId) {
    return cables directly attached to cableId
}

getAllChildKnots(cableId) {
    knots = getDirectlyAttachedKnots(cableId)

    for attachedCableId in getDirectlyAttachedCables(cableId) {
        knots += getAllChildKnots(attachedCableId)
    }

    return knots;
}

But this only covers a single level of recursion (without me just repeating that ad nauseam).

Is there a neat way to do this in SQL Server. It can be assumed that it is not practical to check all Knots in a sort of inverse check to this.

Edit: Adding some sample data for prosperity. Assuming we have Cables with ids {1, 2, ..., 4}; and Knots with ids {1, 2, ..., 9}:

cableCableAttachments:
id | sourceCableId | targetCableId
1  | 1             | 2
2  | 3             | 2
3  | 2             | 4

cableKnotAttachments:
id | sourceCableId | targetKnotId
1  | 1             | 2
2  | 1             | 3
3  | 2             | 4
4  | 3             | 5
5  | 3             | 6
6  | 3             | 7
7  | 4             | 1
8  | 4             | 2
9  | 4             | 3

In which context we would have:

cableId | childKnots
1       | 2, 3, 4, 1
2       | 4, 1, 2, 3
3       | 5, 6, 7, 4
4       | 1, 2, 3

Upvotes: 0

Views: 86

Answers (1)

Matt
Matt

Reputation: 14381

This answer very likely will need some work as it is really difficult to conceptualize the INNER JOIN on the recursive cte without test data and knowing how your relationship is being stored in particular in cableCableAttachments. But this hopeuflly will give you an idea of what to try:

;WITH cteRecursiveCables AS (
    SELECT
       id AS startingAncestorId
       ,id as ancestorId
       ,id AS cableId
       ,1 AS recursionLevel
    FROM
       Cables
    WHERE id = 2 -- For example

    UNION ALL

    SELECT
       startingAncestorId = cte.startingAncestorId
       ,ancestorId = cte.CableId
       ,cableId = att.targetCableId
       ,recursionLevel = cte.recursionLevel + 1
    FROM
       cableCableAttachments att
       INNER JOIN cteRecursiveCables cte
       ON a.sourceCableId = cte.cableId
)

SELECT att.targetKnotId
FROM
    cteRecursiveCables cte
    INNER JOIN cableKnotAttachments att
    ON cte.cableId = att.sourceCableId
;

Upvotes: 1

Related Questions