SQL-запрос, как мне найти пару друзей, у которых есть самые общие друзья?

Question

У меня есть две таблицы. пользователи таблице:

USERS(ID,NAME) 

Друг отношений:

FRIEND(ID1,ID2) 

и я хочу, чтобы найти пары пользователей, которые имеют наиболее общих друзей в то время как два пользователя не являются друзьями.

Наконец, я хочу напечатать пару имен двух пользователей. Примера может служить как: таблицы

пользователей:

(1,Jimmy) 
(2,Sam) 
(3,Alices) 
(4,Tom) 

Friend стол:

(1,2) 
(1,3) 
(4,2) 
(4,3) 

Как пользователи 1 и 4 имеют общие друг 2,3. Пользователи 2 и 3 имеют общие друзья 1,4. Обе две пары друзей имеют ряд общих друзей 2. Таким образом, мы хотим, чтобы напечатать их имена в качестве результатов:

Jimmy,Tom 
Sam,Alices 

Как я могу сделать это в одном запросе?

Answer 1

Я использую SQL Server для его проверки, потому что у меня есть только SQL Server под рукой, но он должен быть прямой, чтобы преобразовать его в синтаксис Oracle.

Я преобразовал его в Oracle, используя SQL Fiddle, хотя я никогда раньше не видел Oracle. См. Окончательный запрос внизу.

Выборочные данные

DECLARE @USERS TABLE (ID int, NAME nvarchar(255)); 

DECLARE @FRIEND TABLE (ID1 int, ID2 int); 

INSERT INTO @USERS (ID, NAME) VALUES (1, 'Jimmy'); 
INSERT INTO @USERS (ID, NAME) VALUES (2, 'Sam'); 
INSERT INTO @USERS (ID, NAME) VALUES (3, 'Alice'); 
INSERT INTO @USERS (ID, NAME) VALUES (4, 'Tom'); 

INSERT INTO @FRIEND (ID1, ID2) VALUES (1,2); 
INSERT INTO @FRIEND (ID1, ID2) VALUES (1,3); 
INSERT INTO @FRIEND (ID1, ID2) VALUES (4,2); 
INSERT INTO @FRIEND (ID1, ID2) VALUES (4,3); 

Пары пользователей

Нам нужны пары пользователей. Это делается по CROSS JOIN. CROSS JOIN вернет в два раза больше строк, чем нам нужно (1,2) and (2,1), но нам нужен только один из них, поэтому мы добавим фильтр пользователем ID.

WITH 
CTE_Pairs 
AS 
(
    SELECT 
     U1.ID AS ID1 
     ,U2.ID AS ID2 
    FROM 
     @USERS AS U1 
     CROSS JOIN @USERS AS U2 
    WHERE 
     U1.ID > U2.ID 
) 
SELECT * 
FROM CTE_Pairs; 

Вывод:

ID1 ID2 
2  1 
3  1 
4  1 
3  2 
4  2 
4  3 

Пары, которые не являются друзьями

После того, как мы все пары, мы должны удалить те пары, которые являются друзьями уже. В таблице FRIEND можно указать пару как (1,2) или как (2,1), поэтому мы должны проверить обе возможности. Мы будем использовать EXCEPT для «вычитания» этих строк.

.... 
,CTE_PairsNonFriends 
AS 
(
    SELECT ID1, ID2 
    FROM CTE_Pairs 

    EXCEPT 

    SELECT ID1, ID2 
    FROM @FRIEND 

    EXCEPT 

    SELECT ID2, ID1 
    FROM @FRIEND 
) 
SELECT * 
FROM CTE_PairsNonFriends; 

Вывод:

ID1 ID2 
3  2 
4  1 

Друзья выбранных пользователей

У нас есть окончательный список пар. Для каждого пользователя нам нужно получить список его ближайших друзей. Простой join достаточно. Снова таблица friend может иметь (1,2) или (2,1), поэтому нам нужно сделать это дважды. И мы делаем это для пользователя ID1 сначала, затем отдельно для пользователя ID2.

.... 
,CTE_FriendsOfUser1 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID1 AS IDUser1 
     ,F1.ID2 AS FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID1 = CTE_PairsNonFriends.ID1 

    UNION -- sic! not ALL 

    SELECT 
     CTE_PairsNonFriends.ID1 AS IDUser1 
     ,F1.ID1 AS FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID2 = CTE_PairsNonFriends.ID1 
) 
,CTE_FriendsOfUser2 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID2 AS IDUser2 
     ,F1.ID2 AS FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID1 = CTE_PairsNonFriends.ID2 

    UNION -- sic! not ALL 

    SELECT 
     CTE_PairsNonFriends.ID2 AS IDUser2 
     ,F1.ID1 AS FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID2 = CTE_PairsNonFriends.ID2 
) 

Вывод:

SELECT * FROM CTE_FriendsOfUser1 

IDUser1 FriendOfUser1 
4   2 
4   3 
3   1 
3   4 


SELECT * FROM CTE_FriendsOfUser2 

IDUser2 FriendOfUser2 
1   2 
1   3 
2   1 
2   4 

