[發明專利]一種面向關系型數據庫的圖查詢方法

有效

• 申請號: 201710055713.1
• 申請日: 2017-01-25
• 公開（公告）號: CN106874422B
• 公開（公告）日: 2019-07-26
• 發明（設計）人: 漆桂林;孫松;張曉
• 申請（專利權）人: 東南大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/22;G06F16/242
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 楊曉玲

1.一種面向關系型數據庫的圖查詢方法，其特征在于，該方法包括如下步驟：

步驟1)對目標關系型數據做離線處理，即按照以下轉換規則將關系型數據轉換成圖結構數據：

a)針對關系型數據庫中所有表、元組，創建表節點和元組節點；

b)針對關系型數據庫中每個元組下的每個列值不為空的列創建屬性節點；

c)對于關系型數據中的外鍵引用、二元關系，創建邊來關聯對應的節點；

在創建節點和邊后按照如下方式生成對應的標識符：

a)取表名作為表節點的標識符；

b)手動指定元組的標識符列；

c)取元組對應的列值作為相應列節點的標識符；

d)取二元關系的表名作為對應邊的標識符；

e)取被引用列的名稱作為外鍵引用邊對應的標識符；

所述二元關系是指關系表有且僅有兩個不同的外鍵，且分別指向關系表s和關系表t中的某個屬性，則該關系表可轉化為關系表s和t之間的一個二元關系；

步驟2)離線構建圖數據索引，具體為：遍歷步驟1)生成的圖結構數據，針對圖結構數據中每個節點、邊，在索引文件中插入一條索引記錄；

步驟3)用戶首先構建圖查詢，所述圖查詢中包括命名節點、目標節點，節點之間用邊來連接，所述命名節點需要加上標識，所述目標節點不需要加上標識，然后利用用戶輸入的詞匯構建的查詢表示成一個有向圖，一個查詢表示成如下的一個五元組；

Q＝(V_Q,E_Q,L_Q,M_Q,T_Q)

其中，V_Q表示查詢中的命名節點集合，命名節點是指節點上有標簽來標識的節點；E_Q為圖查詢中包括的所有邊；L_Q為所有標簽的集合，即無論是節點還是邊的標簽都來自這個集合；M_Q表示圖查詢中包含的中間節點，采用標識“*”來表示；T_Q表示圖查詢中所有的目標查詢節點，這些節點是用戶通過查詢數據想得到的信息，用“？”表示；

步驟4)對用戶構建的圖查詢中的每個節點，通過查詢索引來得到每個節點對應的候選匹配節點集合；

步驟5)通過Top-k匹配算法，在候選匹配項的基礎上搜索與圖查詢近似匹配度最高的k個子圖并返回給用戶。

2.根據權利要求1所述的一種面向關系型數據庫的圖查詢方法，其特征在于，所述步驟1)中構建的圖結構數據存儲在neo4j圖數據庫中。

3.根據權利要求1所述的一種面向關系型數據庫的圖查詢方法，其特征在于，所述步驟2)中用Lucene來構建圖數據索引。

4.根據權利要求1、2或3所述的一種面向關系型數據庫的圖查詢方法，其特征在于，所述步驟3)中，圖查詢中還包括中間節點，所述中間節點不需要加上標識。

5.根據權利要求1、2或3所述的一種面向關系型數據庫的圖查詢方法，其特征在于，所述步驟5)中的Top-k圖匹配算法包括計算圖之間的結構相似度和圖上節點或邊的字符串相似度，然后通過加權計算得到近似匹配度，其中k是由用戶配置的子圖個數。