查询图结构的SQL（传递闭包问题）

Question

我们有一个表格，用于跟踪客户使用的所有礼品卡。这是多对多的关系，一个客户可以使用多张礼品卡，一张礼品卡可以被多个客户使用（部分余额等）

我们需要创建一个数据库视图，可以将这种多对多关联捕获为一个网络（即单个记录）。单个记录应包含所有使用过这些礼品卡的客户的所有礼品卡。

我不知道如何在 SQL 中实现这个。请指教。

客户ID	礼品卡帐号
AAA	1111
BBB	1111
AAA	2222
CCC	2222
DD	3333

我们需要在视图中显示的信息：

客户 ID	礼品卡账户号码
AAA、BBB、CCC	1111；2222
DD	3333；

Answer 1

参见示例（PostgreSql 和 BigQuery）。
想法是

1. 从每个节点（kern）沿着所有路径遍历无向图。在这里可以优化选择合适的节点来遍历图。
2. 为每个紧排组合（分组）路径。每个封闭的完整组只能有一个节点组合。
3. 我们只留下独特的路径。

有测试数据

with recursive gifts as(
  select 'AAA' CustomerId, 1111 GiftCardsAcctNumber 
  union all select 'BBB',1111
  union all select 'AAA',2222
  union all select 'CCC',2222
  union all select 'DDD',3333
  union all select 'EEE',4444
  union all select 'FFF',1111
  union all select 'FFF',4444
)

和递归查询

, r as(
  select 0 lvl,t1.CustomerId kern,t1.CustomerId,t1.GiftCardsAcctNumber GiftId
     ,concat(t1.CustomerId,'-') custS
     ,concat(t1.GiftCardsAcctNumber,'-') giftS
  from gifts t1  
  union all
  select lvl+1,r.kern,g.CustomerId
    ,case when g.GiftCardsAcctNumber=r.GiftId then r.GiftId
     else g.GiftCardsAcctNumber 
     end GiftId
    ,case when g.GiftCardsAcctNumber=r.GiftId then concat(r.custS,'-',g.CustomerId)
     else  r.custS
     end custS
    ,case when g.CustomerId=r.CustomerId then concat(r.giftS,'-',g.GiftCardsAcctNumber) 
     else r.giftS
     end giftS
  from r inner join gifts g 
    on (g.GiftCardsAcctNumber=r.GiftId and g.CustomerId<>r.CustomerId 
         and r.custS not like concat('%',g.CustomerId,'%'))
      or (g.CustomerId=r.CustomerId and g.GiftCardsAcctNumber<>r.GiftId 
           and r.giftS not like concat('%',g.GiftCardsAcctNumber,'%'))
  where (g.CustomerId<>r.CustomerId or g.GiftCardsAcctNumber<>r.GiftId)
)
select distinct cs,gs
from(
  select kern,string_agg(distinct customerId,'-' order by customerid) cs
    ,string_agg(distinct giftId,'-' order by giftid) gs
  from(                                    -- varchar  
     select kern,customerid,cast(giftId as string) giftid
     from( select * from r  )x
     group by kern,customerid,giftid
  ) y
  group by kern
)z

行	CS	gs
1	AAA-BBB-CCC-EEE-FFF	1111-2222-4444
2	DD	3333

请解释一下