Взаимные друзья

join user1 с user2 на свой список друзей, чтобы найти общих друзей.

.... 
,CTE_MutualFriends 
AS 
(
    SELECT * 
    FROM 
     CTE_FriendsOfUser1 
     INNER JOIN CTE_FriendsOfUser2 ON CTE_FriendsOfUser2.FriendOfUser2 = CTE_FriendsOfUser1.FriendOfUser1 
    WHERE 
     CTE_FriendsOfUser1.IDUser1 <> CTE_FriendsOfUser2.IDUser2 
) 

Граф взаимные друзья

,CTE_FriendCount 
AS 
(
    SELECT 
     IDUser1 
     ,IDUser2 
     ,COUNT(*) AS FriendCount 
    FROM CTE_MutualFriends 
    GROUP BY IDUser1, IDUser2 
) 

Окончательный полный запрос с именами пользователей

Сортировать результаты по другу сосчитать. Вы можете вернуть только первую строку (или первые несколько строк), чтобы возвращать пользователям наибольшее количество общих друзей. На самом деле, он должен быть на TOP со связями.

WITH 
CTE_Pairs 
AS 
(
    SELECT 
     U1.ID AS ID1 
     ,U2.ID AS ID2 
    FROM 
     @USERS AS U1 
     CROSS JOIN @USERS AS U2 
    WHERE 
     U1.ID > U2.ID 
) 
,CTE_PairsNonFriends 
AS 
(
    SELECT ID1, ID2 
    FROM CTE_Pairs 

    EXCEPT 

    SELECT ID1, ID2 
    FROM @FRIEND 

    EXCEPT 

    SELECT ID2, ID1 
    FROM @FRIEND 
) 
,CTE_FriendsOfUser1 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID1 AS IDUser1 
     ,F1.ID2 AS FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID1 = CTE_PairsNonFriends.ID1 

    UNION -- sic! not ALL 

    SELECT 
     CTE_PairsNonFriends.ID1 AS IDUser1 
     ,F1.ID1 AS FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID2 = CTE_PairsNonFriends.ID1 
) 
,CTE_FriendsOfUser2 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID2 AS IDUser2 
     ,F1.ID2 AS FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID1 = CTE_PairsNonFriends.ID2 

    UNION -- sic! not ALL 

    SELECT 
     CTE_PairsNonFriends.ID2 AS IDUser2 
     ,F1.ID1 AS FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN @FRIEND AS F1 ON F1.ID2 = CTE_PairsNonFriends.ID2 
) 
,CTE_MutualFriendsRaw 
AS 
(
    SELECT 
     CTE_FriendsOfUser1.FriendOfUser1 AS MutualFriend 
     ,IDUser1 
     ,IDUser2 
    FROM 
     CTE_FriendsOfUser1 
     INNER JOIN CTE_FriendsOfUser2 ON CTE_FriendsOfUser2.FriendOfUser2 = CTE_FriendsOfUser1.FriendOfUser1 
    WHERE 
     CTE_FriendsOfUser1.IDUser1 <> CTE_FriendsOfUser2.IDUser2 
) 
,CTE_MutualFriends 
AS 
(
    SELECT DISTINCT 
     MutualFriend 
     ,CASE WHEN IDUser1 < IDUser2 THEN IDUser1 ELSE IDUser2 END AS IDUser1 
     ,CASE WHEN IDUser1 < IDUser2 THEN IDUser2 ELSE IDUser1 END AS IDUser2 
    FROM 
     CTE_MutualFriendsRaw 
) 
,CTE_FriendCount 
AS 
(
    SELECT 
     IDUser1 
     ,IDUser2 
     ,COUNT(*) AS FriendCount 
    FROM CTE_MutualFriends 
    GROUP BY IDUser1, IDUser2 
) 
SELECT 
    CTE_FriendCount.IDUser1 
    ,CTE_FriendCount.IDUser2 
    ,CTE_FriendCount.FriendCount 
    ,U1.NAME AS Name1 
    ,U2.NAME AS Name2 
FROM 
    CTE_FriendCount 
    INNER JOIN @USERS AS U1 ON U1.ID = CTE_FriendCount.IDUser1 
    INNER JOIN @USERS AS U2 ON U2.ID = CTE_FriendCount.IDUser2 
ORDER BY FriendCount DESC 
; 

Вывод:

IDUser1 IDUser2 FriendCount Name1 Name2 
4   1   2    Tom  Jimmy 
3   2   2    Alice Sam 

Там может быть проблема с CTE_MutualFriends. Опять та же проблема, что пара может быть указана как (1,2) или (2,1). Вы можете иметь, скажем, пару (a,b) со счетом NN и пару (b,a) с другим счетом MM. Строго говоря, должен быть еще один шаг, который ищет такие пары и объединяет их вместе. Я не уверен, что с текущим запросом такие пары возможны или нет.

проблема с исходной версией CTE_MutualFriends, поэтому я добавил дополнительный шаг для устранения дубликатов в окончательной полной версии запроса. Данные данного образца слишком малы и просты, чтобы иметь все возможные варианты, поэтому версия версии давала правильные результаты. Если мы добавим больше записей в данные примера, мы увидим, что необходим дополнительный шаг.

