时间戳

首页 > 解决方案 > 如何计算 SQL 数据库中两条线之间的距离？

sql - 如何计算 SQL 数据库中两条线之间的距离？

问题描述

这是我的数据库示例，包含 3 个列：班级、年份和学生姓名。

在此处输入图像描述

我根据两个给定学生之间的普通学生搜索“距离”。（比如著名的游戏“6度培根”）

目标是计算 Momo Thary (2018) 和 Paul Biloux (2020) 之间的距离。答案是 2 个学生：Momo Thary 和 Jack Spiral 在同一个班。Jack Spiral 和 Lucien Lake 同班。Lucien Lake 和 Paul Biloux 同班。

所以我们可以将 Momo Thary 和 Paul Biloux 与 2 名学生“联系起来”。

我在网上使用 SQLite。通过以下代码，可以知道 Jack Spiral 和 Paul Biloux 的共同玩家：

WITH
  names(name) AS (SELECT 'Jack Spiral' UNION ALL SELECT 'Paul Biloux'),
  common AS (
    SELECT class, year
    FROM Lignes
    WHERE student_name IN names
    GROUP BY class, year
    HAVING COUNT(DISTINCT student_name) = (SELECT COUNT(*) FROM names)
  )
SELECT l1.student_name student
FROM Lignes l1 INNER JOIN Lignes l2
ON l2.year = l1.year AND l2.class = l1.class AND l2.student_name <> l1.student_name
WHERE l2.student_name IN names
GROUP BY student
HAVING COUNT(DISTINCT l2.student_name) = (SELECT COUNT(*) FROM names)
   AND SUM((l1.class, l1.year) IN common) = 0

输出是吕西安湖。

但是如果我将这个脚本用于 Momo Thary 和 Paul Biloux，则没有输出。事实上，是不是需要先用 Jack Spiral 再用 Lucien Lake 来做链接。

是否可以调整脚本，首先知道最快的链接（如果有很多可能的链接），然后知道学生的路径是什么？SQL可能适合做这种类型的代码还是其他语言更合适？

标签： sqlsqlite

解决方案

您可以使用递归查询：

WITH RECURSIVE rec(distance, student_name, path) AS (
  -- start with Paul Biloux
  SELECT 0, 'Paul Biloux', '|Paul Biloux|'
  UNION
  -- increment distance
  SELECT r.distance + 1, l1.student_name, r.path || l1.student_name || '|'
  FROM rec r
  JOIN lignes l1
  -- avoid loops
  ON r.path NOT LIKE '%|' || l1.student_name || '|%'
  -- there is a common class
  WHERE exists (SELECT * FROM lignes l2 WHERE l2.year = l1.year AND l2.grade = l1.grade AND l2.student_name = r.student_name )
)
-- keep only the shortest path
-- if there are more than one, choose one randomely
-- (this is specific to SQLite)
SELECT student_name, MIN(distance) AS dist, path
FROM rec
GROUP BY student_name
ORDER BY distance

结果是：

student_name    dist  path
Paul Biloux     0     |Paul Biloux|
Lucien Lake     1     |Paul Biloux|Lucien Lake|
Thome Defoe     1     |Paul Biloux|Thome Defoe|
Chane Way       2     |Paul Biloux|Lucien Lake|Chane Way|
Jack Spiral     2     |Paul Biloux|Lucien Lake|Jack Spiral|
Mathilde Seine  3     |Paul Biloux|Lucien Lake|Jack Spiral|Mathilde Seine|
Momo Thary      3     |Paul Biloux|Lucien Lake|Jack Spiral|Momo Thary|

这是非常低效的，因为探索了所有可能的路径。

推荐阅读