时间戳

首页 > 解决方案 > 在 Postgresql 中限制基于 FK 的有向无环图的 CTE 搜索

sql - 在 Postgresql 中限制基于 FK 的有向无环图的 CTE 搜索

问题描述

我对原始 SQL 还是很陌生，以前在 ORM 中完成了所有工作，这可能只需要一行额外的 SQL。

在我的 Postgresql 数据库中，我有以下表格：nodes_table和edges_table是用于在 Postgresql 数据库中定义图形（特别是 DAG）的标准表格。

我还有一个edges_group_table，它允许我在逻辑上将一堆边组合在一起。例如，如果图形是管道网络，edges_group_table 可能用于指定哪些边在哪个建筑物中。

我有一个有效的公用表表达式 (CTE)（如下所示）来搜索给定节点的祖先节点。

因为图表可能很大，我希望能够减少 CTE 必须搜索的图表部分。除了指定起始节点之外，我还希望能够指定一个 group_id 以将 CTE 搜索限制在指定组中的那些边缘。

表：

nodes_table
    id
    name

edges_table
    id
    name
    child_id -- a nodes_table id
    parent_id -- a nodes_table id
    group_id -- a edges_group_table id

edges_group_table
    id
    name

如何修改此 CTE 以将图形的祖先搜索限制为 edge_group_table 中提供的组内的那些边？

WITH RECURSIVE graph(id, depth) AS (
    SELECT first.parent_id, 1
        FROM edges_table AS first
        LEFT OUTER JOIN edges_table AS second
        ON first.parent_id = second.child_id
    WHERE first.child_id = 10 -- the node id we start from
UNION
    SELECT DISTINCT parent_id, graph.depth + 1
        FROM graph
        INNER JOIN edges_table
        ON edges_table.child_id = graph.id
)
SELECT id FROM graph
GROUP BY id
ORDER BY MAX(depth) DESC, id ASC

我很感激这方面的任何帮助！

标签： sqlpostgresqlgraphcommon-table-expressiondirected-acyclic-graphs

解决方案

假设您要限制两个搜索，似乎应该很简单，因为将 WHERE 子句添加到 CTE 的递归部分和第一个 select 子句：

WITH RECURSIVE graph(id, depth) AS (
    SELECT first.parent_id, 1
        FROM edges_table AS first
        LEFT OUTER JOIN edges_table AS second
        ON first.parent_id = second.child_id
            AND second.group_id = 15 --limit result for second node
    WHERE first.child_id = 10 -- the node id we start from
UNION
    SELECT DISTINCT parent_id, graph.depth + 1
        FROM graph
        INNER JOIN edges_table
        ON edges_table.child_id = graph.id
        WHERE edges_table.group_id = 15 --and all subsequent nodes
)
SELECT id FROM graph
GROUP BY id
ORDER BY MAX(depth) DESC, id ASC

请注意，在第一个表达式中，我们在 LEFT JOIN 部分使用过滤器而不是 WHERE 子句，这样即使第一条边没有连接到设计边组中的第二条边，它也会返回一行。

推荐阅读