복붙노트

[SQL] 무향 그래프의 연결된 모든 서브 그래프를 찾는 방법

SQL

무향 그래프의 연결된 모든 서브 그래프를 찾는 방법

난 내가 해결하기 위해 고군분투 문제에 대한 몇 가지 도움이 필요합니다.

예 테이블 :

ID |Identifier1 | Identifier2 
---------------------------------
1  |      a     | c         
2  |      b     | f         
3  |      a     | g         
4  |      c     | h        
5  |      b     | j         
6  |      d     | f         
7  |      e     | k  
8  |      i     |          
9  |      l     | h

나는 두 열 사이에 독특한 그룹 ID 할당 서로 관련 그룹 식별자합니다.

원하는 출력 :

Identifier | Gr_ID    |    Gr.Members                 
---------------------------------------------------
a       |      1      |   (a,c,g,h,l)  
b       |      2      |   (b,d,f,j)       
c       |      1      |   (a,c,g,h,l)  
d       |      2      |   (b,d,f,j)       
e       |      3      |   (e,k)                 
f       |      2      |   (b,d,f,j)       
g       |      1      |   (a,c,g,h,l)  
h       |      1      |   (a,c,g,h,l)  
j       |      2      |   (b,d,f,j)       
k       |      3      |   (e,k)                 
l       |      1      |   (a,c,g,h,l)  
i       |      4      |   (i)

참고 : 열 Gr.Members가 대부분 명확한보기에 사용되는 필요가 없습니다.

그러나 상기 그룹 ID가 아닌 행 (두 열 결합에 의해 선택된) 각 식별자에 할당되어야한다.

원하는 출력을 제공하는 쿼리를 작성하는 방법에 어떤 도움?

감사합니다.

업데이트 : 다음은 자신의 예상 출력이 몇 가지 추가 샘플 세트입니다.

주어진 테이블 :

Identifier1 | Identifier2   
----------------------------
    a       |   f
    a       |   g
    a       |  NULL
    b       |   c
    b       |   a
    b       |   h
    b       |   j
    b       |  NULL
    b       |  NULL
    b       |   g
    c       |   k
    c       |   b
    d       |   l
    d       |   f
    d       |   g
    d       |   m
    d       |   a
    d       |  NULL
    d       |   a
    e       |   c
    e       |   b
    e       |  NULL

예상 출력 모든 레코드를 그룹 ID = 1과 동일한 그룹에 속하는 것이다.

주어진 테이블 :

Identifier1 | Identifier2
--------------------------
a           |   a
b           |   b
c           |   a
c           |   b
c           |   c

예상 출력 : 레코드 그룹 ID = 1과 동일한 그룹이어야한다.

해결법

  1. ==============================

    1.여기에 커서를 사용하지 않는 변종이지만, 하나의 재귀 쿼리를 사용합니다.

    여기에 커서를 사용하지 않는 변종이지만, 하나의 재귀 쿼리를 사용합니다.

    기본적으로,이 루프가 검출 될 때 정지 한 그래프에서 에지로 데이터를 처리하고, 그래프의 재귀 모든 에지를 통과. 그런 다음 그룹에서 발견 된 모든 루프를두고 각 그룹 번호를 제공합니다.

    그 아래 작동하는 방법의 자세한 설명을 참조하십시오. 난 당신이 쿼리 CTE--CTE에 의해 실행하고 무엇을 이해하는 각각의 중간 결과를 검토하는 것이 좋습니다.

    샘플 1

    DECLARE @T TABLE (ID int, Ident1 char(1), Ident2 char(1));
INSERT INTO @T (ID, Ident1, Ident2) VALUES
(1, 'a', 'a'),
(2, 'b', 'b'),
(3, 'c', 'a'),
(4, 'c', 'b'),
(5, 'c', 'c');

    샘플 2

    I는 부대 값과 복수의 열을 갖고, Z 값이 하나 개 이상의 행을 추가했다.

    DECLARE @T TABLE (ID int, Ident1 char(1), Ident2 char(1));
