如何检查树中是否存在父/子关系？

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)
);

父母可以有很多孩子，孩子可以有很多父母。编写代码来处理数据库之外的记录总是可行的，但是是否可以使用深度优先（或广度优先）搜索来检查孩子是否有特定父母？

My related question收到了来自CL.的评论，提到了WITH clause，但我对分层查询的经验相当有限，不足以理解，选择和应用页面上的示例到我的目标：

• 仅适用于Oracle中的分层查询。
• 仅用于实现“范围”数字生成器（如Python中）。
• 只看到如何以宽广到狭窄的模式处理记录。
• 不确定是否可以在分层查询中设置扩展结果集。
• 不确定如何选择深度优先或广度优先搜索策略。

有人可以告诉我如何知道一个孩子是否有父母，如果知道两者的名字？

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');

深度/广度优先对此无关紧要。

Answer 2

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

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)