Skip to main content
 首页 » 编程设计

sql之面试问题: SQL recursion in one statement

2024年02月05日18powertoolsteam

我认识的一个人去面试,并被要求解决以下问题。我已经考虑了几个小时,并相信如果不使用尚未得到广泛支持的最新标准中的一些特定于数据库的扩展或功能是不可能的。

我不记得所代表的内容背后的故事,但它不相关。简单来说,您正在尝试表示唯一数字链:

chain 1: 1  -> 2  -> 3 
chain 2: 42 -> 78 
chain 3: 4 
chain 4: 7  -> 8  -> 9 
... 

此信息已为您存储在以下表结构中:

id | parent 
---+------- 
1  | NULL 
2  | 1 
3  | 2 
42 | NULL 
78 | 42 
4  | NULL 
7  | NULL 
8  | 7 
9  | 8 

可能有数百万个这样的链,每个链可以有无限数量的条目。目标是创建第二个表,其中包含完全相同的信息,但第三列包含链的起点:

id | parent | start 
---+--------+------ 
1  | NULL   | 1 
2  | 1      | 1 
3  | 2      | 1 
42 | NULL   | 42 
78 | 42     | 42 
4  | NULL   | 4 
7  | NULL   | 7 
8  | 7      | 7 
9  | 8      | 7 

(面试官声称)这只需 2 个 SQL 查询即可实现。他们提供的提示是首先使用根元素填充目标表(我将其称为 dst),如下所示:

INSERT INTO dst SELECT id, parent, id FROM src WHERE parent IS NULL 

这将为您提供以下内容:

id | parent | start 
---+--------+------ 
1  | NULL   | 1 
42 | NULL   | 42 
4  | NULL   | 4 
7  | NULL   | 7 

他们说您现在只需再执行一个查询即可达到上面所示的目标。

在我看来,你可以做两件事之一。在源表中使用递归来到达每个链的前面,或者在每次更新 dst 后连续执行SELECT start FROM dst WHERE dst.id = src.parent的某个版本(即不能缓存结果)。

我认为 MySQL、PostgreSQL、SQLite 等常见数据库都不支持这两种情况。我确实知道在 PostgreSQL 8.4 中,您可以使用 WITH RECURSIVE 查询实现递归,并且在 Oracle 中,有 STARTWITHCONNECT BY 子句。关键是这些东西特定于数据库类型和版本。

是否有任何方法可以在一次查询中使用常规 SQL92 来实现所需的结果?我能做的最好的事情就是用以下内容填写第一个子项的开始列(也可以使用 LEFT JOIN 来实现相同的结果):

INSERT INTO dst 
    SELECT s.id, s.parent, 
        (SELECT start FROM dst AS d WHERE d.id = s.parent) AS start  
    FROM src AS s 
    WHERE s.parent IS NOT NULL 

如果有某种方法可以在每次插入 dst 后重新执行内部 select 语句,那么问题就可以解决。

请您参考如下方法:

它不能在任何遵循 ANSI SQL 92 的静态 SQL 中实现。

但正如你所说,使用oracle的CONNECT BY可以轻松实现

    SELECT id, 
           parent, 
           CONNECT_BY_ROOT id 
      FROM table 
START WITH parent IS NULL 
CONNECT BY PRIOR id = parent