对于在sqlite中存储为邻接表的树，找出一个节点是否是另一个节点的祖先

Question

问题

我有一个树结构存储为SQL数据库中的邻接表（也称为朴素树）。我希望找出node_b是否是node_a的祖先。我该怎么办？

背景详细信息

存储节点的表定义如下：

CREATE TABLE Nodes(
      id INTEGER PRIMARY KEY,
      parent INTEGER,     
      -- Other node specific data
      FOREIGN KEY (parent) REFERENCES Nodes(id)
    );

树的深度是未知的，但是在通常的使用情况下，期望很小。

树中没有循环。

根节点的父值为NULL。可能有多个根节点。

答案标准我正在寻找一个尽可能快的查询。

[已经完成的工作我想出了一个行之有效的解决方案，将其作为答案发布，但是我想看看是否有更好，更简单，更快的方法。

Answer 1

我的解决方案

以下查询是我使用的解决方案（:node_a和:node_b是所讨论节点及其可能祖先的占位符：

WITH RECURSIVE ancestors AS(
  SELECT parent, id=:node_b AS match 
  FROM NODES WHERE id=:node_a
  UNION ALL
  SELECT n.parent, n.id=:id AS match
  FROM Nodes n JOIN ancestors
  ON ancestors.parent=n.id AND NOT ancestors.match
)
SELECT MAX(match) AS is_ancestor FROM ancestors;

说明

使用公共表表达式来生成一个查询，该查询包含node_a的每个祖先的父代，以及该祖先是否与node_b匹配

[它以node_a本身开头，并检查是否与node_b匹配，并返回由parent和match列组成的行-column_a的直接父级，以及一个表示node_a是否与node_b匹配的布尔值。

然后，通过递归连接到父列，它通过node_a的祖先上升，直到其中一个祖先与node_b匹配或父列为NULL。

如果node_b是node_a的祖先，则该表的一行将包含match列的值true。如果不是，那么match列的所有行都将包含false。由于true和false分别表示为1和0，因此在第一种情况下match列的MAX将为1，在第二种情况下将为0。

因此，如果node_b是node_a的祖先，则整个查询返回1，否则返回0。