域名預訂/競價，好“米”不錯過

這篇文章主要給大家介紹了關于PostgreSQL圖(graph）的遞歸查詢的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用PostgreSQL具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧

背景

在樹形遞歸查詢這篇文章，我記錄了使用CTE語法查詢樹形結構的辦法。在一個樹形結構中，每一個節(jié)點最多有一個上級，可以有任意個數(shù)的下級。

在實際場景中，我們還會遇到對圖(graph）的查詢，圖和樹的最大區(qū)別是，圖的節(jié)點可以有任意個數(shù)的上級和下級。如下圖所示

因為圖可能存在loop結構（上圖紅色箭頭），所以在使用CTE遞歸的過程中，必須要破環(huán)（break loop），否則算法就會進入無限遞歸，永不結束。

存儲和查詢圖結構，目前當紅數(shù)據(jù)庫是neo4j，但是當數(shù)據(jù)量只有十幾萬條的時候，PostgreSQL完全可以勝任。

構造樣本數(shù)據(jù)

-- 每一條有向關系邊都存在上游，下游兩個節(jié)點
drop table if exists demo.t_rel;
create table if not exists demo.t_rel(up int , down int);

-- 唯一約束，避免插入相同的關系
alter table demo.t_rel add constraint udx_t_rel unique (up, down);

insert into demo.t_rel values(6,5),(3,7),(5,1),(1,2),(5,2),(5,7),(7,2),(2,4),(7,4);

-- 構造一條環(huán)數(shù)據(jù)，7-2-4-7
delete from demo.t_rel where up=4 and down=7;
insert into demo.t_rel values(4,7);

遞歸查詢

with recursive
downstream as
(
 select 1 as lvl, r.up, r.down,
   -- 保存當前路徑
   array[]::int[] || r.up || r.down as trace
  from demo.t_rel r 
 where r.up = 7 -- 指定起點
 union all
 select ds.lvl +1, r.up, r.down, ds.trace || r.down
  from demo.t_rel r , downstream ds
 where r.up = ds.down
  -- 破環(huán)
  and not r.down = any(ds.trace)
  and ds.lvl < 20 -- 最大深度
)
select * from downstream ds;

指定節(jié)點的下級

常見的一個場景是，給定一個節(jié)點，查詢這個節(jié)點的所有下級節(jié)點和路徑。使用破環(huán)的算法關鍵如下

使用數(shù)組保存當前的路徑信息。

計算下一個節(jié)點之前，判斷該節(jié)點是否已經(jīng)存在于路徑上。如果是，就說明該點是環(huán)的起點，必須排除這個節(jié)點來達到破環(huán)的效果。

起始節(jié)點和最大深度，都是可選的。如果忽略這兩個條件，就會返回完整的圖信息。

with recursive
downstream as
(
 select 1 as lvl, r.up, r.down,
   -- 保存當前路徑
   array[]::int[] || r.up || r.down as trace
  from demo.t_rel r 
 where r.up = 7 -- 指定起點
 union all
 select ds.lvl +1, r.up, r.down, ds.trace || r.down
  from demo.t_rel r , downstream ds
 where r.up = ds.down
  -- 破環(huán)
  and not r.down = any(ds.trace)
  and ds.lvl < 20 -- 最大深度
)
select * from downstream ds;

上面以節(jié)點7為開始，返回下級的所有節(jié)點和路徑信息，如下。

-- 可以看到并沒有包括7-2-4-7這條環(huán)。
 lvl | up | down | trace
-----+----+------+---------
 1 | 7 | 2 | {7,2}
 1 | 7 | 4 | {7,4}
 2 | 2 | 4 | {7,2,4}
(3 rows)

指定節(jié)點的所有關聯(lián)

在社交網(wǎng)絡的場景中，我們根據(jù)一個特定的節(jié)點，查詢所有的關系網(wǎng)。在本文的樣本數(shù)據(jù)中，我們的需求就變成，同時查詢指定節(jié)點的所有上級和下級。

為了方便后面的測試，我們封裝一個函數(shù)

drop function if exists f_get_rel;

/*
取得某個節(jié)點的相關聯(lián)節(jié)點，和路徑信息。
@start_node 起始節(jié)點。
@direct_flag 查詢方向，-1：查找上級；1：查找下級； 0：查找上下級；
@max_depth 遞歸深度，即查找最多幾級關系。
*/
create or replace function f_get_rel(start_node int, direct_flag int=1, max_depth int=20)
 returns table (direct int, cur_depth int, up_node int, down_node int, trace int[])
as $$
begin

 return query
  with recursive
  downstream as
  (
   select 1 as lvl, r.up, r.down, array[]::int[] || r.up || r.down as trace
    from demo.t_rel r
   where r.up = start_node
    and direct_flag in (0, 1)
   union all
   select ds.lvl +1, r.up, r.down, ds.trace || r.down
    from demo.t_rel r , downstream ds
   where r.up = ds.down
    and not r.down = any(ds.trace)
    and ds.lvl < max_depth
  ),
  upstream as
  (
   select 1 as lvl, r.up, r.down, array[]::int[] || r.up || r.down as trace
    from demo.t_rel r
   where r.down = start_node
    and direct_flag in (0, -1)
   union all
   select us.lvl +1, r.up, r.down, r.up || us.trace
    from demo.t_rel r , upstream us
   where r.down = us.up
    and not r.up = any(us.trace)
    and us.lvl < max_depth
  )
  select -1, us.* from upstream us
   union all
  select 1, ds.* from downstream ds
  order by 1 desc, lvl, up, down
 ;

end;
$$ language plpgsql strict;

測試一下，查詢節(jié)點7的所有3度關聯(lián)節(jié)點信息，如下

dap=# select * from demo.f_get_rel(7,0,3);
 direct | cur_depth | up_node | down_node | trace
--------+-----------+---------+-----------+-----------
  1 |   1 |  7 |   2 | {7,2}
  1 |   1 |  7 |   4 | {7,4}
  1 |   2 |  2 |   4 | {7,2,4}
  -1 |   1 |  3 |   7 | {3,7}
  -1 |   1 |  4 |   7 | {4,7}
  -1 |   1 |  5 |   7 | {5,7}
  -1 |   2 |  2 |   4 | {2,4,7}
  -1 |   2 |  6 |   5 | {6,5,7}
  -1 |   3 |  1 |   2 | {1,2,4,7}
  -1 |   3 |  5 |   2 | {5,2,4,7}
(10 rows)

圖形顯示結果

ECharts模板

在沒有集成圖形界面之前，使用ECharts的示例代碼（地址），可以直觀的查看關系圖譜。對官方樣表進行微調(diào)之后，代碼如下

注意 代碼中的 data 和 links 部分需要進行替換

option = {
 title: {
  text: '數(shù)據(jù)圖譜'
 },
 tooltip: {},
 animationDurationUpdate: 1500,
 animationEasingUpdate: 'quinticInOut',
 series : [
  {
   type: 'graph',
   layout: 'force',
   force: {
     repulsion: 1000
    },
   focusNodeAdjacency: true,
   symbolSize: 30,
   roam: true,
   label: {
    normal: {
     show: true
    }
   },
   edgeSymbol: ['circle', 'arrow'],
   edgeSymbolSize: [4, 10],
   edgeLabel: {
    normal: {
     textStyle: {
      fontSize: 20
     }
    }
   },
   data: [
    { name:"2", draggable: true, symbolSize:20},
   ],
   links: [
    { source:"2", target:"4"},
   ],

  }
 ]
};

造顯示用數(shù)據(jù)

構造 data 部分

-- 根據(jù)節(jié)點的關聯(lián)點數(shù)量，設置圖形大小
with rel as (select * from f_get_rel(7,0,2)),
 up_nodes as (select up_node, count(distinct down_node) as out_cnt from rel group by up_node),
 down_nodes as (select down_node, count(distinct up_node) as in_cnt from rel group by down_node),
 node_cnt as ( select up_node as node, out_cnt as cnt from up_nodes union all select * from down_nodes )
select '{ name:"' || n.node || '", draggable: true, symbolSize:' || sum(n.cnt) * 10 || '},' as node
 from node_cnt n
group by n.node
order by 1;

構造 links 部分

select distinct r.up_node, r.down_node, '{ source:"'|| r.up_node ||'", target:"'|| r.down_node ||'"},' as links
 from f_get_rel(7,0,3) r
order by r.up_node ;

圖形顯示

把構造的data和links替換到ECharts代碼里面

查詢節(jié)點7的所有2度關聯(lián)節(jié)點信息，結果顯示如下

查詢節(jié)點7的所有關聯(lián)節(jié)點信息（不限層級數(shù)），結果顯示如下

本文來自腳本之家，原文鏈接：https://www.jb51.net/article/176407.htm

申請創(chuàng)業(yè)報道，分享創(chuàng)業(yè)好點子。點擊此處，共同探討創(chuàng)業(yè)新機遇！