Несколько самоподсоединений для поиска транзитивных подмножеств (клик)

Question

Проще говоря, у меня есть таблица, представляющая отношение.Строки в таблице представляют пары в моем отношении.Другими словами, первая строка указывает, что идентификатор 1 связан с идентификатором 4 и что идентификатор 4 связан с идентификатором 1. Надеюсь, вам нетрудно увидеть, что мое отношение симметрично,хотя таблица показывает эту симметрию в сжатой форме.

+-----+-----+  
| id1 | id2 |  
+-----+-----+  
|   1 |   4 |  
|   3 |   1 |  
|   2 |   1 |  
|   2 |   3 |  
|   2 |   4 |  
|   5 |   1 |  
+-----+-----+

РЕДАКТИРОВАТЬ Эта таблица предназначена для краткого отображения следующего отношения:
{(1,4), (4,1), (3,1), (1,3), (2,1), (1,2), (2,3), (3,2), (2,4), (4,2), (5,1), (1,5)}.Это может быть визуализировано следующим неориентированным графиком.

CREATE TABLE Test (
id1 int not null,
id2 int not null);

INSERT INTO Test
VALUES
(1,4),
(3,1),
(2,1),
(2,3),
(2,4),
(5,1);

Я хотел бы определить транзитивные подмножества ( клики ) в моей таблице.
РЕДАКТИРОВАТЬ Например, я хотел бы определить переходное подмножество, продемонстрированное тем фактом, что идентификатор 3 связан с идентификатором 1, а идентификатор 1 связан с идентификатором 2подразумевает, что идентификатор 3 связан с идентификатором 2. (Они могут быть видны как треугольники на фото ненаправленного графика. Хотя, в лучшем случае, я хотел бы иметь возможность перечислить другие complete подграфы, которые больше, чем треугольники, если они присутствуют в исходной таблице / графике.)

Я пытался сделать следующее, но набор результатов больше, чем я хочу.Я надеюсь, что есть более простой способ.

select t1.id1, t1.id2, t2.id1, t2.id2, t3.id1, t3.id2
from test as t1
    join test as t2
        on t1.id1 = t2.id1
        or t1.id2 = t2.id2
        or t1.id1 = t2.id2
        or t1.id2 = t2.id1
    join test as t3
        on t2.id1 = t3.id1
        or t2.id2 = t3.id2
        or t2.id1 = t3.id2
        or t2.id2 = t3.id1
where
    not
    (
        t1.id1 = t2.id1
        and
        t1.id2 = t2.id2
    )
    and not
    (
        t2.id1 = t3.id1
        and
        t2.id2 = t3.id2
    )
    and not
    (
        t1.id1 = t3.id1
        and
        t1.id2 = t3.id2
    )
    and
    (
        (
            t3.id1 = t1.id1
            or
            t3.id1 = t1.id2
            or
            t3.id1 = t2.id1
            or
            t3.id1 = t2.id2
        )
        and
        (
            t3.id2 = t1.id1
            or
            t3.id2 = t1.id2
            or
            t3.id2 = t2.id1
            or
            t3.id2 = t2.id2
        )
    );

Фактический результат:

+-----+-----+-----+-----+-----+-----+
| id1 | id2 | id1 | id2 | id1 | id2 |
+-----+-----+-----+-----+-----+-----+
|   1 |   4 |   2 |   4 |   2 |   1 |
|   1 |   4 |   2 |   1 |   2 |   4 |
|   3 |   1 |   2 |   3 |   2 |   1 |
|   3 |   1 |   2 |   1 |   2 |   3 |
|   2 |   1 |   2 |   4 |   1 |   4 |
|   2 |   1 |   2 |   3 |   3 |   1 |
|   2 |   1 |   3 |   1 |   2 |   3 |
|   2 |   1 |   1 |   4 |   2 |   4 |
|   2 |   3 |   2 |   1 |   3 |   1 |
|   2 |   3 |   3 |   1 |   2 |   1 |
|   2 |   4 |   2 |   1 |   1 |   4 |
|   2 |   4 |   1 |   4 |   2 |   1 |
+-----+-----+-----+-----+-----+-----+

