4

试图弄清楚如何查询通过自引用多对多表连接的不同实体组。整个下午都在戳它，以为我会在这里问一下，看看其他人是否有一些想法。

例如，一个 Person 有一组朋友，而这些组是排他的（即组之间没有重叠——如果你愿意的话，是一堆派系）。表结构可能如下所示：

person
| id | name |
| 1  | bob  |
| 2  | frank |
| 3  | chuck |
| 4  | nancy |
| 5  | alice |
| 6  | sally |

cliques
| from_person_id | to_person_id |
|       1        |      2       |
|       1        |      3       |
|       2        |      1       |
|       2        |      3       |
|       3        |      1       |
|       3        |      2       |
|       4        |      5       |
|       4        |      6       |
|       5        |      4       |
|       5        |      6       |
|       6        |      4       |
|       6        |      5       |

（Bob 是 Frank 和 Chuck 的朋友，Frank 是 Bob 和 Chuck 的朋友，Chuck 是 Bob 和 Frank 的朋友，等等）

我可以得到一堆与每个人的朋友相关的集合，但不知道如何将其归结。最终，我真正想要的是一个返回不同集团成员集的查询，例如

| cliques |
| 1, 2, 3 |
| 4, 5, 6 |

但是，当然，除非我使用 group_concat (MySQL) 或 array_agg (PostgreSQL) 之类的东西，否则 SQL 不会那样工作。我并不严格反对这种方法，但我更愿意避免引入特定于后端的实现（我实际上使用的是 Django 的 ORM，但不想分散这些细节的注意力）。

我的问题是：

  • 尝试以这种方式建模事物时，我是否在吠叫错误的树？
  • 有没有办法在调用代码中不诉诸迭代来组装不同的派系？我不是要求每个 clique 有一行，因为这需要特定于 db 的聚合，但可能需要生成的 id-per-clique 和一组 (clique_id, member_id) 元组，然后我可以在调用代码中组装它们？
4

1 回答 1

0

如果您正在寻找连接的子图，这是一种方法。

您可以通过其中任何节点的最小 id 来表征连接子图。

从存储子图 id 的表开始，例如：

create table subgraphids (
     personid int,
     subgraphid int
);

初始化它：

insert into subgraphids(personid, subgraphid)
    select personid, min(subgraphid)
    from (select from_person_id as personid,
                 least(from_person_id, to_person_id) as subgraphid
          from cliques
          union all
          select to_person_id, least(from_person_id, to_person_id)
          from cliques
         ) t
    group by personid;

现在你有了试探性的子图。要更新它们，您可以使用类似的查询：

update subgraphid
    set subgraphid = (select min(s.subgraphid)
                      from cliques c join
                           subgraphid s
                           on c.from_person_id = s.personid or
                              c.to_person_id = s.personid
                      where subgraphid.personid = clique.from_person_id or
                            subgraphid.personid = click.to_person_id
                     );

重复此操作，直到没有更新任何行。您可以明确检查该条件：

select count(*)
from subgraphid
where subgraphid > (select min(s.subgraphid)
                    from cliques c join
                         subgraphid s
                         on c.from_person_id = s.personid or
                            c.to_person_id = s.personid
                    where subgraphid.personid = clique.from_person_id or
                          subgraphid.personid = click.to_person_id
                   );

这将在您的原始图中找到连接的子图。迭代需要在 SQL 之外的调用代码中进行。

于 2013-03-31T22:44:20.110 回答