Oracle синтаксис версии

Проверено с http://sqlfiddle.com/#!4/48e1f/21/0

WITH 
CTE_Pairs 
AS 
(
    SELECT 
     U1.ID ID1 
     ,U2.ID ID2 
    FROM 
     USERS U1 
     CROSS JOIN USERS U2 
    WHERE 
     U1.ID > U2.ID 
) 
,CTE_PairsNonFriends 
AS 
(
    SELECT ID1, ID2 
    FROM CTE_Pairs 

    MINUS 

    SELECT ID1, ID2 
    FROM FRIEND 

    MINUS 

    SELECT ID2, ID1 
    FROM FRIEND 
) 
,CTE_FriendsOfUser1 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID1 IDUser1 
     ,F1.ID2 FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN FRIEND F1 ON F1.ID1 = CTE_PairsNonFriends.ID1 

    UNION 

    SELECT 
     CTE_PairsNonFriends.ID1 IDUser1 
     ,F1.ID1 FriendOfUser1 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN FRIEND F1 ON F1.ID2 = CTE_PairsNonFriends.ID1 
) 
,CTE_FriendsOfUser2 
AS 
(
    SELECT 
     CTE_PairsNonFriends.ID2 IDUser2 
     ,F1.ID2 FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN FRIEND F1 ON F1.ID1 = CTE_PairsNonFriends.ID2 

    UNION 

    SELECT 
     CTE_PairsNonFriends.ID2 IDUser2 
     ,F1.ID1 FriendOfUser2 
    FROM 
     CTE_PairsNonFriends 
     INNER JOIN FRIEND F1 ON F1.ID2 = CTE_PairsNonFriends.ID2 
) 
,CTE_MutualFriendsRaw 
AS 
(
    SELECT 
     CTE_FriendsOfUser1.FriendOfUser1 MutualFriend 
     ,IDUser1 
     ,IDUser2 
    FROM 
     CTE_FriendsOfUser1 
     INNER JOIN CTE_FriendsOfUser2 ON CTE_FriendsOfUser2.FriendOfUser2 = CTE_FriendsOfUser1.FriendOfUser1 
    WHERE 
     CTE_FriendsOfUser1.IDUser1 <> CTE_FriendsOfUser2.IDUser2 
) 
,CTE_MutualFriends 
AS 
(
    SELECT DISTINCT 
     MutualFriend 
     ,CASE WHEN IDUser1 < IDUser2 THEN IDUser1 ELSE IDUser2 END IDUser1 
     ,CASE WHEN IDUser1 < IDUser2 THEN IDUser2 ELSE IDUser1 END IDUser2 
    FROM 
     CTE_MutualFriendsRaw 
) 
,CTE_FriendCount 
AS 
(
    SELECT 
     IDUser1 
     ,IDUser2 
     ,COUNT(*) FriendCount 
    FROM CTE_MutualFriends 
    GROUP BY IDUser1, IDUser2 
) 
SELECT 
    CTE_FriendCount.IDUser1 
    ,CTE_FriendCount.IDUser2 
    ,CTE_FriendCount.FriendCount 
    ,U1.NAME Name1 
    ,U2.NAME Name2 
FROM 
    CTE_FriendCount 
    INNER JOIN USERS U1 ON U1.ID = CTE_FriendCount.IDUser1 
    INNER JOIN USERS U2 ON U2.ID = CTE_FriendCount.IDUser2 
ORDER BY FriendCount DESC 
; 

Answer 2

Я думаю, что вы хотите что-то вроде этого:

WITH uf AS (
    SELECT id1 AS user_id, id2 AS friend_id FROM friends 
    UNION ALL 
    SELECT id2 AS user_id, id1 AS friend_id FROM friends 
), xf AS (
    SELECT user_id1, user_id2, friend_cnt FROM (
     SELECT uf1.user_id AS user_id1, uf2.user_id AS user_id2 
      , COUNT(*) AS friend_cnt 
      , RANK() OVER (ORDER BY COUNT(*) DESC) AS rn 
      FROM uf uf1 INNER JOIN uf uf2 
      ON uf1.friend_id = uf2.friend_id 
      AND uf1.user_id < uf2.user_id 
     GROUP BY uf1.user_id, uf2.user_id 
    ) WHERE rn = 1 
) 
SELECT xf.friend_cnt, u1.username || ',' || u2.username 
    FROM xf INNER JOIN users u1 
    ON xf.user_id1 = u1.user_id 
INNER JOIN users u2 
    ON xf.user_id2 = u2.user_id; 

В первом КТР я получаю пользователей со своими друзьями; во втором я получаю пользователей с друзьями вместе, а затем рейтинг их по счету; в основном запросе я просто получаю имена пользователей и конкатенирую их.

Please see SQL Fiddle demo here. Обратите внимание, что даже если Джимми и Том имеют четырех друзей в демке, значение friend_cnt является 3, как это число друзей они имеют в общем (я добавил несколько друзей к данным выборки).