Ожидаемый набор результатов будет иметь только две строки.Каждая строка будет представлять транзитивное отношение, которое является подмножеством исходного отношения.

╔═════╦═════╦═════╦═════╦═════╦═════╗
║ id1 ║ id2 ║ id1 ║ id2 ║ id1 ║ id2 ║
╠═════╬═════╬═════╬═════╬═════╬═════╣
║   1 ║   4 ║   2 ║   4 ║   2 ║   1 ║
║   3 ║   1 ║   2 ║   1 ║   2 ║   3 ║
╚═════╩═════╩═════╩═════╩═════╩═════╝

EDIT Ожидаемый результат также может выглядеть следующим образом:

╔═════╦═════╦═════╗
║ id1 ║ id2 ║ id3 ║
╠═════╬═════╬═════╣
║   1 ║   4 ║   2 ║
║   3 ║   1 ║   2 ║
╚═════╩═════╩═════╝,

независимо от того,это легче.Мне просто нужно показать тот факт, что наборы
{(1,4), (4,1), (2,4), (4,2), (2,1), (1,2)}
и
{(3,1), (1,3), (2,1), (1,2), (2,3), (3,2)}
являются правильными подмножествамиисходного отношения и сами являются переходными отношениями.Я использую определение, что отношение R транзитивно тогда и только тогда, когда ∀a∀b∀c ((a, b) ∈R ∧ (b, c) ∈R → (a, c) ∈R).Другими словами, я пытаюсь найти все подграфы , которые также являются полными графами .

Я новичок в теории графов, но, похоже, моя проблема в том, чтоаналогично проблеме клики , где я ищу клики, содержащие 3 или более вершин.Я бы принял в качестве ответа решения, которые возвращают только клики с 3 вершинами.Мой вопрос похож на этот один.Однако представленные там решения, кажется, не используют определение клики, которую я хочу, чтобы каждая вершина была связана с каждой другой вершиной внутри клики.

Здесь - это алгоритмЯ нашел с помощью Java.Надеюсь, это поможет в реализации с использованием SQL.

Answer 1

Несколько раз назад мне нужно было создавать кластеры данных с использованием транзитивного замыкания. Лучший способ сделать это - использовать SQLCLR. Вот код GitHub (ссылка на статью также есть)

https://github.com/yorek/non-scalar-uda-transitive-closure

Это может быть хорошей отправной точкой. Можете ли вы также уточнить, каков ожидаемый результат с входными данными, которые у вас есть в образце?

Answer 2

Вот решение.Он основан на идее, что полный граф содержит все возможные комбинации его подграфов.Код здесь, я подробно прокомментирую его на выходных, но на тот случай, если я не смог, по крайней мере, у вас есть код прямо в понедельник.Имейте в виду, что это довольно грубый подход, и если вам нужен график больше 30 узлов, он не будет работать.Тем не менее, я думаю, что это хороший образец "бокового мышления".Наслаждайтесь:

/*
    Create table holding graph data.
    Id1 and Id2 represent the vertex of the graph.
    (Id1, Id2) represent and edge.

    /9730249/neskolko-samopodsoedinenii-dlya-poiska-tranzitivnyh-podmnozhestv-klik#9730251
*/
DROP TABLE IF EXISTS #Graph;
CREATE TABLE #Graph (Id1 INT, Id2 INT);
INSERT INTO 
    #Graph
VALUES
    (1,2)
    ,(1,3)
    ,(1,4)
    ,(2,3)
    ,(2,4)
    ,(5,1)
    --,(4,3) -- Uncomment this to create a complete subgraph of 4 vertex
;
GO

/*
    Create Numbers Table
*/
DROP TABLE IF EXISTS #Numbers;
SELECT TOP (100000)
    ROW_NUMBER() OVER(ORDER BY A.[object_id]) AS Num
INTO 
    #Numbers
FROM 
    sys.[all_columns] a CROSS JOIN sys.[all_columns] b
ORDER BY 
    Num
GO

/*
    Make sure Id1 is always lower then Id2.
    This can be done as the graph is undirected
*/

