面试问题：在一个语句中的SQL递归

Question

我认识的人去了一次面试，并给出了以下问题来解决。我已经考虑了几个小时，并且相信如果不使用某些数据库特定的扩展或最近标准中尚未得到广泛支持的功能，就无法做到这一点。

我不记得背后的故事背后的故事，但它不相关。简单来说，你要代表唯一的数字链：

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中有START WITH和CONNECT 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后，问题就会解决。

Answer 1

它不能在符合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 

Answer 2

有一个在ANSI没有递归查询的支持-92，因为它是在ANSI-99中添加的。自从v2以来，Oracle拥有自己的递归查询语法（CONNECT BY）。虽然自9i起Oracle支持WITH子句，但SQL Server是我知道的第一个支持递归WITH/CTE语法的工具 - Oracle直到11gR2才开始。 PostgreSQL在8.4+中增加了支持。自2006年以来，MySQL已经收到了WITH支持请求，我非常怀疑你会在SQLite中看到它。

你给的例子是只有两层深，所以你可以使用：

INSERT INTO dst 
    SELECT a.id, 
      a.parent, 
      COALESCE(c.id, b.id) AS start 
    FROM SRC a 
LEFT JOIN SRC b ON b.id = a.parent 
LEFT JOIN SRC c ON c.id = b.parent 
    WHERE a.parent IS NOT NULL 

你必须添加一个LEFT JOIN深层次的数量，并以正确的顺序将它们添加到COALESCE功能。

Answer 3

在SQL Server中，您将使用公用表表达式（CTE）。

复制存储的数据我创建了一个临时表

-- Create a temporary table 
CREATE TABLE #SourceData 
(
    ID INT 
    , Parent INT 
) 

-- Setup data (ID, Parent, KeyField) 
INSERT INTO #SourceData VALUES (1, NULL); 
INSERT INTO #SourceData VALUES (2, 1); 
INSERT INTO #SourceData VALUES (3, 2); 
INSERT INTO #SourceData VALUES (42, NULL); 
INSERT INTO #SourceData VALUES (78, 42); 
INSERT INTO #SourceData VALUES (4, NULL); 
INSERT INTO #SourceData VALUES (7, NULL); 
INSERT INTO #SourceData VALUES (8, 7); 
INSERT INTO #SourceData VALUES (9, 8); 

然后，我创建了CTE编译数据结果：

-- Perform CTE 
WITH RecursiveData (ID, Parent, Start) AS 
(
    -- Base query 
    SELECT ID, Parent, ID AS Start 
    FROM #SourceData 
    WHERE Parent IS NULL 

    UNION ALL 

    -- Recursive query 
    SELECT s.ID, s.Parent, rd.Start 
    FROM #SourceData AS s 
      INNER JOIN RecursiveData AS rd ON s.Parent = rd.ID 
) 
SELECT * FROM RecursiveData WHERE Parent IS NULL 

这将输出如下：

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

然后我清理:)

-- Clean up 
DROP TABLE #SourceData