sql – 行使递归查询会见有向图,就仿佛它是一个无向图

>行使字符串记录路径.比行数组更小更快.仍包括全部须要信息.可是,也许会行使很是大的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

（编辑：湖南网）

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