DROP TABLE IF EXISTS #Graph2;
SELECT DISTINCT
    CASE WHEN Id1<Id2 THEN Id1 ELSE Id2 END AS Id1,  
    CASE WHEN Id1<Id2 THEN Id2 ELSE Id1 END AS Id2  
INTO
    #Graph2
FROM 
    #Graph;
GO

/*
    Turn edges into single columns
*/
DROP TABLE IF EXISTS #Graph3;
SELECT 
    CAST(Id1 AS VARCHAR(MAX)) + '>'  + CAST(Id2 AS VARCHAR(MAX)) COLLATE Latin1_General_BIN2 AS [Edge] 
INTO 
    #Graph3 
FROM 
    #Graph2;

/*
    Get the list of all the unique vertexes
*/
DROP TABLE IF EXISTS #Vertex;
WITH cte AS
(
    SELECT Id1 AS Id FROM #Graph
    UNION 
    SELECT Id2 AS Id FROM #Graph
)
SELECT * INTO #Vertex FROM cte;

/*
    Given a complete graph with "n" vertexes, 
    calculate all the possibile complete cyclic subgraphs
*/
-- From https://stackoverflow.com/questions/3686062/generate-all-combinations-in-sql
-- And changed to return all combinations complete cyclic subgraphs 
DROP TABLE IF EXISTS #AllCyclicVertex;
DECLARE @VertexCount INT = (SELECT COUNT(*) FROM [#Vertex]);
WITH Nums AS 
(
    SELECT 
        Num
    FROM 
        #Numbers
    WHERE 
        Num BETWEEN 0 AND POWER(2, @VertexCount) - 1
), BaseSet AS 
(
    SELECT 
        I = POWER(2, ROW_NUMBER() OVER (ORDER BY [Id]) - 1), *
   FROM 
        [#Vertex]
), Combos AS 
(
    SELECT
        CombId = N.Num,
        S.Id,
        K = COUNT(*) OVER (PARTITION BY N.Num)
   FROM
        Nums AS N
    INNER JOIN 
        BaseSet AS S ON N.Num & S.I <> 0
)
SELECT
    DENSE_RANK() OVER (ORDER BY K, [CombID]) AS CombNum,
    K,
    Id
INTO
    #AllCyclicVertex
FROM 
    Combos
WHERE 
    K BETWEEN 3 AND @VertexCount
ORDER BY 
    CombNum, Id;
GO

--SELECT * FROM [#AllCyclicVertex]

/*
    Calculate the edges for the calculated cyclic graphs
*/
DROP TABLE IF EXISTS #WellKnownPatterns;
CREATE TABLE #WellKnownPatterns ([Name] VARCHAR(100), [Id1] INT, [Id2] INT, [Edge] VARCHAR(100) COLLATE Latin1_General_BIN2);

INSERT INTO #WellKnownPatterns 
    ([Name], [Id1], [Id2], [Edge])
SELECT 
    CAST(a.[CombNum] AS VARCHAR(100)) + '/' + CAST(a.[K] AS VARCHAR(100)),
    a.Id AS Id1, 
    b.Id AS Id2,
    CAST(a.[Id] AS VARCHAR(MAX)) + '>'  + CAST(b.[Id] AS VARCHAR(MAX)) AS [Edge]
FROM 
    #AllCyclicVertex a 
INNER JOIN 
    #AllCyclicVertex b ON b.id > a.id AND a.[CombNum] = b.[CombNum]
;

-- SELECT * FROM [#WellKnownPatterns]

/*
    Now take from the original set only those 
    who are EXACT RELATIONAL DIVISION of a well-known cyclic graph
*/

WITH cte AS
(
    SELECT * FROM #Graph3
),
cte2 AS 
(
    SELECT 
        COUNT(*) OVER (PARTITION BY [Name]) AS [EdgeCount],
        * 
    FROM 
        #WellKnownPatterns
)
SELECT
    T1.[Name]
FROM
    cte2 AS T1
LEFT OUTER JOIN
    cte AS S ON T1.[Edge] = S.[Edge]
GROUP BY
    T1.[Name]
HAVING 
    COUNT(S.[Edge]) = MIN(T1.[EdgeCount])
GO

-- Test a solution
SELECT * FROM [#WellKnownPatterns] WHERE [Name] = '1/3'