Find sql connected component between many to many entities

user_6808270 0
Viewed 606

I have two basic entities: financial plan and purchase request. Theese two entities are in many-to-many relationship:

CREATE TABLE FinancialPlan
(
    ID int NOT NULL,
    PRIMARY KEY (ID)
);

CREATE TABLE PurchaseRequest
(
    ID int NOT NULL,
    PRIMARY KEY (ID)
);

CREATE TABLE FP_PR
(
    FP_ID FOREIGN KEY REFERENCES FinancialPlan(ID),
    PR_ID FOREIGN KEY REFERENCES PurchaseRequest(ID)
);

Problem: find all requests, related to specified plan, and all plans, related to requests, related to specified plan, ...

Model could be represented as a graph, where each node represents a plan, or a request, and each edge represents a relationship, then the problem could be rephrased as find connected component, which specified node belongs to.

Example:

Plan     Request    FP_PR

ID  |    ID  |      FP_ID|PR_ID|
----|    ----|      -----|-----|
1   |    1   |      1    |1    |
2   |    2   |      2    |1    |
3   |    3   |      2    |2    |
4   |               3    |2    |
5   |               4    |2    |
                    5    |3    |

Find connected component of finplan ID=1

Desired output:

FP_ID | PR_ID|
------+------+
1     | 1    |
2     | 1    |
2     | 2    |
3     | 2    |
4     | 2    |

I am currently doing it recursively on app side, which may generate to many requests and hang the DB server, could this be done with some recursive DB approach?

Visualization: enter image description here Starting entity is marked by arrow. Desired output is circled.

graph sql-server sql algorithm
1 Answers

SQL Server solution

I guess the main problem is you need to compare by PR_ID then FP_ID. So in recursive part there must be a CASE statement. On 1 run we take data by FP_ID on second by PR_ID and etc with the help of modulo.

DECLARE @fp int = 1

;WITH cte AS (
    SELECT  f.FP_ID,
            f.PR_ID, 
            1 as lev
    FROM #FP_PR f
    WHERE f.FP_id = @fp
    UNION ALL
    SELECT  f.FP_ID,
            f.PR_ID,
            lev+1
    FROM cte c
    CROSS JOIN #FP_PR f -- You can use INNER JOIN instead
    WHERE CASE (lev+1)%2 WHEN 0 THEN f.PR_ID WHEN 1 THEN f.FP_ID END = CASE (lev+1)%2 WHEN 0 THEN c.PR_ID WHEN 1 THEN c.FP_ID END
    AND NOT (f.PR_ID = c.PR_ID AND f.FP_ID = c.FP_ID)
)

SELECT *
FROM cte

Output:

FP_ID   PR_ID   lev
1       1       1
2       1       2
2       2       3
3       2       4
4       2       4
user_28933760
Related