sql – 使用递归查询访问有向图,就好像它是一个无向图

发布时间：2021-01-24 23:53:55 所属栏目：MsSql教程来源：网络整理

导读：我需要您关于访问存储在数据库中的有向图的帮助. 请考虑以下有向图 1-2 2-1,3 3-1 表存储这些关系： create database test;c test;create table ownership ( parent bigint,child bigint,primary key (parent,child));insert into ownership (parent,child)

>使用字符串记录路径.比行数组更小更快.仍包含所有必要信息.但是,可能会使用非常大的bigint数字进行更改.
>使用LIKE运算符检查循环(~~),应该快得多.
>如果您不希望在一段时间内有更多的2147483647行,请使用plain integer columns instead of bigint.更小更快.
>一定要有父母的索引.关于孩子的索引与我的查询无关. (除了您原来在两个方向上移动边缘的地方.)
>对于巨大的图形,我将切换到plpgsql过程,您可以将路径维护为临时表,每步一行和匹配的索引.但是,有点开销,可以获得巨大的图表.

原始查询中的问题：

WHERE (g.parent = o.child or g.child = o.parent)

在此过程中的任何一点只有一个遍历端点.当您在两个方向上拖动有向图时,端点可以是父节点或子节点 – 但不是两者都可以.您必须保存每个步骤的端点,然后：

WHERE g.child IN (o.parent,o.child)

违反指示也会使您的起始条件有问题：

WHERE parent = 1

必须是

WHERE 1 IN (parent,child)

并且这两行(1,2)和(2,1)实际上是重复的……

评论后的补充解决方案

>忽略方向
>每条路径只能走一次边缘.
>使用ARRAY作为路径
>保存路径中的原始方向,而不是实际方向.

注意,这种方式(2,1)和(1,2)是有效的重复,但两者都可以在同一路径中使用.

我介绍了列叶,它保存了每一步的实际终点.

WITH RECURSIVE graph AS (
    SELECT CASE WHEN parent = 1 THEN child ELSE parent END AS leaf,ARRAY[ROW(parent,child)] AS path,0 AS depth
    FROM   ownership
    WHERE  1 in (child,parent)

    UNION ALL
    SELECT CASE WHEN o.parent = g.leaf THEN o.child ELSE o.parent END -- AS leaf,path || ROW(o.parent,o.child) -- AS path,depth + 1 -- AS depth
    FROM   graph g
    JOIN   ownership o ON g.leaf in (o.parent,o.child) 
    AND    ROW(o.parent,o.child) <> ALL(path)
    )
SELECT *
FROM   graph

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

3/3

首页