分离度查询 [英] Degrees of Separation Query

问题描述

我有一个成员对成员连接表.模式为member_id，friend_id，is_active.我想建立一个成为朋友朋友的成员的成员关系列表.我不太确定如何解决该查询，更不用说以半优化的方式了.

I have a table of member-to-member connections. The schema is member_id, friend_id, is_active. I want to build a list of member connections of people who are friends of friends. I'm not really sure how to tackle the query, let alone in a semi-optimized way.

上表的工作方式是，member_id和friend_id在另一张表上本质上是同一件事.在我的系统中，除此一张表外，这些ID通常称为member_id.例如，假设我的member_id为21.我的号码可以在无数其他行上，例如member_id或friend_id，这取决于最初发起实际友谊请求的人，而我并不想在其中重复数据我会伪装成行来基本上做同样的事情.

The table above works in a manner where the member_id and friend_id are essentially the same thing on another table. In my system, these id's are generally referred to as member_id except on this one table. For example, let's say my member_id is 21. My number can be on an infinite amount of other rows as either the member_id or the friend_id it's either based on who initiated the actual friendship request originally, that and I didn't want redundant data where I'd have dupe rows to basically do the same thing.

我想查询一个查询，我不仅可以确定学位程度(例如LinkedIn)，还可以确定一个人可能会显示多少个共同的朋友(例如Facebook).这里的x因子是我前面提到的is_active列.此列可以为0或1.这是一个简单的tinyint列，用作on/off开关.任何具有1的朋友连接都将是活跃的友谊，而0则处于待处理状态.我需要以我的活跃朋友及其活跃朋友等作为该查询的基础.我的朋友没有一个活跃朋友是我的活跃朋友.

I'd like to have a query where I can not only establish a level of degree (think LinkedIn) but I can also establish how many mutual friends one person may have that's being displayed (think Facebook). The x factor here is the is_active column I mentioned earlier. This column could be 0 or 1. It's a simple tinyint column that acts as a on/off switch. Any friend connections with a 1 would be an active friendship whereas 0 is pending. I need to base this query off my active friends and their active friends and so on. Where none of the active friends my friends have are active friends of mine.

如何构造这样的查询(即使我无法显示分离级别并且只能得到相互计数)?现在，我可以想一想，但它涉及到一些嵌套循环的查询，是的，我只是无法想象出对服务器整体性能或运行状况的长期影响.

How can I construct a query like this (even if I can't show the level of separation and only get a mutual count)? Right now, I can sort of think of something but it involves query after query some nested in loops, and yea, I just can't picture that being anything good for my servers' overall performance or health over time.

推荐答案

以下是使用JOIN使用广度优先，最短路径搜索执行搜索的方法.该算法没有魔术，因为我们使用MySQL来找到答案，并且没有合并任何使用任何启发式或优化方法的奇特搜索算法.

Here's how to perform the search using a breadth-first, shortest path search, using JOIN. There is no magic in this algorithm, as we're using MySQL to find our answer, and we're not incorporating any fancy search algorithm that uses any kind of heuristics or optimization.

我的朋友"表具有单向关系，因此在存储"1到2"和"2到1"的意义上，我们确实有重复项.我也排除了is_active，因为实现很明显:

My 'friends' table has unidirectional relationships, so we do have duplicates in the sense that both '1 to 2' and '2 to 1' are stored. I'm also excluding is_active since the implementation will be obvious:

以下是数据:

member_id   friend_id
1           2
1           3
1           4
2           1
2           3
2           5
2           6
3           2
3           1
4           1
5           2
6           2
6           7
7           6
7           8
8           7

我们已选择成员1，我们要问的是7个朋友中的1个朋友，一个朋友的朋友，等等?计数为0表示不，计数为1表示是.

We have member 1 selected, and we're asking is 1 friends with 7, a friend of a friend, etc? A count of 0 means no, and a count of 1 means yes.

SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
  AND f1.friend_id = 7

如果否，那么他们是朋友的朋友吗?

If no, then are they friend of a friend?

SELECT COUNT(*)
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
WHERE f1.member_id = 1
  AND f2.friend_id = 7

如果没有，那么一个朋友的一个朋友呢?

If no, then friend of a friend of a friend?

SELECT COUNT(*)
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
JOIN friends f3
  ON f3.member_id = f2.friend_id
WHERE f1.member_id = 1
  AND f3.friend_id = 7

依此类推...

第三个查询将找到路径"1到2"，"2到6"和"6到7"，返回计数1.

The third query would find the path '1 to 2', '2 to 6', and '6 to 7', returning the count of 1.

每个查询变得更加昂贵(由于连接数量更多)，因此您可能希望在某个时候限制搜索.一件很酷的事情是，这种搜索从两端到中间都有效，这是为最短路径搜索建议的一种简单优化.

Each query becomes more expensive (due to the larger number of joins), so you may want to limit the search at some point. One cool thing is that this search works from both ends toward the middle, which is one simple optimization suggested for shortest path searches.

在这里，如何找到成员1的共同朋友推荐

Here's how to find those mutual friend recommendations for member 1:

SELECT f2.friend_id
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
LEFT JOIN friends f3
  ON f3.member_id = f1.member_id
  AND f3.friend_id = f2.friend_id
WHERE f1.member_id = 1
  AND f2.friend_id <> f1.member_id // Not ourself
  AND f3.friend_id IS NULL // Not already a friend

这篇关于分离度查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！