Postgres 父子网络 ID

Question

我需要计算相互依存对象的网络。对于每个 E-C link，我需要额外的列，即这些对象所属的“唯一网络 ID”。例子来自金融业，其中贷款被link提供给他们资助的对象。

create table ec (
    e varchar(10),
    c varchar(10)
);

insert into ec values ('E1','C1');
insert into ec values ('E1','C2');
insert into ec values ('E1','C3');
insert into ec values ('E2','C3');
insert into ec values ('E3','C3');
insert into ec values ('E3','C4');
insert into ec values ('E4','C5');
insert into ec values ('E4','C6');

并且输出应该是以下之一：

+--------+--------+------------+
| EXP_ID | CRM_ID | NETWORK_ID |
+--------+--------+------------+
| E1     | C1     |          1 |
| E1     | C2     |          1 |
| E1     | C3     |          1 |
| E2     | C3     |          1 |
| E3     | C3     |          1 |
| E3     | C4     |          1 |
| E4     | C5     |          2 |
| E4     | C6     |          2 |
+--------+--------+------------+

或：

+----+------------+
| ID | NETWORK_ID |
+----+------------+
| E1 |          1 |
| E1 |          1 |
| E1 |          1 |
| E2 |          1 |
| E3 |          1 |
| E3 |          1 |
| C1 |          1 |
| C2 |          1 |
| C3 |          1 |
| C3 |          1 |
| C3 |          1 |
| C4 |          1 |
| E4 |          2 |
| C5 |          2 |
| C6 |          2 |
+----+------------+

视觉连接可以这样看：

我一直在研究递归查询，但我不确定这是否是正确的方法。那么，递归查询是一种实现这一目标的方法吗？我应该多考虑一下吗？还是需要其他类似图形分析的东西？

Answer 1

是的，递归查询可以实现这一点。这是一个概念证明，它计算每条边的可到达边的传递集（即网络中的所有边），由给定边的 id 键控，然后取最小的（id of the）边作为代表网络，对于每条边：

WITH RECURSIVE eci AS (
  SELECT row_number() OVER () AS id, * FROM ec
),
networks AS (
  SELECT * FROM eci
UNION
  SELECT LEAST(eci.id, n.id), eci.e, eci.c FROM eci JOIN networks n ON n.e = eci.e OR n.c = eci.c
)
SELECT min(id), ec.e, ec.c FROM ec JOIN networks USING (e, c) GROUP BY e, c;

^{(dbfiddle demo)}

免责声明：我怀疑这是否有效。我试过但未能在递归期间修剪 networks。

Answer 2

我一直在考虑不同的想法，试图减少跨大型网络所需的工作。

我玩过数组，我被 Recurives CTE 阻止了，不允许聚合或多次引用递归表达式 （不将 CTE 连接到自身）.

我目前的 'best' 尝试试图将问题作为递归组合集来解决。如果：

两组共用一个成员(c)
'other' 集有一个 'lower' 标识符

我希望这意味着最坏的情况是二进制模式； 1024 行最多需要 10 的递归深度 （1024 组变成 512，变成 256，等等）.

我考虑这个的原因是@Bergi 的 anser 有一个最坏的情况，即 1024 个节点需要 1023 的递归深度。

然而，相反地，我的方法最终需要 （我认为） 每次迭代都需要更多的努力。我很想知道哪个在更大的数据集上表现更好。

我不是说 Bergi 的不好
我不是说我的更好
我只是说他们不一样

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=b77940437835bb839ea3c92b05b686e9

WITH RECURSIVE
  groups AS
(
  SELECT
    e,
    c,
    DENSE_RANK() OVER (ORDER BY e) AS group_id,
    0                              AS search_depth,
    COUNT(*) OVER ()               AS total_changes
  FROM
    ec

  UNION ALL

  SELECT
    e,
    c,
    new_group_id               AS group_id,
    search_depth + 1           AS search_depth,
    SUM(has_changed) OVER ()   AS total_changes
  FROM
  (
    SELECT
      e, c, group_id, search_depth, new_group_id,
      CASE WHEN group_id = new_group_id THEN 0 ELSE 1 END  AS has_changed
    FROM
    (
      SELECT
        e, c, group_id, search_depth,
        MIN(new_group_id) OVER (PARTITION BY group_id) AS new_group_id
      FROM
      (
        SELECT
          e, c, group_id, search_depth,
          MIN(group_id) OVER (PARTITION BY c) AS new_group_id
        FROM
          groups
        WHERE
          total_changes > 0
      )
        combine_by_c
    )
      combine_by_group
  )
    tally_changes
)
SELECT * FROM groups WHERE total_changes = 0

编辑：

加上两次尝试识别不可能进一步增长的组，并将它们排除在进一步的迭代之外。

根据数据的概况，这可能比节省更多的精力（大多数组需要类似的递归深度），或者它可能有帮助（需要递归深度的大变化）...

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=0710b63cb39fe92e08156a486c5f2216

Postgres 父子网络 ID

Postgres parent - child network id

sql

postgresql

graph-theory