INSERT INTO @T (ID, Ident1, Ident2) VALUES
(1, 'a', 'a'),
(1, 'a', 'c'),
(2, 'b', 'f'),
(3, 'a', 'g'),
(4, 'c', 'h'),
(5, 'b', 'j'),
(6, 'd', 'f'),
(7, 'e', 'k'),
(8, 'i', NULL),
(88, 'z', 'z'),
(9, 'l', 'h');

    샘플 3

    DECLARE @T TABLE (ID int, Ident1 char(1), Ident2 char(1));
INSERT INTO @T (ID, Ident1, Ident2) VALUES
(1, 'a', 'f'),
(2, 'a', 'g'),
(3, 'a', NULL),
(4, 'b', 'c'),
(5, 'b', 'a'),
(6, 'b', 'h'),
(7, 'b', 'j'),
(8, 'b', NULL),
(9, 'b', NULL),
(10, 'b', 'g'),
(11, 'c', 'k'),
(12, 'c', 'b'),
(13, 'd', 'l'),
(14, 'd', 'f'),
(15, 'd', 'g'),
(16, 'd', 'm'),
(17, 'd', 'a'),
(18, 'd', NULL),
(19, 'd', 'a'),
(20, 'e', 'c'),
(21, 'e', 'b'),
(22, 'e', NULL);

    질문

    WITH
CTE_Idents
AS
(
    SELECT Ident1 AS Ident
    FROM @T

    UNION

    SELECT Ident2 AS Ident
    FROM @T
)
,CTE_Pairs
AS
(
    SELECT Ident1, Ident2
    FROM @T
    WHERE Ident1 <> Ident2

    UNION

    SELECT Ident2 AS Ident1, Ident1 AS Ident2
    FROM @T
    WHERE Ident1 <> Ident2
)
,CTE_Recursive
AS
(
    SELECT
        CAST(CTE_Idents.Ident AS varchar(8000)) AS AnchorIdent 
        , Ident1
        , Ident2
        , CAST(',' + Ident1 + ',' + Ident2 + ',' AS varchar(8000)) AS IdentPath
        , 1 AS Lvl
    FROM 
        CTE_Pairs
        INNER JOIN CTE_Idents ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent 
        , CTE_Pairs.Ident1
        , CTE_Pairs.Ident2
        , CAST(CTE_Recursive.IdentPath + CTE_Pairs.Ident2 + ',' AS varchar(8000)) AS IdentPath
        , CTE_Recursive.Lvl + 1 AS Lvl
    FROM
        CTE_Pairs
        INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CTE_Pairs.Ident2 + ',%' AS varchar(8000))
)
,CTE_RecursionResult
AS
(
    SELECT AnchorIdent, Ident1, Ident2
    FROM CTE_Recursive
)
,CTE_CleanResult
AS
(
    SELECT AnchorIdent, Ident1 AS Ident
    FROM CTE_RecursionResult

    UNION

    SELECT AnchorIdent, Ident2 AS Ident
    FROM CTE_RecursionResult
)
SELECT
    CTE_Idents.Ident
    ,CASE WHEN CA_Data.XML_Value IS NULL 
    THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END AS GroupMembers
    ,DENSE_RANK() OVER(ORDER BY 
        CASE WHEN CA_Data.XML_Value IS NULL 
        THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END
    ) AS GroupID
FROM
    CTE_Idents
    CROSS APPLY
    (
        SELECT CTE_CleanResult.Ident+','
        FROM CTE_CleanResult
        WHERE CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
        ORDER BY CTE_CleanResult.Ident FOR XML PATH(''), TYPE
    ) AS CA_XML(XML_Value)
    CROSS APPLY
    (
        SELECT CA_XML.XML_Value.value('.', 'NVARCHAR(MAX)')
    ) AS CA_Data(XML_Value)
WHERE
    CTE_Idents.Ident IS NOT NULL
ORDER BY Ident;

    1 결과

    +-------+--------------+---------+
