Multiple Self-Joins to Find Transitive Subsets (cliques)

Question

In simplest terms, I have a table representing a relation. Rows in the table represent pairs in my relation. In other words, the first row indicates that the id of 1 is related to the id of 4 and that the id of 4 is related to the id of 1. Hopefully, it is not hard for you to see that my relation is symmetric, although the table shows this symmetry in a concise form.

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

EDIT This table is meant to concisely show the following relation:
{(1,4), (4,1), (3,1), (1,3), (2,1), (1,2), (2,3), (3,2), (2,4), (4,2), (5,1), (1,5)}. This can be visualized by the following undirected graph.

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);

I would like to identify transitive subsets (cliques) in my table.
EDIT For example, I would like to identify the transitive subset demonstrated by the fact that the id of 3 is related to the id of 1 and the id of 1 is related to the id of 2 implies that the id of 3 is related to the id of 2. (These can be seen as triangles in the undirected graph photo. Although, in the best case scenario, I would like to be able to list other complete subgraphs that are larger than triangles if they are present in the original table/graph.)

I've tried doing the following but the result set is larger than I want it to be. I hope that there is an easier way.

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
        )
    );

Actual Output:

+-----+-----+-----+-----+-----+-----+
| 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 |
+-----+-----+-----+-----+-----+-----+

The expected result set would only have two rows. Each row would represent a transitive relation that is a subset of the original relation.

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

EDIT The expected output could also look like,

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

whatever is easier. I just need to display the fact that the sets
{(1,4), (4,1), (2,4), (4,2), (2,1), (1,2)}
and
{(3,1), (1,3), (2,1), (1,2), (2,3), (3,2)}
are proper subsets of the original relation and are themselves transitive relations. I am using the definition that a relation R is transitive if and only if ∀a∀b∀c((a,b)∈R ∧ (b,c)∈R → (a,c)∈R). In other words, I am trying to find all subgraphs that are also complete graphs.

I'm new to graphy theory, but it seems like my problem is similar to the clique problem where I am looking for cliques containing 3 or more vertices. I would accept as an answer solutions that return only cliques with 3 vertices. My question is similar to this one. However, the solutions presented there don't seem to use the definition of a clique that I want where every vertex is connected to every other vertex inside of the clique.

Here is an algorithm I found using Java. Hopefully, this will help with an implementation using SQL.

Answer 1

Times ago I needed to create clusters of data using transitive closure. The best way to do that was using SQLCLR. Here's the GitHub code (article to detailed link is there too)

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

That could be a good starting point. Can you also be more precise on what is the expected result with the input data you have in the sample?

Answer 2

Here's the solution. It is based on the idea that a complete graph contains all the possible combination of its subgraphs. Code is here, I'll comment it in detail over the weekend, but it case I couldn't at least you have the code right on monday. Please be aware that this is quite a brute force approach and if you need graph bigger than 30 nodes won't work. Still I think it's a nice sample of "lateral thinking". Enjoy:

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

    https://stackoverflow.com/questions/56979737/multiple-self-joins-to-find-transitive-subsets-cliques/56979901#56979901
*/
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'