处理复杂关系的 SQL 查询

Question

我有一个场景，我有大量的博客。这些博客都有多个帖子。每篇博客文章都可以链接到另一个博客上的一篇文章，但它们随后决不能从该博客链接回链接博客。

澄清一下:

• 站点 A 链接到站点 B(并且可以链接到其他站点)
• 然后站点 B 不能链接到站点 A(但可以链接到其他站点)

每次发布​​帖子时，我都会存储帖子的 ID 和它链接到的网站的 ID。重要的是要记住，一旦单个帖子链接到另一个网站上的任何帖子，其他网站就无法从任何地方链接回来，而不仅仅是链接到的帖子。

站点 A 可以多次链接到站点 B，并且每个帖子都可以链接到多个其他帖子。一个示例场景可能是:

• 站点 A 链接到站点 B
• 站点 C 链接到站点 B
• 站点 D 链接到站点 A

在上面的数据中:

• 站点 A 可以链接到站点 C(或再次链接到站点 B)
• 站点 B 可以链接到站点 D
• 站点 C 可以链接到站点 A 或站点 D(或再次链接到站点 B)
• 站点 D 可以链接到站点 B 或站点 C(或再次链接到站点 A)

这是一些测试数据的链接和所需的 2 个表的转储: http://pastie.org/1506715

我想我需要一个交叉连接来获得所有可能的链接组合，然后考虑现有的关系以防止站点反向链接到相反的方向。到目前为止我的查询是:

SELECT 
t1.* , t2.* FROM test_posts t1, test_posts as t2
WHERE
t1.post_id != t2.post_id
ORDER BY
t1.post_id, t2.post_id;

这给了我帖子之间所有可能的关系。我正在努力解决的是如何排除与上述规则相矛盾的关系。之前的关系记录在 test_smartlinks_to_websites 表中，其中 post_id 属于“原始”网站，而 website_id 属于“目标”网站(请记住，这种关系实际上是网站之间的单向关系，而不是帖子之间的关系)。

我尝试过使用 NOT EXISTS 子查询，但我不确定确切的子句(或者这是否是正确的方法)。

Answer 1

如果我错了请纠正我。看来您的任务是确定有向图中的循环。它并不像看起来那么复杂。请参阅此博客文章以了解它是如何在 SQL 中完成的:http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/ .另请参阅此链接以了解 SQL 中的广度优先搜索:http://willets.org/sqlgraphs.html .

已编辑:添加图像以清晰和理解有向无环图和有环图。

例如，这里有一些类似于您的情况。它不是单个图，而是一组图(如果它们是树，则为森林)。注意没有共同的根。它只是以某种方式连接的节点。在较大的子图中有一个循环，节点在其中相互引用。如果去掉向上的链接，子图就变成无环的。