| Ident | GroupMembers | GroupID |
+-------+--------------+---------+
| a     | a,b,c,       |       1 |
| b     | a,b,c,       |       1 |
| c     | a,b,c,       |       1 |
+-------+--------------+---------+

    이 결과

    +-------+--------------+---------+
| Ident | GroupMembers | GroupID |
+-------+--------------+---------+
| a     | a,c,g,h,l,   |       1 |
| b     | b,d,f,j,     |       2 |
| c     | a,c,g,h,l,   |       1 |
| d     | b,d,f,j,     |       2 |
| e     | e,k,         |       3 |
| f     | b,d,f,j,     |       2 |
| g     | a,c,g,h,l,   |       1 |
| h     | a,c,g,h,l,   |       1 |
| i     | i            |       4 |
| j     | b,d,f,j,     |       2 |
| k     | e,k,         |       3 |
| l     | a,c,g,h,l,   |       1 |
| z     | z            |       5 |
+-------+--------------+---------+

    3 결과

    +-------+--------------------------+---------+
| Ident |       GroupMembers       | GroupID |
+-------+--------------------------+---------+
| a     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| b     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| c     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| d     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| e     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| f     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| g     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| h     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| j     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| k     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| l     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
| m     | a,b,c,d,e,f,g,h,j,k,l,m, |       1 |
+-------+--------------------------+---------+

    나는이 설명은 샘플 데이터의 두 번째 세트를 사용합니다.

    CTE_Idents

    CTE_Idents 모두 Ident1 및 Ident2 컬럼에 나타나는 모든 식별자의 목록을 제공합니다. 그들이 어떤 순서로 표시 할 수 있기 때문에 두 열 함께 UNION을 우리. UNION은 모든 중복을 제거합니다.

    +-------+
| Ident |
+-------+
| NULL  |
| a     |
| b     |
| c     |
| d     |
| e     |
| f     |
| g     |
| h     |
| i     |
| j     |
| k     |
| l     |
| z     |
+-------+

    CTE_Pairs

    CTE_Pairs 양방향의 그래프의 모든 모서리의 목록을 제공한다. 다시 말하지만, UNION은 중복을 제거하는 데 사용됩니다.

    +--------+--------+
| Ident1 | Ident2 |
+--------+--------+
| a      | c      |
| a      | g      |
| b      | f      |
| b      | j      |
| c      | a      |
| c      | h      |
| d      | f      |
| e      | k      |
| f      | b      |
| f      | d      |
| g      | a      |
| h      | c      |
| h      | l      |
| j      | b      |
| k      | e      |
| l      | h      |
+--------+--------+

    CTE 재귀

    CTE_Recursive 재귀 적으로 각각의 고유 한 식별자부터 그래프를 통과 쿼리의 주요 부분이다. 이러한 시작하는 행은 UNION ALL의 첫 부분에 의해 생성된다. UNION ALL의 두 번째 부분은 재귀 자체가 Ident1에 Ident2 연결에 합류했다. 우리는 이후 두 방향으로 기록 된 모든 가장자리 CTE_Pairs를 미리 만들어, 우리는 항상 Ident1 만 Ident2를 연결할 수 있습니다 그리고 우리는 그래프의 모든 경로를 얻을 수 있습니다. 지금까지 통과 된 쉼표로 구분 된 식별자의 캐릭터 - 동시에 쿼리가 IdentPath을 구축합니다. 그것은 WHERE 필터에 사용되는 :

    CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CTE_Pairs.Ident2 + ',%' AS varchar(8000))

    연결된 노드의 목록이 소진되는 즉시 우리가 전에 경로에 포함되었던 식별자 건너로, 재귀가 중지됩니다. AnchorIdent는 재귀의 시작 식별자입니다, 그것은 그룹 결과를 나중에 사용됩니다. LVL 정말 사용하지, 내가 무슨 일이 일어나고 있는지의 더 나은 이해를 위해 포함되어 있습니다.

    +-------------+--------+--------+-------------+-----+
