user2478398 user2478398 - 5 months ago 14
SQL Question

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
Cable
s, and multiple
Knot
s, and a
Knot
can be attached to multiple
Cable
s.

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
Knot
s in a sort of inverse check to this.

Edit:
Adding some sample data for prosperity. Assuming we have
Cables
with
id
s
{1, 2, ..., 4}
; and
Knots
with
id
s
{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

Answer

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
;