Pengelompokan SQL baris yang saling berpotongan/tumpang tindih

Dengan asumsi bahwa semua pasangan ada dalam kombinasi cermin mereka juga (4,5) dan (5,4) . Tetapi solusi berikut ini juga berfungsi tanpa penipuan yang dicerminkan.

Kasus sederhana

Semua koneksi dapat diatur dalam satu urutan menaik dan komplikasi seperti yang saya tambahkan di biola tidak mungkin, kita dapat menggunakan solusi ini tanpa duplikat di rCTE:

Saya mulai dengan mendapatkan minimum a_sno per grup, dengan minimum terkait b_sno :

SELECT row_number() OVER (ORDER BY a_sno) AS grp
     , a_sno, min(b_sno) AS b_sno
FROM   data d
WHERE  a_sno < b_sno
AND    NOT EXISTS (
   SELECT 1 FROM data
   WHERE  b_sno = d.a_sno
   AND    a_sno < b_sno
   )
GROUP  BY a_sno;

Ini hanya membutuhkan satu tingkat kueri karena fungsi jendela dapat dibangun secara agregat:

• Dapatkan jumlah yang berbeda dari kolom tabel yang digabungkan

Hasil:

grp  a_sno  b_sno
1    4      5
2    9      10
3    11     15

Saya menghindari cabang dan baris yang digandakan (digandakan) - berpotensi banyak lebih mahal dengan rantai panjang. Saya menggunakan ORDER BY b_sno LIMIT 1 dalam subkueri berkorelasi untuk membuat ini terbang dalam CTE rekursif.

• Buat indeks unik pada kolom non-unik

Kunci kinerja adalah indeks yang cocok, yang sudah ada yang disediakan oleh batasan PK PRIMARY KEY (a_sno,b_sno) :bukan sebaliknya (b_sno, a_sno) :

• Apakah indeks komposit juga bagus untuk kueri di kolom pertama?

WITH RECURSIVE t AS (
   SELECT row_number() OVER (ORDER BY d.a_sno) AS grp
        , a_sno, min(b_sno) AS b_sno  -- the smallest one
   FROM   data d
   WHERE  a_sno < b_sno
   AND    NOT EXISTS (
      SELECT 1 FROM data
      WHERE  b_sno = d.a_sno
      AND    a_sno < b_sno
      )
   GROUP  BY a_sno
   )

, cte AS (
   SELECT grp, b_sno AS sno FROM t

   UNION ALL
   SELECT c.grp
       , (SELECT b_sno  -- correlated subquery
          FROM   data
          WHERE  a_sno = c.sno
          AND    a_sno < b_sno
          ORDER  BY b_sno
          LIMIT  1)
   FROM   cte  c
   WHERE  c.sno IS NOT NULL
   )
SELECT * FROM cte
WHERE  sno IS NOT NULL   -- eliminate row with NULL
UNION  ALL               -- no duplicates
SELECT grp, a_sno FROM t
ORDER  BY grp, sno;

Kasus yang kurang sederhana

Semua node dapat dicapai dalam urutan menaik dengan satu atau lebih cabang dari root (sno terkecil ).

Kali ini, dapatkan semua sno greater yang lebih besar dan hapus duplikat node yang dapat dikunjungi beberapa kali dengan UNION di akhir:

WITH RECURSIVE t AS (
   SELECT rank() OVER (ORDER BY d.a_sno) AS grp
        , a_sno, b_sno  -- get all rows for smallest a_sno
   FROM   data d
   WHERE  a_sno < b_sno
   AND    NOT EXISTS (
      SELECT 1 FROM data
      WHERE  b_sno = d.a_sno
      AND    a_sno < b_sno
      )
   )   
, cte AS (
   SELECT grp, b_sno AS sno FROM t

   UNION ALL
   SELECT c.grp, d.b_sno
   FROM   cte  c
   JOIN   data d ON d.a_sno = c.sno
                AND d.a_sno < d.b_sno  -- join to all connected rows
   )
SELECT grp, sno FROM cte
UNION                     -- eliminate duplicates
SELECT grp, a_sno FROM t  -- add first rows
ORDER  BY grp, sno;

Tidak seperti solusi pertama, kami tidak mendapatkan baris terakhir dengan NULL di sini (disebabkan oleh subquery yang berkorelasi).

Keduanya harus berkinerja sangat baik - terutama dengan rantai panjang / banyak cabang. Hasil sesuai keinginan:

SQL Fiddle (dengan baris tambahan untuk menunjukkan kesulitan).

Grafik tak berarah

Jika ada minimum lokal yang tidak dapat dicapai dari root dengan traversal menaik, solusi di atas tidak akan berfungsi. Pertimbangkan solusi Farhęg dalam hal ini.