我在 SQL 中有以下三个表:

select * from movie limit 2;

  id  |           title            | year | content_rating | duration |    lang    |       country        |  gross   |  budget  | director_id 
------+----------------------------+------+----------------+----------+------------+----------------------+----------+----------+-------------
  407 | 102 Dalmatians             | 2000 | G              |      100 | English    | USA                  | 66941559 | 85000000 |        2174
 3699 | 10 Cloverfield Lane        | 2016 | PG-13          |      104 | English    | USA                  | 71897215 | 15000000 |        1327
(2 rows)

select * from actor limit 3;

  id  |         name         | facebook_likes 
------+----------------------+----------------
  408 | Christian Bale       |          23000
 1430 | Donna Murphy         |            553
   66 | Robert Downey Jr.    |          21000
(3 rows)

select * from acting limit 3;

 movie_id | actor_id 
----------+----------
      407 |     2024
     3699 |     1841
     3016 |       11
(3 rows)

给定两个 Actor a1 和 a2，我想找到 a1 之间的最短 路径 和 a2。

例如，假设 a1 = 'Tom Cruise' 和 a2 = 'Robert Downey Jr'。

输出应该是

汤姆·克鲁斯和罗伯特·杜瓦尔一起出演了雷霆之日 -> 罗伯特·杜瓦尔和小罗伯特·唐尼一起出演了幸运儿

在这种情况下，汤姆·克鲁斯 与小罗伯特·唐尼 相差 2 度，罗伯特·杜瓦尔 连接着他们。最多，我想输出高达 10 度，然后忽略任何连接。

我尝试实现解决方案 SQL query 6 degrees of separation for network analysis使用递归 CTE，但我认为我没有正确应用它。感谢帮助，提前致谢:)

尝试查询:

with recursive cte as (
select actor.name, movie.title, 1 as level from movie
left join acting on acting.movie_id = movie.id 
left join actor on actor.id = acting.actor_id
where actor.name = 'Tom Cruise'
union  
select actor.name, movie.title, level+1 from movie
left join acting on acting.movie_id = movie.id 
left join actor on actor.id = acting.actor_id
inner join cte on cte.name = actor.name
where cte.name = actor.name and cte.level < 10
)
select * from cte

最佳答案

我不确定您在查询中的第二个选择会返回什么，但这里有一种获取参与者之间分离度的方法:

假设我们有一张 Actor ID 表，Origin。为了获得与我们表中的其中一位 Actor 在同一部电影中扮演过的所有 Actor ，我们需要从 Origin 开始，加入 Acting 然后加入 Movie 以获得我们的原始 Actor 扮演过的所有电影，然后再次加入 Acting 和 Actor 表以获得我们想要的。请注意，代理表出现了两次。如果我们将此应用于递归 CTE 和您的问题，请注意 Origin 表在您的示例中将是 Cte，我们将得到以下结果:

WITH RECURSIVE cte(id, distance) AS (
    SELECT actor.id, 0 
    FROM actor
    WHERE actor.name = 'Tom Cruise'

    UNION

    SELECT DISTINCT actor.id, cte.distance + 1
    FROM cte
    JOIN acting AS acting1 ON (cte.id = acting1.actor_id)
    JOIN movie ON (acting1.movie_id = movie.id)
    JOIN acting AS acting2 ON (movie.id = acting2.movie_id)
    JOIN actor ON (acting2.actor_id = actor.id)
    WHERE cte.id <> actor.id AND cte.distance + 1 <= 10
)

在此之后，cte 表将包含类型为 (id, dist) 的元组，这意味着存在从汤姆克鲁斯到具有此 ID 且距离为 dist 的 Actor 的路径。

DISTINCT 是出于效率原因。我们的 Cte 表中会有很多错误对(第二个值大于真实距离)，特别是如果 Actor 图是密集的，但正确的元组将在 Cte 表中.我所说的正确元组是指一个元组( Actor ，距离)，这样的距离是起始 Actor (例如汤姆克鲁斯)和该 Actor 之间的最短路径。

编辑:糟糕，UNION 已经这样做了，所以重复不需要 DISTINCT。

为了获得该距离，我们添加了一个带有 group by 子句的选择:

WITH RECURSIVE cte(id, distance) AS (
    SELECT actor.id, 0 
    FROM actor
    WHERE actor.name = 'Tom Cruise'

    UNION

    SELECT actor.id, cte.distance + 1
    FROM cte
    JOIN acting AS acting1 ON (cte.id = acting1.actor_id)
    JOIN movie ON (acting1.movie_id = movie.id)
    JOIN acting AS acting2 ON (movie.id = acting2.movie_id)
    JOIN actor ON (acting2.actor_id = actor.id)
    WHERE cte.id <> actor.id AND cte.distance + 1 <= 10
)
SELECT id, MIN(distance) AS distance
FROM cte
GROUP BY id
ORDER BY 2 ASC;

如果您想查看给定的第二个 Actor 的结果，比如小罗伯特唐尼，那么这将为您提供有关分离度的答案:

WITH RECURSIVE cte(id, distance) AS (
    SELECT actor.id, 0 
    FROM actor
    WHERE actor.name = 'Tom Cruise'

    UNION

    SELECT actor.id, cte.distance + 1
    FROM cte
    JOIN acting AS acting1 ON (cte.id = acting1.actor_id)
    JOIN movie ON (acting1.movie_id = movie.id)
    JOIN acting AS acting2 ON (movie.id = acting2.movie_id)
    JOIN actor ON (acting2.actor_id = actor.id)
    WHERE cte.id <> actor.id AND cte.distance + 1 <= 10
), distance_table (id, distance) AS (
    SELECT id, MIN(distance) AS distance
    FROM cte
    GROUP BY id
)
SELECT 'Tom Cruise and ' || actor.name || ' are separated by ' ||
       COALESCE(TO_CHAR(distance_table.distance, '999999'), 'more than 10') || ' degrees of separation'
FROM actor
LEFT JOIN distance_table ON (actor.id = distance_table.id)
WHERE actor.name = 'Robert Downey Jr';

虽然我认为您一般不会想直接从数据库中计算此类信息，但如果您想要一条消息告诉 Actor 之间的路径，就像您提供的那样(汤姆克鲁斯在 Days雷霆与罗伯特·杜瓦尔 -> 罗伯特·杜瓦尔与小罗伯特·唐尼在《幸运的你》中)，然后像这样的东西可以返回:

WITH RECURSIVE cte(id, name, distance, message) AS (
    SELECT actor.id, actor.name, 0, ''
    FROM actor
    WHERE actor.name = 'Tom Cruise'

    UNION

    SELECT actor.id, actor.name, cte.distance + 1, 
           cte.message || '> ' || cte.name || ' was in ' ||
           movie.title || ' with ' || actor.name || ' '
    FROM cte
    JOIN acting AS acting1 ON (cte.id = acting1.actor_id)
    JOIN movie ON (acting1.movie_id = movie.id)
    JOIN acting AS acting2 ON (movie.id = acting2.movie_id)
    JOIN actor ON (acting2.actor_id = actor.id)
    WHERE cte.id <> actor.id AND cte.distance + 1 <= 10
), distance_table (id, distance) AS (
    SELECT id, MIN(distance) AS distance
    FROM cte
    GROUP BY id
)
SELECT id, name, message, distance
FROM cte
WHERE (id, distance) IN (SELECT * FROM distance_table)
ORDER BY distance;

关于php - 寻找最短路径最多分离十度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55717636/