PostgreSQL圖(graph）的遞歸查詢實例

背景

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

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

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

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

構造樣本數據

1. -- 每一條有向關系邊都存在上游，下游兩個節點
2. drop table if exists demo.t_rel;
3. create table if not exists demo.t_rel(up int , down int);
4.  
5. -- 唯一約束，避免插入相同的關系
6. alter table demo.t_rel add constraint udx_t_rel unique (up, down);
7.  
8. insert into demo.t_rel values(6,5),(3,7),(5,1),(1,2),(5,2),(5,7),(7,2),(2,4),(7,4);
9.  
10. -- 構造一條環數據，7-2-4-7
11. delete from demo.t_rel where up=4 and down=7;
12. insert into demo.t_rel values(4,7);

遞歸查詢

指定節點的下級

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

• 使用數組保存當前的路徑信息。
• 計算下一個節點之前，判斷該節點是否已經存在于路徑上。如果是，就說明該點是環的起點，必須排除這個節點來達到破環的效果。
• 起始節點和最大深度，都是可選的。如果忽略這兩個條件，就會返回完整的圖信息。

1. with recursive
2. downstream as
3. (
4. select 1 as lvl, r.up, r.down,
5. -- 保存當前路徑
6. array[]::int[] || r.up || r.down as trace
7. from demo.t_rel r
8. where r.up = 7 -- 指定起點
9. union all
10. select ds.lvl +1, r.up, r.down, ds.trace || r.down
11. from demo.t_rel r , downstream ds
12. where r.up = ds.down
13. -- 破環
14. and not r.down = any(ds.trace)
15. and ds.lvl < 20 -- 最大深度
16. )
17. select * from downstream ds;

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

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

指定節點的所有關聯

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

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

1. drop function if exists f_get_rel;
2.  
3. /*
4. 取得某個節點的相關聯節點，和路徑信息。
5. @start_node 起始節點。
6. @direct_flag 查詢方向，-1：查找上級；1：查找下級； 0：查找上下級；
7. @max_depth 遞歸深度，即查找最多幾級關系。
8. */
9. create or replace function f_get_rel(start_node int, direct_flag int=1, max_depth int=20)
10. returns table (direct int, cur_depth int, up_node int, down_node int, trace int[])
11. as $$
12. begin
13.  
14. return query
15. with recursive
16. downstream as
17. (
18. select 1 as lvl, r.up, r.down, array[]::int[] || r.up || r.down as trace
19. from demo.t_rel r
20. where r.up = start_node
21. and direct_flag in (0, 1)
22. union all
23. select ds.lvl +1, r.up, r.down, ds.trace || r.down
24. from demo.t_rel r , downstream ds
25. where r.up = ds.down
26. and not r.down = any(ds.trace)
27. and ds.lvl < max_depth
28. ),
29. upstream as
30. (
31. select 1 as lvl, r.up, r.down, array[]::int[] || r.up || r.down as trace
32. from demo.t_rel r
33. where r.down = start_node
34. and direct_flag in (0, -1)
35. union all
36. select us.lvl +1, r.up, r.down, r.up || us.trace
37. from demo.t_rel r , upstream us
38. where r.down = us.up
39. and not r.up = any(us.trace)
40. and us.lvl < max_depth
41. )
42. select -1, us.* from upstream us
43. union all
44. select 1, ds.* from downstream ds
45. order by 1 desc, lvl, up, down
46. ;
47.  
48. end;
49. $$ language plpgsql strict;

測試一下，查詢節點7的所有3度關聯節點信息，如下

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

圖形顯示結果

ECharts模板

在沒有集成圖形界面之前，使用ECharts的示例代碼（地址），可以直觀的查看關系圖譜。對官方樣表進行微調之后，代碼如下
注意 代碼中的 data 和 links 部分需要進行替換

1. option = {
2. title: {
3. text: '數據圖譜'
4. },
5. tooltip: {},
6. animationDurationUpdate: 1500,
7. animationEasingUpdate: 'quinticInOut',
8. series : [
9. {
10. type: 'graph',
11. layout: 'force',
12. force: {
13. repulsion: 1000
14. },
15. focusNodeAdjacency: true,
16. symbolSize: 30,
17. roam: true,
18. label: {
19. normal: {
20. show: true
21. }
22. },
23. edgeSymbol: ['circle', 'arrow'],
24. edgeSymbolSize: [4, 10],
25. edgeLabel: {
26. normal: {
27. textStyle: {
28. fontSize: 20
29. }
30. }
31. },
32. data: [
33. { name:"2", draggable: true, symbolSize:20},
34. ],
35. links: [
36. { source:"2", target:"4"},
37. ],
38.  
39. }
40. ]
41. };

造顯示用數據

構造 data 部分

1. -- 根據節點的關聯點數量，設置圖形大小
2. with rel as (select * from f_get_rel(7,0,2)),
3. up_nodes as (select up_node, count(distinct down_node) as out_cnt from rel group byup_node),
4. down_nodes as (select down_node, count(distinct up_node) as in_cnt from rel group bydown_node),
5. node_cnt as ( select up_node as node, out_cnt as cnt from up_nodes union all select * fromdown_nodes )
6. select '{ name:"' || n.node || '", draggable: true, symbolSize:' || sum(n.cnt) * 10 || '},' asnode
7. from node_cnt n
8. group by n.node
9. order by 1;

構造 links 部分

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

圖形顯示

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

查詢節點7的所有2度關聯節點信息，結果顯示如下

查詢節點7的所有關聯節點信息（不限層級數），結果顯示如下

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對我們的支持。