| AnchorIdent | Ident1 | Ident2 |  IdentPath  | Lvl |
+-------------+--------+--------+-------------+-----+
| a           | a      | c      | ,a,c,       |   1 |
| a           | a      | g      | ,a,g,       |   1 |
| b           | b      | f      | ,b,f,       |   1 |
| b           | b      | j      | ,b,j,       |   1 |
| c           | c      | a      | ,c,a,       |   1 |
| c           | c      | h      | ,c,h,       |   1 |
| d           | d      | f      | ,d,f,       |   1 |
| e           | e      | k      | ,e,k,       |   1 |
| f           | f      | b      | ,f,b,       |   1 |
| f           | f      | d      | ,f,d,       |   1 |
| g           | g      | a      | ,g,a,       |   1 |
| h           | h      | c      | ,h,c,       |   1 |
| h           | h      | l      | ,h,l,       |   1 |
| j           | j      | b      | ,j,b,       |   1 |
| k           | k      | e      | ,k,e,       |   1 |
| l           | l      | h      | ,l,h,       |   1 |
| l           | h      | c      | ,l,h,c,     |   2 |
| l           | c      | a      | ,l,h,c,a,   |   3 |
| l           | a      | g      | ,l,h,c,a,g, |   4 |
| j           | b      | f      | ,j,b,f,     |   2 |
| j           | f      | d      | ,j,b,f,d,   |   3 |
| h           | c      | a      | ,h,c,a,     |   2 |
| h           | a      | g      | ,h,c,a,g,   |   3 |
| g           | a      | c      | ,g,a,c,     |   2 |
| g           | c      | h      | ,g,a,c,h,   |   3 |
| g           | h      | l      | ,g,a,c,h,l, |   4 |
| f           | b      | j      | ,f,b,j,     |   2 |
| d           | f      | b      | ,d,f,b,     |   2 |
| d           | b      | j      | ,d,f,b,j,   |   3 |
| c           | h      | l      | ,c,h,l,     |   2 |
| c           | a      | g      | ,c,a,g,     |   2 |
| b           | f      | d      | ,b,f,d,     |   2 |
| a           | c      | h      | ,a,c,h,     |   2 |
| a           | h      | l      | ,a,c,h,l,   |   3 |
+-------------+--------+--------+-------------+-----+

    CTE_CleanResult

    CTE_CleanResult는 CTE_Recursive 만 관련 부분을 떠나 다시 Ident1 및 Ident2 모두 UNION을 사용하여 병합합니다.

    +-------------+-------+
| AnchorIdent | Ident |
+-------------+-------+
| a           | a     |
| a           | c     |
| a           | g     |
| a           | h     |
| a           | l     |
| b           | b     |
| b           | d     |
| b           | f     |
| b           | j     |
| c           | a     |
| c           | c     |
| c           | g     |
| c           | h     |
| c           | l     |
| d           | b     |
| d           | d     |
| d           | f     |
| d           | j     |
| e           | e     |
| e           | k     |
| f           | b     |
| f           | d     |
| f           | f     |
| f           | j     |
| g           | a     |
| g           | c     |
| g           | g     |
| g           | h     |
| g           | l     |
| h           | a     |
| h           | c     |
| h           | g     |
| h           | h     |
| h           | l     |
| j           | b     |
| j           | d     |
| j           | f     |
| j           | j     |
| k           | e     |
| k           | k     |
| l           | a     |
| l           | c     |
| l           | g     |
| l           | h     |
| l           | l     |
+-------------+-------+

    마지막 SELECT

    이제 우리는 각 AnchorIdent에 대한 쉼표로 구분 된 식별자의 값의 캐릭터를 구축 할 필요가있다. CROSS는 XML 그것을하지 FOR와 함께 적용됩니다. DENSE_RANK ()는 각 AnchorIdent의 그룹 ID 번호를 계산합니다.

  2. ==============================

    2.필요에 따라이 스크립트는 테스트 세트 1, 2 및 3에 대한 출력을 생성한다. 스크립트에서 주석으로 알고리즘에 대한 참고 사항.

    필요에 따라이 스크립트는 테스트 세트 1, 2 및 3에 대한 출력을 생성한다. 스크립트에서 주석으로 알고리즘에 대한 참고 사항.

    주의 :

    참고 재귀 CTE를를 사용하여 대답은 하나의 SQL 문 것을 더 우아하지만, 심해 실행 시간을 제공 할 수 있습니다 재귀 열팽창 계수를 사용하여 큰 입력 세트에 대해 (그 대답에이 댓글을 참조)있다. 더 선상하면서 후술하는 바와 같이 용액, 큰 입력 세트 훨씬 빠르게 실행한다.

    SET NOCOUNT ON;

