sql - 在 PostgreSQL 中创建最佳图形关系

Question

我在 PostgreSQL 中有一个表，它包含两列，第一个 ID 和第二个 ID。其中的每一项都意味着第一个ID和第二个ID之间存在关系，并且可以保证第一个ID总是大于第二个ID。

我的目标是处理表格，以便它可以检测网络(相互关联的多个 ID)，并更改表格中该网络的每个关系，以便第一个 ID 是网络中的大 ID，第二个ID始终是网络中最小的ID。
示例:

D->C , C->B , B->A , F->E , H->G

将成为:

D->A , C->A , B->A , F->E , H->G

另一个例子:

D->C , D->B , D->A

将成为:

D->A , C->A , B->A

如何使用 SQL 或 Postgres 过程语言来做到这一点？

编辑:我使用的 PostgreSQL 版本是 9.4。该表由列id1(整数)和id2(整数)组成，它们都是主键。

关于如何断定A是第二个例子集合(A,B,C)中最小的，我用这个查询来确定最小的id2

SELECT id1, MIN(id2) FROM table GROUP BY id1

Answer 1

假设有这样一张表:

CREATE TABLE tbl (
  id1 int
, id2 int
, PRIMARY KEY (id1, id2)
);

根据您的逻辑，循环引用是不可能的。

这recursive CTE会做的工作:

WITH RECURSIVE cte AS (
   SELECT t1.id1, t1.id2, t2.id2 AS next_id2
   FROM   tbl t1
   LEFT   JOIN tbl t2 ON t2.id1 = t1.id2

   UNION ALL
   SELECT t1.id1, t1.next_id2, t2.id2
   FROM   cte t1
   LEFT   JOIN tbl t2 ON t2.id1 = t1.next_id2
   WHERE  t1.next_id2 IS NOT NULL  -- stop iterating at end of graph
   )
SELECT id1, id2
FROM   cte
WHERE  next_id2 IS NULL;  -- only rows where the graph ends

在非递归术语中，选择每一行 并尝试使用LEFT JOIN 找到下一步。

在递归项中，用下一步替换第二个 ID，直到我们到达图的末尾(next_id2 IS NULL)。

在外部 SELECT 中只返回图表结束的行。以任意排序顺序产生结果。

如果图可以 fork ，您还不清楚如何确定最深的兔子洞。