如何检查树中是否存在 parent/child 关系？

Question

检查下表的记录之间是否存在某种关系会很有用：

-- Table: privilege_group
CREATE TABLE privilege_group (
    privilege_group_id integer NOT NULL CONSTRAINT privilege_group_pk PRIMARY KEY AUTOINCREMENT,
    name text NOT NULL,
    CONSTRAINT privilege_group_name UNIQUE (name)
);

-- Table: privilege_relationship
CREATE TABLE privilege_relationship (
    privilege_relationship_id integer NOT NULL CONSTRAINT privilege_relationship_pk PRIMARY KEY AUTOINCREMENT,
    parent_id integer NOT NULL,
    child_id integer NOT NULL,
    CONSTRAINT privilege_relationship_parent_child UNIQUE (parent_id, child_id),
    CONSTRAINT privilege_relationship_parent_id FOREIGN KEY (parent_id)
    REFERENCES privilege_group (privilege_group_id),
    CONSTRAINT privilege_relationship_child_id FOREIGN KEY (child_id)
    REFERENCES privilege_group (privilege_group_id),
    CONSTRAINT privilege_relationship_check CHECK (parent_id != child_id)
);

Parents可以有很多children，children可以有很多parents。始终可以编写代码来处理数据库外部的记录，但是是否可以使用 depth-first（或 breadth-first）搜索来检查 child 是否具有特定的 parent?

My related question received a comment from CL. that mentions the WITH clause，但我在分层查询方面的经验相当有限，不足以理解，select，并将页面上的示例应用到我的目标中：

仅在 Oracle 中使用分层查询。
仅用于实现 "range" 数字生成器（如 Python）。
只见过如何以 broad-to-narrow 模式处理记录。
不确定是否可以在分层查询中扩展结果集。
不确定如何select depth-first 或 breadth-first 搜索策略。

有人可以告诉我如何找出 child 是否有 parent 如果两者的名字都知道吗？

Answer 1

这是一个标准的树搜索（使用 UNION 而不是 UNION ALL 来防止无限循环）：

WITH RECURSIVE ParentsOfG1(id) AS (
  SELECT privilege_group_id
  FROM privilege_group
  WHERE name = 'G1'

  UNION

  SELECT parent_id
  FROM privilege_relationship
  JOIN ParentsOfG1 ON id = child_id
)
SELECT id
FROM ParentsOfG1
WHERE id = (SELECT privilege_group_id
            FROM privilege_group
            WHERE name = 'P2');

Depth/breadth-first与此无关。

Answer 2

的替代方法可能是此查询，该查询已重新格式化并调整为使用可以插入需要检查某些关系的项目的绑定参数：

WITH RECURSIVE parent_of_child(id)
            AS (
        SELECT privilege_group_id
          FROM privilege_group
         WHERE name = :child
         UNION
        SELECT parent_id
          FROM privilege_relationship
          JOIN parent_of_child
            ON id = child_id)
        SELECT id
          FROM parent_of_child
         WHERE id = (
        SELECT privilege_group_id
          FROM privilege_group
         WHERE name = :parent)

如何检查树中是否存在 parent/child 关系？

How to check if a parent/child relationship exists in a tree?

sqlite

recursive-query