背景
在樹形遞歸查詢這篇文章，我記錄了使用CTE語(yǔ)法查詢樹形結(jié)構(gòu)的辦法。在一個(gè)樹形結(jié)構(gòu)中，每一個(gè)節(jié)點(diǎn)最多有一個(gè)上級(jí)，可以有任意個(gè)數(shù)的下級(jí)。
在實(shí)際場(chǎng)景中，我們還會(huì)遇到對(duì)圖(graph）的查詢，圖和樹的最大區(qū)別是，圖的節(jié)點(diǎn)可以有任意個(gè)數(shù)的上級(jí)和下級(jí)。如下圖所示
因?yàn)閳D可能存在loop結(jié)構(gòu)（上圖紅色箭頭），所以在使用CTE遞歸的過(guò)程中，必須要破環(huán)（break loop），否則算法就會(huì)進(jìn)入無(wú)限遞歸，永不結(jié)束。
存儲(chǔ)和查詢圖結(jié)構(gòu)，目前當(dāng)紅數(shù)據(jù)庫(kù)是neo4j，但是當(dāng)數(shù)據(jù)量只有十幾萬(wàn)條的時(shí)候，PostgreSQL完全可以勝任。
構(gòu)造樣本數(shù)據(jù)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
-- 每一條有向關(guān)系邊都存在上游，下游兩個(gè)節(jié)點(diǎn)drop table if exists demo.t_rel;create table if not exists demo.t_rel(up int , down int);-- 唯一約束，避免插入相同的關(guān)系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);-- 構(gòu)造一條環(huán)數(shù)據(jù)，7-2-4-7delete from demo.t_rel where up=4 and down=7;insert into demo.t_rel values(4,7); |
指定節(jié)點(diǎn)的下級(jí)
常見的一個(gè)場(chǎng)景是，給定一個(gè)節(jié)點(diǎn)，查詢這個(gè)節(jié)點(diǎn)的所有下級(jí)節(jié)點(diǎn)和路徑。使用破環(huán)的算法關(guān)鍵如下
- 使用數(shù)組保存當(dāng)前的路徑信息。
- 計(jì)算下一個(gè)節(jié)點(diǎn)之前，判斷該節(jié)點(diǎn)是否已經(jīng)存在于路徑上。如果是，就說(shuō)明該點(diǎn)是環(huán)的起點(diǎn)，必須排除這個(gè)節(jié)點(diǎn)來(lái)達(dá)到破環(huán)的效果。
- 起始節(jié)點(diǎn)和最大深度，都是可選的。如果忽略這兩個(gè)條件，就會(huì)返回完整的圖信息。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
with recursive downstream as( select 1 as lvl, r.up, r.down, -- 保存當(dāng)前路徑 array[]::int[] || r.up || r.down as trace from demo.t_rel r where r.up = 7 -- 指定起點(diǎn) 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é)點(diǎn)7為開始，返回下級(jí)的所有節(jié)點(diǎn)和路徑信息，如下。
|
1
2
3
4
5
6
7
|
-- 可以看到并沒有包括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é)點(diǎn)的所有關(guān)聯(lián)
在社交網(wǎng)絡(luò)的場(chǎng)景中，我們根據(jù)一個(gè)特定的節(jié)點(diǎn)，查詢所有的關(guān)系網(wǎng)。在本文的樣本數(shù)據(jù)中，我們的需求就變成，同時(shí)查詢指定節(jié)點(diǎn)的所有上級(jí)和下級(jí)。
為了方便后面的測(cè)試，我們封裝一個(gè)函數(shù)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
drop function if exists f_get_rel;/*取得某個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)節(jié)點(diǎn)，和路徑信息。@start_node 起始節(jié)點(diǎn)。@direct_flag 查詢方向，-1：查找上級(jí)；1：查找下級(jí)； 0：查找上下級(jí)；@max_depth 遞歸深度，即查找最多幾級(jí)關(guān)系。*/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; |
測(cè)試一下，查詢節(jié)點(diǎn)7的所有3度關(guān)聯(lián)節(jié)點(diǎn)信息，如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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) |
圖形顯示結(jié)果
ECharts模板
在沒有集成圖形界面之前，使用ECharts的示例代碼（地址），可以直觀的查看關(guān)系圖譜。對(duì)官方樣表進(jìn)行微調(diào)之后，代碼如下
注意 代碼中的 data 和 links 部分需要進(jìn)行替換
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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ù)
構(gòu)造 data 部分
|
1
2
3
4
5
6
7
8
9
|
-- 根據(jù)節(jié)點(diǎn)的關(guān)聯(lián)點(diǎn)數(shù)量，設(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 ngroup by n.nodeorder by 1; |
構(gòu)造 links 部分
|
1
2
3
|
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) rorder by r.up_node ; |
圖形顯示
把構(gòu)造的data和links替換到ECharts代碼里面
查詢節(jié)點(diǎn)7的所有2度關(guān)聯(lián)節(jié)點(diǎn)信息，結(jié)果顯示如下
查詢節(jié)點(diǎn)7的所有關(guān)聯(lián)節(jié)點(diǎn)信息（不限層級(jí)數(shù)），結(jié)果顯示如下
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)服務(wù)器之家的支持。
原文鏈接：https://juejin.im/post/5ddfb9b1518825434771d0fc
