將條目連結到組中

我有一個項目對錶，它將一個項目與另一個項目聯繫起來。我想將這些項目分組，以便任何連結在一起的項目，即使是間接連結，都在同一個組中。所以：

person1| person2
-------+--------
john   | george
george | paul
george | ringo
ringo  | paul
brian  | mick
brian  | keith
keith  | bill
mick   | charlie

為此，假設表模式只是：

create table pairs 
 ( person1 varchar not null,
   person2 varchar not null,
   primary key (item1, item2)
 ) ;
create table p2g (person varchar not null, groupid int);
create table group (groupid integer primary key)

它顯然比這更複雜。

所以john與george相關聯，george與paul和ringo相關聯，ringo與paul相關聯；這些是一個獨立的群體。（注意 ringo<->paul 連結在這裡實際上是多餘的；我們不需要它來創建組，但它仍然存在。）同樣，brian/mick/keith/bill/charlie 是一個組。人是唯一的（我們在這裡使用 varchar 名稱以使解釋更清楚，但實際上人是由唯一的 ID 標識的）。所以我想要的是將所有這些組合在一起的某種方式，這樣我就能夠創建看起來像

person  | group
--------+------
john    | 1
george  | 1
paul    | 1
ringo   | 1
brian   | 2
charlie | 2
keith   | 2
mick    | 2
bill    | 2

顯然可以逐行遍歷配對錶（這就是我正在做的事情），但是對於很多配對來說這非常慢。我正在使用的算法是這樣的：

for person1, person2 in pairs:
   group1 = db.exec("select groupid from p2g where person=:person1")
   group2 = db.exec("select groupid from p2g where person=:person2")
   if not group1 and not group2:
       # invent a new group; add person1 and person2 to it
       newgroupid = db.exec("insert into group (null)")
       db.exec("insert into p2g (:newgroupid, :person1)")
       db.exec("insert into p2g (:newgroupid, :person2)")
   else if not group1:
       # add person1 to group2
       db.exec("insert into p2g (:group2, :person1)")
   else if not group2:
       # add person2 to group1
       db.exec("insert into p2g (:group1, :person2)")
   else if group1 == group2:
       nothing to do here, everything's already OK
   else:
       # they're in two different groups. 
       # Put everyone in group2 into group1
       # and delete group2
       db.exec("update p2g set groupid=:group1 where groupid=:group2")
       db.exec("delete from group where groupid=:group2")

但我覺得有一種更 SQLish 的方式可以分批或一次性完成，而不是每行一次。有沒有？（我正在使用 SQLite，如果這有所作為。）

我已經嘗試過為此使用遞歸 CTE，它可以工作，但不能。這個單一的查詢：

with bands (member, leader) as (
   select item1, item1 from pairs 
   union all 
   select p.item2, b.leader 
       from pairs p 
       inner join bands b on b.member=p.item1
) select distinct 'group:'||leader, member from bands order by leader

給出作為輸出

group:john  | john
group:john  | george
group:john  | paul
group:john  | ringo
group:mick  | mick
group:mick  | charlie
group:mick  | keith
group:paul  | paul
group:paul  | ringo
group:paul  | george
group:ringo | ringo
group:ringo | george

這幾乎是正確的：johnandmick組是正確的！但它也包含其他“組”，從其他成員開始，我不知道如何不包括這些。這似乎是正確的方法，但並不完全存在。（另外，如果pairs表還包含“ringo -> john”，即人鍊是循環的，那麼上面的查詢永遠執行，這也不好。）

您的 CTE 的輸出不一致：john, paul, 並且ringo有不同數量的樂隊成員。您應該在兩個方向上遍歷這些對（然後使用 UNION 來防止重複和無限循環）：

with bands (member, leader) as (
   select item1, item2 from pairs
   union
   select item2, item1 from pairs
   union
   select ... -- recursion
) ...

現在，您擁有了所有可能的領導者和樂隊成員組合，但您希望每個樂隊只有一個（隨機但唯一的）領導者。因此，對於具有相同樂隊成員的所有行，選擇具有最小領導者的行：

with bands as (...)
select 'group:'||min(leader), member
from bands
group by member
order by min(leader);

引用自：https://dba.stackexchange.com/questions/203302