CREATE TABLE #tree(node_l CHAR(1),node_r CHAR(1));
CREATE NONCLUSTERED INDEX NIX_tree_node_l ON #tree(node_l)INCLUDE(node_r); -- covering indices to speed up lookup
CREATE NONCLUSTERED INDEX NIX_tree_node_r ON #tree(node_r)INCLUDE(node_l);
INSERT INTO #tree(node_l,node_r) VALUES
    ('a','c'),('b','f'),('a','g'),('c','h'),('b','j'),('d','f'),('e','k'),('i','i'),('l','h'); -- test set 1
    --('a','f'),('a','g'),(CHAR(0),'a'),('b','c'),('b','a'),('b','h'),('b','j'),('b',CHAR(0)),('b',CHAR(0)),('b','g'),('c','k'),('c','b'),('d','l'),('d','f'),('d','g'),('d','m'),('d','a'),('d',CHAR(0)),('d','a'),('e','c'),('e','b'),('e',CHAR(0)); -- test set 2
    --('a','a'),('b','b'),('c','a'),('c','b'),('c','c'); -- test set 3 

CREATE TABLE #sets(node CHAR(1) PRIMARY KEY,group_id INT); -- nodes with group id assigned
CREATE TABLE #visitor_queue(node CHAR(1)); -- contains nodes to visit
CREATE TABLE #visited_nodes(node CHAR(1) PRIMARY KEY CLUSTERED WITH(IGNORE_DUP_KEY=ON)); -- nodes visited for nodes on the queue; ignore duplicate nodes when inserted
CREATE TABLE #visitor_ctx(node_l CHAR(1),node_r CHAR(1)); -- context table, contains deleted nodes as they are visited from #tree

DECLARE @last_created_group_id INT=0;

