[發明專利]基于緩存表構建可達圖的方法

有效

• 申請號: 201910762401.3
• 申請日: 2019-08-19
• 公開（公告）號: CN110543494B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 陳睿;劉國威;何忠毓;周亞曦;李玲;趙雅利
• 申請（專利權）人: 湖南麟淇網絡科技股份有限公司
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2458;G06F16/28
• 代理公司: 長沙科明知識產權代理事務所(普通合伙) 43203
• 代理人: 吳蘭秀

本發明涉及一種基于緩存表構建可達圖的方法，其包括以下步驟：步驟一，構造緩存表：在圖形數據庫或內存中建立一張關系緩存表；步驟二，使用緩存表構建可達圖；步驟三，更新緩存表。本發明適用于以關系數據庫存儲圖構建該圖中節點的可達樹的場景，并存在大量的基于同一個圖的可達樹構建需求。

技術領域

本發明涉及可達圖構建技術領域，尤其涉及一種基于緩存表構建可達圖的方法。

背景技術

目前大數據使用越來越廣泛，我們期望基于大數據來構建可達圖，但是傳統的關系數據庫是基于記錄的，不能夠快速的構建出可達圖；實踐當中，只有很少的節點被多次的訪問，因此本發明通過在構建數據庫時在圖形數據庫或內存中增加了一個緩存表來提高生成可達圖的效率。

傳統的節點關系表如下:

序號	始點	終點
1	A	B
2	A	C
3	B	C
4	C	D
5	F	E
6	F	G

基于上述的數據結構，傳統方法構建以節點A為根的可達圖時，首先查詢節點關系表始點列的值等于A的行，查詢到節點B和節點 C與節點A可達；繼續查詢節點關系表中始點列為B或C的行，查詢到了節點D可由節點C到達；下一步繼續查詢節點關系表中始點列為節點D行，沒有檢索到新的可達節點，算法結束。

按照上述過程，構建以節點A為根的可達樹最少要進行N次數據庫查詢(其中N為該可達樹的節點數)。

發明內容

針對現有技術的不足，本發明提供一種基于緩存表構建可達圖的方法，適用于以關系數據庫存儲圖構建該圖中節點的可達樹的場景，并存在大量的基于同一個圖的可達樹構建需求。