查询用 SQL Server 表模拟的整个图

Question

我有一个包含2个表NODE和EDGE的数据库，其中NODE由两列ID（int）和NAME（varchar）组成 EDGE 由两列 PARENTELMENTID (int) 和 CHILDELMENTID(int) 组成。

在这两个表的帮助下，我现在可以在关系数据库中模拟图形结构。例如：

    CREATE TABLE NODE(ID int, NAME varchar(1));
    CREATE TABLE EDGE(PARENTELEMENTID int, CHILDELEMENTID int);

    INSERT INTO NODE (Id, Name) VALUES(1, 'A');
    INSERT INTO NODE (Id, Name) VALUES(2, 'B');
    INSERT INTO NODE (Id, Name) VALUES(3, 'C');
    INSERT INTO NODE (Id, Name) VALUES(4, 'D');
    INSERT INTO NODE (Id, Name) VALUES(5, 'E');
    INSERT INTO NODE (Id, Name) VALUES(6, 'F');
    INSERT INTO NODE (Id, Name) VALUES(7, 'G');
    INSERT INTO NODE (Id, Name) VALUES(8, 'H');
    INSERT INTO NODE (Id, Name) VALUES(9, 'I');
    INSERT INTO NODE (Id, Name) VALUES(10, 'J');

    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (1, 4);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (1, 5);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (2, 4);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (2, 6);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (3, 7);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (4, 7);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (5, 8);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (6, 9);
    INSERT INTO EDGE (ParentElementId, ChildElementId) VALUES (10, 9);

结果如下图：

我需要的是一个语句来检索该图中的所有节点，从任何节点开始。

我的第一次尝试是以下声明：

    WITH ElementsToGetParentsFrom as (
        select n.Id
        from NODE n
        where n.Id in (1)
    ),
    ParentHierachies AS (
        SELECT p.Id,
               0 as traceLevel,
               NEWID() as TraceId
        from ElementsToGetParentsFrom p
        UNION ALL
        SELECT
            e.ParentElementId as id,
            ph.traceLevel + 1,
            ph.TraceId as TraceId
        FROM EDGE e
        JOIN ParentHierachies ph ON e.ChildElementId = ph.id
    ),
    GetRootIds as (
        select ph.Id,
               dense_rank() over (partition by TraceId order by traceLevel desc) as ranking
        from ParentHierachies ph
    ),
    AllElementsInGraph as (
        select gri.Id as Id
        from GetRootIds gri
        where gri.ranking = 1
        union all
        select e.ChildElementId as Id
        from EDGE e
        join AllElementsInGraph aeit on aeig.Id = e.ParentElementId
    )
    SELECT N.*
    FROM AllElementsInGraph aeig
    INNER JOIN NODE N on aeig.Id = N.Id

我使用第一个 cte 'ElementsToGetParentsFrom' 作为我的语句的入口，以决定我想要检索图形的节点。 第二个 cte“ParentHierachies”从给定节点向上遍历图形，为它们提供级别（用于下一个 cte）和跟踪 ID，以便能够区分不同的根元素。 现在，第三个 cte“GetRootIds”使用traceid 和tracelevel，通过按traceid 对所有id 进行分区并按它们在图中的级别对它们进行排名，将结果减少到仅图的根元素。 在最后一个 cte 'AllElementsInGraph' 中，我从 RootElements 向下遍历以获取图中的所有节点。

只有当我的图更像一棵树时，该语句才有效（我认为这是我的问题，因为当我写这篇文章时，我意识到我混淆了树和图的术语）。 因此，对于我的示例图，我得到了此输入的以下结果：

A -> A,D,E,G,H
B -> B,E,F,H,I
C -> C,G
D -> A,D,E,G,H
E -> A,B,D,E,F,G,H,I
F -> B,E,F,H,I
G -> A,C,D,E,G,H
H -> A,B,D,E,F,G,H,I
I -> B,E,F,H,I,J
J -> I,J

我需要的是一个语句（如果可能的话），在给定任何节点的情况下检索所有节点。

A -> A,B,C,D,E,F,G,H,I,J
B -> A,B,C,D,E,F,G,H,I,J
C -> A,B,C,D,E,F,G,H,I,J
D -> A,B,C,D,E,F,G,H,I,J
E -> A,B,C,D,E,F,G,H,I,J
F -> A,B,C,D,E,F,G,H,I,J
G -> A,B,C,D,E,F,G,H,I,J
H -> A,B,C,D,E,F,G,H,I,J
I -> A,B,C,D,E,F,G,H,I,J
J -> A,B,C,D,E,F,G,H,I,J

Answer 1

如果您想处理任意级别的递归，单个 SELECT 查询是有问题的。

这是一个基于循环方法的版本。

create table #n (id int not null primary key)

declare @start varchar(10)
set @start = 'A'

insert into #n (id) select id from node where name = @start

while @@rowcount > 0
BEGIN

; with nodes (id) as 
    (select ParentElementId from EDGE where ChildElementId in (select id from #n) 
    union all
    select ChildElementid from EDGE where ParentElementid in (select id from #n))

insert into #n (id) select distinct id from nodes where id not in (select id from #n)

END

select * from #n