[發明專利]一種圖數據上的語義關聯搜索的查詢松弛方法

有效

• 申請號: 202010089733.2
• 申請日: 2020-02-13
• 公開（公告）號: CN113254718B
• 公開（公告）日: 2023-08-29
• 發明（設計）人: 李舒馨;程龔
• 申請（專利權）人: 南京大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;G06F40/30
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 奚銘

一種圖數據上的語義關聯搜索的查詢松弛方法，包含以下步驟：給定實體關聯圖和直徑約束，輸入一組查詢實體，分別計算它們的優先級，然后將實體，起始實體，優先級元組加入優先隊列中，只要優先隊列不為空，就取出隊首元組，對查詢實體進行驗證，計算它滿足距離條件的最大成功子查詢集合，更新最優解；如果當前實體的優先級已經無法得出更優的解，則終止，完成查詢。本發明解決了圖數據上給定直徑的情況下實體關聯搜索結果為空的問題，對查詢實體進行松弛，保證結果子查詢可以找到關聯。

技術領域

本發明屬于計算機技術領域，涉及圖搜索技術，為一種圖數據上的語義關聯搜索的查詢松弛方法。

背景技術

圖數據有著很好的表現力，例如RDF數據，它能夠直觀地展現實體，即圖上的點之間復雜的關系，被應用在越來越多的領域中。特別地，圖數據很適合用來回答關聯查詢。也就是說，給定圖上的幾個查詢實體，查詢結果是能夠包含這幾個查詢實體的連通子圖，該子圖表示的實體及其關系被稱為語義關聯。

圖上有很多搜索技術，比較基本的有深度優先搜索、廣度優先搜索、以及這兩種搜索的一些變種。在處理與圖搜索相關的問題時，往往都離不開這兩種方法。

一般地，圖數據是一個有限的有向圖，也稱為實體關聯圖，記為G＝E,A,R,l。其中，E是一個實體集，在圖中表示為頂點；A是一個弧集，每條弧a∈A的方向由尾節點t(a)指向頭節點h(a)，t(a)∈E,h(a)∈E；R是一個關系集；l:A→R代表l標記了弧a(a∈A)，并且關系l(a)∈R。對于給定的非空查詢實體集合如果一個語義關聯x＝E_x,A_x是包含頂點E_x和弧A_x的圖G的子圖，則它滿足以下條件：

(1)它的頂點包含所有的查詢實體，即

(2)它是連通的；

(3)它是最小的，即它的子集都無法滿足以上(1)(2)兩個條件。

根據以上條件，容易得出，語義關聯相當于一棵樹，并且葉子節點都是查詢實體。語義關聯的直徑為任意兩個實體間的最大距離(跳數)。

現有技術在搜索語義關聯時通常的要求是結構緊湊的，比如限制語義關聯結果中實體的數量或是子圖的直徑。一個緊湊的關聯往往能夠展現實體間更緊密且更有意義的關系，這也符合用戶的需求，但這會造成一個問題，限制了語義關聯的大小后，可能無法找到連接所有查詢實體的子圖，因此這些方法給出的結果有可能為空，這給用戶造成了不好的體驗。為了避免空結果的產生，需要針對語義關聯搜索進行查詢松弛。

查詢松弛是一種能夠增加信息檢索結果數量的技術。用于應對在進行查詢時，如果約束過多或過嚴，可能導致結果為空的情況。查詢松弛正是針對這種情況，適當地對約束進行放松，使結果不再為空。例如，用戶在使用搜索引擎時，過多的關鍵詞可能導致搜索結果過少甚至沒有，適當地對關鍵詞進行刪減，往往能增加搜索結果，提高搜索效果。在圖數據上限制語義關聯的大小，搜索結果為空時，情況是類似的，適當地刪除若干查詢實體，保證剩下的查詢實體能夠找到關聯。

發明內容

本發明要解決的問題是：針對圖數據上語義關聯搜索結果為空的情況，需要對關聯查詢進行松弛，從而保證松弛后的子查詢能夠搜索到關聯。

本發明的技術方案為：一種圖數據上的語義關聯搜索的查詢松弛方法，將語義關聯看作樹形，樹中的葉子節點都為實體，其中用于搜索的實體為查詢實體，語義關聯的直徑為任意兩個實體間的最大距離，對于給定的實體關聯圖G和直徑約束D，以及非空查詢實體集合Q，計算出Q的最大成功子查詢集合Q_max用于搜索，實現查詢松弛；