查询相邻列表中最远的子项

Question

所以我有一个SQL查询来检索邻接列表中给定节点的所有子节点。

WITH    RECURSIVE
        q AS
        (
        SELECT  id, name
        FROM    categories h
        WHERE   id = 11846801
        UNION ALL
        SELECT  hc.id, hc.name
        FROM    q
        JOIN    categories hc
        ON      hc.parent = q.id
        )
SELECT  name
FROM    q

有没有一种方法可以修改这个查询，只返回节点的底层？我不能只指定一个给定的级别，因为每条路径可能有不同的深度。

Answer 1

解释1

"所有离开节点的路径从一开始就最长。"

一种方法是在你下降的路上计算等级，只返回最底层的成员：

WITH RECURSIVE q AS (
   SELECT  id, name, 0 AS lvl
   FROM    categories
   WHERE   id = 11846801
   UNION ALL
   SELECT  c.id, c.name, q.lvl + 1
   FROM    q
   JOIN    categories c ON c.parent = q.id
   )
SELECT  id, name
FROM    q
WHERE   lvl = (SELECT max(lvl) FROM q);

解释2

"所有离开节点。"

WITH RECURSIVE q AS (
   SELECT  id, name, parent
   FROM    categories
   WHERE   id = 11846801
   UNION ALL
   SELECT  c.id, c.name, c.parent
   FROM    q
   JOIN    categories c ON c.parent = q.id
   )
SELECT  id, name
FROM    q
WHERE   NOT EXISTS (SELECT FROM q q1 WHERE q1.parent = q.id);

检查q应该比检查基表更快——除非q很大，在这种情况下，主表上的索引可能会更快。

Answer 2

底层的东西从来都不是父母。因此，您可以添加以下where子句：

where id not in (select parent from categories)

实际上，在Postgres中，not in可能不是最有效的方法。因此，这可能更有效：

where not exists (select 1 from categories c where c.parent = q.id)

Answer 3

只是重复Gordon Linoff的答案。他的查询是个好主意，但前提是并没有NULL值。因此，为了应对这种情况，需要一个额外的where条款。

SELECT id WHERE id NOT IN (SELECT parent FROM categories WHERE parent IS NOT NULL);

我今天才知道这件事。（没有足够的代表发表评论）

为了符合SQL标准，IN不仅在左侧的表达式为NULL的情况下返回NULL，而且在列表中未找到匹配项并且列表中的一个表达式为NULL时也返回NULL。

参考http://dev.mysql.com/doc/refman/5.6/en/comparison-operators.html#function_in