我认识的人去了一次面试,并给出了以下问题来解决。我已经考虑了几个小时,并且相信如果不使用某些数据库特定的扩展或最近标准中尚未得到广泛支持的功能,就无法做到这一点。面试问题:在一个语句中的SQL递归
我不记得背后的故事背后的故事,但它不相关。简单来说,你要代表唯一的数字链:
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后,问题就会解决。
我想你需要使用connect_by_root来获取父列。我认为3列网格是所需的最终结果(链,id,父,根)。即选择ID,父母,connect_by_root ID ... – ryanlahue 2010-11-15 02:45:53
@rla:是的,谢谢你的评论。 – zerkms 2010-11-15 02:47:46
很高兴知道,感谢您的解释。 – VokinLoksar 2010-11-15 03:00:02