Recursion in SQL

Question

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

Possible duplicate of [Sql server CTE and recursion example](http://stackoverflow.com/questions/14274942/sql-server-cte-and-recursion-example) — Sam Segers, Jul 05 '16 at 23:10
Looks like you will need at least 1 cte to find all of the cables and then join to get all of the knots. Sample data would be very helpful here — Matt, Jul 05 '16 at 23:14

Matt · Accepted Answer · 2016-07-06T17:47:02.573

1

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
;

edited Jul 06 '16 at 17:47

answered Jul 05 '16 at 23:24

Matt

13,833
2
16
28

Unfortunately I don't have a computer with SQL Server installed to test this data on (current computer only has SQLite, which to the best of my knowledge lacks the capability to confirm this behaviour); however this looks like something I should be able to work from. Thanks for your time; I will verify a similar solution works later today, then mark this as the accepted answer if so. – BeUndead Jul 05 '16 at 23:45
Thank you for the help; I've submitted a small edit to the version which worked for me, but the changes were relatively minor. Accepted as the appropriate answer; thanks again for taking the time to answer. – BeUndead Jul 06 '16 at 17:45
1

yep I just reviewed the edit most of it was just desired aliases. I did change one part of your edit. you can limit the recursion needed by putting the where statement on the anchor table (first table in cte). IT will run faster that way and not have to process records you will not use. Glad it worked! – Matt Jul 06 '16 at 17:48

Recursion in SQL

1 Answers1