В SQL, как разрешить переходные наборы членства?

Question

Учитывая эту таблицу идентификаторов:

╔═══════╤═══════╗
║ tid_1 │ tid_2 ║
╠═══════╪═══════╣
║     1 │     2 ║
║     1 │     9 ║
║     1 │    10 ║
║     2 │     9 ║
║     2 │    10 ║
║     3 │     4 ║
║     9 │    10 ║
║     9 │    12 ║
║     9 │    14 ║
║    12 │    14 ║
╚═══════╧═══════╝

и при условии, что в каждой строке есть метки наборов, которые считаются эквивалентными, как я могу (в PostgreSQL) найти транзитивный набор эквивалентностей?

Другими словами, я знаю, что вещи в коробке 14 можно выбросить вместе с вещи в коробке 12; вещи в коробке 12 с вещами в коробке 9; и коробка 9, в свою очередь ничем не отличается от вещей в коробках 2 и 1.

Затем я хочу пойти и назначить новый идентификатор набора (например, используя наименьший идентификатор из переходная группа) так что я получаю

╔═══════╤═══════╗
║   tid │   sid ║
╠═══════╪═══════╣
║     1 │     1 ║
║     2 │     1 ║
║     3 │     3 ║
║     4 │     3 ║
║     9 │     1 ║
║    10 │     1 ║
║    12 │     1 ║
║    14 │     1 ║
╚═══════╧═══════╝

Мне удалось подойти к этому моменту, который, как я полагаю, является частью решения:

create view transitive_closure as (
  with recursive containment as ( select
    p1.tid_1                          as tid_1,
    p1.tid_2                          as tid_2,
    array[ p1.tid_1 ]                 as chain,
    false                             as is_cyclic
  from links                          as p1
union all
select distinct
    p2.tid_1                          as tid_1,
    p2.tid_2                          as tid_2,
    tc.chain || p2.tid_1              as chain,
    p2.tid_2 = any( chain )           as is_cyclic
  from links as p2
  join containment as tc on ( p2.tid_1 = tc.tid_2 )
  )
select distinct tid_1, tid_3 as tid_2 from containment );

Answer 1

Да, вы очень близки, вам просто нужно проверить и выполнить в своем рекурсивном запросе самый низкий tid, ограничить первую половину рекурсивного запроса корневыми узлами, использовать проверку is_cyclic в качестве условия остановки во втором наполовину и, наконец, выведите объединение столбцов tid_1 и tid_2 вместе с sid:

SQL Fiddle :

with recursive containment as ( 
  select p1.tid_1 as tid_1,
         p1.tid_2 as tid_2,
         case when p1.tid_1 < p1.tid_2
              then p1.tid_1
              else p1.tid_2
          end sid,
          array[ p1.tid_1 ] as chain,
          false as is_cyclic
  from links as p1
 where not exists (select 1 from links l where l.tid_2 = p1.tid_1)
union all
  select p2.tid_1 as tid_1,
         p2.tid_2 as tid_2,
         case when tc.sid < p2.tid_1
               and tc.sid < p2.tid_2
              then tc.sid
              when p2.tid_1 < p2.tid_2
              then p2.tid_1
              else p2.tid_2
         end sid,
         tc.chain || p2.tid_1 as chain,
         p2.tid_2 = any( chain ) as is_cyclic
    from links as p2
    join containment as tc on ( p2.tid_1 = tc.tid_2 )
   where not tc.is_cyclic
)
select tid_1, sid from containment
union
select tid_2, sid from containment

Результаты :

| tid_1 | sid |
|-------|-----|
|     1 |   1 |
|     2 |   1 |
|     3 |   3 |
|     4 |   3 |
|     9 |   1 |
|    10 |   1 |
|    12 |   1 |
|    14 |   1 |