代码之家 › 专栏 › 技术社区 › SiN

从点和关系形成三角形

sql-server sql c#

SiN · 技术社区 · 15 年前

我想从点和它们之间的可选关系生成三角形。并不是所有的点都形成三角形,但其中许多形成三角形。

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

节点(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查询中,当我看到它在managementstudio中执行时,返回的结果很慢。我每分钟收到约2000行,这对我的情况是不可接受的。

事实上,业务的规模正在增加指数

我也尝试过在C的阅读器上使用SqlBulkCopy,但也没有成功。

所以问题是。。。有什么想法或解决办法吗?

2 回复 | 直到 15 年前

Quassnoi 15 年前

我想你只需要这个:

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 如果是对称的,则每对只需存储一次关系,每排列只需存储一次三角形。

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

该查询的设计使三角形也按固定顺序存储:1-3第一、2-3第二、1-3第三,其中1、2和3由连接的节点顺序决定。

还请注意,三角形的数量随着 O(n^3) ,而不是指数( O(exp(N)) ).

100 节点,最多可以有 100 * 99 * 98 / 6 = 161700 三角形。

Mark Nelson 15 年前

“t1.id<t2.id和t3.id>t1.id“不能阻止t2=t3。将此更改为“WHERE t1.id<t2.id和t3.id>t2.id“

卡斯尼的解决方案看起来很有希望。它也有问题。首先,它是将节点ID而不是关系ID选择为三角形。其次,它没有检查n1和n3之间是否存在关系。我把这句话改写为:

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

该解决方案不依赖于关系表中ID排序的任何约束,也不保证三角形表中ID的任何排序。