-- Notes:
-- 1. This algorithm is destructive in its input set, ie #tree will be empty at the end of this procedure
-- 2. This algorithm does not accept NULL values. Populate #tree with CHAR(0) for NULL values (using ISNULL(source_col,CHAR(0)), or COALESCE(source_col,CHAR(0)))
-- 3. When selecting from #sets, to regain the original NULL values use NULLIF(node,CHAR(0))
WHILE EXISTS(SELECT*FROM #tree)
BEGIN
    TRUNCATE TABLE #visited_nodes;
    TRUNCATE TABLE #visitor_ctx;

    -- push first nodes onto the queue (via #visitor_ctx -> #visitor_queue)
    DELETE TOP (1) t
    OUTPUT deleted.node_l,deleted.node_r INTO #visitor_ctx(node_l,node_r)
    FROM #tree AS t;

    INSERT INTO #visitor_queue(node) SELECT node_l FROM #visitor_ctx UNION SELECT node_r FROM #visitor_ctx; -- UNION to filter when node_l equals node_r
    INSERT INTO #visited_nodes(node) SELECT node FROM #visitor_queue; -- keep track of nodes visited

    -- work down the queue by visiting linked nodes in #tree; nodes are deleted as they are visited
    WHILE EXISTS(SELECT*FROM #visitor_queue)
    BEGIN
        TRUNCATE TABLE #visitor_ctx;

        -- pop_front for node on the stack (via #visitor_ctx -> @node)
        DELETE TOP (1) s
        OUTPUT deleted.node INTO #visitor_ctx(node_l)
        FROM #visitor_queue AS s;

        DECLARE @node CHAR(1)=(SELECT node_l FROM #visitor_ctx); 
        TRUNCATE TABLE #visitor_ctx;

        -- visit nodes in #tree where node_l or node_r equal target @node; 
        -- delete visited nodes from #tree, output to #visitor_ctx
        DELETE t
        OUTPUT deleted.node_l,deleted.node_r INTO #visitor_ctx(node_l,node_r)
        FROM #tree AS t
        WHERE t.node_l=@node OR t.node_r=@node;

        -- insert visited nodes in the queue that haven't been visited before
        INSERT INTO #visitor_queue(node) 
        (SELECT node_l FROM #visitor_ctx UNION SELECT node_r FROM #visitor_ctx) EXCEPT (SELECT node FROM #visited_nodes);

        -- keep track of visited nodes (duplicates are ignored by the IGNORE_DUP_KEY option for the PK)
        INSERT INTO #visited_nodes(node)
        SELECT node_l FROM #visitor_ctx UNION SELECT node_r FROM #visitor_ctx;
    END

    SET @last_created_group_id+=1; -- create new group id

    -- insert group into #sets
    INSERT INTO #sets(group_id,node)
    SELECT group_id=@last_created_group_id,node 
    FROM #visited_nodes;
END

SELECT node=NULLIF(node,CHAR(0)),group_id FROM #sets ORDER BY node; -- nodes with their assigned group id

SELECT g.group_id,m.members  -- groups with their members
FROM
    (SELECT DISTINCT group_id FROM #sets) AS g
    CROSS APPLY (
        SELECT members=STUFF((
                SELECT ','+ISNULL(CAST(NULLIF(si.node,CHAR(0)) AS VARCHAR(4)),'NULL')
                FROM #sets AS si 
                WHERE si.group_id=g.group_id
                FOR XML PATH('')
            ),1,1,'')
     ) AS m
ORDER BY g.group_id;

DROP TABLE #visitor_queue;
DROP TABLE #visited_nodes;
DROP TABLE #visitor_ctx;
DROP TABLE #sets;
DROP TABLE #tree;

    세트 1의 출력 :

    +------+----------+
| node | group_id |
+------+----------+
| a    |        1 |
| b    |        2 |
| c    |        1 |
| d    |        2 |
| e    |        4 |
| f    |        2 |
| g    |        1 |
| h    |        1 |
| i    |        3 |
| j    |        2 |
| k    |        4 |
| l    |        1 |
+------+----------+

    세트 2의 출력 :

    +------+----------+
| node | group_id |
+------+----------+
| NULL |        1 |
| a    |        1 |
| b    |        1 |
| c    |        1 |
| d    |        1 |
| e    |        1 |
| f    |        1 |
| g    |        1 |
| h    |        1 |
| j    |        1 |
| k    |        1 |
| l    |        1 |
| m    |        1 |
+------+----------+

    세트 3의 출력 :

    +------+----------+
| node | group_id |
+------+----------+
| a    |        1 |
| b    |        1 |
| c    |        1 |
+------+----------+

    3. from https://stackoverflow.com/questions/35254260/how-to-find-all-connected-subgraphs-of-an-undirected-graph by cc-by-sa and MIT license

'SQL' 카테고리의 다른 글

[SQL] MySQL은 : 분할 쉼표는 여러 행으로 구분 된 목록  (0) 2020.04.02
[SQL] 합니까 sqlite3를 외부 키 제약 조건을 지원하지?  (0) 2020.04.02
[SQL] 자바 프로그램에 방지 SQL 주입 공격  (0) 2020.04.02
[SQL] MySQL의 재귀?  (0) 2020.04.02
[SQL] SQL은 : 2 개의 다른 AUTO_INCREMENT와의 관계 테이블 만들기  (0) 2020.04.02
,

티스토리툴바