sql - 查找 SQL 中值之间的步数

Question

假设我有一个包含以下内容的数据库表:

<表类=“s-表”> <标题> person1_id person2_id <正文> 1 2 3 4 2 3

(此表持续约 60k 行，其中有成对的人，这些成对的人可以出现多次并且不是一成不变的，因此人 1 也可以与人 3 配对)

我需要知道一个人与另一个人之间的步数，例如 4 中的 1 步需要 3 步 (1->2->3->4)。

作为输出，我期望类似的东西:

<表类=“s-表”> <标题> person1_id person2_id 步骤 <正文> 1 4 3

根据我的发现，应该可以使用recursive queries ，但我不知道如何解决这个问题

Answer 1

在递归查询中，您可以确定两个步骤:

• 基本步骤:包含我们要重复的现有行。
• 递归步骤:包含新行，这些新行是从时间步 0 处的基本步骤以及时间步 1+ 处的基本步骤和递归步骤生成的。

---

“基础”步骤

首先，我们要选择相关行来构建我们的基本步骤。对于这一行，我假设您不需要像“(2, 4, 2)”和“(3, 4, 1)”这样的行，所以基本上，您总是希望“person1_id”不要出现在“person2_id”值中。

SELECT person1_id FROM tab 
EXCEPT
SELECT person2_id FROM tab

<表类=“s-表”> <标题> person1_id <正文> 1

这将为我们提供“person1_id”，因此为了获取具有这些 id 的完整行，您可以执行 JOIN操作如下:

SELECT tab.person1_id, tab.person2_id, 1 AS steps
FROM       tab 
INNER JOIN (SELECT person1_id FROM tab 
            EXCEPT
            SELECT person2_id FROM tab) p1_never_p2
        ON tab.person1_id = p1_never_p2.person1_id

<表类=“s-表”> <标题> person1_id person2_id 步骤 <正文> 1 4 1

请注意，只要我们处于基本步长(属于原始表的任何行之间的距离“person1_id<”)，“steps”字段将始终初始化为 1。/em>”和“person2_id”始终为 1)。

---

“递归”步骤

在此步骤中，我们希望将当前表的“person2_id”与原始表的“person1_id”进行匹配，同时保留当前表的“person1_id” >”和原始表的“person2_id”(如果当前表中有 1-2，原始表中有 2-3，我想保留 1-3，因为两行都与 2 匹配)。当前的输出将由递归查询保留，这就是我们在 JOIN 中找到的内容。与原始表格。

WITH RECURSIVE cte AS (
    SELECT tab.person1_id, tab.person2_id, 1 AS steps
    FROM       tab 
    INNER JOIN (SELECT person1_id FROM tab 
                EXCEPT
                SELECT person2_id FROM tab) p1_never_p2
            ON tab.person1_id = p1_never_p2.person1_id

    UNION ALL

    SELECT cte.person1_id, tab.person2_id, cte.steps + 1 AS steps
    FROM       cte
    INNER JOIN tab
            ON cte.person2_id = tab.person1_id
)

请注意，此子查询称为“cte”，尽管它是在 FROM 子句内部调用的，以应用 INNER JOIN 。另请注意，我们增加了在“cte”内不断更新的步数值。

<表类=“s-表”> <标题> person1_id person2_id 步骤 <正文> 1 2 1 1 3 2 1 4 3

基本上，您在这里看到的是基本步骤(第 1 行)和每个递归步骤(第 2 行和第 3 行)。由于UNION ALL，我们拥有这两个步骤中的所有行。操作。

---

由于我们只需要每个“person1_id”值的步数最高的组合，因此我们可以使用 FETCH FIRST ROWS WITH TIES约束如下:

WITH RECURSIVE cte AS (
    SELECT tab.person1_id, tab.person2_id, 1 AS steps
    FROM       tab 
    INNER JOIN (SELECT person1_id FROM tab 
                EXCEPT
                SELECT person2_id FROM tab) p1_never_p2
            ON tab.person1_id = p1_never_p2.person1_id
    UNION ALL
    SELECT cte.person1_id, tab.person2_id, cte.steps + 1 AS steps
    FROM       cte
    INNER JOIN tab
            ON cte.person2_id = tab.person1_id
)
SELECT * 
FROM cte
ORDER BY ROW_NUMBER() OVER(PARTITION BY person1_id ORDER BY steps DESC)
FETCH FIRST ROWS WITH TIES

ROW_NUMBER窗口函数将为每个“person1_id”最大步数生成值1，然后FETCH FIRST ROWS WITH TIES将保留 ROW_NUMBER 的行等于 1，平局。

<表类=“s-表”> <标题> person1_id person2_id 步骤 <正文> 1 4 3

查看演示 here .