CODEWITHSUNDEEP
sqlsql-server-2008graph
Legend
Legend

Reputation: 117030

Getting nodes under a given node?

Given a source node, I would like to get all nodes "under" it where under means that all nodes whose level is less than the given node's level and are reachable from the given node. I remember this can be done using common table expressions and am currently working on it. However, is there a way to do this fast on a large graph (consisting of about 100K nodes)?

Sample data:

CREATE TABLE #TEMP(Source VARCHAR(50), SourceLevel INT, Sink VARCHAR(50), SinkLevel INT);


INSERT INTO #TEMP VALUES('A', 1, 'B', 2);
INSERT INTO #TEMP VALUES('A', 1, 'C', 2);
INSERT INTO #TEMP VALUES('B', 2, 'C', 2);
INSERT INTO #TEMP VALUES('B', 2, 'D', 3);
INSERT INTO #TEMP VALUES('B', 2, 'E', 3);
INSERT INTO #TEMP VALUES('C', 2, 'D', 3);
INSERT INTO #TEMP VALUES('C', 2, 'F', 3);
INSERT INTO #TEMP VALUES('C', 2, 'G', 3);


SELECT *
FROM #TEMP

GO

DROP TABLE #TEMP
GO

Graph:

      A                        Level - 1
     / \
    B---C                      Level - 2
   / \ /|\
  E   D F G                    Level - 3

Example:

Upvotes: 0

Views: 107

Answers (1)

Legend
Legend

Reputation: 117030

One possible solution here, using Recursive CTEs but there is still some problem with this (the answer does not exactly match yet but its getting there). I'll update this query once I get it close to my final requirement.

EDIT 1: The following satisfied all outputs except the one that asks for the root node 'A' in which case, it goes only one level deep for some reason.

EDIT 2: This gives the expected output. I'll check with other use cases now.

;WITH HIERARCHY AS (
  SELECT T.Source, T.SourceLevel, T.Sink, T.SinkLevel
    FROM #TEMP T
   WHERE T.Source = 'A'
   AND T.SourceLevel < T.SinkLevel
 UNION ALL
 SELECT X.Source, X.SourceLevel, X.Sink, X.SinkLevel
   FROM #TEMP X
   JOIN HIERARCHY H ON H.Sink = X.Source
)
SELECT DISTINCT H.Sink
  FROM HIERARCHY H

Upvotes: 1

Related Questions