从点和关系形成三角形

Question

我想从点生成三角形并在它们之间生成可选关系.并非所有点都形成三角形,但其中很多都有.

在初始结构中,我有一个包含以下表的数据库:

节点(id,value)
关系(id,nodeA,nodeB,value)
三角形(id,relation1_id,relation2_id,relation3_id)

为了从节点和关系表生成三角形,我使用了以下查询:

INSERT INTO Triangles
SELECT t1.id, t2.id , t3.id, 
FROM Relations t1, Relations t2, Relations t3
WHERE t1.id < t2.id AND t3.id > t1.id AND
(
t1.nodeA = t2.nodeA 
AND (t3.nodeA = t1.nodeB AND t3.nodeB = t2.nodeB
OR t3.nodeA = t2.nodeB AND t3.nodeB = t1.nodeB)

OR 

t1.nodeA = t2.nodeB
AND (t3.nodeA = t1.nodeB AND t3.nodeB = t2.nodeA
OR t3.nodeA = t2.nodeA AND t3.nodeB = t1.nodeB)
)

它完美地适用于小型数据.(〜<50分)然而,在某些情况下,我得到了大约100分,彼此相关,导致成千上万的关系.因此,当预期的三角形数量达到数十万甚至数百万时,查询可能需要几个小时.

我的主要问题不在于select查询,而我看到它在Management Studio中执行,返回的结果很慢.我每分钟收到大约2000行,这对我来说是不可接受的.

作为事实上,业务的规模正在加起来exponentionally和被可怕影响性能.

我已经尝试过将它作为LINQ从我的代码中反对,但性能更差.

我也试过在C#的读卡器上使用SqlBulkCopy来获得结果,也没有运气.

所以问题是......任何想法或解决方法？

Answer 1

我想你只需要这个：

INSERT
INTO    triangles (relation1_id, relation2_id, relation3_id)
SELECT  r12.id, r23.id, r13.id
FROM    relations r12
JOIN    relations r23
ON      r23.nodeA = r12.nodeB
JOIN    relations r13
ON      r13.nodeA = r12.nodeA
        AND r13.nodeB = r23.nodeB
ON      r12.nodeA = n1.id
WHERE   NOT EXISTS
        (
        SELECT  relation1_id, relation2_id, relation3_id
        FROM    triangles
        INTERSECT
        SELECT  r12.id, r23.id, r13.id
        )

进行以下检查约束：

ALTER TABLE relations ADD CONSTRAINT CHECK (nodeA < nodeB)

这一点是，由于它们relations是对称的，因此您只需要每对存储一次关系，每次排列存储一次三角形。

检查约束确保关系按固定顺序每对存储一次。

查询的设计使得三角形也按固定顺序存储：首先是 1 - 3，第二是 2 - 3，第三是 1 - 3，其中 1、2 和 3 由关系链接的节点的顺序确定。

另请注意，三角形的数量按 增长O(n^3)，而不是指数增长 ( O(exp(N)))。

对于100节点来说，最多可以有100 * 99 * 98 / 6 = 161700三角形。